[DAGCombine] Remove the getNegatibleCost to avoid the out of sync with getNegatedExpression

[steven.zhang]

Summary

We have the getNegatibleCost/getNegatedExpression to evaluate the cost and negate the expression. However, during negating the expression, the cost might change as we are changing the DAG, and then, hit the assertion if we negated the wrong expression as the cost is not trustful anymore.

We are struggling to fix such issues on D75501, D70975, D76638, D76439 etc and I believe there are more potential issues here, as we make assumption that, the cost won't change during negating the expression.

This patch is target to remove the getNegatibleCost to avoid the out of sync with getNegatedExpression, and check the cost during negating the expression. It also reduce the duplicated code between getNegatibleCost and getNegatedExpression. And fix the crash for the test in D76638

The side effect is that, we have to create some nodes which will be removed in the next iteration of DAGCombine soon. And it will change the combine worklist as we always push the operands of the unused node into worklist when it is deleted. But it shouldn't have bad impact as we are designing to not to rely on the combine order.

[RKSimon]

llvm/include/llvm/CodeGen/TargetLowering.h

3538

You might be better off keeping the NegatibleCost enum and using it as a threshold value instead.

[efriedma]

Can you split whatever change affects the PPC tests into a separate patch, if it's not too tricky?

llvm/include/llvm/CodeGen/TargetLowering.h

3538

Maybe expand a little what "profitable" means.

3579

"if it has"?

[steven.zhang]

In D77319#1957709, @efriedma wrote:

Can you split whatever change affects the PPC tests into a separate patch, if it's not too tricky?

Yes, I am trying to do it, and that is the main reason why this revision is in WIP status. It seems that we have different combine order for that case that result in different combination result, though they are semantics the same. I will take a deep look at this.

llvm/include/llvm/CodeGen/TargetLowering.h

3538

Good suggestion.

[steven.zhang]

Keep the NegatibleCost and change its enum value to make it consistent with its semantics. CostX < CostY means the cost of negated X is cheaper than Y.

[steven.zhang]

In D77319#1958627, @steven.zhang wrote:

In D77319#1957709, @efriedma wrote:

Can you split whatever change affects the PPC tests into a separate patch, if it's not too tricky?

Yes, I am trying to do it, and that is the main reason why this revision is in WIP status. It seems that we have different combine order for that case that result in different combination result, though they are semantics the same. I will take a deep look at this.

I cannot as it is tricky... We are creating some nodes during negate the expression, and these nodes will be deleted by recursivelyDeleteUnusedNodes() when we are trying another run of the combine. But their operands will be push into the worklist and keep it if their use is not empty. That means, we might change the order of the instructions to combine. For this case, the order matters the instruction selection, so, we see the changes.

[qiucf]

This patch overall looks like good refactoring, which resolves the 'inconsistency' and redundant logic between two methods.

Test changes make sense here since we have no way to tell combiner that 'these nodes are totally useless'. If we really want to keep tests unchanged, we need to add some hint to getNode or worklist handling logic.

llvm/include/llvm/CodeGen/TargetLowering.h

261

This change can be a parent commit since it's not related to this refactoring.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5734

If I understand correctly, we can make sure only internal bug in this method would hit the assert? Since we shouldn't get non-null NegX but expensive CostX.

I just mean: we used to have many asserts in this function, because we need to ensure it's 'aligned' with return value of getNegatibleCost. But now we removed that function and use null SDValue to represent Expensive results, so we don't need those asserts any more.

Only asserts like here to catch internal bugs are okay.

[steven.zhang]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5734

Thank you for the review. Yes, as the getNegatedExpression could be override by target, we need to make sure that they didn't return non-null value with expensive cost, as we make assumption that, if the return value is null, it means expensive negating.

[steven.zhang]

Gentle ping ...

[spatel]

The existing code is buggy, and there's general agreement that this is a good way forward, so please make whatever NFC changes (like switching the enum values) are possible as preliminary patches. Also, make small edits that were already suggested (improve code comments, add assert message string). That will reduce risk and make the final review easier.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5734

Add an assert string for this and other assert lines (if they are going to remain):
http://llvm.org/docs/CodingStandards.html#assert-liberally

[steven.zhang]

Rebase the patch and add the assertion string, necessary comments and the crash test of D76638.

[steven.zhang]

Minor NFC update to the patch.
To help the reviewer review this patch easier, I summarize the patch as follows:

1. All the changes in DAGCombine.cpp is NFC change, which is just some text replacement with new interface.
2. All the changes in X86 or AMDGPU is also NFC change, which remove the duplicated code of getNegatibleCost and make the getNegatedExpression logic more clean.
3. Inside the TargetLowering.cpp, I merge all the checkers in getNegatibleCost into getNegatedExpression before doing the negation. Most of them are semantics the same, except the FMA/FADD/FMUL. Old logic will return the cost immediately if the LHS is not expensive, which will make the cost of FMUL A, B, A=neutral, B=cheaper as neutral, and now, it is cheaper. We have to negate them both and decide the best cost.
4. The change in the PowerPC test is as expected.

