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);
775 col_cost_init(env, costs, 0.0);
777 /* calculate (negative) costs for affinity neighbours */
779 co_gs_foreach_neighb(an, aff_neigh) {
780 ir_node *m = aff_neigh->irn;
784 /* skip ignore nodes */
785 if (arch_irn_is(env->aenv, m, ignore))
788 neigh = get_co_mst_irn(env, m);
789 c = (double)aff_neigh->costs;
791 /* calculate costs for fixed affinity neighbours */
792 if (neigh->tmp_fixed || neigh->fixed) {
793 int col = get_mst_irn_col(neigh);
794 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
799 /* calculate (positive) costs for interfering neighbours */
800 for (i = 0; i < node->n_neighs; ++i) {
805 int_neigh = node->int_neighs[i];
807 /* skip ignore nodes */
808 if (arch_irn_is(env->aenv, int_neigh, ignore))
811 neigh = get_co_mst_irn(env, int_neigh);
812 col = get_mst_irn_col(neigh);
813 col_cnt = bitset_popcnt(neigh->adm_colors);
815 if (neigh->tmp_fixed || neigh->fixed) {
816 /* colors of fixed interfering neighbours are infeasible */
817 costs[col].cost = COL_COST_INFEASIBLE;
819 else if (col_cnt < env->k) {
820 /* calculate costs for constrained interfering neighbours */
821 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
823 bitset_foreach_clear(neigh->adm_colors, idx) {
824 /* check only explicitly forbidden colors (skip global forbidden ones) */
825 if (! bitset_is_set(env->ignore_regs, idx)) {
826 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
832 /* set all not admissible colors to COL_COST_INFEASIBLE */
833 bitset_foreach_clear(node->adm_colors, idx)
834 costs[idx].cost = COL_COST_INFEASIBLE;
837 /* need forward declaration due to recursive call */
838 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones);
841 * Tries to change node to a color but @p explude_col.
842 * @return 1 if succeeded, 0 otherwise.
844 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, waitq *changed_ones) {
845 int col = get_mst_irn_col(node);
848 /* neighbours has already a different color -> good, temporary fix it */
849 if (col != exclude_col) {
852 waitq_put(changed_ones, node);
856 /* The node has the color it should not have _and_ has not been visited yet. */
857 if (! (node->tmp_fixed || node->fixed)) {
858 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
860 /* Get the costs for giving the node a specific color. */
861 determine_color_costs(env, node, costs);
863 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
864 costs[exclude_col].cost = COL_COST_INFEASIBLE;
866 /* sort the colors according costs, cheapest first. */
867 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
869 /* Try recoloring the node using the color list. */
870 res = recolor_nodes(env, node, costs, changed_ones);
877 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
878 * ATTENTION: Expect @p costs already sorted by increasing costs.
879 * @return 1 if coloring could be applied, 0 otherwise.
881 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
883 waitq *local_changed = new_waitq();
884 waitq *tmp = new_waitq();
886 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
887 DBG_COL_COST(env, LEVEL_1, costs);
888 DB((dbg, LEVEL_1, "\n"));
890 for (i = 0; i < env->n_regs; ++i) {
891 int tgt_col = costs[i].col;
895 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
896 if (costs[i].cost == COL_COST_INFEASIBLE) {
898 del_waitq(local_changed);
903 /* Set the new color of the node and mark the node as temporarily fixed. */
904 assert(! node->tmp_fixed && "Node must not have been temporary fixed.");
906 node->tmp_col = tgt_col;
907 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
909 assert(waitq_empty(local_changed) && "Node queue should be empty here.");
910 waitq_put(local_changed, node);
912 /* try to color all interfering neighbours with current color forbidden */
913 for (j = 0; j < node->n_neighs; ++j) {
917 neigh = node->int_neighs[j];
919 /* skip ignore nodes */
920 if (arch_irn_is(env->aenv, neigh, ignore))
923 nn = get_co_mst_irn(env, neigh);
924 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_fixed: %d, tmp_col: %d, col: %d)\n",
925 neigh, j, nn->fixed, nn->tmp_fixed, nn->tmp_col, nn->col));
928 Try to change the color of the neighbor and record all nodes which
929 get changed in the tmp list. Add this list to the "changed" list for
930 that color. If we did not succeed to change the color of the neighbor,
931 we bail out and try the next color.
933 if (get_mst_irn_col(nn) == tgt_col) {
934 /* try to color neighbour with tgt_col forbidden */
935 neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
937 /* join lists of changed nodes */
938 while (! waitq_empty(tmp))
939 waitq_put(local_changed, waitq_get(tmp));
947 We managed to assign the target color to all neighbors, so from the perspective
948 of the current node, every thing was ok and we can return safely.
951 /* append the local_changed ones to global ones */
952 while (! waitq_empty(local_changed))
953 waitq_put(changed_ones, waitq_get(local_changed));
954 del_waitq(local_changed);
959 /* coloring of neighbours failed, so we try next color */
960 reject_coloring(local_changed);
964 del_waitq(local_changed);
970 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
971 * @return 1 if color @p col could be applied, 0 otherwise
973 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, waitq *changed_ones) {
974 int col = get_mst_irn_col(node);
976 /* if node already has the target color -> good, temporary fix it */
977 if (col == tgt_col) {
978 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
979 if (! node->tmp_fixed) {
981 node->tmp_col = tgt_col;
982 waitq_put(changed_ones, node);
988 Node has not yet a fixed color and target color is admissible
989 -> try to recolor node and it's affinity neighbours
991 if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
992 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
995 col_cost_init_single(env, costs, tgt_col);
997 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
998 res = recolor_nodes(env, node, costs, changed_ones);
999 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1005 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1006 if (node->fixed || node->tmp_fixed)
1007 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1009 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1010 dbg_admissible_colors(env, node);
1011 DB((dbg, LEVEL_4, ")\n"));
1020 * Tries to color an affinity chunk (or at least a part of it).
1021 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1023 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1024 aff_chunk_t *best_chunk = NULL;
1025 int best_color = -1;
1027 waitq *changed_ones = new_waitq();
1028 waitq *tmp_chunks = new_waitq();
1029 waitq *best_starts = NULL;
1033 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1034 DBG_AFF_CHUNK(env, LEVEL_2, c);
1035 DB((dbg, LEVEL_2, "\n"));
1038 /* check which color is the "best" for the given chunk.
1039 * if we found a color which was ok for all nodes, we take it
1040 * and do not look further. (see did_all flag usage below.)
1041 * If we have many colors which fit all nodes it is hard to decide
1042 * which one to take anyway.
1043 * TODO Sebastian: Perhaps we should at all nodes and figure out
1044 * a suitable color using costs as done above (determine_color_costs).
1046 for (col = 0; col < env->n_regs && !did_all; ++col) {
1048 waitq *good_starts = new_waitq();
1049 aff_chunk_t *local_best;
1051 /* skip ignore colors */
1052 if (bitset_is_set(env->ignore_regs, col))
1055 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1057 /* suppose we can color all nodes to the same color */
1060 /* try to bring all nodes of given chunk to the current color. */
1061 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1062 ir_node *irn = c->n[idx];
1063 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1066 assert(! node->fixed && "Node must not have a fixed color.");
1067 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1070 The order of the colored nodes is important, so we record the successfully
1071 colored ones in the order they appeared.
1073 good = change_node_color(env, node, col, changed_ones);
1075 waitq_put(good_starts, node);
1079 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1082 /* try next color when failed */
1086 /* fragment the chunk according to the coloring */
1087 local_best = fragment_chunk(env, col, c, tmp_chunks);
1089 /* search the best of the good list
1090 and make it the new best if it is better than the current */
1092 aff_chunk_assure_weight(env, local_best);
1094 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1095 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1097 if (! best_chunk || best_chunk->weight < local_best->weight) {
1098 best_chunk = local_best;
1101 del_waitq(best_starts);
1102 best_starts = good_starts;
1103 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1105 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1106 del_waitq(good_starts);
1110 del_waitq(good_starts);
1113 /* reject the coloring and bring the coloring to the initial state */
1114 reject_coloring(changed_ones);
1117 /* free all intermediate created chunks except best one */
1118 while (! waitq_empty(tmp_chunks)) {
1119 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1120 if (tmp != best_chunk)
1121 delete_aff_chunk(env, tmp);
1123 del_waitq(tmp_chunks);
1125 /* return if coloring failed */
1127 del_waitq(changed_ones);
1129 del_waitq(best_starts);
1133 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1134 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1135 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1137 /* get the best fragment from the best list and color it */
1138 while (! waitq_empty(best_starts)) {
1139 co_mst_irn_t *node = waitq_get(best_starts);
1142 if (! bitset_is_set(best_chunk->nodes, get_irn_idx(node->irn)))
1145 res = change_node_color(env, node, best_color, changed_ones);
1147 panic("Color manifesting failed for %+F, color %d in chunk %d\n", node->irn, best_color, best_chunk->id);
1149 node->chunk = best_chunk;
1151 /* we colored the successful start nodes, now color the rest of the chunk */
1152 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1153 ir_node *irn = best_chunk->n[idx];
1154 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1157 res = change_node_color(env, node, best_color, changed_ones);
1159 panic("Color manifesting failed for %+F, color %d in chunk %d\n", irn, best_color, best_chunk->id);
1160 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, irn, best_chunk->id));
1162 node->chunk = best_chunk;
1165 /* materialize colors on changed nodes */
1166 while (! waitq_empty(changed_ones)) {
1167 co_mst_irn_t *n = waitq_get(changed_ones);
1169 n->col = n->tmp_col;
1172 /* remove the nodes in best chunk from original chunk */
1173 bitset_andnot(c->nodes, best_chunk->nodes);
1174 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1175 ir_node *irn = c->n[idx];
1177 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1178 int last = ARR_LEN(c->n) - 1;
1180 c->n[idx] = c->n[last];
1181 ARR_SHRINKLEN(c->n, last);
1186 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1187 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1188 ir_node *n = c->n[idx];
1189 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1193 /* fragment the remaining chunk */
1194 visited = bitset_irg_malloc(env->co->irg);
1195 bitset_or(visited, best_chunk->nodes);
1196 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1197 ir_node *irn = c->n[idx];
1198 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1199 aff_chunk_t *new_chunk = new_aff_chunk(env);
1200 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1202 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1203 aff_chunk_assure_weight(env, new_chunk);
1204 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1208 /* clear obsolete chunks and free some memory */
1209 delete_aff_chunk(env, best_chunk);
1210 bitset_free(visited);
1211 del_waitq(changed_ones);
1213 del_waitq(best_starts);
1217 * Main driver for mst safe coalescing algorithm.
1219 int co_solve_heuristic_mst(copy_opt_t *co) {
1220 unsigned n_regs = co->cls->n_regs;
1221 bitset_t *ignore_regs = bitset_alloca(n_regs);
1224 co_mst_env_t mst_env;
1227 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1229 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1232 mst_env.n_regs = n_regs;
1234 mst_env.chunks = new_pqueue();
1236 mst_env.ignore_regs = ignore_regs;
1237 mst_env.ifg = co->cenv->ifg;
1238 mst_env.aenv = co->aenv;
1239 mst_env.chunkset = pset_new_ptr(512);
1241 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1243 /* build affinity chunks */
1244 build_affinity_chunks(&mst_env);
1246 /* color chunks as long as there are some */
1247 while (! pqueue_empty(mst_env.chunks)) {
1248 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1250 color_aff_chunk(&mst_env, chunk);
1251 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1252 delete_aff_chunk(&mst_env, chunk);
1255 /* apply coloring */
1256 foreach_phase_irn(&mst_env.ph, irn) {
1257 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1258 const arch_register_t *reg;
1260 if (arch_irn_is(mst_env.aenv, irn, ignore))
1263 assert(mirn->fixed && "Node should have fixed color");
1265 /* skip nodes where color hasn't changed */
1266 if (mirn->init_col == mirn->col)
1269 reg = arch_register_for_index(co->cls, mirn->col);
1270 arch_set_irn_register(co->aenv, irn, reg);
1271 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1274 /* free allocated memory */
1275 del_pqueue(mst_env.chunks);
1276 phase_free(&mst_env.ph);
1277 del_pset(mst_env.chunkset);
1282 void be_init_copyheur4(void) {
1283 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1286 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);