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