Page MenuHomePhabricator

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

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

Details

Summary

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:
rL370617

So we again have 9 possible patterns with a commuted IR variant of each pattern:
https://rise4fun.com/Alive/VlI
https://rise4fun.com/Alive/n1m
https://rise4fun.com/Alive/1Vn

Part of the motivation is to allow easier recognition and subsequent canonicalization of bswap patterns as discussed in PR43146:
https://bugs.llvm.org/show_bug.cgi?id=43146

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:
rL375025
(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
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
304–305

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.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
304–305

Sure - more asserts are good.

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

Okay, thanks, LG.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
321

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.
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
321

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.