Lines Matching +full:segment +full:-
1 //===- LiveInterval.cpp - Live Interval Representation --------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
15 // individual segment is represented as an instance of LiveRange::Segment,
18 //===----------------------------------------------------------------------===//
35 #include "llvm/Config/llvm-config.h"
50 //===----------------------------------------------------------------------===//
53 // segment collection.
56 // class contains generic algorithms that call collection-specific methods,
62 //===----------------------------------------------------------------------===//
73 using Segment = LiveRange::Segment;
81 /// either a pre-existing one, or the one newly created.
90 assert((!ForVNI || ForVNI->def == Def) &&
94 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
95 impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
99 Segment *S = segmentAt(I);
100 if (SlotIndex::isSameInstr(Def, S->start)) {
101 assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
102 assert(S->valno->def == S->start && "Inconsistent existing value def");
104 // It is possible to have both normal and early-clobber defs of the same
108 // Just convert everything to early-clobber.
109 Def = std::min(Def, S->start);
110 if (Def != S->start)
111 S->start = S->valno->def = Def;
112 return S->valno;
114 assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
115 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
116 segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
124 impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
127 --I;
128 if (I->end <= StartIdx)
130 if (I->end < Use)
132 return I->valno;
140 iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
142 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
143 --I;
144 if (I->end <= StartIdx)
145 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
146 if (I->end < Use) {
147 if (LR->isUndefIn(Undefs, I->end, BeforeUse))
151 return std::make_pair(I->valno, false);
154 /// This method is used when we want to extend the segment specified
159 assert(I != segments().end() && "Not a valid segment!");
160 Segment *S = segmentAt(I);
161 VNInfo *ValNo = I->valno;
163 // Search for the first segment that we can't merge with.
165 for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo)
166 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
168 // If NewEnd was in the middle of a segment, make sure to get its endpoint.
169 S->end = std::max(NewEnd, std::prev(MergeTo)->end);
171 // If the newly formed segment now touches the segment after it and if they
172 // have the same value number, merge the two segments into one segment.
173 if (MergeTo != segments().end() && MergeTo->start <= I->end &&
174 MergeTo->valno == ValNo) {
175 S->end = MergeTo->end;
183 /// This method is used when we want to extend the segment specified
187 assert(I != segments().end() && "Not a valid segment!");
188 Segment *S = segmentAt(I);
189 VNInfo *ValNo = I->valno;
191 // Search for the first segment that we can't merge with.
195 S->start = NewStart;
199 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
200 --MergeTo;
201 } while (NewStart <= MergeTo->start);
203 // If we start in the middle of another segment, just delete a range and
204 // extend that segment.
205 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
206 segmentAt(MergeTo)->end = S->end;
208 // Otherwise, extend the segment right after.
210 Segment *MergeToSeg = segmentAt(MergeTo);
211 MergeToSeg->start = NewStart;
212 MergeToSeg->end = S->end;
219 iterator addSegment(Segment S) {
223 // If the inserted segment starts in the middle or right at the end of
224 // another segment, just extend that segment to contain the segment of S.
227 if (S.valno == B->valno) {
228 if (B->start <= Start && B->end >= Start) {
235 assert(B->end <= Start &&
241 // Otherwise, if this segment ends in the middle of, or right next
242 // to, another segment, merge it into that segment.
244 if (S.valno == I->valno) {
245 if (I->start <= End) {
248 // If S is a complete superset of a segment, we may need to grow its
250 if (End > I->end)
257 assert(I->start >= End &&
262 // Otherwise, this is just a new segment that doesn't interact with
273 Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
276 //===----------------------------------------------------------------------===//
278 // based on a segment vector.
279 //===----------------------------------------------------------------------===//
293 LiveRange::Segments &segmentsColl() { return LR->segments; }
295 void insertAtEnd(const Segment &S) { LR->segments.push_back(S); }
297 iterator find(SlotIndex Pos) { return LR->find(Pos); }
299 iterator findInsertPos(Segment S) { return llvm::upper_bound(*LR, S.start); }
302 //===----------------------------------------------------------------------===//
304 // based on a segment set.
305 //===----------------------------------------------------------------------===//
319 LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; }
321 void insertAtEnd(const Segment &S) {
322 LR->segmentSet->insert(LR->segmentSet->end(), S);
327 LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr));
328 if (I == LR->segmentSet->begin())
336 iterator findInsertPos(Segment S) {
337 iterator I = LR->segmentSet->upper_bound(S);
338 if (I != LR->segmentSet->end() && !(S.start < *I))
346 //===----------------------------------------------------------------------===//
348 //===----------------------------------------------------------------------===//
352 [&](const Segment &X) { return X.end <= Pos; });
356 // Use the segment set, if it is available.
359 // Otherwise use the segment vector.
364 // Use the segment set, if it is available.
366 return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);
367 // Otherwise use the segment vector.
368 return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);
371 // overlaps - Return true if the intersection of the two live ranges is
386 // A->overlaps(C) should return false since we want to be able to join
397 assert((StartPos->start <= i->start || StartPos == other.begin()) &&
400 if (i->start < j->start) {
401 i = std::upper_bound(i, ie, j->start);
402 if (i != begin()) --i;
403 } else if (j->start < i->start) {
405 if (StartPos != other.end() && StartPos->start <= i->start) {
407 j = std::upper_bound(j, je, i->start);
408 if (j != other.begin()) --j;
417 if (i->start > j->start) {
422 if (i->end > j->start)
441 const_iterator J = Other.find(I->start);
448 assert(J->end > I->start);
450 if (J->start < I->end) {
452 SlotIndex Def = std::max(I->start, J->start);
459 if (J->end > I->end) {
463 // Advance J until J->end > I->start.
467 while (J->end <= I->start);
471 /// overlaps - Return true if the live range overlaps an interval specified
476 return I != begin() && (--I)->end > Start;
484 for (const Segment &O : Other.segments) {
486 if (I == end() || I->start > O.start)
490 while (I->end < O.end) {
492 // Get next segment and abort if it was not adjacent.
494 if (I == end() || Last->end != I->start)
505 if (ValNo->id == getNumValNums()-1) {
508 } while (!valnos.empty() && valnos.back()->isUnused());
510 ValNo->markUnused();
514 /// RenumberValues - Renumber all values in order of appearance and delete the
519 for (const Segment &S : segments) {
523 assert(!VNI->isUnused() && "Unused valno used by live segment");
524 VNI->id = (unsigned)valnos.size();
529 void LiveRange::addSegmentToSet(Segment S) {
533 LiveRange::iterator LiveRange::addSegment(Segment S) {
534 // Use the segment set, if it is available.
539 // Otherwise use the segment vector.
543 void LiveRange::append(const Segment S) {
544 // Check that the segment belongs to the back of the list.
551 // Use the segment set, if it is available.
554 // Otherwise use the segment vector.
559 // Use the segment set, if it is available.
562 // Otherwise use the segment vector.
568 // Find the Segment containing this span.
571 // No Segment found, so nothing to do.
575 assert(I->containsInterval(Start, End)
576 && "Segment is not entirely in range!");
578 // If the span we are removing is at the start of the Segment, adjust it.
579 VNInfo *ValNo = I->valno;
580 if (I->start == Start) {
581 if (I->end == End) {
582 segments.erase(I); // Removed the whole Segment.
587 I->start = End;
591 // Otherwise if the span we are removing is at the end of the Segment,
593 if (I->end == End) {
594 I->end = Start;
598 // Otherwise, we are splitting the Segment into two pieces.
599 SlotIndex OldEnd = I->end;
600 I->end = Start; // Trim the old segment.
603 segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
607 VNInfo *ValNo = I->valno;
615 if (none_of(*this, [=](const Segment &S) { return S.valno == ValNo; }))
619 /// removeValNo - Remove all the segments defined by the specified value#.
624 [ValNo](const Segment &S) { return S.valno == ValNo; });
655 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
657 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
661 // and if they are neighbors, remove one Segment. This happens when we
663 if (OutIt->valno == nextValNo && OutIt->end == I->start) {
664 OutIt->end = I->end;
666 // Didn't merge. Move OutIt to the next segment,
668 OutIt->valno = nextValNo;
670 OutIt->start = I->start;
671 OutIt->end = I->end;
684 for (Segment &S : Other.segments)
685 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
697 VNI->id = NumValNos++; // Renumber val#.
705 for (Segment &S : Other.segments)
716 for (const Segment &S : RHS.segments)
720 /// MergeValueInAsValue - Merge all of the live segments of a specific val#
729 for (const Segment &S : RHS.segments)
734 /// MergeValueNumberInto - This method is called when two value nubmers
747 if (V1->id < V2->id) {
748 V1->copyFrom(*V2);
755 if (S->valno != V1) continue; // Not a V1 Segment.
760 iterator Prev = S-1;
761 if (Prev->valno == V2 && Prev->end == S->start) {
762 Prev->end = S->end;
764 // Erase this live-range.
772 // Ensure that it is a V2 live-range.
773 S->valno = V2;
779 if (I->start == S->end && I->valno == V2) {
780 S->end = I->end;
794 assert(segmentSet != nullptr && "segment set must have been created");
797 "segment set can be used only initially before switching to the array");
798 segments.append(segmentSet->begin(), segmentSet->end());
811 // Start our search at the first segment that ends after the first slot.
821 // Go to the next segment that ends after the current slot.
827 // If this segment contains the slot, we're done.
828 if (SegmentI->contains(*SlotI))
833 // We didn't find a segment containing any of the slots.
838 S->~SubRange();
846 if (!I->empty()) {
847 NextPtr = &I->Next;
853 SubRange *Next = I->Next;
856 } while (I != nullptr && I->empty());
863 Next = I->Next;
884 if (VNI->isUnused())
888 if (VNI->isPHIDef())
890 const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
894 if (!MOI->isReg() || !MOI->isDef())
896 if (MOI->getReg() != Reg)
898 LaneBitmask OrigMask = TRI.getSubRegIndexLaneMask(MOI->getSubReg());
936 // We have to split the subrange into a matching and non-matching part.
937 // Reduce lanemask of existing lane to non-matching part.
960 for (const Segment &S : segments)
989 raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveRange::Segment &S) {
990 return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';
994 LLVM_DUMP_METHOD void LiveRange::Segment::dump() const {
1003 for (const Segment &S : segments) {
1005 assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
1018 if (vni->isUnused()) {
1021 OS << vni->def;
1022 if (vni->isPHIDef())
1023 OS << "-phi";
1060 assert(I->start.isValid());
1061 assert(I->end.isValid());
1062 assert(I->start < I->end);
1063 assert(I->valno != nullptr);
1064 assert(I->valno->id < valnos.size());
1065 assert(I->valno == valnos[I->valno->id]);
1067 assert(I->end <= std::next(I)->start);
1068 if (I->end == std::next(I)->start)
1069 assert(I->valno != std::next(I)->valno);
1079 LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg())
1098 //===----------------------------------------------------------------------===//
1100 //===----------------------------------------------------------------------===//
1104 // - When LastStart is invalid, Spills is empty and the iterators are invalid.
1114 // - LR.begin() <= WriteI <= ReadI <= LR.end().
1115 // - Segments in all three areas are fully ordered and coalesced.
1116 // - Segments in area 1 precede and can't coalesce with segments in area 2.
1117 // - Segments in Spills precede and can't coalesce with segments in area 2.
1118 // - No coalescing is possible between segments in Spills and segments in area
1125 // and WriteI[-1].start <= LastStart.
1137 OS << " updater with gap = " << (ReadI - WriteI)
1140 for (const auto &S : make_range(LR->begin(), WriteI))
1146 for (const auto &S : make_range(ReadI, LR->end()))
1157 static inline bool coalescable(const LiveRange::Segment &A,
1158 const LiveRange::Segment &B) {
1168 void LiveRangeUpdater::add(LiveRange::Segment Seg) {
1172 // is using the segment set instead of the segment vector.
1173 if (LR->segmentSet != nullptr) {
1174 LR->addSegmentToSet(Seg);
1184 WriteI = ReadI = LR->begin();
1191 LiveRange::iterator E = LR->end();
1192 if (ReadI != E && ReadI->end <= Seg.start) {
1198 ReadI = WriteI = LR->find(Seg.start);
1200 while (ReadI != E && ReadI->end <= Seg.start)
1204 assert(ReadI == E || ReadI->end > Seg.start);
1206 // Check if the ReadI segment begins early.
1207 if (ReadI != E && ReadI->start <= Seg.start) {
1208 assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1210 if (ReadI->end >= Seg.end)
1213 Seg.start = ReadI->start;
1219 Seg.end = std::max(Seg.end, ReadI->end);
1230 // Try coalescing Seg into WriteI[-1].
1231 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {
1232 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1244 LR->segments.push_back(Seg);
1245 WriteI = ReadI = LR->end();
1254 size_t GapSize = ReadI - WriteI;
1259 LiveRange::iterator B = LR->begin();
1266 if (Src != B && Src[-1].start > SpillSrc[-1].start)
1267 *--Dst = *--Src;
1269 *--Dst = *--SpillSrc;
1271 assert(NumMoved == size_t(Spills.end() - SpillSrc));
1285 LR->segments.erase(WriteI, ReadI);
1286 LR->verify();
1290 // Resize the WriteI - ReadI gap to match Spills.
1291 size_t GapSize = ReadI - WriteI;
1294 size_t WritePos = WriteI - LR->begin();
1295 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1297 WriteI = LR->begin() + WritePos;
1300 LR->segments.erase(WriteI + Spills.size(), ReadI);
1304 LR->verify();
1317 if (VNI->isUnused()) {
1319 EqClass.join(unused->id, VNI->id);
1324 if (VNI->isPHIDef()) {
1325 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1326 assert(MBB && "Phi-def has no defining MBB");
1328 for (MachineBasicBlock *Pred : MBB->predecessors())
1330 EqClass.join(VNI->id, PVNI->id);
1332 // Normal value defined by an instruction. Check for two-addr redef.
1335 // Note that VNI->def may be a use slot for an early clobber def.
1336 if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
1337 EqClass.join(VNI->id, UVNI->id);
1343 EqClass.join(used->id, unused->id);
1356 if (MI->isDebugValue()) {
1359 SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);
1371 MO.setReg(LIV[EqClass - 1]->reg());
1387 SubRanges.resize(NumComponents-1, nullptr);
1398 if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {
1399 SubRanges[ComponentNum-1]
1400 = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);