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