Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -13171,7 +13171,7 @@
if (canIVOverflowOnGT(RHS, Stride, IsSigned))
return getCouldNotCompute();
- const SCEV *Start = IV->getStart();
+ const SCEV *Start = applyLoopGuards(IV->getStart(), L);
const SCEV *End = RHS;
if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS)) {
// If we know that Start >= RHS in the context of loop, then we know that
Index: llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
+++ llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll
@@ -9,24 +9,24 @@
; CHECK-LABEL: 'f'
; CHECK-NEXT: Classifying expressions for: @f
; CHECK-NEXT: %indvar = phi i32 [ 0, %bb.nph ], [ %indvar.next, %bb1 ]
-; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%bb> U: [0,1431655765) S: [0,1431655765) Exits: ((-5 + %x) /u 3) LoopDispositions: { %bb: Computable }
+; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%bb> U: [0,1431655764) S: [0,1431655764) Exits: ((-5 + (5 umax %x)) /u 3) LoopDispositions: { %bb: Computable }
; CHECK-NEXT: %tmp = mul i32 %indvar, -3
-; CHECK-NEXT: --> {0,+,-3}<%bb> U: [4,1) S: [4,1) Exits: (-3 * ((-5 + %x) /u 3)) LoopDispositions: { %bb: Computable }
+; CHECK-NEXT: --> {0,+,-3}<%bb> U: [7,1) S: [7,1) Exits: (-3 * ((-5 + (5 umax %x)) /u 3)) LoopDispositions: { %bb: Computable }
; CHECK-NEXT: %x_addr.04 = add i32 %tmp, %x
-; CHECK-NEXT: --> {%x,+,-3}<%bb> U: full-set S: full-set Exits: ((-3 * ((-5 + %x) /u 3)) + %x) LoopDispositions: { %bb: Computable }
+; CHECK-NEXT: --> {%x,+,-3}<%bb> U: full-set S: full-set Exits: ((-3 * ((-5 + (5 umax %x)) /u 3)) + %x) LoopDispositions: { %bb: Computable }
; CHECK-NEXT: %1 = add i32 %x_addr.04, -3
-; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set Exits: (-3 + (-3 * ((-5 + %x) /u 3)) + %x) LoopDispositions: { %bb: Computable }
+; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set Exits: (-3 + (-3 * ((-5 + (5 umax %x)) /u 3)) + %x) LoopDispositions: { %bb: Computable }
; CHECK-NEXT: %indvar.next = add i32 %indvar, 1
-; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%bb> U: [1,1431655766) S: [1,1431655766) Exits: (1 + ((-5 + %x) /u 3))<nuw><nsw> LoopDispositions: { %bb: Computable }
+; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%bb> U: [1,1431655765) S: [1,1431655765) Exits: (1 + ((-5 + (5 umax %x)) /u 3))<nuw><nsw> LoopDispositions: { %bb: Computable }
; CHECK-NEXT: %lcssa = phi i32 [ %1, %bb1 ]
-; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set --> (-3 + (-3 * ((-5 + %x) /u 3)) + %x) U: full-set S: full-set
+; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set --> (-3 + (-3 * ((-5 + (5 umax %x)) /u 3)) + %x) U: full-set S: full-set
; CHECK-NEXT: %x_addr.0.lcssa = phi i32 [ %lcssa, %bb1.bb2_crit_edge ], [ %x, %entry ]
; CHECK-NEXT: --> %x_addr.0.lcssa U: full-set S: full-set
; CHECK-NEXT: Determining loop execution counts for: @f
-; CHECK-NEXT: Loop %bb: backedge-taken count is ((-5 + %x) /u 3)
-; CHECK-NEXT: Loop %bb: constant max backedge-taken count is 1431655764
-; CHECK-NEXT: Loop %bb: symbolic max backedge-taken count is ((-5 + %x) /u 3)
-; CHECK-NEXT: Loop %bb: Predicated backedge-taken count is ((-5 + %x) /u 3)
+; CHECK-NEXT: Loop %bb: backedge-taken count is ((-5 + (5 umax %x)) /u 3)
+; CHECK-NEXT: Loop %bb: constant max backedge-taken count is 1431655763
+; CHECK-NEXT: Loop %bb: symbolic max backedge-taken count is ((-5 + (5 umax %x)) /u 3)
+; CHECK-NEXT: Loop %bb: Predicated backedge-taken count is ((-5 + (5 umax %x)) /u 3)
; CHECK-NEXT: Predicates:
; CHECK: Loop %bb: Trip multiple is 1
;
Index: llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll
+++ llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll
@@ -7,18 +7,18 @@
; CHECK-NEXT: %k.018 = add i32 %c.idx.val, -1
; CHECK-NEXT: --> (-1 + %c.idx.val) U: full-set S: full-set
; CHECK-NEXT: %k.019 = phi i32 [ %k.0, %bb18 ], [ %k.018, %bb2 ]
-; CHECK-NEXT: --> {(-1 + %c.idx.val),+,-1}<%bb16.preheader> U: full-set S: full-set Exits: 0 LoopDispositions: { %bb16.preheader: Computable }
+; CHECK-NEXT: --> {(-1 + %c.idx.val),+,-1}<nw><%bb16.preheader> U: full-set S: full-set Exits: ((-1 * (1 umax (-2147483648 umin %c.idx.val))) + %c.idx.val) LoopDispositions: { %bb16.preheader: Computable }
; CHECK-NEXT: %x = phi i32 [ 0, %bb2 ], [ %x.1, %bb18 ]
-; CHECK-NEXT: --> {0,+,1}<nuw><%bb16.preheader> U: [0,-2147483647) S: [0,-2147483647) Exits: (-1 + %c.idx.val) LoopDispositions: { %bb16.preheader: Computable }
+; CHECK-NEXT: --> {0,+,1}<nuw><%bb16.preheader> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + (1 umax (-2147483648 umin %c.idx.val))) LoopDispositions: { %bb16.preheader: Computable }
; CHECK-NEXT: %x.1 = add i32 %x, 1
-; CHECK-NEXT: --> {1,+,1}<nuw><%bb16.preheader> U: [1,-2147483646) S: [1,-2147483646) Exits: %c.idx.val LoopDispositions: { %bb16.preheader: Computable }
+; CHECK-NEXT: --> {1,+,1}<nuw><%bb16.preheader> U: [1,-2147483647) S: [1,-2147483647) Exits: (1 umax (-2147483648 umin %c.idx.val)) LoopDispositions: { %bb16.preheader: Computable }
; CHECK-NEXT: %k.0 = add i32 %k.019, -1
-; CHECK-NEXT: --> {(-2 + %c.idx.val),+,-1}<%bb16.preheader> U: full-set S: full-set Exits: -1 LoopDispositions: { %bb16.preheader: Computable }
+; CHECK-NEXT: --> {(-2 + %c.idx.val),+,-1}<nw><%bb16.preheader> U: full-set S: full-set Exits: (-1 + (-1 * (1 umax (-2147483648 umin %c.idx.val))) + %c.idx.val) LoopDispositions: { %bb16.preheader: Computable }
; CHECK-NEXT: Determining loop execution counts for: @f
-; CHECK-NEXT: Loop %bb16.preheader: backedge-taken count is (-1 + %c.idx.val)
-; CHECK-NEXT: Loop %bb16.preheader: constant max backedge-taken count is -2147483648
-; CHECK-NEXT: Loop %bb16.preheader: symbolic max backedge-taken count is (-1 + %c.idx.val)
-; CHECK-NEXT: Loop %bb16.preheader: Predicated backedge-taken count is (-1 + %c.idx.val)
+; CHECK-NEXT: Loop %bb16.preheader: backedge-taken count is (-1 + (1 umax (-2147483648 umin %c.idx.val)))
+; CHECK-NEXT: Loop %bb16.preheader: constant max backedge-taken count is 2147483647
+; CHECK-NEXT: Loop %bb16.preheader: symbolic max backedge-taken count is (-1 + (1 umax (-2147483648 umin %c.idx.val)))
+; CHECK-NEXT: Loop %bb16.preheader: Predicated backedge-taken count is (-1 + (1 umax (-2147483648 umin %c.idx.val)))
; CHECK-NEXT: Predicates:
; CHECK: Loop %bb16.preheader: Trip multiple is 1
;
Index: llvm/test/Analysis/ScalarEvolution/smin-smax-folds.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/smin-smax-folds.ll
+++ llvm/test/Analysis/ScalarEvolution/smin-smax-folds.ll
@@ -29,14 +29,14 @@
; CHECK-LABEL: 'smin_simplify_with_guard'
; CHECK-NEXT: Classifying expressions for: @smin_simplify_with_guard
; CHECK-NEXT: %i.011 = phi i32 [ %n, %for.body.lr.ph ], [ %dec, %for.body ]
-; CHECK-NEXT: --> {%n,+,-1}<nsw><%for.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {%n,+,-1}<nsw><%for.body> U: full-set S: full-set Exits: ((-1 * (0 smax %n))<nsw> + %n) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: %dec = add nsw i32 %i.011, -1
-; CHECK-NEXT: --> {(-1 + %n),+,-1}<nw><%for.body> U: full-set S: full-set Exits: -1 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {(-1 + %n),+,-1}<nw><%for.body> U: full-set S: full-set Exits: (-1 + (-1 * (0 smax %n))<nsw> + %n) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: Determining loop execution counts for: @smin_simplify_with_guard
-; CHECK-NEXT: Loop %for.body: backedge-taken count is %n
+; CHECK-NEXT: Loop %for.body: backedge-taken count is (0 smax %n)
; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 2147483647
-; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is %n
-; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is %n
+; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (0 smax %n)
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (0 smax %n)
; CHECK-NEXT: Predicates:
; CHECK: Loop %for.body: Trip multiple is 1
;
Index: llvm/test/Analysis/ScalarEvolution/trip-count-from-loop-guard.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/trip-count-from-loop-guard.ll
+++ llvm/test/Analysis/ScalarEvolution/trip-count-from-loop-guard.ll
@@ -4,21 +4,21 @@
; if (const > 0)
; for (i8 i = 126; const - i > 0; i++) {}
;
-; TODO: Use loop guard's info 'const > 0' to figure out that max backedge-taken count is 1
+; Use loop guard's info 'const > 0' to figure out that max backedge-taken count is 1
define i32 @range_from_loop_guard(i8 %const) {
; CHECK-LABEL: 'range_from_loop_guard'
; CHECK-NEXT: Classifying expressions for: @range_from_loop_guard
; CHECK-NEXT: %iv = phi i8 [ %iv.next, %loop ], [ 126, %entry ]
-; CHECK-NEXT: --> {126,+,1}<nuw><%loop> U: [126,-2) S: [126,-2) Exits: ((-1 * (0 smin (-126 + %const))) + %const) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT: --> {126,+,1}<nuw><%loop> U: [126,-128) S: [126,-128) Exits: ((-1 * (0 smin (-126 + (1 smax %const))<nsw>))<nsw> + (1 smax %const)) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %iv.next = add nuw i8 %iv, 1
-; CHECK-NEXT: --> {127,+,1}<nuw><%loop> U: [127,-1) S: [127,-1) Exits: (1 + (-1 * (0 smin (-126 + %const))) + %const) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT: --> {127,+,1}<nuw><%loop> U: [127,-127) S: [127,-127) Exits: (1 + (-1 * (0 smin (-126 + (1 smax %const))<nsw>))<nsw> + (1 smax %const)) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %sub = sub i8 %const, %iv
-; CHECK-NEXT: --> {(-126 + %const),+,-1}<nw><%loop> U: full-set S: full-set Exits: (0 smin (-126 + %const)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT: --> {(-126 + %const),+,-1}<nw><%loop> U: full-set S: full-set Exits: ((-1 * (1 smax %const))<nsw> + (0 smin (-126 + (1 smax %const))<nsw>) + %const) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: Determining loop execution counts for: @range_from_loop_guard
-; CHECK-NEXT: Loop %loop: backedge-taken count is (-126 + (-1 * (0 smin (-126 + %const))) + %const)
-; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 127
-; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-126 + (-1 * (0 smin (-126 + %const))) + %const)
-; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-126 + (-1 * (0 smin (-126 + %const))) + %const)
+; CHECK-NEXT: Loop %loop: backedge-taken count is (-126 + (-1 * (0 smin (-126 + (1 smax %const))<nsw>))<nsw> + (1 smax %const))
+; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 1
+; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-126 + (-1 * (0 smin (-126 + (1 smax %const))<nsw>))<nsw> + (1 smax %const))
+; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-126 + (-1 * (0 smin (-126 + (1 smax %const))<nsw>))<nsw> + (1 smax %const))
; CHECK-NEXT: Predicates:
; CHECK: Loop %loop: Trip multiple is 1
;
Index: llvm/test/Analysis/ScalarEvolution/trip-count12.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/trip-count12.ll
+++ llvm/test/Analysis/ScalarEvolution/trip-count12.ll
@@ -5,13 +5,13 @@
; CHECK-LABEL: 'test'
; CHECK-NEXT: Classifying expressions for: @test
; CHECK-NEXT: %p.addr.05 = phi ptr [ %incdec.ptr, %for.body ], [ %p, %for.body.preheader ]
-; CHECK-NEXT: --> {%p,+,2}<nuw><%for.body> U: full-set S: full-set Exits: ((2 * ((zext i32 (-2 + %len) to i64) /u 2))<nuw><nsw> + %p) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {%p,+,2}<nuw><%for.body> U: full-set S: full-set Exits: ((2 * ((zext i32 (-2 + (2 smax %len))<nsw> to i64) /u 2))<nuw><nsw> + %p) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: %len.addr.04 = phi i32 [ %sub, %for.body ], [ %len, %for.body.preheader ]
-; CHECK-NEXT: --> {%len,+,-2}<nsw><%for.body> U: full-set S: full-set Exits: ((-2 * ((-2 + %len) /u 2)) + %len) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {%len,+,-2}<nsw><%for.body> U: full-set S: full-set Exits: ((-2 * ((-2 + (2 smax %len))<nsw> /u 2))<nsw> + %len) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: %res.03 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
; CHECK-NEXT: --> %res.03 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
; CHECK-NEXT: %incdec.ptr = getelementptr inbounds i16, ptr %p.addr.05, i32 1
-; CHECK-NEXT: --> {(2 + %p),+,2}<nw><%for.body> U: full-set S: full-set Exits: (2 + (2 * ((zext i32 (-2 + %len) to i64) /u 2))<nuw><nsw> + %p) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {(2 + %p),+,2}<nw><%for.body> U: full-set S: full-set Exits: (2 + (2 * ((zext i32 (-2 + (2 smax %len))<nsw> to i64) /u 2))<nuw><nsw> + %p) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: %0 = load i16, ptr %p.addr.05, align 2
; CHECK-NEXT: --> %0 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
; CHECK-NEXT: %conv = zext i16 %0 to i32
@@ -19,16 +19,16 @@
; CHECK-NEXT: %add = add i32 %conv, %res.03
; CHECK-NEXT: --> ((zext i16 %0 to i32) + %res.03) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
; CHECK-NEXT: %sub = add nsw i32 %len.addr.04, -2
-; CHECK-NEXT: --> {(-2 + %len),+,-2}<nsw><%for.body> U: full-set S: full-set Exits: (-2 + (-2 * ((-2 + %len) /u 2)) + %len) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT: --> {(-2 + %len),+,-2}<nsw><%for.body> U: full-set S: full-set Exits: (-2 + (-2 * ((-2 + (2 smax %len))<nsw> /u 2))<nsw> + %len) LoopDispositions: { %for.body: Computable }
; CHECK-NEXT: %extract.t = trunc i32 %add to i16
; CHECK-NEXT: --> ((trunc i32 %res.03 to i16) + %0) U: full-set S: full-set
; CHECK-NEXT: %res.0.lcssa.off0 = phi i16 [ %extract.t, %for.cond.for.end_crit_edge ], [ 0, %entry ]
; CHECK-NEXT: --> %res.0.lcssa.off0 U: full-set S: full-set
; CHECK-NEXT: Determining loop execution counts for: @test
-; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-2 + %len) /u 2)
-; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 1073741823
-; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-2 + %len) /u 2)
-; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + %len) /u 2)
+; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-2 + (2 smax %len))<nsw> /u 2)
+; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 1073741822
+; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-2 + (2 smax %len))<nsw> /u 2)
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + (2 smax %len))<nsw> /u 2)
; CHECK-NEXT: Predicates:
; CHECK: Loop %for.body: Trip multiple is 1
;