X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=71e573969212bf04a09e29f51dc29aa42c59bac4;hb=5dfe14ff917ce1b96df2fc89c7074175d66587b8;hp=8b3f867b3a556ce8e29d194545be1f793683e325;hpb=4fdc15b9e6c98c35906c0b3307e07766b3b13264;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 8b3f867b3..71e573969 100644 --- a/ir/ana/irextbb.c +++ b/ir/ana/irextbb.c @@ -1,34 +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. */ @@ -47,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. */ @@ -69,9 +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) || - block == get_irg_end_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. @@ -85,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. @@ -107,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 @@ -124,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); @@ -136,15 +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); - ++extbb->visited; - set_irn_link(prev, extbb->link); - extbb->link = prev; + 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; + } } } @@ -162,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); /* @@ -191,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. */ @@ -205,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. */ @@ -300,16 +369,21 @@ static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk 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; + 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); - irg_extblock_walk_2(block, pre, post, env); + + /* 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 (get_extbb_leader(blk) == get_irg_end_block(current_ir_graph)) { + 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++) { @@ -326,13 +400,16 @@ void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *po } } } + + 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 *end = get_irg_end(irg); - ir_extblk *blk = get_Block_extbb(end); + 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);