LLVM 19.0.0git
LiveIntervalUnion.cpp
Go to the documentation of this file.
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
16#include "llvm/ADT/STLExtras.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.
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.
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
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.
98 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
99 VisitedVRegs.set(SI.value()->reg());
100}
101#endif //!NDEBUG
102
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
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
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}
uint64_t Size
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
const_iterator begin() const
Definition: IntervalMap.h:1146
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
Definition: IntervalMap.h:1172
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
void unify(const LiveInterval &VirtReg, const LiveRange &Range)
const LiveInterval * getOneVReg() const
NDEBUG.
void extract(const LiveInterval &VirtReg, const LiveRange &Range)
LiveSegments::iterator SegmentIter
void verify(LiveVirtRegBitSet &VisitedVRegs)
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
LiveSegments::Allocator Allocator
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
size_t size() const
Definition: LiveInterval.h:305
void set(unsigned Idx)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:25
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.