+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) {