LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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/SSARegMap.h"
00022 #include "llvm/CodeGen/MachineFrameInfo.h"
00023 #include "llvm/Target/TargetInstrInfo.h"
00024 #include "llvm/Target/TargetMachine.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/ADT/STLExtras.h"
00028 using namespace llvm;
00029 
00030 namespace {
00031   Statistic<> NumStores("ra-simple", "Number of stores added");
00032   Statistic<> NumLoads ("ra-simple", "Number of loads added");
00033 
00034   class RegAllocSimple : public MachineFunctionPass {
00035     MachineFunction *MF;
00036     const TargetMachine *TM;
00037     const MRegisterInfo *RegInfo;
00038     
00039     // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where
00040     // these values are spilled
00041     std::map<unsigned, int> StackSlotForVirtReg;
00042 
00043     // RegsUsed - Keep track of what registers are currently in use.  This is a
00044     // bitset.
00045     std::vector<bool> RegsUsed;
00046 
00047     // RegClassIdx - Maps RegClass => which index we can take a register
00048     // from. Since this is a simple register allocator, when we need a register
00049     // of a certain class, we just take the next available one.
00050     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
00051 
00052   public:
00053     virtual const char *getPassName() const {
00054       return "Simple Register Allocator";
00055     }
00056 
00057     /// runOnMachineFunction - Register allocate the whole function
00058     bool runOnMachineFunction(MachineFunction &Fn);
00059 
00060     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00061       AU.addRequiredID(PHIEliminationID);           // Eliminate PHI nodes
00062       MachineFunctionPass::getAnalysisUsage(AU);
00063     }
00064   private:
00065     /// AllocateBasicBlock - Register allocate the specified basic block.
00066     void AllocateBasicBlock(MachineBasicBlock &MBB);
00067 
00068     /// getStackSpaceFor - This returns the offset of the specified virtual
00069     /// register on the stack, allocating space if necessary.
00070     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
00071 
00072     /// Given a virtual register, return a compatible physical register that is
00073     /// currently unused.
00074     ///
00075     /// Side effect: marks that register as being used until manually cleared
00076     ///
00077     unsigned getFreeReg(unsigned virtualReg);
00078 
00079     /// Moves value from memory into that register
00080     unsigned reloadVirtReg(MachineBasicBlock &MBB,
00081                            MachineBasicBlock::iterator I, unsigned VirtReg);
00082 
00083     /// Saves reg value on the stack (maps virtual register to stack value)
00084     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
00085                       unsigned VirtReg, unsigned PhysReg);
00086   };
00087 
00088 }
00089 
00090 /// getStackSpaceFor - This allocates space for the specified virtual
00091 /// register to be held on the stack.
00092 int RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
00093              const TargetRegisterClass *RC) {
00094   // Find the location VirtReg would belong...
00095   std::map<unsigned, int>::iterator I =
00096     StackSlotForVirtReg.lower_bound(VirtReg);
00097 
00098   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
00099     return I->second;          // Already has space allocated?
00100 
00101   // Allocate a new stack object for this spill location...
00102   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
00103                                                        RC->getAlignment());
00104   
00105   // Assign the slot...
00106   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
00107 
00108   return FrameIdx;
00109 }
00110 
00111 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
00112   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(virtualReg);
00113   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
00114   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
00115 
00116   while (1) {
00117     unsigned regIdx = RegClassIdx[RC]++; 
00118     assert(RI+regIdx != RE && "Not enough registers!");
00119     unsigned PhysReg = *(RI+regIdx);
00120     
00121     if (!RegsUsed[PhysReg])
00122       return PhysReg;
00123   }
00124 }
00125 
00126 unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
00127                                        MachineBasicBlock::iterator I,
00128                                        unsigned VirtReg) {
00129   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
00130   int FrameIdx = getStackSpaceFor(VirtReg, RC);
00131   unsigned PhysReg = getFreeReg(VirtReg);
00132 
00133   // Add move instruction(s)
00134   ++NumLoads;
00135   RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx);
00136   return PhysReg;
00137 }
00138 
00139 void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
00140                                   MachineBasicBlock::iterator I,
00141                                   unsigned VirtReg, unsigned PhysReg) {
00142   const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
00143   int FrameIdx = getStackSpaceFor(VirtReg, RC);
00144 
00145   // Add move instruction(s)
00146   ++NumStores;
00147   RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIdx);
00148 }
00149 
00150 
00151 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
00152   // loop over each instruction
00153   for (MachineBasicBlock::iterator MI = MBB.begin(); MI != MBB.end(); ++MI) {
00154     // Made to combat the incorrect allocation of r2 = add r1, r1
00155     std::map<unsigned, unsigned> Virt2PhysRegMap;
00156 
00157     RegsUsed.resize(RegInfo->getNumRegs());
00158     
00159     // a preliminary pass that will invalidate any registers that
00160     // are used by the instruction (including implicit uses)
00161     unsigned Opcode = MI->getOpcode();
00162     const TargetInstrDescriptor &Desc = TM->getInstrInfo()->get(Opcode);
00163     const unsigned *Regs = Desc.ImplicitUses;
00164     while (*Regs)
00165       RegsUsed[*Regs++] = true;
00166     
00167     Regs = Desc.ImplicitDefs;
00168     while (*Regs)
00169       RegsUsed[*Regs++] = true;
00170     
00171     // Loop over uses, move from memory into registers
00172     for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
00173       MachineOperand &op = MI->getOperand(i);
00174       
00175       if (op.isRegister() && op.getReg() &&
00176           MRegisterInfo::isVirtualRegister(op.getReg())) {
00177         unsigned virtualReg = (unsigned) op.getReg();
00178         DEBUG(std::cerr << "op: " << op << "\n");
00179         DEBUG(std::cerr << "\t inst[" << i << "]: ";
00180               MI->print(std::cerr, TM));
00181         
00182         // make sure the same virtual register maps to the same physical
00183         // register in any given instruction
00184         unsigned physReg = Virt2PhysRegMap[virtualReg];
00185         if (physReg == 0) {
00186           if (op.isDef()) {
00187             if (!TM->getInstrInfo()->isTwoAddrInstr(MI->getOpcode()) || i) {
00188               physReg = getFreeReg(virtualReg);
00189             } else {
00190               // must be same register number as the first operand
00191               // This maps a = b + c into b += c, and saves b into a's spot
00192               assert(MI->getOperand(1).isRegister()  &&
00193                      MI->getOperand(1).getReg() &&
00194                      MI->getOperand(1).isUse() &&
00195                      "Two address instruction invalid!");
00196 
00197               physReg = MI->getOperand(1).getReg();
00198               spillVirtReg(MBB, next(MI), virtualReg, physReg);
00199               MI->getOperand(1).setDef();
00200               MI->RemoveOperand(0);
00201               break; // This is the last operand to process
00202             }
00203             spillVirtReg(MBB, next(MI), virtualReg, physReg);
00204           } else {
00205             physReg = reloadVirtReg(MBB, MI, virtualReg);
00206             Virt2PhysRegMap[virtualReg] = physReg;
00207           }
00208         }
00209         MI->SetMachineOperandReg(i, physReg);
00210         DEBUG(std::cerr << "virt: " << virtualReg << 
00211               ", phys: " << op.getReg() << "\n");
00212       }
00213     }
00214     RegClassIdx.clear();
00215     RegsUsed.clear();
00216   }
00217 }
00218 
00219 
00220 /// runOnMachineFunction - Register allocate the whole function
00221 ///
00222 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
00223   DEBUG(std::cerr << "Machine Function " << "\n");
00224   MF = &Fn;
00225   TM = &MF->getTarget();
00226   RegInfo = TM->getRegisterInfo();
00227 
00228   // Loop over all of the basic blocks, eliminating virtual register references
00229   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
00230        MBB != MBBe; ++MBB)
00231     AllocateBasicBlock(*MBB);
00232 
00233   StackSlotForVirtReg.clear();
00234   return true;
00235 }
00236 
00237 FunctionPass *llvm::createSimpleRegisterAllocator() {
00238   return new RegAllocSimple();
00239 }