Expose the LiveInterval interfaces as public headers.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23400 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 01298e9..2cbb46b 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/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/lib/CodeGen/LiveInterval.h b/lib/CodeGen/LiveInterval.h
deleted file mode 100644
index 6cac096..0000000
--- a/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/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 0dac8bb..337dade 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/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/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h
deleted file mode 100644
index 02ecea7..0000000
--- a/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/lib/CodeGen/RegAllocIterativeScan.cpp b/lib/CodeGen/RegAllocIterativeScan.cpp
index 0ebef5e..ca7eddd 100644
--- a/lib/CodeGen/RegAllocIterativeScan.cpp
+++ b/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/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 584316e..a42a366 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/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"