Re: [PATCH] [PR105665] ivopts: check defs of names in base for undefs

[Richard Biener <richard.guenther@gmail.com>]

On Sat, May 28, 2022 at 7:52 AM Alexandre Oliva via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
> The patch for PR 100810 tested for undefined SSA_NAMEs appearing
> directly in the base expression of the potential IV candidate, but
> that's not enough.  The testcase for PR105665 shows an undefined
> SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
> in the referenced SSA_NAME.  The variant of that test shows it can be
> further removed from the referenced SSA_NAME.
>
> To avoid deep recursion, precompute SSA_NAMEs deemed unsuitable
> candidates, so that we can skip them with a flag test.
>
> Regstrapped on x86_64-linux-gnu.  Ok to install?

I don't think you can rely on TREE_VISITED not set at the start of the
pass (and you don't clear it either).  So it's probably better to use a
sbitmap.

I also wonder how you decide that tracking PHIs with (one) uninit arg
is "enough"?  The previous patch indeed is also only somewhat a
hack because the GIMPLE IL doesn't stabilize the "value" of an
SSA default def.  Is it important which edge of the PHI the undef
appears in?  I presume the testcase might have it on the
loop entry edge?  I presume only PHIs in loop headers are to be
considered?

Richard.

>
> for  gcc/ChangeLog
>
>         PR tree-optimization/105665
>         PR tree-optimization/100810
>         * tree-ssa-loop-ivopts.cc (mark_ssa_undefs): Precompute
>         unsuitability of SSA_NAMEs in TREE_VISITED.
>         (find_ssa_undef): Check the precomputed flag.
>         (tree_ssa_iv_optimize): Call mark_ssa_undefs.
>
> for  gcc/testsuite/ChangeLog
>
>         PR tree-optimization/105665
>         PR tree-optimization/100810
>         * gcc.dg/torture/pr105665.c: New.
> ---
>  gcc/testsuite/gcc.dg/torture/pr105665.c |   20 ++++++++++
>  gcc/tree-ssa-loop-ivopts.cc             |   62 ++++++++++++++++++++++++++++++-
>  2 files changed, 80 insertions(+), 2 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/torture/pr105665.c
>
> diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
> new file mode 100644
> index 0000000000000..34cfc65843495
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
> @@ -0,0 +1,20 @@
> +/* { dg-do run } */
> +
> +int a, b, c[1], d[2], *e = c;
> +int main() {
> +  int f = 0;
> +  for (; b < 2; b++) {
> +    int g;
> +    if (f)
> +      g++, b = 40;
> +    a = d[b * b];
> +    for (f = 0; f < 3; f++) {
> +      if (e)
> +        break;
> +      g--;
> +      if (a)
> +        a = g;
> +    }
> +  }
> +  return 0;
> +}
> diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
> index 81b536f930415..d8200f2a53b21 100644
> --- a/gcc/tree-ssa-loop-ivopts.cc
> +++ b/gcc/tree-ssa-loop-ivopts.cc
> @@ -3071,13 +3071,70 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
>    return *slot;
>  }
>
> -/* Find the first undefined SSA name in *TP.  */
> +/* Mark as TREe_VISITED any SSA_NAMEs that are unsuitable as ivopts
> +   candidates for potentially involving undefined behavior.  */
> +
> +static void
> +mark_ssa_undefs (void)
> +{
> +  auto_vec<tree> queue;
> +
> +  unsigned int i;
> +  tree var;
> +  FOR_EACH_SSA_NAME (i, var, cfun)
> +    {
> +      if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
> +         || ssa_defined_default_def_p (var)
> +         || !ssa_undefined_value_p (var, false))
> +       TREE_VISITED (var) = false;
> +      else
> +       {
> +         TREE_VISITED (var) = true;
> +         queue.safe_push (var);
> +         if (dump_file)
> +           fprintf (dump_file, "marking _%i as undef\n",
> +                    SSA_NAME_VERSION (var));
> +       }
> +    }
> +
> +  while (!queue.is_empty ())
> +    {
> +      var = queue.pop ();
> +      gimple *stmt;
> +      imm_use_iterator iter;
> +      FOR_EACH_IMM_USE_STMT (stmt, iter, var)
> +       {
> +         if (is_gimple_call (stmt) || is_a <gasm *> (stmt))
> +           continue;
> +
> +         def_operand_p defvar;
> +         ssa_op_iter diter;
> +         FOR_EACH_PHI_OR_STMT_DEF (defvar, stmt, diter, SSA_OP_DEF)
> +           {
> +             gcc_checking_assert (is_gimple_assign (stmt)
> +                                  || is_a <gphi *> (stmt));
> +             tree def = DEF_FROM_PTR (defvar);
> +             if (TREE_VISITED (def))
> +               continue;
> +             TREE_VISITED (def) = true;
> +             queue.safe_push (def);
> +             if (dump_file)
> +               fprintf (dump_file, "Marking _%i as undef because of _%i\n",
> +                        SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
> +           }
> +       }
> +    }
> +}
> +
> +/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
> +   unsuitable as ivopts candidates for potentially involving undefined
> +   behavior.  */
>
>  static tree
>  find_ssa_undef (tree *tp, int *walk_subtrees, void *)
>  {
>    if (TREE_CODE (*tp) == SSA_NAME
> -      && ssa_undefined_value_p (*tp, false))
> +      && TREE_VISITED (*tp))
>      return *tp;
>    if (!EXPR_P (*tp))
>      *walk_subtrees = 0;
> @@ -8192,6 +8249,7 @@ tree_ssa_iv_optimize (void)
>    auto_bitmap toremove;
>
>    tree_ssa_iv_optimize_init (&data);
> +  mark_ssa_undefs ();
>
>    /* Optimize the loops starting with the innermost ones.  */
>    for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
>
>
> --
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>    Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>