Node Heights

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 *src, const ir_node *tgt)
	Checks if the node tgt is reachable according to data dependence edges from the node src.
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 data dependency path from a node to the end of a basic block. This is useful for scheduling heuristics and can also be used to speedup reachability queries.

Typedef Documentation

ir_heights_t

typedef struct ir_heights_t ir_heights_t

Computed graph Heights.

Definition at line 65 of file firm_types.h.

Function Documentation

get_irn_height()

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.

heights_free()

void heights_free

(

ir_heights_t *

h

)

Frees a heights object.

Parameters

h	The heights object.

heights_new()

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.

heights_reachable_in_block()

int heights_reachable_in_block	(	ir_heights_t *	h,
		const ir_node *	src,
		const ir_node *	tgt )

Checks if the node tgt is reachable according to data dependence edges from the node src.

Both nodes must be in the same block.

Parameters

h	The heights object.
src	The source node of a possible path.
tgt	The target node of a possible path.

Returns

1, if src is data dependent on tgt, 0 if not.

heights_recompute_block()

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.