[PING] Re: [PATCH] tree-optimization/100810 - avoid undefs in IVOPT rewrites

[PING] Re: [PATCH] tree-optimization/100810 - avoid undefs in IVOPT rewrites

[Richard Biener]

On Fri, 1 Apr 2022, Richard Biener wrote:

> The following attempts to avoid IVOPTs rewriting uses using
> IV candidates that involve undefined behavior by using uninitialized
> SSA names.  First we restrict the set of candidates we produce
> for such IVs to the original ones and mark them as not important.
> Second we try to only allow expressing uses with such IV if they
> originally use them.  That is to avoid rewriting all such uses
> in terms of other IVs.  Since cand->iv and use->iv seem to never
> exactly match up we resort to comparing the IV bases.
> 
> The approach ends up similar to the one posted by Roger at
> https://gcc.gnu.org/pipermail/gcc-patches/2021-August/578441.html
> but it marks IV candidates rather than use groups and the cases
> we allow in determine_group_iv_cost_generic are slightly different.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> OK for trunk?

Ping?  Any opinions?

Thanks,
Richard.

> Thanks,
> Richard.
> 
> 2022-01-04  Richard Biener  <rguenther@suse.de>
> 
> 	PR tree-optimization/100810
> 	* tree-ssa-loop-ivopts.cc (struct iv_cand): Add involves_undefs flag.
> 	(find_ssa_undef): New function.
> 	(add_candidate_1): Avoid adding derived candidates with
> 	undefined SSA names and mark the original ones.
> 	(determine_group_iv_cost_generic): Reject rewriting
> 	uses with a different IV when that involves undefined SSA names.
> 
> 	* gcc.dg/torture/pr100810.c: New testcase.
> ---
>  gcc/testsuite/gcc.dg/torture/pr100810.c | 34 +++++++++++++++++++++++++
>  gcc/tree-ssa-loop-ivopts.cc             | 31 ++++++++++++++++++++++
>  2 files changed, 65 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/torture/pr100810.c
> 
> diff --git a/gcc/testsuite/gcc.dg/torture/pr100810.c b/gcc/testsuite/gcc.dg/torture/pr100810.c
> new file mode 100644
> index 00000000000..63566f530f7
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr100810.c
> @@ -0,0 +1,34 @@
> +/* { dg-do run } */
> +
> +int a, b = 1, c = 1, e, f = 1, g, h, j;
> +volatile int d;
> +static void k()
> +{
> +  int i;
> +  h = b;
> +  if (c && a >= 0) {
> +      while (a) {
> +	  i++;
> +	  h--;
> +      }
> +      if (g)
> +	for (h = 0; h < 2; h++)
> +	  ;
> +      if (!b)
> +	i &&d;
> +  }
> +}
> +static void l()
> +{
> +  for (; j < 1; j++)
> +    if (!e && c && f)
> +      k();
> +}
> +int main()
> +{
> +  if (f)
> +    l();
> +  if (h != 1)
> +    __builtin_abort();
> +  return 0;
> +}
> diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
> index 935d2d4d8f3..b0305c494cd 100644
> --- a/gcc/tree-ssa-loop-ivopts.cc
> +++ b/gcc/tree-ssa-loop-ivopts.cc
> @@ -452,6 +452,7 @@ struct iv_cand
>    unsigned id;		/* The number of the candidate.  */
>    bool important;	/* Whether this is an "important" candidate, i.e. such
>  			   that it should be considered by all uses.  */
> +  bool involves_undefs; /* Whether the IV involves undefined values.  */
>    ENUM_BITFIELD(iv_position) pos : 8;	/* Where it is computed.  */
>    gimple *incremented_at;/* For original biv, the statement where it is
>  			   incremented.  */
> @@ -3068,6 +3069,19 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
>    return *slot;
>  }
>  
> +/* Find the first undefined SSA name in *TP.  */
> +
> +static tree
> +find_ssa_undef (tree *tp, int *walk_subtrees, void *)
> +{
> +  if (TREE_CODE (*tp) == SSA_NAME
> +      && ssa_undefined_value_p (*tp, false))
> +    return *tp;
> +  if (!EXPR_P (*tp))
> +    *walk_subtrees = 0;
> +  return NULL;
> +}
> +
>  /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
>     position to POS.  If USE is not NULL, the candidate is set as related to
>     it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
> @@ -3095,6 +3109,17 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
>    if (flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base)))
>      return NULL;
>  
> +  /* If BASE contains undefined SSA names make sure we only record
> +     the original IV.  */
> +  bool involves_undefs = false;
> +  if (walk_tree (&base, find_ssa_undef, NULL, NULL))
> +    {
> +      if (pos != IP_ORIGINAL)
> +	return NULL;
> +      important = false;
> +      involves_undefs = true;
> +    }
> +
>    /* For non-original variables, make sure their values are computed in a type
>       that does not invoke undefined behavior on overflows (since in general,
>       we cannot prove that these induction variables are non-wrapping).  */
> @@ -3143,6 +3168,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
>  	  cand->var_after = cand->var_before;
>  	}
>        cand->important = important;
> +      cand->involves_undefs = involves_undefs;
>        cand->incremented_at = incremented_at;
>        cand->doloop_p = doloop;
>        data->vcands.safe_push (cand);
> @@ -4956,6 +4982,11 @@ determine_group_iv_cost_generic (struct ivopts_data *data,
>       the candidate.  */
>    if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
>      cost = no_cost;
> +  /* If the IV candidate involves undefined SSA values and is not the
> +     same IV as on the USE avoid using that candidate here.  */
> +  else if (cand->involves_undefs
> +	   && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0)))
> +    return false;
>    else
>      cost = get_computation_cost (data, use, cand, false,
>  				 &inv_vars, NULL, &inv_expr);
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)

