callgraph.h 7 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
2
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
19
20
 */

/**
Matthias Braun's avatar
Matthias Braun committed
21
22
23
24
25
26
27
28
29
30
 * @file
 * @brief       Representation and computation of the callgraph.
 * @author      Goetz Lindenmaier
 * @date        21.7.2004
 * @version     $Id$
 * @summary
 *  This file contains the representation of the callgraph.
 *  The nodes of the call graph are ir_graphs.  The edges between
 *  the nodes are calling relations.  I.e., if method a calls method
 *  b at some point, there is an edge between a and b.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
31
 *
Matthias Braun's avatar
Matthias Braun committed
32
33
34
 *  Further this file contains an algorithm to construct the call
 *  graph.  The construction of the callgraph uses the callee
 *  information in Call nodes to determine which methods are called.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
 *
Matthias Braun's avatar
Matthias Braun committed
36
37
38
 *  Finally this file contains an algorithm that computes backedges
 *  in the callgraph, i.e., the algorithm finds possibly recursive calls.
 *  The algorithm computes an upper bound of all recursive calls.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
39
 */
Matthias Braun's avatar
Matthias Braun committed
40
41
42
#ifndef FIRM_ANA_CALLGRAPH_H
#define FIRM_ANA_CALLGRAPH_H

Michael Beck's avatar
Michael Beck committed
43
#include "firm_types.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
44

