[MustExec] Explorer-based LoopSafetyInfoInterface implementation

[jdoerfert]

Summary

This adds a MustBeExecutedContextExplorer-based LoopSafetyInfoInterface
implementation and adjust test coverage through the "-print-mustexecute"
tests. PR42682 is made explicit through FIXME's in the tests.

llvm/include/llvm/Analysis/MustExecute.h

private:
 
   /// Collection of all iterators in flight.
   SmallVector<MustBeExecutedIterator *, 16> Iterators;
 
   /// A unique end iterator.
   MustBeExecutedIterator EndIterator;
 };
 
+/// An implementation of the LoopSafetyInfoInterface using the
+/// MustBeExecutedContextExplorer to determine all reached instructions.
+template<bool TrackThrowingBBs = true, uint64_t MaxInstToExplore = 0>
+struct MustBeExecutedLoopSafetyInfo final : public LoopSafetyInfoInterface {
+
+  MustBeExecutedLoopSafetyInfo(const DominatorTree *DT = nullptr,
+                               const PostDominatorTree *PDT = nullptr,
+                               const LoopInfo *LI = nullptr)
+      : Explorer(true, true, false, true, DT, PDT, LI), It(nullptr) {}
+
+  /// See LoopSafetyInfo::bockMayThrow(...).
+  bool blockMayThrow(const BasicBlock *BB) const override {
+    assert(TrackThrowingBBs && "Object was created without throw tracking.");
+    return ThrowingBlocksMap.lookup(BB);
+  }
+
+  /// See LoopSafetyInfo::bockMayThrow(...).
+  bool anyBlockMayThrow() const override {
+    assert(TrackThrowingBBs && "Object was created without throw tracking.");
+    return ThrowingBlocksMap.lookup(nullptr);
+  };
+
+  /// See LoopSafetyInfo::computeLoopSafetyInfo(...).
+  void computeLoopSafetyInfo(const Loop *CurLoop) override;
+
+  /// See LoopSafetyInfo::isGuaranteedToExecute(...).
+  bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *,
+                             const Loop *CurLoop) const override {
+    return It && It->count(&Inst);
+  }
+
+  /// See LoopSafetyInfo::allLoopPathsLeadToBlock(...).
+  bool allLoopPathsLeadToBlock(const Loop *, const BasicBlock *BB,
+                               const DominatorTree *) const override {
+    assert(BB && "Expected a loop and a block!");
+    // We want to reach the first instruction in the block.
+    const Instruction &BBFirstInst = BB->front();
+    return It && It->count(&BBFirstInst);
+  }
+
+  /// See LoopSafetyInfo::insertInstructionBefore(...).
+  void insertInstructionBefore(const Instruction *NewI,
+                               const Instruction *PosI) override {
+    Explorer.insertInstructionBefore(NewI, PosI);
+  }
+
+  /// See LoopSafetyInfo::insertInstructionAfter(...).
+  void insertInstructionAfter(const Instruction *NewI,
+                              const Instruction *PosI) override {
+    Explorer.insertInstructionAfter(NewI, PosI);
+  }
+
+  /// See LoopSafetyInfo::removeInstruction(...).
+  void removeInstruction(const Instruction *Inst) override {
+    Explorer.removeInstruction(Inst);
+  }
+
+private:
+  MustBeExecutedContextExplorer Explorer;
+  MustBeExecutedContextExplorer::iterator *It;
+  DenseMap<const BasicBlock *, bool> ThrowingBlocksMap;
+};
+
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/MustExecute.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "must-execute"
 
