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