X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillilp.c;h=0a334792241e073f6836cb3703168c631908b848;hb=7ce0bb4ead9ca9c526a3a26bb8469915bf966f12;hp=a61ae4a88b5729ecaae47526a11bc4eec80fc3e9;hpb=22e1dae4b74199ec476e3efb1b48d9f07b721aac;p=libfirm diff --git a/ir/be/bespillilp.c b/ir/be/bespillilp.c index a61ae4a88..0a3347922 100644 --- a/ir/be/bespillilp.c +++ b/ir/be/bespillilp.c @@ -39,12 +39,13 @@ #define MAX(a,b) ((a) > (b) ? (a) : (b)) -#define DBG_LEVEL SET_LEVEL_4 +#define DBG_LEVEL SET_LEVEL_3 -#undef DUMP_SOLUTION +#define DUMP_SOLUTION #define DUMP_ILP -#undef DUMP_STATS +#undef DUMP_STATS +#undef SOLVE_LOCAL #define LPP_SERVER "i44pc52" #define LPP_SOLVER "cplex" @@ -54,6 +55,17 @@ #define is_end_of_block_use(lr) (is_Block((lr)->user)) +/** + * Reloads on edges. + */ +typedef struct _edge_reload_t { + ir_node *irn; + ir_node *bl; + int pos; + int in_mem_var; + struct _edge_reload_t *next; +} edge_reload_t; + typedef struct _spill_stat_t { int n_spills; int n_reloads; @@ -62,11 +74,14 @@ typedef struct _spill_stat_t { typedef struct _spill_ilp_t { const arch_register_class_t *cls; + const be_main_session_env_t *session; firm_dbg_module_t *dbg; lpp_t *lpp; set *irn_use_heads; set *live_ranges; - spill_env_t senv; + set *first_uses; + spill_env_t *senv; + edge_reload_t *edges; struct obstack *obst; int enable_store : 1; int enable_remat : 1; @@ -83,18 +98,30 @@ typedef struct _irn_use_head_t { } irn_use_head_t; struct _live_range_t { - struct list_head list; + struct list_head list; irn_use_head_t *use_head; - ir_node *user; - ir_node *irn; + ir_node *user; + ir_node *irn; int pos; - int in_mem_var; - int is_remat_var; + int in_mem_var; + int is_remat_var; }; -static int has_reg_class(const spill_ilp_t *si, const ir_node *irn) +/* + * Associates the first use of a live-in in a block + * with its live range. + */ +typedef struct _first_use_t { + ir_node *bl; + ir_node *irn; /**< A value live in at bl. */ + live_range_t *lr; /**< The live range for the first use of irn in bl. */ +} first_use_t; + + + +static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn) { - return arch_irn_has_reg_class(si->senv.session->main_env->arch_env, + return arch_irn_has_reg_class(si->session->main_env->arch_env, irn, arch_pos_make_out(0), si->cls); } @@ -114,6 +141,45 @@ static int cmp_irn_use_head(const void *a, const void *b, size_t n) return !(p->irn == q->irn); } +static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn) +{ + irn_use_head_t templ; + templ.irn = (ir_node *) irn; + return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn)); +} + +static int cmp_first_use(const void *a, const void *b, size_t n) +{ + const first_use_t *p = a; + const first_use_t *q = b; + + return !(p->irn == q->irn && p->bl == q->bl); +} + +static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr) +{ + first_use_t templ; + templ.bl = bl; + templ.irn = irn; + templ.lr = lr; + + set_insert(si->first_uses, &templ, sizeof(templ), + HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn))); +} + +static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn) +{ + first_use_t *res; + first_use_t templ; + templ.bl = bl; + templ.irn = irn; + + res = set_find(si->first_uses, &templ, sizeof(templ), + HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn))); + + return res ? res->lr : NULL; +} + /** * Checks, if a vertain node can be recomputed at a certain position. * @param si The spill ILP environment. @@ -125,7 +191,7 @@ static int cmp_irn_use_head(const void *a, const void *b, size_t n) static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live) { int i, n; - const arch_env_t *arch_env = si->senv.session->main_env->arch_env; + const arch_env_t *arch_env = si->session->main_env->arch_env; int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0; for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) { @@ -138,26 +204,26 @@ static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *liv static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos) { - live_range_t lr, *res; + live_range_t lr, *res; irn_use_head_t iuh, *head; int is_new; - unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user)); + unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user)); - lr.user = user; - lr.irn = irn; - lr.pos = pos; - lr.in_mem_var = -1; + lr.user = user; + lr.irn = irn; + lr.pos = pos; + lr.in_mem_var = -1; lr.is_remat_var = -1; - res = set_insert(si->live_ranges, &lr, sizeof(lr), hash); + res = set_insert(si->live_ranges, &lr, sizeof(lr), hash); is_new = res->in_mem_var == -1; - if(is_new) { - char buf[128]; - ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d", - is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0)); - res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0); - } + if(is_new) { + char buf[128]; + ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d", + is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0)); + res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0); + } memset(&iuh, 0, sizeof(iuh)); iuh.irn = irn; @@ -175,118 +241,136 @@ static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user res->use_head = head; - return res; + return res; } -static ir_node *process_irn(spill_ilp_t *si, pset *live, ir_node *irn, int *demand) -{ - int i, n; - int relevant_args = 0, results = 0; - - DBG((si->dbg, LEVEL_1, "at %+F\n", irn)); - - while(is_Proj(irn)) { - if(has_reg_class(si, irn)) { - assert(pset_find_ptr(live, irn) && "node must be live"); - pset_remove_ptr(live, irn); - results++; - } - - DBG((si->dbg, LEVEL_1, "skipped proj %+F\n", irn)); - irn = sched_prev(irn); - } - - DBG((si->dbg, LEVEL_1, "\tlanded at irn %+F\n", irn)); - - if(results > 0) - assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple"); - - if(has_reg_class(si, irn)) { - assert( pset_find_ptr(live, irn) && "node must be live"); - pset_remove_ptr(live, irn); - results = 1; - } - - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *op = get_irn_n(irn, i); - if(has_reg_class(si, op) && !pset_find_ptr(live, op)) { - relevant_args++; - DBG((si->dbg, LEVEL_1, "\trelevant arg %+F\n", op)); - } - } - - *demand = MAX(results, relevant_args); - DBG((si->dbg, LEVEL_1, "\tdemand: %d\n", *demand)); - return irn; +static void print_live_set(spill_ilp_t *si, pset *s) { + ir_node *n; + for(n=pset_first(s); n; n=pset_next(s)) + DBG((si->dbg, LEVEL_3, " %+F\n", n)); } static void process_block(ir_node *bl, void *data) { char buf[128]; - int i, n; - spill_ilp_t *si = data; - int step = 0; - int n_regs = arch_register_class_n_regs(si->cls); + int i, n, skipped=0; + spill_ilp_t *si = data; + int step = 0; + int n_regs = arch_register_class_n_regs(si->cls); int n_preds = get_irn_arity(bl); - pset *live = pset_new_ptr_default(); - irn_live_t *li; - ir_node *irn, *next_irn; - - /* as always, bring the live end nodes to life here */ - live_foreach(bl, li) { - if(live_is_end(li) && has_reg_class(si, li->irn)) { - ir_node *irn = (ir_node *) li->irn; - pset_insert_ptr(live, irn); - - /* - * The "user" of the live range to the end of a block - * is the block itself. This is quite arbitrary. - */ - set_irn_link(irn, get_live_range(si, irn, bl, -1)); - } - } + pset *live = pset_new_ptr_default(); + irn_live_t *li; + ir_node *irn; + + DBG((si->dbg, LEVEL_3, "\n")); + DBG((si->dbg, LEVEL_3, "Processing %+F\n", bl)); + + /* + * Get all live-end values of this block + */ + live_foreach(bl, li) { + if(live_is_end(li) && has_reg_class(si, li->irn)) { + ir_node *irn = (ir_node *) li->irn; + pset_insert_ptr(live, irn); + + /*The "user" of the live range to the end of a block + * is the block itself. This is quite arbitrary. */ + set_irn_link(irn, get_live_range(si, irn, bl, -1)); + } + } + DBG((si->dbg, LEVEL_3, "Live-End:\n")); + print_live_set(si, live); + /* + * Walk through the schedule of this block from end to begin. + * Phis are handled togther with live ins after this loop. + */ for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) { ir_node *l; int cst; + int relevant_args, results; int demand; - int n_live; + int n_cand; int must_be_in_mem; + pset *cand; - /* We handle phi togther with live ins after this loop (see below). */ - if(is_Phi(irn)) - break; + /* + * Determine the number of results + */ + /* Special handling of Projs */ + if(is_Proj(irn)) { + if(has_reg_class(si, irn)) { + assert(pset_find_ptr(live, irn) && "node must be live"); + pset_remove_ptr(live, irn); + skipped++; + } -#if 0 - if(has_reg_class(si, irn)) - pset_remove_ptr(live, irn); + DBG((si->dbg, LEVEL_2, "Skipped %+F\n", irn)); + continue; + } - demand = register_demand(si, live, irn); - n_live = pset_count(live); -#endif + DBG((si->dbg, LEVEL_1, "Irn %+F\n", irn)); + if(skipped > 0) { + /* ModeT node */ + assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple"); + results = skipped; + skipped = 0; + } else { + /* Normal node */ + if(has_reg_class(si, irn)) { + assert(get_irn_mode(irn) != mode_T && "node must not be a tuple"); + assert(pset_find_ptr(live, irn) && "node must be live"); + pset_remove_ptr(live, irn); + results = 1; + } else { + results = 0; + } + } - irn = process_irn(si, live, irn, &demand); - n_live = pset_count(live); + /* cand holds the irns which may be spilled */ + cand = pset_new_ptr(8); + for(l=pset_first(live); l; l=pset_next(live)) + pset_insert_ptr(cand, l); /* - * Determine, how many values (which are not used at the label) - * must be in memory. - * demand means the number of registers, the operation will consume. - * So there are n_regs - demand registers available to store values - * which are not used at this label. The rest must reside in memory. + * Determine number of arguments */ - must_be_in_mem = MAX(n_live + demand - n_regs, 0); + relevant_args = 0; + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + if(has_reg_class(si, op)) { + DBG((si->dbg, LEVEL_2, " arg %+F\n", op)); + relevant_args++; + /* arguments must not be spilled */ + if(pset_find_ptr(cand, op)) + pset_remove_ptr(cand, op); + } + } - if(must_be_in_mem > 0) { + /* + * Determine, how many values must be in memory. + * We have 'n_regs' registers. + * The instr. needs 'demand'. + * So (R:= n_regs - demand) registers can be used for candidates 'cand'. + * The rest (M:= n_cand - R) must reside in memory. + */ + demand = MAX(results, relevant_args); + n_cand = pset_count(cand); + must_be_in_mem = n_cand - (n_regs - demand); - /* - * The constraint limiting the pressure at this label to - * the number of free registers. - */ - ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step); + DBG((si->dbg, LEVEL_1, " Demand: %d, Cands: %d, InMem: %d\n", demand, n_cand, must_be_in_mem)); + DBG((si->dbg, LEVEL_3, " Cand-Set:\n")); + print_live_set(si, cand); + + /* + * Generate the corresponding constraint spilling + * enough candidates at this label. + */ + if(must_be_in_mem > 0) { + ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step); cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem); - for(l = pset_first(live); l; l = pset_next(live)) { + for(l = pset_first(cand); l; l = pset_next(cand)) { live_range_t *lr = get_irn_link(l); lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0); } @@ -297,17 +381,17 @@ static void process_block(ir_node *bl, void *data) if(has_reg_class(si, op)) { live_range_t *op_lr = get_live_range(si, op, irn, i); - set_irn_link(op, op_lr); - /* - * The operand is reloaded at its usage, so it must not occur - * in the constraint which determines which values live at the - * instruction must reside in memory. - */ - if(must_be_in_mem > 0) { - lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0); - } +// /* +// * The operand is reloaded at its usage, so it must not occur +// * in the constraint which determines which values live at the +// * instruction must reside in memory. +// */ +// if(must_be_in_mem > 0) { +// DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op)); +// lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0); +// } /* * Check, if the node is a rematerializable node and @@ -346,12 +430,16 @@ static void process_block(ir_node *bl, void *data) } } - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *op = get_irn_n(irn, i); - if(has_reg_class(si, op) && !is_Phi(irn)) - pset_insert_ptr(live, op); - } + /* + * Insert arguments of current instr into the live set + */ + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + if(has_reg_class(si, op)) + pset_insert_ptr(live, op); + } + del_pset(cand); step++; } @@ -359,9 +447,11 @@ static void process_block(ir_node *bl, void *data) goto end; /* - * Here, only the phis in the block and the values live in are in the - * live set. + * Here, the live set contains + * - phis of the block + * - live-in values of the block * + * TODO: comment is wrong * If a value is live in, it must be in a register in all predecessor * blocks or in memory at the end of all predecessor blocks. Also, the * closest use in the current block must then be from register or @@ -372,41 +462,41 @@ static void process_block(ir_node *bl, void *data) int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl; int cst; - if(is_phi) - lr->use_head->closest_use = lr; - assert(has_reg_class(si, irn)); assert(is_Phi(irn) || is_live_in(bl, irn)); -#if 0 - ir_snprintf(buf, sizeof(buf), "c%s_%N_%N", (is_phi ? "phi" : "li"), irn, bl); - cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0); - lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -n_preds); - - for(i = 0; i < n_preds; ++i) { - ir_node *pred_bl = get_Block_cfgpred_block(bl, i); - ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn; - live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1); + /* Deprecated: Can be done with the first uses map */ + if(is_phi) + lr->use_head->closest_use = lr; - lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0); - } -#endif + /* + * Remind the liverange of the first use of a live (or phi) in the + * current block. + */ + add_first_use(si, bl, irn, lr); for(i = 0; i < n_preds; ++i) { ir_node *pred_bl = get_Block_cfgpred_block(bl, i); ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn; live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1); + edge_reload_t *edge = obstack_alloc(si->obst, sizeof(edge[0])); - ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i); - cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0); + ir_snprintf(buf, sizeof(buf), "edge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn); + edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD); + edge->bl = bl; + edge->irn = end_node; + edge->pos = i; + + ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0); lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0); lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0); + lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0); } } end: - - del_pset(live); + del_pset(live); } /** @@ -451,53 +541,34 @@ static int is_spilled(const spill_ilp_t *si, const live_range_t *lr) return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var)); } +static int is_mem_phi(const ir_node *phi, void *data) +{ + spill_ilp_t *si = data; + return is_spilled(si, get_use_head(si, phi)->closest_use); +} + static void writeback_results(spill_ilp_t *si) { - const be_node_factory_t *fact = si->senv.session->main_env->node_factory; irn_use_head_t *uh; - si->senv.mem_phis = pset_new_ptr_default(); - - for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) { - if(is_Phi(uh->irn) && is_spilled(si, uh->closest_use)) - pset_insert_ptr(si->senv.mem_phis, uh->irn); - } + edge_reload_t *edge; /* Look at each node and examine the usages. */ for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) { live_range_t *lr; - ir_node **reloads; - - int n_reloads = 0; - ir_node *irn = uh->irn; - ir_mode *mode = get_irn_mode(irn); /* Go through all live ranges of the node. */ list_for_each_entry(live_range_t, lr, &uh->head, list) { - int spilled = is_spilled(si, lr); - // int rematd = !is_zero(lpp_get_var_sol(si->lpp, lr->is_remat_var)); - - if(spilled && !is_end_of_block_use(lr)) { - ir_node *bl = get_nodes_block(lr->user); - - - ir_node *spill = be_spill_node(&si->senv, lr->irn); - ir_node *reload = new_Reload(fact, si->cls, si->senv.session->irg, bl, mode, spill); - - /* inc_stats_reload(si); */ - obstack_ptr_grow(si->obst, reload); - n_reloads++; - - sched_add_before(lr->user, reload); - } + if(is_spilled(si, lr) && !is_end_of_block_use(lr)) + be_add_reload(si->senv, lr->irn, lr->user); } + } - if(n_reloads > 0) { - reloads = obstack_finish(si->obst); - be_introduce_copies_ignore(si->senv.session->dom_front, irn, n_reloads, reloads, si->senv.mem_phis); - obstack_free(si->obst, reloads); - } + for(edge = si->edges; edge; edge = edge->next) { + if(!is_zero(edge->in_mem_var)) + be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos); } - be_remove_spilled_phis(&si->senv); + + be_insert_spills_reloads(si->senv, NULL); } void be_spill_ilp(const be_main_session_env_t *session_env, @@ -510,14 +581,16 @@ void be_spill_ilp(const be_main_session_env_t *session_env, ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name); obstack_init(&obst); + si.session = session_env; si.obst = &obst; si.dbg = firm_dbg_register("be.ra.spillilp"); - si.senv.session = session_env; + si.senv = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si); si.cls = cls; si.lpp = new_lpp(problem_name, lpp_minimize); si.irn_use_heads = new_set(cmp_irn_use_head, 4096); si.live_ranges = new_set(cmp_live_range, 16384); - si.senv.spill_ctxs = new_set(be_set_cmp_spillctx, 4096); + si.first_uses = new_set(cmp_first_use, 4096); + si.edges = NULL; si.enable_remat = 0; si.enable_store = 0; @@ -540,8 +613,11 @@ void be_spill_ilp(const be_main_session_env_t *session_env, #endif DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg)); -// lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER); +#ifdef SOLVE_LOCAL lpp_solve_cplex(si.lpp); +#else + lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER); +#endif assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid"); DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n", @@ -559,14 +635,14 @@ void be_spill_ilp(const be_main_session_env_t *session_env, int i; for(i = 0; i < si.lpp->var_next; ++i) { lpp_name_t *name = si.lpp->vars[i]; - fprintf(f, "%10s %4d %10f\n", name->name, name->nr, name->value); + fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value); } fclose(f); } } #endif - writeback_results(&si); + writeback_results(&si); #ifdef DUMP_STATS { @@ -586,8 +662,8 @@ void be_spill_ilp(const be_main_session_env_t *session_env, } #endif - del_set(si.irn_use_heads); - del_set(si.live_ranges); - free_lpp(si.lpp); - obstack_free(&obst, NULL); + del_set(si.irn_use_heads); + del_set(si.live_ranges); + free_lpp(si.lpp); + obstack_free(&obst, NULL); }