This is an archive of the discontinued LLVM Phabricator instance.

Combines pair of rotr/rotl with constant shifts into one instruction with combined shift
ClosedPublic

Authored by andrew.zhogin on Sep 13 2015, 1:51 AM.

Details

Summary

DAGCombiner::visitRotate patch to optimize pair of ROTR/ROTL instructions into one with combined shift operand.
For two ROTR operations with shifts C1, C2; combined shift operand will be (C1 + C2) % bitsize.


rotr x, C1, y
rotr y, C2, z

Combines into:

rotr x, (C1 + C2) % bitsize, z

rotr x, C1, y
rotl y, C2, z

Combines into:

rotr x, (C1 - C2) % bitsize, z

rotl x, C1, y
rotl y, C2, z

Combines into:

rotl x, (C1 + C2) % bitsize, z

rotl x, C1, y
rotr y, C2, z

Combines into:

rotl x, (C1 - C2) % bitsize, z

Diff Detail

Event Timeline

andrew.zhogin retitled this revision from to Combines pair of rotr/rotl with constant shifts into one instruction with combined shift.
andrew.zhogin updated this object.
andrew.zhogin added a reviewer: majnemer.
andrew.zhogin added subscribers: llvm-commits, asl.
andrew.zhogin edited the summary of this revision. (Show Details)
andrew.zhogin added a reviewer: delena.

Updated to the current repository state.

Added test/CodeGen/ARM/ror.ll test for combining two ROTR operations.

delena edited edge metadata.Jul 3 2017, 9:22 AM

I suggest to submit the test first to show the current code. It will let us to see the optimization.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
5290

bool SameSide = (N->getOpcode() == NextOp);

RKSimon added a subscriber: RKSimon.

I suggest to submit the test first to show the current code. It will let us to see the optimization.

+1

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
5281–5300

You can do all of the above as a NFC pre-commit and simplify this patch

5285

Ideally you should replace these with isConstantOrConstantVector calls to support vector rotates.

Common variables promoted to function's begin and ror.ll test added as precommit NFC.
Implemented support for vector operations.
Review comments addressed.

andrew.zhogin marked 3 inline comments as done.Jul 4 2017, 1:10 PM
RKSimon edited edge metadata.Jul 5 2017, 2:41 AM

Please can you regenerate llvm\test\CodeGen\X86\combine-rotates.ll as well? I added this to test vector combines.

Updated test/CodeGen/X86/combine-rotates.ll.

Please can you regenerate llvm\test\CodeGen\X86\combine-rotates.ll as well? I added this to test vector combines.

Done.

A couple of minors but otherwise I think you're almost there.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
5286

Might be worth testing this first - isConstantIntBuildVectorOrConstantInt calls are more costly so we can reduce wasted cpu cycles.

5295

No need to test for BitsizeC - move the DAG.getConstant call inside "if (CombinedShift)"

test/CodeGen/X86/combine-rotates.ll
62

Looks like we need a followup patch to remove rotates by zero.

Conditions optimized according the review comments.

RKSimon accepted this revision.Jul 5 2017, 9:08 AM

LGTM

This revision is now accepted and ready to land.Jul 5 2017, 9:08 AM
This revision was automatically updated to reflect the committed changes.
andrew.zhogin marked 2 inline comments as done.

Thanks Andrew, I added (rot x, 0) -> x folding at rL307184