lib/CodeGen/RegAllocLocal.cpp

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