[llvm-dev] Early legalization pass ? Doing early legalization in an existing pass ?

[Amaury SECHET via llvm-dev]

Hi all,

Some non trivial legalization of operations which aren't supported by the
backend would benefit from having the optimizer pass on them. I noticed
some example trying to optimize various pieces of code over the past weeks.

One offender is the cttz/ctlz intrinsic when defined on 0. On X86, BSR and
NSF are undefined on 0, and only recent CPU have the LZCNT and TZCNT
instructions that are properly defined for 0. The backend insert code with
a branch that checks for 0 and use bsf/bsr or just use a constant.

But if we are to branch anyway, and one path of the branch set the value as
a constant, there are some obvious optimization which can be done, starting
with constant folding. None of these happen in the backend and it doesn't
seems to be the right place anyway. See for instance the sample code from a
serialization/deserialization routine (the code has been tuned to
illustrate the problem in a brief way) :

auto a = ctlz(n, false);
auto b = ((a * 36) + 35) >> 8;

Which will be synthesized as follow:

auto a = (n == 0) ? 64 : ctlz(n, true);
auto b = ((a * 36) + 35) >> 8;

But obviously, recomputing b in the case n is 0 is completely pointless
work. A better codegen would be something like:

if (n == 0) {
  a = 64;
  b = 0;
} else {
  a = ctlz(n, true);
  b = ((a * 36) + 35) >> 8;
}

The optimizer knows how to do these kind of transformations, but the
backend do not. I encountered the same issue a some time back in a memory
allocator, and worked around it, but as I'm encountering it again in the
serialization library, I'm assuming there may be some untapped source of
optimizations here.

I was unsure about where these optimizations should take place. Clearly, we
want to do them early in the pipeline so that other passes can pick up on
it. I was looking around but it didn't seemed like there was a good place
to add this transformation.

Other examples of legalization that may benefit from the optimizer are
splitting of large integral that the backend do not support into multiple
operations on smaller integrals.

Would a EarlyLegalization pass be worth it ? It could use infos from the
backend and do various transformations that the backend would have to do
anyway, which will expose optimization opportunities. Or is there a place
that is appropriate to insert theses ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170123/4d99654e/attachment.html>