2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Simple copy minimization heuristics.
23 * @author Christian Wuerdig
27 * This is the C implementation of the mst algorithm
28 * originally written in Java by Sebastian Hack.
29 * (also known as "heur3" :)
30 * Performs simple copy minimization.
34 #endif /* HAVE_CONFIG_H */
41 #include "raw_bitset.h"
42 #include "irphase_t.h"
53 #include "becopyopt_t.h"
56 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
58 #define COL_COST_INFEASIBLE DBL_MAX
59 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
60 #define NEIGHBOUR_CONSTR_COSTS 64.0
62 #define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk));)
63 #define DBG_COL_COST(env, level, cost) DEBUG_ONLY(if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost));)
65 static int last_chunk_id = 0;
67 typedef struct _col_cost_t {
72 typedef struct _aff_chunk_t {
75 unsigned weight_consistent : 1;
79 typedef struct _aff_edge_t {
85 /* main coalescing environment*/
86 typedef struct _co_mst_env_t {
87 int n_regs; /**< number of regs in class */
88 int k; /**< number of non-ignore registers in class */
89 bitset_t *ignore_regs; /**< set containing all global ignore registers */
90 ir_phase ph; /**< phase object holding data for nodes */
91 pqueue *chunks; /**< priority queue for chunks */
92 pset_new_t chunkset; /**< set holding all chunks */
93 be_ifg_t *ifg; /**< the interference graph */
94 const arch_env_t *aenv; /**< the arch environment */
95 copy_opt_t *co; /**< the copy opt object */
98 /* stores coalescing related information for a node */
99 typedef struct _co_mst_irn_t {
100 ir_node *irn; /**< the irn this information belongs to */
101 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
102 bitset_t *adm_colors; /**< set of admissible colors for this irn */
103 ir_node **int_neighs; /**< ARR_D of all interfering neighbours (cached for speed reasons) */
104 int int_aff_neigh; /**< number of interfering affinity neighbours */
105 int col; /**< color currently assigned */
106 int init_col; /**< the initial color */
107 int tmp_col; /**< a temporary assigned color */
108 unsigned fixed : 1; /**< the color is fixed */
109 unsigned tmp_fixed : 1; /**< the color is temporary fixed */
112 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
114 typedef int decide_func_t(co_mst_irn_t *node, int col);
119 * Write a chunk to stderr for debugging.
121 static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
123 if (c->weight_consistent)
124 ir_fprintf(stderr, " $%d ", c->weight);
125 ir_fprintf(stderr, "{");
126 bitset_foreach(c->nodes, idx) {
127 ir_node *n = get_idx_irn(env->co->irg, idx);
128 ir_fprintf(stderr, " %+F,", n);
130 ir_fprintf(stderr, "}");
134 * Dump all admissible colors to stderr.
136 static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
138 if (bitset_popcnt(node->adm_colors) < 1)
139 fprintf(stderr, "no admissible colors?!?");
141 bitset_foreach(node->adm_colors, idx)
142 fprintf(stderr, " %d", idx);
147 * Dump color-cost pairs to stderr.
149 static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
151 for (i = 0; i < env->n_regs; ++i) {
152 if (cost[i].cost == COL_COST_INFEASIBLE)
153 fprintf(stderr, " (%d, INF)", cost[i].col);
155 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
159 #endif /* DEBUG_libfirm */
161 static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
162 return node->tmp_fixed ? node->tmp_col : node->col;
166 * @return 1 if node @p node has color @p col, 0 otherwise.
168 static int decider_has_color(co_mst_irn_t *node, int col) {
169 return get_mst_irn_col(node) == col;
173 * @return 1 if node @p node has not color @p col, 0 otherwise.
175 static int decider_hasnot_color(co_mst_irn_t *node, int col) {
176 return get_mst_irn_col(node) != col;
180 * Always returns true.
182 static int decider_always_yes(co_mst_irn_t *node, int col) {
186 /* > compares two affinity edges by its weight */
187 static int cmp_aff_edge(const void *a, const void *b) {
188 const aff_edge_t *e1 = a;
189 const aff_edge_t *e2 = b;
191 if (e2->weight == e1->weight) {
192 if (e2->src->node_idx == e1->src->node_idx)
193 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
195 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
197 /* sort in descending order */
198 return QSORT_CMP(e2->weight, e1->weight);
201 /* compares to color-cost pairs */
202 static int cmp_col_cost(const void *a, const void *b) {
203 const col_cost_t *c1 = a;
204 const col_cost_t *c2 = b;
206 return c1->cost < c2->cost ? -1 : 1;
210 * Creates a new affinity chunk
212 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
213 aff_chunk_t *c = xmalloc(sizeof(*c));
215 c->weight_consistent = 0;
216 c->nodes = bitset_irg_malloc(env->co->irg);
217 c->id = last_chunk_id++;
218 pset_new_insert(&env->chunkset, c);
223 * Frees all memory allocated by an affinity chunk.
225 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
226 pset_new_remove(&env->chunkset, c);
227 bitset_free(c->nodes);
232 * Adds a node to an affinity chunk
234 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
235 c->weight_consistent = 0;
237 bitset_set(c->nodes, get_irn_idx(node->irn));
241 * In case there is no phase information for irn, initialize it.
243 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
244 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
245 co_mst_env_t *env = ph->priv;
248 const arch_register_req_t *req;
249 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
254 res->chunk = new_aff_chunk(env);
258 res->int_neighs = NULL;
259 res->int_aff_neigh = 0;
260 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
261 res->init_col = res->col;
263 /* add note to new chunk */
264 aff_chunk_add_node(res->chunk, res);
266 DB((dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id));
268 /* set admissible registers */
269 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
271 /* Exclude colors not assignable to the irn */
272 req = arch_get_register_req(env->aenv, irn, -1);
273 if (arch_register_req_is(req, limited))
274 rbitset_copy_to_bitset(req->limited, res->adm_colors);
276 bitset_set_all(res->adm_colors);
278 /* exclude global ignore registers as well */
279 bitset_andnot(res->adm_colors, env->ignore_regs);
281 /* set the number of interfering affinity neighbours to -1, they are calculated later */
282 res->int_aff_neigh = -1;
284 /* build list of interfering neighbours */
286 /* count them first as an obstack array cannot be extended */
287 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
289 res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len);
291 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
292 res->int_neighs[len++] = neigh;
298 * Check if affinity chunk @p chunk interferes with node @p irn.
300 static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
301 co_mst_irn_t *node = get_co_mst_irn(env, irn);
305 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
306 neigh = node->int_neighs[i];
307 if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
315 * Check if there are interference edges from c1 to c2.
316 * @param env The global co_mst environment
318 * @param c2 Another chunk
319 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
321 static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
327 /* check if there is a node in c2 having an interfering neighbor in c1 */
328 bitset_foreach(c2->nodes, idx) {
329 ir_node *n = get_idx_irn(env->co->irg, idx);
331 if (aff_chunk_interferes(env, c1, n))
339 * Let c1 absorb the nodes of c2 (only possible when there
340 * are no interference edges from c1 to c2).
341 * @return 1 if successful, 0 if not possible
343 static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
344 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id));
345 DBG_AFF_CHUNK(env, LEVEL_4, c1);
346 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id));
347 DBG_AFF_CHUNK(env, LEVEL_4, c2);
348 DB((dbg, LEVEL_4, "\n"));
350 if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
353 bitset_or(c1->nodes, c2->nodes);
354 c1->weight_consistent = 0;
356 bitset_foreach(c2->nodes, idx) {
357 ir_node *n = get_idx_irn(env->co->irg, idx);
358 co_mst_irn_t *mn = get_co_mst_irn(env, n);
362 DB((dbg, LEVEL_4, " ... absorbed, c2 deleted\n"));
363 delete_aff_chunk(env, c2);
366 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
371 * Returns the affinity chunk of @p irn or creates a new
372 * one with @p irn as element if there is none assigned.
374 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
375 co_mst_irn_t *node = get_co_mst_irn(env, irn);
376 assert(node->chunk && "Node should have a chunk.");
381 * Assures that the weight of the given chunk is consistent.
383 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
384 if (! c->weight_consistent) {
388 bitset_foreach(c->nodes, idx) {
389 ir_node *n = get_idx_irn(env->co->irg, idx);
390 affinity_node_t *an = get_affinity_info(env->co, n);
394 co_gs_foreach_neighb(an, neigh) {
395 ir_node *m = neigh->irn;
396 int m_idx = get_irn_idx(m);
398 /* skip ignore nodes */
399 if (arch_irn_is(env->aenv, m, ignore))
402 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
408 c->weight_consistent = 1;
413 * Count the number of interfering affinity neighbours
415 static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
417 ir_node *irn = an->irn;
418 co_mst_irn_t *node = get_co_mst_irn(env, irn);
421 co_gs_foreach_neighb(an, neigh) {
422 ir_node *n = neigh->irn;
425 /* skip ignore nodes */
426 if (arch_irn_is(env->aenv, n, ignore))
429 /* check if the affinity neighbour interfere */
430 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
431 if (node->int_neighs[i] == n) {
442 * Build chunks of nodes connected by affinity edges.
443 * We start at the heaviest affinity edge.
444 * The chunks of the two edge-defining nodes will be
445 * merged if there are no interference edges from one
446 * chunk to the other.
448 static void build_affinity_chunks(co_mst_env_t *env) {
449 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
450 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
453 aff_chunk_t *curr_chunk;
454 pset_new_iterator_t iter;
456 /* at first we create the affinity edge objects */
457 be_ifg_foreach_node(env->ifg, nodes_it, n) {
458 int n_idx = get_irn_idx(n);
462 /* skip ignore nodes */
463 if (arch_irn_is(env->aenv, n, ignore))
466 n1 = get_co_mst_irn(env, n);
467 an = get_affinity_info(env->co, n);
472 if (n1->int_aff_neigh < 0)
473 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
474 co_gs_foreach_neighb(an, neigh) {
475 ir_node *m = neigh->irn;
476 int m_idx = get_irn_idx(m);
478 /* record the edge in only one direction */
483 /* skip ignore nodes */
484 if (arch_irn_is(env->aenv, m, ignore))
490 n2 = get_co_mst_irn(env, m);
491 if (n2->int_aff_neigh < 0) {
492 affinity_node_t *am = get_affinity_info(env->co, m);
493 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
495 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
496 ARR_APP1(aff_edge_t, edges, edge);
502 /* now: sort edges and build the affinity chunks */
503 len = ARR_LEN(edges);
504 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
505 for (i = 0; i < len; ++i) {
506 aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src);
507 aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt);
509 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
511 (void)aff_chunk_absorb(env, c1, c2);
514 /* now insert all chunks into a priority queue */
515 foreach_pset_new(&env->chunkset, curr_chunk, iter) {
516 aff_chunk_assure_weight(env, curr_chunk);
518 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
519 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
520 DBG((dbg, LEVEL_1, "\n"));
523 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
530 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
532 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
533 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
535 waitq *nodes = new_waitq();
537 DBG((dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn));
539 /* init queue and chunk */
540 waitq_put(nodes, node);
541 bitset_set(visited, get_irn_idx(node->irn));
542 aff_chunk_add_node(chunk, node);
543 DB((dbg, LEVEL_1, " %+F", node->irn));
545 /* as long as there are nodes in the queue */
546 while (! waitq_empty(nodes)) {
547 co_mst_irn_t *n = waitq_get(nodes);
548 affinity_node_t *an = get_affinity_info(env->co, n->irn);
550 /* check all affinity neighbors */
553 co_gs_foreach_neighb(an, neigh) {
554 ir_node *m = neigh->irn;
555 int m_idx = get_irn_idx(m);
558 /* skip ignore nodes */
559 if (arch_irn_is(env->aenv, m, ignore))
562 n2 = get_co_mst_irn(env, m);
564 if (! bitset_is_set(visited, m_idx) &&
567 ! aff_chunk_interferes(env, chunk, m) &&
568 bitset_is_set(orig_chunk->nodes, m_idx))
571 following conditions are met:
572 - neighbour is not visited
573 - neighbour likes the color
574 - neighbour has not yet a fixed color
575 - the new chunk doesn't interfere with the neighbour
576 - neighbour belongs or belonged once to the original chunk
578 bitset_set(visited, m_idx);
579 aff_chunk_add_node(chunk, n2);
580 DB((dbg, LEVEL_1, " %+F", n2->irn));
581 /* enqueue for further search */
582 waitq_put(nodes, n2);
588 DB((dbg, LEVEL_1, "\n"));
594 * Fragment the given chunk into chunks having given color and not having given color.
596 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
597 bitset_t *visited = bitset_irg_malloc(env->co->irg);
599 aff_chunk_t *best = NULL;
601 bitset_foreach(c->nodes, idx) {
604 aff_chunk_t *tmp_chunk;
605 decide_func_t *decider;
608 if (bitset_is_set(visited, idx))
611 irn = get_idx_irn(env->co->irg, idx);
612 node = get_co_mst_irn(env, irn);
614 if (get_mst_irn_col(node) == col) {
615 decider = decider_has_color;
619 decider = decider_hasnot_color;
623 /* create a new chunk starting at current node */
624 tmp_chunk = new_aff_chunk(env);
625 waitq_put(tmp, tmp_chunk);
626 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
627 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
629 /* remember the local best */
630 aff_chunk_assure_weight(env, tmp_chunk);
631 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
635 assert(best && "No chunk found?");
636 bitset_free(visited);
641 * Initializes an array of color-cost pairs.
642 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
644 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
647 for (i = 0; i < env->n_regs; ++i) {
649 if (bitset_is_set(env->ignore_regs, i))
650 cost[i].cost = COL_COST_INFEASIBLE;
657 * Initializes an array of color-cost pairs.
658 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
660 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
661 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
662 col_cost_init(env, cost, COL_COST_INFEASIBLE);
669 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
670 * ATTENTION: the queue is empty after calling this function!
672 static INLINE void reject_coloring(waitq *nodes) {
673 while (! waitq_empty(nodes)) {
674 co_mst_irn_t *n = waitq_get(nodes);
680 * Determines the costs for each color if it would be assigned to node @p node.
682 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
683 affinity_node_t *an = get_affinity_info(env->co, node->irn);
687 col_cost_init(env, costs, 0.0);
689 /* calculate (negative) costs for affinity neighbours */
691 co_gs_foreach_neighb(an, aff_neigh) {
692 ir_node *m = aff_neigh->irn;
696 /* skip ignore nodes */
697 if (arch_irn_is(env->aenv, m, ignore))
700 neigh = get_co_mst_irn(env, m);
701 c = (double)aff_neigh->costs;
703 /* calculate costs for fixed affinity neighbours */
704 if (neigh->tmp_fixed || neigh->fixed) {
705 int col = get_mst_irn_col(neigh);
706 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
711 /* calculate (positive) costs for interfering neighbours */
712 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
717 int_neigh = node->int_neighs[i];
719 /* skip ignore nodes */
720 if (arch_irn_is(env->aenv, int_neigh, ignore))
723 neigh = get_co_mst_irn(env, int_neigh);
724 col = get_mst_irn_col(neigh);
725 col_cnt = bitset_popcnt(neigh->adm_colors);
727 if (neigh->tmp_fixed || neigh->fixed) {
728 /* colors of fixed interfering neighbours are infeasible */
729 costs[col].cost = COL_COST_INFEASIBLE;
731 else if (col_cnt < env->k) {
732 /* calculate costs for constrained interfering neighbours */
733 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
735 bitset_foreach_clear(neigh->adm_colors, idx) {
736 /* check only explicitly forbidden colors (skip global forbidden ones) */
737 if (! bitset_is_set(env->ignore_regs, idx)) {
738 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
744 /* set all not admissible colors to COL_COST_INFEASIBLE */
745 bitset_foreach_clear(node->adm_colors, idx)
746 costs[idx].cost = COL_COST_INFEASIBLE;
749 /* need forward declaration due to recursive call */
750 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
753 * Tries to change node to a color but @p explude_col.
754 * @return 1 if succeeded, 0 otherwise.
756 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
757 int col = get_mst_irn_col(node);
760 /* neighbours has already a different color -> good, temporary fix it */
761 if (col != exclude_col) {
764 waitq_put(changed_ones, node);
768 /* The node has the color it should not have _and_ has not been visited yet. */
769 if (! (node->tmp_fixed || node->fixed)) {
770 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
772 /* Get the costs for giving the node a specific color. */
773 determine_color_costs(env, node, costs);
775 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
776 costs[exclude_col].cost = COL_COST_INFEASIBLE;
778 /* sort the colors according costs, cheapest first. */
779 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
781 /* Try recoloring the node using the color list. */
782 res = recolor_nodes(env, node, costs, changed_ones);
789 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
790 * ATTENTION: Expect @p costs already sorted by increasing costs.
791 * @return 1 if coloring could be applied, 0 otherwise.
793 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
795 waitq *local_changed = new_waitq();
796 waitq *tmp = new_waitq();
798 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
799 DBG_COL_COST(env, LEVEL_1, costs);
800 DB((dbg, LEVEL_1, "\n"));
802 for (i = 0; i < env->n_regs; ++i) {
803 int tgt_col = costs[i].col;
807 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
808 if (costs[i].cost == COL_COST_INFEASIBLE) {
810 del_waitq(local_changed);
815 /* Set the new color of the node and mark the node as temporarily fixed. */
816 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
818 node->tmp_col = tgt_col;
820 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
821 waitq_put(local_changed, node);
823 /* try to color all interfering neighbours with current color forbidden */
824 for (j = 0; j < ARR_LEN(node->int_neighs); ++j) {
828 neigh = node->int_neighs[j];
830 /* skip ignore nodes */
831 if (arch_irn_is(env->aenv, neigh, ignore))
834 nn = get_co_mst_irn(env, neigh);
837 Try to change the color of the neighbor and record all nodes which
838 get changed in the tmp list. Add this list to the "changed" list for
839 that color. If we did not succeed to change the color of the neighbor,
840 we bail out and try the next color.
842 if (get_mst_irn_col(nn) == tgt_col) {
843 /* try to color neighbour with tgt_col forbidden */
844 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
846 /* join lists of changed nodes */
847 while (! waitq_empty(tmp))
848 waitq_put(local_changed, waitq_get(tmp));
856 We managed to assign the target color to all neighbors, so from the perspective
857 of the current node, every thing was ok and we can return safely.
860 /* append the local_changed ones to global ones */
861 while (! waitq_empty(local_changed))
862 waitq_put(changed_ones, waitq_get(local_changed));
863 del_waitq(local_changed);
868 /* coloring of neighbours failed, so we try next color */
869 reject_coloring(local_changed);
873 del_waitq(local_changed);
879 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
880 * @return 1 if color @p col could be applied, 0 otherwise
882 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
883 int col = get_mst_irn_col(node);
885 /* if node already has the target color -> good, temporary fix it */
886 if (col == tgt_col) {
887 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
888 if (! node->tmp_fixed) {
890 node->tmp_col = tgt_col;
891 waitq_put(changed_ones, node);
897 Node has not yet a fixed color and target color is admissible
898 -> try to recolor node and it's affinity neighbours
900 if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
901 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
904 col_cost_init_single(env, costs, tgt_col);
906 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
907 res = recolor_nodes(env, node, costs, changed_ones);
908 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
914 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
915 if (node->fixed || node->tmp_fixed)
916 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
918 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
919 dbg_admissible_colors(env, node);
920 DB((dbg, LEVEL_4, ")\n"));
929 * Tries to color an affinity chunk (or at least a part of it).
930 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
932 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
933 aff_chunk_t *best_chunk = NULL;
935 waitq *changed_ones = new_waitq();
936 waitq *tmp_chunks = new_waitq();
940 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
941 DBG_AFF_CHUNK(env, LEVEL_2, c);
942 DB((dbg, LEVEL_2, "\n"));
945 /* check which color is the "best" for the given chunk */
946 for (col = 0; col < env->k; ++col) {
948 aff_chunk_t *local_best;
950 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
952 /* try to bring all nodes of given chunk to the current color. */
953 bitset_foreach(c->nodes, idx) {
954 ir_node *irn = get_idx_irn(env->co->irg, idx);
955 co_mst_irn_t *node = get_co_mst_irn(env, irn);
957 assert(! node->fixed && "Node must not have a fixed color.");
959 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
960 one_good |= change_node_color(env, node, col, changed_ones);
961 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
964 /* try next color when failed */
968 /* fragment the chunk according to the coloring */
969 local_best = fragment_chunk(env, col, c, tmp_chunks);
971 /* search the best of the good list
972 and make it the new best if it is better than the current */
974 aff_chunk_assure_weight(env, local_best);
976 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
977 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
979 if (! best_chunk || best_chunk->weight < local_best->weight) {
980 best_chunk = local_best;
982 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
984 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
988 /* reject the coloring and bring the coloring to the initial state */
989 reject_coloring(changed_ones);
992 /* free all intermediate created chunks except best one */
993 while (! waitq_empty(tmp_chunks)) {
994 aff_chunk_t *tmp = waitq_get(tmp_chunks);
995 if (tmp != best_chunk)
996 delete_aff_chunk(env, tmp);
998 del_waitq(tmp_chunks);
1000 /* return if coloring failed */
1002 del_waitq(changed_ones);
1006 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1007 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1008 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1010 /* get the best fragment from the best list and color it */
1011 bitset_foreach(best_chunk->nodes, idx) {
1012 ir_node *irn = get_idx_irn(env->co->irg, idx);
1013 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1016 res = change_node_color(env, node, best_color, changed_ones);
1017 assert(res && "color manifesting failed");
1019 node->chunk = best_chunk;
1022 /* materialize colors on changed nodes */
1023 while (! waitq_empty(changed_ones)) {
1024 co_mst_irn_t *n = waitq_get(changed_ones);
1026 n->col = n->tmp_col;
1029 /* remove the nodes in best chunk from original chunk */
1030 bitset_andnot(c->nodes, best_chunk->nodes);
1032 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1033 bitset_foreach(c->nodes, idx) {
1034 ir_node *n = get_idx_irn(env->co->irg, idx);
1035 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1039 /* fragment the remaining chunk */
1040 visited = bitset_irg_malloc(env->co->irg);
1041 bitset_or(visited, best_chunk->nodes);
1042 bitset_foreach(c->nodes, idx) {
1043 if (! bitset_is_set(visited, idx)) {
1044 aff_chunk_t *new_chunk = new_aff_chunk(env);
1045 ir_node *irn = get_idx_irn(env->co->irg, idx);
1046 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1048 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1049 aff_chunk_assure_weight(env, new_chunk);
1050 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1054 /* clear obsolete chunks and free some memory */
1055 delete_aff_chunk(env, best_chunk);
1056 bitset_free(visited);
1057 del_waitq(changed_ones);
1061 * Main driver for mst safe coalescing algorithm.
1063 int co_solve_heuristic_mst(copy_opt_t *co)
1065 unsigned n_regs = co->cls->n_regs;
1066 bitset_t *ignore_regs = bitset_alloca(n_regs);
1069 co_mst_env_t mst_env;
1072 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1074 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1077 mst_env.n_regs = n_regs;
1079 mst_env.chunks = new_pqueue();
1081 mst_env.ignore_regs = ignore_regs;
1082 mst_env.ifg = co->cenv->ifg;
1083 mst_env.aenv = co->aenv;
1084 pset_new_init(&mst_env.chunkset);
1086 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1088 /* build affinity chunks */
1089 build_affinity_chunks(&mst_env);
1091 /* color chunks as long as there are some */
1092 while (! pqueue_empty(mst_env.chunks)) {
1093 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1095 color_aff_chunk(&mst_env, chunk);
1096 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1097 delete_aff_chunk(&mst_env, chunk);
1100 /* apply coloring */
1101 foreach_phase_irn(&mst_env.ph, irn) {
1102 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1103 const arch_register_t *reg;
1105 if (arch_irn_is(mst_env.aenv, irn, ignore))
1108 assert(mirn->fixed && "Node should have fixed color");
1110 /* skip nodes where color hasn't changed */
1111 if (mirn->init_col == mirn->col)
1114 reg = arch_register_for_index(co->cls, mirn->col);
1115 arch_set_irn_register(co->aenv, irn, reg);
1116 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1119 /* free allocated memory */
1120 del_pqueue(mst_env.chunks);
1121 phase_free(&mst_env.ph);
1122 pset_new_destroy(&mst_env.chunkset);
1127 void be_init_copyheur4(void)
1129 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1132 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);