X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.cpp;h=025d99ce78812c8f42a003a1cda8b9d206b56b97;hb=28fbb4be5df108cf72a99b73c7c99ded16f3b82f;hp=3da201e0ccf9be508be69f68194edd9ce3630f6a;hpb=18c57a8a09a7c79fbcf4348b0ad8135246ab984f;p=oota-llvm.git

diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index 3da201e0ccf..025d99ce788 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -13,233 +13,92 @@
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "regalloc"
-#include "LiveIntervalUnion.h"
+#include "llvm/CodeGen/LiveIntervalUnion.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 #include <algorithm>
+
 using namespace llvm;
 
-// Find the first segment in the range [SegBegin,Segments.end()) that
-// intersects with LS. If no intersection is found, return the first SI
-// such that SI.start >= LS.End.
-//
-// This logic is tied to the underlying LiveSegments data structure. For now, we
-// use set::upper_bound to find the nearest starting position,
-// then reverse iterate to find the first overlap.
-//
-// Upon entry we have SegBegin.Start < LS.End
-// SegBegin   |--...
-//             \   .
-//       LS ...-|
-//
-// After set::upper_bound, we have SI.start >= LS.start:
-// SI   |--...
-//     /
-// LS |--...
-//
-// Assuming intervals are disjoint, if an intersection exists, it must be the
-// segment found or the one immediately preceeding it. We continue reverse
-// iterating to return the first overlapping segment.
-LiveIntervalUnion::SegmentIter
-LiveIntervalUnion::upperBound(SegmentIter SegBegin,
-                              const LiveSegment &LS) {
-  assert(LS.End > SegBegin->Start && "segment iterator precondition");
+#define DEBUG_TYPE "regalloc"
 
-  // Get the next LIU segment such that segI->Start is not less than seg.Start
-  //
-  // FIXME: Once we have a B+tree, we can make good use of SegBegin as a hint to
-  // upper_bound. For now, we're forced to search again from the root each time.
-  SegmentIter SI = Segments.upper_bound(LS);
-  while (SI != SegBegin) {
-    --SI;
-    if (LS.Start >= SI->End)
-      return ++SI;
-  }
-  return SI;
-}
 
 // Merge a LiveInterval's segments. Guarantee no overlaps.
-//
-// After implementing B+tree, segments will be coalesced.
-void LiveIntervalUnion::unify(LiveInterval &VirtReg) {
+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.
-  SegmentIter SegPos = Segments.begin();
-  for (LiveInterval::iterator VirtRegI = VirtReg.begin(),
-         VirtRegEnd = VirtReg.end();
-       VirtRegI != VirtRegEnd; ++VirtRegI ) {
-
-    LiveSegment Seg(*VirtRegI, &VirtReg);
-    SegPos = Segments.insert(SegPos, Seg);
-
-    assert(*SegPos == Seg && "need equal val for equal key");
-#ifndef NDEBUG
-    // Check for overlap (inductively).
-    if (SegPos != Segments.begin()) {
-      assert(llvm::prior(SegPos)->End <= Seg.Start && "overlapping segments" );
-    }
-    SegmentIter NextPos = llvm::next(SegPos);
-    if (NextPos != Segments.end())
-      assert(Seg.End <= NextPos->Start && "overlapping segments" );
-#endif // NDEBUG
+  LiveRange::const_iterator RegPos = Range.begin();
+  LiveRange::const_iterator RegEnd = Range.end();
+  SegmentIter SegPos = Segments.find(RegPos->start);
+
+  while (SegPos.valid()) {
+    SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
+    if (++RegPos == RegEnd)
+      return;
+    SegPos.advanceTo(RegPos->start);
   }
+
+  // We have reached the end of Segments, so it is no longer necessary to search
+  // for the insertion position.
+  // It is faster to insert the end first.
+  --RegEnd;
+  SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg);
+  for (; RegPos != RegEnd; ++RegPos, ++SegPos)
+    SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
 }
 
 // Remove a live virtual register's segments from this union.
