Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -6821,13 +6821,7 @@ const SCEV *MayExitMaxBECount = nullptr; bool MustExitMaxOrZero = false; - // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts - // and compute maxBECount. - // Do a union of all the predicates here. - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { - BasicBlock *ExitBB = ExitingBlocks[i]; - ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates); - + auto ConsiderExitLimit = [&](BasicBlock *Block, ExitLimit &EL) { assert((AllowPredicates || EL.Predicates.empty()) && "Predicated exit limit when predicates are not allowed!"); @@ -6838,7 +6832,7 @@ // we won't be able to compute an exact value for the loop. CouldComputeBECount = false; else - ExitCounts.emplace_back(ExitBB, EL); + ExitCounts.emplace_back(Block, EL); // 2. Derive the loop's MaxBECount from each exit's max number of // non-exiting iterations. Partition the loop exits into two kinds: @@ -6851,7 +6845,7 @@ // EL.MaxNotTaken, where CouldNotCompute is considered greater than any // computable EL.MaxNotTaken. if (EL.MaxNotTaken != getCouldNotCompute() && Latch && - DT.dominates(ExitBB, Latch)) { + DT.dominates(Block, Latch)) { if (!MustExitMaxBECount) { MustExitMaxBECount = EL.MaxNotTaken; MustExitMaxOrZero = EL.MaxOrZero; @@ -6867,7 +6861,33 @@ getUMaxFromMismatchedTypes(MayExitMaxBECount, EL.MaxNotTaken); } } - } + }; + + // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts + // and compute maxBECount. + // Do a union of all the predicates here. + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { + BasicBlock *ExitBB = ExitingBlocks[i]; + ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates); + ConsiderExitLimit(ExitBB, EL); + } + + if (HasGuards) + // If there are guards in the loop, use their conditions to have a more + // accurate estimation. + for (BasicBlock *BB : L->getBlocks()) + for (Instruction &It : *BB) { + using namespace llvm::PatternMatch; + Value *Condition; + if (match(&It, m_Intrinsic( + m_Value(Condition)))) { + ExitLimit EL = + computeExitLimitFromCond(L, Condition, /*ExitByCond=*/false, + /*ControlsExit=*/false, AllowPredicates); + ConsiderExitLimit(BB, EL); + } + } + const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute()); // The loop backedge will be taken the maximum or zero times if there's Index: test/Analysis/ScalarEvolution/exit_count_from_guards.ll =================================================================== --- test/Analysis/ScalarEvolution/exit_count_from_guards.ll +++ test/Analysis/ScalarEvolution/exit_count_from_guards.ll @@ -0,0 +1,139 @@ +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare void @llvm.experimental.guard(i1, ...) + +; Exit by explicit branch when %iv = 91. +define void @test_explicit_branch() { + +; CHECK-LABEL: Determining loop execution counts for: @test_explicit_branch +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 91 +; CHECK: Loop %loop: Unpredictable predicated backedge-taken count. + +entry: + %iv.pre.lcmp = icmp sle i8 0, 100 + br i1 %iv.pre.lcmp, label %loop, label %exit + +loop: + %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop.continue ] + %iv.gcmp = icmp sle i8 %iv, 90 + br i1 %iv.gcmp, label %loop.continue, label %exceptional.exit + +loop.continue: + %iv.inc = add i8 %iv, 1 + %iv.lcmp = icmp sle i8 %iv.inc, 100 + br i1 %iv.lcmp, label %loop, label %exit + +exceptional.exit: + ret void + +exit: + ret void +} + +; Exit by the only single guard when %iv = 91. +define void @test_guard_01() { + +; CHECK-LABEL: Determining loop execution counts for: @test_guard_01 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 91 +; CHECK: Loop %loop: Unpredictable predicated backedge-taken count. + +entry: + %iv.pre.lcmp = icmp sle i8 0, 100 + br i1 %iv.pre.lcmp, label %loop, label %exit + +loop: + %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.gcmp = icmp sle i8 %iv, 90 + call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ] + + %iv.inc = add i8 %iv, 1 + %iv.lcmp = icmp sle i8 %iv.inc, 100 + br i1 %iv.lcmp, label %loop, label %exit + +exit: + ret void +} + +; Two guards that fail on %iv = 51 and 31, meaning that we exit when %iv = 31. +define void @test_guard_02() { + +; CHECK-LABEL: Determining loop execution counts for: @test_guard_02 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 31 +; CHECK: Loop %loop: Unpredictable predicated backedge-taken count. + +entry: + %iv.pre.lcmp = icmp sle i8 0, 100 + br i1 %iv.pre.lcmp, label %loop, label %exit + +loop: + %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.gcmp1 = icmp sle i8 %iv, 50 + %iv.gcmp2 = icmp sle i8 %iv, 30 + call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp1) [ "deopt"() ] + call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp2) [ "deopt"() ] + + %iv.inc = add i8 %iv, 1 + %iv.lcmp = icmp sle i8 %iv.inc, 100 + br i1 %iv.lcmp, label %loop, label %exit + +exit: + ret void +} + +; Similar to test_guard_02, but now the conditions are joined via AND. +define void @test_guard_03() { + +; CHECK-LABEL: Determining loop execution counts for: @test_guard_03 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 31 +; CHECK: Loop %loop: Unpredictable predicated backedge-taken count. + +entry: + %iv.pre.lcmp = icmp sle i8 0, 100 + br i1 %iv.pre.lcmp, label %loop, label %exit + +loop: + %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.gcmp1 = icmp sle i8 %iv, 50 + %iv.gcmp2 = icmp sle i8 %iv, 30 + %iv.gcmp = and i1 %iv.gcmp1, %iv.gcmp2 + call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ] + + %iv.inc = add i8 %iv, 1 + %iv.lcmp = icmp sle i8 %iv.inc, 100 + br i1 %iv.lcmp, label %loop, label %exit + +exit: + ret void +} + +; Guard fails on the first iteration. +define void @test_guard_04() { + +; CHECK-LABEL: Determining loop execution counts for: @test_guard_04 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 0 +; CHECK: Loop %loop: Unpredictable predicated backedge-taken count. + +entry: + %iv.pre.lcmp = icmp sle i8 0, 100 + br i1 %iv.pre.lcmp, label %loop, label %exit + +loop: + %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.gcmp = icmp sge i8 %iv, 90 + call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ] + + %iv.inc = add i8 %iv, 1 + %iv.lcmp = icmp sle i8 %iv.inc, 100 + br i1 %iv.lcmp, label %loop, label %exit + +exit: + ret void +} Index: test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll =================================================================== --- test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll +++ test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll @@ -137,7 +137,7 @@ %iv.inc = add i32 %iv, 3 %iv.zext = zext i32 %iv to i64 ; CHECK: %iv.zext = zext i32 %iv to i64 -; CHECK-NEXT: --> {0,+,3}<%loop> +; CHECK-NEXT: --> {0,+,3}<%loop> %cmp = icmp ult i32 %iv, 10000 call void(i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ] %c = load volatile i1, i1* %cond