From 6deb4fd20b13c44e5cbef35029d69508c56fb89c Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Tue, 20 Jul 2004 09:20:09 +0000 Subject: [PATCH] irgwalk_blk.c added [r3516] --- ir/ir/Makefile.in | 2 +- ir/ir/irgwalk_blk.c | 224 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 225 insertions(+), 1 deletion(-) create mode 100644 ir/ir/irgwalk_blk.c diff --git a/ir/ir/Makefile.in b/ir/ir/Makefile.in index f059d02f7..68c591602 100644 --- a/ir/ir/Makefile.in +++ b/ir/ir/Makefile.in @@ -23,7 +23,7 @@ SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in \ ircons.c ircons_t.h irgmod.c irgraph_t.h irnode.c iropt.c irvrfy.c \ - irgwalk.c irdump.c irgopt.c irnode_t.h iropt_t.h \ + irgwalk.c irgwalk_blk.c irdump.c irgopt.c irnode_t.h iropt_t.h \ irmode.c irop.c irprog.c irflag.c irflag_t.h irgraph.c \ irmode_t.h irop_t.h irprog_t.h ircgcons.c ircgopt.c diff --git a/ir/ir/irgwalk_blk.c b/ir/ir/irgwalk_blk.c new file mode 100644 index 000000000..3f9293044 --- /dev/null +++ b/ir/ir/irgwalk_blk.c @@ -0,0 +1,224 @@ +/* + * 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. + */ +#ifdef HAVE_CONFIG_H +# include +#endif + +#include "irnode_t.h" +#include "irgraph_t.h" /* visited flag */ +#include "irgwalk.h" +#include "pdeq.h" +#include "pset.h" +#include "firmstat.h" + +/** + * 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 */ +} 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 */ +} block_entry_t; + +/** + * compare two block_entries + */ +static int addr_cmp(const void *elt, const void *key) { + const block_entry_t *e1 = elt; + const block_entry_t *e2 = 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 + */ +static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx) +{ + block_entry_t key; + block_entry_t *elem; + + key.block = block; + elem = pset_find(ctx->blk_map, &key, block_hash(block)); + if (elem) + return elem; + + elem = obstack_alloc(&ctx->obst, sizeof(*elem)); + + elem->block = block; + elem->list = new_pdeq(); + + return pset_insert(ctx->blk_map, elem, block_hash(block)); +} + +/** + * collect nodes + */ +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_putr(ctx->blk_list, node); + return; + } + + block = get_nodes_block(node); + entry = block_find_entry(block, ctx); + + if (get_irn_mode(node) == mode_X) + pdeq_putl(entry->list, node); + else + pdeq_putr(entry->list, node); +} + +/** + * traverse the pre order only, from End to Start + */ +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); + block_entry_t *entry = block_find_entry(block, blks); + + for (j = pdeq_len(entry->list); j > 0; --j) { + ir_node *node = pdeq_getl(entry->list); + pre(node, env); + } + pre(block, env); + } +} + +/** + * traverse the post order only, from Start to End + */ +static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env) +{ + int i, j; + + 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 both + */ +static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env) +{ + 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); + block_entry_t *entry = block_find_entry(block, blks); + + pdeq_putr(blks->blk_list, block); + + for (j = pdeq_len(entry->list); j > 0; --j) { + ir_node *node = pdeq_getl(entry->list); + + pdeq_putr(entry->list, node); + pre(node, env); + } + pre(block, env); + } + + /* second step */ + traverse_post(blks, post, env); +} + + +/** + * Do the traversal + */ +static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env) +{ + if (!post) traverse_pre (blks, pre, env); + else if (!pre) traverse_post(blks, post, env); + else traverse_both(blks, pre, post, 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) +{ + blk_collect_data_t blks; + int old_view = interprocedural_view; + + /* switch off interprocedural view */ + interprocedural_view = 0; + + obstack_init(&blks.obst); + blks.blk_map = new_pset(addr_cmp, 1); + blks.blk_list = new_pdeq(); + + if (node->visited < current_ir_graph->visited) { + /* first step: traverse the graph and fill the lists */ + irg_walk(node, collect_nodes, NULL, &blks); + + /* second step: traverse the list */ + traverse(&blks, pre, post, env); + } + + del_pdeq(blks.blk_list); + del_pset(blks.blk_map); + obstack_free(&blks.obst, NULL); + + interprocedural_view = old_view; +} + +void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) +{ + inc_irg_visited(current_ir_graph); + do_irg_walk_blk(node, pre, post, env); +} + +void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) +{ + ir_graph * rem = current_ir_graph; + + stat_irg_walk_blkwise(irg, (void *)pre, (void *)post); + current_ir_graph = irg; + irg_walk_blkwise(get_irg_end(irg), pre, post, env); + current_ir_graph = rem; +} -- 2.20.1