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

Macros
#define	dominates_for_each(bl, curr)
	Iterate over all nodes which are immediately dominated by a given node.
#define	postdominates_for_each(bl, curr)
	Iterate over all nodes which are immediately post dominated by a given node.

Functions
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
int	block_dominates (const ir_node a, const ir_node b)
	Check, if a block dominates another block.
int	block_strictly_dominates (const ir_node a, const ir_node b)
	Check, if a block strictly dominates another block, i.e.
int	block_postdominates (const ir_node a, const ir_node b)
	Check, if a block post dominates another block.
int	block_strictly_postdominates (const ir_node a, const ir_node b)
	Check, if a block strictly post dominates another block, i.e.
ir_node *	get_Block_dominated_first (const ir_node *block)
	Returns the first node in the list of nodes dominated by a given 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_dominated_next (const ir_node *node)
	Returns the next node in a list of nodes which are dominated by some other node.
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.
ir_node *	node_smallest_common_dominator (ir_node a, ir_node b)
	Returns the smallest common dominator block of two nodes.
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.
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.
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.
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.
void	compute_doms (ir_graph *irg)
	Computes the dominance relation for all basic blocks of a given graph.
void	assure_doms (ir_graph *irg)
	Recomputes dominator relation of a graph if necessary.
void	compute_postdoms (ir_graph *irg)
	Computes the post dominance relation for all basic blocks of a given graph.
void	assure_postdoms (ir_graph *irg)
	Recompute postdominance relation if necessary.
void	free_dom (ir_graph *irg)
	Frees the dominance data structures.
void	free_postdom (ir_graph *irg)
	Frees the postdominance data structures.
void	ir_compute_dominance_frontiers (ir_graph *irg)
	Compute the dominance frontiers for a given graph.
ir_node **	ir_get_dominance_frontier (const ir_node *block)
	Get the dominance frontier of a block.

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.

Macro Definition Documentation

#define dominates_for_each	(	bl,
		curr
	)

Value:

for(curr = get_Block_dominated_first(bl); curr; \

curr = get_Block_dominated_next(curr))

Iterate over all nodes which are immediately dominated by a given node.

Parameters

bl	The block whose dominated blocks shall be iterated on.
curr	An iterator variable of type ir_node*

Definition at line 132 of file irdom.h.

#define postdominates_for_each	(	bl,
		curr
	)

Value:

for(curr = get_Block_postdominated_first(bl); curr; \

curr = get_Block_postdominated_next(curr))

Iterate over all nodes which are immediately post dominated by a given node.

Parameters

bl	The block whose post dominated blocks shall be iterated on.
curr	An iterator variable of type ir_node*

Definition at line 142 of file irdom.h.

Function Documentation

void assure_doms ( ir_graph * irg )

Recomputes dominator relation of a graph if necessary.

void assure_postdoms ( ir_graph * irg )

Recompute postdominance relation if necessary.

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_dominates	(	const ir_node *	a,
		const ir_node *	b
	)

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

a != b.

Parameters

a	The potential dominator block.
b	The potentially dominated block.

Returns: 1, if a strictly 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.

void free_dom ( ir_graph * irg )

Frees the dominance data structures.

Sets the flag in irg to "dom_none".

void free_postdom ( ir_graph * irg )

Frees the postdominance data structures.

Sets the flag in irg to "dom_none".

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_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)

ir_node* node_smallest_common_dominator	(	ir_node *	a,
		ir_node *	b
	)

Returns the smallest common dominator block of two nodes.

Parameters

a	A node.
b	Another node.

Returns: The first block dominating a and b

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.

Macros

Functions

Detailed Description

Macro Definition Documentation

Function Documentation