[DAGCombine] Remove dead node when it is created by getNegatedExpression

[steven.zhang]

Summary

We hit the infinite loop reported by https://bugs.llvm.org/show_bug.cgi?id=46877 and the reason is the same as D77319. So we need to remove the dead node we created to avoid the sideeffect on DAGCombiner.

[hans]

If it avoids an infinite loop, it can't be an NFC change. Is not possible to reduce the original test case?

[qiucf]

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

[spatel]

In D86183#2227988, @qiucf wrote:

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

The test shows that we are not actually infinite looping; we are exponentially increasing compile time with each additional set of FMA combines.

If I limit the live code in the test by changing the final store from "store float %288, float* %80, align 4" and time it:

store float %233, float* %80, align 4 --> "time llc" --> user 0m30.640s
store float %229, float* %80, align 4 --> "time llc" --> user 0m19.956s
store float %224, float* %80, align 4 --> "time llc" --> user 0m10.881s
store float %217, float* %80, align 4 --> "time llc" --> user 0m5.750s

I don't know if that changes the solution or the potential test. Maybe we could add or check some debug statement to track the number of nodes created?

[steven.zhang]

In D86183#2227988, @qiucf wrote:

The original test case is too big to get something useful. I happened to grab a basic block from it. It's not small enough to be a test, but it would be much easier to analyze: https://reviews.llvm.org/P8230

Thank you for doing this! The test is small enough to demonstrate the problem I think.

The test shows that we are not actually infinite looping; we are exponentially increasing compile time with each additional set of FMA combines.
If I limit the live code in the test by changing the final store from "store float %288, float* %80, align 4" and time it:
store float %233, float* %80, align 4 --> "time llc" --> user 0m30.640s
store float %229, float* %80, align 4 --> "time llc" --> user 0m19.956s
store float %224, float* %80, align 4 --> "time llc" --> user 0m10.881s
store float %217, float* %80, align 4 --> "time llc" --> user 0m5.750s
I don't know if that changes the solution or the potential test. Maybe we could add or check some debug statement to track the number of nodes created?

Good catch. And it also explains more clear on why the fix works as we are removing the unnecessary dead nodes we created that increase the problem size of the DAGCombine. As the final DAG is the same w/o the fix and I am worried the test is easy to be broken if we check the temp node we created, I tend to have chaofang's test to verify we are not increasing the compiling time. Does it make sense ?

And thank you for all your help on the tests!

[steven.zhang]

Add the reduce tests.

[spatel]

LGTM

llvm/test/CodeGen/X86/pr46877.ll

1 ↗

(On Diff #286936)

I think if we are going to spend the time to execute a test, we might as well use FileCheck to verify the output asm. That way, we can detect if some future patch is doing something unexpected.

[steven.zhang]

llvm/test/CodeGen/X86/pr46877.ll

1 ↗

(On Diff #286936)

ok，I will update the test.

[hans]

Pushed to 11.x as 4d16d8dfe50eb45545e844c3c9acafd363637dad

Please let me know if there are any follow-ups.

[uabelho]

Hi,

I wrote https://bugs.llvm.org/show_bug.cgi?id=49393 that seems to start happening with this patch.

[steven.zhang]

It seems that, craig is working on this bugzallia issue. Thank you for reporting this.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
   // Don't allow anything with multiple uses unless we know it is free.
   if (!Op.hasOneUse() && Opcode != ISD::ConstantFP) {
     bool IsFreeExtend = Opcode == ISD::FP_EXTEND &&
                         isFPExtFree(VT, Op.getOperand(0).getValueType());
     if (!IsFreeExtend)
       return SDValue();
   }
 
+  auto RemoveDeadNode = [&](SDValue N) {
+    if (N && N.getNode()->use_empty())
+      DAG.RemoveDeadNode(N.getNode());
+  };
+
   SDLoc DL(Op);
 
   switch (Opcode) {
   case ISD::ConstantFP: {
     // Don't invert constant FP values after legalization unless the target says
     // the negated constant is legal.
     bool IsOpLegal =
         isOperationLegal(ISD::ConstantFP, VT) ||
case ISD::FADD: {
     // fold (fneg (fadd X, Y)) -> (fsub (fneg Y), X)
     NegatibleCost CostY = NegatibleCost::Expensive;
     SDValue NegY =
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, CostY, Depth);
 
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = CostX;
+      RemoveDeadNode(NegY);
       return DAG.getNode(ISD::FSUB, DL, VT, NegX, Y, Flags);
     }
 
     // Negate the Y if it is not expensive.
     if (NegY) {
       Cost = CostY;
+      RemoveDeadNode(NegX);
       return DAG.getNode(ISD::FSUB, DL, VT, NegY, X, Flags);
     }
     break;
   }
   case ISD::FSUB: {
     // We can't turn -(A-B) into B-A when we honor signed zeros.
     if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
       break;
case ISD::FDIV: {
     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
     NegatibleCost CostY = NegatibleCost::Expensive;
     SDValue NegY =
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, CostY, Depth);
 
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = CostX;
+      RemoveDeadNode(NegY);
       return DAG.getNode(Opcode, DL, VT, NegX, Y, Flags);
     }
 
     // Ignore X * 2.0 because that is expected to be canonicalized to X + X.
     if (auto *C = isConstOrConstSplatFP(Op.getOperand(1)))
       if (C->isExactlyValue(2.0) && Op.getOpcode() == ISD::FMUL)
         break;
 
     // Negate the Y if it is not expensive.
     if (NegY) {
       Cost = CostY;
+      RemoveDeadNode(NegX);
       return DAG.getNode(Opcode, DL, VT, X, NegY, Flags);
     }
     break;
   }
   case ISD::FMA:
   case ISD::FMAD: {
     if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
       break;
case ISD::FMAD: {
     // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
     NegatibleCost CostY = NegatibleCost::Expensive;
     SDValue NegY =
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, CostY, Depth);
 
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = std::min(CostX, CostZ);
+      RemoveDeadNode(NegY);
       return DAG.getNode(Opcode, DL, VT, NegX, Y, NegZ, Flags);
     }
 
     // Negate the Y if it is not expensive.
     if (NegY) {
       Cost = std::min(CostY, CostZ);
+      RemoveDeadNode(NegX);
       return DAG.getNode(Opcode, DL, VT, X, NegY, NegZ, Flags);
     }
     break;
   }
 
   case ISD::FP_EXTEND:
   case ISD::FSIN:
     if (SDValue NegV = getNegatedExpression(Op.getOperand(0), DAG, LegalOps,