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