GCC Middle and Back End API Reference
dominance.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "timevar.h"
#include "diagnostic-core.h"
#include "cfganal.h"
#include "et-forest.h"
#include "graphds.h"
Include dependency graph for dominance.cc:

Typedefs

typedef unsigned int TBB
 

Functions

void debug_dominance_info (cdi_direction)
 
void debug_dominance_tree (cdi_direction, basic_block)
 
template<typename T >
Tnew_zero_array (unsigned num)
 
static unsigned int dom_convert_dir_to_idx (cdi_direction dir)
 
static void assign_dfs_numbers (struct et_node *node, int *num)
 
static void compute_dom_fast_query (enum cdi_direction dir)
 
static void compute_dom_fast_query_in_region (enum cdi_direction dir, vec< basic_block > region)
 
void calculate_dominance_info (cdi_direction dir, bool compute_fast_query)
 
void calculate_dominance_info_for_region (cdi_direction dir, vec< basic_block > region)
 
void free_dominance_info (function *fn, enum cdi_direction dir)
 
void free_dominance_info (enum cdi_direction dir)
 
void free_dominance_info_for_region (function *fn, enum cdi_direction dir, vec< basic_block > region)
 
basic_block get_immediate_dominator (enum cdi_direction dir, basic_block bb)
 
void set_immediate_dominator (enum cdi_direction dir, basic_block bb, basic_block dominated_by)
 
auto_vec< basic_blockget_dominated_by (enum cdi_direction dir, basic_block bb)
 
auto_vec< basic_blockget_dominated_by_region (enum cdi_direction dir, basic_block *region, unsigned n_region)
 
auto_vec< basic_blockget_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
 
auto_vec< basic_blockget_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
 
void redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, basic_block to)
 
basic_block nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
 
basic_block nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
 
bool dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
 
unsigned bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
 
unsigned bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
 
DEBUG_FUNCTION void verify_dominators (cdi_direction dir)
 
basic_block recompute_dominator (enum cdi_direction dir, basic_block bb)
 
static void prune_bbs_to_update_dominators (vec< basic_block > &bbs, bool conservative)
 
static basic_block root_of_dom_tree (enum cdi_direction dir, basic_block bb)
 
static void determine_dominators_for_sons (struct graph *g, vec< basic_block > bbs, int y, int *son, int *brother)
 
void iterate_fix_dominators (enum cdi_direction dir, vec< basic_block > &bbs, bool conservative)
 
void add_to_dominance_info (enum cdi_direction dir, basic_block bb)
 
void delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
 
basic_block first_dom_son (enum cdi_direction dir, basic_block bb)
 
basic_block next_dom_son (enum cdi_direction dir, basic_block bb)
 
enum dom_state dom_info_state (function *fn, enum cdi_direction dir)
 
enum dom_state dom_info_state (enum cdi_direction dir)
 
void set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
 
bool dom_info_available_p (function *fn, enum cdi_direction dir)
 
bool dom_info_available_p (enum cdi_direction dir)
 
DEBUG_FUNCTION void dot_dominance_tree (FILE *f, enum cdi_direction dir)
 
DEBUG_FUNCTION void dot_dominance_tree (const char *fname, enum cdi_direction dir)
 
static void debug_dominance_tree_1 (enum cdi_direction dir, basic_block root, unsigned indent, bool indent_first)
 

Typedef Documentation

◆ TBB

typedef unsigned int TBB
Calculate (post)dominators in slightly super-linear time.
Copyright (C) 2000-2024 Free Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).

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/>.   
This file implements the well known algorithm from Lengauer and Tarjan
to compute the dominators in a control flow graph.  A basic block D is said
to dominate another block X, when all paths from the entry node of the CFG
to X go also over D.  The dominance relation is a transitive reflexive
relation and its minimal transitive reduction is a tree, called the
dominator tree.  So for each block X besides the entry block exists a
block I(X), called the immediate dominator of X, which is the parent of X
in the dominator tree.

The algorithm computes this dominator tree implicitly by computing for
each block its immediate dominator.  We use tree balancing and path
compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
slowly growing functional inverse of the Ackerman function.   
We name our nodes with integers, beginning with 1.  Zero is reserved for
'undefined' or 'end of list'.  The name of each node is given by the dfs
number of the corresponding basic block.  Please note, that we include the
artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
support multiple entry points.  Its dfs number is of course 1.   
Type of Basic Block aka. TBB  

