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