Author: Max Kazantsev Date: 2020-11-23T16:52:39+07:00 New Revision: 48d7cc6ae23b0e5b1922457462d0f6e4582a1ae7
URL: https://github.com/llvm/llvm-project/commit/48d7cc6ae23b0e5b1922457462d0f6e4582a1ae7 DIFF: https://github.com/llvm/llvm-project/commit/48d7cc6ae23b0e5b1922457462d0f6e4582a1ae7.diff LOG: [SCEV] Fix incorrect treatment of max taken count. PR48225 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. Differential Revision: https://reviews.llvm.org/D91942 Reviewed By: nikic Added: Modified: llvm/lib/Analysis/ScalarEvolution.cpp llvm/test/Analysis/ScalarEvolution/pr48225.ll Removed: ################################################################################ diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 496b0da8853a..a366ad355233 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -7611,8 +7611,6 @@ ScalarEvolution::computeExitLimitFromCondFromBinOpHelper( } 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; } diff --git a/llvm/test/Analysis/ScalarEvolution/pr48225.ll b/llvm/test/Analysis/ScalarEvolution/pr48225.ll index bd7dac26ebd3..eaf9b18d7c5a 100644 --- a/llvm/test/Analysis/ScalarEvolution/pr48225.ll +++ b/llvm/test/Analysis/ScalarEvolution/pr48225.ll @@ -4,7 +4,6 @@ ; 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; @@ -17,16 +16,16 @@ define void @test_and(i1 %boolcond) { ; 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: @@ -52,7 +51,6 @@ 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; @@ -65,16 +63,16 @@ define void @test_or(i1 %boolcond) { ; 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: _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits