[DAGCombine] Transform (A + -2.0*B*C) -> (A - (B+B)*C)

[Quolyk]

Summary

This is my first attempt to contribute to llvm. I'm trying to implement this https://bugs.llvm.org/show_bug.cgi?id=32939. I'm struggling with writing tests for this patch. I will be very thankful if somebody guides me trough writing tests for such thing. Thanks a lot.

[fhahn]

Thanks for working on this!

You could try to add a test case to test/CodeGen/AArch64/fadd-combines.ll for example, i.e. add a new function there with the fadd/fmul pattern you want to match.

[mcrosier]

In the bug report I provided a C test case:

double test2(double a, double b, double c) {
  return a + -2.0*b*c;
}

You can use this to create an IR test case using the following command:

clang test.c -O3 -s -emit-llvm -o test.ll

The IR should look something like this:

define double @test2(double %a, double %b, double %c) local_unnamed_addr #0 {
entry:
  %mul = fmul double %b, -2.000000e+00
  %mul1 = fmul double %mul, %c
  %add = fadd double %mul1, %a
  ret double %add
}

You can add your test case to the file suggested by Florian. That should also include examples of how to add the FILECHECK directives, etc.

[escha]

what is the purpose of this transform? why is the new form considered more canonical?

[Quolyk]

Added some tests

[mcrosier]

In D39830#921143, @escha wrote:

what is the purpose of this transform?

The general assumption is that a FP addition will be less expensive than a FP multiply.

why is the new form considered more canonical?

There was a bit of discussion in D32596 with respect to what is considered canonical form. Basically, in IR reassociation and inst combine prefer the 2*a version primarily because this results in 'a' having a single use, which we generally optimize more aggressively than multiple uses.

Is there a particular case you're concerned about?

[mcrosier]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9719

What if N1 is a constant? I suspect you'll run into an assertion as constants don't have operands.

[craig.topper]

This solution doesn't seem very general, it won't catch.

double test2(double a, double b, double c, double d) {
  return a + -2.0*b*c*d;
}

The constant can be many layers of multiplies away. Reassociate pushes constants down the tree. Should reassociate be pulling out the negate when it factors the tree?

[mcrosier]

In D39830#921949, @craig.topper wrote:

This solution doesn't seem very general, it won't catch.

double test2(double a, double b, double c, double d) {
  return a + -2.0*b*c*d;
}

The constant can be many layers of multiplies away. Reassociate pushes constants down the tree. Should reassociate be pulling out the negate when it factors the tree?

Reassociation prefers to "break up subtracts" by converting X-Y to X+-Y, so it can better commute operands to expose more opportunities to reassociate. It turns out that instcombine also prefers this form when Y is a constant. I'm not sure pulling out the negate would work unless we decide to change the canonical form throughout the pipeline, right?

[Quolyk]

Code review. Fix if N1 is constant.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitFADD(SDNode *N) {
   if ((isFMulNegTwo(N0) && N0.hasOneUse()) ||
       (isFMulNegTwo(N1) && N1.hasOneUse())) {
     bool N1IsFMul = isFMulNegTwo(N1);
     SDValue AddOp = N1IsFMul ? N1.getOperand(0) : N0.getOperand(0);
     SDValue Add = DAG.getNode(ISD::FADD, DL, VT, AddOp, AddOp, Flags);
     return DAG.getNode(ISD::FSUB, DL, VT, N1IsFMul ? N0 : N1, Add, Flags);
   }
 
+  // fold (fadd (fmul (fmul B, -2.0) C), A) -> (fsub A, (fmul (fadd B, B) C)
+  SDValue N0N0 = N0->getOperand(0);
+  if ((isFMulNegTwo(N0N0) && N0N0.hasOneUse())) {
+    SDValue AddOp = N0N0.getOperand(0);
+    SDValue MulOp = N0.getOperand(1);
+    SDValue Add = DAG.getNode(ISD::FADD, DL, VT, AddOp, AddOp, Flags);
+    SDValue Mul = DAG.getNode(ISD::FMUL, DL, VT, Add, MulOp, Flags);
+    return DAG.getNode(ISD::FSUB, DL, VT, N1, Mul, Flags);
+  }
+
+  // fold (fadd A, (fmul (fmul B, -2.0) C)) -> (fsub A, (fmul (fadd B, B) C)
+  if (!N1CFP) {
+    SDValue N1N0 = N1->getOperand(0);
+    if (isFMulNegTwo(N1N0) && N1N0.hasOneUse()) {
+      SDValue AddOp = N1N0.getOperand(0);
+      SDValue MulOp = N1.getOperand(1);
+      SDValue Add = DAG.getNode(ISD::FADD, DL, VT, AddOp, AddOp, Flags);
+      SDValue Mul = DAG.getNode(ISD::FMUL, DL, VT, Add, MulOp, Flags);
+      return DAG.getNode(ISD::FSUB, DL, VT, N0, Mul, Flags);
+    }
+  }
+
   // FIXME: Auto-upgrade the target/function-level option.
   if (Options.NoSignedZerosFPMath || N->getFlags().hasNoSignedZeros()) {
     // fold (fadd A, 0) -> A
     if (ConstantFPSDNode *N1C = isConstOrConstSplatFP(N1))
       if (N1C->isZero())
         return N0;
   }
 

test/CodeGen/AArch64/fadd-combines.ll

 entry:
   %mul = fmul double %b, -2.000000e+00
   %add1 = fadd double %a, %mul
   call void @use(double %mul)
   ret double %add1
 }
 
 declare void @use(double)
+
+; CHECK-LABEL: test8:
+; CHECK: fadd  d1, d1, d1
+; CHECK: fmul  d1, d1, d2
+; CHECK: fsub  d0, d0, d1
+define double @test8(double %a, double %b, double %c) local_unnamed_addr #0 {
+entry:
+  %mul = fmul double %b, -2.000000e+00
+  %mul1 = fmul double %mul, %c
+  %add = fadd double %mul1, %a
+  ret double %add
+}
+
+; DAGCombine will canonicalize 'a - 2.0*b*c' to 'a + -2.0*b*c'
+; CHECK-LABEL: test9:
+; CHECK: fadd  d1, d1, d1
+; CHECK: fmul  d1, d1, d2
+; CHECK: fsub  d0, d0, d1
+define double @test9(double %a, double %b, double %c) local_unnamed_addr #0 {
+entry:
+  %mul = fmul double %b, 2.000000e+00
+  %mul1 = fmul double %mul, %c
+  %sub = fsub double %a, %mul1
+  ret double %sub
+}