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