[AArch64] Lower multiplication by a constant int to shl+sub+shl

[Allen]

Summary

Decompose the const 14 can be separated from D132322
Change the costmodel to lower a = b * C where C = 2^n - 2^m to

lsl     w8, w0, n
sub     w0, w8, w0, lsl m

[efriedma]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14849

The use of all these booleans makes the actual code generation difficult to understand.

Maybe we can simplify with a few lambdas? Name them Shl, Add, Sub, Negate. Then for each case, write out the operations explicitly. For example, in this case, instead of setting AddSubOpc and Sub2Shift, you can write return Sub(Shl(N0, ShiftAmt), Shl(N0, TrailingZeroes)).

[Allen]

address commit, using Lambda

[efriedma]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14832

Since the shift amount is always a constant here, might as well put the call to DAG.getConstant() inside the Shl lambda.

LLVM coding guidelines say you should avoid using "auto" when it's easy to spell out the type.

[Allen]

address comment

[Allen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14832

Done, thanks for your suggestion

[efriedma]

LGTM

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

static SDValue performMulCombine(SDNode *N, SelectionDAG &DAG,
   // Multiplication of a power of two plus/minus one can be done more
   // cheaply as as shift+add/sub. For now, this is true unilaterally. If
   // future CPUs have a cheaper MADD instruction, this may need to be
   // gated on a subtarget feature. For Cyclone, 32-bit MADD is 4 cycles and
   // 64-bit is 5 cycles, so this is always a win.
   // More aggressively, some multiplications N0 * C can be lowered to
   // shift+add+shift if the constant C = A * B where A = 2^N + 1 and B = 2^M,
   // e.g. 6=3*2=(2+1)*2.
-  // TODO: consider lowering more cases, e.g. C = 14, -6, -14 or even 45
+  // TODO: consider lowering more cases, e.g. C = -6, -14 or even 45
   // which equals to (1+2)*16-(1+2).
 
   // TrailingZeroes is used to test if the mul can be lowered to
   // shift+add+shift.
   unsigned TrailingZeroes = ConstValue.countTrailingZeros();
   if (TrailingZeroes) {
     // Conservatively do not lower to shift+add+shift if the mul might be
     // folded into smul or umul.
static SDValue performMulCombine(SDNode *N, SelectionDAG &DAG,
   // and shift+add+shift.
   APInt ShiftedConstValue = ConstValue.ashr(TrailingZeroes);
 
   unsigned ShiftAmt;
   // Is the shifted value the LHS operand of the add/sub?
   bool ShiftValUseIsN0 = true;
   // Do we need to negate the result?
   bool NegateResult = false;
+  // Is the sub has 2 shifted value operands?
+  bool Sub2Shift = false;
 
   if (ConstValue.isNonNegative()) {
     // (mul x, 2^N + 1) => (add (shl x, N), x)
     // (mul x, 2^N - 1) => (sub (shl x, N), x)
     // (mul x, (2^N + 1) * 2^M) => (shl (add (shl x, N), x), M)
+    // (mul x, (2^(N-M) - 1) * 2^M) => (sub (shl x, N), (shl x, M))
     APInt SCVMinus1 = ShiftedConstValue - 1;
+    APInt SCVPlus1 = ShiftedConstValue + 1;
     APInt CVPlus1 = ConstValue + 1;
     if (SCVMinus1.isPowerOf2()) {
       ShiftAmt = SCVMinus1.logBase2();
       AddSubOpc = ISD::ADD;
     } else if (CVPlus1.isPowerOf2()) {
       ShiftAmt = CVPlus1.logBase2();
       AddSubOpc = ISD::SUB;
+    } else if (SCVPlus1.isPowerOf2()) {
+      ShiftAmt = SCVPlus1.logBase2() + TrailingZeroes;
+      AddSubOpc = ISD::SUB;
+      Sub2Shift = true;
     } else
       return SDValue();
   } else {
     // (mul x, -(2^N - 1)) => (sub x, (shl x, N))
     // (mul x, -(2^N + 1)) => - (add (shl x, N), x)
     APInt CVNegPlus1 = -ConstValue + 1;
     APInt CVNegMinus1 = -ConstValue - 1;
     if (CVNegPlus1.isPowerOf2()) {
       ShiftAmt = CVNegPlus1.logBase2();
       AddSubOpc = ISD::SUB;
       ShiftValUseIsN0 = false;
     } else if (CVNegMinus1.isPowerOf2()) {
       ShiftAmt = CVNegMinus1.logBase2();
       AddSubOpc = ISD::ADD;
       NegateResult = true;
     } else
       return SDValue();
   }
 
-  SDValue ShiftedVal = DAG.getNode(ISD::SHL, DL, VT, N0,
+  SDValue ShiftedVal0 = DAG.getNode(ISD::SHL, DL, VT, N0,
                                     DAG.getConstant(ShiftAmt, DL, MVT::i64));
-
-  SDValue AddSubN0 = ShiftValUseIsN0 ? ShiftedVal : N0;
-  SDValue AddSubN1 = ShiftValUseIsN0 ? N0 : ShiftedVal;
+  if (Sub2Shift) {
+    SDValue ShiftedVal1 = DAG.getNode(
+        ISD::SHL, DL, VT, N0, DAG.getConstant(TrailingZeroes, DL, MVT::i64));
+    return DAG.getNode(ISD::SUB, DL, VT, ShiftedVal0, ShiftedVal1);
+  }
+  SDValue AddSubN0 = ShiftValUseIsN0 ? ShiftedVal0 : N0;
+  SDValue AddSubN1 = ShiftValUseIsN0 ? N0 : ShiftedVal0;
   SDValue Res = DAG.getNode(AddSubOpc, DL, VT, AddSubN0, AddSubN1);
   assert(!(NegateResult && TrailingZeroes) &&
          "NegateResult and TrailingZeroes cannot both be true for now.");
   // Negate the result.
   if (NegateResult)
     return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), Res);
   // Shift the result.
   if (TrailingZeroes)

llvm/test/CodeGen/AArch64/mul_pow2.ll

; GISEL-NEXT:    ret
 
   %mul = mul nsw i32 %x, 13
   ret i32 %mul
 }
 
 define i32 @test14(i32 %x) {
 ; CHECK-LABEL: test14:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #14
-; CHECK-NEXT:    mul w0, w0, w8
+; CHECK-NEXT:    lsl w8, w0, #4
+; CHECK-NEXT:    sub w0, w8, w0, lsl #1
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: test14:
 ; GISEL:       // %bb.0:
 ; GISEL-NEXT:    mov w8, #14
 ; GISEL-NEXT:    mul w0, w0, w8
 ; GISEL-NEXT:    ret