llvm/lib/Analysis/MustExecute.cpp

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