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 unsigned last_chunk_id = 0;
85 static int recolor_limit = 7;
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 const ir_node **interfere; /**< An ARR_F containing all inference. */
99 int weight; /**< Weight of this chunk */
100 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
101 unsigned deleted : 1; /**< For debugging: Set if the was deleted. */
102 unsigned id; /**< An id of this chunk. */
104 col_cost_t color_affinity[1];
110 typedef struct _aff_edge_t {
111 const ir_node *src; /**< Source node. */
112 const ir_node *tgt; /**< Target node. */
113 int weight; /**< The weight of this edge. */
116 /* main coalescing environment */
117 typedef struct _co_mst_env_t {
118 int n_regs; /**< number of regs in class */
119 int k; /**< number of non-ignore registers in class */
120 bitset_t *ignore_regs; /**< set containing all global ignore registers */
121 ir_phase ph; /**< phase object holding data for nodes */
122 pqueue_t *chunks; /**< priority queue for chunks */
123 pset *chunkset; /**< set holding all chunks */
124 be_ifg_t *ifg; /**< the interference graph */
125 const arch_env_t *aenv; /**< the arch environment */
126 copy_opt_t *co; /**< the copy opt object */
127 unsigned chunk_visited;
128 col_cost_t **single_cols;
131 /* stores coalescing related information for a node */
132 typedef struct _co_mst_irn_t {
133 const ir_node *irn; /**< the irn this information belongs to */
134 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
135 bitset_t *adm_colors; /**< set of admissible colors for this irn */
136 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
137 int n_neighs; /**< length of the interfering neighbours array. */
138 int int_aff_neigh; /**< number of interfering affinity neighbours */
139 int col; /**< color currently assigned */
140 int init_col; /**< the initial color */
141 int tmp_col; /**< a temporary assigned color */
142 unsigned fixed : 1; /**< the color is fixed */
143 struct list_head list; /**< Queue for coloring undo. */
144 real_t constr_factor;
147 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
149 typedef int decide_func_t(const co_mst_irn_t *node, int col);
154 * Write a chunk to stderr for debugging.
156 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 for (i = 0, l = ARR_LEN(c->n); i < l; ++i) {
163 const ir_node *n = c->n[i];
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->interfere = NEW_ARR_F(const ir_node *, 0);
261 c->weight_consistent = 0;
263 c->id = ++last_chunk_id;
265 pset_insert(env->chunkset, c, c->id);
270 * Frees all memory allocated by an affinity chunk.
272 static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
273 pset_remove(env->chunkset, c, c->id);
274 DEL_ARR_F(c->interfere);
281 * binary search of sorted nodes.
283 * @return the position where n is found in the array arr or ~pos
284 * if the nodes is not here.
286 static INLINE int nodes_bsearch(const ir_node **arr, const ir_node *n) {
287 int hi = ARR_LEN(arr);
291 int md = lo + ((hi - lo) >> 1);
304 /** Check if a node n can be found inside arr. */
305 static int node_contains(const ir_node **arr, const ir_node *n) {
306 int i = nodes_bsearch(arr, n);
311 * Insert a node into the sorted nodes list.
313 * @return 1 if the node was inserted, 0 else
315 static int nodes_insert(const ir_node ***arr, const ir_node *irn) {
316 int idx = nodes_bsearch(*arr, irn);
319 int i, n = ARR_LEN(*arr);
322 ARR_APP1(const ir_node *, *arr, irn);
327 for (i = n - 1; i >= idx; --i)
336 * Adds a node to an affinity chunk
338 static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
341 if (! nodes_insert(&c->n, node->irn))
344 c->weight_consistent = 0;
347 for (i = node->n_neighs - 1; i >= 0; --i) {
348 ir_node *neigh = node->int_neighs[i];
349 nodes_insert(&c->interfere, neigh);
354 * In case there is no phase information for irn, initialize it.
356 static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn, void *old) {
357 co_mst_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
358 co_mst_env_t *env = ph->priv;
361 const arch_register_req_t *req;
362 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
370 res->int_neighs = NULL;
371 res->int_aff_neigh = 0;
372 res->col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
373 res->init_col = res->col;
374 INIT_LIST_HEAD(&res->list);
376 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
378 /* set admissible registers */
379 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
381 /* Exclude colors not assignable to the irn */
382 req = arch_get_register_req(env->aenv, irn, -1);
383 if (arch_register_req_is(req, limited))
384 rbitset_copy_to_bitset(req->limited, res->adm_colors);
386 bitset_set_all(res->adm_colors);
388 /* exclude global ignore registers as well */
389 bitset_andnot(res->adm_colors, env->ignore_regs);
391 /* compute the constraint factor */
392 res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcnt(res->adm_colors)) / env->n_regs;
394 /* set the number of interfering affinity neighbours to -1, they are calculated later */
395 res->int_aff_neigh = -1;
397 /* build list of interfering neighbours */
399 be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh) {
400 if (! arch_irn_is(env->aenv, neigh, ignore)) {
401 obstack_ptr_grow(phase_obst(ph), neigh);
405 res->int_neighs = obstack_finish(phase_obst(ph));
412 * Check if affinity chunk @p chunk interferes with node @p irn.
414 static INLINE int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn) {
415 return node_contains(chunk->interfere, irn);
419 * Check if there are interference edges from c1 to c2.
421 * @param c2 Another chunk
422 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
424 static INLINE int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2) {
430 /* check if there is a node in c2 having an interfering neighbor in c1 */
431 for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) {
432 const ir_node *irn = c2->n[i];
434 if (node_contains(c1->interfere, irn))
441 * Returns the affinity chunk of @p irn or creates a new
442 * one with @p irn as element if there is none assigned.
444 static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn) {
445 co_mst_irn_t *node = get_co_mst_irn(env, irn);
450 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
451 * are no interference edges from chunk(src) to chunk(tgt)).
452 * @return 1 if successful, 0 if not possible
454 static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt) {
455 aff_chunk_t *c1 = get_aff_chunk(env, src);
456 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
459 DB((dbg, LEVEL_4, "Attempt to let c1 (id %u): ", c1 ? c1->id : 0));
461 DBG_AFF_CHUNK(env, LEVEL_4, c1);
463 DB((dbg, LEVEL_4, "{%+F}", src));
465 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %u): ", c2 ? c2->id : 0));
467 DBG_AFF_CHUNK(env, LEVEL_4, c2);
469 DB((dbg, LEVEL_4, "{%+F}", tgt));
471 DB((dbg, LEVEL_4, "\n"));
476 /* no chunk exists */
477 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
480 for (i = mirn->n_neighs - 1; i >= 0; --i) {
481 if (mirn->int_neighs[i] == tgt)
485 /* create one containing both nodes */
486 c1 = new_aff_chunk(env);
487 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
488 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
492 /* c2 already exists */
493 if (! aff_chunk_interferes(c2, src)) {
494 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
498 } else if (c2 == NULL) {
499 /* c1 already exists */
500 if (! aff_chunk_interferes(c1, tgt)) {
501 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
504 } else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) {
507 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
508 aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
510 for (idx = 0, len = ARR_LEN(c2->interfere); idx < len; ++idx) {
511 const ir_node *irn = c2->interfere[idx];
512 nodes_insert(&c1->interfere, irn);
515 c1->weight_consistent = 0;
517 delete_aff_chunk(env, c2);
520 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
524 DB((dbg, LEVEL_4, " ... absorbed\n"));
529 * Assures that the weight of the given chunk is consistent.
531 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
532 if (! c->weight_consistent) {
536 for (i = 0; i < env->n_regs; ++i) {
537 c->color_affinity[i].col = i;
538 c->color_affinity[i].cost = REAL(0.0);
541 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
542 const ir_node *n = c->n[idx];
543 const affinity_node_t *an = get_affinity_info(env->co, n);
544 co_mst_irn_t *node = get_co_mst_irn(env, n);
547 if (node->constr_factor > REAL(0.0)) {
549 bitset_foreach (node->adm_colors, col)
550 c->color_affinity[col].cost += node->constr_factor;
555 co_gs_foreach_neighb(an, neigh) {
556 const ir_node *m = neigh->irn;
558 /* skip ignore nodes */
559 if (arch_irn_is(env->aenv, m, ignore))
562 w += node_contains(c->n, m) ? neigh->costs : 0;
567 for (i = 0; i < env->n_regs; ++i)
568 c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
571 // c->weight = bitset_popcnt(c->nodes);
572 c->weight_consistent = 1;
577 * Count the number of interfering affinity neighbours
579 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an) {
580 const neighb_t *neigh;
581 const ir_node *irn = an->irn;
582 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
585 co_gs_foreach_neighb(an, neigh) {
586 const ir_node *n = neigh->irn;
589 /* skip ignore nodes */
590 if (arch_irn_is(env->aenv, n, ignore))
593 /* check if the affinity neighbour interfere */
594 for (i = 0; i < node->n_neighs; ++i) {
595 if (node->int_neighs[i] == n) {
606 * Build chunks of nodes connected by affinity edges.
607 * We start at the heaviest affinity edge.
608 * The chunks of the two edge-defining nodes will be
609 * merged if there are no interference edges from one
610 * chunk to the other.
612 static void build_affinity_chunks(co_mst_env_t *env) {
613 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
614 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
617 aff_chunk_t *curr_chunk;
619 /* at first we create the affinity edge objects */
620 be_ifg_foreach_node(env->ifg, nodes_it, n) {
621 int n_idx = get_irn_idx(n);
625 /* skip ignore nodes */
626 if (arch_irn_is(env->aenv, n, ignore))
629 n1 = get_co_mst_irn(env, n);
630 an = get_affinity_info(env->co, n);
635 if (n1->int_aff_neigh < 0)
636 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
638 /* build the affinity edges */
639 co_gs_foreach_neighb(an, neigh) {
640 const ir_node *m = neigh->irn;
641 int m_idx = get_irn_idx(m);
643 /* record the edge in only one direction */
648 /* skip ignore nodes */
649 if (arch_irn_is(env->aenv, m, ignore))
655 n2 = get_co_mst_irn(env, m);
656 if (n2->int_aff_neigh < 0) {
657 affinity_node_t *am = get_affinity_info(env->co, m);
658 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
661 * these weights are pure hackery ;-).
662 * It's not chriswue's fault but mine.
664 edge.weight = neigh->costs;
665 ARR_APP1(aff_edge_t, edges, edge);
671 /* now: sort edges and build the affinity chunks */
672 len = ARR_LEN(edges);
673 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
674 for (i = 0; i < len; ++i) {
675 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
677 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
680 /* now insert all chunks into a priority queue */
681 foreach_pset(env->chunkset, curr_chunk) {
682 aff_chunk_assure_weight(env, curr_chunk);
684 DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
685 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
686 DBG((dbg, LEVEL_1, "\n"));
688 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
691 foreach_phase_irn(&env->ph, n) {
692 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
694 if (mirn->chunk == NULL) {
695 /* no chunk is allocated so far, do it now */
696 aff_chunk_t *curr_chunk = new_aff_chunk(env);
697 aff_chunk_add_node(curr_chunk, mirn);
699 aff_chunk_assure_weight(env, curr_chunk);
701 DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
702 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
703 DBG((dbg, LEVEL_1, "\n"));
705 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
712 static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
714 pqueue_t *grow = new_pqueue();
715 const ir_node *max_node = NULL;
719 for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
720 const ir_node *irn = chunk->n[i];
721 affinity_node_t *an = get_affinity_info(env->co, irn);
725 if (arch_irn_is(env->aenv, irn, ignore))
729 co_gs_foreach_neighb(an, neigh)
732 if (w > max_weight) {
740 bitset_t *visited = bitset_irg_malloc(env->co->irg);
742 for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
743 bitset_add_irn(visited, chunk->n[i]);
745 pqueue_put(grow, (void *) max_node, max_weight);
746 bitset_remv_irn(visited, max_node);
748 while (!pqueue_empty(grow)) {
749 ir_node *irn = pqueue_pop_front(grow);
750 affinity_node_t *an = get_affinity_info(env->co, irn);
753 if (arch_irn_is(env->aenv, irn, ignore))
756 assert(i <= ARR_LEN(chunk->n));
761 /* build the affinity edges */
762 co_gs_foreach_neighb(an, neigh) {
763 co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
765 if (bitset_contains_irn(visited, node->irn)) {
766 pqueue_put(grow, (void *) neigh->irn, neigh->costs);
767 bitset_remv_irn(visited, node->irn);
773 bitset_free(visited);
778 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
780 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
781 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
783 waitq *nodes = new_waitq();
785 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%u) from %+F, color %d:", chunk->id, node->irn, col));
787 /* init queue and chunk */
788 waitq_put(nodes, node);
789 bitset_set(visited, get_irn_idx(node->irn));
790 aff_chunk_add_node(chunk, node);
791 DB((dbg, LEVEL_1, " %+F", node->irn));
793 /* as long as there are nodes in the queue */
794 while (! waitq_empty(nodes)) {
795 co_mst_irn_t *n = waitq_get(nodes);
796 affinity_node_t *an = get_affinity_info(env->co, n->irn);
798 /* check all affinity neighbors */
801 co_gs_foreach_neighb(an, neigh) {
802 const ir_node *m = neigh->irn;
803 int m_idx = get_irn_idx(m);
806 /* skip ignore nodes */
807 if (arch_irn_is(env->aenv, m, ignore))
810 n2 = get_co_mst_irn(env, m);
812 if (! bitset_is_set(visited, m_idx) &&
815 ! aff_chunk_interferes(chunk, m) &&
816 node_contains(orig_chunk->n, m))
819 following conditions are met:
820 - neighbour is not visited
821 - neighbour likes the color
822 - neighbour has not yet a fixed color
823 - the new chunk doesn't interfere with the neighbour
824 - neighbour belongs or belonged once to the original chunk
826 bitset_set(visited, m_idx);
827 aff_chunk_add_node(chunk, n2);
828 DB((dbg, LEVEL_1, " %+F", n2->irn));
829 /* enqueue for further search */
830 waitq_put(nodes, n2);
836 DB((dbg, LEVEL_1, "\n"));
842 * Fragment the given chunk into chunks having given color and not having given color.
844 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp) {
845 bitset_t *visited = bitset_irg_malloc(env->co->irg);
847 aff_chunk_t *best = NULL;
849 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
852 aff_chunk_t *tmp_chunk;
853 decide_func_t *decider;
857 if (bitset_is_set(visited, get_irn_idx(irn)))
860 node = get_co_mst_irn(env, irn);
862 if (get_mst_irn_col(node) == col) {
863 decider = decider_has_color;
865 DBG((dbg, LEVEL_4, "\tcolor %d wanted\n", col));
868 decider = decider_hasnot_color;
870 DBG((dbg, LEVEL_4, "\tcolor %d forbidden\n", col));
873 /* create a new chunk starting at current node */
874 tmp_chunk = new_aff_chunk(env);
875 waitq_put(tmp, tmp_chunk);
876 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
877 assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk");
879 /* remember the local best */
880 aff_chunk_assure_weight(env, tmp_chunk);
881 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
885 assert(best && "No chunk found?");
886 bitset_free(visited);
891 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
892 * ATTENTION: the queue is empty after calling this function!
894 static INLINE void reject_coloring(struct list_head *nodes) {
895 co_mst_irn_t *n, *temp;
896 DB((dbg, LEVEL_4, "\treject coloring for"));
897 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
898 DB((dbg, LEVEL_4, " %+F", n->irn));
899 assert(n->tmp_col >= 0);
901 list_del_init(&n->list);
903 DB((dbg, LEVEL_4, "\n"));
906 static INLINE void materialize_coloring(struct list_head *nodes) {
907 co_mst_irn_t *n, *temp;
908 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
909 assert(n->tmp_col >= 0);
912 list_del_init(&n->list);
916 static INLINE void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
919 assert(!node->fixed);
920 assert(node->tmp_col < 0);
921 assert(node->list.next == &node->list && node->list.prev == &node->list);
922 assert(bitset_is_set(node->adm_colors, col));
924 list_add_tail(&node->list, changed);
928 static INLINE int is_loose(co_mst_irn_t *node)
930 return !node->fixed && node->tmp_col < 0;
934 * Determines the costs for each color if it would be assigned to node @p node.
936 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
937 int *neigh_cols = alloca(env->n_regs * sizeof(*neigh_cols));
942 for (i = 0; i < env->n_regs; ++i) {
945 costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
948 for (i = 0; i < node->n_neighs; ++i) {
949 co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]);
950 int col = get_mst_irn_col(n);
955 costs[col].cost = REAL(0.0);
959 coeff = REAL(1.0) / n_loose;
960 for (i = 0; i < env->n_regs; ++i)
961 costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
965 /* need forward declaration due to recursive call */
966 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);
969 * Tries to change node to a color but @p explude_col.
970 * @return 1 if succeeded, 0 otherwise.
972 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) {
973 int col = get_mst_irn_col(node);
976 /* neighbours has already a different color -> good, temporary fix it */
977 if (col != exclude_col) {
979 set_temp_color(node, col, changed);
983 /* The node has the color it should not have _and_ has not been visited yet. */
984 if (is_loose(node)) {
985 col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
987 /* Get the costs for giving the node a specific color. */
988 determine_color_costs(env, node, costs);
990 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
991 costs[exclude_col].cost = REAL(0.0);
993 /* sort the colors according costs, cheapest first. */
994 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt);
996 /* Try recoloring the node using the color list. */
997 res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip);
1004 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
1005 * ATTENTION: Expect @p costs already sorted by increasing costs.
1006 * @return 1 if coloring could be applied, 0 otherwise.
1008 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) {
1010 struct list_head local_changed;
1013 if (depth > *max_depth)
1016 DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
1017 DBG_COL_COST(env, LEVEL_4, costs);
1018 DB((dbg, LEVEL_4, "\n"));
1020 if (depth >= recolor_limit) {
1021 DBG((dbg, LEVEL_4, "\tHit recolor limit\n"));
1025 for (i = 0; i < env->n_regs; ++i) {
1026 int tgt_col = costs[i].col;
1030 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
1031 if (costs[i].cost == REAL(0.0)) {
1032 DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n"));
1036 /* Set the new color of the node and mark the node as temporarily fixed. */
1037 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
1038 INIT_LIST_HEAD(&local_changed);
1039 set_temp_color(node, tgt_col, &local_changed);
1040 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
1042 /* try to color all interfering neighbours with current color forbidden */
1043 for (j = 0; j < node->n_neighs; ++j) {
1047 neigh = node->int_neighs[j];
1049 /* skip ignore nodes */
1050 if (arch_irn_is(env->aenv, neigh, ignore))
1053 nn = get_co_mst_irn(env, neigh);
1054 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
1055 neigh, j, nn->fixed, nn->tmp_col, nn->col));
1058 Try to change the color of the neighbor and record all nodes which
1059 get changed in the tmp list. Add this list to the "changed" list for
1060 that color. If we did not succeed to change the color of the neighbor,
1061 we bail out and try the next color.
1063 if (get_mst_irn_col(nn) == tgt_col) {
1064 /* try to color neighbour with tgt_col forbidden */
1065 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip);
1073 We managed to assign the target color to all neighbors, so from the perspective
1074 of the current node, every thing was ok and we can return safely.
1077 /* append the local_changed ones to global ones */
1078 list_splice(&local_changed, changed);
1082 /* coloring of neighbours failed, so we try next color */
1083 reject_coloring(&local_changed);
1087 DBG((dbg, LEVEL_4, "\tAll colors failed\n"));
1092 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1093 * @return 1 if color @p col could be applied, 0 otherwise
1095 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed) {
1096 int col = get_mst_irn_col(node);
1098 /* if node already has the target color -> good, temporary fix it */
1099 if (col == tgt_col) {
1100 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1102 set_temp_color(node, tgt_col, changed);
1107 Node has not yet a fixed color and target color is admissible
1108 -> try to recolor node and it's affinity neighbours
1110 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1111 col_cost_t *costs = env->single_cols[tgt_col];
1112 int res, max_depth, trip;
1117 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1118 res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip);
1119 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1120 stat_ev_int("heur4_recolor_depth_max", max_depth);
1121 stat_ev_int("heur4_recolor_trip", trip);
1127 #ifdef DEBUG_libfirm
1128 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1129 if (!is_loose(node))
1130 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1132 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1133 dbg_admissible_colors(env, node);
1134 DB((dbg, LEVEL_4, ")\n"));
1143 * Tries to color an affinity chunk (or at least a part of it).
1144 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1146 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1147 aff_chunk_t *best_chunk = NULL;
1148 int n_nodes = ARR_LEN(c->n);
1149 int best_color = -1;
1150 int n_int_chunks = 0;
1151 waitq *tmp_chunks = new_waitq();
1152 waitq *best_starts = NULL;
1153 col_cost_t *order = alloca(env->n_regs * sizeof(order[0]));
1155 int idx, len, i, nidx, pos;
1156 struct list_head changed;
1158 DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
1159 DBG_AFF_CHUNK(env, LEVEL_2, c);
1160 DB((dbg, LEVEL_2, "\n"));
1162 stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
1164 ++env->chunk_visited;
1166 /* compute color preference */
1167 memset(order, 0, env->n_regs * sizeof(order[0]));
1169 for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
1170 const ir_node *n = c->interfere[pos];
1171 co_mst_irn_t *node = get_co_mst_irn(env, n);
1172 aff_chunk_t *chunk = node->chunk;
1174 if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
1175 assert(!chunk->deleted);
1176 chunk->visited = env->chunk_visited;
1179 aff_chunk_assure_weight(env, chunk);
1180 for (i = 0; i < env->n_regs; ++i)
1181 order[i].cost += chunk->color_affinity[i].cost;
1185 for (i = 0; i < env->n_regs; ++i) {
1186 real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
1188 order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
1191 qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
1193 DBG_COL_COST(env, LEVEL_2, order);
1194 DB((dbg, LEVEL_2, "\n"));
1196 /* check which color is the "best" for the given chunk.
1197 * if we found a color which was ok for all nodes, we take it
1198 * and do not look further. (see did_all flag usage below.)
1199 * If we have many colors which fit all nodes it is hard to decide
1200 * which one to take anyway.
1201 * TODO Sebastian: Perhaps we should at all nodes and figure out
1202 * a suitable color using costs as done above (determine_color_costs).
1204 for (i = 0; i < env->k; ++i) {
1205 int col = order[i].col;
1206 waitq *good_starts = new_waitq();
1207 aff_chunk_t *local_best;
1210 /* skip ignore colors */
1211 if (bitset_is_set(env->ignore_regs, col))
1214 DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
1218 /* try to bring all nodes of given chunk to the current color. */
1219 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1220 const ir_node *irn = c->n[idx];
1221 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1224 assert(! node->fixed && "Node must not have a fixed color.");
1225 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1228 The order of the colored nodes is important, so we record the successfully
1229 colored ones in the order they appeared.
1231 INIT_LIST_HEAD(&changed);
1233 good = change_node_color(env, node, col, &changed);
1234 stat_ev_tim_pop("heur4_recolor");
1236 waitq_put(good_starts, node);
1237 materialize_coloring(&changed);
1242 reject_coloring(&changed);
1244 n_succeeded += good;
1245 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
1248 /* unfix all nodes */
1249 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1250 co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
1254 /* try next color when failed */
1255 if (n_succeeded == 0)
1258 /* fragment the chunk according to the coloring */
1259 local_best = fragment_chunk(env, col, c, tmp_chunks);
1261 /* search the best of the good list
1262 and make it the new best if it is better than the current */
1264 aff_chunk_assure_weight(env, local_best);
1266 DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
1267 DBG_AFF_CHUNK(env, LEVEL_3, local_best);
1269 if (! best_chunk || best_chunk->weight < local_best->weight) {
1270 best_chunk = local_best;
1273 del_waitq(best_starts);
1274 best_starts = good_starts;
1275 DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
1277 DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
1278 del_waitq(good_starts);
1282 del_waitq(good_starts);
1285 /* if all nodes were recolored, bail out */
1286 if (n_succeeded == n_nodes)
1290 stat_ev_int("heur4_colors_tried", i);
1292 /* free all intermediate created chunks except best one */
1293 while (! waitq_empty(tmp_chunks)) {
1294 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1295 if (tmp != best_chunk)
1296 delete_aff_chunk(env, tmp);
1298 del_waitq(tmp_chunks);
1300 /* return if coloring failed */
1303 del_waitq(best_starts);
1307 DB((dbg, LEVEL_2, "\tbest chunk #%u ", best_chunk->id));
1308 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1309 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1311 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1312 const ir_node *irn = best_chunk->n[idx];
1313 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1316 /* bring the node to the color. */
1317 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id));
1318 INIT_LIST_HEAD(&changed);
1320 res = change_node_color(env, node, best_color, &changed);
1321 stat_ev_tim_pop("heur4_recolor");
1323 materialize_coloring(&changed);
1326 assert(list_empty(&changed));
1329 /* remove the nodes in best chunk from original chunk */
1330 len = ARR_LEN(best_chunk->n);
1331 for (idx = 0; idx < len; ++idx) {
1332 const ir_node *irn = best_chunk->n[idx];
1333 int pos = nodes_bsearch(c->n, irn);
1338 len = ARR_LEN(c->n);
1339 for (idx = nidx = 0; idx < len; ++idx) {
1340 const ir_node *irn = c->n[idx];
1346 ARR_SHRINKLEN(c->n, nidx);
1349 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1350 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1351 const ir_node *n = c->n[idx];
1352 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1356 /* fragment the remaining chunk */
1357 visited = bitset_irg_malloc(env->co->irg);
1358 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
1359 bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
1361 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1362 const ir_node *irn = c->n[idx];
1363 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1364 aff_chunk_t *new_chunk = new_aff_chunk(env);
1365 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1367 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1368 aff_chunk_assure_weight(env, new_chunk);
1369 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1373 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1374 const ir_node *n = best_chunk->n[idx];
1375 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1379 /* clear obsolete chunks and free some memory */
1380 delete_aff_chunk(env, best_chunk);
1381 bitset_free(visited);
1383 del_waitq(best_starts);
1385 stat_ev_ctx_pop("heur4_color_chunk");
1389 * Main driver for mst safe coalescing algorithm.
1391 int co_solve_heuristic_mst(copy_opt_t *co) {
1392 unsigned n_regs = co->cls->n_regs;
1393 bitset_t *ignore_regs = bitset_alloca(n_regs);
1396 co_mst_env_t mst_env;
1403 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1405 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1408 mst_env.n_regs = n_regs;
1410 mst_env.chunks = new_pqueue();
1412 mst_env.ignore_regs = ignore_regs;
1413 mst_env.ifg = co->cenv->ifg;
1414 mst_env.aenv = co->aenv;
1415 mst_env.chunkset = pset_new_ptr(512);
1416 mst_env.chunk_visited = 0;
1417 mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
1419 for (i = 0; i < n_regs; ++i) {
1420 col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
1422 mst_env.single_cols[i] = vec;
1423 for (j = 0; j < n_regs; ++j) {
1425 vec[j].cost = REAL(0.0);
1429 vec[0].cost = REAL(1.0);
1432 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1434 /* build affinity chunks */
1436 build_affinity_chunks(&mst_env);
1437 stat_ev_tim_pop("heur4_initial_chunk");
1439 /* color chunks as long as there are some */
1440 while (! pqueue_empty(mst_env.chunks)) {
1441 aff_chunk_t *chunk = pqueue_pop_front(mst_env.chunks);
1443 color_aff_chunk(&mst_env, chunk);
1444 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id));
1445 delete_aff_chunk(&mst_env, chunk);
1448 /* apply coloring */
1449 foreach_phase_irn(&mst_env.ph, irn) {
1451 const arch_register_t *reg;
1453 if (arch_irn_is(mst_env.aenv, irn, ignore))
1456 mirn = get_co_mst_irn(&mst_env, irn);
1457 // assert(mirn->fixed && "Node should have fixed color");
1459 /* skip nodes where color hasn't changed */
1460 if (mirn->init_col == mirn->col)
1463 reg = arch_register_for_index(co->cls, mirn->col);
1464 arch_set_irn_register(co->aenv, irn, reg);
1465 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1468 /* free allocated memory */
1469 del_pqueue(mst_env.chunks);
1470 phase_free(&mst_env.ph);
1471 del_pset(mst_env.chunkset);
1473 stat_ev_tim_pop("heur4_total");
1478 static const lc_opt_table_entry_t options[] = {
1479 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1480 LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence),
1485 void be_init_copyheur4(void) {
1486 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1487 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1488 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1489 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1490 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1492 lc_opt_add_table(heur4_grp, options);
1493 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1497 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);