Function Documentation

◆ add_to_dominance_info()

◆ assign_dfs_numbers()

static void assign_dfs_numbers ( struct et_node * node,
int * num )
static
Assign dfs numbers starting from NUM to NODE and its sons.   

References et_node::dfs_num_in, et_node::dfs_num_out, et_node::father, et_node::right, and et_node::son.

Referenced by compute_dom_fast_query(), and compute_dom_fast_query_in_region().

◆ bb_dom_dfs_in()

unsigned bb_dom_dfs_in ( enum cdi_direction dir,
basic_block bb )
Returns the entry dfs number for basic block BB, in the direction DIR.   

References et_node::dfs_num_in, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_OK, and gcc_checking_assert.

Referenced by prune_unused_phi_nodes().

◆ bb_dom_dfs_out()

unsigned bb_dom_dfs_out ( enum cdi_direction dir,
basic_block bb )
Returns the exit dfs number for basic block BB, in the direction DIR.   

References et_node::dfs_num_out, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_OK, and gcc_checking_assert.

Referenced by prune_unused_phi_nodes().

◆ calculate_dominance_info()

void calculate_dominance_info ( cdi_direction dir,
bool compute_fast_query )
The main entry point into this module.  DIR is set depending on whether
we want to compute dominators or postdominators.  If COMPUTE_FAST_QUERY
is false then the DFS numbers allowing for a O(1) dominance query
are not computed.   

References b, cfun, checking_verify_dominators(), compute_dom_fast_query(), basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_NO_FAST_QUERY, DOM_OK, et_new_tree(), et_set_father(), FOR_ALL_BB_FN, FOR_EACH_BB_FN, gcc_assert, n_basic_blocks_for_fn, n_bbs_in_dom_tree, timevar_pop(), and timevar_push().

Referenced by autofdo::afdo_calculate_branch_prob(), analyze_function_body(), build_omp_regions(), clean_up_loop_closed_phi(), cleanup_cfg(), cleanup_tree_cfg_noloop(), compute_code_hoist_data(), create_parallel_loop(), do_ssa_ccp(), loop_distribution::execute(), pass_array_bounds::execute(), execute_early_warn_uninitialized(), execute_fast_vrp(), execute_ranger_vrp(), execute_split_functions(), find_always_executed_bbs(), find_comparisons(), find_conditions(), find_moveable_pseudos(), flow_loops_find(), fwprop_init(), gate_tm_init(), gimple_lower_bitint(), if_convert(), if_convertible_loop_p_1(), init_pre(), init_reassoc(), ipa_analyze_node(), ipa_tm_execute(), ipa_tm_scan_irr_function(), ipa_tm_transform_clone(), ipa_tm_transform_transaction(), ipcp_transform_function(), ira(), loop_optimizer_init(), oacc_entry_exit_ok(), optimize_va_list_gpr_fpr_size(), pair_fusion::pair_fusion(), parallelize_loops(), perform_tree_ssa_dce(), propagate_with_phi(), repair_loop_structures(), sanopt_optimize(), simd_clone_adjust(), split_live_ranges_for_shrink_wrap(), split_paths(), substitute_and_fold_engine::substitute_and_fold(), tail_merge_optimize(), transform_to_exit_first_loop_alt(), tree_estimate_probability(), tree_function_versioning(), tree_ssa_split_loops(), try_shrink_wrapping(), try_shrink_wrapping_separate(), unroll_loops(), update_ssa(), verify_loop_structure(), verify_ssa(), and warn_return_addr_local().

◆ calculate_dominance_info_for_region()

void calculate_dominance_info_for_region ( cdi_direction dir,
vec< basic_block > region )
Analogous to the previous function but compute dominance info for regions
which are single entry, multiple exit regions for CDI_DOMINATORs and
multiple entry, single exit regions for CDI_POST_DOMINATORs.   

References compute_dom_fast_query_in_region(), basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_NO_FAST_QUERY, DOM_OK, et_new_tree(), et_set_father(), FOR_EACH_VEC_ELT, gcc_assert, i, timevar_pop(), and timevar_push().

Referenced by if_convertible_loop_p_1().

◆ compute_dom_fast_query()

static void compute_dom_fast_query ( enum cdi_direction dir)
static
Compute the data necessary for fast resolving of dominator queries in a
static dominator tree.   

