#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"
Typedefs | |
| typedef unsigned int | TBB |
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()
| void add_to_dominance_info | ( | enum cdi_direction | dir, |
| basic_block | bb ) |
References basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_new_tree(), gcc_checking_assert, and n_bbs_in_dom_tree.
Referenced by create_basic_block_1().
◆ assign_dfs_numbers()
|
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 |
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 |
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_FUNCTION void debug_dominance_info | ( | cdi_direction | dir | ) |
References cfun, FOR_EACH_BB_FN, get_immediate_dominator(), and basic_block_def::index.
◆ 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 |
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()
| void delete_from_dominance_info | ( | enum cdi_direction | dir, |
| basic_block | bb ) |
References basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_free_tree(), gcc_checking_assert, n_bbs_in_dom_tree, and NULL.
Referenced by delete_basic_block(), merge_blocks(), and move_block_to_fn().
◆ determine_dominators_for_sons()
|
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()
|
inlinestatic |
Map dominance calculation type to array index used for various dominance information arrays. This version is simple -- it will need to be modified, obviously, if additional values are added to cdi_direction.
References CDI_DOMINATORS, CDI_POST_DOMINATORS, and gcc_checking_assert.
Referenced by add_to_dominance_info(), bb_dom_dfs_in(), bb_dom_dfs_out(), calculate_dominance_info(), calculate_dominance_info_for_region(), compute_dom_fast_query(), compute_dom_fast_query_in_region(), delete_from_dominance_info(), dom_info_state(), dominated_by_p(), first_dom_son(), free_dominance_info(), free_dominance_info_for_region(), get_dominated_by(), get_immediate_dominator(), iterate_fix_dominators(), nearest_common_dominator(), next_dom_son(), recompute_dominator(), redirect_immediate_dominators(), root_of_dom_tree(), set_dom_info_availability(), and set_immediate_dominator().
◆ 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(), tree_switch_conversion::switch_conversion::exp_index_transform(), 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(), insert_trap(), 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]
| enum dom_state dom_info_state | ( | function * | fn, |
| enum cdi_direction | dir ) |
Return dominance availability for dominance info DIR.
References function::cfg, dom_convert_dir_to_idx(), DOM_NONE, and control_flow_graph::x_dom_computed.
Referenced by back_propagate_equivalences(), cleanup_control_flow_pre(), dom_info_available_p(), dom_info_state(), execute_function_todo(), find_if_header(), fix_loop_structure(), gimple_verify_flow_info(), split_edge(), substitute_and_fold_engine::substitute_and_fold(), update_ssa(), and verify_ssa().
◆ 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(), ifcombine_mark_ssa_name(), 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_factor_profitable(), is_feasible_trace(), 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()
| basic_block first_dom_son | ( | enum cdi_direction | dir, |
| basic_block | bb ) |
Returns the first son of BB in the dominator or postdominator tree as determined by DIR.
References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), NULL, and et_node::son.
Referenced by build_omp_regions_1(), compute_avail(), debug_dominance_tree_1(), delete_unreachable_blocks(), do_reassoc(), eliminate_unnecessary_stmts(), fill_always_executed_in_1(), fill_sons_in_loop(), gather_blocks_in_sese_region(), get_dominated_by_region(), get_dominated_to_depth(), ipa_tm_propagate_irr(), place_prologue_for_one_component(), predict_paths_for_bb(), prepare_block_for_update(), remove_edge_and_dominated_blocks(), remove_path(), sanopt_optimize_walker(), scale_dominated_blocks_in_loop(), scale_strictly_dominated_blocks(), sink_code_in_bb(), slpeel_tree_duplicate_loop_to_edge_cfg(), update_dominators_in_loop(), vect_do_peeling(), vect_loop_versioning(), and dom_walker::walk().
◆ 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_explicit_erroneous_behavior(), 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(), 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 ) |
Free dominance information for direction DIR in region REGION.
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_EACH_VEC_ELT, i, NULL, control_flow_graph::x_dom_computed, and control_flow_graph::x_n_bbs_in_dom_tree.
Referenced by if_convertible_loop_p_1().
◆ 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 ) |
Recompute dominance information for basic blocks in the set BBS. The function assumes that the immediate dominators of all the other blocks in CFG are correct, and that there are no unreachable blocks. If CONSERVATIVE is true, we additionally assume that all the ancestors of a block of BBS in the current dominance tree dominate it.
References add_edge(), BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, CDI_DOMINATORS, cfun, determine_dominators_for_sons(), dom_computed, dom_convert_dir_to_idx(), ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, FOR_EACH_VEC_ELT, free(), free_graph(), g, gcc_checking_assert, graphds_domtree(), i, map, new_graph(), NULL, basic_block_def::preds, prune_bbs_to_update_dominators(), recompute_dominator(), root_of_dom_tree(), set_immediate_dominator(), timevar_pop(), timevar_push(), and y.
Referenced by tree_switch_conversion::switch_conversion::exp_index_transform(), tree_switch_conversion::switch_conversion::gen_inbound_check(), gimple_duplicate_seme_region(), gimple_duplicate_sese_tail(), make_forwarder_block(), remove_edge_and_dominated_blocks(), remove_path(), slpeel_tree_duplicate_loop_to_edge_cfg(), unroll_loop_runtime_iterations(), update_dominators_in_loop(), and vect_do_peeling().
◆ nearest_common_dominator()
| basic_block nearest_common_dominator | ( | enum cdi_direction | dir, |
| basic_block | bb1, | ||
| basic_block | bb2 ) |
Find first basic block in the tree dominating both BB1 and BB2.
References et_node::data, basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), et_nca(), and gcc_checking_assert.
Referenced by determine_dominators_for_sons(), dse_classify_store(), duplicate_loop_body_to_header_edge(), insert_bb(), last_always_executed_block(), ncd_for_two_cands(), nearest_common_dominator_for_set(), nearest_common_dominator_of_uses(), prune_bbs_to_update_dominators(), recompute_dominator(), remove_forwarder_block(), remove_forwarder_block_with_phi(), try_shrink_wrapping(), and vect_loop_dist_alias_call().
◆ 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()
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()
| basic_block next_dom_son | ( | enum cdi_direction | dir, |
| basic_block | bb ) |
Returns the next dominance son after BB in the dominator or postdominator tree as determined by DIR, or NULL if it was the last one.
References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), et_node::father, NULL, et_node::right, and et_node::son.
Referenced by build_omp_regions_1(), compute_avail(), debug_dominance_tree_1(), do_reassoc(), fill_always_executed_in_1(), fill_sons_in_loop(), gather_blocks_in_sese_region(), get_dominated_by_region(), get_dominated_to_depth(), ipa_tm_propagate_irr(), place_prologue_for_one_component(), predict_paths_for_bb(), prepare_block_for_update(), remove_edge_and_dominated_blocks(), remove_path(), sanopt_optimize_walker(), scale_dominated_blocks_in_loop(), scale_strictly_dominated_blocks(), slpeel_tree_duplicate_loop_to_edge_cfg(), update_dominators_in_loop(), vect_do_peeling(), vect_loop_versioning(), and dom_walker::walk().
◆ prune_bbs_to_update_dominators()
|
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()
| void redirect_immediate_dominators | ( | enum cdi_direction | dir, |
| basic_block | bb, | ||
| basic_block | to ) |
Redirect all edges pointing to BB to TO.
References basic_block_def::dom, dom_computed, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), gcc_checking_assert, and et_node::son.
Referenced by tree_switch_conversion::switch_conversion::exp_index_transform(), tree_switch_conversion::switch_conversion::gen_inbound_check(), merge_blocks(), and split_block_1().
◆ root_of_dom_tree()
|
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(), tree_switch_conversion::switch_conversion::exp_index_transform(), 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 | ) |
Verify invariants of dominator structure.
References cfun, dom_info_available_p(), error(), FOR_EACH_BB_FN, gcc_assert, get_immediate_dominator(), and basic_block_def::index.
Referenced by gimple_verify_flow_info(), and verify_loop_structure().
