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