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

Functions
ir_node *	get_Block_idom (const ir_node *block)
	return immediate dominator of block More...

ir_node *	get_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_node *	get_Block_dominated_first (const ir_node *block)
	Returns the first node in the list of nodes dominated by a given block. More...

ir_node *	get_Block_postdominated_first (const ir_node *bl)
	Returns the first node in the list of nodes postdominated by a given blcok. More...

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. More...

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. More...

ir_node *	ir_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:

idom: a reference to the block that is the immediate dominator of this block.
dom_depth: a number giving the depth of the block in the dominator tree.
pre_num: Number in preorder traversal.

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

a	The potential dominator block.
b	The 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

a	The potential post dominator block.
b	The 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

a	The potential post dominator block.
b	The 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

n	The node to start walking from.
pre	The pre-visitor callback.
post	The post-visitor callback.
env	Some 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

irg	The graph.
pre	A pre-visitor to call.
post	A post-visitor to call.
env	Some 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

block The 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

node	The 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

block0	A block.
block1	Another 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

block The 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

n	The node to start walking from.
pre	The pre-visitor callback.
post	The post-visitor callback.
env	Some 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

irg	The graph.
pre	A pre-visitor to call.
post	A post-visitor to call.
env	Some private data to give to the visitors.

Functions

Detailed Description

Function Documentation