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