Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4676,6 +4676,113 @@ return setRange(S, SignHint, ConservativeResult); } +// Given a StartRange, Step and MaxBECount for an expression compute a range of +// values that the expression can take. Initially, the expression has a value +// from StartRange and then is changed by Step up to MaxBECount times. All +// values and operations are considered unsigned and of BitWidth size. If the +// expression can potentially overflow, return full range. +static ConstantRange getUnsignedRangeForAR(APInt Step, ConstantRange StartRange, + APInt MaxBECount, + unsigned BitWidth) { + // If either Step or MaxBECount is 0, then the expression won't change, and we + // just need to return the initial range. + if (Step == 0 || MaxBECount == 0) + return StartRange; + if (StartRange.isFullSet()) + return StartRange; + + // Check if Offset is more than full span of BitWidth. If it is, the + // expression is guaranteed to overflow. + if (APInt::getMaxValue(StartRange.getBitWidth()).udiv(Step).ult(MaxBECount)) + return ConstantRange(BitWidth, /* isFullSet = */ true); + if (APInt::getMaxValue(StartRange.getBitWidth()) == MaxBECount * Step) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + // Offset is by how much the expression can change. Checks above guarantee no + // overflow here. + APInt Offset = Step * MaxBECount; + + // Minimum value of the final range will match the minimal value of + // StartRange. + // Maximum value will increase by Offset (provided there is no overflow). + APInt StartMin = StartRange.getLower(); + APInt StartMax = StartRange.getUpper() - 1; + APInt MovedBoundary = StartMax + Offset; + + // It's possible that after increasing StartMax by Offset, the new value will + // fall into the initial range (due to wrap around). This means that the + // expression can take any value in this bitwidth, and we have to return full + // range. + if (StartRange.contains(MovedBoundary)) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + // If we end up with full range, return a proper full range. + if (StartMin == MovedBoundary + 1) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + // No overflow detected, return [StartMin, StartMax + Offset + 1) range. + return ConstantRange(StartMin, MovedBoundary + 1); +} + +// Given a StartRange, Step and MaxBECount for an expression compute a range of +// values that the expression can take. Initially, the expression has a value +// from StartRange and then is changed by Step up to MaxBECount times. +// All values and operations are considered signed and of BitWidth size. If the +// expression can potentially overflow, return full range. +static ConstantRange getSignedRangeForAR(APInt Step, ConstantRange StartRange, + APInt MaxBECount, unsigned BitWidth) { + // If either Step or MaxBECount is 0, then the expression won't change, and we + // just need to return the initial range. + if (Step == 0 || MaxBECount == 0) + return StartRange; + if (StartRange.isFullSet()) + return StartRange; + + APInt StepAbs = Step.abs(); + bool BackDirection = Step.isNegative(); + + // Check if Offset is more than full span of BitWidth. If it is, the + // expression is guaranteed to overflow. + if (APInt::getMaxValue(StartRange.getBitWidth()).udiv(StepAbs).ult(MaxBECount)) + return ConstantRange(BitWidth, /* isFullSet = */ true); + if (APInt::getMaxValue(StartRange.getBitWidth()) == MaxBECount * StepAbs) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + // Offset is by how much the expression can change. Checks above guarantee no + // overflow here. + APInt Offset = StepAbs * MaxBECount; + + // Minimum value of the final range will match the minimal value of StartRange + // if the expression is increasing and will be decreased by Offset otherwise. + // Maximum value of the final range will match the maximal value of StartRange + // if the expression is decreasing and will be increased by Offset otherwise. + APInt StartMin = StartRange.getLower(); + APInt StartMax = StartRange.getUpper() - 1; + APInt MovedBoundary = BackDirection ? StartMin - Offset : StartMax + Offset; + + // It's possible that the new minimum/maximum value will fall into the initial + // range (due to wrap around). This means that the expression can take any + // value in this bitwidth, and we have to return full range. + if (StartRange.contains(MovedBoundary)) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + APInt NewMin, NewMax; + if (BackDirection) { + NewMin = MovedBoundary; + NewMax = StartMax; + } else { + NewMin = StartMin; + NewMax = MovedBoundary; + } + + // If we end up with full range, return a proper full range. + if (NewMin == NewMax + 1) + return ConstantRange(BitWidth, /* isFullSet = */ true); + + // No overflow detected, return [StartMin, StartMax + Offset + 1) range. + return ConstantRange(NewMin, NewMax + 1); +} + ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, const SCEV *Step, const SCEV *MaxBECount, @@ -4684,60 +4791,28 @@ getTypeSizeInBits(MaxBECount->getType()) <= BitWidth && "Precondition!"); - ConstantRange Result(BitWidth, /* isFullSet = */ true); - - // Check for overflow. This must be done with ConstantRange arithmetic - // because we could be called from within the ScalarEvolution overflow - // checking code. - MaxBECount = getNoopOrZeroExtend(MaxBECount, Start->getType()); ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount); - ConstantRange ZExtMaxBECountRange = MaxBECountRange.zextOrTrunc(BitWidth * 2); + APInt MaxBECountValue = MaxBECountRange.getUnsignedMax(); + // First, consider step signed. + ConstantRange StartSRange = getSignedRange(Start); ConstantRange StepSRange = getSignedRange(Step); - ConstantRange SExtStepSRange = StepSRange.sextOrTrunc(BitWidth * 2); - - ConstantRange StartURange = getUnsignedRange(Start); - ConstantRange EndURange = - StartURange.add(MaxBECountRange.multiply(StepSRange)); - - // Check for unsigned overflow. - ConstantRange ZExtStartURange = StartURange.zextOrTrunc(BitWidth * 2); - ConstantRange ZExtEndURange = EndURange.zextOrTrunc(BitWidth * 2); - if (ZExtStartURange.add(ZExtMaxBECountRange.multiply(SExtStepSRange)) == - ZExtEndURange) { - APInt Min = APIntOps::umin(StartURange.getUnsignedMin(), - EndURange.getUnsignedMin()); - APInt Max = APIntOps::umax(StartURange.getUnsignedMax(), - EndURange.getUnsignedMax()); - bool IsFullRange = Min.isMinValue() && Max.isMaxValue(); - if (!IsFullRange) - Result = - Result.intersectWith(ConstantRange(Min, Max + 1)); - } - ConstantRange StartSRange = getSignedRange(Start); - ConstantRange EndSRange = - StartSRange.add(MaxBECountRange.multiply(StepSRange)); - - // Check for signed overflow. This must be done with ConstantRange - // arithmetic because we could be called from within the ScalarEvolution - // overflow checking code. - ConstantRange SExtStartSRange = StartSRange.sextOrTrunc(BitWidth * 2); - ConstantRange SExtEndSRange = EndSRange.sextOrTrunc(BitWidth * 2); - if (SExtStartSRange.add(ZExtMaxBECountRange.multiply(SExtStepSRange)) == - SExtEndSRange) { - APInt Min = - APIntOps::smin(StartSRange.getSignedMin(), EndSRange.getSignedMin()); - APInt Max = - APIntOps::smax(StartSRange.getSignedMax(), EndSRange.getSignedMax()); - bool IsFullRange = Min.isMinSignedValue() && Max.isMaxSignedValue(); - if (!IsFullRange) - Result = - Result.intersectWith(ConstantRange(Min, Max + 1)); - } + // If Step can be both positive and negative, we need to find ranges for the + // maximum absolute step values in both directions and union them. + ConstantRange SR = getSignedRangeForAR(StepSRange.getSignedMin(), StartSRange, + MaxBECountValue, BitWidth); + SR = SR.unionWith(getSignedRangeForAR(StepSRange.getSignedMax(), StartSRange, + MaxBECountValue, BitWidth)); - return Result; + // Next, consider step unsigned. + ConstantRange UR = + getUnsignedRangeForAR(getUnsignedRange(Step).getUnsignedMax(), + getUnsignedRange(Start), MaxBECountValue, BitWidth); + + // Finally, intersect signed and unsigned ranges. + return SR.intersectWith(UR); } ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, Index: test/Analysis/ScalarEvolution/zext-wrap.ll =================================================================== --- test/Analysis/ScalarEvolution/zext-wrap.ll +++ test/Analysis/ScalarEvolution/zext-wrap.ll @@ -6,6 +6,10 @@ br label %bb.i bb.i: ; preds = %bb1.i, %bb.nph +; We should be able to find the range for this expression. +; CHECK: %l_95.0.i1 = phi i8 +; CHECK: --> {0,+,-1}<%bb.i> U: [2,1) S: [2,1){{ *}}Exits: 2 + %l_95.0.i1 = phi i8 [ %tmp1, %bb.i ], [ 0, %entry ] ; This cast shouldn't be folded into the addrec.