Replaces uses of unsigned for indexes in LiveInterval and VNInfo with

a new class, MachineInstrIndex, which hides arithmetic details from
most clients. This is a step towards allowing the register allocator
to update/insert code during allocation.


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

2 files changed, 428 insertions, 162 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 9a9bc5696d..00dd422664 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -21,6 +21,7 @@
 #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"
@@ -32,6 +33,217 @@ namespace llvm {
   class MachineRegisterInfo;
   class TargetRegisterInfo;
   class raw_ostream;
+  
+  /// MachineInstrIndex - An opaque wrapper around machine indexes.
+  class MachineInstrIndex {
+    friend class VNInfo;
+    friend class LiveInterval;
+    friend class LiveIntervals;
+    friend struct DenseMapInfo<MachineInstrIndex>;
+
+  public:
+
+    enum Slot { LOAD, USE, DEF, STORE, NUM };
+
+  private:
+
+    unsigned index;
+
+    static const unsigned PHI_BIT = 1 << 31;
+
+  public:
+
+    /// Construct a default MachineInstrIndex pointing to a reserved index.
+    MachineInstrIndex() : index(0) {}
+
+    /// Construct an index from the given index, pointing to the given slot.
+    MachineInstrIndex(MachineInstrIndex m, Slot s)
+      : index((m.index / NUM) * NUM + s) {} 
+    
+    /// Print this index to the given raw_ostream.
+    void print(raw_ostream &os) const;
+
+    /// Print this index to the given std::ostream.
+    void print(std::ostream &os) const;
+
+    /// Compare two MachineInstrIndex objects for equality.
+    bool operator==(MachineInstrIndex other) const {
+      return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT));
+    }
+    /// Compare two MachineInstrIndex objects for inequality.
+    bool operator!=(MachineInstrIndex other) const {
+      return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT));
+    }
+   
+    /// Compare two MachineInstrIndex objects. Return true if the first index
+    /// is strictly lower than the second.
+    bool operator<(MachineInstrIndex other) const {
+      return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT));
+    }
+    /// Compare two MachineInstrIndex objects. Return true if the first index
+    /// is lower than, or equal to, the second.
+    bool operator<=(MachineInstrIndex other) const {
+      return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT));
+    }
+
+    /// Compare two MachineInstrIndex objects. Return true if the first index
+    /// is greater than the second.
+    bool operator>(MachineInstrIndex other) const {
+      return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT));
+    }
+
+    /// Compare two MachineInstrIndex objects. Return true if the first index
+    /// is greater than, or equal to, the second.
+    bool operator>=(MachineInstrIndex 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 MachineInstrIndex.
+    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.
+    MachineInstrIndex(bool phi, MachineInstrIndex o) : index(o.index) {
+      if (phi)
+        index |= PHI_BIT;
+      else
+        index &= ~PHI_BIT;
+    }
+
+    explicit MachineInstrIndex(unsigned idx)
+      : index(idx & ~PHI_BIT) {}
+
+    MachineInstrIndex(bool phi, unsigned idx)
+      : index(idx & ~PHI_BIT) {
+      if (phi)
+        index |= PHI_BIT;
+    }
+
+    MachineInstrIndex(bool phi, unsigned idx, Slot slot)
+      : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) {
+      if (phi)
+        index |= PHI_BIT;
+    }
+    
+    MachineInstrIndex nextSlot() const {
+      assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) &&
+             "Index out of bounds.");
+      return MachineInstrIndex(index + 1);
+    }
+
+    MachineInstrIndex nextIndex() const {
+      assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) &&
+             "Index out of bounds.");
+      return MachineInstrIndex(index + NUM);
+    }
+
+    MachineInstrIndex prevSlot() const {
+      assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) &&
+             "Index out of bounds.");
+      return MachineInstrIndex(index - 1);
+    }
+
+    MachineInstrIndex prevIndex() const {
+      assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) &&
+             "Index out of bounds.");
+      return MachineInstrIndex(index - NUM);
+    }
+
+    int distance(MachineInstrIndex 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.
+    MachineInstrIndex 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 MachineInstrIndex(i * NUM * factor, o);
+    }
+
+    static MachineInstrIndex emptyKey() {
+      return MachineInstrIndex(true, 0x7fffffff);
+    }
+
+    static MachineInstrIndex tombstoneKey() {
+      return MachineInstrIndex(true, 0x7ffffffe);
+    }
+
+    static unsigned getHashValue(const MachineInstrIndex &v) {
+      return v.index * 37;
+    }
+
+  };
+
+  inline raw_ostream& operator<<(raw_ostream &os, MachineInstrIndex mi) {
+    mi.print(os);
+    return os;
+  }
+
+  inline std::ostream& operator<<(std::ostream &os, MachineInstrIndex mi) {
+    mi.print(os);
+    return os;
+  }
+
+  /// Densemap specialization for MachineInstrIndex.
+  template <>
+  struct DenseMapInfo<MachineInstrIndex> {
+    static inline MachineInstrIndex getEmptyKey() {
+      return MachineInstrIndex::emptyKey();
+    }
+    static inline MachineInstrIndex getTombstoneKey() {
+      return MachineInstrIndex::tombstoneKey();
+    }
+    static inline unsigned getHashValue(const MachineInstrIndex &v) {
+      return MachineInstrIndex::getHashValue(v);
+    }
+    static inline bool isEqual(const MachineInstrIndex &LHS,
+                               const MachineInstrIndex &RHS) {
+      return (LHS == RHS);
+    }
+    static inline bool isPod() { return true; }
+  };
+
 
   /// VNInfo - Value Number Information.
   /// This class holds information about a machine level values, including
