1//===- MachineSink.cpp - Sinking for machine instructions -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass moves instructions into successor blocks when possible, so that
10// they aren't executed on paths where their results aren't needed.
11//
12// This pass is not intended to be a replacement or a complete alternative
13// for an LLVM-IR-level sinking pass. It is only designed to sink simple
14// constructs that are not exposed before lowering and instruction selection.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/MachineSink.h"
19#include "llvm/ADT/DenseSet.h"
20#include "llvm/ADT/DepthFirstIterator.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/PointerIntPair.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/Analysis/CFG.h"
29#include "llvm/Analysis/ProfileSummaryInfo.h"
30#include "llvm/CodeGen/LiveIntervals.h"
31#include "llvm/CodeGen/MachineBasicBlock.h"
32#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
33#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
34#include "llvm/CodeGen/MachineCycleAnalysis.h"
35#include "llvm/CodeGen/MachineDomTreeUpdater.h"
36#include "llvm/CodeGen/MachineDominators.h"
37#include "llvm/CodeGen/MachineFunction.h"
38#include "llvm/CodeGen/MachineFunctionPass.h"
39#include "llvm/CodeGen/MachineInstr.h"
40#include "llvm/CodeGen/MachineLoopInfo.h"
41#include "llvm/CodeGen/MachineOperand.h"
42#include "llvm/CodeGen/MachinePostDominators.h"
43#include "llvm/CodeGen/MachineRegisterInfo.h"
44#include "llvm/CodeGen/MachineSizeOpts.h"
45#include "llvm/CodeGen/PostRAMachineSink.h"
46#include "llvm/CodeGen/RegisterClassInfo.h"
47#include "llvm/CodeGen/RegisterPressure.h"
48#include "llvm/CodeGen/SlotIndexes.h"
49#include "llvm/CodeGen/TargetInstrInfo.h"
50#include "llvm/CodeGen/TargetPassConfig.h"
51#include "llvm/CodeGen/TargetRegisterInfo.h"
52#include "llvm/CodeGen/TargetSchedule.h"
53#include "llvm/CodeGen/TargetSubtargetInfo.h"
54#include "llvm/IR/BasicBlock.h"
55#include "llvm/IR/DebugInfoMetadata.h"
56#include "llvm/IR/LLVMContext.h"
57#include "llvm/InitializePasses.h"
58#include "llvm/Pass.h"
59#include "llvm/Support/BranchProbability.h"
60#include "llvm/Support/CommandLine.h"
61#include "llvm/Support/Debug.h"
62#include "llvm/Support/raw_ostream.h"
63#include <cassert>
64#include <cstdint>
65#include <utility>
66#include <vector>
67
68using namespace llvm;
69
70#define DEBUG_TYPE "machine-sink"
71
72static cl::opt<bool>
73 SplitEdges("machine-sink-split",
74 cl::desc("Split critical edges during machine sinking"),
75 cl::init(Val: true), cl::Hidden);
76
77static cl::opt<bool> UseBlockFreqInfo(
78 "machine-sink-bfi",
79 cl::desc("Use block frequency info to find successors to sink"),
80 cl::init(Val: true), cl::Hidden);
81
82static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
83 "machine-sink-split-probability-threshold",
84 cl::desc(
85 "Percentage threshold for splitting single-instruction critical edge. "
86 "If the branch threshold is higher than this threshold, we allow "
87 "speculative execution of up to 1 instruction to avoid branching to "
88 "splitted critical edge"),
89 cl::init(Val: 40), cl::Hidden);
90
91static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold(
92 "machine-sink-load-instrs-threshold",
93 cl::desc("Do not try to find alias store for a load if there is a in-path "
94 "block whose instruction number is higher than this threshold."),
95 cl::init(Val: 2000), cl::Hidden);
96
97static cl::opt<unsigned> SinkLoadBlocksThreshold(
98 "machine-sink-load-blocks-threshold",
99 cl::desc("Do not try to find alias store for a load if the block number in "
100 "the straight line is higher than this threshold."),
101 cl::init(Val: 20), cl::Hidden);
102
103static cl::opt<bool>
104 SinkInstsIntoCycle("sink-insts-to-avoid-spills",
105 cl::desc("Sink instructions into cycles to avoid "
106 "register spills"),
107 cl::init(Val: false), cl::Hidden);
108
109static cl::opt<unsigned> SinkIntoCycleLimit(
110 "machine-sink-cycle-limit",
111 cl::desc(
112 "The maximum number of instructions considered for cycle sinking."),
113 cl::init(Val: 50), cl::Hidden);
114
115STATISTIC(NumSunk, "Number of machine instructions sunk");
116STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle");
117STATISTIC(NumSplit, "Number of critical edges split");
118STATISTIC(NumCoalesces, "Number of copies coalesced");
119STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
120
121using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
122
123namespace {
124
125class MachineSinking {
126 const TargetSubtargetInfo *STI = nullptr;
127 const TargetInstrInfo *TII = nullptr;
128 const TargetRegisterInfo *TRI = nullptr;
129 MachineRegisterInfo *MRI = nullptr; // Machine register information
130 MachineDominatorTree *DT = nullptr; // Machine dominator tree
131 MachinePostDominatorTree *PDT = nullptr; // Machine post dominator tree
132 MachineCycleInfo *CI = nullptr;
133 ProfileSummaryInfo *PSI = nullptr;
134 MachineBlockFrequencyInfo *MBFI = nullptr;
135 const MachineBranchProbabilityInfo *MBPI = nullptr;
136 AliasAnalysis *AA = nullptr;
137 RegisterClassInfo *RegClassInfo = nullptr;
138 TargetSchedModel SchedModel;
139 // Required for split critical edge
140 LiveIntervals *LIS;
141 SlotIndexes *SI;
142 MachineLoopInfo *MLI;
143
144 // Remember which edges have been considered for breaking.
145 SmallSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>, 8>
146 CEBCandidates;
147 // Memorize the register that also wanted to sink into the same block along
148 // a different critical edge.
149 // {register to sink, sink-to block} -> the first sink-from block.
150 // We're recording the first sink-from block because that (critical) edge
151 // was deferred until we see another register that's going to sink into the
152 // same block.
153 DenseMap<std::pair<Register, MachineBasicBlock *>, MachineBasicBlock *>
154 CEMergeCandidates;
155 // Remember which edges we are about to split.
156 // This is different from CEBCandidates since those edges
157 // will be split.
158 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
159
160 DenseSet<Register> RegsToClearKillFlags;
161
162 using AllSuccsCache =
163 SmallDenseMap<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
164
165 /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
166 /// post-dominated by another DBG_VALUE of the same variable location.
167 /// This is necessary to detect sequences such as:
168 /// %0 = someinst
169 /// DBG_VALUE %0, !123, !DIExpression()
170 /// %1 = anotherinst
171 /// DBG_VALUE %1, !123, !DIExpression()
172 /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
173 /// would re-order assignments.
174 using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
175
176 using SinkItem = std::pair<MachineInstr *, MachineBasicBlock *>;
177
178 /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
179 /// debug instructions to sink.
180 SmallDenseMap<Register, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
181
182 /// Record of debug variables that have had their locations set in the
183 /// current block.
184 DenseSet<DebugVariable> SeenDbgVars;
185
186 DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>
187 HasStoreCache;
188
189 DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>,
190 SmallVector<MachineInstr *>>
191 StoreInstrCache;
192
193 /// Cached BB's register pressure.
194 DenseMap<const MachineBasicBlock *, std::vector<unsigned>>
195 CachedRegisterPressure;
196
197 bool EnableSinkAndFold;
198
199public:
200 MachineSinking(bool EnableSinkAndFold, MachineDominatorTree *DT,
201 MachinePostDominatorTree *PDT, MachineLoopInfo *MLI,
202 SlotIndexes *SI, LiveIntervals *LIS, MachineCycleInfo *CI,
203 ProfileSummaryInfo *PSI, MachineBlockFrequencyInfo *MBFI,
204 const MachineBranchProbabilityInfo *MBPI, AliasAnalysis *AA,
205 RegisterClassInfo *RegClassInfo)
206 : DT(DT), PDT(PDT), CI(CI), PSI(PSI), MBFI(MBFI), MBPI(MBPI), AA(AA),
207 RegClassInfo(RegClassInfo), LIS(LIS), SI(SI), MLI(MLI),
208 EnableSinkAndFold(EnableSinkAndFold) {}
209
210 bool run(MachineFunction &MF);
211
212 void releaseMemory() {
213 CEBCandidates.clear();
214 CEMergeCandidates.clear();
215 }
216
217private:
218 bool ProcessBlock(MachineBasicBlock &MBB);
219 void ProcessDbgInst(MachineInstr &MI);
220 bool isLegalToBreakCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
221 MachineBasicBlock *To, bool BreakPHIEdge);
222 bool isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
223 MachineBasicBlock *To,
224 MachineBasicBlock *&DeferredFromBlock);
225
226 bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
227 MachineInstr &MI);
228
229 /// Postpone the splitting of the given critical
230 /// edge (\p From, \p To).
231 ///
232 /// We do not split the edges on the fly. Indeed, this invalidates
233 /// the dominance information and thus triggers a lot of updates
234 /// of that information underneath.
235 /// Instead, we postpone all the splits after each iteration of
236 /// the main loop. That way, the information is at least valid
237 /// for the lifetime of an iteration.
238 ///
239 /// \return True if the edge is marked as toSplit, false otherwise.
240 /// False can be returned if, for instance, this is not profitable.
241 bool PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
242 MachineBasicBlock *To, bool BreakPHIEdge);
243 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
244 AllSuccsCache &AllSuccessors);
245
246 /// If we sink a COPY inst, some debug users of it's destination may no
247 /// longer be dominated by the COPY, and will eventually be dropped.
248 /// This is easily rectified by forwarding the non-dominated debug uses
249 /// to the copy source.
250 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
251 MachineBasicBlock *TargetBlock);
252 bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
253 MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
254 bool &LocalUse) const;
255 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
256 bool &BreakPHIEdge,
257 AllSuccsCache &AllSuccessors);
258
259 void FindCycleSinkCandidates(CycleRef Cycle, MachineBasicBlock *BB,
260 SmallVectorImpl<MachineInstr *> &Candidates);
261
262 bool
263 aggressivelySinkIntoCycle(CycleRef Cycle, MachineInstr &I,
264 DenseMap<SinkItem, MachineInstr *> &SunkInstrs);
265
266 bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
267 MachineBasicBlock *MBB,
268 MachineBasicBlock *SuccToSinkTo,
269 AllSuccsCache &AllSuccessors);
270
271 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
272 MachineBasicBlock *MBB);
273
274 bool PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB);
275
276 SmallVector<MachineBasicBlock *, 4> &
277 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
278 AllSuccsCache &AllSuccessors) const;
279
280 std::vector<unsigned> &getBBRegisterPressure(const MachineBasicBlock &MBB,
281 bool UseCache = true);
282
283 bool registerPressureSetExceedsLimit(unsigned NRegs,
284 const TargetRegisterClass *RC,
285 const MachineBasicBlock &MBB);
286
287 bool registerPressureExceedsLimit(const MachineBasicBlock &MBB);
288};
289
290class MachineSinkingLegacy : public MachineFunctionPass {
291public:
292 static char ID;
293
294 MachineSinkingLegacy() : MachineFunctionPass(ID) {}
295
296 bool runOnMachineFunction(MachineFunction &MF) override;
297
298 void getAnalysisUsage(AnalysisUsage &AU) const override {
299 MachineFunctionPass::getAnalysisUsage(AU);
300 AU.addRequired<AAResultsWrapperPass>();
301 AU.addRequired<MachineDominatorTreeWrapperPass>();
302 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
303 AU.addRequired<MachineCycleInfoWrapperPass>();
304 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
305 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
306 AU.addPreserved<MachineCycleInfoWrapperPass>();
307 AU.addPreserved<MachineLoopInfoWrapperPass>();
308 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
309 AU.addRequired<ProfileSummaryInfoWrapperPass>();
310 if (UseBlockFreqInfo) {
311 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
312 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
313 }
314 AU.addRequired<TargetPassConfig>();
315 }
316};
317
318} // end anonymous namespace
319
320char MachineSinkingLegacy::ID = 0;
321
322char &llvm::MachineSinkingLegacyID = MachineSinkingLegacy::ID;
323
324INITIALIZE_PASS_BEGIN(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",
325 false, false)
326INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
327INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
328INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
329INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
330INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
331INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
332INITIALIZE_PASS_END(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",
333 false, false)
334
335/// Return true if a target defined block prologue instruction interferes
336/// with a sink candidate.
337static bool blockPrologueInterferes(const MachineBasicBlock *BB,
338 MachineBasicBlock::const_iterator End,
339 const MachineInstr &MI,
340 const TargetRegisterInfo *TRI,
341 const TargetInstrInfo *TII,
342 const MachineRegisterInfo *MRI) {
343 for (MachineBasicBlock::const_iterator PI = BB->getFirstNonPHI(); PI != End;
344 ++PI) {
345 // Only check target defined prologue instructions
346 if (!TII->isBasicBlockPrologue(MI: *PI))
347 continue;
348 for (auto &MO : MI.operands()) {
349 if (!MO.isReg())
350 continue;
351 Register Reg = MO.getReg();
352 if (!Reg)
353 continue;
354 if (MO.isUse()) {
355 if (Reg.isPhysical() &&
356 (TII->isIgnorableUse(MI, OpIdx: MI.getOperandNo(I: &MO)) ||
357 (MRI && MRI->isConstantPhysReg(PhysReg: Reg))))
358 continue;
359 if (PI->modifiesRegister(Reg, TRI))
360 return true;
361 } else {
362 if (PI->readsRegister(Reg, TRI))
363 return true;
364 // Check for interference with non-dead defs
365 auto *DefOp = PI->findRegisterDefOperand(Reg, TRI, isDead: false, Overlap: true);
366 if (DefOp && !DefOp->isDead())
367 return true;
368 }
369 }
370 }
371
372 return false;
373}
374
375bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
376 MachineBasicBlock *MBB) {
377 if (!MI.isCopy())
378 return false;
379
380 Register SrcReg = MI.getOperand(i: 1).getReg();
381 Register DstReg = MI.getOperand(i: 0).getReg();
382 if (!SrcReg.isVirtual() || !DstReg.isVirtual() ||
383 !MRI->hasOneNonDBGUse(RegNo: SrcReg))
384 return false;
385
386 const TargetRegisterClass *SRC = MRI->getRegClass(Reg: SrcReg);
387 const TargetRegisterClass *DRC = MRI->getRegClass(Reg: DstReg);
388 if (SRC != DRC)
389 return false;
390
391 MachineInstr *DefMI = MRI->getVRegDef(Reg: SrcReg);
392 if (!DefMI || DefMI->isCopyLike())
393 return false;
394 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
395 LLVM_DEBUG(dbgs() << "*** to: " << MI);
396 MRI->replaceRegWith(FromReg: DstReg, ToReg: SrcReg);
397 MI.eraseFromParent();
398
399 // Conservatively, clear any kill flags, since it's possible that they are no
400 // longer correct.
401 MRI->clearKillFlags(Reg: SrcReg);
402
403 ++NumCoalesces;
404 return true;
405}
406
407bool MachineSinking::PerformSinkAndFold(MachineInstr &MI,
408 MachineBasicBlock *MBB) {
409 if (MI.isCopy() || MI.mayLoadOrStore() ||
410 MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
411 return false;
412
413 // Don't sink instructions that the target prefers not to sink.
414 if (!TII->shouldSink(MI))
415 return false;
416
417 // Check if it's safe to move the instruction.
418 bool SawStore = true;
419 if (!MI.isSafeToMove(SawStore))
420 return false;
421
422 // Convergent operations may not be made control-dependent on additional
423 // values.
424 if (MI.isConvergent())
425 return false;
426
427 // Don't sink defs/uses of hard registers or if the instruction defines more
428 // than one register.
429 // Don't sink more than two register uses - it'll cover most of the cases and
430 // greatly simplifies the register pressure checks.
431 Register DefReg;
432 Register UsedRegA, UsedRegB;
433 for (const MachineOperand &MO : MI.operands()) {
434 if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
435 MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
436 MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
437 continue;
438 if (!MO.isReg())
439 return false;
440
441 Register Reg = MO.getReg();
442 if (Reg == 0)
443 continue;
444
445 if (Reg.isVirtual()) {
446 if (MO.isDef()) {
447 if (DefReg)
448 return false;
449 DefReg = Reg;
450 continue;
451 }
452
453 if (UsedRegA == 0)
454 UsedRegA = Reg;
455 else if (UsedRegB == 0)
456 UsedRegB = Reg;
457 else
458 return false;
459 continue;
460 }
461
462 if (Reg.isPhysical() && MO.isUse() &&
463 (MRI->isConstantPhysReg(PhysReg: Reg) ||
464 TII->isIgnorableUse(MI, OpIdx: MI.getOperandNo(I: &MO))))
465 continue;
466
467 return false;
468 }
469
470 // Scan uses of the destination register. Every use, except the last, must be
471 // a copy, with a chain of copies terminating with either a copy into a hard
472 // register, or a load/store instruction where the use is part of the
473 // address (*not* the stored value).
474 using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
475 SmallVector<SinkInfo> SinkInto;
476 SmallVector<Register> Worklist;
477
478 const TargetRegisterClass *RC = MRI->getRegClass(Reg: DefReg);
479 const TargetRegisterClass *RCA =
480 UsedRegA == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegA);
481 const TargetRegisterClass *RCB =
482 UsedRegB == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegB);
483
484 Worklist.push_back(Elt: DefReg);
485 while (!Worklist.empty()) {
486 Register Reg = Worklist.pop_back_val();
487
488 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
489 ExtAddrMode MaybeAM;
490 MachineInstr &UseInst = *MO.getParent();
491 if (UseInst.isCopy()) {
492 Register DstReg;
493 if (const MachineOperand &O = UseInst.getOperand(i: 0); O.isReg())
494 DstReg = O.getReg();
495 if (DstReg == 0)
496 return false;
497 if (DstReg.isVirtual()) {
498 Worklist.push_back(Elt: DstReg);
499 continue;
500 }
501 // If we are going to replace a copy, the original instruction must be
502 // as cheap as a copy.
503 if (!TII->isAsCheapAsAMove(MI))
504 return false;
505 // The hard register must be in the register class of the original
506 // instruction's destination register.
507 if (!RC->contains(Reg: DstReg))
508 return false;
509 } else if (UseInst.mayLoadOrStore()) {
510 // If the destination instruction contains more than one use of the
511 // register, we won't be able to remove the original instruction, so
512 // don't sink.
513 if (llvm::count_if(Range: UseInst.operands(), P: [Reg](const MachineOperand &MO) {
514 return MO.isReg() && MO.getReg() == Reg;
515 }) > 1)
516 return false;
517 ExtAddrMode AM;
518 if (!TII->canFoldIntoAddrMode(MemI: UseInst, Reg, AddrI: MI, AM))
519 return false;
520 MaybeAM = AM;
521 } else {
522 return false;
523 }
524
525 if (UseInst.getParent() != MI.getParent()) {
526 // If the register class of the register we are replacing is a superset
527 // of any of the register classes of the operands of the materialized
528 // instruction don't consider that live range extended.
529 const TargetRegisterClass *RCS = MRI->getRegClass(Reg);
530 if (RCA && RCA->hasSuperClassEq(RC: RCS))
531 RCA = nullptr;
532 else if (RCB && RCB->hasSuperClassEq(RC: RCS))
533 RCB = nullptr;
534 if (RCA || RCB) {
535 if (RCA == nullptr) {
536 RCA = RCB;
537 RCB = nullptr;
538 }
539
540 unsigned NRegs = !!RCA + !!RCB;
541 if (RCA == RCB)
542 RCB = nullptr;
543
544 // Check we don't exceed register pressure at the destination.
545 const MachineBasicBlock &MBB = *UseInst.getParent();
546 if (RCB == nullptr) {
547 if (registerPressureSetExceedsLimit(NRegs, RC: RCA, MBB))
548 return false;
549 } else if (registerPressureSetExceedsLimit(NRegs: 1, RC: RCA, MBB) ||
550 registerPressureSetExceedsLimit(NRegs: 1, RC: RCB, MBB)) {
551 return false;
552 }
553 }
554 }
555
556 SinkInto.emplace_back(Args: &UseInst, Args&: MaybeAM);
557 }
558 }
559
560 if (SinkInto.empty())
561 return false;
562
563 // Now we know we can fold the instruction in all its users.
564 for (auto &[SinkDst, MaybeAM] : SinkInto) {
565 MachineInstr *New = nullptr;
566 LLVM_DEBUG(dbgs() << "Sinking copy of"; MI.dump(); dbgs() << "into";
567 SinkDst->dump());
568 if (SinkDst->isCopy()) {
569 // TODO: After performing the sink-and-fold, the original instruction is
570 // deleted. Its value is still available (in a hard register), so if there
571 // are debug instructions which refer to the (now deleted) virtual
572 // register they could be updated to refer to the hard register, in
573 // principle. However, it's not clear how to do that, moreover in some
574 // cases the debug instructions may need to be replicated proportionally
575 // to the number of the COPY instructions replaced and in some extreme
576 // cases we can end up with quadratic increase in the number of debug
577 // instructions.
578
579 // Sink a copy of the instruction, replacing a COPY instruction.
580 MachineBasicBlock::iterator InsertPt = SinkDst->getIterator();
581 Register DstReg = SinkDst->getOperand(i: 0).getReg();
582 TII->reMaterialize(MBB&: *SinkDst->getParent(), MI: InsertPt, DestReg: DstReg, SubIdx: 0, Orig: MI);
583 New = &*std::prev(x: InsertPt);
584 if (!New->getDebugLoc())
585 New->setDebugLoc(SinkDst->getDebugLoc());
586
587 // The operand registers of the "sunk" instruction have their live range
588 // extended and their kill flags may no longer be correct. Conservatively
589 // clear the kill flags.
590 if (UsedRegA)
591 MRI->clearKillFlags(Reg: UsedRegA);
592 if (UsedRegB)
593 MRI->clearKillFlags(Reg: UsedRegB);
594 } else {
595 // Fold instruction into the addressing mode of a memory instruction.
596 New = TII->emitLdStWithAddr(MemI&: *SinkDst, AM: MaybeAM);
597
598 // The registers of the addressing mode may have their live range extended
599 // and their kill flags may no longer be correct. Conservatively clear the
600 // kill flags.
601 if (Register R = MaybeAM.BaseReg; R.isValid() && R.isVirtual())
602 MRI->clearKillFlags(Reg: R);
603 if (Register R = MaybeAM.ScaledReg; R.isValid() && R.isVirtual())
604 MRI->clearKillFlags(Reg: R);
605 }
606 LLVM_DEBUG(dbgs() << "yielding"; New->dump());
607 // Clear the StoreInstrCache, since we may invalidate it by erasing.
608 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
609 StoreInstrCache.clear();
610 SinkDst->eraseFromParent();
611 }
612
613 // Collect operands that need to be cleaned up because the registers no longer
614 // exist (in COPYs and debug instructions). We cannot delete instructions or
615 // clear operands while traversing register uses.
616 SmallVector<MachineOperand *> Cleanup;
617 Worklist.push_back(Elt: DefReg);
618 while (!Worklist.empty()) {
619 Register Reg = Worklist.pop_back_val();
620 for (MachineOperand &MO : MRI->use_operands(Reg)) {
621 MachineInstr *U = MO.getParent();
622 assert((U->isCopy() || U->isDebugInstr()) &&
623 "Only debug uses and copies must remain");
624 if (U->isCopy())
625 Worklist.push_back(Elt: U->getOperand(i: 0).getReg());
626 Cleanup.push_back(Elt: &MO);
627 }
628 }
629
630 // Delete the dead COPYs and clear operands in debug instructions
631 for (MachineOperand *MO : Cleanup) {
632 MachineInstr *I = MO->getParent();
633 if (I->isCopy()) {
634 I->eraseFromParent();
635 } else {
636 MO->setReg(0);
637 MO->setSubReg(0);
638 }
639 }
640
641 MI.eraseFromParent();
642 return true;
643}
644
645/// AllUsesDominatedByBlock - Return true if all uses of the specified register
646/// occur in blocks dominated by the specified block. If any use is in the
647/// definition block, then return false since it is never legal to move def
648/// after uses.
649bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
650 MachineBasicBlock *MBB,
651 MachineBasicBlock *DefMBB,
652 bool &BreakPHIEdge,
653 bool &LocalUse) const {
654 assert(Reg.isVirtual() && "Only makes sense for vregs");
655
656 // Ignore debug uses because debug info doesn't affect the code.
657 if (MRI->use_nodbg_empty(RegNo: Reg))
658 return true;
659
660 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
661 // into and they are all PHI nodes. In this case, machine-sink must break
662 // the critical edge first. e.g.
663 //
664 // %bb.1:
665 // Predecessors according to CFG: %bb.0
666 // ...
667 // %def = DEC64_32r %x, implicit-def dead %eflags
668 // ...
669 // JE_4 <%bb.37>, implicit %eflags
670 // Successors according to CFG: %bb.37 %bb.2
671 //
672 // %bb.2:
673 // %p = PHI %y, %bb.0, %def, %bb.1
674 if (all_of(Range: MRI->use_nodbg_operands(Reg), P: [&](MachineOperand &MO) {
675 MachineInstr *UseInst = MO.getParent();
676 unsigned OpNo = MO.getOperandNo();
677 MachineBasicBlock *UseBlock = UseInst->getParent();
678 return UseBlock == MBB && UseInst->isPHI() &&
679 UseInst->getOperand(i: OpNo + 1).getMBB() == DefMBB;
680 })) {
681 BreakPHIEdge = true;
682 return true;
683 }
684
685 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
686 // Determine the block of the use.
687 MachineInstr *UseInst = MO.getParent();
688 unsigned OpNo = &MO - &UseInst->getOperand(i: 0);
689 MachineBasicBlock *UseBlock = UseInst->getParent();
690 if (UseInst->isPHI()) {
691 // PHI nodes use the operand in the predecessor block, not the block with
692 // the PHI.
693 UseBlock = UseInst->getOperand(i: OpNo + 1).getMBB();
694 } else if (UseBlock == DefMBB) {
695 LocalUse = true;
696 return false;
697 }
698
699 // Check that it dominates.
700 if (!DT->dominates(A: MBB, B: UseBlock))
701 return false;
702 }
703
704 return true;
705}
706
707/// Return true if this machine instruction loads from global offset table or
708/// constant pool.
709static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
710 assert(MI.mayLoad() && "Expected MI that loads!");
711
712 // If we lost memory operands, conservatively assume that the instruction
713 // reads from everything..
714 if (MI.memoperands_empty())
715 return true;
716
717 for (MachineMemOperand *MemOp : MI.memoperands())
718 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
719 if (PSV->isGOT() || PSV->isConstantPool())
720 return true;
721
722 return false;
723}
724
725void MachineSinking::FindCycleSinkCandidates(
726 CycleRef Cycle, MachineBasicBlock *BB,
727 SmallVectorImpl<MachineInstr *> &Candidates) {
728 for (auto &MI : *BB) {
729 LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
730 if (MI.isMetaInstruction()) {
731 LLVM_DEBUG(dbgs() << "CycleSink: not sinking meta instruction\n");
732 continue;
733 }
734 if (!TII->shouldSink(MI)) {
735 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
736 "target\n");
737 continue;
738 }
739 if (!isCycleInvariant(CI: *CI, Cycle, I&: MI)) {
740 LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
741 continue;
742 }
743 bool DontMoveAcrossStore = true;
744 if (!MI.isSafeToMove(SawStore&: DontMoveAcrossStore)) {
745 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
746 continue;
747 }
748 if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
749 LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
750 continue;
751 }
752 if (MI.isConvergent())
753 continue;
754
755 const MachineOperand &MO = MI.getOperand(i: 0);
756 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
757 continue;
758 if (!MRI->hasOneDef(RegNo: MO.getReg()))
759 continue;
760
761 LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
762 Candidates.push_back(Elt: &MI);
763 }
764}
765
766PreservedAnalyses
767MachineSinkingPass::run(MachineFunction &MF,
768 MachineFunctionAnalysisManager &MFAM) {
769 auto *DT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
770 auto *PDT = &MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
771 auto *CI = &MFAM.getResult<MachineCycleAnalysis>(IR&: MF);
772 auto *PSI = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
773 .getCachedResult<ProfileSummaryAnalysis>(
774 IR&: *MF.getFunction().getParent());
775 auto *MBFI = UseBlockFreqInfo
776 ? &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF)
777 : nullptr;
778 auto *MBPI = &MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
779 auto *AA = &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
780 .getManager()
781 .getResult<AAManager>(IR&: MF.getFunction());
782 auto *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF);
783 auto *SI = MFAM.getCachedResult<SlotIndexesAnalysis>(IR&: MF);
784 auto *MLI = MFAM.getCachedResult<MachineLoopAnalysis>(IR&: MF);
785 auto *RegClassInfo = &MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
786 MachineSinking Impl(EnableSinkAndFold, DT, PDT, MLI, SI, LIS, CI, PSI, MBFI,
787 MBPI, AA, RegClassInfo);
788 bool Changed = Impl.run(MF);
789 if (!Changed)
790 return PreservedAnalyses::all();
791 auto PA = getMachineFunctionPassPreservedAnalyses();
792 PA.preserve<MachineCycleAnalysis>();
793 PA.preserve<MachineLoopAnalysis>();
794 if (UseBlockFreqInfo)
795 PA.preserve<MachineBlockFrequencyAnalysis>();
796 return PA;
797}
798
799void MachineSinkingPass::printPipeline(
800 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
801 OS << MapClassName2PassName(name()); // ideally machine-sink
802 if (EnableSinkAndFold)
803 OS << "<enable-sink-fold>";
804}
805
806bool MachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {
807 if (skipFunction(F: MF.getFunction()))
808 return false;
809
810 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
811 bool EnableSinkAndFold = PassConfig->getEnableSinkAndFold();
812
813 auto *DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
814 auto *PDT =
815 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
816 auto *CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
817 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
818 auto *MBFI =
819 UseBlockFreqInfo
820 ? &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI()
821 : nullptr;
822 auto *MBPI =
823 &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
824 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
825 // Get analyses for split critical edge.
826 auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
827 auto *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
828 auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();
829 auto *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;
830 auto *MLIWrapper = getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
831 auto *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
832 auto *RegClassInfo =
833 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
834
835 MachineSinking Impl(EnableSinkAndFold, DT, PDT, MLI, SI, LIS, CI, PSI, MBFI,
836 MBPI, AA, RegClassInfo);
837 return Impl.run(MF);
838}
839
840bool MachineSinking::run(MachineFunction &MF) {
841 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
842
843 STI = &MF.getSubtarget();
844 TII = STI->getInstrInfo();
845 TRI = STI->getRegisterInfo();
846 MRI = &MF.getRegInfo();
847
848 bool EverMadeChange = false;
849
850 while (true) {
851 bool MadeChange = false;
852
853 // Process all basic blocks.
854 CEBCandidates.clear();
855 CEMergeCandidates.clear();
856 ToSplit.clear();
857 for (auto &MBB : MF)
858 MadeChange |= ProcessBlock(MBB);
859
860 // If we have anything we marked as toSplit, split it now.
861 MachineDomTreeUpdater MDTU(DT, PDT,
862 MachineDomTreeUpdater::UpdateStrategy::Lazy);
863 for (const auto &Pair : ToSplit) {
864 auto NewSucc = Pair.first->SplitCriticalEdge(
865 Succ: Pair.second, Analyses: {.LIS: LIS, .SI: SI, /*LV=*/nullptr, .MLI: MLI}, LiveInSets: nullptr, MDTU: &MDTU);
866 if (NewSucc != nullptr) {
867 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
868 << printMBBReference(*Pair.first) << " -- "
869 << printMBBReference(*NewSucc) << " -- "
870 << printMBBReference(*Pair.second) << '\n');
871 if (MBFI)
872 MBFI->onEdgeSplit(NewPredecessor: *Pair.first, NewSuccessor: *NewSucc, MBPI: *MBPI);
873
874 MadeChange = true;
875 ++NumSplit;
876 CI->splitCriticalEdge(Pred: Pair.first, Succ: Pair.second, New: NewSucc);
877 } else
878 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
879 }
880 // If this iteration over the code changed anything, keep iterating.
881 if (!MadeChange)
882 break;
883 EverMadeChange = true;
884 }
885
886 if (SinkInstsIntoCycle) {
887 SmallVector<CycleRef, 8> Cycles(CI->toplevel_cycles());
888 SchedModel.init(TSInfo: STI);
889 bool HasHighPressure;
890
891 DenseMap<SinkItem, MachineInstr *> SunkInstrs;
892
893 enum CycleSinkStage { COPY, LOW_LATENCY, AGGRESSIVE, END };
894 for (unsigned Stage = CycleSinkStage::COPY; Stage != CycleSinkStage::END;
895 ++Stage, SunkInstrs.clear()) {
896 HasHighPressure = false;
897
898 for (auto Cycle : Cycles) {
899 MachineBasicBlock *Preheader = CI->getCyclePreheader(C: Cycle);
900 if (!Preheader) {
901 LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
902 continue;
903 }
904 SmallVector<MachineInstr *, 8> Candidates;
905 FindCycleSinkCandidates(Cycle, BB: Preheader, Candidates);
906
907 unsigned i = 0;
908
909 // Walk the candidates in reverse order so that we start with the use
910 // of a def-use chain, if there is any.
911 // TODO: Sort the candidates using a cost-model.
912 for (MachineInstr *I : llvm::reverse(C&: Candidates)) {
913 // CycleSinkStage::COPY: Sink a limited number of copies
914 if (Stage == CycleSinkStage::COPY) {
915 if (i++ == SinkIntoCycleLimit) {
916 LLVM_DEBUG(dbgs()
917 << "CycleSink: Limit reached of instructions to "
918 "be analyzed.");
919 break;
920 }
921
922 if (!I->isCopy())
923 continue;
924 }
925
926 // CycleSinkStage::LOW_LATENCY: sink unlimited number of instructions
927 // which the target specifies as low-latency
928 if (Stage == CycleSinkStage::LOW_LATENCY &&
929 !TII->hasLowDefLatency(SchedModel, DefMI: *I, DefIdx: 0))
930 continue;
931
932 if (!aggressivelySinkIntoCycle(Cycle, I&: *I, SunkInstrs))
933 continue;
934 EverMadeChange = true;
935 ++NumCycleSunk;
936 }
937
938 // Recalculate the pressure after sinking
939 if (!HasHighPressure)
940 HasHighPressure = registerPressureExceedsLimit(MBB: *Preheader);
941 }
942 if (!HasHighPressure)
943 break;
944 }
945 }
946
947 HasStoreCache.clear();
948 StoreInstrCache.clear();
949
950 // Now clear any kill flags for recorded registers.
951 for (auto I : RegsToClearKillFlags)
952 MRI->clearKillFlags(Reg: I);
953 RegsToClearKillFlags.clear();
954
955 releaseMemory();
956 return EverMadeChange;
957}
958
959bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
960 if ((!EnableSinkAndFold && MBB.succ_size() <= 1) || MBB.empty())
961 return false;
962
963 // Don't bother sinking code out of unreachable blocks. In addition to being
964 // unprofitable, it can also lead to infinite looping, because in an
965 // unreachable cycle there may be nowhere to stop.
966 if (!DT->isReachableFromEntry(A: &MBB))
967 return false;
968
969 bool MadeChange = false;
970
971 // Cache all successors, sorted by frequency info and cycle depth.
972 AllSuccsCache AllSuccessors;
973
974 // Walk the basic block bottom-up. Remember if we saw a store.
975 MachineBasicBlock::iterator I = MBB.end();
976 --I;
977 bool ProcessedBegin, SawStore = false;
978 do {
979 MachineInstr &MI = *I; // The instruction to sink.
980
981 // Predecrement I (if it's not begin) so that it isn't invalidated by
982 // sinking.
983 ProcessedBegin = I == MBB.begin();
984 if (!ProcessedBegin)
985 --I;
986
987 if (MI.isDebugOrPseudoInstr() || MI.isFakeUse()) {
988 if (MI.isDebugValue())
989 ProcessDbgInst(MI);
990 continue;
991 }
992
993 if (EnableSinkAndFold && PerformSinkAndFold(MI, MBB: &MBB)) {
994 MadeChange = true;
995 continue;
996 }
997
998 // Can't sink anything out of a block that has less than two successors.
999 if (MBB.succ_size() <= 1)
1000 continue;
1001
1002 if (PerformTrivialForwardCoalescing(MI, MBB: &MBB)) {
1003 MadeChange = true;
1004 continue;
1005 }
1006
1007 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
1008 ++NumSunk;
1009 MadeChange = true;
1010 }
1011
1012 // If we just processed the first instruction in the block, we're done.
1013 } while (!ProcessedBegin);
1014
1015 SeenDbgUsers.clear();
1016 SeenDbgVars.clear();
1017 // recalculate the bb register pressure after sinking one BB.
1018 CachedRegisterPressure.clear();
1019 return MadeChange;
1020}
1021
1022void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
1023 // When we see DBG_VALUEs for registers, record any vreg it reads, so that
1024 // we know what to sink if the vreg def sinks.
1025 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
1026
1027 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1028 MI.getDebugLoc()->getInlinedAt());
1029 bool SeenBefore = SeenDbgVars.contains(V: Var);
1030
1031 for (MachineOperand &MO : MI.debug_operands()) {
1032 if (MO.isReg() && MO.getReg().isVirtual())
1033 SeenDbgUsers[MO.getReg()].push_back(NewVal: SeenDbgUser(&MI, SeenBefore));
1034 }
1035
1036 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
1037 SeenDbgVars.insert(V: Var);
1038}
1039
1040bool MachineSinking::isWorthBreakingCriticalEdge(
1041 MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To,
1042 MachineBasicBlock *&DeferredFromBlock) {
1043 // FIXME: Need much better heuristics.
1044
1045 // If the pass has already considered breaking this edge (during this pass
1046 // through the function), then let's go ahead and break it. This means
1047 // sinking multiple "cheap" instructions into the same block.
1048 if (!CEBCandidates.insert(V: std::make_pair(x&: From, y&: To)).second)
1049 return true;
1050
1051 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
1052 return true;
1053
1054 // Check and record the register and the destination block we want to sink
1055 // into. Note that we want to do the following before the next check on branch
1056 // probability. Because we want to record the initial candidate even if it's
1057 // on hot edge, so that other candidates that might not on hot edges can be
1058 // sinked as well.
1059 for (const auto &MO : MI.all_defs()) {
1060 Register Reg = MO.getReg();
1061 if (!Reg)
1062 continue;
1063 Register SrcReg = Reg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: Reg, MRI) : Reg;
1064 auto Key = std::make_pair(x&: SrcReg, y&: To);
1065 auto Res = CEMergeCandidates.try_emplace(Key, Args&: From);
1066 // We wanted to sink the same register into the same block, consider it to
1067 // be profitable.
1068 if (!Res.second) {
1069 // Return the source block that was previously held off.
1070 DeferredFromBlock = Res.first->second;
1071 return true;
1072 }
1073 }
1074
1075 if (From->isSuccessor(MBB: To) &&
1076 MBPI->getEdgeProbability(Src: From, Dst: To) <=
1077 BranchProbability(SplitEdgeProbabilityThreshold, 100))
1078 return true;
1079
1080 // MI is cheap, we probably don't want to break the critical edge for it.
1081 // However, if this would allow some definitions of its source operands
1082 // to be sunk then it's probably worth it.
1083 for (const MachineOperand &MO : MI.all_uses()) {
1084 Register Reg = MO.getReg();
1085 if (Reg == 0)
1086 continue;
1087
1088 // We don't move live definitions of physical registers,
1089 // so sinking their uses won't enable any opportunities.
1090 if (Reg.isPhysical())
1091 continue;
1092
1093 // If this instruction is the only user of a virtual register,
1094 // check if breaking the edge will enable sinking
1095 // both this instruction and the defining instruction.
1096 if (MRI->hasOneNonDBGUse(RegNo: Reg)) {
1097 // If the definition resides in same MBB,
1098 // claim it's likely we can sink these together.
1099 // If definition resides elsewhere, we aren't
1100 // blocking it from being sunk so don't break the edge.
1101 if (MRI->getDefBlock(Reg) == MI.getParent())
1102 return true;
1103 }
1104 }
1105
1106 // Let the target decide if it's worth breaking this
1107 // critical edge for a "cheap" instruction.
1108 return TII->shouldBreakCriticalEdgeToSink(MI);
1109}
1110
1111bool MachineSinking::isLegalToBreakCriticalEdge(MachineInstr &MI,
1112 MachineBasicBlock *FromBB,
1113 MachineBasicBlock *ToBB,
1114 bool BreakPHIEdge) {
1115 // Avoid breaking back edge. From == To means backedge for single BB cycle.
1116 if (!SplitEdges || FromBB == ToBB || !FromBB->isSuccessor(MBB: ToBB))
1117 return false;
1118
1119 CycleRef FromCycle = CI->getCycle(Block: FromBB);
1120 CycleRef ToCycle = CI->getCycle(Block: ToBB);
1121
1122 // Check for backedges of more "complex" cycles.
1123 if (FromCycle == ToCycle && FromCycle &&
1124 (!CI->isReducible(C: FromCycle) || CI->getHeader(C: FromCycle) == ToBB))
1125 return false;
1126
1127 // It's not always legal to break critical edges and sink the computation
1128 // to the edge.
1129 //
1130 // %bb.1:
1131 // v1024
1132 // Beq %bb.3
1133 // <fallthrough>
1134 // %bb.2:
1135 // ... no uses of v1024
1136 // <fallthrough>
1137 // %bb.3:
1138 // ...
1139 // = v1024
1140 //
1141 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
1142 //
1143 // %bb.1:
1144 // ...
1145 // Bne %bb.2
1146 // %bb.4:
1147 // v1024 =
1148 // B %bb.3
1149 // %bb.2:
1150 // ... no uses of v1024
1151 // <fallthrough>
1152 // %bb.3:
1153 // ...
1154 // = v1024
1155 //
1156 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
1157 // flow. We need to ensure the new basic block where the computation is
1158 // sunk to dominates all the uses.
1159 // It's only legal to break critical edge and sink the computation to the
1160 // new block if all the predecessors of "To", except for "From", are
1161 // not dominated by "From". Given SSA property, this means these
1162 // predecessors are dominated by "To".
1163 //
1164 // There is no need to do this check if all the uses are PHI nodes. PHI
1165 // sources are only defined on the specific predecessor edges.
1166 if (!BreakPHIEdge) {
1167 for (MachineBasicBlock *Pred : ToBB->predecessors())
1168 if (Pred != FromBB && !DT->dominates(A: ToBB, B: Pred))
1169 return false;
1170 }
1171
1172 return true;
1173}
1174
1175bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
1176 MachineBasicBlock *FromBB,
1177 MachineBasicBlock *ToBB,
1178 bool BreakPHIEdge) {
1179 bool Status = false;
1180 MachineBasicBlock *DeferredFromBB = nullptr;
1181 if (isWorthBreakingCriticalEdge(MI, From: FromBB, To: ToBB, DeferredFromBlock&: DeferredFromBB)) {
1182 // If there is a DeferredFromBB, we consider FromBB only if _both_
1183 // of them are legal to split.
1184 if ((!DeferredFromBB ||
1185 ToSplit.count(key: std::make_pair(x&: DeferredFromBB, y&: ToBB)) ||
1186 isLegalToBreakCriticalEdge(MI, FromBB: DeferredFromBB, ToBB, BreakPHIEdge)) &&
1187 isLegalToBreakCriticalEdge(MI, FromBB, ToBB, BreakPHIEdge)) {
1188 ToSplit.insert(X: std::make_pair(x&: FromBB, y&: ToBB));
1189 if (DeferredFromBB)
1190 ToSplit.insert(X: std::make_pair(x&: DeferredFromBB, y&: ToBB));
1191 Status = true;
1192 }
1193 }
1194
1195 return Status;
1196}
1197
1198std::vector<unsigned> &
1199MachineSinking::getBBRegisterPressure(const MachineBasicBlock &MBB,
1200 bool UseCache) {
1201 // Currently to save compiling time, MBB's register pressure will not change
1202 // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
1203 // register pressure is changed after sinking any instructions into it.
1204 // FIXME: need a accurate and cheap register pressure estiminate model here.
1205
1206 auto RP = CachedRegisterPressure.find(Val: &MBB);
1207 if (UseCache && RP != CachedRegisterPressure.end())
1208 return RP->second;
1209
1210 RegionPressure Pressure;
1211 RegPressureTracker RPTracker(Pressure);
1212
1213 // Initialize the register pressure tracker.
1214 RPTracker.init(mf: MBB.getParent(), rci: RegClassInfo, lis: nullptr, mbb: &MBB, pos: MBB.end(),
1215 /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
1216
1217 for (MachineBasicBlock::const_iterator MII = MBB.instr_end(),
1218 MIE = MBB.instr_begin();
1219 MII != MIE; --MII) {
1220 const MachineInstr &MI = *std::prev(x: MII);
1221 if (MI.isDebugOrPseudoInstr())
1222 continue;
1223 RegisterOperands RegOpers;
1224 RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks: false, IgnoreDead: false);
1225 RPTracker.recedeSkipDebugValues();
1226 assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
1227 RPTracker.recede(RegOpers);
1228 }
1229
1230 RPTracker.closeRegion();
1231
1232 if (RP != CachedRegisterPressure.end()) {
1233 CachedRegisterPressure[&MBB] = RPTracker.getPressure().MaxSetPressure;
1234 return CachedRegisterPressure[&MBB];
1235 }
1236
1237 auto It = CachedRegisterPressure.insert(
1238 KV: std::make_pair(x: &MBB, y&: RPTracker.getPressure().MaxSetPressure));
1239 return It.first->second;
1240}
1241
1242bool MachineSinking::registerPressureSetExceedsLimit(
1243 unsigned NRegs, const TargetRegisterClass *RC,
1244 const MachineBasicBlock &MBB) {
1245 unsigned Weight = NRegs * TRI->getRegClassWeight(RC).RegWeight;
1246 const int *PS = TRI->getRegClassPressureSets(RC);
1247 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB);
1248 for (; *PS != -1; PS++)
1249 if (Weight + BBRegisterPressure[*PS] >=
1250 RegClassInfo->getRegPressureSetLimit(Idx: *PS))
1251 return true;
1252 return false;
1253}
1254
1255// Recalculate RP and check if any pressure set exceeds the set limit.
1256bool MachineSinking::registerPressureExceedsLimit(
1257 const MachineBasicBlock &MBB) {
1258 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB, UseCache: false);
1259
1260 for (unsigned PS = 0; PS < BBRegisterPressure.size(); ++PS) {
1261 if (BBRegisterPressure[PS] >= RegClassInfo->getRegPressureSetLimit(Idx: PS)) {
1262 return true;
1263 }
1264 }
1265
1266 return false;
1267}
1268
1269/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
1270bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
1271 MachineBasicBlock *MBB,
1272 MachineBasicBlock *SuccToSinkTo,
1273 AllSuccsCache &AllSuccessors) {
1274 assert(SuccToSinkTo && "Invalid SinkTo Candidate BB");
1275
1276 if (MBB == SuccToSinkTo)
1277 return false;
1278
1279 // It is profitable if SuccToSinkTo does not post dominate current block.
1280 if (!PDT->dominates(A: SuccToSinkTo, B: MBB))
1281 return true;
1282
1283 // It is profitable to sink an instruction from a deeper cycle to a shallower
1284 // cycle, even if the latter post-dominates the former (PR21115).
1285 if (CI->getCycleDepth(Block: MBB) > CI->getCycleDepth(Block: SuccToSinkTo))
1286 return true;
1287
1288 // Check if only use in post dominated block is PHI instruction.
1289 bool NonPHIUse = false;
1290 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
1291 MachineBasicBlock *UseBlock = UseInst.getParent();
1292 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
1293 NonPHIUse = true;
1294 }
1295 if (!NonPHIUse)
1296 return true;
1297
1298 // If SuccToSinkTo post dominates then also it may be profitable if MI
1299 // can further profitably sinked into another block in next round.
1300 bool BreakPHIEdge = false;
1301 // FIXME - If finding successor is compile time expensive then cache results.
1302 if (MachineBasicBlock *MBB2 =
1303 FindSuccToSinkTo(MI, MBB: SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1304 return isProfitableToSinkTo(Reg, MI, MBB: SuccToSinkTo, SuccToSinkTo: MBB2, AllSuccessors);
1305
1306 CycleRef MCycle = CI->getCycle(Block: MBB);
1307
1308 // If the instruction is not inside a cycle, it is not profitable to sink MI
1309 // to a post dominate block SuccToSinkTo.
1310 if (!MCycle)
1311 return false;
1312
1313 // If this instruction is inside a Cycle and sinking this instruction can make
1314 // more registers live range shorten, it is still prifitable.
1315 for (const MachineOperand &MO : MI.operands()) {
1316 // Ignore non-register operands.
1317 if (!MO.isReg())
1318 continue;
1319 Register Reg = MO.getReg();
1320 if (Reg == 0)
1321 continue;
1322
1323 if (Reg.isPhysical()) {
1324 // Don't handle non-constant and non-ignorable physical register uses.
1325 if (MO.isUse() && !MRI->isConstantPhysReg(PhysReg: Reg) &&
1326 !TII->isIgnorableUse(MI, OpIdx: MI.getOperandNo(I: &MO)))
1327 return false;
1328 continue;
1329 }
1330
1331 // Users for the defs are all dominated by SuccToSinkTo.
1332 if (MO.isDef()) {
1333 // This def register's live range is shortened after sinking.
1334 bool LocalUse = false;
1335 if (!AllUsesDominatedByBlock(Reg, MBB: SuccToSinkTo, DefMBB: MBB, BreakPHIEdge,
1336 LocalUse))
1337 return false;
1338 } else {
1339 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1340 if (!DefMI)
1341 continue;
1342 CycleRef Cycle = CI->getCycle(Block: DefMI->getParent());
1343 // DefMI is defined outside of cycle. There should be no live range
1344 // impact for this operand. Defination outside of cycle means:
1345 // 1: defination is outside of cycle.
1346 // 2: defination is in this cycle, but it is a PHI in the cycle header.
1347 if (Cycle != MCycle ||
1348 (DefMI->isPHI() && Cycle && CI->isReducible(C: Cycle) &&
1349 CI->getHeader(C: Cycle) == DefMI->getParent()))
1350 continue;
1351 // The DefMI is defined inside the cycle.
1352 // If sinking this operand makes some register pressure set exceed limit,
1353 // it is not profitable.
1354 if (registerPressureSetExceedsLimit(NRegs: 1, RC: MRI->getRegClass(Reg),
1355 MBB: *SuccToSinkTo)) {
1356 LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
1357 return false;
1358 }
1359 }
1360 }
1361
1362 // If MI is in cycle and all its operands are alive across the whole cycle or
1363 // if no operand sinking make register pressure set exceed limit, it is
1364 // profitable to sink MI.
1365 return true;
1366}
1367
1368/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
1369/// computing it if it was not already cached.
1370SmallVector<MachineBasicBlock *, 4> &
1371MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
1372 AllSuccsCache &AllSuccessors) const {
1373 // Do we have the sorted successors in cache ?
1374 auto Succs = AllSuccessors.find(Val: MBB);
1375 if (Succs != AllSuccessors.end())
1376 return Succs->second;
1377
1378 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());
1379
1380 // Handle cases where sinking can happen but where the sink point isn't a
1381 // successor. For example:
1382 //
1383 // x = computation
1384 // if () {} else {}
1385 // use x
1386 //
1387 for (MachineDomTreeNode *DTChild : DT->getNode(BB: MBB)->children()) {
1388 // DomTree children of MBB that have MBB as immediate dominator are added.
1389 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
1390 // Skip MBBs already added to the AllSuccs vector above.
1391 !MBB->isSuccessor(MBB: DTChild->getBlock()))
1392 AllSuccs.push_back(Elt: DTChild->getBlock());
1393 }
1394
1395 // Sort Successors according to their cycle depth or block frequency info.
1396 llvm::stable_sort(
1397 Range&: AllSuccs, C: [&](const MachineBasicBlock *L, const MachineBasicBlock *R) {
1398 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(MBB: L).getFrequency() : 0;
1399 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(MBB: R).getFrequency() : 0;
1400 if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI) ||
1401 (!LHSFreq && !RHSFreq))
1402 return CI->getCycleDepth(Block: L) < CI->getCycleDepth(Block: R);
1403 return LHSFreq < RHSFreq;
1404 });
1405
1406 auto it = AllSuccessors.insert(KV: std::make_pair(x&: MBB, y&: AllSuccs));
1407
1408 return it.first->second;
1409}
1410
1411/// FindSuccToSinkTo - Find a successor to sink this instruction to.
1412MachineBasicBlock *
1413MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
1414 bool &BreakPHIEdge,
1415 AllSuccsCache &AllSuccessors) {
1416 assert(MBB && "Invalid MachineBasicBlock!");
1417
1418 // loop over all the operands of the specified instruction. If there is
1419 // anything we can't handle, bail out.
1420
1421 // SuccToSinkTo - This is the successor to sink this instruction to, once we
1422 // decide.
1423 MachineBasicBlock *SuccToSinkTo = nullptr;
1424 for (const MachineOperand &MO : MI.operands()) {
1425 if (!MO.isReg())
1426 continue; // Ignore non-register operands.
1427
1428 Register Reg = MO.getReg();
1429 if (Reg == 0)
1430 continue;
1431
1432 if (Reg.isPhysical()) {
1433 if (MO.isUse()) {
1434 // If the physreg has no defs anywhere, it's just an ambient register
1435 // and we can freely move its uses. Alternatively, if it's allocatable,
1436 // it could get allocated to something with a def during allocation.
1437 if (!MRI->isConstantPhysReg(PhysReg: Reg) &&
1438 !TII->isIgnorableUse(MI, OpIdx: MI.getOperandNo(I: &MO)))
1439 return nullptr;
1440 } else if (!MO.isDead()) {
1441 // A def that isn't dead. We can't move it.
1442 return nullptr;
1443 }
1444 } else {
1445 // Virtual register uses are always safe to sink.
1446 if (MO.isUse())
1447 continue;
1448
1449 // If it's not safe to move defs of the register class, then abort.
1450 if (!TII->isSafeToMoveRegClassDefs(RC: MRI->getRegClass(Reg)))
1451 return nullptr;
1452
1453 // Virtual register defs can only be sunk if all their uses are in blocks
1454 // dominated by one of the successors.
1455 if (SuccToSinkTo) {
1456 // If a previous operand picked a block to sink to, then this operand
1457 // must be sinkable to the same block.
1458 bool LocalUse = false;
1459 if (!AllUsesDominatedByBlock(Reg, MBB: SuccToSinkTo, DefMBB: MBB, BreakPHIEdge,
1460 LocalUse))
1461 return nullptr;
1462
1463 continue;
1464 }
1465
1466 // Otherwise, we should look at all the successors and decide which one
1467 // we should sink to. If we have reliable block frequency information
1468 // (frequency != 0) available, give successors with smaller frequencies
1469 // higher priority, otherwise prioritize smaller cycle depths.
1470 for (MachineBasicBlock *SuccBlock :
1471 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
1472 bool LocalUse = false;
1473 if (AllUsesDominatedByBlock(Reg, MBB: SuccBlock, DefMBB: MBB, BreakPHIEdge,
1474 LocalUse)) {
1475 SuccToSinkTo = SuccBlock;
1476 break;
1477 }
1478 if (LocalUse)
1479 // Def is used locally, it's never safe to move this def.
1480 return nullptr;
1481 }
1482
1483 // If we couldn't find a block to sink to, ignore this instruction.
1484 if (!SuccToSinkTo)
1485 return nullptr;
1486 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
1487 return nullptr;
1488 }
1489 }
1490
1491 // It is not possible to sink an instruction into its own block. This can
1492 // happen with cycles.
1493 if (MBB == SuccToSinkTo)
1494 return nullptr;
1495
1496 // It's not safe to sink instructions to EH landing pad. Control flow into
1497 // landing pad is implicitly defined.
1498 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
1499 return nullptr;
1500
1501 // It ought to be okay to sink instructions into an INLINEASM_BR target, but
1502 // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
1503 // the source block (which this code does not yet do). So for now, forbid
1504 // doing so.
1505 if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
1506 return nullptr;
1507
1508 if (SuccToSinkTo && !TII->isSafeToSink(MI, SuccToSinkTo, CI))
1509 return nullptr;
1510
1511 return SuccToSinkTo;
1512}
1513
1514/// Return true if MI is likely to be usable as a memory operation by the
1515/// implicit null check optimization.
1516///
1517/// This is a "best effort" heuristic, and should not be relied upon for
1518/// correctness. This returning true does not guarantee that the implicit null
1519/// check optimization is legal over MI, and this returning false does not
1520/// guarantee MI cannot possibly be used to do a null check.
1521static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
1522 const TargetInstrInfo *TII,
1523 const TargetRegisterInfo *TRI) {
1524 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
1525
1526 auto *MBB = MI.getParent();
1527 if (MBB->pred_size() != 1)
1528 return false;
1529
1530 auto *PredMBB = *MBB->pred_begin();
1531 auto *PredBB = PredMBB->getBasicBlock();
1532
1533 // Frontends that don't use implicit null checks have no reason to emit
1534 // branches with make.implicit metadata, and this function should always
1535 // return false for them.
1536 if (!PredBB ||
1537 !PredBB->getTerminator()->getMetadata(KindID: LLVMContext::MD_make_implicit))
1538 return false;
1539
1540 const MachineOperand *BaseOp;
1541 int64_t Offset;
1542 bool OffsetIsScalable;
1543 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
1544 return false;
1545
1546 if (!BaseOp->isReg())
1547 return false;
1548
1549 if (!(MI.mayLoad() && !MI.isPredicable()))
1550 return false;
1551
1552 MachineBranchPredicate MBP;
1553 if (TII->analyzeBranchPredicate(MBB&: *PredMBB, MBP, AllowModify: false))
1554 return false;
1555
1556 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1557 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1558 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1559 MBP.LHS.getReg() == BaseOp->getReg();
1560}
1561
1562/// If the sunk instruction is a copy, try to forward the copy instead of
1563/// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
1564/// there's any subregister weirdness involved. Returns true if copy
1565/// propagation occurred.
1566static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,
1567 Register Reg) {
1568 const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
1569 const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
1570
1571 // Copy DBG_VALUE operand and set the original to undef. We then check to
1572 // see whether this is something that can be copy-forwarded. If it isn't,
1573 // continue around the loop.
1574
1575 const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
1576 auto CopyOperands = TII.isCopyInstr(MI: SinkInst);
1577 if (!CopyOperands)
1578 return false;
1579 SrcMO = CopyOperands->Source;
1580 DstMO = CopyOperands->Destination;
1581
1582 // Check validity of forwarding this copy.
1583 bool PostRA = MRI.getNumVirtRegs() == 0;
1584
1585 // Trying to forward between physical and virtual registers is too hard.
1586 if (Reg.isVirtual() != SrcMO->getReg().isVirtual())
1587 return false;
1588
1589 // Only try virtual register copy-forwarding before regalloc, and physical
1590 // register copy-forwarding after regalloc.
1591 bool arePhysRegs = !Reg.isVirtual();
1592 if (arePhysRegs != PostRA)
1593 return false;
1594
1595 // Pre-regalloc, only forward if all subregisters agree (or there are no
1596 // subregs at all). More analysis might recover some forwardable copies.
1597 if (!PostRA)
1598 for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))
1599 if (DbgMO.getSubReg() != SrcMO->getSubReg() ||
1600 DbgMO.getSubReg() != DstMO->getSubReg())
1601 return false;
1602
1603 // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
1604 // of this copy. Only forward the copy if the DBG_VALUE operand exactly
1605 // matches the copy destination.
1606 if (PostRA && Reg != DstMO->getReg())
1607 return false;
1608
1609 for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {
1610 DbgMO.setReg(SrcMO->getReg());
1611 DbgMO.setSubReg(SrcMO->getSubReg());
1612 }
1613 return true;
1614}
1615
1616using MIRegs = std::pair<MachineInstr *, SmallVector<Register, 2>>;
1617/// Sink an instruction and its associated debug instructions.
1618static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
1619 MachineBasicBlock::iterator InsertPos,
1620 ArrayRef<MIRegs> DbgValuesToSink) {
1621 // If we cannot find a location to use (merge with), then we erase the debug
1622 // location to prevent debug-info driven tools from potentially reporting
1623 // wrong location information.
1624 if (SuccToSinkTo.empty())
1625 MI.setDebugLoc(DebugLoc::getDropped());
1626 else
1627 MI.setDebugLoc(DebugLoc::getMergedLocation(
1628 LocA: MI.getDebugLoc(), LocB: SuccToSinkTo.findDebugLoc(MBBI: InsertPos)));
1629
1630 // Move the instruction.
1631 MachineBasicBlock *ParentBlock = MI.getParent();
1632 SuccToSinkTo.splice(Where: InsertPos, Other: ParentBlock, From: MI,
1633 To: ++MachineBasicBlock::iterator(MI));
1634
1635 // Sink a copy of debug users to the insert position. Mark the original
1636 // DBG_VALUE location as 'undef', indicating that any earlier variable
1637 // location should be terminated as we've optimised away the value at this
1638 // point.
1639 for (const auto &DbgValueToSink : DbgValuesToSink) {
1640 MachineInstr *DbgMI = DbgValueToSink.first;
1641 MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(Orig: DbgMI);
1642 SuccToSinkTo.insert(I: InsertPos, MI: NewDbgMI);
1643
1644 bool PropagatedAllSunkOps = true;
1645 for (Register Reg : DbgValueToSink.second) {
1646 if (DbgMI->hasDebugOperandForReg(Reg)) {
1647 if (!attemptDebugCopyProp(SinkInst&: MI, DbgMI&: *DbgMI, Reg)) {
1648 PropagatedAllSunkOps = false;
1649 break;
1650 }
1651 }
1652 }
1653 if (!PropagatedAllSunkOps)
1654 DbgMI->setDebugValueUndef();
1655 }
1656}
1657
1658/// hasStoreBetween - check if there is store betweeen straight line blocks From
1659/// and To.
1660bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1661 MachineBasicBlock *To, MachineInstr &MI) {
1662 // Make sure From and To are in straight line which means From dominates To
1663 // and To post dominates From.
1664 if (!DT->dominates(A: From, B: To) || !PDT->dominates(A: To, B: From))
1665 return true;
1666
1667 auto BlockPair = std::make_pair(x&: From, y&: To);
1668
1669 // Does these two blocks pair be queried before and have a definite cached
1670 // result?
1671 if (auto It = HasStoreCache.find(Val: BlockPair); It != HasStoreCache.end())
1672 return It->second;
1673
1674 if (auto It = StoreInstrCache.find(Val: BlockPair); It != StoreInstrCache.end())
1675 return llvm::any_of(Range&: It->second, P: [&](MachineInstr *I) {
1676 return I->mayAlias(AA, Other: MI, UseTBAA: false);
1677 });
1678
1679 bool SawStore = false;
1680 bool HasAliasedStore = false;
1681 DenseSet<MachineBasicBlock *> HandledBlocks;
1682 DenseSet<MachineBasicBlock *> HandledDomBlocks;
1683 // Go through all reachable blocks from From.
1684 for (MachineBasicBlock *BB : depth_first(G: From)) {
1685 // We insert the instruction at the start of block To, so no need to worry
1686 // about stores inside To.
1687 // Store in block From should be already considered when just enter function
1688 // SinkInstruction.
1689 if (BB == To || BB == From)
1690 continue;
1691
1692 // We already handle this BB in previous iteration.
1693 if (HandledBlocks.count(V: BB))
1694 continue;
1695
1696 HandledBlocks.insert(V: BB);
1697 // To post dominates BB, it must be a path from block From.
1698 if (PDT->dominates(A: To, B: BB)) {
1699 if (!HandledDomBlocks.count(V: BB))
1700 HandledDomBlocks.insert(V: BB);
1701
1702 // If this BB is too big or the block number in straight line between From
1703 // and To is too big, stop searching to save compiling time.
1704 if (BB->sizeWithoutDebugLargerThan(Limit: SinkLoadInstsPerBlockThreshold) ||
1705 HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1706 for (auto *DomBB : HandledDomBlocks) {
1707 if (DomBB != BB && DT->dominates(A: DomBB, B: BB))
1708 HasStoreCache[std::make_pair(x&: DomBB, y&: To)] = true;
1709 else if (DomBB != BB && DT->dominates(A: BB, B: DomBB))
1710 HasStoreCache[std::make_pair(x&: From, y&: DomBB)] = true;
1711 }
1712 HasStoreCache[BlockPair] = true;
1713 return true;
1714 }
1715
1716 for (MachineInstr &I : *BB) {
1717 // Treat as alias conservatively for a call or an ordered memory
1718 // operation.
1719 if (I.isCall() || I.hasOrderedMemoryRef()) {
1720 for (auto *DomBB : HandledDomBlocks) {
1721 if (DomBB != BB && DT->dominates(A: DomBB, B: BB))
1722 HasStoreCache[std::make_pair(x&: DomBB, y&: To)] = true;
1723 else if (DomBB != BB && DT->dominates(A: BB, B: DomBB))
1724 HasStoreCache[std::make_pair(x&: From, y&: DomBB)] = true;
1725 }
1726 HasStoreCache[BlockPair] = true;
1727 return true;
1728 }
1729
1730 if (I.mayStore()) {
1731 SawStore = true;
1732 // We still have chance to sink MI if all stores between are not
1733 // aliased to MI.
1734 // Cache all store instructions, so that we don't need to go through
1735 // all From reachable blocks for next load instruction.
1736 if (I.mayAlias(AA, Other: MI, UseTBAA: false))
1737 HasAliasedStore = true;
1738 StoreInstrCache[BlockPair].push_back(Elt: &I);
1739 }
1740 }
1741 }
1742 }
1743 // If there is no store at all, cache the result.
1744 if (!SawStore)
1745 HasStoreCache[BlockPair] = false;
1746 return HasAliasedStore;
1747}
1748
1749/// Aggressively sink instructions into cycles. This will aggressively try to
1750/// sink all instructions in the top-most preheaders in an attempt to reduce RP.
1751/// In particular, it will sink into multiple successor blocks without limits
1752/// based on the amount of sinking, or the type of ops being sunk (so long as
1753/// they are safe to sink).
1754bool MachineSinking::aggressivelySinkIntoCycle(
1755 CycleRef Cycle, MachineInstr &I,
1756 DenseMap<SinkItem, MachineInstr *> &SunkInstrs) {
1757 // TODO: support instructions with multiple defs
1758 if (I.getNumDefs() > 1)
1759 return false;
1760
1761 LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Finding sink block for: " << I);
1762 assert(CI->getCyclePreheader(Cycle) && "Cycle sink needs a preheader block");
1763 SmallVector<std::pair<RegSubRegPair, MachineInstr *>> Uses;
1764
1765 MachineOperand &DefMO = I.getOperand(i: 0);
1766 for (MachineInstr &MI : MRI->use_instructions(Reg: DefMO.getReg())) {
1767 Uses.push_back(Elt: {{DefMO.getReg(), DefMO.getSubReg()}, &MI});
1768 }
1769
1770 for (std::pair<RegSubRegPair, MachineInstr *> Entry : Uses) {
1771 MachineInstr *MI = Entry.second;
1772 LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Analysing use: " << MI);
1773 if (MI->isPHI()) {
1774 LLVM_DEBUG(
1775 dbgs() << "AggressiveCycleSink: Not attempting to sink for PHI.\n");
1776 continue;
1777 }
1778 // We cannot sink before the prologue
1779 if (MI->isPosition() || TII->isBasicBlockPrologue(MI: *MI)) {
1780 LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Use is BasicBlock prologue, "
1781 "can't sink.\n");
1782 continue;
1783 }
1784 if (!CI->contains(C: Cycle, Block: MI->getParent())) {
1785 LLVM_DEBUG(
1786 dbgs() << "AggressiveCycleSink: Use not in cycle, can't sink.\n");
1787 continue;
1788 }
1789
1790 MachineBasicBlock *SinkBlock = MI->getParent();
1791 MachineInstr *NewMI = nullptr;
1792 SinkItem MapEntry(&I, SinkBlock);
1793
1794 auto SI = SunkInstrs.find(Val: MapEntry);
1795
1796 // Check for the case in which we have already sunk a copy of this
1797 // instruction into the user block.
1798 if (SI != SunkInstrs.end()) {
1799 LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Already sunk to block: "
1800 << printMBBReference(*SinkBlock) << "\n");
1801 NewMI = SI->second;
1802 }
1803
1804 // Create a copy of the instruction in the use block.
1805 if (!NewMI) {
1806 LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Sinking instruction to block: "
1807 << printMBBReference(*SinkBlock) << "\n");
1808
1809 NewMI = I.getMF()->CloneMachineInstr(Orig: &I);
1810 if (DefMO.getReg().isVirtual()) {
1811 const TargetRegisterClass *TRC = MRI->getRegClass(Reg: DefMO.getReg());
1812 Register DestReg = MRI->createVirtualRegister(RegClass: TRC);
1813 NewMI->substituteRegister(FromReg: DefMO.getReg(), ToReg: DestReg, SubIdx: DefMO.getSubReg(),
1814 RegInfo: *TRI);
1815 }
1816 SinkBlock->insert(I: SinkBlock->SkipPHIsAndLabels(I: SinkBlock->begin()),
1817 MI: NewMI);
1818 SunkInstrs.insert(KV: {MapEntry, NewMI});
1819 }
1820
1821 // Conservatively clear any kill flags on uses of sunk instruction
1822 for (MachineOperand &MO : NewMI->all_uses()) {
1823 assert(MO.isReg() && MO.isUse());
1824 RegsToClearKillFlags.insert(V: MO.getReg());
1825 }
1826
1827 // The instruction is moved from its basic block, so do not retain the
1828 // debug information.
1829 assert(!NewMI->isDebugInstr() && "Should not sink debug inst");
1830 NewMI->setDebugLoc(DebugLoc());
1831
1832 // Replace the use with the newly created virtual register.
1833 RegSubRegPair &UseReg = Entry.first;
1834 MI->substituteRegister(FromReg: UseReg.Reg, ToReg: NewMI->getOperand(i: 0).getReg(),
1835 SubIdx: UseReg.SubReg, RegInfo: *TRI);
1836 }
1837 // If we have replaced all uses, then delete the dead instruction
1838 if (I.isDead(MRI: *MRI))
1839 I.eraseFromParent();
1840 return true;
1841}
1842
1843/// SinkInstruction - Determine whether it is safe to sink the specified machine
1844/// instruction out of its current block into a successor.
1845bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1846 AllSuccsCache &AllSuccessors) {
1847 // Don't sink instructions that the target prefers not to sink.
1848 if (!TII->shouldSink(MI))
1849 return false;
1850
1851 // Check if it's safe to move the instruction.
1852 if (!MI.isSafeToMove(SawStore))
1853 return false;
1854
1855 // Convergent operations may not be made control-dependent on additional
1856 // values.
1857 if (MI.isConvergent())
1858 return false;
1859
1860 // Don't break implicit null checks. This is a performance heuristic, and not
1861 // required for correctness.
1862 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
1863 return false;
1864
1865 // FIXME: This should include support for sinking instructions within the
1866 // block they are currently in to shorten the live ranges. We often get
1867 // instructions sunk into the top of a large block, but it would be better to
1868 // also sink them down before their first use in the block. This xform has to
1869 // be careful not to *increase* register pressure though, e.g. sinking
1870 // "x = y + z" down if it kills y and z would increase the live ranges of y
1871 // and z and only shrink the live range of x.
1872
1873 bool BreakPHIEdge = false;
1874 MachineBasicBlock *ParentBlock = MI.getParent();
1875 MachineBasicBlock *SuccToSinkTo =
1876 FindSuccToSinkTo(MI, MBB: ParentBlock, BreakPHIEdge, AllSuccessors);
1877
1878 // If there are no outputs, it must have side-effects.
1879 if (!SuccToSinkTo)
1880 return false;
1881
1882 // If the instruction to move defines a dead physical register which is live
1883 // when leaving the basic block, don't move it because it could turn into a
1884 // "zombie" define of that preg. E.g., EFLAGS.
1885 for (const MachineOperand &MO : MI.all_defs()) {
1886 Register Reg = MO.getReg();
1887 if (Reg == 0 || !Reg.isPhysical())
1888 continue;
1889 if (SuccToSinkTo->isLiveIn(Reg))
1890 return false;
1891 }
1892
1893 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1894
1895 // If the block has multiple predecessors, this is a critical edge.
1896 // Decide if we can sink along it or need to break the edge.
1897 if (SuccToSinkTo->pred_size() > 1) {
1898 // We cannot sink a load across a critical edge - there may be stores in
1899 // other code paths.
1900 bool TryBreak = false;
1901 bool Store =
1902 MI.mayLoad() ? hasStoreBetween(From: ParentBlock, To: SuccToSinkTo, MI) : true;
1903 if (!MI.isSafeToMove(SawStore&: Store)) {
1904 LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1905 TryBreak = true;
1906 }
1907
1908 // We don't want to sink across a critical edge if we don't dominate the
1909 // successor. We could be introducing calculations to new code paths.
1910 if (!TryBreak && !DT->dominates(A: ParentBlock, B: SuccToSinkTo)) {
1911 LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1912 TryBreak = true;
1913 }
1914
1915 // Don't sink instructions into a cycle.
1916 if (!TryBreak && CI->getCycle(Block: SuccToSinkTo) &&
1917 (!CI->isReducible(C: CI->getCycle(Block: SuccToSinkTo)) ||
1918 CI->getHeader(C: CI->getCycle(Block: SuccToSinkTo)) == SuccToSinkTo)) {
1919 LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");
1920 TryBreak = true;
1921 }
1922
1923 // Otherwise we are OK with sinking along a critical edge.
1924 if (!TryBreak)
1925 LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1926 else {
1927 // Mark this edge as to be split.
1928 // If the edge can actually be split, the next iteration of the main loop
1929 // will sink MI in the newly created block.
1930 bool Status = PostponeSplitCriticalEdge(MI, FromBB: ParentBlock, ToBB: SuccToSinkTo,
1931 BreakPHIEdge);
1932 if (!Status)
1933 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1934 "break critical edge\n");
1935 // The instruction will not be sunk this time.
1936 return false;
1937 }
1938 }
1939
1940 if (BreakPHIEdge) {
1941 // BreakPHIEdge is true if all the uses are in the successor MBB being
1942 // sunken into and they are all PHI nodes. In this case, machine-sink must
1943 // break the critical edge first.
1944 bool Status =
1945 PostponeSplitCriticalEdge(MI, FromBB: ParentBlock, ToBB: SuccToSinkTo, BreakPHIEdge);
1946 if (!Status)
1947 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1948 "break critical edge\n");
1949 // The instruction will not be sunk this time.
1950 return false;
1951 }
1952
1953 // Determine where to insert into. Skip phi nodes.
1954 MachineBasicBlock::iterator InsertPos =
1955 SuccToSinkTo->SkipPHIsAndLabels(I: SuccToSinkTo->begin());
1956 if (blockPrologueInterferes(BB: SuccToSinkTo, End: InsertPos, MI, TRI, TII, MRI)) {
1957 LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
1958 return false;
1959 }
1960
1961 // Collect debug users of any vreg that this inst defines.
1962 SmallVector<MIRegs, 4> DbgUsersToSink;
1963 for (auto &MO : MI.all_defs()) {
1964 if (!MO.getReg().isVirtual())
1965 continue;
1966 auto It = SeenDbgUsers.find(Val: MO.getReg());
1967 if (It == SeenDbgUsers.end())
1968 continue;
1969
1970 // Sink any users that don't pass any other DBG_VALUEs for this variable.
1971 auto &Users = It->second;
1972 for (auto &User : Users) {
1973 MachineInstr *DbgMI = User.getPointer();
1974 if (User.getInt()) {
1975 // This DBG_VALUE would re-order assignments. If we can't copy-propagate
1976 // it, it can't be recovered. Set it undef.
1977 if (!attemptDebugCopyProp(SinkInst&: MI, DbgMI&: *DbgMI, Reg: MO.getReg()))
1978 DbgMI->setDebugValueUndef();
1979 } else {
1980 DbgUsersToSink.push_back(
1981 Elt: {DbgMI, SmallVector<Register, 2>(1, MO.getReg())});
1982 }
1983 }
1984 }
1985
1986 // After sinking, some debug users may not be dominated any more. If possible,
1987 // copy-propagate their operands. As it's expensive, don't do this if there's
1988 // no debuginfo in the program.
1989 if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1990 SalvageUnsunkDebugUsersOfCopy(MI, TargetBlock: SuccToSinkTo);
1991
1992 performSink(MI, SuccToSinkTo&: *SuccToSinkTo, InsertPos, DbgValuesToSink: DbgUsersToSink);
1993
1994 // Conservatively, clear any kill flags, since it's possible that they are no
1995 // longer correct.
1996 // Note that we have to clear the kill flags for any register this instruction
1997 // uses as we may sink over another instruction which currently kills the
1998 // used registers.
1999 for (MachineOperand &MO : MI.all_uses())
2000 RegsToClearKillFlags.insert(V: MO.getReg()); // Remember to clear kill flags.
2001
2002 return true;
2003}
2004
2005void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
2006 MachineInstr &MI, MachineBasicBlock *TargetBlock) {
2007 assert(MI.isCopy());
2008 assert(MI.getOperand(1).isReg());
2009
2010 // Enumerate all users of vreg operands that are def'd. Skip those that will
2011 // be sunk. For the rest, if they are not dominated by the block we will sink
2012 // MI into, propagate the copy source to them.
2013 SmallVector<MachineInstr *, 4> DbgDefUsers;
2014 SmallVector<Register, 4> DbgUseRegs;
2015 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
2016 for (auto &MO : MI.all_defs()) {
2017 if (!MO.getReg().isVirtual())
2018 continue;
2019 DbgUseRegs.push_back(Elt: MO.getReg());
2020 for (auto &User : MRI.use_instructions(Reg: MO.getReg())) {
2021 if (!User.isDebugValue() || DT->dominates(A: TargetBlock, B: User.getParent()))
2022 continue;
2023
2024 // If is in same block, will either sink or be use-before-def.
2025 if (User.getParent() == MI.getParent())
2026 continue;
2027
2028 assert(User.hasDebugOperandForReg(MO.getReg()) &&
2029 "DBG_VALUE user of vreg, but has no operand for it?");
2030 DbgDefUsers.push_back(Elt: &User);
2031 }
2032 }
2033
2034 // Point the users of this copy that are no longer dominated, at the source
2035 // of the copy.
2036 for (auto *User : DbgDefUsers) {
2037 for (auto &Reg : DbgUseRegs) {
2038 for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {
2039 DbgOp.setReg(MI.getOperand(i: 1).getReg());
2040 DbgOp.setSubReg(MI.getOperand(i: 1).getSubReg());
2041 }
2042 }
2043 }
2044}
2045
2046//===----------------------------------------------------------------------===//
2047// This pass is not intended to be a replacement or a complete alternative
2048// for the pre-ra machine sink pass. It is only designed to sink COPY
2049// instructions which should be handled after RA.
2050//
2051// This pass sinks COPY instructions into a successor block, if the COPY is not
2052// used in the current block and the COPY is live-in to a single successor
2053// (i.e., doesn't require the COPY to be duplicated). This avoids executing the
2054// copy on paths where their results aren't needed. This also exposes
2055// additional opportunites for dead copy elimination and shrink wrapping.
2056//
2057// These copies were either not handled by or are inserted after the MachineSink
2058// pass. As an example of the former case, the MachineSink pass cannot sink
2059// COPY instructions with allocatable source registers; for AArch64 these type
2060// of copy instructions are frequently used to move function parameters (PhyReg)
2061// into virtual registers in the entry block.
2062//
2063// For the machine IR below, this pass will sink %w19 in the entry into its
2064// successor (%bb.1) because %w19 is only live-in in %bb.1.
2065// %bb.0:
2066// %wzr = SUBSWri %w1, 1
2067// %w19 = COPY %w0
2068// Bcc 11, %bb.2
2069// %bb.1:
2070// Live Ins: %w19
2071// BL @fun
2072// %w0 = ADDWrr %w0, %w19
2073// RET %w0
2074// %bb.2:
2075// %w0 = COPY %wzr
2076// RET %w0
2077// As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
2078// able to see %bb.0 as a candidate.
2079//===----------------------------------------------------------------------===//
2080namespace {
2081
2082class PostRAMachineSinkingImpl {
2083 /// Track which register units have been modified and used.
2084 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
2085
2086 /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
2087 /// entry in this map for each unit it touches. The DBG_VALUE's entry
2088 /// consists of a pointer to the instruction itself, and a vector of registers
2089 /// referred to by the instruction that overlap the key register unit.
2090 DenseMap<MCRegUnit, SmallVector<MIRegs, 2>> SeenDbgInstrs;
2091
2092 /// Sink Copy instructions unused in the same block close to their uses in
2093 /// successors.
2094 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
2095 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
2096
2097public:
2098 bool run(MachineFunction &MF);
2099};
2100
2101class PostRAMachineSinkingLegacy : public MachineFunctionPass {
2102public:
2103 bool runOnMachineFunction(MachineFunction &MF) override;
2104
2105 static char ID;
2106 PostRAMachineSinkingLegacy() : MachineFunctionPass(ID) {}
2107 StringRef getPassName() const override { return "PostRA Machine Sink"; }
2108
2109 void getAnalysisUsage(AnalysisUsage &AU) const override {
2110 AU.setPreservesCFG();
2111 MachineFunctionPass::getAnalysisUsage(AU);
2112 }
2113
2114 MachineFunctionProperties getRequiredProperties() const override {
2115 return MachineFunctionProperties().setNoVRegs();
2116 }
2117};
2118
2119} // namespace
2120
2121char PostRAMachineSinkingLegacy::ID = 0;
2122char &llvm::PostRAMachineSinkingID = PostRAMachineSinkingLegacy::ID;
2123
2124INITIALIZE_PASS(PostRAMachineSinkingLegacy, "postra-machine-sink",
2125 "PostRA Machine Sink", false, false)
2126
2127static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, Register Reg,
2128 const TargetRegisterInfo *TRI) {
2129 LiveRegUnits LiveInRegUnits(*TRI);
2130 LiveInRegUnits.addLiveIns(MBB);
2131 return !LiveInRegUnits.available(Reg);
2132}
2133
2134static MachineBasicBlock *
2135getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
2136 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
2137 Register Reg, const TargetRegisterInfo *TRI) {
2138 // Try to find a single sinkable successor in which Reg is live-in.
2139 MachineBasicBlock *BB = nullptr;
2140 for (auto *SI : SinkableBBs) {
2141 if (aliasWithRegsInLiveIn(MBB&: *SI, Reg, TRI)) {
2142 // If BB is set here, Reg is live-in to at least two sinkable successors,
2143 // so quit.
2144 if (BB)
2145 return nullptr;
2146 BB = SI;
2147 }
2148 }
2149 // Reg is not live-in to any sinkable successors.
2150 if (!BB)
2151 return nullptr;
2152
2153 // Check if any register aliased with Reg is live-in in other successors.
2154 for (auto *SI : CurBB.successors()) {
2155 if (!SinkableBBs.count(Ptr: SI) && aliasWithRegsInLiveIn(MBB&: *SI, Reg, TRI))
2156 return nullptr;
2157 }
2158 return BB;
2159}
2160
2161static MachineBasicBlock *
2162getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
2163 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
2164 ArrayRef<Register> DefedRegsInCopy,
2165 const TargetRegisterInfo *TRI) {
2166 MachineBasicBlock *SingleBB = nullptr;
2167 for (auto DefReg : DefedRegsInCopy) {
2168 MachineBasicBlock *BB =
2169 getSingleLiveInSuccBB(CurBB, SinkableBBs, Reg: DefReg, TRI);
2170 if (!BB || (SingleBB && SingleBB != BB))
2171 return nullptr;
2172 SingleBB = BB;
2173 }
2174 return SingleBB;
2175}
2176
2177static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
2178 const SmallVectorImpl<unsigned> &UsedOpsInCopy,
2179 const LiveRegUnits &UsedRegUnits,
2180 const TargetRegisterInfo *TRI) {
2181 for (auto U : UsedOpsInCopy) {
2182 MachineOperand &MO = MI->getOperand(i: U);
2183 Register SrcReg = MO.getReg();
2184 if (!UsedRegUnits.available(Reg: SrcReg)) {
2185 MachineBasicBlock::iterator NI = std::next(x: MI->getIterator());
2186 for (MachineInstr &UI : make_range(x: NI, y: CurBB.end())) {
2187 if (UI.killsRegister(Reg: SrcReg, TRI)) {
2188 UI.clearRegisterKills(Reg: SrcReg, RegInfo: TRI);
2189 MO.setIsKill(true);
2190 break;
2191 }
2192 }
2193 }
2194 }
2195}
2196
2197static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
2198 const SmallVectorImpl<unsigned> &UsedOpsInCopy,
2199 const SmallVectorImpl<Register> &DefedRegsInCopy) {
2200 for (Register DefReg : DefedRegsInCopy)
2201 SuccBB->removeLiveInOverlappedWith(Reg: DefReg);
2202
2203 for (auto U : UsedOpsInCopy)
2204 SuccBB->addLiveIn(PhysReg: MI->getOperand(i: U).getReg());
2205 SuccBB->sortUniqueLiveIns();
2206}
2207
2208static bool hasRegisterDependency(MachineInstr *MI,
2209 SmallVectorImpl<unsigned> &UsedOpsInCopy,
2210 SmallVectorImpl<Register> &DefedRegsInCopy,
2211 LiveRegUnits &ModifiedRegUnits,
2212 LiveRegUnits &UsedRegUnits) {
2213 bool HasRegDependency = false;
2214 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2215 MachineOperand &MO = MI->getOperand(i);
2216 if (!MO.isReg())
2217 continue;
2218 Register Reg = MO.getReg();
2219 if (!Reg)
2220 continue;
2221 if (MO.isDef()) {
2222 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
2223 HasRegDependency = true;
2224 break;
2225 }
2226 DefedRegsInCopy.push_back(Elt: Reg);
2227
2228 // FIXME: instead of isUse(), readsReg() would be a better fix here,
2229 // For example, we can ignore modifications in reg with undef. However,
2230 // it's not perfectly clear if skipping the internal read is safe in all
2231 // other targets.
2232 } else if (MO.isUse()) {
2233 if (!ModifiedRegUnits.available(Reg)) {
2234 HasRegDependency = true;
2235 break;
2236 }
2237 UsedOpsInCopy.push_back(Elt: i);
2238 }
2239 }
2240 return HasRegDependency;
2241}
2242
2243bool PostRAMachineSinkingImpl::tryToSinkCopy(MachineBasicBlock &CurBB,
2244 MachineFunction &MF,
2245 const TargetRegisterInfo *TRI,
2246 const TargetInstrInfo *TII) {
2247 SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
2248 // FIXME: For now, we sink only to a successor which has a single predecessor
2249 // so that we can directly sink COPY instructions to the successor without
2250 // adding any new block or branch instruction.
2251 for (MachineBasicBlock *SI : CurBB.successors())
2252 if (!SI->livein_empty() && SI->pred_size() == 1)
2253 SinkableBBs.insert(Ptr: SI);
2254
2255 if (SinkableBBs.empty())
2256 return false;
2257
2258 bool Changed = false;
2259
2260 // Track which registers have been modified and used between the end of the
2261 // block and the current instruction.
2262 ModifiedRegUnits.clear();
2263 UsedRegUnits.clear();
2264 SeenDbgInstrs.clear();
2265
2266 for (MachineInstr &MI : llvm::make_early_inc_range(Range: llvm::reverse(C&: CurBB))) {
2267 // Track the operand index for use in Copy.
2268 SmallVector<unsigned, 2> UsedOpsInCopy;
2269 // Track the register number defed in Copy.
2270 SmallVector<Register, 2> DefedRegsInCopy;
2271
2272 // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
2273 // for DBG_VALUEs later, record them when they're encountered.
2274 if (MI.isDebugValue() && !MI.isDebugRef()) {
2275 SmallDenseMap<MCRegUnit, SmallVector<Register, 2>, 4> MIUnits;
2276 bool IsValid = true;
2277 for (MachineOperand &MO : MI.debug_operands()) {
2278 if (MO.isReg() && MO.getReg().isPhysical()) {
2279 // Bail if we can already tell the sink would be rejected, rather
2280 // than needlessly accumulating lots of DBG_VALUEs.
2281 if (hasRegisterDependency(MI: &MI, UsedOpsInCopy, DefedRegsInCopy,
2282 ModifiedRegUnits, UsedRegUnits)) {
2283 IsValid = false;
2284 break;
2285 }
2286
2287 // Record debug use of each reg unit.
2288 for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg()))
2289 MIUnits[Unit].push_back(Elt: MO.getReg());
2290 }
2291 }
2292 if (IsValid) {
2293 for (auto &RegOps : MIUnits)
2294 SeenDbgInstrs[RegOps.first].emplace_back(Args: &MI,
2295 Args: std::move(RegOps.second));
2296 }
2297 continue;
2298 }
2299
2300 // Don't postRASink instructions that the target prefers not to sink.
2301 if (!TII->shouldPostRASink(MI))
2302 continue;
2303
2304 if (MI.isDebugOrPseudoInstr())
2305 continue;
2306
2307 // Do not move any instruction across function call.
2308 if (MI.isCall())
2309 return false;
2310
2311 if (!MI.isCopy() || !MI.getOperand(i: 0).isRenamable()) {
2312 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2313 TRI);
2314 continue;
2315 }
2316
2317 // Don't sink the COPY if it would violate a register dependency.
2318 if (hasRegisterDependency(MI: &MI, UsedOpsInCopy, DefedRegsInCopy,
2319 ModifiedRegUnits, UsedRegUnits)) {
2320 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2321 TRI);
2322 continue;
2323 }
2324 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
2325 "Unexpect SrcReg or DefReg");
2326 MachineBasicBlock *SuccBB =
2327 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
2328 // Don't sink if we cannot find a single sinkable successor in which Reg
2329 // is live-in.
2330 if (!SuccBB) {
2331 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2332 TRI);
2333 continue;
2334 }
2335 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
2336 "Unexpected predecessor");
2337
2338 // Collect DBG_VALUEs that must sink with this copy. We've previously
2339 // recorded which reg units that DBG_VALUEs read, if this instruction
2340 // writes any of those units then the corresponding DBG_VALUEs must sink.
2341 MapVector<MachineInstr *, MIRegs::second_type> DbgValsToSinkMap;
2342 for (auto &MO : MI.all_defs()) {
2343 for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg())) {
2344 for (const auto &MIRegs : SeenDbgInstrs.lookup(Val: Unit)) {
2345 auto &Regs = DbgValsToSinkMap[MIRegs.first];
2346 llvm::append_range(C&: Regs, R: MIRegs.second);
2347 }
2348 }
2349 }
2350 auto DbgValsToSink = DbgValsToSinkMap.takeVector();
2351
2352 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
2353
2354 MachineBasicBlock::iterator InsertPos =
2355 SuccBB->SkipPHIsAndLabels(I: SuccBB->begin());
2356 if (blockPrologueInterferes(BB: SuccBB, End: InsertPos, MI, TRI, TII, MRI: nullptr)) {
2357 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2358 TRI);
2359 LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
2360 continue;
2361 }
2362
2363 // Clear the kill flag if SrcReg is killed between MI and the end of the
2364 // block.
2365 clearKillFlags(MI: &MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
2366 performSink(MI, SuccToSinkTo&: *SuccBB, InsertPos, DbgValuesToSink: DbgValsToSink);
2367 updateLiveIn(MI: &MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
2368
2369 Changed = true;
2370 ++NumPostRACopySink;
2371 }
2372 return Changed;
2373}
2374
2375bool PostRAMachineSinkingImpl::run(MachineFunction &MF) {
2376 bool Changed = false;
2377 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2378 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
2379
2380 ModifiedRegUnits.init(TRI: *TRI);
2381 UsedRegUnits.init(TRI: *TRI);
2382 for (auto &BB : MF)
2383 Changed |= tryToSinkCopy(CurBB&: BB, MF, TRI, TII);
2384
2385 return Changed;
2386}
2387
2388bool PostRAMachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {
2389 if (skipFunction(F: MF.getFunction()))
2390 return false;
2391
2392 return PostRAMachineSinkingImpl().run(MF);
2393}
2394
2395PreservedAnalyses
2396PostRAMachineSinkingPass::run(MachineFunction &MF,
2397 MachineFunctionAnalysisManager &MFAM) {
2398 MFPropsModifier _(*this, MF);
2399
2400 if (!PostRAMachineSinkingImpl().run(MF))
2401 return PreservedAnalyses::all();
2402
2403 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
2404 PA.preserveSet<CFGAnalyses>();
2405 return PA;
2406}
2407