[X86] Reduce some 32-bit imuls into lea + shift

[mkuper]

Summary

The existing code only performs the transformation for imulq on 64-bit platforms. It makes as much sense to make it for imull, on both 32-bit and 64-bit.
It looks like there's some additional clean-up needed, as well as additional patterns, but that'll go into a separate review.

Also extended the test to cover more cases.

[nadav]

LGTM.

llvm/trunk/lib/Target/X86/X86ISelLowering.cpp

   setTargetDAGCombine(ISD::ANY_EXTEND);
   setTargetDAGCombine(ISD::SIGN_EXTEND);
   setTargetDAGCombine(ISD::SIGN_EXTEND_INREG);
   setTargetDAGCombine(ISD::TRUNCATE);
   setTargetDAGCombine(ISD::SINT_TO_FP);
   setTargetDAGCombine(ISD::SETCC);
   setTargetDAGCombine(ISD::INTRINSIC_WO_CHAIN);
   setTargetDAGCombine(ISD::BUILD_VECTOR);
-  if (Subtarget->is64Bit())
-    setTargetDAGCombine(ISD::MUL);
   setTargetDAGCombine(ISD::XOR);
 
   computeRegisterProperties();
 
   // On Darwin, -Os means optimize for size without hurting performance,
   // do not reduce the limit.
   MaxStoresPerMemset = 16; // For @llvm.memset -> sequence of stores
   MaxStoresPerMemsetOptSize = Subtarget->isTargetDarwin() ? 16 : 8;

 /// in order to implement it with two cheaper instructions, e.g.
 /// LEA + SHL, LEA + LEA.
 static SDValue PerformMulCombine(SDNode *N, SelectionDAG &DAG,
                                  TargetLowering::DAGCombinerInfo &DCI) {
   if (DCI.isBeforeLegalize() || DCI.isCalledByLegalizer())
     return SDValue();
 
   EVT VT = N->getValueType(0);
-  if (VT != MVT::i64)
+  if (VT != MVT::i64 && VT != MVT::i32)
     return SDValue();
 
   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
   if (!C)
     return SDValue();
   uint64_t MulAmt = C->getZExtValue();
   if (isPowerOf2_64(MulAmt) || MulAmt == 3 || MulAmt == 5 || MulAmt == 9)
     return SDValue();

llvm/trunk/test/CodeGen/X86/imul.ll

+; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu | FileCheck %s --check-prefix=X64
+; RUN: llc < %s -mtriple=x86_64-pc-linux-gnux32 | FileCheck %s --check-prefix=X64
+; RUN: llc < %s -mtriple=i686-pc-linux | FileCheck %s --check-prefix=X86
+
+define i32 @mul4_32(i32 %A) {
+; X64-LABEL: mul4_32:
+; X64: leal
+; X86-LABEL: mul4_32:
+; X86: shll
+    %mul = mul i32 %A, 4
+    ret i32 %mul
+}
+
+define i64 @mul4_64(i64 %A) {
+; X64-LABEL: mul4_64:
+; X64: leaq
+; X86-LABEL: mul4_64:
+; X86: shldl
+; X86: shll
+    %mul = mul i64 %A, 4
+    ret i64 %mul
+}
+
+define i32 @mul4096_32(i32 %A) {
+; X64-LABEL: mul4096_32:
+; X64: shll
+; X86-LABEL: mul4096_32:
+; X86: shll
+    %mul = mul i32 %A, 4096
+    ret i32 %mul
+}
+
+define i64 @mul4096_64(i64 %A) {
+; X64-LABEL: mul4096_64:
+; X64: shlq
+; X86-LABEL: mul4096_64:
+; X86: shldl
+; X86: shll
+    %mul = mul i64 %A, 4096
+    ret i64 %mul
+}
+
+define i32 @mulmin4096_32(i32 %A) {
+; X64-LABEL: mulmin4096_32:
+; X64: shll
+; X64-NEXT: negl
+; X86-LABEL: mulmin4096_32:
+; X86: shll
+; X86-NEXT: negl
+    %mul = mul i32 %A, -4096
+    ret i32 %mul
+}
+
+define i64 @mulmin4096_64(i64 %A) {
+; X64-LABEL: mulmin4096_64:
+; X64: shlq
+; X64-NEXT: negq
+; X86-LABEL: mulmin4096_64:
+; X86: shldl
+; X86-NEXT: shll
+; X86-NEXT: xorl
+; X86-NEXT: negl
+; X86-NEXT: sbbl
+    %mul = mul i64 %A, -4096
+    ret i64 %mul
+}
+
+define i32 @mul3_32(i32 %A) {
+; X64-LABEL: mul3_32:
+; X64: leal
+; X86-LABEL: mul3_32:
+; But why?!
+; X86: imull
+    %mul = mul i32 %A, 3
+    ret i32 %mul
+}
+
+define i64 @mul3_64(i64 %A) {
+; X64-LABEL: mul3_64:
+; X64: leaq
+; X86-LABEL: mul3_64:
+; X86: mull
+; X86-NEXT: imull
+    %mul = mul i64 %A, 3
+    ret i64 %mul
+}
+
+define i32 @mul40_32(i32 %A) {
+; X64-LABEL: mul40_32:
+; X64: shll
+; X64-NEXT: leal
+; X86-LABEL: mul40_32:
+; X86: shll
+; X86-NEXT: leal
+    %mul = mul i32 %A, 40
+    ret i32 %mul
+}
+
+define i64 @mul40_64(i64 %A) {
+; X64-LABEL: mul40_64:
+; X64: shlq
+; X64-NEXT: leaq
+; X86-LABEL: mul40_64:
+; X86: leal
+; X86-NEXT: movl
+; X86-NEXT: mull
+; X86-NEXT: leal
+    %mul = mul i64 %A, 40
+    ret i64 %mul
+}

llvm/trunk/test/CodeGen/X86/imul64-lea.ll

-; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu | FileCheck %s
-; RUN: llc < %s -mtriple=x86_64-pc-linux-gnux32 | FileCheck %s
-
-; Test that 64-bit LEAs are generated for both LP64 and ILP32 in 64-bit mode.
-declare i64 @foo64()
-
-define i64 @test64() {
-  %tmp.0 = tail call i64 @foo64( )
-  %tmp.1 = mul i64 %tmp.0, 9
-; CHECK-NOT: mul
-; CHECK: leaq
-  ret i64 %tmp.1
-}
-
-; Test that 32-bit LEAs are generated for both LP64 and ILP32 in 64-bit mode.
-declare i32 @foo32()
-
-define i32 @test32() {
-  %tmp.0 = tail call i32 @foo32( )
-  %tmp.1 = mul i32 %tmp.0, 9
-; CHECK-NOT: mul
-; CHECK: leal
-  ret i32 %tmp.1
-}
-

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/ivchain-X86.ll

 ; X64: lea
 ; X64: lea
 ; X64: %loop
 ; complex address modes
 ; X64: (%{{[^)]+}},%{{[^)]+}},
 ;
 ; X32: @user
 ; expensive address computation in the preheader
-; X32: imul
+; X32: shll $4
+; X32: lea
+; X32: lea
 ; X32: %loop
 ; complex address modes
 ; X32: (%{{[^)]+}},%{{[^)]+}},
 define i32 @user(i32* %a, i32* %b, i32 %x) nounwind {
 entry:
   br label %loop
 loop:
   %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ]