Re: [PATCH Take 2] More NEGATE_EXPR folding in match.pd
On Fri, Sep 10, 2021 at 11:22 AM Roger Sayle wrote:
>
>
> Hi Richard,
> Thanks for suggestion, which cleanly solves the problem I was encountering.
> This revised patch adds a Boolean simplify argument to tree-ssa-sccvn.c's
> vn_nary_build_or_lookup_1 to control whether to simplification should be
> performed before value numbering, updating the callers, but then
> avoiding simplification when constructing/value-numbering NEGATE_EXPR.
> This avoids the regression of gcc.dg/tree-ssa/ssa-free-88.c, and enables the
> new test case(s) to pass. Brilliant, thank you.
>
> This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap"
> and "make -k check" with no new failures. Ok for mainline?
OK (sorry for the delay).
>
>
> 2021-09-10 Roger Sayle
> Richard Biener
>
> gcc/ChangeLog
> * match.pd (negation simplifications): Implement some negation
> folding transformations from fold-const.c's fold_negate_expr.
> * tree-ssa-sccvn.c (vn_nary_build_or_lookup_1): Add a SIMPLIFY
> argument, to control whether the op should be simplified prior
> to looking up/assigning a value number.
> (vn_nary_build_or_lookup): Update call to vn_nary_build_or_lookup_1.
> (vn_nary_simplify): Likewise.
> (visit_nary_op): Likewise, but when constructing a NEGATE_EXPR
> now call vn_nary_build_or_lookup_1 disabling simplification.
>
> gcc/testsuite/ChangeLog
> * gcc.dg/fold-negate-1.c: New test case.
>
>
> One potential enhancement request it might be useful to file in Bugzilla
> (I'm not familiar enough with sccvn to investigate this myself), but there's
> a missed optimization opportunity when we recognize one value-number
> as the negation of another (and can therefore materialize one result from
> the other using a single negation instruction). The opportunity is that we
> currently always select the first value number as the parent, and derive
> the second from it, ignoring the expressions themselves. Sometimes, it
> may be profitable to use the second (negated) occurrence as the parent,
> and instead negate that to obtain the first. One could use negate_expr_p
> to decide whether one expression is cheaper to negate than the other.
Note what VN does generally is limited by the order the expressions are
computed, we cannot generally derive something from an expression
computed later.
If we'd do the matching at elimination time we could possibly play
more tricks, like materializing the whole computation and hoping to
elide the redundant later one but that's currently not done.
Thanks,
Richard.
> Both examples in gcc.dg/tree-ssa/ssa-free-88.c would benefit from this:
> Firstly:
> void bar (double x, double z) {
> y[0] = -z / x;
> y[1] = z / x;
> }
> if we select "z / x" as the parent, and derive -(z/x) from it, we can avoid/
> eliminate a negation, over the current code that calculates "(-z)/x" and
> then derives "-((-z)/x)" from it.
> Secondly:
> void foo (double x) {
> y[0] = x * -3.;
> y[1] = x * 3.;
> }
> Following Richard's solution/workaround to PR 19988, we'd prefer to keep
> positive real constants in the constant pool, hence selecting "x * 3.0" as the
> parent and deriving "-(x * 3.0)" from it, would be slightly preferred over the
> current behaviour of placing -3 in the constant pool.
>
> Thanks again,
> --
> Roger
>
> -Original Message-
> From: Richard Biener
> Sent: 09 September 2021 13:05
> To: Roger Sayle
> Cc: GCC Patches
> Subject: Re: [PATCH] More NEGATE_EXPR folding in match.pd
>
> On Thu, Sep 9, 2021 at 12:08 PM Roger Sayle
> wrote:
> >
> >
> > As observed by Jakub in comment #2 of PR 98865, the expression
> > -(a>>63) is optimized in GENERIC but not in GIMPLE. Investigating
> > further it turns out that this is one of a few transformations
> > performed by fold_negate_expr in fold-const.c that aren't yet performed by
> > match.pd.
> > This patch moves/duplicates them there, and should be relatively safe
> > as these transformations are already performed by the compiler, but
> > just in different passes.
> >
> > Alas the one minor complication is that some of these transformations
> > are only wins, if the intermediate result (of the multiplication or
> > division) is only used once, to avoid duplication/performing them again.
> > See gcc.dg/tree-ssa/ssa-free-88.c. Normally, this is the perfect
> > usage of match's single_use (aka SSA's has_single_use). Alas,
> > single_use is not always accurate in match.pd, as some passes will
> > construct and simplify an expression/stmt before inserting it into
> > GIMPLE, and folding during this process sees the temporary undercount from
> > the data-flow.
> > To solve this, this patch introduces a new single_use_is_op_p that
> > double checks that the single_use has the expected tree_code/operation
> > and skips the transformation if we can tell single_use might be invalid.
> >
> > A follow-up patch might be to investigate whether
[PATCH Take 2] More NEGATE_EXPR folding in match.pd
Hi Richard,
Thanks for suggestion, which cleanly solves the problem I was encountering.
This revised patch adds a Boolean simplify argument to tree-ssa-sccvn.c's
vn_nary_build_or_lookup_1 to control whether to simplification should be
performed before value numbering, updating the callers, but then
avoiding simplification when constructing/value-numbering NEGATE_EXPR.
This avoids the regression of gcc.dg/tree-ssa/ssa-free-88.c, and enables the
new test case(s) to pass. Brilliant, thank you.
This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap"
and "make -k check" with no new failures. Ok for mainline?
2021-09-10 Roger Sayle
Richard Biener
gcc/ChangeLog
* match.pd (negation simplifications): Implement some negation
folding transformations from fold-const.c's fold_negate_expr.
* tree-ssa-sccvn.c (vn_nary_build_or_lookup_1): Add a SIMPLIFY
argument, to control whether the op should be simplified prior
to looking up/assigning a value number.
(vn_nary_build_or_lookup): Update call to vn_nary_build_or_lookup_1.
(vn_nary_simplify): Likewise.
(visit_nary_op): Likewise, but when constructing a NEGATE_EXPR
now call vn_nary_build_or_lookup_1 disabling simplification.
gcc/testsuite/ChangeLog
* gcc.dg/fold-negate-1.c: New test case.
One potential enhancement request it might be useful to file in Bugzilla
(I'm not familiar enough with sccvn to investigate this myself), but there's
a missed optimization opportunity when we recognize one value-number
as the negation of another (and can therefore materialize one result from
the other using a single negation instruction). The opportunity is that we
currently always select the first value number as the parent, and derive
the second from it, ignoring the expressions themselves. Sometimes, it
may be profitable to use the second (negated) occurrence as the parent,
and instead negate that to obtain the first. One could use negate_expr_p
to decide whether one expression is cheaper to negate than the other.
Both examples in gcc.dg/tree-ssa/ssa-free-88.c would benefit from this:
Firstly:
void bar (double x, double z) {
y[0] = -z / x;
y[1] = z / x;
}
if we select "z / x" as the parent, and derive -(z/x) from it, we can avoid/
eliminate a negation, over the current code that calculates "(-z)/x" and
then derives "-((-z)/x)" from it.
Secondly:
void foo (double x) {
y[0] = x * -3.;
y[1] = x * 3.;
}
Following Richard's solution/workaround to PR 19988, we'd prefer to keep
positive real constants in the constant pool, hence selecting "x * 3.0" as the
parent and deriving "-(x * 3.0)" from it, would be slightly preferred over the
current behaviour of placing -3 in the constant pool.
Thanks again,
--
Roger
-Original Message-
From: Richard Biener
Sent: 09 September 2021 13:05
To: Roger Sayle
Cc: GCC Patches
Subject: Re: [PATCH] More NEGATE_EXPR folding in match.pd
On Thu, Sep 9, 2021 at 12:08 PM Roger Sayle wrote:
>
>
> As observed by Jakub in comment #2 of PR 98865, the expression
> -(a>>63) is optimized in GENERIC but not in GIMPLE. Investigating
> further it turns out that this is one of a few transformations
> performed by fold_negate_expr in fold-const.c that aren't yet performed by
> match.pd.
> This patch moves/duplicates them there, and should be relatively safe
> as these transformations are already performed by the compiler, but
> just in different passes.
>
> Alas the one minor complication is that some of these transformations
> are only wins, if the intermediate result (of the multiplication or
> division) is only used once, to avoid duplication/performing them again.
> See gcc.dg/tree-ssa/ssa-free-88.c. Normally, this is the perfect
> usage of match's single_use (aka SSA's has_single_use). Alas,
> single_use is not always accurate in match.pd, as some passes will
> construct and simplify an expression/stmt before inserting it into
> GIMPLE, and folding during this process sees the temporary undercount from
> the data-flow.
> To solve this, this patch introduces a new single_use_is_op_p that
> double checks that the single_use has the expected tree_code/operation
> and skips the transformation if we can tell single_use might be invalid.
>
> A follow-up patch might be to investigate whether genmatch.c can be
> tweaked to use this new helper function to implement the :s qualifier
> when the enclosing context is/should be known, but that's overkill to
> just unblock Jakub and Andrew on 98865.
>
> This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap"
> and "make -k check" with no new failures. Ok for mainline?
I think that single_use_is_op_p is "bad" heuristics since it stretches the SSA
operand / immediate use use a bit too far. Generally fold_stmt and thus
match.pd patterns may not rely on stmt operands or immediate uses as only
generated by update_stmt.
In fact the whole
