[MustExec] Add a generic "must-be-executed-context" explorer

[jdoerfert]

Summary

Given an instruction I, the MustBeExecutedContextExplorer allows to
easily traverse instructions that are guaranteed to be executed whenever
I is. For now, these instruction have to be statically "after" I, in
the same or different basic blocks.

[jdoerfert]

Use in ArgumentPromoton (fixed bug), add test, remove unused methods

[nikic]

I'm not sure I understand the design/purpose of this utility. As far as I can see, the main benefit this has over a standard guaranteed-to-transfer loop is that it will be able to continue into a unique successor BB. As most must-exec uses I've seen (including your ArgPromotion example, as well as attribute deduction uses) are interested in instructions that must-exec from entry, this will not happen for non-degenerate CFGs (where BBs have not been merged).

To get something more accurate than a guaranteed-to-transfer loop over the entry block for purposes like attribute deduction, a different interface would be needed that can handle multiple successor blocks. Basically a backwards propagation that discards facts if there's no guaranteed-transfer.

[jdoerfert]

Thanks for taking a look at this!

You are right, this is not what we actually want to do. What we want to do is shown in D64975, basically the final version of this which I haven't mentioned here before.
In a nutshell, the final version can find join points in the CFG (forward/backward direction), enter functions in the CallGraph (forward/backward direction), and use analyses to improve the result.
This commit introduces most of the boilerplate, the interface so we can start implementing users, and a testable subset of the rather large logic part.

In D65186#1605214, @nikic wrote:

I'm not sure I understand the design/purpose of this utility. As far as I can see, the main benefit this has over a standard guaranteed-to-transfer loop is that it will be able to continue into a unique successor BB. As most must-exec uses I've seen (including your ArgPromotion example, as well as attribute deduction uses) are interested in instructions that must-exec from entry, this will not happen for non-degenerate CFGs (where BBs have not been merged).

While beyond the point, the statement is not true. Take the loop header (=the loop body of "do-style" loops) as an example where the unique successor block is not mergeable with the predecessor.
(Basically anytime control merges in the unique successor we cannot merge.)

To get something more accurate than a guaranteed-to-transfer loop over the entry block for purposes like attribute deduction, a different interface would be needed that can handle multiple successor blocks. Basically a backwards propagation that discards facts if there's no guaranteed-transfer.

Site note: We do not only want to do entry block exploration but that is also beyond the point here (see D65402, turns out that patch only looks at entry blocks as a starting point but we should look at call sites as starting point as well).

[hfinkel]

I think that this looks fine, but it should have some direct tests. Either make an analysis that prints out things and then some lit tests, or, some unit tests.

llvm/include/llvm/Analysis/MustExecute.h

232 ↗

