projects / oota-llvm.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Convert more assert(0)+abort() -> LLVM_UNREACHABLE,
[oota-llvm.git] / lib / CodeGen / LiveIntervalAnalysis.cpp
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 66bcf611679ae619043ebab3ccdbdefaa2fa4dd3..6abe465cb1b53f989257a83b77d91e6be586cda7 100644 (file)
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -23,6 +23,7 @@
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
@@ -30,11 +31,17 @@
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include <algorithm>
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include <algorithm>
+#include <limits>
 #include <cmath>
 using namespace llvm;
 
 #include <cmath>
 using namespace llvm;
 
@@ -49,8 +56,10 @@ static cl::opt<int> SplitLimit("split-limit",
 
 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
 
 
 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
 
+static cl::opt<bool> EnableFastSpilling("fast-spill",
+                                        cl::init(false), cl::Hidden);
+
 STATISTIC(numIntervals, "Number of original intervals");
 STATISTIC(numIntervals, "Number of original intervals");
-STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
 STATISTIC(numFolds    , "Number of loads/stores folded into instructions");
 STATISTIC(numSplits   , "Number of intervals split");
 
 STATISTIC(numFolds    , "Number of loads/stores folded into instructions");
 STATISTIC(numSplits   , "Number of intervals split");
 
@@ -64,16 +73,29 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LiveVariables>();
   AU.addPreservedID(MachineLoopInfoID);
   AU.addPreservedID(MachineDominatorsID);
   AU.addRequired<LiveVariables>();
   AU.addPreservedID(MachineLoopInfoID);
   AU.addPreservedID(MachineDominatorsID);
+  
+  if (!StrongPHIElim) {
+    AU.addPreservedID(PHIEliminationID);
+    AU.addRequiredID(PHIEliminationID);
+  }
+  
   AU.addRequiredID(TwoAddressInstructionPassID);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void LiveIntervals::releaseMemory() {
   AU.addRequiredID(TwoAddressInstructionPassID);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void LiveIntervals::releaseMemory() {
+  // Free the live intervals themselves.
+  for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
+       E = r2iMap_.end(); I != E; ++I)
+    delete I->second;
+  
   MBB2IdxMap.clear();
   Idx2MBBMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
   r2iMap_.clear();
   MBB2IdxMap.clear();
   Idx2MBBMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
   r2iMap_.clear();
+  terminatorGaps.clear();
+
   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
   VNInfoAllocator.Reset();
   while (!ClonedMIs.empty()) {
   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
   VNInfoAllocator.Reset();
   while (!ClonedMIs.empty()) {
@@ -83,6 +105,120 @@ void LiveIntervals::releaseMemory() {
   }
 }
 
   }
 }
 
+/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
+/// there is one implicit_def for each use. Add isUndef marker to
+/// implicit_def defs and their uses.
+void LiveIntervals::processImplicitDefs() {
+  SmallSet<unsigned, 8> ImpDefRegs;
+  SmallVector<MachineInstr*, 8> ImpDefMIs;
+  MachineBasicBlock *Entry = mf_->begin();
+  SmallPtrSet<MachineBasicBlock*,16> Visited;
+  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
+         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
+       DFI != E; ++DFI) {
+    MachineBasicBlock *MBB = *DFI;
+    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
+         I != E; ) {
+      MachineInstr *MI = &*I;
+      ++I;
+      if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+        unsigned Reg = MI->getOperand(0).getReg();
+        MI->getOperand(0).setIsUndef();
+        ImpDefRegs.insert(Reg);
+        ImpDefMIs.push_back(MI);
+        continue;
+      }
+
+      bool ChangedToImpDef = false;
+      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+        MachineOperand& MO = MI->getOperand(i);
+        if (!MO.isReg() || !MO.isUse())
+          continue;
+        unsigned Reg = MO.getReg();
+        if (!Reg)
+          continue;
+        if (!ImpDefRegs.count(Reg))
+          continue;
+        // Use is a copy, just turn it into an implicit_def.
+        unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+        if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+            Reg == SrcReg) {
+          bool isKill = MO.isKill();
+          MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
+          for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
+            MI->RemoveOperand(j);
+          if (isKill)
+            ImpDefRegs.erase(Reg);
+          ChangedToImpDef = true;
+          break;
+        }
+
+        MO.setIsUndef();
+        if (MO.isKill() || MI->isRegTiedToDefOperand(i))
+          ImpDefRegs.erase(Reg);
+      }
+
+      if (ChangedToImpDef) {
+        // Backtrack to process this new implicit_def.
+        --I;
+      } else {
+        for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
+          MachineOperand& MO = MI->getOperand(i);
+          if (!MO.isReg() || !MO.isDef())
+            continue;
+          ImpDefRegs.erase(MO.getReg());
+        }
+      }
+    }
+
+    // Any outstanding liveout implicit_def's?
+    for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
+      MachineInstr *MI = ImpDefMIs[i];
+      unsigned Reg = MI->getOperand(0).getReg();
+      if (TargetRegisterInfo::isPhysicalRegister(Reg))
+        // Physical registers are not liveout (yet).
+        continue;
+      if (!ImpDefRegs.count(Reg))
+        continue;
+
+      // If there are multiple defs of the same register and at least one
+      // is not an implicit_def, do not insert implicit_def's before the
+      // uses.
+      bool Skip = false;
+      for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
+             DE = mri_->def_end(); DI != DE; ++DI) {
+        if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
+          Skip = true;
+          break;
+        }
+      }
+      if (Skip)
+        continue;
+
+      for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
+             UE = mri_->use_end(); UI != UE; ) {
+        MachineOperand &RMO = UI.getOperand();
+        MachineInstr *RMI = &*UI;
+        ++UI;
+        MachineBasicBlock *RMBB = RMI->getParent();
+        if (RMBB == MBB)
+          continue;
+        const TargetRegisterClass* RC = mri_->getRegClass(Reg);
+        unsigned NewVReg = mri_->createVirtualRegister(RC);
+        MachineInstrBuilder MIB =
+          BuildMI(*RMBB, RMI, RMI->getDebugLoc(),
+                  tii_->get(TargetInstrInfo::IMPLICIT_DEF), NewVReg);
+        (*MIB).getOperand(0).setIsUndef();
+        RMO.setReg(NewVReg);
+        RMO.setIsUndef();
+        RMO.setIsKill();
+      }
+    }
+    ImpDefRegs.clear();
+    ImpDefMIs.clear();
+  }
+}
+
 void LiveIntervals::computeNumbering() {
   Index2MiMap OldI2MI = i2miMap_;
   std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
 void LiveIntervals::computeNumbering() {
   Index2MiMap OldI2MI = i2miMap_;
   std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
@@ -91,6 +227,7 @@ void LiveIntervals::computeNumbering() {
   MBB2IdxMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
   MBB2IdxMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
+  terminatorGaps.clear();
   
   FunctionSize = 0;
   
   
   FunctionSize = 0;
   
@@ -109,27 +246,60 @@ void LiveIntervals::computeNumbering() {
 
     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
          I != E; ++I) {
 
     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
          I != E; ++I) {
+      
+      if (I == MBB->getFirstTerminator()) {
+        // Leave a gap for before terminators, this is where we will point
+        // PHI kills.
+        bool inserted =
+          terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+        assert(inserted && 
+               "Multiple 'first' terminators encountered during numbering.");
+        inserted = inserted; // Avoid compiler warning if assertions turned off.
+        i2miMap_.push_back(0);
+
+        MIIndex += InstrSlots::NUM;
+      }
+
       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
       assert(inserted && "multiple MachineInstr -> index mappings");
       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
       assert(inserted && "multiple MachineInstr -> index mappings");
+      inserted = true;
       i2miMap_.push_back(I);
       MIIndex += InstrSlots::NUM;
       FunctionSize++;
       
       i2miMap_.push_back(I);
       MIIndex += InstrSlots::NUM;
       FunctionSize++;
       
-      // Insert an empty slot after every instruction.
-      MIIndex += InstrSlots::NUM;
+      // Insert max(1, numdefs) empty slots after every instruction.
+      unsigned Slots = I->getDesc().getNumDefs();
+      if (Slots == 0)
+        Slots = 1;
+      MIIndex += InstrSlots::NUM * Slots;
+      while (Slots--)
+        i2miMap_.push_back(0);
+    }
+  
+    if (MBB->getFirstTerminator() == MBB->end()) {
+      // Leave a gap for before terminators, this is where we will point
+      // PHI kills.
+      bool inserted =
+        terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+      assert(inserted && 
+             "Multiple 'first' terminators encountered during numbering.");
+      inserted = inserted; // Avoid compiler warning if assertions turned off.
       i2miMap_.push_back(0);
       i2miMap_.push_back(0);
+ 
+      MIIndex += InstrSlots::NUM;
     }
     
     // Set the MBB2IdxMap entry for this MBB.
     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
     Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
   }
     }
     
     // Set the MBB2IdxMap entry for this MBB.
     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
     Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
   }
+
   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
   
   if (!OldI2MI.empty())
     for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
   
   if (!OldI2MI.empty())
     for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
-      for (LiveInterval::iterator LI = OI->second.begin(),
-           LE = OI->second.end(); LI != LE; ++LI) {
+      for (LiveInterval::iterator LI = OI->second->begin(),
+           LE = OI->second->end(); LI != LE; ++LI) {
         
         // Remap the start index of the live range to the corresponding new
         // number, or our best guess at what it _should_ correspond to if the
         
         // Remap the start index of the live range to the corresponding new
         // number, or our best guess at what it _should_ correspond to if the
@@ -172,14 +342,14 @@ void LiveIntervals::computeNumbering() {
         }
       }
       
         }
       }
       
