[gcc r13-3279] Add equivalence iterator to relation oracle.

[Andrew Macleod <amacleod@gcc.gnu.org>]

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

commit r13-3279-gaa05838b0536422256e0c477c57f1ea1d2915e92
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Oct 7 12:55:32 2022 -0400

    Add equivalence iterator to relation oracle.
    
    Instead of looping over an exposed equivalence bitmap, provide iterators
    to loop over equivalences, partial equivalences, or both.
    
            * gimple-range-cache.cc (ranger_cache::fill_block_cache): Use
            iterator.
            * value-relation.cc
              (equiv_relation_iterator::equiv_relation_iterator): New.
            (equiv_relation_iterator::next): New.
            (equiv_relation_iterator::get_name): New.
            * value-relation.h (class relation_oracle): Privatize some methods.
            (class equiv_relation_iterator): New.
            (FOR_EACH_EQUIVALENCE): New.
            (FOR_EACH_PARTIAL_EQUIV): New.
            (FOR_EACH_PARTIAL_AND_FULL_EQUIV): New.

Diff:
---
 gcc/gimple-range-cache.cc | 10 ++----
 gcc/value-relation.cc     | 78 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/value-relation.h      | 41 +++++++++++++++++++++++--
 3 files changed, 118 insertions(+), 11 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 4782d47265e..8c80ba6cd14 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1220,15 +1220,9 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
       // See if any equivalences can refine it.
       if (m_oracle)
 	{
-	  unsigned i;
-	  bitmap_iterator bi;
-	  // Query equivalences in read-only mode.
-	  const_bitmap equiv = m_oracle->equiv_set (name, bb);
-	  EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi)
+	  tree equiv_name;
+	  FOR_EACH_EQUIVALENCE (m_oracle, bb, name, equiv_name)
 	    {
-	      if (i == SSA_NAME_VERSION (name))
-		continue;
-	      tree equiv_name = ssa_name (i);
 	      basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
 
 	      // Check if the equiv has any ranges calculated.
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index ceeca53e0a1..50fc190a36b 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1641,3 +1641,81 @@ path_oracle::dump (FILE *f) const
       fprintf (f, "\n");
     }
 }
+
+// ------------------------------------------------------------------------
+//  EQUIV iterator.  Although we have bitmap iterators, don't expose that it
+//  is currently a bitmap.  Use an export iterator to hide future changes.
+
+// Construct a basic iterator over an equivalence bitmap.
+
+equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
+						  basic_block bb, tree name,
+						  bool full, bool partial)
+{
+  m_name = name;
+  m_oracle = oracle;
+  m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
+  m_bm = NULL;
+  if (full)
+    m_bm = oracle->equiv_set (name, bb);
+  if (!m_bm && m_pe)
+    m_bm = m_pe->members;
+  if (m_bm)
+    bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
+}
+
+// Move to the next export bitmap spot.
+
+void
+equiv_relation_iterator::next ()
+{
+  bmp_iter_next (&m_bi, &m_y);
+}
+
+// Fetch the name of the next export in the export list.  Return NULL if
+// iteration is done.
+
+tree
+equiv_relation_iterator::get_name (relation_kind *rel)
+{
+  if (!m_bm)
+    return NULL_TREE;
+
+  while (bmp_iter_set (&m_bi, &m_y))
+    {
+      // Do not return self.
+      tree t = ssa_name (m_y);
+      if (t && t != m_name)
+	{
+	  relation_kind k = VREL_EQ;
+	  if (m_pe && m_bm == m_pe->members)
+	    {
+	      const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
+	      if (equiv_pe && equiv_pe->members == m_pe->members)
+		k = pe_min (m_pe->code, equiv_pe->code);
+	      else
+		k = VREL_VARYING;
+	    }
+	  if (relation_equiv_p (k))
+	    {
+	      if (rel)
+		*rel = k;
+	      return t;
+	    }
+	}
+      next ();
+    }
+
+  // Process partial equivs after full equivs if both were requested.
+  if (m_pe && m_bm != m_pe->members)
+    {
+      m_bm = m_pe->members;
+      if (m_bm)
+	{
+	  // Recursively call back to process First PE.
+	  bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
+	  return get_name (rel);
+	}
+    }
+  return NULL_TREE;
+}
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index f5f2524ad56..a3bbe1e8157 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -100,9 +100,6 @@ public:
   // register a relation between 2 ssa names on an edge.
   void register_edge (edge, relation_kind, tree, tree);
 
-  // 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.
@@ -115,6 +112,11 @@ public:
   virtual void dump (FILE *) const = 0;
   void debug () const;
 protected:
+  friend class equiv_relation_iterator;
+  // Return equivalency set for an SSA name in a basic block.
+  virtual const_bitmap equiv_set (tree, basic_block) = 0;
+  // Return partial equivalency record for an SSA name.
+  virtual const class pe_slice *partial_equiv_set (tree) { return NULL; }
   void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
   // Query for a relation between two equivalency sets in a basic block.
   virtual relation_kind query_relation (basic_block, const_bitmap,
@@ -281,6 +283,39 @@ private:
   struct obstack m_chain_obstack;
 };
 
+// Used to assist with iterating over the equivalence list.
+class equiv_relation_iterator {
+public:
+  equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name,
+			   bool full = true, bool partial = false);
+  void next ();
+  tree get_name (relation_kind *rel = NULL);
+protected:
+  relation_oracle *m_oracle;
+  const_bitmap m_bm;
+  const pe_slice *m_pe;
+  bitmap_iterator m_bi;
+  unsigned m_y;
+  tree m_name;
+};
+
+#define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name)		\
+  for (equiv_relation_iterator iter (oracle, bb, name, true, false);	\
+       ((equiv_name) = iter.get_name ());				\
+       iter.next ())
+
+#define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel)	\
+  for (equiv_relation_iterator iter (oracle, bb, name, false, true);	\
+       ((equiv_name) = iter.get_name (&equiv_rel));			\
+       iter.next ())
+
+#define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, 	\
+						      equiv_rel)	\
+  for (equiv_relation_iterator iter (oracle, bb, name, true, true);	\
+       ((equiv_name) = iter.get_name (&equiv_rel));			\
+       iter.next ())
+
+
 // The value-relation class is used to encapsulate the represention of an
 // individual relation between 2 ssa-names, and to facilitate operating on
 // the relation.