1 /* 2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. 3 * 4 * This file is part of libFirm. 5 * 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. 10 * 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. 14 * 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 17 * PURPOSE. 18 */ 19 20 /** 21 * @file 22 * @brief Representation and computation of the callgraph. 23 * @author Goetz Lindenmaier 24 * @date 21.7.2004 25 * @brief callgraph analysis 26 */ 27 #ifndef FIRM_ANA_CALLGRAPH_H 28 #define FIRM_ANA_CALLGRAPH_H 29 30 #include "firm_types.h" 31 #include "begin.h" 32 33 /** 34 * @ingroup irana 35 * @defgroup callgraph Callgraph 36 * 37 * This file contains the representation of the callgraph. 38 * The nodes of the call graph are ir_graphs. The edges between 39 * the nodes are calling relations. I.e., if method a calls method 40 * b at some point, there is an edge between a and b. 41 * 42 * Further this file contains an algorithm to construct the call 43 * graph. The construction of the callgraph uses the callee 44 * information in Call nodes to determine which methods are called. 45 * 46 * Finally this file contains an algorithm that computes backedges 47 * in the callgraph, i.e., the algorithm finds possibly recursive calls. 48 * The algorithm computes an upper bound of all recursive calls. 49 * @{ 50 */ 51 52 /** Flag to indicate state of callgraph. */ 53 typedef enum { 54 irp_callgraph_none, /**< No callgraph allocated. */ 55 irp_callgraph_consistent, /**< Callgraph constistent but calltree is inconsistent */ 56 irp_callgraph_inconsistent, /**< Callgraph is allocated but inconsistent. */ 57 irp_callgraph_and_calltree_consistent /**< Both callgraph and calltree are consistent. */ 58 } irp_callgraph_state; 59 60 /** Returns the callgraph state of the program representation. */ 61 FIRM_API irp_callgraph_state get_irp_callgraph_state(void); 62 63 /** Sets the callgraph state of the program representation. */ 64 FIRM_API void set_irp_callgraph_state(irp_callgraph_state s); 65 66 /** Returns the number of procedures that call the given irg. */ 67 FIRM_API size_t get_irg_n_callers(const ir_graph *irg); 68 69 /** Returns the caller at position pos. */ 70 FIRM_API ir_graph *get_irg_caller(const ir_graph *irg, size_t pos); 71 72 /** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */ 73 FIRM_API int is_irg_caller_backedge(const ir_graph *irg, size_t pos); 74 75 /** Returns non-zero if the irg has a backedge caller. */ 76 FIRM_API int has_irg_caller_backedge(const ir_graph *irg); 77 78 /** Returns the maximal loop depth of call nodes that call along this edge. */ 79 FIRM_API size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos); 80 81 /** Returns the number of procedures that are called by the given irg. */ 82 FIRM_API size_t get_irg_n_callees(const ir_graph *irg); 83 84 /** Returns the callee at position pos. */ 85 FIRM_API ir_graph *get_irg_callee(const ir_graph *irg, size_t pos); 86 87 /** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */ 88 FIRM_API int is_irg_callee_backedge(const ir_graph *irg, size_t pos); 89 90 /** Returns non-zero if the irg has a backedge callee. */ 91 FIRM_API int has_irg_callee_backedge(const ir_graph *irg); 92 93 /** Returns the maximal loop depth of call nodes that call along this edge. */ 94 FIRM_API size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos); 95 96 /** Returns the maximal loop depth of all paths from an external visible method to 97 this irg. */ 98 FIRM_API size_t get_irg_loop_depth(const ir_graph *irg); 99 100 /** Returns the maximal recursion depth of all paths from an external visible method to 101 this irg. */ 102 FIRM_API size_t get_irg_recursion_depth(const ir_graph *irg); 103 104 /** Returns the method execution frequency of a graph. */ 105 FIRM_API double get_irg_method_execution_frequency(const ir_graph *irg); 106 107 /** 108 * Construct the callgraph. Expects callee information, i.e., 109 * irg_callee_info_consistent must be set. This can be computed with 110 * cgana(). 111 */ 112 FIRM_API void compute_callgraph(void); 113 114 /** Destruct the callgraph. */ 115 FIRM_API void free_callgraph(void); 116 117 118 /** A function type for functions passed to the callgraph walker. */ 119 typedef void callgraph_walk_func(ir_graph *g, void *env); 120 121 /** 122 * Walks over the callgraph. 123 * 124 * Walks over the callgraph, starting at the irp main graph. 125 * Visits ALL graphs in the irp, even if not reached by the main irg, but for 126 * those the call order is not guaranteed. 127 * 128 * Executes pre before visiting the predecessor of a node, post after. 129 * The void* env can be used to pass status information between the 130 * pre and post functions. 131 * 132 * @param pre - walker function, executed before the predecessor of a node are visited 133 * @param post - walker function, executed after the predecessor of a node are visited 134 * @param env - environment, passed to pre and post 135 */ 136 FIRM_API void callgraph_walk(callgraph_walk_func *pre, 137 callgraph_walk_func *post, void *env); 138 139 /** 140 * Compute the backedges that represent recursions and a looptree. 141 */ 142 FIRM_API void find_callgraph_recursions(void); 143 144 /** Computes the interprocedural loop nesting information. 145 * 146 * Computes two numbers for each irg: the depth it is called in 'normal' 147 * loops and the depth of recursions it is in. 148 * 149 * Computes callee info and the callgraph if 150 * this information is not available. 151 * 152 * Expects the main irg is set, see set_irp_main_irg(); 153 */ 154 FIRM_API void analyse_loop_nesting_depth(void); 155 156 /** The state of loop nesting depth. */ 157 typedef enum { 158 loop_nesting_depth_none, /**< Loop nesting depths are not computed, no memory is 159 allocated, access fails. */ 160 loop_nesting_depth_consistent, /**< Loop nesting depth information is computed and correct. */ 161 loop_nesting_depth_inconsistent /**< Loop nesting depth is computed but the graphs have been 162 changed since. */ 163 } loop_nesting_depth_state; 164 165 /** Returns the nesting depth state of the program representation. */ 166 FIRM_API loop_nesting_depth_state get_irp_loop_nesting_depth_state(void); 167 168 /** Sets the nesting depth state of the program representation. */ 169 FIRM_API void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s); 170 171 /** Marks the nesting depth state of the program representation as inconsistent. */ 172 FIRM_API void set_irp_loop_nesting_depth_state_inconsistent(void); 173 174 /** @} */ 175 176 #include "end.h" 177 178 #endif 179