From 646e047765a2d4c38555550fddde66d1e003aece Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 12 Apr 2010 07:39:33 +0000 Subject: [PATCH] Rewrite the overflow checking in the get{Signed,Unsigned}Range code for AddRecs so that it checks for overflow in the computation that it is performing, rather than just checking hasNo{Signed,Unsigned}Wrap, since those flags are for a different computation. This fixes a bug that impacts an upcoming change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@101028 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 44 ++++++++++++++++++++++++-------- 1 file changed, 34 insertions(+), 10 deletions(-) diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index e3159a924fc..32fc9b6f712 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2933,14 +2933,26 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); const SCEV *Start = AddRec->getStart(); - const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); + const SCEV *Step = AddRec->getStepRecurrence(*this); - // Check for overflow. - if (!AddRec->hasNoUnsignedWrap()) + ConstantRange StartRange = getUnsignedRange(Start); + ConstantRange StepRange = getSignedRange(Step); + ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount); + ConstantRange EndRange = + StartRange.add(MaxBECountRange.multiply(StepRange)); + + // Check for overflow. This must be done with ConstantRange arithmetic + // because we could be called from within the ScalarEvolution overflow + // checking code. + ConstantRange ExtStartRange = StartRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtMaxBECountRange = + MaxBECountRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1); + if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != + ExtEndRange) return ConservativeResult; - ConstantRange StartRange = getUnsignedRange(Start); - ConstantRange EndRange = getUnsignedRange(End); APInt Min = APIntOps::umin(StartRange.getUnsignedMin(), EndRange.getUnsignedMin()); APInt Max = APIntOps::umax(StartRange.getUnsignedMax(), @@ -3064,14 +3076,26 @@ ScalarEvolution::getSignedRange(const SCEV *S) { MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); const SCEV *Start = AddRec->getStart(); - const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); + const SCEV *Step = AddRec->getStepRecurrence(*this); - // Check for overflow. - if (!AddRec->hasNoSignedWrap()) + ConstantRange StartRange = getSignedRange(Start); + ConstantRange StepRange = getSignedRange(Step); + ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount); + ConstantRange EndRange = + StartRange.add(MaxBECountRange.multiply(StepRange)); + + // Check for overflow. This must be done with ConstantRange arithmetic + // because we could be called from within the ScalarEvolution overflow + // checking code. + ConstantRange ExtStartRange = StartRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtMaxBECountRange = + MaxBECountRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtEndRange = EndRange.sextOrTrunc(BitWidth*2+1); + if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != + ExtEndRange) return ConservativeResult; - ConstantRange StartRange = getSignedRange(Start); - ConstantRange EndRange = getSignedRange(End); APInt Min = APIntOps::smin(StartRange.getSignedMin(), EndRange.getSignedMin()); APInt Max = APIntOps::smax(StartRange.getSignedMax(), -- 2.34.1