diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index a02a4a6..8d632cb 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -19,6 +19,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallSet.h"
@@ -28,11 +29,6 @@
 #include <algorithm>
 using namespace llvm;
 
-// Print a LiveIndex to a raw_ostream.
-void LiveIndex::print(raw_ostream &os) const {
-  os << (index & ~PHI_BIT);
-}
-
 // An example for liveAt():
 //
 // this = [1,4), liveAt(0) will return false. The instruction defining this
@@ -40,7 +36,7 @@
 // variable it represents. This is because slot 1 is used (def slot) and spans
 // up to slot 3 (store slot).
 //
-bool LiveInterval::liveAt(LiveIndex I) const {
+bool LiveInterval::liveAt(SlotIndex I) const {
   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
 
   if (r == ranges.begin())
@@ -53,7 +49,7 @@
 // liveBeforeAndAt - Check if the interval is live at the index and the index
 // just before it. If index is liveAt, check if it starts a new live range.
 // If it does, then check if the previous live range ends at index-1.
-bool LiveInterval::liveBeforeAndAt(LiveIndex I) const {
+bool LiveInterval::liveBeforeAndAt(SlotIndex I) const {
   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
 
   if (r == ranges.begin())
@@ -131,7 +127,7 @@
 
 /// overlaps - Return true if the live interval overlaps a range specified
 /// by [Start, End).
-bool LiveInterval::overlaps(LiveIndex Start, LiveIndex End) const {
+bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
   assert(Start < End && "Invalid range");
   const_iterator I  = begin();
   const_iterator E  = end();
@@ -149,10 +145,10 @@
 /// specified by I to end at the specified endpoint.  To do this, we should
 /// merge and eliminate all ranges that this will overlap with.  The iterator is
 /// not invalidated.
-void LiveInterval::extendIntervalEndTo(Ranges::iterator I, LiveIndex NewEnd) {
+void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
   assert(I != ranges.end() && "Not a valid interval!");
   VNInfo *ValNo = I->valno;
-  LiveIndex OldEnd = I->end;
+  SlotIndex OldEnd = I->end;
 
   // Search for the first interval that we can't merge with.
   Ranges::iterator MergeTo = next(I);
@@ -167,7 +163,7 @@
   ranges.erase(next(I), MergeTo);
 
   // Update kill info.
-  ValNo->removeKills(OldEnd, I->end.prevSlot_());
+  ValNo->removeKills(OldEnd, I->end.getPrevSlot());
 
   // If the newly formed range now touches the range after it and if they have
   // the same value number, merge the two ranges into one range.
@@ -183,7 +179,7 @@
 /// specified by I to start at the specified endpoint.  To do this, we should
 /// merge and eliminate all ranges that this will overlap with.
 LiveInterval::Ranges::iterator
-LiveInterval::extendIntervalStartTo(Ranges::iterator I, LiveIndex NewStart) {
+LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) {
   assert(I != ranges.end() && "Not a valid interval!");
   VNInfo *ValNo = I->valno;
 
@@ -216,7 +212,7 @@
 
 LiveInterval::iterator
 LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
-  LiveIndex Start = LR.start, End = LR.end;
+  SlotIndex Start = LR.start, End = LR.end;
   iterator it = std::upper_bound(From, ranges.end(), Start);
 
   // If the inserted interval starts in the middle or right at the end of
@@ -268,7 +264,7 @@
 
 /// isInOneLiveRange - Return true if the range specified is entirely in 
 /// a single LiveRange of the live interval.
-bool LiveInterval::isInOneLiveRange(LiveIndex Start, LiveIndex End) {
+bool LiveInterval::isInOneLiveRange(SlotIndex Start, SlotIndex End) {
   Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
   if (I == ranges.begin())
     return false;
@@ -279,7 +275,7 @@
 
 /// removeRange - Remove the specified range from this interval.  Note that
 /// the range must be in a single LiveRange in its entirety.
-void LiveInterval::removeRange(LiveIndex Start, LiveIndex End,
+void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
                                bool RemoveDeadValNo) {
   // Find the LiveRange containing this span.
   Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
@@ -331,7 +327,7 @@
   }
 
   // Otherwise, we are splitting the LiveRange into two pieces.
-  LiveIndex OldEnd = I->end;
+  SlotIndex OldEnd = I->end;
   I->end = Start;   // Trim the old interval.
 
   // Insert the new one.
@@ -362,36 +358,11 @@
     ValNo->setIsUnused(true);
   }
 }
- 
-/// scaleNumbering - Renumber VNI and ranges to provide gaps for new
-/// instructions.                                                   
-
-void LiveInterval::scaleNumbering(unsigned factor) {
-  // Scale ranges.                                                            
-  for (iterator RI = begin(), RE = end(); RI != RE; ++RI) {
-    RI->start = RI->start.scale(factor);
-    RI->end = RI->end.scale(factor);
-  }
-
-  // Scale VNI info.                                                          
-  for (vni_iterator VNI = vni_begin(), VNIE = vni_end(); VNI != VNIE; ++VNI) {
-    VNInfo *vni = *VNI;
-
-    if (vni->isDefAccurate())
-      vni->def = vni->def.scale(factor);
-
-    for (unsigned i = 0; i < vni->kills.size(); ++i) {
-      if (!vni->kills[i].isPHIIndex())
-        vni->kills[i] = vni->kills[i].scale(factor);
-    }
-  }
-}
-
 
 /// getLiveRangeContaining - Return the live range that contains the
 /// specified index, or null if there is none.
 LiveInterval::const_iterator 
-LiveInterval::FindLiveRangeContaining(LiveIndex Idx) const {
+LiveInterval::FindLiveRangeContaining(SlotIndex Idx) const {
   const_iterator It = std::upper_bound(begin(), end(), Idx);
   if (It != ranges.begin()) {
     --It;
@@ -403,7 +374,7 @@
 }
 
 LiveInterval::iterator 
-LiveInterval::FindLiveRangeContaining(LiveIndex Idx) {
+LiveInterval::FindLiveRangeContaining(SlotIndex Idx) {
   iterator It = std::upper_bound(begin(), end(), Idx);
   if (It != begin()) {
     --It;
@@ -416,7 +387,7 @@
 
 /// findDefinedVNInfo - Find the VNInfo defined by the specified
 /// index (register interval).
-VNInfo *LiveInterval::findDefinedVNInfoForRegInt(LiveIndex Idx) const {
+VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const {
   for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end();
        i != e; ++i) {
     if ((*i)->def == Idx)
@@ -440,7 +411,8 @@
 /// join - Join two live intervals (this, and other) together.  This applies
 /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 /// the intervals are not joinable, this aborts.
-void LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments,
+void LiveInterval::join(LiveInterval &Other,
+                        const int *LHSValNoAssignments,
                         const int *RHSValNoAssignments, 
                         SmallVector<VNInfo*, 16> &NewVNInfo,
                         MachineRegisterInfo *MRI) {
@@ -554,14 +526,15 @@
 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 /// current interval, it will replace the value numbers of the overlaped
 /// live ranges with the specified value number.
-void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
-                                     const VNInfo *RHSValNo, VNInfo *LHSValNo) {
+void LiveInterval::MergeValueInAsValue(
+                                    const LiveInterval &RHS,
+                                    const VNInfo *RHSValNo, VNInfo *LHSValNo) {
   SmallVector<VNInfo*, 4> ReplacedValNos;
   iterator IP = begin();
   for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
     if (I->valno != RHSValNo)
       continue;
-    LiveIndex Start = I->start, End = I->end;
+    SlotIndex Start = I->start, End = I->end;
     IP = std::upper_bound(IP, end(), Start);
     // If the start of this range overlaps with an existing liverange, trim it.
     if (IP != begin() && IP[-1].end > Start) {
@@ -621,7 +594,8 @@
 /// MergeInClobberRanges - For any live ranges that are not defined in the
 /// current interval, but are defined in the Clobbers interval, mark them
 /// used with an unknown definition value.
-void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
+void LiveInterval::MergeInClobberRanges(LiveIntervals &li_,
+                                        const LiveInterval &Clobbers,
                                         BumpPtrAllocator &VNInfoAllocator) {
   if (Clobbers.empty()) return;
   
@@ -638,20 +612,20 @@
       ClobberValNo = UnusedValNo;
     else {
       UnusedValNo = ClobberValNo =
-        getNextValue(LiveIndex(), 0, false, VNInfoAllocator);
+        getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator);
       ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo));
     }
 
     bool Done = false;
-    LiveIndex Start = I->start, End = I->end;
+    SlotIndex Start = I->start, End = I->end;
     // If a clobber range starts before an existing range and ends after
     // it, the clobber range will need to be split into multiple ranges.
     // Loop until the entire clobber range is handled.
     while (!Done) {
       Done = true;
       IP = std::upper_bound(IP, end(), Start);
-      LiveIndex SubRangeStart = Start;
-      LiveIndex SubRangeEnd = End;
+      SlotIndex SubRangeStart = Start;
+      SlotIndex SubRangeEnd = End;
 
       // If the start of this range overlaps with an existing liverange, trim it.
       if (IP != begin() && IP[-1].end > SubRangeStart) {
@@ -687,13 +661,14 @@
   }
 }
 
-void LiveInterval::MergeInClobberRange(LiveIndex Start,
-                                       LiveIndex End,
+void LiveInterval::MergeInClobberRange(LiveIntervals &li_,
+                                       SlotIndex Start,
+                                       SlotIndex End,
                                        BumpPtrAllocator &VNInfoAllocator) {
   // Find a value # to use for the clobber ranges.  If there is already a value#
   // for unknown values, use it.
   VNInfo *ClobberValNo =
-    getNextValue(LiveIndex(), 0, false, VNInfoAllocator);
+    getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator);
   
   iterator IP = begin();
   IP = std::upper_bound(IP, end(), Start);
@@ -881,8 +856,6 @@
           OS << "-(";
           for (unsigned j = 0; j != ee; ++j) {
             OS << vni->kills[j];
-            if (vni->kills[j].isPHIIndex())
-              OS << "*";
             if (j != ee-1)
               OS << " ";
           }
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 79f46f3..2a93a35 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -28,6 +28,7 @@
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/ProcessImplicitDefs.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
@@ -80,6 +81,10 @@
   }
   
   AU.addRequiredID(TwoAddressInstructionPassID);
+  AU.addPreserved<ProcessImplicitDefs>();
+  AU.addRequired<ProcessImplicitDefs>();
+  AU.addPreserved<SlotIndexes>();
+  AU.addRequiredTransitive<SlotIndexes>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
@@ -89,12 +94,7 @@
        E = r2iMap_.end(); I != E; ++I)
     delete I->second;
   
-  MBB2IdxMap.clear();
-  Idx2MBBMap.clear();
-  mi2iMap_.clear();
-  i2miMap_.clear();
   r2iMap_.clear();
-  terminatorGaps.clear();
   phiJoinCopies.clear();
 
   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
@@ -106,422 +106,6 @@
   }
 }
 
-static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
-                                   unsigned OpIdx, const TargetInstrInfo *tii_){
-  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
-  if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
-      Reg == SrcReg)
-    return true;
-
-  if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
-    return true;
-  if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
-    return true;
-  return false;
-}
-
-/// 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();
-        ImpDefRegs.insert(Reg);
-        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
-          for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
-            ImpDefRegs.insert(*SS);
-        }
-        ImpDefMIs.push_back(MI);
-        continue;
-      }
-
-      if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
-        MachineOperand &MO = MI->getOperand(2);
-        if (ImpDefRegs.count(MO.getReg())) {
-          // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2
-          // This is an identity copy, eliminate it now.
-          if (MO.isKill()) {
-            LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
-            vi.removeKill(MI);
-          }
-          MI->eraseFromParent();
-          continue;
-        }
-      }
-
-      bool ChangedToImpDef = false;
-      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-        MachineOperand& MO = MI->getOperand(i);
-        if (!MO.isReg() || !MO.isUse() || MO.isUndef())
-          continue;
-        unsigned Reg = MO.getReg();
-        if (!Reg)
-          continue;
-        if (!ImpDefRegs.count(Reg))
-          continue;
-        // Use is a copy, just turn it into an implicit_def.
-        if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) {
-          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);
-            LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
-            vi.removeKill(MI);
-          }
-          ChangedToImpDef = true;
-          break;
-        }
-
-        MO.setIsUndef();
-        if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
-          // Make sure other uses of 
-          for (unsigned j = i+1; j != e; ++j) {
-            MachineOperand &MOJ = MI->getOperand(j);
-            if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
-              MOJ.setIsUndef();
-          }
-          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) ||
-          !ImpDefRegs.count(Reg)) {
-        // Delete all "local" implicit_def's. That include those which define
-        // physical registers since they cannot be liveout.
-        MI->eraseFromParent();
-        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;
-
-      // The only implicit_def which we want to keep are those that are live
-      // out of its block.
-      MI->eraseFromParent();
-
-      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;
-
-        // Turn a copy use into an implicit_def.
-        unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
-        if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
-            Reg == SrcReg) {
-          RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
-          for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
-            RMI->RemoveOperand(j);
-          continue;
-        }
-
-        const TargetRegisterClass* RC = mri_->getRegClass(Reg);
-        unsigned NewVReg = mri_->createVirtualRegister(RC);
-        RMO.setReg(NewVReg);
-        RMO.setIsUndef();
-        RMO.setIsKill();
-      }
-    }
-    ImpDefRegs.clear();
-    ImpDefMIs.clear();
-  }
-}
-
-
-void LiveIntervals::computeNumbering() {
-  Index2MiMap OldI2MI = i2miMap_;
-  std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
-  
-  Idx2MBBMap.clear();
-  MBB2IdxMap.clear();
-  mi2iMap_.clear();
-  i2miMap_.clear();
-  terminatorGaps.clear();
-  phiJoinCopies.clear();
-  
-  FunctionSize = 0;
-  
-  // Number MachineInstrs and MachineBasicBlocks.
-  // Initialize MBB indexes to a sentinal.
-  MBB2IdxMap.resize(mf_->getNumBlockIDs(),
-                    std::make_pair(LiveIndex(),LiveIndex()));
-  
-  LiveIndex MIIndex;
-  for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
-       MBB != E; ++MBB) {
-    LiveIndex StartIdx = MIIndex;
-
-    // Insert an empty slot at the beginning of each block.
-    MIIndex = getNextIndex(MIIndex);
-    i2miMap_.push_back(0);
-
-    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.
-        LiveIndex tGap(true, MIIndex);
-        bool inserted =
-          terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second;
-        assert(inserted && 
-               "Multiple 'first' terminators encountered during numbering.");
-        inserted = inserted; // Avoid compiler warning if assertions turned off.
-        i2miMap_.push_back(0);
-
-        MIIndex = getNextIndex(MIIndex);
-      }
-
-      bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
-      assert(inserted && "multiple MachineInstr -> index mappings");
-      inserted = true;
-      i2miMap_.push_back(I);
-      MIIndex = getNextIndex(MIIndex);
-      FunctionSize++;
-      
-      // Insert max(1, numdefs) empty slots after every instruction.
-      unsigned Slots = I->getDesc().getNumDefs();
-      if (Slots == 0)
-        Slots = 1;
-      while (Slots--) {
-        MIIndex = getNextIndex(MIIndex);
-        i2miMap_.push_back(0);
-      }
-
-    }
-  
-    if (MBB->getFirstTerminator() == MBB->end()) {
-      // Leave a gap for before terminators, this is where we will point
-      // PHI kills.
-      LiveIndex tGap(true, MIIndex);
-      bool inserted =
-        terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second;
-      assert(inserted && 
-             "Multiple 'first' terminators encountered during numbering.");
-      inserted = inserted; // Avoid compiler warning if assertions turned off.
-      i2miMap_.push_back(0);
- 
-      MIIndex = getNextIndex(MIIndex);
-    }
-    
-    // Set the MBB2IdxMap entry for this MBB.
-    MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, getPrevSlot(MIIndex));
-    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) {
-      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
-        // original instruction has been erased.  This is either the following
-        // instruction or its predecessor.
-        unsigned index = LI->start.getVecIndex();
-        LiveIndex::Slot offset = LI->start.getSlot();
-        if (LI->start.isLoad()) {
-          std::vector<IdxMBBPair>::const_iterator I =
-                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
-          // Take the pair containing the index
-          std::vector<IdxMBBPair>::const_iterator J =
-                    (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
-          
-          LI->start = getMBBStartIdx(J->second);
-        } else {
-          LI->start = LiveIndex(
-            LiveIndex(mi2iMap_[OldI2MI[index]]), 
-                              (LiveIndex::Slot)offset);
-        }
-        
-        // Remap the ending index in the same way that we remapped the start,
-        // except for the final step where we always map to the immediately
-        // following instruction.
-        index = (getPrevSlot(LI->end)).getVecIndex();
-        offset  = LI->end.getSlot();
-        if (LI->end.isLoad()) {
-          // VReg dies at end of block.
-          std::vector<IdxMBBPair>::const_iterator I =
-                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
-          --I;
-          
-          LI->end = getNextSlot(getMBBEndIdx(I->second));
-        } else {
-          unsigned idx = index;
-          while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
-          
-          if (index != OldI2MI.size())
-            LI->end =
-              LiveIndex(mi2iMap_[OldI2MI[index]],
-                (idx == index ? offset : LiveIndex::LOAD));
-          else
-            LI->end =
-              LiveIndex(LiveIndex::NUM * i2miMap_.size());
-        }
-      }
-      
-      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.
-        if (vni->isDefAccurate() && !vni->isUnused()) {
-          unsigned index = vni->def.getVecIndex();
-          LiveIndex::Slot offset = vni->def.getSlot();
-          if (vni->def.isLoad()) {
-            std::vector<IdxMBBPair>::const_iterator I =
-                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def);
-            // Take the pair containing the index
-            std::vector<IdxMBBPair>::const_iterator J =
-                    (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
-          
-            vni->def = getMBBStartIdx(J->second);
-          } else {
-            vni->def = LiveIndex(mi2iMap_[OldI2MI[index]], offset);
-          }
-        }
-        
-        // Remap the VNInfo kill indices, which works the same as
-        // the end indices above.
-        for (size_t i = 0; i < vni->kills.size(); ++i) {
-          unsigned index = getPrevSlot(vni->kills[i]).getVecIndex();
-          LiveIndex::Slot offset = vni->kills[i].getSlot();
-
-          if (vni->kills[i].isLoad()) {
-            assert("Value killed at a load slot.");
-            /*std::vector<IdxMBBPair>::const_iterator I =
-             std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
-            --I;
-
-            vni->kills[i] = getMBBEndIdx(I->second);*/
-          } else {
-            if (vni->kills[i].isPHIIndex()) {
-              std::vector<IdxMBBPair>::const_iterator I =
-                std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
-              --I;
-              vni->kills[i] = terminatorGaps[I->second];  
-            } else {
-              assert(OldI2MI[index] != 0 &&
-                     "Kill refers to instruction not present in index maps.");
-              vni->kills[i] = LiveIndex(mi2iMap_[OldI2MI[index]], offset);
-            }
-           
-            /*
-            unsigned idx = index;
-            while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
-            
-            if (index != OldI2MI.size())
-              vni->kills[i] = mi2iMap_[OldI2MI[index]] + 
-                              (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<LiveIndex, LiveIndex> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
-    mbbIndices.first = mbbIndices.first.scale(factor);
-    mbbIndices.second = mbbIndices.second.scale(factor);
-    Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 
-  }
-  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
-
-  // Scale terminator gaps.
-  for (DenseMap<MachineBasicBlock*, LiveIndex>::iterator
-       TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
-       TGI != TGE; ++TGI) {
-    terminatorGaps[TGI->first] = TGI->second.scale(factor);
-  }
-
-  // Scale the intervals.
-  for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
-    LI->second->scaleNumbering(factor);
-  }
-
-  // Scale MachineInstrs.
-  Mi2IndexMap oldmi2iMap = mi2iMap_;
-  LiveIndex highestSlot;
-  for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
-       MI != ME; ++MI) {
-    LiveIndex newSlot = MI->second.scale(factor);
-    mi2iMap_[MI->first] = newSlot;
-    highestSlot = std::max(highestSlot, newSlot); 
-  }
-
-  unsigned highestVIndex = highestSlot.getVecIndex();
-  i2miMap_.clear();
-  i2miMap_.resize(highestVIndex + 1);
-  for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
-       MI != ME; ++MI) {
-    i2miMap_[MI->second.getVecIndex()] = const_cast<MachineInstr *>(MI->first);
-  }
-
-}
-
-
 /// runOnMachineFunction - Register allocate the whole function
 ///
 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
@@ -532,10 +116,9 @@
   tii_ = tm_->getInstrInfo();
   aa_ = &getAnalysis<AliasAnalysis>();
   lv_ = &getAnalysis<LiveVariables>();
+  indexes_ = &getAnalysis<SlotIndexes>();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
 
-  processImplicitDefs();
-  computeNumbering();
   computeIntervals();
   performEarlyCoalescing();
 
@@ -579,12 +162,13 @@
                                             VirtRegMap &vrm, unsigned reg) {
   for (LiveInterval::Ranges::const_iterator
          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
-    for (LiveIndex index = getBaseIndex(I->start),
-           end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end;
-         index = getNextIndex(index)) {
+    for (SlotIndex index = I->start.getBaseIndex(),
+           end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
+           index != end;
+           index = index.getNextIndex()) {
       // skip deleted instructions
       while (index != end && !getInstructionFromIndex(index))
-        index = getNextIndex(index);
+        index = index.getNextIndex();
       if (index == end) break;
 
       MachineInstr *MI = getInstructionFromIndex(index);
@@ -620,16 +204,17 @@
                                   SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
   for (LiveInterval::Ranges::const_iterator
          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
-    for (LiveIndex index = getBaseIndex(I->start),
-           end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end;
-         index = getNextIndex(index)) {
+    for (SlotIndex index = I->start.getBaseIndex(),
+           end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
+           index != end;
+           index = index.getNextIndex()) {
       // Skip deleted instructions.
       MachineInstr *MI = 0;
       while (index != end) {
         MI = getInstructionFromIndex(index);
         if (MI)
           break;
-        index = getNextIndex(index);
+        index = index.getNextIndex();
       }
       if (index == end) break;
 
@@ -664,7 +249,7 @@
 
 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
                                              MachineBasicBlock::iterator mi,
-                                             LiveIndex MIIdx,
+                                             SlotIndex MIIdx,
                                              MachineOperand& MO,
                                              unsigned MOIdx,
                                              LiveInterval &interval) {
@@ -680,11 +265,11 @@
   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
   if (interval.empty()) {
     // Get the Idx of the defining instructions.
-    LiveIndex defIndex = getDefIndex(MIIdx);
+    SlotIndex defIndex = MIIdx.getDefIndex();
     // Earlyclobbers move back one, so that they overlap the live range
     // of inputs.
     if (MO.isEarlyClobber())
-      defIndex = getUseIndex(MIIdx);
+      defIndex = MIIdx.getUseIndex();
     VNInfo *ValNo;
     MachineInstr *CopyMI = NULL;
     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
@@ -704,16 +289,11 @@
     // will be a single kill, in MBB, which comes after the definition.
     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
       // FIXME: what about dead vars?
-      LiveIndex killIdx;
+      SlotIndex killIdx;
       if (vi.Kills[0] != mi)
-        killIdx = getNextSlot(getUseIndex(getInstructionIndex(vi.Kills[0])));
-      else if (MO.isEarlyClobber())
-        // Earlyclobbers that die in this instruction move up one extra, to
-        // compensate for having the starting point moved back one.  This
-        // gets them to overlap the live range of other outputs.
-        killIdx = getNextSlot(getNextSlot(defIndex));
+        killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
       else
-        killIdx = getNextSlot(defIndex);
+        killIdx = defIndex.getStoreIndex();
 
       // If the kill happens after the definition, we have an intra-block
       // live range.
@@ -732,7 +312,8 @@
     // of the defining block, potentially live across some blocks, then is
     // live into some number of blocks, but gets killed.  Start by adding a
     // range that goes from this definition to the end of the defining block.
-    LiveRange NewLR(defIndex, getNextSlot(getMBBEndIdx(mbb)), ValNo);
+    LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(),
+                    ValNo);
     DEBUG(errs() << " +" << NewLR);
     interval.addRange(NewLR);
 
@@ -741,9 +322,10 @@
     // live interval.
     for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 
              E = vi.AliveBlocks.end(); I != E; ++I) {
-      LiveRange LR(getMBBStartIdx(*I),
-                   getNextSlot(getMBBEndIdx(*I)),  // MBB ends at -1.
-                   ValNo);
+      LiveRange LR(
+          getMBBStartIdx(mf_->getBlockNumbered(*I)),
+          getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(),
+          ValNo);
       interval.addRange(LR);
       DEBUG(errs() << " +" << LR);
     }
@@ -752,8 +334,8 @@
     // block to the 'use' slot of the killing instruction.
     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
       MachineInstr *Kill = vi.Kills[i];
-      LiveIndex killIdx =
-        getNextSlot(getUseIndex(getInstructionIndex(Kill)));
+      SlotIndex killIdx =
+        getInstructionIndex(Kill).getDefIndex();
       LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo);
       interval.addRange(LR);
       ValNo->addKill(killIdx);
@@ -772,13 +354,13 @@
       // need to take the LiveRegion that defines this register and split it
       // into two values.
       assert(interval.containsOneValue());
-      LiveIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
-      LiveIndex RedefIndex = getDefIndex(MIIdx);
+      SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex();
+      SlotIndex RedefIndex = MIIdx.getDefIndex();
       if (MO.isEarlyClobber())
-        RedefIndex = getUseIndex(MIIdx);
+        RedefIndex = MIIdx.getUseIndex();
 
       const LiveRange *OldLR =
-        interval.getLiveRangeContaining(getPrevSlot(RedefIndex));
+        interval.getLiveRangeContaining(RedefIndex.getUseIndex());
       VNInfo *OldValNo = OldLR->valno;
 
       // Delete the initial value, which should be short and continuous,
@@ -811,10 +393,8 @@
       // If this redefinition is dead, we need to add a dummy unit live
       // range covering the def slot.
       if (MO.isDead())
-        interval.addRange(
-          LiveRange(RedefIndex, MO.isEarlyClobber() ?
-                                getNextSlot(getNextSlot(RedefIndex)) :
-                                getNextSlot(RedefIndex), OldValNo));
+        interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
+                                    OldValNo));
 
       DEBUG({
           errs() << " RESULT: ";
@@ -829,9 +409,8 @@
         VNInfo *VNI = interval.getValNumInfo(0);
         MachineInstr *Killer = vi.Kills[0];
         phiJoinCopies.push_back(Killer);
-        LiveIndex Start = getMBBStartIdx(Killer->getParent());
-        LiveIndex End =
-          getNextSlot(getUseIndex(getInstructionIndex(Killer)));
+        SlotIndex Start = getMBBStartIdx(Killer->getParent());
+        SlotIndex End = getInstructionIndex(Killer).getDefIndex();
         DEBUG({
             errs() << " Removing [" << Start << "," << End << "] from: ";
             interval.print(errs(), tri_);
@@ -841,7 +420,7 @@
         assert(interval.ranges.size() == 1 &&
                "Newly discovered PHI interval has >1 ranges.");
         MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex());
-        VNI->addKill(terminatorGaps[killMBB]);
+        VNI->addKill(indexes_->getTerminatorGap(killMBB));
         VNI->setHasPHIKill(true);
         DEBUG({
             errs() << " RESULT: ";
@@ -851,8 +430,8 @@
         // 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(LiveIndex(mbb->getNumber()),
-                                0, false, VNInfoAllocator));
+                     interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true),
+                       0, false, VNInfoAllocator));
         LR.valno->setIsPHIDef(true);
         DEBUG(errs() << " replace range with " << LR);
         interval.addRange(LR);
@@ -866,9 +445,9 @@
       // In the case of PHI elimination, each variable definition is only
       // live until the end of the block.  We've already taken care of the
       // rest of the live range.
-      LiveIndex defIndex = getDefIndex(MIIdx);
+      SlotIndex defIndex = MIIdx.getDefIndex();
       if (MO.isEarlyClobber())
-        defIndex = getUseIndex(MIIdx);
+        defIndex = MIIdx.getUseIndex();
 
       VNInfo *ValNo;
       MachineInstr *CopyMI = NULL;
@@ -880,10 +459,10 @@
         CopyMI = mi;
       ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
       
-      LiveIndex killIndex = getNextSlot(getMBBEndIdx(mbb));
+      SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex();
       LiveRange LR(defIndex, killIndex, ValNo);
       interval.addRange(LR);
-      ValNo->addKill(terminatorGaps[mbb]);
+      ValNo->addKill(indexes_->getTerminatorGap(mbb));
       ValNo->setHasPHIKill(true);
       DEBUG(errs() << " +" << LR);
     }
@@ -894,7 +473,7 @@
 
 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
                                               MachineBasicBlock::iterator mi,
-                                              LiveIndex MIIdx,
+                                              SlotIndex MIIdx,
                                               MachineOperand& MO,
                                               LiveInterval &interval,
                                               MachineInstr *CopyMI) {
@@ -905,12 +484,12 @@
       printRegName(interval.reg, tri_);
     });
 
-  LiveIndex baseIndex = MIIdx;
-  LiveIndex start = getDefIndex(baseIndex);
+  SlotIndex baseIndex = MIIdx;
+  SlotIndex start = baseIndex.getDefIndex();
   // Earlyclobbers move back one.
   if (MO.isEarlyClobber())
-    start = getUseIndex(MIIdx);
-  LiveIndex end = start;
+    start = MIIdx.getUseIndex();
+  SlotIndex end = start;
 
   // If it is not used after definition, it is considered dead at
   // the instruction defining it. Hence its interval is:
@@ -919,53 +498,51 @@
   // advance below compensates.
   if (MO.isDead()) {
     DEBUG(errs() << " dead");
-    if (MO.isEarlyClobber())
-      end = getNextSlot(getNextSlot(start));
-    else
-      end = getNextSlot(start);
+    end = start.getStoreIndex();
     goto exit;
   }
 
   // If it is not dead on definition, it must be killed by a
   // subsequent instruction. Hence its interval is:
   // [defSlot(def), useSlot(kill)+1)
-  baseIndex = getNextIndex(baseIndex);
+  baseIndex = baseIndex.getNextIndex();
   while (++mi != MBB->end()) {
-    while (baseIndex.getVecIndex() < i2miMap_.size() &&
-           getInstructionFromIndex(baseIndex) == 0)
-      baseIndex = getNextIndex(baseIndex);
+
+    if (getInstructionFromIndex(baseIndex) == 0)
+      baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
     if (mi->killsRegister(interval.reg, tri_)) {
       DEBUG(errs() << " killed");
-      end = getNextSlot(getUseIndex(baseIndex));
+      end = baseIndex.getDefIndex();
       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);
+          end = baseIndex.getDefIndex();
+          assert(!mi->getOperand(DefIdx).isEarlyClobber() &&
+                 "Two address instruction is an early clobber?"); 
         } 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)
           DEBUG(errs() << " dead");
-          end = getNextSlot(start);
+          end = start.getStoreIndex();
         }
         goto exit;
       }
     }
     
-    baseIndex = getNextIndex(baseIndex);
+    baseIndex = baseIndex.getNextIndex();
   }
   
   // 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. Another possible case is the implicit use of the
   // physical register has been deleted by two-address pass.
-  end = getNextSlot(start);
+  end = start.getStoreIndex();
 
 exit:
   assert(start < end && "did not find end of interval?");
@@ -985,7 +562,7 @@
 
 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
                                       MachineBasicBlock::iterator MI,
-                                      LiveIndex MIIdx,
+                                      SlotIndex MIIdx,
                                       MachineOperand& MO,
                                       unsigned MOIdx) {
   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
@@ -1012,7 +589,7 @@
 }
 
 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
-                                         LiveIndex MIIdx,
+                                         SlotIndex MIIdx,
                                          LiveInterval &interval, bool isAlias) {
   DEBUG({
       errs() << "\t\tlivein register: ";
@@ -1022,18 +599,18 @@
   // Look for kills, if it reaches a def before it's killed, then it shouldn't
   // be considered a livein.
   MachineBasicBlock::iterator mi = MBB->begin();
-  LiveIndex baseIndex = MIIdx;
-  LiveIndex start = baseIndex;
-  while (baseIndex.getVecIndex() < i2miMap_.size() && 
-         getInstructionFromIndex(baseIndex) == 0)
-    baseIndex = getNextIndex(baseIndex);
-  LiveIndex end = baseIndex;
+  SlotIndex baseIndex = MIIdx;
+  SlotIndex start = baseIndex;
+  if (getInstructionFromIndex(baseIndex) == 0)
+    baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
+  SlotIndex end = baseIndex;
   bool SeenDefUse = false;
   
   while (mi != MBB->end()) {
     if (mi->killsRegister(interval.reg, tri_)) {
       DEBUG(errs() << " killed");
-      end = getNextSlot(getUseIndex(baseIndex));
+      end = baseIndex.getDefIndex();
       SeenDefUse = true;
       break;
     } else if (mi->modifiesRegister(interval.reg, tri_)) {
@@ -1042,17 +619,14 @@
       // it. Hence its interval is:
       // [defSlot(def), defSlot(def)+1)
       DEBUG(errs() << " dead");
-      end = getNextSlot(getDefIndex(start));
+      end = start.getStoreIndex();
       SeenDefUse = true;
       break;
     }
 
-    baseIndex = getNextIndex(baseIndex);
     ++mi;
     if (mi != MBB->end()) {
-      while (baseIndex.getVecIndex() < i2miMap_.size() && 
-             getInstructionFromIndex(baseIndex) == 0)
-        baseIndex = getNextIndex(baseIndex);
+      baseIndex = indexes_->getNextNonNullIndex(baseIndex);
     }
   }
 
@@ -1060,7 +634,7 @@
   if (!SeenDefUse) {
     if (isAlias) {
       DEBUG(errs() << " dead");
-      end = getNextSlot(getDefIndex(MIIdx));
+      end = MIIdx.getStoreIndex();
     } else {
       DEBUG(errs() << " live through");
       end = baseIndex;
@@ -1068,7 +642,7 @@
   }
 
   VNInfo *vni =
-    interval.getNextValue(LiveIndex(MBB->getNumber()),
+    interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true),
                           0, false, VNInfoAllocator);
   vni->setIsPHIDef(true);
   LiveRange LR(start, end, vni);
@@ -1139,11 +713,11 @@
       MachineInstr *PHICopy = OtherCopies[i];
       DEBUG(errs() << "Moving: " << *PHICopy);
 
-      LiveIndex MIIndex = getInstructionIndex(PHICopy);
-      LiveIndex DefIndex = getDefIndex(MIIndex);
+      SlotIndex MIIndex = getInstructionIndex(PHICopy);
+      SlotIndex DefIndex = MIIndex.getDefIndex();
       LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
-      LiveIndex StartIndex = SLR->start;
-      LiveIndex EndIndex = SLR->end;
+      SlotIndex StartIndex = SLR->start;
+      SlotIndex EndIndex = SLR->end;
 
       // Delete val# defined by the now identity copy and add the range from
       // beginning of the mbb to the end of the range.
@@ -1169,11 +743,11 @@
       MachineInstr *PHICopy = IdentCopies[i];
       DEBUG(errs() << "Coalescing: " << *PHICopy);
 
-      LiveIndex MIIndex = getInstructionIndex(PHICopy);
-      LiveIndex DefIndex = getDefIndex(MIIndex);
+      SlotIndex MIIndex = getInstructionIndex(PHICopy);
+      SlotIndex DefIndex = MIIndex.getDefIndex();
       LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
-      LiveIndex StartIndex = SLR->start;
-      LiveIndex EndIndex = SLR->end;
+      SlotIndex StartIndex = SLR->start;
+      SlotIndex EndIndex = SLR->end;
 
       // Delete val# defined by the now identity copy and add the range from
       // beginning of the mbb to the end of the range.
@@ -1186,9 +760,9 @@
     }
 
     // Remove the phi join and update the phi block liveness.
-    LiveIndex MIIndex = getInstructionIndex(Join);
-    LiveIndex UseIndex = getUseIndex(MIIndex);
-    LiveIndex DefIndex = getDefIndex(MIIndex);
+    SlotIndex MIIndex = getInstructionIndex(Join);
+    SlotIndex UseIndex = MIIndex.getUseIndex();
+    SlotIndex DefIndex = MIIndex.getDefIndex();
     LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
     LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
     DLR->valno->setCopy(0);
@@ -1218,7 +792,7 @@
        MBBI != E; ++MBBI) {
     MachineBasicBlock *MBB = MBBI;
     // Track the index of the current machine instr.
-    LiveIndex MIIndex = getMBBStartIdx(MBB);
+    SlotIndex MIIndex = getMBBStartIdx(MBB);
     DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
 
     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
@@ -1235,9 +809,8 @@
     }
     
     // Skip over empty initial indices.
-    while (MIIndex.getVecIndex() < i2miMap_.size() &&
-           getInstructionFromIndex(MIIndex) == 0)
-      MIIndex = getNextIndex(MIIndex);
+    if (getInstructionFromIndex(MIIndex) == 0)
+      MIIndex = indexes_->getNextNonNullIndex(MIIndex);
     
     for (; MI != miEnd; ++MI) {
       DEBUG(errs() << MIIndex << "\t" << *MI);
@@ -1254,19 +827,9 @@
         else if (MO.isUndef())
           UndefUses.push_back(MO.getReg());
       }
-
-      // Skip over the empty slots after each instruction.
-      unsigned Slots = MI->getDesc().getNumDefs();
-      if (Slots == 0)
-        Slots = 1;
-
-      while (Slots--)
-        MIIndex = getNextIndex(MIIndex);
       
-      // Skip over empty indices.
-      while (MIIndex.getVecIndex() < i2miMap_.size() &&
-             getInstructionFromIndex(MIIndex) == 0)
-        MIIndex = getNextIndex(MIIndex);
+      // Move to the next instr slot.
+      MIIndex = indexes_->getNextNonNullIndex(MIIndex);
     }
   }
 
@@ -1279,45 +842,6 @@
   }
 }
 
-bool LiveIntervals::findLiveInMBBs(
-                              LiveIndex Start, LiveIndex 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;
-    MBBs.push_back(I->second);
-    ResVal = true;
-    ++I;
-  }
-  return ResVal;
-}
-
-bool LiveIntervals::findReachableMBBs(
-                              LiveIndex Start, LiveIndex 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);
@@ -1389,8 +913,8 @@
 /// isValNoAvailableAt - Return true if the val# of the specified interval
 /// which reaches the given instruction also reaches the specified use index.
 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
-                                       LiveIndex UseIdx) const {
-  LiveIndex Index = getInstructionIndex(MI);  
+                                       SlotIndex UseIdx) const {
+  SlotIndex Index = getInstructionIndex(MI);  
   VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
   LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
   return UI != li.end() && UI->valno == ValNo;
@@ -1417,7 +941,7 @@
     for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
            re = mri_->use_end(); ri != re; ++ri) {
       MachineInstr *UseMI = &*ri;
-      LiveIndex UseIdx = getInstructionIndex(UseMI);
+      SlotIndex UseIdx = getInstructionIndex(UseMI);
       if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
         continue;
       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
@@ -1502,7 +1026,7 @@
 /// returns true.
 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
                                          VirtRegMap &vrm, MachineInstr *DefMI,
-                                         LiveIndex InstrIdx,
+                                         SlotIndex InstrIdx,
                                          SmallVector<unsigned, 2> &Ops,
                                          bool isSS, int Slot, unsigned Reg) {
   // If it is an implicit def instruction, just delete it.
@@ -1540,9 +1064,7 @@
     vrm.transferSpillPts(MI, fmi);
     vrm.transferRestorePts(MI, fmi);
     vrm.transferEmergencySpills(MI, fmi);
-    mi2iMap_.erase(MI);
-    i2miMap_[InstrIdx.getVecIndex()] = fmi;
-    mi2iMap_[fmi] = InstrIdx;
+    ReplaceMachineInstrInMaps(MI, fmi);
     MI = MBB.insert(MBB.erase(MI), fmi);
     ++numFolds;
     return true;
@@ -1570,19 +1092,21 @@
 }
 
 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
-  SmallPtrSet<MachineBasicBlock*, 4> MBBs;
-  for (LiveInterval::Ranges::const_iterator
-         I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
-    std::vector<IdxMBBPair>::const_iterator II =
-      std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
-    if (II == Idx2MBBMap.end())
-      continue;
-    if (I->end > II->first)  // crossing a MBB.
-      return false;
-    MBBs.insert(II->second);
-    if (MBBs.size() > 1)
+  LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
+
+  MachineBasicBlock *mbb =  indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+  if (mbb == 0)
+    return false;
+
+  for (++itr; itr != li.ranges.end(); ++itr) {
+    MachineBasicBlock *mbb2 =
+      indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+    if (mbb2 != mbb)
       return false;
   }
+
   return true;
 }
 
@@ -1614,7 +1138,7 @@
 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 bool LiveIntervals::
 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
-                 bool TrySplit, LiveIndex index, LiveIndex end, 
+                 bool TrySplit, SlotIndex index, SlotIndex end, 
                  MachineInstr *MI,
                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
                  unsigned Slot, int LdSlot,
@@ -1791,14 +1315,13 @@
 
     if (HasUse) {
       if (CreatedNewVReg) {
-        LiveRange LR(getLoadIndex(index), getNextSlot(getUseIndex(index)),
-                     nI.getNextValue(LiveIndex(), 0, false,
-                                     VNInfoAllocator));
+        LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
+                     nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
         DEBUG(errs() << " +" << LR);
         nI.addRange(LR);
       } else {
         // Extend the split live interval to this def / use.
-        LiveIndex End = getNextSlot(getUseIndex(index));
+        SlotIndex End = index.getDefIndex();
         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
                      nI.getValNumInfo(nI.getNumValNums()-1));
         DEBUG(errs() << " +" << LR);
@@ -1806,9 +1329,8 @@
       }
     }
     if (HasDef) {
-      LiveRange LR(getDefIndex(index), getStoreIndex(index),
-                   nI.getNextValue(LiveIndex(), 0, false,
-                                   VNInfoAllocator));
+      LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
+                   nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
       DEBUG(errs() << " +" << LR);
       nI.addRange(LR);
     }
@@ -1824,13 +1346,13 @@
 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
                                    const VNInfo *VNI,
                                    MachineBasicBlock *MBB,
-                                   LiveIndex Idx) const {
-  LiveIndex End = getMBBEndIdx(MBB);
+                                   SlotIndex Idx) const {
+  SlotIndex End = getMBBEndIdx(MBB);
   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
-    if (VNI->kills[j].isPHIIndex())
+    if (VNI->kills[j].isPHI())
       continue;
 
-    LiveIndex KillIdx = VNI->kills[j];
+    SlotIndex KillIdx = VNI->kills[j];
     if (KillIdx > Idx && KillIdx < End)
       return true;
   }
@@ -1841,11 +1363,11 @@
 /// during spilling.
 namespace {
   struct RewriteInfo {
-    LiveIndex Index;
+    SlotIndex Index;
     MachineInstr *MI;
     bool HasUse;
     bool HasDef;
-    RewriteInfo(LiveIndex i, MachineInstr *mi, bool u, bool d)
+    RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d)
       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
   };
 
@@ -1874,8 +1396,8 @@
                     std::vector<LiveInterval*> &NewLIs) {
   bool AllCanFold = true;
   unsigned NewVReg = 0;
-  LiveIndex start = getBaseIndex(I->start);
-  LiveIndex end = getNextIndex(getBaseIndex(getPrevSlot(I->end)));
+  SlotIndex start = I->start.getBaseIndex();
+  SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
 
   // First collect all the def / use in this live range that will be rewritten.
   // Make sure they are sorted according to instruction index.
@@ -1886,7 +1408,7 @@
     MachineOperand &O = ri.getOperand();
     ++ri;
     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
-    LiveIndex index = getInstructionIndex(MI);
+    SlotIndex index = getInstructionIndex(MI);
     if (index < start || index >= end)
       continue;
 
@@ -1910,7 +1432,7 @@
   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
     RewriteInfo &rwi = RewriteMIs[i];
     ++i;
-    LiveIndex index = rwi.Index;
+    SlotIndex index = rwi.Index;
     bool MIHasUse = rwi.HasUse;
     bool MIHasDef = rwi.HasDef;
     MachineInstr *MI = rwi.MI;
@@ -1993,12 +1515,12 @@
       if (MI != ReMatOrigDefMI || !CanDelete) {
         bool HasKill = false;
         if (!HasUse)
-          HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
+          HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
         else {
           // If this is a two-address code, then this index starts a new VNInfo.
-          const VNInfo *VNI = li.findDefinedVNInfoForRegInt(getDefIndex(index));
+          const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
           if (VNI)
-            HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
+            HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
         }
         DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
           SpillIdxes.find(MBBId);
@@ -2071,7 +1593,7 @@
   }
 }
 
-bool LiveIntervals::alsoFoldARestore(int Id, LiveIndex index,
+bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
                         unsigned vr, BitVector &RestoreMBBs,
                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
   if (!RestoreMBBs[Id])
@@ -2085,7 +1607,7 @@
   return false;
 }
 
-void LiveIntervals::eraseRestoreInfo(int Id, LiveIndex index,
+void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
                         unsigned vr, BitVector &RestoreMBBs,
                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
   if (!RestoreMBBs[Id])
@@ -2093,7 +1615,7 @@
   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
     if (Restores[i].index == index && Restores[i].vreg)
-      Restores[i].index = LiveIndex();
+      Restores[i].index = SlotIndex();
 }
 
 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
@@ -2192,18 +1714,18 @@
       }
       
       // Fill in  the new live interval.
-      LiveIndex index = getInstructionIndex(MI);
+      SlotIndex index = getInstructionIndex(MI);
       if (HasUse) {
-        LiveRange LR(getLoadIndex(index), getUseIndex(index),
-                     nI.getNextValue(LiveIndex(), 0, false,
+        LiveRange LR(index.getLoadIndex(), index.getUseIndex(),
+                     nI.getNextValue(SlotIndex(), 0, false,
                                      getVNInfoAllocator()));
         DEBUG(errs() << " +" << LR);
         nI.addRange(LR);
         vrm.addRestorePoint(NewVReg, MI);
       }
       if (HasDef) {
-        LiveRange LR(getDefIndex(index), getStoreIndex(index),
-                     nI.getNextValue(LiveIndex(), 0, false,
+        LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
+                     nI.getNextValue(SlotIndex(), 0, false,
                                      getVNInfoAllocator()));
         DEBUG(errs() << " +" << LR);
         nI.addRange(LR);
@@ -2267,8 +1789,8 @@
   if (vrm.getPreSplitReg(li.reg)) {
     vrm.setIsSplitFromReg(li.reg, 0);
     // Unset the split kill marker on the last use.
-    LiveIndex KillIdx = vrm.getKillPoint(li.reg);
-    if (KillIdx != LiveIndex()) {
+    SlotIndex KillIdx = vrm.getKillPoint(li.reg);
+    if (KillIdx != SlotIndex()) {
       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
       assert(KillMI && "Last use disappeared?");
       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
@@ -2394,7 +1916,7 @@
     while (Id != -1) {
       std::vector<SRInfo> &spills = SpillIdxes[Id];
       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
-        LiveIndex index = spills[i].index;
+        SlotIndex index = spills[i].index;
         unsigned VReg = spills[i].vreg;
         LiveInterval &nI = getOrCreateInterval(VReg);
         bool isReMat = vrm.isReMaterialized(VReg);
@@ -2432,16 +1954,16 @@
             if (FoundUse) {
               // Also folded uses, do not issue a load.
               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
-              nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+              nI.removeRange(index.getLoadIndex(), index.getDefIndex());
             }
-            nI.removeRange(getDefIndex(index), getStoreIndex(index));
+            nI.removeRange(index.getDefIndex(), index.getStoreIndex());
           }
         }
 
         // Otherwise tell the spiller to issue a spill.
         if (!Folded) {
           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
-          bool isKill = LR->end == getStoreIndex(index);
+          bool isKill = LR->end == index.getStoreIndex();
           if (!MI->registerDefIsDead(nI.reg))
             // No need to spill a dead def.
             vrm.addSpillPoint(VReg, isKill, MI);
@@ -2457,8 +1979,8 @@
   while (Id != -1) {
     std::vector<SRInfo> &restores = RestoreIdxes[Id];
     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
-      LiveIndex index = restores[i].index;
-      if (index == LiveIndex())
+      SlotIndex index = restores[i].index;
+      if (index == SlotIndex())
         continue;
       unsigned VReg = restores[i].vreg;
       LiveInterval &nI = getOrCreateInterval(VReg);
@@ -2513,7 +2035,7 @@
       // If folding is not possible / failed, then tell the spiller to issue a
       // load / rematerialization for us.
       if (Folded)
-        nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+        nI.removeRange(index.getLoadIndex(), index.getDefIndex());
       else
         vrm.addRestorePoint(VReg, MI);
     }
@@ -2526,10 +2048,10 @@
   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
     LiveInterval *LI = NewLIs[i];
     if (!LI->empty()) {
-      LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
+      LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI);
       if (!AddedKill.count(LI)) {
         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
-        LiveIndex LastUseIdx = getBaseIndex(LR->end);
+        SlotIndex LastUseIdx = LR->end.getBaseIndex();
         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
         assert(UseIdx != -1);
@@ -2580,7 +2102,7 @@
          E = mri_->reg_end(); I != E; ++I) {
     MachineOperand &O = I.getOperand();
     MachineInstr *MI = O.getParent();
-    LiveIndex Index = getInstructionIndex(MI);
+    SlotIndex Index = getInstructionIndex(MI);
     if (pli.liveAt(Index))
       ++NumConflicts;
   }
@@ -2623,15 +2145,15 @@
     if (SeenMIs.count(MI))
       continue;
     SeenMIs.insert(MI);
-    LiveIndex Index = getInstructionIndex(MI);
+    SlotIndex Index = getInstructionIndex(MI);
     for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
       unsigned PReg = PRegs[i];
       LiveInterval &pli = getInterval(PReg);
       if (!pli.liveAt(Index))
         continue;
       vrm.addEmergencySpill(PReg, MI);
-      LiveIndex StartIdx = getLoadIndex(Index);
-      LiveIndex EndIdx = getNextSlot(getStoreIndex(Index));
+      SlotIndex StartIdx = Index.getLoadIndex();
+      SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
       if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
         pli.removeRange(StartIdx, EndIdx);
         Cut = true;
@@ -2651,7 +2173,8 @@
           continue;
         LiveInterval &spli = getInterval(*AS);
         if (spli.liveAt(Index))
-          spli.removeRange(getLoadIndex(Index), getNextSlot(getStoreIndex(Index)));
+          spli.removeRange(Index.getLoadIndex(),
+                           Index.getNextIndex().getBaseIndex());
       }
     }
   }
@@ -2662,13 +2185,13 @@
                                                   MachineInstr* startInst) {
   LiveInterval& Interval = getOrCreateInterval(reg);
   VNInfo* VN = Interval.getNextValue(
-    LiveIndex(getInstructionIndex(startInst), LiveIndex::DEF),
+    SlotIndex(getInstructionIndex(startInst).getDefIndex()),
     startInst, true, getVNInfoAllocator());
   VN->setHasPHIKill(true);
-  VN->kills.push_back(terminatorGaps[startInst->getParent()]);
+  VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent()));
   LiveRange LR(
-    LiveIndex(getInstructionIndex(startInst), LiveIndex::DEF),
-    getNextSlot(getMBBEndIdx(startInst->getParent())), VN);
+     SlotIndex(getInstructionIndex(startInst).getDefIndex()),
+     getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN);
   Interval.addRange(LR);
   
   return LR;
diff --git a/lib/CodeGen/LiveStackAnalysis.cpp b/lib/CodeGen/LiveStackAnalysis.cpp
index a7bea1f..d2f3775 100644
--- a/lib/CodeGen/LiveStackAnalysis.cpp
+++ b/lib/CodeGen/LiveStackAnalysis.cpp
@@ -27,15 +27,10 @@
 char LiveStacks::ID = 0;
 static RegisterPass<LiveStacks> X("livestacks", "Live Stack Slot Analysis");
 
-void LiveStacks::scaleNumbering(int factor) {
-  // Scale the intervals.
-  for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
-    LI->second.scaleNumbering(factor);
-  }
-}
-
 void LiveStacks::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
+  AU.addPreserved<SlotIndexes>();
+  AU.addRequiredTransitive<SlotIndexes>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp
index b2a7312..cce5ae8 100644
--- a/lib/CodeGen/PreAllocSplitting.cpp
+++ b/lib/CodeGen/PreAllocSplitting.cpp
@@ -57,6 +57,7 @@
     const TargetRegisterInfo* TRI;
     MachineFrameInfo      *MFI;
     MachineRegisterInfo   *MRI;
+    SlotIndexes           *SIs;
     LiveIntervals         *LIs;
     LiveStacks            *LSs;
     VirtRegMap            *VRM;
@@ -68,7 +69,7 @@
     MachineBasicBlock     *BarrierMBB;
 
     // Barrier - Current barrier index.
-    LiveIndex     BarrierIdx;
+    SlotIndex     BarrierIdx;
 
     // CurrLI - Current live interval being split.
     LiveInterval          *CurrLI;
@@ -83,16 +84,19 @@
     DenseMap<unsigned, int> IntervalSSMap;
 
     // Def2SpillMap - A map from a def instruction index to spill index.
-    DenseMap<LiveIndex, LiveIndex> Def2SpillMap;
+    DenseMap<SlotIndex, SlotIndex> Def2SpillMap;
 
   public:
     static char ID;
-    PreAllocSplitting() : MachineFunctionPass(&ID) {}
+    PreAllocSplitting()
+      : MachineFunctionPass(&ID) {}
 
     virtual bool runOnMachineFunction(MachineFunction &MF);
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
+      AU.addRequired<SlotIndexes>();
+      AU.addPreserved<SlotIndexes>();
       AU.addRequired<LiveIntervals>();
       AU.addPreserved<LiveIntervals>();
       AU.addRequired<LiveStacks>();
@@ -129,23 +133,23 @@
   private:
     MachineBasicBlock::iterator
       findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
-                        LiveIndex&);
+                        SlotIndex&);
 
     MachineBasicBlock::iterator
       findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
-                     SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+                     SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
 
     MachineBasicBlock::iterator
-      findRestorePoint(MachineBasicBlock*, MachineInstr*, LiveIndex,
-                     SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+      findRestorePoint(MachineBasicBlock*, MachineInstr*, SlotIndex,
+                     SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
 
     int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
 
     bool IsAvailableInStack(MachineBasicBlock*, unsigned,
-                            LiveIndex, LiveIndex,
-                            LiveIndex&, int&) const;
+                            SlotIndex, SlotIndex,
+                            SlotIndex&, int&) const;
 
-    void UpdateSpillSlotInterval(VNInfo*, LiveIndex, LiveIndex);
+    void UpdateSpillSlotInterval(VNInfo*, SlotIndex, SlotIndex);
 
     bool SplitRegLiveInterval(LiveInterval*);
 
@@ -157,7 +161,7 @@
     bool Rematerialize(unsigned vreg, VNInfo* ValNo,
                        MachineInstr* DefMI,
                        MachineBasicBlock::iterator RestorePt,
-                       LiveIndex RestoreIdx,
+                       SlotIndex RestoreIdx,
                        SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
     MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC,
                             MachineInstr* DefMI,
@@ -209,12 +213,12 @@
 /// instruction index map. If there isn't one, return end().
 MachineBasicBlock::iterator
 PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI,
-                                     LiveIndex &SpotIndex) {
+                                     SlotIndex &SpotIndex) {
   MachineBasicBlock::iterator MII = MI;
   if (++MII != MBB->end()) {
-    LiveIndex Index =
+    SlotIndex Index =
       LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
-    if (Index != LiveIndex()) {
+    if (Index != SlotIndex()) {
       SpotIndex = Index;
       return MII;
     }
@@ -230,7 +234,7 @@
 PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI,
                                   MachineInstr *DefMI,
                                   SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
-                                  LiveIndex &SpillIndex) {
+                                  SlotIndex &SpillIndex) {
   MachineBasicBlock::iterator Pt = MBB->begin();
 
   MachineBasicBlock::iterator MII = MI;
@@ -243,7 +247,7 @@
   if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
     
   while (MII != EndPt && !RefsInMBB.count(MII)) {
-    LiveIndex Index = LIs->getInstructionIndex(MII);
+    SlotIndex Index = LIs->getInstructionIndex(MII);
     
     // We can't insert the spill between the barrier (a call), and its
     // corresponding call frame setup.
@@ -276,9 +280,9 @@
 /// found.
 MachineBasicBlock::iterator
 PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
-                                    LiveIndex LastIdx,
+                                    SlotIndex LastIdx,
                                     SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
-                                    LiveIndex &RestoreIndex) {
+                                    SlotIndex &RestoreIndex) {
   // FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb
   // begin index accordingly.
   MachineBasicBlock::iterator Pt = MBB->end();
@@ -299,10 +303,10 @@
   // FIXME: Limit the number of instructions to examine to reduce
   // compile time?
   while (MII != EndPt) {
-    LiveIndex Index = LIs->getInstructionIndex(MII);
+    SlotIndex Index = LIs->getInstructionIndex(MII);
     if (Index > LastIdx)
       break;
-    LiveIndex Gap = LIs->findGapBeforeInstr(Index);
+    SlotIndex Gap = LIs->findGapBeforeInstr(Index);
       
     // We can't insert a restore between the barrier (a call) and its 
     // corresponding call frame teardown.
@@ -311,7 +315,7 @@
         if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
         ++MII;
       } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode());
-    } else if (Gap != LiveIndex()) {
+    } else if (Gap != SlotIndex()) {
       Pt = MII;
       RestoreIndex = Gap;
     }
@@ -344,7 +348,7 @@
   if (CurrSLI->hasAtLeastOneValue())
     CurrSValNo = CurrSLI->getValNumInfo(0);
   else
-    CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+    CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
                                        LSs->getVNInfoAllocator());
   return SS;
 }
@@ -353,9 +357,9 @@
 /// slot at the specified index.
 bool
 PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB,
-                                    unsigned Reg, LiveIndex DefIndex,
-                                    LiveIndex RestoreIndex,
-                                    LiveIndex &SpillIndex,
+                                    unsigned Reg, SlotIndex DefIndex,
+                                    SlotIndex RestoreIndex,
+                                    SlotIndex &SpillIndex,
                                     int& SS) const {
   if (!DefMBB)
     return false;
@@ -363,7 +367,7 @@
   DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
   if (I == IntervalSSMap.end())
     return false;
-  DenseMap<LiveIndex, LiveIndex>::iterator
+  DenseMap<SlotIndex, SlotIndex>::iterator
     II = Def2SpillMap.find(DefIndex);
   if (II == Def2SpillMap.end())
     return false;
@@ -384,8 +388,8 @@
 /// interval being split, and the spill and restore indicies, update the live
 /// interval of the spill stack slot.
 void
-PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, LiveIndex SpillIndex,
-                                           LiveIndex RestoreIndex) {
+PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, SlotIndex SpillIndex,
+                                           SlotIndex RestoreIndex) {
   assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
          "Expect restore in the barrier mbb");
 
@@ -398,8 +402,8 @@
   }
 
   SmallPtrSet<MachineBasicBlock*, 4> Processed;
-  LiveIndex EndIdx = LIs->getMBBEndIdx(MBB);
-  LiveRange SLR(SpillIndex, LIs->getNextSlot(EndIdx), CurrSValNo);
+  SlotIndex EndIdx = LIs->getMBBEndIdx(MBB);
+  LiveRange SLR(SpillIndex, EndIdx.getNextSlot(), CurrSValNo);
   CurrSLI->addRange(SLR);
   Processed.insert(MBB);
 
@@ -418,7 +422,7 @@
     WorkList.pop_back();
     if (Processed.count(MBB))
       continue;
-    LiveIndex Idx = LIs->getMBBStartIdx(MBB);
+    SlotIndex Idx = LIs->getMBBStartIdx(MBB);
     LR = CurrLI->getLiveRangeContaining(Idx);
     if (LR && LR->valno == ValNo) {
       EndIdx = LIs->getMBBEndIdx(MBB);
@@ -428,7 +432,7 @@
         CurrSLI->addRange(SLR);
       } else if (LR->end > EndIdx) {
         // Live range extends beyond end of mbb, process successors.
-        LiveRange SLR(Idx, LIs->getNextIndex(EndIdx), CurrSValNo);
+        LiveRange SLR(Idx, EndIdx.getNextIndex(), CurrSValNo);
         CurrSLI->addRange(SLR);
         for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
                SE = MBB->succ_end(); SI != SE; ++SI)
@@ -491,12 +495,12 @@
     }
     
     // Once we've found it, extend its VNInfo to our instruction.
-    LiveIndex DefIndex = LIs->getInstructionIndex(Walker);
-    DefIndex = LIs->getDefIndex(DefIndex);
-    LiveIndex EndIndex = LIs->getMBBEndIdx(MBB);
+    SlotIndex DefIndex = LIs->getInstructionIndex(Walker);
+    DefIndex = DefIndex.getDefIndex();
+    SlotIndex EndIndex = LIs->getMBBEndIdx(MBB);
     
     RetVNI = NewVNs[Walker];
-    LI->addRange(LiveRange(DefIndex, LIs->getNextSlot(EndIndex), RetVNI));
+    LI->addRange(LiveRange(DefIndex, EndIndex.getNextSlot(), RetVNI));
   } else if (!ContainsDefs && ContainsUses) {
     SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
     
@@ -528,12 +532,12 @@
                                               IsTopLevel, IsIntraBlock);
     }
 
-    LiveIndex UseIndex = LIs->getInstructionIndex(Walker);
-    UseIndex = LIs->getUseIndex(UseIndex);
-    LiveIndex EndIndex;
+    SlotIndex UseIndex = LIs->getInstructionIndex(Walker);
+    UseIndex = UseIndex.getUseIndex();
+    SlotIndex EndIndex;
     if (IsIntraBlock) {
       EndIndex = LIs->getInstructionIndex(UseI);
-      EndIndex = LIs->getUseIndex(EndIndex);
+      EndIndex = EndIndex.getUseIndex();
     } else
       EndIndex = LIs->getMBBEndIdx(MBB);
 
@@ -542,7 +546,7 @@
     RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
                                     NewVNs, LiveOut, Phis, false, true);
     
-    LI->addRange(LiveRange(UseIndex, LIs->getNextSlot(EndIndex), RetVNI));
+    LI->addRange(LiveRange(UseIndex, EndIndex.getNextSlot(), RetVNI));
     
     // FIXME: Need to set kills properly for inter-block stuff.
     if (RetVNI->isKill(UseIndex)) RetVNI->removeKill(UseIndex);
@@ -588,13 +592,12 @@
                                               IsTopLevel, IsIntraBlock);
     }
 
-    LiveIndex StartIndex = LIs->getInstructionIndex(Walker);
-    StartIndex = foundDef ? LIs->getDefIndex(StartIndex) :
-                            LIs->getUseIndex(StartIndex);
-    LiveIndex EndIndex;
+    SlotIndex StartIndex = LIs->getInstructionIndex(Walker);
+    StartIndex = foundDef ? StartIndex.getDefIndex() : StartIndex.getUseIndex();
+    SlotIndex EndIndex;
     if (IsIntraBlock) {
       EndIndex = LIs->getInstructionIndex(UseI);
-      EndIndex = LIs->getUseIndex(EndIndex);
+      EndIndex = EndIndex.getUseIndex();
     } else
       EndIndex = LIs->getMBBEndIdx(MBB);
 
@@ -604,7 +607,7 @@
       RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
                                       NewVNs, LiveOut, Phis, false, true);
 
-    LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI));
+    LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
     
     if (foundUse && RetVNI->isKill(StartIndex))
       RetVNI->removeKill(StartIndex);
@@ -640,9 +643,9 @@
   // assume that we are not intrablock here.
   if (Phis.count(MBB)) return Phis[MBB]; 
 
-  LiveIndex StartIndex = LIs->getMBBStartIdx(MBB);
+  SlotIndex StartIndex = LIs->getMBBStartIdx(MBB);
   VNInfo *RetVNI = Phis[MBB] =
-    LI->getNextValue(LiveIndex(), /*FIXME*/ 0, false,
+    LI->getNextValue(SlotIndex(), /*FIXME*/ 0, false,
                      LIs->getVNInfoAllocator());
 
   if (!IsIntraBlock) LiveOut[MBB] = RetVNI;
@@ -685,19 +688,19 @@
     for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I =
            IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) {
       I->second->setHasPHIKill(true);
-      LiveIndex KillIndex = LIs->getMBBEndIdx(I->first);
+      SlotIndex KillIndex = LIs->getMBBEndIdx(I->first);
       if (!I->second->isKill(KillIndex))
         I->second->addKill(KillIndex);
     }
   }
       
-  LiveIndex EndIndex;
+  SlotIndex EndIndex;
   if (IsIntraBlock) {
     EndIndex = LIs->getInstructionIndex(UseI);
-    EndIndex = LIs->getUseIndex(EndIndex);
+    EndIndex = EndIndex.getUseIndex();
   } else
     EndIndex = LIs->getMBBEndIdx(MBB);
-  LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI));
+  LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
   if (IsIntraBlock)
     RetVNI->addKill(EndIndex);
 
@@ -733,8 +736,8 @@
        DE = MRI->def_end(); DI != DE; ++DI) {
     Defs[(*DI).getParent()].insert(&*DI);
     
-    LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
-    DefIdx = LIs->getDefIndex(DefIdx);
+    SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
+    DefIdx = DefIdx.getDefIndex();
     
     assert(DI->getOpcode() != TargetInstrInfo::PHI &&
            "Following NewVN isPHIDef flag incorrect. Fix me!");
@@ -769,13 +772,13 @@
   // Add ranges for dead defs
   for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg),
        DE = MRI->def_end(); DI != DE; ++DI) {
-    LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
-    DefIdx = LIs->getDefIndex(DefIdx);
+    SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
+    DefIdx = DefIdx.getDefIndex();
     
     if (LI->liveAt(DefIdx)) continue;
     
     VNInfo* DeadVN = NewVNs[&*DI];
-    LI->addRange(LiveRange(DefIdx, LIs->getNextSlot(DefIdx), DeadVN));
+    LI->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), DeadVN));
     DeadVN->addKill(DefIdx);
   }
 
@@ -784,8 +787,8 @@
        VI != VE; ++VI) {
     VNInfo* VNI = *VI;
     for (unsigned i = 0, e = VNI->kills.size(); i != e; ++i) {
-      LiveIndex KillIdx = VNI->kills[i];
-      if (KillIdx.isPHIIndex())
+      SlotIndex KillIdx = VNI->kills[i];
+      if (KillIdx.isPHI())
         continue;
       MachineInstr *KillMI = LIs->getInstructionFromIndex(KillIdx);
       if (KillMI) {
@@ -826,14 +829,14 @@
     // Locate two-address redefinitions
     for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(),
          KE = OldVN->kills.end(); KI != KE; ++KI) {
-      assert(!KI->isPHIIndex() &&
+      assert(!KI->isPHI() &&
              "VN previously reported having no PHI kills.");
       MachineInstr* MI = LIs->getInstructionFromIndex(*KI);
       unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg);
       if (DefIdx == ~0U) continue;
       if (MI->isRegTiedToUseOperand(DefIdx)) {
         VNInfo* NextVN =
-          CurrLI->findDefinedVNInfoForRegInt(LIs->getDefIndex(*KI));
+          CurrLI->findDefinedVNInfoForRegInt(KI->getDefIndex());
         if (NextVN == OldVN) continue;
         Stack.push_back(NextVN);
       }
@@ -865,10 +868,10 @@
   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
          E = MRI->reg_end(); I != E; ++I) {
     MachineOperand& MO = I.getOperand();
-    LiveIndex InstrIdx = LIs->getInstructionIndex(&*I);
+    SlotIndex InstrIdx = LIs->getInstructionIndex(&*I);
     
-    if ((MO.isUse() && NewLI.liveAt(LIs->getUseIndex(InstrIdx))) ||
-        (MO.isDef() && NewLI.liveAt(LIs->getDefIndex(InstrIdx))))
+    if ((MO.isUse() && NewLI.liveAt(InstrIdx.getUseIndex())) ||
+        (MO.isDef() && NewLI.liveAt(InstrIdx.getDefIndex())))
       OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo()));
   }
   
@@ -893,12 +896,12 @@
 bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo,
                                       MachineInstr* DefMI,
                                       MachineBasicBlock::iterator RestorePt,
-                                      LiveIndex RestoreIdx,
+                                      SlotIndex RestoreIdx,
                                     SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
   MachineBasicBlock& MBB = *RestorePt->getParent();
   
   MachineBasicBlock::iterator KillPt = BarrierMBB->end();
-  LiveIndex KillIdx;
+  SlotIndex KillIdx;
   if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB)
     KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx);
   else
@@ -911,8 +914,8 @@
   LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx);
   
   ReconstructLiveInterval(CurrLI);
-  LiveIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
-  RematIdx = LIs->getDefIndex(RematIdx);
+  SlotIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
+  RematIdx = RematIdx.getDefIndex();
   RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx));
   
   ++NumSplits;
@@ -968,7 +971,7 @@
     if (CurrSLI->hasAtLeastOneValue())
       CurrSValNo = CurrSLI->getValNumInfo(0);
     else
-      CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+      CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
                                          LSs->getVNInfoAllocator());
   }
   
@@ -1052,11 +1055,14 @@
 /// so it would not cross the barrier that's being processed. Shrink wrap
 /// (minimize) the live interval to the last uses.
 bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) {
+  DEBUG(errs() << "Pre-alloc splitting " << LI->reg << " for " << *Barrier
+               << "  result: ");
+
   CurrLI = LI;
 
   // Find live range where current interval cross the barrier.
   LiveInterval::iterator LR =
-    CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx));
+    CurrLI->FindLiveRangeContaining(BarrierIdx.getUseIndex());
   VNInfo *ValNo = LR->valno;
 
   assert(!ValNo->isUnused() && "Val# is defined by a dead def?");
@@ -1065,8 +1071,10 @@
     ? LIs->getInstructionFromIndex(ValNo->def) : NULL;
 
   // If this would create a new join point, do not split.
-  if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent()))
+  if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) {
+    DEBUG(errs() << "FAILED (would create a new join point).\n");
     return false;
+  }
 
   // Find all references in the barrier mbb.
   SmallPtrSet<MachineInstr*, 4> RefsInMBB;
@@ -1078,21 +1086,25 @@
   }
 
   // Find a point to restore the value after the barrier.
-  LiveIndex RestoreIndex;
+  SlotIndex RestoreIndex;
   MachineBasicBlock::iterator RestorePt =
     findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex);
-  if (RestorePt == BarrierMBB->end())
+  if (RestorePt == BarrierMBB->end()) {
+    DEBUG(errs() << "FAILED (could not find a suitable restore point).\n");
     return false;
+  }
 
   if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI))
     if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt,
-                      RestoreIndex, RefsInMBB))
-    return true;
+                      RestoreIndex, RefsInMBB)) {
+      DEBUG(errs() << "success (remat).\n");
+      return true;
+    }
 
   // Add a spill either before the barrier or after the definition.
   MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL;
   const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg);
-  LiveIndex SpillIndex;
+  SlotIndex SpillIndex;
   MachineInstr *SpillMI = NULL;
   int SS = -1;
   if (!ValNo->isDefAccurate()) {
@@ -1103,8 +1115,10 @@
     } else {
       MachineBasicBlock::iterator SpillPt = 
         findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex);
