Utilize new SDNode flag functionality to expand current support for fadd

[mcberg2017]

Summary

This patch originated from D46562 and is a proper subset, with some issues addressed.

[spatel]

There's a lot going on here - in particular, the transforms guarded by 'reassoc'. I'm not sure those are correct as-is.

I know this is tedious, but I have to ask again to split this up and add tests, so we can see diffs for each fold using node-level FMF.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

708–709

clang-format?

769

Change FIXME: the FMF version is good now; the global check is wrong.

(Might want to comment on the broken global checks in multiple places as an NFC preliminary step.)

[mcberg2017]

Removed negation context...

[spatel]

There are several transforms under the last part of this patch, and I'm not sure if we can do them without 'nsz'. This is very similar to D47335 (ping @wristow in case his memory of these cases is better than mine). In that patch, we decided to require 'nsz' for a bunch of reassociations rather than risk breaking some case that we weren't seeing. Should we do that here too at least as a first step? I'm cursing 'nsz' because I just botched that one in D48085.

Here's an example:
(fadd (fadd x, c1), c2) -> (fadd x, (fadd c1, c2))

define float @fadd_consts(float %x) {
  %a1 = fadd float %x, 4.200000e+01
  %a2 = fadd reassoc float %a1, 1.700000e+01
  ret float %a2
}

We don't fold that in IR (instcombine) currently unless that 2nd fadd has 'nsz' too.

[mcberg2017]

Added a todo comment and added nsz to the constraint for the collection of transformations marked.

[mcberg2017]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10363

I think I will change "false" to "considered"

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10366–10368

This seems broken independently of this patch - we just said it's not safe to create new constants, and every transform under here creates a new constant. But we only check 'AllowNewConst' for some of the folds?

Also, I updated the 1st transform under here to not check hasOneUse() in rL334608, so you'll need to rebase.

[mcberg2017]

Sync'd up to head of tree, adjusted one test (newly added here), some minor refactoring for 'AllowNewConst' and add the cleanup from SelectionDAG since fmul, fsub and fadd are all updated to handle what getNode was doing (that code is removed).

[nhaehnle]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10384–10389

This transformation and the similar ones below can change the NaN-ness of the result.

For example, consider x = +inf, c = -0.5. In that case, the LHS is NaN (because of the intermediate -inf + +inf), while the RHS is +inf. Is reassoc supposed to be a strong enough condition to allow this?

I don't see a way for a non-NaN result to be transformed into a NaN result, so perhaps this is okay? But this needs to be a conscious decision and it should be mentioned in the comment above that talks about rounding steps.

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10384–10389

This is circular reasoning, but LLVM does this fold already in IR as long as we have 'nsz reassoc'. This is also allowed by gcc with the equivalent flags:
https://godbolt.org/g/wDh3bM

Our 'reassoc' definition currently says:
"Allow reassociation transformations for floating-point instructions. This may dramatically change results in floating-point."

We could add to that definition if we can make that clearer? Or as you suggest, we can document the potential differences more clearly here by including the INF example.

[mcberg2017]

Updated comment for reassociation case

[nhaehnle]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10384–10389

Those are good points.

It did catch my eye because the documentation of reassoc led me down the path of thinking that sure, there's going to be differences based on different rounding. But this particular difference isn't caused by rounding differences.

Having slept on it and with your points, I think it's okay to do this transform based on reassoc because it doesn't create new NaNs as far as I can tell. If there were similar cases where new NaNs can be created, I think we should tread more carefully. (Of course "mere" rounding differences can create new NaNs, e.g. by turning inf * tiny number into inf * 0, but those should be expected by floating point practicioners, which makes it okay.)

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10366–10367

Shouldn't the 'AllowNewConst' check be moved up here rather than repeated with each transform below?

