/*
- * 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @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
#include "array.h"
#include "pdeq.h"
-
+#include "beirg.h"
#include "iredges.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "execfreq.h"
#include "irdump_t.h"
#include "irtools.h"
+#include "util.h"
#include "debug.h"
#include "beirgmod.h"
#include "bemodule.h"
typedef struct blocksched_env_t blocksched_env_t;
struct blocksched_env_t {
ir_graph *irg;
- struct obstack *obst;
- ir_exec_freq *execfreqs;
+ struct obstack obst;
edge_t *edges;
pdeq *worklist;
int blockcount;
};
+static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
+{
+ return (blocksched_entry_t*)get_irn_link(block);
+}
+
/**
* Collect cfg frequencies of all edges between blocks.
* Also determines edge with highest frequency.
memset(&edge, 0, sizeof(edge));
- entry = OALLOCZ(env->obst, blocksched_entry_t);
+ entry = OALLOCZ(&env->obst, blocksched_entry_t);
entry->block = block;
set_irn_link(block, entry);
} else if (arity == 1) {
ir_node *pred_block = get_Block_cfgpred_block(block, 0);
ir_loop *pred_loop = get_irn_loop(pred_block);
- float freq = (float)get_block_execfreq(env->execfreqs, block);
+ float freq = (float)get_block_execfreq(block);
/* is it an edge leaving a loop */
if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
- float pred_freq = (float)get_block_execfreq(env->execfreqs, pred_block);
+ float pred_freq = (float)get_block_execfreq(pred_block);
edge.outedge_penalty_freq = -(pred_freq - freq);
}
double execfreq;
ir_node *pred_block = get_Block_cfgpred_block(block, i);
- execfreq = get_block_execfreq(env->execfreqs, pred_block);
+ execfreq = get_block_execfreq(pred_block);
edge.pos = i;
edge.execfreq = execfreq;
}
}
+static int cmp_edges_base(const edge_t *e1, const edge_t *e2)
+{
+ long nr1 = get_irn_node_nr(e1->block);
+ long nr2 = get_irn_node_nr(e2->block);
+ if (nr1 < nr2) {
+ return 1;
+ } else if (nr1 > nr2) {
+ return -1;
+ } else {
+ if (e1->pos < e2->pos) {
+ return 1;
+ } else if (e1->pos > e2->pos) {
+ return -1;
+ } else {
+ return 0;
+ }
+ }
+}
+
static int cmp_edges(const void *d1, const void *d2)
{
const edge_t *e1 = (const edge_t*)d1;
const edge_t *e2 = (const edge_t*)d2;
-
- return QSORT_CMP(e2->execfreq, e1->execfreq);
+ double freq1 = e1->execfreq;
+ double freq2 = e2->execfreq;
+ if (freq1 < freq2) {
+ return 1;
+ } else if (freq1 > freq2) {
+ return -1;
+ } else {
+ return cmp_edges_base(e1, e2);
+ }
}
static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
{
- const edge_t *e1 = (const edge_t*)d1;
- const edge_t *e2 = (const edge_t*)d2;
- /* reverse sorting as penalties are negative */
- return QSORT_CMP(e1->outedge_penalty_freq, e2->outedge_penalty_freq);
+ const edge_t *e1 = (const edge_t*)d1;
+ const edge_t *e2 = (const edge_t*)d2;
+ double pen1 = e1->outedge_penalty_freq;
+ double pen2 = e2->outedge_penalty_freq;
+ if (pen1 > pen2) {
+ return 1;
+ } else if (pen1 < pen2) {
+ return -1;
+ } else {
+ return cmp_edges_base(e1, e2);
+ }
}
static void clear_loop_links(ir_loop *loop)
continue;
pred_block = get_Block_cfgpred_block(block, pos);
- entry = (blocksched_entry_t*)get_irn_link(block);
- pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
+ entry = get_blocksched_entry(block);
+ pred_entry = get_blocksched_entry(pred_block);
if (pred_entry->next != NULL || entry->prev != NULL)
continue;
continue;
pred_block = get_Block_cfgpred_block(block, pos);
- entry = (blocksched_entry_t*)get_irn_link(block);
- pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
+ entry = get_blocksched_entry(block);
+ pred_entry = get_blocksched_entry(pred_block);
if (pred_entry->next != NULL || entry->prev != NULL)
continue;
continue;
pred_block = get_Block_cfgpred_block(block, pos);
- entry = (blocksched_entry_t*)get_irn_link(block);
- pred_entry = (blocksched_entry_t*)get_irn_link(pred_block);
+ entry = get_blocksched_entry(block);
+ pred_entry = get_blocksched_entry(pred_block);
/* is 1 of the blocks already attached to another block? */
if (pred_entry->next != NULL || entry->prev != NULL)
ir_node *block = entry->block;
ir_node *succ = NULL;
blocksched_entry_t *succ_entry;
- const ir_edge_t *edge;
- double best_succ_execfreq;
+ double best_succ_execfreq;
if (irn_visited_else_mark(block))
return;
/* we only need to put the first of a series of already connected
* blocks into the worklist */
- succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
+ succ_entry = get_blocksched_entry(succ_block);
while (succ_entry->prev != NULL) {
/* break cycles... */
if (succ_entry->prev->block == succ_block) {
foreach_block_succ(block, edge) {
ir_node *succ_block = get_edge_src_irn(edge);
- double execfreq;
if (irn_visited(succ_block))
continue;
- succ_entry = (blocksched_entry_t*)get_irn_link(succ_block);
+ succ_entry = get_blocksched_entry(succ_block);
if (succ_entry->prev != NULL)
continue;
- execfreq = get_block_execfreq(env->execfreqs, succ_block);
+ double execfreq = get_block_execfreq(succ_block);
if (execfreq > best_succ_execfreq) {
best_succ_execfreq = execfreq;
succ = succ_block;
} while (irn_visited(succ));
}
- succ_entry = (blocksched_entry_t*)get_irn_link(succ);
+ succ_entry = get_blocksched_entry(succ);
entry->next = succ_entry;
succ_entry->prev = entry;
{
ir_graph *irg = env->irg;
ir_node *startblock = get_irg_start_block(irg);
- blocksched_entry_t *entry = (blocksched_entry_t*)get_irn_link(startblock);
+ blocksched_entry_t *entry = get_blocksched_entry(startblock);
ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
inc_irg_visited(irg);
return block_list;
}
-static ir_node **create_block_schedule_greedy(ir_graph *irg, ir_exec_freq *execfreqs)
+static ir_node **create_block_schedule_greedy(ir_graph *irg)
{
blocksched_env_t env;
- struct obstack obst;
blocksched_entry_t *start_entry;
ir_node **block_list;
- obstack_init(&obst);
-
env.irg = irg;
- env.obst = &obst;
- env.execfreqs = execfreqs;
env.edges = NEW_ARR_F(edge_t, 0);
env.worklist = NULL;
env.blockcount = 0;
+ obstack_init(&env.obst);
assure_loopinfo(irg);
be_get_be_obst(irg));
DEL_ARR_F(env.edges);
- obstack_free(&obst, NULL);
+ obstack_free(&env.obst, NULL);
return block_list;
}
static void collect_egde_frequency_ilp(ir_node *block, void *data)
{
- blocksched_ilp_env_t *env = data;
+ blocksched_ilp_env_t *env = (blocksched_ilp_env_t*)data;
ir_graph *irg = env->env.irg;
ir_node *startblock = get_irg_start_block(irg);
int arity;
- lpp_cst_t cst;
char name[64];
int out_count;
blocksched_ilp_entry_t *entry;
snprintf(name, sizeof(name), "block_out_constr_%ld", get_irn_node_nr(block));
out_count = get_irn_n_edges_kind(block, EDGE_KIND_BLOCK);
- entry = OALLOC(env->env.obst, blocksched_ilp_entry_t);
+ entry = OALLOC(&env->env.obst, blocksched_ilp_entry_t);
entry->block = block;
entry->next = NULL;
entry->prev = NULL;
arity = get_irn_arity(block);
if (arity == 1) {
- double execfreq = get_block_execfreq(env->env.execfreqs, block);
+ double execfreq = get_block_execfreq(block);
add_ilp_edge(block, 0, execfreq, env);
}
else {
int i;
+ int cst_idx;
snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
- cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1);
+ cst_idx = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1);
for (i = 0; i < arity; ++i) {
double execfreq;
ilp_edge_t *edge;
ir_node *pred_block = get_Block_cfgpred_block(block, i);
- execfreq = get_block_execfreq(env->env.execfreqs, pred_block);
+ execfreq = get_block_execfreq(pred_block);
edgenum = add_ilp_edge(block, i, execfreq, env);
edge = &env->ilpedges[edgenum];
- lpp_set_factor_fast(env->lpp, cst, edge->ilpvar, 1.0);
+ lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
}
}
}
+static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
+{
+ return (blocksched_ilp_entry_t*)get_irn_link(block);
+}
static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
{
int edge_count = ARR_LEN(env->ilpedges);
- be_options_t *options = be_get_irg_options(env->env.irg);
int i;
/* complete out constraints */
continue;
pred = get_Block_cfgpred_block(block, edge->pos);
- entry = get_irn_link(pred);
+ entry = get_blocksched_ilp_entry(pred);
DB((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);
}
- lpp_solve_net(env->lpp, options->ilp_server, options->ilp_solver);
+ lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
assert(lpp_is_sol_valid(env->lpp));
/* Apply results to edges */
continue;
pred = get_Block_cfgpred_block(block, edge->pos);
- entry = get_irn_link(block);
- pred_entry = get_irn_link(pred);
+ entry = get_blocksched_entry(block);
+ pred_entry = get_blocksched_entry(pred);
assert(entry->prev == NULL && pred_entry->next == NULL);
entry->prev = pred_entry;
}
}
-static ir_node **create_block_schedule_ilp(ir_graph *irg, ir_exec_freq *execfreqs)
+static ir_node **create_block_schedule_ilp(ir_graph *irg)
{
blocksched_ilp_env_t env;
- struct obstack obst;
blocksched_entry_t *start_entry;
ir_node **block_list;
- obstack_init(&obst);
-
env.env.irg = irg;
- env.env.obst = &obst;
- env.env.execfreqs = execfreqs;
env.env.worklist = NULL;
env.env.blockcount = 0;
env.ilpedges = NEW_ARR_F(ilp_edge_t, 0);
+ obstack_init(&env.env.obst);
env.lpp = lpp_new("blockschedule", lpp_minimize);
lpp_set_time_limit(env.lpp, 20);
DEL_ARR_F(env.ilpedges);
lpp_free(env.lpp);
- obstack_free(&obst, NULL);
+ obstack_free(&env.env.obst, NULL);
return block_list;
}
ir_node **be_create_block_schedule(ir_graph *irg)
{
- ir_exec_freq *execfreqs = be_get_irg_exec_freq(irg);
-
switch (algo) {
case BLOCKSCHED_GREEDY:
case BLOCKSCHED_NAIV:
- return create_block_schedule_greedy(irg, execfreqs);
+ return create_block_schedule_greedy(irg);
case BLOCKSCHED_ILP:
- return create_block_schedule_ilp(irg, execfreqs);
+ return create_block_schedule_ilp(irg);
}
panic("unknown blocksched algo");
projects / libfirm / blobdiff