LLVM API Documentation
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 }