This file contains the representation of the callgraph. More...

Typedefs
typedef void	callgraph_walk_func (ir_graph g, void env)
	A function type for functions passed to the callgraph walker.
Enumerations
enum	irp_callgraph_state { irp_callgraph_none, irp_callgraph_consistent, irp_callgraph_inconsistent, irp_callgraph_and_calltree_consistent }
	Flag to indicate state of callgraph. More...
enum	loop_nesting_depth_state { loop_nesting_depth_none, loop_nesting_depth_consistent, loop_nesting_depth_inconsistent }
	The state of loop nesting depth. More...
Functions
irp_callgraph_state	get_irp_callgraph_state (void)
	Returns the callgraph state of the program representation.
void	set_irp_callgraph_state (irp_callgraph_state s)
	Sets the callgraph state of the program representation.
size_t	get_irg_n_callers (const ir_graph *irg)
	Returns the number of procedures that call the given irg.
ir_graph *	get_irg_caller (const ir_graph *irg, size_t pos)
	Returns the caller at position pos.
int	is_irg_caller_backedge (const ir_graph *irg, size_t pos)
	Returns non-zero if the caller at position pos is "a backedge", i.e.
int	has_irg_caller_backedge (const ir_graph *irg)
	Returns non-zero if the irg has a backedge caller.
size_t	get_irg_caller_loop_depth (const ir_graph *irg, size_t pos)
	Returns the maximal loop depth of call nodes that call along this edge.
size_t	get_irg_n_callees (const ir_graph *irg)
	Returns the number of procedures that are called by the given irg.
ir_graph *	get_irg_callee (const ir_graph *irg, size_t pos)
	Returns the callee at position pos.
int	is_irg_callee_backedge (const ir_graph *irg, size_t pos)
	Returns non-zero if the callee at position pos is "a backedge", i.e.
int	has_irg_callee_backedge (const ir_graph *irg)
	Returns non-zero if the irg has a backedge callee.
size_t	get_irg_callee_loop_depth (const ir_graph *irg, size_t pos)
	Returns the maximal loop depth of call nodes that call along this edge.
size_t	get_irg_loop_depth (const ir_graph *irg)
	Returns the maximal loop depth of all paths from an external visible method to this irg.
size_t	get_irg_recursion_depth (const ir_graph *irg)
	Returns the maximal recursion depth of all paths from an external visible method to this irg.
double	get_irg_method_execution_frequency (const ir_graph *irg)
	Returns the method execution frequency of a graph.
void	compute_callgraph (void)
	Construct the callgraph.
void	free_callgraph (void)
	Destruct the callgraph.
void	callgraph_walk (callgraph_walk_func pre, callgraph_walk_func post, void *env)
	Walks over the callgraph.
void	find_callgraph_recursions (void)
	Compute the backedges that represent recursions and a looptree.
void	analyse_loop_nesting_depth (void)
	Computes the interprocedural loop nesting information.
loop_nesting_depth_state	get_irp_loop_nesting_depth_state (void)
	Returns the nesting depth state of the program representation.
void	set_irp_loop_nesting_depth_state (loop_nesting_depth_state s)
	Sets the nesting depth state of the program representation.
void	set_irp_loop_nesting_depth_state_inconsistent (void)
	Marks the nesting depth state of the program representation as inconsistent.
size_t	cgana (ir_entity ***free_methods)
	Analyses a rough estimation of the possible call graph.
void	free_callee_info (ir_graph *irg)
	Frees callee information.
void	free_irp_callee_info (void)
	Frees callee information for all graphs in the current program.
void	opt_call_addrs (void)
	Optimizes the address expressions passed to call nodes.

Detailed Description

This file contains the representation of the callgraph.

The nodes of the call graph are ir_graphs. The edges between the nodes are calling relations. I.e., if method a calls method b at some point, there is an edge between a and b.

Further this file contains an algorithm to construct the call graph. The construction of the callgraph uses the callee information in Call nodes to determine which methods are called.

Finally this file contains an algorithm that computes backedges in the callgraph, i.e., the algorithm finds possibly recursive calls. The algorithm computes an upper bound of all recursive calls.

Typedef Documentation

typedef void callgraph_walk_func(ir_graph *g, void *env)

A function type for functions passed to the callgraph walker.

Definition at line 119 of file callgraph.h.

Enumeration Type Documentation

enum irp_callgraph_state

Flag to indicate state of callgraph.

Enumerator:

irp_callgraph_none	No callgraph allocated.
irp_callgraph_consistent	Callgraph constistent but calltree is inconsistent.
irp_callgraph_inconsistent	Callgraph is allocated but inconsistent.
irp_callgraph_and_calltree_consistent	Both callgraph and calltree are consistent.

Definition at line 53 of file callgraph.h.

enum loop_nesting_depth_state

The state of loop nesting depth.

Enumerator:

loop_nesting_depth_none	Loop nesting depths are not computed, no memory is allocated, access fails.
loop_nesting_depth_consistent	Loop nesting depth information is computed and correct.
loop_nesting_depth_inconsistent	Loop nesting depth is computed but the graphs have been changed since.

Definition at line 157 of file callgraph.h.

Function Documentation

void analyse_loop_nesting_depth ( void )

Computes the interprocedural loop nesting information.

Computes two numbers for each irg: the depth it is called in 'normal' loops and the depth of recursions it is in.

Computes callee info and the callgraph if this information is not available.

Expects the main irg is set, see set_irp_main_irg();

void callgraph_walk	(	callgraph_walk_func *	pre,
		callgraph_walk_func *	post,
		void *	env
	)

Walks over the callgraph.

Walks over the callgraph, starting at the irp main graph. Visits ALL graphs in the irp, even if not reached by the main irg, but for those the call order is not guaranteed.

Executes pre before visiting the predecessor of a node, post after. The void* env can be used to pass status information between the pre and post functions.

Parameters:

pre	- walker function, executed before the predecessor of a node are visited
post	- walker function, executed after the predecessor of a node are visited
env	- environment, passed to pre and post

size_t cgana ( ir_entity *** free_methods )

Analyses a rough estimation of the possible call graph.

Determines for each Call node the set of possibly called methods. Stores the result in the field 'callees' of the Call node. If the address can not be analysed, e.g. because it is loaded from a variable, the array contains the unknown_entity. (See set_Call_callee()). cgana() returns the set of 'free' methods, i.e., the methods that can be called from external or via function pointers. This datastructure must be freed with 'xfree()' by the caller of cgana().

cgana() sets the callee_info_state of each graph and the program to consistent.

The algorithm implements roughly Static Class Hierarchy Analysis as described in "Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis" by Jeffrey Dean and David Grove and Craig Chambers.

Performs some optimizations possible by the analysed information:

Replace SymConst-name nodes by SymConst-entity nodes if possible.
Replace (Sel-method(Alloc)) by SymConst-entity.
Replaces Sel-method by SymConst-entity if the method is never overwritten.

void compute_callgraph ( void )

Construct the callgraph.

Expects callee information, i.e., irg_callee_info_consistent must be set. This can be computed with cgana().

void find_callgraph_recursions ( void )

Compute the backedges that represent recursions and a looptree.

void free_callee_info ( ir_graph * irg )

Frees callee information.

Sets callee_info_state of the graph passed to none. Sets callee field in all call nodes to NULL. Else it happens that the field contains pointers to other than firm arrays.

void free_callgraph ( void )

Destruct the callgraph.

void free_irp_callee_info ( void )

Frees callee information for all graphs in the current program.

ir_graph* get_irg_callee	(	const ir_graph *	irg,
		size_t	pos
	)

Returns the callee at position pos.

size_t get_irg_callee_loop_depth	(	const ir_graph *	irg,
		size_t	pos
	)

Returns the maximal loop depth of call nodes that call along this edge.

ir_graph* get_irg_caller	(	const ir_graph *	irg,
		size_t	pos
	)

Returns the caller at position pos.

size_t get_irg_caller_loop_depth	(	const ir_graph *	irg,
		size_t	pos
	)

Returns the maximal loop depth of call nodes that call along this edge.

size_t get_irg_loop_depth ( const ir_graph * irg )

Returns the maximal loop depth of all paths from an external visible method to this irg.

double get_irg_method_execution_frequency ( const ir_graph * irg )

Returns the method execution frequency of a graph.

size_t get_irg_n_callees ( const ir_graph * irg )

Returns the number of procedures that are called by the given irg.

size_t get_irg_n_callers ( const ir_graph * irg )

Returns the number of procedures that call the given irg.

size_t get_irg_recursion_depth ( const ir_graph * irg )

Returns the maximal recursion depth of all paths from an external visible method to this irg.

irp_callgraph_state get_irp_callgraph_state ( void )

Returns the callgraph state of the program representation.

loop_nesting_depth_state get_irp_loop_nesting_depth_state ( void )

Returns the nesting depth state of the program representation.

int has_irg_callee_backedge ( const ir_graph * irg )

Returns non-zero if the irg has a backedge callee.

int has_irg_caller_backedge ( const ir_graph * irg )

Returns non-zero if the irg has a backedge caller.

int is_irg_callee_backedge	(	const ir_graph *	irg,
		size_t	pos
	)

Returns non-zero if the callee at position pos is "a backedge", i.e.

a recursion.

int is_irg_caller_backedge	(	const ir_graph *	irg,
		size_t	pos
	)

Returns non-zero if the caller at position pos is "a backedge", i.e.

a recursion.

void opt_call_addrs ( void )

Optimizes the address expressions passed to call nodes.

Performs only the optimizations done by cgana.

void set_irp_callgraph_state ( irp_callgraph_state s )

Sets the callgraph state of the program representation.

void set_irp_loop_nesting_depth_state ( loop_nesting_depth_state s )

Sets the nesting depth state of the program representation.

void set_irp_loop_nesting_depth_state_inconsistent ( void )

Marks the nesting depth state of the program representation as inconsistent.

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

Enumeration Type Documentation

Function Documentation