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