[SDAG] fix crash in getNegatedExpression() from altered number of uses

[spatel]

Summary

We've discussed this problem before in D70975. Copying directly from that description:
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().

The problem was similarly partly fixed in D75501, but we missed that the same behavior could originate from fmul/fdiv.

This is another incomplete fix for the whole problem, but I think that requires integrating getNegatibleCost() and getNegatedExpression(), so that we can't alter costs between analysis and rewrite.

[steven.zhang]

Shall we also need to update the cost evaluation for FMUL/FDIV, that is calculating both operands and select the cheapest cost of them ? And it seems that FADD also have such issues. -(A+B)->-A - B or -B-A
Technical speaking, we can't have the same expensive cost for both operands when negating the expression but now, we indeed have sometimes. And we choose one by chance which also would have problems.

I am not clear on the origin design but I wonder if we can remove the check of cost before calling the getNegateExpression, but call it directly, which allow to be null value to avoid such kind of out of sync between these two calls.

[spatel]

In D76439#1932659, @steven.zhang wrote:

Shall we also need to update the cost evaluation for FMUL/FDIV, that is calculating both operands and select the cheapest cost of them ? And it seems that FADD also have such issues. -(A+B)->-A - B or -B-A
Technical speaking, we can't have the same expensive cost for both operands when negating the expression but now, we indeed have sometimes. And we choose one by chance which also would have problems.

Yes, this whole API is unsound - we need to rewrite it to be completely correct. But I think this change makes it at least a little bit safer and more similar to the FMA logic. I can add a FIXME comment for FADD, and try to come up with a similar failure case as this one.

I am not clear on the origin design but I wonder if we can remove the check of cost before calling the getNegateExpression, but call it directly, which allow to be null value to avoid such kind of out of sync between these two calls.

Yes, if I understand correctly, we will need to integrate the cost+rewrite functions, so they are always in sync.

[steven.zhang]

We need to update the cost as they are pair. For now, it returns the first operand immediately if it is not expensive. But it could be neutral. And we will have problems if the cost of second operand is cheap. Because we should return cheap, but now, it is neutral. Does it make sense ?

[spatel]

In D76439#1935992, @steven.zhang wrote:

We need to update the cost as they are pair. For now, it returns the first operand immediately if it is not expensive. But it could be neutral. And we will have problems if the cost of second operand is cheap. Because we should return cheap, but now, it is neutral. Does it make sense ?

Sorry, but I'm not understanding. With this patch we have fneg (fmul/fdiv X, Y):

1. CostX == cheaper == 2; CostY == cheaper == 2 --> negate X
2. CostX == cheaper == 2; CostY == neutral == 1 --> negate X
3. CostX == neutral == 1; CostY == cheaper ==2 --> negate Y
4. CostX == neutral == 1; CostY == neutral == 1 --> negate X

But I have an alternate idea to avoid the crash that is probably a better fix given the current logic:
D76638

[steven.zhang]

In D76439#1937652, @spatel wrote:

In D76439#1935992, @steven.zhang wrote:

We need to update the cost as they are pair. For now, it returns the first operand immediately if it is not expensive. But it could be neutral. And we will have problems if the cost of second operand is cheap. Because we should return cheap, but now, it is neutral. Does it make sense ?

Sorry, but I'm not understanding. With this patch we have fneg (fmul/fdiv X, Y):

1. CostX == cheaper == 2; CostY == cheaper == 2 --> negate X
2. CostX == cheaper == 2; CostY == neutral == 1 --> negate X
3. CostX == neutral == 1; CostY == cheaper ==2 --> negate Y
4. CostX == neutral == 1; CostY == neutral == 1 --> negate X

But I have an alternate idea to avoid the crash that is probably a better fix given the current logic:
D76638

I mean when evaluating the cost of fmul/fdiv X, Y, not the logic inside getNegatedExpression, but the logic inside getNegatibleCost. We have:

• CostX == neutral == 1; CostY == cheaper --> Cost(fmul/fdiv) == neutral (Wrong)

This is the code.

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)    // Steven: if it is neutral, we should not return immediately, we need to check the cost of operand 2 and compare them.
    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);

[spatel]

Abandoning - D77319 will solve the larger problem.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (ConstantFPSDNode *C = isConstOrConstSplatFP(X, /*AllowUndefs*/ true))
         return Y;
 
     // fold (fneg (fsub X, Y)) -> (fsub Y, X)
     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)
+    NegatibleCost CostY = getNegatibleCost(Y, DAG, LegalOps, OptForSize, Depth);
+    // TODO: The comparison is inverted from what we might expect of a "cost"
+    //       because the enum values have "Cheaper" with a larger numerical
+    //       value than "Expensive".
+    if (CostX >= CostY)
+      // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
       return DAG.getNode(
           Opcode, DL, VT,
           getNegatedExpression(X, DAG, LegalOps, OptForSize, Depth), Y, Flags);
 
     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
     return DAG.getNode(
         Opcode, DL, VT, X,
         getNegatedExpression(Y, DAG, LegalOps, OptForSize, Depth), Flags);

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:    movss {{.*#+}} xmm2 = mem[0],zero,zero,zero
+; CHECK-NEXT:    movaps %xmm2, %xmm3
+; CHECK-NEXT:    subss %xmm1, %xmm3
+; CHECK-NEXT:    subss %xmm2, %xmm1
+; CHECK-NEXT:    mulss %xmm0, %xmm1
+; CHECK-NEXT:    subss %xmm0, %xmm3
+; CHECK-NEXT:    divss %xmm1, %xmm3
+; CHECK-NEXT:    movss %xmm3, (%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
+}