[SCEV] Mark AddExprs as nsw or nuw if legal

[sanjoy]

Summary

This uses ScalarEvolution::getRange and not potentially control
dependent nsw and nuw bits on the arithmetic instruction.

[sanjoy]

• rebase over changes to D13612

[sanjoy]

• review. Note the tests passing are gated on D13677

[sanjoy]

• actually add tests

[sanjoy]

ping!

[reames]

lib/Analysis/ScalarEvolution.cpp

1946–1964

Comment?

1949

Given we could have learned a new fact at line 1643, shouldn't this be using that new fact?

[sanjoy]

• address review

[reames]

LGTM

lib/Analysis/ScalarEvolution.cpp

 }
 
 // We're trying to construct a SCEV of type `Type' with `Ops' as operands and
 // `OldFlags' as can't-wrap behavior.  Infer a more aggressive set of
 // can't-overflow flags for the operation if possible.
 static SCEV::NoWrapFlags
 StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
                       const SmallVectorImpl<const SCEV *> &Ops,
-                      SCEV::NoWrapFlags OldFlags) {
+                      SCEV::NoWrapFlags Flags) {
   using namespace std::placeholders;
+  typedef OverflowingBinaryOperator OBO;
 
   bool CanAnalyze =
       Type == scAddExpr || Type == scAddRecExpr || Type == scMulExpr;
   (void)CanAnalyze;
   assert(CanAnalyze && "don't call from other places!");
 
   int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
   SCEV::NoWrapFlags SignOrUnsignWrap =
-      ScalarEvolution::maskFlags(OldFlags, SignOrUnsignMask);
+      ScalarEvolution::maskFlags(Flags, SignOrUnsignMask);
 
   // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
   auto IsKnownNonNegative =
     std::bind(std::mem_fn(&ScalarEvolution::isKnownNonNegative), SE, _1);
 
   if (SignOrUnsignWrap == SCEV::FlagNSW &&
       std::all_of(Ops.begin(), Ops.end(), IsKnownNonNegative))
-    return ScalarEvolution::setFlags(OldFlags,
-                                     (SCEV::NoWrapFlags)SignOrUnsignMask);
+    Flags =
+        ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
+
+  if (SignOrUnsignWrap != SignOrUnsignMask && Type == scAddExpr &&
+      Ops.size() == 2 && isa<SCEVConstant>(Ops[0])) {
+    const APInt &C = cast<SCEVConstant>(Ops[0])->getValue()->getValue();
+    if (!(SignOrUnsignWrap & SCEV::FlagNSW)) {
+      auto NSWRegion =
+        ConstantRange::makeNoWrapRegion(Instruction::Add, C, OBO::NoSignedWrap);
+      if (NSWRegion.contains(SE->getSignedRange(Ops[1])))
+        Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
+    }
+    if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
+      auto NUWRegion =
+        ConstantRange::makeNoWrapRegion(Instruction::Add, C,
+                                        OBO::NoUnsignedWrap);
+      if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
+        Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+    }
+  }
 
-  return OldFlags;
+  return Flags;
 }
 
 /// getAddExpr - Get a canonical add expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags) {
   assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
          "only nuw or nsw allowed");

lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::makeNoWrapRegion(Instruction::BinaryOps BinOp,
                                               const APInt &C,
                                               unsigned NoWrapKind) {
   typedef OverflowingBinaryOperator OBO;
 
   assert(BinOp >= Instruction::BinaryOpsBegin &&
          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 
   assert((NoWrapKind == OBO::NoSignedWrap ||
-          NoWrapKind == OBO::NoUnsignedWrap) && "NoWrapKind invalid!");
+          NoWrapKind == OBO::NoUnsignedWrap ||
+          NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
+         "NoWrapKind invalid!");
 
   unsigned BitWidth = C.getBitWidth();
   if (BinOp != Instruction::Add)
     // Conservative answer: empty set
     return ConstantRange(BitWidth, false);
 
   if (C.isMinValue())
     // Full set: nothing signed / unsigned wraps when added to 0.
     return ConstantRange(BitWidth);
 
-  if (NoWrapKind == OBO::NoUnsignedWrap)
-    return ConstantRange(APInt::getNullValue(BitWidth), -C);
+  ConstantRange Result(BitWidth);
 
+  if (NoWrapKind & OBO::NoUnsignedWrap)
+    Result = Result.intersectWith(
+      ConstantRange(APInt::getNullValue(BitWidth), -C));
+
+  if (NoWrapKind & OBO::NoSignedWrap) {
     if (C.isStrictlyPositive())
-    return ConstantRange(APInt::getSignedMinValue(BitWidth),
-                         APInt::getSignedMinValue(BitWidth) - C);
+      Result = Result.intersectWith(
+        ConstantRange(APInt::getSignedMinValue(BitWidth),
+                      APInt::getSignedMinValue(BitWidth) - C));
+    else
+      Result = Result.intersectWith(
+        ConstantRange(APInt::getSignedMinValue(BitWidth) - C,
+                      APInt::getSignedMinValue(BitWidth)));
+  }
 
-  return ConstantRange(APInt::getSignedMinValue(BitWidth) - C,
-                       APInt::getSignedMinValue(BitWidth));
+  return Result;
 }
 
 /// isFullSet - Return true if this set contains all of the elements possible
 /// for this data-type
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 

