[gcc r12-1719] Initial value-relation code.

[gcc r12-1719] Initial value-relation code.

[Andrew Macleod]

https://gcc.gnu.org/g:3aaa69e5f30e1904d7ca2bb711b1cb0c62b6895f

commit r12-1719-g3aaa69e5f30e1904d7ca2bb711b1cb0c62b6895f
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Jun 17 10:19:31 2021 -0400

    Initial value-relation code.
    
    This code provides a both an equivalence and relation oracle which can be
    accessed via a range_query object.  This initial code drop includes the
    oracles and access them, but does not utilize them yet.
    
            * Makefile.in (OBJS): Add value-relation.o.
            * gimple-range.h: Adjust include files.
            * tree-data-ref.c: Adjust include file order.
            * value-query.cc (range_query::get_value_range): Default to no oracle.
            (range_query::query_relation): New.
            (range_query::query_relation): New.
            * value-query.h (class range_query): Adjust.
            * value-relation.cc: New.
            * value-relation.h: New.

Diff:
---
 gcc/Makefile.in       |   1 +
 gcc/gimple-range.h    |   2 +-
 gcc/tree-data-ref.c   |   2 +-
 gcc/value-query.cc    |  50 +++
 gcc/value-query.h     |  11 +
 gcc/value-relation.cc | 932 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/value-relation.h  | 159 +++++++++
 7 files changed, 1155 insertions(+), 2 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 4cb2966157e..ebf26442992 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1688,6 +1688,7 @@ OBJS = \
 	value-query.o \
 	value-range.o \
 	value-range-equiv.o \
+	value-relation.o \
 	value-prof.o \
 	var-tracking.o \
 	varasm.o \
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index fc28123f9ec..b9cffdb8ee0 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -24,8 +24,8 @@ along with GCC; see the file COPYING3.  If not see
 
 
 #include "range.h"
-#include "range-op.h"
 #include "value-query.h"
+#include "range-op.h"
 #include "gimple-range-edge.h"
 #include "gimple-range-gori.h"
 #include "gimple-range-cache.h"
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 6f3352ffb1f..b6abd8b8de7 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -97,8 +97,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-eh.h"
 #include "ssa.h"
 #include "internal-fn.h"
-#include "range-op.h"
 #include "vr-values.h"
+#include "range-op.h"
 
 static struct datadep_stats
 {
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 93609f3c7c4..17dfdb1ccbe 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -174,6 +174,7 @@ range_query::get_value_range (const_tree expr, gimple *stmt)
 range_query::range_query ()
 {
   equiv_alloc = new equiv_allocator;
+  m_oracle = NULL;
 }
 
 range_query::~range_query ()
@@ -452,3 +453,52 @@ global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
 
   return true;
 }
+
+// Return any known relation between SSA1 and SSA2 before stmt S is executed.
+// If GET_RANGE is true, query the range of both operands first to ensure
+// the defintions have been processed and any relations have be created.
+
+relation_kind
+range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
+{
+  int_range_max tmp;
+  if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
+    return VREL_NONE;
+
+  // Ensure ssa1 and ssa2 have both been evaluated.
+  if (get_range)
+    {
+      range_of_expr (tmp, ssa1, s);
+      range_of_expr (tmp, ssa2, s);
+    }
+  return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
+}
+
+// Return any known relation between SSA1 and SSA2 on edge E.
+// If GET_RANGE is true, query the range of both operands first to ensure
+// the defintions have been processed and any relations have be created.
+
+relation_kind
+range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
+{
+  basic_block bb;
+  int_range_max tmp;
+  if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
+    return VREL_NONE;
+
+  // Use destination block if it has a single predecessor, and this picks
+  // up any relation on the edge.
+  // Otherwise choose the src edge and the result is the same as on-exit.
+  if (!single_pred_p (e->dest))
+    bb = e->src;
+  else
+    bb = e->dest;
+
+  // Ensure ssa1 and ssa2 have both been evaluated.
+  if (get_range)
+    {
+      range_on_edge (tmp, e, ssa1);
+      range_on_edge (tmp, e, ssa2);
+    }
+  return m_oracle->query_relation (bb, ssa1, ssa2);
+}
diff --git a/gcc/value-query.h b/gcc/value-query.h
index 54af031ea42..5161d23714b 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -22,6 +22,8 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_QUERY_H
 #define GCC_QUERY_H
 
+#include "value-relation.h"
+
 // The value_query class is used by optimization passes that require
 // valueizing SSA names in terms of a tree value, but have no neeed
 // for ranges.
@@ -91,6 +93,14 @@ public:
   virtual bool range_on_edge (irange &r, edge, tree expr);
   virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL);
 
+  // Query if there is any relation between SSA1 and SSA2.
+  relation_kind query_relation (gimple *s, tree ssa1, tree ssa2,
+				bool get_range = true);
+  relation_kind query_relation (edge e, tree ssa1, tree ssa2,
+				bool get_range = true);
+  // If present, Access relation oracle for more advanced uses.
+  inline relation_oracle *oracle () const  { return m_oracle; }
+
   // DEPRECATED: This method is used from vr-values.  The plan is to
   // rewrite all uses of it to the above API.
   virtual const class value_range_equiv *get_value_range (const_tree,
@@ -102,6 +112,7 @@ protected:
   void free_value_range_equiv (class value_range_equiv *);
   bool get_tree_range (irange &r, tree expr, gimple *stmt);
   bool get_arith_expr_range (irange &r, tree expr, gimple *stmt);
+  relation_oracle *m_oracle;
 
 private:
   class equiv_allocator *equiv_alloc;
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
new file mode 100644
index 00000000000..3c8698f2a54
--- /dev/null
+++ b/gcc/value-relation.cc
@@ -0,0 +1,932 @@
+/* Header file for the value range relational processing.
+   Copyright (C) 2020-2021 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+
+#include "gimple-range.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
+#include "alloc-pool.h"
+#include "dominance.h"
+
+// These VREL codes are arranged such that VREL_NONE is the first
+// code, and all the rest are contiguous up to and including VREL_LAST.
+
+#define VREL_FIRST              VREL_NONE
+#define VREL_LAST               NE_EXPR
+#define VREL_COUNT              (VREL_LAST - VREL_FIRST + 1)
+
+// vrel_range_assert will either assert that the tree code passed is valid,
+// or mark invalid codes as unreachable to help with table optimation.
+#if CHECKING_P
+  #define vrel_range_assert(c) 			\
+    gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST)
+#else
+  #define vrel_range_assert(c)			\
+    if ((c) < VREL_FIRST || (c) > VREL_LAST)	\
+      gcc_unreachable ();
+#endif
+
+static const char *kind_string[VREL_COUNT] =
+{ "none", "<", "<=", ">", ">=", "empty", "==", "!=" };
+
+// Print a relation_kind REL to file F.
+
+void
+print_relation (FILE *f, relation_kind rel)
+{
+  vrel_range_assert (rel);
+  fprintf (f, " %s ", kind_string[rel - VREL_FIRST]);
+}
+
+// This table is used to negate the operands.  op1 REL op2 -> !(op1 REL op2).
+relation_kind rr_negate_table[VREL_COUNT] = {
+//     NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY,      EQ_EXPR, NE_EXPR
+  VREL_NONE, GE_EXPR, GT_EXPR, LE_EXPR, LT_EXPR, VREL_EMPTY, NE_EXPR, EQ_EXPR };
+
+// Negate the relation, as in logical negation.
+
+relation_kind
+relation_negate (relation_kind r)
+{
+  vrel_range_assert (r);
+  return rr_negate_table [r - VREL_FIRST];
+}
+
+// This table is used to swap the operands.  op1 REL op2 -> op2 REL op1.
+relation_kind rr_swap_table[VREL_COUNT] = {
+//     NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY,      EQ_EXPR, NE_EXPR
+  VREL_NONE, GT_EXPR, GE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR };
+
+// Return the relation as if the operands were swapped.
+
+relation_kind
+relation_swap (relation_kind r)
+{
+  vrel_range_assert (r);
+  return rr_swap_table [r - VREL_FIRST];
+}
+
+// This table is used to perform an intersection between 2 relations.
+
+relation_kind rr_intersect_table[VREL_COUNT][VREL_COUNT] = {
+//   NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
+// VREL_NONE
+  { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
+// LT_EXPR
+  { LT_EXPR, LT_EXPR, LT_EXPR, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, LT_EXPR },
+// LE_EXPR
+  { LE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, LT_EXPR },
+// GT_EXPR
+  { GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR },
+// GE_EXPR
+  { GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR },
+// VREL_EMPTY
+  { VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY },
+// EQ_EXPR
+  { EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY },
+// NE_EXPR
+  { NE_EXPR, LT_EXPR, LT_EXPR, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, NE_EXPR } };
+
+
+// Intersect relation R! with relation R2 and return the resulting relation.
+
+relation_kind
+relation_intersect (relation_kind r1, relation_kind r2)
+{
+  vrel_range_assert (r1);
+  vrel_range_assert (r2);
+  return rr_intersect_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
+}
+
+
+// This table is used to perform a union between 2 relations.
+
+relation_kind rr_union_table[VREL_COUNT][VREL_COUNT] = {
+//    	 NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
+// VREL_NONE
+  { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
+// LT_EXPR
+  { VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR, VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR },
+// LE_EXPR
+  { VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE },
+// GT_EXPR
+  { VREL_NONE, NE_EXPR, VREL_NONE, GT_EXPR, GE_EXPR, GT_EXPR, GE_EXPR, NE_EXPR },
+// GE_EXPR
+  { VREL_NONE, VREL_NONE, VREL_NONE, GE_EXPR, GE_EXPR, GE_EXPR, GE_EXPR, VREL_NONE },
+// VREL_EMPTY
+  { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
+// EQ_EXPR
+  { VREL_NONE, LE_EXPR, LE_EXPR, GE_EXPR, GE_EXPR, EQ_EXPR, EQ_EXPR, VREL_NONE },
+// NE_EXPR
+  { VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR } };
+
+// Union relation R1 with relation R2 and return the result.
+
+relation_kind
+relation_union (relation_kind r1, relation_kind r2)
+{
+  vrel_range_assert (r1);
+  vrel_range_assert (r2);
+  return rr_union_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
+}
+
+
+// -------------------------------------------------------------------------
+
+// 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.
+// This allows for much faster traversal of the DOM chain, as a search for
+// SSA_NAME simply requires walking the DOM chain until a block is found
+// which has the bit for SSA_NAME set. Then scan for the equivalency set in
+// that block.   No previous blcoks 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.
+};
+
+
+// Dump the names in this equivalence set.
+
+void
+equiv_chain::dump (FILE *f) const
+{
+  bitmap_iterator bi;
+  unsigned i;
+
+  if (!m_names)
+    return;
+  fprintf (f, "Equivalence set : [");
+  unsigned c = 0;
+  EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
+    {
+      if (ssa_name (i))
+	{
+	  if (c++)
+	    fprintf (f, ", ");
+	  print_generic_expr (f, ssa_name (i), TDF_SLIM);
+	}
+    }
+  fprintf (f, "]\n");
+}
+
+// Instantiate an equivalency oracle.
+
+equiv_oracle::equiv_oracle ()
+{
+  bitmap_obstack_initialize (&m_bitmaps);
+  m_equiv.create (0);
+  m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
+  m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
+  obstack_init (&m_chain_obstack);
+}
+
+// Destruct an equivalency oracle.
+
+equiv_oracle::~equiv_oracle ()
+{
+  obstack_free (&m_chain_obstack, NULL);
+  m_equiv.release ();
+  bitmap_obstack_release (&m_bitmaps);
+}
+
+// Find and return the equivalency set for SSA along the dominators of BB.
+// This is the external API.
+
+const_bitmap
+equiv_oracle::equiv_set (tree ssa, basic_block bb) const
+{
+  // Search the dominator tree for an equivalency.
+  equiv_chain *equiv = find_equiv_dom (ssa, bb);
+  if (equiv)
+    return equiv->m_names;
+
+  return NULL;
+}
+
+
+// If SSA has an equivalence in block BB, find and return it.
+// Otherwise return NULL.
+
+equiv_chain *
+equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
+{
+  equiv_chain *ptr = NULL;
+  if (bb >= (int)m_equiv.length ())
+    return NULL;
+
+  // If there are equiv sets and SSA is in one in this block, find it.
+  // Otherwise return NULL.
+  if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa))
+    {
+      for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next)
+	if (bitmap_bit_p (ptr->m_names, ssa))
+	  break;
+    }
+  return ptr;
+}
+
+// Starting at block BB, walk the dominator chain looking for the nearest
+// equivalence set containing NAME.
+
+equiv_chain *
+equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  // Short circuit looking for names which have no equivalences.
+  // Saves time looking for something which does not exist.
+  if (!bitmap_bit_p (m_equiv_set, v))
+    return NULL;
+
+  // NAME has at least once equivalence set, check to see if it has one along
+  // the dominator tree.
+  for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      equiv_chain *ptr = find_equiv_block (v, bb->index);
+      if (ptr)
+	return ptr;
+    }
+  return NULL;
+}
+
+// Register equivalance between ssa_name V and set EQUIV in block BB,
+
+bitmap
+equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
+{
+  // V will have an equivalency now.
+  bitmap_set_bit (m_equiv_set, v);
+
+  // If that equiv chain is in this block, simply use it.
+  if (equiv->m_bb == bb)
+    {
+      bitmap_set_bit (equiv->m_names, v);
+      bitmap_set_bit (m_equiv[bb->index]->m_names, v);
+      return NULL;
+    }
+
+  // Otherwise create an equivalence for this block which is a copy
+  // of equiv, the add V to the set.
+  bitmap b = BITMAP_ALLOC (&m_bitmaps);
+  bitmap_copy (b, equiv->m_names);
+  bitmap_set_bit (b, v);
+  return b;
+}
+
+// Register equivalence between set equiv_1 and equiv_2 in block BB.
+// Return NULL if either name can be merged with the other.  Otherwise
+// return a pointer to the combined bitmap of names.  This allows the
+// caller to do any setup required for a new element.
+
+bitmap
+equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
+			      equiv_chain *equiv_2)
+{
+  // If equiv_1 is alreayd in BB, use it as the combined set.
+  if (equiv_1->m_bb == bb)
+    {
+      bitmap_ior_into  (equiv_1->m_names, equiv_2->m_names);
+      // Its hard to delete from a single linked list, so
+      // just clear the second one.
+      if (equiv_2->m_bb == bb)
+	bitmap_clear (equiv_2->m_names);
+      else
+	// Ensure equiv_2s names are in the summary for BB.
+	bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
+      return NULL;
+    }
+  // If equiv_2 is in BB, use it for the combined set.
+  if (equiv_2->m_bb == bb)
+    {
+      bitmap_ior_into (equiv_2->m_names, equiv_1->m_names);
+      // Add equiv_1 names into the summary.
+      bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
+      return NULL;
+    }
+
+  // At this point, neither equivalence is from this block.
+  bitmap b = BITMAP_ALLOC (&m_bitmaps);
+  bitmap_copy (b, equiv_1->m_names);
+  bitmap_ior_into (b, equiv_2->m_names);
+  return b;
+}
+
+
+// Register an equivalence between SSA1 and SSA2 in block BB.
+// The equivalence oracle maintains a vector of equivalencies indexed by basic
+// block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
+// a query is made as to what equivalences both names have already, and
+// any preexisting equivalences are merged to create a single equivalence
+// containing all the ssa_names in this basic block.
+
+void
+equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
+{
+  unsigned v1 = SSA_NAME_VERSION (ssa1);
+  unsigned v2 = SSA_NAME_VERSION (ssa2);
+  equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
+  equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
+
+  // Check if they are the same set
+  if (equiv_1 && equiv_1 == equiv_2)
+    return;
+
+  bitmap equiv_set;
+
+  // Case where we have 2 SSA_NAMEs that are not in any set.
+  if (!equiv_1 && !equiv_2)
+    {
+      bitmap_set_bit (m_equiv_set, v1);
+      bitmap_set_bit (m_equiv_set, v2);
+
+      equiv_set = BITMAP_ALLOC (&m_bitmaps);
+      bitmap_set_bit (equiv_set, v1);
+      bitmap_set_bit (equiv_set, v2);
+    }
+  else if (!equiv_1 && equiv_2)
+    equiv_set = register_equiv (bb, v1, equiv_2);
+  else if (equiv_1 && !equiv_2)
+    equiv_set = register_equiv (bb, v2, equiv_1);
+  else
+    equiv_set = register_equiv (bb, equiv_1, equiv_2);
+
+  // A non-null return is a bitmap that is to be added to the current
+  // block as a new equivalence.
+  if (!equiv_set)
+    return;
+
+  equiv_chain *ptr;
+
+  // Check if this is the first time a block has an equivalence added.
+  // and create a header block. And set the summary for this block.
+  if (!m_equiv[bb->index])
+    {
+      ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
+					   sizeof (equiv_chain));
+      ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
+      bitmap_copy (ptr->m_names, equiv_set);
+      ptr->m_bb = bb;
+      ptr->m_next = NULL;
+      m_equiv[bb->index] = ptr;
+    }
+
+  // Now create the element for this equiv set and initialize it.
+  ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
+  ptr->m_names = equiv_set;
+  ptr->m_bb = bb;
+  gcc_checking_assert (bb->index < (int)m_equiv.length ());
+  ptr->m_next = m_equiv[bb->index]->m_next;
+  m_equiv[bb->index]->m_next = ptr;
+  bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
+}
+
+// Make sure the BB vector is big enough and grow it if needed.
+
+void
+equiv_oracle::limit_check (basic_block bb)
+{
+  int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
+  if (i >= (int)m_equiv.length ())
+    m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
+}
+
+// Dump the equivalence sets in BB to file F.
+
+void
+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);
+}
+
+// Dump all equivalence sets known to the oracle.
+
+void
+equiv_oracle::dump (FILE *f) const
+{
+  fprintf (f, "Equivalency dump\n");
+  for (unsigned i = 0; i < m_equiv.length (); i++)
+    if (m_equiv[i])
+      {
+	fprintf (f, "BB%d\n", i);
+	dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
+      }
+}
+
+
+// --------------------------------------------------------------------------
+
+// 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.
+
+class value_relation
+{
+public:
+  value_relation ();
+  value_relation (relation_kind kind, tree n1, tree n2);
+  void set_relation (relation_kind kind, tree n1, tree n2);
+
+  inline relation_kind kind () const { return related; }
+  inline tree op1 () const { return name1; }
+  inline tree op2 () const { return name2; }
+
+  bool union_ (value_relation &p);
+  bool intersect (value_relation &p);
+  void negate ();
+  void swap ();
+
+  void dump (FILE *f) const;
+private:
+  relation_kind related;
+  tree name1, name2;
+};
+
+// Set relation R between ssa_name N1 and N2.
+
+inline void
+value_relation::set_relation (relation_kind r, tree n1, tree n2)
+{
+  gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
+  related = r;
+  name1 = n1;
+  name2 = n2;
+}
+
+// Default constructor.
+
+inline
+value_relation::value_relation ()
+{
+  related = VREL_NONE;
+  name1 = NULL_TREE;
+  name2 = NULL_TREE;
+}
+
+// Constructor for relation R between SSA version N1 nd N2.
+
+inline
+value_relation::value_relation (relation_kind kind, tree n1, tree n2)
+{
+  set_relation (kind, n1, n2);
+}
+
+// Negate the current relation.
+
+void
+value_relation::negate ()
+{
+  related = relation_negate (related);
+}
+
+// Modify the relation as if the operands were being swapped.
+
+void
+value_relation::swap ()
+{
+  related = relation_swap (related);
+}
+
+// Perform an intersection between 2 relations. *this &&= p.
+
+bool
+value_relation::intersect (value_relation &p)
+{
+  // Save previous value
+  relation_kind old = related;
+
+  if (p.op1 () == op1 () && p.op2 () == op2 ())
+    related = relation_intersect (kind (), p.kind ());
+  else if (p.op2 () == op1 () && p.op1 () == op2 ())
+    related = relation_intersect (kind (), relation_swap (p.kind ()));
+  else
+    return false;
+
+  return old != related;
+}
+
+// Perform a union between 2 relations. *this ||= p.
+
+bool
+value_relation::union_ (value_relation &p)
+{
+  // Save previous value
+  relation_kind old = related;
+
+  if (p.op1 () == op1 () && p.op2 () == op2 ())
+    related = relation_union (kind(), p.kind());
+  else if (p.op2 () == op1 () && p.op1 () == op2 ())
+    related = relation_union (kind(), relation_swap (p.kind ()));
+  else
+    return false;
+
+  return old != related;
+}
+
+
+// Dump the relation to file F.
+
+void
+value_relation::dump (FILE *f) const
+{
+  if (!name1 || !name2)
+    {
+      fprintf (f, "uninitialized");
+      return;
+    }
+  fputc ('(', f);
+  print_generic_expr (f, op1 (), TDF_SLIM);
+  print_relation (f, kind ());
+  print_generic_expr (f, op2 (), TDF_SLIM);
+  fputc(')', f);
+}
+
+// This container is used to link relations in a chain.
+
+class relation_chain : public value_relation
+{
+public:
+  relation_chain *m_next;
+};
+
+// ------------------------------------------------------------------------
+
+// Instantiate a relation oracle.
+
+relation_oracle::relation_oracle ()
+{
+  m_relations.create (0);
+  m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
+  m_relation_set = BITMAP_ALLOC (&m_bitmaps);
+  m_tmp = BITMAP_ALLOC (&m_bitmaps);
+}
+
+// Destruct a relation oracle.
+
+relation_oracle::~relation_oracle ()
+{
+  m_relations.release ();
+}
+
+// Register relation K between ssa_name OP1 and OP2 on STMT.
+
+void
+relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1,
+				    tree op2)
+{
+  gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
+  gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
+  gcc_checking_assert (stmt && gimple_bb (stmt));
+
+  // Don't register lack of a relation.
+  if (k == VREL_NONE)
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      value_relation vr (k, op1, op2);
+      fprintf (dump_file, " Registering value_relation ");
+      vr.dump (dump_file);
+      fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
+      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+    }
+
+  // This relation applies to the entire block, use STMT's block.
+  // Equivalencies are handled by the equivalence oracle.
+  if (k == EQ_EXPR)
+    register_equiv (gimple_bb (stmt), op1, op2);
+  else
+    register_relation (gimple_bb (stmt), k, op1, op2);
+}
+
+// Register relation K between ssa_name OP1 and OP2 on edge E.
+
+void
+relation_oracle::register_relation (edge e, relation_kind k, tree op1,
+				    tree op2)
+{
+  gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
+  gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
+
+  // Do not register lack of relation, or blocks which have more than
+  // edge E for a predecessor.
+  if (k == VREL_NONE || !single_pred_p (e->dest))
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      value_relation vr (k, op1, op2);
+      fprintf (dump_file, " Registering value_relation ");
+      vr.dump (dump_file);
+      fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
+    }
+
+  // Equivalencies are handled by the equivalence oracle.
+  if (k == EQ_EXPR)
+    register_equiv (e->dest, op1, op2);
+  else
+    register_relation (e->dest, k, op1, op2);
+}
+
+// Register relation K between OP! and OP2 in block BB.
+// This creates the record and searches for existing records in the dominator
+// tree to merge with.
+
+void
+relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
+				    tree op2)
+{
+  gcc_checking_assert (k != VREL_NONE);
+
+  value_relation vr(k, op1, op2);
+  int bbi = bb->index;
+
+  if (bbi >= (int)m_relations.length())
+    m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
+
+  // Summary bitmap indicating what ssa_names have relations in this BB.
+  bitmap bm = m_relations[bbi].m_names;
+  if (!bm)
+    bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
+  unsigned v1 = SSA_NAME_VERSION (op1);
+  unsigned v2 = SSA_NAME_VERSION (op2);
+
+  relation_kind curr;
+  relation_chain *ptr;
+  curr = find_relation_block (bbi, v1, v2, &ptr);
+  // There is an existing relation in this block, just intersect with it.
+  if (curr != VREL_NONE)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "    Intersecting with existing ");
+	  ptr->dump (dump_file);
+	}
+      // Check into whether we can simply replace the relation rather than
+      // intersecting it.  THis may help with some optimistic iterative
+      // updating algorithms.
+      ptr->intersect (vr);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, " to produce ");
+	  ptr->dump (dump_file);
+	  fprintf (dump_file, "\n");
+	}
+      return;
+    }
+
+  // Check for an existing relation further up the DOM chain.
+  // By including dominating relations, The first one found in any search
+  // will be the aggregate of all the previous ones.
+  curr = find_relation_dom (bb, v1, v2);
+  if (curr != VREL_NONE)
+    k = relation_intersect (curr, k);
+
+  bitmap_set_bit (bm, v1);
+  bitmap_set_bit (bm, v2);
+  bitmap_set_bit (m_relation_set, v1);
+  bitmap_set_bit (m_relation_set, v2);
+
+  ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
+					  sizeof (relation_chain));
+  ptr->set_relation (k, op1, op2);
+  ptr->m_next = m_relations[bbi].m_head;
+  m_relations[bbi].m_head = ptr;;
+}
+
+// Find the relation between any ssa_name in B1 and any name in B2 in block BB.
+// This will allow equivalencies to be applied to any SSA_NAME in a relation.
+
+relation_kind
+relation_oracle::find_relation_block (unsigned bb, const_bitmap b1,
+				      const_bitmap b2)
+{
+  const_bitmap bm;
+  if (bb >= m_relations.length())
+    return VREL_NONE;
+
+  bm = m_relations[bb].m_names;
+  if (!bm)
+    return VREL_NONE;
+
+  // If both b1 and b2 aren't referenced in thie block, cant be a relation
+  if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2))
+    return VREL_NONE;
+
+  // Search for the fiorst relation that contains BOTH an element from B1
+  // and B2, and return that relation.
+  for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
+    {
+      unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
+      unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
+      if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b1, op2))
+	return ptr->kind ();
+      if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b1, op1))
+	return relation_swap (ptr->kind ());
+    }
+
+  return VREL_NONE;
+}
+
+// Search the DOM tree for a relation between an element of B1 and B2, starting
+// with block BB.
+
+relation_kind
+relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1,
+				    const_bitmap b2)
+{
+  relation_kind r;
+  // If either name does not occur in a relation anywhere, there isnt one.
+  if (!bitmap_intersect_p (m_relation_set, b1)
+      || !bitmap_intersect_p (m_relation_set, b2))
+    return VREL_NONE;
+
+  // Search each block in the DOM tree checking.
+  for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      r = find_relation_block (bb->index, b1, b2);
+      if (r != VREL_NONE)
+	return r;
+    }
+  return VREL_NONE;
+
+}
+
+// Find a relation in block BB between ssa version V1 and V2.  If a relation
+// is found, return a pointer to the chain object in OBJ.
+
+relation_kind
+relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
+				     relation_chain **obj)
+{
+  if (bb >= (int)m_relations.length())
+    return VREL_NONE;
+
+  const_bitmap bm = m_relations[bb].m_names;
+  if (!bm)
+    return VREL_NONE;
+
+  // If both b1 and b2 aren't referenced in thie block, cant be a relation
+  if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
+    return VREL_NONE;
+
+  relation_chain *ptr;
+  for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
+    {
+      unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
+      unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
+      if (v1 == op1 && v2 == op2)
+	{
+	  if (obj)
+	    *obj = ptr;
+	  return ptr->kind ();
+	}
+      if (v1 == op2 && v2 == op1)
+	{
+	  if (obj)
+	    *obj = ptr;
+	  return relation_swap (ptr->kind ());
+	}
+    }
+
+  return VREL_NONE;
+}
+
+// Find a relation between SSA version V1 and V2 in the dominator tree
+// starting with block BB
+
+relation_kind
+relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2)
+{
+  relation_kind r;
+  // IF either name does not occur in a relation anywhere, there isnt one.
+  if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
+    return VREL_NONE;
+
+  for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      r = find_relation_block (bb->index, v1, v2);
+      if (r != VREL_NONE)
+	return r;
+    }
+  return VREL_NONE;
+
+}
+
+// Query if there is a relation between SSA1 and SS2 in block BB or a
+// dominator of BB
+
+relation_kind
+relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
+{
+  relation_kind kind;
+  unsigned v1 = SSA_NAME_VERSION (ssa1);
+  unsigned v2 = SSA_NAME_VERSION (ssa2);
+  if (v1 == v2)
+    return EQ_EXPR;
+
+  // Check for equivalence first.
+  const_bitmap equiv1 = equiv_set (ssa1, bb);
+  if (equiv1 && bitmap_bit_p (equiv1, v2))
+    return EQ_EXPR;
+
+  // Initially look for a direct relationship and just return that.
+  kind = find_relation_dom (bb, v1, v2);
+  if (kind != VREL_NONE)
+    return kind;
+
+  // If one is not found, see if there is a relationship between equivalences.
+  // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either.
+  const_bitmap equiv2 = equiv_set (ssa2, bb);
+  gcc_checking_assert (!equiv2 || !bitmap_bit_p (equiv2, v1));
+
+  if (!equiv1 && !equiv2)
+    kind = VREL_NONE;
+  else if (!equiv1)
+    {
+      bitmap_clear (m_tmp);
+      bitmap_set_bit (m_tmp, v1);
+      kind = find_relation_dom (bb, m_tmp, equiv2);
+    }
+  else if (!equiv2)
+    {
+      bitmap_clear (m_tmp);
+      bitmap_set_bit (m_tmp, v2);
+      kind = find_relation_dom (bb, equiv1, m_tmp);
+    }
+  else
+    kind = find_relation_dom (bb, equiv1, equiv2);
+  return kind;
+}
+
+// Dump all the relations in block BB to file F.
+
+void
+relation_oracle::dump (FILE *f, basic_block bb) const
+{
+  equiv_oracle::dump (f,bb);
+
+  if (bb->index >= (int)m_relations.length ())
+    return;
+  if (!m_relations[bb->index].m_names)
+    return;
+
+  relation_chain *ptr = m_relations[bb->index].m_head;
+  for (; ptr; ptr = ptr->m_next)
+    {
+      fprintf (f, "Relational : ");
+      ptr->dump (f);
+      fprintf (f, "\n");
+    }
+}
+
+// Dump all the relations known to file F.
+
+void
+relation_oracle::dump (FILE *f) const
+{
+  fprintf (f, "Relation dump\n");
+  for (unsigned i = 0; i < m_relations.length (); i++)
+    {
+      fprintf (f, "BB%d\n", i);
+      dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
+    }
+}
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
new file mode 100644
index 00000000000..11488541277
--- /dev/null
+++ b/gcc/value-relation.h
@@ -0,0 +1,159 @@
+/* Header file for the value range relational processing.
+   Copyright (C) 2020-2021 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_VALUE_RELATION_H
+#define GCC_VALUE_RELATION_H
+
+
+// This file provides access to a relation oracle which can be used to
+// maintain and query relations and equivalences between SSA_NAMES.
+//
+// The general range_query object provided in value-query.h provides
+// access to an oracle, if one is available, via the oracle() method.
+// Thre are also a couple of access routines provided, which even if there is
+// no oracle, will return the default VREL_NONE no relation.
+//
+// Typically, when a ranger object is active, there will be an oracle, and
+// any information available can be directly queried.  Ranger also sets and
+// utilizes the relation information to enhance it's range calculations, this
+// is totally transparent to the client, and they are free to make queries.
+//
+//
+// relation_kind is a typedef of enum tree_code, but has restricted range
+// and a couple of extra values.
+//
+// A query is made requesting the relation between SSA1 and SSA@ in a basic
+// block, or on an edge, the possible return values are:
+//
+//  EQ_EXPR, NE_EXPR, LT_EXPR, LE_EXPR, GT_EXPR, and GE_EXPR mean the same.
+//  VREL_NONE : No relation between the 2 names.
+//  VREL_EMPTY : Impossible relation (ie, A < B && A > B produces VREL_EMPTY.
+//
+// The oracle maintains EQ_EXPR relations with equivalency sets, so if a
+// relation comes back EQ_EXPR, it is also possible to query the set of
+// equivlaencies.  These are basically bitmaps over ssa_names.
+//
+// relations are maintained via the dominace trees, are are optimized assuming
+// they are registered in dominance order.   When a new relation is added, it
+// is intersected with whatever existing relation exists in the dominance tree
+// and registered at the specified block.
+
+
+// Rather than introduce a new enumerated type for relations, we can use the
+// existing tree_codes for relations, plus add a couple of #defines for
+// the other cases.  These codes are arranged such that VREL_NONE is the first
+// code, and all the rest are contiguous.
+
+typedef enum tree_code relation_kind;
+
+#define VREL_NONE		TRUTH_NOT_EXPR
+#define VREL_EMPTY		LTGT_EXPR
+
+// General relation kind transformations.
+relation_kind relation_union (relation_kind r1, relation_kind r2);
+relation_kind relation_intersect (relation_kind r1, relation_kind r2);
+relation_kind relation_negate (relation_kind r);
+relation_kind relation_swap (relation_kind r);
+void print_relation (FILE *f, relation_kind rel);
+
+// Declared internally in value-relation.cc
+class equiv_chain;
+
+// 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,
+// and the equivalence is simply applied to that succesor block.
+
+class equiv_oracle
+{
+public:
+  equiv_oracle ();
+  ~equiv_oracle ();
+
+  const_bitmap equiv_set (tree ssa, basic_block bb) const;
+  void register_equiv (basic_block bb, tree ssa1, tree ssa2);
+
+  void dump (FILE *f, basic_block bb) const;
+  void dump (FILE *f) const;
+
+protected:
+  bitmap_obstack m_bitmaps;
+  struct obstack m_chain_obstack;
+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.
+
+  void limit_check (basic_block bb = NULL);
+  equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
+  equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
+
+  bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
+  bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
+			 equiv_chain *equiv_2);
+
+};
+
+// Summary block header for relations.
+
+class relation_chain_head
+{
+public:
+  bitmap m_names;		// ssa_names with relations in this block.
+  class relation_chain *m_head; // List of relations in block.
+};
+
+// A relation oracle maintains a set of relations between ssa_names using the
+// dominator tree structures.  Equivalencies are considered a subset of
+// a general relation and maintained by an equivalence oracle by transparently
+// passing any EQ_EXPR relations to it.
+// Relations are handled at the basic block level.  All relations apply to
+// an entire block, and are thus kept in a summary index by block.
+// Similar to the equivalence oracle, edges are handled by applying the
+// relation to the destination block of the edge, but ONLY if that block
+// has a single successor.  For now.
+
+class relation_oracle : public equiv_oracle
+{
+public:
+  relation_oracle ();
+  ~relation_oracle ();
+
+  void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2);
+  void register_relation (edge e, relation_kind k, tree op1, tree op2);
+
+  relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
+
+  void dump (FILE *f, basic_block bb) const;
+  void dump (FILE *f) const;
+private:
+  bitmap m_tmp;
+  bitmap m_relation_set;  // Index by ssa-name. True if a relation exists
+  vec <relation_chain_head> m_relations;  // Index by BB, list of relations.
+  relation_kind find_relation_block (unsigned bb, const_bitmap b1,
+				     const_bitmap b2);
+  relation_kind find_relation_dom (basic_block bb, const_bitmap b1,
+				   const_bitmap b2);
+  relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
+				     relation_chain **obj = NULL);
+  relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2);
+  void register_relation (basic_block bb, relation_kind k, tree op1, tree op2);
+};
+
+#endif  /* GCC_VALUE_RELATION_H */