lib/CodeGen/RegAllocLocal.cpp

   1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/BasicBlock.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/RegAllocRegistry.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/ADT/DenseMap.h"
  31 #include "llvm/ADT/IndexedMap.h"
  32 #include "llvm/ADT/SmallSet.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 STATISTIC(NumStores, "Number of stores added");
  40 STATISTIC(NumLoads , "Number of loads added");
  41
  42 static RegisterRegAlloc
  43   localRegAlloc("local", "local register allocator",
  44                 createLocalRegisterAllocator);
  45
  46 namespace {
  47   class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
  48   public:
  49     static char ID;
  50     RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {}
  51   private:
  52     const TargetMachine *TM;
  53     MachineFunction *MF;
  54     const TargetRegisterInfo *TRI;
  55     const TargetInstrInfo *TII;
  56
  57     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  58     // values are spilled.
  59     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
  60
  61     // Virt2PhysRegMap - This map contains entries for each virtual register
  62     // that is currently available in a physical register.
  63     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
  64
  65     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
  66       return Virt2PhysRegMap[VirtReg];
  67     }
  68
  69     // PhysRegsUsed - This array is effectively a map, containing entries for
  70     // each physical register that currently has a value (ie, it is in
  71     // Virt2PhysRegMap).  The value mapped to is the virtual register
  72     // corresponding to the physical register (the inverse of the
  73     // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
  74     // because it is used by a future instruction, and to -2 if it is not
  75     // allocatable.  If the entry for a physical register is -1, then the
  76     // physical register is "not in the map".
  77     //
  78     std::vector<int> PhysRegsUsed;
  79
  80     // PhysRegsUseOrder - This contains a list of the physical registers that
  81     // currently have a virtual register value in them.  This list provides an
  82     // ordering of registers, imposing a reallocation order.  This list is only
  83     // used if all registers are allocated and we have to spill one, in which
  84     // case we spill the least recently used register.  Entries at the front of
  85     // the list are the least recently used registers, entries at the back are
  86     // the most recently used.
  87     //
  88     std::vector<unsigned> PhysRegsUseOrder;
  89
  90     // Virt2LastUseMap - This maps each virtual register to its last use
  91     // (MachineInstr*, operand index pair).
  92     IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor>
  93     Virt2LastUseMap;
  94
  95     std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) {
  96       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  97       return Virt2LastUseMap[Reg];
  98     }
  99
 100     // VirtRegModified - This bitset contains information about which virtual
 101     // registers need to be spilled back to memory when their registers are
 102     // scavenged.  If a virtual register has simply been rematerialized, there
 103     // is no reason to spill it to memory when we need the register back.
 104     //
 105     BitVector VirtRegModified;
 106
 107     // UsedInMultipleBlocks - Tracks whether a particular register is used in
 108     // more than one block.
 109     BitVector UsedInMultipleBlocks;
 110
 111     void markVirtRegModified(unsigned Reg, bool Val = true) {
 112       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 113       Reg -= TargetRegisterInfo::FirstVirtualRegister;
 114       if (Val)
 115         VirtRegModified.set(Reg);
 116       else
 117         VirtRegModified.reset(Reg);
 118     }
 119
 120     bool isVirtRegModified(unsigned Reg) const {
 121       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 122       assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
 123              && "Illegal virtual register!");
 124       return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister];
 125     }
 126
 127     void AddToPhysRegsUseOrder(unsigned Reg) {
 128       std::vector<unsigned>::iterator It =
 129         std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg);
 130       if (It != PhysRegsUseOrder.end())
 131         PhysRegsUseOrder.erase(It);
 132       PhysRegsUseOrder.push_back(Reg);
 133     }
 134
 135     void MarkPhysRegRecentlyUsed(unsigned Reg) {
 136       if (PhysRegsUseOrder.empty() ||
 137           PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
 138
 139       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
 140         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
 141           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
 142           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 143           // Add it to the end of the list
 144           PhysRegsUseOrder.push_back(RegMatch);
 145           if (RegMatch == Reg)
 146             return;    // Found an exact match, exit early
 147         }
 148     }
 149
 150   public:
 151     virtual const char *getPassName() const {
 152       return "Local Register Allocator";
 153     }
 154
 155     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 156       AU.addRequiredID(PHIEliminationID);
 157       AU.addRequiredID(TwoAddressInstructionPassID);
 158       MachineFunctionPass::getAnalysisUsage(AU);
 159     }
 160
 161   private:
 162     /// runOnMachineFunction - Register allocate the whole function
 163     bool runOnMachineFunction(MachineFunction &Fn);
 164
 165     /// AllocateBasicBlock - Register allocate the specified basic block.
 166     void AllocateBasicBlock(MachineBasicBlock &MBB);
 167
 168
 169     /// areRegsEqual - This method returns true if the specified registers are
 170     /// related to each other.  To do this, it checks to see if they are equal
 171     /// or if the first register is in the alias set of the second register.
 172     ///
 173     bool areRegsEqual(unsigned R1, unsigned R2) const {
 174       if (R1 == R2) return true;
 175       for (const unsigned *AliasSet = TRI->getAliasSet(R2);
 176            *AliasSet; ++AliasSet) {
 177         if (*AliasSet == R1) return true;
 178       }
 179       return false;
 180     }
 181
 182     /// getStackSpaceFor - This returns the frame index of the specified virtual
 183     /// register on the stack, allocating space if necessary.
 184     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 185
 186     /// removePhysReg - This method marks the specified physical register as no
 187     /// longer being in use.
 188     ///
 189     void removePhysReg(unsigned PhysReg);
 190
 191     /// spillVirtReg - This method spills the value specified by PhysReg into
 192     /// the virtual register slot specified by VirtReg.  It then updates the RA
 193     /// data structures to indicate the fact that PhysReg is now available.
 194     ///
 195     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 196                       unsigned VirtReg, unsigned PhysReg);
 197
 198     /// spillPhysReg - This method spills the specified physical register into
 199     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 200     /// true, then the request is ignored if the physical register does not
 201     /// contain a virtual register.
 202     ///
 203     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 204                       unsigned PhysReg, bool OnlyVirtRegs = false);
 205
 206     /// assignVirtToPhysReg - This method updates local state so that we know
 207     /// that PhysReg is the proper container for VirtReg now.  The physical
 208     /// register must not be used for anything else when this is called.
 209     ///
 210     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 211
 212     /// isPhysRegAvailable - Return true if the specified physical register is
 213     /// free and available for use.  This also includes checking to see if
 214     /// aliased registers are all free...
 215     ///
 216     bool isPhysRegAvailable(unsigned PhysReg) const;
 217
 218     /// getFreeReg - Look to see if there is a free register available in the
 219     /// specified register class.  If not, return 0.
 220     ///
 221     unsigned getFreeReg(const TargetRegisterClass *RC);
 222
 223     /// getReg - Find a physical register to hold the specified virtual
 224     /// register.  If all compatible physical registers are used, this method
 225     /// spills the last used virtual register to the stack, and uses that
 226     /// register. If NoFree is true, that means the caller knows there isn't
 227     /// a free register, do not call getFreeReg().
 228     unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI,
 229                     unsigned VirtReg, bool NoFree = false);
 230
 231     /// reloadVirtReg - This method transforms the specified virtual
 232     /// register use to refer to a physical register.  This method may do this
 233     /// in one of several ways: if the register is available in a physical
 234     /// register already, it uses that physical register.  If the value is not
 235     /// in a physical register, and if there are physical registers available,
 236     /// it loads it into a register.  If register pressure is high, and it is
 237     /// possible, it tries to fold the load of the virtual register into the
 238     /// instruction itself.  It avoids doing this if register pressure is low to
 239     /// improve the chance that subsequent instructions can use the reloaded
 240     /// value.  This method returns the modified instruction.
 241     ///
 242     MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 243                                 unsigned OpNum, SmallSet<unsigned, 4> &RRegs);
 244
 245     /// ComputeLocalLiveness - Computes liveness of registers within a basic
 246     /// block, setting the killed/dead flags as appropriate.
 247     void ComputeLocalLiveness(MachineBasicBlock& MBB);
 248
 249     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 250                        unsigned PhysReg);
 251   };
 252   char RALocal::ID = 0;
 253 }
 254
 255 /// getStackSpaceFor - This allocates space for the specified virtual register
 256 /// to be held on the stack.
 257 int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 258   // Find the location Reg would belong...
 259   int SS = StackSlotForVirtReg[VirtReg];
 260   if (SS != -1)
 261     return SS;          // Already has space allocated?
 262
 263   // Allocate a new stack object for this spill location...
 264   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
 265                                                        RC->getAlignment());
 266
 267   // Assign the slot...
 268   StackSlotForVirtReg[VirtReg] = FrameIdx;
 269   return FrameIdx;
 270 }
 271
 272
 273 /// removePhysReg - This method marks the specified physical register as no
 274 /// longer being in use.
 275 ///
 276 void RALocal::removePhysReg(unsigned PhysReg) {
 277   PhysRegsUsed[PhysReg] = -1;      // PhyReg no longer used
 278
 279   std::vector<unsigned>::iterator It =
 280     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 281   if (It != PhysRegsUseOrder.end())
 282     PhysRegsUseOrder.erase(It);
 283 }
 284
 285
 286 /// spillVirtReg - This method spills the value specified by PhysReg into the
 287 /// virtual register slot specified by VirtReg.  It then updates the RA data
 288 /// structures to indicate the fact that PhysReg is now available.
 289 ///
 290 void RALocal::spillVirtReg(MachineBasicBlock &MBB,
 291                            MachineBasicBlock::iterator I,
 292                            unsigned VirtReg, unsigned PhysReg) {
 293   assert(VirtReg && "Spilling a physical register is illegal!"
 294          " Must not have appropriate kill for the register or use exists beyond"
 295          " the intended one.");
 296   DOUT << "  Spilling register " << TRI->getName(PhysReg)
 297        << " containing %reg" << VirtReg;
 298
 299   if (!isVirtRegModified(VirtReg)) {
 300     DOUT << " which has not been modified, so no store necessary!";
 301     std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg);
 302     if (LastUse.first)
 303       LastUse.first->getOperand(LastUse.second).setIsKill();
 304   } else {
 305     // Otherwise, there is a virtual register corresponding to this physical
 306     // register.  We only need to spill it into its stack slot if it has been
 307     // modified.
 308     const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 309     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 310     DOUT << " to stack slot #" << FrameIndex;
 311     // If the instruction reads the register that's spilled, (e.g. this can
 312     // happen if it is a move to a physical register), then the spill
 313     // instruction is not a kill.
 314     bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg));
 315     TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC);
 316     ++NumStores;   // Update statistics
 317   }
 318
 319   getVirt2PhysRegMapSlot(VirtReg) = 0;   // VirtReg no longer available
 320
 321   DOUT << "\n";
 322   removePhysReg(PhysReg);
 323 }
 324
 325
 326 /// spillPhysReg - This method spills the specified physical register into the
 327 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 328 /// then the request is ignored if the physical register does not contain a
 329 /// virtual register.
 330 ///
 331 void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 332                            unsigned PhysReg, bool OnlyVirtRegs) {
 333   if (PhysRegsUsed[PhysReg] != -1) {            // Only spill it if it's used!
 334     assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!");
 335     if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs)
 336       spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
 337   } else {
 338     // If the selected register aliases any other registers, we must make
 339     // sure that one of the aliases isn't alive.
 340     for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
 341          *AliasSet; ++AliasSet)
 342       if (PhysRegsUsed[*AliasSet] != -1 &&     // Spill aliased register.
 343           PhysRegsUsed[*AliasSet] != -2)       // If allocatable.
 344           if (PhysRegsUsed[*AliasSet])
 345             spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet);
 346   }
 347 }
 348
 349
 350 /// assignVirtToPhysReg - This method updates local state so that we know
 351 /// that PhysReg is the proper container for VirtReg now.  The physical
 352 /// register must not be used for anything else when this is called.
 353 ///
 354 void RALocal::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 355   assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!");
 356   // Update information to note the fact that this register was just used, and
 357   // it holds VirtReg.
 358   PhysRegsUsed[PhysReg] = VirtReg;
 359   getVirt2PhysRegMapSlot(VirtReg) = PhysReg;
 360   AddToPhysRegsUseOrder(PhysReg);   // New use of PhysReg
 361 }
 362
 363
 364 /// isPhysRegAvailable - Return true if the specified physical register is free
 365 /// and available for use.  This also includes checking to see if aliased
 366 /// registers are all free...
 367 ///
 368 bool RALocal::isPhysRegAvailable(unsigned PhysReg) const {
 369   if (PhysRegsUsed[PhysReg] != -1) return false;
 370
 371   // If the selected register aliases any other allocated registers, it is
 372   // not free!
 373   for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
 374        *AliasSet; ++AliasSet)
 375     if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use?
 376       return false;                    // Can't use this reg then.
 377   return true;
 378 }
 379
 380
 381 /// getFreeReg - Look to see if there is a free register available in the
 382 /// specified register class.  If not, return 0.
 383 ///
 384 unsigned RALocal::getFreeReg(const TargetRegisterClass *RC) {
 385   // Get iterators defining the range of registers that are valid to allocate in
 386   // this class, which also specifies the preferred allocation order.
 387   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 388   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 389
 390   for (; RI != RE; ++RI)
 391     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 392       assert(*RI != 0 && "Cannot use register!");
 393       return *RI; // Found an unused register!
 394     }
 395   return 0;
 396 }
 397
 398
 399 /// getReg - Find a physical register to hold the specified virtual
 400 /// register.  If all compatible physical registers are used, this method spills
 401 /// the last used virtual register to the stack, and uses that register.
 402 ///
 403 unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I,
 404                          unsigned VirtReg, bool NoFree) {
 405   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 406
 407   // First check to see if we have a free register of the requested type...
 408   unsigned PhysReg = NoFree ? 0 : getFreeReg(RC);
 409
 410   // If we didn't find an unused register, scavenge one now!
 411   if (PhysReg == 0) {
 412     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 413
 414     // Loop over all of the preallocated registers from the least recently used
 415     // to the most recently used.  When we find one that is capable of holding
 416     // our register, use it.
 417     for (unsigned i = 0; PhysReg == 0; ++i) {
 418       assert(i != PhysRegsUseOrder.size() &&
 419              "Couldn't find a register of the appropriate class!");
 420
 421       unsigned R = PhysRegsUseOrder[i];
 422
 423       // We can only use this register if it holds a virtual register (ie, it
 424       // can be spilled).  Do not use it if it is an explicitly allocated
 425       // physical register!
 426       assert(PhysRegsUsed[R] != -1 &&
 427              "PhysReg in PhysRegsUseOrder, but is not allocated?");
 428       if (PhysRegsUsed[R] && PhysRegsUsed[R] != -2) {
 429         // If the current register is compatible, use it.
 430         if (RC->contains(R)) {
 431           PhysReg = R;
 432           break;
 433         } else {
 434           // If one of the registers aliased to the current register is
 435           // compatible, use it.
 436           for (const unsigned *AliasIt = TRI->getAliasSet(R);
 437                *AliasIt; ++AliasIt) {
 438             if (RC->contains(*AliasIt) &&
 439                 // If this is pinned down for some reason, don't use it.  For
 440                 // example, if CL is pinned, and we run across CH, don't use
 441                 // CH as justification for using scavenging ECX (which will
 442                 // fail).
 443                 PhysRegsUsed[*AliasIt] != 0 &&
 444
 445                 // Make sure the register is allocatable.  Don't allocate SIL on
 446                 // x86-32.
 447                 PhysRegsUsed[*AliasIt] != -2) {
 448               PhysReg = *AliasIt;    // Take an aliased register
 449               break;
 450             }
 451           }
 452         }
 453       }
 454     }
 455
 456     assert(PhysReg && "Physical register not assigned!?!?");
 457
 458     // At this point PhysRegsUseOrder[i] is the least recently used register of
 459     // compatible register class.  Spill it to memory and reap its remains.
 460     spillPhysReg(MBB, I, PhysReg);
 461   }
 462
 463   // Now that we know which register we need to assign this to, do it now!
 464   assignVirtToPhysReg(VirtReg, PhysReg);
 465   return PhysReg;
 466 }
 467
 468
 469 /// reloadVirtReg - This method transforms the specified virtual
 470 /// register use to refer to a physical register.  This method may do this in
 471 /// one of several ways: if the register is available in a physical register
 472 /// already, it uses that physical register.  If the value is not in a physical
 473 /// register, and if there are physical registers available, it loads it into a
 474 /// register.  If register pressure is high, and it is possible, it tries to
 475 /// fold the load of the virtual register into the instruction itself.  It
 476 /// avoids doing this if register pressure is low to improve the chance that
 477 /// subsequent instructions can use the reloaded value.  This method returns the
 478 /// modified instruction.
 479 ///
 480 MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 481                                      unsigned OpNum,
 482                                      SmallSet<unsigned, 4> &ReloadedRegs) {
 483   unsigned VirtReg = MI->getOperand(OpNum).getReg();
 484
 485   // If the virtual register is already available, just update the instruction
 486   // and return.
 487   if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
 488     MarkPhysRegRecentlyUsed(PR);       // Already have this value available!
 489     MI->getOperand(OpNum).setReg(PR);  // Assign the input register
 490     getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
 491     return MI;
 492   }
 493
 494   // Otherwise, we need to fold it into the current instruction, or reload it.
 495   // If we have registers available to hold the value, use them.
 496   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 497   unsigned PhysReg = getFreeReg(RC);
 498   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 499
 500   if (PhysReg) {   // Register is available, allocate it!
 501     assignVirtToPhysReg(VirtReg, PhysReg);
 502   } else {         // No registers available.
 503     // Force some poor hapless value out of the register file to
 504     // make room for the new register, and reload it.
 505     PhysReg = getReg(MBB, MI, VirtReg, true);
 506   }
 507
 508   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 509
 510   DOUT << "  Reloading %reg" << VirtReg << " into "
 511        << TRI->getName(PhysReg) << "\n";
 512
 513   // Add move instruction(s)
 514   TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC);
 515   ++NumLoads;    // Update statistics
 516
 517   MF->getRegInfo().setPhysRegUsed(PhysReg);
 518   MI->getOperand(OpNum).setReg(PhysReg);  // Assign the input register
 519   getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
 520
 521   if (!ReloadedRegs.insert(PhysReg)) {
 522     std::string msg;
 523     raw_string_ostream Msg(msg);
 524     Msg << "Ran out of registers during register allocation!";
 525     if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
 526       Msg << "\nPlease check your inline asm statement for invalid "
 527            << "constraints:\n";
 528       MI->print(Msg, TM);
 529     }
 530     llvm_report_error(Msg.str());
 531   }
 532   for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
 533        *SubRegs; ++SubRegs) {
 534     if (!ReloadedRegs.insert(*SubRegs)) {
 535       std::string msg;
 536       raw_string_ostream Msg(msg);
 537       Msg << "Ran out of registers during register allocation!";
 538       if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
 539         Msg << "\nPlease check your inline asm statement for invalid "
 540              << "constraints:\n";
 541         MI->print(Msg, TM);
 542       }
 543       llvm_report_error(Msg.str());
 544     }
 545   }
 546
 547   return MI;
 548 }
 549
 550 /// isReadModWriteImplicitKill - True if this is an implicit kill for a
 551 /// read/mod/write register, i.e. update partial register.
 552 static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) {
 553   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 554     MachineOperand& MO = MI->getOperand(i);
 555     if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
 556         MO.isDef() && !MO.isDead())
 557       return true;
 558   }
 559   return false;
 560 }
 561
 562 /// isReadModWriteImplicitDef - True if this is an implicit def for a
 563 /// read/mod/write register, i.e. update partial register.
 564 static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) {
 565   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 566     MachineOperand& MO = MI->getOperand(i);
 567     if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
 568         !MO.isDef() && MO.isKill())
 569       return true;
 570   }
 571   return false;
 572 }
 573
 574 // precedes - Helper function to determine with MachineInstr A
 575 // precedes MachineInstr B within the same MBB.
 576 static bool precedes(MachineBasicBlock::iterator A,
 577                      MachineBasicBlock::iterator B) {
 578   if (A == B)
 579     return false;
 580
 581   MachineBasicBlock::iterator I = A->getParent()->begin();
 582   while (I != A->getParent()->end()) {
 583     if (I == A)
 584       return true;
 585     else if (I == B)
 586       return false;
 587
 588     ++I;
 589   }
 590
 591   return false;
 592 }
 593
 594 /// ComputeLocalLiveness - Computes liveness of registers within a basic
 595 /// block, setting the killed/dead flags as appropriate.
 596 void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
 597   MachineRegisterInfo& MRI = MBB.getParent()->getRegInfo();
 598   // Keep track of the most recently seen previous use or def of each reg,
 599   // so that we can update them with dead/kill markers.
 600   DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > LastUseDef;
 601   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
 602        I != E; ++I) {
 603     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 604       MachineOperand& MO = I->getOperand(i);
 605       // Uses don't trigger any flags, but we need to save
 606       // them for later.  Also, we have to process these
 607       // _before_ processing the defs, since an instr
 608       // uses regs before it defs them.
 609       if (MO.isReg() && MO.getReg() && MO.isUse()) {
 610         LastUseDef[MO.getReg()] = std::make_pair(I, i);
 611
 612
 613         if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) continue;
 614
 615         const unsigned* Aliases = TRI->getAliasSet(MO.getReg());
 616         if (Aliases) {
 617           while (*Aliases) {
 618             DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 619               alias = LastUseDef.find(*Aliases);
 620
 621             if (alias != LastUseDef.end() && alias->second.first != I)
 622               LastUseDef[*Aliases] = std::make_pair(I, i);
 623
 624             ++Aliases;
 625           }
 626         }
 627       }
 628     }
 629
 630     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 631       MachineOperand& MO = I->getOperand(i);
 632       // Defs others than 2-addr redefs _do_ trigger flag changes:
 633       //   - A def followed by a def is dead
 634       //   - A use followed by a def is a kill
 635       if (MO.isReg() && MO.getReg() && MO.isDef()) {
 636         DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 637           last = LastUseDef.find(MO.getReg());
 638         if (last != LastUseDef.end()) {
 639           // Check if this is a two address instruction.  If so, then
 640           // the def does not kill the use.
 641           if (last->second.first == I &&
 642               I->isRegTiedToUseOperand(i))
 643             continue;
 644
 645           MachineOperand& lastUD =
 646                       last->second.first->getOperand(last->second.second);
 647           if (lastUD.isDef())
 648             lastUD.setIsDead(true);
 649           else
 650             lastUD.setIsKill(true);
 651         }
 652
 653         LastUseDef[MO.getReg()] = std::make_pair(I, i);
 654       }
 655     }
 656   }
 657
 658   // Live-out (of the function) registers contain return values of the function,
 659   // so we need to make sure they are alive at return time.
 660   if (!MBB.empty() && MBB.back().getDesc().isReturn()) {
 661     MachineInstr* Ret = &MBB.back();
 662     for (MachineRegisterInfo::liveout_iterator
 663          I = MF->getRegInfo().liveout_begin(),
 664          E = MF->getRegInfo().liveout_end(); I != E; ++I)
 665       if (!Ret->readsRegister(*I)) {
 666         Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
 667         LastUseDef[*I] = std::make_pair(Ret, Ret->getNumOperands()-1);
 668       }
 669   }
 670
 671   // Finally, loop over the final use/def of each reg
 672   // in the block and determine if it is dead.
 673   for (DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 674        I = LastUseDef.begin(), E = LastUseDef.end(); I != E; ++I) {
 675     MachineInstr* MI = I->second.first;
 676     unsigned idx = I->second.second;
 677     MachineOperand& MO = MI->getOperand(idx);
 678
 679     bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(MO.getReg());
 680
 681     // A crude approximation of "live-out" calculation
 682     bool usedOutsideBlock = isPhysReg ? false :
 683           UsedInMultipleBlocks.test(MO.getReg() -
 684                                     TargetRegisterInfo::FirstVirtualRegister);
 685     if (!isPhysReg && !usedOutsideBlock)
 686       for (MachineRegisterInfo::reg_iterator UI = MRI.reg_begin(MO.getReg()),
 687            UE = MRI.reg_end(); UI != UE; ++UI)
 688         // Two cases:
 689         // - used in another block
 690         // - used in the same block before it is defined (loop)
 691         if (UI->getParent() != &MBB ||
 692             (MO.isDef() && UI.getOperand().isUse() && precedes(&*UI, MI))) {
 693           UsedInMultipleBlocks.set(MO.getReg() -
 694                                    TargetRegisterInfo::FirstVirtualRegister);
 695           usedOutsideBlock = true;
 696           break;
 697         }
 698
 699     // Physical registers and those that are not live-out of the block
 700     // are killed/dead at their last use/def within this block.
 701     if (isPhysReg || !usedOutsideBlock) {
 702       if (MO.isUse()) {
 703         // Don't mark uses that are tied to defs as kills.
 704         if (!MI->isRegTiedToDefOperand(idx))
 705           MO.setIsKill(true);
 706       } else
 707         MO.setIsDead(true);
 708     }
 709   }
 710 }
 711
 712 void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) {
 713   // loop over each instruction
 714   MachineBasicBlock::iterator MII = MBB.begin();
 715
 716   DEBUG(const BasicBlock *LBB = MBB.getBasicBlock();
 717         if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName());
 718
 719   // Add live-in registers as active.
 720   for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
 721          E = MBB.livein_end(); I != E; ++I) {
 722     unsigned Reg = *I;
 723     MF->getRegInfo().setPhysRegUsed(Reg);
 724     PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 725     AddToPhysRegsUseOrder(Reg);
 726     for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 727          *SubRegs; ++SubRegs) {
 728       if (PhysRegsUsed[*SubRegs] != -2) {
 729         AddToPhysRegsUseOrder(*SubRegs);
 730         PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 731         MF->getRegInfo().setPhysRegUsed(*SubRegs);
 732       }
 733     }
 734   }
 735
 736   ComputeLocalLiveness(MBB);
 737
 738   // Otherwise, sequentially allocate each instruction in the MBB.
 739   while (MII != MBB.end()) {
 740     MachineInstr *MI = MII++;
 741     const TargetInstrDesc &TID = MI->getDesc();
 742     DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI;
 743           DOUT << "  Regs have values: ";
 744           for (unsigned i = 0; i != TRI->getNumRegs(); ++i)
 745             if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
 746                DOUT << "[" << TRI->getName(i)
 747                     << ",%reg" << PhysRegsUsed[i] << "] ";
 748           DOUT << "\n");
 749
 750     // Loop over the implicit uses, making sure that they are at the head of the
 751     // use order list, so they don't get reallocated.
 752     if (TID.ImplicitUses) {
 753       for (const unsigned *ImplicitUses = TID.ImplicitUses;
 754            *ImplicitUses; ++ImplicitUses)
 755         MarkPhysRegRecentlyUsed(*ImplicitUses);
 756     }
 757
 758     SmallVector<unsigned, 8> Kills;
 759     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 760       MachineOperand& MO = MI->getOperand(i);
 761       if (MO.isReg() && MO.isKill()) {
 762         if (!MO.isImplicit())
 763           Kills.push_back(MO.getReg());
 764         else if (!isReadModWriteImplicitKill(MI, MO.getReg()))
 765           // These are extra physical register kills when a sub-register
 766           // is defined (def of a sub-register is a read/mod/write of the
 767           // larger registers). Ignore.
 768           Kills.push_back(MO.getReg());
 769       }
 770     }
 771
 772     // If any physical regs are earlyclobber, spill any value they might
 773     // have in them, then mark them unallocatable.
 774     // If any virtual regs are earlyclobber, allocate them now (before
 775     // freeing inputs that are killed).
 776     if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
 777       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 778         MachineOperand& MO = MI->getOperand(i);
 779         if (MO.isReg() && MO.isDef() && MO.isEarlyClobber() &&
 780             MO.getReg()) {
 781           if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 782             unsigned DestVirtReg = MO.getReg();
 783             unsigned DestPhysReg;
 784
 785             // If DestVirtReg already has a value, use it.
 786             if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 787               DestPhysReg = getReg(MBB, MI, DestVirtReg);
 788             MF->getRegInfo().setPhysRegUsed(DestPhysReg);
 789             markVirtRegModified(DestVirtReg);
 790             getVirtRegLastUse(DestVirtReg) =
 791                    std::make_pair((MachineInstr*)0, 0);
 792             DOUT << "  Assigning " << TRI->getName(DestPhysReg)
 793                  << " to %reg" << DestVirtReg << "\n";
 794             MO.setReg(DestPhysReg);  // Assign the earlyclobber register
 795           } else {
 796             unsigned Reg = MO.getReg();
 797             if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
 798             // These are extra physical register defs when a sub-register
 799             // is defined (def of a sub-register is a read/mod/write of the
 800             // larger registers). Ignore.
 801             if (isReadModWriteImplicitDef(MI, MO.getReg())) continue;
 802
 803             MF->getRegInfo().setPhysRegUsed(Reg);
 804             spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
 805             PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 806             AddToPhysRegsUseOrder(Reg);
 807
 808             for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 809                  *SubRegs; ++SubRegs) {
 810               if (PhysRegsUsed[*SubRegs] != -2) {
 811                 MF->getRegInfo().setPhysRegUsed(*SubRegs);
 812                 PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 813                 AddToPhysRegsUseOrder(*SubRegs);
 814               }
 815             }
 816           }
 817         }
 818       }
 819     }
 820
 821     // Get the used operands into registers.  This has the potential to spill
 822     // incoming values if we are out of registers.  Note that we completely
 823     // ignore physical register uses here.  We assume that if an explicit
 824     // physical register is referenced by the instruction, that it is guaranteed
 825     // to be live-in, or the input is badly hosed.
 826     //
 827     SmallSet<unsigned, 4> ReloadedRegs;
 828     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 829       MachineOperand& MO = MI->getOperand(i);
 830       // here we are looking for only used operands (never def&use)
 831       if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() &&
 832           TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 833         MI = reloadVirtReg(MBB, MI, i, ReloadedRegs);
 834     }
 835
 836     // If this instruction is the last user of this register, kill the
 837     // value, freeing the register being used, so it doesn't need to be
 838     // spilled to memory.
 839     //
 840     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 841       unsigned VirtReg = Kills[i];
 842       unsigned PhysReg = VirtReg;
 843       if (TargetRegisterInfo::isVirtualRegister(VirtReg)) {
 844         // If the virtual register was never materialized into a register, it
 845         // might not be in the map, but it won't hurt to zero it out anyway.
 846         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 847         PhysReg = PhysRegSlot;
 848         PhysRegSlot = 0;
 849       } else if (PhysRegsUsed[PhysReg] == -2) {
 850         // Unallocatable register dead, ignore.
 851         continue;
 852       } else {
 853         assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) &&
 854                "Silently clearing a virtual register?");
 855       }
 856
 857       if (PhysReg) {
 858         DOUT << "  Last use of " << TRI->getName(PhysReg)
 859              << "[%reg" << VirtReg <<"], removing it from live set\n";
 860         removePhysReg(PhysReg);
 861         for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
 862              *SubRegs; ++SubRegs) {
 863           if (PhysRegsUsed[*SubRegs] != -2) {
 864             DOUT  << "  Last use of "
 865                   << TRI->getName(*SubRegs)
 866                   << "[%reg" << VirtReg <<"], removing it from live set\n";
 867             removePhysReg(*SubRegs);
 868           }
 869         }
 870       }
 871     }
 872
 873     // Loop over all of the operands of the instruction, spilling registers that
 874     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 875     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 876       MachineOperand& MO = MI->getOperand(i);
 877       if (MO.isReg() && MO.isDef() && !MO.isImplicit() && MO.getReg() &&
 878           !MO.isEarlyClobber() &&
 879           TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
 880         unsigned Reg = MO.getReg();
 881         if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
 882         // These are extra physical register defs when a sub-register
 883         // is defined (def of a sub-register is a read/mod/write of the
 884         // larger registers). Ignore.
 885         if (isReadModWriteImplicitDef(MI, MO.getReg())) continue;
 886
 887         MF->getRegInfo().setPhysRegUsed(Reg);
 888         spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
 889         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 890         AddToPhysRegsUseOrder(Reg);
 891
 892         for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 893              *SubRegs; ++SubRegs) {
 894           if (PhysRegsUsed[*SubRegs] != -2) {
 895             MF->getRegInfo().setPhysRegUsed(*SubRegs);
 896             PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 897             AddToPhysRegsUseOrder(*SubRegs);
 898           }
 899         }
 900       }
 901     }
 902
 903     // Loop over the implicit defs, spilling them as well.
 904     if (TID.ImplicitDefs) {
 905       for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 906            *ImplicitDefs; ++ImplicitDefs) {
 907         unsigned Reg = *ImplicitDefs;
 908         if (PhysRegsUsed[Reg] != -2) {
 909           spillPhysReg(MBB, MI, Reg, true);
 910           AddToPhysRegsUseOrder(Reg);
 911           PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 912         }
 913         MF->getRegInfo().setPhysRegUsed(Reg);
 914         for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 915              *SubRegs; ++SubRegs) {
 916           if (PhysRegsUsed[*SubRegs] != -2) {
 917             AddToPhysRegsUseOrder(*SubRegs);
 918             PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 919             MF->getRegInfo().setPhysRegUsed(*SubRegs);
 920           }
 921         }
 922       }
 923     }
 924
 925     SmallVector<unsigned, 8> DeadDefs;
 926     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 927       MachineOperand& MO = MI->getOperand(i);
 928       if (MO.isReg() && MO.isDead())
 929         DeadDefs.push_back(MO.getReg());
 930     }
 931
 932     // Okay, we have allocated all of the source operands and spilled any values
 933     // that would be destroyed by defs of this instruction.  Loop over the
 934     // explicit defs and assign them to a register, spilling incoming values if
 935     // we need to scavenge a register.
 936     //
 937     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 938       MachineOperand& MO = MI->getOperand(i);
 939       if (MO.isReg() && MO.isDef() && MO.getReg() &&
 940           !MO.isEarlyClobber() &&
 941           TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 942         unsigned DestVirtReg = MO.getReg();
 943         unsigned DestPhysReg;
 944
 945         // If DestVirtReg already has a value, use it.
 946         if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 947           DestPhysReg = getReg(MBB, MI, DestVirtReg);
 948         MF->getRegInfo().setPhysRegUsed(DestPhysReg);
 949         markVirtRegModified(DestVirtReg);
 950         getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0);
 951         DOUT << "  Assigning " << TRI->getName(DestPhysReg)
 952              << " to %reg" << DestVirtReg << "\n";
 953         MO.setReg(DestPhysReg);  // Assign the output register
 954       }
 955     }
 956
 957     // If this instruction defines any registers that are immediately dead,
 958     // kill them now.
 959     //
 960     for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) {
 961       unsigned VirtReg = DeadDefs[i];
 962       unsigned PhysReg = VirtReg;
 963       if (TargetRegisterInfo::isVirtualRegister(VirtReg)) {
 964         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 965         PhysReg = PhysRegSlot;
 966         assert(PhysReg != 0);
 967         PhysRegSlot = 0;
 968       } else if (PhysRegsUsed[PhysReg] == -2) {
 969         // Unallocatable register dead, ignore.
 970         continue;
 971       }
 972
 973       if (PhysReg) {
 974         DOUT  << "  Register " << TRI->getName(PhysReg)
 975               << " [%reg" << VirtReg
 976               << "] is never used, removing it from live set\n";
 977         removePhysReg(PhysReg);
 978         for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
 979              *AliasSet; ++AliasSet) {
 980           if (PhysRegsUsed[*AliasSet] != -2) {
 981             DOUT  << "  Register " << TRI->getName(*AliasSet)
 982                   << " [%reg" << *AliasSet
 983                   << "] is never used, removing it from live set\n";
 984             removePhysReg(*AliasSet);
 985           }
 986         }
 987       }
 988     }
 989
 990     // Finally, if this is a noop copy instruction, zap it.  (Except that if
 991     // the copy is dead, it must be kept to avoid messing up liveness info for
 992     // the register scavenger.  See pr4100.)
 993     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 994     if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
 995         SrcReg == DstReg && DeadDefs.empty())
 996       MBB.erase(MI);
 997   }
 998
 999   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
