[ISel] Enable generating more fma instructions.

[tsymalla]

Summary

This patch changes a FADD / FMUL => FMA ISel pattern implemented
in D80801 so that it peeks through more than one FMA.

[foad]

llvm/test/CodeGen/AMDGPU/dagcombine-fma-fmad.ll

178

Please precommit the new tests and rebase, so the patch shows the codegen diff.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14178

This seems to be a more limited case of your new reassociation, so can we remove this code now?

14219

I don't understand the logic here. What do copies and extracts have to do with reassociating fmuls and fadds?

[foad]

See the comment on D80801: "The fold implemented here is actually a specialization - we should be able to peek through >1 fma to find this pattern. That's another patch if we want to try that enhancement though." That's what you are implementing here.

[tsymalla]

Rebase.

[tsymalla]

This changes a FADD / FMUL => FMA ISel pattern implemented
in D80801 so that it peeks through more than one FMA. This also
changes the order of the operands, which can help with eliminating
a final COPY.

[tsymalla]

Did not update the lit tests for other targets yet (CodeGen/AArch64/fadd-combines.ll, CodeGen/PowerPC/fma-assoc.ll, CodeGen/PowerPC/machine-combiner.ll, CodeGen/X86/fma_patterns.ll) because I wanted to get some opinion on the change in the operand order first.

[arsenm]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14208

Why use UpdateNodeOperands here instead of just constructing the new node normally?

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14181

Remove "on"?

14182–14184

Looks like clang-format has mangled this comment!

14186–14211

Can you explain this? It is not at all obvious. Are you sure it's not just random? Perhaps it helps your case, but could harm other cases?

[tsymalla]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14186–14211

When keeping the order

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

The compiler will assign the result of the inner FMA to a new (virtual) register which will be used by the outer FMA.
The outer FMA will write its output to the same virtual register which will, in the simple example (fmac_sequence_simple) cause a COPY to the first available register at the end.
Finally, the register allocator will try recoloring the registers.
This output register (in this case, %6) will be marked as recolorizable and assigned to the first available register. As the outer FMA is using %0 and % 1 (a and b), it can only assign to %2, which is in this case v2.
During virtual register rewriting, the compiler will now try to eliminate identity copies. Even if the final copy is regarded as candidate for deletion, it cannot do so because the COPY is used by the final SI_RETURN. So, this generates a superfluous V_MOV at the end.

By changing the operand order, we get following changes:
The multiplicand operand order of the innermost and the outermost FMA is swapped. So, innermost uses %0 and %1 and outermost uses %2 and %3. So, the compiler is able to assign %6 (output of outermost FMA) to $vgpr0 because the register is not used inside the outermost FMA (only in the innermost FMA).
By this, the final COPY can be eliminated because it's essentially a identity copy, removing the final V_MOV.

Changing the instruction order in the DAG basically frees up the desired output register for the register allocator.

I cannot assume this causes harm for other cases, but from fast-math point of view it should not cause any issues. Looking at the (currently failing) test cases, I don't see any actual issues, but please correct me if I'm wrong.

[tsymalla]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14208

This is updating the innermost FMA node which already exists, I am just replacing the last operand of it.
The newly created node is the FMA node in NewFMA:

Example steps:

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

1. NewFMA = fma_o (C, D, fma_i (A, B, fmul(C, D)))
2. fma_i = fma (A, B, E)
=> NewFMA = fma (C, D, fma (A, B, E))

More complex case:

fadd (fma_i0 A, B, (fma (C, D, (fmul (E, F))))), G:
1. TmpFMA = fma_i = fma (C, D, (fmul (E, F))))
2. NewFMA = fma (E, F, fma_i0) = fma (E, F, fma (A, B, fma (C, D, (fmul (E, F))))) (construct outermost FMA)
3. TmpFMA.UpdateNodeOperands: fma_i = fma (C, D, (fmul (E, F)) => fma (C, D, G) => fma (E, F, fma (A, B, fma (C, D, (fmul (E, F))))) = fma (E, F, fma (A, B, fma (C, D, G))) (replace innermost FMA operand with addition operator of the initial FADD)

I can create a new node for the innermost FMA, but isn't UpdateNodeOperands being used for such cases?

[tsymalla]

Addressed comments, added a few comments and updated X86, AArch64, PowerPC
tests.y

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14186–14211

https://reviews.llvm.org/differential/diff/460688/ adds a couple of variations of PPC test cases. All I have done is swapped the operands of the "fadd %F, %G" instruction. If you apply your patch on top of this you will see that the codegen gets worse for these cases, in exactly the same way that it got better for the existing tests. So I do not agree that changing the order of the fmas is a good thing in general.

Because of this, I would prefer to keep the existing order of the fmas. That makes the combine simpler because you only have to mutate the fmul to an fma, and remove the fadd. You don't have to change the existing fmas at all.

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

1 ↗

(On Diff #460670)

Please do this as a separate patch and then rebase this patch on it.

[tsymalla]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14186–14211

Agreed. Thanks for constructing the tests.
However, in this example, the number of instructions (fma_innermost test) will not decrease due to the addition of the v_mov instead of constructing the return value in-place.
I don't think this will negatively affect real-life examples (but I'll check), but for the sake of code quality, we could try getting rid of these moves probably at some other place.

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

1 ↗

(On Diff #460670)

These will be removed again in the next diff.

[tsymalla]

Once more, change the algorithm to keep the operands in order
Use node morphing instead of updating the node operands.

[foad]

I think the patch looks good now, but I am a little confused by the test changes: one of them now uses fmac instead of mac, and the other uses mad instead of fma.

Also could you add another version of fmac_sequence_innermost_fmul to show that it still works if you swap the operands of the outermost fadd?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14197

You don't need to test TmpFMA here. Optionally, this loop could be rewritten as:

if (E) {
  do {
    ...
  } while (isFusedOp(TmpFMA));
}

[RKSimon]

Are you ready to include the changes on other targets?

[foad]

In D132837#3802595, @foad wrote:

I am a little confused by the test changes: one of them now uses fmac instead of mac, and the other uses mad instead of fma.

This is not your fault and need not block the patch. The choice of fma vs fmad depends on whether the combiner is running pre- or post-legalization, and it is a bit random because the pre-legalization combiner does not always re-run combines on new nodes that it creates, so some stuff is (wrongly) left for the post-legalizer combiner to clean up.

[tsymalla]

Remove TmpFMA check, add additional test.

[foad]

LGTM, thanks!

[tsymalla]

In D132837#3805144, @foad wrote:

LGTM, thanks!

Thanks for reviewing!

[foad]

In D132837#3802978, @foad wrote:

In D132837#3802595, @foad wrote:

I am a little confused by the test changes: one of them now uses fmac instead of mac, and the other uses mad instead of fma.

This is not your fault and need not block the patch. The choice of fma vs fmad depends on whether the combiner is running pre- or post-legalization, and it is a bit random because the pre-legalization combiner does not always re-run combines on new nodes that it creates, so some stuff is (wrongly) left for the post-legalizer combiner to clean up.

@deadalnix @RKSimon I debugged this to a case where running the pre-legalization combiner twice in a row would do extra combines that a single pass missed, and D127115 did not help. Is this to be expected? Is it worth debugging more to work out exactly why some combines were missed the first time?

[spatel]

Note that there's a gray area for fast-math-flags with transforms like this: we generally just check FMF on the final value in the sequence to determine if the fold is allowed.
I haven't seen many examples of mixed FMF in practice, but front-ends are becoming more flexible about that via pragma or other decorations, so I added a couple of AArch64 tests to demonstrate current behavior:
ddd27a3d3934

If this patch is reverted for some reason, those tests will need to be updated.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitFADDForFMACombine(SDNode *N) {
 
   // fold (fadd x, (fmul y, z)) -> (fma y, z, x)
   // Note: Commutes FADD operands.
   if (isContractableFMUL(N1) && (Aggressive || N1->hasOneUse())) {
     return DAG.getNode(PreferredFusedOpcode, SL, VT, N1.getOperand(0),
                        N1.getOperand(1), N0);
   }
 
   // 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 also works with nested fma instructions:
+  // fadd (fma A, B, (fma (C, D, (fmul (E, F))))), G -->
+  // fma A, B, (fma C, D, fma (E, F, G))
+  // fadd (G, (fma A, B, (fma (C, D, (fmul (E, F)))))) -->
+  // fma A, B, (fma C, D, fma (E, F, G)).
   // This requires reassociation because it changes the order of operations.
+  if (CanReassociate) {
     SDValue FMA, E;
-  if (CanReassociate && isFusedOp(N0) &&
-      N0.getOperand(2).getOpcode() == ISD::FMUL && N0.hasOneUse() &&
-      N0.getOperand(2).hasOneUse()) {
+    if (isFusedOp(N0) && N0.hasOneUse()) {
       FMA = N0;
       E = N1;
-  } else if (CanReassociate && isFusedOp(N1) &&
-             N1.getOperand(2).getOpcode() == ISD::FMUL && N1.hasOneUse() &&
-             N1.getOperand(2).hasOneUse()) {
+    } else if (isFusedOp(N1) && N1.hasOneUse()) {
       FMA = N1;
       E = N0;
     }
-  if (FMA && E) {
-    SDValue A = FMA.getOperand(0);
-    SDValue B = FMA.getOperand(1);
-    SDValue C = FMA.getOperand(2).getOperand(0);
-    SDValue D = FMA.getOperand(2).getOperand(1);
-    SDValue CDE = DAG.getNode(PreferredFusedOpcode, SL, VT, C, D, E);
-    return DAG.getNode(PreferredFusedOpcode, SL, VT, A, B, CDE);
+
+    SDValue TmpFMA = FMA;
+    while (E && isFusedOp(TmpFMA)) {
+      SDValue FMul = TmpFMA->getOperand(2);
+      if (FMul.getOpcode() == ISD::FMUL && FMul.hasOneUse()) {
+        SDValue C = FMul.getOperand(0);
+        SDValue D = FMul.getOperand(1);
+
+        DAG.MorphNodeTo(FMul.getNode(), PreferredFusedOpcode, FMul->getVTList(),
+                        {C, D, E});
+
+        return FMA;
+      }
+
+      TmpFMA = TmpFMA->getOperand(2);
+    }
   }
 
   // Look through FP_EXTEND nodes to do more combining.
 
   // fold (fadd (fpext (fmul x, y)), z) -> (fma (fpext x), (fpext y), z)
   if (N0.getOpcode() == ISD::FP_EXTEND) {
     SDValue N00 = N0.getOperand(0);
     if (isContractableFMUL(N00) &&
         TLI.isFPExtFoldable(DAG, PreferredFusedOpcode, VT,
                             N00.getValueType())) {
       return DAG.getNode(PreferredFusedOpcode, SL, VT,
                          DAG.getNode(ISD::FP_EXTEND, SL, VT, N00.getOperand(0)),
                          DAG.getNode(ISD::FP_EXTEND, SL, VT, N00.getOperand(1)),
                          N1);
     }
   }
 

llvm/test/CodeGen/AMDGPU/dagcombine-fma-fmad.ll

 ; GCN-NEXT:    v_max_f32_e64 v6, s0, s0 clamp
 ; GCN-NEXT:    v_add_f32_e64 v5, s29, -1.0
 ; GCN-NEXT:    v_sub_f32_e32 v8, s0, v1
 ; GCN-NEXT:    v_fma_f32 v7, -s2, v6, s6
 ; GCN-NEXT:    v_fma_f32 v5, v6, v5, 1.0
 ; GCN-NEXT:    v_mad_f32 v10, s2, v6, v2
 ; GCN-NEXT:    s_mov_b32 s0, 0x3c23d70a
 ; GCN-NEXT:    v_fmac_f32_e32 v1, v6, v8
-; GCN-NEXT:    v_mac_f32_e32 v10, v7, v6
+; GCN-NEXT:    v_fmac_f32_e32 v10, v7, v6
 ; GCN-NEXT:    s_waitcnt lgkmcnt(0)
 ; GCN-NEXT:    v_mul_f32_e32 v9, s10, v0
 ; GCN-NEXT:    v_fma_f32 v0, -v0, s10, s14
 ; GCN-NEXT:    v_mul_f32_e32 v8, s18, v2
 ; GCN-NEXT:    v_mul_f32_e32 v3, s22, v3
 ; GCN-NEXT:    v_fmac_f32_e32 v9, v0, v6
 ; GCN-NEXT:    v_sub_f32_e32 v0, v1, v5
 ; GCN-NEXT:    v_mul_f32_e32 v1, v8, v6
.entry:
   %.i2539 = fmul reassoc nnan nsz arcp contract afn float %.i2536, %4
   %.i2542 = fadd reassoc nnan nsz arcp contract afn float %.i2488, %.i2539
   %.i2545 = fmul reassoc nnan nsz arcp contract afn float %.i2525, %.i2542
   %.i2548 = fadd reassoc nnan nsz arcp contract afn float %.i2469, %.i2545
   %.i2551 = call reassoc nnan nsz arcp contract afn float @llvm.maxnum.f32(float %.i2548, float 0.000000e+00)
   ret float %.i2551
 }
 
 define float @fmac_sequence_simple(float %a, float %b, float %c, float %d, float %e) #0 {
 ; GCN-LABEL: fmac_sequence_simple:
 ; GCN:       ; %bb.0:
 ; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; GCN-NEXT:    s_waitcnt_vscnt null, 0x0
 ; GCN-NEXT:    v_fma_f32 v2, v2, v3, v4
 ; GCN-NEXT:    v_fmac_f32_e32 v2, v0, v1
 ; GCN-NEXT:    v_mov_b32_e32 v0, v2
 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %t0 = fmul fast float %a, %b
   %t1 = fmul fast float %c, %d
   %t2 = fadd fast float %t0, %t1
   %t5 = fadd fast float %t2, %e
   ret float %t5
 }
 
 define float @fmac_sequence_innermost_fmul(float %a, float %b, float %c, float %d, float %e, float %f, float %g) #0 {
 ; GCN-LABEL: fmac_sequence_innermost_fmul:
 ; GCN:       ; %bb.0:
 ; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; GCN-NEXT:    s_waitcnt_vscnt null, 0x0
-; GCN-NEXT:    v_mul_f32_e32 v2, v2, v3
+; GCN-NEXT:    v_mad_f32 v2, v2, v3, v6
 ; GCN-NEXT:    v_fmac_f32_e32 v2, v0, v1
 ; GCN-NEXT:    v_fmac_f32_e32 v2, v4, v5
-; GCN-NEXT:    v_add_f32_e32 v0, v2, v6
+; GCN-NEXT:    v_mov_b32_e32 v0, v2
 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %t0 = fmul fast float %a, %b
   %t1 = fmul fast float %c, %d
   %t2 = fadd fast float %t0, %t1
   %t3 = fmul fast float %e, %f
   %t4 = fadd fast float %t2, %t3
   %t5 = fadd fast float %t4, %g
   ret float %t5
 }
 
 define float @fmac_sequence_innermost_fmul_swapped_operands(float %a, float %b, float %c, float %d, float %e, float %f, float %g) #0 {
 ; GCN-LABEL: fmac_sequence_innermost_fmul_swapped_operands:
 ; GCN:       ; %bb.0:
 ; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; GCN-NEXT:    s_waitcnt_vscnt null, 0x0
-; GCN-NEXT:    v_mul_f32_e32 v2, v2, v3
+; GCN-NEXT:    v_mad_f32 v2, v2, v3, v6
 ; GCN-NEXT:    v_fmac_f32_e32 v2, v0, v1
 ; GCN-NEXT:    v_fmac_f32_e32 v2, v4, v5
-; GCN-NEXT:    v_add_f32_e32 v0, v6, v2
+; GCN-NEXT:    v_mov_b32_e32 v0, v2
 ; GCN-NEXT:    s_setpc_b64 s[30:31]
   %t0 = fmul fast float %a, %b
   %t1 = fmul fast float %c, %d
   %t2 = fadd fast float %t0, %t1
   %t3 = fmul fast float %e, %f
   %t4 = fadd fast float %t2, %t3
   %t5 = fadd fast float %g, %t4
   ret float %t5