[TargetLowering] Use HandleSDNodes to prevent nodes from being deleted by recursive calls in getNegatedExpression.

[craig.topper]

Summary

For binary or ternary ops we call getNegatedExpression multiple
times and then compare costs. While we're doing this we need to
hold a node from the first call across the second call, but its
not yet attached to the DAG. Its possible the second call creates
an identical node and then decides it didn't need it so will try
to delete it if it has no uses. This can cause a reference to the
node we're holding further up the call stack to become invalidated.

To prevent this, we can use a HandleSDNode to artifically give
the node a use without connecting it to the DAG.

I've used a std::list of HandleSDNodes so we can create handles
only when we have a node to hold. HandleSDNode does not have
default constructor and cannot be copied or moved.

Fixes PR49393.

[spatel]

This keeps getting more complicated, but I don't have any better suggestions.
I am still wondering if we can/should assert within getNode() that operand values are not already deleted nodes. Ie, passing those nodes in means the caller has definitely gone out-of-bounds in some way.

[spatel]

LGTM

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
SDValue TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
 
   auto RemoveDeadNode = [&](SDValue N) {
     if (N && N.getNode()->use_empty())
       DAG.RemoveDeadNode(N.getNode());
   };
 
   SDLoc DL(Op);
 
+  // Because getNegatedExpression can delete nodes we need a handle to keep
+  // temporary nodes alive in case the recursion manages to create an identical
+  // node.
+  std::list<HandleSDNode> Handles;
+
   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) ||
         isFPImmLegal(neg(cast<ConstantFPSDNode>(Op)->getValueAPF()), VT,
                      OptForSize);
case ISD::FADD: {
     if (LegalOps && !isOperationLegalOrCustom(ISD::FSUB, VT))
       break;
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1);
 
     // fold (fneg (fadd X, Y)) -> (fsub (fneg X), Y)
     NegatibleCost CostX = NegatibleCost::Expensive;
     SDValue NegX =
         getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
+    // Prevent this node from being deleted by the next call.
+    if (NegX)
+      Handles.emplace_back(NegX);
+
     // fold (fneg (fadd X, Y)) -> (fsub (fneg Y), X)
     NegatibleCost CostY = NegatibleCost::Expensive;
     SDValue NegY =
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, CostY, Depth);
 
+    // We're done with the handles.
+    Handles.clear();
+
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = CostX;
       SDValue N = DAG.getNode(ISD::FSUB, DL, VT, NegX, Y, Flags);
       if (NegY != N)
         RemoveDeadNode(NegY);
       return N;
     }
SDValue TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
   case ISD::FMUL:
   case ISD::FDIV: {
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1);
 
     // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
     NegatibleCost CostX = NegatibleCost::Expensive;
     SDValue NegX =
         getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
+    // Prevent this node from being deleted by the next call.
+    if (NegX)
+      Handles.emplace_back(NegX);
+
     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
     NegatibleCost CostY = NegatibleCost::Expensive;
     SDValue NegY =
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, CostY, Depth);
 
+    // We're done with the handles.
+    Handles.clear();
+
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = CostX;
       SDValue N = DAG.getNode(Opcode, DL, VT, NegX, Y, Flags);
       if (NegY != N)
         RemoveDeadNode(NegY);
       return N;
     }
case ISD::FMAD: {
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1), Z = Op.getOperand(2);
     NegatibleCost CostZ = NegatibleCost::Expensive;
     SDValue NegZ =
         getNegatedExpression(Z, DAG, LegalOps, OptForSize, CostZ, Depth);
     // Give up if fail to negate the Z.
     if (!NegZ)
       break;
 
+    // Prevent this node from being deleted by the next two calls.
+    Handles.emplace_back(NegZ);
+
     // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
     NegatibleCost CostX = NegatibleCost::Expensive;
     SDValue NegX =
         getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
+    // Prevent this node from being deleted by the next call.
+    if (NegX)
+      Handles.emplace_back(NegX);
+
     // 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);
 
+    // We're done with the handles.
+    Handles.clear();
+
     // Negate the X if its cost is less or equal than Y.
     if (NegX && (CostX <= CostY)) {
       Cost = std::min(CostX, CostZ);
       SDValue N = DAG.getNode(Opcode, DL, VT, NegX, Y, NegZ, Flags);
       if (NegY != N)
         RemoveDeadNode(NegY);
       return N;
     }

llvm/test/CodeGen/X86/pr49393.ll

+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+define void @f() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %b.0 = phi i16 [ 0, %entry ], [ %conv77, %for.cond ]
+  %mul18 = mul i16 %b.0, %b.0
+  %arrayidx.real = load double, double* undef, align 1
+  %arrayidx.imag = load double, double* undef, align 1
+  %mul_ac = fmul fast double %arrayidx.real, %arrayidx.real
+  %0 = fadd fast double 0.000000e+00, %arrayidx.real
+  %sub.r = fsub fast double %mul_ac, %0
+  %sub.i = fsub fast double 0.000000e+00, %arrayidx.imag
+  %conv28 = sitofp i16 %mul18 to double
+  %mul_bc32 = fmul fast double %arrayidx.imag, %conv28
+  %mul_bd46 = fmul fast double %mul_bc32, %arrayidx.imag
+  %mul_r49 = fsub fast double 0.000000e+00, %mul_bd46
+  %mul_ac59 = fmul fast double %mul_r49, %sub.r
+  %mul_bc48 = fmul fast double %mul_bc32, %arrayidx.real
+  %mul_i50 = fadd fast double 0.000000e+00, %mul_bc48
+  %1 = fmul fast double %mul_i50, %sub.i
+  %.neg = fneg fast double %0
+  %.neg19 = fmul fast double %1, -1.000000e+00
+  %.neg20 = fadd fast double %.neg, %mul_ac
+  %2 = fadd fast double %.neg20, %mul_ac59
+  %sub.r75 = fadd fast double %2, %.neg19
+  %conv77 = fptosi double %sub.r75 to i16
+  br label %for.cond
+}