[SCEV] Fix incorrect exit count calculated in error scope

[mdchen]

Summary

In computeLoadConstantCompareExitLimit, the addrec used to compute the
exit count should be from the loop which the exiting block belongs to.

[lebedev.ri]

This is missing a test.
Please refer to llvm-project/llvm/test/Analysis/ScalarEvolution/pr48225.ll for inspiration.

[mdchen]

@lebedev.ri Thanks, will add a test. Besides, the bug fixed in ea7ab5a42cd4 seems to have the same root cause.

[mdchen]

Add a test case.

[mkazantsev]

Please reduce the test or give an elaborate explanation of the problem. So far it's not clear to me what was the problem and why it fixed this way.

llvm/lib/Analysis/ScalarEvolution.cpp

7849

You require the IdxExpr be from a containing loop, which automatically makes IdxExpr invariant w.r.t. L. So this whole condition is just trivially false. Is that really what you want to make?

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

Please commit this test separately using auto-generated checks from utils/update_analyze_test_checks.py. If you are addressing some bug from bugs.llvm.com, better name the test after this bug (like prXXXXX.ll).

Then, apply your changes and re-run utils/update_analyze_test_checks.py on it. The diff will show what your patch has changed.

This test is very big. You could also try to use bugpoint tool to reduce the test (see https://llvm.org/docs/Bugpoint.html), because now I cannot figure what's going on here. Both test reduction (if possible) and explanatory comments (which block/loop are causing the problem and why) would be extremely useful to understand your fix.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

7849

Sorry, the whole condition is trivially true. AddRecs from containing loops are always invariant w.r.t child loops.

[mdchen]

llvm/lib/Analysis/ScalarEvolution.cpp

7849

You require the IdxExpr be from a containing loop, which automatically makes IdxExpr invariant w.r.t. L

I see...Actually what I need is IdxExpr->getLoop()==L. Though in this case it won't exceed the scope L from where Idx is computed IIUC, I admit it's incorrect. Will do the change.

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

I tried llvm-reduce but the output was not desirable, will add necessary comments, thanks! In short, the bug is that when computing the exit count of an outerloop's exiting block, the current computeLoadConstantCompareExitLimit method may choose an addrec of its child loop, which is incorrect.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

Then at least do the first step: commit this test as is with auto-generated checks, and then rebase your patch on top of that to show what has changed.

[mdchen]

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

Sorry, I don't understand well. Do you mean that I should separate it into two commits or only keep those changed checks?

[mdchen]

ping

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

I mean two commits.

First commit: this test, with no code changes, with auto-generated checks (use utils/update_analyze_test_checks.py to generate them).
Second commit: your code changes + re-run of utils/update_analyze_test_checks.py to show what has changed.

[mdchen]

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

1

I've submitted the test in D94657, could you review and commit it for me since I don't have the access right.

[mdchen]

ping

[mkazantsev]

LGTM, thanks!

llvm/lib/Analysis/ScalarEvolution.cpp

if (!VarIdx)
     return getCouldNotCompute();
 
   // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
   // Check to see if X is a loop variant variable value now.
   const SCEV *Idx = getSCEV(VarIdx);
   Idx = getSCEVAtScope(Idx, L);
 
   // We can only recognize very limited forms of loop index expressions, in
-  // particular, only affine AddRec's like {C1,+,C2}.
+  // particular, only affine AddRec's like {C1,+,C2}<L>.
   const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
-  if (!IdxExpr || !IdxExpr->isAffine() || isLoopInvariant(IdxExpr, L) ||
+  if (!IdxExpr || IdxExpr->getLoop() != L || !IdxExpr->isAffine() ||
+      isLoopInvariant(IdxExpr, L) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
     return getCouldNotCompute();
 
   unsigned MaxSteps = MaxBruteForceIterations;
   for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
     ConstantInt *ItCst = ConstantInt::get(
                            cast<IntegerType>(IdxExpr->getType()), IterationNum);

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
 @b = dso_local global i32 5, align 4
 @__const.f.g = private unnamed_addr constant [1 x [4 x i16]] [[4 x i16] [i16 1, i16 0, i16 0, i16 0]], align 2
 @a = common dso_local global i32 0, align 4
 @c = common dso_local global i32 0, align 4
 @d = common dso_local global i32 0, align 4
 @e = common dso_local global i32 0, align 4
 
 ; When inner.loop is taken as an exiting block of outer.loop, we cannot use the
 ; addrec of %storemerge1921.3, which is {3, +, -1}<inner.loop>, to calculate the
 ; exit count because it doesn't belong to outer.loop.
 define dso_local i32 @f() {
 ; CHECK-LABEL: 'f'
 ; CHECK-NEXT:  Classifying expressions for: @f
 ; CHECK-NEXT:    %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
-; CHECK-NEXT:    --> {3,+,-1}<nsw><%outer.loop> U: [-2147483648,4) S: [-2147483648,4) Exits: 3 LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
+; CHECK-NEXT:    --> {3,+,-1}<nsw><%outer.loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
 ; CHECK-NEXT:    %storemerge1921 = phi i32 [ 3, %outer.loop ], [ %dec, %for.end ]
 ; CHECK-NEXT:    --> {3,+,-1}<nuw><nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %idxprom20 = zext i32 %storemerge1921 to i64
 ; CHECK-NEXT:    --> {3,+,4294967295}<nuw><nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20
 ; CHECK-NEXT:    --> {(6 + @__const.f.g)<nuw>,+,8589934590}<nuw><%for.cond6> U: [6,-1) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %i = load i16, i16* %arrayidx7, align 2
 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }

 ; CHECK-NEXT:    --> %i7 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %i8 = load volatile i32, i32* @b, align 4
 ; CHECK-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %dec.3 = add nsw i32 %storemerge1921.3, -1
 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%inner.loop> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
 ; CHECK-NEXT:    --> %storemerge1921.lcssa25.3 U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Variant, %for.cond6: Invariant, %inner.loop: Invariant }
 ; CHECK-NEXT:    %dec16 = add nsw i32 %storemerge23, -1
-; CHECK-NEXT:    --> {2,+,-1}<nw><%outer.loop> U: full-set S: full-set Exits: 2 LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
+; CHECK-NEXT:    --> {2,+,-1}<nsw><%outer.loop> U: [0,3) S: [0,3) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
 ; CHECK-NEXT:  Determining loop execution counts for: @f
 ; CHECK-NEXT:  Loop %for.cond6: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for for.cond6: 0
 ; CHECK-NEXT:    exit count for for.end: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %for.cond6: max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %for.cond6: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT:  Loop %inner.loop: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT:    exit count for inner.loop: 0
 ; CHECK-NEXT:    exit count for for.end.3: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:  Loop %inner.loop: max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %inner.loop: Unpredictable predicated backedge-taken count.
-; CHECK-NEXT:  Loop %outer.loop: <multiple exits> backedge-taken count is 0
-; CHECK-NEXT:    exit count for for.cond6: 0
-; CHECK-NEXT:    exit count for inner.loop: 0
+; CHECK-NEXT:  Loop %outer.loop: <multiple exits> Unpredictable backedge-taken count.
+; CHECK-NEXT:    exit count for for.cond6: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:    exit count for inner.loop: ***COULDNOTCOMPUTE***
 ; CHECK-NEXT:    exit count for for.inc13.3: 2
-; CHECK-NEXT:  Loop %outer.loop: max backedge-taken count is 0
-; CHECK-NEXT:  Loop %outer.loop: Predicated backedge-taken count is 0
-; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %outer.loop: Trip multiple is 0
+; CHECK-NEXT:  Loop %outer.loop: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %outer.loop: Unpredictable predicated backedge-taken count.
 ;
 entry:
   store i32 3, i32* @a, align 4
   br label %outer.loop
 
 outer.loop:                              ; preds = %for.inc13.3, %entry
   %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
   br label %for.cond6