Re: Tiny phiprop compile time optimization

[Richard Biener via Gcc-patches]

> Am 23.06.2023 um 18:10 schrieb Jan Hubicka via Gcc-patches 
> :
> 
> Hi,
> here is updated version with TODO_update_ssa_only_virtuals.
> bootstrapped/regtested x86_64-linux. OK?

Ok

Richard 

> gcc/ChangeLog:
> 
>* tree-ssa-phiprop.cc (propagate_with_phi): Compute post dominators on
>demand.
>(pass_phiprop::execute): Do not compute it here; return
>update_ssa_only_virtuals if something changed.
>(pass_data_phiprop): Remove TODO_update_ssa from todos.
>
> 
> diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
> index 8c9ce903472..b01ef4495c2 100644
> --- a/gcc/tree-ssa-phiprop.cc
> +++ b/gcc/tree-ssa-phiprop.cc
> @@ -340,6 +340,9 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
> phiprop_d *phivn,
>   gimple *def_stmt;
>   tree vuse;
> 
> +  if (!dom_info_available_p (cfun, CDI_POST_DOMINATORS))
> +calculate_dominance_info (CDI_POST_DOMINATORS);
> +
>   /* Only replace loads in blocks that post-dominate the PHI node.  That
>  makes sure we don't end up speculating loads.  */
>   if (!dominated_by_p (CDI_POST_DOMINATORS,
> @@ -485,7 +488,7 @@ const pass_data pass_data_phiprop =
>   0, /* properties_provided */
>   0, /* properties_destroyed */
>   0, /* todo_flags_start */
> -  TODO_update_ssa, /* todo_flags_finish */
> +  0, /* todo_flags_finish */
> };
> 
> class pass_phiprop : public gimple_opt_pass
> @@ -513,7 +516,6 @@ pass_phiprop::execute (function *fun)
>   size_t n;
> 
>   calculate_dominance_info (CDI_DOMINATORS);
> -  calculate_dominance_info (CDI_POST_DOMINATORS);
> 
>   n = num_ssa_names;
>   phivn = XCNEWVEC (struct phiprop_d, n);
> @@ -539,7 +541,7 @@ pass_phiprop::execute (function *fun)
> 
>   free_dominance_info (CDI_POST_DOMINATORS);
> 
> -  return 0;
> +  return did_something ? TODO_update_ssa_only_virtuals : 0;
> }
> 
> } // anon namespace

Re: Tiny phiprop compile time optimization

[Jan Hubicka via Gcc-patches]

Hi,
here is updated version with TODO_update_ssa_only_virtuals.
bootstrapped/regtested x86_64-linux. OK?

gcc/ChangeLog:

* tree-ssa-phiprop.cc (propagate_with_phi): Compute post dominators on
demand.
(pass_phiprop::execute): Do not compute it here; return
update_ssa_only_virtuals if something changed.
(pass_data_phiprop): Remove TODO_update_ssa from todos.


diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
index 8c9ce903472..b01ef4495c2 100644
--- a/gcc/tree-ssa-phiprop.cc
+++ b/gcc/tree-ssa-phiprop.cc
@@ -340,6 +340,9 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
phiprop_d *phivn,
   gimple *def_stmt;
   tree vuse;
 
+  if (!dom_info_available_p (cfun, CDI_POST_DOMINATORS))
+   calculate_dominance_info (CDI_POST_DOMINATORS);
+
   /* Only replace loads in blocks that post-dominate the PHI node.  That
  makes sure we don't end up speculating loads.  */
   if (!dominated_by_p (CDI_POST_DOMINATORS,
@@ -485,7 +488,7 @@ const pass_data pass_data_phiprop =
   0, /* properties_provided */
   0, /* properties_destroyed */
   0, /* todo_flags_start */
-  TODO_update_ssa, /* todo_flags_finish */
+  0, /* todo_flags_finish */
 };
 
 class pass_phiprop : public gimple_opt_pass
@@ -513,7 +516,6 @@ pass_phiprop::execute (function *fun)
   size_t n;
 
   calculate_dominance_info (CDI_DOMINATORS);
-  calculate_dominance_info (CDI_POST_DOMINATORS);
 
   n = num_ssa_names;
   phivn = XCNEWVEC (struct phiprop_d, n);
@@ -539,7 +541,7 @@ pass_phiprop::execute (function *fun)
 
   free_dominance_info (CDI_POST_DOMINATORS);
 
-  return 0;
+  return did_something ? TODO_update_ssa_only_virtuals : 0;
 }
 
 } // anon namespace

Re: Tiny phiprop compile time optimization

[Richard Biener via Gcc-patches]

