Index: llvm/trunk/include/llvm/Analysis/MustExecute.h =================================================================== --- llvm/trunk/include/llvm/Analysis/MustExecute.h +++ llvm/trunk/include/llvm/Analysis/MustExecute.h @@ -7,10 +7,17 @@ //===----------------------------------------------------------------------===// /// \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 @@ -164,6 +171,280 @@ 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; + + /// 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 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 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 + InstructionIteratorMap; + + /// A unique end iterator. + MustBeExecutedIterator EndIterator; +}; + +} // namespace llvm #endif Index: llvm/trunk/include/llvm/Analysis/Passes.h =================================================================== --- llvm/trunk/include/llvm/Analysis/Passes.h +++ llvm/trunk/include/llvm/Analysis/Passes.h @@ -103,6 +103,13 @@ // FunctionPass *createMustExecutePrinter(); + //===--------------------------------------------------------------------===// + // + // createMustBeExecutedContextPrinter - This pass prints information about which + // instructions are guaranteed to execute together (run with -analyze). + // + ModulePass *createMustBeExecutedContextPrinter(); + } #endif Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -289,6 +289,7 @@ void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&); void initializeMustExecutePrinterPass(PassRegistry&); +void initializeMustBeExecutedContextPrinterPass(PassRegistry&); void initializeNameAnonGlobalLegacyPassPass(PassRegistry&); void initializeNaryReassociateLegacyPassPass(PassRegistry&); void initializeNewGVNLegacyPassPass(PassRegistry&); Index: llvm/trunk/include/llvm/LinkAllPasses.h =================================================================== --- llvm/trunk/include/llvm/LinkAllPasses.h +++ llvm/trunk/include/llvm/LinkAllPasses.h @@ -219,6 +219,7 @@ (void) llvm::createStraightLineStrengthReducePass(); (void) llvm::createMemDerefPrinter(); (void) llvm::createMustExecutePrinter(); + (void) llvm::createMustBeExecutedContextPrinter(); (void) llvm::createFloat2IntPass(); (void) llvm::createEliminateAvailableExternallyPass(); (void) llvm::createScalarizeMaskedMemIntrinPass(); Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -65,6 +65,7 @@ initializeModuleDebugInfoPrinterPass(Registry); initializeModuleSummaryIndexWrapperPassPass(Registry); initializeMustExecutePrinterPass(Registry); + initializeMustBeExecutedContextPrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializeOptimizationRemarkEmitterWrapperPassPass(Registry); initializePhiValuesWrapperPassPass(Registry); Index: llvm/trunk/lib/Analysis/MustExecute.cpp =================================================================== --- llvm/trunk/lib/Analysis/MustExecute.cpp +++ llvm/trunk/lib/Analysis/MustExecute.cpp @@ -7,6 +7,8 @@ //===----------------------------------------------------------------------===// #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" @@ -19,8 +21,11 @@ #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 & LoopSafetyInfo::getBlockColors() const { return BlockColors; @@ -306,6 +311,17 @@ } 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; @@ -320,6 +336,36 @@ 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 @@ -396,3 +442,75 @@ 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; +} Index: llvm/trunk/test/Analysis/MustExecute/must_be_executed_context.ll =================================================================== --- llvm/trunk/test/Analysis/MustExecute/must_be_executed_context.ll +++ llvm/trunk/test/Analysis/MustExecute/must_be_executed_context.ll @@ -0,0 +1,282 @@ +; 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