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

[andrew.zhogin]

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

---

[andrew.zhogin]

Updated to the current repository state.

[andrew.zhogin]

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

[delena]

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]

In D12833#798373, @delena wrote:

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.

[andrew.zhogin]

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

[RKSimon]

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

[andrew.zhogin]

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

[andrew.zhogin]

In D12833#799348, @RKSimon wrote:

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

Done.

[RKSimon]

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.

[andrew.zhogin]

Conditions optimized according the review comments.

[RKSimon]

LGTM

[RKSimon]

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

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitRotate(SDNode *N) {
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
 
   // fold (rot* x, (trunc (and y, c))) -> (rot* x, (and (trunc y), (trunc c))).
   if (N1.getOpcode() == ISD::TRUNCATE &&
       N1.getOperand(0).getOpcode() == ISD::AND) {
     if (SDValue NewOp1 = distributeTruncateThroughAnd(N1.getNode()))
       return DAG.getNode(N->getOpcode(), dl, VT, N0, NewOp1);
   }
+
+  unsigned NextOp = N0.getOpcode();
+  // fold (rot* (rot* x, c2), c1) -> (rot* x, c1 +- c2 % bitsize)
+  if (NextOp == ISD::ROTL || NextOp == ISD::ROTR)
+    if (SDNode *C1 = DAG.isConstantIntBuildVectorOrConstantInt(N1))
+      if (SDNode *C2 =
+          DAG.isConstantIntBuildVectorOrConstantInt(N0.getOperand(1))) {
+        bool SameSide = (N->getOpcode() == NextOp);
+        unsigned CombineOp = SameSide ? ISD::ADD : ISD::SUB;
+        if (SDValue CombinedShift =
+            DAG.FoldConstantArithmetic(CombineOp, dl, VT, C1, C2)) {
+          unsigned Bitsize = VT.getScalarSizeInBits();
+          SDValue BitsizeC = DAG.getConstant(Bitsize, dl, VT);
+          SDValue CombinedShiftNorm = DAG.FoldConstantArithmetic(
+            ISD::SREM, dl, VT, CombinedShift.getNode(), BitsizeC.getNode());
+          return DAG.getNode(
+            N->getOpcode(), dl, VT, N0->getOperand(0), CombinedShiftNorm);
+        }
+      }
   return SDValue();
 }
 
 SDValue DAGCombiner::visitSHL(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   unsigned OpSizeInBits = VT.getScalarSizeInBits();

test/CodeGen/ARM/ror.ll

 ; RUN: llc -mtriple=arm-eabi -mattr=+v6 %s -o - | FileCheck %s
 
 ; rotr (rotr x, 4), 6 -> rotr x, 10 -> ror r0, r0, #10
 define i32 @test1(i32 %x) nounwind readnone {
 ; CHECK-LABEL: test1:
-; CHECK: ror  r0, r0, #4
-; CHECK: ror  r0, r0, #6
+; CHECK: ror  r0, r0, #10
 ; CHECK: bx  lr
 entry:
   %high_part.i = shl i32 %x, 28
   %low_part.i = lshr i32 %x, 4
   %result.i = or i32 %high_part.i, %low_part.i
   %high_part.i.1 = shl i32 %result.i, 26
   %low_part.i.2 = lshr i32 %result.i, 6
   %result.i.3 = or i32 %low_part.i.2, %high_part.i.1
   ret i32 %result.i.3
 }
 
 ; the same vector test
 define <2 x i32> @test2(<2 x i32> %x) nounwind readnone {
 ; CHECK-LABEL: test2:
-; CHECK: ror  r0, r0, #4
-; CHECK: ror  r1, r1, #4
-; CHECK: ror  r0, r0, #6
-; CHECK: ror  r1, r1, #6
+; CHECK: ror  r0, r0, #10
+; CHECK: ror  r1, r1, #10
 ; CHECK: bx  lr
 entry:
   %high_part.i = shl <2 x i32> %x, <i32 28, i32 28>
   %low_part.i = lshr <2 x i32> %x, <i32 4, i32 4>
   %result.i = or <2 x i32> %high_part.i, %low_part.i
   %high_part.i.1 = shl <2 x i32> %result.i, <i32 26, i32 26>
   %low_part.i.2 = lshr <2 x i32> %result.i, <i32 6, i32 6>
   %result.i.3 = or <2 x i32> %low_part.i.2, %high_part.i.1
   ret <2 x i32> %result.i.3
 }
 

test/CodeGen/X86/combine-rotates.ll

; AVX512-NEXT:    retq
   %5 = shl <4 x i32> %3, <i32 20, i32 19, i32 18, i32 17>
   %6 = or <4 x i32> %4, %5
   ret <4 x i32> %6
 }
 
 define <4 x i32> @combine_vec_rot_rot_splat(<4 x i32> %x) {
 ; XOP-LABEL: combine_vec_rot_rot_splat:
 ; XOP:       # BB#0:
-; XOP-NEXT:    vprotd $29, %xmm0, %xmm0
-; XOP-NEXT:    vprotd $10, %xmm0, %xmm0
+; XOP-NEXT:    vprotd $7, %xmm0, %xmm0
 ; XOP-NEXT:    retq
 ;
 ; AVX512-LABEL: combine_vec_rot_rot_splat:
 ; AVX512:       # BB#0:
 ; AVX512-NEXT:    vpsrld $3, %xmm0, %xmm1
 ; AVX512-NEXT:    vpslld $29, %xmm0, %xmm0
 ; AVX512-NEXT:    vpor %xmm0, %xmm1, %xmm0
 ; AVX512-NEXT:    vpsrld $22, %xmm0, %xmm1
 ; AVX512-NEXT:    vpslld $10, %xmm0, %xmm0
 ; AVX512-NEXT:    vpor %xmm0, %xmm1, %xmm0
 ; AVX512-NEXT:    retq
   %1 = lshr <4 x i32> %x, <i32 3, i32 3, i32 3, i32 3>
   %2 = shl <4 x i32> %x, <i32 29, i32 29, i32 29, i32 29>
   %3 = or <4 x i32> %1, %2
   %4 = lshr <4 x i32> %3, <i32 22, i32 22, i32 22, i32 22>
   %5 = shl <4 x i32> %3, <i32 10, i32 10, i32 10, i32 10>
   %6 = or <4 x i32> %4, %5
   ret <4 x i32> %6
 }
 
 define <4 x i32> @combine_vec_rot_rot_splat_zero(<4 x i32> %x) {
 ; XOP-LABEL: combine_vec_rot_rot_splat_zero:
 ; XOP:       # BB#0:
-; XOP-NEXT:    vprotd $31, %xmm0, %xmm0
-; XOP-NEXT:    vprotd $1, %xmm0, %xmm0
+; XOP-NEXT:    vprotd $0, %xmm0, %xmm0
 ; XOP-NEXT:    retq
 ;
 ; AVX512-LABEL: combine_vec_rot_rot_splat_zero:
 ; AVX512:       # BB#0:
 ; AVX512-NEXT:    vpsrld $1, %xmm0, %xmm1
 ; AVX512-NEXT:    vpslld $31, %xmm0, %xmm0
 ; AVX512-NEXT:    vpor %xmm0, %xmm1, %xmm0
 ; AVX512-NEXT:    vpsrld $31, %xmm0, %xmm1