Mostly rewrite RegAllocFast.

Sorry for the big change. The path leading up to this patch had some TableGen
changes that I didn't want to commit before I knew they were useful. They
weren't, and this version does not need them.

The fast register allocator now does no liveness calculations. Instead it relies
on kill flags provided by isel. (Currently those kill flags are also ignored due
to isel bugs). The allocation algorithm is supposed to work with any subset of
valid kill flags. More kill flags simply means fewer spills inserted.

Registers are allocated from a working set that contains no aliases. That means
most allocations can be done directly without expensive alias checks. When the
working set runs out of registers we do the full alias check to find new free
registers.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103488 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 469 insertions, 700 deletions

diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp
index ab5e1032e1..488f630aa6 100644
--- a/lib/CodeGen/RegAllocFast.cpp
+++ b/lib/CodeGen/RegAllocFast.cpp
@@ -18,7 +18,6 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/Target/TargetInstrInfo.h"
@@ -57,65 +56,44 @@ namespace {
     // values are spilled.
     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
 
-    // Virt2PhysRegMap - This map contains entries for each virtual register
+    // Virt2PhysMap - This map contains entries for each virtual register
     // that is currently available in a physical register.
-    IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
+    DenseMap<unsigned, unsigned> Virt2PhysMap;
 
-    unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
-      return Virt2PhysRegMap[VirtReg];
-    }
+    // RegState - Track the state of a physical register.
+    enum RegState {
+      // A disabled register is not available for allocation, but an alias may
+      // be in use. A register can only be moved out of the disabled state if
+      // all aliases are disabled.
+      regDisabled,
+
+      // A free register is not currently in use and can be allocated
+      // immediately without checking aliases.
+      regFree,
+
+      // A reserved register has been assigned expolicitly (e.g., setting up a
+      // call parameter), and it remains reserved until it is used.
+      regReserved
 
-    // PhysRegsUsed - This array is effectively a map, containing entries for
-    // each physical register that currently has a value (ie, it is in
-    // Virt2PhysRegMap).  The value mapped to is the virtual register
-    // corresponding to the physical register (the inverse of the
-    // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
-    // because it is used by a future instruction, and to -2 if it is not
-    // allocatable.  If the entry for a physical register is -1, then the
-    // physical register is "not in the map".
-    //
-    std::vector<int> PhysRegsUsed;
+      // A register state may also be a virtual register number, indication that
+      // the physical register is currently allocated to a virtual register. In
+      // that case, Virt2PhysMap contains the inverse mapping.
+    };
+
+    // PhysRegState - One of the RegState enums, or a virtreg.
+    std::vector<unsigned> PhysRegState;
 
     // UsedInInstr - BitVector of physregs that are used in the current
     // instruction, and so cannot be allocated.
     BitVector UsedInInstr;
 
-    // Virt2LastUseMap - This maps each virtual register to its last use
-    // (MachineInstr*, operand index pair).
-    IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor>
-    Virt2LastUseMap;
+    // PhysRegDirty - A bit is set for each physreg that holds a dirty virtual
+    // register. Bits for physregs that are not mapped to a virtual register are
+    // invalid.
+    BitVector PhysRegDirty;
 
