This is an archive of the discontinued LLVM Phabricator instance.

[AggressiveInstCombine] convert a chain of 'or-shift' bits into masked compare
ClosedPublic

Authored by spatel on Apr 23 2018, 1:46 PM.

Details

Summary

and (or (lshr X, C), ...), 1 --> (X & C') != 0

I initially thought about implementing the minimal pattern in instcombine as mentioned here:
https://bugs.llvm.org/show_bug.cgi?id=37098#c6

...but we need to do better to catch the more general sequence from the motivating test (more than 2 bits in the compare). And a test-suite run with statistics showed that this pattern only happened 2 times currently. It would potentially happen more often if reassociation worked better (D45842), but it's probably still not too frequent?

This is small enough that I didn't see a need to create a whole new class/file within AggressiveInstCombine. There are likely other relatively small matchers like what was discussed in D44266 that would slide under foldUnusualPatterns() (name suggestions welcome). We could potentially also consolidate matchers for ctpop, bswap, etc under here.

Diff Detail

Repository
rL LLVM

Event Timeline

spatel created this revision.Apr 23 2018, 1:46 PM

This recognizes something like "bitmask-any", where the code checks if any of the bits of V indicated by the mask C' is set. It looks like by replacing or with and you would get the corresponding "bitmask-all". Would it be worthwhile to add it? I don't have a use case, but the symmetry seems somewhat compelling.

spatel added a comment.EditedMay 1 2018, 6:41 AM

This recognizes something like "bitmask-any", where the code checks if any of the bits of V indicated by the mask C' is set. It looks like by replacing or with and you would get the corresponding "bitmask-all". Would it be worthwhile to add it? I don't have a use case, but the symmetry seems somewhat compelling.

Yes, that's correct, and I agree. There are actually 4 similar patterns: any-set, all-set, any-clear, all-clear. We should recognize all of them. I didn't want to go overboard on this patch though because I wasn't sure if this implementation would receive support. At the least, I will add a 'TODO' comment to this patch. Then, we can follow-up to catch the other patterns.

kparzysz accepted this revision.May 1 2018, 7:05 AM

I think we should recognize as much as we can out of the common idioms, and this is one of them. Looks good to me.

lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
76 ↗(On Diff #143631)

You could also match arithmetic shifts-right as long as the shift amount does not move the sign bit into the 0th position. It's not necessary for this patch though.

This revision is now accepted and ready to land.May 1 2018, 7:05 AM
spatel added inline comments.May 1 2018, 10:18 AM
lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
76 ↗(On Diff #143631)

That's a good point. I am assuming this pass runs after instcombine, and instcombine would transform to lshr as a canonicalization step. This is as it happens currently, but might change as you've proposed.

I'll look at adding a phase-ordering test, so we'll know that we don't lose this optimization if the pass order changes.

This revision was automatically updated to reflect the committed changes.