Index: include/llvm/CodeGen/LiveInterval.h =================================================================== --- include/llvm/CodeGen/LiveInterval.h +++ include/llvm/CodeGen/LiveInterval.h @@ -27,6 +27,7 @@ #include "llvm/Support/Allocator.h" #include #include +#include namespace llvm { class CoalescerPair; @@ -188,6 +189,19 @@ Segments segments; // the liveness segments VNInfoList valnos; // value#'s + // the set is used to accelerate initial creation of live ranges for physical registers + typedef std::set SegmentSet; + SegmentSet* segmentSet; + + LiveRange() : segmentSet(NULL) { + } + + ~LiveRange() { + if (segmentSet != NULL) { + delete segmentSet; + } + } + typedef Segments::iterator iterator; iterator begin() { return segments.begin(); } iterator end() { return segments.end(); } @@ -401,6 +415,12 @@ /// appropriate. This returns an iterator to the inserted segment (which /// may have grown since it was inserted). iterator addSegment(Segment S) { + // segment set is created use it instead of the segments vector + if (segmentSet != NULL) { + segsetAdd(S); + return segments.end(); + } + // otherwise use the segment vector return addSegmentFrom(S, segments.begin()); } @@ -496,6 +516,18 @@ const SlotIndex &otherIndex = other.beginIndex(); return thisIndex < otherIndex; } + + /// Activate segment set to speed-up initial creation of + /// large live ranges. The method should be called just + /// after creation of the live range, before adding any + /// segments. + void createSegmentSet(); + + /// Flush segment set into the regular segment vector. + /// The method is to be called in combination with + /// createSegmentSet(), after the live range has been + /// created. + void flushSegmentSet(); void print(raw_ostream &OS) const; void dump() const; @@ -516,6 +548,16 @@ iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); void markValNoForDeletion(VNInfo *V); + // Alternative implementation of live range operations working + // on segment set instead of segment vector. These operations + // are used during initialization of/ live ranges, if the segment + // set has been activated by createSegmentSet(). + SegmentSet::iterator segsetFind(SlotIndex Pos); + VNInfo *segsetCreateDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); + void segsetExtendSegmentEndTo(SegmentSet::iterator I, SlotIndex NewEnd); + VNInfo *segsetExtendInBlock(SlotIndex StartIdx, SlotIndex Kill); + SegmentSet::iterator segsetExtendSegmentStartTo(SegmentSet::iterator I, SlotIndex NewStr); + SegmentSet::iterator segsetAdd(Segment S); }; inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { Index: include/llvm/CodeGen/LiveIntervalAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveIntervalAnalysis.h +++ include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -382,7 +382,11 @@ if (!LR) { // Compute missing ranges on demand. RegUnitRanges[Unit] = LR = new LiveRange(); + // use segment set to speed-up initial computation of the live range + LR->createSegmentSet(); computeRegUnitRange(*LR, Unit); + // flush the segment set to array and destroy it + LR->flushSegmentSet(); } return *LR; } Index: lib/CodeGen/LiveInterval.cpp =================================================================== --- lib/CodeGen/LiveInterval.cpp +++ lib/CodeGen/LiveInterval.cpp @@ -52,6 +52,13 @@ VNInfo *LiveRange::createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) { assert(!Def.isDead() && "Cannot define a value at the dead slot"); + + // if segmentSet exists use it instead of the vector + if (segmentSet != NULL) { + return segsetCreateDeadDef(Def, VNInfoAllocator); + } + + // otherwise use the vector iterator I = find(Def); if (I == end()) { VNInfo *VNI = getNextValue(Def, VNInfoAllocator); @@ -330,6 +337,11 @@ /// 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 the segment set exists, use it instead of the segment vector + if (segmentSet != NULL) { + return segsetExtendInBlock(StartIdx, Kill); + } + // otherwise use the segment vector if (empty()) return nullptr; iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); @@ -570,6 +582,213 @@ return V2; } +/// Activate segment set to speed-up initial creation of large live ranges. The +/// method should be called just after creation of the live range, before adding +/// any segments. +void LiveRange::createSegmentSet() { + assert(segmentSet == NULL && "segments set already exists"); + assert(segments.empty() && "call the method before adding any segment"); + segmentSet = new SegmentSet(); +} + +/// Flush segment set into the regular segment vector. The method is to be called +/// in combination with createSegmentSet(), after the live range has been created. +void LiveRange::flushSegmentSet() { + assert(segmentSet != NULL && "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()); + delete segmentSet; + segmentSet = NULL; + verify(); +} + +// analogous to find, but works with segment set instead of segment vector +LiveRange::SegmentSet::iterator LiveRange::segsetFind(SlotIndex Pos) { + SegmentSet::iterator I = segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), NULL)); + if (I == segmentSet->begin()) { + return I; + } else { + SegmentSet::iterator PrevI = std::prev(I); + if (Pos < (*PrevI).end) { + return PrevI; + } else { + return I; + } + } +} + +// a variant of createDeadDef working with the segment set instead of the segment vector +VNInfo *LiveRange::segsetCreateDeadDef(SlotIndex Def, + VNInfo::Allocator &VNInfoAllocator) { + assert(!Def.isDead() && "Cannot define a value at the dead slot"); + assert(segmentSet != NULL); + + SegmentSet::iterator I = segsetFind(Def); + if (I == segmentSet->end()) { + VNInfo *VNI = getNextValue(Def, VNInfoAllocator); + segmentSet->insert(I, Segment(Def, Def.getDeadSlot(), VNI)); + return VNI; + } + Segment* S = const_cast(&(*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 = getNextValue(Def, VNInfoAllocator); + segmentSet->insert(I, Segment(Def, Def.getDeadSlot(), VNI)); + return VNI; +} + +// a variant of extendInBlock working with the segment set instead of the segment vector +VNInfo *LiveRange::segsetExtendInBlock(SlotIndex StartIdx, SlotIndex Kill) { + assert(segmentSet != NULL); + + if (segmentSet->empty()) { + return nullptr; + } + SlotIndex KillPrev = Kill.getPrevSlot(); + SegmentSet::iterator I = segmentSet->upper_bound(Segment(KillPrev, Kill, NULL)); + if (I != segmentSet->end() && !(KillPrev < *I)) { + ++I; + } + if (I == segmentSet->begin()) { + return nullptr; + } + --I; + if (I->end <= StartIdx) + return nullptr; + if (I->end < Kill) { + segsetExtendSegmentEndTo(I, Kill); + } + return I->valno; +} + +// a variant of extendSegmentEndTo working with the segment set instead of the segment vector +void LiveRange::segsetExtendSegmentEndTo(LiveRange::SegmentSet::iterator I, SlotIndex NewEnd) { + assert(I != segmentSet->end() && "Not a valid segment!"); + Segment* S = const_cast(&(*I)); + VNInfo *ValNo = S->valno; + + // Search for the first segment that we can't merge with. + SegmentSet::iterator MergeTo = std::next(I); + for (; MergeTo != segmentSet->end() && NewEnd >= MergeTo->end; ++MergeTo) { + assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); + } + + // If NewEnd was in the middle of an 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 != segmentSet->end() && MergeTo->start <= I->end && + MergeTo->valno == ValNo) { + S->end = MergeTo->end; + ++MergeTo; + } + + // Erase any dead segments. + segmentSet->erase(std::next(I), MergeTo); +} + +// a variant of extendSegmentStartTo working with the segment set instead of the segment vector +LiveRange::SegmentSet::iterator +LiveRange::segsetExtendSegmentStartTo(LiveRange::SegmentSet::iterator I, SlotIndex NewStart) { + assert(I != segmentSet->end() && "Not a valid segment!"); + VNInfo *ValNo = I->valno; + + // Search for the first segment that we can't merge with. + LiveRange::SegmentSet::iterator MergeTo = I; + do { + if (MergeTo == segmentSet->begin()) { + Segment* S = const_cast(&(*I)); + S->start = NewStart; + segmentSet->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 segment and + // extend that segment. + if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { + Segment* MergeToRange = const_cast(&(*MergeTo)); + MergeToRange->end = I->end; + } else { + // Otherwise, extend the segment right after. + ++MergeTo; + Segment* MergeToRange = const_cast(&(*MergeTo)); + MergeToRange->start = NewStart; + MergeToRange->end = I->end; + } + + segmentSet->erase(std::next(MergeTo), std::next(I)); + return MergeTo; +} + +// analogous to addSegmentFrom, but works with the segment set instead of the segment vector +LiveRange::SegmentSet::iterator LiveRange::segsetAdd(Segment S) { + assert(segmentSet && "segments set must exist"); + assert(segments.empty() && "segments vector must not be filled directly"); + SlotIndex Start = S.start, End = S.end; + SegmentSet::iterator it = segmentSet->upper_bound(S); + if (it != segmentSet->end() && !(Start < *it)) { + ++it; + } + + // 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 != segmentSet->begin()) { + SegmentSet::iterator B = std::prev(it); + if (S.valno == B->valno) { + if (B->start <= Start && B->end >= Start) { + segsetExtendSegmentEndTo(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 != segmentSet->end()) { + if (S.valno == it->valno) { + if (it->start <= End) { + it = segsetExtendSegmentStartTo(it, Start); + + // If S is a complete superset of an segment, we may need to grow its + // endpoint as well. + if (End > it->end) + segsetExtendSegmentEndTo(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. + LiveRange::SegmentSet::iterator retIt = segmentSet->insert(it, S); + return retIt; +} + unsigned LiveInterval::getSize() const { unsigned Sum = 0; for (const_iterator I = begin(), E = end(); I != E; ++I) @@ -723,6 +942,13 @@ 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 != NULL) { + LR->addSegment(Seg); + return; + } + // Flush the state if Start moves backwards. if (!LastStart.isValid() || LastStart > Seg.start) { if (isDirty()) Index: lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- lib/CodeGen/LiveIntervalAnalysis.cpp +++ lib/CodeGen/LiveIntervalAnalysis.cpp @@ -293,6 +293,8 @@ LiveRange *LR = RegUnitRanges[Unit]; if (!LR) { LR = RegUnitRanges[Unit] = new LiveRange(); + // use segment set to speed-up initial computation of the live range + LR->createSegmentSet(); NewRanges.push_back(Unit); } VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); @@ -307,7 +309,10 @@ // Compute the 'normal' part of the ranges. for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { unsigned Unit = NewRanges[i]; - computeRegUnitRange(*RegUnitRanges[Unit], Unit); + LiveRange *LR = RegUnitRanges[Unit]; + computeRegUnitRange(*LR, Unit); + // flush the segment set to array and destroy it + LR->flushSegmentSet(); } }