LLVM API Documentation
00001 //===-- RegAllocLocal.cpp - A BasicBlock 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 register allocator allocates registers to a basic block at a time, 00011 // attempting to keep values in registers and reusing registers as appropriate. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "regalloc" 00016 #include "llvm/BasicBlock.h" 00017 #include "llvm/CodeGen/MachineFunctionPass.h" 00018 #include "llvm/CodeGen/MachineInstr.h" 00019 #include "llvm/CodeGen/MachineFrameInfo.h" 00020 #include "llvm/CodeGen/MachineRegisterInfo.h" 00021 #include "llvm/CodeGen/Passes.h" 00022 #include "llvm/CodeGen/RegAllocRegistry.h" 00023 #include "llvm/Target/TargetInstrInfo.h" 00024 #include "llvm/Target/TargetMachine.h" 00025 #include "llvm/Support/CommandLine.h" 00026 #include "llvm/Support/Debug.h" 00027 #include "llvm/Support/Compiler.h" 00028 #include "llvm/Support/ErrorHandling.h" 00029 #include "llvm/Support/raw_ostream.h" 00030 #include "llvm/ADT/DenseMap.h" 00031 #include "llvm/ADT/IndexedMap.h" 00032 #include "llvm/ADT/SmallSet.h" 00033 #include "llvm/ADT/SmallVector.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/ADT/STLExtras.h" 00036 #include <algorithm> 00037 using namespace llvm; 00038 00039 STATISTIC(NumStores, "Number of stores added"); 00040 STATISTIC(NumLoads , "Number of loads added"); 00041 00042 static RegisterRegAlloc 00043 localRegAlloc("local", "local register allocator", 00044 createLocalRegisterAllocator); 00045 00046 namespace { 00047 class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass { 00048 public: 00049 static char ID; 00050 RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {} 00051 private: 00052 const TargetMachine *TM; 00053 MachineFunction *MF; 00054 const TargetRegisterInfo *TRI; 00055 const TargetInstrInfo *TII; 00056 00057 // StackSlotForVirtReg - Maps virtual regs to the frame index where these 00058 // values are spilled. 00059 IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 00060 00061 // Virt2PhysRegMap - This map contains entries for each virtual register 00062 // that is currently available in a physical register. 00063 IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap; 00064 00065 unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { 00066 return Virt2PhysRegMap[VirtReg]; 00067 } 00068 00069 // PhysRegsUsed - This array is effectively a map, containing entries for 00070 // each physical register that currently has a value (ie, it is in 00071 // Virt2PhysRegMap). The value mapped to is the virtual register 00072 // corresponding to the physical register (the inverse of the 00073 // Virt2PhysRegMap), or 0. The value is set to 0 if this register is pinned 00074 // because it is used by a future instruction, and to -2 if it is not 00075 // allocatable. If the entry for a physical register is -1, then the 00076 // physical register is "not in the map". 00077 // 00078 std::vector<int> PhysRegsUsed; 00079 00080 // PhysRegsUseOrder - This contains a list of the physical registers that 00081 // currently have a virtual register value in them. This list provides an 00082 // ordering of registers, imposing a reallocation order. This list is only 00083 // used if all registers are allocated and we have to spill one, in which 00084 // case we spill the least recently used register. Entries at the front of 00085 // the list are the least recently used registers, entries at the back are 00086 // the most recently used. 00087 // 00088 std::vector<unsigned> PhysRegsUseOrder; 00089 00090 // Virt2LastUseMap - This maps each virtual register to its last use 00091 // (MachineInstr*, operand index pair). 00092 IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor> 00093 Virt2LastUseMap; 00094 00095 std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) { 00096 assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); 00097 return Virt2LastUseMap[Reg]; 00098 } 00099 00100 // VirtRegModified - This bitset contains information about which virtual 00101 // registers need to be spilled back to memory when their registers are 00102 // scavenged. If a virtual register has simply been rematerialized, there 00103 // is no reason to spill it to memory when we need the register back. 00104 // 00105 BitVector VirtRegModified; 00106 00107 // UsedInMultipleBlocks - Tracks whether a particular register is used in 00108 // more than one block. 00109 BitVector UsedInMultipleBlocks; 00110 00111 void markVirtRegModified(unsigned Reg, bool Val = true) { 00112 assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); 00113 Reg -= TargetRegisterInfo::FirstVirtualRegister; 00114 if (Val) 00115 VirtRegModified.set(Reg); 00116 else 00117 VirtRegModified.reset(Reg); 00118 } 00119 00120 bool isVirtRegModified(unsigned Reg) const { 00121 assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); 00122 assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size() 00123 && "Illegal virtual register!"); 00124 return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; 00125 } 00126 00127 void AddToPhysRegsUseOrder(unsigned Reg) { 00128 std::vector<unsigned>::iterator It = 00129 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg); 00130 if (It != PhysRegsUseOrder.end()) 00131 PhysRegsUseOrder.erase(It); 00132 PhysRegsUseOrder.push_back(Reg); 00133 } 00134 00135 void MarkPhysRegRecentlyUsed(unsigned Reg) { 00136 if (PhysRegsUseOrder.empty() || 00137 PhysRegsUseOrder.back() == Reg) return; // Already most recently used 00138 00139 for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) 00140 if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { 00141 unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle 00142 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); 00143 // Add it to the end of the list 00144 PhysRegsUseOrder.push_back(RegMatch); 00145 if (RegMatch == Reg) 00146 return; // Found an exact match, exit early 00147 } 00148 } 00149 00150 public: 00151 virtual const char *getPassName() const { 00152 return "Local Register Allocator"; 00153 } 00154 00155 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00156 AU.setPreservesCFG(); 00157 AU.addRequiredID(PHIEliminationID); 00158 AU.addRequiredID(TwoAddressInstructionPassID); 00159 MachineFunctionPass::getAnalysisUsage(AU); 00160 } 00161 00162 private: 00163 /// runOnMachineFunction - Register allocate the whole function 00164 bool runOnMachineFunction(MachineFunction &Fn); 00165 00166 /// AllocateBasicBlock - Register allocate the specified basic block. 00167 void AllocateBasicBlock(MachineBasicBlock &MBB); 00168 00169 00170 /// areRegsEqual - This method returns true if the specified registers are 00171 /// related to each other. To do this, it checks to see if they are equal 00172 /// or if the first register is in the alias set of the second register. 00173 /// 00174 bool areRegsEqual(unsigned R1, unsigned R2) const { 00175 if (R1 == R2) return true; 00176 for (const unsigned *AliasSet = TRI->getAliasSet(R2); 00177 *AliasSet; ++AliasSet) { 00178 if (*AliasSet == R1) return true; 00179 } 00180 return false; 00181 } 00182 00183 /// getStackSpaceFor - This returns the frame index of the specified virtual 00184 /// register on the stack, allocating space if necessary. 00185 int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 00186 00187 /// removePhysReg - This method marks the specified physical register as no 00188 /// longer being in use. 00189 /// 00190 void removePhysReg(unsigned PhysReg); 00191 00192 /// spillVirtReg - This method spills the value specified by PhysReg into 00193 /// the virtual register slot specified by VirtReg. It then updates the RA 00194 /// data structures to indicate the fact that PhysReg is now available. 00195 /// 00196 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 00197 unsigned VirtReg, unsigned PhysReg); 00198 00199 /// spillPhysReg - This method spills the specified physical register into 00200 /// the virtual register slot associated with it. If OnlyVirtRegs is set to 00201 /// true, then the request is ignored if the physical register does not 00202 /// contain a virtual register. 00203 /// 00204 void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 00205 unsigned PhysReg, bool OnlyVirtRegs = false); 00206 00207 /// assignVirtToPhysReg - This method updates local state so that we know 00208 /// that PhysReg is the proper container for VirtReg now. The physical 00209 /// register must not be used for anything else when this is called. 00210 /// 00211 void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); 00212 00213 /// isPhysRegAvailable - Return true if the specified physical register is 00214 /// free and available for use. This also includes checking to see if 00215 /// aliased registers are all free... 00216 /// 00217 bool isPhysRegAvailable(unsigned PhysReg) const; 00218 00219 /// getFreeReg - Look to see if there is a free register available in the 00220 /// specified register class. If not, return 0. 00221 /// 00222 unsigned getFreeReg(const TargetRegisterClass *RC); 00223 00224 /// getReg - Find a physical register to hold the specified virtual 00225 /// register. If all compatible physical registers are used, this method 00226 /// spills the last used virtual register to the stack, and uses that 00227 /// register. If NoFree is true, that means the caller knows there isn't 00228 /// a free register, do not call getFreeReg(). 00229 unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI, 00230 unsigned VirtReg, bool NoFree = false); 00231 00232 /// reloadVirtReg - This method transforms the specified virtual 00233 /// register use to refer to a physical register. This method may do this 00234 /// in one of several ways: if the register is available in a physical 00235 /// register already, it uses that physical register. If the value is not 00236 /// in a physical register, and if there are physical registers available, 00237 /// it loads it into a register. If register pressure is high, and it is 00238 /// possible, it tries to fold the load of the virtual register into the 00239 /// instruction itself. It avoids doing this if register pressure is low to 00240 /// improve the chance that subsequent instructions can use the reloaded 00241 /// value. This method returns the modified instruction. 00242 /// 00243 MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 00244 unsigned OpNum, SmallSet<unsigned, 4> &RRegs); 00245 00246 /// ComputeLocalLiveness - Computes liveness of registers within a basic 00247 /// block, setting the killed/dead flags as appropriate. 00248 void ComputeLocalLiveness(MachineBasicBlock& MBB); 00249 00250 void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, 00251 unsigned PhysReg); 00252 }; 00253 char RALocal::ID = 0; 00254 } 00255 00256 /// getStackSpaceFor - This allocates space for the specified virtual register 00257 /// to be held on the stack. 00258 int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 00259 // Find the location Reg would belong... 00260 int SS = StackSlotForVirtReg[VirtReg]; 00261 if (SS != -1) 00262 return SS; // Already has space allocated? 00263 00264 // Allocate a new stack object for this spill location... 00265 int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), 00266 RC->getAlignment()); 00267 00268 // Assign the slot... 00269 StackSlotForVirtReg[VirtReg] = FrameIdx; 00270 return FrameIdx; 00271 } 00272 00273 00274 /// removePhysReg - This method marks the specified physical register as no 00275 /// longer being in use. 00276 /// 00277 void RALocal::removePhysReg(unsigned PhysReg) { 00278 PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used 00279 00280 std::vector<unsigned>::iterator It = 00281 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); 00282 if (It != PhysRegsUseOrder.end()) 00283 PhysRegsUseOrder.erase(It); 00284 } 00285 00286 00287 /// spillVirtReg - This method spills the value specified by PhysReg into the 00288 /// virtual register slot specified by VirtReg. It then updates the RA data 00289 /// structures to indicate the fact that PhysReg is now available. 00290 /// 00291 void RALocal::spillVirtReg(MachineBasicBlock &MBB, 00292 MachineBasicBlock::iterator I, 00293 unsigned VirtReg, unsigned PhysReg) { 00294 assert(VirtReg && "Spilling a physical register is illegal!" 00295 " Must not have appropriate kill for the register or use exists beyond" 00296 " the intended one."); 00297 DOUT << " Spilling register " << TRI->getName(PhysReg) 00298 << " containing %reg" << VirtReg; 00299 00300 if (!isVirtRegModified(VirtReg)) { 00301 DOUT << " which has not been modified, so no store necessary!"; 00302 std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg); 00303 if (LastUse.first) 00304 LastUse.first->getOperand(LastUse.second).setIsKill(); 00305 } else { 00306 // Otherwise, there is a virtual register corresponding to this physical 00307 // register. We only need to spill it into its stack slot if it has been 00308 // modified. 00309 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 00310 int FrameIndex = getStackSpaceFor(VirtReg, RC); 00311 DOUT << " to stack slot #" << FrameIndex; 00312 // If the instruction reads the register that's spilled, (e.g. this can 00313 // happen if it is a move to a physical register), then the spill 00314 // instruction is not a kill. 00315 bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg)); 00316 TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC); 00317 ++NumStores; // Update statistics 00318 } 00319 00320 getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available 00321 00322 DOUT << "\n"; 00323 removePhysReg(PhysReg); 00324 } 00325 00326 00327 /// spillPhysReg - This method spills the specified physical register into the 00328 /// virtual register slot associated with it. If OnlyVirtRegs is set to true, 00329 /// then the request is ignored if the physical register does not contain a 00330 /// virtual register. 00331 /// 00332 void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 00333 unsigned PhysReg, bool OnlyVirtRegs) { 00334 if (PhysRegsUsed[PhysReg] != -1) { // Only spill it if it's used! 00335 assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!"); 00336 if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs) 00337 spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg); 00338 } else { 00339 // If the selected register aliases any other registers, we must make 00340 // sure that one of the aliases isn't alive. 00341 for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); 00342 *AliasSet; ++AliasSet) 00343 if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. 00344 PhysRegsUsed[*AliasSet] != -2) // If allocatable. 00345 if (PhysRegsUsed[*AliasSet]) 00346 spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); 00347 } 00348 } 00349 00350 00351 /// assignVirtToPhysReg - This method updates local state so that we know 00352 /// that PhysReg is the proper container for VirtReg now. The physical 00353 /// register must not be used for anything else when this is called. 00354 /// 00355 void RALocal::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 00356 assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!"); 00357 // Update information to note the fact that this register was just used, and 00358 // it holds VirtReg. 00359 PhysRegsUsed[PhysReg] = VirtReg; 00360 getVirt2PhysRegMapSlot(VirtReg) = PhysReg; 00361 AddToPhysRegsUseOrder(PhysReg); // New use of PhysReg 00362 } 00363 00364 00365 /// isPhysRegAvailable - Return true if the specified physical register is free 00366 /// and available for use. This also includes checking to see if aliased 00367 /// registers are all free... 00368 /// 00369 bool RALocal::isPhysRegAvailable(unsigned PhysReg) const { 00370 if (PhysRegsUsed[PhysReg] != -1) return false; 00371 00372 // If the selected register aliases any other allocated registers, it is 00373 // not free! 00374 for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); 00375 *AliasSet; ++AliasSet) 00376 if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use? 00377 return false; // Can't use this reg then. 00378 return true; 00379 } 00380 00381 00382 /// getFreeReg - Look to see if there is a free register available in the 00383 /// specified register class. If not, return 0. 00384 /// 00385 unsigned RALocal::getFreeReg(const TargetRegisterClass *RC) { 00386 // Get iterators defining the range of registers that are valid to allocate in 00387 // this class, which also specifies the preferred allocation order. 00388 TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); 00389 TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); 00390 00391 for (; RI != RE; ++RI) 00392 if (isPhysRegAvailable(*RI)) { // Is reg unused? 00393 assert(*RI != 0 && "Cannot use register!"); 00394 return *RI; // Found an unused register! 00395 } 00396 return 0; 00397 } 00398 00399 00400 /// getReg - Find a physical register to hold the specified virtual 00401 /// register. If all compatible physical registers are used, this method spills 00402 /// the last used virtual register to the stack, and uses that register. 00403 /// 00404 unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, 00405 unsigned VirtReg, bool NoFree) { 00406 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 00407 00408 // First check to see if we have a free register of the requested type... 00409 unsigned PhysReg = NoFree ? 0 : getFreeReg(RC); 00410 00411 // If we didn't find an unused register, scavenge one now! 00412 if (PhysReg == 0) { 00413 assert(!PhysRegsUseOrder.empty() && "No allocated registers??"); 00414 00415 // Loop over all of the preallocated registers from the least recently used 00416 // to the most recently used. When we find one that is capable of holding 00417 // our register, use it. 00418 for (unsigned i = 0; PhysReg == 0; ++i) { 00419 assert(i != PhysRegsUseOrder.size() && 00420 "Couldn't find a register of the appropriate class!"); 00421 00422 unsigned R = PhysRegsUseOrder[i]; 00423 00424 // We can only use this register if it holds a virtual register (ie, it 00425 // can be spilled). Do not use it if it is an explicitly allocated 00426 // physical register! 00427 assert(PhysRegsUsed[R] != -1 && 00428 "PhysReg in PhysRegsUseOrder, but is not allocated?"); 00429 if (PhysRegsUsed[R] && PhysRegsUsed[R] != -2) { 00430 // If the current register is compatible, use it. 00431 if (RC->contains(R)) { 00432 PhysReg = R; 00433 break; 00434 } else { 00435 // If one of the registers aliased to the current register is 00436 // compatible, use it. 00437 for (const unsigned *AliasIt = TRI->getAliasSet(R); 00438 *AliasIt; ++AliasIt) { 00439 if (RC->contains(*AliasIt) && 00440 // If this is pinned down for some reason, don't use it. For 00441 // example, if CL is pinned, and we run across CH, don't use 00442 // CH as justification for using scavenging ECX (which will 00443 // fail). 00444 PhysRegsUsed[*AliasIt] != 0 && 00445 00446 // Make sure the register is allocatable. Don't allocate SIL on 00447 // x86-32. 00448 PhysRegsUsed[*AliasIt] != -2) { 00449 PhysReg = *AliasIt; // Take an aliased register 00450 break; 00451 } 00452 } 00453 } 00454 } 00455 } 00456 00457 assert(PhysReg && "Physical register not assigned!?!?"); 00458 00459 // At this point PhysRegsUseOrder[i] is the least recently used register of 00460 // compatible register class. Spill it to memory and reap its remains. 00461 spillPhysReg(MBB, I, PhysReg); 00462 } 00463 00464 // Now that we know which register we need to assign this to, do it now! 00465 assignVirtToPhysReg(VirtReg, PhysReg); 00466 return PhysReg; 00467 } 00468 00469 00470 /// reloadVirtReg - This method transforms the specified virtual 00471 /// register use to refer to a physical register. This method may do this in 00472 /// one of several ways: if the register is available in a physical register 00473 /// already, it uses that physical register. If the value is not in a physical 00474 /// register, and if there are physical registers available, it loads it into a 00475 /// register. If register pressure is high, and it is possible, it tries to 00476 /// fold the load of the virtual register into the instruction itself. It 00477 /// avoids doing this if register pressure is low to improve the chance that 00478 /// subsequent instructions can use the reloaded value. This method returns the 00479 /// modified instruction. 00480 /// 00481 MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 00482 unsigned OpNum, 00483 SmallSet<unsigned, 4> &ReloadedRegs) { 00484 unsigned VirtReg = MI->getOperand(OpNum).getReg(); 00485 00486 // If the virtual register is already available, just update the instruction 00487 // and return. 00488 if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { 00489 MarkPhysRegRecentlyUsed(PR); // Already have this value available! 00490 MI->getOperand(OpNum).setReg(PR); // Assign the input register 00491 getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); 00492 return MI; 00493 } 00494 00495 // Otherwise, we need to fold it into the current instruction, or reload it. 00496 // If we have registers available to hold the value, use them. 00497 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 00498 unsigned PhysReg = getFreeReg(RC); 00499 int FrameIndex = getStackSpaceFor(VirtReg, RC); 00500 00501 if (PhysReg) { // Register is available, allocate it! 00502 assignVirtToPhysReg(VirtReg, PhysReg); 00503 } else { // No registers available. 00504 // Force some poor hapless value out of the register file to 00505 // make room for the new register, and reload it. 00506 PhysReg = getReg(MBB, MI, VirtReg, true); 00507 } 00508 00509 markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded 00510 00511 DOUT << " Reloading %reg" << VirtReg << " into " 00512 << TRI->getName(PhysReg) << "\n"; 00513 00514 // Add move instruction(s) 00515 TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); 00516 ++NumLoads; // Update statistics 00517 00518 MF->getRegInfo().setPhysRegUsed(PhysReg); 00519 MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register 00520 getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); 00521 00522 if (!ReloadedRegs.insert(PhysReg)) { 00523 std::string msg; 00524 raw_string_ostream Msg(msg); 00525 Msg << "Ran out of registers during register allocation!"; 00526 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 00527 Msg << "\nPlease check your inline asm statement for invalid " 00528 << "constraints:\n"; 00529 MI->print(Msg, TM); 00530 } 00531 llvm_report_error(Msg.str()); 00532 } 00533 for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); 00534 *SubRegs; ++SubRegs) { 00535 if (!ReloadedRegs.insert(*SubRegs)) { 00536 std::string msg; 00537 raw_string_ostream Msg(msg); 00538 Msg << "Ran out of registers during register allocation!"; 00539 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 00540 Msg << "\nPlease check your inline asm statement for invalid " 00541 << "constraints:\n"; 00542 MI->print(Msg, TM); 00543 } 00544 llvm_report_error(Msg.str()); 00545 } 00546 } 00547 00548 return MI; 00549 } 00550 00551 /// isReadModWriteImplicitKill - True if this is an implicit kill for a 00552 /// read/mod/write register, i.e. update partial register. 00553 static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { 00554 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00555 MachineOperand& MO = MI->getOperand(i); 00556 if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && 00557 MO.isDef() && !MO.isDead()) 00558 return true; 00559 } 00560 return false; 00561 } 00562 00563 /// isReadModWriteImplicitDef - True if this is an implicit def for a 00564 /// read/mod/write register, i.e. update partial register. 00565 static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) { 00566 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00567 MachineOperand& MO = MI->getOperand(i); 00568 if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() && 00569 !MO.isDef() && MO.isKill()) 00570 return true; 00571 } 00572 return false; 00573 } 00574 00575 // precedes - Helper function to determine with MachineInstr A 00576 // precedes MachineInstr B within the same MBB. 00577 static bool precedes(MachineBasicBlock::iterator A, 00578 MachineBasicBlock::iterator B) { 00579 if (A == B) 00580 return false; 00581 00582 MachineBasicBlock::iterator I = A->getParent()->begin(); 00583 while (I != A->getParent()->end()) { 00584 if (I == A) 00585 return true; 00586 else if (I == B) 00587 return false; 00588 00589 ++I; 00590 } 00591 00592 return false; 00593 } 00594 00595 /// ComputeLocalLiveness - Computes liveness of registers within a basic 00596 /// block, setting the killed/dead flags as appropriate. 00597 void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) { 00598 MachineRegisterInfo& MRI = MBB.getParent()->getRegInfo(); 00599 // Keep track of the most recently seen previous use or def of each reg, 00600 // so that we can update them with dead/kill markers. 00601 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > LastUseDef; 00602 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 00603 I != E; ++I) { 00604 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 00605 MachineOperand& MO = I->getOperand(i); 00606 // Uses don't trigger any flags, but we need to save 00607 // them for later. Also, we have to process these 00608 // _before_ processing the defs, since an instr 00609 // uses regs before it defs them. 00610 if (MO.isReg() && MO.getReg() && MO.isUse()) { 00611 LastUseDef[MO.getReg()] = std::make_pair(I, i); 00612 00613 00614 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) continue; 00615 00616 const unsigned* Aliases = TRI->getAliasSet(MO.getReg()); 00617 if (Aliases) { 00618 while (*Aliases) { 00619 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator 00620 alias = LastUseDef.find(*Aliases); 00621 00622 if (alias != LastUseDef.end() && alias->second.first != I) 00623 LastUseDef[*Aliases] = std::make_pair(I, i); 00624 00625 ++Aliases; 00626 } 00627 } 00628 } 00629 } 00630 00631 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 00632 MachineOperand& MO = I->getOperand(i); 00633 // Defs others than 2-addr redefs _do_ trigger flag changes: 00634 // - A def followed by a def is dead 00635 // - A use followed by a def is a kill 00636 if (MO.isReg() && MO.getReg() && MO.isDef()) { 00637 DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator 00638 last = LastUseDef.find(MO.getReg()); 00639 if (last != LastUseDef.end()) { 00640 // Check if this is a two address instruction. If so, then 00641 // the def does not kill the use. 00642 if (last->second.first == I && 00643 I->isRegTiedToUseOperand(i)) 00644 continue; 00645 00646 MachineOperand& lastUD = 00647 last->second.first->getOperand(last->second.second); 00648 if (lastUD.isDef()) 00649 lastUD.setIsDead(true); 00650 else 00651 lastUD.setIsKill(true); 00652 } 00653 00654 LastUseDef[MO.getReg()] = std::make_pair(I, i); 00655 } 00656 } 00657 } 00658 00659 // Live-out (of the function) registers contain return values of the function, 00660 // so we need to make sure they are alive at return time. 00661 if (!MBB.empty() && MBB.back().getDesc().isReturn()) { 00662 MachineInstr* Ret = &MBB.back(); 00663 for (MachineRegisterInfo::liveout_iterator 00664 I = MF->getRegInfo().liveout_begin(), 00665 E = MF->getRegInfo().liveout_end(); I != E; ++I) 00666 if (!Ret->readsRegister(*I)) { 00667 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 00668 LastUseDef[*I] = std::make_pair(Ret, Ret->getNumOperands()-1); 00669 } 00670 } 00671 00672 // Finally, loop over the final use/def of each reg 00673 // in the block and determine if it is dead. 00674 for (DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator 00675 I = LastUseDef.begin(), E = LastUseDef.end(); I != E; ++I) { 00676 MachineInstr* MI = I->second.first; 00677 unsigned idx = I->second.second; 00678 MachineOperand& MO = MI->getOperand(idx); 00679 00680 bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(MO.getReg()); 00681 00682 // A crude approximation of "live-out" calculation 00683 bool usedOutsideBlock = isPhysReg ? false : 00684 UsedInMultipleBlocks.test(MO.getReg() - 00685 TargetRegisterInfo::FirstVirtualRegister); 00686 if (!isPhysReg && !usedOutsideBlock) 00687 for (MachineRegisterInfo::reg_iterator UI = MRI.reg_begin(MO.getReg()), 00688 UE = MRI.reg_end(); UI != UE; ++UI) 00689 // Two cases: 00690 // - used in another block 00691 // - used in the same block before it is defined (loop) 00692 if (UI->getParent() != &MBB || 00693 (MO.isDef() && UI.getOperand().isUse() && precedes(&*UI, MI))) { 00694 UsedInMultipleBlocks.set(MO.getReg() - 00695 TargetRegisterInfo::FirstVirtualRegister); 00696 usedOutsideBlock = true; 00697 break; 00698 } 00699 00700 // Physical registers and those that are not live-out of the block 00701 // are killed/dead at their last use/def within this block. 00702 if (isPhysReg || !usedOutsideBlock) { 00703 if (MO.isUse()) { 00704 // Don't mark uses that are tied to defs as kills. 00705 if (!MI->isRegTiedToDefOperand(idx)) 00706 MO.setIsKill(true); 00707 } else 00708 MO.setIsDead(true); 00709 } 00710 } 00711 } 00712 00713 void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { 00714 // loop over each instruction 00715 MachineBasicBlock::iterator MII = MBB.begin(); 00716 00717 DEBUG(const BasicBlock *LBB = MBB.getBasicBlock(); 00718 if (LBB) errs() << "\nStarting RegAlloc of BB: " << LBB->getName()); 00719 00720 // Add live-in registers as active. 00721 for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), 00722 E = MBB.livein_end(); I != E; ++I) { 00723 unsigned Reg = *I; 00724 MF->getRegInfo().setPhysRegUsed(Reg); 00725 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00726 AddToPhysRegsUseOrder(Reg); 00727 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00728 *SubRegs; ++SubRegs) { 00729 if (PhysRegsUsed[*SubRegs] != -2) { 00730 AddToPhysRegsUseOrder(*SubRegs); 00731 PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now 00732 MF->getRegInfo().setPhysRegUsed(*SubRegs); 00733 } 00734 } 00735 } 00736 00737 ComputeLocalLiveness(MBB); 00738 00739 // Otherwise, sequentially allocate each instruction in the MBB. 00740 while (MII != MBB.end()) { 00741 MachineInstr *MI = MII++; 00742 const TargetInstrDesc &TID = MI->getDesc(); 00743 DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; 00744 DOUT << " Regs have values: "; 00745 for (unsigned i = 0; i != TRI->getNumRegs(); ++i) 00746 if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) 00747 DOUT << "[" << TRI->getName(i) 00748 << ",%reg" << PhysRegsUsed[i] << "] "; 00749 DOUT << "\n"); 00750 00751 // Loop over the implicit uses, making sure that they are at the head of the 00752 // use order list, so they don't get reallocated. 00753 if (TID.ImplicitUses) { 00754 for (const unsigned *ImplicitUses = TID.ImplicitUses; 00755 *ImplicitUses; ++ImplicitUses) 00756 MarkPhysRegRecentlyUsed(*ImplicitUses); 00757 } 00758 00759 SmallVector<unsigned, 8> Kills; 00760 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00761 MachineOperand& MO = MI->getOperand(i); 00762 if (MO.isReg() && MO.isKill()) { 00763 if (!MO.isImplicit()) 00764 Kills.push_back(MO.getReg()); 00765 else if (!isReadModWriteImplicitKill(MI, MO.getReg())) 00766 // These are extra physical register kills when a sub-register 00767 // is defined (def of a sub-register is a read/mod/write of the 00768 // larger registers). Ignore. 00769 Kills.push_back(MO.getReg()); 00770 } 00771 } 00772 00773 // If any physical regs are earlyclobber, spill any value they might 00774 // have in them, then mark them unallocatable. 00775 // If any virtual regs are earlyclobber, allocate them now (before 00776 // freeing inputs that are killed). 00777 if (MI->getOpcode()==TargetInstrInfo::INLINEASM) { 00778 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00779 MachineOperand& MO = MI->getOperand(i); 00780 if (MO.isReg() && MO.isDef() && MO.isEarlyClobber() && 00781 MO.getReg()) { 00782 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 00783 unsigned DestVirtReg = MO.getReg(); 00784 unsigned DestPhysReg; 00785 00786 // If DestVirtReg already has a value, use it. 00787 if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) 00788 DestPhysReg = getReg(MBB, MI, DestVirtReg); 00789 MF->getRegInfo().setPhysRegUsed(DestPhysReg); 00790 markVirtRegModified(DestVirtReg); 00791 getVirtRegLastUse(DestVirtReg) = 00792 std::make_pair((MachineInstr*)0, 0); 00793 DOUT << " Assigning " << TRI->getName(DestPhysReg) 00794 << " to %reg" << DestVirtReg << "\n"; 00795 MO.setReg(DestPhysReg); // Assign the earlyclobber register 00796 } else { 00797 unsigned Reg = MO.getReg(); 00798 if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. 00799 // These are extra physical register defs when a sub-register 00800 // is defined (def of a sub-register is a read/mod/write of the 00801 // larger registers). Ignore. 00802 if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; 00803 00804 MF->getRegInfo().setPhysRegUsed(Reg); 00805 spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg 00806 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00807 AddToPhysRegsUseOrder(Reg); 00808 00809 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00810 *SubRegs; ++SubRegs) { 00811 if (PhysRegsUsed[*SubRegs] != -2) { 00812 MF->getRegInfo().setPhysRegUsed(*SubRegs); 00813 PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now 00814 AddToPhysRegsUseOrder(*SubRegs); 00815 } 00816 } 00817 } 00818 } 00819 } 00820 } 00821 00822 // Get the used operands into registers. This has the potential to spill 00823 // incoming values if we are out of registers. Note that we completely 00824 // ignore physical register uses here. We assume that if an explicit 00825 // physical register is referenced by the instruction, that it is guaranteed 00826 // to be live-in, or the input is badly hosed. 00827 // 00828 SmallSet<unsigned, 4> ReloadedRegs; 00829 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00830 MachineOperand& MO = MI->getOperand(i); 00831 // here we are looking for only used operands (never def&use) 00832 if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && 00833 TargetRegisterInfo::isVirtualRegister(MO.getReg())) 00834 MI = reloadVirtReg(MBB, MI, i, ReloadedRegs); 00835 } 00836 00837 // If this instruction is the last user of this register, kill the 00838 // value, freeing the register being used, so it doesn't need to be 00839 // spilled to memory. 00840 // 00841 for (unsigned i = 0, e = Kills.size(); i != e; ++i) { 00842 unsigned VirtReg = Kills[i]; 00843 unsigned PhysReg = VirtReg; 00844 if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { 00845 // If the virtual register was never materialized into a register, it 00846 // might not be in the map, but it won't hurt to zero it out anyway. 00847 unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); 00848 PhysReg = PhysRegSlot; 00849 PhysRegSlot = 0; 00850 } else if (PhysRegsUsed[PhysReg] == -2) { 00851 // Unallocatable register dead, ignore. 00852 continue; 00853 } else { 00854 assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && 00855 "Silently clearing a virtual register?"); 00856 } 00857 00858 if (PhysReg) { 00859 DOUT << " Last use of " << TRI->getName(PhysReg) 00860 << "[%reg" << VirtReg <<"], removing it from live set\n"; 00861 removePhysReg(PhysReg); 00862 for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); 00863 *SubRegs; ++SubRegs) { 00864 if (PhysRegsUsed[*SubRegs] != -2) { 00865 DOUT << " Last use of " 00866 << TRI->getName(*SubRegs) 00867 << "[%reg" << VirtReg <<"], removing it from live set\n"; 00868 removePhysReg(*SubRegs); 00869 } 00870 } 00871 } 00872 } 00873 00874 // Loop over all of the operands of the instruction, spilling registers that 00875 // are defined, and marking explicit destinations in the PhysRegsUsed map. 00876 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00877 MachineOperand& MO = MI->getOperand(i); 00878 if (MO.isReg() && MO.isDef() && !MO.isImplicit() && MO.getReg() && 00879 !MO.isEarlyClobber() && 00880 TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 00881 unsigned Reg = MO.getReg(); 00882 if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. 00883 // These are extra physical register defs when a sub-register 00884 // is defined (def of a sub-register is a read/mod/write of the 00885 // larger registers). Ignore. 00886 if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; 00887 00888 MF->getRegInfo().setPhysRegUsed(Reg); 00889 spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg 00890 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00891 AddToPhysRegsUseOrder(Reg); 00892 00893 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00894 *SubRegs; ++SubRegs) { 00895 if (PhysRegsUsed[*SubRegs] != -2) { 00896 MF->getRegInfo().setPhysRegUsed(*SubRegs); 00897 PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now 00898 AddToPhysRegsUseOrder(*SubRegs); 00899 } 00900 } 00901 } 00902 } 00903 00904 // Loop over the implicit defs, spilling them as well. 00905 if (TID.ImplicitDefs) { 00906 for (const unsigned *ImplicitDefs = TID.ImplicitDefs; 00907 *ImplicitDefs; ++ImplicitDefs) { 00908 unsigned Reg = *ImplicitDefs; 00909 if (PhysRegsUsed[Reg] != -2) { 00910 spillPhysReg(MBB, MI, Reg, true); 00911 AddToPhysRegsUseOrder(Reg); 00912 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00913 } 00914 MF->getRegInfo().setPhysRegUsed(Reg); 00915 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00916 *SubRegs; ++SubRegs) { 00917 if (PhysRegsUsed[*SubRegs] != -2) { 00918 AddToPhysRegsUseOrder(*SubRegs); 00919 PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now 00920 MF->getRegInfo().setPhysRegUsed(*SubRegs); 00921 } 00922 } 00923 } 00924 } 00925 00926 SmallVector<unsigned, 8> DeadDefs; 00927 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00928 MachineOperand& MO = MI->getOperand(i); 00929 if (MO.isReg() && MO.isDead()) 00930 DeadDefs.push_back(MO.getReg()); 00931 } 00932 00933 // Okay, we have allocated all of the source operands and spilled any values 00934 // that would be destroyed by defs of this instruction. Loop over the 00935 // explicit defs and assign them to a register, spilling incoming values if 00936 // we need to scavenge a register. 00937 // 00938 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00939 MachineOperand& MO = MI->getOperand(i); 00940 if (MO.isReg() && MO.isDef() && MO.getReg() && 00941 !MO.isEarlyClobber() && 00942 TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 00943 unsigned DestVirtReg = MO.getReg(); 00944 unsigned DestPhysReg; 00945 00946 // If DestVirtReg already has a value, use it. 00947 if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) 00948 DestPhysReg = getReg(MBB, MI, DestVirtReg); 00949 MF->getRegInfo().setPhysRegUsed(DestPhysReg); 00950 markVirtRegModified(DestVirtReg); 00951 getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); 00952 DOUT << " Assigning " << TRI->getName(DestPhysReg) 00953 << " to %reg" << DestVirtReg << "\n"; 00954 MO.setReg(DestPhysReg); // Assign the output register 00955 } 00956 } 00957 00958 // If this instruction defines any registers that are immediately dead, 00959 // kill them now. 00960 // 00961 for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { 00962 unsigned VirtReg = DeadDefs[i]; 00963 unsigned PhysReg = VirtReg; 00964 if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { 00965 unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); 00966 PhysReg = PhysRegSlot; 00967 assert(PhysReg != 0); 00968 PhysRegSlot = 0; 00969 } else if (PhysRegsUsed[PhysReg] == -2) { 00970 // Unallocatable register dead, ignore. 00971 continue; 00972 } 00973 00974 if (PhysReg) { 00975 DOUT << " Register " << TRI->getName(PhysReg) 00976 << " [%reg" << VirtReg 00977 << "] is never used, removing it from live set\n"; 00978 removePhysReg(PhysReg); 00979 for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); 00980 *AliasSet; ++AliasSet) { 00981 if (PhysRegsUsed[*AliasSet] != -2) { 00982 DOUT << " Register " << TRI->getName(*AliasSet) 00983 << " [%reg" << *AliasSet 00984 << "] is never used, removing it from live set\n"; 00985 removePhysReg(*AliasSet); 00986 } 00987 } 00988 } 00989 } 00990 00991 // Finally, if this is a noop copy instruction, zap it. (Except that if 00992 // the copy is dead, it must be kept to avoid messing up liveness info for 00993 // the register scavenger. See pr4100.) 00994 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00995 if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 00996 SrcReg == DstReg && DeadDefs.empty()) 00997 MBB.erase(MI); 00998 } 00999 01000 MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); 01001 01002 // Spill all physical registers holding virtual registers now. 01003 for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) 01004 if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) { 01005 if (unsigned VirtReg = PhysRegsUsed[i]) 01006 spillVirtReg(MBB, MI, VirtReg, i); 01007 else 01008 removePhysReg(i); 01009 } 01010 01011 #if 0 01012 // This checking code is very expensive. 01013 bool AllOk = true; 01014 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, 01015 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) 01016 if (unsigned PR = Virt2PhysRegMap[i]) { 01017 cerr << "Register still mapped: " << i << " -> " << PR << "\n"; 01018 AllOk = false; 01019 } 01020 assert(AllOk && "Virtual registers still in phys regs?"); 01021 #endif 01022 01023 // Clear any physical register which appear live at the end of the basic 01024 // block, but which do not hold any virtual registers. e.g., the stack 01025 // pointer. 01026 PhysRegsUseOrder.clear(); 01027 } 01028 01029 /// runOnMachineFunction - Register allocate the whole function 01030 /// 01031 bool RALocal::runOnMachineFunction(MachineFunction &Fn) { 01032 DOUT << "Machine Function " << "\n"; 01033 MF = &Fn; 01034 TM = &Fn.getTarget(); 01035 TRI = TM->getRegisterInfo(); 01036 TII = TM->getInstrInfo(); 01037 01038 PhysRegsUsed.assign(TRI->getNumRegs(), -1); 01039 01040 // At various places we want to efficiently check to see whether a register 01041 // is allocatable. To handle this, we mark all unallocatable registers as 01042 // being pinned down, permanently. 01043 { 01044 BitVector Allocable = TRI->getAllocatableSet(Fn); 01045 for (unsigned i = 0, e = Allocable.size(); i != e; ++i) 01046 if (!Allocable[i]) 01047 PhysRegsUsed[i] = -2; // Mark the reg unallocable. 01048 } 01049 01050 // initialize the virtual->physical register map to have a 'null' 01051 // mapping for all virtual registers 01052 unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); 01053 StackSlotForVirtReg.grow(LastVirtReg); 01054 Virt2PhysRegMap.grow(LastVirtReg); 01055 Virt2LastUseMap.grow(LastVirtReg); 01056 VirtRegModified.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister); 01057 UsedInMultipleBlocks.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister); 01058 01059 // Loop over all of the basic blocks, eliminating virtual register references 01060 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 01061 MBB != MBBe; ++MBB) 01062 AllocateBasicBlock(*MBB); 01063 01064 StackSlotForVirtReg.clear(); 01065 PhysRegsUsed.clear(); 01066 VirtRegModified.clear(); 01067 UsedInMultipleBlocks.clear(); 01068 Virt2PhysRegMap.clear(); 01069 Virt2LastUseMap.clear(); 01070 return true; 01071 } 01072 01073 FunctionPass *llvm::createLocalRegisterAllocator() { 01074 return new RALocal(); 01075 }