> Am 19.06.2023 um 20:08 schrieb Andrew Pinski via Gcc-patches 
> :
> 
> On Mon, Jun 19, 2023 at 1:32 AM Richard Biener via Gcc-patches
>  wrote:
>> 
>>> On Mon, 19 Jun 2023, Jan Hubicka wrote:
>>> 
>>> Hi,
>>> this patch avoids unnecessary post dominator and update_ssa in phiprop.
>>> 
>>> Bootstrapped/regtested x86_64-linux, OK?
>>> 
>>> gcc/ChangeLog:
>>> 
>>>  * tree-ssa-phiprop.cc (propagate_with_phi): Add 
>>> post_dominators_computed;
>>>  compute post dominators lazilly.
>>>  (const pass_data pass_data_phiprop): Remove TODO_update_ssa.
>>>  (pass_phiprop::execute): Update; return TODO_update_ssa if something
>>>  changed.
>>> 
>>> diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
>>> index 3cb4900b6be..87e3a2ccf3a 100644
>>> --- a/gcc/tree-ssa-phiprop.cc
>>> +++ b/gcc/tree-ssa-phiprop.cc
>>> @@ -260,7 +260,7 @@ chk_uses (tree, tree *idx, void *data)
>>> 
>>> static bool
>>> propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
>>> - size_t n)
>>> + size_t n, bool *post_dominators_computed)
>>> {
>>>   tree ptr = PHI_RESULT (phi);
>>>   gimple *use_stmt;
>>> @@ -324,6 +324,12 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
>>> phiprop_d *phivn,
>>>   gimple *def_stmt;
>>>   tree vuse;
>>> 
>>> +  if (!*post_dominators_computed)
>>> +{
>>> +   calculate_dominance_info (CDI_POST_DOMINATORS);
>>> +   *post_dominators_computed = true;
>> 
>> I think you can save the parameter by using dom_info_available_p () here
>> and ...
>> 
>>> + }
>>> +
>>>   /* Only replace loads in blocks that post-dominate the PHI node.  That
>>>  makes sure we don't end up speculating loads.  */
>>>   if (!dominated_by_p (CDI_POST_DOMINATORS,
>>> @@ -465,7 +471,7 @@ const pass_data pass_data_phiprop =
>>>   0, /* properties_provided */
>>>   0, /* properties_destroyed */
>>>   0, /* todo_flags_start */
>>> -  TODO_update_ssa, /* todo_flags_finish */
>>> +  0, /* todo_flags_finish */
>>> };
>>> 
>>> class pass_phiprop : public gimple_opt_pass
>>> @@ -490,9 +497,9 @@ pass_phiprop::execute (function *fun)
>>>   gphi_iterator gsi;
>>>   unsigned i;
>>>   size_t n;
>>> +  bool post_dominators_computed = false;
>>> 
>>>   calculate_dominance_info (CDI_DOMINATORS);
>>> -  calculate_dominance_info (CDI_POST_DOMINATORS);
>>> 
>>>   n = num_ssa_names;
>>>   phivn = XCNEWVEC (struct phiprop_d, n);
>>> @@ -508,7 +515,8 @@ pass_phiprop::execute (function *fun)
>>>   if (bb_has_abnormal_pred (bb))
>>>  continue;
>>>   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next ())
>>> - did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
>>> + did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
>>> +  _dominators_computed);
>>> }
>>> 
>>>   if (did_something)
>>> @@ -516,9 +524,10 @@ pass_phiprop::execute (function *fun)
>>> 
>>>   free (phivn);
>>> 
>>> -  free_dominance_info (CDI_POST_DOMINATORS);
>>> +  if (post_dominators_computed)
>>> +free_dominance_info (CDI_POST_DOMINATORS);
>> 
>> unconditionally free_dominance_info here.
>> 
>>> -  return 0;
>>> +  return did_something ? TODO_update_ssa : 0;
>> 
>> I guess that change is following general practice and good to catch
>> undesired changes (update_ssa will exit early when there's nothing
>> to do anyway).
> 
> I wonder if TODO_update_ssa_only_virtuals should be used here rather
> than TODO_update_ssa as the code produces ssa names already and just
> adds memory loads/stores. But I could be wrong.

I guess it should be able to update virtual SSA form itself.  But it’s been 
some time since I wrote the pass …

> 
> Thanks,
> Andrew Pinski
> 
> 
>> 
>> OK with those changes.

Re: Tiny phiprop compile time optimization

[Andrew Pinski via Gcc-patches]

On Mon, Jun 19, 2023 at 1:32 AM Richard Biener via Gcc-patches
 wrote:
