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);
77 * Construct the callgraph. Expects callee information, i.e.,
78 * irg_callee_info_consistent must be set. This can be computed with
81 void compute_callgraph(void);
83 /** Destruct the callgraph. */
84 void free_callgraph(void);
87 /** A function type for functions passed to the callgraph walker. */
88 typedef void callgraph_walk_func(ir_graph *g, void *env);
90 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);
92 /** Compute the backedges that represent recursions and a looptree.
94 void find_callgraph_recursions(void);
96 /** Compute interprocedural performance estimates.
99 * - the loop depth of the method.
100 * The loop depth of an edge between two methods is the
101 * maximal loop depth of the Call nodes that call along this edge.
102 * The loop depth of the method is the loop depth of the most expensive
104 * - The recursion depth. The maximal number of recursions passed
105 * on all paths reaching this method.
106 * - The execution frequency. As loop depth, but the edge weight is the sum
107 * of the execution frequencies of all Calls along the edge.
109 void compute_performance_estimates(void);
111 /** Computes the interprocedural loop nesting information.
113 * Computes two numbers for each irg: the depth it is called in 'normal'
114 * loops and the depth of recursions it is in.
116 * Computes callee info and the callgraph if
117 * this information is not available.
119 void analyse_loop_nesting_depth(void);
121 /** State of loop nesting depth. */
123 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is
124 allocated, access fails. */
125 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */
126 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been
128 } loop_nesting_depth_state;
130 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
131 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
132 void set_irp_loop_nesting_depth_state_inconsistent(void);
135 #endif /* _CALLGRAPH_H_ */