Re: [PATCH] Reset relations when crossing backedges.

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

On Fri, Jan 21, 2022 at 9:30 AM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> As discussed in PR103721, the problem here is that we are crossing a
> backedge and causing us to use relations from a previous iteration of a
> loop.
>
> This handles the testcases in both PR103721 and PR104067 which are variants
> of the same thing.
>
> Tested on x86-64 Linux with the usual regstrap as well as verifying the
> thread count before and after the patch.  The number of threads is
> reduced by a miniscule amount.
>
> I assume we need release manager approval at this point?  OK for trunk?

Not for regression fixes.

Btw, I wonder whether you have to treat irreducible regions in the same
way more generally - which edges are marked as backedge there depends
on which edge into the region was visited first.  I also wonder how we
guarantee that all users of the resolve mode have backedges marked
properly?  Also note that CFG manipulation routines in general do not
keep backedge markings up-to-date so incremental modification and
resolving queries might not mix.

It's a bit unfortunate that we can't query the CFG on whether backedges
are marked.

If you're only dealing with non-irreducible regions you can use a
dominance query to identify a backedge.  Oh, and irreducible regions
are also not marked (but at least CFG manipulation tries to conservatively
keep that info up-to-date).

> gcc/ChangeLog:
>
>         PR 103721/tree-optimization

swapped, it should be PR tree-optimization/103721