-      if (SpillPt == BarrierMBB->begin())
+      if (SpillPt == BarrierMBB->begin()) {
+        DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
         return false; // No gap to insert spill.
+      }
       // Add spill.
     
       SS = CreateSpillStackSlot(CurrLI->reg, RC);
@@ -1116,8 +1130,10 @@
                                  RestoreIndex, SpillIndex, SS)) {
     // If it's already split, just restore the value. There is no need to spill
     // the def again.
-    if (!DefMI)
+    if (!DefMI) {
+      DEBUG(errs() << "FAILED (def is dead).\n");
       return false; // Def is dead. Do nothing.
+    }
     
     if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier,
                              BarrierMBB, SS, RefsInMBB))) {
@@ -1129,12 +1145,16 @@
         // Add spill after the def and the last use before the barrier.
         SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI,
                                  RefsInMBB, SpillIndex);
-        if (SpillPt == DefMBB->begin())
+        if (SpillPt == DefMBB->begin()) {
+          DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
           return false; // No gap to insert spill.
+        }
       } else {
         SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex);
-        if (SpillPt == DefMBB->end())
+        if (SpillPt == DefMBB->end()) {
+          DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
           return false; // No gap to insert spill.
+        }
       }
       // Add spill. 
       SS = CreateSpillStackSlot(CurrLI->reg, RC);
@@ -1162,18 +1182,19 @@
   }
 
   // Update spill stack slot live interval.
-  UpdateSpillSlotInterval(ValNo, LIs->getNextSlot(LIs->getUseIndex(SpillIndex)),
-                          LIs->getDefIndex(RestoreIndex));
+  UpdateSpillSlotInterval(ValNo, SpillIndex.getUseIndex().getNextSlot(),
+                          RestoreIndex.getDefIndex());
 
   ReconstructLiveInterval(CurrLI);
 
   if (!FoldedRestore) {
-    LiveIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
-    RestoreIdx = LIs->getDefIndex(RestoreIdx);
+    SlotIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
+    RestoreIdx = RestoreIdx.getDefIndex();
     RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RestoreIdx));
   }
   
   ++NumSplits;
+  DEBUG(errs() << "success.\n");
   return true;
 }
 
@@ -1254,8 +1275,8 @@
     // reaching definition (VNInfo).
     for (MachineRegisterInfo::use_iterator UI = MRI->use_begin((*LI)->reg),
          UE = MRI->use_end(); UI != UE; ++UI) {
-      LiveIndex index = LIs->getInstructionIndex(&*UI);
-      index = LIs->getUseIndex(index);
+      SlotIndex index = LIs->getInstructionIndex(&*UI);
+      index = index.getUseIndex();
       
       const LiveRange* LR = (*LI)->getLiveRangeContaining(index);
       VNUseCount[LR->valno].insert(&*UI);
@@ -1404,7 +1425,7 @@
   if (LR->valno->hasPHIKill())
     return false;
   
-  LiveIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
+  SlotIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
   if (LR->end < MBBEnd)
     return false;
   
@@ -1467,6 +1488,7 @@
   TII    = TM->getInstrInfo();
   MFI    = MF.getFrameInfo();
   MRI    = &MF.getRegInfo();
+  SIs    = &getAnalysis<SlotIndexes>();
   LIs    = &getAnalysis<LiveIntervals>();
   LSs    = &getAnalysis<LiveStacks>();
   VRM    = &getAnalysis<VirtRegMap>();
diff --git a/lib/CodeGen/ProcessImplicitDefs.cpp b/lib/CodeGen/ProcessImplicitDefs.cpp
new file mode 100644
index 0000000..48567a0
--- /dev/null
+++ b/lib/CodeGen/ProcessImplicitDefs.cpp
@@ -0,0 +1,231 @@
+//===---------------------- ProcessImplicitDefs.cpp -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "processimplicitdefs"
+
+#include "llvm/CodeGen/ProcessImplicitDefs.h"
+
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+
+using namespace llvm;
+
+char ProcessImplicitDefs::ID = 0;
+static RegisterPass<ProcessImplicitDefs> X("processimpdefs",
+                                           "Process Implicit Definitions.");
+
+void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  AU.addPreserved<AliasAnalysis>();
+  AU.addPreserved<LiveVariables>();
+  AU.addRequired<LiveVariables>();
+  AU.addPreservedID(MachineLoopInfoID);
+  AU.addPreservedID(MachineDominatorsID);
+  AU.addPreservedID(TwoAddressInstructionPassID);
+  AU.addPreservedID(PHIEliminationID);
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI,
+                                                 unsigned Reg, unsigned OpIdx,
+                                                 const TargetInstrInfo *tii_) {
+  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+  if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+      Reg == SrcReg)
+    return true;
+
+  if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
+    return true;
+  if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+    return true;
+  return false;
+}
+
+/// 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.
+bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &fn) {
+
+  DEBUG(errs() << "********** PROCESS IMPLICIT DEFS **********\n"
+               << "********** Function: "
+               << ((Value*)fn.getFunction())->getName() << '\n');
+
+  bool Changed = false;
+
+  const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo();
+  const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo();
+  MachineRegisterInfo *mri_ = &fn.getRegInfo();
+
+  LiveVariables *lv_ = &getAnalysis<LiveVariables>();
+
+  SmallSet<unsigned, 8> ImpDefRegs;
+  SmallVector<MachineInstr*, 8> ImpDefMIs;
+  MachineBasicBlock *Entry = fn.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();
+        ImpDefRegs.insert(Reg);
+        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+          for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
+            ImpDefRegs.insert(*SS);
+        }
+        ImpDefMIs.push_back(MI);
+        continue;
+      }
+
+      if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
+        MachineOperand &MO = MI->getOperand(2);
+        if (ImpDefRegs.count(MO.getReg())) {
+          // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2
+          // This is an identity copy, eliminate it now.
+          if (MO.isKill()) {
+            LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
+            vi.removeKill(MI);
+          }
+          MI->eraseFromParent();
+          Changed = true;
+          continue;
+        }
+      }
+
+      bool ChangedToImpDef = false;
+      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+        MachineOperand& MO = MI->getOperand(i);
+        if (!MO.isReg() || !MO.isUse() || MO.isUndef())
+          continue;
+        unsigned Reg = MO.getReg();
+        if (!Reg)
+          continue;
+        if (!ImpDefRegs.count(Reg))
+          continue;
+        // Use is a copy, just turn it into an implicit_def.
+        if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) {
+          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);
+            LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
+            vi.removeKill(MI);
+          }
+          ChangedToImpDef = true;
+          Changed = true;
+          break;
+        }
+
+        Changed = true;
+        MO.setIsUndef();
+        if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
+          // Make sure other uses of 
+          for (unsigned j = i+1; j != e; ++j) {
+            MachineOperand &MOJ = MI->getOperand(j);
+            if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
+              MOJ.setIsUndef();
+          }
+          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) ||
+          !ImpDefRegs.count(Reg)) {
+        // Delete all "local" implicit_def's. That include those which define
+        // physical registers since they cannot be liveout.
+        MI->eraseFromParent();
+        Changed = true;
+        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;
+
+      // The only implicit_def which we want to keep are those that are live
+      // out of its block.
+      MI->eraseFromParent();
+      Changed = true;
+
+      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;
+
+        // Turn a copy use into an implicit_def.
+        unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+        if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+            Reg == SrcReg) {
+          RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
+          for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
+            RMI->RemoveOperand(j);
+          continue;
+        }
+
+        const TargetRegisterClass* RC = mri_->getRegClass(Reg);
+        unsigned NewVReg = mri_->createVirtualRegister(RC);
+        RMO.setReg(NewVReg);
+        RMO.setIsUndef();
+        RMO.setIsKill();
+      }
+    }
+    ImpDefRegs.clear();
+    ImpDefMIs.clear();
+  }
+
+  return Changed;
+}
+
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 836a3f0..6930abf 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -145,6 +145,7 @@
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
       AU.addRequired<LiveIntervals>();
+      AU.addPreserved<SlotIndexes>();
       if (StrongPHIElim)
         AU.addRequiredID(StrongPHIEliminationID);
       // Make sure PassManager knows which analyses to make available
@@ -175,11 +176,11 @@
 
     /// processActiveIntervals - expire old intervals and move non-overlapping
     /// ones to the inactive list.
-    void processActiveIntervals(LiveIndex CurPoint);
+    void processActiveIntervals(SlotIndex CurPoint);
 
     /// processInactiveIntervals - expire old intervals and move overlapping
     /// ones to the active list.
-    void processInactiveIntervals(LiveIndex CurPoint);
+    void processInactiveIntervals(SlotIndex CurPoint);
 
     /// hasNextReloadInterval - Return the next liveinterval that's being
     /// defined by a reload from the same SS as the specified one.
@@ -365,7 +366,7 @@
     return Reg;
 
   VNInfo *vni = cur.begin()->valno;
-  if ((vni->def == LiveIndex()) ||
+  if ((vni->def == SlotIndex()) ||
       vni->isUnused() || !vni->isDefAccurate())
     return Reg;
   MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
@@ -402,7 +403,7 @@
         if (!O.isKill())
           continue;
         MachineInstr *MI = &*I;
-        if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI))))
+        if (SrcLI.liveAt(li_->getInstructionIndex(MI).getDefIndex()))
           O.setIsKill(false);
       }
     }
@@ -479,10 +480,17 @@
 
   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
     if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
-      mri_->setPhysRegUsed(i->second->reg);
-      fixed_.push_back(std::make_pair(i->second, i->second->begin()));
-    } else
-      unhandled_.push(i->second);
+      if (!i->second->empty()) {
+        mri_->setPhysRegUsed(i->second->reg);
+        fixed_.push_back(std::make_pair(i->second, i->second->begin()));
+      }
+    } else {
+      if (i->second->empty()) {
+        assignRegOrStackSlotAtInterval(i->second);
+      }
+      else
+        unhandled_.push(i->second);
+    }
   }
 }
 
@@ -502,13 +510,13 @@
     ++NumIters;
     DEBUG(errs() << "\n*** CURRENT ***: " << *cur << '\n');
 
-    if (!cur->empty()) {
-      processActiveIntervals(cur->beginIndex());
-      processInactiveIntervals(cur->beginIndex());
+    assert(!cur->empty() && "Empty interval in unhandled set.");
 
-      assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
-             "Can only allocate virtual registers!");
-    }
+    processActiveIntervals(cur->beginIndex());
+    processInactiveIntervals(cur->beginIndex());
+
+    assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
+           "Can only allocate virtual registers!");
 
     // Allocating a virtual register. try to find a free
     // physical register or spill an interval (possibly this one) in order to
@@ -585,7 +593,7 @@
 
 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 /// to the inactive list.
