[SCEV] Fix isImpliedViaMerge() with values from previous iteration (PR56242)
authorNikita Popov <npopov@redhat.com>
Mon, 27 Jun 2022 13:09:24 +0000 (15:09 +0200)
committerNikita Popov <npopov@redhat.com>
Tue, 5 Jul 2022 13:31:23 +0000 (15:31 +0200)
commite4d1d0cc2c9ca38f98bc9b70c3e3db3a18f1e06e
tree2c53b9f39bec16b2e6320e54f38af351c707ef40
parent6e2058e58832058f05372c93e8be50695efcc6be
[SCEV] Fix isImpliedViaMerge() with values from previous iteration (PR56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about values coming
from a backedge, as these may refer to a previous loop iteration.
A variant of this issue was fixed in D101829, but the dominance
condition used there isn't quite right: It checks that the value
dominates the incoming block, which doesn't exclude backedges
(values defined in a loop will usually dominate the loop latch,
which is the incoming block of the backedge).

Instead, we should be checking for domination of the phi block.
Any values defined inside the loop will not dominate the loop
header phi.

Fixes https://github.com/llvm/llvm-project/issues/56242.

Differential Revision: https://reviews.llvm.org/D128640
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Transforms/IRCE/decrementing-loop.ll
llvm/test/Transforms/IndVarSimplify/pr56242.ll