New VNInfo alignment patch by Ryan Flynn.
[oota-llvm.git] / include / llvm / CodeGen / LiveInterval.h
index b5b6b2e0c64bff4a6c596d27de480f67c9f35656..21af54ffd132e5c883397d7f94a59e44db570932 100644 (file)
@@ -2,14 +2,14 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LiveRange and LiveInterval classes.  Given some
 // numbering of each the machine instructions an interval [i, j) is said to be a
-// live interval for register v if there is no instruction with number j' > j
+// live interval for register v if there is no instruction with number j' >= j
 // such that v is live at j' and there is no instruction with number i' < i such
 // that v is live at i'. In this implementation intervals can have holes,
 // i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
-#include "llvm/Support/Streams.h"
+#include "llvm/Support/AlignOf.h"
 #include <iosfwd>
-#include <vector>
 #include <cassert>
+#include <climits>
 
 namespace llvm {
   class MachineInstr;
-  class MRegisterInfo;
+  class MachineRegisterInfo;
+  class TargetRegisterInfo;
   struct LiveInterval;
 
-  /// VNInfo - If the value number definition is undefined (e.g. phi
-  /// merge point), it contains ~0u,x. If the value number is not in use, it
-  /// contains ~1u,x to indicate that the value # is not used. 
-  ///   def   - Instruction # of the definition.
-  ///   reg   - Source reg iff val# is defined by a copy; zero otherwise.
-  ///   kills - Instruction # of the kills. If a kill is an odd #, it means
-  ///           the kill is a phi join point.
-  struct VNInfo {
+  /// VNInfo - Value Number Information.
+  /// This class holds information about a machine level values, including
+  /// definition and use points.
+  ///
+  /// Care must be taken in interpreting the def index of the value. The 
+  /// following rules apply:
+  ///
+  /// If the isDefAccurate() method returns false then def does not contain the
+  /// index of the defining MachineInstr, or even (necessarily) to a
+  /// MachineInstr at all. In general such a def index is not meaningful
+  /// and should not be used. The exception is that, for values originally
+  /// defined by PHI instructions, after PHI elimination def will contain the
+  /// index of the MBB in which the PHI originally existed. This can be used
+  /// to insert code (spills or copies) which deals with the value, which will
+  /// be live in to the block.
+
+  class VNInfo {
+  private:
+    enum {
+      HAS_PHI_KILL    = 1,                         
+      REDEF_BY_EC     = 1 << 1,
+      IS_PHI_DEF      = 1 << 2,
+      IS_UNUSED       = 1 << 3,
+      IS_DEF_ACCURATE = 1 << 4
+    };
+
+    unsigned char flags;
+
+  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;
+
+    /// The ID number of this value.
     unsigned id;
+    
+    /// The index of the defining instruction (if isDefAccurate() returns true).
     unsigned def;
-    unsigned reg;
-    SmallVector<unsigned, 4> kills;
-    VNInfo() : id(~1U), def(~1U), reg(0) {}
-    VNInfo(unsigned i, unsigned d, unsigned r)
-      : id(i), def(d), reg(r) {}
+    MachineInstr *copy;
+    KillSet kills;
+
+    VNInfo()
+      : flags(IS_UNUSED), id(~1U), def(0), 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)
+      : flags(IS_DEF_ACCURATE), id(i), def(d), copy(c) {}
+
+    /// VNInfo construtor, copies values from orig, except for the value number.
+    VNInfo(unsigned i, const VNInfo &orig)
+      : flags(orig.flags), id(i), def(orig.def), copy(orig.copy),
+        kills(orig.kills) {}
+
+    /// Used for copying value number info.
+    unsigned getFlags() const { return flags; }
+    void setFlags(unsigned flags) { this->flags = flags; }
+
+    /// Returns true if one or more kills are PHI nodes.
+    bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
+    void setHasPHIKill(bool hasKill) {
+      if (hasKill)
+        flags |= HAS_PHI_KILL;
+      else
+        flags &= ~HAS_PHI_KILL;
+    }
+
+    /// 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; }
+    void setHasRedefByEC(bool hasRedef) {
+      if (hasRedef)
+        flags |= REDEF_BY_EC;
+      else
+        flags &= ~REDEF_BY_EC;
+    }
+  
+    /// 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; }
+    void setIsPHIDef(bool phiDef) {
+      if (phiDef)
+        flags |= IS_PHI_DEF;
+      else
+        flags &= ~IS_PHI_DEF;
+    }
+
+    /// Returns true if this value is unused.
+    bool isUnused() const { return flags & IS_UNUSED; }
+    void setIsUnused(bool unused) {
+      if (unused)
+        flags |= IS_UNUSED;
+      else
+        flags &= ~IS_UNUSED;
+    }
+
+    /// Returns true if the def is accurate.
+    bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
+    void setIsDefAccurate(bool defAccurate) {
+      if (defAccurate)
+        flags |= IS_DEF_ACCURATE;
+      else 
+        flags &= ~IS_DEF_ACCURATE;
+    }
+
   };
 
+  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;
+  }
+
+  inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) {
+    return idx < k.killIdx;
+  }
+
   /// 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).
@@ -97,19 +212,41 @@ namespace llvm {
   /// LiveInterval - This class represents some number of live ranges for a
   /// register or value.  This class also contains a bit of register allocator
   /// state.
-  struct LiveInterval {
+  class LiveInterval {
+  public:
+
     typedef SmallVector<LiveRange,4> Ranges;
     typedef SmallVector<VNInfo*,4> VNInfoList;
 
-    unsigned reg;        // the register of this interval
-    unsigned preference; // preferred register to allocate for this interval
+    unsigned reg;        // the register or stack slot of this interval
+                         // if the top bits is set, it represents a stack slot.
     float weight;        // weight of this interval
     Ranges ranges;       // the ranges in which this register is live
     VNInfoList valnos;   // value#'s
+    
+    struct InstrSlots {
+      enum {
+        LOAD  = 0,
+        USE   = 1,
+        DEF   = 2,
+        STORE = 3,
+        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;
+      }
 
-  public:
-    LiveInterval(unsigned Reg, float Weight)
-      : reg(Reg), preference(0), weight(Weight) {
+    };
+
+    LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
+      : reg(Reg), weight(Weight) {
+      if (IsSS)
+        reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1));
     }
 
     typedef Ranges::iterator iterator;
@@ -139,10 +276,35 @@ namespace llvm {
       while (I->end <= Pos) ++I;
       return I;
     }
+    
+    void clear() {
+      while (!valnos.empty()) {
+        VNInfo *VNI = valnos.back();
+        valnos.pop_back();
+        VNI->~VNInfo();
+      }
+      
+      ranges.clear();
+    }
+
+    /// isStackSlot - Return true if this is a stack slot interval.
+    ///
+    bool isStackSlot() const {
+      return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1));
+    }
+
+    /// getStackSlotIndex - Return stack slot index if this is a stack slot
+    /// interval.
+    int getStackSlotIndex() const {
+      assert(isStackSlot() && "Interval is not a stack slot interval!");
+      return reg & ~(1U << (sizeof(unsigned)*CHAR_BIT-1));
+    }
+
+    bool hasAtLeastOneValue() const { return !valnos.empty(); }
 
     bool containsOneValue() const { return valnos.size() == 1; }
 
-    unsigned getNumValNums() const { return valnos.size(); }
+    unsigned getNumValNums() const { return (unsigned)valnos.size(); }
     
     /// getValNumInfo - Returns pointer to the specified val#.
     ///
