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