#include "iredges.h"
#include "execfreq.h"
#include "irvrfy.h"
+#include "irbackedge_t.h"
#include <lpp/lpp.h>
#include <lpp/mps.h>
#include "bespillremat.h"
#include "bespill.h"
#include "bepressurestat.h"
+#include "beprofile.h"
#include "bechordal_t.h"
#define DUMP_PROBLEM 1
#define DUMP_MPS 2
#define DUMP_SOLUTION 4
+#define DUMP_STATS 8
+#define DUMP_PRESSURE 16
#define KEEPALIVE_REMATS 1
#define KEEPALIVE_SPILLS 2
static int opt_timeout = 300;
static double opt_cost_reload = 8.0;
static double opt_cost_memoperand = 7.0;
-static double opt_cost_spill = 50.0;
+static double opt_cost_spill = 15.0;
static double opt_cost_remat = 1.0;
{ "problem", DUMP_PROBLEM },
{ "mps", DUMP_MPS },
{ "solution", DUMP_SOLUTION },
+ { "stats", DUMP_STATS },
+ { "pressure", DUMP_PRESSURE },
{ NULL, 0 }
};
};
static const lc_opt_table_entry_t options[] = {
- LC_OPT_ENT_ENUM_MASK("keepalive", "keep alive remats, spills or reloads", &keep_alive_var),
+ LC_OPT_ENT_ENUM_MASK("keepalive", "keep alive inserted nodes", &keep_alive_var),
LC_OPT_ENT_BOOL ("goodwin", "activate goodwin reduction", &opt_goodwin),
LC_OPT_ENT_BOOL ("memcopies", "activate memcopy handling", &opt_memcopies),
LC_OPT_ENT_BOOL ("memoperands", "activate memoperands", &opt_memoperands),
- LC_OPT_ENT_ENUM_INT ("remats", "type of remats to insert (none, briggs, noinverse or all)",&remats_var),
+ LC_OPT_ENT_ENUM_INT ("remats", "type of remats to insert", &remats_var),
LC_OPT_ENT_BOOL ("repair_schedule", "repair the schedule by rematting once used nodes",&opt_repair_schedule),
LC_OPT_ENT_BOOL ("no_enlage_liveness", "do not enlarge liveness of operands of remats",&opt_no_enlarge_liveness),
- LC_OPT_ENT_BOOL ("remat_while_live", "remat only values that can be used by real ops", &opt_remat_while_live),
+ LC_OPT_ENT_BOOL ("remat_while_live", "only remat where rematted value was live", &opt_remat_while_live),
- LC_OPT_ENT_ENUM_MASK("dump", "dump problem, mps or solution", &dump_var),
+ LC_OPT_ENT_ENUM_MASK("dump", "dump problem, solution or statistical data", &dump_var),
LC_OPT_ENT_BOOL ("log", "activate the lpp log", &opt_log),
LC_OPT_ENT_INT ("timeout", "ILP solver timeout", &opt_timeout),
set *interferences;
ir_node *m_unknown;
set *memoperands;
+#ifndef SCHEDULE_PHIM
+ pset *phims;
+#endif
DEBUG_ONLY(firm_dbg_module_t * dbg);
} spill_ilp_t;
execution_frequency(const spill_ilp_t *si, const ir_node * irn)
{
#define FUDGE 0.001
+ if(be_profile_has_data())
+ return ((double)be_profile_get_block_execcount(get_block(irn))) + FUDGE;
+
#ifndef EXECFREQ_LOOPDEPH
- return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE;
+ return get_block_execfreq(si->chordal_env->birg->exec_freq, get_block(irn)) + FUDGE;
#else
if(is_Block(irn))
return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
if(!is_rematerializable(si, op))
return NULL;
- remat = obstack_alloc(si->obst, sizeof(*remat));
- remat->op = op;
- remat->cost = get_cost(si, op);
- remat->value = dest_value;
- remat->proj = proj;
+ remat = obstack_alloc(si->obst, sizeof(*remat));
+ remat->op = op;
+ remat->cost = (int)get_cost(si, op);
+ remat->value = dest_value;
+ remat->proj = proj;
remat->inverse = 0;
} else {
arch_inverse_t inverse;
sched_add_after(insert, irn);
}
+static ir_node *
+next_post_remat(const ir_node * irn)
+{
+ op_t *op;
+ ir_node *next;
+
+ if(is_Block(irn)) {
+ next = sched_block_first_nonphi(irn);
+ } else {
+ next = sched_next_op(irn);
+ }
+
+ if(sched_is_end(next))
+ return NULL;
+
+ op = get_irn_link(next);
+ if(op->is_remat && !op->attr.remat.pre) {
+ return next;
+ }
+
+ return NULL;
+}
+
+
+static ir_node *
+next_pre_remat(const spill_ilp_t * si, const ir_node * irn)
+{
+ op_t *op;
+ ir_node *ret;
+
+ if(is_Block(irn)) {
+ ret = sched_block_last_noncf(si, irn);
+ ret = sched_next(ret);
+ ret = sched_prev_op(ret);
+ } else {
+ ret = sched_prev_op(irn);
+ }
+
+ if(sched_is_end(ret) || is_Phi(ret))
+ return NULL;
+
+ op = (op_t*)get_irn_link(ret);
+ if(op->is_remat && op->attr.remat.pre) {
+ return ret;
+ }
+
+ return NULL;
+}
+
/**
* Tells you whether a @p remat can be placed before the irn @p pos
*/
return 1;
}
+static void
+get_live_end(spill_ilp_t * si, ir_node * bb, pset * live)
+{
+ ir_node *irn;
+ int i;
+
+ be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
+ irn = be_lv_get_irn(si->lv, bb, i);
+
+ if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
+ pset_insert_ptr(live, irn);
+ }
+ }
+
+ irn = sched_last(bb);
+
+ /* all values eaten by control flow operations are also live until the end of the block */
+ sched_foreach_reverse(bb, irn) {
+ int i;
+
+ if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
+
+ for(i=get_irn_arity(irn)-1; i>=0; --i) {
+ ir_node *arg = get_irn_n(irn,i);
+
+ if(has_reg_class(si, arg)) {
+ pset_insert_ptr(live, arg);
+ }
+ }
+ }
+ /*
+ * find values that are used by remats at end of block
+ * and insert them into live set
+ */
+ foreach_pre_remat(si, bb, irn) {
+ int n;
+
+ for (n=get_irn_arity(irn)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(irn, n);
+
+ if(!has_reg_class(si, remat_arg)) continue;
+
+ /* if value is becoming live through use by remat */
+ if(!pset_find_ptr(live, remat_arg)) {
+ DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat at end of block %+F\n", remat_arg, irn));
+
+ pset_insert_ptr(live, remat_arg);
+ }
+ }
+ }
+}
+
static void
walker_regclass_copy_insertor(ir_node * irn, void * data)
{
ir_node *irn;
int n, i;
pset *live;
+ pset *post_remats;
+ remat_t *remat;
/* skip start block, no remats to do there */
if(is_start_block(bb)) return;
ir_node *next;
pset *args;
ir_node *arg;
- pset *remat_args;
+ pset *used;
next = sched_prev(irn);
+ /* delete defined value from live set */
+ if(has_reg_class(si, irn)) {
+ pset_remove_ptr(live, irn);
+ }
+
if(is_Phi(irn) || is_Proj(irn)) {
irn = next;
continue;
}
args = pset_new_ptr_default();
+ used = pset_new_ptr_default();
- /* collect arguments of op */
+ /* collect arguments of op and set args of op already live in epilog */
for (n = get_irn_arity(irn)-1; n>=0; --n) {
ir_node *arg = get_irn_n(irn, n);
pset_insert_ptr(args, arg);
- }
-
- /* set args of op already live in epilog */
- pset_foreach(args, arg) {
if(has_reg_class(si, arg)) {
pset_insert_ptr(live, arg);
+ pset_insert_ptr(used, arg);
}
}
- /* delete defined value from live set */
- if(has_reg_class(si, irn)) {
- pset_remove_ptr(live, irn);
- }
-
- remat_args = pset_new_ptr_default();
/* insert all possible remats before irn */
pset_foreach(args, arg) {
remat_info_t *remat_info,
query;
- remat_t *remat;
- /* continue if the operand has the wrong reg class
- */
+ /* continue if the operand has the wrong reg class */
if(!has_reg_class(si, arg))
continue;
ir_node *remat_irn = NULL;
DBG((si->dbg, LEVEL_4, "\t considering remat %+F for arg %+F\n", remat->op, arg));
- if(opt_remat_while_live) {
- if(pset_find_ptr(live, remat->value)) {
- remat_irn = insert_remat_before(si, remat, irn, live);
- }
- } else {
- remat_irn = insert_remat_before(si, remat, irn, live);
- }
+ remat_irn = insert_remat_before(si, remat, irn, live);
+
if(remat_irn) {
for(n=get_irn_arity(remat_irn)-1; n>=0; --n) {
ir_node *remat_arg = get_irn_n(remat_irn, n);
- if(!has_reg_class(si, remat_arg)) continue;
-
- pset_insert_ptr(remat_args, remat_arg);
+ /* collect args of remats which are not args of op */
+ if(has_reg_class(si, remat_arg) && !pset_find_ptr(args, remat_arg)) {
+ pset_insert_ptr(used, remat_arg);
+ }
}
}
}
}
}
- /* now we add remat args to op's args because they could also die at this op */
- pset_foreach(args,arg) {
- if(pset_find_ptr(remat_args, arg)) {
- pset_remove_ptr(remat_args, arg);
- }
- }
- pset_foreach(remat_args,arg) {
- pset_insert_ptr(args, arg);
+ /* do not place post remats after jumps */
+ if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) {
+ del_pset(used);
+ del_pset(args);
+ break;
}
/* insert all possible remats after irn */
- pset_foreach(args, arg) {
+ post_remats = pset_new_ptr_default();
+ pset_foreach(used, arg) {
remat_info_t *remat_info,
query;
- remat_t *remat;
/* continue if the operand has the wrong reg class */
if(!has_reg_class(si, arg))
continue;
}
- /* do not place post remats after jumps */
- if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) continue;
-
if(remat_info->remats_by_operand) {
pset_foreach(remat_info->remats_by_operand, remat) {
/* do not insert remats producing the same value as one of the operands */
if(!pset_find_ptr(args, remat->value)) {
DBG((si->dbg, LEVEL_4, "\t considering remat %+F with arg %+F\n", remat->op, arg));
- if(opt_remat_while_live) {
- if(pset_find_ptr(live, remat->value)) {
- insert_remat_after(si, remat, irn, live);
- }
- } else {
- insert_remat_after(si, remat, irn, live);
+
+ /* only remat values that can be used by real ops */
+ if(!opt_remat_while_live || pset_find_ptr(live, remat->value)) {
+ pset_insert_ptr(post_remats, remat);
}
}
}
}
}
+ pset_foreach(post_remats, remat) {
+ insert_remat_after(si, remat, irn, live);
+ }
+ del_pset(post_remats);
- del_pset(remat_args);
+ del_pset(used);
del_pset(args);
irn = next;
}
pset *live_out = pset_new_ptr_default();
ir_node *value;
- be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
- value = be_lv_get_irn(si->lv, bb, i);
-
- if (has_reg_class(si, value)) {
- pset_insert_ptr(live_out, value);
- }
- }
+ get_live_end(si, bb, live_out);
/* add remats at end of block */
pset_foreach(live_out, value) {
remat_info_t *remat_info,
query;
- remat_t *remat;
query.irn = value;
query.remats = NULL;
pset_insert_ptr(live_in, value);
}
}
+ /* add phis to live_in */
sched_foreach(bb, value) {
if(!is_Phi(value)) break;
}
/* add remat2s at beginning of block */
+ post_remats = pset_new_ptr_default();
pset_foreach(live_in, value) {
remat_info_t *remat_info,
query;
- remat_t *remat;
query.irn = value;
query.remats = NULL;
pset_foreach(remat_info->remats_by_operand, remat) {
DBG((si->dbg, LEVEL_4, "\t considering remat2 %+F at beginning of block %+F\n", remat->op, bb));
- /* put the remat here if all its args are available */
- insert_remat_after(si, remat, bb, live_in);
-
+ /* put the remat here if all its args are available and result is still live */
+ if(!opt_remat_while_live || pset_find_ptr(live_in, remat->value)) {
+ pset_insert_ptr(post_remats, remat);
+ }
}
}
}
+ pset_foreach(post_remats, remat) {
+ insert_remat_after(si, remat, bb, live_in);
+ }
+ del_pset(post_remats);
del_pset(live_in);
}
}
-int
+static int
can_be_copied(const ir_node * bb, const ir_node * irn)
{
- assert(is_merge_edge(bb));
-
- const ir_edge_t *edge = get_block_succ_first(bb);
+ const ir_edge_t *edge = get_block_succ_first(bb);
const ir_node *next_bb = edge->src;
- int pos = edge->pos;
+ int pos = edge->pos;
const ir_node *phi;
+ assert(is_merge_edge(bb));
+
sched_foreach(next_bb, phi) {
const ir_node *phi_arg;
pset_insert_ptr(live, irn);
}
}
+ /*
+ * find values that are used by remats at end of block
+ * and insert them into live set
+ */
+ foreach_pre_remat(si, bb, irn) {
+ int n;
+
+ for (n=get_irn_arity(irn)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(irn, n);
+
+ if(has_reg_class(si, remat_arg)) {
+ pset_insert_ptr(live, remat_arg);
+ }
+ }
+ }
/* collect values used by cond jumps etc. at bb end (use_end) -> always live */
/* their reg_out must always be set */
ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb);
spill->reg_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0);
- /* if irn is used at the end of the block, then it is live anyway */
- //lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", irn, bb);
spill->mem_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0);
del_pset(use_end);
}
-static ir_node *
-next_post_remat(const ir_node * irn)
-{
- op_t *op;
- ir_node *next;
-
- if(is_Block(irn)) {
- next = sched_block_first_nonphi(irn);
- } else {
- next = sched_next_op(irn);
- }
-
- if(sched_is_end(next))
- return NULL;
-
- op = get_irn_link(next);
- if(op->is_remat && !op->attr.remat.pre) {
- return next;
- }
-
- return NULL;
-}
-
-
-static ir_node *
-next_pre_remat(const spill_ilp_t * si, const ir_node * irn)
-{
- op_t *op;
- ir_node *ret;
-
- if(is_Block(irn)) {
- ret = sched_block_last_noncf(si, irn);
- ret = sched_next(ret);
- ret = sched_prev_op(ret);
- } else {
- ret = sched_prev_op(irn);
- }
-
- if(sched_is_end(ret) || is_Phi(ret))
- return NULL;
-
- op = (op_t*)get_irn_link(ret);
- if(op->is_remat && op->attr.remat.pre) {
- return ret;
- }
-
- return NULL;
-}
-
/**
* Find a remat of value @p value in the epilog of @p pos
*/
return spill;
}
-static void
-get_live_end(spill_ilp_t * si, ir_node * bb, pset * live)
-{
- ir_node *irn;
- int i;
-
- be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
- irn = be_lv_get_irn(si->lv, bb, i);
-
- if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
- pset_insert_ptr(live, irn);
- }
- }
-
- irn = sched_last(bb);
-
- /* all values eaten by control flow operations are also live until the end of the block */
- sched_foreach_reverse(bb, irn) {
- int i;
-
- if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
-
- for(i=get_irn_arity(irn)-1; i>=0; --i) {
- ir_node *arg = get_irn_n(irn,i);
-
- if(has_reg_class(si, arg)) {
- pset_insert_ptr(live, arg);
- }
- }
- }
-}
-
/**
* Inserts ILP-constraints and variables for memory copying before the given position
*/
insert_mem_copy_position(si, live, bb);
/*
- * start new live ranges for values used by remats at end of block
- * and assure the remat args are available
+ * assure the remat args are available
*/
foreach_pre_remat(si, bb, tmp) {
op_t *remat_op = get_irn_link(tmp);
for (n=get_irn_arity(tmp)-1; n>=0; --n) {
ir_node *remat_arg = get_irn_n(tmp, n);
op_t *arg_op = get_irn_link(remat_arg);
- ilp_var_t prev_lr;
if(!has_reg_class(si, remat_arg)) continue;
- /* if value is becoming live through use by remat */
- if(!pset_find_ptr(live, remat_arg)) {
- ir_snprintf(buf, sizeof(buf), "lr_%N_end%N", remat_arg, bb);
- prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0);
-
- arg_op->attr.live_range.ilp = prev_lr;
- arg_op->attr.live_range.op = bb;
-
- DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat at end of block %+F\n", remat_arg, tmp));
+ spill = set_find_spill(spill_bb->ilp, remat_arg);
+ assert(spill);
- pset_insert_ptr(live, remat_arg);
- add_to_spill_bb(si, bb, remat_arg);
- }
+ /* arguments of remats have to be live until the very end of the block
+ * remat = reg_out(remat_arg) and (reload(remat_arg) or live_range(remat_arg)),
+ * no remats, they could be in wrong order
+ */
- /* remat <= live_rang(remat_arg) [ + reload(remat_arg) ] */
ir_snprintf(buf, sizeof(buf), "req_remat_%N_arg_%N", tmp, remat_arg);
cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
- lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 3.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->reg_out, -2.0);
lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0);
/* use reload placed for this argument */
/* just to be sure */
check_post = ILP_UNDEF;
+ /* allow original defintions to be removed */
+ if(opt_repair_schedule) {
+ pset_foreach(defs, tmp) {
+ op_t *tmp_op = get_irn_link(tmp);
+ spill_t *spill = set_find_spill(spill_bb->ilp, tmp);
+#if 1
+ ilp_var_t delete;
+ assert(spill);
+
+ ir_snprintf(buf, sizeof(buf), "delete_%N", tmp);
+ delete = lpp_add_var_default(si->lpp, buf, lpp_binary, -1.0*get_cost(si, irn)*execution_frequency(si, bb), 0.0);
+
+ /* op may not be killed if its first live_range is 1 */
+ ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, delete, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0);
+
+ /* op may not be killed if it is spilled after the definition */
+ ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, delete, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
+#else
+ ilp_var_t keep;
+ assert(spill);
+
+ ir_snprintf(buf, sizeof(buf), "keep_%N", tmp);
+ keep = lpp_add_var_default(si->lpp, buf, lpp_binary, get_cost(si, irn)*execution_frequency(si, bb), 1.0);
+
+ /* op may not be killed if its first live_range is 1 */
+ ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
+ lpp_set_factor_fast(si->lpp, cst, keep, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, -1.0);
+
+ /* op may not be killed if it is spilled after the definition */
+ ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
+ lpp_set_factor_fast(si->lpp, cst, keep, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0);
+#endif
+ }
+ } else {
+#if 0
+ pset_foreach(defs, tmp) {
+ op_t *tmp_op = get_irn_link(tmp);
+ spill_t *spill = set_find_spill(spill_bb->ilp, tmp);
+ assert(spill);
+
+ /* live_range or spill should be 1
+ TODO: lr should be live until first use */
+ ir_snprintf(buf, sizeof(buf), "nokillorig_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0);
+ lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
+ }
+#endif
+ }
+
/******************
* P R O L O G
foreach_post_remat(bb, tmp) {
int n;
- pset *remat_args = pset_new_ptr(get_irn_arity(tmp));
op_t *remat_op = get_irn_link(tmp);
+ pset *remat_args = pset_new_ptr(get_irn_arity(tmp));
ir_node *remat_arg;
for (n=get_irn_arity(tmp)-1; n>=0; --n) {
remat_arg = get_irn_n(tmp, n);
+
if(has_reg_class(si, remat_arg)) {
pset_insert_ptr(remat_args, remat_arg);
}
}
- assert(pset_count(remat_args) > 0 && "post remats should have at least one arg");
/* remat + \sum live_range(remat_arg) <= |args| */
ir_snprintf(buf, sizeof(buf), "one_must_die_%N", tmp);
lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
pset_foreach(remat_args, remat_arg) {
+ if(pset_find_ptr(live, remat_arg)) {
+ op_t *remat_arg_op = get_irn_link(remat_arg);
+ lpp_set_factor_fast(si->lpp, cst, remat_arg_op->attr.live_range.ilp, 1.0);
+ }
+ }
+ del_pset(remat_args);
+ }
+
+ foreach_post_remat(bb, tmp) {
+ int n;
+
+ for(n=get_irn_arity(tmp)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(tmp, n);
+
/* if value is becoming live through use by remat2 */
- if(!pset_find_ptr(live, remat_arg)) {
+ if(has_reg_class(si, remat_arg) && !pset_find_ptr(live, remat_arg)) {
op_t *remat_arg_op = get_irn_link(remat_arg);
ilp_cst_t nomem;
/* optimization: all memory stuff should be 0, for we do not want to insert reloads for remats */
ir_snprintf(buf, sizeof(buf), "nomem_%N_%N", remat_arg, bb);
nomem = lpp_add_cst_uniq(si->lpp, buf, lpp_equal, 0.0);
-
lpp_set_factor_fast(si->lpp, nomem, spill->spill, 1.0);
- if(spill_bb->reloads) {
- keyval_t *keyval = set_find_keyval(spill_bb->reloads, remat_arg);
-
- if(keyval) {
- ilp_var_t reload = PTR_TO_INT(keyval->val);
- lpp_set_factor_fast(si->lpp, nomem, reload, 1.0);
- }
- }
- } else {
- op_t *remat_arg_op = get_irn_link(remat_arg);
- lpp_set_factor_fast(si->lpp, cst, remat_arg_op->attr.live_range.ilp, 1.0);
}
}
- del_pset(remat_args);
}
/* L\U is empty at bb start */
/** insert a spill at an arbitrary position */
ir_node *be_spill2(const arch_env_t *arch_env, ir_node *irn, ir_node *insert)
{
- ir_node *bl = is_Block(insert)?insert:get_nodes_block(insert);
+ ir_node *bl = is_Block(insert)?insert:get_nodes_block(insert);
ir_graph *irg = get_irn_irg(bl);
- ir_node *frame = get_irg_frame(irg);
- ir_node *spill;
- ir_node *next;
-
- const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
- const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
+ ir_node *frame = get_irg_frame(irg);
+ ir_node *spill;
+ ir_node *next;
+ const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
- spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn);
+ spill = be_new_Spill(cls, irg, bl, irn);
/*
* search the right insertion point. a spill of a phi cannot be put
* which is its default initialization (see above).
*/
- if(bl == get_irg_start_block(irg) && sched_get_time_step(frame) >= sched_get_time_step(insert))
+ if (bl == get_irg_start_block(irg) && sched_get_time_step(frame) >= sched_get_time_step(insert))
insert = frame;
for (next = sched_next(insert); is_Phi(next) || is_Proj(next); next = sched_next(insert))
pset_foreach(remat_info->remats, remat)
{
if(remat->proj && get_irn_n_edges(remat->proj) == 0) {
+ if(sched_is_scheduled(remat->proj)) {
+ sched_remove((ir_node*)remat->proj);
+ }
set_irn_n((ir_node*)remat->proj, -1, bad);
set_irn_n((ir_node*)remat->proj, 0, bad);
}
if(get_irn_n_edges(remat->op) == 0) {
+ if(sched_is_scheduled(remat->op)) {
+ sched_remove((ir_node*)remat->op);
+ }
for (n=get_irn_arity(remat->op)-1; n>=-1; --n) {
set_irn_n((ir_node*)remat->op, n, bad);
}
ir_node *bad = get_irg_bad(si->chordal_env->irg);
if(si->keep) {
-// ir_node *end = get_irg_end(si->chordal_env->irg);
-// ir_node **keeps;
-
for (n=get_irn_arity(si->keep)-1; n>=0; --n) {
ir_node *keep_arg = get_irn_n(si->keep, n);
op_t *arg_op = get_irn_link(keep_arg);
set_irn_n(si->keep, n, bad);
}
-#if 0
- for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
- ir_node *end_arg = get_End_keepalive(end, i);
-
- if(end_arg != si->keep) {
- obstack_grow(si->obst, &end_arg, sizeof(end_arg));
- }
- }
- keeps = obstack_finish(si->obst);
- set_End_keepalives(end, n-1, keeps);
- obstack_free(si->obst, keeps);
-#endif
} else {
DBG((si->dbg, LEVEL_2, "\t no remats to delete (none have been inserted)\n"));
}
return spills;
}
+static ir_node *
+new_r_PhiM_nokeep(ir_graph * irg, ir_node *block, int arity, ir_node **in)
+{
+ ir_node *res;
+
+ assert( get_irn_arity(block) == arity );
+
+ res = new_ir_node(NULL, irg, block, op_Phi, mode_M, arity, in);
+ res->attr.phi_backedge = new_backedge_arr(irg->obst, arity);
+
+ return res;
+}
+
/**
* @param before The node after which the spill will be placed in the schedule
*/
ins[n] = si->m_unknown;
}
- mem_phi = new_r_Phi(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins, mode_M);
+ mem_phi = new_r_PhiM_nokeep(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins);
defs = set_insert_def(si->values, phi);
assert(defs);
#ifdef SCHEDULE_PHIM
sched_add_after(phi, mem_phi);
+#else
+ pset_insert_ptr(si->phims, mem_phi);
#endif
if(opt_keep_alive & KEEPALIVE_SPILLS)
reload = insert_reload(si, arg, insert_pos);
+ assert(reload && "no reload returned");
set_irn_n(irn, n, reload);
if(opt_keep_alive & KEEPALIVE_RELOADS)
}
}
+#ifndef SCHEDULE_PHIM
+static void
+kill_unused_phims(spill_ilp_t * si, struct kill_helper * kh)
+{
+ ir_node *phi;
+ ir_node *bad = get_irg_bad(si->chordal_env->irg);
+ int n;
+
+ pset_foreach(si->phims, phi) {
+ if(!bitset_is_set(kh->used, get_irn_idx(phi))) {
+
+ set_nodes_block(phi, bad);
+ for (n=get_irn_arity(phi)-1; n>=0; --n) {
+ set_irn_n(phi, n, bad);
+ }
+ }
+ }
+}
+#endif
+
static void
kill_all_unused_values_in_schedule(spill_ilp_t * si)
{
- struct kill_helper kh;
+ struct kill_helper kh;
kh.used = bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
kh.si = si;
irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, kh.used);
+#ifndef SCHEDULE_PHIM
+ kill_unused_phims(si, &kh);
+#endif
irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh);
bitset_free(kh.used);
static void
rewire_uses(spill_ilp_t * si)
{
- dom_front_info_t *dfi = be_compute_dominance_frontiers(si->chordal_env->irg);
defs_t *defs;
pset *ignore = pset_new_ptr(1);
+ be_dom_front_info_t *dom_front = si->chordal_env->birg->dom_front;
pset_insert_ptr(ignore, get_irg_end(si->chordal_env->irg));
// print_irn_pset(spills);
// print_irn_pset(reloads);
- be_ssa_constr_set_ignore(dfi, si->lv, spills, ignore);
+ be_ssa_constr_set_ignore(dom_front, si->lv, spills, ignore);
}
del_pset(reloads);
set_foreach(si->values, defs) {
pset *nodes;
const ir_node *next = defs->remats;
+ int orig_kept = 0;
if(next) {
nodes = pset_new_ptr_default();
- pset_insert_ptr(nodes, defs->value);
+ if(sched_is_scheduled(defs->value)) {
+ pset_insert_ptr(nodes, defs->value);
+ orig_kept = 1;
+ }
while(next) {
pset_insert_ptr(nodes, next);
next = get_irn_link(next);
}
- if(pset_count(nodes) > 1) {
- DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-1, defs->value));
- be_ssa_constr_set(dfi, si->lv, nodes);
- }
+ DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-orig_kept, defs->value));
+ be_ssa_constr_set(dom_front, si->lv, nodes);
del_pset(nodes);
}
}
// remove_unused_defs(si);
-
- be_free_dominance_frontiers(dfi);
}
char dump_suffix2[256];
struct obstack obst;
spill_ilp_t si;
+ be_irg_t *birg = chordal_env->birg;
ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name);
ir_snprintf(dump_suffix, sizeof(dump_suffix), "-%s-remats", chordal_env->cls->name);
if(opt_verify & VERIFY_DOMINANCE)
be_check_dominance(chordal_env->irg);
+ be_assure_dom_front(birg);
+ be_assure_liveness(birg);
+
obstack_init(&obst);
si.chordal_env = chordal_env;
si.obst = &obst;
si.all_possible_remats = pset_new_ptr_default();
si.spills = pset_new_ptr_default();
si.inverse_ops = pset_new_ptr_default();
- si.lv = chordal_env->lv;
+ si.lv = birg->lv;
si.keep = NULL;
si.n_regs = get_n_regs(&si);
/* compute phi classes */
// phi_class_compute(chordal_env->irg);
- be_analyze_regpressure(chordal_env, "-pre");
+ if(opt_dump_flags & DUMP_STATS)
+ be_analyze_regpressure(chordal_env, "-pre");
DBG((si.dbg, LEVEL_2, "\t initializing\n"));
irg_block_walk_graph(chordal_env->irg, luke_initializer, NULL, &si);
assert(lpp_is_sol_valid(si.lpp)
&& "solution of ILP must be valid");
- DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval));
+ DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g, best bound: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval, is_zero(si.lpp->best_bound)?0.0:si.lpp->best_bound));
if(opt_dump_flags & DUMP_SOLUTION) {
FILE *f;
}
}
+#ifndef SCHEDULE_PHIM
+ si.phims = pset_new_ptr_default();
+#endif
writeback_results(&si);
+
#endif /* SOLVE */
kill_all_unused_values_in_schedule(&si);
+#if !defined(SCHEDULE_PHIM) && defined(SOLVE)
+ del_pset(si.phims);
+#endif
+
if(opt_keep_alive & (KEEPALIVE_SPILLS | KEEPALIVE_RELOADS))
be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph);
irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
- dump_pressure_graph(&si, dump_suffix2);
+ if(opt_dump_flags & DUMP_PRESSURE)
+ dump_pressure_graph(&si, dump_suffix2);
- be_analyze_regpressure(chordal_env, "-post");
+ if(opt_dump_flags & DUMP_STATS)
+ be_analyze_regpressure(chordal_env, "-post");
if(opt_verify & VERIFY_DOMINANCE)
be_check_dominance(chordal_env->irg);