@@ -155,50 +317,66 @@ namespace llvm {
     
     /// copyValNumInfo - Copy the value number info for one value number to
     /// another.
-    void copyValNumInfo(VNInfo *DstValNo, VNInfo *SrcValNo) {
+    void copyValNumInfo(VNInfo *DstValNo, const VNInfo *SrcValNo) {
       DstValNo->def = SrcValNo->def;
-      DstValNo->reg = SrcValNo->reg;
+      DstValNo->copy = SrcValNo->copy;
+      DstValNo->setFlags(SrcValNo->getFlags());
       DstValNo->kills = SrcValNo->kills;
     }
 
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
-    VNInfo *getNextValue(unsigned MIIdx, unsigned SrcReg) {
-#ifdef __GNUC__
-      unsigned Alignment = __alignof__(VNInfo);
-#else
-      // FIXME: ugly.
-      unsigned Alignment = 8;
-#endif
-      VNInfo *VNI= static_cast<VNInfo*>(VNInfoAllocator.Allocate(sizeof(VNInfo),
-                                                                 Alignment));
-      new (VNI) VNInfo(valnos.size(), MIIdx, SrcReg);
+    VNInfo *getNextValue(unsigned MIIdx, 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);
+      VNI->setIsDefAccurate(isDefAccurate);
+      valnos.push_back(VNI);
+      return VNI;
+    }
+
+    /// Create a copy of the given value. The new value will be identical except
+    /// for the Value number.
+    VNInfo *createValueCopy(const VNInfo *orig, BumpPtrAllocator &VNInfoAllocator) {
+
+      VNInfo *VNI =
+        static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
+                                                      alignof<VNInfo>()));
+    
+      new (VNI) VNInfo((unsigned)valnos.size(), *orig);
       valnos.push_back(VNI);
       return VNI;
     }
 
-    /// addKillForValNum - Add a kill instruction index to the specified value
+    /// addKill - Add a kill instruction index to the specified value
     /// number.
-    static void addKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
+    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(KillIdx);
+        kills.push_back(newKill);
       } else {
-        SmallVector<unsigned, 4>::iterator
-          I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-        kills.insert(I, KillIdx);
+        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 SmallVector<unsigned, 4> &kills) {
-      for (unsigned i = 0, e = kills.size(); i != e; ++i) {
-        unsigned KillIdx = kills[i];
-        if (!liveAt(KillIdx)) {
-          SmallVector<unsigned, 4>::iterator
-            I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), KillIdx);
-          VNI->kills.insert(I, KillIdx);
+    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);
         }
       }
     }
