[SCEV] Apply loop-guards to addrec's start in howManyGreaterThans

[nikic]

It looks like there are many test failures.

The core problem with this change is that it makes the loop guard actually part of the returned BECount, which is generally not desirable if it will get expanded. Normally we only use loop guards to compute things like ranges.

[aleksandr.popov]

This change was related to https://reviews.llvm.org/D148001, but the final version of that patch is not based on Scev. So this change is not actual for now

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
   // Avoid proven overflow cases: this will ensure that the backedge taken count
   // will not generate any unsigned overflow. Relaxed no-overflow conditions
   // exploit NoWrapFlags, allowing to optimize in presence of undefined
   // behaviors like the case of C language.
   if (!Stride->isOne() && !NoWrap)
     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
     // min(RHS, Start) = RHS at this point.
     if (isLoopEntryGuardedByCond(
             L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, Start, RHS))
       End = RHS;
     else

llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; ScalarEvolution can't compute a trip count because it doesn't know if
 ; dividing by the stride will have a remainder. This could theoretically
 ; be teaching it how to use a more elaborate trip count computation.
 
 define i32 @f(i32 %x) nounwind readnone {
 ; 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
 ;
 entry:
   %0 = icmp ugt i32 %x, 4    ; <i1> [#uses=1]
   br i1 %0, label %bb.nph, label %bb2
 
 bb.nph:   ; preds = %entry

llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 define i32 @f(i32 %c.idx.val) {
 ; CHECK-LABEL: 'f'
 ; CHECK-NEXT:  Classifying expressions for: @f
 ; 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
 ;
 bb2:
   %k.018 = add i32 %c.idx.val, -1   ; <i32> [#uses=2]
   %a14 = icmp slt i32 %k.018, 0    ; <i1> [#uses=1]
   br i1 %a14, label %bb19, label %bb16.preheader
 

llvm/test/Analysis/ScalarEvolution/smin-smax-folds.ll

 declare void @iteration()
 
 ; Test case from PR46939.
 ; The information from the loop guard can be used to simplify the trip count expression.
 define void @smin_simplify_with_guard(i32 %n) {
 ; 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
 ;
 entry:
   %cmp10 = icmp sgt i32 %n, -1
   br i1 %cmp10, label %for.body.lr.ph, label %for.cond.cleanup
 
 for.body.lr.ph:

llvm/test/Analysis/ScalarEvolution/trip-count-from-loop-guard.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
 ; 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
 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
 ;
 entry:
   %cmp0 = icmp sgt i8 %const, 0
   br i1 %cmp0, label %loop, label %fail
 
 loop:

llvm/test/Analysis/ScalarEvolution/trip-count12.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 define zeroext i16 @test(ptr nocapture %p, i32 %len) nounwind readonly {
 ; 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
 ; CHECK-NEXT:    --> (zext i16 %0 to i32) U: [0,65536) S: [0,65536) Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
 ; 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
 ;
 entry:
   %cmp2 = icmp sgt i32 %len, 1
   br i1 %cmp2, label %for.body.preheader, label %for.end
 
 for.body.preheader:                               ; preds = %entry