LiveIntervalUnion.cpp revision 953af2c3c560a13bd5eeb676c128b7e362dca684
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 115 // Search until reaching the end of the LiveUnion segments. 116 LiveInterval::iterator VirtRegEnd = VirtReg->end(); 117 while (IR.LiveUnionI.valid()) { 118 // Slowly advance the live virtual reg iterator until we surpass the next 119 // segment in LiveUnion. 120 // 121 // Note: If this is ever used for coalescing of fixed registers and we have 122 // a live vreg with thousands of segments, then change this code to use 123 // upperBound instead. 124 IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start()); 125 if (IR.VirtRegI == VirtRegEnd) 126 break; // Retain current (nonoverlapping) LiveUnionI 127 128 // VirtRegI may have advanced far beyond LiveUnionI, catch up. 129 IR.LiveUnionI.advanceTo(IR.VirtRegI->start); 130 131 // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end 132 if (!IR.LiveUnionI.valid()) 133 break; 134 if (IR.LiveUnionI.start() < IR.VirtRegI->end) { 135 assert(overlap(*IR.VirtRegI, IR.LiveUnionI) && 136 "upperBound postcondition"); 137 break; 138 } 139 } 140 if (!IR.LiveUnionI.valid()) 141 IR.VirtRegI = VirtRegEnd; 142} 143 144// Find the first intersection, and cache interference info 145// (retain segment iterators into both VirtReg and LiveUnion). 146LiveIntervalUnion::InterferenceResult 147LiveIntervalUnion::Query::firstInterference() { 148 if (FirstInterference != LiveIntervalUnion::InterferenceResult()) { 149 return FirstInterference; 150 } 151 FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->begin()); 152 findIntersection(FirstInterference); 153 return FirstInterference; 154} 155 156// Treat the result as an iterator and advance to the next interfering pair 157// of segments. This is a plain iterator with no filter. 158bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const { 159 assert(isInterference(IR) && "iteration past end of interferences"); 160 161 // Advance either the VirtReg or LiveUnion segment to ensure that we visit all 162 // unique overlapping pairs. 163 if (IR.VirtRegI->end < IR.LiveUnionI.stop()) { 164 if (++IR.VirtRegI == VirtReg->end()) 165 return false; 166 } 167 else { 168 if (!(++IR.LiveUnionI).valid()) { 169 IR.VirtRegI = VirtReg->end(); 170 return false; 171 } 172 } 173 // Short-circuit findIntersection() if possible. 174 if (overlap(*IR.VirtRegI, IR.LiveUnionI)) 175 return true; 176 177 // Find the next intersection. 178 findIntersection(IR); 179 return isInterference(IR); 180} 181 182// Scan the vector of interfering virtual registers in this union. Assume it's 183// quite small. 184bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { 185 SmallVectorImpl<LiveInterval*>::const_iterator I = 186 std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); 187 return I != InterferingVRegs.end(); 188} 189 190// Count the number of virtual registers in this union that interfere with this 191// query's live virtual register. 192// 193// The number of times that we either advance IR.VirtRegI or call 194// LiveUnion.upperBound() will be no more than the number of holes in 195// VirtReg. So each invocation of collectInterferingVRegs() takes 196// time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()). 197// 198// For comments on how to speed it up, see Query::findIntersection(). 199unsigned LiveIntervalUnion::Query:: 200collectInterferingVRegs(unsigned MaxInterferingRegs) { 201 InterferenceResult IR = firstInterference(); 202 LiveInterval::iterator VirtRegEnd = VirtReg->end(); 203 LiveInterval *RecentInterferingVReg = NULL; 204 while (IR.LiveUnionI.valid()) { 205 // Advance the union's iterator to reach an unseen interfering vreg. 206 do { 207 if (IR.LiveUnionI.value() == RecentInterferingVReg) 208 continue; 209 210 if (!isSeenInterference(IR.LiveUnionI.value())) 211 break; 212 213 // Cache the most recent interfering vreg to bypass isSeenInterference. 214 RecentInterferingVReg = IR.LiveUnionI.value(); 215 216 } while ((++IR.LiveUnionI).valid()); 217 if (!IR.LiveUnionI.valid()) 218 break; 219 220 // Advance the VirtReg iterator until surpassing the next segment in 221 // LiveUnion. 222 IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start()); 223 if (IR.VirtRegI == VirtRegEnd) 224 break; 225 226 // Check for intersection with the union's segment. 227 if (overlap(*IR.VirtRegI, IR.LiveUnionI)) { 228 229 if (!IR.LiveUnionI.value()->isSpillable()) 230 SeenUnspillableVReg = true; 231 232 InterferingVRegs.push_back(IR.LiveUnionI.value()); 233 if (InterferingVRegs.size() == MaxInterferingRegs) 234 return MaxInterferingRegs; 235 236 // Cache the most recent interfering vreg to bypass isSeenInterference. 237 RecentInterferingVReg = IR.LiveUnionI.value(); 238 ++IR.LiveUnionI; 239 continue; 240 } 241 // VirtRegI may have advanced far beyond LiveUnionI, 242 // do a fast intersection test to "catch up" 243 IR.LiveUnionI.advanceTo(IR.VirtRegI->start); 244 } 245 SeenAllInterferences = true; 246 return InterferingVRegs.size(); 247} 248