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

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