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