[SCEV][NFC] evaluateAtIteration may produce incorrect result if accuracy of evalutation point is not enough.

[ebrevnov]

Summary

Originally these changes were part of https://reviews.llvm.org/D65276. Decided to have a separate review for changes aimed at improving evaluateAtIteration. The problem is that evaluateAtIteration can produce incorrect result under some circumstances. For example for evaluation 32-bit nested recurrence of level 2 we need to carry all calculations in 33-bits. This requirement applies to input iteration expression as well. Thus if the input iteration expression is 32-bit and we can't prove it doesn't overflow then evaluateAtIteration will give incorrect result.

Please note that we can't just discard all cases when number of bits in iteration expression is less than required. One common case which we need to support is constant. It's known that constant never overflows thus it's safe to extend it to required number of bits. There are over cases where we can prove that expression doesn't overflow.

Thanks
Evgeniy

[ebrevnov]

Use alternative approach to ensure enough precision of 'It'

[ebrevnov]

@apilipenko what do you think now?

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

1209

Ok, I'm definitely not getting something here.

trunc(zext(y, N), M) is always equal to y when N > M and M is width of y. The zext adds zeros, then the truncate removes them.

Additionally, the comments above in the intro to this function seem to directly contradict the newly added code.

There's no test case provided to show a difference in output.

Given all of the above, I'm definitely unconvinced of this patch.

8332

This snippet is fine to land separately. This can already happen K > 1000.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

1630

This line too for same reason.

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

public:
     void setNoWrapFlags(NoWrapFlags Flags) {
       if (Flags & (FlagNUW | FlagNSW))
         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
       SubclassData |= Flags;
     }
 
     /// Return the value of this chain of recurrences at the specified
     /// iteration number.
+    ///
+    /// Note that SCEVCouldNotCompute is returned if evaluation attempt failed.
+    /// For example, if precision of \p It is less than required to perform
+    /// evaluation an instance of SCEVCouldNotCompute is returned.
     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
     /// Return the number of iterations of this loop that produce
     /// values in the specified constant range.  Another way of
     /// looking at this is that it returns the first iteration number
     /// where the value is not in the condition, thus computing the
     /// exit count.  If the iteration count can't be computed, an
     /// instance of SCEVCouldNotCompute is returned.

llvm/lib/Analysis/ScalarEvolution.cpp

static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
   APInt MultiplyFactor = OddFactorial.zext(W+1);
   MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod);
   MultiplyFactor = MultiplyFactor.trunc(W);
 
   // Calculate the product, at width T+W
   IntegerType *CalculationTy = IntegerType::get(SE.getContext(),
                                                       CalculationBits);
   const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
+
+  // 'It' should have at least 'CalculationBits' precision for the calculation
+  // to be correct. Check that by verifying that downconversion of upconverted
+  // value is not changed. In other words check that X == trunc(zext(X)).
+  if (SE.getTypeSizeInBits(It->getType()) < CalculationBits &&
+      It != SE.getTruncateExpr(Dividend, It->getType()))
+    // Return SCEVCouldNotCompute if 'It' doesn't have enough precision.
+    return SE.getCouldNotCompute();
+
   for (unsigned i = 1; i != K; ++i) {
     const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
     Dividend = SE.getMulExpr(Dividend,
                              SE.getTruncateOrZeroExtend(S, CalculationTy));
   }
 
   // Divide by 2^T
   const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
     // loop exit value of the addrec.
     if (!AddRec->getLoop()->contains(L)) {
       // To evaluate this recurrence, we need to know how many times the AddRec
       // loop iterates.  Compute this now.
       const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
 
       // Then, evaluate the AddRec.
-      return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
+      const SCEV *ValAtIter =
+          AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
+      if (!isa<SCEVCouldNotCompute>(ValAtIter)) return ValAtIter;
     }
 
     return AddRec;
   }
 
   if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
     if (Op == Cast->getOperand())

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
 
   // Promote S up to the canonical IV type, if the cast is foldable.
   const SCEV *NewS = S;
   const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
   if (isa<SCEVAddRecExpr>(Ext))
     NewS = Ext;
 
   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
-  //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
+  assert(!isa<SCEVCouldNotCompute>(V) &&
+         "Expansion of AddRec failed. Can't evaluate SCEV at iteration.");
+  // cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
 
   // Truncate the result down to the original type, if needed.
   const SCEV *T = SE.getTruncateOrNoop(V, Ty);
   return expand(T);
 }
 
 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());