From: Bill Schmidt <wschmidt@linux.vnet.ibm.com>
To: Richard Biener <richard.guenther@gmail.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Fix PR71815 (SLSR misses PHI opportunities)
Date: Tue, 20 Jun 2017 14:06:00 -0000 [thread overview]
Message-ID: <ACF8A9B8-540E-4999-A214-90A2B3D06987@linux.vnet.ibm.com> (raw)
In-Reply-To: <CAFiYyc3HQTTzRZ7Qf3iVEq6YgxE1hoar-vHs8W-Wt_zmNCi=Jg@mail.gmail.com>
On Jun 20, 2017, at 6:23 AM, Richard Biener <richard.guenther@gmail.com> wrote:
>
> On Fri, Jun 16, 2017 at 6:10 PM, Bill Schmidt
> <wschmidt@linux.vnet.ibm.com> wrote:
>> Hi,
>>
>> PR71815 identifies a situation where SLSR misses opportunities for
>> PHI candidates when code hoisting is enabled (which is now on by
>> default). The basic problem is that SLSR currently uses an overly
>> simple test for profitability of the transformation. The algorithm
>> currently requires that the PHI basis (through which the non-local
>> SLSR candidate is propagated) has only one use, which is the
>> candidate statement. The true requirement for profitability is
>> that, if the candidate statement will be dead after transformation,
>> then so will the PHI candidate.
>>
>> This patch fixes the problem by looking at the transitive reachability
>> of the PHI definitions. If all paths terminate in the candidate
>> statement, then we know the PHI basis will go dead and we will not
>> make the code worse with the planned replacement. To avoid compile
>> time issues, path search is arbitrarily terminated at depth 10. The
>> new test is used throughout the cost calculation, so appears multiple
>> times in the code.
>>
>> Also, I've added a check to avoid replacing multiply candidates with
>> a stride of 1. Such a candidate is really a copy or cast statement,
>> and if we replace it, we will just generate a different copy or cast
>> statement. I noticed this with one of the test cases from the PR
>> while debugging the problem.
>>
>> I've updated the two test cases that were previously enabled only
>> with -fno-code-hoisting, removing that restriction.
>>
>> Bootstrapped and tested on powerpc64le-unknown-linux-gnu with no
>> regressions. I've also tested this with SPEC cpu2006 and the
>> patch is performance neutral on a POWER8 box (as expected). Is
>> this ok for trunk?
>>
>> Thanks,
>> Bill
>>
>>
>> [gcc]
>>
>> 2016-06-16 Bill Schmidt <wschmidt@linux.vnet.ibm.com>
>>
>> * gimple-ssa-strength-reduction.c (uses_consumed_by_stmt): New
>> function.
>> (find_basis_for_candidate): Call uses_consumed_by_stmt rather than
>> has_single_use.
>> (slsr_process_phi): Likewise.
>> (replace_uncond_cands_and_profitable_phis): Don't replace a
>> multiply candidate with a stride of 1 (copy or cast).
>> (phi_incr_cost): Call uses_consumed_by_stmt rather than
>> has_single_use.
>> (lowest_cost_path): Likewise.
>> (total_savings): Likewise.
>>
>> [gcc/testsuite]
>>
>> 2016-06-16 Bill Schmidt <wschmidt@linux.vnet.ibm.com>
>>
>> * gcc.dg/tree-ssa/slsr-35.c: Remove -fno-code-hoisting workaround.
>> * gcc.dg/tree-ssa/slsr-36.c: Likewise.
>>
>>
>> Index: gcc/gimple-ssa-strength-reduction.c
>> ===================================================================
>> --- gcc/gimple-ssa-strength-reduction.c (revision 239241)
>> +++ gcc/gimple-ssa-strength-reduction.c (working copy)
>> @@ -475,6 +475,48 @@ find_phi_def (tree base)
>> return c->cand_num;
>> }
>>
>> +/* Determine whether all uses of NAME are directly or indirectly
>> + used by STMT. That is, we want to know whether if STMT goes
>> + dead, the definition of NAME also goes dead. */
>> +static bool
>> +uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse)
>
> use a default arg 'unsigned recurse = 0' to hide this implementation
> detail at users.
Good idea, thanks.
>
>> +{
>> + gimple *use_stmt;
>> + imm_use_iterator iter;
>> + bool retval = true;
>> +
>> + FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
>> + {
>> + if (use_stmt == stmt || is_gimple_debug (use_stmt))
>> + continue;
>> +
>> + if (!is_gimple_assign (use_stmt))
>> + {
>> + retval = false;
>> + BREAK_FROM_IMM_USE_STMT (iter);
>> + }
>> +
>> + /* Limit recursion. */
>> + if (recurse >= 10)
>> + {
>> + retval = false;
>> + BREAK_FROM_IMM_USE_STMT (iter);
>> + }
>
> Put this limit right before the recursion.
>
>> + tree next_name = gimple_get_lhs (use_stmt);
>> + if (!next_name || !is_gimple_reg (next_name))
>> + {
>> + retval = false;
>> + BREAK_FROM_IMM_USE_STMT (iter);
>> + }
>> +
>> + if (uses_consumed_by_stmt (next_name, stmt, recurse + 1))
>> + continue;
>
> So this doesn't change dependent on the result which means you likely meant
>
> if (! uses....)
> {
> retval = false;
> BREAK...
> }
>
> which possibly also invalidates your testing?
Grumble. Can't believe I did that. Yep, will respin.
>
> The whole thing is probably easier to optimize if you merge the ifs
> that break into one.
Will do! Thanks, Richard!
Bill
>
> Richard.
>
>> + }
>> +
>> + return retval;
>> +}
>> +
>> /* Helper routine for find_basis_for_candidate. May be called twice:
>> once for the candidate's base expr, and optionally again either for
>> the candidate's phi definition or for a CAND_REF's alternative base
>> @@ -550,7 +592,8 @@ find_basis_for_candidate (slsr_cand_t c)
>>
>> /* If we found a hidden basis, estimate additional dead-code
>> savings if the phi and its feeding statements can be removed. */
>> - if (basis && has_single_use (gimple_phi_result (phi_cand->cand_stmt)))
>> + tree feeding_var = gimple_phi_result (phi_cand->cand_stmt);
>> + if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt, 0))
>> c->dead_savings += phi_cand->dead_savings;
>> }
>> }
>> @@ -777,7 +820,7 @@ slsr_process_phi (gphi *phi, bool speed)
>>
>> /* Gather potential dead code savings if the phi statement
>> can be removed later on. */
>> - if (has_single_use (arg))
>> + if (uses_consumed_by_stmt (arg, phi, 0))
>> {
>> if (gimple_code (arg_stmt) == GIMPLE_PHI)
>> savings += arg_cand->dead_savings;
>> @@ -2384,7 +2427,9 @@ replace_uncond_cands_and_profitable_phis (slsr_can
>> {
>> if (phi_dependent_cand_p (c))
>> {
>> - if (c->kind == CAND_MULT)
>> + /* A multiply candidate with a stride of 1 is just an artifice
>> + of a copy or cast; there is no value in replacing it. */
>> + if (c->kind == CAND_MULT && wi::to_widest (c->stride) != 1)
>> {
>> /* A candidate dependent upon a phi will replace a multiply by
>> a constant with an add, and will insert at most one add for
>> @@ -2630,8 +2675,9 @@ phi_incr_cost (slsr_cand_t c, const widest_int &in
>> if (gimple_code (arg_def) == GIMPLE_PHI)
>> {
>> int feeding_savings = 0;
>> + tree feeding_var = gimple_phi_result (arg_def);
>> cost += phi_incr_cost (c, incr, arg_def, &feeding_savings);
>> - if (has_single_use (gimple_phi_result (arg_def)))
>> + if (uses_consumed_by_stmt (feeding_var, phi, 0))
>> *savings += feeding_savings;
>> }
>> else
>> @@ -2644,7 +2690,7 @@ phi_incr_cost (slsr_cand_t c, const widest_int &in
>> tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
>> tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
>> cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
>> - if (has_single_use (lhs))
>> + if (uses_consumed_by_stmt (lhs, phi, 0))
>> *savings += stmt_cost (arg_cand->cand_stmt, true);
>> }
>> }
>> @@ -2721,7 +2767,7 @@ lowest_cost_path (int cost_in, int repl_savings, s
>> gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
>> local_cost += phi_incr_cost (c, incr, phi, &savings);
>>
>> - if (has_single_use (gimple_phi_result (phi)))
>> + if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt, 0))
>> local_cost -= savings;
>> }
>>
>> @@ -2765,7 +2811,7 @@ total_savings (int repl_savings, slsr_cand_t c, co
>> gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
>> savings -= phi_incr_cost (c, incr, phi, &phi_savings);
>>
>> - if (has_single_use (gimple_phi_result (phi)))
>> + if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt, 0))
>> savings += phi_savings;
>> }
>>
>> Index: gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c (revision 239241)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/slsr-35.c (working copy)
>> @@ -3,7 +3,7 @@
>> phi has an argument which is a parameter. */
>>
>> /* { dg-do compile } */
>> -/* { dg-options "-O3 -fno-code-hoisting -fdump-tree-optimized" } */
>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>>
>> int
>> f (int c, int i)
>> Index: gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c (revision 239241)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/slsr-36.c (working copy)
>> @@ -3,7 +3,7 @@
>> phi has an argument which is a parameter. */
>>
>> /* { dg-do compile } */
>> -/* { dg-options "-O3 -fno-code-hoisting -fdump-tree-optimized" } */
>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>>
>> int
>> f (int s, int c, int i)
next prev parent reply other threads:[~2017-06-20 14:06 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-06-16 16:10 Bill Schmidt
2017-06-20 11:23 ` Richard Biener
2017-06-20 14:06 ` Bill Schmidt [this message]
2017-06-23 16:06 ` Bill Schmidt
2017-06-26 10:04 ` Richard Biener
2017-06-26 19:22 ` H.J. Lu
2017-06-26 20:59 ` Bill Schmidt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ACF8A9B8-540E-4999-A214-90A2B3D06987@linux.vnet.ibm.com \
--to=wschmidt@linux.vnet.ibm.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).