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