nsz Git - libfirm/blob - ir/stat/dags.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/dags.c
   4  * Purpose:     Statistics for Firm. DAG's in graphs.
   5  * Author:      Michael Beck
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 2004 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 #ifdef HAVE_CONFIG_H
  13 # include "config.h"
  14 #endif
  15
  16 #include <assert.h>
  17
  18 #include "irprintf.h"
  19 #include "irdump.h"
  20 #include "dags.h"
  21 #include "irtools.h"
  22
  23 enum dag_counting_options_t {
  24         FIRMSTAT_COPY_CONSTANTS = 0x00000001,  /**< if set, constants will be treated as they are in
  25                                                     the same block as its successors */
  26         FIRMSTAT_LOAD_IS_LEAVE  = 0x00000002,  /**< Load nodes are always leaves */
  27         FIRMSTAT_CALL_IS_LEAVE  = 0x00000004,  /**< Call nodes are always leaves */
  28         FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008,  /**< arguments (Proj(Proj(Start)) are roots */
  29 };
  30
  31 typedef struct _dag_entry_t dag_entry_t;
  32
  33 /**
  34  * Environment for connecting DAG's
  35  */
  36 typedef struct _dag_env_t {
  37         struct obstack obst;
  38         unsigned       num_of_dags;
  39         dag_entry_t    *list_of_dags;
  40         unsigned       options;       /**< DAG counting options */
  41 } dag_env_t;
  42
  43 /**
  44  * a DAG Entry
  45  */
  46 struct _dag_entry_t {
  47         unsigned    id;               /**< assigned ID for this DAG */
  48         ir_node     *root;            /**< one root of the DAG */
  49         unsigned    num_roots;        /**< number of root nodes in the DAG */
  50         unsigned    num_nodes;        /**< overall number of nodes in the DAG */
  51         unsigned    num_inner_nodes;  /**< number of inner nodes in the DAG */
  52         unsigned    is_dead;          /**< marks a dead entry */
  53         dag_entry_t *next;            /**< link all entries of a DAG */
  54         dag_entry_t *link;            /**< if set, this entry is an ID */
  55 };
  56
  57 /**
  58  * return an DAG entry for the node n
  59  */
  60 static dag_entry_t *get_irn_dag_entry(ir_node *n)
  61 {
  62         dag_entry_t *res = get_irn_link(n);
  63
  64         if (res) {
  65                 dag_entry_t *p;
  66
  67                 for (p = res; p->link; p = p->link);
  68
  69                 if (p != res)
  70                         set_irn_link(n, p);
  71
  72                 return p;
  73         }  /* if */
  74         return NULL;
  75 }  /* get_irn_dag_entry */
  76
  77 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
  78
  79 /**
  80  * checks whether a node is an arg
  81  */
  82 static int is_arg(ir_node *node)
  83 {
  84         if (! is_Proj(node))
  85                 return 0;
  86
  87         node = get_Proj_pred(node);
  88         if (! is_Proj(node))
  89                 return 0;
  90
  91         node = get_Proj_pred(node);
  92         return get_irn_op(node) == op_Start;
  93 }  /* is_arg */
  94
  95 /**
  96  * walker for connecting DAGs and counting.
  97  */
  98 static void connect_dags(ir_node *node, void *env)
  99 {
 100         dag_env_t   *dag_env = env;
 101         int         i, arity;
 102         ir_node     *block;
 103         dag_entry_t *entry;
 104         ir_mode     *mode;
 105
 106         if (is_Block(node))
 107                 return;
 108
 109         block = get_nodes_block(node);
 110
 111         /* ignore start end end blocks */
 112         if (block == get_irg_start_block(current_ir_graph) ||
 113                 block == get_irg_end_block(current_ir_graph)) {
 114                 return;
 115         }  /* if */
 116
 117         if (is_Phi(node))
 118                 return;
 119
 120         if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
 121                 return;
 122
 123         mode = get_irn_mode(node);
 124         if (mode == mode_X || mode == mode_M) {
 125                 /* do NOT count mode_X nodes */
 126                 return;
 127         }  /* if */
 128
 129         entry = get_irn_dag_entry(node);
 130
 131         if (! entry) {
 132                 /* found a not assigned node, maybe a new root */
 133                 entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
 134
 135                 entry->num_nodes       = 1;
 136                 entry->num_roots       = 1;
 137                 entry->num_inner_nodes = 0;
 138                 entry->root            = node;
 139                 entry->is_dead         = 0;
 140                 entry->next            = dag_env->list_of_dags;
 141                 entry->link            = NULL;
 142
 143                 ++dag_env->num_of_dags;
 144                 dag_env->list_of_dags = entry;
 145
 146                 set_irn_dag_entry(node, entry);
 147         }  /* if */
 148
 149         /* if this option is set, Loads are allways leaves */
 150         if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && get_irn_op(node) == op_Load)
 151                 return;
 152
 153         if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && get_irn_op(node) == op_Call)
 154                 return;
 155
 156         /* put the predecessors into the same DAG as the current */
 157         for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 158                 ir_node *prev = get_irn_n(node, i);
 159                 ir_mode *mode = get_irn_mode(prev);
 160
 161                 if (is_Phi(prev))
 162                         continue;
 163
 164                 if (mode == mode_X || mode == mode_M)
 165                         continue;
 166
 167                 /*
 168                  * copy constants if requested into the DAG's
 169                  * beware, do NOT add a link, as this will result in
 170                  * wrong intersections
 171                  */
 172                 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 173                         if (get_irn_op(prev) == op_Const || get_irn_op(prev) == op_SymConst) {
 174                                 ++entry->num_nodes;
 175                                 ++entry->num_inner_nodes;
 176                         }  /* if */
 177                 }  /* if */
 178
 179                 /* only nodes from the same block goes into the DAG */
 180                 if (get_nodes_block(prev) == block) {
 181                         dag_entry_t *prev_entry = get_irn_dag_entry(prev);
 182
 183                         if (! prev_entry) {
 184                                 /* not assigned node, put it into the same DAG */
 185                                 set_irn_dag_entry(prev, entry);
 186                                 ++entry->num_nodes;
 187                                 ++entry->num_inner_nodes;
 188                         } else {
 189                                 if (prev_entry != entry) {
 190
 191                                         /* two DAGs intersect */
 192                                         entry->num_roots       += prev_entry->num_roots;
 193                                         entry->num_nodes       += prev_entry->num_nodes;
 194                                         entry->num_inner_nodes += prev_entry->num_inner_nodes;
 195
 196                                         --dag_env->num_of_dags;
 197
 198                                         prev_entry->is_dead = 1;
 199                                         prev_entry->link    = entry;
 200                                 }  /* if */
 201                         }  /* if */
 202                 }  /* if */
 203         }  /* for */
 204 }  /* connect_dags */
 205
 206 #define DEFAULT_RET     1
 207 #define COLOR_RET       1
 208
 209 static unsigned mark_options;
 210
 211 /**
 212  * a vcg attribute hook
 213  */
 214 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
 215 {
 216         static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
 217         dag_entry_t *entry;
 218
 219         /* do not count Bad / NoMem */
 220         if (l) {
 221                 ir_op *op = get_irn_op(l);
 222
 223                 if (op == op_NoMem || op == op_Bad)
 224                         return DEFAULT_RET;
 225
 226                 /* check for additional options */
 227                 op = get_irn_op(n);
 228
 229                 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && op == op_Load)
 230                         return DEFAULT_RET;
 231
 232                 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && op == op_Call)
 233                         return DEFAULT_RET;
 234         }  /* if */
 235
 236         entry = get_irn_dag_entry(n);
 237         if (! entry)
 238                 return DEFAULT_RET;
 239
 240         fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
 241
 242         /* I know the color! */
 243         return COLOR_RET;
 244 }  /* stat_dag_mark_hook */
 245
 246 /**
 247  * count the DAG's size of a graph
 248  */
 249 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
 250 {
 251         dag_env_t   root_env;
 252         dag_entry_t *entry;
 253         unsigned id;
 254
 255         /* do NOT check the const code irg */
 256         if (graph->irg == get_const_code_irg())
 257                 return;
 258
 259         /* first step, clear the links */
 260         irg_walk_graph(graph->irg, firm_clear_link, NULL, NULL);
 261
 262         obstack_init(&root_env.obst);
 263         root_env.num_of_dags  = 0;
 264         root_env.list_of_dags = NULL;
 265         root_env.options      = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE;
 266
 267         /* count them */
 268         irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
 269
 270         printf("Graph %p %s --- %d\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)),
 271                 root_env.num_of_dags);
 272
 273         for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
 274                 if (entry->is_dead)
 275                         continue;
 276                 entry->id = id++;
 277
 278                 printf("number of roots %d number of nodes %d inner %d %ld\n",
 279                         entry->num_roots,
 280                         entry->num_nodes,
 281                         entry->num_inner_nodes,
 282                         get_irn_node_nr(entry->root));
 283         }  /* for */
 284
 285 #if 1
 286         /* dump for test */
 287         mark_options = root_env.options;
 288         set_dump_node_vcgattr_hook(stat_dag_mark_hook);
 289         dump_ir_block_graph(graph->irg, "-dag");
 290         set_dump_node_vcgattr_hook(NULL);
 291 #endif
 292
 293         assert(id == root_env.num_of_dags);
 294
 295         obstack_free(&root_env.obst, NULL);
 296 }  /* count_dags_in_graph */