-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(p->costs, q->costs);
-}
-
-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;
-}
-
-
-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;
-}
-