Page MenuHomePhabricator

[InstCombine] canonicalize shift+logic+shift to reduce dependency chain

Authored by spatel on Nov 5 2019, 6:14 AM.



shift (logic (shift X, C0), Y), C1 --> logic (shift X, C0+C1), (shift Y, C1)

This is an IR translation of an existing SDAG transform added here:

So we again have 9 possible patterns with a commuted IR variant of each pattern:

Part of the motivation is to allow easier recognition and subsequent canonicalization of bswap patterns as discussed in PR43146:

We had to delay this transform because it used to allow the SLP vectorizer to create awful reductions out of simple load-combines. That problem was fixed with:
(we'll bring back load combining in IR someday...)

The backend is also better equipped to deal with these patterns now using hooks like TLI.getShiftAmountThreshold().

The only remaining potential controversy is that the -reassociate pass tends to reverse this kind of pattern (to help GVN?). But since -reassociate doesn't do anything with these specific patterns, there is no conflict currently.

Finally, there's a new pass proposal at D67383 for general tree-height-reduction reassociation, and it could use a cost model to decide how to optimally rearrange these kinds of ops for a target. That patch appears to be stalled.

Diff Detail

Event Timeline

spatel created this revision.Nov 5 2019, 6:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 5 2019, 6:14 AM
lebedev.ri added inline comments.Nov 5 2019, 2:13 PM

Do you want to assert that I (and thus the inner 'shift') is actually a shift?

spatel updated this revision to Diff 228059.Nov 6 2019, 7:11 AM
spatel marked 2 inline comments as done.

Patch updated:
Assert that the input argument is a shift; if that's not true, we're being called from some unexpected place.


Sure - more asserts are good.

lebedev.ri accepted this revision.Nov 6 2019, 9:35 AM

Okay, thanks, LG.


This innermost shift only has to be one-use iff Y is not constant.

This revision is now accepted and ready to land.Nov 6 2019, 9:35 AM
spatel marked an inline comment as done.Nov 6 2019, 10:01 AM
spatel added inline comments.

Good point - I'll make it a TODO for this patch, and we can follow-up with an enhancement.

This revision was automatically updated to reflect the committed changes.