3 * File name: ir/ana/callgraph.h
4 * Purpose: Representation and computation of the callgraph.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004-2007 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
18 * This file contains the representation of the callgraph.
19 * The nodes of the call graph are ir_graphs. The edges between
20 * the nodes are calling relations. I.e., if method a calls method
21 * b at some point, there is an edge between a and b.
23 * Further this file contains an algorithm to construct the call
24 * graph. The construction of the callgraph uses the callee
25 * information in Call nodes to determine which methods are called.
27 * Finally this file contains an algorithm that computes backedges
28 * in the callgraph, i.e., the algorithm finds possibly recursive calls.
29 * The algorithm computes an upper bound of all recursive calls.
31 #include "firm_types.h"
33 /** Flag to indicate state of callgraph. */
35 irp_callgraph_none, /**< No callgraph allocated. */
36 irp_callgraph_consistent, /**< Callgraph constistent but calltree is inconsistent */
37 irp_callgraph_inconsistent, /**< Callgraph is allocated but inconsistent. */
38 irp_callgraph_and_calltree_consistent /**< Both callgraph and calltree are consistent. */
39 } irp_callgraph_state;
41 /** Returns the callgraph state of the program representation. */
42 irp_callgraph_state get_irp_callgraph_state(void);
44 /** Sets the callgraph state of the program representation. */
45 void set_irp_callgraph_state(irp_callgraph_state s);
47 /** Returns the number of procedures that call the given irg. */
48 int get_irg_n_callers(ir_graph *irg);
50 /** Returns the caller at position pos. */
51 ir_graph *get_irg_caller(ir_graph *irg, int pos);
53 /** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
54 int is_irg_caller_backedge(ir_graph *irg, int pos);
56 /** Returns non-zero if the irg has a backedge caller. */
57 int has_irg_caller_backedge(ir_graph *irg);
59 /** Returns the maximal loop depth of call nodes that call along this edge. */
60 int get_irg_caller_loop_depth(ir_graph *irg, int pos);
62 /** Returns the number of procedures that are called by the given irg. */
63 int get_irg_n_callees(ir_graph *irg);
65 /** Returns the callee at position pos. */
66 ir_graph *get_irg_callee(ir_graph *irg, int pos);
68 /** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
69 int is_irg_callee_backedge(ir_graph *irg, int pos);
71 /** Returns non-zero if the irg has a backedge callee. */
72 int has_irg_callee_backedge(ir_graph *irg);
74 /** Returns the maximal loop depth of call nodes that call along this edge. */
75 int get_irg_callee_loop_depth(ir_graph *irg, int pos);
77 /** Returns the maximal loop depth of all paths from an external visible method to
79 int get_irg_loop_depth(ir_graph *irg);
81 /** Returns the maximal recursion depth of all paths from an external visible method to
83 int get_irg_recursion_depth(ir_graph *irg);
85 /** Returns the method execution frequency of a graph. */
86 double get_irg_method_execution_frequency(ir_graph *irg);
89 * Construct the callgraph. Expects callee information, i.e.,
90 * irg_callee_info_consistent must be set. This can be computed with
93 void compute_callgraph(void);
95 /** Destruct the callgraph. */
96 void free_callgraph(void);
99 /** A function type for functions passed to the callgraph walker. */
100 typedef void callgraph_walk_func(ir_graph *g, void *env);
103 * Walks over the callgraph.
105 * Walks over the callgraph, starting at the irp main graph.
106 * Visits ALL graphs in the irp, even if not reached by the main irg, but for
107 * those the call order is not guaranteed.
109 * Executes pre before visiting the predecessor of a node, post after.
110 * The void* env can be used to pass status information between the
111 * pre and post functions.
113 * @param pre - walker function, executed before the predecessor of a node are visited
114 * @param post - walker function, executed after the predecessor of a node are visited
115 * @param env - environment, passed to pre and post
117 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);
120 * Compute the backedges that represent recursions and a looptree.
122 void find_callgraph_recursions(void);
124 /** Compute interprocedural performance estimates.
127 * - the loop depth of the method.
128 * The loop depth of an edge between two methods is the
129 * maximal loop depth of the Call nodes that call along this edge.
130 * The loop depth of the method is the loop depth of the most expensive
132 * - The recursion depth. The maximal number of recursions passed
133 * on all paths reaching this method.
134 * - The execution frequency. As loop depth, but the edge weight is the sum
135 * of the execution frequencies of all Calls along the edge.
137 * Expects the main irg is set, see set_irp_main_irg();
139 void compute_performance_estimates(void);
141 /** Computes the interprocedural loop nesting information.
143 * Computes two numbers for each irg: the depth it is called in 'normal'
144 * loops and the depth of recursions it is in.
146 * Computes callee info and the callgraph if
147 * this information is not available.
149 * Expects the main irg is set, see set_irp_main_irg();
151 void analyse_loop_nesting_depth(void);
153 /** The state of loop nesting depth. */
155 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is
156 allocated, access fails. */
157 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */
158 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been
160 } loop_nesting_depth_state;
162 /** Returns the nesting depth state of the program representation. */
163 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
165 /** Sets the nesting depth state of the program representation. */
166 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
168 /** Marks the nesting depth state of the program representation as inconsistent. */
169 void set_irp_loop_nesting_depth_state_inconsistent(void);
172 #endif /* _CALLGRAPH_H_ */