X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillilp.c;h=67763821f012887ce2decf47c278593029d1b5c6;hb=13dc182ad4f2a1e34735d19cba4bc5bd803e416a;hp=0a334792241e073f6836cb3703168c631908b848;hpb=26f53387e067b7233dd307dcfde3393a6eb798ca;p=libfirm diff --git a/ir/be/bespillilp.c b/ir/be/bespillilp.c index 0a3347922..67763821f 100644 --- a/ir/be/bespillilp.c +++ b/ir/be/bespillilp.c @@ -8,6 +8,12 @@ * Copyright (C) 2005 Universitaet Karlsruhe * Released under the GPL */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef WITH_ILP + #include #include "hashptr.h" @@ -21,6 +27,7 @@ #include "irgwalk.h" #include "irnode_t.h" #include "ircons_t.h" +#include "irloop_t.h" #include #include @@ -34,16 +41,19 @@ #include "benode_t.h" #include "beutil.h" #include "bespillilp.h" +#include "bespill.h" -#define BIGM 1000.0 +#include "bechordal_t.h" + +#define BIGM 100000.0 #define MAX(a,b) ((a) > (b) ? (a) : (b)) -#define DBG_LEVEL SET_LEVEL_3 +#define DBG_LEVEL SET_LEVEL_0 // 3 #define DUMP_SOLUTION #define DUMP_ILP -#undef DUMP_STATS +#define DUMP_STATS #undef SOLVE_LOCAL #define LPP_SERVER "i44pc52" @@ -73,9 +83,9 @@ typedef struct _spill_stat_t { } spill_stat_t; typedef struct _spill_ilp_t { + spill_stat_t stats; const arch_register_class_t *cls; - const be_main_session_env_t *session; - firm_dbg_module_t *dbg; + const be_chordal_env_t *chordal_env; lpp_t *lpp; set *irn_use_heads; set *live_ranges; @@ -85,6 +95,7 @@ typedef struct _spill_ilp_t { struct obstack *obst; int enable_store : 1; int enable_remat : 1; + DEBUG_ONLY(firm_dbg_module_t *dbg;) } spill_ilp_t; typedef struct _live_range_t live_range_t; @@ -118,11 +129,29 @@ typedef struct _first_use_t { } first_use_t; +/** + * Get weight for spill/reload costs + * Actually computed with loop depth. + * @param irn The location where to check for the weights. + * @return The weights at this points. + */ +static double get_weight(const ir_node *irn) +{ + ir_loop *loop = get_irn_loop((ir_node *) irn); + int res = 1; + + if(loop) { + int depth = get_loop_depth(loop); + res += depth * depth; + } + + return res; +} + static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn) { - return arch_irn_has_reg_class(si->session->main_env->arch_env, - irn, arch_pos_make_out(0), si->cls); + return chordal_has_class(si->chordal_env, irn); } static int cmp_live_range(const void *a, const void *b, size_t n) @@ -191,7 +220,7 @@ static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn 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->session->main_env->arch_env; + const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env; int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0; for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) { @@ -220,9 +249,14 @@ static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user if(is_new) { char buf[128]; + double cost = 0.0; + + if(pos >= 0) + cost = get_weight(user) * COST_LOAD; + 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); + res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, cost); } memset(&iuh, 0, sizeof(iuh)); @@ -341,6 +375,7 @@ static void process_block(ir_node *bl, void *data) 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); @@ -383,15 +418,17 @@ static void process_block(ir_node *bl, void *data) 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) { -// 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); -// } +#if 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); + } +#endif /* * Check, if the node is a rematerializable node and @@ -481,13 +518,15 @@ static void process_block(ir_node *bl, void *data) 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), "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); + ir_snprintf(buf, sizeof(buf), "edge_b%N_p%N_i%N", bl, pred_bl, end_node); + edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, get_weight(pred_bl) * COST_LOAD); edge->bl = bl; edge->irn = end_node; edge->pos = i; + edge->next = si->edges; + si->edges = edge; - ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn); + ir_snprintf(buf, sizeof(buf), "cedge_b%N_p%N_i%N", bl, pred_bl, end_node); 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); @@ -511,23 +550,25 @@ end: */ static void add_store_costs(spill_ilp_t *si) { - char buf[64]; - irn_use_head_t *uh; - double costs = si->enable_store ? COST_STORE : 0.0; + if(si->enable_store) { + char buf[64]; + irn_use_head_t *uh; - for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) { - int cst; - live_range_t *lr; + for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) { + int cst; + live_range_t *lr; - ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn); - cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); + ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn); + cst = lpp_add_cst(si->lpp, buf, lpp_less, 0); - ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn); - uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs); - lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM); + ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn); + uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, + get_weight(uh->irn) * COST_STORE); + lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM); - list_for_each_entry(live_range_t, lr, &uh->head, list) - lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0); + list_for_each_entry(live_range_t, lr, &uh->head, list) + lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0); + } } } @@ -556,46 +597,57 @@ static void writeback_results(spill_ilp_t *si) for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) { live_range_t *lr; + si->stats.n_spills += !is_zero(lpp_get_var_sol(si->lpp, uh->spill_var)); + /* Go through all live ranges of the node. */ list_for_each_entry(live_range_t, lr, &uh->head, list) { - if(is_spilled(si, lr) && !is_end_of_block_use(lr)) + if(is_spilled(si, lr) && !is_end_of_block_use(lr)) { + DBG((si->dbg, LEVEL_2, "%+F: inserting reload at user %+F\n", + lr->irn, lr->user)); be_add_reload(si->senv, lr->irn, lr->user); + si->stats.n_reloads += 1; + } } } for(edge = si->edges; edge; edge = edge->next) { - if(!is_zero(edge->in_mem_var)) + if(!is_zero(lpp_get_var_sol(si->lpp, edge->in_mem_var))) { + DBG((si->dbg, LEVEL_2, "%+F: insert reload on edge %d from %+F\n", + edge->irn, edge->pos, edge->bl)); be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos); + si->stats.n_reloads += 1; + } } be_insert_spills_reloads(si->senv, NULL); } -void be_spill_ilp(const be_main_session_env_t *session_env, - const arch_register_class_t *cls) +void be_spill_ilp(const be_chordal_env_t *chordal_env) { char problem_name[256]; struct obstack obst; spill_ilp_t si; - ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name); + ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", + chordal_env->irg, chordal_env->cls->name); obstack_init(&obst); - si.session = session_env; + memset(&si.stats, 0, sizeof(si.stats)); + si.chordal_env = chordal_env; si.obst = &obst; - si.dbg = firm_dbg_register("be.ra.spillilp"); - si.senv = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si); - si.cls = cls; + si.senv = be_new_spill_env(chordal_env, is_mem_phi, &si); +// DEBUG_ONLY(si.senv->dbg = si.dbg;) + si.cls = chordal_env->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.first_uses = new_set(cmp_first_use, 4096); si.edges = NULL; si.enable_remat = 0; - si.enable_store = 0; + si.enable_store = 1; + FIRM_DBG_REGISTER(si.dbg, "firm.be.ra.spillilp"); - firm_dbg_set_mask(si.dbg, DBG_LEVEL); - irg_block_walk_graph(session_env->irg, process_block, NULL, &si); + irg_block_walk_graph(chordal_env->irg, process_block, NULL, &si); if(si.enable_store) add_store_costs(&si); @@ -604,7 +656,7 @@ void be_spill_ilp(const be_main_session_env_t *session_env, FILE *f; char buf[256]; - ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name); + ir_snprintf(buf, sizeof(buf), "%s-spill.ilp", problem_name); if((f = fopen(buf, "wt")) != NULL) { lpp_dump_plain(si.lpp, f); fclose(f); @@ -612,7 +664,7 @@ void be_spill_ilp(const be_main_session_env_t *session_env, } #endif - DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg)); + DBG((si.dbg, LEVEL_1, "%F\n", chordal_env->irg)); #ifdef SOLVE_LOCAL lpp_solve_cplex(si.lpp); #else @@ -630,7 +682,7 @@ void be_spill_ilp(const be_main_session_env_t *session_env, FILE *f; char buf[256]; - ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name); + ir_snprintf(buf, sizeof(buf), "%s-spill.sol", problem_name); if((f = fopen(buf, "wt")) != NULL) { int i; for(i = 0; i < si.lpp->var_next; ++i) { @@ -646,6 +698,7 @@ void be_spill_ilp(const be_main_session_env_t *session_env, #ifdef DUMP_STATS { + char buf[256]; FILE *f; ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name); @@ -654,9 +707,9 @@ void be_spill_ilp(const be_main_session_env_t *session_env, fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next); fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next); fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time); - fprintf(f, "%20s: %d\n", "spills", si->stats.n_spills); - fprintf(f, "%20s: %d\n", "reloads", si->stats.n_reloads); - fprintf(f, "%20s: %d\n", "remats", si->stats.n_remat); + fprintf(f, "%20s: %d\n", "spills", si.stats.n_spills); + fprintf(f, "%20s: %d\n", "reloads", si.stats.n_reloads); + fprintf(f, "%20s: %d\n", "remats", si.stats.n_remat); fclose(f); } } @@ -667,3 +720,10 @@ void be_spill_ilp(const be_main_session_env_t *session_env, free_lpp(si.lpp); obstack_free(&obst, NULL); } + +#else /* WITH_ILP */ + +static void only_that_you_can_compile_without_WITH_ILP_defined(void) { +} + +#endif /* WITH_ILP */