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 "llvm/CodeGen/LiveIntervalUnion.h" 18 #include "llvm/ADT/SparseBitVector.h" 19 #include "llvm/Support/Debug.h" 20 #include "llvm/Support/raw_ostream.h" 21 #include "llvm/Target/TargetRegisterInfo.h" 22 #include <algorithm> 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 if (empty()) { 83 OS << " empty\n"; 84 return; 85 } 86 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) { 87 OS << " [" << SI.start() << ' ' << SI.stop() << "):" 88 << PrintReg(SI.value()->reg, TRI); 89 } 90 OS << '\n'; 91 } 92 93 #ifndef NDEBUG 94 // Verify the live intervals in this union and add them to the visited set. 95 void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { 96 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI) 97 VisitedVRegs.set(SI.value()->reg); 98 } 99 #endif //!NDEBUG 100 101 // Scan the vector of interfering virtual registers in this union. Assume it's 102 // quite small. 103 bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { 104 SmallVectorImpl<LiveInterval*>::const_iterator I = 105 std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); 106 return I != InterferingVRegs.end(); 107 } 108 109 // Collect virtual registers in this union that interfere with this 110 // query's live virtual register. 111 // 112 // The query state is one of: 113 // 114 // 1. CheckedFirstInterference == false: Iterators are uninitialized. 115 // 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. 116 // 3. Iterators left at the last seen intersection. 117 // 118 unsigned LiveIntervalUnion::Query:: 119 collectInterferingVRegs(unsigned MaxInterferingRegs) { 120 // Fast path return if we already have the desired information. 121 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) 122 return InterferingVRegs.size(); 123 124 // Set up iterators on the first call. 125 if (!CheckedFirstInterference) { 126 CheckedFirstInterference = true; 127 128 // Quickly skip interference check for empty sets. 129 if (VirtReg->empty() || LiveUnion->empty()) { 130 SeenAllInterferences = true; 131 return 0; 132 } 133 134 // In most cases, the union will start before VirtReg. 135 VirtRegI = VirtReg->begin(); 136 LiveUnionI.setMap(LiveUnion->getMap()); 137 LiveUnionI.find(VirtRegI->start); 138 } 139 140 LiveInterval::iterator VirtRegEnd = VirtReg->end(); 141 LiveInterval *RecentReg = 0; 142 while (LiveUnionI.valid()) { 143 assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg"); 144 145 // Check for overlapping interference. 146 while (VirtRegI->start < LiveUnionI.stop() && 147 VirtRegI->end > LiveUnionI.start()) { 148 // This is an overlap, record the interfering register. 149 LiveInterval *VReg = LiveUnionI.value(); 150 if (VReg != RecentReg && !isSeenInterference(VReg)) { 151 RecentReg = VReg; 152 InterferingVRegs.push_back(VReg); 153 if (InterferingVRegs.size() >= MaxInterferingRegs) 154 return InterferingVRegs.size(); 155 } 156 // This LiveUnion segment is no longer interesting. 157 if (!(++LiveUnionI).valid()) { 158 SeenAllInterferences = true; 159 return InterferingVRegs.size(); 160 } 161 } 162 163 // The iterators are now not overlapping, LiveUnionI has been advanced 164 // beyond VirtRegI. 165 assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); 166 167 // Advance the iterator that ends first. 168 VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); 169 if (VirtRegI == VirtRegEnd) 170 break; 171 172 // Detect overlap, handle above. 173 if (VirtRegI->start < LiveUnionI.stop()) 174 continue; 175 176 // Still not overlapping. Catch up LiveUnionI. 177 LiveUnionI.advanceTo(VirtRegI->start); 178 } 179 SeenAllInterferences = true; 180 return InterferingVRegs.size(); 181 } 182 183 void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, 184 unsigned NSize) { 185 // Reuse existing allocation. 186 if (NSize == Size) 187 return; 188 clear(); 189 Size = NSize; 190 LIUs = static_cast<LiveIntervalUnion*>( 191 malloc(sizeof(LiveIntervalUnion)*NSize)); 192 for (unsigned i = 0; i != Size; ++i) 193 new(LIUs + i) LiveIntervalUnion(Alloc); 194 } 195 196 void LiveIntervalUnion::Array::clear() { 197 if (!LIUs) 198 return; 199 for (unsigned i = 0; i != Size; ++i) 200 LIUs[i].~LiveIntervalUnion(); 201 free(LIUs); 202 Size = 0; 203 LIUs = 0; 204 } 205