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