lib/CodeGen/RegAllocLocal.cpp

   1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This register allocator allocates registers to a basic block at a time,
  11 // attempting to keep values in registers and reusing registers as appropriate.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "regalloc"
  16 #include "llvm/CodeGen/Passes.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/SSARegMap.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/LiveVariables.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "Support/CommandLine.h"
  25 #include "Support/Debug.h"
  26 #include "Support/Statistic.h"
  27 #include <iostream>
  28 using namespace llvm;
  29
  30 namespace {
  31   Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
  32   Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
  33   cl::opt<bool> DisableKill("disable-kill", cl::Hidden,
  34                             cl::desc("Disable register kill in local-ra"));
  35
  36   class RA : public MachineFunctionPass {
  37     const TargetMachine *TM;
  38     MachineFunction *MF;
  39     const MRegisterInfo *RegInfo;
  40     LiveVariables *LV;
  41
  42     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  43     // values are spilled.
  44     std::map<unsigned, int> StackSlotForVirtReg;
  45
  46     // Virt2PhysRegMap - This map contains entries for each virtual register
  47     // that is currently available in a physical register.
  48     //
  49     std::map<unsigned, unsigned> Virt2PhysRegMap;
  50
  51     // PhysRegsUsed - This map contains entries for each physical register that
  52     // currently has a value (ie, it is in Virt2PhysRegMap).  The value mapped
  53     // to is the virtual register corresponding to the physical register (the
  54     // inverse of the Virt2PhysRegMap), or 0.  The value is set to 0 if this
  55     // register is pinned because it is used by a future instruction.
  56     //
  57     std::map<unsigned, unsigned> PhysRegsUsed;
  58
  59     // PhysRegsUseOrder - This contains a list of the physical registers that
  60     // currently have a virtual register value in them.  This list provides an
  61     // ordering of registers, imposing a reallocation order.  This list is only
  62     // used if all registers are allocated and we have to spill one, in which
  63     // case we spill the least recently used register.  Entries at the front of
  64     // the list are the least recently used registers, entries at the back are
  65     // the most recently used.
  66     //
  67     std::vector<unsigned> PhysRegsUseOrder;
  68
  69     // VirtRegModified - This bitset contains information about which virtual
  70     // registers need to be spilled back to memory when their registers are
  71     // scavenged.  If a virtual register has simply been rematerialized, there
  72     // is no reason to spill it to memory when we need the register back.
  73     //
  74     std::vector<bool> VirtRegModified;
  75
  76     void markVirtRegModified(unsigned Reg, bool Val = true) {
  77       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  78       Reg -= MRegisterInfo::FirstVirtualRegister;
  79       if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1);
  80       VirtRegModified[Reg] = Val;
  81     }
  82
  83     bool isVirtRegModified(unsigned Reg) const {
  84       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  85       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
  86              && "Illegal virtual register!");
  87       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
  88     }
  89
  90     void MarkPhysRegRecentlyUsed(unsigned Reg) {
  91       assert(!PhysRegsUseOrder.empty() && "No registers used!");
  92       if (PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
  93
  94       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
  95         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
  96           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
  97           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
  98           // Add it to the end of the list
  99           PhysRegsUseOrder.push_back(RegMatch);
 100           if (RegMatch == Reg)
 101             return;    // Found an exact match, exit early
 102         }
 103     }
 104
 105   public:
 106     virtual const char *getPassName() const {
 107       return "Local Register Allocator";
 108     }
 109
 110     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 111       if (!DisableKill)
 112         AU.addRequired<LiveVariables>();
 113       AU.addRequiredID(PHIEliminationID);
 114       AU.addRequiredID(TwoAddressInstructionPassID);
 115       MachineFunctionPass::getAnalysisUsage(AU);
 116     }
 117
 118   private:
 119     /// runOnMachineFunction - Register allocate the whole function
 120     bool runOnMachineFunction(MachineFunction &Fn);
 121
 122     /// AllocateBasicBlock - Register allocate the specified basic block.
 123     void AllocateBasicBlock(MachineBasicBlock &MBB);
 124
 125
 126     /// areRegsEqual - This method returns true if the specified registers are
 127     /// related to each other.  To do this, it checks to see if they are equal
 128     /// or if the first register is in the alias set of the second register.
 129     ///
 130     bool areRegsEqual(unsigned R1, unsigned R2) const {
 131       if (R1 == R2) return true;
 132       for (const unsigned *AliasSet = RegInfo->getAliasSet(R2);
 133            *AliasSet; ++AliasSet) {
 134         if (*AliasSet == R1) return true;
 135       }
 136       return false;
 137     }
 138
 139     /// getStackSpaceFor - This returns the frame index of the specified virtual
 140     /// register on the stack, allocating space if necessary.
 141     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 142
 143     /// removePhysReg - This method marks the specified physical register as no
 144     /// longer being in use.
 145     ///
 146     void removePhysReg(unsigned PhysReg);
 147
 148     /// spillVirtReg - This method spills the value specified by PhysReg into
 149     /// the virtual register slot specified by VirtReg.  It then updates the RA
 150     /// data structures to indicate the fact that PhysReg is now available.
 151     ///
 152     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 153                       unsigned VirtReg, unsigned PhysReg);
 154
 155     /// spillPhysReg - This method spills the specified physical register into
 156     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 157     /// true, then the request is ignored if the physical register does not
 158     /// contain a virtual register.
 159     ///
 160     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 161                       unsigned PhysReg, bool OnlyVirtRegs = false);
 162
 163     /// assignVirtToPhysReg - This method updates local state so that we know
 164     /// that PhysReg is the proper container for VirtReg now.  The physical
 165     /// register must not be used for anything else when this is called.
 166     ///
 167     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 168
 169     /// liberatePhysReg - Make sure the specified physical register is available
 170     /// for use.  If there is currently a value in it, it is either moved out of
 171     /// the way or spilled to memory.
 172     ///
 173     void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 174                          unsigned PhysReg);
 175
 176     /// isPhysRegAvailable - Return true if the specified physical register is
 177     /// free and available for use.  This also includes checking to see if
 178     /// aliased registers are all free...
 179     ///
 180     bool isPhysRegAvailable(unsigned PhysReg) const;
 181
 182     /// getFreeReg - Look to see if there is a free register available in the
 183     /// specified register class.  If not, return 0.
 184     ///
 185     unsigned getFreeReg(const TargetRegisterClass *RC);
 186
 187     /// getReg - Find a physical register to hold the specified virtual
 188     /// register.  If all compatible physical registers are used, this method
 189     /// spills the last used virtual register to the stack, and uses that
 190     /// register.
 191     ///
 192     unsigned getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 193                     unsigned VirtReg);
 194
 195     /// reloadVirtReg - This method loads the specified virtual register into a
 196     /// physical register, returning the physical register chosen.  This updates
 197     /// the regalloc data structures to reflect the fact that the virtual reg is
 198     /// now alive in a physical register, and the previous one isn't.
 199     ///
 200     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 201                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 202
 203     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 204                        unsigned PhysReg);
 205   };
 206 }
 207
 208 /// getStackSpaceFor - This allocates space for the specified virtual register
 209 /// to be held on the stack.
 210 int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 211   // Find the location Reg would belong...
 212   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
 213
 214   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
 215     return I->second;          // Already has space allocated?
 216
 217   // Allocate a new stack object for this spill location...
 218   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
 219
 220   // Assign the slot...
 221   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
 222   return FrameIdx;
 223 }
 224
 225
 226 /// removePhysReg - This method marks the specified physical register as no
 227 /// longer being in use.
 228 ///
 229 void RA::removePhysReg(unsigned PhysReg) {
 230   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
 231
 232   std::vector<unsigned>::iterator It =
 233     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 234   if (It != PhysRegsUseOrder.end())
 235     PhysRegsUseOrder.erase(It);
 236 }
 237
 238
 239 /// spillVirtReg - This method spills the value specified by PhysReg into the
 240 /// virtual register slot specified by VirtReg.  It then updates the RA data
 241 /// structures to indicate the fact that PhysReg is now available.
 242 ///
 243 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 244                       unsigned VirtReg, unsigned PhysReg) {
 245   if (!VirtReg && DisableKill) return;
 246   assert(VirtReg && "Spilling a physical register is illegal!"
 247          " Must not have appropriate kill for the register or use exists beyond"
 248          " the intended one.");
 249   DEBUG(std::cerr << "  Spilling register " << RegInfo->getName(PhysReg);
 250         std::cerr << " containing %reg" << VirtReg;
 251         if (!isVirtRegModified(VirtReg))
 252         std::cerr << " which has not been modified, so no store necessary!");
 253
 254   // Otherwise, there is a virtual register corresponding to this physical
 255   // register.  We only need to spill it into its stack slot if it has been
 256   // modified.
 257   if (isVirtRegModified(VirtReg)) {
 258     const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 259     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 260     DEBUG(std::cerr << " to stack slot #" << FrameIndex);
 261     RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC);
 262     ++NumSpilled;   // Update statistics
 263   }
 264   Virt2PhysRegMap.erase(VirtReg);   // VirtReg no longer available
 265
 266   DEBUG(std::cerr << "\n");
 267   removePhysReg(PhysReg);
 268 }
 269
 270
 271 /// spillPhysReg - This method spills the specified physical register into the
 272 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 273 /// then the request is ignored if the physical register does not contain a
 274 /// virtual register.
 275 ///
 276 void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 277                       unsigned PhysReg, bool OnlyVirtRegs) {
 278   std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
 279   if (PI != PhysRegsUsed.end()) {             // Only spill it if it's used!
 280     if (PI->second || !OnlyVirtRegs)
 281       spillVirtReg(MBB, I, PI->second, PhysReg);
 282   } else {
 283     // If the selected register aliases any other registers, we must make
 284     // sure that one of the aliases isn't alive...
 285     for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 286          *AliasSet; ++AliasSet) {
 287       PI = PhysRegsUsed.find(*AliasSet);
 288       if (PI != PhysRegsUsed.end())     // Spill aliased register...
 289         if (PI->second || !OnlyVirtRegs)
 290           spillVirtReg(MBB, I, PI->second, *AliasSet);
 291     }
 292   }
 293 }
 294
 295
 296 /// assignVirtToPhysReg - This method updates local state so that we know
 297 /// that PhysReg is the proper container for VirtReg now.  The physical
 298 /// register must not be used for anything else when this is called.
 299 ///
 300 void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 301   assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
 302          "Phys reg already assigned!");
 303   // Update information to note the fact that this register was just used, and
 304   // it holds VirtReg.
 305   PhysRegsUsed[PhysReg] = VirtReg;
 306   Virt2PhysRegMap[VirtReg] = PhysReg;
 307   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 308 }
 309
 310
 311 /// isPhysRegAvailable - Return true if the specified physical register is free
 312 /// and available for use.  This also includes checking to see if aliased
 313 /// registers are all free...
 314 ///
 315 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
 316   if (PhysRegsUsed.count(PhysReg)) return false;
 317
 318   // If the selected register aliases any other allocated registers, it is
 319   // not free!
 320   for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 321        *AliasSet; ++AliasSet)
 322     if (PhysRegsUsed.count(*AliasSet)) // Aliased register in use?
 323       return false;                    // Can't use this reg then.
 324   return true;
 325 }
 326
 327
 328 /// getFreeReg - Look to see if there is a free register available in the
 329 /// specified register class.  If not, return 0.
 330 ///
 331 unsigned RA::getFreeReg(const TargetRegisterClass *RC) {
 332   // Get iterators defining the range of registers that are valid to allocate in
 333   // this class, which also specifies the preferred allocation order.
 334   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 335   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 336
 337   for (; RI != RE; ++RI)
 338     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 339       assert(*RI != 0 && "Cannot use register!");
 340       return *RI; // Found an unused register!
 341     }
 342   return 0;
 343 }
 344
 345
 346 /// liberatePhysReg - Make sure the specified physical register is available for
 347 /// use.  If there is currently a value in it, it is either moved out of the way
 348 /// or spilled to memory.
 349 ///
 350 void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 351                          unsigned PhysReg) {
 352   // FIXME: This code checks to see if a register is available, but it really
 353   // wants to know if a reg is available BEFORE the instruction executes.  If
 354   // called after killed operands are freed, it runs the risk of reallocating a
 355   // used operand...
 356 #if 0
 357   if (isPhysRegAvailable(PhysReg)) return;  // Already available...
 358
 359   // Check to see if the register is directly used, not indirectly used through
 360   // aliases.  If aliased registers are the ones actually used, we cannot be
 361   // sure that we will be able to save the whole thing if we do a reg-reg copy.
 362   std::map<unsigned, unsigned>::iterator PRUI = PhysRegsUsed.find(PhysReg);
 363   if (PRUI != PhysRegsUsed.end()) {
 364     unsigned VirtReg = PRUI->second;   // The virtual register held...
 365
 366     // Check to see if there is a compatible register available.  If so, we can
 367     // move the value into the new register...
 368     //
 369     const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg);
 370     if (unsigned NewReg = getFreeReg(RC)) {
 371       // Emit the code to copy the value...
 372       RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC);
 373
 374       // Update our internal state to indicate that PhysReg is available and Reg
 375       // isn't.
 376       Virt2PhysRegMap.erase(VirtReg);
 377       removePhysReg(PhysReg);  // Free the physreg
 378
 379       // Move reference over to new register...
 380       assignVirtToPhysReg(VirtReg, NewReg);
 381       return;
 382     }
 383   }
 384 #endif
 385   spillPhysReg(MBB, I, PhysReg);
 386 }
 387
 388
 389 /// getReg - Find a physical register to hold the specified virtual
 390 /// register.  If all compatible physical registers are used, this method spills
 391 /// the last used virtual register to the stack, and uses that register.
 392 ///
 393 unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 394                     unsigned VirtReg) {
 395   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 396
 397   // First check to see if we have a free register of the requested type...
 398   unsigned PhysReg = getFreeReg(RC);
 399
 400   // If we didn't find an unused register, scavenge one now!
 401   if (PhysReg == 0) {
 402     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 403
 404     // Loop over all of the preallocated registers from the least recently used
 405     // to the most recently used.  When we find one that is capable of holding
 406     // our register, use it.
 407     for (unsigned i = 0; PhysReg == 0; ++i) {
 408       assert(i != PhysRegsUseOrder.size() &&
 409              "Couldn't find a register of the appropriate class!");
 410
 411       unsigned R = PhysRegsUseOrder[i];
 412
 413       // We can only use this register if it holds a virtual register (ie, it
 414       // can be spilled).  Do not use it if it is an explicitly allocated
 415       // physical register!
 416       assert(PhysRegsUsed.count(R) &&
 417              "PhysReg in PhysRegsUseOrder, but is not allocated?");
 418       if (PhysRegsUsed[R]) {
 419         // If the current register is compatible, use it.
 420         if (RegInfo->getRegClass(R) == RC) {
 421           PhysReg = R;
 422           break;
 423         } else {
 424           // If one of the registers aliased to the current register is
 425           // compatible, use it.
 426           for (const unsigned *AliasSet = RegInfo->getAliasSet(R);
 427                *AliasSet; ++AliasSet) {
 428             if (RegInfo->getRegClass(*AliasSet) == RC) {
 429               PhysReg = *AliasSet;    // Take an aliased register
 430               break;
 431             }
 432           }
 433         }
 434       }
 435     }
 436
 437     assert(PhysReg && "Physical register not assigned!?!?");
 438
 439     // At this point PhysRegsUseOrder[i] is the least recently used register of
 440     // compatible register class.  Spill it to memory and reap its remains.
 441     spillPhysReg(MBB, I, PhysReg);
 442   }
 443
 444   // Now that we know which register we need to assign this to, do it now!
 445   assignVirtToPhysReg(VirtReg, PhysReg);
 446   return PhysReg;
 447 }
 448
 449
 450 /// reloadVirtReg - This method loads the specified virtual register into a
 451 /// physical register, returning the physical register chosen.  This updates the
 452 /// regalloc data structures to reflect the fact that the virtual reg is now
 453 /// alive in a physical register, and the previous one isn't.
 454 ///
 455 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
 456                            MachineBasicBlock::iterator &I,
 457                            unsigned VirtReg) {
 458   std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
 459   if (It != Virt2PhysRegMap.end()) {
 460     MarkPhysRegRecentlyUsed(It->second);
 461     return It->second;               // Already have this value available!
 462   }
 463
 464   unsigned PhysReg = getReg(MBB, I, VirtReg);
 465
 466   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 467   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 468
 469   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 470
 471   DEBUG(std::cerr << "  Reloading %reg" << VirtReg << " into "
 472                   << RegInfo->getName(PhysReg) << "\n");
 473
 474   // Add move instruction(s)
 475   RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIndex, RC);
 476   ++NumReloaded;    // Update statistics
 477   return PhysReg;
 478 }
 479
 480
 481
 482 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 483   // loop over each instruction
 484   MachineBasicBlock::iterator I = MBB.begin();
 485   for (; I != MBB.end(); ++I) {
 486     MachineInstr *MI = *I;
 487     const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode());
 488     DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI;
 489           std::cerr << "  Regs have values: ";
 490           for (std::map<unsigned, unsigned>::const_iterator
 491                  I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I)
 492              std::cerr << "[" << RegInfo->getName(I->first)
 493                        << ",%reg" << I->second << "] ";
 494           std::cerr << "\n");
 495
 496     // Loop over the implicit uses, making sure that they are at the head of the
 497     // use order list, so they don't get reallocated.
 498     for (const unsigned *ImplicitUses = TID.ImplicitUses;
 499          *ImplicitUses; ++ImplicitUses)
 500         MarkPhysRegRecentlyUsed(*ImplicitUses);
 501
 502     // Get the used operands into registers.  This has the potential to spill
 503     // incoming values if we are out of registers.  Note that we completely
 504     // ignore physical register uses here.  We assume that if an explicit
 505     // physical register is referenced by the instruction, that it is guaranteed
 506     // to be live-in, or the input is badly hosed.
 507     //
 508     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 509       if (MI->getOperand(i).isUse() &&
 510           !MI->getOperand(i).isDef() &&
 511           MI->getOperand(i).isVirtualRegister()){
 512         unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
 513         unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
 514         MI->SetMachineOperandReg(i, PhysSrcReg);  // Assign the input register
 515       }
 516
 517     if (!DisableKill) {
 518       // If this instruction is the last user of anything in registers, kill the
 519       // value, freeing the register being used, so it doesn't need to be
 520       // spilled to memory.
 521       //
 522       for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
 523              KE = LV->killed_end(MI); KI != KE; ++KI) {
 524         unsigned VirtReg = KI->second;
 525         unsigned PhysReg = VirtReg;
 526         if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 527           std::map<unsigned, unsigned>::iterator I =
 528             Virt2PhysRegMap.find(VirtReg);
 529           assert(I != Virt2PhysRegMap.end());
 530           PhysReg = I->second;
 531           Virt2PhysRegMap.erase(I);
 532         }
 533
 534         if (PhysReg) {
 535           DEBUG(std::cerr << "  Last use of " << RegInfo->getName(PhysReg)
 536                       << "[%reg" << VirtReg <<"], removing it from live set\n");
 537           removePhysReg(PhysReg);
 538         }
 539       }
 540     }
 541
 542     // Loop over all of the operands of the instruction, spilling registers that
 543     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 544     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 545       if (MI->getOperand(i).isDef() &&
 546           MI->getOperand(i).isPhysicalRegister()) {
 547         unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
 548         spillPhysReg(MBB, I, Reg, true);  // Spill any existing value in the reg
 549         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 550         PhysRegsUseOrder.push_back(Reg);
 551         for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 552              *AliasSet; ++AliasSet) {
 553             PhysRegsUseOrder.push_back(*AliasSet);
 554             PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 555         }
 556       }
 557
 558     // Loop over the implicit defs, spilling them as well.
 559     for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 560          *ImplicitDefs; ++ImplicitDefs) {
 561       unsigned Reg = *ImplicitDefs;
 562       spillPhysReg(MBB, I, Reg);
 563       PhysRegsUseOrder.push_back(Reg);
 564       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 565       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 566            *AliasSet; ++AliasSet) {
 567           PhysRegsUseOrder.push_back(*AliasSet);
 568           PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 569       }
 570     }
 571
 572     // Okay, we have allocated all of the source operands and spilled any values
 573     // that would be destroyed by defs of this instruction.  Loop over the
 574     // implicit defs and assign them to a register, spilling incoming values if
 575     // we need to scavenge a register.
 576     //
 577     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 578       if (MI->getOperand(i).isDef() &&
 579           MI->getOperand(i).isVirtualRegister()) {
 580         unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
 581         unsigned DestPhysReg;
 582
 583         // If DestVirtReg already has a value, use it.
 584         std::map<unsigned, unsigned>::iterator DestI =
 585           Virt2PhysRegMap.find(DestVirtReg);
 586         if (DestI != Virt2PhysRegMap.end()) {
 587           DestPhysReg = DestI->second;
 588         }
 589         else {
 590           DestPhysReg = getReg(MBB, I, DestVirtReg);
 591         }
 592         markVirtRegModified(DestVirtReg);
 593         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 594       }
 595
 596     if (!DisableKill) {
 597       // If this instruction defines any registers that are immediately dead,
 598       // kill them now.
 599       //
 600       for (LiveVariables::killed_iterator KI = LV->dead_begin(MI),
 601              KE = LV->dead_end(MI); KI != KE; ++KI) {
 602         unsigned VirtReg = KI->second;
 603         unsigned PhysReg = VirtReg;
 604         if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 605           std::map<unsigned, unsigned>::iterator I =
 606             Virt2PhysRegMap.find(VirtReg);
 607           assert(I != Virt2PhysRegMap.end());
 608           PhysReg = I->second;
 609           Virt2PhysRegMap.erase(I);
 610         }
 611
 612         if (PhysReg) {
 613           DEBUG(std::cerr << "  Register " << RegInfo->getName(PhysReg)
 614                           << " [%reg" << VirtReg
 615                           << "] is never used, removing it frame live list\n");
 616           removePhysReg(PhysReg);
 617         }
 618       }
 619     }
 620   }
 621
 622   // Rewind the iterator to point to the first flow control instruction...
 623   const TargetInstrInfo &TII = TM->getInstrInfo();
 624   I = MBB.end();
 625   while (I != MBB.begin() && TII.isTerminatorInstr((*(I-1))->getOpcode()))
 626     --I;
 627
 628   // Spill all physical registers holding virtual registers now.
 629   while (!PhysRegsUsed.empty())
 630     if (unsigned VirtReg = PhysRegsUsed.begin()->second)
 631       spillVirtReg(MBB, I, VirtReg, PhysRegsUsed.begin()->first);
 632     else
 633       removePhysReg(PhysRegsUsed.begin()->first);
 634
 635   for (std::map<unsigned, unsigned>::iterator I = Virt2PhysRegMap.begin(),
 636          E = Virt2PhysRegMap.end(); I != E; ++I)
 637     std::cerr << "Register still mapped: " << I->first << " -> "
 638               << I->second << "\n";
 639
 640   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
 641
 642   // Clear any physical register which appear live at the end of the basic
 643   // block, but which do not hold any virtual registers.  e.g., the stack
 644   // pointer.
 645   PhysRegsUseOrder.clear();
 646 }
 647
 648
 649 /// runOnMachineFunction - Register allocate the whole function
 650 ///
 651 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 652   DEBUG(std::cerr << "Machine Function " << "\n");
 653   MF = &Fn;
 654   TM = &Fn.getTarget();
 655   RegInfo = TM->getRegisterInfo();
 656
 657   if (!DisableKill)
 658     LV = &getAnalysis<LiveVariables>();
 659
 660   // Loop over all of the basic blocks, eliminating virtual register references
 661   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 662        MBB != MBBe; ++MBB)
 663     AllocateBasicBlock(*MBB);
 664
 665   StackSlotForVirtReg.clear();
 666   VirtRegModified.clear();
 667   return true;
 668 }
 669
 670 FunctionPass *llvm::createLocalRegisterAllocator() {
 671   return new RA();
 672 }
 673