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