#define DBG_WORKSET 128
#define DBG_GLOBAL 256
-#define DEAD UINT_MAX
+#define DEAD UINT_MAX
+#define LIVE_END (DEAD-1)
+
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
/**
unsigned time; /**< A use time (see beuses.h). */
unsigned version; /**< That is used in the global pass below.
For usage see the comments below.
- In the local belady pass, this is not
- important. */
+ In the local belady pass, this is not important. */
} loc_t;
typedef struct _workset_t {
{
const loc_t *p = a;
const loc_t *q = b;
- return (int) p->time - (int) q->time;
+ return (p->time > q->time) - (p->time < q->time);
}
static INLINE void workset_print(const workset_t *w)
phase_set_irn_data(&bi->next_uses, irn, use->next);
}
+static INLINE unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, int is_usage)
+{
+ belady_env_t *env = bi->bel;
+ next_use_t *use = get_current_use(bi, irn);
+ int curr_step = sched_get_time_step(env->instr);
+ int flags = arch_irn_get_flags(env->arch, irn);
+
+ assert(!(flags & arch_irn_flags_ignore));
+
+ /* We have to keep nonspillable nodes in the workingset */
+ if(flags & arch_irn_flags_dont_spill)
+ return 0;
+
+ if (!is_usage && use && use->step == curr_step)
+ use = use->next;
+
+ if (use) {
+ assert(use->step >= curr_step);
+ return use->step - curr_step;
+ }
-static INLINE int is_local_phi(const ir_node *irn, const ir_node *bl)
+ return be_is_live_end(env->lv, bi->bl, irn) ? LIVE_END : DEAD;
+}
+
+static INLINE int is_local_phi(const ir_node *bl, const ir_node *irn)
{
return is_Phi(irn) && get_nodes_block(irn) == bl;
}
*/
static INLINE int is_transport_in(const ir_node *bl, const ir_node *irn)
{
- return is_local_phi(irn, bl) || get_nodes_block(irn) != bl;
+ return is_local_phi(bl, irn) || get_nodes_block(irn) != bl;
}
/**
assert(use);
assert(sched_get_time_step(env->instr) == use->step);
if (is_transport_in(bi->bl, val) && use->is_first_use) {
- DBG((dbg, DBG_DECIDE, "entrance node %+F, capacity %d:\n", val, bi->pressure));
+ DBG((dbg, DBG_DECIDE, "entrance node %+F, pressure %d:\n", val, bi->pressure));
if (bi->pressure < env->n_regs) {
workset_insert(env, bi->entrance_reg, val);
insert_reload = 0;
be_add_reload(env->senv, val, env->instr, env->cls, 1);
}
}
- }
- else {
+ } else {
assert(is_usage || "Defined value already in workset?!?");
DBG((dbg, DBG_DECIDE, " skip %+F\n", val));
}
/* Only make more free room if we do not have enough */
if (len > max_allowed) {
- int curr_step = sched_get_time_step(env->instr);
+ // int curr_step = sched_get_time_step(env->instr);
DBG((dbg, DBG_DECIDE, " disposing %d values\n", len - max_allowed));
/* get current next-use distance */
for (i = 0; i < ws->len; ++i) {
- ir_node *val = workset_get_val(ws, i);
- next_use_t *use = phase_get_irn_data(&bi->next_uses, val);
- assert(use == NULL || use->step >= curr_step);
-
- if (!is_usage && use)
- use = use->next;
-
- workset_set_time(ws, i, use ? (unsigned) (use->step - curr_step) : DEAD);
+ ir_node *val = workset_get_val(ws, i);
+ unsigned dist = get_curr_distance(bi, val, is_usage);
+ workset_set_time(ws, i, dist);
}
/* sort entries by increasing nextuse-distance*/
static void belady(ir_node *block, void *data) {
belady_env_t *env = data;
block_info_t *block_info = new_block_info(env, block);
+ void *obst_state = obstack_base(&env->ob);
workset_t *new_vals;
ir_node *irn;
}
phase_free(&block_info->next_uses);
+ obstack_free(&env->ob, obst_state);
/* Remember end-workset for this block */
block_info->ws_end = workset_clone(env, &env->ob, env->ws);
DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block));
workset_foreach(block_info->ws_end, irn, iter)
DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(block_info->ws_end, iter)));
+ DBG((dbg, DBG_WSETS, "Max pressure in block: %d\n", block_info->pressure));
}
/*
const ir_node * const *q = b;
block_info_t *pi = get_block_info(*p);
block_info_t *qi = get_block_info(*q);
- return qi->exec_freq - pi->exec_freq;
+ double diff = qi->exec_freq - pi->exec_freq;
+ return (diff > 0) - (diff < 0);
}
typedef struct _block_end_state_t {
typedef struct _global_end_state_t {
belady_env_t *env;
- bitset_t *failed_phis;
+ bitset_t *succ_phis;
struct obstack obst;
block_end_state_t *end_info;
unsigned gauge;
unsigned version;
} global_end_state_t;
+typedef struct {
+ void *obst_level;
+ unsigned gauge;
+} rollback_info_t;
+
+static INLINE rollback_info_t trans_begin(global_end_state_t *ges)
+{
+ rollback_info_t rb;
+ rb.obst_level = obstack_base(&ges->obst);
+ rb.gauge = ges->gauge;
+ return rb;
+}
+
+static INLINE void trans_rollback(global_end_state_t *ges, rollback_info_t *rb)
+{
+ ges->gauge = rb->gauge;
+ obstack_free(&ges->obst, rb->obst_level);
+}
+
static block_end_state_t *get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
{
unsigned i;
}
}
-static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level);
+static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, double limit, int level);
-static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
+static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, double limit, int level)
{
block_end_state_t *bes = get_block_end_state(ges, bl, irn);
workset_t *end = bes->end_state;
DBG((dbg, DBG_GLOBAL, "\t%2Dthe end set has %d free slots\n",
level, n_regs - len));
slot = len;
- }
- else {
+ } else {
for (i = 0; i < len; ++i)
if (end->vals[i].version < ges->version)
break;
}
if (slot >= 0) {
- int gauge = ges->gauge;
+ rollback_info_t rb = trans_begin(ges);
ir_node *ins_before = block_info_get_last_ins(bi);
double reload_here = be_get_reload_costs(bi->bel->senv, irn, ins_before);
- double bring_in = bi->pressure < n_regs ? can_bring_in(ges, bl, irn, level + 1) : HUGE_VAL;
+ double new_limit = MIN(reload_here, limit);
+ double bring_in = bi->pressure < n_regs ? can_bring_in(ges, bl, irn, new_limit, level + 1) : HUGE_VAL;
DBG((dbg, DBG_GLOBAL, "\t%2Dthere is a free slot. capacity=%d, reload here=%f, bring in=%f\n",
level, n_regs - bi->pressure, reload_here, bring_in));
* the gauge.
*/
if (reload_here <= bring_in) {
- ges->gauge = gauge;
+ trans_rollback(ges, &rb);
bes->costs = reload_here;
bes->reload_at_end = 1;
- }
-
- else {
+ } else {
bes->live_through = 1;
bes->costs = bring_in;
}
end->vals[slot].irn = irn;
end->vals[slot].version = ges->version;
+ end->len = MAX(end->len, slot + 1);
}
}
return bes->costs;
}
-static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
+static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, double limit, int level)
{
double glob_costs = HUGE_VAL;
- int def_block = bl == get_nodes_block(irn);
- int phi = is_Phi(irn);
DBG((dbg, DBG_GLOBAL, "\t%2Dcan bring in for %+F at block %+F\n", level, irn, bl));
- if (phi || !def_block) {
+ if (is_transport_in(bl, irn)) {
int i, n = get_irn_arity(bl);
ir_node **nodes = alloca(get_irn_arity(bl) * sizeof(nodes[0]));
+ rollback_info_t rb = trans_begin(ges);
- int gauge_begin = ges->gauge;
glob_costs = 0.0;
for (i = 0; i < n; ++i) {
ir_node *pr = get_Block_cfgpred_block(bl, i);
- ir_node *op = phi && def_block ? get_irn_n(irn, i) : irn;
- double c = can_make_available_at_end(ges, pr, op, level + 1);
+ ir_node *op = is_local_phi(bl, irn) ? get_irn_n(irn, i) : irn;
+ double c = can_make_available_at_end(ges, pr, op, limit, level + 1);
- if (c >= HUGE_VAL) {
- ges->gauge = gauge_begin;
+ glob_costs += c;
+
+ if (glob_costs >= limit) {
glob_costs = HUGE_VAL;
+ trans_rollback(ges, &rb);
goto end;
}
-
- glob_costs += c;
}
}
for (i = 0; i < ges->gauge; ++i) {
block_end_state_t *bes = &ges->end_info[i];
block_info_t *bi = get_block_info(bes->bl);
- int idx;
+ int idx, end_pressure;
+
+ DBG((dbg, DBG_GLOBAL, "\t\t%+F in %+F, cost %f through: %d, rel: %d\n",
+ bes->irn, bes->bl, bes->costs, bes->live_through, bes->reload_at_end));
/* insert the reload if the val was reloaded at the block's end */
if (bes->reload_at_end) {
DBG((dbg, DBG_GLOBAL, "\t\tadding reload of %+F at end of %+F\n", bes->irn, bes->bl));
}
- /*
- * if the variable is live through the block,
- * update the pressure indicator.
- */
- bi->pressure += bes->live_through;
-
idx = workset_get_index(bes->end_state, bes->irn);
+ if (is_local_phi(bes->bl, bes->irn) && bes->live_through)
+ bitset_add_irn(ges->succ_phis, bes->irn);
+
/*
* set the version number in the workset.
* That will mark this value as fixed in the end set
bes->end_state->vals[idx].version = ges->version;
workset_copy(env, bi->ws_end, bes->end_state);
}
+
+ end_pressure = 0;
+ for (idx = workset_get_length(bes->end_state) - 1; idx >= 0; --idx)
+ if (bes->end_state->vals[idx].version >= ges->version)
+ end_pressure += 1;
+
+ /*
+ * if the variable is live through the block,
+ * update the pressure indicator.
+ */
+ DBG((dbg, DBG_GLOBAL, "\t\told pressure %d, ", bi->pressure));
+
+ bi->pressure = MAX(bi->pressure + bes->live_through, end_pressure);
+
+ DBG((dbg, DBG_GLOBAL, "new pressure: %d, end pressure: %d, end length: %d\n",
+ bi->pressure, end_pressure, workset_get_length(bes->end_state)));
+
}
}
DBG((dbg, DBG_GLOBAL, "\ttrans in var %+F, version %x\n", irn, ges->version));
- bring_in_costs = can_bring_in(ges, block, irn, 1);
+ bring_in_costs = can_bring_in(ges, block, irn, local_costs, 1);
DBG((dbg, DBG_GLOBAL, "\tbring in: %f, local: %f", bring_in_costs, local_costs));
* in a register at the entrance of the block
* or it is too costly, so we have to do the reload locally
*/
- if (bring_in_costs > local_costs) {
-
+ if (bring_in_costs >= local_costs) {
DBG((dbg, DBG_GLOBAL, " -> do local reload\n"));
be_add_reload(env->senv, irn, bi->first_non_in, env->cls, 1);
-
+ } else {
/*
* if the transport-in was a phi (that is actually used in block)
* it will no longer remain and we have to spill it completely.
*/
- if (is_local_phi(irn, block))
- bitset_add_irn(ges->failed_phis, irn);
- }
+ if (is_local_phi(block, irn))
+ bitset_add_irn(ges->succ_phis, irn);
- else {
DBG((dbg, DBG_GLOBAL, " -> do remote reload\n"));
materialize_and_commit_end_state(ges);
}
int i;
obstack_init(&ges.obst);
- ges.gauge = 0;
- ges.env = env;
- ges.version = -1;
- ges.end_info = NEW_ARR_F(block_end_state_t, env->n_blocks);
- ges.failed_phis = bitset_irg_obstack_alloc(&env->ob, env->irg);
+ ges.gauge = 0;
+ ges.env = env;
+ ges.version = -1;
+ ges.end_info = NEW_ARR_F(block_end_state_t, env->n_blocks);
+ ges.succ_phis = bitset_irg_obstack_alloc(&env->ob, env->irg);
/*
* sort the blocks according to execution frequency.
break;
if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)
- && bitset_contains_irn(ges.failed_phis, irn))
+ && !bitset_contains_irn(ges.succ_phis, irn))
be_spill_phi(env->senv, irn);
}
}
+ DEL_ARR_F(ges.end_info);
}
static void collect_blocks(ir_node *bl, void *data)
projects / libfirm / blobdiff