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