Götz Lindenmaier's avatar
Götz Lindenmaier committed
45
46
/** Flag to indicate state of callgraph. */
typedef enum {
Michael Beck's avatar
Michael Beck committed
47
48
49
50
	irp_callgraph_none,                   /**< No callgraph allocated. */
	irp_callgraph_consistent,             /**< Callgraph constistent but calltree is inconsistent */
	irp_callgraph_inconsistent,           /**< Callgraph is allocated but inconsistent. */
	irp_callgraph_and_calltree_consistent /**< Both callgraph and calltree are consistent. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
51
} irp_callgraph_state;
Michael Beck's avatar
Michael Beck committed
52
53

/** Returns the callgraph state of the program representation. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
54
irp_callgraph_state get_irp_callgraph_state(void);
Michael Beck's avatar
Michael Beck committed
55
56

/** Sets the callgraph state of the program representation. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
57
58
void                set_irp_callgraph_state(irp_callgraph_state s);

Michael Beck's avatar
Michael Beck committed
59
/** Returns the number of procedures that call the given irg. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
60
int       get_irg_n_callers(ir_graph *irg);
Michael Beck's avatar
Michael Beck committed
61
62

/** Returns the caller at position pos. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
63
ir_graph *get_irg_caller(ir_graph *irg, int pos);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
64

Michael Beck's avatar
Michael Beck committed
65
/** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
66
int       is_irg_caller_backedge(ir_graph *irg, int pos);
Michael Beck's avatar
Michael Beck committed
67
68

/** Returns non-zero if the irg has a backedge caller. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
69
70
int       has_irg_caller_backedge(ir_graph *irg);

Michael Beck's avatar
Michael Beck committed
71
/** Returns the maximal loop depth of call nodes that call along this edge. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
72
int       get_irg_caller_loop_depth(ir_graph *irg, int pos);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
73

Michael Beck's avatar
Michael Beck committed
74
/** Returns the number of procedures that are called by the given irg. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
75
int       get_irg_n_callees(ir_graph *irg);
Michael Beck's avatar
Michael Beck committed
76
77

/** Returns the callee at position pos. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
78
ir_graph *get_irg_callee(ir_graph *irg, int pos);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
79

Michael Beck's avatar
Michael Beck committed
80
/** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
81
int       is_irg_callee_backedge(ir_graph *irg, int pos);
Michael Beck's avatar
Michael Beck committed
82
83

/** Returns non-zero if the irg has a backedge callee. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
84
85
int       has_irg_callee_backedge(ir_graph *irg);

Michael Beck's avatar
Michael Beck committed
86
/** Returns the maximal loop depth of call nodes that call along this edge. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
87
88
int       get_irg_callee_loop_depth(ir_graph *irg, int pos);

Michael Beck's avatar
Michael Beck committed
89
/** Returns the maximal loop depth of all paths from an external visible method to
Götz Lindenmaier's avatar
Götz Lindenmaier committed
90
91
    this irg. */
int       get_irg_loop_depth(ir_graph *irg);
92

Michael Beck's avatar
Michael Beck committed
93
/** Returns the maximal recursion depth of all paths from an external visible method to
Götz Lindenmaier's avatar
Götz Lindenmaier committed
94
95
    this irg. */
int       get_irg_recursion_depth(ir_graph *irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
96

Michael Beck's avatar
Michael Beck committed
97
98
/** Returns the method execution frequency of a graph. */
double get_irg_method_execution_frequency(ir_graph *irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
99

Michael Beck's avatar
Michael Beck committed
100
101
102
103
104
/**
 * Construct the callgraph. Expects callee information, i.e.,
 * irg_callee_info_consistent must be set.  This can be computed with
 * cgana().
 */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
105
void compute_callgraph(void);
Michael Beck's avatar
Michael Beck committed
106

Götz Lindenmaier's avatar
Götz Lindenmaier committed
107
/** Destruct the callgraph. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
108
109
void free_callgraph(void);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
110

Michael Beck's avatar
Michael Beck committed
111
/** A function type for functions passed to the callgraph walker. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
112
113
typedef void callgraph_walk_func(ir_graph *g, void *env);

Michael Beck's avatar
Michael Beck committed
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/**
 * Walks over the callgraph.
 *
 * Walks over the callgraph, starting at the irp main graph.
 * Visits ALL graphs in the irp, even if not reached by the main irg, but for
 * those the call order is not guaranteed.
 *
 * Executes pre before visiting the predecessor of a node, post after.
 * The void* env can be used to pass status information between the
 * pre and post functions.
 *
 * @param pre  - walker function, executed before the predecessor of a node are visited
 * @param post - walker function, executed after the predecessor of a node are visited
 * @param env  - environment, passed to pre and post
 */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
129
130
void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);

Michael Beck's avatar
Michael Beck committed
131
132
/**
 * Compute the backedges that represent recursions and a looptree.
133
 */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
134
135
void find_callgraph_recursions(void);

136
137
138
139
140
141
142
143
144
145
/** Compute interprocedural performance estimates.
 *
 *  Computes
 *   - the loop depth of the method.
 *     The loop depth of an edge between two methods is the
 *     maximal loop depth of the Call nodes that call along this edge.
 *     The loop depth of the method is the loop depth of the most expensive
 *     path from main().
 *   - The recursion depth.  The maximal number of recursions passed
 *     on all paths reaching this method.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
146
147
 *   - The execution frequency.  As loop depth, but the edge weight is the sum
 *     of the execution frequencies of all Calls along the edge.
Michael Beck's avatar
Michael Beck committed
148
149
 *
 * Expects the main irg is set, see set_irp_main_irg();
150
151
 **/
void compute_performance_estimates(void);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
152

Götz Lindenmaier's avatar
Götz Lindenmaier committed
153
154
155
156
/** Computes the interprocedural loop nesting information.
 *
 * Computes two numbers for each irg:  the depth it is called in 'normal'
 * loops and the depth of recursions it is in.
157
158
159
 *
 * Computes callee info and the callgraph if
 * this information is not available.
Michael Beck's avatar
Michael Beck committed
160
161
 *
 * Expects the main irg is set, see set_irp_main_irg();
162
163
 */
void analyse_loop_nesting_depth(void);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
164

Michael Beck's avatar
Michael Beck committed
165
/** The state of loop nesting depth. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
166
typedef enum {
Michael Beck's avatar
Michael Beck committed
167
168
169
170
171
	loop_nesting_depth_none,         /**< Loop nesting depths are not computed, no memory is
	                                      allocated, access fails. */
	loop_nesting_depth_consistent,   /**< Loop nesting depth information is computed and correct. */
	loop_nesting_depth_inconsistent  /**< Loop nesting depth is computed but the graphs have been
	                                      changed since. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
172
173
} loop_nesting_depth_state;

Michael Beck's avatar
Michael Beck committed
174
/** Returns the nesting depth state of the program representation. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
175
loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
Michael Beck's avatar
Michael Beck committed
176
177

/** Sets the nesting depth state of the program representation. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
178
void                     set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
Michael Beck's avatar
Michael Beck committed
179
180

/** Marks the nesting depth state of the program representation as inconsistent. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
181
182
void                     set_irp_loop_nesting_depth_state_inconsistent(void);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
183

Götz Lindenmaier's avatar
Götz Lindenmaier committed
184
#endif /* _CALLGRAPH_H_ */