References assign_dfs_numbers(), cfun, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_OK, et_node::father, FOR_ALL_BB_FN, and gcc_checking_assert.

Referenced by calculate_dominance_info().

◆ compute_dom_fast_query_in_region()

static void compute_dom_fast_query_in_region ( enum cdi_direction dir,
vec< basic_block > region )
static
Analogous to the previous function but compute the data for reducible
region REGION.   

References assign_dfs_numbers(), basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_OK, et_node::father, gcc_checking_assert, and i.

Referenced by calculate_dominance_info_for_region().

◆ debug_dominance_info()

◆ debug_dominance_tree()

DEBUG_FUNCTION void debug_dominance_tree ( enum cdi_direction dir,
basic_block root )
Prints to stderr representation of the dominance tree (for direction DIR)
rooted in ROOT.   

References debug_dominance_tree_1().

◆ debug_dominance_tree_1()

static void debug_dominance_tree_1 ( enum cdi_direction dir,
basic_block root,
unsigned indent,
bool indent_first )
static
Prints to stderr representation of the dominance tree (for direction DIR)
rooted in ROOT, indented by INDENT tabulators.  If INDENT_FIRST is false,
the first line of the output is not indented.   

References debug_dominance_tree_1(), first_dom_son(), i, basic_block_def::index, and next_dom_son().

Referenced by debug_dominance_tree(), and debug_dominance_tree_1().

◆ delete_from_dominance_info()

◆ determine_dominators_for_sons()

static void determine_dominators_for_sons ( struct graph * g,
vec< basic_block > bbs,
int y,
int * son,
int * brother )
static
See the comment in iterate_fix_dominators.  Finds the immediate dominators
for the sons of Y, found using the SON and BROTHER arrays representing
the dominance tree of graph G.  BBS maps the vertices of G to the basic
blocks.   

References a, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, CDI_DOMINATORS, cfun, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, FOR_EACH_VEC_ELT, free(), g, gcc_assert, graphds_scc(), i, identify_vertices(), nearest_common_dominator(), NULL, basic_block_def::preds, recompute_dominator(), root_of_dom_tree(), set_immediate_dominator(), si, and y.

Referenced by iterate_fix_dominators().

◆ dom_convert_dir_to_idx()

◆ dom_info_available_p() [1/2]

bool dom_info_available_p ( enum cdi_direction dir)

References cfun, and dom_info_available_p().

◆ dom_info_available_p() [2/2]

bool dom_info_available_p ( function * fn,
enum cdi_direction dir )
Returns true if dominance information for direction DIR is available.   

References dom_info_state(), and DOM_NONE.

Referenced by adjust_debug_stmts_now(), and_comparisons_1(), calculate_dominance_info(), calculate_dominance_info_for_region(), rt_bb_visited::check(), cleanup_cfg(), cleanup_tree_cfg_noloop(), compute_dom_fast_query(), compute_dom_fast_query_in_region(), create_basic_block_1(), create_cond_insert_point(), range_query::create_relation_oracle(), delete_basic_block(), delete_unreachable_blocks(), dom_info_available_p(), edge_before_returns_twice_call(), eliminate_unnecessary_stmts(), execute_one_pass(), expand_complex_div_wide(), find_always_executed_bbs(), find_conditions(), follow_outer_ssa_edges(), force_nonfallthru(), free_dominance_info(), free_dominance_info_for_region(), tree_switch_conversion::switch_conversion::gen_inbound_check(), gimple_lower_bitint(), gsi_insert_finally_seq_after_call(), insert_check_and_trap(), insert_cond_bb(), insert_debug_temp_for_var_def(), rt_bb_visited::insert_exit_check_on_edge(), make_forwarder_block(), merge_blocks(), mfb_keep_latches(), move_sese_in_condition(), optimize_mask_stores(), or_comparisons_1(), propagate_with_phi(), ranger_cache::range_from_dom(), fold_using_range::range_of_phi(), redirect_edge_and_branch_force(), release_function_body(), remove_edge_and_dominated_blocks(), remove_forwarder_block(), rest_of_handle_combine(), shrink_wrap_one_built_in_call_with_conds(), split_block_1(), split_edge(), tail_merge_optimize(), ubsan_expand_null_ifn(), ubsan_expand_ptr_ifn(), vect_loop_versioning(), verify_dominators(), and verify_loop_structure().

◆ dom_info_state() [1/2]

