3 * File name: ir/ana/callgraph.h
4 * Purpose: Representation and computation of the callgraph.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 * This file contains the representation of the callgraph.
20 * The nodes of the call graph are ir_graphs. The edges between
21 * the nodes are calling relations. I.e., if method a calls method
22 * b at some point, there is an edge between a and b.
24 * Further this file contains an algorithm to construct the call
25 * graph. The construction of the callgraph uses the callee
26 * information in Call nodes to determine which methods are called.
28 * Finally this file contains an algorithm that computes backedges
29 * in the callgraph, i.e., the algorithm finds possibly recursive calls.
30 * The algorithm computes an upper bound of all recursive calls.
36 /** Flag to indicate state of callgraph. */
39 irp_callgraph_consistent, /* calltree is inconsistent */
40 irp_callgraph_inconsistent,
41 irp_callgraph_and_calltree_consistent
42 } irp_callgraph_state;
43 irp_callgraph_state get_irp_callgraph_state(void);
44 void set_irp_callgraph_state(irp_callgraph_state s);
46 /** The functions that call irg. */
47 int get_irg_n_callers(ir_graph *irg);
48 ir_graph *get_irg_caller(ir_graph *irg, int pos);
50 int is_irg_caller_backedge(ir_graph *irg, int pos);
51 int has_irg_caller_backedge(ir_graph *irg);
53 /** maximal loop depth of call nodes that call along this edge. */
54 int get_irg_caller_loop_depth(ir_graph *irg, int pos);
56 /** The functions called by irg. */
57 int get_irg_n_callees(ir_graph *irg);
58 ir_graph *get_irg_callee(ir_graph *irg, int pos);
60 int is_irg_callee_backedge(ir_graph *irg, int pos);
61 int has_irg_callee_backedge(ir_graph *irg);
63 /** maximal loop depth of call nodes that call along this edge. */
64 int get_irg_callee_loop_depth(ir_graph *irg, int pos);
66 /** Maximal loop depth of all paths from an external visible method to
68 int get_irg_loop_depth(ir_graph *irg);
69 /** Maximal recursion depth of all paths from an external visible method to
71 int get_irg_recursion_depth(ir_graph *irg);
73 double get_irg_method_execution_frequency (ir_graph *irg);
75 /** Construct the callgraph. Expects callee information, i.e.,
76 irg_callee_info_consistent must be set. This can be computed with
78 void compute_callgraph(void);
79 /** Destruct the callgraph. */
80 void free_callgraph(void);
83 /** A function type for fuctions passed to the callgraph walker. */
84 typedef void callgraph_walk_func(ir_graph *g, void *env);
86 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);
88 /** Compute the backedges that represent recursions and a looptree.
90 void find_callgraph_recursions(void);
92 /** Compute interprocedural performance estimates.
95 * - the loop depth of the method.
96 * The loop depth of an edge between two methods is the
97 * maximal loop depth of the Call nodes that call along this edge.
98 * The loop depth of the method is the loop depth of the most expensive
100 * - The recursion depth. The maximal number of recursions passed
101 * on all paths reaching this method.
102 * - The execution freqency. As loop depth, but the edge weight is the sum
103 * of the execution freqencies of all Calls along the edge.
105 void compute_performance_estimates(void);
107 /** Computes the loop nesting information.
109 * Computes callee info and the callgraph if
110 * this information is not available.
112 void analyse_loop_nesting_depth(void);
115 #endif /* _CALLGRAPH_H_ */