[InstCombine] Transform bitwise (A >> C - 1, zext(icmp)) -> zext (bitwise(A < 0,...
authorXChy <xxs_chy@outlook.com>
Mon, 24 Jul 2023 11:04:32 +0000 (13:04 +0200)
committerNikita Popov <npopov@redhat.com>
Mon, 24 Jul 2023 11:04:32 +0000 (13:04 +0200)
commit8a0b2ca8217f3c4380c43ffd8d6b679db3805822
tree957792f4f4f842552e31dbeb567e1864f2e775c9
parent724e2b1225cd7ef7ec1f43dcbe77c9f9f35958d2
[InstCombine] Transform bitwise (A >> C - 1, zext(icmp)) -> zext (bitwise(A < 0, icmp))

This extends foldCastedBitwiseLogic to handle the similar cases.
I have recently submitted a patch to implement a single fold like:

(A > 0) | (A < 0) -> zext (A != 0)

But it is not general enough, and some problems like
a < b & a >= b - 1 happen again.

So I generalize this fold by matching the pattern
bitwise(A >> C - 1, zext(icmp)), and replace A >> C - 1 with
zext(A < 0) here. (C is the scalar size bits of the type of A.)

Then we get bitwise(zext(A < 0), zext(icmp)), this will be folded
by original code in foldCastedBitwiseLogic, into
zext(bitwise(A < 0, icmp)). And finally, any related icmp fold will
be automatically implemented because bitwise(icmp,icmp) had been
implemented.

The proof of the correctness is obvious, because the folds below
were previously proved and implemented.
  A >> C - 1 -> zext(A < 0)
  bitwise(zext(A), zext(B)) -> zext(bitwise(A, B))
And the fold of this patch is the combination of folds above.

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

Differential Revision: https://reviews.llvm.org/D154791
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
llvm/test/Transforms/InstCombine/and-or-icmps.ll