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
  25 // Merge a LiveInterval's segments. Guarantee no overlaps.
  26 void LiveIntervalUnion::unify(LiveInterval &VirtReg) {
  27   if (VirtReg.empty())
  28     return;
  29
  30   // Insert each of the virtual register's live segments into the map.
  31   LiveInterval::iterator RegPos = VirtReg.begin();
  32   LiveInterval::iterator RegEnd = VirtReg.end();
  33   SegmentIter SegPos = Segments.find(RegPos->start);
  34
  35   for (;;) {
  36     SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
  37     if (++RegPos == RegEnd)
  38       return;
  39     SegPos.advanceTo(RegPos->start);
  40   }
  41 }
  42
  43 // Remove a live virtual register's segments from this union.
  44 void LiveIntervalUnion::extract(LiveInterval &VirtReg) {
  45   if (VirtReg.empty())
  46     return;
  47
  48   // Remove each of the virtual register's live segments from the map.
  49   LiveInterval::iterator RegPos = VirtReg.begin();
  50   LiveInterval::iterator RegEnd = VirtReg.end();
  51   SegmentIter SegPos = Segments.find(RegPos->start);
  52
  53   for (;;) {
  54     assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
  55     SegPos.erase();
  56     if (!SegPos.valid())
  57       return;
  58
  59     // Skip all segments that may have been coalesced.
  60     RegPos = VirtReg.advanceTo(RegPos, SegPos.start());
  61     if (RegPos == RegEnd)
  62       return;
  63
  64     SegPos.advanceTo(RegPos->start);
  65   }
  66 }
  67
  68 void
  69 LiveIntervalUnion::print(raw_ostream &OS,
  70                          const AbstractRegisterDescription *RegDesc) const {
  71   OS << "LIU ";
  72   if (RegDesc != NULL)
  73     OS << RegDesc->getName(RepReg);
  74   else {
  75     OS << RepReg;
  76   }
  77   for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI)
  78     dbgs() << " [" << SI.start() << ' ' << SI.stop() << "):%reg"
  79            << SI.value()->reg;
  80   OS << "\n";
  81 }
  82
  83 void LiveIntervalUnion::dump(const AbstractRegisterDescription *RegDesc) const {
  84   print(dbgs(), RegDesc);
  85 }
  86
  87 #ifndef NDEBUG
  88 // Verify the live intervals in this union and add them to the visited set.
  89 void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
  90   for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
  91     VisitedVRegs.set(SI.value()->reg);
  92 }
  93 #endif //!NDEBUG
  94
  95 // Private interface accessed by Query.
  96 //
  97 // Find a pair of segments that intersect, one in the live virtual register
  98 // (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query)
  99 // is responsible for advancing the LiveIntervalUnion segments to find a
 100 // "notable" intersection, which requires query-specific logic.
 101 //
 102 // This design assumes only a fast mechanism for intersecting a single live
 103 // virtual register segment with a set of LiveIntervalUnion segments.  This may
 104 // be ok since most virtual registers have very few segments.  If we had a data
 105 // structure that optimizd MxN intersection of segments, then we would bypass
 106 // the loop that advances within the LiveInterval.
 107 //
 108 // If no intersection exists, set VirtRegI = VirtRegEnd, and set SI to the first
 109 // segment whose start point is greater than LiveInterval's end point.
 110 //
 111 // Assumes that segments are sorted by start position in both
 112 // LiveInterval and LiveSegments.
 113 void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const {
 114   // Search until reaching the end of the LiveUnion segments.
 115   LiveInterval::iterator VirtRegEnd = VirtReg->end();
 116   if (IR.VirtRegI == VirtRegEnd)
 117     return;
 118   while (IR.LiveUnionI.valid()) {
 119     // Slowly advance the live virtual reg iterator until we surpass the next
 120     // segment in LiveUnion.
 121     //
 122     // Note: If this is ever used for coalescing of fixed registers and we have
 123     // a live vreg with thousands of segments, then change this code to use
 124     // upperBound instead.
 125     IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
 126     if (IR.VirtRegI == VirtRegEnd)
 127       break; // Retain current (nonoverlapping) LiveUnionI
 128
 129     // VirtRegI may have advanced far beyond LiveUnionI, catch up.
 130     IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
 131
 132     // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
 133     if (!IR.LiveUnionI.valid())
 134       break;
 135     if (IR.LiveUnionI.start() < IR.VirtRegI->end) {
 136       assert(overlap(*IR.VirtRegI, IR.LiveUnionI) &&
 137              "upperBound postcondition");
 138       break;
 139     }
 140   }
 141   if (!IR.LiveUnionI.valid())
 142     IR.VirtRegI = VirtRegEnd;
 143 }
 144
 145 // Find the first intersection, and cache interference info
 146 // (retain segment iterators into both VirtReg and LiveUnion).
 147 const LiveIntervalUnion::InterferenceResult &
 148 LiveIntervalUnion::Query::firstInterference() {
 149   if (CheckedFirstInterference)
 150     return FirstInterference;
 151   CheckedFirstInterference = true;
 152   InterferenceResult &IR = FirstInterference;
 153
 154   // Quickly skip interference check for empty sets.
 155   if (VirtReg->empty() || LiveUnion->empty()) {
 156     IR.VirtRegI = VirtReg->end();
 157   } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) {
 158     // VirtReg starts first, perform double binary search.
 159     IR.VirtRegI = VirtReg->find(LiveUnion->startIndex());
 160     if (IR.VirtRegI != VirtReg->end())
 161       IR.LiveUnionI = LiveUnion->find(IR.VirtRegI->start);
 162   } else {
 163     // LiveUnion starts first, perform double binary search.
 164     IR.LiveUnionI = LiveUnion->find(VirtReg->beginIndex());
 165     if (IR.LiveUnionI.valid())
 166       IR.VirtRegI = VirtReg->find(IR.LiveUnionI.start());
 167     else
 168       IR.VirtRegI = VirtReg->end();
 169   }
 170   findIntersection(FirstInterference);
 171   assert((IR.VirtRegI == VirtReg->end() || IR.LiveUnionI.valid())
 172          && "Uninitialized iterator");
 173   return FirstInterference;
 174 }
 175
 176 // Treat the result as an iterator and advance to the next interfering pair
 177 // of segments. This is a plain iterator with no filter.
 178 bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const {
 179   assert(isInterference(IR) && "iteration past end of interferences");
 180
 181   // Advance either the VirtReg or LiveUnion segment to ensure that we visit all
 182   // unique overlapping pairs.
 183   if (IR.VirtRegI->end < IR.LiveUnionI.stop()) {
 184     if (++IR.VirtRegI == VirtReg->end())
 185       return false;
 186   }
 187   else {
 188     if (!(++IR.LiveUnionI).valid()) {
 189       IR.VirtRegI = VirtReg->end();
 190       return false;
 191     }
 192   }
 193   // Short-circuit findIntersection() if possible.
 194   if (overlap(*IR.VirtRegI, IR.LiveUnionI))
 195     return true;
 196
 197   // Find the next intersection.
 198   findIntersection(IR);
 199   return isInterference(IR);
 200 }
 201
 202 // Scan the vector of interfering virtual registers in this union. Assume it's
 203 // quite small.
 204 bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
 205   SmallVectorImpl<LiveInterval*>::const_iterator I =
 206     std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
 207   return I != InterferingVRegs.end();
 208 }
 209
 210 // Count the number of virtual registers in this union that interfere with this
 211 // query's live virtual register.
 212 //
 213 // The number of times that we either advance IR.VirtRegI or call
 214 // LiveUnion.upperBound() will be no more than the number of holes in
 215 // VirtReg. So each invocation of collectInterferingVRegs() takes
 216 // time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()).
 217 //
 218 // For comments on how to speed it up, see Query::findIntersection().
 219 unsigned LiveIntervalUnion::Query::
 220 collectInterferingVRegs(unsigned MaxInterferingRegs) {
 221   InterferenceResult IR = firstInterference();
 222   LiveInterval::iterator VirtRegEnd = VirtReg->end();
 223   LiveInterval *RecentInterferingVReg = NULL;
 224   while (IR.LiveUnionI.valid()) {
 225     // Advance the union's iterator to reach an unseen interfering vreg.
 226     do {
 227       if (IR.LiveUnionI.value() == RecentInterferingVReg)
 228         continue;
 229
 230       if (!isSeenInterference(IR.LiveUnionI.value()))
 231         break;
 232
 233       // Cache the most recent interfering vreg to bypass isSeenInterference.
 234       RecentInterferingVReg = IR.LiveUnionI.value();
 235
 236     } while ((++IR.LiveUnionI).valid());
 237     if (!IR.LiveUnionI.valid())
 238       break;
 239
 240     // Advance the VirtReg iterator until surpassing the next segment in
 241     // LiveUnion.
 242     IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
 243     if (IR.VirtRegI == VirtRegEnd)
 244       break;
 245
 246     // Check for intersection with the union's segment.
 247     if (overlap(*IR.VirtRegI, IR.LiveUnionI)) {
 248
 249       if (!IR.LiveUnionI.value()->isSpillable())
 250         SeenUnspillableVReg = true;
 251
 252       if (InterferingVRegs.size() == MaxInterferingRegs)
 253         // Leave SeenAllInterferences set to false to indicate that at least one
 254         // interference exists beyond those we collected.
 255         return MaxInterferingRegs;
 256
 257       InterferingVRegs.push_back(IR.LiveUnionI.value());
 258
 259       // Cache the most recent interfering vreg to bypass isSeenInterference.
 260       RecentInterferingVReg = IR.LiveUnionI.value();
 261       ++IR.LiveUnionI;
 262       continue;
 263     }
 264     // VirtRegI may have advanced far beyond LiveUnionI,
 265     // do a fast intersection test to "catch up"
 266     IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
 267   }
 268   SeenAllInterferences = true;
 269   return InterferingVRegs.size();
 270 }