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 24 using namespace llvm; 25 26 27 // Merge a LiveInterval's segments. Guarantee no overlaps. 28 void 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 while (SegPos.valid()) { 39 SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 40 if (++RegPos == RegEnd) 41 return; 42 SegPos.advanceTo(RegPos->start); 43 } 44 45 // We have reached the end of Segments, so it is no longer necessary to search 46 // for the insertion position. 47 // It is faster to insert the end first. 48 --RegEnd; 49 SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg); 50 for (; RegPos != RegEnd; ++RegPos, ++SegPos) 51 SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 52 } 53 54 // Remove a live virtual register's segments from this union. 55 void LiveIntervalUnion::extract(LiveInterval &VirtReg) { 56 if (VirtReg.empty()) 57 return; 58 ++Tag; 59 60 // Remove each of the virtual register's live segments from the map. 61 LiveInterval::iterator RegPos = VirtReg.begin(); 62 LiveInterval::iterator RegEnd = VirtReg.end(); 63 SegmentIter SegPos = Segments.find(RegPos->start); 64 65 for (;;) { 66 assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval"); 67 SegPos.erase(); 68 if (!SegPos.valid()) 69 return; 70 71 // Skip all segments that may have been coalesced. 72 RegPos = VirtReg.advanceTo(RegPos, SegPos.start()); 73 if (RegPos == RegEnd) 74 return; 75 76 SegPos.advanceTo(RegPos->start); 77 } 78 } 79 80 void 81 LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 82 OS << "LIU " << PrintReg(RepReg, TRI); 83 if (empty()) { 84 OS << " empty\n"; 85 return; 86 } 87 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) { 88 OS << " [" << SI.start() << ' ' << SI.stop() << "):" 89 << PrintReg(SI.value()->reg, TRI); 90 } 91 OS << '\n'; 92 } 93 94 #ifndef NDEBUG 95 // Verify the live intervals in this union and add them to the visited set. 96 void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { 97 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI) 98 VisitedVRegs.set(SI.value()->reg); 99 } 100 #endif //!NDEBUG 101 102 // Scan the vector of interfering virtual registers in this union. Assume it's 103 // quite small. 104 bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { 105 SmallVectorImpl<LiveInterval*>::const_iterator I = 106 std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); 107 return I != InterferingVRegs.end(); 108 } 109 110 // Collect virtual registers in this union that interfere with this 111 // query's live virtual register. 112 // 113 // The query state is one of: 114 // 115 // 1. CheckedFirstInterference == false: Iterators are uninitialized. 116 // 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. 117 // 3. Iterators left at the last seen intersection. 118 // 119 unsigned LiveIntervalUnion::Query:: 120 collectInterferingVRegs(unsigned MaxInterferingRegs) { 121 // Fast path return if we already have the desired information. 122 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) 123 return InterferingVRegs.size(); 124 125 // Set up iterators on the first call. 126 if (!CheckedFirstInterference) { 127 CheckedFirstInterference = true; 128 129 // Quickly skip interference check for empty sets. 130 if (VirtReg->empty() || LiveUnion->empty()) { 131 SeenAllInterferences = true; 132 return 0; 133 } 134 135 // In most cases, the union will start before VirtReg. 136 VirtRegI = VirtReg->begin(); 137 LiveUnionI.setMap(LiveUnion->getMap()); 138 LiveUnionI.find(VirtRegI->start); 139 } 140 141 LiveInterval::iterator VirtRegEnd = VirtReg->end(); 142 LiveInterval *RecentReg = 0; 143 while (LiveUnionI.valid()) { 144 assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg"); 145 146 // Check for overlapping interference. 147 while (VirtRegI->start < LiveUnionI.stop() && 148 VirtRegI->end > LiveUnionI.start()) { 149 // This is an overlap, record the interfering register. 150 LiveInterval *VReg = LiveUnionI.value(); 151 if (VReg != RecentReg && !isSeenInterference(VReg)) { 152 RecentReg = VReg; 153 InterferingVRegs.push_back(VReg); 154 if (InterferingVRegs.size() >= MaxInterferingRegs) 155 return InterferingVRegs.size(); 156 } 157 // This LiveUnion segment is no longer interesting. 158 if (!(++LiveUnionI).valid()) { 159 SeenAllInterferences = true; 160 return InterferingVRegs.size(); 161 } 162 } 163 164 // The iterators are now not overlapping, LiveUnionI has been advanced 165 // beyond VirtRegI. 166 assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); 167 168 // Advance the iterator that ends first. 169 VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); 170 if (VirtRegI == VirtRegEnd) 171 break; 172 173 // Detect overlap, handle above. 174 if (VirtRegI->start < LiveUnionI.stop()) 175 continue; 176 177 // Still not overlapping. Catch up LiveUnionI. 178 LiveUnionI.advanceTo(VirtRegI->start); 179 } 180 SeenAllInterferences = true; 181 return InterferingVRegs.size(); 182 } 183 184 bool LiveIntervalUnion::Query::checkLoopInterference(MachineLoopRange *Loop) { 185 // VirtReg is likely live throughout the loop, so start by checking LIU-Loop 186 // overlaps. 187 IntervalMapOverlaps<LiveIntervalUnion::Map, MachineLoopRange::Map> 188 Overlaps(LiveUnion->getMap(), Loop->getMap()); 189 if (!Overlaps.valid()) 190 return false; 191 192 // The loop is overlapping an LIU assignment. Check VirtReg as well. 193 LiveInterval::iterator VRI = VirtReg->find(Overlaps.start()); 194 195 for (;;) { 196 if (VRI == VirtReg->end()) 197 return false; 198 if (VRI->start < Overlaps.stop()) 199 return true; 200 201 Overlaps.advanceTo(VRI->start); 202 if (!Overlaps.valid()) 203 return false; 204 if (Overlaps.start() < VRI->end) 205 return true; 206 207 VRI = VirtReg->advanceTo(VRI, Overlaps.start()); 208 } 209 } 210