LLVM: lib/CodeGen/LiveIntervalUnion.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
20#include
21#include
22
23using namespace llvm;
24
25#define DEBUG_TYPE "regalloc"
26
27
30 if (Range.empty())
31 return;
32 ++Tag;
33
34
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
47
48
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
58 if (Range.empty())
59 return;
60 ++Tag;
61
62
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
74 RegPos = Range.advanceTo(RegPos, SegPos.start());
75 if (RegPos == RegEnd)
76 return;
77
78 SegPos.advanceTo(RegPos->start);
79 }
80}
81
82void
85 OS << " empty\n";
86 return;
87 }
88 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
89 OS << " [" << SI.start() << ' ' << SI.stop()
91 }
92 OS << '\n';
93}
94
95#ifndef NDEBUG
96
99 VisitedVRegs.set(SI.value()->reg().id());
100}
101#endif
102
105 return nullptr;
106 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
107
108 return SI.value();
109 }
110 return nullptr;
111}
112
113
114
115bool LiveIntervalUnion::Query::isSeenInterference(
117 return is_contained(InterferingVRegs, VirtReg);
118}
119
120
121
122
123
124
125
126
127
128
129unsigned
130LiveIntervalUnion::Query::collectInterferingVRegs(unsigned MaxInterferingRegs) {
131
132 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
133 return InterferingVRegs.size();
134
135
136 if (!CheckedFirstInterference) {
137 CheckedFirstInterference = true;
138
139
140 if (LR->empty() || LiveUnion->empty()) {
141 SeenAllInterferences = true;
142 return 0;
143 }
144
145
146 LRI = LR->begin();
147 LiveUnionI.setMap(LiveUnion->getMap());
148 LiveUnionI.find(LRI->start);
149 }
150
152 const LiveInterval *RecentReg = nullptr;
153 while (LiveUnionI.valid()) {
154 assert(LRI != LREnd && "Reached end of LR");
155
156
157 while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) {
158
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
167 if (!(++LiveUnionI).valid()) {
168 SeenAllInterferences = true;
169 return InterferingVRegs.size();
170 }
171 }
172
173
174
175 assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap");
176
177
178 LRI = LR->advanceTo(LRI, LiveUnionI.start());
179 if (LRI == LREnd)
180 break;
181
182
183 if (LRI->start < LiveUnionI.stop())
184 continue;
185
186
187 LiveUnionI.advanceTo(LRI->start);
188 }
189 SeenAllInterferences = true;
190 return InterferingVRegs.size();
191}
192
194 unsigned NSize) {
195
196 if (NSize == Size)
197 return;
199 Size = NSize;
202 for (unsigned i = 0; i != Size; ++i)
204}
205
207 if (!LIUs)
208 return;
209 for (unsigned i = 0; i != Size; ++i)
211 free(LIUs);
212 Size = 0;
213 LIUs = nullptr;
214}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Register const TargetRegisterInfo * TRI
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Definition LiveIntervalUnion.cpp:193
void clear()
Definition LiveIntervalUnion.cpp:206
LiveIntervalUnion(Allocator &a)
void unify(const LiveInterval &VirtReg, const LiveRange &Range)
Definition LiveIntervalUnion.cpp:28
const LiveInterval * getOneVReg() const
NDEBUG.
Definition LiveIntervalUnion.cpp:103
void extract(const LiveInterval &VirtReg, const LiveRange &Range)
Definition LiveIntervalUnion.cpp:56
LiveSegments::iterator SegmentIter
void verify(LiveVirtRegBitSet &VisitedVRegs)
Definition LiveIntervalUnion.cpp:97
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
Definition LiveIntervalUnion.cpp:83
LiveSegments::Allocator Allocator
LiveInterval - This class represents the liveness of a register, or stack slot.
This class represents the liveness of a register, stack slot, etc.
Segments::const_iterator const_iterator
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.
This is an optimization pass for GlobalISel generic memory operations.
SparseBitVector< 128 > LiveVirtRegBitSet
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI 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.