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     void cleanupAfterFunction() {
  83       RegMap.clear();
  84       SSA2PhysRegMap.clear();
  85       NumBytesAllocated = ByteAlignment;
  86     }
  87
  88     /// Moves value from memory into that register
  89     MachineBasicBlock::iterator
  90     moveUseToReg (MachineBasicBlock *MBB,
  91                   MachineBasicBlock::iterator I, unsigned VirtReg,
  92                   unsigned &PhysReg);
  93
  94     /// Saves reg value on the stack (maps virtual register to stack value)
  95     MachineBasicBlock::iterator
  96     saveVirtRegToStack (MachineBasicBlock *MBB,
  97                         MachineBasicBlock::iterator I, unsigned VirtReg,
  98                         unsigned PhysReg);
  99
 100     MachineBasicBlock::iterator
 101     savePhysRegToStack (MachineBasicBlock *MBB,
 102                         MachineBasicBlock::iterator I, unsigned PhysReg);
 103
 104     /// runOnFunction - Top level implementation of instruction selection for
 105     /// the entire function.
 106     ///
 107     bool runOnMachineFunction(MachineFunction &Fn);
 108
 109     bool runOnFunction(Function &Fn) {
 110       return runOnMachineFunction(MachineFunction::get(&Fn));
 111     }
 112   };
 113
 114 }
 115
 116 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
 117                                             const TargetRegisterClass *regClass)
 118 {
 119   if (RegMap.find(VirtReg) == RegMap.end()) {
 120 #if 0
 121     unsigned size = regClass->getDataSize();
 122     unsigned over = NumBytesAllocated - (NumBytesAllocated % ByteAlignment);
 123     if (size >= ByteAlignment - over) {
 124       // need to pad by (ByteAlignment - over)
 125       NumBytesAllocated += ByteAlignment - over;
 126     }
 127     RegMap[VirtReg] = NumBytesAllocated;
 128     NumBytesAllocated += size;
 129 #endif
 130     // FIXME: forcing each arg to take 4 bytes on the stack
 131     RegMap[VirtReg] = NumBytesAllocated;
 132     NumBytesAllocated += ByteAlignment;
 133   }
 134   return RegMap[VirtReg];
 135 }
 136
 137 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 138   const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
 139   unsigned physReg;
 140   assert(regClass);
 141   if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
 142     unsigned regIdx = RegClassIdx[regClass]++;
 143     assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
 144     physReg = regClass->getRegister(regIdx);
 145   } else {
 146     physReg = regClass->getRegister(0);
 147     // assert(physReg < regClass->getNumRegs() && "No registers in class!");
 148     RegClassIdx[regClass] = 1;
 149   }
 150
 151   if (isAvailableReg(physReg))
 152     return physReg;
 153   else {
 154     return getFreeReg(virtualReg);
 155   }
 156 }
 157
 158 MachineBasicBlock::iterator
 159 RegAllocSimple::moveUseToReg (MachineBasicBlock *MBB,
 160                               MachineBasicBlock::iterator I,
 161                               unsigned VirtReg, unsigned &PhysReg)
 162 {
 163   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 164   assert(regClass);
 165
 166   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 167   PhysReg = getFreeReg(VirtReg);
 168
 169   // Add move instruction(s)
 170   return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
 171                                     RegInfo->getFramePointer(),
 172                                     -stackOffset, regClass->getDataSize());
 173 }
 174
 175 MachineBasicBlock::iterator
 176 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock *MBB,
 177                                     MachineBasicBlock::iterator I,
 178                                     unsigned VirtReg, unsigned PhysReg)
 179 {
 180   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 181   assert(regClass);
 182
 183   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 184
 185   // Add move instruction(s)
 186   return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
 187                                      RegInfo->getFramePointer(),
 188                                      -stackOffset, regClass->getDataSize());
 189 }
 190
 191 MachineBasicBlock::iterator
 192 RegAllocSimple::savePhysRegToStack (MachineBasicBlock *MBB,
 193                                     MachineBasicBlock::iterator I,
 194                                     unsigned PhysReg)
 195 {
 196   const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
 197   assert(regClass);
 198
 199   unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
 200
 201   // Add move instruction(s)
 202   return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
 203                                      RegInfo->getFramePointer(),
 204                                      offset, regClass->getDataSize());
 205 }
 206
 207 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 208   cleanupAfterFunction();
 209
 210   unsigned virtualReg, physReg;
 211   DEBUG(std::cerr << "Machine Function " << "\n");
 212   MF = &Fn;
 213
 214   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 215        MBB != MBBe; ++MBB)
 216   {
 217     CurrMBB = &(*MBB);
 218
 219     // Handle PHI instructions specially: add moves to each pred block
 220     while (MBB->front()->getOpcode() == 0) {
 221       MachineInstr *MI = MBB->front();
 222       // get rid of the phi
 223       MBB->erase(MBB->begin());
 224
 225       DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 226       MachineOperand &targetReg = MI->getOperand(0);
 227
 228       // If it's a virtual register, allocate a physical one
 229       // otherwise, just use whatever register is there now
 230       // note: it MUST be a register -- we're assigning to it
 231       virtualReg = (unsigned) targetReg.getAllocatedRegNum();
 232       if (targetReg.isVirtualRegister()) {
 233         physReg = getFreeReg(virtualReg);
 234       } else {
 235         physReg = targetReg.getAllocatedRegNum();
 236       }
 237
 238       // Find the register class of the target register: should be the
 239       // same as the values we're trying to store there
 240       const TargetRegisterClass* regClass = PhysReg2RegClassMap[physReg];
 241       assert(regClass && "Target register class not found!");
 242       unsigned dataSize = regClass->getDataSize();
 243
 244       for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 245         MachineOperand &opVal = MI->getOperand(i-1);
 246
 247         // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 248         // source path the phi
 249         BasicBlock *opBB =
 250           cast<BasicBlock>(MI->getOperand(i).getVRegValue());
 251         MachineBasicBlock *opBlock = NULL;
 252         for (MachineFunction::iterator opFi = Fn.begin(), opFe = Fn.end();
 253              opFi != opFe; ++opFi)
 254         {
 255           if (opFi->getBasicBlock() == opBB) {
 256             opBlock = opFi; break;
 257           }
 258         }
 259         assert(opBlock && "MachineBasicBlock object not found for specified block!");
 260
 261         MachineBasicBlock::iterator opI = opBlock->end();
 262         MachineInstr *opMI = *(--opI);
 263         const MachineInstrInfo &MII = TM.getInstrInfo();
 264
 265         // insert the move just before the return/branch
 266         if (MII.isReturn(opMI->getOpcode()) || MII.isBranch(opMI->getOpcode()))
 267         {
 268           // Retrieve the constant value from this op, move it to target
 269           // register of the phi
 270           if (opVal.getType() == MachineOperand::MO_SignExtendedImmed ||
 271               opVal.getType() == MachineOperand::MO_UnextendedImmed)
 272           {
 273             opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
 274                                        (unsigned) opVal.getImmedValue(),
 275                                        dataSize);
 276             saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
 277           } else {
 278             // Allocate a physical register and add a move in the BB
 279             unsigned opVirtualReg = (unsigned) opVal.getAllocatedRegNum();
 280             unsigned opPhysReg; // = getFreeReg(opVirtualReg);
 281             opI = moveUseToReg(opBlock, opI, opVirtualReg, opPhysReg);
 282             opI = RegInfo->moveReg2Reg(opBlock, opI, physReg, opPhysReg,
 283                                        dataSize);
 284             // Save that register value to the stack of the TARGET REG
 285             saveVirtRegToStack(opBlock, opI, virtualReg, opPhysReg);
 286           }
 287         }
 288       }
 289
 290       // really delete the instruction
 291       delete MI;
 292
 293       // make regs available to other instructions
 294       clearAllRegs();
 295     }
 296
 297     //loop over each basic block
 298     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
 299     {
 300       MachineInstr *MI = *I;
 301
 302       // FIXME: add a preliminary pass that will invalidate any registers that
 303       // are used by the instruction (including implicit uses)
 304
 305       // Loop over uses, move from memory into registers
 306       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 307         MachineOperand &op = MI->getOperand(i);
 308
 309         if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
 310             op.getType() == MachineOperand::MO_UnextendedImmed)
 311         {
 312           DEBUG(std::cerr << "const\n");
 313         } else if (op.isVirtualRegister()) {
 314           virtualReg = (unsigned) op.getAllocatedRegNum();
 315           DEBUG(std::cerr << "op: " << op << "\n");
 316           DEBUG(std::cerr << "\t inst[" << i << "]: ";
 317                 MI->print(std::cerr, TM));
 318
 319           // make sure the same virtual register maps to the same physical
 320           // register in any given instruction
 321           if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
 322             physReg = VirtReg2PhysRegMap[virtualReg];
 323           } else {
 324             if (op.opIsDef()) {
 325               if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 326                 // must be same register number as the first operand
 327                 // This maps a = b + c into b += c, and saves b into a's spot
 328                 physReg = (unsigned) MI->getOperand(1).getAllocatedRegNum();
 329               } else {
 330                 physReg = getFreeReg(virtualReg);
 331               }
 332               MachineBasicBlock::iterator J = I;
 333               J = saveVirtRegToStack(CurrMBB, ++J, virtualReg, physReg);
 334               I = --J;
 335             } else {
 336               I = moveUseToReg(CurrMBB, I, virtualReg, physReg);
 337             }
 338             VirtReg2PhysRegMap[virtualReg] = physReg;
 339           }
 340           MI->SetMachineOperandReg(i, physReg);
 341           DEBUG(std::cerr << "virt: " << virtualReg <<
 342                 ", phys: " << op.getAllocatedRegNum() << "\n");
 343         }
 344       }
 345
 346       clearAllRegs();
 347       VirtReg2PhysRegMap.clear();
 348     }
 349
 350   }
 351
 352   // add prologue we should preserve callee-save registers...
 353   MachineFunction::iterator Fi = Fn.begin();
 354   MachineBasicBlock *MBB = Fi;
 355   MachineBasicBlock::iterator MBBi = MBB->begin();
 356   RegInfo->emitPrologue(MBB, MBBi, NumBytesAllocated);
 357
 358   // add epilogue to restore the callee-save registers
 359   // loop over the basic block
 360   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 361        MBB != MBBe; ++MBB)
 362   {
 363     // check if last instruction is a RET
 364     MachineBasicBlock::iterator I = (*MBB).end();
 365     MachineInstr *MI = *(--I);
 366     const MachineInstrInfo &MII = TM.getInstrInfo();
 367     if (MII.isReturn(MI->getOpcode())) {
 368       // this block has a return instruction, add epilogue
 369       RegInfo->emitEpilogue(MBB, I, NumBytesAllocated);
 370     }
 371   }
 372
 373   return false;  // We never modify the LLVM itself.
 374 }
 375
 376 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
 377   return new RegAllocSimple(TM);
 378 }