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/MRegisterInfo.h"
  16 #include "llvm/Target/MachineRegInfo.h"
  17 #include "llvm/Target/TargetMachine.h"
  18 #include "llvm/Support/InstVisitor.h"
  19 #include "Support/Statistic.h"
  20 #include <map>
  21
  22 namespace {
  23   struct RegAllocSimple : public FunctionPass {
  24     TargetMachine &TM;
  25     MachineBasicBlock *CurrMBB;
  26     MachineFunction *MF;
  27     unsigned maxOffset;
  28     const MRegisterInfo *RegInfo;
  29     unsigned NumBytesAllocated, ByteAlignment;
  30
  31     // Maps SSA Regs => offsets on the stack where these values are stored
  32     std::map<unsigned, unsigned> RegMap; // FIXME: change name to VirtReg2OffsetMap
  33
  34     // Maps SSA Regs => physical regs
  35     std::map<unsigned, unsigned> SSA2PhysRegMap;
  36
  37     // Maps physical register to their register classes
  38     std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
  39
  40     // Maps RegClass => which index we can take a register from. Since this is a
  41     // simple register allocator, when we need a register of a certain class, we
  42     // just take the next available one.
  43     std::map<unsigned, unsigned> RegsUsed;
  44     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
  45
  46     RegAllocSimple(TargetMachine &tm) : TM(tm), CurrMBB(0), maxOffset(0),
  47                                         RegInfo(tm.getRegisterInfo()),
  48                                         NumBytesAllocated(0), ByteAlignment(4)
  49     {
  50       // build reverse mapping for physReg -> register class
  51       RegInfo->buildReg2RegClassMap(PhysReg2RegClassMap);
  52
  53       RegsUsed[RegInfo->getFramePointer()] = 1;
  54       RegsUsed[RegInfo->getStackPointer()] = 1;
  55     }
  56
  57     bool isAvailableReg(unsigned Reg) {
  58       // assert(Reg < MRegisterInfo::FirstVirtualReg && "...");
  59       return RegsUsed.find(Reg) == RegsUsed.end();
  60     }
  61
  62     ///
  63     unsigned allocateStackSpaceFor(unsigned VirtReg,
  64                                    const TargetRegisterClass *regClass);
  65
  66     /// Given size (in bytes), returns a register that is currently unused
  67     /// Side effect: marks that register as being used until manually cleared
  68     unsigned getFreeReg(unsigned virtualReg);
  69
  70     /// Returns all `borrowed' registers back to the free pool
  71     void clearAllRegs() {
  72         RegClassIdx.clear();
  73     }
  74
  75     /// Moves value from memory into that register
  76     MachineBasicBlock::iterator
  77     moveUseToReg (MachineBasicBlock::iterator I, unsigned VirtReg,
  78                   unsigned &PhysReg);
  79
  80     /// Saves reg value on the stack (maps virtual register to stack value)
  81     MachineBasicBlock::iterator
  82     saveVirtRegToStack (MachineBasicBlock::iterator I, unsigned VirtReg,
  83                         unsigned PhysReg);
  84
  85     MachineBasicBlock::iterator
  86     savePhysRegToStack (MachineBasicBlock::iterator I, unsigned PhysReg);
  87
  88     /// runOnFunction - Top level implementation of instruction selection for
  89     /// the entire function.
  90     ///
  91     bool runOnMachineFunction(MachineFunction &Fn);
  92
  93     bool runOnFunction(Function &Fn) {
  94       return runOnMachineFunction(MachineFunction::get(&Fn));
  95     }
  96   };
  97
  98 }
  99
 100 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
 101                                             const TargetRegisterClass *regClass)
 102 {
 103   if (RegMap.find(VirtReg) == RegMap.end()) {
 104     unsigned size = regClass->getDataSize();
 105     unsigned over = NumBytesAllocated - (NumBytesAllocated % ByteAlignment);
 106     if (size >= ByteAlignment - over) {
 107       // need to pad by (ByteAlignment - over)
 108       NumBytesAllocated += ByteAlignment - over;
 109     }
 110     RegMap[VirtReg] = NumBytesAllocated;
 111     NumBytesAllocated += size;
 112   }
 113   return RegMap[VirtReg];
 114 }
 115
 116 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 117   const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
 118   unsigned physReg;
 119   assert(regClass);
 120   if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
 121     unsigned regIdx = RegClassIdx[regClass]++;
 122     assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
 123     physReg = regClass->getRegister(regIdx);
 124   } else {
 125     physReg = regClass->getRegister(0);
 126     // assert(physReg < regClass->getNumRegs() && "No registers in class!");
 127     RegClassIdx[regClass] = 1;
 128   }
 129
 130   if (isAvailableReg(physReg))
 131     return physReg;
 132   else {
 133     return getFreeReg(virtualReg);
 134   }
 135 }
 136
 137 MachineBasicBlock::iterator
 138 RegAllocSimple::moveUseToReg (MachineBasicBlock::iterator I,
 139                               unsigned VirtReg, unsigned &PhysReg)
 140 {
 141   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 142   assert(regClass);
 143
 144   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 145   PhysReg = getFreeReg(VirtReg);
 146
 147   // FIXME: increment the frame pointer
 148
 149   // Add move instruction(s)
 150   return RegInfo->loadRegOffset2Reg(CurrMBB, I, PhysReg,
 151                                     RegInfo->getFramePointer(),
 152                                     stackOffset, regClass->getDataSize());
 153 }
 154
 155 MachineBasicBlock::iterator
 156 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock::iterator I,
 157                                     unsigned VirtReg, unsigned PhysReg)
 158 {
 159   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 160   assert(regClass);
 161
 162   unsigned offset = allocateStackSpaceFor(VirtReg, regClass);
 163
 164   // Add move instruction(s)
 165   return RegInfo->storeReg2RegOffset(CurrMBB, I, PhysReg,
 166                                      RegInfo->getFramePointer(),
 167                                      offset, regClass->getDataSize());
 168 }
 169
 170 MachineBasicBlock::iterator
 171 RegAllocSimple::savePhysRegToStack (MachineBasicBlock::iterator I,
 172                                     unsigned PhysReg)
 173 {
 174   const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
 175   assert(regClass);
 176
 177   unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
 178
 179   // Add move instruction(s)
 180   return RegInfo->storeReg2RegOffset(CurrMBB, I, PhysReg,
 181                                      RegInfo->getFramePointer(),
 182                                      offset, regClass->getDataSize());
 183 }
 184
 185 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 186   RegMap.clear();
 187   unsigned virtualReg, physReg;
 188   DEBUG(std::cerr << "Machine Function " << "\n");
 189   MF = &Fn;
 190
 191 #if 0
 192   // FIXME: add prolog. we should preserve callee-save registers...
 193   MachineFunction::iterator Fi = Fn.begin();
 194   MachineBasicBlock &MBB = *Fi;
 195   MachineBasicBlock::iterator MBBi = MBB.begin()
 196   const unsigned* calleeSaveRegs = tm.getCalleeSaveRegs();
 197   while (*calleeSaveRegs) {
 198     //MBBi = saveRegToStack(MBBi, *calleeSaveRegs,
 199     ++calleeSaveRegs;
 200   }
 201 #endif
 202
 203   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 204        MBB != MBBe; ++MBB)
 205   {
 206     CurrMBB = &(*MBB);
 207
 208     //loop over each basic block
 209     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
 210     {
 211       MachineInstr *MI = *I;
 212
 213       DEBUG(std::cerr << "instr: ";
 214             MI->print(std::cerr, TM));
 215
 216       // FIXME: add a preliminary pass that will invalidate any registers that
 217       // are used by the instruction (including implicit uses)
 218
 219
 220       // Loop over each instruction:
 221       // uses, move from memory into registers
 222       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 223         MachineOperand &op = MI->getOperand(i);
 224
 225         if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
 226             op.getType() == MachineOperand::MO_UnextendedImmed)
 227         {
 228           DEBUG(std::cerr << "const\n");
 229         } else if (op.isVirtualRegister()) {
 230           virtualReg = (unsigned) op.getAllocatedRegNum();
 231           // save register to stack if it's a def
 232           DEBUG(std::cerr << "op: " << op << "\n");
 233           DEBUG(std::cerr << "\t inst[" << i << "]: ";
 234                 MI->print(std::cerr, TM));
 235           if (op.opIsDef()) {
 236             physReg = getFreeReg(virtualReg);
 237             MachineBasicBlock::iterator J = I;
 238             I = saveVirtRegToStack(J, virtualReg, physReg);
 239           } else {
 240             I = moveUseToReg(I, virtualReg, physReg);
 241           }
 242           MI->SetMachineOperandReg(i, physReg);
 243           DEBUG(std::cerr << "virt: " << virtualReg <<
 244                 ", phys: " << op.getAllocatedRegNum() << "\n");
 245         }
 246       }
 247
 248       clearAllRegs();
 249     }
 250
 251   }
 252
 253   // FIXME: add epilog. we should preserve callee-save registers...
 254
 255   return false;  // We never modify the LLVM itself.
 256 }
 257
 258 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
 259   return new RegAllocSimple(TM);
 260 }