Merge from trunk revision 104c05c5284b7822d770ee51a7d91946c7e56d50.

1 files changed, 1172 insertions, 0 deletions

diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
new file mode 100644
index 0000000..ba01d29
--- /dev/null
+++ b/gcc/value-relation.cc
@@ -0,0 +1,1172 @@
+/* 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 R1 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 table is used to determine transitivity between 2 relations.
+// (A relation0 B) and (B relation1 C) implies  (A result C)
+
+relation_kind rr_transitive_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, LT_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LT_EXPR, VREL_NONE },
+// LE_EXPR
+  { VREL_NONE, LT_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LE_EXPR, VREL_NONE },
+// GT_EXPR
+  { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GT_EXPR, VREL_NONE, GT_EXPR, VREL_NONE },
+// GE_EXPR
+  { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GE_EXPR, VREL_NONE, GE_EXPR, VREL_NONE },
+// VREL_EMPTY
+  { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
+// EQ_EXPR
+  { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_NONE, EQ_EXPR, VREL_NONE },
+// NE_EXPR
+  { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE } };
+
+// Apply transitive operation between relation R1 and relation R2, and
+// return the resulting relation, if any.
+
+relation_kind
+relation_transitive (relation_kind r1, relation_kind r2)
+{
+  vrel_range_assert (r1);
+  vrel_range_assert (r2);
+  return rr_transitive_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] && BASIC_BLOCK_FOR_FN (cfun, 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 ();
+  bool apply_transitive (const value_relation &rel);
+
+  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);
+}
+
+// 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;
+}
+
+// Identify and apply any transitive relations between REL
+// and THIS.  Return true if there was a transformation.
+
+bool
+value_relation::apply_transitive (const value_relation &rel)
+{
+  relation_kind k = VREL_NONE;
+
+  // Idenity any common operand, and notrmalize the relations to
+  // the form : A < B  B < C produces A < C
+  if (rel.op1 () == name2)
+    {
+      // A < B   B < C
+      if (rel.op2 () == name1)
+	return false;
+      k = relation_transitive (kind (), rel.kind ());
+      if (k != VREL_NONE)
+	{
+	  related = k;
+	  name2 = rel.op2 ();
+	  return true;
+	}
+    }
+  else if (rel.op1 () == name1)
+    {
+      // B > A   B < C
+      if (rel.op2 () == name2)
+	return false;
+      k = relation_transitive (relation_swap (kind ()), rel.kind ());
+      if (k != VREL_NONE)
+	{
+	  related = k;
+	  name1 = name2;
+	  name2 = rel.op2 ();
+	  return true;
+	}
+    }
+  else if (rel.op2 () == name2)
+    {
+       // A < B   C > B
+       if (rel.op1 () == name1)
+	 return false;
+      k = relation_transitive (kind (), relation_swap (rel.kind ()));
+      if (k != VREL_NONE)
+	{
+	  related = k;
+	  name2 = rel.op1 ();
+	  return true;
+	}
+    }
+  else if (rel.op2 () == name1)
+    {
+      // B > A  C > B
+      if (rel.op1 () == name2)
+	return false;
+      k = relation_transitive (relation_swap (kind ()),
+			       relation_swap (rel.kind ()));
+      if (k != VREL_NONE)
+	{
+	  related = k;
+	  name1 = name2;
+	  name2 = rel.op1 ();
+	  return true;
+	}
+    }
+  return false;
+}
+
+// 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);
+  m_tmp2 = 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.
+// TRANSITIVE_P is true if this is being registered as a transitive operation,
+// and should not try to register further transitives.
+
+void
+relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
+				    tree op2, bool transitive_p)
+{
+  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");
+	}
+    }
+  else
+    {
+      // 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;;
+    }
+
+  if (!transitive_p)
+    register_transitives (bb, *ptr);
+}
+
+// Starting at ROOT_BB search the DOM tree  looking for relations which
+// may produce transitive relations to RELATION.  EQUIV1 and EQUIV2 are
+// bitmaps for op1/op2 and any of their equivalences that should also be
+// considered.
+
+void
+relation_oracle::register_transitives (basic_block root_bb,
+				       const value_relation &relation,
+				       const_bitmap equiv1,
+				       const_bitmap equiv2)
+{
+  basic_block bb;
+  for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      int bbi = bb->index;
+      if (bbi >= (int)m_relations.length())
+	continue;
+      const_bitmap bm = m_relations[bbi].m_names;
+      if (!bm)
+	continue;
+      if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
+	continue;
+      // At least one of the 2 ops has a relation in this block.
+      relation_chain *ptr;
+      for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
+	{
+	  // In the presence of an equivalence, 2 operands may do not
+	  // naturally match. ie  with equivalence a_2 == b_3
+	  // given c_1 < a_2 && b_3 < d_4
+	  // convert the second relation (b_3 < d_4) to match any
+	  // equivalences to found in the first relation.
+	  // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
+	  // transitive operation:  c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
+
+	  tree r1, r2;
+	  tree p1 = ptr->op1 ();
+	  tree p2 = ptr->op2 ();
+	  // Find which equivalence is in the first operand.
+	  if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
+	    r1 = p1;
+	  else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
+	    r1 = p2;
+	  else
+	    r1 = NULL_TREE;
+
+	  // Find which equivalence is in the second operand.
+	  if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
+	    r2 = p1;
+	  else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
+	    r2 = p2;
+	  else
+	    r2 = NULL_TREE;
+
+	  // Ignore if both NULL (not relevant relation) or the same,
+	  if (r1 == r2)
+	    continue;
+
+	  // Any operand not an equivalence, just take the real operand.
+	  if (!r1)
+	    r1 = relation.op1 ();
+	  if (!r2)
+	    r2 = relation.op2 ();
+
+	  value_relation nr (relation.kind (), r1, r2);
+	  if (nr.apply_transitive (*ptr))
+	    {
+	      register_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 (),
+				 true);
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "   Registering transitive relation ");
+		  nr.dump (dump_file);
+		  fputc ('\n', dump_file);
+		}
+	    }
+
+	}
+    }
+}
+
+// Find adn register any transitive relations implied by RELATION occuring
+// in block BB.
+
+void
+relation_oracle::register_transitives (basic_block bb,
+				       const value_relation &relation)
+{
+  // Only apply transitives to certain kinds of operations.
+  switch (relation.kind ())
+    {
+      case LE_EXPR:
+      case LT_EXPR:
+      case GT_EXPR:
+      case GE_EXPR:
+	break;
+      default:
+	return;
+    }
+
+  // Set up the bitmaps for op1 and op2, and if there are no equivalencies,
+  // set just op1 or op2 in their own bitmap.
+  const_bitmap equiv1 = equiv_set (relation.op1 (), bb);
+  const_bitmap equiv2 = equiv_set (relation.op2 (), bb);
+  if (equiv1)
+    {
+      if (equiv2)
+	register_transitives (bb, relation, equiv1, equiv2);
+      else
+	{
+	  bitmap_clear (m_tmp);
+	  bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op2 ()));
+	  register_transitives (bb, relation, equiv1, m_tmp);
+	}
+    }
+  else if (equiv2)
+    {
+      bitmap_clear (m_tmp);
+      bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ()));
+      register_transitives (bb, relation, m_tmp, equiv2);
+    }
+  else
+    {
+      bitmap_clear (m_tmp);
+      bitmap_clear (m_tmp2);
+      bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ()));
+      bitmap_set_bit (m_tmp2, SSA_NAME_VERSION (relation.op2 ()));
+      register_transitives (bb, relation, m_tmp, m_tmp2);
+    }
+}
+
+// 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 (b2, op2))
+	return ptr->kind ();
+      if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, 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 v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either.
+  // It is possible for out-of-order dominator processing to have an out of
+  // sync set of equivalences..  Down the road, when we do full updates,
+  // change this to an assert to ensure everything is in sync.
+  const_bitmap equiv2 = equiv_set (ssa2, bb);
+  if (equiv2 && bitmap_bit_p (equiv2, v1))
+    return EQ_EXPR;
+
+  // If not equal, see if there is a relationship between equivalences.
+  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++)
+    if (BASIC_BLOCK_FOR_FN (cfun, i))
+      {
+	fprintf (f, "BB%d\n", i);
+	dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
+      }
+}
+
+void
+relation_oracle::debug () const
+{
+  dump (stderr);
+}