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(-)
@@ -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");
+ }
+}
@@ -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