1 //===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
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
7 //===----------------------------------------------------------------------===//
9 // The inline spiller modifies the machine function directly instead of
10 // inserting spills and restores in VirtRegMap.
12 //===----------------------------------------------------------------------===//
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/MapVector.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/CodeGen/LiveInterval.h"
27 #include "llvm/CodeGen/LiveIntervals.h"
28 #include "llvm/CodeGen/LiveRangeCalc.h"
29 #include "llvm/CodeGen/LiveRangeEdit.h"
30 #include "llvm/CodeGen/LiveStacks.h"
31 #include "llvm/CodeGen/MachineBasicBlock.h"
32 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
33 #include "llvm/CodeGen/MachineDominators.h"
34 #include "llvm/CodeGen/MachineFunction.h"
35 #include "llvm/CodeGen/MachineFunctionPass.h"
36 #include "llvm/CodeGen/MachineInstr.h"
37 #include "llvm/CodeGen/MachineInstrBuilder.h"
38 #include "llvm/CodeGen/MachineInstrBundle.h"
39 #include "llvm/CodeGen/MachineLoopInfo.h"
40 #include "llvm/CodeGen/MachineOperand.h"
41 #include "llvm/CodeGen/MachineRegisterInfo.h"
42 #include "llvm/CodeGen/SlotIndexes.h"
43 #include "llvm/CodeGen/TargetInstrInfo.h"
44 #include "llvm/CodeGen/TargetOpcodes.h"
45 #include "llvm/CodeGen/TargetRegisterInfo.h"
46 #include "llvm/CodeGen/TargetSubtargetInfo.h"
47 #include "llvm/CodeGen/VirtRegMap.h"
48 #include "llvm/Config/llvm-config.h"
49 #include "llvm/Support/BlockFrequency.h"
50 #include "llvm/Support/BranchProbability.h"
51 #include "llvm/Support/CommandLine.h"
52 #include "llvm/Support/Compiler.h"
53 #include "llvm/Support/Debug.h"
54 #include "llvm/Support/ErrorHandling.h"
55 #include "llvm/Support/raw_ostream.h"
64 #define DEBUG_TYPE "regalloc"
66 STATISTIC(NumSpilledRanges
, "Number of spilled live ranges");
67 STATISTIC(NumSnippets
, "Number of spilled snippets");
68 STATISTIC(NumSpills
, "Number of spills inserted");
69 STATISTIC(NumSpillsRemoved
, "Number of spills removed");
70 STATISTIC(NumReloads
, "Number of reloads inserted");
71 STATISTIC(NumReloadsRemoved
, "Number of reloads removed");
72 STATISTIC(NumFolded
, "Number of folded stack accesses");
73 STATISTIC(NumFoldedLoads
, "Number of folded loads");
74 STATISTIC(NumRemats
, "Number of rematerialized defs for spilling");
76 static cl::opt
<bool> DisableHoisting("disable-spill-hoist", cl::Hidden
,
77 cl::desc("Disable inline spill hoisting"));
79 RestrictStatepointRemat("restrict-statepoint-remat",
80 cl::init(false), cl::Hidden
,
81 cl::desc("Restrict remat for statepoint operands"));
85 class HoistSpillHelper
: private LiveRangeEdit::Delegate
{
90 MachineDominatorTree
&MDT
;
91 MachineLoopInfo
&Loops
;
93 MachineRegisterInfo
&MRI
;
94 const TargetInstrInfo
&TII
;
95 const TargetRegisterInfo
&TRI
;
96 const MachineBlockFrequencyInfo
&MBFI
;
98 InsertPointAnalysis IPA
;
100 // Map from StackSlot to the LiveInterval of the original register.
101 // Note the LiveInterval of the original register may have been deleted
102 // after it is spilled. We keep a copy here to track the range where
103 // spills can be moved.
104 DenseMap
<int, std::unique_ptr
<LiveInterval
>> StackSlotToOrigLI
;
106 // Map from pair of (StackSlot and Original VNI) to a set of spills which
107 // have the same stackslot and have equal values defined by Original VNI.
108 // These spills are mergeable and are hoist candiates.
109 using MergeableSpillsMap
=
110 MapVector
<std::pair
<int, VNInfo
*>, SmallPtrSet
<MachineInstr
*, 16>>;
111 MergeableSpillsMap MergeableSpills
;
113 /// This is the map from original register to a set containing all its
114 /// siblings. To hoist a spill to another BB, we need to find out a live
115 /// sibling there and use it as the source of the new spill.
116 DenseMap
<unsigned, SmallSetVector
<unsigned, 16>> Virt2SiblingsMap
;
118 bool isSpillCandBB(LiveInterval
&OrigLI
, VNInfo
&OrigVNI
,
119 MachineBasicBlock
&BB
, unsigned &LiveReg
);
121 void rmRedundantSpills(
122 SmallPtrSet
<MachineInstr
*, 16> &Spills
,
123 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
124 DenseMap
<MachineDomTreeNode
*, MachineInstr
*> &SpillBBToSpill
);
127 MachineBasicBlock
*Root
, SmallPtrSet
<MachineInstr
*, 16> &Spills
,
128 SmallVectorImpl
<MachineDomTreeNode
*> &Orders
,
129 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
130 DenseMap
<MachineDomTreeNode
*, unsigned> &SpillsToKeep
,
131 DenseMap
<MachineDomTreeNode
*, MachineInstr
*> &SpillBBToSpill
);
133 void runHoistSpills(LiveInterval
&OrigLI
, VNInfo
&OrigVNI
,
134 SmallPtrSet
<MachineInstr
*, 16> &Spills
,
135 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
136 DenseMap
<MachineBasicBlock
*, unsigned> &SpillsToIns
);
139 HoistSpillHelper(MachineFunctionPass
&pass
, MachineFunction
&mf
,
141 : MF(mf
), LIS(pass
.getAnalysis
<LiveIntervals
>()),
142 LSS(pass
.getAnalysis
<LiveStacks
>()),
143 AA(&pass
.getAnalysis
<AAResultsWrapperPass
>().getAAResults()),
144 MDT(pass
.getAnalysis
<MachineDominatorTree
>()),
145 Loops(pass
.getAnalysis
<MachineLoopInfo
>()), VRM(vrm
),
146 MRI(mf
.getRegInfo()), TII(*mf
.getSubtarget().getInstrInfo()),
147 TRI(*mf
.getSubtarget().getRegisterInfo()),
148 MBFI(pass
.getAnalysis
<MachineBlockFrequencyInfo
>()),
149 IPA(LIS
, mf
.getNumBlockIDs()) {}
151 void addToMergeableSpills(MachineInstr
&Spill
, int StackSlot
,
153 bool rmFromMergeableSpills(MachineInstr
&Spill
, int StackSlot
);
154 void hoistAllSpills();
155 void LRE_DidCloneVirtReg(unsigned, unsigned) override
;
158 class InlineSpiller
: public Spiller
{
163 MachineDominatorTree
&MDT
;
164 MachineLoopInfo
&Loops
;
166 MachineRegisterInfo
&MRI
;
167 const TargetInstrInfo
&TII
;
168 const TargetRegisterInfo
&TRI
;
169 const MachineBlockFrequencyInfo
&MBFI
;
171 // Variables that are valid during spill(), but used by multiple methods.
173 LiveInterval
*StackInt
;
177 // All registers to spill to StackSlot, including the main register.
178 SmallVector
<unsigned, 8> RegsToSpill
;
180 // All COPY instructions to/from snippets.
181 // They are ignored since both operands refer to the same stack slot.
182 SmallPtrSet
<MachineInstr
*, 8> SnippetCopies
;
184 // Values that failed to remat at some point.
185 SmallPtrSet
<VNInfo
*, 8> UsedValues
;
187 // Dead defs generated during spilling.
188 SmallVector
<MachineInstr
*, 8> DeadDefs
;
190 // Object records spills information and does the hoisting.
191 HoistSpillHelper HSpiller
;
193 ~InlineSpiller() override
= default;
196 InlineSpiller(MachineFunctionPass
&pass
, MachineFunction
&mf
, VirtRegMap
&vrm
)
197 : MF(mf
), LIS(pass
.getAnalysis
<LiveIntervals
>()),
198 LSS(pass
.getAnalysis
<LiveStacks
>()),
199 AA(&pass
.getAnalysis
<AAResultsWrapperPass
>().getAAResults()),
200 MDT(pass
.getAnalysis
<MachineDominatorTree
>()),
201 Loops(pass
.getAnalysis
<MachineLoopInfo
>()), VRM(vrm
),
202 MRI(mf
.getRegInfo()), TII(*mf
.getSubtarget().getInstrInfo()),
203 TRI(*mf
.getSubtarget().getRegisterInfo()),
204 MBFI(pass
.getAnalysis
<MachineBlockFrequencyInfo
>()),
205 HSpiller(pass
, mf
, vrm
) {}
207 void spill(LiveRangeEdit
&) override
;
208 void postOptimization() override
;
211 bool isSnippet(const LiveInterval
&SnipLI
);
212 void collectRegsToSpill();
214 bool isRegToSpill(unsigned Reg
) { return is_contained(RegsToSpill
, Reg
); }
216 bool isSibling(unsigned Reg
);
217 bool hoistSpillInsideBB(LiveInterval
&SpillLI
, MachineInstr
&CopyMI
);
218 void eliminateRedundantSpills(LiveInterval
&LI
, VNInfo
*VNI
);
220 void markValueUsed(LiveInterval
*, VNInfo
*);
221 bool canGuaranteeAssignmentAfterRemat(unsigned VReg
, MachineInstr
&MI
);
222 bool reMaterializeFor(LiveInterval
&, MachineInstr
&MI
);
223 void reMaterializeAll();
225 bool coalesceStackAccess(MachineInstr
*MI
, unsigned Reg
);
226 bool foldMemoryOperand(ArrayRef
<std::pair
<MachineInstr
*, unsigned>>,
227 MachineInstr
*LoadMI
= nullptr);
228 void insertReload(unsigned VReg
, SlotIndex
, MachineBasicBlock::iterator MI
);
229 void insertSpill(unsigned VReg
, bool isKill
, MachineBasicBlock::iterator MI
);
231 void spillAroundUses(unsigned Reg
);
235 } // end anonymous namespace
237 Spiller::~Spiller() = default;
239 void Spiller::anchor() {}
241 Spiller
*llvm::createInlineSpiller(MachineFunctionPass
&pass
,
244 return new InlineSpiller(pass
, mf
, vrm
);
247 //===----------------------------------------------------------------------===//
249 //===----------------------------------------------------------------------===//
251 // When spilling a virtual register, we also spill any snippets it is connected
252 // to. The snippets are small live ranges that only have a single real use,
253 // leftovers from live range splitting. Spilling them enables memory operand
254 // folding or tightens the live range around the single use.
256 // This minimizes register pressure and maximizes the store-to-load distance for
257 // spill slots which can be important in tight loops.
259 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
260 /// otherwise return 0.
261 static unsigned isFullCopyOf(const MachineInstr
&MI
, unsigned Reg
) {
262 if (!MI
.isFullCopy())
264 if (MI
.getOperand(0).getReg() == Reg
)
265 return MI
.getOperand(1).getReg();
266 if (MI
.getOperand(1).getReg() == Reg
)
267 return MI
.getOperand(0).getReg();
271 /// isSnippet - Identify if a live interval is a snippet that should be spilled.
272 /// It is assumed that SnipLI is a virtual register with the same original as
274 bool InlineSpiller::isSnippet(const LiveInterval
&SnipLI
) {
275 unsigned Reg
= Edit
->getReg();
277 // A snippet is a tiny live range with only a single instruction using it
278 // besides copies to/from Reg or spills/fills. We accept:
280 // %snip = COPY %Reg / FILL fi#
282 // %Reg = COPY %snip / SPILL %snip, fi#
284 if (SnipLI
.getNumValNums() > 2 || !LIS
.intervalIsInOneMBB(SnipLI
))
287 MachineInstr
*UseMI
= nullptr;
289 // Check that all uses satisfy our criteria.
290 for (MachineRegisterInfo::reg_instr_nodbg_iterator
291 RI
= MRI
.reg_instr_nodbg_begin(SnipLI
.reg
),
292 E
= MRI
.reg_instr_nodbg_end(); RI
!= E
; ) {
293 MachineInstr
&MI
= *RI
++;
295 // Allow copies to/from Reg.
296 if (isFullCopyOf(MI
, Reg
))
299 // Allow stack slot loads.
301 if (SnipLI
.reg
== TII
.isLoadFromStackSlot(MI
, FI
) && FI
== StackSlot
)
304 // Allow stack slot stores.
305 if (SnipLI
.reg
== TII
.isStoreToStackSlot(MI
, FI
) && FI
== StackSlot
)
308 // Allow a single additional instruction.
309 if (UseMI
&& &MI
!= UseMI
)
316 /// collectRegsToSpill - Collect live range snippets that only have a single
318 void InlineSpiller::collectRegsToSpill() {
319 unsigned Reg
= Edit
->getReg();
321 // Main register always spills.
322 RegsToSpill
.assign(1, Reg
);
323 SnippetCopies
.clear();
325 // Snippets all have the same original, so there can't be any for an original
330 for (MachineRegisterInfo::reg_instr_iterator
331 RI
= MRI
.reg_instr_begin(Reg
), E
= MRI
.reg_instr_end(); RI
!= E
; ) {
332 MachineInstr
&MI
= *RI
++;
333 unsigned SnipReg
= isFullCopyOf(MI
, Reg
);
334 if (!isSibling(SnipReg
))
336 LiveInterval
&SnipLI
= LIS
.getInterval(SnipReg
);
337 if (!isSnippet(SnipLI
))
339 SnippetCopies
.insert(&MI
);
340 if (isRegToSpill(SnipReg
))
342 RegsToSpill
.push_back(SnipReg
);
343 LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI
<< '\n');
348 bool InlineSpiller::isSibling(unsigned Reg
) {
349 return Register::isVirtualRegister(Reg
) && VRM
.getOriginal(Reg
) == Original
;
352 /// It is beneficial to spill to earlier place in the same BB in case
354 /// There is an alternative def earlier in the same MBB.
355 /// Hoist the spill as far as possible in SpillMBB. This can ease
356 /// register pressure:
362 /// Hoisting the spill of s to immediately after the def removes the
363 /// interference between x and y:
369 /// This hoist only helps when the copy kills its source.
371 bool InlineSpiller::hoistSpillInsideBB(LiveInterval
&SpillLI
,
372 MachineInstr
&CopyMI
) {
373 SlotIndex Idx
= LIS
.getInstructionIndex(CopyMI
);
375 VNInfo
*VNI
= SpillLI
.getVNInfoAt(Idx
.getRegSlot());
376 assert(VNI
&& VNI
->def
== Idx
.getRegSlot() && "Not defined by copy");
379 Register SrcReg
= CopyMI
.getOperand(1).getReg();
380 LiveInterval
&SrcLI
= LIS
.getInterval(SrcReg
);
381 VNInfo
*SrcVNI
= SrcLI
.getVNInfoAt(Idx
);
382 LiveQueryResult SrcQ
= SrcLI
.Query(Idx
);
383 MachineBasicBlock
*DefMBB
= LIS
.getMBBFromIndex(SrcVNI
->def
);
384 if (DefMBB
!= CopyMI
.getParent() || !SrcQ
.isKill())
387 // Conservatively extend the stack slot range to the range of the original
388 // value. We may be able to do better with stack slot coloring by being more
390 assert(StackInt
&& "No stack slot assigned yet.");
391 LiveInterval
&OrigLI
= LIS
.getInterval(Original
);
392 VNInfo
*OrigVNI
= OrigLI
.getVNInfoAt(Idx
);
393 StackInt
->MergeValueInAsValue(OrigLI
, OrigVNI
, StackInt
->getValNumInfo(0));
394 LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI
->id
<< ": "
395 << *StackInt
<< '\n');
397 // We are going to spill SrcVNI immediately after its def, so clear out
398 // any later spills of the same value.
399 eliminateRedundantSpills(SrcLI
, SrcVNI
);
401 MachineBasicBlock
*MBB
= LIS
.getMBBFromIndex(SrcVNI
->def
);
402 MachineBasicBlock::iterator MII
;
403 if (SrcVNI
->isPHIDef())
404 MII
= MBB
->SkipPHIsLabelsAndDebug(MBB
->begin());
406 MachineInstr
*DefMI
= LIS
.getInstructionFromIndex(SrcVNI
->def
);
407 assert(DefMI
&& "Defining instruction disappeared");
411 // Insert spill without kill flag immediately after def.
412 TII
.storeRegToStackSlot(*MBB
, MII
, SrcReg
, false, StackSlot
,
413 MRI
.getRegClass(SrcReg
), &TRI
);
414 --MII
; // Point to store instruction.
415 LIS
.InsertMachineInstrInMaps(*MII
);
416 LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI
->def
<< '\t' << *MII
);
418 HSpiller
.addToMergeableSpills(*MII
, StackSlot
, Original
);
423 /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
424 /// redundant spills of this value in SLI.reg and sibling copies.
425 void InlineSpiller::eliminateRedundantSpills(LiveInterval
&SLI
, VNInfo
*VNI
) {
426 assert(VNI
&& "Missing value");
427 SmallVector
<std::pair
<LiveInterval
*, VNInfo
*>, 8> WorkList
;
428 WorkList
.push_back(std::make_pair(&SLI
, VNI
));
429 assert(StackInt
&& "No stack slot assigned yet.");
433 std::tie(LI
, VNI
) = WorkList
.pop_back_val();
434 unsigned Reg
= LI
->reg
;
435 LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI
->id
<< '@'
436 << VNI
->def
<< " in " << *LI
<< '\n');
438 // Regs to spill are taken care of.
439 if (isRegToSpill(Reg
))
442 // Add all of VNI's live range to StackInt.
443 StackInt
->MergeValueInAsValue(*LI
, VNI
, StackInt
->getValNumInfo(0));
444 LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt
<< '\n');
446 // Find all spills and copies of VNI.
447 for (MachineRegisterInfo::use_instr_nodbg_iterator
448 UI
= MRI
.use_instr_nodbg_begin(Reg
), E
= MRI
.use_instr_nodbg_end();
450 MachineInstr
&MI
= *UI
++;
451 if (!MI
.isCopy() && !MI
.mayStore())
453 SlotIndex Idx
= LIS
.getInstructionIndex(MI
);
454 if (LI
->getVNInfoAt(Idx
) != VNI
)
457 // Follow sibling copies down the dominator tree.
458 if (unsigned DstReg
= isFullCopyOf(MI
, Reg
)) {
459 if (isSibling(DstReg
)) {
460 LiveInterval
&DstLI
= LIS
.getInterval(DstReg
);
461 VNInfo
*DstVNI
= DstLI
.getVNInfoAt(Idx
.getRegSlot());
462 assert(DstVNI
&& "Missing defined value");
463 assert(DstVNI
->def
== Idx
.getRegSlot() && "Wrong copy def slot");
464 WorkList
.push_back(std::make_pair(&DstLI
, DstVNI
));
471 if (Reg
== TII
.isStoreToStackSlot(MI
, FI
) && FI
== StackSlot
) {
472 LLVM_DEBUG(dbgs() << "Redundant spill " << Idx
<< '\t' << MI
);
473 // eliminateDeadDefs won't normally remove stores, so switch opcode.
474 MI
.setDesc(TII
.get(TargetOpcode::KILL
));
475 DeadDefs
.push_back(&MI
);
477 if (HSpiller
.rmFromMergeableSpills(MI
, StackSlot
))
481 } while (!WorkList
.empty());
484 //===----------------------------------------------------------------------===//
486 //===----------------------------------------------------------------------===//
488 /// markValueUsed - Remember that VNI failed to rematerialize, so its defining
489 /// instruction cannot be eliminated. See through snippet copies
490 void InlineSpiller::markValueUsed(LiveInterval
*LI
, VNInfo
*VNI
) {
491 SmallVector
<std::pair
<LiveInterval
*, VNInfo
*>, 8> WorkList
;
492 WorkList
.push_back(std::make_pair(LI
, VNI
));
494 std::tie(LI
, VNI
) = WorkList
.pop_back_val();
495 if (!UsedValues
.insert(VNI
).second
)
498 if (VNI
->isPHIDef()) {
499 MachineBasicBlock
*MBB
= LIS
.getMBBFromIndex(VNI
->def
);
500 for (MachineBasicBlock
*P
: MBB
->predecessors()) {
501 VNInfo
*PVNI
= LI
->getVNInfoBefore(LIS
.getMBBEndIdx(P
));
503 WorkList
.push_back(std::make_pair(LI
, PVNI
));
508 // Follow snippet copies.
509 MachineInstr
*MI
= LIS
.getInstructionFromIndex(VNI
->def
);
510 if (!SnippetCopies
.count(MI
))
512 LiveInterval
&SnipLI
= LIS
.getInterval(MI
->getOperand(1).getReg());
513 assert(isRegToSpill(SnipLI
.reg
) && "Unexpected register in copy");
514 VNInfo
*SnipVNI
= SnipLI
.getVNInfoAt(VNI
->def
.getRegSlot(true));
515 assert(SnipVNI
&& "Snippet undefined before copy");
516 WorkList
.push_back(std::make_pair(&SnipLI
, SnipVNI
));
517 } while (!WorkList
.empty());
520 bool InlineSpiller::canGuaranteeAssignmentAfterRemat(unsigned VReg
,
522 if (!RestrictStatepointRemat
)
524 // Here's a quick explanation of the problem we're trying to handle here:
525 // * There are some pseudo instructions with more vreg uses than there are
526 // physical registers on the machine.
527 // * This is normally handled by spilling the vreg, and folding the reload
528 // into the user instruction. (Thus decreasing the number of used vregs
529 // until the remainder can be assigned to physregs.)
530 // * However, since we may try to spill vregs in any order, we can end up
531 // trying to spill each operand to the instruction, and then rematting it
532 // instead. When that happens, the new live intervals (for the remats) are
533 // expected to be trivially assignable (i.e. RS_Done). However, since we
534 // may have more remats than physregs, we're guaranteed to fail to assign
536 // At the moment, we only handle this for STATEPOINTs since they're the only
537 // psuedo op where we've seen this. If we start seeing other instructions
538 // with the same problem, we need to revisit this.
539 return (MI
.getOpcode() != TargetOpcode::STATEPOINT
);
542 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
543 bool InlineSpiller::reMaterializeFor(LiveInterval
&VirtReg
, MachineInstr
&MI
) {
544 // Analyze instruction
545 SmallVector
<std::pair
<MachineInstr
*, unsigned>, 8> Ops
;
546 MIBundleOperands::VirtRegInfo RI
=
547 MIBundleOperands(MI
).analyzeVirtReg(VirtReg
.reg
, &Ops
);
552 SlotIndex UseIdx
= LIS
.getInstructionIndex(MI
).getRegSlot(true);
553 VNInfo
*ParentVNI
= VirtReg
.getVNInfoAt(UseIdx
.getBaseIndex());
556 LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ");
557 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
558 MachineOperand
&MO
= MI
.getOperand(i
);
559 if (MO
.isReg() && MO
.isUse() && MO
.getReg() == VirtReg
.reg
)
562 LLVM_DEBUG(dbgs() << UseIdx
<< '\t' << MI
);
566 if (SnippetCopies
.count(&MI
))
569 LiveInterval
&OrigLI
= LIS
.getInterval(Original
);
570 VNInfo
*OrigVNI
= OrigLI
.getVNInfoAt(UseIdx
);
571 LiveRangeEdit::Remat
RM(ParentVNI
);
572 RM
.OrigMI
= LIS
.getInstructionFromIndex(OrigVNI
->def
);
574 if (!Edit
->canRematerializeAt(RM
, OrigVNI
, UseIdx
, false)) {
575 markValueUsed(&VirtReg
, ParentVNI
);
576 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx
<< '\t' << MI
);
580 // If the instruction also writes VirtReg.reg, it had better not require the
581 // same register for uses and defs.
583 markValueUsed(&VirtReg
, ParentVNI
);
584 LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx
<< '\t' << MI
);
588 // Before rematerializing into a register for a single instruction, try to
589 // fold a load into the instruction. That avoids allocating a new register.
590 if (RM
.OrigMI
->canFoldAsLoad() &&
591 foldMemoryOperand(Ops
, RM
.OrigMI
)) {
592 Edit
->markRematerialized(RM
.ParentVNI
);
597 // If we can't guarantee that we'll be able to actually assign the new vreg,
599 if (!canGuaranteeAssignmentAfterRemat(VirtReg
.reg
, MI
)) {
600 markValueUsed(&VirtReg
, ParentVNI
);
601 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx
<< '\t' << MI
);
605 // Allocate a new register for the remat.
606 unsigned NewVReg
= Edit
->createFrom(Original
);
608 // Finally we can rematerialize OrigMI before MI.
610 Edit
->rematerializeAt(*MI
.getParent(), MI
, NewVReg
, RM
, TRI
);
612 // We take the DebugLoc from MI, since OrigMI may be attributed to a
613 // different source location.
614 auto *NewMI
= LIS
.getInstructionFromIndex(DefIdx
);
615 NewMI
->setDebugLoc(MI
.getDebugLoc());
618 LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx
<< '\t'
619 << *LIS
.getInstructionFromIndex(DefIdx
));
622 for (const auto &OpPair
: Ops
) {
623 MachineOperand
&MO
= OpPair
.first
->getOperand(OpPair
.second
);
624 if (MO
.isReg() && MO
.isUse() && MO
.getReg() == VirtReg
.reg
) {
629 LLVM_DEBUG(dbgs() << "\t " << UseIdx
<< '\t' << MI
<< '\n');
635 /// reMaterializeAll - Try to rematerialize as many uses as possible,
636 /// and trim the live ranges after.
637 void InlineSpiller::reMaterializeAll() {
638 if (!Edit
->anyRematerializable(AA
))
643 // Try to remat before all uses of snippets.
644 bool anyRemat
= false;
645 for (unsigned Reg
: RegsToSpill
) {
646 LiveInterval
&LI
= LIS
.getInterval(Reg
);
647 for (MachineRegisterInfo::reg_bundle_iterator
648 RegI
= MRI
.reg_bundle_begin(Reg
), E
= MRI
.reg_bundle_end();
650 MachineInstr
&MI
= *RegI
++;
652 // Debug values are not allowed to affect codegen.
653 if (MI
.isDebugValue())
656 assert(!MI
.isDebugInstr() && "Did not expect to find a use in debug "
657 "instruction that isn't a DBG_VALUE");
659 anyRemat
|= reMaterializeFor(LI
, MI
);
665 // Remove any values that were completely rematted.
666 for (unsigned Reg
: RegsToSpill
) {
667 LiveInterval
&LI
= LIS
.getInterval(Reg
);
668 for (LiveInterval::vni_iterator I
= LI
.vni_begin(), E
= LI
.vni_end();
671 if (VNI
->isUnused() || VNI
->isPHIDef() || UsedValues
.count(VNI
))
673 MachineInstr
*MI
= LIS
.getInstructionFromIndex(VNI
->def
);
674 MI
->addRegisterDead(Reg
, &TRI
);
675 if (!MI
->allDefsAreDead())
677 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI
);
678 DeadDefs
.push_back(MI
);
682 // Eliminate dead code after remat. Note that some snippet copies may be
684 if (DeadDefs
.empty())
686 LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs
.size() << " dead defs.\n");
687 Edit
->eliminateDeadDefs(DeadDefs
, RegsToSpill
, AA
);
689 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
690 // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
691 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
692 // removed, PHI VNI are still left in the LiveInterval.
693 // So to get rid of unused reg, we need to check whether it has non-dbg
694 // reference instead of whether it has non-empty interval.
695 unsigned ResultPos
= 0;
696 for (unsigned Reg
: RegsToSpill
) {
697 if (MRI
.reg_nodbg_empty(Reg
)) {
698 Edit
->eraseVirtReg(Reg
);
702 assert(LIS
.hasInterval(Reg
) &&
703 (!LIS
.getInterval(Reg
).empty() || !MRI
.reg_nodbg_empty(Reg
)) &&
704 "Empty and not used live-range?!");
706 RegsToSpill
[ResultPos
++] = Reg
;
708 RegsToSpill
.erase(RegsToSpill
.begin() + ResultPos
, RegsToSpill
.end());
709 LLVM_DEBUG(dbgs() << RegsToSpill
.size()
710 << " registers to spill after remat.\n");
713 //===----------------------------------------------------------------------===//
715 //===----------------------------------------------------------------------===//
717 /// If MI is a load or store of StackSlot, it can be removed.
718 bool InlineSpiller::coalesceStackAccess(MachineInstr
*MI
, unsigned Reg
) {
720 unsigned InstrReg
= TII
.isLoadFromStackSlot(*MI
, FI
);
721 bool IsLoad
= InstrReg
;
723 InstrReg
= TII
.isStoreToStackSlot(*MI
, FI
);
725 // We have a stack access. Is it the right register and slot?
726 if (InstrReg
!= Reg
|| FI
!= StackSlot
)
730 HSpiller
.rmFromMergeableSpills(*MI
, StackSlot
);
732 LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI
);
733 LIS
.RemoveMachineInstrFromMaps(*MI
);
734 MI
->eraseFromParent();
747 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
749 // Dump the range of instructions from B to E with their slot indexes.
750 static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B
,
751 MachineBasicBlock::iterator E
,
752 LiveIntervals
const &LIS
,
753 const char *const header
,
755 char NextLine
= '\n';
756 char SlotIndent
= '\t';
758 if (std::next(B
) == E
) {
763 dbgs() << '\t' << header
<< ": " << NextLine
;
765 for (MachineBasicBlock::iterator I
= B
; I
!= E
; ++I
) {
766 SlotIndex Idx
= LIS
.getInstructionIndex(*I
).getRegSlot();
768 // If a register was passed in and this instruction has it as a
769 // destination that is marked as an early clobber, print the
770 // early-clobber slot index.
772 MachineOperand
*MO
= I
->findRegisterDefOperand(VReg
);
773 if (MO
&& MO
->isEarlyClobber())
774 Idx
= Idx
.getRegSlot(true);
777 dbgs() << SlotIndent
<< Idx
<< '\t' << *I
;
782 /// foldMemoryOperand - Try folding stack slot references in Ops into their
785 /// @param Ops Operand indices from analyzeVirtReg().
786 /// @param LoadMI Load instruction to use instead of stack slot when non-null.
787 /// @return True on success.
789 foldMemoryOperand(ArrayRef
<std::pair
<MachineInstr
*, unsigned>> Ops
,
790 MachineInstr
*LoadMI
) {
793 // Don't attempt folding in bundles.
794 MachineInstr
*MI
= Ops
.front().first
;
795 if (Ops
.back().first
!= MI
|| MI
->isBundled())
798 bool WasCopy
= MI
->isCopy();
801 // Spill subregs if the target allows it.
802 // We always want to spill subregs for stackmap/patchpoint pseudos.
803 bool SpillSubRegs
= TII
.isSubregFoldable() ||
804 MI
->getOpcode() == TargetOpcode::STATEPOINT
||
805 MI
->getOpcode() == TargetOpcode::PATCHPOINT
||
806 MI
->getOpcode() == TargetOpcode::STACKMAP
;
808 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
810 SmallVector
<unsigned, 8> FoldOps
;
811 for (const auto &OpPair
: Ops
) {
812 unsigned Idx
= OpPair
.second
;
813 assert(MI
== OpPair
.first
&& "Instruction conflict during operand folding");
814 MachineOperand
&MO
= MI
->getOperand(Idx
);
815 if (MO
.isImplicit()) {
816 ImpReg
= MO
.getReg();
820 if (!SpillSubRegs
&& MO
.getSubReg())
822 // We cannot fold a load instruction into a def.
823 if (LoadMI
&& MO
.isDef())
825 // Tied use operands should not be passed to foldMemoryOperand.
826 if (!MI
->isRegTiedToDefOperand(Idx
))
827 FoldOps
.push_back(Idx
);
830 // If we only have implicit uses, we won't be able to fold that.
831 // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
835 MachineInstrSpan
MIS(MI
, MI
->getParent());
837 MachineInstr
*FoldMI
=
838 LoadMI
? TII
.foldMemoryOperand(*MI
, FoldOps
, *LoadMI
, &LIS
)
839 : TII
.foldMemoryOperand(*MI
, FoldOps
, StackSlot
, &LIS
, &VRM
);
843 // Remove LIS for any dead defs in the original MI not in FoldMI.
844 for (MIBundleOperands
MO(*MI
); MO
.isValid(); ++MO
) {
847 Register Reg
= MO
->getReg();
848 if (!Reg
|| Register::isVirtualRegister(Reg
) || MRI
.isReserved(Reg
)) {
851 // Skip non-Defs, including undef uses and internal reads.
854 MIBundleOperands::PhysRegInfo RI
=
855 MIBundleOperands(*FoldMI
).analyzePhysReg(Reg
, &TRI
);
858 // FoldMI does not define this physreg. Remove the LI segment.
859 assert(MO
->isDead() && "Cannot fold physreg def");
860 SlotIndex Idx
= LIS
.getInstructionIndex(*MI
).getRegSlot();
861 LIS
.removePhysRegDefAt(Reg
, Idx
);
865 if (TII
.isStoreToStackSlot(*MI
, FI
) &&
866 HSpiller
.rmFromMergeableSpills(*MI
, FI
))
868 LIS
.ReplaceMachineInstrInMaps(*MI
, *FoldMI
);
870 MI
->getMF()->moveCallSiteInfo(MI
, FoldMI
);
871 MI
->eraseFromParent();
873 // Insert any new instructions other than FoldMI into the LIS maps.
874 assert(!MIS
.empty() && "Unexpected empty span of instructions!");
875 for (MachineInstr
&MI
: MIS
)
877 LIS
.InsertMachineInstrInMaps(MI
);
879 // TII.foldMemoryOperand may have left some implicit operands on the
880 // instruction. Strip them.
882 for (unsigned i
= FoldMI
->getNumOperands(); i
; --i
) {
883 MachineOperand
&MO
= FoldMI
->getOperand(i
- 1);
884 if (!MO
.isReg() || !MO
.isImplicit())
886 if (MO
.getReg() == ImpReg
)
887 FoldMI
->RemoveOperand(i
- 1);
890 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS
.begin(), MIS
.end(), LIS
,
895 else if (Ops
.front().second
== 0) {
897 HSpiller
.addToMergeableSpills(*FoldMI
, StackSlot
, Original
);
903 void InlineSpiller::insertReload(unsigned NewVReg
,
905 MachineBasicBlock::iterator MI
) {
906 MachineBasicBlock
&MBB
= *MI
->getParent();
908 MachineInstrSpan
MIS(MI
, &MBB
);
909 TII
.loadRegFromStackSlot(MBB
, MI
, NewVReg
, StackSlot
,
910 MRI
.getRegClass(NewVReg
), &TRI
);
912 LIS
.InsertMachineInstrRangeInMaps(MIS
.begin(), MI
);
914 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS
.begin(), MI
, LIS
, "reload",
919 /// Check if \p Def fully defines a VReg with an undefined value.
920 /// If that's the case, that means the value of VReg is actually
922 static bool isFullUndefDef(const MachineInstr
&Def
) {
923 if (!Def
.isImplicitDef())
925 assert(Def
.getNumOperands() == 1 &&
926 "Implicit def with more than one definition");
927 // We can say that the VReg defined by Def is undef, only if it is
928 // fully defined by Def. Otherwise, some of the lanes may not be
929 // undef and the value of the VReg matters.
930 return !Def
.getOperand(0).getSubReg();
933 /// insertSpill - Insert a spill of NewVReg after MI.
934 void InlineSpiller::insertSpill(unsigned NewVReg
, bool isKill
,
935 MachineBasicBlock::iterator MI
) {
936 MachineBasicBlock
&MBB
= *MI
->getParent();
938 MachineInstrSpan
MIS(MI
, &MBB
);
939 bool IsRealSpill
= true;
940 if (isFullUndefDef(*MI
)) {
941 // Don't spill undef value.
942 // Anything works for undef, in particular keeping the memory
943 // uninitialized is a viable option and it saves code size and
945 BuildMI(MBB
, std::next(MI
), MI
->getDebugLoc(), TII
.get(TargetOpcode::KILL
))
946 .addReg(NewVReg
, getKillRegState(isKill
));
949 TII
.storeRegToStackSlot(MBB
, std::next(MI
), NewVReg
, isKill
, StackSlot
,
950 MRI
.getRegClass(NewVReg
), &TRI
);
952 LIS
.InsertMachineInstrRangeInMaps(std::next(MI
), MIS
.end());
954 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI
), MIS
.end(), LIS
,
958 HSpiller
.addToMergeableSpills(*std::next(MI
), StackSlot
, Original
);
961 /// spillAroundUses - insert spill code around each use of Reg.
962 void InlineSpiller::spillAroundUses(unsigned Reg
) {
963 LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg
) << '\n');
964 LiveInterval
&OldLI
= LIS
.getInterval(Reg
);
966 // Iterate over instructions using Reg.
967 for (MachineRegisterInfo::reg_bundle_iterator
968 RegI
= MRI
.reg_bundle_begin(Reg
), E
= MRI
.reg_bundle_end();
970 MachineInstr
*MI
= &*(RegI
++);
972 // Debug values are not allowed to affect codegen.
973 if (MI
->isDebugValue()) {
974 // Modify DBG_VALUE now that the value is in a spill slot.
975 MachineBasicBlock
*MBB
= MI
->getParent();
976 LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI
);
977 buildDbgValueForSpill(*MBB
, MI
, *MI
, StackSlot
);
982 assert(!MI
->isDebugInstr() && "Did not expect to find a use in debug "
983 "instruction that isn't a DBG_VALUE");
985 // Ignore copies to/from snippets. We'll delete them.
986 if (SnippetCopies
.count(MI
))
989 // Stack slot accesses may coalesce away.
990 if (coalesceStackAccess(MI
, Reg
))
993 // Analyze instruction.
994 SmallVector
<std::pair
<MachineInstr
*, unsigned>, 8> Ops
;
995 MIBundleOperands::VirtRegInfo RI
=
996 MIBundleOperands(*MI
).analyzeVirtReg(Reg
, &Ops
);
998 // Find the slot index where this instruction reads and writes OldLI.
999 // This is usually the def slot, except for tied early clobbers.
1000 SlotIndex Idx
= LIS
.getInstructionIndex(*MI
).getRegSlot();
1001 if (VNInfo
*VNI
= OldLI
.getVNInfoAt(Idx
.getRegSlot(true)))
1002 if (SlotIndex::isSameInstr(Idx
, VNI
->def
))
1005 // Check for a sibling copy.
1006 unsigned SibReg
= isFullCopyOf(*MI
, Reg
);
1007 if (SibReg
&& isSibling(SibReg
)) {
1008 // This may actually be a copy between snippets.
1009 if (isRegToSpill(SibReg
)) {
1010 LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI
);
1011 SnippetCopies
.insert(MI
);
1015 if (hoistSpillInsideBB(OldLI
, *MI
)) {
1016 // This COPY is now dead, the value is already in the stack slot.
1017 MI
->getOperand(0).setIsDead();
1018 DeadDefs
.push_back(MI
);
1022 // This is a reload for a sib-reg copy. Drop spills downstream.
1023 LiveInterval
&SibLI
= LIS
.getInterval(SibReg
);
1024 eliminateRedundantSpills(SibLI
, SibLI
.getVNInfoAt(Idx
));
1025 // The COPY will fold to a reload below.
1029 // Attempt to fold memory ops.
1030 if (foldMemoryOperand(Ops
))
1033 // Create a new virtual register for spill/fill.
1034 // FIXME: Infer regclass from instruction alone.
1035 unsigned NewVReg
= Edit
->createFrom(Reg
);
1038 insertReload(NewVReg
, Idx
, MI
);
1040 // Rewrite instruction operands.
1041 bool hasLiveDef
= false;
1042 for (const auto &OpPair
: Ops
) {
1043 MachineOperand
&MO
= OpPair
.first
->getOperand(OpPair
.second
);
1046 if (!OpPair
.first
->isRegTiedToDefOperand(OpPair
.second
))
1053 LLVM_DEBUG(dbgs() << "\trewrite: " << Idx
<< '\t' << *MI
<< '\n');
1055 // FIXME: Use a second vreg if instruction has no tied ops.
1058 insertSpill(NewVReg
, true, MI
);
1062 /// spillAll - Spill all registers remaining after rematerialization.
1063 void InlineSpiller::spillAll() {
1064 // Update LiveStacks now that we are committed to spilling.
1065 if (StackSlot
== VirtRegMap::NO_STACK_SLOT
) {
1066 StackSlot
= VRM
.assignVirt2StackSlot(Original
);
1067 StackInt
= &LSS
.getOrCreateInterval(StackSlot
, MRI
.getRegClass(Original
));
1068 StackInt
->getNextValue(SlotIndex(), LSS
.getVNInfoAllocator());
1070 StackInt
= &LSS
.getInterval(StackSlot
);
1072 if (Original
!= Edit
->getReg())
1073 VRM
.assignVirt2StackSlot(Edit
->getReg(), StackSlot
);
1075 assert(StackInt
->getNumValNums() == 1 && "Bad stack interval values");
1076 for (unsigned Reg
: RegsToSpill
)
1077 StackInt
->MergeSegmentsInAsValue(LIS
.getInterval(Reg
),
1078 StackInt
->getValNumInfo(0));
1079 LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt
<< '\n');
1081 // Spill around uses of all RegsToSpill.
1082 for (unsigned Reg
: RegsToSpill
)
1083 spillAroundUses(Reg
);
1085 // Hoisted spills may cause dead code.
1086 if (!DeadDefs
.empty()) {
1087 LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs
.size() << " dead defs\n");
1088 Edit
->eliminateDeadDefs(DeadDefs
, RegsToSpill
, AA
);
1091 // Finally delete the SnippetCopies.
1092 for (unsigned Reg
: RegsToSpill
) {
1093 for (MachineRegisterInfo::reg_instr_iterator
1094 RI
= MRI
.reg_instr_begin(Reg
), E
= MRI
.reg_instr_end();
1096 MachineInstr
&MI
= *(RI
++);
1097 assert(SnippetCopies
.count(&MI
) && "Remaining use wasn't a snippet copy");
1098 // FIXME: Do this with a LiveRangeEdit callback.
1099 LIS
.RemoveMachineInstrFromMaps(MI
);
1100 MI
.eraseFromParent();
1104 // Delete all spilled registers.
1105 for (unsigned Reg
: RegsToSpill
)
1106 Edit
->eraseVirtReg(Reg
);
1109 void InlineSpiller::spill(LiveRangeEdit
&edit
) {
1112 assert(!Register::isStackSlot(edit
.getReg()) &&
1113 "Trying to spill a stack slot.");
1114 // Share a stack slot among all descendants of Original.
1115 Original
= VRM
.getOriginal(edit
.getReg());
1116 StackSlot
= VRM
.getStackSlot(Original
);
1119 LLVM_DEBUG(dbgs() << "Inline spilling "
1120 << TRI
.getRegClassName(MRI
.getRegClass(edit
.getReg()))
1121 << ':' << edit
.getParent() << "\nFrom original "
1122 << printReg(Original
) << '\n');
1123 assert(edit
.getParent().isSpillable() &&
1124 "Attempting to spill already spilled value.");
1125 assert(DeadDefs
.empty() && "Previous spill didn't remove dead defs");
1127 collectRegsToSpill();
1130 // Remat may handle everything.
1131 if (!RegsToSpill
.empty())
1134 Edit
->calculateRegClassAndHint(MF
, Loops
, MBFI
);
1137 /// Optimizations after all the reg selections and spills are done.
1138 void InlineSpiller::postOptimization() { HSpiller
.hoistAllSpills(); }
1140 /// When a spill is inserted, add the spill to MergeableSpills map.
1141 void HoistSpillHelper::addToMergeableSpills(MachineInstr
&Spill
, int StackSlot
,
1142 unsigned Original
) {
1143 BumpPtrAllocator
&Allocator
= LIS
.getVNInfoAllocator();
1144 LiveInterval
&OrigLI
= LIS
.getInterval(Original
);
1145 // save a copy of LiveInterval in StackSlotToOrigLI because the original
1146 // LiveInterval may be cleared after all its references are spilled.
1147 if (StackSlotToOrigLI
.find(StackSlot
) == StackSlotToOrigLI
.end()) {
1148 auto LI
= std::make_unique
<LiveInterval
>(OrigLI
.reg
, OrigLI
.weight
);
1149 LI
->assign(OrigLI
, Allocator
);
1150 StackSlotToOrigLI
[StackSlot
] = std::move(LI
);
1152 SlotIndex Idx
= LIS
.getInstructionIndex(Spill
);
1153 VNInfo
*OrigVNI
= StackSlotToOrigLI
[StackSlot
]->getVNInfoAt(Idx
.getRegSlot());
1154 std::pair
<int, VNInfo
*> MIdx
= std::make_pair(StackSlot
, OrigVNI
);
1155 MergeableSpills
[MIdx
].insert(&Spill
);
1158 /// When a spill is removed, remove the spill from MergeableSpills map.
1159 /// Return true if the spill is removed successfully.
1160 bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr
&Spill
,
1162 auto It
= StackSlotToOrigLI
.find(StackSlot
);
1163 if (It
== StackSlotToOrigLI
.end())
1165 SlotIndex Idx
= LIS
.getInstructionIndex(Spill
);
1166 VNInfo
*OrigVNI
= It
->second
->getVNInfoAt(Idx
.getRegSlot());
1167 std::pair
<int, VNInfo
*> MIdx
= std::make_pair(StackSlot
, OrigVNI
);
1168 return MergeableSpills
[MIdx
].erase(&Spill
);
1171 /// Check BB to see if it is a possible target BB to place a hoisted spill,
1172 /// i.e., there should be a living sibling of OrigReg at the insert point.
1173 bool HoistSpillHelper::isSpillCandBB(LiveInterval
&OrigLI
, VNInfo
&OrigVNI
,
1174 MachineBasicBlock
&BB
, unsigned &LiveReg
) {
1176 unsigned OrigReg
= OrigLI
.reg
;
1177 MachineBasicBlock::iterator MI
= IPA
.getLastInsertPointIter(OrigLI
, BB
);
1179 Idx
= LIS
.getInstructionIndex(*MI
);
1181 Idx
= LIS
.getMBBEndIdx(&BB
).getPrevSlot();
1182 SmallSetVector
<unsigned, 16> &Siblings
= Virt2SiblingsMap
[OrigReg
];
1183 assert(OrigLI
.getVNInfoAt(Idx
) == &OrigVNI
&& "Unexpected VNI");
1185 for (auto const SibReg
: Siblings
) {
1186 LiveInterval
&LI
= LIS
.getInterval(SibReg
);
1187 VNInfo
*VNI
= LI
.getVNInfoAt(Idx
);
1196 /// Remove redundant spills in the same BB. Save those redundant spills in
1197 /// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1198 void HoistSpillHelper::rmRedundantSpills(
1199 SmallPtrSet
<MachineInstr
*, 16> &Spills
,
1200 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
1201 DenseMap
<MachineDomTreeNode
*, MachineInstr
*> &SpillBBToSpill
) {
1202 // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1203 // another spill inside. If a BB contains more than one spill, only keep the
1204 // earlier spill with smaller SlotIndex.
1205 for (const auto CurrentSpill
: Spills
) {
1206 MachineBasicBlock
*Block
= CurrentSpill
->getParent();
1207 MachineDomTreeNode
*Node
= MDT
.getBase().getNode(Block
);
1208 MachineInstr
*PrevSpill
= SpillBBToSpill
[Node
];
1210 SlotIndex PIdx
= LIS
.getInstructionIndex(*PrevSpill
);
1211 SlotIndex CIdx
= LIS
.getInstructionIndex(*CurrentSpill
);
1212 MachineInstr
*SpillToRm
= (CIdx
> PIdx
) ? CurrentSpill
: PrevSpill
;
1213 MachineInstr
*SpillToKeep
= (CIdx
> PIdx
) ? PrevSpill
: CurrentSpill
;
1214 SpillsToRm
.push_back(SpillToRm
);
1215 SpillBBToSpill
[MDT
.getBase().getNode(Block
)] = SpillToKeep
;
1217 SpillBBToSpill
[MDT
.getBase().getNode(Block
)] = CurrentSpill
;
1220 for (const auto SpillToRm
: SpillsToRm
)
1221 Spills
.erase(SpillToRm
);
1224 /// Starting from \p Root find a top-down traversal order of the dominator
1225 /// tree to visit all basic blocks containing the elements of \p Spills.
1226 /// Redundant spills will be found and put into \p SpillsToRm at the same
1227 /// time. \p SpillBBToSpill will be populated as part of the process and
1228 /// maps a basic block to the first store occurring in the basic block.
1229 /// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1230 void HoistSpillHelper::getVisitOrders(
1231 MachineBasicBlock
*Root
, SmallPtrSet
<MachineInstr
*, 16> &Spills
,
1232 SmallVectorImpl
<MachineDomTreeNode
*> &Orders
,
1233 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
1234 DenseMap
<MachineDomTreeNode
*, unsigned> &SpillsToKeep
,
1235 DenseMap
<MachineDomTreeNode
*, MachineInstr
*> &SpillBBToSpill
) {
1236 // The set contains all the possible BB nodes to which we may hoist
1238 SmallPtrSet
<MachineDomTreeNode
*, 8> WorkSet
;
1239 // Save the BB nodes on the path from the first BB node containing
1240 // non-redundant spill to the Root node.
1241 SmallPtrSet
<MachineDomTreeNode
*, 8> NodesOnPath
;
1242 // All the spills to be hoisted must originate from a single def instruction
1243 // to the OrigReg. It means the def instruction should dominate all the spills
1244 // to be hoisted. We choose the BB where the def instruction is located as
1246 MachineDomTreeNode
*RootIDomNode
= MDT
[Root
]->getIDom();
1247 // For every node on the dominator tree with spill, walk up on the dominator
1248 // tree towards the Root node until it is reached. If there is other node
1249 // containing spill in the middle of the path, the previous spill saw will
1250 // be redundant and the node containing it will be removed. All the nodes on
1251 // the path starting from the first node with non-redundant spill to the Root
1252 // node will be added to the WorkSet, which will contain all the possible
1253 // locations where spills may be hoisted to after the loop below is done.
1254 for (const auto Spill
: Spills
) {
1255 MachineBasicBlock
*Block
= Spill
->getParent();
1256 MachineDomTreeNode
*Node
= MDT
[Block
];
1257 MachineInstr
*SpillToRm
= nullptr;
1258 while (Node
!= RootIDomNode
) {
1259 // If Node dominates Block, and it already contains a spill, the spill in
1260 // Block will be redundant.
1261 if (Node
!= MDT
[Block
] && SpillBBToSpill
[Node
]) {
1262 SpillToRm
= SpillBBToSpill
[MDT
[Block
]];
1264 /// If we see the Node already in WorkSet, the path from the Node to
1265 /// the Root node must already be traversed by another spill.
1266 /// Then no need to repeat.
1267 } else if (WorkSet
.count(Node
)) {
1270 NodesOnPath
.insert(Node
);
1272 Node
= Node
->getIDom();
1275 SpillsToRm
.push_back(SpillToRm
);
1277 // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1278 // set the initial status before hoisting start. The value of BBs
1279 // containing original spills is set to 0, in order to descriminate
1280 // with BBs containing hoisted spills which will be inserted to
1281 // SpillsToKeep later during hoisting.
1282 SpillsToKeep
[MDT
[Block
]] = 0;
1283 WorkSet
.insert(NodesOnPath
.begin(), NodesOnPath
.end());
1285 NodesOnPath
.clear();
1288 // Sort the nodes in WorkSet in top-down order and save the nodes
1289 // in Orders. Orders will be used for hoisting in runHoistSpills.
1291 Orders
.push_back(MDT
.getBase().getNode(Root
));
1293 MachineDomTreeNode
*Node
= Orders
[idx
++];
1294 const std::vector
<MachineDomTreeNode
*> &Children
= Node
->getChildren();
1295 unsigned NumChildren
= Children
.size();
1296 for (unsigned i
= 0; i
!= NumChildren
; ++i
) {
1297 MachineDomTreeNode
*Child
= Children
[i
];
1298 if (WorkSet
.count(Child
))
1299 Orders
.push_back(Child
);
1301 } while (idx
!= Orders
.size());
1302 assert(Orders
.size() == WorkSet
.size() &&
1303 "Orders have different size with WorkSet");
1306 LLVM_DEBUG(dbgs() << "Orders size is " << Orders
.size() << "\n");
1307 SmallVector
<MachineDomTreeNode
*, 32>::reverse_iterator RIt
= Orders
.rbegin();
1308 for (; RIt
!= Orders
.rend(); RIt
++)
1309 LLVM_DEBUG(dbgs() << "BB" << (*RIt
)->getBlock()->getNumber() << ",");
1310 LLVM_DEBUG(dbgs() << "\n");
1314 /// Try to hoist spills according to BB hotness. The spills to removed will
1315 /// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1317 void HoistSpillHelper::runHoistSpills(
1318 LiveInterval
&OrigLI
, VNInfo
&OrigVNI
,
1319 SmallPtrSet
<MachineInstr
*, 16> &Spills
,
1320 SmallVectorImpl
<MachineInstr
*> &SpillsToRm
,
1321 DenseMap
<MachineBasicBlock
*, unsigned> &SpillsToIns
) {
1322 // Visit order of dominator tree nodes.
1323 SmallVector
<MachineDomTreeNode
*, 32> Orders
;
1324 // SpillsToKeep contains all the nodes where spills are to be inserted
1325 // during hoisting. If the spill to be inserted is an original spill
1326 // (not a hoisted one), the value of the map entry is 0. If the spill
1327 // is a hoisted spill, the value of the map entry is the VReg to be used
1328 // as the source of the spill.
1329 DenseMap
<MachineDomTreeNode
*, unsigned> SpillsToKeep
;
1330 // Map from BB to the first spill inside of it.
1331 DenseMap
<MachineDomTreeNode
*, MachineInstr
*> SpillBBToSpill
;
1333 rmRedundantSpills(Spills
, SpillsToRm
, SpillBBToSpill
);
1335 MachineBasicBlock
*Root
= LIS
.getMBBFromIndex(OrigVNI
.def
);
1336 getVisitOrders(Root
, Spills
, Orders
, SpillsToRm
, SpillsToKeep
,
1339 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1340 // nodes set and the cost of all the spills inside those nodes.
1341 // The nodes set are the locations where spills are to be inserted
1342 // in the subtree of current node.
1343 using NodesCostPair
=
1344 std::pair
<SmallPtrSet
<MachineDomTreeNode
*, 16>, BlockFrequency
>;
1345 DenseMap
<MachineDomTreeNode
*, NodesCostPair
> SpillsInSubTreeMap
;
1347 // Iterate Orders set in reverse order, which will be a bottom-up order
1348 // in the dominator tree. Once we visit a dom tree node, we know its
1349 // children have already been visited and the spill locations in the
1350 // subtrees of all the children have been determined.
1351 SmallVector
<MachineDomTreeNode
*, 32>::reverse_iterator RIt
= Orders
.rbegin();
1352 for (; RIt
!= Orders
.rend(); RIt
++) {
1353 MachineBasicBlock
*Block
= (*RIt
)->getBlock();
1355 // If Block contains an original spill, simply continue.
1356 if (SpillsToKeep
.find(*RIt
) != SpillsToKeep
.end() && !SpillsToKeep
[*RIt
]) {
1357 SpillsInSubTreeMap
[*RIt
].first
.insert(*RIt
);
1358 // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
1359 SpillsInSubTreeMap
[*RIt
].second
= MBFI
.getBlockFreq(Block
);
1363 // Collect spills in subtree of current node (*RIt) to
1364 // SpillsInSubTreeMap[*RIt].first.
1365 const std::vector
<MachineDomTreeNode
*> &Children
= (*RIt
)->getChildren();
1366 unsigned NumChildren
= Children
.size();
1367 for (unsigned i
= 0; i
!= NumChildren
; ++i
) {
1368 MachineDomTreeNode
*Child
= Children
[i
];
1369 if (SpillsInSubTreeMap
.find(Child
) == SpillsInSubTreeMap
.end())
1371 // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
1372 // should be placed before getting the begin and end iterators of
1373 // SpillsInSubTreeMap[Child].first, or else the iterators may be
1374 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1375 // and the map grows and then the original buckets in the map are moved.
1376 SmallPtrSet
<MachineDomTreeNode
*, 16> &SpillsInSubTree
=
1377 SpillsInSubTreeMap
[*RIt
].first
;
1378 BlockFrequency
&SubTreeCost
= SpillsInSubTreeMap
[*RIt
].second
;
1379 SubTreeCost
+= SpillsInSubTreeMap
[Child
].second
;
1380 auto BI
= SpillsInSubTreeMap
[Child
].first
.begin();
1381 auto EI
= SpillsInSubTreeMap
[Child
].first
.end();
1382 SpillsInSubTree
.insert(BI
, EI
);
1383 SpillsInSubTreeMap
.erase(Child
);
1386 SmallPtrSet
<MachineDomTreeNode
*, 16> &SpillsInSubTree
=
1387 SpillsInSubTreeMap
[*RIt
].first
;
1388 BlockFrequency
&SubTreeCost
= SpillsInSubTreeMap
[*RIt
].second
;
1389 // No spills in subtree, simply continue.
1390 if (SpillsInSubTree
.empty())
1393 // Check whether Block is a possible candidate to insert spill.
1394 unsigned LiveReg
= 0;
1395 if (!isSpillCandBB(OrigLI
, OrigVNI
, *Block
, LiveReg
))
1398 // If there are multiple spills that could be merged, bias a little
1399 // to hoist the spill.
1400 BranchProbability MarginProb
= (SpillsInSubTree
.size() > 1)
1401 ? BranchProbability(9, 10)
1402 : BranchProbability(1, 1);
1403 if (SubTreeCost
> MBFI
.getBlockFreq(Block
) * MarginProb
) {
1404 // Hoist: Move spills to current Block.
1405 for (const auto SpillBB
: SpillsInSubTree
) {
1406 // When SpillBB is a BB contains original spill, insert the spill
1408 if (SpillsToKeep
.find(SpillBB
) != SpillsToKeep
.end() &&
1409 !SpillsToKeep
[SpillBB
]) {
1410 MachineInstr
*SpillToRm
= SpillBBToSpill
[SpillBB
];
1411 SpillsToRm
.push_back(SpillToRm
);
1413 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1414 SpillsToKeep
.erase(SpillBB
);
1416 // Current Block is the BB containing the new hoisted spill. Add it to
1417 // SpillsToKeep. LiveReg is the source of the new spill.
1418 SpillsToKeep
[*RIt
] = LiveReg
;
1420 dbgs() << "spills in BB: ";
1421 for (const auto Rspill
: SpillsInSubTree
)
1422 dbgs() << Rspill
->getBlock()->getNumber() << " ";
1423 dbgs() << "were promoted to BB" << (*RIt
)->getBlock()->getNumber()
1426 SpillsInSubTree
.clear();
1427 SpillsInSubTree
.insert(*RIt
);
1428 SubTreeCost
= MBFI
.getBlockFreq(Block
);
1431 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1432 // save them to SpillsToIns.
1433 for (const auto Ent
: SpillsToKeep
) {
1435 SpillsToIns
[Ent
.first
->getBlock()] = Ent
.second
;
1439 /// For spills with equal values, remove redundant spills and hoist those left
1440 /// to less hot spots.
1442 /// Spills with equal values will be collected into the same set in
1443 /// MergeableSpills when spill is inserted. These equal spills are originated
1444 /// from the same defining instruction and are dominated by the instruction.
1445 /// Before hoisting all the equal spills, redundant spills inside in the same
1446 /// BB are first marked to be deleted. Then starting from the spills left, walk
1447 /// up on the dominator tree towards the Root node where the define instruction
1448 /// is located, mark the dominated spills to be deleted along the way and
1449 /// collect the BB nodes on the path from non-dominated spills to the define
1450 /// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1451 /// where we are considering to hoist the spills. We iterate the WorkSet in
1452 /// bottom-up order, and for each node, we will decide whether to hoist spills
1453 /// inside its subtree to that node. In this way, we can get benefit locally
1454 /// even if hoisting all the equal spills to one cold place is impossible.
1455 void HoistSpillHelper::hoistAllSpills() {
1456 SmallVector
<unsigned, 4> NewVRegs
;
1457 LiveRangeEdit
Edit(nullptr, NewVRegs
, MF
, LIS
, &VRM
, this);
1459 for (unsigned i
= 0, e
= MRI
.getNumVirtRegs(); i
!= e
; ++i
) {
1460 unsigned Reg
= Register::index2VirtReg(i
);
1461 unsigned Original
= VRM
.getPreSplitReg(Reg
);
1462 if (!MRI
.def_empty(Reg
))
1463 Virt2SiblingsMap
[Original
].insert(Reg
);
1466 // Each entry in MergeableSpills contains a spill set with equal values.
1467 for (auto &Ent
: MergeableSpills
) {
1468 int Slot
= Ent
.first
.first
;
1469 LiveInterval
&OrigLI
= *StackSlotToOrigLI
[Slot
];
1470 VNInfo
*OrigVNI
= Ent
.first
.second
;
1471 SmallPtrSet
<MachineInstr
*, 16> &EqValSpills
= Ent
.second
;
1472 if (Ent
.second
.empty())
1476 dbgs() << "\nFor Slot" << Slot
<< " and VN" << OrigVNI
->id
<< ":\n"
1477 << "Equal spills in BB: ";
1478 for (const auto spill
: EqValSpills
)
1479 dbgs() << spill
->getParent()->getNumber() << " ";
1483 // SpillsToRm is the spill set to be removed from EqValSpills.
1484 SmallVector
<MachineInstr
*, 16> SpillsToRm
;
1485 // SpillsToIns is the spill set to be newly inserted after hoisting.
1486 DenseMap
<MachineBasicBlock
*, unsigned> SpillsToIns
;
1488 runHoistSpills(OrigLI
, *OrigVNI
, EqValSpills
, SpillsToRm
, SpillsToIns
);
1491 dbgs() << "Finally inserted spills in BB: ";
1492 for (const auto Ispill
: SpillsToIns
)
1493 dbgs() << Ispill
.first
->getNumber() << " ";
1494 dbgs() << "\nFinally removed spills in BB: ";
1495 for (const auto Rspill
: SpillsToRm
)
1496 dbgs() << Rspill
->getParent()->getNumber() << " ";
1500 // Stack live range update.
1501 LiveInterval
&StackIntvl
= LSS
.getInterval(Slot
);
1502 if (!SpillsToIns
.empty() || !SpillsToRm
.empty())
1503 StackIntvl
.MergeValueInAsValue(OrigLI
, OrigVNI
,
1504 StackIntvl
.getValNumInfo(0));
1506 // Insert hoisted spills.
1507 for (auto const Insert
: SpillsToIns
) {
1508 MachineBasicBlock
*BB
= Insert
.first
;
1509 unsigned LiveReg
= Insert
.second
;
1510 MachineBasicBlock::iterator MI
= IPA
.getLastInsertPointIter(OrigLI
, *BB
);
1511 TII
.storeRegToStackSlot(*BB
, MI
, LiveReg
, false, Slot
,
1512 MRI
.getRegClass(LiveReg
), &TRI
);
1513 LIS
.InsertMachineInstrRangeInMaps(std::prev(MI
), MI
);
1517 // Remove redundant spills or change them to dead instructions.
1518 NumSpills
-= SpillsToRm
.size();
1519 for (auto const RMEnt
: SpillsToRm
) {
1520 RMEnt
->setDesc(TII
.get(TargetOpcode::KILL
));
1521 for (unsigned i
= RMEnt
->getNumOperands(); i
; --i
) {
1522 MachineOperand
&MO
= RMEnt
->getOperand(i
- 1);
1523 if (MO
.isReg() && MO
.isImplicit() && MO
.isDef() && !MO
.isDead())
1524 RMEnt
->RemoveOperand(i
- 1);
1527 Edit
.eliminateDeadDefs(SpillsToRm
, None
, AA
);
1531 /// For VirtReg clone, the \p New register should have the same physreg or
1532 /// stackslot as the \p old register.
1533 void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New
, unsigned Old
) {
1534 if (VRM
.hasPhys(Old
))
1535 VRM
.assignVirt2Phys(New
, VRM
.getPhys(Old
));
1536 else if (VRM
.getStackSlot(Old
) != VirtRegMap::NO_STACK_SLOT
)
1537 VRM
.assignVirt2StackSlot(New
, VRM
.getStackSlot(Old
));
1539 llvm_unreachable("VReg should be assigned either physreg or stackslot");