[RISCV] Optimize multiplication in the zba extension with SH*ADD

[benshi001]

Summary

This patch make the following optimization.

(mul x, 3 * power_of_2) -> (SLLI (SH1ADD x, x), bits)
(mul x, 5 * power_of_2) -> (SLLI (SH2ADD x, x), bits)
(mul x, 9 * power_of_2) -> (SLLI (SH3ADD x, x), bits)

[benshi001]

The new optimization rules must be put before the following generic SH*ADD rules, otherwise the new optimization does not work.

def : Pat<(add (shl GPR:$rs1, (XLenVT 1)), non_imm12:$rs2),
          (SH1ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(add (shl GPR:$rs1, (XLenVT 2)), non_imm12:$rs2),
          (SH2ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(add (shl GPR:$rs1, (XLenVT 3)), non_imm12:$rs2),
          (SH3ADD GPR:$rs1, GPR:$rs2)>;

[benshi001]

For previous Pats, such as

def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 12)), GPR:$rs2),
          (SH2ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

The pattern (rs1*12 + rs2) no long existed after changes in decomposeMulByConstant(), so it has to be changed to

ParFrag<shadd ...>
def : Pat<(shadd GPR:$rs1, (XLenVT 1), (XLenVT 2), non_imm12:$rs2),
          (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

to preserve the previous optimization.

What's more, they must be put before the generic rs1*2+rs2->(shadd rs1, rs2) ones otherwise they can not be matched.

[jrtc27]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

993

To be, shadd means something like A << B + C, not A << B + A << C + D

[benshi001]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

993

change the ParFrag's name to addshl.

[LevyHsu]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

993

If I understand it correctly,
(shl node:$A, node:$B) matches (A<<B)
(shl node:$A, node:$C) matches (A<<C)
which makes the pattern like Jessica said: (A<<B) + (A<<C) + D

But on spec those patterns are:

uint_xlen_t sh1add(uint_xlen_t rs1, uint_xlen_t rs2)
{
return (rs1 << 1) + rs2;
}
uint_xlen_t sh2add(uint_xlen_t rs1, uint_xlen_t rs2)
{
return (rs1 << 2) + rs2;
}
uint_xlen_t sh3add(uint_xlen_t rs1, uint_xlen_t rs2)
{
return (rs1 << 3) + rs2;
}

[LevyHsu]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

993

Nevermind...missed the update

[benshi001]

I did not put the optimization of (mul x, 3 * power_of_2) in decomposeMulByConstant(). The reason is that using a PatLeaf is more simple than checking the pattern (ADD (SLLI), (SLLI).

[benshi001]

I change the $rs2 in the Pat from non_imm12 to GPR as following

def : Pat<(addshl GPR:$rs1, (XLenVT 1), (XLenVT 2), GPR:$rs2),
          (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

Because for a*6 + 10, non_imm12:$rs2 will lead to

addi Rb, zero, 6
mul Ra, Rb, Ra
addi Ra, Ra, 6

while GPR:$rs2 will lead to

addi Rb, zero, 10
sh1add Ra, Ra, Ra
sh1add Ra, Ra, Rb

And I think the later one is better, so I changed non_imm12:$rs2 to GPR:$rs2.

[craig.topper]

In D105796#2885104, @benshi001 wrote:

I change the $rs2 in the Pat from non_imm12 to GPR as following

def : Pat<(addshl GPR:$rs1, (XLenVT 1), (XLenVT 2), GPR:$rs2),
          (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

Because for a*6 + 10, non_imm12:$rs2 will lead to

addi Rb, zero, 6
mul Ra, Rb, Ra
addi Ra, Ra, 6

while GPR:$rs2 will lead to

addi Rb, zero, 10
sh1add Ra, Ra, Ra
sh1add Ra, Ra, Rb

And I think the later one is better, so I changed non_imm12:$rs2 to GPR:$rs2.

I'm not sure I follow this. How can a change to the isel pattern cause a mul to be created? Wasn't the mul already decomposed?

[benshi001]

This comment was removed by benshi001.

[benshi001]

In D105796#2885130, @craig.topper wrote:

In D105796#2885104, @benshi001 wrote:

I change the $rs2 in the Pat from non_imm12 to GPR as following

def : Pat<(addshl GPR:$rs1, (XLenVT 1), (XLenVT 2), GPR:$rs2),
          (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;

Because for a*6 + 10, non_imm12:$rs2 will lead to

addi Rb, zero, 6
mul Ra, Rb, Ra
addi Ra, Ra, 6

while GPR:$rs2 will lead to

addi Rb, zero, 10
sh1add Ra, Ra, Ra
sh1add Ra, Ra, Rb

And I think the later one is better, so I changed non_imm12:$rs2 to GPR:$rs2.

I'm not sure I follow this. How can a change to the isel pattern cause a mul to be created? Wasn't the mul already decomposed?

You are right. For non_imm12:$rs2 in a*10+6, the following is generated

slli    a1, a0, 1
sh3add  a0, a0, a1
addi    a0, a0, 6

For GPR:$rs2, the assembly is

sh2add  a0, a0, a0
addi    a1, zero, 6
sh1add  a0, a0, a1

I think maybe the first one is better, so I will rollback my patch.

[benshi001]

This comment was removed by benshi001.

[benshi001]

I have split previous patch to smaller ones, which would be easy to review. And current patch only contains

(mul x, 3 * power_of_2) -> (SLLI (SH1ADD x, x), bits)
(mul x, 5 * power_of_2) -> (SLLI (SH2ADD x, x), bits)
(mul x, 9 * power_of_2) -> (SLLI (SH3ADD x, x), bits)

[craig.topper]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

1016

Can we rename BSETINVTwoBitsMaskLow to TrailingZerosXForm?

[benshi001]

Do we need to change BSETINVTwoBitsMaskHigh to LeadingZerosXForm ?

[craig.topper]

In D105796#2895304, @benshi001 wrote:

Do we need to change BSETINVTwoBitsMaskHigh to LeadingZerosXForm ?

Since it does 63-leadingzeros i wouldn’t name it LeadingZerosXForm. You can leave it as is until we find another use for it.

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

if (!N->hasOneUse())
     return false;
   // The immediate should not be a simm12.
   if (isInt<12>(N->getSExtValue()))
     return false;
   // The immediate must have exactly two bits set.
   return countPopulation(N->getZExtValue()) == 2;
 }]>;
 
-def BSETINVTwoBitsMaskLow : SDNodeXForm<imm, [{
+def TrailingZerosXForm : SDNodeXForm<imm, [{
   uint64_t I = N->getZExtValue();
   return CurDAG->getTargetConstant(countTrailingZeros(I), SDLoc(N),
                                    N->getValueType(0));
 }]>;
 
 def BSETINVTwoBitsMaskHigh : SDNodeXForm<imm, [{
   uint64_t I = N->getZExtValue();
   return CurDAG->getTargetConstant(63 - countLeadingZeros(I), SDLoc(N),
def BCLRIANDIMask : PatLeaf<(imm), [{
   return Subtarget->is64Bit() ? isPowerOf2_64(~I) : isPowerOf2_32(~I);
 }]>;
 
 def BCLRIANDIMaskLow : SDNodeXForm<imm, [{
   return CurDAG->getTargetConstant((N->getZExtValue() & 0x7ff) | ~0x7ffull,
                                    SDLoc(N), N->getValueType(0));
 }]>;
 
+def C3LeftShift : PatLeaf<(imm), [{
+  uint64_t C = N->getZExtValue();
+  return C > 3 && ((C % 3) == 0) && isPowerOf2_64(C / 3);
+}]>;
+
+def C5LeftShift : PatLeaf<(imm), [{
+  uint64_t C = N->getZExtValue();
+  return C > 5 && ((C % 5) == 0) && isPowerOf2_64(C / 5);
+}]>;
+
+def C9LeftShift : PatLeaf<(imm), [{
+  uint64_t C = N->getZExtValue();
+  return C > 9 && ((C % 9) == 0) && isPowerOf2_64(C / 9);
+}]>;
+
 //===----------------------------------------------------------------------===//
 // Instruction class templates
 //===----------------------------------------------------------------------===//
 
 // Some of these templates should be moved to RISCVInstrFormats.td once the B
 // extension has been ratified.
 
 let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in
def : Pat<(or GPR:$rs1, BSETINVMask:$mask),
           (BSETI GPR:$rs1, BSETINVMask:$mask)>;
 def : Pat<(xor GPR:$rs1, BSETINVMask:$mask),
           (BINVI GPR:$rs1, BSETINVMask:$mask)>;
 
 def : Pat<(and (srl GPR:$rs1, uimmlog2xlen:$shamt), (XLenVT 1)),
           (BEXTI GPR:$rs1, uimmlog2xlen:$shamt)>;
 
 def : Pat<(or GPR:$r, BSETINVTwoBitsMask:$i),
-          (BSETI (BSETI GPR:$r, (BSETINVTwoBitsMaskLow BSETINVTwoBitsMask:$i)),
+          (BSETI (BSETI GPR:$r, (TrailingZerosXForm BSETINVTwoBitsMask:$i)),
                  (BSETINVTwoBitsMaskHigh BSETINVTwoBitsMask:$i))>;
 def : Pat<(xor GPR:$r, BSETINVTwoBitsMask:$i),
-          (BINVI (BINVI GPR:$r, (BSETINVTwoBitsMaskLow BSETINVTwoBitsMask:$i)),
+          (BINVI (BINVI GPR:$r, (TrailingZerosXForm BSETINVTwoBitsMask:$i)),
                  (BSETINVTwoBitsMaskHigh BSETINVTwoBitsMask:$i))>;
 def : Pat<(or GPR:$r, BSETINVORIMask:$i),
           (BSETI (ORI GPR:$r, (BSETINVORIMaskLow BSETINVORIMask:$i)),
                  (BSETINVTwoBitsMaskHigh BSETINVORIMask:$i))>;
 def : Pat<(xor GPR:$r, BSETINVORIMask:$i),
           (BINVI (XORI GPR:$r, (BSETINVORIMaskLow BSETINVORIMask:$i)),
                  (BSETINVTwoBitsMaskHigh BSETINVORIMask:$i))>;
 def : Pat<(and GPR:$r, BCLRITwoBitsMask:$i),

 }]>;
 
 let Predicates = [HasStdExtZba] in {
 def : Pat<(add (shl GPR:$rs1, (XLenVT 1)), non_imm12:$rs2),
           (SH1ADD GPR:$rs1, GPR:$rs2)>;
 def : Pat<(add (shl GPR:$rs1, (XLenVT 2)), non_imm12:$rs2),
           (SH2ADD GPR:$rs1, GPR:$rs2)>;
 def : Pat<(add (shl GPR:$rs1, (XLenVT 3)), non_imm12:$rs2),
           (SH3ADD GPR:$rs1, GPR:$rs2)>;
 
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 6)), GPR:$rs2),
           (SH1ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 10)), GPR:$rs2),
           (SH1ADD (SH2ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 18)), GPR:$rs2),
           (SH1ADD (SH3ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 12)), GPR:$rs2),
           (SH2ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 20)), GPR:$rs2),
           (SH2ADD (SH2ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 36)), GPR:$rs2),
           (SH2ADD (SH3ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 24)), GPR:$rs2),
           (SH3ADD (SH1ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 40)), GPR:$rs2),
           (SH3ADD (SH2ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
 def : Pat<(add (mul_oneuse GPR:$rs1, (XLenVT 72)), GPR:$rs2),
           (SH3ADD (SH3ADD GPR:$rs1, GPR:$rs1), GPR:$rs2)>;
+
+def : Pat<(mul GPR:$r, C3LeftShift:$i),
+          (SLLI (SH1ADD GPR:$r, GPR:$r),
+                (TrailingZerosXForm C3LeftShift:$i))>;
+def : Pat<(mul GPR:$r, C5LeftShift:$i),
+          (SLLI (SH2ADD GPR:$r, GPR:$r),
+                (TrailingZerosXForm C5LeftShift:$i))>;
+def : Pat<(mul GPR:$r, C9LeftShift:$i),
+          (SLLI (SH3ADD GPR:$r, GPR:$r),
+                (TrailingZerosXForm C9LeftShift:$i))>;
 } // Predicates = [HasStdExtZba]
 
 let Predicates = [HasStdExtZba, IsRV64] in {
 def : Pat<(i64 (shl (and GPR:$rs1, 0xFFFFFFFF), uimm5:$shamt)),
           (SLLIUW GPR:$rs1, uimm5:$shamt)>;
 def : Pat<(i64 (add (and GPR:$rs1, 0xFFFFFFFF), non_imm12:$rs2)),
           (ADDUW GPR:$rs1, GPR:$rs2)>;
 def : Pat<(i64 (and GPR:$rs, 0xFFFFFFFF)), (ADDUW GPR:$rs, X0)>;

llvm/test/CodeGen/RISCV/rv32zba.ll

 ; RV32I-LABEL: mul96:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    addi a1, zero, 96
 ; RV32I-NEXT:    mul a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32IB-LABEL: mul96:
 ; RV32IB:       # %bb.0:
-; RV32IB-NEXT:    addi a1, zero, 96
-; RV32IB-NEXT:    mul a0, a0, a1
+; RV32IB-NEXT:    sh1add a0, a0, a0
+; RV32IB-NEXT:    slli a0, a0, 5
 ; RV32IB-NEXT:    ret
 ;
 ; RV32IBA-LABEL: mul96:
 ; RV32IBA:       # %bb.0:
-; RV32IBA-NEXT:    addi a1, zero, 96
-; RV32IBA-NEXT:    mul a0, a0, a1
+; RV32IBA-NEXT:    sh1add a0, a0, a0
+; RV32IBA-NEXT:    slli a0, a0, 5
 ; RV32IBA-NEXT:    ret
   %c = mul i32 %a, 96
   ret i32 %c
 }
 
 define i32 @mul160(i32 %a) {
 ; RV32I-LABEL: mul160:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    addi a1, zero, 160
 ; RV32I-NEXT:    mul a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32IB-LABEL: mul160:
 ; RV32IB:       # %bb.0:
-; RV32IB-NEXT:    addi a1, zero, 160
-; RV32IB-NEXT:    mul a0, a0, a1
+; RV32IB-NEXT:    sh2add a0, a0, a0
+; RV32IB-NEXT:    slli a0, a0, 5
 ; RV32IB-NEXT:    ret
 ;
 ; RV32IBA-LABEL: mul160:
 ; RV32IBA:       # %bb.0:
-; RV32IBA-NEXT:    addi a1, zero, 160
-; RV32IBA-NEXT:    mul a0, a0, a1
+; RV32IBA-NEXT:    sh2add a0, a0, a0
+; RV32IBA-NEXT:    slli a0, a0, 5
 ; RV32IBA-NEXT:    ret
   %c = mul i32 %a, 160
   ret i32 %c
 }
 
 define i32 @mul288(i32 %a) {
 ; RV32I-LABEL: mul288:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    addi a1, zero, 288
 ; RV32I-NEXT:    mul a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32IB-LABEL: mul288:
 ; RV32IB:       # %bb.0:
-; RV32IB-NEXT:    addi a1, zero, 288
-; RV32IB-NEXT:    mul a0, a0, a1
+; RV32IB-NEXT:    sh3add a0, a0, a0
+; RV32IB-NEXT:    slli a0, a0, 5
 ; RV32IB-NEXT:    ret
 ;
 ; RV32IBA-LABEL: mul288:
 ; RV32IBA:       # %bb.0:
-; RV32IBA-NEXT:    addi a1, zero, 288
-; RV32IBA-NEXT:    mul a0, a0, a1
+; RV32IBA-NEXT:    sh3add a0, a0, a0
+; RV32IBA-NEXT:    slli a0, a0, 5
 ; RV32IBA-NEXT:    ret
   %c = mul i32 %a, 288
   ret i32 %c
 }
 
 define i32 @mul258(i32 %a) {
 ; RV32I-LABEL: mul258:
 ; RV32I:       # %bb.0:

llvm/test/CodeGen/RISCV/rv64zba.ll

 ; RV64I-LABEL: mul96:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    addi a1, zero, 96
 ; RV64I-NEXT:    mul a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64IB-LABEL: mul96:
 ; RV64IB:       # %bb.0:
-; RV64IB-NEXT:    addi a1, zero, 96
-; RV64IB-NEXT:    mul a0, a0, a1
+; RV64IB-NEXT:    sh1add a0, a0, a0
+; RV64IB-NEXT:    slli a0, a0, 5
 ; RV64IB-NEXT:    ret
 ;
 ; RV64IBA-LABEL: mul96:
 ; RV64IBA:       # %bb.0:
-; RV64IBA-NEXT:    addi a1, zero, 96
-; RV64IBA-NEXT:    mul a0, a0, a1
+; RV64IBA-NEXT:    sh1add a0, a0, a0
+; RV64IBA-NEXT:    slli a0, a0, 5
 ; RV64IBA-NEXT:    ret
   %c = mul i64 %a, 96
   ret i64 %c
 }
 
 define i64 @mul160(i64 %a) {
 ; RV64I-LABEL: mul160:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    addi a1, zero, 160
 ; RV64I-NEXT:    mul a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64IB-LABEL: mul160:
 ; RV64IB:       # %bb.0:
-; RV64IB-NEXT:    addi a1, zero, 160
-; RV64IB-NEXT:    mul a0, a0, a1
+; RV64IB-NEXT:    sh2add a0, a0, a0
+; RV64IB-NEXT:    slli a0, a0, 5
 ; RV64IB-NEXT:    ret
 ;
 ; RV64IBA-LABEL: mul160:
 ; RV64IBA:       # %bb.0:
-; RV64IBA-NEXT:    addi a1, zero, 160
-; RV64IBA-NEXT:    mul a0, a0, a1
+; RV64IBA-NEXT:    sh2add a0, a0, a0
+; RV64IBA-NEXT:    slli a0, a0, 5
 ; RV64IBA-NEXT:    ret
   %c = mul i64 %a, 160
   ret i64 %c
 }
 
 define i64 @mul288(i64 %a) {
 ; RV64I-LABEL: mul288:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    addi a1, zero, 288
 ; RV64I-NEXT:    mul a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64IB-LABEL: mul288:
 ; RV64IB:       # %bb.0:
-; RV64IB-NEXT:    addi a1, zero, 288
-; RV64IB-NEXT:    mul a0, a0, a1
+; RV64IB-NEXT:    sh3add a0, a0, a0
+; RV64IB-NEXT:    slli a0, a0, 5
 ; RV64IB-NEXT:    ret
 ;
 ; RV64IBA-LABEL: mul288:
 ; RV64IBA:       # %bb.0:
-; RV64IBA-NEXT:    addi a1, zero, 288
-; RV64IBA-NEXT:    mul a0, a0, a1
+; RV64IBA-NEXT:    sh3add a0, a0, a0
+; RV64IBA-NEXT:    slli a0, a0, 5
 ; RV64IBA-NEXT:    ret
   %c = mul i64 %a, 288
   ret i64 %c
 }
 
 define i64 @sh1add_imm(i64 %0) {
 ; RV64I-LABEL: sh1add_imm:
 ; RV64I:       # %bb.0: