{
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)
unsigned version;
} global_end_state_t;
-static block_end_state_t *get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
+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 unsigned get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
{
unsigned i;
for (i = 0; i < state->gauge; ++i) {
block_end_state_t *bei = &state->end_info[i];
if (bei->bl == bl && bei->irn == irn)
- return bei;
+ return i;
}
{
block_info_t *bi = get_block_info(bl);
block_end_state_t *curr;
+ i = state->gauge;
+
/* make sure we have room in the array */
ARR_EXTO(block_end_state_t, state->end_info, (int) state->gauge);
curr->end_state = workset_clone(state->env, &state->obst, bi->ws_end);
curr->costs = -1.0;
++state->gauge;
- return curr;
+ return 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);
+ unsigned bes_index = get_block_end_state(ges, bl, irn);
+ block_end_state_t *bes = &ges->end_info[bes_index];
workset_t *end = bes->end_state;
block_info_t *bi = get_block_info(bl);
int n_regs = bi->bel->n_regs;
}
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 bring_in = HUGE_VAL;
+
+ /* allocate a slot before recursively descending. */
+ end->vals[slot].irn = irn;
+ end->vals[slot].version = ges->version;
+ end->len = MAX(end->len, slot + 1);
+
+ /* look if we can bring the value in. */
+ if (bi->pressure < n_regs) {
+ double new_limit = MIN(reload_here, limit);
+ bring_in = can_bring_in(ges, bl, irn, new_limit, level + 1);
+ }
+ /*
+ * re-read the bes descriptor since meanwhile, the
+ * array could have been displaced by recursive calls
+ */
+ assert(bes_index < ges->gauge);
+ bes = &ges->end_info[bes_index];
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;
+ DBG((dbg, DBG_GLOBAL, "\t%2Ddoing a reload %p\n", level, bes));
} 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);
- } else {
- ges->gauge -= 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)
{
+ belady_env_t *env = ges->env;
double glob_costs = HUGE_VAL;
- DBG((dbg, DBG_GLOBAL, "\t%2Dcan bring in for %+F at block %+F\n", level, irn, bl));
+ DBG((dbg, DBG_GLOBAL, "\t%2Dcan bring in (max %f) for %+F at block %+F\n", level, limit, irn, bl));
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 = is_local_phi(bl, irn) ? get_irn_n(irn, i) : irn;
- double c = can_make_available_at_end(ges, pr, op, level + 1);
+ double c;
- if (c >= HUGE_VAL) {
- ges->gauge = gauge_begin;
+ /*
+ * there might by unknwons as operands of phis in that case
+ * we set the costs to zero, since they won't get spilled.
+ */
+ if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, op))
+ c = can_make_available_at_end(ges, pr, op, limit - glob_costs, level + 1);
+ else
+ c = 0.0;
+
+ glob_costs += c;
+
+ if (glob_costs >= limit) {
glob_costs = HUGE_VAL;
+ trans_rollback(ges, &rb);
goto end;
}
-
- glob_costs += c;
}
}
block_info_t *bi = get_block_info(bes->bl);
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));
+ DBG((dbg, DBG_GLOBAL, "\t\t%+F in %+F, cost: %f through: %d, rel: %d %p\n",
+ bes->irn, bes->bl, bes->costs, bes->live_through, bes->reload_at_end, bes));
/* insert the reload if the val was reloaded at the block's end */
if (bes->reload_at_end) {
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 {
projects / libfirm / blobdiff