X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeblocksched.c;h=b977abc26ea149bfe0c0181214858fb8b0bf51b3;hb=026ec52ac914eee06e7afb961fb754735fb4ad9f;hp=abec3545dfa3268ce9738225940800d2ec6c38fb;hpb=6981dd3274e6753e50f66c8cbe17b37bd41708e5;p=libfirm diff --git a/ir/be/beblocksched.c b/ir/be/beblocksched.c index abec3545d..b977abc26 100644 --- a/ir/be/beblocksched.c +++ b/ir/be/beblocksched.c @@ -1,13 +1,40 @@ /* - * Author: Matthias Braun, Christoph Mallon - * Date: 27.09.2006 - * Copyright: (c) Universitaet Karlsruhe - * License: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. - * CVS-Id: $Id$ + * 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 + * @brief Block-scheduling strategies. + * @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" -#endif /* HAVE_CONFIG_H */ #include "beblocksched.h" @@ -18,25 +45,29 @@ #include "iredges.h" #include "irgwalk.h" +#include "irnode_t.h" #include "irgraph_t.h" #include "irloop.h" #include "irprintf.h" +#include "execfreq.h" #include "irdump_t.h" #include "irtools.h" #include "debug.h" #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 #include #endif /* WITH_ILP */ +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) + typedef enum _blocksched_algos_t { BLOCKSCHED_NAIV, BLOCKSCHED_EXTBB, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP } blocksched_algos_t; @@ -59,7 +90,7 @@ static lc_opt_enum_int_var_t algo_var = { static const lc_opt_table_entry_t be_blocksched_options[] = { LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var), - { NULL } + LC_OPT_LAST }; /* @@ -81,8 +112,8 @@ typedef struct _edge_t { ir_node *block; /**< source block */ int pos; /**< number of cfg predecessor (target) */ double execfreq; /**< the frequency */ - int highest_execfreq; /**< flag that indicates wether this edge is the edge with the highest - execfreq pointing away from this block */ + int highest_execfreq; /**< flag that indicates whether this edge is the edge with the highest + execfreq pointing away from this block */ } edge_t; typedef struct _blocksched_env_t { @@ -92,7 +123,6 @@ typedef struct _blocksched_env_t { edge_t *edges; pdeq *worklist; int blockcount; - DEBUG_ONLY(firm_dbg_module_t *dbg;) } blocksched_env_t; /** @@ -112,12 +142,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_irn_arity(block); + 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); @@ -168,18 +201,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); @@ -191,7 +225,7 @@ static void coalesce_blocks(blocksched_env_t *env) continue; /* schedule the 2 blocks behind each other */ - DBG((env->dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n", + DBG((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n", pred_entry->block, entry->block, edge->execfreq)); pred_entry->next = entry; entry->prev = pred_entry; @@ -201,6 +235,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; @@ -208,7 +243,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); @@ -217,7 +256,7 @@ static void coalesce_blocks(blocksched_env_t *env) continue; /* schedule the 2 blocks behind each other */ - DBG((env->dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n", + DBG((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n", pred_entry->block, entry->block, edge->execfreq)); pred_entry->next = entry; entry->prev = pred_entry; @@ -232,13 +271,12 @@ static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *en const ir_edge_t *edge; double best_succ_execfreq; - if (irn_visited(block)) + if (irn_visited_else_mark(block)) return; env->blockcount++; - mark_irn_visited(block); - DBG((env->dbg, LEVEL_1, "Pick succ of %+F\n", block)); + DBG((dbg, LEVEL_1, "Pick succ of %+F\n", block)); /* put all successors into the worklist */ foreach_block_succ(block, edge) { @@ -263,7 +301,7 @@ static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *en if (irn_visited(succ_entry->block)) continue; - DBG((env->dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block)); + DBG((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block)); pdeq_putr(env->worklist, succ_entry->block); } @@ -272,7 +310,7 @@ static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *en return; } - DBG((env->dbg, LEVEL_1, "deciding...\n")); + DBG((dbg, LEVEL_1, "deciding...\n")); best_succ_execfreq = -1; /* no successor yet: pick the successor block with the highest execution @@ -297,11 +335,11 @@ static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *en } if (succ == NULL) { - DBG((env->dbg, LEVEL_1, "pick from worklist\n")); + DBG((dbg, LEVEL_1, "pick from worklist\n")); do { if (pdeq_empty(env->worklist)) { - DBG((env->dbg, LEVEL_1, "worklist empty\n")); + DBG((dbg, LEVEL_1, "worklist empty\n")); return; } succ = pdeq_getl(env->worklist); @@ -321,6 +359,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); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); env->worklist = new_pdeq(); @@ -328,6 +367,8 @@ static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env) assert(pdeq_empty(env->worklist)); del_pdeq(env->worklist); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); + return entry; } @@ -337,14 +378,15 @@ static ir_node **create_blocksched_array(blocksched_env_t *env, blocksched_entry int i = 0; ir_node **block_list; blocksched_entry_t *entry; + (void) env; block_list = NEW_ARR_D(ir_node *, obst, count); - DBG((env->dbg, LEVEL_1, "Blockschedule:\n")); + DBG((dbg, LEVEL_1, "Blockschedule:\n")); for (entry = first; entry != NULL; entry = entry->next) { assert(i < count); block_list[i++] = entry->block; - DBG((env->dbg, LEVEL_1, "\t%+F\n", entry->block)); + DBG((dbg, LEVEL_1, "\t%+F\n", entry->block)); } assert(i == count); @@ -366,7 +408,6 @@ static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execf env.edges = NEW_ARR_F(edge_t, 0); env.worklist = NULL; env.blockcount = 0; - FIRM_DBG_REGISTER(env.dbg, "firm.be.blocksched"); // collect edge execution frequencies irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env); @@ -504,7 +545,7 @@ static void coalesce_blocks_ilp(blocksched_ilp_env_t *env) pred = get_Block_cfgpred_block(block, edge->pos); entry = get_irn_link(pred); - DBG((env->env.dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n", + DBG((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n", pred, block, edge->pos)); lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0); } @@ -538,7 +579,7 @@ static void coalesce_blocks_ilp(blocksched_ilp_env_t *env) if (is_Bad(get_Block_cfgpred(block, 0))) continue; - is_jump = lpp_get_var_sol(env->lpp, edge->ilpvar); + is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar); if (is_jump) continue; @@ -567,7 +608,6 @@ static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreq env.env.worklist = NULL; env.env.blockcount = 0; env.ilpedges = NEW_ARR_F(ilp_edge_t, 0); - FIRM_DBG_REGISTER(env.env.dbg, "firm.be.blocksched"); env.lpp = new_lpp("blockschedule", lpp_minimize); lpp_set_time_limit(env.lpp, 20); @@ -609,8 +649,7 @@ static void add_block(anchor *list, ir_node *block) { if (list->start == NULL) { list->start = block; list->end = block; - } - else { + } else { set_irn_link(list->end, block); list->end = block; } @@ -670,7 +709,10 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr list.start = NULL; list.end = NULL; list.n_blks = 0; + + 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); /** create an array, so we can go forward and backward */ @@ -681,6 +723,8 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr blk_list[i] = b; } + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK); + return blk_list; } @@ -698,6 +742,8 @@ void be_init_blocksched(void) lc_opt_entry_t *blocksched_grp = lc_opt_get_grp(be_grp, "blocksched"); lc_opt_add_table(blocksched_grp, be_blocksched_options); + + FIRM_DBG_REGISTER(dbg, "firm.be.blocksched"); } BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched); @@ -716,6 +762,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; }