MustExecute.cpp

//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/MustExecute.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

#define DEBUG_TYPE "must-execute"

const DenseMap<BasicBlock *, ColorVector> &
LoopSafetyInfo::getBlockColors() const {
  return BlockColors;
}

void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
  ColorVector &ColorsForNewBlock = BlockColors[New];
  ColorVector &ColorsForOldBlock = BlockColors[Old];
  ColorsForNewBlock = ColorsForOldBlock;
}

bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  (void)BB;
  return anyBlockMayThrow();
}

bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
  return MayThrow;
}

void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  assert(CurLoop != nullptr && "CurLoop can't be null");
  BasicBlock *Header = CurLoop->getHeader();
  // Iterate over header and compute safety info.
  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
  MayThrow = HeaderMayThrow;
  // Iterate over loop instructions and compute safety info.
  // Skip header as it has been computed and stored in HeaderMayThrow.
  // The first block in loopinfo.Blocks is guaranteed to be the header.
  assert(Header == *CurLoop->getBlocks().begin() &&
         "First block must be header");
  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
                            BBE = CurLoop->block_end();
       (BB != BBE) && !MayThrow; ++BB)
    MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);

  computeBlockColors(CurLoop);
}

bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  return ICF.hasICF(BB);
}

bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
  return MayThrow;
}

void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  assert(CurLoop != nullptr && "CurLoop can't be null");
  ICF.clear();
  MW.clear();
  MayThrow = false;
  // Figure out the fact that at least one block may throw.
  for (auto &BB : CurLoop->blocks())
    if (ICF.hasICF(&*BB)) {
      MayThrow = true;
      break;
    }
  computeBlockColors(CurLoop);
}

void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
                                            const BasicBlock *BB) {
  ICF.insertInstructionTo(Inst, BB);
  MW.insertInstructionTo(Inst, BB);
}

void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
  ICF.removeInstruction(Inst);
  MW.removeInstruction(Inst);
}

void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
  // Compute funclet colors if we might sink/hoist in a function with a funclet
  // personality routine.
  Function *Fn = CurLoop->getHeader()->getParent();
  if (Fn->hasPersonalityFn())
    if (Constant *PersonalityFn = Fn->getPersonalityFn())
      if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
        BlockColors = colorEHFunclets(*Fn);
}

/// Return true if we can prove that the given ExitBlock is not reached on the
/// first iteration of the given loop.  That is, the backedge of the loop must
/// be executed before the ExitBlock is executed in any dynamic execution trace.
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
                                           const DominatorTree *DT,
                                           const Loop *CurLoop) {
  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
  if (!CondExitBlock)
    // expect unique exits
    return false;
  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
  if (!BI || !BI->isConditional())
    return false;
  // If condition is constant and false leads to ExitBlock then we always
  // execute the true branch.
  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
    return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
  if (!Cond)
    return false;
  // todo: this would be a lot more powerful if we used scev, but all the
  // plumbing is currently missing to pass a pointer in from the pass
  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
  auto *RHS = Cond->getOperand(1);
  if (!LHS || LHS->getParent() != CurLoop->getHeader())
    return false;
  auto DL = ExitBlock->getModule()->getDataLayout();
  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
                                          IVStart, RHS,
                                          {DL, /*TLI*/ nullptr,
                                              DT, /*AC*/ nullptr, BI});
  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
  if (!SimpleCst)
    return false;
  if (ExitBlock == BI->getSuccessor(0))
    return SimpleCst->isZeroValue();
  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
  return SimpleCst->isAllOnesValue();
}

/// Collect all blocks from \p CurLoop which lie on all possible paths from
/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
static void collectTransitivePredecessors(
    const Loop *CurLoop, const BasicBlock *BB,
    SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
  assert(Predecessors.empty() && "Garbage in predecessors set?");
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
  if (BB == CurLoop->getHeader())
    return;
  SmallVector<const BasicBlock *, 4> WorkList;
  for (auto *Pred : predecessors(BB)) {
    Predecessors.insert(Pred);
    WorkList.push_back(Pred);
  }
  while (!WorkList.empty()) {
    auto *Pred = WorkList.pop_back_val();
    assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
    // We are not interested in backedges and we don't want to leave loop.
    if (Pred == CurLoop->getHeader())
      continue;
    // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
    // blocks of this inner loop, even those that are always executed AFTER the
    // BB. It may make our analysis more conservative than it could be, see test
    // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
    // We can ignore backedge of all loops containing BB to get a sligtly more
    // optimistic result.
    for (auto *PredPred : predecessors(Pred))
      if (Predecessors.insert(PredPred).second)
        WorkList.push_back(PredPred);
  }
}

bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
                                             const BasicBlock *BB,
                                             const DominatorTree *DT) const {
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

  // Fast path: header is always reached once the loop is entered.
  if (BB == CurLoop->getHeader())
    return true;

  // Collect all transitive predecessors of BB in the same loop. This set will
  // be a subset of the blocks within the loop.
  SmallPtrSet<const BasicBlock *, 4> Predecessors;
  collectTransitivePredecessors(CurLoop, BB, Predecessors);

  // Make sure that all successors of, all predecessors of BB which are not
  // dominated by BB, are either:
  // 1) BB,
  // 2) Also predecessors of BB,
  // 3) Exit blocks which are not taken on 1st iteration.
  // Memoize blocks we've already checked.
  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
  for (auto *Pred : Predecessors) {
    // Predecessor block may throw, so it has a side exit.
    if (blockMayThrow(Pred))
      return false;

    // BB dominates Pred, so if Pred runs, BB must run.
    // This is true when Pred is a loop latch.
    if (DT->dominates(BB, Pred))
      continue;

    for (auto *Succ : successors(Pred))
      if (CheckedSuccessors.insert(Succ).second &&
          Succ != BB && !Predecessors.count(Succ))
        // By discharging conditions that are not executed on the 1st iteration,
        // we guarantee that *at least* on the first iteration all paths from
        // header that *may* execute will lead us to the block of interest. So
        // that if we had virtually peeled one iteration away, in this peeled
        // iteration the set of predecessors would contain only paths from
        // header to BB without any exiting edges that may execute.
        //
        // TODO: We only do it for exiting edges currently. We could use the
        // same function to skip some of the edges within the loop if we know
        // that they will not be taken on the 1st iteration.
        //
        // TODO: If we somehow know the number of iterations in loop, the same
        // check may be done for any arbitrary N-th iteration as long as N is
        // not greater than minimum number of iterations in this loop.
        if (CurLoop->contains(Succ) ||
            !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
          return false;
  }

  // All predecessors can only lead us to BB.
  return true;
}

/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once.
bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
                                                 const DominatorTree *DT,
                                                 const Loop *CurLoop) const {
  // If the instruction is in the header block for the loop (which is very
  // common), it is always guaranteed to dominate the exit blocks.  Since this
  // is a common case, and can save some work, check it now.
  if (Inst.getParent() == CurLoop->getHeader())
    // If there's a throw in the header block, we can't guarantee we'll reach
    // Inst unless we can prove that Inst comes before the potential implicit
    // exit.  At the moment, we use a (cheap) hack for the common case where
    // the instruction of interest is the first one in the block.
    return !HeaderMayThrow ||
           Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;

  // If there is a path from header to exit or latch that doesn't lead to our
  // instruction's block, return false.
  return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
}

bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
                                              const DominatorTree *DT,
                                              const Loop *CurLoop) const {
  return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
         allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
}

bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
                                                 const Loop *CurLoop) const {
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

  // Fast path: there are no instructions before header.
  if (BB == CurLoop->getHeader())
    return true;

  // Collect all transitive predecessors of BB in the same loop. This set will
  // be a subset of the blocks within the loop.
  SmallPtrSet<const BasicBlock *, 4> Predecessors;
  collectTransitivePredecessors(CurLoop, BB, Predecessors);
  // Find if there any instruction in either predecessor that could write
  // to memory.
  for (auto *Pred : Predecessors)
    if (MW.mayWriteToMemory(Pred))
      return false;
  return true;
}

bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
                                                 const Loop *CurLoop) const {
  auto *BB = I.getParent();
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
  return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
         doesNotWriteMemoryBefore(BB, CurLoop);
}

namespace {
  struct MustExecutePrinter : public FunctionPass {

    static char ID; // Pass identification, replacement for typeid
    MustExecutePrinter() : FunctionPass(ID) {
      initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
    }
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.setPreservesAll();
      AU.addRequired<DominatorTreeWrapperPass>();
      AU.addRequired<LoopInfoWrapperPass>();
    }
    bool runOnFunction(Function &F) override;
  };
  struct MustBeExecutedContextPrinter : public ModulePass {
    static char ID;

    MustBeExecutedContextPrinter() : ModulePass(ID) {
      initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry());
    }
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.setPreservesAll();
    }
    bool runOnModule(Module &M) override;
  };
}

char MustExecutePrinter::ID = 0;
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
                      "Instructions which execute on loop entry", false, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
                    "Instructions which execute on loop entry", false, true)

FunctionPass *llvm::createMustExecutePrinter() {
  return new MustExecutePrinter();
}

char MustBeExecutedContextPrinter::ID = 0;
INITIALIZE_PASS_BEGIN(
    MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
    "print the must-be-executed-contexed for all instructions", false, true)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
                    "print-must-be-executed-contexts",
                    "print the must-be-executed-contexed for all instructions",
                    false, true)

ModulePass *llvm::createMustBeExecutedContextPrinter() {
  return new MustBeExecutedContextPrinter();
}

bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
  // We provide non-PM analysis here because the old PM doesn't like to query
  // function passes from a module pass.
  SmallVector<std::unique_ptr<PostDominatorTree>, 8> PDTs;
  SmallVector<std::unique_ptr<DominatorTree>, 8> DTs;
  SmallVector<std::unique_ptr<LoopInfo>, 8> LIs;

  GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
    DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
    LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
    return LIs.back().get();
  };
  GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
    DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
    return DTs.back().get();
  };
  GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
    PDTs.push_back(
        std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
    return PDTs.back().get();
  };
  MustBeExecutedContextExplorer Explorer(
      /* ExploreInterBlock */ true,
      /* ExploreCFGForward */ true,
      /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);

  for (Function &F : M) {
    for (Instruction &I : instructions(F)) {
      dbgs() << "-- Explore context of: " << I << "\n";
      for (const Instruction *CI : Explorer.range(&I))
        dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
               << "\n";
    }
  }

  return false;
}

static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
  // TODO: merge these two routines.  For the moment, we display the best
  // result obtained by *either* implementation.  This is a bit unfair since no
  // caller actually gets the full power at the moment.
  SimpleLoopSafetyInfo LSI;
  LSI.computeLoopSafetyInfo(L);
  return LSI.isGuaranteedToExecute(I, DT, L) ||
    isGuaranteedToExecuteForEveryIteration(&I, L);
}

namespace {
/// An assembly annotator class to print must execute information in
/// comments.
class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
  DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;

public:
  MustExecuteAnnotatedWriter(const Function &F,
                             DominatorTree &DT, LoopInfo &LI) {
    for (auto &I: instructions(F)) {
      Loop *L = LI.getLoopFor(I.getParent());
      while (L) {
        if (isMustExecuteIn(I, L, &DT)) {
          MustExec[&I].push_back(L);
        }
        L = L->getParentLoop();
      };
    }
  }
  MustExecuteAnnotatedWriter(const Module &M,
                             DominatorTree &DT, LoopInfo &LI) {
    for (auto &F : M)
    for (auto &I: instructions(F)) {
      Loop *L = LI.getLoopFor(I.getParent());
      while (L) {
        if (isMustExecuteIn(I, L, &DT)) {
          MustExec[&I].push_back(L);
        }
        L = L->getParentLoop();
      };
    }
  }


  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
    if (!MustExec.count(&V))
      return;

    const auto &Loops = MustExec.lookup(&V);
    const auto NumLoops = Loops.size();
    if (NumLoops > 1)
      OS << " ; (mustexec in " << NumLoops << " loops: ";
    else
      OS << " ; (mustexec in: ";

    bool first = true;
    for (const Loop *L : Loops) {
      if (!first)
        OS << ", ";
      first = false;
      OS << L->getHeader()->getName();
    }
    OS << ")";
  }
};
} // namespace

bool MustExecutePrinter::runOnFunction(Function &F) {
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();

  MustExecuteAnnotatedWriter Writer(F, DT, LI);
  F.print(dbgs(), &Writer);

  return false;
}

/// Return true if \p L might be an endless loop.
static bool maybeEndlessLoop(const Loop &L) {
  if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
    return false;
  // TODO: Actually try to prove it is not.
  // TODO: If maybeEndlessLoop is going to be expensive, cache it.
  return true;
}

bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
  if (!LI)
    return false;
  using RPOTraversal = ReversePostOrderTraversal<const Function *>;
  RPOTraversal FuncRPOT(&F);
  return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
                                const LoopInfo>(FuncRPOT, *LI);
}

/// Lookup \p Key in \p Map and return the result, potentially after
/// initializing the optional through \p Fn(\p args).
template <typename K, typename V, typename FnTy, typename... ArgsTy>
static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
                                   FnTy &&Fn, ArgsTy&&... args) {
  Optional<V> &OptVal = Map[Key];
  if (!OptVal.hasValue())
    OptVal = Fn(std::forward<ArgsTy>(args)...);
  return OptVal.getValue();
}

