[X86ISelLowering] Add additional support for multiplication-to-shift conversion.

[• chenli]

Summary

This patch adds support of conversion (mul x, 2^N + 1) => (add (shl x, N), x) and (mul x, 2^N - 1) => (sub (shl x, N), x) if the multiplication can not be converted to LEA + SHL or LEA + LEA. LLVM has already supported this on ARM, and it should also be useful on X86. Note the patch currently only applies to cases where the constant operand is positive, and I am planing to add another patch to support negative cases after this.

[RKSimon]

lib/Target/X86/X86ISelLowering.cpp

24313

There doesn't appear to be anything to prevent overflow here - e.g. for a 32-bit multiply by 0xFFFFFFFF. Do we need an initial patch that replaces the uint64_t MulAmt with APInt MulAmt?

[• chenli]

lib/Target/X86/X86ISelLowering.cpp

24313

I think you are correct. I can create a separate patch to replace uint64_t with APInt in this function.

[• chenli]

Add assertions to make sure overflow never happens.

[RKSimon]

LGTM - with a couple of minor diffs.

lib/Target/X86/X86ISelLowering.cpp

24307

Rephrase the assert message to make it clear that they are the cases that would involve overflow.

test/CodeGen/X86/imul.ll

150

Please add overflow test cases - I don't see them in this file although they maybe somewhere else?

151

Missing newline

lib/Target/X86/X86ISelLowering.cpp

if ((MulAmt % 9) == 0) {
     MulAmt2 = MulAmt / 9;
   } else if ((MulAmt % 5) == 0) {
     MulAmt1 = 5;
     MulAmt2 = MulAmt / 5;
   } else if ((MulAmt % 3) == 0) {
     MulAmt1 = 3;
     MulAmt2 = MulAmt / 3;
   }
+
+  SDLoc DL(N);
+  SDValue NewMul;
   if (MulAmt2 &&
       (isPowerOf2_64(MulAmt2) || MulAmt2 == 3 || MulAmt2 == 5 || MulAmt2 == 9)){
-    SDLoc DL(N);
 
     if (isPowerOf2_64(MulAmt2) &&
         !(N->hasOneUse() && N->use_begin()->getOpcode() == ISD::ADD))
       // If second multiplifer is pow2, issue it first. We want the multiply by
       // 3, 5, or 9 to be folded into the addressing mode unless the lone use
       // is an add.
       std::swap(MulAmt1, MulAmt2);
 
-    SDValue NewMul;
     if (isPowerOf2_64(MulAmt1))
       NewMul = DAG.getNode(ISD::SHL, DL, VT, N->getOperand(0),
                            DAG.getConstant(Log2_64(MulAmt1), DL, MVT::i8));
     else
       NewMul = DAG.getNode(X86ISD::MUL_IMM, DL, VT, N->getOperand(0),
                            DAG.getConstant(MulAmt1, DL, VT));
 
     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) {
+    if (isPowerOf2_64(MulAmt - 1))
+      // (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,
+                                MVT::i8)));
+
+    else if (isPowerOf2_64(MulAmt + 1))
+      // (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));
+  }
+
+  if (NewMul)
     // Do not add new nodes to DAG combiner worklist.
     DCI.CombineTo(N, NewMul, false);
-  }
+
   return SDValue();
 }
 
 static SDValue PerformSHLCombine(SDNode *N, SelectionDAG &DAG) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
   EVT VT = N0.getValueType();

test/CodeGen/X86/imul.ll

 define i32 @mul40_32_minsize(i32 %A) minsize {
 ; X64-LABEL: mul40_32_minsize:
 ; X64: imull
 ; X86-LABEL: mul40_32_minsize:
 ; X86: imull
     %mul = mul i32 %A, 40
     ret i32 %mul
 }
+
+define i32 @mul33_32(i32 %A) {
+; X64-LABEL: mul33_32:
+; X64: shll
+; X64-NEXT: leal
+; X86-LABEL: mul33_32:
+; X86: shll
+; X86-NEXT: addl
+    %mul = mul i32 %A, 33
+    ret i32 %mul
+}
+
+define i32 @mul31_32(i32 %A) {
+; X64-LABEL: mul31_32:
+; X64: shll
+; X64-NEXT: subl
+; X86-LABEL: mul31_32:
+; X86: shll
+; X86-NEXT: subl
+    %mul = mul i32 %A, 31
+    ret i32 %mul
+}
 No newline at end of file