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[1];
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);
186 * Dump color-cost pairs to stderr.
188 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost) {
190 for (i = 0; i < env->n_regs; ++i)
191 fprintf(stderr, " (%d, %.4f)", cost[i].col, cost[i].cost);
194 #endif /* DEBUG_libfirm */
196 static INLINE int get_mst_irn_col(const co_mst_irn_t *node) {
197 return node->tmp_col >= 0 ? node->tmp_col : node->col;
201 * @return 1 if node @p node has color @p col, 0 otherwise.
203 static int decider_has_color(const co_mst_irn_t *node, int col) {
204 return get_mst_irn_col(node) == col;
208 * @return 1 if node @p node has not color @p col, 0 otherwise.
210 static int decider_hasnot_color(const co_mst_irn_t *node, int col) {
211 return get_mst_irn_col(node) != col;
215 * Always returns true.
217 static int decider_always_yes(const co_mst_irn_t *node, int col) {
223 /** compares two affinity edges by its weight */
224 static int cmp_aff_edge(const void *a, const void *b) {
225 const aff_edge_t *e1 = a;
226 const aff_edge_t *e2 = b;
228 if (e2->weight == e1->weight) {
229 if (e2->src->node_idx == e1->src->node_idx)
230 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
232 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
234 /* sort in descending order */
235 return QSORT_CMP(e2->weight, e1->weight);
238 /** compares to color-cost pairs */
239 static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b) {
240 const col_cost_t *c1 = a;
241 const col_cost_t *c2 = b;
242 real_t diff = c1->cost - c2->cost;
243 return (diff > 0) - (diff < 0);
246 static int cmp_col_cost_gt(const void *a, const void *b) {
247 const col_cost_t *c1 = a;
248 const col_cost_t *c2 = b;
249 real_t diff = c2->cost - c1->cost;
250 return (diff > 0) - (diff < 0);
254 * Creates a new affinity chunk
256 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
257 aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0]));
258 c->n = NEW_ARR_F(const ir_node *, 0);
259 c->nodes = bitset_irg_malloc(env->co->irg);
260 c->interfere = bitset_irg_malloc(env->co->irg);
262 c->weight_consistent = 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);
283 * Adds a node to an affinity chunk
285 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
288 if (bitset_is_set(c->nodes, get_irn_idx(node->irn)))
291 c->weight_consistent = 0;
293 bitset_set(c->nodes, get_irn_idx(node->irn));
295 ARR_APP1(ir_node *, c->n, node->irn);
297 for (i = node->n_neighs - 1; i >= 0; --i) {
298 ir_node *neigh = node->int_neighs[i];
299 bitset_set(c->interfere, get_irn_idx(neigh));
304 * In case there is no phase information for irn, initialize it.
306 static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) {
307 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
308 co_mst_env_t *env = ph->priv;
311 const arch_register_req_t *req;
312 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
320 res->int_neighs = NULL;
321 res->int_aff_neigh = 0;
322 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
323 res->init_col = res->col;
324 INIT_LIST_HEAD(&res->list);
326 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
328 /* set admissible registers */
329 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
331 /* Exclude colors not assignable to the irn */
332 req = arch_get_register_req(env->aenv, irn, -1);
333 if (arch_register_req_is(req, limited))
334 rbitset_copy_to_bitset(req->limited, res->adm_colors);
336 bitset_set_all(res->adm_colors);
338 /* exclude global ignore registers as well */
339 bitset_andnot(res->adm_colors, env->ignore_regs);
341 /* compute the constraint factor */
342 res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcnt(res->adm_colors)) / env->n_regs;
344 /* set the number of interfering affinity neighbours to -1, they are calculated later */
345 res->int_aff_neigh = -1;
347 /* build list of interfering neighbours */
349 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
350 if (! arch_irn_is(env->aenv, neigh, ignore)) {
351 obstack_ptr_grow(phase_obst(ph), neigh);
355 res->int_neighs = obstack_finish(phase_obst(ph));
362 * Check if affinity chunk @p chunk interferes with node @p irn.
364 static INLINE int aff_chunk_interferes(co_mst_env_t *env, const aff_chunk_t *chunk, const ir_node *irn) {
366 return bitset_is_set(chunk->interfere, get_irn_idx(irn));
370 * Check if there are interference edges from c1 to c2.
371 * @param env The global co_mst environment
373 * @param c2 Another chunk
374 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
376 static INLINE int aff_chunks_interfere(co_mst_env_t *env, const aff_chunk_t *c1, const aff_chunk_t *c2) {
381 /* check if there is a node in c2 having an interfering neighbor in c1 */
382 return bitset_intersect(c1->interfere, c2->nodes);
386 * Returns the affinity chunk of @p irn or creates a new
387 * one with @p irn as element if there is none assigned.
389 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) {
390 co_mst_irn_t *node = get_co_mst_irn(env, irn);
395 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
396 * are no interference edges from chunk(src) to chunk(tgt)).
397 * @return 1 if successful, 0 if not possible
399 static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt) {
400 aff_chunk_t *c1 = get_aff_chunk(env, src);
401 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
404 DB((dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1 ? c1->id : -1));
406 DBG_AFF_CHUNK(env, LEVEL_4, c1);
408 DB((dbg, LEVEL_4, "{%+F}", src));
410 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2 ? c2->id : -1));
412 DBG_AFF_CHUNK(env, LEVEL_4, c2);
414 DB((dbg, LEVEL_4, "{%+F}", tgt));
416 DB((dbg, LEVEL_4, "\n"));
421 /* no chunk exists */
422 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
425 for (i = mirn->n_neighs - 1; i >= 0; --i) {
426 if (mirn->int_neighs[i] == tgt)
430 /* create one containing both nodes */
431 c1 = new_aff_chunk(env);
432 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
433 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
437 /* c2 already exists */
438 if (! aff_chunk_interferes(env, c2, src)) {
439 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
443 } else if (c2 == NULL) {
444 /* c1 already exists */
445 if (! aff_chunk_interferes(env, c1, tgt)) {
446 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
449 } else if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
452 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
453 aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
455 bitset_or(c1->interfere, c2->interfere);
456 c1->weight_consistent = 0;
458 delete_aff_chunk(env, c2);
461 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
465 DB((dbg, LEVEL_4, " ... absorbed\n"));
470 * Assures that the weight of the given chunk is consistent.
472 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
473 if (! c->weight_consistent) {
477 for (i = 0; i < env->n_regs; ++i) {
478 c->color_affinity[i].col = i;
479 c->color_affinity[i].cost = REAL(0.0);
482 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
483 const ir_node *n = c->n[idx];
484 const affinity_node_t *an = get_affinity_info(env->co, n);
485 co_mst_irn_t *node = get_co_mst_irn(env, n);
488 if (node->constr_factor > REAL(0.0)) {
490 bitset_foreach (node->adm_colors, col)
491 c->color_affinity[col].cost += node->constr_factor;
496 co_gs_foreach_neighb(an, neigh) {
497 const ir_node *m = neigh->irn;
498 const int m_idx = get_irn_idx(m);
500 /* skip ignore nodes */
501 if (arch_irn_is(env->aenv, m, ignore))
504 w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
509 for (i = 0; i < env->n_regs; ++i)
510 c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
513 // c->weight = bitset_popcnt(c->nodes);
514 c->weight_consistent = 1;
519 * Count the number of interfering affinity neighbours
521 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
522 const neighb_t *neigh;
523 const ir_node *irn = an->irn;
524 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
527 co_gs_foreach_neighb(an, neigh) {
528 const ir_node *n = neigh->irn;
531 /* skip ignore nodes */
532 if (arch_irn_is(env->aenv, n, ignore))
535 /* check if the affinity neighbour interfere */
536 for (i = 0; i < node->n_neighs; ++i) {
537 if (node->int_neighs[i] == n) {
548 * Build chunks of nodes connected by affinity edges.
549 * We start at the heaviest affinity edge.
550 * The chunks of the two edge-defining nodes will be
551 * merged if there are no interference edges from one
552 * chunk to the other.
554 static void build_affinity_chunks(co_mst_env_t *env) {
555 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
556 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
559 aff_chunk_t *curr_chunk;
561 /* at first we create the affinity edge objects */
562 be_ifg_foreach_node(env->ifg, nodes_it, n) {
563 int n_idx = get_irn_idx(n);
567 /* skip ignore nodes */
568 if (arch_irn_is(env->aenv, n, ignore))
571 n1 = get_co_mst_irn(env, n);
572 an = get_affinity_info(env->co, n);
577 if (n1->int_aff_neigh < 0)
578 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
580 /* build the affinity edges */
581 co_gs_foreach_neighb(an, neigh) {
582 const ir_node *m = neigh->irn;
583 int m_idx = get_irn_idx(m);
585 /* record the edge in only one direction */
590 /* skip ignore nodes */
591 if (arch_irn_is(env->aenv, m, ignore))
597 n2 = get_co_mst_irn(env, m);
598 if (n2->int_aff_neigh < 0) {
599 affinity_node_t *am = get_affinity_info(env->co, m);
600 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
603 * these weights are pure hackery ;-).
604 * It's not chriswue's fault but mine.
606 edge.weight = neigh->costs;
607 ARR_APP1(aff_edge_t, edges, edge);
613 /* now: sort edges and build the affinity chunks */
614 len = ARR_LEN(edges);
615 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
616 for (i = 0; i < len; ++i) {
617 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
619 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
622 /* now insert all chunks into a priority queue */
623 foreach_pset(env->chunkset, curr_chunk) {
624 aff_chunk_assure_weight(env, curr_chunk);
626 DBG((dbg, LEVEL_1, "entry #%d", curr_chunk->id));
627 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
628 DBG((dbg, LEVEL_1, "\n"));
630 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) {
1379 const arch_register_t *reg;
1381 if (arch_irn_is(mst_env.aenv, irn, ignore))
1384 mirn = get_co_mst_irn(&mst_env, irn);
1385 // assert(mirn->fixed && "Node should have fixed color");
1387 /* skip nodes where color hasn't changed */
1388 if (mirn->init_col == mirn->col)
1391 reg = arch_register_for_index(co->cls, mirn->col);
1392 arch_set_irn_register(co->aenv, irn, reg);
1393 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1396 /* free allocated memory */
1397 del_pqueue(mst_env.chunks);
1398 phase_free(&mst_env.ph);
1399 del_pset(mst_env.chunkset);
1401 stat_ev_tim_pop("heur4_total");
1406 static const lc_opt_table_entry_t options[] = {
1407 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1408 LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence),
1413 void be_init_copyheur4(void) {
1414 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1415 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1416 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1417 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1418 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1420 lc_opt_add_table(heur4_grp, options);
1421 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1425 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);