From 4fdc15b9e6c98c35906c0b3307e07766b3b13264 Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Sat, 18 Mar 2006 21:27:01 +0000 Subject: [PATCH] Fixed extbb construction (why it was damaged ?) Add walker for extbb's [r7473] --- ir/ana/irextbb.c | 78 +++++++++++++++++++++++++++++++++++++++++++++- ir/ana/irextbb.h | 72 ++++++++++++++++++++++++++++++++++++++++-- ir/ana/irextbb_t.h | 6 ++-- 3 files changed, 149 insertions(+), 7 deletions(-) diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 2d5ee83e4..8b3f867b3 100644 --- a/ir/ana/irextbb.c +++ b/ir/ana/irextbb.c @@ -20,6 +20,7 @@ #include "irextbb_t.h" #include "irgwalk.h" #include "irnode_t.h" +#include "irgraph_t.h" #include "xmalloc.h" #include "irprintf.h" @@ -68,7 +69,9 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) int n = get_Block_n_cfgpreds(block); env_t *env = ctx; - if (n <= 0 || n > 1 || block == get_irg_start_block(current_ir_graph)) { + if (n <= 0 || n > 1 || + block == get_irg_start_block(current_ir_graph) || + block == get_irg_end_block(current_ir_graph)) { /* * block is a JOIN-node ie the control flow from * many other blocks joins here. block is a leader. @@ -137,6 +140,9 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) if (get_Block_extbb(prev) != sentinel) break; set_Block_extbb(prev, extbb); + ++extbb->visited; + set_irn_link(prev, extbb->link); + extbb->link = prev; prev = get_Block_cfgpred_block(prev, 0); } } @@ -262,3 +268,73 @@ ir_node *(get_extbb_leader)(ir_extblk *blk) { long get_extbb_node_nr(ir_extblk *blk) { return get_irn_node_nr(get_extbb_leader(blk)); } + +static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env) +{ + int i; + ir_node *node; + + if (extbb_not_visited(blk)) { + mark_extbb_visited(blk); + + if (pre) pre(blk, env); + + node = get_extbb_leader(blk); + for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) { + /* find the corresponding predecessor block. */ + ir_node *pred = get_Block_cfgpred_block(node, i); + if (is_Block(pred)) { + /* recursion */ + irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env); + } + else { + assert(is_Bad(pred)); + } + } + + if (post) post(blk, env); + } +} + +/* walks only over extended Block nodes in the graph. Has it's own visited + flag, so that it can be interleaved with the other walker. */ +void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env) +{ + ir_node *block, *pred; + int i; + + assert(blk); + assert(!get_interprocedural_view()); /* interprocedural_view not implemented */ + inc_irg_block_visited(current_ir_graph); + irg_extblock_walk_2(block, pre, post, env); + + /* keepalive: the endless loops ... */ + if (get_extbb_leader(blk) == get_irg_end_block(current_ir_graph)) { + ir_node *node = get_irg_end(current_ir_graph); + int arity = get_irn_arity(node); + for (i = 0; i < arity; i++) { + pred = get_irn_n(node, i); + if (is_Block(pred)) + irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env); + else if (is_Phi(pred)) { + /* Sometimes the blocks died, but are still reachable through Phis. + * Make sure the algorithms that try to remove these reach them. */ + ir_node *block = get_nodes_block(pred); + + if (! is_Bad(block)) + irg_extblock_walk_2(get_Block_extbb(block), pre, post, env); + } + } + } +} + +/* Walks only over reachable Extended Basic Block nodes in the graph. */ +void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env) +{ + ir_node *end = get_irg_end(irg); + ir_extblk *blk = get_Block_extbb(end); + ir_graph *rem = current_ir_graph; + current_ir_graph = irg; + irg_extblock_walk(blk, pre, post, env); + current_ir_graph = rem; +} diff --git a/ir/ana/irextbb.h b/ir/ana/irextbb.h index d64b5c215..18f0676f9 100644 --- a/ir/ana/irextbb.h +++ b/ir/ana/irextbb.h @@ -20,7 +20,7 @@ #ifndef _IREXTBB_H_ #define _IREXTBB_H_ -#include "irgraph.h" +#include "firm_types.h" #ifndef _IR_EXTBB_TYPEDEF_ #define _IR_EXTBB_TYPEDEF_ @@ -34,75 +34,141 @@ typedef enum { ir_extblk_info_invalid = 2 /**< Extended basic block information is constructed but invalid. */ } irg_extblk_info_state; +/* type of callback function for ir_graph walk */ +#ifndef _EXTBB_WALK_FUNC_TYPEDEF_ +#define _EXTBB_WALK_FUNC_TYPEDEF_ +/** + * The type of a walk function. Does not use the link field. + * + * @param blk - the extended basic block that is just visited + * @param env - an environment pointer passed by the walk functions + */ +typedef void extbb_walk_func(ir_extblk *blk, void *env); +#endif + /** * Compute the extended basic blocks for a graph */ void compute_extbb(ir_graph *irg); /** - * free all extended block info + * free all extended block info. */ void free_extbb(ir_graph *irg); /** * Return the extended block of a node. + * + * @param blk the extended basic block */ ir_extblk *get_nodes_extbb(ir_node *node); /** * Gets the visited counter of an extended block. + * + * @param blk the extended basic block */ unsigned long get_extbb_visited(const ir_extblk *blk); /** * Sets the visited counter of an extended block. + * + * @param blk the extended basic block */ void set_extbb_visited(ir_extblk *blk, unsigned long visited); /** * Mark an extended block as visited in a graph. + * Uses the block visit flag. + * + * @param blk the extended basic block */ void mark_extbb_visited(ir_extblk *blk); /** * Returns non-zero if an extended was visited. + * Uses the block visit flag. + * + * @param blk the extended basic block */ int extbb_visited(const ir_extblk *blk); /** * Returns non-zero if an extended block was NOT visited. + * Uses the block visit flag. + * + * @param blk the extended basic block */ int extbb_not_visited(const ir_extblk *blk); /** * Returns the link field of an extended block. + * + * @param blk the extended basic block */ void *get_extbb_link(const ir_extblk *blk); /** * Sets the link field of an extended block. + * + * @param blk the extended basic block + * @param link the new link value */ void set_extbb_link(ir_extblk *blk, void *link); /** * Return the number of basic blocks of an extended block. + * + * @param blk the extended basic block */ int get_extbb_n_blocks(const ir_extblk *blk); /** * Return the i'th basic block of an extended block. + * + * @param blk the extended basic block + * @param pos the position */ ir_node *get_extbb_block(ir_extblk *blk, int pos); /** - * Return the leader basis block of an extended block. + * Return the leader basic block of an extended block. + * + * @param blk the extended basic block */ ir_node *get_extbb_leader(ir_extblk *blk); /** * Return the node number of an extended block. * Its the block number of the leader block + * + * @param blk the extended basic block */ long get_extbb_node_nr(ir_extblk *blk); +/** + * Walks only over Extended Basic Block nodes in the graph. + * + * @param blk - the start extended block node + * @param pre - walker function, executed before the predecessor of a node are visited + * @param post - walker function, executed after the predecessor of a node are visited + * @param env - environment, passed to pre and post + * + * This function Walks only over Block nodes in the graph. Has it's own visited + * flag, so that it can be interleaved with the other walker. + * If a none block is passed, starts at the block this node belongs to. + * If end is passed also visits kept alive blocks. Does not use the link field. + */ +void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env); + +/** + * Walks only over reachable Extended Basic Block nodes in the graph. + * + * @param irg - the irg graph + * @param pre - walker function, executed before the predecessor of a block are visited + * @param post - walker function, executed after the predecessor of a block are visited + * @param env - environment, passed to pre and post + */ +void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env); + #endif /* _IREXTBB_H_ */ diff --git a/ir/ana/irextbb_t.h b/ir/ana/irextbb_t.h index 926ed8530..6019501f1 100644 --- a/ir/ana/irextbb_t.h +++ b/ir/ana/irextbb_t.h @@ -63,7 +63,7 @@ _set_extbb_visited(ir_extblk *blk, unsigned long visited) { static INLINE void _mark_extbb_visited(ir_extblk *blk) { assert(blk); - blk->visited = current_ir_graph->visited; + blk->visited = current_ir_graph->block_visited; } /** @@ -73,7 +73,7 @@ _mark_extbb_visited(ir_extblk *blk) { static INLINE int _extbb_visited(const ir_extblk *blk) { assert(blk); - return blk->visited >= current_ir_graph->visited; + return blk->visited >= current_ir_graph->block_visited; } /** @@ -83,7 +83,7 @@ _extbb_visited(const ir_extblk *blk) { static INLINE int _extbb_not_visited(const ir_extblk *blk) { assert(blk); - return blk->visited < current_ir_graph->visited; + return blk->visited < current_ir_graph->block_visited; } /** -- 2.20.1