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.
23 enum dag_counting_options_t {
24 FIRMSTAT_COPY_CONSTANTS = 0x00000001, /**< if set, constants will be treated as they are in
25 the same block as its successors */
26 FIRMSTAT_LOAD_IS_LEAVE = 0x00000002, /**< Load nodes are always leaves */
27 FIRMSTAT_CALL_IS_LEAVE = 0x00000004, /**< Call nodes are always leaves */
28 FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008, /**< arguments (Proj(Proj(Start)) are roots */
31 typedef struct _dag_entry_t dag_entry_t;
34 * Environment for connecting DAG's
36 typedef struct _dag_env_t {
38 unsigned num_of_dags; /**< Number of found DAGs so far. */
39 dag_entry_t *list_of_dags; /**< List of found DAGs. */
40 unsigned options; /**< DAG counting options. */
47 unsigned id; /**< assigned ID for this DAG */
48 ir_node *root; /**< one root of the DAG */
49 unsigned num_roots; /**< number of root nodes in the DAG */
50 unsigned num_nodes; /**< overall number of nodes in the DAG */
51 unsigned num_inner_nodes; /**< number of inner nodes in the DAG */
52 unsigned is_dead:1; /**< marks a dead entry */
53 unsigned is_tree:1; /**< True if this DAG is a tree. */
54 unsigned is_ext_ref:1; /**< True if this DAG is external referenced, so it cannot be combined. */
55 dag_entry_t *next; /**< link all entries of a DAG */
56 dag_entry_t *link; /**< if set, this entry is an ID */
60 * return an DAG entry for the node n
62 static dag_entry_t *get_irn_dag_entry(ir_node *n)
64 dag_entry_t *p = get_irn_link(n);
67 /* skip any dead links */
71 } while (p->link != NULL);
76 } /* get_irn_dag_entry */
78 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
81 * checks whether a node is an arg
83 static int is_arg(ir_node *node)
88 node = get_Proj_pred(node);
92 node = get_Proj_pred(node);
93 return get_irn_op(node) == op_Start;
97 * Allocate a new DAG entry.
99 static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node) {
100 dag_entry_t *entry = obstack_alloc(&dag_env->obst, sizeof(*entry));
102 entry->num_nodes = 1;
103 entry->num_roots = 1;
104 entry->num_inner_nodes = 0;
108 entry->is_ext_ref = 0;
109 entry->next = dag_env->list_of_dags;
112 ++dag_env->num_of_dags;
113 dag_env->list_of_dags = entry;
115 set_irn_dag_entry(node, entry);
117 } /* new_dag_entry */
120 * Post-walker to detect DAG roots that are referenced form other blocks
122 static void find_dag_roots(ir_node *node, void *env)
124 dag_env_t *dag_env = env;
132 block = get_nodes_block(node);
134 /* ignore start end end blocks */
135 if (block == get_irg_start_block(current_ir_graph) ||
136 block == get_irg_end_block(current_ir_graph)) {
140 /* Phi nodes always references nodes from "other" block */
142 if (get_irn_mode(node) != mode_M) {
143 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
144 ir_node *prev = get_irn_n(node, i);
149 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
150 if (is_irn_constlike(prev))
154 entry = get_irn_dag_entry(prev);
157 /* found an unassigned node, a new root */
158 entry = new_dag_entry(dag_env, node);
159 entry->is_ext_ref = 1;
165 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
166 ir_node *prev = get_irn_n(node, i);
167 ir_mode *mode = get_irn_mode(prev);
169 if (mode == mode_X || mode == mode_M)
175 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
176 if (is_irn_constlike(prev))
180 if (get_nodes_block(prev) != block) {
181 /* The predecessor is from another block. It forms
183 entry = get_irn_dag_entry(prev);
185 /* found an unassigned node, a new root */
186 entry = new_dag_entry(dag_env, node);
187 entry->is_ext_ref = 1;
192 } /* find_dag_roots */
195 * Pre-walker for connecting DAGs and counting.
197 static void connect_dags(ir_node *node, void *env)
199 dag_env_t *dag_env = env;
208 block = get_nodes_block(node);
210 /* ignore start end end blocks */
211 if (block == get_irg_start_block(current_ir_graph) ||
212 block == get_irg_end_block(current_ir_graph)) {
216 /* ignore Phi nodes */
220 if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
223 mode = get_irn_mode(node);
224 if (mode == mode_X || mode == mode_M) {
225 /* do NOT count mode_X and mode_M nodes */
229 /* if this option is set, Loads are always leaves */
230 if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && get_irn_op(node) == op_Load)
233 if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && get_irn_op(node) == op_Call)
236 entry = get_irn_dag_entry(node);
239 /* found an unassigned node, maybe a new root */
240 entry = new_dag_entry(dag_env, node);
243 /* put the predecessors into the same DAG as the current */
244 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
245 ir_node *prev = get_irn_n(node, i);
246 ir_mode *mode = get_irn_mode(prev);
251 if (mode == mode_X || mode == mode_M)
255 * copy constants if requested into the DAG's
256 * beware, do NOT add a link, as this will result in
257 * wrong intersections
259 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
260 if (is_irn_constlike(prev)) {
262 ++entry->num_inner_nodes;
266 /* only nodes from the same block goes into the DAG */
267 if (get_nodes_block(prev) == block) {
268 dag_entry_t *prev_entry = get_irn_dag_entry(prev);
271 /* not assigned node, put it into the same DAG */
272 set_irn_dag_entry(prev, entry);
274 ++entry->num_inner_nodes;
276 if (prev_entry == entry) {
277 /* We found a node that is already assigned to this DAG.
278 This DAG is not a tree. */
281 /* two DAGs intersect: copy the data to one of them
282 and kill the other */
283 entry->num_roots += prev_entry->num_roots;
284 entry->num_nodes += prev_entry->num_nodes;
285 entry->num_inner_nodes += prev_entry->num_inner_nodes;
286 entry->is_tree &= prev_entry->is_tree;
288 --dag_env->num_of_dags;
290 prev_entry->is_dead = 1;
291 prev_entry->link = entry;
298 #define DEFAULT_RET 1
301 static unsigned mark_options;
304 * a vcg attribute hook
306 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
308 static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
311 /* do not count Bad / NoMem */
313 ir_op *op = get_irn_op(l);
315 if (op == op_NoMem || op == op_Bad)
318 /* check for additional options */
321 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && op == op_Load)
324 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && op == op_Call)
328 entry = get_irn_dag_entry(n);
332 fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
334 /* I know the color! */
336 } /* stat_dag_mark_hook */
339 * count the DAG's size of a graph
341 * @param global the global entry
342 * @param graph the current graph entry
344 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
350 /* do NOT check the const code irg */
351 if (graph->irg == get_const_code_irg())
354 /* first step, clear the links */
355 irg_walk_graph(graph->irg, firm_clear_link, NULL, NULL);
357 obstack_init(&root_env.obst);
358 root_env.num_of_dags = 0;
359 root_env.list_of_dags = NULL;
360 root_env.options = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE;
362 /* find the DAG roots that are referenced from other block */
363 irg_walk_graph(graph->irg, NULL, find_dag_roots, &root_env);
365 /* connect and count them */
366 irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
368 printf("Graph %p %s --- %d\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)),
369 root_env.num_of_dags);
371 for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
376 printf("number of roots %d number of nodes %d inner %d tree %u %ld\n",
379 entry->num_inner_nodes,
381 get_irn_node_nr(entry->root));
386 mark_options = root_env.options;
387 set_dump_node_vcgattr_hook(stat_dag_mark_hook);
388 dump_ir_block_graph(graph->irg, "-dag");
389 set_dump_node_vcgattr_hook(NULL);
392 assert(id == root_env.num_of_dags);
394 obstack_free(&root_env.obst, NULL);
395 } /* count_dags_in_graph */