Index: include/llvm/Analysis/MustExecute.h =================================================================== --- include/llvm/Analysis/MustExecute.h +++ include/llvm/Analysis/MustExecute.h @@ -55,6 +55,9 @@ bool mayThrowBefore(const Instruction *Insn); + bool allPredecessorsLeadToBlock(const BasicBlock *BB, + const DominatorTree *DT); + void invalidateBlock(const BasicBlock *BB); void reset(Loop *L); Index: lib/Analysis/MustExecute.cpp =================================================================== --- lib/Analysis/MustExecute.cpp +++ lib/Analysis/MustExecute.cpp @@ -115,7 +115,7 @@ /// Return true if we can prove that the given ExitBlock is not reached on the /// first iteration of the given loop. That is, the backedge of the loop must /// be executed before the ExitBlock is executed in any dynamic execution trace. -static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock, +static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop) { auto *CondExitBlock = ExitBlock->getSinglePredecessor(); @@ -155,6 +155,57 @@ return SimpleCst->isAllOnesValue(); } +/// Return true if we must reach the block \p BB under assumption that the loop +/// is entered and no instruction throws or otherwise exits abnormally. +bool LoopSafetyInfo::allPredecessorsLeadToBlock(const BasicBlock *BB, + const DominatorTree *DT) { + assert(CurLoop && "Should calculate the info first!"); + 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. + SmallPtrSet Predecessors; + SmallVector WorkList; + for (auto *Pred : predecessors(BB)) { + Predecessors.insert(Pred); + WorkList.push_back(BB); + } + while (!WorkList.empty()) { + auto *Pred = WorkList.pop_back_val(); + assert(CurLoop->contains(Pred) && "Should only reach loop blocks!"); + // We are not interested in backedges. + if (Pred == CurLoop->getHeader()) + continue; + 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)) + // Okay, if the successor is neither the BB nor one of its predecessors, + // but if it an exit block which is not reached on the 1st iteration, we + // can skip it. Otherwise, conservatively return false. We could be much + // smarter here if we took not just the 1st iteration. + 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, @@ -179,41 +230,11 @@ if (SafetyInfo->mayThrowBefore(&Inst)) 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 way from header to exit or latch that doesn't lead to our + // instruction's block, return false. + if (!SafetyInfo->allPredecessorsLeadToBlock(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; } Index: test/Analysis/MustExecute/infinite_loops.ll =================================================================== --- test/Analysis/MustExecute/infinite_loops.ll +++ 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 @@ ; 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 @@ 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 @@ ; 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) Index: test/Analysis/MustExecute/loop-header.ll =================================================================== --- test/Analysis/MustExecute/loop-header.ll +++ test/Analysis/MustExecute/loop-header.ll @@ -57,9 +57,9 @@ ; 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: %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: call void @maythrow_and_use(i32 %v) ; (mustexec in: loop) ; CHECK-NOT: mustexec Index: test/Transforms/LICM/infinite_loops.ll =================================================================== --- test/Transforms/LICM/infinite_loops.ll +++ 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: Index: test/Transforms/LICM/preheader-safe.ll =================================================================== --- test/Transforms/LICM/preheader-safe.ll +++ test/Transforms/LICM/preheader-safe.ll @@ -112,11 +112,30 @@ exit: ret void } -; Negative test - can't move out of throwing block +; Positive test -- we can hoist udiv which is before any thrower. +define void @nothrow_header_pos(i64 %x, i64 %y, i1 %cond) { +; CHECK-LABEL: nothrow_header_pos +; CHECK-LABEL: entry +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +; CHECK: call void @use(i64 %div) +entry: + br label %loop +loop: ; preds = %entry, %for.inc + br label %loop-if +loop-if: + %div = udiv i64 %x, %y + call void @use(i64 %div) + br label %loop +} + +; Negative test -- we cannot hoist across a thrower. define void @nothrow_header_neg(i64 %x, i64 %y, i1 %cond) { ; CHECK-LABEL: nothrow_header_neg ; CHECK-LABEL: entry +; CHECK-NOT: udiv ; CHECK-LABEL: loop +; CHECK: call void @maythrow() ; CHECK: %div = udiv i64 %x, %y ; CHECK: call void @use(i64 %div) entry: @@ -124,6 +143,7 @@ loop: ; preds = %entry, %for.inc br label %loop-if loop-if: + call void @maythrow() %div = udiv i64 %x, %y call void @use(i64 %div) br label %loop