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.
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 */
31 * walker for clearing node links
33 static void clear_links(ir_node *node, void *env)
35 set_irn_link(node, NULL);
38 typedef struct _dag_entry_t dag_entry_t;
41 * Environment for connecting DAG's
43 typedef struct _dag_env_t {
46 dag_entry_t *list_of_dags;
47 unsigned options; /**< DAG counting options */
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 */
65 * return an DAG entry for the node n
67 static dag_entry_t *get_irn_dag_entry(ir_node *n)
69 dag_entry_t *res = get_irn_link(n);
74 for (p = res; p->link; p = p->link);
84 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
87 * checks wheater a node is an arg
89 static int is_arg(ir_node *node)
94 node = get_Proj_pred(node);
98 node = get_Proj_pred(node);
99 return get_irn_op(node) == op_Start;
103 * walker for connecting DAGs and counting.
105 static void connect_dags(ir_node *node, void *env)
107 dag_env_t *dag_env = env;
116 block = get_nodes_block(node);
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))
126 if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
129 mode = get_irn_mode(node);
130 if (mode == mode_X || mode == mode_M) {
131 /* do NOT count mode_X nodes */
135 entry = get_irn_dag_entry(node);
138 /* found a not assigned node, maybe a new root */
139 entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
141 entry->num_nodes = 1;
142 entry->num_roots = 1;
143 entry->num_inner_nodes = 0;
146 entry->next = dag_env->list_of_dags;
149 ++dag_env->num_of_dags;
150 dag_env->list_of_dags = entry;
152 set_irn_dag_entry(node, entry);
155 /* if this option is set, Loads are onways leaves */
156 if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && get_irn_op(node) == op_Load)
159 if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && get_irn_op(node) == op_Call)
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);
170 if (mode == mode_X || mode == mode_M)
174 * copy constants if requested into the DAG's
175 * beware, do NOT add a link, as this will result in
176 * wrong intersections
178 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
179 if (get_irn_op(prev) == op_Const || get_irn_op(prev) == op_SymConst) {
181 ++entry->num_inner_nodes;
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);
190 /* not assigned node, put it into the same DAG */
191 set_irn_dag_entry(prev, entry);
193 ++entry->num_inner_nodes;
196 if (prev_entry != entry) {
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;
203 --dag_env->num_of_dags;
205 prev_entry->is_dead = 1;
206 prev_entry->link = entry;
213 #define DEFAULT_RET 1
216 static unsigned mark_options;
219 * a vcg attribute hook
221 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
223 static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
226 /* do not count Bad / NoMem */
228 ir_op *op = get_irn_op(l);
230 if (op == op_NoMem || op == op_Bad)
233 /* check for additional options */
236 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && op == op_Load)
239 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && op == op_Call)
243 entry = get_irn_dag_entry(n);
247 fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
249 /* I know the color! */
254 * count the DAG's size of a graph
256 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
262 /* do NOT check the const code irg */
263 if (graph->irg == get_const_code_irg())
266 /* first step, clear the links */
267 irg_walk_graph(graph->irg, clear_links, NULL, NULL);
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;
275 irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
277 printf("Graph %p %s --- %d\n", graph->irg, get_entity_name(get_irg_entity(graph->irg)),
278 root_env.num_of_dags);
280 for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
285 printf("number of roots %d number of nodes %d inner %d %ld\n",
288 entry->num_inner_nodes,
289 get_irn_node_nr(entry->root));
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);
300 assert(id == root_env.num_of_dags);
302 obstack_free(&root_env.obst, NULL);