[SelectionDAG] try harder to convert funnel shift to rotate

[spatel]

Summary

Similar to rL337966 - if the DAGCombiner's rotate matching was working as expected,
I don't think we'd see any test diffs here.

AArch only goes right, and PPC only goes left. x86 has both, so no diffs there. If there are test suggestions for other targets, please let me know.

[spatel]

There's a subtle bug in the existing code. The conversion we're using to avoid the select for rotates (1st 2 args are the same, X == Y) only works for pow-of-2 bitwidths:
https://rise4fun.com/Alive/US1r
I can't tell yet if that bug was visible in the codegen for the existing non-pow-of-2 tests, and we just overlooked it.

I'll fix that and update this after.

[spatel]

Patch updated:
Rebased after the bug fix and improvements from rL338592.
The code change is smaller and there are less test diffs.

[spatel]

test/CodeGen/PowerPC/funnel-shift-rot.ll

159–160

This is weird (independent of this patch) - rldcl 3,3,4,0 is rotld 3,3,4.

We used the extended mnemonic for rotate before, but now we failed to print that?

[kparzysz]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5700

Can this be legal-or-custom (and same at line 5707)?

[RKSimon]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5700

see the TODO above:

// TODO: This should also be done if the operation is custom, but we have
// to make sure targets are handling the modulo shift amount as expected.

[spatel]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5700

To add to Simon’s answer, there are known issues with x86 vector lowering discussed in:
https://bugs.llvm.org/show_bug.cgi?id=38243

...so there are many steps left towards standardizing on these intrinsics, but this small one is hopefully ok as-is.

[spatel]

Ping.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::fshr: {
     SDValue X = getValue(I.getArgOperand(0));
     SDValue Y = getValue(I.getArgOperand(1));
     SDValue Z = getValue(I.getArgOperand(2));
     EVT VT = X.getValueType();
 
     // When X == Y, this is rotate. Create the node directly if legal.
     // TODO: This should also be done if the operation is custom, but we have
     // to make sure targets are handling the modulo shift amount as expected.
-    // TODO: If the rotate direction (left or right) corresponding to the shift
-    // is not available, adjust the shift value and invert the direction.
+    if (X == Y) {
       auto RotateOpcode = IsFSHL ? ISD::ROTL : ISD::ROTR;
-    if (X == Y && TLI.isOperationLegal(RotateOpcode, VT)) {
+      if (TLI.isOperationLegal(RotateOpcode, VT)) {
         setValue(&I, DAG.getNode(RotateOpcode, sdl, VT, X, Z));
         return nullptr;
       }
+      // Try the opposite direction.
+      RotateOpcode = IsFSHL ? ISD::ROTR : ISD::ROTL;
+      if (TLI.isOperationLegal(RotateOpcode, VT) &&
+          isPowerOf2_32(VT.getScalarSizeInBits())) {
+        // Negate the shift amount because it is safe to ignore the high bits.
+        SDValue Zero = DAG.getConstant(0, sdl, Z.getValueType());
+        SDValue NegShAmt = DAG.getNode(ISD::SUB, sdl, VT, Zero, Z);
+        setValue(&I, DAG.getNode(RotateOpcode, sdl, VT, X, NegShAmt));
+        return nullptr;
+      }
+    }
 
     // Get the shift amount and inverse shift amount, modulo the bit-width.
     SDValue BitWidthC = DAG.getConstant(VT.getScalarSizeInBits(), sdl, VT);
     SDValue ShAmt = DAG.getNode(ISD::UREM, sdl, VT, Z, BitWidthC);
     SDValue NegZ = DAG.getNode(ISD::SUB, sdl, VT, BitWidthC, Z);
     SDValue InvShAmt = DAG.getNode(ISD::UREM, sdl, VT, NegZ, BitWidthC);
 
     // fshl: (X << (Z % BW)) | (Y >> ((BW - Z) % BW))

test/CodeGen/AArch64/funnel-shift-rot.ll

 ; CHECK-NEXT:    ret
   %f = call i16 @llvm.fshl.i16(i16 %x, i16 %x, i16 %z)
   ret i16 %f
 }
 
 define i32 @rotl_i32(i32 %x, i32 %z) {
 ; CHECK-LABEL: rotl_i32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    orr w8, wzr, #0x20
-; CHECK-NEXT:    sub w8, w8, w1
+; CHECK-NEXT:    neg w8, w1
 ; CHECK-NEXT:    ror w0, w0, w8
 ; CHECK-NEXT:    ret
   %f = call i32 @llvm.fshl.i32(i32 %x, i32 %x, i32 %z)
   ret i32 %f
 }
 
 define i64 @rotl_i64(i64 %x, i64 %z) {
 ; CHECK-LABEL: rotl_i64:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    orr w9, wzr, #0x40
-; CHECK-NEXT:    sub w9, w9, w1
-; CHECK-NEXT:    lsl x8, x0, x1
-; CHECK-NEXT:    lsr x9, x0, x9
-; CHECK-NEXT:    orr x0, x8, x9
+; CHECK-NEXT:    neg x8, x1
+; CHECK-NEXT:    ror x0, x0, x8
 ; CHECK-NEXT:    ret
   %f = call i64 @llvm.fshl.i64(i64 %x, i64 %x, i64 %z)
   ret i64 %f
 }
 
 ; Vector rotate.
 
 define <4 x i32> @rotl_v4i32(<4 x i32> %x, <4 x i32> %z) {

test/CodeGen/PowerPC/funnel-shift-rot.ll

 ; CHECK-NEXT:    blr
   %f = call i16 @llvm.fshr.i16(i16 %x, i16 %x, i16 %z)
   ret i16 %f
 }
 
 define i32 @rotr_i32(i32 %x, i32 %z) {
 ; CHECK-LABEL: rotr_i32:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    subfic 4, 4, 32
-; CHECK-NEXT:    clrlwi 4, 4, 27
+; CHECK-NEXT:    neg 4, 4
 ; CHECK-NEXT:    rlwnm 3, 3, 4, 0, 31
 ; CHECK-NEXT:    blr
   %f = call i32 @llvm.fshr.i32(i32 %x, i32 %x, i32 %z)
   ret i32 %f
 }
 
 define i64 @rotr_i64(i64 %x, i64 %z) {
 ; CHECK-LABEL: rotr_i64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    subfic 4, 4, 64
-; CHECK-NEXT:    rlwinm 4, 4, 0, 26, 31
-; CHECK-NEXT:    rotld 3, 3, 4
+; CHECK-NEXT:    neg 4, 4
+; CHECK-NEXT:    rldcl 3, 3, 4, 0
 ; CHECK-NEXT:    blr
   %f = call i64 @llvm.fshr.i64(i64 %x, i64 %x, i64 %z)
   ret i64 %f
 }
 
 ; Vector rotate.
 
 define <4 x i32> @rotr_v4i32(<4 x i32> %x, <4 x i32> %z) {