-      for (LiveInterval::vni_iterator VNI = OI->second.vni_begin(),
-           VNE = OI->second.vni_end(); VNI != VNE; ++VNI) { 
+      for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
+           VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 
         VNInfo* vni = *VNI;
         
         // Remap the VNInfo def index, which works the same as the
         // start indices above. VN's with special sentinel defs
         // don't need to be remapped.
         VNInfo* vni = *VNI;
         
         // Remap the VNInfo def index, which works the same as the
         // start indices above. VN's with special sentinel defs
         // don't need to be remapped.
-        if (vni->def != ~0U && vni->def != ~1U) {
+        if (vni->isDefAccurate() && !vni->isUnused()) {
           unsigned index = vni->def / InstrSlots::NUM;
           unsigned offset = vni->def % InstrSlots::NUM;
           if (offset == InstrSlots::LOAD) {
           unsigned index = vni->def / InstrSlots::NUM;
           unsigned offset = vni->def % InstrSlots::NUM;
           if (offset == InstrSlots::LOAD) {
@@ -198,18 +368,31 @@ void LiveIntervals::computeNumbering() {
         // Remap the VNInfo kill indices, which works the same as
         // the end indices above.
         for (size_t i = 0; i < vni->kills.size(); ++i) {
         // Remap the VNInfo kill indices, which works the same as
         // the end indices above.
         for (size_t i = 0; i < vni->kills.size(); ++i) {
-          // PHI kills don't need to be remapped.
-          if (!vni->kills[i]) continue;
-          
-          unsigned index = (vni->kills[i]-1) / InstrSlots::NUM;
-          unsigned offset = vni->kills[i] % InstrSlots::NUM;
-          if (offset == InstrSlots::STORE) {
-            std::vector<IdxMBBPair>::const_iterator I =
+          unsigned killIdx = vni->kills[i].killIdx;
+
+          unsigned index = (killIdx - 1) / InstrSlots::NUM;
+          unsigned offset = killIdx % InstrSlots::NUM;
+
+          if (offset == InstrSlots::LOAD) {
+            assert("Value killed at a load slot.");
+            /*std::vector<IdxMBBPair>::const_iterator I =
              std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
             --I;
 
              std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
             --I;
 
-            vni->kills[i] = getMBBEndIdx(I->second);
+            vni->kills[i] = getMBBEndIdx(I->second);*/
           } else {
           } else {
+            if (vni->kills[i].isPHIKill) {
+              std::vector<IdxMBBPair>::const_iterator I =
+                std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
+              --I;
+              vni->kills[i].killIdx = terminatorGaps[I->second];  
+            } else {
+              assert(OldI2MI[index] != 0 &&
+                     "Kill refers to instruction not present in index maps.");
+              vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
+            }
+           
+            /*
             unsigned idx = index;
             while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
             
             unsigned idx = index;
             while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
             
@@ -218,12 +401,63 @@ void LiveIntervals::computeNumbering() {
                               (idx == index ? offset : 0);
             else
               vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
                               (idx == index ? offset : 0);
             else
               vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
+            */
           }
         }
       }
     }
 }
 
           }
         }
       }
     }
 }
 
+void LiveIntervals::scaleNumbering(int factor) {
+  // Need to
+  //  * scale MBB begin and end points
+  //  * scale all ranges.
+  //  * Update VNI structures.
+  //  * Scale instruction numberings 
+
+  // Scale the MBB indices.
+  Idx2MBBMap.clear();
+  for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end();
+       MBB != MBBE; ++MBB) {
+    std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
+    mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor);
+    mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor);
+    Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 
+  }
+  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
+
+  // Scale terminator gaps.
+  for (DenseMap<MachineBasicBlock*, unsigned>::iterator
+       TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
+       TGI != TGE; ++TGI) {
+    terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
+  }
+
+  // Scale the intervals.
+  for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
+    LI->second->scaleNumbering(factor);
+  }
+
+  // Scale MachineInstrs.
+  Mi2IndexMap oldmi2iMap = mi2iMap_;
+  unsigned highestSlot = 0;
+  for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
+       MI != ME; ++MI) {
+    unsigned newSlot = InstrSlots::scale(MI->second, factor);
+    mi2iMap_[MI->first] = newSlot;
+    highestSlot = std::max(highestSlot, newSlot); 
+  }
+
+  i2miMap_.clear();
+  i2miMap_.resize(highestSlot + 1);
+  for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
+       MI != ME; ++MI) {
+    i2miMap_[MI->second] = MI->first;
+  }
+
+}
+
+
 /// runOnMachineFunction - Register allocate the whole function
 ///
 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 /// runOnMachineFunction - Register allocate the whole function
 ///
 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
@@ -236,18 +470,12 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
   lv_ = &getAnalysis<LiveVariables>();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
 
   lv_ = &getAnalysis<LiveVariables>();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
 
+  processImplicitDefs();
   computeNumbering();
   computeIntervals();
 
   numIntervals += getNumIntervals();
 
   computeNumbering();
   computeIntervals();
 
   numIntervals += getNumIntervals();
 
-  DOUT << "********** INTERVALS **********\n";
-  for (iterator I = begin(), E = end(); I != E; ++I) {
-    I->second.print(DOUT, tri_);
-    DOUT << "\n";
-  }
-
-  numIntervalsAfter += getNumIntervals();
   DEBUG(dump());
   return true;
 }
   DEBUG(dump());
   return true;
 }
@@ -256,7 +484,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 void LiveIntervals::print(std::ostream &O, const Module* ) const {
   O << "********** INTERVALS **********\n";
   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 void LiveIntervals::print(std::ostream &O, const Module* ) const {
   O << "********** INTERVALS **********\n";
   for (const_iterator I = begin(), E = end(); I != E; ++I) {
-    I->second.print(O, tri_);
+    I->second->print(O, tri_);
     O << "\n";
   }
 
     O << "\n";
   }
 
@@ -286,13 +514,13 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
       if (index == end) break;
 
       MachineInstr *MI = getInstructionFromIndex(index);
       if (index == end) break;
 
       MachineInstr *MI = getInstructionFromIndex(index);
-      unsigned SrcReg, DstReg;
-      if (tii_->isMoveInstr(*MI, SrcReg, DstReg))
+      unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+      if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
         if (SrcReg == li.reg || DstReg == li.reg)
           continue;
       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
         MachineOperand& mop = MI->getOperand(i);
         if (SrcReg == li.reg || DstReg == li.reg)
           continue;
       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
         MachineOperand& mop = MI->getOperand(i);
-        if (!mop.isRegister())
+        if (!mop.isReg())
           continue;
         unsigned PhysReg = mop.getReg();
         if (PhysReg == 0 || PhysReg == li.reg)
           continue;
         unsigned PhysReg = mop.getReg();
         if (PhysReg == 0 || PhysReg == li.reg)
@@ -311,6 +539,47 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
   return false;
 }
 
   return false;
 }
 
+/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
+/// it can check use as well.
+bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
+                                            unsigned Reg, bool CheckUse,
+                                  SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
+  for (LiveInterval::Ranges::const_iterator
+         I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
+    for (unsigned index = getBaseIndex(I->start),
+           end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
+         index += InstrSlots::NUM) {
+      // Skip deleted instructions.
+      MachineInstr *MI = 0;
+      while (index != end) {
+        MI = getInstructionFromIndex(index);
+        if (MI)
+          break;
+        index += InstrSlots::NUM;
+      }
+      if (index == end) break;
+
+      if (JoinedCopies.count(MI))
+        continue;
+      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+        MachineOperand& MO = MI->getOperand(i);
+        if (!MO.isReg())
+          continue;
+        if (MO.isUse() && !CheckUse)
+          continue;
+        unsigned PhysReg = MO.getReg();
+        if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg))
+          continue;
+        if (tri_->isSubRegister(Reg, PhysReg))
+          return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+
 void LiveIntervals::printRegName(unsigned reg) const {
   if (TargetRegisterInfo::isPhysicalRegister(reg))
     cerr << tri_->getName(reg);
 void LiveIntervals::printRegName(unsigned reg) const {
   if (TargetRegisterInfo::isPhysicalRegister(reg))
     cerr << tri_->getName(reg);
@@ -338,14 +607,19 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
   if (interval.empty()) {
     // Get the Idx of the defining instructions.
     unsigned defIndex = getDefIndex(MIIdx);
   if (interval.empty()) {
     // Get the Idx of the defining instructions.
     unsigned defIndex = getDefIndex(MIIdx);
+    // Earlyclobbers move back one.
+    if (MO.isEarlyClobber())
+      defIndex = getUseIndex(MIIdx);
     VNInfo *ValNo;
     MachineInstr *CopyMI = NULL;
     VNInfo *ValNo;
     MachineInstr *CopyMI = NULL;
-    unsigned SrcReg, DstReg;
+    unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
     if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
         mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
     if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
         mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
-        tii_->isMoveInstr(*mi, SrcReg, DstReg))
+        mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
+        tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
       CopyMI = mi;
       CopyMI = mi;
-    ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
+    // Earlyclobbers move back one.
+    ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
 
     assert(ValNo->id == 0 && "First value in interval is not 0?");
 
 
     assert(ValNo->id == 0 && "First value in interval is not 0?");
 
@@ -364,12 +638,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       // If the kill happens after the definition, we have an intra-block
       // live range.
       if (killIdx > defIndex) {
       // If the kill happens after the definition, we have an intra-block
       // live range.
       if (killIdx > defIndex) {
-        assert(vi.AliveBlocks.none() &&
+        assert(vi.AliveBlocks.empty() &&
                "Shouldn't be alive across any blocks!");
         LiveRange LR(defIndex, killIdx, ValNo);
         interval.addRange(LR);
         DOUT << " +" << LR << "\n";
                "Shouldn't be alive across any blocks!");
         LiveRange LR(defIndex, killIdx, ValNo);
         interval.addRange(LR);
         DOUT << " +" << LR << "\n";
-        interval.addKill(ValNo, killIdx);
+        interval.addKill(ValNo, killIdx, false);
         return;
       }
     }
         return;
       }
     }
@@ -385,14 +659,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
     // Iterate over all of the blocks that the variable is completely
     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
     // live interval.
     // Iterate over all of the blocks that the variable is completely
     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
     // live interval.
-    for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
-      if (vi.AliveBlocks[i]) {
-        LiveRange LR(getMBBStartIdx(i),
-                     getMBBEndIdx(i)+1,  // MBB ends at -1.
-                     ValNo);
-        interval.addRange(LR);
-        DOUT << " +" << LR;
-      }
+    for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 
+             E = vi.AliveBlocks.end(); I != E; ++I) {
+      LiveRange LR(getMBBStartIdx(*I),
+                   getMBBEndIdx(*I)+1,  // MBB ends at -1.
+                   ValNo);
+      interval.addRange(LR);
+      DOUT << " +" << LR;
     }
 
     // Finally, this virtual register is live from the start of any killing
     }
 
     // Finally, this virtual register is live from the start of any killing
