GCC Middle and Back End API Reference
tree-ssa-sccvn.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  vn_pval
 
struct  vn_nary_op_s
 
struct  vn_phi_s
 
struct  vn_reference_op_struct
 
struct  vn_reference_s
 
struct  vn_constant_s
 
struct  vn_avail
 
struct  vn_ssa_aux
 

Typedefs

typedef struct vn_nary_op_svn_nary_op_t
 
typedef const struct vn_nary_op_sconst_vn_nary_op_t
 
typedef struct vn_phi_svn_phi_t
 
typedef const struct vn_phi_sconst_vn_phi_t
 
typedef struct vn_reference_op_struct vn_reference_op_s
 
typedef vn_reference_op_svn_reference_op_t
 
typedef const vn_reference_op_sconst_vn_reference_op_t
 
typedef struct vn_reference_svn_reference_t
 
typedef const struct vn_reference_sconst_vn_reference_t
 
typedef struct vn_constant_svn_constant_t
 
typedef struct vn_ssa_auxvn_ssa_aux_t
 

Enumerations

enum  vn_kind {
  VN_NONE , VN_CONSTANT , VN_NARY , VN_REFERENCE ,
  VN_PHI
}
 
enum  vn_lookup_kind { VN_NOWALK , VN_WALK , VN_WALKREWRITE }
 

Functions

bool expressions_equal_p (tree, tree, bool=true)
 
size_t sizeof_vn_nary_op (unsigned int length)
 
unsigned vn_ref_op_align_unit (vn_reference_op_t op)
 
enum vn_kind vn_get_stmt_kind (gimple *)
 
hashval_t vn_hash_type (tree type)
 
hashval_t vn_hash_constant_with_type (tree constant)
 
bool vn_constant_eq_with_type (tree c1, tree c2)
 
bool has_VN_INFO (tree)
 
vn_ssa_aux_t VN_INFO (tree)
 
tree vn_get_expr_for (tree)
 
void scc_vn_restore_ssa_info (void)
 
vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, struct obstack *)
 
unsigned int vn_nary_length_from_stmt (gimple *)
 
void init_vn_nary_op_from_stmt (vn_nary_op_t, gassign *)
 
hashval_t vn_nary_op_compute_hash (const vn_nary_op_t)
 
tree vn_nary_op_lookup_stmt (gimple *, vn_nary_op_t *)
 
tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code, tree, tree *, vn_nary_op_t *)
 
vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code, tree, tree *, tree, unsigned int)
 
bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, alias_set_type, tree, const vec< vn_reference_op_s > &)
 
vec< vn_reference_op_svn_reference_operands_for_lookup (tree)
 
tree vn_reference_lookup_pieces (tree, alias_set_type, alias_set_type, tree, vec< vn_reference_op_s >, vn_reference_t *, vn_lookup_kind)
 
tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *, bool, tree *=NULL, tree=NULL_TREE, bool=false)
 
void vn_reference_lookup_call (gcall *, vn_reference_t *, vn_reference_t)
 
vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, alias_set_type, poly_int64, poly_int64, tree, vec< vn_reference_op_s >, tree, unsigned int)
 
void print_vn_reference_ops (FILE *, const vec< vn_reference_op_s >)
 
bool vn_nary_op_eq (const_vn_nary_op_t const vno1, const_vn_nary_op_t const vno2)
 
bool vn_nary_may_trap (vn_nary_op_t)
 
bool vn_reference_may_trap (vn_reference_t)
 
bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const)
 
unsigned int get_max_value_id (void)
 
unsigned int get_max_constant_value_id (void)
 
unsigned int get_next_value_id (void)
 
unsigned int get_next_constant_value_id (void)
 
unsigned int get_constant_value_id (tree)
 
unsigned int get_or_alloc_constant_value_id (tree)
 
bool value_id_constant_p (unsigned int v)
 
tree fully_constant_vn_reference_p (vn_reference_t)
 
tree vn_nary_simplify (vn_nary_op_t)
 
unsigned do_rpo_vn (function *, edge, bitmap, bool=false, bool=true, bool=false, vn_lookup_kind=VN_WALKREWRITE)
 
void run_rpo_vn (vn_lookup_kind)
 
