xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
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 #include "llvm/Analysis/MustExecute.h"
10 #include "llvm/ADT/PostOrderIterator.h"
11 #include "llvm/ADT/StringExtras.h"
12 #include "llvm/Analysis/CFG.h"
13 #include "llvm/Analysis/InstructionSimplify.h"
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/Analysis/Passes.h"
16 #include "llvm/Analysis/PostDominators.h"
17 #include "llvm/Analysis/ValueTracking.h"
18 #include "llvm/IR/AssemblyAnnotationWriter.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/InstIterator.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Support/FormattedStream.h"
25 #include "llvm/Support/raw_ostream.h"
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "must-execute"
30 
31 const DenseMap<BasicBlock *, ColorVector> &
32 LoopSafetyInfo::getBlockColors() const {
33   return BlockColors;
34 }
35 
36 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
37   ColorVector &ColorsForNewBlock = BlockColors[New];
38   ColorVector &ColorsForOldBlock = BlockColors[Old];
39   ColorsForNewBlock = ColorsForOldBlock;
40 }
41 
42 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
43   (void)BB;
44   return anyBlockMayThrow();
45 }
46 
47 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
48   return MayThrow;
49 }
50 
51 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
52   assert(CurLoop != nullptr && "CurLoop can't be null");
53   BasicBlock *Header = CurLoop->getHeader();
54   // Iterate over header and compute safety info.
55   HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
56   MayThrow = HeaderMayThrow;
57   // Iterate over loop instructions and compute safety info.
58   // Skip header as it has been computed and stored in HeaderMayThrow.
59   // The first block in loopinfo.Blocks is guaranteed to be the header.
60   assert(Header == *CurLoop->getBlocks().begin() &&
61          "First block must be header");
62   for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
63                             BBE = CurLoop->block_end();
64        (BB != BBE) && !MayThrow; ++BB)
65     MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
66 
67   computeBlockColors(CurLoop);
68 }
69 
70 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
71   return ICF.hasICF(BB);
72 }
73 
74 bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
75   return MayThrow;
76 }
77 
78 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
79   assert(CurLoop != nullptr && "CurLoop can't be null");
80   ICF.clear();
81   MW.clear();
82   MayThrow = false;
83   // Figure out the fact that at least one block may throw.
84   for (const auto &BB : CurLoop->blocks())
85     if (ICF.hasICF(&*BB)) {
86       MayThrow = true;
87       break;
88     }
89   computeBlockColors(CurLoop);
90 }
91 
92 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
93                                             const BasicBlock *BB) {
94   ICF.insertInstructionTo(Inst, BB);
95   MW.insertInstructionTo(Inst, BB);
96 }
97 
98 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
99   ICF.removeInstruction(Inst);
100   MW.removeInstruction(Inst);
101 }
102 
103 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
104   // Compute funclet colors if we might sink/hoist in a function with a funclet
105   // personality routine.
106   Function *Fn = CurLoop->getHeader()->getParent();
107   if (Fn->hasPersonalityFn())
108     if (Constant *PersonalityFn = Fn->getPersonalityFn())
109       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
110         BlockColors = colorEHFunclets(*Fn);
111 }
112 
113 /// Return true if we can prove that the given ExitBlock is not reached on the
114 /// first iteration of the given loop.  That is, the backedge of the loop must
115 /// be executed before the ExitBlock is executed in any dynamic execution trace.
116 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
117                                            const DominatorTree *DT,
118                                            const Loop *CurLoop) {
119   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
120   if (!CondExitBlock)
121     // expect unique exits
122     return false;
123   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
124   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
125   if (!BI || !BI->isConditional())
126     return false;
127   // If condition is constant and false leads to ExitBlock then we always
128   // execute the true branch.
129   if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
130     return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
131   auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
132   if (!Cond)
133     return false;
134   // todo: this would be a lot more powerful if we used scev, but all the
135   // plumbing is currently missing to pass a pointer in from the pass
136   // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
137   auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
138   auto *RHS = Cond->getOperand(1);
139   if (!LHS || LHS->getParent() != CurLoop->getHeader())
140     return false;
141   auto DL = ExitBlock->getModule()->getDataLayout();
142   auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
143   auto *SimpleValOrNull = simplifyCmpInst(Cond->getPredicate(),
144                                           IVStart, RHS,
145                                           {DL, /*TLI*/ nullptr,
146                                               DT, /*AC*/ nullptr, BI});
147   auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
148   if (!SimpleCst)
149     return false;
150   if (ExitBlock == BI->getSuccessor(0))
151     return SimpleCst->isZeroValue();
152   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
153   return SimpleCst->isAllOnesValue();
154 }
155 
156 /// Collect all blocks from \p CurLoop which lie on all possible paths from
157 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
158 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
159 static void collectTransitivePredecessors(
160     const Loop *CurLoop, const BasicBlock *BB,
161     SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
162   assert(Predecessors.empty() && "Garbage in predecessors set?");
163   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
164   if (BB == CurLoop->getHeader())
165     return;
166   SmallVector<const BasicBlock *, 4> WorkList;
167   for (const auto *Pred : predecessors(BB)) {
168     Predecessors.insert(Pred);
169     WorkList.push_back(Pred);
170   }
171   while (!WorkList.empty()) {
172     auto *Pred = WorkList.pop_back_val();
173     assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
174     // We are not interested in backedges and we don't want to leave loop.
175     if (Pred == CurLoop->getHeader())
176       continue;
177     // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
178     // blocks of this inner loop, even those that are always executed AFTER the
179     // BB. It may make our analysis more conservative than it could be, see test
180     // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
181     // We can ignore backedge of all loops containing BB to get a sligtly more
182     // optimistic result.
183     for (const auto *PredPred : predecessors(Pred))
184       if (Predecessors.insert(PredPred).second)
185         WorkList.push_back(PredPred);
186   }
187 }
188 
189 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
190                                              const BasicBlock *BB,
191                                              const DominatorTree *DT) const {
192   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
193 
194   // Fast path: header is always reached once the loop is entered.
195   if (BB == CurLoop->getHeader())
196     return true;
197 
198   // Collect all transitive predecessors of BB in the same loop. This set will
199   // be a subset of the blocks within the loop.
200   SmallPtrSet<const BasicBlock *, 4> Predecessors;
201   collectTransitivePredecessors(CurLoop, BB, Predecessors);
202 
203   // Make sure that all successors of, all predecessors of BB which are not
204   // dominated by BB, are either:
205   // 1) BB,
206   // 2) Also predecessors of BB,
207   // 3) Exit blocks which are not taken on 1st iteration.
208   // Memoize blocks we've already checked.
209   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
210   for (const auto *Pred : Predecessors) {
211     // Predecessor block may throw, so it has a side exit.
212     if (blockMayThrow(Pred))
213       return false;
214 
215     // BB dominates Pred, so if Pred runs, BB must run.
216     // This is true when Pred is a loop latch.
217     if (DT->dominates(BB, Pred))
218       continue;
219 
220     for (const auto *Succ : successors(Pred))
221       if (CheckedSuccessors.insert(Succ).second &&
222           Succ != BB && !Predecessors.count(Succ))
223         // By discharging conditions that are not executed on the 1st iteration,
224         // we guarantee that *at least* on the first iteration all paths from
225         // header that *may* execute will lead us to the block of interest. So
226         // that if we had virtually peeled one iteration away, in this peeled
227         // iteration the set of predecessors would contain only paths from
228         // header to BB without any exiting edges that may execute.
229         //
230         // TODO: We only do it for exiting edges currently. We could use the
231         // same function to skip some of the edges within the loop if we know
232         // that they will not be taken on the 1st iteration.
233         //
234         // TODO: If we somehow know the number of iterations in loop, the same
235         // check may be done for any arbitrary N-th iteration as long as N is
236         // not greater than minimum number of iterations in this loop.
237         if (CurLoop->contains(Succ) ||
238             !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
239           return false;
240   }
241 
242   // All predecessors can only lead us to BB.
243   return true;
244 }
245 
246 /// Returns true if the instruction in a loop is guaranteed to execute at least
247 /// once.
248 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
249                                                  const DominatorTree *DT,
250                                                  const Loop *CurLoop) const {
251   // If the instruction is in the header block for the loop (which is very
252   // common), it is always guaranteed to dominate the exit blocks.  Since this
253   // is a common case, and can save some work, check it now.
254   if (Inst.getParent() == CurLoop->getHeader())
255     // If there's a throw in the header block, we can't guarantee we'll reach
256     // Inst unless we can prove that Inst comes before the potential implicit
257     // exit.  At the moment, we use a (cheap) hack for the common case where
258     // the instruction of interest is the first one in the block.
259     return !HeaderMayThrow ||
260            Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
261 
262   // If there is a path from header to exit or latch that doesn't lead to our
263   // instruction's block, return false.
264   return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
265 }
266 
267 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
268                                               const DominatorTree *DT,
269                                               const Loop *CurLoop) const {
270   return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
271          allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
272 }
273 
274 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
275                                                  const Loop *CurLoop) const {
276   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
277 
278   // Fast path: there are no instructions before header.
279   if (BB == CurLoop->getHeader())
280     return true;
281 
282   // Collect all transitive predecessors of BB in the same loop. This set will
283   // be a subset of the blocks within the loop.
284   SmallPtrSet<const BasicBlock *, 4> Predecessors;
285   collectTransitivePredecessors(CurLoop, BB, Predecessors);
286   // Find if there any instruction in either predecessor that could write
287   // to memory.
288   for (const auto *Pred : Predecessors)
289     if (MW.mayWriteToMemory(Pred))
290       return false;
291   return true;
292 }
293 
294 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
295                                                  const Loop *CurLoop) const {
296   auto *BB = I.getParent();
297   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
298   return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
299          doesNotWriteMemoryBefore(BB, CurLoop);
300 }
301 
302 namespace {
303 struct MustExecutePrinter : public FunctionPass {
304 
305   static char ID; // Pass identification, replacement for typeid
306   MustExecutePrinter() : FunctionPass(ID) {
307     initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
308   }
309   void getAnalysisUsage(AnalysisUsage &AU) const override {
310     AU.setPreservesAll();
311     AU.addRequired<DominatorTreeWrapperPass>();
312     AU.addRequired<LoopInfoWrapperPass>();
313   }
314   bool runOnFunction(Function &F) override;
315 };
316 struct MustBeExecutedContextPrinter : public ModulePass {
317   static char ID;
318 
319   MustBeExecutedContextPrinter() : ModulePass(ID) {
320     initializeMustBeExecutedContextPrinterPass(
321         *PassRegistry::getPassRegistry());
322   }
323   void getAnalysisUsage(AnalysisUsage &AU) const override {
324     AU.setPreservesAll();
325   }
326   bool runOnModule(Module &M) override;
327 };
328 }
329 
330 char MustExecutePrinter::ID = 0;
331 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
332                       "Instructions which execute on loop entry", false, true)
333 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
334 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
335 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
336                     "Instructions which execute on loop entry", false, true)
337 
338 FunctionPass *llvm::createMustExecutePrinter() {
339   return new MustExecutePrinter();
340 }
341 
342 char MustBeExecutedContextPrinter::ID = 0;
343 INITIALIZE_PASS_BEGIN(MustBeExecutedContextPrinter,
344                       "print-must-be-executed-contexts",
345                       "print the must-be-executed-context for all instructions",
346                       false, true)
347 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
348 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
349 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
350 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
351                     "print-must-be-executed-contexts",
352                     "print the must-be-executed-context for all instructions",
353                     false, true)
354 
355 ModulePass *llvm::createMustBeExecutedContextPrinter() {
356   return new MustBeExecutedContextPrinter();
357 }
358 
359 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
360   // We provide non-PM analysis here because the old PM doesn't like to query
361   // function passes from a module pass.
362   SmallVector<std::unique_ptr<PostDominatorTree>, 8> PDTs;
363   SmallVector<std::unique_ptr<DominatorTree>, 8> DTs;
364   SmallVector<std::unique_ptr<LoopInfo>, 8> LIs;
365 
366   GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
367     DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
368     LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
369     return LIs.back().get();
370   };
371   GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
372     DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
373     return DTs.back().get();
374   };
375   GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
376     PDTs.push_back(
377         std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
378     return PDTs.back().get();
379   };
380   MustBeExecutedContextExplorer Explorer(
381       /* ExploreInterBlock */ true,
382       /* ExploreCFGForward */ true,
383       /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
384 
385   for (Function &F : M) {
386     for (Instruction &I : instructions(F)) {
387       dbgs() << "-- Explore context of: " << I << "\n";
388       for (const Instruction *CI : Explorer.range(&I))
389         dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
390                << "\n";
391     }
392   }
393 
394   return false;
395 }
396 
397 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
398   // TODO: merge these two routines.  For the moment, we display the best
399   // result obtained by *either* implementation.  This is a bit unfair since no
400   // caller actually gets the full power at the moment.
401   SimpleLoopSafetyInfo LSI;
402   LSI.computeLoopSafetyInfo(L);
403   return LSI.isGuaranteedToExecute(I, DT, L) ||
404     isGuaranteedToExecuteForEveryIteration(&I, L);
405 }
406 
407 namespace {
408 /// An assembly annotator class to print must execute information in
409 /// comments.
410 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
411   DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
412 
413 public:
414   MustExecuteAnnotatedWriter(const Function &F,
415                              DominatorTree &DT, LoopInfo &LI) {
416     for (const auto &I: instructions(F)) {
417       Loop *L = LI.getLoopFor(I.getParent());
418       while (L) {
419         if (isMustExecuteIn(I, L, &DT)) {
420           MustExec[&I].push_back(L);
421         }
422         L = L->getParentLoop();
423       };
424     }
425   }
426   MustExecuteAnnotatedWriter(const Module &M,
427                              DominatorTree &DT, LoopInfo &LI) {
428     for (const auto &F : M)
429     for (const auto &I: instructions(F)) {
430       Loop *L = LI.getLoopFor(I.getParent());
431       while (L) {
432         if (isMustExecuteIn(I, L, &DT)) {
433           MustExec[&I].push_back(L);
434         }
435         L = L->getParentLoop();
436       };
437     }
438   }
439 
440 
441   void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
442     if (!MustExec.count(&V))
443       return;
444 
445     const auto &Loops = MustExec.lookup(&V);
446     const auto NumLoops = Loops.size();
447     if (NumLoops > 1)
448       OS << " ; (mustexec in " << NumLoops << " loops: ";
449     else
450       OS << " ; (mustexec in: ";
451 
452     ListSeparator LS;
453     for (const Loop *L : Loops)
454       OS << LS << L->getHeader()->getName();
455     OS << ")";
456   }
457 };
458 } // namespace
459 
460 bool MustExecutePrinter::runOnFunction(Function &F) {
461   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
462   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
463 
464   MustExecuteAnnotatedWriter Writer(F, DT, LI);
465   F.print(dbgs(), &Writer);
466 
467   return false;
468 }
469 
470 /// Return true if \p L might be an endless loop.
471 static bool maybeEndlessLoop(const Loop &L) {
472   if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
473     return false;
474   // TODO: Actually try to prove it is not.
475   // TODO: If maybeEndlessLoop is going to be expensive, cache it.
476   return true;
477 }
478 
479 bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
480   if (!LI)
481     return false;
482   using RPOTraversal = ReversePostOrderTraversal<const Function *>;
483   RPOTraversal FuncRPOT(&F);
484   return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
485                                 const LoopInfo>(FuncRPOT, *LI);
486 }
487 
488 /// Lookup \p Key in \p Map and return the result, potentially after
489 /// initializing the optional through \p Fn(\p args).
490 template <typename K, typename V, typename FnTy, typename... ArgsTy>
491 static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
492                                    FnTy &&Fn, ArgsTy&&... args) {
493   Optional<V> &OptVal = Map[Key];
494   if (!OptVal)
495     OptVal = Fn(std::forward<ArgsTy>(args)...);
496   return OptVal.value();
497 }
498 
499 const BasicBlock *
500 MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
501   const LoopInfo *LI = LIGetter(*InitBB->getParent());
502   const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
503 
504   LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
505                     << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
506 
507   const Function &F = *InitBB->getParent();
508   const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
509   const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
510   bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
511                                (L && !maybeEndlessLoop(*L))) &&
512                               F.doesNotThrow();
513   LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
514                     << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
515                     << "\n");
516 
517   // Determine the adjacent blocks in the given direction but exclude (self)
518   // loops under certain circumstances.
519   SmallVector<const BasicBlock *, 8> Worklist;
520   for (const BasicBlock *SuccBB : successors(InitBB)) {
521     bool IsLatch = SuccBB == HeaderBB;
522     // Loop latches are ignored in forward propagation if the loop cannot be
523     // endless and may not throw: control has to go somewhere.
524     if (!WillReturnAndNoThrow || !IsLatch)
525       Worklist.push_back(SuccBB);
526   }
527   LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
528 
529   // If there are no other adjacent blocks, there is no join point.
530   if (Worklist.empty())
531     return nullptr;
532 
533   // If there is one adjacent block, it is the join point.
534   if (Worklist.size() == 1)
535     return Worklist[0];
536 
537   // Try to determine a join block through the help of the post-dominance
538   // tree. If no tree was provided, we perform simple pattern matching for one
539   // block conditionals and one block loops only.
540   const BasicBlock *JoinBB = nullptr;
541   if (PDT)
542     if (const auto *InitNode = PDT->getNode(InitBB))
543       if (const auto *IDomNode = InitNode->getIDom())
544         JoinBB = IDomNode->getBlock();
545 
546   if (!JoinBB && Worklist.size() == 2) {
547     const BasicBlock *Succ0 = Worklist[0];
548     const BasicBlock *Succ1 = Worklist[1];
549     const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
550     const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
551     if (Succ0UniqueSucc == InitBB) {
552       // InitBB -> Succ0 -> InitBB
553       // InitBB -> Succ1  = JoinBB
554       JoinBB = Succ1;
555     } else if (Succ1UniqueSucc == InitBB) {
556       // InitBB -> Succ1 -> InitBB
557       // InitBB -> Succ0  = JoinBB
558       JoinBB = Succ0;
559     } else if (Succ0 == Succ1UniqueSucc) {
560       // InitBB ->          Succ0 = JoinBB
561       // InitBB -> Succ1 -> Succ0 = JoinBB
562       JoinBB = Succ0;
563     } else if (Succ1 == Succ0UniqueSucc) {
564       // InitBB -> Succ0 -> Succ1 = JoinBB
565       // InitBB ->          Succ1 = JoinBB
566       JoinBB = Succ1;
567     } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
568       // InitBB -> Succ0 -> JoinBB
569       // InitBB -> Succ1 -> JoinBB
570       JoinBB = Succ0UniqueSucc;
571     }
572   }
573 
574   if (!JoinBB && L)
575     JoinBB = L->getUniqueExitBlock();
576 
577   if (!JoinBB)
578     return nullptr;
579 
580   LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
581 
582   // In forward direction we check if control will for sure reach JoinBB from
583   // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
584   // are: infinite loops and instructions that do not necessarily transfer
585   // execution to their successor. To check for them we traverse the CFG from
586   // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
587 
588   // If we know the function is "will-return" and "no-throw" there is no need
589   // for futher checks.
590   if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
591 
592     auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
593       return isGuaranteedToTransferExecutionToSuccessor(BB);
594     };
595 
596     SmallPtrSet<const BasicBlock *, 16> Visited;
597     while (!Worklist.empty()) {
598       const BasicBlock *ToBB = Worklist.pop_back_val();
599       if (ToBB == JoinBB)
600         continue;
601 
602       // Make sure all loops in-between are finite.
603       if (!Visited.insert(ToBB).second) {
604         if (!F.hasFnAttribute(Attribute::WillReturn)) {
605           if (!LI)
606             return nullptr;
607 
608           bool MayContainIrreducibleControl = getOrCreateCachedOptional(
609               &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
610           if (MayContainIrreducibleControl)
611             return nullptr;
612 
613           const Loop *L = LI->getLoopFor(ToBB);
614           if (L && maybeEndlessLoop(*L))
615             return nullptr;
616         }
617 
618         continue;
619       }
620 
621       // Make sure the block has no instructions that could stop control
622       // transfer.
623       bool TransfersExecution = getOrCreateCachedOptional(
624           ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
625       if (!TransfersExecution)
626         return nullptr;
627 
628       append_range(Worklist, successors(ToBB));
629     }
630   }
631 
632   LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
633   return JoinBB;
634 }
635 const BasicBlock *
636 MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
637   const LoopInfo *LI = LIGetter(*InitBB->getParent());
638   const DominatorTree *DT = DTGetter(*InitBB->getParent());
639   LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
640                     << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
641 
642   // Try to determine a join block through the help of the dominance tree. If no
643   // tree was provided, we perform simple pattern matching for one block
644   // conditionals only.
645   if (DT)
646     if (const auto *InitNode = DT->getNode(InitBB))
647       if (const auto *IDomNode = InitNode->getIDom())
648         return IDomNode->getBlock();
649 
650   const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
651   const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
652 
653   // Determine the predecessor blocks but ignore backedges.
654   SmallVector<const BasicBlock *, 8> Worklist;
655   for (const BasicBlock *PredBB : predecessors(InitBB)) {
656     bool IsBackedge =
657         (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
658     // Loop backedges are ignored in backwards propagation: control has to come
659     // from somewhere.
660     if (!IsBackedge)
661       Worklist.push_back(PredBB);
662   }
663 
664   // If there are no other predecessor blocks, there is no join point.
665   if (Worklist.empty())
666     return nullptr;
667 
668   // If there is one predecessor block, it is the join point.
669   if (Worklist.size() == 1)
670     return Worklist[0];
671 
672   const BasicBlock *JoinBB = nullptr;
673   if (Worklist.size() == 2) {
674     const BasicBlock *Pred0 = Worklist[0];
675     const BasicBlock *Pred1 = Worklist[1];
676     const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
677     const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
678     if (Pred0 == Pred1UniquePred) {
679       // InitBB <-          Pred0 = JoinBB
680       // InitBB <- Pred1 <- Pred0 = JoinBB
681       JoinBB = Pred0;
682     } else if (Pred1 == Pred0UniquePred) {
683       // InitBB <- Pred0 <- Pred1 = JoinBB
684       // InitBB <-          Pred1 = JoinBB
685       JoinBB = Pred1;
686     } else if (Pred0UniquePred == Pred1UniquePred) {
687       // InitBB <- Pred0 <- JoinBB
688       // InitBB <- Pred1 <- JoinBB
689       JoinBB = Pred0UniquePred;
690     }
691   }
692 
693   if (!JoinBB && L)
694     JoinBB = L->getHeader();
695 
696   // In backwards direction there is no need to show termination of previous
697   // instructions. If they do not terminate, the code afterward is dead, making
698   // any information/transformation correct anyway.
699   return JoinBB;
700 }
701 
702 const Instruction *
703 MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
704     MustBeExecutedIterator &It, const Instruction *PP) {
705   if (!PP)
706     return PP;
707   LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
708 
709   // If we explore only inside a given basic block we stop at terminators.
710   if (!ExploreInterBlock && PP->isTerminator()) {
711     LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
712     return nullptr;
713   }
714 
715   // If we do not traverse the call graph we check if we can make progress in
716   // the current function. First, check if the instruction is guaranteed to
717   // transfer execution to the successor.
718   bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
719   if (!TransfersExecution)
720     return nullptr;
721 
722   // If this is not a terminator we know that there is a single instruction
723   // after this one that is executed next if control is transfered. If not,
724   // we can try to go back to a call site we entered earlier. If none exists, we
725   // do not know any instruction that has to be executd next.
726   if (!PP->isTerminator()) {
727     const Instruction *NextPP = PP->getNextNode();
728     LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
729     return NextPP;
730   }
731 
732   // Finally, we have to handle terminators, trivial ones first.
733   assert(PP->isTerminator() && "Expected a terminator!");
734 
735   // A terminator without a successor is not handled yet.
736   if (PP->getNumSuccessors() == 0) {
737     LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
738     return nullptr;
739   }
740 
741   // A terminator with a single successor, we will continue at the beginning of
742   // that one.
743   if (PP->getNumSuccessors() == 1) {
744     LLVM_DEBUG(
745         dbgs() << "\tUnconditional terminator, continue with successor\n");
746     return &PP->getSuccessor(0)->front();
747   }
748 
749   // Multiple successors mean we need to find the join point where control flow
750   // converges again. We use the findForwardJoinPoint helper function with
751   // information about the function and helper analyses, if available.
752   if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
753     return &JoinBB->front();
754 
755   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
756   return nullptr;
757 }
758 
759 const Instruction *
760 MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
761     MustBeExecutedIterator &It, const Instruction *PP) {
762   if (!PP)
763     return PP;
764 
765   bool IsFirst = !(PP->getPrevNode());
766   LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
767                     << (IsFirst ? " [IsFirst]" : "") << "\n");
768 
769   // If we explore only inside a given basic block we stop at the first
770   // instruction.
771   if (!ExploreInterBlock && IsFirst) {
772     LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
773     return nullptr;
774   }
775 
776   // The block and function that contains the current position.
777   const BasicBlock *PPBlock = PP->getParent();
778 
779   // If we are inside a block we know what instruction was executed before, the
780   // previous one.
781   if (!IsFirst) {
782     const Instruction *PrevPP = PP->getPrevNode();
783     LLVM_DEBUG(
784         dbgs() << "\tIntermediate instruction, continue with previous\n");
785     // We did not enter a callee so we simply return the previous instruction.
786     return PrevPP;
787   }
788 
789   // Finally, we have to handle the case where the program point is the first in
790   // a block but not in the function. We use the findBackwardJoinPoint helper
791   // function with information about the function and helper analyses, if
792   // available.
793   if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
794     return &JoinBB->back();
795 
796   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
797   return nullptr;
798 }
799 
800 MustBeExecutedIterator::MustBeExecutedIterator(
801     MustBeExecutedContextExplorer &Explorer, const Instruction *I)
802     : Explorer(Explorer), CurInst(I) {
803   reset(I);
804 }
805 
806 void MustBeExecutedIterator::reset(const Instruction *I) {
807   Visited.clear();
808   resetInstruction(I);
809 }
810 
811 void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
812   CurInst = I;
813   Head = Tail = nullptr;
814   Visited.insert({I, ExplorationDirection::FORWARD});
815   Visited.insert({I, ExplorationDirection::BACKWARD});
816   if (Explorer.ExploreCFGForward)
817     Head = I;
818   if (Explorer.ExploreCFGBackward)
819     Tail = I;
820 }
821 
822 const Instruction *MustBeExecutedIterator::advance() {
823   assert(CurInst && "Cannot advance an end iterator!");
824   Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
825   if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
826     return Head;
827   Head = nullptr;
828 
829   Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
830   if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
831     return Tail;
832   Tail = nullptr;
833   return nullptr;
834 }
835 
836 PreservedAnalyses MustExecutePrinterPass::run(Function &F,
837                                               FunctionAnalysisManager &AM) {
838   auto &LI = AM.getResult<LoopAnalysis>(F);
839   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
840 
841   MustExecuteAnnotatedWriter Writer(F, DT, LI);
842   F.print(OS, &Writer);
843   return PreservedAnalyses::all();
844 }
845 
846 PreservedAnalyses
847 MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
848   FunctionAnalysisManager &FAM =
849       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
850   GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
851     return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
852   };
853   GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
854     return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
855   };
856   GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
857     return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
858   };
859 
860   MustBeExecutedContextExplorer Explorer(
861       /* ExploreInterBlock */ true,
862       /* ExploreCFGForward */ true,
863       /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
864 
865   for (Function &F : M) {
866     for (Instruction &I : instructions(F)) {
867       OS << "-- Explore context of: " << I << "\n";
868       for (const Instruction *CI : Explorer.range(&I))
869         OS << "  [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
870     }
871   }
872   return PreservedAnalyses::all();
873 }
874