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"
57 #include "becopyopt_t.h"
61 #define COL_COST_INFEASIBLE DBL_MAX
62 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
63 #define NEIGHBOUR_CONSTR_COSTS 64.0
68 #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0)
69 #define DBG_COL_COST(env, level, cost) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0)
71 static firm_dbg_module_t *dbg = NULL;
75 #define DBG_AFF_CHUNK(env, level, chunk)
76 #define DBG_COL_COST(env, level, cost)
80 static int last_chunk_id = 0;
82 typedef struct _col_cost_t {
90 typedef struct _aff_chunk_t {
91 ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
92 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
93 bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
94 int weight; /**< Weight of this chunk */
95 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
96 unsigned deleted : 1; /**< Set if the was deleted. */
97 int id; /**< For debugging: An id of this chunk. */
103 typedef struct _aff_edge_t {
104 ir_node *src; /**< Source node. */
105 ir_node *tgt; /**< Target node. */
106 double weight; /**< The weight of this edge. */
109 /* main coalescing environment */
110 typedef struct _co_mst_env_t {
111 int n_regs; /**< number of regs in class */
112 int k; /**< number of non-ignore registers in class */
113 bitset_t *ignore_regs; /**< set containing all global ignore registers */
114 ir_phase ph; /**< phase object holding data for nodes */
115 pqueue *chunks; /**< priority queue for chunks */
116 pset *chunkset; /**< set holding all chunks */
117 be_ifg_t *ifg; /**< the interference graph */
118 const arch_env_t *aenv; /**< the arch environment */
119 copy_opt_t *co; /**< the copy opt object */
122 /* stores coalescing related information for a node */
123 typedef struct _co_mst_irn_t {
124 ir_node *irn; /**< the irn this information belongs to */
125 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
126 bitset_t *adm_colors; /**< set of admissible colors for this irn */
127 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
128 int n_neighs; /**< length of the interfering neighbours array. */
129 int int_aff_neigh; /**< number of interfering affinity neighbours */
130 int col; /**< color currently assigned */
131 int init_col; /**< the initial color */
132 int tmp_col; /**< a temporary assigned color */
133 unsigned fixed : 1; /**< the color is fixed */
134 struct list_head list; /**< Queue for coloring undo. */
137 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
139 typedef int decide_func_t(const co_mst_irn_t *node, int col);
144 * Write a chunk to stderr for debugging.
146 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
148 if (c->weight_consistent)
149 ir_fprintf(stderr, " $%d ", c->weight);
150 ir_fprintf(stderr, "{");
151 bitset_foreach(c->nodes, idx) {
152 ir_node *n = get_idx_irn(env->co->irg, idx);
153 ir_fprintf(stderr, " %+F,", n);
155 ir_fprintf(stderr, "}");
159 * Dump all admissible colors to stderr.
161 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
165 if (bitset_popcnt(node->adm_colors) < 1)
166 fprintf(stderr, "no admissible colors?!?");
168 bitset_foreach(node->adm_colors, idx)
169 fprintf(stderr, " %d", idx);
174 * Dump color-cost pairs to stderr.
176 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
178 for (i = 0; i < env->n_regs; ++i) {
179 if (cost[i].cost == COL_COST_INFEASIBLE)
180 fprintf(stderr, " (%d, INF)", cost[i].col);
182 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
186 #endif /* DEBUG_libfirm */
188 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
189 return node->tmp_col >= 0 ? node->tmp_col : node->col;
193 * @return 1 if node @p node has color @p col, 0 otherwise.
195 static int decider_has_color(const co_mst_irn_t *node, int col) {
196 return get_mst_irn_col(node) == col;
200 * @return 1 if node @p node has not color @p col, 0 otherwise.
202 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
203 return get_mst_irn_col(node) != col;
207 * Always returns true.
209 static int decider_always_yes(const co_mst_irn_t *node, int col) {
215 /** compares two affinity edges by its weight */
216 static int cmp_aff_edge(const void *a, const void *b) {
217 const aff_edge_t *e1 = a;
218 const aff_edge_t *e2 = b;
220 if (e2->weight == e1->weight) {
221 if (e2->src->node_idx == e1->src->node_idx)
222 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
224 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
226 /* sort in descending order */
227 return QSORT_CMP(e2->weight, e1->weight);
230 /** compares to color-cost pairs */
231 static int cmp_col_cost(const void *a, const void *b) {
232 const col_cost_t *c1 = a;
233 const col_cost_t *c2 = b;
235 return c1->cost < c2->cost ? -1 : 1;
239 * Creates a new affinity chunk
241 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
242 aff_chunk_t *c = xmalloc(sizeof(*c));
244 c->weight_consistent = 0;
245 c->n = NEW_ARR_F(ir_node *, 0);
246 c->nodes = bitset_irg_malloc(env->co->irg);
247 c->interfere = bitset_irg_malloc(env->co->irg);
248 c->id = last_chunk_id++;
249 pset_insert(env->chunkset, c, c->id);
254 * Frees all memory allocated by an affinity chunk.
256 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
257 pset_remove(env->chunkset, c, c->id);
258 bitset_free(c->nodes);
259 bitset_free(c->interfere);
266 * Adds a node to an affinity chunk
268 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
271 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
274 c->weight_consistent = 0;
276 bitset_set(c->nodes, get_irn_idx(node->irn));
278 ARR_APP1(ir_node *, c->n, node->irn);
280 for (i = node->n_neighs - 1; i >= 0; --i) {
281 ir_node *neigh = node->int_neighs[i];
282 bitset_set(c->interfere, get_irn_idx(neigh));
287 * In case there is no phase information for irn, initialize it.
289 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
290 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
291 co_mst_env_t *env = ph->priv;
294 const arch_register_req_t *req;
295 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
303 res->int_neighs = NULL;
304 res->int_aff_neigh = 0;
305 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
306 res->init_col = res->col;
307 INIT_LIST_HEAD(&res->list);
309 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
311 /* set admissible registers */
312 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
314 /* Exclude colors not assignable to the irn */
315 req = arch_get_register_req(env->aenv, irn, -1);
316 if (arch_register_req_is(req, limited))
317 rbitset_copy_to_bitset(req->limited, res->adm_colors);
319 bitset_set_all(res->adm_colors);
321 /* exclude global ignore registers as well */
322 bitset_andnot(res->adm_colors, env->ignore_regs);
324 /* set the number of interfering affinity neighbours to -1, they are calculated later */
325 res->int_aff_neigh = -1;
327 /* build list of interfering neighbours */
329 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
330 if (! arch_irn_is(env->aenv, neigh, ignore)) {
331 obstack_ptr_grow(phase_obst(ph), neigh);
335 res->int_neighs = obstack_finish(phase_obst(ph));
342 * Check if affinity chunk @p chunk interferes with node @p irn.
344 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
346 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
350 * Check if there are interference edges from c1 to c2.
351 * @param env The global co_mst environment
353 * @param c2 Another chunk
354 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
356 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
362 /* check if there is a node in c2 having an interfering neighbor in c1 */
363 tmp = bitset_alloca(get_irg_last_idx(env->co->irg));
364 tmp = bitset_copy(tmp, c1->interfere);
365 tmp = bitset_and(tmp, c2->nodes);
367 return bitset_popcnt(tmp) > 0;
371 * Returns the affinity chunk of @p irn or creates a new
372 * one with @p irn as element if there is none assigned.
374 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
375 co_mst_irn_t *node = get_co_mst_irn(env, irn);
380 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
381 * are no interference edges from chunk(src) to chunk(tgt)).
382 * @return 1 if successful, 0 if not possible
384 static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
385 aff_chunk_t *c1 = get_aff_chunk(env, src);
386 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
389 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
391 DBG_AFF_CHUNK(env, LEVEL_4, c1);
393 DB((dbg, LEVEL_4, "{%+F}", src));
395 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
397 DBG_AFF_CHUNK(env, LEVEL_4, c2);
399 DB((dbg, LEVEL_4, "{%+F}", tgt));
401 DB((dbg, LEVEL_4, "\n"));
406 /* no chunk exists */
407 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
410 for (i = mirn->n_neighs - 1; i >= 0; --i) {
411 if (mirn->int_neighs[i] == tgt)
415 /* create one containing both nodes */
416 c1 = new_aff_chunk(env);
417 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
418 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
422 /* c2 already exists */
423 if (! aff_chunk_interferes(env, c2, src)) {
424 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
428 } else if (c2 == NULL) {
429 /* c1 already exists */
430 if (! aff_chunk_interferes(env, c1, tgt)) {
431 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
434 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
437 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) {
438 ir_node *n = c2->n[idx];
439 co_mst_irn_t *mn = get_co_mst_irn(env, n);
443 if (! bitset_is_set(c1->nodes, get_irn_idx(n)))
444 ARR_APP1(ir_node *, c1->n, n);
447 bitset_or(c1->nodes, c2->nodes);
448 bitset_or(c1->interfere, c2->interfere);
449 c1->weight_consistent = 0;
451 delete_aff_chunk(env, c2);
454 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
458 DB((dbg, LEVEL_4, " ... absorbed\n"));
463 * Assures that the weight of the given chunk is consistent.
465 static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) {
466 if (! c->weight_consistent) {
470 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
471 ir_node *n = c->n[idx];
472 const affinity_node_t *an = get_affinity_info(env->co, n);
476 co_gs_foreach_neighb(an, neigh) {
477 const ir_node *m = neigh->irn;
478 const int m_idx = get_irn_idx(m);
480 /* skip ignore nodes */
481 if (arch_irn_is(env->aenv, m, ignore))
484 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
490 c->weight_consistent = 1;
495 * Count the number of interfering affinity neighbours
497 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
498 const neighb_t *neigh;
499 ir_node *irn = an->irn;
500 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
503 co_gs_foreach_neighb(an, neigh) {
504 const ir_node *n = neigh->irn;
507 /* skip ignore nodes */
508 if (arch_irn_is(env->aenv, n, ignore))
511 /* check if the affinity neighbour interfere */
512 for (i = 0; i < node->n_neighs; ++i) {
513 if (node->int_neighs[i] == n) {
524 * Build chunks of nodes connected by affinity edges.
525 * We start at the heaviest affinity edge.
526 * The chunks of the two edge-defining nodes will be
527 * merged if there are no interference edges from one
528 * chunk to the other.
530 static void build_affinity_chunks(co_mst_env_t *env) {
531 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
532 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
535 aff_chunk_t *curr_chunk;
537 /* at first we create the affinity edge objects */
538 be_ifg_foreach_node(env->ifg, nodes_it, n) {
539 int n_idx = get_irn_idx(n);
543 /* skip ignore nodes */
544 if (arch_irn_is(env->aenv, n, ignore))
547 n1 = get_co_mst_irn(env, n);
548 an = get_affinity_info(env->co, n);
553 if (n1->int_aff_neigh < 0)
554 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
556 /* build the affinity edges */
557 co_gs_foreach_neighb(an, neigh) {
558 ir_node *m = neigh->irn;
559 int m_idx = get_irn_idx(m);
561 /* record the edge in only one direction */
566 /* skip ignore nodes */
567 if (arch_irn_is(env->aenv, m, ignore))
573 n2 = get_co_mst_irn(env, m);
574 if (n2->int_aff_neigh < 0) {
575 affinity_node_t *am = get_affinity_info(env->co, m);
576 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
579 * these weights are pure hackery ;-).
580 * It's not chriswue's fault but mine.
582 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
583 ARR_APP1(aff_edge_t, edges, edge);
589 /* now: sort edges and build the affinity chunks */
590 len = ARR_LEN(edges);
591 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
592 for (i = 0; i < len; ++i) {
593 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
595 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
598 /* now insert all chunks into a priority queue */
599 foreach_pset(env->chunkset, curr_chunk) {
600 aff_chunk_assure_weight(env, curr_chunk);
602 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
603 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
604 DBG((dbg, LEVEL_1, "\n"));
606 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
608 foreach_phase_irn(&env->ph, n) {
609 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
611 if (mirn->chunk == NULL) {
612 /* no chunk is allocated so far, do it now */
613 aff_chunk_t *curr_chunk = new_aff_chunk(env);
614 aff_chunk_add_node(curr_chunk, mirn);
616 aff_chunk_assure_weight(env, curr_chunk);
618 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
619 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
620 DBG((dbg, LEVEL_1, "\n"));
622 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
629 static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
631 pqueue *grow = new_pqueue();
634 ir_node *max_node = NULL;
636 for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
637 ir_node *irn = chunk->n[i];
638 affinity_node_t *an = get_affinity_info(env->co, irn);
642 if (arch_irn_is(env->aenv, irn, ignore))
646 co_gs_foreach_neighb(an, neigh)
649 if (w > max_weight) {
657 bitset_t *visited = bitset_irg_malloc(env->co->irg);
659 for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
660 bitset_add_irn(visited, chunk->n[i]);
662 pqueue_put(grow, max_node, max_weight);
663 bitset_remv_irn(visited, max_node);
665 while (!pqueue_empty(grow)) {
666 ir_node *irn = pqueue_get(grow);
667 affinity_node_t *an = get_affinity_info(env->co, irn);
670 if (arch_irn_is(env->aenv, irn, ignore))
673 assert(i <= ARR_LEN(chunk->n));
678 /* build the affinity edges */
679 co_gs_foreach_neighb(an, neigh) {
680 co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
682 if (bitset_contains_irn(visited, node->irn)) {
683 pqueue_put(grow, neigh->irn, neigh->costs);
684 bitset_remv_irn(visited, node->irn);
690 bitset_free(visited);
695 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
697 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
698 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
700 waitq *nodes = new_waitq();
702 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
704 /* init queue and chunk */
705 waitq_put(nodes, node);
706 bitset_set(visited, get_irn_idx(node->irn));
707 aff_chunk_add_node(chunk, node);
708 DB((dbg, LEVEL_1, " %+F", node->irn));
710 /* as long as there are nodes in the queue */
711 while (! waitq_empty(nodes)) {
712 co_mst_irn_t *n = waitq_get(nodes);
713 affinity_node_t *an = get_affinity_info(env->co, n->irn);
715 /* check all affinity neighbors */
718 co_gs_foreach_neighb(an, neigh) {
719 ir_node *m = neigh->irn;
720 int m_idx = get_irn_idx(m);
723 /* skip ignore nodes */
724 if (arch_irn_is(env->aenv, m, ignore))
727 n2 = get_co_mst_irn(env, m);
729 if (! bitset_is_set(visited, m_idx) &&
732 ! aff_chunk_interferes(env, chunk, m) &&
733 bitset_is_set(orig_chunk->nodes, m_idx))
736 following conditions are met:
737 - neighbour is not visited
738 - neighbour likes the color
739 - neighbour has not yet a fixed color
740 - the new chunk doesn't interfere with the neighbour
741 - neighbour belongs or belonged once to the original chunk
743 bitset_set(visited, m_idx);
744 aff_chunk_add_node(chunk, n2);
745 DB((dbg, LEVEL_1, " %+F", n2->irn));
746 /* enqueue for further search */
747 waitq_put(nodes, n2);
753 DB((dbg, LEVEL_1, "\n"));
759 * Fragment the given chunk into chunks having given color and not having given color.
761 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
762 bitset_t *visited = bitset_irg_malloc(env->co->irg);
764 aff_chunk_t *best = NULL;
766 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
769 aff_chunk_t *tmp_chunk;
770 decide_func_t *decider;
774 if (bitset_is_set(visited, get_irn_idx(irn)))
777 node = get_co_mst_irn(env, irn);
779 if (get_mst_irn_col(node) == col) {
780 decider = decider_has_color;
782 DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
785 decider = decider_hasnot_color;
787 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
790 /* create a new chunk starting at current node */
791 tmp_chunk = new_aff_chunk(env);
792 waitq_put(tmp, tmp_chunk);
793 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
794 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
796 /* remember the local best */
797 aff_chunk_assure_weight(env, tmp_chunk);
798 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
802 assert(best && "No chunk found?");
803 bitset_free(visited);
808 * Initializes an array of color-cost pairs.
809 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
811 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
814 for (i = 0; i < env->n_regs; ++i) {
816 if (bitset_is_set(env->ignore_regs, i))
817 cost[i].cost = COL_COST_INFEASIBLE;
824 * Initializes an array of color-cost pairs.
825 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
827 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
828 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
829 col_cost_init(env, cost, COL_COST_INFEASIBLE);
836 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
837 * ATTENTION: the queue is empty after calling this function!
839 static INLINE void reject_coloring(struct list_head *nodes) {
840 co_mst_irn_t *n, *temp;
841 DB((dbg, LEVEL_4, "\treject coloring for"));
842 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
843 DB((dbg, LEVEL_4, " %+F", n->irn));
844 assert(n->tmp_col >= 0);
846 list_del_init(&n->list);
848 DB((dbg, LEVEL_4, "\n"));
851 static INLINE void materialize_coloring(struct list_head *nodes) {
852 co_mst_irn_t *n, *temp;
853 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
854 assert(n->tmp_col >= 0);
857 list_del_init(&n->list);
861 static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
864 assert(!node->fixed);
865 assert(node->tmp_col < 0);
866 assert(node->list.next == &node->list && node->list.prev == &node->list);
868 list_add_tail(&node->list, changed);
872 static INLINE int is_loose(co_mst_irn_t *node)
874 return !node->fixed && node->tmp_col < 0;
878 * Determines the costs for each color if it would be assigned to node @p node.
880 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
881 affinity_node_t *an = get_affinity_info(env->co, node->irn);
886 col_cost_init(env, costs, 0.0);
888 /* calculate (negative) costs for affinity neighbours */
890 co_gs_foreach_neighb(an, aff_neigh) {
891 ir_node *m = aff_neigh->irn;
895 /* skip ignore nodes */
896 if (arch_irn_is(env->aenv, m, ignore))
899 neigh = get_co_mst_irn(env, m);
900 c = (double)aff_neigh->costs;
902 /* calculate costs for fixed affinity neighbours */
903 if (!is_loose(neigh)) {
904 int col = get_mst_irn_col(neigh);
905 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
910 /* calculate (positive) costs for interfering neighbours */
911 for (i = 0; i < node->n_neighs; ++i) {
916 int_neigh = node->int_neighs[i];
918 assert(!arch_irn_is(env->aenv, int_neigh, ignore));
920 neigh = get_co_mst_irn(env, int_neigh);
921 col = get_mst_irn_col(neigh);
922 col_cnt = bitset_popcnt(neigh->adm_colors);
924 if (!is_loose(neigh)) {
925 /* colors of fixed interfering neighbours are infeasible */
926 costs[col].cost = COL_COST_INFEASIBLE;
928 else if (col_cnt < env->k) {
929 /* calculate costs for constrained interfering neighbours */
930 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
932 bitset_foreach_clear(neigh->adm_colors, idx) {
933 /* check only explicitly forbidden colors (skip global forbidden ones) */
934 if (! bitset_is_set(env->ignore_regs, idx)) {
935 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
940 DB((dbg, LEVEL_4, "\tneigh %+F, loose: %d, color: %d\n", int_neigh, is_loose(neigh), col));
943 /* set all not admissible colors to COL_COST_INFEASIBLE */
944 bitset_foreach_clear(node->adm_colors, idx)
945 costs[idx].cost = COL_COST_INFEASIBLE;
948 static col_cost_t *add_constr_costs(co_mst_env_t *env, col_cost_t *costs, double factor, const co_mst_irn_t *node)
950 int col = get_mst_irn_col(node);
951 int col_cnt = bitset_popcnt(node->adm_colors);
954 if (col_cnt < env->k) {
955 /* calculate costs for constrained interfering nodebours */
956 double ratio = 1.0 - (double) col_cnt / env->k;
958 bitset_foreach_clear(node->adm_colors, idx) {
959 /* check only explicitly forbidden colors (skip global forbidden ones) */
960 if (! bitset_is_set(env->ignore_regs, idx)) {
961 costs[col].cost += ratio * factor;
969 /* need forward declaration due to recursive call */
970 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones);
973 * Tries to change node to a color but @p explude_col.
974 * @return 1 if succeeded, 0 otherwise.
976 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed_ones) {
977 int col = get_mst_irn_col(node);
980 /* neighbours has already a different color -> good, temporary fix it */
981 if (col != exclude_col) {
983 set_temp_color(node, col, changed_ones);
987 /* The node has the color it should not have _and_ has not been visited yet. */
988 if (is_loose(node)) {
989 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
991 /* Get the costs for giving the node a specific color. */
992 determine_color_costs(env, node, costs);
994 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
995 costs[exclude_col].cost = COL_COST_INFEASIBLE;
997 /* sort the colors according costs, cheapest first. */
998 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
1000 /* Try recoloring the node using the color list. */
1001 res = recolor_nodes(env, node, costs, changed_ones);
1008 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
1009 * ATTENTION: Expect @p costs already sorted by increasing costs.
1010 * @return 1 if coloring could be applied, 0 otherwise.
1012 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones) {
1014 struct list_head local_changed;
1016 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
1017 DBG_COL_COST(env, LEVEL_1, costs);
1018 DB((dbg, LEVEL_1, "\n"));
1020 for (i = 0; i < env->n_regs; ++i) {
1021 int tgt_col = costs[i].col;
1025 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
1026 if (costs[i].cost == COL_COST_INFEASIBLE) {
1030 /* Set the new color of the node and mark the node as temporarily fixed. */
1031 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
1032 INIT_LIST_HEAD(&local_changed);
1033 set_temp_color(node, tgt_col, &local_changed);
1034 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
1036 /* try to color all interfering neighbours with current color forbidden */
1037 for (j = 0; j < node->n_neighs; ++j) {
1041 neigh = node->int_neighs[j];
1043 /* skip ignore nodes */
1044 if (arch_irn_is(env->aenv, neigh, ignore))
1047 nn = get_co_mst_irn(env, neigh);
1048 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
1049 neigh, j, nn->fixed, nn->tmp_col, nn->col));
1052 Try to change the color of the neighbor and record all nodes which
1053 get changed in the tmp list. Add this list to the "changed" list for
1054 that color. If we did not succeed to change the color of the neighbor,
1055 we bail out and try the next color.
1057 if (get_mst_irn_col(nn) == tgt_col) {
1058 /* try to color neighbour with tgt_col forbidden */
1059 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed);
1067 We managed to assign the target color to all neighbors, so from the perspective
1068 of the current node, every thing was ok and we can return safely.
1071 /* append the local_changed ones to global ones */
1072 list_splice(&local_changed, changed_ones);
1076 /* coloring of neighbours failed, so we try next color */
1077 reject_coloring(&local_changed);
1085 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1086 * @return 1 if color @p col could be applied, 0 otherwise
1088 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed_ones) {
1089 int col = get_mst_irn_col(node);
1091 /* if node already has the target color -> good, temporary fix it */
1092 if (col == tgt_col) {
1093 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1095 set_temp_color(node, tgt_col, changed_ones);
1100 Node has not yet a fixed color and target color is admissible
1101 -> try to recolor node and it's affinity neighbours
1103 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1104 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
1107 col_cost_init_single(env, costs, tgt_col);
1109 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1110 res = recolor_nodes(env, node, costs, changed_ones);
1111 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1116 #ifdef DEBUG_libfirm
1117 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1118 if (!is_loose(node))
1119 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1121 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1122 dbg_admissible_colors(env, node);
1123 DB((dbg, LEVEL_4, ")\n"));
1132 * Tries to color an affinity chunk (or at least a part of it).
1133 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1135 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1136 aff_chunk_t *best_chunk = NULL;
1137 int best_color = -1;
1139 waitq *tmp_chunks = new_waitq();
1140 waitq *best_starts = NULL;
1141 col_cost_t *order = alloca(env->n_regs * sizeof(*order));
1144 struct list_head changed_ones;
1146 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1147 DBG_AFF_CHUNK(env, LEVEL_2, c);
1148 DB((dbg, LEVEL_2, "\n"));
1150 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1151 ir_node *irn = c->n[idx];
1152 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1155 add_constr_costs(env, order, -1.0, node);
1156 for (i = node->n_neighs - 1; i >= 0; --i) {
1157 co_mst_irn_t *neigh = get_co_mst_irn(env, node->int_neighs[i]);
1158 add_constr_costs(env, order, 1.0, neigh);
1162 for (col = 0; col < env->n_regs; ++col) {
1163 order[col].col = col;
1164 if (bitset_is_set(env->ignore_regs, col))
1165 order[col].cost = COL_COST_INFEASIBLE;
1168 qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost);
1169 chunk_order_nodes(env, c);
1171 /* check which color is the "best" for the given chunk.
1172 * if we found a color which was ok for all nodes, we take it
1173 * and do not look further. (see did_all flag usage below.)
1174 * If we have many colors which fit all nodes it is hard to decide
1175 * which one to take anyway.
1176 * TODO Sebastian: Perhaps we should at all nodes and figure out
1177 * a suitable color using costs as done above (determine_color_costs).
1179 for (col = 0; col < env->n_regs && !did_all; ++col) {
1181 waitq *good_starts = new_waitq();
1182 aff_chunk_t *local_best;
1184 /* skip ignore colors */
1185 if (bitset_is_set(env->ignore_regs, col))
1188 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1190 /* suppose we can color all nodes to the same color */
1193 INIT_LIST_HEAD(&changed_ones);
1195 /* try to bring all nodes of given chunk to the current color. */
1196 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1197 ir_node *irn = c->n[idx];
1198 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1201 assert(! node->fixed && "Node must not have a fixed color.");
1202 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1205 The order of the colored nodes is important, so we record the successfully
1206 colored ones in the order they appeared.
1208 good = change_node_color(env, node, col, &changed_ones);
1210 waitq_put(good_starts, node);
1216 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1219 /* try next color when failed */
1221 reject_coloring(&changed_ones);
1225 /* fragment the chunk according to the coloring */
1226 local_best = fragment_chunk(env, col, c, tmp_chunks);
1228 /* search the best of the good list
1229 and make it the new best if it is better than the current */
1231 aff_chunk_assure_weight(env, local_best);
1233 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1234 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1236 if (! best_chunk || best_chunk->weight < local_best->weight) {
1237 best_chunk = local_best;
1240 del_waitq(best_starts);
1241 best_starts = good_starts;
1242 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1244 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1245 del_waitq(good_starts);
1249 del_waitq(good_starts);
1252 reject_coloring(&changed_ones);
1255 /* free all intermediate created chunks except best one */
1256 while (! waitq_empty(tmp_chunks)) {
1257 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1258 if (tmp != best_chunk)
1259 delete_aff_chunk(env, tmp);
1261 del_waitq(tmp_chunks);
1263 /* return if coloring failed */
1266 del_waitq(best_starts);
1270 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1271 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1272 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1274 INIT_LIST_HEAD(&changed_ones);
1275 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1276 ir_node *irn = best_chunk->n[idx];
1277 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1280 /* bring the node to the color. */
1281 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
1282 INIT_LIST_HEAD(&changed_ones);
1283 res = change_node_color(env, node, best_color, &changed_ones);
1285 materialize_coloring(&changed_ones);
1290 /* remove the nodes in best chunk from original chunk */
1291 bitset_andnot(c->nodes, best_chunk->nodes);
1292 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1293 ir_node *irn = c->n[idx];
1295 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1296 int last = ARR_LEN(c->n) - 1;
1298 c->n[idx] = c->n[last];
1299 ARR_SHRINKLEN(c->n, last);
1304 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1305 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1306 ir_node *n = c->n[idx];
1307 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1311 /* fragment the remaining chunk */
1312 visited = bitset_irg_malloc(env->co->irg);
1313 bitset_or(visited, best_chunk->nodes);
1314 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1315 ir_node *irn = c->n[idx];
1316 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1317 aff_chunk_t *new_chunk = new_aff_chunk(env);
1318 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1320 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1321 aff_chunk_assure_weight(env, new_chunk);
1322 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1326 /* clear obsolete chunks and free some memory */
1327 delete_aff_chunk(env, best_chunk);
1328 bitset_free(visited);
1330 del_waitq(best_starts);
1334 * Main driver for mst safe coalescing algorithm.
1336 int co_solve_heuristic_mst(copy_opt_t *co) {
1337 unsigned n_regs = co->cls->n_regs;
1338 bitset_t *ignore_regs = bitset_alloca(n_regs);
1341 co_mst_env_t mst_env;
1344 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1346 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1349 mst_env.n_regs = n_regs;
1351 mst_env.chunks = new_pqueue();
1353 mst_env.ignore_regs = ignore_regs;
1354 mst_env.ifg = co->cenv->ifg;
1355 mst_env.aenv = co->aenv;
1356 mst_env.chunkset = pset_new_ptr(512);
1358 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1360 /* build affinity chunks */
1361 build_affinity_chunks(&mst_env);
1363 /* color chunks as long as there are some */
1364 while (! pqueue_empty(mst_env.chunks)) {
1365 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1367 color_aff_chunk(&mst_env, chunk);
1368 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1369 delete_aff_chunk(&mst_env, chunk);
1372 /* apply coloring */
1373 foreach_phase_irn(&mst_env.ph, irn) {
1374 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1375 const arch_register_t *reg;
1377 if (arch_irn_is(mst_env.aenv, irn, ignore))
1380 // assert(mirn->fixed && "Node should have fixed color");
1382 /* skip nodes where color hasn't changed */
1383 if (mirn->init_col == mirn->col)
1386 reg = arch_register_for_index(co->cls, mirn->col);
1387 arch_set_irn_register(co->aenv, irn, reg);
1388 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1391 /* free allocated memory */
1392 del_pqueue(mst_env.chunks);
1393 phase_free(&mst_env.ph);
1394 del_pset(mst_env.chunkset);
1399 void be_init_copyheur4(void) {
1400 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1403 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);