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(x: RegPos->start);
38
39 while (SegPos.valid()) {
40 SegPos.insert(a: RegPos->start, b: RegPos->end, y: &VirtReg);
41 if (++RegPos == RegEnd)
42 return;
43 SegPos.advanceTo(x: 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(a: RegEnd->start, b: RegEnd->end, y: &VirtReg);
51 for (; RegPos != RegEnd; ++RegPos, ++SegPos)
52 SegPos.insert(a: RegPos->start, b: RegPos->end, y: &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(x: 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(I: RegPos, Pos: SegPos.start());
75 if (RegPos == RegEnd)
76 return;
77
78 SegPos.advanceTo(x: RegPos->start);
79 }
80}
81
82void LiveIntervalUnion::clearAllSegmentsReferencing(
83 const LiveInterval &VirtRegLI) {
84 ++Tag;
85
86 // Remove all segments referencing VirtReg.
87 for (SegmentIter SegPos = Segments.begin(); SegPos.valid();) {
88 if (SegPos.value()->reg() == VirtRegLI.reg())
89 SegPos.erase();
90 else
91 ++SegPos;
92 }
93}
94
95void
96LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
97 if (empty()) {
98 OS << " empty\n";
99 return;
100 }
101 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
102 OS << " [" << SI.start() << ' ' << SI.stop()
103 << "):" << printReg(Reg: SI.value()->reg(), TRI);
104 }
105 OS << '\n';
106}
107
108#ifndef NDEBUG
109// Verify the live intervals in this union and add them to the visited set.
110void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
111 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
112 VisitedVRegs.set(SI.value()->reg().id());
113}
114#endif //!NDEBUG
115
116const LiveInterval *LiveIntervalUnion::getOneVReg() const {
117 if (empty())
118 return nullptr;
119 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
120 // return the first valid live interval
121 return SI.value();
122 }
123 return nullptr;
124}
125
126// Scan the vector of interfering virtual registers in this union. Assume it's
127// quite small.
128bool LiveIntervalUnion::Query::isSeenInterference(
129 const LiveInterval *VirtReg) const {
130 return is_contained(Range: InterferingVRegs, Element: VirtReg);
131}
132
133// Collect virtual registers in this union that interfere with this
134// query's live virtual register.
135//
136// The query state is one of:
137//
138// 1. CheckedFirstInterference == false: Iterators are uninitialized.
139// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused.
140// 3. Iterators left at the last seen intersection.
141//
142unsigned
143LiveIntervalUnion::Query::collectInterferingVRegs(unsigned MaxInterferingRegs) {
144 // Fast path return if we already have the desired information.
145 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
146 return InterferingVRegs.size();
147
148 // Set up iterators on the first call.
149 if (!CheckedFirstInterference) {
150 CheckedFirstInterference = true;
151
152 // Quickly skip interference check for empty sets.
153 if (LR->empty() || LiveUnion->empty()) {
154 SeenAllInterferences = true;
155 return 0;
156 }
157
158 // In most cases, the union will start before LR.
159 LRI = LR->begin();
160 LiveUnionI.setMap(LiveUnion->getMap());
161 LiveUnionI.find(x: LRI->start);
162 }
163
164 LiveRange::const_iterator LREnd = LR->end();
165 const LiveInterval *RecentReg = nullptr;
166 while (LiveUnionI.valid()) {
167 assert(LRI != LREnd && "Reached end of LR");
168
169 // Check for overlapping interference.
170 while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) {
171 // This is an overlap, record the interfering register.
172 const LiveInterval *VReg = LiveUnionI.value();
173 if (VReg != RecentReg && !isSeenInterference(VirtReg: VReg)) {
174 RecentReg = VReg;
175 InterferingVRegs.push_back(Elt: VReg);
176 if (InterferingVRegs.size() >= MaxInterferingRegs)
177 return InterferingVRegs.size();
178 }
179 // This LiveUnion segment is no longer interesting.
180 if (!(++LiveUnionI).valid()) {
181 SeenAllInterferences = true;
182 return InterferingVRegs.size();
183 }
184 }
185
186 // The iterators are now not overlapping, LiveUnionI has been advanced
187 // beyond LRI.
188 assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap");
189
190 // Advance the iterator that ends first.
191 LRI = LR->advanceTo(I: LRI, Pos: LiveUnionI.start());
192 if (LRI == LREnd)
193 break;
194
195 // Detect overlap, handle above.
196 if (LRI->start < LiveUnionI.stop())
197 continue;
198
199 // Still not overlapping. Catch up LiveUnionI.
200 LiveUnionI.advanceTo(x: LRI->start);
201 }
202 SeenAllInterferences = true;
203 return InterferingVRegs.size();
204}
205
206void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc,
207 unsigned NSize) {
208 // Reuse existing allocation.
209 if (NSize == Size)
210 return;
211 clear();
212 Size = NSize;
213 LIUs = static_cast<LiveIntervalUnion*>(
214 safe_malloc(Sz: sizeof(LiveIntervalUnion)*NSize));
215 for (unsigned i = 0; i != Size; ++i)
216 new(LIUs + i) LiveIntervalUnion(Alloc);
217}
218
219void LiveIntervalUnion::Array::clear() {
220 if (!LIUs)
221 return;
222 for (unsigned i = 0; i != Size; ++i)
223 LIUs[i].~LiveIntervalUnion();
224 free(ptr: LIUs);
225 Size = 0;
226 LIUs = nullptr;
227}
228