1000
1001   // Spill all physical registers holding virtual registers now.
1002   for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i)
1003     if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) {
1004       if (unsigned VirtReg = PhysRegsUsed[i])
1005         spillVirtReg(MBB, MI, VirtReg, i);
1006       else
1007         removePhysReg(i);
1008     }
1009
1010 #if 0
1011   // This checking code is very expensive.
1012   bool AllOk = true;
1013   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
1014            e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
1015     if (unsigned PR = Virt2PhysRegMap[i]) {
1016       cerr << "Register still mapped: " << i << " -> " << PR << "\n";
1017       AllOk = false;
1018     }
1019   assert(AllOk && "Virtual registers still in phys regs?");
1020 #endif
1021
1022   // Clear any physical register which appear live at the end of the basic
1023   // block, but which do not hold any virtual registers.  e.g., the stack
1024   // pointer.
1025   PhysRegsUseOrder.clear();
1026 }
1027
1028 /// runOnMachineFunction - Register allocate the whole function
1029 ///
1030 bool RALocal::runOnMachineFunction(MachineFunction &Fn) {
1031   DOUT << "Machine Function " << "\n";
1032   MF = &Fn;
1033   TM = &Fn.getTarget();
1034   TRI = TM->getRegisterInfo();
1035   TII = TM->getInstrInfo();
1036
1037   PhysRegsUsed.assign(TRI->getNumRegs(), -1);
1038
1039   // At various places we want to efficiently check to see whether a register
1040   // is allocatable.  To handle this, we mark all unallocatable registers as
1041   // being pinned down, permanently.
1042   {
1043     BitVector Allocable = TRI->getAllocatableSet(Fn);
1044     for (unsigned i = 0, e = Allocable.size(); i != e; ++i)
1045       if (!Allocable[i])
1046         PhysRegsUsed[i] = -2;  // Mark the reg unallocable.
1047   }
1048
1049   // initialize the virtual->physical register map to have a 'null'
1050   // mapping for all virtual registers
1051   unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
1052   StackSlotForVirtReg.grow(LastVirtReg);
1053   Virt2PhysRegMap.grow(LastVirtReg);
1054   Virt2LastUseMap.grow(LastVirtReg);
1055   VirtRegModified.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister);
1056   UsedInMultipleBlocks.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister);
1057
1058   // Loop over all of the basic blocks, eliminating virtual register references
1059   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
1060        MBB != MBBe; ++MBB)
1061     AllocateBasicBlock(*MBB);
1062
1063   StackSlotForVirtReg.clear();
1064   PhysRegsUsed.clear();
1065   VirtRegModified.clear();
1066   UsedInMultipleBlocks.clear();
1067   Virt2PhysRegMap.clear();
1068   Virt2LastUseMap.clear();
1069   return true;
1070 }
1071
1072 FunctionPass *llvm::createLocalRegisterAllocator() {
1073   return new RALocal();
1074 }