Author: nicholas Date: Sun Jul 15 21:08:00 2007 New Revision: 39893 URL: http://llvm.org/viewvc/llvm-project?rev=39893&view=rev Log: Handle decrementing loops properly. Fixes PR1533.
Always pass the constant as the second parameter to HowManyLessThans. Remove obsolete "isSigned" parameter. Added: llvm/trunk/test/Analysis/ScalarEvolution/2007-07-15-NegativeStride.ll Modified: llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h llvm/trunk/lib/Analysis/ScalarEvolution.cpp Modified: llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h?rev=39893&r1=39892&r2=39893&view=diff ============================================================================== --- llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h (original) +++ llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h Sun Jul 15 21:08:00 2007 @@ -475,10 +475,8 @@ /// looking at this is that it returns the first iteration number where the /// value is not in the condition, thus computing the exit count. If the /// iteration count can't be computed, an instance of SCEVCouldNotCompute is - /// returned. The isSigned parameter indicates whether the ConstantRange - /// should be treated as signed or unsigned. - SCEVHandle getNumIterationsInRange(ConstantRange Range, - bool isSigned) const; + /// returned. + SCEVHandle getNumIterationsInRange(ConstantRange Range) const; SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, const SCEVHandle &Conc) const; Modified: llvm/trunk/lib/Analysis/ScalarEvolution.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/ScalarEvolution.cpp?rev=39893&r1=39892&r2=39893&view=diff ============================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolution.cpp (original) +++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp Sun Jul 15 21:08:00 2007 @@ -1671,8 +1671,7 @@ ConstantRange CompRange( ICmpInst::makeConstantRange(Cond, CompVal->getValue())); - SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, - false /*Always treat as unsigned range*/); + SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange); if (!isa<SCEVCouldNotCompute>(Ret)) return Ret; } } @@ -1696,7 +1695,8 @@ break; } case ICmpInst::ICMP_SGT: { - SCEVHandle TC = HowManyLessThans(RHS, LHS, L); + SCEVHandle TC = HowManyLessThans(SCEV::getNegativeSCEV(LHS), + SCEV::getNegativeSCEV(RHS), L); if (!isa<SCEVCouldNotCompute>(TC)) return TC; break; } @@ -2406,8 +2406,7 @@ /// this is that it returns the first iteration number where the value is not in /// the condition, thus computing the exit count. If the iteration count can't /// be computed, an instance of SCEVCouldNotCompute is returned. -SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, - bool isSigned) const { +SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { if (Range.isFullSet()) // Infinite loop. return new SCEVCouldNotCompute(); @@ -2419,7 +2418,7 @@ SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop()); if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted)) return ShiftedAddRec->getNumIterationsInRange( - Range.subtract(SC->getValue()->getValue()),isSigned); + Range.subtract(SC->getValue()->getValue())); // This is strange and shouldn't happen. return new SCEVCouldNotCompute(); } @@ -2443,17 +2442,16 @@ // If this is an affine expression then we have this situation: // Solve {0,+,A} in Range === Ax in Range - // Since we know that zero is in the range, we know that the upper value of - // the range must be the first possible exit value. Also note that we - // already checked for a full range. - const APInt &Upper = Range.getUpper(); - APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue(); + // We know that zero is in the range. If A is positive then we know that + // the upper value of the range must be the first possible exit value. + // If A is negative then the lower of the range is the last possible loop + // value. Also note that we already checked for a full range. APInt One(getBitWidth(),1); + APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue(); + APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower(); - // The exit value should be (Upper+A-1)/A. - APInt ExitVal(Upper); - if (A != One) - ExitVal = (Upper + A - One).sdiv(A); + // The exit value should be (End+A)/A. + APInt ExitVal = (End + A).sdiv(A); ConstantInt *ExitValue = ConstantInt::get(ExitVal); // Evaluate at the exit value. If we really did fall out of the valid Added: llvm/trunk/test/Analysis/ScalarEvolution/2007-07-15-NegativeStride.ll URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/test/Analysis/ScalarEvolution/2007-07-15-NegativeStride.ll?rev=39893&view=auto ============================================================================== --- llvm/trunk/test/Analysis/ScalarEvolution/2007-07-15-NegativeStride.ll (added) +++ llvm/trunk/test/Analysis/ScalarEvolution/2007-07-15-NegativeStride.ll Sun Jul 15 21:08:00 2007 @@ -0,0 +1,20 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution 2>&1 | grep "Loop bb: 100 iterations" +; PR1533 + [EMAIL PROTECTED] = weak global [101 x i32] zeroinitializer, align 32 ; <[100 x i32]*> [#uses=1] + +define void @loop(i32 %x) { +entry: + br label %bb + +bb: ; preds = %bb, %entry + %i.01.0 = phi i32 [ 100, %entry ], [ %tmp4, %bb ] ; <i32> [#uses=2] + %tmp1 = getelementptr [101 x i32]* @array, i32 0, i32 %i.01.0 ; <i32*> [#uses=1] + store i32 %x, i32* %tmp1 + %tmp4 = add i32 %i.01.0, -1 ; <i32> [#uses=2] + %tmp7 = icmp sgt i32 %tmp4, -1 ; <i1> [#uses=1] + br i1 %tmp7, label %bb, label %return + +return: ; preds = %bb + ret void +} _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits