From 93011351eadeb5343daf5351eaabfd5289e845c3 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Thu, 6 Aug 2015 20:43:41 +0000 Subject: [PATCH] [IndVars] Fix PR24356. Unsigned predicates increase or decrease agnostic of the signs of their increments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@244265 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 66 +++++++++++------------ test/Transforms/IndVarSimplify/pr24356.ll | 63 ++++++++++++++++++++++ 2 files changed, 93 insertions(+), 36 deletions(-) create mode 100644 test/Transforms/IndVarSimplify/pr24356.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 73f0dc1e44c..3e3032b48fe 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6721,8 +6721,16 @@ bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS, bool ScalarEvolution::isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing) { - SCEV::NoWrapFlags FlagsRequired = SCEV::FlagAnyWrap; - bool IncreasingOnNonNegativeStep = false; + + // A zero step value for LHS means the induction variable is essentially a + // loop invariant value. We don't really depend on the predicate actually + // flipping from false to true (for increasing predicates, and the other way + // around for decreasing predicates), all we care about is that *if* the + // predicate changes then it only changes from false to true. + // + // A zero step value in itself is not very useful, but there may be places + // where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be + // as general as possible. switch (Pred) { default: @@ -6730,53 +6738,39 @@ bool ScalarEvolution::isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: - FlagsRequired = SCEV::FlagNUW; - IncreasingOnNonNegativeStep = true; - break; - case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: - FlagsRequired = SCEV::FlagNUW; - IncreasingOnNonNegativeStep = false; - break; + if (!LHS->getNoWrapFlags(SCEV::FlagNUW)) + return false; + + Increasing = Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE; + return true; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: - FlagsRequired = SCEV::FlagNSW; - IncreasingOnNonNegativeStep = true; - break; - case ICmpInst::ICMP_SLT: - case ICmpInst::ICMP_SLE: - FlagsRequired = SCEV::FlagNSW; - IncreasingOnNonNegativeStep = false; - break; - } + case ICmpInst::ICMP_SLE: { + if (!LHS->getNoWrapFlags(SCEV::FlagNSW)) + return false; - if (!LHS->getNoWrapFlags(FlagsRequired)) - return false; + const SCEV *Step = LHS->getStepRecurrence(*this); - // A zero step value for LHS means the induction variable is essentially a - // loop invariant value. We don't really depend on the predicate actually - // flipping from false to true (for increasing predicates, and the other way - // around for decreasing predicates), all we care about is that *if* the - // predicate changes then it only changes from false to true. - // - // A zero step value in itself is not very useful, but there may be places - // where SCEV can prove X >= 0 but not prove X > 0, so it is helpful to be - // as general as possible. + if (isKnownNonNegative(Step)) { + Increasing = Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE; + return true; + } - if (isKnownNonNegative(LHS->getStepRecurrence(*this))) { - Increasing = IncreasingOnNonNegativeStep; - return true; + if (isKnownNonPositive(Step)) { + Increasing = Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE; + return true; + } + + return false; } - if (isKnownNonPositive(LHS->getStepRecurrence(*this))) { - Increasing = !IncreasingOnNonNegativeStep; - return true; } - return false; + llvm_unreachable("switch has default clause!"); } bool ScalarEvolution::isLoopInvariantPredicate( diff --git a/test/Transforms/IndVarSimplify/pr24356.ll b/test/Transforms/IndVarSimplify/pr24356.ll new file mode 100644 index 00000000000..eac4204c0e1 --- /dev/null +++ b/test/Transforms/IndVarSimplify/pr24356.ll @@ -0,0 +1,63 @@ +; RUN: opt -S -indvars < %s | FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-apple-macosx10.10.0" + +@a = common global i32 0, align 4 + +; Function Attrs: nounwind ssp uwtable +define void @fn1() { +; CHECK-LABEL: @fn1( +bb: + br label %bb4.preheader + +bb4.preheader: ; preds = %bb, %bb16 +; CHECK-LABEL: bb4.preheader: + %b.03 = phi i8 [ 0, %bb ], [ %tmp17, %bb16 ] +; CHECK: %tmp9 = icmp ugt i8 %b.03, 1 +; CHECK-NOT: %tmp9 = icmp ugt i8 0, 1 + + %tmp9 = icmp ugt i8 %b.03, 1 + br i1 %tmp9, label %bb4.preheader.bb18.loopexit.split_crit_edge, label %bb4.preheader.bb4.preheader.split_crit_edge + +bb4.preheader.bb4.preheader.split_crit_edge: ; preds = %bb4.preheader + br label %bb4.preheader.split + +bb4.preheader.bb18.loopexit.split_crit_edge: ; preds = %bb4.preheader + store i32 0, i32* @a, align 4 + br label %bb18.loopexit.split + +bb4.preheader.split: ; preds = %bb4.preheader.bb4.preheader.split_crit_edge + br label %bb7 + +bb4: ; preds = %bb7 + %tmp6 = icmp slt i32 %storemerge2, 0 + br i1 %tmp6, label %bb7, label %bb16 + +bb7: ; preds = %bb4.preheader.split, %bb4 + %storemerge2 = phi i32 [ 0, %bb4.preheader.split ], [ %tmp14, %bb4 ] + %tmp14 = add nsw i32 %storemerge2, 1 + br i1 false, label %bb18.loopexit, label %bb4 + +bb16: ; preds = %bb4 + %tmp14.lcssa5 = phi i32 [ %tmp14, %bb4 ] + %tmp17 = add i8 %b.03, -1 + %tmp2 = icmp eq i8 %tmp17, -2 + br i1 %tmp2, label %bb18.loopexit1, label %bb4.preheader + +bb18.loopexit: ; preds = %bb7 + br label %bb18.loopexit.split + +bb18.loopexit.split: ; preds = %bb4.preheader.bb18.loopexit.split_crit_edge, %bb18.loopexit + br label %bb18 + +bb18.loopexit1: ; preds = %bb16 + %tmp14.lcssa5.lcssa = phi i32 [ %tmp14.lcssa5, %bb16 ] + store i32 %tmp14.lcssa5.lcssa, i32* @a, align 4 + br label %bb18 + +bb18: ; preds = %bb18.loopexit1, %bb18.loopexit.split + ret void +} + +declare void @abort() -- 2.34.1