From 98f11a7d75b54b44b3b136b537644fd3f6d77239 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Sat, 2 Mar 2019 02:31:44 +0000 Subject: [PATCH] [SCEV] Handle case where MaxBECount is less precise than ExactBECount for OR. In some cases, MaxBECount can be less precise than ExactBECount for AND and OR (the AND case was PR26207). In the OR test case, both ExactBECounts are undef, but MaxBECount are different, so we hit the assertion below. This patch uses the same solution the AND case already uses. Assertion failed: ((isa(ExactNotTaken) || !isa(MaxNotTaken)) && "Exact is not allowed to be less precise than Max"), function ExitLimit This patch also consolidates test cases for both AND and OR in a single test case. Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13245 Reviewers: sanjoy, efriedma, mkazantsev Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D58853 llvm-svn: 355259 --- llvm/lib/Analysis/ScalarEvolution.cpp | 8 ++++ .../exact-exit-count-more-precise.ll | 49 ++++++++++++++++++++++ llvm/test/Transforms/IndVarSimplify/pr26207.ll | 20 --------- 3 files changed, 57 insertions(+), 20 deletions(-) create mode 100644 llvm/test/Analysis/ScalarEvolution/exact-exit-count-more-precise.ll delete mode 100644 llvm/test/Transforms/IndVarSimplify/pr26207.ll diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 290e87a..f14f046 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -7272,6 +7272,14 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( if (EL0.ExactNotTaken == EL1.ExactNotTaken) BECount = EL0.ExactNotTaken; } + // There are cases (e.g. PR26207) where computeExitLimitFromCond is able + // to be more aggressive when computing BECount than when computing + // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and + // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken + // to not. + if (isa(MaxBECount) && + !isa(BECount)) + MaxBECount = getConstant(getUnsignedRangeMax(BECount)); return ExitLimit(BECount, MaxBECount, false, {&EL0.Predicates, &EL1.Predicates}); diff --git a/llvm/test/Analysis/ScalarEvolution/exact-exit-count-more-precise.ll b/llvm/test/Analysis/ScalarEvolution/exact-exit-count-more-precise.ll new file mode 100644 index 0000000..8b1f878 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/exact-exit-count-more-precise.ll @@ -0,0 +1,49 @@ +; RUN: opt -analyze -scalar-evolution %s | FileCheck %s + +target triple = "x86_64-unknown-linux-gnu" + +define void @test_and(i16 %in) { + br label %bb2 + +bb2: ; preds = %bb1.i, %bb2, %0 + %_tmp44.i = icmp slt i16 %in, 2 + br i1 %_tmp44.i, label %bb1.i, label %bb2 + +bb1.i: ; preds = %bb1.i, %bb2 + %_tmp25.i = phi i16 [ %in, %bb2 ], [ %_tmp6.i, %bb1.i ] + %_tmp6.i = add nsw i16 %_tmp25.i, 1 + %_tmp10.i = icmp sge i16 %_tmp6.i, 2 + %exitcond.i = icmp eq i16 %_tmp6.i, 2 + %or.cond = and i1 %_tmp10.i, %exitcond.i + br i1 %or.cond, label %bb2, label %bb1.i +} + +; CHECK-LABEL: Determining loop execution counts for: @test_and +; CHECK-NEXT: Loop %bb1.i: backedge-taken count is (1 + (-1 * %in)) +; CHECK-NEXT: Loop %bb1.i: max backedge-taken count is -1 +; CHECK-NEXT: Loop %bb1.i: Predicated backedge-taken count is (1 + (-1 * %in)) + + +define void @test_or() { + %C10 = icmp slt i1 undef, undef + br i1 %C10, label %BB, label %exit + +BB: ; preds = %BB, %0 + %indvars.iv = phi i64 [ -1, %BB ], [ -1, %0 ] + %sum.01 = phi i32 [ %2, %BB ], [ undef, %0 ] + %1 = trunc i64 %indvars.iv to i32 + %2 = add nsw i32 %1, %sum.01 + %B3 = add i32 %1, %2 + %C11 = icmp ult i32 %2, %1 + %C5 = icmp sle i32 %1, %B3 + %B = or i1 %C5, %C11 + br i1 %B, label %BB, label %exit + +exit: ; preds = %BB, %0 + ret void +} + +; CHECK-LABEL: Determining loop execution counts for: @test_or +; CHECK-NEXT: Loop %BB: backedge-taken count is undef +; CHECK-NEXT: Loop %BB: max backedge-taken count is -1 +; CHECK-NEXT: Loop %BB: Predicated backedge-taken count is undef diff --git a/llvm/test/Transforms/IndVarSimplify/pr26207.ll b/llvm/test/Transforms/IndVarSimplify/pr26207.ll deleted file mode 100644 index 9d351e0..0000000 --- a/llvm/test/Transforms/IndVarSimplify/pr26207.ll +++ /dev/null @@ -1,20 +0,0 @@ -; RUN: opt -S -indvars < %s | FileCheck %s - -target triple = "x86_64-unknown-linux-gnu" - -define void @main(i16 %in) { -; CHECK-LABEL: @main( - br label %bb2 - -bb2: ; preds = %bb1.i, %bb2, %0 - %_tmp44.i = icmp slt i16 %in, 2 - br i1 %_tmp44.i, label %bb1.i, label %bb2 - -bb1.i: ; preds = %bb1.i, %bb2 - %_tmp25.i = phi i16 [ %in, %bb2 ], [ %_tmp6.i, %bb1.i ] - %_tmp6.i = add nsw i16 %_tmp25.i, 1 - %_tmp10.i = icmp sge i16 %_tmp6.i, 2 - %exitcond.i = icmp eq i16 %_tmp6.i, 2 - %or.cond = and i1 %_tmp10.i, %exitcond.i - br i1 %or.cond, label %bb2, label %bb1.i -} -- 2.7.4