Page MenuHomePhabricator

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

Authored by spatel on Dec 3 2019, 11:40 AM.

Details

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.

Diff Detail

Event Timeline

spatel created this revision.Dec 3 2019, 11:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 3 2019, 11:40 AM
lebedev.ri added inline comments.Dec 9 2019, 12:15 PM
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 marked an inline comment as done.Dec 9 2019, 2:25 PM
spatel added inline comments.
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5427–5428

Agreed - this is getting too messy.

dstuttard accepted this revision.Dec 10 2019, 2:01 AM

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

This revision is now accepted and ready to land.Dec 10 2019, 2:01 AM

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.

This revision was automatically updated to reflect the committed changes.
fhahn added a subscriber: fhahn.Dec 11 2019, 11:09 AM

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

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.

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.

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 added a comment.Dec 11 2019, 1:30 PM

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 reopened this revision.Dec 11 2019, 1:57 PM

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.

This revision is now accepted and ready to land.Dec 11 2019, 1:57 PM
spatel planned changes to this revision.Dec 11 2019, 3:30 PM
spatel updated this revision to Diff 233461.Dec 11 2019, 5:26 PM
spatel edited the summary of this revision. (Show Details)

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.

This revision is now accepted and ready to land.Dec 11 2019, 5:26 PM
spatel requested review of this revision.Dec 11 2019, 5:27 PM
dstuttard accepted this revision.Dec 17 2019, 3:42 AM

LGTM

Confirmed that this fix also solves my original problem per D70595

This revision is now accepted and ready to land.Dec 17 2019, 3:42 AM
This revision was automatically updated to reflect the committed changes.