From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id D820F3858C55; Thu, 13 Oct 2022 15:29:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D820F3858C55 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665674964; bh=YicFvdG0M/IoX5Q3gU62NzWq4zps6PzvD5knHwhcr8w=; h=From:To:Subject:Date:From; b=NtO2ScgfpNQONvYjk6/ChAhg1arpLq6g8U9AireBX4W2wipwC7uxwO3aG6tyZ6mqG yEFIUSO8wgf5Kj5DBAwW3dSp0Ds49Oa7Y8u1+OUAztdMvmo+r1Nw6iJTmmrDSssKnS v3gMkkJBBHLPDD3n5sb3SYfTU/oLGkYqVjWuFxF4= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-3278] Add partial equivalence support to the relation oracle. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 3130e70dab1e64a7b014391fe941090d5f3b6b7d X-Git-Newrev: b5563410ea613ff2b2d7c6fa1847cfcb1ff91efb Message-Id: <20221013152924.D820F3858C55@sourceware.org> Date: Thu, 13 Oct 2022 15:29:24 +0000 (GMT) List-Id: https://gcc.gnu.org/g:b5563410ea613ff2b2d7c6fa1847cfcb1ff91efb commit r13-3278-gb5563410ea613ff2b2d7c6fa1847cfcb1ff91efb Author: Andrew MacLeod Date: Thu Oct 6 15:00:52 2022 -0400 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. Diff: --- gcc/value-relation.cc | 165 ++++++++++++++++++++++++++++++++++++++++++++++---- gcc/value-relation.h | 78 +++++++++++++++++++++++- 2 files changed, 229 insertions(+), 14 deletions(-) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 1ee6da199f2..ceeca53e0a1 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -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) diff --git a/gcc/value-relation.h b/gcc/value-relation.h index e1347ea8ad8..f5f2524ad56 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -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 m_equiv; // Index by BB. list of equivalences. vec m_self_equiv; // Index by ssa-name, self equivalency set. + vec 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 */