@@ -403,7 +676,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       LiveRange LR(getMBBStartIdx(Kill->getParent()),
                    killIdx, ValNo);
       interval.addRange(LR);
       LiveRange LR(getMBBStartIdx(Kill->getParent()),
                    killIdx, ValNo);
       interval.addRange(LR);
-      interval.addKill(ValNo, killIdx);
+      interval.addKill(ValNo, killIdx, false);
       DOUT << " +" << LR;
     }
 
       DOUT << " +" << LR;
     }
 
@@ -412,7 +685,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
     // must be due to phi elimination or two addr elimination.  If this is
     // the result of two address elimination, then the vreg is one of the
     // def-and-use register operand.
     // must be due to phi elimination or two addr elimination.  If this is
     // the result of two address elimination, then the vreg is one of the
     // def-and-use register operand.
-    if (mi->isRegReDefinedByTwoAddr(interval.reg, MOIdx)) {
+    if (mi->isRegTiedToUseOperand(MOIdx)) {
       // If this is a two-address definition, then we have already processed
       // the live range.  The only problem is that we didn't realize there
       // are actually two values in the live interval.  Because of this we
       // If this is a two-address definition, then we have already processed
       // the live range.  The only problem is that we didn't realize there
       // are actually two values in the live interval.  Because of this we
@@ -421,6 +694,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       assert(interval.containsOneValue());
       unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
       unsigned RedefIndex = getDefIndex(MIIdx);
       assert(interval.containsOneValue());
       unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
       unsigned RedefIndex = getDefIndex(MIIdx);
+      if (MO.isEarlyClobber())
+        RedefIndex = getUseIndex(MIIdx);
 
       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
       VNInfo *OldValNo = OldLR->valno;
 
       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
       VNInfo *OldValNo = OldLR->valno;
@@ -436,17 +711,21 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       // The new value number (#1) is defined by the instruction we claimed
       // defined value #0.
       VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy,
       // The new value number (#1) is defined by the instruction we claimed
       // defined value #0.
       VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy,
+                                            false, // update at *
                                             VNInfoAllocator);
                                             VNInfoAllocator);
-      
+      ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
+
       // Value#0 is now defined by the 2-addr instruction.
       OldValNo->def  = RedefIndex;
       OldValNo->copy = 0;
       // Value#0 is now defined by the 2-addr instruction.
       OldValNo->def  = RedefIndex;
       OldValNo->copy = 0;
+      if (MO.isEarlyClobber())
+        OldValNo->setHasRedefByEC(true);
       
       // Add the new live interval which replaces the range for the input copy.
       LiveRange LR(DefIndex, RedefIndex, ValNo);
       DOUT << " replace range with " << LR;
       interval.addRange(LR);
       
       // Add the new live interval which replaces the range for the input copy.
       LiveRange LR(DefIndex, RedefIndex, ValNo);
       DOUT << " replace range with " << LR;
       interval.addRange(LR);
-      interval.addKill(ValNo, RedefIndex);
+      interval.addKill(ValNo, RedefIndex, false);
 
       // If this redefinition is dead, we need to add a dummy unit live
       // range covering the def slot.
 
       // If this redefinition is dead, we need to add a dummy unit live
       // range covering the def slot.
@@ -471,16 +750,22 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
         DOUT << " Removing [" << Start << "," << End << "] from: ";
         interval.print(DOUT, tri_); DOUT << "\n";
         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
         DOUT << " Removing [" << Start << "," << End << "] from: ";
         interval.print(DOUT, tri_); DOUT << "\n";
-        interval.removeRange(Start, End);
-        VNI->hasPHIKill = true;
+        interval.removeRange(Start, End);        
+        assert(interval.ranges.size() == 1 &&
+               "newly discovered PHI interval has >1 ranges.");
+        MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
+        interval.addKill(VNI, terminatorGaps[killMBB], true);        
+        VNI->setHasPHIKill(true);
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
 
         // Replace the interval with one of a NEW value number.  Note that this
         // value number isn't actually defined by an instruction, weird huh? :)
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
 
         // Replace the interval with one of a NEW value number.  Note that this
         // value number isn't actually defined by an instruction, weird huh? :)
-        LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
+        LiveRange LR(Start, End,
+          interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator));
+        LR.valno->setIsPHIDef(true);
         DOUT << " replace range with " << LR;
         interval.addRange(LR);
         DOUT << " replace range with " << LR;
         interval.addRange(LR);
-        interval.addKill(LR.valno, End);
+        interval.addKill(LR.valno, End, false);
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
       }
 
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
       }
 
@@ -488,21 +773,24 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       // live until the end of the block.  We've already taken care of the
       // rest of the live range.
       unsigned defIndex = getDefIndex(MIIdx);
       // live until the end of the block.  We've already taken care of the
       // rest of the live range.
       unsigned defIndex = getDefIndex(MIIdx);
+      if (MO.isEarlyClobber())
+        defIndex = getUseIndex(MIIdx);
       
       VNInfo *ValNo;
       MachineInstr *CopyMI = NULL;
       
       VNInfo *ValNo;
       MachineInstr *CopyMI = NULL;
-      unsigned SrcReg, DstReg;
+      unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
       if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
           mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
       if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
           mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
-          tii_->isMoveInstr(*mi, SrcReg, DstReg))
+          mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
+          tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
         CopyMI = mi;
         CopyMI = mi;
-      ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
+      ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
       
       unsigned killIndex = getMBBEndIdx(mbb) + 1;
       LiveRange LR(defIndex, killIndex, ValNo);
       interval.addRange(LR);
       
       unsigned killIndex = getMBBEndIdx(mbb) + 1;
       LiveRange LR(defIndex, killIndex, ValNo);
       interval.addRange(LR);
-      interval.addKill(ValNo, killIndex);
-      ValNo->hasPHIKill = true;
+      interval.addKill(ValNo, terminatorGaps[mbb], true);
+      ValNo->setHasPHIKill(true);
       DOUT << " +" << LR;
     }
   }
       DOUT << " +" << LR;
     }
   }
@@ -522,6 +810,9 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 
   unsigned baseIndex = MIIdx;
   unsigned start = getDefIndex(baseIndex);
 
   unsigned baseIndex = MIIdx;
   unsigned start = getDefIndex(baseIndex);
+  // Earlyclobbers move back one.
+  if (MO.isEarlyClobber())
+    start = getUseIndex(MIIdx);
   unsigned end = start;
 
   // If it is not used after definition, it is considered dead at
   unsigned end = start;
 
   // If it is not used after definition, it is considered dead at
@@ -529,7 +820,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
   // [defSlot(def), defSlot(def)+1)
   if (MO.isDead()) {
     DOUT << " dead";
   // [defSlot(def), defSlot(def)+1)
   if (MO.isDead()) {
     DOUT << " dead";
-    end = getDefIndex(start) + 1;
+    end = start + 1;
     goto exit;
   }
 
     goto exit;
   }
 
@@ -545,14 +836,24 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
       DOUT << " killed";
       end = getUseIndex(baseIndex) + 1;
       goto exit;
       DOUT << " killed";
       end = getUseIndex(baseIndex) + 1;
       goto exit;
