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
  26  *  This file contains the representation of the callgraph.
  27  *  The nodes of the call graph are ir_graphs.  The edges between
  28  *  the nodes are calling relations.  I.e., if method a calls method
  29  *  b at some point, there is an edge between a and b.
  30  *
  31  *  Further this file contains an algorithm to construct the call
  32  *  graph.  The construction of the callgraph uses the callee
  33  *  information in Call nodes to determine which methods are called.
  34  *
  35  *  Finally this file contains an algorithm that computes backedges
  36  *  in the callgraph, i.e., the algorithm finds possibly recursive calls.
  37  *  The algorithm computes an upper bound of all recursive calls.
  38  */
  39 #ifndef FIRM_ANA_CALLGRAPH_H
  40 #define FIRM_ANA_CALLGRAPH_H
  41
  42 #include "firm_types.h"
  43 #include "begin.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 FIRM_API irp_callgraph_state get_irp_callgraph_state(void);
  55
  56 /** Sets the callgraph state of the program representation. */
  57 FIRM_API void set_irp_callgraph_state(irp_callgraph_state s);
  58
  59 /** Returns the number of procedures that call the given irg. */
  60 FIRM_API size_t 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, size_t pos);
  64
  65 /** Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
  66 FIRM_API int is_irg_caller_backedge(const ir_graph *irg, size_t pos);
  67
  68 /** Returns non-zero if the irg has a backedge caller. */
  69 FIRM_API 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 FIRM_API size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos);
  73
  74 /** Returns the number of procedures that are called by the given irg. */
  75 FIRM_API size_t get_irg_n_callees(const ir_graph *irg);
  76
  77 /** Returns the callee at position pos. */
  78 FIRM_API ir_graph *get_irg_callee(const ir_graph *irg, size_t pos);
  79
  80 /** Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
  81 FIRM_API int is_irg_callee_backedge(const ir_graph *irg, size_t pos);
  82
  83 /** Returns non-zero if the irg has a backedge callee. */
  84 FIRM_API 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 FIRM_API size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos);
  88
  89 /** Returns the maximal loop depth of all paths from an external visible method to
  90     this irg. */
  91 FIRM_API size_t 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 FIRM_API size_t get_irg_recursion_depth(const ir_graph *irg);
  96
  97 /** Returns the method execution frequency of a graph. */
  98 FIRM_API 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 FIRM_API void compute_callgraph(void);
 106
 107 /** Destruct the callgraph. */
 108 FIRM_API 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 FIRM_API void callgraph_walk(callgraph_walk_func *pre,
 130                              callgraph_walk_func *post, void *env);
 131
 132 /**
 133  * Compute the backedges that represent recursions and a looptree.
 134  */
 135 FIRM_API void find_callgraph_recursions(void);
 136
 137 /** Computes the interprocedural loop nesting information.
 138  *
 139  * Computes two numbers for each irg:  the depth it is called in 'normal'
 140  * loops and the depth of recursions it is in.
 141  *
 142  * Computes callee info and the callgraph if
 143  * this information is not available.
 144  *
 145  * Expects the main irg is set, see set_irp_main_irg();
 146  */
 147 FIRM_API void analyse_loop_nesting_depth(void);
 148
 149 /** The state of loop nesting depth. */
 150 typedef enum {
 151         loop_nesting_depth_none,         /**< Loop nesting depths are not computed, no memory is
 152                                               allocated, access fails. */
 153         loop_nesting_depth_consistent,   /**< Loop nesting depth information is computed and correct. */
 154         loop_nesting_depth_inconsistent  /**< Loop nesting depth is computed but the graphs have been
 155                                               changed since. */
 156 } loop_nesting_depth_state;
 157
 158 /** Returns the nesting depth state of the program representation. */
 159 FIRM_API loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
 160
 161 /** Sets the nesting depth state of the program representation. */
 162 FIRM_API void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
 163
 164 /** Marks the nesting depth state of the program representation as inconsistent. */
 165 FIRM_API void set_irp_loop_nesting_depth_state_inconsistent(void);
 166
 167 #include "end.h"
 168
 169 #endif