This is an archive of the discontinued LLVM Phabricator instance.

Differential D75501

[DAGCombine] Check the uses of negated floating constant and remove the hack
ClosedPublic

Authored by steven.zhang on Mar 2 2020, 11:19 PM.

Details

Reviewers
spatel
lebedev.ri
craig.topper
arsenm
RKSimon
rampitec
nemanjai
jsji
Group Reviewers
Restricted Project
Commits
rG76ceebb0d963: [DAGCombine] Check the uses of negated floating constant and remove the hack
rG3906ae387f07: [DAGCombine] Check the uses of negated floating constant and remove the hack
Summary

This patch is motivated by the case I added in PowerPC/fma-combine.ll, and we hit an assertion here due to somewhat the same reason as https://reviews.llvm.org/D70975 . The case is narrowed down from spec and it is important to us. Though we have some hack, it still failed with my case, as the operand 0 now is NOT a const fp, it is another fma that with const fp. And that const fp is negated which result in multi-uses.

So, I think a better fix is to check the uses of the negated const fp. If there are already use of its negated value, we will have benefit as no extra Node is added.

Diff Detail

Unit TestsFailed

TimeTest
3,900 msLLVM.CodeGen/PowerPC::Unknown Unit Message ("")
20 msLLVM.CodeGen/PowerPC::Unknown Unit Message ("")
60 msLLVM.CodeGen/PowerPC::Unknown Unit Message ("")

Event Timeline

steven.zhang created this revision.Mar 2 2020, 11:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2020, 11:19 PM
Herald added subscribers: kerbowa, • wuzish, hiraditya and 3 others. · View Herald Transcript
Harbormaster completed remote builds in B47865: Diff 247798.Mar 3 2020, 12:49 AM
steven.zhang updated this revision to Diff 247839.Mar 3 2020, 2:49 AM
Harbormaster completed remote builds in B47888: Diff 247839.Mar 3 2020, 5:02 AM
spatel added inline comments.Mar 3 2020, 5:59 AM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5569–5584

This is difficult to read. Please add some intermediate names (maybe as shown below).

It's not clear to me if that's the logic we want - is this a good or better fix for the problem?

bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
                    isFPExtFree(VT, Op.getOperand(0).getValueType());
bool IsFreeConstant =
    Op.getOpcode() == ISD::ConstantFP &&
    !getNegatedExpression(Op, DAG, LegalOperations, ForCodeSize).use_empty();
if (!Op.hasOneUse() && !IsFreeExtend && !IsFreeConstant)
  return NegatibleCost::Expensive;
RKSimon added inline comments.Mar 3 2020, 8:53 AM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5569–5584
if (!Op.hasOneUse()) {
  bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
                    isFPExtFree(VT, Op.getOperand(0).getValueType());
  if (!IsFreeExtend)
    return NegatibleCost::Expensive;

  bool IsFreeConstant = Op.getOpcode() == ISD::ConstantFP &&
        !getNegatedExpression(Op, DAG, LegalOperations, ForCodeSize).use_empty();
  if (!IsFreeConstant)
    return NegatibleCost::Expensive;
}
steven.zhang updated this revision to Diff 248080.Mar 3 2020, 5:48 PM

Update the patch to make it more clear and fix an issue of counting the uses.

steven.zhang marked an inline comment as done.Mar 3 2020, 6:24 PM
steven.zhang added inline comments.
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
5569–5584

Yes, that is exactly what I mean, thank you for the code and I have updated the patch.
Regarding to spatel's question, currently, we are doing special handling for const fp when we don't know which one has better cost. My idea is to remove this special handling and improve the evaluation of the cost for const fp to make it more precise, then reduce the chance that we cannot determine which one is better. Does it make sense ?

And moreover, the special handling cannot handle all the cases. I have added another case in my patch to demonstrate the issue. This is what my case looks like:

t0  =   t1   x    t2   +    t3
        +                   +
        v                   v
 t3  x 42.0 - 1.0       t4  +  1.0
  +
  v
 -t4

We are now negating the expression "t0", so t3 is negated first, which is "-t4 - 1.0". And then, we need to decide to negate t1 or t3 which hit the hack code. So, we call the getNegatibleCost to make the decision. Unfortunately, both are expensive as the operand "-1.0" of expression "t1" now has multiple use. The hack here won't help as it is just checking "t1" and "t2".

Harbormaster failed remote builds in B48007: Diff 248080!Mar 3 2020, 6:30 PM
steven.zhang updated this revision to Diff 248083.Mar 3 2020, 7:06 PM

Fix the logic bug ...

Harbormaster completed remote builds in B48008: Diff 248083.Mar 3 2020, 9:15 PM
spatel accepted this revision.Mar 4 2020, 4:59 AM

LGTM

This revision is now accepted and ready to land.Mar 4 2020, 4:59 AM
Closed by commit rG3906ae387f07: [DAGCombine] Check the uses of negated floating constant and remove the hack (authored by steven.zhang). · Explain WhyMar 4 2020, 8:07 PM
This revision was automatically updated to reflect the committed changes.
spatel mentioned this in D76439: [SDAG] fix crash in getNegatedExpression() from altered number of uses.Mar 19 2020, 11:23 AM
steven.zhang mentioned this in D77319: [DAGCombine] Remove the getNegatibleCost to avoid the out of sync with getNegatedExpression.Apr 3 2020, 1:00 AM

Revision Contents

PathSize
llvm/
lib/
CodeGen/
SelectionDAG/
27 lines
test/
CodeGen/
PowerPC/
101 lines

