lib/CodeGen/RegAllocSimple.cpp

   1 //===-- RegAllocSimple.cpp - A simple generic register allocator ----------===//
   2 //
   3 // This file implements a simple register allocator. *Very* simple.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/CodeGen/MachineFunction.h"
   8 #include "llvm/CodeGen/MachineInstr.h"
   9 #include "llvm/CodeGen/SSARegMap.h"
  10 #include "llvm/Target/MachineInstrInfo.h"
  11 #include "llvm/Target/TargetMachine.h"
  12 #include "Support/Statistic.h"
  13 #include <iostream>
  14 #include <set>
  15
  16 namespace {
  17   Statistic<> NumSpilled ("ra-simple", "Number of registers spilled");
  18   Statistic<> NumReloaded("ra-simple", "Number of registers reloaded");
  19
  20   class RegAllocSimple : public FunctionPass {
  21     TargetMachine &TM;
  22     MachineFunction *MF;
  23     const MRegisterInfo *RegInfo;
  24     unsigned NumBytesAllocated;
  25
  26     // Maps SSA Regs => offsets on the stack where these values are stored
  27     std::map<unsigned, unsigned> VirtReg2OffsetMap;
  28
  29     // RegsUsed - Keep track of what registers are currently in use.
  30     std::set<unsigned> RegsUsed;
  31
  32     // RegClassIdx - Maps RegClass => which index we can take a register
  33     // from. Since this is a simple register allocator, when we need a register
  34     // of a certain class, we just take the next available one.
  35     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
  36
  37   public:
  38
  39     RegAllocSimple(TargetMachine &tm)
  40       : TM(tm), RegInfo(tm.getRegisterInfo()) {
  41       RegsUsed.insert(RegInfo->getFramePointer());
  42       RegsUsed.insert(RegInfo->getStackPointer());
  43
  44       cleanupAfterFunction();
  45     }
  46
  47     bool runOnFunction(Function &Fn) {
  48       return runOnMachineFunction(MachineFunction::get(&Fn));
  49     }
  50
  51     virtual const char *getPassName() const {
  52       return "Simple Register Allocator";
  53     }
  54
  55   private:
  56     /// runOnMachineFunction - Register allocate the whole function
  57     bool runOnMachineFunction(MachineFunction &Fn);
  58
  59     /// AllocateBasicBlock - Register allocate the specified basic block.
  60     void AllocateBasicBlock(MachineBasicBlock &MBB);
  61
  62     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  63     /// in predecessor basic blocks.
  64     void EliminatePHINodes(MachineBasicBlock &MBB);
  65
  66     /// EmitPrologue/EmitEpilogue - Use the register info object to add a
  67     /// prologue/epilogue to the function and save/restore any callee saved
  68     /// registers we are responsible for.
  69     ///
  70     void EmitPrologue();
  71     void EmitEpilogue(MachineBasicBlock &MBB);
  72
  73
  74     /// getStackSpaceFor - This returns the offset of the specified virtual
  75     /// register on the stack, allocating space if neccesary.
  76     unsigned getStackSpaceFor(unsigned VirtReg,
  77                               const TargetRegisterClass *regClass);
  78
  79     /// Given a virtual register, return a compatible physical register that is
  80     /// currently unused.
  81     ///
  82     /// Side effect: marks that register as being used until manually cleared
  83     ///
  84     unsigned getFreeReg(unsigned virtualReg);
  85
  86     /// Returns all `borrowed' registers back to the free pool
  87     void clearAllRegs() {
  88       RegClassIdx.clear();
  89     }
  90
  91     /// Invalidates any references, real or implicit, to physical registers
  92     ///
  93     void invalidatePhysRegs(const MachineInstr *MI) {
  94       unsigned Opcode = MI->getOpcode();
  95       const MachineInstrDescriptor &Desc = TM.getInstrInfo().get(Opcode);
  96       if (const unsigned *regs = Desc.ImplicitUses)
  97         while (*regs)
  98           RegsUsed.insert(*regs++);
  99
 100       if (const unsigned *regs = Desc.ImplicitDefs)
 101         while (*regs)
 102           RegsUsed.insert(*regs++);
 103     }
 104
 105     void cleanupAfterFunction() {
 106       VirtReg2OffsetMap.clear();
 107       NumBytesAllocated = 4;   // FIXME: This is X86 specific
 108     }
 109
 110     /// Moves value from memory into that register
 111     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 112                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 113
 114     /// Saves reg value on the stack (maps virtual register to stack value)
 115     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 116                       unsigned VirtReg, unsigned PhysReg);
 117   };
 118
 119 }
 120
 121 /// getStackSpaceFor - This allocates space for the specified virtual
 122 /// register to be held on the stack.
 123 unsigned RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
 124                                           const TargetRegisterClass *regClass) {
 125   // Find the location VirtReg would belong...
 126   std::map<unsigned, unsigned>::iterator I =
 127     VirtReg2OffsetMap.lower_bound(VirtReg);
 128
 129   if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
 130     return I->second;          // Already has space allocated?
 131
 132   unsigned RegSize = regClass->getDataSize();
 133
 134   // Align NumBytesAllocated.  We should be using TargetData alignment stuff
 135   // to determine this, but we don't know the LLVM type associated with the
 136   // virtual register.  Instead, just align to a multiple of the size for now.
 137   NumBytesAllocated += RegSize-1;
 138   NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
 139
 140   // Assign the slot...
 141   VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
 142
 143   // Reserve the space!
 144   NumBytesAllocated += RegSize;
 145   return NumBytesAllocated-RegSize;
 146 }
 147
 148 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 149   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(virtualReg);
 150
 151   unsigned regIdx = RegClassIdx[RC]++;
 152   assert(regIdx < RC->getNumRegs() && "Not enough registers!");
 153   unsigned physReg = RC->getRegister(regIdx);
 154
 155   if (RegsUsed.find(physReg) == RegsUsed.end())
 156     return physReg;
 157   else
 158     return getFreeReg(virtualReg);
 159 }
 160
 161 unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
 162                                        MachineBasicBlock::iterator &I,
 163                                        unsigned VirtReg) {
 164   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
 165   unsigned stackOffset = getStackSpaceFor(VirtReg, RC);
 166   unsigned PhysReg = getFreeReg(VirtReg);
 167
 168   // Add move instruction(s)
 169   ++NumReloaded;
 170   RegInfo->loadRegOffset2Reg(MBB, I, PhysReg, RegInfo->getFramePointer(),
 171                              -stackOffset, RC);
 172   return PhysReg;
 173 }
 174
 175 void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
 176                                   MachineBasicBlock::iterator &I,
 177                                   unsigned VirtReg, unsigned PhysReg)
 178 {
 179   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
 180   unsigned stackOffset = getStackSpaceFor(VirtReg, RC);
 181
 182   // Add move instruction(s)
 183   ++NumSpilled;
 184   RegInfo->storeReg2RegOffset(MBB, I, PhysReg, RegInfo->getFramePointer(),
 185                               -stackOffset, RC);
 186 }
 187
 188
 189 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 190 /// predecessor basic blocks.
 191 ///
 192 void RegAllocSimple::EliminatePHINodes(MachineBasicBlock &MBB) {
 193   const MachineInstrInfo &MII = TM.getInstrInfo();
 194
 195   while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
 196     MachineInstr *MI = MBB.front();
 197     // Unlink the PHI node from the basic block... but don't delete the PHI yet
 198     MBB.erase(MBB.begin());
 199
 200     DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 201     assert(MI->getOperand(0).isVirtualRegister() &&
 202            "PHI node doesn't write virt reg?");
 203
 204     unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
 205
 206     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 207       MachineOperand &opVal = MI->getOperand(i-1);
 208
 209       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 210       // source path the phi
 211       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 212
 213       // Check to make sure we haven't already emitted the copy for this block.
 214       // This can happen because PHI nodes may have multiple entries for the
 215       // same basic block.  It doesn't matter which entry we use though, because
 216       // all incoming values are guaranteed to be the same for a particular bb.
 217       //
 218       // Note that this is N^2 in the number of phi node entries, but since the
 219       // # of entries is tiny, this is not a problem.
 220       //
 221       bool HaveNotEmitted = true;
 222       for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
 223         if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
 224           HaveNotEmitted = false;
 225           break;
 226         }
 227
 228       if (HaveNotEmitted) {
 229         MachineBasicBlock::iterator opI = opBlock.end();
 230         MachineInstr *opMI = *--opI;
 231
 232         // must backtrack over ALL the branches in the previous block
 233         while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
 234           opMI = *--opI;
 235
 236         // move back to the first branch instruction so new instructions
 237         // are inserted right in front of it and not in front of a non-branch
 238         //
 239         if (!MII.isBranch(opMI->getOpcode()))
 240           ++opI;
 241
 242         const TargetRegisterClass *RC =
 243           MF->getSSARegMap()->getRegClass(virtualReg);
 244
 245         // Retrieve the constant value from this op, move it to target
 246         // register of the phi
 247         if (opVal.isImmediate()) {
 248           RegInfo->moveImm2Reg(opBlock, opI, virtualReg,
 249                                (unsigned) opVal.getImmedValue(), RC);
 250         } else {
 251           RegInfo->moveReg2Reg(opBlock, opI, virtualReg,
 252                                opVal.getAllocatedRegNum(), RC);
 253         }
 254       }
 255     }
 256
 257     // really delete the PHI instruction now!
 258     delete MI;
 259   }
 260 }
 261
 262
 263 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
 264   // loop over each instruction
 265   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
 266     // Made to combat the incorrect allocation of r2 = add r1, r1
 267     std::map<unsigned, unsigned> Virt2PhysRegMap;
 268
 269     MachineInstr *MI = *I;
 270
 271     // a preliminary pass that will invalidate any registers that
 272     // are used by the instruction (including implicit uses)
 273     invalidatePhysRegs(MI);
 274
 275     // Loop over uses, move from memory into registers
 276     for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 277       MachineOperand &op = MI->getOperand(i);
 278
 279       if (op.isVirtualRegister()) {
 280         unsigned virtualReg = (unsigned) op.getAllocatedRegNum();
 281         DEBUG(std::cerr << "op: " << op << "\n");
 282         DEBUG(std::cerr << "\t inst[" << i << "]: ";
 283               MI->print(std::cerr, TM));
 284
 285         // make sure the same virtual register maps to the same physical
 286         // register in any given instruction
 287         unsigned physReg = Virt2PhysRegMap[virtualReg];
 288         if (physReg == 0) {
 289           if (op.opIsDef()) {
 290             if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 291               // must be same register number as the first operand
 292               // This maps a = b + c into b += c, and saves b into a's spot
 293               assert(MI->getOperand(1).isRegister()  &&
 294                      MI->getOperand(1).getAllocatedRegNum() &&
 295                      MI->getOperand(1).opIsUse() &&
 296                      "Two address instruction invalid!");
 297
 298               physReg = MI->getOperand(1).getAllocatedRegNum();
 299             } else {
 300               physReg = getFreeReg(virtualReg);
 301             }
 302             ++I;
 303             spillVirtReg(MBB, I, virtualReg, physReg);
 304             --I;
 305           } else {
 306             physReg = reloadVirtReg(MBB, I, virtualReg);
 307             Virt2PhysRegMap[virtualReg] = physReg;
 308           }
 309         }
 310         MI->SetMachineOperandReg(i, physReg);
 311         DEBUG(std::cerr << "virt: " << virtualReg <<
 312               ", phys: " << op.getAllocatedRegNum() << "\n");
 313       }
 314     }
 315     clearAllRegs();
 316   }
 317 }
 318
 319
 320 /// EmitPrologue - Use the register info object to add a prologue to the
 321 /// function and save any callee saved registers we are responsible for.
 322 ///
 323 void RegAllocSimple::EmitPrologue() {
 324   // Get a list of the callee saved registers, so that we can save them on entry
 325   // to the function.
 326   //
 327   MachineBasicBlock &MBB = MF->front();   // Prolog goes in entry BB
 328   MachineBasicBlock::iterator I = MBB.begin();
 329
 330   const unsigned *CSRegs = RegInfo->getCalleeSaveRegs();
 331   for (unsigned i = 0; CSRegs[i]; ++i) {
 332     const TargetRegisterClass *RegClass = RegInfo->getRegClass(CSRegs[i]);
 333     unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
 334
 335     // Insert the spill to the stack frame...
 336     RegInfo->storeReg2RegOffset(MBB, I,CSRegs[i],RegInfo->getFramePointer(),
 337                                 -Offset, RegClass);
 338     ++NumSpilled;
 339   }
 340
 341   // Add prologue to the function...
 342   RegInfo->emitPrologue(*MF, NumBytesAllocated);
 343 }
 344
 345
 346 /// EmitEpilogue - Use the register info object to add a epilogue to the
 347 /// function and restore any callee saved registers we are responsible for.
 348 ///
 349 void RegAllocSimple::EmitEpilogue(MachineBasicBlock &MBB) {
 350   // Insert instructions before the return.
 351   MachineBasicBlock::iterator I = MBB.end()-1;
 352
 353   const unsigned *CSRegs = RegInfo->getCalleeSaveRegs();
 354   for (unsigned i = 0; CSRegs[i]; ++i) {
 355     const TargetRegisterClass *RegClass = RegInfo->getRegClass(CSRegs[i]);
 356     unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
 357
 358     RegInfo->loadRegOffset2Reg(MBB, I, CSRegs[i],RegInfo->getFramePointer(),
 359                                -Offset, RegClass);
 360     --I;  // Insert in reverse order
 361     ++NumReloaded;
 362   }
 363
 364   RegInfo->emitEpilogue(MBB, NumBytesAllocated);
 365 }
 366
 367
 368 /// runOnMachineFunction - Register allocate the whole function
 369 ///
 370 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 371   DEBUG(std::cerr << "Machine Function " << "\n");
 372   MF = &Fn;
 373
 374   // First pass: eliminate PHI instructions by inserting copies into predecessor
 375   // blocks.
 376   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 377        MBB != MBBe; ++MBB)
 378     EliminatePHINodes(*MBB);
 379
 380   // Loop over all of the basic blocks, eliminating virtual register references
 381   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 382        MBB != MBBe; ++MBB)
 383     AllocateBasicBlock(*MBB);
 384
 385   // Round stack allocation up to a nice alignment to keep the stack aligned
 386   // FIXME: This is X86 specific!  Move to frame manager
 387   NumBytesAllocated = (NumBytesAllocated + 3) & ~3;
 388
 389   // Emit a prologue for the function...
 390   EmitPrologue();
 391
 392   const MachineInstrInfo &MII = TM.getInstrInfo();
 393
 394   // Add epilogue to restore the callee-save registers in each exiting block
 395   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 396        MBB != MBBe; ++MBB) {
 397     // If last instruction is a return instruction, add an epilogue
 398     if (MII.isReturn(MBB->back()->getOpcode()))
 399       EmitEpilogue(*MBB);
 400   }
 401
 402   cleanupAfterFunction();
 403   return true;
 404 }
 405
 406 Pass *createSimpleRegisterAllocator(TargetMachine &TM) {
 407   return new RegAllocSimple(TM);
 408 }