X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.cpp;h=025d99ce78812c8f42a003a1cda8b9d206b56b97;hb=e5457136e7f4d5ef3bddf4ed62416a7e7967220e;hp=cf5fb6a09f14b3424d5e12cf577077c808aa1852;hpb=9942ba9c0ed45c77298cdeb7a9326f04745d5709;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index cf5fb6a09f1..025d99ce788 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -13,26 +13,27 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" -#include "LiveIntervalUnion.h" +#include "llvm/CodeGen/LiveIntervalUnion.h" #include "llvm/ADT/SparseBitVector.h" -#include "llvm/CodeGen/MachineLoopRanges.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetRegisterInfo.h" +#include using namespace llvm; +#define DEBUG_TYPE "regalloc" + // Merge a LiveInterval's segments. Guarantee no overlaps. -void LiveIntervalUnion::unify(LiveInterval &VirtReg) { - if (VirtReg.empty()) +void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) { + if (Range.empty()) return; ++Tag; // Insert each of the virtual register's live segments into the map. - LiveInterval::iterator RegPos = VirtReg.begin(); - LiveInterval::iterator RegEnd = VirtReg.end(); + LiveRange::const_iterator RegPos = Range.begin(); + LiveRange::const_iterator RegEnd = Range.end(); SegmentIter SegPos = Segments.find(RegPos->start); while (SegPos.valid()) { @@ -52,14 +53,14 @@ void LiveIntervalUnion::unify(LiveInterval &VirtReg) { } // Remove a live virtual register's segments from this union. -void LiveIntervalUnion::extract(LiveInterval &VirtReg) { - if (VirtReg.empty()) +void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) { + if (Range.empty()) return; ++Tag; // Remove each of the virtual register's live segments from the map. - LiveInterval::iterator RegPos = VirtReg.begin(); - LiveInterval::iterator RegEnd = VirtReg.end(); + LiveRange::const_iterator RegPos = Range.begin(); + LiveRange::const_iterator RegEnd = Range.end(); SegmentIter SegPos = Segments.find(RegPos->start); for (;;) { @@ -69,7 +70,7 @@ void LiveIntervalUnion::extract(LiveInterval &VirtReg) { return; // Skip all segments that may have been coalesced. - RegPos = VirtReg.advanceTo(RegPos, SegPos.start()); + RegPos = Range.advanceTo(RegPos, SegPos.start()); if (RegPos == RegEnd) return; @@ -79,7 +80,6 @@ void LiveIntervalUnion::extract(LiveInterval &VirtReg) { void LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { - OS << "LIU " << PrintReg(RepReg, TRI); if (empty()) { OS << " empty\n"; return; @@ -99,88 +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(InterferenceResult &IR) const { - // Search until reaching the end of the LiveUnion segments. - LiveInterval::iterator VirtRegEnd = VirtReg->end(); - if (IR.VirtRegI == VirtRegEnd) - return; - while (IR.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) - break; // Retain current (nonoverlapping) LiveUnionI - - // VirtRegI may have advanced far beyond LiveUnionI, catch up. - IR.LiveUnionI.advanceTo(IR.VirtRegI->start); - - // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end - if (!IR.LiveUnionI.valid()) - break; - if (IR.LiveUnionI.start() < IR.VirtRegI->end) { - assert(overlap(*IR.VirtRegI, IR.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; -} - // Scan the vector of interfering virtual registers in this union. Assume it's // quite small. bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { @@ -189,94 +107,99 @@ 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) { - 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(); - LiveInterval::iterator VirtRegEnd = VirtReg->end(); - LiveInterval *RecentInterferingVReg = NULL; - if (IR.VirtRegI != VirtRegEnd) while (IR.LiveUnionI.valid()) { - // Advance the union's iterator to reach an unseen interfering vreg. - do { - if (IR.LiveUnionI.value() == RecentInterferingVReg) - continue; - - if (!isSeenInterference(IR.LiveUnionI.value())) - break; - - // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = IR.LiveUnionI.value(); - } while ((++IR.LiveUnionI).valid()); - if (!IR.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) - break; + // Set up iterators on the first call. + if (!CheckedFirstInterference) { + CheckedFirstInterference = true; - // Check for intersection with the union's segment. - if (overlap(*IR.VirtRegI, IR.LiveUnionI)) { + // Quickly skip interference check for empty sets. + if (VirtReg->empty() || LiveUnion->empty()) { + SeenAllInterferences = true; + return 0; + } - if (!IR.LiveUnionI.value()->isSpillable()) - SeenUnspillableVReg = true; + // In most cases, the union will start before VirtReg. + VirtRegI = VirtReg->begin(); + LiveUnionI.setMap(LiveUnion->getMap()); + LiveUnionI.find(VirtRegI->start); + } - if (InterferingVRegs.size() == MaxInterferingRegs) - // Leave SeenAllInterferences set to false to indicate that at least one - // interference exists beyond those we collected. - return MaxInterferingRegs; + LiveInterval::iterator VirtRegEnd = VirtReg->end(); + LiveInterval *RecentReg = nullptr; + 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(); + } + } - InterferingVRegs.push_back(IR.LiveUnionI.value()); + // The iterators are now not overlapping, LiveUnionI has been advanced + // beyond VirtRegI. + assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); - // Cache the most recent interfering vreg to bypass isSeenInterference. - RecentInterferingVReg = IR.LiveUnionI.value(); - ++IR.LiveUnionI; + // Advance the iterator that ends first. + VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); + if (VirtRegI == VirtRegEnd) + break; + // 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" - IR.LiveUnionI.advanceTo(IR.VirtRegI->start); + + // Still not overlapping. Catch up LiveUnionI. + LiveUnionI.advanceTo(VirtRegI->start); } SeenAllInterferences = true; return InterferingVRegs.size(); } -bool LiveIntervalUnion::Query::checkLoopInterference(MachineLoopRange *Loop) { - // VirtReg is likely live throughout the loop, so start by checking LIU-Loop - // overlaps. - IntervalMapOverlaps - Overlaps(LiveUnion->getMap(), Loop->getMap()); - if (!Overlaps.valid()) - return false; - - // The loop is overlapping an LIU assignment. Check VirtReg as well. - LiveInterval::iterator VRI = VirtReg->find(Overlaps.start()); - - for (;;) { - if (VRI == VirtReg->end()) - return false; - if (VRI->start < Overlaps.stop()) - return true; - - Overlaps.advanceTo(VRI->start); - if (!Overlaps.valid()) - return false; - if (Overlaps.start() < VRI->end) - return true; +void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, + unsigned NSize) { + // Reuse existing allocation. + if (NSize == Size) + return; + clear(); + Size = NSize; + LIUs = static_cast( + malloc(sizeof(LiveIntervalUnion)*NSize)); + for (unsigned i = 0; i != Size; ++i) + new(LIUs + i) LiveIntervalUnion(Alloc); +} - VRI = VirtReg->advanceTo(VRI, Overlaps.start()); - } +void LiveIntervalUnion::Array::clear() { + if (!LIUs) + return; + for (unsigned i = 0; i != Size; ++i) + LIUs[i].~LiveIntervalUnion(); + free(LIUs); + Size = 0; + LIUs = nullptr; }