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;
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 : DT(DT), PDT(PDT), CI(CI), PSI(PSI), MBFI(MBFI), MBPI(MBPI), AA(AA),
209 LIS(LIS), SI(SI), LV(LV), MLI(MLI),
210 EnableSinkAndFold(EnableSinkAndFold) {}
211
212 bool run(MachineFunction &MF);
213
214 void releaseMemory() {
215 CEBCandidates.clear();
216 CEMergeCandidates.clear();
217 }
218
219private:
220 bool ProcessBlock(MachineBasicBlock &MBB);
221 void ProcessDbgInst(MachineInstr &MI);
222 bool isLegalToBreakCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
223 MachineBasicBlock *To, bool BreakPHIEdge);
224 bool isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
225 MachineBasicBlock *To,
226 MachineBasicBlock *&DeferredFromBlock);
227
228 bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
229 MachineInstr &MI);
230
231 /// Postpone the splitting of the given critical
232 /// edge (\p From, \p To).
233 ///
234 /// We do not split the edges on the fly. Indeed, this invalidates
235 /// the dominance information and thus triggers a lot of updates
236 /// of that information underneath.
237 /// Instead, we postpone all the splits after each iteration of
238 /// the main loop. That way, the information is at least valid
239 /// for the lifetime of an iteration.
240 ///
241 /// \return True if the edge is marked as toSplit, false otherwise.
242 /// False can be returned if, for instance, this is not profitable.
243 bool PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
244 MachineBasicBlock *To, bool BreakPHIEdge);
245 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
246 AllSuccsCache &AllSuccessors);
247
248 /// If we sink a COPY inst, some debug users of it's destination may no
249 /// longer be dominated by the COPY, and will eventually be dropped.
250 /// This is easily rectified by forwarding the non-dominated debug uses
251 /// to the copy source.
252 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
253 MachineBasicBlock *TargetBlock);
254 bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
255 MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
256 bool &LocalUse) const;
257 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
258 bool &BreakPHIEdge,
259 AllSuccsCache &AllSuccessors);
260
261 void FindCycleSinkCandidates(CycleRef Cycle, MachineBasicBlock *BB,
262 SmallVectorImpl<MachineInstr *> &Candidates);
263
264 bool
265 aggressivelySinkIntoCycle(CycleRef Cycle, MachineInstr &I,
266 DenseMap<SinkItem, MachineInstr *> &SunkInstrs);
267
268 bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
269 MachineBasicBlock *MBB,
270 MachineBasicBlock *SuccToSinkTo,
271 AllSuccsCache &AllSuccessors);
272
273 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
274 MachineBasicBlock *MBB);
275
276 bool PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB);
277
278 SmallVector<MachineBasicBlock *, 4> &
279 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
280 AllSuccsCache &AllSuccessors) const;
281
282 std::vector<unsigned> &getBBRegisterPressure(const MachineBasicBlock &MBB,
283 bool UseCache = true);
284
285 bool registerPressureSetExceedsLimit(unsigned NRegs,
286 const TargetRegisterClass *RC,
287 const MachineBasicBlock &MBB);
288
289 bool registerPressureExceedsLimit(const MachineBasicBlock &MBB);
290};
291
292class MachineSinkingLegacy : public MachineFunctionPass {
293public:
294 static char ID;
295
296 MachineSinkingLegacy() : MachineFunctionPass(ID) {}
297
298 bool runOnMachineFunction(MachineFunction &MF) override;
299
300 void getAnalysisUsage(AnalysisUsage &AU) const override {
301 MachineFunctionPass::getAnalysisUsage(AU);
302 AU.addRequired<AAResultsWrapperPass>();
303 AU.addRequired<MachineDominatorTreeWrapperPass>();
304 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
305 AU.addRequired<MachineCycleInfoWrapperPass>();
306 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
307 AU.addPreserved<MachineCycleInfoWrapperPass>();
308 AU.addPreserved<MachineLoopInfoWrapperPass>();
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(AAResultsWrapperPass)
331INITIALIZE_PASS_END(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",
332 false, false)
333
334/// Return true if a target defined block prologue instruction interferes
335/// with a sink candidate.
336static bool blockPrologueInterferes(const MachineBasicBlock *BB,
337 MachineBasicBlock::const_iterator End,
338 const MachineInstr &MI,
339 const TargetRegisterInfo *TRI,
340 const TargetInstrInfo *TII,
341 const MachineRegisterInfo *MRI) {
342 for (MachineBasicBlock::const_iterator PI = BB->getFirstNonPHI(); PI != End;
343 ++PI) {
344 // Only check target defined prologue instructions
345 if (!TII->isBasicBlockPrologue(MI: *PI))
346 continue;
347 for (auto &MO : MI.operands()) {
348 if (!MO.isReg())
349 continue;
350 Register Reg = MO.getReg();
351 if (!Reg)
352 continue;
353 if (MO.isUse()) {
354 if (Reg.isPhysical() &&
355 (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(PhysReg: Reg))))
356 continue;
357 if (PI->modifiesRegister(Reg, TRI))
358 return true;
359 } else {
360 if (PI->readsRegister(Reg, TRI))
361 return true;
362 // Check for interference with non-dead defs
363 auto *DefOp = PI->findRegisterDefOperand(Reg, TRI, isDead: false, Overlap: true);
364 if (DefOp && !DefOp->isDead())
365 return true;
366 }
367 }
368 }
369
370 return false;
371}
372
373bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
374 MachineBasicBlock *MBB) {
375 if (!MI.isCopy())
376 return false;
377
378 Register SrcReg = MI.getOperand(i: 1).getReg();
379 Register DstReg = MI.getOperand(i: 0).getReg();
380 if (!SrcReg.isVirtual() || !DstReg.isVirtual() ||
381 !MRI->hasOneNonDBGUse(RegNo: SrcReg))
382 return false;
383
384 const TargetRegisterClass *SRC = MRI->getRegClass(Reg: SrcReg);
385 const TargetRegisterClass *DRC = MRI->getRegClass(Reg: DstReg);
386 if (SRC != DRC)
387 return false;
388
389 MachineInstr *DefMI = MRI->getVRegDef(Reg: SrcReg);
390 if (DefMI->isCopyLike())
391 return false;
392 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
393 LLVM_DEBUG(dbgs() << "*** to: " << MI);
394 MRI->replaceRegWith(FromReg: DstReg, ToReg: SrcReg);
395 MI.eraseFromParent();
396
397 // Conservatively, clear any kill flags, since it's possible that they are no
398 // longer correct.
399 MRI->clearKillFlags(Reg: SrcReg);
400
401 ++NumCoalesces;
402 return true;
403}
404
405bool MachineSinking::PerformSinkAndFold(MachineInstr &MI,
406 MachineBasicBlock *MBB) {
407 if (MI.isCopy() || MI.mayLoadOrStore() ||
408 MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
409 return false;
410
411 // Don't sink instructions that the target prefers not to sink.
412 if (!TII->shouldSink(MI))
413 return false;
414
415 // Check if it's safe to move the instruction.
416 bool SawStore = true;
417 if (!MI.isSafeToMove(SawStore))
418 return false;
419
420 // Convergent operations may not be made control-dependent on additional
421 // values.
422 if (MI.isConvergent())
423 return false;
424
425 // Don't sink defs/uses of hard registers or if the instruction defines more
426 // than one register.
427 // Don't sink more than two register uses - it'll cover most of the cases and
428 // greatly simplifies the register pressure checks.
429 Register DefReg;
430 Register UsedRegA, UsedRegB;
431 for (const MachineOperand &MO : MI.operands()) {
432 if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
433 MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
434 MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
435 continue;
436 if (!MO.isReg())
437 return false;
438
439 Register Reg = MO.getReg();
440 if (Reg == 0)
441 continue;
442
443 if (Reg.isVirtual()) {
444 if (MO.isDef()) {
445 if (DefReg)
446 return false;
447 DefReg = Reg;
448 continue;
449 }
450
451 if (UsedRegA == 0)
452 UsedRegA = Reg;
453 else if (UsedRegB == 0)
454 UsedRegB = Reg;
455 else
456 return false;
457 continue;
458 }
459
460 if (Reg.isPhysical() && MO.isUse() &&
461 (MRI->isConstantPhysReg(PhysReg: Reg) || TII->isIgnorableUse(MO)))
462 continue;
463
464 return false;
465 }
466
467 // Scan uses of the destination register. Every use, except the last, must be
468 // a copy, with a chain of copies terminating with either a copy into a hard
469 // register, or a load/store instruction where the use is part of the
470 // address (*not* the stored value).
471 using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
472 SmallVector<SinkInfo> SinkInto;
473 SmallVector<Register> Worklist;
474
475 const TargetRegisterClass *RC = MRI->getRegClass(Reg: DefReg);
476 const TargetRegisterClass *RCA =
477 UsedRegA == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegA);
478 const TargetRegisterClass *RCB =
479 UsedRegB == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegB);
480
481 Worklist.push_back(Elt: DefReg);
482 while (!Worklist.empty()) {
483 Register Reg = Worklist.pop_back_val();
484
485 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
486 ExtAddrMode MaybeAM;
487 MachineInstr &UseInst = *MO.getParent();
488 if (UseInst.isCopy()) {
489 Register DstReg;
490 if (const MachineOperand &O = UseInst.getOperand(i: 0); O.isReg())
491 DstReg = O.getReg();
492 if (DstReg == 0)
493 return false;
494 if (DstReg.isVirtual()) {
495 Worklist.push_back(Elt: DstReg);
496 continue;
497 }
498 // If we are going to replace a copy, the original instruction must be
499 // as cheap as a copy.
500 if (!TII->isAsCheapAsAMove(MI))
501 return false;
502 // The hard register must be in the register class of the original
503 // instruction's destination register.
504 if (!RC->contains(Reg: DstReg))
505 return false;
506 } else if (UseInst.mayLoadOrStore()) {
507 // If the destination instruction contains more than one use of the
508 // register, we won't be able to remove the original instruction, so
509 // don't sink.
510 if (llvm::count_if(Range: UseInst.operands(), P: [Reg](const MachineOperand &MO) {
511 return MO.isReg() && MO.getReg() == Reg;
512 }) > 1)
513 return false;
514 ExtAddrMode AM;
515 if (!TII->canFoldIntoAddrMode(MemI: UseInst, Reg, AddrI: MI, AM))
516 return false;
517 MaybeAM = AM;
518 } else {
519 return false;
520 }
521
522 if (UseInst.getParent() != MI.getParent()) {
523 // If the register class of the register we are replacing is a superset
524 // of any of the register classes of the operands of the materialized
525 // instruction don't consider that live range extended.
526 const TargetRegisterClass *RCS = MRI->getRegClass(Reg);
527 if (RCA && RCA->hasSuperClassEq(RC: RCS))
528 RCA = nullptr;
529 else if (RCB && RCB->hasSuperClassEq(RC: RCS))
530 RCB = nullptr;
531 if (RCA || RCB) {
532 if (RCA == nullptr) {
533 RCA = RCB;
534 RCB = nullptr;
535 }
536
537 unsigned NRegs = !!RCA + !!RCB;
538 if (RCA == RCB)
539 RCB = nullptr;
540
541 // Check we don't exceed register pressure at the destination.
542 const MachineBasicBlock &MBB = *UseInst.getParent();
543 if (RCB == nullptr) {
544 if (registerPressureSetExceedsLimit(NRegs, RC: RCA, MBB))
545 return false;
546 } else if (registerPressureSetExceedsLimit(NRegs: 1, RC: RCA, MBB) ||
547 registerPressureSetExceedsLimit(NRegs: 1, RC: RCB, MBB)) {
548 return false;
549 }
550 }
551 }
552
553 SinkInto.emplace_back(Args: &UseInst, Args&: MaybeAM);
554 }
555 }
556
557 if (SinkInto.empty())
558 return false;
559
560 // Now we know we can fold the instruction in all its users.
561 for (auto &[SinkDst, MaybeAM] : SinkInto) {
562 MachineInstr *New = nullptr;
563 LLVM_DEBUG(dbgs() << "Sinking copy of"; MI.dump(); dbgs() << "into";
564 SinkDst->dump());
565 if (SinkDst->isCopy()) {
566 // TODO: After performing the sink-and-fold, the original instruction is
567 // deleted. Its value is still available (in a hard register), so if there
568 // are debug instructions which refer to the (now deleted) virtual
569 // register they could be updated to refer to the hard register, in
570 // principle. However, it's not clear how to do that, moreover in some
571 // cases the debug instructions may need to be replicated proportionally
572 // to the number of the COPY instructions replaced and in some extreme
573 // cases we can end up with quadratic increase in the number of debug
574 // instructions.
575
576 // Sink a copy of the instruction, replacing a COPY instruction.
577 MachineBasicBlock::iterator InsertPt = SinkDst->getIterator();
578 Register DstReg = SinkDst->getOperand(i: 0).getReg();
579 TII->reMaterialize(MBB&: *SinkDst->getParent(), MI: InsertPt, DestReg: DstReg, SubIdx: 0, Orig: MI);
580 New = &*std::prev(x: InsertPt);
581 if (!New->getDebugLoc())
582 New->setDebugLoc(SinkDst->getDebugLoc());
583
584 // The operand registers of the "sunk" instruction have their live range
585 // extended and their kill flags may no longer be correct. Conservatively
586 // clear the kill flags.
587 if (UsedRegA)
588 MRI->clearKillFlags(Reg: UsedRegA);
589 if (UsedRegB)
590 MRI->clearKillFlags(Reg: UsedRegB);
591 } else {
592 // Fold instruction into the addressing mode of a memory instruction.
593 New = TII->emitLdStWithAddr(MemI&: *SinkDst, AM: MaybeAM);
594
595 // The registers of the addressing mode may have their live range extended
596 // and their kill flags may no longer be correct. Conservatively clear the
597 // kill flags.
598 if (Register R = MaybeAM.BaseReg; R.isValid() && R.isVirtual())
599 MRI->clearKillFlags(Reg: R);
600 if (Register R = MaybeAM.ScaledReg; R.isValid() && R.isVirtual())
601 MRI->clearKillFlags(Reg: R);
602 }
603 LLVM_DEBUG(dbgs() << "yielding"; New->dump());
604 // Clear the StoreInstrCache, since we may invalidate it by erasing.
605 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
606 StoreInstrCache.clear();
607 SinkDst->eraseFromParent();
608 }
609
610 // Collect operands that need to be cleaned up because the registers no longer
611 // exist (in COPYs and debug instructions). We cannot delete instructions or
612 // clear operands while traversing register uses.
613 SmallVector<MachineOperand *> Cleanup;
614 Worklist.push_back(Elt: DefReg);
615 while (!Worklist.empty()) {
616 Register Reg = Worklist.pop_back_val();
617 for (MachineOperand &MO : MRI->use_operands(Reg)) {
618 MachineInstr *U = MO.getParent();
619 assert((U->isCopy() || U->isDebugInstr()) &&
620 "Only debug uses and copies must remain");
621 if (U->isCopy())
622 Worklist.push_back(Elt: U->getOperand(i: 0).getReg());
623 Cleanup.push_back(Elt: &MO);
624 }
625 }
626
627 // Delete the dead COPYs and clear operands in debug instructions
628 for (MachineOperand *MO : Cleanup) {
629 MachineInstr *I = MO->getParent();
630 if (I->isCopy()) {
631 I->eraseFromParent();
632 } else {
633 MO->setReg(0);
634 MO->setSubReg(0);
635 }
636 }
637
638 MI.eraseFromParent();
639 return true;
640}
641
642/// AllUsesDominatedByBlock - Return true if all uses of the specified register
643/// occur in blocks dominated by the specified block. If any use is in the
644/// definition block, then return false since it is never legal to move def
645/// after uses.
646bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
647 MachineBasicBlock *MBB,
648 MachineBasicBlock *DefMBB,
649 bool &BreakPHIEdge,
650 bool &LocalUse) const {
651 assert(Reg.isVirtual() && "Only makes sense for vregs");
652
653 // Ignore debug uses because debug info doesn't affect the code.
654 if (MRI->use_nodbg_empty(RegNo: Reg))
655 return true;
656
657 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
658 // into and they are all PHI nodes. In this case, machine-sink must break
659 // the critical edge first. e.g.
660 //
661 // %bb.1:
662 // Predecessors according to CFG: %bb.0
663 // ...
664 // %def = DEC64_32r %x, implicit-def dead %eflags
665 // ...
666 // JE_4 <%bb.37>, implicit %eflags
667 // Successors according to CFG: %bb.37 %bb.2
668 //
669 // %bb.2:
670 // %p = PHI %y, %bb.0, %def, %bb.1
671 if (all_of(Range: MRI->use_nodbg_operands(Reg), P: [&](MachineOperand &MO) {
672 MachineInstr *UseInst = MO.getParent();
673 unsigned OpNo = MO.getOperandNo();
674 MachineBasicBlock *UseBlock = UseInst->getParent();
675 return UseBlock == MBB && UseInst->isPHI() &&
676 UseInst->getOperand(i: OpNo + 1).getMBB() == DefMBB;
677 })) {
678 BreakPHIEdge = true;
679 return true;
680 }
681
682 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
683 // Determine the block of the use.
684 MachineInstr *UseInst = MO.getParent();
685 unsigned OpNo = &MO - &UseInst->getOperand(i: 0);
686 MachineBasicBlock *UseBlock = UseInst->getParent();
687 if (UseInst->isPHI()) {
688 // PHI nodes use the operand in the predecessor block, not the block with
689 // the PHI.
690 UseBlock = UseInst->getOperand(i: OpNo + 1).getMBB();
691 } else if (UseBlock == DefMBB) {
692 LocalUse = true;
693 return false;
694 }
695
696 // Check that it dominates.
697 if (!DT->dominates(A: MBB, B: UseBlock))
698 return false;
699 }
700
701 return true;
702}
703
704/// Return true if this machine instruction loads from global offset table or
705/// constant pool.
706static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
707 assert(MI.mayLoad() && "Expected MI that loads!");
708
709 // If we lost memory operands, conservatively assume that the instruction
710 // reads from everything..
711 if (MI.memoperands_empty())
712 return true;
713
714 for (MachineMemOperand *MemOp : MI.memoperands())
715 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
716 if (PSV->isGOT() || PSV->isConstantPool())
717 return true;
718
719 return false;
720}
721
722void MachineSinking::FindCycleSinkCandidates(
723 CycleRef Cycle, MachineBasicBlock *BB,
724 SmallVectorImpl<MachineInstr *> &Candidates) {
725 for (auto &MI : *BB) {
726 LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
727 if (MI.isMetaInstruction()) {
728 LLVM_DEBUG(dbgs() << "CycleSink: not sinking meta instruction\n");
729 continue;
730 }
731 if (!TII->shouldSink(MI)) {
732 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
733 "target\n");
734 continue;
735 }
736 if (!isCycleInvariant(CI: *CI, Cycle, I&: MI)) {
737 LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
738 continue;
739 }
740 bool DontMoveAcrossStore = true;
741 if (!MI.isSafeToMove(SawStore&: DontMoveAcrossStore)) {
742 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
743 continue;
744 }
745 if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
746 LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
747 continue;
748 }
749 if (MI.isConvergent())
750 continue;
751
752 const MachineOperand &MO = MI.getOperand(i: 0);
753 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
754 continue;
755 if (!MRI->hasOneDef(RegNo: MO.getReg()))
756 continue;
757
758 LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
759 Candidates.push_back(Elt: &MI);
760 }
761}
762
763PreservedAnalyses
764MachineSinkingPass::run(MachineFunction &MF,
765 MachineFunctionAnalysisManager &MFAM) {
766 auto *DT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
767 auto *PDT = &MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
768 auto *CI = &MFAM.getResult<MachineCycleAnalysis>(IR&: MF);
769 auto *PSI = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
770 .getCachedResult<ProfileSummaryAnalysis>(
771 IR&: *MF.getFunction().getParent());
772 auto *MBFI = UseBlockFreqInfo
773 ? &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF)
774 : nullptr;
775 auto *MBPI = &MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
776 auto *AA = &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
777 .getManager()
778 .getResult<AAManager>(IR&: MF.getFunction());
779 auto *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF);
780 auto *SI = MFAM.getCachedResult<SlotIndexesAnalysis>(IR&: MF);
781 auto *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(IR&: MF);
782 auto *MLI = MFAM.getCachedResult<MachineLoopAnalysis>(IR&: MF);
783 MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,
784 MBFI, MBPI, AA);
785 bool Changed = Impl.run(MF);
786 if (!Changed)
787 return PreservedAnalyses::all();
788 auto PA = getMachineFunctionPassPreservedAnalyses();
789 PA.preserve<MachineCycleAnalysis>();
790 PA.preserve<MachineLoopAnalysis>();
791 if (UseBlockFreqInfo)
792 PA.preserve<MachineBlockFrequencyAnalysis>();
793 return PA;
794}
795
796void MachineSinkingPass::printPipeline(
797 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
798 OS << MapClassName2PassName(name()); // ideally machine-sink
799 if (EnableSinkAndFold)
800 OS << "<enable-sink-fold>";
801}
802
803bool MachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {
804 if (skipFunction(F: MF.getFunction()))
805 return false;
806
807 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
808 bool EnableSinkAndFold = PassConfig->getEnableSinkAndFold();
809
810 auto *DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
811 auto *PDT =
812 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
813 auto *CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
814 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
815 auto *MBFI =
816 UseBlockFreqInfo
817 ? &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI()
818 : nullptr;
819 auto *MBPI =
820 &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
821 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
822 // Get analyses for split critical edge.
823 auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
824 auto *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
825 auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();
826 auto *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;
827 auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();
828 auto *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
829 auto *MLIWrapper = getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
830 auto *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
831
832 MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,
833 MBFI, MBPI, AA);
834 return Impl.run(MF);
835}
836
837bool MachineSinking::run(MachineFunction &MF) {
838 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
839
840 STI = &MF.getSubtarget();
841 TII = STI->getInstrInfo();
842 TRI = STI->getRegisterInfo();
843 MRI = &MF.getRegInfo();
844
845 RegClassInfo.runOnMachineFunction(MF);
846
847 bool EverMadeChange = false;
848
849 while (true) {
850 bool MadeChange = false;
851
852 // Process all basic blocks.
853 CEBCandidates.clear();
854 CEMergeCandidates.clear();
855 ToSplit.clear();
856 for (auto &MBB : MF)
857 MadeChange |= ProcessBlock(MBB);
858
859 // If we have anything we marked as toSplit, split it now.
860 MachineDomTreeUpdater MDTU(DT, PDT,
861 MachineDomTreeUpdater::UpdateStrategy::Lazy);
862 for (const auto &Pair : ToSplit) {
863 auto NewSucc = Pair.first->SplitCriticalEdge(
864 Succ: Pair.second, Analyses: {.LIS: LIS, .SI: SI, .LV: LV, .MLI: MLI}, LiveInSets: nullptr, MDTU: &MDTU);
865 if (NewSucc != nullptr) {
866 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
867 << printMBBReference(*Pair.first) << " -- "
868 << printMBBReference(*NewSucc) << " -- "
869 << printMBBReference(*Pair.second) << '\n');
870 if (MBFI)
871 MBFI->onEdgeSplit(NewPredecessor: *Pair.first, NewSuccessor: *NewSucc, MBPI: *MBPI);
872
873 MadeChange = true;
874 ++NumSplit;
875 CI->splitCriticalEdge(Pred: Pair.first, Succ: Pair.second, New: NewSucc);
876 } else
877 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
878 }
879 // If this iteration over the code changed anything, keep iterating.
880 if (!MadeChange)
881 break;
882 EverMadeChange = true;
883 }
884
885 if (SinkInstsIntoCycle) {
886 SmallVector<CycleRef, 8> Cycles(CI->toplevel_cycles());
887 SchedModel.init(TSInfo: STI);
888 bool HasHighPressure;
889
890 DenseMap<SinkItem, MachineInstr *> SunkInstrs;
891
892 enum CycleSinkStage { COPY, LOW_LATENCY, AGGRESSIVE, END };
893 for (unsigned Stage = CycleSinkStage::COPY; Stage != CycleSinkStage::END;
894 ++Stage, SunkInstrs.clear()) {
895 HasHighPressure = false;
896
897 for (auto Cycle : Cycles) {
898 MachineBasicBlock *Preheader = CI->getCyclePreheader(C: Cycle);
899 if (!Preheader) {
900 LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
901 continue;
902 }
903 SmallVector<MachineInstr *, 8> Candidates;
904 FindCycleSinkCandidates(Cycle, BB: Preheader, Candidates);
905
906 unsigned i = 0;
907
908 // Walk the candidates in reverse order so that we start with the use
909 // of a def-use chain, if there is any.
910 // TODO: Sort the candidates using a cost-model.
911 for (MachineInstr *I : llvm::reverse(C&: Candidates)) {
912 // CycleSinkStage::COPY: Sink a limited number of copies
913 if (Stage == CycleSinkStage::COPY) {
914 if (i++ == SinkIntoCycleLimit) {
915 LLVM_DEBUG(dbgs()
916 << "CycleSink: Limit reached of instructions to "
917 "be analyzed.");
918 break;
919 }
920
921 if (!I->isCopy())
922 continue;
923 }
924
925 // CycleSinkStage::LOW_LATENCY: sink unlimited number of instructions
926 // which the target specifies as low-latency
927 if (Stage == CycleSinkStage::LOW_LATENCY &&
928 !TII->hasLowDefLatency(SchedModel, DefMI: *I, DefIdx: 0))
929 continue;
930
931 if (!aggressivelySinkIntoCycle(Cycle, I&: *I, SunkInstrs))
932 continue;
933 EverMadeChange = true;
934 ++NumCycleSunk;
935 }
936
937 // Recalculate the pressure after sinking
938 if (!HasHighPressure)
939 HasHighPressure = registerPressureExceedsLimit(MBB: *Preheader);
940 }
941 if (!HasHighPressure)
942 break;
943 }
944 }
945
946 HasStoreCache.clear();
947 StoreInstrCache.clear();
948
949 // Now clear any kill flags for recorded registers.
950 for (auto I : RegsToClearKillFlags)
951 MRI->clearKillFlags(Reg: I);
952 RegsToClearKillFlags.clear();
953
954 releaseMemory();
955 return EverMadeChange;
956}
957
958bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
959 if ((!EnableSinkAndFold && MBB.succ_size() <= 1) || MBB.empty())
960 return false;
961
962 // Don't bother sinking code out of unreachable blocks. In addition to being
963 // unprofitable, it can also lead to infinite looping, because in an
964 // unreachable cycle there may be nowhere to stop.
965 if (!DT->isReachableFromEntry(A: &MBB))
966 return false;
967
968 bool MadeChange = false;
969
970 // Cache all successors, sorted by frequency info and cycle depth.
971 AllSuccsCache AllSuccessors;
972
973 // Walk the basic block bottom-up. Remember if we saw a store.
974 MachineBasicBlock::iterator I = MBB.end();
975 --I;
976 bool ProcessedBegin, SawStore = false;
977 do {
978 MachineInstr &MI = *I; // The instruction to sink.
979
980 // Predecrement I (if it's not begin) so that it isn't invalidated by
981 // sinking.
982 ProcessedBegin = I == MBB.begin();
983 if (!ProcessedBegin)
984 --I;
985
986 if (MI.isDebugOrPseudoInstr() || MI.isFakeUse()) {
987 if (MI.isDebugValue())
988 ProcessDbgInst(MI);
989 continue;
990 }
991
992 if (EnableSinkAndFold && PerformSinkAndFold(MI, MBB: &MBB)) {
993 MadeChange = true;
994 continue;
995 }
996
997 // Can't sink anything out of a block that has less than two successors.
998 if (MBB.succ_size() <= 1)
999 continue;
1000
1001 if (PerformTrivialForwardCoalescing(MI, MBB: &MBB)) {
1002 MadeChange = true;
1003 continue;
1004 }
1005
1006 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
1007 ++NumSunk;
1008 MadeChange = true;
1009 }
1010
1011 // If we just processed the first instruction in the block, we're done.
1012 } while (!ProcessedBegin);
1013
1014 SeenDbgUsers.clear();
1015 SeenDbgVars.clear();
1016 // recalculate the bb register pressure after sinking one BB.
1017 CachedRegisterPressure.clear();
1018 return MadeChange;
1019}
1020
1021void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
1022 // When we see DBG_VALUEs for registers, record any vreg it reads, so that
1023 // we know what to sink if the vreg def sinks.
1024 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
1025
1026 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1027 MI.getDebugLoc()->getInlinedAt());
1028 bool SeenBefore = SeenDbgVars.contains(V: Var);
1029
1030 for (MachineOperand &MO : MI.debug_operands()) {
1031 if (MO.isReg() && MO.getReg().isVirtual())
1032 SeenDbgUsers[MO.getReg()].push_back(NewVal: SeenDbgUser(&MI, SeenBefore));
1033 }
1034
1035 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
1036 SeenDbgVars.insert(V: Var);
1037}
1038
1039bool MachineSinking::isWorthBreakingCriticalEdge(
1040 MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To,
1041 MachineBasicBlock *&DeferredFromBlock) {
1042 // FIXME: Need much better heuristics.
1043
1044 // If the pass has already considered breaking this edge (during this pass
1045 // through the function), then let's go ahead and break it. This means
1046 // sinking multiple "cheap" instructions into the same block.
1047 if (!CEBCandidates.insert(V: std::make_pair(x&: From, y&: To)).second)
1048 return true;
1049
1050 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
1051 return true;
1052
1053 // Check and record the register and the destination block we want to sink
1054 // into. Note that we want to do the following before the next check on branch
1055 // probability. Because we want to record the initial candidate even if it's
1056 // on hot edge, so that other candidates that might not on hot edges can be
1057 // sinked as well.
1058 for (const auto &MO : MI.all_defs()) {
1059 Register Reg = MO.getReg();
1060 if (!Reg)
1061 continue;
1062 Register SrcReg = Reg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: Reg, MRI) : Reg;
1063 auto Key = std::make_pair(x&: SrcReg, y&: To);
1064 auto Res = CEMergeCandidates.try_emplace(Key, Args&: From);
1065 // We wanted to sink the same register into the same block, consider it to
1066 // be profitable.
1067 if (!Res.second) {
1068 // Return the source block that was previously held off.
1069 DeferredFromBlock = Res.first->second;
1070 return true;
1071 }
1072 }
1073
1074 if (From->isSuccessor(MBB: To) &&
1075 MBPI->getEdgeProbability(Src: From, Dst: To) <=
1076 BranchProbability(SplitEdgeProbabilityThreshold, 100))
1077 return true;
1078
1079 // MI is cheap, we probably don't want to break the critical edge for it.
1080 // However, if this would allow some definitions of its source operands
1081 // to be sunk then it's probably worth it.
1082 for (const MachineOperand &MO : MI.all_uses()) {
1083 Register Reg = MO.getReg();
1084 if (Reg == 0)
1085 continue;
1086
1087 // We don't move live definitions of physical registers,
1088 // so sinking their uses won't enable any opportunities.
1089 if (Reg.isPhysical())
1090 continue;
1091
1092 // If this instruction is the only user of a virtual register,
1093 // check if breaking the edge will enable sinking
1094 // both this instruction and the defining instruction.
1095 if (MRI->hasOneNonDBGUse(RegNo: Reg)) {
1096 // If the definition resides in same MBB,
1097 // claim it's likely we can sink these together.
1098 // If definition resides elsewhere, we aren't
1099 // blocking it from being sunk so don't break the edge.
1100 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1101 if (DefMI->getParent() == 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] >=
1262 TRI->getRegPressureSetLimit(MF: *MBB.getParent(), Idx: PS)) {
1263 return true;
1264 }
1265 }
1266
1267 return false;
1268}
1269
1270/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
1271bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
1272 MachineBasicBlock *MBB,
1273 MachineBasicBlock *SuccToSinkTo,
1274 AllSuccsCache &AllSuccessors) {
1275 assert(SuccToSinkTo && "Invalid SinkTo Candidate BB");
1276
1277 if (MBB == SuccToSinkTo)
1278 return false;
1279
1280 // It is profitable if SuccToSinkTo does not post dominate current block.
1281 if (!PDT->dominates(A: SuccToSinkTo, B: MBB))
1282 return true;
1283
1284 // It is profitable to sink an instruction from a deeper cycle to a shallower
1285 // cycle, even if the latter post-dominates the former (PR21115).
1286 if (CI->getCycleDepth(Block: MBB) > CI->getCycleDepth(Block: SuccToSinkTo))
1287 return true;
1288
1289 // Check if only use in post dominated block is PHI instruction.
1290 bool NonPHIUse = false;
1291 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
1292 MachineBasicBlock *UseBlock = UseInst.getParent();
1293 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
1294 NonPHIUse = true;
1295 }
1296 if (!NonPHIUse)
1297 return true;
1298
1299 // If SuccToSinkTo post dominates then also it may be profitable if MI
1300 // can further profitably sinked into another block in next round.
1301 bool BreakPHIEdge = false;
1302 // FIXME - If finding successor is compile time expensive then cache results.
1303 if (MachineBasicBlock *MBB2 =
1304 FindSuccToSinkTo(MI, MBB: SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1305 return isProfitableToSinkTo(Reg, MI, MBB: SuccToSinkTo, SuccToSinkTo: MBB2, AllSuccessors);
1306
1307 CycleRef MCycle = CI->getCycle(Block: MBB);
1308
1309 // If the instruction is not inside a cycle, it is not profitable to sink MI
1310 // to a post dominate block SuccToSinkTo.
1311 if (!MCycle)
1312 return false;
1313
1314 // If this instruction is inside a Cycle and sinking this instruction can make
1315 // more registers live range shorten, it is still prifitable.
1316 for (const MachineOperand &MO : MI.operands()) {
1317 // Ignore non-register operands.
1318 if (!MO.isReg())
1319 continue;
1320 Register Reg = MO.getReg();
1321 if (Reg == 0)
1322 continue;
1323
1324 if (Reg.isPhysical()) {
1325 // Don't handle non-constant and non-ignorable physical register uses.
1326 if (MO.isUse() && !MRI->isConstantPhysReg(PhysReg: Reg) &&
1327 !TII->isIgnorableUse(MO))
1328 return false;
1329 continue;
1330 }
1331
1332 // Users for the defs are all dominated by SuccToSinkTo.
1333 if (MO.isDef()) {
1334 // This def register's live range is shortened after sinking.
1335 bool LocalUse = false;
1336 if (!AllUsesDominatedByBlock(Reg, MBB: SuccToSinkTo, DefMBB: MBB, BreakPHIEdge,
1337 LocalUse))
1338 return false;
1339 } else {
1340 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1341 if (!DefMI)
1342 continue;
1343 CycleRef Cycle = CI->getCycle(Block: DefMI->getParent());
1344 // DefMI is defined outside of cycle. There should be no live range
1345 // impact for this operand. Defination outside of cycle means:
1346 // 1: defination is outside of cycle.
1347 // 2: defination is in this cycle, but it is a PHI in the cycle header.
1348 if (Cycle != MCycle ||
1349 (DefMI->isPHI() && Cycle && CI->isReducible(C: Cycle) &&
1350 CI->getHeader(C: Cycle) == DefMI->getParent()))
1351 continue;
1352 // The DefMI is defined inside the cycle.
1353 // If sinking this operand makes some register pressure set exceed limit,
1354 // it is not profitable.
1355 if (registerPressureSetExceedsLimit(NRegs: 1, RC: MRI->getRegClass(Reg),
1356 MBB: *SuccToSinkTo)) {
1357 LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
1358 return false;
1359 }
1360 }
1361 }
1362
1363 // If MI is in cycle and all its operands are alive across the whole cycle or
1364 // if no operand sinking make register pressure set exceed limit, it is
1365 // profitable to sink MI.
1366 return true;
1367}
1368
1369/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
1370/// computing it if it was not already cached.
1371SmallVector<MachineBasicBlock *, 4> &
1372MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
1373 AllSuccsCache &AllSuccessors) const {
1374 // Do we have the sorted successors in cache ?
1375 auto Succs = AllSuccessors.find(Val: MBB);
1376 if (Succs != AllSuccessors.end())
1377 return Succs->second;
1378
1379 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());
1380
1381 // Handle cases where sinking can happen but where the sink point isn't a
1382 // successor. For example:
1383 //
1384 // x = computation
1385 // if () {} else {}
1386 // use x
1387 //
1388 for (MachineDomTreeNode *DTChild : DT->getNode(BB: MBB)->children()) {
1389 // DomTree children of MBB that have MBB as immediate dominator are added.
1390 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
1391 // Skip MBBs already added to the AllSuccs vector above.
1392 !MBB->isSuccessor(MBB: DTChild->getBlock()))
1393 AllSuccs.push_back(Elt: DTChild->getBlock());
1394 }
1395
1396 // Sort Successors according to their cycle depth or block frequency info.
1397 llvm::stable_sort(
1398 Range&: AllSuccs, C: [&](const MachineBasicBlock *L, const MachineBasicBlock *R) {
1399 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(MBB: L).getFrequency() : 0;
1400 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(MBB: R).getFrequency() : 0;
1401 if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI) ||
1402 (!LHSFreq && !RHSFreq))
1403 return CI->getCycleDepth(Block: L) < CI->getCycleDepth(Block: R);
1404 return LHSFreq < RHSFreq;
1405 });
1406
1407 auto it = AllSuccessors.insert(KV: std::make_pair(x&: MBB, y&: AllSuccs));
1408
1409 return it.first->second;
1410}
1411
1412/// FindSuccToSinkTo - Find a successor to sink this instruction to.
1413MachineBasicBlock *
1414MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
1415 bool &BreakPHIEdge,
1416 AllSuccsCache &AllSuccessors) {
1417 assert(MBB && "Invalid MachineBasicBlock!");
1418
1419 // loop over all the operands of the specified instruction. If there is
1420 // anything we can't handle, bail out.
1421
1422 // SuccToSinkTo - This is the successor to sink this instruction to, once we
1423 // decide.
1424 MachineBasicBlock *SuccToSinkTo = nullptr;
1425 for (const MachineOperand &MO : MI.operands()) {
1426 if (!MO.isReg())
1427 continue; // Ignore non-register operands.
1428
1429 Register Reg = MO.getReg();
1430 if (Reg == 0)
1431 continue;
1432
1433 if (Reg.isPhysical()) {
1434 if (MO.isUse()) {
1435 // If the physreg has no defs anywhere, it's just an ambient register
1436 // and we can freely move its uses. Alternatively, if it's allocatable,
1437 // it could get allocated to something with a def during allocation.
1438 if (!MRI->isConstantPhysReg(PhysReg: Reg) && !TII->isIgnorableUse(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