xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp (revision 38a52bd3b5cac3da6f7f6eef3dd050e6aa08ebb3)
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/ADT/DenseSet.h"
19 #include "llvm/ADT/MapVector.h"
20 #include "llvm/ADT/PointerIntPair.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/SparseBitVector.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/CFG.h"
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
31 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
32 #include "llvm/CodeGen/MachineDominators.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineInstr.h"
36 #include "llvm/CodeGen/MachineLoopInfo.h"
37 #include "llvm/CodeGen/MachineOperand.h"
38 #include "llvm/CodeGen/MachinePostDominators.h"
39 #include "llvm/CodeGen/MachineRegisterInfo.h"
40 #include "llvm/CodeGen/RegisterClassInfo.h"
41 #include "llvm/CodeGen/RegisterPressure.h"
42 #include "llvm/CodeGen/TargetInstrInfo.h"
43 #include "llvm/CodeGen/TargetRegisterInfo.h"
44 #include "llvm/CodeGen/TargetSubtargetInfo.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/DebugInfoMetadata.h"
47 #include "llvm/IR/LLVMContext.h"
48 #include "llvm/InitializePasses.h"
49 #include "llvm/MC/MCRegisterInfo.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/BranchProbability.h"
52 #include "llvm/Support/CommandLine.h"
53 #include "llvm/Support/Debug.h"
54 #include "llvm/Support/raw_ostream.h"
55 #include <algorithm>
56 #include <cassert>
57 #include <cstdint>
58 #include <map>
59 #include <utility>
60 #include <vector>
61 
62 using namespace llvm;
63 
64 #define DEBUG_TYPE "machine-sink"
65 
66 static cl::opt<bool>
67 SplitEdges("machine-sink-split",
68            cl::desc("Split critical edges during machine sinking"),
69            cl::init(true), cl::Hidden);
70 
71 static cl::opt<bool>
72 UseBlockFreqInfo("machine-sink-bfi",
73            cl::desc("Use block frequency info to find successors to sink"),
74            cl::init(true), cl::Hidden);
75 
76 static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
77     "machine-sink-split-probability-threshold",
78     cl::desc(
79         "Percentage threshold for splitting single-instruction critical edge. "
80         "If the branch threshold is higher than this threshold, we allow "
81         "speculative execution of up to 1 instruction to avoid branching to "
82         "splitted critical edge"),
83     cl::init(40), cl::Hidden);
84 
85 static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold(
86     "machine-sink-load-instrs-threshold",
87     cl::desc("Do not try to find alias store for a load if there is a in-path "
88              "block whose instruction number is higher than this threshold."),
89     cl::init(2000), cl::Hidden);
90 
91 static cl::opt<unsigned> SinkLoadBlocksThreshold(
92     "machine-sink-load-blocks-threshold",
93     cl::desc("Do not try to find alias store for a load if the block number in "
94              "the straight line is higher than this threshold."),
95     cl::init(20), cl::Hidden);
96 
97 static cl::opt<bool>
98 SinkInstsIntoLoop("sink-insts-to-avoid-spills",
99                   cl::desc("Sink instructions into loops to avoid "
100                            "register spills"),
101                   cl::init(false), cl::Hidden);
102 
103 static cl::opt<unsigned> SinkIntoLoopLimit(
104     "machine-sink-loop-limit",
105     cl::desc("The maximum number of instructions considered for loop sinking."),
106     cl::init(50), cl::Hidden);
107 
108 STATISTIC(NumSunk,      "Number of machine instructions sunk");
109 STATISTIC(NumLoopSunk,  "Number of machine instructions sunk into a loop");
110 STATISTIC(NumSplit,     "Number of critical edges split");
111 STATISTIC(NumCoalesces, "Number of copies coalesced");
112 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
113 
114 namespace {
115 
116   class MachineSinking : public MachineFunctionPass {
117     const TargetInstrInfo *TII;
118     const TargetRegisterInfo *TRI;
119     MachineRegisterInfo  *MRI;     // Machine register information
120     MachineDominatorTree *DT;      // Machine dominator tree
121     MachinePostDominatorTree *PDT; // Machine post dominator tree
122     MachineLoopInfo *LI;
123     MachineBlockFrequencyInfo *MBFI;
124     const MachineBranchProbabilityInfo *MBPI;
125     AliasAnalysis *AA;
126     RegisterClassInfo RegClassInfo;
127 
128     // Remember which edges have been considered for breaking.
129     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
130     CEBCandidates;
131     // Remember which edges we are about to split.
132     // This is different from CEBCandidates since those edges
133     // will be split.
134     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
135 
136     DenseSet<Register> RegsToClearKillFlags;
137 
138     using AllSuccsCache =
139         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
140 
141     /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
142     /// post-dominated by another DBG_VALUE of the same variable location.
143     /// This is necessary to detect sequences such as:
144     ///     %0 = someinst
145     ///     DBG_VALUE %0, !123, !DIExpression()
146     ///     %1 = anotherinst
147     ///     DBG_VALUE %1, !123, !DIExpression()
148     /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
149     /// would re-order assignments.
150     using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
151 
152     /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
153     /// debug instructions to sink.
154     SmallDenseMap<unsigned, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
155 
156     /// Record of debug variables that have had their locations set in the
157     /// current block.
158     DenseSet<DebugVariable> SeenDbgVars;
159 
160     std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>
161         HasStoreCache;
162     std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>,
163              std::vector<MachineInstr *>>
164         StoreInstrCache;
165 
166     /// Cached BB's register pressure.
167     std::map<MachineBasicBlock *, std::vector<unsigned>> CachedRegisterPressure;
168 
169   public:
170     static char ID; // Pass identification
171 
172     MachineSinking() : MachineFunctionPass(ID) {
173       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
174     }
175 
176     bool runOnMachineFunction(MachineFunction &MF) override;
177 
178     void getAnalysisUsage(AnalysisUsage &AU) const override {
179       MachineFunctionPass::getAnalysisUsage(AU);
180       AU.addRequired<AAResultsWrapperPass>();
181       AU.addRequired<MachineDominatorTree>();
182       AU.addRequired<MachinePostDominatorTree>();
183       AU.addRequired<MachineLoopInfo>();
184       AU.addRequired<MachineBranchProbabilityInfo>();
185       AU.addPreserved<MachineLoopInfo>();
186       if (UseBlockFreqInfo)
187         AU.addRequired<MachineBlockFrequencyInfo>();
188     }
189 
190     void releaseMemory() override {
191       CEBCandidates.clear();
192     }
193 
194   private:
195     bool ProcessBlock(MachineBasicBlock &MBB);
196     void ProcessDbgInst(MachineInstr &MI);
197     bool isWorthBreakingCriticalEdge(MachineInstr &MI,
198                                      MachineBasicBlock *From,
199                                      MachineBasicBlock *To);
200 
201     bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
202                          MachineInstr &MI);
203 
204     /// Postpone the splitting of the given critical
205     /// edge (\p From, \p To).
206     ///
207     /// We do not split the edges on the fly. Indeed, this invalidates
208     /// the dominance information and thus triggers a lot of updates
209     /// of that information underneath.
210     /// Instead, we postpone all the splits after each iteration of
211     /// the main loop. That way, the information is at least valid
212     /// for the lifetime of an iteration.
213     ///
214     /// \return True if the edge is marked as toSplit, false otherwise.
215     /// False can be returned if, for instance, this is not profitable.
216     bool PostponeSplitCriticalEdge(MachineInstr &MI,
217                                    MachineBasicBlock *From,
218                                    MachineBasicBlock *To,
219                                    bool BreakPHIEdge);
220     bool SinkInstruction(MachineInstr &MI, bool &SawStore,
221                          AllSuccsCache &AllSuccessors);
222 
223     /// If we sink a COPY inst, some debug users of it's destination may no
224     /// longer be dominated by the COPY, and will eventually be dropped.
225     /// This is easily rectified by forwarding the non-dominated debug uses
226     /// to the copy source.
227     void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
228                                        MachineBasicBlock *TargetBlock);
229     bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
230                                  MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
231                                  bool &LocalUse) const;
232     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
233                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
234 
235     void FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
236                                 SmallVectorImpl<MachineInstr *> &Candidates);
237     bool SinkIntoLoop(MachineLoop *L, MachineInstr &I);
238 
239     bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
240                               MachineBasicBlock *MBB,
241                               MachineBasicBlock *SuccToSinkTo,
242                               AllSuccsCache &AllSuccessors);
243 
244     bool PerformTrivialForwardCoalescing(MachineInstr &MI,
245                                          MachineBasicBlock *MBB);
246 
247     SmallVector<MachineBasicBlock *, 4> &
248     GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
249                            AllSuccsCache &AllSuccessors) const;
250 
251     std::vector<unsigned> &getBBRegisterPressure(MachineBasicBlock &MBB);
252   };
253 
254 } // end anonymous namespace
255 
256 char MachineSinking::ID = 0;
257 
258 char &llvm::MachineSinkingID = MachineSinking::ID;
259 
260 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
261                       "Machine code sinking", false, false)
262 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
263 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
264 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
265 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
266 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
267                     "Machine code sinking", false, false)
268 
269 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
270                                                      MachineBasicBlock *MBB) {
271   if (!MI.isCopy())
272     return false;
273 
274   Register SrcReg = MI.getOperand(1).getReg();
275   Register DstReg = MI.getOperand(0).getReg();
276   if (!Register::isVirtualRegister(SrcReg) ||
277       !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg))
278     return false;
279 
280   const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
281   const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
282   if (SRC != DRC)
283     return false;
284 
285   MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
286   if (DefMI->isCopyLike())
287     return false;
288   LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
289   LLVM_DEBUG(dbgs() << "*** to: " << MI);
290   MRI->replaceRegWith(DstReg, SrcReg);
291   MI.eraseFromParent();
292 
293   // Conservatively, clear any kill flags, since it's possible that they are no
294   // longer correct.
295   MRI->clearKillFlags(SrcReg);
296 
297   ++NumCoalesces;
298   return true;
299 }
300 
301 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
302 /// occur in blocks dominated by the specified block. If any use is in the
303 /// definition block, then return false since it is never legal to move def
304 /// after uses.
305 bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
306                                              MachineBasicBlock *MBB,
307                                              MachineBasicBlock *DefMBB,
308                                              bool &BreakPHIEdge,
309                                              bool &LocalUse) const {
310   assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs");
311 
312   // Ignore debug uses because debug info doesn't affect the code.
313   if (MRI->use_nodbg_empty(Reg))
314     return true;
315 
316   // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
317   // into and they are all PHI nodes. In this case, machine-sink must break
318   // the critical edge first. e.g.
319   //
320   // %bb.1:
321   //   Predecessors according to CFG: %bb.0
322   //     ...
323   //     %def = DEC64_32r %x, implicit-def dead %eflags
324   //     ...
325   //     JE_4 <%bb.37>, implicit %eflags
326   //   Successors according to CFG: %bb.37 %bb.2
327   //
328   // %bb.2:
329   //     %p = PHI %y, %bb.0, %def, %bb.1
330   if (all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) {
331         MachineInstr *UseInst = MO.getParent();
332         unsigned OpNo = UseInst->getOperandNo(&MO);
333         MachineBasicBlock *UseBlock = UseInst->getParent();
334         return UseBlock == MBB && UseInst->isPHI() &&
335                UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
336       })) {
337     BreakPHIEdge = true;
338     return true;
339   }
340 
341   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
342     // Determine the block of the use.
343     MachineInstr *UseInst = MO.getParent();
344     unsigned OpNo = &MO - &UseInst->getOperand(0);
345     MachineBasicBlock *UseBlock = UseInst->getParent();
346     if (UseInst->isPHI()) {
347       // PHI nodes use the operand in the predecessor block, not the block with
348       // the PHI.
349       UseBlock = UseInst->getOperand(OpNo+1).getMBB();
350     } else if (UseBlock == DefMBB) {
351       LocalUse = true;
352       return false;
353     }
354 
355     // Check that it dominates.
356     if (!DT->dominates(MBB, UseBlock))
357       return false;
358   }
359 
360   return true;
361 }
362 
363 /// Return true if this machine instruction loads from global offset table or
364 /// constant pool.
365 static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
366   assert(MI.mayLoad() && "Expected MI that loads!");
367 
368   // If we lost memory operands, conservatively assume that the instruction
369   // reads from everything..
370   if (MI.memoperands_empty())
371     return true;
372 
373   for (MachineMemOperand *MemOp : MI.memoperands())
374     if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
375       if (PSV->isGOT() || PSV->isConstantPool())
376         return true;
377 
378   return false;
379 }
380 
381 void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
382     SmallVectorImpl<MachineInstr *> &Candidates) {
383   for (auto &MI : *BB) {
384     LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI);
385     if (!TII->shouldSink(MI)) {
386       LLVM_DEBUG(dbgs() << "LoopSink: Instruction not a candidate for this "
387                            "target\n");
388       continue;
389     }
390     if (!L->isLoopInvariant(MI)) {
391       LLVM_DEBUG(dbgs() << "LoopSink: Instruction is not loop invariant\n");
392       continue;
393     }
394     bool DontMoveAcrossStore = true;
395     if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) {
396       LLVM_DEBUG(dbgs() << "LoopSink: Instruction not safe to move.\n");
397       continue;
398     }
399     if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
400       LLVM_DEBUG(dbgs() << "LoopSink: Dont sink GOT or constant pool loads\n");
401       continue;
402     }
403     if (MI.isConvergent())
404       continue;
405 
406     const MachineOperand &MO = MI.getOperand(0);
407     if (!MO.isReg() || !MO.getReg() || !MO.isDef())
408       continue;
409     if (!MRI->hasOneDef(MO.getReg()))
410       continue;
411 
412     LLVM_DEBUG(dbgs() << "LoopSink: Instruction added as candidate.\n");
413     Candidates.push_back(&MI);
414   }
415 }
416 
417 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
418   if (skipFunction(MF.getFunction()))
419     return false;
420 
421   LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
422 
423   TII = MF.getSubtarget().getInstrInfo();
424   TRI = MF.getSubtarget().getRegisterInfo();
425   MRI = &MF.getRegInfo();
426   DT = &getAnalysis<MachineDominatorTree>();
427   PDT = &getAnalysis<MachinePostDominatorTree>();
428   LI = &getAnalysis<MachineLoopInfo>();
429   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
430   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
431   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
432   RegClassInfo.runOnMachineFunction(MF);
433 
434   // MachineSink currently uses MachineLoopInfo, which only recognizes natural
435   // loops. As such, we could sink instructions into irreducible cycles, which
436   // would be non-profitable.
437   // WARNING: The current implementation of hasStoreBetween() is incorrect for
438   // sinking into irreducible cycles (PR53990), this bailout is currently
439   // necessary for correctness, not just profitability.
440   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
441   if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *LI))
442     return false;
443 
444   bool EverMadeChange = false;
445 
446   while (true) {
447     bool MadeChange = false;
448 
449     // Process all basic blocks.
450     CEBCandidates.clear();
451     ToSplit.clear();
452     for (auto &MBB: MF)
453       MadeChange |= ProcessBlock(MBB);
454 
455     // If we have anything we marked as toSplit, split it now.
456     for (auto &Pair : ToSplit) {
457       auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
458       if (NewSucc != nullptr) {
459         LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
460                           << printMBBReference(*Pair.first) << " -- "
461                           << printMBBReference(*NewSucc) << " -- "
462                           << printMBBReference(*Pair.second) << '\n');
463         if (MBFI)
464           MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);
465 
466         MadeChange = true;
467         ++NumSplit;
468       } else
469         LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
470     }
471     // If this iteration over the code changed anything, keep iterating.
472     if (!MadeChange) break;
473     EverMadeChange = true;
474   }
475 
476   if (SinkInstsIntoLoop) {
477     SmallVector<MachineLoop *, 8> Loops(LI->begin(), LI->end());
478     for (auto *L : Loops) {
479       MachineBasicBlock *Preheader = LI->findLoopPreheader(L);
480       if (!Preheader) {
481         LLVM_DEBUG(dbgs() << "LoopSink: Can't find preheader\n");
482         continue;
483       }
484       SmallVector<MachineInstr *, 8> Candidates;
485       FindLoopSinkCandidates(L, Preheader, Candidates);
486 
487       // Walk the candidates in reverse order so that we start with the use
488       // of a def-use chain, if there is any.
489       // TODO: Sort the candidates using a cost-model.
490       unsigned i = 0;
491       for (MachineInstr *I : llvm::reverse(Candidates)) {
492         if (i++ == SinkIntoLoopLimit) {
493           LLVM_DEBUG(dbgs() << "LoopSink:   Limit reached of instructions to "
494                                "be analysed.");
495           break;
496         }
497 
498         if (!SinkIntoLoop(L, *I))
499           break;
500         EverMadeChange = true;
501         ++NumLoopSunk;
502       }
503     }
504   }
505 
506   HasStoreCache.clear();
507   StoreInstrCache.clear();
508 
509   // Now clear any kill flags for recorded registers.
510   for (auto I : RegsToClearKillFlags)
511     MRI->clearKillFlags(I);
512   RegsToClearKillFlags.clear();
513 
514   return EverMadeChange;
515 }
516 
517 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
518   // Can't sink anything out of a block that has less than two successors.
519   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
520 
521   // Don't bother sinking code out of unreachable blocks. In addition to being
522   // unprofitable, it can also lead to infinite looping, because in an
523   // unreachable loop there may be nowhere to stop.
524   if (!DT->isReachableFromEntry(&MBB)) return false;
525 
526   bool MadeChange = false;
527 
528   // Cache all successors, sorted by frequency info and loop depth.
529   AllSuccsCache AllSuccessors;
530 
531   // Walk the basic block bottom-up.  Remember if we saw a store.
532   MachineBasicBlock::iterator I = MBB.end();
533   --I;
534   bool ProcessedBegin, SawStore = false;
535   do {
536     MachineInstr &MI = *I;  // The instruction to sink.
537 
538     // Predecrement I (if it's not begin) so that it isn't invalidated by
539     // sinking.
540     ProcessedBegin = I == MBB.begin();
541     if (!ProcessedBegin)
542       --I;
543 
544     if (MI.isDebugOrPseudoInstr()) {
545       if (MI.isDebugValue())
546         ProcessDbgInst(MI);
547       continue;
548     }
549 
550     bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
551     if (Joined) {
552       MadeChange = true;
553       continue;
554     }
555 
556     if (SinkInstruction(MI, SawStore, AllSuccessors)) {
557       ++NumSunk;
558       MadeChange = true;
559     }
560 
561     // If we just processed the first instruction in the block, we're done.
562   } while (!ProcessedBegin);
563 
564   SeenDbgUsers.clear();
565   SeenDbgVars.clear();
566   // recalculate the bb register pressure after sinking one BB.
567   CachedRegisterPressure.clear();
568 
569   return MadeChange;
570 }
571 
572 void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
573   // When we see DBG_VALUEs for registers, record any vreg it reads, so that
574   // we know what to sink if the vreg def sinks.
575   assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
576 
577   DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
578                     MI.getDebugLoc()->getInlinedAt());
579   bool SeenBefore = SeenDbgVars.contains(Var);
580 
581   for (MachineOperand &MO : MI.debug_operands()) {
582     if (MO.isReg() && MO.getReg().isVirtual())
583       SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
584   }
585 
586   // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
587   SeenDbgVars.insert(Var);
588 }
589 
590 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
591                                                  MachineBasicBlock *From,
592                                                  MachineBasicBlock *To) {
593   // FIXME: Need much better heuristics.
594 
595   // If the pass has already considered breaking this edge (during this pass
596   // through the function), then let's go ahead and break it. This means
597   // sinking multiple "cheap" instructions into the same block.
598   if (!CEBCandidates.insert(std::make_pair(From, To)).second)
599     return true;
600 
601   if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
602     return true;
603 
604   if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
605       BranchProbability(SplitEdgeProbabilityThreshold, 100))
606     return true;
607 
608   // MI is cheap, we probably don't want to break the critical edge for it.
609   // However, if this would allow some definitions of its source operands
610   // to be sunk then it's probably worth it.
611   for (const MachineOperand &MO : MI.operands()) {
612     if (!MO.isReg() || !MO.isUse())
613       continue;
614     Register Reg = MO.getReg();
615     if (Reg == 0)
616       continue;
617 
618     // We don't move live definitions of physical registers,
619     // so sinking their uses won't enable any opportunities.
620     if (Register::isPhysicalRegister(Reg))
621       continue;
622 
623     // If this instruction is the only user of a virtual register,
624     // check if breaking the edge will enable sinking
625     // both this instruction and the defining instruction.
626     if (MRI->hasOneNonDBGUse(Reg)) {
627       // If the definition resides in same MBB,
628       // claim it's likely we can sink these together.
629       // If definition resides elsewhere, we aren't
630       // blocking it from being sunk so don't break the edge.
631       MachineInstr *DefMI = MRI->getVRegDef(Reg);
632       if (DefMI->getParent() == MI.getParent())
633         return true;
634     }
635   }
636 
637   return false;
638 }
639 
640 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
641                                                MachineBasicBlock *FromBB,
642                                                MachineBasicBlock *ToBB,
643                                                bool BreakPHIEdge) {
644   if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
645     return false;
646 
647   // Avoid breaking back edge. From == To means backedge for single BB loop.
648   if (!SplitEdges || FromBB == ToBB)
649     return false;
650 
651   // Check for backedges of more "complex" loops.
652   if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
653       LI->isLoopHeader(ToBB))
654     return false;
655 
656   // It's not always legal to break critical edges and sink the computation
657   // to the edge.
658   //
659   // %bb.1:
660   // v1024
661   // Beq %bb.3
662   // <fallthrough>
663   // %bb.2:
664   // ... no uses of v1024
665   // <fallthrough>
666   // %bb.3:
667   // ...
668   //       = v1024
669   //
670   // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
671   //
672   // %bb.1:
673   // ...
674   // Bne %bb.2
675   // %bb.4:
676   // v1024 =
677   // B %bb.3
678   // %bb.2:
679   // ... no uses of v1024
680   // <fallthrough>
681   // %bb.3:
682   // ...
683   //       = v1024
684   //
685   // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
686   // flow. We need to ensure the new basic block where the computation is
687   // sunk to dominates all the uses.
688   // It's only legal to break critical edge and sink the computation to the
689   // new block if all the predecessors of "To", except for "From", are
690   // not dominated by "From". Given SSA property, this means these
691   // predecessors are dominated by "To".
692   //
693   // There is no need to do this check if all the uses are PHI nodes. PHI
694   // sources are only defined on the specific predecessor edges.
695   if (!BreakPHIEdge) {
696     for (MachineBasicBlock *Pred : ToBB->predecessors())
697       if (Pred != FromBB && !DT->dominates(ToBB, Pred))
698         return false;
699   }
700 
701   ToSplit.insert(std::make_pair(FromBB, ToBB));
702 
703   return true;
704 }
705 
706 std::vector<unsigned> &
707 MachineSinking::getBBRegisterPressure(MachineBasicBlock &MBB) {
708   // Currently to save compiling time, MBB's register pressure will not change
709   // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
710   // register pressure is changed after sinking any instructions into it.
711   // FIXME: need a accurate and cheap register pressure estiminate model here.
712   auto RP = CachedRegisterPressure.find(&MBB);
713   if (RP != CachedRegisterPressure.end())
714     return RP->second;
715 
716   RegionPressure Pressure;
717   RegPressureTracker RPTracker(Pressure);
718 
719   // Initialize the register pressure tracker.
720   RPTracker.init(MBB.getParent(), &RegClassInfo, nullptr, &MBB, MBB.end(),
721                  /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
722 
723   for (MachineBasicBlock::iterator MII = MBB.instr_end(),
724                                    MIE = MBB.instr_begin();
725        MII != MIE; --MII) {
726     MachineInstr &MI = *std::prev(MII);
727     if (MI.isDebugInstr() || MI.isPseudoProbe())
728       continue;
729     RegisterOperands RegOpers;
730     RegOpers.collect(MI, *TRI, *MRI, false, false);
731     RPTracker.recedeSkipDebugValues();
732     assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
733     RPTracker.recede(RegOpers);
734   }
735 
736   RPTracker.closeRegion();
737   auto It = CachedRegisterPressure.insert(
738       std::make_pair(&MBB, RPTracker.getPressure().MaxSetPressure));
739   return It.first->second;
740 }
741 
742 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
743 bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
744                                           MachineBasicBlock *MBB,
745                                           MachineBasicBlock *SuccToSinkTo,
746                                           AllSuccsCache &AllSuccessors) {
747   assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
748 
749   if (MBB == SuccToSinkTo)
750     return false;
751 
752   // It is profitable if SuccToSinkTo does not post dominate current block.
753   if (!PDT->dominates(SuccToSinkTo, MBB))
754     return true;
755 
756   // It is profitable to sink an instruction from a deeper loop to a shallower
757   // loop, even if the latter post-dominates the former (PR21115).
758   if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
759     return true;
760 
761   // Check if only use in post dominated block is PHI instruction.
762   bool NonPHIUse = false;
763   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
764     MachineBasicBlock *UseBlock = UseInst.getParent();
765     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
766       NonPHIUse = true;
767   }
768   if (!NonPHIUse)
769     return true;
770 
771   // If SuccToSinkTo post dominates then also it may be profitable if MI
772   // can further profitably sinked into another block in next round.
773   bool BreakPHIEdge = false;
774   // FIXME - If finding successor is compile time expensive then cache results.
775   if (MachineBasicBlock *MBB2 =
776           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
777     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
778 
779   MachineLoop *ML = LI->getLoopFor(MBB);
780 
781   // If the instruction is not inside a loop, it is not profitable to sink MI to
782   // a post dominate block SuccToSinkTo.
783   if (!ML)
784     return false;
785 
786   auto isRegisterPressureSetExceedLimit = [&](const TargetRegisterClass *RC) {
787     unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
788     const int *PS = TRI->getRegClassPressureSets(RC);
789     // Get register pressure for block SuccToSinkTo.
790     std::vector<unsigned> BBRegisterPressure =
791         getBBRegisterPressure(*SuccToSinkTo);
792     for (; *PS != -1; PS++)
793       // check if any register pressure set exceeds limit in block SuccToSinkTo
794       // after sinking.
795       if (Weight + BBRegisterPressure[*PS] >=
796           TRI->getRegPressureSetLimit(*MBB->getParent(), *PS))
797         return true;
798     return false;
799   };
800 
801   // If this instruction is inside a loop and sinking this instruction can make
802   // more registers live range shorten, it is still prifitable.
803   for (const MachineOperand &MO : MI.operands()) {
804     // Ignore non-register operands.
805     if (!MO.isReg())
806       continue;
807     Register Reg = MO.getReg();
808     if (Reg == 0)
809       continue;
810 
811     if (Register::isPhysicalRegister(Reg)) {
812       if (MO.isUse() &&
813           (MRI->isConstantPhysReg(Reg) || TII->isIgnorableUse(MO)))
814         continue;
815 
816       // Don't handle non-constant and non-ignorable physical register.
817       return false;
818     }
819 
820     // Users for the defs are all dominated by SuccToSinkTo.
821     if (MO.isDef()) {
822       // This def register's live range is shortened after sinking.
823       bool LocalUse = false;
824       if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
825                                    LocalUse))
826         return false;
827     } else {
828       MachineInstr *DefMI = MRI->getVRegDef(Reg);
829       // DefMI is defined outside of loop. There should be no live range
830       // impact for this operand. Defination outside of loop means:
831       // 1: defination is outside of loop.
832       // 2: defination is in this loop, but it is a PHI in the loop header.
833       if (LI->getLoopFor(DefMI->getParent()) != ML ||
834           (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
835         continue;
836       // The DefMI is defined inside the loop.
837       // If sinking this operand makes some register pressure set exceed limit,
838       // it is not profitable.
839       if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg))) {
840         LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
841         return false;
842       }
843     }
844   }
845 
846   // If MI is in loop and all its operands are alive across the whole loop or if
847   // no operand sinking make register pressure set exceed limit, it is
848   // profitable to sink MI.
849   return true;
850 }
851 
852 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
853 /// computing it if it was not already cached.
854 SmallVector<MachineBasicBlock *, 4> &
855 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
856                                        AllSuccsCache &AllSuccessors) const {
857   // Do we have the sorted successors in cache ?
858   auto Succs = AllSuccessors.find(MBB);
859   if (Succs != AllSuccessors.end())
860     return Succs->second;
861 
862   SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());
863 
864   // Handle cases where sinking can happen but where the sink point isn't a
865   // successor. For example:
866   //
867   //   x = computation
868   //   if () {} else {}
869   //   use x
870   //
871   for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
872     // DomTree children of MBB that have MBB as immediate dominator are added.
873     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
874         // Skip MBBs already added to the AllSuccs vector above.
875         !MBB->isSuccessor(DTChild->getBlock()))
876       AllSuccs.push_back(DTChild->getBlock());
877   }
878 
879   // Sort Successors according to their loop depth or block frequency info.
880   llvm::stable_sort(
881       AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
882         uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
883         uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
884         bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
885         return HasBlockFreq ? LHSFreq < RHSFreq
886                             : LI->getLoopDepth(L) < LI->getLoopDepth(R);
887       });
888 
889   auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
890 
891   return it.first->second;
892 }
893 
894 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
895 MachineBasicBlock *
896 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
897                                  bool &BreakPHIEdge,
898                                  AllSuccsCache &AllSuccessors) {
899   assert (MBB && "Invalid MachineBasicBlock!");
900 
901   // Loop over all the operands of the specified instruction.  If there is
902   // anything we can't handle, bail out.
903 
904   // SuccToSinkTo - This is the successor to sink this instruction to, once we
905   // decide.
906   MachineBasicBlock *SuccToSinkTo = nullptr;
907   for (const MachineOperand &MO : MI.operands()) {
908     if (!MO.isReg()) continue;  // Ignore non-register operands.
909 
910     Register Reg = MO.getReg();
911     if (Reg == 0) continue;
912 
913     if (Register::isPhysicalRegister(Reg)) {
914       if (MO.isUse()) {
915         // If the physreg has no defs anywhere, it's just an ambient register
916         // and we can freely move its uses. Alternatively, if it's allocatable,
917         // it could get allocated to something with a def during allocation.
918         if (!MRI->isConstantPhysReg(Reg) && !TII->isIgnorableUse(MO))
919           return nullptr;
920       } else if (!MO.isDead()) {
921         // A def that isn't dead. We can't move it.
922         return nullptr;
923       }
924     } else {
925       // Virtual register uses are always safe to sink.
926       if (MO.isUse()) continue;
927 
928       // If it's not safe to move defs of the register class, then abort.
929       if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
930         return nullptr;
931 
932       // Virtual register defs can only be sunk if all their uses are in blocks
933       // dominated by one of the successors.
934       if (SuccToSinkTo) {
935         // If a previous operand picked a block to sink to, then this operand
936         // must be sinkable to the same block.
937         bool LocalUse = false;
938         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
939                                      BreakPHIEdge, LocalUse))
940           return nullptr;
941 
942         continue;
943       }
944 
945       // Otherwise, we should look at all the successors and decide which one
946       // we should sink to. If we have reliable block frequency information
947       // (frequency != 0) available, give successors with smaller frequencies
948       // higher priority, otherwise prioritize smaller loop depths.
949       for (MachineBasicBlock *SuccBlock :
950            GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
951         bool LocalUse = false;
952         if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
953                                     BreakPHIEdge, LocalUse)) {
954           SuccToSinkTo = SuccBlock;
955           break;
956         }
957         if (LocalUse)
958           // Def is used locally, it's never safe to move this def.
959           return nullptr;
960       }
961 
962       // If we couldn't find a block to sink to, ignore this instruction.
963       if (!SuccToSinkTo)
964         return nullptr;
965       if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
966         return nullptr;
967     }
968   }
969 
970   // It is not possible to sink an instruction into its own block.  This can
971   // happen with loops.
972   if (MBB == SuccToSinkTo)
973     return nullptr;
974 
975   // It's not safe to sink instructions to EH landing pad. Control flow into
976   // landing pad is implicitly defined.
977   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
978     return nullptr;
979 
980   // It ought to be okay to sink instructions into an INLINEASM_BR target, but
981   // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
982   // the source block (which this code does not yet do). So for now, forbid
983   // doing so.
984   if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
985     return nullptr;
986 
987   return SuccToSinkTo;
988 }
989 
990 /// Return true if MI is likely to be usable as a memory operation by the
991 /// implicit null check optimization.
992 ///
993 /// This is a "best effort" heuristic, and should not be relied upon for
994 /// correctness.  This returning true does not guarantee that the implicit null
995 /// check optimization is legal over MI, and this returning false does not
996 /// guarantee MI cannot possibly be used to do a null check.
997 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
998                                              const TargetInstrInfo *TII,
999                                              const TargetRegisterInfo *TRI) {
1000   using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
1001 
1002   auto *MBB = MI.getParent();
1003   if (MBB->pred_size() != 1)
1004     return false;
1005 
1006   auto *PredMBB = *MBB->pred_begin();
1007   auto *PredBB = PredMBB->getBasicBlock();
1008 
1009   // Frontends that don't use implicit null checks have no reason to emit
1010   // branches with make.implicit metadata, and this function should always
1011   // return false for them.
1012   if (!PredBB ||
1013       !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1014     return false;
1015 
1016   const MachineOperand *BaseOp;
1017   int64_t Offset;
1018   bool OffsetIsScalable;
1019   if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
1020     return false;
1021 
1022   if (!BaseOp->isReg())
1023     return false;
1024 
1025   if (!(MI.mayLoad() && !MI.isPredicable()))
1026     return false;
1027 
1028   MachineBranchPredicate MBP;
1029   if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
1030     return false;
1031 
1032   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1033          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1034           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1035          MBP.LHS.getReg() == BaseOp->getReg();
1036 }
1037 
1038 /// If the sunk instruction is a copy, try to forward the copy instead of
1039 /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
1040 /// there's any subregister weirdness involved. Returns true if copy
1041 /// propagation occurred.
1042 static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,
1043                                  Register Reg) {
1044   const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
1045   const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
1046 
1047   // Copy DBG_VALUE operand and set the original to undef. We then check to
1048   // see whether this is something that can be copy-forwarded. If it isn't,
1049   // continue around the loop.
1050 
1051   const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
1052   auto CopyOperands = TII.isCopyInstr(SinkInst);
1053   if (!CopyOperands)
1054     return false;
1055   SrcMO = CopyOperands->Source;
1056   DstMO = CopyOperands->Destination;
1057 
1058   // Check validity of forwarding this copy.
1059   bool PostRA = MRI.getNumVirtRegs() == 0;
1060 
1061   // Trying to forward between physical and virtual registers is too hard.
1062   if (Reg.isVirtual() != SrcMO->getReg().isVirtual())
1063     return false;
1064 
1065   // Only try virtual register copy-forwarding before regalloc, and physical
1066   // register copy-forwarding after regalloc.
1067   bool arePhysRegs = !Reg.isVirtual();
1068   if (arePhysRegs != PostRA)
1069     return false;
1070 
1071   // Pre-regalloc, only forward if all subregisters agree (or there are no
1072   // subregs at all). More analysis might recover some forwardable copies.
1073   if (!PostRA)
1074     for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))
1075       if (DbgMO.getSubReg() != SrcMO->getSubReg() ||
1076           DbgMO.getSubReg() != DstMO->getSubReg())
1077         return false;
1078 
1079   // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
1080   // of this copy. Only forward the copy if the DBG_VALUE operand exactly
1081   // matches the copy destination.
1082   if (PostRA && Reg != DstMO->getReg())
1083     return false;
1084 
1085   for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {
1086     DbgMO.setReg(SrcMO->getReg());
1087     DbgMO.setSubReg(SrcMO->getSubReg());
1088   }
1089   return true;
1090 }
1091 
1092 using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1093 /// Sink an instruction and its associated debug instructions.
1094 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
1095                         MachineBasicBlock::iterator InsertPos,
1096                         SmallVectorImpl<MIRegs> &DbgValuesToSink) {
1097 
1098   // If we cannot find a location to use (merge with), then we erase the debug
1099   // location to prevent debug-info driven tools from potentially reporting
1100   // wrong location information.
1101   if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
1102     MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
1103                                                  InsertPos->getDebugLoc()));
1104   else
1105     MI.setDebugLoc(DebugLoc());
1106 
1107   // Move the instruction.
1108   MachineBasicBlock *ParentBlock = MI.getParent();
1109   SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
1110                       ++MachineBasicBlock::iterator(MI));
1111 
1112   // Sink a copy of debug users to the insert position. Mark the original
1113   // DBG_VALUE location as 'undef', indicating that any earlier variable
1114   // location should be terminated as we've optimised away the value at this
1115   // point.
1116   for (auto DbgValueToSink : DbgValuesToSink) {
1117     MachineInstr *DbgMI = DbgValueToSink.first;
1118     MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(DbgMI);
1119     SuccToSinkTo.insert(InsertPos, NewDbgMI);
1120 
1121     bool PropagatedAllSunkOps = true;
1122     for (unsigned Reg : DbgValueToSink.second) {
1123       if (DbgMI->hasDebugOperandForReg(Reg)) {
1124         if (!attemptDebugCopyProp(MI, *DbgMI, Reg)) {
1125           PropagatedAllSunkOps = false;
1126           break;
1127         }
1128       }
1129     }
1130     if (!PropagatedAllSunkOps)
1131       DbgMI->setDebugValueUndef();
1132   }
1133 }
1134 
1135 /// hasStoreBetween - check if there is store betweeen straight line blocks From
1136 /// and To.
1137 bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1138                                      MachineBasicBlock *To, MachineInstr &MI) {
1139   // Make sure From and To are in straight line which means From dominates To
1140   // and To post dominates From.
1141   if (!DT->dominates(From, To) || !PDT->dominates(To, From))
1142     return true;
1143 
1144   auto BlockPair = std::make_pair(From, To);
1145 
1146   // Does these two blocks pair be queried before and have a definite cached
1147   // result?
1148   if (HasStoreCache.find(BlockPair) != HasStoreCache.end())
1149     return HasStoreCache[BlockPair];
1150 
1151   if (StoreInstrCache.find(BlockPair) != StoreInstrCache.end())
1152     return llvm::any_of(StoreInstrCache[BlockPair], [&](MachineInstr *I) {
1153       return I->mayAlias(AA, MI, false);
1154     });
1155 
1156   bool SawStore = false;
1157   bool HasAliasedStore = false;
1158   DenseSet<MachineBasicBlock *> HandledBlocks;
1159   DenseSet<MachineBasicBlock *> HandledDomBlocks;
1160   // Go through all reachable blocks from From.
1161   for (MachineBasicBlock *BB : depth_first(From)) {
1162     // We insert the instruction at the start of block To, so no need to worry
1163     // about stores inside To.
1164     // Store in block From should be already considered when just enter function
1165     // SinkInstruction.
1166     if (BB == To || BB == From)
1167       continue;
1168 
1169     // We already handle this BB in previous iteration.
1170     if (HandledBlocks.count(BB))
1171       continue;
1172 
1173     HandledBlocks.insert(BB);
1174     // To post dominates BB, it must be a path from block From.
1175     if (PDT->dominates(To, BB)) {
1176       if (!HandledDomBlocks.count(BB))
1177         HandledDomBlocks.insert(BB);
1178 
1179       // If this BB is too big or the block number in straight line between From
1180       // and To is too big, stop searching to save compiling time.
1181       if (BB->size() > SinkLoadInstsPerBlockThreshold ||
1182           HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1183         for (auto *DomBB : HandledDomBlocks) {
1184           if (DomBB != BB && DT->dominates(DomBB, BB))
1185             HasStoreCache[std::make_pair(DomBB, To)] = true;
1186           else if(DomBB != BB && DT->dominates(BB, DomBB))
1187             HasStoreCache[std::make_pair(From, DomBB)] = true;
1188         }
1189         HasStoreCache[BlockPair] = true;
1190         return true;
1191       }
1192 
1193       for (MachineInstr &I : *BB) {
1194         // Treat as alias conservatively for a call or an ordered memory
1195         // operation.
1196         if (I.isCall() || I.hasOrderedMemoryRef()) {
1197           for (auto *DomBB : HandledDomBlocks) {
1198             if (DomBB != BB && DT->dominates(DomBB, BB))
1199               HasStoreCache[std::make_pair(DomBB, To)] = true;
1200             else if(DomBB != BB && DT->dominates(BB, DomBB))
1201               HasStoreCache[std::make_pair(From, DomBB)] = true;
1202           }
1203           HasStoreCache[BlockPair] = true;
1204           return true;
1205         }
1206 
1207         if (I.mayStore()) {
1208           SawStore = true;
1209           // We still have chance to sink MI if all stores between are not
1210           // aliased to MI.
1211           // Cache all store instructions, so that we don't need to go through
1212           // all From reachable blocks for next load instruction.
1213           if (I.mayAlias(AA, MI, false))
1214             HasAliasedStore = true;
1215           StoreInstrCache[BlockPair].push_back(&I);
1216         }
1217       }
1218     }
1219   }
1220   // If there is no store at all, cache the result.
1221   if (!SawStore)
1222     HasStoreCache[BlockPair] = false;
1223   return HasAliasedStore;
1224 }
1225 
1226 /// Sink instructions into loops if profitable. This especially tries to prevent
1227 /// register spills caused by register pressure if there is little to no
1228 /// overhead moving instructions into loops.
1229 bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
1230   LLVM_DEBUG(dbgs() << "LoopSink: Finding sink block for: " << I);
1231   MachineBasicBlock *Preheader = L->getLoopPreheader();
1232   assert(Preheader && "Loop sink needs a preheader block");
1233   MachineBasicBlock *SinkBlock = nullptr;
1234   bool CanSink = true;
1235   const MachineOperand &MO = I.getOperand(0);
1236 
1237   for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
1238     LLVM_DEBUG(dbgs() << "LoopSink:   Analysing use: " << MI);
1239     if (!L->contains(&MI)) {
1240       LLVM_DEBUG(dbgs() << "LoopSink:   Use not in loop, can't sink.\n");
1241       CanSink = false;
1242       break;
1243     }
1244 
1245     // FIXME: Come up with a proper cost model that estimates whether sinking
1246     // the instruction (and thus possibly executing it on every loop
1247     // iteration) is more expensive than a register.
1248     // For now assumes that copies are cheap and thus almost always worth it.
1249     if (!MI.isCopy()) {
1250       LLVM_DEBUG(dbgs() << "LoopSink:   Use is not a copy\n");
1251       CanSink = false;
1252       break;
1253     }
1254     if (!SinkBlock) {
1255       SinkBlock = MI.getParent();
1256       LLVM_DEBUG(dbgs() << "LoopSink:   Setting sink block to: "
1257                         << printMBBReference(*SinkBlock) << "\n");
1258       continue;
1259     }
1260     SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent());
1261     if (!SinkBlock) {
1262       LLVM_DEBUG(dbgs() << "LoopSink:   Can't find nearest dominator\n");
1263       CanSink = false;
1264       break;
1265     }
1266     LLVM_DEBUG(dbgs() << "LoopSink:   Setting nearest common dom block: " <<
1267                printMBBReference(*SinkBlock) << "\n");
1268   }
1269 
1270   if (!CanSink) {
1271     LLVM_DEBUG(dbgs() << "LoopSink: Can't sink instruction.\n");
1272     return false;
1273   }
1274   if (!SinkBlock) {
1275     LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, can't find sink block.\n");
1276     return false;
1277   }
1278   if (SinkBlock == Preheader) {
1279     LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n");
1280     return false;
1281   }
1282   if (SinkBlock->size() > SinkLoadInstsPerBlockThreshold) {
1283     LLVM_DEBUG(dbgs() << "LoopSink: Not Sinking, block too large to analyse.\n");
1284     return false;
1285   }
1286 
1287   LLVM_DEBUG(dbgs() << "LoopSink: Sinking instruction!\n");
1288   SinkBlock->splice(SinkBlock->getFirstNonPHI(), Preheader, I);
1289 
1290   // The instruction is moved from its basic block, so do not retain the
1291   // debug information.
1292   assert(!I.isDebugInstr() && "Should not sink debug inst");
1293   I.setDebugLoc(DebugLoc());
1294   return true;
1295 }
1296 
1297 /// SinkInstruction - Determine whether it is safe to sink the specified machine
1298 /// instruction out of its current block into a successor.
1299 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1300                                      AllSuccsCache &AllSuccessors) {
1301   // Don't sink instructions that the target prefers not to sink.
1302   if (!TII->shouldSink(MI))
1303     return false;
1304 
1305   // Check if it's safe to move the instruction.
1306   if (!MI.isSafeToMove(AA, SawStore))
1307     return false;
1308 
1309   // Convergent operations may not be made control-dependent on additional
1310   // values.
1311   if (MI.isConvergent())
1312     return false;
1313 
1314   // Don't break implicit null checks.  This is a performance heuristic, and not
1315   // required for correctness.
1316   if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
1317     return false;
1318 
1319   // FIXME: This should include support for sinking instructions within the
1320   // block they are currently in to shorten the live ranges.  We often get
1321   // instructions sunk into the top of a large block, but it would be better to
1322   // also sink them down before their first use in the block.  This xform has to
1323   // be careful not to *increase* register pressure though, e.g. sinking
1324   // "x = y + z" down if it kills y and z would increase the live ranges of y
1325   // and z and only shrink the live range of x.
1326 
1327   bool BreakPHIEdge = false;
1328   MachineBasicBlock *ParentBlock = MI.getParent();
1329   MachineBasicBlock *SuccToSinkTo =
1330       FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1331 
1332   // If there are no outputs, it must have side-effects.
1333   if (!SuccToSinkTo)
1334     return false;
1335 
1336   // If the instruction to move defines a dead physical register which is live
1337   // when leaving the basic block, don't move it because it could turn into a
1338   // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
1339   for (const MachineOperand &MO : MI.operands()) {
1340     if (!MO.isReg() || MO.isUse())
1341       continue;
1342     Register Reg = MO.getReg();
1343     if (Reg == 0 || !Register::isPhysicalRegister(Reg))
1344       continue;
1345     if (SuccToSinkTo->isLiveIn(Reg))
1346       return false;
1347   }
1348 
1349   LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1350 
1351   // If the block has multiple predecessors, this is a critical edge.
1352   // Decide if we can sink along it or need to break the edge.
1353   if (SuccToSinkTo->pred_size() > 1) {
1354     // We cannot sink a load across a critical edge - there may be stores in
1355     // other code paths.
1356     bool TryBreak = false;
1357     bool Store =
1358         MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo, MI) : true;
1359     if (!MI.isSafeToMove(AA, Store)) {
1360       LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1361       TryBreak = true;
1362     }
1363 
1364     // We don't want to sink across a critical edge if we don't dominate the
1365     // successor. We could be introducing calculations to new code paths.
1366     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
1367       LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1368       TryBreak = true;
1369     }
1370 
1371     // Don't sink instructions into a loop.
1372     if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
1373       LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
1374       TryBreak = true;
1375     }
1376 
1377     // Otherwise we are OK with sinking along a critical edge.
1378     if (!TryBreak)
1379       LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1380     else {
1381       // Mark this edge as to be split.
1382       // If the edge can actually be split, the next iteration of the main loop
1383       // will sink MI in the newly created block.
1384       bool Status =
1385         PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1386       if (!Status)
1387         LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1388                              "break critical edge\n");
1389       // The instruction will not be sunk this time.
1390       return false;
1391     }
1392   }
1393 
1394   if (BreakPHIEdge) {
1395     // BreakPHIEdge is true if all the uses are in the successor MBB being
1396     // sunken into and they are all PHI nodes. In this case, machine-sink must
1397     // break the critical edge first.
1398     bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
1399                                             SuccToSinkTo, BreakPHIEdge);
1400     if (!Status)
1401       LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1402                            "break critical edge\n");
1403     // The instruction will not be sunk this time.
1404     return false;
1405   }
1406 
1407   // Determine where to insert into. Skip phi nodes.
1408   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
1409   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
1410     ++InsertPos;
1411 
1412   // Collect debug users of any vreg that this inst defines.
1413   SmallVector<MIRegs, 4> DbgUsersToSink;
1414   for (auto &MO : MI.operands()) {
1415     if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1416       continue;
1417     if (!SeenDbgUsers.count(MO.getReg()))
1418       continue;
1419 
1420     // Sink any users that don't pass any other DBG_VALUEs for this variable.
1421     auto &Users = SeenDbgUsers[MO.getReg()];
1422     for (auto &User : Users) {
1423       MachineInstr *DbgMI = User.getPointer();
1424       if (User.getInt()) {
1425         // This DBG_VALUE would re-order assignments. If we can't copy-propagate
1426         // it, it can't be recovered. Set it undef.
1427         if (!attemptDebugCopyProp(MI, *DbgMI, MO.getReg()))
1428           DbgMI->setDebugValueUndef();
1429       } else {
1430         DbgUsersToSink.push_back(
1431             {DbgMI, SmallVector<unsigned, 2>(1, MO.getReg())});
1432       }
1433     }
1434   }
1435 
1436   // After sinking, some debug users may not be dominated any more. If possible,
1437   // copy-propagate their operands. As it's expensive, don't do this if there's
1438   // no debuginfo in the program.
1439   if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1440     SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
1441 
1442   performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
1443 
1444   // Conservatively, clear any kill flags, since it's possible that they are no
1445   // longer correct.
1446   // Note that we have to clear the kill flags for any register this instruction
1447   // uses as we may sink over another instruction which currently kills the
1448   // used registers.
1449   for (MachineOperand &MO : MI.operands()) {
1450     if (MO.isReg() && MO.isUse())
1451       RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
1452   }
1453 
1454   return true;
1455 }
1456 
1457 void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1458     MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1459   assert(MI.isCopy());
1460   assert(MI.getOperand(1).isReg());
1461 
1462   // Enumerate all users of vreg operands that are def'd. Skip those that will
1463   // be sunk. For the rest, if they are not dominated by the block we will sink
1464   // MI into, propagate the copy source to them.
1465   SmallVector<MachineInstr *, 4> DbgDefUsers;
1466   SmallVector<Register, 4> DbgUseRegs;
1467   const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1468   for (auto &MO : MI.operands()) {
1469     if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1470       continue;
1471     DbgUseRegs.push_back(MO.getReg());
1472     for (auto &User : MRI.use_instructions(MO.getReg())) {
1473       if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
1474         continue;
1475 
1476       // If is in same block, will either sink or be use-before-def.
1477       if (User.getParent() == MI.getParent())
1478         continue;
1479 
1480       assert(User.hasDebugOperandForReg(MO.getReg()) &&
1481              "DBG_VALUE user of vreg, but has no operand for it?");
1482       DbgDefUsers.push_back(&User);
1483     }
1484   }
1485 
1486   // Point the users of this copy that are no longer dominated, at the source
1487   // of the copy.
1488   for (auto *User : DbgDefUsers) {
1489     for (auto &Reg : DbgUseRegs) {
1490       for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {
1491         DbgOp.setReg(MI.getOperand(1).getReg());
1492         DbgOp.setSubReg(MI.getOperand(1).getSubReg());
1493       }
1494     }
1495   }
1496 }
1497 
1498 //===----------------------------------------------------------------------===//
1499 // This pass is not intended to be a replacement or a complete alternative
1500 // for the pre-ra machine sink pass. It is only designed to sink COPY
1501 // instructions which should be handled after RA.
1502 //
1503 // This pass sinks COPY instructions into a successor block, if the COPY is not
1504 // used in the current block and the COPY is live-in to a single successor
1505 // (i.e., doesn't require the COPY to be duplicated).  This avoids executing the
1506 // copy on paths where their results aren't needed.  This also exposes
1507 // additional opportunites for dead copy elimination and shrink wrapping.
1508 //
1509 // These copies were either not handled by or are inserted after the MachineSink
1510 // pass. As an example of the former case, the MachineSink pass cannot sink
1511 // COPY instructions with allocatable source registers; for AArch64 these type
1512 // of copy instructions are frequently used to move function parameters (PhyReg)
1513 // into virtual registers in the entry block.
1514 //
1515 // For the machine IR below, this pass will sink %w19 in the entry into its
1516 // successor (%bb.1) because %w19 is only live-in in %bb.1.
1517 // %bb.0:
1518 //   %wzr = SUBSWri %w1, 1
1519 //   %w19 = COPY %w0
1520 //   Bcc 11, %bb.2
1521 // %bb.1:
1522 //   Live Ins: %w19
1523 //   BL @fun
1524 //   %w0 = ADDWrr %w0, %w19
1525 //   RET %w0
1526 // %bb.2:
1527 //   %w0 = COPY %wzr
1528 //   RET %w0
1529 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
1530 // able to see %bb.0 as a candidate.
1531 //===----------------------------------------------------------------------===//
1532 namespace {
1533 
1534 class PostRAMachineSinking : public MachineFunctionPass {
1535 public:
1536   bool runOnMachineFunction(MachineFunction &MF) override;
1537 
1538   static char ID;
1539   PostRAMachineSinking() : MachineFunctionPass(ID) {}
1540   StringRef getPassName() const override { return "PostRA Machine Sink"; }
1541 
1542   void getAnalysisUsage(AnalysisUsage &AU) const override {
1543     AU.setPreservesCFG();
1544     MachineFunctionPass::getAnalysisUsage(AU);
1545   }
1546 
1547   MachineFunctionProperties getRequiredProperties() const override {
1548     return MachineFunctionProperties().set(
1549         MachineFunctionProperties::Property::NoVRegs);
1550   }
1551 
1552 private:
1553   /// Track which register units have been modified and used.
1554   LiveRegUnits ModifiedRegUnits, UsedRegUnits;
1555 
1556   /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
1557   /// entry in this map for each unit it touches. The DBG_VALUE's entry
1558   /// consists of a pointer to the instruction itself, and a vector of registers
1559   /// referred to by the instruction that overlap the key register unit.
1560   DenseMap<unsigned, SmallVector<MIRegs, 2>> SeenDbgInstrs;
1561 
1562   /// Sink Copy instructions unused in the same block close to their uses in
1563   /// successors.
1564   bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
1565                      const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
1566 };
1567 } // namespace
1568 
1569 char PostRAMachineSinking::ID = 0;
1570 char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
1571 
1572 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
1573                 "PostRA Machine Sink", false, false)
1574 
1575 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
1576                                   const TargetRegisterInfo *TRI) {
1577   LiveRegUnits LiveInRegUnits(*TRI);
1578   LiveInRegUnits.addLiveIns(MBB);
1579   return !LiveInRegUnits.available(Reg);
1580 }
1581 
1582 static MachineBasicBlock *
1583 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1584                       const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1585                       unsigned Reg, const TargetRegisterInfo *TRI) {
1586   // Try to find a single sinkable successor in which Reg is live-in.
1587   MachineBasicBlock *BB = nullptr;
1588   for (auto *SI : SinkableBBs) {
1589     if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
1590       // If BB is set here, Reg is live-in to at least two sinkable successors,
1591       // so quit.
1592       if (BB)
1593         return nullptr;
1594       BB = SI;
1595     }
1596   }
1597   // Reg is not live-in to any sinkable successors.
1598   if (!BB)
1599     return nullptr;
1600 
1601   // Check if any register aliased with Reg is live-in in other successors.
1602   for (auto *SI : CurBB.successors()) {
1603     if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1604       return nullptr;
1605   }
1606   return BB;
1607 }
1608 
1609 static MachineBasicBlock *
1610 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1611                       const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1612                       ArrayRef<unsigned> DefedRegsInCopy,
1613                       const TargetRegisterInfo *TRI) {
1614   MachineBasicBlock *SingleBB = nullptr;
1615   for (auto DefReg : DefedRegsInCopy) {
1616     MachineBasicBlock *BB =
1617         getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1618     if (!BB || (SingleBB && SingleBB != BB))
1619       return nullptr;
1620     SingleBB = BB;
1621   }
1622   return SingleBB;
1623 }
1624 
1625 static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
1626                            SmallVectorImpl<unsigned> &UsedOpsInCopy,
1627                            LiveRegUnits &UsedRegUnits,
1628                            const TargetRegisterInfo *TRI) {
1629   for (auto U : UsedOpsInCopy) {
1630     MachineOperand &MO = MI->getOperand(U);
1631     Register SrcReg = MO.getReg();
1632     if (!UsedRegUnits.available(SrcReg)) {
1633       MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1634       for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1635         if (UI.killsRegister(SrcReg, TRI)) {
1636           UI.clearRegisterKills(SrcReg, TRI);
1637           MO.setIsKill(true);
1638           break;
1639         }
1640       }
1641     }
1642   }
1643 }
1644 
1645 static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
1646                          SmallVectorImpl<unsigned> &UsedOpsInCopy,
1647                          SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1648   MachineFunction &MF = *SuccBB->getParent();
1649   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1650   for (unsigned DefReg : DefedRegsInCopy)
1651     for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1652       SuccBB->removeLiveIn(*S);
1653   for (auto U : UsedOpsInCopy) {
1654     Register SrcReg = MI->getOperand(U).getReg();
1655     LaneBitmask Mask;
1656     for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S) {
1657       Mask |= (*S).second;
1658     }
1659     SuccBB->addLiveIn(SrcReg, Mask.any() ? Mask : LaneBitmask::getAll());
1660   }
1661   SuccBB->sortUniqueLiveIns();
1662 }
1663 
1664 static bool hasRegisterDependency(MachineInstr *MI,
1665                                   SmallVectorImpl<unsigned> &UsedOpsInCopy,
1666                                   SmallVectorImpl<unsigned> &DefedRegsInCopy,
1667                                   LiveRegUnits &ModifiedRegUnits,
1668                                   LiveRegUnits &UsedRegUnits) {
1669   bool HasRegDependency = false;
1670   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1671     MachineOperand &MO = MI->getOperand(i);
1672     if (!MO.isReg())
1673       continue;
1674     Register Reg = MO.getReg();
1675     if (!Reg)
1676       continue;
1677     if (MO.isDef()) {
1678       if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1679         HasRegDependency = true;
1680         break;
1681       }
1682       DefedRegsInCopy.push_back(Reg);
1683 
1684       // FIXME: instead of isUse(), readsReg() would be a better fix here,
1685       // For example, we can ignore modifications in reg with undef. However,
1686       // it's not perfectly clear if skipping the internal read is safe in all
1687       // other targets.
1688     } else if (MO.isUse()) {
1689       if (!ModifiedRegUnits.available(Reg)) {
1690         HasRegDependency = true;
1691         break;
1692       }
1693       UsedOpsInCopy.push_back(i);
1694     }
1695   }
1696   return HasRegDependency;
1697 }
1698 
1699 static SmallSet<MCRegister, 4> getRegUnits(MCRegister Reg,
1700                                            const TargetRegisterInfo *TRI) {
1701   SmallSet<MCRegister, 4> RegUnits;
1702   for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
1703     RegUnits.insert(*RI);
1704   return RegUnits;
1705 }
1706 
1707 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1708                                          MachineFunction &MF,
1709                                          const TargetRegisterInfo *TRI,
1710                                          const TargetInstrInfo *TII) {
1711   SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
1712   // FIXME: For now, we sink only to a successor which has a single predecessor
1713   // so that we can directly sink COPY instructions to the successor without
1714   // adding any new block or branch instruction.
1715   for (MachineBasicBlock *SI : CurBB.successors())
1716     if (!SI->livein_empty() && SI->pred_size() == 1)
1717       SinkableBBs.insert(SI);
1718 
1719   if (SinkableBBs.empty())
1720     return false;
1721 
1722   bool Changed = false;
1723 
1724   // Track which registers have been modified and used between the end of the
1725   // block and the current instruction.
1726   ModifiedRegUnits.clear();
1727   UsedRegUnits.clear();
1728   SeenDbgInstrs.clear();
1729 
1730   for (MachineInstr &MI : llvm::make_early_inc_range(llvm::reverse(CurBB))) {
1731     // Track the operand index for use in Copy.
1732     SmallVector<unsigned, 2> UsedOpsInCopy;
1733     // Track the register number defed in Copy.
1734     SmallVector<unsigned, 2> DefedRegsInCopy;
1735 
1736     // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1737     // for DBG_VALUEs later, record them when they're encountered.
1738     if (MI.isDebugValue()) {
1739       SmallDenseMap<MCRegister, SmallVector<unsigned, 2>, 4> MIUnits;
1740       bool IsValid = true;
1741       for (MachineOperand &MO : MI.debug_operands()) {
1742         if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
1743           // Bail if we can already tell the sink would be rejected, rather
1744           // than needlessly accumulating lots of DBG_VALUEs.
1745           if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
1746                                     ModifiedRegUnits, UsedRegUnits)) {
1747             IsValid = false;
1748             break;
1749           }
1750 
1751           // Record debug use of each reg unit.
1752           SmallSet<MCRegister, 4> RegUnits = getRegUnits(MO.getReg(), TRI);
1753           for (MCRegister Reg : RegUnits)
1754             MIUnits[Reg].push_back(MO.getReg());
1755         }
1756       }
1757       if (IsValid) {
1758         for (auto RegOps : MIUnits)
1759           SeenDbgInstrs[RegOps.first].push_back({&MI, RegOps.second});
1760       }
1761       continue;
1762     }
1763 
1764     if (MI.isDebugOrPseudoInstr())
1765       continue;
1766 
1767     // Do not move any instruction across function call.
1768     if (MI.isCall())
1769       return false;
1770 
1771     if (!MI.isCopy() || !MI.getOperand(0).isRenamable()) {
1772       LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1773                                         TRI);
1774       continue;
1775     }
1776 
1777     // Don't sink the COPY if it would violate a register dependency.
1778     if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
1779                               ModifiedRegUnits, UsedRegUnits)) {
1780       LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1781                                         TRI);
1782       continue;
1783     }
1784     assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1785            "Unexpect SrcReg or DefReg");
1786     MachineBasicBlock *SuccBB =
1787         getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1788     // Don't sink if we cannot find a single sinkable successor in which Reg
1789     // is live-in.
1790     if (!SuccBB) {
1791       LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1792                                         TRI);
1793       continue;
1794     }
1795     assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1796            "Unexpected predecessor");
1797 
1798     // Collect DBG_VALUEs that must sink with this copy. We've previously
1799     // recorded which reg units that DBG_VALUEs read, if this instruction
1800     // writes any of those units then the corresponding DBG_VALUEs must sink.
1801     MapVector<MachineInstr *, MIRegs::second_type> DbgValsToSinkMap;
1802     for (auto &MO : MI.operands()) {
1803       if (!MO.isReg() || !MO.isDef())
1804         continue;
1805 
1806       SmallSet<MCRegister, 4> Units = getRegUnits(MO.getReg(), TRI);
1807       for (MCRegister Reg : Units) {
1808         for (auto MIRegs : SeenDbgInstrs.lookup(Reg)) {
1809           auto &Regs = DbgValsToSinkMap[MIRegs.first];
1810           for (unsigned Reg : MIRegs.second)
1811             Regs.push_back(Reg);
1812         }
1813       }
1814     }
1815     SmallVector<MIRegs, 4> DbgValsToSink(DbgValsToSinkMap.begin(),
1816                                          DbgValsToSinkMap.end());
1817 
1818     // Clear the kill flag if SrcReg is killed between MI and the end of the
1819     // block.
1820     clearKillFlags(&MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1821     MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1822     performSink(MI, *SuccBB, InsertPos, DbgValsToSink);
1823     updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1824 
1825     Changed = true;
1826     ++NumPostRACopySink;
1827   }
1828   return Changed;
1829 }
1830 
1831 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1832   if (skipFunction(MF.getFunction()))
1833     return false;
1834 
1835   bool Changed = false;
1836   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1837   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1838 
1839   ModifiedRegUnits.init(*TRI);
1840   UsedRegUnits.init(*TRI);
1841   for (auto &BB : MF)
1842     Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1843 
1844   return Changed;
1845 }
1846