X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=685f60189d9c0246b81971dd2a03da23f301577c;hb=48f0393daa5d5a14ed7e3e32ee2b090759c9371e;hp=55fe5145ae8eab733a3c2938ca001bb7f8011f57;hpb=cb0c12e4aa9e238abd067ec1e9bc8a55115e29a4;p=libfirm diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index 55fe5145a..685f60189 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -38,17 +38,112 @@ #include "belive_t.h" #include "beinsn_t.h" #include "besched_t.h" +#include "benodesets.h" +#include "bejavacoal.h" +#include "bestatevent.h" #ifdef WITH_LIBCORE +#include +#include +#endif /* WITH_LIBCORE */ + +#define DUMP_BEFORE 1 +#define DUMP_AFTER 2 +#define DUMP_APPEL 4 +#define DUMP_ALL 2 * DUMP_APPEL - 1 + +#define COST_FUNC_FREQ 1 +#define COST_FUNC_LOOP 2 +#define COST_FUNC_ALL_ONE 3 + +static unsigned dump_flags = 0; +static unsigned style_flags = 0; +static unsigned do_stats = 0; +static cost_fct_t cost_func = co_get_costs_exec_freq; +static int algo = CO_ALGO_HEUR2; +static int improve = 1; + +#ifdef WITH_LIBCORE +static const lc_opt_enum_mask_items_t dump_items[] = { + { "before", DUMP_BEFORE }, + { "after", DUMP_AFTER }, + { "appel", DUMP_APPEL }, + { "all", DUMP_ALL }, + { NULL, 0 } +}; + +static const lc_opt_enum_mask_items_t style_items[] = { + { "color", CO_IFG_DUMP_COLORS }, + { "labels", CO_IFG_DUMP_LABELS }, + { "constr", CO_IFG_DUMP_CONSTR }, + { "shape", CO_IFG_DUMP_SHAPE }, + { "full", 2 * CO_IFG_DUMP_SHAPE - 1 }, + { NULL, 0 } +}; + +static const lc_opt_enum_mask_items_t algo_items[] = { + { "none", CO_ALGO_NONE }, + { "heur", CO_ALGO_HEUR }, + { "heur2", CO_ALGO_HEUR2 }, +#ifdef WITH_JVM + { "heur3", CO_ALGO_HEUR3 }, +#endif /* WITH_JVM */ +#ifdef WITH_ILP + { "ilp", CO_ALGO_ILP }, +#endif /* WITH_ILP */ + { NULL, 0 } +}; + +typedef int (*opt_funcptr)(void); + +static const lc_opt_enum_func_ptr_items_t cost_func_items[] = { + { "freq", (opt_funcptr) co_get_costs_exec_freq }, + { "loop", (opt_funcptr) co_get_costs_loop_depth }, + { "one", (opt_funcptr) co_get_costs_all_one }, + { NULL, NULL } +}; + +static lc_opt_enum_mask_var_t dump_var = { + &dump_flags, dump_items +}; + +static lc_opt_enum_mask_var_t style_var = { + &style_flags, style_items +}; + +static lc_opt_enum_mask_var_t algo_var = { + &algo, algo_items +}; + +static lc_opt_enum_func_ptr_var_t cost_func_var = { + (opt_funcptr*) &cost_func, cost_func_items +}; + +static const lc_opt_table_entry_t options[] = { + LC_OPT_ENT_ENUM_INT ("algo", "select copy optimization algo", &algo_var), + LC_OPT_ENT_ENUM_FUNC_PTR ("cost", "select a cost function", &cost_func_var), + LC_OPT_ENT_ENUM_MASK ("dump", "dump ifg before or after copy optimization", &dump_var), + LC_OPT_ENT_ENUM_MASK ("style", "dump style for ifg dumping", &style_var), + LC_OPT_ENT_BOOL ("stats", "dump statistics after each optimization", &do_stats), + LC_OPT_ENT_BOOL ("improve", "run heur3 before if algo can exploit start solutions", &improve), + { NULL } +}; /* Insert additional options registration functions here. */ +extern void be_co_ilp_register_options(lc_opt_entry_t *grp); extern void be_co2_register_options(lc_opt_entry_t *grp); extern void be_co3_register_options(lc_opt_entry_t *grp); void co_register_options(lc_opt_entry_t *grp) { - be_co2_register_options(grp); - be_co3_register_options(grp); + lc_opt_entry_t *co_grp = lc_opt_get_grp(grp, "co"); + lc_opt_add_table(co_grp, options); + + be_co2_register_options(co_grp); + be_co3_register_options(co_grp); +#ifdef WITH_ILP + be_co_ilp_register_options(co_grp); +#endif } #endif @@ -67,6 +162,7 @@ void co_register_options(lc_opt_entry_t *grp) DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) + void be_copy_opt_init(void) { } @@ -164,18 +260,21 @@ int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, i int d = get_loop_depth(loop); cost = d*d; } - return cost+1; + return 1+cost; } int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) { + int res; ir_node *root_bl = get_nodes_block(root); ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl; - unsigned long freq = get_block_execfreq_ulong(co->cenv->exec_freq, copy_bl); - return freq > 0 ? (int) freq : 1; + res = get_block_execfreq_ulong(co->cenv->exec_freq, copy_bl); + + /* don't allow values smaller than one. */ + return res < 1 ? 1 : res; } -int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) { +int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node *arg, int pos) { return 1; } @@ -551,6 +650,40 @@ int co_get_lower_bound(const copy_opt_t *co) { return res; } +void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat) +{ + bitset_t *seen = bitset_irg_malloc(co->irg); + affinity_node_t *an; + + memset(stat, 0, sizeof(stat[0])); + + /* count affinity edges. */ + co_gs_foreach_aff_node(co, an) { + neighb_t *neigh; + stat->aff_nodes += 1; + bitset_add_irn(seen, an->irn); + co_gs_foreach_neighb(an, neigh) { + if(!bitset_contains_irn(seen, neigh->irn)) { + stat->aff_edges += 1; + stat->max_costs += neigh->costs; + + if(get_irn_col(co, an->irn) != get_irn_col(co, neigh->irn)) { + stat->costs += neigh->costs; + stat->unsatisfied_edges += 1; + } + + if(nodes_interfere(co->cenv, an->irn, neigh->irn)) { + stat->aff_int += 1; + stat->inevit_costs += neigh->costs; + } + + } + } + } + + bitset_free(seen); +} + /****************************************************************************** _____ _ _____ _ / ____| | | / ____| | @@ -577,7 +710,7 @@ static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) { new_node.irn = n1; new_node.degree = 0; new_node.neighbours = NULL; - node = set_insert(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); + node = set_insert(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn)); allocnew = 1; for (nbr = node->neighbours; nbr; nbr = nbr->next) @@ -662,7 +795,7 @@ int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) { ASSERT_GS_AVAIL(co); new_node.irn = irn; - n = set_find(co->nodes, &new_node, sizeof(new_node), HASH_PTR(new_node.irn)); + n = set_find(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn)); if (n) { return (n->degree > 0); } else @@ -735,7 +868,7 @@ void co_dump_appel_graph(const copy_opt_t *co, FILE *f) if(!arch_irn_is(co->aenv, n->irn, ignore)) { int n_idx = PTR_TO_INT(get_irn_link(n->irn)); if(idx < n_idx) - fprintf(f, "%d %d %d\n", idx, n_idx, n->costs); + fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs); } } } @@ -995,7 +1128,6 @@ static void appel_inter_block_aff(ir_node *bl, void *data) for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) { ir_node *pred = get_Block_cfgpred_block(bl, j); - appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred); int nr = appel_get_live_end_nr(env, pred, irn); assert(nr >= 0); @@ -1008,7 +1140,6 @@ static void appel_inter_block_aff(ir_node *bl, void *data) for(j = 0, n = get_Block_n_cfgpreds(bl); j < n; ++j) { ir_node *pred = get_Block_cfgpred_block(bl, j); - appel_block_info_t *pred_bli = phase_get_irn_data(&env->ph, pred); ir_node *op = get_irn_n(irn, j); int nr = appel_get_live_end_nr(env, pred, op); @@ -1067,12 +1198,12 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f) } /* -___ _____ ____ ____ ___ _____ ____ _ -|_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ -| || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | -| || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| | -|___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | -|_| |___/ + ___ _____ ____ ____ ___ _____ ____ _ + |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ + | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | + | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| | + |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | + |_| |___/ */ static const char *get_dot_color_name(int col) @@ -1119,20 +1250,9 @@ typedef struct _co_ifg_dump_t { unsigned flags; } co_ifg_dump_t; -static const char *get_dot_shape_name(co_ifg_dump_t *cod, ir_node *irn) -{ - arch_register_req_t req; - - arch_get_register_req(cod->co->aenv, &req, irn, BE_OUT_POS(0)); - if(arch_register_req_is(&req, limited)) - return "diamond"; - - return "ellipse"; -} - static void ifg_dump_graph_attr(FILE *f, void *self) { - fprintf(f, "overlay=false"); + fprintf(f, "overlap=scale"); } static int ifg_is_dump_node(void *self, ir_node *irn) @@ -1145,8 +1265,31 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) { co_ifg_dump_t *env = self; const arch_register_t *reg = arch_get_irn_register(env->co->aenv, irn); + arch_register_req_t req; + int limited; + + arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0)); + limited = arch_register_req_is(&req, limited); - ir_fprintf(f, "label=\"%+F\" style=filled color=%s shape=%s", irn, get_dot_color_name(reg->index), get_dot_shape_name(env, irn)); + if(env->flags & CO_IFG_DUMP_LABELS) { + ir_fprintf(f, "label=\"%+F", irn); + + if((env->flags & CO_IFG_DUMP_CONSTR) && limited) { + bitset_t *bs = bitset_alloca(env->co->cls->n_regs); + req.limited(req.limited_env, bs); + ir_fprintf(f, "\\n%B", bs); + } + ir_fprintf(f, "\" "); + } + + else + fprintf(f, "label=\"\" shape=point " ); + + if(env->flags & CO_IFG_DUMP_SHAPE) + fprintf(f, "shape=%s ", limited ? "diamond" : "ellipse"); + + if(env->flags & CO_IFG_DUMP_COLORS) + fprintf(f, "style=filled color=%s ", get_dot_color_name(reg->index)); } static void ifg_dump_at_end(FILE *file, void *self) @@ -1161,11 +1304,18 @@ static void ifg_dump_at_end(FILE *file, void *self) co_gs_foreach_neighb(a, n) { const arch_register_t *nr = arch_get_irn_register(env->co->aenv, n->irn); - int nidx = get_irn_idx(n->irn); + unsigned nidx = get_irn_idx(n->irn); if(aidx < nidx) { const char *color = nr == ar ? "blue" : "red"; - fprintf(file, "\tn%d -- n%d [label=\"%d\" style=dashed color=%s];\n", aidx, nidx, n->costs, color); + fprintf(file, "\tn%d -- n%d [weight=0.01 ", aidx, nidx); + if(env->flags & CO_IFG_DUMP_LABELS) + fprintf(file, "label=\"%d\" ", n->costs); + if(env->flags & CO_IFG_DUMP_COLORS) + fprintf(file, "color=%s ", color); + else + fprintf(file, "style=dotted"); + fprintf(file, "];\n"); } } } @@ -1197,3 +1347,146 @@ void co_solve_park_moon(copy_opt_t *opt) { } + +static int void_algo(copy_opt_t *co) +{ + return 0; +} + +/* + _ _ _ _ _ + / \ | | __ _ ___ _ __(_) |_| |__ _ __ ___ ___ + / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \/ __| + / ___ \| | (_| | (_) | | | | |_| | | | | | | | \__ \ + /_/ \_\_|\__, |\___/|_| |_|\__|_| |_|_| |_| |_|___/ + |___/ +*/ + +typedef struct { + co_algo_t *algo; + const char *name; + int can_improve_existing; +} co_algo_info_t; + +static co_algo_info_t algos[] = { + { void_algo, "none", 0 }, + { co_solve_heuristic, "heur1", 0 }, + { co_solve_heuristic_new, "heur2", 0 }, + { co_solve_heuristic_java, "heur3", 0 }, +#ifdef WITH_ILP + { co_solve_ilp2, "ilp", 1 }, +#endif + { NULL, "", 0 } +}; + +/* + __ __ _ ____ _ + | \/ | __ _(_)_ __ | _ \ _ __(_)_ _____ _ __ + | |\/| |/ _` | | '_ \ | | | | '__| \ \ / / _ \ '__| + | | | | (_| | | | | | | |_| | | | |\ V / __/ | + |_| |_|\__,_|_|_| |_| |____/|_| |_| \_/ \___|_| + +*/ + +void co_driver(be_chordal_env_t *cenv) +{ +#ifdef WITH_LIBCORE + lc_timer_t *timer = lc_timer_register("firm.be.copyopt", "runtime"); +#endif + co_complete_stats_t before, after; + copy_opt_t *co; + co_algo_t *algo_func; + int was_optimal = 0; + + if(algo < 0 || algo >= CO_ALGO_LAST) + return; + + co = new_copy_opt(cenv, cost_func); + co_build_ou_structure(co); + co_build_graph_structure(co); + + co_complete_stats(co, &before); + + be_stat_ev_ull("co_aff_nodes", before.aff_nodes); + be_stat_ev_ull("co_aff_edges", before.aff_edges); + be_stat_ev_ull("co_max_costs", before.max_costs); + be_stat_ev_ull("co_inevit_costs", before.inevit_costs); + be_stat_ev_ull("co_aff_int", before.aff_int); + + be_stat_ev_ull("co_init_costs", before.costs); + be_stat_ev_ull("co_init_unsat", before.unsatisfied_edges); + + /* Dump the interference graph in Appel's format. */ + if(dump_flags & DUMP_APPEL) { + FILE *f = be_chordal_open(cenv, "", ".apl"); + co_dump_appel_graph(co, f); + fclose(f); + } + + if(dump_flags & DUMP_BEFORE) { + FILE *f = be_chordal_open(cenv, "", "-before.dot"); + co_dump_ifg_dot(co, f, style_flags); + fclose(f); + } + + /* if the algo can improve results, provide an initial solution with heur3 */ + if(improve && algos[algo].can_improve_existing) { + co_complete_stats_t stats; + + /* produce a heuristical solution */ + co_solve_heuristic_java(co); + + /* do the stats and provide the current costs */ + co_complete_stats(co, &stats); + be_stat_ev_ull("co_prepare_costs", stats.costs); + } + +#ifdef WITH_JVM + /* start the JVM here so that it does not tamper the timing. */ + if(algo == CO_ALGO_HEUR3) + be_java_coal_start_jvm(); +#endif + + algo_func = algos[algo].algo; + +#ifdef WITH_LIBCORE + lc_timer_reset_and_start(timer); +#endif + + was_optimal = algo_func(co); + +#ifdef WITH_LIBCORE + lc_timer_stop(timer); + be_stat_ev("co_time", lc_timer_elapsed_msec(timer)); +#endif + + be_stat_ev_ull("co_optimal", was_optimal); + + if(dump_flags & DUMP_AFTER) { + FILE *f = be_chordal_open(cenv, "", "-after.dot"); + co_dump_ifg_dot(co, f, style_flags); + fclose(f); + } + + co_complete_stats(co, &after); + + if(do_stats) { + ulong64 optimizable_costs = after.max_costs - after.inevit_costs; + ulong64 evitable = after.costs - after.inevit_costs; + + ir_printf("%30F ", cenv->irg); + printf("%10s %10" ULL_FMT "%10" ULL_FMT "%10" ULL_FMT, cenv->cls->name, after.max_costs, before.costs, after.inevit_costs); + + if(optimizable_costs > 0) + printf("%10" ULL_FMT " %5.2f\n", after.costs, (evitable * 100.0) / optimizable_costs); + else + printf("%10" ULL_FMT " %5s\n", after.costs, "-"); + } + + be_stat_ev_ull("co_after_costs", after.costs); + be_stat_ev_ull("co_after_unsat", after.unsatisfied_edges); + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); +}