Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -1921,8 +1921,9 @@ static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, const SmallVectorImpl &Ops, - SCEV::NoWrapFlags OldFlags) { + SCEV::NoWrapFlags Flags) { using namespace std::placeholders; + typedef OverflowingBinaryOperator OBO; bool CanAnalyze = Type == scAddExpr || Type == scAddRecExpr || Type == scMulExpr; @@ -1931,7 +1932,7 @@ 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 = @@ -1939,10 +1940,28 @@ 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); - return OldFlags; + if (SignOrUnsignWrap != SignOrUnsignMask && Type == scAddExpr && + Ops.size() == 2 && isa(Ops[0])) { + const APInt &C = cast(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 Flags; } /// getAddExpr - Get a canonical add expression, or something simpler if Index: test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll =================================================================== --- test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll +++ test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll @@ -11,7 +11,7 @@ ; 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}<%for.i>][{-4,+,1}<%for.j>][{7,+,1}<%for.k>] +; CHECK: ArrayRef[{3,+,1}<%for.i>][{-4,+,1}<%for.j>][{7,+,1}<%for.k>] define void @foo(i64 %n, i64 %m, i64 %o, double* %A) { entry: Index: test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll =================================================================== --- test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll +++ test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll @@ -11,7 +11,7 @@ ; 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}<%for.cond4.preheader.lr.ph.us>][{-4,+,1}<%for.body6.lr.ph.us.us>][{7,+,1}<%for.body6.us.us>] +; CHECK: ArrayRef[{3,+,1}<%for.cond4.preheader.lr.ph.us>][{-4,+,1}<%for.body6.lr.ph.us.us>][{7,+,1}<%for.body6.us.us>] define void @foo(i64 %n, i64 %m, i64 %o, i64 %p, double* nocapture %A) nounwind uwtable { entry: Index: test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll =================================================================== --- test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll +++ test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll @@ -11,7 +11,7 @@ %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}<%loop> +; CHECK-NEXT: --> {(1 + (sext i32 %start to i64)),+,1}<%loop> %condition = icmp eq i32 %counter, 1 %counter.inc = add i32 %counter, 1 br i1 %condition, label %exit, label %loop @@ -31,7 +31,7 @@ %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}<%loop> +; CHECK-NEXT: --> {(1 + (zext i32 %start to i64)),+,1}<%loop> %condition = icmp eq i32 %counter, 1 %counter.inc = add i32 %counter, 1 br i1 %condition, label %exit, label %loop @@ -51,7 +51,7 @@ %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}<%loop> +; CHECK-NEXT: --> {(2 + (sext i32 (4 * %start) to i64)),+,2}<%loop> %idx.inc = add nsw i32 %idx, 2 %condition = load i1, i1* %c br i1 %condition, label %exit, label %loop @@ -71,7 +71,7 @@ %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}<%loop> +; CHECK-NEXT: --> {(1 + (sext i8 %start to i16)),+,1}<%loop> %idx.inc = add nsw i8 %idx, 1 %condition = load volatile i1, i1* %c br i1 %condition, label %exit, label %loop @@ -91,7 +91,7 @@ %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}<%loop> +; CHECK-NEXT: --> {(1 + (zext i8 %start to i16)),+,1}<%loop> %idx.inc = add nuw i8 %idx, 1 %condition = load volatile i1, i1* %c br i1 %condition, label %exit, label %loop Index: test/Analysis/ScalarEvolution/min-max-exprs.ll =================================================================== --- test/Analysis/ScalarEvolution/min-max-exprs.ll +++ test/Analysis/ScalarEvolution/min-max-exprs.ll @@ -33,7 +33,7 @@ %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}<%bb1> to i64))) smax (-1 + (-1 * (sext i32 %N to i64)))))) +; CHECK-NEXT: --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<%bb1> to i64))) smax (-1 + (-1 * (sext i32 %N to i64)))))) %tmp11 = getelementptr inbounds i32, i32* %A, i64 %tmp9 %tmp12 = load i32, i32* %tmp11, align 4 %tmp13 = shl nsw i32 %tmp12, 1 Index: test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll @@ -0,0 +1,44 @@ +; RUN: opt -S -analyze -scalar-evolution < %s | FileCheck %s + +!0 = !{i8 0, i8 127} + +define void @f0(i8* %len_addr) { +; CHECK-LABEL: Classifying expressions for: @f0 + entry: + %len = load i8, i8* %len_addr, !range !0 + %len_norange = load i8, i8* %len_addr +; CHECK: %len = load i8, i8* %len_addr, !range !0 +; CHECK-NEXT: --> %len U: [0,127) S: [0,127) +; CHECK: %len_norange = load i8, i8* %len_addr +; CHECK-NEXT: --> %len_norange U: full-set S: full-set + + %t0 = add i8 %len, 1 + %t1 = add i8 %len, 2 +; CHECK: %t0 = add i8 %len, 1 +; CHECK-NEXT: --> (1 + %len) U: [1,-128) S: [1,-128) +; CHECK: %t1 = add i8 %len, 2 +; CHECK-NEXT: --> (2 + %len) U: [2,-127) S: [2,-127) + + %t2 = sub i8 %len, 1 + %t3 = sub i8 %len, 2 +; CHECK: %t2 = sub i8 %len, 1 +; CHECK-NEXT: --> (-1 + %len) U: [-1,126) S: [-1,126) +; CHECK: %t3 = sub i8 %len, 2 +; CHECK-NEXT: --> (-2 + %len) U: [-2,125) S: [-2,125) + + %q0 = add i8 %len_norange, 1 + %q1 = add i8 %len_norange, 2 +; CHECK: %q0 = add i8 %len_norange, 1 +; CHECK-NEXT: --> (1 + %len_norange) U: full-set S: full-set +; CHECK: %q1 = add i8 %len_norange, 2 +; CHECK-NEXT: --> (2 + %len_norange) U: full-set S: full-set + + %q2 = sub i8 %len_norange, 1 + %q3 = sub i8 %len_norange, 2 +; CHECK: %q2 = sub i8 %len_norange, 1 +; CHECK-NEXT: --> (-1 + %len_norange) U: full-set S: full-set +; CHECK: %q3 = sub i8 %len_norange, 2 +; CHECK-NEXT: --> (-2 + %len_norange) U: full-set S: full-set + + ret void +} Index: test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll =================================================================== --- test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll +++ test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll @@ -28,7 +28,7 @@ ; 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)),+,33554432}<%test2.loop> in %f = ashr i32 %sext.us, 24 define i32 @test2() { entry: br label %test2.loop