[DAGCombiner] Add bswap(logic_op(bswap(x), y)) regression test case; NFC

[austin880625]

Summary

Fold the following case on SelectionDAG combiner
This patch includes the regression test cases

bswap(logic_op(x, bswap(y))) -> logic_op(bswap(x), y)
bswap(logic_op(bswap(x), y)) -> logic_op(x, bswap(y))
bswap(logic_op(bswap(x), bswap(y))) -> logic_op(x, y) (with multiuse)

[austin880625]

include full context

[goldstein.w.n]

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

327

youre *_rhs_* still have the bswap on the lhs.

385

Can you do two things.

1. Add a negative test that is (bswap (logic (bitreverse a), b))
2. Make some of the tests use bitreverse. You don't need to add new tests, just modify half the bswap ones to use `bitreverse instead.

[RKSimon]

Maybe xor + or bitlogic coverage? You don't need to repeat the tests you've written, just convert some to use the other ops instead

[austin880625]

Update xor, or logical ops coverage in the recently added test cases

[goldstein.w.n]

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

385

ping on this comment, otherwise LG.

[RKSimon]

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

385

+1 for (1) - but I'd prefer equivalent tests added to combine-bitreverse.ll instead of being added to combine-bswap.ll

[austin880625]

add bitreverse test cases and a bswap, bitreverse mixed negative test case

[austin880625]

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

385

I was trying to add (bitreverse (logic (bswap a), b)) in combine-bitreverse.ll and (bswap (logic (bitreverse a), b)) in combine-bswap.ll and found the following:

x86 doesn't have RBIT like ARM, so the first instruction of bitreverse is a bswap(to replace 0x00FF00FF), then the 0x0F0F0F0F, 0x33333333,... twiddling. This cause the (bitreverse (logic (bswap a), b)) actually got optimized as a negative test, just not on the major part of bitreverse.

; X86-LABEL: brev_xor_rhs_bs32:                                                      
; X86:       # %bb.0:                                                                
; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
; X86-NEXT:    bswapl %eax ; <--- this becomes LHS
; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax <---- this line got removed
; X86-NEXT:    movl %eax, %ecx
; X86-NEXT:    andl $252645135, %ecx # imm = 0xF0F0F0F
; X86-NEXT:    shll $4, %ecx
...

Currently I only keep (bswap (logic (bitreverse a), b)) for this patch, then there's no diff after the optimization as desired, though this assumes the order of bswap and the manual bit ops.

Another way is moving these test cases into ARM version(need to create new files), which also reduces a lot of FileCheck lines

[goldstein.w.n]

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

385

I was trying to add (bitreverse (logic (bswap a), b)) in combine-bitreverse.ll and (bswap (logic (bitreverse a), b)) in combine-bswap.ll and found the following:

x86 doesn't have RBIT like ARM, so the first instruction of bitreverse is a bswap(to replace 0x00FF00FF), then the 0x0F0F0F0F, 0x33333333,... twiddling. This cause the (bitreverse (logic (bswap a), b)) actually got optimized as a negative test, just not on the major part of bitreverse.

@RKSimon maybe we should postpone x86 bitreverse lowing till after legalization?

; X86-LABEL: brev_xor_rhs_bs32:                                                      
; X86:       # %bb.0:                                                                
; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
; X86-NEXT:    bswapl %eax ; <--- this becomes LHS
; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax <---- this line got removed
; X86-NEXT:    movl %eax, %ecx
; X86-NEXT:    andl $252645135, %ecx # imm = 0xF0F0F0F
; X86-NEXT:    shll $4, %ecx
...

Currently I only keep (bswap (logic (bitreverse a), b)) for this patch, then there's no diff after the optimization as desired, though this assumes the order of bswap and the manual bit ops.

Another way is moving these test cases into ARM version(need to create new files), which also reduces a lot of FileCheck lines

Putting the test file in the arm backend would be fine.

[austin880625]

move bitreverse related test cases into ARM backend for rbit instruction support

[austin880625]

add positive test cases in ARM backend

[goldstein.w.n]

Applying: Add bswap(logic_op(bswap(x), y)) regression test case; NFC
.git/rebase-apply/patch:127: new blank line at EOF.
+
.git/rebase-apply/patch:220: new blank line at EOF.
+
warning: 2 lines add whitespace errors.

Can you fix the whitespace issues?

[goldstein.w.n]

LGTM.

llvm/test/CodeGen/ARM/combine-bitreverse.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 i16 @llvm.bswap.i16(i16) readnone
+declare i32 @llvm.bswap.i32(i32) readnone
+declare i32 @llvm.bitreverse.i32(i32) readnone
+
+define i32 @brev_and_lhs_brev32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_and_lhs_brev32:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    ands r0, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %a)
+  %2 = and i32 %1, %b
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  ret i32 %3
+}
+
+define i32 @brev_or_lhs_brev32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_or_lhs_brev32:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    orrs r0, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %a)
+  %2 = or i32 %1, %b
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  ret i32 %3
+}
+
+define i32 @brev_xor_rhs_brev32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_xor_rhs_brev32:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r1, r1
+; CHECK-NEXT:    eors r0, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %b)
+  %2 = xor i32 %a, %1
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  ret i32 %3
+}
+
+define i32 @brev_and_all_operand_multiuse(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_and_all_operand_multiuse:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r1, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    and.w r2, r0, r1
+; CHECK-NEXT:    rbit r2, r2
+; CHECK-NEXT:    muls r0, r2, r0
+; CHECK-NEXT:    muls r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %a)
+  %2 = tail call i32 @llvm.bitreverse.i32(i32 %b)
+  %3 = and i32 %1, %2
+  %4 = tail call i32 @llvm.bitreverse.i32(i32 %3)
+  %5 = mul i32 %1, %4 ;increase use of left bitreverse
+  %6 = mul i32 %2, %5 ;increase use of right bitreverse
+
+  ret i32 %6
+}
+
+; negative test
+define i32 @brev_and_rhs_brev32_multiuse1(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_and_rhs_brev32_multiuse1:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r1, r1
+; CHECK-NEXT:    ands r0, r1
+; CHECK-NEXT:    rbit r1, r0
+; CHECK-NEXT:    muls r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %b)
+  %2 = and i32 %1, %a
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  %4 = mul i32 %2, %3 ;increase use of logical op
+  ret i32 %4
+}
+
+; negative test
+define i32 @brev_and_rhs_brev32_multiuse2(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_and_rhs_brev32_multiuse2:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r1, r1
+; CHECK-NEXT:    ands r0, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    muls r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %b)
+  %2 = and i32 %1, %a
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  %4 = mul i32 %1, %3 ;increase use of inner bitreverse
+  ret i32 %4
+}
+
+; negative test
+define i32 @brev_xor_rhs_bs32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: brev_xor_rhs_bs32:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rev r1, r1
+; CHECK-NEXT:    eors r0, r1
+; CHECK-NEXT:    rbit r0, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bswap.i32(i32 %b)
+  %2 = xor i32 %a, %1
+  %3 = tail call i32 @llvm.bitreverse.i32(i32 %2)
+  ret i32 %3
+}
+

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:    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:    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:    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
+  %6 = mul i32 %2, %5 ;increase use of right bswap
+
+  ret i32 %6
+}
+
+; negative test
+define i32 @bs_and_rhs_bs32_multiuse1(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: bs_and_rhs_bs32_multiuse1:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rev r1, r1
+; CHECK-NEXT:    ands r0, r1
+; CHECK-NEXT:    rev r1, r0
+; CHECK-NEXT:    muls r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bswap.i32(i32 %b)
+  %2 = and i32 %1, %a
+  %3 = tail call i32 @llvm.bswap.i32(i32 %2)
+  %4 = mul i32 %2, %3 ;increase use of logical op
+  ret i32 %4
+}
+
+; negative test
+define i32 @bs_xor_rhs_brev32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: bs_xor_rhs_brev32:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rbit r1, r1
+; CHECK-NEXT:    eors r0, r1
+; CHECK-NEXT:    rev r0, r0
+; CHECK-NEXT:    bx lr
+  %1 = tail call i32 @llvm.bitreverse.i32(i32 %b)
+  %2 = xor i32 %a, %1
+  %3 = tail call i32 @llvm.bswap.i32(i32 %2)
+  ret i32 %3
+}
+

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

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown -mattr=+sse2 | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+avx | FileCheck %s --check-prefix=X64
 
 ; These tests just check that the plumbing is in place for @llvm.bitreverse. The
 ; actual output is massive at the moment as llvm.bitreverse is not yet legal.
 
 declare i32 @llvm.bitreverse.i32(i32) readnone
 declare i64 @llvm.bitreverse.i64(i64) readnone
 declare <4 x i32> @llvm.bitreverse.v4i32(<4 x i32>) readnone
