X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=3ae9015d36666401048e99285a3aacaf9610b559;hb=f616f878aa0ea06ad96e9c92a58c75d4fe5b3162;hp=68fe2e060a0f073356dbcf2717f55189c570f8fc;hpb=79e7ff30e109e527ea23d353bdbed97ed45a5be4;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 68fe2e060..3ae9015d3 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-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 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,53 +92,107 @@ 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 he control flow from + * block is a JOIN-node ie the control flow from * many other blocks joins here. block is a leader. * Note that we handle unreachable blocks (n <= 0) here too. */ allocate_extblk(block, env); } - else { - ir_node *add_to = get_Block_cfgpred(block, 0); - - if (! is_Bad(add_to)) - add_to = get_nodes_block(add_to); + else { /* we have only one control flow predecessor */ + ir_node *add_to = get_Block_cfgpred_block(block, 0); /* 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); + } } } } +/** A special extended block used as sentinel */ +static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD }; + /** * Post block-walker. Calculates the extended block info. * During construction, we use the (free) block input of all basic blocks * to point to there previous block. */ -static void post_walk_calc_extbb(ir_node *block, void *env) +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 = &_sentinel; if (! extbb) { - ir_node *prev = block; + ir_node *curr, *prev, *list; - /* search the leader */ - do { - prev = get_nodes_block(get_Block_cfgpred(prev, 0)); + /* + * Search the leader. It can happen, that we fall into an endless + * loop, because we enter an unreachable loop that is not yet detected. + * We break the loop using a sentinel. + */ + for (curr = block; !extbb; curr = prev) { + prev = get_Block_cfgpred_block(curr, 0); extbb = get_Block_extbb(prev); - } while (! extbb); + set_Block_extbb(curr, sentinel); + } + + if (extbb == sentinel) { + /* 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); - addto_extblk(extbb, block); + allocate_extblk(block, env); + extbb = get_Block_extbb(block); + set_Block_extbb(block, sentinel); + } + + /* replace all sentinels by the extbb info */ + prev = block; + list = NULL; + while (1) { + if (get_Block_extbb(prev) != sentinel) + break; + 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; + } } } @@ -132,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); /* @@ -155,16 +241,30 @@ void compute_extbb(ir_graph *irg) { for (block = extbb->link, i = 0; i < len; ++i) { ir_node *nblock = get_irn_link(block); - extbb->blks[i] = block; + /* ensure that the leader is the first one */ + extbb->blks[len - 1 - i] = block; set_irn_link(block, NULL); 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. */ @@ -174,12 +274,12 @@ 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. */ ir_extblk *get_nodes_extbb(ir_node *node) { - ir_node *block = is_Block(node) ? node : get_nodes_block(node); + ir_node *block = is_Block(node) ? node : get_irn_n(node, -1); return get_Block_extbb(block); } @@ -237,3 +337,82 @@ 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); + assert(!get_interprocedural_view()); /* interprocedural_view not implemented */ + 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; +}