Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4676,6 +4676,140 @@ return setRange(S, SignHint, ConservativeResult); } +// Returns true iff (comparisons are unsigned): +// A <= B < C || +// B < C < A || +// C < A <= B +static bool tripleUCompare(APInt A, APInt B, APInt C) { + if (A.ule(B) && B.ult(C)) + return true; + if (B.ult(C) && C.ult(A)) + return true; + if (C.ult(A) && A.ule(B)) + return true; + return false; +} + +// Returns true iff (comparisons are signed): +// A <= B < C || +// B < C < A || +// C < A <= B +static bool tripleSCompare(APInt A, APInt B, APInt C) { + if (A.sle(B) && B.slt(C)) + return true; + if (B.slt(C) && C.slt(A)) + return true; + if (C.slt(A) && A.sle(B)) + return true; + return false; +} + +// 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) { + // By how much the expression can change. + APInt Offset = Step * MaxBECount; + + // If either Step or MaxBECount is 0, then the expression won't change, and we + // just need to return the initial range. + if (Offset == 0) + 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); + + // 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.getUnsignedMin(); + APInt StartMax = StartRange.getUnsignedMax(); + 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 this is the case, the inequality (or its rotated variants) + // StartMin < StartMax < StartMax + Offset + // will not hold. + if (!tripleUCompare(StartMin, StartMax, 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. +// BackDirection argument defines whether it's decreasing or increasing. 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, bool BackDirection, + unsigned BitWidth) { + // By how much the expression can change. + APInt Offset = Step * MaxBECount; + + // If either Step or MaxBECount is 0, then the expression won't change, and we + // just need to return the initial range. + if (Offset == 0) + 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); + + // 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.getSignedMin(); + APInt StartMax = StartRange.getSignedMax(); + 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 this is the case, the inequality (or its rotated variants) + // StartMin < StartMax < StartMax + Offset + // will not hold. + if (!tripleSCompare(StartMin, StartMax, 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 +4818,43 @@ 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); - - 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)); - } + APInt MaxBECountValue = MaxBECountRange.getUnsignedMax(); + // First, consider step signed. 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)); - } + ConstantRange StepSRange = getSignedRange(Step); - return Result; + // 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. + APInt StepSMin = StepSRange.getSignedMin(); + APInt StepSMax = StepSRange.getSignedMax(); + bool CheckBackDirection = false; + bool CheckFwdDirection = false; + + if (StepSMin.isNegative()) + CheckBackDirection = true; + if (!StepSMax.isNegative()) + CheckFwdDirection = true; + + ConstantRange SR(BitWidth, /* isFullSet = */ false); + if (CheckBackDirection) + SR = SR.unionWith( + getSignedRangeForAR(StepSMin.abs(), StartSRange, MaxBECountValue, + /* BackDirection = */ true, BitWidth)); + if (CheckFwdDirection) + SR = SR.unionWith( + getSignedRangeForAR(StepSMax, StartSRange, MaxBECountValue, + /* BackDirection = */ false, BitWidth)); + + // 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.