- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | dom_info |
Typedefs | |
| typedef unsigned int | TBB |
| typedef unsigned int TBB |
Calculate (post)dominators in slightly super-linear time. Copyright (C) 2000-2013 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
| void add_to_dominance_info | ( | ) |
References basic_block_def::dom, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, and et_new_tree().
|
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::right, and et_node::son.
Referenced by compute_dom_fast_query().
| unsigned bb_dom_dfs_in | ( | ) |
Returns the entry dfs number for basic block BB, in the direction DIR.
References et_node::dfs_num_in, basic_block_def::dom, dom_convert_dir_to_idx(), and DOM_OK.
| unsigned bb_dom_dfs_out | ( | ) |
Returns the exit dfs number for basic block BB, in the direction DIR.
References et_node::dfs_num_out, basic_block_def::dom, dom_convert_dir_to_idx(), and DOM_OK.
|
static |
Referenced by calculate_dominance_info(), and verify_dominators().
|
static |
The main entry for calculating the DFS tree or forest. DI is our working structure and REVERSE is true, if we are interested in the reverse flow graph. In that case the result is not necessarily a tree but a forest, because there may be nodes from which the EXIT_BLOCK is unreachable.
References bitmap_set_bit(), calc_dfs_tree_nonrec(), dfs_find_deadend(), dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, dom_info::fake_exit_edge, basic_block_def::index, dom_info::nodes, and basic_block_def::succs.
|
static |
Referenced by calc_dfs_tree().
|
static |
The nonrecursive variant of creating a DFS tree. DI is our working structure, BB the starting basic block for this tree and REVERSE is true, if predecessors should be visited instead of successors of a node. After this is done all nodes reachable from BB were visited, have assigned their dfs number and are linked together to form a tree.
References edge_def::dest, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, ei_edge(), ei_end_p(), ei_next(), free(), basic_block_def::index, basic_block_def::preds, edge_def::src, stack, and basic_block_def::succs.
|
static |
Referenced by calculate_dominance_info(), and verify_dominators().
|
static |
This calculates the immediate dominators (or post-dominators if REVERSE is true). DI is our working structure and should hold the DFS forest. On return the immediate dominator to node V is in di->dom[V].
References bitmap_bit_p(), dom_info::bucket, edge_def::dest, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dom, ei_edge(), ei_end_p(), ei_next(), eval(), dom_info::fake_exit_edge, basic_block_def::index, edge_iterator::index, dom_info::key, link_roots(), dom_info::next_bucket, dom_info::nodes, basic_block_def::preds, edge_def::src, and basic_block_def::succs.
| void calculate_dominance_info | ( | ) |
The main entry point into this module. DIR is set depending on whether we want to compute dominators or postdominators.
References calc_dfs_tree(), calc_idoms(), CDI_POST_DOMINATORS, compute_dom_fast_query(), dom_info::dfs_order, dom_info::dfs_to_bb, dom_info::dom, basic_block_def::dom, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_NO_FAST_QUERY, DOM_OK, et_new_tree(), et_set_father(), free_dom_info(), init_dom_info(), timevar_pop(), and timevar_push().
Referenced by compress(), and eval().
|
static |
Compress the path from V to the root of its set and update path_min at the same time. After compress(di, V) set_chain[V] is the root of the set V is in and path_min[V] is the node with the smallest key[] value on the path from V to that root.
References compress(), dom_info::key, dom_info::path_min, and dom_info::set_chain.
|
static |
Compute the data necessary for fast resolving of dominator queries in a static dominator tree.
References assign_dfs_numbers(), basic_block_def::dom, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_OK, and et_node::father.
Referenced by calculate_dominance_info().
| void debug_dominance_info | ( | enum | cdi_direction | ) |
| DEBUG_FUNCTION void debug_dominance_info | ( | ) |
References get_immediate_dominator(), and basic_block_def::index.
| void debug_dominance_tree | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
| DEBUG_FUNCTION void debug_dominance_tree | ( | ) |
Prints to stderr representation of the dominance tree (for direction DIR) rooted in ROOT.
References 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 first, first_dom_son(), indent, basic_block_def::index, next_dom_son(), and et_node::son.
Referenced by debug_dominance_tree().
| void delete_from_dominance_info | ( | ) |
References basic_block_def::dom, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, and et_free_tree().
|
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 bitmap_set_bit(), CDI_DOMINATORS, vertex::component, dom, free(), graphds_scc(), identify_vertices(), nearest_common_dominator(), basic_block_def::preds, recompute_dominator(), root_of_dom_tree(), set_immediate_dominator(), si, edge_def::src, and graph::vertices.
Referenced by iterate_fix_dominators().
|
static |
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, and CDI_POST_DOMINATORS.
Referenced by add_to_dominance_info(), bb_dom_dfs_in(), bb_dom_dfs_out(), calculate_dominance_info(), compute_dom_fast_query(), delete_from_dominance_info(), dom_info_available_p(), dom_info_state(), dominated_by_p(), first_dom_son(), free_dominance_info(), 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().
| bool dom_info_available_p | ( | ) |
Returns true if dominance information for direction DIR is available.
References dom_convert_dir_to_idx(), and DOM_NONE.
| enum dom_state dom_info_state | ( | ) |
Return dominance availability for dominance info DIR.
References dom_convert_dir_to_idx().
| bool dominated_by_p | ( | ) |
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(A)
&& 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_convert_dir_to_idx(), DOM_OK, and et_below().
Referenced by calc_idoms(), and gimplify_expr().
|
inlinestatic |
Compress the path from V to the set root of V if needed (when the root has changed since the last call). Returns the node with the smallest key[] value on the path from V to the root.
References compress(), dom_info::key, dom_info::path_min, and dom_info::set_chain.
| basic_block first_dom_son | ( | ) |
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(), and et_node::son.
|
static |
Referenced by calculate_dominance_info(), and verify_dominators().
|
static |
Free all allocated memory in DI, but not DI itself.
References dom_info::bucket, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dom, dom_info::fake_exit_edge, free(), dom_info::key, dom_info::next_bucket, dom_info::path_min, dom_info::set_chain, dom_info::set_child, and dom_info::set_size.
| void free_dominance_info | ( | ) |
Free dominance information for direction DIR.
References basic_block_def::dom, dom_convert_dir_to_idx(), dom_info_available_p(), DOM_NONE, et_free_pools(), and et_free_tree_force().
| vec<basic_block> get_all_dominated_blocks | ( | ) |
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().
| vec<basic_block> get_dominated_by | ( | ) |
Returns the list of basic blocks immediately dominated by BB, in the direction DIR.
References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), et_node::right, et_node::son, and vNULL.
| 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 dom, first_dom_son(), basic_block_def::flags, next_dom_son(), and vNULL.
Referenced by gimple_duplicate_sese_region(), gimple_duplicate_sese_tail(), and move_sese_region_to_fn().
| vec<basic_block> get_dominated_to_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(), next_dom_son(), et_node::son, and vNULL.
| basic_block get_immediate_dominator | ( | ) |
Return the immediate dominator of basic block BB.
References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), and et_node::father.
|
static |
Referenced by calculate_dominance_info(), and verify_dominators().
|
static |
Allocate all needed memory in a pessimistic fashion (so we round up). This initializes the contents of DI, which already must be allocated.
References dom_info::bucket, CDI_DOMINATORS, CDI_POST_DOMINATORS, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, dom_info::dom, dom_info::fake_exit_edge, dom_info::key, dom_info::next_bucket, dom_info::nodes, dom_info::path_min, dom_info::set_chain, dom_info::set_child, and dom_info::set_size.
| 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_set_bit(), CDI_DOMINATORS, pointer_map< T >::contains(), vertex::data, determine_dominators_for_sons(), dom, dom_convert_dir_to_idx(), free(), free_graph(), g, graphds_domtree(), pointer_map< T >::insert(), map, graph::n_vertices, new_graph(), basic_block_def::preds, prune_bbs_to_update_dominators(), recompute_dominator(), root_of_dom_tree(), set_immediate_dominator(), edge_def::src, and graph::vertices.
Referenced by emit_case_bit_tests(), gen_inbound_check(), gimple_duplicate_sese_region(), gimple_duplicate_sese_tail(), make_forwarder_block(), remove_edge_and_dominated_blocks(), remove_path(), unroll_loop_runtime_iterations(), and update_dominators_in_loop().
Referenced by calc_idoms().
|
static |
This essentially merges the two sets of V and W, giving a single set with the new root V. The internal representation of these disjoint sets is a balanced tree. Currently link(V,W) is only used with V being the parent of W.
References dom_info::key, dom_info::path_min, dom_info::set_chain, dom_info::set_child, and dom_info::set_size.
| basic_block nearest_common_dominator | ( | ) |
Find first basic block in the tree dominating both BB1 and BB2.
References et_node::data, basic_block_def::dom, dom_convert_dir_to_idx(), and et_nca().
| basic_block nearest_common_dominator_for_set | ( | ) |
Find the nearest common dominator for the basic blocks in BLOCKS, using dominance direction DIR.
References bitmap_first_set_bit(), dom, first, and nearest_common_dominator().
| basic_block next_dom_son | ( | ) |
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, et_node::right, and et_node::son.
|
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, dom, dominated_by_p(), find_edge(), nearest_common_dominator(), basic_block_def::preds, set_immediate_dominator(), single, single_pred(), single_pred_p(), and edge_def::src.
Referenced by iterate_fix_dominators().
| basic_block recompute_dominator | ( | ) |
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, edge_def::dest, dom_convert_dir_to_idx(), dominated_by_p(), nearest_common_dominator(), basic_block_def::preds, edge_def::src, and basic_block_def::succs.
| 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_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), and et_node::son.
Referenced by merge_blocks(), and split_block().
|
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().
| void set_dom_info_availability | ( | ) |
Set the dominance availability for dominance info DIR to NEW_STATE.
References dom_convert_dir_to_idx().
| 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_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), and et_node::father.
Referenced by 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_to_header_edge(), emit_case_bit_tests(), execute_sm_if_changed(), expand_complex_div_wide(), expand_omp_for_generic(), expand_omp_for_init_counts(), expand_omp_for_static_chunk(), expand_omp_for_static_nochunk(), expand_omp_sections(), expand_omp_simd(), expand_parallel_call(), extract_omp_for_update_vars(), force_nonfallthru(), gen_inbound_check(), gimple_duplicate_sese_region(), gimple_duplicate_sese_tail(), hoist_edge_and_branch_if_true(), iterate_fix_dominators(), loopify(), lv_adjust_loop_entry_edge(), mf_build_check_statement_for(), move_sese_region_to_fn(), prune_bbs_to_update_dominators(), redirect_edge_and_branch_force(), remove_forwarder_block(), remove_forwarder_block_with_phi(), sched_create_recovery_edges(), set_prologue_iterations(), slpeel_add_loop_guard(), slpeel_tree_duplicate_loop_to_edge_cfg(), split_block(), split_edge(), translate_clast_for_loop(), unloop_loops(), and unroll_loop_runtime_iterations().
| DEBUG_FUNCTION void verify_dominators | ( | ) |
Verify invariants of dominator structure.
References calc_dfs_tree(), calc_idoms(), CDI_POST_DOMINATORS, dom_info::dfs_order, dom_info::dfs_to_bb, dom_info::dom, dom_info_available_p(), error(), free_dom_info(), get_immediate_dominator(), basic_block_def::index, and init_dom_info().
1.8.1.1