1//===- LiveIntervalUnion.cpp - Live interval union data structure ---------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// LiveIntervalUnion represents a coalesced set of live intervals. This may be 10// used during coalescing to represent a congruence class, or during register 11// allocation to model liveness of a physical register. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/CodeGen/LiveIntervalUnion.h" 16#include "llvm/ADT/STLExtras.h" 17#include "llvm/CodeGen/LiveInterval.h" 18#include "llvm/CodeGen/TargetRegisterInfo.h" 19#include "llvm/Support/raw_ostream.h" 20#include <cassert> 21#include <cstdlib> 22 23using namespace llvm; 24 25#define DEBUG_TYPE "regalloc" 26 27// Merge a LiveInterval's segments. Guarantee no overlaps. 28void LiveIntervalUnion::unify(const LiveInterval &VirtReg, 29 const LiveRange &Range) { 30 if (Range.empty()) 31 return; 32 ++Tag; 33 34 // Insert each of the virtual register's live segments into the map. 35 LiveRange::const_iterator RegPos = Range.begin(); 36 LiveRange::const_iterator RegEnd = Range.end(); 37 SegmentIter SegPos = Segments.find(RegPos->start); 38 39 while (SegPos.valid()) { 40 SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 41 if (++RegPos == RegEnd) 42 return; 43 SegPos.advanceTo(RegPos->start); 44 } 45 46 // We have reached the end of Segments, so it is no longer necessary to search 47 // for the insertion position. 48 // It is faster to insert the end first. 49 --RegEnd; 50 SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg); 51 for (; RegPos != RegEnd; ++RegPos, ++SegPos) 52 SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 53} 54 55// Remove a live virtual register's segments from this union. 56void LiveIntervalUnion::extract(const LiveInterval &VirtReg, 57 const LiveRange &Range) { 58 if (Range.empty()) 59 return; 60 ++Tag; 61 62 // Remove each of the virtual register's live segments from the map. 63 LiveRange::const_iterator RegPos = Range.begin(); 64 LiveRange::const_iterator RegEnd = Range.end(); 65 SegmentIter SegPos = Segments.find(RegPos->start); 66 67 while (true) { 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 = Range.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 103const LiveInterval *LiveIntervalUnion::getOneVReg() const { 104 if (empty()) 105 return nullptr; 106 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) { 107 // return the first valid live interval 108 return SI.value(); 109 } 110 return nullptr; 111} 112 113// Scan the vector of interfering virtual registers in this union. Assume it's 114// quite small. 115bool LiveIntervalUnion::Query::isSeenInterference( 116 const LiveInterval *VirtReg) const { 117 return is_contained(InterferingVRegs, VirtReg); 118} 119 120// Collect virtual registers in this union that interfere with this 121// query's live virtual register. 122// 123// The query state is one of: 124// 125// 1. CheckedFirstInterference == false: Iterators are uninitialized. 126// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. 127// 3. Iterators left at the last seen intersection. 128// 129unsigned 130LiveIntervalUnion::Query::collectInterferingVRegs(unsigned MaxInterferingRegs) { 131 // Fast path return if we already have the desired information. 132 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) 133 return InterferingVRegs.size(); 134 135 // Set up iterators on the first call. 136 if (!CheckedFirstInterference) { 137 CheckedFirstInterference = true; 138 139 // Quickly skip interference check for empty sets. 140 if (LR->empty() || LiveUnion->empty()) { 141 SeenAllInterferences = true; 142 return 0; 143 } 144 145 // In most cases, the union will start before LR. 146 LRI = LR->begin(); 147 LiveUnionI.setMap(LiveUnion->getMap()); 148 LiveUnionI.find(LRI->start); 149 } 150 151 LiveRange::const_iterator LREnd = LR->end(); 152 const LiveInterval *RecentReg = nullptr; 153 while (LiveUnionI.valid()) { 154 assert(LRI != LREnd && "Reached end of LR"); 155 156 // Check for overlapping interference. 157 while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) { 158 // This is an overlap, record the interfering register. 159 const LiveInterval *VReg = LiveUnionI.value(); 160 if (VReg != RecentReg && !isSeenInterference(VReg)) { 161 RecentReg = VReg; 162 InterferingVRegs.push_back(VReg); 163 if (InterferingVRegs.size() >= MaxInterferingRegs) 164 return InterferingVRegs.size(); 165 } 166 // This LiveUnion segment is no longer interesting. 167 if (!(++LiveUnionI).valid()) { 168 SeenAllInterferences = true; 169 return InterferingVRegs.size(); 170 } 171 } 172 173 // The iterators are now not overlapping, LiveUnionI has been advanced 174 // beyond LRI. 175 assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap"); 176 177 // Advance the iterator that ends first. 178 LRI = LR->advanceTo(LRI, LiveUnionI.start()); 179 if (LRI == LREnd) 180 break; 181 182 // Detect overlap, handle above. 183 if (LRI->start < LiveUnionI.stop()) 184 continue; 185 186 // Still not overlapping. Catch up LiveUnionI. 187 LiveUnionI.advanceTo(LRI->start); 188 } 189 SeenAllInterferences = true; 190 return InterferingVRegs.size(); 191} 192 193void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, 194 unsigned NSize) { 195 // Reuse existing allocation. 196 if (NSize == Size) 197 return; 198 clear(); 199 Size = NSize; 200 LIUs = static_cast<LiveIntervalUnion*>( 201 safe_malloc(sizeof(LiveIntervalUnion)*NSize)); 202 for (unsigned i = 0; i != Size; ++i) 203 new(LIUs + i) LiveIntervalUnion(Alloc); 204} 205 206void LiveIntervalUnion::Array::clear() { 207 if (!LIUs) 208 return; 209 for (unsigned i = 0; i != Size; ++i) 210 LIUs[i].~LiveIntervalUnion(); 211 free(LIUs); 212 Size = 0; 213 LIUs = nullptr; 214} 215