[MachineCombiner][RISCV] Support inverse instructions reassociation

[asi-sc]

Summary

This patch adds reassociation of FADD/FSUB instruction pairs.

[asi-sc]

This patch is created to demonstrate the approach. So, I'm intentionally didn't add reviewers. However, it's possible that we'll follow the path this patch shows, so I don't abandon it immediately.

[asi-sc]

sync changes with parent revision, rebase

[asi-sc]

Add tests to cover fadd/fsub reassociation; rebase

[asi-sc]

Since we've moved RISCV reassociation implementation to generic machine combiner mechanism D138302 and added reassociation of inverse instructions to machine combiner in D136754, we now can enable reassociation of inverse for RISCV.

Performance measurements for Whetstone

N1 +8%
N2 +14%

Baseline

Loop content                  Result              MFLOPS      MOPS   Seconds

N1 floating point     -1.12398255667391900       284.545              0.694
N2 floating point     -1.12187079889295083       224.314              6.162
N3 if then else        1.00000000000000000                5715.791    0.186
N4 fixed point        12.00000000000000000               323977497.600    0.000
N5 sin,cos etc.        0.49902937281518078                  20.796   41.147
N6 floating point      0.99999987890802811       169.611             32.708
N7 assignments         3.00000000000000000                7136.783    0.266
N8 exp,sqrt etc.       0.75100163018453681                  21.396   17.882

MWIPS  
                                         1038.403             99.046
This patch

Loop content                  Result              MFLOPS      MOPS   Seconds

N1 floating point     -1.12398255667392588       308.002              0.652
N2 floating point     -1.12187079889289487       257.436              5.460
N3 if then else        1.00000000000000000                5714.154    0.189
N4 fixed point        12.00000000000000000               299507735.273    0.000
N5 sin,cos etc.        0.49902937281518078                  20.861   41.714
N6 floating point      0.99999987890802811       170.068             33.173
N7 assignments         3.00000000000000000                7176.013    0.269
N8 exp,sqrt etc.       0.75100163018453681                  21.117   18.425

MWIPS                                           1047.136             99.882

Compilation flags -O3 -funroll-loops -finline-functions -ffast-math -mtune=sifive-u74

[asi-sc]

A gentle ping.

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVInstrInfo.h

void genAlternativeCodeSequence(
       DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const override;
 
   bool hasReassociableSibling(const MachineInstr &Inst,
                               bool &Commuted) const override;
 
   bool isAssociativeAndCommutative(const MachineInstr &Inst,
                                    bool Invert) const override;
 
+  std::optional<unsigned> getInverseOpcode(unsigned Opcode) const override;
+
 protected:
   const RISCVSubtarget &STI;
 };
 
 namespace RISCV {
 
 // Returns true if this is the sext.w pattern, addiw rd, rs1, 0.
 bool isSEXT_W(const MachineInstr &MI);

llvm/lib/Target/RISCV/RISCVInstrInfo.cpp

const MachineInstr &Sibling =
       *MRI.getVRegDef(Inst.getOperand(OperandIdx).getReg());
 
   return RISCV::hasEqualFRM(Inst, Sibling);
 }
 
 bool RISCVInstrInfo::isAssociativeAndCommutative(const MachineInstr &Inst,
                                                  bool Invert) const {
   unsigned Opc = Inst.getOpcode();
-  if (Invert)
+  if (Invert) {
+    auto InverseOpcode = getInverseOpcode(Opc);
+    if (!InverseOpcode)
       return false;
+    Opc = *InverseOpcode;
+  }
 
   if (isFADD(Opc) || isFMUL(Opc))
     return Inst.getFlag(MachineInstr::MIFlag::FmReassoc) &&
            Inst.getFlag(MachineInstr::MIFlag::FmNsz);
   return false;
 }
 
