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;
81 static int recolor_limit = 4;
83 typedef struct _col_cost_t {
91 typedef struct _aff_chunk_t {
92 ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
93 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
94 bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
95 int weight; /**< Weight of this chunk */
96 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
97 unsigned deleted : 1; /**< Set if the was deleted. */
98 int id; /**< For debugging: An id of this chunk. */
99 col_cost_t *color_affinity;
105 typedef struct _aff_edge_t {
106 ir_node *src; /**< Source node. */
107 ir_node *tgt; /**< Target node. */
108 double weight; /**< The weight of this edge. */
111 /* main coalescing environment */
112 typedef struct _co_mst_env_t {
113 int n_regs; /**< number of regs in class */
114 int k; /**< number of non-ignore registers in class */
115 bitset_t *ignore_regs; /**< set containing all global ignore registers */
116 ir_phase ph; /**< phase object holding data for nodes */
117 pqueue *chunks; /**< priority queue for chunks */
118 pset *chunkset; /**< set holding all chunks */
119 be_ifg_t *ifg; /**< the interference graph */
120 const arch_env_t *aenv; /**< the arch environment */
121 copy_opt_t *co; /**< the copy opt object */
124 /* stores coalescing related information for a node */
125 typedef struct _co_mst_irn_t {
126 ir_node *irn; /**< the irn this information belongs to */
127 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
128 bitset_t *adm_colors; /**< set of admissible colors for this irn */
129 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
130 int n_neighs; /**< length of the interfering neighbours array. */
131 int int_aff_neigh; /**< number of interfering affinity neighbours */
132 int col; /**< color currently assigned */
133 int init_col; /**< the initial color */
134 int tmp_col; /**< a temporary assigned color */
135 unsigned fixed : 1; /**< the color is fixed */
136 struct list_head list; /**< Queue for coloring undo. */
137 double constr_factor;
140 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
142 typedef int decide_func_t(const co_mst_irn_t *node, int col);
147 * Write a chunk to stderr for debugging.
149 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
151 if (c->weight_consistent)
152 ir_fprintf(stderr, " $%d ", c->weight);
153 ir_fprintf(stderr, "{");
154 bitset_foreach(c->nodes, idx) {
155 ir_node *n = get_idx_irn(env->co->irg, idx);
156 ir_fprintf(stderr, " %+F,", n);
158 ir_fprintf(stderr, "}");
162 * Dump all admissible colors to stderr.
164 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
168 if (bitset_popcnt(node->adm_colors) < 1)
169 fprintf(stderr, "no admissible colors?!?");
171 bitset_foreach(node->adm_colors, idx)
172 fprintf(stderr, " %d", idx);
177 * Dump color-cost pairs to stderr.
179 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
181 for (i = 0; i < env->n_regs; ++i) {
182 if (cost[i].cost == COL_COST_INFEASIBLE)
183 fprintf(stderr, " (%d, INF)", cost[i].col);
185 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
189 #endif /* DEBUG_libfirm */
191 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
192 return node->tmp_col >= 0 ? node->tmp_col : node->col;
196 * @return 1 if node @p node has color @p col, 0 otherwise.
198 static int decider_has_color(const co_mst_irn_t *node, int col) {
199 return get_mst_irn_col(node) == col;
203 * @return 1 if node @p node has not color @p col, 0 otherwise.
205 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
206 return get_mst_irn_col(node) != col;
210 * Always returns true.
212 static int decider_always_yes(const co_mst_irn_t *node, int col) {
218 /** compares two affinity edges by its weight */
219 static int cmp_aff_edge(const void *a, const void *b) {
220 const aff_edge_t *e1 = a;
221 const aff_edge_t *e2 = b;
223 if (e2->weight == e1->weight) {
224 if (e2->src->node_idx == e1->src->node_idx)
225 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
227 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
229 /* sort in descending order */
230 return QSORT_CMP(e2->weight, e1->weight);
233 /** compares to color-cost pairs */
234 static int cmp_col_cost(const void *a, const void *b) {
235 const col_cost_t *c1 = a;
236 const col_cost_t *c2 = b;
237 double diff = c1->cost - c2->cost;
238 return (diff > 0) - (diff < 0);
242 * Creates a new affinity chunk
244 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
245 aff_chunk_t *c = xmalloc(sizeof(*c));
247 c->weight_consistent = 0;
248 c->n = NEW_ARR_F(ir_node *, 0);
249 c->nodes = bitset_irg_malloc(env->co->irg);
250 c->interfere = bitset_irg_malloc(env->co->irg);
251 c->color_affinity = xmalloc(env->k * sizeof(c->color_affinity[0]));
252 c->id = last_chunk_id++;
253 pset_insert(env->chunkset, c, c->id);
258 * Frees all memory allocated by an affinity chunk.
260 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
261 pset_remove(env->chunkset, c, c->id);
262 bitset_free(c->nodes);
263 bitset_free(c->interfere);
264 xfree(c->color_affinity);
271 * Adds a node to an affinity chunk
273 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
276 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
279 c->weight_consistent = 0;
281 bitset_set(c->nodes, get_irn_idx(node->irn));
283 ARR_APP1(ir_node *, c->n, node->irn);
285 for (i = node->n_neighs - 1; i >= 0; --i) {
286 ir_node *neigh = node->int_neighs[i];
287 bitset_set(c->interfere, get_irn_idx(neigh));
292 * In case there is no phase information for irn, initialize it.
294 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
295 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
296 co_mst_env_t *env = ph->priv;
299 const arch_register_req_t *req;
300 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
308 res->int_neighs = NULL;
309 res->int_aff_neigh = 0;
310 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
311 res->init_col = res->col;
312 INIT_LIST_HEAD(&res->list);
314 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
316 /* set admissible registers */
317 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
319 /* Exclude colors not assignable to the irn */
320 req = arch_get_register_req(env->aenv, irn, -1);
321 if (arch_register_req_is(req, limited)) {
322 rbitset_copy_to_bitset(req->limited, res->adm_colors);
323 res->constr_factor = 1.0 - (double) bitset_popcnt(res->adm_colors) / env->k;
326 bitset_set_all(res->adm_colors);
328 /* exclude global ignore registers as well */
329 bitset_andnot(res->adm_colors, env->ignore_regs);
331 /* set the number of interfering affinity neighbours to -1, they are calculated later */
332 res->int_aff_neigh = -1;
334 /* build list of interfering neighbours */
336 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
337 if (! arch_irn_is(env->aenv, neigh, ignore)) {
338 obstack_ptr_grow(phase_obst(ph), neigh);
342 res->int_neighs = obstack_finish(phase_obst(ph));
349 * Check if affinity chunk @p chunk interferes with node @p irn.
351 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
353 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
357 * Check if there are interference edges from c1 to c2.
358 * @param env The global co_mst environment
360 * @param c2 Another chunk
361 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
363 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
368 /* check if there is a node in c2 having an interfering neighbor in c1 */
369 return bitset_intersect(c1->interfere, c2->nodes);
373 * Returns the affinity chunk of @p irn or creates a new
374 * one with @p irn as element if there is none assigned.
376 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
377 co_mst_irn_t *node = get_co_mst_irn(env, irn);
382 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
383 * are no interference edges from chunk(src) to chunk(tgt)).
384 * @return 1 if successful, 0 if not possible
386 static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
387 aff_chunk_t *c1 = get_aff_chunk(env, src);
388 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
391 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
393 DBG_AFF_CHUNK(env, LEVEL_4, c1);
395 DB((dbg, LEVEL_4, "{%+F}", src));
397 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
399 DBG_AFF_CHUNK(env, LEVEL_4, c2);
401 DB((dbg, LEVEL_4, "{%+F}", tgt));
403 DB((dbg, LEVEL_4, "\n"));
408 /* no chunk exists */
409 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
412 for (i = mirn->n_neighs - 1; i >= 0; --i) {
413 if (mirn->int_neighs[i] == tgt)
417 /* create one containing both nodes */
418 c1 = new_aff_chunk(env);
419 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
420 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
424 /* c2 already exists */
425 if (! aff_chunk_interferes(env, c2, src)) {
426 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
430 } else if (c2 == NULL) {
431 /* c1 already exists */
432 if (! aff_chunk_interferes(env, c1, tgt)) {
433 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
436 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
439 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) {
440 ir_node *n = c2->n[idx];
441 co_mst_irn_t *mn = get_co_mst_irn(env, n);
445 if (! bitset_is_set(c1->nodes, get_irn_idx(n)))
446 ARR_APP1(ir_node *, c1->n, n);
449 bitset_or(c1->nodes, c2->nodes);
450 bitset_or(c1->interfere, c2->interfere);
451 c1->weight_consistent = 0;
453 delete_aff_chunk(env, c2);
456 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
460 DB((dbg, LEVEL_4, " ... absorbed\n"));
465 * Assures that the weight of the given chunk is consistent.
467 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
468 if (! c->weight_consistent) {
472 for (i = 0; i < env->k; ++i) {
473 c->color_affinity[i].col = i;
474 c->color_affinity[i].cost = 0.0;
477 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
478 ir_node *n = c->n[idx];
479 const affinity_node_t *an = get_affinity_info(env->co, n);
480 co_mst_irn_t *node = get_co_mst_irn(env, n);
482 if (node->constr_factor > 0.0) {
484 bitset_foreach (node->adm_colors, col)
485 c->color_affinity[col].cost -= node->constr_factor;
490 co_gs_foreach_neighb(an, neigh) {
491 const ir_node *m = neigh->irn;
492 const int m_idx = get_irn_idx(m);
494 /* skip ignore nodes */
495 if (arch_irn_is(env->aenv, m, ignore))
498 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
504 c->weight_consistent = 1;
509 * Count the number of interfering affinity neighbours
511 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
512 const neighb_t *neigh;
513 ir_node *irn = an->irn;
514 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
517 co_gs_foreach_neighb(an, neigh) {
518 const ir_node *n = neigh->irn;
521 /* skip ignore nodes */
522 if (arch_irn_is(env->aenv, n, ignore))
525 /* check if the affinity neighbour interfere */
526 for (i = 0; i < node->n_neighs; ++i) {
527 if (node->int_neighs[i] == n) {
538 * Build chunks of nodes connected by affinity edges.
539 * We start at the heaviest affinity edge.
540 * The chunks of the two edge-defining nodes will be
541 * merged if there are no interference edges from one
542 * chunk to the other.
544 static void build_affinity_chunks(co_mst_env_t *env) {
545 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
546 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
549 aff_chunk_t *curr_chunk;
551 /* at first we create the affinity edge objects */
552 be_ifg_foreach_node(env->ifg, nodes_it, n) {
553 int n_idx = get_irn_idx(n);
557 /* skip ignore nodes */
558 if (arch_irn_is(env->aenv, n, ignore))
561 n1 = get_co_mst_irn(env, n);
562 an = get_affinity_info(env->co, n);
567 if (n1->int_aff_neigh < 0)
568 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
570 /* build the affinity edges */
571 co_gs_foreach_neighb(an, neigh) {
572 ir_node *m = neigh->irn;
573 int m_idx = get_irn_idx(m);
575 /* record the edge in only one direction */
580 /* skip ignore nodes */
581 if (arch_irn_is(env->aenv, m, ignore))
587 n2 = get_co_mst_irn(env, m);
588 if (n2->int_aff_neigh < 0) {
589 affinity_node_t *am = get_affinity_info(env->co, m);
590 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
593 * these weights are pure hackery ;-).
594 * It's not chriswue's fault but mine.
596 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
597 ARR_APP1(aff_edge_t, edges, edge);
603 /* now: sort edges and build the affinity chunks */
604 len = ARR_LEN(edges);
605 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
606 for (i = 0; i < len; ++i) {
607 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
609 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
612 /* now insert all chunks into a priority queue */
613 foreach_pset(env->chunkset, curr_chunk) {
614 aff_chunk_assure_weight(env, curr_chunk);
616 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
617 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
618 DBG((dbg, LEVEL_1, "\n"));
620 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
622 foreach_phase_irn(&env->ph, n) {
623 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
625 if (mirn->chunk == NULL) {
626 /* no chunk is allocated so far, do it now */
627 aff_chunk_t *curr_chunk = new_aff_chunk(env);
628 aff_chunk_add_node(curr_chunk, mirn);
630 aff_chunk_assure_weight(env, curr_chunk);
632 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
633 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
634 DBG((dbg, LEVEL_1, "\n"));
636 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
643 static void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
645 pqueue *grow = new_pqueue();
648 ir_node *max_node = NULL;
650 for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
651 ir_node *irn = chunk->n[i];
652 affinity_node_t *an = get_affinity_info(env->co, irn);
656 if (arch_irn_is(env->aenv, irn, ignore))
660 co_gs_foreach_neighb(an, neigh)
663 if (w > max_weight) {
671 bitset_t *visited = bitset_irg_malloc(env->co->irg);
673 for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
674 bitset_add_irn(visited, chunk->n[i]);
676 pqueue_put(grow, max_node, max_weight);
677 bitset_remv_irn(visited, max_node);
679 while (!pqueue_empty(grow)) {
680 ir_node *irn = pqueue_get(grow);
681 affinity_node_t *an = get_affinity_info(env->co, irn);
684 if (arch_irn_is(env->aenv, irn, ignore))
687 assert(i <= ARR_LEN(chunk->n));
692 /* build the affinity edges */
693 co_gs_foreach_neighb(an, neigh) {
694 co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
696 if (bitset_contains_irn(visited, node->irn)) {
697 pqueue_put(grow, neigh->irn, neigh->costs);
698 bitset_remv_irn(visited, node->irn);
704 bitset_free(visited);
709 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
711 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
712 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
714 waitq *nodes = new_waitq();
716 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
718 /* init queue and chunk */
719 waitq_put(nodes, node);
720 bitset_set(visited, get_irn_idx(node->irn));
721 aff_chunk_add_node(chunk, node);
722 DB((dbg, LEVEL_1, " %+F", node->irn));
724 /* as long as there are nodes in the queue */
725 while (! waitq_empty(nodes)) {
726 co_mst_irn_t *n = waitq_get(nodes);
727 affinity_node_t *an = get_affinity_info(env->co, n->irn);
729 /* check all affinity neighbors */
732 co_gs_foreach_neighb(an, neigh) {
733 ir_node *m = neigh->irn;
734 int m_idx = get_irn_idx(m);
737 /* skip ignore nodes */
738 if (arch_irn_is(env->aenv, m, ignore))
741 n2 = get_co_mst_irn(env, m);
743 if (! bitset_is_set(visited, m_idx) &&
746 ! aff_chunk_interferes(env, chunk, m) &&
747 bitset_is_set(orig_chunk->nodes, m_idx))
750 following conditions are met:
751 - neighbour is not visited
752 - neighbour likes the color
753 - neighbour has not yet a fixed color
754 - the new chunk doesn't interfere with the neighbour
755 - neighbour belongs or belonged once to the original chunk
757 bitset_set(visited, m_idx);
758 aff_chunk_add_node(chunk, n2);
759 DB((dbg, LEVEL_1, " %+F", n2->irn));
760 /* enqueue for further search */
761 waitq_put(nodes, n2);
767 DB((dbg, LEVEL_1, "\n"));
773 * Fragment the given chunk into chunks having given color and not having given color.
775 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
776 bitset_t *visited = bitset_irg_malloc(env->co->irg);
778 aff_chunk_t *best = NULL;
780 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
783 aff_chunk_t *tmp_chunk;
784 decide_func_t *decider;
788 if (bitset_is_set(visited, get_irn_idx(irn)))
791 node = get_co_mst_irn(env, irn);
793 if (get_mst_irn_col(node) == col) {
794 decider = decider_has_color;
796 DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
799 decider = decider_hasnot_color;
801 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
804 /* create a new chunk starting at current node */
805 tmp_chunk = new_aff_chunk(env);
806 waitq_put(tmp, tmp_chunk);
807 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
808 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
810 /* remember the local best */
811 aff_chunk_assure_weight(env, tmp_chunk);
812 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
816 assert(best && "No chunk found?");
817 bitset_free(visited);
822 * Initializes an array of color-cost pairs.
823 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
825 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
828 for (i = 0; i < env->n_regs; ++i) {
830 if (bitset_is_set(env->ignore_regs, i))
831 cost[i].cost = COL_COST_INFEASIBLE;
838 * Initializes an array of color-cost pairs.
839 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
841 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
842 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
843 col_cost_init(env, cost, COL_COST_INFEASIBLE);
850 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
851 * ATTENTION: the queue is empty after calling this function!
853 static INLINE void reject_coloring(struct list_head *nodes) {
854 co_mst_irn_t *n, *temp;
855 DB((dbg, LEVEL_4, "\treject coloring for"));
856 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
857 DB((dbg, LEVEL_4, " %+F", n->irn));
858 assert(n->tmp_col >= 0);
860 list_del_init(&n->list);
862 DB((dbg, LEVEL_4, "\n"));
865 static INLINE void materialize_coloring(struct list_head *nodes) {
866 co_mst_irn_t *n, *temp;
867 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
868 assert(n->tmp_col >= 0);
871 list_del_init(&n->list);
875 static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
878 assert(!node->fixed);
879 assert(node->tmp_col < 0);
880 assert(node->list.next == &node->list && node->list.prev == &node->list);
882 list_add_tail(&node->list, changed);
886 static INLINE int is_loose(co_mst_irn_t *node)
888 return !node->fixed && node->tmp_col < 0;
892 * Determines the costs for each color if it would be assigned to node @p node.
894 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
895 affinity_node_t *an = get_affinity_info(env->co, node->irn);
900 col_cost_init(env, costs, 0.0);
902 /* calculate (negative) costs for affinity neighbours */
904 co_gs_foreach_neighb(an, aff_neigh) {
905 ir_node *m = aff_neigh->irn;
909 /* skip ignore nodes */
910 if (arch_irn_is(env->aenv, m, ignore))
913 neigh = get_co_mst_irn(env, m);
914 c = (double)aff_neigh->costs;
916 /* calculate costs for fixed affinity neighbours */
917 if (!is_loose(neigh)) {
918 int col = get_mst_irn_col(neigh);
919 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
924 /* calculate (positive) costs for interfering neighbours */
925 for (i = 0; i < node->n_neighs; ++i) {
930 int_neigh = node->int_neighs[i];
932 assert(!arch_irn_is(env->aenv, int_neigh, ignore));
934 neigh = get_co_mst_irn(env, int_neigh);
935 col = get_mst_irn_col(neigh);
936 col_cnt = bitset_popcnt(neigh->adm_colors);
938 if (!is_loose(neigh)) {
939 /* colors of fixed interfering neighbours are infeasible */
940 costs[col].cost = COL_COST_INFEASIBLE;
942 else if (col_cnt < env->k) {
943 /* calculate costs for constrained interfering neighbours */
944 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
946 bitset_foreach_clear(neigh->adm_colors, idx) {
947 /* check only explicitly forbidden colors (skip global forbidden ones) */
948 if (! bitset_is_set(env->ignore_regs, idx)) {
949 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
954 DB((dbg, LEVEL_4, "\tneigh %+F, loose: %d, color: %d\n", int_neigh, is_loose(neigh), col));
957 /* set all not admissible colors to COL_COST_INFEASIBLE */
958 bitset_foreach_clear(node->adm_colors, idx)
959 costs[idx].cost = COL_COST_INFEASIBLE;
962 /* need forward declaration due to recursive call */
963 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth);
966 * Tries to change node to a color but @p explude_col.
967 * @return 1 if succeeded, 0 otherwise.
969 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed_ones, int depth) {
970 int col = get_mst_irn_col(node);
973 /* neighbours has already a different color -> good, temporary fix it */
974 if (col != exclude_col) {
976 set_temp_color(node, col, changed_ones);
980 /* The node has the color it should not have _and_ has not been visited yet. */
981 if (is_loose(node)) {
982 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
984 /* Get the costs for giving the node a specific color. */
985 determine_color_costs(env, node, costs);
987 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
988 costs[exclude_col].cost = COL_COST_INFEASIBLE;
990 /* sort the colors according costs, cheapest first. */
991 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
993 /* Try recoloring the node using the color list. */
994 res = recolor_nodes(env, node, costs, changed_ones, depth + 1);
1001 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
1002 * ATTENTION: Expect @p costs already sorted by increasing costs.
1003 * @return 1 if coloring could be applied, 0 otherwise.
1005 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones, int depth) {
1007 struct list_head local_changed;
1009 if (depth >= recolor_limit)
1012 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
1013 DBG_COL_COST(env, LEVEL_1, costs);
1014 DB((dbg, LEVEL_1, "\n"));
1016 for (i = 0; i < env->n_regs; ++i) {
1017 int tgt_col = costs[i].col;
1021 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
1022 if (costs[i].cost == COL_COST_INFEASIBLE) {
1026 /* Set the new color of the node and mark the node as temporarily fixed. */
1027 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
1028 INIT_LIST_HEAD(&local_changed);
1029 set_temp_color(node, tgt_col, &local_changed);
1030 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
1032 /* try to color all interfering neighbours with current color forbidden */
1033 for (j = 0; j < node->n_neighs; ++j) {
1037 neigh = node->int_neighs[j];
1039 /* skip ignore nodes */
1040 if (arch_irn_is(env->aenv, neigh, ignore))
1043 nn = get_co_mst_irn(env, neigh);
1044 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
1045 neigh, j, nn->fixed, nn->tmp_col, nn->col));
1048 Try to change the color of the neighbor and record all nodes which
1049 get changed in the tmp list. Add this list to the "changed" list for
1050 that color. If we did not succeed to change the color of the neighbor,
1051 we bail out and try the next color.
1053 if (get_mst_irn_col(nn) == tgt_col) {
1054 /* try to color neighbour with tgt_col forbidden */
1055 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1);
1063 We managed to assign the target color to all neighbors, so from the perspective
1064 of the current node, every thing was ok and we can return safely.
1067 /* append the local_changed ones to global ones */
1068 list_splice(&local_changed, changed_ones);
1072 /* coloring of neighbours failed, so we try next color */
1073 reject_coloring(&local_changed);
1081 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1082 * @return 1 if color @p col could be applied, 0 otherwise
1084 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed_ones, int depth) {
1085 int col = get_mst_irn_col(node);
1087 /* if node already has the target color -> good, temporary fix it */
1088 if (col == tgt_col) {
1089 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1091 set_temp_color(node, tgt_col, changed_ones);
1096 Node has not yet a fixed color and target color is admissible
1097 -> try to recolor node and it's affinity neighbours
1099 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1100 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
1103 col_cost_init_single(env, costs, tgt_col);
1105 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1106 res = recolor_nodes(env, node, costs, changed_ones, depth);
1107 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1112 #ifdef DEBUG_libfirm
1113 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1114 if (!is_loose(node))
1115 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1117 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1118 dbg_admissible_colors(env, node);
1119 DB((dbg, LEVEL_4, ")\n"));
1128 * Tries to color an affinity chunk (or at least a part of it).
1129 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1131 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1132 aff_chunk_t *best_chunk = NULL;
1133 int best_color = -1;
1135 waitq *tmp_chunks = new_waitq();
1136 waitq *best_starts = NULL;
1137 col_cost_t *order = alloca(env->k * sizeof(order[0]));
1140 struct list_head changed_ones;
1143 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1144 DBG_AFF_CHUNK(env, LEVEL_2, c);
1145 DB((dbg, LEVEL_2, "\n"));
1147 /* compute color preference */
1148 memcpy(order, c->color_affinity, env->k * sizeof(order[0]));
1150 bitset_foreach (c->interfere, pos) {
1151 ir_node *n = get_idx_irn(env->co->irg, pos);
1152 co_mst_irn_t *node = get_co_mst_irn(env, n);
1155 if (node->constr_factor > 0.0 && is_loose(node)) {
1156 bitset_foreach (node->adm_colors, col)
1157 order[col].cost += node->constr_factor;
1161 qsort(order, env->k, sizeof(order[0]), cmp_col_cost);
1163 chunk_order_nodes(env, c);
1165 /* check which color is the "best" for the given chunk.
1166 * if we found a color which was ok for all nodes, we take it
1167 * and do not look further. (see did_all flag usage below.)
1168 * If we have many colors which fit all nodes it is hard to decide
1169 * which one to take anyway.
1170 * TODO Sebastian: Perhaps we should at all nodes and figure out
1171 * a suitable color using costs as done above (determine_color_costs).
1173 for (i = 0; i < env->k && !did_all; ++i) {
1174 int col = order[i].col;
1176 waitq *good_starts = new_waitq();
1177 aff_chunk_t *local_best;
1179 /* skip ignore colors */
1180 if (bitset_is_set(env->ignore_regs, col))
1183 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1185 /* suppose we can color all nodes to the same color */
1188 INIT_LIST_HEAD(&changed_ones);
1190 /* try to bring all nodes of given chunk to the current color. */
1191 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1192 ir_node *irn = c->n[idx];
1193 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1196 assert(! node->fixed && "Node must not have a fixed color.");
1197 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1200 The order of the colored nodes is important, so we record the successfully
1201 colored ones in the order they appeared.
1203 good = change_node_color(env, node, col, &changed_ones, 0);
1205 waitq_put(good_starts, node);
1211 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1214 /* try next color when failed */
1216 reject_coloring(&changed_ones);
1220 /* fragment the chunk according to the coloring */
1221 local_best = fragment_chunk(env, col, c, tmp_chunks);
1223 /* search the best of the good list
1224 and make it the new best if it is better than the current */
1226 aff_chunk_assure_weight(env, local_best);
1228 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1229 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1231 if (! best_chunk || best_chunk->weight < local_best->weight) {
1232 best_chunk = local_best;
1235 del_waitq(best_starts);
1236 best_starts = good_starts;
1237 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1239 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1240 del_waitq(good_starts);
1244 del_waitq(good_starts);
1247 reject_coloring(&changed_ones);
1250 /* free all intermediate created chunks except best one */
1251 while (! waitq_empty(tmp_chunks)) {
1252 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1253 if (tmp != best_chunk)
1254 delete_aff_chunk(env, tmp);
1256 del_waitq(tmp_chunks);
1258 /* return if coloring failed */
1261 del_waitq(best_starts);
1265 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1266 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1267 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1269 INIT_LIST_HEAD(&changed_ones);
1270 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1271 ir_node *irn = best_chunk->n[idx];
1272 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1275 /* bring the node to the color. */
1276 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
1277 INIT_LIST_HEAD(&changed_ones);
1278 res = change_node_color(env, node, best_color, &changed_ones, 0);
1280 materialize_coloring(&changed_ones);
1285 /* remove the nodes in best chunk from original chunk */
1286 bitset_andnot(c->nodes, best_chunk->nodes);
1287 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1288 ir_node *irn = c->n[idx];
1290 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1291 int last = ARR_LEN(c->n) - 1;
1293 c->n[idx] = c->n[last];
1294 ARR_SHRINKLEN(c->n, last);
1299 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1300 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1301 ir_node *n = c->n[idx];
1302 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1306 /* fragment the remaining chunk */
1307 visited = bitset_irg_malloc(env->co->irg);
1308 bitset_or(visited, best_chunk->nodes);
1309 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1310 ir_node *irn = c->n[idx];
1311 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1312 aff_chunk_t *new_chunk = new_aff_chunk(env);
1313 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1315 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1316 aff_chunk_assure_weight(env, new_chunk);
1317 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1321 /* clear obsolete chunks and free some memory */
1322 delete_aff_chunk(env, best_chunk);
1323 bitset_free(visited);
1325 del_waitq(best_starts);
1329 * Main driver for mst safe coalescing algorithm.
1331 int co_solve_heuristic_mst(copy_opt_t *co) {
1332 unsigned n_regs = co->cls->n_regs;
1333 bitset_t *ignore_regs = bitset_alloca(n_regs);
1336 co_mst_env_t mst_env;
1339 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1341 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1344 mst_env.n_regs = n_regs;
1346 mst_env.chunks = new_pqueue();
1348 mst_env.ignore_regs = ignore_regs;
1349 mst_env.ifg = co->cenv->ifg;
1350 mst_env.aenv = co->aenv;
1351 mst_env.chunkset = pset_new_ptr(512);
1353 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1355 /* build affinity chunks */
1356 build_affinity_chunks(&mst_env);
1358 /* color chunks as long as there are some */
1359 while (! pqueue_empty(mst_env.chunks)) {
1360 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1362 color_aff_chunk(&mst_env, chunk);
1363 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1364 delete_aff_chunk(&mst_env, chunk);
1367 /* apply coloring */
1368 foreach_phase_irn(&mst_env.ph, irn) {
1369 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1370 const arch_register_t *reg;
1372 if (arch_irn_is(mst_env.aenv, irn, ignore))
1375 // assert(mirn->fixed && "Node should have fixed color");
1377 /* skip nodes where color hasn't changed */
1378 if (mirn->init_col == mirn->col)
1381 reg = arch_register_for_index(co->cls, mirn->col);
1382 arch_set_irn_register(co->aenv, irn, reg);
1383 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1386 /* free allocated memory */
1387 del_pqueue(mst_env.chunks);
1388 phase_free(&mst_env.ph);
1389 del_pset(mst_env.chunkset);
1394 static const lc_opt_table_entry_t options[] = {
1395 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1400 void be_init_copyheur4(void) {
1401 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1402 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1403 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1404 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1405 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1407 lc_opt_add_table(heur4_grp, options);
1408 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1411 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);