unsigned eliminate_with_rpo_vn (bitmap)
 
void free_rpo_vn (void)
 

Variables

tree VN_TOP
 
tree(* vn_valueize )(tree)
 
basic_block vn_context_bb
 

Typedef Documentation

◆ const_vn_nary_op_t

◆ const_vn_phi_t

◆ const_vn_reference_op_t

◆ const_vn_reference_t

◆ vn_constant_t

◆ vn_nary_op_t

N-ary operations in the hashtable consist of length operands, an
opcode, and a type.  Result is the value number of the operation,
and hashcode is stored to avoid having to calculate it
repeatedly.   

◆ vn_phi_t

Phi nodes in the hashtable consist of their non-VN_TOP phi
arguments, and the basic block the phi is in. Result is the value
number of the operation, and hashcode is stored to avoid having to
calculate it repeatedly.  Phi nodes not in the same block are never
considered equivalent.   

◆ vn_reference_op_s

Reference operands only exist in reference operations structures.
They consist of an opcode, type, and some number of operands.  For
a given opcode, some, all, or none of the operands may be used.
The operands are there to store the information that makes up the
portion of the addressing calculation that opcode performs.   

◆ vn_reference_op_t

◆ vn_reference_t

A reference operation in the hashtable is representation as
the vuse, representing the memory state at the time of
the operation, and a collection of operands that make up the
addressing calculation.  If two vn_reference_t's have the same set
of operands, they access the same memory location. We also store
the resulting value number, and the hashcode.   

◆ vn_ssa_aux_t

Enumeration Type Documentation

◆ vn_kind

Enumerator
VN_NONE 
VN_CONSTANT 
VN_NARY 
VN_REFERENCE 
VN_PHI 

◆ vn_lookup_kind

Enumerator
VN_NOWALK 
VN_WALK 
VN_WALKREWRITE 

Function Documentation

◆ alloc_vn_nary_op_noinit()

vn_nary_op_t alloc_vn_nary_op_noinit ( unsigned int length,
struct obstack * stack )
Allocate a vn_nary_op_t with LENGTH operands on STACK.   

References ggc_alloc(), and sizeof_vn_nary_op().

Referenced by alloc_vn_nary_op(), get_or_alloc_expr_for_nary(), VN_INFO(), and vn_nary_build_or_lookup_1().

◆ ao_ref_init_from_vn_reference()

◆ do_rpo_vn()

unsigned do_rpo_vn ( function * fn,
edge entry,
bitmap exit_bbs,
bool iterate,
bool eliminate,
bool skip_entry_phis,
vn_lookup_kind kind )
Region-based entry for RPO VN.  Performs value-numbering and elimination
on the SEME region specified by ENTRY and EXIT_BBS.  If ENTRY is not
the only edge into the region at ENTRY->dest PHI nodes in ENTRY->dest
are not considered.
If ITERATE is true then treat backedges optimistically as not
executed and iterate.  If ELIMINATE is true then perform
elimination, otherwise leave that to the caller.
If SKIP_ENTRY_PHIS is true then force PHI nodes in ENTRY->dest to VARYING.
KIND specifies the amount of work done for handling memory operations.   

References do_rpo_vn_1(), free_rpo_vn(), ggc_alloc(), and todo.

Referenced by execute_early_warn_uninitialized(), tree_if_conversion(), tree_loop_unroll_and_jam(), and tree_unroll_loops_completely().

◆ eliminate_with_rpo_vn()

unsigned eliminate_with_rpo_vn ( bitmap inserted_exprs)
Eliminate fully redundant computations.   

References CDI_DOMINATORS, cfun, ggc_alloc(), inserted_exprs, and rpo_avail.

Referenced by do_rpo_vn_1().

◆ expressions_equal_p()

bool expressions_equal_p ( tree e1,
tree e2,
bool match_vn_top_optimistically )
Tree SCC value numbering
Copyright (C) 2007-2024 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, 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/>.   
In tree-ssa-sccvn.cc   
Compare two expressions E1 and E2 and return true if they are equal.
If match_vn_top_optimistically is true then VN_TOP is equal to anything,
otherwise VN_TOP only matches VN_TOP.   

References ggc_alloc(), OEP_PURE_SAME, operand_equal_p(), TREE_CODE, and VN_TOP.

Referenced by cond_stmts_equal_p(), visit_phi(), visit_reference_op_store(), vn_constant_eq_with_type(), vn_nary_op_eq(), vn_nary_op_insert_into(), vn_phi_eq(), vn_reference_eq(), and vn_reference_op_eq().

◆ free_rpo_vn()

◆ fully_constant_vn_reference_p()

◆ get_constant_value_id()

unsigned int get_constant_value_id ( tree constant)
Lookup a value id for CONSTANT and return it.  If it does not
exist returns 0.   

References vn_constant_s::constant, constant_to_value_id, ggc_alloc(), and vn_hash_constant_with_type().

◆ get_max_constant_value_id()

unsigned int get_max_constant_value_id ( void )
Return the maximum constant value id we have ever seen.   

References next_constant_value_id.

Referenced by init_pre().

◆ get_max_value_id()

unsigned int get_max_value_id ( void )
Return the maximum value id we have ever seen.   

References next_value_id.

Referenced by init_pre().

◆ get_next_constant_value_id()

unsigned int get_next_constant_value_id ( void )
Return the next unique value id for constants.   

References gcc_checking_assert, and next_constant_value_id.

Referenced by get_or_alloc_constant_value_id().

◆ get_next_value_id()

◆ get_or_alloc_constant_value_id()

unsigned int get_or_alloc_constant_value_id ( tree constant)
Lookup a value id for CONSTANT, and if it does not exist, create a
new one and return it.  If it does exist, return it.   

References vn_constant_s::constant, constant_to_value_id, get_next_constant_value_id(), ggc_alloc(), and vn_hash_constant_with_type().

Referenced by get_or_alloc_expr_for_constant(), run_rpo_vn(), set_value_id_for_result(), vn_reference_insert(), and vn_reference_lookup_or_insert_for_pieces().

◆ has_VN_INFO()

bool has_VN_INFO ( tree name)
Return the value numbering info for an SSA_NAME.   
Return whether there is value numbering information for a given SSA name.   

References SSA_NAME_VERSION, and vn_ssa_aux_hash.

Referenced by eliminate_dom_walker::eliminate_stmt(), and tail_merge_valueize().

◆ init_vn_nary_op_from_stmt()

◆ print_vn_reference_ops()

void print_vn_reference_ops ( FILE * outfile,
const vec< vn_reference_op_s > ops )

◆ run_rpo_vn()

◆ scc_vn_restore_ssa_info()

void scc_vn_restore_ssa_info ( void )

◆ sizeof_vn_nary_op()

size_t sizeof_vn_nary_op ( unsigned int length)
inline

◆ value_id_constant_p()

◆ vn_constant_eq_with_type()

bool vn_constant_eq_with_type ( tree c1,
tree c2 )
inline
Compare the constants C1 and C2 with distinguishing type incompatible
constants in the types_compatible_p sense.   

References expressions_equal_p(), ggc_alloc(), TREE_TYPE, and types_compatible_p().

Referenced by pre_expr_d::equal(), and vn_constant_hasher::equal().

◆ vn_get_expr_for()

tree vn_get_expr_for ( tree )

◆ vn_get_stmt_kind()

◆ vn_hash_constant_with_type()

hashval_t vn_hash_constant_with_type ( tree constant)
inline
Hash the constant CONSTANT with distinguishing type incompatible
constants in the types_compatible_p sense.   

References inchash::add_expr(), ggc_alloc(), TREE_TYPE, and vn_hash_type().

Referenced by get_constant_value_id(), get_or_alloc_constant_value_id(), and pre_expr_d::hash().

◆ vn_hash_type()

hashval_t vn_hash_type ( tree type)
inline
Hash the type TYPE using bits that distinguishes it in the
types_compatible_p sense.   

References INTEGRAL_TYPE_P, TYPE_PRECISION, and TYPE_UNSIGNED.

Referenced by vn_hash_constant_with_type(), and vn_phi_compute_hash().

◆ VN_INFO()

vn_ssa_aux_t VN_INFO ( tree name)
extern

◆ vn_nary_length_from_stmt()

unsigned int vn_nary_length_from_stmt ( gimple * stmt)
Return the number of operands for a vn_nary ops structure from STMT.   

