transform fadd chains to increase parallelism

[spatel]

Summary

This is a compromise: with this simple patch, we should always handle a chain of exactly 3 operations optimally, but we're not generating the optimal balanced binary tree for a longer sequence.

In general, this transform will reduce the dependency chain for a sequence of instructions using N operands from a worst case N-1 dependent operations to N/2 dependent operations. The optimal balanced binary tree would reduce the chain to log2(N).

As I see it, the trade-off for not dealing with longer sequences is: (1) we have less complexity in the compiler, (2) we avoid unknown compile-time blowup calculating a balanced tree, and (3) we don't need to worry about the increased register pressure required to parallelize longer sequences. It also seems unlikely that we would ever encounter really long strings of dependent ops like that in the wild, but I'm not sure how to verify that speculation. FWIW, I see no perf difference for test-suite running on btver2 (x86-64) with -ffast-math and this patch.

If this patch looks ok, then I can extend it to cover other associative operations such as fmul, fmax, fmin, integer add, integer mul.

This is a partial fix for:
https://llvm.org/bugs/show_bug.cgi?id=17305

and if extended:
https://llvm.org/bugs/show_bug.cgi?id=21768
https://llvm.org/bugs/show_bug.cgi?id=23116

The issue also came up in:
http://reviews.llvm.org/D8941

[qcolombet]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7662 ↗

(On Diff #24326)

I would prefer the comment to match the actual code, i.e., invert the order of the operand:
(fadd (fadd (fadd z, w), y), x) -> (fadd (fadd z, w), (fadd x, y))

You could even use named operands like this:
(fadd N0: (fadd N00: (fadd z, w), N01: y), N1: x) -> (fadd N00: (fadd z, w), (fadd N1: x, M01: y))

7666 ↗

(On Diff #24326)

You can move this assignment into the next if.

test/CodeGen/X86/fp-fast.ll

124 ↗

(On Diff #24326)

Can’t you be more specific on the input registers?
With a pattern like this, I believe even the old inefficient sequence would match, wouldn’t it?

[spatel]

test/CodeGen/X86/fp-fast.ll

124 ↗

(On Diff #24326)

Hi Quentin,

Thanks for reviewing this patch. I don't think we can be more specific on the inputs: we know that xmm0 - xmm3 are the input registers, but the order of the operands as well as the order of the first two adds may be commuted (not by this patch, but some future patch)?

I made sure that the last check will not work without this patch. It requires that the outputs of the first two adds are inputs to the third add. This final add check is actually too specific because it fixes the order of the operands. I tried every regex combo that I could think of to make that more flexible, but couldn't get anything to work with FileCheck.

[qcolombet]

test/CodeGen/X86/fp-fast.ll

124 ↗

(On Diff #24326)

Let stick to the current order of the operands. If they change we can fix them.

Anyhow, this is not a bit deal, I was just not sure, it wouldn’t match the old sequence :).

[spatel]

test/CodeGen/X86/fp-fast.ll

124 ↗

(On Diff #24326)

Ok - if we're not too concerned with flexibility of the match, it becomes easy. :)
I can just use update_llc_test_checks.py for the exact match.

[spatel]

Patch updated:

1. Fixed fold comment to match code
2. Moved variable declaration closer to use
3. Made test CHECK lines match expected output exactly

[qcolombet]

Thanks Sanjay!

LGTM.

Q.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (TLI.isOperationLegalOrCustom(ISD::FMUL, VT) && !N0CFP && !N1CFP) {
           N0.getOperand(0) == N0.getOperand(1) &&
           N1.getOperand(0) == N1.getOperand(1) &&
           N0.getOperand(0) == N1.getOperand(0)) {
         SDLoc DL(N);
         return DAG.getNode(ISD::FMUL, DL, VT,
                            N0.getOperand(0), DAG.getConstantFP(4.0, DL, VT));
       }
     }
+
+    // Canonicalize chains of adds to LHS to simplify the following transform.
+    if (N0.getOpcode() != ISD::FADD && N1.getOpcode() == ISD::FADD)
+      return DAG.getNode(ISD::FADD, SDLoc(N), VT, N1, N0);
+    
+    // Convert a chain of 3 dependent operations into 2 independent operations
+    // and 1 dependent operation:
+    //  (fadd N0: (fadd N00: (fadd z, w), N01: y), N1: x) ->
+    //  (fadd N00: (fadd z, w), (fadd N1: x, N01: y))
+    if (N0.getOpcode() == ISD::FADD &&  N0.hasOneUse() &&
+        N1.getOpcode() != ISD::FADD) {
+      SDValue N00 = N0.getOperand(0);
+      if (N00.getOpcode() == ISD::FADD) {
+        SDValue N01 = N0.getOperand(1);
+        SDValue NewAdd = DAG.getNode(ISD::FADD, SDLoc(N), VT, N1, N01);
+        return DAG.getNode(ISD::FADD, SDLoc(N), VT, N00, NewAdd);
+      }
+    }
   } // enable-unsafe-fp-math
 
   // FADD -> FMA combines:
   SDValue Fused = visitFADDForFMACombine(N);
   if (Fused) {
     AddToWorklist(Fused.getNode());
     return Fused;
   }

llvm/trunk/test/CodeGen/X86/fp-fast.ll

 ; CHECK-LABEL: test11:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    vxorps %xmm0, %xmm0, %xmm0
 ; CHECK-NEXT:    retq
   %t1 = fsub float -0.0, %a
   %t2 = fadd float %a, %t1
   ret float %t2
 }
+
+; Verify that the first two adds are independent; the destination registers
+; are used as source registers for the third add.
+
+define float @reassociate_adds1(float %a, float %b, float %c, float %d) {
+; CHECK-LABEL: reassociate_adds1:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    vaddss %xmm2, %xmm3, %xmm1
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    retq
+  %add0 = fadd float %a, %b
+  %add1 = fadd float %add0, %c
+  %add2 = fadd float %add1, %d
+  ret float %add2
+}
+
+define float @reassociate_adds2(float %a, float %b, float %c, float %d) {
+; CHECK-LABEL: reassociate_adds2:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    vaddss %xmm2, %xmm3, %xmm1
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    retq
+  %add0 = fadd float %a, %b
+  %add1 = fadd float %c, %add0
+  %add2 = fadd float %add1, %d
+  ret float %add2
+}
+
+define float @reassociate_adds3(float %a, float %b, float %c, float %d) {
+; CHECK-LABEL: reassociate_adds3:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    vaddss %xmm2, %xmm3, %xmm1
+; CHECK-NEXT:    vaddss %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    retq
+  %add0 = fadd float %a, %b
+  %add1 = fadd float %add0, %c
+  %add2 = fadd float %d, %add1
+  ret float %add2
+}
+