[spatel]

llvm/include/llvm/CodeGen/TargetLowering.h

3572

Do we need to initialize the output value here (and other parts of the patch)? I think it would be better to just document in the code comment for this function that the Cost value is invalid if no SDValue is returned. Alternatively, we could add an 'Invalid' enum value if that's really a concern.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12397 ↗

(On Diff #257646)

Would it help to add getCheaperNegatedExpression as a helper with the existing methods right away and rebase this on top of that?

[steven.zhang]

llvm/include/llvm/CodeGen/TargetLowering.h

261

Done in https://reviews.llvm.org/D77993

3572

It makes sense. I will remove this line and add comments that the cost value is undefined if no SDValue returned.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12397 ↗

(On Diff #257646)

Good suggestion. I will do that.

[steven.zhang]

NFC patch https://reviews.llvm.org/D78291 created and I will rebase this patch.

[steven.zhang]

Split this patch into three parts for easy to review:

1. D78291 NFC change by adding new helper functions and the changes in DAGCombine.
2. D78347 Addressing the reason of the change in PowerPC tests.
3. D77319(this patch) Remove the getNegatibleCost and merge it with getNegatedExpression to fix the out of sync issue.

[RKSimon]

LGTM - this looks ready as well - when you are ready please commit the patches separately

[sammccall]

We're seeing infloops in compilation after this change, specifically in an XLA test https://github.com/tensorflow/tensorflow/blob/master/tensorflow/compiler/xla/tests/convolution_variants_test.cc#L380-L398

I've managed to extract an IR reproducer (attached). llc -mcpu=skylake-avx512 module_0000.ir-with-opt.ll hangs with llc built after this change and not before.
Will revert and try to reduce it through bugpoint too

Reproducer:

module_0000.ir-with-opt.ll36 KBDownload

[steven.zhang]

Fix the infinite loop reported by sammccall.

[steven.zhang]

The root cause of the infinite loop:
As mentioned before, the new created node will be deleted later in the next iteration of the DAGCombine. And we will push all the nodes it refers into the worklist to do the combine again. So, the circle reference would happen if the referred nodes refer that node later.
Thus, we need to remove the dead node we created immediately to avoid the side effect to DAGCombinne.

   /// This is the helper function to return the newly negated expression only
   /// when the cost is cheaper.
   SDValue getCheaperNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                       bool LegalOps, bool OptForSize,
                                       unsigned Depth = 0) const {
-    if (getNegatibleCost(Op, DAG, LegalOps, OptForSize, Depth) ==
-        NegatibleCost::Cheaper)
-      return negateExpression(Op, DAG, LegalOps, OptForSize, Depth);
+    NegatibleCost Cost = NegatibleCost::Expensive;
+    SDValue Neg =
+        getNegatedExpression(Op, DAG, LegalOps, OptForSize, Cost, Depth);
+    if (Neg && Cost == NegatibleCost::Cheaper)
+      return Neg;
+    // Remove the new created node to avoid the side effect to the DAG.
+    if (Neg && Neg.getNode()->use_empty())
+      DAG.RemoveDeadNode(Neg.getNode());
     return SDValue();

[steven.zhang]

Gentle ping ...

[RKSimon]

LGTM - cheers

llvm/include/llvm/CodeGen/TargetLowering.h

enum class MulExpansionKind {
     OnlyLegalOrCustom, // Only expand when the resulting instructions are legal
                        // or custom.
   };
 
   /// Enum that specifies when a float negation is beneficial.
   enum class NegatibleCost {
     Cheaper = 0,    // Negated expression is cheaper.
     Neutral = 1,    // Negated expression has the same cost.
     Expensive = 2   // Negated expression is more expensive.
   };
 
   class ArgListEntry {
   public:
     Value *Val = nullptr;
     SDValue Node = SDValue();
     Type *Ty = nullptr;
     bool IsSExt : 1;
public:
   /// physical registers in the exit blocks. This function is called at the end
   /// of instruction selection.
   virtual void insertCopiesSplitCSR(
       MachineBasicBlock *Entry,
       const SmallVectorImpl<MachineBasicBlock *> &Exits) const {
     llvm_unreachable("Not Implemented");
   }
 
-  /// Returns whether computing the negated form of the specified expression is
-  /// more expensive, the same cost or cheaper.
-  virtual NegatibleCost getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                         bool LegalOperations, bool ForCodeSize,
-                                         unsigned Depth = 0) const;
-
-  /// If getNegatibleCost returns Neutral/Cheaper, return the newly negated
-  /// expression.
-  virtual SDValue negateExpression(SDValue Op, SelectionDAG &DAG, bool LegalOps,
-                                   bool OptForSize, unsigned Depth = 0) const;
-
   /// Return the newly negated expression if the cost is not expensive and
   /// set the cost in \p Cost to indicate that if it is cheaper or neutral to
   /// do the negation.
-  SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG, bool LegalOps,
-                               bool OptForSize, NegatibleCost &Cost,
-                               unsigned Depth = 0) const {
-    Cost = getNegatibleCost(Op, DAG, LegalOps, OptForSize, Depth);
-    if (Cost != NegatibleCost::Expensive)
-      return negateExpression(Op, DAG, LegalOps, OptForSize, Depth);
-    return SDValue();
-  }
+  virtual SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG,
+                                       bool LegalOps, bool OptForSize,
+                                       NegatibleCost &Cost,
+                                       unsigned Depth = 0) const;
 
   /// This is the helper function to return the newly negated expression only
   /// when the cost is cheaper.
   SDValue getCheaperNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                       bool LegalOps, bool OptForSize,
                                       unsigned Depth = 0) const {
-    if (getNegatibleCost(Op, DAG, LegalOps, OptForSize, Depth) ==
-        NegatibleCost::Cheaper)
-      return negateExpression(Op, DAG, LegalOps, OptForSize, Depth);
+    NegatibleCost Cost = NegatibleCost::Expensive;
+    SDValue Neg =
+        getNegatedExpression(Op, DAG, LegalOps, OptForSize, Cost, Depth);
+    if (Neg && Cost == NegatibleCost::Cheaper)
+      return Neg;
     return SDValue();
   }
 
   /// This is the helper function to return the newly negated expression if
   /// the cost is not expensive.
   SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG, bool LegalOps,
                                bool OptForSize, unsigned Depth = 0) const {
     NegatibleCost Cost = NegatibleCost::Expensive;
     return getNegatedExpression(Op, DAG, LegalOps, OptForSize, Cost, Depth);
   }
 
   //===--------------------------------------------------------------------===//
   // Lowering methods - These methods must be implemented by targets so that
   // the SelectionDAGBuilder code knows how to lower these.
   //
 
   /// This hook must be implemented to lower the incoming (formal) arguments,
   /// described by the Ins array, into the specified DAG. The implementation
   /// should fill in the InVals array with legal-type argument values, and
   /// return the resulting token chain value.
   virtual SDValue LowerFormalArguments(
       SDValue /*Chain*/, CallingConv::ID /*CallConv*/, bool /*isVarArg*/,
       const SmallVectorImpl<ISD::InputArg> & /*Ins*/, const SDLoc & /*dl*/,
       SelectionDAG & /*DAG*/, SmallVectorImpl<SDValue> & /*InVals*/) const {
     llvm_unreachable("Not Implemented");
   }
 
   /// This structure contains all information that is necessary for lowering
   /// calls. It is passed to TLI::LowerCallTo when the SelectionDAG builder
   /// needs to lower a call, and targets will see this struct in their LowerCall
   /// implementation.
   struct CallLoweringInfo {

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (!isa<ConstantSDNode>(Op.getOperand(0))) {
     DAG.getContext()->emitError("argument to '__builtin_return_address' must "
                                 "be a constant integer");
     return true;
   }
 
   return false;
 }
 