+declare i32 @llvm.bswap.i32(i32) readnone
 
 ; fold (bitreverse undef) -> undef
 define i32 @test_undef() nounwind {
 ; X86-LABEL: test_undef:
 ; X86:       # %bb.0:
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_undef:

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

 ; X64-NEXT:    shll $17, %eax
 ; X64-NEXT:    bswapl %eax
 ; X64-NEXT:    retq
   %s = shl i32 %a0, 17
   %b = call i32 @llvm.bswap.i32(i32 %s)
   ret i32 %b
 }
 
+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:    bswapl %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:    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:    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:    bswapq %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:    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:    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:    bswapq %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:    bswapl %edx
+; X86-NEXT:    imull %ecx, %eax
+; X86-NEXT:    imull %edx, %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:    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
+
+  ret i32 %6
+}
+
+; negative test
+define i32 @bs_and_rhs_bs32_multiuse1(i32 %a, i32 %b) #0 {
+; X86-LABEL: bs_and_rhs_bs32_multiuse1:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    bswapl %ecx
+; X86-NEXT:    andl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    bswapl %eax
+; X86-NEXT:    imull %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: bs_and_rhs_bs32_multiuse1:
+; X64:       # %bb.0:
+; X64-NEXT:    bswapl %esi
+; X64-NEXT:    andl %edi, %esi
+; X64-NEXT:    movl %esi, %eax
+; X64-NEXT:    bswapl %eax
+; X64-NEXT:    imull %esi, %eax
+; X64-NEXT:    retq
+  %1 = tail call i32 @llvm.bswap.i32(i32 %b)
+  %2 = and i32 %1, %a
+  %3 = tail call i32 @llvm.bswap.i32(i32 %2)
+  %4 = mul i32 %2, %3 ;increase use of logical op
+  ret i32 %4
+}
+
+; negative test
+define i32 @bs_and_rhs_bs32_multiuse2(i32 %a, i32 %b) #0 {
+; X86-LABEL: bs_and_rhs_bs32_multiuse2:
+; X86:       # %bb.0:
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    bswapl %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    andl %ecx, %eax
+; X86-NEXT:    bswapl %eax
+; X86-NEXT:    imull %ecx, %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: bs_and_rhs_bs32_multiuse2:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    bswapl %esi
+; X64-NEXT:    andl %esi, %eax
+; X64-NEXT:    bswapl %eax
+; X64-NEXT:    imull %esi, %eax
+; X64-NEXT:    retq
+  %1 = tail call i32 @llvm.bswap.i32(i32 %b)
+  %2 = and i32 %1, %a
+  %3 = tail call i32 @llvm.bswap.i32(i32 %2)
+  %4 = mul i32 %1, %3 ;increase use of inner bswap
+  ret i32 %4
+}
+
 ; negative test
 define i64 @test_bswap64_shift17(i64 %a0) {
 ; X86-LABEL: test_bswap64_shift17:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    shldl $17, %edx, %eax
 ; X86-NEXT:    shll $17, %edx