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