#include <limits.h>
#include "list.h"
+#include "pdeq.h"
#include "bitset.h"
+
#include "debug.h"
+#include "bitfiddle.h"
#include "irphase_t.h"
#include "irgraph_t.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
+#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_irn_t co2_irn_t;
+typedef struct _co2_cloud_t co2_cloud_t;
typedef struct {
- phase_t ph;
+ phase_t ph;
copy_opt_t *co;
- bitset_t *ignore_regs;
- co2_irn_t *touched;
+ 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_irn_t *touched_next;
- int costs;
- col_t tmp_col;
- col_t orig_col;
- unsigned fixed : 1;
- unsigned tmp_fixed : 1;
+ ir_node *irn;
+ co2_cloud_t *cloud;
+ co2_irn_t *touched_next;
+ affinity_node_t *aff;
+ int costs;
+ col_t tmp_col;
+ col_t orig_col;
+ int visited;
+ int fixed_index;
+ 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 {
+ co2_t *env;
+ int costs;
+ int inevit;
+ int best_costs;
+ int n_memb;
+ int max_degree;
+ int ticks;
+ co2_irn_t *master;
+ co2_irn_t **seq;
+ col_t *best_cols;
+ int **failrure_matrix;
+ struct list_head members_head;
+ struct list_head list;
};
+#define NEIGHBOR_FIXED 1
+#define NEIGHBOR_CONSTR 2
+#define SELF_CONSTR 4
+#define DONT_WANT 8
+
+typedef struct {
+ col_t col;
+ int costs;
+ unsigned flags;
+} col_cost_pair_t;
+
#define get_co2_irn(co2, irn) ((co2_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(phase_t *ph, ir_node *irn, void *data)
{
co2_t *env = (co2_t *) ph;
- co2_irn_t *ci = data;
+ co2_irn_t *ci = data ? data : phase_alloc(ph, sizeof(ci[0]));
memset(ci, 0, sizeof(ci[0]));
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, (ir_node *)irn);
env->touched = ci;
+ return ci;
}
return (*q)->costs - (*p)->costs;
}
-typedef struct {
- col_t col;
- int costs;
-} col_cost_pair_t;
+static int cmp_clouds(const void *a, const void *b)
+{
+ const co2_cloud_t **p = a;
+ const co2_cloud_t **q = b;
+ return (*q)->costs - (*p)->costs;
+}
/**
* An order on color/costs pairs.
{
const col_cost_pair_t *p = a;
const col_cost_pair_t *q = b;
- int cost_diff = p->costs - q->costs;
+ int c = p->costs;
+ int d = q->costs;
- return cost_diff;
- // return cost_diff != 0 ? cost_diff : p->col - q->col;
+ return (c > d) - (c < d);
+}
+
+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;
}
static col_t get_col(co2_t *env, ir_node *irn)
return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}
-static INLINE color_is_fix(co2_t *env, ir_node *irn)
+static INLINE int color_is_fix(co2_t *env, ir_node *irn)
{
co2_irn_t *ci = get_co2_irn(env, irn);
return ci->fixed || ci->tmp_fixed;
}
+static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
+{
+ 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.limited(req.limited_env, bs);
+ else {
+ bitset_copy(bs, env->ignore_regs);
+ bitset_flip_all(bs);
+ }
+
+ return bs;
+}
+
+static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
+{
+ bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
+ admissible_colors(env, ci, bs);
+ return bitset_is_set(bs, col);
+}
+
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);
req.limited(req.limited_env, aux);
n_constr = bitset_popcnt(aux);
- bitset_foreach(aux, elm)
- col_costs[elm].costs += costs / n_constr;
+ bitset_foreach(aux, elm) {
+ col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
+ col_costs[elm].flags |= NEIGHBOR_CONSTR;
+ }
}
}
* @param irn The node.
* @param col_costs An array of colors x costs where the costs are written to.
*/
-static void determine_color_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs)
+static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
{
+ 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 = get_affinity_info(env->co, irn);
- arch_register_req_t req;
bitset_pos_t elm;
ir_node *pos;
void *it;
int i;
- /* Put all forbidden colors into the aux bitset. */
- arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
- if(arch_register_req_is(&req, limited)) {
- req.limited(req.limited_env, forb);
- bitset_flip_all(forb);
+#if 0
+ if(get_irn_node_nr(irn) == 2040) {
+ printf("Hallo");
}
- else
- bitset_copy(forb, env->ignore_regs);
+#endif
+
+ /* Put all forbidden colors into the aux bitset. */
+ admissible_colors(env, ci, forb);
+ bitset_flip_all(forb);
for(i = 0; i < n_regs; ++i) {
col_costs[i].col = i;
col_costs[i].costs = 0;
+ col_costs[i].flags = 0;
}
if(a) {
neighb_t *n;
co_gs_foreach_neighb(a, n) {
- co2_irn_t *ni = get_co2_irn(env, n->irn);
-
- if(ni->fixed) {
+ 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);
it = be_ifg_neighbours_iter_alloca(ifg);
be_ifg_foreach_neighbour(ifg, it, irn, pos) {
col_t col = get_col(env, pos);
- if(color_is_fix(env, pos))
- col_costs[col].costs = INT_MAX;
+ 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++;
+ 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;
+ bitset_foreach(forb, elm) {
+ col_costs[elm].costs = INT_MAX;
+ col_costs[elm].flags |= SELF_CONSTR;
+ }
}
+static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
+{
+ int n_regs = env->co->cls->n_regs;
+ int i;
+
+ 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);
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)
{
co2_irn_t *pos;
pos->tmp_fixed = 0;
}
-static void materialize_coloring(co2_t *env, struct list_head *h)
+static void materialize_coloring(struct list_head *h)
{
- const arch_register_class_t *cls = env->co->cls;
- const arch_env_t *aenv = env->co->aenv;
co2_irn_t *pos;
list_for_each_entry(co2_irn_t, pos, h, changed_list) {
}
}
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
+typedef struct {
+ co2_irn_t *ci;
+ col_t col;
+} col_entry_t;
+
+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 INLINE int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, int n_regs, struct list_head *parent_changed, int depth)
+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)
{
- be_ifg_t *ifg = env->co->cenv->ifg;
- co2_irn_t *ci = get_co2_irn(env, irn);
- int res = 0;
+ 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;
ir_node *n;
void *it;
- DBG((env->dbg, LEVEL_2, "\t%2Dtrying 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(costs == INT_MAX) {
+ if(INFEASIBLE(costs)) {
+ DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible due to %s\n", depth, tgt_col, flag_str(col_list[i].flags)));
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,
}
}
-
/*
We managed to assign the target color to all neighbors, so from the perspective
of the current node, every thing was ok and we can return safely.
*/
if(neigh_ok) {
- DBG((env->dbg, LEVEL_2, "\t%2Dcolor %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;
int res = 0;
col_t col = get_col(env, irn);
- DBG((env->dbg, LEVEL_2, "\t%2Dclearing %+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);
col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
/* Get the costs for giving the node a specific color. */
- determine_color_costs(env, irn, csts);
+ determine_color_costs(env, ci, csts);
/* Since the node must not have the not_col, set the costs for that color to "infinity" */
csts[not_col].costs = INT_MAX;
qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
/* Try recoloring the node using the color list. */
- res = recolor(env, irn, csts, n_regs, parent_changed, depth);
+ res = recolor(env, irn, csts, parent_changed, depth);
}
/* If we came here, everything went ok. */
return res;
}
-/**
- * Try to bring a node to a certain color.
- */
-static int try_color(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *changed)
+static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
{
co2_irn_t *ci = get_co2_irn(env, irn);
- be_ifg_t *ifg = env->co->cenv->ifg;
-
- ir_node *n;
- void *it;
+ col_t col = get_col(env, irn);
+ int res = 0;
- ci->tmp_fixed = 1;
- ci->tmp_col = tgt_col;
- list_add(&ci->changed_list, changed);
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
- it = be_ifg_neighbours_iter_alloca(ifg);
- be_ifg_foreach_neighbour(ifg, it, irn, n) {
- col_t c = get_col(env, n);
-
- /* If the neighbor has the target color, re-color the neighbor. */
- if(c == tgt_col) {
- int ok = change_color_not(env, n, tgt_col, changed, 1);
- if(!ok)
- return 0;
+ /* 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;
+ list_add(&ci->changed_list, parent_changed);
}
+
+ DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}ok\n", depth));
+ return 1;
+ }
+
+ 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]));
+
+ /* Get the costs for giving the node a specific color. */
+ single_color_cost(env, tgt_col, seq);
+
+ /* Try recoloring the node using the color list. */
+ res = recolor(env, irn, seq, parent_changed, depth);
+
+ 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 1;
+ return res;
}
-static INLINE int costs_sufficient(co2_irn_t *irn, int costs)
+static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
{
- return costs == -irn->costs;
+ int costs = cloud_costs(env, cloud);
+
+ if(costs < cloud->best_costs) {
+ int i;
+
+ for(i = 0; i < cloud->n_memb; ++i)
+ cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
+
+ cloud->best_costs = costs;
+ }
}
-static void process_affinity_node(co2_t *env, co2_irn_t *ci)
+static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors, int depth)
{
- 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);
- int best_cost = curr_costs(env, a);
- col_t best_col = ci->orig_col;
-
+ col_t col = get_col(env, ci->irn);
+ int balance = 0;
neighb_t *n;
- int i;
- assert(a != NULL && "This node must be an affinity node");
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}node %+F has color %d\n", depth, ci->irn, col));
+ co_gs_foreach_neighb(ci->aff, n) {
+ col_t nc = get_col(env, n->irn);
+ int fixed = color_is_fix(env, n->irn);
+
+#if 0
+ if(fixed) {
+ if(nc == col)
+ balance -= n->costs;
+ else if(!bitset_is_set(tried_colors, nc))
+ balance += n->costs;
+ }
- /* If that node has already been fixed, leave it alone. */
- if(ci->fixed)
- return;
+ else
+ balance += n->costs;
- DB((env->dbg, LEVEL_1, "affinity node %+F cost %d\n", ci->irn, ci->costs));
+#else
+ if(nc == col) {
+ balance -= n->costs;
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}neighbor %+F has the same color, bonus %d\n", depth, n->irn, -n->costs));
+ }
+ else if(!fixed) {
+ balance += n->costs;
+ DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}non fixed neighbor %+F has different color %d, malus %d\n", depth, n->irn, nc, n->costs));
+ }
+#endif
+ }
- /* determine the order in which the colors shall be tried. */
- determine_color_costs(env, ci->irn, col_seq);
- qsort(col_seq, n_regs, sizeof(col_seq[0]), col_cost_pair_lt);
+ return balance;
+}
- /* Try the colors. */
- for(i = 0; i < n_regs; ++i) {
- col_t col = col_seq[i].col;
- int costs = col_seq[i].costs;
+static void adjust_start_colors(co2_t *env, co2_cloud_t *cloud, col_cost_pair_t *seq)
+{
+ int n_regs = env->co->cls->n_regs;
+ bitset_t *adm = bitset_alloca(n_regs);
+ bitset_pos_t col;
+ int i;
- struct list_head changed;
- int ok;
+ for(i = 0; i < cloud->n_memb; ++i) {
+ co2_irn_t *ci = cloud->seq[i];
+ int n_constr;
- DB((env->dbg, LEVEL_2, "\tbest color %d incurring costs %d\n", best_col, best_cost));
+ /* Prefer precolored neighbors. */
+ bitset_clear_all(adm);
+ admissible_colors(env, ci, adm);
+ n_constr = bitset_popcnt(adm);
- /* Also, if the costs are not more optimizable, we do not try additional colors and finish this node. */
- if(best_cost == 0)
- break;
+ bitset_foreach(adm, col) {
+ seq[col].costs = add_saturated(seq[col].costs, -128 * (n_regs - n_constr));
+ }
- if(costs == INT_MAX) {
- DB((env->dbg, LEVEL_1, "\tall following colors after %d will be infeasible\n", col));
- break;
+ bitset_foreach_clear(adm, col) {
+ seq[col].costs = add_saturated(seq[col].costs, 128);
}
+ }
- INIT_LIST_HEAD(&changed);
+ admissible_colors(env, cloud->master, adm);
+ bitset_flip_all(adm);
- DB((env->dbg, LEVEL_1, "\ttrying color %d costing %d\n", col, costs));
+ bitset_foreach(adm, col)
+ seq[col].costs = INT_MAX;
+}
- /* try to assign the same color to the node and all its neighbors. */
- ok = try_color(env, a->irn, col, &changed);
+static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
+{
+ struct list_head changed;
+ int res = 0;
+
+ 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;
+ int n_new_fixed = 0;
+ int n_fixed = 0;
- if(!ok) {
- DBG((env->dbg, LEVEL_2, "\t-> failed.\n"));
- reject_coloring(&changed);
- continue;
- }
+ neighb_t *n;
+ int i;
/*
- Evaluate the recoloring and mark it is as new best if it was better
- as the best current known solution.
+ Investigate if one of the fixed neighbors of this node has changed
+ its color since this node changed its color. If so we will
+ consider changing this node's color again.
*/
- costs = curr_costs(env, a);
- DBG((env->dbg, LEVEL_2, "\t-> cost: %d\n", costs));
- if(costs < best_cost) {
- best_cost = costs;
- best_col = col;
+ co_gs_foreach_neighb(ci->aff, n) {
+ co2_irn_t *ni = get_co2_irn(env, n->irn);
+ n_fixed += ni->fixed;
+ n_new_fixed += ni->fixed && ni->last_color_change > ci->last_color_change;
+ }
+
+ if(n_fixed > 0 && n_new_fixed == 0)
+ return process_node(env, cloud, index + 1);
+
+ determine_color_costs(env, ci, seq);
+
+ /* If this is the first node, adjust the sequence of the coloring. */
+ if(index == 0)
+ adjust_start_colors(env, cloud, seq);
+
+ qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
+
+ for(i = 0; i < n_regs && !done; ++i) {
+ col_t col = seq[i].col;
+ int costs = seq[i].costs;
+ int ok;
+
+ /*
+ if all affinity neighbors fixed,
+ try only color changes to affinity colors.
+ all other colors do no good.
+ */
- materialize_coloring(env, &changed);
+ DB((env->dbg, LEVEL_2, "\t%2{firm:indent}trying %+F index %d for color %d\n", index, ci->irn, index, col));
+ if(INFEASIBLE(costs)) {
+ DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
+ break;
+ }
+
+ bitset_set(cols_tried, col);
+ INIT_LIST_HEAD(&changed);
+ cloud->ticks++;
+ ok = change_color_single(env, ci->irn, col, &changed, index);
+ DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", index, ok ? "ok" : "failed"));
+
+ /* if we succeeded changing the color, we will figure out the next node. */
+ if(ok) {
+ int balance;
+ int finish;
+
+ /* Mark the time of the last color change */
+ ci->last_color_change = cloud->ticks;
+
+ /* 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%2{firm:indent}-> current best coloring %d\n", index, cloud->best_costs));
+ if(cloud->best_costs == cloud->inevit)
+ finish = 1;
+ }
+
+ /* Compute the recoloring balance for this solution. */
+ balance = color_change_balance(env, ci, cols_tried, index);
+ DBG((env->dbg, LEVEL_3, "\t%2{firm:indent}balance for further color changing: %d\n", index, balance));
+
+ /* unfix the node. */
+ reject_coloring(&changed);
+ ci->fixed = 0;
+
+ if(finish || balance <= 0) {
+ res = finish;
+ done = 1;
+ }
+ }
}
+ }
- /* If we had a better coloring already, reject the current one. */
- else
- reject_coloring(&changed);
+ 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);
+ }
+ qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
+ return nbs;
+}
+
+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);
+ }
+ }
}
- /* We found the definite color for this node, so fix it. */
- ci->fixed = 1;
+ del_pdeq(q);
+ bitset_free(seen);
+}
- DB((env->dbg, LEVEL_1, "\tusing %d(%d)\n", best_col, best_cost));
+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;
+ neighb_t *n;
+
+ if(ci->visited >= env->visited)
+ return;
+
+ /* mark the node as visited and add it to the cloud. */
+ ci->visited = env->visited;
+ ci->cloud = cloud;
+ list_add(&ci->cloud_list, &cloud->members_head);
- /* Now, investigate all affinity neighbors of this node. */
- if(0) {
- co2_irn_t **neighbors = alloca(a->degree * sizeof(neighbors[0]));
+ DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
+
+ /* determine the nodes costs */
+ co_gs_foreach_neighb(a, n) {
+ costs += n->costs;
+ DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
+ if(be_ifg_connected(ifg, a->irn, n->irn))
+ cloud->inevit += n->costs;
+ }
- i = 0;
- co_gs_foreach_neighb(a, n)
- neighbors[i++] = get_co2_irn(env, n->irn);
+ /* 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->n_memb++;
- qsort(neighbors, a->degree, sizeof(neighbors[0]), co2_irn_cmp);
- for(i = 0; i < a->degree; ++i)
- process_affinity_node(env, neighbors[i]);
+ /* 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;
+ }
+
+ /* add all the neighbors of the node to the cloud. */
+ co_gs_foreach_neighb(a, n) {
+ affinity_node_t *an = get_affinity_info(env->co, n->irn);
+ assert(an);
+ populate_cloud(env, cloud, an, curr_costs);
}
}
-static void process(co2_t *env)
+static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
+{
+ 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);
+ list_add(&cloud->list, &env->cloud_head);
+ cloud->best_costs = INT_MAX;
+ cloud->env = env;
+ env->visited++;
+ populate_cloud(env, cloud, a, 0);
+
+ /* 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]));
+ cloud->seq[0] = cloud->master;
+ env->visited++;
+ determine_coloring_sequence(env, cloud);
+
+#if 0
+ /* Allocate the failure matrix. */
+ cloud->failrure_matrix = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->failrure_matrix[0]));
+ for(i = 0; i < env->n_regs; ++i) {
+ cloud->failrure_matrix[i] = phase_alloc(&env->ph, env->n_regs * sizeof(cloud->failrure_matrix[i][0]));
+ memset(cloud->failrure_matrix[i], 0, env->n_regs * sizeof(cloud->failrure_matrix[i][0]));
+ }
+#endif
+ return cloud;
+}
+
+static void process_cloud(co2_t *env, co2_cloud_t *cloud, int nr)
{
- struct obstack obst;
- affinity_node_t *an;
- co2_irn_t **nodes;
- int i, n;
+ struct list_head changed;
+ int i;
- obstack_init(&obst);
+ /* initialize the best coloring. */
+ examine_cloud_coloring(env, cloud);
- n = 0;
- co_gs_foreach_aff_node(env->co, an) {
- ir_node *irn = an->irn;
- co2_irn_t *ci = get_co2_irn(env, irn);
+ DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
+ 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)));
+ }
- neighb_t *neighb;
+ process_node(env, cloud, 0);
+ DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
- co_gs_foreach_neighb(an, neighb)
- ci->costs += neighb->costs;
+ /* re-try the best coloring. */
+ INIT_LIST_HEAD(&changed);
+ for(i = 0; i < cloud->n_memb; ++i) {
+ co2_irn_t *ci = cloud->seq[i];
+ col_t col = cloud->best_cols[i];
- obstack_ptr_grow(&obst, ci);
- n++;
+ int ok;
+
+ 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;
}
+ materialize_coloring(&changed);
+
+ {
+ 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);
+ }
+ }
+ assert(!some_fixed);
+ }
+
+ {
+ char buf[256];
+ FILE *f;
- nodes = obstack_finish(&obst);
+ ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, nr);
+ if(f = fopen(buf, "wt")) {
+ be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
+ fclose(f);
+ }
+ }
- /* sort the nodes according to processing order. */
- qsort(nodes, n, sizeof(nodes[0]), co2_irn_cmp);
+}
- for(i = 0; i < n; ++i) {
- if(!nodes[i]->fixed)
- process_affinity_node(env, nodes[i]);
+static void process(co2_t *env)
+{
+ affinity_node_t *a;
+ co2_cloud_t *pos;
+ co2_cloud_t **clouds;
+ int n_clouds;
+ int i;
+ int init_costs = 0;
+ int all_costs = 0;
+ int final_costs = 0;
+
+ n_clouds = 0;
+ co_gs_foreach_aff_node(env->co, a) {
+ co2_irn_t *ci = get_co2_irn(env, a->irn);
+
+ if(!ci->cloud) {
+ co2_cloud_t *cloud = new_cloud(env, a);
+ n_clouds++;
+ }
}
- obstack_free(&obst, NULL);
+ i = 0;
+ clouds = xmalloc(n_clouds * sizeof(clouds[0]));
+ list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
+ clouds[i++] = pos;
+ qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
+
+ for(i = 0; i < n_clouds; ++i) {
+ init_costs += cloud_costs(env, clouds[i]);
+ process_cloud(env, clouds[i], i);
+ all_costs += clouds[i]->costs;
+ final_costs += clouds[i]->best_costs;
+ }
+
+ DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
+
+ xfree(clouds);
}
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);
+
+ ir_fprintf(f, "label=\"%+F,%d\" style=filled color=%s shape=%s", irn, ci->costs,
+ 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) {
+ int idx = get_irn_idx(a->irn);
+ neighb_t *n;
+
+ co_gs_foreach_neighb(a, n) {
+ int nidx = get_irn_idx(n->irn);
+
+ if(idx < nidx) {
+ const char *style = get_col(env, a->irn) == get_col(env, n->irn) ? "dashed" : "dotted";
+ fprintf(file, "\tn%d -- n%d [label=\"%d\" style=%s weight=0.01];\n", idx, nidx, n->costs, style);
+ }
+ }
+ }
+
+}
+
+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.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(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(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);
}
projects / libfirm / blobdiff