/*
- * 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-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
+ * @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 */
+#endif
#include "beblocksched.h"
#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"
-#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>
-#endif /* WITH_LIBCORE */
#ifdef WITH_ILP
#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
#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;
static int algo = BLOCKSCHED_GREEDY;
-#ifdef WITH_LIBCORE
static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
{ "naiv", BLOCKSCHED_NAIV },
{ "extbb", BLOCKSCHED_EXTBB },
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
};
-#endif
/*
* ____ _
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
+ int highest_execfreq; /**< flag that indicates whether this edge is the edge with the highest
execfreq pointing away from this block */
} edge_t;
edge_t *edges;
pdeq *worklist;
int blockcount;
- DEBUG_ONLY(firm_dbg_module_t *dbg;)
} blocksched_env_t;
/**
*/
static void collect_egde_frequency(ir_node *block, void *data)
{
- blocksched_env_t *env = data;
- ir_graph *irg = env->irg;
- ir_node *startblock = get_irg_start_block(irg);
+ blocksched_env_t *env = data;
int arity;
edge_t edge;
blocksched_entry_t *entry;
entry->prev = NULL;
set_irn_link(block, entry);
- if (block == startblock)
- 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);
ARR_APP1(edge_t, env->edges, edge);
} else {
int i;
- double highest_execfreq = -1;
+ double highest_execfreq = -1.0;
int highest_edge_num = -1;
edge.block = block;
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);
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;
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;
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);
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;
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) {
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);
}
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
}
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);
ir_node *startblock = get_irg_start_block(irg);
blocksched_entry_t *entry = get_irn_link(startblock);
+ set_using_visited(irg);
inc_irg_visited(irg);
env->worklist = new_pdeq();
assert(pdeq_empty(env->worklist));
del_pdeq(env->worklist);
+ clear_using_visited(irg);
+
return 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);
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);
// sort interblock edges by execution frequency
qsort(env.edges, ARR_LEN(env.edges), sizeof(env.edges[0]), cmp_edges);
- be_remove_empty_blocks(irg);
+ (void)be_remove_empty_blocks(irg);
if (algo != BLOCKSCHED_NAIV)
coalesce_blocks(&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);
}
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;
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);
irg_block_walk_graph(irg, collect_egde_frequency_ilp, NULL, &env);
- be_remove_empty_blocks(irg);
+ (void)be_remove_empty_blocks(irg);
coalesce_blocks_ilp(&env);
start_entry = finish_block_schedule(&env.env);
if (list->start == NULL) {
list->start = block;
list->end = block;
- }
- else {
+ } else {
set_irn_link(list->end, block);
list->end = block;
}
list.start = NULL;
list.end = NULL;
list.n_blks = 0;
+
+ set_using_irn_link(irg);
+ set_using_visited(irg);
inc_irg_block_visited(irg);
+
create_block_list(get_irg_start_block(irg), &list);
/** create an array, so we can go forward and backward */
blk_list[i] = b;
}
+ clear_using_irn_link(irg);
+ clear_using_visited(irg);
+
return blk_list;
}
* |_| |_|\__,_|_|_| |_|
*
*/
-
-#ifdef WITH_LIBCORE
-void be_block_schedule_register_options(lc_opt_entry_t *grp)
+void be_init_blocksched(void)
{
- static int run_once = 0;
- lc_opt_entry_t *blocksched_grp;
-
- if (run_once)
- return;
-
- run_once = 1;
- blocksched_grp = lc_opt_get_grp(grp, "blocksched");
+ lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+ 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");
}
-#endif /* WITH_LIBCORE */
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched);
ir_node **be_create_block_schedule(ir_graph *irg, ir_exec_freq *execfreqs)
{
projects / libfirm / blobdiff