X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb.c;h=71e573969212bf04a09e29f51dc29aa42c59bac4;hb=109a60bfcf239f2b5304c709a430658920c287cf;hp=4c7916378a091ed66efddf744ccaf46ff0856d23;hpb=88b75a805ce09926dfd05be964bf8b19b8fed959;p=libfirm diff --git a/ir/ana/irextbb.c b/ir/ana/irextbb.c index 4c7916378..71e573969 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-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" @@ -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,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; + } } } @@ -211,20 +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); -#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); + /* 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); /* @@ -251,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. */ @@ -265,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. */ @@ -360,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 *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); + + /* 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++) { @@ -386,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);