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