X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveInterval.h;h=2288c1a98b2db22e6deb87318e52344b8740448e;hb=7b8c2f8587763e0a8ce48f9b7b67287930129c8d;hp=024ca92af9f7ca30bd21da9ba72f49ab16d1f254;hpb=4974b6aae1ec6f385ee212942d9a01ba1f4997e3;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 024ca92af9f..2288c1a98b2 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -9,7 +9,7 @@ // // 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 @@ -21,53 +21,155 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_H #define LLVM_CODEGEN_LIVEINTERVAL_H -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/IntEqClasses.h" #include "llvm/Support/Allocator.h" -#include +#include "llvm/Support/AlignOf.h" +#include "llvm/CodeGen/SlotIndexes.h" #include +#include namespace llvm { + class LiveIntervals; class MachineInstr; + 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. - /// - or reg # of the definition if it's a stack slot liveinterval. - /// copy - Copy iff val# is defined by a copy; zero otherwise. - /// hasPHIKill - One or more of the kills are PHI nodes. - /// kills - Instruction # of the kills. - struct VNInfo { - unsigned id; - unsigned def; + class raw_ostream; + + /// VNInfo - Value Number Information. + /// This class holds information about a machine level values, including + /// definition and use points. + /// + class VNInfo { + private: + enum { + HAS_PHI_KILL = 1, + REDEF_BY_EC = 1 << 1, + IS_PHI_DEF = 1 << 2, + IS_UNUSED = 1 << 3 + }; + MachineInstr *copy; - bool hasPHIKill; - SmallVector kills; - VNInfo() : id(~1U), def(~1U), copy(0), hasPHIKill(false) {} - VNInfo(unsigned i, unsigned d, MachineInstr *c) - : id(i), def(d), copy(c), hasPHIKill(false) {} + unsigned char flags; + + public: + typedef BumpPtrAllocator Allocator; + + /// The ID number of this value. + unsigned id; + + /// The index of the defining instruction (if isDefAccurate() returns true). + SlotIndex def; + + /// VNInfo constructor. + VNInfo(unsigned i, SlotIndex d, MachineInstr *c) + : copy(c), flags(0), id(i), def(d) + { } + + /// VNInfo construtor, copies values from orig, except for the value number. + VNInfo(unsigned i, const VNInfo &orig) + : copy(orig.copy), flags(orig.flags), id(i), def(orig.def) + { } + + /// Copy from the parameter into this VNInfo. + void copyFrom(VNInfo &src) { + flags = src.flags; + copy = src.copy; + def = src.def; + } + + /// Used for copying value number info. + unsigned getFlags() const { return flags; } + void setFlags(unsigned flags) { this->flags = flags; } + + /// Merge flags from another VNInfo + void mergeFlags(const VNInfo *VNI) { + flags = (flags | VNI->flags) & ~IS_UNUSED; + } + + /// For a register interval, if this VN was definied by a copy instr + /// getCopy() returns a pointer to it, otherwise returns 0. + /// For a stack interval the behaviour of this method is undefined. + MachineInstr* getCopy() const { return copy; } + /// For a register interval, set the copy member. + /// This method should not be called on stack intervals as it may lead to + /// undefined behavior. + void setCopy(MachineInstr *c) { copy = c; } + + /// isDefByCopy - Return true when this value was defined by a copy-like + /// instruction as determined by MachineInstr::isCopyLike. + bool isDefByCopy() const { return copy != 0; } + + /// Returns true if one or more kills are PHI nodes. + /// Obsolete, do not use! + 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; + 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; } + /// Set the "redef by early clobber" flag on this value. + 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; } + /// Set the "phi def" flag on this value. + 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; } + /// Set the "is unused" flag on this value. + void setIsUnused(bool unused) { + if (unused) + flags |= IS_UNUSED; + else + flags &= ~IS_UNUSED; + } }; /// 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) + SlotIndex start; // Start point of the interval (inclusive) + SlotIndex 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(SlotIndex S, SlotIndex 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(SlotIndex I) const { return start <= I && I < end; } + /// containsRange - Return true if the given range, [S, E), is covered by + /// this range. + bool containsRange(SlotIndex S, SlotIndex 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); } @@ -76,44 +178,52 @@ namespace llvm { } void dump() const; - void print(std::ostream &os) const; - void print(std::ostream *os) const { if (os) print(*os); } + void print(raw_ostream &os) const; private: LiveRange(); // DO NOT IMPLEMENT }; - std::ostream& operator<<(std::ostream& os, const LiveRange &LR); + template <> struct isPodLike { static const bool value = true; }; + raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); - inline bool operator<(unsigned V, const LiveRange &LR) { + + inline bool operator<(SlotIndex V, const LiveRange &LR) { return V < LR.start; } - inline bool operator<(const LiveRange &LR, unsigned V) { + inline bool operator<(const LiveRange &LR, SlotIndex V) { return LR.start < V; } /// 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 Ranges; typedef SmallVector VNInfoList; - unsigned reg; // the register or stack slot of this interval - // if the top bits is set, it represents a stack slot. + const unsigned reg; // the register or stack slot of this interval. float weight; // weight of this interval - unsigned short preference; // preferred register for this interval Ranges ranges; // the ranges in which this register is live VNInfoList valnos; // value#'s - public: - LiveInterval(unsigned Reg, float Weight, bool IsSS = false) - : reg(Reg), weight(Weight), preference(0) { - if (IsSS) - reg = reg | (1U << (sizeof(unsigned)*8-1)); - } + struct InstrSlots { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4 + }; + + }; + + LiveInterval(unsigned Reg, float Weight) + : reg(Reg), weight(Weight) {} typedef Ranges::iterator iterator; iterator begin() { return ranges.begin(); } @@ -134,26 +244,32 @@ namespace llvm { /// 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 + /// position is in a hole, this method returns an iterator pointing to the /// LiveRange immediately after the hole. - iterator advanceTo(iterator I, unsigned Pos) { - if (Pos >= endNumber()) + iterator advanceTo(iterator I, SlotIndex Pos) { + assert(I != end()); + if (Pos >= endIndex()) return end(); while (I->end <= Pos) ++I; return I; } - /// isStackSlot - Return true if this is a stack slot interval. + /// find - Return an iterator pointing to the first range that ends after + /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster + /// when searching large intervals. /// - bool isStackSlot() const { - return reg & (1U << (sizeof(unsigned)*8-1)); + /// If Pos is contained in a LiveRange, that range is returned. + /// If Pos is in a hole, the following LiveRange is returned. + /// If Pos is beyond endIndex, end() is returned. + iterator find(SlotIndex Pos); + + const_iterator find(SlotIndex Pos) const { + return const_cast(this)->find(Pos); } - /// 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)*8-1)); + void clear() { + valnos.clear(); + ranges.clear(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -161,7 +277,7 @@ namespace llvm { bool containsOneValue() const { return valnos.size() == 1; } unsigned getNumValNums() const { return (unsigned)valnos.size(); } - + /// getValNumInfo - Returns pointer to the specified val#. /// inline VNInfo *getValNumInfo(unsigned ValNo) { @@ -170,106 +286,52 @@ namespace llvm { inline const VNInfo *getValNumInfo(unsigned ValNo) const { return valnos[ValNo]; } - - /// copyValNumInfo - Copy the value number info for one value number to - /// another. - void copyValNumInfo(VNInfo *DstValNo, const VNInfo *SrcValNo) { - DstValNo->def = SrcValNo->def; - DstValNo->copy = SrcValNo->copy; - DstValNo->hasPHIKill = SrcValNo->hasPHIKill; - DstValNo->kills = SrcValNo->kills; + + /// containsValue - Returns true if VNI belongs to this interval. + bool containsValue(const VNInfo *VNI) const { + return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); } /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. - VNInfo *getNextValue(unsigned MIIdx, MachineInstr *CopyMI, - BumpPtrAllocator &VNInfoAllocator) { -#ifdef __GNUC__ - unsigned Alignment = (unsigned)__alignof__(VNInfo); -#else - // FIXME: ugly. - unsigned Alignment = 8; -#endif + VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI, + VNInfo::Allocator &VNInfoAllocator) { VNInfo *VNI = - static_cast(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo), - Alignment)); - new (VNI) VNInfo((unsigned)valnos.size(), MIIdx, CopyMI); + new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def, CopyMI); valnos.push_back(VNI); return VNI; } - /// addKill - Add a kill instruction index to the specified value - /// number. - static void addKill(VNInfo *VNI, unsigned KillIdx) { - SmallVector &kills = VNI->kills; - if (kills.empty()) { - kills.push_back(KillIdx); - } else { - SmallVector::iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - kills.insert(I, KillIdx); - } - } - - /// 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 &kills) { - for (unsigned i = 0, e = static_cast(kills.size()); - i != e; ++i) { - unsigned KillIdx = kills[i]; - if (!liveBeforeAndAt(KillIdx)) { - SmallVector::iterator - I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), KillIdx); - VNI->kills.insert(I, KillIdx); - } - } + /// Create a copy of the given value. The new value will be identical except + /// for the Value number. + VNInfo *createValueCopy(const VNInfo *orig, + VNInfo::Allocator &VNInfoAllocator) { + VNInfo *VNI = + new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); + valnos.push_back(VNI); + return VNI; } - /// removeKill - Remove the specified kill from the list of kills of - /// the specified val#. - static bool removeKill(VNInfo *VNI, unsigned KillIdx) { - SmallVector &kills = VNI->kills; - SmallVector::iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - if (I != kills.end() && *I == KillIdx) { - kills.erase(I); - return true; + /// RenumberValues - Renumber all values in order of appearance and remove + /// unused values. + void RenumberValues(LiveIntervals &lis); + + /// 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 false; + return true; } - /// removeKills - Remove all the kills in specified range - /// [Start, End] of the specified val#. - void removeKills(VNInfo *VNI, unsigned Start, unsigned End) { - SmallVector &kills = VNI->kills; - SmallVector::iterator - I = std::lower_bound(kills.begin(), kills.end(), Start); - SmallVector::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#. - bool isKill(const VNInfo *VNI, unsigned KillIdx) const { - const SmallVector &kills = VNI->kills; - SmallVector::const_iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - return I != kills.end() && *I == KillIdx; - } - /// 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); - - /// MergeInClobberRanges - For any live ranges that are not defined in the - /// current interval, but are defined in the Clobbers interval, mark them - /// used with an unknown definition value. Caller must pass in reference to - /// VNInfoAllocator since it will create a new val#. - void MergeInClobberRanges(const LiveInterval &Clobbers, - BumpPtrAllocator &VNInfoAllocator); + VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); /// MergeValueInAsValue - Merge all of the live ranges of a specific val# /// in RHS into this live interval as the specified value number. @@ -288,62 +350,104 @@ namespace llvm { /// Copy - Copy the specified live interval. This copies all the fields /// except for the register of the interval. - void Copy(const LiveInterval &RHS, BumpPtrAllocator &VNInfoAllocator); - + void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, + VNInfo::Allocator &VNInfoAllocator); + bool empty() const { return ranges.empty(); } - /// beginNumber - Return the lowest numbered slot covered by interval. - unsigned beginNumber() const { - if (empty()) - return 0; + /// beginIndex - Return the lowest numbered slot covered by interval. + SlotIndex beginIndex() const { + assert(!empty() && "Call to beginIndex() on empty interval."); return ranges.front().start; } /// endNumber - return the maximum point of the interval of the whole, /// exclusive. - unsigned endNumber() const { - if (empty()) - return 0; + SlotIndex endIndex() const { + assert(!empty() && "Call to endIndex() on empty interval."); return ranges.back().end; } - bool expiredAt(unsigned index) const { - return index >= endNumber(); + bool expiredAt(SlotIndex index) const { + return index >= endIndex(); + } + + bool liveAt(SlotIndex index) const { + const_iterator r = find(index); + return r != end() && r->start <= index; } - bool liveAt(unsigned index) const; + /// killedAt - Return true if a live range ends at index. Note that the kill + /// point is not contained in the half-open live range. It is usually the + /// getDefIndex() slot following its last use. + bool killedAt(SlotIndex index) const { + const_iterator r = find(index.getUseIndex()); + return r != end() && r->end == index; + } - // 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; + /// killedInRange - Return true if the interval has kills in [Start,End). + /// Note that the kill point is considered the end of a live range, so it is + /// not contained in the live range. If a live range ends at End, it won't + /// be counted as a kill by this method. + bool killedInRange(SlotIndex Start, SlotIndex End) 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(SlotIndex Idx) const { const_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; + /// getLiveRangeContaining - Return the live range that contains the + /// specified index, or null if there is none. + LiveRange *getLiveRangeContaining(SlotIndex Idx) { + iterator I = FindLiveRangeContaining(Idx); + return I == end() ? 0 : &*I; + } + + /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. + VNInfo *getVNInfoAt(SlotIndex Idx) const { + const_iterator I = FindLiveRangeContaining(Idx); + return I == end() ? 0 : I->valno; + } + + /// getVNInfoBefore - Return the VNInfo that is live up to but not + /// necessarilly including Idx, or NULL. Use this to find the reaching def + /// used by an instruction at this SlotIndex position. + VNInfo *getVNInfoBefore(SlotIndex Idx) const { + const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); + return I == end() ? 0 : I->valno; + } /// 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(SlotIndex Idx) { + iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } + + const_iterator FindLiveRangeContaining(SlotIndex Idx) const { + const_iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } + + /// findDefinedVNInfo - Find the by the specified + /// index (register interval) or defined + VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) 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. bool overlaps(const LiveInterval& other) const { + if (other.empty()) + return false; return overlapsFrom(other, other.begin()); } + /// overlaps - Return true if the live interval overlaps a range specified + /// by [Start, End). + bool overlaps(SlotIndex Start, SlotIndex 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. @@ -356,16 +460,31 @@ namespace llvm { addRangeFrom(LR, ranges.begin()); } + /// extendInBlock - If this interval is live before Kill in the basic block + /// that starts at StartIdx, extend it to be live up to Kill, and return + /// the value. If there is no live range before Kill, return NULL. + VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); + /// 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, const int *ValNoAssignments, + void join(LiveInterval &Other, + const int *ValNoAssignments, const int *RHSValNoAssignments, - SmallVector &NewVNInfo); + SmallVector &NewVNInfo, + MachineRegisterInfo *MRI); + + /// isInOneLiveRange - Return true if the range specified is entirely in the + /// a single LiveRange of the live interval. + bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { + const_iterator r = find(Start); + return r != end() && r->containsRange(Start, 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, bool RemoveDeadValNo = false); + /// the range must be a single LiveRange in its entirety. + void removeRange(SlotIndex Start, SlotIndex End, + bool RemoveDeadValNo = false); void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { removeRange(LR.start, LR.end, RemoveDeadValNo); @@ -379,27 +498,96 @@ namespace llvm { /// unsigned getSize() const; - bool operator<(const LiveInterval& other) const { - return beginNumber() < other.beginNumber(); + /// Returns true if the live interval is zero length, i.e. no live ranges + /// span instructions. It doesn't pay to spill such an interval. + bool isZeroLength(SlotIndexes *Indexes) const { + for (const_iterator i = begin(), e = end(); i != e; ++i) + if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < + i->end.getBaseIndex()) + return false; + return true; + } + + /// isSpillable - Can this interval be spilled? + bool isSpillable() const { + return weight != HUGE_VALF; } - 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); + /// markNotSpillable - Mark interval as not spillable + void markNotSpillable() { + weight = HUGE_VALF; + } + + /// ComputeJoinedWeight - Set the weight of a live interval after + /// Other has been merged into it. + void ComputeJoinedWeight(const LiveInterval &Other); + + bool operator<(const LiveInterval& other) const { + const SlotIndex &thisIndex = beginIndex(); + const SlotIndex &otherIndex = other.beginIndex(); + return (thisIndex < otherIndex || + (thisIndex == otherIndex && reg < other.reg)); } + + void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const; 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); + void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); + Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); + void markValNoForDeletion(VNInfo *V); + LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT + }; - inline std::ostream &operator<<(std::ostream &OS, const LiveInterval &LI) { + inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { LI.print(OS); return OS; } -} + /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a + /// LiveInterval into equivalence clases of connected components. A + /// LiveInterval that has multiple connected components can be broken into + /// multiple LiveIntervals. + /// + /// Given a LiveInterval that may have multiple connected components, run: + /// + /// unsigned numComps = ConEQ.Classify(LI); + /// if (numComps > 1) { + /// // allocate numComps-1 new LiveIntervals into LIS[1..] + /// ConEQ.Distribute(LIS); + /// } + + class ConnectedVNInfoEqClasses { + LiveIntervals &LIS; + IntEqClasses EqClass; + + // Note that values a and b are connected. + void Connect(unsigned a, unsigned b); + + unsigned Renumber(); + + public: + explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} + + /// Classify - Classify the values in LI into connected components. + /// Return the number of connected components. + unsigned Classify(const LiveInterval *LI); + + /// getEqClass - Classify creates equivalence classes numbered 0..N. Return + /// the equivalence class assigned the VNI. + unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } + + /// Distribute - Distribute values in LIV[0] into a separate LiveInterval + /// for each connected component. LIV must have a LiveInterval for each + /// connected component. The LiveIntervals in Liv[1..] must be empty. + /// Instructions using LIV[0] are rewritten. + void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); + + }; + +} #endif