2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Statistics for Firm. DAG's in graphs.
23 * @author Michael Beck
35 enum dag_counting_options_t {
36 FIRMSTAT_COPY_CONSTANTS = 0x00000001, /**< if set, constants will be treated as they are in
37 the same block as its successors */
38 FIRMSTAT_LOAD_IS_LEAVE = 0x00000002, /**< Load nodes are always leaves */
39 FIRMSTAT_CALL_IS_LEAVE = 0x00000004, /**< Call nodes are always leaves */
40 FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008, /**< arguments (Proj(Proj(Start)) are roots */
43 typedef struct dag_entry_t dag_entry_t;
46 * Environment for connecting DAG's
48 typedef struct dag_env_t {
50 unsigned num_of_dags; /**< Number of found DAGs so far. */
51 dag_entry_t *list_of_dags; /**< List of found DAGs. */
52 unsigned options; /**< DAG counting options. */
59 unsigned id; /**< assigned ID for this DAG */
60 ir_node *root; /**< one root of the DAG */
61 unsigned num_roots; /**< number of root nodes in the DAG */
62 unsigned num_nodes; /**< overall number of nodes in the DAG */
63 unsigned num_inner_nodes; /**< number of inner nodes in the DAG */
64 unsigned is_dead:1; /**< marks a dead entry */
65 unsigned is_tree:1; /**< True if this DAG is a tree. */
66 unsigned is_ext_ref:1; /**< True if this DAG is external referenced, so it cannot be combined. */
67 dag_entry_t *next; /**< link all entries of a DAG */
68 dag_entry_t *link; /**< if set, this entry is an ID */
72 * return an DAG entry for the node n
74 static dag_entry_t *get_irn_dag_entry(ir_node *n)
76 dag_entry_t *p = get_irn_link(n);
79 /* skip any dead links */
83 } while (p->link != NULL);
88 } /* get_irn_dag_entry */
90 #define set_irn_dag_entry(n, e) set_irn_link(n, e)
93 * checks whether a node is an arg
95 static int is_arg(ir_node *node)
100 node = get_Proj_pred(node);
104 node = get_Proj_pred(node);
105 return is_Start(node);
109 * Allocate a new DAG entry.
111 static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node)
113 dag_entry_t *entry = OALLOC(&dag_env->obst, dag_entry_t);
115 entry->num_nodes = 1;
116 entry->num_roots = 1;
117 entry->num_inner_nodes = 0;
121 entry->is_ext_ref = 0;
122 entry->next = dag_env->list_of_dags;
125 ++dag_env->num_of_dags;
126 dag_env->list_of_dags = entry;
128 set_irn_dag_entry(node, entry);
130 } /* new_dag_entry */
133 * Post-walker to detect DAG roots that are referenced form other blocks
135 static void find_dag_roots(ir_node *node, void *env)
137 dag_env_t *dag_env = env;
145 block = get_nodes_block(node);
147 /* ignore start end end blocks */
148 if (block == get_irg_start_block(current_ir_graph) ||
149 block == get_irg_end_block(current_ir_graph)) {
153 /* Phi nodes always references nodes from "other" block */
155 if (get_irn_mode(node) != mode_M) {
156 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
157 ir_node *prev = get_irn_n(node, i);
162 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
163 if (is_irn_constlike(prev))
167 entry = get_irn_dag_entry(prev);
170 /* found an unassigned node, a new root */
171 entry = new_dag_entry(dag_env, node);
172 entry->is_ext_ref = 1;
178 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
179 ir_node *prev = get_irn_n(node, i);
180 ir_mode *mode = get_irn_mode(prev);
182 if (mode == mode_X || mode == mode_M)
188 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
189 if (is_irn_constlike(prev))
193 if (get_nodes_block(prev) != block) {
194 /* The predecessor is from another block. It forms
196 entry = get_irn_dag_entry(prev);
198 /* found an unassigned node, a new root */
199 entry = new_dag_entry(dag_env, node);
200 entry->is_ext_ref = 1;
205 } /* find_dag_roots */
208 * Pre-walker for connecting DAGs and counting.
210 static void connect_dags(ir_node *node, void *env)
212 dag_env_t *dag_env = env;
221 block = get_nodes_block(node);
223 /* ignore start end end blocks */
224 if (block == get_irg_start_block(current_ir_graph) ||
225 block == get_irg_end_block(current_ir_graph)) {
229 /* ignore Phi nodes */
233 if (dag_env->options & FIRMSTAT_ARGS_ARE_ROOTS && is_arg(node))
236 mode = get_irn_mode(node);
237 if (mode == mode_X || mode == mode_M) {
238 /* do NOT count mode_X and mode_M nodes */
242 /* if this option is set, Loads are always leaves */
243 if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && is_Load(node))
246 if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && is_Call(node))
249 entry = get_irn_dag_entry(node);
252 /* found an unassigned node, maybe a new root */
253 entry = new_dag_entry(dag_env, node);
256 /* put the predecessors into the same DAG as the current */
257 for (i = 0, arity = get_irn_arity(node); i < arity; ++i) {
258 ir_node *prev = get_irn_n(node, i);
259 ir_mode *mode = get_irn_mode(prev);
264 if (mode == mode_X || mode == mode_M)
268 * copy constants if requested into the DAG's
269 * beware, do NOT add a link, as this will result in
270 * wrong intersections
272 if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) {
273 if (is_irn_constlike(prev)) {
275 ++entry->num_inner_nodes;
279 /* only nodes from the same block goes into the DAG */
280 if (get_nodes_block(prev) == block) {
281 dag_entry_t *prev_entry = get_irn_dag_entry(prev);
284 /* not assigned node, put it into the same DAG */
285 set_irn_dag_entry(prev, entry);
287 ++entry->num_inner_nodes;
289 if (prev_entry == entry) {
290 /* We found a node that is already assigned to this DAG.
291 This DAG is not a tree. */
294 /* two DAGs intersect: copy the data to one of them
295 and kill the other */
296 entry->num_roots += prev_entry->num_roots;
297 entry->num_nodes += prev_entry->num_nodes;
298 entry->num_inner_nodes += prev_entry->num_inner_nodes;
299 entry->is_tree &= prev_entry->is_tree;
301 --dag_env->num_of_dags;
303 prev_entry->is_dead = 1;
304 prev_entry->link = entry;
311 #define DEFAULT_RET 1
314 static unsigned mark_options;
317 * a vcg attribute hook
319 static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l)
321 static const char *colors[] = { "purple", "pink", "lightblue", "orange", "khaki", "orchid", "lilac", "turquoise" };
324 /* do not count Bad / NoMem */
326 ir_op *op = get_irn_op(l);
328 if (op == op_NoMem || op == op_Bad)
331 /* check for additional options */
334 if (mark_options & FIRMSTAT_LOAD_IS_LEAVE && op == op_Load)
337 if (mark_options & FIRMSTAT_CALL_IS_LEAVE && op == op_Call)
341 entry = get_irn_dag_entry(n);
345 fprintf(F, "color: %s info3: \"DAG id: %u\"", colors[entry->id & 7], entry->id);
347 /* I know the color! */
349 } /* stat_dag_mark_hook */
352 * count the DAG's size of a graph
354 * @param global the global entry
355 * @param graph the current graph entry
357 void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph)
364 /* do NOT check the const code irg */
365 if (graph->irg == get_const_code_irg())
368 /* first step, clear the links */
369 irg_walk_graph(graph->irg, firm_clear_link, NULL, NULL);
371 obstack_init(&root_env.obst);
372 root_env.num_of_dags = 0;
373 root_env.list_of_dags = NULL;
374 root_env.options = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE;
376 /* find the DAG roots that are referenced from other block */
377 irg_walk_graph(graph->irg, NULL, find_dag_roots, &root_env);
379 /* connect and count them */
380 irg_walk_graph(graph->irg, connect_dags, NULL, &root_env);
382 printf("Graph %p %s --- %u\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)),
383 root_env.num_of_dags);
385 for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) {
390 printf("number of roots %u number of nodes %u inner %u tree %u %ld\n",
393 entry->num_inner_nodes,
395 get_irn_node_nr(entry->root));
400 mark_options = root_env.options;
401 set_dump_node_vcgattr_hook(stat_dag_mark_hook);
402 dump_ir_graph(graph->irg, "-dag");
403 set_dump_node_vcgattr_hook(NULL);
406 assert(id == root_env.num_of_dags);
408 obstack_free(&root_env.obst, NULL);
409 } /* count_dags_in_graph */