Re: [PING] Re: [PATCH] tree-optimization/100810 - avoid undefs in IVOPT rewrites

[Richard Biener]

On Tue, Apr 19, 2022 at 1:06 PM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Fri, 1 Apr 2022, Richard Biener wrote:
>
> > The following attempts to avoid IVOPTs rewriting uses using
> > IV candidates that involve undefined behavior by using uninitialized
> > SSA names.  First we restrict the set of candidates we produce
> > for such IVs to the original ones and mark them as not important.
> > Second we try to only allow expressing uses with such IV if they
> > originally use them.  That is to avoid rewriting all such uses
> > in terms of other IVs.  Since cand->iv and use->iv seem to never
> > exactly match up we resort to comparing the IV bases.
> >
> > The approach ends up similar to the one posted by Roger at
> > https://gcc.gnu.org/pipermail/gcc-patches/2021-August/578441.html
> > but it marks IV candidates rather than use groups and the cases
> > we allow in determine_group_iv_cost_generic are slightly different.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >
> > OK for trunk?
>
> Ping?  Any opinions?

I have now pushed the patch.

Richard.

> Thanks,
> Richard.
>
> > Thanks,
> > Richard.
> >
> > 2022-01-04  Richard Biener  <rguenther@suse.de>
> >
> >       PR tree-optimization/100810
> >       * tree-ssa-loop-ivopts.cc (struct iv_cand): Add involves_undefs flag.
> >       (find_ssa_undef): New function.
> >       (add_candidate_1): Avoid adding derived candidates with
> >       undefined SSA names and mark the original ones.
> >       (determine_group_iv_cost_generic): Reject rewriting
> >       uses with a different IV when that involves undefined SSA names.
> >
> >       * gcc.dg/torture/pr100810.c: New testcase.
> > ---
> >  gcc/testsuite/gcc.dg/torture/pr100810.c | 34 +++++++++++++++++++++++++
> >  gcc/tree-ssa-loop-ivopts.cc             | 31 ++++++++++++++++++++++
> >  2 files changed, 65 insertions(+)
> >  create mode 100644 gcc/testsuite/gcc.dg/torture/pr100810.c
> >
> > diff --git a/gcc/testsuite/gcc.dg/torture/pr100810.c b/gcc/testsuite/gcc.dg/torture/pr100810.c
> > new file mode 100644
> > index 00000000000..63566f530f7
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/torture/pr100810.c
> > @@ -0,0 +1,34 @@
> > +/* { dg-do run } */
> > +
> > +int a, b = 1, c = 1, e, f = 1, g, h, j;
> > +volatile int d;
> > +static void k()
> > +{
> > +  int i;
> > +  h = b;
> > +  if (c && a >= 0) {
> > +      while (a) {
> > +       i++;
> > +       h--;
> > +      }
> > +      if (g)
> > +     for (h = 0; h < 2; h++)
> > +       ;
> > +      if (!b)
> > +     i &&d;
> > +  }
> > +}
> > +static void l()
> > +{
> > +  for (; j < 1; j++)
> > +    if (!e && c && f)
> > +      k();
> > +}
> > +int main()
> > +{
> > +  if (f)
> > +    l();
> > +  if (h != 1)
> > +    __builtin_abort();
> > +  return 0;
> > +}
> > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
> > index 935d2d4d8f3..b0305c494cd 100644
> > --- a/gcc/tree-ssa-loop-ivopts.cc
> > +++ b/gcc/tree-ssa-loop-ivopts.cc
> > @@ -452,6 +452,7 @@ struct iv_cand
> >    unsigned id;               /* The number of the candidate.  */
> >    bool important;    /* Whether this is an "important" candidate, i.e. such
> >                          that it should be considered by all uses.  */
> > +  bool involves_undefs; /* Whether the IV involves undefined values.  */
> >    ENUM_BITFIELD(iv_position) pos : 8;        /* Where it is computed.  */
> >    gimple *incremented_at;/* For original biv, the statement where it is
> >                          incremented.  */
> > @@ -3068,6 +3069,19 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
> >    return *slot;
> >  }
> >
> > +/* Find the first undefined SSA name in *TP.  */
> > +
> > +static tree
> > +find_ssa_undef (tree *tp, int *walk_subtrees, void *)
> > +{
> > +  if (TREE_CODE (*tp) == SSA_NAME
> > +      && ssa_undefined_value_p (*tp, false))
> > +    return *tp;
> > +  if (!EXPR_P (*tp))
> > +    *walk_subtrees = 0;
> > +  return NULL;
> > +}
> > +
> >  /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
> >     position to POS.  If USE is not NULL, the candidate is set as related to
> >     it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
> > @@ -3095,6 +3109,17 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
> >    if (flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base)))
> >      return NULL;
> >
> > +  /* If BASE contains undefined SSA names make sure we only record
> > +     the original IV.  */
> > +  bool involves_undefs = false;
> > +  if (walk_tree (&base, find_ssa_undef, NULL, NULL))
> > +    {
> > +      if (pos != IP_ORIGINAL)
> > +     return NULL;
> > +      important = false;
> > +      involves_undefs = true;
> > +    }
> > +
> >    /* For non-original variables, make sure their values are computed in a type
> >       that does not invoke undefined behavior on overflows (since in general,
> >       we cannot prove that these induction variables are non-wrapping).  */
> > @@ -3143,6 +3168,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
> >         cand->var_after = cand->var_before;
> >       }
> >        cand->important = important;
> > +      cand->involves_undefs = involves_undefs;
> >        cand->incremented_at = incremented_at;
> >        cand->doloop_p = doloop;
> >        data->vcands.safe_push (cand);
> > @@ -4956,6 +4982,11 @@ determine_group_iv_cost_generic (struct ivopts_data *data,
> >       the candidate.  */
> >    if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
> >      cost = no_cost;
> > +  /* If the IV candidate involves undefined SSA values and is not the
> > +     same IV as on the USE avoid using that candidate here.  */
> > +  else if (cand->involves_undefs
> > +        && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0)))
> > +    return false;
> >    else
> >      cost = get_computation_cost (data, use, cand, false,
> >                                &inv_vars, NULL, &inv_expr);
> >
>
> --
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
> Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)