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"
54 #include "becopyopt_t.h"
57 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
59 #define COL_COST_INFEASIBLE DBL_MAX
60 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
61 #define NEIGHBOUR_CONSTR_COSTS 64.0
63 #define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0))
64 #define DBG_COL_COST(env, level, cost) DEBUG_ONLY(do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0))
66 static int last_chunk_id = 0;
68 typedef struct _col_cost_t {
76 typedef struct _aff_chunk_t {
77 ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
78 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
79 bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
80 int weight; /**< Weight of this chunk */
81 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
82 unsigned deleted : 1; /**< Set if the was deleted. */
83 int id; /**< For debugging: An id of this chunk. */
89 typedef struct _aff_edge_t {
90 ir_node *src; /**< Source node. */
91 ir_node *tgt; /**< Target node. */
92 double weight; /**< The weight of this edge. */
95 /* main coalescing environment */
96 typedef struct _co_mst_env_t {
97 int n_regs; /**< number of regs in class */
98 int k; /**< number of non-ignore registers in class */
99 bitset_t *ignore_regs; /**< set containing all global ignore registers */
100 ir_phase ph; /**< phase object holding data for nodes */
101 pqueue *chunks; /**< priority queue for chunks */
102 pset *chunkset; /**< set holding all chunks */
103 be_ifg_t *ifg; /**< the interference graph */
104 const arch_env_t *aenv; /**< the arch environment */
105 copy_opt_t *co; /**< the copy opt object */
108 /* stores coalescing related information for a node */
109 typedef struct _co_mst_irn_t {
110 ir_node *irn; /**< the irn this information belongs to */
111 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
112 bitset_t *adm_colors; /**< set of admissible colors for this irn */
113 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
114 int n_neighs; /**< length of the interfering neighbours array. */
115 int int_aff_neigh; /**< number of interfering affinity neighbours */
116 int col; /**< color currently assigned */
117 int init_col; /**< the initial color */
118 int tmp_col; /**< a temporary assigned color */
119 unsigned fixed : 1; /**< the color is fixed */
120 unsigned tmp_fixed : 1; /**< the color is temporary fixed */
123 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
125 typedef int decide_func_t(const co_mst_irn_t *node, int col);
130 * Write a chunk to stderr for debugging.
132 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
134 if (c->weight_consistent)
135 ir_fprintf(stderr, " $%d ", c->weight);
136 ir_fprintf(stderr, "{");
137 bitset_foreach(c->nodes, idx) {
138 ir_node *n = get_idx_irn(env->co->irg, idx);
139 ir_fprintf(stderr, " %+F,", n);
141 ir_fprintf(stderr, "}");
145 * Dump all admissible colors to stderr.
147 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
151 if (bitset_popcnt(node->adm_colors) < 1)
152 fprintf(stderr, "no admissible colors?!?");
154 bitset_foreach(node->adm_colors, idx)
155 fprintf(stderr, " %d", idx);
160 * Dump color-cost pairs to stderr.
162 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
164 for (i = 0; i < env->n_regs; ++i) {
165 if (cost[i].cost == COL_COST_INFEASIBLE)
166 fprintf(stderr, " (%d, INF)", cost[i].col);
168 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
172 #endif /* DEBUG_libfirm */
174 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
175 return node->tmp_fixed ? node->tmp_col : node->col;
179 * @return 1 if node @p node has color @p col, 0 otherwise.
181 static int decider_has_color(const co_mst_irn_t *node, int col) {
182 return get_mst_irn_col(node) == col;
186 * @return 1 if node @p node has not color @p col, 0 otherwise.
188 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
189 return get_mst_irn_col(node) != col;
193 * Always returns true.
195 static int decider_always_yes(const co_mst_irn_t *node, int col) {
201 /** compares two affinity edges by its weight */
202 static int cmp_aff_edge(const void *a, const void *b) {
203 const aff_edge_t *e1 = a;
204 const aff_edge_t *e2 = b;
206 if (e2->weight == e1->weight) {
207 if (e2->src->node_idx == e1->src->node_idx)
208 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
210 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
212 /* sort in descending order */
213 return QSORT_CMP(e2->weight, e1->weight);
216 /** compares to color-cost pairs */
217 static int cmp_col_cost(const void *a, const void *b) {
218 const col_cost_t *c1 = a;
219 const col_cost_t *c2 = b;
221 return c1->cost < c2->cost ? -1 : 1;
225 * Creates a new affinity chunk
227 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
228 aff_chunk_t *c = xmalloc(sizeof(*c));
230 c->weight_consistent = 0;
231 c->n = NEW_ARR_F(ir_node *, 0);
232 c->nodes = bitset_irg_malloc(env->co->irg);
233 c->interfere = bitset_irg_malloc(env->co->irg);
234 c->id = last_chunk_id++;
235 pset_insert(env->chunkset, c, c->id);
240 * Frees all memory allocated by an affinity chunk.
242 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
243 pset_remove(env->chunkset, c, c->id);
244 bitset_free(c->nodes);
245 bitset_free(c->interfere);
252 * Adds a node to an affinity chunk
254 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
257 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
260 c->weight_consistent = 0;
262 bitset_set(c->nodes, get_irn_idx(node->irn));
264 ARR_APP1(ir_node *, c->n, node->irn);
266 for (i = node->n_neighs - 1; i >= 0; --i) {
267 ir_node *neigh = node->int_neighs[i];
268 bitset_set(c->interfere, get_irn_idx(neigh));
273 * In case there is no phase information for irn, initialize it.
275 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
276 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
277 co_mst_env_t *env = ph->priv;
280 const arch_register_req_t *req;
281 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
290 res->int_neighs = NULL;
291 res->int_aff_neigh = 0;
292 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
293 res->init_col = res->col;
295 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
297 /* set admissible registers */
298 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
300 /* Exclude colors not assignable to the irn */
301 req = arch_get_register_req(env->aenv, irn, -1);
302 if (arch_register_req_is(req, limited))
303 rbitset_copy_to_bitset(req->limited, res->adm_colors);
305 bitset_set_all(res->adm_colors);
307 /* exclude global ignore registers as well */
308 bitset_andnot(res->adm_colors, env->ignore_regs);
310 /* set the number of interfering affinity neighbours to -1, they are calculated later */
311 res->int_aff_neigh = -1;
313 /* build list of interfering neighbours */
315 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
316 if (! arch_irn_is(env->aenv, neigh, ignore)) {
317 obstack_ptr_grow(phase_obst(ph), neigh);
321 res->int_neighs = obstack_finish(phase_obst(ph));
328 * Check if affinity chunk @p chunk interferes with node @p irn.
330 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
332 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
336 * Check if there are interference edges from c1 to c2.
337 * @param env The global co_mst environment
339 * @param c2 Another chunk
340 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
342 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
348 /* check if there is a node in c2 having an interfering neighbor in c1 */
349 tmp = bitset_alloca(get_irg_last_idx(env->co->irg));
350 tmp = bitset_copy(tmp, c1->interfere);
351 tmp = bitset_and(tmp, c2->nodes);
353 return bitset_popcnt(tmp) > 0;
357 * Returns the affinity chunk of @p irn or creates a new
358 * one with @p irn as element if there is none assigned.
360 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
361 co_mst_irn_t *node = get_co_mst_irn(env, irn);
366 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
367 * are no interference edges from chunk(src) to chunk(tgt)).
368 * @return 1 if successful, 0 if not possible
370 static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
371 aff_chunk_t *c1 = get_aff_chunk(env, src);
372 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
375 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
377 DBG_AFF_CHUNK(env, LEVEL_4, c1);
379 DB((dbg, LEVEL_4, "{%+F}", src));
381 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
383 DBG_AFF_CHUNK(env, LEVEL_4, c2);
385 DB((dbg, LEVEL_4, "{%+F}", tgt));
387 DB((dbg, LEVEL_4, "\n"));
392 /* no chunk exists */
393 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
396 for (i = mirn->n_neighs - 1; i >= 0; --i) {
397 if (mirn->int_neighs[i] == tgt)
401 /* create one containing both nodes */
402 c1 = new_aff_chunk(env);
403 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
404 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
408 /* c2 already exists */
409 if (! aff_chunk_interferes(env, c2, src)) {
410 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
414 } else if (c2 == NULL) {
415 /* c1 already exists */
416 if (! aff_chunk_interferes(env, c1, tgt)) {
417 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
420 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
423 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) {
424 ir_node *n = c2->n[idx];
425 co_mst_irn_t *mn = get_co_mst_irn(env, n);
429 if (! bitset_is_set(c1->nodes, get_irn_idx(n)))
430 ARR_APP1(ir_node *, c1->n, n);
433 bitset_or(c1->nodes, c2->nodes);
434 bitset_or(c1->interfere, c2->interfere);
435 c1->weight_consistent = 0;
437 delete_aff_chunk(env, c2);
440 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
444 DB((dbg, LEVEL_4, " ... absorbed\n"));
449 * Assures that the weight of the given chunk is consistent.
451 static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) {
452 if (! c->weight_consistent) {
456 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
457 ir_node *n = c->n[idx];
458 const affinity_node_t *an = get_affinity_info(env->co, n);
462 co_gs_foreach_neighb(an, neigh) {
463 const ir_node *m = neigh->irn;
464 const int m_idx = get_irn_idx(m);
466 /* skip ignore nodes */
467 if (arch_irn_is(env->aenv, m, ignore))
470 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
476 c->weight_consistent = 1;
481 * Count the number of interfering affinity neighbours
483 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
484 const neighb_t *neigh;
485 ir_node *irn = an->irn;
486 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
489 co_gs_foreach_neighb(an, neigh) {
490 const ir_node *n = neigh->irn;
493 /* skip ignore nodes */
494 if (arch_irn_is(env->aenv, n, ignore))
497 /* check if the affinity neighbour interfere */
498 for (i = 0; i < node->n_neighs; ++i) {
499 if (node->int_neighs[i] == n) {
510 * Build chunks of nodes connected by affinity edges.
511 * We start at the heaviest affinity edge.
512 * The chunks of the two edge-defining nodes will be
513 * merged if there are no interference edges from one
514 * chunk to the other.
516 static void build_affinity_chunks(co_mst_env_t *env) {
517 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
518 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
521 aff_chunk_t *curr_chunk;
523 /* at first we create the affinity edge objects */
524 be_ifg_foreach_node(env->ifg, nodes_it, n) {
525 int n_idx = get_irn_idx(n);
529 /* skip ignore nodes */
530 if (arch_irn_is(env->aenv, n, ignore))
533 n1 = get_co_mst_irn(env, n);
534 an = get_affinity_info(env->co, n);
539 if (n1->int_aff_neigh < 0)
540 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
542 /* build the affinity edges */
543 co_gs_foreach_neighb(an, neigh) {
544 ir_node *m = neigh->irn;
545 int m_idx = get_irn_idx(m);
547 /* record the edge in only one direction */
552 /* skip ignore nodes */
553 if (arch_irn_is(env->aenv, m, ignore))
559 n2 = get_co_mst_irn(env, m);
560 if (n2->int_aff_neigh < 0) {
561 affinity_node_t *am = get_affinity_info(env->co, m);
562 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
564 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
565 ARR_APP1(aff_edge_t, edges, edge);
571 /* now: sort edges and build the affinity chunks */
572 len = ARR_LEN(edges);
573 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
574 for (i = 0; i < len; ++i) {
575 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
577 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
580 /* now insert all chunks into a priority queue */
581 foreach_pset(env->chunkset, curr_chunk) {
582 aff_chunk_assure_weight(env, curr_chunk);
584 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
585 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
586 DBG((dbg, LEVEL_1, "\n"));
588 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
590 foreach_phase_irn(&env->ph, n) {
591 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
593 if (mirn->chunk == NULL) {
594 /* no chunk is allocated so far, do it now */
595 aff_chunk_t *curr_chunk = new_aff_chunk(env);
596 aff_chunk_add_node(curr_chunk, mirn);
598 aff_chunk_assure_weight(env, curr_chunk);
600 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
601 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
602 DBG((dbg, LEVEL_1, "\n"));
604 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
612 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
614 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
615 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
617 waitq *nodes = new_waitq();
619 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
621 /* init queue and chunk */
622 waitq_put(nodes, node);
623 bitset_set(visited, get_irn_idx(node->irn));
624 aff_chunk_add_node(chunk, node);
625 DB((dbg, LEVEL_1, " %+F", node->irn));
627 /* as long as there are nodes in the queue */
628 while (! waitq_empty(nodes)) {
629 co_mst_irn_t *n = waitq_get(nodes);
630 affinity_node_t *an = get_affinity_info(env->co, n->irn);
632 /* check all affinity neighbors */
635 co_gs_foreach_neighb(an, neigh) {
636 ir_node *m = neigh->irn;
637 int m_idx = get_irn_idx(m);
640 /* skip ignore nodes */
641 if (arch_irn_is(env->aenv, m, ignore))
644 n2 = get_co_mst_irn(env, m);
646 if (! bitset_is_set(visited, m_idx) &&
649 ! aff_chunk_interferes(env, chunk, m) &&
650 bitset_is_set(orig_chunk->nodes, m_idx))
653 following conditions are met:
654 - neighbour is not visited
655 - neighbour likes the color
656 - neighbour has not yet a fixed color
657 - the new chunk doesn't interfere with the neighbour
658 - neighbour belongs or belonged once to the original chunk
660 bitset_set(visited, m_idx);
661 aff_chunk_add_node(chunk, n2);
662 DB((dbg, LEVEL_1, " %+F", n2->irn));
663 /* enqueue for further search */
664 waitq_put(nodes, n2);
670 DB((dbg, LEVEL_1, "\n"));
676 * Fragment the given chunk into chunks having given color and not having given color.
678 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
679 bitset_t *visited = bitset_irg_malloc(env->co->irg);
681 aff_chunk_t *best = NULL;
683 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
686 aff_chunk_t *tmp_chunk;
687 decide_func_t *decider;
691 if (bitset_is_set(visited, get_irn_idx(irn)))
694 node = get_co_mst_irn(env, irn);
696 if (get_mst_irn_col(node) == col) {
697 decider = decider_has_color;
699 DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
702 decider = decider_hasnot_color;
704 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
707 /* create a new chunk starting at current node */
708 tmp_chunk = new_aff_chunk(env);
709 waitq_put(tmp, tmp_chunk);
710 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
711 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
713 /* remember the local best */
714 aff_chunk_assure_weight(env, tmp_chunk);
715 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
719 assert(best && "No chunk found?");
720 bitset_free(visited);
725 * Initializes an array of color-cost pairs.
726 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
728 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
731 for (i = 0; i < env->n_regs; ++i) {
733 if (bitset_is_set(env->ignore_regs, i))
734 cost[i].cost = COL_COST_INFEASIBLE;
741 * Initializes an array of color-cost pairs.
742 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
744 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
745 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
746 col_cost_init(env, cost, COL_COST_INFEASIBLE);
753 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
754 * ATTENTION: the queue is empty after calling this function!
756 static INLINE void reject_coloring(waitq *nodes) {
757 DB((dbg, LEVEL_4, "\treject coloring for"));
758 while (! waitq_empty(nodes)) {
759 co_mst_irn_t *n = waitq_get(nodes);
760 DB((dbg, LEVEL_4, " %+F", n->irn));
763 DB((dbg, LEVEL_4, "\n"));
767 * Determines the costs for each color if it would be assigned to node @p node.
769 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
770 affinity_node_t *an = get_affinity_info(env->co, node->irn);
774 col_cost_init(env, costs, 0.0);
776 /* calculate (negative) costs for affinity neighbours */
778 co_gs_foreach_neighb(an, aff_neigh) {
779 ir_node *m = aff_neigh->irn;
783 /* skip ignore nodes */
784 if (arch_irn_is(env->aenv, m, ignore))
787 neigh = get_co_mst_irn(env, m);
788 c = (double)aff_neigh->costs;
790 /* calculate costs for fixed affinity neighbours */
791 if (neigh->tmp_fixed || neigh->fixed) {
792 int col = get_mst_irn_col(neigh);
793 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
798 /* calculate (positive) costs for interfering neighbours */
799 for (i = 0; i < node->n_neighs; ++i) {
804 int_neigh = node->int_neighs[i];
806 /* skip ignore nodes */
807 if (arch_irn_is(env->aenv, int_neigh, ignore))
810 neigh = get_co_mst_irn(env, int_neigh);
811 col = get_mst_irn_col(neigh);
812 col_cnt = bitset_popcnt(neigh->adm_colors);
814 if (neigh->tmp_fixed || neigh->fixed) {
815 /* colors of fixed interfering neighbours are infeasible */
816 costs[col].cost = COL_COST_INFEASIBLE;
818 else if (col_cnt < env->k) {
819 /* calculate costs for constrained interfering neighbours */
820 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
822 bitset_foreach_clear(neigh->adm_colors, idx) {
823 /* check only explicitly forbidden colors (skip global forbidden ones) */
824 if (! bitset_is_set(env->ignore_regs, idx)) {
825 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
831 /* set all not admissible colors to COL_COST_INFEASIBLE */
832 bitset_foreach_clear(node->adm_colors, idx)
833 costs[idx].cost = COL_COST_INFEASIBLE;
836 /* need forward declaration due to recursive call */
837 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
840 * Tries to change node to a color but @p explude_col.
841 * @return 1 if succeeded, 0 otherwise.
843 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
844 int col = get_mst_irn_col(node);
847 /* neighbours has already a different color -> good, temporary fix it */
848 if (col != exclude_col) {
851 waitq_put(changed_ones, node);
855 /* The node has the color it should not have _and_ has not been visited yet. */
856 if (! (node->tmp_fixed || node->fixed)) {
857 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
859 /* Get the costs for giving the node a specific color. */
860 determine_color_costs(env, node, costs);
862 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
863 costs[exclude_col].cost = COL_COST_INFEASIBLE;
865 /* sort the colors according costs, cheapest first. */
866 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
868 /* Try recoloring the node using the color list. */
869 res = recolor_nodes(env, node, costs, changed_ones);
876 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
877 * ATTENTION: Expect @p costs already sorted by increasing costs.
878 * @return 1 if coloring could be applied, 0 otherwise.
880 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
882 waitq *local_changed = new_waitq();
883 waitq *tmp = new_waitq();
885 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
886 DBG_COL_COST(env, LEVEL_1, costs);
887 DB((dbg, LEVEL_1, "\n"));
889 for (i = 0; i < env->n_regs; ++i) {
890 int tgt_col = costs[i].col;
894 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
895 if (costs[i].cost == COL_COST_INFEASIBLE) {
897 del_waitq(local_changed);
902 /* Set the new color of the node and mark the node as temporarily fixed. */
903 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
905 node->tmp_col = tgt_col;
906 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
908 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
909 waitq_put(local_changed, node);
911 /* try to color all interfering neighbours with current color forbidden */
912 for (j = 0; j < node->n_neighs; ++j) {
916 neigh = node->int_neighs[j];
918 /* skip ignore nodes */
919 if (arch_irn_is(env->aenv, neigh, ignore))
922 nn = get_co_mst_irn(env, neigh);
923 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_fixed: %d, tmp_col: %d, col: %d)\n",
924 neigh, j, nn->fixed, nn->tmp_fixed, nn->tmp_col, nn->col));
927 Try to change the color of the neighbor and record all nodes which
928 get changed in the tmp list. Add this list to the "changed" list for
929 that color. If we did not succeed to change the color of the neighbor,
930 we bail out and try the next color.
932 if (get_mst_irn_col(nn) == tgt_col) {
933 /* try to color neighbour with tgt_col forbidden */
934 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
936 /* join lists of changed nodes */
937 while (! waitq_empty(tmp))
938 waitq_put(local_changed, waitq_get(tmp));
946 We managed to assign the target color to all neighbors, so from the perspective
947 of the current node, every thing was ok and we can return safely.
950 /* append the local_changed ones to global ones */
951 while (! waitq_empty(local_changed))
952 waitq_put(changed_ones, waitq_get(local_changed));
953 del_waitq(local_changed);
958 /* coloring of neighbours failed, so we try next color */
959 reject_coloring(local_changed);
963 del_waitq(local_changed);
969 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
970 * @return 1 if color @p col could be applied, 0 otherwise
972 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
973 int col = get_mst_irn_col(node);
975 /* if node already has the target color -> good, temporary fix it */
976 if (col == tgt_col) {
977 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
978 if (! node->tmp_fixed) {
980 node->tmp_col = tgt_col;
981 waitq_put(changed_ones, node);
987 Node has not yet a fixed color and target color is admissible
988 -> try to recolor node and it's affinity neighbours
990 if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
991 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
994 col_cost_init_single(env, costs, tgt_col);
996 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
997 res = recolor_nodes(env, node, costs, changed_ones);
998 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1004 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1005 if (node->fixed || node->tmp_fixed)
1006 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1008 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1009 dbg_admissible_colors(env, node);
1010 DB((dbg, LEVEL_4, ")\n"));
1019 * Tries to color an affinity chunk (or at least a part of it).
1020 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1022 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1023 aff_chunk_t *best_chunk = NULL;
1024 int best_color = -1;
1025 waitq *changed_ones = new_waitq();
1026 waitq *tmp_chunks = new_waitq();
1027 waitq *best_starts = NULL;
1031 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1032 DBG_AFF_CHUNK(env, LEVEL_2, c);
1033 DB((dbg, LEVEL_2, "\n"));
1036 /* check which color is the "best" for the given chunk */
1037 for (col = 0; col < env->n_regs; ++col) {
1039 waitq *good_starts = new_waitq();
1040 aff_chunk_t *local_best;
1042 /* skip ignore colors */
1043 if (bitset_is_set(env->ignore_regs, col))
1046 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1048 /* try to bring all nodes of given chunk to the current color. */
1049 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1050 ir_node *irn = c->n[idx];
1051 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1054 assert(! node->fixed && "Node must not have a fixed color.");
1055 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1058 The order of the colored nodes is important, so we record the successfully
1059 colored ones in the order they appeared.
1061 good = change_node_color(env, node, col, changed_ones);
1063 waitq_put(good_starts, node);
1066 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1069 /* try next color when failed */
1073 /* fragment the chunk according to the coloring */
1074 local_best = fragment_chunk(env, col, c, tmp_chunks);
1076 /* search the best of the good list
1077 and make it the new best if it is better than the current */
1079 aff_chunk_assure_weight(env, local_best);
1081 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1082 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1084 if (! best_chunk || best_chunk->weight < local_best->weight) {
1085 best_chunk = local_best;
1088 del_waitq(best_starts);
1089 best_starts = good_starts;
1090 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1092 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1093 del_waitq(good_starts);
1097 del_waitq(good_starts);
1100 /* reject the coloring and bring the coloring to the initial state */
1101 reject_coloring(changed_ones);
1104 /* free all intermediate created chunks except best one */
1105 while (! waitq_empty(tmp_chunks)) {
1106 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1107 if (tmp != best_chunk)
1108 delete_aff_chunk(env, tmp);
1110 del_waitq(tmp_chunks);
1112 /* return if coloring failed */
1114 del_waitq(changed_ones);
1116 del_waitq(best_starts);
1120 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1121 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1122 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1124 /* get the best fragment from the best list and color it */
1125 while (! waitq_empty(best_starts)) {
1126 co_mst_irn_t *node = waitq_get(best_starts);
1129 if (! bitset_is_set(best_chunk->nodes, get_irn_idx(node->irn)))
1132 res = change_node_color(env, node, best_color, changed_ones);
1134 panic("Color manifesting failed for %+F, color %d in chunk %d\n", node->irn, best_color, best_chunk->id);
1136 node->chunk = best_chunk;
1138 /* we colored the successful start nodes, now color the rest of the chunk */
1139 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1140 ir_node *irn = best_chunk->n[idx];
1141 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1144 res = change_node_color(env, node, best_color, changed_ones);
1146 panic("Color manifesting failed for %+F, color %d in chunk %d\n", irn, best_color, best_chunk->id);
1147 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, irn, best_chunk->id));
1149 node->chunk = best_chunk;
1152 /* materialize colors on changed nodes */
1153 while (! waitq_empty(changed_ones)) {
1154 co_mst_irn_t *n = waitq_get(changed_ones);
1156 n->col = n->tmp_col;
1159 /* remove the nodes in best chunk from original chunk */
1160 bitset_andnot(c->nodes, best_chunk->nodes);
1161 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1162 ir_node *irn = c->n[idx];
1164 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1165 int last = ARR_LEN(c->n) - 1;
1167 c->n[idx] = c->n[last];
1168 ARR_SHRINKLEN(c->n, last);
1173 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1174 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1175 ir_node *n = c->n[idx];
1176 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1180 /* fragment the remaining chunk */
1181 visited = bitset_irg_malloc(env->co->irg);
1182 bitset_or(visited, best_chunk->nodes);
1183 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1184 ir_node *irn = c->n[idx];
1185 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1186 aff_chunk_t *new_chunk = new_aff_chunk(env);
1187 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1189 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1190 aff_chunk_assure_weight(env, new_chunk);
1191 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1195 /* clear obsolete chunks and free some memory */
1196 delete_aff_chunk(env, best_chunk);
1197 bitset_free(visited);
1198 del_waitq(changed_ones);
1200 del_waitq(best_starts);
1204 * Main driver for mst safe coalescing algorithm.
1206 int co_solve_heuristic_mst(copy_opt_t *co) {
1207 unsigned n_regs = co->cls->n_regs;
1208 bitset_t *ignore_regs = bitset_alloca(n_regs);
1211 co_mst_env_t mst_env;
1214 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1216 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1219 mst_env.n_regs = n_regs;
1221 mst_env.chunks = new_pqueue();
1223 mst_env.ignore_regs = ignore_regs;
1224 mst_env.ifg = co->cenv->ifg;
1225 mst_env.aenv = co->aenv;
1226 mst_env.chunkset = pset_new_ptr(512);
1228 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1230 /* build affinity chunks */
1231 build_affinity_chunks(&mst_env);
1233 /* color chunks as long as there are some */
1234 while (! pqueue_empty(mst_env.chunks)) {
1235 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1237 color_aff_chunk(&mst_env, chunk);
1238 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1239 delete_aff_chunk(&mst_env, chunk);
1242 /* apply coloring */
1243 foreach_phase_irn(&mst_env.ph, irn) {
1244 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1245 const arch_register_t *reg;
1247 if (arch_irn_is(mst_env.aenv, irn, ignore))
1250 assert(mirn->fixed && "Node should have fixed color");
1252 /* skip nodes where color hasn't changed */
1253 if (mirn->init_col == mirn->col)
1256 reg = arch_register_for_index(co->cls, mirn->col);
1257 arch_set_irn_register(co->aenv, irn, reg);
1258 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1261 /* free allocated memory */
1262 del_pqueue(mst_env.chunks);
1263 phase_free(&mst_env.ph);
1264 del_pset(mst_env.chunkset);
1269 void be_init_copyheur4(void) {
1270 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1273 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);