Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -6723,6 +6723,18 @@ BitWidth); ConservativeResult = ConservativeResult.intersectWith(RangeFromFactoring, RangeType); + + // Try to compute range starting from exit-value with negative step + const Loop *L = AddRec->getLoop(); + const SCEV *ExitValue = getSCEVAtScope(S, L->getParentLoop()); + if (isLoopInvariant(ExitValue, L)) { + const SCEV *NegStep = + getNegativeSCEV(AddRec->getStepRecurrence(*this)); + RangeFromAffine = + getRangeForAffineAR(ExitValue, NegStep, MaxBECount, BitWidth); + ConservativeResult = + ConservativeResult.intersectWith(RangeFromAffine, RangeType); + } } // Now try symbolic BE count and more powerful methods. Index: llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll +++ llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll @@ -33,17 +33,17 @@ ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] ; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ] -; CHECK-NEXT: --> {(-1 + %n),+,-1}<%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(-1 + %n),+,-1}<%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %a = sub i32 %n, %i -; CHECK-NEXT: --> {%n,+,-1}<%loop> U: full-set S: full-set Exits: 1 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%n,+,-1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: 1 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %b = sub i32 %n.minus.1, %i -; CHECK-NEXT: --> {(-1 + %n),+,-1}<%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(-1 + %n),+,-1}<%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %c = sub i32 2147483647, %i ; CHECK-NEXT: --> {2147483647,+,-1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add nuw nsw i32 %i, 1 ; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %j.next = add nsw i32 %j, -1 -; CHECK-NEXT: --> {(-2 + %n),+,-1}<%loop> U: full-set S: full-set Exits: -1 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(-2 + %n),+,-1}<%loop> U: [-1,2147483646) S: [-1,2147483646) Exits: -1 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_step_1_flags ; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %n) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 2147483646 Index: llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll +++ llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll @@ -7,11 +7,11 @@ ; CHECK-LABEL: 'test_guard_less_than_16' ; CHECK-NEXT: Classifying expressions for: @test_guard_less_than_16 ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ] -; CHECK-NEXT: --> {%i,+,1}<%loop> U: full-set S: full-set Exits: 15 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%i,+,1}<%loop> U: [0,16) S: [0,16) Exits: 15 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, ptr %a, i64 %iv -; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 16 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: [1,17) S: [1,17) Exits: 16 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_less_than_16 ; CHECK-NEXT: Loop %loop: backedge-taken count is (15 + (-1 * %i)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 15 @@ -40,11 +40,11 @@ ; CHECK-LABEL: 'test_guard_less_than_16_operands_swapped' ; CHECK-NEXT: Classifying expressions for: @test_guard_less_than_16_operands_swapped ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ] -; CHECK-NEXT: --> {%i,+,1}<%loop> U: full-set S: full-set Exits: 15 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%i,+,1}<%loop> U: [0,16) S: [0,16) Exits: 15 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, ptr %a, i64 %iv -; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 16 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: [1,17) S: [1,17) Exits: 16 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_less_than_16_operands_swapped ; CHECK-NEXT: Loop %loop: backedge-taken count is (15 + (-1 * %i)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 15 @@ -106,11 +106,11 @@ ; CHECK-LABEL: 'test_guard_uge_16_branches_flipped' ; CHECK-NEXT: Classifying expressions for: @test_guard_uge_16_branches_flipped ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ] -; CHECK-NEXT: --> {%i,+,1}<%loop> U: full-set S: full-set Exits: 15 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%i,+,1}<%loop> U: [0,16) S: [0,16) Exits: 15 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, ptr %a, i64 %iv -; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (60 + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 16 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: [1,17) S: [1,17) Exits: 16 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_uge_16_branches_flipped ; CHECK-NEXT: Loop %loop: backedge-taken count is (15 + (-1 * %i)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 15 @@ -887,9 +887,9 @@ ; CHECK-NEXT: %init = phi i32 [ 2, %entry ], [ 3, %bb1 ] ; CHECK-NEXT: --> %init U: [2,4) S: [2,4) ; CHECK-NEXT: %iv = phi i32 [ %iv.next, %loop ], [ %init, %loop.ph ] -; CHECK-NEXT: --> {%init,+,1}<%loop> U: [2,11) S: [2,11) Exits: 9 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%init,+,1}<%loop> U: [2,10) S: [2,10) Exits: 9 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add i32 %iv, 1 -; CHECK-NEXT: --> {(1 + %init),+,1}<%loop> U: [3,12) S: [3,12) Exits: 10 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %init),+,1}<%loop> U: [3,11) S: [3,11) Exits: 10 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @guard_pessimizes_analysis_step1 ; CHECK-NEXT: Loop %loop: backedge-taken count is (9 + (-1 * %init)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 7 @@ -1024,9 +1024,9 @@ ; CHECK-NEXT: %shr = lshr i32 %blockSize, 2 ; CHECK-NEXT: --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824) ; CHECK-NEXT: %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ] -; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [-1073741822,1073741824) S: [-1073741822,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [1,1073741824) S: [1,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: %dec = add i32 %iv, -1 -; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [-1073741823,1073741823) S: [-1073741823,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [0,1073741823) S: [0,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_uge ; CHECK-NEXT: Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4)) ; CHECK-NEXT: Loop %while.body: constant max backedge-taken count is 1073741822 @@ -1061,9 +1061,9 @@ ; CHECK-NEXT: %shr = lshr i32 %blockSize, 2 ; CHECK-NEXT: --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824) ; CHECK-NEXT: %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ] -; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [-1073741822,1073741824) S: [-1073741822,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [1,1073741824) S: [1,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: %dec = add i32 %iv, -1 -; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [-1073741823,1073741823) S: [-1073741823,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [0,1073741823) S: [0,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_ugt ; CHECK-NEXT: Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4)) ; CHECK-NEXT: Loop %while.body: constant max backedge-taken count is 1073741822 @@ -1098,9 +1098,9 @@ ; CHECK-NEXT: %shr = lshr i32 %blockSize, 2 ; CHECK-NEXT: --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824) ; CHECK-NEXT: %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ] -; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [-255,1073741824) S: [-255,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: %dec = add i32 %iv, -1 -; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [-256,1073741823) S: [-256,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [0,256) S: [0,256) Exits: 0 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_uge_and_ule ; CHECK-NEXT: Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4)) ; CHECK-NEXT: Loop %while.body: constant max backedge-taken count is 255 @@ -1139,9 +1139,9 @@ ; CHECK-NEXT: %shr = lshr i32 %blockSize, 2 ; CHECK-NEXT: --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824) ; CHECK-NEXT: %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ] -; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [-255,1073741824) S: [-255,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(%blockSize /u 4),+,-1}<%while.body> U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: %dec = add i32 %iv, -1 -; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [-256,1073741823) S: [-256,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable } +; CHECK-NEXT: --> {(-1 + (%blockSize /u 4)),+,-1}<%while.body> U: [0,256) S: [0,256) Exits: 0 LoopDispositions: { %while.body: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_ugt_and_ult ; CHECK-NEXT: Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4)) ; CHECK-NEXT: Loop %while.body: constant max backedge-taken count is 255 @@ -1217,11 +1217,11 @@ ; CHECK-NEXT: %and = and i1 %c.0, %c.1 ; CHECK-NEXT: --> (%c.0 umin %c.1) U: full-set S: full-set ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ] -; CHECK-NEXT: --> {%i,+,1}<%loop> U: full-set S: full-set Exits: 17 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%i,+,1}<%loop> U: [5,18) S: [5,18) Exits: 17 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, ptr %a, i64 %iv -; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: [6,19) S: [6,19) Exits: 18 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_slt_sgt_2 ; CHECK-NEXT: Loop %loop: backedge-taken count is (17 + (-1 * %i)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 12 @@ -1291,11 +1291,11 @@ ; CHECK-NEXT: %and = and i1 %c.0, %c.1 ; CHECK-NEXT: --> (%c.0 umin %c.1) U: full-set S: full-set ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ] -; CHECK-NEXT: --> {%i,+,1}<%loop> U: full-set S: full-set Exits: 17 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%i,+,1}<%loop> U: [4,18) S: [4,18) Exits: 17 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, ptr %a, i64 %iv -; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * %i) + %a),+,4}<%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: [5,19) S: [5,19) Exits: 18 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_sle_sge_2 ; CHECK-NEXT: Loop %loop: backedge-taken count is (17 + (-1 * %i)) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 13 Index: llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll +++ llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll @@ -69,9 +69,9 @@ ; CHECK-NEXT: %shl = shl i64 %zext, 31 ; CHECK-NEXT: --> (2147483648 * (zext i32 %start to i64)) U: [0,9223372034707292161) S: [0,9223372034707292161) ; CHECK-NEXT: %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ %shl, %entry ] -; CHECK-NEXT: --> {(2147483648 * (zext i32 %start to i64)),+,-1}<%loop> U: [-9223372036854775808,9223372034707292161) S: [-9223372036854775808,9223372034707292161) Exits: -9223372036854775806 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(2147483648 * (zext i32 %start to i64)),+,-1}<%loop> U: [-9223372036854775806,9223372034707292161) S: [-9223372036854775806,9223372034707292161) Exits: -9223372036854775806 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %indvars.iv.next = add nsw i64 %indvars.iv, -1 -; CHECK-NEXT: --> {(-1 + (2147483648 * (zext i32 %start to i64))),+,-1}<%loop> U: full-set S: full-set Exits: -9223372036854775807 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(-1 + (2147483648 * (zext i32 %start to i64))),+,-1}<%loop> U: [-9223372036854775807,9223372034707292160) S: [-9223372036854775807,9223372034707292160) Exits: -9223372036854775807 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_02 ; CHECK-NEXT: Loop %loop: backedge-taken count is (9223372036854775806 + (2147483648 * (zext i32 %start to i64))) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is -2147483650 Index: llvm/test/Analysis/ScalarEvolution/nsw.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/nsw.ll +++ llvm/test/Analysis/ScalarEvolution/nsw.ll @@ -278,9 +278,9 @@ ; CHECK-NEXT: %array = alloca [10 x i32], align 4 ; CHECK-NEXT: --> %array U: [0,-3) S: [-9223372036854775808,9223372036854775805) ; CHECK-NEXT: %index = phi i32 [ %inc5, %for.body ], [ %arg, %entry ] -; CHECK-NEXT: --> {%arg,+,1}<%for.body> U: full-set S: full-set Exits: (-1 + (10 smax (1 + %arg))) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {%arg,+,1}<%for.body> U: [-2147483648,2147483647) S: [-2147483648,2147483647) Exits: (-1 + (10 smax (1 + %arg))) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %sub = add nsw i32 %index, -2 -; CHECK-NEXT: --> {(-2 + %arg),+,1}<%for.body> U: full-set S: full-set Exits: (-3 + (10 smax (1 + %arg))) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {(-2 + %arg),+,1}<%for.body> U: [2147483646,2147483645) S: [2147483646,2147483645) Exits: (-3 + (10 smax (1 + %arg))) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %idxprom = sext i32 %sub to i64 ; CHECK-NEXT: --> {(-2 + (sext i32 %arg to i64)),+,1}<%for.body> U: [-2147483650,4294967303) S: [-2147483650,4294967303) Exits: (-2 + (zext i32 (-1 + (-1 * %arg) + (10 smax (1 + %arg))) to i64) + (sext i32 %arg to i64)) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %arrayidx = getelementptr inbounds [10 x i32], ptr %array, i64 0, i64 %idxprom 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,9 +29,9 @@ ; 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: [0,-2147483648) S: [0,-2147483648) Exits: 0 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: [-1,2147483647) S: [-1,2147483647) Exits: -1 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: constant max backedge-taken count is 2147483647 Index: llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll +++ llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll @@ -71,10 +71,7 @@ ; CHECK: outer: ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i32 [ [[SUB1]], [[OUTER_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[OUTER_INC:%.*]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_INC:%.*]], [[OUTER_INC]] ], [ 0, [[OUTER_PREHEADER]] ] -; CHECK-NEXT: [[SUB2:%.*]] = sub nsw i32 [[ARG]], [[I]] -; CHECK-NEXT: [[SUB3:%.*]] = sub nsw i32 [[SUB2]], 1 -; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 0, [[SUB3]] -; CHECK-NEXT: br i1 [[CMP2]], label [[INNER_PH:%.*]], label [[OUTER_INC]] +; CHECK-NEXT: br i1 true, label [[INNER_PH:%.*]], label [[OUTER_INC]] ; CHECK: inner.ph: ; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK: inner: Index: llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll +++ llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll @@ -12,7 +12,7 @@ define void @test_predicated_simple_unsigned(ptr %p, ptr %arr) { ; CHECK-LABEL: @test_predicated_simple_unsigned( ; CHECK-NEXT: preheader: -; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0:!range !.*]] +; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0:![0-9]+]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -61,7 +61,7 @@ define void @test_predicated_simple_signed(ptr %p, ptr %arr) { ; CHECK-LABEL: @test_predicated_simple_signed( ; CHECK-NEXT: preheader: -; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0]] +; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -118,9 +118,9 @@ ; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK: outer: ; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_INC:%.*]], [[OUTER_INC:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] -; CHECK-NEXT: [[SUB2:%.*]] = sub nsw i32 [[ARG]], [[I]] +; CHECK-NEXT: [[SUB2:%.*]] = sub nuw nsw i32 [[ARG]], [[I]] ; CHECK-NEXT: [[SUB3:%.*]] = sub nsw i32 [[SUB2]], 1 -; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 0, [[SUB3]] +; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i32 0, [[SUB3]] ; CHECK-NEXT: br i1 [[CMP2]], label [[INNER_PH:%.*]], label [[OUTER_INC]] ; CHECK: inner.ph: ; CHECK-NEXT: br label [[INNER:%.*]] @@ -176,11 +176,7 @@ ; CHECK: outer.preheader: ; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK: outer: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_INC:%.*]], [[OUTER_INC:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] -; CHECK-NEXT: [[SUB2:%.*]] = sub nsw i32 [[ARG]], [[I]] -; CHECK-NEXT: [[SUB3:%.*]] = sub nsw i32 [[SUB2]], 1 -; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 0, [[SUB3]] -; CHECK-NEXT: br i1 [[CMP2]], label [[INNER_PH:%.*]], label [[OUTER_INC]] +; CHECK-NEXT: br i1 true, label [[INNER_PH:%.*]], label [[OUTER_INC:%.*]] ; CHECK: inner.ph: ; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK: inner: @@ -188,7 +184,6 @@ ; CHECK: outer.inc.loopexit: ; CHECK-NEXT: br label [[OUTER_INC]] ; CHECK: outer.inc: -; CHECK-NEXT: [[I_INC]] = add nuw nsw i32 [[I]], 1 ; CHECK-NEXT: br i1 false, label [[OUTER]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: exit.loopexit: ; CHECK-NEXT: br label [[EXIT]] @@ -235,7 +230,7 @@ ; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK: outer: ; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_INC:%.*]], [[OUTER_INC:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] -; CHECK-NEXT: [[SUB2:%.*]] = sub nsw i32 [[ARG]], [[I]] +; CHECK-NEXT: [[SUB2:%.*]] = sub nuw nsw i32 [[ARG]], [[I]] ; CHECK-NEXT: [[SUB3:%.*]] = sub nsw i32 [[SUB2]], 1 ; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i32 0, [[SUB3]] ; CHECK-NEXT: br i1 [[CMP2]], label [[INNER_PH:%.*]], label [[OUTER_INC]] @@ -470,7 +465,7 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -478,7 +473,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 @@ -521,7 +516,7 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -529,7 +524,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[FAIL:%.*]], label [[BACKEDGE]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 @@ -624,7 +619,7 @@ ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[START:%.*]] = zext i32 [[LEN]] to i64 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -632,7 +627,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub nsw i64 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 @@ -678,7 +673,7 @@ ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[START:%.*]] = zext i32 [[LEN]] to i64 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -686,7 +681,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub nsw i64 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[FAIL:%.*]], label [[BACKEDGE]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 @@ -835,7 +830,7 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -843,7 +838,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 @@ -886,7 +881,7 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 -; CHECK-NEXT: [[RANGE_CHECK1:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] @@ -894,7 +889,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 -; CHECK-NEXT: br i1 [[RANGE_CHECK1]], label [[FAIL:%.*]], label [[BACKEDGE]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 Index: llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll +++ llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll @@ -196,7 +196,7 @@ ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP0]], [[PREHEADER]] ] ; CHECK-NEXT: [[EL:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[INDVARS_IV]] ; CHECK-NEXT: store atomic i32 0, ptr [[EL]] unordered, align 4 -; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 ; CHECK-NEXT: br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]] ; @@ -241,7 +241,7 @@ ; CHECK-NEXT: [[EL:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[INDVARS_IV]] ; CHECK-NEXT: store atomic i32 0, ptr [[EL]] unordered, align 4 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 -; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1 ; CHECK-NEXT: br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]] ; @@ -285,7 +285,7 @@ ; CHECK-NEXT: [[EL:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[INDVARS_IV]] ; CHECK-NEXT: store atomic i32 0, ptr [[EL]] unordered, align 4 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 -; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1 ; CHECK-NEXT: br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]] ; @@ -336,7 +336,7 @@ ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP0]], [[PREHEADER]] ] ; CHECK-NEXT: [[EL:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[INDVARS_IV]] ; CHECK-NEXT: store atomic i32 0, ptr [[EL]] unordered, align 4 -; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 ; CHECK-NEXT: br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]] ; @@ -398,7 +398,7 @@ ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP0]], [[PREHEADER]] ] ; CHECK-NEXT: [[EL:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[INDVARS_IV]] ; CHECK-NEXT: store atomic i32 0, ptr [[EL]] unordered, align 4 -; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 ; CHECK-NEXT: br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]] ;