[DAGCombiner] Add bswap(logic_op(bswap(x), y)) optimization

[austin880625]

Summary

This is the implementation of D149782

The patch implements a helper function that matches and fold the following cases in the DAGCombiner:

1. bswap(logic_op(x, bswap(y))) -> logic_op(bswap(x), y)
2. bswap(logic_op(bswap(x), y)) -> logic_op(x, bswap(y))
3. bswap(logic_op(bswap(x), bswap(y))) -> logic_op(x, y) in multiuse case, which still reduces the number of instructions.

The helper function accepts SDValue with BSWAP and BITREVERSE opcode. This patch folds the BSWAP cases and remain the BITREVERSE optimization in the future

[austin880625]

include full patch context

[goldstein.w.n]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9985

There is no opcode parameter. Maybe 'bswap or bitreverse nodes'?

[goldstein.w.n]

The summary/commit message should explain the transform you're adding.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10000

OldLHS might be from a node with multiple results - you need OldLHS->hasOneUse() (same for OldRHS below)

[goldstein.w.n]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10000

Thats already there in: if (OldLHS.getOpcode() == Opcode && OldLHS.hasOneUse()) { no?

Although I realized we will miss the following case:
(bswap (logic (bswap X), (bswap Y)) -> (logic X, Y)
if (bswap X) and / or (bswap Y) are multi-use.

Even if both arms are mult-use we still save an instruction doing this optimizations.
Maybe there should be a check if both arms match opcode, and if so, to ignore
multiuse check?

[austin880625]

Add implementation of bswap(logic_op(bswap(x), bswap(y))) -> logic_op(x, y) fold
Update some comments that are not aligned with code

[goldstein.w.n]

LGTM. Note, I'm not a maintainer so please wait a day or so before pushing so others can check it out.

Maybe follow up patch to enable for bitreverse?

[austin880625]

update with the base commit of test cases

[austin880625]

update with test cases and rebase onto main

[RKSimon]

Please can you rebase on D149782 ?

[austin880625]

oh by rebase onto main I mean I rebased the two commit(for D149782 and for D149783) in my branch onto the main branch together, so this patch is still based on the commit for D149782. For clarity these are the commands I used:

git diff main HEAD~ -U999999 > ../62236-DAG-test.patch #for D149782, based on previously pulled main branch
git diff HEAD~ HEAD -U999999 > ../62236-DAG-impl.patch #for this D149783

Let me know if I did something wrong here(or there's better commit arrangement

[goldstein.w.n]

In D149783#4325160, @austin880625 wrote:

oh by rebase onto main I mean I rebased the two commit(for D149782 and for D149783) in my branch onto the main branch together, so this patch is still based on the commit for D149782. For clarity these are the commands I used:

git diff main HEAD~ -U999999 > ../62236-DAG-test.patch #for D149782, based on previously pulled main branch
git diff HEAD~ HEAD -U999999 > ../62236-DAG-impl.patch #for this D149783

The issue is that you updated purely D149782 with the new tests, but the current version of D149783 is not based on the version of D149782 with the new tests.

[RKSimon]

Yes, we're missing the new arm test coverage

[austin880625]

@goldstein.w.n Sorry I downloaded the raw patch and compared with my git diff one without finding actual difference. Might need more clarification on how to confirm "not based on the version of D149782"

From the diff with previous patch the bs_xor_rhs_brev32 test case was removed in the diff context, so I thought it should be based on the new test cases alr? However the test cases in ARM backend only contains negative tests so they have no diff in this patch, maybe I should also copy some positive ones from x86.

[austin880625]

In D149783#4325222, @RKSimon wrote:

Yes, we're missing the new arm test coverage

noted, adding the ARM positive test cases

[austin880625]

contain the diff with updated positive tests(based on new test case change)

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10003

(style) Break up if-else chains as each cases returns

[austin880625]

fix if styling on early return

[goldstein.w.n]

LGTM. @RKSimon do you still have concerns?

[RKSimon]

LGTM - @goldstein.w.n please can you help commit Austin's bswap patches?

[goldstein.w.n]

In D149783#4345098, @RKSimon wrote:

LGTM - @goldstein.w.n please can you help commit Austin's bswap patches?

Sure.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue combineShiftToMULH(SDNode *N, SelectionDAG &DAG,
   }
 
   SDValue Result =
       DAG.getNode(MulhOpcode, DL, NarrowVT, LeftOp.getOperand(0), MulhRightOp);
   return (N->getOpcode() == ISD::SRA ? DAG.getSExtOrTrunc(Result, DL, WideVT)
                                      : DAG.getZExtOrTrunc(Result, DL, WideVT));
 }
 
+// fold (bswap (logic_op(bswap(x),y))) -> logic_op(x,bswap(y))
+// This helper function accept SDNode with opcode ISD::BSWAP and ISD::BITREVERSE
+static SDValue foldBitOrderCrossLogicOp(SDNode *N, SelectionDAG &DAG) {
+  unsigned Opcode = N->getOpcode();
+  if (Opcode != ISD::BSWAP && Opcode != ISD::BITREVERSE)
+    return SDValue();
+
+  SDValue N0 = N->getOperand(0);
+  EVT VT = N->getValueType(0);
+  SDLoc DL(N);
+  if (ISD::isBitwiseLogicOp(N0.getOpcode()) && N0.hasOneUse()) {
+    SDValue OldLHS = N0.getOperand(0);
+    SDValue OldRHS = N0.getOperand(1);
+
+    // If both operands are bswap/bitreverse, ignore the multiuse
+    // Otherwise need to ensure logic_op and bswap/bitreverse(x) have one use.
+    if (OldLHS.getOpcode() == Opcode && OldRHS.getOpcode() == Opcode) {
+      return DAG.getNode(N0.getOpcode(), DL, VT, OldLHS.getOperand(0),
+                         OldRHS.getOperand(0));
+    }
+
+    if (OldLHS.getOpcode() == Opcode && OldLHS.hasOneUse()) {
+      SDValue NewBitReorder = DAG.getNode(Opcode, DL, VT, OldRHS);
+      return DAG.getNode(N0.getOpcode(), DL, VT, OldLHS.getOperand(0),
+                         NewBitReorder);
+    }
+
+    if (OldRHS.getOpcode() == Opcode && OldRHS.hasOneUse()) {
+      SDValue NewBitReorder = DAG.getNode(Opcode, DL, VT, OldLHS);
+      return DAG.getNode(N0.getOpcode(), DL, VT, NewBitReorder,
+                         OldRHS.getOperand(0));
+    }
+  }
+  return SDValue();
+}
+
 SDValue DAGCombiner::visitSRA(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   if (SDValue V = DAG.simplifyShift(N0, N1))
     return V;
 
   EVT VT = N0.getValueType();
   unsigned OpSizeInBits = VT.getScalarSizeInBits();
if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL) &&
     if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
         ShAmt->getZExtValue() % 8 == 0) {
       SDValue NewSwap = DAG.getNode(ISD::BSWAP, DL, VT, N0.getOperand(0));
       unsigned InverseShift = N0.getOpcode() == ISD::SHL ? ISD::SRL : ISD::SHL;
       return DAG.getNode(InverseShift, DL, VT, NewSwap, N0.getOperand(1));
     }
   }
 
