Line data Source code
1 : //===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // The inline spiller modifies the machine function directly instead of
11 : // inserting spills and restores in VirtRegMap.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "LiveRangeCalc.h"
16 : #include "Spiller.h"
17 : #include "SplitKit.h"
18 : #include "llvm/ADT/ArrayRef.h"
19 : #include "llvm/ADT/DenseMap.h"
20 : #include "llvm/ADT/MapVector.h"
21 : #include "llvm/ADT/None.h"
22 : #include "llvm/ADT/STLExtras.h"
23 : #include "llvm/ADT/SetVector.h"
24 : #include "llvm/ADT/SmallPtrSet.h"
25 : #include "llvm/ADT/SmallVector.h"
26 : #include "llvm/ADT/Statistic.h"
27 : #include "llvm/Analysis/AliasAnalysis.h"
28 : #include "llvm/CodeGen/LiveInterval.h"
29 : #include "llvm/CodeGen/LiveIntervals.h"
30 : #include "llvm/CodeGen/LiveRangeEdit.h"
31 : #include "llvm/CodeGen/LiveStacks.h"
32 : #include "llvm/CodeGen/MachineBasicBlock.h"
33 : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
34 : #include "llvm/CodeGen/MachineDominators.h"
35 : #include "llvm/CodeGen/MachineFunction.h"
36 : #include "llvm/CodeGen/MachineFunctionPass.h"
37 : #include "llvm/CodeGen/MachineInstr.h"
38 : #include "llvm/CodeGen/MachineInstrBuilder.h"
39 : #include "llvm/CodeGen/MachineInstrBundle.h"
40 : #include "llvm/CodeGen/MachineLoopInfo.h"
41 : #include "llvm/CodeGen/MachineOperand.h"
42 : #include "llvm/CodeGen/MachineRegisterInfo.h"
43 : #include "llvm/CodeGen/SlotIndexes.h"
44 : #include "llvm/CodeGen/TargetInstrInfo.h"
45 : #include "llvm/CodeGen/TargetOpcodes.h"
46 : #include "llvm/CodeGen/TargetRegisterInfo.h"
47 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
48 : #include "llvm/CodeGen/VirtRegMap.h"
49 : #include "llvm/Config/llvm-config.h"
50 : #include "llvm/Support/BlockFrequency.h"
51 : #include "llvm/Support/BranchProbability.h"
52 : #include "llvm/Support/CommandLine.h"
53 : #include "llvm/Support/Compiler.h"
54 : #include "llvm/Support/Debug.h"
55 : #include "llvm/Support/ErrorHandling.h"
56 : #include "llvm/Support/raw_ostream.h"
57 : #include <cassert>
58 : #include <iterator>
59 : #include <tuple>
60 : #include <utility>
61 : #include <vector>
62 :
63 : using namespace llvm;
64 :
65 : #define DEBUG_TYPE "regalloc"
66 :
67 : STATISTIC(NumSpilledRanges, "Number of spilled live ranges");
68 : STATISTIC(NumSnippets, "Number of spilled snippets");
69 : STATISTIC(NumSpills, "Number of spills inserted");
70 : STATISTIC(NumSpillsRemoved, "Number of spills removed");
71 : STATISTIC(NumReloads, "Number of reloads inserted");
72 : STATISTIC(NumReloadsRemoved, "Number of reloads removed");
73 : STATISTIC(NumFolded, "Number of folded stack accesses");
74 : STATISTIC(NumFoldedLoads, "Number of folded loads");
75 : STATISTIC(NumRemats, "Number of rematerialized defs for spilling");
76 :
77 : static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
78 : cl::desc("Disable inline spill hoisting"));
79 :
80 : namespace {
81 :
82 : class HoistSpillHelper : private LiveRangeEdit::Delegate {
83 : MachineFunction &MF;
84 : LiveIntervals &LIS;
85 : LiveStacks &LSS;
86 : AliasAnalysis *AA;
87 : MachineDominatorTree &MDT;
88 : MachineLoopInfo &Loops;
89 : VirtRegMap &VRM;
90 : MachineRegisterInfo &MRI;
91 : const TargetInstrInfo &TII;
92 : const TargetRegisterInfo &TRI;
93 : const MachineBlockFrequencyInfo &MBFI;
94 :
95 : InsertPointAnalysis IPA;
96 :
97 : // Map from StackSlot to the LiveInterval of the original register.
98 : // Note the LiveInterval of the original register may have been deleted
99 : // after it is spilled. We keep a copy here to track the range where
100 : // spills can be moved.
101 : DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI;
102 :
103 : // Map from pair of (StackSlot and Original VNI) to a set of spills which
104 : // have the same stackslot and have equal values defined by Original VNI.
105 : // These spills are mergeable and are hoist candiates.
106 : using MergeableSpillsMap =
107 : MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>;
108 : MergeableSpillsMap MergeableSpills;
109 :
110 : /// This is the map from original register to a set containing all its
111 : /// siblings. To hoist a spill to another BB, we need to find out a live
112 : /// sibling there and use it as the source of the new spill.
113 : DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap;
114 :
115 : bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
116 : MachineBasicBlock &BB, unsigned &LiveReg);
117 :
118 : void rmRedundantSpills(
119 : SmallPtrSet<MachineInstr *, 16> &Spills,
120 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
121 : DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
122 :
123 : void getVisitOrders(
124 : MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
125 : SmallVectorImpl<MachineDomTreeNode *> &Orders,
126 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
127 : DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
128 : DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
129 :
130 : void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
131 : SmallPtrSet<MachineInstr *, 16> &Spills,
132 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
133 : DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
134 :
135 : public:
136 193999 : HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
137 : VirtRegMap &vrm)
138 387998 : : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
139 193999 : LSS(pass.getAnalysis<LiveStacks>()),
140 193999 : AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
141 193999 : MDT(pass.getAnalysis<MachineDominatorTree>()),
142 193999 : Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
143 387998 : MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
144 193999 : TRI(*mf.getSubtarget().getRegisterInfo()),
145 193999 : MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
146 387998 : IPA(LIS, mf.getNumBlockIDs()) {}
147 :
148 : void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
149 : unsigned Original);
150 : bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
151 : void hoistAllSpills();
152 : void LRE_DidCloneVirtReg(unsigned, unsigned) override;
153 : };
154 :
155 : class InlineSpiller : public Spiller {
156 : MachineFunction &MF;
157 : LiveIntervals &LIS;
158 : LiveStacks &LSS;
159 : AliasAnalysis *AA;
160 : MachineDominatorTree &MDT;
161 : MachineLoopInfo &Loops;
162 : VirtRegMap &VRM;
163 : MachineRegisterInfo &MRI;
164 : const TargetInstrInfo &TII;
165 : const TargetRegisterInfo &TRI;
166 : const MachineBlockFrequencyInfo &MBFI;
167 :
168 : // Variables that are valid during spill(), but used by multiple methods.
169 : LiveRangeEdit *Edit;
170 : LiveInterval *StackInt;
171 : int StackSlot;
172 : unsigned Original;
173 :
174 : // All registers to spill to StackSlot, including the main register.
175 : SmallVector<unsigned, 8> RegsToSpill;
176 :
177 : // All COPY instructions to/from snippets.
178 : // They are ignored since both operands refer to the same stack slot.
179 : SmallPtrSet<MachineInstr*, 8> SnippetCopies;
180 :
181 : // Values that failed to remat at some point.
182 : SmallPtrSet<VNInfo*, 8> UsedValues;
183 :
184 : // Dead defs generated during spilling.
185 : SmallVector<MachineInstr*, 8> DeadDefs;
186 :
187 : // Object records spills information and does the hoisting.
188 : HoistSpillHelper HSpiller;
189 :
190 581986 : ~InlineSpiller() override = default;
191 :
192 : public:
193 193999 : InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
194 387998 : : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
195 193999 : LSS(pass.getAnalysis<LiveStacks>()),
196 193999 : AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
197 193999 : MDT(pass.getAnalysis<MachineDominatorTree>()),
198 193999 : Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
199 387998 : MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
200 193999 : TRI(*mf.getSubtarget().getRegisterInfo()),
201 193999 : MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
202 193999 : HSpiller(pass, mf, vrm) {}
203 :
204 : void spill(LiveRangeEdit &) override;
205 : void postOptimization() override;
206 :
207 : private:
208 : bool isSnippet(const LiveInterval &SnipLI);
209 : void collectRegsToSpill();
210 :
211 : bool isRegToSpill(unsigned Reg) { return is_contained(RegsToSpill, Reg); }
212 :
213 : bool isSibling(unsigned Reg);
214 : bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
215 : void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
216 :
217 : void markValueUsed(LiveInterval*, VNInfo*);
218 : bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
219 : void reMaterializeAll();
220 :
221 : bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
222 : bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
223 : MachineInstr *LoadMI = nullptr);
224 : void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI);
225 : void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI);
226 :
227 : void spillAroundUses(unsigned Reg);
228 : void spillAll();
229 : };
230 :
231 : } // end anonymous namespace
232 :
233 : Spiller::~Spiller() = default;
234 :
235 0 : void Spiller::anchor() {}
236 :
237 193999 : Spiller *llvm::createInlineSpiller(MachineFunctionPass &pass,
238 : MachineFunction &mf,
239 : VirtRegMap &vrm) {
240 193999 : return new InlineSpiller(pass, mf, vrm);
241 : }
242 :
243 : //===----------------------------------------------------------------------===//
244 : // Snippets
245 : //===----------------------------------------------------------------------===//
246 :
247 : // When spilling a virtual register, we also spill any snippets it is connected
248 : // to. The snippets are small live ranges that only have a single real use,
249 : // leftovers from live range splitting. Spilling them enables memory operand
250 : // folding or tightens the live range around the single use.
251 : //
252 : // This minimizes register pressure and maximizes the store-to-load distance for
253 : // spill slots which can be important in tight loops.
254 :
255 : /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
256 : /// otherwise return 0.
257 : static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg) {
258 : if (!MI.isFullCopy())
259 : return 0;
260 71962 : if (MI.getOperand(0).getReg() == Reg)
261 27006 : return MI.getOperand(1).getReg();
262 44956 : if (MI.getOperand(1).getReg() == Reg)
263 : return MI.getOperand(0).getReg();
264 : return 0;
265 : }
266 :
267 : /// isSnippet - Identify if a live interval is a snippet that should be spilled.
268 : /// It is assumed that SnipLI is a virtual register with the same original as
269 : /// Edit->getReg().
270 24326 : bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
271 24326 : unsigned Reg = Edit->getReg();
272 :
273 : // A snippet is a tiny live range with only a single instruction using it
274 : // besides copies to/from Reg or spills/fills. We accept:
275 : //
276 : // %snip = COPY %Reg / FILL fi#
277 : // %snip = USE %snip
278 : // %Reg = COPY %snip / SPILL %snip, fi#
279 : //
280 24326 : if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
281 12474 : return false;
282 :
283 : MachineInstr *UseMI = nullptr;
284 :
285 : // Check that all uses satisfy our criteria.
286 : for (MachineRegisterInfo::reg_instr_nodbg_iterator
287 11852 : RI = MRI.reg_instr_nodbg_begin(SnipLI.reg),
288 30297 : E = MRI.reg_instr_nodbg_end(); RI != E; ) {
289 : MachineInstr &MI = *RI++;
290 :
291 : // Allow copies to/from Reg.
292 5131 : if (isFullCopyOf(MI, Reg))
293 6055 : continue;
294 :
295 : // Allow stack slot loads.
296 : int FI;
297 24174 : if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
298 : continue;
299 :
300 : // Allow stack slot stores.
301 23638 : if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
302 : continue;
303 :
304 : // Allow a single additional instruction.
305 23250 : if (UseMI && &MI != UseMI)
306 10860 : return false;
307 : UseMI = &MI;
308 : }
309 : return true;
310 : }
311 :
312 : /// collectRegsToSpill - Collect live range snippets that only have a single
313 : /// real use.
314 30076 : void InlineSpiller::collectRegsToSpill() {
315 30076 : unsigned Reg = Edit->getReg();
316 :
317 : // Main register always spills.
318 30076 : RegsToSpill.assign(1, Reg);
319 30076 : SnippetCopies.clear();
320 :
321 : // Snippets all have the same original, so there can't be any for an original
322 : // register.
323 30076 : if (Original == Reg)
324 14260 : return;
325 :
326 : for (MachineRegisterInfo::reg_instr_iterator
327 80387 : RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
328 : MachineInstr &MI = *RI++;
329 76327 : unsigned SnipReg = isFullCopyOf(MI, Reg);
330 : if (!isSibling(SnipReg))
331 47767 : continue;
332 24326 : LiveInterval &SnipLI = LIS.getInterval(SnipReg);
333 24326 : if (!isSnippet(SnipLI))
334 : continue;
335 992 : SnippetCopies.insert(&MI);
336 1984 : if (isRegToSpill(SnipReg))
337 : continue;
338 988 : RegsToSpill.push_back(SnipReg);
339 : LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
340 : ++NumSnippets;
341 : }
342 : }
343 :
344 0 : bool InlineSpiller::isSibling(unsigned Reg) {
345 82811 : return TargetRegisterInfo::isVirtualRegister(Reg) &&
346 52146 : VRM.getOriginal(Reg) == Original;
347 : }
348 :
349 : /// It is beneficial to spill to earlier place in the same BB in case
350 : /// as follows:
351 : /// There is an alternative def earlier in the same MBB.
352 : /// Hoist the spill as far as possible in SpillMBB. This can ease
353 : /// register pressure:
354 : ///
355 : /// x = def
356 : /// y = use x
357 : /// s = copy x
358 : ///
359 : /// Hoisting the spill of s to immediately after the def removes the
360 : /// interference between x and y:
361 : ///
362 : /// x = def
363 : /// spill x
364 : /// y = use killed x
365 : ///
366 : /// This hoist only helps when the copy kills its source.
367 : ///
368 0 : bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
369 : MachineInstr &CopyMI) {
370 0 : SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
371 : #ifndef NDEBUG
372 : VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
373 : assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");
374 : #endif
375 :
376 0 : unsigned SrcReg = CopyMI.getOperand(1).getReg();
377 0 : LiveInterval &SrcLI = LIS.getInterval(SrcReg);
378 0 : VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
379 0 : LiveQueryResult SrcQ = SrcLI.Query(Idx);
380 0 : MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
381 0 : if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
382 0 : return false;
383 :
384 : // Conservatively extend the stack slot range to the range of the original
385 : // value. We may be able to do better with stack slot coloring by being more
386 : // careful here.
387 : assert(StackInt && "No stack slot assigned yet.");
388 0 : LiveInterval &OrigLI = LIS.getInterval(Original);
389 0 : VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
390 0 : StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
391 : LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
392 : << *StackInt << '\n');
393 :
394 : // We are going to spill SrcVNI immediately after its def, so clear out
395 : // any later spills of the same value.
396 0 : eliminateRedundantSpills(SrcLI, SrcVNI);
397 :
398 0 : MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
399 : MachineBasicBlock::iterator MII;
400 0 : if (SrcVNI->isPHIDef())
401 0 : MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
402 : else {
403 : MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
404 : assert(DefMI && "Defining instruction disappeared");
405 : MII = DefMI;
406 : ++MII;
407 : }
408 : // Insert spill without kill flag immediately after def.
409 0 : TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
410 0 : MRI.getRegClass(SrcReg), &TRI);
411 : --MII; // Point to store instruction.
412 0 : LIS.InsertMachineInstrInMaps(*MII);
413 : LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);
414 :
415 0 : HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
416 : ++NumSpills;
417 0 : return true;
418 : }
419 :
420 : /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
421 : /// redundant spills of this value in SLI.reg and sibling copies.
422 11204 : void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
423 : assert(VNI && "Missing value");
424 : SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
425 11204 : WorkList.push_back(std::make_pair(&SLI, VNI));
426 : assert(StackInt && "No stack slot assigned yet.");
427 :
428 : do {
429 : LiveInterval *LI;
430 : std::tie(LI, VNI) = WorkList.pop_back_val();
431 17821 : unsigned Reg = LI->reg;
432 : LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'
433 : << VNI->def << " in " << *LI << '\n');
434 :
435 : // Regs to spill are taken care of.
436 17821 : if (isRegToSpill(Reg))
437 4616 : continue;
438 :
439 : // Add all of VNI's live range to StackInt.
440 26410 : StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
441 : LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
442 :
443 : // Find all spills and copies of VNI.
444 : for (MachineRegisterInfo::use_instr_nodbg_iterator
445 13205 : UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
446 69736 : UI != E; ) {
447 : MachineInstr &MI = *UI++;
448 56531 : if (!MI.isCopy() && !MI.mayStore())
449 52118 : continue;
450 30191 : SlotIndex Idx = LIS.getInstructionIndex(MI);
451 30191 : if (LI->getVNInfoAt(Idx) != VNI)
452 : continue;
453 :
454 : // Follow sibling copies down the dominator tree.
455 10237 : if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
456 : if (isSibling(DstReg)) {
457 6617 : LiveInterval &DstLI = LIS.getInterval(DstReg);
458 6617 : VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
459 : assert(DstVNI && "Missing defined value");
460 : assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");
461 6617 : WorkList.push_back(std::make_pair(&DstLI, DstVNI));
462 : }
463 10237 : continue;
464 : }
465 :
466 : // Erase spills.
467 : int FI;
468 4413 : if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
469 : LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI);
470 : // eliminateDeadDefs won't normally remove stores, so switch opcode.
471 409 : MI.setDesc(TII.get(TargetOpcode::KILL));
472 409 : DeadDefs.push_back(&MI);
473 : ++NumSpillsRemoved;
474 409 : if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
475 : --NumSpills;
476 : }
477 : }
478 17821 : } while (!WorkList.empty());
479 11204 : }
480 :
481 : //===----------------------------------------------------------------------===//
482 : // Rematerialization
483 : //===----------------------------------------------------------------------===//
484 :
485 : /// markValueUsed - Remember that VNI failed to rematerialize, so its defining
486 : /// instruction cannot be eliminated. See through snippet copies
487 1365 : void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
488 : SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
489 1365 : WorkList.push_back(std::make_pair(LI, VNI));
490 : do {
491 : std::tie(LI, VNI) = WorkList.pop_back_val();
492 3896 : if (!UsedValues.insert(VNI).second)
493 : continue;
494 :
495 2938 : if (VNI->isPHIDef()) {
496 1048 : MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
497 3433 : for (MachineBasicBlock *P : MBB->predecessors()) {
498 4770 : VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
499 2385 : if (PVNI)
500 2385 : WorkList.push_back(std::make_pair(LI, PVNI));
501 : }
502 : continue;
503 : }
504 :
505 : // Follow snippet copies.
506 : MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
507 1890 : if (!SnippetCopies.count(MI))
508 : continue;
509 146 : LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
510 : assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
511 146 : VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
512 : assert(SnipVNI && "Snippet undefined before copy");
513 146 : WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
514 3896 : } while (!WorkList.empty());
515 1365 : }
516 :
517 : /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
518 46161 : bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
519 : // Analyze instruction
520 : SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
521 : MIBundleOperands::VirtRegInfo RI =
522 46161 : MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops);
523 :
524 46161 : if (!RI.Reads)
525 : return false;
526 :
527 29879 : SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
528 29879 : VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
529 :
530 29879 : if (!ParentVNI) {
531 : LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ");
532 0 : for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
533 0 : MachineOperand &MO = MI.getOperand(i);
534 0 : if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg)
535 : MO.setIsUndef();
536 : }
537 : LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI);
538 : return true;
539 : }
540 :
541 29879 : if (SnippetCopies.count(&MI))
542 : return false;
543 :
544 29473 : LiveInterval &OrigLI = LIS.getInterval(Original);
545 58946 : VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
546 : LiveRangeEdit::Remat RM(ParentVNI);
547 29473 : RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
548 :
549 29473 : if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
550 1141 : markValueUsed(&VirtReg, ParentVNI);
551 : LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
552 1141 : return false;
553 : }
554 :
555 : // If the instruction also writes VirtReg.reg, it had better not require the
556 : // same register for uses and defs.
557 28332 : if (RI.Tied) {
558 224 : markValueUsed(&VirtReg, ParentVNI);
559 : LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI);
560 224 : return false;
561 : }
562 :
563 : // Before rematerializing into a register for a single instruction, try to
564 : // fold a load into the instruction. That avoids allocating a new register.
565 34470 : if (RM.OrigMI->canFoldAsLoad() &&
566 12724 : foldMemoryOperand(Ops, RM.OrigMI)) {
567 2407 : Edit->markRematerialized(RM.ParentVNI);
568 : ++NumFoldedLoads;
569 2407 : return true;
570 : }
571 :
572 : // Allocate a new register for the remat.
573 25701 : unsigned NewVReg = Edit->createFrom(Original);
574 :
575 : // Finally we can rematerialize OrigMI before MI.
576 : SlotIndex DefIdx =
577 51402 : Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);
578 :
579 : // We take the DebugLoc from MI, since OrigMI may be attributed to a
580 : // different source location.
581 : auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
582 25701 : NewMI->setDebugLoc(MI.getDebugLoc());
583 :
584 : (void)DefIdx;
585 : LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
586 : << *LIS.getInstructionFromIndex(DefIdx));
587 :
588 : // Replace operands
589 51408 : for (const auto &OpPair : Ops) {
590 25707 : MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
591 25707 : if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) {
592 25707 : MO.setReg(NewVReg);
593 : MO.setIsKill();
594 : }
595 : }
596 : LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n');
597 :
598 : ++NumRemats;
599 : return true;
600 : }
601 :
602 : /// reMaterializeAll - Try to rematerialize as many uses as possible,
603 : /// and trim the live ranges after.
604 30076 : void InlineSpiller::reMaterializeAll() {
605 30076 : if (!Edit->anyRematerializable(AA))
606 : return;
607 :
608 14366 : UsedValues.clear();
609 :
610 : // Try to remat before all uses of snippets.
611 : bool anyRemat = false;
612 29137 : for (unsigned Reg : RegsToSpill) {
613 14771 : LiveInterval &LI = LIS.getInterval(Reg);
614 : for (MachineRegisterInfo::reg_bundle_iterator
615 29542 : RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
616 60932 : RegI != E; ) {
617 : MachineInstr &MI = *RegI++;
618 :
619 : // Debug values are not allowed to affect codegen.
620 46161 : if (MI.isDebugValue())
621 : continue;
622 :
623 : assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "
624 : "instruction that isn't a DBG_VALUE");
625 :
626 46161 : anyRemat |= reMaterializeFor(LI, MI);
627 : }
628 : }
629 14366 : if (!anyRemat)
630 : return;
631 :
632 : // Remove any values that were completely rematted.
633 27488 : for (unsigned Reg : RegsToSpill) {
634 13880 : LiveInterval &LI = LIS.getInterval(Reg);
635 15415 : for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
636 29295 : I != E; ++I) {
637 15415 : VNInfo *VNI = *I;
638 15415 : if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
639 848 : continue;
640 14567 : MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
641 14567 : MI->addRegisterDead(Reg, &TRI);
642 14567 : if (!MI->allDefsAreDead())
643 : continue;
644 : LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
645 14567 : DeadDefs.push_back(MI);
646 : }
647 : }
648 :
649 : // Eliminate dead code after remat. Note that some snippet copies may be
650 : // deleted here.
651 13608 : if (DeadDefs.empty())
652 : return;
653 : LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
654 27148 : Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
655 :
656 : // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
657 : // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
658 : // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
659 : // removed, PHI VNI are still left in the LiveInterval.
660 : // So to get rid of unused reg, we need to check whether it has non-dbg
661 : // reference instead of whether it has non-empty interval.
662 : unsigned ResultPos = 0;
663 27408 : for (unsigned Reg : RegsToSpill) {
664 13834 : if (MRI.reg_nodbg_empty(Reg)) {
665 13832 : Edit->eraseVirtReg(Reg);
666 13832 : continue;
667 : }
668 :
669 : assert(LIS.hasInterval(Reg) &&
670 : (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
671 : "Empty and not used live-range?!");
672 :
673 4 : RegsToSpill[ResultPos++] = Reg;
674 : }
675 27148 : RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
676 : LLVM_DEBUG(dbgs() << RegsToSpill.size()
677 : << " registers to spill after remat.\n");
678 : }
679 :
680 : //===----------------------------------------------------------------------===//
681 : // Spilling
682 : //===----------------------------------------------------------------------===//
683 :
684 : /// If MI is a load or store of StackSlot, it can be removed.
685 43682 : bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
686 43682 : int FI = 0;
687 43682 : unsigned InstrReg = TII.isLoadFromStackSlot(*MI, FI);
688 : bool IsLoad = InstrReg;
689 43682 : if (!IsLoad)
690 42906 : InstrReg = TII.isStoreToStackSlot(*MI, FI);
691 :
692 : // We have a stack access. Is it the right register and slot?
693 43682 : if (InstrReg != Reg || FI != StackSlot)
694 : return false;
695 :
696 660 : if (!IsLoad)
697 460 : HSpiller.rmFromMergeableSpills(*MI, StackSlot);
698 :
699 : LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI);
700 660 : LIS.RemoveMachineInstrFromMaps(*MI);
701 660 : MI->eraseFromParent();
702 :
703 : if (IsLoad) {
704 : ++NumReloadsRemoved;
705 : --NumReloads;
706 : } else {
707 : ++NumSpillsRemoved;
708 : --NumSpills;
709 : }
710 :
711 660 : return true;
712 : }
713 :
714 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
715 : LLVM_DUMP_METHOD
716 : // Dump the range of instructions from B to E with their slot indexes.
717 : static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,
718 : MachineBasicBlock::iterator E,
719 : LiveIntervals const &LIS,
720 : const char *const header,
721 : unsigned VReg =0) {
722 : char NextLine = '\n';
723 : char SlotIndent = '\t';
724 :
725 : if (std::next(B) == E) {
726 : NextLine = ' ';
727 : SlotIndent = ' ';
728 : }
729 :
730 : dbgs() << '\t' << header << ": " << NextLine;
731 :
732 : for (MachineBasicBlock::iterator I = B; I != E; ++I) {
733 : SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();
734 :
735 : // If a register was passed in and this instruction has it as a
736 : // destination that is marked as an early clobber, print the
737 : // early-clobber slot index.
738 : if (VReg) {
739 : MachineOperand *MO = I->findRegisterDefOperand(VReg);
740 : if (MO && MO->isEarlyClobber())
741 : Idx = Idx.getRegSlot(true);
742 : }
743 :
744 : dbgs() << SlotIndent << Idx << '\t' << *I;
745 : }
746 : }
747 : #endif
748 :
749 : /// foldMemoryOperand - Try folding stack slot references in Ops into their
750 : /// instructions.
751 : ///
752 : /// @param Ops Operand indices from analyzeVirtReg().
753 : /// @param LoadMI Load instruction to use instead of stack slot when non-null.
754 : /// @return True on success.
755 44768 : bool InlineSpiller::
756 : foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
757 : MachineInstr *LoadMI) {
758 44768 : if (Ops.empty())
759 : return false;
760 : // Don't attempt folding in bundles.
761 44768 : MachineInstr *MI = Ops.front().first;
762 44768 : if (Ops.back().first != MI || MI->isBundled())
763 : return false;
764 :
765 : bool WasCopy = MI->isCopy();
766 : unsigned ImpReg = 0;
767 :
768 : // Spill subregs if the target allows it.
769 : // We always want to spill subregs for stackmap/patchpoint pseudos.
770 51632 : bool SpillSubRegs = TII.isSubregFoldable() ||
771 6870 : MI->getOpcode() == TargetOpcode::STATEPOINT ||
772 51580 : MI->getOpcode() == TargetOpcode::PATCHPOINT ||
773 : MI->getOpcode() == TargetOpcode::STACKMAP;
774 :
775 : // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
776 : // operands.
777 : SmallVector<unsigned, 8> FoldOps;
778 90370 : for (const auto &OpPair : Ops) {
779 45681 : unsigned Idx = OpPair.second;
780 : assert(MI == OpPair.first && "Instruction conflict during operand folding");
781 45681 : MachineOperand &MO = MI->getOperand(Idx);
782 45681 : if (MO.isImplicit()) {
783 7 : ImpReg = MO.getReg();
784 7 : continue;
785 : }
786 :
787 45674 : if (!SpillSubRegs && MO.getSubReg())
788 73 : return false;
789 : // We cannot fold a load instruction into a def.
790 45601 : if (LoadMI && MO.isDef())
791 : return false;
792 : // Tied use operands should not be passed to foldMemoryOperand.
793 45601 : if (!MI->isRegTiedToDefOperand(Idx))
794 44891 : FoldOps.push_back(Idx);
795 : }
796 :
797 : // If we only have implicit uses, we won't be able to fold that.
798 : // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
799 44689 : if (FoldOps.empty())
800 : return false;
801 :
802 44682 : MachineInstrSpan MIS(MI);
803 :
804 : MachineInstr *FoldMI =
805 44682 : LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
806 76640 : : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS);
807 44682 : if (!FoldMI)
808 : return false;
809 :
810 : // Remove LIS for any dead defs in the original MI not in FoldMI.
811 97453 : for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
812 69538 : if (!MO->isReg())
813 69356 : continue;
814 67593 : unsigned Reg = MO->getReg();
815 67593 : if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
816 12526 : MRI.isReserved(Reg)) {
817 : continue;
818 : }
819 : // Skip non-Defs, including undef uses and internal reads.
820 11361 : if (MO->isUse())
821 : continue;
822 : MIBundleOperands::PhysRegInfo RI =
823 4930 : MIBundleOperands(*FoldMI).analyzePhysReg(Reg, &TRI);
824 4930 : if (RI.FullyDefined)
825 : continue;
826 : // FoldMI does not define this physreg. Remove the LI segment.
827 : assert(MO->isDead() && "Cannot fold physreg def");
828 182 : SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
829 182 : LIS.removePhysRegDefAt(Reg, Idx);
830 : }
831 :
832 : int FI;
833 27915 : if (TII.isStoreToStackSlot(*MI, FI) &&
834 3 : HSpiller.rmFromMergeableSpills(*MI, FI))
835 : --NumSpills;
836 27915 : LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
837 27915 : MI->eraseFromParent();
838 :
839 : // Insert any new instructions other than FoldMI into the LIS maps.
840 : assert(!MIS.empty() && "Unexpected empty span of instructions!");
841 55830 : for (MachineInstr &MI : MIS)
842 27915 : if (&MI != FoldMI)
843 0 : LIS.InsertMachineInstrInMaps(MI);
844 :
845 : // TII.foldMemoryOperand may have left some implicit operands on the
846 : // instruction. Strip them.
847 27915 : if (ImpReg)
848 0 : for (unsigned i = FoldMI->getNumOperands(); i; --i) {
849 0 : MachineOperand &MO = FoldMI->getOperand(i - 1);
850 0 : if (!MO.isReg() || !MO.isImplicit())
851 : break;
852 0 : if (MO.getReg() == ImpReg)
853 0 : FoldMI->RemoveOperand(i - 1);
854 : }
855 :
856 : LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,
857 : "folded"));
858 :
859 27915 : if (!WasCopy)
860 : ++NumFolded;
861 19096 : else if (Ops.front().second == 0) {
862 : ++NumSpills;
863 9189 : HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
864 : } else
865 : ++NumReloads;
866 : return true;
867 : }
868 :
869 0 : void InlineSpiller::insertReload(unsigned NewVReg,
870 : SlotIndex Idx,
871 : MachineBasicBlock::iterator MI) {
872 0 : MachineBasicBlock &MBB = *MI->getParent();
873 :
874 0 : MachineInstrSpan MIS(MI);
875 0 : TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
876 0 : MRI.getRegClass(NewVReg), &TRI);
877 :
878 0 : LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
879 :
880 : LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",
881 : NewVReg));
882 : ++NumReloads;
883 0 : }
884 :
885 : /// Check if \p Def fully defines a VReg with an undefined value.
886 : /// If that's the case, that means the value of VReg is actually
887 : /// not relevant.
888 : static bool isFullUndefDef(const MachineInstr &Def) {
889 5334 : if (!Def.isImplicitDef())
890 : return false;
891 : assert(Def.getNumOperands() == 1 &&
892 : "Implicit def with more than one definition");
893 : // We can say that the VReg defined by Def is undef, only if it is
894 : // fully defined by Def. Otherwise, some of the lanes may not be
895 : // undef and the value of the VReg matters.
896 12 : return !Def.getOperand(0).getSubReg();
897 : }
898 :
899 : /// insertSpill - Insert a spill of NewVReg after MI.
900 5334 : void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill,
901 : MachineBasicBlock::iterator MI) {
902 5334 : MachineBasicBlock &MBB = *MI->getParent();
903 :
904 5334 : MachineInstrSpan MIS(MI);
905 : bool IsRealSpill = true;
906 12 : if (isFullUndefDef(*MI)) {
907 : // Don't spill undef value.
908 : // Anything works for undef, in particular keeping the memory
909 : // uninitialized is a viable option and it saves code size and
910 : // run time.
911 24 : BuildMI(MBB, std::next(MI), MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
912 12 : .addReg(NewVReg, getKillRegState(isKill));
913 : IsRealSpill = false;
914 : } else
915 5322 : TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot,
916 5322 : MRI.getRegClass(NewVReg), &TRI);
917 :
918 5334 : LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end());
919 :
920 : LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS,
921 : "spill"));
922 : ++NumSpills;
923 5334 : if (IsRealSpill)
924 5322 : HSpiller.addToMergeableSpills(*std::next(MI), StackSlot, Original);
925 5334 : }
926 :
927 : /// spillAroundUses - insert spill code around each use of Reg.
928 17232 : void InlineSpiller::spillAroundUses(unsigned Reg) {
929 : LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n');
930 17232 : LiveInterval &OldLI = LIS.getInterval(Reg);
931 :
932 : // Iterate over instructions using Reg.
933 : for (MachineRegisterInfo::reg_bundle_iterator
934 34464 : RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
935 62378 : RegI != E; ) {
936 45146 : MachineInstr *MI = &*(RegI++);
937 :
938 : // Debug values are not allowed to affect codegen.
939 45146 : if (MI->isDebugValue()) {
940 : // Modify DBG_VALUE now that the value is in a spill slot.
941 0 : MachineBasicBlock *MBB = MI->getParent();
942 : LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI);
943 0 : buildDbgValueForSpill(*MBB, MI, *MI, StackSlot);
944 0 : MBB->erase(MI);
945 32248 : continue;
946 : }
947 :
948 : assert(!MI->isDebugInstr() && "Did not expect to find a use in debug "
949 : "instruction that isn't a DBG_VALUE");
950 :
951 : // Ignore copies to/from snippets. We'll delete them.
952 45146 : if (SnippetCopies.count(MI))
953 : continue;
954 :
955 : // Stack slot accesses may coalesce away.
956 43682 : if (coalesceStackAccess(MI, Reg))
957 : continue;
958 :
959 : // Analyze instruction.
960 : SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;
961 : MIBundleOperands::VirtRegInfo RI =
962 43022 : MIBundleOperands(*MI).analyzeVirtReg(Reg, &Ops);
963 :
964 : // Find the slot index where this instruction reads and writes OldLI.
965 : // This is usually the def slot, except for tied early clobbers.
966 43022 : SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
967 86044 : if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
968 23522 : if (SlotIndex::isSameInstr(Idx, VNI->def))
969 : Idx = VNI->def;
970 :
971 : // Check for a sibling copy.
972 43022 : unsigned SibReg = isFullCopyOf(*MI, Reg);
973 23819 : if (SibReg && isSibling(SibReg)) {
974 : // This may actually be a copy between snippets.
975 15189 : if (isRegToSpill(SibReg)) {
976 : LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI);
977 0 : SnippetCopies.insert(MI);
978 0 : continue;
979 : }
980 15189 : if (RI.Writes) {
981 8601 : if (hoistSpillInsideBB(OldLI, *MI)) {
982 : // This COPY is now dead, the value is already in the stack slot.
983 4616 : MI->getOperand(0).setIsDead();
984 4616 : DeadDefs.push_back(MI);
985 4616 : continue;
986 : }
987 : } else {
988 : // This is a reload for a sib-reg copy. Drop spills downstream.
989 6588 : LiveInterval &SibLI = LIS.getInterval(SibReg);
990 13176 : eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
991 : // The COPY will fold to a reload below.
992 : }
993 : }
994 :
995 : // Attempt to fold memory ops.
996 38406 : if (foldMemoryOperand(Ops))
997 : continue;
998 :
999 : // Create a new virtual register for spill/fill.
1000 : // FIXME: Infer regclass from instruction alone.
1001 12898 : unsigned NewVReg = Edit->createFrom(Reg);
1002 :
1003 12898 : if (RI.Reads)
1004 15630 : insertReload(NewVReg, Idx, MI);
1005 :
1006 : // Rewrite instruction operands.
1007 : bool hasLiveDef = false;
1008 26101 : for (const auto &OpPair : Ops) {
1009 13203 : MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
1010 13203 : MO.setReg(NewVReg);
1011 13203 : if (MO.isUse()) {
1012 7847 : if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1013 : MO.setIsKill();
1014 : } else {
1015 5356 : if (!MO.isDead())
1016 : hasLiveDef = true;
1017 : }
1018 : }
1019 : LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n');
1020 :
1021 : // FIXME: Use a second vreg if instruction has no tied ops.
1022 12898 : if (RI.Writes)
1023 5353 : if (hasLiveDef)
1024 10668 : insertSpill(NewVReg, true, MI);
1025 : }
1026 17232 : }
1027 :
1028 : /// spillAll - Spill all registers remaining after rematerialization.
1029 16504 : void InlineSpiller::spillAll() {
1030 : // Update LiveStacks now that we are committed to spilling.
1031 16504 : if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
1032 14514 : StackSlot = VRM.assignVirt2StackSlot(Original);
1033 29028 : StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
1034 29028 : StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
1035 : } else
1036 3980 : StackInt = &LSS.getInterval(StackSlot);
1037 :
1038 33008 : if (Original != Edit->getReg())
1039 9375 : VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1040 :
1041 : assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
1042 33736 : for (unsigned Reg : RegsToSpill)
1043 34464 : StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
1044 : StackInt->getValNumInfo(0));
1045 : LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
1046 :
1047 : // Spill around uses of all RegsToSpill.
1048 33736 : for (unsigned Reg : RegsToSpill)
1049 17232 : spillAroundUses(Reg);
1050 :
1051 : // Hoisted spills may cause dead code.
1052 16504 : if (!DeadDefs.empty()) {
1053 : LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
1054 9218 : Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
1055 : }
1056 :
1057 : // Finally delete the SnippetCopies.
1058 33736 : for (unsigned Reg : RegsToSpill) {
1059 732 : for (MachineRegisterInfo::reg_instr_iterator
1060 17232 : RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
1061 17964 : RI != E; ) {
1062 : MachineInstr &MI = *(RI++);
1063 : assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy");
1064 : // FIXME: Do this with a LiveRangeEdit callback.
1065 732 : LIS.RemoveMachineInstrFromMaps(MI);
1066 732 : MI.eraseFromParent();
1067 : }
1068 : }
1069 :
1070 : // Delete all spilled registers.
1071 33736 : for (unsigned Reg : RegsToSpill)
1072 17232 : Edit->eraseVirtReg(Reg);
1073 16504 : }
1074 :
1075 30076 : void InlineSpiller::spill(LiveRangeEdit &edit) {
1076 : ++NumSpilledRanges;
1077 30076 : Edit = &edit;
1078 : assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
1079 : && "Trying to spill a stack slot.");
1080 : // Share a stack slot among all descendants of Original.
1081 44336 : Original = VRM.getOriginal(edit.getReg());
1082 30076 : StackSlot = VRM.getStackSlot(Original);
1083 30076 : StackInt = nullptr;
1084 :
1085 : LLVM_DEBUG(dbgs() << "Inline spilling "
1086 : << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))
1087 : << ':' << edit.getParent() << "\nFrom original "
1088 : << printReg(Original) << '\n');
1089 : assert(edit.getParent().isSpillable() &&
1090 : "Attempting to spill already spilled value.");
1091 : assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
1092 :
1093 30076 : collectRegsToSpill();
1094 30076 : reMaterializeAll();
1095 :
1096 : // Remat may handle everything.
1097 30076 : if (!RegsToSpill.empty())
1098 16504 : spillAll();
1099 :
1100 30076 : Edit->calculateRegClassAndHint(MF, Loops, MBFI);
1101 30076 : }
1102 :
1103 : /// Optimizations after all the reg selections and spills are done.
1104 193995 : void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1105 :
1106 : /// When a spill is inserted, add the spill to MergeableSpills map.
1107 19127 : void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
1108 : unsigned Original) {
1109 19127 : BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1110 19127 : LiveInterval &OrigLI = LIS.getInterval(Original);
1111 : // save a copy of LiveInterval in StackSlotToOrigLI because the original
1112 : // LiveInterval may be cleared after all its references are spilled.
1113 19127 : if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
1114 14093 : auto LI = llvm::make_unique<LiveInterval>(OrigLI.reg, OrigLI.weight);
1115 14093 : LI->assign(OrigLI, Allocator);
1116 : StackSlotToOrigLI[StackSlot] = std::move(LI);
1117 : }
1118 19127 : SlotIndex Idx = LIS.getInstructionIndex(Spill);
1119 19127 : VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot());
1120 19127 : std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1121 19127 : MergeableSpills[MIdx].insert(&Spill);
1122 19127 : }
1123 :
1124 : /// When a spill is removed, remove the spill from MergeableSpills map.
1125 : /// Return true if the spill is removed successfully.
1126 872 : bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
1127 : int StackSlot) {
1128 872 : auto It = StackSlotToOrigLI.find(StackSlot);
1129 872 : if (It == StackSlotToOrigLI.end())
1130 : return false;
1131 872 : SlotIndex Idx = LIS.getInstructionIndex(Spill);
1132 872 : VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
1133 872 : std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1134 1744 : return MergeableSpills[MIdx].erase(&Spill);
1135 : }
1136 :
1137 : /// Check BB to see if it is a possible target BB to place a hoisted spill,
1138 : /// i.e., there should be a living sibling of OrigReg at the insert point.
1139 0 : bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
1140 : MachineBasicBlock &BB, unsigned &LiveReg) {
1141 : SlotIndex Idx;
1142 0 : unsigned OrigReg = OrigLI.reg;
1143 0 : MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, BB);
1144 0 : if (MI != BB.end())
1145 0 : Idx = LIS.getInstructionIndex(*MI);
1146 : else
1147 0 : Idx = LIS.getMBBEndIdx(&BB).getPrevSlot();
1148 0 : SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg];
1149 : assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI");
1150 :
1151 0 : for (auto const SibReg : Siblings) {
1152 0 : LiveInterval &LI = LIS.getInterval(SibReg);
1153 0 : VNInfo *VNI = LI.getVNInfoAt(Idx);
1154 0 : if (VNI) {
1155 0 : LiveReg = SibReg;
1156 0 : return true;
1157 : }
1158 : }
1159 : return false;
1160 : }
1161 :
1162 : /// Remove redundant spills in the same BB. Save those redundant spills in
1163 : /// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1164 0 : void HoistSpillHelper::rmRedundantSpills(
1165 : SmallPtrSet<MachineInstr *, 16> &Spills,
1166 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
1167 : DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1168 : // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1169 : // another spill inside. If a BB contains more than one spill, only keep the
1170 : // earlier spill with smaller SlotIndex.
1171 0 : for (const auto CurrentSpill : Spills) {
1172 0 : MachineBasicBlock *Block = CurrentSpill->getParent();
1173 0 : MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
1174 0 : MachineInstr *PrevSpill = SpillBBToSpill[Node];
1175 0 : if (PrevSpill) {
1176 0 : SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
1177 0 : SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
1178 0 : MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1179 0 : MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1180 0 : SpillsToRm.push_back(SpillToRm);
1181 0 : SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
1182 : } else {
1183 0 : SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
1184 : }
1185 : }
1186 0 : for (const auto SpillToRm : SpillsToRm)
1187 : Spills.erase(SpillToRm);
1188 0 : }
1189 :
1190 : /// Starting from \p Root find a top-down traversal order of the dominator
1191 : /// tree to visit all basic blocks containing the elements of \p Spills.
1192 : /// Redundant spills will be found and put into \p SpillsToRm at the same
1193 : /// time. \p SpillBBToSpill will be populated as part of the process and
1194 : /// maps a basic block to the first store occurring in the basic block.
1195 : /// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1196 0 : void HoistSpillHelper::getVisitOrders(
1197 : MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
1198 : SmallVectorImpl<MachineDomTreeNode *> &Orders,
1199 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
1200 : DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
1201 : DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1202 : // The set contains all the possible BB nodes to which we may hoist
1203 : // original spills.
1204 : SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;
1205 : // Save the BB nodes on the path from the first BB node containing
1206 : // non-redundant spill to the Root node.
1207 : SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath;
1208 : // All the spills to be hoisted must originate from a single def instruction
1209 : // to the OrigReg. It means the def instruction should dominate all the spills
1210 : // to be hoisted. We choose the BB where the def instruction is located as
1211 : // the Root.
1212 0 : MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
1213 : // For every node on the dominator tree with spill, walk up on the dominator
1214 : // tree towards the Root node until it is reached. If there is other node
1215 : // containing spill in the middle of the path, the previous spill saw will
1216 : // be redundant and the node containing it will be removed. All the nodes on
1217 : // the path starting from the first node with non-redundant spill to the Root
1218 : // node will be added to the WorkSet, which will contain all the possible
1219 : // locations where spills may be hoisted to after the loop below is done.
1220 0 : for (const auto Spill : Spills) {
1221 0 : MachineBasicBlock *Block = Spill->getParent();
1222 0 : MachineDomTreeNode *Node = MDT[Block];
1223 0 : MachineInstr *SpillToRm = nullptr;
1224 0 : while (Node != RootIDomNode) {
1225 : // If Node dominates Block, and it already contains a spill, the spill in
1226 : // Block will be redundant.
1227 0 : if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1228 0 : SpillToRm = SpillBBToSpill[MDT[Block]];
1229 0 : break;
1230 : /// If we see the Node already in WorkSet, the path from the Node to
1231 : /// the Root node must already be traversed by another spill.
1232 : /// Then no need to repeat.
1233 0 : } else if (WorkSet.count(Node)) {
1234 : break;
1235 : } else {
1236 0 : NodesOnPath.insert(Node);
1237 : }
1238 0 : Node = Node->getIDom();
1239 : }
1240 0 : if (SpillToRm) {
1241 0 : SpillsToRm.push_back(SpillToRm);
1242 : } else {
1243 : // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1244 : // set the initial status before hoisting start. The value of BBs
1245 : // containing original spills is set to 0, in order to descriminate
1246 : // with BBs containing hoisted spills which will be inserted to
1247 : // SpillsToKeep later during hoisting.
1248 0 : SpillsToKeep[MDT[Block]] = 0;
1249 0 : WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
1250 : }
1251 0 : NodesOnPath.clear();
1252 : }
1253 :
1254 : // Sort the nodes in WorkSet in top-down order and save the nodes
1255 : // in Orders. Orders will be used for hoisting in runHoistSpills.
1256 : unsigned idx = 0;
1257 0 : Orders.push_back(MDT.getBase().getNode(Root));
1258 : do {
1259 0 : MachineDomTreeNode *Node = Orders[idx++];
1260 : const std::vector<MachineDomTreeNode *> &Children = Node->getChildren();
1261 0 : unsigned NumChildren = Children.size();
1262 0 : for (unsigned i = 0; i != NumChildren; ++i) {
1263 0 : MachineDomTreeNode *Child = Children[i];
1264 0 : if (WorkSet.count(Child))
1265 0 : Orders.push_back(Child);
1266 : }
1267 0 : } while (idx != Orders.size());
1268 : assert(Orders.size() == WorkSet.size() &&
1269 : "Orders have different size with WorkSet");
1270 :
1271 : #ifndef NDEBUG
1272 : LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");
1273 : SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1274 : for (; RIt != Orders.rend(); RIt++)
1275 : LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");
1276 : LLVM_DEBUG(dbgs() << "\n");
1277 : #endif
1278 0 : }
1279 :
1280 : /// Try to hoist spills according to BB hotness. The spills to removed will
1281 : /// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1282 : /// \p SpillsToIns.
1283 0 : void HoistSpillHelper::runHoistSpills(
1284 : LiveInterval &OrigLI, VNInfo &OrigVNI,
1285 : SmallPtrSet<MachineInstr *, 16> &Spills,
1286 : SmallVectorImpl<MachineInstr *> &SpillsToRm,
1287 : DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) {
1288 : // Visit order of dominator tree nodes.
1289 : SmallVector<MachineDomTreeNode *, 32> Orders;
1290 : // SpillsToKeep contains all the nodes where spills are to be inserted
1291 : // during hoisting. If the spill to be inserted is an original spill
1292 : // (not a hoisted one), the value of the map entry is 0. If the spill
1293 : // is a hoisted spill, the value of the map entry is the VReg to be used
1294 : // as the source of the spill.
1295 : DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep;
1296 : // Map from BB to the first spill inside of it.
1297 : DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;
1298 :
1299 0 : rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1300 :
1301 0 : MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
1302 0 : getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1303 : SpillBBToSpill);
1304 :
1305 : // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1306 : // nodes set and the cost of all the spills inside those nodes.
1307 : // The nodes set are the locations where spills are to be inserted
1308 : // in the subtree of current node.
1309 : using NodesCostPair =
1310 : std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
1311 : DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;
1312 :
1313 : // Iterate Orders set in reverse order, which will be a bottom-up order
1314 : // in the dominator tree. Once we visit a dom tree node, we know its
1315 : // children have already been visited and the spill locations in the
1316 : // subtrees of all the children have been determined.
1317 : SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1318 0 : for (; RIt != Orders.rend(); RIt++) {
1319 0 : MachineBasicBlock *Block = (*RIt)->getBlock();
1320 :
1321 : // If Block contains an original spill, simply continue.
1322 0 : if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
1323 0 : SpillsInSubTreeMap[*RIt].first.insert(*RIt);
1324 : // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
1325 0 : SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1326 0 : continue;
1327 : }
1328 :
1329 : // Collect spills in subtree of current node (*RIt) to
1330 : // SpillsInSubTreeMap[*RIt].first.
1331 0 : const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren();
1332 0 : unsigned NumChildren = Children.size();
1333 0 : for (unsigned i = 0; i != NumChildren; ++i) {
1334 0 : MachineDomTreeNode *Child = Children[i];
1335 0 : if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
1336 0 : continue;
1337 : // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
1338 : // should be placed before getting the begin and end iterators of
1339 : // SpillsInSubTreeMap[Child].first, or else the iterators may be
1340 : // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1341 : // and the map grows and then the original buckets in the map are moved.
1342 : SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1343 : SpillsInSubTreeMap[*RIt].first;
1344 0 : BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1345 0 : SubTreeCost += SpillsInSubTreeMap[Child].second;
1346 0 : auto BI = SpillsInSubTreeMap[Child].first.begin();
1347 0 : auto EI = SpillsInSubTreeMap[Child].first.end();
1348 0 : SpillsInSubTree.insert(BI, EI);
1349 0 : SpillsInSubTreeMap.erase(Child);
1350 : }
1351 :
1352 : SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1353 : SpillsInSubTreeMap[*RIt].first;
1354 0 : BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1355 : // No spills in subtree, simply continue.
1356 0 : if (SpillsInSubTree.empty())
1357 0 : continue;
1358 :
1359 : // Check whether Block is a possible candidate to insert spill.
1360 0 : unsigned LiveReg = 0;
1361 0 : if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1362 0 : continue;
1363 :
1364 : // If there are multiple spills that could be merged, bias a little
1365 : // to hoist the spill.
1366 0 : BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
1367 : ? BranchProbability(9, 10)
1368 0 : : BranchProbability(1, 1);
1369 0 : if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1370 : // Hoist: Move spills to current Block.
1371 0 : for (const auto SpillBB : SpillsInSubTree) {
1372 : // When SpillBB is a BB contains original spill, insert the spill
1373 : // to SpillsToRm.
1374 0 : if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
1375 0 : !SpillsToKeep[SpillBB]) {
1376 0 : MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1377 0 : SpillsToRm.push_back(SpillToRm);
1378 : }
1379 : // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1380 0 : SpillsToKeep.erase(SpillBB);
1381 : }
1382 : // Current Block is the BB containing the new hoisted spill. Add it to
1383 : // SpillsToKeep. LiveReg is the source of the new spill.
1384 0 : SpillsToKeep[*RIt] = LiveReg;
1385 : LLVM_DEBUG({
1386 : dbgs() << "spills in BB: ";
1387 : for (const auto Rspill : SpillsInSubTree)
1388 : dbgs() << Rspill->getBlock()->getNumber() << " ";
1389 : dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()
1390 : << "\n";
1391 : });
1392 0 : SpillsInSubTree.clear();
1393 0 : SpillsInSubTree.insert(*RIt);
1394 0 : SubTreeCost = MBFI.getBlockFreq(Block);
1395 : }
1396 : }
1397 : // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1398 : // save them to SpillsToIns.
1399 0 : for (const auto Ent : SpillsToKeep) {
1400 0 : if (Ent.second)
1401 0 : SpillsToIns[Ent.first->getBlock()] = Ent.second;
1402 : }
1403 0 : }
1404 :
1405 : /// For spills with equal values, remove redundant spills and hoist those left
1406 : /// to less hot spots.
1407 : ///
1408 : /// Spills with equal values will be collected into the same set in
1409 : /// MergeableSpills when spill is inserted. These equal spills are originated
1410 : /// from the same defining instruction and are dominated by the instruction.
1411 : /// Before hoisting all the equal spills, redundant spills inside in the same
1412 : /// BB are first marked to be deleted. Then starting from the spills left, walk
1413 : /// up on the dominator tree towards the Root node where the define instruction
1414 : /// is located, mark the dominated spills to be deleted along the way and
1415 : /// collect the BB nodes on the path from non-dominated spills to the define
1416 : /// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1417 : /// where we are considering to hoist the spills. We iterate the WorkSet in
1418 : /// bottom-up order, and for each node, we will decide whether to hoist spills
1419 : /// inside its subtree to that node. In this way, we can get benefit locally
1420 : /// even if hoisting all the equal spills to one cold place is impossible.
1421 193995 : void HoistSpillHelper::hoistAllSpills() {
1422 : SmallVector<unsigned, 4> NewVRegs;
1423 387991 : LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1424 :
1425 3197391 : for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
1426 3003395 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1427 3003395 : unsigned Original = VRM.getPreSplitReg(Reg);
1428 3003395 : if (!MRI.def_empty(Reg))
1429 1409128 : Virt2SiblingsMap[Original].insert(Reg);
1430 : }
1431 :
1432 : // Each entry in MergeableSpills contains a spill set with equal values.
1433 210945 : for (auto &Ent : MergeableSpills) {
1434 16949 : int Slot = Ent.first.first;
1435 16949 : LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
1436 16949 : VNInfo *OrigVNI = Ent.first.second;
1437 16949 : SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1438 16949 : if (Ent.second.empty())
1439 19 : continue;
1440 :
1441 : LLVM_DEBUG({
1442 : dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
1443 : << "Equal spills in BB: ";
1444 : for (const auto spill : EqValSpills)
1445 : dbgs() << spill->getParent()->getNumber() << " ";
1446 : dbgs() << "\n";
1447 : });
1448 :
1449 : // SpillsToRm is the spill set to be removed from EqValSpills.
1450 : SmallVector<MachineInstr *, 16> SpillsToRm;
1451 : // SpillsToIns is the spill set to be newly inserted after hoisting.
1452 : DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;
1453 :
1454 16930 : runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1455 :
1456 : LLVM_DEBUG({
1457 : dbgs() << "Finally inserted spills in BB: ";
1458 : for (const auto Ispill : SpillsToIns)
1459 : dbgs() << Ispill.first->getNumber() << " ";
1460 : dbgs() << "\nFinally removed spills in BB: ";
1461 : for (const auto Rspill : SpillsToRm)
1462 : dbgs() << Rspill->getParent()->getNumber() << " ";
1463 : dbgs() << "\n";
1464 : });
1465 :
1466 : // Stack live range update.
1467 33860 : LiveInterval &StackIntvl = LSS.getInterval(Slot);
1468 16930 : if (!SpillsToIns.empty() || !SpillsToRm.empty())
1469 1548 : StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1470 : StackIntvl.getValNumInfo(0));
1471 :
1472 : // Insert hoisted spills.
1473 17433 : for (auto const Insert : SpillsToIns) {
1474 : MachineBasicBlock *BB = Insert.first;
1475 : unsigned LiveReg = Insert.second;
1476 503 : MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, *BB);
1477 503 : TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot,
1478 503 : MRI.getRegClass(LiveReg), &TRI);
1479 503 : LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI);
1480 : ++NumSpills;
1481 : }
1482 :
1483 : // Remove redundant spills or change them to dead instructions.
1484 16930 : NumSpills -= SpillsToRm.size();
1485 18610 : for (auto const RMEnt : SpillsToRm) {
1486 1680 : RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1487 11320 : for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1488 9640 : MachineOperand &MO = RMEnt->getOperand(i - 1);
1489 9640 : if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1490 35 : RMEnt->RemoveOperand(i - 1);
1491 : }
1492 : }
1493 33860 : Edit.eliminateDeadDefs(SpillsToRm, None, AA);
1494 : }
1495 193996 : }
1496 :
1497 : /// For VirtReg clone, the \p New register should have the same physreg or
1498 : /// stackslot as the \p old register.
1499 32 : void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
1500 64 : if (VRM.hasPhys(Old))
1501 32 : VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1502 0 : else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1503 0 : VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1504 : else
1505 0 : llvm_unreachable("VReg should be assigned either physreg or stackslot");
1506 32 : }
|
