lib/CodeGen/LiveIntervalUnion.cpp

   1 //===-- LiveIntervalUnion.cpp - Live interval union data structure --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // LiveIntervalUnion represents a coalesced set of live intervals. This may be
  11 // used during coalescing to represent a congruence class, or during register
  12 // allocation to model liveness of a physical register.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "regalloc"
  17 #include "LiveIntervalUnion.h"
  18 #include "llvm/ADT/SparseBitVector.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include <algorithm>
  22 using namespace llvm;
  23
  24 // Find the first segment in the range [SegBegin,Segments.end()) that
  25 // intersects with LS. If no intersection is found, return the first SI
  26 // such that SI.start >= LS.End.
  27 //
  28 // This logic is tied to the underlying LiveSegments data structure. For now, we
  29 // use set::upper_bound to find the nearest starting position,
  30 // then reverse iterate to find the first overlap.
  31 //
  32 // Upon entry we have SegBegin.Start < LS.End
  33 // SegBegin   |--...
  34 //             \   .
  35 //       LS ...-|
  36 //
  37 // After set::upper_bound, we have SI.start >= LS.start:
  38 // SI   |--...
  39 //     /
  40 // LS |--...
  41 //
  42 // Assuming intervals are disjoint, if an intersection exists, it must be the
  43 // segment found or the one immediately preceeding it. We continue reverse
  44 // iterating to return the first overlapping segment.
  45 LiveIntervalUnion::SegmentIter
  46 LiveIntervalUnion::upperBound(SegmentIter SegBegin,
  47                               const LiveSegment &LS) {
  48   assert(LS.End > SegBegin->Start && "segment iterator precondition");
  49
  50   // Get the next LIU segment such that segI->Start is not less than seg.Start
  51   //
  52   // FIXME: Once we have a B+tree, we can make good use of SegBegin as a hint to
  53   // upper_bound. For now, we're forced to search again from the root each time.
  54   SegmentIter SI = Segments.upper_bound(LS);
  55   while (SI != SegBegin) {
  56     --SI;
  57     if (LS.Start >= SI->End)
  58       return ++SI;
  59   }
  60   return SI;
  61 }
  62
  63 // Merge a LiveInterval's segments. Guarantee no overlaps.
  64 //
  65 // After implementing B+tree, segments will be coalesced.
  66 void LiveIntervalUnion::unify(LiveInterval &VirtReg) {
  67
  68   // Insert each of the virtual register's live segments into the map.
  69   SegmentIter SegPos = Segments.begin();
  70   for (LiveInterval::iterator VirtRegI = VirtReg.begin(),
  71          VirtRegEnd = VirtReg.end();
  72        VirtRegI != VirtRegEnd; ++VirtRegI ) {
  73
  74     LiveSegment Seg(*VirtRegI, &VirtReg);
  75     SegPos = Segments.insert(SegPos, Seg);
  76
  77     assert(*SegPos == Seg && "need equal val for equal key");
  78 #ifndef NDEBUG
  79     // Check for overlap (inductively).
  80     if (SegPos != Segments.begin()) {
  81       assert(llvm::prior(SegPos)->End <= Seg.Start && "overlapping segments" );
  82     }
  83     SegmentIter NextPos = llvm::next(SegPos);
  84     if (NextPos != Segments.end())
  85       assert(Seg.End <= NextPos->Start && "overlapping segments" );
  86 #endif // NDEBUG
  87   }
  88 }
  89
  90 // Remove a live virtual register's segments from this union.
  91 void LiveIntervalUnion::extract(const LiveInterval &VirtReg) {
  92
  93   // Remove each of the virtual register's live segments from the map.
  94   SegmentIter SegPos = Segments.begin();
  95   for (LiveInterval::const_iterator VirtRegI = VirtReg.begin(),
  96          VirtRegEnd = VirtReg.end();
  97        VirtRegI != VirtRegEnd; ++VirtRegI) {
  98
  99     LiveSegment Seg(*VirtRegI, const_cast<LiveInterval*>(&VirtReg));
 100     SegPos = upperBound(SegPos, Seg);
 101     assert(SegPos != Segments.end() && "missing VirtReg segment");
 102
 103     Segments.erase(SegPos++);
 104   }
 105 }
 106
 107 raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveSegment &LS) {
 108   return OS << '[' << LS.Start << ',' << LS.End << ':' <<
 109     LS.VirtReg->reg << ")";
 110 }
 111
 112 void LiveSegment::dump() const {
 113   dbgs() << *this << "\n";
 114 }
 115
 116 void
 117 LiveIntervalUnion::print(raw_ostream &OS,
 118                          const AbstractRegisterDescription *RegDesc) const {
 119   OS << "LIU ";
 120   if (RegDesc != NULL)
 121     OS << RegDesc->getName(RepReg);
 122   else {
 123     OS << RepReg;
 124   }
 125   for (LiveSegments::const_iterator SI = Segments.begin(),
 126          SegEnd = Segments.end(); SI != SegEnd; ++SI) {
 127     dbgs() << " " << *SI;
 128   }
 129   OS << "\n";
 130 }
 131
 132 void LiveIntervalUnion::dump(const AbstractRegisterDescription *RegDesc) const {
 133   print(dbgs(), RegDesc);
 134 }
 135
 136 #ifndef NDEBUG
 137 // Verify the live intervals in this union and add them to the visited set.
 138 void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
 139   SegmentIter SI = Segments.begin();
 140   SegmentIter SegEnd = Segments.end();
 141   if (SI == SegEnd) return;
 142   VisitedVRegs.set(SI->VirtReg->reg);
 143   for (++SI; SI != SegEnd; ++SI) {
 144     VisitedVRegs.set(SI->VirtReg->reg);
 145     assert(llvm::prior(SI)->End <= SI->Start && "overlapping segments" );
 146   }
 147 }
 148 #endif //!NDEBUG
 149
 150 // Private interface accessed by Query.
 151 //
 152 // Find a pair of segments that intersect, one in the live virtual register
 153 // (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query)
 154 // is responsible for advancing the LiveIntervalUnion segments to find a
 155 // "notable" intersection, which requires query-specific logic.
 156 //
 157 // This design assumes only a fast mechanism for intersecting a single live
 158 // virtual register segment with a set of LiveIntervalUnion segments.  This may
 159 // be ok since most virtual registers have very few segments.  If we had a data
 160 // structure that optimizd MxN intersection of segments, then we would bypass
 161 // the loop that advances within the LiveInterval.
 162 //
 163 // If no intersection exists, set VirtRegI = VirtRegEnd, and set SI to the first
 164 // segment whose start point is greater than LiveInterval's end point.
 165 //
 166 // Assumes that segments are sorted by start position in both
 167 // LiveInterval and LiveSegments.
 168 void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const {
 169
 170   // Search until reaching the end of the LiveUnion segments.
 171   LiveInterval::iterator VirtRegEnd = VirtReg->end();
 172   SegmentIter LiveUnionEnd = LiveUnion->end();
 173   while (IR.LiveUnionI != LiveUnionEnd) {
 174
 175     // Slowly advance the live virtual reg iterator until we surpass the next
 176     // segment in LiveUnion.
 177     //
 178     // Note: If this is ever used for coalescing of fixed registers and we have
 179     // a live vreg with thousands of segments, then change this code to use
 180     // upperBound instead.
 181     while (IR.VirtRegI != VirtRegEnd &&
 182            IR.VirtRegI->end <= IR.LiveUnionI->Start)
 183       ++IR.VirtRegI;
 184     if (IR.VirtRegI == VirtRegEnd)
 185       break; // Retain current (nonoverlapping) LiveUnionI
 186
 187     // VirtRegI may have advanced far beyond LiveUnionI,
 188     // do a fast intersection test to "catch up"
 189     LiveSegment Seg(*IR.VirtRegI, VirtReg);
 190     IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
 191
 192     // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
 193     if (IR.LiveUnionI == LiveUnionEnd)
 194       break;
 195     if (IR.LiveUnionI->Start < IR.VirtRegI->end) {
 196       assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) &&
 197              "upperBound postcondition");
 198       break;
 199     }
 200   }
 201   if (IR.LiveUnionI == LiveUnionEnd)
 202     IR.VirtRegI = VirtRegEnd;
 203 }
 204
 205 // Find the first intersection, and cache interference info
 206 // (retain segment iterators into both VirtReg and LiveUnion).
 207 LiveIntervalUnion::InterferenceResult
 208 LiveIntervalUnion::Query::firstInterference() {
 209   if (FirstInterference != LiveIntervalUnion::InterferenceResult()) {
 210     return FirstInterference;
 211   }
 212   FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->begin());
 213   findIntersection(FirstInterference);
 214   return FirstInterference;
 215 }
 216
 217 // Treat the result as an iterator and advance to the next interfering pair
 218 // of segments. This is a plain iterator with no filter.
 219 bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const {
 220   assert(isInterference(IR) && "iteration past end of interferences");
 221
 222   // Advance either the VirtReg or LiveUnion segment to ensure that we visit all
 223   // unique overlapping pairs.
 224   if (IR.VirtRegI->end < IR.LiveUnionI->End) {
 225     if (++IR.VirtRegI == VirtReg->end())
 226       return false;
 227   }
 228   else {
 229     if (++IR.LiveUnionI == LiveUnion->end()) {
 230       IR.VirtRegI = VirtReg->end();
 231       return false;
 232     }
 233   }
 234   // Short-circuit findIntersection() if possible.
 235   if (overlap(*IR.VirtRegI, *IR.LiveUnionI))
 236     return true;
 237
 238   // Find the next intersection.
 239   findIntersection(IR);
 240   return isInterference(IR);
 241 }
 242
 243 // Scan the vector of interfering virtual registers in this union. Assume it's
 244 // quite small.
 245 bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
 246   SmallVectorImpl<LiveInterval*>::const_iterator I =
 247     std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
 248   return I != InterferingVRegs.end();
 249 }
 250
 251 // Count the number of virtual registers in this union that interfere with this
 252 // query's live virtual register.
 253 //
 254 // The number of times that we either advance IR.VirtRegI or call
 255 // LiveUnion.upperBound() will be no more than the number of holes in
 256 // VirtReg. So each invocation of collectInterferingVRegs() takes
 257 // time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()).
 258 //
 259 // For comments on how to speed it up, see Query::findIntersection().
 260 unsigned LiveIntervalUnion::Query::
 261 collectInterferingVRegs(unsigned MaxInterferingRegs) {
 262   InterferenceResult IR = firstInterference();
 263   LiveInterval::iterator VirtRegEnd = VirtReg->end();
 264   SegmentIter LiveUnionEnd = LiveUnion->end();
 265   LiveInterval *RecentInterferingVReg = NULL;
 266   while (IR.LiveUnionI != LiveUnionEnd) {
 267     // Advance the union's iterator to reach an unseen interfering vreg.
 268     do {
 269       if (IR.LiveUnionI->VirtReg == RecentInterferingVReg)
 270         continue;
 271
 272       if (!isSeenInterference(IR.LiveUnionI->VirtReg))
 273         break;
 274
 275       // Cache the most recent interfering vreg to bypass isSeenInterference.
 276       RecentInterferingVReg = IR.LiveUnionI->VirtReg;
 277
 278     } while( ++IR.LiveUnionI != LiveUnionEnd);
 279     if (IR.LiveUnionI == LiveUnionEnd)
 280       break;
 281
 282     // Advance the VirtReg iterator until surpassing the next segment in
 283     // LiveUnion.
 284     //
 285     // Note: If this is ever used for coalescing of fixed registers and we have
 286     // a live virtual register with thousands of segments, then use upperBound
 287     // instead.
 288     while (IR.VirtRegI != VirtRegEnd &&
 289            IR.VirtRegI->end <= IR.LiveUnionI->Start)
 290       ++IR.VirtRegI;
 291     if (IR.VirtRegI == VirtRegEnd)
 292       break;
 293
 294     // Check for intersection with the union's segment.
 295     if (overlap(*IR.VirtRegI, *IR.LiveUnionI)) {
 296
 297       if (!IR.LiveUnionI->VirtReg->isSpillable())
 298         SeenUnspillableVReg = true;
 299
 300       InterferingVRegs.push_back(IR.LiveUnionI->VirtReg);
 301       if (InterferingVRegs.size() == MaxInterferingRegs)
 302         return MaxInterferingRegs;
 303
 304       // Cache the most recent interfering vreg to bypass isSeenInterference.
 305       RecentInterferingVReg = IR.LiveUnionI->VirtReg;
 306       ++IR.LiveUnionI;
 307       continue;
 308     }
 309     // VirtRegI may have advanced far beyond LiveUnionI,
 310     // do a fast intersection test to "catch up"
 311     LiveSegment Seg(*IR.VirtRegI, VirtReg);
 312     IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg);
 313   }
 314   SeenAllInterferences = true;
 315   return InterferingVRegs.size();
 316 }