#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"
int n;
int ret = 0;
-// if(is_Proj(irn))
-// irn = get_Proj_pred(irn);
+ if(is_Proj(irn))
+ irn = get_Proj_pred(irn);
for(n=get_irn_arity(irn)-1; n>=0; --n) {
const ir_node *arg = get_irn_n(irn, n);
be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
value = be_lv_get_irn(si->lv, bb, i);
- if (be_is_live_end(si->lv, bb, value) && has_reg_class(si, value)) {
+ if (has_reg_class(si, value)) {
pset_insert_ptr(live_out, value);
}
}
be_lv_foreach(si->lv, bb, be_lv_state_in, i) {
value = be_lv_get_irn(si->lv, bb, i);
- if (has_reg_class(si, value)) {
+ if(has_reg_class(si, value)) {
+ pset_insert_ptr(live_in, value);
+ }
+ }
+ sched_foreach(bb, value) {
+ if(!is_Phi(value)) break;
+
+ if(has_reg_class(si, value)) {
pset_insert_ptr(live_in, value);
}
}
/* add remat2s at beginning of block */
pset_foreach(live_in, value) {
- if ((be_is_live_in(si->lv, bb, value) || (is_Phi(value) && get_nodes_block(value)==bb)) && has_reg_class(si, value)) {
- remat_info_t *remat_info,
- query;
- remat_t *remat;
+ remat_info_t *remat_info,
+ query;
+ remat_t *remat;
- query.irn = value;
- query.remats = NULL;
- query.remats_by_operand = NULL;
- remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value));
+ query.irn = value;
+ query.remats = NULL;
+ query.remats_by_operand = NULL;
+ remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value));
- if(remat_info && remat_info->remats_by_operand) {
- 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));
+ if(remat_info && remat_info->remats_by_operand) {
+ 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 */
+ insert_remat_after(si, remat, bb, live_in);
- }
}
}
}
}
}
+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;
+}
+
/**
* Preparation of blocks' ends for Luke Blockwalker(tm)(R)
*/
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 */
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)
}
}
- // value_op->attr.live_range.ilp != ILP_UNDEF
if(pset_find_ptr(live, value) && cst != ILP_UNDEF) {
lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, -n_remats);
}
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 */
/* 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;
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);
+ ir_node *remat_arg;
for (n=get_irn_arity(tmp)-1; n>=0; --n) {
- ir_node *remat_arg = get_irn_n(tmp, 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");
- if(!has_reg_class(si, remat_arg)) continue;
+ /* remat + \sum live_range(remat_arg) <= |args| */
+ ir_snprintf(buf, sizeof(buf), "one_must_die_%N", tmp);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, pset_count(remat_args));
+ lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+ pset_foreach(remat_args, remat_arg) {
/* if value is becoming live through use by remat2 */
if(!pset_find_ptr(live, remat_arg)) {
op_t *remat_arg_op = get_irn_link(remat_arg);
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 */
spill = set_find_spill(spill_bb->ilp, remat_arg);
assert(spill);
- /* remat <= reg_in_argument */
ir_snprintf(buf, sizeof(buf), "req_remat2_%N_%N_arg_%N", tmp, bb, remat_arg);
cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
const ir_node *remat;
int n_remats = 0;
- if(op->attr.live_range.ilp == ILP_UNDEF) continue;
-
cst = ILP_UNDEF;
foreach_post_remat(bb, remat) {
const op_t *remat_op = get_irn_link(remat);
if(cst == ILP_UNDEF) {
- /* \sum post_remat <= 1 + #post_remats * next(lr) */
- ir_snprintf(buf, sizeof(buf), "remat2_%N_%N_arg_%N", remat, bb, irn);
- cst = lpp_add_cst(si->lpp, buf, lpp_less, 1.0);
+ /* sum remat2s <= 1 + n_remats*live_range */
+ ir_snprintf(buf, sizeof(buf), "dying_lr_%N_%N", irn, bb);
+ cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
}
lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
++n_remats;
}
}
}
- if(n_remats) {
- lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, n_remats);
+ if(cst != ILP_UNDEF && op->attr.live_range.ilp != ILP_UNDEF) {
+ lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -n_remats);
}
}
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
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);
+
+ 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", free, si->cls->name));
- return free;
+ 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