X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firextbb2.c;h=31f77bea62c067b4c840aae5848f576c684e8522;hb=fe49319b78e1670a09a150b79a1dea01880798c2;hp=6826e615bfc4931d75bcc6d50a32f908806ecfe7;hpb=f6cc87ea620e16ecb9d388f54abc8e76906e5488;p=libfirm diff --git a/ir/ana/irextbb2.c b/ir/ana/irextbb2.c index 6826e615b..31f77bea6 100644 --- a/ir/ana/irextbb2.c +++ b/ir/ana/irextbb2.c @@ -1,23 +1,34 @@ /* - * Project: libFIRM - * File name: ir/ana/irextbb2.c - * Purpose: Alternate extended basic block computation - * Author: Matthias Braun - * 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 - * + * @file + * @brief Alternative extended basic block computation + * @author Matthias Braun + * @date 5.2005 + * @version $Id$ + * @brief * Alternative algorithm for computing extended basic blocks (using out edges * and execution frequencies) - * - * @author Matthias Braun */ +#include "config.h" + #include "irextbb_t.h" #include "irgwalk.h" #include "irnode_t.h" @@ -28,10 +39,10 @@ #include "irprintf.h" #include "execfreq.h" -typedef struct _env { - struct obstack *obst; /**< the obstack where allocations took place */ +typedef struct env { + struct obstack *obst; /**< the obstack where allocations took place */ ir_extblk *head; /**< head of the list of all extended blocks */ - exec_freq_t *execfreqs; + ir_exec_freq *execfreqs; } env_t; /** @@ -39,7 +50,7 @@ typedef struct _env { */ static ir_extblk *allocate_extblk(ir_node *block, env_t *env) { - ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk)); + ir_extblk *extblk = OALLOC(env->obst, ir_extblk); extblk->kind = k_ir_extblk; extblk->visited = 1; @@ -71,16 +82,19 @@ static void addto_extblk(ir_extblk *extblk, ir_node *block) * Returns the number of block successors. * we are interested only in 1, 2 and >2. */ -static int get_block_n_succs(ir_node *block) { +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; } @@ -92,11 +106,12 @@ static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env); static void create_extblk(ir_node *block, env_t *env) { - if(irn_visited(block)) + ir_extblk *extblk; + + if (irn_visited_else_mark(block)) return; - ir_extblk *extblk = allocate_extblk(block, env); - mark_irn_visited(block); + extblk = allocate_extblk(block, env); pick_successor(block, extblk, env); } @@ -104,16 +119,15 @@ static void create_extblk(ir_node *block, env_t *env) static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env) { const ir_edge_t *edge; - ir_node *best_succ = NULL; - double best_execfreq = -1; - - /* 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. - */ - if(get_block_n_succs(block) > 2) { - const ir_edge_t *edge; + ir_node *best_succ = NULL; + double best_execfreq = -1; + /* + 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. + */ + if (get_block_n_succs(block) > 2) { foreach_block_succ(block, edge) { ir_node *succ = get_edge_src_irn(edge); create_extblk(succ, env); @@ -126,29 +140,35 @@ static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env) ir_node *succ = get_edge_src_irn(edge); double execfreq; - if(get_Block_n_cfgpreds(succ) > 1) { + if (irn_visited(succ)) + continue; + + if (get_Block_n_cfgpreds(succ) > 1) { create_extblk(succ, env); continue; } execfreq = get_block_execfreq(env->execfreqs, succ); - // remember best sucessor and make non best successor with only 1 - // pred block to new extbb leaders - if(execfreq > best_execfreq) { - if(best_succ != NULL) { + /* + Remember best successor and make non best successor with only 1 + pred block to new extbb leaders. + */ + if (execfreq > best_execfreq) { + if (best_succ != NULL) { create_extblk(best_succ, env); } best_execfreq = execfreq; best_succ = succ; - } else { + } + else { create_extblk(succ, env); } } - // add best successor and recursively try to pick more - if(best_succ != NULL) { + /* add best successor and recursively try to pick more */ + if (best_succ != NULL) { addto_extblk(extblk, best_succ); mark_irn_visited(best_succ); pick_successor(best_succ, extblk, env); @@ -158,20 +178,22 @@ static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env) /* * Compute the extended basic blocks for a graph */ -void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) { - env_t env; +void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs) +{ + env_t env; ir_extblk *extbb, *next; - ir_node *endblock; + ir_node *endblock; if (irg->extbb_obst) { obstack_free(irg->extbb_obst, NULL); - } else { - irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst)); + } + else { + irg->extbb_obst = XMALLOC(struct obstack); } obstack_init(irg->extbb_obst); - env.obst = irg->extbb_obst; - env.head = NULL; + env.obst = irg->extbb_obst; + env.head = NULL; env.execfreqs = execfreqs; assure_irg_outs(irg); @@ -180,19 +202,17 @@ void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) { inc_irg_visited(irg); create_extblk(get_irg_start_block(irg), &env); - // the end block needs a extbb assigned (even for endless loops) + /* the end block needs a extbb assigned (even for endless loops) */ endblock = get_irg_end_block(irg); - if(!irn_visited(endblock)) { - create_extblk(endblock, &env); - } + create_extblk(endblock, &env); /* - * Ok, we have now the list of all extended blocks starting with env.head - * every extended block "knowns" the number of blocks in visited and - * the blocks are linked in link. - * Now we can create arrays that hold the blocks, some kind of "out" edges - * for the extended block - */ + Ok, we have now the list of all extended blocks starting with env.head + every extended block "knowns" the number of blocks in visited and + the blocks are linked in link. + Now we can create arrays that hold the blocks, some kind of "out" edges + for the extended block + */ for (extbb = env.head; extbb; extbb = next) { int i, len = (int)extbb->visited; ir_node *block; @@ -201,8 +221,8 @@ void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) { extbb->blks = NEW_ARR_D(ir_node *, env.obst, len); - for (block = extbb->link, i = 0; i < len; ++i) { - ir_node *nblock = get_irn_link(block); + for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) { + ir_node *nblock = (ir_node*) get_irn_link(block); /* ensure that the leader is the first one */ extbb->blks[len - 1 - i] = block; @@ -210,16 +230,18 @@ void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) { block = nblock; } - for(i = 0; i < len; ++i) { - if(i > 0) +#if 0 + for (i = 0; i < len; ++i) { + if (i > 0) printf(", "); ir_printf("%+F", extbb->blks[i]); } printf("\n"); +#endif extbb->link = NULL; extbb->visited = 0; } - irg->extblk_state = extblk_valid; + irg->extblk_state = ir_extblk_info_valid; }