X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firgwalk_blk.c;h=86c876e31df1ac817e39ffa4afadd4bfb6dc9a37;hb=5f05c97be1452a4fd611648879c1544a8af611c9;hp=8cb178d90d0d707c5aa33e24ed95334b282497c5;hpb=7f90a1b1412f032e0cce1d6f13b25ea9dd2dba19;p=libfirm diff --git a/ir/ir/irgwalk_blk.c b/ir/ir/irgwalk_blk.c index 8cb178d90..86c876e31 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-2007 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" @@ -16,25 +30,35 @@ #include "irnode_t.h" #include "irgraph_t.h" /* visited flag */ #include "irgwalk.h" -#include "pdeq.h" #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 */ - pdeq *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; /** * An entry for a block in the blk_map */ typedef struct _block_entry_t { - ir_node *block; /**< the block */ - pdeq *list; /**< the instruction list */ + ir_node *block; /**< the block */ + ir_node **phi_list; /**< the list of Phi instruction */ + ir_node **df_list; /**< the list of data flow instruction */ + ir_node **cf_list; /**< the list of control flow instructions */ + ir_node **entry_list; /**< list of all block entries */ } block_entry_t; /** @@ -47,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 */ @@ -64,66 +80,19 @@ 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; elem = obstack_alloc(&ctx->obst, sizeof(*elem)); - elem->block = block; - elem->list = new_pdeq(); + elem->block = block; + elem->phi_list = NEW_ARR_F(ir_node *, 0); + elem->df_list = NEW_ARR_F(ir_node *, 0); + 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)); -} - -/** - * Post-walker: collect nodes and put them on the right list - */ -static void collect_nodes(ir_node *node, void *env) -{ - blk_collect_data_t *ctx = env; - ir_node *block; - block_entry_t *entry; - - if (is_Block(node)) { - /* it's a block, put it into the block list */ - pdeq_putl(ctx->blk_list, node); - return; - } - - block = get_nodes_block(node); - entry = block_find_entry(block, ctx); - - if (get_irn_mode(node) == mode_X) { - /* - * put all mode_X nodes to the start, later we can - * move them to the end. - */ - pdeq_putr(entry->list, node); - } - else - pdeq_putl(entry->list, node); -} - -/** - * move mode_X nodes to the end of the schedule - */ -static void move_X_nodes_to_end(pdeq *list) -{ - int j; - - /* move mode_X nodes to the end */ - for (j = pdeq_len(list); j > 0; --j) { - ir_node *node = pdeq_getr(list); - - if (get_irn_mode(node) == mode_X) { - pdeq_putl(list, node); - } - else { - pdeq_putr(list, node); - break; - } - } + return pset_insert(ctx->blk_map, elem, HASH_PTR(block)); } /** @@ -133,18 +102,31 @@ static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env { int i, j; - for (i = pdeq_len(blks->blk_list); i > 0; --i) { - ir_node *block = pdeq_getl(blks->blk_list); + for (i = ARR_LEN(blks->blk_list) - 1; i >= 0; --i) { + ir_node *block = blks->blk_list[i]; block_entry_t *entry = block_find_entry(block, blks); - /* move mode_X nodes to the end */ - move_X_nodes_to_end(entry->list); + for (j = ARR_LEN(entry->cf_list) - 1; j >= 0; --j) { + ir_node *node = entry->cf_list[j]; + pre(node, env); + } - for (j = pdeq_len(entry->list); j > 0; --j) { - ir_node *node = pdeq_getl(entry->list); + for (j = ARR_LEN(entry->df_list) - 1; j >= 0; --j) { + ir_node *node = entry->df_list[j]; pre(node, env); } + + for (j = ARR_LEN(entry->phi_list) - 1; j >= 0; --j) { + ir_node *node = entry->phi_list[j]; + pre(node, env); + } + pre(block, env); + + DEL_ARR_F(entry->entry_list); + DEL_ARR_F(entry->phi_list); + DEL_ARR_F(entry->df_list); + DEL_ARR_F(entry->cf_list); } } @@ -155,19 +137,31 @@ static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *e { int i, j; - for (i = pdeq_len(blks->blk_list); i > 0; --i) { - ir_node *block = pdeq_getr(blks->blk_list); + for (i = 0; i < ARR_LEN(blks->blk_list); ++i) { + ir_node *block = blks->blk_list[i]; block_entry_t *entry = block_find_entry(block, blks); post(block, env); - /* move mode_X nodes to the end */ - move_X_nodes_to_end(entry->list); + for (j = 0; j < ARR_LEN(entry->phi_list); ++j) { + ir_node *node = entry->phi_list[j]; + post(node, env); + } - for (j = pdeq_len(entry->list); j > 0; --j) { - ir_node *node = pdeq_getr(entry->list); + for (j = 0; j < ARR_LEN(entry->df_list); ++j) { + ir_node *node = entry->df_list[j]; post(node, env); } + + for (j = 0; j < ARR_LEN(entry->cf_list); ++j) { + ir_node *node = entry->cf_list[j]; + post(node, env); + } + + DEL_ARR_F(entry->entry_list); + DEL_ARR_F(entry->phi_list); + DEL_ARR_F(entry->df_list); + DEL_ARR_F(entry->cf_list); } } @@ -178,37 +172,30 @@ static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk { int i, j; - /* pre walk, rotate all lists */ - for (i = pdeq_len(blks->blk_list); i > 0; --i) { - ir_node *block = pdeq_getl(blks->blk_list); + for (i = ARR_LEN(blks->blk_list) - 1; i >= 0; --i) { + ir_node *block = blks->blk_list[i]; block_entry_t *entry = block_find_entry(block, blks); - pdeq_putr(blks->blk_list, block); - - /* move mode_X nodes to the end */ - move_X_nodes_to_end(entry->list); + for (j = ARR_LEN(entry->cf_list) - 1; j >= 0; --j) { + ir_node *node = entry->cf_list[j]; + pre(node, env); + } - for (j = pdeq_len(entry->list); j > 0; --j) { - ir_node *node = pdeq_getl(entry->list); + for (j = ARR_LEN(entry->df_list) - 1; j >= 0; --j) { + ir_node *node = entry->df_list[j]; + pre(node, env); + } - pdeq_putr(entry->list, node); + for (j = ARR_LEN(entry->phi_list) - 1; j >= 0; --j) { + ir_node *node = entry->phi_list[j]; pre(node, env); } + pre(block, env); } /* second step */ - for (i = pdeq_len(blks->blk_list); i > 0; --i) { - ir_node *block = pdeq_getr(blks->blk_list); - block_entry_t *entry = block_find_entry(block, blks); - - post(block, env); - - for (j = pdeq_len(entry->list); j > 0; --j) { - ir_node *node = pdeq_getr(entry->list); - post(node, env); - } - } + traverse_post(blks, post, env); } @@ -222,49 +209,211 @@ static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func else traverse_both(blks, pre, post, env); } + +/** + * walks over the graph and collects all blocks and all block entries + */ +static void collect_walk(ir_node *node, blk_collect_data_t *env) +{ + int i, is_phi; + block_entry_t *entry; + ir_node *block; + + mark_irn_visited(node); + + if (node->op == op_Block) { + /* predecessors of a block are control flow nodes */ + 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 (irn_not_visited(pred)) { + collect_walk(pred, env); + + /* control flow predecessors are always block inputs */ + entry = block_find_entry(blk, env); + ARR_APP1(ir_node *, entry->entry_list, pred); + } + } + + /* it's a block, put it into the block list */ + if (node == get_irg_end_block(current_ir_graph)) { + /* Put the end block always last. If we don't do it here, + * it might be placed elsewhere if the graph contains + * endless loops. + */ + } + else { + ARR_APP1(ir_node *, env->blk_list, node); + } + } + else { + block = get_nodes_block(node); + + if (irn_not_visited(block)) + collect_walk(block, env); + + is_phi = is_Phi(node); + for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) { + ir_node *pred = _get_walk_irn_n(env, node, i); + + if (irn_not_visited(pred)) { + collect_walk(pred, env); + + /* 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); + } + } + } + } + } +} + +/** + * walks over the nodes of a block + * and collects them into the right list + */ +static void collect_blks_lists(ir_node *node, ir_node *block, + block_entry_t *entry, blk_collect_data_t *env) +{ + int i; + + mark_irn_visited(node); + + /* + * Do not descent into Phi predecessors, these are always + * outside the current block because Phi edges are always + * "outside". + */ + if (! is_Phi(node)) { + 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 (irn_not_visited(pred)) { + if (block != blk) + continue; + collect_blks_lists(pred, block, entry, env); + } + } + } + } + else { + ARR_APP1(ir_node *, entry->phi_list, node); + return; + } + + if (get_irn_mode(node) == mode_X) { + ARR_APP1(ir_node *, entry->cf_list, node); + } + else { + ARR_APP1(ir_node *, entry->df_list, node); + } +} + +/** + * walk over the graph and collect all lists + */ +static void collect_lists(blk_collect_data_t *env) +{ + int i, j; + ir_node *block, *node; + block_entry_t *entry; + + inc_irg_visited(current_ir_graph); + + for (i = ARR_LEN(env->blk_list) - 1; i >= 0; --i) { + block = env->blk_list[i]; + entry = block_find_entry(block, env); + + for (j = ARR_LEN(entry->entry_list) - 1; j >= 0; --j) { + node = entry->entry_list[j]; + + /* a entry might already be visited due to Phi loops */ + if (node->visited < current_ir_graph->visited) + collect_blks_lists(node, block, entry, env); + } + } +} + /** * Intraprozedural graph walker over blocks. */ static void -do_irg_walk_blk(ir_node *node, 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_pdeq(); + blks.blk_map = new_pset(addr_cmp, 1); + blks.blk_list = NEW_ARR_F(ir_node *, 0); + blks.follow_deps = follow_deps != 0; - if (node->visited < current_ir_graph->visited) { - /* first step: traverse the graph and fill the lists */ - irg_walk(node, NULL, collect_nodes, &blks); + /* first step: traverse the graph and fill the lists */ + set_using_visited(irg); + inc_irg_visited(irg); + collect_walk(end_node, &blks); - /* second step: traverse the list */ - traverse(&blks, pre, post, env); - } + /* add the end block */ + ARR_APP1(ir_node *, blks.blk_list, end_blk); + + /* and the end node */ + entry = block_find_entry(end_blk, &blks); + ARR_APP1(ir_node *, entry->entry_list, end_node); + + collect_lists(&blks); + + /* second step: traverse the list */ + traverse(&blks, pre, post, env); - del_pdeq(blks.blk_list); + DEL_ARR_F(blks.blk_list); del_pset(blks.blk_map); obstack_free(&blks.obst, NULL); +#ifdef INTERPROCEDURAL_VIEW set_interprocedural_view(old_view); +#endif + clear_using_visited(irg); } -void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) +void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) { - inc_irg_visited(current_ir_graph); - do_irg_walk_blk(node, pre, post, 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, 0); + current_ir_graph = rem; } -void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) + +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, (void *)pre, (void *)post); + hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post); current_ir_graph = irg; - irg_walk_blkwise(get_irg_end(irg), pre, post, env); + do_irg_walk_blk(irg, pre, post, env, 1); current_ir_graph = rem; }