X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgwalk_blk.c;h=c5b022f0bb21f62dcf5dedfe3b182b3614073dfd;hb=bb5c6d5ce2e35c4074900017f8c8e1a4935054d0;hp=0eba7000d2f8073be5f4891c222a19766d193f23;hpb=59319b0a4305b2e53699f76401d25e0ac55fe3da;p=libfirm diff --git a/ir/ir/irgwalk_blk.c b/ir/ir/irgwalk_blk.c index 0eba7000d..c5b022f0b 100644 --- a/ir/ir/irgwalk_blk.c +++ b/ir/ir/irgwalk_blk.c @@ -1,13 +1,27 @@ /* - * Project: libFIRM - * File name: ir/ir/irgwalk_blk.c - * Purpose: - * Author: Michael Beck - * Modified by: - * Created: - * CVS-ID: $Id$ - * Copyright: (c) 1999-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. + */ + +/** + * @file + * @brief Blockwise walker implementation + * @author Michael Beck + * @version $Id$ */ #ifdef HAVE_CONFIG_H # include "config.h" @@ -19,14 +33,21 @@ #include "pset.h" #include "irhooks.h" #include "array.h" +#include "hashptr.h" + +#define _get_walk_arity(env, node) \ + ((env)->follow_deps ? get_irn_ins_or_deps((node)) : get_irn_arity((node))) +#define _get_walk_irn_n(env, node, pos) \ + ((env)->follow_deps ? get_irn_in_or_dep((node), (pos)) : get_irn_n((node), (pos))) /** * Metadata for block walker */ typedef struct _blk_collect_data_t { - struct obstack obst; /**< obstack to allocate objects on */ - pset *blk_map; /**< Hash map: Block -> List */ - ir_node **blk_list; /**< the Block list */ + struct obstack obst; /**< obstack to allocate objects on */ + pset *blk_map; /**< Hash map: Block -> List */ + ir_node **blk_list; /**< the Block list */ + unsigned follow_deps : 1; /**< follow dependency edges */ } blk_collect_data_t; /** @@ -50,14 +71,6 @@ static int addr_cmp(const void *elt, const void *key) { return e1->block != e2->block; } -/** - * calculates a hash value for an block address - * Addresses are typically aligned at 32bit, so we ignore the lowest bits - */ -static INLINE unsigned block_hash(const ir_node *node) { - return (unsigned)node >> 3; -} - /** * Returns the associates block_entry_t for an block */ @@ -67,7 +80,7 @@ static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx) block_entry_t *elem; key.block = block; - elem = pset_find(ctx->blk_map, &key, block_hash(block)); + elem = pset_find(ctx->blk_map, &key, HASH_PTR(block)); if (elem) return elem; @@ -79,7 +92,7 @@ static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx) elem->cf_list = NEW_ARR_F(ir_node *, 0); elem->entry_list = NEW_ARR_F(ir_node *, 0); - return pset_insert(ctx->blk_map, elem, block_hash(block)); + return pset_insert(ctx->blk_map, elem, HASH_PTR(block)); } /** @@ -206,15 +219,15 @@ static void collect_walk(ir_node *node, blk_collect_data_t *env) block_entry_t *entry; ir_node *block; - set_irn_visited(node, current_ir_graph->visited); + mark_irn_visited(node); if (node->op == op_Block) { /* predecessors of a block are control flow nodes */ - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); + for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) { + ir_node *pred = _get_walk_irn_n(env, node, i); ir_node *blk = get_nodes_block(pred); - if (pred->visited < current_ir_graph->visited) { + if (!irn_visited(pred)) { collect_walk(pred, env); /* control flow predecessors are always block inputs */ @@ -237,24 +250,28 @@ static void collect_walk(ir_node *node, blk_collect_data_t *env) else { block = get_nodes_block(node); - if (block->visited < current_ir_graph->visited) + if (!irn_visited(block)) collect_walk(block, env); is_phi = is_Phi(node); - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); - ir_node *blk = get_nodes_block(pred); + for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) { + ir_node *pred = _get_walk_irn_n(env, node, i); - if (pred->visited < current_ir_graph->visited) { + if (!irn_visited(pred)) { collect_walk(pred, env); - /* - * Note that Phi predecessors are always block entries - * because Phi edges are always "outside" a block - */ - if (block != blk || is_phi) { - entry = block_find_entry(blk, env); - ARR_APP1(ir_node *, entry->entry_list, pred); + /* BEWARE: predecessors of End nodes might be blocks */ + if (is_no_Block(pred)) { + ir_node *blk = get_nodes_block(pred); + + /* + * Note that Phi predecessors are always block entries + * because Phi edges are always "outside" a block + */ + if (block != blk || is_phi) { + entry = block_find_entry(blk, env); + ARR_APP1(ir_node *, entry->entry_list, pred); + } } } } @@ -270,7 +287,7 @@ static void collect_blks_lists(ir_node *node, ir_node *block, { int i; - set_irn_visited(node, current_ir_graph->visited); + mark_irn_visited(node); /* * Do not descent into Phi predecessors, these are always @@ -278,14 +295,18 @@ static void collect_blks_lists(ir_node *node, ir_node *block, * "outside". */ if (! is_Phi(node)) { - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); - ir_node *blk = get_nodes_block(pred); + for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) { + ir_node *pred = _get_walk_irn_n(env, node, i); + + /* BEWARE: predecessors of End nodes might be blocks */ + if (is_no_Block(pred)) { + ir_node *blk = get_nodes_block(pred); - if (pred->visited < current_ir_graph->visited) { - if (block != blk) - continue; - collect_blks_lists(pred, block, entry, env); + if (!irn_visited(pred)) { + if (block != blk) + continue; + collect_blks_lists(pred, block, entry, env); + } } } } @@ -331,22 +352,26 @@ static void collect_lists(blk_collect_data_t *env) * Intraprozedural graph walker over blocks. */ static void -do_irg_walk_blk(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) +do_irg_walk_blk(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env, unsigned follow_deps) { ir_node *end_node = get_irg_end(irg); ir_node *end_blk = get_irg_end_block(irg); blk_collect_data_t blks; - int old_view = get_interprocedural_view(); block_entry_t *entry; +#ifdef INTERPROCEDURAL_VIEW /* switch off interprocedural view */ - set_interprocedural_view(false); + int old_view = get_interprocedural_view(); + set_interprocedural_view(0); +#endif obstack_init(&blks.obst); - blks.blk_map = new_pset(addr_cmp, 1); - blks.blk_list = NEW_ARR_F(ir_node *, 0); + blks.blk_map = new_pset(addr_cmp, 1); + blks.blk_list = NEW_ARR_F(ir_node *, 0); + blks.follow_deps = follow_deps != 0; /* first step: traverse the graph and fill the lists */ + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); collect_walk(end_node, &blks); @@ -366,15 +391,29 @@ do_irg_walk_blk(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *en del_pset(blks.blk_map); obstack_free(&blks.obst, NULL); +#ifdef INTERPROCEDURAL_VIEW set_interprocedural_view(old_view); +#endif + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { ir_graph * rem = current_ir_graph; - hook_irg_walk_blkwise(irg, (void *)pre, (void *)post); + hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post); + current_ir_graph = irg; + do_irg_walk_blk(irg, pre, post, env, 0); + current_ir_graph = rem; +} + + +void irg_walk_in_or_dep_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) +{ + ir_graph * rem = current_ir_graph; + + hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post); current_ir_graph = irg; - do_irg_walk_blk(irg, pre, post, env); + do_irg_walk_blk(irg, pre, post, env, 1); current_ir_graph = rem; }