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
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(Reg: 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().id());
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(Range: InterferingVRegs, Element: 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(x: 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(VirtReg: VReg)) {
161 RecentReg = VReg;
162 InterferingVRegs.push_back(Elt: 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(I: LRI, Pos: 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(x: 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(Sz: 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(ptr: LIUs);
212 Size = 0;
213 LIUs = nullptr;
214}
215