[DAGCombine][ARM] Combine pattern for REV16

[SjoerdMeijer]

Summary

This adds another pattern matcher to the combiner to generate the REV16 instruction for a case that we were not handling.

[RKSimon]

llvm/test/CodeGen/Thumb2/thumb2-rev16.ll

2

Might be best if you regenerate+commit this file against trunk and then rebase the patch so it shows the full codegen diff.

[SjoerdMeijer]

Ah yes, thanks for the tip.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5657

This looks like it only works for MVT::i32 cases, but there doesn't seem to be any VT check?

5663

Use isConstOrConstSplat instead of dyn_cast<ConstantSDNode> ?

[SjoerdMeijer]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5704

This looks like it only works for MVT::i32 cases, but there doesn't seem to be any VT check?

That is checked here, but I will add an assert to MatchBSwapHWordOrAndAnd

[SjoerdMeijer]

Thanks for looking. Comments addressed

[SjoerdMeijer]

friendly ping

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5655

Use current formatting rules, so lowerCamel: "matchBSwap..."
(can fix the related function names as a preliminary step)

5658

Also assert that N->getOpcode() == ISD::OR ?

5667–5669

This is too specific - what if the operands of the "or" are commuted?

This patch should have a test for that possibility:

define i32 @bswap_ror_commuted(i32 %a) {
    %l8 = shl i32 %a, 8
    %r8 = lshr i32 %a, 8
    %mask_l8 = and i32 %l8, 4278255360
    %mask_r8 = and i32 %r8, 16711935
    %tmp = or i32 %mask_r8, %mask_l8
    ret i32 %tmp
}

5674–5675

These could use more descriptive names: ShiftAmt{1/2}.
These are using isConstOrConstSplat(), but the 'and' mask operands are not. Change the above code to match this?

[SjoerdMeijer]

Thanks for looking! Comments addressed. I have also added more test for the cases that shouldn't trigger.

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5668–5671

This check works, but it makes me nervous because I think it requires demanded bits to alter the code for correctness.
Take this example where the masks are paired with the wrong shift op (and please add a test like this to the patch):

define i32 @not_rev16(i32 %a) {
    %l8 = shl i32 %a, 8
    %r8 = lshr i32 %a, 8
    %mask_r8 = and i32 %r8, 4278255360
    %mask_l8 = and i32 %l8, 16711935
    %tmp = or i32 %mask_r8, %mask_l8
    ret i32 %tmp
}

To be safe, I think we should enforce that the masks and shifts are paired correctly.
So we could do something like:

// Canonicalize mask ops to ensure that shift-left operand is on the left.
if (Mask2 == 0xff00ff00) {
  std::swap(N0, N1);
  std::swap(Mask1, Mask2)
}

or maybe better - go back to the earlier rev of this patch and call this function with the operands reversed:

if (SDValue BSwap = matchBSwapHWordOrAndAnd(TLI, DAG, N, N0, N1, VT,
                                            getShiftAmountTy(VT)))
  return BSwap;
// Try again with commuted operands.
if (SDValue BSwap = matchBSwapHWordOrAndAnd(TLI, DAG, N, N1, N0, VT,
                                            getShiftAmountTy(VT)))
  return BSwap;

[SjoerdMeijer]

Many thanks again for the feedback! Really liked that suggestion: so now calling the same function twice but with the operands swapped to check the commuted case. Have also added the suggested test case.

[spatel]

In D74032#1876021, @SjoerdMeijer wrote:

Many thanks again for the feedback! Really liked that suggestion: so now calling the same function twice but with the operands swapped to check the commuted case. Have also added the suggested test case.

There's 1 more concern for this transform - do we need to limit it when the intermediate values have other uses? This will be interesting because the answer may be different for different targets. Ie, for ARM/Thumb/AArch64, we're able to reduce the whole sequence to a single rev16, so it's always a good transform. But for x86, we're going to need a bswap and ror.

So we need to:

1. Add a test like this:

define i32 @extra_maskop_uses2(i32 %a) {
    %l8 = shl i32 %a, 8
    %r8 = lshr i32 %a, 8
    %mask_l8 = and i32 %l8, 4278255360
    %mask_r8 = and i32 %r8, 16711935
    %or = or i32 %mask_r8, %mask_l8
    %mul = mul i32 %mask_r8, %mask_l8   ; use the mask ops for some other reason 
    %r = mul i32 %mul, %or              ; and use that result for some other reason
    ret i32 %r
}

2. Copy that test (maybe the whole test file) over to llvm/tests/CodeGen/X86 and generate CHECK lines with utils/update_llc_test_checks.py.
3. Possibly add some 'hasOneUse()' logic to the code to avoid regressions.

Please push the test changes to trunk before updating in this review (no need for pre-commit review unless you have questions/concerns).

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5664–5665

Nit: the input variables are "0" and "1", but this shifts the indexing to "1" and "2". It would be better to make this consistent (same for the "Shift" variables below this).

Most of the code in DAGCombiner uses "0"-based indexing.

[SjoerdMeijer]

Thanks, I will first add the tests (will indeed add the whole test file). Will do that on Monday, and after that, will return and revisit this patch

[SjoerdMeijer]

New x86 test committed in: https://reviews.llvm.org/rGa02056c96070

[SjoerdMeijer]

Fixed the off-by-1 error in the variable naming, and added hasOneUse checks for the AND instructions.

[spatel]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5664

This check seems over-protective. If only one of the 'and' ops has extra uses, the transform is probably still worth doing. It's ok to add a TODO comment here if you want and make that a small follow-up patch after adding more tests to exercise those cases.

llvm/test/CodeGen/X86/rev16.ll

227–228

Remove TODO comment - this is working as expected.
It also works with aarch64. The missed transform for arm/thumb seems to be because there's an early target-specific combine that creates "bfi", so we miss the generic pattern matching for bswap because it only runs with !LegalOperations. I'm not sure if/why we need that restriction.

[SjoerdMeijer]

Thanks, this has been a good and useful introduction to DAGCombine for me :-)
Before committing, I will add a TODO saying that this hasOneUse is a bit over-protective for now (will follow up later), and will remove the TODO from the test case.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (!C || C->getAPIntValue() != 16)
       return false;
     Parts[0] = Parts[1] = N.getOperand(0).getOperand(0).getNode();
     return true;
   }
 
   return false;
 }
 
