[SCEV] Disable canonical expansion for nested recurrences.

[ebrevnov]

Summary

This is a continuation of https://reviews.llvm.org/D62563. Essentially I took latest change proposed by Artur and tried to address Philip's concern "Does this mean that evaluateAtIteration may return an incorrect result? If so, I'd very much like to see an assert which trips on that usage."

[apilipenko]

The original patch introduces a function minIterationWidthForEvaluateAtIteration. This way it exposes the limitation of evaluateAtIteration through the API and makes it possible for the user to choose the proper It width (e.g. like I did in the first revision https://reviews.llvm.org/D62563?vs=on&id=201795). What was the reason to remove it?

include/llvm/Analysis/ScalarEvolutionExpressions.h

347–349

Because you removed minIterationWidthForEvaluateAtIteration from the API, now the description on evaluateAtIteration is very vague. I'd prefer to specify this limitation more specifically.

lib/Analysis/ScalarEvolution.cpp

1208–1212

Any reason to express this check in this way and not as a comparison of CalculationBits with It bitwidth?

11670

I don't think that it makes much sense to ask loop disposition of scCouldNotCompute. I think the caller of this API should handle scCouldNotCompute case instead.

[ebrevnov]

This comment was removed by ebrevnov.

[ebrevnov]

This comment was removed by ebrevnov.

[ebrevnov]

Splitting exitsting patch to two parts. The first one is an actual fix for the problem. The second one is an enhancement to evaluateAtIteration which is going to be reviewd and committed separately.

[ebrevnov]

This comment was removed by ebrevnov.

[ebrevnov]

ping @apilipenko

[ebrevnov]

ping @apilipenko

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