X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=71e573969212bf04a09e29f51dc29aa42c59bac4;hb=5dfe14ff917ce1b96df2fc89c7074175d66587b8;hp=2d5ee83e40b9cd3d74806c3a6073dfe9d643ed04;hpb=149167f9a2f92e8f1ccc21caf2ec4592b9f6fb84;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 2d5ee83e4..71e573969 100644 --- a/ir/ana/irextbb.c +++ b/ir/ana/irextbb.c @@ -1,33 +1,52 @@ /* - * Project: libFIRM - * File name: ir/ana/irextbb.c - * Purpose: Extended basis block support. - * Author: Michael Beck - * Modified by: - * Created: 5.2005 - * CVS-ID: $Id$ - * Copyright: (c) 2002-2005 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 irextbb.c - * - * Computes extended basic blocks. - * - * @author Michael Beck + * @file + * @brief Extended basis block support. + * @author Michael Beck + * @date 5.2005 + * @version $Id$ */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + #include "irextbb_t.h" #include "irgwalk.h" #include "irnode_t.h" +#include "irgraph_t.h" +#include "iredges_t.h" +#include "irouts.h" #include "xmalloc.h" #include "irprintf.h" typedef struct _env { struct obstack *obst; /**< the obstack where allocations took place */ ir_extblk *head; /**< head of the list of all extended blocks */ + ir_node *start_block; /**< the start block of the current graph */ } env_t; +int (is_ir_extbb)(const void *thing) { + return _is_ir_extbb(thing); +} + /** * allocate a new extended block header. */ @@ -46,20 +65,25 @@ static void allocate_extblk(ir_node *block, env_t *env) } /** - * add a block to an extended block + * Returns the number of block successors. + * we are interested only in 1, 2 and >2. */ -static void addto_extblk(ir_extblk *extblk, ir_node *block) -{ - /* link all blocks belonging to this extended block */ - set_irn_link(block, extblk->link); - - extblk->link = block; - extblk->visited++; - - set_Block_extbb(block, extblk); +static int get_block_n_succs(ir_node *block) { + if (edges_activated(current_ir_graph)) { + const ir_edge_t *edge; + + edge = get_block_succ_first(block); + if (! edge) + return 0; + edge = get_block_succ_next(block, edge); + if (! edge) + return 1; + edge = get_block_succ_next(block, edge); + return edge ? 3 : 2; + } + return get_Block_n_cfg_outs(block); } - /** * Pre block-walker. Calculates the extended block info. */ @@ -68,7 +92,7 @@ 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 == env->start_block) { /* * block is a JOIN-node ie the control flow from * many other blocks joins here. block is a leader. @@ -82,18 +106,38 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) /* blocks with only one BAD predecessors are leaders too */ if (is_Bad(add_to)) { allocate_extblk(block, env); - } - else { + } else { /* * Only one control flow predecessor. This block belongs * to the same extended basic block as its predecessor. */ - set_Block_extbb(block, NULL); + ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0)); + + if (irn_not_visited(cf_op)) { + ir_node *pred_bl = get_nodes_block(cf_op); + if (get_block_n_succs(pred_bl) > 2) { + /* More than two successors means we have a jump table. + * we cannot include a jump target into the current extended + * basic block, so create a new one here. + */ + allocate_extblk(block, env); + } else { + /* either the previous block has only one successor or + * this is the first successor after an if, include it. + */ + set_Block_extbb(block, NULL); + } + mark_irn_visited(cf_op); + } else { + /* already marked, so begin a new extended block here */ + allocate_extblk(block, env); + } } } } -static int _sentinel; +/** A special extended block used as sentinel */ +static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD, NULL, NULL }; /** * Post block-walker. Calculates the extended block info. @@ -104,10 +148,10 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) { ir_extblk *extbb = get_Block_extbb(block); env_t *env = ctx; - ir_extblk *sentinel = (ir_extblk *)&_sentinel; + ir_extblk *sentinel = &_sentinel; if (! extbb) { - ir_node *curr, *prev; + ir_node *curr, *prev, *list; /* * Search the leader. It can happen, that we fall into an endless @@ -121,7 +165,7 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) } if (extbb == sentinel) { - /* We detect a dead loop. We fix this by allocating an + /* We detect a dead loop. We fix this by allocating a * special Extended block */ ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block); @@ -133,12 +177,22 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) /* replace all sentinels by the extbb info */ prev = block; + list = NULL; while (1) { if (get_Block_extbb(prev) != sentinel) break; - set_Block_extbb(prev, extbb); + set_irn_link(prev, list); + list = prev; prev = get_Block_cfgpred_block(prev, 0); } + /* arg, the list is in wrong order, turn around and add to the extbb list */ + for (curr = list; curr; curr = prev) { + prev = get_irn_link(curr); + set_irn_link(curr, extbb->link); + extbb->link = curr; + set_Block_extbb(curr, extbb); + ++extbb->visited; + } } } @@ -156,9 +210,17 @@ void compute_extbb(ir_graph *irg) { } obstack_init(irg->extbb_obst); - env.obst = irg->extbb_obst; - env.head = NULL; + env.obst = irg->extbb_obst; + env.head = NULL; + env.start_block = get_irg_start_block(irg); + + if (! edges_activated(irg)) { + /* we don't have edges */ + assure_irg_outs(irg); + } + /* we must mark nodes, so increase the visited flag */ + inc_irg_visited(irg); irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env); /* @@ -185,11 +247,24 @@ void compute_extbb(ir_graph *irg) { block = nblock; } +#ifndef NDEBUG + /* check it */ + for (i = len - 1; i > 0; --i) { + ir_node *blk = extbb->blks[i]; + + if (get_Block_n_cfgpreds(blk) != 1) { + assert(!"Block for more than one predecessors is no leader"); + } else if (get_Block_cfgpred_block(blk, 0) != extbb->blks[i - 1]) { + assert(!"extbb block order wrong"); + } + } +#endif + extbb->link = NULL; extbb->visited = 0; } - irg->extblk_state = ir_extblk_info_valid; + irg->extblk_state = extblk_valid; } /* free all extended block info. */ @@ -199,7 +274,7 @@ void free_extbb(ir_graph *irg) { xfree(irg->extbb_obst); irg->extbb_obst = NULL; } - irg->extblk_state = ir_extblk_info_none; + irg->extblk_state = extblk_none; } /* Return the extended block of a node. */ @@ -262,3 +337,81 @@ 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 *pred, *start_bl = get_irg_start_block(current_ir_graph); + ir_extblk *start_blk = get_Block_extbb(start_bl); + int i; + + assert(blk); + inc_irg_block_visited(current_ir_graph); + + /* assure the start block is the first one */ + mark_extbb_visited(start_blk); + if (post) + post(start_blk, env); + irg_extblock_walk_2(blk, pre, post, env); + + /* keepalive: the endless loops ... */ + if (blk == get_Block_extbb(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); + } + } + } + + if (pre) + pre(start_blk, 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 *endbl = get_irg_end_block(irg); + ir_extblk *blk = get_Block_extbb(endbl); + ir_graph *rem = current_ir_graph; + current_ir_graph = irg; + irg_extblock_walk(blk, pre, post, env); + current_ir_graph = rem; +}