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