X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=7dc890e0018b603fbf6aa773197223147128d314;hb=2176caea24ef5a9786dc4ada2bd2eaf74ad88b4d;hp=780974af4d6cc6073bb0777e6f36eff541e4e970;hpb=48f893878b07f6e334389ff52abda5cc2adbf179;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index 780974af4..7dc890e00 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -1,18 +1,35 @@ +/* + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ /** - * 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 -#ifdef WITH_LIBCORE #include #include -#endif /* WITH_LIBCORE */ #include #include @@ -20,6 +37,7 @@ #include "list.h" #include "pdeq.h" #include "bitset.h" +#include "raw_bitset.h" #include "debug.h" #include "bitfiddle.h" @@ -30,25 +48,25 @@ #include "irprintf.h" #include "irtools.h" +#include "bemodule.h" #include "beabi.h" #include "benode_t.h" #include "becopyopt.h" #include "becopyopt_t.h" #include "bechordal_t.h" +#include "beirg_t.h" #define DUMP_BEFORE 1 #define DUMP_AFTER 2 #define DUMP_CLOUD 4 #define DUMP_ALL 2 * DUMP_CLOUD - 1 -static int dump_flags = 0; -static int subtree_iter = 4; -static int max_depth = 20; -static double constr_factor = 0.9; +static unsigned dump_flags = 0; +static int subtree_iter = 4; +static int max_depth = 20; +static double constr_factor = 0.9; /* Options using libcore */ -#ifdef WITH_LIBCORE - static const lc_opt_enum_mask_items_t dump_items[] = { { "before", DUMP_BEFORE }, { "after", DUMP_AFTER }, @@ -62,19 +80,24 @@ static lc_opt_enum_mask_var_t dump_var = { }; static const lc_opt_table_entry_t options[] = { - LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var), - LC_OPT_ENT_INT ("iter", "iterations for subtree nodes (standard: 3)", &subtree_iter), + LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var), + 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 (default 20)", &max_depth), - { NULL } + LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth), + LC_OPT_LAST }; -void be_co2_register_options(lc_opt_entry_t *grp) +void be_init_copyheur2(void) { - lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2"); + 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); } -#endif + +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2); /* ____ _ _ @@ -101,7 +124,7 @@ typedef struct { } col_cost_pair_t; typedef struct { - phase_t ph; + ir_phase ph; copy_opt_t *co; bitset_t *ignore_regs; co2_irn_t *touched; @@ -172,7 +195,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(phase_t *ph, ir_node *irn, void *data) +static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data) { co2_t *env = (co2_t *) ph; affinity_node_t *a = get_affinity_info(env->co, irn); @@ -200,8 +223,8 @@ static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data) static int cmp_clouds_gt(const void *a, const void *b) { - const co2_cloud_t **p = a; - const co2_cloud_t **q = b; + const co2_cloud_t * const *p = a; + const co2_cloud_t * const *q = b; double c = CLOUD_WEIGHT(*p); double d = CLOUD_WEIGHT(*q); return QSORT_CMP(d, c); @@ -241,15 +264,21 @@ static INLINE int color_is_fix(co2_t *env, ir_node *irn) static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci) { - if(!ci->adm_cache) { - arch_register_req_t req; + if(ci->adm_cache == NULL) { + const arch_register_req_t *req; ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs); - arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0)); - if(arch_register_req_is(&req, limited)) { - req.limited(req.limited_env, ci->adm_cache); + req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0)); + + if(arch_register_req_is(req, limited)) { + int i, n; + + n = env->n_regs; + for(i = 0; i < n; ++i) { + if(rbitset_is_set(req->limited, i)) + bitset_set(ci->adm_cache, i); + } ci->is_constrained = 1; - } - else { + } else { bitset_copy(ci->adm_cache, env->ignore_regs); bitset_flip_all(ci->adm_cache); } @@ -279,19 +308,20 @@ static INLINE int is_constrained(co2_t *env, co2_irn_t *ci) static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs) { - bitset_t *aux = bitset_alloca(env->co->cls->n_regs); - arch_register_req_t req; + const arch_register_req_t *req; - arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0)); + req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0)); - if(arch_register_req_is(&req, limited)) { - bitset_pos_t elm; - int n_constr; + if (arch_register_req_is(req, limited)) { + unsigned n_regs = env->co->cls->n_regs; + unsigned n_constr = 0; + unsigned i; - req.limited(req.limited_env, aux); - n_constr = bitset_popcnt(aux); - bitset_foreach(aux, elm) { - col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr); + n_constr = rbitset_popcnt(req->limited, n_regs); + for (i = 0; i < n_regs; ++i) { + if (rbitset_is_set(req->limited, i)) { + col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr); + } } } } @@ -403,7 +433,6 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l be_ifg_t *ifg = env->co->cenv->ifg; co2_irn_t *ci = get_co2_irn(env, irn); int res = 0; - int n_aff = 0; int i; @@ -673,7 +702,7 @@ 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])); 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; @@ -703,7 +732,6 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth) INIT_LIST_HEAD(&changed); for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) { col_t col = seq[i].col; - int costs = seq[i].costs; int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0; int subtree_costs, sum_costs; @@ -867,7 +895,6 @@ static void process_cloud(co2_cloud_t *cloud) int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0])); pdeq *q; - struct list_head changed; edge_t *edges; int i; int best_col; @@ -956,7 +983,7 @@ static void process_cloud(co2_cloud_t *cloud) DBG((env->dbg, LEVEL_3, "mst:\n")); for(i = 0; i < cloud->n_memb; ++i) { - co2_cloud_irn_t *ci = cloud->seq[i]; + DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]); DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn)); } @@ -1030,7 +1057,7 @@ static void process(co2_t *env) co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); if(!ci->cloud) { - co2_cloud_t *cloud = new_cloud(env, a); + new_cloud(env, a); n_clouds++; } } @@ -1056,7 +1083,8 @@ static void process(co2_t *env) FILE *f; ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i); - if(f = fopen(buf, "wt")) { + f = fopen(buf, "wt"); + if(f != NULL) { be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env); fclose(f); } @@ -1089,7 +1117,7 @@ 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[] = { "blue", @@ -1125,15 +1153,15 @@ 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) { - arch_register_req_t req; + const arch_register_req_t *req; - arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0)); - if(arch_register_req_is(&req, limited)) + req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0)); + if(arch_register_req_is(req, limited)) return "diamond"; if(ci->fixed) @@ -1147,6 +1175,7 @@ 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"); } @@ -1170,7 +1199,7 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) peri = 2; if(cci->cloud && cci->cloud->mst_root) - snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn); + ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn); } ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri, @@ -1220,13 +1249,13 @@ static be_ifg_dump_dot_cb_t ifg_dot_cb = { }; -void co_solve_heuristic_new(copy_opt_t *co) +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); + phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL); env.touched = NULL; env.visited = 0; env.co = co; @@ -1240,7 +1269,8 @@ void co_solve_heuristic_new(copy_opt_t *co) if(dump_flags & DUMP_BEFORE) { ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name); - if(f = fopen(buf, "wt")) { + f = fopen(buf, "wt"); + if (f != NULL) { be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); fclose(f); } @@ -1250,7 +1280,8 @@ void co_solve_heuristic_new(copy_opt_t *co) if(dump_flags & DUMP_AFTER) { ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name); - if(f = fopen(buf, "wt")) { + f = fopen(buf, "wt"); + if (f != NULL) { be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); fclose(f); } @@ -1258,4 +1289,5 @@ void co_solve_heuristic_new(copy_opt_t *co) writeback_colors(&env); phase_free(&env.ph); + return 0; }