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 int *map_regs; /**< map the available colors to the available registers */
91 ir_phase ph; /**< phase object holding data for nodes */
92 pqueue *chunks; /**< priority queue for chunks */
93 pset_new_t chunkset; /**< set holding all chunks */
94 be_ifg_t *ifg; /**< the interference graph */
95 const arch_env_t *aenv; /**< the arch environment */
96 copy_opt_t *co; /**< the copy opt object */
99 /* stores coalescing related information for a node */
100 typedef struct _co_mst_irn_t {
101 ir_node *irn; /**< the irn this information belongs to */
102 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
103 bitset_t *adm_colors; /**< set of admissible colors for this irn */
104 ir_node **int_neighs; /**< ARR_D of all interfering neighbours (cached for speed reasons) */
105 int int_aff_neigh; /**< number of interfering affinity neighbours */
106 int col; /**< color currently assigned */
107 int init_col; /**< the initial color */
108 int tmp_col; /**< a temporary assigned color */
109 unsigned fixed : 1; /**< the color is fixed */
110 unsigned tmp_fixed : 1; /**< the color is temporary fixed */
113 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
115 typedef int decide_func_t(co_mst_irn_t *node, int col);
120 * Write a chunk to stderr for debugging.
122 static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
124 if (c->weight_consistent)
125 ir_fprintf(stderr, " $%d ", c->weight);
126 ir_fprintf(stderr, "{");
127 bitset_foreach(c->nodes, idx) {
128 ir_node *n = get_idx_irn(env->co->irg, idx);
129 ir_fprintf(stderr, " %+F,", n);
131 ir_fprintf(stderr, "}");
135 * Dump all admissible colors to stderr.
137 static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
139 if (bitset_popcnt(node->adm_colors) < 1)
140 fprintf(stderr, "no admissible colors?!?");
142 bitset_foreach(node->adm_colors, idx)
143 fprintf(stderr, " %d", idx);
148 * Dump color-cost pairs to stderr.
150 static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
152 for (i = 0; i < env->n_regs; ++i) {
153 if (cost[i].cost == COL_COST_INFEASIBLE)
154 fprintf(stderr, " (%d, INF)", cost[i].col);
156 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
160 #endif /* DEBUG_libfirm */
162 static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
163 return node->tmp_fixed ? node->tmp_col : node->col;
167 * @return 1 if node @p node has color @p col, 0 otherwise.
169 static int decider_has_color(co_mst_irn_t *node, int col) {
170 return get_mst_irn_col(node) == col;
174 * @return 1 if node @p node has not color @p col, 0 otherwise.
176 static int decider_hasnot_color(co_mst_irn_t *node, int col) {
177 return get_mst_irn_col(node) != col;
181 * Always returns true.
183 static int decider_always_yes(co_mst_irn_t *node, int col) {
187 /* > compares two affinity edges by its weight */
188 static int cmp_aff_edge(const void *a, const void *b) {
189 const aff_edge_t *e1 = a;
190 const aff_edge_t *e2 = b;
192 if (e2->weight == e1->weight) {
193 if (e2->src->node_idx == e1->src->node_idx)
194 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
196 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
198 /* sort in descending order */
199 return QSORT_CMP(e2->weight, e1->weight);
202 /* compares to color-cost pairs */
203 static int cmp_col_cost(const void *a, const void *b) {
204 const col_cost_t *c1 = a;
205 const col_cost_t *c2 = b;
207 return c1->cost < c2->cost ? -1 : 1;
211 * Creates a new affinity chunk
213 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
214 aff_chunk_t *c = xmalloc(sizeof(*c));
216 c->weight_consistent = 0;
217 c->nodes = bitset_irg_malloc(env->co->irg);
218 c->id = last_chunk_id++;
219 pset_new_insert(&env->chunkset, c);
224 * Frees all memory allocated by an affinity chunk.
226 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
227 pset_new_remove(&env->chunkset, c);
228 bitset_free(c->nodes);
233 * Adds a node to an affinity chunk
235 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
236 c->weight_consistent = 0;
238 bitset_set(c->nodes, get_irn_idx(node->irn));
242 * In case there is no phase information for irn, initialize it.
244 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
245 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
246 co_mst_env_t *env = ph->priv;
249 const arch_register_req_t *req;
250 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
255 res->chunk = new_aff_chunk(env);
259 res->int_neighs = NULL;
260 res->int_aff_neigh = 0;
261 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
262 res->init_col = res->col;
264 /* add note to new chunk */
265 aff_chunk_add_node(res->chunk, res);
267 DB((dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id));
269 /* set admissible registers */
270 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
272 /* Exclude colors not assignable to the irn */
273 req = arch_get_register_req(env->aenv, irn, -1);
274 if (arch_register_req_is(req, limited))
275 rbitset_copy_to_bitset(req->limited, res->adm_colors);
277 bitset_set_all(res->adm_colors);
279 /* exclude global ignore registers as well */
280 bitset_andnot(res->adm_colors, env->ignore_regs);
282 /* set the number of interfering affinity neighbours to -1, they are calculated later */
283 res->int_aff_neigh = -1;
285 /* build list of interfering neighbours */
287 /* count them first as an obstack array cannot be extended */
288 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
290 res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len);
292 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
293 res->int_neighs[len++] = neigh;
299 * Check if affinity chunk @p chunk interferes with node @p irn.
301 static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
302 co_mst_irn_t *node = get_co_mst_irn(env, irn);
306 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
307 neigh = node->int_neighs[i];
308 if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
316 * Check if there are interference edges from c1 to c2.
317 * @param env The global co_mst environment
319 * @param c2 Another chunk
320 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
322 static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
328 /* check if there is a node in c2 having an interfering neighbor in c1 */
329 bitset_foreach(c2->nodes, idx) {
330 ir_node *n = get_idx_irn(env->co->irg, idx);
332 if (aff_chunk_interferes(env, c1, n))
340 * Let c1 absorb the nodes of c2 (only possible when there
341 * are no interference edges from c1 to c2).
342 * @return 1 if successful, 0 if not possible
344 static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
345 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id));
346 DBG_AFF_CHUNK(env, LEVEL_4, c1);
347 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id));
348 DBG_AFF_CHUNK(env, LEVEL_4, c2);
349 DB((dbg, LEVEL_4, "\n"));
351 if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
354 bitset_or(c1->nodes, c2->nodes);
355 c1->weight_consistent = 0;
357 bitset_foreach(c2->nodes, idx) {
358 ir_node *n = get_idx_irn(env->co->irg, idx);
359 co_mst_irn_t *mn = get_co_mst_irn(env, n);
363 DB((dbg, LEVEL_4, " ... absorbed, c2 deleted\n"));
364 delete_aff_chunk(env, c2);
367 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
372 * Returns the affinity chunk of @p irn or creates a new
373 * one with @p irn as element if there is none assigned.
375 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
376 co_mst_irn_t *node = get_co_mst_irn(env, irn);
377 assert(node->chunk && "Node should have a chunk.");
382 * Assures that the weight of the given chunk is consistent.
384 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
385 if (! c->weight_consistent) {
389 bitset_foreach(c->nodes, idx) {
390 ir_node *n = get_idx_irn(env->co->irg, idx);
391 affinity_node_t *an = get_affinity_info(env->co, n);
395 co_gs_foreach_neighb(an, neigh) {
396 ir_node *m = neigh->irn;
397 int m_idx = get_irn_idx(m);
399 /* skip ignore nodes */
400 if (arch_irn_is(env->aenv, m, ignore))
403 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
409 c->weight_consistent = 1;
414 * Count the number of interfering affinity neighbours
416 static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
418 ir_node *irn = an->irn;
419 co_mst_irn_t *node = get_co_mst_irn(env, irn);
422 co_gs_foreach_neighb(an, neigh) {
423 ir_node *n = neigh->irn;
426 /* skip ignore nodes */
427 if (arch_irn_is(env->aenv, n, ignore))
430 /* check if the affinity neighbour interfere */
431 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
432 if (node->int_neighs[i] == n) {
443 * Build chunks of nodes connected by affinity edges.
444 * We start at the heaviest affinity edge.
445 * The chunks of the two edge-defining nodes will be
446 * merged if there are no interference edges from one
447 * chunk to the other.
449 static void build_affinity_chunks(co_mst_env_t *env) {
450 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
451 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
454 aff_chunk_t *curr_chunk;
455 pset_new_iterator_t iter;
457 /* at first we create the affinity edge objects */
458 be_ifg_foreach_node(env->ifg, nodes_it, n) {
459 int n_idx = get_irn_idx(n);
463 /* skip ignore nodes */
464 if (arch_irn_is(env->aenv, n, ignore))
467 n1 = get_co_mst_irn(env, n);
468 an = get_affinity_info(env->co, n);
473 if (n1->int_aff_neigh < 0)
474 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
475 co_gs_foreach_neighb(an, neigh) {
476 ir_node *m = neigh->irn;
477 int m_idx = get_irn_idx(m);
479 /* record the edge in only one direction */
484 /* skip ignore nodes */
485 if (arch_irn_is(env->aenv, m, ignore))
491 n2 = get_co_mst_irn(env, m);
492 if (n2->int_aff_neigh < 0) {
493 affinity_node_t *am = get_affinity_info(env->co, m);
494 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
496 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
497 ARR_APP1(aff_edge_t, edges, edge);
503 /* now: sort edges and build the affinity chunks */
504 len = ARR_LEN(edges);
505 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
506 for (i = 0; i < len; ++i) {
507 aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src);
508 aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt);
510 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
512 (void)aff_chunk_absorb(env, c1, c2);
515 /* now insert all chunks into a priority queue */
516 foreach_pset_new(&env->chunkset, curr_chunk, iter) {
517 aff_chunk_assure_weight(env, curr_chunk);
519 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
520 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
521 DBG((dbg, LEVEL_1, "\n"));
524 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
531 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
533 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
534 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
536 waitq *nodes = new_waitq();
538 DBG((dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn));
540 /* init queue and chunk */
541 waitq_put(nodes, node);
542 bitset_set(visited, get_irn_idx(node->irn));
543 aff_chunk_add_node(chunk, node);
544 DB((dbg, LEVEL_1, " %+F", node->irn));
546 /* as long as there are nodes in the queue */
547 while (! waitq_empty(nodes)) {
548 co_mst_irn_t *n = waitq_get(nodes);
549 affinity_node_t *an = get_affinity_info(env->co, n->irn);
551 /* check all affinity neighbors */
554 co_gs_foreach_neighb(an, neigh) {
555 ir_node *m = neigh->irn;
556 int m_idx = get_irn_idx(m);
559 /* skip ignore nodes */
560 if (arch_irn_is(env->aenv, m, ignore))
563 n2 = get_co_mst_irn(env, m);
565 if (! bitset_is_set(visited, m_idx) &&
568 ! aff_chunk_interferes(env, chunk, m) &&
569 bitset_is_set(orig_chunk->nodes, m_idx))
572 following conditions are met:
573 - neighbour is not visited
574 - neighbour likes the color
575 - neighbour has not yet a fixed color
576 - the new chunk doesn't interfere with the neighbour
577 - neighbour belongs or belonged once to the original chunk
579 bitset_set(visited, m_idx);
580 aff_chunk_add_node(chunk, n2);
581 DB((dbg, LEVEL_1, " %+F", n2->irn));
582 /* enqueue for further search */
583 waitq_put(nodes, n2);
589 DB((dbg, LEVEL_1, "\n"));
595 * Fragment the given chunk into chunks having given color and not having given color.
597 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
598 bitset_t *visited = bitset_irg_malloc(env->co->irg);
600 aff_chunk_t *best = NULL;
602 bitset_foreach(c->nodes, idx) {
605 aff_chunk_t *tmp_chunk;
606 decide_func_t *decider;
609 if (bitset_is_set(visited, idx))
612 irn = get_idx_irn(env->co->irg, idx);
613 node = get_co_mst_irn(env, irn);
615 if (get_mst_irn_col(node) == col) {
616 decider = decider_has_color;
620 decider = decider_hasnot_color;
624 /* create a new chunk starting at current node */
625 tmp_chunk = new_aff_chunk(env);
626 waitq_put(tmp, tmp_chunk);
627 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
628 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
630 /* remember the local best */
631 aff_chunk_assure_weight(env, tmp_chunk);
632 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
636 assert(best && "No chunk found?");
637 bitset_free(visited);
642 * Initializes an array of color-cost pairs.
643 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
645 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
648 for (i = 0; i < env->n_regs; ++i) {
650 if (bitset_is_set(env->ignore_regs, i))
651 cost[i].cost = COL_COST_INFEASIBLE;
658 * Initializes an array of color-cost pairs.
659 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
661 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
662 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
663 col_cost_init(env, cost, COL_COST_INFEASIBLE);
670 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
671 * ATTENTION: the queue is empty after calling this function!
673 static INLINE void reject_coloring(waitq *nodes) {
674 while (! waitq_empty(nodes)) {
675 co_mst_irn_t *n = waitq_get(nodes);
681 * Determines the costs for each color if it would be assigned to node @p node.
683 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
684 affinity_node_t *an = get_affinity_info(env->co, node->irn);
688 col_cost_init(env, costs, 0.0);
690 /* calculate (negative) costs for affinity neighbours */
692 co_gs_foreach_neighb(an, aff_neigh) {
693 ir_node *m = aff_neigh->irn;
697 /* skip ignore nodes */
698 if (arch_irn_is(env->aenv, m, ignore))
701 neigh = get_co_mst_irn(env, m);
702 c = (double)aff_neigh->costs;
704 /* calculate costs for fixed affinity neighbours */
705 if (neigh->tmp_fixed || neigh->fixed) {
706 int col = get_mst_irn_col(neigh);
707 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
712 /* calculate (positive) costs for interfering neighbours */
713 for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
718 int_neigh = node->int_neighs[i];
720 /* skip ignore nodes */
721 if (arch_irn_is(env->aenv, int_neigh, ignore))
724 neigh = get_co_mst_irn(env, int_neigh);
725 col = get_mst_irn_col(neigh);
726 col_cnt = bitset_popcnt(neigh->adm_colors);
728 if (neigh->tmp_fixed || neigh->fixed) {
729 /* colors of fixed interfering neighbours are infeasible */
730 costs[col].cost = COL_COST_INFEASIBLE;
732 else if (col_cnt < env->k) {
733 /* calculate costs for constrained interfering neighbours */
734 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
736 bitset_foreach_clear(neigh->adm_colors, idx) {
737 /* check only explicitly forbidden colors (skip global forbidden ones) */
738 if (! bitset_is_set(env->ignore_regs, idx)) {
739 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
745 /* set all not admissible colors to COL_COST_INFEASIBLE */
746 bitset_foreach_clear(node->adm_colors, idx)
747 costs[idx].cost = COL_COST_INFEASIBLE;
750 /* need forward declaration due to recursive call */
751 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
754 * Tries to change node to a color but @p explude_col.
755 * @return 1 if succeeded, 0 otherwise.
757 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
758 int col = get_mst_irn_col(node);
761 /* neighbours has already a different color -> good, temporary fix it */
762 if (col != exclude_col) {
765 waitq_put(changed_ones, node);
769 /* The node has the color it should not have _and_ has not been visited yet. */
770 if (! (node->tmp_fixed || node->fixed)) {
771 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
773 /* Get the costs for giving the node a specific color. */
774 determine_color_costs(env, node, costs);
776 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
777 costs[exclude_col].cost = COL_COST_INFEASIBLE;
779 /* sort the colors according costs, cheapest first. */
780 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
782 /* Try recoloring the node using the color list. */
783 res = recolor_nodes(env, node, costs, changed_ones);
790 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
791 * ATTENTION: Expect @p costs already sorted by increasing costs.
792 * @return 1 if coloring could be applied, 0 otherwise.
794 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
796 waitq *local_changed = new_waitq();
797 waitq *tmp = new_waitq();
799 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
800 DBG_COL_COST(env, LEVEL_1, costs);
801 DB((dbg, LEVEL_1, "\n"));
803 for (i = 0; i < env->n_regs; ++i) {
804 int tgt_col = costs[i].col;
808 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
809 if (costs[i].cost == COL_COST_INFEASIBLE) {
811 del_waitq(local_changed);
816 /* Set the new color of the node and mark the node as temporarily fixed. */
817 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
819 node->tmp_col = tgt_col;
821 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
822 waitq_put(local_changed, node);
824 /* try to color all interfering neighbours with current color forbidden */
825 for (j = 0; j < ARR_LEN(node->int_neighs); ++j) {
829 neigh = node->int_neighs[j];
831 /* skip ignore nodes */
832 if (arch_irn_is(env->aenv, neigh, ignore))
835 nn = get_co_mst_irn(env, neigh);
838 Try to change the color of the neighbor and record all nodes which
839 get changed in the tmp list. Add this list to the "changed" list for
840 that color. If we did not succeed to change the color of the neighbor,
841 we bail out and try the next color.
843 if (get_mst_irn_col(nn) == tgt_col) {
844 /* try to color neighbour with tgt_col forbidden */
845 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
847 /* join lists of changed nodes */
848 while (! waitq_empty(tmp))
849 waitq_put(local_changed, waitq_get(tmp));
857 We managed to assign the target color to all neighbors, so from the perspective
858 of the current node, every thing was ok and we can return safely.
861 /* append the local_changed ones to global ones */
862 while (! waitq_empty(local_changed))
863 waitq_put(changed_ones, waitq_get(local_changed));
864 del_waitq(local_changed);
869 /* coloring of neighbours failed, so we try next color */
870 reject_coloring(local_changed);
874 del_waitq(local_changed);
880 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
881 * @return 1 if color @p col could be applied, 0 otherwise
883 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
884 int col = get_mst_irn_col(node);
886 /* if node already has the target color -> good, temporary fix it */
887 if (col == tgt_col) {
888 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
889 if (! node->tmp_fixed) {
891 node->tmp_col = tgt_col;
892 waitq_put(changed_ones, node);
898 Node has not yet a fixed color and target color is admissible
899 -> try to recolor node and it's affinity neighbours
901 if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
902 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
905 col_cost_init_single(env, costs, tgt_col);
907 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
908 res = recolor_nodes(env, node, costs, changed_ones);
909 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
915 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
916 if (node->fixed || node->tmp_fixed)
917 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
919 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
920 dbg_admissible_colors(env, node);
921 DB((dbg, LEVEL_4, ")\n"));
930 * Tries to color an affinity chunk (or at least a part of it).
931 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
933 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
934 aff_chunk_t *best_chunk = NULL;
936 waitq *changed_ones = new_waitq();
937 waitq *tmp_chunks = new_waitq();
941 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
942 DBG_AFF_CHUNK(env, LEVEL_2, c);
943 DB((dbg, LEVEL_2, "\n"));
946 /* check which color is the "best" for the given chunk */
947 for (col = 0; col < env->k; ++col) {
948 int reg_col = env->map_regs[col];
950 aff_chunk_t *local_best;
952 DB((dbg, LEVEL_3, "\ttrying color %d\n", reg_col));
954 /* try to bring all nodes of given chunk to the current color. */
955 bitset_foreach(c->nodes, idx) {
956 ir_node *irn = get_idx_irn(env->co->irg, idx);
957 co_mst_irn_t *node = get_co_mst_irn(env, irn);
959 assert(! node->fixed && "Node must not have a fixed color.");
961 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, reg_col));
962 one_good |= change_node_color(env, node, reg_col, changed_ones);
963 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, reg_col, one_good ? "succeeded" : "failed"));
966 /* try next color when failed */
970 /* fragment the chunk according to the coloring */
971 local_best = fragment_chunk(env, reg_col, c, tmp_chunks);
973 /* search the best of the good list
974 and make it the new best if it is better than the current */
976 aff_chunk_assure_weight(env, local_best);
978 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, reg_col));
979 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
981 if (! best_chunk || best_chunk->weight < local_best->weight) {
982 best_chunk = local_best;
983 best_color = reg_col;
984 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
986 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
990 /* reject the coloring and bring the coloring to the initial state */
991 reject_coloring(changed_ones);
994 /* free all intermediate created chunks except best one */
995 while (! waitq_empty(tmp_chunks)) {
996 aff_chunk_t *tmp = waitq_get(tmp_chunks);
997 if (tmp != best_chunk)
998 delete_aff_chunk(env, tmp);
1000 del_waitq(tmp_chunks);
1002 /* return if coloring failed */
1004 del_waitq(changed_ones);
1008 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1009 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1010 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1012 /* get the best fragment from the best list and color it */
1013 bitset_foreach(best_chunk->nodes, idx) {
1014 ir_node *irn = get_idx_irn(env->co->irg, idx);
1015 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1018 res = change_node_color(env, node, best_color, changed_ones);
1019 assert(res && "color manifesting failed");
1021 node->chunk = best_chunk;
1024 /* materialize colors on changed nodes */
1025 while (! waitq_empty(changed_ones)) {
1026 co_mst_irn_t *n = waitq_get(changed_ones);
1028 n->col = n->tmp_col;
1031 /* remove the nodes in best chunk from original chunk */
1032 bitset_andnot(c->nodes, best_chunk->nodes);
1034 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1035 bitset_foreach(c->nodes, idx) {
1036 ir_node *n = get_idx_irn(env->co->irg, idx);
1037 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1041 /* fragment the remaining chunk */
1042 visited = bitset_irg_malloc(env->co->irg);
1043 bitset_or(visited, best_chunk->nodes);
1044 bitset_foreach(c->nodes, idx) {
1045 if (! bitset_is_set(visited, idx)) {
1046 aff_chunk_t *new_chunk = new_aff_chunk(env);
1047 ir_node *irn = get_idx_irn(env->co->irg, idx);
1048 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1050 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1051 aff_chunk_assure_weight(env, new_chunk);
1052 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1056 /* clear obsolete chunks and free some memory */
1057 delete_aff_chunk(env, best_chunk);
1058 bitset_free(visited);
1059 del_waitq(changed_ones);
1063 * Main driver for mst safe coalescing algorithm.
1065 int co_solve_heuristic_mst(copy_opt_t *co)
1067 unsigned n_regs = co->cls->n_regs;
1068 bitset_t *ignore_regs = bitset_alloca(n_regs);
1069 unsigned k, idx, num;
1071 co_mst_env_t mst_env;
1074 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1076 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1079 mst_env.map_regs = NEW_ARR_D(int, phase_obst(&mst_env.ph), k);
1080 for (idx = num = 0; idx < n_regs; ++idx) {
1081 if (bitset_is_set(ignore_regs, idx))
1083 mst_env.map_regs[num++] = idx;
1086 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1087 mst_env.n_regs = n_regs;
1089 mst_env.chunks = new_pqueue();
1091 mst_env.ignore_regs = ignore_regs;
1092 mst_env.ifg = co->cenv->ifg;
1093 mst_env.aenv = co->aenv;
1094 pset_new_init(&mst_env.chunkset);
1096 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1098 /* build affinity chunks */
1099 build_affinity_chunks(&mst_env);
1101 /* color chunks as long as there are some */
1102 while (! pqueue_empty(mst_env.chunks)) {
1103 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1105 color_aff_chunk(&mst_env, chunk);
1106 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1107 delete_aff_chunk(&mst_env, chunk);
1110 /* apply coloring */
1111 foreach_phase_irn(&mst_env.ph, irn) {
1112 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1113 const arch_register_t *reg;
1115 if (arch_irn_is(mst_env.aenv, irn, ignore))
1118 assert(mirn->fixed && "Node should have fixed color");
1120 /* skip nodes where color hasn't changed */
1121 if (mirn->init_col == mirn->col)
1124 reg = arch_register_for_index(co->cls, mirn->col);
1125 arch_set_irn_register(co->aenv, irn, reg);
1126 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1129 /* free allocated memory */
1130 del_pqueue(mst_env.chunks);
1131 phase_free(&mst_env.ph);
1132 pset_new_destroy(&mst_env.chunkset);
1137 void be_init_copyheur4(void)
1139 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1142 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);