From 7b78d3920c713de2555b5d0f476bc31a0d9aac5d Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Fri, 17 Aug 2018 06:19:17 +0000 Subject: [PATCH] [MustExecute] Fix algorithmic bug in isGuaranteedToExecute. PR38514 The description of `isGuaranteedToExecute` does not correspond to its implementation. According to description, it should return `true` if an instruction is executed under the assumption that its loop is *entered*. However there is a sophisticated alrogithm inside that tries to prove that the instruction is executed if the loop is *exited*, which is not the same thing for infinite loops. There is an attempt to protect from dealing with infinite loops by prohibiting loops without exit blocks, however an infinite loop can have exit blocks. As result of that, MustExecute can falsely consider some blocks that are never entered as mustexec, and LICM can hoist dangerous instructions out of them basing on this fact. This may introduce UB to programs which did not contain it initially. This patch removes the problematic algorithm and replaced it with a one which tries to prove what is required in description. Differential Revision: https://reviews.llvm.org/D50558 Reviewed By: reames llvm-svn: 339984 --- llvm/include/llvm/Analysis/MustExecute.h | 6 ++ llvm/lib/Analysis/MustExecute.cpp | 103 +++++++++++++++-------- llvm/test/Analysis/MustExecute/infinite_loops.ll | 25 ++---- llvm/test/Analysis/MustExecute/loop-header.ll | 37 ++++++++ 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 6998c12..8977439 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 ed847c9..ab09100 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 Predecessors; + SmallVector 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 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 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 1dc5372..b8158e1 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 3e72999..d0ec5fa 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 07238c3..6189bdb 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,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: -- 2.7.4