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