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