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