#include <lpp/lpp.h>
#include <lpp/lpp_net.h>
+#include <lpp/lpp_cplex.h>
#include "be_t.h"
#include "belive_t.h"
#include "bearch.h"
#include "benode_t.h"
#include "beutil.h"
+#include "bespillilp.h"
#define BIGM 1000.0
#define MAX(a,b) ((a) > (b) ? (a) : (b))
-#define DBG_LEVEL SET_LEVEL_3
+#define DBG_LEVEL SET_LEVEL_4
#define DUMP_SOLUTION
#define DUMP_ILP
+#undef DUMP_STATS
+#undef SOLVE_LOCAL
#define LPP_SERVER "i44pc52"
#define LPP_SOLVER "cplex"
#define is_end_of_block_use(lr) (is_Block((lr)->user))
+/**
+ * Reloads on edges.
+ */
+typedef struct _edge_reload_t {
+ ir_node *irn;
+ ir_node *bl;
+ int pos;
+ int in_mem_var;
+ struct _edge_reload_t *next;
+} edge_reload_t;
+
+typedef struct _spill_stat_t {
+ int n_spills;
+ int n_reloads;
+ int n_remat;
+} spill_stat_t;
+
typedef struct _spill_ilp_t {
- const be_main_session_env_t *session_env;
- const arch_register_class_t *cls;
+ const arch_register_class_t *cls;
+ const be_main_session_env_t *session;
firm_dbg_module_t *dbg;
- lpp_t *lpp;
+ lpp_t *lpp;
set *irn_use_heads;
- set *live_ranges;
- set *spill_ctx;
- pset *remove_phis;
- struct obstack *obst;
+ set *live_ranges;
+ set *first_uses;
+ spill_env_t *senv;
+ edge_reload_t *edges;
+ struct obstack *obst;
int enable_store : 1;
int enable_remat : 1;
} spill_ilp_t;
int is_remat_var;
};
-typedef struct _spill_ctx_t {
- ir_node *spilled; /**< The spilled node. */
- ir_node *user; /**< The node this spill is for. */
- ir_node *spill; /**< The spill itself. */
-} spill_ctx_t;
-
-static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
-{
- return arch_irn_has_reg_class(si->session_env->main_env->arch_env,
- irn, arch_pos_make_out(0), si->cls);
-}
+/*
+ * Associates the first use of a live-in in a block
+ * with its live range.
+ */
+typedef struct _first_use_t {
+ ir_node *bl;
+ ir_node *irn; /**< A value live in at bl. */
+ live_range_t *lr; /**< The live range for the first use of irn in bl. */
+} first_use_t;
-static int register_demand(spill_ilp_t *si, const ir_node *irn)
-{
- const arch_env_t *arch_env = si->session_env->main_env->arch_env;
- int n_in = arch_get_n_operands(arch_env, irn, 0);
- int n_out = arch_get_n_operands(arch_env, irn, -1);
- return MAX(n_in, n_out);
-}
-static int cmp_spill_ctx(const void *a, const void *b, size_t n)
+static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
{
- const spill_ctx_t *p = a;
- const spill_ctx_t *q = b;
- return !(p->user == q->user && p->spilled == q->spilled);
+ return arch_irn_has_reg_class(si->session->main_env->arch_env,
+ irn, arch_pos_make_out(0), si->cls);
}
static int cmp_live_range(const void *a, const void *b, size_t n)
return !(p->irn == q->irn);
}
+static int cmp_first_use(const void *a, const void *b, size_t n)
+{
+ const first_use_t *p = a;
+ const first_use_t *q = b;
+
+ return !(p->irn == q->irn && p->bl == q->bl);
+}
+
+static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
+{
+ first_use_t templ;
+ templ.bl = bl;
+ templ.irn = irn;
+ templ.lr = lr;
+
+ set_insert(si->first_uses, &templ, sizeof(templ),
+ HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
+}
+
+static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
+{
+ first_use_t *res;
+ first_use_t templ;
+ templ.bl = bl;
+ templ.irn = irn;
+
+ res = set_find(si->first_uses, &templ, sizeof(templ),
+ HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
+
+ return res ? res->lr : NULL;
+}
+
/**
* Checks, if a vertain node can be recomputed at a certain position.
* @param si The spill ILP environment.
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_env->main_env->arch_env;
+ const arch_env_t *arch_env = si->session->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) {
return remat;
}
-static spill_ctx_t *get_spill_ctx(spill_ilp_t *si, ir_node *spilled, ir_node *ctx_irn)
-{
- spill_ctx_t templ, *res;
-
- templ.spilled = spilled;
- templ.user = ctx_irn;
- templ.spill = NULL;
-
- res = set_insert(si->spill_ctx, &templ, sizeof(templ),
- HASH_COMBINE(HASH_PTR(spilled), HASH_PTR(ctx_irn)));
-
- return res;
-}
-
static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
{
live_range_t lr, *res;
return res;
}
-static live_range_t *lookup_live_range(const spill_ilp_t *si, ir_node *irn,
- ir_node *user, int pos)
-{
- live_range_t lr;
- unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
-
- lr.user = user;
- lr.irn = irn;
- lr.pos = pos;
- lr.in_mem_var = -1;
-
- return set_find(si->live_ranges, &lr, sizeof(lr), hash);
-}
-
-static void create_block_live_range_sets(ir_node *bl, void *data)
+static ir_node *process_irn(spill_ilp_t *si, pset *live, ir_node *irn, int *demand)
{
- assert(is_Block(bl));
- set_irn_link(bl, pset_new_ptr_default());
-}
-
-static void delete_block_live_range_sets(ir_node *bl, void *data)
-{
- assert(is_Block(bl));
+ int i, n;
+ int relevant_args = 0, results = 0;
- del_pset(get_irn_link(bl));
- set_irn_link(bl, NULL);
-}
+ DBG((si->dbg, LEVEL_1, "at %+F\n", irn));
-#if 0
-static void annotate_live_ranges(ir_node *irn, void *data)
-{
- const ir_edge_t *edge;
+ while(is_Proj(irn)) {
+ if(has_reg_class(si, irn)) {
+ assert(pset_find_ptr(live, irn) && "node must be live");
+ pset_remove_ptr(live, irn);
+ results++;
+ }
- foreach_out_edge(irn, edge) {
- pset *lr_set;
+ DBG((si->dbg, LEVEL_1, "skipped proj %+F\n", irn));
+ irn = sched_prev(irn);
+ }
- ir_node *user = edge->use;
- int pos = edge->pos;
- ir_node *bl = get_nodes_block(user);
+ DBG((si->dbg, LEVEL_1, "\tlanded at irn %+F\n", irn));
- if(is_Phi(user))
- bl = get_Block_cfgpred_block(bl, pos);
+ if(results > 0)
+ assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
- lr_set = get_irn_link(bl);
+ if(has_reg_class(si, irn)) {
+ assert( pset_find_ptr(live, irn) && "node must be live");
+ pset_remove_ptr(live, irn);
+ results = 1;
+ }
+ for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
+ ir_node *op = get_irn_n(irn, i);
+ if(has_reg_class(si, op) && !pset_find_ptr(live, op)) {
+ relevant_args++;
+ DBG((si->dbg, LEVEL_1, "\trelevant arg %+F\n", op));
+ }
}
-}
-#endif
+ *demand = MAX(results, relevant_args);
+ DBG((si->dbg, LEVEL_1, "\tdemand: %d\n", *demand));
+ return irn;
+}
static void process_block(ir_node *bl, void *data)
{
}
}
- sched_foreach_reverse(bl, irn) {
+ for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
ir_node *l;
int cst;
int demand;
if(is_Phi(irn))
break;
+#if 0
if(has_reg_class(si, irn))
pset_remove_ptr(live, irn);
- demand = register_demand(si, irn);
+ demand = register_demand(si, live, irn);
+ n_live = pset_count(live);
+#endif
+
+ irn = process_irn(si, live, irn, &demand);
n_live = pset_count(live);
/*
* So there are n_regs - demand registers available to store values
* which are not used at this label. The rest must reside in memory.
*/
- must_be_in_mem = MAX(n_live - (n_regs - demand), 0);
+ must_be_in_mem = MAX(n_live + demand - n_regs, 0);
+
+ DBG((si->dbg, LEVEL_1, "%+F: demand: %d, live: %d, in mem: %d\n",
+ irn, demand, n_live, must_be_in_mem));
if(must_be_in_mem > 0) {
* The constraint limiting the pressure at this label to
* the number of free registers.
*/
- ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step);
+ ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
for(l = pset_first(live); l; l = pset_next(live)) {
* in the constraint which determines which values live at the
* instruction must reside in memory.
*/
- if(must_be_in_mem > 0) {
+ if(must_be_in_mem > 0)
lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
- }
/*
* Check, if the node is a rematerializable node and
int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
int cst;
+ /* Deprecated: Can be done with the first uses map */
if(is_phi)
lr->use_head->closest_use = lr;
+ /*
+ * Remind the liverange of the first use of a live (or phi) in the
+ * current block.
+ */
+ add_first_use(si, bl, irn, lr);
+
assert(has_reg_class(si, irn));
assert(is_Phi(irn) || is_live_in(bl, irn));
-#if 0
- ir_snprintf(buf, sizeof(buf), "c%s_%N_%N", (is_phi ? "phi" : "li"), irn, bl);
- cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
- lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -n_preds);
-
for(i = 0; i < n_preds; ++i) {
ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn;
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]));
- lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
- }
-#endif
+ 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);
+ edge->bl = bl;
+ edge->irn = end_node;
+ edge->pos = i;
- for(i = 0; i < n_preds; ++i) {
- ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
- ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn;
- live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1);
- ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i);
- cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
+ ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N",
+ bl, pred_bl, end_node, op_lr->irn);
+ 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);
+ lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
}
}
return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
}
-static ir_node *spill_irn(spill_ilp_t *si, ir_node *irn, ir_node *ctx_irn)
-{
- const be_node_factory_t *fact = si->session_env->main_env->node_factory;
- const arch_env_t *arch_env = si->session_env->main_env->arch_env;
- spill_ctx_t *ctx;
-
- ctx = get_spill_ctx(si, irn, ctx_irn);
- if(ctx->spill)
- return ctx->spill;
-
- ctx->spill = be_spill(fact, arch_env, irn);
- return ctx->spill;
-}
-
-static ir_node *spill_phi(spill_ilp_t *si, ir_node *phi, ir_node *ctx_irn, pset *rem_phis)
-{
- int i, n;
- ir_mode *mode = get_irn_mode(phi);
- ir_node **ins;
- ir_node *bl = get_nodes_block(phi);
- ir_graph *irg = get_irn_irg(bl);
- spill_ctx_t *ctx;
-
- assert(is_Phi(phi));
-
- ctx = get_spill_ctx(si, phi, ctx_irn);
- if(ctx->spill)
- return ctx->spill;
-
- n = get_irn_arity(phi);
- ins = malloc(n * sizeof(ins[0]));
-
- for(i = 0; i < n; ++i)
- ins[i] = new_r_Unknown(irg, mode_M);
-
- ctx->spill = new_r_Phi(irg, bl, n, ins, mode_M);
- free(ins);
-
- for(i = 0; i < n; ++i) {
- ir_node *arg = get_irn_n(phi, i);
- ir_node *res;
-
- if(is_Phi(arg))
- res = spill_phi(si, arg, ctx_irn, rem_phis);
- else
- res = spill_irn(si, arg, ctx_irn);
-
- set_irn_n(ctx->spill, i, res);
- }
-
- return ctx->spill;
-}
-
-static ir_node *spill_live_range(spill_ilp_t *si, live_range_t *lr, pset *rem_phis)
-{
- const live_range_t *closest = lr->use_head->closest_use;
-
- if(is_Phi(lr->irn) && closest && is_spilled(si, closest))
- return spill_phi(si, lr->irn, lr->irn, rem_phis);
- else
- return spill_irn(si, lr->irn, lr->irn);
-}
-
-
static void writeback_results(spill_ilp_t *si)
{
- const be_node_factory_t *fact = si->session_env->main_env->node_factory;
- const arch_env_t *arch_env = si->session_env->main_env->arch_env;
- ir_node *irn;
irn_use_head_t *uh;
- pset *rem_phis = pset_new_ptr_default();
+ edge_reload_t *edge;
+ pset *mem_phis = pset_new_ptr_default();
+ /* Put all completely spilled phis into the mem_phis set */
for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
if(is_Phi(uh->irn) && is_spilled(si, uh->closest_use))
- pset_insert_ptr(rem_phis, uh->irn);
+ pset_insert_ptr(mem_phis, uh->irn);
}
/* Look at each node and examine the usages. */
for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
- live_range_t *lr;
- ir_node **reloads;
-
- int n_reloads = 0;
- ir_node *irn = uh->irn;
- ir_mode *mode = get_irn_mode(irn);
+ live_range_t *lr;
/* Go through all live ranges of the node. */
- list_for_each_entry(live_range_t, lr, &uh->head, list) {
- int spilled = is_spilled(si, lr);
- // int rematd = !is_zero(lpp_get_var_sol(si->lpp, lr->is_remat_var));
-
- if(spilled && !is_end_of_block_use(lr)) {
- ir_node *bl = get_nodes_block(lr->user);
- ir_node *spill = spill_live_range(si, lr, rem_phis);
- ir_node *reload = new_Reload(fact, si->cls,
- si->session_env->irg, bl, mode, spill);
-
- obstack_ptr_grow(si->obst, reload);
- n_reloads++;
-
- sched_add_before(lr->user, reload);
- }
-
- }
-
- if(n_reloads > 0) {
- reloads = obstack_finish(si->obst);
- be_introduce_copies_ignore(si->session_env->dom_front, irn,
- n_reloads, reloads, rem_phis);
- obstack_free(si->obst, reloads);
+ list_for_each_entry(live_range_t, lr, &uh->head, list) {
+ if(is_spilled(si, lr) && !is_end_of_block_use(lr))
+ be_add_spill(si->senv, lr->irn, lr->user);
}
- }
-
- for(irn = pset_first(rem_phis); irn; irn = pset_next(rem_phis)) {
- int i, n;
+ }
- for(i = 0, n = get_irn_arity(irn); i < n; ++i)
- set_irn_n(irn, i, new_r_Bad(si->session_env->irg));
- sched_remove(irn);
+ for(edge = si->edges; edge; edge = edge->next) {
+ if(!is_zero(edge->in_mem_var))
+ be_add_spill_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
}
+
+ be_insert_spills_reloads(si->senv, mem_phis, NULL);
+ del_pset(mem_phis);
}
void be_spill_ilp(const be_main_session_env_t *session_env,
const arch_register_class_t *cls)
{
- char buf[256];
char problem_name[256];
- struct obstack obst;
- spill_ilp_t si;
+ struct obstack obst;
+ spill_ilp_t si;
ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
- obstack_init(&obst);
- si.obst = &obst;
- si.dbg = firm_dbg_register("be.ra.spillilp");
- si.session_env = session_env;
- si.cls = 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.spill_ctx = new_set(cmp_spill_ctx, 4096);
- si.enable_remat = 1;
- si.enable_store = 0;
+ obstack_init(&obst);
+ si.session = session_env;
+ si.obst = &obst;
+ si.dbg = firm_dbg_register("be.ra.spillilp");
+ si.senv = be_new_spill_env(si.dbg, session_env, cls);
+ si.cls = 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;
firm_dbg_set_mask(si.dbg, DBG_LEVEL);
irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
#ifdef DUMP_ILP
{
FILE *f;
+ char buf[256];
ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
if((f = fopen(buf, "wt")) != NULL) {
#endif
DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
+#ifdef SOLVE_LOCAL
+ lpp_solve_cplex(si.lpp);
+#else
lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
- assert(lpp_is_sol_valid(si.lpp) && "ILP not feasible");
-
+#endif
assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
#ifdef DUMP_SOLUTION
{
FILE *f;
+ char buf[256];
ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
if((f = fopen(buf, "wt")) != NULL) {
int i;
for(i = 0; i < si.lpp->var_next; ++i) {
lpp_name_t *name = si.lpp->vars[i];
- fprintf(f, "%10s %4d %10f\n", name->name, name->nr, name->value);
+ fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
}
fclose(f);
}
}
#endif
- writeback_results(&si);
+
+ // writeback_results(&si);
+
+#ifdef DUMP_STATS
+ {
+ FILE *f;
+
+ ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
+ if((f = fopen(buf, "wt")) != NULL) {
+ fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
+ 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);
+ fclose(f);
+ }
+ }
+#endif
del_set(si.irn_use_heads);
del_set(si.live_ranges);
projects / libfirm / blobdiff