+std::optional<unsigned>
+RISCVInstrInfo::getInverseOpcode(unsigned Opcode) const {
+  switch (Opcode) {
+  default:
+    return std::nullopt;
+  case RISCV::FADD_H:
+    return RISCV::FSUB_H;
+  case RISCV::FADD_S:
+    return RISCV::FSUB_S;
+  case RISCV::FADD_D:
+    return RISCV::FSUB_D;
+  case RISCV::FSUB_H:
+    return RISCV::FADD_H;
+  case RISCV::FSUB_S:
+    return RISCV::FADD_S;
+  case RISCV::FSUB_D:
+    return RISCV::FADD_D;
+  }
+}
+
 static bool canCombineFPFusedMultiply(const MachineInstr &Root,
                                       const MachineOperand &MO,
                                       bool DoRegPressureReduce) {
   if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
     return false;
   const MachineRegisterInfo &MRI = Root.getMF()->getRegInfo();
   MachineInstr *MI = MRI.getVRegDef(MO.getReg());
   if (!MI || !isFMUL(MI->getOpcode()))

llvm/test/CodeGen/RISCV/machine-combiner.ll

; CHECK-NEXT:    ret
   %t4 = fadd nsz reassoc double %t3, %a5
   %t5 = fadd nsz reassoc double %t4, %a6
   ret double %t5
 }
 
 define double @test_reassoc_big2(double %a0, double %a1, i32 %a2, double %a3, i32 %a4, double %a5) {
 ; CHECK-LABEL: test_reassoc_big2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    fcvt.d.w ft0, a0
-; CHECK-NEXT:    fcvt.d.w ft1, a1
-; CHECK-NEXT:    fmul.d ft0, fa2, ft0
-; CHECK-NEXT:    fmul.d ft1, ft1, fa1
-; CHECK-NEXT:    fadd.d ft2, fa0, fa1
-; CHECK-NEXT:    fadd.d ft3, fa2, fa1
-; CHECK-NEXT:    fmul.d ft0, ft1, ft0
-; CHECK-NEXT:    fadd.d ft1, fa2, ft2
-; CHECK-NEXT:    fmul.d ft2, fa0, ft3
-; CHECK-NEXT:    fsub.d ft1, fa3, ft1
-; CHECK-NEXT:    fmul.d ft0, ft0, ft2
-; CHECK-NEXT:    fmul.d fa0, ft1, ft0
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa3, fa2
+; CHECK-NEXT:    fadd.d ft2, fa2, fa1
+; CHECK-NEXT:    fcvt.d.w ft3, a0
+; CHECK-NEXT:    fcvt.d.w ft4, a1
+; CHECK-NEXT:    fmul.d ft3, fa2, ft3
+; CHECK-NEXT:    fmul.d ft4, ft4, fa1
+; CHECK-NEXT:    fsub.d ft0, ft1, ft0
+; CHECK-NEXT:    fmul.d ft1, fa0, ft2
+; CHECK-NEXT:    fmul.d ft2, ft4, ft3
+; CHECK-NEXT:    fmul.d ft0, ft0, ft1
+; CHECK-NEXT:    fmul.d fa0, ft0, ft2
 ; CHECK-NEXT:    ret
   %cvt1 = sitofp i32 %a2 to double
   %cvt2 = sitofp i32 %a4 to double
   %t5 = fmul nsz reassoc double %a3, %cvt1
   %t9 = fmul nsz reassoc double %cvt2, %t5
   %t4 = fmul nsz reassoc double %t9, %a1
   %t0 = fadd nsz reassoc double %a0, %a1
   %t1 = fadd nsz reassoc double %a3, %t0

 ; CHECK-NEXT:    fnmsub.d ft1, fa0, fa1, fa2
 ; CHECK-NEXT:    fdiv.d fa0, ft1, ft0
 ; CHECK-NEXT:    ret
   %t0 = fmul contract double %a0, %a1
   %t1 = fsub contract double %a2, %t0
   %t2 = fdiv double %t1, %t0
   ret double %t2
 }
+
+define double @test_reassoc_fsub1(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub1:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa2, fa3
+; CHECK-NEXT:    fadd.d fa0, ft0, ft1
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fadd nsz reassoc double %t0, %a2
+  %t2 = fsub nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub2(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa2, fa3
+; CHECK-NEXT:    fsub.d fa0, ft0, ft1
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %t0, %a2
+  %t2 = fadd nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub3(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub3:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fadd.d ft1, fa2, fa3
+; CHECK-NEXT:    fsub.d fa0, ft0, ft1
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %t0, %a2
+  %t2 = fsub nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub4(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub4:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa2, fa3
+; CHECK-NEXT:    fadd.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fadd nsz reassoc double %a2, %t0
+  %t2 = fsub nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub5(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub5:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fadd.d ft1, fa2, fa3
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %a2, %t0
+  %t2 = fadd nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub6(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub6:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa2, fa3
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %a2, %t0
+  %t2 = fsub nsz reassoc double %t1, %a3
+  ret double %t2
+}
+
+define double @test_reassoc_fsub7(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub7:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa3, fa2
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fadd nsz reassoc double %t0, %a2
+  %t2 = fsub nsz reassoc double %a3, %t1
+  ret double %t2
+}
+
+define double @test_reassoc_fsub8(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub8:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa3, fa2
+; CHECK-NEXT:    fadd.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %t0, %a2
+  %t2 = fadd nsz reassoc double %a3, %t1
+  ret double %t2
+}
+
+define double @test_reassoc_fsub9(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub9:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fadd.d ft1, fa3, fa2
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %t0, %a2
+  %t2 = fsub nsz reassoc double %a3, %t1
+  ret double %t2
+}
+
+define double @test_reassoc_fsub10(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub10:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa3, fa2
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fadd nsz reassoc double %a2, %t0
+  %t2 = fsub nsz reassoc double %a3, %t1
+  ret double %t2
+}
+
+define double @test_reassoc_fsub11(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub11:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fadd.d ft1, fa3, fa2
+; CHECK-NEXT:    fsub.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %a2, %t0
+  %t2 = fadd nsz reassoc double %a3, %t1
+  ret double %t2
+}
+
+define double @test_reassoc_fsub12(double %a0, double %a1, double %a2, double %a3) {
+; CHECK-LABEL: test_reassoc_fsub12:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    fadd.d ft0, fa0, fa1
+; CHECK-NEXT:    fsub.d ft1, fa3, fa2
+; CHECK-NEXT:    fadd.d fa0, ft1, ft0
+; CHECK-NEXT:    ret
+  %t0 = fadd nsz reassoc double %a0, %a1
+  %t1 = fsub nsz reassoc double %a2, %t0
+  %t2 = fsub nsz reassoc double %a3, %t1
+  ret double %t2
+}