+ return res;
+}
+
+/**
+ * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
+ * ATTENTION: Expect @p costs already sorted by increasing costs.
+ * @return 1 if coloring could be applied, 0 otherwise.
+ */
+static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones) {
+ int i;
+ struct list_head local_changed;
+
+ DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
+ DBG_COL_COST(env, LEVEL_1, costs);
+ DB((dbg, LEVEL_1, "\n"));
+
+ for (i = 0; i < env->n_regs; ++i) {
+ int tgt_col = costs[i].col;
+ int neigh_ok = 1;
+ int j;
+
+ /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
+ if (costs[i].cost == COL_COST_INFEASIBLE) {
+ return 0;
+ }
+
+ /* Set the new color of the node and mark the node as temporarily fixed. */
+ assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
+ INIT_LIST_HEAD(&local_changed);
+ set_temp_color(node, tgt_col, &local_changed);
+ DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
+
+ /* try to color all interfering neighbours with current color forbidden */
+ for (j = 0; j < node->n_neighs; ++j) {
+ co_mst_irn_t *nn;
+ ir_node *neigh;
+
+ neigh = node->int_neighs[j];
+
+ /* skip ignore nodes */
+ if (arch_irn_is(env->aenv, neigh, ignore))
+ continue;
+
+ nn = get_co_mst_irn(env, neigh);
+ DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
+ neigh, j, nn->fixed, nn->tmp_col, nn->col));
+
+ /*
+ Try to change the color of the neighbor and record all nodes which
+ get changed in the tmp list. Add this list to the "changed" list for
+ that color. If we did not succeed to change the color of the neighbor,
+ we bail out and try the next color.
+ */
+ if (get_mst_irn_col(nn) == tgt_col) {
+ /* try to color neighbour with tgt_col forbidden */
+ neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed);
+
+ if (!neigh_ok)
+ break;
+ }
+ }
+
+ /*
+ 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) {
+ /* append the local_changed ones to global ones */
+ list_splice(&local_changed, changed_ones);
+ return 1;
+ }
+ else {
+ /* coloring of neighbours failed, so we try next color */
+ reject_coloring(&local_changed);
+ }
+ }
+
+ return 0;
+}
+
+/**
+ * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
+ * @return 1 if color @p col could be applied, 0 otherwise
+ */
+static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed_ones) {
+ int col = get_mst_irn_col(node);
+
+ /* if node already has the target color -> good, temporary fix it */
+ if (col == tgt_col) {
+ DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
+ if (is_loose(node))
+ set_temp_color(node, tgt_col, changed_ones);
+ return 1;
+ }
+
+ /*
+ Node has not yet a fixed color and target color is admissible
+ -> try to recolor node and it's affinity neighbours
+ */
+ if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
+ col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
+ int res;
+
+ col_cost_init_single(env, costs, tgt_col);
+
+ DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
+ res = recolor_nodes(env, node, costs, changed_ones);
+ DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
+
+ return res;
+ }
+
+#ifndef NDEBUG
+ if (firm_dbg_get_mask(dbg) & LEVEL_4) {
+ if (!is_loose(node))
+ DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
+ else {
+ DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
+ dbg_admissible_colors(env, node);
+ DB((dbg, LEVEL_4, ")\n"));
+ }
+ }
+#endif
+
+ return 0;
+}
+
+/**
+ * Tries to color an affinity chunk (or at least a part of it).
+ * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
+ */
+static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
+ aff_chunk_t *best_chunk = NULL;
+ int best_color = -1;
+ int did_all = 0;
+ waitq *tmp_chunks = new_waitq();
+ waitq *best_starts = NULL;
+ bitset_t *visited;
+ int col, idx, len;
+ struct list_head changed_ones;
+
+ DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
+ DBG_AFF_CHUNK(env, LEVEL_2, c);
+ DB((dbg, LEVEL_2, "\n"));
+
+
+ /* check which color is the "best" for the given chunk.
+ * if we found a color which was ok for all nodes, we take it
+ * and do not look further. (see did_all flag usage below.)
+ * If we have many colors which fit all nodes it is hard to decide
+ * which one to take anyway.
+ * TODO Sebastian: Perhaps we should at all nodes and figure out
+ * a suitable color using costs as done above (determine_color_costs).
+ */
+ for (col = 0; col < env->n_regs && !did_all; ++col) {
+ int one_good = 0;
+ waitq *good_starts = new_waitq();
+ aff_chunk_t *local_best;
+
+ /* skip ignore colors */
+ if (bitset_is_set(env->ignore_regs, col))
+ continue;
+
+ DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
+
+ /* suppose we can color all nodes to the same color */
+ did_all = 1;
+
+ INIT_LIST_HEAD(&changed_ones);
+
+ /* try to bring all nodes of given chunk to the current color. */
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ ir_node *irn = c->n[idx];
+ co_mst_irn_t *node = get_co_mst_irn(env, irn);
+ int good = 0;
+
+ assert(! node->fixed && "Node must not have a fixed color.");
+ DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
+
+ /*
+ The order of the colored nodes is important, so we record the successfully
+ colored ones in the order they appeared.
+ */
+ good = change_node_color(env, node, col, &changed_ones);
+ if (good) {
+ waitq_put(good_starts, node);
+ }
+
+ one_good |= good;
+ did_all &= good;
+
+ DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
+ }
+
+ /* try next color when failed */
+ if (! one_good) {
+ reject_coloring(&changed_ones);
+ continue;
+ }
+
+ /* fragment the chunk according to the coloring */
+ local_best = fragment_chunk(env, col, c, tmp_chunks);
+
+ /* search the best of the good list
+ and make it the new best if it is better than the current */
+ if (local_best) {
+ aff_chunk_assure_weight(env, local_best);
+
+ DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
+ DBG_AFF_CHUNK(env, LEVEL_4, local_best);
+
+ if (! best_chunk || best_chunk->weight < local_best->weight) {
+ best_chunk = local_best;
+ best_color = col;
+ if (best_starts)
+ del_waitq(best_starts);
+ best_starts = good_starts;
+ DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
+ } else {
+ DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
+ del_waitq(good_starts);
+ }
+ }
+ else {
+ del_waitq(good_starts);
+ }
+
+ reject_coloring(&changed_ones);
+ }
+
+ /* free all intermediate created chunks except best one */
+ while (! waitq_empty(tmp_chunks)) {
+ aff_chunk_t *tmp = waitq_get(tmp_chunks);
+ if (tmp != best_chunk)
+ delete_aff_chunk(env, tmp);
+ }
+ del_waitq(tmp_chunks);
+
+ /* return if coloring failed */
+ if (! best_chunk) {
+ if (best_starts)
+ del_waitq(best_starts);
+ return;
+ }
+
+ DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
+ DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
+ DB((dbg, LEVEL_2, "using color %d\n", best_color));
+
+ INIT_LIST_HEAD(&changed_ones);
+ for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
+ ir_node *irn = best_chunk->n[idx];
+ co_mst_irn_t *node = get_co_mst_irn(env, irn);
+ int res;
+
+ /* bring the node to the color. */
+ DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
+ INIT_LIST_HEAD(&changed_ones);
+ res = change_node_color(env, node, best_color, &changed_ones);
+ if (res) {
+ materialize_coloring(&changed_ones);
+ node->fixed = 1;
+ }
+ }
+
+ /* remove the nodes in best chunk from original chunk */
+ bitset_andnot(c->nodes, best_chunk->nodes);
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ ir_node *irn = c->n[idx];
+
+ if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
+ int last = ARR_LEN(c->n) - 1;
+
+ c->n[idx] = c->n[last];
+ ARR_SHRINKLEN(c->n, last);
+ len--;
+ }
+ }
+
+ /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ ir_node *n = c->n[idx];
+ co_mst_irn_t *nn = get_co_mst_irn(env, n);
+ nn->chunk = c;
+ }
+
+ /* fragment the remaining chunk */
+ visited = bitset_irg_malloc(env->co->irg);
+ bitset_or(visited, best_chunk->nodes);
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ ir_node *irn = c->n[idx];
+ if (! bitset_is_set(visited, get_irn_idx(irn))) {
+ aff_chunk_t *new_chunk = new_aff_chunk(env);
+ co_mst_irn_t *node = get_co_mst_irn(env, irn);
+
+ expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
+ aff_chunk_assure_weight(env, new_chunk);
+ pqueue_put(env->chunks, new_chunk, new_chunk->weight);
+ }
+ }
+
+ /* clear obsolete chunks and free some memory */
+ delete_aff_chunk(env, best_chunk);
+ bitset_free(visited);
+ if (best_starts)
+ del_waitq(best_starts);