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