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