-void RALinScan::processActiveIntervals(LiveIndex CurPoint)
+void RALinScan::processActiveIntervals(SlotIndex CurPoint)
 {
   DEBUG(errs() << "\tprocessing active intervals:\n");
 
@@ -631,7 +639,7 @@
 
 /// processInactiveIntervals - expire old intervals and move overlapping
 /// ones to the active list.
-void RALinScan::processInactiveIntervals(LiveIndex CurPoint)
+void RALinScan::processInactiveIntervals(SlotIndex CurPoint)
 {
   DEBUG(errs() << "\tprocessing inactive intervals:\n");
 
@@ -712,7 +720,7 @@
   return IP.end();
 }
 
-static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, LiveIndex Point){
+static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, SlotIndex Point){
   for (unsigned i = 0, e = V.size(); i != e; ++i) {
     RALinScan::IntervalPtr &IP = V[i];
     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
@@ -738,7 +746,7 @@
   if (SI.hasAtLeastOneValue())
     VNI = SI.getValNumInfo(0);
   else
-    VNI = SI.getNextValue(LiveIndex(), 0, false,
+    VNI = SI.getNextValue(SlotIndex(), 0, false,
                           ls_->getVNInfoAllocator());
 
   LiveInterval &RI = li_->getInterval(cur->reg);
@@ -906,7 +914,7 @@
   backUpRegUses();
 
   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
-  LiveIndex StartPosition = cur->beginIndex();
+  SlotIndex StartPosition = cur->beginIndex();
   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 
   // If start of this live interval is defined by a move instruction and its
@@ -916,7 +924,7 @@
   // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
   if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
     VNInfo *vni = cur->begin()->valno;
-    if ((vni->def != LiveIndex()) && !vni->isUnused() &&
+    if ((vni->def != SlotIndex()) && !vni->isUnused() &&
          vni->isDefAccurate()) {
       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
@@ -1118,6 +1126,7 @@
         DowngradedRegs.clear();
         assignRegOrStackSlotAtInterval(cur);
       } else {
+        assert(false && "Ran out of registers during register allocation!");
         llvm_report_error("Ran out of registers during register allocation!");
       }
       return;
@@ -1172,7 +1181,7 @@
       LiveInterval *ReloadLi = added[i];
       if (ReloadLi->weight == HUGE_VALF &&
           li_->getApproximateInstructionCount(*ReloadLi) == 0) {
-        LiveIndex ReloadIdx = ReloadLi->beginIndex();
+        SlotIndex ReloadIdx = ReloadLi->beginIndex();
         MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
         int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
         if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
@@ -1242,7 +1251,7 @@
     spilled.insert(sli->reg);
   }
 
-  LiveIndex earliestStart = earliestStartInterval->beginIndex();
+  SlotIndex earliestStart = earliestStartInterval->beginIndex();
 
   DEBUG(errs() << "\t\trolling back to: " << earliestStart << '\n');
 
@@ -1323,7 +1332,7 @@
     LiveInterval *ReloadLi = added[i];
     if (ReloadLi->weight == HUGE_VALF &&
         li_->getApproximateInstructionCount(*ReloadLi) == 0) {
-      LiveIndex ReloadIdx = ReloadLi->beginIndex();
+      SlotIndex ReloadIdx = ReloadLi->beginIndex();
       MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
       int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
       if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index a6e33fa..5757e47 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -85,6 +85,8 @@
 
     /// PBQP analysis usage.
     virtual void getAnalysisUsage(AnalysisUsage &au) const {
+      au.addRequired<SlotIndexes>();
+      au.addPreserved<SlotIndexes>();
       au.addRequired<LiveIntervals>();
       //au.addRequiredID(SplitCriticalEdgesID);
       au.addRequired<RegisterCoalescer>();
@@ -684,7 +686,7 @@
     vni = stackInterval.getValNumInfo(0);
   else
     vni = stackInterval.getNextValue(
-      LiveIndex(), 0, false, lss->getVNInfoAllocator());
+      SlotIndex(), 0, false, lss->getVNInfoAllocator());
 
   LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
   stackInterval.MergeRangesInAsValue(rhsInterval, vni);
@@ -832,7 +834,7 @@
   tm = &mf->getTarget();
   tri = tm->getRegisterInfo();
   tii = tm->getInstrInfo();
-  mri = &mf->getRegInfo();
+  mri = &mf->getRegInfo(); 
 
   lis = &getAnalysis<LiveIntervals>();
   lss = &getAnalysis<LiveStacks>();
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 2aa6307..e711a06 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -76,6 +76,7 @@
   AU.addRequired<AliasAnalysis>();
   AU.addRequired<LiveIntervals>();
   AU.addPreserved<LiveIntervals>();
+  AU.addPreserved<SlotIndexes>();
   AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineLoopInfo>();
   AU.addPreservedID(MachineDominatorsID);
@@ -105,7 +106,7 @@
 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
                                                     LiveInterval &IntB,
                                                     MachineInstr *CopyMI) {
-  LiveIndex CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+  SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
 
   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
   // the example above.
@@ -120,7 +121,7 @@
   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 
   // AValNo is the value number in A that defines the copy, A3 in the example.
-  LiveIndex CopyUseIdx = li_->getUseIndex(CopyIdx);
+  SlotIndex CopyUseIdx = CopyIdx.getUseIndex();
   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
   assert(ALR != IntA.end() && "Live range not found!");
   VNInfo *AValNo = ALR->valno;
@@ -158,13 +159,13 @@
 
   // Get the LiveRange in IntB that this value number starts with.
   LiveInterval::iterator ValLR =
-    IntB.FindLiveRangeContaining(li_->getPrevSlot(AValNo->def));
+    IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
   assert(ValLR != IntB.end() && "Live range not found!");
 
   // Make sure that the end of the live range is inside the same block as
   // CopyMI.
   MachineInstr *ValLREndInst =
-    li_->getInstructionFromIndex(li_->getPrevSlot(ValLR->end));
+    li_->getInstructionFromIndex(ValLR->end.getPrevSlot());
   if (!ValLREndInst ||
       ValLREndInst->getParent() != CopyMI->getParent()) return false;
 
@@ -193,7 +194,7 @@
       IntB.print(errs(), tri_);
     });
 
-  LiveIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
+  SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
   // We are about to delete CopyMI, so need to remove it as the 'instruction
   // that defines this value #'. Update the the valnum with the new defining
   // instruction #.
@@ -306,8 +307,8 @@
 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
                                                         LiveInterval &IntB,
                                                         MachineInstr *CopyMI) {
-  LiveIndex CopyIdx =
-    li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+  SlotIndex CopyIdx =
+    li_->getInstructionIndex(CopyMI).getDefIndex();
 
   // FIXME: For now, only eliminate the copy by commuting its def when the
   // source register is a virtual register. We want to guard against cases
@@ -330,7 +331,7 @@
 
   // AValNo is the value number in A that defines the copy, A3 in the example.
   LiveInterval::iterator ALR =
-    IntA.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx));
+    IntA.FindLiveRangeContaining(CopyIdx.getUseIndex()); // 
 
   assert(ALR != IntA.end() && "Live range not found!");
   VNInfo *AValNo = ALR->valno;
@@ -376,7 +377,7 @@
   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
          UE = mri_->use_end(); UI != UE; ++UI) {
     MachineInstr *UseMI = &*UI;
-    LiveIndex UseIdx = li_->getInstructionIndex(UseMI);
+    SlotIndex UseIdx = li_->getInstructionIndex(UseMI);
     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
     if (ULR == IntA.end())
       continue;
@@ -401,7 +402,7 @@
   bool BHasPHIKill = BValNo->hasPHIKill();
   SmallVector<VNInfo*, 4> BDeadValNos;
   VNInfo::KillSet BKills;
-  std::map<LiveIndex, LiveIndex> BExtend;
+  std::map<SlotIndex, SlotIndex> BExtend;
 
   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
   // A = or A, B
@@ -428,7 +429,7 @@
     ++UI;
     if (JoinedCopies.count(UseMI))
       continue;
-    LiveIndex UseIdx= li_->getUseIndex(li_->getInstructionIndex(UseMI));
+    SlotIndex UseIdx = li_->getInstructionIndex(UseMI).getUseIndex();
     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
     if (ULR == IntA.end() || ULR->valno != AValNo)
       continue;
@@ -439,7 +440,7 @@
       if (Extended)
         UseMO.setIsKill(false);
       else
-        BKills.push_back(li_->getNextSlot(UseIdx));
+        BKills.push_back(UseIdx.getDefIndex());
     }
     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
@@ -448,7 +449,7 @@
       // This copy will become a noop. If it's defining a new val#,
       // remove that val# as well. However this live range is being
       // extended to the end of the existing live range defined by the copy.
-      LiveIndex DefIdx = li_->getDefIndex(UseIdx);
+      SlotIndex DefIdx = UseIdx.getDefIndex();
       const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
       BHasPHIKill |= DLR->valno->hasPHIKill();
       assert(DLR->valno->def == DefIdx);
@@ -495,8 +496,8 @@
   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
        AI != AE; ++AI) {
     if (AI->valno != AValNo) continue;
-    LiveIndex End = AI->end;
-    std::map<LiveIndex, LiveIndex>::iterator
+    SlotIndex End = AI->end;
+    std::map<SlotIndex, SlotIndex>::iterator
       EI = BExtend.find(End);
     if (EI != BExtend.end())
       End = EI->second;
@@ -507,7 +508,7 @@
     if (BHasSubRegs) {
       for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
         LiveInterval &SRLI = li_->getInterval(*SR);
-        SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator());
+        SRLI.MergeInClobberRange(*li_, AI->start, End, li_->getVNInfoAllocator());
       }
     }
   }
@@ -551,7 +552,7 @@
 /// from a physical register live interval as well as from the live intervals
 /// of its sub-registers.
 static void removeRange(LiveInterval &li,
-                        LiveIndex Start, LiveIndex End,
+                        SlotIndex Start, SlotIndex End,
                         LiveIntervals *li_, const TargetRegisterInfo *tri_) {
   li.removeRange(Start, End, true);
   if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
@@ -559,8 +560,9 @@
       if (!li_->hasInterval(*SR))
         continue;
       LiveInterval &sli = li_->getInterval(*SR);
-      LiveIndex RemoveStart = Start;
-      LiveIndex RemoveEnd = Start;
+      SlotIndex RemoveStart = Start;
+      SlotIndex RemoveEnd = Start;
+
       while (RemoveEnd != End) {
         LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart);
         if (LR == sli.end())
@@ -577,14 +579,14 @@
 /// as the copy instruction, trim the live interval to the last use and return
 /// true.
 bool
-SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(LiveIndex CopyIdx,
+SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
                                                     MachineBasicBlock *CopyMBB,
                                                     LiveInterval &li,
                                                     const LiveRange *LR) {
-  LiveIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
-  LiveIndex LastUseIdx;
+  SlotIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
+  SlotIndex LastUseIdx;
   MachineOperand *LastUse =
-    lastRegisterUse(LR->start, li_->getPrevSlot(CopyIdx), li.reg, LastUseIdx);
+    lastRegisterUse(LR->start, CopyIdx.getPrevSlot(), li.reg, LastUseIdx);
   if (LastUse) {
     MachineInstr *LastUseMI = LastUse->getParent();
     if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
@@ -603,8 +605,8 @@
     // There are uses before the copy, just shorten the live range to the end
     // of last use.
     LastUse->setIsKill();
-    removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
-    LR->valno->addKill(li_->getNextSlot(LastUseIdx));
+    removeRange(li, LastUseIdx.getDefIndex(), LR->end, li_, tri_);
+    LR->valno->addKill(LastUseIdx.getDefIndex());
     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
     if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
         DstReg == li.reg) {
@@ -617,7 +619,7 @@
 
   // Is it livein?
   if (LR->start <= MBBStart && LR->end > MBBStart) {
-    if (LR->start == LiveIndex()) {
+    if (LR->start == li_->getZeroIndex()) {
       assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
       // Live-in to the function but dead. Remove it from entry live-in set.
       mf_->begin()->removeLiveIn(li.reg);
@@ -634,7 +636,7 @@
                                                        unsigned DstReg,
                                                        unsigned DstSubIdx,
                                                        MachineInstr *CopyMI) {
-  LiveIndex CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI));
+  SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getUseIndex();
   LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
   assert(SrcLR != SrcInt.end() && "Live range not found!");
   VNInfo *ValNo = SrcLR->valno;
@@ -683,7 +685,7 @@
       return false;
   }
 
-  LiveIndex DefIdx = li_->getDefIndex(CopyIdx);
+  SlotIndex DefIdx = CopyIdx.getDefIndex();
   const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
   DLR->valno->setCopy(0);
   // Don't forget to update sub-register intervals.
@@ -716,7 +718,7 @@
     // should mark it dead:
     if (DefMI->getParent() == MBB) {
       DefMI->addRegisterDead(SrcInt.reg, tri_);
-      SrcLR->end = li_->getNextSlot(SrcLR->start);
+      SrcLR->end = SrcLR->start.getNextSlot();
     }
   }
 
@@ -815,8 +817,8 @@
         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
          allocatableRegs_[CopyDstReg])) {
       LiveInterval &LI = li_->getInterval(CopyDstReg);
-      LiveIndex DefIdx =
-        li_->getDefIndex(li_->getInstructionIndex(UseMI));
+      SlotIndex DefIdx =
+        li_->getInstructionIndex(UseMI).getDefIndex();
       if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
         if (DLR->valno->def == DefIdx)
           DLR->valno->setCopy(UseMI);
@@ -835,12 +837,12 @@
     if (!UseMO.isKill())
       continue;
     MachineInstr *UseMI = UseMO.getParent();
-    LiveIndex UseIdx =
-      li_->getUseIndex(li_->getInstructionIndex(UseMI));
+    SlotIndex UseIdx =
+      li_->getInstructionIndex(UseMI).getUseIndex();
     const LiveRange *LR = LI.getLiveRangeContaining(UseIdx);
     if (!LR ||
-        (!LR->valno->isKill(li_->getNextSlot(UseIdx)) &&
-         LR->valno->def != li_->getNextSlot(UseIdx))) {
+        (!LR->valno->isKill(UseIdx.getDefIndex()) &&
+         LR->valno->def != UseIdx.getDefIndex())) {
       // Interesting problem. After coalescing reg1027's def and kill are both
       // at the same point:  %reg1027,0.000000e+00 = [56,814:0)  0@70-(814)
       //
@@ -881,16 +883,16 @@
 /// Return true if live interval is removed.
 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
                                                         MachineInstr *CopyMI) {
-  LiveIndex CopyIdx = li_->getInstructionIndex(CopyMI);
+  SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
   LiveInterval::iterator MLR =
-    li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
+    li.FindLiveRangeContaining(CopyIdx.getDefIndex());
   if (MLR == li.end())
     return false;  // Already removed by ShortenDeadCopySrcLiveRange.
-  LiveIndex RemoveStart = MLR->start;
-  LiveIndex RemoveEnd = MLR->end;
-  LiveIndex DefIdx = li_->getDefIndex(CopyIdx);
+  SlotIndex RemoveStart = MLR->start;
+  SlotIndex RemoveEnd = MLR->end;
+  SlotIndex DefIdx = CopyIdx.getDefIndex();
   // Remove the liverange that's defined by this.
-  if (RemoveStart == DefIdx && RemoveEnd == li_->getNextSlot(DefIdx)) {
+  if (RemoveStart == DefIdx && RemoveEnd == DefIdx.getStoreIndex()) {
     removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
     return removeIntervalIfEmpty(li, li_, tri_);
   }
@@ -901,7 +903,7 @@
 /// the val# it defines. If the live interval becomes empty, remove it as well.
 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
                                              MachineInstr *DefMI) {
-  LiveIndex DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI));
+  SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex();
   LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
   if (DefIdx != MLR->valno->def)
     return false;
@@ -912,10 +914,10 @@
 /// PropagateDeadness - Propagate the dead marker to the instruction which
 /// defines the val#.
 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
-                              LiveIndex &LRStart, LiveIntervals *li_,
+                              SlotIndex &LRStart, LiveIntervals *li_,
                               const TargetRegisterInfo* tri_) {
   MachineInstr *DefMI =
-    li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
+    li_->getInstructionFromIndex(LRStart.getDefIndex());
   if (DefMI && DefMI != CopyMI) {
     int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false);
     if (DeadIdx != -1)
@@ -923,7 +925,7 @@
     else
       DefMI->addOperand(MachineOperand::CreateReg(li.reg,
                    /*def*/true, /*implicit*/true, /*kill*/false, /*dead*/true));
-    LRStart = li_->getNextSlot(LRStart);
+    LRStart = LRStart.getNextSlot();
   }
 }
 
@@ -934,8 +936,8 @@
 bool
 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
                                                       MachineInstr *CopyMI) {
-  LiveIndex CopyIdx = li_->getInstructionIndex(CopyMI);
-  if (CopyIdx == LiveIndex()) {
+  SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
+  if (CopyIdx == SlotIndex()) {
     // FIXME: special case: function live in. It can be a general case if the
     // first instruction index starts at > 0 value.
     assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
@@ -948,13 +950,13 @@
   }
 
   LiveInterval::iterator LR =
-    li.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx));
+    li.FindLiveRangeContaining(CopyIdx.getPrevIndex().getStoreIndex());
   if (LR == li.end())
     // Livein but defined by a phi.
     return false;
 
