diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/MustExecute.h | 6 | ||||
| -rw-r--r-- | llvm/lib/Analysis/MustExecute.cpp | 103 | ||||
| -rw-r--r-- | llvm/test/Analysis/MustExecute/infinite_loops.ll | 25 | ||||
| -rw-r--r-- | llvm/test/Analysis/MustExecute/loop-header.ll | 37 | ||||
| -rw-r--r-- | llvm/test/Transforms/LICM/infinite_loops.ll | 7 |
5 files changed, 125 insertions, 53 deletions
diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h index 6998c121feb..89774395415 100644 --- a/llvm/include/llvm/Analysis/MustExecute.h +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -62,6 +62,12 @@ public: /// instruction that may throw or otherwise exit abnormally. bool anyBlockMayThrow() const; + /// Return true if we must reach the block \p BB under assumption that the + /// loop \p CurLoop is entered and no instruction throws or otherwise exits + /// abnormally. + bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, + const DominatorTree *DT) const; + /// Computes safety information for a loop checks loop body & header for /// the possibility of may throw exception, it takes LoopSafetyInfo and loop /// as argument. Updates safety information in LoopSafetyInfo argument. diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp index ed847c9109a..ab091005a20 100644 --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -98,6 +98,73 @@ static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, return SimpleCst->isAllOnesValue(); } + +bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop, + const BasicBlock *BB, + const DominatorTree *DT) const { + assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); + + // Fast path: header is always reached once the loop is entered. + if (BB == CurLoop->getHeader()) + return true; + + // Collect all transitive predecessors of BB in the same loop. This set will + // be a subset of the blocks within the loop. + SmallPtrSet<const BasicBlock *, 4> Predecessors; + SmallVector<const BasicBlock *, 4> WorkList; + for (auto *Pred : predecessors(BB)) { + Predecessors.insert(Pred); + WorkList.push_back(Pred); + } + while (!WorkList.empty()) { + auto *Pred = WorkList.pop_back_val(); + assert(CurLoop->contains(Pred) && "Should only reach loop blocks!"); + // We are not interested in backedges and we don't want to leave loop. + if (Pred == CurLoop->getHeader()) + continue; + // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all + // blocks of this inner loop, even those that are always executed AFTER the + // BB. It may make our analysis more conservative than it could be, see test + // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll. + // We can ignore backedge of all loops containing BB to get a sligtly more + // optimistic result. + for (auto *PredPred : predecessors(Pred)) + if (Predecessors.insert(PredPred).second) + WorkList.push_back(PredPred); + } + + // Make sure that all successors of all predecessors of BB are either: + // 1) BB, + // 2) Also predecessors of BB, + // 3) Exit blocks which are not taken on 1st iteration. + // Memoize blocks we've already checked. + SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors; + for (auto *Pred : Predecessors) + for (auto *Succ : successors(Pred)) + if (CheckedSuccessors.insert(Succ).second && + Succ != BB && !Predecessors.count(Succ)) + // By discharging conditions that are not executed on the 1st iteration, + // we guarantee that *at least* on the first iteration all paths from + // header that *may* execute will lead us to the block of interest. So + // that if we had virtually peeled one iteration away, in this peeled + // iteration the set of predecessors would contain only paths from + // header to BB without any exiting edges that may execute. + // + // TODO: We only do it for exiting edges currently. We could use the + // same function to skip some of the edges within the loop if we know + // that they will not be taken on the 1st iteration. + // + // TODO: If we somehow know the number of iterations in loop, the same + // check may be done for any arbitrary N-th iteration as long as N is + // not greater than minimum number of iterations in this loop. + if (CurLoop->contains(Succ) || + !CanProveNotTakenFirstIteration(Succ, DT, CurLoop)) + return false; + + // All predecessors can only lead us to BB. + return true; +} + /// Returns true if the instruction in a loop is guaranteed to execute at least /// once. bool llvm::isGuaranteedToExecute(const Instruction &Inst, @@ -123,41 +190,11 @@ bool llvm::isGuaranteedToExecute(const Instruction &Inst, if (SafetyInfo->anyBlockMayThrow()) return false; - // Note: There are two styles of reasoning intermixed below for - // implementation efficiency reasons. They are: - // 1) If we can prove that the instruction dominates all exit blocks, then we - // know the instruction must have executed on *some* iteration before we - // exit. We do not prove *which* iteration the instruction must execute on. - // 2) If we can prove that the instruction dominates the latch and all exits - // which might be taken on the first iteration, we know the instruction must - // execute on the first iteration. This second style allows a conditional - // exit before the instruction of interest which is provably not taken on the - // first iteration. This is a quite common case for range check like - // patterns. TODO: support loops with multiple latches. - - const bool InstDominatesLatch = - CurLoop->getLoopLatch() != nullptr && - DT->dominates(Inst.getParent(), CurLoop->getLoopLatch()); - - // Get the exit blocks for the current loop. - SmallVector<BasicBlock *, 8> ExitBlocks; - CurLoop->getExitBlocks(ExitBlocks); - - // Verify that the block dominates each of the exit blocks of the loop. - for (BasicBlock *ExitBlock : ExitBlocks) - if (!DT->dominates(Inst.getParent(), ExitBlock)) - if (!InstDominatesLatch || - !CanProveNotTakenFirstIteration(ExitBlock, DT, CurLoop)) - return false; - - // As a degenerate case, if the loop is statically infinite then we haven't - // proven anything since there are no exit blocks. - if (ExitBlocks.empty()) + // If there is a path from header to exit or latch that doesn't lead to our + // instruction's block, return false. + if (!SafetyInfo->allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT)) return false; - // FIXME: In general, we have to prove that the loop isn't an infinite loop. - // See http::llvm.org/PR24078 . (The "ExitBlocks.empty()" check above is - // just a special case of this.) return true; } diff --git a/llvm/test/Analysis/MustExecute/infinite_loops.ll b/llvm/test/Analysis/MustExecute/infinite_loops.ll index 1dc5372920a..b8158e10204 100644 --- a/llvm/test/Analysis/MustExecute/infinite_loops.ll +++ b/llvm/test/Analysis/MustExecute/infinite_loops.ll @@ -2,7 +2,7 @@ ; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s ; Infinite loop. -; TODO: backedge is provably mustexecute, but the analysis does not know this. +; 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: @@ -10,17 +10,13 @@ define void @test_no_exit_block(i1 %cond, i32 %a, i32 %b) { ; 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) - -; FIXME: Should be mustexec in backedge. The current analysis does not handle -; loops without exit blocks at all. -; CHECK-NOT: ; (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 -; CHECK-NEXT: br label [[LOOP]] +; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 ; (mustexec in: loop) +; CHECK-NEXT: br label [[LOOP]] ; (mustexec in: loop) ; entry: br label %loop @@ -75,7 +71,7 @@ exit: ret void } -; FIXME: This code demonstrates a bug. %div should not be mustexec. +; 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: @@ -84,13 +80,10 @@ define void @test_impossible_exit_in_untaken_block(i1 %cond, i32 %a, i32 %b, i32 ; 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: - -; FIXME: The block below is NOT always taken!!! Current this example demonstrates a -; bug in current mustexecute analysis. - -; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; (mustexec in: loop) -; CHECK-NEXT: store i32 [[DIV]], i32* [[P:%.*]] ; (mustexec in: loop) -; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[EXIT:%.*]] ; (mustexec in: loop) +; 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) diff --git a/llvm/test/Analysis/MustExecute/loop-header.ll b/llvm/test/Analysis/MustExecute/loop-header.ll index 3e729993d42..d0ec5fa6872 100644 --- a/llvm/test/Analysis/MustExecute/loop-header.ll +++ b/llvm/test/Analysis/MustExecute/loop-header.ll @@ -83,6 +83,43 @@ exit: ret i1 false } +; FIXME: everything in inner loop header should be must execute +; for outer as well +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: 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-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) + +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: + %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 diff --git a/llvm/test/Transforms/LICM/infinite_loops.ll b/llvm/test/Transforms/LICM/infinite_loops.ll index 07238c396b8..6189bdb1a97 100644 --- a/llvm/test/Transforms/LICM/infinite_loops.ll +++ b/llvm/test/Transforms/LICM/infinite_loops.ll @@ -2,23 +2,22 @@ ; RUN: opt -S -basicaa -licm < %s | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s -; FIXME: This test demonstrates a bug in MustExecute analysis. We hoist sdiv -; which can be a division by zero from a block which is never taken. +; Make sure we don't hoist the unsafe division to some executable block. define void @test_impossible_exit_in_untaken_block(i32 %a, i32 %b, i32* %p) { ; CHECK-LABEL: @test_impossible_exit_in_untaken_block( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: br i1 false, label [[NEVER_TAKEN:%.*]], label [[BACKEDGE]] ; CHECK: never_taken: +; 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 ; CHECK-NEXT: br label [[LOOP]] ; CHECK: exit: -; CHECK-NEXT: store i32 [[DIV]], i32* [[P:%.*]], align 4 ; CHECK-NEXT: ret void ; entry: |
