blob: 027d7416163c039186f5b2acae2817a35602c734 [file] [log] [blame]
/* Header file for the value range relational processing.
Copyright (C) 2020-2022 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <>
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
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
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
<>. */
// This file provides access to a relation oracle which can be used to
// maintain and query relations and equivalences between SSA_NAMES.
// The general range_query object provided in value-query.h provides
// access to an oracle, if one is available, via the oracle() method.
// Thre are also a couple of access routines provided, which even if there is
// no oracle, will return the default VREL_VARYING no relation.
// Typically, when a ranger object is active, there will be an oracle, and
// any information available can be directly queried. Ranger also sets and
// utilizes the relation information to enhance it's range calculations, this
// is totally transparent to the client, and they are free to make queries.
// relation_kind is a new enum which represents the different relations,
// often with a direct mapping to treee codes. ie VREL_EQ is equivalent to
// A query is made requesting the relation between SSA1 and SSA@ in a basic
// block, or on an edge, the possible return values are:
// VREL_EQ, VREL_NE, VREL_LT, VREL_LE, VREL_GT, and VREL_GE mean the same.
// VREL_VARYING : No relation between the 2 names.
// VREL_UNDEFINED : Impossible relation (ie, A < B && A > B)
// The oracle maintains VREL_EQ relations with equivalency sets, so if a
// relation comes back VREL_EQ, it is also possible to query the set of
// equivlaencies. These are basically bitmaps over ssa_names. An iterator is
// provided later for this activity.
// Relations are maintained via the dominace trees and are optimized assuming
// they are registered in dominance order. When a new relation is added, it
// is intersected with whatever existing relation exists in the dominance tree
// and registered at the specified block.
// These codes are arranged such that VREL_VARYING is the first code, and all
// the rest are contiguous.
typedef enum relation_kind_t
VREL_VARYING = 0, // No known relation, AKA varying.
VREL_UNDEFINED, // Impossible relation, ie (r1 < r2) && (r2 > r1)
VREL_LT, // r1 < r2
VREL_LE, // r1 <= r2
VREL_GT, // r1 > r2
VREL_GE, // r1 >= r2
VREL_EQ, // 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
VREL_LAST // terminate, not a real relation.
} relation_kind;
// General relation kind transformations.
relation_kind relation_union (relation_kind r1, relation_kind r2);
relation_kind relation_intersect (relation_kind r1, relation_kind r2);
relation_kind relation_negate (relation_kind r);
relation_kind relation_swap (relation_kind r);
inline bool relation_lt_le_gt_ge_p (relation_kind r)
{ 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
virtual ~relation_oracle () { }
// register a relation between 2 ssa names at a stmt.
void register_stmt (gimple *, relation_kind, tree, tree);
// register a relation between 2 ssa names on an edge.
void register_edge (edge, relation_kind, tree, tree);
// 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.
virtual relation_kind query_relation (basic_block, tree, tree) = 0;
relation_kind validate_relation (relation_kind, tree, tree);
relation_kind validate_relation (relation_kind, vrange &, vrange &);
virtual void dump (FILE *, basic_block) const = 0;
virtual void dump (FILE *) const = 0;
void debug () const;
friend class equiv_relation_iterator;
// Return equivalency set for an SSA name in a basic block.
virtual const_bitmap equiv_set (tree, basic_block) = 0;
// Return partial equivalency record for an SSA name.
virtual const class pe_slice *partial_equiv_set (tree) { return NULL; }
void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
// Query for a relation between two equivalency sets in a basic block.
virtual relation_kind query_relation (basic_block, const_bitmap,
const_bitmap) = 0;
friend class path_oracle;
// This class represents an equivalency set, and contains a link to the next
// one in the list to be searched.
class equiv_chain
bitmap m_names; // ssa-names in equiv set.
basic_block m_bb; // Block this belongs to
equiv_chain *m_next; // Next in block list.
void dump (FILE *f) const; // Show names in this list.
equiv_chain *find (unsigned ssa);
class pe_slice
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,
// and the equivalence is simply applied to that succesor block.
class equiv_oracle : public relation_oracle
equiv_oracle ();
~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)
void dump (FILE *f, basic_block bb) const override;
void dump (FILE *f) const override;
bitmap_obstack m_bitmaps;
struct obstack m_chain_obstack;
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;
equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
equiv_chain *equiv_2);
void register_initial_def (tree ssa);
void add_equiv_to_block (basic_block bb, bitmap equiv);
// Summary block header for relations.
class relation_chain_head
bitmap m_names; // ssa_names with relations in this block.
class relation_chain *m_head; // List of relations in block.
int m_num_relations; // Number of relations in block.
relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
// A relation oracle maintains a set of relations between ssa_names using the
// dominator tree structures. Equivalencies are considered a subset of
// a general relation and maintained by an equivalence oracle by transparently
// passing any EQ_EXPR relations to it.
// Relations are handled at the basic block level. All relations apply to
// an entire block, and are thus kept in a summary index by block.
// Similar to the equivalence oracle, edges are handled by applying the
// relation to the destination block of the edge, but ONLY if that block
// has a single successor. For now.
class dom_oracle : public equiv_oracle
dom_oracle ();
~dom_oracle ();
void register_relation (basic_block bb, relation_kind k, tree op1, tree op2)
final override;
relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2)
final override;
relation_kind query_relation (basic_block bb, const_bitmap b1,
const_bitmap b2) final override;
void dump (FILE *f, basic_block bb) const final override;
void dump (FILE *f) const final override;
bitmap m_tmp, m_tmp2;
bitmap m_relation_set; // Index by ssa-name. True if a relation exists
vec <relation_chain_head> m_relations; // Index by BB, list of relations.
relation_kind find_relation_block (unsigned bb, const_bitmap b1,
const_bitmap b2) const;
relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
relation_chain **obj = NULL) const;
relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
tree op2);
void register_transitives (basic_block, const class value_relation &);
// A path_oracle implements relations in a list. The only sense of ordering
// is the latest registered relation is the first found during a search.
// It can be constructed with an optional "root" oracle which will be used
// to look up any relations not found in the list.
// This allows the client to walk paths starting at some block and register
// and query relations along that path, ignoring other edges.
// For registering a relation, a query if made of the root oracle if there is
// any known relationship at block BB, and it is combined with this new
// relation and entered in the list.
// Queries are resolved by looking first in the list, and only if nothing is
// found is the root oracle queried at block BB.
// reset_path is used to clear all locally registered paths to initial state.
class path_oracle : public relation_oracle
path_oracle (relation_oracle *oracle = NULL);
~path_oracle ();
const_bitmap equiv_set (tree, basic_block) final override;
void register_relation (basic_block, relation_kind, tree, tree) final override;
void killing_def (tree);
relation_kind query_relation (basic_block, tree, tree) final override;
relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
final override;
void reset_path (relation_oracle *oracle = NULL);
void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
void dump (FILE *, basic_block) const final override;
void dump (FILE *) const final override;
void register_equiv (basic_block bb, tree ssa1, tree ssa2);
equiv_chain m_equiv;
relation_chain_head m_relations;
relation_oracle *m_root;
bitmap m_killed_defs;
bitmap_obstack m_bitmaps;
struct obstack m_chain_obstack;
// Used to assist with iterating over the equivalence list.
class equiv_relation_iterator {
equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name,
bool full = true, bool partial = false);
void next ();
tree get_name (relation_kind *rel = NULL);
relation_oracle *m_oracle;
const_bitmap m_bm;
const pe_slice *m_pe;
bitmap_iterator m_bi;
unsigned m_y;
tree m_name;
#define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \
for (equiv_relation_iterator iter (oracle, bb, name, true, false); \
((equiv_name) = iter.get_name ()); \ ())
#define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \
for (equiv_relation_iterator iter (oracle, bb, name, false, true); \
((equiv_name) = iter.get_name (&equiv_rel)); \ ())
#define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \
equiv_rel) \
for (equiv_relation_iterator iter (oracle, bb, name, true, true); \
((equiv_name) = iter.get_name (&equiv_rel)); \ ())
// -----------------------------------------------------------------------
// Range-ops deals with a LHS and 2 operands. A relation trio is a set of
// 3 potential relations packed into a single unsigned value.
// 1 - LHS relation OP1
// 2 - LHS relation OP2
// 3 - OP1 relation OP2
// VREL_VARYING is a value of 0, and is the default for each position.
class relation_trio
relation_trio ();
relation_trio (relation_kind lhs_op1, relation_kind lhs_op2,
relation_kind op1_op2);
relation_kind lhs_op1 ();
relation_kind lhs_op2 ();
relation_kind op1_op2 ();
relation_trio swap_op1_op2 ();
static relation_trio lhs_op1 (relation_kind k);
static relation_trio lhs_op2 (relation_kind k);
static relation_trio op1_op2 (relation_kind k);
unsigned m_val;
// Default VREL_VARYING for all 3 relations.
#define TRIO_VARYING relation_trio ()
#define TRIO_SHIFT 4
#define TRIO_MASK 0x000F
// These 3 classes are shortcuts for when a caller has a single relation to
// pass as a trio, it can simply construct the appropriate one. The other
// unspecified realtions will be VREL_VARYING.
inline relation_trio::relation_trio ()
m_val = 0;
inline relation_trio::relation_trio (relation_kind lhs_op1,
relation_kind lhs_op2,
relation_kind op1_op2)
unsigned i1 = (unsigned) lhs_op1;
unsigned i2 = ((unsigned) lhs_op2) << TRIO_SHIFT;
unsigned i3 = ((unsigned) op1_op2) << (TRIO_SHIFT * 2);
m_val = i1 | i2 | i3;
inline relation_trio
relation_trio::lhs_op1 (relation_kind k)
return relation_trio (k, VREL_VARYING, VREL_VARYING);
inline relation_trio
relation_trio::lhs_op2 (relation_kind k)
return relation_trio (VREL_VARYING, k, VREL_VARYING);
inline relation_trio
relation_trio::op1_op2 (relation_kind k)
return relation_trio (VREL_VARYING, VREL_VARYING, k);
inline relation_kind
relation_trio::lhs_op1 ()
return (relation_kind) (m_val & TRIO_MASK);
inline relation_kind
relation_trio::lhs_op2 ()
return (relation_kind) ((m_val >> TRIO_SHIFT) & TRIO_MASK);
inline relation_kind
relation_trio::op1_op2 ()
return (relation_kind) ((m_val >> (TRIO_SHIFT * 2)) & TRIO_MASK);
inline relation_trio
relation_trio::swap_op1_op2 ()
return relation_trio (lhs_op2 (), lhs_op1 (), relation_swap (op1_op2 ()));
// -----------------------------------------------------------------------
// The value-relation class is used to encapsulate the represention of an
// individual relation between 2 ssa-names, and to facilitate operating on
// the relation.
class value_relation
value_relation ();
value_relation (relation_kind kind, tree n1, tree n2);
void set_relation (relation_kind kind, tree n1, tree n2);
inline relation_kind kind () const { return related; }
inline tree op1 () const { return name1; }
inline tree op2 () const { return name2; }
bool union_ (value_relation &p);
bool intersect (value_relation &p);
void negate ();
bool apply_transitive (const value_relation &rel);
void dump (FILE *f) const;
relation_kind related;
tree name1, name2;
// Set relation R between ssa_name N1 and N2.
inline void
value_relation::set_relation (relation_kind r, tree n1, tree n2)
gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
&& TREE_CODE (n2) == SSA_NAME);
if (n1 == n2)
related = VREL_VARYING;
name1 = NULL_TREE;
name2 = NULL_TREE;
related = r;
name1 = n1;
name2 = n2;
// Default constructor.
value_relation::value_relation ()
related = VREL_VARYING;
name1 = NULL_TREE;
name2 = NULL_TREE;
// Constructor for relation R between SSA version N1 nd N2.
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;
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;
// 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);