-TargetLowering::NegatibleCost
-TargetLowering::getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                 bool LegalOperations, bool ForCodeSize,
+SDValue TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
+                                             bool LegalOps, bool OptForSize,
+                                             NegatibleCost &Cost,
                                              unsigned Depth) const {
   // fneg is removable even if it has multiple uses.
-  if (Op.getOpcode() == ISD::FNEG)
-    return NegatibleCost::Cheaper;
+  if (Op.getOpcode() == ISD::FNEG) {
+    Cost = NegatibleCost::Cheaper;
+    return Op.getOperand(0);
+  }
 
-  // Don't allow anything with multiple uses unless we know it is free.
-  EVT VT = Op.getValueType();
+  // Don't recurse exponentially.
+  if (Depth > SelectionDAG::MaxRecursionDepth)
+    return SDValue();
+
+  // Pre-increment recursion depth for use in recursive calls.
+  ++Depth;
   const SDNodeFlags Flags = Op->getFlags();
   const TargetOptions &Options = DAG.getTarget().Options;
-  if (!Op.hasOneUse()) {
-    bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
-                        isFPExtFree(VT, Op.getOperand(0).getValueType());
-
-    // If we already have the use of the negated floating constant, it is free
-    // to negate it even it has multiple uses.
-    bool IsFreeConstant =
-        Op.getOpcode() == ISD::ConstantFP &&
-        !negateExpression(Op, DAG, LegalOperations, ForCodeSize).use_empty();
+  EVT VT = Op.getValueType();
+  unsigned Opcode = Op.getOpcode();
 
-    if (!IsFreeExtend && !IsFreeConstant)
-      return NegatibleCost::Expensive;
+  // 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();
   }
 
-  // Don't recurse exponentially.
-  if (Depth > SelectionDAG::MaxRecursionDepth)
-    return NegatibleCost::Expensive;
+  SDLoc DL(Op);
 
-  switch (Op.getOpcode()) {
+  switch (Opcode) {
   case ISD::ConstantFP: {
-    if (!LegalOperations)
-      return NegatibleCost::Neutral;
-
     // Don't invert constant FP values after legalization unless the target says
     // the negated constant is legal.
-    if (isOperationLegal(ISD::ConstantFP, VT) ||
+    bool IsOpLegal =
+        isOperationLegal(ISD::ConstantFP, VT) ||
         isFPImmLegal(neg(cast<ConstantFPSDNode>(Op)->getValueAPF()), VT,
-                     ForCodeSize))
-      return NegatibleCost::Neutral;
+                     OptForSize);
+
+    if (LegalOps && !IsOpLegal)
+      break;
+
+    APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
+    V.changeSign();
+    SDValue CFP = DAG.getConstantFP(V, DL, VT);
+
+    // If we already have the use of the negated floating constant, it is free
+    // to negate it even it has multiple uses.
+    if (!Op.hasOneUse() && CFP.use_empty())
       break;
+    Cost = NegatibleCost::Neutral;
+    return CFP;
   }
   case ISD::BUILD_VECTOR: {
     // Only permit BUILD_VECTOR of constants.
     if (llvm::any_of(Op->op_values(), [&](SDValue N) {
           return !N.isUndef() && !isa<ConstantFPSDNode>(N);
         }))
-      return NegatibleCost::Expensive;
-    if (!LegalOperations)
-      return NegatibleCost::Neutral;
-    if (isOperationLegal(ISD::ConstantFP, VT) &&
-        isOperationLegal(ISD::BUILD_VECTOR, VT))
-      return NegatibleCost::Neutral;
-    if (llvm::all_of(Op->op_values(), [&](SDValue N) {
-          return N.isUndef() ||
-                 isFPImmLegal(neg(cast<ConstantFPSDNode>(N)->getValueAPF()), VT,
-                              ForCodeSize);
-        }))
-      return NegatibleCost::Neutral;
       break;
-  }
-  case ISD::FADD: {
-    if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
-      return NegatibleCost::Expensive;
-
-    // After operation legalization, it might not be legal to create new FSUBs.
-    if (LegalOperations && !isOperationLegalOrCustom(ISD::FSUB, VT))
-      return NegatibleCost::Expensive;
-
-    // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
-    NegatibleCost V0 = getNegatibleCost(Op.getOperand(0), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1);
-    if (V0 != NegatibleCost::Expensive)
-      return V0;
-    // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
-    return getNegatibleCost(Op.getOperand(1), DAG, LegalOperations, ForCodeSize,
-                            Depth + 1);
-  }
-  case ISD::FSUB:
-    // We can't turn -(A-B) into B-A when we honor signed zeros.
-    if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
-      return NegatibleCost::Expensive;
-
-    // fold (fneg (fsub A, B)) -> (fsub B, A)
-    return NegatibleCost::Neutral;
-  case ISD::FMUL:
-  case ISD::FDIV: {
-    // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y) or (fmul X, (fneg Y))
-    NegatibleCost V0 = getNegatibleCost(Op.getOperand(0), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1);
-    if (V0 != NegatibleCost::Expensive)
-      return V0;
-
-    // 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)
-        return NegatibleCost::Expensive;
-
-    return getNegatibleCost(Op.getOperand(1), DAG, LegalOperations, ForCodeSize,
-                            Depth + 1);
-  }
-  case ISD::FMA:
-  case ISD::FMAD: {
-    if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
-      return NegatibleCost::Expensive;
-
-    // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
-    // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
-    NegatibleCost V2 = getNegatibleCost(Op.getOperand(2), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1);
-    if (NegatibleCost::Expensive == V2)
-      return NegatibleCost::Expensive;
-
-    // One of Op0/Op1 must be cheaply negatible, then select the cheapest.
-    NegatibleCost V0 = getNegatibleCost(Op.getOperand(0), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1);
-    NegatibleCost V1 = getNegatibleCost(Op.getOperand(1), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1);
-    NegatibleCost V01 = std::min(V0, V1);
-    if (V01 == NegatibleCost::Expensive)
-      return NegatibleCost::Expensive;
-    return std::min(V01, V2);
-  }
-
-  case ISD::FP_EXTEND:
-  case ISD::FP_ROUND:
-  case ISD::FSIN:
-    return getNegatibleCost(Op.getOperand(0), DAG, LegalOperations, ForCodeSize,
-                            Depth + 1);
-  }
-
-  return NegatibleCost::Expensive;
-}
-
-SDValue TargetLowering::negateExpression(SDValue Op, SelectionDAG &DAG,
-                                         bool LegalOps, bool OptForSize,
-                                         unsigned Depth) const {
-  // fneg is removable even if it has multiple uses.
-  if (Op.getOpcode() == ISD::FNEG)
-    return Op.getOperand(0);
 
-  assert(Depth <= SelectionDAG::MaxRecursionDepth &&
-         "negateExpression doesn't match getNegatibleCost");
+    bool IsOpLegal =
+        (isOperationLegal(ISD::ConstantFP, VT) &&
+         isOperationLegal(ISD::BUILD_VECTOR, VT)) ||
+        llvm::all_of(Op->op_values(), [&](SDValue N) {
+          return N.isUndef() ||
+                 isFPImmLegal(neg(cast<ConstantFPSDNode>(N)->getValueAPF()), VT,
+                              OptForSize);
+        });
 
-  // Pre-increment recursion depth for use in recursive calls.
-  ++Depth;
-  const SDNodeFlags Flags = Op->getFlags();
-  EVT VT = Op.getValueType();
-  unsigned Opcode = Op.getOpcode();
-  SDLoc DL(Op);
+    if (LegalOps && !IsOpLegal)
+      break;
 
-  switch (Opcode) {
-  case ISD::ConstantFP: {
-    APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
-    V.changeSign();
-    return DAG.getConstantFP(V, DL, VT);
-  }
-  case ISD::BUILD_VECTOR: {
     SmallVector<SDValue, 4> Ops;
     for (SDValue C : Op->op_values()) {
       if (C.isUndef()) {
         Ops.push_back(C);
         continue;
       }
       APFloat V = cast<ConstantFPSDNode>(C)->getValueAPF();
       V.changeSign();
       Ops.push_back(DAG.getConstantFP(V, DL, C.getValueType()));
     }
+    Cost = NegatibleCost::Neutral;
     return DAG.getBuildVector(VT, DL, Ops);
   }
   case ISD::FADD: {
+    if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
+      break;
+
+    // After operation legalization, it might not be legal to create new FSUBs.
+    if (LegalOps && !isOperationLegalOrCustom(ISD::FSUB, VT))
+      break;
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1);
-    assert((DAG.getTarget().Options.NoSignedZerosFPMath ||
-            Flags.hasNoSignedZeros()) &&
-           "Expected NSZ fp-flag");
 
     // fold (fneg (fadd X, Y)) -> (fsub (fneg X), Y)
-    NegatibleCost CostX = getNegatibleCost(X, DAG, LegalOps, OptForSize, Depth);
-    if (CostX != NegatibleCost::Expensive)
-      return DAG.getNode(ISD::FSUB, DL, VT,
-                         negateExpression(X, DAG, LegalOps, OptForSize, Depth),
-                         Y, Flags);
-
+    NegatibleCost CostX = NegatibleCost::Expensive;
+    SDValue NegX =
+        getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
     // fold (fneg (fadd X, Y)) -> (fsub (fneg Y), X)
-    return DAG.getNode(ISD::FSUB, DL, VT,
-                       negateExpression(Y, DAG, LegalOps, OptForSize, Depth), X,
-                       Flags);
+    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;
+      return DAG.getNode(ISD::FSUB, DL, VT, NegX, Y, Flags);
+    }
+
+    // Negate the Y if it is not expensive.
+    if (NegY) {
+      Cost = CostY;
+      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;
+
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1);
     // fold (fneg (fsub 0, Y)) -> Y
     if (ConstantFPSDNode *C = isConstOrConstSplatFP(X, /*AllowUndefs*/ true))
-      if (C->isZero())
+      if (C->isZero()) {
+        Cost = NegatibleCost::Cheaper;
         return Y;
+      }
 
     // fold (fneg (fsub X, Y)) -> (fsub Y, X)
+    Cost = NegatibleCost::Neutral;
     return DAG.getNode(ISD::FSUB, DL, VT, Y, X, Flags);
   }
   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 = getNegatibleCost(X, DAG, LegalOps, OptForSize, Depth);
