#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 "gimplify.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	record_equivalences_from_incoming_edge (basic_block, class const_and_copies , class avail_exprs_stack , bitmap blocks_on_stack)

static void	eliminate_redundant_computations (gimple_stmt_iterator , class const_and_copies , class avail_exprs_stack *)

static void	record_equivalences_from_stmt (gimple , int, class avail_exprs_stack )

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 bool	single_block_loop_p (basic_block bb)

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 struct opt_stats_d	opt_stats

Function Documentation

◆ all_uses_feed_or_dominated_by_stmt()

static 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 CDI_DOMINATORS, dominated_by_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_assign_lhs(), gimple_bb(), is_gimple_assign(), is_gimple_debug(), single_imm_use(), TREE_CODE, and USE_STMT.

Referenced by dom_opt_dom_walker::set_global_ranges_from_unreachable_edges().

◆ back_propagate_equivalences()

static 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 bitmap_bit_p, CDI_DOMINATORS, dom_info_state(), DOM_OK, dom_valueize(), dominated_by_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), gimple_fold_stmt_to_constant_1(), gimple_get_lhs(), is_gimple_min_invariant(), no_follow_ssa_edges(), record_equality(), TREE_CODE, and USE_STMT.

Referenced by record_temporary_equivalences().

◆ cprop_into_stmt()

static 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_operand(), FOR_EACH_SSA_USE_OPERAND, ggc_alloc(), NULL, SSA_OP_USE, TREE_CODE, and USE_FROM_PTR.

Referenced by dom_opt_dom_walker::optimize_stmt().

◆ cprop_into_successor_phis()

static 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 FOR_EACH_EDGE, get_use_from_ptr(), ggc_alloc(), 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().

◆ cprop_operand()

static 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 dump_file, dump_flags, ggc_alloc(), gimple_bb(), gimple_set_modified(), may_propagate_copy(), may_propagate_copy_into_asm(), 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().

◆ dom_valueize()

static tree dom_valueize ( tree t )

static

Valueize hook for gimple_fold_stmt_to_constant_1.

References ggc_alloc(), SSA_NAME_VALUE, and TREE_CODE.

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

◆ dump_dominator_optimization_stats()

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

static

Dump SSA statistics on FILE.

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

◆ eliminate_redundant_computations()

static void eliminate_redundant_computations	(	gimple_stmt_iterator *	gsi,
		class const_and_copies *	const_and_copies,
		class avail_exprs_stack *	avail_exprs_stack )

static

Search for redundant computations in STMT.  If any are found, then
replace them with the variable holding the result of the computation.

If safe, record this expression into AVAIL_EXPRS_STACK and
CONST_AND_COPIES.

