[gcc r12-3632] Provide a relation oracle for paths.

[gcc r12-3632] Provide a relation oracle for paths.

[Andrew Macleod]

https://gcc.gnu.org/g:534c5352a02485a41ebfb133b42edbbecba7eba3

commit r12-3632-g534c5352a02485a41ebfb133b42edbbecba7eba3
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Sep 17 09:48:35 2021 -0400

    Provide a relation oracle for paths.
    
    This provides a path_oracle class which can optionally be used in conjunction
    with another oracle to track relations on a path as it is walked.
    
            * value-relation.cc (class equiv_chain): Move to header file.
            (path_oracle::path_oracle): New.
            (path_oracle::~path_oracle): New.
            (path_oracle::register_relation): New.
            (path_oracle::query_relation): New.
            (path_oracle::reset_path): New.
            (path_oracle::dump): New.
            * value-relation.h (class equiv_chain): Move to here.
            (class path_oracle): New.

Diff:
---
 gcc/value-relation.cc | 188 ++++++++++++++++++++++++++++++++++++++++++++++----
 gcc/value-relation.h  |  51 +++++++++++++-
 2 files changed, 224 insertions(+), 15 deletions(-)

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index 3e077d38a11..d370f93d128 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -190,9 +190,6 @@ relation_transitive (relation_kind r1, relation_kind r2)
 
 // -------------------------------------------------------------------------
 
-// This class represents an equivalency set, and contains a link to the next
-// one in the list to be searched.
-
 // The very first element in the m_equiv chain is actually just a summary
 // element in which the m_names bitmap is used to indicate that an ssa_name
 // has an equivalence set in this block.
@@ -201,16 +198,6 @@ relation_transitive (relation_kind r1, relation_kind r2)
 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
 // that block.   No previous lists need be searched.
 
-class equiv_chain
-{
-public:
-  bitmap m_names;		// ssa-names in equiv set.
-  basic_block m_bb;		// Block this belongs to
-  equiv_chain *m_next;		// Next in block list.
-  void dump (FILE *f) const;	// Show names in this list.
-  equiv_chain *find (unsigned ssa);
-};
-
 // If SSA has an equivalence in this list, find and return it.
 // Otherwise return NULL.
 
@@ -1172,3 +1159,178 @@ relation_oracle::debug () const
 {
   dump (stderr);
 }
