nsz Git - libfirm/blob - include/libfirm/callgraph.h

   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 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