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