lib/CodeGen/RegAllocSimple.cpp

   1 //===-- RegAllocSimple.cpp - A simple generic register allocator ----------===//
   2 //
   3 // This file implements a simple register allocator. *Very* simple: It immediate
   4 // spills every value right after it is computed, and it reloads all used
   5 // operands from the spill area to temporary registers before each instruction.
   6 // It does not keep values in registers across instructions.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/CodeGen/Passes.h"
  11 #include "llvm/CodeGen/MachineFunctionPass.h"
  12 #include "llvm/CodeGen/MachineInstr.h"
  13 #include "llvm/CodeGen/SSARegMap.h"
  14 #include "llvm/CodeGen/MachineFrameInfo.h"
  15 #include "llvm/Target/MachineInstrInfo.h"
  16 #include "llvm/Target/TargetMachine.h"
  17 #include "Support/Statistic.h"
  18 #include <iostream>
  19
  20 namespace {
  21   Statistic<> NumSpilled ("ra-simple", "Number of registers spilled");
  22   Statistic<> NumReloaded("ra-simple", "Number of registers reloaded");
  23
  24   class RegAllocSimple : public MachineFunctionPass {
  25     MachineFunction *MF;
  26     const TargetMachine *TM;
  27     const MRegisterInfo *RegInfo;
  28
  29     // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where
  30     // these values are spilled
  31     std::map<unsigned, int> StackSlotForVirtReg;
  32
  33     // RegsUsed - Keep track of what registers are currently in use.  This is a
  34     // bitset.
  35     std::vector<bool> RegsUsed;
  36
  37     // RegClassIdx - Maps RegClass => which index we can take a register
  38     // from. Since this is a simple register allocator, when we need a register
  39     // of a certain class, we just take the next available one.
  40     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
  41
  42   public:
  43     virtual const char *getPassName() const {
  44       return "Simple Register Allocator";
  45     }
  46
  47     /// runOnMachineFunction - Register allocate the whole function
  48     bool runOnMachineFunction(MachineFunction &Fn);
  49
  50     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  51       AU.addRequiredID(PHIEliminationID);           // Eliminate PHI nodes
  52       MachineFunctionPass::getAnalysisUsage(AU);
  53     }
  54   private:
  55     /// AllocateBasicBlock - Register allocate the specified basic block.
  56     void AllocateBasicBlock(MachineBasicBlock &MBB);
  57
  58     /// getStackSpaceFor - This returns the offset of the specified virtual
  59     /// register on the stack, allocating space if neccesary.
  60     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
  61
  62     /// Given a virtual register, return a compatible physical register that is
  63     /// currently unused.
  64     ///
  65     /// Side effect: marks that register as being used until manually cleared
  66     ///
  67     unsigned getFreeReg(unsigned virtualReg);
  68
  69     /// Moves value from memory into that register
  70     unsigned reloadVirtReg(MachineBasicBlock &MBB,
  71                            MachineBasicBlock::iterator &I, unsigned VirtReg);
  72
  73     /// Saves reg value on the stack (maps virtual register to stack value)
  74     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
  75                       unsigned VirtReg, unsigned PhysReg);
  76   };
  77
  78 }
  79
  80 /// getStackSpaceFor - This allocates space for the specified virtual
  81 /// register to be held on the stack.
  82 int RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
  83                                      const TargetRegisterClass *RC) {
  84   // Find the location VirtReg would belong...
  85   std::map<unsigned, int>::iterator I =
  86     StackSlotForVirtReg.lower_bound(VirtReg);
  87
  88   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
  89     return I->second;          // Already has space allocated?
  90
  91   // Allocate a new stack object for this spill location...
  92   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
  93
  94   // Assign the slot...
  95   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
  96
  97   return FrameIdx;
  98 }
  99
 100 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 101   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(virtualReg);
 102   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 103   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 104
 105   while (1) {
 106     unsigned regIdx = RegClassIdx[RC]++;
 107     assert(RI+regIdx != RE && "Not enough registers!");
 108     unsigned PhysReg = *(RI+regIdx);
 109
 110     if (!RegsUsed[PhysReg])
 111       return PhysReg;
 112   }
 113 }
 114
 115 unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
 116                                        MachineBasicBlock::iterator &I,
 117                                        unsigned VirtReg) {
 118   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
 119   int FrameIdx = getStackSpaceFor(VirtReg, RC);
 120   unsigned PhysReg = getFreeReg(VirtReg);
 121
 122   // Add move instruction(s)
 123   ++NumReloaded;
 124   RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx, RC);
 125   return PhysReg;
 126 }
 127
 128 void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
 129                                   MachineBasicBlock::iterator &I,
 130                                   unsigned VirtReg, unsigned PhysReg) {
 131   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
 132   int FrameIdx = getStackSpaceFor(VirtReg, RC);
 133
 134   // Add move instruction(s)
 135   ++NumSpilled;
 136   RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIdx, RC);
 137 }
 138
 139
 140 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
 141   // loop over each instruction
 142   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
 143     // Made to combat the incorrect allocation of r2 = add r1, r1
 144     std::map<unsigned, unsigned> Virt2PhysRegMap;
 145
 146     MachineInstr *MI = *I;
 147
 148     RegsUsed.resize(MRegisterInfo::FirstVirtualRegister);
 149
 150     // a preliminary pass that will invalidate any registers that
 151     // are used by the instruction (including implicit uses)
 152     unsigned Opcode = MI->getOpcode();
 153     const MachineInstrDescriptor &Desc = TM->getInstrInfo().get(Opcode);
 154     if (const unsigned *Regs = Desc.ImplicitUses)
 155       while (*Regs)
 156         RegsUsed[*Regs++] = true;
 157
 158     if (const unsigned *Regs = Desc.ImplicitDefs)
 159       while (*Regs)
 160         RegsUsed[*Regs++] = true;
 161
 162     // Loop over uses, move from memory into registers
 163     for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 164       MachineOperand &op = MI->getOperand(i);
 165
 166       if (op.isVirtualRegister()) {
 167         unsigned virtualReg = (unsigned) op.getAllocatedRegNum();
 168         DEBUG(std::cerr << "op: " << op << "\n");
 169         DEBUG(std::cerr << "\t inst[" << i << "]: ";
 170               MI->print(std::cerr, *TM));
 171
 172         // make sure the same virtual register maps to the same physical
 173         // register in any given instruction
 174         unsigned physReg = Virt2PhysRegMap[virtualReg];
 175         if (physReg == 0) {
 176           if (op.opIsDef()) {
 177             if (TM->getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 178               // must be same register number as the first operand
 179               // This maps a = b + c into b += c, and saves b into a's spot
 180               assert(MI->getOperand(1).isRegister()  &&
 181                      MI->getOperand(1).getAllocatedRegNum() &&
 182                      MI->getOperand(1).opIsUse() &&
 183                      "Two address instruction invalid!");
 184
 185               physReg = MI->getOperand(1).getAllocatedRegNum();
 186             } else {
 187               physReg = getFreeReg(virtualReg);
 188             }
 189             ++I;
 190             spillVirtReg(MBB, I, virtualReg, physReg);
 191             --I;
 192           } else {
 193             physReg = reloadVirtReg(MBB, I, virtualReg);
 194             Virt2PhysRegMap[virtualReg] = physReg;
 195           }
 196         }
 197         MI->SetMachineOperandReg(i, physReg);
 198         DEBUG(std::cerr << "virt: " << virtualReg <<
 199               ", phys: " << op.getAllocatedRegNum() << "\n");
 200       }
 201     }
 202     RegClassIdx.clear();
 203     RegsUsed.clear();
 204   }
 205 }
 206
 207
 208 /// runOnMachineFunction - Register allocate the whole function
 209 ///
 210 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 211   DEBUG(std::cerr << "Machine Function " << "\n");
 212   MF = &Fn;
 213   TM = &MF->getTarget();
 214   RegInfo = TM->getRegisterInfo();
 215
 216   // Loop over all of the basic blocks, eliminating virtual register references
 217   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 218        MBB != MBBe; ++MBB)
 219     AllocateBasicBlock(*MBB);
 220
 221   StackSlotForVirtReg.clear();
 222   return true;
 223 }
 224
 225 Pass *createSimpleRegisterAllocator() {
 226   return new RegAllocSimple();
 227 }