This file introduces a relation oracle to GCC.
Rather than introducing a new enum for relations, I chose to reuse a
range of enum tree_code, leaving us with mostly familiar names:
EQ_EXPR, NE_EXPR, GT_EXPR, GE_EXPR, LT_EXPR and LE_EXPR. In addition to
these relations, are 2 other codes:
#define VREL_NONE TRUTH_NOT_EXPR
#define VREL_EMPTY LTGT_EXPR
VREL_NONE represents a lack of a relation (ie a = b + c there is no
relation between b and c, so thats VREL_NONE)
VREL_EMPTY represents an EMPTY , or impossible relation. This is
usually the result of combining relations that apply (ie, a > b && a <
b provides a VREL_EMPTY representing the relation between a and b on
the true side. Its impossible.)
The additional relations have tree codes chosen carefully to form a
contiguous series from VREL_NONE to NE_EXPR enabling some internal
calculation tables to be used indexing from 0..last_relation . This is
easily changed, but seems convenient.
The oracle is pretty basic to start, but will be enhanced as we move
along. It requires a dominance tree and stores/looks up things based on
dominance. It hasn't been extensively analyzed in an iterative/on-demand
environment yet, so there may be some warts that show up. It should
never give a wrong result, but its possible it may miss something in
some instances. We'll work those out as we find them. It exists in
2 parts:
- an equivalence oracle which manages all the EQ_EXPR relations, and
groups equivalences as sets, and
- a relation oracle which derives from that which handles all the other
relations.
The API is straightforward. Relations are registered via one of 2 routines:
void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2);
void register_relation (edge e, relation_kind k, tree op1, tree op2);
and there is a single query routine:
relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2);
Our friend the range_query object now contains a relation pointer, and
this is set and used by ranger. range_query has also had 2 query
routines added so if a pass is using a ranger, it can also invoke the
range queries that same way range_of_expr is invokes. ie:
get_range_query (cfun)->query_relation (stmt, ssa1, ssa2) THis
mechanism has the advantage that you dont need to check if an oracle is
present, it'll simple return VREL_NONE (no relation) between 2 ssa-names
if there is no oracle.
More advanced users can access the oracle directly via the
get_range_query (cfun)->oracle () call. It would be possible to create
an oracle for a pass without a ranger, and manage the relations in the
pass. That is not being done yet, but would be easy enough to add the
enable/disable() oracle routines much like the enable/disable_ranger
routines.
When using ranger, this information is set and propagated automatically,
and the results are transparently applied to the ranges that are
generated. For instance,
if (a_2 < b_3) // register relation a_2 < b_3 on the true edge
c_3 = a_2 > b_3 // applies a_2 < b_3, and the range of c_3 is set
to [0, 0] or false.
Currently only direct 1st order relations are tracked. I will get to
transitive relations soon, but that is not in this first round.
Relations on edges are also currently limited to single predecessor
blocks .. They are simply dropped/ignored if the destination of the
edge has multiple preds.
I will be writing up a relation guide in the not too distant future,
alone with a few of the other components.
This patch provides the oracle, as well as the range_query interface,
but does not actually do anything.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
>From 3aaa69e5f30e1904d7ca2bb711b1cb0c62b6895f Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Thu, 17 Jun 2021 10:19:31 -0400
Subject: [PATCH 1/7] 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.
---
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(-)
create mode 100644 gcc/value-relation.cc
create mode 100644 gcc/value-relation.h
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 <amacl...@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 <amacl...@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 */
--
2.17.2
