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