#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "fold-const.h"
#include "cfganal.h"
#include "cfgloop.h"
#include "gimple-iterator.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "tree-inline.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "domwalk.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-threadupdate.h"
#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
#include "tree-ssa-dom.h"
#include "tree-cfgcleanup.h"
#include "dbgcnt.h"
#include "alloc-pool.h"
#include "tree-vrp.h"
#include "vr-values.h"
#include "gimple-range.h"
#include "gimple-range-path.h"
#include "alias.h"

Include dependency graph for tree-ssa-dom.cc:

Data Structures
class	edge_info
struct	opt_stats_d
class	dom_jt_state
class	dom_jt_simplifier
class	dom_opt_dom_walker

Functions
static void	record_equality (tree, tree, class const_and_copies *)
static void	record_equivalences_from_phis (basic_block)
static void	dump_dominator_optimization_stats (FILE file, hash_table< expr_elt_hasher > )
static void	record_temporary_equivalences (edge, class const_and_copies , class avail_exprs_stack , bitmap)
void	free_dom_edge_info (edge e)
static void	free_all_edge_infos (void)
static void	record_edge_info (basic_block bb)
gimple_opt_pass *	make_pass_dominator (gcc::context *ctxt)
static tree	dom_valueize (tree t)
static void	back_propagate_equivalences (tree lhs, edge e, class const_and_copies *const_and_copies, bitmap domby)
static bool	all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
static void	maybe_set_nonzero_bits (edge e, tree var)
static void	htab_statistics (FILE *file, const hash_table< expr_elt_hasher > &htab)
bool	simple_iv_increment_p (gimple *stmt)
static void	cprop_into_successor_phis (basic_block bb, class const_and_copies *const_and_copies)
static void	cprop_operand (gimple stmt, use_operand_p op_p, range_query query)
static void	cprop_into_stmt (gimple stmt, range_query query)
static void	reduce_vector_comparison_to_scalar_comparison (gimple *stmt)

Variables
static bool	cfg_altered
static bitmap	need_eh_cleanup
static vec< gimple * >	need_noreturn_fixup
static bitmap	names_without_foldable_uses
static struct opt_stats_d	opt_stats

Function Documentation

◆ all_uses_feed_or_dominated_by_stmt()

bool all_uses_feed_or_dominated_by_stmt	(	tree	name,
		gimple *	stmt )

static

Return true if all uses of NAME are dominated by STMT or feed STMT
via a chain of single immediate uses.

References all_uses_feed_or_dominated_by_stmt(), CDI_DOMINATORS, dominated_by_p(), FOR_EACH_IMM_USE_FAST, gimple_assign_lhs(), gimple_bb(), is_gimple_assign(), is_gimple_debug(), single_imm_use(), TREE_CODE, and USE_STMT.

Referenced by all_uses_feed_or_dominated_by_stmt(), and dom_opt_dom_walker::set_global_ranges_from_unreachable_edges().

◆ back_propagate_equivalences()

void back_propagate_equivalences	(	tree	lhs,
		edge	e,
		class const_and_copies *	const_and_copies,
		bitmap	domby )

static

We have just found an equivalence for LHS on an edge E.
Look backwards to other uses of LHS and see if we can derive
additional equivalences that are valid on edge E.

References back_propagate_equivalences(), bitmap_bit_p, bitmap_set_bit, CDI_DOMINATORS, dom_info_state(), DOM_OK, dom_valueize(), dominated_by_p(), FOR_EACH_IMM_USE_FAST, gcc_checking_assert, gimple_bb(), gimple_fold_stmt_to_constant_1(), gimple_get_lhs(), is_gimple_min_invariant(), names_without_foldable_uses, no_follow_ssa_edges(), record_equality(), SSA_NAME_VERSION, TREE_CODE, and USE_STMT.

Referenced by back_propagate_equivalences(), and record_temporary_equivalences().

◆ cprop_into_stmt()

void cprop_into_stmt	(	gimple *	stmt,
		range_query *	query )

static

CONST_AND_COPIES is a table which maps an SSA_NAME to the current
known value for that SSA_NAME (or NULL if no value is known).