References boolean_type_node, dump_file, dump_flags, fold_convert, gcc_assert, gcc_checking_assert, gcc_unreachable, ggc_alloc(), gimple_assign_lhs(), gimple_call_lhs(), gimple_get_lhs(), gimple_phi_result(), gimple_set_modified(), gimple_switch_index(), gimple_vdef(), gsi_stmt(), insert(), is_gimple_assign(), is_gimple_call(), is_gimple_min_invariant(), avail_exprs_stack::lookup_avail_expr(), may_propagate_copy_into_stmt(), opt_stats_d::num_exprs_considered, opt_stats_d::num_re, opt_stats, print_generic_expr(), print_gimple_expr(), propagate_tree_value_into_stmt(), const_and_copies::record_const_or_copy(), simple_iv_increment_p(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TDF_DETAILS, TREE_CODE, TREE_TYPE, and useless_type_conversion_p().

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

◆ free_all_edge_infos()

static 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_dom_edge_info(), and basic_block_def::preds.

◆ 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 edge_info::edge_info(), and NULL.

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

◆ htab_statistics()

static 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, ggc_alloc(), HOST_SIZE_T_PRINT_DEC, and hash_table< Descriptor, Lazy, Allocator >::size().

◆ make_pass_dominator()

gimple_opt_pass * make_pass_dominator ( gcc::context * ctxt )

References ggc_alloc().

◆ maybe_set_nonzero_bits()

static 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 wi::bit_and_not(), wi::bit_not(), CONVERT_EXPR_CODE_P, wi::ctz(), get_nonzero_bits(), get_ptr_info(), ggc_alloc(), 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(), NULL, POINTER_TYPE_P, 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 dom_opt_dom_walker::set_global_ranges_from_unreachable_edges().

◆ record_edge_info()

static 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 boolean_type_node, build2(), CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, edge_info::cond_equivalences, constant_boolean_node(), DECIMAL_FLOAT_MODE_P, edge_info::edge_info(), EDGE_PRED, EDGE_SUCC, element_mode(), error_mark_node, extract_true_false_edges_from_block(), fold_convert_loc(), FOR_EACH_EDGE, free(), free_dom_edge_info(), ggc_alloc(), gimple_bb(), 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_next(), gsi_start_phis(), 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, gphi_iterator::phi(), PHI_ARG_DEF, PHI_RESULT, real_maybe_zerop(), record_conditions(), edge_info::record_simple_equiv(), single_block_loop_p(), SSA_NAME_DEF_STMT, ssa_name_has_boolean_range(), basic_block_def::succs, TREE_CODE, and TREE_TYPE.

Referenced by dom_opt_dom_walker::before_dom_children().

◆ record_equality()

static 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, ggc_alloc(), has_single_use(), HONOR_SIGNED_ZEROS(), is_gimple_min_invariant(), NULL, real_equal(), const_and_copies::record_const_or_copy(), SSA_NAME_VALUE, TREE_CODE, TREE_REAL_CST, tree_swap_operands_p(), and y.

Referenced by back_propagate_equivalences(), and record_temporary_equivalences().

◆ record_equivalences_from_incoming_edge()

static void record_equivalences_from_incoming_edge	(	basic_block	bb,
		class const_and_copies *	const_and_copies,
		class avail_exprs_stack *	avail_exprs_stack,
		bitmap	blocks_on_stack )

static

Record any equivalences created by the incoming edge to BB into
CONST_AND_COPIES and AVAIL_EXPRS_STACK.  If BB has more than one
incoming edge, then no equivalence is created.

References CDI_DOMINATORS, get_immediate_dominator(), ggc_alloc(), record_temporary_equivalences(), and single_pred_edge_ignoring_loop_edges().

Referenced by dom_opt_dom_walker::before_dom_children().

◆ record_equivalences_from_phis()

static 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, ggc_alloc(), 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(), 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().

◆ record_equivalences_from_stmt()

static void record_equivalences_from_stmt	(	gimple *	stmt,
		int	may_optimize_p,
		class avail_exprs_stack *	avail_exprs_stack )

static

STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
the available expressions table or the const_and_copies table.
Detect and record those equivalences into AVAIL_EXPRS_STACK. 

We handle only very simple copy equivalences here.  The heavy
lifing is done by eliminate_redundant_computations.

References build1(), dom_valueize(), dump_file, dump_flags, fold_build2, fold_convert, gcc_assert, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_single_p(), gimple_build_assign(), gimple_has_volatile_ops(), gimple_references_memory_p(), gimple_set_vuse(), gimple_vdef(), is_gimple_assign(), is_gimple_min_invariant(), is_gimple_reg(), avail_exprs_stack::lookup_avail_expr(), print_generic_expr(), ptr_type_node, set_ssa_name_value(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, TREE_TYPE, and unshare_expr().

Referenced by dom_opt_dom_walker::optimize_stmt().

◆ record_temporary_equivalences()

static 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(), ggc_alloc(), i, avail_exprs_stack::record_cond(), record_equality(), edge_info::simple_equivalences, SSA_NAME_DEF_STMT, and TREE_CODE.

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

◆ reduce_vector_comparison_to_scalar_comparison()

static 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 dump_file, dump_flags, ggc_alloc(), 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(), 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().

◆ 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} +/- ...

References ggc_alloc(), 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, SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by eliminate_redundant_computations().

◆ single_block_loop_p()

static bool single_block_loop_p ( basic_block bb )

static

Return TRUE if BB has precisely two preds, one of which
is a backedge from a forwarder block where the forwarder
block is a direct successor of BB.  Being a forwarder
block, it has no side effects other than transfer of
control.  Otherwise return FALSE.

References count, DECL_NONLOCAL, EDGE_COUNT, EDGE_PRED, EDGE_SUCC, ggc_alloc(), gimple_label_label(), gimple_seq_empty_p(), gsi_end_p(), gsi_last_bb(), gsi_prev(), gsi_stmt(), NULL, phi_nodes(), basic_block_def::preds, and basic_block_def::succs.

Referenced by record_edge_info().

Variable Documentation

◆ cfg_altered

bool cfg_altered

static

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

◆ need_eh_cleanup

bitmap need_eh_cleanup

static

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

◆ 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(), 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()

◆ eliminate_redundant_computations()

◆ 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_incoming_edge()

◆ record_equivalences_from_phis()

◆ record_equivalences_from_stmt()

◆ record_temporary_equivalences()

◆ reduce_vector_comparison_to_scalar_comparison()

◆ simple_iv_increment_p()

◆ single_block_loop_p()

Variable Documentation

◆ cfg_altered

◆ need_eh_cleanup

◆ need_noreturn_fixup

◆ opt_stats