>
> On Mon, 19 Jun 2023, Jan Hubicka wrote:
>
> > Hi,
> > this patch avoids unnecessary post dominator and update_ssa in phiprop.
> >
> > Bootstrapped/regtested x86_64-linux, OK?
> >
> > gcc/ChangeLog:
> >
> >   * tree-ssa-phiprop.cc (propagate_with_phi): Add 
> > post_dominators_computed;
> >   compute post dominators lazilly.
> >   (const pass_data pass_data_phiprop): Remove TODO_update_ssa.
> >   (pass_phiprop::execute): Update; return TODO_update_ssa if something
> >   changed.
> >
> > diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
> > index 3cb4900b6be..87e3a2ccf3a 100644
> > --- a/gcc/tree-ssa-phiprop.cc
> > +++ b/gcc/tree-ssa-phiprop.cc
> > @@ -260,7 +260,7 @@ chk_uses (tree, tree *idx, void *data)
> >
> >  static bool
> >  propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
> > - size_t n)
> > + size_t n, bool *post_dominators_computed)
> >  {
> >tree ptr = PHI_RESULT (phi);
> >gimple *use_stmt;
> > @@ -324,6 +324,12 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
> > phiprop_d *phivn,
> >gimple *def_stmt;
> >tree vuse;
> >
> > +  if (!*post_dominators_computed)
> > +{
> > +   calculate_dominance_info (CDI_POST_DOMINATORS);
> > +   *post_dominators_computed = true;
>
> I think you can save the parameter by using dom_info_available_p () here
> and ...
>
> > + }
> > +
> >/* Only replace loads in blocks that post-dominate the PHI node.  
> > That
> >   makes sure we don't end up speculating loads.  */
> >if (!dominated_by_p (CDI_POST_DOMINATORS,
> > @@ -465,7 +471,7 @@ const pass_data pass_data_phiprop =
> >0, /* properties_provided */
> >0, /* properties_destroyed */
> >0, /* todo_flags_start */
> > -  TODO_update_ssa, /* todo_flags_finish */
> > +  0, /* todo_flags_finish */
> >  };
> >
> >  class pass_phiprop : public gimple_opt_pass
> > @@ -490,9 +497,9 @@ pass_phiprop::execute (function *fun)
> >gphi_iterator gsi;
> >unsigned i;
> >size_t n;
> > +  bool post_dominators_computed = false;
> >
> >calculate_dominance_info (CDI_DOMINATORS);
> > -  calculate_dominance_info (CDI_POST_DOMINATORS);
> >
> >n = num_ssa_names;
> >phivn = XCNEWVEC (struct phiprop_d, n);
> > @@ -508,7 +515,8 @@ pass_phiprop::execute (function *fun)
> >if (bb_has_abnormal_pred (bb))
> >   continue;
> >for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next ())
> > - did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
> > + did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
> > +  _dominators_computed);
> >  }
> >
> >if (did_something)
> > @@ -516,9 +524,10 @@ pass_phiprop::execute (function *fun)
> >
> >free (phivn);
> >
> > -  free_dominance_info (CDI_POST_DOMINATORS);
> > +  if (post_dominators_computed)
> > +free_dominance_info (CDI_POST_DOMINATORS);
>
> unconditionally free_dominance_info here.
>
> > -  return 0;
> > +  return did_something ? TODO_update_ssa : 0;
>
> I guess that change is following general practice and good to catch
> undesired changes (update_ssa will exit early when there's nothing
> to do anyway).

I wonder if TODO_update_ssa_only_virtuals should be used here rather
than TODO_update_ssa as the code produces ssa names already and just
adds memory loads/stores. But I could be wrong.

Thanks,
Andrew Pinski


>
> OK with those changes.

Re: Tiny phiprop compile time optimization

[Richard Biener via Gcc-patches]

On Mon, 19 Jun 2023, Jan Hubicka wrote:

