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);
70 /** Maximal recursion depth of all paths from an external visible method to
72 int get_irg_recursion_depth(ir_graph *irg);
74 double get_irg_method_execution_frequency (ir_graph *irg);
76 /** Construct the callgraph. Expects callee information, i.e.,
77 irg_callee_info_consistent must be set. This can be computed with
79 void compute_callgraph(void);
80 /** Destruct the callgraph. */
81 void free_callgraph(void);
84 /** A function type for fuctions passed to the callgraph walker. */
85 typedef void callgraph_walk_func(ir_graph *g, void *env);
87 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);
89 /** Compute the backedges that represent recursions and a looptree.
91 void find_callgraph_recursions(void);
93 /** Compute interprocedural performance estimates.
96 * - the loop depth of the method.
97 * The loop depth of an edge between two methods is the
98 * maximal loop depth of the Call nodes that call along this edge.
99 * The loop depth of the method is the loop depth of the most expensive
101 * - The recursion depth. The maximal number of recursions passed
102 * on all paths reaching this method.
103 * - The execution freqency. As loop depth, but the edge weight is the sum
104 * of the execution freqencies of all Calls along the edge.
106 void compute_performance_estimates(void);
108 /** Computes the interprocedural loop nesting information.
110 * Computes two numbers for each irg: the depth it is called in 'normal'
111 * loops and the depth of recursions it is in.
113 * Computes callee info and the callgraph if
114 * this information is not available.
116 void analyse_loop_nesting_depth(void);
118 /** State of loop nesting depth. */
120 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is
121 allocated, access fails. */
122 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */
123 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been
125 } loop_nesting_depth_state;
127 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
128 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
129 void set_irp_loop_nesting_depth_state_inconsistent(void);
132 #endif /* _CALLGRAPH_H_ */