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