1 //===- MachineSink.cpp - Sinking for machine instructions -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass moves instructions into successor blocks when possible, so that
11 // they aren't executed on paths where their results aren't needed.
13 // This pass is not intended to be a replacement or a complete alternative
14 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
15 // constructs that are not exposed before lowering and instruction selection.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/SparseBitVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
28 #include "llvm/CodeGen/MachineDominators.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineOperand.h"
34 #include "llvm/CodeGen/MachinePostDominators.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/TargetInstrInfo.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/IR/BasicBlock.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/IR/DebugInfoMetadata.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/BranchProbability.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/raw_ostream.h"
56 #define DEBUG_TYPE "machine-sink"
59 SplitEdges("machine-sink-split",
60 cl::desc("Split critical edges during machine sinking"),
61 cl::init(true), cl::Hidden);
64 UseBlockFreqInfo("machine-sink-bfi",
65 cl::desc("Use block frequency info to find successors to sink"),
66 cl::init(true), cl::Hidden);
68 static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
69 "machine-sink-split-probability-threshold",
71 "Percentage threshold for splitting single-instruction critical edge. "
72 "If the branch threshold is higher than this threshold, we allow "
73 "speculative execution of up to 1 instruction to avoid branching to "
74 "splitted critical edge"),
75 cl::init(40), cl::Hidden);
77 STATISTIC(NumSunk, "Number of machine instructions sunk");
78 STATISTIC(NumSplit, "Number of critical edges split");
79 STATISTIC(NumCoalesces, "Number of copies coalesced");
83 class MachineSinking : public MachineFunctionPass {
84 const TargetInstrInfo *TII;
85 const TargetRegisterInfo *TRI;
86 MachineRegisterInfo *MRI; // Machine register information
87 MachineDominatorTree *DT; // Machine dominator tree
88 MachinePostDominatorTree *PDT; // Machine post dominator tree
90 const MachineBlockFrequencyInfo *MBFI;
91 const MachineBranchProbabilityInfo *MBPI;
94 // Remember which edges have been considered for breaking.
95 SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
97 // Remember which edges we are about to split.
98 // This is different from CEBCandidates since those edges
100 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
102 SparseBitVector<> RegsToClearKillFlags;
104 using AllSuccsCache =
105 std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
108 static char ID; // Pass identification
110 MachineSinking() : MachineFunctionPass(ID) {
111 initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
114 bool runOnMachineFunction(MachineFunction &MF) override;
116 void getAnalysisUsage(AnalysisUsage &AU) const override {
117 AU.setPreservesCFG();
118 MachineFunctionPass::getAnalysisUsage(AU);
119 AU.addRequired<AAResultsWrapperPass>();
120 AU.addRequired<MachineDominatorTree>();
121 AU.addRequired<MachinePostDominatorTree>();
122 AU.addRequired<MachineLoopInfo>();
123 AU.addRequired<MachineBranchProbabilityInfo>();
124 AU.addPreserved<MachineDominatorTree>();
125 AU.addPreserved<MachinePostDominatorTree>();
126 AU.addPreserved<MachineLoopInfo>();
127 if (UseBlockFreqInfo)
128 AU.addRequired<MachineBlockFrequencyInfo>();
131 void releaseMemory() override {
132 CEBCandidates.clear();
136 bool ProcessBlock(MachineBasicBlock &MBB);
137 bool isWorthBreakingCriticalEdge(MachineInstr &MI,
138 MachineBasicBlock *From,
139 MachineBasicBlock *To);
141 /// \brief Postpone the splitting of the given critical
142 /// edge (\p From, \p To).
144 /// We do not split the edges on the fly. Indeed, this invalidates
145 /// the dominance information and thus triggers a lot of updates
146 /// of that information underneath.
147 /// Instead, we postpone all the splits after each iteration of
148 /// the main loop. That way, the information is at least valid
149 /// for the lifetime of an iteration.
151 /// \return True if the edge is marked as toSplit, false otherwise.
152 /// False can be returned if, for instance, this is not profitable.
153 bool PostponeSplitCriticalEdge(MachineInstr &MI,
154 MachineBasicBlock *From,
155 MachineBasicBlock *To,
157 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
159 AllSuccsCache &AllSuccessors);
160 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
161 MachineBasicBlock *DefMBB,
162 bool &BreakPHIEdge, bool &LocalUse) const;
163 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
164 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
165 bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
166 MachineBasicBlock *MBB,
167 MachineBasicBlock *SuccToSinkTo,
168 AllSuccsCache &AllSuccessors);
170 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
171 MachineBasicBlock *MBB);
173 SmallVector<MachineBasicBlock *, 4> &
174 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
175 AllSuccsCache &AllSuccessors) const;
178 } // end anonymous namespace
180 char MachineSinking::ID = 0;
182 char &llvm::MachineSinkingID = MachineSinking::ID;
184 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
185 "Machine code sinking", false, false)
186 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
187 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
188 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
189 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
190 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
191 "Machine code sinking", false, false)
193 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
194 MachineBasicBlock *MBB) {
198 unsigned SrcReg = MI.getOperand(1).getReg();
199 unsigned DstReg = MI.getOperand(0).getReg();
200 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
201 !TargetRegisterInfo::isVirtualRegister(DstReg) ||
202 !MRI->hasOneNonDBGUse(SrcReg))
205 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
206 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
210 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
211 if (DefMI->isCopyLike())
213 DEBUG(dbgs() << "Coalescing: " << *DefMI);
214 DEBUG(dbgs() << "*** to: " << MI);
215 MRI->replaceRegWith(DstReg, SrcReg);
216 MI.eraseFromParent();
218 // Conservatively, clear any kill flags, since it's possible that they are no
220 MRI->clearKillFlags(SrcReg);
226 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
227 /// occur in blocks dominated by the specified block. If any use is in the
228 /// definition block, then return false since it is never legal to move def
231 MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
232 MachineBasicBlock *MBB,
233 MachineBasicBlock *DefMBB,
235 bool &LocalUse) const {
236 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
237 "Only makes sense for vregs");
239 // Ignore debug uses because debug info doesn't affect the code.
240 if (MRI->use_nodbg_empty(Reg))
243 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
244 // into and they are all PHI nodes. In this case, machine-sink must break
245 // the critical edge first. e.g.
247 // %bb.1: derived from LLVM BB %bb4.preheader
248 // Predecessors according to CFG: %bb.0
250 // %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
252 // JE_4 <%bb.37>, implicit %eflags
253 // Successors according to CFG: %bb.37 %bb.2
255 // %bb.2: derived from LLVM BB %bb.nph
256 // Predecessors according to CFG: %bb.0 %bb.1
257 // %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
259 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
260 MachineInstr *UseInst = MO.getParent();
261 unsigned OpNo = &MO - &UseInst->getOperand(0);
262 MachineBasicBlock *UseBlock = UseInst->getParent();
263 if (!(UseBlock == MBB && UseInst->isPHI() &&
264 UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
265 BreakPHIEdge = false;
272 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
273 // Determine the block of the use.
274 MachineInstr *UseInst = MO.getParent();
275 unsigned OpNo = &MO - &UseInst->getOperand(0);
276 MachineBasicBlock *UseBlock = UseInst->getParent();
277 if (UseInst->isPHI()) {
278 // PHI nodes use the operand in the predecessor block, not the block with
280 UseBlock = UseInst->getOperand(OpNo+1).getMBB();
281 } else if (UseBlock == DefMBB) {
286 // Check that it dominates.
287 if (!DT->dominates(MBB, UseBlock))
294 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
295 if (skipFunction(MF.getFunction()))
298 DEBUG(dbgs() << "******** Machine Sinking ********\n");
300 TII = MF.getSubtarget().getInstrInfo();
301 TRI = MF.getSubtarget().getRegisterInfo();
302 MRI = &MF.getRegInfo();
303 DT = &getAnalysis<MachineDominatorTree>();
304 PDT = &getAnalysis<MachinePostDominatorTree>();
305 LI = &getAnalysis<MachineLoopInfo>();
306 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
307 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
308 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
310 bool EverMadeChange = false;
313 bool MadeChange = false;
315 // Process all basic blocks.
316 CEBCandidates.clear();
319 MadeChange |= ProcessBlock(MBB);
321 // If we have anything we marked as toSplit, split it now.
322 for (auto &Pair : ToSplit) {
323 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
324 if (NewSucc != nullptr) {
325 DEBUG(dbgs() << " *** Splitting critical edge: "
326 << printMBBReference(*Pair.first) << " -- "
327 << printMBBReference(*NewSucc) << " -- "
328 << printMBBReference(*Pair.second) << '\n');
332 DEBUG(dbgs() << " *** Not legal to break critical edge\n");
334 // If this iteration over the code changed anything, keep iterating.
335 if (!MadeChange) break;
336 EverMadeChange = true;
339 // Now clear any kill flags for recorded registers.
340 for (auto I : RegsToClearKillFlags)
341 MRI->clearKillFlags(I);
342 RegsToClearKillFlags.clear();
344 return EverMadeChange;
347 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
348 // Can't sink anything out of a block that has less than two successors.
349 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
351 // Don't bother sinking code out of unreachable blocks. In addition to being
352 // unprofitable, it can also lead to infinite looping, because in an
353 // unreachable loop there may be nowhere to stop.
354 if (!DT->isReachableFromEntry(&MBB)) return false;
356 bool MadeChange = false;
358 // Cache all successors, sorted by frequency info and loop depth.
359 AllSuccsCache AllSuccessors;
361 // Walk the basic block bottom-up. Remember if we saw a store.
362 MachineBasicBlock::iterator I = MBB.end();
364 bool ProcessedBegin, SawStore = false;
366 MachineInstr &MI = *I; // The instruction to sink.
368 // Predecrement I (if it's not begin) so that it isn't invalidated by
370 ProcessedBegin = I == MBB.begin();
374 if (MI.isDebugValue())
377 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
383 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
388 // If we just processed the first instruction in the block, we're done.
389 } while (!ProcessedBegin);
394 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
395 MachineBasicBlock *From,
396 MachineBasicBlock *To) {
397 // FIXME: Need much better heuristics.
399 // If the pass has already considered breaking this edge (during this pass
400 // through the function), then let's go ahead and break it. This means
401 // sinking multiple "cheap" instructions into the same block.
402 if (!CEBCandidates.insert(std::make_pair(From, To)).second)
405 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
408 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
409 BranchProbability(SplitEdgeProbabilityThreshold, 100))
412 // MI is cheap, we probably don't want to break the critical edge for it.
413 // However, if this would allow some definitions of its source operands
414 // to be sunk then it's probably worth it.
415 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
416 const MachineOperand &MO = MI.getOperand(i);
417 if (!MO.isReg() || !MO.isUse())
419 unsigned Reg = MO.getReg();
423 // We don't move live definitions of physical registers,
424 // so sinking their uses won't enable any opportunities.
425 if (TargetRegisterInfo::isPhysicalRegister(Reg))
428 // If this instruction is the only user of a virtual register,
429 // check if breaking the edge will enable sinking
430 // both this instruction and the defining instruction.
431 if (MRI->hasOneNonDBGUse(Reg)) {
432 // If the definition resides in same MBB,
433 // claim it's likely we can sink these together.
434 // If definition resides elsewhere, we aren't
435 // blocking it from being sunk so don't break the edge.
436 MachineInstr *DefMI = MRI->getVRegDef(Reg);
437 if (DefMI->getParent() == MI.getParent())
445 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
446 MachineBasicBlock *FromBB,
447 MachineBasicBlock *ToBB,
449 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
452 // Avoid breaking back edge. From == To means backedge for single BB loop.
453 if (!SplitEdges || FromBB == ToBB)
456 // Check for backedges of more "complex" loops.
457 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
458 LI->isLoopHeader(ToBB))
461 // It's not always legal to break critical edges and sink the computation
469 // ... no uses of v1024
475 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
484 // ... no uses of v1024
490 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
491 // flow. We need to ensure the new basic block where the computation is
492 // sunk to dominates all the uses.
493 // It's only legal to break critical edge and sink the computation to the
494 // new block if all the predecessors of "To", except for "From", are
495 // not dominated by "From". Given SSA property, this means these
496 // predecessors are dominated by "To".
498 // There is no need to do this check if all the uses are PHI nodes. PHI
499 // sources are only defined on the specific predecessor edges.
501 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
502 E = ToBB->pred_end(); PI != E; ++PI) {
505 if (!DT->dominates(ToBB, *PI))
510 ToSplit.insert(std::make_pair(FromBB, ToBB));
515 /// collectDebgValues - Scan instructions following MI and collect any
516 /// matching DBG_VALUEs.
517 static void collectDebugValues(MachineInstr &MI,
518 SmallVectorImpl<MachineInstr *> &DbgValues) {
520 if (!MI.getOperand(0).isReg())
523 MachineBasicBlock::iterator DI = MI; ++DI;
524 for (MachineBasicBlock::iterator DE = MI.getParent()->end();
526 if (!DI->isDebugValue())
528 if (DI->getOperand(0).isReg() &&
529 DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
530 DbgValues.push_back(&*DI);
534 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
535 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
536 MachineBasicBlock *MBB,
537 MachineBasicBlock *SuccToSinkTo,
538 AllSuccsCache &AllSuccessors) {
539 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
541 if (MBB == SuccToSinkTo)
544 // It is profitable if SuccToSinkTo does not post dominate current block.
545 if (!PDT->dominates(SuccToSinkTo, MBB))
548 // It is profitable to sink an instruction from a deeper loop to a shallower
549 // loop, even if the latter post-dominates the former (PR21115).
550 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
553 // Check if only use in post dominated block is PHI instruction.
554 bool NonPHIUse = false;
555 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
556 MachineBasicBlock *UseBlock = UseInst.getParent();
557 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
563 // If SuccToSinkTo post dominates then also it may be profitable if MI
564 // can further profitably sinked into another block in next round.
565 bool BreakPHIEdge = false;
566 // FIXME - If finding successor is compile time expensive then cache results.
567 if (MachineBasicBlock *MBB2 =
568 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
569 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
571 // If SuccToSinkTo is final destination and it is a post dominator of current
572 // block then it is not profitable to sink MI into SuccToSinkTo block.
576 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
577 /// computing it if it was not already cached.
578 SmallVector<MachineBasicBlock *, 4> &
579 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
580 AllSuccsCache &AllSuccessors) const {
581 // Do we have the sorted successors in cache ?
582 auto Succs = AllSuccessors.find(MBB);
583 if (Succs != AllSuccessors.end())
584 return Succs->second;
586 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
589 // Handle cases where sinking can happen but where the sink point isn't a
590 // successor. For example:
596 const std::vector<MachineDomTreeNode *> &Children =
597 DT->getNode(MBB)->getChildren();
598 for (const auto &DTChild : Children)
599 // DomTree children of MBB that have MBB as immediate dominator are added.
600 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
601 // Skip MBBs already added to the AllSuccs vector above.
602 !MBB->isSuccessor(DTChild->getBlock()))
603 AllSuccs.push_back(DTChild->getBlock());
605 // Sort Successors according to their loop depth or block frequency info.
607 AllSuccs.begin(), AllSuccs.end(),
608 [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
609 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
610 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
611 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
612 return HasBlockFreq ? LHSFreq < RHSFreq
613 : LI->getLoopDepth(L) < LI->getLoopDepth(R);
616 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
618 return it.first->second;
621 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
623 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
625 AllSuccsCache &AllSuccessors) {
626 assert (MBB && "Invalid MachineBasicBlock!");
628 // Loop over all the operands of the specified instruction. If there is
629 // anything we can't handle, bail out.
631 // SuccToSinkTo - This is the successor to sink this instruction to, once we
633 MachineBasicBlock *SuccToSinkTo = nullptr;
634 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
635 const MachineOperand &MO = MI.getOperand(i);
636 if (!MO.isReg()) continue; // Ignore non-register operands.
638 unsigned Reg = MO.getReg();
639 if (Reg == 0) continue;
641 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
643 // If the physreg has no defs anywhere, it's just an ambient register
644 // and we can freely move its uses. Alternatively, if it's allocatable,
645 // it could get allocated to something with a def during allocation.
646 if (!MRI->isConstantPhysReg(Reg))
648 } else if (!MO.isDead()) {
649 // A def that isn't dead. We can't move it.
653 // Virtual register uses are always safe to sink.
654 if (MO.isUse()) continue;
656 // If it's not safe to move defs of the register class, then abort.
657 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
660 // Virtual register defs can only be sunk if all their uses are in blocks
661 // dominated by one of the successors.
663 // If a previous operand picked a block to sink to, then this operand
664 // must be sinkable to the same block.
665 bool LocalUse = false;
666 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
667 BreakPHIEdge, LocalUse))
673 // Otherwise, we should look at all the successors and decide which one
674 // we should sink to. If we have reliable block frequency information
675 // (frequency != 0) available, give successors with smaller frequencies
676 // higher priority, otherwise prioritize smaller loop depths.
677 for (MachineBasicBlock *SuccBlock :
678 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
679 bool LocalUse = false;
680 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
681 BreakPHIEdge, LocalUse)) {
682 SuccToSinkTo = SuccBlock;
686 // Def is used locally, it's never safe to move this def.
690 // If we couldn't find a block to sink to, ignore this instruction.
693 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
698 // It is not possible to sink an instruction into its own block. This can
699 // happen with loops.
700 if (MBB == SuccToSinkTo)
703 // It's not safe to sink instructions to EH landing pad. Control flow into
704 // landing pad is implicitly defined.
705 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
711 /// \brief Return true if MI is likely to be usable as a memory operation by the
712 /// implicit null check optimization.
714 /// This is a "best effort" heuristic, and should not be relied upon for
715 /// correctness. This returning true does not guarantee that the implicit null
716 /// check optimization is legal over MI, and this returning false does not
717 /// guarantee MI cannot possibly be used to do a null check.
718 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
719 const TargetInstrInfo *TII,
720 const TargetRegisterInfo *TRI) {
721 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
723 auto *MBB = MI.getParent();
724 if (MBB->pred_size() != 1)
727 auto *PredMBB = *MBB->pred_begin();
728 auto *PredBB = PredMBB->getBasicBlock();
730 // Frontends that don't use implicit null checks have no reason to emit
731 // branches with make.implicit metadata, and this function should always
732 // return false for them.
734 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
739 if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
742 if (!(MI.mayLoad() && !MI.isPredicable()))
745 MachineBranchPredicate MBP;
746 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
749 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
750 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
751 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
752 MBP.LHS.getReg() == BaseReg;
755 /// SinkInstruction - Determine whether it is safe to sink the specified machine
756 /// instruction out of its current block into a successor.
757 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
758 AllSuccsCache &AllSuccessors) {
759 // Don't sink instructions that the target prefers not to sink.
760 if (!TII->shouldSink(MI))
763 // Check if it's safe to move the instruction.
764 if (!MI.isSafeToMove(AA, SawStore))
767 // Convergent operations may not be made control-dependent on additional
769 if (MI.isConvergent())
772 // Don't break implicit null checks. This is a performance heuristic, and not
773 // required for correctness.
774 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
777 // FIXME: This should include support for sinking instructions within the
778 // block they are currently in to shorten the live ranges. We often get
779 // instructions sunk into the top of a large block, but it would be better to
780 // also sink them down before their first use in the block. This xform has to
781 // be careful not to *increase* register pressure though, e.g. sinking
782 // "x = y + z" down if it kills y and z would increase the live ranges of y
783 // and z and only shrink the live range of x.
785 bool BreakPHIEdge = false;
786 MachineBasicBlock *ParentBlock = MI.getParent();
787 MachineBasicBlock *SuccToSinkTo =
788 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
790 // If there are no outputs, it must have side-effects.
794 // If the instruction to move defines a dead physical register which is live
795 // when leaving the basic block, don't move it because it could turn into a
796 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
797 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
798 const MachineOperand &MO = MI.getOperand(I);
799 if (!MO.isReg()) continue;
800 unsigned Reg = MO.getReg();
801 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
802 if (SuccToSinkTo->isLiveIn(Reg))
806 DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
808 // If the block has multiple predecessors, this is a critical edge.
809 // Decide if we can sink along it or need to break the edge.
810 if (SuccToSinkTo->pred_size() > 1) {
811 // We cannot sink a load across a critical edge - there may be stores in
813 bool TryBreak = false;
815 if (!MI.isSafeToMove(AA, store)) {
816 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
820 // We don't want to sink across a critical edge if we don't dominate the
821 // successor. We could be introducing calculations to new code paths.
822 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
823 DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
827 // Don't sink instructions into a loop.
828 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
829 DEBUG(dbgs() << " *** NOTE: Loop header found\n");
833 // Otherwise we are OK with sinking along a critical edge.
835 DEBUG(dbgs() << "Sinking along critical edge.\n");
837 // Mark this edge as to be split.
838 // If the edge can actually be split, the next iteration of the main loop
839 // will sink MI in the newly created block.
841 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
843 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
844 "break critical edge\n");
845 // The instruction will not be sunk this time.
851 // BreakPHIEdge is true if all the uses are in the successor MBB being
852 // sunken into and they are all PHI nodes. In this case, machine-sink must
853 // break the critical edge first.
854 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
855 SuccToSinkTo, BreakPHIEdge);
857 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
858 "break critical edge\n");
859 // The instruction will not be sunk this time.
863 // Determine where to insert into. Skip phi nodes.
864 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
865 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
868 // collect matching debug values.
869 SmallVector<MachineInstr *, 2> DbgValuesToSink;
870 collectDebugValues(MI, DbgValuesToSink);
872 // Merge or erase debug location to ensure consistent stepping in profilers
874 if (!SuccToSinkTo->empty() && InsertPos != SuccToSinkTo->end())
875 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
876 InsertPos->getDebugLoc()));
878 MI.setDebugLoc(DebugLoc());
881 // Move the instruction.
882 SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
883 ++MachineBasicBlock::iterator(MI));
885 // Move previously adjacent debug value instructions to the insert position.
886 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
887 DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
888 MachineInstr *DbgMI = *DBI;
889 SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI,
890 ++MachineBasicBlock::iterator(DbgMI));
893 // Conservatively, clear any kill flags, since it's possible that they are no
895 // Note that we have to clear the kill flags for any register this instruction
896 // uses as we may sink over another instruction which currently kills the
898 for (MachineOperand &MO : MI.operands()) {
899 if (MO.isReg() && MO.isUse())
900 RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.