X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=60f8b6646cf736f51cfd89b4f7fa99a736590d1f;hb=505d3662efed6efbca2c43eea2fe23b87816b285;hp=df212f51fa1cf426afbb462d3ad3498fd19655b1;hpb=83d77a73fc9f2a6bfa9bfc55e3fbc0398b08e7b6;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index df212f51f..60f8b6646 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -1,18 +1,35 @@ +/* + * Copyright (C) 1995-2008 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 "lc_opts.h" +#include "lc_opts_enum.h" #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,28 +48,28 @@ #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 double constr_factor = 0.5; - -/* Options using libcore */ -#ifdef WITH_LIBCORE +static unsigned dump_flags = 0; +static int subtree_iter = 4; +static int max_depth = 20; +static double constr_factor = 0.9; static const lc_opt_enum_mask_items_t dump_items[] = { { "before", DUMP_BEFORE }, - { "after", DUMP_AFTER }, - { "cloud", DUMP_CLOUD }, + { "after", DUMP_AFTER }, + { "cloud", DUMP_CLOUD }, { "all", DUMP_ALL }, { NULL, 0 } }; @@ -61,18 +79,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), - { 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); /* ____ _ _ @@ -99,7 +123,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; @@ -110,7 +134,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; @@ -160,12 +184,17 @@ struct _co2_cloud_t { struct list_head list; }; +typedef struct { + co2_cloud_irn_t *src, *tgt; + int costs; +} edge_t; + #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs) #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, const ir_node *irn, void *data) { co2_t *env = (co2_t *) ph; affinity_node_t *a = get_affinity_info(env->co, irn); @@ -193,8 +222,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); @@ -213,13 +242,20 @@ static int col_cost_pair_lt(const void *a, const void *b) return QSORT_CMP(c, d); } -static col_t get_col(co2_t *env, ir_node *irn) +int cmp_edges(const void *a, const void *b) +{ + const edge_t *p = a; + const edge_t *q = b; + return QSORT_CMP(q->costs, p->costs); +} + +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; @@ -227,15 +263,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); } @@ -263,21 +305,22 @@ static INLINE int is_constrained(co2_t *env, co2_irn_t *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) { - 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); + } } } } @@ -294,14 +337,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; @@ -357,6 +400,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; @@ -381,47 +425,27 @@ static void materialize_coloring(struct list_head *h) } } -typedef struct { - co2_irn_t *ci; - col_t col; -} col_entry_t; +static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth); -static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed) -{ - co2_irn_t *pos; - col_entry_t ent; - - list_for_each_entry(co2_irn_t, pos, changed, changed_list) { - ent.ci = pos; - ent.col = pos->tmp_col; - pos->tmp_col = 0; - obstack_grow(obst, &ent, sizeof(ent)); - } - memset(&ent, 0, sizeof(ent)); - obstack_grow(obst, &ent, sizeof(ent)); - return obstack_finish(obst); -} - -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_single(co2_t *env, ir_node *irn, col_t tgt_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; co2_irn_t *ci = get_co2_irn(env, irn); int res = 0; - int n_aff = 0; int i; + if(depth >= max_depth) + return 0; + for(i = 0; i < n_regs; ++i) { col_t tgt_col = col_list[i].col; unsigned costs = col_list[i].costs; 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)); @@ -488,7 +512,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; @@ -529,7 +553,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); @@ -566,160 +590,12 @@ end: return res; } -static void front_inval_color(co2_cloud_irn_t *ci, col_t col) -{ - int *base = FRONT_BASE(ci, col); - memset(base, -1, ci->mst_n_childs * sizeof(base[0])); -} - -typedef struct { - co2_cloud_irn_t *src, *tgt; - int costs; -} edge_t; - -int cmp_edges(const void *a, const void *b) -{ - const edge_t *p = a; - const edge_t *q = b; - return QSORT_CMP(q->costs, p->costs); -} - -static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci) -{ - while(ci != ci->mst_parent) - ci = ci->mst_parent; - return ci; -} - - -static int cmp_parent(const void *a, const void *b) -{ - const co2_cloud_irn_t *p = a; - const co2_cloud_irn_t *q = b; - return QSORT_CMP(q->mst_costs, p->mst_costs); -} - -static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col) -{ - int n_regs = ci->cloud->env->n_regs; - int i, j; - - for(i = 0; i < ci->mst_n_childs; ++i) { - co2_cloud_irn_t *c = ci->mst_childs[i]; - for(j = 0; j < n_regs; ++j) { - int costs = c->col_costs[j]; - if(INFEASIBLE(costs)) - c->tmp_coloring[j].costs = INT_MAX; - else { - int add = j != (int) col ? c->mst_costs : 0; - c->tmp_coloring[j].costs = add + costs; - } - c->tmp_coloring[j].col = j; - } - qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt); - } -} - -static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq) -{ - int n_regs = ci->cloud->env->n_regs; - bitset_t *adm = bitset_alloca(n_regs); - int i, j; - - // TODO: Prefer some colors depending on the neighbors, etc. - - admissible_colors(ci->cloud->env, &ci->inh, adm); - for(i = 0; i < n_regs; ++i) { - seq[i].col = i; - - if (!bitset_is_set(adm, i)) - seq[i].costs = INT_MAX; - else { - seq[i].costs = 0; - for(j = 0; j < ci->mst_n_childs; ++j) { - co2_cloud_irn_t *child = ci->mst_childs[j]; - if (!INFEASIBLE(child->col_costs[i])) - seq[i].costs -= ci->mst_childs[j]->col_costs[i]; - } - } - } - - qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); -} - -static int push_front(co2_cloud_irn_t *ci, int *front) -{ - co2_t *env = ci->cloud->env; - int n_regs = env->n_regs; - int min_diff = INT_MAX; - int min_chld = -1; - int i; - - for(i = 0; i < ci->mst_n_childs; ++i) { - co2_cloud_irn_t *child = ci->mst_childs[i]; - int idx = front[i]; - - - if(idx + 1 < n_regs) { - int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs; - if(diff < min_diff) { - min_diff = diff; - min_chld = i; - } - } - } - - if(min_chld >= 0) { - co2_cloud_irn_t *child = ci->mst_childs[min_chld]; - DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff)); - front[min_chld] += 1; - } - - return min_chld; -} - -static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth) -{ - int n_childs = ci->mst_n_childs; - /* - select the front for the given color. - The front will determine the colors of the children. - */ - int *front = FRONT_BASE(ci, col); - int i, ok = 1; - - ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0); - for(i = 0; i < n_childs && ok; ++i) { - co2_cloud_irn_t *child = ci->mst_childs[i]; - col_t col = front[i]; - - ok = color_subtree(child, col, changed, depth + 1); - } - - return ok; -} - -static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth) -{ - co2_t *env = ci->cloud->env; - struct list_head changed; - int i, ok = 1; - - INIT_LIST_HEAD(&changed); - *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1); - - for (i = 0; i < ci->mst_n_childs && ok; ++i) { - co2_cloud_irn_t *child = ci->mst_childs[i]; - col_t tgt_col = child->tmp_coloring[front[i]].col; - - ok = color_subtree(child, tgt_col, &changed, depth + 1); - } - - reject_coloring(&changed); - - return ok; -} - +/** + * Examine the costs of the current coloring concerning a MST subtree. + * @param ci The subtree root. + * @param col The color of @p ci. + * @return The best coloring for that subtree under the assumption that @p ci has color @p col. + */ static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col) { int *front = FRONT_BASE(ci, col); @@ -737,97 +613,15 @@ static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col) return cost; } -static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth) -{ - co2_t *env = ci->cloud->env; - int n_regs = env->n_regs; - col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0])); - int *front = alloca(ci->mst_n_childs * sizeof(front[0])); - int best_col = -1; - int best_cost = INT_MAX; - - - int i; - - DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn)); - - for (i = 0; i < ci->mst_n_childs; ++i) - cloud_mst_build_colorings(ci->mst_childs[i], depth + 1); - - for (i = 0; i < n_regs; ++i) - ci->col_costs[i] = INT_MAX; - - /* Sort the children according to the cost of the affinity edge they have to the current node. */ - // qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent); - - determine_start_colors(ci, seq); - // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); - - for(i = 0; i < n_regs; ++i) { - col_t col = seq[i].col; - int costs = seq[i].costs; - int done = 0; - - if(INFEASIBLE(costs)) - break; - - /* - Judge, if it is worthwhile trying this color. - If another color was so good that we cannot get any better, bail out here. - Perhaps??? - */ - - DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col)); - - /* This sorts the tmp_coloring array in the children according to the costs of the current color. */ - fill_tmp_coloring(ci, col); - - /* Initialize the front. It gives the indexes into the color tmp_coloring array. */ - memset(front, 0, ci->mst_n_childs * sizeof(front)); - - /* - As long as we have color configurations to try. - We try the best ones first and get worse over and over. - */ - while (!done) { - int j, try_push; - - if (try_coloring(ci, col, front, &try_push, depth + 1)) { - int *res_front = FRONT_BASE(ci, col); - int costs; - - for(j = 0; j < ci->mst_n_childs; ++j) { - co2_cloud_irn_t *child = ci->mst_childs[j]; - col_t col = child->tmp_coloring[front[j]].col; - res_front[j] = col; - } - - costs = examine_subtree_coloring(ci, col); - ci->col_costs[col] = costs; - done = 1; - - /* Set the current best color. */ - if(costs < best_cost) { - best_cost = costs; - best_col = col; - } - } - - DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed")); - - /* Worsen the configuration, if that one didn't succeed. */ - if (!done) - done = try_push ? push_front(ci, front) < 0 : 1; - } - } - - DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn)); - for(i = 0; i < n_regs; ++i) - DBG((env->dbg, LEVEL_2, "%2{firm:indent} color %d costs %d\n", depth, i, ci->col_costs[i])); - - return best_col; -} - +/** + * Determine color badnesses of a node. + * Badness means that it is unlikely that the node in question can + * obtain a color. The higher the badness, the more unlikely it is that + * the node can be assigned that color. + * @param ci The node. + * @param badness An integer array as long as there are registers. + * @note The array badness is not cleared. + */ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) { co2_t *env = ci->cloud->env; @@ -837,7 +631,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); @@ -862,19 +656,15 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness) } } be_ifg_neighbours_break(ifg, it); - -} - -static int cloud_color_badness(co2_cloud_t *cloud) -{ - int *badness = alloca(cloud->env->n_regs * sizeof(badness[0])); - int i; - - memset(badness, 0, cloud->env->n_regs * sizeof(badness[0])); - for(i = 0; i < cloud->n_memb; ++i) - node_color_badness(cloud->seq[i], badness); } +/** + * Determine the badness of a MST subtree. + * The badness is written into the color_badness array of each node and accumulated in the parents. + * @see node_color_badness() for a definition of badness. + * @param ci The root of the subtree. + * @param depth Depth for debugging purposes. + */ static void determine_color_badness(co2_cloud_irn_t *ci, int depth) { co2_t *env = ci->cloud->env; @@ -895,6 +685,9 @@ static void determine_color_badness(co2_cloud_irn_t *ci, int depth) DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j])); } +/** + * Unfix all nodes in a MST subtree. + */ static void unfix_subtree(co2_cloud_irn_t *ci) { int i; @@ -909,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; @@ -939,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; @@ -982,14 +774,6 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth) if(sum_costs == 0) break; - - /* If we are at the root and we achieved an acceptable amount of optimization, we finish. */ -#if 0 - if(is_root && (ci->cloud->inevit * stop_percentage < ci->cloud->inevit - sum_costs)) { - assert(best_col != -1); - break; - } -#endif } if(!is_root) { @@ -1063,9 +847,6 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) populate_cloud(env, cloud, a, 0); cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom; - /* Allocate space for the best colors array, where the best coloring is saved. */ - // cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0])); - /* Also allocate space for the node sequence and compute that sequence. */ cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0])); @@ -1081,7 +862,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; @@ -1090,7 +871,7 @@ static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth) DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col)); ok = change_color_single(ci->cloud->env, irn, col, &changed, depth); - assert(ok && "Color changing may not fail while committing the coloring"); + // assert(ok && "Color changing may not fail while committing the coloring"); materialize_coloring(&changed); for(i = 0; i < ci->mst_n_childs; ++i) { @@ -1098,15 +879,22 @@ static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth) } } +static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci) +{ + while(ci != ci->mst_parent) + ci = ci->mst_parent; + return ci; +} + + 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 = malloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0])); + 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; @@ -1195,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)); } @@ -1269,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++; } } @@ -1282,7 +1070,10 @@ static void process(co2_t *env) for(i = 0; i < n_clouds; ++i) { init_costs += cloud_costs(clouds[i]); + + /* Process the cloud. */ process_cloud(clouds[i]); + all_costs += clouds[i]->costs; final_costs += cloud_costs(clouds[i]); @@ -1292,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); } @@ -1311,7 +1103,7 @@ static void writeback_colors(co2_t *env) 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(aenv, (ir_node *) irn->irn, reg); } } @@ -1325,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", @@ -1361,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) @@ -1383,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"); } @@ -1406,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, @@ -1418,19 +1211,6 @@ static void ifg_dump_at_end(FILE *file, void *self) co2_t *env = self; affinity_node_t *a; -#if 0 - co2_cloud_t *pos; - - list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) { - int i; - - for(i = 0; i < pos->n_memb - 1; ++i) { - fprintf(file, "\tn%d -- n%d [style=dotted color=green];\n", get_irn_idx(pos->seq[i]->inh.irn), get_irn_idx(pos->seq[i+1]->inh.irn)); - } - } -#endif - - co_gs_foreach_aff_node(env->co, a) { co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn); int idx = get_irn_idx(a->irn); @@ -1469,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; @@ -1489,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); } @@ -1499,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); } @@ -1507,4 +1289,5 @@ void co_solve_heuristic_new(copy_opt_t *co) writeback_colors(&env); phase_free(&env.ph); + return 0; }