+  if (SDValue V = foldBitOrderCrossLogicOp(N, DAG))
+    return V;
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitBITREVERSE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
 
   // fold (bitreverse c1) -> c2

llvm/test/CodeGen/ARM/combine-bswap.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=thumbv7m-none-eabi -mattr=v7 | FileCheck %s --check-prefixes=CHECK
 
 declare i32 @llvm.bswap.i32(i32) readnone
 declare i64 @llvm.bswap.i64(i64) readnone
 declare i32 @llvm.bitreverse.i32(i32) readnone
 
 define i32 @bs_and_lhs_bs32(i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: bs_and_lhs_bs32:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    rev r0, r0
+; CHECK-NEXT:    rev r1, r1
 ; CHECK-NEXT:    ands r0, r1
-; CHECK-NEXT:    rev r0, r0
 ; CHECK-NEXT:    bx lr
   %1 = tail call i32 @llvm.bswap.i32(i32 %a)
   %2 = and i32 %1, %b
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i64 @bs_or_rhs_bs64(i64 %a, i64 %b) #0 {
 ; CHECK-LABEL: bs_or_rhs_bs64:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    rev r2, r2
-; CHECK-NEXT:    orrs r1, r2
-; CHECK-NEXT:    rev r2, r1
-; CHECK-NEXT:    rev r1, r3
-; CHECK-NEXT:    orrs r0, r1
-; CHECK-NEXT:    rev r1, r0
+; CHECK-NEXT:    rev r1, r1
+; CHECK-NEXT:    rev r0, r0
+; CHECK-NEXT:    orrs r2, r1
+; CHECK-NEXT:    orr.w r1, r0, r3
 ; CHECK-NEXT:    mov r0, r2
 ; CHECK-NEXT:    bx lr
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = or i64 %a, %1
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i32 @bs_and_all_operand_multiuse(i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: bs_and_all_operand_multiuse:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    rev r1, r1
-; CHECK-NEXT:    rev r0, r0
 ; CHECK-NEXT:    and.w r2, r0, r1
-; CHECK-NEXT:    rev r2, r2
+; CHECK-NEXT:    rev r0, r0
+; CHECK-NEXT:    rev r1, r1
 ; CHECK-NEXT:    muls r0, r2, r0
 ; CHECK-NEXT:    muls r0, r1, r0
 ; CHECK-NEXT:    bx lr
   %1 = tail call i32 @llvm.bswap.i32(i32 %a)
   %2 = tail call i32 @llvm.bswap.i32(i32 %b)
   %3 = and i32 %1, %2
   %4 = tail call i32 @llvm.bswap.i32(i32 %3)
   %5 = mul i32 %1, %4 ;increase use of left bswap

llvm/test/CodeGen/X86/combine-bswap.ll

 }
 
 define i32 @bs_and_lhs_bs32(i32 %a, i32 %b) #0 {
 ; X86-LABEL: bs_and_lhs_bs32:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_and_lhs_bs32:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    bswapl %eax
-; X64-NEXT:    andl %esi, %eax
+; X64-NEXT:    movl %esi, %eax
 ; X64-NEXT:    bswapl %eax
+; X64-NEXT:    andl %edi, %eax
 ; X64-NEXT:    retq
   %1 = tail call i32 @llvm.bswap.i32(i32 %a)
   %2 = and i32 %1, %b
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i64 @bs_or_lhs_bs64(i64 %a, i64 %b) #0 {
 ; X86-LABEL: bs_or_lhs_bs64:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
-; X86-NEXT:    bswapl %edx
-; X86-NEXT:    orl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    bswapl %edx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_or_lhs_bs64:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    bswapq %rax
-; X64-NEXT:    orq %rsi, %rax
+; X64-NEXT:    movq %rsi, %rax
 ; X64-NEXT:    bswapq %rax
+; X64-NEXT:    orq %rdi, %rax
 ; X64-NEXT:    retq
   %1 = tail call i64 @llvm.bswap.i64(i64 %a)
   %2 = or i64 %1, %b
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i64 @bs_xor_rhs_bs64(i64 %a, i64 %b) #0 {
 ; X86-LABEL: bs_xor_rhs_bs64:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
-; X86-NEXT:    bswapl %edx
-; X86-NEXT:    xorl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    bswapl %edx
+; X86-NEXT:    xorl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_xor_rhs_bs64:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rsi, %rax
-; X64-NEXT:    bswapq %rax
-; X64-NEXT:    xorq %rdi, %rax
+; X64-NEXT:    movq %rdi, %rax
 ; X64-NEXT:    bswapq %rax
+; X64-NEXT:    xorq %rsi, %rax
 ; X64-NEXT:    retq
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = xor i64 %a, %1
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i32 @bs_and_all_operand_multiuse(i32 %a, i32 %b) #0 {
 ; X86-LABEL: bs_and_all_operand_multiuse:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    bswapl %ecx
-; X86-NEXT:    bswapl %eax
-; X86-NEXT:    movl %ecx, %edx
-; X86-NEXT:    andl %eax, %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %eax, %edx
 ; X86-NEXT:    bswapl %edx
-; X86-NEXT:    imull %ecx, %eax
+; X86-NEXT:    andl %ecx, %eax
+; X86-NEXT:    bswapl %ecx
 ; X86-NEXT:    imull %edx, %eax
+; X86-NEXT:    imull %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_and_all_operand_multiuse:
 ; X64:       # %bb.0:
-; X64-NEXT:    bswapl %edi
-; X64-NEXT:    bswapl %esi
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    andl %esi, %eax
 ; X64-NEXT:    bswapl %eax
-; X64-NEXT:    imull %edi, %esi
+; X64-NEXT:    andl %esi, %edi
+; X64-NEXT:    bswapl %esi
+; X64-NEXT:    imull %edi, %eax
 ; X64-NEXT:    imull %esi, %eax
 ; X64-NEXT:    retq
   %1 = tail call i32 @llvm.bswap.i32(i32 %a)
   %2 = tail call i32 @llvm.bswap.i32(i32 %b)
   %3 = and i32 %1, %2
   %4 = tail call i32 @llvm.bswap.i32(i32 %3)
   %5 = mul i32 %1, %4 ;increase use of left bswap
   %6 = mul i32 %2, %5 ;increase use of right bswap