LLVM 22.0.0git
InlineSpiller.cpp
Go to the documentation of this file.
1//===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The inline spiller modifies the machine function directly instead of
10// inserting spills and restores in VirtRegMap.
11//
12//===----------------------------------------------------------------------===//
13
14#include "AllocationOrder.h"
15#include "SplitKit.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/MapVector.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/Statistic.h"
46#include "llvm/Config/llvm-config.h"
51#include "llvm/Support/Debug.h"
54#include <cassert>
55#include <iterator>
56#include <tuple>
57#include <utility>
58
59using namespace llvm;
60
61#define DEBUG_TYPE "regalloc"
62
63STATISTIC(NumSpilledRanges, "Number of spilled live ranges");
64STATISTIC(NumSnippets, "Number of spilled snippets");
65STATISTIC(NumSpills, "Number of spills inserted");
66STATISTIC(NumSpillsRemoved, "Number of spills removed");
67STATISTIC(NumReloads, "Number of reloads inserted");
68STATISTIC(NumReloadsRemoved, "Number of reloads removed");
69STATISTIC(NumFolded, "Number of folded stack accesses");
70STATISTIC(NumFoldedLoads, "Number of folded loads");
71STATISTIC(NumRemats, "Number of rematerialized defs for spilling");
72
73static cl::opt<bool>
74RestrictStatepointRemat("restrict-statepoint-remat",
75 cl::init(false), cl::Hidden,
76 cl::desc("Restrict remat for statepoint operands"));
77
78namespace {
79class HoistSpillHelper : private LiveRangeEdit::Delegate {
81 LiveIntervals &LIS;
82 LiveStacks &LSS;
84 VirtRegMap &VRM;
86 const TargetInstrInfo &TII;
88 const MachineBlockFrequencyInfo &MBFI;
89
91
92 // Map from StackSlot to the LiveInterval of the original register.
93 // Note the LiveInterval of the original register may have been deleted
94 // after it is spilled. We keep a copy here to track the range where
95 // spills can be moved.
97
98 // Map from pair of (StackSlot and Original VNI) to a set of spills which
99 // have the same stackslot and have equal values defined by Original VNI.
100 // These spills are mergeable and are hoist candidates.
101 using MergeableSpillsMap =
103 MergeableSpillsMap MergeableSpills;
104
105 /// This is the map from original register to a set containing all its
106 /// siblings. To hoist a spill to another BB, we need to find out a live
107 /// sibling there and use it as the source of the new spill.
109
110 bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
111 MachineBasicBlock &BB, Register &LiveReg);
112
113 void rmRedundantSpills(
117
118 void getVisitOrders(
124
125 void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
129
130public:
131 HoistSpillHelper(const Spiller::RequiredAnalyses &Analyses,
132 MachineFunction &mf, VirtRegMap &vrm)
133 : MF(mf), LIS(Analyses.LIS), LSS(Analyses.LSS), MDT(Analyses.MDT),
134 VRM(vrm), MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
135 TRI(*mf.getSubtarget().getRegisterInfo()), MBFI(Analyses.MBFI),
136 IPA(LIS, mf.getNumBlockIDs()) {}
137
138 void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
139 Register Original);
140 bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
141 void hoistAllSpills();
142 void LRE_DidCloneVirtReg(Register, Register) override;
143};
144
145class InlineSpiller : public Spiller {
146 MachineFunction &MF;
147 LiveIntervals &LIS;
148 LiveStacks &LSS;
149 VirtRegMap &VRM;
150 MachineRegisterInfo &MRI;
151 const TargetInstrInfo &TII;
152 const TargetRegisterInfo &TRI;
153 LiveRegMatrix *Matrix = nullptr;
154
155 // Variables that are valid during spill(), but used by multiple methods.
156 LiveRangeEdit *Edit = nullptr;
157 LiveInterval *StackInt = nullptr;
158 int StackSlot;
159 Register Original;
160 AllocationOrder *Order = nullptr;
161
162 // All registers to spill to StackSlot, including the main register.
163 SmallVector<Register, 8> RegsToSpill;
164
165 // All registers that were replaced by the spiller through some other method,
166 // e.g. rematerialization.
167 SmallVector<Register, 8> RegsReplaced;
168
169 // All COPY instructions to/from snippets.
170 // They are ignored since both operands refer to the same stack slot.
171 // For bundled copies, this will only include the first header copy.
172 SmallPtrSet<MachineInstr*, 8> SnippetCopies;
173
174 // Values that failed to remat at some point.
175 SmallPtrSet<VNInfo*, 8> UsedValues;
176
177 // Dead defs generated during spilling.
178 SmallVector<MachineInstr*, 8> DeadDefs;
179
180 // Object records spills information and does the hoisting.
181 HoistSpillHelper HSpiller;
182
183 // Live range weight calculator.
184 VirtRegAuxInfo &VRAI;
185
186 ~InlineSpiller() override = default;
187
188public:
189 InlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF,
190 VirtRegMap &VRM, VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix)
191 : MF(MF), LIS(Analyses.LIS), LSS(Analyses.LSS), VRM(VRM),
192 MRI(MF.getRegInfo()), TII(*MF.getSubtarget().getInstrInfo()),
193 TRI(*MF.getSubtarget().getRegisterInfo()), Matrix(Matrix),
194 HSpiller(Analyses, MF, VRM), VRAI(VRAI) {}
195
196 void spill(LiveRangeEdit &, AllocationOrder *Order = nullptr) override;
197 ArrayRef<Register> getSpilledRegs() override { return RegsToSpill; }
198 ArrayRef<Register> getReplacedRegs() override { return RegsReplaced; }
199 void postOptimization() override;
200
201private:
202 bool isSnippet(const LiveInterval &SnipLI);
203 void collectRegsToSpill();
204
205 bool isRegToSpill(Register Reg) { return is_contained(RegsToSpill, Reg); }
206
207 bool isSibling(Register Reg);
208 bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
209 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
210
211 void markValueUsed(LiveInterval*, VNInfo*);
212 bool canGuaranteeAssignmentAfterRemat(Register VReg, MachineInstr &MI);
213 bool hasPhysRegAvailable(const MachineInstr &MI);
214 bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
215 void reMaterializeAll();
216
217 bool coalesceStackAccess(MachineInstr *MI, Register Reg);
218 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
219 MachineInstr *LoadMI = nullptr);
220 void insertReload(Register VReg, SlotIndex, MachineBasicBlock::iterator MI);
221 void insertSpill(Register VReg, bool isKill, MachineBasicBlock::iterator MI);
222
223 void spillAroundUses(Register Reg);
224 void spillAll();
225};
226
227} // end anonymous namespace
228
229Spiller::~Spiller() = default;
230
231void Spiller::anchor() {}
232
233Spiller *
234llvm::createInlineSpiller(const InlineSpiller::RequiredAnalyses &Analyses,
235 MachineFunction &MF, VirtRegMap &VRM,
237 return new InlineSpiller(Analyses, MF, VRM, VRAI, Matrix);
238}
239
240//===----------------------------------------------------------------------===//
241// Snippets
242//===----------------------------------------------------------------------===//
243
244// When spilling a virtual register, we also spill any snippets it is connected
245// to. The snippets are small live ranges that only have a single real use,
246// leftovers from live range splitting. Spilling them enables memory operand
247// folding or tightens the live range around the single use.
248//
249// This minimizes register pressure and maximizes the store-to-load distance for
250// spill slots which can be important in tight loops.
251
252/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
253/// otherwise return 0.
255 const TargetInstrInfo &TII) {
256 if (!TII.isCopyInstr(MI))
257 return Register();
258
259 const MachineOperand &DstOp = MI.getOperand(0);
260 const MachineOperand &SrcOp = MI.getOperand(1);
261
262 // TODO: Probably only worth allowing subreg copies with undef dests.
263 if (DstOp.getSubReg() != SrcOp.getSubReg())
264 return Register();
265 if (DstOp.getReg() == Reg)
266 return SrcOp.getReg();
267 if (SrcOp.getReg() == Reg)
268 return DstOp.getReg();
269 return Register();
270}
271
272/// Check for a copy bundle as formed by SplitKit.
274 const TargetInstrInfo &TII) {
275 if (!FirstMI.isBundled())
276 return isCopyOf(FirstMI, Reg, TII);
277
278 assert(!FirstMI.isBundledWithPred() && FirstMI.isBundledWithSucc() &&
279 "expected to see first instruction in bundle");
280
281 Register SnipReg;
283 while (I->isBundledWithSucc()) {
284 const MachineInstr &MI = *I;
285 auto CopyInst = TII.isCopyInstr(MI);
286 if (!CopyInst)
287 return Register();
288
289 const MachineOperand &DstOp = *CopyInst->Destination;
290 const MachineOperand &SrcOp = *CopyInst->Source;
291 if (DstOp.getReg() == Reg) {
292 if (!SnipReg)
293 SnipReg = SrcOp.getReg();
294 else if (SnipReg != SrcOp.getReg())
295 return Register();
296 } else if (SrcOp.getReg() == Reg) {
297 if (!SnipReg)
298 SnipReg = DstOp.getReg();
299 else if (SnipReg != DstOp.getReg())
300 return Register();
301 }
302
303 ++I;
304 }
305
306 return Register();
307}
308
309static void getVDefInterval(const MachineInstr &MI, LiveIntervals &LIS) {
310 for (const MachineOperand &MO : MI.all_defs())
311 if (MO.getReg().isVirtual())
312 LIS.getInterval(MO.getReg());
313}
314
315/// isSnippet - Identify if a live interval is a snippet that should be spilled.
316/// It is assumed that SnipLI is a virtual register with the same original as
317/// Edit->getReg().
318bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
319 Register Reg = Edit->getReg();
320
321 // A snippet is a tiny live range with only a single instruction using it
322 // besides copies to/from Reg or spills/fills.
323 // Exception is done for statepoint instructions which will fold fills
324 // into their operands.
325 // We accept:
326 //
327 // %snip = COPY %Reg / FILL fi#
328 // %snip = USE %snip
329 // %snip = STATEPOINT %snip in var arg area
330 // %Reg = COPY %snip / SPILL %snip, fi#
331 //
332 if (!LIS.intervalIsInOneMBB(SnipLI))
333 return false;
334
335 // Number of defs should not exceed 2 not accounting defs coming from
336 // statepoint instructions.
337 unsigned NumValNums = SnipLI.getNumValNums();
338 for (auto *VNI : SnipLI.vnis()) {
339 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
340 if (MI->getOpcode() == TargetOpcode::STATEPOINT)
341 --NumValNums;
342 }
343 if (NumValNums > 2)
344 return false;
345
346 MachineInstr *UseMI = nullptr;
347
348 // Check that all uses satisfy our criteria.
350 RI = MRI.reg_bundle_nodbg_begin(SnipLI.reg()),
351 E = MRI.reg_bundle_nodbg_end();
352 RI != E;) {
353 MachineInstr &MI = *RI++;
354
355 // Allow copies to/from Reg.
356 if (isCopyOfBundle(MI, Reg, TII))
357 continue;
358
359 // Allow stack slot loads.
360 int FI;
361 if (SnipLI.reg() == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
362 continue;
363
364 // Allow stack slot stores.
365 if (SnipLI.reg() == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
366 continue;
367
368 if (StatepointOpers::isFoldableReg(&MI, SnipLI.reg()))
369 continue;
370
371 // Allow a single additional instruction.
372 if (UseMI && &MI != UseMI)
373 return false;
374 UseMI = &MI;
375 }
376 return true;
377}
378
379/// collectRegsToSpill - Collect live range snippets that only have a single
380/// real use.
381void InlineSpiller::collectRegsToSpill() {
382 Register Reg = Edit->getReg();
383
384 // Main register always spills.
385 RegsToSpill.assign(1, Reg);
386 SnippetCopies.clear();
387 RegsReplaced.clear();
388
389 // Snippets all have the same original, so there can't be any for an original
390 // register.
391 if (Original == Reg)
392 return;
393
394 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {
395 Register SnipReg = isCopyOfBundle(MI, Reg, TII);
396 if (!isSibling(SnipReg))
397 continue;
398 LiveInterval &SnipLI = LIS.getInterval(SnipReg);
399 if (!isSnippet(SnipLI))
400 continue;
401 SnippetCopies.insert(&MI);
402 if (isRegToSpill(SnipReg))
403 continue;
404 RegsToSpill.push_back(SnipReg);
405 LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
406 ++NumSnippets;
407 }
408}
409
410bool InlineSpiller::isSibling(Register Reg) {
411 return Reg.isVirtual() && VRM.getOriginal(Reg) == Original;
412}
413
414/// It is beneficial to spill to earlier place in the same BB in case
415/// as follows:
416/// There is an alternative def earlier in the same MBB.
417/// Hoist the spill as far as possible in SpillMBB. This can ease
418/// register pressure:
419///
420/// x = def
421/// y = use x
422/// s = copy x
423///
424/// Hoisting the spill of s to immediately after the def removes the
425/// interference between x and y:
426///
427/// x = def
428/// spill x
429/// y = use killed x
430///
431/// This hoist only helps when the copy kills its source.
432///
433bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
434 MachineInstr &CopyMI) {
435 SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
436#ifndef NDEBUG
437 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
438 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");
439#endif
440
441 Register SrcReg = CopyMI.getOperand(1).getReg();
442 LiveInterval &SrcLI = LIS.getInterval(SrcReg);
443 VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
444 LiveQueryResult SrcQ = SrcLI.Query(Idx);
445 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
446 if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
447 return false;
448
449 // Conservatively extend the stack slot range to the range of the original
450 // value. We may be able to do better with stack slot coloring by being more
451 // careful here.
452 assert(StackInt && "No stack slot assigned yet.");
453 LiveInterval &OrigLI = LIS.getInterval(Original);
454 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
455 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
456 LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
457 << *StackInt << '\n');
458
459 // We are going to spill SrcVNI immediately after its def, so clear out
460 // any later spills of the same value.
461 eliminateRedundantSpills(SrcLI, SrcVNI);
462
463 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
465 if (SrcVNI->isPHIDef())
466 MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin(), SrcReg);
467 else {
468 MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
469 assert(DefMI && "Defining instruction disappeared");
470 MII = DefMI;
471 ++MII;
472 }
473 MachineInstrSpan MIS(MII, MBB);
474 // Insert spill without kill flag immediately after def.
475 TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
476 MRI.getRegClass(SrcReg), &TRI, Register());
477 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
478 for (const MachineInstr &MI : make_range(MIS.begin(), MII))
479 getVDefInterval(MI, LIS);
480 --MII; // Point to store instruction.
481 LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);
482
483 // If there is only 1 store instruction is required for spill, add it
484 // to mergeable list. In X86 AMX, 2 intructions are required to store.
485 // We disable the merge for this case.
486 if (MIS.begin() == MII)
487 HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
488 ++NumSpills;
489 return true;
490}
491
492/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
493/// redundant spills of this value in SLI.reg and sibling copies.
494void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
495 assert(VNI && "Missing value");
497 WorkList.push_back(std::make_pair(&SLI, VNI));
498 assert(StackInt && "No stack slot assigned yet.");
499
500 do {
501 LiveInterval *LI;
502 std::tie(LI, VNI) = WorkList.pop_back_val();
503 Register Reg = LI->reg();
504 LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'
505 << VNI->def << " in " << *LI << '\n');
506
507 // Regs to spill are taken care of.
508 if (isRegToSpill(Reg))
509 continue;
510
511 // Add all of VNI's live range to StackInt.
512 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
513 LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
514
515 // Find all spills and copies of VNI.
516 for (MachineInstr &MI :
517 llvm::make_early_inc_range(MRI.use_nodbg_bundles(Reg))) {
518 if (!MI.mayStore() && !TII.isCopyInstr(MI))
519 continue;
520 SlotIndex Idx = LIS.getInstructionIndex(MI);
521 if (LI->getVNInfoAt(Idx) != VNI)
522 continue;
523
524 // Follow sibling copies down the dominator tree.
525 if (Register DstReg = isCopyOfBundle(MI, Reg, TII)) {
526 if (isSibling(DstReg)) {
527 LiveInterval &DstLI = LIS.getInterval(DstReg);
528 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
529 assert(DstVNI && "Missing defined value");
530 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");
531
532 WorkList.push_back(std::make_pair(&DstLI, DstVNI));
533 }
534 continue;
535 }
536
537 // Erase spills.
538 int FI;
539 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
540 LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI);
541 // eliminateDeadDefs won't normally remove stores, so switch opcode.
542 MI.setDesc(TII.get(TargetOpcode::KILL));
543 DeadDefs.push_back(&MI);
544 ++NumSpillsRemoved;
545 if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
546 --NumSpills;
547 }
548 }
549 } while (!WorkList.empty());
550}
551
552//===----------------------------------------------------------------------===//
553// Rematerialization
554//===----------------------------------------------------------------------===//
555
556/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
557/// instruction cannot be eliminated. See through snippet copies
558void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
560 WorkList.push_back(std::make_pair(LI, VNI));
561 do {
562 std::tie(LI, VNI) = WorkList.pop_back_val();
563 if (!UsedValues.insert(VNI).second)
564 continue;
565
566 if (VNI->isPHIDef()) {
567 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
568 for (MachineBasicBlock *P : MBB->predecessors()) {
569 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
570 if (PVNI)
571 WorkList.push_back(std::make_pair(LI, PVNI));
572 }
573 continue;
574 }
575
576 // Follow snippet copies.
577 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
578 if (!SnippetCopies.count(MI))
579 continue;
580 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
581 assert(isRegToSpill(SnipLI.reg()) && "Unexpected register in copy");
582 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
583 assert(SnipVNI && "Snippet undefined before copy");
584 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
585 } while (!WorkList.empty());
586}
587
588bool InlineSpiller::canGuaranteeAssignmentAfterRemat(Register VReg,
589 MachineInstr &MI) {
591 return true;
592 // Here's a quick explanation of the problem we're trying to handle here:
593 // * There are some pseudo instructions with more vreg uses than there are
594 // physical registers on the machine.
595 // * This is normally handled by spilling the vreg, and folding the reload
596 // into the user instruction. (Thus decreasing the number of used vregs
597 // until the remainder can be assigned to physregs.)
598 // * However, since we may try to spill vregs in any order, we can end up
599 // trying to spill each operand to the instruction, and then rematting it
600 // instead. When that happens, the new live intervals (for the remats) are
601 // expected to be trivially assignable (i.e. RS_Done). However, since we
602 // may have more remats than physregs, we're guaranteed to fail to assign
603 // one.
604 // At the moment, we only handle this for STATEPOINTs since they're the only
605 // pseudo op where we've seen this. If we start seeing other instructions
606 // with the same problem, we need to revisit this.
607 if (MI.getOpcode() != TargetOpcode::STATEPOINT)
608 return true;
609 // For STATEPOINTs we allow re-materialization for fixed arguments only hoping
610 // that number of physical registers is enough to cover all fixed arguments.
611 // If it is not true we need to revisit it.
612 for (unsigned Idx = StatepointOpers(&MI).getVarIdx(),
613 EndIdx = MI.getNumOperands();
614 Idx < EndIdx; ++Idx) {
615 MachineOperand &MO = MI.getOperand(Idx);
616 if (MO.isReg() && MO.getReg() == VReg)
617 return false;
618 }
619 return true;
620}
621
622/// hasPhysRegAvailable - Check if there is an available physical register for
623/// rematerialization.
624bool InlineSpiller::hasPhysRegAvailable(const MachineInstr &MI) {
625 if (!Order || !Matrix)
626 return false;
627
628 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
629 SlotIndex PrevIdx = UseIdx.getPrevSlot();
630
631 for (MCPhysReg PhysReg : *Order) {
632 if (!Matrix->checkInterference(PrevIdx, UseIdx, PhysReg))
633 return true;
634 }
635
636 return false;
637}
638
639/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
640bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
641 // Analyze instruction
643 VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, VirtReg.reg(), &Ops);
644
645 // Defs without reads will be deleted if unused after remat is
646 // completed for other users of the virtual register.
647 if (!RI.Reads) {
648 LLVM_DEBUG(dbgs() << "\tskipping remat of def " << MI);
649 return false;
650 }
651
652 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
653 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
654
655 if (!ParentVNI) {
656 LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ");
657 for (MachineOperand &MO : MI.all_uses())
658 if (MO.getReg() == VirtReg.reg())
659 MO.setIsUndef();
660 LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI);
661 return true;
662 }
663
664 // Snippets copies are ignored for remat, and will be deleted if they
665 // don't feed a live user after rematerialization completes.
666 if (SnippetCopies.count(&MI)) {
667 LLVM_DEBUG(dbgs() << "\tskipping remat snippet copy for " << UseIdx << '\t'
668 << MI);
669 return false;
670 }
671
672 LiveInterval &OrigLI = LIS.getInterval(Original);
673 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
674 assert(OrigVNI && "corrupted sub-interval");
675 MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
676 // This can happen if for two reasons: 1) This could be a phi valno,
677 // or 2) the remat def has already been removed from the original
678 // live interval; this happens if we rematted to all uses, and
679 // then further split one of those live ranges.
680 if (!DefMI) {
681 markValueUsed(&VirtReg, ParentVNI);
682 LLVM_DEBUG(dbgs() << "\tcannot remat missing def for " << UseIdx << '\t'
683 << MI);
684 return false;
685 }
686
687 LiveRangeEdit::Remat RM(ParentVNI);
688 RM.OrigMI = DefMI;
689 if (!Edit->canRematerializeAt(RM, UseIdx)) {
690 markValueUsed(&VirtReg, ParentVNI);
691 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
692 return false;
693 }
694
695 // If the instruction also writes VirtReg.reg, it had better not require the
696 // same register for uses and defs.
697 if (RI.Tied) {
698 markValueUsed(&VirtReg, ParentVNI);
699 LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI);
700 return false;
701 }
702
703 // Before rematerializing into a register for a single instruction, try to
704 // fold a load into the instruction. That avoids allocating a new register.
705 if (RM.OrigMI->canFoldAsLoad() &&
706 (RM.OrigMI->mayLoad() || !hasPhysRegAvailable(MI)) &&
707 foldMemoryOperand(Ops, RM.OrigMI)) {
708 Edit->markRematerialized(RM.ParentVNI);
709 ++NumFoldedLoads;
710 return true;
711 }
712
713 // If we can't guarantee that we'll be able to actually assign the new vreg,
714 // we can't remat.
715 if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg(), MI)) {
716 markValueUsed(&VirtReg, ParentVNI);
717 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
718 return false;
719 }
720
721 // Allocate a new register for the remat.
722 Register NewVReg = Edit->createFrom(Original);
723
724 // Constrain it to the register class of MI.
725 MRI.constrainRegClass(NewVReg, MRI.getRegClass(VirtReg.reg()));
726
727 // Finally we can rematerialize OrigMI before MI.
728 SlotIndex DefIdx =
729 Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);
730
731 // We take the DebugLoc from MI, since OrigMI may be attributed to a
732 // different source location.
733 auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
734 NewMI->setDebugLoc(MI.getDebugLoc());
735
736 (void)DefIdx;
737 LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
738 << *LIS.getInstructionFromIndex(DefIdx));
739
740 // Replace operands
741 for (const auto &OpPair : Ops) {
742 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
743 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg()) {
744 MO.setReg(NewVReg);
745 MO.setIsKill();
746 }
747 }
748 LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n');
749
750 ++NumRemats;
751 return true;
752}
753
754/// reMaterializeAll - Try to rematerialize as many uses as possible,
755/// and trim the live ranges after.
756void InlineSpiller::reMaterializeAll() {
757 UsedValues.clear();
758
759 // Try to remat before all uses of snippets.
760 bool anyRemat = false;
761 for (Register Reg : RegsToSpill) {
762 LiveInterval &LI = LIS.getInterval(Reg);
763 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {
764 // Debug values are not allowed to affect codegen.
765 if (MI.isDebugValue())
766 continue;
767
768 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "
769 "instruction that isn't a DBG_VALUE");
770
771 anyRemat |= reMaterializeFor(LI, MI);
772 }
773 }
774 if (!anyRemat)
775 return;
776
777 // Remove any values that were completely rematted.
778 for (Register Reg : RegsToSpill) {
779 LiveInterval &LI = LIS.getInterval(Reg);
780 for (VNInfo *VNI : LI.vnis()) {
781 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
782 continue;
783 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
784 MI->addRegisterDead(Reg, &TRI);
785 if (!MI->allDefsAreDead())
786 continue;
787 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
788 DeadDefs.push_back(MI);
789 // If MI is a bundle header, also try removing copies inside the bundle,
790 // otherwise the verifier would complain "live range continues after dead
791 // def flag".
792 if (MI->isBundledWithSucc() && !MI->isBundledWithPred()) {
793 MachineBasicBlock::instr_iterator BeginIt = MI->getIterator(),
794 EndIt = MI->getParent()->instr_end();
795 ++BeginIt; // Skip MI that was already handled.
796
797 bool OnlyDeadCopies = true;
798 for (MachineBasicBlock::instr_iterator It = BeginIt;
799 It != EndIt && It->isBundledWithPred(); ++It) {
800
801 auto DestSrc = TII.isCopyInstr(*It);
802 bool IsCopyToDeadReg =
803 DestSrc && DestSrc->Destination->getReg() == Reg;
804 if (!IsCopyToDeadReg) {
805 OnlyDeadCopies = false;
806 break;
807 }
808 }
809 if (OnlyDeadCopies) {
810 for (MachineBasicBlock::instr_iterator It = BeginIt;
811 It != EndIt && It->isBundledWithPred(); ++It) {
812 It->addRegisterDead(Reg, &TRI);
813 LLVM_DEBUG(dbgs() << "All defs dead: " << *It);
814 DeadDefs.push_back(&*It);
815 }
816 }
817 }
818 }
819 }
820
821 // Eliminate dead code after remat. Note that some snippet copies may be
822 // deleted here.
823 if (DeadDefs.empty())
824 return;
825 LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
826 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
827
828 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
829 // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
830 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
831 // removed, PHI VNI are still left in the LiveInterval.
832 // So to get rid of unused reg, we need to check whether it has non-dbg
833 // reference instead of whether it has non-empty interval.
834 unsigned ResultPos = 0;
835 for (Register Reg : RegsToSpill) {
836 if (MRI.reg_nodbg_empty(Reg)) {
837 Edit->eraseVirtReg(Reg);
838 RegsReplaced.push_back(Reg);
839 continue;
840 }
841
842 assert(LIS.hasInterval(Reg) &&
843 (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
844 "Empty and not used live-range?!");
845
846 RegsToSpill[ResultPos++] = Reg;
847 }
848 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
849 LLVM_DEBUG(dbgs() << RegsToSpill.size()
850 << " registers to spill after remat.\n");
851}
852
853//===----------------------------------------------------------------------===//
854// Spilling
855//===----------------------------------------------------------------------===//
856
857/// If MI is a load or store of StackSlot, it can be removed.
858bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, Register Reg) {
859 int FI = 0;
860 Register InstrReg = TII.isLoadFromStackSlot(*MI, FI);
861 bool IsLoad = InstrReg.isValid();
862 if (!IsLoad)
863 InstrReg = TII.isStoreToStackSlot(*MI, FI);
864
865 // We have a stack access. Is it the right register and slot?
866 if (InstrReg != Reg || FI != StackSlot)
867 return false;
868
869 if (!IsLoad)
870 HSpiller.rmFromMergeableSpills(*MI, StackSlot);
871
872 LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI);
873 LIS.RemoveMachineInstrFromMaps(*MI);
874 MI->eraseFromParent();
875
876 if (IsLoad) {
877 ++NumReloadsRemoved;
878 --NumReloads;
879 } else {
880 ++NumSpillsRemoved;
881 --NumSpills;
882 }
883
884 return true;
885}
886
887#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
889// Dump the range of instructions from B to E with their slot indexes.
892 LiveIntervals const &LIS,
893 const char *const header,
894 Register VReg = Register()) {
895 char NextLine = '\n';
896 char SlotIndent = '\t';
897
898 if (std::next(B) == E) {
899 NextLine = ' ';
900 SlotIndent = ' ';
901 }
902
903 dbgs() << '\t' << header << ": " << NextLine;
904
905 for (MachineBasicBlock::iterator I = B; I != E; ++I) {
907
908 // If a register was passed in and this instruction has it as a
909 // destination that is marked as an early clobber, print the
910 // early-clobber slot index.
911 if (VReg) {
912 MachineOperand *MO = I->findRegisterDefOperand(VReg, /*TRI=*/nullptr);
913 if (MO && MO->isEarlyClobber())
914 Idx = Idx.getRegSlot(true);
915 }
916
917 dbgs() << SlotIndent << Idx << '\t' << *I;
918 }
919}
920#endif
921
922/// foldMemoryOperand - Try folding stack slot references in Ops into their
923/// instructions.
924///
925/// @param Ops Operand indices from AnalyzeVirtRegInBundle().
926/// @param LoadMI Load instruction to use instead of stack slot when non-null.
927/// @return True on success.
928bool InlineSpiller::
929foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
930 MachineInstr *LoadMI) {
931 if (Ops.empty())
932 return false;
933 // Don't attempt folding in bundles.
934 MachineInstr *MI = Ops.front().first;
935 if (Ops.back().first != MI || MI->isBundled())
936 return false;
937
938 bool WasCopy = TII.isCopyInstr(*MI).has_value();
939 Register ImpReg;
940
941 // TII::foldMemoryOperand will do what we need here for statepoint
942 // (fold load into use and remove corresponding def). We will replace
943 // uses of removed def with loads (spillAroundUses).
944 // For that to work we need to untie def and use to pass it through
945 // foldMemoryOperand and signal foldPatchpoint that it is allowed to
946 // fold them.
947 bool UntieRegs = MI->getOpcode() == TargetOpcode::STATEPOINT;
948
949 // Spill subregs if the target allows it.
950 // We always want to spill subregs for stackmap/patchpoint pseudos.
951 bool SpillSubRegs = TII.isSubregFoldable() ||
952 MI->getOpcode() == TargetOpcode::STATEPOINT ||
953 MI->getOpcode() == TargetOpcode::PATCHPOINT ||
954 MI->getOpcode() == TargetOpcode::STACKMAP;
955
956 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
957 // operands.
959 for (const auto &OpPair : Ops) {
960 unsigned Idx = OpPair.second;
961 assert(MI == OpPair.first && "Instruction conflict during operand folding");
962 MachineOperand &MO = MI->getOperand(Idx);
963
964 // No point restoring an undef read, and we'll produce an invalid live
965 // interval.
966 // TODO: Is this really the correct way to handle undef tied uses?
967 if (MO.isUse() && !MO.readsReg() && !MO.isTied())
968 continue;
969
970 if (MO.isImplicit()) {
971 ImpReg = MO.getReg();
972 continue;
973 }
974
975 if (!SpillSubRegs && MO.getSubReg())
976 return false;
977 // We cannot fold a load instruction into a def.
978 if (LoadMI && MO.isDef())
979 return false;
980 // Tied use operands should not be passed to foldMemoryOperand.
981 if (UntieRegs || !MI->isRegTiedToDefOperand(Idx))
982 FoldOps.push_back(Idx);
983 }
984
985 // If we only have implicit uses, we won't be able to fold that.
986 // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
987 if (FoldOps.empty())
988 return false;
989
990 MachineInstrSpan MIS(MI, MI->getParent());
991
993 if (UntieRegs)
994 for (unsigned Idx : FoldOps) {
995 MachineOperand &MO = MI->getOperand(Idx);
996 if (!MO.isTied())
997 continue;
998 unsigned Tied = MI->findTiedOperandIdx(Idx);
999 if (MO.isUse())
1000 TiedOps.emplace_back(Tied, Idx);
1001 else {
1002 assert(MO.isDef() && "Tied to not use and def?");
1003 TiedOps.emplace_back(Idx, Tied);
1004 }
1005 MI->untieRegOperand(Idx);
1006 }
1007
1008 MachineInstr *FoldMI =
1009 LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
1010 : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);
1011 if (!FoldMI) {
1012 // Re-tie operands.
1013 for (auto Tied : TiedOps)
1014 MI->tieOperands(Tied.first, Tied.second);
1015 return false;
1016 }
1017
1018 // Remove LIS for any dead defs in the original MI not in FoldMI.
1019 for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
1020 if (!MO->isReg())
1021 continue;
1022 Register Reg = MO->getReg();
1023 if (!Reg || Reg.isVirtual() || MRI.isReserved(Reg)) {
1024 continue;
1025 }
1026 // Skip non-Defs, including undef uses and internal reads.
1027 if (MO->isUse())
1028 continue;
1029 PhysRegInfo RI = AnalyzePhysRegInBundle(*FoldMI, Reg, &TRI);
1030 if (RI.FullyDefined)
1031 continue;
1032 // FoldMI does not define this physreg. Remove the LI segment.
1033 assert(MO->isDead() && "Cannot fold physreg def");
1034 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
1035 LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);
1036 }
1037
1038 int FI;
1039 if (TII.isStoreToStackSlot(*MI, FI) &&
1040 HSpiller.rmFromMergeableSpills(*MI, FI))
1041 --NumSpills;
1042 LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
1043 // Update the call info.
1044 if (MI->isCandidateForAdditionalCallInfo())
1045 MI->getMF()->moveAdditionalCallInfo(MI, FoldMI);
1046
1047 // If we've folded a store into an instruction labelled with debug-info,
1048 // record a substitution from the old operand to the memory operand. Handle
1049 // the simple common case where operand 0 is the one being folded, plus when
1050 // the destination operand is also a tied def. More values could be
1051 // substituted / preserved with more analysis.
1052 if (MI->peekDebugInstrNum() && Ops[0].second == 0) {
1053 // Helper lambda.
1054 auto MakeSubstitution = [this,FoldMI,MI,&Ops]() {
1055 // Substitute old operand zero to the new instructions memory operand.
1056 unsigned OldOperandNum = Ops[0].second;
1057 unsigned NewNum = FoldMI->getDebugInstrNum();
1058 unsigned OldNum = MI->getDebugInstrNum();
1059 MF.makeDebugValueSubstitution({OldNum, OldOperandNum},
1061 };
1062
1063 const MachineOperand &Op0 = MI->getOperand(Ops[0].second);
1064 if (Ops.size() == 1 && Op0.isDef()) {
1065 MakeSubstitution();
1066 } else if (Ops.size() == 2 && Op0.isDef() && MI->getOperand(1).isTied() &&
1067 Op0.getReg() == MI->getOperand(1).getReg()) {
1068 MakeSubstitution();
1069 }
1070 } else if (MI->peekDebugInstrNum()) {
1071 // This is a debug-labelled instruction, but the operand being folded isn't
1072 // at operand zero. Most likely this means it's a load being folded in.
1073 // Substitute any register defs from operand zero up to the one being
1074 // folded -- past that point, we don't know what the new operand indexes
1075 // will be.
1076 MF.substituteDebugValuesForInst(*MI, *FoldMI, Ops[0].second);
1077 }
1078
1079 MI->eraseFromParent();
1080
1081 // Insert any new instructions other than FoldMI into the LIS maps.
1082 assert(!MIS.empty() && "Unexpected empty span of instructions!");
1083 for (MachineInstr &MI : MIS)
1084 if (&MI != FoldMI)
1086
1087 // TII.foldMemoryOperand may have left some implicit operands on the
1088 // instruction. Strip them.
1089 if (ImpReg)
1090 for (unsigned i = FoldMI->getNumOperands(); i; --i) {
1091 MachineOperand &MO = FoldMI->getOperand(i - 1);
1092 if (!MO.isReg() || !MO.isImplicit())
1093 break;
1094 if (MO.getReg() == ImpReg)
1095 FoldMI->removeOperand(i - 1);
1096 }
1097
1098 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,
1099 "folded"));
1100
1101 if (!WasCopy)
1102 ++NumFolded;
1103 else if (Ops.front().second == 0) {
1104 ++NumSpills;
1105 // If there is only 1 store instruction is required for spill, add it
1106 // to mergeable list. In X86 AMX, 2 intructions are required to store.
1107 // We disable the merge for this case.
1108 if (std::distance(MIS.begin(), MIS.end()) <= 1)
1109 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
1110 } else
1111 ++NumReloads;
1112 return true;
1113}
1114
1115void InlineSpiller::insertReload(Register NewVReg,
1116 SlotIndex Idx,
1118 MachineBasicBlock &MBB = *MI->getParent();
1119
1120 MachineInstrSpan MIS(MI, &MBB);
1121 TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
1122 MRI.getRegClass(NewVReg), &TRI, Register());
1123
1124 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
1125
1126 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",
1127 NewVReg));
1128 ++NumReloads;
1129}
1130
1131/// Check if \p Def fully defines a VReg with an undefined value.
1132/// If that's the case, that means the value of VReg is actually
1133/// not relevant.
1134static bool isRealSpill(const MachineInstr &Def) {
1135 if (!Def.isImplicitDef())
1136 return true;
1137
1138 // We can say that the VReg defined by Def is undef, only if it is
1139 // fully defined by Def. Otherwise, some of the lanes may not be
1140 // undef and the value of the VReg matters.
1141 return Def.getOperand(0).getSubReg();
1142}
1143
1144/// insertSpill - Insert a spill of NewVReg after MI.
1145void InlineSpiller::insertSpill(Register NewVReg, bool isKill,
1147 // Spill are not terminators, so inserting spills after terminators will
1148 // violate invariants in MachineVerifier.
1149 assert(!MI->isTerminator() && "Inserting a spill after a terminator");
1150 MachineBasicBlock &MBB = *MI->getParent();
1151
1152 MachineInstrSpan MIS(MI, &MBB);
1153 MachineBasicBlock::iterator SpillBefore = std::next(MI);
1154 bool IsRealSpill = isRealSpill(*MI);
1155
1156 if (IsRealSpill)
1157 TII.storeRegToStackSlot(MBB, SpillBefore, NewVReg, isKill, StackSlot,
1158 MRI.getRegClass(NewVReg), &TRI, Register());
1159 else
1160 // Don't spill undef value.
1161 // Anything works for undef, in particular keeping the memory
1162 // uninitialized is a viable option and it saves code size and
1163 // run time.
1164 BuildMI(MBB, SpillBefore, MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
1165 .addReg(NewVReg, getKillRegState(isKill));
1166
1168 LIS.InsertMachineInstrRangeInMaps(Spill, MIS.end());
1169 for (const MachineInstr &MI : make_range(Spill, MIS.end()))
1170 getVDefInterval(MI, LIS);
1171
1172 LLVM_DEBUG(
1173 dumpMachineInstrRangeWithSlotIndex(Spill, MIS.end(), LIS, "spill"));
1174 ++NumSpills;
1175 // If there is only 1 store instruction is required for spill, add it
1176 // to mergeable list. In X86 AMX, 2 intructions are required to store.
1177 // We disable the merge for this case.
1178 if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)
1179 HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);
1180}
1181
1182/// spillAroundUses - insert spill code around each use of Reg.
1183void InlineSpiller::spillAroundUses(Register Reg) {
1184 LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n');
1185 LiveInterval &OldLI = LIS.getInterval(Reg);
1186
1187 // Iterate over instructions using Reg.
1188 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {
1189 // Debug values are not allowed to affect codegen.
1190 if (MI.isDebugValue()) {
1191 // Modify DBG_VALUE now that the value is in a spill slot.
1192 MachineBasicBlock *MBB = MI.getParent();
1193 LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << MI);
1194 buildDbgValueForSpill(*MBB, &MI, MI, StackSlot, Reg);
1195 MBB->erase(MI);
1196 continue;
1197 }
1198
1199 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "
1200 "instruction that isn't a DBG_VALUE");
1201
1202 // Ignore copies to/from snippets. We'll delete them.
1203 if (SnippetCopies.count(&MI))
1204 continue;
1205
1206 // Stack slot accesses may coalesce away.
1207 if (coalesceStackAccess(&MI, Reg))
1208 continue;
1209
1210 // Analyze instruction.
1213
1214 // Find the slot index where this instruction reads and writes OldLI.
1215 // This is usually the def slot, except for tied early clobbers.
1217 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
1218 if (SlotIndex::isSameInstr(Idx, VNI->def))
1219 Idx = VNI->def;
1220
1221 // Check for a sibling copy.
1222 Register SibReg = isCopyOfBundle(MI, Reg, TII);
1223 if (SibReg && isSibling(SibReg)) {
1224 // This may actually be a copy between snippets.
1225 if (isRegToSpill(SibReg)) {
1226 LLVM_DEBUG(dbgs() << "Found new snippet copy: " << MI);
1227 SnippetCopies.insert(&MI);
1228 continue;
1229 }
1230 if (RI.Writes) {
1231 if (hoistSpillInsideBB(OldLI, MI)) {
1232 // This COPY is now dead, the value is already in the stack slot.
1233 MI.getOperand(0).setIsDead();
1234 DeadDefs.push_back(&MI);
1235 continue;
1236 }
1237 } else {
1238 // This is a reload for a sib-reg copy. Drop spills downstream.
1239 LiveInterval &SibLI = LIS.getInterval(SibReg);
1240 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
1241 // The COPY will fold to a reload below.
1242 }
1243 }
1244
1245 // Attempt to fold memory ops.
1246 if (foldMemoryOperand(Ops))
1247 continue;
1248
1249 // Create a new virtual register for spill/fill.
1250 // FIXME: Infer regclass from instruction alone.
1251 Register NewVReg = Edit->createFrom(Reg);
1252
1253 if (RI.Reads)
1254 insertReload(NewVReg, Idx, &MI);
1255
1256 // Rewrite instruction operands.
1257 bool hasLiveDef = false;
1258 for (const auto &OpPair : Ops) {
1259 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
1260 MO.setReg(NewVReg);
1261 if (MO.isUse()) {
1262 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1263 MO.setIsKill();
1264 } else {
1265 if (!MO.isDead())
1266 hasLiveDef = true;
1267 }
1268 }
1269 LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << MI << '\n');
1270
1271 // FIXME: Use a second vreg if instruction has no tied ops.
1272 if (RI.Writes)
1273 if (hasLiveDef)
1274 insertSpill(NewVReg, true, &MI);
1275 }
1276}
1277
1278/// spillAll - Spill all registers remaining after rematerialization.
1279void InlineSpiller::spillAll() {
1280 // Update LiveStacks now that we are committed to spilling.
1281 if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
1282 StackSlot = VRM.assignVirt2StackSlot(Original);
1283 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
1284 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
1285 } else
1286 StackInt = &LSS.getInterval(StackSlot);
1287
1288 if (Original != Edit->getReg())
1289 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1290
1291 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
1292 for (Register Reg : RegsToSpill)
1293 StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
1294 StackInt->getValNumInfo(0));
1295 LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
1296
1297 // Spill around uses of all RegsToSpill.
1298 for (Register Reg : RegsToSpill) {
1299 spillAroundUses(Reg);
1300 // Assign all of the spilled registers to the slot so that
1301 // LiveDebugVariables knows about these locations later on.
1302 if (VRM.getStackSlot(Reg) == VirtRegMap::NO_STACK_SLOT)
1303 VRM.assignVirt2StackSlot(Reg, StackSlot);
1304 }
1305
1306 // Hoisted spills may cause dead code.
1307 if (!DeadDefs.empty()) {
1308 LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
1309 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);
1310 }
1311
1312 // Finally delete the SnippetCopies.
1313 for (Register Reg : RegsToSpill) {
1314 for (MachineInstr &MI :
1315 llvm::make_early_inc_range(MRI.reg_instructions(Reg))) {
1316 assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy");
1317 // FIXME: Do this with a LiveRangeEdit callback.
1319 MI.eraseFromBundle();
1320 }
1321 }
1322
1323 // Delete all spilled registers.
1324 for (Register Reg : RegsToSpill)
1325 Edit->eraseVirtReg(Reg);
1326}
1327
1328void InlineSpiller::spill(LiveRangeEdit &edit, AllocationOrder *order) {
1329 ++NumSpilledRanges;
1330 Edit = &edit;
1331 Order = order;
1332 assert(!edit.getReg().isStack() && "Trying to spill a stack slot.");
1333 // Share a stack slot among all descendants of Original.
1334 Original = VRM.getOriginal(edit.getReg());
1335 StackSlot = VRM.getStackSlot(Original);
1336 StackInt = nullptr;
1337
1338 LLVM_DEBUG(dbgs() << "Inline spilling "
1339 << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))
1340 << ':' << edit.getParent() << "\nFrom original "
1341 << printReg(Original) << '\n');
1342 assert(edit.getParent().isSpillable() &&
1343 "Attempting to spill already spilled value.");
1344 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
1345
1346 collectRegsToSpill();
1347 reMaterializeAll();
1348
1349 // Remat may handle everything.
1350 if (!RegsToSpill.empty())
1351 spillAll();
1352
1353 Edit->calculateRegClassAndHint(MF, VRAI);
1354}
1355
1356/// Optimizations after all the reg selections and spills are done.
1357void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1358
1359/// When a spill is inserted, add the spill to MergeableSpills map.
1360void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
1361 Register Original) {
1363 LiveInterval &OrigLI = LIS.getInterval(Original);
1364 // save a copy of LiveInterval in StackSlotToOrigLI because the original
1365 // LiveInterval may be cleared after all its references are spilled.
1366
1367 auto [Place, Inserted] = StackSlotToOrigLI.try_emplace(StackSlot);
1368 if (Inserted) {
1369 auto LI = std::make_unique<LiveInterval>(OrigLI.reg(), OrigLI.weight());
1370 LI->assign(OrigLI, Allocator);
1371 Place->second = std::move(LI);
1372 }
1373
1374 SlotIndex Idx = LIS.getInstructionIndex(Spill);
1375 VNInfo *OrigVNI = Place->second->getVNInfoAt(Idx.getRegSlot());
1376 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1377 MergeableSpills[MIdx].insert(&Spill);
1378}
1379
1380/// When a spill is removed, remove the spill from MergeableSpills map.
1381/// Return true if the spill is removed successfully.
1382bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
1383 int StackSlot) {
1384 auto It = StackSlotToOrigLI.find(StackSlot);
1385 if (It == StackSlotToOrigLI.end())
1386 return false;
1387 SlotIndex Idx = LIS.getInstructionIndex(Spill);
1388 VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
1389 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1390 return MergeableSpills[MIdx].erase(&Spill);
1391}
1392
1393/// Check BB to see if it is a possible target BB to place a hoisted spill,
1394/// i.e., there should be a living sibling of OrigReg at the insert point.
1395bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
1396 MachineBasicBlock &BB, Register &LiveReg) {
1397 SlotIndex Idx = IPA.getLastInsertPoint(OrigLI, BB);
1398 // The original def could be after the last insert point in the root block,
1399 // we can't hoist to here.
1400 if (Idx < OrigVNI.def) {
1401 // TODO: We could be better here. If LI is not alive in landing pad
1402 // we could hoist spill after LIP.
1403 LLVM_DEBUG(dbgs() << "can't spill in root block - def after LIP\n");
1404 return false;
1405 }
1406 Register OrigReg = OrigLI.reg();
1407 SmallSetVector<Register, 16> &Siblings = Virt2SiblingsMap[OrigReg];
1408 assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI");
1409
1410 for (const Register &SibReg : Siblings) {
1411 LiveInterval &LI = LIS.getInterval(SibReg);
1412 VNInfo *VNI = LI.getVNInfoAt(Idx);
1413 if (VNI) {
1414 LiveReg = SibReg;
1415 return true;
1416 }
1417 }
1418 return false;
1419}
1420
1421/// Remove redundant spills in the same BB. Save those redundant spills in
1422/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1423void HoistSpillHelper::rmRedundantSpills(
1427 // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1428 // another spill inside. If a BB contains more than one spill, only keep the
1429 // earlier spill with smaller SlotIndex.
1430 for (auto *const CurrentSpill : Spills) {
1431 MachineBasicBlock *Block = CurrentSpill->getParent();
1432 MachineDomTreeNode *Node = MDT.getNode(Block);
1433 MachineInstr *PrevSpill = SpillBBToSpill[Node];
1434 if (PrevSpill) {
1435 SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
1436 SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
1437 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1438 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1439 SpillsToRm.push_back(SpillToRm);
1440 SpillBBToSpill[MDT.getNode(Block)] = SpillToKeep;
1441 } else {
1442 SpillBBToSpill[MDT.getNode(Block)] = CurrentSpill;
1443 }
1444 }
1445 for (auto *const SpillToRm : SpillsToRm)
1446 Spills.erase(SpillToRm);
1447}
1448
1449/// Starting from \p Root find a top-down traversal order of the dominator
1450/// tree to visit all basic blocks containing the elements of \p Spills.
1451/// Redundant spills will be found and put into \p SpillsToRm at the same
1452/// time. \p SpillBBToSpill will be populated as part of the process and
1453/// maps a basic block to the first store occurring in the basic block.
1454/// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1455void HoistSpillHelper::getVisitOrders(
1461 // The set contains all the possible BB nodes to which we may hoist
1462 // original spills.
1464 // Save the BB nodes on the path from the first BB node containing
1465 // non-redundant spill to the Root node.
1467 // All the spills to be hoisted must originate from a single def instruction
1468 // to the OrigReg. It means the def instruction should dominate all the spills
1469 // to be hoisted. We choose the BB where the def instruction is located as
1470 // the Root.
1471 MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
1472 // For every node on the dominator tree with spill, walk up on the dominator
1473 // tree towards the Root node until it is reached. If there is other node
1474 // containing spill in the middle of the path, the previous spill saw will
1475 // be redundant and the node containing it will be removed. All the nodes on
1476 // the path starting from the first node with non-redundant spill to the Root
1477 // node will be added to the WorkSet, which will contain all the possible
1478 // locations where spills may be hoisted to after the loop below is done.
1479 for (auto *const Spill : Spills) {
1480 MachineBasicBlock *Block = Spill->getParent();
1482 MachineInstr *SpillToRm = nullptr;
1483 while (Node != RootIDomNode) {
1484 // If Node dominates Block, and it already contains a spill, the spill in
1485 // Block will be redundant.
1486 if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1487 SpillToRm = SpillBBToSpill[MDT[Block]];
1488 break;
1489 /// If we see the Node already in WorkSet, the path from the Node to
1490 /// the Root node must already be traversed by another spill.
1491 /// Then no need to repeat.
1492 } else if (WorkSet.count(Node)) {
1493 break;
1494 } else {
1495 NodesOnPath.insert(Node);
1496 }
1497 Node = Node->getIDom();
1498 }
1499 if (SpillToRm) {
1500 SpillsToRm.push_back(SpillToRm);
1501 } else {
1502 // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1503 // set the initial status before hoisting start. The value of BBs
1504 // containing original spills is set to 0, in order to descriminate
1505 // with BBs containing hoisted spills which will be inserted to
1506 // SpillsToKeep later during hoisting.
1507 SpillsToKeep[MDT[Block]] = Register();
1508 WorkSet.insert_range(NodesOnPath);
1509 }
1510 NodesOnPath.clear();
1511 }
1512
1513 // Sort the nodes in WorkSet in top-down order and save the nodes
1514 // in Orders. Orders will be used for hoisting in runHoistSpills.
1515 unsigned idx = 0;
1516 Orders.push_back(MDT.getNode(Root));
1517 do {
1518 MachineDomTreeNode *Node = Orders[idx++];
1519 for (MachineDomTreeNode *Child : Node->children()) {
1520 if (WorkSet.count(Child))
1521 Orders.push_back(Child);
1522 }
1523 } while (idx != Orders.size());
1524 assert(Orders.size() == WorkSet.size() &&
1525 "Orders have different size with WorkSet");
1526
1527#ifndef NDEBUG
1528 LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");
1530 for (; RIt != Orders.rend(); RIt++)
1531 LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");
1532 LLVM_DEBUG(dbgs() << "\n");
1533#endif
1534}
1535
1536/// Try to hoist spills according to BB hotness. The spills to removed will
1537/// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1538/// \p SpillsToIns.
1539void HoistSpillHelper::runHoistSpills(
1540 LiveInterval &OrigLI, VNInfo &OrigVNI,
1544 // Visit order of dominator tree nodes.
1546 // SpillsToKeep contains all the nodes where spills are to be inserted
1547 // during hoisting. If the spill to be inserted is an original spill
1548 // (not a hoisted one), the value of the map entry is 0. If the spill
1549 // is a hoisted spill, the value of the map entry is the VReg to be used
1550 // as the source of the spill.
1552 // Map from BB to the first spill inside of it.
1554
1555 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1556
1557 MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
1558 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1559 SpillBBToSpill);
1560
1561 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1562 // nodes set and the cost of all the spills inside those nodes.
1563 // The nodes set are the locations where spills are to be inserted
1564 // in the subtree of current node.
1565 using NodesCostPair =
1566 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
1568
1569 // Iterate Orders set in reverse order, which will be a bottom-up order
1570 // in the dominator tree. Once we visit a dom tree node, we know its
1571 // children have already been visited and the spill locations in the
1572 // subtrees of all the children have been determined.
1574 for (; RIt != Orders.rend(); RIt++) {
1575 MachineBasicBlock *Block = (*RIt)->getBlock();
1576
1577 // If Block contains an original spill, simply continue.
1578 if (auto It = SpillsToKeep.find(*RIt);
1579 It != SpillsToKeep.end() && !It->second) {
1580 auto &SIt = SpillsInSubTreeMap[*RIt];
1581 SIt.first.insert(*RIt);
1582 // Sit.second contains the cost of spill.
1583 SIt.second = MBFI.getBlockFreq(Block);
1584 continue;
1585 }
1586
1587 // Collect spills in subtree of current node (*RIt) to
1588 // SpillsInSubTreeMap[*RIt].first.
1589 for (MachineDomTreeNode *Child : (*RIt)->children()) {
1590 if (!SpillsInSubTreeMap.contains(Child))
1591 continue;
1592 // The stmt:
1593 // "auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt]"
1594 // below should be placed before getting the begin and end iterators of
1595 // SpillsInSubTreeMap[Child].first, or else the iterators may be
1596 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1597 // and the map grows and then the original buckets in the map are moved.
1598 auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt];
1599 auto ChildIt = SpillsInSubTreeMap.find(Child);
1600 SubTreeCost += ChildIt->second.second;
1601 auto BI = ChildIt->second.first.begin();
1602 auto EI = ChildIt->second.first.end();
1603 SpillsInSubTree.insert(BI, EI);
1604 SpillsInSubTreeMap.erase(ChildIt);
1605 }
1606
1607 auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt];
1608 // No spills in subtree, simply continue.
1609 if (SpillsInSubTree.empty())
1610 continue;
1611
1612 // Check whether Block is a possible candidate to insert spill.
1613 Register LiveReg;
1614 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1615 continue;
1616
1617 // If there are multiple spills that could be merged, bias a little
1618 // to hoist the spill.
1619 BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
1620 ? BranchProbability(9, 10)
1621 : BranchProbability(1, 1);
1622 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1623 // Hoist: Move spills to current Block.
1624 for (auto *const SpillBB : SpillsInSubTree) {
1625 // When SpillBB is a BB contains original spill, insert the spill
1626 // to SpillsToRm.
1627 if (auto It = SpillsToKeep.find(SpillBB);
1628 It != SpillsToKeep.end() && !It->second) {
1629 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1630 SpillsToRm.push_back(SpillToRm);
1631 }
1632 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1633 SpillsToKeep.erase(SpillBB);
1634 }
1635 // Current Block is the BB containing the new hoisted spill. Add it to
1636 // SpillsToKeep. LiveReg is the source of the new spill.
1637 SpillsToKeep[*RIt] = LiveReg;
1638 LLVM_DEBUG({
1639 dbgs() << "spills in BB: ";
1640 for (const auto Rspill : SpillsInSubTree)
1641 dbgs() << Rspill->getBlock()->getNumber() << " ";
1642 dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()
1643 << "\n";
1644 });
1645 SpillsInSubTree.clear();
1646 SpillsInSubTree.insert(*RIt);
1647 SubTreeCost = MBFI.getBlockFreq(Block);
1648 }
1649 }
1650 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1651 // save them to SpillsToIns.
1652 for (const auto &Ent : SpillsToKeep) {
1653 if (Ent.second)
1654 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1655 }
1656}
1657
1658/// For spills with equal values, remove redundant spills and hoist those left
1659/// to less hot spots.
1660///
1661/// Spills with equal values will be collected into the same set in
1662/// MergeableSpills when spill is inserted. These equal spills are originated
1663/// from the same defining instruction and are dominated by the instruction.
1664/// Before hoisting all the equal spills, redundant spills inside in the same
1665/// BB are first marked to be deleted. Then starting from the spills left, walk
1666/// up on the dominator tree towards the Root node where the define instruction
1667/// is located, mark the dominated spills to be deleted along the way and
1668/// collect the BB nodes on the path from non-dominated spills to the define
1669/// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1670/// where we are considering to hoist the spills. We iterate the WorkSet in
1671/// bottom-up order, and for each node, we will decide whether to hoist spills
1672/// inside its subtree to that node. In this way, we can get benefit locally
1673/// even if hoisting all the equal spills to one cold place is impossible.
1674void HoistSpillHelper::hoistAllSpills() {
1675 SmallVector<Register, 4> NewVRegs;
1676 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1677
1678 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
1680 Register Original = VRM.getPreSplitReg(Reg);
1681 if (!MRI.def_empty(Reg) && Original.isValid())
1682 Virt2SiblingsMap[Original].insert(Reg);
1683 }
1684
1685 // Each entry in MergeableSpills contains a spill set with equal values.
1686 for (auto &Ent : MergeableSpills) {
1687 int Slot = Ent.first.first;
1688 LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
1689 VNInfo *OrigVNI = Ent.first.second;
1690 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1691 if (Ent.second.empty())
1692 continue;
1693
1694 LLVM_DEBUG({
1695 dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
1696 << "Equal spills in BB: ";
1697 for (const auto spill : EqValSpills)
1698 dbgs() << spill->getParent()->getNumber() << " ";
1699 dbgs() << "\n";
1700 });
1701
1702 // SpillsToRm is the spill set to be removed from EqValSpills.
1704 // SpillsToIns is the spill set to be newly inserted after hoisting.
1706
1707 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1708
1709 LLVM_DEBUG({
1710 dbgs() << "Finally inserted spills in BB: ";
1711 for (const auto &Ispill : SpillsToIns)
1712 dbgs() << Ispill.first->getNumber() << " ";
1713 dbgs() << "\nFinally removed spills in BB: ";
1714 for (const auto Rspill : SpillsToRm)
1715 dbgs() << Rspill->getParent()->getNumber() << " ";
1716 dbgs() << "\n";
1717 });
1718
1719 // Stack live range update.
1720 LiveInterval &StackIntvl = LSS.getInterval(Slot);
1721 if (!SpillsToIns.empty() || !SpillsToRm.empty())
1722 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1723 StackIntvl.getValNumInfo(0));
1724
1725 // Insert hoisted spills.
1726 for (auto const &Insert : SpillsToIns) {
1727 MachineBasicBlock *BB = Insert.first;
1728 Register LiveReg = Insert.second;
1729 MachineBasicBlock::iterator MII = IPA.getLastInsertPointIter(OrigLI, *BB);
1730 MachineInstrSpan MIS(MII, BB);
1731 TII.storeRegToStackSlot(*BB, MII, LiveReg, false, Slot,
1732 MRI.getRegClass(LiveReg), &TRI, Register());
1733 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
1734 for (const MachineInstr &MI : make_range(MIS.begin(), MII))
1735 getVDefInterval(MI, LIS);
1736 ++NumSpills;
1737 }
1738
1739 // Remove redundant spills or change them to dead instructions.
1740 NumSpills -= SpillsToRm.size();
1741 for (auto *const RMEnt : SpillsToRm) {
1742 RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1743 for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1744 MachineOperand &MO = RMEnt->getOperand(i - 1);
1745 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1746 RMEnt->removeOperand(i - 1);
1747 }
1748 }
1749 Edit.eliminateDeadDefs(SpillsToRm, {});
1750 }
1751}
1752
1753/// For VirtReg clone, the \p New register should have the same physreg or
1754/// stackslot as the \p old register.
1755void HoistSpillHelper::LRE_DidCloneVirtReg(Register New, Register Old) {
1756 if (VRM.hasPhys(Old))
1757 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1758 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1759 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1760 else
1761 llvm_unreachable("VReg should be assigned either physreg or stackslot");
1762 if (VRM.hasShape(Old))
1763 VRM.assignVirt2Shape(New, VRM.getShape(Old));
1764}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
This file defines the DenseMap class.
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
static LLVM_DUMP_METHOD void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E, LiveIntervals const &LIS, const char *const header, Register VReg=Register())
static Register isCopyOfBundle(const MachineInstr &FirstMI, Register Reg, const TargetInstrInfo &TII)
Check for a copy bundle as formed by SplitKit.
static bool isRealSpill(const MachineInstr &Def)
Check if Def fully defines a VReg with an undefined value.
static cl::opt< bool > RestrictStatepointRemat("restrict-statepoint-remat", cl::init(false), cl::Hidden, cl::desc("Restrict remat for statepoint operands"))
static Register isCopyOf(const MachineInstr &MI, Register Reg, const TargetInstrInfo &TII)
isFullCopyOf - If MI is a COPY to or from Reg, return the other register, otherwise return 0.
static void getVDefInterval(const MachineInstr &MI, LiveIntervals &LIS)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Live Register Matrix
#define I(x, y, z)
Definition MD5.cpp:58
Register Reg
Register const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
Promote Memory to Register
Definition Mem2Reg.cpp:110
#define P(N)
Basic Register Allocator
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:167
bool erase(const KeyT &Val)
Definition DenseMap.h:311
iterator end()
Definition DenseMap.h:81
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition DenseMap.h:158
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:222
Register getReg() const
Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg, MachineInstr::MIFlag Flags=MachineInstr::NoFlags) const override
Store the specified register of the given register class to the specified stack frame index.
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg, MachineInstr::MIFlag Flags=MachineInstr::NoFlags) const override
Load the specified register of the given register class from the specified stack frame index.
Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
Determines the latest safe point in a block in which we can insert a split, spill or other instructio...
Definition SplitKit.h:50
LiveInterval - This class represents the liveness of a register, or stack slot.
float weight() const
Register reg() const
bool isSpillable() const
isSpillable - Can this interval be spilled?
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
VNInfo::Allocator & getVNInfoAllocator()
LiveInterval & getInterval(Register Reg)
void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E)
LLVM_ABI void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
Result of a LiveRange query.
bool isKill() const
Return true if the live-in value is killed by this instruction.
Callback methods for LiveRangeEdit owners.
const LiveInterval & getParent() const
Register getReg() const
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
LLVM_ABI void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)
MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the...
iterator_range< vni_iterator > vnis()
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...
unsigned getNumValNums() const
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
MIBundleOperands - Iterate over all operands in a bundle of machine instructions.
LLVM_ABI iterator SkipPHIsLabelsAndDebug(iterator I, Register Reg=Register(), bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
Instructions::iterator instr_iterator
Instructions::const_iterator const_instr_iterator
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
static const unsigned int DebugOperandMemNumber
A reserved operand number representing the instructions memory operand, for instructions that have a ...
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
MachineInstrSpan provides an interface to get an iteration range containing the instruction it was in...
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
bool isBundledWithPred() const
Return true if this instruction is part of a bundle, and it is not the first instruction in the bundl...
LLVM_ABI void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
bool isBundledWithSucc() const
Return true if this instruction is part of a bundle, and it is not the last instruction in the bundle...
LLVM_ABI unsigned getDebugInstrNum()
Fetch the instruction number of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
bool isBundled() const
Return true if this instruction part of a bundle.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
void setIsUndef(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
defusechain_instr_iterator< true, true, true, false > reg_bundle_nodbg_iterator
reg_bundle_nodbg_iterator/reg_bundle_nodbg_begin/reg_bundle_nodbg_end - Walk all defs and uses of the...
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:36
Wrapper class representing virtual and physical registers.
Definition Register.h:19
constexpr bool isStack() const
Return true if this is a stack slot.
Definition Register.h:43
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition Register.h:67
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition Register.h:102
constexpr bool isValid() const
Definition Register.h:107
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:74
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:66
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
LLVM_ABI void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
size_type size() const
Definition SmallPtrSet.h:99
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:338
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
std::reverse_iterator< iterator > reverse_iterator
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Spiller interface.
Definition Spiller.h:33
virtual ~Spiller()=0
Register getReg() const
MI-level Statepoint operands.
Definition StackMaps.h:159
LLVM_ABI bool isFoldableReg(Register Reg) const
Return true if Reg is used only in operands which can be folded to stack usage.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
static constexpr int NO_STACK_SLOT
Definition VirtRegMap.h:66
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI PhysRegInfo AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg, const TargetRegisterInfo *TRI)
AnalyzePhysRegInBundle - Analyze how the current instruction or bundle uses a physical register.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:632
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:383
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI VirtRegInfo AnalyzeVirtRegInBundle(MachineInstr &MI, Register Reg, SmallVectorImpl< std::pair< MachineInstr *, unsigned > > *Ops=nullptr)
AnalyzeVirtRegInBundle - Analyze how the current instruction or bundle uses a virtual register.
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
unsigned getKillRegState(bool B)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition MCRegister.h:21
Spiller * createInlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix=nullptr)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex, Register SpillReg)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1897
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Remat - Information needed to rematerialize at a specific location.
Information about how a physical register Reg is used by a set of operands.
bool FullyDefined
Reg or a super-register is defined.
VirtRegInfo - Information about a virtual register used by a set of operands.
bool Reads
Reads - One of the operands read the virtual register.
bool Tied
Tied - Uses and defs must use the same register.
bool Writes
Writes - One of the operands writes the virtual register.