Diff 248080

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 5,560 Lines • ▼ Show 20 LinesTargetLowering::getNegatibleCost(SDValue Op, SelectionDAG &DAG,
unsigned Depth) const { unsigned Depth) const {
// fneg is removable even if it has multiple uses. // fneg is removable even if it has multiple uses.
if (Op.getOpcode() == ISD::FNEG) if (Op.getOpcode() == ISD::FNEG)
return NegatibleCost::Cheaper; return NegatibleCost::Cheaper;
// Don't allow anything with multiple uses unless we know it is free. // Don't allow anything with multiple uses unless we know it is free.
EVT VT = Op.getValueType(); EVT VT = Op.getValueType();
const SDNodeFlags Flags = Op->getFlags(); const SDNodeFlags Flags = Op->getFlags();
const TargetOptions &Options = DAG.getTarget().Options; const TargetOptions &Options = DAG.getTarget().Options;
if (!Op.hasOneUse() && !(Op.getOpcode() == ISD::FP_EXTEND && if (!Op.hasOneUse()) {
isFPExtFree(VT, Op.getOperand(0).getValueType()))) bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
isFPExtFree(VT, Op.getOperand(0).getValueType());
if (!IsFreeExtend)
return NegatibleCost::Expensive; return NegatibleCost::Expensive;
// 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 &&
!getNegatedExpression(Op, DAG, LegalOperations, ForCodeSize)
.use_empty();
if (!IsFreeConstant)
return NegatibleCost::Expensive;
}
spatelUnsubmitted
Not Done
ReplyInline Actions

This is difficult to read. Please add some intermediate names (maybe as shown below).

It's not clear to me if that's the logic we want - is this a good or better fix for the problem?

bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
                    isFPExtFree(VT, Op.getOperand(0).getValueType());
bool IsFreeConstant =
    Op.getOpcode() == ISD::ConstantFP &&
    !getNegatedExpression(Op, DAG, LegalOperations, ForCodeSize).use_empty();
if (!Op.hasOneUse() && !IsFreeExtend && !IsFreeConstant)
  return NegatibleCost::Expensive;
spatel: This is difficult to read. Please add some intermediate names (maybe as shown below). It's not…
RKSimonUnsubmitted
Not Done
ReplyInline Actions
if (!Op.hasOneUse()) {
  bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&
                    isFPExtFree(VT, Op.getOperand(0).getValueType());
  if (!IsFreeExtend)
    return NegatibleCost::Expensive;

  bool IsFreeConstant = Op.getOpcode() == ISD::ConstantFP &&
        !getNegatedExpression(Op, DAG, LegalOperations, ForCodeSize).use_empty();
  if (!IsFreeConstant)
    return NegatibleCost::Expensive;
}
RKSimon: ``` if (!Op.hasOneUse()) { bool IsFreeExtend = Op.getOpcode() == ISD::FP_EXTEND &&…
steven.zhangAuthorUnsubmitted
Done
ReplyInline Actions

Yes, that is exactly what I mean, thank you for the code and I have updated the patch.
Regarding to spatel's question, currently, we are doing special handling for const fp when we don't know which one has better cost. My idea is to remove this special handling and improve the evaluation of the cost for const fp to make it more precise, then reduce the chance that we cannot determine which one is better. Does it make sense ?

And moreover, the special handling cannot handle all the cases. I have added another case in my patch to demonstrate the issue. This is what my case looks like:

t0  =   t1   x    t2   +    t3
        +                   +
        v                   v
 t3  x 42.0 - 1.0       t4  +  1.0
  +
  v
 -t4

We are now negating the expression "t0", so t3 is negated first, which is "-t4 - 1.0". And then, we need to decide to negate t1 or t3 which hit the hack code. So, we call the getNegatibleCost to make the decision. Unfortunately, both are expensive as the operand "-1.0" of expression "t1" now has multiple use. The hack here won't help as it is just checking "t1" and "t2".

steven.zhang: Yes, that is exactly what I mean, thank you for the code and I have updated the patch.
// Don't recurse exponentially. // Don't recurse exponentially.
if (Depth > SelectionDAG::MaxRecursionDepth) if (Depth > SelectionDAG::MaxRecursionDepth)
return NegatibleCost::Expensive; return NegatibleCost::Expensive;
switch (Op.getOpcode()) { switch (Op.getOpcode()) {
case ISD::ConstantFP: { case ISD::ConstantFP: {
if (!LegalOperations) if (!LegalOperations)
return NegatibleCost::Neutral; return NegatibleCost::Neutral;
▲ Show 20 Lines • Show All 188 Lines • ▼ Show 20 Lines case ISD::FMAD: {
SDValue Neg2 = getNegatedExpression(Op.getOperand(2), DAG, LegalOperations, SDValue Neg2 = getNegatedExpression(Op.getOperand(2), DAG, LegalOperations,
ForCodeSize, Depth + 1); ForCodeSize, Depth + 1);
NegatibleCost V0 = getNegatibleCost(Op.getOperand(0), DAG, LegalOperations, NegatibleCost V0 = getNegatibleCost(Op.getOperand(0), DAG, LegalOperations,
ForCodeSize, Depth + 1); ForCodeSize, Depth + 1);
NegatibleCost V1 = getNegatibleCost(Op.getOperand(1), DAG, LegalOperations, NegatibleCost V1 = getNegatibleCost(Op.getOperand(1), DAG, LegalOperations,
ForCodeSize, Depth + 1); ForCodeSize, Depth + 1);
// TODO: This is a hack. It is possible that costs have changed between now if (V0 > V1) {
// and the initial calls to getNegatibleCost(). 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. A better fix would eliminate uses as a cost factor or
// track the change in uses as we rewrite the expression.
if (V0 > V1 || (V0 == V1 && isa<ConstantFPSDNode>(Op.getOperand(0)))) {
// fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z)) // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
SDValue Neg0 = getNegatedExpression( SDValue Neg0 = getNegatedExpression(
Op.getOperand(0), DAG, LegalOperations, ForCodeSize, Depth + 1); Op.getOperand(0), DAG, LegalOperations, ForCodeSize, Depth + 1);
return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(), Neg0, return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(), Neg0,
Op.getOperand(1), Neg2, Flags); Op.getOperand(1), Neg2, Flags);
} }
// fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z)) // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
▲ Show 20 Lines • Show All 1,934 Lines • Show Last 20 Lines

llvm/test/CodeGen/PowerPC/fma-combine.ll

Show First 20 Lines • Show All 131 Lines • ▼ Show 20 Lines
entry: entry:
%fneg = fneg double %a %fneg = fneg double %a
store double %fneg, double* @v, align 8 store double %fneg, double* @v, align 8
%fneg1 = fneg double %c %fneg1 = fneg double %c
%mul = fmul double %fneg1, %b %mul = fmul double %fneg1, %b
%add = fsub double %mul, %a %add = fsub double %mul, %a
ret double %add ret double %add
} }
define float @fma_combine_no_ice() {
; CHECK-FAST-LABEL: fma_combine_no_ice:
; CHECK-FAST: # %bb.0:
; CHECK-FAST-NEXT: addis 3, 2, .LCPI4_0@toc@ha
; CHECK-FAST-NEXT: addis 4, 2, .LCPI4_1@toc@ha
; CHECK-FAST-NEXT: lfs 0, .LCPI4_0@toc@l(3)
; CHECK-FAST-NEXT: lfsx 2, 0, 3
; CHECK-FAST-NEXT: addis 3, 2, .LCPI4_2@toc@ha
; CHECK-FAST-NEXT: lfs 3, .LCPI4_1@toc@l(4)
; CHECK-FAST-NEXT: lfs 1, .LCPI4_2@toc@l(3)
; CHECK-FAST-NEXT: xsmaddasp 3, 2, 0
; CHECK-FAST-NEXT: xsmaddasp 1, 2, 3
; CHECK-FAST-NEXT: xsnmsubasp 1, 3, 2
; CHECK-FAST-NEXT: blr
;
; CHECK-FAST-NOVSX-LABEL: fma_combine_no_ice:
; CHECK-FAST-NOVSX: # %bb.0:
; CHECK-FAST-NOVSX-NEXT: addis 3, 2, .LCPI4_0@toc@ha
; CHECK-FAST-NOVSX-NEXT: lfs 0, .LCPI4_0@toc@l(3)
; CHECK-FAST-NOVSX-NEXT: addis 3, 2, .LCPI4_1@toc@ha
; CHECK-FAST-NOVSX-NEXT: lfs 1, 0(3)
; CHECK-FAST-NOVSX-NEXT: lfs 2, .LCPI4_1@toc@l(3)
; CHECK-FAST-NOVSX-NEXT: addis 3, 2, .LCPI4_2@toc@ha
; CHECK-FAST-NOVSX-NEXT: fmadds 0, 1, 2, 0
; CHECK-FAST-NOVSX-NEXT: lfs 2, .LCPI4_2@toc@l(3)
; CHECK-FAST-NOVSX-NEXT: fmadds 2, 1, 0, 2
; CHECK-FAST-NOVSX-NEXT: fnmsubs 1, 0, 1, 2
; CHECK-FAST-NOVSX-NEXT: blr
;
; CHECK-LABEL: fma_combine_no_ice:
; CHECK: # %bb.0:
; CHECK-NEXT: addis 3, 2, .LCPI4_0@toc@ha
; CHECK-NEXT: addis 4, 2, .LCPI4_1@toc@ha
; CHECK-NEXT: lfs 0, .LCPI4_0@toc@l(3)
; CHECK-NEXT: lfsx 2, 0, 3
; CHECK-NEXT: addis 3, 2, .LCPI4_2@toc@ha
; CHECK-NEXT: lfs 3, .LCPI4_1@toc@l(4)
; CHECK-NEXT: lfs 1, .LCPI4_2@toc@l(3)
; CHECK-NEXT: xsmaddasp 3, 2, 0
; CHECK-NEXT: xsmaddasp 1, 2, 3
; CHECK-NEXT: xsnmsubasp 1, 3, 2
; CHECK-NEXT: blr
%tmp = load float, float* undef, align 4
%tmp2 = load float, float* undef, align 4
%tmp3 = fmul fast float %tmp, 0x3FE372D780000000
%tmp4 = fadd fast float %tmp3, 1.000000e+00
%tmp5 = fmul fast float %tmp2, %tmp4
%tmp6 = load float, float* undef, align 4
%tmp7 = load float, float* undef, align 4
%tmp8 = fmul fast float %tmp7, 0x3FE372D780000000
%tmp9 = fsub fast float -1.000000e+00, %tmp8
%tmp10 = fmul fast float %tmp9, %tmp6
%tmp11 = fadd fast float %tmp5, 5.000000e-01
%tmp12 = fadd fast float %tmp11, %tmp10
ret float %tmp12
}
; This would crash while trying getNegatedExpression().
define double @getNegatedExpression_crash(double %x, double %y) {
; CHECK-FAST-LABEL: getNegatedExpression_crash:
; CHECK-FAST: # %bb.0:
; CHECK-FAST-NEXT: addis 3, 2, .LCPI5_1@toc@ha
; CHECK-FAST-NEXT: addis 4, 2, .LCPI5_0@toc@ha
; CHECK-FAST-NEXT: lfs 3, .LCPI5_1@toc@l(3)
; CHECK-FAST-NEXT: lfs 4, .LCPI5_0@toc@l(4)
; CHECK-FAST-NEXT: xssubdp 0, 1, 3
; CHECK-FAST-NEXT: xsmaddadp 3, 1, 4
; CHECK-FAST-NEXT: xsmaddadp 0, 3, 2
; CHECK-FAST-NEXT: fmr 1, 0
; CHECK-FAST-NEXT: blr
;
; CHECK-FAST-NOVSX-LABEL: getNegatedExpression_crash:
; CHECK-FAST-NOVSX: # %bb.0:
; CHECK-FAST-NOVSX-NEXT: addis 3, 2, .LCPI5_0@toc@ha
; CHECK-FAST-NOVSX-NEXT: addis 4, 2, .LCPI5_1@toc@ha
; CHECK-FAST-NOVSX-NEXT: lfs 0, .LCPI5_0@toc@l(3)
; CHECK-FAST-NOVSX-NEXT: lfs 3, .LCPI5_1@toc@l(4)
; CHECK-FAST-NOVSX-NEXT: fmadd 3, 1, 3, 0
; CHECK-FAST-NOVSX-NEXT: fsub 0, 1, 0
; CHECK-FAST-NOVSX-NEXT: fmadd 1, 3, 2, 0
; CHECK-FAST-NOVSX-NEXT: blr
;
; CHECK-LABEL: getNegatedExpression_crash:
; CHECK: # %bb.0:
; CHECK-NEXT: addis 3, 2, .LCPI5_1@toc@ha
; CHECK-NEXT: addis 4, 2, .LCPI5_0@toc@ha
; CHECK-NEXT: lfs 3, .LCPI5_1@toc@l(3)
; CHECK-NEXT: lfs 4, .LCPI5_0@toc@l(4)
; CHECK-NEXT: xssubdp 0, 1, 3
; CHECK-NEXT: xsmaddadp 3, 1, 4
; CHECK-NEXT: xsmaddadp 0, 3, 2
; CHECK-NEXT: fmr 1, 0
; CHECK-NEXT: blr
%neg = fneg fast double %x
%fma = call fast double @llvm.fma.f64(double %neg, double 42.0, double -1.0)
%add = fadd fast double %x, 1.0
%fma1 = call fast double @llvm.fma.f64(double %fma, double %y, double %add)
ret double %fma1
}
declare double @llvm.fma.f64(double, double, double) nounwind readnone