/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveRangeCalc.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LiveRangeCalc.cpp - Calculate live ranges --------------------------===// |
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 | | // Implementation of the LiveRangeCalc class. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "LiveRangeCalc.h" |
14 | | #include "llvm/ADT/BitVector.h" |
15 | | #include "llvm/ADT/STLExtras.h" |
16 | | #include "llvm/ADT/SetVector.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/CodeGen/LiveInterval.h" |
19 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | | #include "llvm/CodeGen/MachineDominators.h" |
21 | | #include "llvm/CodeGen/MachineFunction.h" |
22 | | #include "llvm/CodeGen/MachineInstr.h" |
23 | | #include "llvm/CodeGen/MachineOperand.h" |
24 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
25 | | #include "llvm/CodeGen/SlotIndexes.h" |
26 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
27 | | #include "llvm/MC/LaneBitmask.h" |
28 | | #include "llvm/Support/ErrorHandling.h" |
29 | | #include "llvm/Support/raw_ostream.h" |
30 | | #include <algorithm> |
31 | | #include <cassert> |
32 | | #include <iterator> |
33 | | #include <tuple> |
34 | | #include <utility> |
35 | | |
36 | | using namespace llvm; |
37 | | |
38 | | #define DEBUG_TYPE "regalloc" |
39 | | |
40 | | // Reserve an address that indicates a value that is known to be "undef". |
41 | | static VNInfo UndefVNI(0xbad, SlotIndex()); |
42 | | |
43 | 31.1M | void LiveRangeCalc::resetLiveOutMap() { |
44 | 31.1M | unsigned NumBlocks = MF->getNumBlockIDs(); |
45 | 31.1M | Seen.clear(); |
46 | 31.1M | Seen.resize(NumBlocks); |
47 | 31.1M | EntryInfos.clear(); |
48 | 31.1M | Map.resize(NumBlocks); |
49 | 31.1M | } |
50 | | |
51 | | void LiveRangeCalc::reset(const MachineFunction *mf, |
52 | | SlotIndexes *SI, |
53 | | MachineDominatorTree *MDT, |
54 | 18.3M | VNInfo::Allocator *VNIA) { |
55 | 18.3M | MF = mf; |
56 | 18.3M | MRI = &MF->getRegInfo(); |
57 | 18.3M | Indexes = SI; |
58 | 18.3M | DomTree = MDT; |
59 | 18.3M | Alloc = VNIA; |
60 | 18.3M | resetLiveOutMap(); |
61 | 18.3M | LiveIn.clear(); |
62 | 18.3M | } |
63 | | |
64 | | static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, |
65 | 21.4M | LiveRange &LR, const MachineOperand &MO) { |
66 | 21.4M | const MachineInstr &MI = *MO.getParent(); |
67 | 21.4M | SlotIndex DefIdx = |
68 | 21.4M | Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber()); |
69 | 21.4M | |
70 | 21.4M | // Create the def in LR. This may find an existing def. |
71 | 21.4M | LR.createDeadDef(DefIdx, Alloc); |
72 | 21.4M | } |
73 | | |
74 | 12.8M | void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) { |
75 | 12.8M | assert(MRI && Indexes && "call reset() first"); |
76 | 12.8M | |
77 | 12.8M | // Step 1: Create minimal live segments for every definition of Reg. |
78 | 12.8M | // Visit all def operands. If the same instruction has multiple defs of Reg, |
79 | 12.8M | // createDeadDef() will deduplicate. |
80 | 12.8M | const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); |
81 | 12.8M | unsigned Reg = LI.reg; |
82 | 34.5M | for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { |
83 | 34.5M | if (!MO.isDef() && !MO.readsReg()20.2M ) |
84 | 16.2k | continue; |
85 | 34.5M | |
86 | 34.5M | unsigned SubReg = MO.getSubReg(); |
87 | 34.5M | if (LI.hasSubRanges() || (33.9M SubReg != 033.9M && TrackSubRegs661k )) { |
88 | 796k | LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)659k |
89 | 796k | : MRI->getMaxLaneMaskForVReg(Reg)136k ; |
90 | 796k | // If this is the first time we see a subregister def, initialize |
91 | 796k | // subranges by creating a copy of the main range. |
92 | 796k | if (!LI.hasSubRanges() && !LI.empty()200k ) { |
93 | 93.2k | LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg); |
94 | 93.2k | LI.createSubRangeFrom(*Alloc, ClassMask, LI); |
95 | 93.2k | } |
96 | 796k | |
97 | 796k | LI.refineSubRanges(*Alloc, SubMask, |
98 | 1.06M | [&MO, this](LiveInterval::SubRange &SR) { |
99 | 1.06M | if (MO.isDef()) |
100 | 312k | createDeadDef(*Indexes, *Alloc, SR, MO); |
101 | 1.06M | }, |
102 | 796k | *Indexes, TRI); |
103 | 796k | } |
104 | 34.5M | |
105 | 34.5M | // Create the def in the main liverange. We do not have to do this if |
106 | 34.5M | // subranges are tracked as we recreate the main range later in this case. |
107 | 34.5M | if (MO.isDef() && !LI.hasSubRanges()14.3M ) |
108 | 14.0M | createDeadDef(*Indexes, *Alloc, LI, MO); |
109 | 34.5M | } |
110 | 12.8M | |
111 | 12.8M | // We may have created empty live ranges for partially undefined uses, we |
112 | 12.8M | // can't keep them because we won't find defs in them later. |
113 | 12.8M | LI.removeEmptySubRanges(); |
114 | 12.8M | |
115 | 12.8M | // Step 2: Extend live segments to all uses, constructing SSA form as |
116 | 12.8M | // necessary. |
117 | 12.8M | if (LI.hasSubRanges()) { |
118 | 586k | for (LiveInterval::SubRange &S : LI.subranges()) { |
119 | 586k | LiveRangeCalc SubLRC; |
120 | 586k | SubLRC.reset(MF, Indexes, DomTree, Alloc); |
121 | 586k | SubLRC.extendToUses(S, Reg, S.LaneMask, &LI); |
122 | 586k | } |
123 | 200k | LI.clear(); |
124 | 200k | constructMainRangeFromSubranges(LI); |
125 | 12.6M | } else { |
126 | 12.6M | resetLiveOutMap(); |
127 | 12.6M | extendToUses(LI, Reg, LaneBitmask::getAll()); |
128 | 12.6M | } |
129 | 12.8M | } |
130 | | |
131 | 201k | void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) { |
132 | 201k | // First create dead defs at all defs found in subranges. |
133 | 201k | LiveRange &MainRange = LI; |
134 | 201k | assert(MainRange.segments.empty() && MainRange.valnos.empty() && |
135 | 201k | "Expect empty main liverange"); |
136 | 201k | |
137 | 588k | for (const LiveInterval::SubRange &SR : LI.subranges()) { |
138 | 597k | for (const VNInfo *VNI : SR.valnos) { |
139 | 597k | if (!VNI->isUnused() && !VNI->isPHIDef()597k ) |
140 | 596k | MainRange.createDeadDef(VNI->def, *Alloc); |
141 | 597k | } |
142 | 588k | } |
143 | 201k | resetLiveOutMap(); |
144 | 201k | extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI); |
145 | 201k | } |
146 | | |
147 | 2.10M | void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { |
148 | 2.10M | assert(MRI && Indexes && "call reset() first"); |
149 | 2.10M | |
150 | 2.10M | // Visit all def operands. If the same instruction has multiple defs of Reg, |
151 | 2.10M | // LR.createDeadDef() will deduplicate. |
152 | 2.10M | for (MachineOperand &MO : MRI->def_operands(Reg)) |
153 | 7.06M | createDeadDef(*Indexes, *Alloc, LR, MO); |
154 | 2.10M | } |
155 | | |
156 | | void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask, |
157 | 15.5M | LiveInterval *LI) { |
158 | 15.5M | SmallVector<SlotIndex, 4> Undefs; |
159 | 15.5M | if (LI != nullptr) |
160 | 787k | LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes); |
161 | 15.5M | |
162 | 15.5M | // Visit all operands that read Reg. This may include partial defs. |
163 | 15.5M | bool IsSubRange = !Mask.all(); |
164 | 15.5M | const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); |
165 | 51.1M | for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { |
166 | 51.1M | // Clear all kill flags. They will be reinserted after register allocation |
167 | 51.1M | // by LiveIntervals::addKillFlags(). |
168 | 51.1M | if (MO.isUse()) |
169 | 28.8M | MO.setIsKill(false); |
170 | 51.1M | // MO::readsReg returns "true" for subregister defs. This is for keeping |
171 | 51.1M | // liveness of the entire register (i.e. for the main range of the live |
172 | 51.1M | // interval). For subranges, definitions of non-overlapping subregisters |
173 | 51.1M | // do not count as uses. |
174 | 51.1M | if (!MO.readsReg() || (29.8M IsSubRange29.8M && MO.isDef()2.68M )) |
175 | 22.0M | continue; |
176 | 29.0M | |
177 | 29.0M | unsigned SubReg = MO.getSubReg(); |
178 | 29.0M | if (SubReg != 0) { |
179 | 2.36M | LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg); |
180 | 2.36M | if (MO.isDef()) |
181 | 210k | SLM = ~SLM; |
182 | 2.36M | // Ignore uses not reading the current (sub)range. |
183 | 2.36M | if ((SLM & Mask).none()) |
184 | 1.13M | continue; |
185 | 27.8M | } |
186 | 27.8M | |
187 | 27.8M | // Determine the actual place of the use. |
188 | 27.8M | const MachineInstr *MI = MO.getParent(); |
189 | 27.8M | unsigned OpNo = (&MO - &MI->getOperand(0)); |
190 | 27.8M | SlotIndex UseIdx; |
191 | 27.8M | if (MI->isPHI()) { |
192 | 14.2k | assert(!MO.isDef() && "Cannot handle PHI def of partial register."); |
193 | 14.2k | // The actual place where a phi operand is used is the end of the pred |
194 | 14.2k | // MBB. PHI operands are paired: (Reg, PredMBB). |
195 | 14.2k | UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB()); |
196 | 27.8M | } else { |
197 | 27.8M | // Check for early-clobber redefs. |
198 | 27.8M | bool isEarlyClobber = false; |
199 | 27.8M | unsigned DefIdx; |
200 | 27.8M | if (MO.isDef()) |
201 | 210k | isEarlyClobber = MO.isEarlyClobber(); |
202 | 27.6M | else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) { |
203 | 407k | // FIXME: This would be a lot easier if tied early-clobber uses also |
204 | 407k | // had an early-clobber flag. |
205 | 407k | isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber(); |
206 | 407k | } |
207 | 27.8M | UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber); |
208 | 27.8M | } |
209 | 27.8M | |
210 | 27.8M | // MI is reading Reg. We may have visited MI before if it happens to be |
211 | 27.8M | // reading Reg multiple times. That is OK, extend() is idempotent. |
212 | 27.8M | extend(LR, UseIdx, Reg, Undefs); |
213 | 27.8M | } |
214 | 15.5M | } |
215 | | |
216 | 989k | void LiveRangeCalc::updateFromLiveIns() { |
217 | 989k | LiveRangeUpdater Updater; |
218 | 2.46M | for (const LiveInBlock &I : LiveIn) { |
219 | 2.46M | if (!I.DomNode) |
220 | 820k | continue; |
221 | 1.64M | MachineBasicBlock *MBB = I.DomNode->getBlock(); |
222 | 1.64M | assert(I.Value && "No live-in value found"); |
223 | 1.64M | SlotIndex Start, End; |
224 | 1.64M | std::tie(Start, End) = Indexes->getMBBRange(MBB); |
225 | 1.64M | |
226 | 1.64M | if (I.Kill.isValid()) |
227 | 106k | // Value is killed inside this block. |
228 | 106k | End = I.Kill; |
229 | 1.54M | else { |
230 | 1.54M | // The value is live-through, update LiveOut as well. |
231 | 1.54M | // Defer the Domtree lookup until it is needed. |
232 | 1.54M | assert(Seen.test(MBB->getNumber())); |
233 | 1.54M | Map[MBB] = LiveOutPair(I.Value, nullptr); |
234 | 1.54M | } |
235 | 1.64M | Updater.setDest(&I.LR); |
236 | 1.64M | Updater.add(Start, End, I.Value); |
237 | 1.64M | } |
238 | 989k | LiveIn.clear(); |
239 | 989k | } |
240 | | |
241 | | void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, |
242 | 28.7M | ArrayRef<SlotIndex> Undefs) { |
243 | 28.7M | assert(Use.isValid() && "Invalid SlotIndex"); |
244 | 28.7M | assert(Indexes && "Missing SlotIndexes"); |
245 | 28.7M | assert(DomTree && "Missing dominator tree"); |
246 | 28.7M | |
247 | 28.7M | MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot()); |
248 | 28.7M | assert(UseMBB && "No MBB at Use"); |
249 | 28.7M | |
250 | 28.7M | // Is there a def in the same MBB we can extend? |
251 | 28.7M | auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use); |
252 | 28.7M | if (EP.first != nullptr || EP.second4.09M ) |
253 | 24.6M | return; |
254 | 4.09M | |
255 | 4.09M | // Find the single reaching def, or determine if Use is jointly dominated by |
256 | 4.09M | // multiple values, and we may need to create even more phi-defs to preserve |
257 | 4.09M | // VNInfo SSA form. Perform a search for all predecessor blocks where we |
258 | 4.09M | // know the dominating VNInfo. |
259 | 4.09M | if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs)) |
260 | 3.42M | return; |
261 | 668k | |
262 | 668k | // When there were multiple different values, we may need new PHIs. |
263 | 668k | calculateValues(); |
264 | 668k | } |
265 | | |
266 | | // This function is called by a client after using the low-level API to add |
267 | | // live-out and live-in blocks. The unique value optimization is not |
268 | | // available, SplitEditor::transferValues handles that case directly anyway. |
269 | 989k | void LiveRangeCalc::calculateValues() { |
270 | 989k | assert(Indexes && "Missing SlotIndexes"); |
271 | 989k | assert(DomTree && "Missing dominator tree"); |
272 | 989k | updateSSA(); |
273 | 989k | updateFromLiveIns(); |
274 | 989k | } |
275 | | |
276 | | bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs, |
277 | | MachineBasicBlock &MBB, BitVector &DefOnEntry, |
278 | 1.02k | BitVector &UndefOnEntry) { |
279 | 1.02k | unsigned BN = MBB.getNumber(); |
280 | 1.02k | if (DefOnEntry[BN]) |
281 | 197 | return true; |
282 | 824 | if (UndefOnEntry[BN]) |
283 | 1 | return false; |
284 | 823 | |
285 | 823 | auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool { |
286 | 819 | for (MachineBasicBlock *S : B.successors()) |
287 | 1.34k | DefOnEntry[S->getNumber()] = true; |
288 | 819 | DefOnEntry[BN] = true; |
289 | 819 | return true; |
290 | 819 | }; |
291 | 823 | |
292 | 823 | SetVector<unsigned> WorkList; |
293 | 823 | // Checking if the entry of MBB is reached by some def: add all predecessors |
294 | 823 | // that are potentially defined-on-exit to the work list. |
295 | 823 | for (MachineBasicBlock *P : MBB.predecessors()) |
296 | 1.46k | WorkList.insert(P->getNumber()); |
297 | 823 | |
298 | 968 | for (unsigned i = 0; i != WorkList.size(); ++i145 ) { |
299 | 964 | // Determine if the exit from the block is reached by some def. |
300 | 964 | unsigned N = WorkList[i]; |
301 | 964 | MachineBasicBlock &B = *MF->getBlockNumbered(N); |
302 | 964 | if (Seen[N]) { |
303 | 964 | const LiveOutPair &LOB = Map[&B]; |
304 | 964 | if (LOB.first != nullptr && LOB.first != &UndefVNI668 ) |
305 | 663 | return MarkDefined(B); |
306 | 301 | } |
307 | 301 | SlotIndex Begin, End; |
308 | 301 | std::tie(Begin, End) = Indexes->getMBBRange(&B); |
309 | 301 | // Treat End as not belonging to B. |
310 | 301 | // If LR has a segment S that starts at the next block, i.e. [End, ...), |
311 | 301 | // std::upper_bound will return the segment following S. Instead, |
312 | 301 | // S should be treated as the first segment that does not overlap B. |
313 | 301 | LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(), |
314 | 301 | End.getPrevSlot()); |
315 | 301 | if (UB != LR.begin()) { |
316 | 294 | LiveRange::Segment &Seg = *std::prev(UB); |
317 | 294 | if (Seg.end > Begin) { |
318 | 0 | // There is a segment that overlaps B. If the range is not explicitly |
319 | 0 | // undefined between the end of the segment and the end of the block, |
320 | 0 | // treat the block as defined on exit. If it is, go to the next block |
321 | 0 | // on the work list. |
322 | 0 | if (LR.isUndefIn(Undefs, Seg.end, End)) |
323 | 0 | continue; |
324 | 0 | return MarkDefined(B); |
325 | 0 | } |
326 | 294 | } |
327 | 301 | |
328 | 301 | // No segment overlaps with this block. If this block is not defined on |
329 | 301 | // entry, or it undefines the range, do not process its predecessors. |
330 | 301 | if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) { |
331 | 5 | UndefOnEntry[N] = true; |
332 | 5 | continue; |
333 | 5 | } |
334 | 296 | if (DefOnEntry[N]) |
335 | 156 | return MarkDefined(B); |
336 | 140 | |
337 | 140 | // Still don't know: add all predecessors to the work list. |
338 | 140 | for (MachineBasicBlock *P : B.predecessors()) |
339 | 266 | WorkList.insert(P->getNumber()); |
340 | 140 | } |
341 | 823 | |
342 | 823 | UndefOnEntry[BN] = true; |
343 | 4 | return false; |
344 | 823 | } |
345 | | |
346 | | bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, |
347 | | SlotIndex Use, unsigned PhysReg, |
348 | 4.09M | ArrayRef<SlotIndex> Undefs) { |
349 | 4.09M | unsigned UseMBBNum = UseMBB.getNumber(); |
350 | 4.09M | |
351 | 4.09M | // Block numbers where LR should be live-in. |
352 | 4.09M | SmallVector<unsigned, 16> WorkList(1, UseMBBNum); |
353 | 4.09M | |
354 | 4.09M | // Remember if we have seen more than one value. |
355 | 4.09M | bool UniqueVNI = true; |
356 | 4.09M | VNInfo *TheVNI = nullptr; |
357 | 4.09M | |
358 | 4.09M | bool FoundUndef = false; |
359 | 4.09M | |
360 | 4.09M | // Using Seen as a visited set, perform a BFS for all reaching defs. |
361 | 31.9M | for (unsigned i = 0; i != WorkList.size(); ++i27.8M ) { |
362 | 27.8M | MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); |
363 | 27.8M | |
364 | | #ifndef NDEBUG |
365 | | if (MBB->pred_empty()) { |
366 | | MBB->getParent()->verify(); |
367 | | errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo()) |
368 | | << " does not have a corresponding definition on every path:\n"; |
369 | | const MachineInstr *MI = Indexes->getInstructionFromIndex(Use); |
370 | | if (MI != nullptr) |
371 | | errs() << Use << " " << *MI; |
372 | | report_fatal_error("Use not jointly dominated by defs."); |
373 | | } |
374 | | |
375 | | if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && |
376 | | !MBB->isLiveIn(PhysReg)) { |
377 | | MBB->getParent()->verify(); |
378 | | const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); |
379 | | errs() << "The register " << printReg(PhysReg, TRI) |
380 | | << " needs to be live in to " << printMBBReference(*MBB) |
381 | | << ", but is missing from the live-in list.\n"; |
382 | | report_fatal_error("Invalid global physical register"); |
383 | | } |
384 | | #endif |
385 | | FoundUndef |= MBB->pred_empty(); |
386 | 27.8M | |
387 | 41.1M | for (MachineBasicBlock *Pred : MBB->predecessors()) { |
388 | 41.1M | // Is this a known live-out block? |
389 | 41.1M | if (Seen.test(Pred->getNumber())) { |
390 | 12.3M | if (VNInfo *VNI = Map[Pred].first) { |
391 | 1.87M | if (TheVNI && TheVNI != VNI948k ) |
392 | 15.0k | UniqueVNI = false; |
393 | 1.87M | TheVNI = VNI; |
394 | 1.87M | } |
395 | 12.3M | continue; |
396 | 12.3M | } |
397 | 28.8M | |
398 | 28.8M | SlotIndex Start, End; |
399 | 28.8M | std::tie(Start, End) = Indexes->getMBBRange(Pred); |
400 | 28.8M | |
401 | 28.8M | // First time we see Pred. Try to determine the live-out value, but set |
402 | 28.8M | // it as null if Pred is live-through with an unknown value. |
403 | 28.8M | auto EP = LR.extendInBlock(Undefs, Start, End); |
404 | 28.8M | VNInfo *VNI = EP.first; |
405 | 28.8M | FoundUndef |= EP.second; |
406 | 28.8M | setLiveOutValue(Pred, EP.second ? &UndefVNI7 : VNI28.8M ); |
407 | 28.8M | if (VNI) { |
408 | 4.34M | if (TheVNI && TheVNI != VNI1.17M ) |
409 | 962k | UniqueVNI = false; |
410 | 4.34M | TheVNI = VNI; |
411 | 4.34M | } |
412 | 28.8M | if (VNI || EP.second24.5M ) |
413 | 4.34M | continue; |
414 | 24.5M | |
415 | 24.5M | // No, we need a live-in value for Pred as well |
416 | 24.5M | if (Pred != &UseMBB) |
417 | 23.7M | WorkList.push_back(Pred->getNumber()); |
418 | 729k | else |
419 | 729k | // Loopback to UseMBB, so value is really live through. |
420 | 729k | Use = SlotIndex(); |
421 | 24.5M | } |
422 | 27.8M | } |
423 | 4.09M | |
424 | 4.09M | LiveIn.clear(); |
425 | 4.09M | FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI4.09M ); |
426 | 4.09M | if (!Undefs.empty() && FoundUndef3.45k ) |
427 | 8 | UniqueVNI = false; |
428 | 4.09M | |
429 | 4.09M | // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but |
430 | 4.09M | // neither require it. Skip the sorting overhead for small updates. |
431 | 4.09M | if (WorkList.size() > 4) |
432 | 980k | array_pod_sort(WorkList.begin(), WorkList.end()); |
433 | 4.09M | |
434 | 4.09M | // If a unique reaching def was found, blit in the live ranges immediately. |
435 | 4.09M | if (UniqueVNI) { |
436 | 3.42M | assert(TheVNI != nullptr && TheVNI != &UndefVNI); |
437 | 3.42M | LiveRangeUpdater Updater(&LR); |
438 | 26.5M | for (unsigned BN : WorkList) { |
439 | 26.5M | SlotIndex Start, End; |
440 | 26.5M | std::tie(Start, End) = Indexes->getMBBRange(BN); |
441 | 26.5M | // Trim the live range in UseMBB. |
442 | 26.5M | if (BN == UseMBBNum && Use.isValid()3.42M ) |
443 | 2.71M | End = Use; |
444 | 23.8M | else |
445 | 23.8M | Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr); |
446 | 26.5M | Updater.add(Start, End, TheVNI); |
447 | 26.5M | } |
448 | 3.42M | return true; |
449 | 3.42M | } |
450 | 668k | |
451 | 668k | // Prepare the defined/undefined bit vectors. |
452 | 668k | EntryInfoMap::iterator Entry; |
453 | 668k | bool DidInsert; |
454 | 668k | std::tie(Entry, DidInsert) = EntryInfos.insert( |
455 | 668k | std::make_pair(&LR, std::make_pair(BitVector(), BitVector()))); |
456 | 668k | if (DidInsert) { |
457 | 660k | // Initialize newly inserted entries. |
458 | 660k | unsigned N = MF->getNumBlockIDs(); |
459 | 660k | Entry->second.first.resize(N); |
460 | 660k | Entry->second.second.resize(N); |
461 | 660k | } |
462 | 668k | BitVector &DefOnEntry = Entry->second.first; |
463 | 668k | BitVector &UndefOnEntry = Entry->second.second; |
464 | 668k | |
465 | 668k | // Multiple values were found, so transfer the work list to the LiveIn array |
466 | 668k | // where UpdateSSA will use it as a work list. |
467 | 668k | LiveIn.reserve(WorkList.size()); |
468 | 1.33M | for (unsigned BN : WorkList) { |
469 | 1.33M | MachineBasicBlock *MBB = MF->getBlockNumbered(BN); |
470 | 1.33M | if (!Undefs.empty() && |
471 | 1.33M | !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry)1.02k ) |
472 | 5 | continue; |
473 | 1.33M | addLiveInBlock(LR, DomTree->getNode(MBB)); |
474 | 1.33M | if (MBB == &UseMBB) |
475 | 668k | LiveIn.back().Kill = Use; |
476 | 1.33M | } |
477 | 668k | |
478 | 668k | return false; |
479 | 668k | } |
480 | | |
481 | | // This is essentially the same iterative algorithm that SSAUpdater uses, |
482 | | // except we already have a dominator tree, so we don't have to recompute it. |
483 | 989k | void LiveRangeCalc::updateSSA() { |
484 | 989k | assert(Indexes && "Missing SlotIndexes"); |
485 | 989k | assert(DomTree && "Missing dominator tree"); |
486 | 989k | |
487 | 989k | // Interate until convergence. |
488 | 989k | bool Changed; |
489 | 1.78M | do { |
490 | 1.78M | Changed = false; |
491 | 1.78M | // Propagate live-out values down the dominator tree, inserting phi-defs |
492 | 1.78M | // when necessary. |
493 | 6.68M | for (LiveInBlock &I : LiveIn) { |
494 | 6.68M | MachineDomTreeNode *Node = I.DomNode; |
495 | 6.68M | // Skip block if the live-in value has already been determined. |
496 | 6.68M | if (!Node) |
497 | 955k | continue; |
498 | 5.72M | MachineBasicBlock *MBB = Node->getBlock(); |
499 | 5.72M | MachineDomTreeNode *IDom = Node->getIDom(); |
500 | 5.72M | LiveOutPair IDomValue; |
501 | 5.72M | |
502 | 5.72M | // We need a live-in value to a block with no immediate dominator? |
503 | 5.72M | // This is probably an unreachable block that has survived somehow. |
504 | 5.72M | bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); |
505 | 5.72M | |
506 | 5.72M | // IDom dominates all of our predecessors, but it may not be their |
507 | 5.72M | // immediate dominator. Check if any of them have live-out values that are |
508 | 5.72M | // properly dominated by IDom. If so, we need a phi-def here. |
509 | 5.72M | if (!needPHI) { |
510 | 5.45M | IDomValue = Map[IDom->getBlock()]; |
511 | 5.45M | |
512 | 5.45M | // Cache the DomTree node that defined the value. |
513 | 5.45M | if (IDomValue.first && IDomValue.first != &UndefVNI5.32M && |
514 | 5.45M | !IDomValue.second5.32M ) { |
515 | 520k | Map[IDom->getBlock()].second = IDomValue.second = |
516 | 520k | DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); |
517 | 520k | } |
518 | 5.45M | |
519 | 7.93M | for (MachineBasicBlock *Pred : MBB->predecessors()) { |
520 | 7.93M | LiveOutPair &Value = Map[Pred]; |
521 | 7.93M | if (!Value.first || Value.first == IDomValue.first7.44M ) |
522 | 7.34M | continue; |
523 | 589k | if (Value.first == &UndefVNI) { |
524 | 1 | needPHI = true; |
525 | 1 | break; |
526 | 1 | } |
527 | 589k | |
528 | 589k | // Cache the DomTree node that defined the value. |
529 | 589k | if (!Value.second) |
530 | 451k | Value.second = |
531 | 451k | DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); |
532 | 589k | |
533 | 589k | // This predecessor is carrying something other than IDomValue. |
534 | 589k | // It could be because IDomValue hasn't propagated yet, or it could be |
535 | 589k | // because MBB is in the dominance frontier of that value. |
536 | 589k | if (DomTree->dominates(IDom, Value.second)) { |
537 | 543k | needPHI = true; |
538 | 543k | break; |
539 | 543k | } |
540 | 589k | } |
541 | 5.45M | } |
542 | 5.72M | |
543 | 5.72M | // The value may be live-through even if Kill is set, as can happen when |
544 | 5.72M | // we are called from extendRange. In that case LiveOutSeen is true, and |
545 | 5.72M | // LiveOut indicates a foreign or missing value. |
546 | 5.72M | LiveOutPair &LOP = Map[MBB]; |
547 | 5.72M | |
548 | 5.72M | // Create a phi-def if required. |
549 | 5.72M | if (needPHI) { |
550 | 820k | Changed = true; |
551 | 820k | assert(Alloc && "Need VNInfo allocator to create PHI-defs"); |
552 | 820k | SlotIndex Start, End; |
553 | 820k | std::tie(Start, End) = Indexes->getMBBRange(MBB); |
554 | 820k | LiveRange &LR = I.LR; |
555 | 820k | VNInfo *VNI = LR.getNextValue(Start, *Alloc); |
556 | 820k | I.Value = VNI; |
557 | 820k | // This block is done, we know the final value. |
558 | 820k | I.DomNode = nullptr; |
559 | 820k | |
560 | 820k | // Add liveness since updateFromLiveIns now skips this node. |
561 | 820k | if (I.Kill.isValid()) { |
562 | 670k | if (VNI) |
563 | 670k | LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); |
564 | 670k | } else { |
565 | 150k | if (VNI) |
566 | 150k | LR.addSegment(LiveInterval::Segment(Start, End, VNI)); |
567 | 150k | LOP = LiveOutPair(VNI, Node); |
568 | 150k | } |
569 | 4.90M | } else if (IDomValue.first && IDomValue.first != &UndefVNI4.79M ) { |
570 | 4.79M | // No phi-def here. Remember incoming value. |
571 | 4.79M | I.Value = IDomValue.first; |
572 | 4.79M | |
573 | 4.79M | // If the IDomValue is killed in the block, don't propagate through. |
574 | 4.79M | if (I.Kill.isValid()) |
575 | 260k | continue; |
576 | 4.53M | |
577 | 4.53M | // Propagate IDomValue if it isn't killed: |
578 | 4.53M | // MBB is live-out and doesn't define its own value. |
579 | 4.53M | if (LOP.first == IDomValue.first) |
580 | 2.56M | continue; |
581 | 1.96M | Changed = true; |
582 | 1.96M | LOP = IDomValue; |
583 | 1.96M | } |
584 | 5.72M | } |
585 | 1.78M | } while (Changed); |
586 | 989k | } |
587 | | |
588 | | bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB, |
589 | | ArrayRef<SlotIndex> Defs, |
590 | 0 | const SlotIndexes &Indexes) { |
591 | 0 | const MachineFunction &MF = *MBB->getParent(); |
592 | 0 | BitVector DefBlocks(MF.getNumBlockIDs()); |
593 | 0 | for (SlotIndex I : Defs) |
594 | 0 | DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber()); |
595 | 0 |
|
596 | 0 | SetVector<unsigned> PredQueue; |
597 | 0 | PredQueue.insert(MBB->getNumber()); |
598 | 0 | for (unsigned i = 0; i != PredQueue.size(); ++i) { |
599 | 0 | unsigned BN = PredQueue[i]; |
600 | 0 | if (DefBlocks[BN]) |
601 | 0 | return true; |
602 | 0 | const MachineBasicBlock *B = MF.getBlockNumbered(BN); |
603 | 0 | for (const MachineBasicBlock *P : B->predecessors()) |
604 | 0 | PredQueue.insert(P->getNumber()); |
605 | 0 | } |
606 | 0 | return false; |
607 | 0 | } |