This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Determine demanded and known bits for funnel shifts
ClosedPublic

Authored by nikic on Nov 24 2018, 7:18 AM.

Details

Summary

Support funnel shifts in InstCombine demanded bits simplification. If the shift amount is constant, we can determine both the demanded bits of the operands, as well as the known bits of the result.

If one of the operands has no demanded bits, it will be replaced by undef and the funnel shift will be simplified into a simple shift due to the simplifications added in D54778.


This change has been split off from D54666.

Another place where support for computing fsh demanded bits can be added is the DemandedBits analysis driving BDCE. This will allow handling funnel shifts with multiple uses. Unfortunately DemandedBits only tracks bits on a per-instruction level, so that the different demanded bits of the two operands cannot be leveraged.

Diff Detail

Event Timeline

nikic created this revision.Nov 24 2018, 7:18 AM
nikic marked an inline comment as done.Nov 24 2018, 7:23 AM
nikic added inline comments.
test/Transforms/InstCombine/fsh.ll
292

This first simplifies to (x << 26) >> 30, which is then reduced to (x >> 4) & 7.

spatel accepted this revision.Nov 24 2018, 9:47 AM
spatel added a subscriber: nagisa.

LGTM. I don't know if vector types will show the same simplifications, but it would be nice to have at least one of the tests repeated with a vector type, so we know if that is missing or works as expected.

Also, I know we're not getting the motivating case due to multi-use, and I agree with @nagisa that it should be filed as a bug report because I'm also not sure how to solve it.

This revision is now accepted and ready to land.Nov 24 2018, 9:47 AM
This revision was automatically updated to reflect the committed changes.

I've added two tests for vectors. It works for the constant splat case, and fails if it's only constant modulo the bitwidth. That may be something we want to handle in the future (also for the zero shift case).

I've opened a bug report for the multi-use case here: https://bugs.llvm.org/show_bug.cgi?id=39771

I think the next step here would be to add support for funnel shifts to DemandedBits analysis and ValueTracking. It won't solve the motivating case either, but may help for other things.