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) : TM(tm),
  64                                         RegInfo(tm.getRegisterInfo()),
  65                                         PhysRegClasses(RegInfo)
  66     {
  67       RegsUsed[RegInfo->getFramePointer()] = 1;
  68       RegsUsed[RegInfo->getStackPointer()] = 1;
  69
  70       cleanupAfterFunction();
  71     }
  72
  73     bool isAvailableReg(unsigned Reg) {
  74       // assert(Reg < MRegisterInfo::FirstVirtualReg && "...");
  75       return RegsUsed.find(Reg) == RegsUsed.end();
  76     }
  77
  78     ///
  79     unsigned allocateStackSpaceFor(unsigned VirtReg,
  80                                    const TargetRegisterClass *regClass);
  81
  82     /// Given size (in bytes), returns a register that is currently unused
  83     /// Side effect: marks that register as being used until manually cleared
  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 MachineInstrInfo &MII = TM.getInstrInfo();
  96       const MachineInstrDescriptor &Desc = MII.get(Opcode);
  97       const unsigned *regs = Desc.ImplicitUses;
  98       while (*regs)
  99         RegsUsed[*regs++] = 1;
 100
 101       regs = Desc.ImplicitDefs;
 102       while (*regs)
 103         RegsUsed[*regs++] = 1;
 104     }
 105
 106     void cleanupAfterFunction() {
 107       VirtReg2OffsetMap.clear();
 108       SSA2PhysRegMap.clear();
 109       NumBytesAllocated = 4;   /* FIXME: This is X86 specific */
 110     }
 111
 112     /// Moves value from memory into that register
 113     MachineBasicBlock::iterator
 114     moveUseToReg (MachineBasicBlock *MBB,
 115                   MachineBasicBlock::iterator I, unsigned VirtReg,
 116                   unsigned &PhysReg);
 117
 118     /// Saves reg value on the stack (maps virtual register to stack value)
 119     MachineBasicBlock::iterator
 120     saveVirtRegToStack (MachineBasicBlock *MBB,
 121                         MachineBasicBlock::iterator I, unsigned VirtReg,
 122                         unsigned PhysReg);
 123
 124     MachineBasicBlock::iterator
 125     savePhysRegToStack (MachineBasicBlock *MBB,
 126                         MachineBasicBlock::iterator I, unsigned PhysReg);
 127
 128     /// runOnFunction - Top level implementation of instruction selection for
 129     /// the entire function.
 130     ///
 131     bool runOnMachineFunction(MachineFunction &Fn);
 132
 133     bool runOnFunction(Function &Fn) {
 134       return runOnMachineFunction(MachineFunction::get(&Fn));
 135     }
 136   };
 137
 138 }
 139
 140 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
 141                                             const TargetRegisterClass *regClass)
 142 {
 143   if (VirtReg2OffsetMap.find(VirtReg) == VirtReg2OffsetMap.end()) {
 144     unsigned RegSize = regClass->getDataSize();
 145
 146     // Align NumBytesAllocated.  We should be using TargetData alignment stuff
 147     // to determine this, but we don't know the LLVM type associated with the
 148     // virtual register.  Instead, just align to a multiple of the size for now.
 149     NumBytesAllocated += RegSize-1;
 150     NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
 151
 152     // Assign the slot...
 153     VirtReg2OffsetMap[VirtReg] = NumBytesAllocated;
 154
 155     // Reserve the space!
 156     NumBytesAllocated += RegSize;
 157   }
 158   return VirtReg2OffsetMap[VirtReg];
 159 }
 160
 161 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 162   const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
 163   unsigned physReg;
 164   assert(regClass);
 165   if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
 166     unsigned regIdx = RegClassIdx[regClass]++;
 167     assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
 168     physReg = regClass->getRegister(regIdx);
 169   } else {
 170     physReg = regClass->getRegister(0);
 171     // assert(physReg < regClass->getNumRegs() && "No registers in class!");
 172     RegClassIdx[regClass] = 1;
 173   }
 174
 175   if (isAvailableReg(physReg))
 176     return physReg;
 177   else {
 178     return getFreeReg(virtualReg);
 179   }
 180 }
 181
 182 MachineBasicBlock::iterator
 183 RegAllocSimple::moveUseToReg (MachineBasicBlock *MBB,
 184                               MachineBasicBlock::iterator I,
 185                               unsigned VirtReg, unsigned &PhysReg)
 186 {
 187   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 188   assert(regClass);
 189
 190   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 191   PhysReg = getFreeReg(VirtReg);
 192
 193   // Add move instruction(s)
 194   return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
 195                                     RegInfo->getFramePointer(),
 196                                     -stackOffset, regClass->getDataSize());
 197 }
 198
 199 MachineBasicBlock::iterator
 200 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock *MBB,
 201                                     MachineBasicBlock::iterator I,
 202                                     unsigned VirtReg, unsigned PhysReg)
 203 {
 204   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 205   assert(regClass);
 206
 207   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 208
 209   // Add move instruction(s)
 210   return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
 211                                      RegInfo->getFramePointer(),
 212                                      -stackOffset, regClass->getDataSize());
 213 }
 214
 215 MachineBasicBlock::iterator
 216 RegAllocSimple::savePhysRegToStack (MachineBasicBlock *MBB,
 217                                     MachineBasicBlock::iterator I,
 218                                     unsigned PhysReg)
 219 {
 220   const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
 221   assert(regClass);
 222
 223   unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
 224
 225   // Add move instruction(s)
 226   return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
 227                                      RegInfo->getFramePointer(),
 228                                      offset, regClass->getDataSize());
 229 }
 230
 231 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 232   cleanupAfterFunction();
 233
 234   unsigned virtualReg, physReg;
 235   DEBUG(std::cerr << "Machine Function " << "\n");
 236   MF = &Fn;
 237
 238   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 239        MBB != MBBe; ++MBB)
 240   {
 241     MachineBasicBlock *CurrMBB = &(*MBB);
 242
 243     // Handle PHI instructions specially: add moves to each pred block
 244     while (MBB->front()->getOpcode() == 0) {
 245       MachineInstr *MI = MBB->front();
 246       // get rid of the phi
 247       MBB->erase(MBB->begin());
 248
 249       // a preliminary pass that will invalidate any registers that
 250       // are used by the instruction (including implicit uses)
 251       invalidatePhysRegs(MI);
 252
 253       DEBUG(std::cerr << "num invalid regs: " << RegsUsed.size() << "\n");
 254
 255       DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 256       MachineOperand &targetReg = MI->getOperand(0);
 257
 258       // If it's a virtual register, allocate a physical one
 259       // otherwise, just use whatever register is there now
 260       // note: it MUST be a register -- we're assigning to it
 261       virtualReg = (unsigned) targetReg.getAllocatedRegNum();
 262       if (targetReg.isVirtualRegister()) {
 263         physReg = getFreeReg(virtualReg);
 264       } else {
 265         physReg = virtualReg;
 266       }
 267
 268       // Find the register class of the target register: should be the
 269       // same as the values we're trying to store there
 270       const TargetRegisterClass* regClass = PhysRegClasses[physReg];
 271       assert(regClass && "Target register class not found!");
 272       unsigned dataSize = regClass->getDataSize();
 273
 274       for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 275         MachineOperand &opVal = MI->getOperand(i-1);
 276
 277         // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 278         // source path the phi
 279         MachineBasicBlock *opBlock = MI->getOperand(i).getMachineBasicBlock();
 280         MachineBasicBlock::iterator opI = opBlock->end();
 281         MachineInstr *opMI = *(--opI);
 282         const MachineInstrInfo &MII = TM.getInstrInfo();
 283         // must backtrack over ALL the branches in the previous block, until no more
 284         while ((MII.isBranch(opMI->getOpcode()) || MII.isReturn(opMI->getOpcode()))
 285                && opI != opBlock->begin())
 286         {
 287           opMI = *(--opI);
 288         }
 289         // move back to the first branch instruction so new instructions
 290         // are inserted right in front of it and not in front of a non-branch
 291         ++opI;
 292
 293
 294         // Retrieve the constant value from this op, move it to target
 295         // register of the phi
 296         if (opVal.getType() == MachineOperand::MO_SignExtendedImmed ||
 297             opVal.getType() == MachineOperand::MO_UnextendedImmed)
 298         {
 299           opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
 300                                      (unsigned) opVal.getImmedValue(),
 301                                      dataSize);
 302           saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
 303         } else {
 304           // Allocate a physical register and add a move in the BB
 305           unsigned opVirtualReg = (unsigned) opVal.getAllocatedRegNum();
 306           unsigned opPhysReg; // = getFreeReg(opVirtualReg);
 307           opI = moveUseToReg(opBlock, opI, opVirtualReg, physReg);
 308           //opI = RegInfo->moveReg2Reg(opBlock, opI, physReg, opPhysReg,
 309           //                           dataSize);
 310           // Save that register value to the stack of the TARGET REG
 311           saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
 312         }
 313
 314         // make regs available to other instructions
 315         clearAllRegs();
 316       }
 317
 318       // really delete the instruction
 319       delete MI;
 320     }
 321
 322     //loop over each basic block
 323     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
 324     {
 325       MachineInstr *MI = *I;
 326
 327       // a preliminary pass that will invalidate any registers that
 328       // are used by the instruction (including implicit uses)
 329       invalidatePhysRegs(MI);
 330
 331       // Loop over uses, move from memory into registers
 332       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 333         MachineOperand &op = MI->getOperand(i);
 334
 335         if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
 336             op.getType() == MachineOperand::MO_UnextendedImmed)
 337         {
 338           DEBUG(std::cerr << "const\n");
 339         } else if (op.isVirtualRegister()) {
 340           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           if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
 348             physReg = VirtReg2PhysRegMap[virtualReg];
 349           } else {
 350             if (op.opIsDef()) {
 351               if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 352                 // must be same register number as the first operand
 353                 // This maps a = b + c into b += c, and saves b into a's spot
 354                 physReg = (unsigned) MI->getOperand(1).getAllocatedRegNum();
 355               } else {
 356                 physReg = getFreeReg(virtualReg);
 357               }
 358               MachineBasicBlock::iterator J = I;
 359               J = saveVirtRegToStack(CurrMBB, ++J, virtualReg, physReg);
 360               I = --J;
 361             } else {
 362               I = moveUseToReg(CurrMBB, I, virtualReg, physReg);
 363             }
 364             VirtReg2PhysRegMap[virtualReg] = physReg;
 365           }
 366           MI->SetMachineOperandReg(i, physReg);
 367           DEBUG(std::cerr << "virt: " << virtualReg <<
 368                 ", phys: " << op.getAllocatedRegNum() << "\n");
 369         }
 370       }
 371
 372       clearAllRegs();
 373       VirtReg2PhysRegMap.clear();
 374     }
 375
 376   }
 377
 378   // add prologue we should preserve callee-save registers...
 379   MachineFunction::iterator Fi = Fn.begin();
 380   MachineBasicBlock *MBB = Fi;
 381   MachineBasicBlock::iterator MBBi = MBB->begin();
 382   RegInfo->emitPrologue(MBB, MBBi, NumBytesAllocated);
 383
 384   // add epilogue to restore the callee-save registers
 385   // loop over the basic block
 386   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 387        MBB != MBBe; ++MBB)
 388   {
 389     // check if last instruction is a RET
 390     MachineBasicBlock::iterator I = (*MBB).end();
 391     MachineInstr *MI = *(--I);
 392     const MachineInstrInfo &MII = TM.getInstrInfo();
 393     if (MII.isReturn(MI->getOpcode())) {
 394       // this block has a return instruction, add epilogue
 395       RegInfo->emitEpilogue(MBB, I, NumBytesAllocated);
 396     }
 397   }
 398
 399   return false;  // We never modify the LLVM itself.
 400 }
 401
 402 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
 403   return new RegAllocSimple(TM);
 404 }