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