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