LLVM API Documentation

RegAllocSimple.cpp

Go to the documentation of this file.
00001 //===-- RegAllocSimple.cpp - A simple generic register allocator ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a simple register allocator. *Very* simple: It immediate
00011 // spills every value right after it is computed, and it reloads all used
00012 // operands from the spill area to temporary registers before each instruction.
00013 // It does not keep values in registers across instructions.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #define DEBUG_TYPE "regalloc"
00018 #include "llvm/CodeGen/Passes.h"
00019 #include "llvm/CodeGen/MachineFunctionPass.h"
00020 #include "llvm/CodeGen/MachineInstr.h"
00021 #include "llvm/CodeGen/MachineFrameInfo.h"
00022 #include "llvm/CodeGen/MachineRegisterInfo.h"
00023 #include "llvm/CodeGen/RegAllocRegistry.h"
00024 #include "llvm/Target/TargetInstrInfo.h"
00025 #include "llvm/Target/TargetMachine.h"
00026 #include "llvm/Support/Debug.h"
00027 #include "llvm/Support/Compiler.h"
00028 #include "llvm/ADT/Statistic.h"
00029 #include "llvm/ADT/STLExtras.h"
00030 #include <map>
00031 using namespace llvm;
00032 
00033 STATISTIC(NumStores, "Number of stores added");
00034 STATISTIC(NumLoads , "Number of loads added");
00035 
00036 namespace {
00037   static RegisterRegAlloc
00038     simpleRegAlloc("simple", "simple register allocator",
00039                    createSimpleRegisterAllocator);
00040 
00041   class VISIBILITY_HIDDEN RegAllocSimple : public MachineFunctionPass {
00042   public:
00043     static char ID;
00044     RegAllocSimple() : MachineFunctionPass(&ID) {}
00045   private:
00046     MachineFunction *MF;
00047     const TargetMachine *TM;
00048     const TargetRegisterInfo *TRI;
00049     const TargetInstrInfo *TII;
00050 
00051     // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where
00052     // these values are spilled
00053     std::map<unsigned, int> StackSlotForVirtReg;
00054 
00055     // RegsUsed - Keep track of what registers are currently in use.  This is a
00056     // bitset.
00057     std::vector<bool> RegsUsed;
00058 
00059     // RegClassIdx - Maps RegClass => which index we can take a register
00060     // from. Since this is a simple register allocator, when we need a register
00061     // of a certain class, we just take the next available one.
00062     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
00063 
00064   public:
00065     virtual const char *getPassName() const {
00066       return "Simple Register Allocator";
00067     }
00068 
00069     /// runOnMachineFunction - Register allocate the whole function
00070     bool runOnMachineFunction(MachineFunction &Fn);
00071 
00072     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00073       AU.setPreservesCFG();
00074       AU.addRequiredID(PHIEliminationID);           // Eliminate PHI nodes
00075       MachineFunctionPass::getAnalysisUsage(AU);
00076     }
00077   private:
00078     /// AllocateBasicBlock - Register allocate the specified basic block.
00079     void AllocateBasicBlock(MachineBasicBlock &MBB);
00080 
00081     /// getStackSpaceFor - This returns the offset of the specified virtual
00082     /// register on the stack, allocating space if necessary.
00083     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
00084 
00085     /// Given a virtual register, return a compatible physical register that is
00086     /// currently unused.
00087     ///
00088     /// Side effect: marks that register as being used until manually cleared
00089     ///
00090     unsigned getFreeReg(unsigned virtualReg);
00091 
00092     /// Moves value from memory into that register
00093     unsigned reloadVirtReg(MachineBasicBlock &MBB,
00094                            MachineBasicBlock::iterator I, unsigned VirtReg);
00095 
00096     /// Saves reg value on the stack (maps virtual register to stack value)
00097     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
00098                       unsigned VirtReg, unsigned PhysReg);
00099   };
00100   char RegAllocSimple::ID = 0;
00101 }
00102 
00103 /// getStackSpaceFor - This allocates space for the specified virtual
00104 /// register to be held on the stack.
00105 int RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
00106                                      const TargetRegisterClass *RC) {
00107   // Find the location VirtReg would belong...
00108   std::map<unsigned, int>::iterator I = StackSlotForVirtReg.find(VirtReg);
00109 
00110   if (I != StackSlotForVirtReg.end())
00111     return I->second;          // Already has space allocated?
00112 
00113   // Allocate a new stack object for this spill location...
00114   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
00115                                                        RC->getAlignment());
00116 
00117   // Assign the slot...
00118   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
00119 
00120   return FrameIdx;
00121 }
00122 
00123 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
00124   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtualReg);
00125   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
00126 #ifndef NDEBUG
00127   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
00128 #endif
00129 
00130   while (1) {
00131     unsigned regIdx = RegClassIdx[RC]++;
00132     assert(RI+regIdx != RE && "Not enough registers!");
00133     unsigned PhysReg = *(RI+regIdx);
00134 
00135     if (!RegsUsed[PhysReg]) {
00136       MF->getRegInfo().setPhysRegUsed(PhysReg);
00137       return PhysReg;
00138     }
00139   }
00140 }
00141 
00142 unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
00143                                        MachineBasicBlock::iterator I,
00144                                        unsigned VirtReg) {
00145   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(VirtReg);
00146   int FrameIdx = getStackSpaceFor(VirtReg, RC);
00147   unsigned PhysReg = getFreeReg(VirtReg);
00148 
00149   // Add move instruction(s)
00150   ++NumLoads;
00151   TII->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx, RC);
00152   return PhysReg;
00153 }
00154 
00155 void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
00156                                   MachineBasicBlock::iterator I,
00157                                   unsigned VirtReg, unsigned PhysReg) {
00158   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(VirtReg);
00159   
00160   int FrameIdx = getStackSpaceFor(VirtReg, RC);
00161 
00162   // Add move instruction(s)
00163   ++NumStores;
00164   TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIdx, RC);
00165 }
00166 
00167 
00168 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
00169   // loop over each instruction
00170   for (MachineBasicBlock::iterator MI = MBB.begin(); MI != MBB.end(); ++MI) {
00171     // Made to combat the incorrect allocation of r2 = add r1, r1
00172     std::map<unsigned, unsigned> Virt2PhysRegMap;
00173 
00174     RegsUsed.resize(TRI->getNumRegs());
00175 
00176     // This is a preliminary pass that will invalidate any registers that are
00177     // used by the instruction (including implicit uses).
00178     const TargetInstrDesc &Desc = MI->getDesc();
00179     const unsigned *Regs;
00180     if (Desc.ImplicitUses) {
00181       for (Regs = Desc.ImplicitUses; *Regs; ++Regs)
00182         RegsUsed[*Regs] = true;
00183     }
00184 
00185     if (Desc.ImplicitDefs) {
00186       for (Regs = Desc.ImplicitDefs; *Regs; ++Regs) {
00187         RegsUsed[*Regs] = true;
00188         MF->getRegInfo().setPhysRegUsed(*Regs);
00189       }
00190     }
00191 
00192     // Loop over uses, move from memory into registers.
00193     for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
00194       MachineOperand &MO = MI->getOperand(i);
00195 
00196       if (MO.isReg() && MO.getReg() &&
00197           TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
00198         unsigned virtualReg = (unsigned) MO.getReg();
00199         DOUT << "op: " << MO << "\n";
00200         DOUT << "\t inst[" << i << "]: ";
00201         DEBUG(MI->print(*cerr.stream(), TM));
00202 
00203         // make sure the same virtual register maps to the same physical
00204         // register in any given instruction
00205         unsigned physReg = Virt2PhysRegMap[virtualReg];
00206         if (physReg == 0) {
00207           if (MO.isDef()) {
00208             unsigned TiedOp;
00209             if (!MI->isRegTiedToUseOperand(i, &TiedOp)) {
00210               physReg = getFreeReg(virtualReg);
00211             } else {
00212               // must be same register number as the source operand that is 
00213               // tied to. This maps a = b + c into b = b + c, and saves b into
00214               // a's spot.
00215               assert(MI->getOperand(TiedOp).isReg()  &&
00216                      MI->getOperand(TiedOp).getReg() &&
00217                      MI->getOperand(TiedOp).isUse() &&
00218                      "Two address instruction invalid!");
00219 
00220               physReg = MI->getOperand(TiedOp).getReg();
00221             }
00222             spillVirtReg(MBB, next(MI), virtualReg, physReg);
00223           } else {
00224             physReg = reloadVirtReg(MBB, MI, virtualReg);
00225             Virt2PhysRegMap[virtualReg] = physReg;
00226           }
00227         }
00228         MO.setReg(physReg);
00229         DOUT << "virt: " << virtualReg << ", phys: " << MO.getReg() << "\n";
00230       }
00231     }
00232     RegClassIdx.clear();
00233     RegsUsed.clear();
00234   }
00235 }
00236 
00237 
00238 /// runOnMachineFunction - Register allocate the whole function
00239 ///
00240 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
00241   DOUT << "Machine Function\n";
00242   MF = &Fn;
00243   TM = &MF->getTarget();
00244   TRI = TM->getRegisterInfo();
00245   TII = TM->getInstrInfo();
00246 
00247   // Loop over all of the basic blocks, eliminating virtual register references
00248   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
00249        MBB != MBBe; ++MBB)
00250     AllocateBasicBlock(*MBB);
00251 
00252   StackSlotForVirtReg.clear();
00253   return true;
00254 }
00255 
00256 FunctionPass *llvm::createSimpleRegisterAllocator() {
00257   return new RegAllocSimple();
00258 }