-    std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) {
-      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
-      return Virt2LastUseMap[Reg];
-    }
-
-    // VirtRegModified - This bitset contains information about which virtual
-    // registers need to be spilled back to memory when their registers are
-    // scavenged.  If a virtual register has simply been rematerialized, there
-    // is no reason to spill it to memory when we need the register back.
-    //
-    BitVector VirtRegModified;
-
-    // UsedInMultipleBlocks - Tracks whether a particular register is used in
-    // more than one block.
-    BitVector UsedInMultipleBlocks;
-
-    void markVirtRegModified(unsigned Reg, bool Val = true) {
-      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
-      Reg -= TargetRegisterInfo::FirstVirtualRegister;
-      if (Val)
-        VirtRegModified.set(Reg);
-      else
-        VirtRegModified.reset(Reg);
-    }
-
-    bool isVirtRegModified(unsigned Reg) const {
-      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
-      assert(Reg - TargetRegisterInfo::FirstVirtualRegister <
-             VirtRegModified.size() && "Illegal virtual register!");
-      return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister];
-    }
+    // ReservedRegs - vector of reserved physical registers.
+    BitVector ReservedRegs;
 
   public:
     virtual const char *getPassName() const {
@@ -124,104 +102,32 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
-      AU.addRequired<LiveVariables>();
       AU.addRequiredID(PHIEliminationID);
       AU.addRequiredID(TwoAddressInstructionPassID);
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
   private:
-    /// runOnMachineFunction - Register allocate the whole function
     bool runOnMachineFunction(MachineFunction &Fn);
-
-    /// AllocateBasicBlock - Register allocate the specified basic block.
     void AllocateBasicBlock(MachineBasicBlock &MBB);
-
-
-    /// areRegsEqual - This method returns true if the specified registers are
-    /// related to each other.  To do this, it checks to see if they are equal
-    /// or if the first register is in the alias set of the second register.
-    ///
-    bool areRegsEqual(unsigned R1, unsigned R2) const {
-      if (R1 == R2) return true;
-      for (const unsigned *AliasSet = TRI->getAliasSet(R2);
-           *AliasSet; ++AliasSet) {
-        if (*AliasSet == R1) return true;
-      }
-      return false;
-    }
-
-    /// getStackSpaceFor - This returns the frame index of the specified virtual
-    /// register on the stack, allocating space if necessary.
     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
-
-    /// removePhysReg - This method marks the specified physical register as no
-    /// longer being in use.
-    ///
-    void removePhysReg(unsigned PhysReg);
-
-    /// spillVirtReg - This method spills the value specified by PhysReg into
-    /// the virtual register slot specified by VirtReg.  It then updates the RA
-    /// data structures to indicate the fact that PhysReg is now available.
-    ///
+    void killVirtReg(unsigned VirtReg);
     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
-                      unsigned VirtReg, unsigned PhysReg);
-
-    /// spillPhysReg - This method spills the specified physical register into
-    /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
-    /// true, then the request is ignored if the physical register does not
-    /// contain a virtual register.
-    ///
+                      unsigned VirtReg, bool isKill);
+    void killPhysReg(unsigned PhysReg);
     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
-                      unsigned PhysReg, bool OnlyVirtRegs = false);
-
-    /// assignVirtToPhysReg - This method updates local state so that we know
-    /// that PhysReg is the proper container for VirtReg now.  The physical
-    /// register must not be used for anything else when this is called.
-    ///
+                      unsigned PhysReg, bool isKill);
     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
-
-    /// isPhysRegAvailable - Return true if the specified physical register is
-    /// free and available for use.  This also includes checking to see if
-    /// aliased registers are all free...
-    ///
-    bool isPhysRegAvailable(unsigned PhysReg) const;
-
-    /// isPhysRegSpillable - Can PhysReg be freed by spilling?
-    bool isPhysRegSpillable(unsigned PhysReg) const;
-
-    /// getFreeReg - Look to see if there is a free register available in the
-    /// specified register class.  If not, return 0.
-    ///
-    unsigned getFreeReg(const TargetRegisterClass *RC);
-
-    /// getReg - Find a physical register to hold the specified virtual
-    /// register.  If all compatible physical registers are used, this method
-    /// spills the last used virtual register to the stack, and uses that
-    /// register. If NoFree is true, that means the caller knows there isn't
-    /// a free register, do not call getFreeReg().
-    unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                    unsigned VirtReg, bool NoFree = false);
-
-    /// reloadVirtReg - This method transforms the specified virtual
-    /// register use to refer to a physical register.  This method may do this
-    /// in one of several ways: if the register is available in a physical
-    /// register already, it uses that physical register.  If the value is not
-    /// in a physical register, and if there are physical registers available,
-    /// it loads it into a register: PhysReg if that is an available physical
-    /// register, otherwise any physical register of the right class.
-    /// If register pressure is high, and it is possible, it tries to fold the
-    /// load of the virtual register into the instruction itself.  It avoids
-    /// doing this if register pressure is low to improve the chance that
-    /// subsequent instructions can use the reloaded value.  This method
-    /// returns the modified instruction.
-    ///
-    MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                                unsigned OpNum, SmallSet<unsigned, 4> &RRegs,
-                                unsigned PhysReg);
-
-    void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
-                       unsigned PhysReg);
+    unsigned allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                          unsigned VirtReg);
+    unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                           unsigned VirtReg);
+    unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                           unsigned VirtReg);
+    void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                        unsigned PhysReg);
+    void spillAll(MachineBasicBlock &MBB, MachineInstr *MI);
+    void setPhysReg(MachineOperand &MO, unsigned PhysReg);
   };
   char RAFast::ID = 0;
 }