Propagate values from CONST_AND_COPIES into the uses, vuses and
vdef_ops of STMT.

References cprop_into_stmt(), cprop_operand(), FOR_EACH_SSA_USE_OPERAND, NULL, SSA_OP_USE, TREE_CODE, and USE_FROM_PTR.

Referenced by cprop_into_stmt(), and dom_opt_dom_walker::optimize_stmt().

◆ cprop_into_successor_phis()

void cprop_into_successor_phis	(	basic_block	bb,
		class const_and_copies *	const_and_copies )

static

Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
successors of BB.

References cprop_into_successor_phis(), FOR_EACH_EDGE, get_use_from_ptr(), gimple_phi_arg_imm_use_ptr(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, may_propagate_copy(), gphi_iterator::phi(), const_and_copies::pop_to_marker(), propagate_value(), const_and_copies::push_marker(), const_and_copies::record_const_or_copy(), edge_info::simple_equivalences, SSA_NAME_VALUE, basic_block_def::succs, and TREE_CODE.

Referenced by dom_opt_dom_walker::before_dom_children(), and cprop_into_successor_phis().

◆ cprop_operand()

void cprop_operand	(	gimple *	stmt,
		use_operand_p	op_p,
		range_query *	query )

static

Replace *OP_P in STMT with any known equivalent value for *OP_P from
CONST_AND_COPIES.

References cprop_operand(), dump_file, dump_flags, gimple_bb(), gimple_set_modified(), may_propagate_copy(), opt_stats_d::num_const_prop, opt_stats_d::num_copy_prop, opt_stats, print_generic_expr(), propagate_value(), r, range_query::range_of_expr(), SSA_NAME_DEF_STMT, SSA_NAME_VALUE, TDF_DETAILS, TREE_CODE, TREE_TYPE, and USE_FROM_PTR.

Referenced by cprop_into_stmt(), and cprop_operand().

◆ dom_valueize()

tree dom_valueize ( tree t )

static

Valueize hook for gimple_fold_stmt_to_constant_1.

References dom_valueize(), SSA_NAME_VALUE, and TREE_CODE.

Referenced by back_propagate_equivalences(), dom_valueize(), dom_opt_dom_walker::optimize_stmt(), record_equivalences_from_phis(), and dom_opt_dom_walker::record_equivalences_from_stmt().

◆ dump_dominator_optimization_stats()

void dump_dominator_optimization_stats	(	FILE *	file,
		hash_table< expr_elt_hasher > *	avail_exprs )

static

Dump SSA statistics on FILE.

References dump_dominator_optimization_stats(), htab_statistics(), opt_stats_d::num_exprs_considered, opt_stats_d::num_stmts, and opt_stats.

Referenced by dump_dominator_optimization_stats().

◆ free_all_edge_infos()

void free_all_edge_infos ( void )

static

Free all EDGE_INFO structures associated with edges in the CFG.
If a particular edge can be threaded, copy the redirection
target from the EDGE_INFO structure into the edge's AUX field
as required by code to update the CFG and SSA graph for
jump threading.

References cfun, FOR_EACH_BB_FN, FOR_EACH_EDGE, free_all_edge_infos(), free_dom_edge_info(), and basic_block_def::preds.

Referenced by free_all_edge_infos().

◆ free_dom_edge_info()

void free_dom_edge_info ( edge e )

Free the edge_info data attached to E, if it exists and
clear e->aux.

References free_dom_edge_info(), and NULL.

Referenced by edge_info::edge_info(), free_all_edge_infos(), free_dom_edge_info(), record_edge_info(), and remove_ctrl_stmt_and_useless_edges().

◆ htab_statistics()

void htab_statistics	(	FILE *	file,
		const hash_table< expr_elt_hasher > &	htab )

static

Dump statistics for the hash table HTAB.

References hash_table< Descriptor, Lazy, Allocator >::collisions(), hash_table< Descriptor, Lazy, Allocator >::elements(), fmt_size_t, HOST_SIZE_T_PRINT_DEC, htab_statistics(), and hash_table< Descriptor, Lazy, Allocator >::size().

◆ make_pass_dominator()

gimple_opt_pass * make_pass_dominator ( gcc::context * ctxt )

References make_pass_dominator().

Referenced by make_pass_dominator(), and make_pass_empty_loop().

◆ maybe_set_nonzero_bits()

void maybe_set_nonzero_bits	(	edge	e,
		tree	var )

static

Handle
_4 = x_3 & 31;
if (_4 != 0)
  goto <bb 6>;
else
  goto <bb 7>;
<bb 6>:
__builtin_unreachable ();
<bb 7>:

If x_3 has no other immediate uses (checked by caller), var is the
x_3 var, we can clear low 5 bits from the non-zero bitmask.

References ptr_info_def::align, wi::bit_and_not(), wi::bit_not(), CONVERT_EXPR_CODE_P, wi::ctz(), get_nonzero_bits(), get_ptr_info(), gimple_assign_cast_p(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), HOST_BITS_PER_INT, integer_zerop(), is_gimple_assign(), maybe_set_nonzero_bits(), ptr_info_def::misalign, NULL, POINTER_TYPE_P, safe_dyn_cast(), set_nonzero_bits(), set_ptr_info_alignment(), SSA_NAME_DEF_STMT, SSA_NAME_PTR_INFO, wi::to_wide(), TREE_CODE, TREE_TYPE, and TYPE_PRECISION.

Referenced by maybe_set_nonzero_bits(), and dom_opt_dom_walker::set_global_ranges_from_unreachable_edges().

◆ record_edge_info()

void record_edge_info ( basic_block bb )

static

We have finished optimizing BB, record any information implied by
taking a specific outgoing edge from BB.

References as_a(), boolean_type_node, build2(), CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, edge_info::cond_equivalences, constant_boolean_node(), DECIMAL_FLOAT_MODE_P, element_mode(), error_mark_node, extract_true_false_edges_from_block(), fold_convert_loc(), FOR_EACH_EDGE, free(), free_dom_edge_info(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_location(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), gsi_end_p(), gsi_last_bb(), gsi_stmt(), HONOR_SIGNED_ZEROS(), i, basic_block_def::index, integer_onep(), integer_zerop(), invert_truthvalue_loc(), is_gimple_min_invariant(), label_to_block(), last_basic_block_for_fn, NULL, real_maybe_zerop(), record_conditions(), record_edge_info(), edge_info::record_simple_equiv(), ssa_name_has_boolean_range(), basic_block_def::succs, TREE_CODE, and TREE_TYPE.

Referenced by dom_opt_dom_walker::before_dom_children(), and record_edge_info().

◆ record_equality()

void record_equality	(	tree	x,
		tree	y,
		class const_and_copies *	const_and_copies )

static

Local functions.

Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
This constrains the cases in which we may treat this as assignment.

References dconst0, has_single_use(), HONOR_SIGNED_ZEROS(), is_gimple_min_invariant(), NULL, real_equal(), const_and_copies::record_const_or_copy(), record_equality(), SSA_NAME_VALUE, TREE_CODE, TREE_REAL_CST, tree_swap_operands_p(), and y.

Referenced by back_propagate_equivalences(), record_equality(), and record_temporary_equivalences().

◆ record_equivalences_from_phis()

void record_equivalences_from_phis ( basic_block bb )

static

PHI nodes can create equivalences too.

Ignoring any alternatives which are the same as the result, if
all the alternatives are equal, then the PHI node creates an
equivalence.

References dom_valueize(), FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_for_stmt(), gsi_next(), gsi_start_phis(), i, may_propagate_copy(), NULL, operand_equal_for_phi_arg_p(), gphi_iterator::phi(), record_equivalences_from_phis(), remove_phi_node(), set_ssa_name_value(), SET_USE, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TREE_CODE, and virtual_operand_p().

Referenced by dom_opt_dom_walker::before_dom_children(), and record_equivalences_from_phis().

◆ record_temporary_equivalences()

void record_temporary_equivalences	(	edge	e,
		class const_and_copies *	const_and_copies,
		class avail_exprs_stack *	avail_exprs_stack,
		bitmap	blocks_on_stack )

static

Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
by traversing edge E (which are cached in E->aux).

Callers are responsible for managing the unwinding markers.

References back_propagate_equivalences(), edge_info::cond_equivalences, eni_size_weights, estimate_num_insns(), i, avail_exprs_stack::record_cond(), record_equality(), record_temporary_equivalences(), edge_info::simple_equivalences, SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by dom_opt_dom_walker::record_equivalences_from_incoming_edge(), record_temporary_equivalences(), and dom_jt_state::register_equivs_edge().

◆ reduce_vector_comparison_to_scalar_comparison()

void reduce_vector_comparison_to_scalar_comparison ( gimple * stmt )

static

If STMT is a comparison of two uniform vectors reduce it to a comparison
of scalar objects, otherwise leave STMT unchanged.

References as_a(), dump_file, dump_flags, gimple_assign_rhs1(), gimple_assign_single_p(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_cond_set_lhs(), gimple_cond_set_rhs(), gimple_set_modified(), NULL_TREE, print_gimple_stmt(), reduce_vector_comparison_to_scalar_comparison(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, TREE_TYPE, uniform_vector_p(), and VECTOR_TYPE_P.

Referenced by dom_opt_dom_walker::optimize_stmt(), and reduce_vector_comparison_to_scalar_comparison().

◆ simple_iv_increment_p()

bool simple_iv_increment_p ( gimple * stmt )

Returns true when STMT is a simple iv increment.  It detects the
following situation:

i_1 = phi (..., i_k)
[...]
i_j = i_{j-1}  for each j : 2 <= j <= k-1
[...]
i_k = i_{k-1} +/- ...

Header file for SSA dominator optimizations.
   Copyright (C) 2013-2026 Free Software Foundation, Inc.

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/>.

References gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_assign_ssa_name_copy_p(), gimple_phi_arg_def(), gimple_phi_num_args(), i, simple_iv_increment_p(), SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by dom_opt_dom_walker::eliminate_redundant_computations(), and simple_iv_increment_p().

Variable Documentation

◆ cfg_altered

bool cfg_altered

static

Track whether or not we have changed the control flow graph.

Referenced by dom_opt_dom_walker::optimize_stmt().

◆ names_without_foldable_uses

bitmap names_without_foldable_uses

static

Bitmap of SSA names that have no use in an assignment or call that
defines an SSA name, so back_propagate_equivalences has nothing to do
for them.  A bit is cleared when DOM adds such a use.

Referenced by back_propagate_equivalences(), and dom_opt_dom_walker::before_dom_children().

◆ need_eh_cleanup

bitmap need_eh_cleanup

static

Bitmap of blocks that have had EH statements cleaned.  We should
remove their dead edges eventually.

Referenced by dom_opt_dom_walker::optimize_stmt().

◆ need_noreturn_fixup

vec<gimple *> need_noreturn_fixup

static

Referenced by dom_opt_dom_walker::optimize_stmt().

◆ opt_stats

struct opt_stats_d opt_stats

static

Referenced by cprop_operand(), dump_dominator_optimization_stats(), dom_opt_dom_walker::eliminate_redundant_computations(), and dom_opt_dom_walker::optimize_stmt().

Data Structures

Functions

Variables

Function Documentation

◆ all_uses_feed_or_dominated_by_stmt()

◆ back_propagate_equivalences()

◆ cprop_into_stmt()

◆ cprop_into_successor_phis()

◆ cprop_operand()

◆ dom_valueize()

◆ dump_dominator_optimization_stats()

◆ free_all_edge_infos()

◆ free_dom_edge_info()

◆ htab_statistics()

◆ make_pass_dominator()

◆ maybe_set_nonzero_bits()

◆ record_edge_info()

◆ record_equality()

◆ record_equivalences_from_phis()

◆ record_temporary_equivalences()

◆ reduce_vector_comparison_to_scalar_comparison()

◆ simple_iv_increment_p()

Variable Documentation

◆ cfg_altered

◆ names_without_foldable_uses

◆ need_eh_cleanup

◆ need_noreturn_fixup

◆ opt_stats