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