diff options
Diffstat (limited to 'include/llvm/CodeGen/LiveInterval.h')
| -rw-r--r-- | include/llvm/CodeGen/LiveInterval.h | 441 |
1 files changed, 340 insertions, 101 deletions
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 9a9bc56..00dd422 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -21,6 +21,7 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_H #define LLVM_CODEGEN_LIVEINTERVAL_H +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/AlignOf.h" @@ -32,6 +33,217 @@ namespace llvm { class MachineRegisterInfo; class TargetRegisterInfo; class raw_ostream; + + /// MachineInstrIndex - An opaque wrapper around machine indexes. + class MachineInstrIndex { + friend class VNInfo; + friend class LiveInterval; + friend class LiveIntervals; + friend struct DenseMapInfo<MachineInstrIndex>; + + public: + + enum Slot { LOAD, USE, DEF, STORE, NUM }; + + private: + + unsigned index; + + static const unsigned PHI_BIT = 1 << 31; + + public: + + /// Construct a default MachineInstrIndex pointing to a reserved index. + MachineInstrIndex() : index(0) {} + + /// Construct an index from the given index, pointing to the given slot. + MachineInstrIndex(MachineInstrIndex m, Slot s) + : index((m.index / NUM) * NUM + s) {} + + /// Print this index to the given raw_ostream. + void print(raw_ostream &os) const; + + /// Print this index to the given std::ostream. + void print(std::ostream &os) const; + + /// Compare two MachineInstrIndex objects for equality. + bool operator==(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT)); + } + /// Compare two MachineInstrIndex objects for inequality. + bool operator!=(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT)); + } + + /// Compare two MachineInstrIndex objects. Return true if the first index + /// is strictly lower than the second. + bool operator<(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT)); + } + /// Compare two MachineInstrIndex objects. Return true if the first index + /// is lower than, or equal to, the second. + bool operator<=(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT)); + } + + /// Compare two MachineInstrIndex objects. Return true if the first index + /// is greater than the second. + bool operator>(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT)); + } + + /// Compare two MachineInstrIndex objects. Return true if the first index + /// is greater than, or equal to, the second. + bool operator>=(MachineInstrIndex other) const { + return ((index & ~PHI_BIT) >= (other.index & ~PHI_BIT)); + } + + /// Returns true if this index represents a load. + bool isLoad() const { + return ((index % NUM) == LOAD); + } + + /// Returns true if this index represents a use. + bool isUse() const { + return ((index % NUM) == USE); + } + + /// Returns true if this index represents a def. + bool isDef() const { + return ((index % NUM) == DEF); + } + + /// Returns true if this index represents a store. + bool isStore() const { + return ((index % NUM) == STORE); + } + + /// Returns the slot for this MachineInstrIndex. + Slot getSlot() const { + return static_cast<Slot>(index % NUM); + } + + /// Returns true if this index represents a non-PHI use/def. + bool isNonPHIIndex() const { + return ((index & PHI_BIT) == 0); + } + + /// Returns true if this index represents a PHI use/def. + bool isPHIIndex() const { + return ((index & PHI_BIT) == PHI_BIT); + } + + private: + + /// Construct an index from the given index, with its PHI kill marker set. + MachineInstrIndex(bool phi, MachineInstrIndex o) : index(o.index) { + if (phi) + index |= PHI_BIT; + else + index &= ~PHI_BIT; + } + + explicit MachineInstrIndex(unsigned idx) + : index(idx & ~PHI_BIT) {} + + MachineInstrIndex(bool phi, unsigned idx) + : index(idx & ~PHI_BIT) { + if (phi) + index |= PHI_BIT; + } + + MachineInstrIndex(bool phi, unsigned idx, Slot slot) + : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) { + if (phi) + index |= PHI_BIT; + } + + MachineInstrIndex nextSlot() const { + assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) && + "Index out of bounds."); + return MachineInstrIndex(index + 1); + } + + MachineInstrIndex nextIndex() const { + assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) && + "Index out of bounds."); + return MachineInstrIndex(index + NUM); + } + + MachineInstrIndex prevSlot() const { + assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) && + "Index out of bounds."); + return MachineInstrIndex(index - 1); + } + + MachineInstrIndex prevIndex() const { + assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) && + "Index out of bounds."); + return MachineInstrIndex(index - NUM); + } + + int distance(MachineInstrIndex other) const { + return (other.index & ~PHI_BIT) - (index & ~PHI_BIT); + } + + /// Returns an unsigned number suitable as an index into a + /// vector over all instructions. + unsigned getVecIndex() const { + return (index & ~PHI_BIT) / NUM; + } + + /// Scale this index by the given factor. + MachineInstrIndex scale(unsigned factor) const { + unsigned i = (index & ~PHI_BIT) / NUM, + o = (index % ~PHI_BIT) % NUM; + assert(index <= (~0U & ~PHI_BIT) / (factor * NUM) && + "Rescaled interval would overflow"); + return MachineInstrIndex(i * NUM * factor, o); + } + + static MachineInstrIndex emptyKey() { + return MachineInstrIndex(true, 0x7fffffff); + } + + static MachineInstrIndex tombstoneKey() { + return MachineInstrIndex(true, 0x7ffffffe); + } + + static unsigned getHashValue(const MachineInstrIndex &v) { + return v.index * 37; + } + + }; + + inline raw_ostream& operator<<(raw_ostream &os, MachineInstrIndex mi) { + mi.print(os); + return os; + } + + inline std::ostream& operator<<(std::ostream &os, MachineInstrIndex mi) { + mi.print(os); + return os; + } + + /// Densemap specialization for MachineInstrIndex. + template <> + struct DenseMapInfo<MachineInstrIndex> { + static inline MachineInstrIndex getEmptyKey() { + return MachineInstrIndex::emptyKey(); + } + static inline MachineInstrIndex getTombstoneKey() { + return MachineInstrIndex::tombstoneKey(); + } + static inline unsigned getHashValue(const MachineInstrIndex &v) { + return MachineInstrIndex::getHashValue(v); + } + static inline bool isEqual(const MachineInstrIndex &LHS, + const MachineInstrIndex &RHS) { + return (LHS == RHS); + } + static inline bool isPod() { return true; } + }; + /// VNInfo - Value Number Information. /// This class holds information about a machine level values, including @@ -65,36 +277,24 @@ namespace llvm { } cr; 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; + typedef SmallVector<MachineInstrIndex, 4> KillSet; /// The ID number of this value. unsigned id; /// The index of the defining instruction (if isDefAccurate() returns true). - unsigned def; + MachineInstrIndex def; KillSet kills; VNInfo() - : flags(IS_UNUSED), id(~1U), def(0) { cr.copy = 0; } + : flags(IS_UNUSED), id(~1U) { cr.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) + VNInfo(unsigned i, MachineInstrIndex d, MachineInstr *c) : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; } /// VNInfo construtor, copies values from orig, except for the value number. @@ -134,6 +334,7 @@ namespace llvm { /// Returns true if one or more kills are PHI nodes. 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; @@ -144,6 +345,7 @@ namespace llvm { /// 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; @@ -154,6 +356,7 @@ namespace llvm { /// 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; @@ -163,6 +366,7 @@ namespace llvm { /// 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; @@ -172,6 +376,7 @@ namespace llvm { /// Returns true if the def is accurate. bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; } + /// Set the "is def accurate" flag on this value. void setIsDefAccurate(bool defAccurate) { if (defAccurate) flags |= IS_DEF_ACCURATE; @@ -179,38 +384,74 @@ namespace llvm { flags &= ~IS_DEF_ACCURATE; } - }; + /// Returns true if the given index is a kill of this value. + bool isKill(MachineInstrIndex k) const { + KillSet::const_iterator + i = std::lower_bound(kills.begin(), kills.end(), k); + return (i != kills.end() && *i == k); + } - 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; - } + /// addKill - Add a kill instruction index to the specified value + /// number. + void addKill(MachineInstrIndex k) { + if (kills.empty()) { + kills.push_back(k); + } else { + KillSet::iterator + i = std::lower_bound(kills.begin(), kills.end(), k); + kills.insert(i, k); + } + } - inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) { - return idx < k.killIdx; - } + /// Remove the specified kill index from this value's kills list. + /// Returns true if the value was present, otherwise returns false. + bool removeKill(MachineInstrIndex k) { + KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k); + if (i != kills.end() && *i == k) { + kills.erase(i); + return true; + } + return false; + } + + /// Remove all kills in the range [s, e). + void removeKills(MachineInstrIndex s, MachineInstrIndex e) { + KillSet::iterator + si = std::lower_bound(kills.begin(), kills.end(), s), + se = std::upper_bound(kills.begin(), kills.end(), e); + + kills.erase(si, se); + } + + }; /// 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) + MachineInstrIndex start; // Start point of the interval (inclusive) + MachineInstrIndex 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(MachineInstrIndex S, MachineInstrIndex 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(MachineInstrIndex I) const { return start <= I && I < end; } + /// containsRange - Return true if the given range, [S, E), is covered by + /// this range. + bool containsRange(MachineInstrIndex S, MachineInstrIndex 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); } @@ -228,11 +469,11 @@ namespace llvm { raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); - inline bool operator<(unsigned V, const LiveRange &LR) { + inline bool operator<(MachineInstrIndex V, const LiveRange &LR) { return V < LR.start; } - inline bool operator<(const LiveRange &LR, unsigned V) { + inline bool operator<(const LiveRange &LR, MachineInstrIndex V) { return LR.start < V; } @@ -260,14 +501,6 @@ namespace llvm { 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; - } - }; LiveInterval(unsigned Reg, float Weight, bool IsSS = false) @@ -297,8 +530,8 @@ namespace llvm { /// 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()) + iterator advanceTo(iterator I, MachineInstrIndex Pos) { + if (Pos >= endIndex()) return end(); while (I->end <= Pos) ++I; return I; @@ -344,15 +577,12 @@ namespace llvm { /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. - VNInfo *getNextValue(unsigned MIIdx, MachineInstr *CopyMI, + VNInfo *getNextValue(MachineInstrIndex def, 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); + new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI); VNI->setIsDefAccurate(isDefAccurate); valnos.push_back(VNI); return VNI; @@ -372,50 +602,52 @@ namespace llvm { return VNI; } - /// addKill - Add a kill instruction index to the specified value - /// number. - 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(newKill); - } else { - 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 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); + if (!liveBeforeAndAt(kills[i])) { + VNI->addKill(kills[i]); } } } + /* REMOVE_ME + /// addKill - Add a kill instruction index to the specified value + /// number. + static void addKill(VNInfo *VNI, MachineInstrIndex killIdx) { + assert(killIdx.isUse() && "Kill must be a use."); + if (VNI->kills.empty()) { + VNI->kills.push_back(killIdx); + } else { + VNInfo::KillSet::iterator + I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), killIdx); + VNI->kills.insert(I, killIdx); + } + } + /// removeKill - Remove the specified kill from the list of kills of /// the specified val#. - static bool removeKill(VNInfo *VNI, unsigned KillIdx) { - VNInfo::KillSet &kills = VNI->kills; + static bool removeKill(VNInfo *VNI, MachineInstrIndex Kill) { + VNInfo::KillSet::iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - if (I != kills.end() && I->killIdx == KillIdx) { - kills.erase(I); + I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill); + if (I != VNI->kills.end() && (*I == Kill)) { + VNI->kills.erase(I); return true; } return false; + } + + /// removeKills - Remove all the kills in specified range /// [Start, End] of the specified val#. - static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) { + static void removeKills(VNInfo *VNI, MachineInstrIndex Start, + MachineInstrIndex End) { + VNInfo::KillSet &kills = VNI->kills; VNInfo::KillSet::iterator @@ -424,15 +656,16 @@ namespace llvm { 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; + static bool isKill(const VNInfo *VNI, MachineInstrIndex Kill) { VNInfo::KillSet::const_iterator - I = std::lower_bound(kills.begin(), kills.end(), KillIdx); - return I != kills.end() && I->killIdx == KillIdx; + I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill); + return I != VNI->kills.end() && (*I == Kill); } + */ /// isOnlyLROfValNo - Return true if the specified live range is the only /// one defined by the its val#. @@ -460,7 +693,8 @@ namespace llvm { /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a /// single LiveRange only. - void MergeInClobberRange(unsigned Start, unsigned End, + void MergeInClobberRange(MachineInstrIndex Start, + MachineInstrIndex End, BumpPtrAllocator &VNInfoAllocator); /// MergeValueInAsValue - Merge all of the live ranges of a specific val# @@ -485,58 +719,62 @@ namespace llvm { bool empty() const { return ranges.empty(); } - /// beginNumber - Return the lowest numbered slot covered by interval. - unsigned beginNumber() const { + /// beginIndex - Return the lowest numbered slot covered by interval. + MachineInstrIndex beginIndex() const { if (empty()) - return 0; + return MachineInstrIndex(); return ranges.front().start; } /// endNumber - return the maximum point of the interval of the whole, /// exclusive. - unsigned endNumber() const { + MachineInstrIndex endIndex() const { if (empty()) - return 0; + return MachineInstrIndex(); return ranges.back().end; } - bool expiredAt(unsigned index) const { - return index >= endNumber(); + bool expiredAt(MachineInstrIndex index) const { + return index >= endIndex(); } - bool liveAt(unsigned index) const; + bool liveAt(MachineInstrIndex 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; + bool liveBeforeAndAt(MachineInstrIndex index) 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(MachineInstrIndex Idx) const { const_iterator I = FindLiveRangeContaining(Idx); 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) { + LiveRange *getLiveRangeContaining(MachineInstrIndex 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; + const_iterator FindLiveRangeContaining(MachineInstrIndex Idx) const; /// 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(MachineInstrIndex Idx); + + /// findDefinedVNInfo - Find the by the specified + /// index (register interval) or defined + VNInfo *findDefinedVNInfoForRegInt(MachineInstrIndex Idx) const; + + /// findDefinedVNInfo - Find the VNInfo that's defined by the specified + /// register (stack inteval only). + VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) 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. @@ -546,7 +784,7 @@ namespace llvm { /// overlaps - Return true if the live interval overlaps a range specified /// by [Start, End). - bool overlaps(unsigned Start, unsigned End) const; + bool overlaps(MachineInstrIndex Start, MachineInstrIndex 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 @@ -570,11 +808,12 @@ namespace llvm { /// isInOneLiveRange - Return true if the range specified is entirely in the /// a single LiveRange of the live interval. - bool isInOneLiveRange(unsigned Start, unsigned End); + bool isInOneLiveRange(MachineInstrIndex Start, MachineInstrIndex End); /// removeRange - Remove the specified range from this interval. Note that /// the range must be a single LiveRange in its entirety. - void removeRange(unsigned Start, unsigned End, bool RemoveDeadValNo = false); + void removeRange(MachineInstrIndex Start, MachineInstrIndex End, + bool RemoveDeadValNo = false); void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { removeRange(LR.start, LR.end, RemoveDeadValNo); @@ -597,7 +836,7 @@ namespace llvm { void ComputeJoinedWeight(const LiveInterval &Other); bool operator<(const LiveInterval& other) const { - return beginNumber() < other.beginNumber(); + return beginIndex() < other.beginIndex(); } void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const; @@ -606,8 +845,8 @@ namespace llvm { 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, MachineInstrIndex NewEnd); + Ranges::iterator extendIntervalStartTo(Ranges::iterator I, MachineInstrIndex NewStr); LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT }; |