[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

1343–1344

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

1357

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

1357

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 *getUnsignedOverflowLimitForStep(const SCEV *Step,
   return SE->getConstant(APInt::getMinValue(BitWidth) -
                          SE->getUnsignedRange(Step).getUnsignedMax());
 }
 
 namespace {
 
 struct ExtendOpTraitsBase {
   typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *);
+  typedef APInt (APInt::*GetExtendAPIntTy)(unsigned width) const;
 };
 
 // Used to make code generic over signed and unsigned overflow.
 template <typename ExtendOp> struct ExtendOpTraits {
   // Members present:
   //
   // static const SCEV::NoWrapFlags WrapType;
   //
   // static const ExtendOpTraitsBase::GetExtendExprTy GetExtendExpr;
   //
   // static const SCEV *getOverflowLimitForStep(const SCEV *Step,
   //                                           ICmpInst::Predicate *Pred,
   //                                           ScalarEvolution *SE);
+  //
+  // static const ExtendOpTraitsBase::GetExtendAPIntTy GetExtendAPInt;
 };
 
 template <>
 struct ExtendOpTraits<SCEVSignExtendExpr> : public ExtendOpTraitsBase {
   static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
 
   static const GetExtendExprTy GetExtendExpr;
+  static const GetExtendAPIntTy GetExtendAPInt;
 
   static const SCEV *getOverflowLimitForStep(const SCEV *Step,
                                              ICmpInst::Predicate *Pred,
                                              ScalarEvolution *SE) {
     return getSignedOverflowLimitForStep(Step, Pred, SE);
   }
 };
 
 const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
     SCEVSignExtendExpr>::GetExtendExpr = &ScalarEvolution::getSignExtendExpr;
 
+const ExtendOpTraitsBase::GetExtendAPIntTy ExtendOpTraits<
+    SCEVSignExtendExpr>::GetExtendAPInt = &APInt::sext;
+
 template <>
 struct ExtendOpTraits<SCEVZeroExtendExpr> : public ExtendOpTraitsBase {
   static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
 
   static const GetExtendExprTy GetExtendExpr;
+  static const GetExtendAPIntTy GetExtendAPInt;
 
   static const SCEV *getOverflowLimitForStep(const SCEV *Step,
                                              ICmpInst::Predicate *Pred,
                                              ScalarEvolution *SE) {
     return getUnsignedOverflowLimitForStep(Step, Pred, SE);
   }
 };
 
 const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
     SCEVZeroExtendExpr>::GetExtendExpr = &ScalarEvolution::getZeroExtendExpr;
+
+const ExtendOpTraitsBase::GetExtendAPIntTy ExtendOpTraits<
+    SCEVZeroExtendExpr>::GetExtendAPInt = &APInt::zext;
 }
 
 // The recurrence AR has been shown to have no signed/unsigned wrap or something
 // close to it. Typically, if we can prove NSW/NUW for AR, then we can just as
 // easily prove NSW/NUW for its preincrement or postincrement sibling. This
 // allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
 // Start),+,Step} => {(Step + sext/zext(Start),+,Step} As a result, the
 // expression "Step + sext/zext(PreIncAR)" is congruent with
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)}
+//
+// 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();
+  unsigned BitWidth = StartAI.getBitWidth();
+
+  auto Extend = [&](const APInt &AI) {
+    auto ExtendAPInt = ExtendOpTraits<ExtendOpTy>::GetExtendAPInt;
+    return (AI.*ExtendAPInt)(BitWidth * 2);
+  };
+
+  for (unsigned Delta : {-2, -1, 1, 2}) {
+    APInt DeltaAI(BitWidth, Delta, true);
+    APInt PreStartAI = StartAI - DeltaAI;
+
+    if (Extend(PreStartAI + DeltaAI) != (Extend(PreStartAI) + Extend(DeltaAI)))
+      continue;  // proves (3)
+
+    const SCEV *PreStart = getConstant(PreStartAI);
+
+    // 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
+}