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

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