enum dom_state dom_info_state ( enum cdi_direction dir)

References cfun, and dom_info_state().

◆ dom_info_state() [2/2]

◆ dominated_by_p()

bool dominated_by_p ( enum cdi_direction dir,
const_basic_block bb1,
const_basic_block bb2 )
Given a dominator tree, we can determine whether one thing
 dominates another in constant time by using two DFS numbers:

 1. The number for when we visit a node on the way down the tree
 2. The number for when we visit a node on the way back up the tree

 You can view these as bounds for the range of dfs numbers the
 nodes in the subtree of the dominator tree rooted at that node
 will contain.

 The dominator tree is always a simple acyclic tree, so there are
 only three possible relations two nodes in the dominator tree have
 to each other:

 1. Node A is above Node B (and thus, Node A dominates node B)

  A
  |
  C
 / \
B   D


In the above case, DFS_Number_In of A will be <= DFS_Number_In of
B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
because we must hit A in the dominator tree *before* B on the walk
down, and we will hit A *after* B on the walk back up

2. Node A is below node B (and thus, node B dominates node A)


  B
  |
  A
 / \
C   D

In the above case, DFS_Number_In of A will be >= DFS_Number_In of
B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.

This is because we must hit A in the dominator tree *after* B on
the walk down, and we will hit A *before* B on the walk back up

3. Node A and B are siblings (and thus, neither dominates the other)

  C
  |
  D
 / \
A   B

In the above case, DFS_Number_In of A will *always* be <=
DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
DFS_Number_Out of B.  This is because we will always finish the dfs
walk of one of the subtrees before the other, and thus, the dfs
numbers for one subtree can't intersect with the range of dfs
numbers for the other subtree.  If you swap A and B's position in
the dominator tree, the comparison changes direction, but the point
is that both comparisons will always go the same way if there is no
dominance relationship.

Thus, it is sufficient to write

A_Dominates_B (node A, node B)
{
  return DFS_Number_In(A) <= DFS_Number_In(B)
         && DFS_Number_Out (A) >= DFS_Number_Out(B);
}

A_Dominated_by_B (node A, node B)
{
  return DFS_Number_In(A) >= DFS_Number_In(B)
         && DFS_Number_Out (A) <= DFS_Number_Out(B);
}   
Return TRUE in case BB1 is dominated by BB2.   

References et_node::dfs_num_in, et_node::dfs_num_out, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_OK, et_below(), and gcc_checking_assert.

Referenced by add_autoinc_candidates(), add_to_dst_predicate_list(), add_to_predicate_list(), adjust_debug_stmts_now(), autofdo::afdo_find_equiv_class(), all_phi_incrs_profitable_1(), all_uses_feed_or_dominated_by_stmt(), analyze_insns_in_loop(), and_comparisons_1(), back_propagate_equivalences(), bb_in_region(), bb_loop_header_p(), dom_walker::bb_reachable(), branch_removable_p(), can_dup_for_shrink_wrapping(), can_get_prologue(), can_move_invariant_reg(), can_track_predicate_on_edge(), check_dependency(), check_exit_phi(), check_name(), check_simple_exit(), chk_uses(), cleanup_tree_cfg_noloop(), uninit_analysis::collect_phi_def_edges(), compute_access_range(), compute_added_num_insns(), compute_always_reached(), compute_live_loop_exits(), compute_merit(), convert_to_divmod(), def_dominates_uses(), deps_ok_for_redirect_from_bb_to_bb(), destroy_loop(), do_invalidate(), do_not_sink(), do_rpo_vn_1(), do_warn_aggressive_loop_optimizations(), dominated_by_forbidden(), dominated_by_p_w_unex(), duplicate_loop_body_to_header_edge(), easy_exit_values(), empty_bb_without_guard_p(), execute_cse_conv_1(), execute_sm_if_changed(), expr_invariant_in_region_p(), extract_true_false_controlled_edges(), factor_out_conditional_operation(), fill_always_executed_in_1(), ranger_cache::fill_block_cache(), fill_sons_in_loop(), find_always_executed_bbs(), find_basis_for_base_expr(), find_basis_for_candidate(), find_control_dep_blocks(), find_if_case_2(), find_loop_guard(), find_single_drs(), find_subloop_latch_edge_by_ivs(), fix_loop_bb_probability(), flow_loop_nodes_find(), follow_outer_ssa_edges(), fully_replaceable(), get_cond_invariant_branch(), get_continuation_for_phi(), get_control_equiv_head_block(), get_loop_latch_edges(), get_representative_for(), gimple_duplicate_seme_region(), glb_enum_p(), hoist_guard(), hoist_memory_references(), idx_infer_loop_bounds(), if_convertible_bb_p(), if_convertible_loop_p_1(), ifcvt_available_on_edge_p(), infer_loop_bounds_from_undefined(), uninit_analysis::init_use_preds(), insert_initializers(), insert_into_preds_of_block(), insert_phi_nodes(), insert_updated_phi_nodes_for(), insn_dominated_by_p(), instantiate_scev_name(), interpret_rhs_expr(), invariant_for_use(), is_feasible_trace(), is_maybe_undefined(), iv_get_reaching_def(), just_once_each_iteration_p(), latch_dominated_by_data_ref(), loop_iter_phi_semi_invariant_p(), mark_aliased_reaching_defs_necessary_1(), mark_irreducible_loops(), mark_loops_in_oacc_kernels_region(), may_eliminate_iv(), maybe_record_sincos(), maybe_skip_until(), mfb_keep_latches(), move_early_exit_stmts(), move_sese_region_to_fn(), number_of_iterations_exit_assumptions(), optimize_range_tests_var_bound(), or_comparisons_1(), pcom_stmt_dominates_stmt_p(), phi_add_costs_1(), phivn_valid_p(), place_prologue_for_one_component(), predict_loops(), predict_paths_for_bb(), predict_paths_leading_to_edge(), dom_walker::propagate_unreachable_to_edges(), propagate_with_phi(), prune_bbs_to_update_dominators(), prune_clobbered_mems(), ranger_cache::range_from_dom(), fold_using_range::range_of_phi(), reachable_at_most_once(), reassoc_stmt_dominates_stmt_p(), recompute_dominator(), record_estimate(), record_increment(), record_nonwrapping_iv(), remove_edge_and_dominated_blocks(), remove_forwarder_block_with_phi(), remove_path(), ranger_cache::resolve_dom(), rewrite_blocks(), rewrite_debug_stmt_uses(), rpe_enum_p(), scev_var_range_cant_overflow(), select_best_block(), set_cond_stmt_execution_predicate(), set_livein_block(), set_switch_stmt_execution_predicate(), simple_control_dep_chain(), single_pred_edge_ignoring_loop_edges(), sink_code_in_bb(), pcom_worker::split_data_refs_to_components(), split_edge(), split_live_ranges_for_shrink_wrap(), split_loop(), split_loop_on_cond(), ssa_name_any_use_dominates_bb_p(), statement_sink_location(), stmt_after_inc_pos(), stmt_dominates_stmt_p(), pcom_worker::suitable_component_p(), thread_private_new_memory(), tm_log_add(), transaction_invariant_address_p(), translate_vuse_through_block(), tree_estimate_loop_size(), tree_estimate_probability_bb(), try_shrink_wrapping(), unroll_jam_possible_p(), update_debug_stmt(), update_dep_bb(), update_range_test(), update_rep_bb(), value_available_p(), vec_init_loop_exit_info(), vect_compute_data_ref_alignment(), vect_get_and_check_slp_defs(), vect_get_external_def_edge(), vect_loop_versioning(), vect_schedule_slp_node(), vect_slp_function(), vect_stmt_dominates_stmt_p(), verify_loop_structure(), verify_use(), ccp_propagate::visit_phi(), vn_nary_op_get_predicated_value(), vn_nary_op_insert_into(), vuse_semi_invariant_p(), warn_return_addr_local(), and warn_uninit_phi_uses().

◆ dot_dominance_tree() [1/2]

DEBUG_FUNCTION void dot_dominance_tree ( const char * fname,
enum cdi_direction dir )
Convenience wrapper around the above that dumps the dominance tree in
direction DIR to the file at path FNAME in dot form.   

References dot_dominance_tree(), errno, and fopen.

◆ dot_dominance_tree() [2/2]

DEBUG_FUNCTION void dot_dominance_tree ( FILE * f,
enum cdi_direction dir )
Dump the dominance tree in direction DIR to the file F in dot form.
This allows easily visualizing the tree using graphviz.   

References cfun, FOR_EACH_BB_FN, get_immediate_dominator(), and basic_block_def::index.

Referenced by dot_dominance_tree().

◆ first_dom_son()

◆ free_dominance_info() [1/2]

void free_dominance_info ( enum cdi_direction dir)

References cfun, and free_dominance_info().

◆ free_dominance_info() [2/2]

void free_dominance_info ( function * fn,
enum cdi_direction dir )
Free dominance information for direction DIR.   

References function::cfg, basic_block_def::dom, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_NONE, et_free_pools(), et_free_tree_force(), FOR_ALL_BB_FN, NULL, control_flow_graph::x_dom_computed, and control_flow_graph::x_n_bbs_in_dom_tree.

Referenced by autofdo::afdo_annotate_cfg(), autofdo::afdo_calculate_branch_prob(), analyze_function_body(), autofdo::auto_profile(), cfg_layout_finalize(), clean_up_after_unswitching(), cleanup_cfg(), cleanup_control_flow_pre(), simplify_using_ranges::cleanup_edges_and_switches(), compute_alignments(), create_parallel_loop(), cse_main(), delete_unmarked_insns(), do_reload(), do_ssa_ccp(), loop_distribution::execute(), execute_cleanup_eh_1(), execute_early_warn_uninitialized(), execute_function_todo(), execute_one_pass(), execute_pass_list(), execute_split_paths(), execute_tm_mark(), expand_all_functions(), expand_ifn_va_arg_1(), expand_thunk(), find_comparisons(), find_conditions(), find_moveable_pseudos(), fini_reassoc(), free_code_hoist_mem(), free_dominance_info(), fwprop_done(), cgraph_node::get_body(), gimple_lower_bitint(), gimple_ssa_isolate_erroneous_paths(), if_convert(), input_function(), ipa_analyze_node(), ipcp_transform_function(), ira(), make_forwarders_with_degenerate_phis(), oacc_do_neutering(), oacc_entry_exit_ok(), optimize_inline_calls(), perform_tree_ssa_dce(), symbol_table::process_new_functions(), rest_of_handle_combine(), rest_of_handle_dse(), simplify_gimple_switch_label_vec(), split_function(), split_live_ranges_for_shrink_wrap(), tail_merge_optimize(), fwd_jt_path_registry::thread_block_1(), transform_to_exit_first_loop_alt(), tree_estimate_probability(), tree_function_versioning(), tree_loop_unroll_and_jam(), tree_optimize_tail_calls_1(), tree_profiling(), tree_ssa_split_loops(), try_shrink_wrapping(), try_shrink_wrapping_separate(), unsplit_eh_edges(), back_jt_path_registry::update_cfg(), verify_loop_structure(), verify_ssa(), and pair_fusion::~pair_fusion().

◆ free_dominance_info_for_region()

void free_dominance_info_for_region ( function * fn,
enum cdi_direction dir,
vec< basic_block > region )

◆ get_all_dominated_blocks()

auto_vec< basic_block > get_all_dominated_blocks ( enum cdi_direction dir,
basic_block bb )
Returns the list of basic blocks including BB dominated by BB, in the
direction DIR.  The vector will be sorted in preorder.   

References get_dominated_to_depth().

Referenced by delete_unreachable_blocks(), eliminate_unnecessary_stmts(), hoist_code(), oacc_entry_exit_ok(), remove_edge_and_dominated_blocks(), and slpeel_tree_duplicate_loop_to_edge_cfg().

◆ get_dominated_by()

auto_vec< basic_block > get_dominated_by ( enum cdi_direction dir,
basic_block bb )
Returns the list of basic blocks immediately dominated by BB, in the
direction DIR.   

References basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), gcc_checking_assert, and et_node::son.

Referenced by autofdo::afdo_find_equiv_class(), duplicate_loop_body_to_header_edge(), and unroll_loop_runtime_iterations().

◆ get_dominated_by_region()

auto_vec< basic_block > get_dominated_by_region ( enum cdi_direction dir,
basic_block * region,
unsigned n_region )
Returns the list of basic blocks that are immediately dominated (in
direction DIR) by some block between N_REGION ones stored in REGION,
except for blocks in the REGION itself.   

References first_dom_son(), basic_block_def::flags, i, and next_dom_son().

Referenced by gimple_duplicate_seme_region(), gimple_duplicate_sese_tail(), and move_sese_region_to_fn().

◆ get_dominated_to_depth()

auto_vec< basic_block > get_dominated_to_depth ( enum cdi_direction dir,
basic_block bb,
int depth )
Returns the list of basic blocks including BB dominated by BB, in the
direction DIR up to DEPTH in the dominator tree.  The DEPTH of zero will
produce a vector containing all dominated blocks.  The vector will be sorted
in preorder.   

References first_dom_son(), i, and next_dom_son().

Referenced by get_all_dominated_blocks(), and hoist_code().

◆ get_immediate_dominator()

basic_block get_immediate_dominator ( enum cdi_direction dir,
basic_block bb )
Return the immediate dominator of basic block BB.   

References et_node::data, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), et_node::father, gcc_checking_assert, and NULL.

Referenced by add_to_predicate_list(), strlen_pass::before_dom_children(), uncprop_dom_walker::before_dom_children(), bound_difference(), can_remove_asan_check(), compute_avail(), compute_bb_predicates(), compute_control_dep_chain(), compute_control_dep_chain_pdom(), compute_dominance_frontiers(), copy_bbs(), debug_dominance_info(), determine_max_movement(), determine_value_range(), dot_dominance_tree(), expand_omp_for_generic(), expand_omp_taskloop_for_outer(), fill_always_executed_in_1(), find_block_to_duplicate_for_splitting_paths(), find_control_dep_blocks(), control_dependences::find_control_dependence(), find_dominating_aa_status(), equiv_oracle::find_equiv_dom(), dom_oracle::find_relation_dom(), tree_switch_conversion::switch_conversion::gen_inbound_check(), get_continuation_for_phi(), get_control_equiv_head_block(), get_live_virtual_operand_on_edge(), gsi_prev_dom_bb_nondebug(), hoist_guard(), imm_dom_path_with_freeing_call(), uninit_analysis::init_from_phi_def(), uninit_analysis::init_use_preds(), insert(), is_feasible_trace(), move_computations_worker(), move_sese_region_to_fn(), place_prologue_for_one_component(), dom_ranger::pre_bb(), propagate_necessity(), propagate_with_phi(), prune_unused_phi_nodes(), dom_oracle::query(), ranger_cache::range_from_dom(), record_equivalences_from_incoming_edge(), dom_oracle::register_transitives(), remove_edge_and_dominated_blocks(), remove_forwarder_block(), remove_forwarder_block_with_phi(), remove_path(), ranger_cache::resolve_dom(), select_best_block(), simple_control_dep_chain(), simplify_using_initial_conditions(), slpeel_tree_duplicate_loop_to_edge_cfg(), split_edge(), split_live_ranges_for_shrink_wrap(), statement_sink_location(), translate_vuse_through_block(), try_shrink_wrapping(), vect_do_peeling(), vect_loop_dist_alias_call(), verify_dominators(), vn_phi_eq(), vn_phi_insert(), vn_phi_lookup(), and warn_uninitialized_vars().

◆ iterate_fix_dominators()

void iterate_fix_dominators ( enum cdi_direction dir,
vec< basic_block > & bbs,
bool conservative )

◆ nearest_common_dominator()

◆ nearest_common_dominator_for_set()

basic_block nearest_common_dominator_for_set ( enum cdi_direction dir,
bitmap blocks )
Find the nearest common dominator for the basic blocks in BLOCKS,
using dominance direction DIR.   

References BASIC_BLOCK_FOR_FN, bitmap_first_set_bit(), cfun, EXECUTE_IF_SET_IN_BITMAP, i, and nearest_common_dominator().

Referenced by deps_ok_for_redirect_from_bb_to_bb(), hoist_code(), insert_updated_phi_nodes_for(), split_live_ranges_for_shrink_wrap(), and update_ssa().

◆ new_zero_array()

template<typename T >
T * new_zero_array ( unsigned num)
inline
Allocate and zero-initialize NUM elements of type T (T must be a
POD-type).  Note: after transition to C++11 or later,
`x = new_zero_array <T> (num);' can be replaced with
`x = new T[num] {};'.   

◆ next_dom_son()

◆ prune_bbs_to_update_dominators()

static void prune_bbs_to_update_dominators ( vec< basic_block > & bbs,
bool conservative )
static
Use simple heuristics (see iterate_fix_dominators) to determine dominators
of BBS.  We assume that all the immediate dominators except for those of the
blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
currently recorded immediate dominators of blocks in BBS really dominate the
blocks.  The basic blocks for that we determine the dominator are removed
from BBS.   

References CDI_DOMINATORS, cfun, dominated_by_p(), ENTRY_BLOCK_PTR_FOR_FN, find_edge(), FOR_EACH_EDGE, gcc_assert, i, nearest_common_dominator(), NULL, basic_block_def::preds, set_immediate_dominator(), single_pred(), and single_pred_p().

Referenced by iterate_fix_dominators().

◆ recompute_dominator()

basic_block recompute_dominator ( enum cdi_direction dir,
basic_block bb )
Determine immediate dominator (or postdominator, according to DIR) of BB,
assuming that dominators of other blocks are correct.  We also use it to
recompute the dominators in a restricted area, by iterating it until it
reaches a fixed point.   

References CDI_DOMINATORS, dom_computed, dom_convert_dir_to_idx(), dominated_by_p(), FOR_EACH_EDGE, gcc_checking_assert, nearest_common_dominator(), NULL, basic_block_def::preds, and basic_block_def::succs.

Referenced by destroy_loop(), determine_dominators_for_sons(), doloop_modify(), edge_before_returns_twice_call(), execute_sm_if_changed(), expand_omp_for_generic(), expand_omp_for_static_chunk(), expand_omp_for_static_nochunk(), expand_omp_taskloop_for_inner(), expand_omp_taskloop_for_outer(), and iterate_fix_dominators().

◆ redirect_immediate_dominators()

◆ root_of_dom_tree()

static basic_block root_of_dom_tree ( enum cdi_direction dir,
basic_block bb )
static
Returns root of the dominance tree in the direction DIR that contains
BB.   

References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), and et_root().

Referenced by determine_dominators_for_sons(), and iterate_fix_dominators().

◆ set_dom_info_availability()

void set_dom_info_availability ( enum cdi_direction dir,
enum dom_state new_state )
Set the dominance availability for dominance info DIR to NEW_STATE.   

References dom_computed, and dom_convert_dir_to_idx().

Referenced by cleanup_control_flow_pre(), and verify_ssa().

◆ set_immediate_dominator()

void set_immediate_dominator ( enum cdi_direction dir,
basic_block bb,
basic_block dominated_by )
Set the immediate dominator of the block possibly removing
existing edge.  NULL can be used to remove any edge.   

References et_node::data, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), et_node::father, and gcc_checking_assert.

Referenced by branch_fixup(), rt_bb_visited::check(), combine_blocks(), copy_bbs(), create_cond_insert_point(), create_empty_if_region_on_edge(), create_empty_loop_on_edge(), destroy_loop(), determine_dominators_for_sons(), doloop_modify(), duplicate_loop_body_to_header_edge(), edge_before_returns_twice_call(), execute_sm_if_changed(), expand_complex_div_wide(), expand_omp_for_generic(), expand_omp_for_init_counts(), expand_omp_for_init_vars(), expand_omp_for_ordered_loops(), expand_omp_for_static_chunk(), expand_omp_for_static_nochunk(), expand_omp_ordered_sink(), expand_omp_sections(), expand_omp_simd(), expand_omp_target(), expand_omp_taskloop_for_inner(), expand_omp_taskloop_for_outer(), expand_omp_taskreg(), expand_parallel_call(), extract_omp_for_update_vars(), force_nonfallthru(), tree_switch_conversion::switch_conversion::gen_inbound_check(), gimple_duplicate_seme_region(), gimple_duplicate_sese_tail(), gimple_lower_bitint(), gsi_insert_finally_seq_after_call(), hoist_guard(), insert_check_and_trap(), insert_cond_bb(), rt_bb_visited::insert_exit_check_on_edge(), iterate_fix_dominators(), lv_adjust_loop_entry_edge(), move_sese_in_condition(), move_sese_region_to_fn(), optimize_mask_stores(), prune_bbs_to_update_dominators(), redirect_edge_and_branch_force(), remove_forwarder_block(), remove_forwarder_block_with_phi(), shrink_wrap_one_built_in_call_with_conds(), slpeel_add_loop_guard(), slpeel_tree_duplicate_loop_to_edge_cfg(), split_block_1(), split_edge(), ubsan_expand_null_ifn(), ubsan_expand_ptr_ifn(), unloop_loops(), unroll_loop_runtime_iterations(), vect_do_peeling(), and vect_loop_versioning().

◆ verify_dominators()

DEBUG_FUNCTION void verify_dominators ( cdi_direction dir)