Node Heights

The height is a measure for the longest datadependencies path from a node to the end of a basic block. More...

Typedefs
typedef struct ir_heights_t	ir_heights_t
	Computed graph Heights.

Functions
unsigned	get_irn_height (const ir_heights_t *h, const ir_node *irn)
	Returns the height of a node inside a basic block.
int	heights_reachable_in_block (ir_heights_t *h, const ir_node *n, const ir_node *m)
	Checks if a certain node is reachable according to data dependence edges from another node.
unsigned	heights_recompute_block (ir_heights_t *h, ir_node *block)
	Recomputes the height information for a certain block.
ir_heights_t *	heights_new (ir_graph *irg)
	Creates a new heights object.
void	heights_free (ir_heights_t *h)
	Frees a heights object.

Detailed Description

The height is a measure for the longest datadependencies path from a node to the end of a basic block.

This is usefull for scheduling heuristics and can also be used to speedup reachability queries.

Typedef Documentation

typedef struct ir_heights_t ir_heights_t

Computed graph Heights.

Definition at line 75 of file firm_types.h.

Function Documentation

unsigned get_irn_height	(	const ir_heights_t *	h,
		const ir_node *	irn
	)

Returns the height of a node inside a basic block.

The height of the node is the maximal number of edges between a sink node in that block and the node itself (plus 1).

Parameters

h	The heights object.
irn	The node.

Returns

The height of the node.

void heights_free

(

ir_heights_t *

h

)

Frees a heights object.

Parameters

h	The heights object.

ir_heights_t* heights_new

(

ir_graph *

irg

)

Creates a new heights object.

This also computes the heights for each block in the graph.

Parameters

irg	The graph.

int heights_reachable_in_block	(	ir_heights_t *	h,
		const ir_node *	n,
		const ir_node *	m
	)

Checks if a certain node is reachable according to data dependence edges from another node.

Both nodes must be in the same block.

Parameters

h	The heights object.
n	The first node.
m	The other node.

Returns

1, if n is data dependent on m, 0 if not.

unsigned heights_recompute_block	(	ir_heights_t *	h,
		ir_node *	block
	)

Recomputes the height information for a certain block.

This can be used to recompute the height information of a block.

Parameters

h	The heights object.
block	The block

Returns

The maximum over all heights in the block.