-void LiveIntervalUnion::extract(const LiveInterval &VirtReg) {
+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.
-  SegmentIter SegPos = Segments.begin();
-  for (LiveInterval::const_iterator VirtRegI = VirtReg.begin(),
-         VirtRegEnd = VirtReg.end();
-       VirtRegI != VirtRegEnd; ++VirtRegI) {
-
-    LiveSegment Seg(*VirtRegI, const_cast<LiveInterval*>(&VirtReg));
-    SegPos = upperBound(SegPos, Seg);
-    assert(SegPos != Segments.end() && "missing VirtReg segment");
-
-    Segments.erase(SegPos++);
+  LiveRange::const_iterator RegPos = Range.begin();
+  LiveRange::const_iterator RegEnd = Range.end();
+  SegmentIter SegPos = Segments.find(RegPos->start);
+
+  for (;;) {
+    assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
+    SegPos.erase();
+    if (!SegPos.valid())
+      return;
+
+    // Skip all segments that may have been coalesced.
+    RegPos = Range.advanceTo(RegPos, SegPos.start());
+    if (RegPos == RegEnd)
+      return;
+
+    SegPos.advanceTo(RegPos->start);
   }
 }
 
-raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveSegment &LS) {
-  return OS << '[' << LS.Start << ',' << LS.End << ':' <<
-    LS.VirtReg->reg << ")";
-}
-
-void LiveSegment::dump() const {
-  dbgs() << *this << "\n";
-}
-
 void
-LiveIntervalUnion::print(raw_ostream &OS,
-                         const AbstractRegisterDescription *RegDesc) const {
-  OS << "LIU ";
-  if (RegDesc != NULL)
-    OS << RegDesc->getName(RepReg);
-  else {
-    OS << RepReg;
+LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
+  if (empty()) {
+    OS << " empty\n";
+    return;
   }
-  for (LiveSegments::const_iterator SI = Segments.begin(),
-         SegEnd = Segments.end(); SI != SegEnd; ++SI) {
-    dbgs() << " " << *SI;
+  for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
+    OS << " [" << SI.start() << ' ' << SI.stop() << "):"
+       << PrintReg(SI.value()->reg, TRI);
   }
-  OS << "\n";
-}
-
-void LiveIntervalUnion::dump(const AbstractRegisterDescription *RegDesc) const {
-  print(dbgs(), RegDesc);
+  OS << '\n';
 }
 
 #ifndef NDEBUG
 // Verify the live intervals in this union and add them to the visited set.
 void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
-  SegmentIter SI = Segments.begin();
-  SegmentIter SegEnd = Segments.end();
-  if (SI == SegEnd) return;
-  VisitedVRegs.set(SI->VirtReg->reg);
-  for (++SI; SI != SegEnd; ++SI) {
-    VisitedVRegs.set(SI->VirtReg->reg);
-    assert(llvm::prior(SI)->End <= SI->Start && "overlapping segments" );
-  }
+  for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
+    VisitedVRegs.set(SI.value()->reg);
 }
 #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 VIRTREGs 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();
