Node Heights

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

Typedefs
typedef struct ir_heights_t	ir_heights_t
	Computed graph Heights. More...

Functions
unsigned	get_irn_height (const ir_heights_t *h, const ir_node *irn)
	Returns the height of a node inside a basic block. More...
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. More...
unsigned	heights_recompute_block (ir_heights_t *h, ir_node *block)
	Recomputes the height information for a certain block. More...
ir_heights_t *	heights_new (ir_graph *irg)
	Creates a new heights object. More...
void	heights_free (ir_heights_t *h)
	Frees a heights object. More...

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

typedef struct ir_heights_t ir_heights_t

Computed graph Heights.

Definition at line 65 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 *	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.

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.