[SCEV] Be less conservative when extending bitwidths for computing ranges.

[mzolotukhin]

Summary

In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C,
where ranges for A, B, and C are known. To avoid overflow, we need to
operate on a bigger bitwidth, and originally we chose 2*x+1 for this
(x being the original bitwidth). However, it is safe to use just 2*x:

A+B*C <= (2^x - 1) + (2^x - 1)*(2^x - 1) =

=  2^x - 1 + 2^2x - 2^x - 2^x + 1 =
= 2^2x - 2^x <= 2^2x - 1

Unnecessary extending of bitwidths results in noticeable slowdowns: ranges
perform arithmetic operations using APInt, which are much slower when bitwidths
are bigger than 64.

[sanjoy]

lgtm

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
   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 + 1);
+  ConstantRange ZExtMaxBECountRange = MaxBECountRange.zextOrTrunc(BitWidth * 2);
 
   ConstantRange StepSRange = getSignedRange(Step);
-  ConstantRange SExtStepSRange = StepSRange.sextOrTrunc(BitWidth * 2 + 1);
+  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 + 1);
-  ConstantRange ZExtEndURange = EndURange.zextOrTrunc(BitWidth * 2 + 1);
+  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 + 1);
-  ConstantRange SExtEndSRange = EndSRange.sextOrTrunc(BitWidth * 2 + 1);
+  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)