+
+path_oracle::path_oracle (relation_oracle *oracle)
+{
+  m_root = oracle;
+  bitmap_obstack_initialize (&m_bitmaps);
+  obstack_init (&m_chain_obstack);
+
+  // Initialize header records.
+  m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
+  m_equiv.m_bb = NULL;
+  m_equiv.m_next = NULL;
+  m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
+  m_relations.m_head = NULL;
+}
+
+path_oracle::~path_oracle ()
+{
+  obstack_free (&m_chain_obstack, NULL);
+  bitmap_obstack_release (&m_bitmaps);
+}
+
+// Return the equiv set for SSA, and if there isn't one, check for equivs
+// starting in block BB.
+
+const_bitmap
+path_oracle::equiv_set (tree ssa, basic_block bb)
+{
+  // Check the list first.
+  equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
+  if (ptr)
+    return ptr->m_names;
+
+  // Otherwise defer to the root oracle.
+  if (m_root)
+    return m_root->equiv_set (ssa, bb);
+
+  // Allocate a throw away bitmap if there isn't a root oracle.
+  bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
+  bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
+  return tmp;
+}
+
+// Register an equivalence between SSA1 and SSA2 resolving unkowns from
+// block BB.
+
+void
+path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
+{
+  const_bitmap equiv_1 = equiv_set (ssa1, bb);
+  const_bitmap equiv_2 = equiv_set (ssa2, bb);
+
+  // Check if they are the same set, if so, we're done.
+  if (bitmap_equal_p (equiv_1, equiv_2))
+    return;
+
+  // Don't mess around, simply create a new record and insert it first.
+  bitmap b = BITMAP_ALLOC (&m_bitmaps);
+  bitmap_copy (b, equiv_1);
+  bitmap_ior_into (b, equiv_2);
+
+  equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
+						    sizeof (equiv_chain));
+  ptr->m_names = b;
+  ptr->m_bb = NULL;
+  ptr->m_next = m_equiv.m_next;
+  m_equiv.m_next = ptr;
+  bitmap_ior_into (m_equiv.m_names, b);
+}
+
+// Register relation K between SSA1 and SSA2, resolving unknowns by
+// querying from BB.
+
+void
+path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
+				tree ssa2)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      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);
+    }
+
+  if (k == EQ_EXPR)
+    {
+      register_equiv (bb, ssa1, ssa2);
+      return;
+    }
+
+  relation_kind curr = query_relation (bb, ssa1, ssa2);
+  if (curr != VREL_NONE)
+    k = relation_intersect (curr, k);
+
+  bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
+  bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
+  relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
+						      sizeof (relation_chain));
+  ptr->set_relation (k, ssa1, ssa2);
+  ptr->m_next = m_relations.m_head;
+  m_relations.m_head = ptr;
+}
+
+// Query for a relationship between equiv set B1 and B2, resolving unknowns
+// starting at block BB.
+
+relation_kind
+path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
+{
+  if (bitmap_equal_p (b1, b2))
+    return EQ_EXPR;
+
+  relation_kind k = m_relations.find_relation (b1, b2);
+
+  if (k == VREL_NONE && m_root)
+    k = m_root->query_relation (bb, b1, b2);
+
+  return k;
+}
+
+// Query for a relationship between SSA1 and SSA2, resolving unknowns
+// starting at block BB.
+
+relation_kind
+path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
+{
+  unsigned v1 = SSA_NAME_VERSION (ssa1);
+  unsigned v2 = SSA_NAME_VERSION (ssa2);
+
+  if (v1 == v2)
+    return EQ_EXPR;
+
+  const_bitmap equiv_1 = equiv_set (ssa1, bb);
+  const_bitmap equiv_2 = equiv_set (ssa2, bb);
+  if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
+    return EQ_EXPR;
+
+  return query_relation (bb, equiv_1, equiv_2);
+}
+
+// Reset any relations registered on this path.
+
+void
+path_oracle::reset_path ()
+{
+  m_equiv.m_next = NULL;
+  bitmap_clear (m_equiv.m_names);
+  m_relations.m_head = NULL;
+  bitmap_clear (m_relations.m_names);
+}
+
+// Dump relation in basic block... Do nothing here.
+
+void
+path_oracle::dump (FILE *, basic_block) const
+{
+}
+
+// Dump the relations and equivalencies found in the path.
+
+void
+path_oracle::dump (FILE *f) const
+{
+  equiv_chain *ptr = m_equiv.m_next;
+  for (; ptr; ptr = ptr->m_next)
+    ptr->dump (f);
+
+  relation_chain *ptr2 = m_relations.m_head;
+  for (; ptr2; ptr2 = ptr2->m_next)
+    {
+      fprintf (f, "Relational : ");
+      ptr2->dump (f);
+      fprintf (f, "\n");
+    }
+}
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index 323b1e6be8d..574fdc9efe8 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -98,8 +98,18 @@ public:
   void debug () const;
 };
 
-// Declared internally in value-relation.cc
-class equiv_chain;
+// This class represents an equivalency set, and contains a link to the next
+// one in the list to be searched.
+
+class equiv_chain
+{
+public:
+  bitmap m_names;		// ssa-names in equiv set.
+  basic_block m_bb;		// Block this belongs to
+  equiv_chain *m_next;		// Next in block list.
+  void dump (FILE *f) const;	// Show names in this list.
+  equiv_chain *find (unsigned ssa);
+};
 
 // The equivalency oracle maintains equivalencies using the dominator tree.
 // Equivalencies apply to an entire basic block.  Equivalencies on edges
@@ -188,4 +198,41 @@ private:
 
 };
 
+// A path_oracle implements relations in a list.  The only sense of ordering
+// is the latest registered relation is the first found during a search.
+// It can be constructed with an optional "root" oracle which will be used
+// to look up any relations not found in the list.
+// This allows the client to walk paths starting at some block and register
+// and query relations along that path, ignoring other edges.
+//
+// For registering a relation, a query if made of the root oracle if there is
+// any known relationship at block BB, and it is combined with this new
+// relation and entered in the list.
+//
+// Queries are resolved by looking first in the list, and only if nothing is
+// found is the root oracle queried at block BB.
+//
+// reset_path is used to clear all locally registered paths to initial state.
+
+class path_oracle : public relation_oracle
+{
+public:
+  path_oracle (relation_oracle *oracle = NULL);
+  ~path_oracle ();
+  const_bitmap equiv_set (tree, basic_block);
+  void register_relation (basic_block, relation_kind, tree, tree);
+  relation_kind query_relation (basic_block, tree, tree);
+  relation_kind query_relation (basic_block, const_bitmap, const_bitmap);
+  void reset_path ();
+  void dump (FILE *, basic_block) const;
+  void dump (FILE *) const;
+private:
+  void register_equiv (basic_block bb, tree ssa1, tree ssa2);
+  equiv_chain m_equiv;
+  relation_chain_head m_relations;
+  relation_oracle *m_root;
+
+  bitmap_obstack m_bitmaps;
+  struct obstack m_chain_obstack;
+};
 #endif  /* GCC_VALUE_RELATION_H */