[X86][Codegen] Shift amount mod: sh? i64 x, (32-y) --> sh? i64 x, -(y+32)

[lebedev.ri]

Summary

I've seen this in the wild when looking into a +5% runtime regression.
I was hoping that this would fix it, but it doesn't.

I'm not certain whether this is always beneficial?
But i'm actually mainly interested in the case where we already compute (y+32) (see last test),
so if we aren't okay with this in general, i can try restricting it to getNodeIfExists().

https://alive2.llvm.org/ce/z/ZCzJio

[lebedev.ri]

Ping

[RKSimon]

I think this does make sense, the increased use of basic 2op LEAs shouldn't be a perf issue, and we should reduce register pressure.

Any other comments?

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

3858

Please can you rebase this? I've tried to cleanup some of the repeated casts

[lebedev.ri]

llvm/test/CodeGen/X86/64-bit-shift-by-32-minus-y.ll

293–300

To reiterate, i'm most interested in this case, where we already computed the x+32, so we get that for free.

[lebedev.ri]

@RKSimon thank you for taking a look!
Rebased.

[spatel]

This would regress the case if the 32-x has another use (add test)?

define i64 @sub_cse(i64 %val, i64 %shamt, i64*%dst) nounwind {
  %negshamt = sub i64 32, %shamt
  store i64 %negshamt, i64* %dst
  %shifted = shl i64 %val, %negshamt
  ret i64 %shifted
}

[lebedev.ri]

Adding testcase from @spatel.

[lebedev.ri]

Don't transform if the old sub has other uses.

[spatel]

hasOneUse() protects against regression. The other cases look neutral or better, so LGTM.

[lebedev.ri]

In D101944#2750966, @spatel wrote:

hasOneUse() protects against regression. The other cases look neutral or better, so LGTM.

Thank you for the review!

[RKSimon]

@lebedev.ri https://bugs.llvm.org/show_bug.cgi?id=50431 appears to be due to this - please can you take a look at @craig.topper's proposed fix?

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