-  LiveIndex RemoveStart = LR->start;
-  LiveIndex RemoveEnd = li_->getNextSlot(li_->getDefIndex(CopyIdx));
+  SlotIndex RemoveStart = LR->start;
+  SlotIndex RemoveEnd = CopyIdx.getStoreIndex();
   if (LR->end > RemoveEnd)
     // More uses past this copy? Nothing to do.
     return false;
@@ -974,7 +976,7 @@
     // If the live range starts in another mbb and the copy mbb is not a fall
     // through mbb, then we can only cut the range from the beginning of the
     // copy mbb.
-    RemoveStart = li_->getNextSlot(li_->getMBBStartIdx(CopyMBB));
+    RemoveStart = li_->getMBBStartIdx(CopyMBB).getNextIndex().getBaseIndex();
 
   if (LR->valno->def == RemoveStart) {
     // If the def MI defines the val# and this copy is the only kill of the
@@ -1030,14 +1032,14 @@
 
   // If the virtual register live interval extends into a loop, turn down
   // aggressiveness.
-  LiveIndex CopyIdx =
-    li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+  SlotIndex CopyIdx =
+    li_->getInstructionIndex(CopyMI).getDefIndex();
   const MachineLoop *L = loopInfo->getLoopFor(CopyMBB);
   if (!L) {
     // Let's see if the virtual register live interval extends into the loop.
     LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx);
     assert(DLR != DstInt.end() && "Live range not found!");
-    DLR = DstInt.FindLiveRangeContaining(li_->getNextSlot(DLR->end));
+    DLR = DstInt.FindLiveRangeContaining(DLR->end.getNextSlot());
     if (DLR != DstInt.end()) {
       CopyMBB = li_->getMBBFromIndex(DLR->start);
       L = loopInfo->getLoopFor(CopyMBB);
@@ -1047,7 +1049,7 @@
   if (!L || Length <= Threshold)
     return true;
 
-  LiveIndex UseIdx = li_->getUseIndex(CopyIdx);
+  SlotIndex UseIdx = CopyIdx.getUseIndex();
   LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
   MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
   if (loopInfo->getLoopFor(SMBB) != L) {
@@ -1060,7 +1062,7 @@
       if (SuccMBB == CopyMBB)
         continue;
       if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB),
-                          li_->getNextSlot(li_->getMBBEndIdx(SuccMBB))))
+                      li_->getMBBEndIdx(SuccMBB).getNextIndex().getBaseIndex()))
         return false;
     }
   }
@@ -1091,12 +1093,12 @@
 
   // If the virtual register live interval is defined or cross a loop, turn
   // down aggressiveness.
-  LiveIndex CopyIdx =
-    li_->getDefIndex(li_->getInstructionIndex(CopyMI));
-  LiveIndex UseIdx = li_->getUseIndex(CopyIdx);
+  SlotIndex CopyIdx =
+    li_->getInstructionIndex(CopyMI).getDefIndex();
+  SlotIndex UseIdx = CopyIdx.getUseIndex();
   LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
   assert(SLR != SrcInt.end() && "Live range not found!");
-  SLR = SrcInt.FindLiveRangeContaining(li_->getPrevSlot(SLR->start));
+  SLR = SrcInt.FindLiveRangeContaining(SLR->start.getPrevSlot());
   if (SLR == SrcInt.end())
     return true;
   MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
@@ -1116,7 +1118,7 @@
       if (PredMBB == SMBB)
         continue;
       if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB),
-                          li_->getNextSlot(li_->getMBBEndIdx(PredMBB))))
+                      li_->getMBBEndIdx(PredMBB).getNextIndex().getBaseIndex()))
         return false;
     }
   }
@@ -1705,7 +1707,7 @@
 
     // Update the liveintervals of sub-registers.
     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
-      li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
+      li_->getOrCreateInterval(*AS).MergeInClobberRanges(*li_, *ResSrcInt,
                                                  li_->getVNInfoAllocator());
   }
 
@@ -1867,7 +1869,7 @@
 /// is live at the given point.
 bool SimpleRegisterCoalescing::ValueLiveAt(LiveInterval::iterator LRItr,
                                            LiveInterval::iterator LREnd,
-                                           LiveIndex defPoint) const {
+                                           SlotIndex defPoint) const {
   for (const VNInfo *valno = LRItr->valno;
        (LRItr != LREnd) && (LRItr->valno == valno); ++LRItr) {
     if (LRItr->contains(defPoint))
@@ -2047,7 +2049,7 @@
   // Update the liveintervals of sub-registers.
   if (TargetRegisterInfo::isPhysicalRegister(LHS.reg))
     for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS)
-      li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS,
+      li_->getOrCreateInterval(*AS).MergeInClobberRanges(*li_, LHS,
                                                     li_->getVNInfoAllocator());
 
   return true;
@@ -2148,7 +2150,7 @@
     } else {
       // It was defined as a copy from the LHS, find out what value # it is.
       RHSValNoInfo =
-        LHS.getLiveRangeContaining(li_->getPrevSlot(RHSValNoInfo0->def))->valno;
+        LHS.getLiveRangeContaining(RHSValNoInfo0->def.getPrevSlot())->valno;
       RHSValID = RHSValNoInfo->id;
       RHSVal0DefinedFromLHS = RHSValID;
     }
@@ -2212,7 +2214,7 @@
 
       // Figure out the value # from the RHS.
       LHSValsDefinedFromRHS[VNI]=
-        RHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno;
+        RHS.getLiveRangeContaining(VNI->def.getPrevSlot())->valno;
     }
 
     // Loop over the value numbers of the RHS, seeing if any are defined from
@@ -2230,7 +2232,7 @@
 
       // Figure out the value # from the LHS.
       RHSValsDefinedFromLHS[VNI]=
-        LHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno;
+        LHS.getLiveRangeContaining(VNI->def.getPrevSlot())->valno;
     }
 
     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
@@ -2494,11 +2496,11 @@
 /// lastRegisterUse - Returns the last use of the specific register between
 /// cycles Start and End or NULL if there are no uses.
 MachineOperand *
-SimpleRegisterCoalescing::lastRegisterUse(LiveIndex Start,
-                                          LiveIndex End,
+SimpleRegisterCoalescing::lastRegisterUse(SlotIndex Start,
+                                          SlotIndex End,
                                           unsigned Reg,
-                                          LiveIndex &UseIdx) const{
-  UseIdx = LiveIndex();
+                                          SlotIndex &UseIdx) const{
+  UseIdx = SlotIndex();
   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     MachineOperand *LastUse = NULL;
     for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg),
@@ -2510,22 +2512,24 @@
           SrcReg == DstReg)
         // Ignore identity copies.
         continue;
-      LiveIndex Idx = li_->getInstructionIndex(UseMI);
+      SlotIndex Idx = li_->getInstructionIndex(UseMI);
+      // FIXME: Should this be Idx != UseIdx? SlotIndex() will return something
+      // that compares higher than any other interval.
       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
         LastUse = &Use;
-        UseIdx = li_->getUseIndex(Idx);
+        UseIdx = Idx.getUseIndex();
       }
     }
     return LastUse;
   }
 
-  LiveIndex s = Start;
-  LiveIndex e = li_->getBaseIndex(li_->getPrevSlot(End));
+  SlotIndex s = Start;
+  SlotIndex e = End.getPrevSlot().getBaseIndex();
   while (e >= s) {
     // Skip deleted instructions
     MachineInstr *MI = li_->getInstructionFromIndex(e);
-    while (e != LiveIndex() && li_->getPrevIndex(e) >= s && !MI) {
-      e = li_->getPrevIndex(e);
+    while (e != SlotIndex() && e.getPrevIndex() >= s && !MI) {
+      e = e.getPrevIndex();
       MI = li_->getInstructionFromIndex(e);
     }
     if (e < s || MI == NULL)
@@ -2539,12 +2543,12 @@
         MachineOperand &Use = MI->getOperand(i);
         if (Use.isReg() && Use.isUse() && Use.getReg() &&
             tri_->regsOverlap(Use.getReg(), Reg)) {
-          UseIdx = li_->getUseIndex(e);
+          UseIdx = e.getUseIndex();
           return &Use;
         }
       }
 
-    e = li_->getPrevIndex(e);
+    e = e.getPrevIndex();
   }
 
   return NULL;
@@ -2568,7 +2572,7 @@
 static bool isZeroLengthInterval(LiveInterval *li, LiveIntervals *li_) {
   for (LiveInterval::Ranges::const_iterator
          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
-    if (li_->getPrevIndex(i->end) > i->start)
+    if (i->end.getPrevIndex() > i->start)
       return false;
   return true;
 }
@@ -2579,7 +2583,7 @@
   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
        mbbi != mbbe; ++mbbi) {
     MachineBasicBlock* MBB = mbbi;
-    LiveIndex MBBEnd = li_->getMBBEndIdx(MBB);
+    SlotIndex MBBEnd = li_->getMBBEndIdx(MBB);
     MachineLoop* loop = loopInfo->getLoopFor(MBB);
     unsigned loopDepth = loop ? loop->getLoopDepth() : 0;
     bool isExiting = loop ? loop->isLoopExiting(MBB) : false;
@@ -2621,7 +2625,7 @@
         float Weight = li_->getSpillWeight(HasDef, HasUse, loopDepth);
         if (HasDef && isExiting) {
           // Looks like this is a loop count variable update.
-          LiveIndex DefIdx = li_->getDefIndex(li_->getInstructionIndex(MI));
+          SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex();
           const LiveRange *DLR =
             li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
           if (DLR->end > MBBEnd)
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h
index 7f282a4..78f8a9a 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.h
+++ b/lib/CodeGen/SimpleRegisterCoalescing.h
@@ -146,7 +146,7 @@
     /// TrimLiveIntervalToLastUse - If there is a last use in the same basic
     /// block as the copy instruction, trim the ive interval to the last use
     /// and return true.
-    bool TrimLiveIntervalToLastUse(LiveIndex CopyIdx,
+    bool TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
                                    MachineBasicBlock *CopyMBB,
                                    LiveInterval &li, const LiveRange *LR);
 
@@ -205,7 +205,7 @@
     /// iterator, or any subsequent range with the same value number,
     /// is live at the given point.
     bool ValueLiveAt(LiveInterval::iterator LRItr, LiveInterval::iterator LREnd, 
-                     LiveIndex defPoint) const;                                  
+                     SlotIndex defPoint) const;                                  
 
     /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of
     /// the specified live interval is defined by a copy from the specified
@@ -241,9 +241,8 @@
 
     /// lastRegisterUse - Returns the last use of the specific register between
     /// cycles Start and End or NULL if there are no uses.
-    MachineOperand *lastRegisterUse(LiveIndex Start,
-                                    LiveIndex End, unsigned Reg,
-                                    LiveIndex &LastUseIdx) const;
+    MachineOperand *lastRegisterUse(SlotIndex Start, SlotIndex End,
+                                    unsigned Reg, SlotIndex &LastUseIdx) const;
 
     /// CalculateSpillWeights - Compute spill weights for all virtual register
     /// live intervals.
diff --git a/lib/CodeGen/SlotIndexes.cpp b/lib/CodeGen/SlotIndexes.cpp
new file mode 100644
index 0000000..6b04029
--- /dev/null
+++ b/lib/CodeGen/SlotIndexes.cpp
@@ -0,0 +1,189 @@
+//===-- SlotIndexes.cpp - Slot Indexes Pass  ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "slotindexes"
+
+#include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+std::auto_ptr<IndexListEntry> SlotIndex::emptyKeyPtr(0),
+                              SlotIndex::tombstoneKeyPtr(0);
+
+char SlotIndexes::ID = 0;
+static RegisterPass<SlotIndexes> X("slotindexes", "Slot index numbering");
+
+void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
+  au.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(au);
+}
+
+void SlotIndexes::releaseMemory() {
+  mi2iMap.clear();
+  mbb2IdxMap.clear();
+  idx2MBBMap.clear();
+  terminatorGaps.clear();
+  clearList();
+}
+
+bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
+
+  // Compute numbering as follows:
+  // Grab an iterator to the start of the index list.
+  // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
+  // iterator in lock-step (though skipping it over indexes which have
+  // null pointers in the instruction field).
+  // At each iteration assert that the instruction pointed to in the index
+  // is the same one pointed to by the MI iterator. This 
+
+  // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
+  // only need to be set up once after the first numbering is computed.
+
+  mf = &fn;
+  initList();
+
+  const unsigned gap = 1;
+
+  // Check that the list contains only the sentinal.
+  assert(indexListHead->getNext() == 0 &&
+         "Index list non-empty at initial numbering?");
+  assert(idx2MBBMap.empty() &&
+         "Index -> MBB mapping non-empty at initial numbering?");
+  assert(mbb2IdxMap.empty() &&
+         "MBB -> Index mapping non-empty at initial numbering?");
+  assert(mi2iMap.empty() &&
+         "MachineInstr -> Index mapping non-empty at initial numbering?");
+
+  functionSize = 0;
+  /*  
+  for (unsigned s = 0; s < SlotIndex::NUM; ++s) {  
+    indexList.push_back(createEntry(0, s));
+  }
+
+  unsigned index = gap * SlotIndex::NUM;
+  */
+
+  unsigned index = 0;
+
+  // Iterate over the the function.
+  for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end();
+       mbbItr != mbbEnd; ++mbbItr) {
+    MachineBasicBlock *mbb = &*mbbItr;
+
+    // Insert an index for the MBB start.
+    push_back(createEntry(0, index));
+    SlotIndex blockStartIndex(back(), SlotIndex::LOAD);
+
+    index += gap * SlotIndex::NUM;
+
+    for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end();
+         miItr != miEnd; ++miItr) {
+      MachineInstr *mi = &*miItr;
+
+      if (miItr == mbb->getFirstTerminator()) {
+        push_back(createEntry(0, index));
+        terminatorGaps.insert(
+          std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
+        index += gap * SlotIndex::NUM;
+      }
+
+      // Insert a store index for the instr.
+      push_back(createEntry(mi, index));
+
+      // Save this base index in the maps.
+      mi2iMap.insert(
+        std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD)));
+ 
+      ++functionSize;
+
+      unsigned Slots = mi->getDesc().getNumDefs();
+      if (Slots == 0)
+        Slots = 1;
+
+      index += (Slots + 1) * gap * SlotIndex::NUM;
+    }
+
+    if (mbb->getFirstTerminator() == mbb->end()) {
+      push_back(createEntry(0, index));
+      terminatorGaps.insert(
+        std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
+      index += gap * SlotIndex::NUM;
+    }
+
+    SlotIndex blockEndIndex(back(), SlotIndex::STORE);
+    mbb2IdxMap.insert(
+      std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex)));
+
+    idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb));
+  }
+
+  // One blank instruction at the end.
+  push_back(createEntry(0, index));
+
+  // Sort the Idx2MBBMap
+  std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
+
+  DEBUG(dump());
+
+  // And we're done!
+  return false;
+}
+
+void SlotIndexes::renumber() {
+  assert(false && "SlotIndexes::runmuber is not fully implemented yet.");
+
+  // Compute numbering as follows:
+  // Grab an iterator to the start of the index list.
+  // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
+  // iterator in lock-step (though skipping it over indexes which have
+  // null pointers in the instruction field).
+  // At each iteration assert that the instruction pointed to in the index
+  // is the same one pointed to by the MI iterator. This 
+
+  // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
+  // only need to be set up once - when the first numbering is computed.
+
+  assert(false && "Renumbering not supported yet.");
+}
+
+void SlotIndexes::dump() const {
+  for (const IndexListEntry *itr = front(); itr != getTail();
+       itr = itr->getNext()) {
+    errs() << itr->getIndex() << " ";
+
+    if (itr->getInstr() != 0) {
+      errs() << *itr->getInstr();
+    } else {
+      errs() << "\n";
+    }
+  }
+
+  for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin();
+       itr != mbb2IdxMap.end(); ++itr) {
+    errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - ["
+           << itr->second.first << ", " << itr->second.second << "]\n";
+  }
+}
+
+// Print a SlotIndex to a raw_ostream.
+void SlotIndex::print(raw_ostream &os) const {
+  os << getIndex();
+  if (isPHI())
+    os << "*";
+}
+
+// Dump a SlotIndex to stderr.
+void SlotIndex::dump() const {
+  print(errs());
+  errs() << "\n";
+}
+
diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index 0277d64..95e85be 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -51,13 +51,15 @@
 
   /// Ensures there is space before the given machine instruction, returns the
   /// instruction's new number.
