diff mbox series

[COMMITTED] Provide a relation oracle for paths.

Message ID 7b28ef8a-f13a-40c3-a15a-224ab5f6dd5f@redhat.com
State New
Headers show
Series [COMMITTED] Provide a relation oracle for paths. | expand

Commit Message

Andrew MacLeod Sept. 17, 2021, 6:20 p.m. UTC
This patch provides a path-oracle which complies with the 
relation_oracle base class and is used to track any relations that are 
found along a specific path.

There are upcoming threader changes which utilize this oracle.

As paths are walked, gimple_range_fold can be used to automatically 
register any relations that are discovered on this path and allowing the 
normal kind of relational folding to happen.  This also allows 
equivalencies to be entered between PHI defs and the use on the PHI edge 
that the path traverses.

Furthermore, it can be used in conjunction with a normal ranger 
dominance based relation oracle which can be used to automatically 
utilize any relations/equivalences that are active at the start of the 
path an integrate seemlessly with the path relation list.

Bootstrapped on x86_64-pc-linux-gnu with no regressions, pushed. Client 
threader code coming shortly.

Andrew
diff mbox series

Patch

From 534c5352a02485a41ebfb133b42edbbecba7eba3 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Fri, 17 Sep 2021 09:48:35 -0400
Subject: [PATCH 2/2] 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.
---
 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 */
-- 
2.17.2