[RISCV] Add isel pattern to optimize (mul (and X, 0xffffffff), (and Y, 0xffffffff)) on RV64

[craig.topper]

Summary

This patterns computes the full 64 bit product of a 32x32 unsigned
multiply. This requires a two pairs of SLLI+SRLI to zero the
upper 32 bits of the inputs.

We can do better than this by using two SLLI to move the lower
bits to the upper bits then use MULHU to compute the product. This
is the high half of a full 64x64 product. Since we put 32 0s in the lower
bits of the inputs we know the 128-bit product will have zeros in the
lower 64 bits. So the upper 64 bits, which MULHU computes, will contain
the original 64 bit product we were after.

The same trick would work for (mul (sext_inreg X, i32), (sext_inreg Y, i32)) using MULHS, but sext_inreg
is sext.w which is already one instruction so we wouldn't save anything.

[jrtc27]

I think the final line of your commit message is the wrong way round?

[craig.topper]

In D99026#2639787, @jrtc27 wrote:

I think the final line of your commit message is the wrong way round?

Maybe it was poorly written. How does it look now?

[jrtc27]

In D99026#2639788, @craig.topper wrote:

In D99026#2639787, @jrtc27 wrote:

I think the final line of your commit message is the wrong way round?

Maybe it was poorly written. How does it look now?

Ah that makes more sense, I misunderstood what your point was

[craig.topper]

In D99026#2639790, @jrtc27 wrote:

In D99026#2639788, @craig.topper wrote:

In D99026#2639787, @jrtc27 wrote:

I think the final line of your commit message is the wrong way round?

Maybe it was poorly written. How does it look now?

Ah that makes more sense, I misunderstood what your point was

I guess maybe we shouldn’t do this with Zba which has zext.w. Unless we know the ‘and’ is only used by the mul.

llvm/lib/Target/RISCV/RISCVInstrInfoM.td

def : Pat<(and (riscv_remuw (assertzexti32 GPR:$rs1),
                             (assertzexti32 GPR:$rs2)), 0xffffffff),
           (REMU GPR:$rs1, GPR:$rs2)>;
 
 // Although the sexti32 operands may not have originated from an i32 srem,
 // this pattern is safe as it is impossible for two sign extended inputs to
 // produce a result where res[63:32]=0 and res[31]=1.
 def : Pat<(srem (sexti32 (i64 GPR:$rs1)), (sexti32 (i64 GPR:$rs2))),
           (REMW GPR:$rs1, GPR:$rs2)>;
+
+// Special case for calculating the full 64-bit product of a 32x32 unsigned
+// multiply where the inputs aren't known to be zero extended. We can shift the
+// inputs left by 32 and use a MULHU. This saves two SRLIs needed to finish
+// zeroing the upper 32 bits.
+// TODO: If one of the operands is zero extended and the other isn't, we might
+// still be better off shifting both left by 32.
+def : Pat<(i64 (mul (and GPR:$rs1, 0xffffffff), (and GPR:$rs2, 0xffffffff))),
+          (MULHU (SLLI GPR:$rs1, 32), (SLLI GPR:$rs2, 32))>;
 } // Predicates = [HasStdExtM, IsRV64]

llvm/test/CodeGen/RISCV/rv64i-w-insts-legalization.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv64 -mattr=+m -verify-machineinstrs < %s | FileCheck %s
 
 define signext i32 @addw(i32 signext %s, i32 signext %n, i32 signext %k) nounwind {
 ; CHECK-LABEL: addw:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    bge a0, a1, .LBB0_2
 ; CHECK-NEXT:  # %bb.1: # %for.body.preheader
 ; CHECK-NEXT:    not a2, a0
 ; CHECK-NEXT:    add a2, a2, a1
 ; CHECK-NEXT:    addi a3, a0, 1
 ; CHECK-NEXT:    mul a3, a2, a3
-; CHECK-NEXT:    slli a2, a2, 32
-; CHECK-NEXT:    srli a2, a2, 32
 ; CHECK-NEXT:    sub a1, a1, a0
 ; CHECK-NEXT:    addi a1, a1, -2
 ; CHECK-NEXT:    slli a1, a1, 32
-; CHECK-NEXT:    srli a1, a1, 32
-; CHECK-NEXT:    mul a1, a2, a1
+; CHECK-NEXT:    slli a2, a2, 32
+; CHECK-NEXT:    mulhu a1, a2, a1
 ; CHECK-NEXT:    srli a1, a1, 1
 ; CHECK-NEXT:    add a0, a3, a0
 ; CHECK-NEXT:    addw a0, a0, a1
 ; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB0_2:
 ; CHECK-NEXT:    mv a0, zero
 ; CHECK-NEXT:    ret
 entry:

 define signext i32 @subw(i32 signext %s, i32 signext %n, i32 signext %k) nounwind {
 ; CHECK-LABEL: subw:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    bge a0, a1, .LBB1_2
 ; CHECK-NEXT:  # %bb.1: # %for.body.preheader
 ; CHECK-NEXT:    not a2, a0
 ; CHECK-NEXT:    add a3, a2, a1
 ; CHECK-NEXT:    mul a2, a3, a2
-; CHECK-NEXT:    slli a3, a3, 32
-; CHECK-NEXT:    srli a3, a3, 32
 ; CHECK-NEXT:    sub a1, a1, a0
 ; CHECK-NEXT:    addi a1, a1, -2
 ; CHECK-NEXT:    slli a1, a1, 32
-; CHECK-NEXT:    srli a1, a1, 32
-; CHECK-NEXT:    mul a1, a3, a1
+; CHECK-NEXT:    slli a3, a3, 32
+; CHECK-NEXT:    mulhu a1, a3, a1
 ; CHECK-NEXT:    srli a1, a1, 1
 ; CHECK-NEXT:    sub a0, a2, a0
 ; CHECK-NEXT:    subw a0, a0, a1
 ; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB1_2:
 ; CHECK-NEXT:    mv a0, zero
 ; CHECK-NEXT:    ret
 entry:

llvm/test/CodeGen/RISCV/xaluo.ll

 ; RV32-NEXT:    mul a0, a0, a1
 ; RV32-NEXT:    sw a0, 0(a2)
 ; RV32-NEXT:    mv a0, a3
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: umulo.i32:
 ; RV64:       # %bb.0: # %entry
 ; RV64-NEXT:    slli a1, a1, 32
-; RV64-NEXT:    srli a1, a1, 32
 ; RV64-NEXT:    slli a0, a0, 32
-; RV64-NEXT:    srli a0, a0, 32
-; RV64-NEXT:    mul a1, a0, a1
+; RV64-NEXT:    mulhu a1, a0, a1
 ; RV64-NEXT:    srli a0, a1, 32
 ; RV64-NEXT:    snez a0, a0
 ; RV64-NEXT:    sw a1, 0(a2)
 ; RV64-NEXT:    ret
 entry:
   %t = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %v1, i32 %v2)
   %val = extractvalue {i32, i1} %t, 0
   %obit = extractvalue {i32, i1} %t, 1

 ; RV32-NEXT:  # %bb.1: # %entry
 ; RV32-NEXT:    mv a0, a1
 ; RV32-NEXT:  .LBB42_2: # %entry
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: umulo.select.i32:
 ; RV64:       # %bb.0: # %entry
 ; RV64-NEXT:    slli a2, a1, 32
-; RV64-NEXT:    srli a2, a2, 32
 ; RV64-NEXT:    slli a3, a0, 32
-; RV64-NEXT:    srli a3, a3, 32
-; RV64-NEXT:    mul a2, a3, a2
+; RV64-NEXT:    mulhu a2, a3, a2
 ; RV64-NEXT:    srli a2, a2, 32
 ; RV64-NEXT:    bnez a2, .LBB42_2
 ; RV64-NEXT:  # %bb.1: # %entry
 ; RV64-NEXT:    mv a0, a1
 ; RV64-NEXT:  .LBB42_2: # %entry
 ; RV64-NEXT:    ret
 entry:
   %t = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
 define i1 @umulo.not.i32(i32 %v1, i32 %v2) {
 ; RV32-LABEL: umulo.not.i32:
 ; RV32:       # %bb.0: # %entry
 ; RV32-NEXT:    mulhu a0, a0, a1
 ; RV32-NEXT:    seqz a0, a0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: umulo.not.i32:
 ; RV64:       # %bb.0: # %entry
 ; RV64-NEXT:    slli a1, a1, 32
-; RV64-NEXT:    srli a1, a1, 32
 ; RV64-NEXT:    slli a0, a0, 32
-; RV64-NEXT:    srli a0, a0, 32
-; RV64-NEXT:    mul a0, a0, a1
+; RV64-NEXT:    mulhu a0, a0, a1
 ; RV64-NEXT:    srli a0, a0, 32
 ; RV64-NEXT:    seqz a0, a0
 ; RV64-NEXT:    ret
 entry:
   %t = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = xor i1 %obit, true
   ret i1 %ret

 ; RV32-NEXT:    ret
 ; RV32-NEXT:  .LBB57_2: # %continue
 ; RV32-NEXT:    addi a0, zero, 1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: umulo.br.i32:
 ; RV64:       # %bb.0: # %entry
 ; RV64-NEXT:    slli a1, a1, 32
-; RV64-NEXT:    srli a1, a1, 32
 ; RV64-NEXT:    slli a0, a0, 32
-; RV64-NEXT:    srli a0, a0, 32
-; RV64-NEXT:    mul a0, a0, a1
+; RV64-NEXT:    mulhu a0, a0, a1
 ; RV64-NEXT:    srli a0, a0, 32
 ; RV64-NEXT:    beqz a0, .LBB57_2
 ; RV64-NEXT:  # %bb.1: # %overflow
 ; RV64-NEXT:    mv a0, zero
 ; RV64-NEXT:    ret
 ; RV64-NEXT:  .LBB57_2: # %continue
 ; RV64-NEXT:    addi a0, zero, 1
 ; RV64-NEXT:    ret