[DAGCombiner] Hoist funnel shifts from logic operation.

[fzhinkin]

Summary

Hoist funnel shift from logic op:
logic_op (FSH x0, x1, s), (FSH y0, y1, s) --> FSH (logic_op x0, y0), (logic_op x1, y1), s

The transformation improves code generated for some cases related to issue https://github.com/llvm/llvm-project/issues/49541.

Reduced amount of funnel shifts can also improve throughput on x86 CPUs by utilizing more available ports: https://quick-bench.com/q/gC7AKkJJsDZzRrs_JWDzm9t_iDM

Transformation correctness checks:
https://alive2.llvm.org/ce/z/TKPULH
https://alive2.llvm.org/ce/z/UvTd_9
https://alive2.llvm.org/ce/z/j8qW3_
https://alive2.llvm.org/ce/z/7Wq7gE
https://alive2.llvm.org/ce/z/Xr5w8R
https://alive2.llvm.org/ce/z/D5xe_E
https://alive2.llvm.org/ce/z/2yBZiy

[spatel]

Please pre-commit the new tests with baseline results, so we'll just show the diffs in this patch.
Add an alive2 proof link for at least one of the patterns to the patch description, so we can show correctness.

[fzhinkin]

In D130994#3700572, @spatel wrote:

Please pre-commit the new tests with baseline results, so we'll just show the diffs in this patch.

Unfortunately, I don't have a permission to commit. Here's a patch adding tests with checks generated using llc build from the main branch:

D130994_precommit_tests.patch5 KBDownload

.

I'll appreciate if you can help me with committing it.

Add an alive2 proof link for at least one of the patterns to the patch description, so we can show correctness.

Done, thanks!

[spatel]

In D130994#3702138, @fzhinkin wrote:

In D130994#3700572, @spatel wrote:

Please pre-commit the new tests with baseline results, so we'll just show the diffs in this patch.

Unfortunately, I don't have a permission to commit. Here's a patch adding tests with checks generated using llc build from the main branch:

D130994_precommit_tests.patch5 KBDownload

.

I'll appreciate if you can help me with committing it.

Sure: 249a7ed75072

Add an alive2 proof link for at least one of the patterns to the patch description, so we can show correctness.

Done, thanks!

Great - please update the patch here Phab with the test changes.

[fzhinkin]

Rebase

[fzhinkin]

In D130994#3702339, @spatel wrote:

In D130994#3702138, @fzhinkin wrote:

In D130994#3700572, @spatel wrote:

Please pre-commit the new tests with baseline results, so we'll just show the diffs in this patch.

Unfortunately, I don't have a permission to commit. Here's a patch adding tests with checks generated using llc build from the main branch:

D130994_precommit_tests.patch5 KBDownload

.

I'll appreciate if you can help me with committing it.

Sure: 249a7ed75072

Thank you!

Add an alive2 proof link for at least one of the patterns to the patch description, so we can show correctness.

Done, thanks!

Great - please update the patch here Phab with the test changes.

Done

[spatel]

