X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=180d0c56f75fc069259ab93e5cb102fdde484ff7;hb=1a17ce1b27aa55ac4037e2317a9d017fe6fa45c3;hp=1fa28c9ae26fa3f01c86f6cbcbb161190125e283;hpb=a639804a0d4b5af1db69fe60ce2e608572ecb017;p=libfirm diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c index 1fa28c9ae..180d0c56f 100644 --- a/ir/be/bespillremat.c +++ b/ir/be/bespillremat.c @@ -39,18 +39,20 @@ #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" @@ -62,6 +64,8 @@ #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 @@ -85,11 +89,10 @@ 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_spill = 30.0; static double opt_cost_remat = 1.0; @@ -98,6 +101,8 @@ 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 } }; @@ -137,9 +142,8 @@ static const lc_opt_table_entry_t options[] = { LC_OPT_ENT_ENUM_INT ("remats", "type of remats to insert (none, briggs, noinverse or all)",&remats_var), LC_OPT_ENT_BOOL ("repair_schedule", "repair the schedule by rematting once used nodes",&opt_repair_schedule), LC_OPT_ENT_BOOL ("no_enlage_liveness", "do not enlarge liveness of operands of remats",&opt_no_enlarge_liveness), - LC_OPT_ENT_BOOL ("remat_while_live", "remat only values that can be used by real ops", &opt_remat_while_live), - LC_OPT_ENT_ENUM_MASK("dump", "dump problem, mps or solution", &dump_var), + LC_OPT_ENT_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), @@ -416,6 +420,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 @@ -486,11 +493,11 @@ get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * 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; @@ -602,8 +609,8 @@ get_irn_n_nonignore_args(const spill_ilp_t * si, const ir_node * irn) int n; int ret = 0; -// if(is_Proj(irn)) -// irn = get_Proj_pred(irn); + if(is_Proj(irn)) + irn = get_Proj_pred(irn); for(n=get_irn_arity(irn)-1; n>=0; --n) { const ir_node *arg = get_irn_n(irn, n); @@ -976,17 +983,6 @@ is_start_block(const ir_node * bb) return get_irg_start_block(get_irn_irg(bb)) == bb; } -static int -is_before_frame(const ir_node * bb, const ir_node * irn) -{ - const ir_node *frame = get_irg_frame(get_irn_irg(bb)); - - if(is_start_block(bb) && sched_get_time_step(frame) >= sched_get_time_step(irn)) - return 1; - else - return 0; -} - static int is_merge_edge(const ir_node * bb) { @@ -1011,6 +1007,38 @@ is_diverge_edge(const ir_node * bb) return 1; } +static void +get_live_end(spill_ilp_t * si, ir_node * bb, pset * live) +{ + ir_node *irn; + int i; + + be_lv_foreach(si->lv, bb, be_lv_state_end, i) { + irn = be_lv_get_irn(si->lv, bb, i); + + if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) { + pset_insert_ptr(live, irn); + } + } + + irn = sched_last(bb); + + /* all values eaten by control flow operations are also live until the end of the block */ + sched_foreach_reverse(bb, irn) { + int i; + + if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break; + + for(i=get_irn_arity(irn)-1; i>=0; --i) { + ir_node *arg = get_irn_n(irn,i); + + if(has_reg_class(si, arg)) { + pset_insert_ptr(live, arg); + } + } + } +} + static void walker_regclass_copy_insertor(ir_node * irn, void * data) { @@ -1041,7 +1069,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 @@ -1050,13 +1077,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); @@ -1066,76 +1098,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; @@ -1153,41 +1154,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)); - if(opt_remat_while_live) { - if(pset_find_ptr(live, remat->value)) { - remat_irn = insert_remat_before(si, remat, irn, live); - } - } else { - remat_irn = insert_remat_before(si, remat, irn, live); - } + remat_irn = insert_remat_before(si, remat, irn, live); + if(remat_irn) { for(n=get_irn_arity(remat_irn)-1; n>=0; --n) { ir_node *remat_arg = get_irn_n(remat_irn, n); - if(!has_reg_class(si, remat_arg)) continue; - - pset_insert_ptr(remat_args, remat_arg); + /* collect args of remats which are not args of op */ + if(has_reg_class(si, remat_arg) && !pset_find_ptr(args, remat_arg)) { + pset_insert_ptr(used, remat_arg); + } } } } } } - /* now we add remat args to op's args because they could also die at this op */ - pset_foreach(args,arg) { - if(pset_find_ptr(remat_args, arg)) { - pset_remove_ptr(remat_args, arg); - } - } - pset_foreach(remat_args,arg) { - pset_insert_ptr(args, arg); + /* do not place post remats after jumps */ + if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) { + del_pset(used); + del_pset(args); + break; } /* insert all possible remats after irn */ - pset_foreach(args, arg) { + post_remats = pset_new_ptr_default(); + pset_foreach(used, arg) { remat_info_t *remat_info, query; - remat_t *remat; /* continue if the operand has the wrong reg class */ if(!has_reg_class(si, arg)) @@ -1202,27 +1196,26 @@ 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)); - if(opt_remat_while_live) { - if(pset_find_ptr(live, remat->value)) { - insert_remat_after(si, remat, irn, live); - } - } else { - insert_remat_after(si, remat, irn, live); + + /* only remat values that can be used be real ops */ + if(pset_find_ptr(live, remat->value)) { + pset_insert_ptr(post_remats, remat); } } } } } + pset_foreach(post_remats, remat) { + insert_remat_after(si, remat, irn, live); + } + del_pset(post_remats); - del_pset(remat_args); + del_pset(used); del_pset(args); irn = next; } @@ -1232,19 +1225,12 @@ walker_remat_insertor(ir_node * bb, void * data) pset *live_out = pset_new_ptr_default(); ir_node *value; - be_lv_foreach(si->lv, bb, be_lv_state_end, i) { - value = be_lv_get_irn(si->lv, bb, i); - - if (be_is_live_end(si->lv, bb, value) && has_reg_class(si, value)) { - pset_insert_ptr(live_out, value); - } - } + get_live_end(si, bb, live_out); /* add remats at end of block */ pset_foreach(live_out, value) { remat_info_t *remat_info, query; - remat_t *remat; query.irn = value; query.remats = NULL; @@ -1269,38 +1255,108 @@ walker_remat_insertor(ir_node * bb, void * data) be_lv_foreach(si->lv, bb, be_lv_state_in, i) { value = be_lv_get_irn(si->lv, bb, i); - if (has_reg_class(si, value)) { + if(has_reg_class(si, value)) { + pset_insert_ptr(live_in, value); + } + } + /* add phis to live_in */ + sched_foreach(bb, value) { + if(!is_Phi(value)) break; + + if(has_reg_class(si, value)) { pset_insert_ptr(live_in, value); } } /* add remat2s at beginning of block */ + post_remats = pset_new_ptr_default(); pset_foreach(live_in, value) { - if ((be_is_live_in(si->lv, bb, value) || (is_Phi(value) && get_nodes_block(value)==bb)) && has_reg_class(si, value)) { - remat_info_t *remat_info, - query; - remat_t *remat; - - query.irn = value; - query.remats = NULL; - query.remats_by_operand = NULL; - remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); + remat_info_t *remat_info, + query; - 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)); + query.irn = value; + query.remats = NULL; + query.remats_by_operand = NULL; + remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value)); - /* put the remat here if all its args are available */ - insert_remat_after(si, remat, bb, live_in); + 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(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) */ @@ -1316,18 +1372,13 @@ 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); } } @@ -1394,7 +1445,7 @@ luke_endwalker(ir_node * bb, void * data) ilp_cst_t rel_cst; ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn); - reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0); + reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), can_be_copied(bb, irn)); set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload)); /* reload <= mem_out */ @@ -1563,38 +1614,6 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) 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 */ @@ -1655,7 +1674,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); @@ -1712,7 +1730,6 @@ luke_blockwalker(ir_node * bb, void * data) pset *defs = pset_new_ptr_default(); const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; - live = pset_new_ptr_default(); /**************************************** @@ -1758,7 +1775,41 @@ 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); + } + } + } } if(opt_memcopies) @@ -1842,6 +1893,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 */ @@ -1861,30 +1913,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); + } } } } @@ -1922,7 +1976,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); } @@ -2076,7 +2129,7 @@ skip_one_must_die: /* new live range for each used value */ ir_snprintf(buf, sizeof(buf), "lr_%N_%N", arg, irn); - prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, is_before_frame(bb, irn)?1.0:0.0); + prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0); /* the epilog stuff - including post_use, check_post, check_post_remat */ ir_snprintf(buf, sizeof(buf), "post_use_%N_%N", arg, irn); @@ -2093,7 +2146,26 @@ 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); + } + /* forall post remat which use arg add a similar cst */ + foreach_post_remat(irn, remat) { + int n; + + for (n=get_irn_arity(remat)-1; n>=0; --n) { + ir_node *remat_arg = get_irn_n(remat, n); + op_t *remat_op = get_irn_link(remat); + + if(remat_arg == arg) { + DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn)); + + /* post_use >= remat */ + ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); + lpp_set_factor_fast(si->lpp, cst, post_use, -1.0); + lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); + } + } } /* if value is not an arg of op and not possibly defined by post remat @@ -2115,27 +2187,7 @@ skip_one_must_die: } } - - /* forall post remat which use arg add a similar cst */ - foreach_post_remat(irn, remat) { - int n; - - for (n=get_irn_arity(remat)-1; n>=0; --n) { - ir_node *remat_arg = get_irn_n(remat, n); - op_t *remat_op = get_irn_link(remat); - - if(remat_arg == arg) { - DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn)); - - ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++); - cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0); - lpp_set_factor_fast(si->lpp, cst, post_use, -1.0); - lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); - } - } - } - - if(opt_memoperands) { + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { for(n = get_irn_arity(irn)-1; n>=0; --n) { if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) { ilp_var_t memoperand; @@ -2149,8 +2201,6 @@ skip_one_must_die: 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); } } } @@ -2159,18 +2209,70 @@ skip_one_must_die: 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); + } + } /****************** @@ -2187,7 +2289,7 @@ skip_one_must_die: pset_remove_ptr(live, tmp); } - if(opt_memoperands) { + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { ir_snprintf(buf, sizeof(buf), "one_memoperand_%N", irn); one_memoperand = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); } @@ -2209,7 +2311,7 @@ skip_one_must_die: assert(spill); ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn); - op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), is_before_frame(bb, irn)?0.0:1.0); + op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0); /* reload <= mem_out */ ir_snprintf(buf, sizeof(buf), "req_reload_%N_%N", arg, irn); @@ -2231,7 +2333,7 @@ skip_one_must_die: } } - if(opt_memoperands) { + if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) { n_memoperands = 0; for(n = get_irn_arity(irn)-1; n>=0; --n) { if(get_irn_n(irn, n) == arg) { @@ -2271,9 +2373,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; @@ -2324,7 +2424,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); @@ -2341,7 +2449,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); @@ -2362,10 +2469,6 @@ skip_one_must_die: 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; @@ -2411,14 +2514,40 @@ skip_one_must_die: 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) { - ir_node *remat_arg = get_irn_n(tmp, n); + remat_arg = get_irn_n(tmp, n); - if(!has_reg_class(si, remat_arg)) continue; + 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(!pset_find_ptr(live, remat_arg)) { + if(has_reg_class(si, remat_arg) && !pset_find_ptr(live, remat_arg)) { op_t *remat_arg_op = get_irn_link(remat_arg); ilp_cst_t nomem; @@ -2438,16 +2567,7 @@ skip_one_must_die: /* optimization: all memory stuff should be 0, for we do not want to insert reloads for remats */ ir_snprintf(buf, sizeof(buf), "nomem_%N_%N", remat_arg, bb); nomem = lpp_add_cst_uniq(si->lpp, buf, lpp_equal, 0.0); - lpp_set_factor_fast(si->lpp, nomem, spill->spill, 1.0); - if(spill_bb->reloads) { - keyval_t *keyval = set_find_keyval(spill_bb->reloads, remat_arg); - - if(keyval) { - ilp_var_t reload = PTR_TO_INT(keyval->val); - lpp_set_factor_fast(si->lpp, nomem, reload, 1.0); - } - } } } } @@ -2567,7 +2687,6 @@ skip_one_must_die: 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); @@ -2580,8 +2699,6 @@ skip_one_must_die: const ir_node *remat; int n_remats = 0; - if(op->attr.live_range.ilp == ILP_UNDEF) continue; - cst = ILP_UNDEF; foreach_post_remat(bb, remat) { @@ -2594,9 +2711,9 @@ skip_one_must_die: const op_t *remat_op = get_irn_link(remat); if(cst == ILP_UNDEF) { - /* \sum post_remat <= 1 + #post_remats * next(lr) */ - ir_snprintf(buf, sizeof(buf), "remat2_%N_%N_arg_%N", remat, bb, irn); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 1.0); + /* sum remat2s <= 1 + n_remats*live_range */ + ir_snprintf(buf, sizeof(buf), "dying_lr_%N_%N", irn, bb); + cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0); } lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0); ++n_remats; @@ -2604,8 +2721,8 @@ skip_one_must_die: } } } - if(n_remats) { - lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, n_remats); + if(cst != ILP_UNDEF && op->attr.live_range.ilp != ILP_UNDEF) { + lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -n_remats); } } @@ -2635,13 +2752,14 @@ skip_one_must_die: /* 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); @@ -3311,11 +3429,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); } @@ -3335,9 +3459,6 @@ delete_unnecessary_remats(spill_ilp_t * si) ir_node *bad = get_irg_bad(si->chordal_env->irg); if(si->keep) { -// ir_node *end = get_irg_end(si->chordal_env->irg); -// ir_node **keeps; - for (n=get_irn_arity(si->keep)-1; n>=0; --n) { ir_node *keep_arg = get_irn_n(si->keep, n); op_t *arg_op = get_irn_link(keep_arg); @@ -3369,18 +3490,6 @@ delete_unnecessary_remats(spill_ilp_t * si) set_irn_n(si->keep, n, bad); } -#if 0 - for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) { - ir_node *end_arg = get_End_keepalive(end, i); - - if(end_arg != si->keep) { - obstack_grow(si->obst, &end_arg, sizeof(end_arg)); - } - } - keeps = obstack_finish(si->obst); - set_End_keepalives(end, n-1, keeps); - obstack_free(si->obst, keeps); -#endif } else { DBG((si->dbg, LEVEL_2, "\t no remats to delete (none have been inserted)\n")); } @@ -3547,7 +3656,6 @@ insert_reload(spill_ilp_t * si, const ir_node * value, ir_node * after) 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; @@ -3559,10 +3667,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) @@ -3850,13 +3955,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; }; @@ -3872,7 +3977,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 @@ -3896,13 +4001,13 @@ kill_all_unused_values_in_schedule(spill_ilp_t * si) { struct kill_helper kh; - kh.used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); + kh.used = bitset_malloc(get_irg_last_idx(si->chordal_env->irg)); kh.si = si; irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, kh.used); irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh); - lc_bitset_free(kh.used); + bitset_free(kh.used); } void @@ -4001,20 +4106,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); } @@ -4055,18 +4162,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 @@ -4160,33 +4271,6 @@ 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) { @@ -4228,7 +4312,11 @@ 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"); + + DBG((si.dbg, LEVEL_2, "\t initializing\n")); + irg_block_walk_graph(chordal_env->irg, luke_initializer, NULL, &si); if(opt_remats) { /* collect remats */ @@ -4256,7 +4344,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); @@ -4344,14 +4431,15 @@ be_spill_remat(const be_chordal_env_t * chordal_env) if(opt_memcopies) { verify_phiclasses(&si); - assign_spillslots(&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"); if(opt_verify & VERIFY_DOMINANCE) be_check_dominance(chordal_env->irg);