X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fstat%2Fdags.c;h=2612fb323326c2edd535e175b5f6c46b4d756bf3;hb=78bac126e7f9ca55761ab892ebfa9c19a4a65fcf;hp=cdece5452da8944fc358363d73101c0f0e716109;hpb=913726a12709fd431025fdd1f4bc520269cb0372;p=libfirm diff --git a/ir/stat/dags.c b/ir/stat/dags.c index cdece5452..2612fb323 100644 --- a/ir/stat/dags.c +++ b/ir/stat/dags.c @@ -1,17 +1,29 @@ /* - * Project: libFIRM - * File name: ir/ir/dags.c - * Purpose: Statistics for Firm. DAG's in graphs. - * Author: Michael Beck - * Created: - * CVS-ID: $Id$ - * Copyright: (c) 2004 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +/** + * @file + * @brief Statistics for Firm. DAG's in graphs. + * @author Michael Beck + * @version $Id$ + */ +#include "config.h" #include @@ -28,28 +40,30 @@ enum dag_counting_options_t { FIRMSTAT_ARGS_ARE_ROOTS = 0x00000008, /**< arguments (Proj(Proj(Start)) are roots */ }; -typedef struct _dag_entry_t dag_entry_t; +typedef struct dag_entry_t dag_entry_t; /** * Environment for connecting DAG's */ -typedef struct _dag_env_t { +typedef struct dag_env_t { struct obstack obst; - unsigned num_of_dags; - dag_entry_t *list_of_dags; - unsigned options; /**< DAG counting options */ + unsigned num_of_dags; /**< Number of found DAGs so far. */ + dag_entry_t *list_of_dags; /**< List of found DAGs. */ + unsigned options; /**< DAG counting options. */ } dag_env_t; /** * a DAG Entry */ -struct _dag_entry_t { +struct dag_entry_t { unsigned id; /**< assigned ID for this DAG */ ir_node *root; /**< one root of the DAG */ unsigned num_roots; /**< number of root nodes in the DAG */ unsigned num_nodes; /**< overall number of nodes in the DAG */ unsigned num_inner_nodes; /**< number of inner nodes in the DAG */ - unsigned is_dead; /**< marks a dead entry */ + unsigned is_dead:1; /**< marks a dead entry */ + unsigned is_tree:1; /**< True if this DAG is a tree. */ + unsigned is_ext_ref:1; /**< True if this DAG is external referenced, so it cannot be combined. */ dag_entry_t *next; /**< link all entries of a DAG */ dag_entry_t *link; /**< if set, this entry is an ID */ }; @@ -59,25 +73,24 @@ struct _dag_entry_t { */ static dag_entry_t *get_irn_dag_entry(ir_node *n) { - dag_entry_t *res = get_irn_link(n); - - if (res) { - dag_entry_t *p; - - for (p = res; p->link; p = p->link); - - if (p != res) + dag_entry_t *p = (dag_entry_t*)get_irn_link(n); + + if (p) { + /* skip any dead links */ + if (p->link) { + do { + p = p->link; + } while (p->link != NULL); set_irn_link(n, p); - - return p; + } } /* if */ - return NULL; + return p; } /* get_irn_dag_entry */ #define set_irn_dag_entry(n, e) set_irn_link(n, e) /** - * checks wether a node is an arg + * checks whether a node is an arg */ static int is_arg(ir_node *node) { @@ -89,15 +102,114 @@ static int is_arg(ir_node *node) return 0; node = get_Proj_pred(node); - return get_irn_op(node) == op_Start; + return is_Start(node); } /* is_arg */ /** - * walker for connecting DAGs and counting. + * Allocate a new DAG entry. + */ +static dag_entry_t *new_dag_entry(dag_env_t *dag_env, ir_node *node) +{ + dag_entry_t *entry = OALLOC(&dag_env->obst, dag_entry_t); + + entry->num_nodes = 1; + entry->num_roots = 1; + entry->num_inner_nodes = 0; + entry->root = node; + entry->is_dead = 0; + entry->is_tree = 1; + entry->is_ext_ref = 0; + entry->next = dag_env->list_of_dags; + entry->link = NULL; + + ++dag_env->num_of_dags; + dag_env->list_of_dags = entry; + + set_irn_dag_entry(node, entry); + return entry; +} /* new_dag_entry */ + +/** + * Post-walker to detect DAG roots that are referenced form other blocks + */ +static void find_dag_roots(ir_node *node, void *env) +{ + dag_env_t *dag_env = (dag_env_t*)env; + int i, arity; + dag_entry_t *entry; + ir_node *block; + + if (is_Block(node)) + return; + + block = get_nodes_block(node); + + /* ignore start end end blocks */ + if (block == get_irg_start_block(current_ir_graph) || + block == get_irg_end_block(current_ir_graph)) { + return; + } /* if */ + + /* Phi nodes always references nodes from "other" block */ + if (is_Phi(node)) { + if (get_irn_mode(node) != mode_M) { + for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *prev = get_irn_n(node, i); + + if (is_Phi(prev)) + continue; + + if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) { + if (is_irn_constlike(prev)) + continue; + } /* if */ + + entry = get_irn_dag_entry(prev); + + if (! entry) { + /* found an unassigned node, a new root */ + entry = new_dag_entry(dag_env, node); + entry->is_ext_ref = 1; + } /* if */ + } /* for */ + } /* if */ + } else { + + for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *prev = get_irn_n(node, i); + ir_mode *mode = get_irn_mode(prev); + + if (mode == mode_X || mode == mode_M) + continue; + + if (is_Phi(prev)) + continue; + + if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) { + if (is_irn_constlike(prev)) + continue; + } /* if */ + + if (get_nodes_block(prev) != block) { + /* The predecessor is from another block. It forms + a root. */ + entry = get_irn_dag_entry(prev); + if (! entry) { + /* found an unassigned node, a new root */ + entry = new_dag_entry(dag_env, node); + entry->is_ext_ref = 1; + } /* if */ + } /* if */ + } /* for */ + } /* if */ +} /* find_dag_roots */ + +/** + * Pre-walker for connecting DAGs and counting. */ static void connect_dags(ir_node *node, void *env) { - dag_env_t *dag_env = env; + dag_env_t *dag_env = (dag_env_t*)env; int i, arity; ir_node *block; dag_entry_t *entry; @@ -114,6 +226,7 @@ static void connect_dags(ir_node *node, void *env) return; } /* if */ + /* ignore Phi nodes */ if (is_Phi(node)) return; @@ -122,37 +235,24 @@ static void connect_dags(ir_node *node, void *env) mode = get_irn_mode(node); if (mode == mode_X || mode == mode_M) { - /* do NOT count mode_X nodes */ + /* do NOT count mode_X and mode_M nodes */ return; } /* if */ - entry = get_irn_dag_entry(node); - - if (! entry) { - /* found a not assigned node, maybe a new root */ - entry = obstack_alloc(&dag_env->obst, sizeof(*entry)); + /* if this option is set, Loads are always leaves */ + if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && is_Load(node)) + return; - entry->num_nodes = 1; - entry->num_roots = 1; - entry->num_inner_nodes = 0; - entry->root = node; - entry->is_dead = 0; - entry->next = dag_env->list_of_dags; - entry->link = NULL; + if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && is_Call(node)) + return; - ++dag_env->num_of_dags; - dag_env->list_of_dags = entry; + entry = get_irn_dag_entry(node); - set_irn_dag_entry(node, entry); + if (! entry) { + /* found an unassigned node, maybe a new root */ + entry = new_dag_entry(dag_env, node); } /* if */ - /* if this option is set, Loads are allways leaves */ - if (dag_env->options & FIRMSTAT_LOAD_IS_LEAVE && get_irn_op(node) == op_Load) - return; - - if (dag_env->options & FIRMSTAT_CALL_IS_LEAVE && get_irn_op(node) == op_Call) - return; - /* put the predecessors into the same DAG as the current */ for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *prev = get_irn_n(node, i); @@ -170,7 +270,7 @@ static void connect_dags(ir_node *node, void *env) * wrong intersections */ if (dag_env->options & FIRMSTAT_COPY_CONSTANTS) { - if (get_irn_op(prev) == op_Const || get_irn_op(prev) == op_SymConst) { + if (is_irn_constlike(prev)) { ++entry->num_nodes; ++entry->num_inner_nodes; } /* if */ @@ -186,12 +286,17 @@ static void connect_dags(ir_node *node, void *env) ++entry->num_nodes; ++entry->num_inner_nodes; } else { - if (prev_entry != entry) { - - /* two DAGs intersect */ + if (prev_entry == entry) { + /* We found a node that is already assigned to this DAG. + This DAG is not a tree. */ + entry->is_tree = 0; + } else { + /* two DAGs intersect: copy the data to one of them + and kill the other */ entry->num_roots += prev_entry->num_roots; entry->num_nodes += prev_entry->num_nodes; entry->num_inner_nodes += prev_entry->num_inner_nodes; + entry->is_tree &= prev_entry->is_tree; --dag_env->num_of_dags; @@ -245,12 +350,16 @@ static int stat_dag_mark_hook(FILE *F, ir_node *n, ir_node *l) /** * count the DAG's size of a graph + * + * @param global the global entry + * @param graph the current graph entry */ void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph) { dag_env_t root_env; dag_entry_t *entry; unsigned id; + (void) global; /* do NOT check the const code irg */ if (graph->irg == get_const_code_irg()) @@ -264,10 +373,13 @@ void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph) root_env.list_of_dags = NULL; root_env.options = FIRMSTAT_COPY_CONSTANTS | FIRMSTAT_LOAD_IS_LEAVE | FIRMSTAT_CALL_IS_LEAVE; - /* count them */ + /* find the DAG roots that are referenced from other block */ + irg_walk_graph(graph->irg, NULL, find_dag_roots, &root_env); + + /* connect and count them */ irg_walk_graph(graph->irg, connect_dags, NULL, &root_env); - printf("Graph %p %s --- %d\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)), + printf("Graph %p %s --- %u\n", (void *)graph->irg, get_entity_name(get_irg_entity(graph->irg)), root_env.num_of_dags); for (id = 0, entry = root_env.list_of_dags; entry; entry = entry->next) { @@ -275,10 +387,11 @@ void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph) continue; entry->id = id++; - printf("number of roots %d number of nodes %d inner %d %ld\n", + printf("number of roots %u number of nodes %u inner %u tree %u %ld\n", entry->num_roots, entry->num_nodes, entry->num_inner_nodes, + entry->is_tree, get_irn_node_nr(entry->root)); } /* for */ @@ -286,7 +399,7 @@ void count_dags_in_graph(graph_entry_t *global, graph_entry_t *graph) /* dump for test */ mark_options = root_env.options; set_dump_node_vcgattr_hook(stat_dag_mark_hook); - dump_ir_block_graph(graph->irg, "-dag"); + dump_ir_graph(graph->irg, "-dag"); set_dump_node_vcgattr_hook(NULL); #endif