[SDAG] remove use restriction in isNegatibleForFree() when called from getNegatedExpression()

[spatel]

Summary

This is an alternate fix for the bug discussed in D70595. This also includes minimal tests for other in-tree targets to show the problem more generally.

We check the number of uses as a predicate for whether some value is free to negate, but that use count can change as we rewrite the expression in getNegatedExpression(). So something that was marked free to negate during the cost evaluation phase becomes not free to negate during the rewrite phase (or the inverse - something that was not free becomes free). This can lead to a crash/assert because we expect that everything in an expression that is negatible to be handled in the corresponding code within getNegatedExpression().

This patch adds a hack to work-around the case where we probably no longer detect that either multiply operand of an FMA isNegatibleForFree which is assumed to be true when we started rewriting the expression.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5427–5428

Three nearby bool params is super easy to get in the wrong order.
Should these be stored/passed as a struct?

[spatel]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5427–5428

Agreed - this is getting too messy.

[dstuttard]

This fixes the issue I encountered for the original fix in D70595

Also agree with the comment about multi-bool params - but other than that LGTM

[spatel]

Given that this fixes a crash and has no known bugs itself, I'll plan to commit it as-is and then follow-up with the refactoring to reduce risk/increase testing.

[fhahn]

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

[spatel]

In D70975#1780237, @fhahn wrote:

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

Thanks for letting us know. Can you check if D70595 would cause the same cycle?
Will it be possible to reduce a test that can be shared? I'm not sure how to proceed without a test.

[fhahn]

In D70975#1780280, @spatel wrote:

In D70975#1780237, @fhahn wrote:

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

Thanks for letting us know. Can you check if D70595 would cause the same cycle?
Will it be possible to reduce a test that can be shared? I'm not sure how to proceed without a test.

I'll see if I can reduce it tomorrow! I looked at the debug output and it seems the cycle is quite simple.

[spatel]

In D70975#1780280, @spatel wrote:

In D70975#1780237, @fhahn wrote:

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

Thanks for letting us know. Can you check if D70595 would cause the same cycle?
Will it be possible to reduce a test that can be shared? I'm not sure how to proceed without a test.

I can't tell from this log, but it's possible that this bot has infinite looped because of this change?
http://lab.llvm.org:8011/builders/clang-s390x-linux-lnt/builds/15964

If we need to revert and D70595 would also cause problems, I have a one-line hack that could work-around the crashing that motivated this patch and hopefully not induce any other significant diffs:

diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index f8afdaf086a..b85150fb7cd 100644
--- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -5619,7 +5619,12 @@ SDValue TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                  ForCodeSize, Depth + 1);
     char V1 = isNegatibleForFree(Op.getOperand(1), DAG, LegalOperations,
                                  ForCodeSize, Depth + 1);
