From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2136) id 5C5123858C2C; Fri, 21 Jan 2022 10:19:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5C5123858C2C MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Aldy Hernandez To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-6787] Reset relations when crossing backedges. X-Act-Checkin: gcc X-Git-Author: Aldy Hernandez X-Git-Refname: refs/heads/master X-Git-Oldrev: c2d9159717b474f9c06dde4d32b48b87164deb50 X-Git-Newrev: eb5ee6464809e051e0292471597931a660485658 Message-Id: <20220121101922.5C5123858C2C@sourceware.org> Date: Fri, 21 Jan 2022 10:19:22 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 21 Jan 2022 10:19:22 -0000 https://gcc.gnu.org/g:eb5ee6464809e051e0292471597931a660485658 commit r12-6787-geb5ee6464809e051e0292471597931a660485658 Author: Aldy Hernandez Date: Thu Jan 20 10:28:26 2022 +0100 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. gcc/ChangeLog: 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): Mark DFS edges. * 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. Diff: --- 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(-) 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 &); 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 0134e0328ba..077ab4230a7 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1251,7 +1251,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); @@ -1385,7 +1385,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 d840234f355..6f471338fdf 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -229,6 +229,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: