lib/CodeGen/RegAllocSimple.cpp

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