From 44fb5881d8edf448d6231a5b8df583aecd6bcd42 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Tue, 26 Jan 2016 22:29:46 +0000 Subject: [PATCH] Merging r258184: ------------------------------------------------------------------------ r258184 | sanjoy | 2016-01-19 12:53:51 -0800 (Tue, 19 Jan 2016) | 20 lines [SCEV] Fix PR26207 In some cases, the max backedge taken count can be more conservative than the exact backedge taken count (for instance, because ScalarEvolution::getRange is not control-flow sensitive whereas computeExitLimitFromICmp can be). In these cases, computeExitLimitFromCond (specifically the bit that deals with `and` and `or` instructions) can create an ExitLimit instance with a `SCEVCouldNotCompute` max backedge count expression, but a computable exact backedge count expression. This violates an implicit SCEV assumption: a computable exact BE count should imply a computable max BE count. This change - Makes the above implicit invariant explicit by adding an assert to ExitLimit's constructor - Changes `computeExitLimitFromCond` to be more robust around conservative max backedge counts ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_38@258869 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 6 +++++- lib/Analysis/ScalarEvolution.cpp | 8 ++++++++ test/Transforms/IndVarSimplify/pr26207.ll | 20 ++++++++++++++++++++ 3 files changed, 33 insertions(+), 1 deletion(-) create mode 100644 test/Transforms/IndVarSimplify/pr26207.ll diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index c08335de3e7..ef930578884 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -412,7 +412,11 @@ namespace llvm { /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} - ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {} + ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) { + assert((isa(Exact) || + !isa(Max)) && + "Exact is not allowed to be less precise than Max"); + } /// Test whether this ExitLimit contains any computed information, or /// whether it's all SCEVCouldNotCompute values. diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 34074efd1ce..ef1bb3a36c8 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -5368,6 +5368,14 @@ ScalarEvolution::computeExitLimitFromCond(const Loop *L, BECount = EL0.Exact; } + // 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.Exact and EL1.Exact + // to match, but for EL0.Max and EL1.Max to not. + if (isa(MaxBECount) && + !isa(BECount)) + MaxBECount = BECount; + return ExitLimit(BECount, MaxBECount); } if (BO->getOpcode() == Instruction::Or) { diff --git a/test/Transforms/IndVarSimplify/pr26207.ll b/test/Transforms/IndVarSimplify/pr26207.ll new file mode 100644 index 00000000000..9d351e09857 --- /dev/null +++ b/test/Transforms/IndVarSimplify/pr26207.ll @@ -0,0 +1,20 @@ +; 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.34.1