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

   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   Statistics for Firm. DAG's in graphs.
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include <assert.h>
  29
  30 #include "irprintf.h"
  31 #include "irdump.h"
  32 #include "dags.h"
  33 #include "irtools.h"
  34
  35 enum dag_counting_options_t {
  36         FIRMSTAT_COPY_CONSTANTS = 0x00000001,  /**< if set, constants will be treated as they are in
  37                                                     the same block as its successors */
  38         FIRMSTAT_LOAD_IS_LEAVE  = 0x00000002,  /**< Load nodes are always leaves */
  39         FIRMSTAT_CALL_IS_LEAVE  = 0x00000004,  /**< Call nodes are always leaves */
  40         FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008,  /**< arguments (Proj(Proj(Start)) are roots */
  41 };
  42
  43 typedef struct _dag_entry_t dag_entry_t;
  44
  45 /**
  46  * Environment for connecting DAG's
  47  */
  48 typedef struct _dag_env_t {
  49         struct obstack obst;
  50         unsigned       num_of_dags;   /**< Number of found DAGs so far. */
  51         dag_entry_t    *list_of_dags; /**< List of found DAGs. */
  52         unsigned       options;       /**< DAG counting options. */
  53 } dag_env_t;
  54
  55 /**
  56  * a DAG Entry
  57  */
  58 struct _dag_entry_t {
  59         unsigned    id;               /**< assigned ID for this DAG */
  60         ir_node     *root;            /**< one root of the DAG */
  61         unsigned    num_roots;        /**< number of root nodes in the DAG */
  62         unsigned    num_nodes;        /**< overall number of nodes in the DAG */
  63         unsigned    num_inner_nodes;  /**< number of inner nodes in the DAG */
  64         unsigned    is_dead:1;        /**< marks a dead entry */
  65         unsigned    is_tree:1;        /**< True if this DAG is a tree. */
  66         unsigned    is_ext_ref:1;     /**< True if this DAG is external referenced, so it cannot be combined. */
  67         dag_entry_t *next;            /**< link all entries of a DAG */
  68         dag_entry_t *link;            /**< if set, this entry is an ID */
  69 };
  70
  71 /**
  72  * return an DAG entry for the node n
  73  */
  74 static dag_entry_t *get_irn_dag_entry(ir_node *n)
  75 {
  76         dag_entry_t *p = get_irn_link(n);
  77
  78         if (p) {
  79                 /* skip any dead links */
  80                 if (p->link) {
  81                         do {
  82                                 p = p->link;
  83                         } while (p->link != NULL);
  84                         set_irn_link(n, p);
  85                 }
  86         }  /* if */
  87         return p;
  88 }  /* get_irn_dag_entry */
  89
  90 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
  91
  92 /**
  93  * checks whether a node is an arg
  94  */
  95 static int is_arg(ir_node *node)
  96 {
  97         if (! is_Proj(node))
  98                 return 0;
  99
 100         node = get_Proj_pred(node);
 101         if (! is_Proj(node))
 102                 return 0;
 103
 104         node = get_Proj_pred(node);
 105         return is_Start(node);
 106 }  /* is_arg */
 107
 108 /**
 109  * Allocate a new DAG entry.
 110  */
 111 static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node)
 112 {
 113         dag_entry_t *entry = OALLOC(&dag_env->obst, dag_entry_t);
 114
 115         entry->num_nodes       = 1;
 116         entry->num_roots       = 1;
 117         entry->num_inner_nodes = 0;
 118         entry->root            = node;
 119         entry->is_dead         = 0;
 120         entry->is_tree         = 1;
 121         entry->is_ext_ref      = 0;
 122         entry->next            = dag_env->list_of_dags;
 123         entry->link            = NULL;
 124
 125         ++dag_env->num_of_dags;
 126         dag_env->list_of_dags = entry;
 127
 128         set_irn_dag_entry(node, entry);
 129         return entry;
 130 }  /* new_dag_entry */
 131
 132 /**
 133  * Post-walker to detect DAG roots that are referenced form other blocks
 134  */
 135 static void find_dag_roots(ir_node *node, void *env)
 136 {
 137         dag_env_t   *dag_env = env;
 138         int         i, arity;
 139         dag_entry_t *entry;
 140         ir_node     *block;
 141
 142         if (is_Block(node))
 143                 return;
 144
 145         block = get_nodes_block(node);
 146
 147         /* ignore start end end blocks */
 148         if (block == get_irg_start_block(current_ir_graph) ||
 149                 block == get_irg_end_block(current_ir_graph)) {
 150                 return;
 151         }  /* if */
 152
 153         /* Phi nodes always references nodes from "other" block */
 154         if (is_Phi(node)) {
 155                 if (get_irn_mode(node) != mode_M) {
 156                         for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 157                                 ir_node *prev = get_irn_n(node, i);
 158
 159                                 if (is_Phi(prev))
 160                                         continue;
 161
 162                                 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 163                                         if (is_irn_constlike(prev))
 164                                                 continue;
 165                                 }  /* if */
 166
 167                                 entry = get_irn_dag_entry(prev);
 168
 169                                 if (! entry) {
 170                                         /* found an unassigned node, a new root */
 171                                         entry = new_dag_entry(dag_env, node);
 172                                         entry->is_ext_ref = 1;
 173                                 }  /* if */
 174                         }  /* for */
 175                 }  /* if */
 176         } else {
 177
 178                 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 179                                 ir_node *prev = get_irn_n(node, i);
 180                                 ir_mode *mode = get_irn_mode(prev);
 181
 182                                 if (mode == mode_X || mode == mode_M)
 183                                         continue;
 184
 185                                 if (is_Phi(prev))
 186                                         continue;
 187
 188                                 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 189                                         if (is_irn_constlike(prev))
 190                                                 continue;
 191                                 }  /* if */
 192
 193                                 if (get_nodes_block(prev) != block) {
 194                                         /* The predecessor is from another block. It forms
 195                                            a root. */
 196                                         entry = get_irn_dag_entry(prev);
 197                                         if (! entry) {
 198                                                 /* found an unassigned node, a new root */
 199                                                 entry = new_dag_entry(dag_env, node);
 200                                                 entry->is_ext_ref = 1;
 201                                         }  /* if */
 202                                 }  /* if */
 203                         }  /* for */
 204         }  /* if */
 205 }  /* find_dag_roots */
 206
 207 /**
 208  * Pre-walker for connecting DAGs and counting.
 209  */
 210 static void connect_dags(ir_node *node, void *env)
 211 {
 212         dag_env_t   *dag_env = env;
 213         int         i, arity;
 214         ir_node     *block;
 215         dag_entry_t *entry;
 216         ir_mode     *mode;
 217
 218         if (is_Block(node))
 219                 return;
 220
 221         block = get_nodes_block(node);
 222
 223         /* ignore start end end blocks */
 224         if (block == get_irg_start_block(current_ir_graph) ||
 225                 block == get_irg_end_block(current_ir_graph)) {
 226                 return;
 227         }  /* if */
 228
 229         /* ignore Phi nodes */
 230         if (is_Phi(node))
 231                 return;
 232
 233         if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
 234                 return;
 235
 236         mode = get_irn_mode(node);
 237         if (mode == mode_X || mode == mode_M) {
 238                 /* do NOT count mode_X and mode_M nodes */
 239                 return;
 240         }  /* if */
 241
 242         /* if this option is set, Loads are always leaves */
 243         if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && is_Load(node))
 244                 return;
 245
 246         if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && is_Call(node))
 247                 return;
 248
 249         entry = get_irn_dag_entry(node);
 250
 251         if (! entry) {
 252                 /* found an unassigned node, maybe a new root */
 253                 entry = new_dag_entry(dag_env, node);
 254         }  /* if */
 255
 256         /* put the predecessors into the same DAG as the current */
 257         for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 258                 ir_node *prev = get_irn_n(node, i);
 259                 ir_mode *mode = get_irn_mode(prev);
 260
 261                 if (is_Phi(prev))
 262                         continue;
 263
 264                 if (mode == mode_X || mode == mode_M)
 265                         continue;
 266
 267                 /*
 268                  * copy constants if requested into the DAG's
 269                  * beware, do NOT add a link, as this will result in
 270                  * wrong intersections
 271                  */
 272                 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 273                         if (is_irn_constlike(prev)) {
 274                                 ++entry->num_nodes;
 275                                 ++entry->num_inner_nodes;
 276                         }  /* if */
 277                 }  /* if */
 278
 279                 /* only nodes from the same block goes into the DAG */
 280                 if (get_nodes_block(prev) == block) {
 281                         dag_entry_t *prev_entry = get_irn_dag_entry(prev);
 282
 283                         if (! prev_entry) {
 284                                 /* not assigned node, put it into the same DAG */
 285                                 set_irn_dag_entry(prev, entry);
 286                                 ++entry->num_nodes;
 287                                 ++entry->num_inner_nodes;
 288                         } else {
 289                                 if (prev_entry == entry) {
 290                                         /* We found a node that is already assigned to this DAG.
 291                                            This DAG is not a tree. */
 292                                         entry->is_tree = 0;
 293                                 } else {
 294                                         /* two DAGs intersect: copy the data to one of them
 295                                            and kill the other */
 296                                         entry->num_roots       += prev_entry->num_roots;
 297                                         entry->num_nodes       += prev_entry->num_nodes;
 298                                         entry->num_inner_nodes += prev_entry->num_inner_nodes;
 299                                         entry->is_tree         &= prev_entry->is_tree;
 300
 301                                         --dag_env->num_of_dags;
 302
 303                                         prev_entry->is_dead = 1;
 304                                         prev_entry->link    = entry;
 305                                 }  /* if */
 306                         }  /* if */
 307                 }  /* if */
 308         }  /* for */
 309 }  /* connect_dags */
 310
 311 #define DEFAULT_RET     1
 312 #define COLOR_RET       1
 313
 314 static unsigned mark_options;
 315
 316 /**
 317  * a vcg attribute hook
 318  */
 319 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
 320 {
 321         static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
 322         dag_entry_t *entry;
 323
 324         /* do not count Bad / NoMem */
 325         if (l) {
 326                 ir_op *op = get_irn_op(l);
 327
 328                 if (op == op_NoMem || op == op_Bad)
 329                         return DEFAULT_RET;
 330
 331                 /* check for additional options */
 332                 op = get_irn_op(n);
 333
 334                 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && op == op_Load)
 335                         return DEFAULT_RET;
 336
 337                 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && op == op_Call)
 338                         return DEFAULT_RET;
 339         }  /* if */
 340
 341         entry = get_irn_dag_entry(n);
 342         if (! entry)
 343                 return DEFAULT_RET;
 344
 345         fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
 346
 347         /* I know the color! */
 348         return COLOR_RET;
 349 }  /* stat_dag_mark_hook */
 350
 351 /**
 352  * count the DAG's size of a graph
 353  *
 354  * @param global  the global entry
 355  * @param graph   the current graph entry
 356  */
 357 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
 358 {
 359         dag_env_t   root_env;
 360         dag_entry_t *entry;
 361         unsigned id;
 362         (void) global;
 363
 364         /* do NOT check the const code irg */
 365         if (graph->irg == get_const_code_irg())
 366                 return;
 367
 368         /* first step, clear the links */
 369         irg_walk_graph(graph->irg, firm_clear_link, NULL, NULL);
 370
 371         obstack_init(&root_env.obst);
 372         root_env.num_of_dags  = 0;
 373         root_env.list_of_dags = NULL;
 374         root_env.options      = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE;
 375
 376         /* find the DAG roots that are referenced from other block */
 377         irg_walk_graph(graph->irg, NULL, find_dag_roots, &root_env);
 378
 379         /* connect and count them */
 380         irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
 381
 382         printf("Graph %p %s --- %u\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)),
 383                 root_env.num_of_dags);
 384
 385         for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
 386                 if (entry->is_dead)
 387                         continue;
 388                 entry->id = id++;
 389
 390                 printf("number of roots %u number of nodes %u inner %u tree %u %ld\n",
 391                         entry->num_roots,
 392                         entry->num_nodes,
 393                         entry->num_inner_nodes,
 394                         entry->is_tree,
 395                         get_irn_node_nr(entry->root));
 396         }  /* for */
 397
 398 #if 1
 399         /* dump for test */
 400         mark_options = root_env.options;
 401         set_dump_node_vcgattr_hook(stat_dag_mark_hook);
 402         dump_ir_graph(graph->irg, "-dag");
 403         set_dump_node_vcgattr_hook(NULL);
 404 #endif
 405
 406         assert(id == root_env.num_of_dags);
 407
 408         obstack_free(&root_env.obst, NULL);
 409 }  /* count_dags_in_graph */