#include <lpp/lpp_net.h>
#include <lpp/lpp_cplex.h>
//#include <lc_pset.h>
-#include <libcore/lc_bitset.h>
+//#include <libcore/lc_bitset.h>
#include "be_t.h"
#include "belive_t.h"
#include "besched_t.h"
#include "beirgmod.h"
#include "bearch.h"
+#include "beabi.h"
#include "benode_t.h"
#include "beutil.h"
#include "bespillremat.h"
static int opt_remats = REMATS_ALL;
static int opt_repair_schedule = 0;
static int opt_no_enlarge_liveness = 0;
-static int opt_remat_while_live = 1;
static int opt_timeout = 300;
static double opt_cost_reload = 8.0;
static double opt_cost_memoperand = 7.0;
LC_OPT_ENT_ENUM_INT ("remats", "type of remats to insert (none, briggs, noinverse or all)",&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_ENUM_MASK("dump", "dump problem, mps or solution", &dump_var),
LC_OPT_ENT_BOOL ("log", "activate the lpp log", &opt_log),
return get_irg_start_block(get_irn_irg(bb)) == bb;
}
-static int
-is_before_frame(const ir_node * bb, const ir_node * irn)
-{
- const ir_node *frame = get_irg_frame(get_irn_irg(bb));
-
- if(is_start_block(bb) && sched_get_time_step(frame) >= sched_get_time_step(irn))
- return 1;
- else
- return 0;
-}
-
static int
is_merge_edge(const ir_node * bb)
{
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);
+ }
+ }
+ }
+}
+
static void
walker_regclass_copy_insertor(ir_node * irn, void * data)
{
}
}
-
/**
* Insert (so far unused) remats into the irg to
* recompute the potential liveness of all values
walker_remat_insertor(ir_node * bb, void * data)
{
spill_ilp_t *si = data;
- spill_bb_t *spill_bb;
ir_node *irn;
int n, i;
- pset *live = pset_new_ptr_default();
+ pset *live;
+ pset *post_remats;
+ remat_t *remat;
+
+ /* skip start block, no remats to do there */
+ if(is_start_block(bb)) return;
DBG((si->dbg, LEVEL_3, "\t Entering %+F\n\n", bb));
+ live = pset_new_ptr_default();
be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
ir_node *value = be_lv_get_irn(si->lv, bb, i);
}
}
- spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
- set_irn_link(bb, spill_bb);
-
irn = sched_last(bb);
while(!sched_is_end(irn)) {
ir_node *next;
- op_t *op;
pset *args;
ir_node *arg;
- pset *remat_args;
+ pset *used;
next = sched_prev(irn);
- DBG((si->dbg, LEVEL_5, "\t at %+F (next: %+F)\n", irn, next));
+ /* delete defined value from live set */
+ if(has_reg_class(si, irn)) {
+ pset_remove_ptr(live, irn);
+ }
if(is_Phi(irn) || is_Proj(irn)) {
- op_t *op;
-
- if(has_reg_class(si, irn)) {
- pset_remove_ptr(live, irn);
- }
-
- op = obstack_alloc(si->obst, sizeof(*op));
- op->is_remat = 0;
- op->attr.live_range.args.reloads = NULL;
- op->attr.live_range.ilp = ILP_UNDEF;
- set_irn_link(irn, op);
-
irn = next;
continue;
}
- op = obstack_alloc(si->obst, sizeof(*op));
- op->is_remat = 0;
- op->attr.live_range.ilp = ILP_UNDEF;
- op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
- memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
- set_irn_link(irn, op);
-
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 be real ops */
+ if(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(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);
}
}
+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_node *next_bb = edge->src;
+ int pos = edge->pos;
+ const ir_node *phi;
+
+ sched_foreach(next_bb, phi) {
+ const ir_node *phi_arg;
+
+ if(!is_Phi(phi)) break;
+
+ phi_arg = get_irn_n(phi, pos);
+
+ if(phi_arg == irn) {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**
+ * Initialize additional node info
+ */
+static void
+luke_initializer(ir_node * bb, void * data)
+{
+ spill_ilp_t *si = (spill_ilp_t*)data;
+ spill_bb_t *spill_bb;
+ ir_node *irn;
+
+ spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
+ set_irn_link(bb, spill_bb);
+
+ sched_foreach(bb, irn) {
+ op_t *op;
+
+ op = obstack_alloc(si->obst, sizeof(*op));
+ op->is_remat = 0;
+ op->attr.live_range.ilp = ILP_UNDEF;
+ if(is_Phi(irn)) {
+ if(opt_memcopies) {
+ op->attr.live_range.args.copies = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn));
+ memset(op->attr.live_range.args.copies, 0xFF, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn));
+ }
+ } else if(!is_Proj(irn)) {
+ op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
+ memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
+ } else {
+ op->attr.live_range.args.reloads = NULL;
+ }
+ set_irn_link(irn, op);
+ }
+}
+
+
/**
* Preparation of blocks' ends for Luke Blockwalker(tm)(R)
*/
spill_bb_t *spill_bb = get_irn_link(bb);
int i;
-
live = pset_new_ptr_default();
use_end = pset_new_ptr_default();
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)) {
- op_t *op;
-
pset_insert_ptr(live, irn);
- op = get_irn_link(irn);
- assert(!op->is_remat);
}
}
ilp_cst_t rel_cst;
ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn);
- reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0);
+ reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), can_be_copied(bb, irn));
set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload));
/* reload <= mem_out */
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
*/
if(!has_reg_class(si, phi)) continue;
to_copy = get_irn_n(phi, pos);
-
to_copy_op = get_irn_link(to_copy);
to_copy_spill = set_find_spill(spill_bb->ilp, to_copy);
pset *defs = pset_new_ptr_default();
const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
-
live = pset_new_ptr_default();
/****************************************
lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
}
}
- /* maybe we should also assure that reg_out >= live_range etc. */
+ ir_snprintf(buf, sizeof(buf), "reg_out2_%N_%N", bb, irn);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
+
+ /* value may only die at bb end if it is used for a mem copy */
+ /* reg_out + \sum copy - reload - remat - live_range >= 0 */
+ lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
+ if(reload != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, reload, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -1.0);
+ foreach_pre_remat(si, bb, tmp) {
+ op_t *remat_op = get_irn_link(tmp);
+ if(remat_op->attr.remat.remat->value == irn) {
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
+ }
+ }
+ if(is_merge_edge(bb)) {
+ const ir_edge_t *edge = get_block_succ_first(bb);
+ const ir_node *next_bb = edge->src;
+ int pos = edge->pos;
+ const ir_node *phi;
+
+ sched_foreach(next_bb, phi) {
+ const ir_node *phi_arg;
+
+ if(!is_Phi(phi)) break;
+
+ phi_arg = get_irn_n(phi, pos);
+
+ if(phi_arg == irn) {
+ op_t *phi_op = get_irn_link(phi);
+ ilp_var_t copy = phi_op->attr.live_range.args.copies[pos];
+
+ lpp_set_factor_fast(si->lpp, cst, copy, 1.0);
+ }
+ }
+ }
}
if(opt_memcopies)
op = get_irn_link(irn);
/* skip remats */
if(op->is_remat) continue;
+
DBG((si->dbg, LEVEL_4, "\t at node %+F\n", irn));
/* collect defined values */
used = pset_new_ptr(pset_count(live) + get_irn_arity(irn));
remat_defs = pset_new_ptr(pset_count(live));
- for (n=get_irn_arity(irn)-1; n>=0; --n) {
- ir_node *irn_arg = get_irn_n(irn, n);
- if(has_reg_class(si, irn_arg)) {
- set_insert_keyval(args, irn_arg, (void*)n);
- pset_insert_ptr(used, irn_arg);
+ if(!is_start_block(bb) || !be_is_Barrier(irn)) {
+ for (n=get_irn_arity(irn)-1; n>=0; --n) {
+ ir_node *irn_arg = get_irn_n(irn, n);
+ if(has_reg_class(si, irn_arg)) {
+ set_insert_keyval(args, irn_arg, (void*)n);
+ pset_insert_ptr(used, irn_arg);
+ }
}
- }
- foreach_post_remat(irn, tmp) {
- op_t *remat_op = get_irn_link(tmp);
+ foreach_post_remat(irn, tmp) {
+ op_t *remat_op = get_irn_link(tmp);
- pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value);
+ pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value);
- for (n=get_irn_arity(tmp)-1; n>=0; --n) {
- ir_node *remat_arg = get_irn_n(tmp, n);
- if(has_reg_class(si, remat_arg)) {
- pset_insert_ptr(used, remat_arg);
+ for (n=get_irn_arity(tmp)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(tmp, n);
+ if(has_reg_class(si, remat_arg)) {
+ pset_insert_ptr(used, remat_arg);
+ }
}
}
- }
- foreach_pre_remat(si, irn, tmp) {
- for (n=get_irn_arity(tmp)-1; n>=0; --n) {
- ir_node *remat_arg = get_irn_n(tmp, n);
- if(has_reg_class(si, remat_arg)) {
- pset_insert_ptr(used, remat_arg);
+ foreach_pre_remat(si, irn, tmp) {
+ for (n=get_irn_arity(tmp)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(tmp, n);
+ if(has_reg_class(si, remat_arg)) {
+ pset_insert_ptr(used, remat_arg);
+ }
}
}
}
/* new live range for each used value */
ir_snprintf(buf, sizeof(buf), "lr_%N_%N", arg, irn);
- prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, is_before_frame(bb, irn)?1.0:0.0);
+ prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0);
/* the epilog stuff - including post_use, check_post, check_post_remat */
ir_snprintf(buf, sizeof(buf), "post_use_%N_%N", arg, irn);
cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0);
+ }
+
+ /* forall post remat which use arg add a similar cst */
+ foreach_post_remat(irn, remat) {
+ int n;
+ for (n=get_irn_arity(remat)-1; n>=0; --n) {
+ ir_node *remat_arg = get_irn_n(remat, n);
+ op_t *remat_op = get_irn_link(remat);
+
+ if(remat_arg == arg) {
+ DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn));
+
+ /* post_use >= remat */
+ ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
+ lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+ }
+ }
}
/* if value is not an arg of op and not possibly defined by post remat
}
}
-
- /* forall post remat which use arg add a similar cst */
- foreach_post_remat(irn, remat) {
- int n;
-
- for (n=get_irn_arity(remat)-1; n>=0; --n) {
- ir_node *remat_arg = get_irn_n(remat, n);
- op_t *remat_op = get_irn_link(remat);
-
- if(remat_arg == arg) {
- DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn));
-
- ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
- cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
- lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
- lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
- }
- }
- }
-
- if(opt_memoperands) {
+ if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
for(n = get_irn_arity(irn)-1; n>=0; --n) {
if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) {
ilp_var_t memoperand;
lpp_set_factor_fast(si->lpp, cst, memoperand, 1.0);
lpp_set_factor_fast(si->lpp, cst, post_use, 1.0);
-// if(arg_op->attr.live_range.ilp != ILP_UNDEF)
-// lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0);
}
}
}
arg_op->attr.live_range.ilp = prev_lr;
arg_op->attr.live_range.op = irn;
- /*if(!pset_find_ptr(live, arg)) {
- pset_insert_ptr(live, arg);
- add_to_spill_bb(si, bb, arg);
- }*/
pset_insert_ptr(live, arg);
-
}
/* just to be sure */
check_post = ILP_UNDEF;
-
-
/******************
* P R O L O G
******************/
pset_remove_ptr(live, tmp);
}
- if(opt_memoperands) {
+ if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
ir_snprintf(buf, sizeof(buf), "one_memoperand_%N", irn);
one_memoperand = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
}
assert(spill);
ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn);
- op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), is_before_frame(bb, irn)?0.0:1.0);
+ op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0);
/* reload <= mem_out */
ir_snprintf(buf, sizeof(buf), "req_reload_%N_%N", arg, irn);
}
}
- if(opt_memoperands) {
+ if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
n_memoperands = 0;
for(n = get_irn_arity(irn)-1; n>=0; --n) {
if(get_irn_n(irn, n) == arg) {
}
}
-
/* requirements for remats */
- /* start new live ranges for values used by remats */
foreach_pre_remat(si, irn, tmp) {
op_t *remat_op = get_irn_link(tmp);
int n;
del_set(args);
del_pset(defs);
defs = pset_new_ptr_default();
+
+ /* skip everything above barrier in start block */
+ if(is_start_block(bb) && be_is_Barrier(irn)) {
+ assert(pset_count(live) == 0);
+ break;
+ }
+
}
+ del_pset(defs);
}
/* construct mem_outs for all values */
-
set_foreach(spill_bb->ilp, spill) {
ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", spill->irn, bb);
cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
int n;
op_t *op = get_irn_link(spill->irn);
- /* do we have to copy a phi argument? */
- op->attr.live_range.args.copies = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(spill->irn));
- memset(op->attr.live_range.args.copies, 0xFF, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(spill->irn));
-
for(n=get_irn_arity(spill->irn)-1; n>=0; --n) {
const ir_node *arg = get_irn_n(spill->irn, n);
double freq=0.0;
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 */
/* walk forward now and compute constraints for placing spills */
/* this must only be done for values that are not defined in this block */
- /* TODO are these values at start of block? if yes, just check whether this is a diverge edge and skip the loop */
pset_foreach(live, irn) {
/*
* if value is defined in this block we can anways place the spill directly after the def
* -> no constraint necessary
*/
- if(!is_Phi(irn) && get_nodes_block(irn) == bb) continue;
+ if(!is_Phi(irn) && get_nodes_block(irn) == bb) {
+ assert(0);
+ }
spill = set_find_spill(spill_bb->ilp, irn);
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"));
}
void perform_memory_operand(spill_ilp_t * si, memoperand_t * memoperand)
{
defs_t *defs;
- ir_node *reload;
ir_node *value = get_irn_n(memoperand->irn, memoperand->pos);
ir_node *spill;
const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
spill = defs->spills;
assert(spill && "no spill placed before reload");
- reload = be_reload(arch_env, si->cls, memoperand->irn, get_irn_mode(value), spill);
-
- arch_perform_memory_operand(arch_env, memoperand->irn, reload, memoperand->pos);
- sched_remove(reload);
+ arch_perform_memory_operand(arch_env, memoperand->irn, spill, memoperand->pos);
}
void insert_memoperands(spill_ilp_t * si)
static void
walker_collect_used(ir_node * irn, void * data)
{
- lc_bitset_t *used = data;
+ bitset_t *used = data;
- lc_bitset_set(used, get_irn_idx(irn));
+ bitset_set(used, get_irn_idx(irn));
}
struct kill_helper {
- lc_bitset_t *used;
+ bitset_t *used;
spill_ilp_t *si;
};
ir_node *next = sched_next(irn);
int n;
- if(!lc_bitset_is_set(kh->used, get_irn_idx(irn))) {
+ if(!bitset_is_set(kh->used, get_irn_idx(irn))) {
if(be_is_Spill(irn) || be_is_Reload(irn)) {
DBG((kh->si->dbg, LEVEL_1, "\t SUBOPTIMAL! %+F IS UNUSED (cost: %g)\n", irn, get_cost(kh->si, irn)*execution_frequency(kh->si, bb)));
#if 0
{
struct kill_helper kh;
- kh.used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
+ 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);
irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh);
- lc_bitset_free(kh.used);
+ bitset_free(kh.used);
}
void
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(dfi, si->lv, nodes);
del_pset(nodes);
}
static int
get_n_regs(spill_ilp_t * si)
{
- int arch_n_regs = arch_register_class_n_regs(si->cls);
- int free = 0;
- int i;
+ int arch_n_regs = arch_register_class_n_regs(si->cls);
- for(i=0; i<arch_n_regs; i++) {
- if(!arch_register_type_is(&si->cls->regs[i], ignore)) {
- free++;
- }
- }
+ bitset_t *arch_regs = bitset_malloc(arch_n_regs);
+ bitset_t *abi_regs = bitset_malloc(arch_n_regs);
+
+ arch_put_non_ignore_regs(si->chordal_env->birg->main_env->arch_env, si->cls, arch_regs);
+ be_abi_put_ignore_regs(si->chordal_env->birg->abi, si->cls, abi_regs);
- DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", free, si->cls->name));
- return free;
+ bitset_andnot(arch_regs, abi_regs);
+ arch_n_regs = bitset_popcnt(arch_regs);
+
+ bitset_free(arch_regs);
+ bitset_free(abi_regs);
+
+ DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", arch_n_regs, si->cls->name));
+ return arch_n_regs;
}
static void
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);
+
if(opt_remats) {
/* collect remats */
DBG((si.dbg, LEVEL_1, "Collecting remats\n"));
be_liveness_recompute(si.lv);
/* build the ILP */
-
DBG((si.dbg, LEVEL_1, "\tBuilding ILP\n"));
DBG((si.dbg, LEVEL_2, "\t endwalker\n"));
irg_block_walk_graph(chordal_env->irg, luke_endwalker, NULL, &si);
projects / libfirm / blobdiff