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

[Allen]

Summary

Change the costmodel to lower a = b * C where C = -(2^n - 2^m) to

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

[efriedma]

LGTM

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14836

Fix line wrapping?

[Allen]

Fix line wrapping

[Allen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14836

Done, thanks

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 = -6, -14 or even 45
-  // which equals to (1+2)*16-(1+2).
+  // TODO: lower more cases, e.g. C = 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.
     if (N0->hasOneUse() && (isSignExtended(N0.getNode(), DAG) ||
if (SCVMinus1.isPowerOf2()) {
       return Sub(Shl(N0, ShiftAmt), N0);
     } else if (SCVPlus1.isPowerOf2()) {
       ShiftAmt = SCVPlus1.logBase2() + TrailingZeroes;
       return Sub(Shl(N0, ShiftAmt), Shl(N0, TrailingZeroes));
     }
   } else {
     // (mul x, -(2^N - 1)) => (sub x, (shl x, N))
     // (mul x, -(2^N + 1)) => - (add (shl x, N), x)
+    // (mul x, -(2^(N-M) - 1) * 2^M) => (sub (shl x, M), (shl x, N))
+    APInt SCVPlus1 = -ShiftedConstValue + 1;
     APInt CVNegPlus1 = -ConstValue + 1;
     APInt CVNegMinus1 = -ConstValue - 1;
     if (CVNegPlus1.isPowerOf2()) {
       ShiftAmt = CVNegPlus1.logBase2();
       return Sub(N0, Shl(N0, ShiftAmt));
     } else if (CVNegMinus1.isPowerOf2()) {
       ShiftAmt = CVNegMinus1.logBase2();
       return Negate(Add(Shl(N0, ShiftAmt), N0));
+    } else if (SCVPlus1.isPowerOf2()) {
+      ShiftAmt = SCVPlus1.logBase2() + TrailingZeroes;
+      return Sub(Shl(N0, TrailingZeroes), Shl(N0, ShiftAmt));
     }
   }
 
   return SDValue();
 }
 
 static SDValue performVectorCompareAndMaskUnaryOpCombine(SDNode *N,
                                                          SelectionDAG &DAG) {

llvm/test/CodeGen/AArch64/mul_pow2.ll

 ; GISEL-NEXT:    ret
   %mul = mul nsw i32 %x, -5
   ret i32 %mul
 }
 
 define i32 @ntest6(i32 %x) {
 ; CHECK-LABEL: ntest6:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #-6
-; CHECK-NEXT:    mul w0, w0, w8
+; CHECK-NEXT:    lsl w8, w0, #1
+; CHECK-NEXT:    sub w0, w8, w0, lsl #3
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: ntest6:
 ; GISEL:       // %bb.0:
 ; GISEL-NEXT:    mov w8, #-6
 ; GISEL-NEXT:    mul w0, w0, w8
 ; GISEL-NEXT:    ret
 
; GISEL-NEXT:    ret
 
   %mul = mul nsw i32 %x, -11
   ret i32 %mul
 }
 
 define i32 @ntest12(i32 %x) {
 ; CHECK-LABEL: ntest12:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #-12
-; CHECK-NEXT:    mul w0, w0, w8
+; CHECK-NEXT:    lsl w8, w0, #2
+; CHECK-NEXT:    sub w0, w8, w0, lsl #4
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: ntest12:
 ; GISEL:       // %bb.0:
 ; GISEL-NEXT:    mov w8, #-12
 ; GISEL-NEXT:    mul w0, w0, w8
 ; GISEL-NEXT:    ret
 

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