Page MenuHomePhabricator

DAGCombiner: fold (xor (shl 1, x), -1) -> (rotl -2, x)
ClosedPublic

Authored by majnemer on Mar 15 2015, 3:03 PM.

Details

Summary

Targets which provide a rotate make it possible to replace a sequence of
(XOR (SHL 1, x), -1) with (ROTL -2, x). This saves an instruction on
architectures like X86 and POWER(64).

Diff Detail

Repository
rL LLVM

Event Timeline

majnemer updated this revision to Diff 22007.Mar 15 2015, 3:03 PM
majnemer retitled this revision from to DAGCombiner: fold (xor (shl 1, x), -1) -> (rotl -2, x).
majnemer updated this object.
majnemer added reviewers: chandlerc, nadav, resistor.
majnemer added a subscriber: Unknown Object (MLST).
nadav edited edge metadata.Mar 15 2015, 10:56 PM

David, the code and test case look great. The transformation is not trivial. Do you mind adding a line of comment that explains why -2 is used? Maybe an example input like 00000001 -> 11111101. Also a comment about how rotate can only pull in 1s and how large x values are undefined.

majnemer updated this revision to Diff 22013.Mar 15 2015, 11:44 PM
majnemer edited edge metadata.
  • Add comments to explain the reasoning behind the transform.
silvas added a subscriber: silvas.Mar 16 2015, 6:00 PM

Maybe a z3 proof in the commit message would make people feel a bit more at home with this also?

Maybe a z3 proof in the commit message would make people feel a bit more at home with this also?

I sent this out for review mainly for the SelectionDAG specific bits. I think the arithmetic behind it is pretty clear.

FWIW, the logic seems straight forward to me too. LGTM.

This revision was automatically updated to reflect the committed changes.