[SelectionDAG] Handle non-power-of-2 bitwidths in expandROT

[RKSimon]

llvm/test/CodeGen/WebAssembly/fshl.ll

5

move the triple into the run command?

7

Please can you add a comment referencing the ossfuzz url?

[foad]

Add a comment.

[foad]

llvm/test/CodeGen/WebAssembly/fshl.ll

5

Could do but why? That is definitely not the prevailing style in test/CodeGen/WebAssembly/.

[spatel]

Do we guarantee that the rotate amount is not undef? (Can we assert that?)
The expansion may fail if the rotate amount is 'undef':
https://alive2.llvm.org/ce/z/tqjuC7

llvm/test/CodeGen/WebAssembly/fshl.ll

5

This should be fine. Specifying the target in the IR is the default.
Over in x86, we tend to prefer to put it on the RUN line because we have many tests that vary the subtarget slightly...because there are so many HW variations to think about.

[spatel]

Can we pre-commit the test before this patch with a FIXME note? This is currently miscompiling?

[nikic]

In D86449#2236491, @spatel wrote:

Do we guarantee that the rotate amount is not undef? (Can we assert that?)
The expansion may fail if the rotate amount is 'undef':
https://alive2.llvm.org/ce/z/tqjuC7

Undef is a legal rotate amount (because we spec rotate to be modulo the bitwidth, unlike normal shifts, where it is poison). However, I don't think it makes sense to consider undef-related issues at the SDAG layer at this point in time. They are much less likely to cause practical miscompiles here, and it's much harder to be undef-correct in SDAG (because expansion and legalization will often introduce multiple uses of the values, with the issues that may entail, as in this case). Being pedantic about this would need a lot of FREEZE.

[spatel]

In D86449#2237244, @nikic wrote:

In D86449#2236491, @spatel wrote:

Do we guarantee that the rotate amount is not undef? (Can we assert that?)
The expansion may fail if the rotate amount is 'undef':
https://alive2.llvm.org/ce/z/tqjuC7

Undef is a legal rotate amount (because we spec rotate to be modulo the bitwidth, unlike normal shifts, where it is poison). However, I don't think it makes sense to consider undef-related issues at the SDAG layer at this point in time. They are much less likely to cause practical miscompiles here, and it's much harder to be undef-correct in SDAG (because expansion and legalization will often introduce multiple uses of the values, with the issues that may entail, as in this case). Being pedantic about this would need a lot of FREEZE.

Yes, I agree that we don't want to take undef in codegen too seriously. We may want to add that fold for safety though because it seems to survive on most targets here.

And I see now that we are currently crashing on this example (on all targets?), so we need to get this fixed ASAP.
LGTM.

[RKSimon]

llvm/test/CodeGen/WebAssembly/fshl.ll

5

Yeah - don't worry, its just I'm so used to it I think it looks tidier these days.... </OCD>

[spatel]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

6287

This can't be right - both shifts are HsOpc. We need another test with a variable shift amount to make sure this is correct?

[foad]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

6287

It's correct. We want to shift by 1..32, so we do a shift by 1 and then a shift by 0..31.

[spatel]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

6287

Oops, disregard. Too early in the AM. :)

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

