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