[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

14854

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

14830

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

14830

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,
   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;
 
+  auto Shl = [&](auto N0, auto N1) {
+    return DAG.getNode(ISD::SHL, DL, VT, N0, N1);
+  };
+  auto Sub = [&](auto N0, auto N1) {
+    return DAG.getNode(ISD::SUB, DL, VT, N0, N1);
+  };
+
   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;
+      return Sub(Shl(N0, DAG.getConstant(ShiftAmt, DL, MVT::i64)),
+                 Shl(N0, DAG.getConstant(TrailingZeroes, DL, MVT::i64)));
     } 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,
-                                   DAG.getConstant(ShiftAmt, DL, MVT::i64));
-
-  SDValue AddSubN0 = ShiftValUseIsN0 ? ShiftedVal : N0;
-  SDValue AddSubN1 = ShiftValUseIsN0 ? N0 : ShiftedVal;
+  SDValue ShiftedVal0 = Shl(N0, DAG.getConstant(ShiftAmt, DL, MVT::i64));
+  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);
+    return Sub(DAG.getConstant(0, DL, VT), Res);
   // Shift the result.
   if (TrailingZeroes)
-    return DAG.getNode(ISD::SHL, DL, VT, Res,
-                       DAG.getConstant(TrailingZeroes, DL, MVT::i64));
+    return Shl(Res, DAG.getConstant(TrailingZeroes, DL, MVT::i64));
   return Res;
 }
 
 static SDValue performVectorCompareAndMaskUnaryOpCombine(SDNode *N,
                                                          SelectionDAG &DAG) {
   // Take advantage of vector comparisons producing 0 or -1 in each lane to
   // optimize away operation when it's from a constant.
   //

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