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 workstack.
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 nonexisting 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. 8283. 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 depthfirst 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 reverseCFG 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 depthfirst 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 depthfirst 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 depthfirst 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 depthfirst search on the reverse graph. If INITIALIZE_STACK is nonzero, the exit block is added to the basic block stack. DATA is the current depthfirst search context. If INITIALIZE_STACK is nonzero, there is an element on the stack.
Allocate stack for backtracking 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 backtracking 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 dowhile loop.
Find an already visited predecessor.
No blocks are reachable from EXIT at all. Find a deadend 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 backtracking 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 backtracking 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 backtracking 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.