@@ -206,10 +384,10 @@ namespace llvm {
     /// removeKill - Remove the specified kill from the list of kills of
     /// the specified val#.
     static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
+      VNInfo::KillSet &kills = VNI->kills;
+      VNInfo::KillSet::iterator
         I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      if (I != kills.end() && *I == KillIdx) {
+      if (I != kills.end() && I->killIdx == KillIdx) {
         kills.erase(I);
         return true;
       }
@@ -218,20 +396,41 @@ namespace llvm {
 
     /// removeKills - Remove all the kills in specified range
     /// [Start, End] of the specified val#.
-    void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
+    static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
+      VNInfo::KillSet &kills = VNI->kills;
+
+      VNInfo::KillSet::iterator
         I = std::lower_bound(kills.begin(), kills.end(), Start);
-      SmallVector<unsigned, 4>::iterator
+      VNInfo::KillSet::iterator
         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;
+      VNInfo::KillSet::const_iterator
+        I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
+      return I != kills.end() && I->killIdx == KillIdx;
+    }
+
+    /// isOnlyLROfValNo - Return true if the specified live range is the only
+    /// one defined by the its val#.
+    bool isOnlyLROfValNo(const LiveRange *LR) {
+      for (const_iterator I = begin(), E = end(); I != E; ++I) {
+        const LiveRange *Tmp = I;
+        if (Tmp != LR && Tmp->valno == LR->valno)
+          return false;
+      }
+      return true;
+    }
     
     /// MergeValueNumberInto - This method is called when two value nubmers
     /// are found to be equivalent.  This eliminates V1, replacing all
     /// LiveRanges with the V1 value number with the V2 value number.  This can
     /// cause merging of V1/V2 values numbers and compaction of the value space.
-    void MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
+    VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
 
     /// MergeInClobberRanges - For any live ranges that are not defined in the
     /// current interval, but are defined in the Clobbers interval, mark them
@@ -240,24 +439,45 @@ namespace llvm {
     void MergeInClobberRanges(const LiveInterval &Clobbers,
                               BumpPtrAllocator &VNInfoAllocator);
 
-    /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
-    /// interval as the specified value number.  The LiveRanges in RHS are
-    /// allowed to overlap with LiveRanges in the current interval, but only if
-    /// the overlapping LiveRanges have the specified value number.
+    /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
+    /// single LiveRange only.
+    void MergeInClobberRange(unsigned Start, unsigned End,
+                             BumpPtrAllocator &VNInfoAllocator);
+
+    /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+    /// in RHS into this live interval as the specified value number.
+    /// 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 MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo);
+
+    /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+    /// in RHS into this live interval as the specified value number.
+    /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
+    /// current interval, but only if the overlapping LiveRanges have the
+    /// specified value number.
+    void MergeValueInAsValue(const LiveInterval &RHS,
+                             const VNInfo *RHSValNo, VNInfo *LHSValNo);
+
+    /// Copy - Copy the specified live interval. This copies all the fields
+    /// except for the register of the interval.
+    void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
+              BumpPtrAllocator &VNInfoAllocator);
     
     bool empty() const { return ranges.empty(); }
 
     /// beginNumber - Return the lowest numbered slot covered by interval.
     unsigned beginNumber() const {
-      assert(!empty() && "empty interval for register");
+      if (empty())
+        return 0;
       return ranges.front().start;
     }
 
     /// endNumber - return the maximum point of the interval of the whole,
     /// exclusive.
     unsigned endNumber() const {
-      assert(!empty() && "empty interval for register");
+      if (empty())
+        return 0;
       return ranges.back().end;
     }
 
@@ -267,6 +487,11 @@ namespace llvm {
 
     bool liveAt(unsigned 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;
+
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
     const LiveRange *getLiveRangeContaining(unsigned Idx) const {
@@ -274,6 +499,13 @@ namespace llvm {
       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) {
+      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;
@@ -281,19 +513,22 @@ namespace llvm {
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
     iterator FindLiveRangeContaining(unsigned Idx);
-    
-    /// getOverlapingRanges - Given another live interval which is defined as a
-    /// copy from this one, return a list of all of the live ranges where the
-    /// two overlap and have different value numbers.
-    void getOverlapingRanges(const LiveInterval &Other, unsigned CopyIdx,
-                             std::vector<LiveRange*> &Ranges);
 
+    /// 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.
     bool overlaps(const LiveInterval& other) const {
       return overlapsFrom(other, other.begin());
     }
 
+    /// overlaps - Return true if the live interval overlaps a range specified
+    /// by [Start, End).
+    bool overlaps(unsigned Start, unsigned 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
     /// scanning the Other interval starting at I.
@@ -309,17 +544,31 @@ 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, int *ValNoAssignments,
-              int *RHSValNoAssignments, SmallVector<VNInfo*, 16> &NewVNInfo);
+    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(unsigned Start, unsigned End);
 
     /// removeRange - Remove the specified range from this interval.  Note that
-    /// the range must already be in this interval in its entirety.
-    void removeRange(unsigned Start, unsigned End);
+    /// the range must be a single LiveRange in its entirety.
+    void removeRange(unsigned Start, unsigned End, bool RemoveDeadValNo = false);
 
-    void removeRange(LiveRange LR) {
-      removeRange(LR.start, LR.end);
+    void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
+      removeRange(LR.start, LR.end, RemoveDeadValNo);
     }
 
+    /// removeValNo - Remove all the ranges defined by the specified value#.
+    /// Also remove the value# from value# list.
+    void removeValNo(VNInfo *ValNo);
+
+    /// scaleNumbering - Renumber VNI and ranges to provide gaps for new
+    /// instructions.
+    void scaleNumbering(unsigned factor);
+
     /// getSize - Returns the sum of sizes of all the LiveRange's.
     ///
     unsigned getSize() const;
@@ -328,17 +577,19 @@ namespace llvm {
       return beginNumber() < other.beginNumber();
     }
 
-    void print(std::ostream &OS, const MRegisterInfo *MRI = 0) const;
-    void print(std::ostream *OS, const MRegisterInfo *MRI = 0) const {
-      if (OS) print(*OS, MRI);
+    void print(std::ostream &OS, const TargetRegisterInfo *TRI = 0) const;
+    void print(std::ostream *OS, const TargetRegisterInfo *TRI = 0) const {
+      if (OS) print(*OS, TRI);
     }
     void dump() const;
 
   private:
+
     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
     void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
     Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
+
   };
 
   inline std::ostream &operator<<(std::ostream &OS, const LiveInterval &LI) {