Author: Florian Hahn Date: 2021-05-11T20:52:59-07:00 New Revision: 4e46ff469405bc73ec25fcf78126fb5fbd7a18a1
URL: https://github.com/llvm/llvm-project/commit/4e46ff469405bc73ec25fcf78126fb5fbd7a18a1 DIFF: https://github.com/llvm/llvm-project/commit/4e46ff469405bc73ec25fcf78126fb5fbd7a18a1.diff LOG: [SCEV] By more careful when traversing phis in isImpliedViaMerge. I think currently isImpliedViaMerge can incorrectly return true for phis in a loop/cycle, if the found condition involves the previous value of Consider the case in exit_cond_depends_on_inner_loop. At some point, we call (modulo simplifications) isImpliedViaMerge(<=, %x.lcssa, -1, %call, -1). The existing code tries to prove IncV <= -1 for all incoming values InvV using the found condition (%call <= -1). At the moment this succeeds, but only because it does not compare the same runtime value. The found condition checks the value of the last iteration, but the incoming value is from the *previous* iteration. Hence we incorrectly determine that the *previous* value was <= -1, which may not be true. I think we need to be more careful when looking at the incoming values here. In particular, we need to rule out that a found condition refers to any value that may refer to one of the previous iterations. I'm not sure there's a reliable way to do so (that also works of irreducible control flow). So for now this patch adds an additional requirement that the incoming value must properly dominate the phi block. This should ensure the values do not change in a cycle. I am not entirely sure if will catch all cases and I appreciate a through second look in that regard. Alternatively we could also unconditionally bail out in this case, instead of checking the incoming values Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D101829 (cherry picked from commit 6c99e631201aaea0a75708749cbaf2ba08a493f9) Added: Modified: llvm/lib/Analysis/ScalarEvolution.cpp llvm/test/Transforms/IRCE/decrementing-loop.ll llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll Removed: ################################################################################ diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index fe9d8297d679..1a9ae68573e9 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -10622,6 +10622,10 @@ bool ScalarEvolution::isImpliedViaMerge(ICmpInst::Predicate Pred, if (!dominates(RHS, IncBB)) return false; const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); + // Make sure L does not refer to a value from a potentially previous + // iteration of a loop. + if (!properlyDominates(L, IncBB)) + return false; if (!ProvedEasily(L, RHS)) return false; } diff --git a/llvm/test/Transforms/IRCE/decrementing-loop.ll b/llvm/test/Transforms/IRCE/decrementing-loop.ll index a824522cf206..d809fb4f7d97 100644 --- a/llvm/test/Transforms/IRCE/decrementing-loop.ll +++ b/llvm/test/Transforms/IRCE/decrementing-loop.ll @@ -212,16 +212,17 @@ exit: ret void } +; TODO: we need to be more careful when trying to look through phi nodes in +; cycles, because the condition to prove may reference the previous value of +; the phi. So we currently fail to optimize this case. ; Check that we can figure out that IV is non-negative via implication through ; two Phi nodes, one being AddRec. define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) { ; CHECK-LABEL: test_05 -; CHECK: mainloop: -; CHECK-NEXT: br label %loop -; CHECK: loop: -; CHECK: br i1 true, label %in.bounds, label %out.of.bounds -; CHECK: loop.preloop: +; CHECK: entry: +; CHECK: br label %merge +; CHECK-NOT: mainloop entry: %len.a = load i32, i32* %a_len_ptr, !range !0 diff --git a/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll b/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll index eec7908b6a8b..e574c2f84ea3 100644 --- a/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll +++ b/llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll @@ -453,7 +453,8 @@ define i32 @exit_cond_depends_on_inner_loop() { ; CHECK-NEXT: br i1 [[INNER_COND]], label [[INNER]], label [[OUTER_EXITING_1:%.*]] ; CHECK: outer.exiting.1: ; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[INNER]] ] -; CHECK-NEXT: br i1 false, label [[EXIT:%.*]], label [[OUTER_LATCH]] +; CHECK-NEXT: [[OUTER_COND_1:%.*]] = icmp sgt i32 [[X_LCSSA]], -1 +; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[EXIT:%.*]], label [[OUTER_LATCH]] ; CHECK: outer.latch: ; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i32 [[IV_OUTER]], 1 ; CHECK-NEXT: [[OUTER_COND_2:%.*]] = icmp ult i32 [[IV_OUTER]], 100 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
