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
  22 enum dag_counting_options_t {
  23   FIRMSTAT_COPY_CONSTANTS = 0x00000001,         /**< if set, constants will be treated as they are in
  24                                                      the same block as its successors */
  25 };
  26
  27 /**
  28  * walker for clearing node links
  29  */
  30 static void clear_links(ir_node *node, void *env)
  31 {
  32   set_irn_link(node, NULL);
  33 }
  34
  35 typedef struct _dag_entry_t dag_entry_t;
  36
  37 /**
  38  * Environment for connecting DAG's
  39  */
  40 typedef struct _dag_env_t {
  41   struct obstack obst;
  42   unsigned       num_of_dags;
  43   dag_entry_t    *list_of_dags;
  44   unsigned       options;               /**< DAG counting options */
  45 } dag_env_t;
  46
  47 /**
  48  * a DAG Entry
  49  */
  50 struct _dag_entry_t {
  51   unsigned    id;                       /**< assigned ID for this DAG */
  52   ir_node     *root;                    /**< one root of the DAG */
  53   unsigned    num_roots;                /**< number of root nodes in the DAG */
  54   unsigned    num_nodes;                /**< overall number of nodes in the DAG */
  55   unsigned    num_inner_nodes;          /**< number of inner nodes in the DAG */
  56   unsigned    is_dead;                  /**< marks a dead entry */
  57   dag_entry_t *next;                    /**< link all entries of a DAG */
  58   dag_entry_t *link;                    /**< if set, this entry is an ID */
  59 };
  60
  61 /**
  62  * return an DAG entry for the node n
  63  */
  64 static dag_entry_t *get_irn_dag_entry(ir_node *n)
  65 {
  66   dag_entry_t *res = get_irn_link(n);
  67
  68   if (res) {
  69     dag_entry_t *p;
  70
  71     for (p = res; p->link; p = p->link);
  72
  73     if (p != res)
  74       set_irn_link(n, p);
  75
  76     return p;
  77   }
  78   return NULL;
  79 }
  80
  81 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
  82
  83 /**
  84  * walker for connecting DAGs and counting.
  85  */
  86 static void connect_dags(ir_node *node, void *env)
  87 {
  88   dag_env_t   *dag_env = env;
  89   int         i, arity;
  90   ir_node     *block;
  91   dag_entry_t *entry;
  92   ir_mode     *mode;
  93
  94   if (is_Block(node))
  95     return;
  96
  97   block = get_nodes_block(node);
  98
  99   /* ignore start end end blocks */
 100   if (block == get_irg_start_block(current_ir_graph) ||
 101       block == get_irg_end_block(current_ir_graph))
 102     return;
 103
 104   if (is_Phi(node))
 105     return;
 106
 107   mode = get_irn_mode(node);
 108   if (mode == mode_X || mode == mode_M) {
 109     /* do NOT count mode_X nodes */
 110     return;
 111   }
 112
 113   entry = get_irn_dag_entry(node);
 114
 115   if (! entry) {
 116     /* found a not assigned node, maybe a new root */
 117     entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
 118
 119     entry->num_nodes       = 1;
 120     entry->num_roots       = 1;
 121     entry->num_inner_nodes = 0;
 122     entry->root            = node;
 123     entry->is_dead         = 0;
 124     entry->next            = dag_env->list_of_dags;
 125     entry->link            = NULL;
 126
 127     ++dag_env->num_of_dags;
 128     dag_env->list_of_dags = entry;
 129
 130     set_irn_dag_entry(node, entry);
 131   }
 132
 133   /* put the predecessors into the same DAG as the current */
 134   for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 135     ir_node *prev = get_irn_n(node, i);
 136     ir_mode *mode = get_irn_mode(prev);
 137
 138     if (is_Phi(prev))
 139       continue;
 140
 141     if (mode == mode_X || mode == mode_M)
 142       continue;
 143
 144     /*
 145      * copy constants if requested into the DAG's
 146      * beware, do NOT add a link, as this will result in
 147      * wrong intersections
 148      */
 149     if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 150       if (get_irn_op(prev) == op_Const || get_irn_op(prev) == op_SymConst) {
 151         ++entry->num_nodes;
 152         ++entry->num_inner_nodes;
 153       }
 154     }
 155
 156     /* only nodes from the same block goes into the DAG */
 157     if (get_nodes_block(prev) == block) {
 158       dag_entry_t *prev_entry = get_irn_dag_entry(prev);
 159
 160       if (! prev_entry) {
 161         /* not assigned node, put it into the same DAG */
 162         set_irn_dag_entry(prev, entry);
 163         ++entry->num_nodes;
 164         ++entry->num_inner_nodes;
 165       }
 166       else {
 167         if (prev_entry != entry) {
 168
 169           /* two DAGs intersect */
 170           entry->num_roots       += prev_entry->num_roots;
 171           entry->num_nodes       += prev_entry->num_nodes;
 172           entry->num_inner_nodes += prev_entry->num_inner_nodes;
 173
 174           --dag_env->num_of_dags;
 175
 176           prev_entry->is_dead = 1;
 177           prev_entry->link    = entry;
 178         }
 179       }
 180     }
 181   }
 182 }
 183
 184 /**
 185  * a vcg attribute hook
 186  */
 187 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
 188 {
 189   static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
 190   dag_entry_t *entry;
 191
 192   /* do not count Bad / NoMem */
 193   if (l && (get_irn_op(l) == op_NoMem || get_irn_op(l) == op_Bad))
 194     return 0;
 195
 196   entry = get_irn_dag_entry(n);
 197   if (! entry)
 198     return 0;
 199
 200   fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
 201
 202   /* I know the color! */
 203   return 1;
 204 }
 205
 206 /**
 207  * count the DAG's size of a graph
 208  */
 209 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
 210 {
 211   dag_env_t   root_env;
 212   dag_entry_t *entry;
 213   unsigned id;
 214
 215   /* do NOT check the const code irg */
 216   if (graph->irg == get_const_code_irg())
 217     return;
 218
 219   /* first step, clear the links */
 220   irg_walk_graph(graph->irg, clear_links, NULL, NULL);
 221
 222   obstack_init(&root_env.obst);
 223   root_env.num_of_dags  = 0;
 224   root_env.list_of_dags = NULL;
 225   root_env.options      = FIRMSTAT_COPY_CONSTANTS;
 226
 227   /* count them */
 228   irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
 229
 230   printf("Graph %p %s --- %d\n", graph->irg, get_entity_name(get_irg_entity(graph->irg)),
 231       root_env.num_of_dags);
 232
 233   for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
 234     if (entry->is_dead)
 235       continue;
 236     entry->id = id++;
 237
 238     printf("number of roots %d number of nodes %d inner %d %ld\n",
 239       entry->num_roots,
 240       entry->num_nodes,
 241       entry->num_inner_nodes,
 242       get_irn_node_nr(entry->root));
 243   }
 244
 245 #if 1
 246   /* dump for test */
 247   set_dump_node_vcgattr_hook(stat_dag_mark_hook);
 248   dump_ir_block_graph(graph->irg, "-dag");
 249   set_dump_node_vcgattr_hook(NULL);
 250 #endif
 251
 252   assert(id == root_env.num_of_dags);
 253
 254   obstack_free(&root_env.obst, NULL);
 255 }