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