X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgwalk.c;h=10fb15914b7a76ca05260f53fc29eb0b73a7ca9d;hb=a158f864beaee2de7ba4e0610a3a9960a0be5ed4;hp=440dc613071055351a252fabb7d230885c5cc3d8;hpb=a4219fc055a51f1adfff90c85838f3831028a7f3;p=libfirm diff --git a/ir/ir/irgwalk.c b/ir/ir/irgwalk.c index 440dc6130..10fb15914 100644 --- a/ir/ir/irgwalk.c +++ b/ir/ir/irgwalk.c @@ -1,27 +1,12 @@ /* - * Copyright (C) 1995-2011 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. + * Copyright (C) 2012 University of Karlsruhe. */ /** * @file * @brief Functions for traversing ir graphs * @author Boris Boesler, Goetz Lindenmaier, Michael Beck - * @version $Id$ * @brief * traverse an ir graph * - execute the pre function before recursion @@ -37,6 +22,7 @@ #include "irgwalk.h" #include "irhooks.h" #include "entity_t.h" +#include "ircons.h" #include "error.h" #include "pset_new.h" @@ -44,117 +30,95 @@ /** * specialized version of irg_walk_2, called if only pre callback exists - * - * @return number of visited nodes */ -static unsigned irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env) +static void irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); pre(node, env); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_2_pre(pred, pre, env); + 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 < irg->visited) - cnt += irg_walk_2_pre(pred, pre, env); + 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 unsigned irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env) +static void irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_2_post(pred, post, env); + 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 < irg->visited) - cnt += irg_walk_2_post(pred, post, env); + 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 unsigned irg_walk_2_both(ir_node *node, irg_walk_func *pre, +static void irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); pre(node, env); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_2_both(pred, pre, post, env); + 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 < irg->visited) - cnt += irg_walk_2_both(pred, pre, post, env); + irg_walk_2_both(pred, pre, post, env); } post(node, env); - - return cnt; } -/** - * Intraprozedural graph walker. - * - * @return number of visited nodes - */ -unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, - void *env) +void irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, + void *env) { if (irn_visited(node)) - return 0; + return; - 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); + 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); } -/* a counter */ -static unsigned nodes_touched = 0; - void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { assert(is_ir_node(node)); - nodes_touched = irg_walk_2(node, pre, post, env); + irg_walk_2(node, pre, post, env); } void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, @@ -171,9 +135,6 @@ void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, current_ir_graph = rem; } -/* - * 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; @@ -181,13 +142,9 @@ void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void 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; } -/* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog. - Sets current_ir_graph properly for each walk. Conserves current - current_ir_graph. */ void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) { size_t i, n; @@ -199,127 +156,103 @@ void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) } } -/***************************************************************************/ - /** * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists - * - * @return number of visited nodes */ -static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env) +static void irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); pre(node, env); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_pre(pred, pre, env); + irg_walk_in_or_dep_2_pre(pred, pre, env); } for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_in_or_dep(node, i); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_pre(pred, pre, env); + irg_walk_in_or_dep_2_pre(pred, pre, env); } - return cnt; } /** * specialized version of irg_walk_in_or_dep_2, called if only post callback exists - * - * @return number of visited nodes */ -static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env) +static void irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_post(pred, post, env); + irg_walk_in_or_dep_2_post(pred, post, env); } for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_in_or_dep(node, i); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_post(pred, post, env); + irg_walk_in_or_dep_2_post(pred, post, env); } post(node, env); - - return cnt; } /** * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist - * - * @return number of visited nodes */ -static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) +static void irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { int i; - unsigned cnt = 1; ir_graph *irg = get_irn_irg(node); set_irn_visited(node, irg->visited); pre(node, env); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env); + irg_walk_in_or_dep_2_both(pred, pre, post, env); } for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) { ir_node *pred = get_irn_in_or_dep(node, i); if (pred->visited < irg->visited) - cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env); + irg_walk_in_or_dep_2_both(pred, pre, post, env); } post(node, env); - - return cnt; } /** * Intraprozedural graph walker. Follows dependency edges as well. - * - * @return number of visited nodes */ -static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) +static void irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { if (irn_visited(node)) - return 0; + return; - if (! post) return irg_walk_in_or_dep_2_pre (node, pre, env); - else if (! pre) return irg_walk_in_or_dep_2_post(node, post, env); - else return irg_walk_in_or_dep_2_both(node, pre, post, env); + if (! post) irg_walk_in_or_dep_2_pre (node, pre, env); + else if (! pre) irg_walk_in_or_dep_2_post(node, post, env); + else irg_walk_in_or_dep_2_both(node, pre, post, env); } -/* - * Generic graph walker. Follows dependency edges as well. - */ void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) { assert(is_ir_node(node)); ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); inc_irg_visited(current_ir_graph); - nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env); + irg_walk_in_or_dep_2(node, pre, post, env); ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); } -/* - * Walk over a graph. Follow all edges (including dependencies) - */ void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { ir_graph * rem = current_ir_graph; @@ -327,17 +260,13 @@ void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func * hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post); current_ir_graph = irg; irg_walk_in_or_dep(get_irg_end(irg), pre, post, env); - irg->estimated_node_count = nodes_touched; current_ir_graph = rem; } -/***************************************************************************/ - /* Walks back from n until it finds a real cf op. */ static ir_node *get_cf_op(ir_node *n) { while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) { - n = skip_Id(n); n = skip_Tuple(n); n = skip_Proj(n); } @@ -372,38 +301,26 @@ static void irg_block_walk_2(ir_node *node, irg_walk_func *pre, post(node, env); } - -/* walks only over Block nodes in the graph. Has its own visited - flag, so that it can be interleaved with the other walker. */ -void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) +void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, + void *env) { - ir_graph *irg = get_irn_irg(node); - ir_node *block, *pred; - int i; + ir_graph *irg = get_irn_irg(node); + ir_node *block = is_Block(node) ? node : get_nodes_block(node); hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post); - assert(node); ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED); inc_irg_block_visited(irg); - block = is_Block(node) ? node : get_nodes_block(node); - assert(is_Block(block)); irg_block_walk_2(block, pre, post, env); - /* keepalive: the endless loops ... */ + /* Some blocks might be only reachable through keep-alive edges */ if (is_End(node)) { int arity = get_irn_arity(node); + int i; for (i = 0; i < arity; i++) { - pred = get_irn_n(node, i); - if (!is_Block(pred)) { - pred = get_nodes_block(pred); - if (!is_Block(pred)) { - /* if rare cases a kept node might have a bad block input */ - continue; - } - } - /* Sometimes the blocks died, but are still reachable through kept nodes. - * Make sure the algorithms that try to remove these reach them. */ + ir_node *pred = get_irn_n(node, i); + if (!is_Block(pred)) + continue; irg_block_walk_2(pred, pre, post, env); } } @@ -411,9 +328,6 @@ void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED); } -/* - * walk over a graph block wise - */ void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { @@ -423,22 +337,19 @@ 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) { ir_graph * rem = current_ir_graph; current_ir_graph = irg; + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); irg_walk_2(irg->anchor, pre, post, env); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); current_ir_graph = rem; } -/********************************************************************/ - typedef struct walk_env { irg_walk_func *pre; irg_walk_func *post; @@ -477,15 +388,9 @@ static void walk_entity(ir_entity *ent, void *env) if (ent->initializer != NULL) { walk_initializer(ent->initializer, my_env); - } else if (entity_has_compound_ent_values(ent)) { - size_t i, n_vals = get_compound_ent_n_values(ent); - - for (i = 0; i < n_vals; i++) - irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env); } } -/* Walks over all code in const_code_irg. */ void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env) { walk_env my_env;