Tiny phiprop compile time optimization

Tiny phiprop compile time optimization

[Jan Hubicka]

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 (&gsi))
-	did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
+	did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
+					     &post_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

Re: Tiny phiprop compile time optimization

[Richard Biener]

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 (&gsi))
> -	did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
> +	did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
> +					     &post_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.

Re: Tiny phiprop compile time optimization

[Andrew Pinski]

On Mon, Jun 19, 2023 at 1:32 AM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> 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 (&gsi))
> > -     did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
> > +     did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
> > +                                          &post_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]

> Am 19.06.2023 um 20:08 schrieb Andrew Pinski via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> On Mon, Jun 19, 2023 at 1:32 AM Richard Biener via Gcc-patches
> <gcc-patches@gcc.gnu.org> 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 (&gsi))
>>> -     did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
>>> +     did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n,
>>> +                                          &post_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

[Jan Hubicka]

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]

> Am 23.06.2023 um 18:10 schrieb Jan Hubicka via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> 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