[DAGCombiner] tighten constraints for fma fold

[spatel]

Summary

fadd (fma A, B, (fmul C, D)), E --> fma A, B, (fma C, D, E)

This is only allowed when "reassoc" is present on the fadd.

As discussed in D80801, this transform goes beyond what is allowed by "contract" FMF (-ffp-contract=fast). That is because we are fusing the trailing add of 'E' with a multiply, but without "reassoc", the code mandates that the products A*B and C*D are added together before adding in 'E'.

I've added this example to the LangRef to try to clarify the meaning of "contract". If that seems reasonable, we should probably do something similar for the clang docs because there does not appear to be any formal spec for the behavior of -ffp-contract=fast.

[spatel]

Ping.

[cameron.mcinally]

LGTM, but I encourage others to review too.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

11991

Do we need to check Aggressive here? For a hypothetical target with 2 FMUL/FADD ports and 1 FMA port, assuming slow FMAs, this could be a performance loss.

It shouldn't be a problem for modern chips that I care about, so just picking nits.

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

11991

Removing the 'Aggressive' clause was the previous patch. :)
D80801

The reason for not requiring 'Aggressive' is that using FMA on this case is what we should assume is the best case for a default target that supports FMA. As discussed in the earlier patch, we know that this is difficult to get right for all code sequences/targets, so there is already an opt-out to bypass this in SDAG and use MachineCombiner instead. Potentially, we could also transform patterns like this after they have been fused to FMA. That would again be in MachineCombiner (where we have the detailed scheduler info).

[cameron.mcinally]

Oops, missed that. Sorry.

Still LGTM.

[spatel]

Any other comments/feedback?

[qiucf]

Hi, I see reassoc and contract are equivalent in many cases (at least in DAG combiner):

define double @foo(double %a, double %b, double %c) {
entry:
  %0 = fmul reassoc double %a, %b
  %1 = fadd reassoc double %0, %c
  ret double %1
}
; => no contract bit, it's still fused into fma

define double @foo2(double %a, double %b) {
entry:
  %0 = fmul double %a, 1.1
  %1 = call contract double @llvm.fma.f64(double %0, double 2.1, double %b)
  ret double %1
}
; => no reassoc set, (fma (fmul x, c1), c2, y) became (fma x, c1*c2, y)

declare double @llvm.fma.f64(double, double, double)

Is this expected, or we need to differentiate them in more places?

[spatel]

In D82499#2329454, @qiucf wrote:

Hi, I see reassoc and contract are equivalent in many cases (at least in DAG combiner):

define double @foo(double %a, double %b, double %c) {
entry:
  %0 = fmul reassoc double %a, %b
  %1 = fadd reassoc double %0, %c
  ret double %1
}
; => no contract bit, it's still fused into fma

define double @foo2(double %a, double %b) {
entry:
  %0 = fmul double %a, 1.1
  %1 = call contract double @llvm.fma.f64(double %0, double 2.1, double %b)
  ret double %1
}
; => no reassoc set, (fma (fmul x, c1), c2, y) became (fma x, c1*c2, y)

declare double @llvm.fma.f64(double, double, double)

Is this expected, or we need to differentiate them in more places?

In the first example, I think of reassoc as including anything that contract could enable, so reassoc is a superset. If that's not the right model, we should adjust the documentation to allow the other interpretation. It does look like gcc makes some distinction between "unsafe" and FP-contraction, but it does not behave the way I was expecting:
https://godbolt.org/z/EfhPYT

The second example looks very similar to the bug we fixed with this patch: we are not allowed to reassociate the order of multiplications with contract alone, so that's a bug.
Let me know if I should post a patch for that or if you are already working on it.

[qiucf]

Let me know if I should post a patch for that or if you are already working on it.

Yes. I posted D89527.

It does look like gcc makes some distinction between "unsafe" and FP-contraction, but it does not behave the way I was expecting: https://godbolt.org/z/EfhPYT

The way compiler handles the option might be somewhat confusing: https://stackoverflow.com/questions/43352510 Besides, since GCC doesn't support pragma FP_CONTRACT (#pragma STDC FP_CONTRACT ON) well, -ffp-contract=on is equivalent to -ffp-contract=off in GCC. Clang looks to handle it correctly.

llvm/docs/LangRef.rst

