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 = 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 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 *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 *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_get(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", col));
868 decider = decider_hasnot_color;
870 DBG((dbg, LEVEL_4, "\tcolor %d forbidden", 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 if (depth >= recolor_limit)
1019 DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
1020 DBG_COL_COST(env, LEVEL_4, costs);
1021 DB((dbg, LEVEL_4, "\n"));
1023 for (i = 0; i < env->n_regs; ++i) {
1024 int tgt_col = costs[i].col;
1028 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
1029 if (costs[i].cost == REAL(0.0))
1032 /* Set the new color of the node and mark the node as temporarily fixed. */
1033 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
1034 INIT_LIST_HEAD(&local_changed);
1035 set_temp_color(node, tgt_col, &local_changed);
1036 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
1038 /* try to color all interfering neighbours with current color forbidden */
1039 for (j = 0; j < node->n_neighs; ++j) {
1043 neigh = node->int_neighs[j];
1045 /* skip ignore nodes */
1046 if (arch_irn_is(env->aenv, neigh, ignore))
1049 nn = get_co_mst_irn(env, neigh);
1050 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
1051 neigh, j, nn->fixed, nn->tmp_col, nn->col));
1054 Try to change the color of the neighbor and record all nodes which
1055 get changed in the tmp list. Add this list to the "changed" list for
1056 that color. If we did not succeed to change the color of the neighbor,
1057 we bail out and try the next color.
1059 if (get_mst_irn_col(nn) == tgt_col) {
1060 /* try to color neighbour with tgt_col forbidden */
1061 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip);
1069 We managed to assign the target color to all neighbors, so from the perspective
1070 of the current node, every thing was ok and we can return safely.
1073 /* append the local_changed ones to global ones */
1074 list_splice(&local_changed, changed);
1078 /* coloring of neighbours failed, so we try next color */
1079 reject_coloring(&local_changed);
1087 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1088 * @return 1 if color @p col could be applied, 0 otherwise
1090 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed) {
1091 int col = get_mst_irn_col(node);
1093 /* if node already has the target color -> good, temporary fix it */
1094 if (col == tgt_col) {
1095 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1097 set_temp_color(node, tgt_col, changed);
1102 Node has not yet a fixed color and target color is admissible
1103 -> try to recolor node and it's affinity neighbours
1105 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1106 col_cost_t *costs = env->single_cols[tgt_col];
1107 int res, max_depth, trip;
1112 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1113 res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip);
1114 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1115 stat_ev_int("heur4_recolor_depth_max", max_depth);
1116 stat_ev_int("heur4_recolor_trip", trip);
1122 #ifdef DEBUG_libfirm
1123 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1124 if (!is_loose(node))
1125 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1127 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1128 dbg_admissible_colors(env, node);
1129 DB((dbg, LEVEL_4, ")\n"));
1138 * Tries to color an affinity chunk (or at least a part of it).
1139 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1141 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
1142 aff_chunk_t *best_chunk = NULL;
1143 int n_nodes = ARR_LEN(c->n);
1144 int best_color = -1;
1145 int n_int_chunks = 0;
1146 waitq *tmp_chunks = new_waitq();
1147 waitq *best_starts = NULL;
1148 col_cost_t *order = alloca(env->n_regs * sizeof(order[0]));
1150 int idx, len, i, nidx, pos;
1151 struct list_head changed;
1153 DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
1154 DBG_AFF_CHUNK(env, LEVEL_2, c);
1155 DB((dbg, LEVEL_2, "\n"));
1157 stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
1159 ++env->chunk_visited;
1161 /* compute color preference */
1162 memset(order, 0, env->n_regs * sizeof(order[0]));
1164 for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
1165 const ir_node *n = c->interfere[pos];
1166 co_mst_irn_t *node = get_co_mst_irn(env, n);
1167 aff_chunk_t *chunk = node->chunk;
1169 if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
1170 assert(!chunk->deleted);
1171 chunk->visited = env->chunk_visited;
1174 aff_chunk_assure_weight(env, chunk);
1175 for (i = 0; i < env->n_regs; ++i)
1176 order[i].cost += chunk->color_affinity[i].cost;
1180 for (i = 0; i < env->n_regs; ++i) {
1181 real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
1183 order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
1186 qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
1188 DBG_COL_COST(env, LEVEL_2, order);
1189 DB((dbg, LEVEL_2, "\n"));
1191 /* check which color is the "best" for the given chunk.
1192 * if we found a color which was ok for all nodes, we take it
1193 * and do not look further. (see did_all flag usage below.)
1194 * If we have many colors which fit all nodes it is hard to decide
1195 * which one to take anyway.
1196 * TODO Sebastian: Perhaps we should at all nodes and figure out
1197 * a suitable color using costs as done above (determine_color_costs).
1199 for (i = 0; i < env->k; ++i) {
1200 int col = order[i].col;
1201 waitq *good_starts = new_waitq();
1202 aff_chunk_t *local_best;
1205 /* skip ignore colors */
1206 if (bitset_is_set(env->ignore_regs, col))
1209 DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
1213 /* try to bring all nodes of given chunk to the current color. */
1214 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1215 const ir_node *irn = c->n[idx];
1216 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1219 assert(! node->fixed && "Node must not have a fixed color.");
1220 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1223 The order of the colored nodes is important, so we record the successfully
1224 colored ones in the order they appeared.
1226 INIT_LIST_HEAD(&changed);
1228 good = change_node_color(env, node, col, &changed);
1229 stat_ev_tim_pop("heur4_recolor");
1231 waitq_put(good_starts, node);
1232 materialize_coloring(&changed);
1237 reject_coloring(&changed);
1239 n_succeeded += good;
1240 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
1243 /* unfix all nodes */
1244 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1245 co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
1249 /* try next color when failed */
1250 if (n_succeeded == 0)
1253 /* fragment the chunk according to the coloring */
1254 local_best = fragment_chunk(env, col, c, tmp_chunks);
1256 /* search the best of the good list
1257 and make it the new best if it is better than the current */
1259 aff_chunk_assure_weight(env, local_best);
1261 DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
1262 DBG_AFF_CHUNK(env, LEVEL_3, local_best);
1264 if (! best_chunk || best_chunk->weight < local_best->weight) {
1265 best_chunk = local_best;
1268 del_waitq(best_starts);
1269 best_starts = good_starts;
1270 DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
1272 DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
1273 del_waitq(good_starts);
1277 del_waitq(good_starts);
1280 /* if all nodes were recolored, bail out */
1281 if (n_succeeded == n_nodes)
1285 stat_ev_int("heur4_colors_tried", i);
1287 /* free all intermediate created chunks except best one */
1288 while (! waitq_empty(tmp_chunks)) {
1289 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1290 if (tmp != best_chunk)
1291 delete_aff_chunk(env, tmp);
1293 del_waitq(tmp_chunks);
1295 /* return if coloring failed */
1298 del_waitq(best_starts);
1302 DB((dbg, LEVEL_2, "\tbest chunk #%u ", best_chunk->id));
1303 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1304 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1306 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1307 const ir_node *irn = best_chunk->n[idx];
1308 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1311 /* bring the node to the color. */
1312 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id));
1313 INIT_LIST_HEAD(&changed);
1315 res = change_node_color(env, node, best_color, &changed);
1316 stat_ev_tim_pop("heur4_recolor");
1318 materialize_coloring(&changed);
1321 assert(list_empty(&changed));
1324 /* remove the nodes in best chunk from original chunk */
1325 len = ARR_LEN(best_chunk->n);
1326 for (idx = 0; idx < len; ++idx) {
1327 const ir_node *irn = best_chunk->n[idx];
1328 int pos = nodes_bsearch(c->n, irn);
1333 len = ARR_LEN(c->n);
1334 for (idx = nidx = 0; idx < len; ++idx) {
1335 const ir_node *irn = c->n[idx];
1341 ARR_SHRINKLEN(c->n, nidx);
1344 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1345 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1346 const ir_node *n = c->n[idx];
1347 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1351 /* fragment the remaining chunk */
1352 visited = bitset_irg_malloc(env->co->irg);
1353 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
1354 bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
1356 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1357 const ir_node *irn = c->n[idx];
1358 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1359 aff_chunk_t *new_chunk = new_aff_chunk(env);
1360 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1362 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1363 aff_chunk_assure_weight(env, new_chunk);
1364 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1368 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1369 const ir_node *n = best_chunk->n[idx];
1370 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1374 /* clear obsolete chunks and free some memory */
1375 delete_aff_chunk(env, best_chunk);
1376 bitset_free(visited);
1378 del_waitq(best_starts);
1380 stat_ev_ctx_pop("heur4_color_chunk");
1384 * Main driver for mst safe coalescing algorithm.
1386 int co_solve_heuristic_mst(copy_opt_t *co) {
1387 unsigned n_regs = co->cls->n_regs;
1388 bitset_t *ignore_regs = bitset_alloca(n_regs);
1391 co_mst_env_t mst_env;
1398 phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
1400 k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
1403 mst_env.n_regs = n_regs;
1405 mst_env.chunks = new_pqueue();
1407 mst_env.ignore_regs = ignore_regs;
1408 mst_env.ifg = co->cenv->ifg;
1409 mst_env.aenv = co->aenv;
1410 mst_env.chunkset = pset_new_ptr(512);
1411 mst_env.chunk_visited = 0;
1412 mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
1414 for (i = 0; i < n_regs; ++i) {
1415 col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
1417 mst_env.single_cols[i] = vec;
1418 for (j = 0; j < n_regs; ++j) {
1420 vec[j].cost = REAL(0.0);
1424 vec[0].cost = REAL(1.0);
1427 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1429 /* build affinity chunks */
1431 build_affinity_chunks(&mst_env);
1432 stat_ev_tim_pop("heur4_initial_chunk");
1434 /* color chunks as long as there are some */
1435 while (! pqueue_empty(mst_env.chunks)) {
1436 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
1438 color_aff_chunk(&mst_env, chunk);
1439 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id));
1440 delete_aff_chunk(&mst_env, chunk);
1443 /* apply coloring */
1444 foreach_phase_irn(&mst_env.ph, irn) {
1446 const arch_register_t *reg;
1448 if (arch_irn_is(mst_env.aenv, irn, ignore))
1451 mirn = get_co_mst_irn(&mst_env, irn);
1452 // assert(mirn->fixed && "Node should have fixed color");
1454 /* skip nodes where color hasn't changed */
1455 if (mirn->init_col == mirn->col)
1458 reg = arch_register_for_index(co->cls, mirn->col);
1459 arch_set_irn_register(co->aenv, irn, reg);
1460 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1463 /* free allocated memory */
1464 del_pqueue(mst_env.chunks);
1465 phase_free(&mst_env.ph);
1466 del_pset(mst_env.chunkset);
1468 stat_ev_tim_pop("heur4_total");
1473 static const lc_opt_table_entry_t options[] = {
1474 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1475 LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence),
1480 void be_init_copyheur4(void) {
1481 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1482 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1483 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1484 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1485 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1487 lc_opt_add_table(heur4_grp, options);
1488 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");
1492 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);