LLVM API Documentation

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

RegAllocLocal.cpp

Go to the documentation of this file.
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 }