``nsz``
    is poison and/or guaranteed to not exist in the operation.
 
 ``arcp``
    Allow Reciprocal - Allow optimizations to use the reciprocal of an
    argument rather than perform division.
 
 ``contract``
    Allow floating-point contraction (e.g. fusing a multiply followed by an
-   addition into a fused multiply-and-add).
+   addition into a fused multiply-and-add). This does not enable reassociating
+   to form arbitrary contractions. For example, ``(a*b) + (c*d) + e`` can not
+   be transformed into ``(a*b) + ((c*d) + e)`` to create two fma operations.
 
 ``afn``
    Approximate functions - Allow substitution of approximate calculations for
    functions (sin, log, sqrt, etc). See floating-point intrinsic definitions
    for places where this can apply to LLVM's intrinsic math functions.
 
 ``reassoc``
    Allow reassociation transformations for floating-point instructions.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool HasFMA =
       (!LegalOperations || TLI.isOperationLegalOrCustom(ISD::FMA, VT));
 
   // No valid opcode, do not combine.
   if (!HasFMAD && !HasFMA)
     return SDValue();
 
   SDNodeFlags Flags = N->getFlags();
   bool CanFuse = Options.UnsafeFPMath || isContractable(N);
+  bool CanReassociate =
+      Options.UnsafeFPMath || N->getFlags().hasAllowReassociation();
   bool AllowFusionGlobally = (Options.AllowFPOpFusion == FPOpFusion::Fast ||
                               CanFuse || HasFMAD);
   // If the addition is not contractable, do not combine.
   if (!AllowFusionGlobally && !isContractable(N))
     return SDValue();
 
   if (STI && STI->generateFMAsInMachineCombiner(OptLevel))
     return SDValue();
 