(On Diff #211408)

This comment, that all instructions A-E will be visited, seems contradicted by the table below (where starting at A visits {A, B} and starting at B visits {B} and so on).

250 ↗

(On Diff #211408)

Why does this not also include E and F?

[jdoerfert]

Add printer and explicit tests, fix examples in the comment

[jdoerfert]

Reverted the comments/examples in the comments back to their original form. Added the second more complex one.
The comment states that this might not be what you get (as it isn't now) but they explain the idea rather nicely.

I also added a printer pass and the tests from the example so we can "see" the progress.

llvm/include/llvm/Analysis/MustExecute.h

232 ↗

(On Diff #211408)

That was me changing the comment from the original to the less powerful striped down version even if that was actually not necessary. Will make it consistent again (see below).

250 ↗

(On Diff #211408)

In this patch it wouldn't derive this, though, maybe I should make the comment include them again (the original comment, and others I removed did contain E and F.

[hfinkel]

LGTM

llvm/trunk/include/llvm/Analysis/MustExecute.h

 //===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// Contains a collection of routines for determining if a given instruction is
-/// guaranteed to execute if a given point in control flow is reached.  The most
+/// guaranteed to execute if a given point in control flow is reached. The most
 /// common example is an instruction within a loop being provably executed if we
 /// branch to the header of it's containing loop.
 ///
+/// There are two interfaces available to determine if an instruction is
+/// executed once a given point in the control flow is reached:
+/// 1) A loop-centric one derived from LoopSafetyInfo.
+/// 2) A "must be executed context"-based one implemented in the
+///    MustBeExecutedContextExplorer.
+/// Please refer to the class comments for more information.
+///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
 #define LLVM_ANALYSIS_MUSTEXECUTE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
public:
   /// this removal.
   void removeInstruction(const Instruction *Inst);
 
   ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
 
   virtual ~ICFLoopSafetyInfo() {};
 };
 
+struct MustBeExecutedContextExplorer;
+
+/// Must be executed iterators visit stretches of instructions that are
+/// guaranteed to be executed together, potentially with other instruction
+/// executed in-between.
+///
+/// Given the following code, and assuming all statements are single
+/// instructions which transfer execution to the successor (see
+/// isGuaranteedToTransferExecutionToSuccessor), there are two possible
+/// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
+/// and E. If we start at C or D, we will visit all instructions A-E.
+///
+/// \code
+///   A;
+///   B;
+///   if (...) {
+///     C;
+///     D;
+///   }
+///   E;
+/// \endcode
+///
+///
+/// Below is the example extneded with instructions F and G. Now we assume F
+/// might not transfer execution to it's successor G. As a result we get the
+/// following visit sets:
+///
+/// Start Instruction   | Visit Set
+/// A                   | A, B,       E, F
+///    B                | A, B,       E, F
+///       C             | A, B, C, D, E, F
+///          D          | A, B, C, D, E, F
+///             E       | A, B,       E, F
+///                F    | A, B,       E, F
+///                   G | A, B,       E, F, G
+///
+///
+/// \code
+///   A;
+///   B;
+///   if (...) {
+///     C;
+///     D;
+///   }
+///   E;
+///   F;  // Might not transfer execution to its successor G.
+///   G;
+/// \endcode
+///
+///
+/// A more complex example involving conditionals, loops, break, and continue
+/// is shown below. We again assume all instructions will transmit control to
+/// the successor and we assume we can prove the inner loop to be finite. We
+/// omit non-trivial branch conditions as the exploration is oblivious to them.
+/// Constant branches are assumed to be unconditional in the CFG. The resulting
+/// visist sets are shown in the table below.
+///
+/// \code
+///   A;
+///   while (true) {
+///     B;
+///     if (...)
+///       C;
+///     if (...)
+///       continue;
+///     D;
+///     if (...)
+///       break;
+///     do {
+///       if (...)
+///         continue;
+///       E;
+///     } while (...);
+///     F;
+///   }
+///   G;
+/// \endcode
+///
+/// Start Instruction    | Visit Set
+/// A                    | A, B
+///    B                 | A, B
+///       C              | A, B, C
+///          D           | A, B,    D
+///             E        | A, B,    D, E, F
+///                F     | A, B,    D,    F
+///                   G  | A, B,    D,       G
+///
+///
+/// Note that the examples show optimal visist sets but not necessarily the ones
+/// derived by the explorer depending on the available CFG analyses (see
+/// MustBeExecutedContextExplorer). Also note that we, depending on the options,
+/// the visit set can contain instructions from other functions.
+struct MustBeExecutedIterator {
+  /// Type declarations that make his class an input iterator.
+  ///{
+  typedef const Instruction *value_type;
+  typedef std::ptrdiff_t difference_type;
+  typedef const Instruction **pointer;
+  typedef const Instruction *&reference;
+  typedef std::input_iterator_tag iterator_category;
+  ///}
+
+  using ExplorerTy = MustBeExecutedContextExplorer;
+
+  MustBeExecutedIterator(const MustBeExecutedIterator &Other)
+      : Visited(Other.Visited), Explorer(Other.Explorer),
+        CurInst(Other.CurInst) {}
+
+  MustBeExecutedIterator(MustBeExecutedIterator &&Other)
+      : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
+        CurInst(Other.CurInst) {}
+
+  MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
+    if (this != &Other) {
+      std::swap(Visited, Other.Visited);
+      std::swap(CurInst, Other.CurInst);
+    }
+    return *this;
+  }
+
+  ~MustBeExecutedIterator() {}
+
+  /// Pre- and post-increment operators.
+  ///{
+  MustBeExecutedIterator &operator++() {
+    CurInst = advance();
+    return *this;
   }
 
+  MustBeExecutedIterator operator++(int) {
+    MustBeExecutedIterator tmp(*this);
+    operator++();
+    return tmp;
+  }
+  ///}
+
+  /// Equality and inequality operators. Note that we ignore the history here.
+  ///{
+  bool operator==(const MustBeExecutedIterator &Other) const {
+    return CurInst == Other.CurInst;
+  }
+
+  bool operator!=(const MustBeExecutedIterator &Other) const {
+    return !(*this == Other);
+  }
+  ///}
+
+  /// Return the underlying instruction.
+  const Instruction *&operator*() { return CurInst; }
+  const Instruction *getCurrentInst() const { return CurInst; }
+
+  /// Return true if \p I was encountered by this iterator already.
+  bool count(const Instruction *I) const { return Visited.count(I); }
+
+private:
+  using VisitedSetTy = DenseSet<const Instruction *>;
+
+  /// Private constructors.
+  MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
+
+  /// Reset the iterator to its initial state pointing at \p I.
+  void reset(const Instruction *I);
+
+  /// Try to advance one of the underlying positions (Head or Tail).
+  ///
+  /// \return The next instruction in the must be executed context, or nullptr
+  ///         if none was found.
+  const Instruction *advance();
+
+  /// A set to track the visited instructions in order to deal with endless
+  /// loops and recursion.
+  VisitedSetTy Visited;
+
+  /// A reference to the explorer that created this iterator.
+  ExplorerTy &Explorer;
+
+  /// The instruction we are currently exposing to the user. There is always an
+  /// instruction that we know is executed with the given program point,
+  /// initially the program point itself.
+  const Instruction *CurInst;
+
+  friend struct MustBeExecutedContextExplorer;
+};
+
+/// A "must be executed context" for a given program point PP is the set of
+/// instructions, potentially before and after PP, that are executed always when
+/// PP is reached. The MustBeExecutedContextExplorer an interface to explore
+/// "must be executed contexts" in a module through the use of
+/// MustBeExecutedIterator.
+///
+/// The explorer exposes "must be executed iterators" that traverse the must be
+/// executed context. There is little information sharing between iterators as
+/// the expected use case involves few iterators for "far apart" instructions.
+/// If that changes, we should consider caching more intermediate results.
+struct MustBeExecutedContextExplorer {
+
+  /// In the description of the parameters we use PP to denote a program point
+  /// for which the must be executed context is explored, or put differently,
+  /// for which the MustBeExecutedIterator is created.
+  ///
+  /// \param ExploreInterBlock    Flag to indicate if instructions in blocks
+  ///                             other than the parent of PP should be
+  ///                             explored.
+  MustBeExecutedContextExplorer(bool ExploreInterBlock)
+      : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
+
+  /// Clean up the dynamically allocated iterators.
+  ~MustBeExecutedContextExplorer() {
+    DeleteContainerSeconds(InstructionIteratorMap);
+  }
+
+  /// Iterator-based interface. \see MustBeExecutedIterator.
+  ///{
+  using iterator = MustBeExecutedIterator;
+  using const_iterator = const MustBeExecutedIterator;
+
+  /// Return an iterator to explore the context around \p PP.
+  iterator &begin(const Instruction *PP) {
+    auto *&It = InstructionIteratorMap[PP];
+    if (!It)
+      It = new iterator(*this, PP);
+    return *It;
+  }
+
+  /// Return an iterator to explore the cached context around \p PP.
+  const_iterator &begin(const Instruction *PP) const {
+    return *InstructionIteratorMap.lookup(PP);
+  }
+
+  /// Return an universal end iterator.
+  ///{
+  iterator &end() { return EndIterator; }
+  iterator &end(const Instruction *) { return EndIterator; }
+
+  const_iterator &end() const { return EndIterator; }
+  const_iterator &end(const Instruction *) const { return EndIterator; }
+  ///}
+
+  /// Return an iterator range to explore the context around \p PP.
+  llvm::iterator_range<iterator> range(const Instruction *PP) {
+    return llvm::make_range(begin(PP), end(PP));
+  }
+
+  /// Return an iterator range to explore the cached context around \p PP.
+  llvm::iterator_range<const_iterator> range(const Instruction *PP) const {
+    return llvm::make_range(begin(PP), end(PP));
+  }
+  ///}
+
+  /// Return the next instruction that is guaranteed to be executed after \p PP.
+  ///
+  /// \param It              The iterator that is used to traverse the must be
+  ///                        executed context.
+  /// \param PP              The program point for which the next instruction
+  ///                        that is guaranteed to execute is determined.
+  const Instruction *
+  getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
+                                   const Instruction *PP);
+
+  /// Parameter that limit the performed exploration. See the constructor for
+  /// their meaning.
+  ///{
+  const bool ExploreInterBlock;
+  ///}
+
+private:
+  /// Map from instructions to associated must be executed iterators.
+  DenseMap<const Instruction *, MustBeExecutedIterator *>
+      InstructionIteratorMap;
+
+  /// A unique end iterator.
+  MustBeExecutedIterator EndIterator;
+};
+
+} // namespace llvm
+
 #endif

llvm/trunk/include/llvm/Analysis/Passes.h

namespace llvm {
   //===--------------------------------------------------------------------===//
   //
   // createMustExecutePrinter - This pass collects information about which
   // instructions within a loop are guaranteed to execute if the loop header is
   // entered and prints it with -analyze.
   //
   FunctionPass *createMustExecutePrinter();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createMustBeExecutedContextPrinter - This pass prints information about which
+  // instructions are guaranteed to execute together (run with -analyze).
+  //
+  ModulePass *createMustBeExecutedContextPrinter();
+
 }
 
 #endif

llvm/trunk/include/llvm/InitializePasses.h

 void initializeMemorySanitizerLegacyPassPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeMergeICmpsLegacyPassPass(PassRegistry &);
 void initializeMergedLoadStoreMotionLegacyPassPass(PassRegistry&);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&);
 void initializeMustExecutePrinterPass(PassRegistry&);