bool TargetLowering::expandROT(SDNode *Node, SDValue &Result,
   bool IsLeft = Node->getOpcode() == ISD::ROTL;
   SDValue Op0 = Node->getOperand(0);
   SDValue Op1 = Node->getOperand(1);
   SDLoc DL(SDValue(Node, 0));
 
   EVT ShVT = Op1.getValueType();
   SDValue Zero = DAG.getConstant(0, DL, ShVT);
 
-  assert(isPowerOf2_32(EltSizeInBits) && EltSizeInBits > 1 &&
-         "Expecting the type bitwidth to be a power of 2");
-
   // If a rotate in the other direction is supported, use it.
   unsigned RevRot = IsLeft ? ISD::ROTR : ISD::ROTL;
-  if (isOperationLegalOrCustom(RevRot, VT)) {
+  if (isOperationLegalOrCustom(RevRot, VT) && isPowerOf2_32(EltSizeInBits)) {
     SDValue Sub = DAG.getNode(ISD::SUB, DL, ShVT, Zero, Op1);
     Result = DAG.getNode(RevRot, DL, VT, Op0, Sub);
     return true;
   }
 
   if (VT.isVector() && (!isOperationLegalOrCustom(ISD::SHL, VT) ||
                         !isOperationLegalOrCustom(ISD::SRL, VT) ||
                         !isOperationLegalOrCustom(ISD::SUB, VT) ||
                         !isOperationLegalOrCustomOrPromote(ISD::OR, VT) ||
                         !isOperationLegalOrCustomOrPromote(ISD::AND, VT)))
     return false;
 
-  // Otherwise,
-  //   (rotl x, c) -> (or (shl x, (and c, w-1)), (srl x, (and -c, w-1)))
-  //   (rotr x, c) -> (or (srl x, (and c, w-1)), (shl x, (and -c, w-1)))
-  //
   unsigned ShOpc = IsLeft ? ISD::SHL : ISD::SRL;
   unsigned HsOpc = IsLeft ? ISD::SRL : ISD::SHL;
   SDValue BitWidthMinusOneC = DAG.getConstant(EltSizeInBits - 1, DL, ShVT);
+  SDValue ShVal;
+  SDValue HsVal;
+  if (isPowerOf2_32(EltSizeInBits)) {
+    // (rotl x, c) -> x << (c & (w - 1)) | x >> (-c & (w - 1))
+    // (rotr x, c) -> x >> (c & (w - 1)) | x << (-c & (w - 1))
     SDValue NegOp1 = DAG.getNode(ISD::SUB, DL, ShVT, Zero, Op1);
-  SDValue And0 = DAG.getNode(ISD::AND, DL, ShVT, Op1, BitWidthMinusOneC);
-  SDValue And1 = DAG.getNode(ISD::AND, DL, ShVT, NegOp1, BitWidthMinusOneC);
-  Result = DAG.getNode(ISD::OR, DL, VT, DAG.getNode(ShOpc, DL, VT, Op0, And0),
-                       DAG.getNode(HsOpc, DL, VT, Op0, And1));
+    SDValue ShAmt = DAG.getNode(ISD::AND, DL, ShVT, Op1, BitWidthMinusOneC);
+    ShVal = DAG.getNode(ShOpc, DL, VT, Op0, ShAmt);
+    SDValue HsAmt = DAG.getNode(ISD::AND, DL, ShVT, NegOp1, BitWidthMinusOneC);
+    HsVal = DAG.getNode(HsOpc, DL, VT, Op0, HsAmt);
+  } else {
+    // (rotl x, c) -> x << (c % w) | x >> 1 >> (w - 1 - (c % w))
+    // (rotr x, c) -> x >> (c % w) | x << 1 << (w - 1 - (c % w))
+    SDValue BitWidthC = DAG.getConstant(EltSizeInBits, DL, ShVT);
+    SDValue ShAmt = DAG.getNode(ISD::UREM, DL, ShVT, Op1, BitWidthC);
+    ShVal = DAG.getNode(ShOpc, DL, VT, Op0, ShAmt);
+    SDValue HsAmt = DAG.getNode(ISD::SUB, DL, ShVT, BitWidthMinusOneC, ShAmt);
+    SDValue One = DAG.getConstant(1, DL, ShVT);
+    HsVal =
+        DAG.getNode(HsOpc, DL, VT, DAG.getNode(HsOpc, DL, VT, Op0, One), HsAmt);
+  }
+  Result = DAG.getNode(ISD::OR, DL, VT, ShVal, HsVal);
   return true;
 }
 
 bool TargetLowering::expandFP_TO_SINT(SDNode *Node, SDValue &Result,
                                       SelectionDAG &DAG) const {
   unsigned OpNo = Node->isStrictFPOpcode() ? 1 : 0;
   SDValue Src = Node->getOperand(OpNo);
   EVT SrcVT = Src.getValueType();

llvm/test/CodeGen/WebAssembly/fshl.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s | FileCheck %s
+
+target triple = "wasm32-unknown-unknown"
+
+; From https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=25150
+define i33 @fshr_multi_use(i33 %a) {
+; CHECK-LABEL: fshr_multi_use:
+; CHECK:         .functype fshr_multi_use (i64) -> (i64)
+; CHECK-NEXT:  # %bb.0:
+; CHECK-NEXT:    local.get 0
+; CHECK-NEXT:    i64.const 1
+; CHECK-NEXT:    i64.shr_u
+; CHECK-NEXT:    i64.const 31
+; CHECK-NEXT:    i64.and
+; CHECK-NEXT:    # fallthrough-return
+  %b = tail call i33 @llvm.fshr.i33(i33 %a, i33 %a, i33 1)
+  %e = and i33 %b, 31
+  ret i33 %e
+}
+
+declare i33 @llvm.fshr.i33(i33, i33, i33)