Pull the LiveRange and LiveInterval classes out of LiveIntervals.h (which

will soon be renamed) into their own file.  The new file should not emit
DEBUG output or have other side effects.  The LiveInterval class also now
doesn't know whether its working on registers or some other thing.

In the future we will want to use the LiveInterval class and friends to do
stack packing.  In addition to a code simplification, this will allow us to
do it more easily.


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

2 files changed, 110 insertions, 75 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
new file mode 100644
index 0000000000..33bc036b66
--- /dev/null
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -0,0 +1,109 @@
+//===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===//
+//
+//                     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 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
+// such that v is live at j' abd 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
+// individual range is represented as an instance of LiveRange, and the whole
+// interval is represented as an instance of LiveInterval.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
+#define LLVM_CODEGEN_LIVEINTERVAL_H
+
+#include <iosfwd>
+#include <vector>
+#include <cassert>
+
+namespace llvm {
+  /// 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)
+    LiveRange(unsigned S, unsigned E) : start(S), end(E) {
+      assert(S < E && "Cannot create empty or backwards range");
+    }
+
+    bool operator<(const LiveRange &LR) const {
+      return start < LR.start || (start == LR.start && end < LR.end);
+    }
+    bool operator==(const LiveRange &LR) const {
+      return start == LR.start && end == LR.end;
+    }
+    private:
+    LiveRange(); // DO NOT IMPLEMENT
+  };
+  std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
+
+  /// 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 {
+    typedef std::vector<LiveRange> Ranges;
+    unsigned reg;        // the register of this interval
+    float weight;        // weight of this interval
+    Ranges ranges;       // the ranges in which this register is live
+    bool isDefinedOnce;  // True if this interval contains one value.
+
+    LiveInterval(unsigned Reg, float Weight)
+      : reg(Reg), weight(Weight), isDefinedOnce(false) {
+    }
+
+    bool containsOneValue() const { return isDefinedOnce; }
+
+    bool empty() const { return ranges.empty(); }
+
+    /// start - Return the lowest numbered slot covered by interval.
+    unsigned start() const {
+      assert(!empty() && "empty interval for register");
+      return ranges.front().start;
+    }
+
+    /// end - return the maximum point of the interval of the whole,
+    /// exclusive.
+    unsigned end() const {
+      assert(!empty() && "empty interval for register");
+      return ranges.back().end;
+    }
+
+    bool expiredAt(unsigned index) const {
+      return end() <= (index + 1);
+    }
+
+    bool liveAt(unsigned index) const;
+
+    bool overlaps(const LiveInterval& other) const;
+
+    void addRange(LiveRange R);
+
+    void join(const LiveInterval& other);
+
+    bool operator<(const LiveInterval& other) const {
+      return start() < other.start();
+    }
+
+    bool operator==(const LiveInterval& other) const {
+      return reg == other.reg;
+    }
+
+  private:
+    Ranges::iterator mergeRangesForward(Ranges::iterator it);
+    Ranges::iterator mergeRangesBackward(Ranges::iterator it);
+  };
+
+  std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
+}
+
+#endif
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index a70deffdc1..84c8e069df 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -21,6 +21,7 @@
 #define LLVM_CODEGEN_LIVEINTERVALS_H
 
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "LiveInterval.h"
 #include <list>
 
 namespace llvm {
@@ -29,81 +30,6 @@ namespace llvm {
     class MRegisterInfo;
     class VirtRegMap;
 
-    /// 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)
-      LiveRange(unsigned S, unsigned E) : start(S), end(E) {
-        assert(S < E && "Cannot create empty or backwards range");
-      }
-
-      bool operator<(const LiveRange &LR) const {
-        return start < LR.start || (start == LR.start && end < LR.end);
-      }
-      bool operator==(const LiveRange &LR) const {
-        return start == LR.start && end == LR.end;
-      }
-    private:
-      LiveRange(); // DO NOT IMPLEMENT
-    };
-    std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
-
-    struct LiveInterval {
-        typedef std::vector<LiveRange> Ranges;
-        unsigned reg;   // the register of this interval
-        float weight;   // weight of this interval:
-                        //     (number of uses *10^loopDepth)
-        Ranges ranges;  // the ranges in which this register is live
-        bool isDefinedOnce;  // True if there is one def of this register
-
-        explicit LiveInterval(unsigned r);
-
-        bool empty() const { return ranges.empty(); }
-
-        bool spilled() const;
-
-        /// start - Return the lowest numbered slot covered by interval.
-        unsigned start() const {
-            assert(!empty() && "empty interval for register");
-            return ranges.front().start;
-        }
-
-        /// end - return the maximum point of the interval of the whole,
-        /// exclusive.
-        unsigned end() const {
-            assert(!empty() && "empty interval for register");
-            return ranges.back().end;
-        }
-
-        bool expiredAt(unsigned index) const {
-            return end() <= (index + 1);
-        }
-
-        bool liveAt(unsigned index) const;
-
-        bool overlaps(const LiveInterval& other) const;
-
-        void addRange(LiveRange R);
-
-        void join(const LiveInterval& other);
-
-        bool operator<(const LiveInterval& other) const {
-            return start() < other.start();
-        }
-
-        bool operator==(const LiveInterval& other) const {
-            return reg == other.reg;
-        }
-
-    private:
-        Ranges::iterator mergeRangesForward(Ranges::iterator it);
-        Ranges::iterator mergeRangesBackward(Ranges::iterator it);
-    };
-
-    std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
-
     class LiveIntervals : public MachineFunctionPass
     {
     public: