2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Representation and computation of the callgraph.
9 * @author Goetz Lindenmaier
11 * @brief callgraph analysis
13 #ifndef FIRM_ANA_CALLGRAPH_H
14 #define FIRM_ANA_CALLGRAPH_H
16 #include "firm_types.h"
21 * @defgroup callgraph Callgraph
23 * This file contains the representation of the callgraph.
24 * The nodes of the call graph are ir_graphs. The edges between
25 * the nodes are calling relations. I.e., if method a calls method
26 * b at some point, there is an edge between a and b.
28 * Further this file contains an algorithm to construct the call
29 * graph. The construction of the callgraph uses the callee
30 * information in Call nodes to determine which methods are called.
32 * Finally this file contains an algorithm that computes backedges
33 * in the callgraph, i.e., the algorithm finds possibly recursive calls.
34 * The algorithm computes an upper bound of all recursive calls.
38 /** Flag to indicate state of callgraph. */
40 irp_callgraph_none, /**< No callgraph allocated. */
41 irp_callgraph_consistent, /**< Callgraph constistent but calltree is inconsistent */
42 irp_callgraph_inconsistent, /**< Callgraph is allocated but inconsistent. */
43 irp_callgraph_and_calltree_consistent /**< Both callgraph and calltree are consistent. */
44 } irp_callgraph_state;
46 /** Returns the callgraph state of the program representation. */
47 FIRM_API irp_callgraph_state get_irp_callgraph_state(void);
49 /** Sets the callgraph state of the program representation. */
50 FIRM_API void set_irp_callgraph_state(irp_callgraph_state s);
52 /** Returns the number of procedures that call the given irg. */
53 FIRM_API size_t get_irg_n_callers(const ir_graph *irg);
55 /** Returns the caller at position pos. */
56 FIRM_API ir_graph *get_irg_caller(const ir_graph *irg, size_t pos);
58 /** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
59 FIRM_API int is_irg_caller_backedge(const ir_graph *irg, size_t pos);
61 /** Returns non-zero if the irg has a backedge caller. */
62 FIRM_API int has_irg_caller_backedge(const ir_graph *irg);
64 /** Returns the maximal loop depth of call nodes that call along this edge. */
65 FIRM_API size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos);
67 /** Returns the number of procedures that are called by the given irg. */
68 FIRM_API size_t get_irg_n_callees(const ir_graph *irg);
70 /** Returns the callee at position pos. */
71 FIRM_API ir_graph *get_irg_callee(const ir_graph *irg, size_t pos);
73 /** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
74 FIRM_API int is_irg_callee_backedge(const ir_graph *irg, size_t pos);
76 /** Returns non-zero if the irg has a backedge callee. */
77 FIRM_API int has_irg_callee_backedge(const ir_graph *irg);
79 /** Returns the maximal loop depth of call nodes that call along this edge. */
80 FIRM_API size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos);
82 /** Returns the maximal loop depth of all paths from an external visible method to
84 FIRM_API size_t get_irg_loop_depth(const ir_graph *irg);
86 /** Returns the maximal recursion depth of all paths from an external visible method to
88 FIRM_API size_t get_irg_recursion_depth(const ir_graph *irg);
90 /** Returns the method execution frequency of a graph. */
91 FIRM_API double get_irg_method_execution_frequency(const ir_graph *irg);
94 * Construct the callgraph. Expects callee information, i.e.,
95 * irg_callee_info_consistent must be set. This can be computed with
98 FIRM_API void compute_callgraph(void);
100 /** Destruct the callgraph. */
101 FIRM_API void free_callgraph(void);
104 /** A function type for functions passed to the callgraph walker. */
105 typedef void callgraph_walk_func(ir_graph *g, void *env);
108 * Walks over the callgraph.
110 * Walks over the callgraph, starting at the irp main graph.
111 * Visits ALL graphs in the irp, even if not reached by the main irg, but for
112 * those the call order is not guaranteed.
114 * Executes pre before visiting the predecessor of a node, post after.
115 * The void* env can be used to pass status information between the
116 * pre and post functions.
118 * @param pre - walker function, executed before the predecessor of a node are visited
119 * @param post - walker function, executed after the predecessor of a node are visited
120 * @param env - environment, passed to pre and post
122 FIRM_API void callgraph_walk(callgraph_walk_func *pre,
123 callgraph_walk_func *post, void *env);
126 * Compute the backedges that represent recursions and a looptree.
128 FIRM_API void find_callgraph_recursions(void);
130 /** Computes the interprocedural loop nesting information.
132 * Computes two numbers for each irg: the depth it is called in 'normal'
133 * loops and the depth of recursions it is in.
135 * Computes callee info and the callgraph if
136 * this information is not available.
138 * Expects the main irg is set, see set_irp_main_irg();
140 FIRM_API void analyse_loop_nesting_depth(void);
142 /** The state of loop nesting depth. */
144 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is
145 allocated, access fails. */
146 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */
147 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been
149 } loop_nesting_depth_state;
151 /** Returns the nesting depth state of the program representation. */
152 FIRM_API loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
154 /** Sets the nesting depth state of the program representation. */
155 FIRM_API void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
157 /** Marks the nesting depth state of the program representation as inconsistent. */
158 FIRM_API void set_irp_loop_nesting_depth_state_inconsistent(void);