>         * gimple-range-path.cc
>         (path_range_query::relations_may_be_invalidated): New.
>         (path_range_query::compute_ranges_in_block): Reset relations if
>         they may be invalidated.
>         (path_range_query::maybe_register_phi_relation): Exit if relations
>         may be invalidated on incoming edge.
>         (path_range_query::compute_phi_relations): Pass incoming PHI edge
>         to maybe_register_phi_relation.
>         * gimple-range-path.h (relations_may_be_invalidated): New.
>         (maybe_register_phi_relation): Pass edge instead of tree.
>         * tree-ssa-threadbackward.cc (back_threader::back_threader):
>         * value-relation.cc (path_oracle::path_oracle): Call
>         mark_dfs_back_edges.
>         (path_oracle::register_relation): Add SSA names to m_registered
>         bitmap.
>         (path_oracle::reset_path): Clear m_registered bitmap.
>         * value-relation.h (path_oracle::set_root_oracle): New.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/pr103721-2.c: New test.
>         * gcc.dg/pr103721.c: New test.
> ---
>  gcc/gimple-range-path.cc          | 48 +++++++++++++++++++++++++++----
>  gcc/gimple-range-path.h           |  3 +-
>  gcc/testsuite/gcc.dg/pr103721-2.c | 28 ++++++++++++++++++
>  gcc/testsuite/gcc.dg/pr103721.c   | 25 ++++++++++++++++
>  gcc/tree-ssa-threadbackward.cc    |  4 +++
>  gcc/value-relation.cc             |  4 +--
>  gcc/value-relation.h              |  1 +
>  7 files changed, 104 insertions(+), 9 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/pr103721-2.c
>  create mode 100644 gcc/testsuite/gcc.dg/pr103721.c
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index a1bcca0b5fb..3ee4989f4b0 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -400,6 +400,19 @@ path_range_query::compute_ranges_in_phis (basic_block bb)
>    bitmap_ior_into (m_has_cache_entry, phi_set);
>  }
>
> +// Return TRUE if relations may be invalidated after crossing edge E.
> +
> +bool
> +path_range_query::relations_may_be_invalidated (edge e)
> +{
> +  // As soon as the path crosses a back edge, we can encounter
> +  // definitions of SSA_NAMEs that may have had a use in the path
> +  // already, so this will then be a new definition.  The relation
> +  // code is all designed around seeing things in dominator order, and
> +  // crossing a back edge in the path violates this assumption.
> +  return (e->flags & EDGE_DFS_BACK);
> +}
> +
>  // Compute ranges defined in the current block, or exported to the
>  // next block.
>
> @@ -440,6 +453,22 @@ path_range_query::compute_ranges_in_block (basic_block bb)
>    // Solve imports that are exported to the next block.
>    basic_block next = next_bb ();
>    edge e = find_edge (bb, next);
> +
> +  if (m_resolve && relations_may_be_invalidated (e))
> +    {
> +      if (DEBUG_SOLVER)
> +       fprintf (dump_file,
> +                "Resetting relations as they may be invalidated in %d->%d.\n",
> +                e->src->index, e->dest->index);
> +
> +      path_oracle *p = get_path_oracle ();
> +      p->reset_path ();
> +      // ?? Instead of nuking the root oracle altogether, we could
> +      // reset the path oracle to search for relations from the top of
> +      // the loop with the root oracle.  Something for future development.
> +      p->set_root_oracle (nullptr);
> +    }
> +
>    EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
>      {
>        tree name = ssa_name (i);
> @@ -742,9 +771,19 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
>    return true;
>  }
>
> +// If possible, register the relation on the incoming edge E into PHI.
> +
>  void
> -path_range_query::maybe_register_phi_relation (gphi *phi, tree arg)
> +path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
>  {
> +  tree arg = gimple_phi_arg_def (phi, e->dest_idx);
> +
> +  if (!gimple_range_ssa_p (arg))
> +    return;
> +
> +  if (relations_may_be_invalidated (e))
> +    return;
> +
>    basic_block bb = gimple_bb (phi);
>    tree result = gimple_phi_result (phi);
>
> @@ -754,7 +793,7 @@ path_range_query::maybe_register_phi_relation (gphi *phi, tree arg)
>      return;
>
>    if (dump_file && (dump_flags & TDF_DETAILS))
> -    fprintf (dump_file, "  from bb%d:", bb->index);
> +    fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
>
>    get_path_oracle ()->killing_def (result);
>    m_oracle->register_relation (entry_bb (), EQ_EXPR, arg, result);
> @@ -787,10 +826,7 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
>        for (size_t i = 0; i < nargs; ++i)
>         if (e_in == gimple_phi_arg_edge (phi, i))
>           {
> -           tree arg = gimple_phi_arg_def (phi, i);
> -
> -           if (gimple_range_ssa_p (arg))
> -             maybe_register_phi_relation (phi, arg);
> +           maybe_register_phi_relation (phi, e_in);
>             break;
>           }
>      }
> diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
> index f090b7c2727..1820626161f 100644
> --- a/gcc/gimple-range-path.h
> +++ b/gcc/gimple-range-path.h
> @@ -63,10 +63,11 @@ private:
>    void ssa_range_in_phi (irange &r, gphi *phi);
>    void compute_outgoing_relations (basic_block bb, basic_block next);
>    void compute_phi_relations (basic_block bb, basic_block prev);
> -  void maybe_register_phi_relation (gphi *, tree arg);
> +  void maybe_register_phi_relation (gphi *, edge e);
>    bool add_to_imports (tree name, bitmap imports);
>    bool import_p (tree name);
>    bool ssa_defined_in_bb (tree name, basic_block bb);
> +  bool relations_may_be_invalidated (edge);
>
>    // Path navigation.
>    void set_path (const vec<basic_block> &);
> diff --git a/gcc/testsuite/gcc.dg/pr103721-2.c b/gcc/testsuite/gcc.dg/pr103721-2.c
> new file mode 100644
> index 00000000000..aefa1f0f147
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr103721-2.c
> @@ -0,0 +1,28 @@
> +// { dg-do run }
> +// { dg-options "-O2" }
> +
> +extern void abort ();
> +struct S { int x; } a[10];
> +struct S *b;
> +
> +int
> +main ()
> +{
> +  int i, j = 0;
> +  struct S *q = a;
> +
> +  for (i = 100; --i > 0; )
> +    {
> +      struct S *p;
> +      j++;
> +      if (j >= 10)
> +        j = 0;
> +      p = &a[j];
> +
> +      if (p == q)
> +        abort ();
> +      __atomic_thread_fence (__ATOMIC_SEQ_CST);
> +      q = p;
> +    }
> +  return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/pr103721.c b/gcc/testsuite/gcc.dg/pr103721.c
> new file mode 100644
> index 00000000000..6ec2e44b30f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr103721.c
> @@ -0,0 +1,25 @@
> +// { dg-do run }
> +// { dg-options "-O2" }
> +
> +int ipos = 0;
> +int f (int world)
> +{
> +  int searchVolume = world;
> +  int currentVolume = 0;
> +  while (currentVolume != searchVolume && searchVolume) {
> +    currentVolume = searchVolume;
> +    if (ipos != 0)
> +      searchVolume = 0;
> +    else
> +      searchVolume = 1;
> +  }
> +  return (currentVolume);
> +}
> +int main()
> +{
> +  const int i = f (1111);
> +  __builtin_printf ("%d\n", (int)(i));
> +  if (i != 1)
> +   __builtin_abort ();
> +  return 0;
> +}
> diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> index d685b659df0..3ca65b32216 100644
> --- a/gcc/tree-ssa-threadbackward.cc
> +++ b/gcc/tree-ssa-threadbackward.cc
> @@ -144,6 +144,10 @@ back_threader::back_threader (function *fun, unsigned flags, bool first)
>    m_flags = flags;
>    m_solver = new path_range_query (flags & BT_RESOLVE);
>    m_last_stmt = NULL;
> +
> +  // The path solver needs EDGE_DFS_BACK in resolving mode.
> +  if (flags & BT_RESOLVE)
> +    mark_dfs_back_edges ();
>  }
>
>  back_threader::~back_threader ()
> diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
> index 32ca693c464..fcb574553df 100644
> --- a/gcc/value-relation.cc
> +++ b/gcc/value-relation.cc
> @@ -1234,7 +1234,7 @@ relation_oracle::debug () const
>
>  path_oracle::path_oracle (relation_oracle *oracle)
>  {
> -  m_root = oracle;
> +  set_root_oracle (oracle);
>    bitmap_obstack_initialize (&m_bitmaps);
>    obstack_init (&m_chain_obstack);
>
> @@ -1368,7 +1368,7 @@ path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
>        value_relation vr (k, ssa1, ssa2);
>        fprintf (dump_file, " Registering value_relation (path_oracle) ");
>        vr.dump (dump_file);
> -      fprintf (dump_file, " (bb%d)\n", bb->index);
> +      fprintf (dump_file, " (root: bb%d)\n", bb->index);
>      }
>
>    if (k == EQ_EXPR)
> diff --git a/gcc/value-relation.h b/gcc/value-relation.h
> index 44d0796d939..848ffd3dab0 100644
> --- a/gcc/value-relation.h
> +++ b/gcc/value-relation.h
> @@ -227,6 +227,7 @@ public:
>    relation_kind query_relation (basic_block, tree, tree);
>    relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
>    void reset_path ();
> +  void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
>    void dump (FILE *, basic_block) const;
>    void dump (FILE *) const;
>  private:
> --
> 2.34.1
>