From bb688cec09d08fb4c5e17d82c86bba11f0ce3168 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 11 Aug 2011 20:41:41 +0000 Subject: Remove some dead code. The InterferenceResult iterator turned out to be less important than we thought it would be. LiveIntervalUnion clients want higher level information, like the list of interfering virtual registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137346 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveIntervalUnion.cpp | 19 ------------------- 1 file changed, 19 deletions(-) (limited to 'lib/CodeGen/LiveIntervalUnion.cpp') diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index 70003e7..b30e169 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -91,25 +91,6 @@ LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { OS << '\n'; } -void LiveIntervalUnion::InterferenceResult::print(raw_ostream &OS, - const TargetRegisterInfo *TRI) const { - OS << '[' << start() << ';' << stop() << "):" - << PrintReg(interference()->reg, TRI); -} - -void LiveIntervalUnion::Query::print(raw_ostream &OS, - const TargetRegisterInfo *TRI) { - OS << "Interferences with "; - LiveUnion->print(OS, TRI); - InterferenceResult IR = firstInterference(); - while (isInterference(IR)) { - OS << " "; - IR.print(OS, TRI); - OS << '\n'; - nextInterference(IR); - } -} - #ifndef NDEBUG // Verify the live intervals in this union and add them to the visited set. void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { -- cgit v1.1 From 9942ba9c0ed45c77298cdeb7a9326f04745d5709 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 11 Aug 2011 21:18:34 +0000 Subject: Remove more dead code. collectInterferingVRegs will be the primary function for interference checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137354 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveIntervalUnion.cpp | 28 ++-------------------------- 1 file changed, 2 insertions(+), 26 deletions(-) (limited to 'lib/CodeGen/LiveIntervalUnion.cpp') diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index b30e169..cf5fb6a 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -181,32 +181,6 @@ LiveIntervalUnion::Query::firstInterference() { return FirstInterference; } -// Treat the result as an iterator and advance to the next interfering pair -// of segments. This is a plain iterator with no filter. -bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const { - assert(isInterference(IR) && "iteration past end of interferences"); - - // Advance either the VirtReg or LiveUnion segment to ensure that we visit all - // unique overlapping pairs. - if (IR.VirtRegI->end < IR.LiveUnionI.stop()) { - if (++IR.VirtRegI == VirtReg->end()) - return false; - } - else { - if (!(++IR.LiveUnionI).valid()) { - IR.VirtRegI = VirtReg->end(); - return false; - } - } - // Short-circuit findIntersection() if possible. - if (overlap(*IR.VirtRegI, IR.LiveUnionI)) - return true; - - // Find the next intersection. - findIntersection(IR); - return isInterference(IR); -} - // Scan the vector of interfering virtual registers in this union. Assume it's // quite small. bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { @@ -226,6 +200,8 @@ bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { // For comments on how to speed it up, see Query::findIntersection(). unsigned LiveIntervalUnion::Query:: collectInterferingVRegs(unsigned MaxInterferingRegs) { + if (InterferingVRegs.size() >= MaxInterferingRegs) + return InterferingVRegs.size(); InterferenceResult IR = firstInterference(); LiveInterval::iterator VirtRegEnd = VirtReg->end(); LiveInterval *RecentInterferingVReg = NULL; -- cgit v1.1 From fe026e182993a94381d197f140b19b999c3e17ec Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 11 Aug 2011 22:46:04 +0000 Subject: Eliminate the last use of InterferenceResult. The Query class now holds two iterators instead of an InterferenceResult instance. The iterators are used as bookmarks for repeated collectInterferingVRegs calls. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137380 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveIntervalUnion.cpp | 114 ++++++++++++++++++-------------------- 1 file changed, 54 insertions(+), 60 deletions(-) (limited to 'lib/CodeGen/LiveIntervalUnion.cpp') diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index cf5fb6a..6c3dc16 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -117,68 +117,35 @@ void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { // // Assumes that segments are sorted by start position in both // LiveInterval and LiveSegments. -void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const { +void LiveIntervalUnion::Query::findIntersection() { // Search until reaching the end of the LiveUnion segments. LiveInterval::iterator VirtRegEnd = VirtReg->end(); - if (IR.VirtRegI == VirtRegEnd) + if (VirtRegI == VirtRegEnd) return; - while (IR.LiveUnionI.valid()) { + while (LiveUnionI.valid()) { // Slowly advance the live virtual reg iterator until we surpass the next // segment in LiveUnion. // // Note: If this is ever used for coalescing of fixed registers and we have // a live vreg with thousands of segments, then change this code to use // upperBound instead. - IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start()); - if (IR.VirtRegI == VirtRegEnd) + VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); + if (VirtRegI == VirtRegEnd) break; // Retain current (nonoverlapping) LiveUnionI // VirtRegI may have advanced far beyond LiveUnionI, catch up. - IR.LiveUnionI.advanceTo(IR.VirtRegI->start); + LiveUnionI.advanceTo(VirtRegI->start); // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end - if (!IR.LiveUnionI.valid()) + if (!LiveUnionI.valid()) break; - if (IR.LiveUnionI.start() < IR.VirtRegI->end) { - assert(overlap(*IR.VirtRegI, IR.LiveUnionI) && - "upperBound postcondition"); + if (LiveUnionI.start() < VirtRegI->end) { + assert(overlap(*VirtRegI, LiveUnionI) && "upperBound postcondition"); break; } } - if (!IR.LiveUnionI.valid()) - IR.VirtRegI = VirtRegEnd; -} - -// Find the first intersection, and cache interference info -// (retain segment iterators into both VirtReg and LiveUnion). -const LiveIntervalUnion::InterferenceResult & -LiveIntervalUnion::Query::firstInterference() { - if (CheckedFirstInterference) - return FirstInterference; - CheckedFirstInterference = true; - InterferenceResult &IR = FirstInterference; - IR.LiveUnionI.setMap(LiveUnion->getMap()); - - // Quickly skip interference check for empty sets. - if (VirtReg->empty() || LiveUnion->empty()) { - IR.VirtRegI = VirtReg->end(); - } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) { - // VirtReg starts first, perform double binary search. - IR.VirtRegI = VirtReg->find(LiveUnion->startIndex()); - if (IR.VirtRegI != VirtReg->end()) - IR.LiveUnionI.find(IR.VirtRegI->start); - } else { - // LiveUnion starts first, perform double binary search. - IR.LiveUnionI.find(VirtReg->beginIndex()); - if (IR.LiveUnionI.valid()) - IR.VirtRegI = VirtReg->find(IR.LiveUnionI.start()); - else - IR.VirtRegI = VirtReg->end(); - } - findIntersection(FirstInterference); - assert((IR.VirtRegI == VirtReg->end() || IR.LiveUnionI.valid()) - && "Uninitialized iterator"); - return FirstInterference; + if (!LiveUnionI.valid()) + VirtRegI = VirtRegEnd; } // Scan the vector of interfering virtual registers in this union. Assume it's @@ -200,37 +167,64 @@ bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { // For comments on how to speed it up, see Query::findIntersection(). unsigned LiveIntervalUnion::Query:: collectInterferingVRegs(unsigned MaxInterferingRegs) { - if (InterferingVRegs.size() >= MaxInterferingRegs) + // Fast path return if we already have the desired information. + if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) return InterferingVRegs.size(); - InterferenceResult IR = firstInterference(); + + // Set up iterators on the first call. + if (!CheckedFirstInterference) { + CheckedFirstInterference = true; + LiveUnionI.setMap(LiveUnion->getMap()); + + // Quickly skip interference check for empty sets. + if (VirtReg->empty() || LiveUnion->empty()) { + VirtRegI = VirtReg->end(); + } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) { + // VirtReg starts first, perform double binary search. + VirtRegI = VirtReg->find(LiveUnion->startIndex()); + if (VirtRegI != VirtReg->end()) + LiveUnionI.find(VirtRegI->start); + } else { + // LiveUnion starts first, perform double binary search. + LiveUnionI.find(VirtReg->beginIndex()); + if (LiveUnionI.valid()) + VirtRegI = VirtReg->find(LiveUnionI.start()); + else + VirtRegI = VirtReg->end(); + } + findIntersection(); + assert((VirtRegI == VirtReg->end() || LiveUnionI.valid()) + && "Uninitialized iterator"); + } + LiveInterval::iterator VirtRegEnd = VirtReg->end(); LiveInterval *RecentInterferingVReg = NULL; - if (IR.VirtRegI != VirtRegEnd) while (IR.LiveUnionI.valid()) { + if (VirtRegI != VirtRegEnd) while (LiveUnionI.valid()) { // Advance the union's iterator to reach an unseen interfering vreg. do { - if (IR.LiveUnionI.value() == RecentInterferingVReg) + if (LiveUnionI.value() == RecentInterferingVReg) continue; - if (!isSeenInterference(IR.LiveUnionI.value())) + if (!isSeenInterference(LiveUnionI.value())) break; // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = IR.LiveUnionI.value(); + RecentInterferingVReg = LiveUnionI.value(); - } while ((++IR.LiveUnionI).valid()); - if (!IR.LiveUnionI.valid()) + } while ((++LiveUnionI).valid()); + if (!LiveUnionI.valid()) break; // Advance the VirtReg iterator until surpassing the next segment in // LiveUnion. - IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start()); - if (IR.VirtRegI == VirtRegEnd) + VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); + if (VirtRegI == VirtRegEnd) break; // Check for intersection with the union's segment. - if (overlap(*IR.VirtRegI, IR.LiveUnionI)) { + if (overlap(*VirtRegI, LiveUnionI)) { - if (!IR.LiveUnionI.value()->isSpillable()) + if (!LiveUnionI.value()->isSpillable()) SeenUnspillableVReg = true; if (InterferingVRegs.size() == MaxInterferingRegs) @@ -238,17 +232,17 @@ collectInterferingVRegs(unsigned MaxInterferingRegs) { // interference exists beyond those we collected. return MaxInterferingRegs; - InterferingVRegs.push_back(IR.LiveUnionI.value()); + InterferingVRegs.push_back(LiveUnionI.value()); // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = IR.LiveUnionI.value(); - ++IR.LiveUnionI; + RecentInterferingVReg = LiveUnionI.value(); + ++LiveUnionI; continue; } // VirtRegI may have advanced far beyond LiveUnionI, // do a fast intersection test to "catch up" - IR.LiveUnionI.advanceTo(IR.VirtRegI->start); + LiveUnionI.advanceTo(VirtRegI->start); } SeenAllInterferences = true; return InterferingVRegs.size(); -- cgit v1.1 From 9b7ff12dd1e5e93d3305b366f79896308bed4a60 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 12 Aug 2011 00:22:04 +0000 Subject: Simplify the interference checking code a bit. This is possible now that we now longer provide an interface to iterate the interference overlaps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137397 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveIntervalUnion.cpp | 151 +++++++++++--------------------------- 1 file changed, 42 insertions(+), 109 deletions(-) (limited to 'lib/CodeGen/LiveIntervalUnion.cpp') diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index 6c3dc16..110fe1e 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -99,55 +99,6 @@ void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { } #endif //!NDEBUG -// Private interface accessed by Query. -// -// Find a pair of segments that intersect, one in the live virtual register -// (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query) -// is responsible for advancing the LiveIntervalUnion segments to find a -// "notable" intersection, which requires query-specific logic. -// -// This design assumes only a fast mechanism for intersecting a single live -// virtual register segment with a set of LiveIntervalUnion segments. This may -// be ok since most virtual registers have very few segments. If we had a data -// structure that optimizd MxN intersection of segments, then we would bypass -// the loop that advances within the LiveInterval. -// -// If no intersection exists, set VirtRegI = VirtRegEnd, and set SI to the first -// segment whose start point is greater than LiveInterval's end point. -// -// Assumes that segments are sorted by start position in both -// LiveInterval and LiveSegments. -void LiveIntervalUnion::Query::findIntersection() { - // Search until reaching the end of the LiveUnion segments. - LiveInterval::iterator VirtRegEnd = VirtReg->end(); - if (VirtRegI == VirtRegEnd) - return; - while (LiveUnionI.valid()) { - // Slowly advance the live virtual reg iterator until we surpass the next - // segment in LiveUnion. - // - // Note: If this is ever used for coalescing of fixed registers and we have - // a live vreg with thousands of segments, then change this code to use - // upperBound instead. - VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); - if (VirtRegI == VirtRegEnd) - break; // Retain current (nonoverlapping) LiveUnionI - - // VirtRegI may have advanced far beyond LiveUnionI, catch up. - LiveUnionI.advanceTo(VirtRegI->start); - - // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end - if (!LiveUnionI.valid()) - break; - if (LiveUnionI.start() < VirtRegI->end) { - assert(overlap(*VirtRegI, LiveUnionI) && "upperBound postcondition"); - break; - } - } - if (!LiveUnionI.valid()) - VirtRegI = VirtRegEnd; -} - // Scan the vector of interfering virtual registers in this union. Assume it's // quite small. bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { @@ -156,15 +107,15 @@ bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { return I != InterferingVRegs.end(); } -// Count the number of virtual registers in this union that interfere with this +// Collect virtual registers in this union that interfere with this // query's live virtual register. // -// The number of times that we either advance IR.VirtRegI or call -// LiveUnion.upperBound() will be no more than the number of holes in -// VirtReg. So each invocation of collectInterferingVRegs() takes -// time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()). +// The query state is one of: +// +// 1. CheckedFirstInterference == false: Iterators are uninitialized. +// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. +// 3. Iterators left at the last seen intersection. // -// For comments on how to speed it up, see Query::findIntersection(). unsigned LiveIntervalUnion::Query:: collectInterferingVRegs(unsigned MaxInterferingRegs) { // Fast path return if we already have the desired information. @@ -174,74 +125,56 @@ collectInterferingVRegs(unsigned MaxInterferingRegs) { // Set up iterators on the first call. if (!CheckedFirstInterference) { CheckedFirstInterference = true; - LiveUnionI.setMap(LiveUnion->getMap()); // Quickly skip interference check for empty sets. if (VirtReg->empty() || LiveUnion->empty()) { - VirtRegI = VirtReg->end(); - } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) { - // VirtReg starts first, perform double binary search. - VirtRegI = VirtReg->find(LiveUnion->startIndex()); - if (VirtRegI != VirtReg->end()) - LiveUnionI.find(VirtRegI->start); - } else { - // LiveUnion starts first, perform double binary search. - LiveUnionI.find(VirtReg->beginIndex()); - if (LiveUnionI.valid()) - VirtRegI = VirtReg->find(LiveUnionI.start()); - else - VirtRegI = VirtReg->end(); + SeenAllInterferences = true; + return 0; } - findIntersection(); - assert((VirtRegI == VirtReg->end() || LiveUnionI.valid()) - && "Uninitialized iterator"); + + // In most cases, the union will start before VirtReg. + VirtRegI = VirtReg->begin(); + LiveUnionI.setMap(LiveUnion->getMap()); + LiveUnionI.find(VirtRegI->start); } LiveInterval::iterator VirtRegEnd = VirtReg->end(); - LiveInterval *RecentInterferingVReg = NULL; - if (VirtRegI != VirtRegEnd) while (LiveUnionI.valid()) { - // Advance the union's iterator to reach an unseen interfering vreg. - do { - if (LiveUnionI.value() == RecentInterferingVReg) - continue; - - if (!isSeenInterference(LiveUnionI.value())) - break; + LiveInterval *RecentReg = 0; + while (LiveUnionI.valid()) { + assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg"); + + // Check for overlapping interference. + while (VirtRegI->start < LiveUnionI.stop() && + VirtRegI->end > LiveUnionI.start()) { + // This is an overlap, record the interfering register. + LiveInterval *VReg = LiveUnionI.value(); + if (VReg != RecentReg && !isSeenInterference(VReg)) { + RecentReg = VReg; + InterferingVRegs.push_back(VReg); + if (InterferingVRegs.size() >= MaxInterferingRegs) + return InterferingVRegs.size(); + } + // This LiveUnion segment is no longer interesting. + if (!(++LiveUnionI).valid()) { + SeenAllInterferences = true; + return InterferingVRegs.size(); + } + } - // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = LiveUnionI.value(); + // The iterators are now not overlapping, LiveUnionI has been advanced + // beyond VirtRegI. + assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); - } while ((++LiveUnionI).valid()); - if (!LiveUnionI.valid()) - break; - - // Advance the VirtReg iterator until surpassing the next segment in - // LiveUnion. + // Advance the iterator that ends first. VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); if (VirtRegI == VirtRegEnd) break; - // Check for intersection with the union's segment. - if (overlap(*VirtRegI, LiveUnionI)) { - - if (!LiveUnionI.value()->isSpillable()) - SeenUnspillableVReg = true; - - if (InterferingVRegs.size() == MaxInterferingRegs) - // Leave SeenAllInterferences set to false to indicate that at least one - // interference exists beyond those we collected. - return MaxInterferingRegs; - - InterferingVRegs.push_back(LiveUnionI.value()); - - // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = LiveUnionI.value(); - ++LiveUnionI; - + // Detect overlap, handle above. + if (VirtRegI->start < LiveUnionI.stop()) continue; - } - // VirtRegI may have advanced far beyond LiveUnionI, - // do a fast intersection test to "catch up" + + // Still not overlapping. Catch up LiveUnionI. LiveUnionI.advanceTo(VirtRegI->start); } SeenAllInterferences = true; -- cgit v1.1