-    } else if (mi->modifiesRegister(interval.reg, tri_)) {
-      // Another instruction redefines the register before it is ever read.
-      // Then the register is essentially dead at the instruction that defines
-      // it. Hence its interval is:
-      // [defSlot(def), defSlot(def)+1)
-      DOUT << " dead";
-      end = getDefIndex(start) + 1;
-      goto exit;
+    } else {
+      int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
+      if (DefIdx != -1) {
+        if (mi->isRegTiedToUseOperand(DefIdx)) {
+          // Two-address instruction.
+          end = getDefIndex(baseIndex);
+          if (mi->getOperand(DefIdx).isEarlyClobber())
+            end = getUseIndex(baseIndex);
+        } else {
+          // Another instruction redefines the register before it is ever read.
+          // Then the register is essentially dead at the instruction that defines
+          // it. Hence its interval is:
+          // [defSlot(def), defSlot(def)+1)
+          DOUT << " dead";
+          end = start + 1;
+        }
+        goto exit;
+      }
     }
     
     baseIndex += InstrSlots::NUM;
     }
     
     baseIndex += InstrSlots::NUM;
@@ -560,20 +861,23 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
   
   // The only case we should have a dead physreg here without a killing or
   // instruction where we know it's dead is if it is live-in to the function
   
   // The only case we should have a dead physreg here without a killing or
   // instruction where we know it's dead is if it is live-in to the function
-  // and never used.
-  assert(!CopyMI && "physreg was not killed in defining block!");
-  end = getDefIndex(start) + 1;  // It's dead.
+  // and never used. Another possible case is the implicit use of the
+  // physical register has been deleted by two-address pass.
+  end = start + 1;
 
 exit:
   assert(start < end && "did not find end of interval?");
 
   // Already exists? Extend old live interval.
   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 
 exit:
   assert(start < end && "did not find end of interval?");
 
   // Already exists? Extend old live interval.
   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
-  VNInfo *ValNo = (OldLR != interval.end())
-    ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator);
+  bool Extend = OldLR != interval.end();
+  VNInfo *ValNo = Extend
+    ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
+  if (MO.isEarlyClobber() && Extend)
+    ValNo->setHasRedefByEC(true);
   LiveRange LR(start, end, ValNo);
   interval.addRange(LR);
   LiveRange LR(start, end, ValNo);
   interval.addRange(LR);
-  interval.addKill(LR.valno, end);
+  interval.addKill(LR.valno, end, false);
   DOUT << " +" << LR << '\n';
 }
 
   DOUT << " +" << LR << '\n';
 }
 
@@ -587,19 +891,20 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
                              getOrCreateInterval(MO.getReg()));
   else if (allocatableRegs_[MO.getReg()]) {
     MachineInstr *CopyMI = NULL;
                              getOrCreateInterval(MO.getReg()));
   else if (allocatableRegs_[MO.getReg()]) {
     MachineInstr *CopyMI = NULL;
-    unsigned SrcReg, DstReg;
+    unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
         MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
         MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
-        tii_->isMoveInstr(*MI, SrcReg, DstReg))
+        MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
+        tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
       CopyMI = MI;
       CopyMI = MI;
-    handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 
+    handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
                               getOrCreateInterval(MO.getReg()), CopyMI);
     // Def of a register also defines its sub-registers.
     for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
       // If MI also modifies the sub-register explicitly, avoid processing it
       // more than once. Do not pass in TRI here so it checks for exact match.
       if (!MI->modifiesRegister(*AS))
                               getOrCreateInterval(MO.getReg()), CopyMI);
     // Def of a register also defines its sub-registers.
     for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
       // If MI also modifies the sub-register explicitly, avoid processing it
       // more than once. Do not pass in TRI here so it checks for exact match.
       if (!MI->modifiesRegister(*AS))
-        handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 
+        handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
                                   getOrCreateInterval(*AS), 0);
   }
 }
                                   getOrCreateInterval(*AS), 0);
   }
 }
@@ -614,12 +919,18 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
   MachineBasicBlock::iterator mi = MBB->begin();
   unsigned baseIndex = MIIdx;
   unsigned start = baseIndex;
   MachineBasicBlock::iterator mi = MBB->begin();
   unsigned baseIndex = MIIdx;
   unsigned start = baseIndex;
-  unsigned end = start;
+  while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 
+         getInstructionFromIndex(baseIndex) == 0)
+    baseIndex += InstrSlots::NUM;
+  unsigned end = baseIndex;
+  bool SeenDefUse = false;
+  
   while (mi != MBB->end()) {
     if (mi->killsRegister(interval.reg, tri_)) {
       DOUT << " killed";
       end = getUseIndex(baseIndex) + 1;
   while (mi != MBB->end()) {
     if (mi->killsRegister(interval.reg, tri_)) {
       DOUT << " killed";
       end = getUseIndex(baseIndex) + 1;
-      goto exit;
+      SeenDefUse = true;
+      break;
     } else if (mi->modifiesRegister(interval.reg, tri_)) {
       // Another instruction redefines the register before it is ever read.
       // Then the register is essentially dead at the instruction that defines
     } else if (mi->modifiesRegister(interval.reg, tri_)) {
       // Another instruction redefines the register before it is ever read.
       // Then the register is essentially dead at the instruction that defines
@@ -627,19 +938,21 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
       // [defSlot(def), defSlot(def)+1)
       DOUT << " dead";
       end = getDefIndex(start) + 1;
       // [defSlot(def), defSlot(def)+1)
       DOUT << " dead";
       end = getDefIndex(start) + 1;
-      goto exit;
+      SeenDefUse = true;
+      break;
     }
 
     baseIndex += InstrSlots::NUM;
     }
 
     baseIndex += InstrSlots::NUM;
-    while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 
-           getInstructionFromIndex(baseIndex) == 0)
-      baseIndex += InstrSlots::NUM;
     ++mi;
     ++mi;
+    if (mi != MBB->end()) {
+      while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 
+             getInstructionFromIndex(baseIndex) == 0)
+        baseIndex += InstrSlots::NUM;
+    }
   }
 
   }
 
-exit:
   // Live-in register might not be used at all.
   // Live-in register might not be used at all.
-  if (end == MIIdx) {
+  if (!SeenDefUse) {
     if (isAlias) {
       DOUT << " dead";
       end = getDefIndex(MIIdx) + 1;
     if (isAlias) {
       DOUT << " dead";
       end = getDefIndex(MIIdx) + 1;
@@ -649,9 +962,13 @@ exit:
     }
   }
 
     }
   }
 
-  LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
+  VNInfo *vni =
+    interval.getNextValue(MBB->getNumber(), 0, false, VNInfoAllocator);
+  vni->setIsPHIDef(true);
+  LiveRange LR(start, end, vni);
+  
   interval.addRange(LR);
   interval.addRange(LR);
-  interval.addKill(LR.valno, end);
+  interval.addKill(LR.valno, end, false);
   DOUT << " +" << LR << '\n';
 }
 
   DOUT << " +" << LR << '\n';
 }
 
@@ -659,21 +976,17 @@ exit:
 /// registers. for some ordering of the machine instructions [1,N] a
 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 /// which a variable is live
 /// registers. for some ordering of the machine instructions [1,N] a
 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 /// which a variable is live
-void LiveIntervals::computeIntervals() {
+void LiveIntervals::computeIntervals() { 
+
   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
        << "********** Function: "
        << ((Value*)mf_->getFunction())->getName() << '\n';
   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
        << "********** Function: "
        << ((Value*)mf_->getFunction())->getName() << '\n';
-  // Track the index of the current machine instr.
-  unsigned MIIndex = 0;
-  
-  // Skip over empty initial indices.
-  while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
-         getInstructionFromIndex(MIIndex) == 0)
-    MIIndex += InstrSlots::NUM;
   
   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
        MBBI != E; ++MBBI) {
     MachineBasicBlock *MBB = MBBI;
   
   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
        MBBI != E; ++MBBI) {
     MachineBasicBlock *MBB = MBBI;
+    // Track the index of the current machine instr.
+    unsigned MIIndex = getMBBStartIdx(MBB);
     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 
     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 
     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
@@ -689,6 +1002,11 @@ void LiveIntervals::computeIntervals() {
                                true);
     }
     
                                true);
     }
     
+    // Skip over empty initial indices.
+    while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
+           getInstructionFromIndex(MIIndex) == 0)
+      MIIndex += InstrSlots::NUM;
+    
     for (; MI != miEnd; ++MI) {
       DOUT << MIIndex << "\t" << *MI;
 
     for (; MI != miEnd; ++MI) {
       DOUT << MIIndex << "\t" << *MI;
 
@@ -696,11 +1014,16 @@ void LiveIntervals::computeIntervals() {
       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
         MachineOperand &MO = MI->getOperand(i);
         // handle register defs - build intervals
       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
         MachineOperand &MO = MI->getOperand(i);
         // handle register defs - build intervals
-        if (MO.isRegister() && MO.getReg() && MO.isDef())
+        if (MO.isReg() && MO.getReg() && MO.isDef()) {
           handleRegisterDef(MBB, MI, MIIndex, MO, i);
           handleRegisterDef(MBB, MI, MIIndex, MO, i);
+        }
       }
       }
-      
-      MIIndex += InstrSlots::NUM;
+
+      // Skip over the empty slots after each instruction.
+      unsigned Slots = MI->getDesc().getNumDefs();
+      if (Slots == 0)
+        Slots = 1;
+      MIIndex += InstrSlots::NUM * Slots;
       
       // Skip over empty indices.
       while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
       
       // Skip over empty indices.
       while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
@@ -710,14 +1033,14 @@ void LiveIntervals::computeIntervals() {
   }
 }
 
   }
 }
 
-bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
+bool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End,
                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
   std::vector<IdxMBBPair>::const_iterator I =
                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
   std::vector<IdxMBBPair>::const_iterator I =
