X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=0de1bdca138bc8cad4581be244cd15f1a9665bdc;hb=97927c8e372f337e8342b698072facf4ffa453ad;hp=2fd073ea609b980839b68610996a872ccdb529a3;hpb=9ddbd0c91c28e03fc11832797b204f1d4d9cf82b;p=libfirm diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c index 2fd073ea6..0de1bdca1 100644 --- a/ir/be/bespillremat.c +++ b/ir/be/bespillremat.c @@ -33,56 +33,148 @@ #include "iredges.h" #include "execfreq.h" #include "irvrfy.h" +#include "irbackedge_t.h" #include +#include #include #include //#include -#include +//#include #include "be_t.h" #include "belive_t.h" #include "besched_t.h" #include "beirgmod.h" #include "bearch.h" +#include "beabi.h" #include "benode_t.h" #include "beutil.h" #include "bespillremat.h" #include "bespill.h" #include "bepressurestat.h" +#include "beprofile.h" #include "bechordal_t.h" -//#define DUMP_SOLUTION -//#define DUMP_ILP -//#define KEEPALIVE /* keep alive all inserted remats and dump graph with remats */ -//#define COLLECT_REMATS /* enable rematerialization */ -//#define COLLECT_INVERSE_REMATS /* enable placement of inverse remats */ -//#define ONLY_BRIGGS_REMATS /* only remats without parameters (or only with ignored params) */ -#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_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 NO_MEMCOPIES -//#define VERIFY_DOMINANCE -#define WITH_MEMOPERANDS +#ifdef WITH_LIBCORE +#include +#include +#endif /* WITH_LIBCORE */ + +#define DUMP_PROBLEM 1 +#define DUMP_MPS 2 +#define DUMP_SOLUTION 4 +#define DUMP_STATS 8 +#define DUMP_PRESSURE 16 + +#define KEEPALIVE_REMATS 1 +#define KEEPALIVE_SPILLS 2 +#define KEEPALIVE_RELOADS 4 + +#define VERIFY_MEMINTERF 1 +#define VERIFY_DOMINANCE 2 + +#define REMATS_NONE 0 +#define REMATS_BRIGGS 1 +#define REMATS_NOINVERSE 2 +#define REMATS_ALL 3 + +static int opt_dump_flags = 0; +static int opt_log = 0; +static int opt_keep_alive = 0; +static int opt_goodwin = 1; +static int opt_memcopies = 1; +static int opt_memoperands = 1; +static int opt_verify = VERIFY_MEMINTERF; +static int opt_remats = REMATS_ALL; +static int opt_repair_schedule = 0; +static int opt_no_enlarge_liveness = 0; +static int opt_remat_while_live = 1; +static int opt_timeout = 300; +static double opt_cost_reload = 8.0; +static double opt_cost_memoperand = 7.0; +static double opt_cost_spill = 50.0; +static double opt_cost_remat = 1.0; + + +#ifdef WITH_LIBCORE +static const lc_opt_enum_mask_items_t dump_items[] = { + { "problem", DUMP_PROBLEM }, + { "mps", DUMP_MPS }, + { "solution", DUMP_SOLUTION }, + { "stats", DUMP_STATS }, + { "pressure", DUMP_PRESSURE }, + { NULL, 0 } +}; + +static lc_opt_enum_mask_var_t dump_var = { + &opt_dump_flags, dump_items +}; + +static const lc_opt_enum_mask_items_t keepalive_items[] = { + { "remats", KEEPALIVE_REMATS }, + { "spills", KEEPALIVE_SPILLS }, + { "reloads", KEEPALIVE_RELOADS }, + { NULL, 0 } +}; + +static lc_opt_enum_mask_var_t keep_alive_var = { + &opt_keep_alive, keepalive_items +}; + +static const lc_opt_enum_mask_items_t remats_items[] = { + { "none", REMATS_NONE }, + { "briggs", REMATS_BRIGGS }, + { "noinverse", REMATS_NOINVERSE }, + { "all", REMATS_ALL }, + { NULL, 0 } +}; + +static lc_opt_enum_mask_var_t remats_var = { + &opt_remats, remats_items +}; + +static const lc_opt_table_entry_t options[] = { + LC_OPT_ENT_ENUM_MASK("keepalive", "keep alive remats, spills or reloads", &keep_alive_var), + + LC_OPT_ENT_BOOL ("goodwin", "activate goodwin reduction", &opt_goodwin), + LC_OPT_ENT_BOOL ("memcopies", "activate memcopy handling", &opt_memcopies), + LC_OPT_ENT_BOOL ("memoperands", "activate memoperands", &opt_memoperands), + LC_OPT_ENT_ENUM_INT ("remats", "type of remats to insert (none, briggs, noinverse or all)",&remats_var), + LC_OPT_ENT_BOOL ("repair_schedule", "repair the schedule by rematting once used nodes",&opt_repair_schedule), + LC_OPT_ENT_BOOL ("no_enlage_liveness", "do not enlarge liveness of operands of remats",&opt_no_enlarge_liveness), + LC_OPT_ENT_BOOL ("remat_while_live", "only remat where rematted value was live", &opt_remat_while_live), + + LC_OPT_ENT_ENUM_MASK("dump", "dump problem, mps, solution, stats or pressure", &dump_var), + LC_OPT_ENT_BOOL ("log", "activate the lpp log", &opt_log), + LC_OPT_ENT_INT ("timeout", "ILP solver timeout", &opt_timeout), + + LC_OPT_ENT_DBL ("cost_reload", "cost of a reload", &opt_cost_reload), + LC_OPT_ENT_DBL ("cost_memoperand", "cost of a memory operand", &opt_cost_memoperand), + LC_OPT_ENT_DBL ("cost_spill", "cost of a spill instruction", &opt_cost_spill), + LC_OPT_ENT_DBL ("cost_remat", "cost of a rematerialization", &opt_cost_remat), + { NULL } +}; + +void be_spill_remat_register_options(lc_opt_entry_t *grp) +{ + lc_opt_entry_t *my_grp = lc_opt_get_grp(grp, "remat"); + lc_opt_add_table(my_grp, options); +} +#endif + + +//#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */ +//#define SCHEDULE_PHIM /* insert phim nodes into schedule */ #define SOLVE //#define SOLVE_LOCAL #define LPP_SERVER "i44pc52" #define LPP_SOLVER "cplex" -#define COST_LOAD 8 -#define COST_MEMOPERAND 7 -#define COST_STORE 50 -#define COST_REMAT 1 -#define ILP_TIMEOUT 300 -#define MAX_PATHS 16 +#define MAX_PATHS INT_MAX #define ILP_UNDEF -1 typedef struct _spill_ilp_t { @@ -95,15 +187,14 @@ typedef struct _spill_ilp_t { set *remat_info; pset *all_possible_remats; pset *inverse_ops; -#ifdef KEEPALIVE ir_node *keep; -#endif set *values; /**< for collecting all definitions of values before running ssa-construction */ pset *spills; set *interferences; ir_node *m_unknown; -#ifdef WITH_MEMOPERANDS set *memoperands; +#ifndef SCHEDULE_PHIM + pset *phims; #endif DEBUG_ONLY(firm_dbg_module_t * dbg); } spill_ilp_t; @@ -174,13 +265,11 @@ typedef struct _spill_t { ilp_var_t spill; } spill_t; -#ifdef WITH_MEMOPERANDS typedef struct _memoperand_t { ir_node *irn; /**< the irn */ unsigned int pos; /**< the position of the argument */ ilp_var_t ilp; /**< the ilp var for this memory operand */ } memoperand_t; -#endif static INLINE int has_reg_class(const spill_ilp_t * si, const ir_node * irn) @@ -221,7 +310,6 @@ cmp_spill(const void *a, const void *b, size_t size) return !(p->irn == q->irn); } -#ifdef WITH_MEMOPERANDS static int cmp_memoperands(const void *a, const void *b, size_t size) { @@ -230,7 +318,6 @@ cmp_memoperands(const void *a, const void *b, size_t size) return !(p->irn == q->irn && p->pos == q->pos); } -#endif static keyval_t * set_find_keyval(set * set, const void * key) @@ -271,7 +358,6 @@ set_insert_def(set * set, const ir_node * value) return set_insert(set, &query, sizeof(query), HASH_PTR(value)); } -#ifdef WITH_MEMOPERANDS static memoperand_t * set_insert_memoperand(set * set, ir_node * irn, unsigned int pos, ilp_var_t ilp) { @@ -292,7 +378,6 @@ set_find_memoperand(set * set, const ir_node * irn, unsigned int pos) query.pos = pos; return set_find(set, &query, sizeof(query), HASH_PTR(irn)+pos); } -#endif static spill_t * @@ -341,6 +426,9 @@ static double execution_frequency(const spill_ilp_t *si, const ir_node * irn) { #define FUDGE 0.001 + if(be_profile_has_data()) + return ((double)be_profile_get_block_execcount(get_block(irn))) + FUDGE; + #ifndef EXECFREQ_LOOPDEPH return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE; #else @@ -355,9 +443,9 @@ static double get_cost(const spill_ilp_t * si, const ir_node * irn) { if(be_is_Spill(irn)) { - return COST_STORE; + return opt_cost_spill; } else if(be_is_Reload(irn)){ - return COST_LOAD; + return opt_cost_reload; } else { return arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, irn); } @@ -404,18 +492,18 @@ get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * const ir_node *proj = NULL; if(is_Proj(dest_value)) { - op = get_irn_n(op, 0); + op = get_Proj_pred(op); proj = dest_value; } if(!is_rematerializable(si, op)) return NULL; - remat = obstack_alloc(si->obst, sizeof(*remat)); - remat->op = op; - remat->cost = get_cost(si, op); - remat->value = dest_value; - remat->proj = proj; + remat = obstack_alloc(si->obst, sizeof(*remat)); + remat->op = op; + remat->cost = get_cost(si, op); + remat->value = dest_value; + remat->proj = proj; remat->inverse = 0; } else { arch_inverse_t inverse; @@ -505,7 +593,6 @@ add_remat(const spill_ilp_t * si, const remat_t * remat) } } -#ifdef NO_SINGLE_USE_REMATS static int get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn) { @@ -521,22 +608,24 @@ get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn) return i; } -#endif -#ifdef ONLY_BRIGGS_REMATS static int get_irn_n_nonignore_args(const spill_ilp_t * si, const ir_node * irn) { int n; - unsigned int ret = 0; + int ret = 0; + + if(is_Proj(irn)) + irn = get_Proj_pred(irn); for(n=get_irn_arity(irn)-1; n>=0; --n) { - if(has_reg_class(si, irn)) ++ret; + const ir_node *arg = get_irn_n(irn, n); + + if(has_reg_class(si, arg)) ++ret; } return ret; } -#endif static INLINE void get_remats_from_op(spill_ilp_t * si, const ir_node * op) @@ -545,12 +634,8 @@ get_remats_from_op(spill_ilp_t * si, const ir_node * op) remat_t *remat; if( has_reg_class(si, op) -#ifdef NO_SINGLE_USE_REMATS - && (get_irn_n_nonremat_edges(si, op) > 1) -#endif -#ifdef ONLY_BRIGGS_REMATS - && (get_irn_n_nonignore_args(si, op) == 0) -#endif + && (opt_repair_schedule || get_irn_n_nonremat_edges(si, op) > 1) + && (opt_remats != REMATS_BRIGGS || get_irn_n_nonignore_args(si, op) == 0) ) { remat = get_remat_from_op(si, op, op); if(remat) { @@ -558,22 +643,21 @@ get_remats_from_op(spill_ilp_t * si, const ir_node * op) } } -#if defined(COLLECT_INVERSE_REMATS) && !defined(ONLY_BRIGGS_REMATS) - /* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg) - for each arg */ - 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 */ - remat = get_remat_from_op(si, arg, op); - if(remat) { - add_remat(si, remat); + if(opt_remats == REMATS_ALL) { + /* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg) + for each arg */ + 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 */ + remat = get_remat_from_op(si, arg, op); + if(remat) { + add_remat(si, remat); + } } } } -#endif - } static INLINE int @@ -688,6 +772,55 @@ sched_put_before(const spill_ilp_t * si, ir_node * insert, ir_node * irn) sched_add_after(insert, irn); } +static ir_node * +next_post_remat(const ir_node * irn) +{ + op_t *op; + ir_node *next; + + if(is_Block(irn)) { + next = sched_block_first_nonphi(irn); + } else { + next = sched_next_op(irn); + } + + if(sched_is_end(next)) + return NULL; + + op = get_irn_link(next); + if(op->is_remat && !op->attr.remat.pre) { + return next; + } + + return NULL; +} + + +static ir_node * +next_pre_remat(const spill_ilp_t * si, const ir_node * irn) +{ + op_t *op; + ir_node *ret; + + if(is_Block(irn)) { + ret = sched_block_last_noncf(si, irn); + ret = sched_next(ret); + ret = sched_prev_op(ret); + } else { + ret = sched_prev_op(irn); + } + + if(sched_is_end(ret) || is_Phi(ret)) + return NULL; + + op = (op_t*)get_irn_link(ret); + if(op->is_remat && op->attr.remat.pre) { + return ret; + } + + return NULL; +} + /** * Tells you whether a @p remat can be placed before the irn @p pos */ @@ -723,15 +856,15 @@ can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * for(n=get_irn_arity(op)-1; n>=0 && res; --n) { const ir_node *arg = get_irn_n(op, n); -#ifdef NO_ENLARGE_L1V3N355 - if(has_reg_class(si, arg) && live) { - res &= pset_find_ptr(live, arg)?1:0; + if(opt_no_enlarge_liveness) { + if(has_reg_class(si, arg) && live) { + res &= pset_find_ptr((pset*)live, arg)?1:0; + } else { + res &= value_is_defined_before(si, pos, arg); + } } else { res &= value_is_defined_before(si, pos, arg); } -#else - res &= value_is_defined_before(si, pos, arg); -#endif } return res; @@ -819,7 +952,7 @@ insert_remat_after(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const *proj_copy; op_t *op; - DBG((si->dbg, LEVEL_3, "\t >inserting remat %+F\n", remat->op)); + DBG((si->dbg, LEVEL_3, "\t >inserting remat2 %+F\n", remat->op)); copy = insert_copy_after(si, remat->op, pos); @@ -899,24 +1032,86 @@ get_block_n_succs(const ir_node *block) { return edge ? 2 : 1; } +static int +is_start_block(const ir_node * bb) +{ + return get_irg_start_block(get_irn_irg(bb)) == bb; +} + static int is_merge_edge(const ir_node * bb) { -#ifdef GOODWIN_REDUCTION - return get_block_n_succs(bb) == 1; -#else - return 1; -#endif + if(is_start_block(bb)) + return 0; + + if(opt_goodwin) + return get_block_n_succs(bb) == 1; + else + return 1; } static int is_diverge_edge(const ir_node * bb) { -#ifdef GOODWIN_REDUCTION - return get_Block_n_cfgpreds(bb) == 1; -#else - return 1; -#endif + if(is_start_block(bb)) + return 0; + + if(opt_goodwin) + return get_Block_n_cfgpreds(bb) == 1; + else + return 1; +} + +static void +get_live_end(spill_ilp_t * si, ir_node * bb, pset * live) +{ + ir_node *irn; + int i; + + be_lv_foreach(si->lv, bb, be_lv_state_end, i) { + irn = be_lv_get_irn(si->lv, bb, i); + + if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { + pset_insert_ptr(live, irn); + } + } + + irn = sched_last(bb); + + /* all values eaten by control flow operations are also live until the end of the block */ + sched_foreach_reverse(bb, irn) { + int i; + + if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break; + + for(i=get_irn_arity(irn)-1; i>=0; --i) { + ir_node *arg = get_irn_n(irn,i); + + if(has_reg_class(si, arg)) { + pset_insert_ptr(live, arg); + } + } + } + /* + * find values that are used by remats at end of block + * and insert them into live set + */ + foreach_pre_remat(si, bb, irn) { + int n; + + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(irn, n); + + if(!has_reg_class(si, remat_arg)) continue; + + /* if value is becoming live through use by remat */ + if(!pset_find_ptr(live, remat_arg)) { + DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat at end of block %+F\n", remat_arg, irn)); + + pset_insert_ptr(live, remat_arg); + } + } + } } static void @@ -949,7 +1144,6 @@ walker_regclass_copy_insertor(ir_node * irn, void * data) } } - /** * Insert (so far unused) remats into the irg to * recompute the potential liveness of all values @@ -958,13 +1152,18 @@ static void walker_remat_insertor(ir_node * bb, void * data) { spill_ilp_t *si = data; - spill_bb_t *spill_bb; ir_node *irn; int n, i; - pset *live = pset_new_ptr_default(); + pset *live; + pset *post_remats; + remat_t *remat; + + /* skip start block, no remats to do there */ + if(is_start_block(bb)) return; DBG((si->dbg, LEVEL_3, "\t Entering %+F\n\n", bb)); + live = pset_new_ptr_default(); be_lv_foreach(si->lv, bb, be_lv_state_end, i) { ir_node *value = be_lv_get_irn(si->lv, bb, i); @@ -974,76 +1173,45 @@ walker_remat_insertor(ir_node * bb, void * data) } } - spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb)); - set_irn_link(bb, spill_bb); - irn = sched_last(bb); while(!sched_is_end(irn)) { ir_node *next; - op_t *op; pset *args; ir_node *arg; - pset *remat_args; + pset *used; next = sched_prev(irn); - DBG((si->dbg, LEVEL_5, "\t at %+F (next: %+F)\n", irn, next)); + /* delete defined value from live set */ + if(has_reg_class(si, irn)) { + pset_remove_ptr(live, irn); + } if(is_Phi(irn) || is_Proj(irn)) { - op_t *op; - - if(has_reg_class(si, irn)) { - pset_remove_ptr(live, irn); - } - - op = obstack_alloc(si->obst, sizeof(*op)); - op->is_remat = 0; - op->attr.live_range.args.reloads = NULL; - op->attr.live_range.ilp = ILP_UNDEF; - set_irn_link(irn, op); - irn = next; continue; } - op = obstack_alloc(si->obst, sizeof(*op)); - op->is_remat = 0; - op->attr.live_range.ilp = ILP_UNDEF; - op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn)); - memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn)); - set_irn_link(irn, op); - args = pset_new_ptr_default(); + used = pset_new_ptr_default(); - /* collect arguments of op */ + /* collect arguments of op and set args of op already live in epilog */ for (n = get_irn_arity(irn)-1; n>=0; --n) { ir_node *arg = get_irn_n(irn, n); pset_insert_ptr(args, arg); - } - - /* set args of op already live in epilog */ - pset_foreach(args, arg) { if(has_reg_class(si, arg)) { pset_insert_ptr(live, arg); + pset_insert_ptr(used, arg); } } - /* delete defined value from live set */ - if(has_reg_class(si, irn)) { - pset_remove_ptr(live, irn); - } - - - remat_args = pset_new_ptr_default(); /* insert all possible remats before irn */ pset_foreach(args, arg) { remat_info_t *remat_info, query; - remat_t *remat; - /* continue if the operand has the wrong reg class - */ + /* continue if the operand has the wrong reg class */ if(!has_reg_class(si, arg)) continue; @@ -1061,41 +1229,34 @@ walker_remat_insertor(ir_node * bb, void * data) ir_node *remat_irn = NULL; 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)) { - remat_irn = insert_remat_before(si, remat, irn, live); - } -#else 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); + /* collect args of remats which are not args of op */ + if(has_reg_class(si, remat_arg) && !pset_find_ptr(args, remat_arg)) { + pset_insert_ptr(used, remat_arg); + } } } } } } - /* now we add remat args to op's args because they could also die at this op */ - pset_foreach(args,arg) { - if(pset_find_ptr(remat_args, arg)) { - pset_remove_ptr(remat_args, arg); - } - } - pset_foreach(remat_args,arg) { - pset_insert_ptr(args, arg); + /* do not place post remats after jumps */ + if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) { + del_pset(used); + del_pset(args); + break; } /* insert all possible remats after irn */ - pset_foreach(args, arg) { + post_remats = pset_new_ptr_default(); + pset_foreach(used, arg) { remat_info_t *remat_info, query; - remat_t *remat; /* continue if the operand has the wrong reg class */ if(!has_reg_class(si, arg)) @@ -1110,82 +1271,167 @@ 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_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_after(si, remat, irn, live); + + /* only remat values that can be used by real ops */ + if(!opt_remat_while_live || pset_find_ptr(live, remat->value)) { + pset_insert_ptr(post_remats, remat); } -#else - insert_remat_after(si, remat, irn, live); -#endif } } } } + pset_foreach(post_remats, remat) { + insert_remat_after(si, remat, irn, live); + } + del_pset(post_remats); - del_pset(remat_args); + del_pset(used); del_pset(args); irn = next; } - be_lv_foreach(si->lv, bb, be_lv_state_end | be_lv_state_in, i) { - ir_node *value = be_lv_get_irn(si->lv, bb, i); + /* add remats at end if successor has multiple predecessors */ + if(is_merge_edge(bb)) { + pset *live_out = pset_new_ptr_default(); + ir_node *value; - /* add remats at end if successor has multiple predecessors */ - if(is_merge_edge(bb)) { - /* add remats at end of block */ - if (be_is_live_end(si->lv, bb, value) && has_reg_class(si, value)) { - remat_info_t *remat_info, - query; - remat_t *remat; - - query.irn = value; - query.remats = NULL; - query.remats_by_operand = NULL; - remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); - - if(remat_info && remat_info->remats) { - pset_foreach(remat_info->remats, remat) { - DBG((si->dbg, LEVEL_4, "\t considering remat %+F at end of block %+F\n", remat->op, bb)); - - insert_remat_before(si, remat, bb, NULL); - } + get_live_end(si, bb, live_out); + + /* add remats at end of block */ + pset_foreach(live_out, value) { + remat_info_t *remat_info, + query; + + query.irn = value; + query.remats = NULL; + query.remats_by_operand = NULL; + remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); + + if(remat_info && remat_info->remats) { + pset_foreach(remat_info->remats, remat) { + DBG((si->dbg, LEVEL_4, "\t considering remat %+F at end of block %+F\n", remat->op, bb)); + + insert_remat_before(si, remat, bb, live_out); } } } - if(is_diverge_edge(bb)) { - /* add remat2s at beginning of block */ - if ((be_is_live_in(si->lv, bb, value) || (is_Phi(value) && get_nodes_block(value)==bb)) && has_reg_class(si, value)) { - remat_info_t *remat_info, - query; - remat_t *remat; + del_pset(live_out); + } + + if(is_diverge_edge(bb)) { + pset *live_in = pset_new_ptr_default(); + ir_node *value; + + be_lv_foreach(si->lv, bb, be_lv_state_in, i) { + value = be_lv_get_irn(si->lv, bb, i); + + if(has_reg_class(si, value)) { + pset_insert_ptr(live_in, value); + } + } + /* add phis to live_in */ + sched_foreach(bb, value) { + if(!is_Phi(value)) break; - query.irn = value; - query.remats = NULL; - query.remats_by_operand = NULL; - remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); + if(has_reg_class(si, value)) { + pset_insert_ptr(live_in, value); + } + } - if(remat_info && remat_info->remats) { - pset_foreach(remat_info->remats, remat) { - DBG((si->dbg, LEVEL_4, "\t considering remat %+F at beginning of block %+F\n", remat->op, bb)); + /* add remat2s at beginning of block */ + post_remats = pset_new_ptr_default(); + pset_foreach(live_in, value) { + remat_info_t *remat_info, + query; - /* put the remat here if all its args are available */ - insert_remat_after(si, remat, bb, NULL); + query.irn = value; + query.remats = NULL; + query.remats_by_operand = NULL; + remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); + + if(remat_info && remat_info->remats_by_operand) { + pset_foreach(remat_info->remats_by_operand, remat) { + DBG((si->dbg, LEVEL_4, "\t considering remat2 %+F at beginning of block %+F\n", remat->op, bb)); + /* put the remat here if all its args are available and result is still live */ + if(!opt_remat_while_live || pset_find_ptr(live_in, remat->value)) { + pset_insert_ptr(post_remats, remat); } } } } + pset_foreach(post_remats, remat) { + insert_remat_after(si, remat, bb, live_in); + } + del_pset(post_remats); + del_pset(live_in); } } +static int +can_be_copied(const ir_node * bb, const ir_node * irn) +{ + const ir_edge_t *edge = get_block_succ_first(bb); + const ir_node *next_bb = edge->src; + int pos = edge->pos; + const ir_node *phi; + + assert(is_merge_edge(bb)); + + sched_foreach(next_bb, phi) { + const ir_node *phi_arg; + + if(!is_Phi(phi)) break; + + phi_arg = get_irn_n(phi, pos); + + if(phi_arg == irn) { + return 1; + } + } + return 0; +} + +/** + * Initialize additional node info + */ +static void +luke_initializer(ir_node * bb, void * data) +{ + spill_ilp_t *si = (spill_ilp_t*)data; + spill_bb_t *spill_bb; + ir_node *irn; + + spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb)); + set_irn_link(bb, spill_bb); + + sched_foreach(bb, irn) { + op_t *op; + + op = obstack_alloc(si->obst, sizeof(*op)); + op->is_remat = 0; + op->attr.live_range.ilp = ILP_UNDEF; + if(is_Phi(irn)) { + if(opt_memcopies) { + op->attr.live_range.args.copies = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn)); + memset(op->attr.live_range.args.copies, 0xFF, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn)); + } + } else if(!is_Proj(irn)) { + op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn)); + memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn)); + } else { + op->attr.live_range.args.reloads = NULL; + } + set_irn_link(irn, op); + } +} + + /** * Preparation of blocks' ends for Luke Blockwalker(tm)(R) */ @@ -1201,18 +1447,28 @@ luke_endwalker(ir_node * bb, void * data) spill_bb_t *spill_bb = get_irn_link(bb); int i; - live = pset_new_ptr_default(); use_end = pset_new_ptr_default(); be_lv_foreach(si->lv, bb, be_lv_state_end, i) { irn = be_lv_get_irn(si->lv, bb, i); if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { - op_t *op; - pset_insert_ptr(live, irn); - op = get_irn_link(irn); - assert(!op->is_remat); + } + } + /* + * find values that are used by remats at end of block + * and insert them into live set + */ + foreach_pre_remat(si, bb, irn) { + int n; + + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(irn, n); + + if(has_reg_class(si, remat_arg)) { + pset_insert_ptr(live, remat_arg); + } } } @@ -1251,6 +1507,7 @@ luke_endwalker(ir_node * bb, void * data) spill_t query, *spill; double spill_cost; + int default_spilled; /* handle values used by control flow nodes later separately */ @@ -1259,29 +1516,26 @@ luke_endwalker(ir_node * bb, void * data) 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); + spill_cost = is_Unknown(irn)?0.0001:opt_cost_spill*execution_frequency(si, bb); ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb); spill->reg_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 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_default(si->lpp, buf, lpp_binary, 0.0, 0.0); + spill->mem_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); /* by default spill value right after definition */ - if(be_is_live_in(si->lv, bb, irn)) { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 0.0); - } else { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 1.0); - } + default_spilled = be_is_live_in(si->lv, bb, irn) || is_Phi(irn); + spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, !default_spilled); 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_default(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb), 0.0); + reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), can_be_copied(bb, irn)); set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload)); /* reload <= mem_out */ @@ -1301,14 +1555,15 @@ luke_endwalker(ir_node * bb, void * data) ilp_cst_t end_use_req, rel_cst; ilp_var_t reload; + int default_spilled; 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); + spill_cost = is_Unknown(irn)?0.0001:opt_cost_spill*execution_frequency(si, bb); ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", irn, bb); - spill->reg_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0); + spill->reg_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); /* if irn is used at the end of the block, then it is live anyway */ //lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0); @@ -1316,15 +1571,12 @@ luke_endwalker(ir_node * bb, void * data) spill->mem_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - if(be_is_live_in(si->lv, bb, irn)) { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 0.0); - } else { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 1.0); - } + default_spilled = be_is_live_in(si->lv, bb, irn) || is_Phi(irn); + spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, !default_spilled); /* reload for use be control flow op */ ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn); - reload = lpp_add_var_default(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb), 1.0); + reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0); set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload)); /* reload <= mem_out */ @@ -1344,55 +1596,6 @@ luke_endwalker(ir_node * bb, void * data) del_pset(use_end); } -static ir_node * -next_post_remat(const ir_node * irn) -{ - op_t *op; - ir_node *next; - - if(is_Block(irn)) { - next = sched_block_first_nonphi(irn); - } else { - next = sched_next_op(irn); - } - - if(sched_is_end(next)) - return NULL; - - op = get_irn_link(next); - if(op->is_remat && !op->attr.remat.pre) { - return next; - } - - return NULL; -} - - -static ir_node * -next_pre_remat(const spill_ilp_t * si, const ir_node * irn) -{ - op_t *op; - ir_node *ret; - - if(is_Block(irn)) { - ret = sched_block_last_noncf(si, irn); - ret = sched_next(ret); - ret = sched_prev_op(ret); - } else { - ret = sched_prev_op(irn); - } - - if(sched_is_end(ret) || is_Phi(ret)) - return NULL; - - op = (op_t*)get_irn_link(ret); - if(op->is_remat && op->attr.remat.pre) { - return ret; - } - - return NULL; -} - /** * Find a remat of value @p value in the epilog of @p pos */ @@ -1428,11 +1631,12 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) spill_t *spill, query; char buf[256]; + int default_spilled; 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); + double spill_cost = is_Unknown(irn)?0.0001:opt_cost_spill*execution_frequency(si, bb); spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn)); @@ -1444,48 +1648,13 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) spill->mem_out = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb); - if(be_is_live_in(si->lv, bb, irn)) { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 0.0); - } else { - spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, 1.0); - } + default_spilled = be_is_live_in(si->lv, bb, irn) || is_Phi(irn); + spill->spill = lpp_add_var_default(si->lpp, buf, lpp_binary, spill_cost, !default_spilled); } return spill; } -static void -get_live_end(spill_ilp_t * si, ir_node * bb, pset * live) -{ - ir_node *irn; - int i; - - be_lv_foreach(si->lv, bb, be_lv_state_end, i) { - irn = be_lv_get_irn(si->lv, bb, i); - - if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { - pset_insert_ptr(live, irn); - } - } - - irn = sched_last(bb); - - /* all values eaten by control flow operations are also live until the end of the block */ - sched_foreach_reverse(bb, irn) { - int i; - - if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break; - - for(i=get_irn_arity(irn)-1; i>=0; --i) { - ir_node *arg = get_irn_n(irn,i); - - if(has_reg_class(si, arg)) { - pset_insert_ptr(live, arg); - } - } - } -} - /** * Inserts ILP-constraints and variables for memory copying before the given position */ @@ -1546,7 +1715,6 @@ insert_mem_copy_position(spill_ilp_t * si, pset * live, const ir_node * block) 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); @@ -1601,10 +1769,7 @@ luke_blockwalker(ir_node * bb, void * data) ir_node *tmp; spill_t *spill; pset *defs = pset_new_ptr_default(); -#ifdef WITH_MEMOPERANDS const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; -#endif - live = pset_new_ptr_default(); @@ -1651,16 +1816,48 @@ luke_blockwalker(ir_node * bb, void * data) lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); } } - /* maybe we should also assure that reg_out >= live_range etc. */ + ir_snprintf(buf, sizeof(buf), "reg_out2_%N_%N", bb, irn); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0); + + /* value may only die at bb end if it is used for a mem copy */ + /* reg_out + \sum copy - reload - remat - live_range >= 0 */ + lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0); + if(reload != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, reload, -1.0); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -1.0); + foreach_pre_remat(si, bb, tmp) { + op_t *remat_op = get_irn_link(tmp); + if(remat_op->attr.remat.remat->value == irn) { + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); + } + } + if(is_merge_edge(bb)) { + const ir_edge_t *edge = get_block_succ_first(bb); + const ir_node *next_bb = edge->src; + int pos = edge->pos; + const ir_node *phi; + + sched_foreach(next_bb, phi) { + const ir_node *phi_arg; + + if(!is_Phi(phi)) break; + + phi_arg = get_irn_n(phi, pos); + + if(phi_arg == irn) { + op_t *phi_op = get_irn_link(phi); + ilp_var_t copy = phi_op->attr.live_range.args.copies[pos]; + + lpp_set_factor_fast(si->lpp, cst, copy, 1.0); + } + } + } } -#ifndef NO_MEMCOPIES - insert_mem_copy_position(si, live, bb); -#endif + if(opt_memcopies) + insert_mem_copy_position(si, live, bb); /* - * start new live ranges for values used by remats at end of block - * and assure the remat args are available + * assure the remat args are available */ foreach_pre_remat(si, bb, tmp) { op_t *remat_op = get_irn_link(tmp); @@ -1669,29 +1866,22 @@ luke_blockwalker(ir_node * bb, void * data) for (n=get_irn_arity(tmp)-1; n>=0; --n) { ir_node *remat_arg = get_irn_n(tmp, n); op_t *arg_op = get_irn_link(remat_arg); - ilp_var_t prev_lr; if(!has_reg_class(si, remat_arg)) continue; - /* if value is becoming live through use by remat */ - if(!pset_find_ptr(live, remat_arg)) { - ir_snprintf(buf, sizeof(buf), "lr_%N_end%N", remat_arg, bb); - prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0); - - arg_op->attr.live_range.ilp = prev_lr; - arg_op->attr.live_range.op = bb; - - DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat at end of block %+F\n", remat_arg, tmp)); + spill = set_find_spill(spill_bb->ilp, remat_arg); + assert(spill); - pset_insert_ptr(live, remat_arg); - add_to_spill_bb(si, bb, remat_arg); - } + /* arguments of remats have to be live until the very end of the block + * remat = reg_out(remat_arg) and (reload(remat_arg) or live_range(remat_arg)), + * no remats, they could be in wrong order + */ - /* remat <= live_rang(remat_arg) [ + reload(remat_arg) ] */ ir_snprintf(buf, sizeof(buf), "req_remat_%N_arg_%N", tmp, remat_arg); cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 3.0); + lpp_set_factor_fast(si->lpp, cst, spill->reg_out, -2.0); lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0); /* use reload placed for this argument */ @@ -1727,9 +1917,7 @@ luke_blockwalker(ir_node * bb, void * data) pset *used; pset *remat_defs; keyval_t *keyval; -#ifdef WITH_MEMOPERANDS ilp_cst_t one_memoperand; -#endif /* iterate only until first phi */ if(is_Phi(irn)) @@ -1738,6 +1926,7 @@ luke_blockwalker(ir_node * bb, void * data) 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 */ @@ -1757,30 +1946,32 @@ luke_blockwalker(ir_node * bb, void * data) used = pset_new_ptr(pset_count(live) + get_irn_arity(irn)); remat_defs = pset_new_ptr(pset_count(live)); - for (n=get_irn_arity(irn)-1; n>=0; --n) { - ir_node *irn_arg = get_irn_n(irn, n); - if(has_reg_class(si, irn_arg)) { - set_insert_keyval(args, irn_arg, (void*)n); - pset_insert_ptr(used, irn_arg); + if(!is_start_block(bb) || !be_is_Barrier(irn)) { + for (n=get_irn_arity(irn)-1; n>=0; --n) { + ir_node *irn_arg = get_irn_n(irn, n); + if(has_reg_class(si, irn_arg)) { + set_insert_keyval(args, irn_arg, (void*)n); + pset_insert_ptr(used, irn_arg); + } } - } - foreach_post_remat(irn, tmp) { - op_t *remat_op = get_irn_link(tmp); + foreach_post_remat(irn, tmp) { + op_t *remat_op = get_irn_link(tmp); - pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value); + pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value); - for (n=get_irn_arity(tmp)-1; n>=0; --n) { - ir_node *remat_arg = get_irn_n(tmp, n); - if(has_reg_class(si, remat_arg)) { - pset_insert_ptr(used, remat_arg); + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(tmp, n); + if(has_reg_class(si, remat_arg)) { + pset_insert_ptr(used, remat_arg); + } } } - } - foreach_pre_remat(si, irn, tmp) { - for (n=get_irn_arity(tmp)-1; n>=0; --n) { - ir_node *remat_arg = get_irn_n(tmp, n); - if(has_reg_class(si, remat_arg)) { - pset_insert_ptr(used, remat_arg); + foreach_pre_remat(si, irn, tmp) { + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(tmp, n); + if(has_reg_class(si, remat_arg)) { + pset_insert_ptr(used, remat_arg); + } } } } @@ -1818,7 +2009,6 @@ luke_blockwalker(ir_node * bb, void * data) } } - // 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); } @@ -1989,29 +2179,8 @@ skip_one_must_die: cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); lpp_set_factor_fast(si->lpp, cst, post_use, -1.0); lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0); - - } - - /* 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_uniq(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, post_use, 1.0); - lpp_set_factor_fast(si->lpp, cst, 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_uniq(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); - } } - /* forall post remat which use arg add a similar cst */ foreach_post_remat(irn, remat) { int n; @@ -2023,6 +2192,7 @@ skip_one_must_die: if(remat_arg == arg) { DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn)); + /* post_use >= remat */ ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++); cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); lpp_set_factor_fast(si->lpp, cst, post_use, -1.0); @@ -2031,42 +2201,110 @@ skip_one_must_die: } } -#ifdef WITH_MEMOPERANDS - for(n = get_irn_arity(irn)-1; n>=0; --n) { - if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) { - ilp_var_t memoperand; + /* 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_uniq(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, post_use, 1.0); + lpp_set_factor_fast(si->lpp, cst, 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_uniq(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); + } + } + + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { + for(n = get_irn_arity(irn)-1; n>=0; --n) { + if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) { + ilp_var_t memoperand; - ir_snprintf(buf, sizeof(buf), "memoperand_%N_%d", irn, n); - memoperand = lpp_add_var_default(si->lpp, buf, lpp_binary, COST_MEMOPERAND*execution_frequency(si, bb), 0.0); - set_insert_memoperand(si->memoperands, irn, n, memoperand); + ir_snprintf(buf, sizeof(buf), "memoperand_%N_%d", irn, n); + memoperand = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_memoperand*execution_frequency(si, bb), 0.0); + set_insert_memoperand(si->memoperands, irn, n, memoperand); - ir_snprintf(buf, sizeof(buf), "nolivepost_%N_%d", irn, n); - cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); + ir_snprintf(buf, sizeof(buf), "nolivepost_%N_%d", irn, n); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); - lpp_set_factor_fast(si->lpp, cst, memoperand, 1.0); - lpp_set_factor_fast(si->lpp, cst, post_use, 1.0); -// if(arg_op->attr.live_range.ilp != ILP_UNDEF) -// lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, memoperand, 1.0); + lpp_set_factor_fast(si->lpp, cst, post_use, 1.0); + } } } -#endif /* 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); - } /* just to be sure */ check_post = ILP_UNDEF; - + /* allow original defintions to be removed */ + if(opt_repair_schedule) { + pset_foreach(defs, tmp) { + op_t *tmp_op = get_irn_link(tmp); + spill_t *spill = set_find_spill(spill_bb->ilp, tmp); +#if 1 + ilp_var_t delete; + assert(spill); + + ir_snprintf(buf, sizeof(buf), "delete_%N", tmp); + delete = lpp_add_var_default(si->lpp, buf, lpp_binary, -1.0*get_cost(si, irn)*execution_frequency(si, bb), 0.0); + + /* op may not be killed if its first live_range is 1 */ + ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); + lpp_set_factor_fast(si->lpp, cst, delete, 1.0); + lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0); + + /* op may not be killed if it is spilled after the definition */ + ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); + lpp_set_factor_fast(si->lpp, cst, delete, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0); +#else + ilp_var_t keep; + assert(spill); + + ir_snprintf(buf, sizeof(buf), "keep_%N", tmp); + keep = lpp_add_var_default(si->lpp, buf, lpp_binary, get_cost(si, irn)*execution_frequency(si, bb), 1.0); + + /* op may not be killed if its first live_range is 1 */ + ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0); + lpp_set_factor_fast(si->lpp, cst, keep, 1.0); + lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, -1.0); + + /* op may not be killed if it is spilled after the definition */ + ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0); + lpp_set_factor_fast(si->lpp, cst, keep, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0); +#endif + } + } else { + pset_foreach(defs, tmp) { + op_t *tmp_op = get_irn_link(tmp); + spill_t *spill = set_find_spill(spill_bb->ilp, tmp); + assert(spill); + + /* live_range or spill should be 1 + TODO: lr should be live until first use */ + ir_snprintf(buf, sizeof(buf), "nokillorig_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 1.0); + lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0); + } + } /****************** @@ -2083,10 +2321,10 @@ skip_one_must_die: pset_remove_ptr(live, tmp); } -#ifdef WITH_MEMOPERANDS - ir_snprintf(buf, sizeof(buf), "one_memoperand_%N", irn); - one_memoperand = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); -#endif + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { + ir_snprintf(buf, sizeof(buf), "one_memoperand_%N", irn); + one_memoperand = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); + } /*********************************************************** * 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 @@ -2099,15 +2337,13 @@ skip_one_must_die: int i = PTR_TO_INT(keyval->val); op_t *arg_op = get_irn_link(arg); ilp_cst_t requirements; -#ifdef WITH_MEMOPERANDS int n_memoperands; -#endif 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_default(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb), 1.0); + op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0); /* reload <= mem_out */ ir_snprintf(buf, sizeof(buf), "req_reload_%N_%N", arg, irn); @@ -2129,35 +2365,35 @@ skip_one_must_die: } } -#ifdef WITH_MEMOPERANDS - n_memoperands = 0; - for(n = get_irn_arity(irn)-1; n>=0; --n) { - if(get_irn_n(irn, n) == arg) { - n_memoperands++; + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { + n_memoperands = 0; + for(n = get_irn_arity(irn)-1; n>=0; --n) { + if(get_irn_n(irn, n) == arg) { + n_memoperands++; + } } - } - for(n = get_irn_arity(irn)-1; n>=0; --n) { - if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) { - memoperand_t *memoperand; - memoperand = set_find_memoperand(si->memoperands, irn, n); + for(n = get_irn_arity(irn)-1; n>=0; --n) { + if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) { + memoperand_t *memoperand; + memoperand = set_find_memoperand(si->memoperands, irn, n); - /* memoperand <= mem_out */ - ir_snprintf(buf, sizeof(buf), "req_memoperand_%N_%d", irn, n); - cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, memoperand->ilp, 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0); + /* memoperand <= mem_out */ + ir_snprintf(buf, sizeof(buf), "req_memoperand_%N_%d", irn, n); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, memoperand->ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0); - /* the memoperand is only sufficient if it is used once by the op */ - if(n_memoperands == 1) - lpp_set_factor_fast(si->lpp, requirements, memoperand->ilp, 1.0); + /* the memoperand is only sufficient if it is used once by the op */ + if(n_memoperands == 1) + lpp_set_factor_fast(si->lpp, requirements, memoperand->ilp, 1.0); - lpp_set_factor_fast(si->lpp, one_memoperand, memoperand->ilp, 1.0); + lpp_set_factor_fast(si->lpp, one_memoperand, memoperand->ilp, 1.0); - /* we have one more free register if we use a memory operand */ - lpp_set_factor_fast(si->lpp, check_pre, memoperand->ilp, -1.0); + /* we have one more free register if we use a memory operand */ + lpp_set_factor_fast(si->lpp, check_pre, memoperand->ilp, -1.0); + } } } -#endif } /* iterate over L\U */ @@ -2169,9 +2405,7 @@ skip_one_must_die: } } - /* requirements for remats */ - /* start new live ranges for values used by remats */ foreach_pre_remat(si, irn, tmp) { op_t *remat_op = get_irn_link(tmp); int n; @@ -2222,7 +2456,15 @@ skip_one_must_die: del_set(args); del_pset(defs); defs = pset_new_ptr_default(); + + /* skip everything above barrier in start block */ + if(is_start_block(bb) && be_is_Barrier(irn)) { + assert(pset_count(live) == 0); + break; + } + } + del_pset(defs); @@ -2239,7 +2481,6 @@ skip_one_must_die: } /* construct mem_outs for all values */ - set_foreach(spill_bb->ilp, spill) { ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", spill->irn, bb); cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); @@ -2248,20 +2489,18 @@ skip_one_must_die: lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0); if(pset_find_ptr(live, spill->irn)) { + int default_spilled; 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_default(si->lpp, buf, lpp_binary, 0.0, 1.0); + default_spilled = be_is_live_in(si->lv, bb, spill->irn) || is_Phi(spill->irn); + spill->mem_in = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, default_spilled); lpp_set_factor_fast(si->lpp, cst, spill->mem_in, -1.0); - if(is_Phi(spill->irn) && get_nodes_block(spill->irn) == bb) { + if(opt_memcopies && 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; @@ -2283,7 +2522,7 @@ skip_one_must_die: /* copies are not for free */ ir_snprintf(buf, sizeof(buf), "copy_%N_%N", arg, spill->irn); - var = lpp_add_var_default(si->lpp, buf, lpp_binary, COST_STORE * freq, 1.0); + var = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_spill * freq, 1.0); for(m=n; m>=0; --m) { const ir_node *arg2 = get_irn_n(spill->irn, m); @@ -2293,16 +2532,77 @@ skip_one_must_die: } } +#if 0 /* copy <= mem_in */ ir_snprintf(buf, sizeof(buf), "nocopy_%N_%N", arg, spill->irn); cst = lpp_add_cst_uniq(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); +#endif } } } } + foreach_post_remat(bb, tmp) { + int n; + op_t *remat_op = get_irn_link(tmp); + pset *remat_args = pset_new_ptr(get_irn_arity(tmp)); + ir_node *remat_arg; + + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + remat_arg = get_irn_n(tmp, n); + + if(has_reg_class(si, remat_arg)) { + pset_insert_ptr(remat_args, remat_arg); + } + } + + /* remat + \sum live_range(remat_arg) <= |args| */ + ir_snprintf(buf, sizeof(buf), "one_must_die_%N", tmp); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, pset_count(remat_args)); + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + + pset_foreach(remat_args, remat_arg) { + if(pset_find_ptr(live, remat_arg)) { + op_t *remat_arg_op = get_irn_link(remat_arg); + lpp_set_factor_fast(si->lpp, cst, remat_arg_op->attr.live_range.ilp, 1.0); + } + } + del_pset(remat_args); + } + + foreach_post_remat(bb, tmp) { + int n; + + for(n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(tmp, n); + + /* if value is becoming live through use by remat2 */ + if(has_reg_class(si, remat_arg) && !pset_find_ptr(live, remat_arg)) { + op_t *remat_arg_op = get_irn_link(remat_arg); + ilp_cst_t nomem; + + DBG((si->dbg, LEVEL_3, " value %+F becoming live through use by remat2 at bb start %+F\n", remat_arg, tmp)); + + pset_insert_ptr(live, remat_arg); + spill = add_to_spill_bb(si, bb, remat_arg); + remat_arg_op->attr.live_range.ilp = ILP_UNDEF; + + /* we need reg_in and mem_in for this value; they will be referenced later */ + ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N", remat_arg, bb); + spill->reg_in = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0); + ir_snprintf(buf, sizeof(buf), "mem_in_%N_%N", remat_arg, bb); + spill->mem_in = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); + + + /* optimization: all memory stuff should be 0, for we do not want to insert reloads for remats */ + ir_snprintf(buf, sizeof(buf), "nomem_%N_%N", remat_arg, bb); + nomem = lpp_add_cst_uniq(si->lpp, buf, lpp_equal, 0.0); + lpp_set_factor_fast(si->lpp, nomem, spill->spill, 1.0); + } + } + } /* L\U is empty at bb start */ /* arg is live throughout epilog if it is reg_in into this block */ @@ -2310,6 +2610,8 @@ skip_one_must_die: /* check the register pressure at the beginning of the block * including remats */ + /* reg_in entspricht post_use */ + ir_snprintf(buf, sizeof(buf), "check_start_%N", bb); cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, si->n_regs); @@ -2320,7 +2622,7 @@ skip_one_must_die: assert(spill); ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N", irn, bb); - spill->reg_in = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); + spill->reg_in = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0); lpp_set_factor_fast(si->lpp, cst, spill->reg_in, 1.0); @@ -2331,36 +2633,8 @@ skip_one_must_die: lpp_set_factor_fast(si->lpp, nospill, spill->mem_in, 1.0); lpp_set_factor_fast(si->lpp, nospill, spill->spill, 1.0); - } - foreach_post_remat(bb, irn) { - op_t *remat_op = get_irn_link(irn); - - DBG((si->dbg, LEVEL_4, "\t next post remat: %+F\n", irn)); - assert(remat_op->is_remat && !remat_op->attr.remat.pre); - - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); - } - - /* forall post remats add requirements */ - foreach_post_remat(bb, tmp) { - int n; - - for (n=get_irn_arity(tmp)-1; n>=0; --n) { - ir_node *remat_arg = get_irn_n(tmp, n); - op_t *remat_op = get_irn_link(tmp); - - if(!has_reg_class(si, remat_arg)) continue; - - spill = set_find_spill(spill_bb->ilp, remat_arg); - assert(spill); - - /* remat <= reg_in_argument */ - ir_snprintf(buf, sizeof(buf), "req_remat2_%N_%N_arg_%N", tmp, bb, remat_arg); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0); - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); - } - } + } /* post_remats are NOT included in register pressure check because + they do not increase regpressure */ /* mem_in/reg_in for live_in values, especially phis and their arguments */ pset_foreach(live, irn) { @@ -2400,7 +2674,9 @@ skip_one_must_die: assert(spill_p); lpp_set_factor_fast(si->lpp, mem_in, spill_p->mem_out, -1.0); - lpp_set_factor_fast(si->lpp, mem_in, op->attr.live_range.args.copies[n], -1.0); + if(opt_memcopies) + lpp_set_factor_fast(si->lpp, mem_in, op->attr.live_range.args.copies[n], -1.0); + lpp_set_factor_fast(si->lpp, reg_in, spill_p->reg_out, -1.0); } } @@ -2431,36 +2707,91 @@ skip_one_must_die: } } + foreach_post_remat(bb, tmp) { + int n; + + for (n=get_irn_arity(tmp)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(tmp, n); + op_t *remat_op = get_irn_link(tmp); + + if(!has_reg_class(si, remat_arg)) continue; + + spill = set_find_spill(spill_bb->ilp, remat_arg); + assert(spill); + + 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); + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + } + } + + pset_foreach(live, irn) { + const op_t *op = get_irn_link(irn); + const ir_node *remat; + int n_remats = 0; + + cst = ILP_UNDEF; + + foreach_post_remat(bb, remat) { + int n; + + for (n=get_irn_arity(remat)-1; n>=0; --n) { + const ir_node *arg = get_irn_n(remat, n); + + if(arg == irn) { + const op_t *remat_op = get_irn_link(remat); + + if(cst == ILP_UNDEF) { + /* sum remat2s <= 1 + n_remats*live_range */ + ir_snprintf(buf, sizeof(buf), "dying_lr_%N_%N", irn, bb); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); + } + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + ++n_remats; + break; + } + } + } + if(cst != ILP_UNDEF && op->attr.live_range.ilp != ILP_UNDEF) { + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -n_remats); + } + } + /* first live ranges from reg_ins */ pset_foreach(live, irn) { op_t *op = get_irn_link(irn); - spill = set_find_spill(spill_bb->ilp, irn); - assert(spill && spill->irn == irn); + if(op->attr.live_range.ilp != ILP_UNDEF) { - ir_snprintf(buf, sizeof(buf), "first_lr_%N_%N", irn, bb); - cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, 1.0); - lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0); + spill = set_find_spill(spill_bb->ilp, irn); + assert(spill && spill->irn == irn); - foreach_post_remat(bb, tmp) { - op_t *remat_op = get_irn_link(tmp); + ir_snprintf(buf, sizeof(buf), "first_lr_%N_%N", irn, bb); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, 1.0); + lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0); - if(remat_op->attr.remat.remat->value == irn) { - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0); + foreach_post_remat(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); + } } } } /* walk forward now and compute constraints for placing spills */ /* this must only be done for values that are not defined in this block */ - /* TODO are these values at start of block? if yes, just check whether this is a diverge edge and skip the loop */ pset_foreach(live, irn) { /* * if value is defined in this block we can anways place the spill directly after the def * -> no constraint necessary */ - if(!is_Phi(irn) && get_nodes_block(irn) == bb) continue; + if(!is_Phi(irn) && get_nodes_block(irn) == bb) { + assert(0); + } spill = set_find_spill(spill_bb->ilp, irn); @@ -2593,6 +2924,7 @@ values_interfere_in_block(const spill_ilp_t * si, const ir_node * bb, const ir_n if(get_nodes_block(user) == bb && !is_Phi(user) && b != user + && !pset_find_ptr(si->inverse_ops, user) && value_dominates(b, user)) return 1; } @@ -2616,7 +2948,7 @@ luke_interferencewalker(ir_node * bb, void * data) /* 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)) { - if(a_op->is_remat) + if(a_op->is_remat || pset_find_ptr(si->inverse_ops, a)) continue; for(l2=_be_lv_next_irn(si->lv, bb, 0xff, l1+1); l2>=0; l2=_be_lv_next_irn(si->lv, bb, 0xff, l2+1)) { @@ -2626,7 +2958,7 @@ luke_interferencewalker(ir_node * bb, void * data) /* 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(b_op->is_remat) + if(b_op->is_remat || pset_find_ptr(si->inverse_ops, b)) continue; if(values_interfere_in_block(si, bb, a, b)) { @@ -2704,7 +3036,7 @@ find_copy_path(spill_ilp_t * si, const ir_node * irn, const ir_node * target, il paths += find_copy_path(si, arg, target, any_interfere, copies, visited); pset_remove(copies, INT_TO_PTR(copy), copy); - /*if(paths > MAX_PATHS) { + if(paths > MAX_PATHS) { if(pset_count(copies) == 0) { ilp_cst_t cst; char buf[256]; @@ -2724,7 +3056,7 @@ find_copy_path(spill_ilp_t * si, const ir_node * irn, const ir_node * target, il } } else if(pset_count(copies) == 0) { paths = 0; - }*/ + } } } @@ -2759,7 +3091,7 @@ find_copy_path(spill_ilp_t * si, const ir_node * irn, const ir_node * target, il paths += find_copy_path(si, user, target, any_interfere, copies, visited); pset_remove(copies, INT_TO_PTR(copy), copy); - /*if(paths > MAX_PATHS) { + if(paths > MAX_PATHS) { if(pset_count(copies) == 0) { ilp_cst_t cst; char buf[256]; @@ -2778,7 +3110,7 @@ find_copy_path(spill_ilp_t * si, const ir_node * irn, const ir_node * target, il } } else if(pset_count(copies) == 0) { paths = 0; - }*/ + } } } @@ -2896,7 +3228,6 @@ is_zero(double x) return fabs(x) < 0.00001; } -#ifdef KEEPALIVE static int mark_remat_nodes_hook(FILE *F, ir_node *n, ir_node *l) { spill_ilp_t *si = get_irg_link(current_ir_graph); @@ -2937,7 +3268,6 @@ dump_graph_with_remats(ir_graph * irg, const char * suffix) be_dump(irg, suffix, dump_ir_block_graph_sched); set_dump_node_vcgattr_hook(NULL); } -#endif /** * Edge hook to dump the schedule edges with annotated register pressure. @@ -3017,7 +3347,6 @@ dump_pressure_graph(spill_ilp_t * si, const char *suffix) be_dump(si->chordal_env->irg, suffix, dump_ir_block_graph_sched_pressure); } -#ifdef KEEPALIVE static void connect_all_remats_with_keep(spill_ilp_t * si) { @@ -3042,7 +3371,6 @@ connect_all_remats_with_keep(spill_ilp_t * si) obstack_free(si->obst, ins); } } -#endif static void connect_all_spills_with_keep(spill_ilp_t * si) @@ -3133,11 +3461,17 @@ clean_remat_info(spill_ilp_t * si) pset_foreach(remat_info->remats, remat) { if(remat->proj && get_irn_n_edges(remat->proj) == 0) { + if(sched_is_scheduled(remat->proj)) { + sched_remove((ir_node*)remat->proj); + } set_irn_n((ir_node*)remat->proj, -1, bad); set_irn_n((ir_node*)remat->proj, 0, bad); } if(get_irn_n_edges(remat->op) == 0) { + if(sched_is_scheduled(remat->op)) { + sched_remove((ir_node*)remat->op); + } for (n=get_irn_arity(remat->op)-1; n>=-1; --n) { set_irn_n((ir_node*)remat->op, n, bad); } @@ -3152,88 +3486,73 @@ clean_remat_info(spill_ilp_t * si) static void delete_unnecessary_remats(spill_ilp_t * si) { -#ifdef KEEPALIVE - 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; + if(opt_keep_alive & KEEPALIVE_REMATS) { + int n; + ir_node *bad = get_irg_bad(si->chordal_env->irg); - 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; + if(si->keep) { + 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; - assert(arg_op->is_remat); + assert(arg_op->is_remat); - name = si->lpp->vars[arg_op->attr.remat.ilp]; + name = si->lpp->vars[arg_op->attr.remat.ilp]; - if(is_zero(name->value)) { - DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", keep_arg)); - /* TODO check whether reload is preferred over remat (could be bug) */ - delete_remat(si, keep_arg); - } else { - if(!arg_op->attr.remat.remat->inverse) { - if(arg_op->attr.remat.pre) { - DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", keep_arg)); - } else { - DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", keep_arg)); - } + if(is_zero(name->value)) { + DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", keep_arg)); + /* TODO check whether reload is preferred over remat (could be bug) */ + delete_remat(si, keep_arg); } else { - if(arg_op->attr.remat.pre) { - DBG((si->dbg, LEVEL_2, "\t**INVERSE remat kept: %+F\n", keep_arg)); + if(!arg_op->attr.remat.remat->inverse) { + if(arg_op->attr.remat.pre) { + DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", keep_arg)); + } else { + DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", keep_arg)); + } } else { - DBG((si->dbg, LEVEL_2, "\t%%%%INVERSE remat2 kept: %+F\n", keep_arg)); + if(arg_op->attr.remat.pre) { + DBG((si->dbg, LEVEL_2, "\t**INVERSE remat kept: %+F\n", keep_arg)); + } else { + DBG((si->dbg, LEVEL_2, "\t%%%%INVERSE remat2 kept: %+F\n", keep_arg)); + } } } - } - set_irn_n(si->keep, n, bad); - } -#if 0 - for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) { - ir_node *end_arg = get_End_keepalive(end, i); - - if(end_arg != si->keep) { - obstack_grow(si->obst, &end_arg, sizeof(end_arg)); + set_irn_n(si->keep, n, bad); } + } else { + DBG((si->dbg, LEVEL_2, "\t no remats to delete (none have been inserted)\n")); } - keeps = obstack_finish(si->obst); - set_End_keepalives(end, n-1, keeps); - obstack_free(si->obst, keeps); -#endif } else { - DBG((si->dbg, LEVEL_2, "\t no remats to delete (none have been inserted)\n")); - } -#else - ir_node *remat; + 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)); - } + 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.pre) { - DBG((si->dbg, LEVEL_2, "\t**INVERSE remat kept: %+F\n", remat)); + 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 { - DBG((si->dbg, LEVEL_2, "\t%%%%INVERSE remat2 kept: %+F\n", remat)); + 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 * @@ -3255,10 +3574,22 @@ get_spills_for_value(spill_ilp_t * si, const ir_node * value) return spills; } +static ir_node * +new_r_PhiM_nokeep(ir_graph * irg, ir_node *block, int arity, ir_node **in) +{ + ir_node *res; + + assert( get_irn_arity(block) == arity ); + + res = new_ir_node(NULL, irg, block, op_Phi, mode_M, arity, in); + res->attr.phi_backedge = new_backedge_arr(irg->obst, arity); + + return res; +} + /** * @param before The node after which the spill will be placed in the schedule */ -/* TODO set context properly */ static ir_node * insert_spill(spill_ilp_t * si, ir_node * irn, const ir_node * value, ir_node * before) { @@ -3277,9 +3608,8 @@ insert_spill(spill_ilp_t * si, ir_node * irn, const ir_node * value, ir_node * b set_irn_link(spill, defs->spills); defs->spills = spill; -#ifdef KEEPALIVE_SPILLS - pset_insert_ptr(si->spills, spill); -#endif + if(opt_keep_alive & KEEPALIVE_SPILLS) + pset_insert_ptr(si->spills, spill); return spill; } @@ -3301,7 +3631,7 @@ insert_mem_phi(spill_ilp_t * si, ir_node * phi) ins[n] = si->m_unknown; } - mem_phi = new_r_Phi(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins, mode_M); + mem_phi = new_r_PhiM_nokeep(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins); defs = set_insert_def(si->values, phi); assert(defs); @@ -3310,12 +3640,15 @@ insert_mem_phi(spill_ilp_t * si, ir_node * phi) set_irn_link(mem_phi, defs->spills); defs->spills = mem_phi; +#ifdef SCHEDULE_PHIM sched_add_after(phi, mem_phi); - -#ifdef KEEPALIVE_SPILLS - pset_insert_ptr(si->spills, mem_phi); +#else + pset_insert_ptr(si->phims, mem_phi); #endif + if(opt_keep_alive & KEEPALIVE_SPILLS) + pset_insert_ptr(si->spills, mem_phi); + return mem_phi; } @@ -3367,11 +3700,9 @@ insert_reload(spill_ilp_t * si, const ir_node * value, ir_node * after) return reload; } -#ifdef WITH_MEMOPERANDS void perform_memory_operand(spill_ilp_t * si, memoperand_t * memoperand) { defs_t *defs; - ir_node *reload; ir_node *value = get_irn_n(memoperand->irn, memoperand->pos); ir_node *spill; const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; @@ -3383,10 +3714,7 @@ void perform_memory_operand(spill_ilp_t * si, memoperand_t * memoperand) spill = defs->spills; assert(spill && "no spill placed before reload"); - reload = be_reload(arch_env, si->cls, memoperand->irn, get_irn_mode(value), spill); - - arch_perform_memory_operand(arch_env, memoperand->irn, reload, memoperand->pos); - sched_remove(reload); + arch_perform_memory_operand(arch_env, memoperand->irn, spill, memoperand->pos); } void insert_memoperands(spill_ilp_t * si) @@ -3401,7 +3729,6 @@ void insert_memoperands(spill_ilp_t * si) } } } -#endif static void walker_spill_placer(ir_node * bb, void * data) { @@ -3542,18 +3869,19 @@ phim_fixer(spill_ilp_t *si) { ir_node *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(opt_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); + if(!is_zero(name->value)) { + spill = insert_mem_copy(si, pred, value); + } else { + spill = val_defs->spills; + } } else { spill = val_defs->spills; } -#else - spill = val_defs->spills; -#endif + assert(spill && "no spill placed before PhiM"); set_irn_n(phi_m, n, spill); } @@ -3603,9 +3931,8 @@ walker_reload_placer(ir_node * bb, void * data) { reload = insert_reload(si, irn, insert_pos); -#ifdef KEEPALIVE_RELOADS - pset_insert_ptr(si->spills, reload); -#endif + if(opt_keep_alive & KEEPALIVE_RELOADS) + pset_insert_ptr(si->spills, reload); } } } @@ -3658,11 +3985,11 @@ walker_reload_placer(ir_node * bb, void * data) { reload = insert_reload(si, arg, insert_pos); + assert(reload && "no reload returned"); set_irn_n(irn, n, reload); -#ifdef KEEPALIVE_RELOADS - pset_insert_ptr(si->spills, reload); -#endif + if(opt_keep_alive & KEEPALIVE_RELOADS) + pset_insert_ptr(si->spills, reload); } } } @@ -3676,13 +4003,13 @@ walker_reload_placer(ir_node * bb, void * data) { static void walker_collect_used(ir_node * irn, void * data) { - lc_bitset_t *used = data; + bitset_t *used = data; - lc_bitset_set(used, get_irn_idx(irn)); + bitset_set(used, get_irn_idx(irn)); } struct kill_helper { - lc_bitset_t *used; + bitset_t *used; spill_ilp_t *si; }; @@ -3698,7 +4025,7 @@ walker_kill_unused(ir_node * bb, void * data) ir_node *next = sched_next(irn); int n; - if(!lc_bitset_is_set(kh->used, get_irn_idx(irn))) { + if(!bitset_is_set(kh->used, get_irn_idx(irn))) { if(be_is_Spill(irn) || be_is_Reload(irn)) { DBG((kh->si->dbg, LEVEL_1, "\t SUBOPTIMAL! %+F IS UNUSED (cost: %g)\n", irn, get_cost(kh->si, irn)*execution_frequency(kh->si, bb))); #if 0 @@ -3717,18 +4044,41 @@ walker_kill_unused(ir_node * bb, void * data) } } +#ifndef SCHEDULE_PHIM +static void +kill_unused_phims(spill_ilp_t * si, struct kill_helper * kh) +{ + ir_node *phi; + ir_node *bad = get_irg_bad(si->chordal_env->irg); + int n; + + pset_foreach(si->phims, phi) { + if(!bitset_is_set(kh->used, get_irn_idx(phi))) { + + set_nodes_block(phi, bad); + for (n=get_irn_arity(phi)-1; n>=0; --n) { + set_irn_n(phi, n, bad); + } + } + } +} +#endif + static void kill_all_unused_values_in_schedule(spill_ilp_t * si) { - struct kill_helper kh; + struct kill_helper kh; - kh.used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); + kh.used = bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); kh.si = si; irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, kh.used); +#ifndef SCHEDULE_PHIM + kill_unused_phims(si, &kh); +#endif irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh); - lc_bitset_free(kh.used); + bitset_free(kh.used); } void @@ -3827,20 +4177,22 @@ rewire_uses(spill_ilp_t * si) set_foreach(si->values, defs) { pset *nodes; const ir_node *next = defs->remats; + int orig_kept = 0; if(next) { nodes = pset_new_ptr_default(); - pset_insert_ptr(nodes, defs->value); + if(sched_is_scheduled(defs->value)) { + pset_insert_ptr(nodes, defs->value); + orig_kept = 1; + } while(next) { pset_insert_ptr(nodes, next); next = get_irn_link(next); } - if(pset_count(nodes) > 1) { - DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-1, defs->value)); - be_ssa_constr_set(dfi, si->lv, nodes); - } + DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-orig_kept, defs->value)); + be_ssa_constr_set(dfi, si->lv, nodes); del_pset(nodes); } @@ -3864,9 +4216,8 @@ writeback_results(spill_ilp_t * 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); irg_block_walk_graph(si->chordal_env->irg, walker_reload_placer, NULL, si); -#ifdef WITH_MEMOPERANDS - insert_memoperands(si); -#endif + if(opt_memoperands) + insert_memoperands(si); phim_fixer(si); /* clean the remat info! there are still back-edges leading there! */ @@ -3882,18 +4233,22 @@ writeback_results(spill_ilp_t * si) static int get_n_regs(spill_ilp_t * si) { - int arch_n_regs = arch_register_class_n_regs(si->cls); - int free = 0; - int i; + int arch_n_regs = arch_register_class_n_regs(si->cls); - for(i=0; icls->regs[i], ignore)) { - free++; - } - } + bitset_t *arch_regs = bitset_malloc(arch_n_regs); + bitset_t *abi_regs = bitset_malloc(arch_n_regs); + + arch_put_non_ignore_regs(si->chordal_env->birg->main_env->arch_env, si->cls, arch_regs); + be_abi_put_ignore_regs(si->chordal_env->birg->abi, si->cls, abi_regs); + + bitset_andnot(arch_regs, abi_regs); + arch_n_regs = bitset_popcnt(arch_regs); - DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", free, si->cls->name)); - return free; + bitset_free(arch_regs); + bitset_free(abi_regs); + + DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", arch_n_regs, si->cls->name)); + return arch_n_regs; } static void @@ -3987,36 +4342,10 @@ verify_phiclasses(spill_ilp_t * si) irg_block_walk_graph(si->chordal_env->irg, luke_meminterferencechecker, NULL, si); } -static void -walker_spillslotassigner(ir_node * irn, void * data) -{ - void *cls; - - if(!be_is_Spill(irn)) return; - - /* set spill context to phi class if it has one ;) */ - (void) cls; -#if 0 - // Matze: not needed anymore - cls = get_phi_class(irn); - if(cls) - be_set_Spill_context(irn, cls); - else - be_set_Spill_context(irn, irn); -#endif -} - - -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 buf[256]; char problem_name[256]; char dump_suffix[256]; char dump_suffix2[256]; @@ -4030,9 +4359,8 @@ be_spill_remat(const be_chordal_env_t * chordal_env) 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 + if(opt_verify & VERIFY_DOMINANCE) + be_check_dominance(chordal_env->irg); obstack_init(&obst); si.chordal_env = chordal_env; @@ -4041,16 +4369,12 @@ be_spill_remat(const be_chordal_env_t * chordal_env) si.lpp = new_lpp(problem_name, lpp_minimize); si.remat_info = new_set(cmp_remat_info, 4096); si.interferences = new_set(cmp_interference, 32); -#ifdef WITH_MEMOPERANDS si.memoperands = new_set(cmp_memoperands, 128); -#endif si.all_possible_remats = pset_new_ptr_default(); si.spills = pset_new_ptr_default(); si.inverse_ops = pset_new_ptr_default(); si.lv = chordal_env->lv; -#ifdef KEEPALIVE si.keep = NULL; -#endif si.n_regs = get_n_regs(&si); set_irg_link(chordal_env->irg, &si); @@ -4059,25 +4383,29 @@ be_spill_remat(const be_chordal_env_t * chordal_env) /* compute phi classes */ // phi_class_compute(chordal_env->irg); - be_analyze_regpressure(chordal_env, "-pre"); + if(opt_dump_flags & DUMP_STATS) + be_analyze_regpressure(chordal_env, "-pre"); -#ifdef COLLECT_REMATS - /* collect remats */ - DBG((si.dbg, LEVEL_1, "Collecting remats\n")); - irg_walk_graph(chordal_env->irg, walker_remat_collector, NULL, &si); -#endif + DBG((si.dbg, LEVEL_2, "\t initializing\n")); + irg_block_walk_graph(chordal_env->irg, luke_initializer, NULL, &si); + + if(opt_remats) { + /* collect remats */ + DBG((si.dbg, LEVEL_1, "Collecting remats\n")); + irg_walk_graph(chordal_env->irg, walker_remat_collector, NULL, &si); + } /* insert possible remats */ DBG((si.dbg, LEVEL_1, "Inserting possible remats\n")); irg_block_walk_graph(chordal_env->irg, walker_remat_insertor, NULL, &si); DBG((si.dbg, LEVEL_2, " -> inserted %d possible remats\n", pset_count(si.all_possible_remats))); -#ifdef KEEPALIVE - DBG((si.dbg, LEVEL_1, "Connecting remats with keep and dumping\n")); - connect_all_remats_with_keep(&si); - /* dump graph with inserted remats */ - dump_graph_with_remats(chordal_env->irg, dump_suffix); -#endif + if(opt_keep_alive & KEEPALIVE_REMATS) { + DBG((si.dbg, LEVEL_1, "Connecting remats with keep and dumping\n")); + connect_all_remats_with_keep(&si); + /* dump graph with inserted remats */ + dump_graph_with_remats(chordal_env->irg, dump_suffix); + } /* insert copies for phi arguments not in my regclass */ irg_walk_graph(chordal_env->irg, walker_regclass_copy_insertor, NULL, &si); @@ -4087,7 +4415,6 @@ be_spill_remat(const be_chordal_env_t * chordal_env) be_liveness_recompute(si.lv); /* build the ILP */ - DBG((si.dbg, LEVEL_1, "\tBuilding ILP\n")); DBG((si.dbg, LEVEL_2, "\t endwalker\n")); irg_block_walk_graph(chordal_env->irg, luke_endwalker, NULL, &si); @@ -4095,31 +4422,44 @@ 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 + if(opt_memcopies) { + DBG((si.dbg, LEVEL_2, "\t memcopyhandler\n")); + memcopyhandler(&si); + } -#ifdef DUMP_ILP - { + if(opt_dump_flags & DUMP_PROBLEM) { FILE *f; - char buf[256]; - ir_snprintf(buf, sizeof(buf), "%s-spillremat.ilp", problem_name); if ((f = fopen(buf, "wt")) != NULL) { lpp_dump_plain(si.lpp, f); fclose(f); } } -#endif + + if(opt_dump_flags & DUMP_MPS) { + FILE *f; + + ir_snprintf(buf, sizeof(buf), "%s-spillremat.mps", problem_name); + if((f = fopen(buf, "wt")) != NULL) { + mps_write_mps(si.lpp, s_mps_fixed, f); + fclose(f); + } + + ir_snprintf(buf, sizeof(buf), "%s-spillremat.mst", problem_name); + if((f = fopen(buf, "wt")) != NULL) { + mps_write_mst(si.lpp, s_mps_fixed, f); + fclose(f); + } + } + + lpp_check_startvals(si.lpp); #ifdef SOLVE DBG((si.dbg, LEVEL_1, "\tSolving %s (%d variables, %d constraints)\n", problem_name, si.lpp->var_next, si.lpp->cst_next)); -#ifdef ILP_TIMEOUT - lpp_set_time_limit(si.lpp, ILP_TIMEOUT); -#endif + lpp_set_time_limit(si.lpp, opt_timeout); - lpp_set_log(si.lpp, stdout); + if(opt_log) + lpp_set_log(si.lpp, stdout); #ifdef SOLVE_LOCAL lpp_solve_cplex(si.lpp); @@ -4129,10 +4469,9 @@ be_spill_remat(const be_chordal_env_t * chordal_env) assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid"); - DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval)); + DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g, best bound: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval, is_zero(si.lpp->best_bound)?0.0:si.lpp->best_bound)); -#ifdef DUMP_SOLUTION - { + if(opt_dump_flags & DUMP_SOLUTION) { FILE *f; char buf[256]; @@ -4146,45 +4485,49 @@ be_spill_remat(const be_chordal_env_t * chordal_env) fclose(f); } } -#endif +#ifndef SCHEDULE_PHIM + si.phims = pset_new_ptr_default(); +#endif writeback_results(&si); + #endif /* SOLVE */ kill_all_unused_values_in_schedule(&si); -#if defined(KEEPALIVE_SPILLS) || defined(KEEPALIVE_RELOADS) - be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph); +#if !defined(SCHEDULE_PHIM) && defined(SOLVE) + del_pset(si.phims); #endif + if(opt_keep_alive & (KEEPALIVE_SPILLS | KEEPALIVE_RELOADS)) + be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph); + // move reloads upwards be_liveness_recompute(si.lv); irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si); move_reloads_upward(&si); -#ifndef NO_MEMCOPIES - verify_phiclasses(&si); - assign_spillslots(&si); -#endif + if(opt_memcopies) { + verify_phiclasses(&si); + } irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si); - dump_pressure_graph(&si, dump_suffix2); + if(opt_dump_flags & DUMP_PRESSURE) + dump_pressure_graph(&si, dump_suffix2); - be_analyze_regpressure(chordal_env, "-post"); + if(opt_dump_flags & DUMP_STATS) + be_analyze_regpressure(chordal_env, "-post"); -#ifdef VERIFY_DOMINANCE - be_check_dominance(chordal_env->irg); -#endif + if(opt_verify & VERIFY_DOMINANCE) + be_check_dominance(chordal_env->irg); free_dom(chordal_env->irg); del_set(si.interferences); del_pset(si.inverse_ops); del_pset(si.all_possible_remats); -#ifdef WITH_MEMOPERANDS del_set(si.memoperands); -#endif del_pset(si.spills); free_lpp(si.lpp); obstack_free(&obst, NULL);