References CONSTRUCTOR_NELTS, ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs_code(), and gimple_num_ops().

Referenced by compute_avail(), vn_nary_build_or_lookup_1(), vn_nary_op_insert_stmt(), and vn_nary_op_lookup_stmt().

◆ vn_nary_may_trap()

bool vn_nary_may_trap ( vn_nary_op_t nary)

◆ vn_nary_op_compute_hash()

◆ vn_nary_op_eq()

bool vn_nary_op_eq ( const_vn_nary_op_t const vno1,
const_vn_nary_op_t const vno2 )
Compare nary operations VNO1 and VNO2 and return true if they are
equivalent.   

References expressions_equal_p(), ggc_alloc(), i, TREE_CODE, TREE_TYPE, TYPE_PRECISION, and types_compatible_p().

Referenced by pre_expr_d::equal(), and vn_nary_op_hasher::equal().

◆ vn_nary_op_insert_pieces()

vn_nary_op_t vn_nary_op_insert_pieces ( unsigned int length,
enum tree_code code,
tree type,
tree * ops,
tree result,
unsigned int value_id )
Insert a n-ary operation into the current hash table using it's
pieces.  Return the vn_nary_op_t structure we created and put in
the hashtable.   

References alloc_vn_nary_op(), ggc_alloc(), init_vn_nary_op_from_pieces(), vn_tables_s::nary, vn_reference_s::result, valid_info, vn_reference_s::value_id, and vn_nary_op_insert_into().

Referenced by vn_reference_insert().

◆ vn_nary_op_lookup_pieces()

tree vn_nary_op_lookup_pieces ( unsigned int length,
enum tree_code code,
tree type,
tree * ops,
vn_nary_op_t * vnresult )
Lookup a n-ary operation by its pieces and return the resulting value
number if it exists in the hash table.  Return NULL_TREE if it does
not exist in the hash table or if the result field of the operation
is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
if it exists.   

References ggc_alloc(), init_vn_nary_op_from_pieces(), sizeof_vn_nary_op(), and vn_nary_op_lookup_1().

Referenced by phi_translate_1(), process_bb(), valueized_wider_op(), visit_nary_op(), visit_phi(), vn_lookup_simplify_result(), and vn_reference_lookup().

◆ vn_nary_op_lookup_stmt()

tree vn_nary_op_lookup_stmt ( gimple * stmt,
vn_nary_op_t * vnresult )
Lookup the rhs of STMT in the current hash table, and return the resulting
value number if it exists in the hash table.  Return NULL_TREE if
it does not exist in the hash table.  VNRESULT will contain the
vn_nary_op_t from the hashtable if it exists.   

References ggc_alloc(), init_vn_nary_op_from_stmt(), sizeof_vn_nary_op(), vn_nary_length_from_stmt(), and vn_nary_op_lookup_1().

Referenced by compute_avail(), visit_nary_op(), and vn_nary_build_or_lookup_1().

◆ vn_nary_simplify()

tree vn_nary_simplify ( vn_nary_op_t nary)

◆ vn_ref_op_align_unit()

◆ vn_reference_eq()

bool vn_reference_eq ( const_vn_reference_t const vr1,
const_vn_reference_t const vr2 )
Return true if reference operations VR1 and VR2 are equivalent.  This
means they have the same set of operands and vuses.   

References COMPLETE_TYPE_P, expressions_equal_p(), ggc_alloc(), i, INTEGRAL_TYPE_P, known_eq, TREE_CODE, TREE_INT_CST_LOW, TREE_OPERAND, TREE_TYPE, TYPE_PRECISION, TYPE_SIZE, TYPE_VECTOR_SUBPARTS(), types_compatible_p(), VECTOR_BOOLEAN_TYPE_P, and vn_reference_op_eq().

Referenced by pre_expr_d::equal(), and vn_reference_hasher::equal().

◆ vn_reference_insert_pieces()

◆ vn_reference_lookup()