SDValue DAGCombiner::visitFADDForFMACombine(SDNode *N) {
   // Note: Commutes FADD operands.
   if (isContractableFMUL(N1) && (Aggressive || N1->hasOneUse())) {
     return DAG.getNode(PreferredFusedOpcode, SL, VT,
                        N1.getOperand(0), N1.getOperand(1), N0, Flags);
   }
 
   // fadd (fma A, B, (fmul C, D)), E --> fma A, B, (fma C, D, E)
   // fadd E, (fma A, B, (fmul C, D)) --> fma A, B, (fma C, D, E)
+  // This requires reassociation because it changes the order of operations.
   SDValue FMA, E;
-  if (CanFuse && N0.getOpcode() == PreferredFusedOpcode &&
+  if (CanReassociate && N0.getOpcode() == PreferredFusedOpcode &&
       N0.getOperand(2).getOpcode() == ISD::FMUL && N0.hasOneUse() &&
       N0.getOperand(2).hasOneUse()) {
     FMA = N0;
     E = N1;
-  } else if (CanFuse && N1.getOpcode() == PreferredFusedOpcode &&
+  } else if (CanReassociate && N1.getOpcode() == PreferredFusedOpcode &&
              N1.getOperand(2).getOpcode() == ISD::FMUL && N1.hasOneUse() &&
              N1.getOperand(2).hasOneUse()) {
     FMA = N1;
     E = N0;
   }
   if (FMA && E) {
     SDValue A = FMA.getOperand(0);
     SDValue B = FMA.getOperand(1);

llvm/test/CodeGen/AArch64/fadd-combines.ll

 ; CHECK-NEXT:    ret
   %m1 = fmul fast double %a, %b
   %m2 = fmul fast double %c, %d
   %a1 = fadd fast double %m1, %m2
   %a2 = fadd fast double %a1, %n1
   ret double %a2
 }
 
+; Minimum FMF - the 1st fadd is contracted because that combines
+; fmul+fadd as specified by the order of operations; the 2nd fadd
+; requires reassociation to fuse with c*d.
+
 define float @fadd_fma_fmul_fmf(float %a, float %b, float %c, float %d, float %n0) nounwind {
 ; CHECK-LABEL: fadd_fma_fmul_fmf:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    fmadd s2, s2, s3, s4
 ; CHECK-NEXT:    fmadd s0, s0, s1, s2
 ; CHECK-NEXT:    ret
   %m1 = fmul float %a, %b
   %m2 = fmul float %c, %d
   %a1 = fadd contract float %m1, %m2
   %a2 = fadd reassoc float %n0, %a1
   ret float %a2
 }
 
-; Minimum FMF, commute final add operands, change type.
+; Not minimum FMF.
 
 define float @fadd_fma_fmul_2(float %a, float %b, float %c, float %d, float %n0) nounwind {
 ; CHECK-LABEL: fadd_fma_fmul_2:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmadd s2, s2, s3, s4
+; CHECK-NEXT:    fmul s2, s2, s3
 ; CHECK-NEXT:    fmadd s0, s0, s1, s2
+; CHECK-NEXT:    fadd s0, s4, s0
 ; CHECK-NEXT:    ret
   %m1 = fmul float %a, %b
   %m2 = fmul float %c, %d
   %a1 = fadd contract float %m1, %m2
   %a2 = fadd contract float %n0, %a1
   ret float %a2
 }
 

llvm/test/CodeGen/X86/fma_patterns.ll

 ; AVX512-NEXT:    retq
   %m1 = fmul fast double %a, %b
   %m2 = fmul fast double %c, %d
   %a1 = fadd fast double %m1, %m2
   %a2 = fadd fast double %a1, %n1
   ret double %a2
 }
 
+; Minimum FMF - the 1st fadd is contracted because that combines
+; fmul+fadd as specified by the order of operations; the 2nd fadd
+; requires reassociation to fuse with c*d.
+
 define float @fadd_fma_fmul_fmf(float %a, float %b, float %c, float %d, float %n0) nounwind {
 ; FMA-LABEL: fadd_fma_fmul_fmf:
 ; FMA:       # %bb.0:
 ; FMA-NEXT:    vfmadd213ss {{.*#+}} xmm2 = (xmm3 * xmm2) + xmm4
 ; FMA-NEXT:    vfmadd213ss {{.*#+}} xmm0 = (xmm1 * xmm0) + xmm2
 ; FMA-NEXT:    retq
 ;
 ; FMA4-LABEL: fadd_fma_fmul_fmf:

 ; AVX512-NEXT:    retq
   %m1 = fmul float %a, %b
   %m2 = fmul float %c, %d
   %a1 = fadd contract float %m1, %m2
   %a2 = fadd reassoc float %n0, %a1
   ret float %a2
 }
 
-; Minimum FMF, commute final add operands, change type.
+; Not minimum FMF.
 
 define float @fadd_fma_fmul_2(float %a, float %b, float %c, float %d, float %n0) nounwind {
 ; FMA-LABEL: fadd_fma_fmul_2:
 ; FMA:       # %bb.0:
-; FMA-NEXT:    vfmadd213ss {{.*#+}} xmm2 = (xmm3 * xmm2) + xmm4
-; FMA-NEXT:    vfmadd213ss {{.*#+}} xmm0 = (xmm1 * xmm0) + xmm2
+; FMA-NEXT:    vmulss %xmm3, %xmm2, %xmm2
+; FMA-NEXT:    vfmadd231ss {{.*#+}} xmm2 = (xmm1 * xmm0) + xmm2
+; FMA-NEXT:    vaddss %xmm2, %xmm4, %xmm0
 ; FMA-NEXT:    retq
 ;
 ; FMA4-LABEL: fadd_fma_fmul_2:
 ; FMA4:       # %bb.0:
-; FMA4-NEXT:    vfmaddss {{.*#+}} xmm2 = (xmm2 * xmm3) + xmm4
+; FMA4-NEXT:    vmulss %xmm3, %xmm2, %xmm2
 ; FMA4-NEXT:    vfmaddss {{.*#+}} xmm0 = (xmm0 * xmm1) + xmm2
+; FMA4-NEXT:    vaddss %xmm0, %xmm4, %xmm0
 ; FMA4-NEXT:    retq
 ;
 ; AVX512-LABEL: fadd_fma_fmul_2:
 ; AVX512:       # %bb.0:
-; AVX512-NEXT:    vfmadd213ss {{.*#+}} xmm2 = (xmm3 * xmm2) + xmm4
-; AVX512-NEXT:    vfmadd213ss {{.*#+}} xmm0 = (xmm1 * xmm0) + xmm2
+; AVX512-NEXT:    vmulss %xmm3, %xmm2, %xmm2
+; AVX512-NEXT:    vfmadd231ss {{.*#+}} xmm2 = (xmm1 * xmm0) + xmm2
+; AVX512-NEXT:    vaddss %xmm2, %xmm4, %xmm0
 ; AVX512-NEXT:    retq
   %m1 = fmul float %a, %b
   %m2 = fmul float %c, %d
   %a1 = fadd contract float %m1, %m2
   %a2 = fadd contract float %n0, %a1
   ret float %a2
 }