/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/HexagonBlockRanges.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- HexagonBlockRanges.cpp ---------------------------------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | |
10 | | #define DEBUG_TYPE "hbr" |
11 | | |
12 | | #include "HexagonBlockRanges.h" |
13 | | #include "HexagonInstrInfo.h" |
14 | | #include "HexagonSubtarget.h" |
15 | | #include "llvm/ADT/BitVector.h" |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
18 | | #include "llvm/CodeGen/MachineFunction.h" |
19 | | #include "llvm/CodeGen/MachineInstr.h" |
20 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
21 | | #include "llvm/MC/MCRegisterInfo.h" |
22 | | #include "llvm/Support/Debug.h" |
23 | | #include "llvm/Support/raw_ostream.h" |
24 | | #include "llvm/Target/TargetRegisterInfo.h" |
25 | | #include <algorithm> |
26 | | #include <cassert> |
27 | | #include <cstdint> |
28 | | #include <iterator> |
29 | | #include <map> |
30 | | #include <utility> |
31 | | |
32 | | using namespace llvm; |
33 | | |
34 | 8.57k | bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const { |
35 | 8.57k | // If A contains start(), or "this" contains A.start(), then overlap. |
36 | 8.57k | IndexType S = start(), E = end(), AS = A.start(), AE = A.end(); |
37 | 8.57k | if (AS == S) |
38 | 12 | return true; |
39 | 8.55k | bool SbAE = (S < AE) || 8.55k (S == AE && 3 A.TiedEnd0 ); // S-before-AE. |
40 | 8.26k | bool ASbE = (AS < E) || (AS == E && 8.26k TiedEnd2.66k ); // AS-before-E. |
41 | 8.55k | if ((AS < S && 8.55k SbAE3 ) || (S < AS && 8.55k ASbE8.55k )) |
42 | 293 | return true; |
43 | 8.26k | // Otherwise no overlap. |
44 | 8.26k | return false; |
45 | 8.26k | } |
46 | | |
47 | 13.1k | bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const { |
48 | 13.1k | if (start() <= A.start()13.1k ) { |
49 | 3.19k | // Treat "None" in the range end as equal to the range start. |
50 | 3.19k | IndexType E = (end() != IndexType::None) ? end()3.19k : start()0 ; |
51 | 3.19k | IndexType AE = (A.end() != IndexType::None) ? A.end()3.19k : A.start()0 ; |
52 | 3.19k | if (AE <= E) |
53 | 19 | return true; |
54 | 13.1k | } |
55 | 13.1k | return false; |
56 | 13.1k | } |
57 | | |
58 | 273 | void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) { |
59 | 273 | // Allow merging adjacent ranges. |
60 | 273 | assert(end() == A.start() || overlaps(A)); |
61 | 273 | IndexType AS = A.start(), AE = A.end(); |
62 | 273 | if (AS < start() || 273 start() == IndexType::None273 ) |
63 | 0 | setStart(AS); |
64 | 273 | if (end() < AE || 273 end() == IndexType::None269 ) { |
65 | 4 | setEnd(AE); |
66 | 4 | TiedEnd = A.TiedEnd; |
67 | 273 | } else { |
68 | 269 | if (end() == AE) |
69 | 55 | TiedEnd |= A.TiedEnd; |
70 | 269 | } |
71 | 273 | if (A.Fixed) |
72 | 0 | Fixed = true; |
73 | 273 | } |
74 | | |
75 | 16 | void HexagonBlockRanges::RangeList::include(const RangeList &RL) { |
76 | 16 | for (auto &R : RL) |
77 | 31 | if (31 !is_contained(*this, R)31 ) |
78 | 31 | push_back(R); |
79 | 16 | } |
80 | | |
81 | | // Merge all overlapping ranges in the list, so that all that remains |
82 | | // is a list of disjoint ranges. |
83 | 17.4k | void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) { |
84 | 17.4k | if (empty()) |
85 | 0 | return; |
86 | 17.4k | |
87 | 17.4k | std::sort(begin(), end()); |
88 | 17.4k | iterator Iter = begin(); |
89 | 17.4k | |
90 | 25.9k | while (Iter != end()-125.9k ) { |
91 | 8.53k | iterator Next = std::next(Iter); |
92 | 8.53k | // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start. |
93 | 8.53k | // This allows merging dead ranges, but is not valid for live ranges. |
94 | 0 | bool Merge = MergeAdjacent && (Iter->end() == Next->start()); |
95 | 8.53k | if (Merge || 8.53k Iter->overlaps(*Next)8.53k ) { |
96 | 273 | Iter->merge(*Next); |
97 | 273 | erase(Next); |
98 | 273 | continue; |
99 | 273 | } |
100 | 8.26k | ++Iter; |
101 | 8.26k | } |
102 | 17.4k | } |
103 | | |
104 | | // Compute a range A-B and add it to the list. |
105 | | void HexagonBlockRanges::RangeList::addsub(const IndexRange &A, |
106 | 16 | const IndexRange &B) { |
107 | 16 | // Exclusion of non-overlapping ranges makes some checks simpler |
108 | 16 | // later in this function. |
109 | 16 | if (!A.overlaps(B)16 ) { |
110 | 0 | // A - B = A. |
111 | 0 | add(A); |
112 | 0 | return; |
113 | 0 | } |
114 | 16 | |
115 | 16 | IndexType AS = A.start(), AE = A.end(); |
116 | 16 | IndexType BS = B.start(), BE = B.end(); |
117 | 16 | |
118 | 16 | // If AE is None, then A is included in B, since A and B overlap. |
119 | 16 | // The result of subtraction if empty, so just return. |
120 | 16 | if (AE == IndexType::None) |
121 | 0 | return; |
122 | 16 | |
123 | 16 | if (16 AS < BS16 ) { |
124 | 15 | // A starts before B. |
125 | 15 | // AE cannot be None since A and B overlap. |
126 | 15 | assert(AE != IndexType::None); |
127 | 15 | // Add the part of A that extends on the "less" side of B. |
128 | 15 | add(AS, BS, A.Fixed, false); |
129 | 15 | } |
130 | 16 | |
131 | 16 | if (BE < AE16 ) { |
132 | 16 | // BE cannot be Exit here. |
133 | 16 | if (BE == IndexType::None) |
134 | 0 | add(BS, AE, A.Fixed, false); |
135 | 16 | else |
136 | 16 | add(BE, AE, A.Fixed, false); |
137 | 16 | } |
138 | 16 | } |
139 | | |
140 | | // Subtract a given range from each element in the list. |
141 | 16 | void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) { |
142 | 16 | // Cannot assume that the list is unionized (i.e. contains only non- |
143 | 16 | // overlapping ranges. |
144 | 16 | RangeList T; |
145 | 38 | for (iterator Next, I = begin(); I != end()38 ; I = Next22 ) { |
146 | 22 | IndexRange &Rg = *I; |
147 | 22 | if (Rg.overlaps(Range)22 ) { |
148 | 16 | T.addsub(Rg, Range); |
149 | 16 | Next = this->erase(I); |
150 | 22 | } else { |
151 | 6 | Next = std::next(I); |
152 | 6 | } |
153 | 22 | } |
154 | 16 | include(T); |
155 | 16 | } |
156 | | |
157 | | HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B) |
158 | 2.06k | : Block(B) { |
159 | 2.06k | IndexType Idx = IndexType::First; |
160 | 2.06k | First = Idx; |
161 | 11.3k | for (auto &In : B) { |
162 | 11.3k | if (In.isDebugValue()) |
163 | 12 | continue; |
164 | 11.3k | assert(getIndex(&In) == IndexType::None && "Instruction already in map"); |
165 | 11.3k | Map.insert(std::make_pair(Idx, &In)); |
166 | 11.3k | ++Idx; |
167 | 11.3k | } |
168 | 2.06k | Last = B.empty() ? IndexType::None147 : unsigned(Idx)-11.91k ; |
169 | 2.06k | } |
170 | | |
171 | 168 | MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const { |
172 | 168 | auto F = Map.find(Idx); |
173 | 168 | return (F != Map.end()) ? F->second168 : nullptr0 ; |
174 | 168 | } |
175 | | |
176 | | HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex( |
177 | 11.7k | MachineInstr *MI) const { |
178 | 11.7k | for (auto &I : Map) |
179 | 1.33M | if (1.33M I.second == MI1.33M ) |
180 | 11.7k | return I.first; |
181 | 1 | return IndexType::None; |
182 | 1 | } |
183 | | |
184 | | HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex( |
185 | 20.7k | IndexType Idx) const { |
186 | 20.7k | assert (Idx != IndexType::None); |
187 | 20.7k | if (Idx == IndexType::Entry) |
188 | 0 | return IndexType::None; |
189 | 20.7k | if (20.7k Idx == IndexType::Exit20.7k ) |
190 | 0 | return Last; |
191 | 20.7k | if (20.7k Idx == First20.7k ) |
192 | 3.52k | return IndexType::Entry; |
193 | 17.2k | return unsigned(Idx)-1; |
194 | 17.2k | } |
195 | | |
196 | | HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex( |
197 | 21.5k | IndexType Idx) const { |
198 | 21.5k | assert (Idx != IndexType::None); |
199 | 21.5k | if (Idx == IndexType::Entry) |
200 | 0 | return IndexType::First; |
201 | 21.5k | if (21.5k Idx == IndexType::Exit || 21.5k Idx == Last21.5k ) |
202 | 4.46k | return IndexType::None; |
203 | 17.0k | return unsigned(Idx)+1; |
204 | 17.0k | } |
205 | | |
206 | | void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI, |
207 | 33 | MachineInstr *NewMI) { |
208 | 952 | for (auto &I : Map) { |
209 | 952 | if (I.second != OldMI) |
210 | 919 | continue; |
211 | 33 | if (33 NewMI != nullptr33 ) |
212 | 33 | I.second = NewMI; |
213 | 33 | else |
214 | 0 | Map.erase(I.first); |
215 | 952 | break; |
216 | 952 | } |
217 | 33 | } |
218 | | |
219 | | HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf) |
220 | | : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()), |
221 | | TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()), |
222 | 860 | Reserved(TRI.getReservedRegs(mf)) { |
223 | 860 | // Consider all non-allocatable registers as reserved. |
224 | 17.2k | for (const TargetRegisterClass *RC : TRI.regclasses()) { |
225 | 17.2k | if (RC->isAllocatable()) |
226 | 9.46k | continue; |
227 | 7.74k | for (unsigned R : *RC) |
228 | 49.8k | Reserved[R] = true; |
229 | 17.2k | } |
230 | 860 | } |
231 | | |
232 | | HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns( |
233 | | const MachineBasicBlock &B, const MachineRegisterInfo &MRI, |
234 | 3.78k | const TargetRegisterInfo &TRI) { |
235 | 3.78k | RegisterSet LiveIns; |
236 | 3.78k | RegisterSet Tmp; |
237 | 3.78k | |
238 | 11.8k | for (auto I : B.liveins()) { |
239 | 11.8k | MCSubRegIndexIterator S(I.PhysReg, &TRI); |
240 | 11.8k | if (I.LaneMask.all() || 11.8k (I.LaneMask.any() && 10.3k !S.isValid()10.3k )) { |
241 | 11.8k | Tmp.insert({I.PhysReg, 0}); |
242 | 11.8k | continue; |
243 | 11.8k | } |
244 | 6 | for (; 2 S.isValid()6 ; ++S4 ) { |
245 | 4 | unsigned SI = S.getSubRegIndex(); |
246 | 4 | if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SI)).any()) |
247 | 4 | Tmp.insert({S.getSubReg(), 0}); |
248 | 4 | } |
249 | 11.8k | } |
250 | 3.78k | |
251 | 11.8k | for (auto R : Tmp) { |
252 | 11.8k | if (!Reserved[R.Reg]) |
253 | 9.80k | LiveIns.insert(R); |
254 | 11.8k | for (auto S : expandToSubRegs(R, MRI, TRI)) |
255 | 11.9k | if (11.9k !Reserved[S.Reg]11.9k ) |
256 | 9.89k | LiveIns.insert(S); |
257 | 11.8k | } |
258 | 3.78k | return LiveIns; |
259 | 3.78k | } |
260 | | |
261 | | HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs( |
262 | | RegisterRef R, const MachineRegisterInfo &MRI, |
263 | 322k | const TargetRegisterInfo &TRI) { |
264 | 322k | RegisterSet SRs; |
265 | 322k | |
266 | 322k | if (R.Sub != 0322k ) { |
267 | 0 | SRs.insert(R); |
268 | 0 | return SRs; |
269 | 0 | } |
270 | 322k | |
271 | 322k | if (322k TargetRegisterInfo::isPhysicalRegister(R.Reg)322k ) { |
272 | 322k | MCSubRegIterator I(R.Reg, &TRI); |
273 | 322k | if (!I.isValid()) |
274 | 229k | SRs.insert({R.Reg, 0}); |
275 | 506k | for (; I.isValid()506k ; ++I183k ) |
276 | 183k | SRs.insert({*I, 0}); |
277 | 322k | } else { |
278 | 120 | assert(TargetRegisterInfo::isVirtualRegister(R.Reg)); |
279 | 120 | auto &RC = *MRI.getRegClass(R.Reg); |
280 | 120 | unsigned PReg = *RC.begin(); |
281 | 120 | MCSubRegIndexIterator I(PReg, &TRI); |
282 | 120 | if (!I.isValid()) |
283 | 120 | SRs.insert({R.Reg, 0}); |
284 | 120 | for (; I.isValid()120 ; ++I0 ) |
285 | 0 | SRs.insert({R.Reg, I.getSubRegIndex()}); |
286 | 120 | } |
287 | 322k | return SRs; |
288 | 322k | } |
289 | | |
290 | | void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap, |
291 | 2.06k | RegToRangeMap &LiveMap) { |
292 | 2.06k | std::map<RegisterRef,IndexType> LastDef, LastUse; |
293 | 2.06k | RegisterSet LiveOnEntry; |
294 | 2.06k | MachineBasicBlock &B = IndexMap.getBlock(); |
295 | 2.06k | MachineRegisterInfo &MRI = B.getParent()->getRegInfo(); |
296 | 2.06k | |
297 | 2.06k | for (auto R : getLiveIns(B, MRI, TRI)) |
298 | 4.95k | LiveOnEntry.insert(R); |
299 | 2.06k | |
300 | 2.06k | for (auto R : LiveOnEntry) |
301 | 4.95k | LastDef[R] = IndexType::Entry; |
302 | 2.06k | |
303 | 25.9k | auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void { |
304 | 25.9k | auto LD = LastDef[R], LU = LastUse[R]; |
305 | 25.9k | if (LD == IndexType::None) |
306 | 37 | LD = IndexType::Entry; |
307 | 25.9k | if (LU == IndexType::None) |
308 | 193 | LU = IndexType::Exit; |
309 | 25.9k | LiveMap[R].add(LD, LU, false, false); |
310 | 25.9k | LastUse[R] = LastDef[R] = IndexType::None; |
311 | 25.9k | }; |
312 | 2.06k | |
313 | 2.06k | RegisterSet Defs, Clobbers; |
314 | 2.06k | |
315 | 11.3k | for (auto &In : B) { |
316 | 11.3k | if (In.isDebugValue()) |
317 | 12 | continue; |
318 | 11.3k | IndexType Index = IndexMap.getIndex(&In); |
319 | 11.3k | // Process uses first. |
320 | 34.1k | for (auto &Op : In.operands()) { |
321 | 34.1k | if (!Op.isReg() || 34.1k !Op.isUse()23.5k || Op.isUndef()13.1k ) |
322 | 21.2k | continue; |
323 | 12.8k | RegisterRef R = { Op.getReg(), Op.getSubReg() }; |
324 | 12.8k | if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && 12.8k Reserved[R.Reg]12.7k ) |
325 | 1.56k | continue; |
326 | 11.2k | bool IsKill = Op.isKill(); |
327 | 12.3k | for (auto S : expandToSubRegs(R, MRI, TRI)) { |
328 | 12.3k | LastUse[S] = Index; |
329 | 12.3k | if (IsKill) |
330 | 7.61k | closeRange(S); |
331 | 12.3k | } |
332 | 34.1k | } |
333 | 11.3k | // Process defs and clobbers. |
334 | 11.3k | Defs.clear(); |
335 | 11.3k | Clobbers.clear(); |
336 | 34.1k | for (auto &Op : In.operands()) { |
337 | 34.1k | if (!Op.isReg() || 34.1k !Op.isDef()23.5k || Op.isUndef()10.4k ) |
338 | 23.6k | continue; |
339 | 10.4k | RegisterRef R = { Op.getReg(), Op.getSubReg() }; |
340 | 11.3k | for (auto S : expandToSubRegs(R, MRI, TRI)) { |
341 | 11.3k | if (TargetRegisterInfo::isPhysicalRegister(S.Reg) && 11.3k Reserved[S.Reg]11.2k ) |
342 | 3.25k | continue; |
343 | 8.07k | if (8.07k Op.isDead()8.07k ) |
344 | 185 | Clobbers.insert(S); |
345 | 8.07k | else |
346 | 7.89k | Defs.insert(S); |
347 | 11.3k | } |
348 | 34.1k | } |
349 | 11.3k | |
350 | 34.1k | for (auto &Op : In.operands()) { |
351 | 34.1k | if (!Op.isRegMask()) |
352 | 33.8k | continue; |
353 | 229 | const uint32_t *BM = Op.getRegMask(); |
354 | 32.0k | for (unsigned PR = 1, N = TRI.getNumRegs(); PR != N32.0k ; ++PR31.8k ) { |
355 | 31.8k | // Skip registers that have subregisters. A register is preserved |
356 | 31.8k | // iff its bit is set in the regmask, so if R1:0 was preserved, both |
357 | 31.8k | // R1 and R0 would also be present. |
358 | 31.8k | if (MCSubRegIterator(PR, &TRI, false).isValid()) |
359 | 10.0k | continue; |
360 | 21.7k | if (21.7k Reserved[PR]21.7k ) |
361 | 5.95k | continue; |
362 | 15.8k | if (15.8k BM[PR/32] & (1u << (PR%32))15.8k ) |
363 | 2.74k | continue; |
364 | 13.0k | RegisterRef R = { PR, 0 }; |
365 | 13.0k | if (!Defs.count(R)) |
366 | 12.9k | Clobbers.insert(R); |
367 | 31.8k | } |
368 | 34.1k | } |
369 | 11.3k | // Defs and clobbers can overlap, e.g. |
370 | 11.3k | // %D0<def,dead> = COPY %vreg5, %R0<imp-def>, %R1<imp-def> |
371 | 11.3k | for (RegisterRef R : Defs) |
372 | 7.89k | Clobbers.erase(R); |
373 | 11.3k | |
374 | 11.3k | // Update maps for defs. |
375 | 7.89k | for (RegisterRef S : Defs) { |
376 | 7.89k | // Defs should already be expanded into subregs. |
377 | 7.89k | assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) || |
378 | 7.89k | !MCSubRegIterator(S.Reg, &TRI, false).isValid()); |
379 | 7.89k | if (LastDef[S] != IndexType::None || 7.89k LastUse[S] != IndexType::None7.53k ) |
380 | 367 | closeRange(S); |
381 | 7.89k | LastDef[S] = Index; |
382 | 7.89k | } |
383 | 11.3k | // Update maps for clobbers. |
384 | 13.1k | for (RegisterRef S : Clobbers) { |
385 | 13.1k | // Clobbers should already be expanded into subregs. |
386 | 13.1k | assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) || |
387 | 13.1k | !MCSubRegIterator(S.Reg, &TRI, false).isValid()); |
388 | 13.1k | if (LastDef[S] != IndexType::None || 13.1k LastUse[S] != IndexType::None12.9k ) |
389 | 213 | closeRange(S); |
390 | 13.1k | // Create a single-instruction range. |
391 | 13.1k | LastDef[S] = LastUse[S] = Index; |
392 | 13.1k | closeRange(S); |
393 | 13.1k | } |
394 | 11.3k | } |
395 | 2.06k | |
396 | 2.06k | // Collect live-on-exit. |
397 | 2.06k | RegisterSet LiveOnExit; |
398 | 2.06k | for (auto *SB : B.successors()) |
399 | 1.72k | for (auto R : getLiveIns(*SB, MRI, TRI)) |
400 | 5.02k | LiveOnExit.insert(R); |
401 | 2.06k | |
402 | 2.06k | for (auto R : LiveOnExit) |
403 | 4.02k | LastUse[R] = IndexType::Exit; |
404 | 2.06k | |
405 | 2.06k | // Process remaining registers. |
406 | 2.06k | RegisterSet Left; |
407 | 2.06k | for (auto &I : LastUse) |
408 | 17.3k | if (17.3k I.second != IndexType::None17.3k ) |
409 | 4.56k | Left.insert(I.first); |
410 | 2.06k | for (auto &I : LastDef) |
411 | 17.4k | if (17.4k I.second != IndexType::None17.4k ) |
412 | 4.66k | Left.insert(I.first); |
413 | 2.06k | for (auto R : Left) |
414 | 4.68k | closeRange(R); |
415 | 2.06k | |
416 | 2.06k | // Finalize the live ranges. |
417 | 2.06k | for (auto &P : LiveMap) |
418 | 17.4k | P.second.unionize(); |
419 | 2.06k | } |
420 | | |
421 | | HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap( |
422 | 2.06k | InstrIndexMap &IndexMap) { |
423 | 2.06k | RegToRangeMap LiveMap; |
424 | 2.06k | DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n'); |
425 | 2.06k | computeInitialLiveRanges(IndexMap, LiveMap); |
426 | 2.06k | DEBUG(dbgs() << __func__ << ": live map\n" |
427 | 2.06k | << PrintRangeMap(LiveMap, TRI) << '\n'); |
428 | 2.06k | return LiveMap; |
429 | 2.06k | } |
430 | | |
431 | | HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap( |
432 | 2.06k | InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) { |
433 | 2.06k | RegToRangeMap DeadMap; |
434 | 2.06k | |
435 | 142k | auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void { |
436 | 142k | auto F = LiveMap.find(R); |
437 | 142k | if (F == LiveMap.end() || 142k F->second.empty()17.3k ) { |
438 | 124k | DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false); |
439 | 124k | return; |
440 | 124k | } |
441 | 17.3k | |
442 | 17.3k | RangeList &RL = F->second; |
443 | 17.3k | RangeList::iterator A = RL.begin(), Z = RL.end()-1; |
444 | 17.3k | |
445 | 17.3k | // Try to create the initial range. |
446 | 17.3k | if (A->start() != IndexType::Entry17.3k ) { |
447 | 12.4k | IndexType DE = IndexMap.getPrevIndex(A->start()); |
448 | 12.4k | if (DE != IndexType::Entry) |
449 | 9.38k | DeadMap[R].add(IndexType::Entry, DE, false, false); |
450 | 12.4k | } |
451 | 17.3k | |
452 | 25.6k | while (A != Z25.6k ) { |
453 | 8.26k | // Creating a dead range that follows A. Pay attention to empty |
454 | 8.26k | // ranges (i.e. those ending with "None"). |
455 | 8.26k | IndexType AE = (A->end() == IndexType::None) ? A->start()0 : A->end()8.26k ; |
456 | 8.26k | IndexType DS = IndexMap.getNextIndex(AE); |
457 | 8.26k | ++A; |
458 | 8.26k | IndexType DE = IndexMap.getPrevIndex(A->start()); |
459 | 8.26k | if (DS < DE) |
460 | 3.26k | DeadMap[R].add(DS, DE, false, false); |
461 | 8.26k | } |
462 | 17.3k | |
463 | 17.3k | // Try to create the final range. |
464 | 17.3k | if (Z->end() != IndexType::Exit17.3k ) { |
465 | 13.2k | IndexType ZE = (Z->end() == IndexType::None) ? Z->start()0 : Z->end()13.2k ; |
466 | 13.2k | IndexType DS = IndexMap.getNextIndex(ZE); |
467 | 13.2k | if (DS < IndexType::Exit) |
468 | 8.96k | DeadMap[R].add(DS, IndexType::Exit, false, false); |
469 | 13.2k | } |
470 | 142k | }; |
471 | 2.06k | |
472 | 2.06k | MachineFunction &MF = *IndexMap.getBlock().getParent(); |
473 | 2.06k | auto &MRI = MF.getRegInfo(); |
474 | 2.06k | unsigned NumRegs = TRI.getNumRegs(); |
475 | 2.06k | BitVector Visited(NumRegs); |
476 | 288k | for (unsigned R = 1; R < NumRegs288k ; ++R286k ) { |
477 | 375k | for (auto S : expandToSubRegs({R,0}, MRI, TRI)) { |
478 | 375k | if (Reserved[S.Reg] || 375k Visited[S.Reg]268k ) |
479 | 233k | continue; |
480 | 142k | addDeadRanges(S); |
481 | 142k | Visited[S.Reg] = true; |
482 | 142k | } |
483 | 286k | } |
484 | 2.06k | for (auto &P : LiveMap) |
485 | 17.4k | if (17.4k TargetRegisterInfo::isVirtualRegister(P.first.Reg)17.4k ) |
486 | 60 | addDeadRanges(P.first); |
487 | 2.06k | |
488 | 2.06k | DEBUG(dbgs() << __func__ << ": dead map\n" |
489 | 2.06k | << PrintRangeMap(DeadMap, TRI) << '\n'); |
490 | 2.06k | return DeadMap; |
491 | 2.06k | } |
492 | | |
493 | | raw_ostream &llvm::operator<<(raw_ostream &OS, |
494 | 0 | HexagonBlockRanges::IndexType Idx) { |
495 | 0 | if (Idx == HexagonBlockRanges::IndexType::None) |
496 | 0 | return OS << '-'; |
497 | 0 | if (0 Idx == HexagonBlockRanges::IndexType::Entry0 ) |
498 | 0 | return OS << 'n'; |
499 | 0 | if (0 Idx == HexagonBlockRanges::IndexType::Exit0 ) |
500 | 0 | return OS << 'x'; |
501 | 0 | return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1; |
502 | 0 | } |
503 | | |
504 | | // A mapping to translate between instructions and their indices. |
505 | | raw_ostream &llvm::operator<<(raw_ostream &OS, |
506 | 0 | const HexagonBlockRanges::IndexRange &IR) { |
507 | 0 | OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}'0 : ']'0 ); |
508 | 0 | if (IR.Fixed) |
509 | 0 | OS << '!'; |
510 | 0 | return OS; |
511 | 0 | } |
512 | | |
513 | | raw_ostream &llvm::operator<<(raw_ostream &OS, |
514 | 0 | const HexagonBlockRanges::RangeList &RL) { |
515 | 0 | for (auto &R : RL) |
516 | 0 | OS << R << " "; |
517 | 0 | return OS; |
518 | 0 | } |
519 | | |
520 | | raw_ostream &llvm::operator<<(raw_ostream &OS, |
521 | 0 | const HexagonBlockRanges::InstrIndexMap &M) { |
522 | 0 | for (auto &In : M.Block) { |
523 | 0 | HexagonBlockRanges::IndexType Idx = M.getIndex(&In); |
524 | 0 | OS << Idx << (Idx == M.Last ? ". "0 : " "0 ) << In; |
525 | 0 | } |
526 | 0 | return OS; |
527 | 0 | } |
528 | | |
529 | | raw_ostream &llvm::operator<<(raw_ostream &OS, |
530 | 0 | const HexagonBlockRanges::PrintRangeMap &P) { |
531 | 0 | for (auto &I : P.Map) { |
532 | 0 | const HexagonBlockRanges::RangeList &RL = I.second; |
533 | 0 | OS << PrintReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n"; |
534 | 0 | } |
535 | 0 | return OS; |
536 | 0 | } |