2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Statistics for Firm. DAG's in graphs.
21 enum dag_counting_options_t {
22 FIRMSTAT_COPY_CONSTANTS = 0x00000001, /**< if set, constants will be treated as they are in
23 the same block as its successors */
24 FIRMSTAT_LOAD_IS_LEAVE = 0x00000002, /**< Load nodes are always leaves */
25 FIRMSTAT_CALL_IS_LEAVE = 0x00000004, /**< Call nodes are always leaves */
26 FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008, /**< arguments (Proj(Proj(Start)) are roots */
29 typedef struct dag_entry_t dag_entry_t;
32 * Environment for connecting DAG's
34 typedef struct dag_env_t {
36 unsigned num_of_dags; /**< Number of found DAGs so far. */
37 dag_entry_t *list_of_dags; /**< List of found DAGs. */
38 unsigned options; /**< DAG counting options. */
45 unsigned id; /**< assigned ID for this DAG */
46 ir_node *root; /**< one root of the DAG */
47 unsigned num_roots; /**< number of root nodes in the DAG */
48 unsigned num_nodes; /**< overall number of nodes in the DAG */
49 unsigned num_inner_nodes; /**< number of inner nodes in the DAG */
50 unsigned is_dead:1; /**< marks a dead entry */
51 unsigned is_tree:1; /**< True if this DAG is a tree. */
52 unsigned is_ext_ref:1; /**< True if this DAG is external referenced, so it cannot be combined. */
53 dag_entry_t *next; /**< link all entries of a DAG */
54 dag_entry_t *link; /**< if set, this entry is an ID */
58 * return an DAG entry for the node n
60 static dag_entry_t *get_irn_dag_entry(const ir_node *n)
62 dag_entry_t *p = (dag_entry_t*)get_irn_link(n);
65 /* skip any dead links */
69 } while (p->link != NULL);
70 /* hacky cast to ir_node* */
71 set_irn_link((ir_node*)n, p);
77 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
80 * checks whether a node is an arg
82 static int is_arg(ir_node *node)
87 node = get_Proj_pred(node);
91 node = get_Proj_pred(node);
92 return is_Start(node);
96 * Allocate a new DAG entry.
98 static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node)
100 dag_entry_t *entry = OALLOC(&dag_env->obst, dag_entry_t);
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);
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 = (dag_env_t*)env;
132 block = get_nodes_block(node);
134 /* ignore start end end blocks */
135 ir_graph *const irg = get_Block_irg(block);
136 if (block == get_irg_start_block(irg) || block == get_irg_end_block(irg))
139 /* Phi nodes always references nodes from "other" block */
141 if (get_irn_mode(node) != mode_M) {
142 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
143 ir_node *prev = get_irn_n(node, i);
148 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
149 if (is_irn_constlike(prev))
153 entry = get_irn_dag_entry(prev);
156 /* found an unassigned node, a new root */
157 entry = new_dag_entry(dag_env, node);
158 entry->is_ext_ref = 1;
164 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
165 ir_node *prev = get_irn_n(node, i);
166 ir_mode *mode = get_irn_mode(prev);
168 if (mode == mode_X || mode == mode_M)
174 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
175 if (is_irn_constlike(prev))
179 if (get_nodes_block(prev) != block) {
180 /* The predecessor is from another block. It forms
182 entry = get_irn_dag_entry(prev);
184 /* found an unassigned node, a new root */
185 entry = new_dag_entry(dag_env, node);
186 entry->is_ext_ref = 1;
194 * Pre-walker for connecting DAGs and counting.
196 static void connect_dags(ir_node *node, void *env)
198 dag_env_t *dag_env = (dag_env_t*)env;
207 block = get_nodes_block(node);
209 /* ignore start end end blocks */
210 ir_graph *const irg = get_Block_irg(block);
211 if (block == get_irg_start_block(irg) || block == get_irg_end_block(irg))
214 /* ignore Phi nodes */
218 if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
221 mode = get_irn_mode(node);
222 if (mode == mode_X || mode == mode_M) {
223 /* do NOT count mode_X and mode_M nodes */
227 /* if this option is set, Loads are always leaves */
228 if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && is_Load(node))
231 if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && is_Call(node))
234 entry = get_irn_dag_entry(node);
237 /* found an unassigned node, maybe a new root */
238 entry = new_dag_entry(dag_env, node);
241 /* put the predecessors into the same DAG as the current */
242 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
243 ir_node *prev = get_irn_n(node, i);
244 ir_mode *mode = get_irn_mode(prev);
249 if (mode == mode_X || mode == mode_M)
253 * copy constants if requested into the DAG's
254 * beware, do NOT add a link, as this will result in
255 * wrong intersections
257 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
258 if (is_irn_constlike(prev)) {
260 ++entry->num_inner_nodes;
264 /* only nodes from the same block goes into the DAG */
265 if (get_nodes_block(prev) == block) {
266 dag_entry_t *prev_entry = get_irn_dag_entry(prev);
269 /* not assigned node, put it into the same DAG */
270 set_irn_dag_entry(prev, entry);
272 ++entry->num_inner_nodes;
274 if (prev_entry == entry) {
275 /* We found a node that is already assigned to this DAG.
276 This DAG is not a tree. */
279 /* two DAGs intersect: copy the data to one of them
280 and kill the other */
281 entry->num_roots += prev_entry->num_roots;
282 entry->num_nodes += prev_entry->num_nodes;
283 entry->num_inner_nodes += prev_entry->num_inner_nodes;
284 entry->is_tree &= prev_entry->is_tree;
286 --dag_env->num_of_dags;
288 prev_entry->is_dead = 1;
289 prev_entry->link = entry;
296 #define DEFAULT_RET 1
299 static unsigned mark_options;
302 * a vcg attribute hook
304 static int stat_dag_mark_hook(FILE *F, const ir_node *n, const ir_node *l)
306 static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
309 /* do not count Bad / NoMem */
311 if (is_NoMem(l) || is_Bad(l))
314 /* check for additional options */
315 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && is_Load(n))
318 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && is_Call(n))
322 entry = get_irn_dag_entry(n);
326 fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
328 /* I know the color! */
333 * count the DAG's size of a graph
335 * @param global the global entry
336 * @param graph the current graph entry
338 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
345 /* do NOT check the const code irg */
346 if (graph->irg == get_const_code_irg())
349 /* first step, clear the links */
350 irg_walk_graph(graph->irg, firm_clear_link, NULL, NULL);
352 obstack_init(&root_env.obst);
353 root_env.num_of_dags = 0;
354 root_env.list_of_dags = NULL;
355 root_env.options = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE;
357 /* find the DAG roots that are referenced from other block */
358 irg_walk_graph(graph->irg, NULL, find_dag_roots, &root_env);
360 /* connect and count them */
361 irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
363 printf("Graph %p %s --- %u\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)),
364 root_env.num_of_dags);
366 for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
371 printf("number of roots %u number of nodes %u inner %u tree %u %ld\n",
374 entry->num_inner_nodes,
375 (unsigned)entry->is_tree,
376 get_irn_node_nr(entry->root));
380 mark_options = root_env.options;
381 set_dump_node_vcgattr_hook(stat_dag_mark_hook);
382 dump_ir_graph(graph->irg, "dag");
383 set_dump_node_vcgattr_hook(NULL);
385 assert(id == root_env.num_of_dags);
387 obstack_free(&root_env.obst, NULL);