-  SegmentIter LiveUnionEnd = LiveUnion->end();
-  while (IR.LiveUnionI != LiveUnionEnd) {
-
-    // 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.
-    while (IR.VirtRegI != VirtRegEnd &&
-           IR.VirtRegI->end <= IR.LiveUnionI->Start)
-      ++IR.VirtRegI;
-    if (IR.VirtRegI == VirtRegEnd)
-      break; // Retain current (nonoverlapping) LiveUnionI
-
-    // VirtRegI may have advanced far beyond LiveUnionI,
-    // do a fast intersection test to "catch up"
-    LiveSegment Seg(*IR.VirtRegI, VirtReg);
-    IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
-
-    // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
-    if (IR.LiveUnionI == LiveUnionEnd)
-      break;
-    if (IR.LiveUnionI->Start < IR.VirtRegI->end) {
-      assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
-             "upperBound postcondition");
-      break;
-    }
-  }
-  if (IR.LiveUnionI == LiveUnionEnd)
-    IR.VirtRegI = VirtRegEnd;
-}
-
-// Find the first intersection, and cache interference info
-// (retain segment iterators into both VirtReg and LiveUnion).
-LiveIntervalUnion::InterferenceResult
-LiveIntervalUnion::Query::firstInterference() {
-  if (FirstInterference != LiveIntervalUnion::InterferenceResult()) {
-    return FirstInterference;
-  }
-  FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->begin());
-  findIntersection(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->End) {
-    if (++IR.VirtRegI == VirtReg->end())
-      return false;
-  }
-  else {
-    if (++IR.LiveUnionI == LiveUnion->end()) {
-      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 {
@@ -248,69 +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) {
-  InterferenceResult IR = firstInterference();
-  LiveInterval::iterator VirtRegEnd = VirtReg->end();
-  SegmentIter LiveUnionEnd = LiveUnion->end();
-  LiveInterval *RecentInterferingVReg = NULL;
-  while (IR.LiveUnionI != LiveUnionEnd) {
-    // Advance the union's iterator to reach an unseen interfering vreg.
-    do {
-      if (IR.LiveUnionI->VirtReg == RecentInterferingVReg)
-        continue;
+  // Fast path return if we already have the desired information.
+  if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
+    return InterferingVRegs.size();
+
+  // Set up iterators on the first call.
+  if (!CheckedFirstInterference) {
+    CheckedFirstInterference = true;
+
+    // Quickly skip interference check for empty sets.
+    if (VirtReg->empty() || LiveUnion->empty()) {
+      SeenAllInterferences = true;
+      return 0;
+    }
 
-      if (!isSeenInterference(IR.LiveUnionI->VirtReg))
-        break;
+    // In most cases, the union will start before VirtReg.
+    VirtRegI = VirtReg->begin();
+    LiveUnionI.setMap(LiveUnion->getMap());
+    LiveUnionI.find(VirtRegI->start);
+  }
 
-      // Cache the most recent interfering vreg to bypass isSeenInterference.
-      RecentInterferingVReg = IR.LiveUnionI->VirtReg;
+  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();
+      }
+    }
 
-    } while( ++IR.LiveUnionI != LiveUnionEnd);
-    if (IR.LiveUnionI == LiveUnionEnd)
-      break;
+    // The iterators are now not overlapping, LiveUnionI has been advanced
+    // beyond VirtRegI.
+    assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap");
 
-    // Advance the VirtReg iterator until surpassing the next segment in
-    // LiveUnion.
-    //
-    // Note: If this is ever used for coalescing of fixed registers and we have
-    // a live virtual register with thousands of segments, then use upperBound
-    // instead.
-    while (IR.VirtRegI != VirtRegEnd &&
-           IR.VirtRegI->end <= IR.LiveUnionI->Start)
-      ++IR.VirtRegI;
-    if (IR.VirtRegI == VirtRegEnd)
+    // 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(*IR.VirtRegI, *IR.LiveUnionI)) {
-
-      if (!IR.LiveUnionI->VirtReg->isSpillable())
-        SeenUnspillableVReg = true;
-
-      InterferingVRegs.push_back(IR.LiveUnionI->VirtReg);
-      if (InterferingVRegs.size() == MaxInterferingRegs)
-        return MaxInterferingRegs;
-
-      // Cache the most recent interfering vreg to bypass isSeenInterference.
-      RecentInterferingVReg = IR.LiveUnionI->VirtReg;
-      ++IR.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"
-    LiveSegment Seg(*IR.VirtRegI, VirtReg);
-    IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
+
+    // Still not overlapping. Catch up LiveUnionI.
+    LiveUnionI.advanceTo(VirtRegI->start);
   }
   SeenAllInterferences = true;
   return InterferingVRegs.size();
 }
+
+void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc,
+                                    unsigned NSize) {
+  // Reuse existing allocation.
+  if (NSize == Size)
+    return;
+  clear();
+  Size = NSize;
+  LIUs = static_cast<LiveIntervalUnion*>(
+    malloc(sizeof(LiveIntervalUnion)*NSize));
+  for (unsigned i = 0; i != Size; ++i)
+    new(LIUs + i) LiveIntervalUnion(Alloc);
+}
+
+void LiveIntervalUnion::Array::clear() {
+  if (!LIUs)
+    return;
+  for (unsigned i = 0; i != Size; ++i)
+    LIUs[i].~LiveIntervalUnion();
+  free(LIUs);
+  Size =  0;
+  LIUs = nullptr;
+}