Reset relations when crossing backedges.

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?

gcc/ChangeLog:

	PR 103721/tree-optimization
	* 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

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
>

On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> 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.

OK, I've pushed it to fix the P1s.  We can continue refining the
solution in a follow-up patch.

>
> 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

Jeff, Andrew??

> 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.

Ughh.  The call to mark_dfs_back_edges is currently in the backward
threader.  Perhaps we could put it in the path_range_query
constructor?  That way other users of path_range_query can benefit
(loop_ch for instance, though it doesn't use it in a way that crosses
backedges so perhaps it's unaffected).  Does that sound reasonable?

Aldy

>
> 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
> >
>

On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > 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.
>
> OK, I've pushed it to fix the P1s.  We can continue refining the
> solution in a follow-up patch.
>
> >
> > 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
>
> Jeff, Andrew??
>
> > 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.
>
> Ughh.  The call to mark_dfs_back_edges is currently in the backward
> threader.  Perhaps we could put it in the path_range_query
> constructor?  That way other users of path_range_query can benefit
> (loop_ch for instance, though it doesn't use it in a way that crosses
> backedges so perhaps it's unaffected).  Does that sound reasonable?

Hmm, I'd rather keep the burden on the callers because many already
should have backedges marked.  What you could instead do is
add sth like

  if (flag_checking)
    {
       auto_edge_flag saved_dfs_back;
       for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
set, clear dfs_back
       mark_dfs_back_edges ();
       for-each-edge-in-cfg () verify the flags are set on the same
edges and clear saved_dfs_back
    }

to the path_range_query constructor.  That way we at least notice when passes
do _not_ have the backedges marked properly.

Richard.

> Aldy
>
> >
> > 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
> > >
> >
>

On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > >
> > > 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.
> >
> > OK, I've pushed it to fix the P1s.  We can continue refining the
> > solution in a follow-up patch.
> >
> > >
> > > 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
> >
> > Jeff, Andrew??
> >
> > > 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.
> >
> > Ughh.  The call to mark_dfs_back_edges is currently in the backward
> > threader.  Perhaps we could put it in the path_range_query
> > constructor?  That way other users of path_range_query can benefit
> > (loop_ch for instance, though it doesn't use it in a way that crosses
> > backedges so perhaps it's unaffected).  Does that sound reasonable?
>
> Hmm, I'd rather keep the burden on the callers because many already
> should have backedges marked.  What you could instead do is
> add sth like
>
>   if (flag_checking)
>     {
>        auto_edge_flag saved_dfs_back;
>        for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
> set, clear dfs_back
>        mark_dfs_back_edges ();
>        for-each-edge-in-cfg () verify the flags are set on the same
> edges and clear saved_dfs_back
>     }
>
> to the path_range_query constructor.  That way we at least notice when passes
> do _not_ have the backedges marked properly.

Sounds good.  Thanks.

I've put the verifier by mark_dfs_back_edges(), since it really has
nothing to do with the path solver.  Perhaps it's useful for someone
else.

The patch triggered with the loop-ch use, so I've added a
corresponding mark_dfs_back_edges there.

OK pending tests?

Aldy

On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > > <richard.guenther@gmail.com> wrote:
> > > >
> > > > 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.
> > >
> > > OK, I've pushed it to fix the P1s.  We can continue refining the
> > > solution in a follow-up patch.
> > >
> > > >
> > > > 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
> > >
> > > Jeff, Andrew??
> > >
> > > > 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.
> > >
> > > Ughh.  The call to mark_dfs_back_edges is currently in the backward
> > > threader.  Perhaps we could put it in the path_range_query
> > > constructor?  That way other users of path_range_query can benefit
> > > (loop_ch for instance, though it doesn't use it in a way that crosses
> > > backedges so perhaps it's unaffected).  Does that sound reasonable?
> >
> > Hmm, I'd rather keep the burden on the callers because many already
> > should have backedges marked.  What you could instead do is
> > add sth like
> >
> >   if (flag_checking)
> >     {
> >        auto_edge_flag saved_dfs_back;
> >        for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
> > set, clear dfs_back
> >        mark_dfs_back_edges ();
> >        for-each-edge-in-cfg () verify the flags are set on the same
> > edges and clear saved_dfs_back
> >     }
> >
> > to the path_range_query constructor.  That way we at least notice when passes
> > do _not_ have the backedges marked properly.
>
> Sounds good.  Thanks.
>
> I've put the verifier by mark_dfs_back_edges(), since it really has
> nothing to do with the path solver.  Perhaps it's useful for someone
> else.
>
> The patch triggered with the loop-ch use, so I've added a
> corresponding mark_dfs_back_edges there.
>
> OK pending tests?

Please rename dfs_back_edges_available_p to sth not suggesting
it's a simple predicate check, like maybe verify_marked_backedges.

+
+  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());

I'd prefer the following which allows even release checking builds
to verify this with -fchecking.

  if (!m_resolve)
    if (flag_checking)
      verify_marked_backedges ();

and then ideally verify_marked_backedges () should raise an
internal_error () for the edge not marked properly, best by
also specifying it.  Just like other CFG verifiers do.

The loop ch and backwards threader changes are OK.  You
can post the verification independently again.

Thanks,
Richard.

>
> Aldy

On Mon, Jan 24, 2022 at 9:51 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> > > >
> > > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > > > <richard.guenther@gmail.com> wrote:
> > > > >
> > > > > 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.
> > > >
> > > > OK, I've pushed it to fix the P1s.  We can continue refining the
> > > > solution in a follow-up patch.
> > > >
> > > > >
> > > > > 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
> > > >
> > > > Jeff, Andrew??
> > > >
> > > > > 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.
> > > >
> > > > Ughh.  The call to mark_dfs_back_edges is currently in the backward
> > > > threader.  Perhaps we could put it in the path_range_query
> > > > constructor?  That way other users of path_range_query can benefit
> > > > (loop_ch for instance, though it doesn't use it in a way that crosses
> > > > backedges so perhaps it's unaffected).  Does that sound reasonable?
> > >
> > > Hmm, I'd rather keep the burden on the callers because many already
> > > should have backedges marked.  What you could instead do is
> > > add sth like
> > >
> > >   if (flag_checking)
> > >     {
> > >        auto_edge_flag saved_dfs_back;
> > >        for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
> > > set, clear dfs_back
> > >        mark_dfs_back_edges ();
> > >        for-each-edge-in-cfg () verify the flags are set on the same
> > > edges and clear saved_dfs_back
> > >     }
> > >
> > > to the path_range_query constructor.  That way we at least notice when passes
> > > do _not_ have the backedges marked properly.
> >
> > Sounds good.  Thanks.
> >
> > I've put the verifier by mark_dfs_back_edges(), since it really has
> > nothing to do with the path solver.  Perhaps it's useful for someone
> > else.
> >
> > The patch triggered with the loop-ch use, so I've added a
> > corresponding mark_dfs_back_edges there.
> >
> > OK pending tests?
>
> Please rename dfs_back_edges_available_p to sth not suggesting
> it's a simple predicate check, like maybe verify_marked_backedges.
>
> +
> +  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());
>
> I'd prefer the following which allows even release checking builds
> to verify this with -fchecking.
>
>   if (!m_resolve)
>     if (flag_checking)
>       verify_marked_backedges ();
>
> and then ideally verify_marked_backedges () should raise an
> internal_error () for the edge not marked properly, best by
> also specifying it.  Just like other CFG verifiers do.
>
> The loop ch and backwards threader changes are OK.  You
> can post the verification independently again.

How about this?

Tested on x86-64 Linux.

On 1/21/2022 3:29 AM, Aldy Hernandez wrote:
> On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
>> 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.
> OK, I've pushed it to fix the P1s.  We can continue refining the
> solution in a follow-up patch.
>
>> 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
> Jeff, Andrew??
I think this comes down to the dominator discussion we were having in 
BZ.   My understanding from reading Andrew's messages is that need to 
reset relations when we cross an edge where the source of the edge does 
not dominate the destination of the edge.   That would solve the loop 
problem,  the irreducible region problem and I think other possibly 
latent problems with threading & relations.

Jeff

Ping

On Mon, Jan 24, 2022, 20:20 Aldy Hernandez <aldyh@redhat.com> wrote:

> On Mon, Jan 24, 2022 at 9:51 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
> > > <richard.guenther@gmail.com> wrote:
> > > >
> > > > On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com>
> wrote:
> > > > >
> > > > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > > > > <richard.guenther@gmail.com> wrote:
> > > > > >
> > > > > > 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.
> > > > >
> > > > > OK, I've pushed it to fix the P1s.  We can continue refining the
> > > > > solution in a follow-up patch.
> > > > >
> > > > > >
> > > > > > 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
> > > > >
> > > > > Jeff, Andrew??
> > > > >
> > > > > > 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.
> > > > >
> > > > > Ughh.  The call to mark_dfs_back_edges is currently in the backward
> > > > > threader.  Perhaps we could put it in the path_range_query
> > > > > constructor?  That way other users of path_range_query can benefit
> > > > > (loop_ch for instance, though it doesn't use it in a way that
> crosses
> > > > > backedges so perhaps it's unaffected).  Does that sound reasonable?
> > > >
> > > > Hmm, I'd rather keep the burden on the callers because many already
> > > > should have backedges marked.  What you could instead do is
> > > > add sth like
> > > >
> > > >   if (flag_checking)
> > > >     {
> > > >        auto_edge_flag saved_dfs_back;
> > > >        for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
> > > > set, clear dfs_back
> > > >        mark_dfs_back_edges ();
> > > >        for-each-edge-in-cfg () verify the flags are set on the same
> > > > edges and clear saved_dfs_back
> > > >     }
> > > >
> > > > to the path_range_query constructor.  That way we at least notice
> when passes
> > > > do _not_ have the backedges marked properly.
> > >
> > > Sounds good.  Thanks.
> > >
> > > I've put the verifier by mark_dfs_back_edges(), since it really has
> > > nothing to do with the path solver.  Perhaps it's useful for someone
> > > else.
> > >
> > > The patch triggered with the loop-ch use, so I've added a
> > > corresponding mark_dfs_back_edges there.
> > >
> > > OK pending tests?
> >
> > Please rename dfs_back_edges_available_p to sth not suggesting
> > it's a simple predicate check, like maybe verify_marked_backedges.
> >
> > +
> > +  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());
> >
> > I'd prefer the following which allows even release checking builds
> > to verify this with -fchecking.
> >
> >   if (!m_resolve)
> >     if (flag_checking)
> >       verify_marked_backedges ();
> >
> > and then ideally verify_marked_backedges () should raise an
> > internal_error () for the edge not marked properly, best by
> > also specifying it.  Just like other CFG verifiers do.
> >
> > The loop ch and backwards threader changes are OK.  You
> > can post the verification independently again.
>
> How about this?
>
> Tested on x86-64 Linux.
>

On Tue, Feb 1, 2022 at 7:41 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Ping

I didn't quite get Jeffs comment, so I waited (sorry).  I've meanwhile added

extern bool mark_dfs_back_edges (struct function *);

so please make verify_mark_backedges take a struct function * and replace
'cfun' with the explicit argument.

+           gcc_unreachable ();

should be sth like

            internal_error ("%<verify_marked_backedges%> failed");

OK with those changes.

Thanks,
Richard.

> On Mon, Jan 24, 2022, 20:20 Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> On Mon, Jan 24, 2022 at 9:51 AM Richard Biener
>> <richard.guenther@gmail.com> wrote:
>> >
>> > On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>> > >
>> > > On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
>> > > <richard.guenther@gmail.com> wrote:
>> > > >
>> > > > On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>> > > > >
>> > > > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
>> > > > > <richard.guenther@gmail.com> wrote:
>> > > > > >
>> > > > > > 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.
>> > > > >
>> > > > > OK, I've pushed it to fix the P1s.  We can continue refining the
>> > > > > solution in a follow-up patch.
>> > > > >
>> > > > > >
>> > > > > > 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
>> > > > >
>> > > > > Jeff, Andrew??
>> > > > >
>> > > > > > 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.
>> > > > >
>> > > > > Ughh.  The call to mark_dfs_back_edges is currently in the backward
>> > > > > threader.  Perhaps we could put it in the path_range_query
>> > > > > constructor?  That way other users of path_range_query can benefit
>> > > > > (loop_ch for instance, though it doesn't use it in a way that crosses
>> > > > > backedges so perhaps it's unaffected).  Does that sound reasonable?
>> > > >
>> > > > Hmm, I'd rather keep the burden on the callers because many already
>> > > > should have backedges marked.  What you could instead do is
>> > > > add sth like
>> > > >
>> > > >   if (flag_checking)
>> > > >     {
>> > > >        auto_edge_flag saved_dfs_back;
>> > > >        for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is
>> > > > set, clear dfs_back
>> > > >        mark_dfs_back_edges ();
>> > > >        for-each-edge-in-cfg () verify the flags are set on the same
>> > > > edges and clear saved_dfs_back
>> > > >     }
>> > > >
>> > > > to the path_range_query constructor.  That way we at least notice when passes
>> > > > do _not_ have the backedges marked properly.
>> > >
>> > > Sounds good.  Thanks.
>> > >
>> > > I've put the verifier by mark_dfs_back_edges(), since it really has
>> > > nothing to do with the path solver.  Perhaps it's useful for someone
>> > > else.
>> > >
>> > > The patch triggered with the loop-ch use, so I've added a
>> > > corresponding mark_dfs_back_edges there.
>> > >
>> > > OK pending tests?
>> >
>> > Please rename dfs_back_edges_available_p to sth not suggesting
>> > it's a simple predicate check, like maybe verify_marked_backedges.
>> >
>> > +
>> > +  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());
>> >
>> > I'd prefer the following which allows even release checking builds
>> > to verify this with -fchecking.
>> >
>> >   if (!m_resolve)
>> >     if (flag_checking)
>> >       verify_marked_backedges ();
>> >
>> > and then ideally verify_marked_backedges () should raise an
>> > internal_error () for the edge not marked properly, best by
>> > also specifying it.  Just like other CFG verifiers do.
>> >
>> > The loop ch and backwards threader changes are OK.  You
>> > can post the verification independently again.
>>
>> How about this?
>>
>> Tested on x86-64 Linux.

Hello,

On Fri, Jan 21 2022, Aldy Hernandez via Gcc-patches 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?
>
> gcc/ChangeLog:
>
> 	PR 103721/tree-optimization
> 	* 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.

this has caused around 5% regression of 429.mcf when built with -O2 -flto
(generic march) on x86_64 (I tried and confirmed on AMD Zen3, Zen2 and
Intel Cascadelake), the two former cases can be seen here:

https://lnt.opensuse.org/db_default/v4/SPEC/graph?plot.0=469.60.0
https://lnt.opensuse.org/db_default/v4/SPEC/graph?plot.0=413.60.0&plot.1=292.60.0&

This does not seem to be a regression against gcc11 and I am not sure
whether it is worth a bug-report, but perhaps it is worth looking at as
it may indicate where we can improve further?

Martin

On 2/2/2022 2:27 AM, Richard Biener wrote:
> On Tue, Feb 1, 2022 at 7:41 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>> Ping
> I didn't quite get Jeffs comment, so I waited (sorry).  I've meanwhile added
Sorry.  IIRC the concern was whether or not we need to do something 
special for irreducible regions.  In that case which edge gets marked as 
the backedge depends on graph traversal order.  My suggestion was to use 
the dominance relationship instead of edge flags.

Jeff

On Sat, Mar 19, 2022 at 8:27 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 2/2/2022 2:27 AM, Richard Biener wrote:
> > On Tue, Feb 1, 2022 at 7:41 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >> Ping
> > I didn't quite get Jeffs comment, so I waited (sorry).  I've meanwhile added
> Sorry.  IIRC the concern was whether or not we need to do something
> special for irreducible regions.  In that case which edge gets marked as
> the backedge depends on graph traversal order.  My suggestion was to use
> the dominance relationship instead of edge flags.

Ah.  Yes - it depends on what situation we are trying to detect here.  If we
are just trying to identify PHI arguments from "backedges" using dominance
info is good.  If we are trying to detect backedges from a CFG walk then we
have to use a backedge DFS that matches our CFG walk, otherwise the
backedges might not match ours for irreducible regions.

Richard.

> Jeff
>