Author: wmat Date: Tue Feb 12 09:09:36 2008 New Revision: 47007 URL: http://llvm.org/viewvc/llvm-project?rev=47007&view=rev Log: Fix PR2002. Suppose n is the initial value for the induction variable (with step 1) and m is its final value. Then, the correct trip count is SMAX(m,n)-n. Previously, we used SMAX(0,m-n), but m-n may overflow and can't in general be interpreted as signed.
Patch by Nick Lewycky. Added: llvm/trunk/test/Analysis/ScalarEvolution/2008-02-12-SMAXTripCount.ll Modified: llvm/trunk/lib/Analysis/ScalarEvolution.cpp Modified: llvm/trunk/lib/Analysis/ScalarEvolution.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/ScalarEvolution.cpp?rev=47007&r1=47006&r2=47007&view=diff ============================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolution.cpp (original) +++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp Tue Feb 12 09:09:36 2008 @@ -2527,19 +2527,17 @@ if (AddRec->isAffine()) { // The number of iterations for "{n,+,1} < m", is m-n. However, we don't // know that m is >= n on input to the loop. If it is, the condition - // returns true zero times. To handle both cases, we return SMAX(0, m-n). + // returns true zero times. To handle both cases, we return SMAX(m, n)-n. // FORNOW: We only support unit strides. SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType()); if (AddRec->getOperand(1) != One) return UnknownValue; - SCEVHandle Iters = SE.getMinusSCEV(RHS, AddRec->getOperand(0)); + SCEVHandle Start = AddRec->getOperand(0); + SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start) : (SCEVHandle)RHS; - if (isSigned) - return SE.getSMaxExpr(SE.getIntegerSCEV(0, RHS->getType()), Iters); - else - return Iters; + return SE.getMinusSCEV(End, Start); } return UnknownValue; Added: llvm/trunk/test/Analysis/ScalarEvolution/2008-02-12-SMAXTripCount.ll URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/test/Analysis/ScalarEvolution/2008-02-12-SMAXTripCount.ll?rev=47007&view=auto ============================================================================== --- llvm/trunk/test/Analysis/ScalarEvolution/2008-02-12-SMAXTripCount.ll (added) +++ llvm/trunk/test/Analysis/ScalarEvolution/2008-02-12-SMAXTripCount.ll Tue Feb 12 09:09:36 2008 @@ -0,0 +1,16 @@ +; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop loop: ( 100 + ( -100 smax %n)) iterations!} +; PR2002 + +define void @foo(i8 %n) { +entry: + br label %loop +loop: + %i = phi i8 [ -100, %entry ], [ %i.inc, %next ] + %cond = icmp slt i8 %i, %n + br i1 %cond, label %next, label %return +next: + %i.inc = add i8 %i, 1 + br label %loop +return: + ret void +} _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits