X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=89677f6bd98512d19b4d1165272dee084e4c64e7;hb=d0331faf03740c021da65c7e07e3bf11fa2dabbd;hp=6a75d7b37474fe31f3d8da1179ee5734fe4ab7cf;hpb=8ac7ae6ba4279ea406b3231a9ed5d75c9a95e5c5;p=libfirm diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c index 6a75d7b37..89677f6bd 100644 --- a/ir/be/bespillremat.c +++ b/ir/be/bespillremat.c @@ -29,9 +29,10 @@ #include "irnode_t.h" #include "ircons_t.h" #include "irloop_t.h" -#include "phiclass.h" +#include "phiclass_t.h" #include "iredges.h" #include "execfreq.h" +#include "irvrfy.h" #include #include @@ -48,6 +49,7 @@ #include "beutil.h" #include "bespillremat.h" #include "bespill.h" +#include "bepressurestat.h" #include "bechordal_t.h" @@ -61,31 +63,31 @@ #define REMAT_WHILE_LIVE /* only remat values that are live */ //#define NO_ENLARGE_L1V3N355 /* do not remat after the death of some operand */ //#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */ -//#define MAY_DIE_AT_PRE_REMAT /* allow values to die after a pre remat */ -#define CHECK_POST_REMAT /* check pressure after post remats (conservative but otherwise we can temporarily exceed the register pressure) */ +#define MAY_DIE_AT_REMAT /* allow values to die after a pre remat */ #define NO_SINGLE_USE_REMATS /* do not repair schedule */ //#define KEEPALIVE_SPILLS //#define KEEPALIVE_RELOADS -//#define GOODWIN_REDUCTION +#define GOODWIN_REDUCTION +//#define NO_MEMCOPIES +//#define VERIFY_DOMINANCE #define SOLVE //#define SOLVE_LOCAL #define LPP_SERVER "i44pc52" #define LPP_SOLVER "cplex" -#define COST_LOAD 10 +#define COST_LOAD 8 #define COST_STORE 50 #define COST_REMAT 1 -#define ILP_TIMEOUT 90 - +#define ILP_TIMEOUT 300 +#define MAX_PATHS 16 #define ILP_UNDEF -1 typedef struct _spill_ilp_t { const arch_register_class_t *cls; int n_regs; const be_chordal_env_t *chordal_env; - spill_env_t *senv; lpp_t *lpp; struct obstack *obst; set *remat_info; @@ -95,8 +97,8 @@ typedef struct _spill_ilp_t { ir_node *keep; #endif set *values; /**< for collecting all definitions of values before running ssa-construction */ - set *execfreqs; pset *spills; + set *interferences; ir_node *m_unknown; DEBUG_ONLY(firm_dbg_module_t * dbg); } spill_ilp_t; @@ -105,16 +107,15 @@ typedef int ilp_var_t; typedef int ilp_cst_t; typedef struct _spill_bb_t { - set *ilp; - pset *copys_needed; - ilp_var_t *reloads; + set *ilp; + set *reloads; } spill_bb_t; typedef struct _remat_t { - const ir_node *op; /**< for copy_irn */ - const ir_node *proj; /**< not NULL if the above op produces a tuple */ - const ir_node *value; /**< the value which is being recomputed by this remat */ - int cost; /**< cost of this remat */ + const ir_node *op; /**< for copy_irn */ + const ir_node *value; /**< the value which is being recomputed by this remat */ + ir_node *proj; /**< not NULL if the above op produces a tuple */ + int cost; /**< cost of this remat */ int inverse; /**< nonzero if this is an inverse remat */ } remat_t; @@ -134,7 +135,10 @@ typedef struct _op_t { struct { ilp_var_t ilp; ir_node *op; /** the operation this live range belongs to */ - ilp_var_t *reloads; + union { + ilp_var_t *reloads; + ilp_var_t *copies; + } args; } live_range; } attr; } op_t; @@ -286,19 +290,28 @@ cmp_keyval(const void *a, const void *b, size_t size) } static double -execution_frequency(const spill_ilp_t * si, const ir_node * irn) +execution_frequency(const spill_ilp_t *si, const ir_node * irn) { - if(si->execfreqs) { - if(is_Block(irn)) { - return get_block_execfreq(si->execfreqs, irn); - } else { - return get_block_execfreq(si->execfreqs, get_nodes_block(irn)); - } +#define FUDGE 0.001 +#ifndef EXECFREQ_LOOPDEPH + return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE; +#else + if(is_Block(irn)) + return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE; + else + return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE; +#endif +} + +static double +get_cost(const spill_ilp_t * si, const ir_node * irn) +{ + if(be_is_Spill(irn)) { + return COST_STORE; + } else if(be_is_Reload(irn)){ + return COST_LOAD; } else { - if(is_Block(irn)) - return exp(get_loop_depth(get_irn_loop(irn)) * log(10)); - else - return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)); + return arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, irn); } } @@ -308,8 +321,7 @@ execution_frequency(const spill_ilp_t * si, const ir_node * irn) static INLINE int is_rematerializable(const spill_ilp_t * si, const ir_node * irn) { - int i, - n; + int n; const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0; @@ -318,8 +330,8 @@ is_rematerializable(const spill_ilp_t * si, const ir_node * irn) ir_fprintf(stderr, " Node %+F is not rematerializable\n", irn); #endif - for (i = 0, n = get_irn_arity(irn); i < n && remat; ++i) { - ir_node *op = get_irn_n(irn, i); + for (n = get_irn_arity(irn)-1; n>=0 && remat; --n) { + ir_node *op = get_irn_n(irn, n); remat &= has_reg_class(si, op) || arch_irn_get_flags(arch_env, op) & arch_irn_flags_ignore || (get_irn_op(op) == op_NoMem); // if(!remat) @@ -353,34 +365,33 @@ get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * remat = obstack_alloc(si->obst, sizeof(*remat)); remat->op = op; - remat->cost = arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, op); + remat->cost = get_cost(si, op); remat->value = dest_value; remat->proj = proj; remat->inverse = 0; } else { arch_inverse_t inverse; - int i, - n; + int n; /* get the index of the operand we want to retrieve by the inverse op */ - for (i = 0, n = get_irn_arity(op); i < n; ++i) { - ir_node *arg = get_irn_n(op, i); + for (n = get_irn_arity(op)-1; n>=0; --n) { + ir_node *arg = get_irn_n(op, n); if(arg == dest_value) break; } - if(i == n) return NULL; + if(n<0) return NULL; - DBG((si->dbg, LEVEL_5, "\t requesting inverse op for argument %d of op %+F\n", i, op)); + DBG((si->dbg, LEVEL_5, "\t requesting inverse op for argument %d of op %+F\n", n, op)); /* else ask the backend to give an inverse op */ - if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, i, &inverse, si->obst)) { + if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, n, &inverse, si->obst)) { int i; DBG((si->dbg, LEVEL_4, "\t backend gave us an inverse op with %d nodes and cost %d\n", inverse.n, inverse.costs)); assert(inverse.n > 0 && "inverse op should have at least one node"); - for(i=0; i=0; --i) { pset_insert_ptr(si->inverse_ops, inverse.nodes[i]); } @@ -415,8 +426,7 @@ add_remat(const spill_ilp_t * si, const remat_t * remat) { remat_info_t *remat_info, query; - int i, - n; + int n; assert(remat->op); assert(remat->value); @@ -432,8 +442,8 @@ add_remat(const spill_ilp_t * si, const remat_t * remat) pset_insert(remat_info->remats, remat, HASH_PTR(remat->op)); /* insert the remat into the remats_be_operand set of each argument of the remat op */ - for (i = 0, n = get_irn_arity(remat->op); i < n; ++i) { - ir_node *arg = get_irn_n(remat->op, i); + for (n = get_irn_arity(remat->op)-1; n>=0; --n) { + ir_node *arg = get_irn_n(remat->op, n); query.irn = arg; query.remats = NULL; @@ -466,8 +476,7 @@ get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn) static INLINE void get_remats_from_op(spill_ilp_t * si, const ir_node * op) { - int i, - n; + int n; remat_t *remat; #ifdef NO_SINGLE_USE_REMATS @@ -484,8 +493,8 @@ get_remats_from_op(spill_ilp_t * si, const ir_node * op) #ifdef COLLECT_INVERSE_REMATS /* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg) for each arg */ - for (i = 0, n = get_irn_arity(op); i < n; ++i) { - ir_node *arg = get_irn_n(op, i); + for (n = get_irn_arity(op)-1; n>=0; --n) { + ir_node *arg = get_irn_n(op, n); if(has_reg_class(si, arg)) { /* try to get an inverse remat */ @@ -619,8 +628,7 @@ can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * { const ir_node *op = remat->op; const ir_node *prev; - int i, - n, + int n, res = 1; if(is_Block(pos)) { @@ -644,8 +652,8 @@ can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * } #endif - for(i=0, n=get_irn_arity(op); i=0 && res; --n) { + const ir_node *arg = get_irn_n(op, n); #ifdef NO_ENLARGE_L1V3N355 if(has_reg_class(si, arg) && live) { @@ -706,6 +714,8 @@ insert_copy_before(const spill_ilp_t * si, const ir_node * irn, ir_node * pos) bb = is_Block(pos)?pos:get_nodes_block(pos); copy = exact_copy(irn); + + _set_phi_class(copy, NULL); set_nodes_block(copy, bb); sched_put_before(si, pos, copy); @@ -723,13 +733,15 @@ insert_copy_after(const spill_ilp_t * si, const ir_node * irn, ir_node * pos) bb = is_Block(pos)?pos:get_nodes_block(pos); copy = exact_copy(irn); + + _set_phi_class(copy, NULL); set_nodes_block(copy, bb); sched_put_after(pos, copy); return copy; } -static void +static ir_node * insert_remat_after(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live) { char buf[256]; @@ -743,7 +755,6 @@ insert_remat_after(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, copy = insert_copy_after(si, remat->op, pos); -// ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", remat->value, pos); ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", copy, pos); op = obstack_alloc(si->obst, sizeof(*op)); op->is_remat = 1; @@ -761,10 +772,14 @@ insert_remat_after(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, } else { proj_copy = NULL; } + + return copy; } + + return NULL; } -static void +static ir_node * insert_remat_before(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live) { char buf[256]; @@ -778,7 +793,6 @@ insert_remat_before(spill_ilp_t * si, const remat_t * remat, const ir_node * pos copy = insert_copy_before(si, remat->op, pos); -// ir_snprintf(buf, sizeof(buf), "remat_%N_%N", remat->value, pos); ir_snprintf(buf, sizeof(buf), "remat_%N_%N", copy, pos); op = obstack_alloc(si->obst, sizeof(*op)); op->is_remat = 1; @@ -796,10 +810,15 @@ insert_remat_before(spill_ilp_t * si, const remat_t * remat, const ir_node * pos } else { proj_copy = NULL; } + + return copy; } + + return NULL; } -static int get_block_n_succs(ir_node *block) { +static int +get_block_n_succs(const ir_node *block) { const ir_edge_t *edge; assert(edges_activated(current_ir_graph)); @@ -812,6 +831,57 @@ static int get_block_n_succs(ir_node *block) { return edge ? 2 : 1; } +static int +is_merge_edge(const ir_node * bb) +{ +#ifdef GOODWIN_REDUCTION + return get_block_n_succs(bb) == 1; +#else + return 1; +#endif +} + +static int +is_diverge_edge(const ir_node * bb) +{ +#ifdef GOODWIN_REDUCTION + return get_Block_n_cfgpreds(bb) == 1; +#else + return 1; +#endif +} + +static void +walker_regclass_copy_insertor(ir_node * irn, void * data) +{ + spill_ilp_t *si = data; + + if(is_Phi(irn) && has_reg_class(si, irn)) { + int n; + + for(n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *phi_arg = get_irn_n(irn, n); + ir_node *bb = get_Block_cfgpred_block(get_nodes_block(irn), n); + + if(!has_reg_class(si, phi_arg)) { + ir_node *copy = be_new_Copy(si->cls, si->chordal_env->irg, bb, phi_arg); + ir_node *pos = sched_block_last_noncf(si, bb); + op_t *op = obstack_alloc(si->obst, sizeof(*op)); + + DBG((si->dbg, LEVEL_2, "\t copy to my regclass for arg %+F of %+F\n", phi_arg, irn)); + sched_add_after(pos, copy); + set_irn_n(irn, n, copy); + + op->is_remat = 0; + op->attr.live_range.args.reloads = NULL; + op->attr.live_range.ilp = ILP_UNDEF; + set_irn_link(copy, op); + } + } + } +} + + /** * Insert (so far unused) remats into the irg to * recompute the potential liveness of all values @@ -822,8 +892,7 @@ walker_remat_insertor(ir_node * bb, void * data) spill_ilp_t *si = data; spill_bb_t *spill_bb; ir_node *irn; - int i, - n; + int n; irn_live_t *li; pset *live = pset_new_ptr_default(); @@ -847,6 +916,7 @@ walker_remat_insertor(ir_node * bb, void * data) op_t *op; pset *args; ir_node *arg; + pset *remat_args; next = sched_prev(irn); @@ -861,7 +931,7 @@ walker_remat_insertor(ir_node * bb, void * data) op = obstack_alloc(si->obst, sizeof(*op)); op->is_remat = 0; - op->attr.live_range.reloads = NULL; + op->attr.live_range.args.reloads = NULL; op->attr.live_range.ilp = ILP_UNDEF; set_irn_link(irn, op); @@ -872,27 +942,34 @@ walker_remat_insertor(ir_node * bb, void * data) op = obstack_alloc(si->obst, sizeof(*op)); op->is_remat = 0; op->attr.live_range.ilp = ILP_UNDEF; - op->attr.live_range.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.reloads) * get_irn_arity(irn)); - memset(op->attr.live_range.reloads, 0xFF, sizeof(*op->attr.live_range.reloads) * get_irn_arity(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)); set_irn_link(irn, op); args = pset_new_ptr_default(); /* collect arguments of op */ - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *arg = get_irn_n(irn, i); + 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 live in epilog */ + /* set args of op already live in epilog */ pset_foreach(args, arg) { if(has_reg_class(si, arg)) { pset_insert_ptr(live, arg); } } + /* delete defined value from live set */ + if(has_reg_class(si, irn)) { + pset_remove_ptr(live, irn); + } - /* insert all possible remats after irn */ + + remat_args = pset_new_ptr_default(); + + /* insert all possible remats before irn */ pset_foreach(args, arg) { remat_info_t *remat_info, query; @@ -912,39 +989,48 @@ walker_remat_insertor(ir_node * bb, void * data) 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) { + pset_foreach(remat_info->remats, remat) { + ir_node *remat_irn = NULL; - 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)); + DBG((si->dbg, LEVEL_4, "\t considering remat %+F for arg %+F\n", remat->op, arg)); #ifdef REMAT_WHILE_LIVE - if(pset_find_ptr(live, remat->value)) { - insert_remat_after(si, remat, irn, live); - } + if(pset_find_ptr(live, remat->value)) { + remat_irn = insert_remat_before(si, remat, irn, live); + } #else - insert_remat_after(si, remat, irn, live); + remat_irn = insert_remat_before(si, remat, irn, live); #endif + 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); + } } } } } - /* delete defined value from live set */ - if(has_reg_class(si, irn)) { - pset_remove_ptr(live, irn); + /* 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); } - /* insert all possible remats before irn */ + /* insert all possible remats after 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; @@ -957,20 +1043,27 @@ walker_remat_insertor(ir_node * bb, void * data) continue; } - if(remat_info->remats) { - pset_foreach(remat_info->remats, remat) { - DBG((si->dbg, LEVEL_4, "\t considering remat %+F for arg %+F\n", remat->op, arg)); + /* 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)); #ifdef REMAT_WHILE_LIVE - if(pset_find_ptr(live, remat->value)) { - insert_remat_before(si, remat, irn, live); - } + if(pset_find_ptr(live, remat->value)) { + insert_remat_after(si, remat, irn, live); + } #else - insert_remat_before(si, remat, irn, live); + insert_remat_after(si, remat, irn, live); #endif + } } } } + del_pset(remat_args); del_pset(args); irn = next; } @@ -978,10 +1071,8 @@ walker_remat_insertor(ir_node * bb, void * data) live_foreach(bb, li) { ir_node *value = (ir_node *) li->irn; -#ifdef GOODWIN_REDUCTION /* add remats at end if successor has multiple predecessors */ - if(get_block_n_succs(bb) == 1 && get_Block_n_cfgpreds(get_block_succ_first(bb)->src) > 1) { -#endif + if(is_merge_edge(bb)) { /* add remats at end of block */ if (live_is_end(li) && has_reg_class(si, value)) { remat_info_t *remat_info, @@ -1001,11 +1092,8 @@ walker_remat_insertor(ir_node * bb, void * data) } } } - -#ifdef GOODWIN_REDUCTION } - if(get_Block_n_cfgpreds(bb) == 1 && get_block_n_succs(get_Block_cfgpred_block(bb,0)) > 1) { -#endif + if(is_diverge_edge(bb)) { /* add remat2s at beginning of block */ if ((live_is_in(li) || (is_Phi(value) && get_nodes_block(value)==bb)) && has_reg_class(si, value)) { remat_info_t *remat_info, @@ -1027,11 +1115,7 @@ walker_remat_insertor(ir_node * bb, void * data) } } } - -#ifdef GOODWIN_REDUCTION } -#endif - } } @@ -1066,59 +1150,117 @@ luke_endwalker(ir_node * bb, void * data) } /* collect values used by cond jumps etc. at bb end (use_end) -> always live */ - /* their reg_out is unimportant because it can always be set */ + /* their reg_out must always be set */ sched_foreach_reverse(bb, irn) { - int i, - n; + int n; if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break; - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *irn_arg = get_irn_n(irn, i); + 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)) { - pset_insert_ptr(use_end, irn); + pset_insert_ptr(use_end, irn_arg); } } } ir_snprintf(buf, sizeof(buf), "check_end_%N", bb); + //cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs); cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - pset_count(use_end)); - spill_bb->ilp = new_set(cmp_spill, 16); + spill_bb->ilp = new_set(cmp_spill, pset_count(live)+pset_count(use_end)); - live_foreach(bb, li) { - irn = (ir_node *) li->irn; - if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { - spill_t query, - *spill; + /* if this is a merge edge we can reload at the end of this block */ + if(is_merge_edge(bb)) { + spill_bb->reloads = new_set(cmp_keyval, pset_count(live)+pset_count(use_end)); + } else if(pset_count(use_end)){ + spill_bb->reloads = new_set(cmp_keyval, pset_count(use_end)); + } else { + spill_bb->reloads = NULL; + } - query.irn = irn; - spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); + pset_foreach(live,irn) { + spill_t query, + *spill; + double spill_cost; - ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb); - spill->reg_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - /* if irn is used at the end of the block, then it is live anyway */ - if(!pset_find_ptr(use_end, irn)) - 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(si->lpp, buf, lpp_binary, 0.0); + /* handle values used by control flow nodes later separately */ + if(pset_find_ptr(use_end, irn)) continue; + + query.irn = irn; + spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); + + spill_cost = is_Unknown(irn)?0.0001:COST_STORE*execution_frequency(si, bb); + + ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb); + spill->reg_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + 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(si->lpp, buf, lpp_binary, 0.0); -#ifdef GOODWIN_REDUCTION - if(get_Block_n_cfgpreds(bb) == 1 && get_block_n_succs(get_Block_cfgpred_block(bb,0)) > 1) { - ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, bb)); - } else { - spill->spill = ILP_UNDEF; - } -#else ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, bb)); -#endif + spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, spill_cost); - spill->reg_in = ILP_UNDEF; - spill->mem_in = ILP_UNDEF; - } + if(is_merge_edge(bb)) { + ilp_var_t reload; + ilp_cst_t rel_cst; + + ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn); + reload = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb)); + set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload)); + + /* reload <= mem_out */ + rel_cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, rel_cst, reload, 1.0); + lpp_set_factor_fast(si->lpp, rel_cst, spill->mem_out, -1.0); + } + + spill->reg_in = ILP_UNDEF; + spill->mem_in = ILP_UNDEF; + } + + pset_foreach(use_end,irn) { + spill_t query, + *spill; + double spill_cost; + ilp_cst_t end_use_req, + rel_cst; + ilp_var_t reload; + + query.irn = irn; + spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); + + spill_cost = is_Unknown(irn)?0.0001:COST_STORE*execution_frequency(si, bb); + + ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb); + spill->reg_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.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(si->lpp, buf, lpp_binary, 0.0); + + ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); + spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, spill_cost); + + ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn); + reload = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb)); + set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload)); + + /* reload <= mem_out */ + rel_cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, rel_cst, reload, 1.0); + lpp_set_factor_fast(si->lpp, rel_cst, spill->mem_out, -1.0); + + spill->reg_in = ILP_UNDEF; + spill->mem_in = ILP_UNDEF; + + ir_snprintf(buf, sizeof(buf), "req_cf_end_%N_%N", irn, bb); + end_use_req = lpp_add_cst(si->lpp, buf, lpp_equal, 1); + lpp_set_factor_fast(si->lpp, end_use_req, spill->reg_out, 1.0); } del_pset(live); @@ -1201,25 +1343,6 @@ find_post_remat(const ir_node * value, const ir_node * pos) return NULL; } -/** - * Find a remat of value @p value in the prolog of @p pos - */ -static ir_node * -find_pre_remat(const spill_ilp_t * si, const ir_node * value, const ir_node * pos) -{ - while((pos = next_pre_remat(si,pos)) != NULL) { - op_t *op; - - op = get_irn_link(pos); - assert(op->is_remat && op->attr.remat.pre); - - if(op->attr.remat.remat->value == value) - return (ir_node*)pos; - } - - return NULL; -} - static spill_t * add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) { @@ -1231,6 +1354,8 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) query.irn = irn; spill = set_find(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); if(!spill) { + double spill_cost = is_Unknown(irn)?0.0001:COST_STORE*execution_frequency(si, bb); + spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); spill->reg_out = ILP_UNDEF; @@ -1240,323 +1365,528 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", irn, bb); spill->mem_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); -#ifdef GOODWIN_REDUCTION - if(get_Block_n_cfgpreds(bb) == 1 && get_block_n_succs(get_Block_cfgpred_block(bb,0)) > 1) { - ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, bb)); - } else { - spill->spill = ILP_UNDEF; - } -#else ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, bb)); -#endif + spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, spill_cost); } return spill; } -/** - * Walk all irg blocks and emit this ILP - */ static void -luke_blockwalker(ir_node * bb, void * data) +get_live_end(spill_ilp_t * si, ir_node * bb, pset * live) { - spill_ilp_t *si = (spill_ilp_t*)data; - ir_node *irn; irn_live_t *li; - pset *live; - char buf[256]; - ilp_cst_t cst; - spill_bb_t *spill_bb = get_irn_link(bb); - int i; - ir_node *tmp; - spill_t *spill; - - - live = pset_new_ptr_default(); - - /* do something at the end of the block */ + ir_node *irn; - /* init live values at end of block */ live_foreach(bb, li) { - ir_node *irn = (ir_node *) li->irn; + irn = (ir_node *) li->irn; if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { pset_insert_ptr(live, irn); } } -#ifdef GOODWIN_REDUCTION - if(get_block_n_succs(bb) == 1 && get_Block_n_cfgpreds(get_block_succ_first(bb)->src) > 1) { - spill_bb->reloads = obstack_alloc(si->obst, pset_count(live) * sizeof(*spill_bb->reloads)); - memset(spill_bb->reloads, 0xFF, pset_count(live) * sizeof(*spill_bb->reloads)); - } else { - spill_bb->reloads = NULL; - } -#else - spill_bb->reloads = obstack_alloc(si->obst, pset_count(live) * sizeof(*spill_bb->reloads)); - memset(spill_bb->reloads, 0xFF, pset_count(live) * sizeof(*spill_bb->reloads)); -#endif + irn = sched_last(bb); - i=0; - live_foreach(bb, li) { - ir_node *irn = (ir_node *) li->irn; - op_t *op; + /* all values eaten by control flow operations are also live until the end of the block */ + sched_foreach_reverse(bb, irn) { + int i; - if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { - spill = set_find_spill(spill_bb->ilp, irn); - assert(spill); + if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break; - if(spill_bb->reloads) { - ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn); - spill_bb->reloads[i] = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb)); + for(i=get_irn_arity(irn)-1; i>=0; --i) { + ir_node *arg = get_irn_n(irn,i); - /* reload <= mem_out */ - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, spill_bb->reloads[i], 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0); + if(has_reg_class(si, arg)) { + pset_insert_ptr(live, arg); } + } + } +} - op = get_irn_link(irn); - assert(!op->is_remat); +/** + * Inserts ILP-constraints and variables for memory copying before the given position + */ +static void +insert_mem_copy_position(spill_ilp_t * si, pset * live, const ir_node * block) +{ + const ir_node *succ; + const ir_edge_t *edge; + spill_bb_t *spill_bb = get_irn_link(block); + ir_node *phi; + int pos; + ilp_cst_t cst; + ilp_var_t copyreg; + char buf[256]; + ir_node *tmp; - ir_snprintf(buf, sizeof(buf), "lr_%N_%N", irn, bb); - op->attr.live_range.ilp = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - op->attr.live_range.op = bb; - ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", bb, irn); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + assert(edges_activated(current_ir_graph)); - /* reg_out - reload - remat - live_range <= 0 */ - lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0); - if(spill_bb->reloads) lpp_set_factor_fast(si->lpp, cst, spill_bb->reloads[i], -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); - } - } + edge = get_block_succ_first(block); + if(!edge) return; - ++i; - } - } - DBG((si->dbg, LEVEL_4, "\t %d values live at end of block %+F\n", pset_count(live), bb)); + succ = edge->src; + pos = edge->pos; - sched_foreach_reverse(bb, irn) { - op_t *op; - op_t *tmp_op; - int n, - k, - d = 0; - ilp_cst_t check_pre, - check_post; -#ifdef CHECK_POST_REMAT - ilp_cst_t check_post_remat; + edge = get_block_succ_next(block, edge); + /* next block can only contain phis, if this is a merge edge */ + if(edge) return; + + ir_snprintf(buf, sizeof(buf), "copyreg_%N", block); + copyreg = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + + ir_snprintf(buf, sizeof(buf), "check_copyreg_%N", block); + cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs); + + pset_foreach(live, tmp) { + spill_t *spill; +#if 0 + op_t *op = get_irn_link(irn); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, 1.0); #endif - set *args = new_set(cmp_keyval, get_irn_arity(irn)); - keyval_t *keyval; + spill = set_find_spill(spill_bb->ilp, tmp); + assert(spill); - if(is_Phi(irn)) - break; + lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0); + } + lpp_set_factor_fast(si->lpp, cst, copyreg, 1.0); - op = get_irn_link(irn); - /* skip remats */ - if(op->is_remat) continue; - DBG((si->dbg, LEVEL_4, "\t at node %+F\n", irn)); + sched_foreach(succ, phi) { + const ir_node *to_copy; + op_t *to_copy_op; + spill_t *to_copy_spill; + op_t *phi_op = get_irn_link(phi); + ilp_var_t reload = ILP_UNDEF; + + if(!is_Phi(phi)) break; + 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); + assert(to_copy_spill); + + if(spill_bb->reloads) { + keyval_t *keyval = set_find_keyval(spill_bb->reloads, to_copy); + + if(keyval) { + reload = PTR_TO_INT(keyval->val); + } + } + + ir_snprintf(buf, sizeof(buf), "req_copy_%N_%N", block, to_copy); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + /* copy - reg_out - reload - remat - live_range <= 0 */ + lpp_set_factor_fast(si->lpp, cst, phi_op->attr.live_range.args.copies[pos], 1.0); + lpp_set_factor_fast(si->lpp, cst, to_copy_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, to_copy_op->attr.live_range.ilp, -1.0); + foreach_pre_remat(si, block, tmp) { + op_t *remat_op = get_irn_link(tmp); + if(remat_op->attr.remat.remat->value == to_copy) { + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); + } + } + + ir_snprintf(buf, sizeof(buf), "copyreg_%N_%N", block, to_copy); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + /* copy - reg_out - copyreg <= 0 */ + lpp_set_factor_fast(si->lpp, cst, phi_op->attr.live_range.args.copies[pos], 1.0); + lpp_set_factor_fast(si->lpp, cst, to_copy_spill->reg_out, -1.0); + lpp_set_factor_fast(si->lpp, cst, copyreg, -1.0); + } +} + + +/** + * Walk all irg blocks and emit this ILP + */ +static void +luke_blockwalker(ir_node * bb, void * data) +{ + spill_ilp_t *si = (spill_ilp_t*)data; + ir_node *irn; + pset *live; + char buf[256]; + ilp_cst_t cst; + spill_bb_t *spill_bb = get_irn_link(bb); + ir_node *tmp; + spill_t *spill; + pset *defs = pset_new_ptr_default(); + + + live = pset_new_ptr_default(); + + /**************************************** + * B A S I C B L O C K E N D + ***************************************/ + + + /* init live values at end of block */ + get_live_end(si, bb, live); + + pset_foreach(live, irn) { + op_t *op; + ilp_var_t reload = ILP_UNDEF; + + spill = set_find_spill(spill_bb->ilp, irn); + assert(spill); + + if(spill_bb->reloads) { + keyval_t *keyval = set_find_keyval(spill_bb->reloads, irn); + + if(keyval) { + reload = PTR_TO_INT(keyval->val); + } + } + + op = get_irn_link(irn); + assert(!op->is_remat); + + ir_snprintf(buf, sizeof(buf), "lr_%N_%N", irn, bb); + op->attr.live_range.ilp = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + op->attr.live_range.op = bb; + + ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", bb, irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + /* reg_out - 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); + } + } + /* maybe we should also assure that reg_out >= live_range etc. */ + } + +#ifndef NO_MEMCOPIES + insert_mem_copy_position(si, live, bb); +#endif + + /* + * start new live ranges for values used by remats at end of block + * and assure the remat args are available + */ + foreach_pre_remat(si, bb, tmp) { + op_t *remat_op = get_irn_link(tmp); + int n; + + 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(si->lpp, buf, lpp_binary, 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)); + + pset_insert_ptr(live, remat_arg); + add_to_spill_bb(si, bb, remat_arg); + } + + /* 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, arg_op->attr.live_range.ilp, -1.0); + + /* use reload placed for this argument */ + 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, cst, reload, -1.0); + } + } + } + } + DBG((si->dbg, LEVEL_4, "\t %d values live at end of block %+F\n", pset_count(live), bb)); + + + + + /************************************** + * B A S I C B L O C K B O D Y + **************************************/ + + sched_foreach_reverse_from(sched_block_last_noncf(si, bb), irn) { + op_t *op; + op_t *tmp_op; + int n, + u = 0, + d = 0; + ilp_cst_t check_pre, + check_post; + set *args; + pset *used; + pset *remat_defs; + keyval_t *keyval; + + /* iterate only until first phi */ + if(is_Phi(irn)) + break; + + 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 */ if(has_reg_class(si, irn)) { - assert(pset_find_ptr(live, irn)); - pset_remove_ptr(live, irn); + pset_insert_ptr(defs, irn); } - /* init set of irn's arguments */ - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *irn_arg = get_irn_n(irn, i); + /* skip projs */ + if(is_Proj(irn)) continue; + + /* + * init set of irn's arguments + * and all possibly used values around this op + * and values defined by post remats + */ + args = new_set(cmp_keyval, get_irn_arity(irn)); + 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*)i); + 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); -#ifdef CHECK_POST_REMAT - /* check the register pressure after the epilog */ - ir_snprintf(buf, sizeof(buf), "check_post_remat_%N", irn); - check_post_remat = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs); + pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value); - /* iterate over L\U */ - pset_foreach(live, tmp) { - if(!set_find_keyval(args, tmp)) { - /* if a live value is not used by irn */ - tmp_op = get_irn_link(tmp); -// assert(tmp_op->attr.live_range.op != irn); - lpp_set_factor_fast(si->lpp, check_post_remat, tmp_op->attr.live_range.ilp, 1.0); + 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); + } } } - /* iterate over following remats and remove possibly defined values again from check_post_remat */ - foreach_post_remat(irn, tmp) { - op_t *remat_op = get_irn_link(tmp); - const ir_node *value = remat_op->attr.remat.remat->value; - op_t *val_op = get_irn_link(value); - assert(remat_op->is_remat && !remat_op->attr.remat.pre); + /********************************** + * I N E P I L O G O F irn + **********************************/ - /* values that are defined by remat2s are not counted */ -#ifdef REMAT_WHILE_LIVE - assert(val_op->attr.live_range.ilp); - lpp_set_factor_fast(si->lpp, check_post_remat, val_op->attr.live_range.ilp, 0.0); -#else - if(val_op->attr.live_range.ilp != ILP_UNDEF) { - lpp_set_factor_fast(si->lpp, check_post_remat, val_op->attr.live_range.ilp, 0.0); + /* ensure each dying value is used by only one post remat */ + pset_foreach(used, tmp) { + ir_node *value = tmp; + op_t *value_op = get_irn_link(value); + ir_node *remat; + int n_remats = 0; + + cst = ILP_UNDEF; + foreach_post_remat(irn, remat) { + op_t *remat_op = get_irn_link(remat); + + for(n=get_irn_arity(remat)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(remat, n); + + /* if value is used by this remat add it to constraint */ + if(remat_arg == value) { + if(n_remats == 0) { + /* sum remat2s <= 1 + n_remats*live_range */ + ir_snprintf(buf, sizeof(buf), "dying_lr_%N_%N", value, irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 1.0); + } + + n_remats++; + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + break; + } + } + } + + // 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); } -#endif /* REMAT_WHILE_LIVE */ } -#endif /* CHECK_POST_REMAT */ + /* ensure at least one value dies at post remat */ + foreach_post_remat(irn, 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)) { + + /* does arg always die at this op? */ + if(!pset_find_ptr(live, remat_arg)) + goto skip_one_must_die; + + pset_insert_ptr(remat_args, remat_arg); + } + } + + /* remat + \sum live_range(remat_arg) <= |args| */ + ir_snprintf(buf, sizeof(buf), "one_must_die_%+F", tmp); + cst = lpp_add_cst(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) { + op_t *arg_op = get_irn_link(remat_arg); + + lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0); + } + +skip_one_must_die: + del_pset(remat_args); + } - /* new live ranges for values from L\U defined by remat2s or used by remats */ + /* new live ranges for values from L\U defined by post remats */ pset_foreach(live, tmp) { - ir_node *value = tmp;//remat_op->attr.remat.remat->value; + ir_node *value = tmp; op_t *value_op = get_irn_link(value); - if(!set_find_keyval(args, value)) { + if(!set_find_keyval(args, value) && !pset_find_ptr(defs, value)) { ilp_var_t prev_lr = ILP_UNDEF; ir_node *remat; - cst = ILP_UNDEF; - - foreach_post_remat(irn, remat) { - op_t *remat_op = get_irn_link(remat); - - /* if value is being rematerialized by this remat */ - if(value == remat_op->attr.remat.remat->value) { - if(cst == ILP_UNDEF) { - /* next_live_range <= prev_live_range + sum remat2s */ - ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - ir_snprintf(buf, sizeof(buf), "lr_%N_%N", value, irn); - prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0); - lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0); - } - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); - } - } + if(pset_find_ptr(remat_defs, value)) { + + /* next_live_range <= prev_live_range + sum remat2s */ + ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + ir_snprintf(buf, sizeof(buf), "lr_%N_%N", value, irn); + prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); -#ifdef MAY_DIE_AT_PRE_REMAT - if(cst == ILP_UNDEF) { - foreach_pre_remat(si, irn, remat) { - int i, - n; - - for (i = 0, n = get_irn_arity(remat); i < n; ++i) { - ir_node *remat_arg = get_irn_n(remat, i); - - /* if value is being used by this remat */ - if(value == remat_arg) { - /* next_live_range <= prev_live_range */ - ir_snprintf(buf, sizeof(buf), "lr_%N_%N", value, irn); - prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - - ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0); - lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0); - goto fertig; - } - /* TODO check afterwards whether lr dies after a pre-remat (should not happen) */ + lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0); + + foreach_post_remat(irn, remat) { + op_t *remat_op = get_irn_link(remat); + + /* if value is being rematerialized by this remat */ + if(value == remat_op->attr.remat.remat->value) { + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); } } - } -#endif -fertig: - if(prev_lr != ILP_UNDEF) { value_op->attr.live_range.ilp = prev_lr; value_op->attr.live_range.op = irn; } } } - /* get count of values in my register class defined by irn */ - /* also add defined values to check_post_remat; do this before iterating over args */ - if(get_irn_mode(irn) == mode_T) { - ir_node *proj = sched_next(irn); - op_t *proj_op = get_irn_link(proj); + /* requirements for post remats and start live ranges from L/U' for values dying here */ + foreach_post_remat(irn, tmp) { + op_t *remat_op = get_irn_link(tmp); + int n; - while(is_Proj(proj)) { - if(has_reg_class(si, proj)) { - ++d; -#ifdef CHECK_POST_REMAT - lpp_set_factor_fast(si->lpp, check_post_remat, proj_op->attr.live_range.ilp, 1.0); -#endif + 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); + + if(!has_reg_class(si, remat_arg)) continue; + + /* only for values in L\U (TODO and D?), the others are handled with post_use */ + if(!pset_find_ptr(used, remat_arg)) { + /* remat <= live_range(remat_arg) */ + ir_snprintf(buf, sizeof(buf), "req_remat2_%N_arg_%N", tmp, remat_arg); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + /* if value is becoming live through use by remat2 */ + if(!pset_find_ptr(live, remat_arg)) { + ilp_var_t lr; + + ir_snprintf(buf, sizeof(buf), "lr_%N_%N", remat_arg, irn); + lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + + arg_op->attr.live_range.ilp = lr; + arg_op->attr.live_range.op = irn; + + DBG((si->dbg, LEVEL_3, " value %+F becoming live through use by remat2 %+F\n", remat_arg, tmp)); + + pset_insert_ptr(live, remat_arg); + add_to_spill_bb(si, bb, remat_arg); + } + + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0); } - proj = sched_next(proj); - proj_op = get_irn_link(proj); - } - } else { - if(has_reg_class(si, irn)) { - d = 1; -#ifdef CHECK_POST_REMAT - lpp_set_factor_fast(si->lpp, check_post_remat, op->attr.live_range.ilp, 1.0); -#endif } } + + d = pset_count(defs); DBG((si->dbg, LEVEL_4, "\t %+F produces %d values in my register class\n", irn, d)); /* count how many regs irn needs for arguments */ - k = set_count(args); + u = set_count(args); - /* check the register pressure in the prolog */ - /* sum_{L\U} lr <= n - |U| */ - ir_snprintf(buf, sizeof(buf), "check_pre_%N", irn); - check_pre = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - k); /* check the register pressure in the epilog */ + /* sum_{L\U'} lr + sum_{U'} post_use <= k - |D| */ ir_snprintf(buf, sizeof(buf), "check_post_%N", irn); check_post = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - d); - set_foreach(args, keyval) { - ilp_var_t next_lr; - op_t *arg_op; + /* add L\U' to check_post */ + pset_foreach(live, tmp) { + if(!pset_find_ptr(used, tmp) && !pset_find_ptr(defs, tmp)) { + /* if a live value is not used by irn */ + tmp_op = get_irn_link(tmp); + lpp_set_factor_fast(si->lpp, check_post, tmp_op->attr.live_range.ilp, 1.0); + } + } + + /*********************************************************** + * I T E R A T I O N O V E R U S E S F O R E P I L O G + **********************************************************/ + + + pset_foreach(used, tmp) { + ilp_var_t prev_lr; ilp_var_t post_use; int p = 0; spill_t *spill; - ir_node *arg = keyval->key; + ir_node *arg = tmp; + op_t *arg_op = get_irn_link(arg); + ir_node *remat; spill = add_to_spill_bb(si, bb, arg); + /* new live range for each used value */ ir_snprintf(buf, sizeof(buf), "lr_%N_%N", arg, irn); - next_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - - i = (int)keyval->val; - assert(ilpp, buf, lpp_binary, 0.0); - ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn); - op->attr.live_range.reloads[i] = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, irn)); - - /* reload <= mem_out */ - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[i], 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0); - - arg_op = get_irn_link(arg); - - /* requirement: arg must be in register for use */ - /* reload + remat + live_range == 1 */ - ir_snprintf(buf, sizeof(buf), "req_%N_%N", irn, arg); - cst = lpp_add_cst(si->lpp, buf, lpp_equal, 1.0); - - lpp_set_factor_fast(si->lpp, cst, next_lr, 1.0); - lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[i], 1.0); - foreach_pre_remat(si, irn, tmp) { - op_t *remat_op = get_irn_link(tmp); - if(remat_op->attr.remat.remat->value == arg) { - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); - } - } - - /* the epilog stuff - including post_use, post, post_remat */ + /* the epilog stuff - including post_use, check_post, check_post_remat */ ir_snprintf(buf, sizeof(buf), "post_use_%N_%N", arg, irn); post_use = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); @@ -1566,24 +1896,42 @@ fertig: if(pset_find_ptr(live, arg)) { DBG((si->dbg, LEVEL_3, "\t arg %+F is possibly live in epilog of %+F\n", arg, irn)); + /* post_use >= next_lr + remat */ ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++); cst = lpp_add_cst(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); -#ifdef CHECK_POST_REMAT - lpp_set_factor_fast(si->lpp, check_post_remat, arg_op->attr.live_range.ilp, 1.0); -#endif } - /*forall remat2 which use arg add a similar cst*/ - foreach_post_remat(irn, tmp) { - int i, - n; + /* if value is not an arg of op and not possibly defined by post remat + * then it may only die and not become live + */ + if(!set_find_keyval(args, arg)) { + /* post_use <= prev_lr */ + ir_snprintf(buf, sizeof(buf), "req_post_use_%N_%N", arg, irn); + cst = lpp_add_cst(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, prev_lr, -1.0); + + if(!pset_find_ptr(remat_defs, arg) && pset_find_ptr(live, arg)) { + /* next_lr <= prev_lr */ + ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", arg, irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0); + } + } - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *remat_arg = get_irn_n(tmp, i); - op_t *remat_op = get_irn_link(tmp); + + + /* 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)); @@ -1596,40 +1944,73 @@ fertig: } } - /* new live range begins for each argument */ - arg_op->attr.live_range.ilp = next_lr; + /* new live range begins for each used value */ + 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); + } - /* start new live ranges for values used by remats */ - foreach_pre_remat(si, irn, tmp) { - int i, - n; + /* just to be sure */ + check_post = ILP_UNDEF; - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *remat_arg = get_irn_n(tmp, i); - 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_%N", remat_arg, irn); - prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - arg_op->attr.live_range.ilp = prev_lr; - arg_op->attr.live_range.op = irn; + /****************** + * P R O L O G + ******************/ + + /* check the register pressure in the prolog */ + /* sum_{L\U} lr <= k - |U| */ + ir_snprintf(buf, sizeof(buf), "check_pre_%N", irn); + check_pre = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - u); + + /* for the prolog remove defined values from the live set */ + pset_foreach(defs, tmp) { + pset_remove_ptr(live, tmp); + } + + /*********************************************************** + * I T E R A T I O N O V E R A R G S F O R P R O L O G + **********************************************************/ + + + set_foreach(args, keyval) { + spill_t *spill; + ir_node *arg = keyval->key; + int i = PTR_TO_INT(keyval->val); + op_t *arg_op = get_irn_link(arg); + + spill = set_find_spill(spill_bb->ilp, arg); + assert(spill); + + ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn); + op->attr.live_range.args.reloads[i] = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb)); + + /* reload <= mem_out */ + ir_snprintf(buf, sizeof(buf), "req_reload_%N_%N", arg, irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.args.reloads[i], 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0); - DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat %+F\n", remat_arg, tmp)); + /* requirement: arg must be in register for use */ + /* reload + remat + live_range == 1 */ + ir_snprintf(buf, sizeof(buf), "req_%N_%N", irn, arg); + cst = lpp_add_cst(si->lpp, buf, lpp_equal, 1.0); - /* TODO ist das hier die richtige Stelle???? */ - pset_insert_ptr(live, remat_arg); - add_to_spill_bb(si, bb, remat_arg); + lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.args.reloads[i], 1.0); + foreach_pre_remat(si, irn, tmp) { + op_t *remat_op = get_irn_link(tmp); + if(remat_op->attr.remat.remat->value == arg) { + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); } - /* TODO check afterwards whether lr dies after a pre-remat (should not happen) */ } } @@ -1638,21 +2019,21 @@ fertig: if(!set_find_keyval(args, tmp)) { /* if a live value is not used by irn */ tmp_op = get_irn_link(tmp); -// assert(tmp_op->attr.live_range.op != irn); lpp_set_factor_fast(si->lpp, check_pre, tmp_op->attr.live_range.ilp, 1.0); - lpp_set_factor_fast(si->lpp, check_post, tmp_op->attr.live_range.ilp, 1.0); } } + /* 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 i, - n; + int n; - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *remat_arg = get_irn_n(tmp, i); + 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; @@ -1667,68 +2048,17 @@ fertig: if((keyval = set_find_keyval(args, remat_arg)) != NULL) { int index = (int)keyval->val; - lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[index], -1.0); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.args.reloads[index], -1.0); } } } - /* requirements for remats2 - * - * TODO unsure if this does the right thing. - * should insert values into set if they do not become live through remat and - * op - */ - foreach_post_remat(irn, tmp) { - op_t *remat_op = get_irn_link(tmp); - int i, - n; - - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *remat_arg = get_irn_n(tmp, i); - op_t *arg_op = get_irn_link(remat_arg); - - if(!has_reg_class(si, remat_arg)) continue; - - /* only for values in L\U, the others are handled with post_use */ - if(!set_find_keyval(args, remat_arg)) { - /* remat <= live_rang(remat_arg) */ - ir_snprintf(buf, sizeof(buf), "req_remat2_%N_arg_%N", tmp, remat_arg); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - - /* if value is becoming live through use by remat2 */ - if(!pset_find_ptr(live, remat_arg)) { - ilp_var_t lr; - - ir_snprintf(buf, sizeof(buf), "lr_%N_%N", remat_arg, irn); - lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - - arg_op->attr.live_range.ilp = lr; - arg_op->attr.live_range.op = irn; - - DBG((si->dbg, LEVEL_3, " value %+F becoming live through use by remat2 %+F\n", remat_arg, tmp)); - - pset_insert_ptr(live, remat_arg); - add_to_spill_bb(si, bb, remat_arg); - } - - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); - lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0); - } - } - } -#ifdef CHECK_POST_REMAT - /* iterate over following remats and add them to check_post_remat */ - foreach_post_remat(irn, tmp) { - op_t *remat_op = get_irn_link(tmp); - - assert(remat_op->is_remat && !remat_op->attr.remat.pre); - - lpp_set_factor_fast(si->lpp, check_post_remat, remat_op->attr.remat.ilp, 1.0); - } -#endif + /************************* + * D O N E W I T H O P + *************************/ DBG((si->dbg, LEVEL_4, "\t %d values live at %+F\n", pset_count(live), irn)); @@ -1736,18 +2066,25 @@ fertig: assert(has_reg_class(si, tmp)); } - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *arg = get_irn_n(irn, i); + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *arg = get_irn_n(irn, n); assert(!find_post_remat(arg, irn) && "there should be no post remat for an argument of an op"); } + del_pset(remat_defs); + del_pset(used); del_set(args); + del_pset(defs); + defs = pset_new_ptr_default(); } - /* do something at the beginning of the block */ + /*************************************** + * B E G I N N I N G O F B L O C K + ***************************************/ + /* we are now at the beginning of the basic block, there are only \Phis in front of us */ DBG((si->dbg, LEVEL_3, "\t %d values live at beginning of block %+F\n", pset_count(live), bb)); @@ -1763,17 +2100,61 @@ fertig: cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); lpp_set_factor_fast(si->lpp, cst, spill->mem_out, 1.0); - if(spill->spill != ILP_UNDEF) { - lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0); - } + lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0); if(pset_find_ptr(live, spill->irn)) { DBG((si->dbg, LEVEL_5, "\t %+F live at beginning of block %+F\n", spill->irn, bb)); ir_snprintf(buf, sizeof(buf), "mem_in_%N_%N", spill->irn, bb); spill->mem_in = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); - lpp_set_factor_fast(si->lpp, cst, spill->mem_in, -1.0); + + if(is_Phi(spill->irn) && get_nodes_block(spill->irn) == bb) { + 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; + int m; + ilp_var_t var; + + + /* argument already done? */ + if(op->attr.live_range.args.copies[n] != ILP_UNDEF) continue; + + /* get sum of execution frequencies of blocks with the same phi argument */ + for(m=n; m>=0; --m) { + const ir_node *arg2 = get_irn_n(spill->irn, m); + + if(arg==arg2) { + freq += execution_frequency(si, get_Block_cfgpred_block(bb, m)); + } + } + + /* copies are not for free */ + ir_snprintf(buf, sizeof(buf), "copy_%N_%N", arg, spill->irn); + var = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE * freq); + + for(m=n; m>=0; --m) { + const ir_node *arg2 = get_irn_n(spill->irn, m); + + if(arg==arg2) { + op->attr.live_range.args.copies[m] = var; + } + } + + /* copy <= mem_in */ + ir_snprintf(buf, sizeof(buf), "nocopy_%N_%N", arg, spill->irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, var, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->mem_in, -1.0); + } + } } } @@ -1788,13 +2169,23 @@ fertig: cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs); pset_foreach(live, irn) { - spill = set_find_spill(spill_bb->ilp, irn); - assert(spill); + ilp_cst_t nospill; + + spill = set_find_spill(spill_bb->ilp, irn); + assert(spill); + + ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N", irn, bb); + spill->reg_in = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + + lpp_set_factor_fast(si->lpp, cst, spill->reg_in, 1.0); + + /* spill + mem_in <= 1 */ + ir_snprintf(buf, sizeof(buf), "nospill_%N_%N", irn, bb); + nospill = lpp_add_cst(si->lpp, buf, lpp_less, 1); - ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N", irn, bb); - spill->reg_in = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + lpp_set_factor_fast(si->lpp, nospill, spill->mem_in, 1.0); + lpp_set_factor_fast(si->lpp, nospill, spill->spill, 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->reg_in, 1.0); } foreach_post_remat(bb, irn) { op_t *remat_op = get_irn_link(irn); @@ -1805,13 +2196,12 @@ fertig: lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); } - /* forall remat2 add requirements */ + /* forall post remats add requirements */ foreach_post_remat(bb, tmp) { - int i, - n; + int n; - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *remat_arg = get_irn_n(tmp, i); + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(tmp, n); op_t *remat_op = get_irn_link(tmp); if(!has_reg_class(si, remat_arg)) continue; @@ -1819,7 +2209,7 @@ fertig: spill = set_find_spill(spill_bb->ilp, remat_arg); assert(spill); - /* TODO verify this is placed correctly */ + /* 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); @@ -1830,18 +2220,17 @@ fertig: /* mem_in/reg_in for live_in values, especially phis and their arguments */ pset_foreach(live, irn) { int p = 0, - i, n; spill = set_find_spill(spill_bb->ilp, irn); assert(spill && spill->irn == irn); if(is_Phi(irn) && get_nodes_block(irn) == bb) { - for (i = 0, n = get_Phi_n_preds(irn); i < n; ++i) { + for (n=get_Phi_n_preds(irn)-1; n>=0; --n) { ilp_cst_t mem_in, reg_in; - ir_node *phi_arg = get_Phi_pred(irn, i); - ir_node *bb_p = get_Block_cfgpred_block(bb, i); + ir_node *phi_arg = get_Phi_pred(irn, n); + ir_node *bb_p = get_Block_cfgpred_block(bb, n); spill_bb_t *spill_bb_p = get_irn_link(bb_p); spill_t *spill_p; @@ -1868,10 +2257,10 @@ fertig: } else { /* else assure the value arrives on all paths in the same resource */ - for (i = 0, n = get_Block_n_cfgpreds(bb); i < n; ++i) { + for (n=get_Block_n_cfgpreds(bb)-1; n>=0; --n) { ilp_cst_t mem_in, reg_in; - ir_node *bb_p = get_Block_cfgpred_block(bb, i); + ir_node *bb_p = get_Block_cfgpred_block(bb, n); spill_bb_t *spill_bb_p = get_irn_link(bb_p); spill_t *spill_p; @@ -1915,19 +2304,25 @@ fertig: /* walk forward now and compute constraints for placing spills */ /* this must only be done for values that are not defined in this block */ -#ifdef GOODWIN_REDUCTION - if(get_Block_n_cfgpreds(bb) == 1 && get_block_n_succs(get_Block_cfgpred_block(bb,0)) > 1) { -#endif - pset_foreach(live, irn) { - ir_snprintf(buf, sizeof(buf), "req_spill_%N_%N", spill->irn, bb); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + /* 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; - spill = set_find_spill(spill_bb->ilp, irn); - assert(spill); - lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0); + spill = set_find_spill(spill_bb->ilp, irn); + assert(spill); + ir_snprintf(buf, sizeof(buf), "req_spill_%N_%N", irn, bb); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); + + lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0); + if(is_diverge_edge(bb)) lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0); + + if(!is_Phi(irn)) { sched_foreach_op(bb, tmp) { op_t *op = get_irn_link(tmp); @@ -1938,73 +2333,413 @@ fertig: ir_node *value = op->attr.remat.remat->value; if(value == irn) { - /* only collect remats up to the first use of a value */ + /* only collect remats up to the first real use of a value */ lpp_set_factor_fast(si->lpp, cst, op->attr.remat.ilp, -1.0); } } else { - int i, - n; + int n; - for (i = 0, n = get_irn_arity(tmp); i < n; ++i) { - ir_node *arg = get_irn_n(tmp, i); + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *arg = get_irn_n(tmp, n); if(arg == irn) { /* if a value is used stop collecting remats */ - cst = ILP_UNDEF; + goto next_live; } - break; } } - if(cst == ILP_UNDEF) break; } } -#ifdef GOODWIN_REDUCTION +next_live: } -#endif + del_pset(live); +} - /* if a value is used by a mem-phi, then mem_in of this value is 0 (has to be spilled again into a different slot) - mem_in(phi) -> not mem_in(orig_value) TODO: how does this depend on a certain predecessor? - */ +typedef struct _irnlist_t { + struct list_head list; + ir_node *irn; +} irnlist_t; - /* mem_in of mem-phi has associated costs (but first one is free) */ - /* define n_mem_copies as positive integer in each predecessor block, - #mem_in into this block from predecessor block - 1 weighted with SPILL_COST*execfreq(predecessor) - TODO - */ +typedef struct _interference_t { + struct list_head blocklist; + ir_node *a; + ir_node *b; +} interference_t; +static int +cmp_interference(const void *a, const void *b, size_t size) +{ + const interference_t *p = a; + const interference_t *q = b; - del_pset(live); + return !(p->a == q->a && p->b == q->b); } +static interference_t * +set_find_interference(set * set, ir_node * a, ir_node * b) +{ + interference_t query; -#if 0 - * Speicherkopienminimierung: teste Speicherwerte auf Interferenz - * und weise Spillkontexte zu. Sorge bei Phis dafuer, dass gleiche - * Kontexte zusammenfliessen (Operanden und Ergebnis hat gleichen - * Kontext) -#endif + query.a = (a>b)?a:b; + query.b = (a>b)?b:a; -static INLINE int -is_zero(double x) + return set_find(set, &query, sizeof(query), HASH_PTR(PTR_TO_INT(a) ^ PTR_TO_INT(b))); +} + +static interference_t * +set_insert_interference(spill_ilp_t * si, set * set, ir_node * a, ir_node * b, ir_node * bb) { - return fabs(x) < 0.00001; + interference_t query, + *result; + irnlist_t *list = obstack_alloc(si->obst, sizeof(*list)); + + list->irn = bb; + + result = set_find_interference(set, a, b); + if(result) { + + list_add(&list->list, &result->blocklist); + return result; + } + + query.a = (a>b)?a:b; + query.b = (a>b)?b:a; + + result = set_insert(set, &query, sizeof(query), HASH_PTR(PTR_TO_INT(a) ^ PTR_TO_INT(b))); + + INIT_LIST_HEAD(&result->blocklist); + list_add(&list->list, &result->blocklist); + + return result; } -#if 0 static int -is_spilled(const spill_ilp_t * si, const live_range_t * lr) +values_interfere_in_block(ir_node * bb, ir_node * a, ir_node * b) { - return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var)); + const ir_edge_t *edge; + + if(get_nodes_block(a) != bb && get_nodes_block(b) != bb) { + /* both values are live in, so they interfere */ + return 1; + } + + /* ensure a dominates b */ + if(value_dominates(b,a)) { + const ir_node * t; + t = b; + b = a; + a = t; + } + assert(get_nodes_block(b) == bb && "at least b should be defined here in this block"); + + + /* the following code is stolen from bera.c */ + if(is_live_end(bb, a)) + return 1; + + foreach_out_edge(a, edge) { + const ir_node *user = edge->src; + if(get_nodes_block(user) == bb + && !is_Phi(user) + && b != user + && value_dominates(b, user)) + return 1; + } + + return 0; } -#endif +/** + * Walk all irg blocks and collect interfering values inside of phi classes + */ +static void +luke_interferencewalker(ir_node * bb, void * data) +{ + spill_ilp_t *si = (spill_ilp_t*)data; + irn_live_t *li1, + *li2; + + live_foreach(bb, li1) { + ir_node *a = (ir_node *) li1->irn; + op_t *a_op = get_irn_link(a); + + if(a_op->is_remat) continue; + + /* a is only interesting if it is in my register class and if it is inside a phi class */ + if (has_reg_class(si, a) && get_phi_class(a)) { + for(li2=li1->next; li2; li2 = li2->next) { + ir_node *b = (ir_node *) li2->irn; + op_t *b_op = get_irn_link(b); + + if(b_op->is_remat) continue; + + /* a and b are only interesting if they are in the same phi class */ + if(has_reg_class(si, b) && get_phi_class(a) == get_phi_class(b)) { + if(values_interfere_in_block(bb, a, b)) { + DBG((si->dbg, LEVEL_4, "\tvalues interfere in %+F: %+F, %+F\n", bb, a, b)); + set_insert_interference(si, si->interferences, a, b, bb); + } + } + } + } + } +} + +static unsigned int copy_path_id = 0; + +static void +write_copy_path_cst(spill_ilp_t *si, pset * copies, ilp_var_t any_interfere) +{ + ilp_cst_t cst; + ilp_var_t copy; + char buf[256]; + void *ptr; + + ir_snprintf(buf, sizeof(buf), "copy_path-%d", copy_path_id++); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + + lpp_set_factor_fast(si->lpp, cst, any_interfere, 1.0); + + pset_foreach(copies, ptr) { + copy = PTR_TO_INT(ptr); + lpp_set_factor_fast(si->lpp, cst, copy, -1.0); + } +} + +/** + * @parameter copies contains a path of copies which lead us to irn + * @parameter visited contains a set of nodes already visited on this path + */ static int -is_mem_phi(const ir_node * phi, void *data) +find_copy_path(spill_ilp_t * si, ir_node * irn, ir_node * target, ilp_var_t any_interfere, pset * copies, pset * visited) { - spill_ilp_t *si = data; -// return is_spilled(si, get_use_head(si, phi)->closest_use); - return 0; + ir_edge_t *edge; + op_t *op = get_irn_link(irn); + pset *visited_users = pset_new_ptr_default(); + int paths = 0; + + if(op->is_remat) return; + + pset_insert_ptr(visited, irn); + + if(is_Phi(irn)) { + int n; + pset *visited_operands = pset_new_ptr(get_irn_arity(irn)); + + /* visit all operands */ + for(n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *arg = get_irn_n(irn, n); + ilp_var_t copy = op->attr.live_range.args.copies[n]; + + if(!has_reg_class(si, arg)) continue; + if(pset_find_ptr(visited_operands, arg)) continue; + pset_insert_ptr(visited_operands, arg); + + if(arg == target) { + if(++paths > MAX_PATHS && pset_count(copies) != 0) { + del_pset(visited_operands); + del_pset(visited_users); + pset_remove_ptr(visited, irn); + return paths; + } + pset_insert(copies, INT_TO_PTR(copy), copy); + write_copy_path_cst(si, copies, any_interfere); + pset_remove(copies, INT_TO_PTR(copy), copy); + } else if(!pset_find_ptr(visited, arg)) { + pset_insert(copies, INT_TO_PTR(copy), copy); + paths += find_copy_path(si, arg, target, any_interfere, copies, visited); + pset_remove(copies, INT_TO_PTR(copy), copy); + + if(paths > MAX_PATHS) { + if(pset_count(copies) == 0) { + ilp_cst_t cst; + char buf[256]; + + ir_snprintf(buf, sizeof(buf), "always_copy-%d-%d", any_interfere, copy); + cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0); + lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0); + lpp_set_factor_fast(si->lpp, cst, copy, 1.0); + DBG((si->dbg, LEVEL_1, "ALWAYS COPYING %d FOR INTERFERENCE %d\n", copy, any_interfere)); + + paths = 0; + } else { + del_pset(visited_operands); + del_pset(visited_users); + pset_remove_ptr(visited, irn); + return paths; + } + } + } + } + + del_pset(visited_operands); + } + + /* visit all uses which are phis */ + foreach_out_edge(irn, edge) { + ir_node *user = edge->src; + int pos = edge->pos; + op_t *op = get_irn_link(user); + ilp_var_t copy; + + if(!is_Phi(user)) continue; + if(!has_reg_class(si, user)) continue; + if(pset_find_ptr(visited_users, user)) continue; + pset_insert_ptr(visited_users, user); + + copy = op->attr.live_range.args.copies[pos]; + + if(user == target) { + if(++paths > MAX_PATHS && pset_count(copies) != 0) { + del_pset(visited_users); + pset_remove_ptr(visited, irn); + return paths; + } + pset_insert(copies, INT_TO_PTR(copy), copy); + write_copy_path_cst(si, copies, any_interfere); + pset_remove(copies, INT_TO_PTR(copy), copy); + } else if(!pset_find_ptr(visited, user)) { + pset_insert(copies, INT_TO_PTR(copy), copy); + paths += find_copy_path(si, user, target, any_interfere, copies, visited); + pset_remove(copies, INT_TO_PTR(copy), copy); + + if(paths > MAX_PATHS) { + if(pset_count(copies) == 0) { + ilp_cst_t cst; + char buf[256]; + + ir_snprintf(buf, sizeof(buf), "always_copy-%d-%d", any_interfere, copy); + cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0); + lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0); + lpp_set_factor_fast(si->lpp, cst, copy, 1.0); + DBG((si->dbg, LEVEL_1, "ALWAYS COPYING %d FOR INTERFERENCE %d\n", copy, any_interfere)); + + paths = 0; + } else { + del_pset(visited_users); + pset_remove_ptr(visited, irn); + return paths; + } + } + } + } + + del_pset(visited_users); + pset_remove_ptr(visited, irn); + return paths; +} + +static void +gen_copy_constraints(spill_ilp_t * si, ir_node * a, ir_node * b, ilp_var_t any_interfere) +{ + pset * copies = pset_new_ptr_default(); + pset * visited = pset_new_ptr_default(); + + find_copy_path(si, a, b, any_interfere, copies, visited); + + del_pset(visited); + del_pset(copies); +} + + +static void +memcopyhandler(spill_ilp_t * si) +{ + interference_t *interference; + char buf[256]; + /* teste Speicherwerte auf Interferenz */ + + /* analyze phi classes */ + phi_class_compute(si->chordal_env->irg); + + DBG((si->dbg, LEVEL_2, "\t calling interferencewalker\n")); + irg_block_walk_graph(si->chordal_env->irg, luke_interferencewalker, NULL, si); + + /* now lets emit the ILP unequations for the crap */ + set_foreach(si->interferences, interference) { + irnlist_t *irnlist; + ilp_var_t interfere, + any_interfere; + ilp_cst_t any_interfere_cst, + cst; + const ir_node *a = interference->a; + const ir_node *b = interference->b; + + /* any_interf <= \sum interf */ + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N", a, b); + any_interfere_cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + any_interfere = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + + lpp_set_factor_fast(si->lpp, any_interfere_cst, any_interfere, 1.0); + + list_for_each_entry(irnlist_t, irnlist, &interference->blocklist, list) { + const ir_node *bb = irnlist->irn; + spill_bb_t *spill_bb = get_irn_link(bb); + spill_t *spilla, + *spillb, + query; + char buf[256]; + + query.irn = a; + spilla = set_find_spill(spill_bb->ilp, a); + assert(spilla); + + query.irn = b; + spillb = set_find_spill(spill_bb->ilp, b); + assert(spillb); + + /* interfere <-> (mem_in_a or spill_a) and (mem_in_b or spill_b): */ + /* 1: mem_in_a + mem_in_b + spill_a + spill_b - interfere <= 1 */ + /* 2: - mem_in_a - spill_a + interfere <= 0 */ + /* 3: - mem_in_b - spill_b + interfere <= 0 */ + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N", bb, a, b); + interfere = lpp_add_var(si->lpp, buf, lpp_binary, 0.0); + + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-1", bb, a, b); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 1); + + lpp_set_factor_fast(si->lpp, cst, interfere, -1.0); + if(spilla->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spilla->mem_in, 1.0); + lpp_set_factor_fast(si->lpp, cst, spilla->spill, 1.0); + if(spillb->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spillb->mem_in, 1.0); + lpp_set_factor_fast(si->lpp, cst, spillb->spill, 1.0); + + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-2", bb, a, b); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + + lpp_set_factor_fast(si->lpp, cst, interfere, 1.0); + if(spilla->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spilla->mem_in, -1.0); + lpp_set_factor_fast(si->lpp, cst, spilla->spill, -1.0); + + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N_%N-3", bb, a, b); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + + lpp_set_factor_fast(si->lpp, cst, interfere, 1.0); + if(spillb->mem_in != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, spillb->mem_in, -1.0); + lpp_set_factor_fast(si->lpp, cst, spillb->spill, -1.0); + + + lpp_set_factor_fast(si->lpp, any_interfere_cst, interfere, -1.0); + + /* any_interfere >= interf */ + ir_snprintf(buf, sizeof(buf), "interfere_%N_%N-%N", a, b, bb); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + + lpp_set_factor_fast(si->lpp, cst, interfere, 1.0); + lpp_set_factor_fast(si->lpp, cst, any_interfere, -1.0); + } + + /* now that we know whether the two values interfere in memory we can drop constraints to enforce copies */ + gen_copy_constraints(si,a,b,any_interfere); + } +} + + +static INLINE int +is_zero(double x) +{ + return fabs(x) < 0.00001; } #ifdef KEEPALIVE @@ -2071,12 +2806,12 @@ sched_pressure_edge_hook(FILE *F, ir_node *irn) static void dump_ir_block_graph_sched_pressure(ir_graph *irg, const char *suffix) { - DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook(); + DUMP_NODE_EDGE_FUNC old_edge_hook = get_dump_node_edge_hook(); dump_consts_local(0); set_dump_node_edge_hook(sched_pressure_edge_hook); dump_ir_block_graph(irg, suffix); - set_dump_node_edge_hook(old); + set_dump_node_edge_hook(old_edge_hook); } static void @@ -2085,8 +2820,7 @@ walker_pressure_annotator(ir_node * bb, void * data) spill_ilp_t *si = data; ir_node *irn; irn_live_t *li; - int i, - n; + int n; pset *live = pset_new_ptr_default(); int projs = 0; @@ -2113,8 +2847,8 @@ walker_pressure_annotator(ir_node * bb, void * data) if(!is_Proj(irn)) projs = 0; - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *arg = get_irn_n(irn, i); + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *arg = get_irn_n(irn, n); if(has_reg_class(si, arg)) pset_insert_ptr(live, arg); } @@ -2221,23 +2955,21 @@ ir_node *be_spill2(const arch_env_t *arch_env, ir_node *irn, ir_node *insert, ir static void delete_remat(spill_ilp_t * si, ir_node * remat) { - int i, - n; + int n; ir_node *bad = get_irg_bad(si->chordal_env->irg); sched_remove(remat); /* kill links to operands */ - for (i = -1, n = get_irn_arity(remat); i < n; ++i) { - set_irn_n(remat, i, bad); + for (n=get_irn_arity(remat)-1; n>=-1; --n) { + set_irn_n(remat, n, bad); } } static void clean_remat_info(spill_ilp_t * si) { - int i, - n; + int n; remat_t *remat; remat_info_t *remat_info; ir_node *bad = get_irg_bad(si->chordal_env->irg); @@ -2253,8 +2985,8 @@ clean_remat_info(spill_ilp_t * si) } if(get_irn_n_edges(remat->op) == 0) { - for (i = -1, n = get_irn_arity(remat->op); i < n; ++i) { - set_irn_n(remat->op, i, bad); + for (n=get_irn_arity(remat->op)-1; n>=-1; --n) { + set_irn_n(remat->op, n, bad); } } } @@ -2268,16 +3000,15 @@ static void delete_unnecessary_remats(spill_ilp_t * si) { #ifdef KEEPALIVE - int i, - n; + int n; 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 (i = 0, n = get_irn_arity(si->keep); i < n; ++i) { - ir_node *keep_arg = get_irn_n(si->keep, i); + 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); lpp_name_t *name; @@ -2305,7 +3036,7 @@ delete_unnecessary_remats(spill_ilp_t * si) } } - set_irn_n(si->keep, i, bad); + set_irn_n(si->keep, n, bad); } #if 0 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) { @@ -2325,39 +3056,79 @@ delete_unnecessary_remats(spill_ilp_t * si) #else ir_node *remat; - pset_foreach(si->all_possible_remats, remat) { - op_t *remat_op = get_irn_link(remat); - lpp_name_t *name = si->lpp->vars[remat_op->attr.remat.ilp]; + pset_foreach(si->all_possible_remats, remat) { + op_t *remat_op = get_irn_link(remat); + lpp_name_t *name = si->lpp->vars[remat_op->attr.remat.ilp]; + + if(is_zero(name->value)) { + DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", remat)); + /* TODO check whether reload is preferred over remat (could be bug) */ + delete_remat(si, remat); + } else { + if(!remat_op->attr.remat.remat->inverse) { + if(remat_op->attr.remat.pre) { + DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", remat)); + } else { + DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", remat)); + } + } else { + if(remat_op->attr.remat.pre) { + DBG((si->dbg, LEVEL_2, "\t**INVERSE remat kept: %+F\n", remat)); + } else { + DBG((si->dbg, LEVEL_2, "\t%%%%INVERSE remat2 kept: %+F\n", remat)); + } + } + } + } +#endif +} + +static pset * +get_spills_for_value(spill_ilp_t * si, ir_node * value) +{ + pset *spills = pset_new_ptr_default(); + + ir_node *next; + defs_t *defs; + + defs = set_find_def(si->values, value); + + if(defs && defs->spills) { + for(next = defs->spills; next; next = get_irn_link(next)) { + pset_insert_ptr(spills, next); + } + } + + return spills; +} + +static pset * +get_remats_for_value(spill_ilp_t * si, ir_node * value) +{ + pset *remats = pset_new_ptr_default(); + + ir_node *next; + defs_t *defs; - if(is_zero(name->value)) { - DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", remat)); - /* TODO check whether reload is preferred over remat (could be bug) */ - delete_remat(si, remat); - } else { - if(!remat_op->attr.remat.remat->inverse) { - if(remat_op->attr.remat.pre) { - DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", remat)); - } else { - DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", remat)); - } - } else { - if(remat_op->attr.remat.pre) { - DBG((si->dbg, LEVEL_2, "\t**INVERSE remat kept: %+F\n", remat)); - } else { - DBG((si->dbg, LEVEL_2, "\t%%%%INVERSE remat2 kept: %+F\n", remat)); - } - } + pset_insert_ptr(remats, value); + defs = set_find_def(si->values, value); + + if(defs && defs->remats) { + for(next = defs->remats; next; next = get_irn_link(next)) { + pset_insert_ptr(remats, next); } } -#endif + + return remats; } + /** * @param before The node after which the spill will be placed in the schedule */ /* TODO set context properly */ static ir_node * -insert_spill(spill_ilp_t * si, const ir_node * irn, const ir_node * value, const ir_node * before) +insert_spill(spill_ilp_t * si, ir_node * irn, ir_node * value, ir_node * before) { defs_t *defs; ir_node *spill; @@ -2390,13 +3161,13 @@ insert_mem_phi(spill_ilp_t * si, const ir_node * phi) ir_node *mem_phi; ir_node **ins; defs_t *defs; - int i, - n; + int n; + op_t *op = get_irn_link(phi); NEW_ARR_A(ir_node*, ins, get_irn_arity(phi)); - for(i=0,n=get_irn_arity(phi); im_unknown; + for(n=get_irn_arity(phi)-1; n>=0; --n) { + 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); @@ -2408,10 +3179,13 @@ insert_mem_phi(spill_ilp_t * si, const ir_node * phi) set_irn_link(mem_phi, defs->spills); defs->spills = mem_phi; + sched_add_after(phi, mem_phi); + #ifdef KEEPALIVE_SPILLS pset_insert_ptr(si->spills, mem_phi); #endif + return mem_phi; } @@ -2434,59 +3208,6 @@ insert_remat(spill_ilp_t * si, ir_node * remat) defs->remats = remat; } -#if 0 -static void -collect_spills(spill_ilp_t * si, ir_node * value, pset * spills, pset * visited) -{ - ir_node *next; - defs_t *defs; - - defs = set_find_def(si->values, value); - - if(defs && defs->spills) { - for(next = defs->spills; next; next = get_irn_link(next)) { - pset_insert_ptr(spills, next); - } - } else if (is_Phi(value)) { - /* recursion */ - if(!pset_find_ptr(visited, value)) { - int i, - n; - - pset_insert_ptr(visited, value); - for(i=0, n=get_irn_arity(value); ivalues, value); - - if(defs && defs->spills) { - for(next = defs->spills; next; next = get_irn_link(next)) { - pset_insert_ptr(spills, next); - } - } - - return spills; -} /** * Add reload before operation and add to list of defs @@ -2502,25 +3223,7 @@ insert_reload(spill_ilp_t * si, const ir_node * value, const ir_node * after) DBG((si->dbg, LEVEL_3, "\t inserting reload for value %+F before %+F\n", value, after)); defs = set_find_def(si->values, value); - /* get a spill of this value */ -#if 0 - if((!defs || !defs->spills) && is_Phi(value)) { - pset *spills; - - spills = get_spills_for_value(si, value); - - spill = pset_first(spills); - del_pset(spills); - if(!defs) { - defs = set_insert_def(si->values, value); - } - defs->spills = spill; - set_irn_link(spill, NULL); - } else { - spill = defs->spills; - } -#endif spill = defs->spills; assert(spill && "no spill placed before reload"); @@ -2555,18 +3258,24 @@ walker_spill_placer(ir_node * bb, void * data) { } } - if(spill->spill != ILP_UNDEF) { - name = si->lpp->vars[spill->spill]; - if(!is_zero(name->value)) { - if(spill->reg_in > 0) { - name = si->lpp->vars[spill->reg_in]; - if(!is_zero(name->value)) { - insert_spill(si, spill->irn, spill->irn, bb); - continue; - } + name = si->lpp->vars[spill->spill]; + if(!is_zero(name->value)) { + /* place spill directly after definition */ + if(get_nodes_block(spill->irn) == bb) { + insert_spill(si, spill->irn, spill->irn, spill->irn); + continue; + } + + /* place spill at bb start */ + if(spill->reg_in > 0) { + name = si->lpp->vars[spill->reg_in]; + if(!is_zero(name->value)) { + insert_spill(si, spill->irn, spill->irn, bb); + continue; } - pset_insert_ptr(spills_to_do, spill->irn); } + /* place spill after a remat */ + pset_insert_ptr(spills_to_do, spill->irn); } } DBG((si->dbg, LEVEL_3, "\t %d spills to do in block %+F\n", pset_count(spills_to_do), bb)); @@ -2600,29 +3309,86 @@ walker_spill_placer(ir_node * bb, void * data) { del_pset(spills_to_do); } +static ir_node * +insert_mem_copy(spill_ilp_t * si, const ir_node * bb, const ir_node * value) +{ + ir_node *insert_pos = bb; + ir_node *spill; + const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; + + /* find last definition of arg value in block */ + ir_node *next; + defs_t *defs; + int last = 0; + + defs = set_find_def(si->values, value); + + if(defs && defs->remats) { + for(next = defs->remats; next; next = get_irn_link(next)) { + if(get_nodes_block(next) == bb && sched_get_time_step(next) > last) { + last = sched_get_time_step(next); + insert_pos = next; + } + } + } + + if(get_nodes_block(value) == bb && sched_get_time_step(value) > last) { + last = sched_get_time_step(value); + insert_pos = value; + } + + DBG((si->dbg, LEVEL_2, "\t inserting mem copy for value %+F after %+F\n", value, insert_pos)); + + spill = be_spill2(arch_env, is_Block(insert_pos)?value:insert_pos, insert_pos, value); + + return spill; +} + static void phim_fixer(spill_ilp_t *si) { defs_t *defs; set_foreach(si->values, defs) { const ir_node *phi = defs->value; - const ir_node *phi_m = defs->spills; - int i, - n; + op_t *op = get_irn_link(phi); + ir_node *phi_m = NULL; + ir_node *next = defs->spills; + int n; if(!is_Phi(phi)) continue; - if(!phi_m || !is_Phi(phi_m) || get_irn_mode(phi_m) != mode_M) continue; - for(i=0,n=get_irn_arity(phi); i=0; --n) { + const ir_node *value = get_irn_n(phi, n); defs_t *val_defs = set_find_def(si->values, value); + ir_node *arg = get_irn_n(phi_m, n); /* get a spill of this value */ ir_node *spill = val_defs->spills; - assert(spill && "no spill placed before PhiM"); - set_irn_n(phi_m, i, spill); +#ifndef NO_MEMCOPIES + ir_node *pred = get_Block_cfgpred_block(get_nodes_block(phi), n); + lpp_name_t *name = si->lpp->vars[op->attr.live_range.args.copies[n]]; + + if(!is_zero(name->value)) { + spill = insert_mem_copy(si, pred, value); + } else { + assert(spill && "no spill placed before PhiM"); + } +#else + assert(spill && "no spill placed before PhiM"); +#endif + set_irn_n(phi_m, n, spill); } } } @@ -2635,6 +3401,51 @@ walker_reload_placer(ir_node * bb, void * data) { int i; irn_live_t *li; + /* reloads at end of block */ + if(spill_bb->reloads) { + keyval_t *keyval; + + set_foreach(spill_bb->reloads, keyval) { + ir_node *irn = (ir_node*)keyval->key; + ilp_var_t reload = PTR_TO_INT(keyval->val); + lpp_name_t *name; + + name = si->lpp->vars[reload]; + if(!is_zero(name->value)) { + ir_node *reload; + ir_node *insert_pos = bb; + ir_node *prev = sched_block_last_noncf(si, bb); + op_t *prev_op = get_irn_link(prev); + + while(be_is_Spill(prev)) { + prev = sched_prev(prev); + } + + prev_op = get_irn_link(prev); + + /* insert reload before pre-remats */ + while(!sched_is_end(prev) && !be_is_Reload(prev) && !is_Phi(prev) + && prev_op->is_remat && prev_op->attr.remat.pre) { + insert_pos = prev; + + do { + prev = sched_prev(prev); + } while(be_is_Spill(prev)); + + prev_op = get_irn_link(prev); + + } + + reload = insert_reload(si, irn, insert_pos); + +#ifdef KEEPALIVE_RELOADS + pset_insert_ptr(si->spills, reload); +#endif + } + } + } + + /* walk and insert more reloads and collect remats */ sched_foreach_reverse(bb, irn) { op_t *op = get_irn_link(irn); @@ -2648,31 +3459,41 @@ walker_reload_placer(ir_node * bb, void * data) { } else { int n; - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *arg = get_irn_n(irn, i); + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *arg = get_irn_n(irn, n); - if(op->attr.live_range.reloads && op->attr.live_range.reloads[i] != ILP_UNDEF) { + if(op->attr.live_range.args.reloads && op->attr.live_range.args.reloads[n] != ILP_UNDEF) { lpp_name_t *name; - name = si->lpp->vars[op->attr.live_range.reloads[i]]; + name = si->lpp->vars[op->attr.live_range.args.reloads[n]]; if(!is_zero(name->value)) { ir_node *reload; ir_node *insert_pos = irn; ir_node *prev = sched_prev(insert_pos); - op_t *prev_op = get_irn_link(prev); + op_t *prev_op; + + while(be_is_Spill(prev)) { + prev = sched_prev(prev); + } + + prev_op = get_irn_link(prev); /* insert reload before pre-remats */ - while(!sched_is_end(prev) && !be_is_Reload(prev) && !be_is_Spill(prev) + while(!sched_is_end(prev) && !be_is_Reload(prev) && !is_Phi(prev) && prev_op->is_remat && prev_op->attr.remat.pre) { insert_pos = prev; - prev = sched_prev(insert_pos); + do { + prev = sched_prev(prev); + } while(be_is_Spill(prev)); + prev_op = get_irn_link(prev); + } reload = insert_reload(si, arg, insert_pos); - set_irn_n(irn, i, reload); + set_irn_n(irn, n, reload); #ifdef KEEPALIVE_RELOADS pset_insert_ptr(si->spills, reload); @@ -2683,43 +3504,8 @@ walker_reload_placer(ir_node * bb, void * data) { } } - /* reloads at end of block */ - if(spill_bb->reloads) { - i=0; - live_foreach(bb, li) { - ir_node *irn = (ir_node *) li->irn; - - if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { - lpp_name_t *name; - - name = si->lpp->vars[spill_bb->reloads[i]]; - if(!is_zero(name->value)) { - ir_node *reload; - ir_node *insert_pos = bb; - ir_node *prev = sched_prev(insert_pos); - op_t *prev_op = get_irn_link(prev); - - /* insert reload before pre-remats */ - while(!sched_is_end(prev) && !be_is_Reload(prev) && !be_is_Spill(prev) - && prev_op->is_remat && prev_op->attr.remat.pre) { - insert_pos = prev; - - prev = sched_prev(insert_pos); - prev_op = get_irn_link(prev); - } - - reload = insert_reload(si, irn, insert_pos); - -#ifdef KEEPALIVE_RELOADS - pset_insert_ptr(si->spills, reload); -#endif - } - ++i; - } - } - } - del_set(spill_bb->ilp); + if(spill_bb->reloads) del_set(spill_bb->reloads); } static void @@ -2730,27 +3516,36 @@ walker_collect_used(ir_node * irn, void * data) lc_bitset_set(used, get_irn_idx(irn)); } +struct kill_helper { + lc_bitset_t *used; + spill_ilp_t *si; +}; + static void walker_kill_unused(ir_node * bb, void * data) { - lc_bitset_t *used = data; - const ir_node *bad = get_irg_bad(get_irn_irg(bb)); - ir_node *irn; + struct kill_helper *kh = data; + const ir_node *bad = get_irg_bad(get_irn_irg(bb)); + ir_node *irn; for(irn=sched_first(bb); !sched_is_end(irn);) { ir_node *next = sched_next(irn); - int i, - n; + int n; - if(!lc_bitset_is_set(used, get_irn_idx(irn))) { - assert(!be_is_Spill(irn) && !be_is_Reload(irn) && "something is fishy, spill or remat is unused"); + if(!lc_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 + assert(lpp_get_sol_state(kh->si->lpp) != lpp_optimal && "optimal solution is suboptimal?"); +#endif + } sched_remove(irn); set_nodes_block(irn, bad); - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - set_irn_n(irn, i, bad); + for (n=get_irn_arity(irn)-1; n>=0; --n) { + set_irn_n(irn, n, bad); } } irn = next; @@ -2760,12 +3555,15 @@ walker_kill_unused(ir_node * bb, void * data) static void kill_all_unused_values_in_schedule(spill_ilp_t * si) { - lc_bitset_t *used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); + struct kill_helper kh; - irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, used); - irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, used); + kh.used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); + kh.si = si; - lc_bitset_free(used); + 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); } static void @@ -2778,11 +3576,55 @@ print_irn_pset(pset * p) } } +static void +dump_phi_class(spill_ilp_t * si, pset * phiclass, const char * file) +{ + FILE *f = fopen(file, "w"); + ir_node *irn; + interference_t *interference; + + pset_break(phiclass); + set_break(si->interferences); + + ir_fprintf(f, "digraph phiclass {\n"); + + pset_foreach(phiclass, irn) { + if(is_Phi(irn)) + ir_fprintf(f, " %F%N [shape=box]\n",irn,irn); + } + + pset_foreach(phiclass, irn) { + int n; + + if(!is_Phi(irn)) continue; + + for(n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *arg = get_irn_n(irn, n); + + ir_fprintf(f, " %F%N -> %F%N\n",irn,irn,arg,arg); + } + } + + set_foreach(si->interferences, interference) { + const ir_node *a = interference->a; + const ir_node *b = interference->b; + if(get_phi_class(a) == phiclass) { + ir_fprintf(f, " %F%N -> %F%N [color=red,dir=none,style=bold]\n",a,a,b,b); + } + } + + ir_fprintf(f, "}"); + fclose(f); +} + 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); + + pset_insert_ptr(ignore, get_irg_end(si->chordal_env->irg)); /* then fix uses of spills */ set_foreach(si->values, defs) { @@ -2791,32 +3633,29 @@ rewire_uses(spill_ilp_t * si) ir_node *next = defs->remats; int remats = 0; - if(next) { - reloads = pset_new_ptr_default(); + reloads = pset_new_ptr_default(); - while(next) { - if(be_is_Reload(next)) { - pset_insert_ptr(reloads, next); - } else { - ++remats; - } - next = get_irn_link(next); + while(next) { + if(be_is_Reload(next)) { + pset_insert_ptr(reloads, next); + } else { + ++remats; } + next = get_irn_link(next); + } - spills = get_spills_for_value(si, defs->value); - DBG((si->dbg, LEVEL_2, "\t %d remats, %d reloads, and %d spills for value %+F\n", remats, pset_count(reloads), pset_count(spills), defs->value)); - if(pset_count(spills) > 1) { - assert(pset_count(reloads) > 0); -// print_irn_pset(spills); -// print_irn_pset(reloads); - -// be_ssa_constr_set_uses(dfi, spills, reloads); - be_ssa_constr_set(dfi, spills); - } + spills = get_spills_for_value(si, defs->value); + DBG((si->dbg, LEVEL_2, "\t %d remats, %d reloads, and %d spills for value %+F\n", remats, pset_count(reloads), pset_count(spills), defs->value)); + if(pset_count(spills) > 1) { + //assert(pset_count(reloads) > 0); + // print_irn_pset(spills); + // print_irn_pset(reloads); - del_pset(reloads); - del_pset(spills); + be_ssa_constr_set_ignore(dfi, spills, ignore); } + + del_pset(reloads); + del_pset(spills); } /* first fix uses of remats and reloads */ @@ -2847,6 +3686,7 @@ rewire_uses(spill_ilp_t * si) be_free_dominance_frontiers(dfi); } + static void writeback_results(spill_ilp_t * si) { @@ -2858,8 +3698,8 @@ writeback_results(spill_ilp_t * si) delete_unnecessary_remats(si); si->m_unknown = new_r_Unknown(si->chordal_env->irg, mode_M); irg_block_walk_graph(si->chordal_env->irg, walker_spill_placer, NULL, si); - phim_fixer(si); irg_block_walk_graph(si->chordal_env->irg, walker_reload_placer, NULL, si); + phim_fixer(si); /* clean the remat info! there are still back-edges leading there! */ clean_remat_info(si); @@ -2909,7 +3749,10 @@ walker_reload_mover(ir_node * bb, void * data) pressure = (int)get_irn_link(irn); while(pressure < si->n_regs) { - if(sched_is_end(irn) || (be_is_Reload(irn) && has_reg_class(si, irn))) break; + if( sched_is_end(irn) || + (be_is_Reload(irn) && has_reg_class(si, irn)) || + /* do not move reload before its spill */ + (irn == be_get_Reload_mem(reload)) ) break; set_irn_link(irn, INT_TO_PTR(pressure+1)); DBG((si->dbg, LEVEL_5, "new regpressure before %+F: %d\n", irn, pressure+1)); @@ -2931,39 +3774,105 @@ move_reloads_upward(spill_ilp_t * si) irg_block_walk_graph(si->chordal_env->irg, walker_reload_mover, NULL, si); } + +/** + * Walk all irg blocks and check for interfering spills inside of phi classes + */ +static void +luke_meminterferencechecker(ir_node * bb, void * data) +{ + spill_ilp_t *si = (spill_ilp_t*)data; + irn_live_t *li1, + *li2; + + live_foreach(bb, li1) { + ir_node *a = (ir_node *) li1->irn; + + if(!be_is_Spill(a) && (!is_Phi(a) || get_irn_mode(a) != mode_T)) continue; + + /* a is only interesting if it is inside a phi class */ + if (get_phi_class(a)) { + for(li2=li1->next; li2; li2 = li2->next) { + ir_node *b = (ir_node *) li2->irn; + + if(!be_is_Spill(b) && (!is_Phi(b) || get_irn_mode(b) != mode_T)) continue; + + /* a and b are only interesting if they are in the same phi class */ + if(get_phi_class(a) == get_phi_class(b)) { + if(values_interfere_in_block(bb, a, b)) { + ir_fprintf(stderr, "$$ Spills interfere in %+F: %+F, %+F \t$$\n", bb, a, b); + } + } + } + } + } +} + +static void +verify_phiclasses(spill_ilp_t * si) +{ + /* analyze phi classes */ + phi_class_compute(si->chordal_env->irg); + + DBG((si->dbg, LEVEL_2, "\t calling memory interference checker\n")); + irg_block_walk_graph(si->chordal_env->irg, luke_meminterferencechecker, NULL, si); +} + +static void +walker_spillslotassigner(ir_node * irn, void * data) +{ + spill_ilp_t *si = (spill_ilp_t*)data; + void *cls; + + if(!be_is_Spill(irn)) return; + + /* set spill context to phi class if it has one ;) */ + + cls = get_phi_class(irn); + if(cls) + be_set_Spill_context(irn, cls); + else + be_set_Spill_context(irn, irn); +} + + +static void +assign_spillslots(spill_ilp_t * si) +{ + DBG((si->dbg, LEVEL_2, "\t calling spill slot assigner\n")); + irg_walk_graph(si->chordal_env->irg, walker_spillslotassigner, NULL, si); +} + void be_spill_remat(const be_chordal_env_t * chordal_env) { char problem_name[256]; char dump_suffix[256]; char dump_suffix2[256]; - char dump_suffix3[256]; struct obstack obst; spill_ilp_t si; 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); ir_snprintf(dump_suffix2, sizeof(dump_suffix2), "-%s-pressure", chordal_env->cls->name); - ir_snprintf(dump_suffix3, sizeof(dump_suffix3), "-%s-reloads_moved", chordal_env->cls->name); FIRM_DBG_REGISTER(si.dbg, "firm.be.ra.spillremat"); DBG((si.dbg, LEVEL_1, "\n\n\t\t===== Processing %s =====\n\n", problem_name)); +#ifdef VERIFY_DOMINANCE + be_check_dominance(chordal_env->irg); +#endif + obstack_init(&obst); si.chordal_env = chordal_env; si.obst = &obst; - si.senv = be_new_spill_env(chordal_env, is_mem_phi, &si); si.cls = chordal_env->cls; si.lpp = new_lpp(problem_name, lpp_minimize); si.remat_info = new_set(cmp_remat_info, 4096); + si.interferences = new_set(cmp_interference, 32); si.all_possible_remats = pset_new_ptr_default(); si.spills = pset_new_ptr_default(); si.inverse_ops = pset_new_ptr_default(); -#ifndef EXECFREQ_LOOPDEPH - si.execfreqs = compute_execfreq(chordal_env->irg); -#else - si.execfreqs = NULL; -#endif #ifdef KEEPALIVE si.keep = NULL; #endif @@ -2972,6 +3881,11 @@ be_spill_remat(const be_chordal_env_t * chordal_env) set_irg_link(chordal_env->irg, &si); compute_doms(chordal_env->irg); + /* compute phi classes */ +// phi_class_compute(chordal_env->irg); + + be_analyze_regpressure(chordal_env, "-pre"); + #ifdef COLLECT_REMATS /* collect remats */ DBG((si.dbg, LEVEL_1, "Collecting remats\n")); @@ -2990,6 +3904,8 @@ be_spill_remat(const be_chordal_env_t * chordal_env) dump_graph_with_remats(chordal_env->irg, dump_suffix); #endif + /* insert copies for phi arguments not in my regclass */ + irg_walk_graph(chordal_env->irg, walker_regclass_copy_insertor, NULL, &si); /* recompute liveness */ DBG((si.dbg, LEVEL_1, "Recomputing liveness\n")); @@ -3004,6 +3920,11 @@ be_spill_remat(const be_chordal_env_t * chordal_env) DBG((si.dbg, LEVEL_2, "\t blockwalker\n")); irg_block_walk_graph(chordal_env->irg, luke_blockwalker, NULL, &si); +#ifndef NO_MEMCOPIES + DBG((si.dbg, LEVEL_2, "\t memcopyhandler\n")); + memcopyhandler(&si); +#endif + #ifdef DUMP_ILP { FILE *f; @@ -3019,7 +3940,9 @@ be_spill_remat(const be_chordal_env_t * chordal_env) #ifdef SOLVE DBG((si.dbg, LEVEL_1, "\tSolving %F\n", chordal_env->irg)); +#ifdef ILP_TIMEOUT lpp_set_time_limit(si.lpp, ILP_TIMEOUT); +#endif #ifdef SOLVE_LOCAL lpp_solve_cplex(si.lpp); @@ -3054,32 +3977,38 @@ be_spill_remat(const be_chordal_env_t * chordal_env) kill_all_unused_values_in_schedule(&si); -// be_dump(chordal_env->irg, "-bla", dump_ir_block_graph); +#if defined(KEEPALIVE_SPILLS) || defined(KEEPALIVE_RELOADS) + be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph); +#endif + // move reloads upwards be_liveness(chordal_env->irg); irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si); + move_reloads_upward(&si); - dump_pressure_graph(&si, dump_suffix2); +#ifndef NO_MEMCOPIES + verify_phiclasses(&si); + assign_spillslots(&si); +#endif + + irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si); - // TODO fix temporarily exceeded regpressure due to remat2s + dump_pressure_graph(&si, dump_suffix2); - // TODO insert copys to fix interferences in memory + //be_analyze_regpressure(chordal_env, "-post"); - // move reloads upwards - move_reloads_upward(&si); - irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si); - dump_pressure_graph(&si, dump_suffix3); +#ifdef VERIFY_DOMINANCE + be_check_dominance(chordal_env->irg); +#endif free_dom(chordal_env->irg); + del_set(si.interferences); del_pset(si.inverse_ops); del_pset(si.all_possible_remats); del_pset(si.spills); -#ifndef EXECFREQ_LOOPDEPH - free_execfreq(si.execfreqs); -#endif free_lpp(si.lpp); obstack_free(&obst, NULL); -// exit(0); + DBG((si.dbg, LEVEL_1, "\tdone.\n")); } #else /* WITH_ILP */