- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | depth_first_search_dsS |
Typedefs | |
| typedef struct depth_first_search_dsS * | depth_first_search_ds |
| typedef struct depth_first_search_dsS* depth_first_search_ds |
| void add_noreturn_fake_exit_edges | ( | void | ) |
This function will add a fake edge between any block which has no successors, and the exit block. Some data flow equations require these edges to exist.
Referenced by output_location(), and pre_insert_copies().
| void bitmap_intersection_of_preds | ( | ) |
Set the bitmap DST to the intersection of SRC of predecessors of basic block B.
| void bitmap_intersection_of_succs | ( | ) |
Intersection and union of preds/succs for sbitmap based data flow solvers. All four functions defined below take the same arguments: B is the basic block to perform the operation for. DST is the target sbitmap, i.e. the result. SRC is an sbitmap vector of size last_basic_block so that it can be indexed with basic block indices. DST may be (but does not have to be) SRC[B->index].
Set the bitmap DST to the intersection of SRC of successors of basic block B.
| void bitmap_union_of_preds | ( | ) |
Set the bitmap DST to the union of SRC of predecessors of basic block B.
| void bitmap_union_of_succs | ( | ) |
Set the bitmap DST to the union of SRC of successors of basic block B.
| void compute_dominance_frontiers | ( | ) |
|
static |
@verbatim
Compute dominance frontiers, ala Harvey, Ferrante, et al.
This algorithm can be found in Timothy Harvey's PhD thesis, at http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative dominance algorithms.
First, we identify each join point, j (any node with more than one incoming edge is a join point).
We then examine each predecessor, p, of j and walk up the dominator tree starting at p.
We stop the walk when we reach j's immediate dominator - j is in the dominance frontier of each of the nodes in the walk, except for j's immediate dominator. Intuitively, all of the rest of j's dominators are shared by j's predecessors as well. Since they dominate j, they will not have j in their dominance frontiers.
The number of nodes touched by this algorithm is equal to the size of the dominance frontiers, no more, no less.
References bitmap_copy(), bitmap_ones(), edge_def::dest, basic_block_def::index, simple_bitmap_def::popcount, simple_bitmap_def::size, and basic_block_def::succs.
| bitmap compute_idf | ( | ) |
Given a set of blocks with variable definitions (DEF_BLOCKS), return a bitmap with all the blocks in the iterated dominance frontier of the blocks in DEF_BLOCKS. DFS contains dominance frontier information as returned by compute_dominance_frontiers. The resulting set of blocks are the potential sites where PHI nodes are needed. The caller is responsible for freeing the memory allocated for the return value.
Each block can appear at most twice on the work-stack.
Seed the work list with all the blocks in DEF_BLOCKS. We use
vec::quick_push here for speed. This is safe because we know that
the number of definition blocks is no greater than the number of
basic blocks, which is the initial capacity of WORK_STACK. Pop a block off the worklist, add every block that appears in
the original block's DF that we have not already processed to
the worklist. Iterate until the worklist is empty. Blocks
which are added to the worklist are potential sites for
PHI nodes. Since the registration of NEW -> OLD name mappings is done
separately from the call to update_ssa, when updating the SSA
form, the basic blocks where new and/or old names are defined
may have disappeared by CFG cleanup calls. In this case,
we may pull a non-existing block from the work stack.
| void connect_infinite_loops_to_exit | ( | void | ) |
This function adds a fake edge between any infinite loops to the exit block. Some optimizations require a path from each node to the exit node. See also Morgan, Figure 3.10, pp. 82-83. The current implementation is ugly, not attempting to minimize the number of inserted fake edges. To reduce the number of fake edges to insert, add fake edges from _innermost_ loops containing only nodes not reachable from the exit block.
Perform depth-first search in the reverse graph to find nodes
reachable from the exit block. Repeatedly add fake edges, updating the unreachable nodes.
|
read |
Functions to access an edge list with a vector representation. Enough data is kept such that given an index number, the pred and succ that edge represents can be determined, or given a pred and a succ, its index number can be returned. This allows algorithms which consume a lot of memory to represent the normally full matrix of edge (pred,succ) with a single indexed vector, edge (EDGE_INDEX (pred, succ)), with no wasted space in the client code due to sparse flow graphs.
This functions initializes the edge list. Basically the entire flowgraph is processed, and all edges are assigned a number, and the data structure is filled in.
Determine the number of edges in the flow graph by counting successor
edges on each basic block. Follow successors of blocks, and register these edges.
References free().
Referenced by compute_insert_delete().
| int dfs_enumerate_from | ( | basic_block | bb, |
| int | reverse, | ||
| bool(*)(const_basic_block, const void *) | predicate, | ||
| basic_block * | rslt, | ||
| int | rslt_max, | ||
| const void * | data | ||
| ) |
Performs dfs search from BB over vertices satisfying PREDICATE; if REVERSE, go against direction of edges. Returns number of blocks found and their list in RSLT. RSLT can contain at most RSLT_MAX items.
A bitmap to keep track of visited blocks. Allocating it each time
this function is called is not possible, since dfs_enumerate_from
is often used on small (almost) disjoint parts of cfg (bodies of
loops), and allocating a large sbitmap would lead to quadratic
behavior. Resize the VISITED sbitmap if necessary.
Ensure that we increase the size of the sbitmap exponentially.
References bitmap_set_bit(), CDI_DOMINATORS, get_immediate_dominator(), basic_block_def::index, basic_block_def::preds, and edge_def::src.
Referenced by thread_single_edge().
| basic_block dfs_find_deadend | ( | ) |
Helper routine for inverted_post_order_compute flow_dfs_compute_reverse_execute, and the reverse-CFG deapth first search in dominance.c. BB has to belong to a region of CFG unreachable by inverted traversal from the exit. i.e. there's no control flow path from ENTRY to EXIT that contains this BB. This can happen in two cases - if there's an infinite loop or if there's a block that has no successor (call to a function with no return). Some RTL passes deal with this condition by calling connect_infinite_loops_to_exit () and/or add_noreturn_fake_exit_edges (). However, those methods involve modifying the CFG itself which may not be desirable. Hence, we deal with the infinite loop/no return cases by identifying a unique basic block that can reach all blocks in such a region by inverted traversal. This function returns a basic block that guarantees that all blocks in the region are reachable by starting an inverted traversal from the returned block.
References bitmap_set_bit(), basic_block_def::index, and basic_block_def::preds.
| edge find_edge | ( | ) |
Given PRED and SUCC blocks, return the edge which connects the blocks. If no such edge exists, return NULL.
References ei_next(), ei_safe_edge(), edge_def::flags, basic_block_def::preds, and remove_edge().
| int find_edge_index | ( | ) |
This routine will determine what, if any, edge there is between a specified predecessor and successor.
References remove_fake_predecessors().
|
inlinestatic |
Find the immediate postdominator PDOM of the specified basic block BLOCK. This function is necessary because some blocks have negative numbers.
References edge_def::flags, control_dependences::m_el, and control_dependences::set_control_dependence_map_bit().
| void find_unreachable_blocks | ( | void | ) |
Find unreachable blocks. An unreachable block will have 0 in the reachable bit in block->flags. A nonzero value indicates the block is reachable.
Clear all the reachability flags.
Add our starting points to the worklist. Almost always there will
be only one. It isn't inconceivable that we might one day directly
support Fortran alternate entry points. Mark the block reachable.
Iterate: find everything reachable from what we've already seen.
References basic_block_def::flags.
Referenced by replace_locals_op().
|
static |
Referenced by pre_and_rev_post_order_compute(), remove_fake_edges(), and remove_fake_exit_edges().
|
static |
Add the specified basic block to the top of the dfs data structures. When the search continues, it will start at the block.
|
static |
Continue the depth-first search through the reverse graph starting with the block at the stack's top and ending when the stack is empty. Visited nodes are marked. Returns an unvisited basic block, or NULL if there is none available.
Perform depth-first search on adjacent vertices.
Determine if there are unvisited basic blocks.
Referenced by remove_fake_exit_edges().
|
static |
|
static |
Destroy the data structures needed for depth-first search on the reverse graph.
|
static |
Referenced by remove_fake_edges().
|
static |
Compute the depth first search order on the _reverse_ graph and store in the array DFS_ORDER, marking the nodes visited in VISITED. Returns the number of nodes visited. The computation is split into three pieces: flow_dfs_compute_reverse_init () creates the necessary data structures. flow_dfs_compute_reverse_add_bb () adds a basic block to the data structures. The block will start the search. flow_dfs_compute_reverse_execute () continues (or starts) the search using the block on the top of the stack, stopping when the stack is empty. flow_dfs_compute_reverse_finish () destroys the necessary data structures. Thus, the user will probably call ..._init(), call ..._add_bb() to add a beginning basic block to the stack, call ..._execute(), possibly add another bb to the stack and again call ..._execute(), ..., and finally call _finish().
Initialize the data structures used for depth-first search on the reverse graph. If INITIALIZE_STACK is nonzero, the exit block is added to the basic block stack. DATA is the current depth-first search context. If INITIALIZE_STACK is nonzero, there is an element on the stack.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
References bitmap_clear(), and sbitmap_alloc().
| void free_edge_list | ( | ) |
This function free's memory associated with an edge list.
| int inverted_post_order_compute | ( | ) |
Compute the reverse top sort order of the inverted CFG i.e. starting from the exit block and following the edges backward (from successors to predecessors). This ordering can be used for forward dataflow problems among others. This function assumes that all blocks in the CFG are reachable from the ENTRY (but not necessarily from EXIT). If there's an infinite loop, a simple inverted traversal starting from the blocks with no successors can't visit all blocks. To solve this problem, we first do inverted traversal starting from the blocks with no successor. And if there's any block left that's not visited by the regular inverted traversal from EXIT, those blocks are in such problematic region. Among those, we find one block that has any visited predecessor (which is an entry into such a region), and start looking for a "dead end" from that block and do another inverted traversal from that block.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Put all blocks that have no successor into the initial work list.
Push the initial edge on to the stack.
The inverted traversal loop.
Look at the edge on the top of the stack.
Check if the predecessor has been visited yet.
Mark that we have visited the destination.
Since the predecessor node has been visited for the first
time, check its predecessors. Detect any infinite loop and activate the kludge.
Note that this doesn't check EXIT_BLOCK itself
since EXIT_BLOCK is always added after the outer do-while loop. Find an already visited predecessor.
No blocks are reachable from EXIT at all.
Find a dead-end from the ENTRY, and restart the iteration. The only case the below while fires is
when there's an infinite loop. EXIT_BLOCK is always included.
| bool mark_dfs_back_edges | ( | void | ) |
Mark the back edges in DFS traversal.
Return nonzero if a loop (natural or otherwise) is present.
Inspired by Depth_First_Search_PP described in:
Advanced Compiler Design and Implementation
Steven Muchnick
Morgan Kaufmann, 1997
and heavily borrowed from pre_and_rev_post_order_compute. Allocate the preorder and postorder number arrays.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors.
Referenced by draw_cfg_nodes().
| int post_order_compute | ( | int * | post_order, |
| bool | include_entry_exit, | ||
| bool | delete_unreachable | ||
| ) |
Compute reverse top sort order. This is computing a post order numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is true, unreachable blocks are deleted.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors. Delete the unreachable blocks if some were found and we are
supposed to do it.
References ei_next(), ei_one_before_end_p(), and basic_block_def::index.
| int pre_and_rev_post_order_compute | ( | int * | pre_order, |
| int * | rev_post_order, | ||
| bool | include_entry_exit | ||
| ) |
Like pre_and_rev_post_order_compute_fn but operating on the current function and asserting that all nodes were visited.
The number of nodes visited should be the number of blocks.
The number of nodes visited should be the number of blocks minus
the entry and exit blocks which are not visited here.
References bitmap_bit_p(), flow_dfs_compute_reverse_add_bb(), basic_block_def::index, basic_block_def::preds, depth_first_search_dsS::sp, edge_def::src, depth_first_search_dsS::stack, and depth_first_search_dsS::visited_blocks.
| int pre_and_rev_post_order_compute_fn | ( | struct function * | fn, |
| int * | pre_order, | ||
| int * | rev_post_order, | ||
| bool | include_entry_exit | ||
| ) |
Compute the depth first search order of FN and store in the array PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the reverse completion number for each node. Returns the number of nodes visited. A depth first search tries to get as far away from the starting point as quickly as possible. In case the function has unreachable blocks the number of nodes visited does not include them. pre_order is a really a preorder numbering of the graph. rev_post_order is really a reverse postorder numbering of the graph.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors. There are no successors for the DEST node so assign
its reverse completion number. There are no more successors for the SRC node
so assign its reverse completion number.
| DEBUG_FUNCTION void print_edge_list | ( | ) |
This function provides debug output showing an edge list.
References edge_def::dest, basic_block_def::index, edge_def::src, and basic_block_def::succs.
| void remove_fake_edges | ( | void | ) |
This routine will remove all fake edges from the flow graph. If we remove all fake successors, it will automatically remove all fake predecessors.
References flow_dfs_compute_reverse_add_bb(), and flow_dfs_compute_reverse_init().
| void remove_fake_exit_edges | ( | void | ) |
This routine will remove all fake edges to the EXIT_BLOCK.
References dfs_find_deadend(), flow_dfs_compute_reverse_add_bb(), flow_dfs_compute_reverse_execute(), and make_edge().
Referenced by pre_insert_copies().
|
static |
This routine will remove any fake predecessor edges for a basic block. When the edge is removed, it is also removed from whatever successor list it is in.
References make_single_succ_edge(), and basic_block_def::succs.
Referenced by find_edge_index().
| basic_block* single_pred_before_succ_order | ( | void | ) |
Returns the list of basic blocks in the function in an order that guarantees that if a block X has just a single predecessor Y, then Y is after X in the ordering.
Walk the predecessors of x as long as they have precisely one
predecessor and add them to the list, so that they get stored
after x.
| DEBUG_FUNCTION void verify_edge_list | ( | ) |
This function provides an internal consistency check of an edge list, verifying that all edges are present, and that there are no extra edges.
We've verified that all the edges are in the list, now lets make sure
there are no spurious edges in the list. This is an expensive check!
References edge_def::dest, basic_block_def::index, edge_def::src, and basic_block_def::succs.
1.8.1.1