20 files changed, 1862 insertions, 1434 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 05bd173dd2..e31a7f0a25 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -21,221 +21,19 @@
 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
 #define LLVM_CODEGEN_LIVEINTERVAL_H
 
-#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/AlignOf.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
+  class LiveIntervals;
   class MachineInstr;
   class MachineRegisterInfo;
   class TargetRegisterInfo;
   class raw_ostream;
-  
-  /// LiveIndex - An opaque wrapper around machine indexes.
-  class LiveIndex {
-    friend class VNInfo;
-    friend class LiveInterval;
-    friend class LiveIntervals;
-    friend struct DenseMapInfo<LiveIndex>;
-
-  public:
-
-    enum Slot { LOAD, USE, DEF, STORE, NUM };
-
-  private:
-
-    unsigned index;
-
-    static const unsigned PHI_BIT = 1 << 31;
-
-  public:
-
-    /// Construct a default LiveIndex pointing to a reserved index.
-    LiveIndex() : index(0) {}
-
-    /// Construct an index from the given index, pointing to the given slot.
-    LiveIndex(LiveIndex m, Slot s)
-      : index((m.index / NUM) * NUM + s) {} 
-    
-    /// Print this index to the given raw_ostream.
-    void print(raw_ostream &os) const;
-
-    /// Compare two LiveIndex objects for equality.
-    bool operator==(LiveIndex other) const {
-      return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT));
-    }
-    /// Compare two LiveIndex objects for inequality.
-    bool operator!=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT));
-    }
-   
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is strictly lower than the second.
-    bool operator<(LiveIndex other) const {
-      return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT));
-    }
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is lower than, or equal to, the second.
-    bool operator<=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT));
-    }
-
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is greater than the second.
-    bool operator>(LiveIndex other) const {
-      return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT));
-    }
-
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is greater than, or equal to, the second.
-    bool operator>=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) >= (other.index & ~PHI_BIT));
-    }
-
-    /// Returns true if this index represents a load.
-    bool isLoad() const {
-      return ((index % NUM) == LOAD);
-    }
-
-    /// Returns true if this index represents a use.
-    bool isUse() const {
-      return ((index % NUM) == USE);
-    }
-
-    /// Returns true if this index represents a def.
-    bool isDef() const {
-      return ((index % NUM) == DEF);
-    }
-
-    /// Returns true if this index represents a store.
-    bool isStore() const {
-      return ((index % NUM) == STORE);
-    }
-
-    /// Returns the slot for this LiveIndex.
-    Slot getSlot() const {
-      return static_cast<Slot>(index % NUM);
-    }
-
-    /// Returns true if this index represents a non-PHI use/def.
-    bool isNonPHIIndex() const {
-      return ((index & PHI_BIT) == 0);
-    }
-
-    /// Returns true if this index represents a PHI use/def.
-    bool isPHIIndex() const {
-      return ((index & PHI_BIT) == PHI_BIT);
-    }
-
-  private:
-
-    /// Construct an index from the given index, with its PHI kill marker set.
-    LiveIndex(bool phi, LiveIndex o) : index(o.index) {
-      if (phi)
-        index |= PHI_BIT;
-      else
-        index &= ~PHI_BIT;
-    }
-
-    explicit LiveIndex(unsigned idx)
-      : index(idx & ~PHI_BIT) {}
-
-    LiveIndex(bool phi, unsigned idx)
-      : index(idx & ~PHI_BIT) {
-      if (phi)
-        index |= PHI_BIT;
-    }
-
-    LiveIndex(bool phi, unsigned idx, Slot slot)
-      : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) {
-      if (phi)
-        index |= PHI_BIT;
-    }
-    
-    LiveIndex nextSlot_() const {
-      assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index + 1);
-    }
-
-    LiveIndex nextIndex_() const {
-      assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index + NUM);
-    }
-
-    LiveIndex prevSlot_() const {
-      assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index - 1);
-    }
-
-    LiveIndex prevIndex_() const {
-      assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index - NUM);
-    }
-
-    int distance(LiveIndex other) const {
-      return (other.index & ~PHI_BIT) - (index & ~PHI_BIT);
-    }
-
-    /// Returns an unsigned number suitable as an index into a
-    /// vector over all instructions.
-    unsigned getVecIndex() const {
-      return (index & ~PHI_BIT) / NUM;
-    }
-
-    /// Scale this index by the given factor.
-    LiveIndex scale(unsigned factor) const {
-      unsigned i = (index & ~PHI_BIT) / NUM,
-               o = (index % ~PHI_BIT) % NUM;
-      assert(index <= (~0U & ~PHI_BIT) / (factor * NUM) &&
-             "Rescaled interval would overflow");
-      return LiveIndex(i * NUM * factor, o);
-    }
-
-    static LiveIndex emptyKey() {
-      return LiveIndex(true, 0x7fffffff);
-    }
-
-    static LiveIndex tombstoneKey() {
-      return LiveIndex(true, 0x7ffffffe);
-    }
-
-    static unsigned getHashValue(const LiveIndex &v) {
-      return v.index * 37;
-    }
-
-  };
-
-  inline raw_ostream& operator<<(raw_ostream &os, LiveIndex mi) {
-    mi.print(os);
-    return os;
-  }
-
-  /// Densemap specialization for LiveIndex.
-  template <>
-  struct DenseMapInfo<LiveIndex> {
-    static inline LiveIndex getEmptyKey() {
-      return LiveIndex::emptyKey();
-    }
-    static inline LiveIndex getTombstoneKey() {
-      return LiveIndex::tombstoneKey();
-    }
-    static inline unsigned getHashValue(const LiveIndex &v) {
-      return LiveIndex::getHashValue(v);
-    }
-    static inline bool isEqual(const LiveIndex &LHS,
-                               const LiveIndex &RHS) {
-      return (LHS == RHS);
-    }
-    static inline bool isPod() { return true; }
-  };
-
 
   /// VNInfo - Value Number Information.
   /// This class holds information about a machine level values, including
@@ -270,23 +68,25 @@ namespace llvm {
 
   public:
 
-    typedef SmallVector<LiveIndex, 4> KillSet;
+    typedef SmallVector<SlotIndex, 4> KillSet;
 
     /// The ID number of this value.
     unsigned id;
     
     /// The index of the defining instruction (if isDefAccurate() returns true).
-    LiveIndex def;
+    SlotIndex def;
 
     KillSet kills;
 
-    VNInfo()
-      : flags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+    /*
+    VNInfo(LiveIntervals &li_)
+      : defflags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+    */
 
     /// VNInfo constructor.
     /// d is presumed to point to the actual defining instr. If it doesn't
     /// setIsDefAccurate(false) should be called after construction.
-    VNInfo(unsigned i, LiveIndex d, MachineInstr *c)
+    VNInfo(unsigned i, SlotIndex d, MachineInstr *c)
       : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
 
     /// VNInfo construtor, copies values from orig, except for the value number.
@@ -377,7 +177,7 @@ namespace llvm {
     }
 
     /// Returns true if the given index is a kill of this value.
-    bool isKill(LiveIndex k) const {
+    bool isKill(SlotIndex k) const {
       KillSet::const_iterator
         i = std::lower_bound(kills.begin(), kills.end(), k);
       return (i != kills.end() && *i == k);
@@ -385,7 +185,7 @@ namespace llvm {
 
     /// addKill - Add a kill instruction index to the specified value
     /// number.
-    void addKill(LiveIndex k) {
+    void addKill(SlotIndex k) {
       if (kills.empty()) {
         kills.push_back(k);
       } else {
@@ -397,7 +197,7 @@ namespace llvm {
 
     /// Remove the specified kill index from this value's kills list.
     /// Returns true if the value was present, otherwise returns false.
-    bool removeKill(LiveIndex k) {
+    bool removeKill(SlotIndex k) {
       KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
       if (i != kills.end() && *i == k) {
         kills.erase(i);
@@ -407,7 +207,7 @@ namespace llvm {
     }
 
     /// Remove all kills in the range [s, e).
-    void removeKills(LiveIndex s, LiveIndex e) {
+    void removeKills(SlotIndex s, SlotIndex e) {
       KillSet::iterator
         si = std::lower_bound(kills.begin(), kills.end(), s),
         se = std::upper_bound(kills.begin(), kills.end(), e);
@@ -421,11 +221,11 @@ namespace llvm {
   /// program, with an inclusive start point and an exclusive end point.
   /// These ranges are rendered as [start,end).
   struct LiveRange {
-    LiveIndex start;  // Start point of the interval (inclusive)
-    LiveIndex end;    // End point of the interval (exclusive)
+    SlotIndex start;  // Start point of the interval (inclusive)
+    SlotIndex end;    // End point of the interval (exclusive)
     VNInfo *valno;   // identifier for the value contained in this interval.
 
-    LiveRange(LiveIndex S, LiveIndex E, VNInfo *V)
+    LiveRange(SlotIndex S, SlotIndex E, VNInfo *V)
       : start(S), end(E), valno(V) {
 
       assert(S < E && "Cannot create empty or backwards range");
@@ -433,13 +233,13 @@ namespace llvm {
 
     /// contains - Return true if the index is covered by this range.
     ///
-    bool contains(LiveIndex I) const {
+    bool contains(SlotIndex I) const {
       return start <= I && I < end;
     }
 
     /// containsRange - Return true if the given range, [S, E), is covered by
     /// this range. 
-    bool containsRange(LiveIndex S, LiveIndex E) const {
+    bool containsRange(SlotIndex S, SlotIndex E) const {
       assert((S < E) && "Backwards interval?");
       return (start <= S && S < end) && (start < E && E <= end);
     }
@@ -461,11 +261,11 @@ namespace llvm {
   raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 
 
-  inline bool operator<(LiveIndex V, const LiveRange &LR) {
+  inline bool operator<(SlotIndex V, const LiveRange &LR) {
     return V < LR.start;
   }
 
-  inline bool operator<(const LiveRange &LR, LiveIndex V) {
+  inline bool operator<(const LiveRange &LR, SlotIndex V) {
     return LR.start < V;
   }
 
@@ -522,7 +322,7 @@ namespace llvm {
     /// end of the interval.  If no LiveRange contains this position, but the
     /// position is in a hole, this method returns an iterator pointing the the
     /// LiveRange immediately after the hole.
-    iterator advanceTo(iterator I, LiveIndex Pos) {
+    iterator advanceTo(iterator I, SlotIndex Pos) {
       if (Pos >= endIndex())
         return end();
       while (I->end <= Pos) ++I;
@@ -569,7 +369,7 @@ namespace llvm {
 
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
-    VNInfo *getNextValue(LiveIndex def, MachineInstr *CopyMI,
+    VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
                          bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
       VNInfo *VNI =
         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
@@ -625,13 +425,15 @@ namespace llvm {
     /// current interval, but are defined in the Clobbers interval, mark them
     /// used with an unknown definition value. Caller must pass in reference to
     /// VNInfoAllocator since it will create a new val#.
-    void MergeInClobberRanges(const LiveInterval &Clobbers,
+    void MergeInClobberRanges(LiveIntervals &li_,
+                              const LiveInterval &Clobbers,
                               BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
     /// single LiveRange only.
-    void MergeInClobberRange(LiveIndex Start,
-                             LiveIndex End,
+    void MergeInClobberRange(LiveIntervals &li_,
+                             SlotIndex Start,
+                             SlotIndex End,
                              BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
@@ -657,56 +459,54 @@ namespace llvm {
     bool empty() const { return ranges.empty(); }
 
     /// beginIndex - Return the lowest numbered slot covered by interval.
-    LiveIndex beginIndex() const {
-      if (empty())
-        return LiveIndex();
+    SlotIndex beginIndex() const {
+      assert(!empty() && "Call to beginIndex() on empty interval.");
       return ranges.front().start;
     }
 
     /// endNumber - return the maximum point of the interval of the whole,
     /// exclusive.
-    LiveIndex endIndex() const {
-      if (empty())
-        return LiveIndex();
+    SlotIndex endIndex() const {
+      assert(!empty() && "Call to endIndex() on empty interval.");
       return ranges.back().end;
     }
 
-    bool expiredAt(LiveIndex index) const {
+    bool expiredAt(SlotIndex index) const {
       return index >= endIndex();
     }
 
-    bool liveAt(LiveIndex index) const;
+    bool liveAt(SlotIndex index) const;
 
     // 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 liveBeforeAndAt(LiveIndex index) const;
+    bool liveBeforeAndAt(SlotIndex index) const;
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    const LiveRange *getLiveRangeContaining(LiveIndex Idx) const {
+    const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
       const_iterator I = FindLiveRangeContaining(Idx);
       return I == end() ? 0 : &*I;
     }
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    LiveRange *getLiveRangeContaining(LiveIndex Idx) {
+    LiveRange *getLiveRangeContaining(SlotIndex Idx) {
       iterator I = FindLiveRangeContaining(Idx);
       return I == end() ? 0 : &*I;
     }
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    const_iterator FindLiveRangeContaining(LiveIndex Idx) const;
+    const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    iterator FindLiveRangeContaining(LiveIndex Idx);
+    iterator FindLiveRangeContaining(SlotIndex Idx);
 
     /// findDefinedVNInfo - Find the by the specified
     /// index (register interval) or defined 
-    VNInfo *findDefinedVNInfoForRegInt(LiveIndex Idx) const;
+    VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
 
     /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
     /// register (stack inteval only).
@@ -721,7 +521,7 @@ namespace llvm {
 
     /// overlaps - Return true if the live interval overlaps a range specified
     /// by [Start, End).
-    bool overlaps(LiveIndex Start, LiveIndex End) const;
+    bool overlaps(SlotIndex Start, SlotIndex End) const;
 
     /// overlapsFrom - Return true if the intersection of the two live intervals
     /// is not empty.  The specified iterator is a hint that we can begin
@@ -738,18 +538,19 @@ namespace llvm {
     /// 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 join(LiveInterval &Other, const int *ValNoAssignments,
+    void join(LiveInterval &Other,
+              const int *ValNoAssignments,
               const int *RHSValNoAssignments,
               SmallVector<VNInfo*, 16> &NewVNInfo,
               MachineRegisterInfo *MRI);
 
     /// isInOneLiveRange - Return true if the range specified is entirely in the
     /// a single LiveRange of the live interval.
-    bool isInOneLiveRange(LiveIndex Start, LiveIndex End);
+    bool isInOneLiveRange(SlotIndex Start, SlotIndex End);
 
     /// removeRange - Remove the specified range from this interval.  Note that
     /// the range must be a single LiveRange in its entirety.
-    void removeRange(LiveIndex Start, LiveIndex End,
+    void removeRange(SlotIndex Start, SlotIndex End,
                      bool RemoveDeadValNo = false);
 
     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
@@ -773,8 +574,8 @@ namespace llvm {
     void ComputeJoinedWeight(const LiveInterval &Other);
 
     bool operator<(const LiveInterval& other) const {
-      const LiveIndex &thisIndex = beginIndex();
-      const LiveIndex &otherIndex = other.beginIndex();
+      const SlotIndex &thisIndex = beginIndex();
+      const SlotIndex &otherIndex = other.beginIndex();
       return (thisIndex < otherIndex ||
               (thisIndex == otherIndex && reg < other.reg));
     }
@@ -785,8 +586,9 @@ namespace llvm {
   private:
 
     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
-    void extendIntervalEndTo(Ranges::iterator I, LiveIndex NewEnd);
-    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, LiveIndex NewStr);
+    void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
+    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
+
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
 
   };
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 511db6db10..efb4a03d88 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -23,12 +23,14 @@
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include <cmath>
+#include <iterator>
 
 namespace llvm {
 
@@ -40,21 +42,6 @@ namespace llvm {
   class TargetInstrInfo;
   class TargetRegisterClass;
   class VirtRegMap;
-  typedef std::pair<LiveIndex, MachineBasicBlock*> IdxMBBPair;
-
-  inline bool operator<(LiveIndex V, const IdxMBBPair &IM) {
-    return V < IM.first;
-  }
-
-  inline bool operator<(const IdxMBBPair &IM, LiveIndex V) {
-    return IM.first < V;
-  }
-
-  struct Idx2MBBCompare {
-    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
-      return LHS.first < RHS.first;
-    }
-  };
   
   class LiveIntervals : public MachineFunctionPass {
     MachineFunction* mf_;
@@ -64,33 +51,15 @@ namespace llvm {
     const TargetInstrInfo* tii_;
     AliasAnalysis *aa_;
     LiveVariables* lv_;
+    SlotIndexes* indexes_;
 
     /// Special pool allocator for VNInfo's (LiveInterval val#).
     ///
     BumpPtrAllocator VNInfoAllocator;
 
-    /// MBB2IdxMap - The indexes of the first and last instructions in the
-    /// specified basic block.
-    std::vector<std::pair<LiveIndex, LiveIndex> > MBB2IdxMap;
-
-    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
-    /// and MBB id.
-    std::vector<IdxMBBPair> Idx2MBBMap;
-
-    /// FunctionSize - The number of instructions present in the function
-    uint64_t FunctionSize;
-
-    typedef DenseMap<const MachineInstr*, LiveIndex> Mi2IndexMap;
-    Mi2IndexMap mi2iMap_;
-
-    typedef std::vector<MachineInstr*> Index2MiMap;
-    Index2MiMap i2miMap_;
-
     typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
     Reg2IntervalMap r2iMap_;
 
-    DenseMap<MachineBasicBlock*, LiveIndex> terminatorGaps;
-
     /// phiJoinCopies - Copy instructions which are PHI joins.
     SmallVector<MachineInstr*, 16> phiJoinCopies;
 
@@ -100,48 +69,10 @@ namespace llvm {
     /// CloneMIs - A list of clones as result of re-materialization.
     std::vector<MachineInstr*> CloneMIs;
 
-    typedef LiveInterval::InstrSlots InstrSlots;
-
   public:
     static char ID; // Pass identification, replacement for typeid
     LiveIntervals() : MachineFunctionPass(&ID) {}
 
-    LiveIndex getBaseIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::LOAD);
-    }
-    LiveIndex getBoundaryIndex(LiveIndex index) {
-      return LiveIndex(index,
-        (LiveIndex::Slot)(LiveIndex::NUM - 1));
-    }
-    LiveIndex getLoadIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::LOAD);
-    }
-    LiveIndex getUseIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::USE);
-    }
-    LiveIndex getDefIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::DEF);
-    }
-    LiveIndex getStoreIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::STORE);
-    }    
-
-    LiveIndex getNextSlot(LiveIndex m) const {
-      return m.nextSlot_();
-    }
-
-    LiveIndex getNextIndex(LiveIndex m) const {
-      return m.nextIndex_();
-    }
-
-    LiveIndex getPrevSlot(LiveIndex m) const {
-      return m.prevSlot_();
-    }
-
-    LiveIndex getPrevIndex(LiveIndex m) const {
-      return m.prevIndex_();
-    }
-
     static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
       return (isDef + isUse) * powf(10.0F, (float)loopDepth);
     }
@@ -170,111 +101,18 @@ namespace llvm {
       return r2iMap_.count(reg);
     }
 
-    /// getMBBStartIdx - Return the base index of the first instruction in the
-    /// specified MachineBasicBlock.
-    LiveIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
-      return getMBBStartIdx(MBB->getNumber());
-    }
-    LiveIndex getMBBStartIdx(unsigned MBBNo) const {
-      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
-      return MBB2IdxMap[MBBNo].first;
-    }
-
-    /// getMBBEndIdx - Return the store index of the last instruction in the
-    /// specified MachineBasicBlock.
-    LiveIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
-      return getMBBEndIdx(MBB->getNumber());
-    }
-    LiveIndex getMBBEndIdx(unsigned MBBNo) const {
-      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
-      return MBB2IdxMap[MBBNo].second;
-    }
-
     /// getScaledIntervalSize - get the size of an interval in "units,"
     /// where every function is composed of one thousand units.  This
     /// measure scales properly with empty index slots in the function.
     double getScaledIntervalSize(LiveInterval& I) {
-      return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+      return (1000.0 * I.getSize()) / indexes_->getIndexesLength();
     }
     
     /// getApproximateInstructionCount - computes an estimate of the number
     /// of instructions in a given LiveInterval.
     unsigned getApproximateInstructionCount(LiveInterval& I) {
       double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
-      return (unsigned)(IntervalPercentage * FunctionSize);
-    }
-
-    /// getMBBFromIndex - given an index in any instruction of an
-    /// MBB return a pointer the MBB
-    MachineBasicBlock* getMBBFromIndex(LiveIndex index) const {
-      std::vector<IdxMBBPair>::const_iterator I =
-        std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
-      // Take the pair containing the index
-      std::vector<IdxMBBPair>::const_iterator J =
-        ((I != Idx2MBBMap.end() && I->first > index) ||
-         (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
-
-      assert(J != Idx2MBBMap.end() && J->first <= index &&
-             index <= getMBBEndIdx(J->second) &&
-             "index does not correspond to an MBB");
-      return J->second;
-    }
-
-    /// getInstructionIndex - returns the base index of instr
-    LiveIndex getInstructionIndex(const MachineInstr* instr) const {
-      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
-      assert(it != mi2iMap_.end() && "Invalid instruction!");
-      return it->second;
-    }
-
-    /// getInstructionFromIndex - given an index in any slot of an
-    /// instruction return a pointer the instruction
-    MachineInstr* getInstructionFromIndex(LiveIndex index) const {
-      // convert index to vector index
-      unsigned i = index.getVecIndex();
-      assert(i < i2miMap_.size() &&
-             "index does not correspond to an instruction");
-      return i2miMap_[i];
-    }
-
-    /// hasGapBeforeInstr - Return true if the previous instruction slot,
-    /// i.e. Index - InstrSlots::NUM, is not occupied.
-    bool hasGapBeforeInstr(LiveIndex Index) {
-      Index = getBaseIndex(getPrevIndex(Index));
-      return getInstructionFromIndex(Index) == 0;
-    }
-
-    /// hasGapAfterInstr - Return true if the successive instruction slot,
-    /// i.e. Index + InstrSlots::Num, is not occupied.
-    bool hasGapAfterInstr(LiveIndex Index) {
-      Index = getBaseIndex(getNextIndex(Index));
-      return getInstructionFromIndex(Index) == 0;
-    }
-
-    /// findGapBeforeInstr - Find an empty instruction slot before the
-    /// specified index. If "Furthest" is true, find one that's furthest
-    /// away from the index (but before any index that's occupied).
-    LiveIndex findGapBeforeInstr(LiveIndex Index, bool Furthest = false) {
-      Index = getBaseIndex(getPrevIndex(Index));
-      if (getInstructionFromIndex(Index))
-        return LiveIndex();  // No gap!
-      if (!Furthest)
-        return Index;
-      LiveIndex PrevIndex = getBaseIndex(getPrevIndex(Index));
-      while (getInstructionFromIndex(Index)) {
-        Index = PrevIndex;
-        PrevIndex = getBaseIndex(getPrevIndex(Index));
-      }
-      return Index;
-    }
-
-    /// InsertMachineInstrInMaps - Insert the specified machine instruction
-    /// into the instruction index map at the given index.
-    void InsertMachineInstrInMaps(MachineInstr *MI, LiveIndex Index) {
-      i2miMap_[Index.getVecIndex()] = MI;
-      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
-      assert(it == mi2iMap_.end() && "Already in map!");
-      mi2iMap_[MI] = Index;
+      return (unsigned)(IntervalPercentage * indexes_->getFunctionSize());
     }
 
     /// conflictsWithPhysRegDef - Returns true if the specified register
@@ -288,19 +126,7 @@ namespace llvm {
                                  bool CheckUse,
                                  SmallPtrSet<MachineInstr*,32> &JoinedCopies);
 
-    /// findLiveInMBBs - Given a live range, if the value of the range
-    /// is live in any MBB returns true as well as the list of basic blocks
-    /// in which the value is live.
-    bool findLiveInMBBs(LiveIndex Start, LiveIndex End,
-                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
-    /// findReachableMBBs - Return a list MBB that can be reached via any
-    /// branch or fallthroughs. Return true if the list is not empty.
-    bool findReachableMBBs(LiveIndex Start, LiveIndex End,
-                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
     // Interval creation
-
     LiveInterval &getOrCreateInterval(unsigned reg) {
       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
       if (I == r2iMap_.end())
@@ -325,36 +151,75 @@ namespace llvm {
       r2iMap_.erase(I);
     }
 
+    SlotIndex getZeroIndex() const {
+      return indexes_->getZeroIndex();
+    }
+
+    SlotIndex getInvalidIndex() const {
+      return indexes_->getInvalidIndex();
+    }
+
     /// isNotInMIMap - returns true if the specified machine instr has been
     /// removed or was never entered in the map.
-    bool isNotInMIMap(MachineInstr* instr) const {
-      return !mi2iMap_.count(instr);
+    bool isNotInMIMap(const MachineInstr* Instr) const {
+      return !indexes_->hasIndex(Instr);
+    }
+
+    /// Returns the base index of the given instruction.
+    SlotIndex getInstructionIndex(const MachineInstr *instr) const {
+      return indexes_->getInstructionIndex(instr);
+    }
+    
+    /// Returns the instruction associated with the given index.
+    MachineInstr* getInstructionFromIndex(SlotIndex index) const {
+      return indexes_->getInstructionFromIndex(index);
+    }
+
+    /// Return the first index in the given basic block.
+    SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
+      return indexes_->getMBBStartIdx(mbb);
+    } 
+
+    /// Return the last index in the given basic block.
+    SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
+      return indexes_->getMBBEndIdx(mbb);
+    } 
+
+    MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+      return indexes_->getMBBFromIndex(index);
+    }
+
+    bool hasGapBeforeInstr(SlotIndex index) {
+      return indexes_->hasGapBeforeInstr(index);
+    }
+
+    bool hasGapAfterInstr(SlotIndex index) {
+      return indexes_->hasGapAfterInstr(index);
+    }
+
+    SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
+      return indexes_->findGapBeforeInstr(index, furthest);
+    }
+
+    void InsertMachineInstrInMaps(MachineInstr *MI, SlotIndex Index) {
+      indexes_->insertMachineInstrInMaps(MI, Index);
     }
 
-    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
-    /// deleted.
     void RemoveMachineInstrFromMaps(MachineInstr *MI) {
-      // remove index -> MachineInstr and
-      // MachineInstr -> index mappings
-      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
-      if (mi2i != mi2iMap_.end()) {
-        i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
-        mi2iMap_.erase(mi2i);
-      }
+      indexes_->removeMachineInstrFromMaps(MI);
     }
 
-    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
-    /// maps used by register allocator.
     void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
-      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
-      if (mi2i == mi2iMap_.end())
-        return;
-      i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
-      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
-      assert(it != mi2iMap_.end() && "Invalid instruction!");
-      LiveIndex Index = it->second;
-      mi2iMap_.erase(it);
-      mi2iMap_[NewMI] = Index;
+      indexes_->replaceMachineInstrInMaps(MI, NewMI);
+    }
+
+    bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
+                        S