LGTM
I'll push this for you if there are no other comments.
You could request commit access now (given your patch history, I don't think there would be a problem):
https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

[fzhinkin]

In D130994#3702714, @spatel wrote:

LGTM
I'll push this for you if there are no other comments.
You could request commit access now (given your patch history, I don't think there would be a problem):
https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

Thank you!

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *N) {
   if (HandOpcode == ISD::BSWAP) {
     // If either operand has other uses, this transform is not an improvement.
     if (!N0.hasOneUse() || !N1.hasOneUse())
       return SDValue();
     SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
     return DAG.getNode(HandOpcode, DL, VT, Logic);
   }
 
+  // For funnel shifts FSHL/FSHR:
+  // logic_op (OP x, x1, s), (OP y, y1, s) -->
+  // --> OP (logic_op x, y), (logic_op, x1, y1), s
+  if ((HandOpcode == ISD::FSHL || HandOpcode == ISD::FSHR) &&
+      N0.getOperand(2) == N1.getOperand(2)) {
+    if (!N0.hasOneUse() || !N1.hasOneUse())
+      return SDValue();
+    SDValue X1 = N0.getOperand(1);
+    SDValue Y1 = N1.getOperand(1);
+    SDValue S = N0.getOperand(2);
+    SDValue Logic0 = DAG.getNode(LogicOpcode, DL, VT, X, Y);
+    SDValue Logic1 = DAG.getNode(LogicOpcode, DL, VT, X1, Y1);
+    return DAG.getNode(HandOpcode, DL, VT, Logic0, Logic1, S);
+  }
+
   // Simplify xor/and/or (bitcast(A), bitcast(B)) -> bitcast(op (A,B))
   // Only perform this optimization up until type legalization, before
   // LegalizeVectorOprs. LegalizeVectorOprs promotes vector operations by
   // adding bitcasts. For example (xor v4i32) is promoted to (v2i64), and
   // we don't want to undo this promotion.
   // We also handle SCALAR_TO_VECTOR because xor/or/and operations are cheaper
   // on scalars.
   if ((HandOpcode == ISD::BITCAST || HandOpcode == ISD::SCALAR_TO_VECTOR) &&

llvm/test/CodeGen/X86/funnel-shift-logic-fold.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s --check-prefixes=X64
+
+declare i64 @llvm.fshl.i64(i64, i64, i64) nounwind readnone
+declare i64 @llvm.fshr.i64(i64, i64, i64) nounwind readnone
+
+define i64 @hoist_fshl_from_or(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshl_from_or:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    orq %rcx, %rsi
+; X64-NEXT:    orq %rdx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shldq %cl, %rsi, %rax
+; X64-NEXT:    retq
+  %fshl.0 = call i64 @llvm.fshl.i64(i64 %a, i64 %b, i64 %s)
+  %fshl.1 = call i64 @llvm.fshl.i64(i64 %c, i64 %d, i64 %s)
+  %res = or i64 %fshl.0, %fshl.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshl_from_and(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshl_from_and:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    andq %rcx, %rsi
+; X64-NEXT:    andq %rdx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shldq %cl, %rsi, %rax
+; X64-NEXT:    retq
+  %fshl.0 = call i64 @llvm.fshl.i64(i64 %a, i64 %b, i64 %s)
+  %fshl.1 = call i64 @llvm.fshl.i64(i64 %c, i64 %d, i64 %s)
+  %res = and i64 %fshl.0, %fshl.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshl_from_xor(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshl_from_xor:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    xorq %rcx, %rsi
+; X64-NEXT:    xorq %rdx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shldq %cl, %rsi, %rax
+; X64-NEXT:    retq
+  %fshl.0 = call i64 @llvm.fshl.i64(i64 %a, i64 %b, i64 %s)
+  %fshl.1 = call i64 @llvm.fshl.i64(i64 %c, i64 %d, i64 %s)
+  %res = xor i64 %fshl.0, %fshl.1
+  ret i64 %res
+}
+
+define i64 @fshl_or_with_different_shift_value(i64 %a, i64 %b, i64 %c, i64 %d) nounwind {
+; X64-LABEL: fshl_or_with_different_shift_value:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdx, %rax
+; X64-NEXT:    shldq $12, %rsi, %rdi
+; X64-NEXT:    shldq $13, %rcx, %rax
+; X64-NEXT:    orq %rdi, %rax
+; X64-NEXT:    retq
+  %fshl.0 = call i64 @llvm.fshl.i64(i64 %a, i64 %b, i64 12)
+  %fshl.1 = call i64 @llvm.fshl.i64(i64 %c, i64 %d, i64 13)
+  %res = or i64 %fshl.0, %fshl.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshl_from_or_const_shift(i64 %a, i64 %b, i64 %c, i64 %d) nounwind {
+; X64-LABEL: hoist_fshl_from_or_const_shift:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    orq %rcx, %rsi
+; X64-NEXT:    orq %rdx, %rax
+; X64-NEXT:    shldq $15, %rsi, %rax
+; X64-NEXT:    retq
+  %fshl.0 = call i64 @llvm.fshl.i64(i64 %a, i64 %b, i64 15)
+  %fshl.1 = call i64 @llvm.fshl.i64(i64 %c, i64 %d, i64 15)
+  %res = or i64 %fshl.0, %fshl.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshr_from_or(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshr_from_or:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    orq %rdx, %rdi
+; X64-NEXT:    orq %rcx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shrdq %cl, %rdi, %rax
+; X64-NEXT:    retq
+  %fshr.0 = call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 %s)
+  %fshr.1 = call i64 @llvm.fshr.i64(i64 %c, i64 %d, i64 %s)
+  %res = or i64 %fshr.0, %fshr.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshr_from_and(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshr_from_and:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    andq %rdx, %rdi
+; X64-NEXT:    andq %rcx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shrdq %cl, %rdi, %rax
+; X64-NEXT:    retq
+  %fshr.0 = call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 %s)
+  %fshr.1 = call i64 @llvm.fshr.i64(i64 %c, i64 %d, i64 %s)
+  %res = and i64 %fshr.0, %fshr.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshr_from_xor(i64 %a, i64 %b, i64 %c, i64 %d, i64 %s) nounwind {
+; X64-LABEL: hoist_fshr_from_xor:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    xorq %rdx, %rdi
+; X64-NEXT:    xorq %rcx, %rax
+; X64-NEXT:    movl %r8d, %ecx
+; X64-NEXT:    shrdq %cl, %rdi, %rax
+; X64-NEXT:    retq
+  %fshr.0 = call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 %s)
+  %fshr.1 = call i64 @llvm.fshr.i64(i64 %c, i64 %d, i64 %s)
+  %res = xor i64 %fshr.0, %fshr.1
+  ret i64 %res
+}
+
+define i64 @fshr_or_with_different_shift_value(i64 %a, i64 %b, i64 %c, i64 %d) nounwind {
+; X64-LABEL: fshr_or_with_different_shift_value:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdx, %rax
+; X64-NEXT:    shldq $52, %rsi, %rdi
+; X64-NEXT:    shldq $51, %rcx, %rax
+; X64-NEXT:    orq %rdi, %rax
+; X64-NEXT:    retq
+  %fshr.0 = call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 12)
+  %fshr.1 = call i64 @llvm.fshr.i64(i64 %c, i64 %d, i64 13)
+  %res = or i64 %fshr.0, %fshr.1
+  ret i64 %res
+}
+
+define i64 @hoist_fshr_from_or_const_shift(i64 %a, i64 %b, i64 %c, i64 %d) nounwind {
+; X64-LABEL: hoist_fshr_from_or_const_shift:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    orq %rcx, %rsi
+; X64-NEXT:    orl %edx, %eax
+; X64-NEXT:    shldq $49, %rsi, %rax
+; X64-NEXT:    retq
+  %fshr.0 = call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 15)
+  %fshr.1 = call i64 @llvm.fshr.i64(i64 %c, i64 %d, i64 15)
+  %res = or i64 %fshr.0, %fshr.1
+  ret i64 %res
+}

llvm/test/CodeGen/X86/icmp-shift-opt.ll

 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; X86-NEXT:    .p2align 4, 0x90
 ; X86-NEXT:  .LBB0_1: # %loop
 ; X86-NEXT:    # =>This Inner Loop Header: Depth=1
 ; X86-NEXT:    addl $1, %edi
 ; X86-NEXT:    adcl $0, %esi
 ; X86-NEXT:    adcl $0, %edx
 ; X86-NEXT:    adcl $0, %ecx
-; X86-NEXT:    movl %ecx, %ebx
-; X86-NEXT:    shldl $4, %edx, %ebx
+; X86-NEXT:    movl %edx, %ebx
+; X86-NEXT:    orl %ecx, %ebx
 ; X86-NEXT:    movl %esi, %ebp
-; X86-NEXT:    orl %ecx, %ebp
-; X86-NEXT:    shrdl $28, %edx, %ebp
 ; X86-NEXT:    orl %ebx, %ebp
+; X86-NEXT:    shrdl $28, %ebx, %ebp
 ; X86-NEXT:    jne .LBB0_1
 ; X86-NEXT:  # %bb.2: # %exit
 ; X86-NEXT:    movl %edi, (%eax)
 ; X86-NEXT:    movl %esi, 4(%eax)
 ; X86-NEXT:    movl %edx, 8(%eax)
 ; X86-NEXT:    movl %ecx, 12(%eax)
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    popl %edi

 
 exit:
   ret i128 %inc
 }
 
 define i1 @opt_setcc_srl_eq_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_srl_eq_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shrdl $17, %ecx, %eax
-; X86-NEXT:    orl %esi, %ecx
-; X86-NEXT:    shldl $15, %edx, %esi
-; X86-NEXT:    orl %esi, %eax
-; X86-NEXT:    shrdl $17, %edx, %ecx
-; X86-NEXT:    orl %eax, %ecx
+; X86-NEXT:    orl %ecx, %edx
+; X86-NEXT:    orl %eax, %edx
+; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    shldl $15, %edx, %eax
 ; X86-NEXT:    sete %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_srl_eq_zero:
 ; X64:       # %bb.0:
 ; X64-NEXT:    shrq $17, %rdi
 ; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
    %srl = lshr i128 %a, 17
    %cmp = icmp eq i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_srl_ne_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_srl_ne_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shrdl $17, %ecx, %eax
-; X86-NEXT:    orl %esi, %ecx
-; X86-NEXT:    shldl $15, %edx, %esi
-; X86-NEXT:    orl %esi, %eax
-; X86-NEXT:    shrdl $17, %edx, %ecx
-; X86-NEXT:    orl %eax, %ecx
+; X86-NEXT:    orl %ecx, %edx
+; X86-NEXT:    orl %eax, %edx
+; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    shldl $15, %edx, %eax
 ; X86-NEXT:    setne %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_srl_ne_zero:
 ; X64:       # %bb.0:
 ; X64-NEXT:    shrq $17, %rdi
 ; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    setne %al
 ; X64-NEXT:    retq
    %srl = lshr i128 %a, 17
    %cmp = icmp ne i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_eq_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_shl_eq_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shldl $17, %edx, %esi
-; X86-NEXT:    orl %eax, %edx
-; X86-NEXT:    shldl $17, %ecx, %edx
-; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    orl %esi, %ecx
-; X86-NEXT:    orl %ecx, %edx
+; X86-NEXT:    shll $17, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    sete %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_shl_eq_zero:
 ; X64:       # %bb.0:
 ; X64-NEXT:    shlq $17, %rsi
 ; X64-NEXT:    orq %rdi, %rsi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
    %shl = shl i128 %a, 17
    %cmp = icmp eq i128 %shl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_ne_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_shl_ne_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shldl $17, %edx, %esi
-; X86-NEXT:    orl %eax, %edx
-; X86-NEXT:    shldl $17, %ecx, %edx
-; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    orl %esi, %ecx
-; X86-NEXT:    orl %ecx, %edx
+; X86-NEXT:    shll $17, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    setne %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_shl_ne_zero:
 ; X64:       # %bb.0:
 ; X64-NEXT:    shlq $17, %rsi
 ; X64-NEXT:    orq %rdi, %rsi
 ; X64-NEXT:    setne %al
 ; X64-NEXT:    retq

 }
 
 ; Check that optimization is applied to DAG having appropriate shape
 ; even if there were no actual shift's expansion.
 define i1 @opt_setcc_expanded_shl_correct_shifts(i64 %a, i64 %b) nounwind {
 ; X86-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    orl %eax, %edx
-; X86-NEXT:    shldl $17, %ecx, %edx
+; X86-NEXT:    orl %eax, %ecx
 ; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    orl %edx, %ecx
 ; X86-NEXT:    sete %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; X64:       # %bb.0:
 ; X64-NEXT:    shlq $17, %rdi
 ; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    sete %al