tree vn_reference_lookup ( tree op,
tree vuse,
vn_lookup_kind kind,
vn_reference_t * vnresult,
bool tbaa_p,
tree * last_vuse_ptr,
tree mask,
bool redundant_store_removal_p )
Lookup OP in the current hash table, and return the resulting value
number if it exists in the hash table.  Return NULL_TREE if it does
not exist in the hash table or if the result field of the structure
was NULL..  VNRESULT will be filled in with the vn_reference_t
stored in the hashtable if one exists.  When TBAA_P is false assume
we are looking up a store and treat it as having alias-set zero.
*LAST_VUSE_PTR will be updated with the VUSE the value lookup succeeded.
MASK is either NULL_TREE, or can be an INTEGER_CST if the result of the
load is bitwise anded with MASK and so we are only interested in a subset
of the bits and can ignore if the other bits are uninitialized or
not initialized with constants.  When doing redundant store removal
the caller has to set REDUNDANT_STORE_REMOVAL_P.   

References ao_ref_alias_set(), ao_ref_base(), ao_ref_base_alias_set(), ao_ref_init(), ao_ref_init_from_vn_reference(), cfun, poly_int< N, C >::coeffs, copy_reference_ops_from_ref(), fully_constant_vn_reference_p(), gcc_assert, gcc_checking_assert, ggc_alloc(), i, known_eq, NULL, NULL_TREE, operand_equal_p(), vn_reference_s::operands, PROP_objsz, r, sext_hwi(), shared_lookup_references, sizetype, TREE_TYPE, TYPE_PRECISION, valueize_refs_1(), valueize_shared_reference_ops_from_ref(), vn_nary_op_lookup_pieces(), VN_NOWALK, vn_reference_compute_hash(), vn_reference_lookup_1(), vn_reference_lookup_2(), vn_reference_lookup_3(), vn_reference_s::vuse, vuse_ssa_val(), vuse_valueize(), walk_non_aliased_vuses(), and wide_int_to_tree().

Referenced by eliminate_dom_walker::eliminate_stmt(), visit_nary_op(), visit_reference_op_load(), and visit_reference_op_store().

◆ vn_reference_lookup_call()

◆ vn_reference_lookup_pieces()

tree vn_reference_lookup_pieces ( tree vuse,
alias_set_type set,
alias_set_type base_set,
tree type,
vec< vn_reference_op_s > operands,
vn_reference_t * vnresult,
vn_lookup_kind kind )
Lookup a reference operation by it's parts, in the current hash table.
Returns the resulting value number if it exists in the hash table,
NULL_TREE otherwise.  VNRESULT will be filled in with the actual
vn_reference_t stored in the hashtable if something is found.   

References ao_ref_init_from_vn_reference(), vn_reference_s::base_set, fully_constant_vn_reference_p(), gcc_checking_assert, ggc_alloc(), NULL, NULL_TREE, operand_equal_p(), vn_reference_s::operands, r, vn_reference_s::set, shared_lookup_references, type(), valueize_refs_1(), VN_NOWALK, vn_reference_compute_hash(), vn_reference_lookup_1(), vn_reference_lookup_2(), vn_reference_lookup_3(), vn_reference_s::vuse, vuse_ssa_val(), vuse_valueize(), and walk_non_aliased_vuses().

Referenced by compute_avail(), and phi_translate_1().

◆ vn_reference_may_trap()

◆ vn_reference_operands_for_lookup()

vec< vn_reference_op_s > vn_reference_operands_for_lookup ( tree op)
Return a reference op vector from OP that can be used for
vn_reference_lookup_pieces.  The caller is responsible for releasing
the vector.   

References ggc_alloc(), and valueize_shared_reference_ops_from_ref().

Referenced by compute_avail().

Variable Documentation

◆ vn_context_bb

◆ VN_TOP

◆ vn_valueize

tree(* vn_valueize) (tree) ( tree )
extern
Valueize NAME if it is an SSA name, otherwise just return it.  This hook
is initialized by run_scc_vn.   
Valueization hook for simplify_replace_tree.  Valueize NAME if it is
an SSA name, otherwise just return it.   

Referenced by do_rpo_vn_1(), process_bb(), try_to_simplify(), valueize_refs_1(), valueized_wider_op(), visit_stmt(), vn_nary_build_or_lookup_1(), vn_phi_insert(), vn_phi_lookup(), vn_reference_fold_indirect(), vn_reference_lookup_3(), vn_reference_maybe_forwprop_address(), and vn_valueize_for_srt().