X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeblocksched.c;h=872c63040cda974023d6f0121817a743d42dd8ff;hb=dd4cd761ab637d4488c7e29f49843b1b02366acf;hp=ee4669ac6deb128d25842f0b93d87bbcd2489cc1;hpb=7ee20c8e5b735aa494db70b8f4d6ee3092ee9892;p=libfirm diff --git a/ir/be/beblocksched.c b/ir/be/beblocksched.c index ee4669ac6..872c63040 100644 --- a/ir/be/beblocksched.c +++ b/ir/be/beblocksched.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -23,6 +23,16 @@ * @author Matthias Braun, Christoph Mallon * @date 27.09.2006 * @version $Id$ + * + * The goals of the greedy (and ILP) algorithm here works by assuming that + * we want to change as many jumps to fallthroughs as possible (executed jumps + * actually, we have to look at the execution frequencies). The algorithms + * do this by collecting execution frequencies of all branches (which is easily + * possible when all critical edges are split) then removes critical edges where + * possible as we don't need and want them anymore now. The algorithms then try + * to change as many edges to fallthroughs as possible, this is done by setting + * a next and prev pointers on blocks. The greedy algorithm sorts the edges by + * execution frequencies and tries to transform them to fallthroughs in this order */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -48,10 +58,10 @@ #include "beirgmod.h" #include "bemodule.h" #include "be.h" +#include "error.h" -#include -#include -#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #ifdef WITH_ILP #include @@ -105,7 +115,7 @@ typedef struct _edge_t { int pos; /**< number of cfg predecessor (target) */ double execfreq; /**< the frequency */ int highest_execfreq; /**< flag that indicates whether this edge is the edge with the highest - execfreq pointing away from this block */ + execfreq pointing away from this block */ } edge_t; typedef struct _blocksched_env_t { @@ -134,12 +144,15 @@ static void collect_egde_frequency(ir_node *block, void *data) entry->prev = NULL; set_irn_link(block, entry); - if (block == get_irg_start_block(env->irg)) - return; - arity = get_Block_n_cfgpreds(block); - if (arity == 1) { + if (arity == 0) { + assert(block == get_irg_start_block(env->irg) + || block == get_irg_end_block(env->irg)); + /* must be the start block (or end-block for endless loops), nothing to + * do here */ + return; + } else if (arity == 1) { edge.block = block; edge.pos = 0; edge.execfreq = get_block_execfreq(env->execfreqs, block); @@ -190,18 +203,19 @@ static void coalesce_blocks(blocksched_env_t *env) for (i = 0; i < edge_count; ++i) { const edge_t *edge = &env->edges[i]; ir_node *block = edge->block; + int pos = edge->pos; ir_node *pred_block; blocksched_entry_t *entry, *pred_entry; - /* the block might have been removed already... */ - if (is_Bad(get_Block_cfgpred(block, 0))) - continue; - /* only check edge with highest frequency */ if (! edge->highest_execfreq) continue; - pred_block = get_Block_cfgpred_block(block, edge->pos); + /* the block might have been removed already... */ + if (is_Bad(get_Block_cfgpred(block, 0))) + continue; + + pred_block = get_Block_cfgpred_block(block, pos); entry = get_irn_link(block); pred_entry = get_irn_link(pred_block); @@ -223,6 +237,7 @@ static void coalesce_blocks(blocksched_env_t *env) for (i = 0; i < edge_count; ++i) { const edge_t *edge = &env->edges[i]; ir_node *block = edge->block; + int pos = edge->pos; ir_node *pred_block; blocksched_entry_t *entry, *pred_entry; @@ -230,7 +245,11 @@ static void coalesce_blocks(blocksched_env_t *env) if (is_Bad(get_Block_cfgpred(block, 0))) continue; - pred_block = get_Block_cfgpred_block(block, edge->pos); + /* we can't do fallthroughs in backedges */ + if (is_backedge(block, pos)) + continue; + + pred_block = get_Block_cfgpred_block(block, pos); entry = get_irn_link(block); pred_entry = get_irn_link(pred_block); @@ -343,7 +362,7 @@ static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env) ir_node *startblock = get_irg_start_block(irg); blocksched_entry_t *entry = get_irn_link(startblock); - set_using_visited(irg); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); env->worklist = new_pdeq(); @@ -351,7 +370,7 @@ static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env) assert(pdeq_empty(env->worklist)); del_pdeq(env->worklist); - clear_using_visited(irg); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); return entry; } @@ -694,8 +713,7 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr list.end = NULL; list.n_blks = 0; - set_using_irn_link(irg); - set_using_visited(irg); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK); inc_irg_block_visited(irg); create_block_list(get_irg_start_block(irg), &list); @@ -708,8 +726,7 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr blk_list[i] = b; } - clear_using_irn_link(irg); - clear_using_visited(irg); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK); return blk_list; } @@ -748,6 +765,6 @@ ir_node **be_create_block_schedule(ir_graph *irg, ir_exec_freq *execfreqs) #endif /* WITH_ILP */ } - assert(0 && "unknown blocksched algo"); + panic("unknown blocksched algo"); return NULL; }