2 * Copyright (C) 1995-2008 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"
58 #include "becopyopt_t.h"
62 #define COL_COST_INFEASIBLE DBL_MAX
63 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
64 #define NEIGHBOUR_CONSTR_COSTS 64.0
69 #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while(0)
70 #define DBG_COL_COST(env, level, cost) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while(0)
72 static firm_dbg_module_t *dbg = NULL;
76 #define DBG_AFF_CHUNK(env, level, chunk)
77 #define DBG_COL_COST(env, level, cost)
82 #define REAL(C) (C ## f)
84 static int last_chunk_id = 0;
85 static int recolor_limit = 4;
86 static real_t dislike_influence = REAL(0.1);
88 typedef struct _col_cost_t {
96 typedef struct _aff_chunk_t {
97 const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
98 bitset_t *nodes; /**< A bitset containing all nodes inside this chunk. */
99 bitset_t *interfere; /**< A bitset containing all interfering neighbours of the nodes in this chunk. */
100 int weight; /**< Weight of this chunk */
101 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
102 unsigned deleted : 1; /**< For debugging: Set if the was deleted. */
103 int id; /**< An id of this chunk. */
105 col_cost_t *color_affinity;
111 typedef struct _aff_edge_t {
112 const ir_node *src; /**< Source node. */
113 const ir_node *tgt; /**< Target node. */
114 double weight; /**< The weight of this edge. */
117 /* main coalescing environment */
118 typedef struct _co_mst_env_t {
119 int n_regs; /**< number of regs in class */
120 int k; /**< number of non-ignore registers in class */
121 bitset_t *ignore_regs; /**< set containing all global ignore registers */
122 ir_phase ph; /**< phase object holding data for nodes */
123 pqueue *chunks; /**< priority queue for chunks */
124 pset *chunkset; /**< set holding all chunks */
125 be_ifg_t *ifg; /**< the interference graph */
126 const arch_env_t *aenv; /**< the arch environment */
127 copy_opt_t *co; /**< the copy opt object */
129 col_cost_t **single_cols;
132 /* stores coalescing related information for a node */
133 typedef struct _co_mst_irn_t {
134 const ir_node *irn; /**< the irn this information belongs to */
135 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
136 bitset_t *adm_colors; /**< set of admissible colors for this irn */
137 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
138 int n_neighs; /**< length of the interfering neighbours array. */
139 int int_aff_neigh; /**< number of interfering affinity neighbours */
140 int col; /**< color currently assigned */
141 int init_col; /**< the initial color */
142 int tmp_col; /**< a temporary assigned color */
143 unsigned fixed : 1; /**< the color is fixed */
144 struct list_head list; /**< Queue for coloring undo. */
145 real_t constr_factor;
148 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
150 typedef int decide_func_t(const co_mst_irn_t *node, int col);
155 * Write a chunk to stderr for debugging.
157 static void dbg_aff_chunk(const co_mst_env_t *env, const aff_chunk_t *c) {
159 if (c->weight_consistent)
160 ir_fprintf(stderr, " $%d ", c->weight);
161 ir_fprintf(stderr, "{");
162 bitset_foreach(c->nodes, idx) {
163 ir_node *n = get_idx_irn(env->co->irg, idx);
164 ir_fprintf(stderr, " %+F,", n);
166 ir_fprintf(stderr, "}");
170 * Dump all admissible colors to stderr.
172 static void dbg_admissible_colors(const co_mst_env_t *env, const co_mst_irn_t *node) {
176 if (bitset_popcnt(node->adm_colors) < 1)
177 fprintf(stderr, "no admissible colors?!?");
179 bitset_foreach(node->adm_colors, idx)
180 fprintf(stderr, " %d", idx);
185 * Dump color-cost pairs to stderr.
187 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
189 for (i = 0; i < env->n_regs; ++i)
190 fprintf(stderr, " (%d, %.4f)", cost[i].col, cost[i].cost);
193 #endif /* DEBUG_libfirm */
195 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
196 return node->tmp_col >= 0 ? node->tmp_col : node->col;
200 * @return 1 if node @p node has color @p col, 0 otherwise.
202 static int decider_has_color(const co_mst_irn_t *node, int col) {
203 return get_mst_irn_col(node) == col;
207 * @return 1 if node @p node has not color @p col, 0 otherwise.
209 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
210 return get_mst_irn_col(node) != col;
214 * Always returns true.
216 static int decider_always_yes(const co_mst_irn_t *node, int col) {
222 /** compares two affinity edges by its weight */
223 static int cmp_aff_edge(const void *a, const void *b) {
224 const aff_edge_t *e1 = a;
225 const aff_edge_t *e2 = b;
227 if (e2->weight == e1->weight) {
228 if (e2->src->node_idx == e1->src->node_idx)
229 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
231 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
233 /* sort in descending order */
234 return QSORT_CMP(e2->weight, e1->weight);
237 /** compares to color-cost pairs */
238 static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b) {
239 const col_cost_t *c1 = a;
240 const col_cost_t *c2 = b;
241 real_t diff = c1->cost - c2->cost;
242 return (diff > 0) - (diff < 0);
245 static int cmp_col_cost_gt(const void *a, const void *b) {
246 const col_cost_t *c1 = a;
247 const col_cost_t *c2 = b;
248 real_t diff = c2->cost - c1->cost;
249 return (diff > 0) - (diff < 0);
253 * Creates a new affinity chunk
255 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
256 aff_chunk_t *c = xmalloc(sizeof(*c));
258 c->weight_consistent = 0;
259 c->n = NEW_ARR_F(const ir_node *, 0);
260 c->nodes = bitset_irg_malloc(env->co->irg);
261 c->interfere = bitset_irg_malloc(env->co->irg);
262 c->color_affinity = xmalloc(env->n_regs * sizeof(c->color_affinity[0]));
264 c->id = last_chunk_id++;
266 pset_insert(env->chunkset, c, c->id);
271 * Frees all memory allocated by an affinity chunk.
273 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
274 pset_remove(env->chunkset, c, c->id);
275 bitset_free(c->nodes);
276 bitset_free(c->interfere);
277 xfree(c->color_affinity);
284 * Adds a node to an affinity chunk
286 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
289 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
292 c->weight_consistent = 0;
294 bitset_set(c->nodes, get_irn_idx(node->irn));
296 ARR_APP1(ir_node *, c->n, node->irn);
298 for (i = node->n_neighs - 1; i >= 0; --i) {
299 ir_node *neigh = node->int_neighs[i];
300 bitset_set(c->interfere, get_irn_idx(neigh));
305 * In case there is no phase information for irn, initialize it.
307 static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) {
308 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
309 co_mst_env_t *env = ph->priv;
312 const arch_register_req_t *req;
313 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
321 res->int_neighs = NULL;
322 res->int_aff_neigh = 0;
323 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
324 res->init_col = res->col;
325 INIT_LIST_HEAD(&res->list);
327 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
329 /* set admissible registers */
330 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
332 /* Exclude colors not assignable to the irn */
333 req = arch_get_register_req(env->aenv, irn, -1);
334 if (arch_register_req_is(req, limited))
335 rbitset_copy_to_bitset(req->limited, res->adm_colors);
337 bitset_set_all(res->adm_colors);
339 /* exclude global ignore registers as well */
340 bitset_andnot(res->adm_colors, env->ignore_regs);
342 /* compute the constraint factor */
343 res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcnt(res->adm_colors)) / env->n_regs;
345 /* set the number of interfering affinity neighbours to -1, they are calculated later */
346 res->int_aff_neigh = -1;
348 /* build list of interfering neighbours */
350 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
351 if (! arch_irn_is(env->aenv, neigh, ignore)) {
352 obstack_ptr_grow(phase_obst(ph), neigh);
356 res->int_neighs = obstack_finish(phase_obst(ph));
363 * Check if affinity chunk @p chunk interferes with node @p irn.
365 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, const ir_node *irn) {
367 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
371 * Check if there are interference edges from c1 to c2.
372 * @param env The global co_mst environment
374 * @param c2 Another chunk
375 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
377 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
382 /* check if there is a node in c2 having an interfering neighbor in c1 */
383 return bitset_intersect(c1->interfere, c2->nodes);
387 * Returns the affinity chunk of @p irn or creates a new
388 * one with @p irn as element if there is none assigned.
390 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) {
391 co_mst_irn_t *node = get_co_mst_irn(env, irn);
396 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
397 * are no interference edges from chunk(src) to chunk(tgt)).
398 * @return 1 if successful, 0 if not possible
400 static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt) {
401 aff_chunk_t *c1 = get_aff_chunk(env, src);
402 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
405 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
407 DBG_AFF_CHUNK(env, LEVEL_4, c1);
409 DB((dbg, LEVEL_4, "{%+F}", src));
411 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
413 DBG_AFF_CHUNK(env, LEVEL_4, c2);
415 DB((dbg, LEVEL_4, "{%+F}", tgt));
417 DB((dbg, LEVEL_4, "\n"));
422 /* no chunk exists */
423 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
426 for (i = mirn->n_neighs - 1; i >= 0; --i) {
427 if (mirn->int_neighs[i] == tgt)
431 /* create one containing both nodes */
432 c1 = new_aff_chunk(env);
433 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
434 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
438 /* c2 already exists */
439 if (! aff_chunk_interferes(env, c2, src)) {
440 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
444 } else if (c2 == NULL) {
445 /* c1 already exists */
446 if (! aff_chunk_interferes(env, c1, tgt)) {
447 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
450 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
453 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
454 aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
456 bitset_or(c1->interfere, c2->interfere);
457 c1->weight_consistent = 0;
459 delete_aff_chunk(env, c2);
462 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
466 DB((dbg, LEVEL_4, " ... absorbed\n"));
471 * Assures that the weight of the given chunk is consistent.
473 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
474 if (! c->weight_consistent) {
478 for (i = 0; i < env->n_regs; ++i) {
479 c->color_affinity[i].col = i;
480 c->color_affinity[i].cost = REAL(0.0);
483 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
484 const ir_node *n = c->n[idx];
485 const affinity_node_t *an = get_affinity_info(env->co, n);
486 co_mst_irn_t *node = get_co_mst_irn(env, n);
489 if (node->constr_factor > REAL(0.0)) {
491 bitset_foreach (node->adm_colors, col)
492 c->color_affinity[col].cost += node->constr_factor;
497 co_gs_foreach_neighb(an, neigh) {
498 const ir_node *m = neigh->irn;
499 const int m_idx = get_irn_idx(m);
501 /* skip ignore nodes */
502 if (arch_irn_is(env->aenv, m, ignore))
505 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
510 for (i = 0; i < env->n_regs; ++i)
511 c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
514 // c->weight = bitset_popcnt(c->nodes);
515 c->weight_consistent = 1;
520 * Count the number of interfering affinity neighbours
522 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
523 const neighb_t *neigh;
524 const ir_node *irn = an->irn;
525 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
528 co_gs_foreach_neighb(an, neigh) {
529 const ir_node *n = neigh->irn;
532 /* skip ignore nodes */
533 if (arch_irn_is(env->aenv, n, ignore))
536 /* check if the affinity neighbour interfere */
537 for (i = 0; i < node->n_neighs; ++i) {
538 if (node->int_neighs[i] == n) {
549 * Build chunks of nodes connected by affinity edges.
550 * We start at the heaviest affinity edge.
551 * The chunks of the two edge-defining nodes will be
552 * merged if there are no interference edges from one
553 * chunk to the other.
555 static void build_affinity_chunks(co_mst_env_t *env) {
556 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
557 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
560 aff_chunk_t *curr_chunk;
562 /* at first we create the affinity edge objects */
563 be_ifg_foreach_node(env->ifg, nodes_it, n) {
564 int n_idx = get_irn_idx(n);
568 /* skip ignore nodes */
569 if (arch_irn_is(env->aenv, n, ignore))
572 n1 = get_co_mst_irn(env, n);
573 an = get_affinity_info(env->co, n);
578 if (n1->int_aff_neigh < 0)
579 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
581 /* build the affinity edges */
582 co_gs_foreach_neighb(an, neigh) {
583 const ir_node *m = neigh->irn;
584 int m_idx = get_irn_idx(m);
586 /* record the edge in only one direction */
591 /* skip ignore nodes */
592 if (arch_irn_is(env->aenv, m, ignore))
598 n2 = get_co_mst_irn(env, m);
599 if (n2->int_aff_neigh < 0) {
600 affinity_node_t *am = get_affinity_info(env->co, m);
601 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
604 * these weights are pure hackery ;-).
605 * It's not chriswue's fault but mine.
607 edge.weight = neigh->costs;
608 ARR_APP1(aff_edge_t, edges, edge);
614 /* now: sort edges and build the affinity chunks */
615 len = ARR_LEN(edges);
616 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
617 for (i = 0; i < len; ++i) {
618 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
620 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
623 /* now insert all chunks into a priority queue */
624 foreach_pset(env->chunkset, curr_chunk) {
625 aff_chunk_assure_weight(env, curr_chunk);
627 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
628 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
629 DBG((dbg, LEVEL_1, "\n"));
631 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
633 foreach_phase_irn(&env->ph, n) {
634 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
636 if (mirn->chunk == NULL) {
637 /* no chunk is allocated so far, do it now */
638 aff_chunk_t *curr_chunk = new_aff_chunk(env);
639 aff_chunk_add_node(curr_chunk, mirn);
641 aff_chunk_assure_weight(env, curr_chunk);
643 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
644 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
645 DBG((dbg, LEVEL_1, "\n"));
647 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
654 static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
656 pqueue *grow = new_pqueue();
657 const ir_node *max_node = NULL;
661 for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
662 const ir_node *irn = chunk->n[i];
663 affinity_node_t *an = get_affinity_info(env->co, irn);
667 if (arch_irn_is(env->aenv, irn, ignore))
671 co_gs_foreach_neighb(an, neigh)
674 if (w > max_weight) {
682 bitset_t *visited = bitset_irg_malloc(env->co->irg);
684 for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
685 bitset_add_irn(visited, chunk->n[i]);
687 pqueue_put(grow, (void *) max_node, max_weight);
688 bitset_remv_irn(visited, max_node);
690 while (!pqueue_empty(grow)) {
691 ir_node *irn = pqueue_get(grow);
692 affinity_node_t *an = get_affinity_info(env->co, irn);
695 if (arch_irn_is(env->aenv, irn, ignore))
698 assert(i <= ARR_LEN(chunk->n));
703 /* build the affinity edges */
704 co_gs_foreach_neighb(an, neigh) {
705 co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
707 if (bitset_contains_irn(visited, node->irn)) {
708 pqueue_put(grow, (void *) neigh->irn, neigh->costs);
709 bitset_remv_irn(visited, node->irn);
715 bitset_free(visited);
720 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
722 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
723 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
725 waitq *nodes = new_waitq();
727 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%d) from %+F, color %d:", chunk->id, node->irn, col));
729 /* init queue and chunk */
730 waitq_put(nodes, node);
731 bitset_set(visited, get_irn_idx(node->irn));
732 aff_chunk_add_node(chunk, node);
733 DB((dbg, LEVEL_1, " %+F", node->irn));
735 /* as long as there are nodes in the queue */
736 while (! waitq_empty(nodes)) {
737 co_mst_irn_t *n = waitq_get(nodes);
738 affinity_node_t *an = get_affinity_info(env->co, n->irn);
740 /* check all affinity neighbors */
743 co_gs_foreach_neighb(an, neigh) {
744 const ir_node *m = neigh->irn;
745 int m_idx = get_irn_idx(m);
748 /* skip ignore nodes */
749 if (arch_irn_is(env->aenv, m, ignore))
752 n2 = get_co_mst_irn(env, m);
754 if (! bitset_is_set(visited, m_idx) &&
757 ! aff_chunk_interferes(env, chunk, m) &&
758 bitset_is_set(orig_chunk->nodes, m_idx))
761 following conditions are met:
762 - neighbour is not visited
763 - neighbour likes the color
764 - neighbour has not yet a fixed color
765 - the new chunk doesn't interfere with the neighbour
766 - neighbour belongs or belonged once to the original chunk
768 bitset_set(visited, m_idx);
769 aff_chunk_add_node(chunk, n2);
770 DB((dbg, LEVEL_1, " %+F", n2->irn));
771 /* enqueue for further search */
772 waitq_put(nodes, n2);
778 DB((dbg, LEVEL_1, "\n"));
784 * Fragment the given chunk into chunks having given color and not having given color.
786 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
787 bitset_t *visited = bitset_irg_malloc(env->co->irg);
789 aff_chunk_t *best = NULL;
791 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
794 aff_chunk_t *tmp_chunk;
795 decide_func_t *decider;
799 if (bitset_is_set(visited, get_irn_idx(irn)))
802 node = get_co_mst_irn(env, irn);
804 if (get_mst_irn_col(node) == col) {
805 decider = decider_has_color;
807 DBG((dbg, LEVEL_4, "\tcolor %d wanted", col));
810 decider = decider_hasnot_color;
812 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", col));
815 /* create a new chunk starting at current node */
816 tmp_chunk = new_aff_chunk(env);
817 waitq_put(tmp, tmp_chunk);
818 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
819 assert(bitset_popcnt(tmp_chunk->nodes) > 0 && "No nodes added to chunk");
821 /* remember the local best */
822 aff_chunk_assure_weight(env, tmp_chunk);
823 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
827 assert(best && "No chunk found?");
828 bitset_free(visited);
833 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
834 * ATTENTION: the queue is empty after calling this function!
836 static INLINE void reject_coloring(struct list_head *nodes) {
837 co_mst_irn_t *n, *temp;
838 DB((dbg, LEVEL_4, "\treject coloring for"));
839 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
840 DB((dbg, LEVEL_4, " %+F", n->irn));
841 assert(n->tmp_col >= 0);
843 list_del_init(&n->list);
845 DB((dbg, LEVEL_4, "\n"));
848 static INLINE void materialize_coloring(struct list_head *nodes) {
849 co_mst_irn_t *n, *temp;
850 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
851 assert(n->tmp_col >= 0);
854 list_del_init(&n->list);
858 static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
861 assert(!node->fixed);
862 assert(node->tmp_col < 0);
863 assert(node->list.next == &node->list && node->list.prev == &node->list);
864 assert(bitset_is_set(node->adm_colors, col));
866 list_add_tail(&node->list, changed);
870 static INLINE int is_loose(co_mst_irn_t *node)
872 return !node->fixed && node->tmp_col < 0;
876 * Determines the costs for each color if it would be assigned to node @p node.
878 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
879 int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols));
884 for (i = 0; i < env->n_regs; ++i) {
887 costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
890 for (i = 0; i < node->n_neighs; ++i) {
891 co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]);
892 int col = get_mst_irn_col(n);
897 costs[col].cost = REAL(0.0);
901 coeff = REAL(1.0) / n_loose;
902 for (i = 0; i < env->n_regs; ++i)
903 costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
907 /* need forward declaration due to recursive call */
908 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, int *max_depth, int *trip);
911 * Tries to change node to a color but @p explude_col.
912 * @return 1 if succeeded, 0 otherwise.
914 static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int exclude_col, struct list_head *changed, int depth, int *max_depth, int *trip) {
915 int col = get_mst_irn_col(node);
918 /* neighbours has already a different color -> good, temporary fix it */
919 if (col != exclude_col) {
921 set_temp_color(node, col, changed);
925 /* The node has the color it should not have _and_ has not been visited yet. */
926 if (is_loose(node)) {
927 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
929 /* Get the costs for giving the node a specific color. */
930 determine_color_costs(env, node, costs);
932 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
933 costs[exclude_col].cost = REAL(0.0);
935 /* sort the colors according costs, cheapest first. */
936 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt);
938 /* Try recoloring the node using the color list. */
939 res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip);
946 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
947 * ATTENTION: Expect @p costs already sorted by increasing costs.
948 * @return 1 if coloring could be applied, 0 otherwise.
950 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, struct list_head *changed, int depth, int *max_depth, int *trip) {
952 struct list_head local_changed;
955 if (depth > *max_depth)
958 if (depth >= recolor_limit)
961 DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
962 DBG_COL_COST(env, LEVEL_4, costs);
963 DB((dbg, LEVEL_4, "\n"));
965 for (i = 0; i < env->n_regs; ++i) {
966 int tgt_col = costs[i].col;
970 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
971 if (costs[i].cost == REAL(0.0))
974 /* Set the new color of the node and mark the node as temporarily fixed. */
975 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
976 INIT_LIST_HEAD(&local_changed);
977 set_temp_color(node, tgt_col, &local_changed);
978 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
980 /* try to color all interfering neighbours with current color forbidden */
981 for (j = 0; j < node->n_neighs; ++j) {
985 neigh = node->int_neighs[j];
987 /* skip ignore nodes */
988 if (arch_irn_is(env->aenv, neigh, ignore))
991 nn = get_co_mst_irn(env, neigh);
992 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
993 neigh, j, nn->fixed, nn->tmp_col, nn->col));
996 Try to change the color of the neighbor and record all nodes which
997 get changed in the tmp list. Add this list to the "changed" list for
998 that color. If we did not succeed to change the color of the neighbor,
999 we bail out and try the next color.
1001 if (get_mst_irn_col(nn) == tgt_col) {
1002 /* try to color neighbour with tgt_col forbidden */
1003 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip);
1011 We managed to assign the target color to all neighbors, so from the perspective
1012 of the current node, every thing was ok and we can return safely.
1015 /* append the local_changed ones to global ones */
1016 list_splice(&local_changed, changed);
1020 /* coloring of neighbours failed, so we try next color */
1021 reject_coloring(&local_changed);
1029 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1030 * @return 1 if color @p col could be applied, 0 otherwise
1032 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed) {
1033 int col = get_mst_irn_col(node);
1035 /* if node already has the target color -> good, temporary fix it */
1036 if (col == tgt_col) {
1037 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1039 set_temp_color(node, tgt_col, changed);
1044 Node has not yet a fixed color and target color is admissible
1045 -> try to recolor node and it's affinity neighbours
1047 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1048 col_cost_t *costs = env->single_cols[tgt_col];
1049 int res, max_depth, trip;
1054 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1055 res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip);
1056 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1057 stat_ev_int("heur4_recolor_depth_max", max_depth);
1058 stat_ev_int("heur4_recolor_trip", trip);
1064 #ifdef DEBUG_libfirm
1065 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1066 if (!is_loose(node))
1067 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1069 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1070 dbg_admissible_colors(env, node);
1071 DB((dbg, LEVEL_4, ")\n"));
1080 * Tries to color an affinity chunk (or at least a part of it).
1081 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1083 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1084 aff_chunk_t *best_chunk = NULL;
1085 int n_nodes = ARR_LEN(c->n);
1086 int best_color = -1;
1087 int n_int_chunks = 0;
1088 waitq *tmp_chunks = new_waitq();
1089 waitq *best_starts = NULL;
1090 col_cost_t *order = alloca(env->n_regs * sizeof(order[0]));
1093 struct list_head changed;
1096 DB((dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
1097 DBG_AFF_CHUNK(env, LEVEL_2, c);
1098 DB((dbg, LEVEL_2, "\n"));
1100 stat_ev_ctx_push_fmt("heur4_color_chunk", "%d", c->id);
1102 ++env->chunk_visited;
1104 /* compute color preference */
1105 memset(order, 0, env->n_regs * sizeof(order[0]));
1107 bitset_foreach (c->interfere, pos) {
1108 ir_node *n = get_idx_irn(env->co->irg, pos);
1109 co_mst_irn_t *node = get_co_mst_irn(env, n);
1110 aff_chunk_t *chunk = node->chunk;
1112 if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
1113 assert(!chunk->deleted);
1114 chunk->visited = env->chunk_visited;
1117 aff_chunk_assure_weight(env, chunk);
1118 for (i = 0; i < env->n_regs; ++i)
1119 order[i].cost += chunk->color_affinity[i].cost;
1123 for (i = 0; i < env->n_regs; ++i) {
1124 real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
1126 order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
1129 qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
1131 DBG_COL_COST(env, LEVEL_2, order);
1132 DB((dbg, LEVEL_2, "\n"));
1134 /* check which color is the "best" for the given chunk.
1135 * if we found a color which was ok for all nodes, we take it
1136 * and do not look further. (see did_all flag usage below.)
1137 * If we have many colors which fit all nodes it is hard to decide
1138 * which one to take anyway.
1139 * TODO Sebastian: Perhaps we should at all nodes and figure out
1140 * a suitable color using costs as done above (determine_color_costs).
1142 for (i = 0; i < env->k; ++i) {
1143 int col = order[i].col;
1144 waitq *good_starts = new_waitq();
1145 aff_chunk_t *local_best;
1148 /* skip ignore colors */
1149 if (bitset_is_set(env->ignore_regs, col))
1152 DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
1156 /* try to bring all nodes of given chunk to the current color. */
1157 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1158 const ir_node *irn = c->n[idx];
1159 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1162 assert(! node->fixed && "Node must not have a fixed color.");
1163 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1166 The order of the colored nodes is important, so we record the successfully
1167 colored ones in the order they appeared.
1169 INIT_LIST_HEAD(&changed);
1171 good = change_node_color(env, node, col, &changed);
1172 stat_ev_tim_pop("heur4_recolor");
1174 waitq_put(good_starts, node);
1175 materialize_coloring(&changed);
1180 reject_coloring(&changed);
1182 n_succeeded += good;
1183 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
1186 /* unfix all nodes */
1187 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1188 co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
1192 /* try next color when failed */
1193 if (n_succeeded == 0)
1196 /* fragment the chunk according to the coloring */
1197 local_best = fragment_chunk(env, col, c, tmp_chunks);
1199 /* search the best of the good list
1200 and make it the new best if it is better than the current */
1202 aff_chunk_assure_weight(env, local_best);
1204 DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
1205 DBG_AFF_CHUNK(env, LEVEL_3, local_best);
1207 if (! best_chunk || best_chunk->weight < local_best->weight) {
1208 best_chunk = local_best;
1211 del_waitq(best_starts);
1212 best_starts = good_starts;
1213 DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
1215 DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
1216 del_waitq(good_starts);
1220 del_waitq(good_starts);
1223 /* if all nodes were recolored, bail out */
1224 if (n_succeeded == n_nodes)
1228 stat_ev_int("heur4_colors_tried", i);
1230 /* free all intermediate created chunks except best one */
1231 while (! waitq_empty(tmp_chunks)) {
1232 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1233 if (tmp != best_chunk)
1234 delete_aff_chunk(env, tmp);
1236 del_waitq(tmp_chunks);
1238 /* return if coloring failed */
1241 del_waitq(best_starts);
1245 DB((dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
1246 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1247 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1249 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1250 const ir_node *irn = best_chunk->n[idx];
1251 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1254 /* bring the node to the color. */
1255 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%d\n", best_color, node->irn, best_chunk->id));
1256 INIT_LIST_HEAD(&changed);
1258 res = change_node_color(env, node, best_color, &changed);
1259 stat_ev_tim_pop("heur4_recolor");
1261 materialize_coloring(&changed);
1264 assert(list_empty(&changed));
1267 /* remove the nodes in best chunk from original chunk */
1268 bitset_andnot(c->nodes, best_chunk->nodes);
1269 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1270 const ir_node *irn = c->n[idx];
1272 if (bitset_is_set(best_chunk->nodes, get_irn_idx(irn))) {
1273 int last = ARR_LEN(c->n) - 1;
1275 c->n[idx] = c->n[last];
1276 ARR_SHRINKLEN(c->n, last);
1281 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1282 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1283 const ir_node *n = c->n[idx];
1284 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1288 /* fragment the remaining chunk */
1289 visited = bitset_irg_malloc(env->co->irg);
1290 bitset_or(visited, best_chunk->nodes);
1291 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1292 const ir_node *irn = c->n[idx];
1293 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1294 aff_chunk_t *new_chunk = new_aff_chunk(env);
1295 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1297 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1298 aff_chunk_assure_weight(env, new_chunk);
1299 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1303 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1304 const ir_node *n = best_chunk->n[idx];
1305 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1309 /* clear obsolete chunks and free some memory */
1310 delete_aff_chunk(env, best_chunk);
1311 bitset_free(visited);
1313 del_waitq(best_starts);
1315 stat_ev_ctx_pop("heur4_color_chunk");
1319 * Main driver for mst safe coalescing algorithm.
1321 int co_solve_heuristic_mst(copy_opt_t *co) {
1322 unsigned n_regs = co->cls->n_regs;
1323 bitset_t *ignore_regs = bitset_alloca(n_regs);
1326 co_mst_env_t mst_env;
1331 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1333 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1336 mst_env.n_regs = n_regs;
1338 mst_env.chunks = new_pqueue();
1340 mst_env.ignore_regs = ignore_regs;
1341 mst_env.ifg = co->cenv->ifg;
1342 mst_env.aenv = co->aenv;
1343 mst_env.chunkset = pset_new_ptr(512);
1344 mst_env.chunk_visited = 0;
1345 mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
1347 for (i = 0; i < n_regs; ++i) {
1348 col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
1350 mst_env.single_cols[i] = vec;
1351 for (j = 0; j < n_regs; ++j) {
1353 vec[j].cost = REAL(0.0);
1357 vec[0].cost = REAL(1.0);
1360 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1362 /* build affinity chunks */
1364 build_affinity_chunks(&mst_env);
1365 stat_ev_tim_pop("heur4_initial_chunk");
1367 /* color chunks as long as there are some */
1368 while (! pqueue_empty(mst_env.chunks)) {
1369 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1371 color_aff_chunk(&mst_env, chunk);
1372 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
1373 delete_aff_chunk(&mst_env, chunk);
1376 /* apply coloring */
1377 foreach_phase_irn(&mst_env.ph, irn) {
1378 co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
1379 const arch_register_t *reg;
1381 if (arch_irn_is(mst_env.aenv, irn, ignore))
1384 // assert(mirn->fixed && "Node should have fixed color");
1386 /* skip nodes where color hasn't changed */
1387 if (mirn->init_col == mirn->col)
1390 reg = arch_register_for_index(co->cls, mirn->col);
1391 arch_set_irn_register(co->aenv, irn, reg);
1392 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1395 /* free allocated memory */
1396 del_pqueue(mst_env.chunks);
1397 phase_free(&mst_env.ph);
1398 del_pset(mst_env.chunkset);
1400 stat_ev_tim_pop("heur4_total");
1405 static const lc_opt_table_entry_t options[] = {
1406 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1407 LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence),
1412 void be_init_copyheur4(void) {
1413 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1414 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1415 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1416 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1417 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1419 lc_opt_add_table(heur4_grp, options);
1420 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1424 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);