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}<%bb> U: [0,1431655765) S: [0,1431655765) Exits: ((-5 + %x) /u 3) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: --> {0,+,1}<%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}<%bb> U: [1,1431655766) S: [1,1431655766) Exits: (1 + ((-5 + %x) /u 3)) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: --> {1,+,1}<%bb> U: [1,1431655765) S: [1,1431655765) Exits: (1 + ((-5 + (5 umax %x)) /u 3)) 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}<%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}<%bb16.preheader> U: [0,-2147483647) S: [0,-2147483647) Exits: (-1 + %c.idx.val) LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: --> {0,+,1}<%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}<%bb16.preheader> U: [1,-2147483646) S: [1,-2147483646) Exits: %c.idx.val LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: --> {1,+,1}<%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}<%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}<%for.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {%n,+,-1}<%for.body> U: full-set S: full-set Exits: ((-1 * (0 smax %n)) + %n) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %dec = add nsw i32 %i.011, -1 -; CHECK-NEXT: --> {(-1 + %n),+,-1}<%for.body> U: full-set S: full-set Exits: -1 LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {(-1 + %n),+,-1}<%for.body> U: full-set S: full-set Exits: (-1 + (-1 * (0 smax %n)) + %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}<%loop> U: [126,-2) S: [126,-2) Exits: ((-1 * (0 smin (-126 + %const))) + %const) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {126,+,1}<%loop> U: [126,-128) S: [126,-128) Exits: ((-1 * (0 smin (-126 + (1 smax %const)))) + (1 smax %const)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw i8 %iv, 1 -; CHECK-NEXT: --> {127,+,1}<%loop> U: [127,-1) S: [127,-1) Exits: (1 + (-1 * (0 smin (-126 + %const))) + %const) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {127,+,1}<%loop> U: [127,-127) S: [127,-127) Exits: (1 + (-1 * (0 smin (-126 + (1 smax %const)))) + (1 smax %const)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %sub = sub i8 %const, %iv -; CHECK-NEXT: --> {(-126 + %const),+,-1}<%loop> U: full-set S: full-set Exits: (0 smin (-126 + %const)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(-126 + %const),+,-1}<%loop> U: full-set S: full-set Exits: ((-1 * (1 smax %const)) + (0 smin (-126 + (1 smax %const))) + %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)))) + (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)))) + (1 smax %const)) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-126 + (-1 * (0 smin (-126 + (1 smax %const)))) + (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}<%for.body> U: full-set S: full-set Exits: ((2 * ((zext i32 (-2 + %len) to i64) /u 2)) + %p) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {%p,+,2}<%for.body> U: full-set S: full-set Exits: ((2 * ((zext i32 (-2 + (2 smax %len)) to i64) /u 2)) + %p) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %len.addr.04 = phi i32 [ %sub, %for.body ], [ %len, %for.body.preheader ] -; CHECK-NEXT: --> {%len,+,-2}<%for.body> U: full-set S: full-set Exits: ((-2 * ((-2 + %len) /u 2)) + %len) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {%len,+,-2}<%for.body> U: full-set S: full-set Exits: ((-2 * ((-2 + (2 smax %len)) /u 2)) + %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: <> LoopDispositions: { %for.body: Variant } ; CHECK-NEXT: %incdec.ptr = getelementptr inbounds i16, ptr %p.addr.05, i32 1 -; CHECK-NEXT: --> {(2 + %p),+,2}<%for.body> U: full-set S: full-set Exits: (2 + (2 * ((zext i32 (-2 + %len) to i64) /u 2)) + %p) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {(2 + %p),+,2}<%for.body> U: full-set S: full-set Exits: (2 + (2 * ((zext i32 (-2 + (2 smax %len)) to i64) /u 2)) + %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: <> 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: <> LoopDispositions: { %for.body: Variant } ; CHECK-NEXT: %sub = add nsw i32 %len.addr.04, -2 -; CHECK-NEXT: --> {(-2 + %len),+,-2}<%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}<%for.body> U: full-set S: full-set Exits: (-2 + (-2 * ((-2 + (2 smax %len)) /u 2)) + %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)) /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)) /u 2) +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + (2 smax %len)) /u 2) ; CHECK-NEXT: Predicates: ; CHECK: Loop %for.body: Trip multiple is 1 ;