This is an archive of the discontinued LLVM Phabricator instance.

[SDAG][X86] Expand pow2 mulo using shifts
ClosedPublic

Authored by nikic on Mar 6 2019, 12:32 PM.

Details

Summary

Expand MULO with constant power of two operand to a shift. The overflow is checked with (x << shift) >> shift == x.

Diff Detail

Event Timeline

nikic created this revision.Mar 6 2019, 12:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2019, 12:32 PM
nikic marked 2 inline comments as done.Mar 6 2019, 12:35 PM
nikic added inline comments.
llvm/test/CodeGen/X86/mulo-pow2.ll
30

This being optimized is a nice side-effect, but we really should have a fold for mulo(x, 1).

109

This code is generated by the mulo(x, 2) -> addo(x, x) fold and seems worse than what we'd get from the shift expansion. Not sure what to do about it.

nikic planned changes to this revision.Mar 7 2019, 12:06 AM
nikic added inline comments.
llvm/test/CodeGen/X86/mulo-pow2.ll
133

This one isn't right ... INT_MIN can be multiplied by 0 and 1, not by 0 and -1.

nikic updated this revision to Diff 189934.Mar 8 2019, 2:09 PM

Ensure the optimization is not applied to signed min.

nikic updated this revision to Diff 189987.Mar 9 2019, 5:58 AM

Add changes to an ARM test.

nikic marked an inline comment as done.Mar 9 2019, 6:39 AM
nikic added inline comments.
llvm/test/CodeGen/ARM/umulo-32.ll
41 ↗(On Diff #189987)

We're doing a select of setcc here, both get expanded and the setcc is converted into this construction.

efriedma added inline comments.
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5529

(!isSigned || C.isNonNegative()) is specifically supposed to handle llvm.smul.with.overflow.i32(%x, INT_MIN)? Can't you just convert that to llvm.umul.with.overflow.i32(%x, INT_MIN) and lower it using an unsigned shift?

nikic updated this revision to Diff 190141.Mar 11 2019, 12:58 PM

Handle smulo with signed_min like umulo via logical shift.

nikic marked 2 inline comments as done.Mar 11 2019, 12:59 PM
nikic added inline comments.
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5529

Yes, you're right. I've implemented this now.

This revision is now accepted and ready to land.Mar 11 2019, 5:22 PM
This revision was automatically updated to reflect the committed changes.
nikic marked an inline comment as done.