1 | //===- SplitKit.cpp - Toolkit for splitting 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 | // This file contains the SplitAnalysis class as well as mutator functions for |
10 | // live range splitting. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #include "SplitKit.h" |
15 | #include "llvm/ADT/STLExtras.h" |
16 | #include "llvm/ADT/Statistic.h" |
17 | #include "llvm/Analysis/AliasAnalysis.h" |
18 | #include "llvm/CodeGen/LiveRangeEdit.h" |
19 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
20 | #include "llvm/CodeGen/MachineDominators.h" |
21 | #include "llvm/CodeGen/MachineInstr.h" |
22 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
23 | #include "llvm/CodeGen/MachineLoopInfo.h" |
24 | #include "llvm/CodeGen/MachineOperand.h" |
25 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
26 | #include "llvm/CodeGen/TargetInstrInfo.h" |
27 | #include "llvm/CodeGen/TargetOpcodes.h" |
28 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
29 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
30 | #include "llvm/CodeGen/VirtRegMap.h" |
31 | #include "llvm/Config/llvm-config.h" |
32 | #include "llvm/IR/DebugLoc.h" |
33 | #include "llvm/Support/Allocator.h" |
34 | #include "llvm/Support/BlockFrequency.h" |
35 | #include "llvm/Support/Debug.h" |
36 | #include "llvm/Support/ErrorHandling.h" |
37 | #include "llvm/Support/raw_ostream.h" |
38 | #include <algorithm> |
39 | #include <cassert> |
40 | #include <iterator> |
41 | #include <limits> |
42 | #include <tuple> |
43 | |
44 | using namespace llvm; |
45 | |
46 | #define DEBUG_TYPE "regalloc" |
47 | |
48 | static cl::opt<bool> |
49 | EnableLoopIVHeuristic("enable-split-loopiv-heuristic" , |
50 | cl::desc("Enable loop iv regalloc heuristic" ), |
51 | cl::init(Val: true)); |
52 | |
53 | STATISTIC(NumFinished, "Number of splits finished" ); |
54 | STATISTIC(NumSimple, "Number of splits that were simple" ); |
55 | STATISTIC(NumCopies, "Number of copies inserted for splitting" ); |
56 | STATISTIC(NumRemats, "Number of rematerialized defs for splitting" ); |
57 | |
58 | //===----------------------------------------------------------------------===// |
59 | // Last Insert Point Analysis |
60 | //===----------------------------------------------------------------------===// |
61 | |
62 | InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, |
63 | unsigned BBNum) |
64 | : LIS(lis), LastInsertPoint(BBNum) {} |
65 | |
66 | SlotIndex |
67 | InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI, |
68 | const MachineBasicBlock &MBB) { |
69 | unsigned Num = MBB.getNumber(); |
70 | std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num]; |
71 | SlotIndex MBBEnd = LIS.getMBBEndIdx(mbb: &MBB); |
72 | |
73 | SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors; |
74 | bool EHPadSuccessor = false; |
75 | for (const MachineBasicBlock *SMBB : MBB.successors()) { |
76 | if (SMBB->isEHPad()) { |
77 | ExceptionalSuccessors.push_back(Elt: SMBB); |
78 | EHPadSuccessor = true; |
79 | } else if (SMBB->isInlineAsmBrIndirectTarget()) |
80 | ExceptionalSuccessors.push_back(Elt: SMBB); |
81 | } |
82 | |
83 | // Compute insert points on the first call. The pair is independent of the |
84 | // current live interval. |
85 | if (!LIP.first.isValid()) { |
86 | MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator(); |
87 | if (FirstTerm == MBB.end()) |
88 | LIP.first = MBBEnd; |
89 | else |
90 | LIP.first = LIS.getInstructionIndex(Instr: *FirstTerm); |
91 | |
92 | // If there is a landing pad or inlineasm_br successor, also find the |
93 | // instruction. If there is no such instruction, we don't need to do |
94 | // anything special. We assume there cannot be multiple instructions that |
95 | // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we |
96 | // assume that if there are any, they will be after any other call |
97 | // instructions in the block. |
98 | if (ExceptionalSuccessors.empty()) |
99 | return LIP.first; |
100 | for (const MachineInstr &MI : llvm::reverse(C: MBB)) { |
101 | if ((EHPadSuccessor && MI.isCall()) || |
102 | MI.getOpcode() == TargetOpcode::INLINEASM_BR) { |
103 | LIP.second = LIS.getInstructionIndex(Instr: MI); |
104 | break; |
105 | } |
106 | } |
107 | } |
108 | |
109 | // If CurLI is live into a landing pad successor, move the last insert point |
110 | // back to the call that may throw. |
111 | if (!LIP.second) |
112 | return LIP.first; |
113 | |
114 | if (none_of(Range&: ExceptionalSuccessors, P: [&](const MachineBasicBlock *EHPad) { |
115 | return LIS.isLiveInToMBB(LR: CurLI, mbb: EHPad); |
116 | })) |
117 | return LIP.first; |
118 | |
119 | // Find the value leaving MBB. |
120 | const VNInfo *VNI = CurLI.getVNInfoBefore(Idx: MBBEnd); |
121 | if (!VNI) |
122 | return LIP.first; |
123 | |
124 | // The def of statepoint instruction is a gc relocation and it should be alive |
125 | // in landing pad. So we cannot split interval after statepoint instruction. |
126 | if (SlotIndex::isSameInstr(A: VNI->def, B: LIP.second)) |
127 | if (auto *I = LIS.getInstructionFromIndex(index: LIP.second)) |
128 | if (I->getOpcode() == TargetOpcode::STATEPOINT) |
129 | return LIP.second; |
130 | |
131 | // If the value leaving MBB was defined after the call in MBB, it can't |
132 | // really be live-in to the landing pad. This can happen if the landing pad |
133 | // has a PHI, and this register is undef on the exceptional edge. |
134 | if (!SlotIndex::isEarlierInstr(A: VNI->def, B: LIP.second) && VNI->def < MBBEnd) |
135 | return LIP.first; |
136 | |
137 | // Value is properly live-in to the landing pad. |
138 | // Only allow inserts before the call. |
139 | return LIP.second; |
140 | } |
141 | |
142 | MachineBasicBlock::iterator |
143 | InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI, |
144 | MachineBasicBlock &MBB) { |
145 | SlotIndex LIP = getLastInsertPoint(CurLI, MBB); |
146 | if (LIP == LIS.getMBBEndIdx(mbb: &MBB)) |
147 | return MBB.end(); |
148 | return LIS.getInstructionFromIndex(index: LIP); |
149 | } |
150 | |
151 | //===----------------------------------------------------------------------===// |
152 | // Split Analysis |
153 | //===----------------------------------------------------------------------===// |
154 | |
155 | SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, |
156 | const MachineLoopInfo &mli) |
157 | : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli), |
158 | TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {} |
159 | |
160 | void SplitAnalysis::clear() { |
161 | UseSlots.clear(); |
162 | UseBlocks.clear(); |
163 | ThroughBlocks.clear(); |
164 | CurLI = nullptr; |
165 | } |
166 | |
167 | /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. |
168 | void SplitAnalysis::analyzeUses() { |
169 | assert(UseSlots.empty() && "Call clear first" ); |
170 | |
171 | // First get all the defs from the interval values. This provides the correct |
172 | // slots for early clobbers. |
173 | for (const VNInfo *VNI : CurLI->valnos) |
174 | if (!VNI->isPHIDef() && !VNI->isUnused()) |
175 | UseSlots.push_back(Elt: VNI->def); |
176 | |
177 | // Get use slots form the use-def chain. |
178 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
179 | for (MachineOperand &MO : MRI.use_nodbg_operands(Reg: CurLI->reg())) |
180 | if (!MO.isUndef()) |
181 | UseSlots.push_back(Elt: LIS.getInstructionIndex(Instr: *MO.getParent()).getRegSlot()); |
182 | |
183 | array_pod_sort(Start: UseSlots.begin(), End: UseSlots.end()); |
184 | |
185 | // Remove duplicates, keeping the smaller slot for each instruction. |
186 | // That is what we want for early clobbers. |
187 | UseSlots.erase(CS: std::unique(first: UseSlots.begin(), last: UseSlots.end(), |
188 | binary_pred: SlotIndex::isSameInstr), |
189 | CE: UseSlots.end()); |
190 | |
191 | // Compute per-live block info. |
192 | calcLiveBlockInfo(); |
193 | |
194 | LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in " |
195 | << UseBlocks.size() << " blocks, through " |
196 | << NumThroughBlocks << " blocks.\n" ); |
197 | } |
198 | |
199 | /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks |
200 | /// where CurLI is live. |
201 | void SplitAnalysis::calcLiveBlockInfo() { |
202 | ThroughBlocks.resize(N: MF.getNumBlockIDs()); |
203 | NumThroughBlocks = NumGapBlocks = 0; |
204 | if (CurLI->empty()) |
205 | return; |
206 | |
207 | LiveInterval::const_iterator LVI = CurLI->begin(); |
208 | LiveInterval::const_iterator LVE = CurLI->end(); |
209 | |
210 | SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; |
211 | UseI = UseSlots.begin(); |
212 | UseE = UseSlots.end(); |
213 | |
214 | // Loop over basic blocks where CurLI is live. |
215 | MachineFunction::iterator MFI = |
216 | LIS.getMBBFromIndex(index: LVI->start)->getIterator(); |
217 | while (true) { |
218 | BlockInfo BI; |
219 | BI.MBB = &*MFI; |
220 | SlotIndex Start, Stop; |
221 | std::tie(args&: Start, args&: Stop) = LIS.getSlotIndexes()->getMBBRange(MBB: BI.MBB); |
222 | |
223 | // If the block contains no uses, the range must be live through. At one |
224 | // point, RegisterCoalescer could create dangling ranges that ended |
225 | // mid-block. |
226 | if (UseI == UseE || *UseI >= Stop) { |
227 | ++NumThroughBlocks; |
228 | ThroughBlocks.set(BI.MBB->getNumber()); |
229 | // The range shouldn't end mid-block if there are no uses. This shouldn't |
230 | // happen. |
231 | assert(LVI->end >= Stop && "range ends mid block with no uses" ); |
232 | } else { |
233 | // This block has uses. Find the first and last uses in the block. |
234 | BI.FirstInstr = *UseI; |
235 | assert(BI.FirstInstr >= Start); |
236 | do ++UseI; |
237 | while (UseI != UseE && *UseI < Stop); |
238 | BI.LastInstr = UseI[-1]; |
239 | assert(BI.LastInstr < Stop); |
240 | |
241 | // LVI is the first live segment overlapping MBB. |
242 | BI.LiveIn = LVI->start <= Start; |
243 | |
244 | // When not live in, the first use should be a def. |
245 | if (!BI.LiveIn) { |
246 | assert(LVI->start == LVI->valno->def && "Dangling Segment start" ); |
247 | assert(LVI->start == BI.FirstInstr && "First instr should be a def" ); |
248 | BI.FirstDef = BI.FirstInstr; |
249 | } |
250 | |
251 | // Look for gaps in the live range. |
252 | BI.LiveOut = true; |
253 | while (LVI->end < Stop) { |
254 | SlotIndex LastStop = LVI->end; |
255 | if (++LVI == LVE || LVI->start >= Stop) { |
256 | BI.LiveOut = false; |
257 | BI.LastInstr = LastStop; |
258 | break; |
259 | } |
260 | |
261 | if (LastStop < LVI->start) { |
262 | // There is a gap in the live range. Create duplicate entries for the |
263 | // live-in snippet and the live-out snippet. |
264 | ++NumGapBlocks; |
265 | |
266 | // Push the Live-in part. |
267 | BI.LiveOut = false; |
268 | UseBlocks.push_back(Elt: BI); |
269 | UseBlocks.back().LastInstr = LastStop; |
270 | |
271 | // Set up BI for the live-out part. |
272 | BI.LiveIn = false; |
273 | BI.LiveOut = true; |
274 | BI.FirstInstr = BI.FirstDef = LVI->start; |
275 | } |
276 | |
277 | // A Segment that starts in the middle of the block must be a def. |
278 | assert(LVI->start == LVI->valno->def && "Dangling Segment start" ); |
279 | if (!BI.FirstDef) |
280 | BI.FirstDef = LVI->start; |
281 | } |
282 | |
283 | UseBlocks.push_back(Elt: BI); |
284 | |
285 | // LVI is now at LVE or LVI->end >= Stop. |
286 | if (LVI == LVE) |
287 | break; |
288 | } |
289 | |
290 | // Live segment ends exactly at Stop. Move to the next segment. |
291 | if (LVI->end == Stop && ++LVI == LVE) |
292 | break; |
293 | |
294 | // Pick the next basic block. |
295 | if (LVI->start < Stop) |
296 | ++MFI; |
297 | else |
298 | MFI = LIS.getMBBFromIndex(index: LVI->start)->getIterator(); |
299 | } |
300 | |
301 | LooksLikeLoopIV = EnableLoopIVHeuristic && UseBlocks.size() == 2 && |
302 | any_of(Range&: UseBlocks, P: [this](BlockInfo &BI) { |
303 | MachineLoop *L = Loops.getLoopFor(BB: BI.MBB); |
304 | return BI.LiveIn && BI.LiveOut && BI.FirstDef && L && |
305 | L->isLoopLatch(BB: BI.MBB); |
306 | }); |
307 | |
308 | assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count" ); |
309 | } |
310 | |
311 | unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { |
312 | if (cli->empty()) |
313 | return 0; |
314 | LiveInterval *li = const_cast<LiveInterval*>(cli); |
315 | LiveInterval::iterator LVI = li->begin(); |
316 | LiveInterval::iterator LVE = li->end(); |
317 | unsigned Count = 0; |
318 | |
319 | // Loop over basic blocks where li is live. |
320 | MachineFunction::const_iterator MFI = |
321 | LIS.getMBBFromIndex(index: LVI->start)->getIterator(); |
322 | SlotIndex Stop = LIS.getMBBEndIdx(mbb: &*MFI); |
323 | while (true) { |
324 | ++Count; |
325 | LVI = li->advanceTo(I: LVI, Pos: Stop); |
326 | if (LVI == LVE) |
327 | return Count; |
328 | do { |
329 | ++MFI; |
330 | Stop = LIS.getMBBEndIdx(mbb: &*MFI); |
331 | } while (Stop <= LVI->start); |
332 | } |
333 | } |
334 | |
335 | bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { |
336 | Register OrigReg = VRM.getOriginal(VirtReg: CurLI->reg()); |
337 | const LiveInterval &Orig = LIS.getInterval(Reg: OrigReg); |
338 | assert(!Orig.empty() && "Splitting empty interval?" ); |
339 | LiveInterval::const_iterator I = Orig.find(Pos: Idx); |
340 | |
341 | // Range containing Idx should begin at Idx. |
342 | if (I != Orig.end() && I->start <= Idx) |
343 | return I->start == Idx; |
344 | |
345 | // Range does not contain Idx, previous must end at Idx. |
346 | return I != Orig.begin() && (--I)->end == Idx; |
347 | } |
348 | |
349 | void SplitAnalysis::analyze(const LiveInterval *li) { |
350 | clear(); |
351 | CurLI = li; |
352 | analyzeUses(); |
353 | } |
354 | |
355 | //===----------------------------------------------------------------------===// |
356 | // Split Editor |
357 | //===----------------------------------------------------------------------===// |
358 | |
359 | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. |
360 | SplitEditor::SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM, |
361 | MachineDominatorTree &MDT, |
362 | MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI) |
363 | : SA(SA), LIS(LIS), VRM(VRM), MRI(VRM.getMachineFunction().getRegInfo()), |
364 | MDT(MDT), TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()), |
365 | TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()), |
366 | MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {} |
367 | |
368 | void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { |
369 | Edit = &LRE; |
370 | SpillMode = SM; |
371 | OpenIdx = 0; |
372 | RegAssign.clear(); |
373 | Values.clear(); |
374 | |
375 | // Reset the LiveIntervalCalc instances needed for this spill mode. |
376 | LICalc[0].reset(mf: &VRM.getMachineFunction(), SI: LIS.getSlotIndexes(), MDT: &MDT, |
377 | VNIA: &LIS.getVNInfoAllocator()); |
378 | if (SpillMode) |
379 | LICalc[1].reset(mf: &VRM.getMachineFunction(), SI: LIS.getSlotIndexes(), MDT: &MDT, |
380 | VNIA: &LIS.getVNInfoAllocator()); |
381 | |
382 | Edit->anyRematerializable(); |
383 | } |
384 | |
385 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
386 | LLVM_DUMP_METHOD void SplitEditor::dump() const { |
387 | if (RegAssign.empty()) { |
388 | dbgs() << " empty\n" ; |
389 | return; |
390 | } |
391 | |
392 | for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) |
393 | dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); |
394 | dbgs() << '\n'; |
395 | } |
396 | #endif |
397 | |
398 | /// Find a subrange corresponding to the exact lane mask @p LM in the live |
399 | /// interval @p LI. The interval @p LI is assumed to contain such a subrange. |
400 | /// This function is used to find corresponding subranges between the |
401 | /// original interval and the new intervals. |
402 | template <typename T> auto &getSubrangeImpl(LaneBitmask LM, T &LI) { |
403 | for (auto &S : LI.subranges()) |
404 | if (S.LaneMask == LM) |
405 | return S; |
406 | llvm_unreachable("SubRange for this mask not found" ); |
407 | } |
408 | |
409 | LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM, |
410 | LiveInterval &LI) { |
411 | return getSubrangeImpl(LM, LI); |
412 | } |
413 | |
414 | const LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM, |
415 | const LiveInterval &LI) { |
416 | return getSubrangeImpl(LM, LI); |
417 | } |
418 | |
419 | /// Find a subrange corresponding to the lane mask @p LM, or a superset of it, |
420 | /// in the live interval @p LI. The interval @p LI is assumed to contain such |
421 | /// a subrange. This function is used to find corresponding subranges between |
422 | /// the original interval and the new intervals. |
423 | const LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, |
424 | const LiveInterval &LI) { |
425 | for (const LiveInterval::SubRange &S : LI.subranges()) |
426 | if ((S.LaneMask & LM) == LM) |
427 | return S; |
428 | llvm_unreachable("SubRange for this mask not found" ); |
429 | } |
430 | |
431 | void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) { |
432 | if (!LI.hasSubRanges()) { |
433 | LI.createDeadDef(VNI); |
434 | return; |
435 | } |
436 | |
437 | SlotIndex Def = VNI->def; |
438 | if (Original) { |
439 | // If we are transferring a def from the original interval, make sure |
440 | // to only update the subranges for which the original subranges had |
441 | // a def at this location. |
442 | for (LiveInterval::SubRange &S : LI.subranges()) { |
443 | auto &PS = getSubRangeForMask(LM: S.LaneMask, LI: Edit->getParent()); |
444 | VNInfo *PV = PS.getVNInfoAt(Idx: Def); |
445 | if (PV != nullptr && PV->def == Def) |
446 | S.createDeadDef(Def, VNIAlloc&: LIS.getVNInfoAllocator()); |
447 | } |
448 | } else { |
449 | // This is a new def: either from rematerialization, or from an inserted |
450 | // copy. Since rematerialization can regenerate a definition of a sub- |
451 | // register, we need to check which subranges need to be updated. |
452 | const MachineInstr *DefMI = LIS.getInstructionFromIndex(index: Def); |
453 | assert(DefMI != nullptr); |
454 | LaneBitmask LM; |
455 | for (const MachineOperand &DefOp : DefMI->defs()) { |
456 | Register R = DefOp.getReg(); |
457 | if (R != LI.reg()) |
458 | continue; |
459 | if (unsigned SR = DefOp.getSubReg()) |
460 | LM |= TRI.getSubRegIndexLaneMask(SubIdx: SR); |
461 | else { |
462 | LM = MRI.getMaxLaneMaskForVReg(Reg: R); |
463 | break; |
464 | } |
465 | } |
466 | for (LiveInterval::SubRange &S : LI.subranges()) |
467 | if ((S.LaneMask & LM).any()) |
468 | S.createDeadDef(Def, VNIAlloc&: LIS.getVNInfoAllocator()); |
469 | } |
470 | } |
471 | |
472 | VNInfo *SplitEditor::defValue(unsigned RegIdx, |
473 | const VNInfo *ParentVNI, |
474 | SlotIndex Idx, |
475 | bool Original) { |
476 | assert(ParentVNI && "Mapping NULL value" ); |
477 | assert(Idx.isValid() && "Invalid SlotIndex" ); |
478 | assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI" ); |
479 | LiveInterval *LI = &LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
480 | |
481 | // Create a new value. |
482 | VNInfo *VNI = LI->getNextValue(Def: Idx, VNInfoAllocator&: LIS.getVNInfoAllocator()); |
483 | |
484 | bool Force = LI->hasSubRanges(); |
485 | ValueForcePair FP(Force ? nullptr : VNI, Force); |
486 | // Use insert for lookup, so we can add missing values with a second lookup. |
487 | std::pair<ValueMap::iterator, bool> InsP = |
488 | Values.insert(KV: std::make_pair(x: std::make_pair(x&: RegIdx, y: ParentVNI->id), y&: FP)); |
489 | |
490 | // This was the first time (RegIdx, ParentVNI) was mapped, and it is not |
491 | // forced. Keep it as a simple def without any liveness. |
492 | if (!Force && InsP.second) |
493 | return VNI; |
494 | |
495 | // If the previous value was a simple mapping, add liveness for it now. |
496 | if (VNInfo *OldVNI = InsP.first->second.getPointer()) { |
497 | addDeadDef(LI&: *LI, VNI: OldVNI, Original); |
498 | |
499 | // No longer a simple mapping. Switch to a complex mapping. If the |
500 | // interval has subranges, make it a forced mapping. |
501 | InsP.first->second = ValueForcePair(nullptr, Force); |
502 | } |
503 | |
504 | // This is a complex mapping, add liveness for VNI |
505 | addDeadDef(LI&: *LI, VNI, Original); |
506 | return VNI; |
507 | } |
508 | |
509 | void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) { |
510 | ValueForcePair &VFP = Values[std::make_pair(x&: RegIdx, y: ParentVNI.id)]; |
511 | VNInfo *VNI = VFP.getPointer(); |
512 | |
513 | // ParentVNI was either unmapped or already complex mapped. Either way, just |
514 | // set the force bit. |
515 | if (!VNI) { |
516 | VFP.setInt(true); |
517 | return; |
518 | } |
519 | |
520 | // This was previously a single mapping. Make sure the old def is represented |
521 | // by a trivial live range. |
522 | addDeadDef(LI&: LIS.getInterval(Reg: Edit->get(idx: RegIdx)), VNI, Original: false); |
523 | |
524 | // Mark as complex mapped, forced. |
525 | VFP = ValueForcePair(nullptr, true); |
526 | } |
527 | |
528 | SlotIndex SplitEditor::buildSingleSubRegCopy( |
529 | Register FromReg, Register ToReg, MachineBasicBlock &MBB, |
530 | MachineBasicBlock::iterator InsertBefore, unsigned SubIdx, |
531 | LiveInterval &DestLI, bool Late, SlotIndex Def, const MCInstrDesc &Desc) { |
532 | bool FirstCopy = !Def.isValid(); |
533 | MachineInstr *CopyMI = BuildMI(BB&: MBB, I: InsertBefore, MIMD: DebugLoc(), MCID: Desc) |
534 | .addReg(RegNo: ToReg, flags: RegState::Define | getUndefRegState(B: FirstCopy) |
535 | | getInternalReadRegState(B: !FirstCopy), SubReg: SubIdx) |
536 | .addReg(RegNo: FromReg, flags: 0, SubReg: SubIdx); |
537 | |
538 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
539 | if (FirstCopy) { |
540 | Def = Indexes.insertMachineInstrInMaps(MI&: *CopyMI, Late).getRegSlot(); |
541 | } else { |
542 | CopyMI->bundleWithPred(); |
543 | } |
544 | return Def; |
545 | } |
546 | |
547 | SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg, |
548 | LaneBitmask LaneMask, MachineBasicBlock &MBB, |
549 | MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) { |
550 | const MCInstrDesc &Desc = |
551 | TII.get(Opcode: TII.getLiveRangeSplitOpcode(Reg: FromReg, MF: *MBB.getParent())); |
552 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
553 | if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(Reg: FromReg)) { |
554 | // The full vreg is copied. |
555 | MachineInstr *CopyMI = |
556 | BuildMI(BB&: MBB, I: InsertBefore, MIMD: DebugLoc(), MCID: Desc, DestReg: ToReg).addReg(RegNo: FromReg); |
557 | return Indexes.insertMachineInstrInMaps(MI&: *CopyMI, Late).getRegSlot(); |
558 | } |
559 | |
560 | // Only a subset of lanes needs to be copied. The following is a simple |
561 | // heuristic to construct a sequence of COPYs. We could add a target |
562 | // specific callback if this turns out to be suboptimal. |
563 | LiveInterval &DestLI = LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
564 | |
565 | // First pass: Try to find a perfectly matching subregister index. If none |
566 | // exists find the one covering the most lanemask bits. |
567 | const TargetRegisterClass *RC = MRI.getRegClass(Reg: FromReg); |
568 | assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class" ); |
569 | |
570 | SmallVector<unsigned, 8> SubIndexes; |
571 | |
572 | // Abort if we cannot possibly implement the COPY with the given indexes. |
573 | if (!TRI.getCoveringSubRegIndexes(MRI, RC, LaneMask, Indexes&: SubIndexes)) |
574 | report_fatal_error(reason: "Impossible to implement partial COPY" ); |
575 | |
576 | SlotIndex Def; |
577 | for (unsigned BestIdx : SubIndexes) { |
578 | Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, SubIdx: BestIdx, |
579 | DestLI, Late, Def, Desc); |
580 | } |
581 | |
582 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); |
583 | DestLI.refineSubRanges( |
584 | Allocator, LaneMask, |
585 | Apply: [Def, &Allocator](LiveInterval::SubRange &SR) { |
586 | SR.createDeadDef(Def, VNIAlloc&: Allocator); |
587 | }, |
588 | Indexes, TRI); |
589 | |
590 | return Def; |
591 | } |
592 | |
593 | VNInfo *SplitEditor::defFromParent(unsigned RegIdx, const VNInfo *ParentVNI, |
594 | SlotIndex UseIdx, MachineBasicBlock &MBB, |
595 | MachineBasicBlock::iterator I) { |
596 | SlotIndex Def; |
597 | LiveInterval *LI = &LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
598 | |
599 | // We may be trying to avoid interference that ends at a deleted instruction, |
600 | // so always begin RegIdx 0 early and all others late. |
601 | bool Late = RegIdx != 0; |
602 | |
603 | // Attempt cheap-as-a-copy rematerialization. |
604 | Register Original = VRM.getOriginal(VirtReg: Edit->get(idx: RegIdx)); |
605 | LiveInterval &OrigLI = LIS.getInterval(Reg: Original); |
606 | VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx: UseIdx); |
607 | |
608 | Register Reg = LI->reg(); |
609 | bool DidRemat = false; |
610 | if (OrigVNI) { |
611 | LiveRangeEdit::Remat RM(ParentVNI); |
612 | RM.OrigMI = LIS.getInstructionFromIndex(index: OrigVNI->def); |
613 | if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, cheapAsAMove: true)) { |
614 | Def = Edit->rematerializeAt(MBB, MI: I, DestReg: Reg, RM, TRI, Late); |
615 | ++NumRemats; |
616 | DidRemat = true; |
617 | } |
618 | } |
619 | if (!DidRemat) { |
620 | LaneBitmask LaneMask; |
621 | if (OrigLI.hasSubRanges()) { |
622 | LaneMask = LaneBitmask::getNone(); |
623 | for (LiveInterval::SubRange &S : OrigLI.subranges()) { |
624 | if (S.liveAt(index: UseIdx)) |
625 | LaneMask |= S.LaneMask; |
626 | } |
627 | } else { |
628 | LaneMask = LaneBitmask::getAll(); |
629 | } |
630 | |
631 | if (LaneMask.none()) { |
632 | const MCInstrDesc &Desc = TII.get(Opcode: TargetOpcode::IMPLICIT_DEF); |
633 | MachineInstr *ImplicitDef = BuildMI(BB&: MBB, I, MIMD: DebugLoc(), MCID: Desc, DestReg: Reg); |
634 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
635 | Def = Indexes.insertMachineInstrInMaps(MI&: *ImplicitDef, Late).getRegSlot(); |
636 | } else { |
637 | ++NumCopies; |
638 | Def = buildCopy(FromReg: Edit->getReg(), ToReg: Reg, LaneMask, MBB, InsertBefore: I, Late, RegIdx); |
639 | } |
640 | } |
641 | |
642 | // Define the value in Reg. |
643 | return defValue(RegIdx, ParentVNI, Idx: Def, Original: false); |
644 | } |
645 | |
646 | /// Create a new virtual register and live interval. |
647 | unsigned SplitEditor::openIntv() { |
648 | // Create the complement as index 0. |
649 | if (Edit->empty()) |
650 | Edit->createEmptyInterval(); |
651 | |
652 | // Create the open interval. |
653 | OpenIdx = Edit->size(); |
654 | Edit->createEmptyInterval(); |
655 | return OpenIdx; |
656 | } |
657 | |
658 | void SplitEditor::selectIntv(unsigned Idx) { |
659 | assert(Idx != 0 && "Cannot select the complement interval" ); |
660 | assert(Idx < Edit->size() && "Can only select previously opened interval" ); |
661 | LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); |
662 | OpenIdx = Idx; |
663 | } |
664 | |
665 | SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { |
666 | assert(OpenIdx && "openIntv not called before enterIntvBefore" ); |
667 | LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx); |
668 | Idx = Idx.getBaseIndex(); |
669 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
670 | if (!ParentVNI) { |
671 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
672 | return Idx; |
673 | } |
674 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
675 | MachineInstr *MI = LIS.getInstructionFromIndex(index: Idx); |
676 | assert(MI && "enterIntvBefore called with invalid index" ); |
677 | |
678 | VNInfo *VNI = defFromParent(RegIdx: OpenIdx, ParentVNI, UseIdx: Idx, MBB&: *MI->getParent(), I: MI); |
679 | return VNI->def; |
680 | } |
681 | |
682 | SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { |
683 | assert(OpenIdx && "openIntv not called before enterIntvAfter" ); |
684 | LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx); |
685 | Idx = Idx.getBoundaryIndex(); |
686 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
687 | if (!ParentVNI) { |
688 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
689 | return Idx; |
690 | } |
691 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
692 | MachineInstr *MI = LIS.getInstructionFromIndex(index: Idx); |
693 | assert(MI && "enterIntvAfter called with invalid index" ); |
694 | |
695 | VNInfo *VNI = defFromParent(RegIdx: OpenIdx, ParentVNI, UseIdx: Idx, MBB&: *MI->getParent(), |
696 | I: std::next(x: MachineBasicBlock::iterator(MI))); |
697 | return VNI->def; |
698 | } |
699 | |
700 | SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { |
701 | assert(OpenIdx && "openIntv not called before enterIntvAtEnd" ); |
702 | SlotIndex End = LIS.getMBBEndIdx(mbb: &MBB); |
703 | SlotIndex Last = End.getPrevSlot(); |
704 | LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", " |
705 | << Last); |
706 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: Last); |
707 | if (!ParentVNI) { |
708 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
709 | return End; |
710 | } |
711 | SlotIndex LSP = SA.getLastSplitPoint(BB: &MBB); |
712 | if (LSP < Last) { |
713 | // It could be that the use after LSP is a def, and thus the ParentVNI |
714 | // just selected starts at that def. For this case to exist, the def |
715 | // must be part of a tied def/use pair (as otherwise we'd have split |
716 | // distinct live ranges into individual live intervals), and thus we |
717 | // can insert the def into the VNI of the use and the tied def/use |
718 | // pair can live in the resulting interval. |
719 | Last = LSP; |
720 | ParentVNI = Edit->getParent().getVNInfoAt(Idx: Last); |
721 | if (!ParentVNI) { |
722 | // undef use --> undef tied def |
723 | LLVM_DEBUG(dbgs() << ": tied use not live\n" ); |
724 | return End; |
725 | } |
726 | } |
727 | |
728 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id); |
729 | VNInfo *VNI = defFromParent(RegIdx: OpenIdx, ParentVNI, UseIdx: Last, MBB, |
730 | I: SA.getLastSplitPointIter(BB: &MBB)); |
731 | RegAssign.insert(a: VNI->def, b: End, y: OpenIdx); |
732 | LLVM_DEBUG(dump()); |
733 | return VNI->def; |
734 | } |
735 | |
736 | /// useIntv - indicate that all instructions in MBB should use OpenLI. |
737 | void SplitEditor::useIntv(const MachineBasicBlock &MBB) { |
738 | useIntv(Start: LIS.getMBBStartIdx(mbb: &MBB), End: LIS.getMBBEndIdx(mbb: &MBB)); |
739 | } |
740 | |
741 | void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { |
742 | assert(OpenIdx && "openIntv not called before useIntv" ); |
743 | LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):" ); |
744 | RegAssign.insert(a: Start, b: End, y: OpenIdx); |
745 | LLVM_DEBUG(dump()); |
746 | } |
747 | |
748 | SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { |
749 | assert(OpenIdx && "openIntv not called before leaveIntvAfter" ); |
750 | LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx); |
751 | |
752 | // The interval must be live beyond the instruction at Idx. |
753 | SlotIndex Boundary = Idx.getBoundaryIndex(); |
754 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: Boundary); |
755 | if (!ParentVNI) { |
756 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
757 | return Boundary.getNextSlot(); |
758 | } |
759 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
760 | MachineInstr *MI = LIS.getInstructionFromIndex(index: Boundary); |
761 | assert(MI && "No instruction at index" ); |
762 | |
763 | // In spill mode, make live ranges as short as possible by inserting the copy |
764 | // before MI. This is only possible if that instruction doesn't redefine the |
765 | // value. The inserted COPY is not a kill, and we don't need to recompute |
766 | // the source live range. The spiller also won't try to hoist this copy. |
767 | if (SpillMode && !SlotIndex::isSameInstr(A: ParentVNI->def, B: Idx) && |
768 | MI->readsVirtualRegister(Reg: Edit->getReg())) { |
769 | forceRecompute(RegIdx: 0, ParentVNI: *ParentVNI); |
770 | defFromParent(RegIdx: 0, ParentVNI, UseIdx: Idx, MBB&: *MI->getParent(), I: MI); |
771 | return Idx; |
772 | } |
773 | |
774 | VNInfo *VNI = defFromParent(RegIdx: 0, ParentVNI, UseIdx: Boundary, MBB&: *MI->getParent(), |
775 | I: std::next(x: MachineBasicBlock::iterator(MI))); |
776 | return VNI->def; |
777 | } |
778 | |
779 | SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { |
780 | assert(OpenIdx && "openIntv not called before leaveIntvBefore" ); |
781 | LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx); |
782 | |
783 | // The interval must be live into the instruction at Idx. |
784 | Idx = Idx.getBaseIndex(); |
785 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
786 | if (!ParentVNI) { |
787 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
788 | return Idx.getNextSlot(); |
789 | } |
790 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
791 | |
792 | MachineInstr *MI = LIS.getInstructionFromIndex(index: Idx); |
793 | assert(MI && "No instruction at index" ); |
794 | VNInfo *VNI = defFromParent(RegIdx: 0, ParentVNI, UseIdx: Idx, MBB&: *MI->getParent(), I: MI); |
795 | return VNI->def; |
796 | } |
797 | |
798 | SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { |
799 | assert(OpenIdx && "openIntv not called before leaveIntvAtTop" ); |
800 | SlotIndex Start = LIS.getMBBStartIdx(mbb: &MBB); |
801 | LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", " |
802 | << Start); |
803 | |
804 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: Start); |
805 | if (!ParentVNI) { |
806 | LLVM_DEBUG(dbgs() << ": not live\n" ); |
807 | return Start; |
808 | } |
809 | |
810 | unsigned RegIdx = 0; |
811 | Register Reg = LIS.getInterval(Reg: Edit->get(idx: RegIdx)).reg(); |
812 | VNInfo *VNI = defFromParent(RegIdx, ParentVNI, UseIdx: Start, MBB, |
813 | I: MBB.SkipPHIsLabelsAndDebug(I: MBB.begin(), Reg)); |
814 | RegAssign.insert(a: Start, b: VNI->def, y: OpenIdx); |
815 | LLVM_DEBUG(dump()); |
816 | return VNI->def; |
817 | } |
818 | |
819 | static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) { |
820 | return any_of(Range: MI.defs(), P: [Reg](const MachineOperand &MO) { |
821 | return MO.isReg() && MO.isTied() && MO.getReg() == Reg; |
822 | }); |
823 | } |
824 | |
825 | void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { |
826 | assert(OpenIdx && "openIntv not called before overlapIntv" ); |
827 | const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: Start); |
828 | assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && |
829 | "Parent changes value in extended range" ); |
830 | assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && |
831 | "Range cannot span basic blocks" ); |
832 | |
833 | // The complement interval will be extended as needed by LICalc.extend(). |
834 | if (ParentVNI) |
835 | forceRecompute(RegIdx: 0, ParentVNI: *ParentVNI); |
836 | |
837 | // If the last use is tied to a def, we can't mark it as live for the |
838 | // interval which includes only the use. That would cause the tied pair |
839 | // to end up in two different intervals. |
840 | if (auto *MI = LIS.getInstructionFromIndex(index: End)) |
841 | if (hasTiedUseOf(MI&: *MI, Reg: Edit->getReg())) { |
842 | LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n" ); |
843 | return; |
844 | } |
845 | |
846 | LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):" ); |
847 | RegAssign.insert(a: Start, b: End, y: OpenIdx); |
848 | LLVM_DEBUG(dump()); |
849 | } |
850 | |
851 | //===----------------------------------------------------------------------===// |
852 | // Spill modes |
853 | //===----------------------------------------------------------------------===// |
854 | |
855 | void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { |
856 | LiveInterval *LI = &LIS.getInterval(Reg: Edit->get(idx: 0)); |
857 | LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n" ); |
858 | RegAssignMap::iterator AssignI; |
859 | AssignI.setMap(RegAssign); |
860 | |
861 | for (const VNInfo *C : Copies) { |
862 | SlotIndex Def = C->def; |
863 | MachineInstr *MI = LIS.getInstructionFromIndex(index: Def); |
864 | assert(MI && "No instruction for back-copy" ); |
865 | |
866 | MachineBasicBlock *MBB = MI->getParent(); |
867 | MachineBasicBlock::iterator MBBI(MI); |
868 | bool AtBegin; |
869 | do AtBegin = MBBI == MBB->begin(); |
870 | while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr()); |
871 | |
872 | LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); |
873 | LIS.removeVRegDefAt(LI&: *LI, Pos: Def); |
874 | LIS.RemoveMachineInstrFromMaps(MI&: *MI); |
875 | MI->eraseFromParent(); |
876 | |
877 | // Adjust RegAssign if a register assignment is killed at Def. We want to |
878 | // avoid calculating the live range of the source register if possible. |
879 | AssignI.find(x: Def.getPrevSlot()); |
880 | if (!AssignI.valid() || AssignI.start() >= Def) |
881 | continue; |
882 | // If MI doesn't kill the assigned register, just leave it. |
883 | if (AssignI.stop() != Def) |
884 | continue; |
885 | unsigned RegIdx = AssignI.value(); |
886 | // We could hoist back-copy right after another back-copy. As a result |
887 | // MMBI points to copy instruction which is actually dead now. |
888 | // We cannot set its stop to MBBI which will be the same as start and |
889 | // interval does not support that. |
890 | SlotIndex Kill = |
891 | AtBegin ? SlotIndex() : LIS.getInstructionIndex(Instr: *MBBI).getRegSlot(); |
892 | if (AtBegin || !MBBI->readsVirtualRegister(Reg: Edit->getReg()) || |
893 | Kill <= AssignI.start()) { |
894 | LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx |
895 | << '\n'); |
896 | forceRecompute(RegIdx, ParentVNI: *Edit->getParent().getVNInfoAt(Idx: Def)); |
897 | } else { |
898 | LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); |
899 | AssignI.setStop(Kill); |
900 | } |
901 | } |
902 | } |
903 | |
904 | MachineBasicBlock* |
905 | SplitEditor::findShallowDominator(MachineBasicBlock *MBB, |
906 | MachineBasicBlock *DefMBB) { |
907 | if (MBB == DefMBB) |
908 | return MBB; |
909 | assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def." ); |
910 | |
911 | const MachineLoopInfo &Loops = SA.Loops; |
912 | const MachineLoop *DefLoop = Loops.getLoopFor(BB: DefMBB); |
913 | MachineDomTreeNode *DefDomNode = MDT[DefMBB]; |
914 | |
915 | // Best candidate so far. |
916 | MachineBasicBlock *BestMBB = MBB; |
917 | unsigned BestDepth = std::numeric_limits<unsigned>::max(); |
918 | |
919 | while (true) { |
920 | const MachineLoop *Loop = Loops.getLoopFor(BB: MBB); |
921 | |
922 | // MBB isn't in a loop, it doesn't get any better. All dominators have a |
923 | // higher frequency by definition. |
924 | if (!Loop) { |
925 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB) |
926 | << " dominates " << printMBBReference(*MBB) |
927 | << " at depth 0\n" ); |
928 | return MBB; |
929 | } |
930 | |
931 | // We'll never be able to exit the DefLoop. |
932 | if (Loop == DefLoop) { |
933 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB) |
934 | << " dominates " << printMBBReference(*MBB) |
935 | << " in the same loop\n" ); |
936 | return MBB; |
937 | } |
938 | |
939 | // Least busy dominator seen so far. |
940 | unsigned Depth = Loop->getLoopDepth(); |
941 | if (Depth < BestDepth) { |
942 | BestMBB = MBB; |
943 | BestDepth = Depth; |
944 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB) |
945 | << " dominates " << printMBBReference(*MBB) |
946 | << " at depth " << Depth << '\n'); |
947 | } |
948 | |
949 | // Leave loop by going to the immediate dominator of the loop header. |
950 | // This is a bigger stride than simply walking up the dominator tree. |
951 | MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); |
952 | |
953 | // Too far up the dominator tree? |
954 | if (!IDom || !MDT.dominates(A: DefDomNode, B: IDom)) |
955 | return BestMBB; |
956 | |
957 | MBB = IDom->getBlock(); |
958 | } |
959 | } |
960 | |
961 | void SplitEditor::computeRedundantBackCopies( |
962 | DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { |
963 | LiveInterval *LI = &LIS.getInterval(Reg: Edit->get(idx: 0)); |
964 | const LiveInterval *Parent = &Edit->getParent(); |
965 | SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); |
966 | SmallPtrSet<VNInfo *, 8> DominatedVNIs; |
967 | |
968 | // Aggregate VNIs having the same value as ParentVNI. |
969 | for (VNInfo *VNI : LI->valnos) { |
970 | if (VNI->isUnused()) |
971 | continue; |
972 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: VNI->def); |
973 | EqualVNs[ParentVNI->id].insert(Ptr: VNI); |
974 | } |
975 | |
976 | // For VNI aggregation of each ParentVNI, collect dominated, i.e., |
977 | // redundant VNIs to BackCopies. |
978 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { |
979 | const VNInfo *ParentVNI = Parent->getValNumInfo(ValNo: i); |
980 | if (!NotToHoistSet.count(V: ParentVNI->id)) |
981 | continue; |
982 | SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); |
983 | SmallPtrSetIterator<VNInfo *> It2 = It1; |
984 | for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { |
985 | It2 = It1; |
986 | for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { |
987 | if (DominatedVNIs.count(Ptr: *It1) || DominatedVNIs.count(Ptr: *It2)) |
988 | continue; |
989 | |
990 | MachineBasicBlock *MBB1 = LIS.getMBBFromIndex(index: (*It1)->def); |
991 | MachineBasicBlock *MBB2 = LIS.getMBBFromIndex(index: (*It2)->def); |
992 | if (MBB1 == MBB2) { |
993 | DominatedVNIs.insert(Ptr: (*It1)->def < (*It2)->def ? (*It2) : (*It1)); |
994 | } else if (MDT.dominates(A: MBB1, B: MBB2)) { |
995 | DominatedVNIs.insert(Ptr: *It2); |
996 | } else if (MDT.dominates(A: MBB2, B: MBB1)) { |
997 | DominatedVNIs.insert(Ptr: *It1); |
998 | } |
999 | } |
1000 | } |
1001 | if (!DominatedVNIs.empty()) { |
1002 | forceRecompute(RegIdx: 0, ParentVNI: *ParentVNI); |
1003 | append_range(C&: BackCopies, R&: DominatedVNIs); |
1004 | DominatedVNIs.clear(); |
1005 | } |
1006 | } |
1007 | } |
1008 | |
1009 | /// For SM_Size mode, find a common dominator for all the back-copies for |
1010 | /// the same ParentVNI and hoist the backcopies to the dominator BB. |
1011 | /// For SM_Speed mode, if the common dominator is hot and it is not beneficial |
1012 | /// to do the hoisting, simply remove the dominated backcopies for the same |
1013 | /// ParentVNI. |
1014 | void SplitEditor::hoistCopies() { |
1015 | // Get the complement interval, always RegIdx 0. |
1016 | LiveInterval *LI = &LIS.getInterval(Reg: Edit->get(idx: 0)); |
1017 | const LiveInterval *Parent = &Edit->getParent(); |
1018 | |
1019 | // Track the nearest common dominator for all back-copies for each ParentVNI, |
1020 | // indexed by ParentVNI->id. |
1021 | using DomPair = std::pair<MachineBasicBlock *, SlotIndex>; |
1022 | SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); |
1023 | // The total cost of all the back-copies for each ParentVNI. |
1024 | SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); |
1025 | // The ParentVNI->id set for which hoisting back-copies are not beneficial |
1026 | // for Speed. |
1027 | DenseSet<unsigned> NotToHoistSet; |
1028 | |
1029 | // Find the nearest common dominator for parent values with multiple |
1030 | // back-copies. If a single back-copy dominates, put it in DomPair.second. |
1031 | for (VNInfo *VNI : LI->valnos) { |
1032 | if (VNI->isUnused()) |
1033 | continue; |
1034 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: VNI->def); |
1035 | assert(ParentVNI && "Parent not live at complement def" ); |
1036 | |
1037 | // Don't hoist remats. The complement is probably going to disappear |
1038 | // completely anyway. |
1039 | if (Edit->didRematerialize(ParentVNI)) |
1040 | continue; |
1041 | |
1042 | MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(index: VNI->def); |
1043 | |
1044 | DomPair &Dom = NearestDom[ParentVNI->id]; |
1045 | |
1046 | // Keep directly defined parent values. This is either a PHI or an |
1047 | // instruction in the complement range. All other copies of ParentVNI |
1048 | // should be eliminated. |
1049 | if (VNI->def == ParentVNI->def) { |
1050 | LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); |
1051 | Dom = DomPair(ValMBB, VNI->def); |
1052 | continue; |
1053 | } |
1054 | // Skip the singly mapped values. There is nothing to gain from hoisting a |
1055 | // single back-copy. |
1056 | if (Values.lookup(Val: std::make_pair(x: 0, y&: ParentVNI->id)).getPointer()) { |
1057 | LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); |
1058 | continue; |
1059 | } |
1060 | |
1061 | if (!Dom.first) { |
1062 | // First time we see ParentVNI. VNI dominates itself. |
1063 | Dom = DomPair(ValMBB, VNI->def); |
1064 | } else if (Dom.first == ValMBB) { |
1065 | // Two defs in the same block. Pick the earlier def. |
1066 | if (!Dom.second.isValid() || VNI->def < Dom.second) |
1067 | Dom.second = VNI->def; |
1068 | } else { |
1069 | // Different basic blocks. Check if one dominates. |
1070 | MachineBasicBlock *Near = |
1071 | MDT.findNearestCommonDominator(A: Dom.first, B: ValMBB); |
1072 | if (Near == ValMBB) |
1073 | // Def ValMBB dominates. |
1074 | Dom = DomPair(ValMBB, VNI->def); |
1075 | else if (Near != Dom.first) |
1076 | // None dominate. Hoist to common dominator, need new def. |
1077 | Dom = DomPair(Near, SlotIndex()); |
1078 | Costs[ParentVNI->id] += MBFI.getBlockFreq(MBB: ValMBB); |
1079 | } |
1080 | |
1081 | LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' |
1082 | << VNI->def << " for parent " << ParentVNI->id << '@' |
1083 | << ParentVNI->def << " hoist to " |
1084 | << printMBBReference(*Dom.first) << ' ' << Dom.second |
1085 | << '\n'); |
1086 | } |
1087 | |
1088 | // Insert the hoisted copies. |
1089 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { |
1090 | DomPair &Dom = NearestDom[i]; |
1091 | if (!Dom.first || Dom.second.isValid()) |
1092 | continue; |
1093 | // This value needs a hoisted copy inserted at the end of Dom.first. |
1094 | const VNInfo *ParentVNI = Parent->getValNumInfo(ValNo: i); |
1095 | MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(index: ParentVNI->def); |
1096 | // Get a less loopy dominator than Dom.first. |
1097 | Dom.first = findShallowDominator(MBB: Dom.first, DefMBB); |
1098 | if (SpillMode == SM_Speed && |
1099 | MBFI.getBlockFreq(MBB: Dom.first) > Costs[ParentVNI->id]) { |
1100 | NotToHoistSet.insert(V: ParentVNI->id); |
1101 | continue; |
1102 | } |
1103 | SlotIndex LSP = SA.getLastSplitPoint(BB: Dom.first); |
1104 | if (LSP <= ParentVNI->def) { |
1105 | NotToHoistSet.insert(V: ParentVNI->id); |
1106 | continue; |
1107 | } |
1108 | Dom.second = defFromParent(RegIdx: 0, ParentVNI, UseIdx: LSP, MBB&: *Dom.first, |
1109 | I: SA.getLastSplitPointIter(BB: Dom.first))->def; |
1110 | } |
1111 | |
1112 | // Remove redundant back-copies that are now known to be dominated by another |
1113 | // def with the same value. |
1114 | SmallVector<VNInfo*, 8> BackCopies; |
1115 | for (VNInfo *VNI : LI->valnos) { |
1116 | if (VNI->isUnused()) |
1117 | continue; |
1118 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx: VNI->def); |
1119 | const DomPair &Dom = NearestDom[ParentVNI->id]; |
1120 | if (!Dom.first || Dom.second == VNI->def || |
1121 | NotToHoistSet.count(V: ParentVNI->id)) |
1122 | continue; |
1123 | BackCopies.push_back(Elt: VNI); |
1124 | forceRecompute(RegIdx: 0, ParentVNI: *ParentVNI); |
1125 | } |
1126 | |
1127 | // If it is not beneficial to hoist all the BackCopies, simply remove |
1128 | // redundant BackCopies in speed mode. |
1129 | if (SpillMode == SM_Speed && !NotToHoistSet.empty()) |
1130 | computeRedundantBackCopies(NotToHoistSet, BackCopies); |
1131 | |
1132 | removeBackCopies(Copies&: BackCopies); |
1133 | } |
1134 | |
1135 | /// transferValues - Transfer all possible values to the new live ranges. |
1136 | /// Values that were rematerialized are left alone, they need LICalc.extend(). |
1137 | bool SplitEditor::transferValues() { |
1138 | bool Skipped = false; |
1139 | RegAssignMap::const_iterator AssignI = RegAssign.begin(); |
1140 | for (const LiveRange::Segment &S : Edit->getParent()) { |
1141 | LLVM_DEBUG(dbgs() << " blit " << S << ':'); |
1142 | VNInfo *ParentVNI = S.valno; |
1143 | // RegAssign has holes where RegIdx 0 should be used. |
1144 | SlotIndex Start = S.start; |
1145 | AssignI.advanceTo(x: Start); |
1146 | do { |
1147 | unsigned RegIdx; |
1148 | SlotIndex End = S.end; |
1149 | if (!AssignI.valid()) { |
1150 | RegIdx = 0; |
1151 | } else if (AssignI.start() <= Start) { |
1152 | RegIdx = AssignI.value(); |
1153 | if (AssignI.stop() < End) { |
1154 | End = AssignI.stop(); |
1155 | ++AssignI; |
1156 | } |
1157 | } else { |
1158 | RegIdx = 0; |
1159 | End = std::min(a: End, b: AssignI.start()); |
1160 | } |
1161 | |
1162 | // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. |
1163 | LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '(' |
1164 | << printReg(Edit->get(RegIdx)) << ')'); |
1165 | LiveInterval &LI = LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
1166 | |
1167 | // Check for a simply defined value that can be blitted directly. |
1168 | ValueForcePair VFP = Values.lookup(Val: std::make_pair(x&: RegIdx, y&: ParentVNI->id)); |
1169 | if (VNInfo *VNI = VFP.getPointer()) { |
1170 | LLVM_DEBUG(dbgs() << ':' << VNI->id); |
1171 | LI.addSegment(S: LiveInterval::Segment(Start, End, VNI)); |
1172 | Start = End; |
1173 | continue; |
1174 | } |
1175 | |
1176 | // Skip values with forced recomputation. |
1177 | if (VFP.getInt()) { |
1178 | LLVM_DEBUG(dbgs() << "(recalc)" ); |
1179 | Skipped = true; |
1180 | Start = End; |
1181 | continue; |
1182 | } |
1183 | |
1184 | LiveIntervalCalc &LIC = getLICalc(RegIdx); |
1185 | |
1186 | // This value has multiple defs in RegIdx, but it wasn't rematerialized, |
1187 | // so the live range is accurate. Add live-in blocks in [Start;End) to the |
1188 | // LiveInBlocks. |
1189 | MachineFunction::iterator MBB = LIS.getMBBFromIndex(index: Start)->getIterator(); |
1190 | SlotIndex BlockStart, BlockEnd; |
1191 | std::tie(args&: BlockStart, args&: BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB: &*MBB); |
1192 | |
1193 | // The first block may be live-in, or it may have its own def. |
1194 | if (Start != BlockStart) { |
1195 | VNInfo *VNI = LI.extendInBlock(StartIdx: BlockStart, Kill: std::min(a: BlockEnd, b: End)); |
1196 | assert(VNI && "Missing def for complex mapped value" ); |
1197 | LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB)); |
1198 | // MBB has its own def. Is it also live-out? |
1199 | if (BlockEnd <= End) |
1200 | LIC.setLiveOutValue(MBB: &*MBB, VNI); |
1201 | |
1202 | // Skip to the next block for live-in. |
1203 | ++MBB; |
1204 | BlockStart = BlockEnd; |
1205 | } |
1206 | |
1207 | // Handle the live-in blocks covered by [Start;End). |
1208 | assert(Start <= BlockStart && "Expected live-in block" ); |
1209 | while (BlockStart < End) { |
1210 | LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB)); |
1211 | BlockEnd = LIS.getMBBEndIdx(mbb: &*MBB); |
1212 | if (BlockStart == ParentVNI->def) { |
1213 | // This block has the def of a parent PHI, so it isn't live-in. |
1214 | assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?" ); |
1215 | VNInfo *VNI = LI.extendInBlock(StartIdx: BlockStart, Kill: std::min(a: BlockEnd, b: End)); |
1216 | assert(VNI && "Missing def for complex mapped parent PHI" ); |
1217 | if (End >= BlockEnd) |
1218 | LIC.setLiveOutValue(MBB: &*MBB, VNI); // Live-out as well. |
1219 | } else { |
1220 | // This block needs a live-in value. The last block covered may not |
1221 | // be live-out. |
1222 | if (End < BlockEnd) |
1223 | LIC.addLiveInBlock(LR&: LI, DomNode: MDT[&*MBB], Kill: End); |
1224 | else { |
1225 | // Live-through, and we don't know the value. |
1226 | LIC.addLiveInBlock(LR&: LI, DomNode: MDT[&*MBB]); |
1227 | LIC.setLiveOutValue(MBB: &*MBB, VNI: nullptr); |
1228 | } |
1229 | } |
1230 | BlockStart = BlockEnd; |
1231 | ++MBB; |
1232 | } |
1233 | Start = End; |
1234 | } while (Start != S.end); |
1235 | LLVM_DEBUG(dbgs() << '\n'); |
1236 | } |
1237 | |
1238 | LICalc[0].calculateValues(); |
1239 | if (SpillMode) |
1240 | LICalc[1].calculateValues(); |
1241 | |
1242 | return Skipped; |
1243 | } |
1244 | |
1245 | static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) { |
1246 | const LiveRange::Segment *Seg = LR.getSegmentContaining(Idx: Def); |
1247 | if (Seg == nullptr) |
1248 | return true; |
1249 | if (Seg->end != Def.getDeadSlot()) |
1250 | return false; |
1251 | // This is a dead PHI. Remove it. |
1252 | LR.removeSegment(S: *Seg, RemoveDeadValNo: true); |
1253 | return true; |
1254 | } |
1255 | |
1256 | void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, |
1257 | LiveRange &LR, LaneBitmask LM, |
1258 | ArrayRef<SlotIndex> Undefs) { |
1259 | for (MachineBasicBlock *P : B.predecessors()) { |
1260 | SlotIndex End = LIS.getMBBEndIdx(mbb: P); |
1261 | SlotIndex LastUse = End.getPrevSlot(); |
1262 | // The predecessor may not have a live-out value. That is OK, like an |
1263 | // undef PHI operand. |
1264 | const LiveInterval &PLI = Edit->getParent(); |
1265 | // Need the cast because the inputs to ?: would otherwise be deemed |
1266 | // "incompatible": SubRange vs LiveInterval. |
1267 | const LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, LI: PLI) |
1268 | : static_cast<const LiveRange &>(PLI); |
1269 | if (PSR.liveAt(index: LastUse)) |
1270 | LIC.extend(LR, Use: End, /*PhysReg=*/0, Undefs); |
1271 | } |
1272 | } |
1273 | |
1274 | void SplitEditor::extendPHIKillRanges() { |
1275 | // Extend live ranges to be live-out for successor PHI values. |
1276 | |
1277 | // Visit each PHI def slot in the parent live interval. If the def is dead, |
1278 | // remove it. Otherwise, extend the live interval to reach the end indexes |
1279 | // of all predecessor blocks. |
1280 | |
1281 | const LiveInterval &ParentLI = Edit->getParent(); |
1282 | for (const VNInfo *V : ParentLI.valnos) { |
1283 | if (V->isUnused() || !V->isPHIDef()) |
1284 | continue; |
1285 | |
1286 | unsigned RegIdx = RegAssign.lookup(x: V->def); |
1287 | LiveInterval &LI = LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
1288 | LiveIntervalCalc &LIC = getLICalc(RegIdx); |
1289 | MachineBasicBlock &B = *LIS.getMBBFromIndex(index: V->def); |
1290 | if (!removeDeadSegment(Def: V->def, LR&: LI)) |
1291 | extendPHIRange(B, LIC, LR&: LI, LM: LaneBitmask::getAll(), /*Undefs=*/{}); |
1292 | } |
1293 | |
1294 | SmallVector<SlotIndex, 4> Undefs; |
1295 | LiveIntervalCalc SubLIC; |
1296 | |
1297 | for (const LiveInterval::SubRange &PS : ParentLI.subranges()) { |
1298 | for (const VNInfo *V : PS.valnos) { |
1299 | if (V->isUnused() || !V->isPHIDef()) |
1300 | continue; |
1301 | unsigned RegIdx = RegAssign.lookup(x: V->def); |
1302 | LiveInterval &LI = LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
1303 | LiveInterval::SubRange &S = getSubRangeForMaskExact(LM: PS.LaneMask, LI); |
1304 | if (removeDeadSegment(Def: V->def, LR&: S)) |
1305 | continue; |
1306 | |
1307 | MachineBasicBlock &B = *LIS.getMBBFromIndex(index: V->def); |
1308 | SubLIC.reset(mf: &VRM.getMachineFunction(), SI: LIS.getSlotIndexes(), MDT: &MDT, |
1309 | VNIA: &LIS.getVNInfoAllocator()); |
1310 | Undefs.clear(); |
1311 | LI.computeSubRangeUndefs(Undefs, LaneMask: PS.LaneMask, MRI, Indexes: *LIS.getSlotIndexes()); |
1312 | extendPHIRange(B, LIC&: SubLIC, LR&: S, LM: PS.LaneMask, Undefs); |
1313 | } |
1314 | } |
1315 | } |
1316 | |
1317 | /// rewriteAssigned - Rewrite all uses of Edit->getReg(). |
1318 | void SplitEditor::rewriteAssigned(bool ExtendRanges) { |
1319 | struct ExtPoint { |
1320 | ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N) |
1321 | : MO(O), RegIdx(R), Next(N) {} |
1322 | |
1323 | MachineOperand MO; |
1324 | unsigned RegIdx; |
1325 | SlotIndex Next; |
1326 | }; |
1327 | |
1328 | SmallVector<ExtPoint,4> ExtPoints; |
1329 | |
1330 | for (MachineOperand &MO : |
1331 | llvm::make_early_inc_range(Range: MRI.reg_operands(Reg: Edit->getReg()))) { |
1332 | MachineInstr *MI = MO.getParent(); |
1333 | // LiveDebugVariables should have handled all DBG_VALUE instructions. |
1334 | if (MI->isDebugValue()) { |
1335 | LLVM_DEBUG(dbgs() << "Zapping " << *MI); |
1336 | MO.setReg(0); |
1337 | continue; |
1338 | } |
1339 | |
1340 | // <undef> operands don't really read the register, so it doesn't matter |
1341 | // which register we choose. When the use operand is tied to a def, we must |
1342 | // use the same register as the def, so just do that always. |
1343 | SlotIndex Idx = LIS.getInstructionIndex(Instr: *MI); |
1344 | if (MO.isDef() || MO.isUndef()) |
1345 | Idx = Idx.getRegSlot(EC: MO.isEarlyClobber()); |
1346 | |
1347 | // Rewrite to the mapped register at Idx. |
1348 | unsigned RegIdx = RegAssign.lookup(x: Idx); |
1349 | LiveInterval &LI = LIS.getInterval(Reg: Edit->get(idx: RegIdx)); |
1350 | MO.setReg(LI.reg()); |
1351 | LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent()) |
1352 | << '\t' << Idx << ':' << RegIdx << '\t' << *MI); |
1353 | |
1354 | // Extend liveness to Idx if the instruction reads reg. |
1355 | if (!ExtendRanges || MO.isUndef()) |
1356 | continue; |
1357 | |
1358 | // Skip instructions that don't read Reg. |
1359 | if (MO.isDef()) { |
1360 | if (!MO.getSubReg() && !MO.isEarlyClobber()) |
1361 | continue; |
1362 | // We may want to extend a live range for a partial redef, or for a use |
1363 | // tied to an early clobber. |
1364 | if (!Edit->getParent().liveAt(index: Idx.getPrevSlot())) |
1365 | continue; |
1366 | } else { |
1367 | assert(MO.isUse()); |
1368 | bool IsEarlyClobber = false; |
1369 | if (MO.isTied()) { |
1370 | // We want to extend a live range into `e` slot rather than `r` slot if |
1371 | // tied-def is early clobber, because the `e` slot already contained |
1372 | // in the live range of early-clobber tied-def operand, give an example |
1373 | // here: |
1374 | // 0 %0 = ... |
1375 | // 16 early-clobber %0 = Op %0 (tied-def 0), ... |
1376 | // 32 ... = Op %0 |
1377 | // Before extend: |
1378 | // %0 = [0r, 0d) [16e, 32d) |
1379 | // The point we want to extend is 0d to 16e not 16r in this case, but if |
1380 | // we use 16r here we will extend nothing because that already contained |
1381 | // in [16e, 32d). |
1382 | unsigned OpIdx = MO.getOperandNo(); |
1383 | unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx); |
1384 | const MachineOperand &DefOp = MI->getOperand(i: DefOpIdx); |
1385 | IsEarlyClobber = DefOp.isEarlyClobber(); |
1386 | } |
1387 | |
1388 | Idx = Idx.getRegSlot(EC: IsEarlyClobber); |
1389 | } |
1390 | |
1391 | SlotIndex Next = Idx; |
1392 | if (LI.hasSubRanges()) { |
1393 | // We have to delay extending subranges until we have seen all operands |
1394 | // defining the register. This is because a <def,read-undef> operand |
1395 | // will create an "undef" point, and we cannot extend any subranges |
1396 | // until all of them have been accounted for. |
1397 | if (MO.isUse()) |
1398 | ExtPoints.push_back(Elt: ExtPoint(MO, RegIdx, Next)); |
1399 | } else { |
1400 | LiveIntervalCalc &LIC = getLICalc(RegIdx); |
1401 | LIC.extend(LR&: LI, Use: Next, PhysReg: 0, Undefs: ArrayRef<SlotIndex>()); |
1402 | } |
1403 | } |
1404 | |
1405 | for (ExtPoint &EP : ExtPoints) { |
1406 | LiveInterval &LI = LIS.getInterval(Reg: Edit->get(idx: EP.RegIdx)); |
1407 | assert(LI.hasSubRanges()); |
1408 | |
1409 | LiveIntervalCalc SubLIC; |
1410 | Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg(); |
1411 | LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(SubIdx: Sub) |
1412 | : MRI.getMaxLaneMaskForVReg(Reg); |
1413 | for (LiveInterval::SubRange &S : LI.subranges()) { |
1414 | if ((S.LaneMask & LM).none()) |
1415 | continue; |
1416 | // The problem here can be that the new register may have been created |
1417 | // for a partially defined original register. For example: |
1418 | // %0:subreg_hireg<def,read-undef> = ... |
1419 | // ... |
1420 | // %1 = COPY %0 |
1421 | if (S.empty()) |
1422 | continue; |
1423 | SubLIC.reset(mf: &VRM.getMachineFunction(), SI: LIS.getSlotIndexes(), MDT: &MDT, |
1424 | VNIA: &LIS.getVNInfoAllocator()); |
1425 | SmallVector<SlotIndex, 4> Undefs; |
1426 | LI.computeSubRangeUndefs(Undefs, LaneMask: S.LaneMask, MRI, Indexes: *LIS.getSlotIndexes()); |
1427 | SubLIC.extend(LR&: S, Use: EP.Next, PhysReg: 0, Undefs); |
1428 | } |
1429 | } |
1430 | |
1431 | for (Register R : *Edit) { |
1432 | LiveInterval &LI = LIS.getInterval(Reg: R); |
1433 | if (!LI.hasSubRanges()) |
1434 | continue; |
1435 | LI.clear(); |
1436 | LI.removeEmptySubRanges(); |
1437 | LIS.constructMainRangeFromSubranges(LI); |
1438 | } |
1439 | } |
1440 | |
1441 | void SplitEditor::deleteRematVictims() { |
1442 | SmallVector<MachineInstr*, 8> Dead; |
1443 | for (const Register &R : *Edit) { |
1444 | LiveInterval *LI = &LIS.getInterval(Reg: R); |
1445 | for (const LiveRange::Segment &S : LI->segments) { |
1446 | // Dead defs end at the dead slot. |
1447 | if (S.end != S.valno->def.getDeadSlot()) |
1448 | continue; |
1449 | if (S.valno->isPHIDef()) |
1450 | continue; |
1451 | MachineInstr *MI = LIS.getInstructionFromIndex(index: S.valno->def); |
1452 | assert(MI && "Missing instruction for dead def" ); |
1453 | MI->addRegisterDead(Reg: LI->reg(), RegInfo: &TRI); |
1454 | |
1455 | if (!MI->allDefsAreDead()) |
1456 | continue; |
1457 | |
1458 | LLVM_DEBUG(dbgs() << "All defs dead: " << *MI); |
1459 | Dead.push_back(Elt: MI); |
1460 | } |
1461 | } |
1462 | |
1463 | if (Dead.empty()) |
1464 | return; |
1465 | |
1466 | Edit->eliminateDeadDefs(Dead, RegsBeingSpilled: std::nullopt); |
1467 | } |
1468 | |
1469 | void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) { |
1470 | // Fast-path for common case. |
1471 | if (!ParentVNI.isPHIDef()) { |
1472 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) |
1473 | forceRecompute(RegIdx: I, ParentVNI); |
1474 | return; |
1475 | } |
1476 | |
1477 | // Trace value through phis. |
1478 | SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist. |
1479 | SmallVector<const VNInfo *, 4> WorkList; |
1480 | Visited.insert(Ptr: &ParentVNI); |
1481 | WorkList.push_back(Elt: &ParentVNI); |
1482 | |
1483 | const LiveInterval &ParentLI = Edit->getParent(); |
1484 | const SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
1485 | do { |
1486 | const VNInfo &VNI = *WorkList.back(); |
1487 | WorkList.pop_back(); |
1488 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) |
1489 | forceRecompute(RegIdx: I, ParentVNI: VNI); |
1490 | if (!VNI.isPHIDef()) |
1491 | continue; |
1492 | |
1493 | MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(index: VNI.def); |
1494 | for (const MachineBasicBlock *Pred : MBB.predecessors()) { |
1495 | SlotIndex PredEnd = Indexes.getMBBEndIdx(mbb: Pred); |
1496 | VNInfo *PredVNI = ParentLI.getVNInfoBefore(Idx: PredEnd); |
1497 | assert(PredVNI && "Value available in PhiVNI predecessor" ); |
1498 | if (Visited.insert(Ptr: PredVNI).second) |
1499 | WorkList.push_back(Elt: PredVNI); |
1500 | } |
1501 | } while(!WorkList.empty()); |
1502 | } |
1503 | |
1504 | void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { |
1505 | ++NumFinished; |
1506 | |
1507 | // At this point, the live intervals in Edit contain VNInfos corresponding to |
1508 | // the inserted copies. |
1509 | |
1510 | // Add the original defs from the parent interval. |
1511 | for (const VNInfo *ParentVNI : Edit->getParent().valnos) { |
1512 | if (ParentVNI->isUnused()) |
1513 | continue; |
1514 | unsigned RegIdx = RegAssign.lookup(x: ParentVNI->def); |
1515 | defValue(RegIdx, ParentVNI, Idx: ParentVNI->def, Original: true); |
1516 | |
1517 | // Force rematted values to be recomputed everywhere. |
1518 | // The new live ranges may be truncated. |
1519 | if (Edit->didRematerialize(ParentVNI)) |
1520 | forceRecomputeVNI(ParentVNI: *ParentVNI); |
1521 | } |
1522 | |
1523 | // Hoist back-copies to the complement interval when in spill mode. |
1524 | switch (SpillMode) { |
1525 | case SM_Partition: |
1526 | // Leave all back-copies as is. |
1527 | break; |
1528 | case SM_Size: |
1529 | case SM_Speed: |
1530 | // hoistCopies will behave differently between size and speed. |
1531 | hoistCopies(); |
1532 | } |
1533 | |
1534 | // Transfer the simply mapped values, check if any are skipped. |
1535 | bool Skipped = transferValues(); |
1536 | |
1537 | // Rewrite virtual registers, possibly extending ranges. |
1538 | rewriteAssigned(ExtendRanges: Skipped); |
1539 | |
1540 | if (Skipped) |
1541 | extendPHIKillRanges(); |
1542 | else |
1543 | ++NumSimple; |
1544 | |
1545 | // Delete defs that were rematted everywhere. |
1546 | if (Skipped) |
1547 | deleteRematVictims(); |
1548 | |
1549 | // Get rid of unused values and set phi-kill flags. |
1550 | for (Register Reg : *Edit) { |
1551 | LiveInterval &LI = LIS.getInterval(Reg); |
1552 | LI.removeEmptySubRanges(); |
1553 | LI.RenumberValues(); |
1554 | } |
1555 | |
1556 | // Provide a reverse mapping from original indices to Edit ranges. |
1557 | if (LRMap) { |
1558 | auto Seq = llvm::seq<unsigned>(Begin: 0, End: Edit->size()); |
1559 | LRMap->assign(in_start: Seq.begin(), in_end: Seq.end()); |
1560 | } |
1561 | |
1562 | // Now check if any registers were separated into multiple components. |
1563 | ConnectedVNInfoEqClasses ConEQ(LIS); |
1564 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) { |
1565 | // Don't use iterators, they are invalidated by create() below. |
1566 | Register VReg = Edit->get(idx: i); |
1567 | LiveInterval &LI = LIS.getInterval(Reg: VReg); |
1568 | SmallVector<LiveInterval*, 8> SplitLIs; |
1569 | LIS.splitSeparateComponents(LI, SplitLIs); |
1570 | Register Original = VRM.getOriginal(VirtReg: VReg); |
1571 | for (LiveInterval *SplitLI : SplitLIs) |
1572 | VRM.setIsSplitFromReg(virtReg: SplitLI->reg(), SReg: Original); |
1573 | |
1574 | // The new intervals all map back to i. |
1575 | if (LRMap) |
1576 | LRMap->resize(N: Edit->size(), NV: i); |
1577 | } |
1578 | |
1579 | // Calculate spill weight and allocation hints for new intervals. |
1580 | Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI); |
1581 | |
1582 | assert(!LRMap || LRMap->size() == Edit->size()); |
1583 | } |
1584 | |
1585 | //===----------------------------------------------------------------------===// |
1586 | // Single Block Splitting |
1587 | //===----------------------------------------------------------------------===// |
1588 | |
1589 | bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, |
1590 | bool SingleInstrs) const { |
1591 | // Always split for multiple instructions. |
1592 | if (!BI.isOneInstr()) |
1593 | return true; |
1594 | // Don't split for single instructions unless explicitly requested. |
1595 | if (!SingleInstrs) |
1596 | return false; |
1597 | // Splitting a live-through range always makes progress. |
1598 | if (BI.LiveIn && BI.LiveOut) |
1599 | return true; |
1600 | // No point in isolating a copy. It has no register class constraints. |
1601 | MachineInstr *MI = LIS.getInstructionFromIndex(index: BI.FirstInstr); |
1602 | bool copyLike = TII.isCopyInstr(MI: *MI) || MI->isSubregToReg(); |
1603 | if (copyLike) |
1604 | return false; |
1605 | // Finally, don't isolate an end point that was created by earlier splits. |
1606 | return isOriginalEndpoint(Idx: BI.FirstInstr); |
1607 | } |
1608 | |
1609 | void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { |
1610 | openIntv(); |
1611 | SlotIndex LastSplitPoint = SA.getLastSplitPoint(BB: BI.MBB); |
1612 | SlotIndex SegStart = enterIntvBefore(Idx: std::min(a: BI.FirstInstr, |
1613 | b: LastSplitPoint)); |
1614 | if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { |
1615 | useIntv(Start: SegStart, End: leaveIntvAfter(Idx: BI.LastInstr)); |
1616 | } else { |
1617 | // The last use is after the last valid split point. |
1618 | SlotIndex SegStop = leaveIntvBefore(Idx: LastSplitPoint); |
1619 | useIntv(Start: SegStart, End: SegStop); |
1620 | overlapIntv(Start: SegStop, End: BI.LastInstr); |
1621 | } |
1622 | } |
1623 | |
1624 | //===----------------------------------------------------------------------===// |
1625 | // Global Live Range Splitting Support |
1626 | //===----------------------------------------------------------------------===// |
1627 | |
1628 | // These methods support a method of global live range splitting that uses a |
1629 | // global algorithm to decide intervals for CFG edges. They will insert split |
1630 | // points and color intervals in basic blocks while avoiding interference. |
1631 | // |
1632 | // Note that splitSingleBlock is also useful for blocks where both CFG edges |
1633 | // are on the stack. |
1634 | |
1635 | void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, |
1636 | unsigned IntvIn, SlotIndex LeaveBefore, |
1637 | unsigned IntvOut, SlotIndex EnterAfter){ |
1638 | SlotIndex Start, Stop; |
1639 | std::tie(args&: Start, args&: Stop) = LIS.getSlotIndexes()->getMBBRange(Num: MBBNum); |
1640 | |
1641 | LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop |
1642 | << ") intf " << LeaveBefore << '-' << EnterAfter |
1643 | << ", live-through " << IntvIn << " -> " << IntvOut); |
1644 | |
1645 | assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks" ); |
1646 | |
1647 | assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block" ); |
1648 | assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf" ); |
1649 | assert((!EnterAfter || EnterAfter >= Start) && "Interference before block" ); |
1650 | |
1651 | MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(N: MBBNum); |
1652 | |
1653 | if (!IntvOut) { |
1654 | LLVM_DEBUG(dbgs() << ", spill on entry.\n" ); |
1655 | // |
1656 | // <<<<<<<<< Possible LeaveBefore interference. |
1657 | // |-----------| Live through. |
1658 | // -____________ Spill on entry. |
1659 | // |
1660 | selectIntv(Idx: IntvIn); |
1661 | SlotIndex Idx = leaveIntvAtTop(MBB&: *MBB); |
1662 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference" ); |
1663 | (void)Idx; |
1664 | return; |
1665 | } |
1666 | |
1667 | if (!IntvIn) { |
1668 | LLVM_DEBUG(dbgs() << ", reload on exit.\n" ); |
1669 | // |
1670 | // >>>>>>> Possible EnterAfter interference. |
1671 | // |-----------| Live through. |
1672 | // ___________-- Reload on exit. |
1673 | // |
1674 | selectIntv(Idx: IntvOut); |
1675 | SlotIndex Idx = enterIntvAtEnd(MBB&: *MBB); |
1676 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference" ); |
1677 | (void)Idx; |
1678 | return; |
1679 | } |
1680 | |
1681 | if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { |
1682 | LLVM_DEBUG(dbgs() << ", straight through.\n" ); |
1683 | // |
1684 | // |-----------| Live through. |
1685 | // ------------- Straight through, same intv, no interference. |
1686 | // |
1687 | selectIntv(Idx: IntvOut); |
1688 | useIntv(Start, End: Stop); |
1689 | return; |
1690 | } |
1691 | |
1692 | // We cannot legally insert splits after LSP. |
1693 | SlotIndex LSP = SA.getLastSplitPoint(Num: MBBNum); |
1694 | assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf" ); |
1695 | |
1696 | if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || |
1697 | LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { |
1698 | LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n" ); |
1699 | // |
1700 | // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. |
1701 | // |-----------| Live through. |
1702 | // ------======= Switch intervals between interference. |
1703 | // |
1704 | selectIntv(Idx: IntvOut); |
1705 | SlotIndex Idx; |
1706 | if (LeaveBefore && LeaveBefore < LSP) { |
1707 | Idx = enterIntvBefore(Idx: LeaveBefore); |
1708 | useIntv(Start: Idx, End: Stop); |
1709 | } else { |
1710 | Idx = enterIntvAtEnd(MBB&: *MBB); |
1711 | } |
1712 | selectIntv(Idx: IntvIn); |
1713 | useIntv(Start, End: Idx); |
1714 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference" ); |
1715 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference" ); |
1716 | return; |
1717 | } |
1718 | |
1719 | LLVM_DEBUG(dbgs() << ", create local intv for interference.\n" ); |
1720 | // |
1721 | // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. |
1722 | // |-----------| Live through. |
1723 | // ==---------== Switch intervals before/after interference. |
1724 | // |
1725 | assert(LeaveBefore <= EnterAfter && "Missed case" ); |
1726 | |
1727 | selectIntv(Idx: IntvOut); |
1728 | SlotIndex Idx = enterIntvAfter(Idx: EnterAfter); |
1729 | useIntv(Start: Idx, End: Stop); |
1730 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference" ); |
1731 | |
1732 | selectIntv(Idx: IntvIn); |
1733 | Idx = leaveIntvBefore(Idx: LeaveBefore); |
1734 | useIntv(Start, End: Idx); |
1735 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference" ); |
1736 | } |
1737 | |
1738 | void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, |
1739 | unsigned IntvIn, SlotIndex LeaveBefore) { |
1740 | SlotIndex Start, Stop; |
1741 | std::tie(args&: Start, args&: Stop) = LIS.getSlotIndexes()->getMBBRange(MBB: BI.MBB); |
1742 | |
1743 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';' |
1744 | << Stop << "), uses " << BI.FirstInstr << '-' |
1745 | << BI.LastInstr << ", reg-in " << IntvIn |
1746 | << ", leave before " << LeaveBefore |
1747 | << (BI.LiveOut ? ", stack-out" : ", killed in block" )); |
1748 | |
1749 | assert(IntvIn && "Must have register in" ); |
1750 | assert(BI.LiveIn && "Must be live-in" ); |
1751 | assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference" ); |
1752 | |
1753 | if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { |
1754 | LLVM_DEBUG(dbgs() << " before interference.\n" ); |
1755 | // |
1756 | // <<< Interference after kill. |
1757 | // |---o---x | Killed in block. |
1758 | // ========= Use IntvIn everywhere. |
1759 | // |
1760 | selectIntv(Idx: IntvIn); |
1761 | useIntv(Start, End: BI.LastInstr); |
1762 | return; |
1763 | } |
1764 | |
1765 | SlotIndex LSP = SA.getLastSplitPoint(BB: BI.MBB); |
1766 | |
1767 | if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { |
1768 | // |
1769 | // <<< Possible interference after last use. |
1770 | // |---o---o---| Live-out on stack. |
1771 | // =========____ Leave IntvIn after last use. |
1772 | // |
1773 | // < Interference after last use. |
1774 | // |---o---o--o| Live-out on stack, late last use. |
1775 | // ============ Copy to stack after LSP, overlap IntvIn. |
1776 | // \_____ Stack interval is live-out. |
1777 | // |
1778 | if (BI.LastInstr < LSP) { |
1779 | LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n" ); |
1780 | selectIntv(Idx: IntvIn); |
1781 | SlotIndex Idx = leaveIntvAfter(Idx: BI.LastInstr); |
1782 | useIntv(Start, End: Idx); |
1783 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference" ); |
1784 | } else { |
1785 | LLVM_DEBUG(dbgs() << ", spill before last split point.\n" ); |
1786 | selectIntv(Idx: IntvIn); |
1787 | SlotIndex Idx = leaveIntvBefore(Idx: LSP); |
1788 | overlapIntv(Start: Idx, End: BI.LastInstr); |
1789 | useIntv(Start, End: Idx); |
1790 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference" ); |
1791 | } |
1792 | return; |
1793 | } |
1794 | |
1795 | // The interference is overlapping somewhere we wanted to use IntvIn. That |
1796 | // means we need to create a local interval that can be allocated a |
1797 | // different register. |
1798 | unsigned LocalIntv = openIntv(); |
1799 | (void)LocalIntv; |
1800 | LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n" ); |
1801 | |
1802 | if (!BI.LiveOut || BI.LastInstr < LSP) { |
1803 | // |
1804 | // <<<<<<< Interference overlapping uses. |
1805 | // |---o---o---| Live-out on stack. |
1806 | // =====----____ Leave IntvIn before interference, then spill. |
1807 | // |
1808 | SlotIndex To = leaveIntvAfter(Idx: BI.LastInstr); |
1809 | SlotIndex From = enterIntvBefore(Idx: LeaveBefore); |
1810 | useIntv(Start: From, End: To); |
1811 | selectIntv(Idx: IntvIn); |
1812 | useIntv(Start, End: From); |
1813 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference" ); |
1814 | return; |
1815 | } |
1816 | |
1817 | // <<<<<<< Interference overlapping uses. |
1818 | // |---o---o--o| Live-out on stack, late last use. |
1819 | // =====------- Copy to stack before LSP, overlap LocalIntv. |
1820 | // \_____ Stack interval is live-out. |
1821 | // |
1822 | SlotIndex To = leaveIntvBefore(Idx: LSP); |
1823 | overlapIntv(Start: To, End: BI.LastInstr); |
1824 | SlotIndex From = enterIntvBefore(Idx: std::min(a: To, b: LeaveBefore)); |
1825 | useIntv(Start: From, End: To); |
1826 | selectIntv(Idx: IntvIn); |
1827 | useIntv(Start, End: From); |
1828 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference" ); |
1829 | } |
1830 | |
1831 | void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, |
1832 | unsigned IntvOut, SlotIndex EnterAfter) { |
1833 | SlotIndex Start, Stop; |
1834 | std::tie(args&: Start, args&: Stop) = LIS.getSlotIndexes()->getMBBRange(MBB: BI.MBB); |
1835 | |
1836 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';' |
1837 | << Stop << "), uses " << BI.FirstInstr << '-' |
1838 | << BI.LastInstr << ", reg-out " << IntvOut |
1839 | << ", enter after " << EnterAfter |
1840 | << (BI.LiveIn ? ", stack-in" : ", defined in block" )); |
1841 | |
1842 | SlotIndex LSP = SA.getLastSplitPoint(BB: BI.MBB); |
1843 | |
1844 | assert(IntvOut && "Must have register out" ); |
1845 | assert(BI.LiveOut && "Must be live-out" ); |
1846 | assert((!EnterAfter || EnterAfter < LSP) && "Bad interference" ); |
1847 | |
1848 | if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { |
1849 | LLVM_DEBUG(dbgs() << " after interference.\n" ); |
1850 | // |
1851 | // >>>> Interference before def. |
1852 | // | o---o---| Defined in block. |
1853 | // ========= Use IntvOut everywhere. |
1854 | // |
1855 | selectIntv(Idx: IntvOut); |
1856 | useIntv(Start: BI.FirstInstr, End: Stop); |
1857 | return; |
1858 | } |
1859 | |
1860 | if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { |
1861 | LLVM_DEBUG(dbgs() << ", reload after interference.\n" ); |
1862 | // |
1863 | // >>>> Interference before def. |
1864 | // |---o---o---| Live-through, stack-in. |
1865 | // ____========= Enter IntvOut before first use. |
1866 | // |
1867 | selectIntv(Idx: IntvOut); |
1868 | SlotIndex Idx = enterIntvBefore(Idx: std::min(a: LSP, b: BI.FirstInstr)); |
1869 | useIntv(Start: Idx, End: Stop); |
1870 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference" ); |
1871 | return; |
1872 | } |
1873 | |
1874 | // The interference is overlapping somewhere we wanted to use IntvOut. That |
1875 | // means we need to create a local interval that can be allocated a |
1876 | // different register. |
1877 | LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n" ); |
1878 | // |
1879 | // >>>>>>> Interference overlapping uses. |
1880 | // |---o---o---| Live-through, stack-in. |
1881 | // ____---====== Create local interval for interference range. |
1882 | // |
1883 | selectIntv(Idx: IntvOut); |
1884 | SlotIndex Idx = enterIntvAfter(Idx: EnterAfter); |
1885 | useIntv(Start: Idx, End: Stop); |
1886 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference" ); |
1887 | |
1888 | openIntv(); |
1889 | SlotIndex From = enterIntvBefore(Idx: std::min(a: Idx, b: BI.FirstInstr)); |
1890 | useIntv(Start: From, End: Idx); |
1891 | } |
1892 | |
1893 | void SplitAnalysis::BlockInfo::print(raw_ostream &OS) const { |
1894 | OS << "{" << printMBBReference(MBB: *MBB) << ", " |
1895 | << "uses " << FirstInstr << " to " << LastInstr << ", " |
1896 | << "1st def " << FirstDef << ", " |
1897 | << (LiveIn ? "live in" : "dead in" ) << ", " |
1898 | << (LiveOut ? "live out" : "dead out" ) << "}" ; |
1899 | } |
1900 | |
1901 | void SplitAnalysis::BlockInfo::dump() const { |
1902 | print(OS&: dbgs()); |
1903 | dbgs() << "\n" ; |
1904 | } |
1905 | |