+static cl::opt<bool> MustExecutePrinterUseExplorer(
+    "print-mustexecute-use-explorer", cl::Hidden, cl::init(false),
+    cl::desc(
+        "Use 'must-be-executed-context' explorer for the mustexecute printer"));
+
 const DenseMap<BasicBlock *, ColorVector> &
 LoopSafetyInfo::getBlockColors() const {
   return BlockColors;
 }
 
 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
   ColorVector &ColorsForNewBlock = BlockColors[New];
   ColorVector &ColorsForOldBlock = BlockColors[Old];

 
 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)) {
+  MustExecuteAnnotatedWriter(const Function &F, DominatorTree &DT,
+                             LoopInfo &LI) {
+    if (MustExecutePrinterUseExplorer) {
+      MustBeExecutedLoopSafetyInfo<false> MBELSI(&DT, nullptr, &LI);
+
+      SmallVector<Loop *, 16> Loops;
+      Loops.append(LI.begin(), LI.end());
+      // Perform the isGuaranteedToExecute check loop by loop to reuse cached
+      // results computed by computeLoopSafetyInfo.
+      while (!Loops.empty()) {
+        Loop *L = Loops.pop_back_val();
+        MBELSI.computeLoopSafetyInfo(L);
+        for (BasicBlock *BB : L->blocks())
+          for (Instruction &I : *BB)
+            if (MBELSI.isGuaranteedToExecute(I, &DT, L))
+              MustExec[&I].push_back(L);
+        Loops.append(L->begin(), L->end());
+      }
+    } else {
+
+      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))
+    if (!MustExec.count(&V)) {
+      OS << " ; no mustexec loop";
       return;
+    }
 
     const auto &Loops = MustExec.lookup(&V);
     const auto NumLoops = Loops.size();
     if (NumLoops > 1)
       OS << " ; (mustexec in " << NumLoops << " loops: ";
     else
       OS << " ; (mustexec in: ";
 
void MustBeExecutedContextExplorer::removeInstruction(const Instruction *I) {
   InstructionIteratorMap.erase(I);
   BlockTransferMap.erase(I->getParent());
   FunctionExitJoinPointMap.erase(I->getFunction());
   for (auto &It : InstructionIteratorMap) {
     It.getSecond()->Visited->erase({I, ExplorationDirection::FORWARD});
     It.getSecond()->Visited->erase({I, ExplorationDirection::BACKWARD});
   }
 }
+
+template <bool TrackThrowingBBs, uint64_t MaxInstToExplore>
+void MustBeExecutedLoopSafetyInfo<
+    TrackThrowingBBs, MaxInstToExplore>::computeLoopSafetyInfo(const Loop *L) {
+  assert(L && "Expected a loop!");
+  LLVM_DEBUG(dbgs() << "Compute loop safety info for " << L->getName()
+                    << "\n";);
+
+  const Instruction &LoopFirstInst = L->getHeader()->front();
+  It = &Explorer.begin(&LoopFirstInst);
+
+  // Explore the context until we run out of the loop.
+  // TODO: This might be a case where we want to guide the exploraiton.
+  uint64_t InstExplorer = 0;
+  while (const Instruction *I = **It) {
+    // This assumes we explore the CFG "forward" first and the explorer is not
+    // interprocedural.
+    if (!L->contains(I))
+      break;
+    ++(*It);
+    if (MaxInstToExplore && ++InstExplorer >= MaxInstToExplore)
+      break;
+  }
+  LLVM_DEBUG(dbgs() << "done exploring the loop\n");
+
+  if (TrackThrowingBBs) {
+    // Fill the ThrowingBlocksMap with basic block -> may throw information.
+    bool AnyMayThrow = false;
+    for (const BasicBlock *BB : L->blocks()) {
+      bool BBMayThrow = false;
+      for (const Instruction &I : *BB)
+        if ((BBMayThrow = I.mayThrow()))
+          break;
+      AnyMayThrow |= BBMayThrow;
+      ThrowingBlocksMap[BB] = BBMayThrow;
+    }
+
+    // Use nullptr as key for "any" block.
+    ThrowingBlocksMap[nullptr] = AnyMayThrow;
+  }
+}
+

llvm/test/Analysis/MustExecute/const-cond.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s
+; RUN: opt -disable-output -print-mustexecute -print-mustexecute-use-explorer %s 2>&1 | FileCheck %s
 
 ; In general the CFG below is easily simplified but this is useful for
 ; pass ordering issue elimination.
 define i1 @const_cond(i32 %high) {
+;
 ; CHECK-LABEL: @const_cond(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
+; CHECK-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; CHECK:       loop: ; preds = [[BACKEDGE:%.*]], [[ENTRY:%.*]]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ] ; (mustexec in: loop)
 ; CHECK-NEXT:    br i1 true, label [[NEXT:%.*]], label [[NEVER1:%.*]] ; (mustexec in: loop)
-; CHECK:       next:
+; CHECK:       next: ; preds = [[LOOP]]
 ; CHECK-NEXT:    br i1 false, label [[NEVER2:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
-; CHECK:       backedge:
+; CHECK:       backedge: ; preds = [[NEXT]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; (mustexec in: loop)
 ; CHECK-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; (mustexec in: loop)
 ; CHECK-NEXT:    br i1 [[EXIT_TEST]], label [[LOOP]], label [[EXIT:%.*]] ; (mustexec in: loop)
-; CHECK:       exit:
-; CHECK-NEXT:    ret i1 false
-; CHECK:       never1:
-; CHECK-NEXT:    unreachable
-; CHECK:       never2:
-; CHECK-NEXT:    unreachable
+; CHECK:       exit: ; preds = [[BACKEDGE]]
+; CHECK-NEXT:    ret i1 false ; no mustexec loop
+; CHECK:       never1: ; preds = [[LOOP]]
+; CHECK-NEXT:    unreachable ; no mustexec loop
+; CHECK:       never2: ; preds = [[NEXT]]
+; CHECK-NEXT:    unreachable ; no mustexec loop
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   br i1 true, label %next, label %never1
 next:

llvm/test/Analysis/MustExecute/infinite_loops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s
+; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s --check-prefixes=BOTH,SLSI
+; RUN: opt -disable-output -print-mustexecute -print-mustexecute-use-explorer %s 2>&1 | FileCheck %s --check-prefixes=BOTH,ELSI
 
 ; Infinite loop.
 ; Make sure that the backedge is mustexec.
 define void @test_no_exit_block(i1 %cond, i32 %a, i32 %b) {
-; CHECK-LABEL: @test_no_exit_block(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
-; CHECK:       maybe_taken:
-; CHECK-NOT:   mustexec
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
-; CHECK-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
+; BOTH-LABEL: @test_no_exit_block(
+; BOTH-NEXT:  entry:
+; BOTH-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; BOTH:       loop: ; preds = [[BACKEDGE:%.*]], [[ENTRY:%.*]]
+; BOTH-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ] ; (mustexec in: loop)
+; BOTH-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
+; BOTH:       maybe_taken: ; preds = [[LOOP]]
+; BOTH-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; no mustexec loop
+; BOTH-NEXT:    br label [[BACKEDGE]] ; no mustexec loop
+; BOTH:       backedge: ; preds = [[MAYBE_TAKEN]], [[LOOP]]
+; BOTH-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
+; BOTH-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   br i1 %cond, label %maybe_taken, label %backedge
 
 maybe_taken:
   %div = sdiv i32 %a, %b
   br label %backedge
 
 backedge:
   %iv.next = add i32 %iv, 1
   br label %loop
 }
 
 ; Unlike the test before, we can say that backedge is mustexec, which is the
 ; correct behavior.
 define void @test_impossible_exit_on_latch(i1 %cond, i32 %a, i32 %b) {
-; CHECK-LABEL: @test_impossible_exit_on_latch(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
-; CHECK:       maybe_taken:
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
-; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT:%.*]] ; (mustexec in: loop)
-; CHECK:       exit:
-; CHECK-NEXT:    ret void
+;
+; BOTH-LABEL: @test_impossible_exit_on_latch(
+; BOTH-NEXT:  entry:
+; BOTH-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; BOTH:       loop: ; preds = [[BACKEDGE:%.*]], [[ENTRY:%.*]]
+; BOTH-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ] ; (mustexec in: loop)
+; BOTH-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
+; BOTH:       maybe_taken: ; preds = [[LOOP]]
+; BOTH-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; no mustexec loop
+; BOTH-NEXT:    br label [[BACKEDGE]] ; no mustexec loop
+; BOTH:       backedge: ; preds = [[MAYBE_TAKEN]], [[LOOP]]
+; BOTH-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
+; BOTH-NEXT:    br i1 true, label [[LOOP]], label [[EXIT:%.*]] ; (mustexec in: loop)
+; BOTH:       exit: ; preds = [[BACKEDGE]]
+; BOTH-NEXT:    ret void ; no mustexec loop
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   br i1 %cond, label %maybe_taken, label %backedge
 
 maybe_taken:
   %div = sdiv i32 %a, %b
   br label %backedge
 
 backedge:
   %iv.next = add i32 %iv, 1
   br i1 true, label %loop, label %exit
 
 exit:
   ret void
 }
 
 ; Make sure that sdiv is NOT marked as mustexec.
 define void @test_impossible_exit_in_untaken_block(i1 %cond, i32 %a, i32 %b, i32* %p) {
-; CHECK-LABEL: @test_impossible_exit_in_untaken_block(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP:%.*]]
-; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
-; CHECK:       maybe_taken:
-; CHECK-NOT:   mustexec
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    store i32 [[DIV]], i32* [[P:%.*]]
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
-; CHECK-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
-; CHECK:       exit:
-; CHECK-NEXT:    ret void
+; SLSI-LABEL: @test_impossible_exit_in_untaken_block(
+; SLSI-NEXT:  entry:
+; SLSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; SLSI:       loop: ; preds = [[BACKEDGE:%.*]], [[ENTRY:%.*]]
+; SLSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ] ; (mustexec in: loop)
+; SLSI-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
+; SLSI:       maybe_taken: ; preds = [[LOOP]]
+; SLSI-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; no mustexec loop
+; SLSI-NEXT:    store i32 [[DIV]], i32* [[P:%.*]] ; no mustexec loop
+; SLSI-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]] ; no mustexec loop
+; SLSI:       backedge: ; preds = [[MAYBE_TAKEN]], [[LOOP]]
+; SLSI-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop)
+; SLSI-NEXT:    br label [[LOOP]] ; (mustexec in: loop)
+; SLSI:       exit: ; preds = [[MAYBE_TAKEN]]
+; SLSI-NEXT:    ret void ; no mustexec loop
+;
+; ELSI-LABEL: @test_impossible_exit_in_untaken_block(
+; ELSI-NEXT:  entry:
+; ELSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; ELSI:       loop: ; preds = [[BACKEDGE:%.*]], [[ENTRY:%.*]]
+; ELSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE]] ] ; (mustexec in: loop)
+; ELSI-NEXT:    br i1 [[COND:%.*]], label [[MAYBE_TAKEN:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
+; ELSI:       maybe_taken: ; preds = [[LOOP]]
+; ELSI-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; no mustexec loop
+; ELSI-NEXT:    store i32 [[DIV]], i32* [[P:%.*]] ; no mustexec loop
+; ELSI-NEXT:    br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]] ; no mustexec loop
+; ELSI:       backedge: ; preds = [[MAYBE_TAKEN]], [[LOOP]]
+; ELSI-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1 ; no mustexec loop
+; ELSI-NEXT:    br label [[LOOP]] ; no mustexec loop
+; ELSI:       exit: ; preds = [[MAYBE_TAKEN]]
+; ELSI-NEXT:    ret void ; no mustexec loop
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   br i1 %cond, label %maybe_taken, label %backedge
 