+void initializeMustBeExecutedContextPrinterPass(PassRegistry&);
 void initializeNameAnonGlobalLegacyPassPass(PassRegistry&);
 void initializeNaryReassociateLegacyPassPass(PassRegistry&);
 void initializeNewGVNLegacyPassPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
       (void) llvm::createSpeculativeExecutionPass();
       (void) llvm::createSpeculativeExecutionIfHasBranchDivergencePass();
       (void) llvm::createRewriteSymbolsPass();
       (void) llvm::createStraightLineStrengthReducePass();
       (void) llvm::createMemDerefPrinter();
       (void) llvm::createMustExecutePrinter();
+      (void) llvm::createMustBeExecutedContextPrinter();
       (void) llvm::createFloat2IntPass();
       (void) llvm::createEliminateAvailableExternallyPass();
       (void) llvm::createScalarizeMaskedMemIntrinPass();
       (void) llvm::createWarnMissedTransformationsPass();
       (void) llvm::createHardwareLoopsPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolutionWrapperPass();

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceWrapperPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeModuleSummaryIndexWrapperPassPass(Registry);
   initializeMustExecutePrinterPass(Registry);
+  initializeMustBeExecutedContextPrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
   initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
   initializePhiValuesWrapperPassPass(Registry);
   initializePostDominatorTreeWrapperPassPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);

