X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=316e31a03ca2a69f601fd56a15facdcd02120451;hb=4ed245f5007168dab7850942a7ee6b6b29a19817;hp=9088ddf011a29ef9d2008ef1299ec7ffede04425;hpb=b2396bbf9d898dd5b8b8161455eed907a1d81c7d;p=libfirm diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c index 9088ddf01..316e31a03 100644 --- a/ir/be/becopyopt.c +++ b/ir/be/becopyopt.c @@ -26,6 +26,8 @@ #include "phiclass.h" #include "irbitset.h" #include "irphase_t.h" +#include "irprintf_t.h" + #include "bearch.h" #include "benode_t.h" @@ -37,14 +39,95 @@ #include "beinsn_t.h" #include "besched_t.h" +#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 int dump_flags = 0; +static int style_flags = 0; +static int do_stats = 0; +static cost_fct_t cost_func = co_get_costs_exec_freq; +static int algo = CO_ALGO_HEUR2; + #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 }, + { "heur3", CO_ALGO_HEUR3 }, + { "ilp", CO_ALGO_ILP }, + { NULL, 0 } +}; + +static const lc_opt_enum_func_ptr_items_t cost_func_items[] = { + { "freq", co_get_costs_exec_freq }, + { "loop", co_get_costs_loop_depth }, + { "one", co_get_costs_all_one }, + { NULL, 0 } +}; + +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 = { + &cost_func, cost_func_items +}; + +static const lc_opt_table_entry_t options[] = { + LC_OPT_ENT_ENUM_INT ("algo", "select copy optimization algo (heur, heur2, heur3, ilp)", &algo_var), + LC_OPT_ENT_ENUM_FUNC_PTR ("cost", "select a cost function (freq, loop, one)", &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), + { 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); + 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 @@ -166,7 +249,8 @@ int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, i int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) { ir_node *root_bl = get_nodes_block(root); ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl; - return (int) get_block_execfreq(co->cenv->exec_freq, copy_bl); + unsigned long freq = get_block_execfreq_ulong(co->cenv->exec_freq, copy_bl); + return freq > 0 ? (int) freq : 1; } @@ -896,7 +980,7 @@ static void appel_walker(ir_node *bl, void *data) } DBG((env->co->cenv->dbg, LEVEL_2, "%+F\n", bl)); - be_liveness_end_of_block(env->co->aenv, env->co->cls, bl, live); + be_liveness_end_of_block(env->co->cenv->lv, env->co->aenv, env->co->cls, bl, live); /* Generate the bad and ugly. */ for(i = n_insns - 1; i >= 0; --i) { @@ -990,7 +1074,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); @@ -1003,7 +1086,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); @@ -1021,7 +1103,7 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f) appel_clique_walker_t env; bitset_t *adm = bitset_alloca(co->cls->n_regs); - be_liveness(co->irg); + be_liveness_recompute(co->cenv->lv); obstack_init(&env.obst); phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init); env.curr_nr = co->cls->n_regs; @@ -1061,8 +1143,242 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f) obstack_free(&env.obst, NULL); } +/* + ___ _____ ____ ____ ___ _____ ____ _ + |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ + | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | + | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| | + |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | + |_| |___/ +*/ + +static const char *get_dot_color_name(int col) +{ + static const char *names[] = { + "blue", + "red", + "green", + "yellow", + "cyan", + "magenta", + "orange", + "chocolate", + "beige", + "navy", + "darkgreen", + "darkred", + "lightPink", + "chartreuse", + "lightskyblue", + "linen", + "pink", + "lightslateblue", + "mintcream", + "red", + "darkolivegreen", + "mediumblue", + "mistyrose", + "salmon", + "darkseagreen", + "mediumslateblue" + "moccasin", + "tomato", + "forestgreen", + "darkturquoise", + "palevioletred" + }; + + return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white"; +} + +typedef struct _co_ifg_dump_t { + const copy_opt_t *co; + unsigned flags; +} co_ifg_dump_t; + +static void ifg_dump_graph_attr(FILE *f, void *self) +{ + fprintf(f, "overlap=scale"); +} + +static int ifg_is_dump_node(void *self, ir_node *irn) +{ + co_ifg_dump_t *cod = self; + return !arch_irn_is(cod->co->aenv, irn, ignore); +} + +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); + + 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) +{ + co_ifg_dump_t *env = self; + affinity_node_t *a; + + co_gs_foreach_aff_node(env->co, a) { + const arch_register_t *ar = arch_get_irn_register(env->co->aenv, a->irn); + unsigned aidx = get_irn_idx(a->irn); + neighb_t *n; + + co_gs_foreach_neighb(a, n) { + const arch_register_t *nr = arch_get_irn_register(env->co->aenv, 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 [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=dashed"); + fprintf(file, "];\n"); + } + } + } +} + + +static be_ifg_dump_dot_cb_t ifg_dot_cb = { + ifg_is_dump_node, + ifg_dump_graph_attr, + ifg_dump_node_attr, + NULL, + NULL, + ifg_dump_at_end +}; + + + +void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags) +{ + co_ifg_dump_t cod; + + cod.co = co; + cod.flags = flags; + be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &cod); +} + void co_solve_park_moon(copy_opt_t *opt) { } + +static int void_algo(copy_opt_t *co) +{ + return 0; +} + +/* + _ _ _ _ _ + / \ | | __ _ ___ _ __(_) |_| |__ _ __ ___ ___ + / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \/ __| + / ___ \| | (_| | (_) | | | | |_| | | | | | | | \__ \ + /_/ \_\_|\__, |\___/|_| |_|\__|_| |_|_| |_| |_|___/ + |___/ +*/ + +static co_algo_t *algos[] = { + void_algo, + co_solve_heuristic, + co_solve_heuristic_new, + co_solve_heuristic_java, +#ifdef WITH_ILP + co_solve_ilp2 +#endif +}; + +/* + __ __ _ ____ _ + | \/ | __ _(_)_ __ | _ \ _ __(_)_ _____ _ __ + | |\/| |/ _` | | '_ \ | | | | '__| \ \ / / _ \ '__| + | | | | (_| | | | | | | |_| | | | |\ V / __/ | + |_| |_|\__,_|_|_| |_| |____/|_| |_| \_/ \___|_| + +*/ + +void co_driver(be_chordal_env_t *cenv) +{ + copy_opt_t *co; + co_algo_t *algo_func; + int init_costs; + + 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); + init_costs = co_get_copy_costs(co); + + /* 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); + } + + algo_func = algos[algo]; + algo_func(co); + + if(dump_flags & DUMP_AFTER) { + FILE *f = be_chordal_open(cenv, "", "-after.dot"); + co_dump_ifg_dot(co, f, style_flags); + fclose(f); + } + + if(do_stats) { + int optimizable_costs = co_get_max_copy_costs(co) - co_get_lower_bound(co); + int remaining = co_get_copy_costs(co); + int evitable = remaining - co_get_lower_bound(co); + + ir_printf("%30F %10s %10d%10d%10d%10d", cenv->irg, cenv->cls->name, + co_get_max_copy_costs(co), init_costs, + co_get_inevit_copy_costs(co), co_get_lower_bound(co)); + + if(optimizable_costs > 0) + printf("%10d %5.2f\n", remaining, (evitable * 100.0) / optimizable_costs); + else + printf("%10d %5s\n", remaining, "-"); + } + + co_free_graph_structure(co); + co_free_ou_structure(co); + free_copy_opt(co); +}