X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=bad56eb10c14665e56e46e8b595e6f4d1603d33e;hb=39cb52264857d7c21c7141ba82bb55adaa78064d;hp=a500d92f30eb41876a5d45964d983691eff4344a;hpb=4d5c3365a58cba59993045a9e08e686d8ae079a7;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index a500d92f3..bad56eb10 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -18,16 +18,16 @@ */ /** - * More experiments on coalescing. - * @author Sebastian Hack - * @date 14.04.2006 + * @file + * @brief More experiments on coalescing. + * @author Sebastian Hack + * @date 14.04.2006 + * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif -#include -#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #include #include @@ -48,10 +48,11 @@ #include "bemodule.h" #include "beabi.h" -#include "benode_t.h" +#include "benode.h" #include "becopyopt.h" #include "becopyopt_t.h" #include "bechordal_t.h" +#include "beirg.h" #define DUMP_BEFORE 1 #define DUMP_AFTER 2 @@ -63,7 +64,6 @@ static int subtree_iter = 4; static int max_depth = 20; static double constr_factor = 0.9; -/* Options using libcore */ static const lc_opt_enum_mask_items_t dump_items[] = { { "before", DUMP_BEFORE }, { "after", DUMP_AFTER }, @@ -81,21 +81,9 @@ static const lc_opt_table_entry_t options[] = { LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter), LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor), LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth), - { NULL } + LC_OPT_LAST }; -void be_init_copyheur2(void) -{ - lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); - lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra"); - lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal"); - lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2"); - - lc_opt_add_table(co2_grp, options); -} - -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2); - /* ____ _ _ / ___|| |_ __ _ _ __| |_ @@ -132,7 +120,7 @@ typedef struct { } co2_t; struct _co2_irn_t { - ir_node *irn; + const ir_node *irn; affinity_node_t *aff; co2_irn_t *touched_next; col_t tmp_col; @@ -192,7 +180,7 @@ typedef struct { #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn)) -static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data) +static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data) { co2_t *env = (co2_t *) ph; affinity_node_t *a = get_affinity_info(env->co, irn); @@ -202,7 +190,7 @@ static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data) memset(ci, 0, size); INIT_LIST_HEAD(&ci->changed_list); ci->touched_next = env->touched; - ci->orig_col = get_irn_col(env->co, irn); + ci->orig_col = get_irn_col(irn); env->touched = ci; ci->irn = irn; ci->aff = a; @@ -247,24 +235,24 @@ int cmp_edges(const void *a, const void *b) return QSORT_CMP(q->costs, p->costs); } -static col_t get_col(co2_t *env, ir_node *irn) +static col_t get_col(co2_t *env, const ir_node *irn) { co2_irn_t *ci = get_co2_irn(env, irn); return ci->tmp_fixed ? ci->tmp_col : ci->orig_col; } -static INLINE int color_is_fix(co2_t *env, ir_node *irn) +static inline int color_is_fix(co2_t *env, const ir_node *irn) { co2_irn_t *ci = get_co2_irn(env, irn); return ci->fixed || ci->tmp_fixed; } -static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci) +static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci) { if(ci->adm_cache == NULL) { const arch_register_req_t *req; ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs); - req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0)); + req = arch_get_register_req_out(ci->irn); if(arch_register_req_is(req, limited)) { int i, n; @@ -284,30 +272,28 @@ static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci) return ci->adm_cache; } -static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs) +static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs) { bitset_copy(bs, get_adm(env, ci)); return bs; } -static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col) +static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col) { bitset_t *bs = get_adm(env, ci); return bitset_is_set(bs, col); } -static INLINE int is_constrained(co2_t *env, co2_irn_t *ci) +static inline int is_constrained(co2_t *env, co2_irn_t *ci) { if(!ci->adm_cache) get_adm(env, ci); return ci->is_constrained; } -static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs) +static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs) { - const arch_register_req_t *req; - - req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0)); + const arch_register_req_t *req = arch_get_register_req_out(irn); if (arch_register_req_is(req, limited)) { unsigned n_regs = env->co->cls->n_regs; @@ -335,14 +321,14 @@ static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *co */ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs) { - ir_node *irn = ci->irn; + const ir_node *irn = ci->irn; be_ifg_t *ifg = env->co->cenv->ifg; int n_regs = env->co->cls->n_regs; bitset_t *forb = bitset_alloca(n_regs); affinity_node_t *a = ci->aff; bitset_pos_t elm; - ir_node *pos; + const ir_node *pos; void *it; int i; @@ -398,6 +384,7 @@ static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pai seq[i].costs = INT_MAX; } + (void) ci; assert(is_color_admissible(env, ci, col)); seq[col].col = 0; seq[0].col = col; @@ -422,9 +409,9 @@ static void materialize_coloring(struct list_head *h) } } -static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth); +static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth); -static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth) +static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth) { int n_regs = env->co->cls->n_regs; be_ifg_t *ifg = env->co->cenv->ifg; @@ -442,7 +429,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l int neigh_ok = 1; struct list_head changed; - ir_node *n; + const ir_node *n; void *it; DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn)); @@ -509,7 +496,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l return res; } -static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth) +static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth) { co2_irn_t *ci = get_co2_irn(env, irn); int res = 0; @@ -531,7 +518,7 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list /* The node has the color it should not have _and_ has not been visited yet. */ if(!color_is_fix(env, irn)) { int n_regs = env->co->cls->n_regs; - col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0])); + col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs); /* Get the costs for giving the node a specific color. */ determine_color_costs(env, ci, csts); @@ -550,7 +537,7 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list return res; } -static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth) +static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth) { co2_irn_t *ci = get_co2_irn(env, irn); col_t col = get_col(env, irn); @@ -572,7 +559,7 @@ static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct l if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) { int n_regs = env->co->cls->n_regs; - col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0])); + col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs); /* Get the costs for giving the node a specific color. */ single_color_cost(env, ci, tgt_col, seq); @@ -628,7 +615,7 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) bitset_t *bs = bitset_alloca(n_regs); bitset_pos_t elm; - ir_node *irn; + const ir_node *irn; void *it; admissible_colors(env, &ci->inh, bs); @@ -697,9 +684,9 @@ static void unfix_subtree(co2_cloud_irn_t *ci) static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth) { co2_t *env = ci->cloud->env; - col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0])); + col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs); int is_root = ci->mst_parent == ci; - col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn); + col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn); int min_badness = INT_MAX; int best_col_costs = INT_MAX; int best_col = -1; @@ -859,7 +846,7 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth) { - ir_node *irn = ci->inh.irn; + const ir_node *irn = ci->inh.irn; int *front = FRONT_BASE(ci, col); int i, ok; struct list_head changed; @@ -889,15 +876,13 @@ static void process_cloud(co2_cloud_t *cloud) co2_t *env = cloud->env; int n_regs = env->n_regs; int n_edges = 0; - int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0])); + int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb); pdeq *q; edge_t *edges; int i; int best_col; - memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0])); - /* Collect all edges in the cloud on an obstack and sort the increasingly */ obstack_init(&cloud->obst); for(i = 0; i < cloud->n_memb; ++i) { @@ -989,18 +974,13 @@ static void process_cloud(co2_cloud_t *cloud) int n_childs = ci->mst_n_childs; int j; - ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0])); - ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0])); - ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0])); - ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0])); - memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0])); - memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0])); - memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0])); - memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0])); + ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs); + ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs); + ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs); + ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs); for(j = 0; j < env->n_regs; j++) ci->col_costs[j] = INT_MAX; - } determine_color_badness(cloud->mst_root, 0); @@ -1060,7 +1040,7 @@ static void process(co2_t *env) } i = 0; - clouds = xmalloc(n_clouds * sizeof(clouds[0])); + clouds = XMALLOCN(co2_cloud_t*, n_clouds); list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) clouds[i++] = pos; qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt); @@ -1095,12 +1075,11 @@ static void process(co2_t *env) static void writeback_colors(co2_t *env) { - const arch_env_t *aenv = env->co->aenv; co2_irn_t *irn; for(irn = env->touched; irn; irn = irn->touched_next) { const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col); - arch_set_irn_register(aenv, irn->irn, reg); + arch_set_irn_register((ir_node*)irn->irn, reg); } } @@ -1114,9 +1093,9 @@ static void writeback_colors(co2_t *env) |_| |___/ */ -static const char *get_dot_color_name(int col) +static const char *get_dot_color_name(size_t col) { - static const char *names[] = { + static const char *const names[] = { "blue", "red", "green", @@ -1150,14 +1129,13 @@ static const char *get_dot_color_name(int col) "palevioletred" }; - return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white"; + return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white"; } -static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci) +static const char *get_dot_shape_name(co2_irn_t *ci) { - const arch_register_req_t *req; + const arch_register_req_t *req = arch_get_register_req_out(ci->irn); - req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0)); if(arch_register_req_is(req, limited)) return "diamond"; @@ -1172,13 +1150,15 @@ static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci) static void ifg_dump_graph_attr(FILE *f, void *self) { + (void) self; fprintf(f, "overlay=false"); } static int ifg_is_dump_node(void *self, ir_node *irn) { - co2_t *env = self; - return !arch_irn_is(env->co->aenv, irn, ignore); + const arch_register_req_t *req = arch_get_register_req_out(irn); + (void)self; + return !(req->type & arch_register_req_type_ignore); } static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) @@ -1199,7 +1179,7 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) } ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri, - get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci)); + get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci)); } static void ifg_dump_at_end(FILE *file, void *self) @@ -1244,12 +1224,11 @@ static be_ifg_dump_dot_cb_t ifg_dot_cb = { ifg_dump_at_end }; - int co_solve_heuristic_new(copy_opt_t *co) { - char buf[256]; + char buf[256]; co2_t env; - FILE *f; + FILE *f; phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL); env.touched = NULL; @@ -1257,9 +1236,7 @@ int co_solve_heuristic_new(copy_opt_t *co) env.co = co; env.n_regs = co->cls->n_regs; env.ignore_regs = bitset_alloca(co->cls->n_regs); - arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs); - bitset_flip_all(env.ignore_regs); - be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs); + be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs); FIRM_DBG_REGISTER(env.dbg, "firm.be.co2"); INIT_LIST_HEAD(&env.cloud_head); @@ -1287,3 +1264,20 @@ int co_solve_heuristic_new(copy_opt_t *co) phase_free(&env.ph); return 0; } + +void be_init_copyheur2(void) +{ + lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); + lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra"); + lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal"); + lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2"); + + static co_algo_info copyheur = { + co_solve_heuristic_new, 0 + }; + + lc_opt_add_table(co2_grp, options); + be_register_copyopt("heur2", ©heur); +} + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);