const BasicBlock *
MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
  const LoopInfo *LI = LIGetter(*InitBB->getParent());
  const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());

  LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
                    << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));

  const Function &F = *InitBB->getParent();
  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
  const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
  bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
                               (L && !maybeEndlessLoop(*L))) &&
                              F.doesNotThrow();
  LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
                    << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
                    << "\n");

  // Determine the adjacent blocks in the given direction but exclude (self)
  // loops under certain circumstances.
  SmallVector<const BasicBlock *, 8> Worklist;
  for (const BasicBlock *SuccBB : successors(InitBB)) {
    bool IsLatch = SuccBB == HeaderBB;
    // Loop latches are ignored in forward propagation if the loop cannot be
    // endless and may not throw: control has to go somewhere.
    if (!WillReturnAndNoThrow || !IsLatch)
      Worklist.push_back(SuccBB);
  }
  LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");

  // If there are no other adjacent blocks, there is no join point.
  if (Worklist.empty())
    return nullptr;

  // If there is one adjacent block, it is the join point.
  if (Worklist.size() == 1)
    return Worklist[0];

  // Try to determine a join block through the help of the post-dominance
  // tree. If no tree was provided, we perform simple pattern matching for one
  // block conditionals and one block loops only.
  const BasicBlock *JoinBB = nullptr;
  if (PDT)
    if (const auto *InitNode = PDT->getNode(InitBB))
      if (const auto *IDomNode = InitNode->getIDom())
        JoinBB = IDomNode->getBlock();

  if (!JoinBB && Worklist.size() == 2) {
    const BasicBlock *Succ0 = Worklist[0];
    const BasicBlock *Succ1 = Worklist[1];
    const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
    const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
    if (Succ0UniqueSucc == InitBB) {
      // InitBB -> Succ0 -> InitBB
      // InitBB -> Succ1  = JoinBB
      JoinBB = Succ1;
    } else if (Succ1UniqueSucc == InitBB) {
      // InitBB -> Succ1 -> InitBB
      // InitBB -> Succ0  = JoinBB
      JoinBB = Succ0;
    } else if (Succ0 == Succ1UniqueSucc) {
      // InitBB ->          Succ0 = JoinBB
      // InitBB -> Succ1 -> Succ0 = JoinBB
      JoinBB = Succ0;
    } else if (Succ1 == Succ0UniqueSucc) {
      // InitBB -> Succ0 -> Succ1 = JoinBB
      // InitBB ->          Succ1 = JoinBB
      JoinBB = Succ1;
    } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
      // InitBB -> Succ0 -> JoinBB
      // InitBB -> Succ1 -> JoinBB
      JoinBB = Succ0UniqueSucc;
    }
  }

  if (!JoinBB && L)
    JoinBB = L->getUniqueExitBlock();

  if (!JoinBB)
    return nullptr;

  LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");

  // In forward direction we check if control will for sure reach JoinBB from
  // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
  // are: infinite loops and instructions that do not necessarily transfer
  // execution to their successor. To check for them we traverse the CFG from
  // the adjacent blocks to the JoinBB, looking at all intermediate blocks.

  // If we know the function is "will-return" and "no-throw" there is no need
  // for futher checks.
  if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {

    auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
      return isGuaranteedToTransferExecutionToSuccessor(BB);
    };

    SmallPtrSet<const BasicBlock *, 16> Visited;
    while (!Worklist.empty()) {
      const BasicBlock *ToBB = Worklist.pop_back_val();
      if (ToBB == JoinBB)
        continue;

      // Make sure all loops in-between are finite.
      if (!Visited.insert(ToBB).second) {
        if (!F.hasFnAttribute(Attribute::WillReturn)) {
          if (!LI)
            return nullptr;

          bool MayContainIrreducibleControl = getOrCreateCachedOptional(
              &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
          if (MayContainIrreducibleControl)
            return nullptr;

          const Loop *L = LI->getLoopFor(ToBB);
          if (L && maybeEndlessLoop(*L))
            return nullptr;
        }

        continue;
      }

      // Make sure the block has no instructions that could stop control
      // transfer.
      bool TransfersExecution = getOrCreateCachedOptional(
          ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
      if (!TransfersExecution)
        return nullptr;

      for (const BasicBlock *AdjacentBB : successors(ToBB))
        Worklist.push_back(AdjacentBB);
    }
  }

  LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
  return JoinBB;
}
const BasicBlock *
MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
  const LoopInfo *LI = LIGetter(*InitBB->getParent());
  const DominatorTree *DT = DTGetter(*InitBB->getParent());
  LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
                    << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));

  // Try to determine a join block through the help of the dominance tree. If no
  // tree was provided, we perform simple pattern matching for one block
  // conditionals only.
  if (DT)
    if (const auto *InitNode = DT->getNode(InitBB))
      if (const auto *IDomNode = InitNode->getIDom())
        return IDomNode->getBlock();

  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
  const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;

  // Determine the predecessor blocks but ignore backedges.
  SmallVector<const BasicBlock *, 8> Worklist;
  for (const BasicBlock *PredBB : predecessors(InitBB)) {
    bool IsBackedge =
        (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
    // Loop backedges are ignored in backwards propagation: control has to come
    // from somewhere.
    if (!IsBackedge)
      Worklist.push_back(PredBB);
  }

  // If there are no other predecessor blocks, there is no join point.
  if (Worklist.empty())
    return nullptr;

  // If there is one predecessor block, it is the join point.
  if (Worklist.size() == 1)
    return Worklist[0];

  const BasicBlock *JoinBB = nullptr;
  if (Worklist.size() == 2) {
    const BasicBlock *Pred0 = Worklist[0];
    const BasicBlock *Pred1 = Worklist[1];
    const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
    const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
    if (Pred0 == Pred1UniquePred) {
      // InitBB <-          Pred0 = JoinBB
      // InitBB <- Pred1 <- Pred0 = JoinBB
      JoinBB = Pred0;
    } else if (Pred1 == Pred0UniquePred) {
      // InitBB <- Pred0 <- Pred1 = JoinBB
      // InitBB <-          Pred1 = JoinBB
      JoinBB = Pred1;
    } else if (Pred0UniquePred == Pred1UniquePred) {
      // InitBB <- Pred0 <- JoinBB
      // InitBB <- Pred1 <- JoinBB
      JoinBB = Pred0UniquePred;
    }
  }

  if (!JoinBB && L)
    JoinBB = L->getHeader();

  // In backwards direction there is no need to show termination of previous
  // instructions. If they do not terminate, the code afterward is dead, making
  // any information/transformation correct anyway.
  return JoinBB;
}

