nsz Git - libfirm/blob - ir/ana/callgraph.h

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