Index: include/llvm/Analysis/MustExecute.h =================================================================== --- include/llvm/Analysis/MustExecute.h +++ include/llvm/Analysis/MustExecute.h @@ -62,6 +62,12 @@ /// 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. Index: lib/Analysis/MustExecute.cpp =================================================================== --- lib/Analysis/MustExecute.cpp +++ lib/Analysis/MustExecute.cpp @@ -58,7 +58,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(); @@ -98,6 +98,56 @@ 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. + 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)) + // If we are dealing with exiting edge which is not taken on the first + // iteration, we can safely continue. + // 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. + 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 +173,11 @@ 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 way 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; } 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/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: