[gcc r12-6787] Reset relations when crossing backedges.

[gcc r12-6787] Reset relations when crossing backedges.

[Aldy Hernandez]

https://gcc.gnu.org/g:eb5ee6464809e051e0292471597931a660485658

commit r12-6787-geb5ee6464809e051e0292471597931a660485658
Author: Aldy Hernandez <aldyh@redhat.com>
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<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 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: