[SCEV] make SCEV smarter about proving no-wrap.

[sanjoy]

Summary

Teach SCEV to prove no overflow for an add recurrence by proving
something about the range of another add recurrence a loop-invariant
distance away from it.

[atrick]

The logic is great. But we really need to determine whether computing SCEV for each recurrence 5 times is worthwhile. Please do some compile time experiments where SCEV is taking more time than usual to find out how much worse this makes it.

Why did you do this rather than checking SCEV's for existing phis? (I realize this is strictly better, but I'm curious about your motivation given that this is potentially a lot of extra work)

lib/Analysis/ScalarEvolution.cpp

1332–1333

I would like better comments here. It should show the formula.

e.g.

{start - delta,+,step} ult (INT_MAX - delta)

[sanjoy]

In D7980#133867, @atrick wrote:

The logic is great. But we really need to determine whether computing SCEV for each recurrence 5 times is worthwhile. Please do some compile time experiments where SCEV is taking more time than usual to find out how much worse this makes it.

Sure, I'll run some experiments and measure the compile time.

Why did you do this rather than checking SCEV's for existing phis?

Do you mean just checking the folding set for an _existing_ SCEVAddRec instead of SE.getAddRecExpr(PreStart, Step, AR->getLoop(), SCEV::FlagAnyWrap)? That sounds like a very good idea, I'll try that.

[sanjoy]

Addresses review.

When writing down a proof for proveNoWrapByVaryingStart (thanks for
prodding me to do that!) I realized that the first version had a bug

• we need to prove (S-X)+X does not overflow for the inference to be

valid. This current version addresses that.

The current version also swaps out a full SCEVAddRecExpr construction
and just looks at the UniqueSCEVs set instead, and gives up if there
isn't a pre-existing add recurrence of the form we need. This should
address the compile time issue.

[atrick]

Otherwise looks great!

lib/Analysis/ScalarEvolution.cpp

1346

I still don't see the bug. How can (3) be false with (1) and (2)? A counter example would help.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

1346

You're right, (3) is just (1) in the 0th iteration. I'll fix this.

[sanjoy]

• Address review

[atrick]

LGTM

include/llvm/Analysis/ScalarEvolution.h

private:
 
     /// forgetMemoizedResults - Drop memoized information computed for S.
     void forgetMemoizedResults(const SCEV *S);
 
     /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
     /// pointer.
     bool checkValidity(const SCEV *S) const;
 
+    // Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be equal
+    // to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is equivalent to
+    // proving no signed (resp. unsigned) wrap in {`Start`,+,`Step`} if
+    // `ExtendOpTy` is `SCEVSignExtendExpr` (resp. `SCEVZeroExtendExpr`).
+    //
+    template<typename ExtendOpTy>
+    bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
+                                   const Loop *L);
+
   public:
     static char ID; // Pass identification, replacement for typeid
     ScalarEvolution();
 
     LLVMContext &getContext() const { return F->getContext(); }
 
     /// isSCEVable - Test if values of the given type are analyzable within
     /// the SCEV framework. This primarily includes integer types, and it

lib/Analysis/ScalarEvolution.cpp

static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty,
   const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE);
   if (!PreStart)
     return (SE->*GetExtendExpr)(AR->getStart(), Ty);
 
   return SE->getAddExpr((SE->*GetExtendExpr)(AR->getStepRecurrence(*SE), Ty),
                         (SE->*GetExtendExpr)(PreStart, Ty));
 }
 
+// Try to prove away overflow by looking at "nearby" add recurrences.  A
+// motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
+// does not itself wrap then we can conclude that `{1,+,4}` is `nuw`.
+//
+// Formally:
+//
+//     {S,+,X} == {S-T,+,X} + T
+//  => Ext({S,+,X}) == Ext({S-T,+,X} + T)
+//
+// If ({S-T,+,X} + T) does not overflow  ... (1)
+//
+//  RHS == Ext({S-T,+,X} + T) == Ext({S-T,+,X}) + Ext(T)
+//
+// If {S-T,+,X} does not overflow  ... (2)
+//
+//  RHS == Ext({S-T,+,X}) + Ext(T) == {Ext(S-T),+,Ext(X)} + Ext(T)
+//      == {Ext(S-T)+Ext(T),+,Ext(X)}
+//
+// If (S-T)+T does not overflow  ... (3)
+//
+//  RHS == {Ext(S-T)+Ext(T),+,Ext(X)} == {Ext(S-T+T),+,Ext(X)}
+//      == {Ext(S),+,Ext(X)} == LHS
+//
+// Thus, if (1), (2) and (3) are true for some T, then
+//   Ext({S,+,X}) == {Ext(S),+,Ext(X)}
+//
+// (3) is implied by (1) -- "(S-T)+T does not overflow" is simply "({S-T,+,X}+T)
+// does not overflow" restricted to the 0th iteration.  Therefore we only need
+// to check for (1) and (2).
+//
+// In the current context, S is `Start`, X is `Step`, Ext is `ExtendOpTy` and T
+// is `Delta` (defined below).
+//
+template <typename ExtendOpTy>
+bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start,
+                                                const SCEV *Step,
+                                                const Loop *L) {
+  auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
+
+  // We restrict `Start` to a constant to prevent SCEV from spending too much
+  // time here.  It is correct (but more expensive) to continue with a
+  // non-constant `Start` and do a general SCEV subtraction to compute
+  // `PreStart` below.
+  //
+  const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
+  if (!StartC)
+    return false;
+
+  APInt StartAI = StartC->getValue()->getValue();
+
+  for (unsigned Delta : {-2, -1, 1, 2}) {
+    const SCEV *PreStart = getConstant(StartAI - Delta);
+
+    // Give up if we don't already have the add recurrence we need because
+    // actually constructing an add recurrence is relatively expensive.
+    const SCEVAddRecExpr *PreAR = [&]() {
+      FoldingSetNodeID ID;
+      ID.AddInteger(scAddRecExpr);
+      ID.AddPointer(PreStart);
+      ID.AddPointer(Step);
+      ID.AddPointer(L);
+      void *IP = nullptr;
+      return static_cast<SCEVAddRecExpr *>(
+        UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+    }();
+
+    if (PreAR && PreAR->getNoWrapFlags(WrapType)) {  // proves (2)
+      const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
+      ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
+      const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
+          DeltaS, &Pred, this);
+      if (Limit && isKnownPredicate(Pred, PreAR, Limit))  // proves (1)
+        return true;
+    }
+  }
+
+  return false;
+}
+
 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
                                                Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
if (AR->isAffine()) {
             const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(
                 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this),
                 getSignExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
           }
         }
       }
+
+      if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
+        const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
+        return getAddRecExpr(
+            getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this),
+            getZeroExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
+      }
     }
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
if (AR->isAffine()) {
         if (C1.isStrictlyPositive() && C2.isStrictlyPositive() && C2.ugt(C1) &&
             C2.isPowerOf2()) {
           Start = getSignExtendExpr(Start, Ty);
           const SCEV *NewAR = getAddRecExpr(getConstant(AR->getType(), 0), Step,
                                             L, AR->getNoWrapFlags());
           return getAddExpr(Start, getSignExtendExpr(NewAR, Ty));
         }
       }
+
+      if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
+        const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
+        return getAddRecExpr(
+            getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this),
+            getSignExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
+      }
     }
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);

test/Analysis/ScalarEvolution/nowrap-preinc-limits.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define void @f(i1* %condition) {
+; CHECK-LABEL: Classifying expressions for: @f
+ entry: 
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
+  %idx.inc = add nsw i32 %idx, 1
+
+  %idx.inc2 = add i32 %idx.inc, 1
+  %idx.inc2.zext = zext i32 %idx.inc2 to i64
+
+; CHECK: %idx.inc2.zext = zext i32 %idx.inc2 to i64
+; CHECK-NEXT: -->  {2,+,1}<nuw><%loop>
+
+  %c = load volatile i1, i1* %condition
+  br i1 %c, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @g(i1* %condition) {
+; CHECK-LABEL: Classifying expressions for: @g
+ entry:
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
+  %idx.inc = add nsw i32 %idx, 3
+
+  %idx.inc2 = add i32 %idx.inc, -1
+  %idx.inc2.sext = sext i32 %idx.inc2 to i64
+; CHECK: %idx.inc2.sext = sext i32 %idx.inc2 to i64
+; CHECK-NEXT: -->  {2,+,3}<nuw><nsw><%loop>
+
+  %c = load volatile i1, i1* %condition
+  br i1 %c, label %loop, label %exit
+
+ exit:
+  ret void
+}