From 9f93d30a26ae9928f886ef7271efeafcea2a00a6 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Sat, 24 Apr 2010 03:09:42 +0000 Subject: [PATCH] ScalarEvolution support for <= and >= loops. Also, generalize ScalarEvolutions's min and max recognition to handle some new forms of min and max that this change makes more common. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102234 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 127 +++++++++++++++--- .../2008-11-18-LessThanOrEqual.ll | 1 - .../ScalarEvolution/2008-12-08-FiniteSGE.ll | 1 - .../2008-12-11-SMaxOverflow.ll | 6 +- test/Analysis/ScalarEvolution/sle.ll | 27 ++++ 5 files changed, 138 insertions(+), 24 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/sle.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d62eef7a81a..0ef5d84be5a 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -3416,10 +3416,22 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // fall through case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: - if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) - return getSMaxExpr(getSCEV(LHS), getSCEV(RHS)); - else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) - return getSMinExpr(getSCEV(LHS), getSCEV(RHS)); + // a >s b ? a+x : b+x -> smax(a, b)+x + // a >s b ? b+x : a+x -> smin(a, b)+x + if (LHS->getType() == U->getType()) { + const SCEV *LS = getSCEV(LHS); + const SCEV *RS = getSCEV(RHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, RS); + if (LDiff == RDiff) + return getAddExpr(getSMaxExpr(LS, RS), LDiff); + LDiff = getMinusSCEV(LA, RS); + RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getSMinExpr(LS, RS), LDiff); + } break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: @@ -3427,28 +3439,52 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // fall through case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: - if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) - return getUMaxExpr(getSCEV(LHS), getSCEV(RHS)); - else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) - return getUMinExpr(getSCEV(LHS), getSCEV(RHS)); + // a >u b ? a+x : b+x -> umax(a, b)+x + // a >u b ? b+x : a+x -> umin(a, b)+x + if (LHS->getType() == U->getType()) { + const SCEV *LS = getSCEV(LHS); + const SCEV *RS = getSCEV(RHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, RS); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, RS), LDiff); + LDiff = getMinusSCEV(LA, RS); + RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getUMinExpr(LS, RS), LDiff); + } break; case ICmpInst::ICMP_NE: - // n != 0 ? n : 1 -> umax(n, 1) - if (LHS == U->getOperand(1) && - isa(U->getOperand(2)) && - cast(U->getOperand(2))->isOne() && + // n != 0 ? n+x : 1+x -> umax(n, 1)+x + if (LHS->getType() == U->getType() && isa(RHS) && - cast(RHS)->isZero()) - return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(2))); + cast(RHS)->isZero()) { + const SCEV *One = getConstant(LHS->getType(), 1); + const SCEV *LS = getSCEV(LHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, One); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, One), LDiff); + } break; case ICmpInst::ICMP_EQ: - // n == 0 ? 1 : n -> umax(n, 1) - if (LHS == U->getOperand(2) && - isa(U->getOperand(1)) && - cast(U->getOperand(1))->isOne() && + // n == 0 ? 1+x : n+x -> umax(n, 1)+x + if (LHS->getType() == U->getType() && isa(RHS) && - cast(RHS)->isZero()) - return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(1))); + cast(RHS)->isZero()) { + const SCEV *One = getConstant(LHS->getType(), 1); + const SCEV *LS = getSCEV(LHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, One); + const SCEV *RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, One), LDiff); + } break; default: break; @@ -3885,6 +3921,57 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, if (!isa(Ret)) return Ret; } + // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by + // adding or subtracting 1 from one of the operands. + switch (Cond) { + case ICmpInst::ICMP_SLE: + if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Cond = ICmpInst::ICMP_SLT; + } else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), -1, true), LHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Cond = ICmpInst::ICMP_SLT; + } + break; + case ICmpInst::ICMP_SGE: + if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), -1, true), RHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Cond = ICmpInst::ICMP_SGT; + } else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Cond = ICmpInst::ICMP_SGT; + } + break; + case ICmpInst::ICMP_ULE: + if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), 1, false), RHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Cond = ICmpInst::ICMP_ULT; + } else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), -1, false), LHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Cond = ICmpInst::ICMP_ULT; + } + break; + case ICmpInst::ICMP_UGE: + if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), -1, false), RHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Cond = ICmpInst::ICMP_UGT; + } else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), 1, false), LHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Cond = ICmpInst::ICMP_UGT; + } + break; + default: + break; + } + switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) diff --git a/test/Analysis/ScalarEvolution/2008-11-18-LessThanOrEqual.ll b/test/Analysis/ScalarEvolution/2008-11-18-LessThanOrEqual.ll index 06637b5eaee..335bbaf9ad0 100644 --- a/test/Analysis/ScalarEvolution/2008-11-18-LessThanOrEqual.ll +++ b/test/Analysis/ScalarEvolution/2008-11-18-LessThanOrEqual.ll @@ -1,6 +1,5 @@ ; RUN: opt < %s -analyze -scalar-evolution |& \ ; RUN: grep {Loop %bb: backedge-taken count is (7 + (-1 \\* %argc))} -; XFAIL: * define i32 @main(i32 %argc, i8** %argv) nounwind { entry: diff --git a/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll b/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll index 226221b297f..25a0434b29e 100644 --- a/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll +++ b/test/Analysis/ScalarEvolution/2008-12-08-FiniteSGE.ll @@ -1,5 +1,4 @@ ; RUN: opt < %s -analyze -scalar-evolution | grep {backedge-taken count is 255} -; XFAIL: * define i32 @foo(i32 %x, i32 %y, i32* %lam, i32* %alp) nounwind { bb1.thread: diff --git a/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll b/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll index 33a74795d2e..12254e37dcc 100644 --- a/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll +++ b/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll @@ -1,5 +1,7 @@ -; RUN: opt < %s -analyze -scalar-evolution | grep {0 smax} -; XFAIL: * +; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s + +; CHECK: @f +; CHECK: Loop %bb16.preheader: backedge-taken count is (-1 + %c.idx.val) define i32 @f(i32 %c.idx.val) { diff --git a/test/Analysis/ScalarEvolution/sle.ll b/test/Analysis/ScalarEvolution/sle.ll new file mode 100644 index 00000000000..f38f6b63dce --- /dev/null +++ b/test/Analysis/ScalarEvolution/sle.ll @@ -0,0 +1,27 @@ +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s + +; ScalarEvolution should be able to use nsw information to prove that +; this loop has a finite trip count. + +; CHECK: @le +; CHECK: Loop %for.body: backedge-taken count is %n +; CHECK: Loop %for.body: max backedge-taken count is 9223372036854775807 + +define void @le(i64 %n, double* nocapture %p) nounwind { +entry: + %cmp6 = icmp slt i64 %n, 0 ; [#uses=1] + br i1 %cmp6, label %for.end, label %for.body + +for.body: ; preds = %for.body, %entry + %i = phi i64 [ %i.next, %for.body ], [ 0, %entry ] ; [#uses=2] + %arrayidx = getelementptr double* %p, i64 %i ; [#uses=2] + %t4 = load double* %arrayidx ; [#uses=1] + %mul = fmul double %t4, 2.200000e+00 ; [#uses=1] + store double %mul, double* %arrayidx + %i.next = add nsw i64 %i, 1 ; [#uses=2] + %cmp = icmp sgt i64 %i.next, %n ; [#uses=1] + br i1 %cmp, label %for.end, label %for.body + +for.end: ; preds = %for.body, %entry + ret void +} -- 2.34.1