[SCEV] Fix incorrect treatment of max taken count. PR48225

[mkazantsev]

Summary

SCEV makes a logical mistake when handling EitherMayExit in
case when both conditions must be met to exit the loop. The
mistake looks like follows: "if condition A fails within at most X first
iterations, and B fails within at most Y first iterations, then A & B
fails at most within min (X, Y) first iterations". This is wrong, because
both of them must fail at the same time.

Simple example illustrating this is following: we have an IV with step 1,
condition A = "IV is even", condition B = "IV is odd". Both A and B
will fail within first two iterations. But it doesn't mean that both of them
will fail within first two first iterations at the same time, which would mean
that IV is neither even nor odd at the same time within first 2 iterations.

We can only do so for known exact BE counts, but not for max.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

if (EL0.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL1.MaxNotTaken;
     else if (EL1.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL0.MaxNotTaken;
     else
       MaxBECount = getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken);
   } else {
     // Both conditions must be same at the same time for the loop to exit.
     // For now, be conservative.
-    if (EL0.MaxNotTaken == EL1.MaxNotTaken)
-      MaxBECount = EL0.MaxNotTaken;
     if (EL0.ExactNotTaken == EL1.ExactNotTaken)
       BECount = EL0.ExactNotTaken;
   }
 
   // There are cases (e.g. PR26207) where computeExitLimitFromCond is able
   // to be more aggressive when computing BECount than when computing
   // MaxBECount.  In these cases it is possible for EL0.ExactNotTaken and
   // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken

llvm/test/Analysis/ScalarEvolution/pr48225.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; Tests demonstrate the bug reported as PR48225 by Congzhe Cao.
 
-; FIXME: This test demonstrates a bug in max backedge taken count computation.
 ; When %boolcond = false and %cond = 0:
 ; - %cond.false.on.first.iter is false on 1st iteration;
 ; - %cond.false.on.second.iter is false on 2nd iteration;
 ; - Therefore, their AND is false on first two iterations, and the backedge is taken twice.
 ;  'max backedge-taken count is 1' is a bug caused by wrong treatment of AND
 ;  condition in the computation logic. It should be 2.
 define void @test_and(i1 %boolcond) {
 ; CHECK-LABEL: 'test_and'
 ; CHECK-NEXT:  Classifying expressions for: @test_and
 ; CHECK-NEXT:    %conv = zext i1 %boolcond to i32
 ; CHECK-NEXT:    --> (zext i1 %boolcond to i32) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %inc, %backedge ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2) S: [0,2) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %or.cond = and i1 %cond.false.on.first.iter, %cond.false.on.second.iter
 ; CHECK-NEXT:    --> %or.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %inc = add nuw nsw i32 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,3) S: [1,3) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_and
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for loop: 2
 ; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   %conv = zext i1 %boolcond to i32
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %inc, %backedge ]

 
 exit:
   unreachable
 
 for.end:
   ret void
 }
 
-; FIXME: This test demonstrates a bug in max backedge taken count computation.
 ; When %boolcond = false and %cond = 0:
 ; - %cond.true.on.first.iter is true on 1st iteration;
 ; - %cond.true.on.second.iter is true on 2nd iteration;
 ; - Therefore, their OR is true on first two iterations, and the backedge is taken twice.
 ;  'max backedge-taken count is 1' is a bug caused by wrong treatment of OR
 ;  condition in the computation logic. It should be 2.
 define void @test_or(i1 %boolcond) {
 ; CHECK-LABEL: 'test_or'
 ; CHECK-NEXT:  Classifying expressions for: @test_or
 ; CHECK-NEXT:    %conv = zext i1 %boolcond to i32
 ; CHECK-NEXT:    --> (zext i1 %boolcond to i32) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %inc, %backedge ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2) S: [0,2) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,3) S: [0,3) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %or.cond = or i1 %cond.true.on.first.iter, %cond.true.on.second.iter
 ; CHECK-NEXT:    --> %or.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %inc = add nuw nsw i32 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,3) S: [1,3) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_or
 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for loop: 2
 ; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   %conv = zext i1 %boolcond to i32
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %inc, %backedge ]