@@ -243,676 +149,544 @@ int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
   return FrameIdx;
 }
 
-
-/// removePhysReg - This method marks the specified physical register as no
-/// longer being in use.
-///
-void RAFast::removePhysReg(unsigned PhysReg) {
-  PhysRegsUsed[PhysReg] = -1;      // PhyReg no longer used
+/// killVirtReg - Mark virtreg as no longer available.
+void RAFast::killVirtReg(unsigned VirtReg) {
+  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
+         "killVirtReg needs a virtual register");
+  DEBUG(dbgs() << "  Killing %reg" << VirtReg << "\n");
+  DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg);
+  if (i == Virt2PhysMap.end()) return;
+  unsigned PhysReg = i->second;
+  assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping");
+  PhysRegState[PhysReg] = regFree;
+  Virt2PhysMap.erase(i);
 }
 
-
-/// spillVirtReg - This method spills the value specified by PhysReg into the
-/// virtual register slot specified by VirtReg.  It then updates the RA data
-/// structures to indicate the fact that PhysReg is now available.
-///
+/// spillVirtReg - This method spills the value specified by VirtReg into the
+/// corresponding stack slot if needed. If isKill is set, the register is also
+/// killed.
 void RAFast::spillVirtReg(MachineBasicBlock &MBB,
-                           MachineBasicBlock::iterator I,
-                           unsigned VirtReg, unsigned PhysReg) {
-  assert(VirtReg && "Spilling a physical register is illegal!"
-         " Must not have appropriate kill for the register or use exists beyond"
-         " the intended one.");
-  DEBUG(dbgs() << "  Spilling register " << TRI->getName(PhysReg)
-               << " containing %reg" << VirtReg);
-
-  if (!isVirtRegModified(VirtReg)) {
-    DEBUG(dbgs() << " which has not been modified, so no store necessary!");
-    std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg);
-    if (LastUse.first)
-      LastUse.first->getOperand(LastUse.second).setIsKill();
-  } else {
-    // Otherwise, there is a virtual register corresponding to this physical
-    // register.  We only need to spill it into its stack slot if it has been
-    // modified.
+                          MachineBasicBlock::iterator I,
+                          unsigned VirtReg, bool isKill) {
+  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
+         "Spilling a physical register is illegal!");
+  DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg);
+  assert(i != Virt2PhysMap.end() && "Spilling unmapped virtual register");
+  unsigned PhysReg = i->second;
+  assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping");
+
+  if (PhysRegDirty.test(PhysReg)) {
+    PhysRegDirty.reset(PhysReg);
+    DEBUG(dbgs() << "  Spilling register " << TRI->getName(PhysReg)
+      << " containing %reg" << VirtReg);
     const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
     int FrameIndex = getStackSpaceFor(VirtReg, RC);
-    DEBUG(dbgs() << " to stack slot #" << FrameIndex);
-    // If the instruction reads the register that's spilled, (e.g. this can
-    // happen if it is a move to a physical register), then the spill
-    // instruction is not a kill.
-    bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg));
+    DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n");
     TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC, TRI);
     ++NumStores;   // Update statistics
   }
 
-  getVirt2PhysRegMapSlot(VirtReg) = 0;   // VirtReg no longer available
-
-  DEBUG(dbgs() << '\n');
-  removePhysReg(PhysReg);
+  if (isKill) {
+    PhysRegState[PhysReg] = regFree;
+    Virt2PhysMap.erase(i);
+  }
 }
 
