libFirm
 All Data Structures Functions Variables Typedefs Enumerations Enumerator Groups Pages
Dominance Information

The dominator information is stored in three fields of block nodes: More...

Functions

ir_nodeget_Block_idom (const ir_node *block)
 return immediate dominator of block More...
 
ir_nodeget_Block_ipostdom (const ir_node *block)
 return immediate postdominator of a block More...
 
int block_dominates (const ir_node *a, const ir_node *b)
 Check, if a block dominates another block. More...
 
int block_postdominates (const ir_node *a, const ir_node *b)
 Check, if a block post dominates another block. More...
 
int block_strictly_postdominates (const ir_node *a, const ir_node *b)
 Check, if a block strictly post dominates another block, i.e. More...
 
ir_nodeget_Block_dominated_first (const ir_node *block)
 Returns the first node in the list of nodes dominated by a given block. More...
 
ir_nodeget_Block_postdominated_first (const ir_node *bl)
 Returns the first node in the list of nodes postdominated by a given blcok. More...
 
ir_nodeget_Block_dominated_next (const ir_node *node)
 Returns the next node in a list of nodes which are dominated by some other node. More...
 
ir_nodeget_Block_postdominated_next (const ir_node *node)
 Returns the next node in a list of nodes which are postdominated by another node. More...
 
ir_nodeir_deepest_common_dominator (ir_node *block0, ir_node *block1)
 Returns the deepest common dominator of two blocks. More...
 
void dom_tree_walk (ir_node *n, irg_walk_func *pre, irg_walk_func *post, void *env)
 Visit all nodes in the dominator subtree of a given node. More...
 
void postdom_tree_walk (ir_node *n, irg_walk_func *pre, irg_walk_func *post, void *env)
 Visit all nodes in the post dominator subtree of a given node. More...
 
void dom_tree_walk_irg (ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 Walk over the dominator tree of an irg starting at the root. More...
 
void postdom_tree_walk_irg (ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 Walk over the post dominator tree of an irg starting at the root. More...
 
void compute_doms (ir_graph *irg)
 Computes the dominance relation for all basic blocks of a given graph. More...
 
void compute_postdoms (ir_graph *irg)
 Computes the post dominance relation for all basic blocks of a given graph. More...
 
void ir_compute_dominance_frontiers (ir_graph *irg)
 Compute the dominance frontiers for a given graph. More...
 
ir_node ** ir_get_dominance_frontier (const ir_node *block)
 Get the dominance frontier of a block. More...
 

Detailed Description

The dominator information is stored in three fields of block nodes:

We generally presume (like Tarjan) that endless loops do not exist. The implementation assumes a control dependency from End to loop header.

Function Documentation

int block_dominates ( const ir_node a,
const ir_node b 
)

Check, if a block dominates another block.

Parameters
aThe potential dominator block.
bThe potentially dominated block.
Returns
1, if a dominates b, else 0.
int block_postdominates ( const ir_node a,
const ir_node b 
)

Check, if a block post dominates another block.

Parameters
aThe potential post dominator block.
bThe potentially post dominated block.
Returns
1, if a post dominates b, else 0.
int block_strictly_postdominates ( const ir_node a,
const ir_node b 
)

Check, if a block strictly post dominates another block, i.e.

a != b.

Parameters
aThe potential post dominator block.
bThe potentially post dominated block.
Returns
1, if a strictly post dominates b, else 0.
void compute_doms ( ir_graph irg)

Computes the dominance relation for all basic blocks of a given graph.

Sets a flag in irg to "dom_consistent". If the control flow of the graph is changed this flag must be set to "dom_inconsistent". Does not compute dominator information for control dead code. Blocks not reachable from Start contain the following information:

idom = NULL;
dom_depth = -1;
pre_num = -1;

Also constructs outs information. As this information is correct after the run does not free the outs information.

void compute_postdoms ( ir_graph irg)

Computes the post dominance relation for all basic blocks of a given graph.

Sets a flag in irg to "dom_consistent". If the control flow of the graph is changed this flag must be set to "dom_inconsistent". Does not compute post dominator information for endless lops. Blocks not reachable from End contain the following information:

idom = NULL;
dom_depth = -1;
pre_num = -1;

Also constructs outs information. As this information is correct after the run does not free the outs information.

void dom_tree_walk ( ir_node n,
irg_walk_func pre,
irg_walk_func post,
void *  env 
)

Visit all nodes in the dominator subtree of a given node.

Call a pre-visitor before descending to the children and call a post-visitor after returning from them.

Parameters
nThe node to start walking from.
preThe pre-visitor callback.
postThe post-visitor callback.
envSome custom data passed to the visitors.
void dom_tree_walk_irg ( ir_graph irg,
irg_walk_func pre,
irg_walk_func post,
void *  env 
)

Walk over the dominator tree of an irg starting at the root.

Parameters
irgThe graph.
preA pre-visitor to call.
postA post-visitor to call.
envSome private data to give to the visitors.
ir_node* get_Block_dominated_first ( const ir_node block)

Returns the first node in the list of nodes dominated by a given block.

Each node keeps a list of nodes which it immediately dominates. The nodes are queued using the next pointer in the dom_info struct. Each node keeps a head of this list using the pointer first in the same structure.

Parameters
blockThe block for which to get the first node dominated by bl.
Returns
The first node dominated by bl.
ir_node* get_Block_dominated_next ( const ir_node node)

Returns the next node in a list of nodes which are dominated by some other node.

See Also
get_Block_dominated_first().
Parameters
nodeThe previous node.
Returns
The next node in this list or NULL if it was the last.
ir_node* get_Block_idom ( const ir_node block)

return immediate dominator of block

ir_node* get_Block_ipostdom ( const ir_node block)

return immediate postdominator of a block

ir_node* get_Block_postdominated_first ( const ir_node bl)

Returns the first node in the list of nodes postdominated by a given blcok.

ir_node* get_Block_postdominated_next ( const ir_node node)

Returns the next node in a list of nodes which are postdominated by another node.

void ir_compute_dominance_frontiers ( ir_graph irg)

Compute the dominance frontiers for a given graph.

The information is freed automatically when dominance info is freed.

ir_node* ir_deepest_common_dominator ( ir_node block0,
ir_node block1 
)

Returns the deepest common dominator of two blocks.

Parameters
block0A block.
block1Another block.
Returns
The deepest block dominating block0 and block1.
ir_node** ir_get_dominance_frontier ( const ir_node block)

Get the dominance frontier of a block.

Parameters
blockThe block whose dominance frontier you want.
Returns
A list containing all blocks in the dominance frontier of block (as array, use ARR_LEN() to determine the size)
void postdom_tree_walk ( ir_node n,
irg_walk_func pre,
irg_walk_func post,
void *  env 
)

Visit all nodes in the post dominator subtree of a given node.

Call a pre-visitor before descending to the children and call a post-visitor after returning from them.

Parameters
nThe node to start walking from.
preThe pre-visitor callback.
postThe post-visitor callback.
envSome custom data passed to the visitors.
void postdom_tree_walk_irg ( ir_graph irg,
irg_walk_func pre,
irg_walk_func post,
void *  env 
)

Walk over the post dominator tree of an irg starting at the root.

Parameters
irgThe graph.
preA pre-visitor to call.
postA post-visitor to call.
envSome private data to give to the visitors.