Again, I think that particular change is independent of the FMF change, so it should be reviewed/committed as a separate patch (preferably before we make the FMF change, so we're not increasing the chance of hitting the bug).

Not sure how/if we can make that difference visible in a regression test with in-tree targets. Remove the existing variable in trunk and see if anything breaks?

[mcberg2017]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10366–10367

The AllowNewConst change is NFC, is I will track it as a simple check in, then update this review afterwards.

[mcberg2017]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10366–10367

I wound up keeping some of the refactoring so it is not quite NFC, the review should appear shortly. The resultant change here in this review will make the code change quite small.

[mcberg2017]

D48289 is now required to be checked in before this change.

[mcberg2017]

Updated for rL334984

[spatel]

LGTM - see inline for a nit.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10356–10358

I'd prefer that we not perpetuate UnsafeFPMath any more than necessary, so I'd say something like:
FP reassociation can have drastic effects on results. For example, inf * -2.0 + inf -> NaN, but reassociation allows that to become inf * -1.0 -> -inf.

[mcberg2017]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10356–10358

I am going to remove the comment, if we leave a special message about reassocation, someone can infer it is different from Unsafe and therefore new behavior, when it is not.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

case ISD::ConstantFP: {
 
     // Don't invert constant FP values after legalization unless the target says
     // the negated constant is legal.
     return TLI.isOperationLegal(ISD::ConstantFP, VT) ||
       TLI.isFPImmLegal(neg(cast<ConstantFPSDNode>(Op)->getValueAPF()), VT);
   }
   case ISD::FADD:
     // FIXME: determine better conditions for this xform.
     if (!Options->UnsafeFPMath) return 0;
 
     // After operation legalization, it might not be legal to create new FSUBs.
     if (LegalOperations && !TLI.isOperationLegalOrCustom(ISD::FSUB, VT))
       return 0;
 
     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
     if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
                                     Options, Depth + 1))
       return V;
static SDValue GetNegatedExpression(SDValue Op, SelectionDAG &DAG,
   switch (Op.getOpcode()) {
   default: llvm_unreachable("Unknown code");
   case ISD::ConstantFP: {
     APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
     V.changeSign();
     return DAG.getConstantFP(V, SDLoc(Op), Op.getValueType());
   }
   case ISD::FADD:
     // FIXME: determine better conditions for this xform.
     assert(Options.UnsafeFPMath);
 
     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
     if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
                            DAG.getTargetLoweringInfo(), &Options, Depth+1))
       return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
                          GetNegatedExpression(Op.getOperand(0), DAG,
                                               LegalOperations, Depth+1),
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);
   }
 