@@ -65,36 +277,24 @@ namespace llvm {
     } cr;
 
   public:
-    /// Holds information about individual kills.
-    struct KillInfo {
-      bool isPHIKill : 1;
-      unsigned killIdx : 31;
 
-      KillInfo(bool isPHIKill, unsigned killIdx)
-        : isPHIKill(isPHIKill), killIdx(killIdx) {
-
-        assert(killIdx != 0 && "Zero kill indices are no longer permitted.");
-      }
-
-    };
-
-    typedef SmallVector<KillInfo, 4> KillSet;
+    typedef SmallVector<MachineInstrIndex, 4> KillSet;
 
     /// The ID number of this value.
     unsigned id;
     
     /// The index of the defining instruction (if isDefAccurate() returns true).
-    unsigned def;
+    MachineInstrIndex def;
 
     KillSet kills;
 
     VNInfo()
-      : flags(IS_UNUSED), id(~1U), def(0) { cr.copy = 0; }
+      : flags(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, unsigned d, MachineInstr *c)
+    VNInfo(unsigned i, MachineInstrIndex 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.
@@ -134,6 +334,7 @@ namespace llvm {
 
     /// Returns true if one or more kills are PHI nodes.
     bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
+    /// Set the PHI kill flag on this value.
     void setHasPHIKill(bool hasKill) {
       if (hasKill)
         flags |= HAS_PHI_KILL;
@@ -144,6 +345,7 @@ namespace llvm {
     /// Returns true if this value is re-defined by an early clobber somewhere
     /// during the live range.
     bool hasRedefByEC() const { return flags & REDEF_BY_EC; }
+    /// Set the "redef by early clobber" flag on this value.
     void setHasRedefByEC(bool hasRedef) {
       if (hasRedef)
         flags |= REDEF_BY_EC;
@@ -154,6 +356,7 @@ namespace llvm {
     /// Returns true if this value is defined by a PHI instruction (or was,
     /// PHI instrucions may have been eliminated).
     bool isPHIDef() const { return flags & IS_PHI_DEF; }
+    /// Set the "phi def" flag on this value.
     void setIsPHIDef(bool phiDef) {
       if (phiDef)
         flags |= IS_PHI_DEF;
@@ -163,6 +366,7 @@ namespace llvm {
 
     /// Returns true if this value is unused.
     bool isUnused() const { return flags & IS_UNUSED; }
+    /// Set the "is unused" flag on this value.
     void setIsUnused(bool unused) {
       if (unused)
         flags |= IS_UNUSED;
@@ -172,6 +376,7 @@ namespace llvm {
 
     /// Returns true if the def is accurate.
     bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
+    /// Set the "is def accurate" flag on this value.
     void setIsDefAccurate(bool defAccurate) {
       if (defAccurate)
         flags |= IS_DEF_ACCURATE;
@@ -179,38 +384,74 @@ namespace llvm {
         flags &= ~IS_DEF_ACCURATE;
     }
 
-  };
+    /// Returns true if the given index is a kill of this value.
+    bool isKill(MachineInstrIndex k) const {
+      KillSet::const_iterator
+        i = std::lower_bound(kills.begin(), kills.end(), k);
+      return (i != kills.end() && *i == k);
+    }
 
-  inline bool operator<(const VNInfo::KillInfo &k1, const VNInfo::KillInfo &k2){
-    return k1.killIdx < k2.killIdx;
-  }
-  
-  inline bool operator<(const VNInfo::KillInfo &k, unsigned idx) {
-    return k.killIdx < idx;
-  }
+    /// addKill - Add a kill instruction index to the specified value
+    /// number.
+    void addKill(MachineInstrIndex k) {
+      if (kills.empty()) {
+        kills.push_back(k);
+      } else {
+        KillSet::iterator
+          i = std::lower_bound(kills.begin(), kills.end(), k);
+        kills.insert(i, k);
+      }
+    }
 
-  inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) {
-    return idx < k.killIdx;
-  }
+    /// Remove the specified kill index from this value's kills list.
+    /// Returns true if the value was present, otherwise returns false.
+    bool removeKill(MachineInstrIndex k) {
+      KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
+      if (i != kills.end() && *i == k) {
+        kills.erase(i);
+        return true;
+      }
+      return false;
+    }
+
+    /// Remove all kills in the range [s, e).
+    void removeKills(MachineInstrIndex s, MachineInstrIndex e) {
+      KillSet::iterator
+        si = std::lower_bound(kills.begin(), kills.end(), s),
+        se = std::upper_bound(kills.begin(), kills.end(), e);
+
+      kills.erase(si, se);
+    }
+
+  };
 
   /// LiveRange structure - This represents a simple register range in the
   /// program, with an inclusive start point and an exclusive end point.
   /// These ranges are rendered as [start,end).
   struct LiveRange {
-    unsigned start;  // Start point of the interval (inclusive)
-    unsigned end;    // End point of the interval (exclusive)
+    MachineInstrIndex start;  // Start point of the interval (inclusive)
+    MachineInstrIndex end;    // End point of the interval (exclusive)
     VNInfo *valno;   // identifier for the value contained in this interval.
 
-    LiveRange(unsigned S, unsigned E, VNInfo *V) : start(S), end(E), valno(V) {
+    LiveRange(MachineInstrIndex S, MachineInstrIndex E, VNInfo *V)
+      : start(S), end(E), valno(V) {
+
       assert(S < E && "Cannot create empty or backwards range");
     }
 
     /// contains - Return true if the index is covered by this range.
     ///
-    bool contains(unsigned I) const {
+    bool contains(MachineInstrIndex I) const {
       return start <= I && I < end;
     }
 
+    /// containsRange - Return true if the given range, [S, E), is covered by
+    /// this range. 
+    bool containsRange(MachineInstrIndex S, MachineInstrIndex E) const {
+      assert((S < E) && "Backwards interval?");
+      return (start <= S && S < end) && (start < E && E <= end);
+    }
+
     bool operator<(const LiveRange &LR) const {
       return start < LR.start || (start == LR.start && end < LR.end);
     }
@@ -228,11 +469,11 @@ namespace llvm {
   raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 
 
-  inline bool operator<(unsigned V, const LiveRange &LR) {
+  inline bool operator<(MachineInstrIndex V, const LiveRange &LR) {
     return V < LR.start;
   }
 
-  inline bool operator<(const LiveRange &LR, unsigned V) {
+  inline bool operator<(const LiveRange &LR, MachineInstrIndex V) {
     return LR.start < V;
   }
 
@@ -260,14 +501,6 @@ namespace llvm {
         NUM   = 4
       };
 
-      static unsigned scale(unsigned slot, unsigned factor) {
-        unsigned index = slot / NUM,
-                 offset = slot % NUM;
-        assert(index <= ~0U / (factor * NUM) &&
-               "Rescaled interval would overflow");
-        return index * NUM * factor + offset;
-      }
-
     };
 
     LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
@@ -297,8 +530,8 @@ 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, unsigned Pos) {
-      if (Pos >= endNumber())
+    iterator advanceTo(iterator I, MachineInstrIndex Pos) {
+      if (Pos >= endIndex())
         return end();
       while (I->end <= Pos) ++I;
       return I;
@@ -344,15 +577,12 @@ namespace llvm {
 
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
-    VNInfo *getNextValue(unsigned MIIdx, MachineInstr *CopyMI,
+    VNInfo *getNextValue(MachineInstrIndex def, MachineInstr *CopyMI,
                          bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
-
-      assert(MIIdx != ~0u && MIIdx != ~1u &&
-             "PHI def / unused flags should now be passed explicitly.");
       VNInfo *VNI =
         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
                                                       alignof<VNInfo>()));
-      new (VNI) VNInfo((unsigned)valnos.size(), MIIdx, CopyMI);
+      new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI);
       VNI->setIsDefAccurate(isDefAccurate);
       valnos.push_back(VNI);
       return VNI;
@@ -372,50 +602,52 @@ namespace llvm {
       return VNI;
     }
 
-    /// addKill - Add a kill instruction index to the specified value
-    /// number.
-    static void addKill(VNInfo *VNI, unsigned KillIdx, bool phiKill) {
-      VNInfo::KillSet &kills = VNI->kills;
-      VNInfo::KillInfo newKill(phiKill, KillIdx);
-      if (kills.empty()) {
-        kills.push_back(newKill);
-      } else {
-        VNInfo::KillSet::iterator
-          I = std::lower_bound(kills.begin(), kills.end(), newKill);
-        kills.insert(I, newKill);
-      }
-    }
-
     /// addKills - Add a number of kills into the VNInfo kill vector. If this
     /// interval is live at a kill point, then the kill is not added.
     void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
       for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
            i != e; ++i) {
-        const VNInfo::KillInfo &Kill = kills[i];
-        if (!liveBeforeAndAt(Kill.killIdx)) {
-          VNInfo::KillSet::iterator
-            I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
-          VNI->kills.insert(I, Kill);
+        if (!liveBeforeAndAt(kills[i])) {
+          VNI->addKill(kills[i]);
         }
       }
     }
 
+    /* REMOVE_ME
+    /// addKill - Add a kill instruction index to the specified value
+    /// number.
+    static void addKill(VNInfo *VNI, MachineInstrIndex killIdx) {
+      assert(killIdx.isUse() && "Kill must be a use.");
+      if (VNI->kills.empty()) {
+        VNI->kills.push_back(killIdx);
+      } else {
+        VNInfo::KillSet::iterator
+          I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), killIdx);
+        VNI->kills.insert(I, killIdx);
+      }
+    }
+
     /// removeKill - Remove the specified kill from the list of kills of
     /// the specified val#.
-    static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
-      VNInfo::KillSet &kills = VNI->kills;
+    static bool removeKill(VNInfo *VNI, MachineInstrIndex Kill) {
+      
       VNInfo::KillSet::iterator
-        I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      if (I != kills.end() && I->killIdx == KillIdx) {
-        kills.erase(I);
+        I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
+      if (I != VNI->kills.end() && (*I == Kill)) {
+        VNI->kills.erase(I);
         return true;
       }
       return false;
+      
     }
+    
+
 
     /// removeKills - Remove all the kills in specified range
     /// [Start, End] of the specified val#.
-    static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
+    static void removeKills(VNInfo *VNI, MachineInstrIndex Start,
+                                         MachineInstrIndex End) {
+
       VNInfo::KillSet &kills = VNI->kills;
 
       VNInfo::KillSet::iterator
@@ -424,15 +656,16 @@ namespace llvm {
         E = std::upper_bound(kills.begin(), kills.end(), End);
       kills.erase(I, E);
     }
+    
 
     /// isKill - Return true if the specified index is a kill of the
     /// specified val#.
-    static bool isKill(const VNInfo *VNI, unsigned KillIdx) {
-      const VNInfo::KillSet &kills = VNI->kills;
+    static bool isKill(const VNInfo *VNI, MachineInstrIndex Kill) {
       VNInfo::KillSet::const_iterator
-        I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      return I != kills.end() && I->killIdx == KillIdx;
+        I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
+      return I != VNI->kills.end() && (*I == Kill);
     }
+    */
 
     /// isOnlyLROfValNo - Return true if the specified live range is the only
     /// one defined by the its val#.
@@ -460,7 +693,8 @@ namespace llvm {
 
     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
     /// single LiveRange only.
-    void MergeInClobberRange(unsigned Start, unsigned End,
+    void MergeInClobberRange(MachineInstrIndex Start,
+                             MachineInstrIndex End,
                              BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
@@ -485,58 +719,62 @@ namespace llvm {
     
     bool empty() const { return ranges.empty(); }
 
-    /// beginNumber - Return the lowest numbered slot covered by interval.
-    unsigned beginNumber() const {
+    /// beginIndex - Return the lowest numbered slot covered by interval.
+    MachineInstrIndex beginIndex() const {
       if (empty())
-        return 0;
+        return MachineInstrIndex();
       return ranges.front().start;
     }
 
     /// endNumber - return the maximum point of the interval of the whole,
     /// exclusive.
-    unsigned endNumber() const {
+    MachineInstrIndex endIndex() const {
       if (empty())
-        return 0;
+        return MachineInstrIndex();
       return ranges.back().end;
     }
 
-    bool expiredAt(unsigned index) const {
-      return index >= endNumber();
+    bool expiredAt(MachineInstrIndex index) const {
+      return index >= endIndex();
     }
 
-    bool liveAt(unsigned index) const;
+    bool liveAt(MachineInstrIndex 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(unsigned index) const;
+    bool liveBeforeAndAt(MachineInstrIndex index) const;
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    const LiveRange *getLiveRangeContaining(unsigned Idx) const {
+    const LiveRange *getLiveRangeContaining(MachineInstrIndex 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(unsigned Idx) {
+    LiveRange *getLiveRangeContaining(MachineInstrIndex 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(unsigned Idx) const;
+    const_iterator FindLiveRangeContaining(MachineInstrIndex Idx) const;
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    iterator FindLiveRangeContaining(unsigned Idx);
+    iterator FindLiveRangeContaining(MachineInstrIndex Idx);
+
+    /// findDefinedVNInfo - Find the by the specified
+    /// index (register interval) or defined 
+    VNInfo *findDefinedVNInfoForRegInt(MachineInstrIndex Idx) const;
+
+    /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
+    /// register (stack inteval only).
+    VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const;
 
-    /// findDefinedVNInfo - Find the VNInfo that's defined at the specified
-    /// index (register interval) or defined by the specified register (stack
-    /// inteval).
-    VNInfo *findDefinedVNInfo(unsigned DefIdxOrReg) const;
     
     /// overlaps - Return true if the intersection of the two live intervals is
     /// not empty.
@@ -546,7 +784,7 @@ namespace llvm {
 
     /// overlaps - Return true if the live interval overlaps a range specified
     /// by [Start, End).
-    bool overlaps(unsigned Start, unsigned End) const;
+    bool overlaps(MachineInstrIndex Start, MachineInstrIndex 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
@@ -570,11 +808,12 @@ namespace llvm {
 
     /// isInOneLiveRange - Return true if the range specified is entirely in the
     /// a single LiveRange of the live interval.
-    bool isInOneLiveRange(unsigned Start, unsigned End);
+    bool isInOneLiveRange(MachineInstrIndex Start, MachineInstrIndex End);
 
     /// removeRange - Remove the specified range from this interval.  Note that
     /// the range must be a single LiveRange in its entirety.
-    void removeRange(unsigned Start, unsigned End, bool RemoveDeadValNo = false);
+    void removeRange(MachineInstrIndex Start, MachineInstrIndex End,
+                     bool RemoveDeadValNo = false);
 
     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
       removeRange(LR.start, LR.end, RemoveDeadValNo);
@@ -597,7 +836,7 @@ namespace llvm {
     void ComputeJoinedWeight(const LiveInterval &Other);
 
     bool operator<(const LiveInterval& other) const {
-      return beginNumber() < other.beginNumber();
+      return beginIndex() < other.beginIndex();
     }
 
     void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const;
@@ -606,8 +845,8 @@ namespace llvm {
   private:
 
     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
-    void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
-    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
+    void extendIntervalEndTo(Ranges::iterator I, MachineInstrIndex NewEnd);
+    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, MachineInstrIndex NewStr);
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
 
   };
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index da9ff30edf..dbeedcf2ee 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -40,13 +40,13 @@ namespace llvm {
   class TargetInstrInfo;
   class TargetRegisterClass;
   class VirtRegMap;
-  typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
+  typedef std::pair<MachineInstrIndex, MachineBasicBlock*> IdxMBBPair;
 
-  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
+  inline bool operator<(MachineInstrIndex V, const IdxMBBPair &IM) {
     return V < IM.first;
   }
 
-  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
+  inline bool operator<(const IdxMBBPair &IM, MachineInstrIndex V) {
     return IM.first < V;
   }
 
@@ -65,13 +65,16 @@ namespace llvm {
     AliasAnalysis *aa_;
     LiveVariables* lv_;
 
+
+    
+
     /// 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<unsigned, unsigned> > MBB2IdxMap;
+    std::vector<std::pair<MachineInstrIndex, MachineInstrIndex> > MBB2IdxMap;
 
     /// Idx2MBBMap - Sorted list of pairs of index of first instruction
     /// and MBB id.
@@ -80,7 +83,7 @@ namespace llvm {
     /// FunctionSize - The number of instructions present in the function
     uint64_t FunctionSize;
 
-    typedef DenseMap<const MachineInstr*, unsigned> Mi2IndexMap;
+    typedef DenseMap<const MachineInstr*, MachineInstrIndex> Mi2IndexMap;
     Mi2IndexMap mi2iMap_;
 
     typedef std::vector<MachineInstr*> Index2MiMap;
@@ -89,7 +92,7 @@ namespace llvm {
     typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
     Reg2IntervalMap r2iMap_;
 
-    DenseMap<MachineBasicBlock*, unsigned> terminatorGaps;
+    DenseMap<MachineBasicBlock*, MachineInstrIndex> terminatorGaps;
 
     BitVector allocatableRegs_;
 
@@ -101,23 +104,40 @@ namespace llvm {
     static char ID; // Pass identification, replacement for typeid
     LiveIntervals() : MachineFunctionPass(&ID) {}
 
-    static unsigned getBaseIndex(unsigned index) {
-      return index - (index % InstrSlots::NUM);
+    static MachineInstrIndex getBaseIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index, MachineInstrIndex::LOAD);
+    }
+    static MachineInstrIndex getBoundaryIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index,
+        (MachineInstrIndex::Slot)(MachineInstrIndex::NUM - 1));
+    }
+    static MachineInstrIndex getLoadIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index, MachineInstrIndex::LOAD);
+    }
+    static MachineInstrIndex getUseIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index, MachineInstrIndex::USE);
     }
-    static unsigned getBoundaryIndex(unsigned index) {
-      return getBaseIndex(index + InstrSlots::NUM - 1);
+    static MachineInstrIndex getDefIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index, MachineInstrIndex::DEF);
     }
-    static unsigned getLoadIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::LOAD;
+    static MachineInstrIndex getStoreIndex(MachineInstrIndex index) {
+      return MachineInstrIndex(index, MachineInstrIndex::STORE);
     }
-    static unsigned getUseIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::USE;
+
+    MachineInstrIndex getNextSlot(MachineInstrIndex m) const {
+      return m.nextSlot();
+    }
+
+    MachineInstrIndex getNextIndex(MachineInstrIndex m) const {
+      return m.nextIndex();
     }
-    static unsigned getDefIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::DEF;
+
+    MachineInstrIndex getPrevSlot(MachineInstrIndex m) const {
+      return m.prevSlot();
     }
-    static unsigned getStoreIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::STORE;
+
+    MachineInstrIndex getPrevIndex(MachineInstrIndex m) const {
+      return m.prevIndex();
     }
 
     static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
@@ -150,20 +170,20 @@ namespace llvm {
 
     /// getMBBStartIdx - Return the base index of the first instruction in the
     /// specified MachineBasicBlock.
-    unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
+    MachineInstrIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
       return getMBBStartIdx(MBB->getNumber());
     }
-    unsigned getMBBStartIdx(unsigned MBBNo) const {
+    MachineInstrIndex 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.
-    unsigned getMBBEndIdx(MachineBasicBlock *MBB) const {
+    MachineInstrIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
       return getMBBEndIdx(MBB->getNumber());
     }
-    unsigned getMBBEndIdx(unsigned MBBNo) const {
+    MachineInstrIndex getMBBEndIdx(unsigned MBBNo) const {
       assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
       return MBB2IdxMap[MBBNo].second;
     }
@@ -184,7 +204,7 @@ namespace llvm {
 
     /// getMBBFromIndex - given an index in any instruction of an
     /// MBB return a pointer the MBB
-    MachineBasicBlock* getMBBFromIndex(unsigned index) const {
+    MachineBasicBlock* getMBBFromIndex(MachineInstrIndex index) const {
       std::vector<IdxMBBPair>::const_iterator I =
         std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
       // Take the pair containing the index
@@ -192,14 +212,14 @@ namespace llvm {
         ((I != Idx2MBBMap.end() && I->first > index) ||
          (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
 
-      assert(J != Idx2MBBMap.end() && J->first < index+1 &&
+      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
-    unsigned getInstructionIndex(const MachineInstr* instr) const {
+    MachineInstrIndex getInstructionIndex(const MachineInstr* instr) const {
       Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
       assert(it != mi2iMap_.end() && "Invalid instruction!");
       return it->second;
@@ -207,48 +227,50 @@ namespace llvm {
 
     /// getInstructionFromIndex - given an index in any slot of an
     /// instruction return a pointer the instruction
-    MachineInstr* getInstructionFromIndex(unsigned index) const {
-      index /= InstrSlots::NUM; // convert index to vector index
-      assert(index < i2miMap_.size() &&
+    MachineInstr* getInstructionFromIndex(MachineInstrIndex index) const {
+      // convert index to vector index
+      unsigned i = index.getVecIndex();
+      assert(i < i2miMap_.size() &&
              "index does not correspond to an instruction");
-      return i2miMap_[index];
+      return i2miMap_[i];
     }
 
     /// hasGapBeforeInstr - Return true if the previous instruction slot,
     /// i.e. Index - InstrSlots::NUM, is not occupied.
-    bool hasGapBeforeInstr(unsigned Index) {
-      Index = getBaseIndex(Index - InstrSlots::NUM);
+    bool hasGapBeforeInstr(MachineInstrIndex Index) {
+      Index = getBaseIndex(Index.prevIndex());
       return getInstructionFromIndex(Index) == 0;
     }
 
     /// hasGapAfterInstr - Return true if the successive instruction slot,
     /// i.e. Index + InstrSlots::Num, is not occupied.
-    bool hasGapAfterInstr(unsigned Index) {
-      Index = getBaseIndex(Index + InstrSlots::NUM);
+    bool hasGapAfterInstr(MachineInstrIndex Index) {
+      Index = getBaseIndex(Index.nextIndex());
       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).
-    unsigned findGapBeforeInstr(unsigned Index, bool Furthest = false) {
-      Index = getBaseIndex(Index - InstrSlots::NUM);
+    MachineInstrIndex findGapBeforeInstr(MachineInstrIndex Index,
+                                         bool Furthest = false) {
+      Index = getBaseIndex(Index.prevIndex());
       if (getInstructionFromIndex(Index))
-        return 0;  // No gap!
+        return MachineInstrIndex();  // No gap!
       if (!Furthest)
         return Index;
-      unsigned PrevIndex = getBaseIndex(Index - InstrSlots::NUM);
+      MachineInstrIndex PrevIndex = getBaseIndex(Index.prevIndex());
       while (getInstructionFromIndex(Index)) {
         Index = PrevIndex;
-        PrevIndex = getBaseIndex(Index - InstrSlots::NUM);
+        PrevIndex = getBaseIndex(Index.prevIndex());
       }
       return Index;
     }
 
     /// InsertMachineInstrInMaps - Insert the specified machine instruction
     /// into the instruction index map at the given index.
-    void InsertMachineInstrInMaps(MachineInstr *MI, unsigned Index) {
-      i2miMap_[Index / InstrSlots::NUM] = MI;
+    void InsertMachineInstrInMaps(MachineInstr *MI, MachineInstrIndex Index) {
+      i2miMap_[Index.index / MachineInstrIndex::NUM] = MI;
       Mi2IndexMap::iterator it = mi2iMap_.find(MI);
       assert(it == mi2iMap_.end() && "Already in map!");
       mi2iMap_[MI] = Index;
@@ -268,12 +290,12 @@ namespace llvm {
     /// 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(unsigned Start, unsigned End,
+    bool findLiveInMBBs(MachineInstrIndex Start, MachineInstrIndex 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(unsigned Start, unsigned End,
+    bool findReachableMBBs(MachineInstrIndex Start, MachineInstrIndex End,
                         SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
 
     // Interval creation
@@ -292,7 +314,7 @@ namespace llvm {
     /// addLiveRangeToEndOfBlock - Given a register and an instruction,
     /// adds a live range from that instruction to the end of its MBB.
     LiveRange addLiveRangeToEndOfBlock(unsigned reg,
-                                        MachineInstr* startInst);
+                                       MachineInstr* startInst);
 
     // Interval removal
 
@@ -315,7 +337,7 @@ namespace llvm {
       // MachineInstr -> index mappings
       Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
       if (mi2i != mi2iMap_.end()) {
-        i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
+        i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
         mi2iMap_.erase(mi2i);
       }
     }
@@ -326,10 +348,10 @@ namespace llvm {
       Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
       if (mi2i == mi2iMap_.end())
         return;
-      i2miMap_[mi2i->second/InstrSlots::NUM] = NewMI;
+      i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
       Mi2IndexMap::iterator it = mi2iMap_.find(MI);
       assert(it != mi2iMap_.end() && "Invalid instruction!");
-      unsigned Index = it->second;
+      MachineInstrIndex Index = it->second;
       mi2iMap_.erase(it);
       mi2iMap_[NewMI] = Index;
     }
@@ -413,27 +435,29 @@ namespace llvm {
     /// (calls handlePhysicalRegisterDef and
     /// handleVirtualRegisterDef)
     void handleRegisterDef(MachineBasicBlock *MBB,
-                           MachineBasicBlock::iterator MI, unsigned MIIdx,
+                           MachineBasicBlock::iterator MI,
+                           MachineInstrIndex MIIdx,
                            MachineOperand& MO, unsigned MOIdx);
 
     /// handleVirtualRegisterDef - update intervals for a virtual
     /// register def
     void handleVirtualRegisterDef(MachineBasicBlock *MBB,
                                   MachineBasicBlock::iterator MI,
-                                  unsigned MIIdx, MachineOperand& MO,
-                                  unsigned MOIdx, LiveInterval& interval);
+                                  MachineInstrIndex MIIdx, MachineOperand& MO,
+                                  unsigned MOIdx,
+                                  LiveInterval& interval);
 
     /// handlePhysicalRegisterDef - update intervals for a physical register
     /// def.
     void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
                                    MachineBasicBlock::iterator mi,
-                                   unsigned MIIdx, MachineOperand& MO,
+                                   MachineInstrIndex MIIdx, MachineOperand& MO,
                                    LiveInterval &interval,
                                    MachineInstr *CopyMI);
 
     /// handleLiveInRegister - Create interval for a livein register.
     void handleLiveInRegister(MachineBasicBlock* mbb,
-                              unsigned MIIdx,
+                              MachineInstrIndex MIIdx,
                               LiveInterval &interval, bool isAlias = false);
 
     /// getReMatImplicitUse - If the remat definition MI has one (for now, we
@@ -446,7 +470,7 @@ namespace llvm {
     /// which reaches the given instruction also reaches the specified use
     /// index.
     bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
-                            unsigned UseIdx) const;
+                            MachineInstrIndex UseIdx) const;
 
     /// isReMaterializable - Returns true if the definition MI of the specified
     /// val# of the specified interval is re-materializable. Also returns true
@@ -461,9 +485,9 @@ namespace llvm {
     /// MI. If it is successul, MI is updated with the newly created MI and
     /// returns true.
     bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
-                              MachineInstr *DefMI, unsigned InstrIdx,
+                              MachineInstr *DefMI, MachineInstrIndex InstrIdx,
                               SmallVector<unsigned, 2> &Ops,
-                              bool isSS, int Slot, unsigned Reg);
+                              bool isSS, int FrameIndex, unsigned Reg);
 
     /// canFoldMemoryOperand - Return true if the specified load / store
     /// folding is possible.
@@ -474,7 +498,8 @@ namespace llvm {
     /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
     /// VNInfo that's after the specified index but is within the basic block.
     bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
-                              MachineBasicBlock *MBB, unsigned Idx) const;
+                              MachineBasicBlock *MBB,
+                              MachineInstrIndex Idx) const;
 
     /// hasAllocatableSuperReg - Return true if the specified physical register
     /// has any super register that's allocatable.
@@ -482,16 +507,17 @@ namespace llvm {
 
     /// SRInfo - Spill / restore info.
     struct SRInfo {
-      int index;
+      MachineInstrIndex index;
       unsigned vreg;
       bool canFold;
-      SRInfo(int i, unsigned vr, bool f) : index(i), vreg(vr), canFold(f) {};
+      SRInfo(MachineInstrIndex i, unsigned vr, bool f)
+        : index(i), vreg(vr), canFold(f) {}
     };
 
-    bool alsoFoldARestore(int Id, int index, unsigned vr,
+    bool alsoFoldARestore(int Id, MachineInstrIndex index, unsigned vr,
                           BitVector &RestoreMBBs,
                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
-    void eraseRestoreInfo(int Id, int index, unsigned vr,
+    void eraseRestoreInfo(int Id, MachineInstrIndex index, unsigned vr,
                           BitVector &RestoreMBBs,
                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
 
@@ -510,8 +536,9 @@ namespace llvm {
     /// functions for addIntervalsForSpills to rewrite uses / defs for the given
     /// live range.
     bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
-        bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
-        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
+        bool TrySplit, MachineInstrIndex index, MachineInstrIndex end,
+        MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
+        unsigned Slot, int LdSlot,
         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
         VirtRegMap &vrm, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,