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