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 "dags.h"
  19
  20 enum dag_counting_options_t {
  21   FIRMSTAT_COPY_CONSTANTS = 0x00000001,         /**< if set, constants will be treated as they are in
  22                                                      the same block as its successors */
  23 };
  24
  25 /**
  26  * walker for clearing node links
  27  */
  28 static void clear_links(ir_node *node, void *env)
  29 {
  30   set_irn_link(node, NULL);
  31 }
  32
  33 typedef struct _dag_entry_t dag_entry_t;
  34
  35 /**
  36  * Environment for connecting DAG's
  37  */
  38 typedef struct _dag_env_t {
  39   struct obstack obst;
  40   unsigned       num_of_dags;
  41   dag_entry_t    *list_of_dags;
  42   unsigned       options;               /**< DAG counting options */
  43 } dag_env_t;
  44
  45 /**
  46  * a DAG Entry
  47  */
  48 struct _dag_entry_t {
  49   ir_node     *root;
  50   unsigned    num_roots;
  51   unsigned    num_nodes;
  52   unsigned    num_inner_nodes;
  53   unsigned    is_dead;
  54   dag_entry_t *next;
  55 };
  56
  57 /**
  58  * a DAG Entry link
  59  */
  60 typedef struct _dag_link_t {
  61   dag_entry_t   *entry;
  62 } dag_link_t;
  63
  64 /**
  65  * walker for connecting DAGs and counting.
  66  */
  67 static void connect_dags(ir_node *node, void *env)
  68 {
  69   dag_env_t  *dag_env = env;
  70   int        i, arity;
  71   ir_node    *block;
  72   dag_link_t *link;
  73
  74   if (is_Block(node))
  75     return;
  76
  77   block = get_nodes_Block(node);
  78
  79   /* ignore start end end blocks */
  80   if (block == get_irg_start_block(current_ir_graph) ||
  81       block == get_irg_end_block(current_ir_graph))
  82     return;
  83
  84   link = get_irn_link(node);
  85
  86   if (! link) {
  87     /* not assigned node found, maybe a new root */
  88     dag_entry_t *entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
  89
  90     link        = obstack_alloc(&dag_env->obst, sizeof(*link));
  91     link->entry = entry;
  92
  93     entry->num_nodes       = 1;
  94     entry->num_roots       = 1;
  95     entry->num_inner_nodes = 0;
  96     entry->root            = node;
  97     entry->is_dead         = 0;
  98     entry->next            = dag_env->list_of_dags;
  99
 100     ++dag_env->num_of_dags;
 101     dag_env->list_of_dags = entry;
 102
 103     set_irn_link(node, link);
 104   }
 105
 106   /* put the predecessors into the same DAG as the current */
 107   for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 108     ir_node *prev      = get_irn_n(node, i);
 109     int     special    = 0;
 110
 111     /*
 112      * copy constants if requested into the DAG's
 113      * beware, do NOT add a link, as this will result in
 114      * wrong intersections
 115      */
 116     if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
 117       if (get_irn_op(prev) == op_Const || get_irn_op(prev) == op_SymConst) {
 118         ++link->entry->num_nodes;
 119         ++link->entry->num_inner_nodes;
 120       }
 121     }
 122
 123     if (get_nodes_Block(prev) == block) {
 124       dag_link_t *prev_link = get_irn_link(prev);
 125
 126       if (! prev_link) {
 127         /* not assigned node, do it */
 128         set_irn_link(prev, link);
 129         ++link->entry->num_nodes;
 130         ++link->entry->num_inner_nodes;
 131       }
 132       else if (prev_link->entry != link->entry) {
 133         /* two DAGs intersect */
 134
 135         assert(link->entry);
 136
 137         link->entry->num_roots       += prev_link->entry->num_roots;
 138         link->entry->num_nodes       += prev_link->entry->num_nodes;
 139         link->entry->num_inner_nodes += prev_link->entry->num_inner_nodes;
 140
 141         --dag_env->num_of_dags;
 142
 143         prev_link->entry->is_dead = 1;
 144         prev_link->entry          = link->entry;
 145       }
 146     }
 147   }
 148 }
 149
 150 /**
 151  * count the DAG's size of a graph
 152  */
 153 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
 154 {
 155   dag_env_t   root_env;
 156   dag_entry_t *entry;
 157
 158   /* do NOT check the const code irg */
 159   if (graph->irg == get_const_code_irg())
 160     return;
 161
 162   /* first step, clear the links */
 163   irg_walk_graph(graph->irg, clear_links, NULL, NULL);
 164
 165   obstack_init(&root_env.obst);
 166   root_env.num_of_dags  = 0;
 167   root_env.list_of_dags = NULL;
 168   root_env.options      = FIRMSTAT_COPY_CONSTANTS;
 169
 170   /* count them */
 171   irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
 172
 173   printf("Graph %p %s --- %d\n", graph->irg, get_entity_name(get_irg_entity(graph->irg)),
 174       root_env.num_of_dags);
 175
 176   for (entry = root_env.list_of_dags; entry; entry = entry->next) {
 177     if (entry->is_dead)
 178       continue;
 179
 180     printf("number of roots %d number of nodes %d inner %d %d\n",
 181       entry->num_roots,
 182       entry->num_nodes,
 183       entry->num_inner_nodes,
 184       get_irn_node_nr(entry->root));
 185   }
 186
 187   obstack_free(&root_env.obst, NULL);
 188 }