3 * File name: ir/ir/dags.c
4 * Purpose: Statistics for Firm. DAG's in graphs.
8 * Copyright: (c) 2004 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
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 */
26 * walker for clearing node links
28 static void clear_links(ir_node *node, void *env)
30 set_irn_link(node, NULL);
33 typedef struct _dag_entry_t dag_entry_t;
36 * Environment for connecting DAG's
38 typedef struct _dag_env_t {
41 dag_entry_t *list_of_dags;
42 unsigned options; /**< DAG counting options */
52 unsigned num_inner_nodes;
60 typedef struct _dag_link_t {
65 * walker for connecting DAGs and counting.
67 static void connect_dags(ir_node *node, void *env)
69 dag_env_t *dag_env = env;
77 block = get_nodes_Block(node);
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))
84 link = get_irn_link(node);
87 /* not assigned node found, maybe a new root */
88 dag_entry_t *entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
90 link = obstack_alloc(&dag_env->obst, sizeof(*link));
95 entry->num_inner_nodes = 0;
98 entry->next = dag_env->list_of_dags;
100 ++dag_env->num_of_dags;
101 dag_env->list_of_dags = entry;
103 set_irn_link(node, link);
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);
112 * copy constants if requested into the DAG's
113 * beware, do NOT add a link, as this will result in
114 * wrong intersections
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;
123 if (get_nodes_Block(prev) == block) {
124 dag_link_t *prev_link = get_irn_link(prev);
127 /* not assigned node, do it */
128 set_irn_link(prev, link);
129 ++link->entry->num_nodes;
130 ++link->entry->num_inner_nodes;
132 else if (prev_link->entry != link->entry) {
133 /* two DAGs intersect */
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;
141 --dag_env->num_of_dags;
143 prev_link->entry->is_dead = 1;
144 prev_link->entry = link->entry;
151 * count the DAG's size of a graph
153 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
158 /* do NOT check the const code irg */
159 if (graph->irg == get_const_code_irg())
162 /* first step, clear the links */
163 irg_walk_graph(graph->irg, clear_links, NULL, NULL);
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;
171 irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
173 printf("Graph %p %s --- %d\n", graph->irg, get_entity_name(get_irg_entity(graph->irg)),
174 root_env.num_of_dags);
176 for (entry = root_env.list_of_dags; entry; entry = entry->next) {
180 printf("number of roots %d number of nodes %d inner %d %d\n",
183 entry->num_inner_nodes,
184 get_irn_node_nr(entry->root));
187 obstack_free(&root_env.obst, NULL);