-    if (V0 >= V1) {
+    // TODO: It is possible that costs have changed between now and the initial
+    //       calls to isNegatibleForFree(). That is because we are rewriting the
+    //       expression, and that may change the number of uses (and therefore
+    //       the cost) of values. If the negation costs are equal, only negate
+    //       this value if it is a constant. Otherwise, try operand 1.
+    if (V0 > V1 || (V0 == V1 && isa<ConstantFPSDNode>(Op.getOperand(0)))) {
       // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
       SDValue Neg0 = getNegatedExpression(
           Op.getOperand(0), DAG, LegalOperations, ForCodeSize, Depth + 1);

[fhahn]

In D70975#1780401, @fhahn wrote:

In D70975#1780280, @spatel wrote:

In D70975#1780237, @fhahn wrote:

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

Thanks for letting us know. Can you check if D70595 would cause the same cycle?
Will it be possible to reduce a test that can be shared? I'm not sure how to proceed without a test.

I'll see if I can reduce it tomorrow! I looked at the debug output and it seems the cycle is quite simple.

With this patch, running llc on the snippet below causes a combiner cycle.

define linkonce_odr i64 @quux(double* %arg, double %arg1, double %arg2, double %arg3, double %arg4, double %arg5) {
bb:
  %tmp = fdiv double 1.000000e+00, %arg1
  %tmp6 = fmul double %tmp, %arg2
  %tmp7 = fmul double %tmp, %arg3
  %tmp8 = fmul double %tmp, %arg4
  %tmp9 = fmul double %tmp, %arg5
  %tmp10 = fneg double %tmp7
  %tmp11 = fmul double %tmp6, %tmp8
  %tmp12 = fmul double %tmp9, 4.000000e+00
  %tmp13 = fsub double %tmp11, %tmp12
  %tmp14 = fneg double %tmp9
  %tmp15 = fmul double %tmp6, %tmp14
  %tmp16 = fmul double %tmp6, %tmp15
  %tmp17 = fmul double %tmp7, %tmp12
  %tmp18 = fadd double %tmp16, %tmp17
  %tmp19 = fmul double %tmp8, %tmp8
  %tmp20 = fsub double %tmp18, %tmp19
  %tmp21 = call i64 @wombat(double* nonnull undef, double 1.000000e+00, double %tmp10, double %tmp13, double %tmp20)
  ret i64 %tmp21
}
declare i64 @wombat(double*, double, double, double, double)

[spatel]

In D70975#1780450, @fhahn wrote:

In D70975#1780401, @fhahn wrote:

In D70975#1780280, @spatel wrote:

In D70975#1780237, @fhahn wrote:

This seems to cause a DAGCombiner to not terminate for some inputs on AArch64. Unfortunately I cannot share the inputs that cause the cycle :(

Thanks for letting us know. Can you check if D70595 would cause the same cycle?
Will it be possible to reduce a test that can be shared? I'm not sure how to proceed without a test.

I'll see if I can reduce it tomorrow! I looked at the debug output and it seems the cycle is quite simple.

With this patch, running llc on the snippet below causes a combiner cycle.

define linkonce_odr i64 @quux(double* %arg, double %arg1, double %arg2, double %arg3, double %arg4, double %arg5) {
bb:
  %tmp = fdiv double 1.000000e+00, %arg1
  %tmp6 = fmul double %tmp, %arg2
  %tmp7 = fmul double %tmp, %arg3
  %tmp8 = fmul double %tmp, %arg4
  %tmp9 = fmul double %tmp, %arg5
  %tmp10 = fneg double %tmp7
  %tmp11 = fmul double %tmp6, %tmp8
  %tmp12 = fmul double %tmp9, 4.000000e+00
  %tmp13 = fsub double %tmp11, %tmp12
  %tmp14 = fneg double %tmp9
  %tmp15 = fmul double %tmp6, %tmp14
  %tmp16 = fmul double %tmp6, %tmp15
  %tmp17 = fmul double %tmp7, %tmp12
  %tmp18 = fadd double %tmp16, %tmp17
  %tmp19 = fmul double %tmp8, %tmp8
  %tmp20 = fsub double %tmp18, %tmp19
  %tmp21 = call i64 @wombat(double* nonnull undef, double 1.000000e+00, double %tmp10, double %tmp13, double %tmp20)
  ret i64 %tmp21
}
declare i64 @wombat(double*, double, double, double, double)

Thanks! Reverted this to investigate further.

[spatel]

Patch revised:
I do not know how to solve this properly, so I'm proposing a one-line hack to prevent the crashing we have today.
The earlier draft of this patch could lead to infinite looping (tests added with rG83e1bd36be98).
D70595 would avoid that particular hang, but it does not fix the bug for the test cases shown here - they still crash/assert.
This fixes the crashing and does not induce any hangs that I know of.
But there are no guarantees here AFAICT - I think we need to rewrite this whole thing.

[dstuttard]

LGTM

Confirmed that this fix also solves my original problem per D70595

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

DAG.getContext()->emitError("argument to '__builtin_return_address' must "
                                 "be a constant integer");
     return true;
   }
 
   return false;
 }
 
 char TargetLowering::isNegatibleForFree(SDValue Op, SelectionDAG &DAG,
                                         bool LegalOperations, bool ForCodeSize,
                                         unsigned Depth) const {
   // fneg is removable even if it has multiple uses.
   if (Op.getOpcode() == ISD::FNEG)
     return 2;
 
   // Don't allow anything with multiple uses unless we know it is free.
   EVT VT = Op.getValueType();
   const SDNodeFlags Flags = Op->getFlags();
   const TargetOptions &Options = DAG.getTarget().Options;
case ISD::FMAD: {
 
     SDValue Neg2 = getNegatedExpression(Op.getOperand(2), DAG, LegalOperations,
                                         ForCodeSize, Depth + 1);
 
     char V0 = isNegatibleForFree(Op.getOperand(0), DAG, LegalOperations,
                                  ForCodeSize, Depth + 1);
     char V1 = isNegatibleForFree(Op.getOperand(1), DAG, LegalOperations,
                                  ForCodeSize, Depth + 1);
-    if (V0 >= V1) {
+    // TODO: This is a hack. It is possible that costs have changed between now
+    //       and the initial calls to isNegatibleForFree(). That is because we
+    //       are rewriting the expression, and that may change the number of
+    //       uses (and therefore the cost) of values. If the negation costs are
+    //       equal, only negate this value if it is a constant. Otherwise, try
+    //       operand 1. A better fix would eliminate uses as a cost factor or
+    //       track the change in uses as we rewrite the expression.
+    if (V0 > V1 || (V0 == V1 && isa<ConstantFPSDNode>(Op.getOperand(0)))) {
       // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
       SDValue Neg0 = getNegatedExpression(
           Op.getOperand(0), DAG, LegalOperations, ForCodeSize, Depth + 1);
       return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(), Neg0,
                          Op.getOperand(1), Neg2, Flags);
     }
 
     // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))

llvm/test/CodeGen/AArch64/arm64-fmadd.ll

 ; CHECK-LABEL: fnms64:
 ; CHECK: fnmsub d0, d0, d1, d2
 entry:
   %mul = fmul double %c, -1.000000e+00
   %0 = tail call double @llvm.fma.f64(double %a, double %b, double %mul)
   ret double %0
 }
 
+; This would crash while trying getNegatedExpression().
+
+define float @negated_constant(float %x) {
+; CHECK-LABEL: negated_constant:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #-1037565952
+; CHECK-NEXT:    mov w9, #1109917696
+; CHECK-NEXT:    fmov s1, w8
+; CHECK-NEXT:    fmul s1, s0, s1
+; CHECK-NEXT:    fmov s2, w9
+; CHECK-NEXT:    fmadd s0, s0, s2, s1
+; CHECK-NEXT:    ret
+  %m = fmul float %x, 42.0
+  %fma = call nsz float @llvm.fma.f32(float %x, float -42.0, float %m)
+  %nfma = fneg float %fma
+  ret float %nfma
+}
+
 declare float @llvm.fma.f32(float, float, float) nounwind readnone
 declare double @llvm.fma.f64(double, double, double) nounwind readnone

llvm/test/CodeGen/X86/fma-fneg-combine-2.ll

entry:
   %0 = tail call nsz float @llvm.fma.f32(float %x, float %suby, float %negz)
   %1 = fsub float -0.000000e+00, %0
   ret float %1
 }
 
 define float @test_fneg_fma_subx_suby_negz_f32(float %w, float %x, float %y, float %z)  {
 ; FMA3-LABEL: test_fneg_fma_subx_suby_negz_f32:
 ; FMA3:       # %bb.0: # %entry
-; FMA3-NEXT:    vsubss %xmm0, %xmm1, %xmm1
-; FMA3-NEXT:    vsubss %xmm2, %xmm0, %xmm0
+; FMA3-NEXT:    vsubss %xmm1, %xmm0, %xmm1
+; FMA3-NEXT:    vsubss %xmm0, %xmm2, %xmm0
 ; FMA3-NEXT:    vfmadd213ss {{.*#+}} xmm0 = (xmm1 * xmm0) + xmm3
 ; FMA3-NEXT:    retq
 ;
 ; FMA4-LABEL: test_fneg_fma_subx_suby_negz_f32:
 ; FMA4:       # %bb.0: # %entry
-; FMA4-NEXT:    vsubss %xmm0, %xmm1, %xmm1
-; FMA4-NEXT:    vsubss %xmm2, %xmm0, %xmm0
+; FMA4-NEXT:    vsubss %xmm1, %xmm0, %xmm1
+; FMA4-NEXT:    vsubss %xmm0, %xmm2, %xmm0
 ; FMA4-NEXT:    vfmaddss %xmm3, %xmm0, %xmm1, %xmm0
 ; FMA4-NEXT:    retq
 entry:
   %subx = fsub nsz float %w, %x
   %suby = fsub nsz float %w, %y
   %negz = fsub float -0.000000e+00, %z
   %0 = tail call nsz float @llvm.fma.f32(float %subx, float %suby, float %negz)
   %1 = fsub float -0.000000e+00, %0
entry:
   %subx = fsub nsz float %w, %x
   %negy = fsub float -0.000000e+00, %y
   %negz = fsub float -0.000000e+00, %z
   %0 = tail call nsz float @llvm.fma.f32(float %subx, float %negy, float %negz)
   %1 = fsub float -0.000000e+00, %0
   ret float %1
 }
 
+; This would crash while trying getNegatedExpression().
+
+define float @negated_constant(float %x) {
+; FMA3-LABEL: negated_constant:
+; FMA3:       # %bb.0:
+; FMA3-NEXT:    vmulss {{.*}}(%rip), %xmm0, %xmm1
+; FMA3-NEXT:    vfmadd132ss {{.*#+}} xmm0 = (xmm0 * mem) + xmm1
+; FMA3-NEXT:    retq
+;
+; FMA4-LABEL: negated_constant:
+; FMA4:       # %bb.0:
+; FMA4-NEXT:    vmulss {{.*}}(%rip), %xmm0, %xmm1
+; FMA4-NEXT:    vfmaddss %xmm1, {{.*}}(%rip), %xmm0, %xmm0
+; FMA4-NEXT:    retq
+  %m = fmul float %x, 42.0
+  %fma = call nsz float @llvm.fma.f32(float %x, float -42.0, float %m)
+  %nfma = fneg float %fma
+  ret float %nfma
+}
+
 declare float @llvm.fma.f32(float, float, float)