test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll

 ; RUN: opt < %s -analyze -delinearize  | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayRef[{3,+,1}<nuw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 
 ; void foo(long n, long m, long o, long p, double A[n][m][o+p]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * (%o + %p)) + %A),+,(8 * (%o + %p) * %m)}<%for.cond4.preheader.lr.ph.us>,+,(8 * (%o + %p))}<%for.body6.lr.ph.us.us>,+,8}<%for.body6.us.us>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][(%o + %p)] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nw><%for.cond4.preheader.lr.ph.us>][{-4,+,1}<nw><%for.body6.lr.ph.us.us>][{7,+,1}<nw><%for.body6.us.us>]
+; CHECK: ArrayRef[{3,+,1}<nuw><%for.cond4.preheader.lr.ph.us>][{-4,+,1}<nw><%for.body6.lr.ph.us.us>][{7,+,1}<nw><%for.body6.us.us>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i64 %p, double* nocapture %A) nounwind uwtable {
 entry:
   %add = add nsw i64 %p, %o
   %cmp22 = icmp sgt i64 %n, 0
   br i1 %cmp22, label %for.cond1.preheader.lr.ph, label %for.end16
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry

test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll

 ; ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
 define void @infer.sext.0(i1* %c, i32 %start) {
 ; CHECK-LABEL: Classifying expressions for: @infer.sext.0
  entry:
   br label %loop
 
  loop:
   %counter = phi i32 [ 0, %entry ], [ %counter.inc, %loop ]
   %idx = phi i32 [ %start, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nsw i32 %idx, 1
   %idx.inc.sext = sext i32 %idx.inc to i64
 ; CHECK: %idx.inc.sext = sext i32 %idx.inc to i64
-; CHECK-NEXT: -->  {(1 + (sext i32 %start to i64)),+,1}<nsw><%loop>
+; CHECK-NEXT: -->  {(1 + (sext i32 %start to i64))<nsw>,+,1}<nsw><%loop>
   %condition = icmp eq i32 %counter, 1
   %counter.inc = add i32 %counter, 1
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
 define void @infer.zext.0(i1* %c, i32 %start) {
 ; CHECK-LABEL: Classifying expressions for: @infer.zext.0
  entry:
   br label %loop
 
  loop:
   %counter = phi i32 [ 0, %entry ], [ %counter.inc, %loop ]
   %idx = phi i32 [ %start, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nuw i32 %idx, 1
   %idx.inc.sext = zext i32 %idx.inc to i64
 ; CHECK: %idx.inc.sext = zext i32 %idx.inc to i64
-; CHECK-NEXT: -->  {(1 + (zext i32 %start to i64)),+,1}<nuw><%loop>
+; CHECK-NEXT: -->  {(1 + (zext i32 %start to i64))<nuw><nsw>,+,1}<nuw><%loop>
   %condition = icmp eq i32 %counter, 1
   %counter.inc = add i32 %counter, 1
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
 define void @infer.sext.1(i32 %start, i1* %c) {
 ; CHECK-LABEL: Classifying expressions for: @infer.sext.1
  entry:
   %start.mul = mul i32 %start, 4
   %start.real = add i32 %start.mul, 2
   br label %loop
 
  loop:
   %idx = phi i32 [ %start.real, %entry ], [ %idx.inc, %loop ]
   %idx.sext = sext i32 %idx to i64
 ; CHECK: %idx.sext = sext i32 %idx to i64
-; CHECK-NEXT:  -->  {(2 + (sext i32 (4 * %start) to i64)),+,2}<nsw><%loop>
+; CHECK-NEXT:  -->  {(2 + (sext i32 (4 * %start) to i64))<nsw>,+,2}<nsw><%loop>
   %idx.inc = add nsw i32 %idx, 2
   %condition = load i1, i1* %c
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
 define void @infer.sext.2(i1* %c, i8 %start) {
 ; CHECK-LABEL: Classifying expressions for: @infer.sext.2
  entry:
   %start.inc = add i8 %start, 1
   %entry.condition = icmp slt i8 %start, 127
   br i1 %entry.condition, label %loop, label %exit
 
  loop:
   %idx = phi i8 [ %start.inc, %entry ], [ %idx.inc, %loop ]
   %idx.sext = sext i8 %idx to i16
 ; CHECK: %idx.sext = sext i8 %idx to i16
-; CHECK-NEXT: -->  {(1 + (sext i8 %start to i16)),+,1}<nsw><%loop>
+; CHECK-NEXT: -->  {(1 + (sext i8 %start to i16))<nsw>,+,1}<nsw><%loop>
   %idx.inc = add nsw i8 %idx, 1
   %condition = load volatile i1, i1* %c
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
 define void @infer.zext.1(i1* %c, i8 %start) {
 ; CHECK-LABEL: Classifying expressions for: @infer.zext.1
  entry:
   %start.inc = add i8 %start, 1
   %entry.condition = icmp ult i8 %start, 255
   br i1 %entry.condition, label %loop, label %exit
 
  loop:
   %idx = phi i8 [ %start.inc, %entry ], [ %idx.inc, %loop ]
   %idx.zext = zext i8 %idx to i16
 ; CHECK: %idx.zext = zext i8 %idx to i16
-; CHECK-NEXT: -->  {(1 + (zext i8 %start to i16)),+,1}<nuw><%loop>
+; CHECK-NEXT: -->  {(1 + (zext i8 %start to i16))<nuw><nsw>,+,1}<nuw><%loop>
   %idx.inc = add nuw i8 %idx, 1
   %condition = load volatile i1, i1* %c
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }

test/Analysis/ScalarEvolution/min-max-exprs.ll

 bb2:                                              ; preds = %bb1
   %tmp3 = add nuw nsw i32 %i.0, 3
   %tmp4 = icmp slt i32 %tmp3, %N
   %tmp5 = sext i32 %tmp3 to i64
   %tmp6 = sext i32 %N to i64
   %tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp6
 ;                  min(N, i+3)
 ; CHECK:           select i1 %tmp4, i64 %tmp5, i64 %tmp6
-; CHECK-NEXT:  --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nw><%bb1> to i64))<nsw>) smax (-1 + (-1 * (sext i32 %N to i64))<nsw>)))<nsw>)
+; CHECK-NEXT:  --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nuw><%bb1> to i64))<nsw>)<nsw> smax (-1 + (-1 * (sext i32 %N to i64))<nsw>)<nsw>))<nsw>)<nsw>
   %tmp11 = getelementptr inbounds i32, i32* %A, i64 %tmp9
   %tmp12 = load i32, i32* %tmp11, align 4
   %tmp13 = shl nsw i32 %tmp12, 1
   %tmp14 = icmp sge i32 3, %i.0
   %tmp17 = add nsw i64 %i.0.1, -3
   %tmp19 = select i1 %tmp14, i64 0, i64 %tmp17
 ;                  max(0, i - 3)
 ; CHECK:           select i1 %tmp14, i64 0, i64 %tmp17

test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+define void @f0(i8* %len_addr) {
+; CHECK-LABEL: @f0(
+ entry:
+  %len = load i8, i8* %len_addr, !range !0
+  %len_norange = load i8, i8* %len_addr
+
+  %t0 = add i8 %len, 1
+  %t1 = add i8 %len, 2
+
+  %t2 = sub i8 %len, 1
+  %t3 = sub i8 %len, 2
+
+  %q0 = add i8 %len_norange, 1
+  %q1 = add i8 %len_norange, 2
+
+  %q2 = sub i8 %len_norange, 1
+  %q3 = sub i8 %len_norange, 2
+
+  ret void
+}
+
+!0 = !{i8 0, i8 126}

test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll

 }
 
 ; PR15470: LSR miscompile. The test2 function should return '1'.
 ;
 ; SCEV does not know how to denormalize chained recurrences, so make
 ; sure they aren't marked as post-inc users.
 ;
 ; CHECK-LABEL: IV Users for loop %test2.loop
-; CHECK: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us)),+,33554432}<%test2.loop> in %f = ashr i32 %sext.us, 24
+; CHECK: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us))<nuw><nsw>,+,33554432}<%test2.loop> in %f = ashr i32 %sext.us, 24
 define i32 @test2() {
 entry:
   br label %test2.loop
 
 test2.loop:
   %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test2.loop ]
   %inc11.us = add nsw i32 %inc1115.us, 1
   %cmp.us = icmp slt i32 %inc11.us, 2

unittests/IR/ConstantRangeTest.cpp

for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
 
     EXPECT_FALSE(NUWRegion.isEmptySet());
 
     auto NSWRegion =
       ConstantRange::makeNoWrapRegion(Instruction::Add, C, OBO::NoSignedWrap);
 
     EXPECT_FALSE(NSWRegion.isEmptySet());
 
+    auto NoWrapRegion =
+      ConstantRange::makeNoWrapRegion(Instruction::Add, C,
+                                      OBO::NoSignedWrap | OBO::NoUnsignedWrap);
+
+    EXPECT_FALSE(NoWrapRegion.isEmptySet());
+    EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
+
     for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
          ++I) {
       bool Overflow = false;
       I.uadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
     }
 
     for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
          ++I) {
       bool Overflow = false;
       I.sadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
     }
+
+    for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+
+      I.sadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+
+      I.uadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
   }
 }
 
 }  // anonymous namespace