+/// spillAll - Spill all dirty virtregs without killing them.
+void RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) {
+  SmallVector<unsigned, 16> Dirty;
+  for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(),
+       e = Virt2PhysMap.end(); i != e; ++i)
+    if (PhysRegDirty.test(i->second))
+      Dirty.push_back(i->first);
+  for (unsigned i = 0, e = Dirty.size(); i != e; ++i)
+    spillVirtReg(MBB, MI, Dirty[i], false);
+}
 
-/// spillPhysReg - This method spills the specified physical register into the
-/// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
-/// then the request is ignored if the physical register does not contain a
-/// virtual register.
-///
-void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
-                           unsigned PhysReg, bool OnlyVirtRegs) {
-  if (PhysRegsUsed[PhysReg] != -1) {            // Only spill it if it's used!
-    assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!");
-    if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs)
-      spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
+/// killPhysReg - Kill any virtual register aliased by PhysReg.
+void RAFast::killPhysReg(unsigned PhysReg) {
+  // Fast path for the normal case.
+  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
+  case regDisabled:
+    break;
+  case regFree:
+    return;
+  case regReserved:
+    PhysRegState[PhysReg] = regFree;
+    return;
+  default:
+    killVirtReg(VirtReg);
     return;
   }
 
-  // If the selected register aliases any other registers, we must make
-  // sure that one of the aliases isn't alive.
-  for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
-       *AliasSet; ++AliasSet) {
-    if (PhysRegsUsed[*AliasSet] == -1 ||     // Spill aliased register.
-        PhysRegsUsed[*AliasSet] == -2)       // If allocatable.
-      continue;
-
-    if (PhysRegsUsed[*AliasSet])
-      spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet);
+  // This is a disabled register, we have to check aliases.
+  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
+       unsigned Alias = *AS; ++AS) {
+    switch (unsigned VirtReg = PhysRegState[Alias]) {
+    case regDisabled:
+    case regFree:
+      break;
+    case regReserved:
+      PhysRegState[Alias] = regFree;
+      break;
+    default:
+      killVirtReg(VirtReg);
+      break;
+    }
   }
 }
 
+/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If
+/// isKill is set, they are also killed.
+void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                           unsigned PhysReg, bool isKill) {
+  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
+  case regDisabled:
+    break;
+  case regFree:
+    return;
+  case regReserved:
+    if (isKill)
+      PhysRegState[PhysReg] = regFree;
+    return;
+  default:
+    spillVirtReg(MBB, MI, VirtReg, isKill);
+    return;
+  }
+
+  // This is a disabled register, we have to check aliases.
+  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
+       unsigned Alias = *AS; ++AS) {
+    switch (unsigned VirtReg = PhysRegState[Alias]) {
+    case regDisabled:
+    case regFree:
+      break;
+    case regReserved:
+      if (isKill)
+        PhysRegState[Alias] = regFree;
+      break;
+    default:
+      spillVirtReg(MBB, MI, VirtReg, isKill);
+      break;
+    }
+  }
+}
 
 /// assignVirtToPhysReg - This method updates local state so that we know
 /// that PhysReg is the proper container for VirtReg now.  The physical
 /// register must not be used for anything else when this is called.
 ///
 void RAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
