X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgwalk.c;h=e393fa38e8d0f1421c9ffa75ddb79ac3ce89a3db;hb=014643c20bee2345c928105e06c815d4f083753a;hp=3661b4115ae937093e3c9e29acc59709cbb594b1;hpb=c80c368f7ae4222880121ed11c78ecd4cc5dec18;p=libfirm diff --git a/ir/ir/irgwalk.c b/ir/ir/irgwalk.c index 3661b4115..e393fa38e 100644 --- a/ir/ir/irgwalk.c +++ b/ir/ir/irgwalk.c @@ -3,39 +3,46 @@ * File name: ir/ir/irgwalk.c * Purpose: * Author: Boris Boesler - * Modified by: Goetz Lindenmaier + * Modified by: Goetz Lindenmaier, Michael Beck * Created: * CVS-ID: $Id$ - * Copyright: (c) 1999-2003 Universität Karlsruhe + * Copyright: (c) 1999-20036Universität Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ /** -* traverse an ir graph -* - execute the pre function before recursion -* - execute the post function after recursion -*/ + * @file irgwalk.c + * + * traverse an ir graph + * - execute the pre function before recursion + * - execute the post function after recursion + */ #ifdef HAVE_CONFIG_H -# include +# include "config.h" #endif -#include +#ifdef HAVE_STDLIB_H +# include +#endif #include "irnode_t.h" #include "irgraph_t.h" /* visited flag */ #include "irprog.h" #include "irgwalk.h" #include "typewalk.h" -#include "firmstat.h" +#include "irhooks.h" #include "ircgcons.h" #include "eset.h" #include "array.h" -/* walk over an interprocedural graph (callgraph). Visits only graphs in irg_set. */ -static void irg_walk_cg(ir_node * node, int visited, eset * irg_set, +/** + * Walk over an interprocedural graph (callgraph). + * Visits only graphs in irg_set. + */ +static void irg_walk_cg(ir_node * node, unsigned long visited, eset * irg_set, irg_walk_func *pre, irg_walk_func *post, void * env) { int i; ir_graph * rem = current_ir_graph; @@ -105,13 +112,15 @@ static void irg_walk_cg(ir_node * node, int visited, eset * irg_set, } -/* Insert all ir_graphs in irg_set, that are (transitive) reachable. */ +/** + * Insert all ir_graphs in irg_set, that are (transitive) reachable. + */ static void collect_irgs(ir_node * node, eset * irg_set) { - if (get_irn_op(node) == op_Call) { + if (is_Call(node)) { int i; for (i = get_Call_n_callees(node) - 1; i >= 0; --i) { entity * ent = get_Call_callee(node, i); - ir_graph * irg = ent ? get_entity_irg(ent) : NULL; + ir_graph * irg = get_entity_irg(ent); if (irg && !eset_contains(irg_set, irg)) { eset_insert(irg_set, irg); irg_walk_graph(irg, (irg_walk_func *) collect_irgs, NULL, irg_set); @@ -122,102 +131,128 @@ static void collect_irgs(ir_node * node, eset * irg_set) { /** * specialized version of irg_walk_2, called if only pre callback exists + * + * @return number of visited nodes */ -static void +static unsigned irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void * env) { int i; - set_irn_visited(node, current_ir_graph->visited); + unsigned cnt = 1; + ir_graph *irg = current_ir_graph; + + set_irn_visited(node, irg->visited); pre(node, env); if (node->op != op_Block) { ir_node *pred = get_irn_n(node, -1); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_pre(pred, pre, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_pre(pred, pre, env); } for (i = get_irn_arity(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(node, i); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_pre(pred, pre, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_pre(pred, pre, env); } + return cnt; } /** * specialized version of irg_walk_2, called if only post callback exists + * + * @return number of visited nodes */ -static void +static unsigned irg_walk_2_post(ir_node *node, irg_walk_func *post, void * env) { int i; - set_irn_visited(node, current_ir_graph->visited); + unsigned cnt = 1; + ir_graph *irg = current_ir_graph; + + set_irn_visited(node, irg->visited); if (node->op != op_Block) { ir_node *pred = get_irn_n(node, -1); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_post(pred, post, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_post(pred, post, env); } for (i = get_irn_arity(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(node, i); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_post(pred, post, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_post(pred, post, env); } post(node, env); + + return cnt; } /** * specialized version of irg_walk_2, called if pre and post callbacks exist + * + * @return number of visited nodes */ -static void +static unsigned irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) { int i; - set_irn_visited(node, current_ir_graph->visited); + unsigned cnt = 1; + ir_graph *irg = current_ir_graph; + + set_irn_visited(node, irg->visited); pre(node, env); if (node->op != op_Block) { ir_node *pred = get_irn_n(node, -1); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_both(pred, pre, post, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_both(pred, pre, post, env); } for (i = get_irn_arity(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(node, i); - if (pred->visited < current_ir_graph->visited) - irg_walk_2_both(pred, pre, post, env); + if (pred->visited < irg->visited) + cnt += irg_walk_2_both(pred, pre, post, env); } post(node, env); + + return cnt; } /** * Intraprozedural graph walker. + * + * @return number of visited nodes */ -static void +static unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) { if (node->visited < current_ir_graph->visited) { - if (!post) irg_walk_2_pre (node, pre, env); - else if (!pre) irg_walk_2_post(node, post, env); - else irg_walk_2_both(node, pre, post, env); + if (!post) return irg_walk_2_pre (node, pre, env); + else if (!pre) return irg_walk_2_post(node, post, env); + else return irg_walk_2_both(node, pre, post, env); } + return 0; } +/* a counter */ +static unsigned nodes_touched = 0; + /* * generic graph walker */ void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { - assert(node && node->kind==k_ir_node); + assert(is_ir_node(node)); if (get_interprocedural_view()) { eset * irg_set = eset_create(); - int visited; + unsigned long visited; ir_graph * irg; assert(get_irp_ip_view_state() == ip_view_valid); - set_interprocedural_view(false); + set_interprocedural_view(0); eset_insert(irg_set, current_ir_graph); irg_walk(node, (irg_walk_func *) collect_irgs, NULL, irg_set); - set_interprocedural_view(true); + set_interprocedural_view(1); visited = get_max_irg_visited() + 1; for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) { set_irg_visited(irg, visited); @@ -226,18 +261,21 @@ void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) eset_destroy(irg_set); } else { inc_irg_visited(current_ir_graph); - irg_walk_2(node, pre, post, env); + nodes_touched = irg_walk_2(node, pre, post, env); } return; } - +/* + * walk over a graph + */ void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { ir_graph * rem = current_ir_graph; - stat_irg_walk(irg, (void *)pre, (void *)post); + hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post); current_ir_graph = irg; irg_walk(get_irg_end(irg), pre, post, env); + irg->estimated_node_count = nodes_touched; current_ir_graph = rem; } @@ -260,8 +298,10 @@ void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) { /***************************************************************************/ -/* Returns current_ir_graph and sets it to the irg of predecessor index - of node n. */ +/** + * Returns current_ir_graph and sets it to the irg of predecessor index + * of node n. + */ static INLINE ir_graph * switch_irg (ir_node *n, int index) { ir_graph *old_current = current_ir_graph; @@ -314,7 +354,7 @@ void cg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) { ir_graph *rem = current_ir_graph; int rem_view = get_interprocedural_view(); - set_interprocedural_view(true); + set_interprocedural_view(1); inc_max_irg_visited(); /* Fix all irg_visited flags */ @@ -388,8 +428,8 @@ static void irg_block_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *p { int i; - if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) { - set_Block_block_visited(node, get_irg_block_visited(current_ir_graph)); + if (Block_not_block_visited(node)) { + mark_Block_block_visited(node); if(pre) pre(node, env); @@ -419,14 +459,14 @@ void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void ir_node *block, *pred; int i; - stat_irg_block_walk(current_ir_graph, node, (void *)pre, (void *)post); + hook_irg_block_walk(current_ir_graph, node, (generic_func *)pre, (generic_func *)post); assert(node); assert(!get_interprocedural_view()); /* interprocedural_view not implemented, because it * interleaves with irg_walk */ inc_irg_block_visited(current_ir_graph); if (is_no_Block(node)) block = get_nodes_block(node); else block = node; - assert(get_irn_opcode(block) == iro_Block); + assert(get_irn_op(block) == op_Block); irg_block_walk_2(block, pre, post, env); /* keepalive: the endless loops ... */ @@ -442,9 +482,9 @@ void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void for (i = 0; i < arity; i++) { pred = get_irn_n(node, i); if (get_irn_op(pred) == op_Phi) { - ir_node *block = get_nodes_block(pred); + ir_node *block = get_nodes_block(pred); - if (! is_Bad(block)) + if (! is_Bad(block)) irg_block_walk_2(block, pre, post, env); } } @@ -453,7 +493,9 @@ void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void return; } - +/* + * walk over a graph block wise + */ void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { ir_graph * rem = current_ir_graph; @@ -462,6 +504,22 @@ void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre, current_ir_graph = rem; } +/* + * Additionally walk over all anchors. Do NOT increase the visit flag. + */ +void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { + int i; + ir_graph * rem = current_ir_graph; + current_ir_graph = irg; + + for (i = 0; i < anchor_max; ++i) { + ir_node *anchor = irg->anchors[i]; + + irg_walk_2(anchor, pre, post, env); + } + current_ir_graph = rem; +} + /********************************************************************/ typedef struct walk_env { @@ -470,7 +528,9 @@ typedef struct walk_env { void *env; } walk_env; -/* Walk to all constant expressions in this entity. */ +/** + * Walk to all constant expressions in this entity. + */ static void walk_entity(entity *ent, void *env) { walk_env *my_env = (walk_env *)env; @@ -480,9 +540,9 @@ static void walk_entity(entity *ent, void *env) irg_walk(get_atomic_ent_value(ent), my_env->pre, my_env->post, my_env->env); } else { - int i, n = get_compound_ent_n_values(ent); + int i, n_vals = get_compound_ent_n_values(ent); - for (i = 0; i < n; i++) + for (i = 0; i < n_vals; i++) irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env); } } @@ -510,14 +570,13 @@ void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env) { /* Walk constant array bounds. */ for (i = 0; i < get_irp_n_types(); i++) { - type *tp = get_irp_type(i); - if (is_array_type(tp)) { + ir_type *tp = get_irp_type(i); + if (is_Array_type(tp)) { for (j = 0; j < get_array_n_dimensions(tp); j++) { - ir_node *n; - n = get_array_lower_bound(tp, j); - if (n) irg_walk(n, pre, post, env); - n = get_array_upper_bound(tp, j); - if (n) irg_walk(n, pre, post, env); + ir_node *n = get_array_lower_bound(tp, j); + if (n) irg_walk(n, pre, post, env); + n = get_array_upper_bound(tp, j); + if (n) irg_walk(n, pre, post, env); } } }