LLVM API Documentation

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