[SCEV] Make getPostIncExpr guaranteed to return AddRec

[mkazantsev]

Summary

The current implementation of getPostIncExpr invokes getAddExpr for two recurrencies
and expects that it always returns it a recurrency. But this is not guaranteed to happen if we
have reached max recursion depth or refused to make SCEV simplification for other reasons.

This patch changes its implementation so that now it always returns SCEVAddRec without
relying on getAddExpr.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

10221 ↗

(On Diff #132966)

This is unnecessary -- the step for {A,+,B,+,C} will always be {B,+,C} so we should be able to use Ops.push_back(SE.getAddExpr(getOperand(i), getOperand(i+1))); in the loop below.

10223 ↗

(On Diff #132966)

Also state why we can't guarantee it (SCEV does not simplify to fixed point etc.).

10224 ↗

(On Diff #132966)

I didn't quite understand what you meant by "last op of this is non zero".

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

10224 ↗

(On Diff #132966)

When we create an AddRecurrency, if we found out that the last stey was zero we pop it out. For example, if we add {1,+,1} and {2,+,-1}, we have {1+2,+,1-1} where the last element is zero, so it will be removed. It means that whatever the last operand in this is, it is NOT a constant zero (otherwise it would have been removed earlier). The fact that the returned value has the same value as its last element guarantees as that the returned value is an AddRec.

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

10232 ↗

(On Diff #133146)

"We know that the last operand is not a constant zero" -> might be nice to assert this.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

10232 ↗

(On Diff #133146)

Will do.

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h

public:
     /// 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.
     const SCEV *getNumIterationsInRange(const ConstantRange &Range,
                                         ScalarEvolution &SE) const;
 
     /// Return an expression representing the value of this expression
     /// one iteration of the loop ahead.
-    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
-      return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
-    }
+    const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddRecExpr;
     }
   };
 
   /// This class represents a signed maximum selection.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (auto Roots =
         return SE.getCouldNotCompute(); // Something strange happened
       }
     }
   }
 
   return SE.getCouldNotCompute();
 }
 
+const SCEVAddRecExpr *
+SCEVAddRecExpr::getPostIncExpr(ScalarEvolution &SE) const {
+  assert(getNumOperands() > 1 && "AddRec with zero step?");
+  // There is a temptation to just call getAddExpr(this, getStepRecurrence(SE)),
+  // but in this case we cannot guarantee that the value returned will be an
+  // AddRec because SCEV does not have a fixed point where it stops
+  // simplification: it is legal to return ({rec1} + {rec2}). For example, it
+  // may happen if we reach arithmetic depth limit while simplifying. So we
+  // construct the returned value explicitly.
+  SmallVector<const SCEV *, 3> Ops;
+  // If this is {A,+,B,+,C,...,+,N}, then its step is {B,+,C,+,...,+,N}, and
+  // (this + Step) is {A+B,+,B+C,+...,+,N}.
+  for (unsigned i = 0, e = getNumOperands() - 1; i < e; ++i)
+    Ops.push_back(SE.getAddExpr(getOperand(i), getOperand(i + 1)));
+  // We know that the last operand is not a constant zero (otherwise it would
+  // have been popped out earlier). This guarantees us that if the result has
+  // the same last operand, then it will also not be popped out, meaning that
+  // the returned value will be an AddRec.
+  const SCEV *Last = getOperand(getNumOperands() - 1);
+  assert(!Last->isZero() && "Recurrency with zero step?");
+  Ops.push_back(Last);
+  return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, getLoop(),
+                                               SCEV::FlagAnyWrap));
+}
+
 // Return true when S contains at least an undef value.
 static inline bool containsUndefs(const SCEV *S) {
   return SCEVExprContains(S, [](const SCEV *S) {
     if (const auto *SU = dyn_cast<SCEVUnknown>(S))
       return isa<UndefValue>(SU->getValue());
     else if (const auto *SC = dyn_cast<SCEVConstant>(S))
       return isa<UndefValue>(SC->getValue());
     return false;

llvm/trunk/test/Analysis/ScalarEvolution/pr35890.ll

+; RUN: opt < %s -scalar-evolution-max-arith-depth=0  -indvars  -S | FileCheck %s
+
+target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Check that it does not crash because SCEVAddRec's step is not an AddRec.
+
+define void @pr35890(i32* %inc_ptr, i32 %a) {
+
+; CHECK-LABEL: @pr35890(
+
+entry:
+  %inc = load i32, i32* %inc_ptr, !range !0
+  %ne.cond = icmp ne i32 %inc, 0
+  br i1 %ne.cond, label %loop, label %bail
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %a.1 = add i32 %a, 1
+  %iv.next = add i32 %iv, %a.1
+  %iv.wide = zext i32 %iv to i64
+  %iv.square = mul i64 %iv.wide, %iv.wide
+  %iv.cube = mul i64 %iv.square, %iv.wide
+  %brcond = icmp slt i64 %iv.wide, %iv.cube
+  br i1 %brcond, label %if.true, label %if.false
+
+if.true:
+  br label %backedge
+
+if.false:
+  br label %backedge
+
+backedge:
+  %loopcond = icmp slt i32 %iv, 200
+  br i1 %loopcond, label %loop, label %exit
+
+exit:
+  ret void
+
+bail:
+  ret void
+}
+
+!0 = !{i32 0, i32 100}