Re: [PATCH V2] Clean up loop-closed PHIs after loop finalize

[Jiufu Guo <guojiufu@linux.ibm.com>]

On 2020-11-16 17:35, Richard Biener wrote:
> On Mon, Nov 16, 2020 at 10:26 AM Jiufu Guo <guojiufu@linux.ibm.com> 
> wrote:
>> 
>> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>> 
>> > Richard Biener <rguenther@suse.de> writes:
>> >
>> >> On Wed, 11 Nov 2020, Jiufu Guo wrote:
>> >>
>> >>>
>> >>> Thanks a lot for the suggestion from previous mails.
>> >>> The patch was updated accordingly.
>> >>>
>> >>> This updated patch propagates loop-closed PHIs them out after
>> >>> loop_optimizer_finalize under a new introduced flag.  At some cases,
>> >>> to clean up loop-closed PHIs would save efforts of optimization passes
>> >>> after loopdone.
>> >>>
>> >>> This patch passes bootstrap and regtest on ppc64le.  Is this ok for trunk?
>> >>
>> >> Comments below
>> >>
>> >>>    free_numbers_of_iterations_estimates (fn);
>> >>>
>> >>> +  if (flag_clean_up_loop_closed_phi
>> >>
>> >> Sorry if there was miscommunication but I've not meant to add a
>> >> new user-visible flag but instead a flag argument to loop_optimizer_finalize
>> >> (as said, you can default it to false to only need to change the
>> >> one in fini_loops)
>> > Sorry for misunderstand.
>> > Updated the patch.
>> 
>> Thanks for the comments!  The patch was updated accordingly.
>> 
>> This updated patch clean up loop closed PHIs in 
>> loop_optimizer_finalize,
>> which is called when some loop optimizations are done. For some cases,
>> this would save efforts of optimization passes after loopdone.
>> 
>> gcc/ChangeLog:
>> 2020-10-16  Jiufu Guo   <guojiufu@linux.ibm.com>
>> 
>>         * cfgloop.h (loop_optimizer_finalize): Add flag argument.
>>         * loop-init.c (loop_optimizer_finalize): Call 
>> clean_up_loop_closed_phi.
>>         * tree-cfgcleanup.h (clean_up_loop_closed_phi): New declare.
>>         * tree-ssa-loop.c (tree_ssa_loop_done): Call 
>> loop_optimizer_finalize
>>         with flag argument.
>>         * tree-ssa-propagate.c (clean_up_loop_closed_phi): New 
>> function.
>> 
>> gcc/testsuite/ChangeLog:
>> 2020-10-16  Jiufu Guo   <guojiufu@linux.ibm.com>
>> 
>>         * gcc.dg/tree-ssa/loopclosedphi.c: New test.
>> 
>> ---
>>  gcc/cfgloop.h                                 |  2 +-
>>  gcc/loop-init.c                               |  9 ++-
>>  gcc/testsuite/gcc.dg/tree-ssa/loopclosedphi.c | 21 +++++++
>>  gcc/tree-cfgcleanup.h                         |  1 +
>>  gcc/tree-ssa-loop.c                           |  2 +-
>>  gcc/tree-ssa-propagate.c                      | 63 
>> +++++++++++++++++++
>>  6 files changed, 95 insertions(+), 3 deletions(-)
>>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loopclosedphi.c
>> 
>> diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
>> index d14689dc31f..438b1f779bb 100644
>> --- a/gcc/cfgloop.h
>> +++ b/gcc/cfgloop.h
>> @@ -824,7 +824,7 @@ extern void init_set_costs (void);
>> 
>>  /* Loop optimizer initialization.  */
>>  extern void loop_optimizer_init (unsigned);
>> -extern void loop_optimizer_finalize (function *);
>> +extern void loop_optimizer_finalize (function *, bool = false);
>>  inline void
>>  loop_optimizer_finalize ()
>>  {
>> diff --git a/gcc/loop-init.c b/gcc/loop-init.c
>> index 401e5282907..0cb6f509b89 100644
>> --- a/gcc/loop-init.c
>> +++ b/gcc/loop-init.c
>> @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
>>  #include "tree-ssa-loop-niter.h"
>>  #include "loop-unroll.h"
>>  #include "tree-scalar-evolution.h"
>> +#include "tree-cfgcleanup.h"
>> 
>> 
>>  /* Apply FLAGS to the loop state.  */
>> @@ -133,7 +134,7 @@ loop_optimizer_init (unsigned flags)
>>  /* Finalize loop structures.  */
>> 
>>  void
>> -loop_optimizer_finalize (struct function *fn)
>> +loop_optimizer_finalize (struct function *fn, bool 
>> clean_loop_closed_phi)
>>  {
>>    class loop *loop;
>>    basic_block bb;
>> @@ -145,6 +146,12 @@ loop_optimizer_finalize (struct function *fn)
>> 
>>    free_numbers_of_iterations_estimates (fn);
>> 
>> +  if (clean_loop_closed_phi && loops_state_satisfies_p (fn, 
>> LOOP_CLOSED_SSA))
>> +    {
>> +      clean_up_loop_closed_phi (fn);
>> +      loops_state_clear (fn, LOOP_CLOSED_SSA);
>> +    }
>> +
>>    /* If we should preserve loop structure, do not free it but clear
>>       flags that advanced properties are there as we are not 
>> preserving
>>       that in full.  */
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loopclosedphi.c 
>> b/gcc/testsuite/gcc.dg/tree-ssa/loopclosedphi.c
>> new file mode 100644
>> index 00000000000..d71b757fbca
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/loopclosedphi.c
>> @@ -0,0 +1,21 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O3 -fno-tree-ch -w -fdump-tree-loopdone-details" } 
>> */
>> +
>> +void
>> +t6 (int qz, int wh)
>> +{
>> +  int jl = wh;
>> +
>> +  while (1.0 * qz / wh < 1)
>> +    {
>> +      qz = wh * (wh + 2);
>> +
>> +      while (wh < 1)
>> +        jl = 0;
>> +    }
>> +
>> +  while (qz < 1)
>> +    qz = jl * wh;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "Replacing" 2 "loopdone"} } */
>> diff --git a/gcc/tree-cfgcleanup.h b/gcc/tree-cfgcleanup.h
>> index 6ff6726bfe4..9e368d63709 100644
>> --- a/gcc/tree-cfgcleanup.h
>> +++ b/gcc/tree-cfgcleanup.h
>> @@ -26,5 +26,6 @@ extern bool cleanup_tree_cfg (unsigned = 0);
>>  extern bool fixup_noreturn_call (gimple *stmt);
>>  extern bool delete_unreachable_blocks_update_callgraph (cgraph_node 
>> *dst_node,
>>                                                         bool 
>> update_clones);
>> +extern unsigned clean_up_loop_closed_phi (function *);
>> 
>>  #endif /* GCC_TREE_CFGCLEANUP_H */
>> diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c
>> index 5e8365d4e83..339a0c50bc8 100644
>> --- a/gcc/tree-ssa-loop.c
>> +++ b/gcc/tree-ssa-loop.c
>> @@ -529,7 +529,7 @@ tree_ssa_loop_done (void)
>>  {
>>    free_numbers_of_iterations_estimates (cfun);
>>    scev_finalize ();
>> -  loop_optimizer_finalize ();
>> +  loop_optimizer_finalize (cfun, true);
>>    return 0;
>>  }
>> 
>> diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
>> index 87dbf55fab9..daa1db82afc 100644
>> --- a/gcc/tree-ssa-propagate.c
>> +++ b/gcc/tree-ssa-propagate.c
>> @@ -1549,3 +1549,66 @@ propagate_tree_value_into_stmt 
>> (gimple_stmt_iterator *gsi, tree val)
>>    else
>>      gcc_unreachable ();
>>  }
>> +
>> +/* Check exits of each loop in FUN, walk over loop closed PHIs in
>> +   each exit basic block and propagate degenerate PHIs.  */
>> +
>> +unsigned
>> +clean_up_loop_closed_phi (function *fun)
>> +{
>> +  unsigned i;
>> +  edge e;
>> +  gphi *phi;
>> +  tree rhs;
>> +  tree lhs;
>> +  gphi_iterator gsi;
>> +  struct loop *loop;
>> +
>> +  /* Check dominator info before get loop-close PHIs from loop exits. 
>>  */
>> +  if (dom_info_state (CDI_DOMINATORS) != DOM_OK)
> 
> Please change this to
> 
>        /* Avoid possibly quadratic work when scanning for loop exits 
> across
>           all loops of a nest.  */
>        if (!loop_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
>          return 0;
> 

Great suggestion, thanks!

And, the patch for loop-init.c, is also updated a little as below: call
clean_up_loop_closed_phi before release_recorded_exits, to avoid flag
LOOPS_HAVE_RECORDED_EXITS is cleared before checked.

-----------------
diff --git a/gcc/loop-init.c b/gcc/loop-init.c
index 401e5282907..ac87dafef6e 100644
--- a/gcc/loop-init.c
+++ b/gcc/loop-init.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
  #include "tree-ssa-loop-niter.h"
  #include "loop-unroll.h"
  #include "tree-scalar-evolution.h"
+#include "tree-cfgcleanup.h"

  ^L
  /* Apply FLAGS to the loop state.  */
@@ -133,13 +134,19 @@ loop_optimizer_init (unsigned flags)
  /* Finalize loop structures.  */

  void
-loop_optimizer_finalize (struct function *fn)
+loop_optimizer_finalize (struct function *fn, bool 
clean_loop_closed_phi)
  {
    class loop *loop;
    basic_block bb;

    timevar_push (TV_LOOP_FINI);

+  if (clean_loop_closed_phi && loops_state_satisfies_p (fn, 
LOOP_CLOSED_SSA))
+    {
+      clean_up_loop_closed_phi (fn);
+      loops_state_clear (fn, LOOP_CLOSED_SSA);
+    }
+
    if (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS))
      release_recorded_exits (fn);
----------------
>> +    return 0;
>> +
>> +  /* Walk over loop in function.  */
>> +  FOR_EACH_LOOP_FN (fun, loop, 0)
>> +    {
>> +      /* Check each exit edege of loop.  */
>> +      auto_vec<edge> exits = get_loop_exit_edges (loop);
>> +      FOR_EACH_VEC_ELT (exits, i, e)
>> +       if (single_pred_p (e->dest))
>> +         /* Walk over loop-closed PHIs.  */
>> +         for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);)
>> +           {
>> +             phi = gsi.phi ();
>> +             rhs = degenerate_phi_result (phi);
> 
>   rhs = gimple_phi_arg_def (phi, 0);
Thanks, sorry for missing this, you mentioned in previous mail.

I will commit the updated patch.

Thanks!
Jiufu Guo.


> 
> OK with that changes.
> 
> Thanks,
> Richard.
> 
>> +             lhs = gimple_phi_result (phi);
>> +
>> +             if (rhs && may_propagate_copy (lhs, rhs))
>> +               {
>> +                 /* Dump details.  */
>> +                 if (dump_file && (dump_flags & TDF_DETAILS))
>> +                   {
>> +                     fprintf (dump_file, "  Replacing '");
>> +                     print_generic_expr (dump_file, lhs, dump_flags);
>> +                     fprintf (dump_file, "' with '");
>> +                     print_generic_expr (dump_file, rhs, dump_flags);
>> +                     fprintf (dump_file, "'\n");
>> +                   }
>> +
>> +                 use_operand_p use_p;
>> +                 imm_use_iterator iter;
>> +                 gimple *use_stmt;
>> +                 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
>> +                   {
>> +                     FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
>> +                       replace_exp (use_p, rhs);
>> +                     update_stmt (use_stmt);
>> +                   }
>> +                 remove_phi_node (&gsi, true);
>> +               }
>> +             else
>> +               gsi_next (&gsi);
>> +           }
>> +    }
>> +
>> +  return 0;
>> +}
>> --
>> 2.25.1
>> 
>> 
>> 
>> 
>> >>
>> >>> +      && loops_state_satisfies_p (fn, LOOP_CLOSED_SSA))
>> >>> +    {
>> >>> +      clean_up_loop_closed_phi (fn);
>> >>> +      loops_state_clear (fn, LOOP_CLOSED_SSA);
>> >>> +    }
>> >>> +
>> > ......
>> >>> +  gphi *phi;
>> >>> +  tree rhs;
>> >>> +  tree lhs;
>> >>> +  gphi_iterator gsi;
>> >>> +  struct loop *loop;
>> >>> +  bool cfg_altered = false;
>> >>> +
>> >>> +  /* Check dominator info before get loop-close PHIs from loop exits.  */
>> >>> +  if (dom_info_state (CDI_DOMINATORS) != DOM_OK)
>> >>
>> >> Why?
>> >>
>> > As you said, loop_optimizer_finalize is also called from where dominator
>> > info is not ready, e.g. called from: vrp(execute_vrp).
>> > At there, loop exits info is not ready, and then
>> > get_loop_exit_edges/get_loop_body_with_size function does not work.
>> >
>> >>> +  /* Walk over loop in function.  */
>> >>> +  FOR_EACH_LOOP_FN (fun, loop, 0)
>> >>> +    {
>> >>> +      /* Check each exit edege of loop.  */
>> >>> +      auto_vec<edge> exits = get_loop_exit_edges (loop);
>> >>> +      FOR_EACH_VEC_ELT (exits, i, e)
>> >>> +   if (single_pred_p (e->dest))
>> >>> +     /* Walk over loop-closed PHIs.  */
>> >>> +     for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);)
>> >>> +       {
>> >>> +         phi = gsi.phi ();
>> >>> +         rhs = degenerate_phi_result (phi);
>> >>
>> >> You have a single predecessor, thus the result is always degenerate.
>> >>
>> >>> +         lhs = gimple_phi_result (phi);
>> >>> +
>> >>> +         if (rhs && may_propagate_copy (lhs, rhs))
>> >>> +           {
>> >>> +             gimple_stmt_iterator psi = gsi;
>> >>> +             /* Advance the iterator before stmt is removed.  */
>> >>> +             gsi_next (&gsi);
>> >>
>> >> remove_phi_node should take care of this, you shouldn't need this
>> >> (just do not advance the iterator when you remove the PHI node).
>> >>
>> > Yeap, get it! Thanks, will update the patch accordingly.
>> >>> +
>> > ......
>> >>> +
>> >>> +             replace_uses_by (lhs, rhs);
>> >>> +             remove_phi_node (&psi, true);
>> >>> +             cfg_altered = true;
>> >>
>> >> in the end the return value is unused but I think we should avoid
>> >> altering the CFG since doing so requires it to be cleaned up for
>> >> unreachable blocks.  That means to open-code replace_uses_by as
>> >>
>> >>   imm_use_iterator imm_iter;
>> >>   use_operand_p use;
>> >>   gimple *stmt;
>> >>   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
>> >>     {
>> >>       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
>> >>         replace_exp (use, val);
>> >>       update_stmt (stmt);
>> >>     }
>> >
>> > Thansk! This could also save some code in replace_uses_by.
>> >
>> > BR.
>> > Jiufu Guo
>> >>
>> >> Thanks,
>> >> Richard.
>> >>
>> >>> +           }
>> >>> +         else
>> >>> +           gsi_next (&gsi);
>> >>> +       }
>> >>> +    }
>> >>> +
>> >>> +  return cfg_altered;
>> >>> +}
>> >>>