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"
55 #include "becopyopt_t.h"
59 #define COL_COST_INFEASIBLE DBL_MAX
60 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
61 #define NEIGHBOUR_CONSTR_COSTS 64.0
65 #define DBG_AFF_CHUNK(env, level, chunk)
66 #define DBG_COL_COST(env, level, cost)
70 static firm_dbg_module_t *dbg = NULL;
71 #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0)
72 #define DBG_COL_COST(env, level, cost) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0)
76 static int last_chunk_id = 0;
78 typedef struct _col_cost_t {
86 typedef struct _aff_chunk_t {
87 ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
88 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
89 bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
90 int weight; /**< Weight of this chunk */
91 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
92 unsigned deleted : 1; /**< Set if the was deleted. */
93 int id; /**< For debugging: An id of this chunk. */
99 typedef struct _aff_edge_t {
100 ir_node *src; /**< Source node. */
101 ir_node *tgt; /**< Target node. */
102 double weight; /**< The weight of this edge. */
105 /* main coalescing environment */
106 typedef struct _co_mst_env_t {
107 int n_regs; /**< number of regs in class */
108 int k; /**< number of non-ignore registers in class */
109 bitset_t *ignore_regs; /**< set containing all global ignore registers */
110 ir_phase ph; /**< phase object holding data for nodes */
111 pqueue *chunks; /**< priority queue for chunks */
112 pset *chunkset; /**< set holding all chunks */
113 be_ifg_t *ifg; /**< the interference graph */
114 const arch_env_t *aenv; /**< the arch environment */
115 copy_opt_t *co; /**< the copy opt object */
118 /* stores coalescing related information for a node */
119 typedef struct _co_mst_irn_t {
120 ir_node *irn; /**< the irn this information belongs to */
121 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
122 bitset_t *adm_colors; /**< set of admissible colors for this irn */
123 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
124 int n_neighs; /**< length of the interfering neighbours array. */
125 int int_aff_neigh; /**< number of interfering affinity neighbours */
126 int col; /**< color currently assigned */
127 int init_col; /**< the initial color */
128 int tmp_col; /**< a temporary assigned color */
129 unsigned fixed : 1; /**< the color is fixed */
130 struct list_head list; /**< Queue for coloring undo. */
133 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
135 typedef int decide_func_t(const co_mst_irn_t *node, int col);
140 * Write a chunk to stderr for debugging.
142 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
144 if (c->weight_consistent)
145 ir_fprintf(stderr, " $%d ", c->weight);
146 ir_fprintf(stderr, "{");
147 bitset_foreach(c->nodes, idx) {
148 ir_node *n = get_idx_irn(env->co->irg, idx);
149 ir_fprintf(stderr, " %+F,", n);
151 ir_fprintf(stderr, "}");
155 * Dump all admissible colors to stderr.
157 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
161 if (bitset_popcnt(node->adm_colors) < 1)
162 fprintf(stderr, "no admissible colors?!?");
164 bitset_foreach(node->adm_colors, idx)
165 fprintf(stderr, " %d", idx);
170 * Dump color-cost pairs to stderr.
172 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
174 for (i = 0; i < env->n_regs; ++i) {
175 if (cost[i].cost == COL_COST_INFEASIBLE)
176 fprintf(stderr, " (%d, INF)", cost[i].col);
178 fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
182 #endif /* DEBUG_libfirm */
184 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
185 return node->tmp_col >= 0 ? node->tmp_col : node->col;
189 * @return 1 if node @p node has color @p col, 0 otherwise.
191 static int decider_has_color(const co_mst_irn_t *node, int col) {
192 return get_mst_irn_col(node) == col;
196 * @return 1 if node @p node has not color @p col, 0 otherwise.
198 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
199 return get_mst_irn_col(node) != col;
203 * Always returns true.
205 static int decider_always_yes(const co_mst_irn_t *node, int col) {
211 static int cmp_node_order(const void *a, const void *b)
216 /** compares two affinity edges by its weight */
217 static int cmp_aff_edge(const void *a, const void *b) {
218 const aff_edge_t *e1 = a;
219 const aff_edge_t *e2 = b;
221 if (e2->weight == e1->weight) {
222 if (e2->src->node_idx == e1->src->node_idx)
223 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
225 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
227 /* sort in descending order */
228 return QSORT_CMP(e2->weight, e1->weight);
231 /** compares to color-cost pairs */
232 static int cmp_col_cost(const void *a, const void *b) {
233 const col_cost_t *c1 = a;
234 const col_cost_t *c2 = b;
236 return c1->cost < c2->cost ? -1 : 1;
240 * Creates a new affinity chunk
242 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
243 aff_chunk_t *c = xmalloc(sizeof(*c));
245 c->weight_consistent = 0;
246 c->n = NEW_ARR_F(ir_node *, 0);
247 c->nodes = bitset_irg_malloc(env->co->irg);
248 c->interfere = bitset_irg_malloc(env->co->irg);
249 c->id = last_chunk_id++;
250 pset_insert(env->chunkset, c, c->id);
255 * Frees all memory allocated by an affinity chunk.
257 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
258 pset_remove(env->chunkset, c, c->id);
259 bitset_free(c->nodes);
260 bitset_free(c->interfere);
267 * Adds a node to an affinity chunk
269 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
272 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
275 c->weight_consistent = 0;
277 bitset_set(c->nodes, get_irn_idx(node->irn));
279 ARR_APP1(ir_node *, c->n, node->irn);
281 for (i = node->n_neighs - 1; i >= 0; --i) {
282 ir_node *neigh = node->int_neighs[i];
283 bitset_set(c->interfere, get_irn_idx(neigh));
288 * In case there is no phase information for irn, initialize it.
290 static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
291 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
292 co_mst_env_t *env = ph->priv;
295 const arch_register_req_t *req;
296 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
304 res->int_neighs = NULL;
305 res->int_aff_neigh = 0;
306 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
307 res->init_col = res->col;
308 INIT_LIST_HEAD(&res->list);
310 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
312 /* set admissible registers */
313 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
315 /* Exclude colors not assignable to the irn */
316 req = arch_get_register_req(env->aenv, irn, -1);
317 if (arch_register_req_is(req, limited))
318 rbitset_copy_to_bitset(req->limited, res->adm_colors);
320 bitset_set_all(res->adm_colors);
322 /* exclude global ignore registers as well */
323 bitset_andnot(res->adm_colors, env->ignore_regs);
325 /* set the number of interfering affinity neighbours to -1, they are calculated later */
326 res->int_aff_neigh = -1;
328 /* build list of interfering neighbours */
330 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
331 if (! arch_irn_is(env->aenv, neigh, ignore)) {
332 obstack_ptr_grow(phase_obst(ph), neigh);
336 res->int_neighs = obstack_finish(phase_obst(ph));
343 * Check if affinity chunk @p chunk interferes with node @p irn.
345 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, ir_node *irn) {
347 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
351 * Check if there are interference edges from c1 to c2.
352 * @param env The global co_mst environment
354 * @param c2 Another chunk
355 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
357 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
363 /* check if there is a node in c2 having an interfering neighbor in c1 */
364 tmp = bitset_alloca(get_irg_last_idx(env->co->irg));
365 tmp = bitset_copy(tmp, c1->interfere);
366 tmp = bitset_and(tmp, c2->nodes);
368 return bitset_popcnt(tmp) > 0;
372 * Returns the affinity chunk of @p irn or creates a new
373 * one with @p irn as element if there is none assigned.
375 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
376 co_mst_irn_t *node = get_co_mst_irn(env, irn);
381 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
382 * are no interference edges from chunk(src) to chunk(tgt)).
383 * @return 1 if successful, 0 if not possible
385 static int aff_chunk_absorb(co_mst_env_t *env, ir_node *src, ir_node *tgt) {
386 aff_chunk_t *c1 = get_aff_chunk(env, src);
387 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
390 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
392 DBG_AFF_CHUNK(env, LEVEL_4, c1);
394 DB((dbg, LEVEL_4, "{%+F}", src));
396 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
398 DBG_AFF_CHUNK(env, LEVEL_4, c2);
400 DB((dbg, LEVEL_4, "{%+F}", tgt));
402 DB((dbg, LEVEL_4, "\n"));
407 /* no chunk exists */
408 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
411 for (i = mirn->n_neighs - 1; i >= 0; --i) {
412 if (mirn->int_neighs[i] == tgt)
416 /* create one containing both nodes */
417 c1 = new_aff_chunk(env);
418 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
419 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
423 /* c2 already exists */
424 if (! aff_chunk_interferes(env, c2, src)) {
425 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
429 } else if (c2 == NULL) {
430 /* c1 already exists */
431 if (! aff_chunk_interferes(env, c1, tgt)) {
432 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
435 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
438 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx) {
439 ir_node *n = c2->n[idx];
440 co_mst_irn_t *mn = get_co_mst_irn(env, n);
444 if (! bitset_is_set(c1->nodes, get_irn_idx(n)))
445 ARR_APP1(ir_node *, c1->n, n);
448 bitset_or(c1->nodes, c2->nodes);
449 bitset_or(c1->interfere, c2->interfere);
450 c1->weight_consistent = 0;
452 delete_aff_chunk(env, c2);
455 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
459 DB((dbg, LEVEL_4, " ... absorbed\n"));
464 * Assures that the weight of the given chunk is consistent.
466 static void aff_chunk_assure_weight(const co_mst_env_t *env, aff_chunk_t *c) {
467 if (! c->weight_consistent) {
471 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
472 ir_node *n = c->n[idx];
473 const affinity_node_t *an = get_affinity_info(env->co, n);
477 co_gs_foreach_neighb(an, neigh) {
478 const ir_node *m = neigh->irn;
479 const int m_idx = get_irn_idx(m);
481 /* skip ignore nodes */
482 if (arch_irn_is(env->aenv, m, ignore))
485 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
491 c->weight_consistent = 1;
496 * Count the number of interfering affinity neighbours
498 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
499 const neighb_t *neigh;
500 ir_node *irn = an->irn;
501 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
504 co_gs_foreach_neighb(an, neigh) {
505 const ir_node *n = neigh->irn;
508 /* skip ignore nodes */
509 if (arch_irn_is(env->aenv, n, ignore))
512 /* check if the affinity neighbour interfere */
513 for (i = 0; i < node->n_neighs; ++i) {
514 if (node->int_neighs[i] == n) {
525 * Build chunks of nodes connected by affinity edges.
526 * We start at the heaviest affinity edge.
527 * The chunks of the two edge-defining nodes will be
528 * merged if there are no interference edges from one
529 * chunk to the other.
531 static void build_affinity_chunks(co_mst_env_t *env) {
532 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
533 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
536 aff_chunk_t *curr_chunk;
538 /* at first we create the affinity edge objects */
539 be_ifg_foreach_node(env->ifg, nodes_it, n) {
540 int n_idx = get_irn_idx(n);
544 /* skip ignore nodes */
545 if (arch_irn_is(env->aenv, n, ignore))
548 n1 = get_co_mst_irn(env, n);
549 an = get_affinity_info(env->co, n);
554 if (n1->int_aff_neigh < 0)
555 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
557 /* build the affinity edges */
558 co_gs_foreach_neighb(an, neigh) {
559 ir_node *m = neigh->irn;
560 int m_idx = get_irn_idx(m);
562 /* record the edge in only one direction */
567 /* skip ignore nodes */
568 if (arch_irn_is(env->aenv, m, ignore))
574 n2 = get_co_mst_irn(env, m);
575 if (n2->int_aff_neigh < 0) {
576 affinity_node_t *am = get_affinity_info(env->co, m);
577 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
580 * these weights are pure hackery ;-).
581 * It's not chriswue's fault but mine.
583 edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
584 ARR_APP1(aff_edge_t, edges, edge);
590 /* now: sort edges and build the affinity chunks */
591 len = ARR_LEN(edges);
592 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
593 for (i = 0; i < len; ++i) {
594 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
596 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
599 /* now insert all chunks into a priority queue */
600 foreach_pset(env->chunkset, curr_chunk) {
601 aff_chunk_assure_weight(env, curr_chunk);
603 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
604 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
605 DBG((dbg, LEVEL_1, "\n"));
607 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
609 foreach_phase_irn(&env->ph, n) {
610 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
612 if (mirn->chunk == NULL) {
613 /* no chunk is allocated so far, do it now */
614 aff_chunk_t *curr_chunk = new_aff_chunk(env);
615 aff_chunk_add_node(curr_chunk, mirn);
617 aff_chunk_assure_weight(env, curr_chunk);
619 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
620 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
621 DBG((dbg, LEVEL_1, "\n"));
623 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
631 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
633 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
634 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
636 waitq *nodes = new_waitq();
638 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
640 /* init queue and chunk */
641 waitq_put(nodes, node);
642 bitset_set(visited, get_irn_idx(node->irn));
643 aff_chunk_add_node(chunk, node);
644 DB((dbg, LEVEL_1, " %+F", node->irn));
646 /* as long as there are nodes in the queue */
647 while (! waitq_empty(nodes)) {
648 co_mst_irn_t *n = waitq_get(nodes);
649 affinity_node_t *an = get_affinity_info(env->co, n->irn);
651 /* check all affinity neighbors */
654 co_gs_foreach_neighb(an, neigh) {
655 ir_node *m = neigh->irn;
656 int m_idx = get_irn_idx(m);
659 /* skip ignore nodes */
660 if (arch_irn_is(env->aenv, m, ignore))
663 n2 = get_co_mst_irn(env, m);
665 if (! bitset_is_set(visited, m_idx) &&
668 ! aff_chunk_interferes(env, chunk, m) &&
669 bitset_is_set(orig_chunk->nodes, m_idx))
672 following conditions are met:
673 - neighbour is not visited
674 - neighbour likes the color
675 - neighbour has not yet a fixed color
676 - the new chunk doesn't interfere with the neighbour
677 - neighbour belongs or belonged once to the original chunk
679 bitset_set(visited, m_idx);
680 aff_chunk_add_node(chunk, n2);
681 DB((dbg, LEVEL_1, " %+F", n2->irn));
682 /* enqueue for further search */
683 waitq_put(nodes, n2);
689 DB((dbg, LEVEL_1, "\n"));
695 * Fragment the given chunk into chunks having given color and not having given color.
697 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
698 bitset_t *visited = bitset_irg_malloc(env->co->irg);
700 aff_chunk_t *best = NULL;
702 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
705 aff_chunk_t *tmp_chunk;
706 decide_func_t *decider;
710 if (bitset_is_set(visited, get_irn_idx(irn)))
713 node = get_co_mst_irn(env, irn);
715 if (get_mst_irn_col(node) == col) {
716 decider = decider_has_color;
718 DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
721 decider = decider_hasnot_color;
723 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
726 /* create a new chunk starting at current node */
727 tmp_chunk = new_aff_chunk(env);
728 waitq_put(tmp, tmp_chunk);
729 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
730 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
732 /* remember the local best */
733 aff_chunk_assure_weight(env, tmp_chunk);
734 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
738 assert(best && "No chunk found?");
739 bitset_free(visited);
744 * Initializes an array of color-cost pairs.
745 * Sets forbidden colors to costs COL_COST_INFEASIBLE and all others to @p c.
747 static INLINE void col_cost_init(co_mst_env_t *env, col_cost_t *cost, double c) {
750 for (i = 0; i < env->n_regs; ++i) {
752 if (bitset_is_set(env->ignore_regs, i))
753 cost[i].cost = COL_COST_INFEASIBLE;
760 * Initializes an array of color-cost pairs.
761 * Sets all colors except color @p col to COL_COST_INFEASIBLE and @p col to 0.0
763 static INLINE void col_cost_init_single(co_mst_env_t *env, col_cost_t *cost, int col) {
764 assert(! bitset_is_set(env->ignore_regs, col) && "Attempt to use forbidden color.");
765 col_cost_init(env, cost, COL_COST_INFEASIBLE);
772 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
773 * ATTENTION: the queue is empty after calling this function!
775 static INLINE void reject_coloring(struct list_head *nodes) {
776 co_mst_irn_t *n, *temp;
777 DB((dbg, LEVEL_4, "\treject coloring for"));
778 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
779 DB((dbg, LEVEL_4, " %+F", n->irn));
780 assert(n->tmp_col >= 0);
782 list_del_init(&n->list);
784 DB((dbg, LEVEL_4, "\n"));
787 static INLINE void materialize_coloring(struct list_head *nodes) {
788 co_mst_irn_t *n, *temp;
789 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
790 assert(n->tmp_col >= 0);
793 list_del_init(&n->list);
797 static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
800 assert(!node->fixed);
801 assert(node->tmp_col < 0);
802 assert(node->list.next == &node->list && node->list.prev == &node->list);
804 list_add_tail(&node->list, changed);
808 static INLINE int is_loose(co_mst_irn_t *node)
810 return !node->fixed && node->tmp_col < 0;
814 * Determines the costs for each color if it would be assigned to node @p node.
816 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
817 affinity_node_t *an = get_affinity_info(env->co, node->irn);
822 col_cost_init(env, costs, 0.0);
824 /* calculate (negative) costs for affinity neighbours */
826 co_gs_foreach_neighb(an, aff_neigh) {
827 ir_node *m = aff_neigh->irn;
831 /* skip ignore nodes */
832 if (arch_irn_is(env->aenv, m, ignore))
835 neigh = get_co_mst_irn(env, m);
836 c = (double)aff_neigh->costs;
838 /* calculate costs for fixed affinity neighbours */
839 if (!is_loose(neigh)) {
840 int col = get_mst_irn_col(neigh);
841 costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
846 /* calculate (positive) costs for interfering neighbours */
847 for (i = 0; i < node->n_neighs; ++i) {
852 int_neigh = node->int_neighs[i];
854 /* skip ignore nodes */
855 if (arch_irn_is(env->aenv, int_neigh, ignore))
858 neigh = get_co_mst_irn(env, int_neigh);
859 col = get_mst_irn_col(neigh);
860 col_cnt = bitset_popcnt(neigh->adm_colors);
862 if (!is_loose(neigh)) {
863 /* colors of fixed interfering neighbours are infeasible */
864 costs[col].cost = COL_COST_INFEASIBLE;
866 else if (col_cnt < env->k) {
867 /* calculate costs for constrained interfering neighbours */
868 double ratio = 1.0 - ((double)col_cnt / (double)env->k);
870 bitset_foreach_clear(neigh->adm_colors, idx) {
871 /* check only explicitly forbidden colors (skip global forbidden ones) */
872 if (! bitset_is_set(env->ignore_regs, idx)) {
873 costs[col].cost += ratio * NEIGHBOUR_CONSTR_COSTS;
878 DB((dbg, LEVEL_4, "\tneigh %+F, loose: %d, color: %d\n", int_neigh, is_loose(neigh), col));
881 /* set all not admissible colors to COL_COST_INFEASIBLE */
882 bitset_foreach_clear(node->adm_colors, idx)
883 costs[idx].cost = COL_COST_INFEASIBLE;
886 /* need forward declaration due to recursive call */
887 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones);
890 * Tries to change node to a color but @p explude_col.
891 * @return 1 if succeeded, 0 otherwise.
893 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed_ones) {
894 int col = get_mst_irn_col(node);
897 /* neighbours has already a different color -> good, temporary fix it */
898 if (col != exclude_col) {
900 set_temp_color(node, col, changed_ones);
904 /* The node has the color it should not have _and_ has not been visited yet. */
905 if (is_loose(node)) {
906 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
908 /* Get the costs for giving the node a specific color. */
909 determine_color_costs(env, node, costs);
911 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
912 costs[exclude_col].cost = COL_COST_INFEASIBLE;
914 /* sort the colors according costs, cheapest first. */
915 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost);
917 /* Try recoloring the node using the color list. */
918 res = recolor_nodes(env, node, costs, changed_ones);
925 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
926 * ATTENTION: Expect @p costs already sorted by increasing costs.
927 * @return 1 if coloring could be applied, 0 otherwise.
929 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed_ones) {
931 struct list_head local_changed;
933 DBG((dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
934 DBG_COL_COST(env, LEVEL_1, costs);
935 DB((dbg, LEVEL_1, "\n"));
937 for (i = 0; i < env->n_regs; ++i) {
938 int tgt_col = costs[i].col;
942 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
943 if (costs[i].cost == COL_COST_INFEASIBLE) {
947 /* Set the new color of the node and mark the node as temporarily fixed. */
948 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
949 INIT_LIST_HEAD(&local_changed);
950 set_temp_color(node, tgt_col, &local_changed);
951 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
953 /* try to color all interfering neighbours with current color forbidden */
954 for (j = 0; j < node->n_neighs; ++j) {
958 neigh = node->int_neighs[j];
960 /* skip ignore nodes */
961 if (arch_irn_is(env->aenv, neigh, ignore))
964 nn = get_co_mst_irn(env, neigh);
965 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
966 neigh, j, nn->fixed, nn->tmp_col, nn->col));
969 Try to change the color of the neighbor and record all nodes which
970 get changed in the tmp list. Add this list to the "changed" list for
971 that color. If we did not succeed to change the color of the neighbor,
972 we bail out and try the next color.
974 if (get_mst_irn_col(nn) == tgt_col) {
975 /* try to color neighbour with tgt_col forbidden */
976 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed);
984 We managed to assign the target color to all neighbors, so from the perspective
985 of the current node, every thing was ok and we can return safely.
988 co_mst_irn_t *n, *temp;
989 /* append the local_changed ones to global ones */
990 list_splice(&local_changed, changed_ones);
994 /* coloring of neighbours failed, so we try next color */
995 reject_coloring(&local_changed);
1003 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1004 * @return 1 if color @p col could be applied, 0 otherwise
1006 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed_ones) {
1007 int col = get_mst_irn_col(node);
1009 /* if node already has the target color -> good, temporary fix it */
1010 if (col == tgt_col) {
1011 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1013 set_temp_color(node, tgt_col, changed_ones);
1018 Node has not yet a fixed color and target color is admissible
1019 -> try to recolor node and it's affinity neighbours
1021 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1022 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
1025 col_cost_init_single(env, costs, tgt_col);
1027 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1028 res = recolor_nodes(env, node, costs, changed_ones);
1029 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1035 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1036 if (!is_loose(node))
1037 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1039 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1040 dbg_admissible_colors(env, node);
1041 DB((dbg, LEVEL_4, ")\n"));
1050 * Tries to color an affinity chunk (or at least a part of it).
1051 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1053 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1054 aff_chunk_t *best_chunk = NULL;
1055 int best_color = -1;
1057 waitq *tmp_chunks = new_waitq();
1058 waitq *best_starts = NULL;
1062 struct list_head changed_ones;
1064 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1065 DBG_AFF_CHUNK(env, LEVEL_2, c);
1066 DB((dbg, LEVEL_2, "\n"));
1069 /* check which color is the "best" for the given chunk.
1070 * if we found a color which was ok for all nodes, we take it
1071 * and do not look further. (see did_all flag usage below.)
1072 * If we have many colors which fit all nodes it is hard to decide
1073 * which one to take anyway.
1074 * TODO Sebastian: Perhaps we should at all nodes and figure out
1075 * a suitable color using costs as done above (determine_color_costs).
1077 for (col = 0; col < env->n_regs && !did_all; ++col) {
1079 waitq *good_starts = new_waitq();
1080 aff_chunk_t *local_best;
1082 /* skip ignore colors */
1083 if (bitset_is_set(env->ignore_regs, col))
1086 DB((dbg, LEVEL_3, "\ttrying color %d\n", col));
1088 /* suppose we can color all nodes to the same color */
1091 INIT_LIST_HEAD(&changed_ones);
1093 /* try to bring all nodes of given chunk to the current color. */
1094 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1095 ir_node *irn = c->n[idx];
1096 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1099 assert(! node->fixed && "Node must not have a fixed color.");
1100 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1103 The order of the colored nodes is important, so we record the successfully
1104 colored ones in the order they appeared.
1106 good = change_node_color(env, node, col, &changed_ones);
1108 waitq_put(good_starts, node);
1114 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
1117 /* try next color when failed */
1119 reject_coloring(&changed_ones);
1123 /* fragment the chunk according to the coloring */
1124 local_best = fragment_chunk(env, col, c, tmp_chunks);
1126 /* search the best of the good list
1127 and make it the new best if it is better than the current */
1129 aff_chunk_assure_weight(env, local_best);
1131 DB((dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1132 DBG_AFF_CHUNK(env, LEVEL_4, local_best);
1134 if (! best_chunk || best_chunk->weight < local_best->weight) {
1135 best_chunk = local_best;
1138 del_waitq(best_starts);
1139 best_starts = good_starts;
1140 DB((dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1142 DB((dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
1143 del_waitq(good_starts);
1147 del_waitq(good_starts);
1150 reject_coloring(&changed_ones);
1153 /* free all intermediate created chunks except best one */
1154 while (! waitq_empty(tmp_chunks)) {
1155 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1156 if (tmp != best_chunk)
1157 delete_aff_chunk(env, tmp);
1159 del_waitq(tmp_chunks);
1161 /* return if coloring failed */
1164 del_waitq(best_starts);
1168 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1169 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1170 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1172 INIT_LIST_HEAD(&changed_ones);
1173 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1174 ir_node *irn = best_chunk->n[idx];
1175 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1176 co_mst_irn_t *n, *temp;
1179 /* bring the node to the color. */
1180 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
1181 INIT_LIST_HEAD(&changed_ones);
1182 res = change_node_color(env, node, best_color, &changed_ones);
1184 materialize_coloring(&changed_ones);
1189 /* remove the nodes in best chunk from original chunk */
1190 bitset_andnot(c->nodes, best_chunk->nodes);
1191 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1192 ir_node *irn = c->n[idx];
1194 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1195 int last = ARR_LEN(c->n) - 1;
1197 c->n[idx] = c->n[last];
1198 ARR_SHRINKLEN(c->n, last);
1203 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1204 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1205 ir_node *n = c->n[idx];
1206 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1210 /* fragment the remaining chunk */
1211 visited = bitset_irg_malloc(env->co->irg);
1212 bitset_or(visited, best_chunk->nodes);
1213 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1214 ir_node *irn = c->n[idx];
1215 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1216 aff_chunk_t *new_chunk = new_aff_chunk(env);
1217 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1219 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1220 aff_chunk_assure_weight(env, new_chunk);
1221 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1225 /* clear obsolete chunks and free some memory */
1226 delete_aff_chunk(env, best_chunk);
1227 bitset_free(visited);
1229 del_waitq(best_starts);
1233 * Main driver for mst safe coalescing algorithm.
1235 int co_solve_heuristic_mst(copy_opt_t *co) {
1236 unsigned n_regs = co->cls->n_regs;
1237 bitset_t *ignore_regs = bitset_alloca(n_regs);
1240 co_mst_env_t mst_env;
1243 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1245 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1248 mst_env.n_regs = n_regs;
1250 mst_env.chunks = new_pqueue();
1252 mst_env.ignore_regs = ignore_regs;
1253 mst_env.ifg = co->cenv->ifg;
1254 mst_env.aenv = co->aenv;
1255 mst_env.chunkset = pset_new_ptr(512);
1257 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1259 /* build affinity chunks */
1260 build_affinity_chunks(&mst_env);
1262 /* color chunks as long as there are some */
1263 while (! pqueue_empty(mst_env.chunks)) {
1264 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1266 color_aff_chunk(&mst_env, chunk);
1267 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1268 delete_aff_chunk(&mst_env, chunk);
1271 /* apply coloring */
1272 foreach_phase_irn(&mst_env.ph, irn) {
1273 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1274 const arch_register_t *reg;
1276 if (arch_irn_is(mst_env.aenv, irn, ignore))
1279 // assert(mirn->fixed && "Node should have fixed color");
1281 /* skip nodes where color hasn't changed */
1282 if (mirn->init_col == mirn->col)
1285 reg = arch_register_for_index(co->cls, mirn->col);
1286 arch_set_irn_register(co->aenv, irn, reg);
1287 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1290 /* free allocated memory */
1291 del_pqueue(mst_env.chunks);
1292 phase_free(&mst_env.ph);
1293 del_pset(mst_env.chunkset);
1298 void be_init_copyheur4(void) {
1299 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1302 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);