1 //===- MachineSink.cpp - Sinking for machine instructions -----------------===//
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
7 //===----------------------------------------------------------------------===//
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.
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.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/SparseBitVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/CodeGen/MachineBasicBlock.h"
27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunction.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineInstr.h"
33 #include "llvm/CodeGen/MachineLoopInfo.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachinePostDominators.h"
36 #include "llvm/CodeGen/MachineRegisterInfo.h"
37 #include "llvm/CodeGen/TargetInstrInfo.h"
38 #include "llvm/CodeGen/TargetRegisterInfo.h"
39 #include "llvm/CodeGen/TargetSubtargetInfo.h"
40 #include "llvm/IR/BasicBlock.h"
41 #include "llvm/IR/DebugInfoMetadata.h"
42 #include "llvm/IR/LLVMContext.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/MC/MCRegisterInfo.h"
45 #include "llvm/Pass.h"
46 #include "llvm/Support/BranchProbability.h"
47 #include "llvm/Support/CommandLine.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/raw_ostream.h"
59 #define DEBUG_TYPE "machine-sink"
62 SplitEdges("machine-sink-split",
63 cl::desc("Split critical edges during machine sinking"),
64 cl::init(true), cl::Hidden);
67 UseBlockFreqInfo("machine-sink-bfi",
68 cl::desc("Use block frequency info to find successors to sink"),
69 cl::init(true), cl::Hidden);
71 static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
72 "machine-sink-split-probability-threshold",
74 "Percentage threshold for splitting single-instruction critical edge. "
75 "If the branch threshold is higher than this threshold, we allow "
76 "speculative execution of up to 1 instruction to avoid branching to "
77 "splitted critical edge"),
78 cl::init(40), cl::Hidden);
80 STATISTIC(NumSunk, "Number of machine instructions sunk");
81 STATISTIC(NumSplit, "Number of critical edges split");
82 STATISTIC(NumCoalesces, "Number of copies coalesced");
83 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
87 class MachineSinking : public MachineFunctionPass {
88 const TargetInstrInfo *TII;
89 const TargetRegisterInfo *TRI;
90 MachineRegisterInfo *MRI; // Machine register information
91 MachineDominatorTree *DT; // Machine dominator tree
92 MachinePostDominatorTree *PDT; // Machine post dominator tree
94 const MachineBlockFrequencyInfo *MBFI;
95 const MachineBranchProbabilityInfo *MBPI;
98 // Remember which edges have been considered for breaking.
99 SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
101 // Remember which edges we are about to split.
102 // This is different from CEBCandidates since those edges
104 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
106 SparseBitVector<> RegsToClearKillFlags;
108 using AllSuccsCache =
109 std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
111 /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
112 /// post-dominated by another DBG_VALUE of the same variable location.
113 /// This is necessary to detect sequences such as:
115 /// DBG_VALUE %0, !123, !DIExpression()
117 /// DBG_VALUE %1, !123, !DIExpression()
118 /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
119 /// would re-order assignments.
120 using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
122 /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
123 /// debug instructions to sink.
124 SmallDenseMap<unsigned, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
126 /// Record of debug variables that have had their locations set in the
128 DenseSet<DebugVariable> SeenDbgVars;
131 static char ID; // Pass identification
133 MachineSinking() : MachineFunctionPass(ID) {
134 initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
137 bool runOnMachineFunction(MachineFunction &MF) override;
139 void getAnalysisUsage(AnalysisUsage &AU) const override {
140 MachineFunctionPass::getAnalysisUsage(AU);
141 AU.addRequired<AAResultsWrapperPass>();
142 AU.addRequired<MachineDominatorTree>();
143 AU.addRequired<MachinePostDominatorTree>();
144 AU.addRequired<MachineLoopInfo>();
145 AU.addRequired<MachineBranchProbabilityInfo>();
146 AU.addPreserved<MachineLoopInfo>();
147 if (UseBlockFreqInfo)
148 AU.addRequired<MachineBlockFrequencyInfo>();
151 void releaseMemory() override {
152 CEBCandidates.clear();
156 bool ProcessBlock(MachineBasicBlock &MBB);
157 void ProcessDbgInst(MachineInstr &MI);
158 bool isWorthBreakingCriticalEdge(MachineInstr &MI,
159 MachineBasicBlock *From,
160 MachineBasicBlock *To);
162 /// Postpone the splitting of the given critical
163 /// edge (\p From, \p To).
165 /// We do not split the edges on the fly. Indeed, this invalidates
166 /// the dominance information and thus triggers a lot of updates
167 /// of that information underneath.
168 /// Instead, we postpone all the splits after each iteration of
169 /// the main loop. That way, the information is at least valid
170 /// for the lifetime of an iteration.
172 /// \return True if the edge is marked as toSplit, false otherwise.
173 /// False can be returned if, for instance, this is not profitable.
174 bool PostponeSplitCriticalEdge(MachineInstr &MI,
175 MachineBasicBlock *From,
176 MachineBasicBlock *To,
178 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
179 AllSuccsCache &AllSuccessors);
181 /// If we sink a COPY inst, some debug users of it's destination may no
182 /// longer be dominated by the COPY, and will eventually be dropped.
183 /// This is easily rectified by forwarding the non-dominated debug uses
184 /// to the copy source.
185 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
186 MachineBasicBlock *TargetBlock);
187 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
188 MachineBasicBlock *DefMBB,
189 bool &BreakPHIEdge, bool &LocalUse) const;
190 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
191 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
192 bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
193 MachineBasicBlock *MBB,
194 MachineBasicBlock *SuccToSinkTo,
195 AllSuccsCache &AllSuccessors);
197 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
198 MachineBasicBlock *MBB);
200 SmallVector<MachineBasicBlock *, 4> &
201 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
202 AllSuccsCache &AllSuccessors) const;
205 } // end anonymous namespace
207 char MachineSinking::ID = 0;
209 char &llvm::MachineSinkingID = MachineSinking::ID;
211 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
212 "Machine code sinking", false, false)
213 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
214 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
215 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
216 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
217 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
218 "Machine code sinking", false, false)
220 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
221 MachineBasicBlock *MBB) {
225 Register SrcReg = MI.getOperand(1).getReg();
226 Register DstReg = MI.getOperand(0).getReg();
227 if (!Register::isVirtualRegister(SrcReg) ||
228 !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg))
231 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
232 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
236 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
237 if (DefMI->isCopyLike())
239 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
240 LLVM_DEBUG(dbgs() << "*** to: " << MI);
241 MRI->replaceRegWith(DstReg, SrcReg);
242 MI.eraseFromParent();
244 // Conservatively, clear any kill flags, since it's possible that they are no
246 MRI->clearKillFlags(SrcReg);
252 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
253 /// occur in blocks dominated by the specified block. If any use is in the
254 /// definition block, then return false since it is never legal to move def
257 MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
258 MachineBasicBlock *MBB,
259 MachineBasicBlock *DefMBB,
261 bool &LocalUse) const {
262 assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs");
264 // Ignore debug uses because debug info doesn't affect the code.
265 if (MRI->use_nodbg_empty(Reg))
268 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
269 // into and they are all PHI nodes. In this case, machine-sink must break
270 // the critical edge first. e.g.
273 // Predecessors according to CFG: %bb.0
275 // %def = DEC64_32r %x, implicit-def dead %eflags
277 // JE_4 <%bb.37>, implicit %eflags
278 // Successors according to CFG: %bb.37 %bb.2
281 // %p = PHI %y, %bb.0, %def, %bb.1
282 if (llvm::all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) {
283 MachineInstr *UseInst = MO.getParent();
284 unsigned OpNo = UseInst->getOperandNo(&MO);
285 MachineBasicBlock *UseBlock = UseInst->getParent();
286 return UseBlock == MBB && UseInst->isPHI() &&
287 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
293 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
294 // Determine the block of the use.
295 MachineInstr *UseInst = MO.getParent();
296 unsigned OpNo = &MO - &UseInst->getOperand(0);
297 MachineBasicBlock *UseBlock = UseInst->getParent();
298 if (UseInst->isPHI()) {
299 // PHI nodes use the operand in the predecessor block, not the block with
301 UseBlock = UseInst->getOperand(OpNo+1).getMBB();
302 } else if (UseBlock == DefMBB) {
307 // Check that it dominates.
308 if (!DT->dominates(MBB, UseBlock))
315 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
316 if (skipFunction(MF.getFunction()))
319 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
321 TII = MF.getSubtarget().getInstrInfo();
322 TRI = MF.getSubtarget().getRegisterInfo();
323 MRI = &MF.getRegInfo();
324 DT = &getAnalysis<MachineDominatorTree>();
325 PDT = &getAnalysis<MachinePostDominatorTree>();
326 LI = &getAnalysis<MachineLoopInfo>();
327 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
328 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
329 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
331 bool EverMadeChange = false;
334 bool MadeChange = false;
336 // Process all basic blocks.
337 CEBCandidates.clear();
340 MadeChange |= ProcessBlock(MBB);
342 // If we have anything we marked as toSplit, split it now.
343 for (auto &Pair : ToSplit) {
344 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
345 if (NewSucc != nullptr) {
346 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
347 << printMBBReference(*Pair.first) << " -- "
348 << printMBBReference(*NewSucc) << " -- "
349 << printMBBReference(*Pair.second) << '\n');
353 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
355 // If this iteration over the code changed anything, keep iterating.
356 if (!MadeChange) break;
357 EverMadeChange = true;
360 // Now clear any kill flags for recorded registers.
361 for (auto I : RegsToClearKillFlags)
362 MRI->clearKillFlags(I);
363 RegsToClearKillFlags.clear();
365 return EverMadeChange;
368 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
369 // Can't sink anything out of a block that has less than two successors.
370 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
372 // Don't bother sinking code out of unreachable blocks. In addition to being
373 // unprofitable, it can also lead to infinite looping, because in an
374 // unreachable loop there may be nowhere to stop.
375 if (!DT->isReachableFromEntry(&MBB)) return false;
377 bool MadeChange = false;
379 // Cache all successors, sorted by frequency info and loop depth.
380 AllSuccsCache AllSuccessors;
382 // Walk the basic block bottom-up. Remember if we saw a store.
383 MachineBasicBlock::iterator I = MBB.end();
385 bool ProcessedBegin, SawStore = false;
387 MachineInstr &MI = *I; // The instruction to sink.
389 // Predecrement I (if it's not begin) so that it isn't invalidated by
391 ProcessedBegin = I == MBB.begin();
395 if (MI.isDebugInstr()) {
396 if (MI.isDebugValue())
401 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
407 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
412 // If we just processed the first instruction in the block, we're done.
413 } while (!ProcessedBegin);
415 SeenDbgUsers.clear();
421 void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
422 // When we see DBG_VALUEs for registers, record any vreg it reads, so that
423 // we know what to sink if the vreg def sinks.
424 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
426 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
427 MI.getDebugLoc()->getInlinedAt());
428 bool SeenBefore = SeenDbgVars.count(Var) != 0;
430 MachineOperand &MO = MI.getOperand(0);
431 if (MO.isReg() && MO.getReg().isVirtual())
432 SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
434 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
435 SeenDbgVars.insert(Var);
438 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
439 MachineBasicBlock *From,
440 MachineBasicBlock *To) {
441 // FIXME: Need much better heuristics.
443 // If the pass has already considered breaking this edge (during this pass
444 // through the function), then let's go ahead and break it. This means
445 // sinking multiple "cheap" instructions into the same block.
446 if (!CEBCandidates.insert(std::make_pair(From, To)).second)
449 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
452 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
453 BranchProbability(SplitEdgeProbabilityThreshold, 100))
456 // MI is cheap, we probably don't want to break the critical edge for it.
457 // However, if this would allow some definitions of its source operands
458 // to be sunk then it's probably worth it.
459 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
460 const MachineOperand &MO = MI.getOperand(i);
461 if (!MO.isReg() || !MO.isUse())
463 Register Reg = MO.getReg();
467 // We don't move live definitions of physical registers,
468 // so sinking their uses won't enable any opportunities.
469 if (Register::isPhysicalRegister(Reg))
472 // If this instruction is the only user of a virtual register,
473 // check if breaking the edge will enable sinking
474 // both this instruction and the defining instruction.
475 if (MRI->hasOneNonDBGUse(Reg)) {
476 // If the definition resides in same MBB,
477 // claim it's likely we can sink these together.
478 // If definition resides elsewhere, we aren't
479 // blocking it from being sunk so don't break the edge.
480 MachineInstr *DefMI = MRI->getVRegDef(Reg);
481 if (DefMI->getParent() == MI.getParent())
489 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
490 MachineBasicBlock *FromBB,
491 MachineBasicBlock *ToBB,
493 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
496 // Avoid breaking back edge. From == To means backedge for single BB loop.
497 if (!SplitEdges || FromBB == ToBB)
500 // Check for backedges of more "complex" loops.
501 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
502 LI->isLoopHeader(ToBB))
505 // It's not always legal to break critical edges and sink the computation
513 // ... no uses of v1024
519 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
528 // ... no uses of v1024
534 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
535 // flow. We need to ensure the new basic block where the computation is
536 // sunk to dominates all the uses.
537 // It's only legal to break critical edge and sink the computation to the
538 // new block if all the predecessors of "To", except for "From", are
539 // not dominated by "From". Given SSA property, this means these
540 // predecessors are dominated by "To".
542 // There is no need to do this check if all the uses are PHI nodes. PHI
543 // sources are only defined on the specific predecessor edges.
545 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
546 E = ToBB->pred_end(); PI != E; ++PI) {
549 if (!DT->dominates(ToBB, *PI))
554 ToSplit.insert(std::make_pair(FromBB, ToBB));
559 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
560 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
561 MachineBasicBlock *MBB,
562 MachineBasicBlock *SuccToSinkTo,
563 AllSuccsCache &AllSuccessors) {
564 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
566 if (MBB == SuccToSinkTo)
569 // It is profitable if SuccToSinkTo does not post dominate current block.
570 if (!PDT->dominates(SuccToSinkTo, MBB))
573 // It is profitable to sink an instruction from a deeper loop to a shallower
574 // loop, even if the latter post-dominates the former (PR21115).
575 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
578 // Check if only use in post dominated block is PHI instruction.
579 bool NonPHIUse = false;
580 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
581 MachineBasicBlock *UseBlock = UseInst.getParent();
582 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
588 // If SuccToSinkTo post dominates then also it may be profitable if MI
589 // can further profitably sinked into another block in next round.
590 bool BreakPHIEdge = false;
591 // FIXME - If finding successor is compile time expensive then cache results.
592 if (MachineBasicBlock *MBB2 =
593 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
594 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
596 // If SuccToSinkTo is final destination and it is a post dominator of current
597 // block then it is not profitable to sink MI into SuccToSinkTo block.
601 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
602 /// computing it if it was not already cached.
603 SmallVector<MachineBasicBlock *, 4> &
604 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
605 AllSuccsCache &AllSuccessors) const {
606 // Do we have the sorted successors in cache ?
607 auto Succs = AllSuccessors.find(MBB);
608 if (Succs != AllSuccessors.end())
609 return Succs->second;
611 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
614 // Handle cases where sinking can happen but where the sink point isn't a
615 // successor. For example:
621 const std::vector<MachineDomTreeNode *> &Children =
622 DT->getNode(MBB)->getChildren();
623 for (const auto &DTChild : Children)
624 // DomTree children of MBB that have MBB as immediate dominator are added.
625 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
626 // Skip MBBs already added to the AllSuccs vector above.
627 !MBB->isSuccessor(DTChild->getBlock()))
628 AllSuccs.push_back(DTChild->getBlock());
630 // Sort Successors according to their loop depth or block frequency info.
632 AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
633 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
634 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
635 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
636 return HasBlockFreq ? LHSFreq < RHSFreq
637 : LI->getLoopDepth(L) < LI->getLoopDepth(R);
640 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
642 return it.first->second;
645 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
647 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
649 AllSuccsCache &AllSuccessors) {
650 assert (MBB && "Invalid MachineBasicBlock!");
652 // Loop over all the operands of the specified instruction. If there is
653 // anything we can't handle, bail out.
655 // SuccToSinkTo - This is the successor to sink this instruction to, once we
657 MachineBasicBlock *SuccToSinkTo = nullptr;
658 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
659 const MachineOperand &MO = MI.getOperand(i);
660 if (!MO.isReg()) continue; // Ignore non-register operands.
662 Register Reg = MO.getReg();
663 if (Reg == 0) continue;
665 if (Register::isPhysicalRegister(Reg)) {
667 // If the physreg has no defs anywhere, it's just an ambient register
668 // and we can freely move its uses. Alternatively, if it's allocatable,
669 // it could get allocated to something with a def during allocation.
670 if (!MRI->isConstantPhysReg(Reg))
672 } else if (!MO.isDead()) {
673 // A def that isn't dead. We can't move it.
677 // Virtual register uses are always safe to sink.
678 if (MO.isUse()) continue;
680 // If it's not safe to move defs of the register class, then abort.
681 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
684 // Virtual register defs can only be sunk if all their uses are in blocks
685 // dominated by one of the successors.
687 // If a previous operand picked a block to sink to, then this operand
688 // must be sinkable to the same block.
689 bool LocalUse = false;
690 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
691 BreakPHIEdge, LocalUse))
697 // Otherwise, we should look at all the successors and decide which one
698 // we should sink to. If we have reliable block frequency information
699 // (frequency != 0) available, give successors with smaller frequencies
700 // higher priority, otherwise prioritize smaller loop depths.
701 for (MachineBasicBlock *SuccBlock :
702 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
703 bool LocalUse = false;
704 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
705 BreakPHIEdge, LocalUse)) {
706 SuccToSinkTo = SuccBlock;
710 // Def is used locally, it's never safe to move this def.
714 // If we couldn't find a block to sink to, ignore this instruction.
717 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
722 // It is not possible to sink an instruction into its own block. This can
723 // happen with loops.
724 if (MBB == SuccToSinkTo)
727 // It's not safe to sink instructions to EH landing pad. Control flow into
728 // landing pad is implicitly defined.
729 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
735 /// Return true if MI is likely to be usable as a memory operation by the
736 /// implicit null check optimization.
738 /// This is a "best effort" heuristic, and should not be relied upon for
739 /// correctness. This returning true does not guarantee that the implicit null
740 /// check optimization is legal over MI, and this returning false does not
741 /// guarantee MI cannot possibly be used to do a null check.
742 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
743 const TargetInstrInfo *TII,
744 const TargetRegisterInfo *TRI) {
745 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
747 auto *MBB = MI.getParent();
748 if (MBB->pred_size() != 1)
751 auto *PredMBB = *MBB->pred_begin();
752 auto *PredBB = PredMBB->getBasicBlock();
754 // Frontends that don't use implicit null checks have no reason to emit
755 // branches with make.implicit metadata, and this function should always
756 // return false for them.
758 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
761 const MachineOperand *BaseOp;
763 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI))
766 if (!BaseOp->isReg())
769 if (!(MI.mayLoad() && !MI.isPredicable()))
772 MachineBranchPredicate MBP;
773 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
776 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
777 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
778 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
779 MBP.LHS.getReg() == BaseOp->getReg();
782 /// If the sunk instruction is a copy, try to forward the copy instead of
783 /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
784 /// there's any subregister weirdness involved. Returns true if copy
785 /// propagation occurred.
786 static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI) {
787 const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
788 const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
790 // Copy DBG_VALUE operand and set the original to undef. We then check to
791 // see whether this is something that can be copy-forwarded. If it isn't,
792 // continue around the loop.
793 MachineOperand DbgMO = DbgMI.getOperand(0);
795 const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
796 auto CopyOperands = TII.isCopyInstr(SinkInst);
799 SrcMO = CopyOperands->Source;
800 DstMO = CopyOperands->Destination;
802 // Check validity of forwarding this copy.
803 bool PostRA = MRI.getNumVirtRegs() == 0;
805 // Trying to forward between physical and virtual registers is too hard.
806 if (DbgMO.getReg().isVirtual() != SrcMO->getReg().isVirtual())
809 // Only try virtual register copy-forwarding before regalloc, and physical
810 // register copy-forwarding after regalloc.
811 bool arePhysRegs = !DbgMO.getReg().isVirtual();
812 if (arePhysRegs != PostRA)
815 // Pre-regalloc, only forward if all subregisters agree (or there are no
816 // subregs at all). More analysis might recover some forwardable copies.
817 if (!PostRA && (DbgMO.getSubReg() != SrcMO->getSubReg() ||
818 DbgMO.getSubReg() != DstMO->getSubReg()))
821 // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
822 // of this copy. Only forward the copy if the DBG_VALUE operand exactly
823 // matches the copy destination.
824 if (PostRA && DbgMO.getReg() != DstMO->getReg())
827 DbgMI.getOperand(0).setReg(SrcMO->getReg());
828 DbgMI.getOperand(0).setSubReg(SrcMO->getSubReg());
832 /// Sink an instruction and its associated debug instructions.
833 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
834 MachineBasicBlock::iterator InsertPos,
835 SmallVectorImpl<MachineInstr *> &DbgValuesToSink) {
837 // If we cannot find a location to use (merge with), then we erase the debug
838 // location to prevent debug-info driven tools from potentially reporting
839 // wrong location information.
840 if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
841 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
842 InsertPos->getDebugLoc()));
844 MI.setDebugLoc(DebugLoc());
846 // Move the instruction.
847 MachineBasicBlock *ParentBlock = MI.getParent();
848 SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
849 ++MachineBasicBlock::iterator(MI));
851 // Sink a copy of debug users to the insert position. Mark the original
852 // DBG_VALUE location as 'undef', indicating that any earlier variable
853 // location should be terminated as we've optimised away the value at this
855 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
856 DBE = DbgValuesToSink.end();
858 MachineInstr *DbgMI = *DBI;
859 MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI);
860 SuccToSinkTo.insert(InsertPos, NewDbgMI);
862 if (!attemptDebugCopyProp(MI, *DbgMI))
863 DbgMI->getOperand(0).setReg(0);
867 /// SinkInstruction - Determine whether it is safe to sink the specified machine
868 /// instruction out of its current block into a successor.
869 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
870 AllSuccsCache &AllSuccessors) {
871 // Don't sink instructions that the target prefers not to sink.
872 if (!TII->shouldSink(MI))
875 // Check if it's safe to move the instruction.
876 if (!MI.isSafeToMove(AA, SawStore))
879 // Convergent operations may not be made control-dependent on additional
881 if (MI.isConvergent())
884 // Don't break implicit null checks. This is a performance heuristic, and not
885 // required for correctness.
886 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
889 // FIXME: This should include support for sinking instructions within the
890 // block they are currently in to shorten the live ranges. We often get
891 // instructions sunk into the top of a large block, but it would be better to
892 // also sink them down before their first use in the block. This xform has to
893 // be careful not to *increase* register pressure though, e.g. sinking
894 // "x = y + z" down if it kills y and z would increase the live ranges of y
895 // and z and only shrink the live range of x.
897 bool BreakPHIEdge = false;
898 MachineBasicBlock *ParentBlock = MI.getParent();
899 MachineBasicBlock *SuccToSinkTo =
900 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
902 // If there are no outputs, it must have side-effects.
906 // If the instruction to move defines a dead physical register which is live
907 // when leaving the basic block, don't move it because it could turn into a
908 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
909 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
910 const MachineOperand &MO = MI.getOperand(I);
911 if (!MO.isReg()) continue;
912 Register Reg = MO.getReg();
913 if (Reg == 0 || !Register::isPhysicalRegister(Reg))
915 if (SuccToSinkTo->isLiveIn(Reg))
919 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
921 // If the block has multiple predecessors, this is a critical edge.
922 // Decide if we can sink along it or need to break the edge.
923 if (SuccToSinkTo->pred_size() > 1) {
924 // We cannot sink a load across a critical edge - there may be stores in
926 bool TryBreak = false;
928 if (!MI.isSafeToMove(AA, store)) {
929 LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
933 // We don't want to sink across a critical edge if we don't dominate the
934 // successor. We could be introducing calculations to new code paths.
935 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
936 LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
940 // Don't sink instructions into a loop.
941 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
942 LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
946 // Otherwise we are OK with sinking along a critical edge.
948 LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
950 // Mark this edge as to be split.
951 // If the edge can actually be split, the next iteration of the main loop
952 // will sink MI in the newly created block.
954 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
956 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
957 "break critical edge\n");
958 // The instruction will not be sunk this time.
964 // BreakPHIEdge is true if all the uses are in the successor MBB being
965 // sunken into and they are all PHI nodes. In this case, machine-sink must
966 // break the critical edge first.
967 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
968 SuccToSinkTo, BreakPHIEdge);
970 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
971 "break critical edge\n");
972 // The instruction will not be sunk this time.
976 // Determine where to insert into. Skip phi nodes.
977 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
978 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
981 // Collect debug users of any vreg that this inst defines.
982 SmallVector<MachineInstr *, 4> DbgUsersToSink;
983 for (auto &MO : MI.operands()) {
984 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
986 if (!SeenDbgUsers.count(MO.getReg()))
989 // Sink any users that don't pass any other DBG_VALUEs for this variable.
990 auto &Users = SeenDbgUsers[MO.getReg()];
991 for (auto &User : Users) {
992 MachineInstr *DbgMI = User.getPointer();
994 // This DBG_VALUE would re-order assignments. If we can't copy-propagate
995 // it, it can't be recovered. Set it undef.
996 if (!attemptDebugCopyProp(MI, *DbgMI))
997 DbgMI->getOperand(0).setReg(0);
999 DbgUsersToSink.push_back(DbgMI);
1004 // After sinking, some debug users may not be dominated any more. If possible,
1005 // copy-propagate their operands. As it's expensive, don't do this if there's
1006 // no debuginfo in the program.
1007 if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1008 SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
1010 performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
1012 // Conservatively, clear any kill flags, since it's possible that they are no
1014 // Note that we have to clear the kill flags for any register this instruction
1015 // uses as we may sink over another instruction which currently kills the
1017 for (MachineOperand &MO : MI.operands()) {
1018 if (MO.isReg() && MO.isUse())
1019 RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
1025 void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1026 MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1027 assert(MI.isCopy());
1028 assert(MI.getOperand(1).isReg());
1030 // Enumerate all users of vreg operands that are def'd. Skip those that will
1031 // be sunk. For the rest, if they are not dominated by the block we will sink
1032 // MI into, propagate the copy source to them.
1033 SmallVector<MachineInstr *, 4> DbgDefUsers;
1034 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1035 for (auto &MO : MI.operands()) {
1036 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1038 for (auto &User : MRI.use_instructions(MO.getReg())) {
1039 if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
1042 // If is in same block, will either sink or be use-before-def.
1043 if (User.getParent() == MI.getParent())
1046 assert(User.getOperand(0).isReg() &&
1047 "DBG_VALUE user of vreg, but non reg operand?");
1048 DbgDefUsers.push_back(&User);
1052 // Point the users of this copy that are no longer dominated, at the source
1054 for (auto *User : DbgDefUsers) {
1055 User->getOperand(0).setReg(MI.getOperand(1).getReg());
1056 User->getOperand(0).setSubReg(MI.getOperand(1).getSubReg());
1060 //===----------------------------------------------------------------------===//
1061 // This pass is not intended to be a replacement or a complete alternative
1062 // for the pre-ra machine sink pass. It is only designed to sink COPY
1063 // instructions which should be handled after RA.
1065 // This pass sinks COPY instructions into a successor block, if the COPY is not
1066 // used in the current block and the COPY is live-in to a single successor
1067 // (i.e., doesn't require the COPY to be duplicated). This avoids executing the
1068 // copy on paths where their results aren't needed. This also exposes
1069 // additional opportunites for dead copy elimination and shrink wrapping.
1071 // These copies were either not handled by or are inserted after the MachineSink
1072 // pass. As an example of the former case, the MachineSink pass cannot sink
1073 // COPY instructions with allocatable source registers; for AArch64 these type
1074 // of copy instructions are frequently used to move function parameters (PhyReg)
1075 // into virtual registers in the entry block.
1077 // For the machine IR below, this pass will sink %w19 in the entry into its
1078 // successor (%bb.1) because %w19 is only live-in in %bb.1.
1080 // %wzr = SUBSWri %w1, 1
1086 // %w0 = ADDWrr %w0, %w19
1091 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
1092 // able to see %bb.0 as a candidate.
1093 //===----------------------------------------------------------------------===//
1096 class PostRAMachineSinking : public MachineFunctionPass {
1098 bool runOnMachineFunction(MachineFunction &MF) override;
1101 PostRAMachineSinking() : MachineFunctionPass(ID) {}
1102 StringRef getPassName() const override { return "PostRA Machine Sink"; }
1104 void getAnalysisUsage(AnalysisUsage &AU) const override {
1105 AU.setPreservesCFG();
1106 MachineFunctionPass::getAnalysisUsage(AU);
1109 MachineFunctionProperties getRequiredProperties() const override {
1110 return MachineFunctionProperties().set(
1111 MachineFunctionProperties::Property::NoVRegs);
1115 /// Track which register units have been modified and used.
1116 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
1118 /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
1119 /// entry in this map for each unit it touches.
1120 DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgInstrs;
1122 /// Sink Copy instructions unused in the same block close to their uses in
1124 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
1125 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
1129 char PostRAMachineSinking::ID = 0;
1130 char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
1132 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
1133 "PostRA Machine Sink", false, false)
1135 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
1136 const TargetRegisterInfo *TRI) {
1137 LiveRegUnits LiveInRegUnits(*TRI);
1138 LiveInRegUnits.addLiveIns(MBB);
1139 return !LiveInRegUnits.available(Reg);
1142 static MachineBasicBlock *
1143 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1144 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1145 unsigned Reg, const TargetRegisterInfo *TRI) {
1146 // Try to find a single sinkable successor in which Reg is live-in.
1147 MachineBasicBlock *BB = nullptr;
1148 for (auto *SI : SinkableBBs) {
1149 if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
1150 // If BB is set here, Reg is live-in to at least two sinkable successors,
1157 // Reg is not live-in to any sinkable successors.
1161 // Check if any register aliased with Reg is live-in in other successors.
1162 for (auto *SI : CurBB.successors()) {
1163 if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1169 static MachineBasicBlock *
1170 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1171 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1172 ArrayRef<unsigned> DefedRegsInCopy,
1173 const TargetRegisterInfo *TRI) {
1174 MachineBasicBlock *SingleBB = nullptr;
1175 for (auto DefReg : DefedRegsInCopy) {
1176 MachineBasicBlock *BB =
1177 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1178 if (!BB || (SingleBB && SingleBB != BB))
1185 static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
1186 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1187 LiveRegUnits &UsedRegUnits,
1188 const TargetRegisterInfo *TRI) {
1189 for (auto U : UsedOpsInCopy) {
1190 MachineOperand &MO = MI->getOperand(U);
1191 Register SrcReg = MO.getReg();
1192 if (!UsedRegUnits.available(SrcReg)) {
1193 MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1194 for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1195 if (UI.killsRegister(SrcReg, TRI)) {
1196 UI.clearRegisterKills(SrcReg, TRI);
1205 static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
1206 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1207 SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1208 MachineFunction &MF = *SuccBB->getParent();
1209 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1210 for (unsigned DefReg : DefedRegsInCopy)
1211 for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1212 SuccBB->removeLiveIn(*S);
1213 for (auto U : UsedOpsInCopy) {
1214 Register SrcReg = MI->getOperand(U).getReg();
1216 for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S) {
1217 Mask |= (*S).second;
1219 SuccBB->addLiveIn(SrcReg, Mask.any() ? Mask : LaneBitmask::getAll());
1221 SuccBB->sortUniqueLiveIns();
1224 static bool hasRegisterDependency(MachineInstr *MI,
1225 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1226 SmallVectorImpl<unsigned> &DefedRegsInCopy,
1227 LiveRegUnits &ModifiedRegUnits,
1228 LiveRegUnits &UsedRegUnits) {
1229 bool HasRegDependency = false;
1230 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1231 MachineOperand &MO = MI->getOperand(i);
1234 Register Reg = MO.getReg();
1238 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1239 HasRegDependency = true;
1242 DefedRegsInCopy.push_back(Reg);
1244 // FIXME: instead of isUse(), readsReg() would be a better fix here,
1245 // For example, we can ignore modifications in reg with undef. However,
1246 // it's not perfectly clear if skipping the internal read is safe in all
1248 } else if (MO.isUse()) {
1249 if (!ModifiedRegUnits.available(Reg)) {
1250 HasRegDependency = true;
1253 UsedOpsInCopy.push_back(i);
1256 return HasRegDependency;
1259 static SmallSet<unsigned, 4> getRegUnits(unsigned Reg,
1260 const TargetRegisterInfo *TRI) {
1261 SmallSet<unsigned, 4> RegUnits;
1262 for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
1263 RegUnits.insert(*RI);
1267 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1268 MachineFunction &MF,
1269 const TargetRegisterInfo *TRI,
1270 const TargetInstrInfo *TII) {
1271 SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
1272 // FIXME: For now, we sink only to a successor which has a single predecessor
1273 // so that we can directly sink COPY instructions to the successor without
1274 // adding any new block or branch instruction.
1275 for (MachineBasicBlock *SI : CurBB.successors())
1276 if (!SI->livein_empty() && SI->pred_size() == 1)
1277 SinkableBBs.insert(SI);
1279 if (SinkableBBs.empty())
1282 bool Changed = false;
1284 // Track which registers have been modified and used between the end of the
1285 // block and the current instruction.
1286 ModifiedRegUnits.clear();
1287 UsedRegUnits.clear();
1288 SeenDbgInstrs.clear();
1290 for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
1291 MachineInstr *MI = &*I;
1294 // Track the operand index for use in Copy.
1295 SmallVector<unsigned, 2> UsedOpsInCopy;
1296 // Track the register number defed in Copy.
1297 SmallVector<unsigned, 2> DefedRegsInCopy;
1299 // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1300 // for DBG_VALUEs later, record them when they're encountered.
1301 if (MI->isDebugValue()) {
1302 auto &MO = MI->getOperand(0);
1303 if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
1304 // Bail if we can already tell the sink would be rejected, rather
1305 // than needlessly accumulating lots of DBG_VALUEs.
1306 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1307 ModifiedRegUnits, UsedRegUnits))
1310 // Record debug use of each reg unit.
1311 SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
1312 for (unsigned Reg : Units)
1313 SeenDbgInstrs[Reg].push_back(MI);
1318 if (MI->isDebugInstr())
1321 // Do not move any instruction across function call.
1325 if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
1326 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1331 // Don't sink the COPY if it would violate a register dependency.
1332 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1333 ModifiedRegUnits, UsedRegUnits)) {
1334 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1338 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1339 "Unexpect SrcReg or DefReg");
1340 MachineBasicBlock *SuccBB =
1341 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1342 // Don't sink if we cannot find a single sinkable successor in which Reg
1345 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1349 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1350 "Unexpected predecessor");
1352 // Collect DBG_VALUEs that must sink with this copy. We've previously
1353 // recorded which reg units that DBG_VALUEs read, if this instruction
1354 // writes any of those units then the corresponding DBG_VALUEs must sink.
1355 SetVector<MachineInstr *> DbgValsToSinkSet;
1356 SmallVector<MachineInstr *, 4> DbgValsToSink;
1357 for (auto &MO : MI->operands()) {
1358 if (!MO.isReg() || !MO.isDef())
1361 SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
1362 for (unsigned Reg : Units)
1363 for (auto *MI : SeenDbgInstrs.lookup(Reg))
1364 DbgValsToSinkSet.insert(MI);
1366 DbgValsToSink.insert(DbgValsToSink.begin(), DbgValsToSinkSet.begin(),
1367 DbgValsToSinkSet.end());
1369 // Clear the kill flag if SrcReg is killed between MI and the end of the
1371 clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1372 MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1373 performSink(*MI, *SuccBB, InsertPos, DbgValsToSink);
1374 updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1377 ++NumPostRACopySink;
1382 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1383 if (skipFunction(MF.getFunction()))
1386 bool Changed = false;
1387 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1388 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1390 ModifiedRegUnits.init(*TRI);
1391 UsedRegUnits.init(*TRI);
1393 Changed |= tryToSinkCopy(BB, MF, TRI, TII);