/*
- * 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.
*
* @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
#include "beblocksched.h"
#include "beirgmod.h"
#include "bemodule.h"
#include "be.h"
+#include "error.h"
+
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
#ifdef WITH_ILP
#include <lpp/lpp.h>
static int algo = BLOCKSCHED_GREEDY;
-
-#ifdef WITH_LIBCORE
-
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
-#include <libcore/lc_timing.h>
-
static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
{ "naiv", BLOCKSCHED_NAIV },
{ "extbb", BLOCKSCHED_EXTBB },
LC_OPT_ENT_ENUM_INT ("algo", "the block scheduling algorithm", &algo_var),
LC_OPT_LAST
};
-#endif /* WITH_LIBCORE */
/*
* ____ _
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 {
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);
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);
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);
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((dbg, LEVEL_1, "Pick succ of %+F\n", block));
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();
assert(pdeq_empty(env->worklist));
del_pdeq(env->worklist);
- clear_using_visited(irg);
+ ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
return entry;
}
}
else {
int i;
- int *edgenums = alloca(sizeof(edgenums[0]) * arity);
snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater, arity - 1);
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);
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;
}
*/
void be_init_blocksched(void)
{
-#ifdef WITH_LIBCORE
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);
-#endif
+
FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
}
#endif /* WITH_ILP */
}
- assert(0 && "unknown blocksched algo");
+ panic("unknown blocksched algo");
return NULL;
}
projects / libfirm / blobdiff