2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Representation and computation of the callgraph.
23 * @author Goetz Lindenmaier
27 * This file contains the representation of the callgraph.
28 * The nodes of the call graph are ir_graphs. The edges between
29 * the nodes are calling relations. I.e., if method a calls method
30 * b at some point, there is an edge between a and b.
32 * Further this file contains an algorithm to construct the call
33 * graph. The construction of the callgraph uses the callee
34 * information in Call nodes to determine which methods are called.
36 * Finally this file contains an algorithm that computes backedges
37 * in the callgraph, i.e., the algorithm finds possibly recursive calls.
38 * The algorithm computes an upper bound of all recursive calls.
40 #ifndef FIRM_ANA_CALLGRAPH_H
41 #define FIRM_ANA_CALLGRAPH_H
43 #include "firm_types.h"
46 /** Flag to indicate state of callgraph. */
48 irp_callgraph_none, /**< No callgraph allocated. */
49 irp_callgraph_consistent, /**< Callgraph constistent but calltree is inconsistent */
50 irp_callgraph_inconsistent, /**< Callgraph is allocated but inconsistent. */
51 irp_callgraph_and_calltree_consistent /**< Both callgraph and calltree are consistent. */
52 } irp_callgraph_state;
54 /** Returns the callgraph state of the program representation. */
55 FIRM_API irp_callgraph_state get_irp_callgraph_state(void);
57 /** Sets the callgraph state of the program representation. */
58 FIRM_API void set_irp_callgraph_state(irp_callgraph_state s);
60 /** Returns the number of procedures that call the given irg. */
61 FIRM_API int get_irg_n_callers(const ir_graph *irg);
63 /** Returns the caller at position pos. */
64 ir_graph *get_irg_caller(const ir_graph *irg, int pos);
66 /** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
67 FIRM_API int is_irg_caller_backedge(const ir_graph *irg, int pos);
69 /** Returns non-zero if the irg has a backedge caller. */
70 FIRM_API int has_irg_caller_backedge(const ir_graph *irg);
72 /** Returns the maximal loop depth of call nodes that call along this edge. */
73 FIRM_API int get_irg_caller_loop_depth(const ir_graph *irg, int pos);
75 /** Returns the number of procedures that are called by the given irg. */
76 FIRM_API int get_irg_n_callees(const ir_graph *irg);
78 /** Returns the callee at position pos. */
79 FIRM_API ir_graph *get_irg_callee(const ir_graph *irg, int pos);
81 /** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
82 FIRM_API int is_irg_callee_backedge(const ir_graph *irg, int pos);
84 /** Returns non-zero if the irg has a backedge callee. */
85 FIRM_API int has_irg_callee_backedge(const ir_graph *irg);
87 /** Returns the maximal loop depth of call nodes that call along this edge. */
88 FIRM_API int get_irg_callee_loop_depth(const ir_graph *irg, int pos);
90 /** Returns the maximal loop depth of all paths from an external visible method to
92 FIRM_API int get_irg_loop_depth(const ir_graph *irg);
94 /** Returns the maximal recursion depth of all paths from an external visible method to
96 FIRM_API int get_irg_recursion_depth(const ir_graph *irg);
98 /** Returns the method execution frequency of a graph. */
99 FIRM_API double get_irg_method_execution_frequency(const ir_graph *irg);
102 * Construct the callgraph. Expects callee information, i.e.,
103 * irg_callee_info_consistent must be set. This can be computed with
106 FIRM_API void compute_callgraph(void);
108 /** Destruct the callgraph. */
109 FIRM_API void free_callgraph(void);
112 /** A function type for functions passed to the callgraph walker. */
113 typedef void callgraph_walk_func(ir_graph *g, void *env);
116 * Walks over the callgraph.
118 * Walks over the callgraph, starting at the irp main graph.
119 * Visits ALL graphs in the irp, even if not reached by the main irg, but for
120 * those the call order is not guaranteed.
122 * Executes pre before visiting the predecessor of a node, post after.
123 * The void* env can be used to pass status information between the
124 * pre and post functions.
126 * @param pre - walker function, executed before the predecessor of a node are visited
127 * @param post - walker function, executed after the predecessor of a node are visited
128 * @param env - environment, passed to pre and post
130 FIRM_API void callgraph_walk(callgraph_walk_func *pre,
131 callgraph_walk_func *post, void *env);
134 * Compute the backedges that represent recursions and a looptree.
136 FIRM_API void find_callgraph_recursions(void);
138 /** Compute interprocedural performance estimates.
141 * - the loop depth of the method.
142 * The loop depth of an edge between two methods is the
143 * maximal loop depth of the Call nodes that call along this edge.
144 * The loop depth of the method is the loop depth of the most expensive
146 * - The recursion depth. The maximal number of recursions passed
147 * on all paths reaching this method.
148 * - The execution frequency. As loop depth, but the edge weight is the sum
149 * of the execution frequencies of all Calls along the edge.
151 * Expects the main irg is set, see set_irp_main_irg();
153 FIRM_API void compute_performance_estimates(void);
155 /** Computes the interprocedural loop nesting information.
157 * Computes two numbers for each irg: the depth it is called in 'normal'
158 * loops and the depth of recursions it is in.
160 * Computes callee info and the callgraph if
161 * this information is not available.
163 * Expects the main irg is set, see set_irp_main_irg();
165 FIRM_API void analyse_loop_nesting_depth(void);
167 /** The state of loop nesting depth. */
169 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is
170 allocated, access fails. */
171 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */
172 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been
174 } loop_nesting_depth_state;
176 /** Returns the nesting depth state of the program representation. */
177 FIRM_API loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
179 /** Sets the nesting depth state of the program representation. */
180 FIRM_API void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
182 /** Marks the nesting depth state of the program representation as inconsistent. */
183 FIRM_API void set_irp_loop_nesting_depth_state_inconsistent(void);