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