#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include <algorithm>
using namespace llvm;
+namespace {
+//===----------------------------------------------------------------------===//
+// Implementation of various methods necessary for calculation of live ranges.
+// The implementation of the methods abstracts from the concrete type of the
+// segment collection.
+//
+// Implementation of the class follows the Template design pattern. The base
+// class contains generic algorithms that call collection-specific methods,
+// which are provided in concrete subclasses. In order to avoid virtual calls
+// these methods are provided by means of C++ template instantiation.
+// The base class calls the methods of the subclass through method impl(),
+// which casts 'this' pointer to the type of the subclass.
+//
+//===----------------------------------------------------------------------===//
+
+template <typename ImplT, typename IteratorT, typename CollectionT>
+class CalcLiveRangeUtilBase {
+protected:
+ LiveRange *LR;
+
+protected:
+ CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
+
+public:
+ typedef LiveRange::Segment Segment;
+ typedef IteratorT iterator;
+
+ VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) {
+ assert(!Def.isDead() && "Cannot define a value at the dead slot");
+
+ iterator I = impl().find(Def);
+ if (I == segments().end()) {
+ VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+ impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
+ return VNI;
+ }
+
+ Segment *S = segmentAt(I);
+ if (SlotIndex::isSameInstr(Def, S->start)) {
+ assert(S->valno->def == S->start && "Inconsistent existing value def");
+
+ // It is possible to have both normal and early-clobber defs of the same
+ // register on an instruction. It doesn't make a lot of sense, but it is
+ // possible to specify in inline assembly.
+ //
+ // Just convert everything to early-clobber.
+ Def = std::min(Def, S->start);
+ if (Def != S->start)
+ S->start = S->valno->def = Def;
+ return S->valno;
+ }
+ assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
+ VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+ segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
+ return VNI;
+ }
+
+ VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
+ if (segments().empty())
+ return nullptr;
+ iterator I =
+ impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
+ if (I == segments().begin())
+ return nullptr;
+ --I;
+ if (I->end <= StartIdx)
+ return nullptr;
+ if (I->end < Use)
+ extendSegmentEndTo(I, Use);
+ return I->valno;
+ }
+
+ /// This method is used when we want to extend the segment specified
+ /// by I to end at the specified endpoint. To do this, we should
+ /// merge and eliminate all segments that this will overlap
+ /// with. The iterator is not invalidated.
+ void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
+ assert(I != segments().end() && "Not a valid segment!");
+ Segment *S = segmentAt(I);
+ VNInfo *ValNo = I->valno;
+
+ // Search for the first segment that we can't merge with.
+ iterator MergeTo = std::next(I);
+ for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo)
+ assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
+
+ // If NewEnd was in the middle of a segment, make sure to get its endpoint.
+ S->end = std::max(NewEnd, std::prev(MergeTo)->end);
+
+ // If the newly formed segment now touches the segment after it and if they
+ // have the same value number, merge the two segments into one segment.
+ if (MergeTo != segments().end() && MergeTo->start <= I->end &&
+ MergeTo->valno == ValNo) {
+ S->end = MergeTo->end;
+ ++MergeTo;
+ }
+
+ // Erase any dead segments.
+ segments().erase(std::next(I), MergeTo);
+ }
+
+ /// This method is used when we want to extend the segment specified
+ /// by I to start at the specified endpoint. To do this, we should
+ /// merge and eliminate all segments that this will overlap with.
+ iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
+ assert(I != segments().end() && "Not a valid segment!");
+ Segment *S = segmentAt(I);
+ VNInfo *ValNo = I->valno;
+
+ // Search for the first segment that we can't merge with.
+ iterator MergeTo = I;
+ do {
+ if (MergeTo == segments().begin()) {
+ S->start = NewStart;
+ segments().erase(MergeTo, I);
+ return I;
+ }
+ assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
+ --MergeTo;
+ } while (NewStart <= MergeTo->start);
+
+ // If we start in the middle of another segment, just delete a range and
+ // extend that segment.
+ if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
+ segmentAt(MergeTo)->end = S->end;
+ } else {
+ // Otherwise, extend the segment right after.
+ ++MergeTo;
+ Segment *MergeToSeg = segmentAt(MergeTo);
+ MergeToSeg->start = NewStart;
+ MergeToSeg->end = S->end;
+ }
+
+ segments().erase(std::next(MergeTo), std::next(I));
+ return MergeTo;
+ }
+
+ iterator addSegment(Segment S) {
+ SlotIndex Start = S.start, End = S.end;
+ iterator I = impl().findInsertPos(S);
+
+ // If the inserted segment starts in the middle or right at the end of
+ // another segment, just extend that segment to contain the segment of S.
+ if (I != segments().begin()) {
+ iterator B = std::prev(I);
+ if (S.valno == B->valno) {
+ if (B->start <= Start && B->end >= Start) {
+ extendSegmentEndTo(B, End);
+ return B;
+ }
+ } else {
+ // Check to make sure that we are not overlapping two live segments with
+ // different valno's.
+ assert(B->end <= Start &&
+ "Cannot overlap two segments with differing ValID's"
+ " (did you def the same reg twice in a MachineInstr?)");
+ }
+ }
+
+ // Otherwise, if this segment ends in the middle of, or right next
+ // to, another segment, merge it into that segment.
+ if (I != segments().end()) {
+ if (S.valno == I->valno) {
+ if (I->start <= End) {
+ I = extendSegmentStartTo(I, Start);
+
+ // If S is a complete superset of a segment, we may need to grow its
+ // endpoint as well.
+ if (End > I->end)
+ extendSegmentEndTo(I, End);
+ return I;
+ }
+ } else {
+ // Check to make sure that we are not overlapping two live segments with
+ // different valno's.
+ assert(I->start >= End &&
+ "Cannot overlap two segments with differing ValID's");
+ }
+ }
+
+ // Otherwise, this is just a new segment that doesn't interact with
+ // anything.
+ // Insert it.
+ return segments().insert(I, S);
+ }
+
+private:
+ ImplT &impl() { return *static_cast<ImplT *>(this); }
+
+ CollectionT &segments() { return impl().segmentsColl(); }
+
+ Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
+};
+
+//===----------------------------------------------------------------------===//
+// Instantiation of the methods for calculation of live ranges
+// based on a segment vector.
+//===----------------------------------------------------------------------===//
+
+class CalcLiveRangeUtilVector;
+typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator,
+ LiveRange::Segments> CalcLiveRangeUtilVectorBase;
+
+class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {
+public:
+ CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {}
+
+private:
+ friend CalcLiveRangeUtilVectorBase;
+
+ LiveRange::Segments &segmentsColl() { return LR->segments; }
+
+ void insertAtEnd(const Segment &S) { LR->segments.push_back(S); }
+
+ iterator find(SlotIndex Pos) { return LR->find(Pos); }
+
+ iterator findInsertPos(Segment S) {
+ return std::upper_bound(LR->begin(), LR->end(), S.start);
+ }
+};
+
+//===----------------------------------------------------------------------===//
+// Instantiation of the methods for calculation of live ranges
+// based on a segment set.
+//===----------------------------------------------------------------------===//
+
+class CalcLiveRangeUtilSet;
+typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilSet,
+ LiveRange::SegmentSet::iterator,
+ LiveRange::SegmentSet> CalcLiveRangeUtilSetBase;
+
+class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {
+public:
+ CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {}
+
+private:
+ friend CalcLiveRangeUtilSetBase;
+
+ LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; }
+
+ void insertAtEnd(const Segment &S) {
+ LR->segmentSet->insert(LR->segmentSet->end(), S);
+ }
+
+ iterator find(SlotIndex Pos) {
+ iterator I =
+ LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr));
+ if (I == LR->segmentSet->begin())
+ return I;
+ iterator PrevI = std::prev(I);
+ if (Pos < (*PrevI).end)
+ return PrevI;
+ return I;
+ }
+
+ iterator findInsertPos(Segment S) {
+ iterator I = LR->segmentSet->upper_bound(S);
+ if (I != LR->segmentSet->end() && !(S.start < *I))
+ ++I;
+ return I;
+ }
+};
+} // namespace
+
+//===----------------------------------------------------------------------===//
+// LiveRange methods
+//===----------------------------------------------------------------------===//
+
LiveRange::iterator LiveRange::find(SlotIndex Pos) {
// This algorithm is basically std::upper_bound.
// Unfortunately, std::upper_bound cannot be used with mixed types until we
VNInfo *LiveRange::createDeadDef(SlotIndex Def,
VNInfo::Allocator &VNInfoAllocator) {
- assert(!Def.isDead() && "Cannot define a value at the dead slot");
- iterator I = find(Def);
- if (I == end()) {
- VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
- segments.push_back(Segment(Def, Def.getDeadSlot(), VNI));
- return VNI;
- }
- if (SlotIndex::isSameInstr(Def, I->start)) {
- assert(I->valno->def == I->start && "Inconsistent existing value def");
-
- // It is possible to have both normal and early-clobber defs of the same
- // register on an instruction. It doesn't make a lot of sense, but it is
- // possible to specify in inline assembly.
- //
- // Just convert everything to early-clobber.
- Def = std::min(Def, I->start);
- if (Def != I->start)
- I->start = I->valno->def = Def;
- return I->valno;
- }
- assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
- VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
- segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI));
- return VNI;
+ // Use the segment set, if it is available.
+ if (segmentSet != nullptr)
+ return CalcLiveRangeUtilSet(this).createDeadDef(Def, VNInfoAllocator);
+ // Otherwise use the segment vector.
+ return CalcLiveRangeUtilVector(this).createDeadDef(Def, VNInfoAllocator);
}
// overlaps - Return true if the intersection of the two live ranges is
}
}
-/// This method is used when we want to extend the segment specified by I to end
-/// at the specified endpoint. To do this, we should merge and eliminate all
-/// segments that this will overlap with. The iterator is not invalidated.
-void LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
- assert(I != end() && "Not a valid segment!");
- VNInfo *ValNo = I->valno;
-
- // Search for the first segment that we can't merge with.
- iterator MergeTo = std::next(I);
- for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) {
- assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
- }
-
- // If NewEnd was in the middle of a segment, make sure to get its endpoint.
- I->end = std::max(NewEnd, std::prev(MergeTo)->end);
-
- // If the newly formed segment now touches the segment after it and if they
- // have the same value number, merge the two segments into one segment.
- if (MergeTo != end() && MergeTo->start <= I->end &&
- MergeTo->valno == ValNo) {
- I->end = MergeTo->end;
- ++MergeTo;
- }
-
- // Erase any dead segments.
- segments.erase(std::next(I), MergeTo);
+void LiveRange::addSegmentToSet(Segment S) {
+ CalcLiveRangeUtilSet(this).addSegment(S);
}
-
-/// This method is used when we want to extend the segment specified by I to
-/// start at the specified endpoint. To do this, we should merge and eliminate
-/// all segments that this will overlap with.
-LiveRange::iterator
-LiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) {
- assert(I != end() && "Not a valid segment!");
- VNInfo *ValNo = I->valno;
-
- // Search for the first segment that we can't merge with.
- iterator MergeTo = I;
- do {
- if (MergeTo == begin()) {
- I->start = NewStart;
- segments.erase(MergeTo, I);
- return I;
- }
- assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
- --MergeTo;
- } while (NewStart <= MergeTo->start);
-
- // If we start in the middle of another segment, just delete a range and
- // extend that segment.
- if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
- MergeTo->end = I->end;
- } else {
- // Otherwise, extend the segment right after.
- ++MergeTo;
- MergeTo->start = NewStart;
- MergeTo->end = I->end;
+LiveRange::iterator LiveRange::addSegment(Segment S) {
+ // Use the segment set, if it is available.
+ if (segmentSet != nullptr) {
+ addSegmentToSet(S);
+ return end();
}
-
- segments.erase(std::next(MergeTo), std::next(I));
- return MergeTo;
+ // Otherwise use the segment vector.
+ return CalcLiveRangeUtilVector(this).addSegment(S);
}
void LiveRange::append(const Segment S) {
segments.push_back(S);
}
-LiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) {
- SlotIndex Start = S.start, End = S.end;
- iterator it = std::upper_bound(From, end(), Start);
-
- // If the inserted segment starts in the middle or right at the end of
- // another segment, just extend that segment to contain the segment of S.
- if (it != begin()) {
- iterator B = std::prev(it);
- if (S.valno == B->valno) {
- if (B->start <= Start && B->end >= Start) {
- extendSegmentEndTo(B, End);
- return B;
- }
- } else {
- // Check to make sure that we are not overlapping two live segments with
- // different valno's.
- assert(B->end <= Start &&
- "Cannot overlap two segments with differing ValID's"
- " (did you def the same reg twice in a MachineInstr?)");
- }
- }
-
- // Otherwise, if this segment ends in the middle of, or right next to, another
- // segment, merge it into that segment.
- if (it != end()) {
- if (S.valno == it->valno) {
- if (it->start <= End) {
- it = extendSegmentStartTo(it, Start);
-
- // If S is a complete superset of a segment, we may need to grow its
- // endpoint as well.
- if (End > it->end)
- extendSegmentEndTo(it, End);
- return it;
- }
- } else {
- // Check to make sure that we are not overlapping two live segments with
- // different valno's.
- assert(it->start >= End &&
- "Cannot overlap two segments with differing ValID's");
- }
- }
-
- // Otherwise, this is just a new segment that doesn't interact with anything.
- // Insert it.
- return segments.insert(it, 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 live range before Kill, return NULL.
VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
- if (empty())
- return nullptr;
- iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
- if (I == begin())
- return nullptr;
- --I;
- if (I->end <= StartIdx)
- return nullptr;
- if (I->end < Kill)
- extendSegmentEndTo(I, Kill);
- return I->valno;
+ // Use the segment set, if it is available.
+ if (segmentSet != nullptr)
+ return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
+ // Otherwise use the segment vector.
+ return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
}
/// Remove the specified segment from this range. Note that the segment must
/// Also remove the value# from value# list.
void LiveRange::removeValNo(VNInfo *ValNo) {
if (empty()) return;
- iterator I = end();
- iterator E = begin();
- do {
- --I;
- if (I->valno == ValNo)
- segments.erase(I);
- } while (I != E);
+ segments.erase(std::remove_if(begin(), end(), [ValNo](const Segment &S) {
+ return S.valno == ValNo;
+ }), end());
// Now that ValNo is dead, remove it.
markValNoForDeletion(ValNo);
}
return V2;
}
+void LiveRange::flushSegmentSet() {
+ assert(segmentSet != nullptr && "segment set must have been created");
+ assert(
+ segments.empty() &&
+ "segment set can be used only initially before switching to the array");
+ segments.append(segmentSet->begin(), segmentSet->end());
+ segmentSet = nullptr;
+ verify();
+}
+
+bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const {
+ ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
+ ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
+
+ // If there are no regmask slots, we have nothing to search.
+ if (SlotI == SlotE)
+ return false;
+
+ // Start our search at the first segment that ends after the first slot.
+ const_iterator SegmentI = find(*SlotI);
+ const_iterator SegmentE = end();
+
+ // If there are no segments that end after the first slot, we're done.
+ if (SegmentI == SegmentE)
+ return false;
+
+ // Look for each slot in the live range.
+ for ( ; SlotI != SlotE; ++SlotI) {
+ // Go to the next segment that ends after the current slot.
+ // The slot may be within a hole in the range.
+ SegmentI = advanceTo(SegmentI, *SlotI);
+ if (SegmentI == SegmentE)
+ return false;
+
+ // If this segment contains the slot, we're done.
+ if (SegmentI->contains(*SlotI))
+ return true;
+ // Otherwise, look for the next slot.
+ }
+
+ // We didn't find a segment containing any of the slots.
+ return false;
+}
+
+void LiveInterval::freeSubRange(SubRange *S) {
+ S->~SubRange();
+ // Memory was allocated with BumpPtr allocator and is not freed here.
+}
+
void LiveInterval::removeEmptySubRanges() {
SubRange **NextPtr = &SubRanges;
SubRange *I = *NextPtr;
}
// Skip empty subranges until we find the first nonempty one.
do {
- I = I->Next;
+ SubRange *Next = I->Next;
+ freeSubRange(I);
+ I = Next;
} while (I != nullptr && I->empty());
*NextPtr = I;
}
}
+void LiveInterval::clearSubRanges() {
+ for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
+ Next = I->Next;
+ freeSubRange(I);
+ }
+ SubRanges = nullptr;
+}
+
/// Helper function for constructMainRangeFromSubranges(): Search the CFG
/// backwards until we find a place covered by a LiveRange segment that actually
/// has a valno set.
static void determineMissingVNIs(const SlotIndexes &Indexes, LiveInterval &LI) {
SmallPtrSet<const MachineBasicBlock*, 5> Visited;
- for (LiveRange::Segment &S : LI.segments) {
- if (S.valno != nullptr)
- continue;
- // This can only happen at the begin of a basic block.
- assert(S.start.isBlock() && "valno should only be missing at block begin");
-
- Visited.clear();
- const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start);
- for (const MachineBasicBlock *Pred : MBB->predecessors()) {
- VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited);
- if (VNI != nullptr) {
- S.valno = VNI;
- break;
+
+ LiveRange::iterator OutIt;
+ VNInfo *PrevValNo = nullptr;
+ for (LiveRange::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+ LiveRange::Segment &S = *I;
+ // Determine final VNI if necessary.
+ if (S.valno == nullptr) {
+ // This can only happen at the begin of a basic block.
+ assert(S.start.isBlock() && "valno should only be missing at block begin");
+
+ Visited.clear();
+ const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start);
+ for (const MachineBasicBlock *Pred : MBB->predecessors()) {
+ VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited);
+ if (VNI != nullptr) {
+ S.valno = VNI;
+ break;
+ }
}
+ assert(S.valno != nullptr && "could not determine valno");
+ }
+ // Merge with previous segment if it has the same VNI.
+ if (PrevValNo == S.valno && OutIt->end == S.start) {
+ OutIt->end = S.end;
+ } else {
+ // Didn't merge. Move OutIt to next segment.
+ if (PrevValNo == nullptr)
+ OutIt = LI.begin();
+ else
+ ++OutIt;
+
+ if (OutIt != I)
+ *OutIt = *I;
+ PrevValNo = S.valno;
}
- assert(S.valno != nullptr && "could not determine valno");
}
+ // If we merged some segments chop off the end.
+ ++OutIt;
+ LI.segments.erase(OutIt, LI.end());
}
void LiveInterval::constructMainRangeFromSubranges(
// - If any of the subranges is live at a point the main liverange has to be
// live too, conversily if no subrange is live the main range mustn't be
// live either.
- // We do this by scannig through all the subranges simultaneously creating new
+ // We do this by scanning through all the subranges simultaneously creating new
// segments in the main range as segments start/ends come up in the subranges.
assert(hasSubRanges() && "expected subranges to be present");
assert(segments.empty() && valnos.empty() && "expected empty main range");
Segment CurrentSegment;
bool ConstructingSegment = false;
bool NeedVNIFixup = false;
- unsigned ActiveMask = 0;
+ LaneBitmask ActiveMask = 0;
SlotIndex Pos = First;
while (true) {
SlotIndex NextPos = Last;
END_SEGMENT,
} Event = NOTHING;
// Which subregister lanes are affected by the current event.
- unsigned EventMask = 0;
+ LaneBitmask EventMask = 0;
// Whether a BEGIN_SEGMENT is also a valno definition point.
bool IsDef = false;
// Find the next begin or end of a subrange segment. Combine masks if we
NeedVNIFixup = true;
}
+ // In rare cases we can produce adjacent segments with the same value
+ // number (if they come from different subranges, but happen to have
+ // the same defining instruction). VNIFixup will fix those cases.
+ if (!empty() && segments.back().end == Pos &&
+ segments.back().valno == VNI)
+ NeedVNIFixup = true;
CurrentSegment.start = Pos;
CurrentSegment.valno = VNI;
ConstructingSegment = true;
super::print(OS);
// Print subranges
for (const SubRange &SR : subranges()) {
- OS << format(" L%04X ", SR.LaneMask) << SR;
+ OS << " L" << PrintLaneMask(SR.LaneMask) << ' ' << SR;
}
}
super::verify();
// Make sure SubRanges are fine and LaneMasks are disjunct.
- unsigned Mask = 0;
- unsigned MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) : ~0u;
+ LaneBitmask Mask = 0;
+ LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) : ~0u;
for (const SubRange &SR : subranges()) {
// Subrange lanemask should be disjunct to any previous subrange masks.
assert((Mask & SR.LaneMask) == 0);
// subrange mask should not contained in maximum lane mask for the vreg.
assert((Mask & ~MaxMask) == 0);
+ // empty subranges must be removed.
+ assert(!SR.empty());
SR.verify();
// Main liverange should cover subrange.
void LiveRangeUpdater::add(LiveRange::Segment Seg) {
assert(LR && "Cannot add to a null destination");
+ // Fall back to the regular add method if the live range
+ // is using the segment set instead of the segment vector.
+ if (LR->segmentSet != nullptr) {
+ LR->addSegmentToSet(Seg);
+ return;
+ }
+
// Flush the state if Start moves backwards.
if (!LastStart.isValid() || LastStart > Seg.start) {
if (isDirty())
LR->verify();
}
-unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) {
+unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
// Create initial equivalence classes.
EqClass.clear();
- EqClass.grow(LI->getNumValNums());
+ EqClass.grow(LR.getNumValNums());
const VNInfo *used = nullptr, *unused = nullptr;
// Determine connections.
- for (const VNInfo *VNI : LI->valnos) {
+ for (const VNInfo *VNI : LR.valnos) {
// Group all unused values into one class.
if (VNI->isUnused()) {
if (unused)
// Connect to values live out of predecessors.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI)
- if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
+ if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
EqClass.join(VNI->id, PVNI->id);
} else {
// Normal value defined by an instruction. Check for two-addr redef.
// FIXME: This could be coincidental. Should we really check for a tied
// operand constraint?
// Note that VNI->def may be a use slot for an early clobber def.
- if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def))
+ if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
EqClass.join(VNI->id, UVNI->id);
}
}
return EqClass.getNumClasses();
}
-void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
- MachineRegisterInfo &MRI) {
- assert(LIV[0] && "LIV[0] must be set");
- LiveInterval &LI = *LIV[0];
+template<typename LiveRangeT, typename EqClassesT>
+static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
+ EqClassesT VNIClasses) {
+ // Move segments to new intervals.
+ LiveRange::iterator J = LR.begin(), E = LR.end();
+ while (J != E && VNIClasses[J->valno->id] == 0)
+ ++J;
+ for (LiveRange::iterator I = J; I != E; ++I) {
+ if (unsigned eq = VNIClasses[I->valno->id]) {
+ assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&
+ "New intervals should be empty");
+ SplitLRs[eq-1]->segments.push_back(*I);
+ } else
+ *J++ = *I;
+ }
+ LR.segments.erase(J, E);
+ // Transfer VNInfos to their new owners and renumber them.
+ unsigned j = 0, e = LR.getNumValNums();
+ while (j != e && VNIClasses[j] == 0)
+ ++j;
+ for (unsigned i = j; i != e; ++i) {
+ VNInfo *VNI = LR.getValNumInfo(i);
+ if (unsigned eq = VNIClasses[i]) {
+ VNI->id = SplitLRs[eq-1]->getNumValNums();
+ SplitLRs[eq-1]->valnos.push_back(VNI);
+ } else {
+ VNI->id = j;
+ LR.valnos[j++] = VNI;
+ }
+ }
+ LR.valnos.resize(j);
+}
+
+void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
+ MachineRegisterInfo &MRI) {
// Rewrite instructions.
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
RE = MRI.reg_end(); RI != RE;) {
// NULL. If the use is tied to a def, VNI will be the defined value.
if (!VNI)
continue;
- MO.setReg(LIV[getEqClass(VNI)]->reg);
+ if (unsigned EqClass = getEqClass(VNI))
+ MO.setReg(LIV[EqClass-1]->reg);
}
- // Move runs to new intervals.
- LiveInterval::iterator J = LI.begin(), E = LI.end();
- while (J != E && EqClass[J->valno->id] == 0)
- ++J;
- for (LiveInterval::iterator I = J; I != E; ++I) {
- if (unsigned eq = EqClass[I->valno->id]) {
- assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
- "New intervals should be empty");
- LIV[eq]->segments.push_back(*I);
- } else
- *J++ = *I;
- }
- // TODO: do not cheat anymore by simply cleaning all subranges
- LI.clearSubRanges();
- LI.segments.erase(J, E);
-
- // Transfer VNInfos to their new owners and renumber them.
- unsigned j = 0, e = LI.getNumValNums();
- while (j != e && EqClass[j] == 0)
- ++j;
- for (unsigned i = j; i != e; ++i) {
- VNInfo *VNI = LI.getValNumInfo(i);
- if (unsigned eq = EqClass[i]) {
- VNI->id = LIV[eq]->getNumValNums();
- LIV[eq]->valnos.push_back(VNI);
- } else {
- VNI->id = j;
- LI.valnos[j++] = VNI;
+ // Distribute subregister liveranges.
+ if (LI.hasSubRanges()) {
+ unsigned NumComponents = EqClass.getNumClasses();
+ SmallVector<unsigned, 8> VNIMapping;
+ SmallVector<LiveInterval::SubRange*, 8> SubRanges;
+ BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
+ for (LiveInterval::SubRange &SR : LI.subranges()) {
+ // Create new subranges in the split intervals and construct a mapping
+ // for the VNInfos in the subrange.
+ unsigned NumValNos = SR.valnos.size();
+ VNIMapping.clear();
+ VNIMapping.reserve(NumValNos);
+ SubRanges.clear();
+ SubRanges.resize(NumComponents-1, nullptr);
+ for (unsigned I = 0; I < NumValNos; ++I) {
+ const VNInfo &VNI = *SR.valnos[I];
+ const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def);
+ assert(MainRangeVNI != nullptr
+ && "SubRange def must have corresponding main range def");
+ unsigned ComponentNum = getEqClass(MainRangeVNI);
+ VNIMapping.push_back(ComponentNum);
+ if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {
+ SubRanges[ComponentNum-1]
+ = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);
+ }
+ }
+ DistributeRange(SR, SubRanges.data(), VNIMapping);
}
+ LI.removeEmptySubRanges();
}
- LI.valnos.resize(j);
+
+ // Distribute main liverange.
+ DistributeRange(LI, LIV, EqClass);
}
projects / oota-llvm.git / blobdiff