Expose the LiveInterval interfaces as public headers.

llvm-svn: 23400

6 files changed, 4 insertions, 400 deletions

diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index 01298e9c6c9..2cbb46b082e 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -18,7 +18,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "LiveInterval.h"
+#include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Target/MRegisterInfo.h"
 #include <algorithm>
diff --git a/llvm/lib/CodeGen/LiveInterval.h b/llvm/lib/CodeGen/LiveInterval.h
deleted file mode 100644
index 6cac0960b21..00000000000
--- a/llvm/lib/CodeGen/LiveInterval.h
+++ /dev/null
@@ -1,197 +0,0 @@
-//===-- 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' 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
-// 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 {
-  class MRegisterInfo;
-
-  /// 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)
-    unsigned ValId;  // identifier for the value contained in this interval.
-
-    LiveRange(unsigned S, unsigned E, unsigned V) : start(S), end(E), ValId(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 {
-      return start <= I && I < end;
-    }
-
-    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;
-    }
-
-    void dump() const;
-
-  private:
-    LiveRange(); // DO NOT IMPLEMENT
-  };
-  std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
-
-  inline bool operator<(unsigned V, const LiveRange &LR) {
-    return V < LR.start;
-  }
-
-
-  /// 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
-
-    LiveInterval(unsigned Reg, float Weight)
-      : reg(Reg), weight(Weight), NumValues(0) {
-    }
-
-    typedef Ranges::iterator iterator;
-    iterator begin() { return ranges.begin(); }
-    iterator end()   { return ranges.end(); }
-
-    typedef Ranges::const_iterator const_iterator;
-    const_iterator begin() const { return ranges.begin(); }
-    const_iterator end() const  { return ranges.end(); }
-
-
-    /// advanceTo - Advance the specified iterator to point to the LiveRange
-    /// containing the specified position, or end() if the position is past the
-    /// 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())
-        return end();
-      while (I->end <= Pos) ++I;
-      return I;
-    }
-
-    void swap(LiveInterval& other) {
-      std::swap(reg, other.reg);
-      std::swap(weight, other.weight);
-      ranges.swap(other.ranges);
-      std::swap(NumValues, other.NumValues);
-    }
-
-    bool containsOneValue() const { return NumValues == 1; }
-
-    unsigned getNextValue() {
-      return NumValues++;
-    }
-
-    bool empty() const { return ranges.empty(); }
-
-    /// beginNumber - Return the lowest numbered slot covered by interval.
-    unsigned beginNumber() const {
-      assert(!empty() && "empty interval for register");
-      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");
-      return ranges.back().end;
-    }
-
-    bool expiredAt(unsigned index) const {
-      return index >= endNumber();
-    }
-
-    bool liveAt(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;
-
-
-    /// joinable - Two intervals are joinable if the either don't overlap at all
-    /// or if the destination of the copy is a single assignment value, and it
-    /// only overlaps with one value in the source interval.
-    bool joinable(const LiveInterval& other, unsigned CopyIdx) 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());
-    }
-
-    /// 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.
-    bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
-
-    /// addRange - Add the specified LiveRange to this interval, merging
-    /// intervals as appropriate.  This returns an iterator to the inserted live
-    /// range (which may have grown since it was inserted.
-    void addRange(LiveRange LR) {
-      addRangeFrom(LR, ranges.begin());
-    }
-
-    /// join - Join two live intervals (this, and other) together.  This
-    /// operation is the result of a copy instruction in the source program,
-    /// that occurs at index 'CopyIdx' that copies from 'other' to 'this'.  This
-    /// destroys 'other'.
-    void join(LiveInterval& other, unsigned CopyIdx);
-
-
-    /// 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);
-
-    bool operator<(const LiveInterval& other) const {
-      return beginNumber() < other.beginNumber();
-    }
-
-    void print(std::ostream &OS, const MRegisterInfo *MRI = 0) const;
-    void dump() const;
-
-  private:
-    unsigned NumValues;  // the number of distinct values in this interval.
-    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) {
-    LI.print(OS);
-    return OS;
-  }
-}
-
-#endif
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
index 0dac8bbb28d..337dadeb902 100644
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -16,7 +16,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "liveintervals"
-#include "LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "VirtRegMap.h"
 #include "llvm/Value.h"
 #include "llvm/Analysis/LoopInfo.h"
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.h b/llvm/lib/CodeGen/LiveIntervalAnalysis.h
deleted file mode 100644
index 02ecea7af0c..00000000000
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.h
+++ /dev/null
@@ -1,199 +0,0 @@
-//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- 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 LiveInterval analysis pass.  Given some numbering of
-// each the machine instructions (in this implemention depth-first order) 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).
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
-#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "LiveInterval.h"
-
-namespace llvm {
-
-  class LiveVariables;
-  class MRegisterInfo;
-  class TargetInstrInfo;
-  class VirtRegMap;
-
-  class LiveIntervals : public MachineFunctionPass {
-    MachineFunction* mf_;
-    const TargetMachine* tm_;
-    const MRegisterInfo* mri_;
-    const TargetInstrInfo* tii_;
-    LiveVariables* lv_;
-
-    typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
-    Mi2IndexMap mi2iMap_;
-
-    typedef std::vector<MachineInstr*> Index2MiMap;
-    Index2MiMap i2miMap_;
-
-    typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
-    Reg2IntervalMap r2iMap_;
-
-    typedef DenseMap<unsigned> Reg2RegMap;
-    Reg2RegMap r2rMap_;
-
-    std::vector<bool> allocatableRegs_;
-
-  public:
-    struct InstrSlots
-    {
-      enum {
-        LOAD  = 0,
-        USE   = 1,
-        DEF   = 2,
-        STORE = 3,
-        NUM   = 4,
-      };
-    };
-
-    static unsigned getBaseIndex(unsigned index) {
-      return index - (index % InstrSlots::NUM);
-    }
-    static unsigned getBoundaryIndex(unsigned index) {
-      return getBaseIndex(index + InstrSlots::NUM - 1);
-    }
-    static unsigned getLoadIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::LOAD;
-    }
-    static unsigned getUseIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::USE;
-    }
-    static unsigned getDefIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::DEF;
-    }
-    static unsigned getStoreIndex(unsigned index) {
-      return getBaseIndex(index) + InstrSlots::STORE;
-    }
-
-    typedef Reg2IntervalMap::iterator iterator;
-    typedef Reg2IntervalMap::const_iterator const_iterator;
-    const_iterator begin() const { return r2iMap_.begin(); }
-    const_iterator end() const { return r2iMap_.end(); }
-    iterator begin() { return r2iMap_.begin(); }
-    iterator end() { return r2iMap_.end(); }
-    unsigned getNumIntervals() const { return r2iMap_.size(); }
-
-    LiveInterval &getInterval(unsigned reg) {
-      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
-      assert(I != r2iMap_.end() && "Interval does not exist for register");
-      return I->second;
-    }
-
-    const LiveInterval &getInterval(unsigned reg) const {
-      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
-      assert(I != r2iMap_.end() && "Interval does not exist for register");
-      return I->second;
-    }
-
-    /// getInstructionIndex - returns the base index of instr
-    unsigned getInstructionIndex(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(unsigned index) const {
-      index /= InstrSlots::NUM; // convert index to vector index
-      assert(index < i2miMap_.size() &&
-             "index does not correspond to an instruction");
-      return i2miMap_[index];
-    }
-
-    std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
-                                                     VirtRegMap& vrm,
-                                                     int slot);
-
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-    virtual void releaseMemory();
-
-    /// runOnMachineFunction - pass entry point
-    virtual bool runOnMachineFunction(MachineFunction&);
-
-    /// print - Implement the dump method.
-    virtual void print(std::ostream &O, const Module* = 0) const;
-
-  private:
-    /// computeIntervals - compute live intervals
-    void computeIntervals();
-
-    /// joinIntervals - join compatible live intervals
-    void joinIntervals();
-
-    /// joinIntervalsInMachineBB - Join intervals based on move
-    /// instructions in the specified basic block.
-    void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
-
-    /// handleRegisterDef - update intervals for a register def
-    /// (calls handlePhysicalRegisterDef and
-    /// handleVirtualRegisterDef)
-    void handleRegisterDef(MachineBasicBlock* mbb,
-                           MachineBasicBlock::iterator mi,
-                           unsigned reg);
-
-    /// handleVirtualRegisterDef - update intervals for a virtual
-    /// register def
-    void handleVirtualRegisterDef(MachineBasicBlock* mbb,
-                                  MachineBasicBlock::iterator mi,
-                                  LiveInterval& interval);
-
-    /// handlePhysicalRegisterDef - update intervals for a physical register
-    /// def.  If the defining instruction is a move instruction, SrcReg will be
-    /// the input register, and DestReg will be the result.  Note that Interval
-    /// may not match DestReg (it might be an alias instead).
-    ///
-    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
-                                   MachineBasicBlock::iterator mi,
-                                   LiveInterval& interval,
-                                   unsigned SrcReg, unsigned DestReg,
-                                   bool isLiveIn = false);
-
-    /// Return true if the two specified registers belong to different
-    /// register classes.  The registers may be either phys or virt regs.
-    bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
-
-    bool overlapsAliases(const LiveInterval *lhs,
-                         const LiveInterval *rhs) const;
-
-    static LiveInterval createInterval(unsigned Reg);
-
-    LiveInterval &getOrCreateInterval(unsigned reg) {
-      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
-      if (I == r2iMap_.end())
-        I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg)));
-      return I->second;
-    }
-
-    /// rep - returns the representative of this register
-    unsigned rep(unsigned Reg) {
-      unsigned Rep = r2rMap_[Reg];
-      if (Rep)
-        return r2rMap_[Reg] = rep(Rep);
-      return Reg;
-    }
-
-    void printRegName(unsigned reg) const;
-  };
-
-} // End llvm namespace
-
-#endif
diff --git a/llvm/lib/CodeGen/RegAllocIterativeScan.cpp b/llvm/lib/CodeGen/RegAllocIterativeScan.cpp
index 0ebef5ef643..ca7eddd1cc6 100644
--- a/llvm/lib/CodeGen/RegAllocIterativeScan.cpp
+++ b/llvm/lib/CodeGen/RegAllocIterativeScan.cpp
@@ -28,7 +28,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
-#include "LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
 #include <algorithm>
diff --git a/llvm/lib/CodeGen/RegAllocLinearScan.cpp b/llvm/lib/CodeGen/RegAllocLinearScan.cpp
index 584316ecd76..a42a366ef36 100644
--- a/llvm/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/llvm/lib/CodeGen/RegAllocLinearScan.cpp
@@ -12,7 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
 #include "llvm/Function.h"