diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h --- a/llvm/include/llvm/Analysis/MustExecute.h +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -697,6 +697,69 @@ MustBeExecutedIterator EndIterator; }; +/// An implementation of the LoopSafetyInfoInterface using the +/// MustBeExecutedContextExplorer to determine all reached instructions. +template +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 ThrowingBlocksMap; +}; + } // namespace llvm #endif diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -27,6 +27,11 @@ #define DEBUG_TYPE "must-execute" +static cl::opt MustExecutePrinterUseExplorer( + "print-mustexecute-use-explorer", cl::Hidden, cl::init(false), + cl::desc( + "Use 'must-be-executed-context' explorer for the mustexecute printer")); + const DenseMap & LoopSafetyInfo::getBlockColors() const { return BlockColors; @@ -407,16 +412,35 @@ DenseMap > MustExec; public: - MustExecuteAnnotatedWriter(const Function &F, - DominatorTree &DT, LoopInfo &LI) { - for (auto &I: instructions(F)) { - Loop *L = LI.getLoopFor(I.getParent()); - while (L) { - if (isMustExecuteIn(I, L, &DT)) { - MustExec[&I].push_back(L); - } - L = L->getParentLoop(); - }; + MustExecuteAnnotatedWriter(const Function &F, DominatorTree &DT, + LoopInfo &LI) { + if (MustExecutePrinterUseExplorer) { + MustBeExecutedLoopSafetyInfo MBELSI(&DT, nullptr, &LI); + + SmallVector 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, @@ -435,8 +459,10 @@ 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(); @@ -1185,3 +1211,45 @@ It.getSecond()->Visited->erase({I, ExplorationDirection::BACKWARD}); } } + +template +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; + } +} + diff --git a/llvm/test/Analysis/MustExecute/const-cond.ll b/llvm/test/Analysis/MustExecute/const-cond.ll --- a/llvm/test/Analysis/MustExecute/const-cond.ll +++ b/llvm/test/Analysis/MustExecute/const-cond.ll @@ -1,27 +1,29 @@ ; 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 diff --git a/llvm/test/Analysis/MustExecute/infinite_loops.ll b/llvm/test/Analysis/MustExecute/infinite_loops.ll --- a/llvm/test/Analysis/MustExecute/infinite_loops.ll +++ b/llvm/test/Analysis/MustExecute/infinite_loops.ll @@ -1,22 +1,22 @@ ; 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 @@ -37,20 +37,21 @@ ; 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 @@ -73,22 +74,37 @@ ; 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 diff --git a/llvm/test/Analysis/MustExecute/loop-header.ll b/llvm/test/Analysis/MustExecute/loop-header.ll --- a/llvm/test/Analysis/MustExecute/loop-header.ll +++ b/llvm/test/Analysis/MustExecute/loop-header.ll @@ -1,14 +1,22 @@ ; 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 @@ -25,12 +33,23 @@ } 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 @@ -51,23 +70,50 @@ ; 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 @@ -84,19 +130,44 @@ } 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 @@ -106,6 +177,7 @@ 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 @@ -122,17 +194,21 @@ ; 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 diff --git a/llvm/test/Analysis/MustExecute/must_execute_context_explorer.ll b/llvm/test/Analysis/MustExecute/must_execute_context_explorer.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/MustExecute/must_execute_context_explorer.ll @@ -0,0 +1,383 @@ +; 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 +}