+ return !node->fixed && node->tmp_col < 0;
+}
+
+/**
+ * Determines the costs for each color if it would be assigned to node @p node.
+ */
+static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
+ int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols));
+ int n_loose = 0;
+ real_t coeff;
+ int i;
+
+ for (i = 0; i < env->n_regs; ++i) {
+ neigh_cols[i] = 0;
+ costs[i].col = i;
+ costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
+ }
+
+ for (i = 0; i < node->n_neighs; ++i) {
+ co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]);
+ int col = get_mst_irn_col(n);
+ if (is_loose(n)) {
+ ++n_loose;
+ ++neigh_cols[col];
+ } else
+ costs[col].cost = REAL(0.0);
+ }
+
+ if (n_loose > 0) {
+ coeff = REAL(1.0) / n_loose;
+ for (i = 0; i < env->n_regs; ++i)
+ costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
+ }
+}
+
+/* need forward declaration due to recursive call */
+static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth, int *max_depth, int *trip);
+
+/**
+ * Tries to change node to a color but @p explude_col.
+ * @return 1 if succeeded, 0 otherwise.
+ */
+static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed, int depth, int *max_depth, int *trip) {
+ int col = get_mst_irn_col(node);
+ int res = 0;
+
+ /* neighbours has already a different color -> good, temporary fix it */
+ if (col != exclude_col) {
+ if (is_loose(node))
+ set_temp_color(node, col, changed);
+ return 1;
+ }
+
+ /* The node has the color it should not have _and_ has not been visited yet. */
+ if (is_loose(node)) {
+ col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
+
+ /* Get the costs for giving the node a specific color. */
+ determine_color_costs(env, node, costs);
+
+ /* Since the node must not have the not_col, set the costs for that color to "infinity" */
+ costs[exclude_col].cost = REAL(0.0);
+
+ /* sort the colors according costs, cheapest first. */
+ qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt);
+
+ /* Try recoloring the node using the color list. */
+ res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip);
+ }
+
+ 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, int depth, int *max_depth, int *trip) {
+ int i;
+ struct list_head local_changed;
+
+ ++*trip;
+ if (depth > *max_depth)
+ *max_depth = depth;
+
+ DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
+ DBG_COL_COST(env, LEVEL_4, costs);
+ DB((dbg, LEVEL_4, "\n"));
+
+ if (depth >= recolor_limit) {
+ DBG((dbg, LEVEL_4, "\tHit recolor limit\n"));
+ return 0;
+ }
+
+ 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 == REAL(0.0)) {
+ DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n"));
+ 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(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, depth + 1, max_depth, trip);
+
+ 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);
+ return 1;
+ }
+ else {
+ /* coloring of neighbours failed, so we try next color */
+ reject_coloring(&local_changed);
+ }
+ }
+
+ DBG((dbg, LEVEL_4, "\tAll colors failed\n"));
+ 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) {
+ 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);
+ 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 = env->single_cols[tgt_col];
+ int res, max_depth, trip;
+
+ max_depth = 0;
+ trip = 0;
+
+ DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
+ res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip);
+ DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
+ stat_ev_int("heur4_recolor_depth_max", max_depth);
+ stat_ev_int("heur4_recolor_trip", trip);
+
+
+ return res;
+ }
+
+#ifdef DEBUG_libfirm
+ 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 n_nodes = ARR_LEN(c->n);
+ int best_color = -1;
+ int n_int_chunks = 0;
+ waitq *tmp_chunks = new_waitq();
+ waitq *best_starts = NULL;
+ col_cost_t *order = alloca(env->n_regs * sizeof(order[0]));
+ bitset_t *visited;
+ int idx, len, i, nidx, pos;
+ struct list_head changed;
+
+ DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
+ DBG_AFF_CHUNK(env, LEVEL_2, c);
+ DB((dbg, LEVEL_2, "\n"));
+
+ stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
+
+ ++env->chunk_visited;
+
+ /* compute color preference */
+ memset(order, 0, env->n_regs * sizeof(order[0]));
+
+ for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
+ const ir_node *n = c->interfere[pos];
+ co_mst_irn_t *node = get_co_mst_irn(env, n);
+ aff_chunk_t *chunk = node->chunk;
+
+ if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
+ assert(!chunk->deleted);
+ chunk->visited = env->chunk_visited;
+ ++n_int_chunks;
+
+ aff_chunk_assure_weight(env, chunk);
+ for (i = 0; i < env->n_regs; ++i)
+ order[i].cost += chunk->color_affinity[i].cost;
+ }
+ }
+
+ for (i = 0; i < env->n_regs; ++i) {
+ real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
+ order[i].col = i;
+ order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
+ }
+
+ qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
+
+ DBG_COL_COST(env, LEVEL_2, order);
+ 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 (i = 0; i < env->k; ++i) {
+ int col = order[i].col;
+ waitq *good_starts = new_waitq();
+ aff_chunk_t *local_best;
+ int n_succeeded;
+
+ /* skip ignore colors */
+ if (bitset_is_set(env->ignore_regs, col))
+ continue;
+
+ DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
+
+ n_succeeded = 0;
+
+ /* try to bring all nodes of given chunk to the current color. */
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ const ir_node *irn = c->n[idx];
+ co_mst_irn_t *node = get_co_mst_irn(env, irn);
+ int good;
+
+ 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.
+ */
+ INIT_LIST_HEAD(&changed);
+ stat_ev_tim_push();
+ good = change_node_color(env, node, col, &changed);
+ stat_ev_tim_pop("heur4_recolor");
+ if (good) {
+ waitq_put(good_starts, node);
+ materialize_coloring(&changed);
+ node->fixed = 1;
+ }
+
+ else
+ reject_coloring(&changed);
+
+ n_succeeded += good;
+ DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
+ }
+
+ /* unfix all nodes */
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
+ node->fixed = 0;
+ }
+
+ /* try next color when failed */
+ if (n_succeeded == 0)
+ 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_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
+ DBG_AFF_CHUNK(env, LEVEL_3, 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_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
+ } else {
+ DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
+ del_waitq(good_starts);
+ }
+ }
+ else {
+ del_waitq(good_starts);
+ }
+
+ /* if all nodes were recolored, bail out */
+ if (n_succeeded == n_nodes)
+ break;
+ }
+
+ stat_ev_int("heur4_colors_tried", i);
+
+ /* 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 #%u ", best_chunk->id));
+ DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
+ DB((dbg, LEVEL_2, "using color %d\n", best_color));
+
+ for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
+ const 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 #%u\n", best_color, node->irn, best_chunk->id));
+ INIT_LIST_HEAD(&changed);
+ stat_ev_tim_push();
+ res = change_node_color(env, node, best_color, &changed);
+ stat_ev_tim_pop("heur4_recolor");
+ if (res) {
+ materialize_coloring(&changed);
+ node->fixed = 1;
+ }
+ assert(list_empty(&changed));
+ }
+
+ /* remove the nodes in best chunk from original chunk */
+ len = ARR_LEN(best_chunk->n);
+ for (idx = 0; idx < len; ++idx) {
+ const ir_node *irn = best_chunk->n[idx];
+ int pos = nodes_bsearch(c->n, irn);
+
+ if (pos > 0)
+ c->n[pos] = NULL;
+ }
+ len = ARR_LEN(c->n);
+ for (idx = nidx = 0; idx < len; ++idx) {
+ const ir_node *irn = c->n[idx];
+
+ if (irn != NULL) {
+ c->n[nidx++] = irn;
+ }
+ }
+ ARR_SHRINKLEN(c->n, nidx);
+
+
+ /* 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) {
+ const 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);
+ for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
+ bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
+
+ for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
+ const 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);
+ }
+ }
+
+ for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
+ const ir_node *n = best_chunk->n[idx];
+ co_mst_irn_t *nn = get_co_mst_irn(env, n);
+ nn->chunk = NULL;
+ }
+
+ /* clear obsolete chunks and free some memory */
+ delete_aff_chunk(env, best_chunk);
+ bitset_free(visited);
+ if (best_starts)
+ del_waitq(best_starts);
+
+ stat_ev_ctx_pop("heur4_color_chunk");
+}
+
+/**
+ * Main driver for mst safe coalescing algorithm.
+ */
+int co_solve_heuristic_mst(copy_opt_t *co) {
+ unsigned n_regs = co->cls->n_regs;
+ bitset_t *ignore_regs = bitset_alloca(n_regs);
+ unsigned i, j, k;
+ ir_node *irn;
+ co_mst_env_t mst_env;
+
+ last_chunk_id = 0;
+
+ stat_ev_tim_push();