]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/CodeGen/MachineSink.cpp
MFV r329710: 8966 Source file zfs_acl.c, function zfs_aclset_common contains a use...
[FreeBSD/FreeBSD.git] / contrib / llvm / lib / CodeGen / MachineSink.cpp
1 //===- MachineSink.cpp - Sinking for machine instructions -----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass moves instructions into successor blocks when possible, so that
11 // they aren't executed on paths where their results aren't needed.
12 //
13 // This pass is not intended to be a replacement or a complete alternative
14 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
15 // constructs that are not exposed before lowering and instruction selection.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/SparseBitVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
28 #include "llvm/CodeGen/MachineDominators.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineOperand.h"
34 #include "llvm/CodeGen/MachinePostDominators.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/TargetInstrInfo.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/IR/BasicBlock.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/IR/DebugInfoMetadata.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/BranchProbability.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include <algorithm>
48 #include <cassert>
49 #include <cstdint>
50 #include <map>
51 #include <utility>
52 #include <vector>
53
54 using namespace llvm;
55
56 #define DEBUG_TYPE "machine-sink"
57
58 static cl::opt<bool>
59 SplitEdges("machine-sink-split",
60            cl::desc("Split critical edges during machine sinking"),
61            cl::init(true), cl::Hidden);
62
63 static cl::opt<bool>
64 UseBlockFreqInfo("machine-sink-bfi",
65            cl::desc("Use block frequency info to find successors to sink"),
66            cl::init(true), cl::Hidden);
67
68 static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
69     "machine-sink-split-probability-threshold",
70     cl::desc(
71         "Percentage threshold for splitting single-instruction critical edge. "
72         "If the branch threshold is higher than this threshold, we allow "
73         "speculative execution of up to 1 instruction to avoid branching to "
74         "splitted critical edge"),
75     cl::init(40), cl::Hidden);
76
77 STATISTIC(NumSunk,      "Number of machine instructions sunk");
78 STATISTIC(NumSplit,     "Number of critical edges split");
79 STATISTIC(NumCoalesces, "Number of copies coalesced");
80
81 namespace {
82
83   class MachineSinking : public MachineFunctionPass {
84     const TargetInstrInfo *TII;
85     const TargetRegisterInfo *TRI;
86     MachineRegisterInfo  *MRI;     // Machine register information
87     MachineDominatorTree *DT;      // Machine dominator tree
88     MachinePostDominatorTree *PDT; // Machine post dominator tree
89     MachineLoopInfo *LI;
90     const MachineBlockFrequencyInfo *MBFI;
91     const MachineBranchProbabilityInfo *MBPI;
92     AliasAnalysis *AA;
93
94     // Remember which edges have been considered for breaking.
95     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
96     CEBCandidates;
97     // Remember which edges we are about to split.
98     // This is different from CEBCandidates since those edges
99     // will be split.
100     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
101
102     SparseBitVector<> RegsToClearKillFlags;
103
104     using AllSuccsCache =
105         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
106
107   public:
108     static char ID; // Pass identification
109
110     MachineSinking() : MachineFunctionPass(ID) {
111       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
112     }
113
114     bool runOnMachineFunction(MachineFunction &MF) override;
115
116     void getAnalysisUsage(AnalysisUsage &AU) const override {
117       AU.setPreservesCFG();
118       MachineFunctionPass::getAnalysisUsage(AU);
119       AU.addRequired<AAResultsWrapperPass>();
120       AU.addRequired<MachineDominatorTree>();
121       AU.addRequired<MachinePostDominatorTree>();
122       AU.addRequired<MachineLoopInfo>();
123       AU.addRequired<MachineBranchProbabilityInfo>();
124       AU.addPreserved<MachineDominatorTree>();
125       AU.addPreserved<MachinePostDominatorTree>();
126       AU.addPreserved<MachineLoopInfo>();
127       if (UseBlockFreqInfo)
128         AU.addRequired<MachineBlockFrequencyInfo>();
129     }
130
131     void releaseMemory() override {
132       CEBCandidates.clear();
133     }
134
135   private:
136     bool ProcessBlock(MachineBasicBlock &MBB);
137     bool isWorthBreakingCriticalEdge(MachineInstr &MI,
138                                      MachineBasicBlock *From,
139                                      MachineBasicBlock *To);
140
141     /// \brief Postpone the splitting of the given critical
142     /// edge (\p From, \p To).
143     ///
144     /// We do not split the edges on the fly. Indeed, this invalidates
145     /// the dominance information and thus triggers a lot of updates
146     /// of that information underneath.
147     /// Instead, we postpone all the splits after each iteration of
148     /// the main loop. That way, the information is at least valid
149     /// for the lifetime of an iteration.
150     ///
151     /// \return True if the edge is marked as toSplit, false otherwise.
152     /// False can be returned if, for instance, this is not profitable.
153     bool PostponeSplitCriticalEdge(MachineInstr &MI,
154                                    MachineBasicBlock *From,
155                                    MachineBasicBlock *To,
156                                    bool BreakPHIEdge);
157     bool SinkInstruction(MachineInstr &MI, bool &SawStore,
158
159                          AllSuccsCache &AllSuccessors);
160     bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
161                                  MachineBasicBlock *DefMBB,
162                                  bool &BreakPHIEdge, bool &LocalUse) const;
163     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
164                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
165     bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
166                               MachineBasicBlock *MBB,
167                               MachineBasicBlock *SuccToSinkTo,
168                               AllSuccsCache &AllSuccessors);
169
170     bool PerformTrivialForwardCoalescing(MachineInstr &MI,
171                                          MachineBasicBlock *MBB);
172
173     SmallVector<MachineBasicBlock *, 4> &
174     GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
175                            AllSuccsCache &AllSuccessors) const;
176   };
177
178 } // end anonymous namespace
179
180 char MachineSinking::ID = 0;
181
182 char &llvm::MachineSinkingID = MachineSinking::ID;
183
184 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
185                       "Machine code sinking", false, false)
186 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
187 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
188 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
189 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
190 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
191                     "Machine code sinking", false, false)
192
193 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
194                                                      MachineBasicBlock *MBB) {
195   if (!MI.isCopy())
196     return false;
197
198   unsigned SrcReg = MI.getOperand(1).getReg();
199   unsigned DstReg = MI.getOperand(0).getReg();
200   if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
201       !TargetRegisterInfo::isVirtualRegister(DstReg) ||
202       !MRI->hasOneNonDBGUse(SrcReg))
203     return false;
204
205   const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
206   const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
207   if (SRC != DRC)
208     return false;
209
210   MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
211   if (DefMI->isCopyLike())
212     return false;
213   DEBUG(dbgs() << "Coalescing: " << *DefMI);
214   DEBUG(dbgs() << "*** to: " << MI);
215   MRI->replaceRegWith(DstReg, SrcReg);
216   MI.eraseFromParent();
217
218   // Conservatively, clear any kill flags, since it's possible that they are no
219   // longer correct.
220   MRI->clearKillFlags(SrcReg);
221
222   ++NumCoalesces;
223   return true;
224 }
225
226 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
227 /// occur in blocks dominated by the specified block. If any use is in the
228 /// definition block, then return false since it is never legal to move def
229 /// after uses.
230 bool
231 MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
232                                         MachineBasicBlock *MBB,
233                                         MachineBasicBlock *DefMBB,
234                                         bool &BreakPHIEdge,
235                                         bool &LocalUse) const {
236   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
237          "Only makes sense for vregs");
238
239   // Ignore debug uses because debug info doesn't affect the code.
240   if (MRI->use_nodbg_empty(Reg))
241     return true;
242
243   // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
244   // into and they are all PHI nodes. In this case, machine-sink must break
245   // the critical edge first. e.g.
246   //
247   // %bb.1: derived from LLVM BB %bb4.preheader
248   //   Predecessors according to CFG: %bb.0
249   //     ...
250   //     %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
251   //     ...
252   //     JE_4 <%bb.37>, implicit %eflags
253   //   Successors according to CFG: %bb.37 %bb.2
254   //
255   // %bb.2: derived from LLVM BB %bb.nph
256   //   Predecessors according to CFG: %bb.0 %bb.1
257   //     %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
258   BreakPHIEdge = true;
259   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
260     MachineInstr *UseInst = MO.getParent();
261     unsigned OpNo = &MO - &UseInst->getOperand(0);
262     MachineBasicBlock *UseBlock = UseInst->getParent();
263     if (!(UseBlock == MBB && UseInst->isPHI() &&
264           UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
265       BreakPHIEdge = false;
266       break;
267     }
268   }
269   if (BreakPHIEdge)
270     return true;
271
272   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
273     // Determine the block of the use.
274     MachineInstr *UseInst = MO.getParent();
275     unsigned OpNo = &MO - &UseInst->getOperand(0);
276     MachineBasicBlock *UseBlock = UseInst->getParent();
277     if (UseInst->isPHI()) {
278       // PHI nodes use the operand in the predecessor block, not the block with
279       // the PHI.
280       UseBlock = UseInst->getOperand(OpNo+1).getMBB();
281     } else if (UseBlock == DefMBB) {
282       LocalUse = true;
283       return false;
284     }
285
286     // Check that it dominates.
287     if (!DT->dominates(MBB, UseBlock))
288       return false;
289   }
290
291   return true;
292 }
293
294 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
295   if (skipFunction(MF.getFunction()))
296     return false;
297
298   DEBUG(dbgs() << "******** Machine Sinking ********\n");
299
300   TII = MF.getSubtarget().getInstrInfo();
301   TRI = MF.getSubtarget().getRegisterInfo();
302   MRI = &MF.getRegInfo();
303   DT = &getAnalysis<MachineDominatorTree>();
304   PDT = &getAnalysis<MachinePostDominatorTree>();
305   LI = &getAnalysis<MachineLoopInfo>();
306   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
307   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
308   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
309
310   bool EverMadeChange = false;
311
312   while (true) {
313     bool MadeChange = false;
314
315     // Process all basic blocks.
316     CEBCandidates.clear();
317     ToSplit.clear();
318     for (auto &MBB: MF)
319       MadeChange |= ProcessBlock(MBB);
320
321     // If we have anything we marked as toSplit, split it now.
322     for (auto &Pair : ToSplit) {
323       auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
324       if (NewSucc != nullptr) {
325         DEBUG(dbgs() << " *** Splitting critical edge: "
326                      << printMBBReference(*Pair.first) << " -- "
327                      << printMBBReference(*NewSucc) << " -- "
328                      << printMBBReference(*Pair.second) << '\n');
329         MadeChange = true;
330         ++NumSplit;
331       } else
332         DEBUG(dbgs() << " *** Not legal to break critical edge\n");
333     }
334     // If this iteration over the code changed anything, keep iterating.
335     if (!MadeChange) break;
336     EverMadeChange = true;
337   }
338
339   // Now clear any kill flags for recorded registers.
340   for (auto I : RegsToClearKillFlags)
341     MRI->clearKillFlags(I);
342   RegsToClearKillFlags.clear();
343
344   return EverMadeChange;
345 }
346
347 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
348   // Can't sink anything out of a block that has less than two successors.
349   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
350
351   // Don't bother sinking code out of unreachable blocks. In addition to being
352   // unprofitable, it can also lead to infinite looping, because in an
353   // unreachable loop there may be nowhere to stop.
354   if (!DT->isReachableFromEntry(&MBB)) return false;
355
356   bool MadeChange = false;
357
358   // Cache all successors, sorted by frequency info and loop depth.
359   AllSuccsCache AllSuccessors;
360
361   // Walk the basic block bottom-up.  Remember if we saw a store.
362   MachineBasicBlock::iterator I = MBB.end();
363   --I;
364   bool ProcessedBegin, SawStore = false;
365   do {
366     MachineInstr &MI = *I;  // The instruction to sink.
367
368     // Predecrement I (if it's not begin) so that it isn't invalidated by
369     // sinking.
370     ProcessedBegin = I == MBB.begin();
371     if (!ProcessedBegin)
372       --I;
373
374     if (MI.isDebugValue())
375       continue;
376
377     bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
378     if (Joined) {
379       MadeChange = true;
380       continue;
381     }
382
383     if (SinkInstruction(MI, SawStore, AllSuccessors)) {
384       ++NumSunk;
385       MadeChange = true;
386     }
387
388     // If we just processed the first instruction in the block, we're done.
389   } while (!ProcessedBegin);
390
391   return MadeChange;
392 }
393
394 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
395                                                  MachineBasicBlock *From,
396                                                  MachineBasicBlock *To) {
397   // FIXME: Need much better heuristics.
398
399   // If the pass has already considered breaking this edge (during this pass
400   // through the function), then let's go ahead and break it. This means
401   // sinking multiple "cheap" instructions into the same block.
402   if (!CEBCandidates.insert(std::make_pair(From, To)).second)
403     return true;
404
405   if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
406     return true;
407
408   if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
409       BranchProbability(SplitEdgeProbabilityThreshold, 100))
410     return true;
411
412   // MI is cheap, we probably don't want to break the critical edge for it.
413   // However, if this would allow some definitions of its source operands
414   // to be sunk then it's probably worth it.
415   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
416     const MachineOperand &MO = MI.getOperand(i);
417     if (!MO.isReg() || !MO.isUse())
418       continue;
419     unsigned Reg = MO.getReg();
420     if (Reg == 0)
421       continue;
422
423     // We don't move live definitions of physical registers,
424     // so sinking their uses won't enable any opportunities.
425     if (TargetRegisterInfo::isPhysicalRegister(Reg))
426       continue;
427
428     // If this instruction is the only user of a virtual register,
429     // check if breaking the edge will enable sinking
430     // both this instruction and the defining instruction.
431     if (MRI->hasOneNonDBGUse(Reg)) {
432       // If the definition resides in same MBB,
433       // claim it's likely we can sink these together.
434       // If definition resides elsewhere, we aren't
435       // blocking it from being sunk so don't break the edge.
436       MachineInstr *DefMI = MRI->getVRegDef(Reg);
437       if (DefMI->getParent() == MI.getParent())
438         return true;
439     }
440   }
441
442   return false;
443 }
444
445 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
446                                                MachineBasicBlock *FromBB,
447                                                MachineBasicBlock *ToBB,
448                                                bool BreakPHIEdge) {
449   if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
450     return false;
451
452   // Avoid breaking back edge. From == To means backedge for single BB loop.
453   if (!SplitEdges || FromBB == ToBB)
454     return false;
455
456   // Check for backedges of more "complex" loops.
457   if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
458       LI->isLoopHeader(ToBB))
459     return false;
460
461   // It's not always legal to break critical edges and sink the computation
462   // to the edge.
463   //
464   // %bb.1:
465   // v1024
466   // Beq %bb.3
467   // <fallthrough>
468   // %bb.2:
469   // ... no uses of v1024
470   // <fallthrough>
471   // %bb.3:
472   // ...
473   //       = v1024
474   //
475   // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
476   //
477   // %bb.1:
478   // ...
479   // Bne %bb.2
480   // %bb.4:
481   // v1024 =
482   // B %bb.3
483   // %bb.2:
484   // ... no uses of v1024
485   // <fallthrough>
486   // %bb.3:
487   // ...
488   //       = v1024
489   //
490   // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
491   // flow. We need to ensure the new basic block where the computation is
492   // sunk to dominates all the uses.
493   // It's only legal to break critical edge and sink the computation to the
494   // new block if all the predecessors of "To", except for "From", are
495   // not dominated by "From". Given SSA property, this means these
496   // predecessors are dominated by "To".
497   //
498   // There is no need to do this check if all the uses are PHI nodes. PHI
499   // sources are only defined on the specific predecessor edges.
500   if (!BreakPHIEdge) {
501     for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
502            E = ToBB->pred_end(); PI != E; ++PI) {
503       if (*PI == FromBB)
504         continue;
505       if (!DT->dominates(ToBB, *PI))
506         return false;
507     }
508   }
509
510   ToSplit.insert(std::make_pair(FromBB, ToBB));
511   
512   return true;
513 }
514
515 /// collectDebgValues - Scan instructions following MI and collect any
516 /// matching DBG_VALUEs.
517 static void collectDebugValues(MachineInstr &MI,
518                                SmallVectorImpl<MachineInstr *> &DbgValues) {
519   DbgValues.clear();
520   if (!MI.getOperand(0).isReg())
521     return;
522
523   MachineBasicBlock::iterator DI = MI; ++DI;
524   for (MachineBasicBlock::iterator DE = MI.getParent()->end();
525        DI != DE; ++DI) {
526     if (!DI->isDebugValue())
527       return;
528     if (DI->getOperand(0).isReg() &&
529         DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
530       DbgValues.push_back(&*DI);
531   }
532 }
533
534 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
535 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
536                                           MachineBasicBlock *MBB,
537                                           MachineBasicBlock *SuccToSinkTo,
538                                           AllSuccsCache &AllSuccessors) {
539   assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
540
541   if (MBB == SuccToSinkTo)
542     return false;
543
544   // It is profitable if SuccToSinkTo does not post dominate current block.
545   if (!PDT->dominates(SuccToSinkTo, MBB))
546     return true;
547
548   // It is profitable to sink an instruction from a deeper loop to a shallower
549   // loop, even if the latter post-dominates the former (PR21115).
550   if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
551     return true;
552
553   // Check if only use in post dominated block is PHI instruction.
554   bool NonPHIUse = false;
555   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
556     MachineBasicBlock *UseBlock = UseInst.getParent();
557     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
558       NonPHIUse = true;
559   }
560   if (!NonPHIUse)
561     return true;
562
563   // If SuccToSinkTo post dominates then also it may be profitable if MI
564   // can further profitably sinked into another block in next round.
565   bool BreakPHIEdge = false;
566   // FIXME - If finding successor is compile time expensive then cache results.
567   if (MachineBasicBlock *MBB2 =
568           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
569     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
570
571   // If SuccToSinkTo is final destination and it is a post dominator of current
572   // block then it is not profitable to sink MI into SuccToSinkTo block.
573   return false;
574 }
575
576 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
577 /// computing it if it was not already cached.
578 SmallVector<MachineBasicBlock *, 4> &
579 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
580                                        AllSuccsCache &AllSuccessors) const {
581   // Do we have the sorted successors in cache ?
582   auto Succs = AllSuccessors.find(MBB);
583   if (Succs != AllSuccessors.end())
584     return Succs->second;
585
586   SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
587                                                MBB->succ_end());
588
589   // Handle cases where sinking can happen but where the sink point isn't a
590   // successor. For example:
591   //
592   //   x = computation
593   //   if () {} else {}
594   //   use x
595   //
596   const std::vector<MachineDomTreeNode *> &Children =
597     DT->getNode(MBB)->getChildren();
598   for (const auto &DTChild : Children)
599     // DomTree children of MBB that have MBB as immediate dominator are added.
600     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
601         // Skip MBBs already added to the AllSuccs vector above.
602         !MBB->isSuccessor(DTChild->getBlock()))
603       AllSuccs.push_back(DTChild->getBlock());
604
605   // Sort Successors according to their loop depth or block frequency info.
606   std::stable_sort(
607       AllSuccs.begin(), AllSuccs.end(),
608       [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
609         uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
610         uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
611         bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
612         return HasBlockFreq ? LHSFreq < RHSFreq
613                             : LI->getLoopDepth(L) < LI->getLoopDepth(R);
614       });
615
616   auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
617
618   return it.first->second;
619 }
620
621 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
622 MachineBasicBlock *
623 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
624                                  bool &BreakPHIEdge,
625                                  AllSuccsCache &AllSuccessors) {
626   assert (MBB && "Invalid MachineBasicBlock!");
627
628   // Loop over all the operands of the specified instruction.  If there is
629   // anything we can't handle, bail out.
630
631   // SuccToSinkTo - This is the successor to sink this instruction to, once we
632   // decide.
633   MachineBasicBlock *SuccToSinkTo = nullptr;
634   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
635     const MachineOperand &MO = MI.getOperand(i);
636     if (!MO.isReg()) continue;  // Ignore non-register operands.
637
638     unsigned Reg = MO.getReg();
639     if (Reg == 0) continue;
640
641     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
642       if (MO.isUse()) {
643         // If the physreg has no defs anywhere, it's just an ambient register
644         // and we can freely move its uses. Alternatively, if it's allocatable,
645         // it could get allocated to something with a def during allocation.
646         if (!MRI->isConstantPhysReg(Reg))
647           return nullptr;
648       } else if (!MO.isDead()) {
649         // A def that isn't dead. We can't move it.
650         return nullptr;
651       }
652     } else {
653       // Virtual register uses are always safe to sink.
654       if (MO.isUse()) continue;
655
656       // If it's not safe to move defs of the register class, then abort.
657       if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
658         return nullptr;
659
660       // Virtual register defs can only be sunk if all their uses are in blocks
661       // dominated by one of the successors.
662       if (SuccToSinkTo) {
663         // If a previous operand picked a block to sink to, then this operand
664         // must be sinkable to the same block.
665         bool LocalUse = false;
666         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
667                                      BreakPHIEdge, LocalUse))
668           return nullptr;
669
670         continue;
671       }
672
673       // Otherwise, we should look at all the successors and decide which one
674       // we should sink to. If we have reliable block frequency information
675       // (frequency != 0) available, give successors with smaller frequencies
676       // higher priority, otherwise prioritize smaller loop depths.
677       for (MachineBasicBlock *SuccBlock :
678            GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
679         bool LocalUse = false;
680         if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
681                                     BreakPHIEdge, LocalUse)) {
682           SuccToSinkTo = SuccBlock;
683           break;
684         }
685         if (LocalUse)
686           // Def is used locally, it's never safe to move this def.
687           return nullptr;
688       }
689
690       // If we couldn't find a block to sink to, ignore this instruction.
691       if (!SuccToSinkTo)
692         return nullptr;
693       if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
694         return nullptr;
695     }
696   }
697
698   // It is not possible to sink an instruction into its own block.  This can
699   // happen with loops.
700   if (MBB == SuccToSinkTo)
701     return nullptr;
702
703   // It's not safe to sink instructions to EH landing pad. Control flow into
704   // landing pad is implicitly defined.
705   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
706     return nullptr;
707
708   return SuccToSinkTo;
709 }
710
711 /// \brief Return true if MI is likely to be usable as a memory operation by the
712 /// implicit null check optimization.
713 ///
714 /// This is a "best effort" heuristic, and should not be relied upon for
715 /// correctness.  This returning true does not guarantee that the implicit null
716 /// check optimization is legal over MI, and this returning false does not
717 /// guarantee MI cannot possibly be used to do a null check.
718 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
719                                              const TargetInstrInfo *TII,
720                                              const TargetRegisterInfo *TRI) {
721   using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
722
723   auto *MBB = MI.getParent();
724   if (MBB->pred_size() != 1)
725     return false;
726
727   auto *PredMBB = *MBB->pred_begin();
728   auto *PredBB = PredMBB->getBasicBlock();
729
730   // Frontends that don't use implicit null checks have no reason to emit
731   // branches with make.implicit metadata, and this function should always
732   // return false for them.
733   if (!PredBB ||
734       !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
735     return false;
736
737   unsigned BaseReg;
738   int64_t Offset;
739   if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
740     return false;
741
742   if (!(MI.mayLoad() && !MI.isPredicable()))
743     return false;
744
745   MachineBranchPredicate MBP;
746   if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
747     return false;
748
749   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
750          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
751           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
752          MBP.LHS.getReg() == BaseReg;
753 }
754
755 /// SinkInstruction - Determine whether it is safe to sink the specified machine
756 /// instruction out of its current block into a successor.
757 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
758                                      AllSuccsCache &AllSuccessors) {
759   // Don't sink instructions that the target prefers not to sink.
760   if (!TII->shouldSink(MI))
761     return false;
762
763   // Check if it's safe to move the instruction.
764   if (!MI.isSafeToMove(AA, SawStore))
765     return false;
766
767   // Convergent operations may not be made control-dependent on additional
768   // values.
769   if (MI.isConvergent())
770     return false;
771
772   // Don't break implicit null checks.  This is a performance heuristic, and not
773   // required for correctness.
774   if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
775     return false;
776
777   // FIXME: This should include support for sinking instructions within the
778   // block they are currently in to shorten the live ranges.  We often get
779   // instructions sunk into the top of a large block, but it would be better to
780   // also sink them down before their first use in the block.  This xform has to
781   // be careful not to *increase* register pressure though, e.g. sinking
782   // "x = y + z" down if it kills y and z would increase the live ranges of y
783   // and z and only shrink the live range of x.
784
785   bool BreakPHIEdge = false;
786   MachineBasicBlock *ParentBlock = MI.getParent();
787   MachineBasicBlock *SuccToSinkTo =
788       FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
789
790   // If there are no outputs, it must have side-effects.
791   if (!SuccToSinkTo)
792     return false;
793
794   // If the instruction to move defines a dead physical register which is live
795   // when leaving the basic block, don't move it because it could turn into a
796   // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
797   for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
798     const MachineOperand &MO = MI.getOperand(I);
799     if (!MO.isReg()) continue;
800     unsigned Reg = MO.getReg();
801     if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
802     if (SuccToSinkTo->isLiveIn(Reg))
803       return false;
804   }
805
806   DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
807
808   // If the block has multiple predecessors, this is a critical edge.
809   // Decide if we can sink along it or need to break the edge.
810   if (SuccToSinkTo->pred_size() > 1) {
811     // We cannot sink a load across a critical edge - there may be stores in
812     // other code paths.
813     bool TryBreak = false;
814     bool store = true;
815     if (!MI.isSafeToMove(AA, store)) {
816       DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
817       TryBreak = true;
818     }
819
820     // We don't want to sink across a critical edge if we don't dominate the
821     // successor. We could be introducing calculations to new code paths.
822     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
823       DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
824       TryBreak = true;
825     }
826
827     // Don't sink instructions into a loop.
828     if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
829       DEBUG(dbgs() << " *** NOTE: Loop header found\n");
830       TryBreak = true;
831     }
832
833     // Otherwise we are OK with sinking along a critical edge.
834     if (!TryBreak)
835       DEBUG(dbgs() << "Sinking along critical edge.\n");
836     else {
837       // Mark this edge as to be split.
838       // If the edge can actually be split, the next iteration of the main loop
839       // will sink MI in the newly created block.
840       bool Status =
841         PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
842       if (!Status)
843         DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
844               "break critical edge\n");
845       // The instruction will not be sunk this time.
846       return false;
847     }
848   }
849
850   if (BreakPHIEdge) {
851     // BreakPHIEdge is true if all the uses are in the successor MBB being
852     // sunken into and they are all PHI nodes. In this case, machine-sink must
853     // break the critical edge first.
854     bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
855                                             SuccToSinkTo, BreakPHIEdge);
856     if (!Status)
857       DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
858             "break critical edge\n");
859     // The instruction will not be sunk this time.
860     return false;
861   }
862
863   // Determine where to insert into. Skip phi nodes.
864   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
865   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
866     ++InsertPos;
867
868   // collect matching debug values.
869   SmallVector<MachineInstr *, 2> DbgValuesToSink;
870   collectDebugValues(MI, DbgValuesToSink);
871
872   // Merge or erase debug location to ensure consistent stepping in profilers
873   // and debuggers.
874   if (!SuccToSinkTo->empty() && InsertPos != SuccToSinkTo->end())
875     MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
876                                                  InsertPos->getDebugLoc()));
877   else
878     MI.setDebugLoc(DebugLoc());
879
880
881   // Move the instruction.
882   SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
883                        ++MachineBasicBlock::iterator(MI));
884
885   // Move previously adjacent debug value instructions to the insert position.
886   for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
887          DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
888     MachineInstr *DbgMI = *DBI;
889     SuccToSinkTo->splice(InsertPos, ParentBlock,  DbgMI,
890                          ++MachineBasicBlock::iterator(DbgMI));
891   }
892
893   // Conservatively, clear any kill flags, since it's possible that they are no
894   // longer correct.
895   // Note that we have to clear the kill flags for any register this instruction
896   // uses as we may sink over another instruction which currently kills the
897   // used registers.
898   for (MachineOperand &MO : MI.operands()) {
899     if (MO.isReg() && MO.isUse())
900       RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
901   }
902
903   return true;
904 }