[COMMITTED 1/4] Add partial equivalence support to the relation oracle.

[COMMITTED 1/4] Add partial equivalence support to the relation oracle.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 181 bytes --]

This patch provide the new relation kinds as well as management of the 
partial equivalency slice table.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed

Andrew


[-- Attachment #2: 0001-Add-partial-equivalence-support-to-the-relation-orac.patch --]
[-- Type: text/x-patch, Size: 13486 bytes --]

From b5563410ea613ff2b2d7c6fa1847cfcb1ff91efb Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 6 Oct 2022 15:00:52 -0400
Subject: [PATCH 1/4] Add partial equivalence support to the relation oracle.

This provides enhancements to the equivalence oracle to also track
partial equivalences.  They are tracked similar to equivalences, except
it tracks a 'slice' of another ssa name.   8, 16, 32 and 64 bit slices are
tracked.  This will allow casts and mask of the same value to compare
equal.

	* value-relation.cc (equiv_chain::dump): Don't print empty
	equivalences.
	(equiv_oracle::equiv_oracle): Allocate a partial equiv table.
	(equiv_oracle::~equiv_oracle): Release the partial equiv table.
	(equiv_oracle::add_partial_equiv): New.
	(equiv_oracle::partial_equiv_set): New.
	(equiv_oracle::partial_equiv): New.
	(equiv_oracle::query_relation): Check for partial equivs too.
	(equiv_oracle::dump): Also dump partial equivs.
	(dom_oracle::register_relation): Handle partial equivs.
	(dom_oracle::query_relation): Check for partial equivs.
	* value-relation.h (enum relation_kind_t): Add partial equivs.
	(relation_partial_equiv_p): New.
	(relation_equiv_p): New.
	(class pe_slice): New.
	(class equiv_oracle): Add prototypes.
	(pe_to_bits): New.
	(bits_to_pe): New.
	(pe_min): New.
---
 gcc/value-relation.cc | 165 +++++++++++++++++++++++++++++++++++++++---
 gcc/value-relation.h  |  78 +++++++++++++++++++-
 2 files changed, 229 insertions(+), 14 deletions(-)

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index 1ee6da199f2..ceeca53e0a1 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -32,10 +32,11 @@ along with GCC; see the file COPYING3.  If not see
 #include "alloc-pool.h"
 #include "dominance.h"
 
-#define VREL_LAST               VREL_NE
+#define VREL_LAST               VREL_PE64
 
 static const char *kind_string[VREL_LAST + 1] =
-{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=" };
+{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
+  "pe32", "pe64" };
 
 // Print a relation_kind REL to file F.
 
@@ -302,7 +303,7 @@ equiv_chain::dump (FILE *f) const
   bitmap_iterator bi;
   unsigned i;
 
-  if (!m_names)
+  if (!m_names || bitmap_empty_p (m_names))
     return;
   fprintf (f, "Equivalence set : [");
   unsigned c = 0;
@@ -329,18 +330,124 @@ equiv_oracle::equiv_oracle ()
   obstack_init (&m_chain_obstack);
   m_self_equiv.create (0);
   m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
+  m_partial.create (0);
+  m_partial.safe_grow_cleared (num_ssa_names + 1);
 }
 
 // Destruct an equivalency oracle.
 
 equiv_oracle::~equiv_oracle ()
 {
+  m_partial.release ();
   m_self_equiv.release ();
   obstack_free (&m_chain_obstack, NULL);
   m_equiv.release ();
   bitmap_obstack_release (&m_bitmaps);
 }
 
+// Add a partial equivalence R between OP1 and OP2.
+
+void
+equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
+{
+  int v1 = SSA_NAME_VERSION (op1);
+  int v2 = SSA_NAME_VERSION (op2);
+  int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
+  int bits = pe_to_bits (r);
+  gcc_checking_assert (bits && prec2 >= bits);
+
+  if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
+    m_partial.safe_grow_cleared (num_ssa_names + 1);
+  gcc_checking_assert (v1 < (int)m_partial.length ()
+		       && v2 < (int)m_partial.length ());
+
+  pe_slice &pe1 = m_partial[v1];
+  pe_slice &pe2 = m_partial[v2];
+
+  if (pe1.members)
+    {
+      // If the definition pe1 already has an entry, either the stmt is
+      // being re-evaluated, or the def was used before being registered.
+      // In either case, if PE2 has an entry, we simply do nothing.
+      if (pe2.members)
+	return;
+      // PE1 is the LHS and already has members, so everything in the set
+      // should be a slice of PE2 rather than PE1.
+      pe2.code = pe_min (r, pe1.code);
+      pe2.ssa_base = op2;
+      pe2.members = pe1.members;
+      bitmap_iterator bi;
+      unsigned x;
+      EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
+	{
+	  m_partial[x].ssa_base = op2;
+	  m_partial[x].code = pe2.code;
+	}
+      bitmap_set_bit (pe1.members, v2);
+      return;
+    }
+  if (pe2.members)
+    {
+      pe1.ssa_base = pe2.ssa_base;
+      // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
+      // more than an 8 bit equivalence here, so choose MIN value.
+      pe1.code = pe_min (r, pe2.code);
+      pe1.members = pe2.members;
+      bitmap_set_bit (pe1.members, v1);
+    }
+  else
+    {
+      // Neither name has an entry, simply create op1 as slice of op2.
+      pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
+      if (pe2.code == VREL_VARYING)
+	return;
+      pe2.ssa_base = op2;
+      pe2.members = BITMAP_ALLOC (&m_bitmaps);
+      bitmap_set_bit (pe2.members, v2);
+      pe1.ssa_base = op2;
+      pe1.code = r;
+      pe1.members = pe2.members;
+      bitmap_set_bit (pe1.members, v1);
+    }
+}
+
+// Return the set of partial equivalences associated with NAME.  The bitmap
+// will be NULL if there are none.
+
+const pe_slice *
+equiv_oracle::partial_equiv_set (tree name)
+{
+  int v = SSA_NAME_VERSION (name);
+  if (v >= (int)m_partial.length ())
+    return NULL;
+  return &m_partial[v];
+}
+
+// Query if there is a partial equivalence between SSA1 and SSA2.  Return
+// VREL_VARYING if there is not one.  If BASE is non-null, return the base
+// ssa-name this is a slice of.
+
+relation_kind
+equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
+{
+  int v1 = SSA_NAME_VERSION (ssa1);
+  int v2 = SSA_NAME_VERSION (ssa2);
+
+  if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
+    return VREL_VARYING;
+
+  const pe_slice &pe1 = m_partial[v1];
+  const pe_slice &pe2 = m_partial[v2];
+  if (pe1.members && pe2.members == pe1.members)
+    {
+      if (base)
+	*base = pe1.ssa_base;
+      return pe_min (pe1.code, pe2.code);
+    }
+  return VREL_VARYING;
+}
+
+
 // Find and return the equivalency set for SSA along the dominators of BB.
 // This is the external API.
 
@@ -365,7 +472,7 @@ equiv_oracle::equiv_set (tree ssa, basic_block bb)
   return m_self_equiv[v];
 }
 
-// Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
+// Query if there is a relation (equivalence) between 2 SSA_NAMEs.
 
 relation_kind
 equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
@@ -373,7 +480,9 @@ equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
   // If the 2 ssa names share the same equiv set, they are equal.
   if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
     return VREL_EQ;
-  return VREL_VARYING;
+
+  // Check if there is a partial equivalence.
+  return partial_equiv (ssa1, ssa2);
 }
 
 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
@@ -515,6 +624,12 @@ void
 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
 				 tree ssa2)
 {
+  // Process partial equivalencies.
+  if (relation_partial_equiv_p (k))
+    {
+      add_partial_equiv (k, ssa1, ssa2);
+      return;
+    }
   // Only handle equality relations.
   if (k != VREL_EQ)
     return;
@@ -611,12 +726,34 @@ equiv_oracle::dump (FILE *f, basic_block bb) const
 {
   if (bb->index >= (int)m_equiv.length ())
     return;
-  if (!m_equiv[bb->index])
-    return;
-
-  equiv_chain *ptr = m_equiv[bb->index]->m_next;
-  for (; ptr; ptr = ptr->m_next)
-    ptr->dump (f);
+  // Process equivalences.
+  if (m_equiv[bb->index])
+    {
+      equiv_chain *ptr = m_equiv[bb->index]->m_next;
+      for (; ptr; ptr = ptr->m_next)
+	ptr->dump (f);
+    }
+  // Look for partial equivalences defined in this block..
+  for (unsigned i = 0; i < num_ssa_names; i++)
+    {
+      tree name = ssa_name (i);
+      if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
+	continue;
+      if (i >= m_partial.length ())
+	break;
+     tree base = m_partial[i].ssa_base;
+      if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
+	{
+	  relation_kind k = partial_equiv (name, base);
+	  if (k != VREL_VARYING)
+	    {
+	      value_relation vr (k, name, base);
+	      fprintf (f, "Partial equiv ");
+	      vr.dump (f);
+	      fputc ('\n',f);
+	    }
+	}
+    }
 }
 
 // Dump all equivalence sets known to the oracle.
@@ -906,7 +1043,7 @@ dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
     return;
 
   // Equivalencies are handled by the equivalence oracle.
-  if (k == VREL_EQ)
+  if (relation_equiv_p (k))
     equiv_oracle::register_relation (bb, k, op1, op2);
   else
     {
@@ -1210,6 +1347,10 @@ dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
   if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
     return VREL_EQ;
 
+  kind = partial_equiv (ssa1, ssa2);
+  if (kind != VREL_VARYING)
+    return kind;
+
   // Initially look for a direct relationship and just return that.
   kind = find_relation_dom (bb, v1, v2);
   if (kind != VREL_VARYING)
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index e1347ea8ad8..f5f2524ad56 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -70,7 +70,11 @@ typedef enum relation_kind_t
   VREL_GT,		// r1 > r2
   VREL_GE,		// r1 >= r2
   VREL_EQ,		// r1 == r2
-  VREL_NE		// r1 != r2
+  VREL_NE,		// r1 != r2
+  VREL_PE8,		// 8 bit partial equivalency
+  VREL_PE16,		// 16 bit partial equivalency
+  VREL_PE32,		// 32 bit partial equivalency
+  VREL_PE64		// 64 bit partial equivalency
 } relation_kind;
 
 // General relation kind transformations.
@@ -79,7 +83,12 @@ relation_kind relation_intersect (relation_kind r1, relation_kind r2);
 relation_kind relation_negate (relation_kind r);
 relation_kind relation_swap (relation_kind r);
 inline bool relation_lt_le_gt_ge_p (relation_kind r)
-				    { return (r >= VREL_LT && r <= VREL_GE); }
+		      { return (r >= VREL_LT && r <= VREL_GE); }
+inline bool relation_partial_equiv_p (relation_kind r)
+		      { return (r >= VREL_PE8 && r <= VREL_PE64); }
+inline bool relation_equiv_p (relation_kind r)
+		      { return r == VREL_EQ || relation_partial_equiv_p (r); }
+
 void print_relation (FILE *f, relation_kind rel);
 
 class relation_oracle
@@ -93,6 +102,7 @@ public:
 
   // Return equivalency set for an SSA name in a basic block.
   virtual const_bitmap equiv_set (tree, basic_block) = 0;
+  virtual const class pe_slice *partial_equiv_set (tree) { return NULL; }
   // register a relation between 2 ssa names in a basic block.
   virtual void register_relation (basic_block, relation_kind, tree, tree) = 0;
   // Query for a relation between two ssa names in a basic block.
@@ -125,6 +135,14 @@ public:
   equiv_chain *find (unsigned ssa);
 };
 
+class pe_slice
+{
+public:
+  tree ssa_base;  	// Slice of this name.
+  relation_kind code;	// bits that are equivalent.
+  bitmap members;	// Other members in the partial equivalency.
+};
+
 // The equivalency oracle maintains equivalencies using the dominator tree.
 // Equivalencies apply to an entire basic block.  Equivalencies on edges
 // can be represented only on edges whose destination is a single-pred block,
@@ -137,9 +155,12 @@ public:
   ~equiv_oracle ();
 
   const_bitmap equiv_set (tree ssa, basic_block bb) final override;
+  const pe_slice *partial_equiv_set (tree name) final override;
   void register_relation (basic_block bb, relation_kind k, tree ssa1,
 			  tree ssa2) override;
 
+  void add_partial_equiv (relation_kind, tree, tree);
+  relation_kind partial_equiv (tree ssa1, tree ssa2, tree *base = NULL) const;
   relation_kind query_relation (basic_block, tree, tree) override;
   relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
     override;
@@ -153,6 +174,7 @@ private:
   bitmap m_equiv_set;	// Index by ssa-name. true if an equivalence exists.
   vec <equiv_chain *> m_equiv;	// Index by BB.  list of equivalences.
   vec <bitmap> m_self_equiv;  // Index by ssa-name, self equivalency set.
+  vec <pe_slice> m_partial;  // Partial equivalencies.
 
   void limit_check (basic_block bb = NULL);
   equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
@@ -315,4 +337,56 @@ value_relation::value_relation (relation_kind kind, tree n1, tree n2)
   set_relation (kind, n1, n2);
 }
 
+// Return the number of bits associated with partial equivalency T.
+// Return 0 if this is not a supported partial equivalency relation.
+
+inline int
+pe_to_bits (relation_kind t)
+{
+  switch (t)
+  {
+    case VREL_PE8:
+      return 8;
+    case VREL_PE16:
+      return 16;
+    case VREL_PE32:
+      return 32;
+    case VREL_PE64:
+      return 64;
+    default:
+      return 0;
+  }
+}
+
+// Return the partial equivalency code associated with the number of BITS.
+// return VREL_VARYING if there is no exact match.
+
+inline relation_kind
+bits_to_pe (int bits)
+{
+  switch (bits)
+  {
+    case 8:
+      return VREL_PE8;
+    case 16:
+      return VREL_PE16;
+    case 32:
+      return VREL_PE32;
+    case 64:
+      return VREL_PE64;
+    default:
+      return VREL_VARYING;
+  }
+}
+
+// Given partial equivalencies T1 and T2, return the snmallest kind.
+
+inline relation_kind
+pe_min (relation_kind t1, relation_kind t2)
+{
+  gcc_checking_assert (relation_partial_equiv_p (t1));
+  gcc_checking_assert (relation_partial_equiv_p (t2));
+  // VREL_PE are declared small to large, so simple min will suffice.
+  return MIN (t1, t2);
+}
 #endif  /* GCC_VALUE_RELATION_H */
-- 
2.37.3