X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=d27f7bdaba019482d85bb6318f6c574b3b0cce25;hb=ed73d993f7df08a4e968e86e97224283ea781c64;hp=0fba13d27bdf534dbad909f987779a24f03cf0a0;hpb=dd7574b350e321b7d0531ed878ed5f79cbf8bf72;p=libfirm diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c index 0fba13d27..d27f7bdab 100644 --- a/ir/be/becopyheur2.c +++ b/ir/be/becopyheur2.c @@ -5,18 +5,30 @@ * @date 14.04.2006 */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef WITH_LIBCORE +#include +#include +#endif /* WITH_LIBCORE */ + #include #include #include "list.h" #include "pdeq.h" #include "bitset.h" + #include "debug.h" +#include "bitfiddle.h" #include "irphase_t.h" #include "irgraph_t.h" #include "irnode_t.h" #include "irprintf.h" +#include "irtools.h" #include "beabi.h" #include "benode_t.h" @@ -24,102 +36,157 @@ #include "becopyopt_t.h" #include "bechordal_t.h" -#define INFEASIBLE(col) ((col) > (INT_MAX - 10)) +#define DUMP_BEFORE 1 +#define DUMP_AFTER 2 +#define DUMP_CLOUD 4 + +static int dump_flags = 0; + +/* Options using libcore */ +#ifdef WITH_LIBCORE + +static const lc_opt_enum_mask_items_t dump_items[] = { + { "before", DUMP_BEFORE }, + { "after", DUMP_AFTER }, + { "cloud", DUMP_CLOUD }, + { "all", 2 * DUMP_CLOUD - 1 }, + { NULL, 0 } +}; + +static lc_opt_enum_mask_var_t dump_var = { + &dump_flags, dump_items +}; + +static const lc_opt_table_entry_t options[] = { + LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var), + { NULL } +}; + +void be_co2_register_options(lc_opt_entry_t *grp) +{ + lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2"); + lc_opt_add_table(co2_grp, options); +} +#endif + +/* + ____ _ _ + / ___|| |_ __ _ _ __| |_ + \___ \| __/ _` | '__| __| + ___) | || (_| | | | |_ + |____/ \__\__,_|_| \__| + +*/ + +#define INFEASIBLE(cost) ((cost) == INT_MAX) + +static be_ifg_dump_dot_cb_t ifg_dot_cb; typedef unsigned col_t; -typedef struct _co2_irn_t co2_irn_t; -typedef struct _co2_cloud_t co2_cloud_t; +typedef struct _co2_irn_t co2_irn_t; +typedef struct _co2_cloud_t co2_cloud_t; +typedef struct _co2_cloud_irn_t co2_cloud_irn_t; + +typedef struct { + col_t col; + int costs; +} col_cost_pair_t; typedef struct { - phase_t ph; + phase_t ph; copy_opt_t *co; - bitset_t *ignore_regs; - co2_irn_t *touched; - int visited; + bitset_t *ignore_regs; + co2_irn_t *touched; + int visited; + int n_regs; + struct list_head cloud_head; DEBUG_ONLY(firm_dbg_module_t *dbg;) } co2_t; struct _co2_irn_t { ir_node *irn; - co2_cloud_t *cloud; - co2_irn_t *touched_next; affinity_node_t *aff; - int costs; + co2_irn_t *touched_next; col_t tmp_col; col_t orig_col; - int visited; - int rank; + int last_color_change; unsigned fixed : 1; unsigned tmp_fixed : 1; struct list_head changed_list; - struct list_head cloud_list; }; -struct _co2_cloud_t { - int costs; - int inevit; - int best_costs; - int n_memb; - int max_degree; - co2_irn_t *master; - co2_irn_t **seq; - col_t *best_cols; - struct list_head members_head; - struct list_head list; +struct _co2_cloud_irn_t { + struct _co2_irn_t inh; + co2_cloud_t *cloud; + int visited; + int index; + co2_cloud_irn_t *mst_parent; + int mst_costs; + int mst_n_childs; + co2_cloud_irn_t **mst_childs; + int *col_costs; + int costs; + int *fronts; + col_cost_pair_t *tmp_coloring; + struct list_head cloud_list; + struct list_head mst_list; }; -#define NEIGHBOR_FIXED 1 -#define NEIGHBOR_CONSTR 2 -#define SELF_CONSTR 4 -#define DONT_WANT 8 +struct _co2_cloud_t { + co2_t *env; + struct obstack obst; + int costs; + int mst_costs; + int inevit; + int best_costs; + int n_memb; + int max_degree; + int ticks; + co2_cloud_irn_t *master; + co2_cloud_irn_t *mst_root; + co2_cloud_irn_t **seq; + struct list_head members_head; + struct list_head list; +}; -typedef struct { - col_t col; - int costs; - unsigned flags; -} col_cost_pair_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_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, const ir_node *irn, void *data) +static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data) { - co2_t *env = (co2_t *) ph; - co2_irn_t *ci = data; + co2_t *env = (co2_t *) ph; + affinity_node_t *a = get_affinity_info(env->co, irn); + size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t); + co2_irn_t *ci = data ? data : phase_alloc(ph, size); - memset(ci, 0, sizeof(ci[0])); + memset(ci, 0, size); INIT_LIST_HEAD(&ci->changed_list); - INIT_LIST_HEAD(&ci->cloud_list); - ci->irn = irn; ci->touched_next = env->touched; ci->orig_col = get_irn_col(env->co, irn); - ci->aff = get_affinity_info(env->co, irn); env->touched = ci; -} + ci->irn = irn; + ci->aff = a; + if(a) { + co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci; + INIT_LIST_HEAD(&cci->cloud_list); + cci->mst_parent = cci; + } -static int co2_irn_cmp(const void *a, const void *b) -{ - const co2_irn_t **p = a; - const co2_irn_t **q = b; - return (*q)->costs - (*p)->costs; + return ci; } -static int cmp_clouds(const void *a, const void *b) + +static int cmp_clouds_gt(const void *a, const void *b) { const co2_cloud_t **p = a; const co2_cloud_t **q = b; - return (*q)->costs - (*p)->costs; -} - -static co2_cloud_t *new_cloud(co2_t *env) -{ - co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0])); - memset(cloud, 0, sizeof(cloud[0])); - INIT_LIST_HEAD(&cloud->members_head); - INIT_LIST_HEAD(&cloud->list); - cloud->best_costs = INT_MAX; - return cloud; + int c = (*p)->costs; + int d = (*q)->costs; + return CMP(d, c); } /** @@ -132,25 +199,7 @@ static int col_cost_pair_lt(const void *a, const void *b) const col_cost_pair_t *q = b; int c = p->costs; int d = q->costs; - - if(c > d) - return 1; - if(c < d) - return -1; - - return 0; -} - -const char *flag_str(unsigned int fl) -{ - static char buf[10]; - - buf[0] = fl & NEIGHBOR_CONSTR ? 'c' : '-'; - buf[1] = fl & NEIGHBOR_FIXED ? 'n' : '-'; - buf[2] = fl & SELF_CONSTR ? 'C' : '-'; - buf[3] = fl & DONT_WANT ? 'd' : '-'; - buf[4] = '\0'; - return buf; + return CMP(c, d); } static col_t get_col(co2_t *env, ir_node *irn) @@ -201,8 +250,7 @@ static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *co req.limited(req.limited_env, aux); n_constr = bitset_popcnt(aux); bitset_foreach(aux, elm) { - col_costs[elm].costs += costs / n_constr; - col_costs[elm].flags |= NEIGHBOR_CONSTR; + col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr); } } } @@ -230,10 +278,6 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co void *it; int i; - if(get_irn_node_nr(irn) == 2040) { - printf("Hallo"); - } - /* Put all forbidden colors into the aux bitset. */ admissible_colors(env, ci, forb); bitset_flip_all(forb); @@ -241,7 +285,6 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co for(i = 0; i < n_regs; ++i) { col_costs[i].col = i; col_costs[i].costs = 0; - col_costs[i].flags = 0; } if(a) { @@ -250,7 +293,7 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co co_gs_foreach_neighb(a, n) { if(color_is_fix(env, n->irn)) { col_t col = get_col(env, n->irn); - col_costs[col].costs -= 100 * n->costs; + col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128); } incur_constraint_costs(env, n->irn, col_costs, -n->costs); @@ -262,18 +305,16 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co col_t col = get_col(env, pos); if(color_is_fix(env, pos)) { col_costs[col].costs = INT_MAX; - col_costs[col].flags |= NEIGHBOR_FIXED; } else { incur_constraint_costs(env, pos, col_costs, INT_MAX); - col_costs[col].costs += 10 * be_ifg_degree(ifg, pos); + col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos)); } } /* Set the costs to infinity for each color which is not allowed at this node. */ bitset_foreach(forb, elm) { col_costs[elm].costs = INT_MAX; - col_costs[elm].flags |= SELF_CONSTR; } } @@ -286,41 +327,11 @@ static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq) for(i = 0; i < n_regs; ++i) { seq[i].col = i; seq[i].costs = INT_MAX; - seq[i].flags = 0; - seq[i].flags = DONT_WANT; } seq[col].col = 0; seq[0].col = col; seq[0].costs = 0; - seq[0].flags = 0; -} - -static int curr_costs(co2_t *env, affinity_node_t *a) -{ - col_t a_col = get_col(env, a->irn); - int costs = 0; - neighb_t *n; - - co_gs_foreach_neighb(a, n) { - col_t n_col = get_col(env, n->irn); - costs += n_col != a_col ? n->costs : 0; - } - - return costs; -} - -static int cloud_costs(co2_t *env, co2_cloud_t *cloud) -{ - int costs = 0; - co2_irn_t *ci; - - list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) { - affinity_node_t *a = get_affinity_info(env->co, ci->irn); - costs += curr_costs(env, a); - } - - return costs; } static void reject_coloring(struct list_head *h) @@ -336,7 +347,7 @@ static void materialize_coloring(struct list_head *h) co2_irn_t *pos; list_for_each_entry(co2_irn_t, pos, h, changed_list) { - pos->orig_col = pos->tmp_col; + pos->orig_col = pos->tmp_col; pos->tmp_fixed = 0; } } @@ -384,18 +395,18 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l ir_node *n; void *it; - DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying color %d(%d) on %+F\n", depth, tgt_col, costs, irn)); + DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn)); /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */ if(INFEASIBLE(costs)) { - DB((env->dbg, LEVEL_4, "\t\t%2Ncolor %d infeasible due to %s\n", depth, tgt_col, flag_str(col_list[i].flags))); + DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col)); ci->tmp_fixed = 0; return 0; } /* Set the new color of the node and mark the node as temporarily fixed. */ - ci->tmp_col = tgt_col; - ci->tmp_fixed = 1; + ci->tmp_col = tgt_col; + ci->tmp_fixed = 1; /* If that color has costs > 0, there's at least one neighbor having that color, @@ -430,7 +441,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l of the current node, every thing was ok and we can return safely. */ if(neigh_ok) { - DBG((env->dbg, LEVEL_3, "\t\t%2Ncolor %d(%d) was ok\n", depth, tgt_col, costs)); + DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs)); list_splice(&changed, parent_changed); res = 1; break; @@ -453,13 +464,13 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list int res = 0; col_t col = get_col(env, irn); - DBG((env->dbg, LEVEL_3, "\t\t%2Nclearing %+F(%d) of color %d\n", depth, irn, col, not_col)); + DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col)); /* the node does not have to forbidden color. That's fine, mark it as visited and return. */ if(col != not_col) { if(!ci->tmp_fixed) { - ci->tmp_col = col; - ci->tmp_fixed = 1; + ci->tmp_col = col; + ci->tmp_fixed = 1; } list_add(&ci->changed_list, parent_changed); @@ -494,25 +505,21 @@ static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct l col_t col = get_col(env, irn); int res = 0; - DBG((env->dbg, LEVEL_3, "\t\t%2Ntrying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col)); - - /* If the color is already fix, bail out. */ - if(color_is_fix(env, irn)) - return 0; + DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col)); /* the node has the wanted color. That's fine, mark it as visited and return. */ if(col == tgt_col) { if(!ci->tmp_fixed) { - ci->tmp_col = col; - ci->tmp_fixed = 1; + ci->tmp_col = col; + ci->tmp_fixed = 1; + list_add(&ci->changed_list, parent_changed); } - list_add(&ci->changed_list, parent_changed); - DB((env->dbg, LEVEL_3, "\t\tok\n")); + DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}ok\n", depth)); return 1; } - else { + if(!color_is_fix(env, irn)) { int n_regs = env->co->cls->n_regs; col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0])); @@ -522,373 +529,280 @@ static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct l /* Try recoloring the node using the color list. */ res = recolor(env, irn, seq, parent_changed, depth); - DB((env->dbg, LEVEL_3, "\t\tcolor %d %s for %+F\n", tgt_col, res ? "was ok" : "failed", irn)); + DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn)); } return res; } - -#if 0 -static void try_color(co2_t *env, co2_irn_t *ci, col_t col, struct list_head *parent_changed) +static void front_inval_color(co2_cloud_irn_t *ci, col_t col) { - be_ifg_t *ifg = env->co->cenv->ifg; - int n_regs = env->co->cls->n_regs; - col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0])); - affinity_node_t *a = get_affinity_info(env->co, ci->irn); - co2_irn_t **nbs = alloca(a->degree * sizeof(nbs[0])); - int ok = 0; - - col_t new_col; - neighb_t *n; - - assert(a != NULL && "This node must be an affinity node"); + int *base = FRONT_BASE(ci, col); + memset(base, -1, ci->mst_n_childs * sizeof(base[0])); +} - /* If that node has already been fixed, leave it alone. */ - if(color_is_fix(env, ci->irn) || !is_color_admissible(env, ci, col)) { - // DB((env->dbg, LEVEL_2, "\t-> color is already fix: %d\n", get_col(env, ci->irn))); - return; - } +typedef struct { + co2_cloud_irn_t *src, *tgt; + int costs; +} edge_t; - DB((env->dbg, LEVEL_1, "\taffinity node %+F cost %d trying color %d\n", ci->irn, ci->costs, col)); +int cmp_edges(const void *a, const void *b) +{ + const edge_t *p = a; + const edge_t *q = b; + return CMP(p->costs, q->costs); +} - single_color_cost(env, col, col_seq); - recolor(env, ci->irn, col_seq, parent_changed, 0); - new_col = get_col(env, ci->irn); +static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci) +{ + while(ci->mst_parent != ci->mst_parent) + ci = ci->mst_parent; + return ci; +} - ci->tmp_fixed = 1; - ci->tmp_col = new_col; - DB((env->dbg, LEVEL_2, "\t-> has color %d now. %d wanted\n", new_col, col)); +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 CMP(q->mst_costs, p->mst_costs); +} - i = 0; - co_gs_foreach_neighb(a, n) - nbs[i++] = get_co2_irn(env, n->irn); +static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col) +{ + int n_regs = ci->cloud->env->n_regs; + int i, j; - co_gs_foreach_neighb(a, n) { - co2_irn_t *ni = get_co2_irn(env, n->irn); - col_t tgt_col = be_ifg_connected(ifg, ci->irn, ni->irn) ? get_col(env, ni->irn) : new_col; - try_color(env, ni, tgt_col, parent_changed); + 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 process_cloud(co2_t *env, co2_cloud_t *cloud) +static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq) { - int n_regs = env->co->cls->n_regs; - col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0])); - int best_costs = cloud_costs(env, cloud); - int best_col = 0; + int n_regs = ci->cloud->env->n_regs; + bitset_t *adm = bitset_alloca(n_regs); + int i, j; - struct list_head changed; - co2_irn_t *ci; - int i; + // 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; - i = 0; - DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn)); - list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) { - DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs)); + 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]; + } + } } - determine_color_costs(env, cloud->master, cols); - qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt); - - best_col = cols[0].col; - for(i = 0; i < n_regs; ++i) { - col_t col = cols[i].col; - int reject = 1; - int costs; + qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); +} - INIT_LIST_HEAD(&changed); - DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs)); +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; - /* try to recolor all the cloud members. */ - try_color(env, cloud->master, col, &changed); + for(i = 0; i < ci->mst_n_childs; ++i) { + co2_cloud_irn_t *child = ci->mst_childs[i]; + int idx = front[i]; - /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */ - costs = cloud_costs(env, cloud); - /* materialize the new coloring. */ - if(costs < best_costs) { - materialize_coloring(&changed); - best_costs = costs; - best_col = col; - reject = 0; + 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; + } } - - /* We won't get the cloud any better so stop it. */ - if(costs == 0) - break; - - if(reject) - reject_coloring(&changed); } - DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs)); - - /* fix all cloud members */ - list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) { - ci->fixed = 1; + 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 void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed) +static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth) { - ir_node *irn = ci->irn; - - if(!color_is_fix(env, irn)) { - int n_regs = env->co->cls->n_regs; - bitset_t *tried = bitset_alloca(n_regs); - bitset_t *adm = bitset_alloca(n_regs); - col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0])); - - affinity_node_t *a = get_affinity_info(env->co, irn); - int best_costs = cloud_costs(env, ci->cloud); - int best_col = get_col(env, ci->irn); - - int i; - - determine_color_costs(env, ci, seq); - if(!INFEASIBLE(seq[preferred].costs)) - seq[preferred].costs = INT_MIN; - - qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); - - for(i = 0; i < n_regs; ++i) { - col_t col = seq[i].col; - - struct list_head changed; - int ok, costs; - - INIT_LIST_HEAD(&changed); - ok = change_color_single(env, irn, col, &changed, 0); - col = get_col(env, irn); - - if(!bitset_is_set(tried, col)) { - neighb_t *n; - - if(!ci->tmp_col) { - ci->tmp_col = col; - ci->tmp_fixed = 1; - list_add(&ci->changed_list, &changed); - } - - co_gs_foreach_neighb(a, n) { - co2_irn_t *ni = get_co2_irn(env, n->irn); - try_affinity_node(env, ni, col, &changed); - } - - examine_coloring(env, ci->cloud); - reject_coloring(&changed); - - bitset_set(tried, col); - } - } + 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; } -#endif -static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud) +static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth) { - int costs = cloud_costs(env, cloud); + co2_t *env = ci->cloud->env; + struct list_head changed; + int i, ok = 1; - if(costs < cloud->best_costs) { - int i; + INIT_LIST_HEAD(&changed); + *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1); - for(i = 0; i < cloud->n_memb; ++i) - cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn); + 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; - cloud->best_costs = costs; + ok = color_subtree(child, tgt_col, &changed, depth + 1); } + + reject_coloring(&changed); + + return ok; } -static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors) +static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col) { - col_t col = get_col(env, ci->irn); - neighb_t *n; - int balance = 0; + int *front = FRONT_BASE(ci, col); + int cost = 0; + int i; - co_gs_foreach_neighb(ci->aff, n) { - col_t nc = get_col(env, n->irn); - int fixed = color_is_fix(env, n->irn); + for(i = 0; i < ci->mst_n_childs; ++i) { + co2_cloud_irn_t *chld = ci->mst_childs[i]; + col_t chld_col = front[i]; - if(nc == col) - balance -= n->costs; - else if(!fixed || !bitset_is_set(tried_colors, nc)) - balance += n->costs; + cost += examine_subtree_coloring(chld, chld_col); + cost += col != chld_col ? chld->mst_costs : 0; } - DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance)); - return balance; + return cost; } -static void keep_sensible_colors(co2_t *env, co2_irn_t *ci, col_cost_pair_t *seq) +static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth) { - bitset_t *fixed_cols = bitset_alloca(env->co->cls->n_regs); - int all_fixed = 1; - neighb_t *n; + 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; - co_gs_foreach_neighb(ci->aff, n) { - all_fixed &= color_is_fix(env, n->irn); - bitset_set(fixed_cols, get_col(env, n->irn)); - } - if(all_fixed) { - bitset_pos_t i; - bitset_flip_all(fixed_cols); - bitset_foreach(fixed_cols, i) - seq[i].costs = INT_MAX; - } -} + int i; -static int process_node(co2_t *env, co2_cloud_t *cloud, int index) -{ - struct list_head changed; - int res = 0; + DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn)); - if(index < cloud->n_memb) { - co2_irn_t *ci = cloud->seq[index]; - int n_regs = env->co->cls->n_regs; - col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0])); - bitset_t *cols_tried = bitset_alloca(n_regs); - int done = 0; - //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0])); + for (i = 0; i < ci->mst_n_childs; ++i) + cloud_mst_build_colorings(ci->mst_childs[i], depth + 1); - int i; + for (i = 0; i < n_regs; ++i) + ci->col_costs[i] = INT_MAX; - determine_color_costs(env, ci, seq); + /* 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); - if(index == 0) { - col_t col = get_col(env, ci->irn); - int min_costs = INT_MAX; - int i; + determine_start_colors(ci, seq); + // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); - for(i = 0; i < n_regs; ++i) - min_costs = MIN(min_costs, seq[i].costs); + for(i = 0; i < n_regs; ++i) { + col_t col = seq[i].col; + int costs = seq[i].costs; + int done = 0; - seq[col].costs = min_costs - 1; - } + if(INFEASIBLE(costs)) + break; - //keep_sensible_colors(env, ci, seq); - qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt); + /* + Judge, if it is worthwhile trying this color. + If another color was so good that we cannot get any better, bail out here. + Perhaps??? + */ -#if 0 - if(index == cloud->n_memb - 1) { - for(i = 0; i < n_regs; ++i) - if(seq[i].costs >= 0) - seq[i].costs = INT_MAX; - } -#endif + 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); - for(i = 0; i < n_regs && !done; ++i) { - col_t col = seq[i].col; - int costs = seq[i].costs; - int ok; + /* Initialize the front. It gives the indexes into the color tmp_coloring array. */ + memset(front, 0, ci->mst_n_childs * sizeof(front)); - /* - if all affinity neighbors fixed, - try only color changes to affinity colors. - all other colors do no good. - */ + /* + 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; - DB((env->dbg, LEVEL_2, "\t%2Ntrying %+F index %d for color %d\n", index, ci->irn, index, col)); - if(INFEASIBLE(costs)) { - DBG((env->dbg, LEVEL_2, "\t%2N-> color is infeasible due to %s\n", index, flag_str(seq[i].flags))); - break; - } + if (try_coloring(ci, col, front, &try_push, depth + 1)) { + int *res_front = FRONT_BASE(ci, col); + int costs; - bitset_set(cols_tried, col); - INIT_LIST_HEAD(&changed); - ok = change_color_single(env, ci->irn, col, &changed, 0); - DB((env->dbg, LEVEL_2, "\t%2N-> %s\n", index, ok ? "ok" : "failed")); - - /* if we succeeded changing the color, we will figure out the next node. */ - if(ok) { - int finish; - - /* materialize the coloring and fix the node's color. */ - ci->fixed = 1; - - /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */ - finish = process_node(env, cloud, index + 1); - - /* if this is the last node in the coloring sequence, examine the coloring */ - if(index == cloud->n_memb - 1) { - examine_cloud_coloring(env, cloud); - DB((env->dbg, LEVEL_2, "\t%2N-> current best coloring %d\n", index, cloud->best_costs)); - if(cloud->best_costs == cloud->inevit) { - done = 1; - res = 1; - } + 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; } - /* unfix the node. */ - reject_coloring(&changed); - ci->fixed = 0; + costs = examine_subtree_coloring(ci, col); + ci->col_costs[col] = costs; + done = 1; - if(finish || color_change_balance(env, ci, cols_tried) <= 0) { - res = finish; - 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; } } - return res; -} - -static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs) -{ - int i; - neighb_t *n; - - i = 0; - co_gs_foreach_neighb(ci->aff, n) { - nbs[i++] = get_co2_irn(env, n->irn); - } + 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])); - qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp); - return nbs; + return best_col; } -static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud) -{ - pdeq *q = new_pdeq1(cloud->master); - bitset_t *seen = bitset_malloc(get_irg_last_idx(env->co->irg)); - co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0])); - int i, j; - - j = 0; - bitset_set(seen, get_irn_idx(cloud->master->irn)); - while(!pdeq_empty(q)) { - co2_irn_t *curr = pdeq_getl(q); - - cloud->seq[j++] = curr; - get_neighb_arr(env, curr, nbs); - - for(i = 0; i < curr->aff->degree; ++i) { - co2_irn_t *ni = nbs[i]; - int idx = get_irn_idx(ni->irn); - if(!bitset_is_set(seen, idx)) { - pdeq_putr(q, ni); - bitset_set(seen, idx); - } - } - } - - del_pdeq(q); - bitset_free(seen); -} static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs) { - be_ifg_t *ifg = env->co->cenv->ifg; - co2_irn_t *ci = get_co2_irn(env, a->irn); - int costs = 0; + be_ifg_t *ifg = env->co->cenv->ifg; + co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); + int costs = 0; neighb_t *n; if(ci->visited >= env->visited) @@ -899,12 +813,12 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i ci->cloud = cloud; list_add(&ci->cloud_list, &cloud->members_head); - DB((env->dbg, LEVEL_3, "%+F\n", ci->irn)); + DB((env->dbg, LEVEL_3, "\t%+F\n", ci->inh.irn)); /* determine the nodes costs */ co_gs_foreach_neighb(a, n) { costs += n->costs; - DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn)); + DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs)); if(be_ifg_connected(ifg, a->irn, n->irn)) cloud->inevit += n->costs; } @@ -912,13 +826,13 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i /* add the node's cost to the total costs of the cloud. */ ci->costs = costs; cloud->costs += costs; - cloud->max_degree = MAX(cloud->max_degree, ci->aff->degree); + cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree); cloud->n_memb++; /* If this is the heaviest node in the cloud, set it as the cloud's master. */ if(costs >= curr_costs) { - cloud->master = ci; curr_costs = costs; + cloud->master = ci; } /* add all the neighbors of the node to the cloud. */ @@ -929,67 +843,164 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i } } -static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a) +static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a) { + co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0])); + co2_cloud_irn_t *ci; + int i; + + DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn)); + memset(cloud, 0, sizeof(cloud[0])); + INIT_LIST_HEAD(&cloud->members_head); + INIT_LIST_HEAD(&cloud->list); + list_add(&cloud->list, &env->cloud_head); + cloud->best_costs = INT_MAX; + cloud->env = env; env->visited++; populate_cloud(env, cloud, a, 0); - cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0])); - cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0])); - env->visited++; - cloud->seq[0] = cloud->master; - determine_coloring_sequence(env, cloud); + /* 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])); + + i = 0; + list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) { + ci->index = i; + cloud->seq[i++] = ci; + } + DBG((env->dbg, LEVEL_2, "cloud cost %d\n", cloud->costs)); + + return cloud; } -static void process_cloud(co2_t *env, co2_cloud_t *cloud) +static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth) { + ir_node *irn = ci->inh.irn; + int *front = FRONT_BASE(ci, col); + int i, ok; + + 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"); + + for(i = 0; i < ci->mst_n_childs; ++i) { + apply_coloring(ci->mst_childs[i], front[i], changed, depth + 1); + } +} + +static void process_cloud(co2_cloud_t *cloud) +{ + co2_t *env = cloud->env; + int n_edges = 0; + struct list_head changed; + edge_t *edges; int i; + int best_col; - /* initialize the best coloring. */ - examine_cloud_coloring(env, cloud); - - DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit)); + /* 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) { - co2_irn_t *ci = cloud->seq[i]; - DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn))); + co2_cloud_irn_t *ci = cloud->seq[i]; + neighb_t *n; + + co_gs_foreach_neighb(ci->inh.aff, n) { + co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn); + if(ci->index < ni->index) { + edge_t e; + e.src = ci; + e.tgt = ni; + e.costs = n->costs; + obstack_grow(&cloud->obst, &e, sizeof(e)); + n_edges++; + } + } + } + edges = obstack_finish(&cloud->obst); + qsort(edges, n_edges, sizeof(edges[0]), cmp_edges); + + /* Compute the maximum spanning tree using Kruskal/Union-Find */ + DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn)); + for(i = 0; i < n_edges; ++i) { + edge_t *e = &edges[i]; + co2_cloud_irn_t *p_src = find_mst_root(e->src); + co2_cloud_irn_t *p_tgt = find_mst_root(e->tgt); + + if(p_src != p_tgt) { + p_tgt->mst_n_childs++; + p_src->mst_parent = p_tgt; + p_src->mst_costs = e->costs; + + DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", p_src->inh.irn, p_tgt->inh.irn, e->costs)); + } } + obstack_free(&cloud->obst, edges); - process_node(env, cloud, 0); - DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs)); + for(i = 0; i < cloud->n_memb; ++i) { + co2_cloud_irn_t *ci = cloud->seq[i]; + ci->mst_childs = obstack_alloc(&cloud->obst, ci->mst_n_childs * sizeof(ci->mst_childs)); + ci->col_costs = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->col_costs[0])); + ci->tmp_coloring = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->tmp_coloring[0])); + ci->fronts = obstack_alloc(&cloud->obst, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0])); + memset(ci->col_costs, 0, env->n_regs * sizeof(ci->col_costs[0])); + memset(ci->tmp_coloring, 0, env->n_regs * sizeof(ci->tmp_coloring[0])); + memset(ci->fronts, 0, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0])); + + ci->mst_n_childs = 0; + } - /* re-try the best coloring. */ - INIT_LIST_HEAD(&changed); + /* build the child arrays in the nodes */ for(i = 0; i < cloud->n_memb; ++i) { - co2_irn_t *ci = cloud->seq[i]; - col_t col = cloud->best_cols[i]; + co2_cloud_irn_t *ci = cloud->seq[i]; + if(ci->mst_parent != ci) + ci->mst_parent->mst_childs[ci->mst_parent->mst_n_childs++] = ci; + else { + cloud->mst_root = ci; + cloud->mst_costs = 0; + } + } - int ok; + /* Compute the "best" colorings. */ + best_col = cloud_mst_build_colorings(cloud->mst_root, 0); - DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col)); - ok = change_color_single(env, ci->irn, col, &changed, 0); - assert(ok); - ci->fixed = 1; + for(i = 0; i < env->n_regs; ++i) { + int c; + c = examine_subtree_coloring(cloud->mst_root, i); + DBG((env->dbg, LEVEL_2, "color %d costs %d\n", i, c)); } + + /* Apply the coloring for the best color in the root node and fix all nodes in this cloud */ + INIT_LIST_HEAD(&changed); + apply_coloring(cloud->mst_root, best_col, &changed, 0); materialize_coloring(&changed); + for(i = 0; i < cloud->n_memb; ++i) + cloud->seq[i]->inh.fixed = 1; - { - co2_irn_t *ci; - int some_fixed = 0; - for(ci = env->touched; ci; ci = ci->touched_next) { - if(ci->tmp_fixed) { - some_fixed = 1; - ir_printf("%+F is still temp fixed\n", ci->irn); - } + obstack_free(&cloud->obst, NULL); +} + +static int cloud_costs(co2_cloud_t *cloud) +{ + int i, costs = 0; + neighb_t *n; + + for(i = 0; i < cloud->n_memb; ++i) { + co2_irn_t *ci = (co2_irn_t *) cloud->seq[i]; + col_t col = get_col(cloud->env, ci->irn); + co_gs_foreach_neighb(ci->aff, n) { + col_t n_col = get_col(cloud->env, n->irn); + costs += col != n_col ? n->costs : 0; } - assert(!some_fixed); } + + return costs / 2; } static void process(co2_t *env) { affinity_node_t *a; - struct list_head cloud_head; co2_cloud_t *pos; co2_cloud_t **clouds; int n_clouds; @@ -998,33 +1009,39 @@ static void process(co2_t *env) int all_costs = 0; int final_costs = 0; - - INIT_LIST_HEAD(&cloud_head); - n_clouds = 0; co_gs_foreach_aff_node(env->co, a) { - co2_irn_t *ci = get_co2_irn(env, a->irn); + co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn); if(!ci->cloud) { - co2_cloud_t *cloud = new_cloud(env); - - init_cloud(env, cloud, a); - list_add(&cloud->list, &cloud_head); + co2_cloud_t *cloud = new_cloud(env, a); n_clouds++; } } i = 0; clouds = xmalloc(n_clouds * sizeof(clouds[0])); - list_for_each_entry(co2_cloud_t, pos, &cloud_head, list) + list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) clouds[i++] = pos; - qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds); + qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt); for(i = 0; i < n_clouds; ++i) { - init_costs += cloud_costs(env, clouds[i]); - process_cloud(env, clouds[i]); + init_costs += cloud_costs(clouds[i]); + process_cloud(clouds[i]); all_costs += clouds[i]->costs; - final_costs += clouds[i]->best_costs; + final_costs += cloud_costs(clouds[i]); + + /* Dump the IFG if the user demanded it. */ + if (dump_flags & DUMP_CLOUD) { + char buf[256]; + 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")) { + be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env); + fclose(f); + } + } } DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs)); @@ -1043,21 +1060,172 @@ static void writeback_colors(co2_t *env) } } + +/* + ___ _____ ____ ____ ___ _____ ____ _ + |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _ + | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` | + | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| | + |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, | + |_| |___/ +*/ + +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"; +} + +static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci) +{ + 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)) + return "diamond"; + + if(ci->fixed) + return "rectangle"; + + if(ci->tmp_fixed) + return "hexagon"; + + return "ellipse"; +} + +static void ifg_dump_graph_attr(FILE *f, 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); +} + +static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn) +{ + co2_t *env = self; + co2_irn_t *ci = get_co2_irn(env, irn); + int peri = 1; + + if(ci->aff) { + co2_cloud_irn_t *cci = (void *) ci; + if (cci->cloud && cci->cloud->mst_root == cci) + peri = 2; + } + + ir_fprintf(f, "label=\"%+F\" style=filled peripheries=%d color=%s shape=%s", irn, peri, + get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci)); +} + +static void ifg_dump_at_end(FILE *file, void *self) +{ + co2_t *env = self; + affinity_node_t *a; + + 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); + neighb_t *n; + + co_gs_foreach_neighb(a, n) { + int nidx = get_irn_idx(n->irn); + co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn); + + if(idx < nidx) { + const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red"; + const char *arr = "arrowhead=dot arrowtail=dot"; + + if(ci->mst_parent == ai) + arr = "arrowtail=normal"; + else if(ai->mst_parent == ci) + arr = "arrowhead=normal"; + + fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color); + } + } + } +} + + +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_solve_heuristic_new(copy_opt_t *co) { co2_t env; + FILE *f; - phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init); + phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init); env.touched = NULL; env.visited = 0; 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); FIRM_DBG_REGISTER(env.dbg, "firm.be.co2"); + INIT_LIST_HEAD(&env.cloud_head); + + if(dump_flags & DUMP_BEFORE) { + if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) { + be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); + fclose(f); + } + } process(&env); + + if(dump_flags & DUMP_AFTER) { + if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) { + be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env); + fclose(f); + } + } + writeback_colors(&env); phase_free(&env.ph); }