X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=de41e7cb772200753eaa8f6aeb7a99888be41355;hb=6f996fb00afc2ae14904b46fb21e2968b5faf4f7;hp=789cb256792eb16b7e57862c4a829ea311e3bb92;hpb=a9ee2b1a5617058955324f719cfe493d01d36609;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 789cb2567..de41e7cb7 100644 --- a/ir/ana/irextbb.c +++ b/ir/ana/irextbb.c @@ -1,22 +1,33 @@ /* - * 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" @@ -29,10 +40,11 @@ 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); + return _is_ir_extbb(thing); } /** @@ -52,26 +64,11 @@ static void allocate_extblk(ir_node *block, env_t *env) set_irn_link(block, NULL); } -/** - * add a block to an extended block - */ -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); -} - /** * Returns the number of block successors. * we are interested only in 1, 2 and >2. */ static int get_block_n_succs(ir_node *block) { -#ifdef FIRM_EDGES_INPLACE if (edges_activated(current_ir_graph)) { const ir_edge_t *edge; @@ -84,7 +81,6 @@ static int get_block_n_succs(ir_node *block) { edge = get_block_succ_next(block, edge); return edge ? 3 : 2; } -#endif return get_Block_n_cfg_outs(block); } @@ -96,8 +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. @@ -111,8 +106,7 @@ 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. @@ -127,16 +121,14 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) * basic block, so create a new one here. */ allocate_extblk(block, env); - } - else { + } 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 { + } else { /* already marked, so begin a new extended block here */ allocate_extblk(block, env); } @@ -145,7 +137,7 @@ static void pre_walk_calc_extbb(ir_node *block, void *ctx) } /** A special extended block used as sentinel */ -static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD }; +static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD, NULL, NULL }; /** * Post block-walker. Calculates the extended block info. @@ -159,7 +151,7 @@ static void post_walk_calc_extbb(ir_node *block, void *ctx) 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 @@ -173,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); @@ -185,78 +177,25 @@ 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; + } } } -#ifdef NEED_SORT -/** - * Walker for cf_dependent_on(). - * This function searches a node tgt recursively from a given node - * but is restricted to the given extended basic block. - * - * @return 1 if tgt was reachable from curr, 0 if not. - */ -static int check_cf_dependence(ir_node *curr, ir_node *tgt, ir_extblk *extbb) -{ - int n, i; - - /* Note: we did not include the leader in our serach, so - there could not be any loops here. */ - if (get_Block_extbb(curr) != extbb) - return 0; - - if (curr == tgt) - return 1; - - for (i = 0, n = get_Block_n_cfgpreds(curr); i < n; ++i) { - if (check_cf_dependence(get_Block_cfgpred_block(curr, i), tgt, extbb)) - return 1; - } - return 0; -} - -/** - * Check if a block is control dependent on another one. - * Both blocks must be in the same extended basic block. - * @param blk1 The first block. - * @param blk2 The second block. - * @return 1, if blk1 is control dependent (transitively) on blk2, 0 if not. - */ -static int cf_dependent_on(ir_node *blk1, ir_node *blk2) -{ - ir_extblk *extbb = get_Block_extbb(blk1); - ir_graph *irg = get_irn_irg(blk1); - - assert(extbb == get_Block_extbb(blk2)); - return check_cf_dependence(blk1, blk2, extbb); -} - -/** - * Compare two blocks for dependency. - * - * @return - * 0 if both blocks nodes are equal - * 1 block b1 depends on block b2 - * -1 block b2 depends on block d2 - */ -static int block_order(const void *b1, const void *b2) -{ - ir_node *n1 = *(ir_node **)b1; - ir_node *n2 = *(ir_node **)b2; - - return n1 == n2 ? 0 : (cf_dependent_on(n1, n2) ? -1 : 1); -} -#endif /* NEED_SORT */ - /* * Compute the extended basic blocks for a graph */ @@ -271,17 +210,14 @@ 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); -#ifdef FIRM_EDGES_INPLACE - if (edges_activated(irg)) { - /* we have edges */ + if (! edges_activated(irg)) { + /* we don't have edges */ + assure_irg_outs(irg); } - else -#endif - if (get_irg_outs_state(irg) != outs_consistent) - compute_irg_outs(irg); /* we must mark nodes, so increase the visited flag */ inc_irg_visited(irg); @@ -311,19 +247,21 @@ void compute_extbb(ir_graph *irg) { block = nblock; } - extbb->link = NULL; - extbb->visited = 0; +#ifndef NDEBUG + /* check it */ + for (i = len - 1; i > 0; --i) { + ir_node *blk = extbb->blks[i]; -#ifdef NEED_SORT - /* we want the blocks in scheduled order, so sort them */ - /* FIXME: is this really needed? Or generates the algorithm automagically ordered ones? */ - if (len > 1) { - /* temporary remove the leader from the extended block to break loops */ - set_Block_extbb(extbb->blks[0], NULL); - qsort(&extbb->blks[1], len-1, sizeof(extbb->blks[0]), block_order); - set_Block_extbb(extbb->blks[0], extbb); + 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 = extblk_valid;