+// Match this pattern:
+//   (or (and (shl (A, 8)), 0xff00ff00), (and (srl (A, 8)), 0x00ff00ff))
+// And rewrite this to:
+//   (rotr (bswap A), 16)
+static SDValue matchBSwapHWordOrAndAnd(const TargetLowering &TLI,
+                                       SelectionDAG &DAG, SDNode *N, SDValue N0,
+                                       SDValue N1, EVT VT, EVT ShiftAmountTy) {
+  assert(N->getOpcode() == ISD::OR && VT == MVT::i32 &&
+         "MatchBSwapHWordOrAndAnd: expecting i32");
+  if (!TLI.isOperationLegalOrCustom(ISD::ROTR, VT))
+    return SDValue();
+  if (N0.getOpcode() != ISD::AND || N1.getOpcode() != ISD::AND)
+    return SDValue();
+  // TODO: this is too restrictive; lifting this restriction requires more tests
+  if (!N0->hasOneUse() || !N1->hasOneUse())
+    return SDValue();
+  ConstantSDNode *Mask0 = isConstOrConstSplat(N0.getOperand(1));
+  ConstantSDNode *Mask1 = isConstOrConstSplat(N1.getOperand(1));
+  if (!Mask0 || !Mask1)
+    return SDValue();
+  if (Mask0->getAPIntValue() != 0xff00ff00 ||
+      Mask1->getAPIntValue() != 0x00ff00ff)
+    return SDValue();
+  SDValue Shift0 = N0.getOperand(0);
+  SDValue Shift1 = N1.getOperand(0);
+  if (Shift0.getOpcode() != ISD::SHL || Shift1.getOpcode() != ISD::SRL)
+    return SDValue();
+  ConstantSDNode *ShiftAmt0 = isConstOrConstSplat(Shift0.getOperand(1));
+  ConstantSDNode *ShiftAmt1 = isConstOrConstSplat(Shift1.getOperand(1));
+  if (!ShiftAmt0 || !ShiftAmt1)
+    return SDValue();
+  if (ShiftAmt0->getAPIntValue() != 8 || ShiftAmt1->getAPIntValue() != 8)
+    return SDValue();
+  if (Shift0.getOperand(0) != Shift1.getOperand(0))
+    return SDValue();
+
+  SDLoc DL(N);
+  SDValue BSwap = DAG.getNode(ISD::BSWAP, DL, VT, Shift0.getOperand(0));
+  SDValue ShAmt = DAG.getConstant(16, DL, ShiftAmountTy);
+  return DAG.getNode(ISD::ROTR, DL, VT, BSwap, ShAmt);
+}
+
 /// Match a 32-bit packed halfword bswap. That is
 /// ((x & 0x000000ff) << 8) |
 /// ((x & 0x0000ff00) >> 8) |
 /// ((x & 0x00ff0000) << 8) |
 /// ((x & 0xff000000) >> 8)
 /// => (rotl (bswap x), 16)
 SDValue DAGCombiner::MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1) {
   if (!LegalOperations)
     return SDValue();
 
   EVT VT = N->getValueType(0);
   if (VT != MVT::i32)
     return SDValue();
   if (!TLI.isOperationLegalOrCustom(ISD::BSWAP, VT))
     return SDValue();
 
+  if (SDValue BSwap = matchBSwapHWordOrAndAnd(TLI, DAG, N, N0, N1, VT,
+                                              getShiftAmountTy(VT)))
+  return BSwap;
+
+  // Try again with commuted operands.
+  if (SDValue BSwap = matchBSwapHWordOrAndAnd(TLI, DAG, N, N1, N0, VT,
+                                              getShiftAmountTy(VT)))
+  return BSwap;
+
+
   // Look for either
   // (or (bswaphpair), (bswaphpair))
   // (or (or (bswaphpair), (and)), (and))
   // (or (or (and), (bswaphpair)), (and))
   SDNode *Parts[4] = {};
 
   if (isBSwapHWordPair(N0, Parts)) {
     // (or (or (and), (and)), (or (and), (and)))

llvm/test/CodeGen/Thumb2/thumb2-rev16.ll

-; XFAIL: *
-; fixme rev16 pattern is not matching
-
-; RUN: llc < %s -mtriple=thumb-- -mcpu=arm1156t2-s -mattr=+thumb2 | grep "rev16\W*r[0-9]*,\W*r[0-9]*" | count 1
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=thumbv7m-none-eabi -o - |  FileCheck %s
 
 ; 0xff00ff00 = 4278255360
 ; 0x00ff00ff = 16711935
-define i32 @f1(i32 %a) {
+define i32 @rev16(i32 %a) {
+; CHECK-LABEL: rev16:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rev16 r0, r0
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 8
+    %r8 = lshr i32 %a, 8
+    %mask_l8 = and i32 %l8, 4278255360
+    %mask_r8 = and i32 %r8, 16711935
+    %tmp = or i32 %mask_l8, %mask_r8
+    ret i32 %tmp
+}
+
+define i32 @not_rev16(i32 %a) {
+; CHECK-LABEL: not_rev16:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #65280
+; CHECK-NEXT:    and.w r1, r1, r0, lsr #8
+; CHECK-NEXT:    and r0, r0, #65280
+; CHECK-NEXT:    orr.w r0, r1, r0, lsl #8
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 8
+    %r8 = lshr i32 %a, 8
+    %mask_r8 = and i32 %r8, 4278255360
+    %mask_l8 = and i32 %l8, 16711935
+    %tmp = or i32 %mask_r8, %mask_l8
+    ret i32 %tmp
+}
+
+define i32 @extra_maskop_uses2(i32 %a) {
+; CHECK-LABEL: extra_maskop_uses2:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #-16711936
+; CHECK-NEXT:    mov.w r2, #16711935
+; CHECK-NEXT:    and.w r1, r1, r0, lsl #8
+; CHECK-NEXT:    and.w r0, r2, r0, lsr #8
+; CHECK-NEXT:    adds r2, r0, r1
+; CHECK-NEXT:    muls r0, r1, r0
+; CHECK-NEXT:    muls r0, r2, r0
+; CHECK-NEXT:    bx lr
+  %l8 = shl i32 %a, 8
+  %r8 = lshr i32 %a, 8
+  %mask_l8 = and i32 %l8, 4278255360
+  %mask_r8 = and i32 %r8, 16711935
+  %or = or i32 %mask_r8, %mask_l8
+  %mul = mul i32 %mask_r8, %mask_l8   ; another use of the mask ops
+  %r = mul i32 %mul, %or              ; and use that result
+  ret i32 %r
+}
+
+
+define i32 @bswap_ror_commuted(i32 %a) {
+; CHECK-LABEL: bswap_ror_commuted:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rev16 r0, r0
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 8
+    %r8 = lshr i32 %a, 8
+    %mask_l8 = and i32 %l8, 4278255360
+    %mask_r8 = and i32 %r8, 16711935
+    %tmp = or i32 %mask_r8, %mask_l8
+    ret i32 %tmp
+}
+
+define i32 @different_shift_amount(i32 %a) {
+; CHECK-LABEL: different_shift_amount:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #16711935
+; CHECK-NEXT:    movw r2, #65024
+; CHECK-NEXT:    and.w r1, r1, r0, lsr #8
+; CHECK-NEXT:    movt r2, #65280
+; CHECK-NEXT:    and.w r0, r2, r0, lsl #9
+; CHECK-NEXT:    add r0, r1
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 9
+    %r8 = lshr i32 %a, 8
+    %mask_l8 = and i32 %l8, 4278255360
+    %mask_r8 = and i32 %r8, 16711935
+    %tmp = or i32 %mask_l8, %mask_r8
+    ret i32 %tmp
+}
+
+define i32 @different_constant(i32 %a) {
+; CHECK-LABEL: different_constant:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #16711935
+; CHECK-NEXT:    and.w r0, r1, r0, lsr #8
+; CHECK-NEXT:    bx lr
     %l8 = shl i32 %a, 8
     %r8 = lshr i32 %a, 8
+    %mask_l8 = and i32 %l8, 42
+    %mask_r8 = and i32 %r8, 16711935
+    %tmp = or i32 %mask_l8, %mask_r8
+    ret i32 %tmp
+}
+
+define i32 @different_op(i32 %a) {
+; CHECK-LABEL: different_op:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #16711935
+; CHECK-NEXT:    movw r2, #256
+; CHECK-NEXT:    and.w r1, r1, r0, lsr #8
+; CHECK-NEXT:    movt r2, #255
+; CHECK-NEXT:    add.w r0, r2, r0, lsl #8
+; CHECK-NEXT:    orrs r0, r1
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 8
+    %r8 = lshr i32 %a, 8
+    %mask_l8 = sub i32 %l8, 4278255360
+    %mask_r8 = and i32 %r8, 16711935
+    %tmp = or i32 %mask_l8, %mask_r8
+    ret i32 %tmp
+}
+
+define i32 @different_vars(i32 %a, i32 %b) {
+; CHECK-LABEL: different_vars:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r2, #16711935
+; CHECK-NEXT:    and.w r1, r2, r1, lsr #8
+; CHECK-NEXT:    mov.w r2, #-16711936
+; CHECK-NEXT:    and.w r0, r2, r0, lsl #8
+; CHECK-NEXT:    add r0, r1
+; CHECK-NEXT:    bx lr
+    %l8 = shl i32 %a, 8
+    %r8 = lshr i32 %b, 8
     %mask_l8 = and i32 %l8, 4278255360
     %mask_r8 = and i32 %r8, 16711935
     %tmp = or i32 %mask_l8, %mask_r8
     ret i32 %tmp
 }
 
+
+; FIXME: this rev16 pattern is not matching
+
 ; 0xff000000 = 4278190080
 ; 0x00ff0000 = 16711680
 ; 0x0000ff00 = 65280
 ; 0x000000ff = 255
 define i32 @f2(i32 %a) {
+; CHECK-LABEL: f2:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mov.w r1, #16711680
+; CHECK-NEXT:    and r2, r0, #16711680
+; CHECK-NEXT:    and.w r1, r1, r0, lsr #8
+; CHECK-NEXT:    orr.w r1, r1, r2, lsl #8
+; CHECK-NEXT:    ubfx r2, r0, #8, #8
+; CHECK-NEXT:    bfi r2, r0, #8, #8
+; CHECK-NEXT:    adds r0, r2, r1
+; CHECK-NEXT:    bx lr
     %l8 = shl i32 %a, 8
     %r8 = lshr i32 %a, 8
     %masklo_l8 = and i32 %l8, 65280
     %maskhi_l8 = and i32 %l8, 4278190080
     %masklo_r8 = and i32 %r8, 255
     %maskhi_r8 = and i32 %r8, 16711680
     %tmp1 = or i32 %masklo_l8, %masklo_r8
     %tmp2 = or i32 %maskhi_l8, %maskhi_r8
     %tmp = or i32 %tmp1, %tmp2
     ret i32 %tmp
 }

llvm/test/CodeGen/X86/rev16.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-- | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-- | FileCheck %s --check-prefix=X64
 
 ; 0xff00ff00 = 4278255360
 ; 0x00ff00ff = 16711935
 define i32 @rev16(i32 %a) {
 ; X86-LABEL: rev16:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    shll $8, %ecx
-; X86-NEXT:    shrl $8, %eax
-; X86-NEXT:    andl $-16711936, %ecx # imm = 0xFF00FF00
-; X86-NEXT:    andl $16711935, %eax # imm = 0xFF00FF
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    bswapl %eax
+; X86-NEXT:    rorl $16, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: rev16:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    shll $8, %eax
-; X64-NEXT:    shrl $8, %edi
-; X64-NEXT:    andl $-16711936, %eax # imm = 0xFF00FF00
-; X64-NEXT:    andl $16711935, %edi # imm = 0xFF00FF
-; X64-NEXT:    addl %edi, %eax
+; X64-NEXT:    bswapl %eax
+; X64-NEXT:    rorl $16, %eax
 ; X64-NEXT:    retq
   %l8 = shl i32 %a, 8
   %r8 = lshr i32 %a, 8
   %mask_l8 = and i32 %l8, 4278255360
   %mask_r8 = and i32 %r8, 16711935
   %tmp = or i32 %mask_l8, %mask_r8
   ret i32 %tmp
 }
; X64-NEXT:    retq
   %r = mul i32 %mul, %or              ; and use that result
   ret i32 %r
 }
 
 define i32 @bswap_ror_commuted(i32 %a) {
 ; X86-LABEL: bswap_ror_commuted:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    shll $8, %ecx
-; X86-NEXT:    shrl $8, %eax
-; X86-NEXT:    andl $-16711936, %ecx # imm = 0xFF00FF00
-; X86-NEXT:    andl $16711935, %eax # imm = 0xFF00FF
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    bswapl %eax
+; X86-NEXT:    rorl $16, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bswap_ror_commuted:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    shll $8, %eax
-; X64-NEXT:    shrl $8, %edi
-; X64-NEXT:    andl $-16711936, %eax # imm = 0xFF00FF00
-; X64-NEXT:    andl $16711935, %edi # imm = 0xFF00FF
-; X64-NEXT:    addl %edi, %eax
+; X64-NEXT:    bswapl %eax
+; X64-NEXT:    rorl $16, %eax
 ; X64-NEXT:    retq
   %l8 = shl i32 %a, 8
   %r8 = lshr i32 %a, 8
   %mask_l8 = and i32 %l8, 4278255360
   %mask_r8 = and i32 %r8, 16711935
   %tmp = or i32 %mask_r8, %mask_l8
   ret i32 %tmp
 }

 ; X64-NEXT:    retq
   %l8 = shl i32 %a, 8
   %r8 = lshr i32 %b, 8
   %mask_l8 = and i32 %l8, 4278255360
   %mask_r8 = and i32 %r8, 16711935
   %tmp = or i32 %mask_l8, %mask_r8
   ret i32 %tmp
 }
 
-; TODO: another pattern that we are currently not matching
-;
 ; 0xff000000 = 4278190080
 ; 0x00ff0000 = 16711680
 ; 0x0000ff00 = 65280
 ; 0x000000ff = 255
 define i32 @f2(i32 %a) {
 ; X86-LABEL: f2:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax