[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

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

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

10224

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

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

10224

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

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

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

10232

Will do.

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.

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?");
+  const SCEV *Step = getStepRecurrence(SE);
+  // There is a temptation to just call SE.getAddExpr(this, Step), but in this
+  // case we cannot guarantee that the value returned will be an AddRec. So we
+  // make it explicitly. Given that the last op of this is non zero, it will
+  // also be non-zero if we add this and Step one by one operand. This does give
+  // us a guarantee of result being SCEVAddRec.
+  SmallVector<const SCEV *, 3> Ops;
+  if (const SCEVAddRecExpr *StepAR = dyn_cast<SCEVAddRecExpr>(Step)) {
+    assert(StepAR->getNumOperands() < this->getNumOperands() &&
+           "Step of an AddRec is not less complex than the AddRec?");
+    for (unsigned i = 0, e = StepAR->getNumOperands(); i < e; ++i)
+      Ops.push_back(SE.getAddExpr(getOperand(i), StepAR->getOperand(i)));
+    Ops.insert(Ops.end(), op_begin() + StepAR->getNumOperands(), op_end());
+  } else {
+    Ops.push_back(SE.getAddExpr(getOperand(0), Step));
+    Ops.insert(Ops.end(), op_begin() + 1, op_end());
+  }
+  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;

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}