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