if (ShiftAmt->getOpcode() == ISD::ADD || ShiftAmt->getOpcode() == ISD::SUB) {
     auto *Add1C = dyn_cast<ConstantSDNode>(Add1);
     // If we are shifting by X+/-N where N == 0 mod Size, then just shift by X
     // to avoid the ADD/SUB.
     if (Add1C && Add1C->getAPIntValue().urem(Size) == 0) {
       NewShiftAmt = Add0;
       // If we are shifting by N-X where N == 0 mod Size, then just shift by -X
       // to generate a NEG instead of a SUB of a constant.
     } else if (ShiftAmt->getOpcode() == ISD::SUB && Add0C &&
-               Add0C->getAPIntValue() != 0 &&
-               Add0C->getAPIntValue().urem(Size) == 0) {
+               Add0C->getZExtValue() != 0) {
+      EVT SubVT = ShiftAmt.getValueType();
+      SDValue X;
+      if (Add0C->getZExtValue() % Size == 0)
+        X = Add1;
+      else if (ShiftAmt.hasOneUse() && Size == 64 &&
+               Add0C->getZExtValue() % 32 == 0) {
+        // We have a 64-bit shift by (n*32-x), turn it into -(x+n*32).
+        // This is mainly beneficial if we already compute (x+n*32).
+        if (Add1.getOpcode() == ISD::TRUNCATE) {
+          Add1 = Add1.getOperand(0);
+          SubVT = Add1.getValueType();
+        }
+        X = CurDAG->getNode(ISD::ADD, DL, SubVT, Add1,
+                            CurDAG->getZExtOrTrunc(Add0, DL, SubVT));
+        insertDAGNode(*CurDAG, OrigShiftAmt, X);
+      } else
+        return false;
       // Insert a negate op.
       // TODO: This isn't guaranteed to replace the sub if there is a logic cone
       // that uses it that's not a shift.
-      EVT SubVT = ShiftAmt.getValueType();
       SDValue Zero = CurDAG->getConstant(0, DL, SubVT);
-      SDValue Neg = CurDAG->getNode(ISD::SUB, DL, SubVT, Zero, Add1);
+      SDValue Neg = CurDAG->getNode(ISD::SUB, DL, SubVT, Zero, X);
       NewShiftAmt = Neg;
 
       // Insert these operands into a valid topological order so they can
       // get selected independently.
       insertDAGNode(*CurDAG, OrigShiftAmt, Zero);
       insertDAGNode(*CurDAG, OrigShiftAmt, Neg);
     } else
       return false;

llvm/test/CodeGen/X86/64-bit-shift-by-32-minus-y.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-NOBMI2
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi2 | FileCheck %s --check-prefixes=X64-BMI2
 ; RUN: llc < %s -mtriple=i686-unknown-unknown                | FileCheck %s --check-prefixes=X32-NOBMI2
 ; RUN: llc < %s -mtriple=i686-unknown-unknown   -mattr=+bmi2 | FileCheck %s --check-prefixes=X32-BMI2
 
 define i64 @t0(i64 %val, i64 %shamt) nounwind {
 ; X64-NOBMI2-LABEL: t0:
 ; X64-NOBMI2:       # %bb.0:
 ; X64-NOBMI2-NEXT:    movq %rdi, %rax
-; X64-NOBMI2-NEXT:    movb $32, %cl
-; X64-NOBMI2-NEXT:    subb %sil, %cl
+; X64-NOBMI2-NEXT:    leaq 32(%rsi), %rcx
+; X64-NOBMI2-NEXT:    negq %rcx
+; X64-NOBMI2-NEXT:    # kill: def $cl killed $cl killed $rcx
 ; X64-NOBMI2-NEXT:    shlq %cl, %rax
 ; X64-NOBMI2-NEXT:    retq
 ;
 ; X64-BMI2-LABEL: t0:
 ; X64-BMI2:       # %bb.0:
-; X64-BMI2-NEXT:    movb $32, %al
-; X64-BMI2-NEXT:    subb %sil, %al
-; X64-BMI2-NEXT:    shlxq %rax, %rdi, %rax
+; X64-BMI2-NEXT:    addq $32, %rsi
+; X64-BMI2-NEXT:    negq %rsi
+; X64-BMI2-NEXT:    shlxq %rsi, %rdi, %rax
 ; X64-BMI2-NEXT:    retq
 ;
 ; X32-NOBMI2-LABEL: t0:
 ; X32-NOBMI2:       # %bb.0:
 ; X32-NOBMI2-NEXT:    pushl %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NOBMI2-NEXT:    movb $32, %cl
; X32-BMI2-NEXT:    retl
   %shifted = shl i64 %val, %negshamt
   ret i64 %shifted
 }
 
 define i64 @t4(i64 %val, i64 %shamt) nounwind {
 ; X64-NOBMI2-LABEL: t4:
 ; X64-NOBMI2:       # %bb.0:
 ; X64-NOBMI2-NEXT:    movq %rdi, %rax
-; X64-NOBMI2-NEXT:    movb $96, %cl
-; X64-NOBMI2-NEXT:    subb %sil, %cl
+; X64-NOBMI2-NEXT:    leaq 96(%rsi), %rcx
+; X64-NOBMI2-NEXT:    negq %rcx
+; X64-NOBMI2-NEXT:    # kill: def $cl killed $cl killed $rcx
 ; X64-NOBMI2-NEXT:    shlq %cl, %rax
 ; X64-NOBMI2-NEXT:    retq
 ;
 ; X64-BMI2-LABEL: t4:
 ; X64-BMI2:       # %bb.0:
-; X64-BMI2-NEXT:    movb $96, %al
-; X64-BMI2-NEXT:    subb %sil, %al
-; X64-BMI2-NEXT:    shlxq %rax, %rdi, %rax
+; X64-BMI2-NEXT:    addq $96, %rsi
+; X64-BMI2-NEXT:    negq %rsi
+; X64-BMI2-NEXT:    shlxq %rsi, %rdi, %rax
 ; X64-BMI2-NEXT:    retq
 ;
 ; X32-NOBMI2-LABEL: t4:
 ; X32-NOBMI2:       # %bb.0:
 ; X32-NOBMI2-NEXT:    pushl %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X32-NOBMI2-NEXT:    movb $96, %cl
; X32-BMI2-NEXT:    retl
   %negshamt = sub i64 96, %shamt
   %shifted = shl i64 %val, %negshamt
   ret i64 %shifted
 }
 
 define i64 @t5_cse(i64 %val, i64 %shamt, i64*%dst) nounwind {
 ; X64-NOBMI2-LABEL: t5_cse:
 ; X64-NOBMI2:       # %bb.0:
+; X64-NOBMI2-NEXT:    movq %rsi, %rcx
 ; X64-NOBMI2-NEXT:    movq %rdi, %rax
-; X64-NOBMI2-NEXT:    leaq 32(%rsi), %rcx
+; X64-NOBMI2-NEXT:    addq $32, %rcx
 ; X64-NOBMI2-NEXT:    movq %rcx, (%rdx)
-; X64-NOBMI2-NEXT:    movb $32, %cl
-; X64-NOBMI2-NEXT:    subb %sil, %cl
+; X64-NOBMI2-NEXT:    negq %rcx
+; X64-NOBMI2-NEXT:    # kill: def $cl killed $cl killed $rcx
 ; X64-NOBMI2-NEXT:    shlq %cl, %rax
 ; X64-NOBMI2-NEXT:    retq
 ;
 ; X64-BMI2-LABEL: t5_cse:
 ; X64-BMI2:       # %bb.0:
-; X64-BMI2-NEXT:    leaq 32(%rsi), %rax
-; X64-BMI2-NEXT:    movq %rax, (%rdx)
-; X64-BMI2-NEXT:    movb $32, %al
-; X64-BMI2-NEXT:    subb %sil, %al
-; X64-BMI2-NEXT:    shlxq %rax, %rdi, %rax
+; X64-BMI2-NEXT:    addq $32, %rsi
+; X64-BMI2-NEXT:    movq %rsi, (%rdx)
+; X64-BMI2-NEXT:    negq %rsi
+; X64-BMI2-NEXT:    shlxq %rsi, %rdi, %rax
 ; X64-BMI2-NEXT:    retq
 ;
 ; X32-NOBMI2-LABEL: t5_cse:
 ; X32-NOBMI2:       # %bb.0:
 ; X32-NOBMI2-NEXT:    pushl %ebx
 ; X32-NOBMI2-NEXT:    pushl %edi
 ; X32-NOBMI2-NEXT:    pushl %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; X32-NOBMI2-NEXT:    movl {{[0-9]+}}(%esp), %edx