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

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