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