[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 ↗

(On Diff #222096)

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 ↗

(On Diff #222096)

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

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

1630 ↗

(On Diff #222096)

This line too for same reason.

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 an
+    /// evaluation 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.

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);
+
+  // Zero extension indicates insufficient precision of incoming "It".
+  // In this case result of calculations may be incorrect. Go ahead and return
+  // SCEVCouldNotCompute.
+  if (isa<SCEVZeroExtendExpr>(Dividend))
+    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));
case scUnknown:
     // All non-instruction values are loop invariant.  All instructions are loop
     // invariant if they are not contained in the specified loop.
     // Instructions are never considered invariant in the function body
     // (null loop) because they are defined within the "loop".
     if (auto *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
       return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
     return LoopInvariant;
   case scCouldNotCompute:
-    llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+    return LoopVariant;
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
   return getLoopDisposition(S, L) == LoopInvariant;
 }
 

test/Transforms/IndVarSimplify/exit_value_tests.ll

Loop:   ; preds = %Loop, %0
   %c = icmp eq i32 %X, %N    ; <i1> [#uses=1]
   br i1 %c, label %Out, label %Loop
 
 Out:    ; preds = %Loop
   %Y = mul i32 %X, %X   ; <i32> [#uses=1]
   ret i32 %Y
 }
 
-define i32 @NSquareOver2(i32 %N) {
-; <label>:0
-; CHECK-LABEL: @NSquareOver2(
-; CHECK-NEXT:  Out:
-; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N:%.*]] to i33
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[N]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i33
-; CHECK-NEXT:    [[TMP3:%.*]] = mul i33 [[TMP0]], [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i33 [[TMP3]], 1
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i33 [[TMP4]] to i32
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[N]], [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 15
-; CHECK-NEXT:    ret i32 [[TMP7]]
-;
-  br label %Loop
-
-Loop:   ; preds = %Loop, %0
-  %X = phi i32 [ 0, %0 ], [ %X2, %Loop ]    ; <i32> [#uses=3]
-  %Y = phi i32 [ 15, %0 ], [ %Y2, %Loop ]    ; <i32> [#uses=1]
-  %Y2 = add i32 %Y, %X    ; <i32> [#uses=2]
-  %X2 = add i32 %X, 1   ; <i32> [#uses=1]
-  %c = icmp eq i32 %X, %N    ; <i1> [#uses=1]
-  br i1 %c, label %Out, label %Loop
-
-Out:    ; preds = %Loop
-  ret i32 %Y2
-}
-
 define i32 @strength_reduced() {
 ; <label>:0
 ; CHECK-LABEL: @strength_reduced(
 ; CHECK-NEXT:  Out:
 ; CHECK-NEXT:    ret i32 500500
 ;
   br label %Loop