> Hi,
> this patch avoids unnecessary post dominator and update_ssa in phiprop.
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> gcc/ChangeLog:
> 
>   * tree-ssa-phiprop.cc (propagate_with_phi): Add 
> post_dominators_computed;
>   compute post dominators lazilly.
>   (const pass_data pass_data_phiprop): Remove TODO_update_ssa.
>   (pass_phiprop::execute): Update; return TODO_update_ssa if something
>   changed.
> 
> diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
> index 3cb4900b6be..87e3a2ccf3a 100644
> --- a/gcc/tree-ssa-phiprop.cc
> +++ b/gcc/tree-ssa-phiprop.cc
> @@ -260,7 +260,7 @@ chk_uses (tree, tree *idx, void *data)
>  
>  static bool
>  propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
> - size_t n)
> + size_t n, bool *post_dominators_computed)
>  {
>tree ptr = PHI_RESULT (phi);
>gimple *use_stmt;
> @@ -324,6 +324,12 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
> phiprop_d *phivn,
>gimple *def_stmt;
>tree vuse;
>  
> +  if (!*post_dominators_computed)
> +{
> +   calculate_dominance_info (CDI_POST_DOMINATORS);
> +   *post_dominators_computed = true;

I think you can save the parameter by using dom_info_available_p () here
and ...

> + }
> +
>/* Only replace loads in blocks that post-dominate the PHI node.  That
>   makes sure we don't end up speculating loads.  */
>if (!dominated_by_p (CDI_POST_DOMINATORS,
> @@ -465,7 +471,7 @@ const pass_data pass_data_phiprop =
>0, /* properties_provided */
>0, /* properties_destroyed */
>0, /* todo_flags_start */
> -  TODO_update_ssa, /* todo_flags_finish */
> +  0, /* todo_flags_finish */
>  };
>  
>  class pass_phiprop : public gimple_opt_pass
> @@ -490,9 +497,9 @@ pass_phiprop::execute (function *fun)
>gphi_iterator gsi;
>unsigned i;
>size_t n;
> +  bool post_dominators_computed = false;
>  
>calculate_dominance_info (CDI_DOMINATORS);
> -  calculate_dominance_info (CDI_POST_DOMINATORS);
>  
>n = num_ssa_names;
>phivn = XCNEWVEC (struct phiprop_d, n);
> @@ -508,7 +515,8 @@ pass_phiprop::execute (function *fun)
>if (bb_has_abnormal_pred (bb))
>   continue;
>for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next ())
> - did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
> + did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
> +  _dominators_computed);
>  }
>  
>if (did_something)
> @@ -516,9 +524,10 @@ pass_phiprop::execute (function *fun)
>  
>free (phivn);
>  
> -  free_dominance_info (CDI_POST_DOMINATORS);
> +  if (post_dominators_computed)
> +free_dominance_info (CDI_POST_DOMINATORS);

unconditionally free_dominance_info here.

> -  return 0;
> +  return did_something ? TODO_update_ssa : 0;

I guess that change is following general practice and good to catch
undesired changes (update_ssa will exit early when there's nothing
to do anyway).

OK with those changes.

Tiny phiprop compile time optimization

[Jan Hubicka via Gcc-patches]

Hi,
this patch avoids unnecessary post dominator and update_ssa in phiprop.

Bootstrapped/regtested x86_64-linux, OK?

gcc/ChangeLog:

* tree-ssa-phiprop.cc (propagate_with_phi): Add 
post_dominators_computed;
compute post dominators lazilly.
(const pass_data pass_data_phiprop): Remove TODO_update_ssa.
(pass_phiprop::execute): Update; return TODO_update_ssa if something
changed.

diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
index 3cb4900b6be..87e3a2ccf3a 100644
--- a/gcc/tree-ssa-phiprop.cc
+++ b/gcc/tree-ssa-phiprop.cc
@@ -260,7 +260,7 @@ chk_uses (tree, tree *idx, void *data)
 
 static bool
 propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
-   size_t n)
+   size_t n, bool *post_dominators_computed)
 {
   tree ptr = PHI_RESULT (phi);
   gimple *use_stmt;
@@ -324,6 +324,12 @@ propagate_with_phi (basic_block bb, gphi *phi, struct 
phiprop_d *phivn,
   gimple *def_stmt;
   tree vuse;
 
+  if (!*post_dominators_computed)
+{
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+ *post_dominators_computed = true;
+   }
+
   /* Only replace loads in blocks that post-dominate the PHI node.  That
  makes sure we don't end up speculating loads.  */
   if (!dominated_by_p (CDI_POST_DOMINATORS,
@@ -465,7 +471,7 @@ const pass_data pass_data_phiprop =
   0, /* properties_provided */
   0, /* properties_destroyed */
   0, /* todo_flags_start */
-  TODO_update_ssa, /* todo_flags_finish */
+  0, /* todo_flags_finish */
 };
 
 class pass_phiprop : public gimple_opt_pass
@@ -490,9 +497,9 @@ pass_phiprop::execute (function *fun)
   gphi_iterator gsi;
   unsigned i;
   size_t n;
+  bool post_dominators_computed = false;
 
   calculate_dominance_info (CDI_DOMINATORS);
-  calculate_dominance_info (CDI_POST_DOMINATORS);
 
   n = num_ssa_names;
   phivn = XCNEWVEC (struct phiprop_d, n);
@@ -508,7 +515,8 @@ pass_phiprop::execute (function *fun)
   if (bb_has_abnormal_pred (bb))
continue;
   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next ())
-   did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
+   did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
+_dominators_computed);
 }
 
   if (did_something)
@@ -516,9 +524,10 @@ pass_phiprop::execute (function *fun)
 
   free (phivn);
 
-  free_dominance_info (CDI_POST_DOMINATORS);
+  if (post_dominators_computed)
+free_dominance_info (CDI_POST_DOMINATORS);
 
-  return 0;
+  return did_something ? TODO_update_ssa : 0;
 }
 
 } // anon namespace