#define DBG_SLOTS 32
#define DBG_TRACE 64
#define DBG_WORKSET 128
-#define DEBUG_LVL 0 //(DBG_START | DBG_DECIDE | DBG_WSETS | DBG_FIX | DBG_SPILL)
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
-typedef struct _workset_t workset_t;
+/**
+ * An association between a node and a point in time.
+ */
+typedef struct _loc_t {
+ ir_node *irn; /**< A node. */
+ unsigned time; /**< A use time (see beuses.h). */
+} loc_t;
+
+typedef struct _workset_t {
+ int len; /**< current length */
+ loc_t vals[0]; /**< inlined array of the values/distances in this working set */
+} workset_t;
typedef struct _belady_env_t {
struct obstack ob;
spill_env_t *senv; /**< see bespill.h */
} belady_env_t;
-struct _workset_t {
- int len; /**< current length */
- loc_t vals[0]; /**< inlined array of the values/distances in this working set */
-};
+static int loc_compare(const void *a, const void *b)
+{
+ const loc_t *p = a;
+ const loc_t *q = b;
+ return p->time - q->time;
+}
void workset_print(const workset_t *w)
{
static INLINE unsigned get_distance(belady_env_t *env, const ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses)
{
int flags = arch_irn_get_flags(env->arch, def);
- unsigned dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses);
+ unsigned dist;
assert(! (flags & arch_irn_flags_ignore));
- /* we have to keep nonspillable nodes in the workingset */
+ /* We have to keep nonspillable nodes in the workingset */
if(flags & arch_irn_flags_dont_spill)
return 0;
+ dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses);
+
+ if(USES_IS_INFINITE(dist))
+ dist = USES_INFINITY;
+
return dist;
}
if (! workset_contains(ws, val)) {
DBG((dbg, DBG_DECIDE, " insert %+F\n", val));
to_insert[demand++] = val;
- if (is_usage)
+ if (is_usage) {
+ DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr));
be_add_reload(env->senv, val, env->instr);
+ }
}
else {
assert(is_usage || "Defined value already in workset?!?");
/* Only make more free room if we do not have enough */
if (len > max_allowed) {
/* get current next-use distance */
- for (i = 0; i < ws->len; ++i)
- workset_set_time(ws, i, get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage));
+ for (i = 0; i < ws->len; ++i) {
+ unsigned dist = get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage);
+ workset_set_time(ws, i, dist);
+ }
/*
FIX for don't spill nodes:
/* irnb is not in memory at the end of pred, so we have to reload it */
DBG((dbg, DBG_FIX, " reload %+F\n", irnb));
+ DBG((dbg, DBG_SPILL, "Reload %+F before %+F,%d\n", irnb, blk, i));
be_add_reload_on_edge(env->senv, irnb, blk, i);
next_value:
belady_env_t env;
FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady");
- //firm_dbg_set_mask(dbg, DBG_START);
+ //firm_dbg_set_mask(dbg, DBG_SPILL);
/* init belady env */
obstack_init(&env.ob);
env.cenv = chordal_env;
env.arch = chordal_env->birg->main_env->arch_env;
env.cls = chordal_env->cls;
- env.n_regs = arch_count_non_ignore_regs(env.arch, env.cls);
+ env.n_regs = env.cls->n_regs - be_put_ignore_regs(chordal_env->birg, chordal_env->cls, NULL);
env.ws = new_workset(&env, &env.ob);
- env.uses = be_begin_uses(chordal_env->irg, chordal_env->lv, chordal_env->birg->main_env->arch_env, env.cls);
+ env.uses = be_begin_uses(chordal_env->irg, chordal_env->exec_freq, chordal_env->lv);
if(spill_env == NULL) {
env.senv = be_new_spill_env(chordal_env);
} else {
}
DEBUG_ONLY(be_set_spill_env_dbg_module(env.senv, dbg);)
- DBG((dbg, LEVEL_1, "running on register class: %s\n", env.cls->name));
-
be_clear_links(chordal_env->irg);
/* Decide which phi nodes will be spilled and place copies for them into the graph */
irg_block_walk_graph(chordal_env->irg, spill_phi_walker, NULL, &env);