contrib/llvm-project/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/Analysis/CFG.h"
  12 #include "llvm/Analysis/InstructionSimplify.h"
  13 #include "llvm/Analysis/LoopInfo.h"
  14 #include "llvm/Analysis/Passes.h"
  15 #include "llvm/Analysis/PostDominators.h"
  16 #include "llvm/Analysis/ValueTracking.h"
  17 #include "llvm/IR/AssemblyAnnotationWriter.h"
  18 #include "llvm/IR/DataLayout.h"
  19 #include "llvm/IR/InstIterator.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/InitializePasses.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/Support/FormattedStream.h"
  25 #include "llvm/Support/raw_ostream.h"
  26
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "must-execute"
  30
  31 const DenseMap<BasicBlock *, ColorVector> &
  32 LoopSafetyInfo::getBlockColors() const {
  33   return BlockColors;
  34 }
  35
  36 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
  37   ColorVector &ColorsForNewBlock = BlockColors[New];
  38   ColorVector &ColorsForOldBlock = BlockColors[Old];
  39   ColorsForNewBlock = ColorsForOldBlock;
  40 }
  41
  42 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  43   (void)BB;
  44   return anyBlockMayThrow();
  45 }
  46
  47 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
  48   return MayThrow;
  49 }
  50
  51 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  52   assert(CurLoop != nullptr && "CurLoop can't be null");
  53   BasicBlock *Header = CurLoop->getHeader();
  54   // Iterate over header and compute safety info.
  55   HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
  56   MayThrow = HeaderMayThrow;
  57   // Iterate over loop instructions and compute safety info.
  58   // Skip header as it has been computed and stored in HeaderMayThrow.
  59   // The first block in loopinfo.Blocks is guaranteed to be the header.
  60   assert(Header == *CurLoop->getBlocks().begin() &&
  61          "First block must be header");
  62   for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
  63                             BBE = CurLoop->block_end();
  64        (BB != BBE) && !MayThrow; ++BB)
  65     MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
  66
  67   computeBlockColors(CurLoop);
  68 }
  69
  70 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  71   return ICF.hasICF(BB);
  72 }
  73
  74 bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
  75   return MayThrow;
  76 }
  77
  78 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  79   assert(CurLoop != nullptr && "CurLoop can't be null");
  80   ICF.clear();
  81   MW.clear();
  82   MayThrow = false;
  83   // Figure out the fact that at least one block may throw.
  84   for (auto &BB : CurLoop->blocks())
  85     if (ICF.hasICF(&*BB)) {
  86       MayThrow = true;
  87       break;
  88     }
  89   computeBlockColors(CurLoop);
  90 }
  91
  92 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
  93                                             const BasicBlock *BB) {
  94   ICF.insertInstructionTo(Inst, BB);
  95   MW.insertInstructionTo(Inst, BB);
  96 }
  97
  98 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
  99   ICF.removeInstruction(Inst);
 100   MW.removeInstruction(Inst);
 101 }
 102
 103 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
 104   // Compute funclet colors if we might sink/hoist in a function with a funclet
 105   // personality routine.
 106   Function *Fn = CurLoop->getHeader()->getParent();
 107   if (Fn->hasPersonalityFn())
 108     if (Constant *PersonalityFn = Fn->getPersonalityFn())
 109       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
 110         BlockColors = colorEHFunclets(*Fn);
 111 }
 112
 113 /// Return true if we can prove that the given ExitBlock is not reached on the
 114 /// first iteration of the given loop.  That is, the backedge of the loop must
 115 /// be executed before the ExitBlock is executed in any dynamic execution trace.
 116 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
 117                                            const DominatorTree *DT,
 118                                            const Loop *CurLoop) {
 119   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
 120   if (!CondExitBlock)
 121     // expect unique exits
 122     return false;
 123   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
 124   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
 125   if (!BI || !BI->isConditional())
 126     return false;
 127   // If condition is constant and false leads to ExitBlock then we always
 128   // execute the true branch.
 129   if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
 130     return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
 131   auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
 132   if (!Cond)
 133     return false;
 134   // todo: this would be a lot more powerful if we used scev, but all the
 135   // plumbing is currently missing to pass a pointer in from the pass
 136   // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
 137   auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
 138   auto *RHS = Cond->getOperand(1);
 139   if (!LHS || LHS->getParent() != CurLoop->getHeader())
 140     return false;
 141   auto DL = ExitBlock->getModule()->getDataLayout();
 142   auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
 143   auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
 144                                           IVStart, RHS,
 145                                           {DL, /*TLI*/ nullptr,
 146                                               DT, /*AC*/ nullptr, BI});
 147   auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
 148   if (!SimpleCst)
 149     return false;
 150   if (ExitBlock == BI->getSuccessor(0))
 151     return SimpleCst->isZeroValue();
 152   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
 153   return SimpleCst->isAllOnesValue();
 154 }
 155
 156 /// Collect all blocks from \p CurLoop which lie on all possible paths from
 157 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
 158 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
 159 static void collectTransitivePredecessors(
 160     const Loop *CurLoop, const BasicBlock *BB,
 161     SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
 162   assert(Predecessors.empty() && "Garbage in predecessors set?");
 163   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 164   if (BB == CurLoop->getHeader())
 165     return;
 166   SmallVector<const BasicBlock *, 4> WorkList;
 167   for (auto *Pred : predecessors(BB)) {
 168     Predecessors.insert(Pred);
 169     WorkList.push_back(Pred);
 170   }
 171   while (!WorkList.empty()) {
 172     auto *Pred = WorkList.pop_back_val();
 173     assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
 174     // We are not interested in backedges and we don't want to leave loop.
 175     if (Pred == CurLoop->getHeader())
 176       continue;
 177     // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
 178     // blocks of this inner loop, even those that are always executed AFTER the
 179     // BB. It may make our analysis more conservative than it could be, see test
 180     // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
 181     // We can ignore backedge of all loops containing BB to get a sligtly more
 182     // optimistic result.
 183     for (auto *PredPred : predecessors(Pred))
 184       if (Predecessors.insert(PredPred).second)
 185         WorkList.push_back(PredPred);
 186   }
 187 }
 188
 189 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
 190                                              const BasicBlock *BB,
 191                                              const DominatorTree *DT) const {
 192   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 193
 194   // Fast path: header is always reached once the loop is entered.
 195   if (BB == CurLoop->getHeader())
 196     return true;
 197
 198   // Collect all transitive predecessors of BB in the same loop. This set will
 199   // be a subset of the blocks within the loop.
 200   SmallPtrSet<const BasicBlock *, 4> Predecessors;
 201   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 202
 203   // Make sure that all successors of, all predecessors of BB which are not
 204   // dominated by BB, are either:
 205   // 1) BB,
 206   // 2) Also predecessors of BB,
 207   // 3) Exit blocks which are not taken on 1st iteration.
 208   // Memoize blocks we've already checked.
 209   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
 210   for (auto *Pred : Predecessors) {
 211     // Predecessor block may throw, so it has a side exit.
 212     if (blockMayThrow(Pred))
 213       return false;
 214
 215     // BB dominates Pred, so if Pred runs, BB must run.
 216     // This is true when Pred is a loop latch.
 217     if (DT->dominates(BB, Pred))
 218       continue;
 219
 220     for (auto *Succ : successors(Pred))
 221       if (CheckedSuccessors.insert(Succ).second &&
 222           Succ != BB && !Predecessors.count(Succ))
 223         // By discharging conditions that are not executed on the 1st iteration,
 224         // we guarantee that *at least* on the first iteration all paths from
 225         // header that *may* execute will lead us to the block of interest. So
 226         // that if we had virtually peeled one iteration away, in this peeled
 227         // iteration the set of predecessors would contain only paths from
 228         // header to BB without any exiting edges that may execute.
 229         //
 230         // TODO: We only do it for exiting edges currently. We could use the
 231         // same function to skip some of the edges within the loop if we know
 232         // that they will not be taken on the 1st iteration.
 233         //
 234         // TODO: If we somehow know the number of iterations in loop, the same
 235         // check may be done for any arbitrary N-th iteration as long as N is
 236         // not greater than minimum number of iterations in this loop.
 237         if (CurLoop->contains(Succ) ||
 238             !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
 239           return false;
 240   }
 241
 242   // All predecessors can only lead us to BB.
 243   return true;
 244 }
 245
 246 /// Returns true if the instruction in a loop is guaranteed to execute at least
 247 /// once.
 248 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
 249                                                  const DominatorTree *DT,
 250                                                  const Loop *CurLoop) const {
 251   // If the instruction is in the header block for the loop (which is very
 252   // common), it is always guaranteed to dominate the exit blocks.  Since this
 253   // is a common case, and can save some work, check it now.
 254   if (Inst.getParent() == CurLoop->getHeader())
 255     // If there's a throw in the header block, we can't guarantee we'll reach
 256     // Inst unless we can prove that Inst comes before the potential implicit
 257     // exit.  At the moment, we use a (cheap) hack for the common case where
 258     // the instruction of interest is the first one in the block.
 259     return !HeaderMayThrow ||
 260            Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
 261
 262   // If there is a path from header to exit or latch that doesn't lead to our
 263   // instruction's block, return false.
 264   return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
 265 }
 266
 267 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
 268                                               const DominatorTree *DT,
 269                                               const Loop *CurLoop) const {
 270   return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
 271          allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
 272 }
 273
 274 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
 275                                                  const Loop *CurLoop) const {
 276   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 277
 278   // Fast path: there are no instructions before header.
 279   if (BB == CurLoop->getHeader())
 280     return true;
 281
 282   // Collect all transitive predecessors of BB in the same loop. This set will
 283   // be a subset of the blocks within the loop.
 284   SmallPtrSet<const BasicBlock *, 4> Predecessors;
 285   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 286   // Find if there any instruction in either predecessor that could write
 287   // to memory.
 288   for (auto *Pred : Predecessors)
 289     if (MW.mayWriteToMemory(Pred))
 290       return false;
 291   return true;
 292 }
 293
 294 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
 295                                                  const Loop *CurLoop) const {
 296   auto *BB = I.getParent();
 297   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 298   return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
 299          doesNotWriteMemoryBefore(BB, CurLoop);
 300 }
 301
 302 namespace {
 303   struct MustExecutePrinter : public FunctionPass {
 304
 305     static char ID; // Pass identification, replacement for typeid
 306     MustExecutePrinter() : FunctionPass(ID) {
 307       initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
 308     }
 309     void getAnalysisUsage(AnalysisUsage &AU) const override {
 310       AU.setPreservesAll();
 311       AU.addRequired<DominatorTreeWrapperPass>();
 312       AU.addRequired<LoopInfoWrapperPass>();
 313     }
 314     bool runOnFunction(Function &F) override;
 315   };
 316   struct MustBeExecutedContextPrinter : public ModulePass {
 317     static char ID;
 318
 319     MustBeExecutedContextPrinter() : ModulePass(ID) {
 320       initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry());
 321     }
 322     void getAnalysisUsage(AnalysisUsage &AU) const override {
 323       AU.setPreservesAll();
 324     }
 325     bool runOnModule(Module &M) override;
 326   };
 327 }
 328
 329 char MustExecutePrinter::ID = 0;
 330 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
 331                       "Instructions which execute on loop entry", false, true)
 332 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 333 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 334 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
 335                     "Instructions which execute on loop entry", false, true)
 336
 337 FunctionPass *llvm::createMustExecutePrinter() {
 338   return new MustExecutePrinter();
 339 }
 340
 341 char MustBeExecutedContextPrinter::ID = 0;
 342 INITIALIZE_PASS_BEGIN(
 343     MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
 344     "print the must-be-executed-contexed for all instructions", false, true)
 345 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 346 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 347 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 348 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
 349                     "print-must-be-executed-contexts",
 350                     "print the must-be-executed-contexed for all instructions",
 351                     false, true)
 352
 353 ModulePass *llvm::createMustBeExecutedContextPrinter() {
 354   return new MustBeExecutedContextPrinter();
 355 }
 356
 357 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
 358   // We provide non-PM analysis here because the old PM doesn't like to query
 359   // function passes from a module pass.
 360   SmallVector<std::unique_ptr<PostDominatorTree>, 8> PDTs;
 361   SmallVector<std::unique_ptr<DominatorTree>, 8> DTs;
 362   SmallVector<std::unique_ptr<LoopInfo>, 8> LIs;
 363
 364   GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
 365     DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
 366     LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
 367     return LIs.back().get();
 368   };
 369   GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
 370     DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
 371     return DTs.back().get();
 372   };
 373   GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
 374     PDTs.push_back(
 375         std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
 376     return PDTs.back().get();
 377   };
 378   MustBeExecutedContextExplorer Explorer(
 379       /* ExploreInterBlock */ true,
 380       /* ExploreCFGForward */ true,
 381       /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
 382
 383   for (Function &F : M) {
 384     for (Instruction &I : instructions(F)) {
 385       dbgs() << "-- Explore context of: " << I << "\n";
 386       for (const Instruction *CI : Explorer.range(&I))
 387         dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
 388                << "\n";
 389     }
 390   }
 391
 392   return false;
 393 }
 394
 395 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
 396   // TODO: merge these two routines.  For the moment, we display the best
 397   // result obtained by *either* implementation.  This is a bit unfair since no
 398   // caller actually gets the full power at the moment.
 399   SimpleLoopSafetyInfo LSI;
 400   LSI.computeLoopSafetyInfo(L);
 401   return LSI.isGuaranteedToExecute(I, DT, L) ||
 402     isGuaranteedToExecuteForEveryIteration(&I, L);
 403 }
 404
 405 namespace {
 406 /// An assembly annotator class to print must execute information in
 407 /// comments.
 408 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
 409   DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
 410
 411 public:
 412   MustExecuteAnnotatedWriter(const Function &F,
 413                              DominatorTree &DT, LoopInfo &LI) {
 414     for (auto &I: instructions(F)) {
 415       Loop *L = LI.getLoopFor(I.getParent());
 416       while (L) {
 417         if (isMustExecuteIn(I, L, &DT)) {
 418           MustExec[&I].push_back(L);
 419         }
 420         L = L->getParentLoop();
 421       };
 422     }
 423   }
 424   MustExecuteAnnotatedWriter(const Module &M,
 425                              DominatorTree &DT, LoopInfo &LI) {
 426     for (auto &F : M)
 427     for (auto &I: instructions(F)) {
 428       Loop *L = LI.getLoopFor(I.getParent());
 429       while (L) {
 430         if (isMustExecuteIn(I, L, &DT)) {
 431           MustExec[&I].push_back(L);
 432         }
 433         L = L->getParentLoop();
 434       };
 435     }
 436   }
 437
 438
 439   void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
 440     if (!MustExec.count(&V))
 441       return;
 442
 443     const auto &Loops = MustExec.lookup(&V);
 444     const auto NumLoops = Loops.size();
 445     if (NumLoops > 1)
 446       OS << " ; (mustexec in " << NumLoops << " loops: ";
 447     else
 448       OS << " ; (mustexec in: ";
 449
 450     bool first = true;
 451     for (const Loop *L : Loops) {
 452       if (!first)
 453         OS << ", ";
 454       first = false;
 455       OS << L->getHeader()->getName();
 456     }
 457     OS << ")";
 458   }
 459 };
 460 } // namespace
 461
 462 bool MustExecutePrinter::runOnFunction(Function &F) {
 463   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 464   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 465
 466   MustExecuteAnnotatedWriter Writer(F, DT, LI);
 467   F.print(dbgs(), &Writer);
 468
 469   return false;
 470 }
 471
 472 /// Return true if \p L might be an endless loop.
 473 static bool maybeEndlessLoop(const Loop &L) {
 474   if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
 475     return false;
 476   // TODO: Actually try to prove it is not.
 477   // TODO: If maybeEndlessLoop is going to be expensive, cache it.
 478   return true;
 479 }
 480
 481 bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
 482   if (!LI)
 483     return false;
 484   using RPOTraversal = ReversePostOrderTraversal<const Function *>;
 485   RPOTraversal FuncRPOT(&F);
 486   return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
 487                                 const LoopInfo>(FuncRPOT, *LI);
 488 }
 489
 490 /// Lookup \p Key in \p Map and return the result, potentially after
 491 /// initializing the optional through \p Fn(\p args).
 492 template <typename K, typename V, typename FnTy, typename... ArgsTy>
 493 static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
 494                                    FnTy &&Fn, ArgsTy&&... args) {
 495   Optional<V> &OptVal = Map[Key];
 496   if (!OptVal.hasValue())
 497     OptVal = Fn(std::forward<ArgsTy>(args)...);
 498   return OptVal.getValue();
 499 }
 500
 501 const BasicBlock *
 502 MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
 503   const LoopInfo *LI = LIGetter(*InitBB->getParent());
 504   const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
 505
 506   LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
 507                     << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
 508
 509   const Function &F = *InitBB->getParent();
 510   const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
 511   const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
 512   bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
 513                                (L && !maybeEndlessLoop(*L))) &&
 514                               F.doesNotThrow();
 515   LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
 516                     << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
 517                     << "\n");
 518
 519   // Determine the adjacent blocks in the given direction but exclude (self)
 520   // loops under certain circumstances.
 521   SmallVector<const BasicBlock *, 8> Worklist;
 522   for (const BasicBlock *SuccBB : successors(InitBB)) {
 523     bool IsLatch = SuccBB == HeaderBB;
 524     // Loop latches are ignored in forward propagation if the loop cannot be
 525     // endless and may not throw: control has to go somewhere.
 526     if (!WillReturnAndNoThrow || !IsLatch)
 527       Worklist.push_back(SuccBB);
 528   }
 529   LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
 530
 531   // If there are no other adjacent blocks, there is no join point.
 532   if (Worklist.empty())
 533     return nullptr;
 534
 535   // If there is one adjacent block, it is the join point.
 536   if (Worklist.size() == 1)
 537     return Worklist[0];
 538
 539   // Try to determine a join block through the help of the post-dominance
 540   // tree. If no tree was provided, we perform simple pattern matching for one
 541   // block conditionals and one block loops only.
 542   const BasicBlock *JoinBB = nullptr;
 543   if (PDT)
 544     if (const auto *InitNode = PDT->getNode(InitBB))
 545       if (const auto *IDomNode = InitNode->getIDom())
 546         JoinBB = IDomNode->getBlock();
 547
 548   if (!JoinBB && Worklist.size() == 2) {
 549     const BasicBlock *Succ0 = Worklist[0];
 550     const BasicBlock *Succ1 = Worklist[1];
 551     const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
 552     const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
 553     if (Succ0UniqueSucc == InitBB) {
 554       // InitBB -> Succ0 -> InitBB
 555       // InitBB -> Succ1  = JoinBB
 556       JoinBB = Succ1;
 557     } else if (Succ1UniqueSucc == InitBB) {
 558       // InitBB -> Succ1 -> InitBB
 559       // InitBB -> Succ0  = JoinBB
 560       JoinBB = Succ0;
 561     } else if (Succ0 == Succ1UniqueSucc) {
 562       // InitBB ->          Succ0 = JoinBB
 563       // InitBB -> Succ1 -> Succ0 = JoinBB
 564       JoinBB = Succ0;
 565     } else if (Succ1 == Succ0UniqueSucc) {
 566       // InitBB -> Succ0 -> Succ1 = JoinBB
 567       // InitBB ->          Succ1 = JoinBB
 568       JoinBB = Succ1;
 569     } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
 570       // InitBB -> Succ0 -> JoinBB
 571       // InitBB -> Succ1 -> JoinBB
 572       JoinBB = Succ0UniqueSucc;
 573     }
 574   }
 575
 576   if (!JoinBB && L)
 577     JoinBB = L->getUniqueExitBlock();
 578
 579   if (!JoinBB)
 580     return nullptr;
 581
 582   LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
 583
 584   // In forward direction we check if control will for sure reach JoinBB from
 585   // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
 586   // are: infinite loops and instructions that do not necessarily transfer
 587   // execution to their successor. To check for them we traverse the CFG from
 588   // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
 589
 590   // If we know the function is "will-return" and "no-throw" there is no need
 591   // for futher checks.
 592   if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
 593
 594     auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
 595       return isGuaranteedToTransferExecutionToSuccessor(BB);
 596     };
 597
 598     SmallPtrSet<const BasicBlock *, 16> Visited;
 599     while (!Worklist.empty()) {
 600       const BasicBlock *ToBB = Worklist.pop_back_val();
 601       if (ToBB == JoinBB)
 602         continue;
 603
 604       // Make sure all loops in-between are finite.
 605       if (!Visited.insert(ToBB).second) {
 606         if (!F.hasFnAttribute(Attribute::WillReturn)) {
 607           if (!LI)
 608             return nullptr;
 609
 610           bool MayContainIrreducibleControl = getOrCreateCachedOptional(
 611               &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
 612           if (MayContainIrreducibleControl)
 613             return nullptr;
 614
 615           const Loop *L = LI->getLoopFor(ToBB);
 616           if (L && maybeEndlessLoop(*L))
 617             return nullptr;
 618         }
 619
 620         continue;
 621       }
 622
 623       // Make sure the block has no instructions that could stop control
 624       // transfer.
 625       bool TransfersExecution = getOrCreateCachedOptional(
 626           ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
 627       if (!TransfersExecution)
 628         return nullptr;
 629
 630       for (const BasicBlock *AdjacentBB : successors(ToBB))
 631         Worklist.push_back(AdjacentBB);
 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 }