* Copyright (C) 2005 Universitaet Karlsruhe
* Released under the GPL
*/
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifdef WITH_ILP
+
#include <math.h>
#include "hashptr.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "ircons_t.h"
+#include "irloop_t.h"
#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
#include "benode_t.h"
#include "beutil.h"
#include "bespillilp.h"
+#include "bespill.h"
-#define BIGM 1000.0
+#include "bechordal_t.h"
+
+#define BIGM 100000.0
#define MAX(a,b) ((a) > (b) ? (a) : (b))
-#define DBG_LEVEL SET_LEVEL_3
+#define DBG_LEVEL SET_LEVEL_0 // 3
#define DUMP_SOLUTION
#define DUMP_ILP
-#undef DUMP_STATS
+#define DUMP_STATS
#undef SOLVE_LOCAL
#define LPP_SERVER "i44pc52"
} spill_stat_t;
typedef struct _spill_ilp_t {
+ spill_stat_t stats;
const arch_register_class_t *cls;
- const be_main_session_env_t *session;
+ const be_chordal_env_t *chordal_env;
firm_dbg_module_t *dbg;
lpp_t *lpp;
set *irn_use_heads;
} first_use_t;
+/**
+ * Get weight for spill/reload costs
+ * Actually computed with loop depth.
+ * @param irn The location where to check for the weights.
+ * @return The weights at this points.
+ */
+static double get_weight(const ir_node *irn)
+{
+ ir_loop *loop = get_irn_loop((ir_node *) irn);
+ int res = 1;
+
+ if(loop) {
+ int depth = get_loop_depth(loop);
+ res += depth * depth;
+ }
+
+ return res;
+}
+
static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
{
- return arch_irn_has_reg_class(si->session->main_env->arch_env,
- irn, arch_pos_make_out(0), si->cls);
+ return chordal_has_class(si->chordal_env, irn);
}
static int cmp_live_range(const void *a, const void *b, size_t n)
static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
{
int i, n;
- const arch_env_t *arch_env = si->session->main_env->arch_env;
+ const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
if(is_new) {
char buf[128];
+ double cost = 0.0;
+
+ if(pos >= 0)
+ cost = get_weight(user) * COST_LOAD;
+
ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
- res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0);
+ res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, cost);
}
memset(&iuh, 0, sizeof(iuh));
if(has_reg_class(si, op)) {
DBG((si->dbg, LEVEL_2, " arg %+F\n", op));
relevant_args++;
+
/* arguments must not be spilled */
if(pset_find_ptr(cand, op))
pset_remove_ptr(cand, op);
live_range_t *op_lr = get_live_range(si, op, irn, i);
set_irn_link(op, op_lr);
-// /*
-// * The operand is reloaded at its usage, so it must not occur
-// * in the constraint which determines which values live at the
-// * instruction must reside in memory.
-// */
-// if(must_be_in_mem > 0) {
-// DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
-// lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
-// }
+#if 0
+ /*
+ * The operand is reloaded at its usage, so it must not occur
+ * in the constraint which determines which values live at the
+ * instruction must reside in memory.
+ */
+ if(must_be_in_mem > 0) {
+ DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
+ lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
+ }
+#endif
/*
* Check, if the node is a rematerializable node and
live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1);
edge_reload_t *edge = obstack_alloc(si->obst, sizeof(edge[0]));
- ir_snprintf(buf, sizeof(buf), "edge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn);
- edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD);
+ ir_snprintf(buf, sizeof(buf), "edge_b%N_p%N_i%N", bl, pred_bl, end_node);
+ edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, get_weight(pred_bl) * COST_LOAD);
edge->bl = bl;
edge->irn = end_node;
edge->pos = i;
+ edge->next = si->edges;
+ si->edges = edge;
- ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn);
+ ir_snprintf(buf, sizeof(buf), "cedge_b%N_p%N_i%N", bl, pred_bl, end_node);
cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
*/
static void add_store_costs(spill_ilp_t *si)
{
- char buf[64];
- irn_use_head_t *uh;
- double costs = si->enable_store ? COST_STORE : 0.0;
+ if(si->enable_store) {
+ char buf[64];
+ irn_use_head_t *uh;
- for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
- int cst;
- live_range_t *lr;
+ for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
+ int cst;
+ live_range_t *lr;
- ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
- cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+ ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
+ cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
- ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
- uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs);
- lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
+ ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
+ uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary,
+ get_weight(uh->irn) * COST_STORE);
+ lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
- list_for_each_entry(live_range_t, lr, &uh->head, list)
- lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
+ list_for_each_entry(live_range_t, lr, &uh->head, list)
+ lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
+ }
}
}
for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
live_range_t *lr;
+ si->stats.n_spills += !is_zero(lpp_get_var_sol(si->lpp, uh->spill_var));
+
/* Go through all live ranges of the node. */
list_for_each_entry(live_range_t, lr, &uh->head, list) {
- if(is_spilled(si, lr) && !is_end_of_block_use(lr))
+ if(is_spilled(si, lr) && !is_end_of_block_use(lr)) {
+ DBG((si->dbg, LEVEL_2, "%+F: inserting reload at user %+F\n",
+ lr->irn, lr->user));
be_add_reload(si->senv, lr->irn, lr->user);
+ si->stats.n_reloads += 1;
+ }
}
}
for(edge = si->edges; edge; edge = edge->next) {
- if(!is_zero(edge->in_mem_var))
+ if(!is_zero(lpp_get_var_sol(si->lpp, edge->in_mem_var))) {
+ DBG((si->dbg, LEVEL_2, "%+F: insert reload on edge %d from %+F\n",
+ edge->irn, edge->pos, edge->bl));
be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
+ si->stats.n_reloads += 1;
+ }
}
be_insert_spills_reloads(si->senv, NULL);
}
-void be_spill_ilp(const be_main_session_env_t *session_env,
- const arch_register_class_t *cls)
+void be_spill_ilp(const be_chordal_env_t *chordal_env)
{
char problem_name[256];
struct obstack obst;
spill_ilp_t si;
- ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
+ ir_snprintf(problem_name, sizeof(problem_name), "%F_%s",
+ chordal_env->irg, chordal_env->cls->name);
obstack_init(&obst);
- si.session = session_env;
+ memset(&si.stats, 0, sizeof(si.stats));
+ si.chordal_env = chordal_env;
si.obst = &obst;
- si.dbg = firm_dbg_register("be.ra.spillilp");
- si.senv = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si);
- si.cls = cls;
+ si.senv = be_new_spill_env(si.dbg, chordal_env, is_mem_phi, &si);
+ si.cls = chordal_env->cls;
si.lpp = new_lpp(problem_name, lpp_minimize);
si.irn_use_heads = new_set(cmp_irn_use_head, 4096);
si.live_ranges = new_set(cmp_live_range, 16384);
si.first_uses = new_set(cmp_first_use, 4096);
si.edges = NULL;
si.enable_remat = 0;
- si.enable_store = 0;
+ si.enable_store = 1;
+ FIRM_DBG_REGISTER(si.dbg, "be.ra.spillilp");
firm_dbg_set_mask(si.dbg, DBG_LEVEL);
- irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
+ irg_block_walk_graph(chordal_env->irg, process_block, NULL, &si);
if(si.enable_store)
add_store_costs(&si);
FILE *f;
char buf[256];
- ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
+ ir_snprintf(buf, sizeof(buf), "%s-spill.ilp", problem_name);
if((f = fopen(buf, "wt")) != NULL) {
lpp_dump_plain(si.lpp, f);
fclose(f);
}
#endif
- DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
+ DBG((si.dbg, LEVEL_1, "%F\n", chordal_env->irg));
#ifdef SOLVE_LOCAL
lpp_solve_cplex(si.lpp);
#else
FILE *f;
char buf[256];
- ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
+ ir_snprintf(buf, sizeof(buf), "%s-spill.sol", problem_name);
if((f = fopen(buf, "wt")) != NULL) {
int i;
for(i = 0; i < si.lpp->var_next; ++i) {
#ifdef DUMP_STATS
{
+ char buf[256];
FILE *f;
ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
- fprintf(f, "%20s: %d\n", "spills", si->stats.n_spills);
- fprintf(f, "%20s: %d\n", "reloads", si->stats.n_reloads);
- fprintf(f, "%20s: %d\n", "remats", si->stats.n_remat);
+ fprintf(f, "%20s: %d\n", "spills", si.stats.n_spills);
+ fprintf(f, "%20s: %d\n", "reloads", si.stats.n_reloads);
+ fprintf(f, "%20s: %d\n", "remats", si.stats.n_remat);
fclose(f);
}
}
free_lpp(si.lpp);
obstack_free(&obst, NULL);
}
+
+#else /* WITH_ILP */
+
+static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
+}
+
+#endif /* WITH_ILP */
projects / libfirm / blobdiff