[CVP] Expand bound `urem`s
authorRoman Lebedev <lebedev.ri@gmail.com>
Fri, 30 Dec 2022 16:06:59 +0000 (19:06 +0300)
committerRoman Lebedev <lebedev.ri@gmail.com>
Fri, 30 Dec 2022 16:40:46 +0000 (19:40 +0300)
commit66efb986322b206834e7c9e1eb777fa053912c39
tree8e11a7e5cabb173f606e2b99ed543a64b5f4ed16
parent3cb827f9d3e9c502a1a08f1de1980e906aa30c3d
[CVP] Expand bound `urem`s

This kind of thing happens really frequently in LLVM's very own
shuffle combining methods, and it is even considered bad practice
to use `%` there, instead of using this expansion directly.
Though, many of the cases there have variable divisors,
so this won't help everything.

Simple case: https://alive2.llvm.org/ce/z/PjvYf-
There's alternative expansion via `umin`:
https://alive2.llvm.org/ce/z/hWCVPb

BUT while we can transform the first expansion
into the `umin` one (e.g. for SCEV):
https://alive2.llvm.org/ce/z/iNxKmJ
... we can't go in the opposite direction.

Also, the non-`umin` expansion seems somewhat more codegen-friendly:
https://godbolt.org/z/qzjx5bqWK
https://godbolt.org/z/a7bj1axbx

There's second variant of precondition:
https://alive2.llvm.org/ce/z/zE6cbM
but there the numerator must be non-undef / must be frozen.
llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
llvm/test/Transforms/CorrelatedValuePropagation/urem-expansion.ll
llvm/test/Transforms/CorrelatedValuePropagation/urem.ll
llvm/test/Transforms/PhaseOrdering/cmp-logic.ll