libFirm
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_theights_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
hThe heights object.
irnThe node.
Returns
The height of the node.
void heights_free ( ir_heights_t h)

Frees a heights object.

Parameters
hThe 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
irgThe 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
hThe heights object.
srcThe source node of a possible path.
tgtThe 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
hThe heights object.
blockThe block
Returns
The maximum over all heights in the block.