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(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0))
63 #define DBG_COL_COST(env, level, cost) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0))
65 static int last_chunk_id = 0;
67 typedef struct _col_cost_t {
75 typedef struct _aff_chunk_t {
76 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
77 int weight; /**< Weight of this chunk */
78 unsigned weight_consistent:1; /**< Set if the weight is consistent. */
79 int id; /**< For debugging: An id of this chunk. */
85 typedef struct _aff_edge_t {
86 ir_node *src; /**< Source node. */
87 ir_node *tgt; /**< Target node. */
88 double weight; /**< The weight of this edge. */
91 /* main coalescing environment */
92 typedef struct _co_mst_env_t {
93 int n_regs; /**< number of regs in class */
94 int k; /**< number of non-ignore registers in class */
95 bitset_t *ignore_regs; /**< set containing all global ignore registers */
96 int *map_regs; /**< map the available colors to the available registers */
97 ir_phase ph; /**< phase object holding data for nodes */
98 pqueue *chunks; /**< priority queue for chunks */
99 pset_new_t chunkset; /**< set holding all chunks */
100 be_ifg_t *ifg; /**< the interference graph */
101 const arch_env_t *aenv; /**< the arch environment */
102 copy_opt_t *co; /**< the copy opt object */
105 /* stores coalescing related information for a node */
106 typedef struct _co_mst_irn_t {
107 ir_node *irn; /**< the irn this information belongs to */
108 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
109 bitset_t *adm_colors; /**< set of admissible colors for this irn */
110 ir_node **int_neighs; /**< ARR_D of all interfering neighbours (cached for speed reasons) */
111 int int_aff_neigh; /**< number of interfering affinity neighbours */
112 int col; /**< color currently assigned */
113 int init_col; /**< the initial color */
114 int tmp_col; /**< a temporary assigned color */
115 unsigned fixed : 1; /**< the color is fixed */
116 unsigned tmp_fixed : 1; /**< the color is temporary fixed */
119 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
121 typedef int decide_func_t(co_mst_irn_t *node, int col);
126 * Write a chunk to stderr for debugging.
128 static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
130 if (c->weight_consistent)
131 ir_fprintf(stderr, " $%d ", c->weight);
132 ir_fprintf(stderr, "{");
133 bitset_foreach(c->nodes, idx) {
134 ir_node *n = get_idx_irn(env->co->irg, idx);
135 ir_fprintf(stderr, " %+F,", n);
137 ir_fprintf(stderr, "}");
141 * Dump all admissible colors to stderr.
143 static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
145 if (bitset_popcnt(node->adm_colors) < 1)
146 fprintf(stderr, "no admissible colors?!?");
148 bitset_foreach(node->adm_colors, idx)
149 fprintf(stderr, " %d", idx);
154 * Dump color-cost pairs to stderr.
156 static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
158 for (i = 0; i < env->n_regs; ++i) {
159 if (cost[i].cost == COL_COST_INFEASIBLE)
160 fprintf(stderr, " (%d, INF)", cost[i].col);
162 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
166 #endif /* DEBUG_libfirm */
168 static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
169 return node->tmp_fixed ? node->tmp_col : node->col;
173 * @return 1 if node @p node has color @p col, 0 otherwise.
175 static int decider_has_color(co_mst_irn_t *node, int col) {
176 return get_mst_irn_col(node) == col;
180 * @return 1 if node @p node has not color @p col, 0 otherwise.
182 static int decider_hasnot_color(co_mst_irn_t *node, int col) {
183 return get_mst_irn_col(node) != col;
187 * Always returns true.
189 static int decider_always_yes(co_mst_irn_t *node, int col) {
193 /** compares two affinity edges by its weight */
194 static int cmp_aff_edge(const void *a, const void *b) {
195 const aff_edge_t *e1 = a;
196 const aff_edge_t *e2 = b;
198 if (e2->weight == e1->weight) {
199 if (e2->src->node_idx == e1->src->node_idx)
200 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
202 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
204 /* sort in descending order */
205 return QSORT_CMP(e2->weight, e1->weight);
208 /** compares to color-cost pairs */
209 static int cmp_col_cost(const void *a, const void *b) {
210 const col_cost_t *c1 = a;
211 const col_cost_t *c2 = b;
213 return c1->cost < c2->cost ? -1 : 1;
217 * Creates a new affinity chunk
219 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
220 aff_chunk_t *c = xmalloc(sizeof(*c));
222 c->weight_consistent = 0;
223 c->nodes = bitset_irg_malloc(env->co->irg);
224 c->id = last_chunk_id++;
225 pset_new_insert(&env->chunkset, c);
230 * Frees all memory allocated by an affinity chunk.
232 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
233 pset_new_remove(&env->chunkset, c);
234 bitset_free(c->nodes);
239 * Adds a node to an affinity chunk
241 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
242 c->weight_consistent = 0;
244 bitset_set(c->nodes, get_irn_idx(node->irn));
248 * In case there is no phase information for irn, initialize it.
250 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
251 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
252 co_mst_env_t *env = ph->priv;
255 const arch_register_req_t *req;
256 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
261 res->chunk = new_aff_chunk(env);
265 res->int_neighs = NULL;
266 res->int_aff_neigh = 0;
267 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
268 res->init_col = res->col;
270 /* add note to new chunk */
271 aff_chunk_add_node(res->chunk, res);
273 DB((dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id));
275 /* set admissible registers */
276 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
278 /* Exclude colors not assignable to the irn */
279 req = arch_get_register_req(env->aenv, irn, -1);
280 if (arch_register_req_is(req, limited))
281 rbitset_copy_to_bitset(req->limited, res->adm_colors);
283 bitset_set_all(res->adm_colors);
285 /* exclude global ignore registers as well */
286 bitset_andnot(res->adm_colors, env->ignore_regs);
288 /* set the number of interfering affinity neighbours to -1, they are calculated later */
289 res->int_aff_neigh = -1;
291 /* build list of interfering neighbours */
293 /* count them first as an obstack array cannot be extended */
294 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
296 res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len);
298 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
299 res->int_neighs[len++] = neigh;
305 * Check if affinity chunk @p chunk interferes with node @p irn.
307 static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
308 co_mst_irn_t *node = get_co_mst_irn(env, irn);
312 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
313 neigh = node->int_neighs[i];
314 if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
322 * Check if there are interference edges from c1 to c2.
323 * @param env The global co_mst environment
325 * @param c2 Another chunk
326 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
328 static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
334 /* check if there is a node in c2 having an interfering neighbor in c1 */
335 bitset_foreach(c2->nodes, idx) {
336 ir_node *n = get_idx_irn(env->co->irg, idx);
338 if (aff_chunk_interferes(env, c1, n))
346 * Let c1 absorb the nodes of c2 (only possible when there
347 * are no interference edges from c1 to c2).
348 * @return 1 if successful, 0 if not possible
350 static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
351 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id));
352 DBG_AFF_CHUNK(env, LEVEL_4, c1);
353 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id));
354 DBG_AFF_CHUNK(env, LEVEL_4, c2);
355 DB((dbg, LEVEL_4, "\n"));
357 if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
360 bitset_or(c1->nodes, c2->nodes);
361 c1->weight_consistent = 0;
363 bitset_foreach(c2->nodes, idx) {
364 ir_node *n = get_idx_irn(env->co->irg, idx);
365 co_mst_irn_t *mn = get_co_mst_irn(env, n);
369 DB((dbg, LEVEL_4, " ... absorbed, c2 deleted\n"));
370 delete_aff_chunk(env, c2);
373 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
378 * Returns the affinity chunk of @p irn or creates a new
379 * one with @p irn as element if there is none assigned.
381 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
382 co_mst_irn_t *node = get_co_mst_irn(env, irn);
383 assert(node->chunk && "Node should have a chunk.");
388 * Assures that the weight of the given chunk is consistent.
390 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
391 if (! c->weight_consistent) {
395 bitset_foreach(c->nodes, idx) {
396 ir_node *n = get_idx_irn(env->co->irg, idx);
397 affinity_node_t *an = get_affinity_info(env->co, n);
401 co_gs_foreach_neighb(an, neigh) {
402 ir_node *m = neigh->irn;
403 int m_idx = get_irn_idx(m);
405 /* skip ignore nodes */
406 if (arch_irn_is(env->aenv, m, ignore))
409 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
415 c->weight_consistent = 1;
420 * Count the number of interfering affinity neighbours
422 static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
424 ir_node *irn = an->irn;
425 co_mst_irn_t *node = get_co_mst_irn(env, irn);
428 co_gs_foreach_neighb(an, neigh) {
429 ir_node *n = neigh->irn;
432 /* skip ignore nodes */
433 if (arch_irn_is(env->aenv, n, ignore))
436 /* check if the affinity neighbour interfere */
437 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
438 if (node->int_neighs[i] == n) {
449 * Build chunks of nodes connected by affinity edges.
450 * We start at the heaviest affinity edge.
451 * The chunks of the two edge-defining nodes will be
452 * merged if there are no interference edges from one
453 * chunk to the other.
455 static void build_affinity_chunks(co_mst_env_t *env) {
456 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
457 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
460 aff_chunk_t *curr_chunk;
461 pset_new_iterator_t iter;
463 /* at first we create the affinity edge objects */
464 be_ifg_foreach_node(env->ifg, nodes_it, n) {
465 int n_idx = get_irn_idx(n);
469 /* skip ignore nodes */
470 if (arch_irn_is(env->aenv, n, ignore))
473 n1 = get_co_mst_irn(env, n);
474 an = get_affinity_info(env->co, n);
479 if (n1->int_aff_neigh < 0)
480 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
481 co_gs_foreach_neighb(an, neigh) {
482 ir_node *m = neigh->irn;
483 int m_idx = get_irn_idx(m);
485 /* record the edge in only one direction */
490 /* skip ignore nodes */
491 if (arch_irn_is(env->aenv, m, ignore))
497 n2 = get_co_mst_irn(env, m);
498 if (n2->int_aff_neigh < 0) {
499 affinity_node_t *am = get_affinity_info(env->co, m);
500 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
502 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
503 ARR_APP1(aff_edge_t, edges, edge);
509 /* now: sort edges and build the affinity chunks */
510 len = ARR_LEN(edges);
511 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
512 for (i = 0; i < len; ++i) {
513 aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src);
514 aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt);
516 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
518 (void)aff_chunk_absorb(env, c1, c2);
521 /* now insert all chunks into a priority queue */
522 foreach_pset_new(&env->chunkset, curr_chunk, iter) {
523 aff_chunk_assure_weight(env, curr_chunk);
525 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
526 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
527 DBG((dbg, LEVEL_1, "\n"));
530 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
537 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
539 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
540 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
542 waitq *nodes = new_waitq();
544 DBG((dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn));
546 /* init queue and chunk */
547 waitq_put(nodes, node);
548 bitset_set(visited, get_irn_idx(node->irn));
549 aff_chunk_add_node(chunk, node);
550 DB((dbg, LEVEL_1, " %+F", node->irn));
552 /* as long as there are nodes in the queue */
553 while (! waitq_empty(nodes)) {
554 co_mst_irn_t *n = waitq_get(nodes);
555 affinity_node_t *an = get_affinity_info(env->co, n->irn);
557 /* check all affinity neighbors */
560 co_gs_foreach_neighb(an, neigh) {
561 ir_node *m = neigh->irn;
562 int m_idx = get_irn_idx(m);
565 /* skip ignore nodes */
566 if (arch_irn_is(env->aenv, m, ignore))
569 n2 = get_co_mst_irn(env, m);
571 if (! bitset_is_set(visited, m_idx) &&
574 ! aff_chunk_interferes(env, chunk, m) &&
575 bitset_is_set(orig_chunk->nodes, m_idx))
578 following conditions are met:
579 - neighbour is not visited
580 - neighbour likes the color
581 - neighbour has not yet a fixed color
582 - the new chunk doesn't interfere with the neighbour
583 - neighbour belongs or belonged once to the original chunk
585 bitset_set(visited, m_idx);
586 aff_chunk_add_node(chunk, n2);
587 DB((dbg, LEVEL_1, " %+F", n2->irn));
588 /* enqueue for further search */
589 waitq_put(nodes, n2);
595 DB((dbg, LEVEL_1, "\n"));
601 * Fragment the given chunk into chunks having given color and not having given color.
603 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
604 bitset_t *visited = bitset_irg_malloc(env->co->irg);
606 aff_chunk_t *best = NULL;
608 bitset_foreach(c->nodes, idx) {
611 aff_chunk_t *tmp_chunk;
612 decide_func_t *decider;
615 if (bitset_is_set(visited, idx))
618 irn = get_idx_irn(env->co->irg, idx);
619 node = get_co_mst_irn(env, irn);
621 if (get_mst_irn_col(node) == col) {
622 decider = decider_has_color;
626 decider = decider_hasnot_color;
630 /* create a new chunk starting at current node */
631 tmp_chunk = new_aff_chunk(env);
632 waitq_put(tmp, tmp_chunk);
633 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
634 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
636 /* remember the local best */
637 aff_chunk_assure_weight(env, tmp_chunk);
638 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
642 assert(best && "No chunk found?");
643 bitset_free(visited);
648 * Initializes an array of color-cost pairs.
649 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
651 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
654 for (i = 0; i < env->n_regs; ++i) {
656 if (bitset_is_set(env->ignore_regs, i))
657 cost[i].cost = COL_COST_INFEASIBLE;
664 * Initializes an array of color-cost pairs.
665 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
667 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
668 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
669 col_cost_init(env, cost, COL_COST_INFEASIBLE);
676 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
677 * ATTENTION: the queue is empty after calling this function!
679 static INLINE void reject_coloring(waitq *nodes) {
680 while (! waitq_empty(nodes)) {
681 co_mst_irn_t *n = waitq_get(nodes);
687 * Determines the costs for each color if it would be assigned to node @p node.
689 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
690 affinity_node_t *an = get_affinity_info(env->co, node->irn);
694 col_cost_init(env, costs, 0.0);
696 /* calculate (negative) costs for affinity neighbours */
698 co_gs_foreach_neighb(an, aff_neigh) {
699 ir_node *m = aff_neigh->irn;
703 /* skip ignore nodes */
704 if (arch_irn_is(env->aenv, m, ignore))
707 neigh = get_co_mst_irn(env, m);
708 c = (double)aff_neigh->costs;
710 /* calculate costs for fixed affinity neighbours */
711 if (neigh->tmp_fixed || neigh->fixed) {
712 int col = get_mst_irn_col(neigh);
713 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
718 /* calculate (positive) costs for interfering neighbours */
719 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
724 int_neigh = node->int_neighs[i];
726 /* skip ignore nodes */
727 if (arch_irn_is(env->aenv, int_neigh, ignore))
730 neigh = get_co_mst_irn(env, int_neigh);
731 col = get_mst_irn_col(neigh);
732 col_cnt = bitset_popcnt(neigh->adm_colors);
734 if (neigh->tmp_fixed || neigh->fixed) {
735 /* colors of fixed interfering neighbours are infeasible */
736 costs[col].cost = COL_COST_INFEASIBLE;
738 else if (col_cnt < env->k) {
739 /* calculate costs for constrained interfering neighbours */
740 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
742 bitset_foreach_clear(neigh->adm_colors, idx) {
743 /* check only explicitly forbidden colors (skip global forbidden ones) */
744 if (! bitset_is_set(env->ignore_regs, idx)) {
745 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
751 /* set all not admissible colors to COL_COST_INFEASIBLE */
752 bitset_foreach_clear(node->adm_colors, idx)
753 costs[idx].cost = COL_COST_INFEASIBLE;
756 /* need forward declaration due to recursive call */
757 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
760 * Tries to change node to a color but @p explude_col.
761 * @return 1 if succeeded, 0 otherwise.
763 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
764 int col = get_mst_irn_col(node);
767 /* neighbours has already a different color -> good, temporary fix it */
768 if (col != exclude_col) {
771 waitq_put(changed_ones, node);
775 /* The node has the color it should not have _and_ has not been visited yet. */
776 if (! (node->tmp_fixed || node->fixed)) {
777 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
779 /* Get the costs for giving the node a specific color. */
780 determine_color_costs(env, node, costs);
782 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
783 costs[exclude_col].cost = COL_COST_INFEASIBLE;
785 /* sort the colors according costs, cheapest first. */
786 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
788 /* Try recoloring the node using the color list. */
789 res = recolor_nodes(env, node, costs, changed_ones);
796 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
797 * ATTENTION: Expect @p costs already sorted by increasing costs.
798 * @return 1 if coloring could be applied, 0 otherwise.
800 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
802 waitq *local_changed = new_waitq();
803 waitq *tmp = new_waitq();
805 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
806 DBG_COL_COST(env, LEVEL_1, costs);
807 DB((dbg, LEVEL_1, "\n"));
809 for (i = 0; i < env->n_regs; ++i) {
810 int tgt_col = costs[i].col;
814 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
815 if (costs[i].cost == COL_COST_INFEASIBLE) {
817 del_waitq(local_changed);
822 /* Set the new color of the node and mark the node as temporarily fixed. */
823 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
825 node->tmp_col = tgt_col;
827 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
828 waitq_put(local_changed, node);
830 /* try to color all interfering neighbours with current color forbidden */
831 for (j = 0; j < ARR_LEN(node->int_neighs); ++j) {
835 neigh = node->int_neighs[j];
837 /* skip ignore nodes */
838 if (arch_irn_is(env->aenv, neigh, ignore))
841 nn = get_co_mst_irn(env, neigh);
844 Try to change the color of the neighbor and record all nodes which
845 get changed in the tmp list. Add this list to the "changed" list for
846 that color. If we did not succeed to change the color of the neighbor,
847 we bail out and try the next color.
849 if (get_mst_irn_col(nn) == tgt_col) {
850 /* try to color neighbour with tgt_col forbidden */
851 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
853 /* join lists of changed nodes */
854 while (! waitq_empty(tmp))
855 waitq_put(local_changed, waitq_get(tmp));
863 We managed to assign the target color to all neighbors, so from the perspective
864 of the current node, every thing was ok and we can return safely.
867 /* append the local_changed ones to global ones */
868 while (! waitq_empty(local_changed))
869 waitq_put(changed_ones, waitq_get(local_changed));
870 del_waitq(local_changed);
875 /* coloring of neighbours failed, so we try next color */
876 reject_coloring(local_changed);
880 del_waitq(local_changed);
886 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
887 * @return 1 if color @p col could be applied, 0 otherwise
889 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
890 int col = get_mst_irn_col(node);
892 /* if node already has the target color -> good, temporary fix it */
893 if (col == tgt_col) {
894 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
895 if (! node->tmp_fixed) {
897 node->tmp_col = tgt_col;
898 waitq_put(changed_ones, node);
904 Node has not yet a fixed color and target color is admissible
905 -> try to recolor node and it's affinity neighbours
907 if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
908 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
911 col_cost_init_single(env, costs, tgt_col);
913 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
914 res = recolor_nodes(env, node, costs, changed_ones);
915 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
921 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
922 if (node->fixed || node->tmp_fixed)
923 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
925 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
926 dbg_admissible_colors(env, node);
927 DB((dbg, LEVEL_4, ")\n"));
936 * Tries to color an affinity chunk (or at least a part of it).
937 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
939 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
940 aff_chunk_t *best_chunk = NULL;
942 waitq *changed_ones = new_waitq();
943 waitq *tmp_chunks = new_waitq();
947 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
948 DBG_AFF_CHUNK(env, LEVEL_2, c);
949 DB((dbg, LEVEL_2, "\n"));
952 /* check which color is the "best" for the given chunk */
953 for (col = 0; col < env->k; ++col) {
954 int reg_col = env->map_regs[col];
956 aff_chunk_t *local_best;
958 DB((dbg, LEVEL_3, "\ttrying color %d\n", reg_col));
960 /* try to bring all nodes of given chunk to the current color. */
961 bitset_foreach(c->nodes, idx) {
962 ir_node *irn = get_idx_irn(env->co->irg, idx);
963 co_mst_irn_t *node = get_co_mst_irn(env, irn);
965 assert(! node->fixed && "Node must not have a fixed color.");
967 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, reg_col));
968 one_good |= change_node_color(env, node, reg_col, changed_ones);
969 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, reg_col, one_good ? "succeeded" : "failed"));
972 /* try next color when failed */
976 /* fragment the chunk according to the coloring */
977 local_best = fragment_chunk(env, reg_col, c, tmp_chunks);
979 /* search the best of the good list
980 and make it the new best if it is better than the current */
982 aff_chunk_assure_weight(env, local_best);
984 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, reg_col));
985 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
987 if (! best_chunk || best_chunk->weight < local_best->weight) {
988 best_chunk = local_best;
989 best_color = reg_col;
990 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
992 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
996 /* reject the coloring and bring the coloring to the initial state */
997 reject_coloring(changed_ones);
1000 /* free all intermediate created chunks except best one */
1001 while (! waitq_empty(tmp_chunks)) {
1002 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1003 if (tmp != best_chunk)
1004 delete_aff_chunk(env, tmp);
1006 del_waitq(tmp_chunks);
1008 /* return if coloring failed */
1010 del_waitq(changed_ones);
1014 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1015 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1016 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1018 /* get the best fragment from the best list and color it */
1019 bitset_foreach(best_chunk->nodes, idx) {
1020 ir_node *irn = get_idx_irn(env->co->irg, idx);
1021 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1024 res = change_node_color(env, node, best_color, changed_ones);
1025 assert(res && "color manifesting failed");
1027 node->chunk = best_chunk;
1030 /* materialize colors on changed nodes */
1031 while (! waitq_empty(changed_ones)) {
1032 co_mst_irn_t *n = waitq_get(changed_ones);
1034 n->col = n->tmp_col;
1037 /* remove the nodes in best chunk from original chunk */
1038 bitset_andnot(c->nodes, best_chunk->nodes);
1040 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1041 bitset_foreach(c->nodes, idx) {
1042 ir_node *n = get_idx_irn(env->co->irg, idx);
1043 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1047 /* fragment the remaining chunk */
1048 visited = bitset_irg_malloc(env->co->irg);
1049 bitset_or(visited, best_chunk->nodes);
1050 bitset_foreach(c->nodes, idx) {
1051 if (! bitset_is_set(visited, idx)) {
1052 aff_chunk_t *new_chunk = new_aff_chunk(env);
1053 ir_node *irn = get_idx_irn(env->co->irg, idx);
1054 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1056 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1057 aff_chunk_assure_weight(env, new_chunk);
1058 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1062 /* clear obsolete chunks and free some memory */
1063 delete_aff_chunk(env, best_chunk);
1064 bitset_free(visited);
1065 del_waitq(changed_ones);
1069 * Main driver for mst safe coalescing algorithm.
1071 int co_solve_heuristic_mst(copy_opt_t *co)
1073 unsigned n_regs = co->cls->n_regs;
1074 bitset_t *ignore_regs = bitset_alloca(n_regs);
1075 unsigned k, idx, num;
1077 co_mst_env_t mst_env;
1080 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1082 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1085 /* Create a color to register number map. In some architectures registers are ignore "in the middle"
1086 of the register set. */
1087 mst_env.map_regs = NEW_ARR_D(int, phase_obst(&mst_env.ph), k);
1088 for (idx = num = 0; idx < n_regs; ++idx) {
1089 if (bitset_is_set(ignore_regs, idx))
1091 mst_env.map_regs[num++] = idx;
1095 mst_env.n_regs = n_regs;
1097 mst_env.chunks = new_pqueue();
1099 mst_env.ignore_regs = ignore_regs;
1100 mst_env.ifg = co->cenv->ifg;
1101 mst_env.aenv = co->aenv;
1102 pset_new_init(&mst_env.chunkset);
1104 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1106 /* build affinity chunks */
1107 build_affinity_chunks(&mst_env);
1109 /* color chunks as long as there are some */
1110 while (! pqueue_empty(mst_env.chunks)) {
1111 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1113 color_aff_chunk(&mst_env, chunk);
1114 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1115 delete_aff_chunk(&mst_env, chunk);
1118 /* apply coloring */
1119 foreach_phase_irn(&mst_env.ph, irn) {
1120 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1121 const arch_register_t *reg;
1123 if (arch_irn_is(mst_env.aenv, irn, ignore))
1126 assert(mirn->fixed && "Node should have fixed color");
1128 /* skip nodes where color hasn't changed */
1129 if (mirn->init_col == mirn->col)
1132 reg = arch_register_for_index(co->cls, mirn->col);
1133 arch_set_irn_register(co->aenv, irn, reg);
1134 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1137 /* free allocated memory */
1138 del_pqueue(mst_env.chunks);
1139 phase_free(&mst_env.ph);
1140 pset_new_destroy(&mst_env.chunkset);
1145 void be_init_copyheur4(void) {
1146 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1149 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);