-    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
+    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
 
   bool ResVal = false;
   while (I != Idx2MBBMap.end()) {
 
   bool ResVal = false;
   while (I != Idx2MBBMap.end()) {
-    if (LR.end <= I->first)
+    if (I->first >= End)
       break;
     MBBs.push_back(I->second);
     ResVal = true;
       break;
     MBBs.push_back(I->second);
     ResVal = true;
@@ -726,11 +1049,38 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
   return ResVal;
 }
 
   return ResVal;
 }
 
+bool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End,
+                              SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
+  std::vector<IdxMBBPair>::const_iterator I =
+    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
+
+  bool ResVal = false;
+  while (I != Idx2MBBMap.end()) {
+    if (I->first > End)
+      break;
+    MachineBasicBlock *MBB = I->second;
+    if (getMBBEndIdx(MBB) > End)
+      break;
+    for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
+           SE = MBB->succ_end(); SI != SE; ++SI)
+      MBBs.push_back(*SI);
+    ResVal = true;
+    ++I;
+  }
+  return ResVal;
+}
+
+LiveInterval* LiveIntervals::createInterval(unsigned reg) {
+  float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
+  return new LiveInterval(reg, Weight);
+}
 
 
-LiveInterval LiveIntervals::createInterval(unsigned reg) {
-  float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
-                       HUGE_VALF : 0.0F;
-  return LiveInterval(reg, Weight);
+/// dupInterval - Duplicate a live interval. The caller is responsible for
+/// managing the allocated memory.
+LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
+  LiveInterval *NewLI = createInterval(li->reg);
+  NewLI->Copy(*li, mri_, getVNInfoAllocator());
+  return NewLI;
 }
 
 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
 }
 
 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
@@ -739,12 +1089,18 @@ unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
   if (!VNI->copy)
     return 0;
 
   if (!VNI->copy)
     return 0;
 
-  if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
-    return VNI->copy->getOperand(1).getReg();
-  if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+  if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
+    // If it's extracting out of a physical register, return the sub-register.
+    unsigned Reg = VNI->copy->getOperand(1).getReg();
+    if (TargetRegisterInfo::isPhysicalRegister(Reg))
+      Reg = tri_->getSubReg(Reg, VNI->copy->getOperand(2).getImm());
+    return Reg;
+  } else if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
+             VNI->copy->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
     return VNI->copy->getOperand(2).getReg();
     return VNI->copy->getOperand(2).getReg();
-  unsigned SrcReg, DstReg;
-  if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
+
+  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+  if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
     return SrcReg;
   assert(0 && "Unrecognized copy instruction!");
   return 0;
     return SrcReg;
   assert(0 && "Unrecognized copy instruction!");
   return 0;
@@ -762,11 +1118,15 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
   unsigned RegOp = 0;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
   unsigned RegOp = 0;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister() || !MO.isUse())
+    if (!MO.isReg() || !MO.isUse())
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0 || Reg == li.reg)
       continue;
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0 || Reg == li.reg)
       continue;
+    
+    if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
+        !allocatableRegs_[Reg])
+      continue;
     // FIXME: For now, only remat MI with at most one register operand.
     assert(!RegOp &&
            "Can't rematerialize instruction with multiple register operand!");
     // FIXME: For now, only remat MI with at most one register operand.
     assert(!RegOp &&
            "Can't rematerialize instruction with multiple register operand!");
@@ -792,6 +1152,7 @@ bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
 /// val# of the specified interval is re-materializable.
 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
                                        const VNInfo *ValNo, MachineInstr *MI,
 /// val# of the specified interval is re-materializable.
 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
                                        const VNInfo *ValNo, MachineInstr *MI,
+                                       SmallVectorImpl<LiveInterval*> &SpillIs,
                                        bool &isLoad) {
   if (DisableReMat)
     return false;
                                        bool &isLoad) {
   if (DisableReMat)
     return false;
@@ -828,8 +1189,8 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 
     // If the instruction accesses memory and the memory could be non-constant,
     // assume the instruction is not rematerializable.
 
     // If the instruction accesses memory and the memory could be non-constant,
     // assume the instruction is not rematerializable.
-    for (std::list<MachineMemOperand>::const_iterator I = MI->memoperands_begin(),
-         E = MI->memoperands_end(); I != E; ++I) {
+    for (std::list<MachineMemOperand>::const_iterator
+           I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){
       const MachineMemOperand &MMO = *I;
       if (MMO.isVolatile() || MMO.isStore())
         return false;
       const MachineMemOperand &MMO = *I;
       if (MMO.isVolatile() || MMO.isStore())
         return false;
@@ -864,7 +1225,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
         MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
                                           E = mri_->def_end();
 
         MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
                                           E = mri_->def_end();
 
-        // For the def, it should be the only def.
+        // For the def, it should be the only def of that register.
         if (MO.isDef() && (next(I) != E || IsLiveIn))
           return false;
 
         if (MO.isDef() && (next(I) != E || IsLiveIn))
           return false;
 
@@ -877,7 +1238,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
             else if (Reg != ImpUse)
               return false;
           }
             else if (Reg != ImpUse)
               return false;
           }
-          // For uses, there should be only one associate def.
+          // For the use, there should be only one associated def.
           if (I != E && (next(I) != E || IsLiveIn))
             return false;
         }
           if (I != E && (next(I) != E || IsLiveIn))
             return false;
         }
@@ -897,27 +1258,43 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
         return false;
     }
       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
         return false;
     }
+
+    // If a register operand of the re-materialized instruction is going to
+    // be spilled next, then it's not legal to re-materialize this instruction.
+    for (unsigned i = 0, e = SpillIs.size(); i != e; ++i)
+      if (ImpUse == SpillIs[i]->reg)
+        return false;
   }
   return true;
 }
 
   }
   return true;
 }
 
+/// isReMaterializable - Returns true if the definition MI of the specified
+/// val# of the specified interval is re-materializable.
+bool LiveIntervals::isReMaterializable(const LiveInterval &li,
+                                       const VNInfo *ValNo, MachineInstr *MI) {
+  SmallVector<LiveInterval*, 4> Dummy1;
+  bool Dummy2;
+  return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2);
+}
+
 /// isReMaterializable - Returns true if every definition of MI of every
 /// val# of the specified interval is re-materializable.
 /// isReMaterializable - Returns true if every definition of MI of every
 /// val# of the specified interval is re-materializable.
-bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
+bool LiveIntervals::isReMaterializable(const LiveInterval &li,
+                                       SmallVectorImpl<LiveInterval*> &SpillIs,
+                                       bool &isLoad) {
   isLoad = false;
   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
        i != e; ++i) {
     const VNInfo *VNI = *i;
   isLoad = false;
   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
        i != e; ++i) {
     const VNInfo *VNI = *i;
-    unsigned DefIdx = VNI->def;
-    if (DefIdx == ~1U)
+    if (VNI->isUnused())
       continue; // Dead val#.
     // Is the def for the val# rematerializable?
       continue; // Dead val#.
     // Is the def for the val# rematerializable?
-    if (DefIdx == ~0u)
+    if (!VNI->isDefAccurate())
       return false;
       return false;
-    MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
+    MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
     bool DefIsLoad = false;
     if (!ReMatDefMI ||
     bool DefIsLoad = false;
     if (!ReMatDefMI ||
-        !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
+        !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
       return false;
     isLoad |= DefIsLoad;
   }
       return false;
     isLoad |= DefIsLoad;
   }
@@ -931,8 +1308,6 @@ static bool FilterFoldedOps(MachineInstr *MI,
                             SmallVector<unsigned, 2> &Ops,
                             unsigned &MRInfo,
                             SmallVector<unsigned, 2> &FoldOps) {
                             SmallVector<unsigned, 2> &Ops,
                             unsigned &MRInfo,
                             SmallVector<unsigned, 2> &FoldOps) {
-  const TargetInstrDesc &TID = MI->getDesc();
-
   MRInfo = 0;
   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
     unsigned OpIdx = Ops[i];
   MRInfo = 0;
   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
     unsigned OpIdx = Ops[i];
@@ -944,8 +1319,7 @@ static bool FilterFoldedOps(MachineInstr *MI,
       MRInfo |= (unsigned)VirtRegMap::isMod;
     else {
       // Filter out two-address use operand(s).
       MRInfo |= (unsigned)VirtRegMap::isMod;
     else {
       // Filter out two-address use operand(s).
-      if (!MO.isImplicit() &&
-          TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
+      if (MI->isRegTiedToDefOperand(OpIdx)) {
         MRInfo = VirtRegMap::isModRef;
         continue;
       }
         MRInfo = VirtRegMap::isModRef;
         continue;
       }
@@ -1057,7 +1431,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
   // use operand. Make sure we rewrite that as well.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
   // use operand. Make sure we rewrite that as well.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isRegister())
+    if (!MO.isReg())
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
@@ -1084,15 +1458,13 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
                  SmallVector<int, 4> &ReMatIds,
                  const MachineLoopInfo *loopInfo,
                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
                  SmallVector<int, 4> &ReMatIds,
                  const MachineLoopInfo *loopInfo,
                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
-                 std::map<unsigned,unsigned> &MBBVRegsMap,
-                 std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
-  MachineBasicBlock *MBB = MI->getParent();
-  unsigned loopDepth = loopInfo->getLoopDepth(MBB);
+                 DenseMap<unsigned,unsigned> &MBBVRegsMap,
+                 std::vector<LiveInterval*> &NewLIs) {
   bool CanFold = false;
  RestartInstruction:
   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
     MachineOperand& mop = MI->getOperand(i);
   bool CanFold = false;
  RestartInstruction:
   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
     MachineOperand& mop = MI->getOperand(i);
-    if (!mop.isRegister())
+    if (!mop.isReg())
       continue;
     unsigned Reg = mop.getReg();
     unsigned RegI = Reg;
       continue;
     unsigned Reg = mop.getReg();
     unsigned RegI = Reg;
@@ -1144,7 +1516,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
     Ops.push_back(i);
     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
       const MachineOperand &MOj = MI->getOperand(j);
     Ops.push_back(i);
     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
       const MachineOperand &MOj = MI->getOperand(j);
-      if (!MOj.isRegister())
+      if (!MOj.isReg())
         continue;
       unsigned RegJ = MOj.getReg();
       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
         continue;
       unsigned RegJ = MOj.getReg();
       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
@@ -1168,10 +1540,16 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
       // the INSERT_SUBREG and both target registers that would overlap.
       HasUse = false;
 
       // the INSERT_SUBREG and both target registers that would overlap.
       HasUse = false;
 
-    // Update stack slot spill weight if we are splitting.
-    float Weight = getSpillWeight(HasDef, HasUse, loopDepth);
-      if (!TrySplit)
-      SSWeight += Weight;
+    // Create a new virtual register for the spill interval.
+    // Create the new register now so we can map the fold instruction
+    // to the new register so when it is unfolded we get the correct
+    // answer.
+    bool CreatedNewVReg = false;
+    if (NewVReg == 0) {
+      NewVReg = mri_->createVirtualRegister(rc);
+      vrm.grow();
+      CreatedNewVReg = true;
+    }
 
     if (!TryFold)
       CanFold = false;
 
     if (!TryFold)
       CanFold = false;
@@ -1180,16 +1558,21 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
       // optimal point to insert a load / store later.
       if (!TrySplit) {
         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
       // optimal point to insert a load / store later.
       if (!TrySplit) {
         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
-                                 Ops, FoldSS, FoldSlot, Reg)) {
+                                 Ops, FoldSS, FoldSlot, NewVReg)) {
           // Folding the load/store can completely change the instruction in
           // unpredictable ways, rescan it from the beginning.
           // Folding the load/store can completely change the instruction in
           // unpredictable ways, rescan it from the beginning.
+
+          if (FoldSS) {
+            // We need to give the new vreg the same stack slot as the
+            // spilled interval.
+            vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
+          }
+
           HasUse = false;
           HasDef = false;
           CanFold = false;
           HasUse = false;
           HasDef = false;
           CanFold = false;
-          if (isRemoved(MI)) {
-            SSWeight -= Weight;
+          if (isNotInMIMap(MI))
             break;
             break;
-          }
           goto RestartInstruction;
         }
       } else {
           goto RestartInstruction;
         }
       } else {
@@ -1198,13 +1581,6 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
       }
     }
 
       }
     }
 
-    // Create a new virtual register for the spill interval.
-    bool CreatedNewVReg = false;
-    if (NewVReg == 0) {
-      NewVReg = mri_->createVirtualRegister(rc);
-      vrm.grow();
-      CreatedNewVReg = true;
-    }
     mop.setReg(NewVReg);
     if (mop.isImplicit())
       rewriteImplicitOps(li, MI, NewVReg, vrm);
     mop.setReg(NewVReg);
     if (mop.isImplicit())
       rewriteImplicitOps(li, MI, NewVReg, vrm);
@@ -1248,7 +1624,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
     if (DefIsReMat && ImpUse)
       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
 
     if (DefIsReMat && ImpUse)
       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
 
-    // create a new register interval for this spill / remat.
+    // Create a new register interval for this spill / remat.
     LiveInterval &nI = getOrCreateInterval(NewVReg);
     if (CreatedNewVReg) {
       NewLIs.push_back(&nI);
     LiveInterval &nI = getOrCreateInterval(NewVReg);
     if (CreatedNewVReg) {
       NewLIs.push_back(&nI);
@@ -1260,7 +1636,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
     if (HasUse) {
       if (CreatedNewVReg) {
         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
     if (HasUse) {
       if (CreatedNewVReg) {
         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
-                     nI.getNextValue(~0U, 0, VNInfoAllocator));
+                     nI.getNextValue(0, 0, false, VNInfoAllocator));
         DOUT << " +" << LR;
         nI.addRange(LR);
       } else {
         DOUT << " +" << LR;
         nI.addRange(LR);
       } else {
@@ -1274,7 +1650,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
     }
     if (HasDef) {
       LiveRange LR(getDefIndex(index), getStoreIndex(index),
     }
     if (HasDef) {
       LiveRange LR(getDefIndex(index), getStoreIndex(index),
-                   nI.getNextValue(~0U, 0, VNInfoAllocator));
+                   nI.getNextValue(0, 0, false, VNInfoAllocator));
       DOUT << " +" << LR;
       nI.addRange(LR);
     }
       DOUT << " +" << LR;
       nI.addRange(LR);
     }
@@ -1290,7 +1666,10 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
                                    MachineBasicBlock *MBB, unsigned Idx) const {
   unsigned End = getMBBEndIdx(MBB);
   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
                                    MachineBasicBlock *MBB, unsigned Idx) const {
   unsigned End = getMBBEndIdx(MBB);
   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
-    unsigned KillIdx = VNI->kills[j];
+    if (VNI->kills[j].isPHIKill)
+      continue;
+
+    unsigned KillIdx = VNI->kills[j].killIdx;
     if (KillIdx > Idx && KillIdx < End)
       return true;
   }
     if (KillIdx > Idx && KillIdx < End)
       return true;
   }
@@ -1327,11 +1706,11 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
                     SmallVector<int, 4> &ReMatIds,
                     const MachineLoopInfo *loopInfo,
                     BitVector &SpillMBBs,
                     SmallVector<int, 4> &ReMatIds,
                     const MachineLoopInfo *loopInfo,
                     BitVector &SpillMBBs,
-                    std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
+                    DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
                     BitVector &RestoreMBBs,
                     BitVector &RestoreMBBs,
-                    std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
-                    std::map<unsigned,unsigned> &MBBVRegsMap,
-                    std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
+                    DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
+                    DenseMap<unsigned,unsigned> &MBBVRegsMap,
+                    std::vector<LiveInterval*> &NewLIs) {
   bool AllCanFold = true;
   unsigned NewVReg = 0;
   unsigned start = getBaseIndex(I->start);
   bool AllCanFold = true;
   unsigned NewVReg = 0;
   unsigned start = getBaseIndex(I->start);
@@ -1397,7 +1776,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
     unsigned MBBId = MBB->getNumber();
     unsigned ThisVReg = 0;
     if (TrySplit) {
     unsigned MBBId = MBB->getNumber();
     unsigned ThisVReg = 0;
     if (TrySplit) {
-      std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
+      DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
       if (NVI != MBBVRegsMap.end()) {
         ThisVReg = NVI->second;
         // One common case:
       if (NVI != MBBVRegsMap.end()) {
         ThisVReg = NVI->second;
         // One common case:
@@ -1433,7 +1812,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
-                         ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight);
+                         ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
     if (!HasDef && !HasUse)
       continue;
 
     if (!HasDef && !HasUse)
       continue;
 
@@ -1459,7 +1838,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
           if (VNI)
             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
         }
           if (VNI)
             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
         }
-        std::map<unsigned, std::vector<SRInfo> >::iterator SII =
+        DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
           SpillIdxes.find(MBBId);
         if (!HasKill) {
           if (SII == SpillIdxes.end()) {
           SpillIdxes.find(MBBId);
         if (!HasKill) {
           if (SII == SpillIdxes.end()) {
@@ -1492,14 +1871,14 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
     }
 
     if (HasUse) {
     }
 
     if (HasUse) {
-      std::map<unsigned, std::vector<SRInfo> >::iterator SII =
+      DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
         SpillIdxes.find(MBBId);
       if (SII != SpillIdxes.end() &&
           SII->second.back().vreg == NewVReg &&
           (int)index > SII->second.back().index)
         // Use(s) following the last def, it's not safe to fold the spill.
         SII->second.back().canFold = false;
         SpillIdxes.find(MBBId);
       if (SII != SpillIdxes.end() &&
           SII->second.back().vreg == NewVReg &&
           (int)index > SII->second.back().index)
         // Use(s) following the last def, it's not safe to fold the spill.
         SII->second.back().canFold = false;
-      std::map<unsigned, std::vector<SRInfo> >::iterator RII =
+      DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
         RestoreIdxes.find(MBBId);
       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
         // If we are splitting live intervals, only fold if it's the first
         RestoreIdxes.find(MBBId);
       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
         // If we are splitting live intervals, only fold if it's the first
@@ -1532,7 +1911,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
 
 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
                         BitVector &RestoreMBBs,
 
 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
                         BitVector &RestoreMBBs,
-                        std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
+                        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
   if (!RestoreMBBs[Id])
     return false;
   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
   if (!RestoreMBBs[Id])
     return false;
   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
@@ -1546,7 +1925,7 @@ bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
 
 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
                         BitVector &RestoreMBBs,
 
 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
                         BitVector &RestoreMBBs,
-                        std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
+                        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
   if (!RestoreMBBs[Id])
     return;
   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
   if (!RestoreMBBs[Id])
     return;
   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
@@ -1582,18 +1961,111 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
       NewLIs.push_back(&getOrCreateInterval(NewVReg));
       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = MI->getOperand(i);
       NewLIs.push_back(&getOrCreateInterval(NewVReg));
       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = MI->getOperand(i);
-        if (MO.isReg() && MO.getReg() == li.reg)
+        if (MO.isReg() && MO.getReg() == li.reg) {
           MO.setReg(NewVReg);
           MO.setReg(NewVReg);
+          MO.setIsUndef();
+        }
       }
     }
   }
 }
 
       }
     }
   }
 }
 
+std::vector<LiveInterval*> LiveIntervals::
+addIntervalsForSpillsFast(const LiveInterval &li,
+                          const MachineLoopInfo *loopInfo,
+                          VirtRegMap &vrm) {
+  unsigned slot = vrm.assignVirt2StackSlot(li.reg);
+
+  std::vector<LiveInterval*> added;
+
+  assert(li.weight != HUGE_VALF &&
+         "attempt to spill already spilled interval!");
+
+  DOUT << "\t\t\t\tadding intervals for spills for interval: ";
+  DEBUG(li.dump());
+  DOUT << '\n';
+
+  const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
+
+  MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg);
+  while (RI != mri_->reg_end()) {
+    MachineInstr* MI = &*RI;
+    
+    SmallVector<unsigned, 2> Indices;
+    bool HasUse = false;
+    bool HasDef = false;
+    
+    for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
+      MachineOperand& mop = MI->getOperand(i);
+      if (!mop.isReg() || mop.getReg() != li.reg) continue;
+      
+      HasUse |= MI->getOperand(i).isUse();
+      HasDef |= MI->getOperand(i).isDef();
+      
+      Indices.push_back(i);
+    }
+    
+    if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI),
+                              Indices, true, slot, li.reg)) {
+      unsigned NewVReg = mri_->createVirtualRegister(rc);
+      vrm.grow();
+      vrm.assignVirt2StackSlot(NewVReg, slot);
+      
+      // create a new register for this spill
+      LiveInterval &nI = getOrCreateInterval(NewVReg);
+
+      // the spill weight is now infinity as it
+      // cannot be spilled again
+      nI.weight = HUGE_VALF;
+      
+      // Rewrite register operands to use the new vreg.
+      for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
+           E = Indices.end(); I != E; ++I) {
+        MI->getOperand(*I).setReg(NewVReg);
+        
+        if (MI->getOperand(*I).isUse())
+          MI->getOperand(*I).setIsKill(true);
+      }
+      
+      // Fill in  the new live interval.
+      unsigned index = getInstructionIndex(MI);
+      if (HasUse) {
+        LiveRange LR(getLoadIndex(index), getUseIndex(index),
+                     nI.getNextValue(0, 0, false, getVNInfoAllocator()));
+        DOUT << " +" << LR;
+        nI.addRange(LR);
+        vrm.addRestorePoint(NewVReg, MI);
+      }
+      if (HasDef) {
+        LiveRange LR(getDefIndex(index), getStoreIndex(index),
+                     nI.getNextValue(0, 0, false, getVNInfoAllocator()));
+        DOUT << " +" << LR;
+        nI.addRange(LR);
+        vrm.addSpillPoint(NewVReg, true, MI);
+      }
+      
+      added.push_back(&nI);
+        
+      DOUT << "\t\t\t\tadded new interval: ";
+      DEBUG(nI.dump());
+      DOUT << '\n';
+    }
+    
+    
+    RI = mri_->reg_begin(li.reg);
+  }
+
+  return added;
+}
 
 std::vector<LiveInterval*> LiveIntervals::
 addIntervalsForSpills(const LiveInterval &li,
 
 std::vector<LiveInterval*> LiveIntervals::
 addIntervalsForSpills(const LiveInterval &li,
-                      const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
-                      float &SSWeight) {
+                      SmallVectorImpl<LiveInterval*> &SpillIs,
+                      const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
+  
+  if (EnableFastSpilling)
+    return addIntervalsForSpillsFast(li, loopInfo, vrm);
+  
   assert(li.weight != HUGE_VALF &&
          "attempt to spill already spilled interval!");
 
   assert(li.weight != HUGE_VALF &&
          "attempt to spill already spilled interval!");
 
@@ -1601,15 +2073,12 @@ addIntervalsForSpills(const LiveInterval &li,
   li.print(DOUT, tri_);
   DOUT << '\n';
 
   li.print(DOUT, tri_);
   DOUT << '\n';
 
-  // Spill slot weight.
-  SSWeight = 0.0f;
-
-  // Each bit specify whether it a spill is required in the MBB.
+  // Each bit specify whether a spill is required in the MBB.
   BitVector SpillMBBs(mf_->getNumBlockIDs());
   BitVector SpillMBBs(mf_->getNumBlockIDs());
-  std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
+  DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
   BitVector RestoreMBBs(mf_->getNumBlockIDs());
   BitVector RestoreMBBs(mf_->getNumBlockIDs());
-  std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
-  std::map<unsigned,unsigned> MBBVRegsMap;
+  DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
+  DenseMap<unsigned,unsigned> MBBVRegsMap;
   std::vector<LiveInterval*> NewLIs;
   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
 
   std::vector<LiveInterval*> NewLIs;
   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
 
@@ -1645,7 +2114,7 @@ addIntervalsForSpills(const LiveInterval &li,
     int LdSlot = 0;
     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
     bool isLoad = isLoadSS ||
     int LdSlot = 0;
     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
     bool isLoad = isLoadSS ||
-      (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
+      (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
     bool IsFirstRange = true;
     for (LiveInterval::Ranges::const_iterator
            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
     bool IsFirstRange = true;
     for (LiveInterval::Ranges::const_iterator
            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
@@ -1658,18 +2127,17 @@ addIntervalsForSpills(const LiveInterval &li,
                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                              false, vrm, rc, ReMatIds, loopInfo,
                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                              false, vrm, rc, ReMatIds, loopInfo,
                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
-                             MBBVRegsMap, NewLIs, SSWeight);
+                             MBBVRegsMap, NewLIs);
       } else {
         rewriteInstructionsForSpills(li, false, I, NULL, 0,
                              Slot, 0, false, false, false,
                              false, vrm, rc, ReMatIds, loopInfo,
                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
       } else {
         rewriteInstructionsForSpills(li, false, I, NULL, 0,
                              Slot, 0, false, false, false,
                              false, vrm, rc, ReMatIds, loopInfo,
                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
-                             MBBVRegsMap, NewLIs, SSWeight);
+                             MBBVRegsMap, NewLIs);
       }
       IsFirstRange = false;
     }
 
       }
       IsFirstRange = false;
     }
 
-    SSWeight = 0.0f;  // Already accounted for when split.
     handleSpilledImpDefs(li, vrm, rc, NewLIs);
     return NewLIs;
   }
     handleSpilledImpDefs(li, vrm, rc, NewLIs);
     return NewLIs;
   }
@@ -1684,14 +2152,13 @@ addIntervalsForSpills(const LiveInterval &li,
        i != e; ++i) {
     const VNInfo *VNI = *i;
     unsigned VN = VNI->id;
        i != e; ++i) {
     const VNInfo *VNI = *i;
     unsigned VN = VNI->id;
-    unsigned DefIdx = VNI->def;
-    if (DefIdx == ~1U)
+    if (VNI->isUnused())
       continue; // Dead val#.
     // Is the def for the val# rematerializable?
       continue; // Dead val#.
     // Is the def for the val# rematerializable?
-    MachineInstr *ReMatDefMI = (DefIdx == ~0u)
-      ? 0 : getInstructionFromIndex(DefIdx);
+    MachineInstr *ReMatDefMI = VNI->isDefAccurate()
+      ? getInstructionFromIndex(VNI->def) : 0;
     bool dummy;
     bool dummy;
-    if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
+    if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
       // Remember how to remat the def of this val#.
       ReMatOrigDefs[VN] = ReMatDefMI;
       // Original def may be modified so we have to make a copy here.
       // Remember how to remat the def of this val#.
       ReMatOrigDefs[VN] = ReMatDefMI;
       // Original def may be modified so we have to make a copy here.
@@ -1700,7 +2167,7 @@ addIntervalsForSpills(const LiveInterval &li,
       ReMatDefs[VN] = Clone;
 
       bool CanDelete = true;
       ReMatDefs[VN] = Clone;
 
       bool CanDelete = true;
-      if (VNI->hasPHIKill) {
+      if (VNI->hasPHIKill()) {
         // A kill is a phi node, not all of its uses can be rematerialized.
         // It must not be deleted.
         CanDelete = false;
         // A kill is a phi node, not all of its uses can be rematerialized.
         // It must not be deleted.
         CanDelete = false;
@@ -1718,8 +2185,15 @@ addIntervalsForSpills(const LiveInterval &li,
   }
 
   // One stack slot per live interval.
   }
 
   // One stack slot per live interval.
-  if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
-    Slot = vrm.assignVirt2StackSlot(li.reg);
+  if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
+    if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
+      Slot = vrm.assignVirt2StackSlot(li.reg);
+    
+    // This case only occurs when the prealloc splitter has already assigned
+    // a stack slot to this vreg.
+    else
+      Slot = vrm.getStackSlot(li.reg);
+  }
 
   // Create new intervals and rewrite defs and uses.
   for (LiveInterval::Ranges::const_iterator
 
   // Create new intervals and rewrite defs and uses.
   for (LiveInterval::Ranges::const_iterator
@@ -1731,12 +2205,12 @@ addIntervalsForSpills(const LiveInterval &li,
     int LdSlot = 0;
     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
     bool isLoad = isLoadSS ||
     int LdSlot = 0;
     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
     bool isLoad = isLoadSS ||
-      (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
+      (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                                CanDelete, vrm, rc, ReMatIds, loopInfo,
                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
                                CanDelete, vrm, rc, ReMatIds, loopInfo,
                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
-                               MBBVRegsMap, NewLIs, SSWeight);
+                               MBBVRegsMap, NewLIs);
   }
 
   // Insert spills / restores if we are splitting.
   }
 
   // Insert spills / restores if we are splitting.
@@ -1750,8 +2224,6 @@ addIntervalsForSpills(const LiveInterval &li,
   if (NeedStackSlot) {
     int Id = SpillMBBs.find_first();
     while (Id != -1) {
   if (NeedStackSlot) {
     int Id = SpillMBBs.find_first();
     while (Id != -1) {
-      MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
-      unsigned loopDepth = loopInfo->getLoopDepth(MBB);
       std::vector<SRInfo> &spills = SpillIdxes[Id];
       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
         int index = spills[i].index;
       std::vector<SRInfo> &spills = SpillIdxes[Id];
       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
         int index = spills[i].index;
@@ -1766,7 +2238,7 @@ addIntervalsForSpills(const LiveInterval &li,
           CanFold = true;
           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
             MachineOperand &MO = MI->getOperand(j);
           CanFold = true;
           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
             MachineOperand &MO = MI->getOperand(j);
-            if (!MO.isRegister() || MO.getReg() != VReg)
+            if (!MO.isReg() || MO.getReg() != VReg)
               continue;
 
             Ops.push_back(j);
               continue;
 
             Ops.push_back(j);
@@ -1789,7 +2261,7 @@ addIntervalsForSpills(const LiveInterval &li,
         if (CanFold && !Ops.empty()) {
           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
             Folded = true;
         if (CanFold && !Ops.empty()) {
           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
             Folded = true;
-            if (FoundUse > 0) {
+            if (FoundUse) {
               // Also folded uses, do not issue a load.
               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
               // Also folded uses, do not issue a load.
               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
@@ -1808,10 +2280,6 @@ addIntervalsForSpills(const LiveInterval &li,
           if (isKill)
             AddedKill.insert(&nI);
         }
           if (isKill)
             AddedKill.insert(&nI);
         }
-
-        // Update spill slot weight.
-        if (!isReMat)
-          SSWeight += getSpillWeight(true, false, loopDepth);
       }
       Id = SpillMBBs.find_next(Id);
     }
       }
       Id = SpillMBBs.find_next(Id);
     }
@@ -1819,9 +2287,6 @@ addIntervalsForSpills(const LiveInterval &li,
 
   int Id = RestoreMBBs.find_first();
   while (Id != -1) {
 
   int Id = RestoreMBBs.find_first();
   while (Id != -1) {
-    MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
-    unsigned loopDepth = loopInfo->getLoopDepth(MBB);
-
     std::vector<SRInfo> &restores = RestoreIdxes[Id];
     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
       int index = restores[i].index;
     std::vector<SRInfo> &restores = RestoreIdxes[Id];
     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
       int index = restores[i].index;
@@ -1837,7 +2302,7 @@ addIntervalsForSpills(const LiveInterval &li,
         CanFold = true;
         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
           MachineOperand &MO = MI->getOperand(j);
         CanFold = true;
         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
           MachineOperand &MO = MI->getOperand(j);
-          if (!MO.isRegister() || MO.getReg() != VReg)
+          if (!MO.isReg() || MO.getReg() != VReg)
             continue;
 
           if (MO.isDef()) {
             continue;
 
           if (MO.isDef()) {
@@ -1860,18 +2325,20 @@ addIntervalsForSpills(const LiveInterval &li,
           int LdSlot = 0;
           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
           // If the rematerializable def is a load, also try to fold it.
           int LdSlot = 0;
           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
           // If the rematerializable def is a load, also try to fold it.
-          if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
+          if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
                                           Ops, isLoadSS, LdSlot, VReg);
             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
                                           Ops, isLoadSS, LdSlot, VReg);
-          unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
-          if (ImpUse) {
-            // Re-matting an instruction with virtual register use. Add the
-            // register as an implicit use on the use MI and update the register
-            // interval's spill weight to HUGE_VALF to prevent it from being
-            // spilled.
-            LiveInterval &ImpLi = getInterval(ImpUse);
-            ImpLi.weight = HUGE_VALF;
-            MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
+          if (!Folded) {
+            unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
+            if (ImpUse) {
+              // Re-matting an instruction with virtual register use. Add the
+              // register as an implicit use on the use MI and update the register
+              // interval's spill weight to HUGE_VALF to prevent it from being
+              // spilled.
+              LiveInterval &ImpLi = getInterval(ImpUse);
+              ImpLi.weight = HUGE_VALF;
+              MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
+            }
           }
         }
       }
           }
         }
       }
@@ -1881,10 +2348,6 @@ addIntervalsForSpills(const LiveInterval &li,
         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
       else
         vrm.addRestorePoint(VReg, MI);
         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
       else
         vrm.addRestorePoint(VReg, MI);
-
-      // Update spill slot weight.
-      if (!isReMat)
-        SSWeight += getSpillWeight(false, true, loopDepth);
     }
     Id = RestoreMBBs.find_next(Id);
   }
     }
     Id = RestoreMBBs.find_next(Id);
   }
@@ -1902,8 +2365,7 @@ addIntervalsForSpills(const LiveInterval &li,
         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
         assert(UseIdx != -1);
         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
         assert(UseIdx != -1);
-        if (LastUse->getOperand(UseIdx).isImplicit() ||
-            LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
+        if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
           LastUse->getOperand(UseIdx).setIsKill();
           vrm.addKillPoint(LI->reg, LastUseIdx);
         }
           LastUse->getOperand(UseIdx).setIsKill();
           vrm.addKillPoint(LI->reg, LastUseIdx);
         }
@@ -1958,8 +2420,9 @@ unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
 }
 
 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
 }
 
 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
-/// around all defs and uses of the specified interval.
-void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
+/// around all defs and uses of the specified interval. Return true if it
+/// was able to cut its interval.
+bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
                                             unsigned PhysReg, VirtRegMap &vrm) {
   unsigned SpillReg = getRepresentativeReg(PhysReg);
 
                                             unsigned PhysReg, VirtRegMap &vrm) {
   unsigned SpillReg = getRepresentativeReg(PhysReg);
 
@@ -1967,9 +2430,10 @@ void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
     // If there are registers which alias PhysReg, but which are not a
     // sub-register of the chosen representative super register. Assert
     // since we can't handle it yet.
     // If there are registers which alias PhysReg, but which are not a
     // sub-register of the chosen representative super register. Assert
     // since we can't handle it yet.
-    assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
+    assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
            tri_->isSuperRegister(*AS, SpillReg));
 
            tri_->isSuperRegister(*AS, SpillReg));
 
+  bool Cut = false;
   LiveInterval &pli = getInterval(SpillReg);
   SmallPtrSet<MachineInstr*, 8> SeenMIs;
   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
   LiveInterval &pli = getInterval(SpillReg);
   SmallPtrSet<MachineInstr*, 8> SeenMIs;
   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
@@ -1982,7 +2446,22 @@ void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
     unsigned Index = getInstructionIndex(MI);
     if (pli.liveAt(Index)) {
       vrm.addEmergencySpill(SpillReg, MI);
     unsigned Index = getInstructionIndex(MI);
     if (pli.liveAt(Index)) {
       vrm.addEmergencySpill(SpillReg, MI);
-      pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
+      unsigned StartIdx = getLoadIndex(Index);
+      unsigned EndIdx = getStoreIndex(Index)+1;
+      if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
+        pli.removeRange(StartIdx, EndIdx);
+        Cut = true;
+      } else {
+        std::string msg;
+        raw_string_ostream Msg(msg);
+        Msg << "Ran out of registers during register allocation!";
+        if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
+          Msg << "\nPlease check your inline asm statement for invalid "
+               << "constraints:\n";
+          MI->print(Msg, tm_);
+        }
+        llvm_report_error(Msg.str());
+      }
       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
         if (!hasInterval(*AS))
           continue;
       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
         if (!hasInterval(*AS))
           continue;
@@ -1992,16 +2471,18 @@ void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
       }
     }
   }
       }
     }
   }
+  return Cut;
 }
 
 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
 }
 
 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
-                                                   MachineInstr* startInst) {
+                                                  MachineInstr* startInst) {
   LiveInterval& Interval = getOrCreateInterval(reg);
   VNInfo* VN = Interval.getNextValue(
             getInstructionIndex(startInst) + InstrSlots::DEF,
   LiveInterval& Interval = getOrCreateInterval(reg);
   VNInfo* VN = Interval.getNextValue(
             getInstructionIndex(startInst) + InstrSlots::DEF,
-            startInst, getVNInfoAllocator());
-  VN->hasPHIKill = true;
-  VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
+            startInst, true, getVNInfoAllocator());
+  VN->setHasPHIKill(true);
+  VN->kills.push_back(
+    VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
                getMBBEndIdx(startInst->getParent()) + 1, VN);
   Interval.addRange(LR);
   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
                getMBBEndIdx(startInst->getParent()) + 1, VN);
   Interval.addRange(LR);
C/C++ LLVM-based compilers that forbids OOTA behaviors