-    if (CostX != NegatibleCost::Expensive)
-      return DAG.getNode(Opcode, DL, VT,
-                         negateExpression(X, DAG, LegalOps, OptForSize, Depth),
-                         Y, Flags);
 
+    // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
+    NegatibleCost CostX = NegatibleCost::Expensive;
+    SDValue NegX =
+        getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
-    return DAG.getNode(Opcode, DL, VT, X,
-                       negateExpression(Y, DAG, LegalOps, OptForSize, Depth),
-                       Flags);
+    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;
+      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;
+      return DAG.getNode(Opcode, DL, VT, X, NegY, Flags);
+    }
+    break;
   }
   case ISD::FMA:
   case ISD::FMAD: {
-    assert((DAG.getTarget().Options.NoSignedZerosFPMath ||
-            Flags.hasNoSignedZeros()) &&
-           "Expected NSZ fp-flag");
+    if (!Options.NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
+      break;
 
     SDValue X = Op.getOperand(0), Y = Op.getOperand(1), Z = Op.getOperand(2);
-    SDValue NegZ = negateExpression(Z, DAG, LegalOps, OptForSize, Depth);
-    NegatibleCost CostX = getNegatibleCost(X, DAG, LegalOps, OptForSize, Depth);
-    NegatibleCost CostY = getNegatibleCost(Y, DAG, LegalOps, OptForSize, Depth);
-    if (CostX <= CostY) {
-      // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
-      SDValue NegX = negateExpression(X, DAG, LegalOps, OptForSize, Depth);
+    NegatibleCost CostZ = NegatibleCost::Expensive;
+    SDValue NegZ =
+        getNegatedExpression(Z, DAG, LegalOps, OptForSize, CostZ, Depth);
+    // Give up if fail to negate the Z.
+    if (!NegZ)
+      break;
+
+    NegatibleCost CostX = NegatibleCost::Expensive;
+    SDValue NegX =
+        getNegatedExpression(X, DAG, LegalOps, OptForSize, CostX, Depth);
+    // 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);
       return DAG.getNode(Opcode, DL, VT, NegX, Y, NegZ, Flags);
     }
 
-    // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
-    SDValue NegY = negateExpression(Y, DAG, LegalOps, OptForSize, Depth);
+    // Negate the Y if it is not expensive.
+    if (NegY) {
+      Cost = std::min(CostY, CostZ);
       return DAG.getNode(Opcode, DL, VT, X, NegY, NegZ, Flags);
     }
+    break;
+  }
 
   case ISD::FP_EXTEND:
   case ISD::FSIN:
-    return DAG.getNode(
-        Opcode, DL, VT,
-        negateExpression(Op.getOperand(0), DAG, LegalOps, OptForSize, Depth));
+    if (SDValue NegV = getNegatedExpression(Op.getOperand(0), DAG, LegalOps,
+                                            OptForSize, Cost, Depth))
+      return DAG.getNode(Opcode, DL, VT, NegV);
+    break;
   case ISD::FP_ROUND:
-    return DAG.getNode(
-        ISD::FP_ROUND, DL, VT,
-        negateExpression(Op.getOperand(0), DAG, LegalOps, OptForSize, Depth),
-        Op.getOperand(1));
+    if (SDValue NegV = getNegatedExpression(Op.getOperand(0), DAG, LegalOps,
+                                            OptForSize, Cost, Depth))
+      return DAG.getNode(ISD::FP_ROUND, DL, VT, NegV, Op.getOperand(1));
+    break;
   }
 
