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 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifndef _CALLGRAPH_H_
  14 #define _CALLGRAPH_H_
  15
  16 /**
  17  * @file callgraph.h
  18  *
  19  *  This file contains the representation of the callgraph.
  20  *  The nodes of the call graph are ir_graphs.  The edges between
  21  *  the nodes are calling relations.  I.e., if method a calls method
  22  *  b at some point, there is an edge between a and b.
  23  *
  24  *  Further this file contains an algorithm to construct the call
  25  *  graph.  The construction of the callgraph uses the callee
  26  *  information in Call nodes to determine which methods are called.
  27  *
  28  *  Finally this file contains an algorithm that computes backedges
  29  *  in the callgraph, i.e., the algorithm finds possibly recursive calls.
  30  *  The algorithm computes an upper bound of all recursive calls.
  31  *
  32  */
  33
  34 #include "irgraph.h"
  35
  36 /** Flag to indicate state of callgraph. */
  37 typedef enum {
  38   irp_callgraph_none,
  39   irp_callgraph_consistent,   /* calltree is inconsistent */
  40   irp_callgraph_inconsistent,
  41   irp_callgraph_and_calltree_consistent
  42 } irp_callgraph_state;
  43 irp_callgraph_state get_irp_callgraph_state(void);
  44 void                set_irp_callgraph_state(irp_callgraph_state s);
  45
  46 /** The functions that call irg. */
  47 int       get_irg_n_callers(ir_graph *irg);
  48 ir_graph *get_irg_caller(ir_graph *irg, int pos);
  49
  50 int       is_irg_caller_backedge(ir_graph *irg, int pos);
  51 int       has_irg_caller_backedge(ir_graph *irg);
  52
  53 /** maximal loop depth of call nodes that call along this edge. */
  54 int       get_irg_caller_loop_depth(ir_graph *irg, int pos);
  55
  56 /** The functions called by irg. */
  57 int       get_irg_n_callees(ir_graph *irg);
  58 ir_graph *get_irg_callee(ir_graph *irg, int pos);
  59
  60 int       is_irg_callee_backedge(ir_graph *irg, int pos);
  61 int       has_irg_callee_backedge(ir_graph *irg);
  62
  63 /** maximal loop depth of call nodes that call along this edge. */
  64 int       get_irg_callee_loop_depth(ir_graph *irg, int pos);
  65
  66 /** Maximal loop depth of all paths from an external visible method to
  67     this irg. */
  68 int       get_irg_loop_depth(ir_graph *irg);
  69
  70 /** Maximal recursion depth of all paths from an external visible method to
  71     this irg. */
  72 int       get_irg_recursion_depth(ir_graph *irg);
  73
  74 double get_irg_method_execution_frequency (ir_graph *irg);
  75
  76 /**
  77  * Construct the callgraph. Expects callee information, i.e.,
  78  * irg_callee_info_consistent must be set.  This can be computed with
  79  * cgana().
  80  */
  81 void compute_callgraph(void);
  82
  83 /** Destruct the callgraph. */
  84 void free_callgraph(void);
  85
  86
  87 /** A function type for functions passed to the callgraph walker. */
  88 typedef void callgraph_walk_func(ir_graph *g, void *env);
  89
  90 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env);
  91
  92 /** Compute the backedges that represent recursions and a looptree.
  93  */
  94 void find_callgraph_recursions(void);
  95
  96 /** Compute interprocedural performance estimates.
  97  *
  98  *  Computes
  99  *   - the loop depth of the method.
 100  *     The loop depth of an edge between two methods is the
 101  *     maximal loop depth of the Call nodes that call along this edge.
 102  *     The loop depth of the method is the loop depth of the most expensive
 103  *     path from main().
 104  *   - The recursion depth.  The maximal number of recursions passed
 105  *     on all paths reaching this method.
 106  *   - The execution frequency.  As loop depth, but the edge weight is the sum
 107  *     of the execution frequencies of all Calls along the edge.
 108  **/
 109 void compute_performance_estimates(void);
 110
 111 /** Computes the interprocedural loop nesting information.
 112  *
 113  * Computes two numbers for each irg:  the depth it is called in 'normal'
 114  * loops and the depth of recursions it is in.
 115  *
 116  * Computes callee info and the callgraph if
 117  * this information is not available.
 118  */
 119 void analyse_loop_nesting_depth(void);
 120
 121 /** State of loop nesting depth. */
 122 typedef enum {
 123   loop_nesting_depth_none,             /**< Loop nesting depths are not computed, no memory is
 124                                             allocated, access fails. */
 125   loop_nesting_depth_consistent,       /**< Loop nesting depth information is computed and correct. */
 126   loop_nesting_depth_inconsistent      /**< Loop nesting depth is computed but the graphs have been
 127                                             changed since. */
 128 } loop_nesting_depth_state;
 129
 130 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void);
 131 void                     set_irp_loop_nesting_depth_state(loop_nesting_depth_state s);
 132 void                     set_irp_loop_nesting_depth_state_inconsistent(void);
 133
 134
 135 #endif /* _CALLGRAPH_H_ */