Google GitGoogle Git
Sign in
gnu/gcc.git/refs/heads/master/./gcc/value-relation.cc
blob: 5fc7817936888c548d7f99439653ca63e47da8eb [file]
/* Header file for the value range relational processing.
Copyright (C) 2020-2026 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"
static const char *const kind_string[VREL_LAST] =
{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
"pe32", "pe64" };
// Print a relation_kind REL to file F.
void
print_relation (FILE *f, relation_kind rel)
{
fprintf (f, " %s ", kind_string[rel]);
}
// This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
// Partial equivalence can't be negated, so VARYING is correct.
static const unsigned char rr_negate_table[VREL_LAST] = {
VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
VREL_EQ, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING };
// Negate the relation, as in logical negation.
relation_kind
relation_negate (relation_kind r)
{
return relation_kind (rr_negate_table [r]);
}
// This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
// Partial equivalences swap to themselves as the low N bits are equal.
static const unsigned char rr_swap_table[VREL_LAST] = {
VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 };
// Return the relation as if the operands were swapped.
relation_kind
relation_swap (relation_kind r)
{
return relation_kind (rr_swap_table [r]);
}
// This table is used to perform an intersection between 2 relations.
// EQ is a full equivalency, and thus replaces any partial equivalence.
// Likewise, the higher bit PE is more "equivalent" than the lower bit version
// and thus more restrictive.
static const unsigned char rr_intersect_table[VREL_LAST][VREL_LAST] = {
// VREL_VARYING
{ VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_UNDEFINED
{ VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
// VREL_LT
{ VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
VREL_UNDEFINED, VREL_LT,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_LE
{ VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
VREL_EQ, VREL_LT,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GT
{ VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
VREL_UNDEFINED, VREL_GT,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GE
{ VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
VREL_EQ, VREL_GT,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_EQ
{ VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
VREL_EQ, VREL_UNDEFINED,
VREL_EQ, VREL_EQ, VREL_EQ, VREL_EQ },
// VREL_NE
{ VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
VREL_UNDEFINED, VREL_NE,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_PE8
{ VREL_PE8, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_EQ, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_PE16
{ VREL_PE16, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_EQ, VREL_VARYING,
VREL_PE16, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_PE32
{ VREL_PE32, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_EQ, VREL_VARYING,
VREL_PE32, VREL_PE32, VREL_PE32, VREL_PE64 },
// VREL_PE64
{ VREL_PE64, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_EQ, VREL_VARYING,
VREL_PE64, VREL_PE64, VREL_PE64, VREL_PE64 } };
// Intersect relation R1 with relation R2 and return the resulting relation.
relation_kind
relation_intersect (relation_kind r1, relation_kind r2)
{
return relation_kind (rr_intersect_table[r1][r2]);
}
// This table is used to perform a union between 2 relations.
// EQ unions with a PE to produce the same PE, and likewise whichever PE
// has the least common bits forms the union.
static const unsigned char rr_union_table[VREL_LAST][VREL_LAST] = {
// VREL_VARYING
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_UNDEFINED
{ VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE,
VREL_EQ, VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_LT
{ VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_LE
{ VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
VREL_LE, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GT
{ VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GE
{ VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
VREL_GE, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_EQ
{ VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
VREL_VARYING, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_NE
{ VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
VREL_VARYING, VREL_NE,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_PE8
{ VREL_VARYING, VREL_PE8, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE8, VREL_VARYING,
VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
// VREL_PE16
{ VREL_VARYING, VREL_PE16, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE16, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
// VREL_PE32
{ VREL_VARYING, VREL_PE32, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE32, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
// VREL_PE64
{ VREL_VARYING, VREL_PE64, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE64, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
// Union relation R1 with relation R2 and return the result.
relation_kind
relation_union (relation_kind r1, relation_kind r2)
{
return relation_kind (rr_union_table[r1][r2]);
}
// This table is used to determine transitivity between 2 relations.
// (A relation0 B) and (B relation1 C) implies (A result C)
// Chaining two partial equivalences leaves only the bits both agree on, ie
// the narrower of the two.
static const unsigned char rr_transitive_table[VREL_LAST][VREL_LAST] = {
// VREL_VARYING
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_UNDEFINED
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_LT
{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
VREL_LT, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_LE
{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
VREL_LE, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GT
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
VREL_GT, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_GE
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
VREL_GE, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_EQ
{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
// VREL_NE
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_NE, VREL_VARYING,
VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
// VREL_PE8
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE8, VREL_VARYING,
VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
// VREL_PE16
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE16, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
// VREL_PE32
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE32, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
// VREL_PE64
{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
VREL_VARYING, VREL_PE64, VREL_VARYING,
VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
// 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)
{
return relation_kind (rr_transitive_table[r1][r2]);
}
// When one name is an equivalence of another, ensure the equivalence
// range is correct. Specifically for floating point, a +0 is also
// equivalent to a -0 which may not be reflected. See PR 111694.
void
adjust_equivalence_range (vrange &range)
{
if (range.undefined_p () || !is_a<frange> (range))
return;
frange fr = as_a<frange> (range);
// If range includes 0 make sure both signs of zero are included.
if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
{
frange zeros (range.type (), dconstm0, dconst0);
range.union_ (zeros);
}
}
// Given an equivalence set EQUIV, set all the bits in B that are still valid
// members of EQUIV in basic block BB.
void
relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
{
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
{
tree ssa = ssa_name (i);
if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
{
const_bitmap ssa_equiv = equiv_set (ssa, bb);
if (ssa_equiv == equivs)
bitmap_set_bit (b, i);
}
}
}
// 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 definitions have been processed and any relations have be created.
relation_kind
relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
{
if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
return VREL_VARYING;
return query (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 definitions have been processed and any relations have be created.
relation_kind
relation_oracle::query (edge e, tree ssa1, tree ssa2)
{
basic_block bb;
if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
return VREL_VARYING;
// 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;
return query (bb, ssa1, ssa2);
}
// -------------------------------------------------------------------------
// 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 lists need be searched.
// If SSA has an equivalence in this list, find and return it.
// Otherwise return NULL.
equiv_chain *
equiv_chain::find (unsigned ssa)
{
equiv_chain *ptr = NULL;
// If there are equiv sets and SSA is in one in this list, find it.
// Otherwise return NULL.
if (bitmap_bit_p (m_names, ssa))
{
for (ptr = m_next; ptr; ptr = ptr->m_next)
if (bitmap_bit_p (ptr->m_names, ssa))
break;
}
return ptr;
}
// Dump the names in this equivalence set.
void
equiv_chain::dump (FILE *f) const
{
bitmap_iterator bi;
unsigned i;
if (!m_names || bitmap_empty_p (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);
bitmap_tree_view (m_equiv_set);
obstack_init (&m_chain_obstack);
m_name_info.create (0);
m_name_info.safe_grow_cleared (num_ssa_names + 1);
m_partial.create (0);
m_partial.safe_grow_cleared (num_ssa_names + 1);
// Create a bitmap to avoid registering multiple equivalences from a LHS.
// See PR 124809.
m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
bitmap_tree_view (m_lhs_equiv_set_p);
}
// Destruct an equivalency oracle.
equiv_oracle::~equiv_oracle ()
{
m_partial.release ();
m_name_info.release ();
obstack_free (&m_chain_obstack, NULL);
m_equiv.release ();
bitmap_obstack_release (&m_bitmaps);
}
// Add a partial equivalence R between OP1 and OP2. Return false if no
// new relation is added.
bool
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 false;
// If there are no uses of op2, do not register.
if (has_zero_uses (op2))
return false;
// 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 = pe_min (m_partial[x].code, pe2.code);
}
bitmap_set_bit (pe1.members, v2);
return true;
}
if (pe2.members)
{
// If there are no uses of op1, do not register.
if (has_zero_uses (op1))
return false;
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
{
// If there are no uses of either operand, do not register.
if (has_zero_uses (op1) || has_zero_uses (op2))
return false;
// 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 false;
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 true;
}
// 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;
}
void
equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
{
if (v >= m_name_info.length ())
m_name_info.safe_grow_cleared (num_ssa_names + 1);
if (!m_name_info[v].m_block_list)
m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (m_name_info[v].m_block_list, bbi);
}
void
equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
{
bitmap_iterator bi;
unsigned v;
EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
register_equiv_block (v, bb->index);
}
// 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)
{
// Search the dominator tree for an equivalency.
equiv_chain *equiv = find_equiv_dom (ssa, bb);
if (equiv)
return equiv->m_names;
// Otherwise return a cached equiv set containing just this SSA.
unsigned v = SSA_NAME_VERSION (ssa);
if (v >= m_name_info.length ())
m_name_info.safe_grow_cleared (num_ssa_names + 1);
if (!m_name_info[v].m_self_equiv)
{
m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (m_name_info[v].m_self_equiv, v);
}
return m_name_info[v].m_self_equiv;
}
// Query if there is a relation (equivalence) between 2 SSA_NAMEs.
relation_kind
equiv_oracle::query (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;
// Check if there is a partial equivalence.
return partial_equiv (ssa1, ssa2);
}
// Query if there is a relation (equivalence) between 2 SSA_NAMEs.
relation_kind
equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
const_bitmap e2)
{
// If the 2 ssa names share the same equiv set, they are equal.
if (bitmap_equal_p (e1, e2))
return VREL_EQ;
return VREL_VARYING;
}
// 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
{
if (bb >= (int)m_equiv.length () || !m_equiv[bb])
return NULL;
return m_equiv[bb]->find (ssa);
}
// 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 equivalence 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);
// Add BB to V.
register_equiv_block (v, bb->index);
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);
valid_equivs (b, equiv->m_names, bb);
bitmap_set_bit (b, v);
// Add BB to the all the equiv names.
register_equiv_block (b, bb);
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 already in BB, use it as the combined set.
if (equiv_1->m_bb == bb)
{
valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
// 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 the new names are in the summary for BB.
bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
// Add BB to the names in equiv2.
register_equiv_block (equiv_2->m_names, bb);
}
return NULL;
}
// If equiv_2 is in BB, use it for the combined set.
if (equiv_2->m_bb == bb)
{
valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
// Ensure the new names are in the summary.
bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
// Add BB to the names in equiv1.
register_equiv_block (equiv_1->m_names, bb);
return NULL;
}
// At this point, neither equivalence is from this block.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
valid_equivs (b, equiv_1->m_names, bb);
valid_equivs (b, equiv_2->m_names, bb);
// Add BB to the all the equiv names.
register_equiv_block (b, bb);
return b;
}
// Create an equivalency set containing only SSA in its definition block.
// This is done the first time SSA is registered in an equivalency and blocks
// any DOM searches past the definition.
void
equiv_oracle::register_initial_def (tree ssa)
{
if (SSA_NAME_IS_DEFAULT_DEF (ssa))
return;
basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
// If defining stmt is not in the IL, simply return.
if (!bb)
return;
gcc_checking_assert (!find_equiv_dom (ssa, bb));
unsigned v = SSA_NAME_VERSION (ssa);
bitmap_set_bit (m_equiv_set, v);
bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (equiv_set, v);
add_equiv_to_block (bb, equiv_set);
}
// Clear the equivalence lists and partial equivalencs for NAME.
void
equiv_oracle::clear (tree name)
{
unsigned v = SSA_NAME_VERSION (name);
// Remove NAME from any blocks it is an equivalence in.
if (bitmap_bit_p (m_equiv_set, v))
{
gcc_checking_assert (m_name_info[v].m_block_list);
bitmap_iterator bi;
unsigned bbi;
EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
{
if (bbi >= m_equiv.length ())
break;
if (!m_equiv[bbi])
continue;
equiv_chain *ptr = m_equiv[bbi]->find (v);
if (ptr)
{
bitmap_clear_bit (ptr->m_names, v);
bitmap_clear_bit (m_equiv[bbi]->m_names, v);
}
}
bitmap_clear_bit (m_equiv_set, v);
bitmap_clear (m_name_info[v].m_block_list);
}
// Eliminate any partial equivs.
if (v < m_partial.length ())
m_partial[v].members = NULL;
}
// 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 between 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.
// Return false if no new relation is added.
bool
equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
{
// Process partial equivalencies.
if (relation_partial_equiv_p (k))
return add_partial_equiv (k, ssa1, ssa2);
// Only handle equality relations.
if (k != VREL_EQ)
return false;
unsigned v1 = SSA_NAME_VERSION (ssa1);
unsigned v2 = SSA_NAME_VERSION (ssa2);
// If this is the first time an ssa_name has an equivalency registered
// create a self-equivalency record in the def block.
if (!bitmap_bit_p (m_equiv_set, v1))
register_initial_def (ssa1);
if (!bitmap_bit_p (m_equiv_set, v2))
register_initial_def (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 false;
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 false;
add_equiv_to_block (bb, equiv_set);
return true;
}
// Add an equivalency record in block BB containing bitmap EQUIV_SET.
// Note the internal caller is responsible for allocating EQUIV_SET properly.
void
equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
{
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.
limit_check (bb);
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);
// Add BB to the equiv set.
register_equiv_block (equiv_set, bb);
}
// 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;
// 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.
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));
}
}
// --------------------------------------------------------------------------
// Adjust the relation by Swapping the operands and relation.
void
value_relation::swap ()
{
related = relation_swap (related);
tree tmp = name1;
name1 = name2;
name2 = tmp;
}
// Perform an intersection between 2 relations. *this &&= p.
// Return false if the relations cannot be intersected.
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_VARYING;
// Identify any common operand, and normalize 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_VARYING)
{
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_VARYING)
{
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_VARYING)
{
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_VARYING)
{
related = k;
name1 = name2;
name2 = rel.op1 ();
return true;
}
}
return false;
}
// Create a trio from this value relation given LHS, OP1 and OP2.
relation_trio
value_relation::create_trio (tree lhs, tree op1, tree op2)
{
relation_kind lhs_1;
if (lhs == name1 && op1 == name2)
lhs_1 = related;
else if (lhs == name2 && op1 == name1)
lhs_1 = relation_swap (related);
else
lhs_1 = VREL_VARYING;
relation_kind lhs_2;
if (lhs == name1 && op2 == name2)
lhs_2 = related;
else if (lhs == name2 && op2 == name1)
lhs_2 = relation_swap (related);
else
lhs_2 = VREL_VARYING;
relation_kind op_op;
if (op1 == name1 && op2 == name2)
op_op = related;
else if (op1 == name2 && op2 == name1)
op_op = relation_swap (related);
else if (op1 == op2)
op_op = VREL_EQ;
else
op_op = VREL_VARYING;
return relation_trio (lhs_1, lhs_2, op_op);
}
// Dump the relation to file F.
void
value_relation::dump (FILE *f) const
{
if (!name1 || !name2)
{
fprintf (f, "no relation registered");
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;
};
// Given relation record PTR in block BB, return the next relation in the
// list. If PTR is NULL, retrieve the first relation in BB.
// If NAME is sprecified, return only relations which include NAME.
// Return NULL when there are no relations left.
relation_chain *
dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
tree name) const
{
relation_chain *p;
// No value_relation pointer is used to initialize the iterator.
if (!ptr)
{
int bbi = bb->index;
if (bbi >= (int)m_relations.length())
return NULL;
else
p = m_relations[bbi].m_head;
}
else
p = ptr->m_next;
if (name)
for ( ; p; p = p->m_next)
if (p->op1 () == name || p->op2 () == name)
break;
return p;
}
// Instantiate a block relation iterator to iterate over the relations
// on exit from block BB in ORACLE. Limit this to relations involving NAME
// if specified. Return the first such relation in VR if there is one.
block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
basic_block bb,
value_relation &vr,
tree name)
{
m_oracle = oracle;
m_bb = bb;
m_name = name;
m_ptr = oracle->next_relation (bb, NULL, m_name);
if (m_ptr)
{
m_done = false;
vr = *m_ptr;
}
else
m_done = true;
}
// Retrieve the next relation from the iterator and return it in VR.
void
block_relation_iterator::get_next_relation (value_relation &vr)
{
m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
if (m_ptr)
{
vr = *m_ptr;
if (m_name)
{
if (vr.op1 () != m_name)
{
gcc_checking_assert (vr.op2 () == m_name);
vr.swap ();
}
}
}
else
m_done = true;
}
// ------------------------------------------------------------------------
// Find the relation between any ssa_name in B1 and any name in B2 in LIST.
// This will allow equivalencies to be applied to any SSA_NAME in a relation.
relation_kind
relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
{
if (!m_names)
return VREL_VARYING;
// If both b1 and b2 aren't referenced in this block, cant be a relation
if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
return VREL_VARYING;
// Search for the first relation that contains BOTH an element from B1
// and B2, and return that relation.
for (relation_chain *ptr = 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_VARYING;
}
// ------------------------------------------------------------------------
// frontier_data methods - what one side of a bidirectional search knows.
// Construct frontier data allocating the bitmap from OBSTACK and side flag RHS.
frontier_data::frontier_data (bitmap_obstack *obstack, bool rhs)
{
m_known.create (0);
m_visited = BITMAP_ALLOC (obstack);
m_root = NULL_TREE;
m_rhs = rhs;
}
// Record that the root of this search is related to ssa version V by REL.
void
frontier_data::set_known (unsigned v, relation_kind rel)
{
if (m_known.length () <= v)
m_known.safe_grow_cleared (num_ssa_names + 1);
m_known[v] = rel;
}
// Return what the root of this search is known to be relative to ssa version V.
relation_kind
frontier_data::known_relation (unsigned v) const
{
if (v < m_known.length ())
return m_known[v];
return VREL_VARYING;
}
// Reset for the next search. Only the entries which were actually set need
// to be put back, and m_visited lists exactly those.
void
frontier_data::clear_search ()
{
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (m_visited, 0, i, bi)
{
if (i < m_known.length ())
m_known[i] = VREL_VARYING;
}
bitmap_clear (m_visited);
m_root = NULL_TREE;
}
// ------------------------------------------------------------------------
// Instantiate a relation oracle.
dom_oracle::dom_oracle () : m_lhs_search (&m_bitmaps, false),
m_rhs_search (&m_bitmaps, true)
{
m_relations.create (0);
m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
m_relation_set = BITMAP_ALLOC (&m_bitmaps);
m_block_list.create (0);
m_block_list.safe_grow_cleared (num_ssa_names + 1);
m_tmp = BITMAP_ALLOC (&m_bitmaps);
m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
m_near.create (0);
m_worklist.create (0);
m_wl_ix = 0;
}
// Destruct a relation oracle.
dom_oracle::~dom_oracle ()
{
m_worklist.release ();
m_near.release ();
m_block_list.release ();
m_relations.release ();
}
// Remove any relations with NAME from this list.
void
relation_chain_head::clear (tree name)
{
unsigned v = SSA_NAME_VERSION (name);
if (!m_names || !bitmap_bit_p (m_names, v))
return;
relation_chain *ptr, *last = NULL;;
for (ptr = m_head; ptr; ptr = ptr->m_next)
{
tree op1 = ptr->op1 ();
tree op2 = ptr->op2 ();
// Delink any elements with NAME.
if (op1 == name || op2 == name)
{
if (!last)
m_head = ptr->m_next;
else
last->m_next = ptr->m_next;
m_num_relations--;
}
else
last = ptr;
}
// And remove name from the possible relations in this block bitfield.
bitmap_clear_bit (m_names, v);
}
// Remove any relations involving NAME from the DOM oracle
void
dom_oracle::clear (tree name)
{
equiv_oracle::clear (name);
unsigned v = SSA_NAME_VERSION (name);
if (bitmap_bit_p (m_relation_set, v))
{
gcc_checking_assert (m_block_list[v]);
bitmap_iterator bi;
unsigned bbi;
EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
{
if (bbi >= m_relations.length())
break;
m_relations[bbi].clear (name);
}
bitmap_clear_bit (m_relation_set, v);
bitmap_clear (m_block_list[v]);
}
}
// Register relation K between ssa_name OP1 and OP2 on STMT.
// Return false if no new relation is added.
bool
relation_oracle::record (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_VARYING)
return false;
// If an equivalence is being added between a PHI and one of its arguments
// make sure that that argument is not defined in the same block.
// This can happen along back edges and the equivalence will not be
// applicable as it would require a use before def.
if (k == VREL_EQ && is_a<gphi *> (stmt))
{
tree phi_def = gimple_phi_result (stmt);
gcc_checking_assert (phi_def == op1 || phi_def == op2);
tree arg = op2;
if (phi_def == op2)
arg = op1;
if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
return false;
}
// If the LHS of a statement has already been processed and an equivalence
// registered, do not register another one. See PR 124809.
if (m_lhs_equiv_set_p && relation_equiv_p (k)
&& gimple_get_lhs (stmt) == op1)
{
if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
return false;
}
bool ret = record (gimple_bb (stmt), k, op1, op2);
if (ret && 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);
}
return ret;
}
// Register relation K between ssa_name OP1 and OP2 on edge E.
// Return false if no new relation is added.
bool
relation_oracle::record (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_VARYING || !single_pred_p (e->dest))
return false;
bool ret = record (e->dest, k, op1, op2);
if (ret && 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);
}
return ret;
}
// 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. Return false if no new relation is added.
bool
dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
{
// If the 2 ssa_names are the same, do nothing. An equivalence is implied,
// and no other relation makes sense.
if (op1 == op2)
return false;
// Do not register an impossible relation.
if (k == VREL_UNDEFINED)
return false;
// Equivalencies are handled by the equivalence oracle.
if (relation_equiv_p (k))
return equiv_oracle::record (bb, k, op1, op2);
else
{
relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
return ptr != NULL;
}
}
void
dom_oracle::record_relation_block (unsigned v, unsigned bbi)
{
if (v>= m_block_list.length ())
m_block_list.safe_grow_cleared (num_ssa_names + 1);
if (!m_block_list[v])
m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (m_block_list[v], bbi);
}
// Register relation K between OP1 and OP2 in block BB by creating a new
// record. It is an error for there to be an existing record.
// Return the record, or NULL if no record was created.
relation_chain *
dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
tree op2)
{
int bbi = bb->index;
if (bbi >= (int)m_relations.length())
m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
return NULL;
m_relations[bbi].m_num_relations++;
// 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.
relation_chain *ptr;
// 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);
// Assert there is no existing relation.
gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
== VREL_VARYING);
bitmap_set_bit (bm, v1);
bitmap_set_bit (bm, v2);
bitmap_set_bit (m_relation_set, v1);
bitmap_set_bit (m_relation_set, v2);
record_relation_block (v1, bbi);
record_relation_block (v2, bbi);
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;
return ptr;
}
// Register relation K between OP1 and OP2 in block BB by searching the
// dominator tree for any existing record to merge with. If there were
// none, create a new record.
// Return the record, or NULL if no record was found or created.
relation_chain *
dom_oracle::search_and_merge_relation (basic_block bb, relation_kind k,
tree op1, tree op2)
{
// Check for invalid relations to register.
gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED
&& k != VREL_EQ);
relation_chain *ptr;
relation_kind curr = find_relation_block (bb->index, op1, op2, &ptr);
// If there is an existing relation in this block, just intersect with it.
if (curr != VREL_VARYING)
{
// If K contradicts what is already recorded, the block is unreachable.
// Leave the existing relation alone rather than replacing it with
// UNDEFINED, matching what the dominator merge below does.
if (relation_intersect (curr, k) == VREL_UNDEFINED)
return NULL;
// If there was no change, return no record.
value_relation vr (k, op1, op2);
if (!ptr->intersect (vr))
return NULL;
return ptr;
}
// Create the relation in this block.
ptr = create_relation_in_bb (bb, k, op1, op2);
if (ptr)
{
// 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 (get_immediate_dominator (CDI_DOMINATORS, bb),
op1, op2);
if (curr != VREL_VARYING)
{
curr = relation_intersect (curr, k);
// Intersect the new relation with the existing one, unless the
// result is UNDEFINED. Then just leave it.
if (curr != k && curr != VREL_UNDEFINED)
ptr->set_relation (curr, op1, op2);
}
}
return 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
dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
const_bitmap b2) const
{
if (bb >= m_relations.length())
return VREL_VARYING;
return m_relations[bb].find_relation (b1, b2);
}
// Search the DOM tree for a relation between an element of equivalency set B1
// and B2, starting with block BB.
relation_kind
dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
{
relation_kind r;
if (bitmap_equal_p (b1, b2))
return VREL_EQ;
// If either name does not occur in a relation anywhere, there isn't one.
if (!bitmap_intersect_p (m_relation_set, b1)
|| !bitmap_intersect_p (m_relation_set, b2))
return VREL_VARYING;
// 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_VARYING)
return r;
}
return VREL_VARYING;
}
// 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
dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
relation_chain **obj) const
{
if (bb >= (int)m_relations.length())
return VREL_VARYING;
const_bitmap bm = m_relations[bb].m_names;
if (!bm)
return VREL_VARYING;
unsigned v1 = SSA_NAME_VERSION (ssa1);
unsigned v2 = SSA_NAME_VERSION (ssa2);
// If both b1 and b2 aren't referenced in this block, cant be a relation
if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
return VREL_VARYING;
relation_chain *ptr;
for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
{
tree op1 = ptr->op1 ();
tree op2 = ptr->op2 ();
if (ssa1 == op1 && ssa2 == op2)
{
if (obj)
*obj = ptr;
return ptr->kind ();
}
if (ssa1 == op2 && ssa2 == op1)
{
if (obj)
*obj = ptr;
return relation_swap (ptr->kind ());
}
}
return VREL_VARYING;
}
// See if a relation can be found between SSA1 and SSA2 in basic block BB based
// on values as they exist in basic block ORIG. This will only occur
// if SSA1 and SSA2 occur in the same statement together.
relation_kind
dom_oracle::recomputed_relation (basic_block orig_bb, tree ssa1,
tree ssa2) const
{
if (ssa1 == ssa2)
return VREL_EQ;
if (!orig_bb)
return VREL_VARYING;
gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
if (!gori_ssa)
return VREL_VARYING;
gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
// Both ssa1 and ssa2 must be exported somewhere.
if (!gori_ssa->is_export_p (ssa1) || !gori_ssa->is_export_p (ssa2))
return VREL_VARYING;
relation_kind result = VREL_VARYING;
use_operand_p use_p;
imm_use_iterator iter;
// Any statement with both SSA1 and SSA2 as operands may imply a relation
// between them, once the range of its LHS at ORIG_BB is known.
FOR_EACH_IMM_USE_FAST (use_p, iter, ssa1)
{
bool reversed = false;
gimple *s = USE_STMT (use_p);
// S must be a binary assignment LHS = op1 op2
if (!is_gimple_assign (s) || gimple_num_ops (s) != 3)
continue;
// S must strictly dominate ORIG_BB. DOMINATED_BY_P is block granular,
// so the same-block case must be excluded.
basic_block sbb = gimple_bb (s);
if (!sbb || sbb == orig_bb
|| !dominated_by_p (CDI_DOMINATORS, orig_bb, sbb))
continue;
gimple_range_op_handler s_handler (s);
if (!s_handler)
continue;
if (s_handler.operand1 () == ssa1)
{
// op1 == ssa1, move on if op2 != ssa2.
if (s_handler.operand2 () != ssa2)
continue;
}
// Otherwise only move on if op1 == ssa2 && op2 == ssa1.
else if (s_handler.operand1 () != ssa2 || s_handler.operand2 () != ssa1)
continue;
else
reversed = true;
// Find the outgoing edge of SBB which must have been taken to reach
// ORIG_BB. SINGLE_PRED_P is required as well as dominance: if E->dest
// has another predecessor, it can dominate ORIG_BB via a path which
// never traversed E, and E's range would not apply.
edge e = NULL, se;
edge_iterator ei;
FOR_EACH_EDGE (se, ei, sbb->succs)
if (single_pred_p (se->dest)
&& dominated_by_p (CDI_DOMINATORS, orig_bb, se->dest))
{
e = se;
break;
}
if (!e)
continue;
int_range_max edge_range;
gimple *stmt = gori.edge_range_p (edge_range, e);
if (!stmt)
continue;
// Walk back from the terminator of SBB towards S, recalculating each
// value as it would be in ORIG_BB rather than as it is on E. This is
// the whole point: RANGE_ON_ENTRY cannot supply S's LHS at ORIG_BB
// because it evaluates each dominating edge using the values available
// at that edge's source.
tree lhs_s = s_handler.lhs ();
value_range lhs_range (edge_range);
while (stmt && stmt != s)
{
bool ret;
gimple_range_op_handler handler (stmt);
if (!handler)
break;
tree op1 = handler.operand1 ();
tree op2 = handler.operand2 ();
value_range op1_range (TREE_TYPE (op1));
value_range op2_range;
// Follow the operand whose dependency chain reaches S's LHS.
bool op1_dep = gimple_range_ssa_p (op1)
&& (op1 == lhs_s || gori_ssa->in_chain_p (lhs_s, op1));
bool op2_dep = gimple_range_ssa_p (op2)
&& (op2 == lhs_s || gori_ssa->in_chain_p (lhs_s, op2));
if (op1_dep == op2_dep)
break;
if (op1_dep)
{
if (!op2)
ret = handler.calc_op1 (op1_range, lhs_range);
else
{
op2_range.set_range_class (TREE_TYPE (op2));
get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
op2);
ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
}
if (!ret)
break;
lhs_range = op1_range;
stmt = SSA_NAME_DEF_STMT (op1);
}
else
{
op2_range.set_range_class (TREE_TYPE (op2));
get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
if (!ret)
break;
lhs_range = op2_range;
stmt = SSA_NAME_DEF_STMT (op2);
}
// Bail if the chain leaves SBB.
if (!stmt || gimple_bb (stmt) != sbb)
break;
}
if (stmt != s)
continue;
// LHS_RANGE is now S's LHS as it is known in ORIG_BB.
value_range op1_range (TREE_TYPE (s_handler.operand1 ()));
value_range op2_range (TREE_TYPE (s_handler.operand2 ()));
get_range_query (cfun)->range_on_entry (op1_range, orig_bb,
s_handler.operand1 ());
get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
s_handler.operand2 ());
relation_kind r = s_handler.op1_op2_relation (lhs_range, op1_range,
op2_range);
if (reversed)
r = relation_swap (r);
relation_kind k = relation_intersect (result, r);
if (k != VREL_UNDEFINED)
result = k;
}
return result;
}
// Find a relation between SSA1 and SSA2 in the dominator tree starting with
// block BB
relation_kind
dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
{
relation_kind r;
unsigned v1 = SSA_NAME_VERSION (ssa1);
unsigned v2 = SSA_NAME_VERSION (ssa2);
// IF either name does not occur in a relation anywhere, there isn't one.
if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
return VREL_VARYING;
for (basic_block bb = start_bb;
bb;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
r = find_relation_block (bb->index, ssa1, ssa2);
if (r != VREL_VARYING)
return r;
}
return VREL_VARYING;
}
// Starting with basic block BB, look for the next block in the dominator
// tree which contains a relation involving NAME. There can be more than one,
// and they are returned in the class local m_near vector. The block in which
// the relations are found are returned. If no relations are found, NULL is
// returned and the m_near vector is empty.
basic_block
dom_oracle::nearest_relations (tree name, basic_block bb)
{
if (TREE_CODE (name) != SSA_NAME)
return NULL;
unsigned v = SSA_NAME_VERSION (name);
if (!bitmap_bit_p (m_relation_set, v))
return NULL;
// A relation involving NAME can only be registered in a block
// dominated by NAME's definition. Relations occurring *in* the def block
// are attached to the def block itself, so once that block has been
// examined there is nothing left to find and the walk can terminate.
basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
bool at_def = false;
m_near.truncate (0);
for (; bb && !at_def; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
at_def = (bb == def_bb);
if (bb->index >= (int) m_relations.length ())
continue;
const_bitmap bm = m_relations[bb->index].m_names;
if (!bm || !bitmap_bit_p (bm, v))
continue;
for (relation_chain *ptr = m_relations[bb->index].m_head;
ptr; ptr = ptr->m_next)
{
if (v == SSA_NAME_VERSION (ptr->op1 ())
&& !SSA_NAME_IN_FREE_LIST (ptr->op2 ()))
m_near.safe_push ({ ptr->kind (), ptr->op2 (), bb });
else if (v == SSA_NAME_VERSION (ptr->op2 ())
&& !SSA_NAME_IN_FREE_LIST (ptr->op1 ()))
m_near.safe_push ({ relation_swap (ptr->kind ()),
ptr->op1 (), bb });
}
if (!m_near.is_empty ())
return bb;
}
return NULL;
}
// Record relation K between OP1 and OP2, discovered by a search in block BB,
// so subsequent queries in BB or anything it dominates find it directly.
// Use SEARCH_AND_MERGE_RELATION rather than CREATE_RELATION_IN_BB. The pair
// may already have a record in BB from an earlier query, in which case the
// two must be intersected rather than a second record created.
void
dom_oracle::cache_relation (basic_block bb, relation_kind k, tree op1,
tree op2)
{
if (!bb || op1 == op2)
return;
// There is nothing useful to record for VARYING or UNDEFINED and
// Equivalences belong to the equivalence oracle.
if (k == VREL_VARYING || k == VREL_UNDEFINED || relation_equiv_p (k))
return;
search_and_merge_relation (bb, k, op1, op2);
}
// Begin the search for SIDE at its root ROOT, whose equivalence set is
// EQUIV, in block BB. Every name equivalent to ROOT is an equally good
// starting point, so seed them all.
void
dom_oracle::start_search (frontier_data &side, tree root, const_bitmap equiv,
basic_block bb)
{
side.m_root = root;
unsigned root_v = SSA_NAME_VERSION (root);
m_worklist.safe_push ({ VREL_EQ, root, bb, side.m_rhs });
bitmap_set_bit (side.m_visited, root_v);
side.set_known (root_v, VREL_EQ);
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi)
{
// Equivalences are maintained lazily, so ensure they are still
// valid before adding them to the frontier.
tree name = ssa_name (i);
if (i == root_v || !name || SSA_NAME_IN_FREE_LIST (name))
continue;
m_worklist.safe_push ({ VREL_EQ, name, bb, side.m_rhs });
bitmap_set_bit (side.m_visited, i);
side.set_known (i, VREL_EQ);
}
}
// SIDE's root has been shown to be related to NAME by REL. Queue NAME for
// expansion starting at block BB.
void
dom_oracle::add_to_frontier (frontier_data &side, tree name, relation_kind rel,
basic_block bb)
{
unsigned v = SSA_NAME_VERSION (name);
if (!side.visited_p (v))
{
bitmap_set_bit (side.m_visited, v);
side.set_known (v, rel);
m_worklist.safe_push ({ rel, name, bb, side.m_rhs });
return;
}
// NAME already had a relation, so intersect the two and requeue NAME if
// there is an improvement.
relation_kind curr = side.known_relation (v);
relation_kind k = relation_intersect (curr, rel);
if (k != curr && k != VREL_UNDEFINED)
{
side.set_known (v, k);
m_worklist.safe_push ({ k, name, bb, side.m_rhs });
}
}
// Expand worklist entry W, looking for a name the other side of the search
// has already reached. BB is the block the query was made in. Return true
// and set RESULT if a match was found. W is passed by value as
// add_to_frontier may realloc the vector.
bool
dom_oracle::expand_frontier (frontier_element w, basic_block bb,
relation_kind &result)
{
frontier_data &self = w.rhs ? m_rhs_search : m_lhs_search;
frontier_data &other = w.rhs ? m_lhs_search : m_rhs_search;
if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
{
fprintf (dump_file, " %s frontier expanding: ", w.rhs ? "RHS" : "LHS");
print_generic_expr (dump_file, w.name, TDF_SLIM);
fprintf (dump_file, " (rel: %d)\n", w.rel);
}
basic_block found = nearest_relations (w.name, w.bb);
if (!found)
return false;
for (unsigned i = 0; i < m_near.length (); ++i)
{
// nearest_relations sets m_near[i].rel as "w.name <rel> m_near.name",
// so composing it with "root <w.rel> w.name" gives "root <kind> next".
value_relation path (w.rel, self.m_root, w.name);
value_relation near_rel (m_near[i].rel, w.name, m_near[i].name);
if (!path.apply_transitive (near_rel))
continue;
relation_kind kind = path.kind ();
tree next = path.op2 ();
unsigned nv = SSA_NAME_VERSION (next);
// If the other side has reached NEXT it knows "other_root <rel> next",
// which composes with what is known here to relate the two roots.
if (other.visited_p (nv))
{
relation_kind k
= relation_transitive (kind,
relation_swap (other.known_relation (nv)));
// If the result is not VARYING, we have a match.
if (k != VREL_VARYING)
{
result = w.rhs ? relation_swap (k) : k;
if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
{
fprintf (dump_file, " %s frontier found connection at: ",
w.rhs ? "RHS" : "LHS");
print_generic_expr (dump_file, next, TDF_SLIM);
fprintf (dump_file, ", combined relation: ");
print_relation (dump_file, result);
fputc ('\n', dump_file);
}
return true;
}
}
// Add to this side's frontier if it has not visited NEXT yet.
add_to_frontier (self, next, kind, bb);
}
// Keep searching for NAME in the dominator tree. Do not search past
// the def block as that is pointless. Do search the def block however
// as relations within the body of the block are stored there.
// Use whatever the latest known relation value is.
basic_block idom = get_immediate_dominator (CDI_DOMINATORS, found);
if (idom && gimple_bb (SSA_NAME_DEF_STMT (w.name)) != found)
m_worklist.safe_push ({ self.known_relation (SSA_NAME_VERSION (w.name)),
w.name, idom, w.rhs });
return false;
}
// Search for a relation between LHS and RHS in block BB or one of its
// dominators, expanding a frontier from both names until the two meet.
// LHS_EQUIV and RHS_EQUIV are the equivalence sets of LHS and RHS.
relation_kind
dom_oracle::relation_search (basic_block bb, tree lhs, const_bitmap lhs_equiv,
tree rhs, const_bitmap rhs_equiv)
{
// Initialize both search frontiers.
start_search (m_lhs_search, lhs, lhs_equiv, bb);
start_search (m_rhs_search, rhs, rhs_equiv, bb);
relation_kind result = VREL_VARYING;
// Each expansion walks the dominator tree looking for the next block with
// a relation.
unsigned budget = param_transitive_relations_work_bound;
if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
{
fprintf (dump_file, "Bidirectional relation search: ");
print_generic_expr (dump_file, lhs, TDF_SLIM);
fprintf (dump_file, " vs ");
print_generic_expr (dump_file, rhs, TDF_SLIM);
fprintf (dump_file, " in bb%d\n", bb ? bb->index : -1);
}
// Expand until exhausted or until a connection is found.
while (m_wl_ix < m_worklist.length ())
{
if (!budget--)
{
if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
fprintf (dump_file, " search budget exhausted\n");
break;
}
if (expand_frontier (m_worklist[m_wl_ix++], bb, result))
break;
}
// Clear search state for reuse.
m_worklist.truncate (0);
m_wl_ix = 0;
m_lhs_search.clear_search ();
m_rhs_search.clear_search ();
// Check to see if any new relations can be formed by recomputing an
// expression using LHS and RHS.
// This call must come after the worklists are cleared above. The call
// may invoke range_on_entry which may trigger another relation search,
// and thus the current search must be cleared before making this call.
relation_kind rel = recomputed_relation (bb, lhs, rhs);
if (rel != VREL_VARYING)
{
rel = relation_intersect (result, rel);
if (rel != VREL_UNDEFINED)
result = rel;
}
// Record whatever was found so the next query for this pair is a direct
// lookup rather than another search.
cache_relation (bb, result, lhs, rhs);
if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION)
&& result != VREL_VARYING)
{
fprintf (dump_file, " relation_search returning: ");
print_generic_expr (dump_file, lhs, TDF_SLIM);
print_relation (dump_file, result);
print_generic_expr (dump_file, rhs, TDF_SLIM);
fprintf (dump_file, "\n");
}
return result;
}
// Query if there is a relation between SSA1 and SS2 in block BB or a
// dominator of BB
relation_kind
dom_oracle::query (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 VREL_EQ;
// If v1 or v2 do not have any relations or equivalences, a partial
// equivalence is the only possibility.
if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
|| (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
return partial_equiv (ssa1, ssa2);
// Check for equivalence first. They must be in each equivalency set.
const_bitmap equiv1 = equiv_set (ssa1, bb);
const_bitmap equiv2 = equiv_set (ssa2, bb);
if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
return VREL_EQ;
// A statement such as c = a & 0xff makes a partial equivalence between
// c and a, and an ordinary comparison can then relate the same pair.
// If both exist, prefer the relation, so look for that first.
kind = relation_search (bb, ssa1, equiv1, ssa2, equiv2);
// Finally look for partial equivalences.
if (kind == VREL_VARYING)
kind = partial_equiv (ssa1, ssa2);
return kind;
}
// Dump all the relations in block BB to file F.
void
dom_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;
value_relation vr;
FOR_EACH_RELATION_BB (this, bb, vr)
{
fprintf (f, "Relational : ");
vr.dump (f);
fprintf (f, "\n");
}
}
// Dump all the relations known to file F.
void
dom_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);
}
path_oracle::path_oracle (relation_oracle *oracle)
{
set_root_oracle (oracle);
bitmap_obstack_initialize (&m_bitmaps);
obstack_init (&m_chain_obstack);
// Initialize header records.
m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
m_equiv.m_bb = NULL;
m_equiv.m_next = NULL;
m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
m_relations.m_head = NULL;
m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
}
path_oracle::~path_oracle ()
{
obstack_free (&m_chain_obstack, NULL);
bitmap_obstack_release (&m_bitmaps);
}
// Clear any range info and relations associated with NAME.
void
path_oracle::clear (tree name)
{
if (m_root)
m_root->clear (name);
m_relations.clear (name);
unsigned v = SSA_NAME_VERSION (name);
equiv_chain *ptr = m_equiv.find (v);
if (ptr)
bitmap_clear_bit (ptr->m_names, v);
}
// Return the equiv set for SSA, and if there isn't one, check for equivs
// starting in block BB.
const_bitmap
path_oracle::equiv_set (tree ssa, basic_block bb)
{
// Check the list first.
equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
if (ptr)
return ptr->m_names;
// Otherwise defer to the root oracle.
if (m_root)
return m_root->equiv_set (ssa, bb);
// Allocate a throw away bitmap if there isn't a root oracle.
bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
return tmp;
}
// Register an equivalence between SSA1 and SSA2 resolving unknowns from
// block BB. Return false if no new equivalence was added.
bool
path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
{
const_bitmap equiv_1 = equiv_set (ssa1, bb);
const_bitmap equiv_2 = equiv_set (ssa2, bb);
// Check if they are the same set, if so, we're done.
if (bitmap_equal_p (equiv_1, equiv_2))
return false;
// Don't mess around, simply create a new record and insert it first.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
valid_equivs (b, equiv_1, bb);
valid_equivs (b, equiv_2, bb);
equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
sizeof (equiv_chain));
ptr->m_names = b;
ptr->m_bb = NULL;
ptr->m_next = m_equiv.m_next;
m_equiv.m_next = ptr;
bitmap_ior_into (m_equiv.m_names, b);
return true;
}
// Register killing definition of an SSA_NAME.
void
path_oracle::killing_def (tree ssa)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Registering killing_def (path_oracle) ");
print_generic_expr (dump_file, ssa, TDF_SLIM);
fprintf (dump_file, "\n");
}
unsigned v = SSA_NAME_VERSION (ssa);
bitmap_set_bit (m_killed_defs, v);
bitmap_set_bit (m_equiv.m_names, v);
// Now add an equivalency with itself so we don't look to the root oracle.
bitmap b = BITMAP_ALLOC (&m_bitmaps);
bitmap_set_bit (b, v);
equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
sizeof (equiv_chain));
ptr->m_names = b;
ptr->m_bb = NULL;
ptr->m_next = m_equiv.m_next;
m_equiv.m_next = ptr;
// Walk the relation list and remove SSA from any relations.
if (!bitmap_bit_p (m_relations.m_names, v))
return;
bitmap_clear_bit (m_relations.m_names, v);
relation_chain **prev = &(m_relations.m_head);
relation_chain *next = NULL;
for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
{
gcc_checking_assert (*prev == ptr);
next = ptr->m_next;
if (SSA_NAME_VERSION (ptr->op1 ()) == v
|| SSA_NAME_VERSION (ptr->op2 ()) == v)
*prev = ptr->m_next;
else
prev = &(ptr->m_next);
}
}
// Register relation K between SSA1 and SSA2, resolving unknowns by
// querying from BB. Return false if no new relation is registered.
bool
path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
{
// If the 2 ssa_names are the same, do nothing. An equivalence is implied,
// and no other relation makes sense.
if (ssa1 == ssa2)
return false;
// Partial equivalences are tracked in the root equivalence oracle rather
// than on the path. Registering a partial equivalence in the path would
// cause normal relations to collapse to VARYING.
if (relation_partial_equiv_p (k))
return false;
relation_kind curr = query (bb, ssa1, ssa2);
// Likewise, a partial equivalency result should not be combined with K
// or the result drops to VARYING.
if (curr != VREL_VARYING && !relation_partial_equiv_p (curr))
k = relation_intersect (curr, k);
// Do not register an impossible relation.
if (k == VREL_UNDEFINED)
return false;
bool ret;
if (k == VREL_EQ)
ret = register_equiv (bb, ssa1, ssa2);
else
{
bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
sizeof (relation_chain));
ptr->set_relation (k, ssa1, ssa2);
ptr->m_next = m_relations.m_head;
m_relations.m_head = ptr;
ret = true;
}
if (ret && dump_file && (dump_flags & TDF_DETAILS))
{
value_relation vr (k, ssa1, ssa2);
fprintf (dump_file, " Registering value_relation (path_oracle) ");
vr.dump (dump_file);
fprintf (dump_file, " (root: bb%d)\n", bb->index);
}
return ret;
}
// Query for a relationship between equiv set B1 and B2, resolving unknowns
// starting at block BB.
relation_kind
path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
{
if (bitmap_equal_p (b1, b2))
return VREL_EQ;
relation_kind k = m_relations.find_relation (b1, b2);
// Do not look at the root oracle for names that have been killed
// along the path.
if (bitmap_intersect_p (m_killed_defs, b1)
|| bitmap_intersect_p (m_killed_defs, b2))
return k;
// Query the root oracle for relations with path local equivalencies.
if (k == VREL_VARYING && m_root)
k = m_root->query (bb, b1, b2);
return k;
}
// Query for a relationship between SSA1 and SSA2, resolving unknowns
// starting at block BB.
relation_kind
path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
{
unsigned v1 = SSA_NAME_VERSION (ssa1);
unsigned v2 = SSA_NAME_VERSION (ssa2);
if (v1 == v2)
return VREL_EQ;
const_bitmap equiv_1 = equiv_set (ssa1, bb);
const_bitmap equiv_2 = equiv_set (ssa2, bb);
if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
return VREL_EQ;
relation_kind rel = query (bb, equiv_1, equiv_2);
// If the path relation query fails, check for relations in the root oracle.
if (rel == VREL_VARYING && m_root)
rel = m_root->query (bb, ssa1, ssa2);
return rel;
}
// Reset any relations registered on this path. ORACLE is the root
// oracle to use.
void
path_oracle::reset_path (relation_oracle *oracle)
{
set_root_oracle (oracle);
m_equiv.m_next = NULL;
bitmap_clear (m_equiv.m_names);
m_relations.m_head = NULL;
bitmap_clear (m_relations.m_names);
bitmap_clear (m_killed_defs);
}
// Dump relation in basic block... Do nothing here.
void
path_oracle::dump (FILE *, basic_block) const
{
}
// Dump the relations and equivalencies found in the path.
void
path_oracle::dump (FILE *f) const
{
equiv_chain *ptr = m_equiv.m_next;
relation_chain *ptr2 = m_relations.m_head;
if (ptr || ptr2)
fprintf (f, "\npath_oracle:\n");
for (; ptr; ptr = ptr->m_next)
ptr->dump (f);
for (; ptr2; ptr2 = ptr2->m_next)
{
fprintf (f, "Relational : ");
ptr2->dump (f);
fprintf (f, "\n");
}
}
// ------------------------------------------------------------------------
// EQUIV iterator. Although we have bitmap iterators, don't expose that it
// is currently a bitmap. Use an export iterator to hide future changes.
// Construct a basic iterator over an equivalence bitmap.
equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
basic_block bb, tree name,
bool full, bool partial)
{
m_name = name;
m_oracle = oracle;
m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
m_bm = NULL;
if (full)
m_bm = oracle->equiv_set (name, bb);
if (!m_bm && m_pe)
m_bm = m_pe->members;
if (m_bm)
bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
}
// Move to the next export bitmap spot.
void
equiv_relation_iterator::next ()
{
bmp_iter_next (&m_bi, &m_y);
}
// Fetch the name of the next export in the export list. Return NULL if
// iteration is done.
tree
equiv_relation_iterator::get_name (relation_kind *rel)
{
if (!m_bm)
return NULL_TREE;
while (bmp_iter_set (&m_bi, &m_y))
{
// Do not return self.
tree t = ssa_name (m_y);
if (t && t != m_name)
{
relation_kind k = VREL_EQ;
if (m_pe && m_bm == m_pe->members)
{
const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
if (equiv_pe && equiv_pe->members == m_pe->members)
k = pe_min (m_pe->code, equiv_pe->code);
else
k = VREL_VARYING;
}
if (relation_equiv_p (k))
{
if (rel)
*rel = k;
return t;
}
}
next ();
}
// Process partial equivs after full equivs if both were requested.
if (m_pe && m_bm != m_pe->members)
{
m_bm = m_pe->members;
if (m_bm)
{
// Recursively call back to process First PE.
bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
return get_name (rel);
}
}
return NULL_TREE;
}
#if CHECKING_P
#include "selftest.h"
namespace selftest
{
void
relation_tests ()
{
// rr_*_table tables use unsigned char rather than relation_kind.
ASSERT_LT (VREL_LAST, UCHAR_MAX);
for (relation_kind r1 = VREL_VARYING; r1 < VREL_LAST;
r1 = relation_kind (r1 + 1))
{
// Swapping the operands twice is a no-op.
ASSERT_EQ (relation_swap (relation_swap (r1)), r1);
// VARYING intersect X is X.
// UNDEFINED intersect X is UNDEFINED.
ASSERT_EQ (relation_intersect (VREL_VARYING, r1), r1);
ASSERT_EQ (relation_intersect (VREL_UNDEFINED, r1), VREL_UNDEFINED);
// UNDEFINED union X is X.
// VARYING union X is VARYING.
ASSERT_EQ (relation_union (VREL_UNDEFINED, r1), r1);
ASSERT_EQ (relation_union (VREL_VARYING, r1), VREL_VARYING);
// Verify commutativity of relation_intersect and relation_union.
for (relation_kind r2 = VREL_VARYING; r2 < VREL_LAST;
r2 = relation_kind (r2 + 1))
{
ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
}
}
// Verify partial equivalence properties.
for (relation_kind r1 = VREL_PE8; r1 <= VREL_PE64;
r1 = relation_kind (r1 + 1))
{
ASSERT_EQ (relation_swap (r1), r1);
ASSERT_EQ (relation_intersect (VREL_EQ, r1), VREL_EQ);
ASSERT_EQ (relation_union (VREL_EQ, r1), r1);
ASSERT_EQ (relation_transitive (VREL_EQ, r1), r1);
ASSERT_EQ (relation_transitive (r1, VREL_EQ), r1);
for (relation_kind r2 = VREL_PE8; r2 <= VREL_PE64;
r2 = relation_kind (r2 + 1))
{
ASSERT_EQ (relation_intersect (r1, r2), MAX (r1, r2));
ASSERT_EQ (relation_union (r1, r2), pe_min (r1, r2));
ASSERT_EQ (relation_transitive (r1, r2), pe_min (r1, r2));
}
}
}
} // namespace selftest
#endif // CHECKING_P