[SCEV] Retain AddExpr flags when subtracting a foldable constant.

[fhahn]

Summary

Currently we drop wrapping flags for expressions like (A + C1)<flags> - C2.
If C1 >= 0, C2 >= 0 and C1 >= C2, we should be able to fold (C1 - C2),
which will be >= 0 && <= C1, so we should be able to retain the flags of
the original expression. The key here is that we fold (C1 - C2) to a
non-negative constant.

I would appreciate a careful look in case I am missing a case. The logic
at the moment is quite specialized, do you think this could/should be
generalized?

This can improve results after using SimplifyICmpOperands, which may
subtract one in order to use stricter predicates, as is the case for
isKnownPredicate.

Simple example with Alive2. Not how to best construct an example without
concrete constants.

https://alive2.llvm.org/ce/z/QtNrFd

[efriedma]

For nuw, if adding a constant doesn't overflow, adding a smaller one doesn't overflow. For nsw, similarly, if adding a constant doesn't overflow, adding a constant with the same sign and smaller magnitude doesn't overflow.

Not sure I like the way the logic is written here; it's not obvious that the above rules have a common subset, so it's sort of hard to follow.

I don't think the AddExpr->getNumOperands() == 2 check is necessary.

[reames]

I agree w/Eli's comments.

[mkazantsev]

+1 to what Eli said.

[fhahn]

Thanks Eli! I split up the code to handle NSW & NUW separately. Is this along the lines of your suggestion?

[efriedma]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

if (Ok) {
       // Evaluate the expression in the larger type.
       const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1);
       // If it folds to something simple, use it. Otherwise, don't.
       if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
         return getTruncateExpr(Fold, Ty);
     }
   }
 
+  if (Ops.size() == 2) {
+    // Check if we have an expression of the form ((X + C1) - C2), where C1 and
+    // C2 can be folded in a way that allows retaining wrapping flags of (X +
+    // C1).
+    const SCEV *A = Ops[0];
+    const SCEV *B = Ops[1];
+    auto *AddExpr = dyn_cast<SCEVAddExpr>(B);
+    auto *C = dyn_cast<SCEVConstant>(A);
+    if (AddExpr && C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
+      auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
+      auto C2 = C->getAPInt();
+      SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap;
+
+      APInt ConstAdd = C1 + C2;
+      auto AddFlags = AddExpr->getNoWrapFlags();
+      // Adding a smaller constant is NUW if the original AddExpr was NUW.
+      if (ScalarEvolution::maskFlags(AddFlags, SCEV::FlagNUW) ==
+              SCEV::FlagNUW &&
+          ConstAdd.ule(C1)) {
+        PreservedFlags =
+            ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW);
+      }
+
+      // Adding a constant with the same sign and small magnitude is NSW, if the
+      // original AddExpr was NSW.
+      if (ScalarEvolution::maskFlags(AddFlags, SCEV::FlagNSW) ==
+              SCEV::FlagNSW &&
+          C1.isSignBitSet() == ConstAdd.isSignBitSet() &&
+          ConstAdd.abs().ule(C1.abs())) {
+        PreservedFlags =
+            ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW);
+      }
+
+      if (PreservedFlags != SCEV::FlagAnyWrap) {
+        SmallVector<const SCEV *, 4> NewOps(AddExpr->op_begin(),
+                                            AddExpr->op_end());
+        NewOps[0] = getConstant(ConstAdd);
+        return getAddExpr(NewOps, PreservedFlags);
+      }
+    }
+  }
+
   // Skip past any other cast SCEVs.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
     ++Idx;
 
   // If there are add operands they would be next.
   if (Idx < Ops.size()) {
     bool DeletedAdd = false;
     // If the original flags and all inlined SCEVAddExprs are NUW, use the

llvm/test/Analysis/LoopAccessAnalysis/reverse-memcheck-bounds.ll

 ;   for (i = 0; i < 10000; i++) {
 ;     B[i] = A[15000 - i] * 3;
 ;   }
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnueabi"
 
 ; CHECK: function 'f':
-; CHECK: (Low: (20000 + %a) High: (60004 + %a))
+; CHECK: (Low: (20000 + %a)<nuw> High: (60004 + %a))
 
 @B = common global i32* null, align 8
 @A = common global i32* null, align 8
 
 define void @f() {
 entry:
   %a = load i32*, i32** @A, align 8
   %b = load i32*, i32** @B, align 8

llvm/test/Transforms/IndVarSimplify/eliminate-exit-no-dl.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 
 ; Check the case where one exit has a pointer EC, and the other doesn't.
 ; Note that this test case is really really fragile.  Removing any
 ; instruction in the below causes the result to differ.  Note that the lack
 ; of a data layout (with pointer size info) is critical to getting a pointer
 ; EC returned by SCEV.
 
 @global = external global [0 x i8], align 1
 
 define void @foo() {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 add (i64 ptrtoint ([0 x i8]* @global to i64), i64 500), i64 add (i64 ptrtoint ([0 x i8]* @global to i64), i64 1))
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 add (i64 ptrtoint ([0 x i8]* @global to i64), i64 1), [[UMIN]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[TMP0]], 0
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[TMP:%.*]] = phi i8* [ [[TMP4:%.*]], [[BB7:%.*]] ], [ getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 2), [[BB:%.*]] ]
 ; CHECK-NEXT:    [[TMP4]] = getelementptr inbounds i8, i8* [[TMP]], i64 -1
 ; CHECK-NEXT:    [[TMP6:%.*]] = load i8, i8* [[TMP4]], align 1
-; CHECK-NEXT:    br i1 [[TMP1]], label [[BB7]], label [[BB11:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB7]], label [[BB11:%.*]]
 ; CHECK:       bb7:
 ; CHECK-NEXT:    [[TMP8:%.*]] = zext i8 [[TMP6]] to i64
 ; CHECK-NEXT:    br i1 true, label [[BB11]], label [[BB3]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br label %bb3