[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

7828

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

7828

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

7828

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}<L2> where L is inside L2.
   const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
-  if (!IdxExpr || !IdxExpr->isAffine() || isLoopInvariant(IdxExpr, L) ||
+  if (!IdxExpr || !IdxExpr->getLoop()->contains(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

+; 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 5, i16 0, i16 0, i16 2]], 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
+
+define dso_local i32 @f() {
+; CHECK:  -->  {2,+,-1}<nsw><%for.cond1.preheader> U: [0,3) S: [0,3)    Exits: <<Unknown>>
+; CHECK:    Loop %for.cond1.preheader: <multiple exits> Unpredictable backedge-taken count.
+; CHECK:    exit count for for.cond6: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.1: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.2: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.3: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.inc13.3: 2
+; CHECK:  Loop %for.cond1.preheader: max backedge-taken count is 2
+; CHECK:  Loop %for.cond1.preheader: Unpredictable predicated backedge-taken count.
+
+entry:
+  store i32 3, i32* @a, align 4
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc13.3
+  %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
+  br label %for.cond3.preheader
+
+for.cond3.preheader:                              ; preds = %for.cond1.preheader
+  br label %for.cond6
+
+for.cond6:                                        ; preds = %for.end, %for.cond3.preheader
+  %storemerge1921 = phi i32 [ 3, %for.cond3.preheader ], [ %dec, %for.end ]
+  %idxprom20 = zext i32 %storemerge1921 to i64
+  %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20
+  %0 = load i16, i16* %arrayidx7, align 2
+  %tobool8 = icmp eq i16 %0, 0
+  br i1 %tobool8, label %if.end.loopexit, label %for.end
+
+if.end.loopexit:                                  ; preds = %for.cond6
+  %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
+  br label %if.end
+
+if.end.loopexit27:                                ; preds = %for.cond6.1
+  %storemerge1822.lcssa.ph28 = phi i32 [ 1, %for.cond6.1 ]
+  br label %if.end
+
+if.end.loopexit29:                                ; preds = %for.cond6.2
+  %storemerge1822.lcssa.ph30 = phi i32 [ 2, %for.cond6.2 ]
+  br label %if.end
+
+if.end.loopexit31:                                ; preds = %for.cond6.3
+  %storemerge1822.lcssa.ph32 = phi i32 [ 3, %for.cond6.3 ]
+  br label %if.end
+
+if.end:                                           ; preds = %if.end.loopexit31, %if.end.loopexit29, %if.end.loopexit27, %if.end.loopexit
+  %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph28, %if.end.loopexit27 ], [ %storemerge1822.lcssa.ph30, %if.end.loopexit29 ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
+  store i32 %storemerge1822.lcssa, i32* @c, align 4
+  store i32 2, i32* @d, align 4
+  %1 = load i32, i32* @e, align 4
+  br label %cleanup
+
+for.end:                                          ; preds = %for.cond6
+  %2 = load volatile i32, i32* @b, align 4
+  %tobool9 = icmp eq i32 %2, 0
+  %dec = add nsw i32 %storemerge1921, -1
+  br i1 %tobool9, label %for.cond6, label %for.inc13
+
+for.inc13:                                        ; preds = %for.end
+  br label %for.cond6.1
+
+cleanup.loopexit:                                 ; preds = %for.inc13.3
+  %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
+  store i32 %inc.lcssa.lcssa, i32* @c, align 4
+  br label %cleanup
+
+cleanup:                                          ; preds = %cleanup.loopexit, %if.end
+  %retval.0 = phi i32 [ %1, %if.end ], [ 0, %cleanup.loopexit ]
+  ret i32 %retval.0
+
+for.cond6.1:                                      ; preds = %for.end.1, %for.inc13
+  %storemerge1921.1 = phi i32 [ 3, %for.inc13 ], [ %dec.1, %for.end.1 ]
+  %idxprom20.1 = zext i32 %storemerge1921.1 to i64
+  %arrayidx7.1 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.1
+  %3 = load i16, i16* %arrayidx7.1, align 2
+  %tobool8.1 = icmp eq i16 %3, 0
+  br i1 %tobool8.1, label %if.end.loopexit27, label %for.end.1
+
+for.end.1:                                        ; preds = %for.cond6.1
+  %4 = load volatile i32, i32* @b, align 4
+  %tobool9.1 = icmp eq i32 %4, 0
+  %dec.1 = add nsw i32 %storemerge1921.1, -1
+  br i1 %tobool9.1, label %for.cond6.1, label %for.inc13.1
+
+for.inc13.1:                                      ; preds = %for.end.1
+  br label %for.cond6.2
+
+for.cond6.2:                                      ; preds = %for.end.2, %for.inc13.1
+  %storemerge1921.2 = phi i32 [ 3, %for.inc13.1 ], [ %dec.2, %for.end.2 ]
+  %idxprom20.2 = zext i32 %storemerge1921.2 to i64
+  %arrayidx7.2 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.2
+  %5 = load i16, i16* %arrayidx7.2, align 2
+  %tobool8.2 = icmp eq i16 %5, 0
+  br i1 %tobool8.2, label %if.end.loopexit29, label %for.end.2
+
+for.end.2:                                        ; preds = %for.cond6.2
+  %6 = load volatile i32, i32* @b, align 4
+  %tobool9.2 = icmp eq i32 %6, 0
+  %dec.2 = add nsw i32 %storemerge1921.2, -1
+  br i1 %tobool9.2, label %for.cond6.2, label %for.inc13.2
+
+for.inc13.2:                                      ; preds = %for.end.2
+  br label %for.cond6.3
+
+for.cond6.3:                                      ; preds = %for.end.3, %for.inc13.2
+  %storemerge1921.3 = phi i32 [ 3, %for.inc13.2 ], [ %dec.3, %for.end.3 ]
+  %idxprom20.3 = zext i32 %storemerge1921.3 to i64
+  %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
+  %7 = load i16, i16* %arrayidx7.3, align 2
+  %tobool8.3 = icmp eq i16 %7, 0
+  br i1 %tobool8.3, label %if.end.loopexit31, label %for.end.3
+
+for.end.3:                                        ; preds = %for.cond6.3
+  %8 = load volatile i32, i32* @b, align 4
+  %tobool9.3 = icmp eq i32 %8, 0
+  %dec.3 = add nsw i32 %storemerge1921.3, -1
+  br i1 %tobool9.3, label %for.cond6.3, label %for.inc13.3
+
+for.inc13.3:                                      ; preds = %for.end.3
+  %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
+  store i32 %storemerge1921.lcssa25.3, i32* @d, align 4
+  %dec16 = add nsw i32 %storemerge23, -1
+  store i32 %dec16, i32* @a, align 4
+  %tobool = icmp eq i32 %dec16, 0
+  br i1 %tobool, label %cleanup.loopexit, label %for.cond1.preheader
+}