#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include <cassert>
#include <climits>
+#include <set>
namespace llvm {
class CoalescerPair;
return isDeadDef() ? nullptr : LateVal;
}
+ /// Returns the value alive at the end of the instruction, if any. This can
+ /// be a live-through value, a live def or a dead def.
+ VNInfo *valueOutOrDead() const {
+ return LateVal;
+ }
+
/// 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 {
Segments segments; // the liveness segments
VNInfoList valnos; // value#'s
+ // The segment set is used temporarily to accelerate initial computation
+ // of live ranges of physical registers in computeRegUnitRange.
+ // After that the set is flushed to the segment vector and deleted.
+ typedef std::set<Segment> SegmentSet;
+ std::unique_ptr<SegmentSet> segmentSet;
+
typedef Segments::iterator iterator;
iterator begin() { return segments.begin(); }
iterator end() { return segments.end(); }
const_vni_iterator vni_begin() const { return valnos.begin(); }
const_vni_iterator vni_end() const { return valnos.end(); }
+ /// Constructs a new LiveRange object.
+ LiveRange(bool UseSegmentSet = false)
+ : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>()
+ : nullptr) {}
+
+ /// Constructs a new LiveRange object by copying segments and valnos from
+ /// another LiveRange.
+ LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) {
+ assert(Other.segmentSet == nullptr &&
+ "Copying of LiveRanges with active SegmentSets is not supported");
+
+ // Duplicate valnos.
+ for (const VNInfo *VNI : Other.valnos) {
+ createValueCopy(VNI, Allocator);
+ }
+ // Now we can copy segments and remap their valnos.
+ for (const Segment &S : Other.segments) {
+ segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
+ }
+ }
+
/// 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 range. If no Segment contains this position, but the
/// 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());
- }
+ iterator addSegment(Segment S);
- /// 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);
+ /// If this range is live before @p Use in the basic block that starts at
+ /// @p StartIdx, extend it to be live up to @p Use, and return the value. If
+ /// there is no segment before @p Use, return nullptr.
+ VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use);
/// join - Join two live ranges (this, and other) together. This applies
/// mappings to the value numbers in the LHS/RHS ranges as specified. If
removeSegment(S.start, S.end, RemoveDeadValNo);
}
+ /// Remove segment pointed to by iterator @p I from this range. This does
+ /// not remove dead value numbers.
+ iterator removeSegment(iterator I) {
+ return segments.erase(I);
+ }
+
/// Query Liveness at Idx.
/// The sub-instruction slot of Idx doesn't matter, only the instruction
/// it refers to is considered.
/// 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())
+ for (const Segment &S : segments)
+ if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
+ S.end.getBaseIndex())
return false;
return true;
}
+ // Returns true if any segment in the live range contains any of the
+ // provided slot indexes. Slots which occur in holes between
+ // segments will not cause the function to return true.
+ bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
+
bool operator<(const LiveRange& other) const {
const SlotIndex &thisIndex = beginIndex();
const SlotIndex &otherIndex = other.beginIndex();
return thisIndex < otherIndex;
}
+ /// Flush segment set into the regular segment vector.
+ /// The method is to be called after the live range
+ /// has been created, if use of the segment set was
+ /// activated in the constructor of the live range.
+ void flushSegmentSet();
+
void print(raw_ostream &OS) const;
void dump() const;
void verify() const;
#endif
- private:
+ protected:
+ /// Append a segment to the list of segments.
+ void append(const LiveRange::Segment S);
- iterator addSegmentFrom(Segment S, iterator From);
- void extendSegmentEndTo(iterator I, SlotIndex NewEnd);
- iterator extendSegmentStartTo(iterator I, SlotIndex NewStr);
+ private:
+ friend class LiveRangeUpdater;
+ void addSegmentToSet(Segment S);
void markValNoForDeletion(VNInfo *V);
};
public:
typedef LiveRange super;
+ /// A live range for subregisters. The LaneMask specifies which parts of the
+ /// super register are covered by the interval.
+ /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
+ class SubRange : public LiveRange {
+ public:
+ SubRange *Next;
+ LaneBitmask LaneMask;
+
+ /// Constructs a new SubRange object.
+ SubRange(LaneBitmask LaneMask)
+ : Next(nullptr), LaneMask(LaneMask) {
+ }
+
+ /// Constructs a new SubRange object by copying liveness from @p Other.
+ SubRange(LaneBitmask LaneMask, const LiveRange &Other,
+ BumpPtrAllocator &Allocator)
+ : LiveRange(Other, Allocator), Next(nullptr), LaneMask(LaneMask) {
+ }
+ };
+
+ private:
+ SubRange *SubRanges; ///< Single linked list of subregister live ranges.
+
+ public:
const unsigned reg; // the register or stack slot of this interval.
float weight; // weight of this interval
LiveInterval(unsigned Reg, float Weight)
- : reg(Reg), weight(Weight) {}
+ : SubRanges(nullptr), reg(Reg), weight(Weight) {}
+
+ ~LiveInterval() {
+ clearSubRanges();
+ }
+
+ template<typename T>
+ class SingleLinkedListIterator {
+ T *P;
+ public:
+ SingleLinkedListIterator<T>(T *P) : P(P) {}
+ SingleLinkedListIterator<T> &operator++() {
+ P = P->Next;
+ return *this;
+ }
+ SingleLinkedListIterator<T> &operator++(int) {
+ SingleLinkedListIterator res = *this;
+ ++*this;
+ return res;
+ }
+ bool operator!=(const SingleLinkedListIterator<T> &Other) {
+ return P != Other.operator->();
+ }
+ bool operator==(const SingleLinkedListIterator<T> &Other) {
+ return P == Other.operator->();
+ }
+ T &operator*() const {
+ return *P;
+ }
+ T *operator->() const {
+ return P;
+ }
+ };
+
+ typedef SingleLinkedListIterator<SubRange> subrange_iterator;
+ subrange_iterator subrange_begin() {
+ return subrange_iterator(SubRanges);
+ }
+ subrange_iterator subrange_end() {
+ return subrange_iterator(nullptr);
+ }
+
+ typedef SingleLinkedListIterator<const SubRange> const_subrange_iterator;
+ const_subrange_iterator subrange_begin() const {
+ return const_subrange_iterator(SubRanges);
+ }
+ const_subrange_iterator subrange_end() const {
+ return const_subrange_iterator(nullptr);
+ }
+
+ iterator_range<subrange_iterator> subranges() {
+ return make_range(subrange_begin(), subrange_end());
+ }
+
+ iterator_range<const_subrange_iterator> subranges() const {
+ return make_range(subrange_begin(), subrange_end());
+ }
+
+ /// Creates a new empty subregister live range. The range is added at the
+ /// beginning of the subrange list; subrange iterators stay valid.
+ SubRange *createSubRange(BumpPtrAllocator &Allocator,
+ LaneBitmask LaneMask) {
+ SubRange *Range = new (Allocator) SubRange(LaneMask);
+ appendSubRange(Range);
+ return Range;
+ }
+
+ /// Like createSubRange() but the new range is filled with a copy of the
+ /// liveness information in @p CopyFrom.
+ SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator,
+ LaneBitmask LaneMask,
+ const LiveRange &CopyFrom) {
+ SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
+ appendSubRange(Range);
+ return Range;
+ }
+
+ /// Returns true if subregister liveness information is available.
+ bool hasSubRanges() const {
+ return SubRanges != nullptr;
+ }
+
+ /// Removes all subregister liveness information.
+ void clearSubRanges();
+
+ /// Removes all subranges without any segments (subranges without segments
+ /// are not considered valid and should only exist temporarily).
+ void removeEmptySubRanges();
+
+ /// Construct main live range by merging the SubRanges of @p LI.
+ void constructMainRangeFromSubranges(const SlotIndexes &Indexes,
+ VNInfo::Allocator &VNIAllocator);
/// getSize - Returns the sum of sizes of all the LiveRange's.
///
void print(raw_ostream &OS) const;
void dump() const;
+ /// \brief Walks the interval and assert if any invariants fail to hold.
+ ///
+ /// Note that this is a no-op when asserts are disabled.
+#ifdef NDEBUG
+ void verify(const MachineRegisterInfo *MRI = nullptr) const {}
+#else
+ void verify(const MachineRegisterInfo *MRI = nullptr) const;
+#endif
+
private:
- LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION;
+ /// Appends @p Range to SubRanges list.
+ void appendSubRange(SubRange *Range) {
+ Range->Next = SubRanges;
+ SubRanges = Range;
+ }
+ /// Free memory held by SubRange.
+ void freeSubRange(SubRange *S);
};
inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
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);
+ /// Classify the values in \p LR into connected components.
+ /// Returns the number of connected components.
+ unsigned Classify(const LiveRange &LR);
/// 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);
-
+ /// Distribute values in \p LI into a separate LiveIntervals
+ /// for each connected component. LIV must have an empty LiveInterval for
+ /// each additional connected component. The first connected component is
+ /// left in \p LI.
+ void Distribute(LiveInterval &LI, LiveInterval *LIV[],
+ MachineRegisterInfo &MRI);
};
}
projects / oota-llvm.git / blobdiff