const Instruction *
MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
    MustBeExecutedIterator &It, const Instruction *PP) {
  if (!PP)
    return PP;
  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");

  // If we explore only inside a given basic block we stop at terminators.
  if (!ExploreInterBlock && PP->isTerminator()) {
    LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
    return nullptr;
  }

  // If we do not traverse the call graph we check if we can make progress in
  // the current function. First, check if the instruction is guaranteed to
  // transfer execution to the successor.
  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
  if (!TransfersExecution)
    return nullptr;

  // If this is not a terminator we know that there is a single instruction
  // after this one that is executed next if control is transfered. If not,
  // we can try to go back to a call site we entered earlier. If none exists, we
  // do not know any instruction that has to be executd next.
  if (!PP->isTerminator()) {
    const Instruction *NextPP = PP->getNextNode();
    LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
    return NextPP;
  }

  // Finally, we have to handle terminators, trivial ones first.
  assert(PP->isTerminator() && "Expected a terminator!");

  // A terminator without a successor is not handled yet.
  if (PP->getNumSuccessors() == 0) {
    LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
    return nullptr;
  }

  // A terminator with a single successor, we will continue at the beginning of
  // that one.
  if (PP->getNumSuccessors() == 1) {
    LLVM_DEBUG(
        dbgs() << "\tUnconditional terminator, continue with successor\n");
    return &PP->getSuccessor(0)->front();
  }

  // Multiple successors mean we need to find the join point where control flow
  // converges again. We use the findForwardJoinPoint helper function with
  // information about the function and helper analyses, if available.
  if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
    return &JoinBB->front();

  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
  return nullptr;
}

const Instruction *
MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
    MustBeExecutedIterator &It, const Instruction *PP) {
  if (!PP)
    return PP;

  bool IsFirst = !(PP->getPrevNode());
  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
                    << (IsFirst ? " [IsFirst]" : "") << "\n");

  // If we explore only inside a given basic block we stop at the first
  // instruction.
  if (!ExploreInterBlock && IsFirst) {
    LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
    return nullptr;
  }

  // The block and function that contains the current position.
  const BasicBlock *PPBlock = PP->getParent();

  // If we are inside a block we know what instruction was executed before, the
  // previous one.
  if (!IsFirst) {
    const Instruction *PrevPP = PP->getPrevNode();
    LLVM_DEBUG(
        dbgs() << "\tIntermediate instruction, continue with previous\n");
    // We did not enter a callee so we simply return the previous instruction.
    return PrevPP;
  }

  // Finally, we have to handle the case where the program point is the first in
  // a block but not in the function. We use the findBackwardJoinPoint helper
  // function with information about the function and helper analyses, if
  // available.
  if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
    return &JoinBB->back();

  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
  return nullptr;
}

MustBeExecutedIterator::MustBeExecutedIterator(
    MustBeExecutedContextExplorer &Explorer, const Instruction *I)
    : Explorer(Explorer), CurInst(I) {
  reset(I);
}

void MustBeExecutedIterator::reset(const Instruction *I) {
  Visited.clear();
  resetInstruction(I);
}

void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
  CurInst = I;
  Head = Tail = nullptr;
  Visited.insert({I, ExplorationDirection::FORWARD});
  Visited.insert({I, ExplorationDirection::BACKWARD});
  if (Explorer.ExploreCFGForward)
    Head = I;
  if (Explorer.ExploreCFGBackward)
    Tail = I;
}

const Instruction *MustBeExecutedIterator::advance() {
  assert(CurInst && "Cannot advance an end iterator!");
  Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
  if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
    return Head;
  Head = nullptr;

  Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
  if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
    return Tail;
  Tail = nullptr;
  return nullptr;
}