Improve mul combine for negative multiplayer (2^c - 1)

[m_zuckerman]

Summary

This function improves the mul instruction combine function (combineMul)
by adding new layer of logic.
In this patch, we are adding the ability to fold (mul x, -((1 << c) -1))
or (mul x, -((1 << c) +1)) into (neg(X << c) -x) or (neg((x << c) + x) respective.

[igorb]

lib/Target/X86/X86ISelLowering.cpp

30263

does NumSign * SignMulAmt == MulAmt, or i missing something ?

30271

this is common code for the both cases . can we put it after if/else ?
if (NumSign == -1 && NewMul) ...

test/CodeGen/X86/imul.ll

175

Sorry, i can't understand the test output. Could you please auto-generate the CHECKS ?

[m_zuckerman]

lib/Target/X86/X86ISelLowering.cpp

30263

Yes mine is sext will the MulAmt is zext

[igorb]

LGTM

[efriedma]

How did this get merged without any performance data? It isn't obvious this is a good idea.

[m_zuckerman]

Hi Eli,

We tested the patch with internal performance tests.
If you have test/suite/benchmark that my patch bring down, please share them with me.

Regards,
Michael Zuckerman

[efriedma]

I don't have any specific issue with this patch (I don't do x86 benchmarking), but it would be a good idea to have some sort of record of what this is actually improving; if someone revisits this code in the future, they won't have access to Intel-internal benchmark numbers.

lib/Target/X86/X86ISelLowering.cpp

if (isPowerOf2_64(MulAmt2))
       NewMul = DAG.getNode(ISD::SHL, DL, VT, NewMul,
                            DAG.getConstant(Log2_64(MulAmt2), DL, MVT::i8));
     else
       NewMul = DAG.getNode(X86ISD::MUL_IMM, DL, VT, NewMul,
                            DAG.getConstant(MulAmt2, DL, VT));
   }
 
   if (!NewMul) {
-    assert(MulAmt != 0 && MulAmt != (VT == MVT::i64 ? UINT64_MAX : UINT32_MAX)
-           && "Both cases that could cause potential overflows should have "
-              "already been handled.");
-    if (isPowerOf2_64(MulAmt - 1))
+    assert(MulAmt != 0 &&
+           MulAmt != (VT == MVT::i64 ? UINT64_MAX : UINT32_MAX) &&
+           "Both cases that could cause potential overflows should have "
+    int64_t SignMulAmt = C->getSExtValue();
+    if ((SignMulAmt != INT64_MIN) && (SignMulAmt != INT64_MAX) &&
+        (SignMulAmt != -INT64_MAX)) {
+      int NumSign = SignMulAmt > 0 ? 1 : -1;
+      bool IsPowerOf2_64PlusOne = isPowerOf2_64(NumSign * SignMulAmt - 1);
+      bool IsPowerOf2_64MinusOne = isPowerOf2_64(NumSign * SignMulAmt + 1);
+      if (IsPowerOf2_64PlusOne) {
         // (mul x, 2^N + 1) => (add (shl x, N), x)
-      NewMul = DAG.getNode(ISD::ADD, DL, VT, N->getOperand(0),
-                                DAG.getNode(ISD::SHL, DL, VT, N->getOperand(0),
-                                DAG.getConstant(Log2_64(MulAmt - 1), DL,
+        NewMul = DAG.getNode(
+            ISD::ADD, DL, VT, N->getOperand(0),
+                        DAG.getConstant(Log2_64(NumSign * SignMulAmt - 1), DL,
                                         MVT::i8)));
-
-    else if (isPowerOf2_64(MulAmt + 1))
+      } else if (IsPowerOf2_64MinusOne) {
         // (mul x, 2^N - 1) => (sub (shl x, N), x)
-      NewMul = DAG.getNode(ISD::SUB, DL, VT, DAG.getNode(ISD::SHL, DL, VT,
-                                N->getOperand(0),
-                                DAG.getConstant(Log2_64(MulAmt + 1),
-                                DL, MVT::i8)), N->getOperand(0));
+        NewMul = DAG.getNode(
+            ISD::SUB, DL, VT,
+            DAG.getNode(ISD::SHL, DL, VT, N->getOperand(0),
+                        DAG.getConstant(Log2_64(NumSign * SignMulAmt + 1), DL,
+                                        MVT::i8)),
+            N->getOperand(0));
+      }
+      // To negate, subtract the number from zero
+      if ((IsPowerOf2_64PlusOne || IsPowerOf2_64PlusOne) && NumSign == -1)
+        NewMul =
+            DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), NewMul);
+    }
   }
 
   if (NewMul)
     // Do not add new nodes to DAG combiner worklist.
     DCI.CombineTo(N, NewMul, false);
 
   return SDValue();
 }

test/CodeGen/X86/imul.ll

 
 define i64 @mul18446744073709551615_64(i64 %A) {
 ; X64-LABEL: mul18446744073709551615_64:
 ; X64: negq %rdi
 ; X64-NEXT: movq  %rdi, %rax
     %mul = mul i64 %A, 18446744073709551615
     ret i64 %mul
 }
+
+define i32 @test(i32 %a) {
+; X64-LABEL: test:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    shll $5, %eax
+; X64-NEXT:    subl %edi, %eax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    shll $5, %eax
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i32 %a, 31
+  ret i32 %tmp3
+}
+
+define i32 @test1(i32 %a) {
+; X64-LABEL: test1:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    shll $5, %eax
+; X64-NEXT:    subl %edi, %eax
+; X64-NEXT:    negl %eax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test1:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    shll $5, %eax
+; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    negl %eax
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i32 %a, -31
+  ret i32 %tmp3
+}
+
+
+define i32 @test2(i32 %a) {
+; X64-LABEL: test2:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    shll $5, %eax
+; X64-NEXT:    leal (%rax,%rdi), %eax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test2:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    shll $5, %eax
+; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i32 %a, 33
+  ret i32 %tmp3
+}
+
+define i32 @test3(i32 %a) {
+; X64-LABEL: test3:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    shll $5, %eax
+; X64-NEXT:    leal (%rax,%rdi), %eax
+; X64-NEXT:    negl %eax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test3:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    shll $5, %eax
+; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    negl %eax
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i32 %a, -33
+  ret i32 %tmp3
+}
+
+define i64 @test4(i64 %a) {
+; X64-LABEL: test4:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    shlq $5, %rax
+; X64-NEXT:    subq %rdi, %rax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test4:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %eax, %ecx
+; X86-NEXT:    shll $5, %ecx
+; X86-NEXT:    subl %eax, %ecx
+; X86-NEXT:    movl $31, %eax
+; X86-NEXT:    mull {{[0-9]+}}(%esp)
+; X86-NEXT:    addl %ecx, %edx
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i64 %a, 31
+  ret i64 %tmp3
+}
+
+define i64 @test5(i64 %a) {
+; X64-LABEL: test5:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    shlq $5, %rax
+; X64-NEXT:    subq %rdi, %rax
+; X64-NEXT:    negq %rax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test5:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    pushl %esi
+; X86-NEXT:  .Lcfi0:
+; X86-NEXT:    .cfi_def_cfa_offset 8
+; X86-NEXT:  .Lcfi1:
+; X86-NEXT:    .cfi_offset %esi, -8
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %eax, %esi
+; X86-NEXT:    shll $5, %esi
+; X86-NEXT:    subl %eax, %esi
+; X86-NEXT:    movl $-31, %edx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    mull %edx
+; X86-NEXT:    subl %ecx, %edx
+; X86-NEXT:    subl %esi, %edx
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i64 %a, -31
+  ret i64 %tmp3
+}
+
+
+define i64 @test6(i64 %a) {
+; X64-LABEL: test6:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    shlq $5, %rax
+; X64-NEXT:    leaq (%rax,%rdi), %rax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test6:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %eax, %ecx
+; X86-NEXT:    shll $5, %ecx
+; X86-NEXT:    addl %eax, %ecx
+; X86-NEXT:    movl $33, %eax
+; X86-NEXT:    mull {{[0-9]+}}(%esp)
+; X86-NEXT:    addl %ecx, %edx
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i64 %a, 33
+  ret i64 %tmp3
+}
+
+define i64 @test7(i64 %a) {
+; X64-LABEL: test7:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    shlq $5, %rax
+; X64-NEXT:    leaq (%rax,%rdi), %rax
+; X64-NEXT:    negq %rax
+; X64-NEXT:    retq
+;
+; X86-LABEL: test7:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    pushl %esi
+; X86-NEXT:  .Lcfi2:
+; X86-NEXT:    .cfi_def_cfa_offset 8
+; X86-NEXT:  .Lcfi3:
+; X86-NEXT:    .cfi_offset %esi, -8
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl %eax, %esi
+; X86-NEXT:    shll $5, %esi
+; X86-NEXT:    addl %eax, %esi
+; X86-NEXT:    movl $-33, %edx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    mull %edx
+; X86-NEXT:    subl %ecx, %edx
+; X86-NEXT:    subl %esi, %edx
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i64 %a, -33
+  ret i64 %tmp3
+}
+
+define i64 @testOverflow(i64 %a) {
+; X64-LABEL: testOverflow:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movabsq $9223372036854775807, %rax # imm = 0x7FFFFFFFFFFFFFFF
+; X64-NEXT:    imulq %rdi, %rax
+; X64-NEXT:    retq
+;
+; X86-LABEL: testOverflow:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    pushl %esi
+; X86-NEXT:  .Lcfi4:
+; X86-NEXT:    .cfi_def_cfa_offset 8
+; X86-NEXT:  .Lcfi5:
+; X86-NEXT:    .cfi_offset %esi, -8
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl $-1, %edx
+; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    mull %edx
+; X86-NEXT:    movl %ecx, %esi
+; X86-NEXT:    shll $31, %esi
+; X86-NEXT:    subl %ecx, %esi
+; X86-NEXT:    addl %esi, %edx
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    popl %esi
+; X86-NEXT:    retl
+entry:
+  %tmp3 = mul i64 %a, 9223372036854775807
+  ret i64 %tmp3
+}