-  assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!");
-  // Update information to note the fact that this register was just used, and
-  // it holds VirtReg.
-  PhysRegsUsed[PhysReg] = VirtReg;
-  getVirt2PhysRegMapSlot(VirtReg) = PhysReg;
-  UsedInInstr.set(PhysReg);
-}
-
-
-/// isPhysRegAvailable - Return true if the specified physical register is free
-/// and available for use.  This also includes checking to see if aliased
-/// registers are all free...
-///
-bool RAFast::isPhysRegAvailable(unsigned PhysReg) const {
-  if (PhysRegsUsed[PhysReg] != -1) return false;
-
-  // If the selected register aliases any other allocated registers, it is
-  // not free!
-  for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
-       *AliasSet; ++AliasSet)
-    if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use?
-      return false;                    // Can't use this reg then.
-  return true;
-}
-
-/// isPhysRegSpillable - Return true if the specified physical register can be
-/// spilled for use in the current instruction.
-///
-bool RAFast::isPhysRegSpillable(unsigned PhysReg) const {
-  // Test that PhysReg and all aliases are either free or assigned to a VirtReg
-  // that is not used in the instruction.
-  if (PhysRegsUsed[PhysReg] != -1 &&
-      (PhysRegsUsed[PhysReg] <= 0 || UsedInInstr.test(PhysReg)))
-    return false;
-
-  for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
-       *AliasSet; ++AliasSet)
-    if (PhysRegsUsed[*AliasSet] != -1 &&
-        (PhysRegsUsed[*AliasSet] <= 0 || UsedInInstr.test(*AliasSet)))
-      return false;
-  return true;
+  DEBUG(dbgs() << "  Assigning %reg" << VirtReg << " to "
+               << TRI->getName(PhysReg) << "\n");
+  Virt2PhysMap.insert(std::make_pair(VirtReg, PhysReg));
+  PhysRegState[PhysReg] = VirtReg;
 }
 
+/// allocVirtReg - Allocate a physical register for VirtReg.
+unsigned RAFast::allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                              unsigned VirtReg) {
+  const unsigned spillCost = 100;
+  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
+         "Can only allocate virtual registers");
 
-/// getFreeReg - Look to see if there is a free register available in the
-/// specified register class.  If not, return 0.
-///
-unsigned RAFast::getFreeReg(const TargetRegisterClass *RC) {
-  // Get iterators defining the range of registers that are valid to allocate in
-  // this class, which also specifies the preferred allocation order.
-  TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
-  TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
-
-  for (; RI != RE; ++RI)
-    if (isPhysRegAvailable(*RI)) {       // Is reg unused?
-      assert(*RI != 0 && "Cannot use register!");
-      return *RI; // Found an unused register!
+  const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
+  TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF);
+  TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF);
+
+  // First try to find a completely free register.
+  unsigned BestCost = 0, BestReg = 0;
+  bool hasDisabled = false;
+  for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
+    unsigned PhysReg = *I;
+    switch(PhysRegState[PhysReg]) {
+    case regDisabled:
+      hasDisabled = true;
+    case regReserved:
+      continue;
+    case regFree:
+      if (!UsedInInstr.test(PhysReg)) {
+        assignVirtToPhysReg(VirtReg, PhysReg);
+        return PhysReg;
+      }
+      continue;
+    default:
+      // Grab the first spillable register we meet.
+      if (!BestReg && !UsedInInstr.test(PhysReg)) {
+        BestReg = PhysReg;
+        BestCost = PhysRegDirty.test(PhysReg) ? spillCost : 1;
+      }
+      continue;
     }
-  return 0;
-}
-
+  }
 
-/// getReg - Find a physical register to hold the specified virtual
-/// register.  If all compatible physical registers are used, this method spills
-/// the last used virtual register to the stack, and uses that register.
-///
-unsigned RAFast::getReg(MachineBasicBlock &MBB, MachineInstr *I,
-                         unsigned VirtReg, bool NoFree) {
-  const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
+  DEBUG(dbgs() << "  Allocating %reg" << VirtReg << " from " << RC->getName()
+               << " candidate=" << TRI->getName(BestReg) << "\n");
 
-  // First check to see if we have a free register of the requested type...
-  unsigned PhysReg = NoFree ? 0 : getFreeReg(RC);
+  // Try to extend the working set for RC if there were any disabled registers.
+  if (hasDisabled && (!BestReg || BestCost >= spillCost)) {
+    for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
+      unsigned PhysReg = *I;
+      if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg))
+        continue;
 
-  if (PhysReg != 0) {
-    // Assign the register.
-    assignVirtToPhysReg(VirtReg, PhysReg);
-    return PhysReg;
+      // Calculate the cost of bringing PhysReg into the working set.
+      unsigned Cost=0;
+      bool Impossible = false;
+      for (const unsigned *AS = TRI->getAliasSet(PhysReg);
+      unsigned Alias = *AS; ++AS) {
+        if (UsedInInstr.test(Alias)) {
+          Impossible = true;
+          break;
+        }
+        switch (PhysRegState[Alias]) {
+        case regDisabled:
+          break;
+        case regReserved:
+          Impossible = true;
+          break;
+        case regFree:
+          Cost++;
+          break;
+        default:
+          Cost += PhysRegDirty.test(Alias) ? spillCost : 1;
+          break;
+        }
+      }
+      if (Impossible) continue;
+      DEBUG(dbgs() << "  - candidate " << TRI->getName(PhysReg)
+        << " cost=" << Cost << "\n");
+      if (!BestReg || Cost < BestCost) {
+        BestReg = PhysReg;
+        BestCost = Cost;
+        if (Cost < spillCost) break;
+      }
+    }
   }
 
-  // If we didn't find an unused register, scavenge one now! Don't be fancy,
-  // just grab the first possible register.
-  TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
-  TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
-
-  for (; RI != RE; ++RI)
-    if (isPhysRegSpillable(*RI)) {
-      PhysReg = *RI;
-      break;
+  if (BestReg) {
+    // BestCost is 0 when all aliases are already disabled.
+    if (BestCost) {
+      if (PhysRegState[BestReg] != regDisabled)
+        spillVirtReg(MBB, MI, PhysRegState[BestReg], true);
+      else {
+        MF->getRegInfo().setPhysRegUsed(BestReg);
+        // Make sure all aliases are disabled.
+        for (const unsigned *AS = TRI->getAliasSet(BestReg);
+             unsigned Alias = *AS; ++AS) {
+          MF->getRegInfo().setPhysRegUsed(Alias);
+          switch (PhysRegState[Alias]) {
+          case regDisabled:
+            continue;
+          case regFree:
+            PhysRegState[Alias] = regDisabled;
+            break;
+          default:
+            spillVirtReg(MBB, MI, PhysRegState[Alias], true);
+            PhysRegState[Alias] = regDisabled;
+            break;
+          }
+        }
+      }
     }
+    assignVirtToPhysReg(VirtReg, BestReg);
+    return BestReg;
+  }
 
-  assert(PhysReg && "Physical register not assigned!?!?");
-  spillPhysReg(MBB, I, PhysReg);
-  assignVirtToPhysReg(VirtReg, PhysReg);
-  return PhysReg;
+  // Nothing we can do.
+  std::string msg;
+  raw_string_ostream Msg(msg);
+  Msg << "Ran out of registers during register allocation!";
+  if (MI->isInlineAsm()) {
+    Msg << "\nPlease check your inline asm statement for "
+        << "invalid constraints:\n";
+    MI->print(Msg, TM);
+  }
+  report_fatal_error(Msg.str());
+  return 0;
 }
 
+/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
+unsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                               unsigned VirtReg) {
+  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
+         "Not a virtual register");
+  unsigned PhysReg = Virt2PhysMap.lookup(VirtReg);
+  if (!PhysReg)
+    PhysReg = allocVirtReg(MBB, MI, VirtReg);
+  UsedInInstr.set(PhysReg);
+  PhysRegDirty.set(PhysReg);
+  return PhysReg;
+}
 
-/// reloadVirtReg - This method transforms the specified virtual
-/// register use to refer to a physical register.  This method may do this in
-/// one of several ways: if the register is available in a physical register
-/// already, it uses that physical register.  If the value is not in a physical
-/// register, and if there are physical registers available, it loads it into a
-/// register: PhysReg if that is an available physical register, otherwise any
-/// register.  If register pressure is high, and it is possible, it tries to
-/// fold the load of the virtual register into the instruction itself.  It
-/// avoids doing this if register pressure is low to improve the chance that
-/// subsequent instructions can use the reloaded value.  This method returns
-/// the modified instruction.
-///
-MachineInstr *RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
-                                     unsigned OpNum,
-                                     SmallSet<unsigned, 4> &ReloadedRegs,
-                                     unsigned PhysReg) {
-  unsigned VirtReg = MI->getOperand(OpNum).getReg();
-
-  // If the virtual register is already available, just update the instruction
-  // and return.
-  if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
-    MI->getOperand(OpNum).setReg(PR);  // Assign the input register
-    if (!MI->isDebugValue()) {
-      // Do not do these for DBG_VALUE as they can affect codegen.
-      UsedInInstr.set(PR);
-      getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
-    }
-    return MI;
+/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
+unsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                               unsigned VirtReg) {
+  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
+         "Not a virtual register");
+  unsigned PhysReg = Virt2PhysMap.lookup(VirtReg);
+  if (!PhysReg) {
+    PhysReg = allocVirtReg(MBB, MI, VirtReg);
+    PhysRegDirty.reset(PhysReg);
+    const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
+    int FrameIndex = getStackSpaceFor(VirtReg, RC);
+    DEBUG(dbgs() << "  Reloading %reg" << VirtReg << " into "
+      << TRI->getName(PhysReg) << "\n");
+    TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI);
+    ++NumLoads;
   }
+  UsedInInstr.set(PhysReg);
+  return PhysReg;
+}
 
-  // Otherwise, we need to fold it into the current instruction, or reload it.
-  // If we have registers available to hold the value, use them.
-  const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
-  // If we already have a PhysReg (this happens when the instruction is a
-  // reg-to-reg copy with a PhysReg destination) use that.
-  if (!PhysReg || !TargetRegisterInfo::isPhysicalRegister(PhysReg) ||
-      !isPhysRegAvailable(PhysReg))
-    PhysReg = getFreeReg(RC);
-  int FrameIndex = getStackSpaceFor(VirtReg, RC);
-
-  if (PhysReg) {   // Register is available, allocate it!
-    assignVirtToPhysReg(VirtReg, PhysReg);
-  } else {         // No registers available.
-    // Force some poor hapless value out of the register file to
-    // make room for the new register, and reload it.
-    PhysReg = getReg(MBB, MI, VirtReg, true);
+/// reservePhysReg - Mark PhysReg as reserved. This is very similar to
+/// defineVirtReg except the physreg is reverved instead of allocated.
+void RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
+                            unsigned PhysReg) {
+  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
+  case regDisabled:
+    break;
+  case regFree:
+    PhysRegState[PhysReg] = regReserved;
+    return;
+  case regReserved:
+    return;
+  default:
+    spillVirtReg(MBB, MI, VirtReg, true);
+    PhysRegState[PhysReg] = regReserved;
+    return;
   }
 
-  markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
-
-  DEBUG(dbgs() << "  Reloading %reg" << VirtReg << " into "
-               << TRI->getName(PhysReg) << "\n");
-
-  // Add move instruction(s)
-  TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI);
-  ++NumLoads;    // Update statistics
-
-  MF->getRegInfo().setPhysRegUsed(PhysReg);
-  MI->getOperand(OpNum).setReg(PhysReg);  // Assign the input register
-  getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
-
-  if (!ReloadedRegs.insert(PhysReg)) {
-    std::string msg;
-    raw_string_ostream Msg(msg);
-    Msg << "Ran out of registers during register allocation!";
-    if (MI->isInlineAsm()) {
-      Msg << "\nPlease check your inline asm statement for invalid "
-           << "constraints:\n";
-      MI->print(Msg, TM);
-    }
-    report_fatal_error(Msg.str());
-  }
-  for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
-       *SubRegs; ++SubRegs) {
-    if (ReloadedRegs.insert(*SubRegs)) continue;
-
-    std::string msg;
-    raw_string_ostream Msg(msg);
-    Msg << "Ran out of registers during register allocation!";
-    if (MI->isInlineAsm()) {
-      Msg << "\nPlease check your inline asm statement for invalid "
-           << "constraints:\n";
-      MI->print(Msg, TM);
+  // This is a disabled register, disable all aliases.
+  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
+       unsigned Alias = *AS; ++AS) {
+    switch (unsigned VirtReg = PhysRegState[Alias]) {
+    case regDisabled:
+    case regFree:
+      break;
+    case regReserved:
+      // is a super register already reserved?
+      if (TRI->isSuperRegister(PhysReg, Alias))
+        return;
+      break;
+    default:
+      spillVirtReg(MBB, MI, VirtReg, true);
+      break;
     }
-    report_fatal_error(Msg.str());
+    PhysRegState[Alias] = regDisabled;
+    MF->getRegInfo().setPhysRegUsed(Alias);
   }
-
-  return MI;
+  PhysRegState[PhysReg] = regReserved;
+  MF->getRegInfo().setPhysRegUsed(PhysReg);
 }
 
-/// isReadModWriteImplicitKill - True if this is an implicit kill for a
-/// read/mod/write register, i.e. update partial register.
-static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) {
-  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-    MachineOperand &MO = MI->getOperand(i);
-    if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
-        MO.isDef() && !MO.isDead())
-      return true;
-  }
-  return false;
-}
-
-/// isReadModWriteImplicitDef - True if this is an implicit def for a
-/// read/mod/write register, i.e. update partial register.
-static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) {
-  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-    MachineOperand &MO = MI->getOperand(i);
-    if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
-        !MO.isDef() && MO.isKill())
-      return true;
-  }
-  return false;
+// setPhysReg - Change MO the refer the PhysReg, considering subregs.
+void RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) {
+  if (unsigned Idx = MO.getSubReg()) {
+    MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0);
+    MO.setSubReg(0);
+  } else
+    MO.setReg(PhysReg);
 }
 
 void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
-  // loop over each instruction
-  MachineBasicBlock::iterator MII = MBB.begin();
+  DEBUG(dbgs() << "\nBB#" << MBB.getNumber() << ", "<< MBB.getName() << "\n");
 
-  DEBUG({
-      const BasicBlock *LBB = MBB.getBasicBlock();
-      if (LBB)
-        dbgs() << "\nStarting RegAlloc of BB: " << LBB->getName();
-    });
+  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
+  assert(Virt2PhysMap.empty() && "Mapping not cleared form last block?");
+  PhysRegDirty.reset();
 
-  // Add live-in registers as active.
+  MachineBasicBlock::iterator MII = MBB.begin();
+
+  // Add live-in registers as live.
   for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
-         E = MBB.livein_end(); I != E; ++I) {
-    unsigned Reg = *I;
-    MF->getRegInfo().setPhysRegUsed(Reg);
-    PhysRegsUsed[Reg] = 0;            // It is free and reserved now
-    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
-         *SubRegs; ++SubRegs) {
-      if (PhysRegsUsed[*SubRegs] == -2) continue;
-      PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
-      MF->getRegInfo().setPhysRegUsed(*SubRegs);
-    }
-  }
+         E = MBB.livein_end(); I != E; ++I)
+    reservePhysReg(MBB, MII, *I);
+
+  SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs;
 
   // Otherwise, sequentially allocate each instruction in the MBB.
   while (MII != MBB.end()) {
     MachineInstr *MI = MII++;
     const TargetInstrDesc &TID = MI->getDesc();
     DEBUG({
-        dbgs() << "\nStarting RegAlloc of: " << *MI;
-        dbgs() << "  Regs have values: ";
-        for (unsigned i = 0; i != TRI->getNumRegs(); ++i)
-          if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
-            dbgs() << "[" << TRI->getName(i)
-                   << ",%reg" << PhysRegsUsed[i] << "] ";
+        dbgs() << "\nStarting RegAlloc of: " << *MI << "Working set:";
+        for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
+          if (PhysRegState[Reg] == regDisabled) continue;
+          dbgs() << " " << TRI->getName(Reg);
+          switch(PhysRegState[Reg]) {
+          case regFree:
+            break;
+          case regReserved:
+            dbgs() << "(resv)";
+            break;
+          default:
+            dbgs() << "=%reg" << PhysRegState[Reg];
+            if (PhysRegDirty.test(Reg))
+              dbgs() << "*";
+            assert(Virt2PhysMap.lookup(PhysRegState[Reg]) == Reg &&
+                   "Bad inverse map");
+            break;
+          }
+        }
         dbgs() << '\n';
+        // Check that Virt2PhysMap is the inverse.
+        for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(),
+             e = Virt2P