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 24using namespace llvm; 25 26 27// Merge a LiveInterval's segments. Guarantee no overlaps. 28void 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. 55void 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 80void 81LiveIntervalUnion::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. 96void 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. 104bool 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// 119unsigned LiveIntervalUnion::Query:: 120collectInterferingVRegs(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 184bool 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