-  // FIXME: Auto-upgrade the target/function-level option.
-  if (Options.NoSignedZerosFPMath || N->getFlags().hasNoSignedZeros()) {
+  ConstantFPSDNode *N1C = isConstOrConstSplatFP(N1);
+  if (N1C && N1C->isZero()) {
+    if (N1C->isNegative() || Options.UnsafeFPMath ||
+        Flags.hasNoSignedZeros()) {
       // fold (fadd A, 0) -> A
-    if (ConstantFPSDNode *N1C = isConstOrConstSplatFP(N1))
-      if (N1C->isZero())
-        return N0;
     }
+  }
 
   // If 'unsafe math' is enabled, fold lots of things.
-  if (Options.UnsafeFPMath) {
-    // No FP constant should be created after legalization as Instruction
-    // Selection pass has a hard time dealing with FP constants.
-    bool AllowNewConst = (Level < AfterLegalizeDAG);
-
-    // fadd (fadd x, c1), c2 -> fadd x, c1 + c2
-    if (N1CFP && N0.getOpcode() == ISD::FADD &&
-        isConstantFPBuildVectorOrConstantFP(N0.getOperand(1))) {
-      SDValue NewC = DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(1), N1, Flags);
-      return DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(0), NewC, Flags);
-    }
-
+  if (Options.UnsafeFPMath || Flags.hasNoNaNs()) {
     // If allowed, fold (fadd (fneg x), x) -> 0.0
     if (AllowNewConst && N0.getOpcode() == ISD::FNEG && N0.getOperand(0) == N1)
       return DAG.getConstantFP(0.0, DL, VT);
 
     // If allowed, fold (fadd x, (fneg x)) -> 0.0
     if (AllowNewConst && N1.getOpcode() == ISD::FNEG && N1.getOperand(0) == N0)
       return DAG.getConstantFP(0.0, DL, VT);
+  }
+
+  // If 'unsafe math' or reassoc and nsz, fold lots of things.
+  // TODO: break out portions of the transformations below for which Unsafe is 
+  //       considered and which do not require both nsz and reassoc
+  if (Options.UnsafeFPMath ||
+      (Flags.hasAllowReassociation() && Flags.hasNoSignedZeros())) {
+    // No FP constant should be created after legalization as Instruction
+    // Selection pass has a hard time dealing with FP constants.
+
+    // fadd (fadd x, c1), c2 -> fadd x, c1 + c2
+    if (N1CFP && N0.getOpcode() == ISD::FADD && AllowNewConst &&
+        isConstantFPBuildVectorOrConstantFP(N0.getOperand(1))) {
+      SDValue NewC = DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(1), N1, Flags);
+      return DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(0), NewC, Flags);
+    }
 
     // We can fold chains of FADD's of the same value into multiplications.
     // This transform is not safe in general because we are reducing the number
     // of rounding steps.
     if (TLI.isOperationLegalOrCustom(ISD::FMUL, VT) && !N0CFP && !N1CFP) {
       if (N0.getOpcode() == ISD::FMUL) {
         bool CFP00 = isConstantFPBuildVectorOrConstantFP(N0.getOperand(0));
         bool CFP01 = isConstantFPBuildVectorOrConstantFP(N0.getOperand(1));
 
         // (fadd (fmul x, c), x) -> (fmul x, c+1)
-        if (CFP01 && !CFP00 && N0.getOperand(0) == N1) {
+        if (CFP01 && !CFP00 && N0.getOperand(0) == N1 && AllowNewConst) {
           SDValue NewCFP = DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(1),
                                        DAG.getConstantFP(1.0, DL, VT), Flags);
           return DAG.getNode(ISD::FMUL, DL, VT, N1, NewCFP, Flags);
         }
 
         // (fadd (fmul x, c), (fadd x, x)) -> (fmul x, c+2)
-        if (CFP01 && !CFP00 && N1.getOpcode() == ISD::FADD &&
+        if (CFP01 && !CFP00 && N1.getOpcode() == ISD::FADD && AllowNewConst &&
             N1.getOperand(0) == N1.getOperand(1) &&
             N0.getOperand(0) == N1.getOperand(0)) {
           SDValue NewCFP = DAG.getNode(ISD::FADD, DL, VT, N0.getOperand(1),
                                        DAG.getConstantFP(2.0, DL, VT), Flags);
           return DAG.getNode(ISD::FMUL, DL, VT, N0.getOperand(0), NewCFP, Flags);
         }
       }
 
       if (N1.getOpcode() == ISD::FMUL) {
         bool CFP10 = isConstantFPBuildVectorOrConstantFP(N1.getOperand(0));
         bool CFP11 = isConstantFPBuildVectorOrConstantFP(N1.getOperand(1));
 
         // (fadd x, (fmul x, c)) -> (fmul x, c+1)
-        if (CFP11 && !CFP10 && N1.getOperand(0) == N0) {
+        if (CFP11 && !CFP10 && N1.getOperand(0) == N0 && AllowNewConst ) {
           SDValue NewCFP = DAG.getNode(ISD::FADD, DL, VT, N1.getOperand(1),
                                        DAG.getConstantFP(1.0, DL, VT), Flags);
           return DAG.getNode(ISD::FMUL, DL, VT, N0, NewCFP, Flags);
         }
 
         // (fadd (fadd x, x), (fmul x, c)) -> (fmul x, c+2)
-        if (CFP11 && !CFP10 && N0.getOpcode() == ISD::FADD &&
+        if (CFP11 && !CFP10 && N0.getOpcode() == ISD::FADD && AllowNewConst &&
             N0.getOperand(0) == N0.getOperand(1) &&
             N1.getOperand(0) == N0.getOperand(0)) {
           SDValue NewCFP = DAG.getNode(ISD::FADD, DL, VT, N1.getOperand(1),
                                        DAG.getConstantFP(2.0, DL, VT), Flags);
           return DAG.getNode(ISD::FMUL, DL, VT, N1.getOperand(0), NewCFP, Flags);
         }
       }
 
if (TLI.isOperationLegalOrCustom(ISD::FMUL, VT) && !N0CFP && !N1CFP) {
       if (N1.getOpcode() == ISD::FADD && AllowNewConst) {
         bool CFP10 = isConstantFPBuildVectorOrConstantFP(N1.getOperand(0));
         // (fadd x, (fadd x, x)) -> (fmul x, 3.0)
         if (!CFP10 && N1.getOperand(0) == N1.getOperand(1) &&
             N1.getOperand(0) == N0) {
           return DAG.getNode(ISD::FMUL, DL, VT,
                              N0, DAG.getConstantFP(3.0, DL, VT), Flags);
         }
-      }
 
         // (fadd (fadd x, x), (fadd x, x)) -> (fmul x, 4.0)
-      if (AllowNewConst &&
-          N0.getOpcode() == ISD::FADD && N1.getOpcode() == ISD::FADD &&
+        if (N0.getOpcode() == ISD::FADD && 
             N0.getOperand(0) == N0.getOperand(1) &&
             N1.getOperand(0) == N1.getOperand(1) &&
             N0.getOperand(0) == N1.getOperand(0)) {
           return DAG.getNode(ISD::FMUL, DL, VT, N0.getOperand(0),
                              DAG.getConstantFP(4.0, DL, VT), Flags);
         }
       }
+    }
   } // enable-unsafe-fp-math
 
   // FADD -> FMA combines:
   if (SDValue Fused = visitFADDForFMACombine(N)) {
     AddToWorklist(Fused.getNode());
     return Fused;
   }
   return SDValue();

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::UMAX:
     assert(N1.getValueType() == N2.getValueType() &&
            N1.getValueType() == VT && "Binary operator types must match!");
     break;
   case ISD::FADD:
   case ISD::FSUB:
   case ISD::FMUL:
   case ISD::FDIV:
   case ISD::FREM:
-    if (getTarget().Options.UnsafeFPMath) {
-      if (Opcode == ISD::FADD) {
-        // x+0 --> x
-        if (N2CFP && N2CFP->getValueAPF().isZero())
-          return N1;
-      } else if (Opcode == ISD::FSUB) {
-        // x-0 --> x
-        if (N2CFP && N2CFP->getValueAPF().isZero())
-          return N1;
-      } else if (Opcode == ISD::FMUL) {
-        // x*0 --> 0
-        if (N2CFP && N2CFP->isZero())
-          return N2;
-        // x*1 --> x
-        if (N2CFP && N2CFP->isExactlyValue(1.0))
-          return N1;
-      }
-    }
     assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
     assert(N1.getValueType() == N2.getValueType() &&
            N1.getValueType() == VT && "Binary operator types must match!");
     break;
   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
     assert(N1.getValueType() == VT &&
            N1.getValueType().isFloatingPoint() &&
            N2.getValueType().isFloatingPoint() &&

test/CodeGen/AArch64/fadd-combines.ll

; CHECK-NEXT:    ret
   call void @use(double %mul)
   ret double %add1
 }
 
 define float @fadd_const_multiuse_fmf(float %x) {
 ; CHECK-LABEL: fadd_const_multiuse_fmf:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    adrp x8, .LCPI7_0
+; CHECK-NEXT:    adrp x9, .LCPI7_1
 ; CHECK-NEXT:    ldr s1, [x8, :lo12:.LCPI7_0]
-; CHECK-NEXT:    fadd s0, s0, s1
-; CHECK-NEXT:    fmov s1, #17.00000000
+; CHECK-NEXT:    ldr s2, [x9, :lo12:.LCPI7_1]
 ; CHECK-NEXT:    fadd s1, s0, s1
-; CHECK-NEXT:    fadd s0, s0, s1
+; CHECK-NEXT:    fadd s0, s0, s2
+; CHECK-NEXT:    fadd s0, s1, s0
 ; CHECK-NEXT:    ret
   %a1 = fadd float %x, 42.0
   %a2 = fadd nsz reassoc float %a1, 17.0
   %a3 = fadd float %a1, %a2
   ret float %a3
 }
 
 ; DAGCombiner transforms this into: (x + 59.0) + (x + 17.0).

test/CodeGen/AMDGPU/fadd.ll

define amdgpu_kernel void @fadd_v8f32(<8 x float> addrspace(1)* %out, <8 x float> %a, <8 x float> %b) #0 {
   %add = fadd <8 x float> %a, %b
   store <8 x float> %add, <8 x float> addrspace(1)* %out, align 32
   ret void
 }
 
 ; FUNC-LABEL: {{^}}fadd_0_nsz_attr_f32:
 ; SI-NOT: v_add_f32
 define amdgpu_kernel void @fadd_0_nsz_attr_f32(float addrspace(1)* %out, float %a) #1 {
-   %add = fadd float %a, 0.0
+   %add = fadd nsz float %a, 0.0
    store float %add, float addrspace(1)* %out, align 4
    ret void
 }
 
 attributes #0 = { nounwind }
 attributes #1 = { nounwind "no-signed-zeros-fp-math"="true" }

test/CodeGen/X86/fmf-flags.ll

; X86-NEXT:    retl
   ret float %z
 }
 
 declare float @llvm.fmuladd.f32(float %a, float %b, float %c);
 
 define float @fast_fmuladd_opts(float %a , float %b , float %c) {
 ; X64-LABEL: fast_fmuladd_opts:
 ; X64:       # %bb.0:
-; X64-NEXT:    movaps %xmm0, %xmm1
-; X64-NEXT:    addss %xmm0, %xmm1
-; X64-NEXT:    addss %xmm0, %xmm1
-; X64-NEXT:    movaps %xmm1, %xmm0
+; X64-NEXT:    mulss {{.*}}(%rip), %xmm0
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: fast_fmuladd_opts:
 ; X86:       # %bb.0:
 ; X86-NEXT:    flds {{[0-9]+}}(%esp)
-; X86-NEXT:    fld %st(0)
-; X86-NEXT:    fadd %st(1)
-; X86-NEXT:    faddp %st(1)
+; X86-NEXT:    fmuls {{.*}}
 ; X86-NEXT:    retl
   %res = call fast float @llvm.fmuladd.f32(float %a, float 2.0, float %a)
   ret float %res
 }
 
 ; The multiply is strict.
 
 @mul1 = common global double 0.000000e+00, align 4
 
 define double @not_so_fast_mul_add(double %x) {
 ; X64-LABEL: not_so_fast_mul_add:
 ; X64:       # %bb.0:
-; X64-NEXT:    movsd {{.*#+}} xmm1 = mem[0],zero
+; X64-NEXT:    movsd {{.*}}(%rip), %xmm1
 ; X64-NEXT:    mulsd %xmm0, %xmm1
-; X64-NEXT:    addsd %xmm1, %xmm0
+; X64-NEXT:    mulsd {{.*}}(%rip), %xmm0
 ; X64-NEXT:    movsd %xmm1, {{.*}}(%rip)
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: not_so_fast_mul_add:
 ; X86:       # %bb.0:
 ; X86-NEXT:    fldl {{[0-9]+}}(%esp)
 ; X86-NEXT:    fld %st(0)
 ; X86-NEXT:    fmull {{\.LCPI.*}}
-; X86-NEXT:    fadd %st(0), %st(1)
+; X86-NEXT:    fxch %st(1)
+; X86-NEXT:    fmull {{\.LCPI.*}}
+; X86-NEXT:    fxch %st(1)
 ; X86-NEXT:    fstpl mul1
 ; X86-NEXT:    retl
   %m = fmul double %x, 4.2
   %a = fadd fast double %m, %x
   store double %m, double* @mul1, align 4
   ret double %a
 }
 

test/CodeGen/X86/fp-fold.ll

 ; UNSAFE-LABEL: fadd_zero:
 ; UNSAFE:       # %bb.0:
 ; UNSAFE-NEXT:    retq
   %r = fadd float %x, 0.0
   ret float %r
 }
 
 define float @fadd_negzero(float %x) {
-; STRICT-LABEL: fadd_negzero:
-; STRICT:       # %bb.0:
-; STRICT-NEXT:    addss {{.*}}(%rip), %xmm0
-; STRICT-NEXT:    retq
-;
-; UNSAFE-LABEL: fadd_negzero:
-; UNSAFE:       # %bb.0:
-; UNSAFE-NEXT:    retq
+; ANY-LABEL: fadd_negzero:
+; ANY:       # %bb.0:
+; ANY-NEXT:    retq
   %r = fadd float %x, -0.0
   ret float %r
 }
 
+define float @fadd_produce_zero(float %x) {
+; ANY-LABEL: fadd_produce_zero:
+; ANY:       # %bb.0:
+; ANY-NEXT:    xorps %xmm0, %xmm0
+; ANY-NEXT:    retq
+  %neg = fsub nsz float 0.0, %x
+  %r = fadd nnan float %neg, %x
+  ret float %r
+}
+
+define float @fadd_reassociate(float %x) {
+; ANY-LABEL: fadd_reassociate:
+; ANY:       # %bb.0:
+; ANY-NEXT:    addss {{.*}}(%rip), %xmm0
+; ANY-NEXT:    retq
+  %sum = fadd float %x, 8.0
+  %r = fadd reassoc nsz float %sum, 12.0
+  ret float %r
+}
+
 define float @fadd_negzero_nsz(float %x) {
 ; ANY-LABEL: fadd_negzero_nsz:
 ; ANY:       # %bb.0:
 ; ANY-NEXT:    retq
   %r = fadd nsz float %x, -0.0
   ret float %r
 }