llvm/test/Analysis/MustExecute/loop-header.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s
+; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s --check-prefixes=BOTH,SLSI
+; RUN: opt -disable-output -print-mustexecute -print-mustexecute-use-explorer %s 2>&1 | FileCheck %s --check-prefixes=BOTH,ELSI
 
 define i1 @header_with_icf(i32* noalias %p, i32 %high) {
-; CHECK-LABEL: @header_with_icf(
-; CHECK-LABEL:       loop:
-; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] ; (mustexec in: loop)
-; CHECK:          %v = load i32, i32* %p ; (mustexec in: loop)
-; CHECK:          call void @maythrow_and_use(i32 %v) ; (mustexec in: loop)
-; CHECK-NOT: mustexec
-
+;
+; BOTH-LABEL: @header_with_icf(
+; BOTH-NEXT:  entry:
+; BOTH-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; BOTH:       loop: ; preds = [[LOOP]], [[ENTRY:%.*]]
+; BOTH-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] ; (mustexec in: loop)
+; BOTH-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in: loop)
+; BOTH-NEXT:    call void @maythrow_and_use(i32 [[V]]) ; (mustexec in: loop)
+; BOTH-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; no mustexec loop
+; BOTH-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; no mustexec loop
+; BOTH-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; no mustexec loop
+; BOTH:       exit: ; preds = [[LOOP]]
+; BOTH-NEXT:    ret i1 false ; no mustexec loop
+;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %loop]
   %v = load i32, i32* %p
   call void @maythrow_and_use(i32 %v)
   %iv.next = add nsw nuw i32 %iv, 1
   %exit.test = icmp slt i32 %iv, %high
   br i1 %exit.test, label %exit, label %loop
 
 exit:
   ret i1 false
 }
 
 define i1 @split_header(i32* noalias %p, i32 %high) {
-; CHECK-LABEL: @split_header(
-; CHECK-LABEL:       loop:
-; CHECK:          %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ]  ; (mustexec in: loop)
-; CHECK:          %v = load i32, i32* %p ; (mustexec in: loop)
-; CHECK:          br label %next ; (mustexec in: loop)
-; CHECK-NOT: mustexec
+;
+; BOTH-LABEL: @split_header(
+; BOTH-NEXT:  entry:
+; BOTH-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; BOTH:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; BOTH-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; BOTH-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in: loop)
+; BOTH-NEXT:    br label [[NEXT]] ; (mustexec in: loop)
+; BOTH:       next: ; preds = [[LOOP]]
+; SLSI-NEXT:    call void @maythrow_and_use(i32 [[V]]) ; no mustexec loop
+; ELSI-NEXT:    call void @maythrow_and_use(i32 [[V]]) ; (mustexec in: loop)
+; BOTH-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; no mustexec loop
+; BOTH-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; no mustexec loop
+; BOTH-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; no mustexec loop
+; BOTH:       exit: ; preds = [[NEXT]]
+; BOTH-NEXT:    ret i1 false ; no mustexec loop
+;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   %v = load i32, i32* %p
   br label %next
 next:
   call void @maythrow_and_use(i32 %v)
   %iv.next = add nsw nuw i32 %iv, 1
   %exit.test = icmp slt i32 %iv, %high
   br i1 %exit.test, label %exit, label %loop
 
 exit:
   ret i1 false
 }
 
 ; FIXME: everything in inner loop header should be must execute
 ; for outer as well
 define i1 @nested(i32* noalias %p, i32 %high) {
-; CHECK-LABEL: @nested
-; CHECK-LABEL: loop:                                             ; preds = %next
-; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
-; CHECK:         br label %inner_loop ; (mustexec in: loop)
-; CHECK-LABEL: inner_loop:
-; CHECK:         %v = load i32, i32* %p ; (mustexec in: inner_loop)
-; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in: inner_loop)
-; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in: inner_loop)
-; CHECK-NOT: mustexec
-
+;
+; SLSI-LABEL: @nested(
+; SLSI-NEXT:  entry:
+; SLSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; SLSI:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; SLSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; SLSI-NEXT:    br label [[INNER_LOOP:%.*]] ; (mustexec in: loop)
+; SLSI:       inner_loop: ; preds = [[INNER_LOOP]], [[LOOP]]
+; SLSI-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in: inner_loop)
+; SLSI-NEXT:    [[INNER_TEST:%.*]] = icmp eq i32 [[V]], 0 ; (mustexec in: inner_loop)
+; SLSI-NEXT:    br i1 [[INNER_TEST]], label [[INNER_LOOP]], label [[NEXT]] ; (mustexec in: inner_loop)
+; SLSI:       next: ; preds = [[INNER_LOOP]]
+; SLSI-NEXT:    call void @maythrow_and_use(i32 [[V]]) ; no mustexec loop
+; SLSI-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; no mustexec loop
+; SLSI-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; no mustexec loop
+; SLSI-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; no mustexec loop
+; SLSI:       exit: ; preds = [[NEXT]]
+; SLSI-NEXT:    ret i1 false ; no mustexec loop
+;
+; ELSI-LABEL: @nested(
+; ELSI-NEXT:  entry:
+; ELSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; ELSI:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; ELSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; ELSI-NEXT:    br label [[INNER_LOOP:%.*]] ; (mustexec in: loop)
+; ELSI:       inner_loop: ; preds = [[INNER_LOOP]], [[LOOP]]
+; ELSI-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI-NEXT:    [[INNER_TEST:%.*]] = icmp eq i32 [[V]], 0 ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI-NEXT:    br i1 [[INNER_TEST]], label [[INNER_LOOP]], label [[NEXT]] ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI:       next: ; preds = [[INNER_LOOP]]
+; ELSI-NEXT:    call void @maythrow_and_use(i32 [[V]]) ; no mustexec loop
+; ELSI-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; no mustexec loop
+; ELSI-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; no mustexec loop
+; ELSI-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; no mustexec loop
+; ELSI:       exit: ; preds = [[NEXT]]
+; ELSI-NEXT:    ret i1 false ; no mustexec loop
+;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   br label %inner_loop
-  
 inner_loop:
   %v = load i32, i32* %p
   %inner.test = icmp eq i32 %v, 0
   br i1 %inner.test, label %inner_loop, label %next
 
 next:
   call void @maythrow_and_use(i32 %v)
   %iv.next = add nsw nuw i32 %iv, 1
   %exit.test = icmp slt i32 %iv, %high
   br i1 %exit.test, label %exit, label %loop
 
 exit:
   ret i1 false
 }
 
 define i1 @nested_no_throw(i32* noalias %p, i32 %high) {
-; CHECK-LABEL: @nested_no_throw
-; CHECK-LABEL: loop:                                             ; preds = %next
-; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
-; CHECK:         br label %inner_loop ; (mustexec in: loop)
-; CHECK-LABEL: inner_loop:
-; CHECK:         %v = load i32, i32* %p ; (mustexec in 2 loops: inner_loop, loop)
-; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in 2 loops: inner_loop, loop)
-; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in 2 loops: inner_loop, loop)
-; CHECK-LABEL: next:
-; CHECK:         %iv.next = add nuw nsw i32 %iv, 1 ; (mustexec in: loop)
-; CHECK:         %exit.test = icmp slt i32 %iv, %high ; (mustexec in: loop)
-; CHECK:         br i1 %exit.test, label %exit, label %loop ; (mustexec in: loop)
-
+;
+; SLSI-LABEL: @nested_no_throw(
+; SLSI-NEXT:  entry:
+; SLSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; SLSI:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; SLSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; SLSI-NEXT:    br label [[INNER_LOOP:%.*]] ; (mustexec in: loop)
+; SLSI:       inner_loop: ; preds = [[INNER_LOOP]], [[LOOP]]
+; SLSI-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in 2 loops: inner_loop, loop)
+; SLSI-NEXT:    store i32 1, i32* [[P]] ; (mustexec in 2 loops: inner_loop, loop)
+; SLSI-NEXT:    [[INNER_TEST:%.*]] = icmp eq i32 [[V]], 0 ; (mustexec in 2 loops: inner_loop, loop)
+; SLSI-NEXT:    br i1 [[INNER_TEST]], label [[INNER_LOOP]], label [[NEXT]] ; (mustexec in 2 loops: inner_loop, loop)
+; SLSI:       next: ; preds = [[INNER_LOOP]]
+; FIXME the following three lines are not correct ( https://llvm.org/PR42682 )
+; SLSI-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; (mustexec in: loop)
+; SLSI-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; (mustexec in: loop)
+; SLSI-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; (mustexec in: loop)
+; SLSI:       exit: ; preds = [[NEXT]]
+; SLSI-NEXT:    ret i1 false ; no mustexec loop
+;
+; ELSI-LABEL: @nested_no_throw(
+; ELSI-NEXT:  entry:
+; ELSI-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; ELSI:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; ELSI-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; ELSI-NEXT:    br label [[INNER_LOOP:%.*]] ; (mustexec in: loop)
+; ELSI:       inner_loop: ; preds = [[INNER_LOOP]], [[LOOP]]
+; ELSI-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI-NEXT:    store i32 1, i32* [[P]] ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI-NEXT:    [[INNER_TEST:%.*]] = icmp eq i32 [[V]], 0 ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI-NEXT:    br i1 [[INNER_TEST]], label [[INNER_LOOP]], label [[NEXT]] ; (mustexec in 2 loops: loop, inner_loop)
+; ELSI:       next: ; preds = [[INNER_LOOP]]
+; ELSI-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; no mustexec loop
+; ELSI-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; no mustexec loop
+; ELSI-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; no mustexec loop
+; ELSI:       exit: ; preds = [[NEXT]]
+; ELSI-NEXT:    ret i1 false ; no mustexec loop
+;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   br label %inner_loop
 
 inner_loop:
   %v = load i32, i32* %p
+  store i32 1, i32* %p
   %inner.test = icmp eq i32 %v, 0
   br i1 %inner.test, label %inner_loop, label %next
 
 next:
   %iv.next = add nsw nuw i32 %iv, 1
   %exit.test = icmp slt i32 %iv, %high
   br i1 %exit.test, label %exit, label %loop
 
 exit:
   ret i1 false
 }
 
 ; Since all the instructions in the loop dominate the only exit
 ; and there's no implicit control flow in the loop, all must execute
 ; FIXME: handled by loop safety info, test it
 define i1 @nothrow_loop(i32* noalias %p, i32 %high) {
-; CHECK-LABEL: @nothrow_loop(
-; CHECK-LABEL:  loop:
-; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
-; CHECK:          br label %next ; (mustexec in: loop)
-; CHECK-LABEL: next:
-; CHECK:          %v = load i32, i32* %p ; (mustexec in: loop)
-; CHECK:          %iv.next = add nuw nsw i32 %iv, 1 ; (mustexec in: loop)
-; CHECK:          %exit.test = icmp slt i32 %iv, %high ; (mustexec in: loop)
-; CHECK:          br i1 %exit.test, label %exit, label %loop ; (mustexec in: loop)
-; CHECK-NOT: mustexec
-
+;
+; BOTH-LABEL: @nothrow_loop(
+; BOTH-NEXT:  entry:
+; BOTH-NEXT:    br label [[LOOP:%.*]] ; no mustexec loop
+; BOTH:       loop: ; preds = [[NEXT:%.*]], [[ENTRY:%.*]]
+; BOTH-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[NEXT]] ] ; (mustexec in: loop)
+; BOTH-NEXT:    br label [[NEXT]] ; (mustexec in: loop)
+; BOTH:       next: ; preds = [[LOOP]]
+; BOTH-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]] ; (mustexec in: loop)
+; BOTH-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; (mustexec in: loop)
+; BOTH-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; (mustexec in: loop)
+; BOTH-NEXT:    br i1 [[EXIT_TEST]], label [[EXIT:%.*]], label [[LOOP]] ; (mustexec in: loop)
+; BOTH:       exit: ; preds = [[NEXT]]
+; BOTH-NEXT:    ret i1 false ; no mustexec loop
+;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   br label %next
 next:
   %v = load i32, i32* %p

llvm/test/Analysis/MustExecute/must_execute_context_explorer.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s --check-prefixes=BOTH,SLSI
+; RUN: opt -disable-output -print-mustexecute -print-mustexecute-use-explorer %s 2>&1 | FileCheck %s --check-prefixes=BOTH,ELSI
+
+; int A, B, C, D, E, F, G;
+;
+; void foo(int c) {
+;   A = 0;
+;   while (1) {
+;     B = 1;
+;     if (c)
+;       C = 2;
+;     if (c)       // endless for c != 0
+;       continue;
+;     D = 3;
+;     if (--c)
+;       break;
+;     do {
+;       if (c++)
+;         continue;
+;       E = 4;
+;     } while (c++);
+;     F = 5;
+;   }
+;   G = 6;
+; }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@A = common global i32 0, align 4
+@B = common global i32 0, align 4
+@C = common global i32 0, align 4
+@D = common global i32 0, align 4
+@E = common global i32 0, align 4
+@F = common global i32 0, align 4
+@G = common global i32 0, align 4
+
+define void @foo(i32 %arg) {
+; SLSI-LABEL: @foo(
+; SLSI-NEXT:  BB_A:
+; SLSI-NEXT:    store i32 0, i32* @A, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[LOOPOUTER:%.*]] ; no mustexec loop
+; SLSI:       LoopOuter: ; preds = [[BB_F:%.*]], [[BB10:%.*]], [[BB_A:%.*]]
+; SLSI-NEXT:    [[DOT0:%.*]] = phi i32 [ [[ARG:%.*]], [[BB_A]] ], [ [[TMP29:%.*]], [[BB_F]] ], [ [[ARG]], [[BB10]] ] ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    store i32 1, i32* @B, align 4 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[ARG]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br label [[BB10]] ; (mustexec in: LoopOuter)
+; SLSI:       bb10: ; preds = [[LOOPOUTER]]
+; SLSI-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[ARG]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br i1 [[TMP12]], label [[LOOPOUTER]], label [[BB_D:%.*]] ; (mustexec in: LoopOuter)
+; SLSI:       BB_D: ; preds = [[BB10]]
+; FIXME the following four lines are not correct ( https://llvm.org/PR42682 )
+; SLSI-NEXT:    store i32 3, i32* @D, align 4 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP17:%.*]] = add nsw i32 [[DOT0]], -1 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP18:%.*]] = icmp ne i32 [[TMP17]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br i1 [[TMP18]], label [[BB_G:%.*]], label [[LOOPINNER:%.*]] ; (mustexec in: LoopOuter)
+; SLSI:       LoopInner: ; preds = [[BB22:%.*]], [[BB_D]]
+; SLSI-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP29]], [[BB22]] ], [ [[TMP17]], [[BB_D]] ] ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP22:%.*]] = add nsw i32 [[DOT1]], 1 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP23:%.*]] = icmp ne i32 [[DOT1]], 0 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    br i1 [[TMP23]], label [[BB22]], label [[BB_E:%.*]] ; (mustexec in: LoopInner)
+; SLSI:       BB_E: ; preds = [[LOOPINNER]]
+; SLSI-NEXT:    store i32 4, i32* @E, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[BB22]] ; no mustexec loop
+; SLSI:       bb22: ; preds = [[BB_E]], [[LOOPINNER]]
+; SLSI-NEXT:    [[TMP29]] = add nsw i32 [[TMP22]], 1 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP30:%.*]] = icmp ne i32 [[TMP22]], 0 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    br i1 [[TMP30]], label [[LOOPINNER]], label [[BB_F]] ; (mustexec in: LoopInner)
+; SLSI:       BB_F: ; preds = [[BB22]]
+; SLSI-NEXT:    store i32 5, i32* @F, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[LOOPOUTER]] ; no mustexec loop
+; SLSI:       BB_G: ; preds = [[BB_D]]
+; SLSI-NEXT:    store i32 6, i32* @G, align 4 ; no mustexec loop
+; SLSI-NEXT:    ret void ; no mustexec loop
+;
+; ELSI-LABEL: @foo(
+; ELSI-NEXT:  BB_A:
+; ELSI-NEXT:    store i32 0, i32* @A, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[LOOPOUTER:%.*]] ; no mustexec loop
+; ELSI:       LoopOuter: ; preds = [[BB_F:%.*]], [[BB10:%.*]], [[BB_A:%.*]]
+; ELSI-NEXT:    [[DOT0:%.*]] = phi i32 [ [[ARG:%.*]], [[BB_A]] ], [ [[TMP29:%.*]], [[BB_F]] ], [ [[ARG]], [[BB10]] ] ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    store i32 1, i32* @B, align 4 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[ARG]], 0 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    br label [[BB10]] ; (mustexec in: LoopOuter)
+; ELSI:       bb10: ; preds = [[LOOPOUTER]]
+; ELSI-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[ARG]], 0 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    br i1 [[TMP12]], label [[LOOPOUTER]], label [[BB_D:%.*]] ; (mustexec in: LoopOuter)
+; ELSI:       BB_D: ; preds = [[BB10]]
+; ELSI-NEXT:    store i32 3, i32* @D, align 4 ; no mustexec loop
+; ELSI-NEXT:    [[TMP17:%.*]] = add nsw i32 [[DOT0]], -1 ; no mustexec loop
+; ELSI-NEXT:    [[TMP18:%.*]] = icmp ne i32 [[TMP17]], 0 ; no mustexec loop
+; ELSI-NEXT:    br i1 [[TMP18]], label [[BB_G:%.*]], label [[LOOPINNER:%.*]] ; no mustexec loop
+; ELSI:       LoopInner: ; preds = [[BB22:%.*]], [[BB_D]]
+; ELSI-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP29]], [[BB22]] ], [ [[TMP17]], [[BB_D]] ] ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP22:%.*]] = add nsw i32 [[DOT1]], 1 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP23:%.*]] = icmp ne i32 [[DOT1]], 0 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    br i1 [[TMP23]], label [[BB22]], label [[BB_E:%.*]] ; (mustexec in: LoopInner)
+; ELSI:       BB_E: ; preds = [[LOOPINNER]]
+; ELSI-NEXT:    store i32 4, i32* @E, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[BB22]] ; no mustexec loop
+; ELSI:       bb22: ; preds = [[BB_E]], [[LOOPINNER]]
+; ELSI-NEXT:    [[TMP29]] = add nsw i32 [[TMP22]], 1 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP30:%.*]] = icmp ne i32 [[TMP22]], 0 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    br i1 [[TMP30]], label [[LOOPINNER]], label [[BB_F]] ; (mustexec in: LoopInner)
+; ELSI:       BB_F: ; preds = [[BB22]]
+; ELSI-NEXT:    store i32 5, i32* @F, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[LOOPOUTER]] ; no mustexec loop
+; ELSI:       BB_G: ; preds = [[BB_D]]
+; ELSI-NEXT:    store i32 6, i32* @G, align 4 ; no mustexec loop
+; ELSI-NEXT:    ret void ; no mustexec loop
+;
+BB_A:
+  store i32 0, i32* @A, align 4
+  br label %LoopOuter
+
+LoopOuter:                                        ; preds = %bb10, %BB_F, %BB_A
+  %.0 = phi i32 [ %arg, %BB_A ], [ %tmp29, %BB_F ], [ %arg, %bb10 ]
+  store i32 1, i32* @B, align 4
+  %tmp6 = icmp ne i32 %arg, 0
+  br label %bb10
+
+bb10:                                             ; preds = %BB_C, %LoopOuter
+  %tmp12 = icmp ne i32 %arg, 0
+  br i1 %tmp12, label %LoopOuter, label %BB_D
+
+BB_D:                                             ; preds = %bb10
+  store i32 3, i32* @D, align 4
+  %tmp17 = add nsw i32 %.0, -1
+  %tmp18 = icmp ne i32 %tmp17, 0
+  br i1 %tmp18, label %BB_G, label %LoopInner
+
+LoopInner:                                        ; preds = %BB_D, %bb22
+  %.1 = phi i32 [ %tmp29, %bb22 ], [ %tmp17, %BB_D ]
+  %tmp22 = add nsw i32 %.1, 1
+  %tmp23 = icmp ne i32 %.1, 0
+  br i1 %tmp23, label %bb22, label %BB_E
+
+BB_E:                                             ; preds = %LoopInner
+  store i32 4, i32* @E, align 4
+  br label %bb22
+
+bb22:                                             ; preds = %LoopInner, %BB_E
+  %tmp29 = add nsw i32 %tmp22, 1
+  %tmp30 = icmp ne i32 %tmp22, 0
+  br i1 %tmp30, label %LoopInner, label %BB_F
+
+BB_F:                                             ; preds = %bb22
+  store i32 5, i32* @F, align 4
+  br label %LoopOuter
+
+BB_G:                                             ; preds = %BB_D
+  store i32 6, i32* @G, align 4
+  ret void
+}
+
+; Function Attrs: willreturn
+define void @foo_willreturn(i32 %arg) willreturn {
+; SLSI-LABEL: @foo_willreturn(
+; SLSI-NEXT:  BB_A:
+; SLSI-NEXT:    store i32 0, i32* @A, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[LOOPOUTER:%.*]] ; no mustexec loop
+; SLSI:       LoopOuter: ; preds = [[BB_F:%.*]], [[BB10:%.*]], [[BB_A:%.*]]
+; SLSI-NEXT:    [[DOT0:%.*]] = phi i32 [ [[ARG:%.*]], [[BB_A]] ], [ [[TMP29:%.*]], [[BB_F]] ], [ [[TMP11:%.*]], [[BB10]] ] ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    store i32 1, i32* @B, align 4 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP5:%.*]] = add nsw i32 [[DOT0]], 1 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[DOT0]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br i1 [[TMP6]], label [[BB_C:%.*]], label [[BB10]] ; (mustexec in: LoopOuter)
+; SLSI:       BB_C: ; preds = [[LOOPOUTER]]
+; SLSI-NEXT:    store i32 2, i32* @C, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[BB10]] ; no mustexec loop
+; SLSI:       bb10: ; preds = [[BB_C]], [[LOOPOUTER]]
+; SLSI-NEXT:    [[TMP11]] = add nsw i32 [[TMP5]], 1 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[TMP5]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br i1 [[TMP12]], label [[LOOPOUTER]], label [[BB_D:%.*]] ; (mustexec in: LoopOuter)
+; SLSI:       BB_D: ; preds = [[BB10]]
+; SLSI-NEXT:    store i32 3, i32* @D, align 4 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP17:%.*]] = add nsw i32 [[TMP11]], 1 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    [[TMP18:%.*]] = icmp ne i32 [[TMP11]], 0 ; (mustexec in: LoopOuter)
+; SLSI-NEXT:    br i1 [[TMP18]], label [[BB_G:%.*]], label [[LOOPINNER:%.*]] ; (mustexec in: LoopOuter)
+; SLSI:       LoopInner: ; preds = [[BB22:%.*]], [[BB_D]]
+; SLSI-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP29]], [[BB22]] ], [ [[TMP17]], [[BB_D]] ] ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP22:%.*]] = add nsw i32 [[DOT1]], 1 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP23:%.*]] = icmp ne i32 [[DOT1]], 0 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    br i1 [[TMP23]], label [[BB22]], label [[BB_E:%.*]] ; (mustexec in: LoopInner)
+; SLSI:       BB_E: ; preds = [[LOOPINNER]]
+; SLSI-NEXT:    store i32 4, i32* @E, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[BB22]] ; no mustexec loop
+; SLSI:       bb22: ; preds = [[BB_E]], [[LOOPINNER]]
+; SLSI-NEXT:    [[TMP29]] = add nsw i32 [[TMP22]], 1 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    [[TMP30:%.*]] = icmp ne i32 [[TMP22]], 0 ; (mustexec in: LoopInner)
+; SLSI-NEXT:    br i1 [[TMP30]], label [[LOOPINNER]], label [[BB_F]] ; (mustexec in: LoopInner)
+; SLSI:       BB_F: ; preds = [[BB22]]
+; SLSI-NEXT:    store i32 5, i32* @F, align 4 ; no mustexec loop
+; SLSI-NEXT:    br label [[LOOPOUTER]] ; no mustexec loop
+; SLSI:       BB_G: ; preds = [[BB_D]]
+; SLSI-NEXT:    store i32 6, i32* @G, align 4 ; no mustexec loop
+; SLSI-NEXT:    ret void ; no mustexec loop
+;
+; ELSI-LABEL: @foo_willreturn(
+; ELSI-NEXT:  BB_A:
+; ELSI-NEXT:    store i32 0, i32* @A, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[LOOPOUTER:%.*]] ; no mustexec loop
+; ELSI:       LoopOuter: ; preds = [[BB_F:%.*]], [[BB10:%.*]], [[BB_A:%.*]]
+; ELSI-NEXT:    [[DOT0:%.*]] = phi i32 [ [[ARG:%.*]], [[BB_A]] ], [ [[TMP29:%.*]], [[BB_F]] ], [ [[TMP11:%.*]], [[BB10]] ] ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    store i32 1, i32* @B, align 4 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    [[TMP5:%.*]] = add nsw i32 [[DOT0]], 1 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[DOT0]], 0 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    br i1 [[TMP6]], label [[BB_C:%.*]], label [[BB10]] ; (mustexec in: LoopOuter)
+; ELSI:       BB_C: ; preds = [[LOOPOUTER]]
+; ELSI-NEXT:    store i32 2, i32* @C, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[BB10]] ; no mustexec loop
+; ELSI:       bb10: ; preds = [[BB_C]], [[LOOPOUTER]]
+; ELSI-NEXT:    [[TMP11]] = add nsw i32 [[TMP5]], 1 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[TMP5]], 0 ; (mustexec in: LoopOuter)
+; ELSI-NEXT:    br i1 [[TMP12]], label [[LOOPOUTER]], label [[BB_D:%.*]] ; (mustexec in: LoopOuter)
+; ELSI:       BB_D: ; preds = [[BB10]]
+; FIXME the following four lines could be improved (nothrow is known up to this point)
+; ELSI-NEXT:    store i32 3, i32* @D, align 4 ; no mustexec loop
+; ELSI-NEXT:    [[TMP17:%.*]] = add nsw i32 [[TMP11]], 1 ; no mustexec loop
+; ELSI-NEXT:    [[TMP18:%.*]] = icmp ne i32 [[TMP11]], 0 ; no mustexec loop
+; ELSI-NEXT:    br i1 [[TMP18]], label [[BB_G:%.*]], label [[LOOPINNER:%.*]] ; no mustexec loop
+; ELSI:       LoopInner: ; preds = [[BB22:%.*]], [[BB_D]]
+; ELSI-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP29]], [[BB22]] ], [ [[TMP17]], [[BB_D]] ] ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP22:%.*]] = add nsw i32 [[DOT1]], 1 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP23:%.*]] = icmp ne i32 [[DOT1]], 0 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    br i1 [[TMP23]], label [[BB22]], label [[BB_E:%.*]] ; (mustexec in: LoopInner)
+; ELSI:       BB_E: ; preds = [[LOOPINNER]]
+; ELSI-NEXT:    store i32 4, i32* @E, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[BB22]] ; no mustexec loop
+; ELSI:       bb22: ; preds = [[BB_E]], [[LOOPINNER]]
+; ELSI-NEXT:    [[TMP29]] = add nsw i32 [[TMP22]], 1 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    [[TMP30:%.*]] = icmp ne i32 [[TMP22]], 0 ; (mustexec in: LoopInner)
+; ELSI-NEXT:    br i1 [[TMP30]], label [[LOOPINNER]], label [[BB_F]] ; (mustexec in: LoopInner)
+; ELSI:       BB_F: ; preds = [[BB22]]
+; ELSI-NEXT:    store i32 5, i32* @F, align 4 ; no mustexec loop
+; ELSI-NEXT:    br label [[LOOPOUTER]] ; no mustexec loop
+; ELSI:       BB_G: ; preds = [[BB_D]]
+; ELSI-NEXT:    store i32 6, i32* @G, align 4 ; no mustexec loop
+; ELSI-NEXT:    ret void ; no mustexec loop
+;
+BB_A:
+  store i32 0, i32* @A, align 4
+  br label %LoopOuter
+
+LoopOuter:                                        ; preds = %bb10, %BB_F, %BB_A
+  %.0 = phi i32 [ %arg, %BB_A ], [ %tmp29, %BB_F ], [ %tmp11, %bb10 ]
+  store i32 1, i32* @B, align 4
+  %tmp5 = add nsw i32 %.0, 1
+  %tmp6 = icmp ne i32 %.0, 0
+  br i1 %tmp6, label %BB_C, label %bb10
+
+BB_C:                                             ; preds = %LoopOuter
+  store i32 2, i32* @C, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %BB_C, %LoopOuter
+  %tmp11 = add nsw i32 %tmp5, 1
+  %tmp12 = icmp ne i32 %tmp5, 0
+  br i1 %tmp12, label %LoopOuter, label %BB_D
+
+BB_D:                                             ; preds = %bb10
+  store i32 3, i32* @D, align 4
+  %tmp17 = add nsw i32 %tmp11, 1
+  %tmp18 = icmp ne i32 %tmp11, 0
+  br i1 %tmp18, label %BB_G, label %LoopInner
+
+LoopInner:                                        ; preds = %BB_D, %bb22
+  %.1 = phi i32 [ %tmp29, %bb22 ], [ %tmp17, %BB_D ]
+  %tmp22 = add nsw i32 %.1, 1
+  %tmp23 = icmp ne i32 %.1, 0
+  br i1 %tmp23, label %bb22, label %BB_E
+
+BB_E:                                             ; preds = %LoopInner
+  store i32 4, i32* @E, align 4
+  br label %bb22
+
+bb22:                                             ; preds = %LoopInner, %BB_E
+  %tmp29 = add nsw i32 %tmp22, 1
+  %tmp30 = icmp ne i32 %tmp22, 0
+  br i1 %tmp30, label %LoopInner, label %BB_F
+
+BB_F:                                             ; preds = %bb22
+  store i32 5, i32* @F, align 4
+  br label %LoopOuter
+
+BB_G:                                             ; preds = %BB_D
+  store i32 6, i32* @G, align 4
+  ret void
+}
+
+; Function Attrs: willreturn nounwind
+define void @foo_willreturn_nounwind(i32 %arg) willreturn nounwind {
+;
+; BOTH-LABEL: @foo_willreturn_nounwind(
+; BOTH-NEXT:  BB_A:
+; BOTH-NEXT:    store i32 0, i32* @A, align 4 ; no mustexec loop
+; BOTH-NEXT:    br label [[LOOPOUTER:%.*]] ; no mustexec loop
+; BOTH:       LoopOuter: ; preds = [[BB_F:%.*]], [[BB10:%.*]], [[BB_A:%.*]]
+; BOTH-NEXT:    [[DOT0:%.*]] = phi i32 [ [[ARG:%.*]], [[BB_A]] ], [ [[TMP29:%.*]], [[BB_F]] ], [ [[TMP11:%.*]], [[BB10]] ] ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    store i32 1, i32* @B, align 4 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    [[TMP5:%.*]] = add nsw i32 [[DOT0]], 1 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    [[TMP6:%.*]] = icmp ne i32 [[DOT0]], 0 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    br i1 [[TMP6]], label [[BB_C:%.*]], label [[BB10]] ; (mustexec in: LoopOuter)
+; BOTH:       BB_C: ; preds = [[LOOPOUTER]]
+; BOTH-NEXT:    store i32 2, i32* @C, align 4 ; no mustexec loop
+; BOTH-NEXT:    br label [[BB10]] ; no mustexec loop
+; BOTH:       bb10: ; preds = [[BB_C]], [[LOOPOUTER]]
+; BOTH-NEXT:    [[TMP11]] = add nsw i32 [[TMP5]], 1 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    [[TMP12:%.*]] = icmp ne i32 [[TMP5]], 0 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    br i1 [[TMP12]], label [[LOOPOUTER]], label [[BB_D:%.*]] ; (mustexec in: LoopOuter)
+; BOTH:       BB_D: ; preds = [[BB10]]
+; BOTH-NEXT:    store i32 3, i32* @D, align 4 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    [[TMP17:%.*]] = add nsw i32 [[TMP11]], 1 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    [[TMP18:%.*]] = icmp ne i32 [[TMP11]], 0 ; (mustexec in: LoopOuter)
+; BOTH-NEXT:    br i1 [[TMP18]], label [[BB_G:%.*]], label [[LOOPINNER:%.*]] ; (mustexec in: LoopOuter)
+; BOTH:       LoopInner: ; preds = [[BB22:%.*]], [[BB_D]]
+; BOTH-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP29]], [[BB22]] ], [ [[TMP17]], [[BB_D]] ] ; (mustexec in: LoopInner)
+; BOTH-NEXT:    [[TMP22:%.*]] = add nsw i32 [[DOT1]], 1 ; (mustexec in: LoopInner)
+; BOTH-NEXT:    [[TMP23:%.*]] = icmp ne i32 [[DOT1]], 0 ; (mustexec in: LoopInner)
+; BOTH-NEXT:    br i1 [[TMP23]], label [[BB22]], label [[BB_E:%.*]] ; (mustexec in: LoopInner)
+; BOTH:       BB_E: ; preds = [[LOOPINNER]]
+; BOTH-NEXT:    store i32 4, i32* @E, align 4 ; no mustexec loop
+; BOTH-NEXT:    br label [[BB22]] ; no mustexec loop
+; BOTH:       bb22: ; preds = [[BB_E]], [[LOOPINNER]]
+; BOTH-NEXT:    [[TMP29]] = add nsw i32 [[TMP22]], 1 ; (mustexec in: LoopInner)
+; BOTH-NEXT:    [[TMP30:%.*]] = icmp ne i32 [[TMP22]], 0 ; (mustexec in: LoopInner)
+; BOTH-NEXT:    br i1 [[TMP30]], label [[LOOPINNER]], label [[BB_F]] ; (mustexec in: LoopInner)
+; BOTH:       BB_F: ; preds = [[BB22]]
+; BOTH-NEXT:    store i32 5, i32* @F, align 4 ; no mustexec loop
+; BOTH-NEXT:    br label [[LOOPOUTER]] ; no mustexec loop
+; BOTH:       BB_G: ; preds = [[BB_D]]
+; BOTH-NEXT:    store i32 6, i32* @G, align 4 ; no mustexec loop
+; BOTH-NEXT:    ret void ; no mustexec loop
+;
+BB_A:
+  store i32 0, i32* @A, align 4
+  br label %LoopOuter
+
+LoopOuter:                                        ; preds = %bb10, %BB_F, %BB_A
+  %.0 = phi i32 [ %arg, %BB_A ], [ %tmp29, %BB_F ], [ %tmp11, %bb10 ]
+  store i32 1, i32* @B, align 4
+  %tmp5 = add nsw i32 %.0, 1
+  %tmp6 = icmp ne i32 %.0, 0
+  br i1 %tmp6, label %BB_C, label %bb10
+
+BB_C:                                             ; preds = %LoopOuter
+  store i32 2, i32* @C, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %BB_C, %LoopOuter
+  %tmp11 = add nsw i32 %tmp5, 1
+  %tmp12 = icmp ne i32 %tmp5, 0
+  br i1 %tmp12, label %LoopOuter, label %BB_D
+
+BB_D:                                             ; preds = %bb10
+  store i32 3, i32* @D, align 4
+  %tmp17 = add nsw i32 %tmp11, 1
+  %tmp18 = icmp ne i32 %tmp11, 0
+  br i1 %tmp18, label %BB_G, label %LoopInner
+
+LoopInner:                                        ; preds = %BB_D, %bb22
+  %.1 = phi i32 [ %tmp29, %bb22 ], [ %tmp17, %BB_D ]
+  %tmp22 = add nsw i32 %.1, 1
+  %tmp23 = icmp ne i32 %.1, 0
+  br i1 %tmp23, label %bb22, label %BB_E
+
+BB_E:                                             ; preds = %LoopInner
+  store i32 4, i32* @E, align 4
+  br label %bb22
+
+bb22:                                             ; preds = %LoopInner, %BB_E
+  %tmp29 = add nsw i32 %tmp22, 1
+  %tmp30 = icmp ne i32 %tmp22, 0
+  br i1 %tmp30, label %LoopInner, label %BB_F
+
+BB_F:                                             ; preds = %bb22
+  store i32 5, i32* @F, align 4
+  br label %LoopOuter
+
+BB_G:                                             ; preds = %BB_D
+  store i32 6, i32* @G, align 4
+  ret void
+}