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

5289

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

5280

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

5284

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

5285

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

5294

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

test/CodeGen/X86/combine-rotates.ll

62 ↗

(On Diff #105248)

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

if (isConstantOrConstantVector(N01, /* NoOpaques */ true)) {
       return DAG.getNode(ISD::AND, DL, TruncVT, Trunc00, Trunc01);
     }
   }
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitRotate(SDNode *N) {
+  SDLoc dl(N);
+  SDValue N0 = N->getOperand(0);
+  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 (N->getOperand(1).getOpcode() == ISD::TRUNCATE &&
-      N->getOperand(1).getOperand(0).getOpcode() == ISD::AND) {
-    if (SDValue NewOp1 =
-            distributeTruncateThroughAnd(N->getOperand(1).getNode()))
-      return DAG.getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
-                         N->getOperand(0), NewOp1);
+  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 (ConstantSDNode *C1 = getAsNonOpaqueConstant(N1))
+    if (NextOp == ISD::ROTL || NextOp == ISD::ROTR)
+      if (ConstantSDNode *C2 = getAsNonOpaqueConstant(N0.getOperand(1))) {
+        bool MainIsRotr = N->getOpcode() == ISD::ROTR;
+        bool NextIsRotr = NextOp == ISD::ROTR;
+        bool SameSide = MainIsRotr == NextIsRotr;
+
+        unsigned Bitsize = VT.getScalarSizeInBits();
+        unsigned CombineOp = SameSide ? ISD::ADD : ISD::SUB;
+        SDValue CombinedShift =
+          DAG.FoldConstantArithmetic(CombineOp, dl, VT, C1, C2);
+        ConstantSDNode *CombinedShiftC = getAsNonOpaqueConstant(CombinedShift);
+        ConstantSDNode *BitsizeC =
+          getAsNonOpaqueConstant(DAG.getConstant(Bitsize, dl, VT));
+        if (CombinedShiftC && BitsizeC) {
+          SDValue CombinedShiftNorm = DAG.FoldConstantArithmetic(
+            ISD::SREM, dl, VT, CombinedShiftC, BitsizeC);
+          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, #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
+}
+