Fix PR21694 - Revert improper use of divide in SCEV HowFarToZero computation

[meheff]

Summary

r219517 added a use of SCEV divide in HowFarToZero computation. This divide can produce incorrect results as we are using an unsigned divide for what should be a modular divide. This change reverts back to a more conservative computation using trailing zeros.

[majnemer]

LGTM

[meheff]

Andrew, any comment on this? This just reverts back to a previous more
conservative (and correct) analysis.

Mark

[atrick]

Sorry I didn't respond. I wasn't able to easily convince myself that this fixes the problem. Since this reverts to the previous implementation, I think it's a good change. But the code is written in a way that is extremely hard to reason about.

For example:

• StepV could be negative but still be a power of two, is this expected?

• Why are we checking GetMinTrailingZeros(getNegativeSCEV(Start)) instead of GetMinTrailingZeros(Distance)?

If we can only handle counting up here, lets be more clear about that.

lib/Analysis/ScalarEvolution.cpp

if (!CountDown && CR.getUnsignedMin().isMinValue())
         ? getConstant(APInt::getMinValue(CR.getBitWidth()))
         : getConstant(APInt::getMaxValue(CR.getBitWidth()));
     else
       MaxBECount = getConstant(CountDown ? CR.getUnsignedMax()
                                          : -CR.getUnsignedMin());
     return ExitLimit(Distance, MaxBECount);
   }
 
-  // If the step exactly divides the distance then unsigned divide computes the
-  // backedge count.
-  const SCEV *Q, *R;
-  ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
-  SCEVUDivision::divide(SE, Distance, Step, &Q, &R);
-  if (R->isZero()) {
-    const SCEV *Exact =
-        getUDivExactExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
-    return ExitLimit(Exact, Exact);
-  }
+  // If Step is a power of two that evenly divides Start we know that the loop
+  // will always terminate.  Start may not be a constant so we just have the
+  // number of trailing zeros available.  This is safe even in presence of
+  // overflow as the recurrence will overflow to exactly 0.
+  const APInt &StepV = StepC->getValue()->getValue();
+  if (StepV.isPowerOf2() &&
+      GetMinTrailingZeros(getNegativeSCEV(Start)) >= StepV.countTrailingZeros())
+    return getUDivExactExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
 
   // If the condition controls loop exit (the loop exits only if the expression
   // is true) and the addition is no-wrap we can use unsigned divide to
   // compute the backedge count.  In this case, the step may not divide the
   // distance, but we don't care because if the condition is "missed" the loop
   // will have undefined behavior due to wrapping.
   if (ControlsExit && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
     const SCEV *Exact =