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. More...

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. More...

void	set_irp_callgraph_state (irp_callgraph_state s)
	Sets the callgraph state of the program representation. More...

size_t	get_irg_n_callers (const ir_graph *irg)
	Returns the number of procedures that call the given irg. More...

ir_graph *	get_irg_caller (const ir_graph *irg, size_t pos)
	Returns the caller at position pos. More...

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. More...

int	has_irg_caller_backedge (const ir_graph *irg)
	Returns non-zero if the irg has a backedge caller. More...

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. More...

size_t	get_irg_n_callees (const ir_graph *irg)
	Returns the number of procedures that are called by the given irg. More...

ir_graph *	get_irg_callee (const ir_graph *irg, size_t pos)
	Returns the callee at position pos. More...

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. More...

int	has_irg_callee_backedge (const ir_graph *irg)
	Returns non-zero if the irg has a backedge callee. More...

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. More...

double	get_irg_method_execution_frequency (const ir_graph *irg)
	Returns the method execution frequency of a graph. More...

void	compute_callgraph (void)
	Construct the callgraph. More...

void	free_callgraph (void)
	Destruct the callgraph. More...

void	callgraph_walk (callgraph_walk_func pre, callgraph_walk_func post, void *env)
	Walks over the callgraph. More...

void	find_callgraph_recursions (void)
	Compute the backedges that represent recursions and a looptree. More...

void	analyse_loop_nesting_depth (void)
	Computes the interprocedural loop nesting information. More...

loop_nesting_depth_state	get_irp_loop_nesting_depth_state (void)
	Returns the nesting depth state of the program representation. More...

void	set_irp_loop_nesting_depth_state (loop_nesting_depth_state s)
	Sets the nesting depth state of the program representation. More...

void	set_irp_loop_nesting_depth_state_inconsistent (void)
	Marks the nesting depth state of the program representation as inconsistent. More...

size_t	cgana (ir_entity ***free_methods)
	Analyses a rough estimation of the possible call graph. More...

void	free_callee_info (ir_graph *irg)
	Frees callee information. More...

void	free_irp_callee_info (void)
	Frees callee information for all graphs in the current program. More...

void	opt_call_addrs (void)
	Optimizes the address expressions passed to call nodes. More...

int	cg_call_has_callees (const ir_node *node)
	Sets, get and remove the callee information for a Call node. More...

size_t	cg_get_call_n_callees (const ir_node *node)
	Returns the number of callees of Call node `node`. More...

ir_entity *	cg_get_call_callee (const ir_node *node, size_t pos)
	Returns callee number `pos` of Call node `node`. More...

void	cg_set_call_callee_arr (ir_node node, size_t n, ir_entity *arr)
	Sets the full callee array. More...

void	cg_remove_call_callee_arr (ir_node *node)
	Frees callee array of call node `node`. More...

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

◆ callgraph_walk_func

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

A function type for functions passed to the callgraph walker.

Definition at line 99 of file callgraph.h.

Enumeration Type Documentation

◆ irp_callgraph_state

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 41 of file callgraph.h.

◆ loop_nesting_depth_state

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 137 of file callgraph.h.

Function Documentation

◆ analyse_loop_nesting_depth()

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();

◆ callgraph_walk()

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 callees 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

◆ cg_call_has_callees()

int cg_call_has_callees ( const ir_node * node )

Sets, get and remove the callee information for a Call node.

The callee information lists all method entities that can be called from this node. If the address expression can not be analyzed fully, e.g., as entities can be called that are not in the compilation unit, the array contains the unknown_entity. The array contains only entities with peculiarity_existent, but with all kinds of visibility. The entities not necessarily contain an irg.

The array is only accessible if callee information is valid. See flag in graph.

The memory allocated for the array is managed automatically, i.e., it must not be freed if the Call node is removed from the graph.

Parameters

node	A Call node.

◆ cg_get_call_callee()

ir_entity* cg_get_call_callee	(	const ir_node *	node,
		size_t	pos
	)

Returns callee number pos of Call node node.

◆ cg_get_call_n_callees()

size_t cg_get_call_n_callees ( const ir_node * node )

Returns the number of callees of Call node node.

◆ cg_remove_call_callee_arr()

void cg_remove_call_callee_arr ( ir_node * node )

Frees callee array of call node node.

◆ cg_set_call_callee_arr()

void cg_set_call_callee_arr	(	ir_node *	node,
		size_t	n,
		ir_entity **	arr
	)

Sets the full callee array.

The passed array is copied.

◆ cgana()

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 data structure 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 (Sel-method(Alloc)) by Address.
Replaces Sel-method by Address if the method is never overwritten.

◆ compute_callgraph()

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().

◆ find_callgraph_recursions()

void find_callgraph_recursions ( void )

Compute the backedges that represent recursions and a looptree.

◆ free_callee_info()

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.

◆ free_callgraph()

void free_callgraph ( void )

Destruct the callgraph.

◆ free_irp_callee_info()

void free_irp_callee_info ( void )

Frees callee information for all graphs in the current program.

◆ get_irg_callee()

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

Returns the callee at position pos.

◆ get_irg_callee_loop_depth()

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.

◆ get_irg_caller()

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

Returns the caller at position pos.

◆ get_irg_caller_loop_depth()

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.

◆ get_irg_method_execution_frequency()

double get_irg_method_execution_frequency ( const ir_graph * irg )

Returns the method execution frequency of a graph.

◆ get_irg_n_callees()

size_t get_irg_n_callees ( const ir_graph * irg )

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

◆ get_irg_n_callers()

size_t get_irg_n_callers ( const ir_graph * irg )

Returns the number of procedures that call the given irg.

◆ get_irp_callgraph_state()

irp_callgraph_state get_irp_callgraph_state ( void )

Returns the callgraph state of the program representation.

◆ get_irp_loop_nesting_depth_state()

loop_nesting_depth_state get_irp_loop_nesting_depth_state ( void )

Returns the nesting depth state of the program representation.

◆ has_irg_callee_backedge()

int has_irg_callee_backedge ( const ir_graph * irg )

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

◆ has_irg_caller_backedge()

int has_irg_caller_backedge ( const ir_graph * irg )

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

◆ is_irg_callee_backedge()

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.

◆ is_irg_caller_backedge()

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.