-  llvm_unreachable("Unknown code");
+  return SDValue();
 }
 
 //===----------------------------------------------------------------------===//
 // Legalization Utilities
 //===----------------------------------------------------------------------===//
 
 bool TargetLowering::expandMUL_LOHI(unsigned Opcode, EVT VT, SDLoc dl,
                                     SDValue LHS, SDValue RHS,

llvm/lib/Target/AMDGPU/AMDGPUISelLowering.h

public:
   bool isFNegFree(EVT VT) const override;
   bool isTruncateFree(EVT Src, EVT Dest) const override;
   bool isTruncateFree(Type *Src, Type *Dest) const override;
 
   bool isZExtFree(Type *Src, Type *Dest) const override;
   bool isZExtFree(EVT Src, EVT Dest) const override;
   bool isZExtFree(SDValue Val, EVT VT2) const override;
 
-  NegatibleCost getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                 bool LegalOperations, bool ForCodeSize,
-                                 unsigned Depth) const override;
+  SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG,
+                               NegatibleCost &Cost,
 
   bool isNarrowingProfitable(EVT VT1, EVT VT2) const override;
 
   EVT getTypeForExtReturn(LLVMContext &Context, EVT VT,
                           ISD::NodeType ExtendKind) const override;
 
   MVT getVectorIdxTy(const DataLayout &) const override;
   bool isSelectSupported(SelectSupportKind) const override;

llvm/lib/Target/AMDGPU/AMDGPUISelLowering.cpp

case ISD::LOAD:
           AMDGPUAS::CONSTANT_ADDRESS_32BIT)
         return true;
       return false;
     }
     break;
   }
 }
 
-TargetLowering::NegatibleCost
-AMDGPUTargetLowering::getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                       bool LegalOperations, bool ForCodeSize,
-                                       unsigned Depth) const {
+SDValue AMDGPUTargetLowering::getNegatedExpression(
+    SDValue Op, SelectionDAG &DAG, bool LegalOperations, bool ForCodeSize,
+    NegatibleCost &Cost, unsigned Depth) const {
+
   switch (Op.getOpcode()) {
   case ISD::FMA:
   case ISD::FMAD: {
     // Negating a fma is not free if it has users without source mods.
     if (!allUsesHaveSourceMods(Op.getNode()))
-      return NegatibleCost::Expensive;
+      return SDValue();
     break;
   }
   default:
     break;
   }
 
-  return TargetLowering::getNegatibleCost(Op, DAG, LegalOperations, ForCodeSize,
-                                          Depth);
+  return TargetLowering::getNegatedExpression(Op, DAG, LegalOperations,
+                                              ForCodeSize, Cost, Depth);
 }
 
 //===---------------------------------------------------------------------===//
 // Target Properties
 //===---------------------------------------------------------------------===//
 
 bool AMDGPUTargetLowering::isFAbsFree(EVT VT) const {
   assert(VT.isFloatingPoint());

llvm/lib/Target/X86/X86ISelLowering.h

public:
     bool isTypeDesirableForOp(unsigned Opc, EVT VT) const override;
 
     /// Return true if the target has native support for the
     /// specified value type and it is 'desirable' to use the type. e.g. On x86
     /// i16 is legal, but undesirable since i16 instruction encodings are longer
     /// and some i16 instructions are slow.
     bool IsDesirableToPromoteOp(SDValue Op, EVT &PVT) const override;
 
-    /// Returns whether computing the negated form of the specified expression
-    /// is more expensive, the same cost or cheaper.
-    NegatibleCost getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                   bool LegalOperations, bool ForCodeSize,
-                                   unsigned Depth) const override;
-
-    /// If getNegatibleCost returns Neutral/Cheaper, return the newly negated
-    /// expression.
-    SDValue negateExpression(SDValue Op, SelectionDAG &DAG,
+    /// Return the newly negated expression if the cost is not expensive and
+    /// set the cost in \p Cost to indicate that if it is cheaper or neutral to
+    /// do the negation.
+    SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                  bool LegalOperations, bool ForCodeSize,
+                                 NegatibleCost &Cost,
                                  unsigned Depth) const override;
 
     MachineBasicBlock *
     EmitInstrWithCustomInserter(MachineInstr &MI,
                                 MachineBasicBlock *MBB) const override;
 
     /// This method returns the name of a target specific DAG node.
     const char *getTargetNodeName(unsigned Opcode) const override;
 

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue combineFneg(SDNode *N, SelectionDAG &DAG,
   bool LegalOperations = !DCI.isBeforeLegalizeOps();
   if (SDValue NegArg =
           TLI.getNegatedExpression(Arg, DAG, LegalOperations, CodeSize))
     return DAG.getBitcast(OrigVT, NegArg);
 
   return SDValue();
 }
 
-TargetLowering::NegatibleCost
-X86TargetLowering::getNegatibleCost(SDValue Op, SelectionDAG &DAG,
-                                    bool LegalOperations, bool ForCodeSize,
-                                    unsigned Depth) const {
-  // fneg patterns are removable even if they have multiple uses.
-  if (isFNEG(DAG, Op.getNode(), Depth))
-    return NegatibleCost::Cheaper;
-
-  // Don't recurse exponentially.
-  if (Depth > SelectionDAG::MaxRecursionDepth)
-    return NegatibleCost::Expensive;
-
-  EVT VT = Op.getValueType();
-  EVT SVT = VT.getScalarType();
-  switch (Op.getOpcode()) {
-  case ISD::FMA:
-  case X86ISD::FMSUB:
-  case X86ISD::FNMADD:
-  case X86ISD::FNMSUB:
-  case X86ISD::FMADD_RND:
-  case X86ISD::FMSUB_RND:
-  case X86ISD::FNMADD_RND:
-  case X86ISD::FNMSUB_RND: {
-    if (!Op.hasOneUse() || !Subtarget.hasAnyFMA() || !isTypeLegal(VT) ||
-        !(SVT == MVT::f32 || SVT == MVT::f64) ||
-        !isOperationLegal(ISD::FMA, VT))
-      break;
-
-    // This is always negatible for free but we might be able to remove some
-    // extra operand negations as well.
-    for (int i = 0; i != 3; ++i) {
-      NegatibleCost V = getNegatibleCost(Op.getOperand(i), DAG, LegalOperations,
-                                         ForCodeSize, Depth + 1);
-      if (V == NegatibleCost::Cheaper)
-        return V;
-    }
-    return NegatibleCost::Neutral;
-  }
-  case X86ISD::FRCP:
-    return getNegatibleCost(Op.getOperand(0), DAG, LegalOperations, ForCodeSize,
-                            Depth + 1);
-  }
-
-  return TargetLowering::getNegatibleCost(Op, DAG, LegalOperations, ForCodeSize,
-                                          Depth);
-}
-
-SDValue X86TargetLowering::negateExpression(SDValue Op, SelectionDAG &DAG,
+SDValue X86TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                                 bool LegalOperations,
                                                 bool ForCodeSize,
+                                                NegatibleCost &Cost,
                                                 unsigned Depth) const {
   // fneg patterns are removable even if they have multiple uses.
-  if (SDValue Arg = isFNEG(DAG, Op.getNode(), Depth))
+  if (SDValue Arg = isFNEG(DAG, Op.getNode(), Depth)) {
+    Cost = NegatibleCost::Cheaper;
     return DAG.getBitcast(Op.getValueType(), Arg);
+  }
 
   EVT VT = Op.getValueType();
   EVT SVT = VT.getScalarType();
   unsigned Opc = Op.getOpcode();
   switch (Opc) {
   case ISD::FMA:
   case X86ISD::FMSUB:
   case X86ISD::FNMADD:
for (int i = 0; i != 3; ++i)
       NewOps[i] = getCheaperNegatedExpression(
           Op.getOperand(i), DAG, LegalOperations, ForCodeSize, Depth + 1);
 
     bool NegA = !!NewOps[0];
     bool NegB = !!NewOps[1];
     bool NegC = !!NewOps[2];
     unsigned NewOpc = negateFMAOpcode(Opc, NegA != NegB, NegC, true);
 
+    Cost = (NegA || NegB || NegC) ? NegatibleCost::Cheaper
+                                  : NegatibleCost::Neutral;
+
     // Fill in the non-negated ops with the original values.
     for (int i = 0, e = Op.getNumOperands(); i != e; ++i)
       if (!NewOps[i])
         NewOps[i] = Op.getOperand(i);
     return DAG.getNode(NewOpc, SDLoc(Op), VT, NewOps);
   }
   case X86ISD::FRCP:
-    return DAG.getNode(Opc, SDLoc(Op), VT,
-                       negateExpression(Op.getOperand(0), DAG, LegalOperations,
-                                        ForCodeSize, Depth + 1));
+    if (SDValue NegOp0 =
+            getNegatedExpression(Op.getOperand(0), DAG, LegalOperations,
+                                 ForCodeSize, Cost, Depth + 1))
+      return DAG.getNode(Opc, SDLoc(Op), VT, NegOp0);
     break;
   }
 
-  return TargetLowering::negateExpression(Op, DAG, LegalOperations, ForCodeSize,
-                                          Depth);
+  return TargetLowering::getNegatedExpression(Op, DAG, LegalOperations,
+                                              ForCodeSize, Cost, Depth);
 }
 
 static SDValue lowerX86FPLogicOp(SDNode *N, SelectionDAG &DAG,
                                  const X86Subtarget &Subtarget) {
   MVT VT = N->getSimpleValueType(0);
   // If we have integer vector types available, use the integer opcodes.
   if (!VT.isVector() || !Subtarget.hasSSE2())
     return SDValue();

llvm/test/CodeGen/X86/neg_fp.ll

; CHECK-NEXT:    retl
   %t11 = fmul double %t, %t
   %t13 = fsub double %t11, %t
   %t14 = fneg double %t
   %t15 = fmul double %t, %t14
   %t16 = fmul double %t, %t15
   %t18 = fadd double %t16, %t7
   ret double %t18
 }
