[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

158 ↗

(On Diff #158572)

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

5714 ↗

(On Diff #158572)

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

[RKSimon]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5714 ↗

(On Diff #158572)

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

5714 ↗

(On Diff #158572)

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.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::fshr: {
     SDValue ShAmt = DAG.getNode(ISD::UREM, sdl, VT, Z, BitWidthC);
 
     // When X == Y, this is rotate. If the data type has a power-of-2 size, we
     // avoid the select that is necessary in the general case to filter out
     // the 0-shift possibility that leads to UB.
     if (X == Y && isPowerOf2_32(VT.getScalarSizeInBits())) {
       // 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.
       auto RotateOpcode = IsFSHL ? ISD::ROTL : ISD::ROTR;
       if (TLI.isOperationLegal(RotateOpcode, VT)) {
         setValue(&I, DAG.getNode(RotateOpcode, sdl, VT, X, Z));
         return nullptr;
       }
+
+      // Some targets only rotate one way. Try the opposite direction.
+      RotateOpcode = IsFSHL ? ISD::ROTR : ISD::ROTL;
+      if (TLI.isOperationLegal(RotateOpcode, VT)) {
+        // Negate the shift amount because it is safe to ignore the high bits.
+        SDValue NegShAmt = DAG.getNode(ISD::SUB, sdl, VT, Zero, Z);
+        setValue(&I, DAG.getNode(RotateOpcode, sdl, VT, X, NegShAmt));
+        return nullptr;
+      }
+
       // fshl (rotl): (X << (Z % BW)) | (X >> ((0 - Z) % BW))
       // fshr (rotr): (X << ((0 - Z) % BW)) | (X >> (Z % BW))
       SDValue NegZ = DAG.getNode(ISD::SUB, sdl, VT, Zero, Z);
       SDValue NShAmt = DAG.getNode(ISD::UREM, sdl, VT, NegZ, BitWidthC);
       SDValue ShX = DAG.getNode(ISD::SHL, sdl, VT, X, IsFSHL ? ShAmt : NShAmt);
       SDValue ShY = DAG.getNode(ISD::SRL, sdl, VT, X, IsFSHL ? NShAmt : ShAmt);
       setValue(&I, DAG.getNode(ISD::OR, sdl, VT, ShX, ShY));
       return nullptr;

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

 ; 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:    neg 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) {

llvm/trunk/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:    neg 4, 4
-; CHECK-NEXT:    clrlwi 4, 4, 27
 ; 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:    neg 4, 4
-; CHECK-NEXT:    rlwinm 4, 4, 0, 26, 31
-; CHECK-NEXT:    rotld 3, 3, 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) {