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