+
+; This would crash because the negated expression for %sub4
+; creates a new use of %sub1 and that alters the negated cost
+
+define float @fdiv_extra_use_changes_cost(float %a0, float %a1, float %a2) nounwind {
+; CHECK-LABEL: fdiv_extra_use_changes_cost:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pushl %eax
+; CHECK-NEXT:    movss {{.*#+}} xmm0 = mem[0],zero,zero,zero
+; CHECK-NEXT:    movss {{.*#+}} xmm1 = mem[0],zero,zero,zero
+; CHECK-NEXT:    subss {{[0-9]+}}(%esp), %xmm1
+; CHECK-NEXT:    movaps %xmm1, %xmm2
+; CHECK-NEXT:    mulss %xmm0, %xmm2
+; CHECK-NEXT:    subss %xmm1, %xmm0
+; CHECK-NEXT:    divss %xmm2, %xmm0
+; CHECK-NEXT:    movss %xmm0, (%esp)
+; CHECK-NEXT:    flds (%esp)
+; CHECK-NEXT:    popl %eax
+; CHECK-NEXT:    retl
+  %sub1 = fsub fast float %a0, %a1
+  %mul2 = fmul fast float %sub1, %a2
+  %neg = fneg fast float %a0
+  %add3 = fadd fast float %a1, %neg
+  %sub4 = fadd fast float %add3, %a2
+  %div5 = fdiv fast float %sub4, %mul2
+  ret float %div5
+}