[LoongArch] Optimize multiplication with immediates

[benshi001]

Summary

Optimize (mul x, imm) to (ADD (SLLI x, s0), (SLLI x, s1)) or
(SUB (SLLI x, s0), (SLLI x, s1)) if possible.

[benshi001]

ping ...

[SixWeining]

The changes LGTM except a nit in comments. Thanks.

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

3169

Seems this condition only applies to ADD but no SUB. For example, in below test, 65280 is 0xff00 which has 8 consecutive set bits.

[benshi001]

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

3169

Thanks. Fixed.

[SixWeining]

Thanks.

llvm/lib/Target/LoongArch/LoongArchISelLowering.cpp

if (auto *ConstNode = dyn_cast<ConstantSDNode>(C.getNode())) {
     if ((Imm + 1).isPowerOf2() || (Imm - 1).isPowerOf2() ||
         (1 - Imm).isPowerOf2() || (-1 - Imm).isPowerOf2())
       return true;
     // Break MUL into (ALSL x, (SLLI x, imm0), imm1).
     if (ConstNode->hasOneUse() &&
         ((Imm - 2).isPowerOf2() || (Imm - 4).isPowerOf2() ||
          (Imm - 8).isPowerOf2() || (Imm - 16).isPowerOf2()))
       return true;
+    // Break (MUL x, imm) into (ADD (SLLI x, s0), (SLLI x, s1)),
+    // in which the immediate has two set bits. Or Break (MUL x, imm)
+    // into (SUB (SLLI x, s0), (SLLI x, s1)), in which the immediate
+    // equals to (1 << s0) - (1 << s1).
+    if (ConstNode->hasOneUse() && !(Imm.sge(-2048) && Imm.sle(4095))) {
+      unsigned Shifts = Imm.countr_zero();
+      // Reject immediates which can be composed via a single LUI.
+      if (Shifts >= 12)
+        return false;
+      // Reject multiplications can be optimized to
+      // (SLLI (ALSL x, x, 1/2/3/4), s).
+      APInt ImmPop = Imm.ashr(Shifts);
+      if (ImmPop == 3 || ImmPop == 5 || ImmPop == 9 || ImmPop == 17)
+        return false;
+      // We do not consider the case `(-Imm - ImmSmall).isPowerOf2()`,
+      // since it needs one more instruction than other 3 cases.
+      APInt ImmSmall = APInt(Imm.getBitWidth(), 1 << Shifts, true);
+      if ((Imm - ImmSmall).isPowerOf2() || (Imm + ImmSmall).isPowerOf2() ||
+          (ImmSmall - Imm).isPowerOf2())
+        return true;
+    }
   }
 
   return false;
 }
 
 bool LoongArchTargetLowering::isLegalAddressingMode(const DataLayout &DL,
                                                     const AddrMode &AM,
                                                     Type *Ty, unsigned AS,

llvm/test/CodeGen/LoongArch/ir-instruction/mul.ll

 ; LA64-NEXT:    ret
   %b = mul i64 %a, 4352
   ret i64 %b
 }
 
 define signext i32 @mul_i32_65792(i32 %a) {
 ; LA32-LABEL: mul_i32_65792:
 ; LA32:       # %bb.0:
-; LA32-NEXT:    lu12i.w $a1, 16
-; LA32-NEXT:    ori $a1, $a1, 256
-; LA32-NEXT:    mul.w $a0, $a0, $a1
+; LA32-NEXT:    slli.w $a1, $a0, 8
+; LA32-NEXT:    slli.w $a0, $a0, 16
+; LA32-NEXT:    add.w $a0, $a0, $a1
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i32_65792:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, 16
-; LA64-NEXT:    ori $a1, $a1, 256
-; LA64-NEXT:    mul.d $a0, $a0, $a1
-; LA64-NEXT:    addi.w $a0, $a0, 0
+; LA64-NEXT:    slli.d $a1, $a0, 8
+; LA64-NEXT:    slli.d $a0, $a0, 16
+; LA64-NEXT:    add.w $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i32 %a, 65792
   ret i32 %b
 }
 
 define signext i32 @mul_i32_65280(i32 %a) {
 ; LA32-LABEL: mul_i32_65280:
 ; LA32:       # %bb.0:
-; LA32-NEXT:    lu12i.w $a1, 15
-; LA32-NEXT:    ori $a1, $a1, 3840
-; LA32-NEXT:    mul.w $a0, $a0, $a1
+; LA32-NEXT:    slli.w $a1, $a0, 8
+; LA32-NEXT:    slli.w $a0, $a0, 16
+; LA32-NEXT:    sub.w $a0, $a0, $a1
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i32_65280:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, 15
-; LA64-NEXT:    ori $a1, $a1, 3840
-; LA64-NEXT:    mul.d $a0, $a0, $a1
-; LA64-NEXT:    addi.w $a0, $a0, 0
+; LA64-NEXT:    slli.d $a1, $a0, 8
+; LA64-NEXT:    slli.d $a0, $a0, 16
+; LA64-NEXT:    sub.w $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i32 %a, 65280
   ret i32 %b
 }
 
 define signext i32 @mul_i32_minus_65280(i32 %a) {
 ; LA32-LABEL: mul_i32_minus_65280:
 ; LA32:       # %bb.0:
-; LA32-NEXT:    lu12i.w $a1, -16
-; LA32-NEXT:    ori $a1, $a1, 256
-; LA32-NEXT:    mul.w $a0, $a0, $a1
+; LA32-NEXT:    slli.w $a1, $a0, 16
+; LA32-NEXT:    slli.w $a0, $a0, 8
+; LA32-NEXT:    sub.w $a0, $a0, $a1
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i32_minus_65280:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, -16
-; LA64-NEXT:    ori $a1, $a1, 256
-; LA64-NEXT:    mul.d $a0, $a0, $a1
-; LA64-NEXT:    addi.w $a0, $a0, 0
+; LA64-NEXT:    slli.d $a1, $a0, 16
+; LA64-NEXT:    slli.d $a0, $a0, 8
+; LA64-NEXT:    sub.w $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i32 %a, -65280
   ret i32 %b
 }
 
 define i64 @mul_i64_65792(i64 %a) {
 ; LA32-LABEL: mul_i64_65792:
 ; LA32:       # %bb.0:
 ; LA32-NEXT:    lu12i.w $a2, 16
 ; LA32-NEXT:    ori $a2, $a2, 256
 ; LA32-NEXT:    mul.w $a1, $a1, $a2
 ; LA32-NEXT:    mulh.wu $a3, $a0, $a2
 ; LA32-NEXT:    add.w $a1, $a3, $a1
 ; LA32-NEXT:    mul.w $a0, $a0, $a2
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i64_65792:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, 16
-; LA64-NEXT:    ori $a1, $a1, 256
-; LA64-NEXT:    mul.d $a0, $a0, $a1
+; LA64-NEXT:    slli.d $a1, $a0, 8
+; LA64-NEXT:    slli.d $a0, $a0, 16
+; LA64-NEXT:    add.d $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i64 %a, 65792
   ret i64 %b
 }
 
 define i64 @mul_i64_65280(i64 %a) {
 ; LA32-LABEL: mul_i64_65280:
 ; LA32:       # %bb.0:
 ; LA32-NEXT:    lu12i.w $a2, 15
 ; LA32-NEXT:    ori $a2, $a2, 3840
 ; LA32-NEXT:    mul.w $a1, $a1, $a2
 ; LA32-NEXT:    mulh.wu $a3, $a0, $a2
 ; LA32-NEXT:    add.w $a1, $a3, $a1
 ; LA32-NEXT:    mul.w $a0, $a0, $a2
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i64_65280:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, 15
-; LA64-NEXT:    ori $a1, $a1, 3840
-; LA64-NEXT:    mul.d $a0, $a0, $a1
+; LA64-NEXT:    slli.d $a1, $a0, 8
+; LA64-NEXT:    slli.d $a0, $a0, 16
+; LA64-NEXT:    sub.d $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i64 %a, 65280
   ret i64 %b
 }
 
 define i64 @mul_i64_minus_65280(i64 %a) {
 ; LA32-LABEL: mul_i64_minus_65280:
 ; LA32:       # %bb.0:
 ; LA32-NEXT:    lu12i.w $a2, -16
 ; LA32-NEXT:    ori $a2, $a2, 256
 ; LA32-NEXT:    mul.w $a1, $a1, $a2
 ; LA32-NEXT:    mulh.wu $a3, $a0, $a2
 ; LA32-NEXT:    sub.w $a3, $a3, $a0
 ; LA32-NEXT:    add.w $a1, $a3, $a1
 ; LA32-NEXT:    mul.w $a0, $a0, $a2
 ; LA32-NEXT:    ret
 ;
 ; LA64-LABEL: mul_i64_minus_65280:
 ; LA64:       # %bb.0:
-; LA64-NEXT:    lu12i.w $a1, -16
-; LA64-NEXT:    ori $a1, $a1, 256
-; LA64-NEXT:    mul.d $a0, $a0, $a1
+; LA64-NEXT:    slli.d $a1, $a0, 16
+; LA64-NEXT:    slli.d $a0, $a0, 8
+; LA64-NEXT:    sub.d $a0, $a0, $a1
 ; LA64-NEXT:    ret
   %b = mul i64 %a, -65280
   ret i64 %b
 }
 
 ;; This multiplication is not transformed, due to
 ;; 1088 can be composed via a single ORI.
 define i64 @mul_i64_1088(i64 %a) {