-  LiveIndex makeSpaceBefore(MachineInstr *mi) {
+  SlotIndex makeSpaceBefore(MachineInstr *mi) {
     if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
-      lis->scaleNumbering(2);
-      ls->scaleNumbering(2);
+      // FIXME: Should be updated to use rewrite-in-place methods when they're
+      // introduced. Currently broken.
+      //lis->scaleNumbering(2);
+      //ls->scaleNumbering(2);
     }
 
-    LiveIndex miIdx = lis->getInstructionIndex(mi);
+    SlotIndex miIdx = lis->getInstructionIndex(mi);
 
     assert(lis->hasGapBeforeInstr(miIdx));
     
@@ -66,13 +68,15 @@
 
   /// Ensure there is space after the given machine instruction, returns the
   /// instruction's new number.
-  LiveIndex makeSpaceAfter(MachineInstr *mi) {
+  SlotIndex makeSpaceAfter(MachineInstr *mi) {
     if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
-      lis->scaleNumbering(2);
-      ls->scaleNumbering(2);
+      // FIXME: Should be updated to use rewrite-in-place methods when they're
+      // introduced. Currently broken.
+      // lis->scaleNumbering(2);
+      // ls->scaleNumbering(2);
     }
 
-    LiveIndex miIdx = lis->getInstructionIndex(mi);
+    SlotIndex miIdx = lis->getInstructionIndex(mi);
 
     assert(lis->hasGapAfterInstr(miIdx));
 
@@ -83,19 +87,19 @@
   /// after the given instruction. Returns the base index of the inserted
   /// instruction. The caller is responsible for adding an appropriate
   /// LiveInterval to the LiveIntervals analysis.
-  LiveIndex insertStoreAfter(MachineInstr *mi, unsigned ss,
+  SlotIndex insertStoreAfter(MachineInstr *mi, unsigned ss,
                                      unsigned vreg,
                                      const TargetRegisterClass *trc) {
 
     MachineBasicBlock::iterator nextInstItr(next(mi)); 
 
-    LiveIndex miIdx = makeSpaceAfter(mi);
+    SlotIndex miIdx = makeSpaceAfter(mi);
 
     tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
                              true, ss, trc);
     MachineBasicBlock::iterator storeInstItr(next(mi));
     MachineInstr *storeInst = &*storeInstItr;
-    LiveIndex storeInstIdx = lis->getNextIndex(miIdx);
+    SlotIndex storeInstIdx = miIdx.getNextIndex();
 
     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
            "Store inst index already in use.");
@@ -108,15 +112,15 @@
   /// Insert a store of the given vreg to the given stack slot immediately
   /// before the given instructnion. Returns the base index of the inserted
   /// Instruction.
-  LiveIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
+  SlotIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
                                       unsigned vreg,
                                       const TargetRegisterClass *trc) {
-    LiveIndex miIdx = makeSpaceBefore(mi);
+    SlotIndex miIdx = makeSpaceBefore(mi);
   
     tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
     MachineBasicBlock::iterator storeInstItr(prior(mi));
     MachineInstr *storeInst = &*storeInstItr;
-    LiveIndex storeInstIdx = lis->getPrevIndex(miIdx);
+    SlotIndex storeInstIdx = miIdx.getPrevIndex();
 
     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
            "Store inst index already in use.");
@@ -131,9 +135,9 @@
                                       unsigned vreg,
                                       const TargetRegisterClass *trc) {
 
-    LiveIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
-    LiveIndex start = lis->getDefIndex(lis->getInstructionIndex(mi)),
-                      end = lis->getUseIndex(storeInstIdx);
+    SlotIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
+    SlotIndex start = lis->getInstructionIndex(mi).getDefIndex(),
+              end = storeInstIdx.getUseIndex();
 
     VNInfo *vni =
       li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
@@ -149,18 +153,18 @@
   /// after the given instruction. Returns the base index of the inserted
   /// instruction. The caller is responsibel for adding/removing an appropriate
   /// range vreg's LiveInterval.
-  LiveIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
+  SlotIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
                                     unsigned vreg,
                                     const TargetRegisterClass *trc) {
 
     MachineBasicBlock::iterator nextInstItr(next(mi)); 
 
-    LiveIndex miIdx = makeSpaceAfter(mi);
+    SlotIndex miIdx = makeSpaceAfter(mi);
 
     tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
     MachineBasicBlock::iterator loadInstItr(next(mi));
     MachineInstr *loadInst = &*loadInstItr;
-    LiveIndex loadInstIdx = lis->getNextIndex(miIdx);
+    SlotIndex loadInstIdx = miIdx.getNextIndex();
 
     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
            "Store inst index already in use.");
@@ -174,15 +178,15 @@
   /// before the given instruction. Returns the base index of the inserted
   /// instruction. The caller is responsible for adding an appropriate
   /// LiveInterval to the LiveIntervals analysis.
-  LiveIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
+  SlotIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
                                      unsigned vreg,
                                      const TargetRegisterClass *trc) {  
-    LiveIndex miIdx = makeSpaceBefore(mi);
+    SlotIndex miIdx = makeSpaceBefore(mi);
   
     tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
     MachineBasicBlock::iterator loadInstItr(prior(mi));
     MachineInstr *loadInst = &*loadInstItr;
-    LiveIndex loadInstIdx = lis->getPrevIndex(miIdx);
+    SlotIndex loadInstIdx = miIdx.getPrevIndex();
 
     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
            "Load inst index already in use.");
@@ -197,9 +201,9 @@
                                       unsigned vreg,
                                       const TargetRegisterClass *trc) {
 
-    LiveIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
-    LiveIndex start = lis->getDefIndex(loadInstIdx),
-                      end = lis->getUseIndex(lis->getInstructionIndex(mi));
+    SlotIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
+    SlotIndex start = loadInstIdx.getDefIndex(),
+              end = lis->getInstructionIndex(mi).getUseIndex();
 
     VNInfo *vni =
       li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
@@ -321,21 +325,21 @@
     vrm->assignVirt2StackSlot(li->reg, ss);
 
     MachineInstr *mi = 0;
-    LiveIndex storeIdx = LiveIndex();
+    SlotIndex storeIdx = SlotIndex();
 
     if (valno->isDefAccurate()) {
       // If we have an accurate def we can just grab an iterator to the instr
       // after the def.
       mi = lis->getInstructionFromIndex(valno->def);
-      storeIdx = lis->getDefIndex(insertStoreAfter(mi, ss, li->reg, trc));
+      storeIdx = insertStoreAfter(mi, ss, li->reg, trc).getDefIndex();
     } else {
       // if we get here we have a PHI def.
       mi = &lis->getMBBFromIndex(valno->def)->front();
-      storeIdx = lis->getDefIndex(insertStoreBefore(mi, ss, li->reg, trc));
+      storeIdx = insertStoreBefore(mi, ss, li->reg, trc).getDefIndex();
     }
 
     MachineBasicBlock *defBlock = mi->getParent();
-    LiveIndex loadIdx = LiveIndex();
+    SlotIndex loadIdx = SlotIndex();
 
     // Now we need to find the load...
     MachineBasicBlock::iterator useItr(mi);
@@ -343,11 +347,11 @@
 
     if (useItr != defBlock->end()) {
       MachineInstr *loadInst = useItr;
-      loadIdx = lis->getUseIndex(insertLoadBefore(loadInst, ss, li->reg, trc));
+      loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc).getUseIndex();
     }
     else {
       MachineInstr *loadInst = &defBlock->back();
-      loadIdx = lis->getUseIndex(insertLoadAfter(loadInst, ss, li->reg, trc));
+      loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc).getUseIndex();
     }
 
     li->removeRange(storeIdx, loadIdx, true);
diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp
index eed2daa..c299192 100644
--- a/lib/CodeGen/StackSlotColoring.cpp
+++ b/lib/CodeGen/StackSlotColoring.cpp
@@ -98,6 +98,8 @@
     
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
+      AU.addRequired<SlotIndexes>();
+      AU.addPreserved<SlotIndexes>();
       AU.addRequired<LiveStacks>();
       AU.addRequired<VirtRegMap>();
       AU.addPreserved<VirtRegMap>();      
diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 5658a65..3c13906 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -72,6 +72,8 @@
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
       AU.addRequired<MachineDominatorTree>();
+      AU.addRequired<SlotIndexes>();
+      AU.addPreserved<SlotIndexes>();
       AU.addRequired<LiveIntervals>();
       
       // TODO: Actually make this true.
@@ -294,7 +296,7 @@
 static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
                      LiveIntervals& LI) {
   LiveInterval& I = LI.getOrCreateInterval(r);
-  LiveIndex idx = LI.getMBBStartIdx(MBB);
+  SlotIndex idx = LI.getMBBStartIdx(MBB);
   return I.liveAt(idx);
 }
 
@@ -427,7 +429,7 @@
     }
 
     LiveInterval& PI = LI.getOrCreateInterval(DestReg);
-    LiveIndex pIdx = LI.getDefIndex(LI.getInstructionIndex(P));
+    SlotIndex pIdx = LI.getInstructionIndex(P).getDefIndex();
     VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno;
     PhiValueNumber.insert(std::make_pair(DestReg, PVN->id));
 
@@ -747,7 +749,7 @@
       
       LiveInterval& I = LI.getInterval(curr.second);
       MachineBasicBlock::iterator term = MBB->getFirstTerminator();
-      LiveIndex endIdx = LiveIndex();
+      SlotIndex endIdx = SlotIndex();
       if (term != MBB->end())
         endIdx = LI.getInstructionIndex(term);
       else
@@ -771,7 +773,7 @@
   
   // Renumber the instructions so that we can perform the index computations
   // needed to create new live intervals.
-  LI.computeNumbering();
+  LI.renumber();
   
   // For copies that we inserted at the ends of predecessors, we construct
   // live intervals.  This is pretty easy, since we know that the destination
@@ -783,15 +785,15 @@
        InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) {
     if (RegHandled.insert(I->first).second) {
       LiveInterval& Int = LI.getOrCreateInterval(I->first);
-      LiveIndex instrIdx = LI.getInstructionIndex(I->second);
-      if (Int.liveAt(LI.getDefIndex(instrIdx)))
-        Int.removeRange(LI.getDefIndex(instrIdx),
-                        LI.getNextSlot(LI.getMBBEndIdx(I->second->getParent())),
+      SlotIndex instrIdx = LI.getInstructionIndex(I->second);
+      if (Int.liveAt(instrIdx.getDefIndex()))
+        Int.removeRange(instrIdx.getDefIndex(),
+                        LI.getMBBEndIdx(I->second->getParent()).getNextSlot(),
                         true);
       
       LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second);
       R.valno->setCopy(I->second);
-      R.valno->def = LI.getDefIndex(LI.getInstructionIndex(I->second));
+      R.valno->def = LI.getInstructionIndex(I->second).getDefIndex();
     }
   }
 }
@@ -816,8 +818,8 @@
           Stacks[I->getOperand(i).getReg()].size()) {
         // Remove the live range for the old vreg.
         LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg());
-        LiveInterval::iterator OldLR = OldInt.FindLiveRangeContaining(
-                  LI.getUseIndex(LI.getInstructionIndex(I)));
+        LiveInterval::iterator OldLR =
+          OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex());
         if (OldLR != OldInt.end())
           OldInt.removeRange(*OldLR, true);
         
@@ -829,11 +831,10 @@
         VNInfo* FirstVN = *Int.vni_begin();
         FirstVN->setHasPHIKill(false);
         if (I->getOperand(i).isKill())
-          FirstVN->addKill(
-                 LI.getUseIndex(LI.getInstructionIndex(I)));
+          FirstVN->addKill(LI.getInstructionIndex(I).getUseIndex());
         
         LiveRange LR (LI.getMBBStartIdx(I->getParent()),
-                      LI.getNextSlot(LI.getUseIndex(LI.getInstructionIndex(I))),
+                      LI.getInstructionIndex(I).getUseIndex().getNextSlot(),
                       FirstVN);
         
         Int.addRange(LR);
@@ -862,14 +863,14 @@
   LiveInterval& LHS = LI.getOrCreateInterval(primary);
   LiveInterval& RHS = LI.getOrCreateInterval(secondary);
   
-  LI.computeNumbering();
+  LI.renumber();
   
   DenseMap<VNInfo*, VNInfo*> VNMap;
   for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
     LiveRange R = *I;
  
-    LiveIndex Start = R.start;
-    LiveIndex End = R.end;
+    SlotIndex Start = R.start;
+    SlotIndex End = R.end;
     if (LHS.getLiveRangeContaining(Start))
       return false;
     
@@ -963,19 +964,19 @@
           TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(),
                             I->first, SI->first, RC, RC);
           
-          LI.computeNumbering();
+          LI.renumber();
           
           LiveInterval& Int = LI.getOrCreateInterval(I->first);
-          LiveIndex instrIdx =
+          SlotIndex instrIdx =
                      LI.getInstructionIndex(--SI->second->getFirstTerminator());
-          if (Int.liveAt(LI.getDefIndex(instrIdx)))
-            Int.removeRange(LI.getDefIndex(instrIdx),
-                            LI.getNextSlot(LI.getMBBEndIdx(SI->second)), true);
+          if (Int.liveAt(instrIdx.getDefIndex()))
+            Int.removeRange(instrIdx.getDefIndex(),
+                            LI.getMBBEndIdx(SI->second).getNextSlot(), true);
 
           LiveRange R = LI.addLiveRangeToEndOfBlock(I->first,
                                             --SI->second->getFirstTerminator());
           R.valno->setCopy(--SI->second->getFirstTerminator());
-          R.valno->def = LI.getDefIndex(instrIdx);
+          R.valno->def = instrIdx.getDefIndex();
           
           DEBUG(errs() << "Renaming failed: " << SI->first << " -> "
                        << I->first << "\n");
@@ -1010,7 +1011,7 @@
       if (PI.containsOneValue()) {
         LI.removeInterval(DestReg);
       } else {
-        LiveIndex idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+        SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
         PI.removeRange(*PI.getLiveRangeContaining(idx), true);
       }
     } else {
@@ -1024,7 +1025,7 @@
         LiveInterval& InputI = LI.getInterval(reg);
         if (MBB != PInstr->getParent() &&
             InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) &&
-            InputI.expiredAt(LI.getNextIndex(LI.getInstructionIndex(PInstr))))
+            InputI.expiredAt(LI.getInstructionIndex(PInstr).getNextIndex()))
           InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()),
                              LI.getInstructionIndex(PInstr),
                              true);
@@ -1032,7 +1033,7 @@
       
       // If the PHI is not dead, then the valno defined by the PHI
       // now has an unknown def.
-      LiveIndex idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+      SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
       const LiveRange* PLR = PI.getLiveRangeContaining(idx);
       PLR->valno->setIsPHIDef(true);
       LiveRange R (LI.getMBBStartIdx(PInstr->getParent()),
@@ -1044,7 +1045,7 @@
     PInstr->eraseFromParent();
   }
   
-  LI.computeNumbering();
+  LI.renumber();
   
   return true;
 }
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index cac098b..ce3eed1 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -56,7 +56,7 @@
   TII = mf.getTarget().getInstrInfo();
   TRI = mf.getTarget().getRegisterInfo();
   MF = &mf;
-  
+
   ReMatId = MAX_STACK_SLOT+1;
   LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
   
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index bdc2d1f..a5599f6 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -80,7 +80,7 @@
 
     /// Virt2SplitKillMap - This is splitted virtual register to its last use
     /// (kill) index mapping.
-    IndexedMap<LiveIndex> Virt2SplitKillMap;
+    IndexedMap<SlotIndex> Virt2SplitKillMap;
 
     /// ReMatMap - This is virtual register to re-materialized instruction
     /// mapping. Each virtual register whose definition is going to be
@@ -142,7 +142,7 @@
     VirtRegMap() : MachineFunctionPass(&ID), Virt2PhysMap(NO_PHYS_REG),
                    Virt2StackSlotMap(NO_STACK_SLOT), 
                    Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
-                   Virt2SplitKillMap(LiveIndex()), ReMatMap(NULL),
+                   Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL),
                    ReMatId(MAX_STACK_SLOT+1),
                    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
     virtual bool runOnMachineFunction(MachineFunction &MF);
@@ -266,17 +266,17 @@
     }
 
     /// @brief record the last use (kill) of a split virtual register.
-    void addKillPoint(unsigned virtReg, LiveIndex index) {
+    void addKillPoint(unsigned virtReg, SlotIndex index) {
       Virt2SplitKillMap[virtReg] = index;
     }
 
-    LiveIndex getKillPoint(unsigned virtReg) const {
+    SlotIndex getKillPoint(unsigned virtReg) const {
       return Virt2SplitKillMap[virtReg];
     }
 
     /// @brief remove the last use (kill) of a split virtual register.
     void removeKillPoint(unsigned virtReg) {
-      Virt2SplitKillMap[virtReg] = LiveIndex();
+      Virt2SplitKillMap[virtReg] = SlotIndex();
     }
 
     /// @brief returns true if the specified MachineInstr is a spill point.