llvm/trunk/lib/Analysis/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/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/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];
struct MustExecutePrinter : public FunctionPass {
     }
     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) {
+  MustBeExecutedContextExplorer Explorer(true);
+  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);
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;
 }
+
+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();
+  }
+
+  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) {
+  CurInst = I;
+  Visited.clear();
+  Visited.insert(I);
+}
+
+const Instruction *MustBeExecutedIterator::advance() {
+  assert(CurInst && "Cannot advance an end iterator!");
+  const Instruction *Next =
+      Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
+  if (Next && !Visited.insert(Next).second)
+    Next = nullptr;
+  return Next;
+}

llvm/trunk/test/Analysis/MustExecute/must_be_executed_context.ll

+; RUN: opt -print-mustexecute               -analyze 2>&1 < %s | FileCheck %s --check-prefix=ME
+; RUN: opt -print-must-be-executed-contexts -analyze 2>&1 < %s | FileCheck %s --check-prefix=MBEC
+;
+;    void simple_conditional(int c) {
+;      A();
+;      B();
+;      if (c) {
+;        C();
+;        D();
+;      }
+;      E();
+;      F();
+;      G();
+;    }
+;
+; Best result:
+; Start Instruction   | Visit Set
+; A                   | A, B,       E, F
+;    B                | A, B,       E, F
+;       C             | A, B, C, D, E, F
+;          D          | A, B, C, D, E, F
+;             E       | A, B,       E, F
+;                F    | A, B,       E, F
+;                   G | A, B,       E, F, G
+;
+; FIXME: We miss the B -> E and backward exploration.
+;
+; There are no loops so print-mustexec will not do anything.
+; ME-NOT: mustexec
+;
+define void @simple_conditional(i32 %arg) {
+bb:
+  call void @A()
+; MBEC:      -- Explore context of:   call void @A()
+; MBEC-NEXT:   [F: simple_conditional]   call void @A()
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NOT:    call
+
+  call void @B()
+; MBEC:      -- Explore context of:   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   call void @B()
+; MBEC-NEXT:   [F: simple_conditional]   %tmp = icmp eq i32 %arg, 0
+; MBEC-NEXT:   [F: simple_conditional]   br i1 %tmp, label %bb2, label %bb1
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: %tmp
+
+  %tmp = icmp eq i32 %arg, 0
+  br i1 %tmp, label %bb2, label %bb1
+
+bb1:                                              ; preds = %bb
+  call void @C()
+; MBEC:      -- Explore context of:   call void @C()
+; MBEC-NEXT:   [F: simple_conditional]   call void @C()
+; MBEC-NEXT:   [F: simple_conditional]   call void @D()
+; MBEC-NEXT:   [F: simple_conditional]   br label %bb2
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NOT:    call
+
+  call void @D()
+; MBEC:      -- Explore context of:   call void @D()
+; MBEC-NEXT:   [F: simple_conditional]   call void @D()
+; MBEC-NEXT:   [F: simple_conditional]   br label %bb2
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: br
+
+  br label %bb2
+
+bb2:                                              ; preds = %bb, %bb1
+  call void @E()
+; MBEC:      -- Explore context of:   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   call void @E()
+; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NOT:    call
+
+  call void @F() ; might not return!
+; MBEC:      -- Explore context of:   call void @F()
+; MBEC-NEXT:   [F: simple_conditional]   call void @F()
+; MBEC-NOT:    call
+
+  call void @G()
+; MBEC:      -- Explore context of:   call void @G()
+; MBEC-NEXT:   [F: simple_conditional]   call void @G()
+; MBEC-NEXT:   [F: simple_conditional]   ret void
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: ret
+
+  ret void
+}
+
+
+;    void complex_loops_and_control(int c, int d) {
+;      A();
+;      while (1) {
+;        B();
+;        if (++c == d)
+;          C();
+;        if (++c == d)
+;          continue;
+;        D();
+;        if (++c == d)
+;          break;
+;        do {
+;          if (++c == d)
+;            continue;
+;          E();
+;        } while (++c == d);
+;        F();
+;      }
+;      G();
+;    }
+;
+; Best result:
+; Start Instruction    | Visit Set
+; A                    | A, B
+;    B                 | A, B
+;       C              | A, B, C
+;          D           | A, B,    D
+;             E        | A, B,    D, E, F
+;                F     | A, B,    D,    F
+;                   G  | A, B,    D,       G
+;
+;
+; ME: define void @complex_loops_and_control
+define void @complex_loops_and_control(i32 %arg, i32 %arg1) {
+bb:
+  call void @A()
+; ME:     call void @A()
+; ME-NOT: mustexec
+; ME-NEXT: br
+; MBEC:      -- Explore context of:   call void @A()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @A()
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb2
+; MBEC-NEXT:   [F: complex_loops_and_control]   %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: br
+  br label %bb2
+
+bb2:                                              ; preds = %.backedge, %bb
+  %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ]
+  call void @B()
+; ME: call void @B() ; (mustexec in: bb2)
+; MBEC:      -- Explore context of:   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @B()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp = add nsw i32 %.0, 1
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp3 = icmp eq i32 %tmp, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp3, label %bb4, label %bb5
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: %tmp
+  %tmp = add nsw i32 %.0, 1
+  %tmp3 = icmp eq i32 %tmp, %arg1
+  br i1 %tmp3, label %bb4, label %bb5
+
+bb4:                                              ; preds = %bb2
+  call void @C()
+; ME: call void @C()
+; ME-NOT: mustexec
+; ME-NEXT: br
+; FIXME: Missing A and B (backward)
+; MBEC:      -- Explore context of:   call void @C()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @C()
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb5
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp6 = add nsw i32 %.0, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp7 = icmp eq i32 %tmp6, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp7, label %bb8, label %bb9
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: br
+  br label %bb5
+
+bb5:                                              ; preds = %bb4, %bb2
+  %tmp6 = add nsw i32 %.0, 2
+  %tmp7 = icmp eq i32 %tmp6, %arg1
+  br i1 %tmp7, label %bb8, label %bb9
+
+bb8:                                              ; preds = %bb5
+  br label %.backedge
+
+.backedge:                                        ; preds = %bb8, %bb22
+  %.0.be = phi i32 [ %tmp6, %bb8 ], [ %.lcssa, %bb22 ]
+  br label %bb2
+
+bb9:                                              ; preds = %bb5
+  call void @D()
+; ME: call void @D()
+; ME-NOT: mustexec
+; ME-NEXT: %tmp10
+; FIXME: Missing A and B (backward)
+; MBEC:      -- Explore context of:   call void @D()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @D()
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp10 = add nsw i32 %.0, 3
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp11 = icmp eq i32 %tmp10, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp11, label %bb12, label %bb13
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: %tmp10
+  %tmp10 = add nsw i32 %.0, 3
+  %tmp11 = icmp eq i32 %tmp10, %arg1
+  br i1 %tmp11, label %bb12, label %bb13
+
+bb12:                                             ; preds = %bb9
+  br label %bb23
+
+bb13:                                             ; preds = %bb9
+  br label %bb14
+
+bb14:                                             ; preds = %bb19, %bb13
+  %.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ]
+  %tmp15 = add nsw i32 %.1, 1
+  %tmp16 = icmp eq i32 %tmp15, %arg1
+  br i1 %tmp16, label %bb17, label %bb18
+
+bb17:                                             ; preds = %bb14
+  br label %bb19
+
+bb18:                                             ; preds = %bb14
+  call void @E()
+; ME: call void @E()
+; ME-NOT: mustexec
+; ME-NEXT: br
+; FIXME: Missing A, B, and D (backward), as well as F
+; MBEC:      -- Explore context of:   call void @E()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @E()
+; MBEC-NEXT:   [F: complex_loops_and_control]   br label %bb19
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp20 = add nsw i32 %.1, 2
+; MBEC-NEXT:   [F: complex_loops_and_control]   %tmp21 = icmp eq i32 %tmp20, %arg1
+; MBEC-NEXT:   [F: complex_loops_and_control]   br i1 %tmp21, label %bb14, label %bb22
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: br
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb17
+  %tmp20 = add nsw i32 %.1, 2
+  %tmp21 = icmp eq i32 %tmp20, %arg1
+  br i1 %tmp21, label %bb14, label %bb22
+
+bb22:                                             ; preds = %bb19
+  %.lcssa = phi i32 [ %tmp20, %bb19 ]
+  call void @F()
+; ME: call void @F()
+; ME-NOT: mustexec
+; ME-NEXT: br
+; FIXME: Missing A, B, and D (backward)
+; MBEC:      -- Explore context of:   call void @F()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @F()
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: br
+  br label %.backedge
+
+bb23:                                             ; preds = %bb12
+  call void @G()
+; ME: call void @G()
+; ME-NOT: mustexec
+; ME-NEXT: ret
+; FIXME: Missing A, B, and D (backward)
+; MBEC:      -- Explore context of:   call void @G()
+; MBEC-NEXT:   [F: complex_loops_and_control]   call void @G()
+; MBEC-NEXT:   [F: complex_loops_and_control]   ret void
+; MBEC-NOT:    call
+; MBEC:      -- Explore context of: ret
+  ret void
+}
+
+declare void @A() nounwind willreturn
+
+declare void @B() nounwind willreturn
+
+declare void @C() nounwind willreturn
+
+declare void @D() nounwind willreturn
+
+declare void @E() nounwind willreturn
+
+declare void @F() nounwind
+
+declare void @G() nounwind willreturn