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   return FirstInterference;
 172 }
 173
 174 // Treat the result as an iterator and advance to the next interfering pair
 175 // of segments. This is a plain iterator with no filter.
 176 bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const {
 177   assert(isInterference(IR) && "iteration past end of interferences");
 178
 179   // Advance either the VirtReg or LiveUnion segment to ensure that we visit all
 180   // unique overlapping pairs.
 181   if (IR.VirtRegI->end < IR.LiveUnionI.stop()) {
 182     if (++IR.VirtRegI == VirtReg->end())
 183       return false;
 184   }
 185   else {
 186     if (!(++IR.LiveUnionI).valid()) {
 187       IR.VirtRegI = VirtReg->end();
 188       return false;
 189     }
 190   }
 191   // Short-circuit findIntersection() if possible.
 192   if (overlap(*IR.VirtRegI, IR.LiveUnionI))
 193     return true;
 194
 195   // Find the next intersection.
 196   findIntersection(IR);
 197   return isInterference(IR);
 198 }
 199
 200 // Scan the vector of interfering virtual registers in this union. Assume it's
 201 // quite small.
 202 bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
 203   SmallVectorImpl<LiveInterval*>::const_iterator I =
 204     std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
 205   return I != InterferingVRegs.end();
 206 }
 207
 208 // Count the number of virtual registers in this union that interfere with this
 209 // query's live virtual register.
 210 //
 211 // The number of times that we either advance IR.VirtRegI or call
 212 // LiveUnion.upperBound() will be no more than the number of holes in
 213 // VirtReg. So each invocation of collectInterferingVRegs() takes
 214 // time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()).
 215 //
 216 // For comments on how to speed it up, see Query::findIntersection().
 217 unsigned LiveIntervalUnion::Query::
 218 collectInterferingVRegs(unsigned MaxInterferingRegs) {
 219   InterferenceResult IR = firstInterference();
 220   LiveInterval::iterator VirtRegEnd = VirtReg->end();
 221   LiveInterval *RecentInterferingVReg = NULL;
 222   while (IR.LiveUnionI.valid()) {
 223     // Advance the union's iterator to reach an unseen interfering vreg.
 224     do {
 225       if (IR.LiveUnionI.value() == RecentInterferingVReg)
 226         continue;
 227
 228       if (!isSeenInterference(IR.LiveUnionI.value()))
 229         break;
 230
 231       // Cache the most recent interfering vreg to bypass isSeenInterference.
 232       RecentInterferingVReg = IR.LiveUnionI.value();
 233
 234     } while ((++IR.LiveUnionI).valid());
 235     if (!IR.LiveUnionI.valid())
 236       break;
 237
 238     // Advance the VirtReg iterator until surpassing the next segment in
 239     // LiveUnion.
 240     IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
 241     if (IR.VirtRegI == VirtRegEnd)
 242       break;
 243
 244     // Check for intersection with the union's segment.
 245     if (overlap(*IR.VirtRegI, IR.LiveUnionI)) {
 246
 247       if (!IR.LiveUnionI.value()->isSpillable())
 248         SeenUnspillableVReg = true;
 249
 250       if (InterferingVRegs.size() == MaxInterferingRegs)
 251         // Leave SeenAllInterferences set to false to indicate that at least one
 252         // interference exists beyond those we collected.
 253         return MaxInterferingRegs;
 254
 255       InterferingVRegs.push_back(IR.LiveUnionI.value());
 256
 257       // Cache the most recent interfering vreg to bypass isSeenInterference.
 258       RecentInterferingVReg = IR.LiveUnionI.value();
 259       ++IR.LiveUnionI;
 260       continue;
 261     }
 262     // VirtRegI may have advanced far beyond LiveUnionI,
 263     // do a fast intersection test to "catch up"
 264     IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
 265   }
 266   SeenAllInterferences = true;
 267   return InterferingVRegs.size();
 268 }