This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Fix PR71815 (SLSR misses PHI opportunities)


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.

> +{
> +  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?

The whole thing is probably easier to optimize if you merge the ifs
that break into one.

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)
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]