[LVI] Look through negations when evaluating conditions
authorKeno Fischer <keno@juliacomputing.com>
Wed, 4 Jan 2023 01:49:17 +0000 (01:49 +0000)
committerKeno Fischer <keno@juliacomputing.com>
Thu, 5 Jan 2023 23:03:46 +0000 (23:03 +0000)
commit1436a9232b10487a097f62bf85025fc6b6b66fde
tree3f324d2b73f9997eabdf2c7d5c402cd07401e2bf
parentcf8fd210a35c8e93136cb8edc5c6a2e818dc1b1d
[LVI] Look through negations when evaluating conditions

This teaches LVI (and thus CVP) to extract range information
from branches whose condition is negated using (`xor %c, true`).
On the implementation side, we switch the cache to additionally
track whether we're looking for the inverted value or not and
otherwise using the existing support for computing inverted
conditions.

I think the biggest question here is why this negation shows up
here at all. After all, it should always be possible for some
other pass to fold such a negation into a branch, comparison or
some other logical operation. Indeed, instcombine does just that.
However, these negations can be otherwise fairly persistent, e.g.
instsimplify is not able to exchange branch conditions from
negations. In addition, jumpthreading, which sits at the same
point in default pass pipeline also handles this pattern, which
adds further evidence that we might expect these negations to
not have been canonicalized away yet at this point in the pass
pipeline.

In the particular case I was looking at there was a bit of a
circular dependency where flags computed by cvp were needed
by instcombine, and incstombine's folding of the negation was
needed for cvp. Adding a second instombine pass would have
worked of course, but instcombine can be somewhat expensive,
so it appeared desirable to not require it to have run
before cvp (as is the case in the default pass pipeline).

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D140933
llvm/lib/Analysis/LazyValueInfo.cpp
llvm/test/Transforms/CorrelatedValuePropagation/basic.ll