LLVM API Documentation
00001 //===-- RegAllocLocal.cpp - A BasicBlock 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 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/CodeGen/Passes.h" 00017 #include "llvm/CodeGen/MachineFunctionPass.h" 00018 #include "llvm/CodeGen/MachineInstr.h" 00019 #include "llvm/CodeGen/SSARegMap.h" 00020 #include "llvm/CodeGen/MachineFrameInfo.h" 00021 #include "llvm/CodeGen/LiveVariables.h" 00022 #include "llvm/Target/TargetInstrInfo.h" 00023 #include "llvm/Target/TargetMachine.h" 00024 #include "llvm/Support/CommandLine.h" 00025 #include "llvm/Support/Debug.h" 00026 #include "llvm/ADT/DenseMap.h" 00027 #include "llvm/ADT/Statistic.h" 00028 #include <algorithm> 00029 using namespace llvm; 00030 00031 namespace { 00032 Statistic<> NumStores("ra-local", "Number of stores added"); 00033 Statistic<> NumLoads ("ra-local", "Number of loads added"); 00034 Statistic<> NumFolded("ra-local", "Number of loads/stores folded into " 00035 "instructions"); 00036 class RA : public MachineFunctionPass { 00037 const TargetMachine *TM; 00038 MachineFunction *MF; 00039 const MRegisterInfo *RegInfo; 00040 LiveVariables *LV; 00041 00042 // StackSlotForVirtReg - Maps virtual regs to the frame index where these 00043 // values are spilled. 00044 std::map<unsigned, int> StackSlotForVirtReg; 00045 00046 // Virt2PhysRegMap - This map contains entries for each virtual register 00047 // that is currently available in a physical register. 00048 DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap; 00049 00050 unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { 00051 return Virt2PhysRegMap[VirtReg]; 00052 } 00053 00054 // PhysRegsUsed - This array is effectively a map, containing entries for 00055 // each physical register that currently has a value (ie, it is in 00056 // Virt2PhysRegMap). The value mapped to is the virtual register 00057 // corresponding to the physical register (the inverse of the 00058 // Virt2PhysRegMap), or 0. The value is set to 0 if this register is pinned 00059 // because it is used by a future instruction. If the entry for a physical 00060 // register is -1, then the physical register is "not in the map". 00061 // 00062 std::vector<int> PhysRegsUsed; 00063 00064 // PhysRegsUseOrder - This contains a list of the physical registers that 00065 // currently have a virtual register value in them. This list provides an 00066 // ordering of registers, imposing a reallocation order. This list is only 00067 // used if all registers are allocated and we have to spill one, in which 00068 // case we spill the least recently used register. Entries at the front of 00069 // the list are the least recently used registers, entries at the back are 00070 // the most recently used. 00071 // 00072 std::vector<unsigned> PhysRegsUseOrder; 00073 00074 // VirtRegModified - This bitset contains information about which virtual 00075 // registers need to be spilled back to memory when their registers are 00076 // scavenged. If a virtual register has simply been rematerialized, there 00077 // is no reason to spill it to memory when we need the register back. 00078 // 00079 std::vector<bool> VirtRegModified; 00080 00081 void markVirtRegModified(unsigned Reg, bool Val = true) { 00082 assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); 00083 Reg -= MRegisterInfo::FirstVirtualRegister; 00084 if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); 00085 VirtRegModified[Reg] = Val; 00086 } 00087 00088 bool isVirtRegModified(unsigned Reg) const { 00089 assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); 00090 assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() 00091 && "Illegal virtual register!"); 00092 return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister]; 00093 } 00094 00095 void MarkPhysRegRecentlyUsed(unsigned Reg) { 00096 if(PhysRegsUseOrder.empty() || 00097 PhysRegsUseOrder.back() == Reg) return; // Already most recently used 00098 00099 for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) 00100 if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { 00101 unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle 00102 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); 00103 // Add it to the end of the list 00104 PhysRegsUseOrder.push_back(RegMatch); 00105 if (RegMatch == Reg) 00106 return; // Found an exact match, exit early 00107 } 00108 } 00109 00110 public: 00111 virtual const char *getPassName() const { 00112 return "Local Register Allocator"; 00113 } 00114 00115 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00116 AU.addRequired<LiveVariables>(); 00117 AU.addRequiredID(PHIEliminationID); 00118 AU.addRequiredID(TwoAddressInstructionPassID); 00119 MachineFunctionPass::getAnalysisUsage(AU); 00120 } 00121 00122 private: 00123 /// runOnMachineFunction - Register allocate the whole function 00124 bool runOnMachineFunction(MachineFunction &Fn); 00125 00126 /// AllocateBasicBlock - Register allocate the specified basic block. 00127 void AllocateBasicBlock(MachineBasicBlock &MBB); 00128 00129 00130 /// areRegsEqual - This method returns true if the specified registers are 00131 /// related to each other. To do this, it checks to see if they are equal 00132 /// or if the first register is in the alias set of the second register. 00133 /// 00134 bool areRegsEqual(unsigned R1, unsigned R2) const { 00135 if (R1 == R2) return true; 00136 for (const unsigned *AliasSet = RegInfo->getAliasSet(R2); 00137 *AliasSet; ++AliasSet) { 00138 if (*AliasSet == R1) return true; 00139 } 00140 return false; 00141 } 00142 00143 /// getStackSpaceFor - This returns the frame index of the specified virtual 00144 /// register on the stack, allocating space if necessary. 00145 int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 00146 00147 /// removePhysReg - This method marks the specified physical register as no 00148 /// longer being in use. 00149 /// 00150 void removePhysReg(unsigned PhysReg); 00151 00152 /// spillVirtReg - This method spills the value specified by PhysReg into 00153 /// the virtual register slot specified by VirtReg. It then updates the RA 00154 /// data structures to indicate the fact that PhysReg is now available. 00155 /// 00156 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 00157 unsigned VirtReg, unsigned PhysReg); 00158 00159 /// spillPhysReg - This method spills the specified physical register into 00160 /// the virtual register slot associated with it. If OnlyVirtRegs is set to 00161 /// true, then the request is ignored if the physical register does not 00162 /// contain a virtual register. 00163 /// 00164 void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 00165 unsigned PhysReg, bool OnlyVirtRegs = false); 00166 00167 /// assignVirtToPhysReg - This method updates local state so that we know 00168 /// that PhysReg is the proper container for VirtReg now. The physical 00169 /// register must not be used for anything else when this is called. 00170 /// 00171 void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); 00172 00173 /// liberatePhysReg - Make sure the specified physical register is available 00174 /// for use. If there is currently a value in it, it is either moved out of 00175 /// the way or spilled to memory. 00176 /// 00177 void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, 00178 unsigned PhysReg); 00179 00180 /// isPhysRegAvailable - Return true if the specified physical register is 00181 /// free and available for use. This also includes checking to see if 00182 /// aliased registers are all free... 00183 /// 00184 bool isPhysRegAvailable(unsigned PhysReg) const; 00185 00186 /// getFreeReg - Look to see if there is a free register available in the 00187 /// specified register class. If not, return 0. 00188 /// 00189 unsigned getFreeReg(const TargetRegisterClass *RC); 00190 00191 /// getReg - Find a physical register to hold the specified virtual 00192 /// register. If all compatible physical registers are used, this method 00193 /// spills the last used virtual register to the stack, and uses that 00194 /// register. 00195 /// 00196 unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI, 00197 unsigned VirtReg); 00198 00199 /// reloadVirtReg - This method transforms the specified specified virtual 00200 /// register use to refer to a physical register. This method may do this 00201 /// in one of several ways: if the register is available in a physical 00202 /// register already, it uses that physical register. If the value is not 00203 /// in a physical register, and if there are physical registers available, 00204 /// it loads it into a register. If register pressure is high, and it is 00205 /// possible, it tries to fold the load of the virtual register into the 00206 /// instruction itself. It avoids doing this if register pressure is low to 00207 /// improve the chance that subsequent instructions can use the reloaded 00208 /// value. This method returns the modified instruction. 00209 /// 00210 MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 00211 unsigned OpNum); 00212 00213 00214 void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, 00215 unsigned PhysReg); 00216 }; 00217 } 00218 00219 /// getStackSpaceFor - This allocates space for the specified virtual register 00220 /// to be held on the stack. 00221 int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 00222 // Find the location Reg would belong... 00223 std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg); 00224 00225 if (I != StackSlotForVirtReg.end() && I->first == VirtReg) 00226 return I->second; // Already has space allocated? 00227 00228 // Allocate a new stack object for this spill location... 00229 int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), 00230 RC->getAlignment()); 00231 00232 // Assign the slot... 00233 StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); 00234 return FrameIdx; 00235 } 00236 00237 00238 /// removePhysReg - This method marks the specified physical register as no 00239 /// longer being in use. 00240 /// 00241 void RA::removePhysReg(unsigned PhysReg) { 00242 PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used 00243 00244 std::vector<unsigned>::iterator It = 00245 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); 00246 if (It != PhysRegsUseOrder.end()) 00247 PhysRegsUseOrder.erase(It); 00248 } 00249 00250 00251 /// spillVirtReg - This method spills the value specified by PhysReg into the 00252 /// virtual register slot specified by VirtReg. It then updates the RA data 00253 /// structures to indicate the fact that PhysReg is now available. 00254 /// 00255 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, 00256 unsigned VirtReg, unsigned PhysReg) { 00257 assert(VirtReg && "Spilling a physical register is illegal!" 00258 " Must not have appropriate kill for the register or use exists beyond" 00259 " the intended one."); 00260 DEBUG(std::cerr << " Spilling register " << RegInfo->getName(PhysReg); 00261 std::cerr << " containing %reg" << VirtReg; 00262 if (!isVirtRegModified(VirtReg)) 00263 std::cerr << " which has not been modified, so no store necessary!"); 00264 00265 // Otherwise, there is a virtual register corresponding to this physical 00266 // register. We only need to spill it into its stack slot if it has been 00267 // modified. 00268 if (isVirtRegModified(VirtReg)) { 00269 const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); 00270 int FrameIndex = getStackSpaceFor(VirtReg, RC); 00271 DEBUG(std::cerr << " to stack slot #" << FrameIndex); 00272 RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex); 00273 ++NumStores; // Update statistics 00274 } 00275 00276 getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available 00277 00278 DEBUG(std::cerr << "\n"); 00279 removePhysReg(PhysReg); 00280 } 00281 00282 00283 /// spillPhysReg - This method spills the specified physical register into the 00284 /// virtual register slot associated with it. If OnlyVirtRegs is set to true, 00285 /// then the request is ignored if the physical register does not contain a 00286 /// virtual register. 00287 /// 00288 void RA::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 00289 unsigned PhysReg, bool OnlyVirtRegs) { 00290 if (PhysRegsUsed[PhysReg] != -1) { // Only spill it if it's used! 00291 if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs) 00292 spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg); 00293 } else { 00294 // If the selected register aliases any other registers, we must make 00295 // sure that one of the aliases isn't alive... 00296 for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); 00297 *AliasSet; ++AliasSet) 00298 if (PhysRegsUsed[*AliasSet] != -1) // Spill aliased register... 00299 if (PhysRegsUsed[*AliasSet] || !OnlyVirtRegs) 00300 spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); 00301 } 00302 } 00303 00304 00305 /// assignVirtToPhysReg - This method updates local state so that we know 00306 /// that PhysReg is the proper container for VirtReg now. The physical 00307 /// register must not be used for anything else when this is called. 00308 /// 00309 void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 00310 assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!"); 00311 // Update information to note the fact that this register was just used, and 00312 // it holds VirtReg. 00313 PhysRegsUsed[PhysReg] = VirtReg; 00314 getVirt2PhysRegMapSlot(VirtReg) = PhysReg; 00315 PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg 00316 } 00317 00318 00319 /// isPhysRegAvailable - Return true if the specified physical register is free 00320 /// and available for use. This also includes checking to see if aliased 00321 /// registers are all free... 00322 /// 00323 bool RA::isPhysRegAvailable(unsigned PhysReg) const { 00324 if (PhysRegsUsed[PhysReg] != -1) return false; 00325 00326 // If the selected register aliases any other allocated registers, it is 00327 // not free! 00328 for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); 00329 *AliasSet; ++AliasSet) 00330 if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? 00331 return false; // Can't use this reg then. 00332 return true; 00333 } 00334 00335 00336 /// getFreeReg - Look to see if there is a free register available in the 00337 /// specified register class. If not, return 0. 00338 /// 00339 unsigned RA::getFreeReg(const TargetRegisterClass *RC) { 00340 // Get iterators defining the range of registers that are valid to allocate in 00341 // this class, which also specifies the preferred allocation order. 00342 TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); 00343 TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); 00344 00345 for (; RI != RE; ++RI) 00346 if (isPhysRegAvailable(*RI)) { // Is reg unused? 00347 assert(*RI != 0 && "Cannot use register!"); 00348 return *RI; // Found an unused register! 00349 } 00350 return 0; 00351 } 00352 00353 00354 /// liberatePhysReg - Make sure the specified physical register is available for 00355 /// use. If there is currently a value in it, it is either moved out of the way 00356 /// or spilled to memory. 00357 /// 00358 void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, 00359 unsigned PhysReg) { 00360 spillPhysReg(MBB, I, PhysReg); 00361 } 00362 00363 00364 /// getReg - Find a physical register to hold the specified virtual 00365 /// register. If all compatible physical registers are used, this method spills 00366 /// the last used virtual register to the stack, and uses that register. 00367 /// 00368 unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, 00369 unsigned VirtReg) { 00370 const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); 00371 00372 // First check to see if we have a free register of the requested type... 00373 unsigned PhysReg = getFreeReg(RC); 00374 00375 // If we didn't find an unused register, scavenge one now! 00376 if (PhysReg == 0) { 00377 assert(!PhysRegsUseOrder.empty() && "No allocated registers??"); 00378 00379 // Loop over all of the preallocated registers from the least recently used 00380 // to the most recently used. When we find one that is capable of holding 00381 // our register, use it. 00382 for (unsigned i = 0; PhysReg == 0; ++i) { 00383 assert(i != PhysRegsUseOrder.size() && 00384 "Couldn't find a register of the appropriate class!"); 00385 00386 unsigned R = PhysRegsUseOrder[i]; 00387 00388 // We can only use this register if it holds a virtual register (ie, it 00389 // can be spilled). Do not use it if it is an explicitly allocated 00390 // physical register! 00391 assert(PhysRegsUsed[R] != -1 && 00392 "PhysReg in PhysRegsUseOrder, but is not allocated?"); 00393 if (PhysRegsUsed[R]) { 00394 // If the current register is compatible, use it. 00395 if (RC->contains(R)) { 00396 PhysReg = R; 00397 break; 00398 } else { 00399 // If one of the registers aliased to the current register is 00400 // compatible, use it. 00401 for (const unsigned *AliasSet = RegInfo->getAliasSet(R); 00402 *AliasSet; ++AliasSet) { 00403 if (RC->contains(*AliasSet)) { 00404 PhysReg = *AliasSet; // Take an aliased register 00405 break; 00406 } 00407 } 00408 } 00409 } 00410 } 00411 00412 assert(PhysReg && "Physical register not assigned!?!?"); 00413 00414 // At this point PhysRegsUseOrder[i] is the least recently used register of 00415 // compatible register class. Spill it to memory and reap its remains. 00416 spillPhysReg(MBB, I, PhysReg); 00417 } 00418 00419 // Now that we know which register we need to assign this to, do it now! 00420 assignVirtToPhysReg(VirtReg, PhysReg); 00421 return PhysReg; 00422 } 00423 00424 00425 /// reloadVirtReg - This method transforms the specified specified virtual 00426 /// register use to refer to a physical register. This method may do this in 00427 /// one of several ways: if the register is available in a physical register 00428 /// already, it uses that physical register. If the value is not in a physical 00429 /// register, and if there are physical registers available, it loads it into a 00430 /// register. If register pressure is high, and it is possible, it tries to 00431 /// fold the load of the virtual register into the instruction itself. It 00432 /// avoids doing this if register pressure is low to improve the chance that 00433 /// subsequent instructions can use the reloaded value. This method returns the 00434 /// modified instruction. 00435 /// 00436 MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 00437 unsigned OpNum) { 00438 unsigned VirtReg = MI->getOperand(OpNum).getReg(); 00439 00440 // If the virtual register is already available, just update the instruction 00441 // and return. 00442 if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { 00443 MarkPhysRegRecentlyUsed(PR); // Already have this value available! 00444 MI->SetMachineOperandReg(OpNum, PR); // Assign the input register 00445 return MI; 00446 } 00447 00448 // Otherwise, we need to fold it into the current instruction, or reload it. 00449 // If we have registers available to hold the value, use them. 00450 const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); 00451 unsigned PhysReg = getFreeReg(RC); 00452 int FrameIndex = getStackSpaceFor(VirtReg, RC); 00453 00454 if (PhysReg) { // Register is available, allocate it! 00455 assignVirtToPhysReg(VirtReg, PhysReg); 00456 } else { // No registers available. 00457 // If we can fold this spill into this instruction, do so now. 00458 if (MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)){ 00459 ++NumFolded; 00460 // Since we changed the address of MI, make sure to update live variables 00461 // to know that the new instruction has the properties of the old one. 00462 LV->instructionChanged(MI, FMI); 00463 return MBB.insert(MBB.erase(MI), FMI); 00464 } 00465 00466 // It looks like we can't fold this virtual register load into this 00467 // instruction. Force some poor hapless value out of the register file to 00468 // make room for the new register, and reload it. 00469 PhysReg = getReg(MBB, MI, VirtReg); 00470 } 00471 00472 markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded 00473 00474 DEBUG(std::cerr << " Reloading %reg" << VirtReg << " into " 00475 << RegInfo->getName(PhysReg) << "\n"); 00476 00477 // Add move instruction(s) 00478 RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex); 00479 ++NumLoads; // Update statistics 00480 00481 MI->SetMachineOperandReg(OpNum, PhysReg); // Assign the input register 00482 return MI; 00483 } 00484 00485 00486 00487 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { 00488 // loop over each instruction 00489 MachineBasicBlock::iterator MI = MBB.begin(); 00490 for (; MI != MBB.end(); ++MI) { 00491 const TargetInstrDescriptor &TID = TM->getInstrInfo()->get(MI->getOpcode()); 00492 DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI; 00493 std::cerr << " Regs have values: "; 00494 for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) 00495 if (PhysRegsUsed[i] != -1) 00496 std::cerr << "[" << RegInfo->getName(i) 00497 << ",%reg" << PhysRegsUsed[i] << "] "; 00498 std::cerr << "\n"); 00499 00500 // Loop over the implicit uses, making sure that they are at the head of the 00501 // use order list, so they don't get reallocated. 00502 for (const unsigned *ImplicitUses = TID.ImplicitUses; 00503 *ImplicitUses; ++ImplicitUses) 00504 MarkPhysRegRecentlyUsed(*ImplicitUses); 00505 00506 // Get the used operands into registers. This has the potential to spill 00507 // incoming values if we are out of registers. Note that we completely 00508 // ignore physical register uses here. We assume that if an explicit 00509 // physical register is referenced by the instruction, that it is guaranteed 00510 // to be live-in, or the input is badly hosed. 00511 // 00512 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00513 MachineOperand& MO = MI->getOperand(i); 00514 // here we are looking for only used operands (never def&use) 00515 if (!MO.isDef() && MO.isRegister() && MO.getReg() && 00516 MRegisterInfo::isVirtualRegister(MO.getReg())) 00517 MI = reloadVirtReg(MBB, MI, i); 00518 } 00519 00520 // If this instruction is the last user of anything in registers, kill the 00521 // value, freeing the register being used, so it doesn't need to be 00522 // spilled to memory. 00523 // 00524 for (LiveVariables::killed_iterator KI = LV->killed_begin(MI), 00525 KE = LV->killed_end(MI); KI != KE; ++KI) { 00526 unsigned VirtReg = KI->second; 00527 unsigned PhysReg = VirtReg; 00528 if (MRegisterInfo::isVirtualRegister(VirtReg)) { 00529 // If the virtual register was never materialized into a register, it 00530 // might not be in the map, but it won't hurt to zero it out anyway. 00531 unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); 00532 PhysReg = PhysRegSlot; 00533 PhysRegSlot = 0; 00534 } 00535 00536 if (PhysReg) { 00537 DEBUG(std::cerr << " Last use of " << RegInfo->getName(PhysReg) 00538 << "[%reg" << VirtReg <<"], removing it from live set\n"); 00539 removePhysReg(PhysReg); 00540 } 00541 } 00542 00543 // Loop over all of the operands of the instruction, spilling registers that 00544 // are defined, and marking explicit destinations in the PhysRegsUsed map. 00545 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00546 MachineOperand& MO = MI->getOperand(i); 00547 if (MO.isDef() && MO.isRegister() && MO.getReg() && 00548 MRegisterInfo::isPhysicalRegister(MO.getReg())) { 00549 unsigned Reg = MO.getReg(); 00550 spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in the reg 00551 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00552 PhysRegsUseOrder.push_back(Reg); 00553 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 00554 *AliasSet; ++AliasSet) { 00555 PhysRegsUseOrder.push_back(*AliasSet); 00556 PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now 00557 } 00558 } 00559 } 00560 00561 // Loop over the implicit defs, spilling them as well. 00562 for (const unsigned *ImplicitDefs = TID.ImplicitDefs; 00563 *ImplicitDefs; ++ImplicitDefs) { 00564 unsigned Reg = *ImplicitDefs; 00565 spillPhysReg(MBB, MI, Reg, true); 00566 PhysRegsUseOrder.push_back(Reg); 00567 PhysRegsUsed[Reg] = 0; // It is free and reserved now 00568 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 00569 *AliasSet; ++AliasSet) { 00570 PhysRegsUseOrder.push_back(*AliasSet); 00571 PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now 00572 } 00573 } 00574 00575 // Okay, we have allocated all of the source operands and spilled any values 00576 // that would be destroyed by defs of this instruction. Loop over the 00577 // implicit defs and assign them to a register, spilling incoming values if 00578 // we need to scavenge a register. 00579 // 00580 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00581 MachineOperand& MO = MI->getOperand(i); 00582 if (MO.isDef() && MO.isRegister() && MO.getReg() && 00583 MRegisterInfo::isVirtualRegister(MO.getReg())) { 00584 unsigned DestVirtReg = MO.getReg(); 00585 unsigned DestPhysReg; 00586 00587 // If DestVirtReg already has a value, use it. 00588 if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) 00589 DestPhysReg = getReg(MBB, MI, DestVirtReg); 00590 markVirtRegModified(DestVirtReg); 00591 MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register 00592 } 00593 } 00594 00595 // If this instruction defines any registers that are immediately dead, 00596 // kill them now. 00597 // 00598 for (LiveVariables::killed_iterator KI = LV->dead_begin(MI), 00599 KE = LV->dead_end(MI); KI != KE; ++KI) { 00600 unsigned VirtReg = KI->second; 00601 unsigned PhysReg = VirtReg; 00602 if (MRegisterInfo::isVirtualRegister(VirtReg)) { 00603 unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); 00604 PhysReg = PhysRegSlot; 00605 assert(PhysReg != 0); 00606 PhysRegSlot = 0; 00607 } 00608 00609 if (PhysReg) { 00610 DEBUG(std::cerr << " Register " << RegInfo->getName(PhysReg) 00611 << " [%reg" << VirtReg 00612 << "] is never used, removing it frame live list\n"); 00613 removePhysReg(PhysReg); 00614 } 00615 } 00616 } 00617 00618 MI = MBB.getFirstTerminator(); 00619 00620 // Spill all physical registers holding virtual registers now. 00621 for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) 00622 if (PhysRegsUsed[i] != -1) 00623 if (unsigned VirtReg = PhysRegsUsed[i]) 00624 spillVirtReg(MBB, MI, VirtReg, i); 00625 else 00626 removePhysReg(i); 00627 00628 #ifndef NDEBUG 00629 bool AllOk = true; 00630 for (unsigned i = MRegisterInfo::FirstVirtualRegister, 00631 e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i) 00632 if (unsigned PR = Virt2PhysRegMap[i]) { 00633 std::cerr << "Register still mapped: " << i << " -> " << PR << "\n"; 00634 AllOk = false; 00635 } 00636 assert(AllOk && "Virtual registers still in phys regs?"); 00637 #endif 00638 00639 // Clear any physical register which appear live at the end of the basic 00640 // block, but which do not hold any virtual registers. e.g., the stack 00641 // pointer. 00642 PhysRegsUseOrder.clear(); 00643 } 00644 00645 00646 /// runOnMachineFunction - Register allocate the whole function 00647 /// 00648 bool RA::runOnMachineFunction(MachineFunction &Fn) { 00649 DEBUG(std::cerr << "Machine Function " << "\n"); 00650 MF = &Fn; 00651 TM = &Fn.getTarget(); 00652 RegInfo = TM->getRegisterInfo(); 00653 LV = &getAnalysis<LiveVariables>(); 00654 00655 PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); 00656 00657 // initialize the virtual->physical register map to have a 'null' 00658 // mapping for all virtual registers 00659 Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); 00660 00661 // Loop over all of the basic blocks, eliminating virtual register references 00662 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 00663 MBB != MBBe; ++MBB) 00664 AllocateBasicBlock(*MBB); 00665 00666 StackSlotForVirtReg.clear(); 00667 PhysRegsUsed.clear(); 00668 VirtRegModified.clear(); 00669 Virt2PhysRegMap.clear(); 00670 return true; 00671 } 00672 00673 FunctionPass *llvm::createLocalRegisterAllocator() { 00674 return new RA(); 00675 }