X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveInterval.h;h=3a9fef6fbd78176b9aac3a4d868590fad2e364a5;hb=d8324e6983d06c3d56debcbfdc9ead0e0d4a817d;hp=00dd422664024635a6f6ba494d50b29960eaaeee;hpb=8651125d2885f74546b6e2a556082111d5b75da3;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 00dd4226640..3a9fef6fbd7 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -9,555 +9,234 @@ // // 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 range 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. +// that v is live at i'. In this implementation ranges can have holes, +// i.e. a range might look like [1,20), [50,65), [1000,1001). Each +// individual segment is represented as an instance of LiveRange::Segment, +// and the whole range is represented as an instance of LiveRange. // //===----------------------------------------------------------------------===// #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/ADT/IntEqClasses.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Support/AlignOf.h" +#include "llvm/Support/Allocator.h" #include #include namespace llvm { + class CoalescerPair; + class LiveIntervals; class MachineInstr; 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; - - 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(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 { - 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; } - }; - + template class SmallPtrSet; /// VNInfo - Value Number Information. /// This class holds information about a machine level values, including /// definition and use points. /// - /// Care must be taken in interpreting the def index of the value. The - /// following rules apply: - /// - /// If the isDefAccurate() method returns false then def does not contain the - /// index of the defining MachineInstr, or even (necessarily) to a - /// MachineInstr at all. In general such a def index is not meaningful - /// and should not be used. The exception is that, for values originally - /// defined by PHI instructions, after PHI elimination def will contain the - /// index of the MBB in which the PHI originally existed. This can be used - /// to insert code (spills or copies) which deals with the value, which will - /// be live in to the block. class VNInfo { - private: - enum { - HAS_PHI_KILL = 1, - REDEF_BY_EC = 1 << 1, - IS_PHI_DEF = 1 << 2, - IS_UNUSED = 1 << 3, - IS_DEF_ACCURATE = 1 << 4 - }; - - unsigned char flags; - union { - MachineInstr *copy; - unsigned reg; - } cr; - public: - - typedef SmallVector KillSet; + typedef BumpPtrAllocator Allocator; /// The ID number of this value. unsigned id; - - /// The index of the defining instruction (if isDefAccurate() returns true). - MachineInstrIndex def; - KillSet kills; - - VNInfo() - : flags(IS_UNUSED), id(~1U) { cr.copy = 0; } + /// The index of the defining instruction. + SlotIndex def; /// 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, MachineInstrIndex d, MachineInstr *c) - : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; } + VNInfo(unsigned i, SlotIndex d) + : id(i), def(d) + { } /// VNInfo construtor, copies values from orig, except for the value number. VNInfo(unsigned i, const VNInfo &orig) - : flags(orig.flags), cr(orig.cr), id(i), def(orig.def), kills(orig.kills) + : id(i), def(orig.def) { } /// Copy from the parameter into this VNInfo. void copyFrom(VNInfo &src) { - flags = src.flags; - cr = src.cr; def = src.def; - kills = src.kills; - } - - /// Used for copying value number info. - unsigned getFlags() const { return flags; } - void setFlags(unsigned flags) { this->flags = flags; } - - /// 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 cr.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) { cr.copy = c; } - - /// For a stack interval, returns the reg which this stack interval was - /// defined from. - /// For a register interval the behaviour of this method is undefined. - unsigned getReg() const { return cr.reg; } - /// For a stack interval, set the defining register. - /// This method should not be called on register intervals as it may lead - /// to undefined behaviour. - void setReg(unsigned reg) { cr.reg = reg; } - - /// 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; - 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 defined by a PHI instruction (or was, + /// PHI instructions may have been eliminated). + /// PHI-defs begin at a block boundary, all other defs begin at register or + /// EC slots. + bool isPHIDef() const { return def.isBlock(); } + /// 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; - } + bool isUnused() const { return !def.isValid(); } - /// 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; - else - flags &= ~IS_DEF_ACCURATE; - } + /// Mark this value as unused. + void markUnused() { def = SlotIndex(); } + }; - /// 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); - } + /// Result of a LiveRange query. This class hides the implementation details + /// of live ranges, and it should be used as the primary interface for + /// examining live ranges around instructions. + class LiveQueryResult { + VNInfo *const EarlyVal; + VNInfo *const LateVal; + const SlotIndex EndPoint; + const bool Kill; - /// 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); - } - } + public: + LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, + bool Kill) + : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) + {} - /// 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; + /// Return the value that is live-in to the instruction. This is the value + /// that will be read by the instruction's use operands. Return NULL if no + /// value is live-in. + VNInfo *valueIn() const { + return EarlyVal; } - /// 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); + /// Return true if the live-in value is killed by this instruction. This + /// means that either the live range ends at the instruction, or it changes + /// value. + bool isKill() const { + return Kill; } - }; - - /// 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 { - 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(MachineInstrIndex S, MachineInstrIndex E, VNInfo *V) - : start(S), end(E), valno(V) { - - assert(S < E && "Cannot create empty or backwards range"); + /// Return true if this instruction has a dead def. + bool isDeadDef() const { + return EndPoint.isDead(); } - /// contains - Return true if the index is covered by this range. - /// - bool contains(MachineInstrIndex I) const { - return start <= I && I < end; + /// Return the value leaving the instruction, if any. This can be a + /// live-through value, or a live def. A dead def returns NULL. + VNInfo *valueOut() const { + return isDeadDef() ? 0 : LateVal; } - /// 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); + /// Return the value defined by this instruction, if any. This includes + /// dead defs, it is the value created by the instruction's def operands. + VNInfo *valueDefined() const { + return EarlyVal == LateVal ? 0 : LateVal; } - 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; + /// Return the end point of the last live range segment to interact with + /// the instruction, if any. + /// + /// The end point is an invalid SlotIndex only if the live range doesn't + /// intersect the instruction at all. + /// + /// The end point may be at or past the end of the instruction's basic + /// block. That means the value was live out of the block. + SlotIndex endPoint() const { + return EndPoint; } - - void dump() const; - void print(raw_ostream &os) const; - - private: - LiveRange(); // DO NOT IMPLEMENT }; - raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); + /// This class represents the liveness of a register, stack slot, etc. + /// It manages an ordered list of Segment objects. + /// The Segments are organized in a static single assignment form: At places + /// where a new value is defined or different values reach a CFG join a new + /// segment with a new value number is used. + class LiveRange { + public: + /// This represents a simple continuous liveness interval for a value. + /// The start point is inclusive, the end point exclusive. These intervals + /// are rendered as [start,end). + struct Segment { + 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 segment. - inline bool operator<(MachineInstrIndex V, const LiveRange &LR) { - return V < LR.start; - } + Segment() : valno(0) {} - inline bool operator<(const LiveRange &LR, MachineInstrIndex V) { - return LR.start < V; - } + Segment(SlotIndex S, SlotIndex E, VNInfo *V) + : start(S), end(E), valno(V) { + assert(S < E && "Cannot create empty or backwards segment"); + } - /// LiveInterval - This class represents some number of live ranges for a - /// register or value. This class also contains a bit of register allocator - /// state. - class LiveInterval { - public: + /// Return true if the index is covered by this segment. + bool contains(SlotIndex I) const { + return start <= I && I < end; + } - typedef SmallVector Ranges; - typedef SmallVector VNInfoList; + /// Return true if the given interval, [S, E), is covered by this segment. + bool containsInterval(SlotIndex S, SlotIndex E) const { + assert((S < E) && "Backwards interval?"); + return (start <= S && S < end) && (start < E && E <= end); + } - unsigned reg; // the register or stack slot of this interval - // if the top bits is set, it represents a stack slot. - float weight; // weight of this interval - Ranges ranges; // the ranges in which this register is live - VNInfoList valnos; // value#'s - - struct InstrSlots { - enum { - LOAD = 0, - USE = 1, - DEF = 2, - STORE = 3, - NUM = 4 - }; + bool operator<(const Segment &Other) const { + return start < Other.start || (start == Other.start && end < Other.end); + } + bool operator==(const Segment &Other) const { + return start == Other.start && end == Other.end; + } + void dump() const; }; - LiveInterval(unsigned Reg, float Weight, bool IsSS = false) - : reg(Reg), weight(Weight) { - if (IsSS) - reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1)); - } + typedef SmallVector Segments; + typedef SmallVector VNInfoList; - typedef Ranges::iterator iterator; - iterator begin() { return ranges.begin(); } - iterator end() { return ranges.end(); } + Segments segments; // the liveness segments + VNInfoList valnos; // value#'s + + typedef Segments::iterator iterator; + iterator begin() { return segments.begin(); } + iterator end() { return segments.end(); } - typedef Ranges::const_iterator const_iterator; - const_iterator begin() const { return ranges.begin(); } - const_iterator end() const { return ranges.end(); } + typedef Segments::const_iterator const_iterator; + const_iterator begin() const { return segments.begin(); } + const_iterator end() const { return segments.end(); } typedef VNInfoList::iterator vni_iterator; vni_iterator vni_begin() { return valnos.begin(); } - vni_iterator vni_end() { return valnos.end(); } + vni_iterator vni_end() { return valnos.end(); } typedef VNInfoList::const_iterator const_vni_iterator; const_vni_iterator vni_begin() const { return valnos.begin(); } - const_vni_iterator vni_end() const { return valnos.end(); } + const_vni_iterator vni_end() const { return valnos.end(); } - /// advanceTo - Advance the specified iterator to point to the LiveRange + /// advanceTo - Advance the specified iterator to point to the Segment /// 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, MachineInstrIndex Pos) { + /// end of the range. If no Segment contains this position, but the + /// position is in a hole, this method returns an iterator pointing to the + /// Segment immediately after the hole. + iterator advanceTo(iterator I, SlotIndex Pos) { + assert(I != end()); if (Pos >= endIndex()) return end(); while (I->end <= Pos) ++I; return I; } - - void clear() { - while (!valnos.empty()) { - VNInfo *VNI = valnos.back(); - valnos.pop_back(); - VNI->~VNInfo(); - } - - ranges.clear(); - } - /// isStackSlot - Return true if this is a stack slot interval. + /// find - Return an iterator pointing to the first segment that ends after + /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster + /// when searching large ranges. /// - bool isStackSlot() const { - return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1)); + /// If Pos is contained in a Segment, that segment is returned. + /// If Pos is in a hole, the following Segment 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); + } + + void clear() { + valnos.clear(); + segments.clear(); } - /// 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)*CHAR_BIT-1)); + size_t size() const { + return segments.size(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -565,7 +244,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) { @@ -575,279 +254,313 @@ namespace llvm { return valnos[ValNo]; } + /// containsValue - Returns true if VNI belongs to this range. + 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(MachineInstrIndex def, MachineInstr *CopyMI, - bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){ + VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { VNInfo *VNI = - static_cast(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo), - alignof())); - new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI); - VNI->setIsDefAccurate(isDefAccurate); + new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); valnos.push_back(VNI); return VNI; } + /// createDeadDef - Make sure the range has a value defined at Def. + /// If one already exists, return it. Otherwise allocate a new value and + /// add liveness for a dead def. + VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); + /// Create a copy of the given value. The new value will be identical except /// for the Value number. VNInfo *createValueCopy(const VNInfo *orig, - BumpPtrAllocator &VNInfoAllocator) { - + VNInfo::Allocator &VNInfoAllocator) { VNInfo *VNI = - static_cast(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo), - alignof())); - - new (VNI) VNInfo((unsigned)valnos.size(), *orig); + new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); valnos.push_back(VNI); return VNI; } - /// 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(kills.size()); - i != e; ++i) { - 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, MachineInstrIndex Kill) { - - VNInfo::KillSet::iterator - 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, MachineInstrIndex Start, - MachineInstrIndex End) { - - VNInfo::KillSet &kills = VNI->kills; + /// RenumberValues - Renumber all values in order of appearance and remove + /// unused values. + void RenumberValues(); - VNInfo::KillSet::iterator - I = std::lower_bound(kills.begin(), kills.end(), Start); - VNInfo::KillSet::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#. - static bool isKill(const VNInfo *VNI, MachineInstrIndex Kill) { - VNInfo::KillSet::const_iterator - 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#. - 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 true; - } - - /// MergeValueNumberInto - This method is called when two value nubmers + /// MergeValueNumberInto - This method is called when two value numbers /// are found to be equivalent. This eliminates V1, replacing all - /// LiveRanges with the V1 value number with the V2 value number. This can + /// segments 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. VNInfo* 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); - - /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a - /// single LiveRange only. - void MergeInClobberRange(MachineInstrIndex Start, - MachineInstrIndex End, - BumpPtrAllocator &VNInfoAllocator); - - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, it will replace the value numbers of the overlaped - /// live ranges with the specified value number. - void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); - - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, but only if the overlapping LiveRanges have the + /// Merge all of the live segments of a specific val# in RHS into this live + /// range as the specified value number. The segments in RHS are allowed + /// to overlap with segments in the current range, it will replace the + /// value numbers of the overlaped live segments with the specified value + /// number. + void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); + + /// MergeValueInAsValue - Merge all of the segments of a specific val# + /// in RHS into this live range as the specified value number. + /// The segments in RHS are allowed to overlap with segments in the + /// current range, but only if the overlapping segments have the /// specified value number. - void MergeValueInAsValue(const LiveInterval &RHS, + void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo); - /// Copy - Copy the specified live interval. This copies all the fields - /// except for the register of the interval. - void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, - BumpPtrAllocator &VNInfoAllocator); - - bool empty() const { return ranges.empty(); } + bool empty() const { return segments.empty(); } - /// beginIndex - Return the lowest numbered slot covered by interval. - MachineInstrIndex beginIndex() const { - if (empty()) - return MachineInstrIndex(); - return ranges.front().start; + /// beginIndex - Return the lowest numbered slot covered. + SlotIndex beginIndex() const { + assert(!empty() && "Call to beginIndex() on empty range."); + return segments.front().start; } - /// endNumber - return the maximum point of the interval of the whole, + /// endNumber - return the maximum point of the range of the whole, /// exclusive. - MachineInstrIndex endIndex() const { - if (empty()) - return MachineInstrIndex(); - return ranges.back().end; + SlotIndex endIndex() const { + assert(!empty() && "Call to endIndex() on empty range."); + return segments.back().end; } - bool expiredAt(MachineInstrIndex index) const { + bool expiredAt(SlotIndex index) const { return index >= endIndex(); } - 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(MachineInstrIndex index) const; + bool liveAt(SlotIndex index) const { + const_iterator r = find(index); + return r != end() && r->start <= index; + } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - const LiveRange *getLiveRangeContaining(MachineInstrIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); + /// Return the segment that contains the specified index, or null if there + /// is none. + const Segment *getSegmentContaining(SlotIndex Idx) const { + const_iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : &*I; } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - LiveRange *getLiveRangeContaining(MachineInstrIndex Idx) { - iterator I = FindLiveRangeContaining(Idx); + /// Return the live segment that contains the specified index, or null if + /// there is none. + Segment *getSegmentContaining(SlotIndex Idx) { + iterator I = FindSegmentContaining(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(MachineInstrIndex Idx) const; + /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. + VNInfo *getVNInfoAt(SlotIndex Idx) const { + const_iterator I = FindSegmentContaining(Idx); + 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(MachineInstrIndex Idx); + /// 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 = FindSegmentContaining(Idx.getPrevSlot()); + return I == end() ? 0 : I->valno; + } - /// findDefinedVNInfo - Find the by the specified - /// index (register interval) or defined - VNInfo *findDefinedVNInfoForRegInt(MachineInstrIndex Idx) const; + /// Return an iterator to the segment that contains the specified index, or + /// end() if there is none. + iterator FindSegmentContaining(SlotIndex Idx) { + iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } - /// findDefinedVNInfo - Find the VNInfo that's defined by the specified - /// register (stack inteval only). - VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const; + const_iterator FindSegmentContaining(SlotIndex Idx) const { + const_iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } - - /// overlaps - Return true if the intersection of the two live intervals is + /// overlaps - Return true if the intersection of the two live ranges is /// not empty. - bool overlaps(const LiveInterval& other) const { + bool overlaps(const LiveRange &other) const { + if (other.empty()) + return false; return overlapsFrom(other, other.begin()); } - /// overlaps - Return true if the live interval overlaps a range specified + /// overlaps - Return true if the two ranges have overlapping segments + /// that are not coalescable according to CP. + /// + /// Overlapping segments where one range is defined by a coalescable + /// copy are allowed. + bool overlaps(const LiveRange &Other, const CoalescerPair &CP, + const SlotIndexes&) const; + + /// overlaps - Return true if the live range overlaps an interval specified /// by [Start, End). - bool overlaps(MachineInstrIndex Start, MachineInstrIndex End) const; + bool overlaps(SlotIndex Start, SlotIndex End) const; - /// overlapsFrom - Return true if the intersection of the two live intervals + /// overlapsFrom - Return true if the intersection of the two live ranges /// 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; + /// scanning the Other range starting at I. + bool overlapsFrom(const LiveRange &Other, const_iterator I) const; + + /// Add the specified Segment to this range, merging segments as + /// appropriate. This returns an iterator to the inserted segment (which + /// may have grown since it was inserted). + iterator addSegment(Segment S) { + return addSegmentFrom(S, segments.begin()); + } + + /// extendInBlock - If this range 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 segment before Kill, return NULL. + VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); + + /// join - Join two live ranges (this, and other) together. This applies + /// mappings to the value numbers in the LHS/RHS ranges as specified. If + /// the ranges are not joinable, this aborts. + void join(LiveRange &Other, + const int *ValNoAssignments, + const int *RHSValNoAssignments, + SmallVectorImpl &NewVNInfo); + + /// True iff this segment is a single segment that lies between the + /// specified boundaries, exclusively. Vregs live across a backedge are not + /// considered local. The boundaries are expected to lie within an extended + /// basic block, so vregs that are not live out should contain no holes. + bool isLocal(SlotIndex Start, SlotIndex End) const { + return beginIndex() > Start.getBaseIndex() && + endIndex() < End.getBoundaryIndex(); + } + + /// Remove the specified segment from this range. Note that the segment + /// must be a single Segment in its entirety. + void removeSegment(SlotIndex Start, SlotIndex End, + bool RemoveDeadValNo = false); + + void removeSegment(Segment S, bool RemoveDeadValNo = false) { + removeSegment(S.start, S.end, RemoveDeadValNo); + } + + /// Query Liveness at Idx. + /// The sub-instruction slot of Idx doesn't matter, only the instruction + /// it refers to is considered. + LiveQueryResult Query(SlotIndex Idx) const { + // Find the segment that enters the instruction. + const_iterator I = find(Idx.getBaseIndex()); + const_iterator E = end(); + if (I == E) + return LiveQueryResult(0, 0, SlotIndex(), false); + + // Is this an instruction live-in segment? + // If Idx is the start index of a basic block, include live-in segments + // that start at Idx.getBaseIndex(). + VNInfo *EarlyVal = 0; + VNInfo *LateVal = 0; + SlotIndex EndPoint; + bool Kill = false; + if (I->start <= Idx.getBaseIndex()) { + EarlyVal = I->valno; + EndPoint = I->end; + // Move to the potentially live-out segment. + if (SlotIndex::isSameInstr(Idx, I->end)) { + Kill = true; + if (++I == E) + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + // Special case: A PHIDef value can have its def in the middle of a + // segment if the value happens to be live out of the layout + // predecessor. + // Such a value is not live-in. + if (EarlyVal->def == Idx.getBaseIndex()) + EarlyVal = 0; + } + // I now points to the segment that may be live-through, or defined by + // this instr. Ignore segments starting after the current instr. + if (!SlotIndex::isEarlierInstr(Idx, I->start)) { + LateVal = I->valno; + EndPoint = I->end; + } + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } - /// 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()); + /// removeValNo - Remove all the segments defined by the specified value#. + /// Also remove the value# from value# list. + void removeValNo(VNInfo *ValNo); + + /// Returns true if the live range is zero length, i.e. no live segments + /// span instructions. It doesn't pay to spill such a range. + 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; } - /// 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, - const int *RHSValNoAssignments, - SmallVector &NewVNInfo, - MachineRegisterInfo *MRI); + bool operator<(const LiveRange& other) const { + const SlotIndex &thisIndex = beginIndex(); + const SlotIndex &otherIndex = other.beginIndex(); + return thisIndex < otherIndex; + } - /// isInOneLiveRange - Return true if the range specified is entirely in the - /// a single LiveRange of the live interval. - bool isInOneLiveRange(MachineInstrIndex Start, MachineInstrIndex End); + void print(raw_ostream &OS) const; + void dump() const; - /// removeRange - Remove the specified range from this interval. Note that - /// the range must be a single LiveRange in its entirety. - void removeRange(MachineInstrIndex Start, MachineInstrIndex End, - bool RemoveDeadValNo = false); + /// \brief Walk the range and assert if any invariants fail to hold. + /// + /// Note that this is a no-op when asserts are disabled. +#ifdef NDEBUG + void verify() const {} +#else + void verify() const; +#endif - void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { - removeRange(LR.start, LR.end, RemoveDeadValNo); - } + private: - /// removeValNo - Remove all the ranges defined by the specified value#. - /// Also remove the value# from value# list. - void removeValNo(VNInfo *ValNo); + iterator addSegmentFrom(Segment S, iterator From); + void extendSegmentEndTo(iterator I, SlotIndex NewEnd); + iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); + void markValNoForDeletion(VNInfo *V); + + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { + LR.print(OS); + return OS; + } + + /// LiveInterval - This class represents the liveness of a register, + /// or stack slot. + class LiveInterval : public LiveRange { + public: + typedef LiveRange super; + + const unsigned reg; // the register or stack slot of this interval. + float weight; // weight of this interval - /// scaleNumbering - Renumber VNI and ranges to provide gaps for new - /// instructions. - void scaleNumbering(unsigned factor); + LiveInterval(unsigned Reg, float Weight) + : reg(Reg), weight(Weight) {} /// getSize - Returns the sum of sizes of all the LiveRange's. /// unsigned getSize() const; - /// ComputeJoinedWeight - Set the weight of a live interval after - /// Other has been merged into it. - void ComputeJoinedWeight(const LiveInterval &Other); + /// isSpillable - Can this interval be spilled? + bool isSpillable() const { + return weight != llvm::huge_valf; + } + + /// markNotSpillable - Mark interval as not spillable + void markNotSpillable() { + weight = llvm::huge_valf; + } bool operator<(const LiveInterval& other) const { - return beginIndex() < other.beginIndex(); + 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 print(raw_ostream &OS) const; void dump() const; private: - - Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); - void extendIntervalEndTo(Ranges::iterator I, MachineInstrIndex NewEnd); - Ranges::iterator extendIntervalStartTo(Ranges::iterator I, MachineInstrIndex NewStr); - LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT + LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; }; @@ -855,6 +568,116 @@ namespace llvm { LI.print(OS); return OS; } -} + raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); + + inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { + return V < S.start; + } + + inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { + return S.start < V; + } + + /// Helper class for performant LiveRange bulk updates. + /// + /// Calling LiveRange::addSegment() repeatedly can be expensive on large + /// live ranges because segments after the insertion point may need to be + /// shifted. The LiveRangeUpdater class can defer the shifting when adding + /// many segments in order. + /// + /// The LiveRange will be in an invalid state until flush() is called. + class LiveRangeUpdater { + LiveRange *LR; + SlotIndex LastStart; + LiveRange::iterator WriteI; + LiveRange::iterator ReadI; + SmallVector Spills; + void mergeSpills(); + + public: + /// Create a LiveRangeUpdater for adding segments to LR. + /// LR will temporarily be in an invalid state until flush() is called. + LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {} + + ~LiveRangeUpdater() { flush(); } + + /// Add a segment to LR and coalesce when possible, just like + /// LR.addSegment(). Segments should be added in increasing start order for + /// best performance. + void add(LiveRange::Segment); + + void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { + add(LiveRange::Segment(Start, End, VNI)); + } + + /// Return true if the LR is currently in an invalid state, and flush() + /// needs to be called. + bool isDirty() const { return LastStart.isValid(); } + + /// Flush the updater state to LR so it is valid and contains all added + /// segments. + void flush(); + + /// Select a different destination live range. + void setDest(LiveRange *lr) { + if (LR != lr && isDirty()) + flush(); + LR = lr; + } + + /// Get the current destination live range. + LiveRange *getDest() const { return LR; } + + void dump() const; + void print(raw_ostream&) const; + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { + X.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