[SCEV] Remember blocks for which we know symbolic exit count but not exact

[mkazantsev]

Summary

The old code didn't bother to memoize blocks for which exact exit count is not
known. As result, in situation when exact isn't known but symbolic is known, this
info was lost. This patch fixes the situation: now we memoize when symbolic is
known (exact always implies symbolic, so this is a strict superset of what was before).

[nikic]

LG

llvm/lib/Analysis/ScalarEvolution.cpp

assert((AllowPredicates || EL.Predicates.empty()) &&
            "Predicated exit limit when predicates are not allowed!");
 
     // 1. For each exit that can be computed, add an entry to ExitCounts.
     // CouldComputeBECount is true only if all exits can be computed.
     if (EL.ExactNotTaken == getCouldNotCompute())
       // We couldn't compute an exact value for this exit, so
       // we won't be able to compute an exact value for the loop.
       CouldComputeBECount = false;
-    else
+    // Remember exit count if either exact or symbolic is known. Because
+    // Exact always implies symbolic, only check symbolic.
+    if (EL.SymbolicMaxNotTaken != getCouldNotCompute())
       ExitCounts.emplace_back(ExitBB, EL);
+    else
+      assert(EL.ExactNotTaken == getCouldNotCompute() &&
+             "Exact is known but symbolic isn't?");
 
     // 2. Derive the loop's MaxBECount from each exit's max number of
     // non-exiting iterations. Partition the loop exits into two kinds:
     // LoopMustExits and LoopMayExits.
     //
     // If the exit dominates the loop latch, it is a LoopMustExit otherwise it
     // is a LoopMayExit.  If any computable LoopMustExit is found, then
     // MaxBECount is the minimum EL.ConstantMaxNotTaken of computable

llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll

 ; CHECK-NEXT:    --> {(sext i32 {%iv,+,1}<nsw><%loop2> to i64),+,1}<nsw><%loop3> U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: (sext i32 {%iv,+,1}<nsw><%loop2> to i64) LoopDispositions: { %loop3: Computable, %loop.header: Variant }
 ; CHECK-NEXT:    %iv3.next = add nsw i64 %iv3, 1
 ; CHECK-NEXT:    --> {(1 + (sext i32 {%iv,+,1}<nsw><%loop2> to i64))<nsw>,+,1}<nsw><%loop3> U: [-2147483647,2147483649) S: [-2147483647,2147483649) Exits: (1 + (sext i32 {%iv,+,1}<nsw><%loop2> to i64))<nsw> LoopDispositions: { %loop3: Computable, %loop.header: Variant }
 ; CHECK-NEXT:    %iv.next = trunc i64 %iv3 to i32
 ; CHECK-NEXT:    --> {{\{}}{%iv,+,1}<nsw><%loop2>,+,1}<%loop3> U: full-set S: full-set --> {%iv,+,1}<nsw><%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Variant, %loop3: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test
 ; CHECK-NEXT:  Loop %loop2: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %loop2: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop2: Unpredictable symbolic max backedge-taken count.
+; CHECK-NEXT:  Loop %loop2: symbolic max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %loop2: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT:  Loop %loop3: backedge-taken count is false
 ; CHECK-NEXT:  Loop %loop3: constant max backedge-taken count is false
 ; CHECK-NEXT:  Loop %loop3: symbolic max backedge-taken count is false
 ; CHECK-NEXT:  Loop %loop3: Predicated backedge-taken count is false
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop3: Trip multiple is 1
 ; CHECK-NEXT:  Loop %loop.header: <multiple exits> Unpredictable backedge-taken count.

llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll

 ; CHECK-NEXT:    %loop_cond = call i1 @cond()
 ; CHECK-NEXT:    --> %loop_cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_litter_conditions
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for range_check_block: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
-; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is -1
+; CHECK-NEXT:    symbolic max exit count for loop: -1
 ; CHECK-NEXT:    symbolic max exit count for range_check_block: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    symbolic max exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %loop
 
 loop:

 ; CHECK-NEXT:    %loop_cond = call i1 @cond()
 ; CHECK-NEXT:    --> %loop_cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_litter_conditions_bad_context
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for range_check_block: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
-; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is -1
+; CHECK-NEXT:    symbolic max exit count for loop: -1
 ; CHECK-NEXT:    symbolic max exit count for range_check_block: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    symbolic max exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %loop
 
 loop:

 ; CHECK-NEXT:    --> {(-1 + %start),+,-1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %loop_cond = call i1 @cond()
 ; CHECK-NEXT:    --> %loop_cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_and_conditions
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
-; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is -1
+; CHECK-NEXT:    symbolic max exit count for loop: -1
 ; CHECK-NEXT:    symbolic max exit count for backedge: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]

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

 ; One side of the expression test against a value that will be skipped.
 ; We can't assume undefined behavior just because we have an NSW flag.
 ;
 define void @exit_orcond_nsw(i32 *%a) nounwind {
 ; CHECK-LABEL: 'exit_orcond_nsw'
 ; CHECK-NEXT:  Determining loop execution counts for: @exit_orcond_nsw
 ; CHECK-NEXT:  Loop %for.body.i: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body.i: constant max backedge-taken count is 1
-; CHECK-NEXT:  Loop %for.body.i: Unpredictable symbolic max backedge-taken count.
+; CHECK-NEXT:  Loop %for.body.i: symbolic max backedge-taken count is 1
 ; CHECK-NEXT:  Loop %for.body.i: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %for.body.i
 
 for.body.i:                                       ; preds = %for.body.i, %entry
   %b.01.i = phi i32 [ 0, %entry ], [ %add.i, %for.body.i ]
   %tobool.i = icmp ne i32 %b.01.i, 0

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

 
 declare void @Doit_bb7([15 x i32]*, [17 x i32]*, [9 x i32]*) nounwind
 
 define void @Doit_bb7_2E_i([9 x i32]* %x1, [15 x i32]* %c, [17 x i32]* %b, [9 x i32]* %a, i32* %q, i32* %x1.sub, i32* %b9, i32* %a10, i32* %c11) nounwind {
 ; CHECK-LABEL: 'Doit_bb7_2E_i'
 ; CHECK-NEXT:  Determining loop execution counts for: @Doit_bb7_2E_i
 ; CHECK-NEXT:  Loop %bb7.i: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %bb7.i: constant max backedge-taken count is 8
-; CHECK-NEXT:  Loop %bb7.i: Unpredictable symbolic max backedge-taken count.
+; CHECK-NEXT:  Loop %bb7.i: symbolic max backedge-taken count is 8
 ; CHECK-NEXT:  Loop %bb7.i: Unpredictable predicated backedge-taken count.
 ;
 newFuncRoot:
   br label %bb7.i
 
 Try.exit.exitStub:    ; preds = %bb7.i
   ret void
 

llvm/test/Analysis/ScalarEvolution/widenable-condition.ll

 ; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2001) S: [1,2001) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %widenable_cond3 = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    --> %widenable_cond3 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %exiplicit_guard_cond4 = and i1 %cond_1, %widenable_cond3
 ; CHECK-NEXT:    --> (%cond_1 umin %widenable_cond3) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @wc_max
 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 1999
-; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 1999
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   br label %loop
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %loop]
   %iv.next = add i32 %iv, 1
   store i32 %iv, i32 *@G