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 #define DISABLE_STATEV
41 #include "raw_bitset.h"
42 #include "irphase_t.h"
57 #include "becopyopt_t.h"
61 #define COL_COST_INFEASIBLE DBL_MAX
62 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
63 #define NEIGHBOUR_CONSTR_COSTS 64.0
68 #define DBG_AFF_CHUNK(env, level, chunk) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_aff_chunk((env), (chunk)); } while (0)
69 #define DBG_COL_COST(env, level, cost) do { if (firm_dbg_get_mask(dbg) & (level)) dbg_col_cost((env), (cost)); } while (0)
71 static firm_dbg_module_t *dbg = NULL;
75 #define DBG_AFF_CHUNK(env, level, chunk)
76 #define DBG_COL_COST(env, level, cost)
81 #define REAL(C) (C ## f)
83 static unsigned last_chunk_id = 0;
84 static int recolor_limit = 7;
85 static real_t dislike_influence = REAL(0.1);
87 typedef struct _col_cost_t {
95 typedef struct _aff_chunk_t {
96 const ir_node **n; /**< An ARR_F containing all nodes of the chunk. */
97 const ir_node **interfere; /**< An ARR_F containing all inference. */
98 int weight; /**< Weight of this chunk */
99 unsigned weight_consistent : 1; /**< Set if the weight is consistent. */
100 unsigned deleted : 1; /**< For debugging: Set if the was deleted. */
101 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 list_head chunklist; /**< list holding all chunks */
124 be_ifg_t *ifg; /**< the interference graph */
125 copy_opt_t *co; /**< the copy opt object */
126 unsigned chunk_visited;
127 col_cost_t **single_cols;
130 /* stores coalescing related information for a node */
131 typedef struct _co_mst_irn_t {
132 const ir_node *irn; /**< the irn this information belongs to */
133 aff_chunk_t *chunk; /**< the chunk this irn belongs to */
134 bitset_t *adm_colors; /**< set of admissible colors for this irn */
135 ir_node **int_neighs; /**< array of all interfering neighbours (cached for speed reasons) */
136 int n_neighs; /**< length of the interfering neighbours array. */
137 int int_aff_neigh; /**< number of interfering affinity neighbours */
138 int col; /**< color currently assigned */
139 int init_col; /**< the initial color */
140 int tmp_col; /**< a temporary assigned color */
141 unsigned fixed : 1; /**< the color is fixed */
142 struct list_head list; /**< Queue for coloring undo. */
143 real_t constr_factor;
146 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
148 typedef int decide_func_t(const co_mst_irn_t *node, int col);
153 * Write a chunk to stderr for debugging.
155 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)
177 if (bitset_popcount(node->adm_colors) < 1)
178 fprintf(stderr, "no admissible colors?!?");
180 bitset_foreach(node->adm_colors, idx) {
181 fprintf(stderr, " %d", idx);
187 * Dump color-cost pairs to stderr.
189 static void dbg_col_cost(const co_mst_env_t *env, const col_cost_t *cost)
192 for (i = 0; i < env->n_regs; ++i)
193 fprintf(stderr, " (%d, %.4f)", cost[i].col, cost[i].cost);
196 #endif /* DEBUG_libfirm */
198 static inline int get_mst_irn_col(const co_mst_irn_t *node)
200 return node->tmp_col >= 0 ? node->tmp_col : node->col;
204 * @return 1 if node @p node has color @p col, 0 otherwise.
206 static int decider_has_color(const co_mst_irn_t *node, int col)
208 return get_mst_irn_col(node) == col;
212 * @return 1 if node @p node has not color @p col, 0 otherwise.
214 static int decider_hasnot_color(const co_mst_irn_t *node, int col)
216 return get_mst_irn_col(node) != col;
220 * Always returns true.
222 static int decider_always_yes(const co_mst_irn_t *node, int col)
229 /** compares two affinity edges by its weight */
230 static int cmp_aff_edge(const void *a, const void *b)
232 const aff_edge_t *e1 = a;
233 const aff_edge_t *e2 = b;
235 if (e2->weight == e1->weight) {
236 if (e2->src->node_idx == e1->src->node_idx)
237 return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
239 return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
241 /* sort in descending order */
242 return QSORT_CMP(e2->weight, e1->weight);
245 /** compares to color-cost pairs */
246 static __attribute__((unused)) int cmp_col_cost_lt(const void *a, const void *b)
248 const col_cost_t *c1 = a;
249 const col_cost_t *c2 = b;
250 real_t diff = c1->cost - c2->cost;
251 return (diff > 0) - (diff < 0);
254 static int cmp_col_cost_gt(const void *a, const void *b)
256 const col_cost_t *c1 = a;
257 const col_cost_t *c2 = b;
258 if (c2->cost == c1->cost)
259 return QSORT_CMP(c1->col, c2->col);
261 real_t diff = c2->cost - c1->cost;
262 return (diff > 0) - (diff < 0);
266 * Creates a new affinity chunk
268 static inline aff_chunk_t *new_aff_chunk(co_mst_env_t *env)
270 aff_chunk_t *c = XMALLOCF(aff_chunk_t, color_affinity, env->n_regs);
271 c->n = NEW_ARR_F(const ir_node *, 0);
272 c->interfere = NEW_ARR_F(const ir_node *, 0);
274 c->weight_consistent = 0;
276 c->id = ++last_chunk_id;
278 list_add(&c->list, &env->chunklist);
283 * Frees all memory allocated by an affinity chunk.
285 static inline void delete_aff_chunk(aff_chunk_t *c)
288 DEL_ARR_F(c->interfere);
295 * binary search of sorted nodes.
297 * @return the position where n is found in the array arr or ~pos
298 * if the nodes is not here.
300 static inline int nodes_bsearch(const ir_node **arr, const ir_node *n)
302 int hi = ARR_LEN(arr);
306 int md = lo + ((hi - lo) >> 1);
319 /** Check if a node n can be found inside arr. */
320 static int node_contains(const ir_node **arr, const ir_node *n)
322 int i = nodes_bsearch(arr, n);
327 * Insert a node into the sorted nodes list.
329 * @return 1 if the node was inserted, 0 else
331 static int nodes_insert(const ir_node ***arr, const ir_node *irn)
333 int idx = nodes_bsearch(*arr, irn);
336 int i, n = ARR_LEN(*arr);
339 ARR_APP1(const ir_node *, *arr, irn);
344 for (i = n - 1; i >= idx; --i)
353 * Adds a node to an affinity chunk
355 static inline void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node)
359 if (! nodes_insert(&c->n, node->irn))
362 c->weight_consistent = 0;
365 for (i = node->n_neighs - 1; i >= 0; --i) {
366 ir_node *neigh = node->int_neighs[i];
367 nodes_insert(&c->interfere, neigh);
372 * In case there is no phase information for irn, initialize it.
374 static void *co_mst_irn_init(ir_phase *ph, const ir_node *irn)
376 co_mst_irn_t *res = phase_alloc(ph, sizeof(res[0]));
377 co_mst_env_t *env = ph->priv;
379 const arch_register_req_t *req;
380 neighbours_iter_t nodes_it;
388 res->int_neighs = NULL;
389 res->int_aff_neigh = 0;
390 res->col = arch_register_get_index(arch_get_irn_register(irn));
391 res->init_col = res->col;
392 INIT_LIST_HEAD(&res->list);
394 DB((dbg, LEVEL_4, "Creating phase info for %+F\n", irn));
396 /* set admissible registers */
397 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
399 /* Exclude colors not assignable to the irn */
400 req = arch_get_register_req_out(irn);
401 if (arch_register_req_is(req, limited))
402 rbitset_copy_to_bitset(req->limited, res->adm_colors);
404 bitset_set_all(res->adm_colors);
406 /* exclude global ignore registers as well */
407 bitset_andnot(res->adm_colors, env->ignore_regs);
409 /* compute the constraint factor */
410 res->constr_factor = (real_t) (1 + env->n_regs - bitset_popcount(res->adm_colors)) / env->n_regs;
412 /* set the number of interfering affinity neighbours to -1, they are calculated later */
413 res->int_aff_neigh = -1;
415 /* build list of interfering neighbours */
417 be_ifg_foreach_neighbour(env->ifg, &nodes_it, irn, neigh) {
418 if (!arch_irn_is_ignore(neigh)) {
419 obstack_ptr_grow(phase_obst(ph), neigh);
423 res->int_neighs = obstack_finish(phase_obst(ph));
429 * Check if affinity chunk @p chunk interferes with node @p irn.
431 static inline int aff_chunk_interferes(const aff_chunk_t *chunk, const ir_node *irn)
433 return node_contains(chunk->interfere, irn);
437 * Check if there are interference edges from c1 to c2.
439 * @param c2 Another chunk
440 * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
442 static inline int aff_chunks_interfere(const aff_chunk_t *c1, const aff_chunk_t *c2)
449 /* check if there is a node in c2 having an interfering neighbor in c1 */
450 for (i = ARR_LEN(c2->n) - 1; i >= 0; --i) {
451 const ir_node *irn = c2->n[i];
453 if (node_contains(c1->interfere, irn))
460 * Returns the affinity chunk of @p irn or creates a new
461 * one with @p irn as element if there is none assigned.
463 static inline aff_chunk_t *get_aff_chunk(co_mst_env_t *env, const ir_node *irn)
465 co_mst_irn_t *node = get_co_mst_irn(env, irn);
470 * Let chunk(src) absorb the nodes of chunk(tgt) (only possible when there
471 * are no interference edges from chunk(src) to chunk(tgt)).
472 * @return 1 if successful, 0 if not possible
474 static int aff_chunk_absorb(co_mst_env_t *env, const ir_node *src, const ir_node *tgt)
476 aff_chunk_t *c1 = get_aff_chunk(env, src);
477 aff_chunk_t *c2 = get_aff_chunk(env, tgt);
480 DB((dbg, LEVEL_4, "Attempt to let c1 (id %u): ", c1 ? c1->id : 0));
482 DBG_AFF_CHUNK(env, LEVEL_4, c1);
484 DB((dbg, LEVEL_4, "{%+F}", src));
486 DB((dbg, LEVEL_4, "\n\tabsorb c2 (id %u): ", c2 ? c2->id : 0));
488 DBG_AFF_CHUNK(env, LEVEL_4, c2);
490 DB((dbg, LEVEL_4, "{%+F}", tgt));
492 DB((dbg, LEVEL_4, "\n"));
497 /* no chunk exists */
498 co_mst_irn_t *mirn = get_co_mst_irn(env, src);
501 for (i = mirn->n_neighs - 1; i >= 0; --i) {
502 if (mirn->int_neighs[i] == tgt)
506 /* create one containing both nodes */
507 c1 = new_aff_chunk(env);
508 aff_chunk_add_node(c1, get_co_mst_irn(env, src));
509 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
513 /* c2 already exists */
514 if (! aff_chunk_interferes(c2, src)) {
515 aff_chunk_add_node(c2, get_co_mst_irn(env, src));
519 } else if (c2 == NULL) {
520 /* c1 already exists */
521 if (! aff_chunk_interferes(c1, tgt)) {
522 aff_chunk_add_node(c1, get_co_mst_irn(env, tgt));
525 } else if (c1 != c2 && ! aff_chunks_interfere(c1, c2)) {
528 for (idx = 0, len = ARR_LEN(c2->n); idx < len; ++idx)
529 aff_chunk_add_node(c1, get_co_mst_irn(env, c2->n[idx]));
531 for (idx = 0, len = ARR_LEN(c2->interfere); idx < len; ++idx) {
532 const ir_node *irn = c2->interfere[idx];
533 nodes_insert(&c1->interfere, irn);
536 c1->weight_consistent = 0;
538 delete_aff_chunk(c2);
541 DB((dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
545 DB((dbg, LEVEL_4, " ... absorbed\n"));
550 * Assures that the weight of the given chunk is consistent.
552 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c)
554 if (! c->weight_consistent) {
558 for (i = 0; i < env->n_regs; ++i) {
559 c->color_affinity[i].col = i;
560 c->color_affinity[i].cost = REAL(0.0);
563 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
564 const ir_node *n = c->n[idx];
565 const affinity_node_t *an = get_affinity_info(env->co, n);
566 co_mst_irn_t *node = get_co_mst_irn(env, n);
569 if (node->constr_factor > REAL(0.0)) {
571 bitset_foreach (node->adm_colors, col)
572 c->color_affinity[col].cost += node->constr_factor;
577 co_gs_foreach_neighb(an, neigh) {
578 const ir_node *m = neigh->irn;
580 if (arch_irn_is_ignore(m))
583 w += node_contains(c->n, m) ? neigh->costs : 0;
588 for (i = 0; i < env->n_regs; ++i)
589 c->color_affinity[i].cost *= (REAL(1.0) / ARR_LEN(c->n));
592 // c->weight = bitset_popcount(c->nodes);
593 c->weight_consistent = 1;
598 * Count the number of interfering affinity neighbours
600 static int count_interfering_aff_neighs(co_mst_env_t *env, const affinity_node_t *an)
602 const neighb_t *neigh;
603 const ir_node *irn = an->irn;
604 const co_mst_irn_t *node = get_co_mst_irn(env, irn);
607 co_gs_foreach_neighb(an, neigh) {
608 const ir_node *n = neigh->irn;
611 if (arch_irn_is_ignore(n))
614 /* check if the affinity neighbour interfere */
615 for (i = 0; i < node->n_neighs; ++i) {
616 if (node->int_neighs[i] == n) {
627 * Build chunks of nodes connected by affinity edges.
628 * We start at the heaviest affinity edge.
629 * The chunks of the two edge-defining nodes will be
630 * merged if there are no interference edges from one
631 * chunk to the other.
633 static void build_affinity_chunks(co_mst_env_t *env)
635 nodes_iter_t nodes_it;
636 aff_edge_t *edges = NEW_ARR_F(aff_edge_t, 0);
639 aff_chunk_t *curr_chunk;
641 /* at first we create the affinity edge objects */
642 be_ifg_foreach_node(env->ifg, &nodes_it, n) {
643 int n_idx = get_irn_idx(n);
647 if (arch_irn_is_ignore(n))
650 n1 = get_co_mst_irn(env, n);
651 an = get_affinity_info(env->co, n);
656 if (n1->int_aff_neigh < 0)
657 n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
659 /* build the affinity edges */
660 co_gs_foreach_neighb(an, neigh) {
661 const ir_node *m = neigh->irn;
662 int m_idx = get_irn_idx(m);
664 /* record the edge in only one direction */
669 /* skip ignore nodes */
670 if (arch_irn_is_ignore(m))
676 n2 = get_co_mst_irn(env, m);
677 if (n2->int_aff_neigh < 0) {
678 affinity_node_t *am = get_affinity_info(env->co, m);
679 n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
682 * these weights are pure hackery ;-).
683 * It's not chriswue's fault but mine.
685 edge.weight = neigh->costs;
686 ARR_APP1(aff_edge_t, edges, edge);
692 /* now: sort edges and build the affinity chunks */
693 len = ARR_LEN(edges);
694 qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
695 for (i = 0; i < len; ++i) {
696 DBG((dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
698 (void)aff_chunk_absorb(env, edges[i].src, edges[i].tgt);
701 /* now insert all chunks into a priority queue */
702 list_for_each_entry(aff_chunk_t, curr_chunk, &env->chunklist, list) {
703 aff_chunk_assure_weight(env, curr_chunk);
705 DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
706 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
707 DBG((dbg, LEVEL_1, "\n"));
709 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
712 foreach_phase_irn(&env->ph, n) {
713 co_mst_irn_t *mirn = get_co_mst_irn(env, n);
715 if (mirn->chunk == NULL) {
716 /* no chunk is allocated so far, do it now */
717 aff_chunk_t *curr_chunk = new_aff_chunk(env);
718 aff_chunk_add_node(curr_chunk, mirn);
720 aff_chunk_assure_weight(env, curr_chunk);
722 DBG((dbg, LEVEL_1, "entry #%u", curr_chunk->id));
723 DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
724 DBG((dbg, LEVEL_1, "\n"));
726 pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
733 static __attribute__((unused)) void chunk_order_nodes(co_mst_env_t *env, aff_chunk_t *chunk)
735 pqueue_t *grow = new_pqueue();
736 const ir_node *max_node = NULL;
740 for (i = ARR_LEN(chunk->n) - 1; i >= 0; i--) {
741 const ir_node *irn = chunk->n[i];
742 affinity_node_t *an = get_affinity_info(env->co, irn);
746 if (arch_irn_is_ignore(irn))
750 co_gs_foreach_neighb(an, neigh)
753 if (w > max_weight) {
761 bitset_t *visited = bitset_irg_malloc(env->co->irg);
763 for (i = ARR_LEN(chunk->n) - 1; i >= 0; --i)
764 bitset_add_irn(visited, chunk->n[i]);
766 pqueue_put(grow, (void *) max_node, max_weight);
767 bitset_remv_irn(visited, max_node);
769 while (!pqueue_empty(grow)) {
770 ir_node *irn = pqueue_pop_front(grow);
771 affinity_node_t *an = get_affinity_info(env->co, irn);
774 if (arch_irn_is_ignore(irn))
777 assert(i <= ARR_LEN(chunk->n));
782 /* build the affinity edges */
783 co_gs_foreach_neighb(an, neigh) {
784 co_mst_irn_t *node = get_co_mst_irn(env, neigh->irn);
786 if (bitset_contains_irn(visited, node->irn)) {
787 pqueue_put(grow, (void *) neigh->irn, neigh->costs);
788 bitset_remv_irn(visited, node->irn);
794 bitset_free(visited);
799 * Greedy collect affinity neighbours into thew new chunk @p chunk starting at node @p node.
801 static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *visited,
802 aff_chunk_t *chunk, aff_chunk_t *orig_chunk, decide_func_t *decider, int col)
804 waitq *nodes = new_waitq();
806 DBG((dbg, LEVEL_1, "\n\tExpanding new chunk (#%u) from %+F, color %d:", chunk->id, node->irn, col));
808 /* init queue and chunk */
809 waitq_put(nodes, node);
810 bitset_set(visited, get_irn_idx(node->irn));
811 aff_chunk_add_node(chunk, node);
812 DB((dbg, LEVEL_1, " %+F", node->irn));
814 /* as long as there are nodes in the queue */
815 while (! waitq_empty(nodes)) {
816 co_mst_irn_t *n = waitq_get(nodes);
817 affinity_node_t *an = get_affinity_info(env->co, n->irn);
819 /* check all affinity neighbors */
822 co_gs_foreach_neighb(an, neigh) {
823 const ir_node *m = neigh->irn;
824 int m_idx = get_irn_idx(m);
827 if (arch_irn_is_ignore(m))
830 n2 = get_co_mst_irn(env, m);
832 if (! bitset_is_set(visited, m_idx) &&
835 ! aff_chunk_interferes(chunk, m) &&
836 node_contains(orig_chunk->n, m))
839 following conditions are met:
840 - neighbour is not visited
841 - neighbour likes the color
842 - neighbour has not yet a fixed color
843 - the new chunk doesn't interfere with the neighbour
844 - neighbour belongs or belonged once to the original chunk
846 bitset_set(visited, m_idx);
847 aff_chunk_add_node(chunk, n2);
848 DB((dbg, LEVEL_1, " %+F", n2->irn));
849 /* enqueue for further search */
850 waitq_put(nodes, n2);
856 DB((dbg, LEVEL_1, "\n"));
862 * Fragment the given chunk into chunks having given color and not having given color.
864 static aff_chunk_t *fragment_chunk(co_mst_env_t *env, int col, aff_chunk_t *c, waitq *tmp)
866 bitset_t *visited = bitset_irg_malloc(env->co->irg);
868 aff_chunk_t *best = NULL;
870 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
873 aff_chunk_t *tmp_chunk;
874 decide_func_t *decider;
878 if (bitset_is_set(visited, get_irn_idx(irn)))
881 node = get_co_mst_irn(env, irn);
883 if (get_mst_irn_col(node) == col) {
884 decider = decider_has_color;
886 DBG((dbg, LEVEL_4, "\tcolor %d wanted\n", col));
889 decider = decider_hasnot_color;
891 DBG((dbg, LEVEL_4, "\tcolor %d forbidden\n", col));
894 /* create a new chunk starting at current node */
895 tmp_chunk = new_aff_chunk(env);
896 waitq_put(tmp, tmp_chunk);
897 expand_chunk_from(env, node, visited, tmp_chunk, c, decider, col);
898 assert(ARR_LEN(tmp_chunk->n) > 0 && "No nodes added to chunk");
900 /* remember the local best */
901 aff_chunk_assure_weight(env, tmp_chunk);
902 if (check_for_best && (! best || best->weight < tmp_chunk->weight))
906 assert(best && "No chunk found?");
907 bitset_free(visited);
912 * Resets the temporary fixed color of all nodes within wait queue @p nodes.
913 * ATTENTION: the queue is empty after calling this function!
915 static inline void reject_coloring(struct list_head *nodes)
917 co_mst_irn_t *n, *temp;
918 DB((dbg, LEVEL_4, "\treject coloring for"));
919 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
920 DB((dbg, LEVEL_4, " %+F", n->irn));
921 assert(n->tmp_col >= 0);
923 list_del_init(&n->list);
925 DB((dbg, LEVEL_4, "\n"));
928 static inline void materialize_coloring(struct list_head *nodes)
930 co_mst_irn_t *n, *temp;
931 list_for_each_entry_safe(co_mst_irn_t, n, temp, nodes, list) {
932 assert(n->tmp_col >= 0);
935 list_del_init(&n->list);
939 static inline void set_temp_color(co_mst_irn_t *node, int col, struct list_head *changed)
942 assert(!node->fixed);
943 assert(node->tmp_col < 0);
944 assert(node->list.next == &node->list && node->list.prev == &node->list);
945 assert(bitset_is_set(node->adm_colors, col));
947 list_add_tail(&node->list, changed);
951 static inline int is_loose(co_mst_irn_t *node)
953 return !node->fixed && node->tmp_col < 0;
957 * Determines the costs for each color if it would be assigned to node @p node.
959 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs)
961 int *neigh_cols = ALLOCAN(int, env->n_regs);
966 for (i = 0; i < env->n_regs; ++i) {
969 costs[i].cost = bitset_is_set(node->adm_colors, i) ? node->constr_factor : REAL(0.0);
972 for (i = 0; i < node->n_neighs; ++i) {
973 co_mst_irn_t *n = get_co_mst_irn(env, node->int_neighs[i]);
974 int col = get_mst_irn_col(n);
979 costs[col].cost = REAL(0.0);
983 coeff = REAL(1.0) / n_loose;
984 for (i = 0; i < env->n_regs; ++i)
985 costs[i].cost *= REAL(1.0) - coeff * neigh_cols[i];
989 /* need forward declaration due to recursive call */
990 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);
993 * Tries to change node to a color but @p explude_col.
994 * @return 1 if succeeded, 0 otherwise.
996 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)
998 int col = get_mst_irn_col(node);
1001 /* neighbours has already a different color -> good, temporary fix it */
1002 if (col != exclude_col) {
1004 set_temp_color(node, col, changed);
1008 /* The node has the color it should not have _and_ has not been visited yet. */
1009 if (is_loose(node)) {
1010 col_cost_t *costs = ALLOCAN(col_cost_t, env->n_regs);
1012 /* Get the costs for giving the node a specific color. */
1013 determine_color_costs(env, node, costs);
1015 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
1016 costs[exclude_col].cost = REAL(0.0);
1018 /* sort the colors according costs, cheapest first. */
1019 qsort(costs, env->n_regs, sizeof(costs[0]), cmp_col_cost_gt);
1021 /* Try recoloring the node using the color list. */
1022 res = recolor_nodes(env, node, costs, changed, depth + 1, max_depth, trip);
1029 * Tries to bring node @p node to cheapest color and color all interfering neighbours with other colors.
1030 * ATTENTION: Expect @p costs already sorted by increasing costs.
1031 * @return 1 if coloring could be applied, 0 otherwise.
1033 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)
1036 struct list_head local_changed;
1039 if (depth > *max_depth)
1042 DBG((dbg, LEVEL_4, "\tRecoloring %+F with color-costs", node->irn));
1043 DBG_COL_COST(env, LEVEL_4, costs);
1044 DB((dbg, LEVEL_4, "\n"));
1046 if (depth >= recolor_limit) {
1047 DBG((dbg, LEVEL_4, "\tHit recolor limit\n"));
1051 for (i = 0; i < env->n_regs; ++i) {
1052 int tgt_col = costs[i].col;
1056 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
1057 if (costs[i].cost == REAL(0.0)) {
1058 DBG((dbg, LEVEL_4, "\tAll further colors forbidden\n"));
1062 /* Set the new color of the node and mark the node as temporarily fixed. */
1063 assert(node->tmp_col < 0 && "Node must not have been temporary fixed.");
1064 INIT_LIST_HEAD(&local_changed);
1065 set_temp_color(node, tgt_col, &local_changed);
1066 DBG((dbg, LEVEL_4, "\tTemporary setting %+F to color %d\n", node->irn, tgt_col));
1068 /* try to color all interfering neighbours with current color forbidden */
1069 for (j = 0; j < node->n_neighs; ++j) {
1073 neigh = node->int_neighs[j];
1075 if (arch_irn_is_ignore(neigh))
1078 nn = get_co_mst_irn(env, neigh);
1079 DB((dbg, LEVEL_4, "\tHandling neighbour %+F, at position %d (fixed: %d, tmp_col: %d, col: %d)\n",
1080 neigh, j, nn->fixed, nn->tmp_col, nn->col));
1083 Try to change the color of the neighbor and record all nodes which
1084 get changed in the tmp list. Add this list to the "changed" list for
1085 that color. If we did not succeed to change the color of the neighbor,
1086 we bail out and try the next color.
1088 if (get_mst_irn_col(nn) == tgt_col) {
1089 /* try to color neighbour with tgt_col forbidden */
1090 neigh_ok = change_node_color_excluded(env, nn, tgt_col, &local_changed, depth + 1, max_depth, trip);
1098 We managed to assign the target color to all neighbors, so from the perspective
1099 of the current node, every thing was ok and we can return safely.
1102 /* append the local_changed ones to global ones */
1103 list_splice(&local_changed, changed);
1107 /* coloring of neighbours failed, so we try next color */
1108 reject_coloring(&local_changed);
1112 DBG((dbg, LEVEL_4, "\tAll colors failed\n"));
1117 * Tries to bring node @p node and all it's neighbours to color @p tgt_col.
1118 * @return 1 if color @p col could be applied, 0 otherwise
1120 static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col, struct list_head *changed)
1122 int col = get_mst_irn_col(node);
1124 /* if node already has the target color -> good, temporary fix it */
1125 if (col == tgt_col) {
1126 DBG((dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
1128 set_temp_color(node, tgt_col, changed);
1133 Node has not yet a fixed color and target color is admissible
1134 -> try to recolor node and it's affinity neighbours
1136 if (is_loose(node) && bitset_is_set(node->adm_colors, tgt_col)) {
1137 col_cost_t *costs = env->single_cols[tgt_col];
1138 int res, max_depth, trip;
1143 DBG((dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
1144 res = recolor_nodes(env, node, costs, changed, 0, &max_depth, &trip);
1145 DBG((dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
1146 stat_ev_int("heur4_recolor_depth_max", max_depth);
1147 stat_ev_int("heur4_recolor_trip", trip);
1153 #ifdef DEBUG_libfirm
1154 if (firm_dbg_get_mask(dbg) & LEVEL_4) {
1155 if (!is_loose(node))
1156 DB((dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
1158 DB((dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
1159 dbg_admissible_colors(env, node);
1160 DB((dbg, LEVEL_4, ")\n"));
1169 * Tries to color an affinity chunk (or at least a part of it).
1170 * Inserts uncolored parts of the chunk as a new chunk into the priority queue.
1172 static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c)
1174 aff_chunk_t *best_chunk = NULL;
1175 int n_nodes = ARR_LEN(c->n);
1176 int best_color = -1;
1177 int n_int_chunks = 0;
1178 waitq *tmp_chunks = new_waitq();
1179 waitq *best_starts = NULL;
1180 col_cost_t *order = ALLOCANZ(col_cost_t, env->n_regs);
1182 int idx, len, i, nidx, pos;
1183 struct list_head changed;
1185 DB((dbg, LEVEL_2, "fragmentizing chunk #%u", c->id));
1186 DBG_AFF_CHUNK(env, LEVEL_2, c);
1187 DB((dbg, LEVEL_2, "\n"));
1189 stat_ev_ctx_push_fmt("heur4_color_chunk", "%u", c->id);
1191 ++env->chunk_visited;
1193 /* compute color preference */
1194 for (pos = 0, len = ARR_LEN(c->interfere); pos < len; ++pos) {
1195 const ir_node *n = c->interfere[pos];
1196 co_mst_irn_t *node = get_co_mst_irn(env, n);
1197 aff_chunk_t *chunk = node->chunk;
1199 if (is_loose(node) && chunk && chunk->visited < env->chunk_visited) {
1200 assert(!chunk->deleted);
1201 chunk->visited = env->chunk_visited;
1204 aff_chunk_assure_weight(env, chunk);
1205 for (i = 0; i < env->n_regs; ++i)
1206 order[i].cost += chunk->color_affinity[i].cost;
1210 for (i = 0; i < env->n_regs; ++i) {
1211 real_t dislike = n_int_chunks > 0 ? REAL(1.0) - order[i].cost / n_int_chunks : REAL(0.0);
1213 order[i].cost = (REAL(1.0) - dislike_influence) * c->color_affinity[i].cost + dislike_influence * dislike;
1216 qsort(order, env->n_regs, sizeof(order[0]), cmp_col_cost_gt);
1218 DBG_COL_COST(env, LEVEL_2, order);
1219 DB((dbg, LEVEL_2, "\n"));
1221 /* check which color is the "best" for the given chunk.
1222 * if we found a color which was ok for all nodes, we take it
1223 * and do not look further. (see did_all flag usage below.)
1224 * If we have many colors which fit all nodes it is hard to decide
1225 * which one to take anyway.
1226 * TODO Sebastian: Perhaps we should at all nodes and figure out
1227 * a suitable color using costs as done above (determine_color_costs).
1229 for (i = 0; i < env->k; ++i) {
1230 int col = order[i].col;
1231 waitq *good_starts = new_waitq();
1232 aff_chunk_t *local_best;
1235 /* skip ignore colors */
1236 if (bitset_is_set(env->ignore_regs, col))
1239 DB((dbg, LEVEL_2, "\ttrying color %d\n", col));
1243 /* try to bring all nodes of given chunk to the current color. */
1244 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1245 const ir_node *irn = c->n[idx];
1246 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1249 assert(! node->fixed && "Node must not have a fixed color.");
1250 DB((dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
1253 The order of the colored nodes is important, so we record the successfully
1254 colored ones in the order they appeared.
1256 INIT_LIST_HEAD(&changed);
1258 good = change_node_color(env, node, col, &changed);
1259 stat_ev_tim_pop("heur4_recolor");
1261 waitq_put(good_starts, node);
1262 materialize_coloring(&changed);
1267 reject_coloring(&changed);
1269 n_succeeded += good;
1270 DB((dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, good ? "succeeded" : "failed"));
1273 /* unfix all nodes */
1274 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1275 co_mst_irn_t *node = get_co_mst_irn(env, c->n[idx]);
1279 /* try next color when failed */
1280 if (n_succeeded == 0)
1283 /* fragment the chunk according to the coloring */
1284 local_best = fragment_chunk(env, col, c, tmp_chunks);
1286 /* search the best of the good list
1287 and make it the new best if it is better than the current */
1289 aff_chunk_assure_weight(env, local_best);
1291 DB((dbg, LEVEL_3, "\t\tlocal best chunk (id %u) for color %d: ", local_best->id, col));
1292 DBG_AFF_CHUNK(env, LEVEL_3, local_best);
1294 if (! best_chunk || best_chunk->weight < local_best->weight) {
1295 best_chunk = local_best;
1298 del_waitq(best_starts);
1299 best_starts = good_starts;
1300 DB((dbg, LEVEL_3, "\n\t\t... setting global best chunk (id %u), color %d\n", best_chunk->id, best_color));
1302 DB((dbg, LEVEL_3, "\n\t\t... omitting, global best is better\n"));
1303 del_waitq(good_starts);
1307 del_waitq(good_starts);
1310 /* if all nodes were recolored, bail out */
1311 if (n_succeeded == n_nodes)
1315 stat_ev_int("heur4_colors_tried", i);
1317 /* free all intermediate created chunks except best one */
1318 while (! waitq_empty(tmp_chunks)) {
1319 aff_chunk_t *tmp = waitq_get(tmp_chunks);
1320 if (tmp != best_chunk)
1321 delete_aff_chunk(tmp);
1323 del_waitq(tmp_chunks);
1325 /* return if coloring failed */
1328 del_waitq(best_starts);
1332 DB((dbg, LEVEL_2, "\tbest chunk #%u ", best_chunk->id));
1333 DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
1334 DB((dbg, LEVEL_2, "using color %d\n", best_color));
1336 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1337 const ir_node *irn = best_chunk->n[idx];
1338 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1341 /* bring the node to the color. */
1342 DB((dbg, LEVEL_4, "\tManifesting color %d for %+F, chunk #%u\n", best_color, node->irn, best_chunk->id));
1343 INIT_LIST_HEAD(&changed);
1345 res = change_node_color(env, node, best_color, &changed);
1346 stat_ev_tim_pop("heur4_recolor");
1348 materialize_coloring(&changed);
1351 assert(list_empty(&changed));
1354 /* remove the nodes in best chunk from original chunk */
1355 len = ARR_LEN(best_chunk->n);
1356 for (idx = 0; idx < len; ++idx) {
1357 const ir_node *irn = best_chunk->n[idx];
1358 int pos = nodes_bsearch(c->n, irn);
1363 len = ARR_LEN(c->n);
1364 for (idx = nidx = 0; idx < len; ++idx) {
1365 const ir_node *irn = c->n[idx];
1371 ARR_SHRINKLEN(c->n, nidx);
1374 /* we have to get the nodes back into the original chunk because they are scattered over temporary chunks */
1375 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1376 const ir_node *n = c->n[idx];
1377 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1381 /* fragment the remaining chunk */
1382 visited = bitset_irg_malloc(env->co->irg);
1383 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx)
1384 bitset_set(visited, get_irn_idx(best_chunk->n[idx]));
1386 for (idx = 0, len = ARR_LEN(c->n); idx < len; ++idx) {
1387 const ir_node *irn = c->n[idx];
1388 if (! bitset_is_set(visited, get_irn_idx(irn))) {
1389 aff_chunk_t *new_chunk = new_aff_chunk(env);
1390 co_mst_irn_t *node = get_co_mst_irn(env, irn);
1392 expand_chunk_from(env, node, visited, new_chunk, c, decider_always_yes, 0);
1393 aff_chunk_assure_weight(env, new_chunk);
1394 pqueue_put(env->chunks, new_chunk, new_chunk->weight);
1398 for (idx = 0, len = ARR_LEN(best_chunk->n); idx < len; ++idx) {
1399 const ir_node *n = best_chunk->n[idx];
1400 co_mst_irn_t *nn = get_co_mst_irn(env, n);
1404 /* clear obsolete chunks and free some memory */
1405 delete_aff_chunk(best_chunk);
1406 bitset_free(visited);
1408 del_waitq(best_starts);
1410 stat_ev_ctx_pop("heur4_color_chunk");
1414 * Main driver for mst safe coalescing algorithm.
1416 static int co_solve_heuristic_mst(copy_opt_t *co)
1418 unsigned n_regs = co->cls->n_regs;
1419 bitset_t *ignore_regs = bitset_alloca(n_regs);
1422 co_mst_env_t mst_env;
1429 phase_init(&mst_env.ph, co->irg, co_mst_irn_init);
1430 phase_set_private(&mst_env.ph, &mst_env);
1432 k = be_put_ignore_regs(co->cenv->irg, co->cls, ignore_regs);
1435 mst_env.n_regs = n_regs;
1437 mst_env.chunks = new_pqueue();
1439 mst_env.ignore_regs = ignore_regs;
1440 mst_env.ifg = co->cenv->ifg;
1441 INIT_LIST_HEAD(&mst_env.chunklist);
1442 mst_env.chunk_visited = 0;
1443 mst_env.single_cols = phase_alloc(&mst_env.ph, sizeof(*mst_env.single_cols) * n_regs);
1445 for (i = 0; i < n_regs; ++i) {
1446 col_cost_t *vec = phase_alloc(&mst_env.ph, sizeof(*vec) * n_regs);
1448 mst_env.single_cols[i] = vec;
1449 for (j = 0; j < n_regs; ++j) {
1451 vec[j].cost = REAL(0.0);
1455 vec[0].cost = REAL(1.0);
1458 DBG((dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
1460 /* build affinity chunks */
1462 build_affinity_chunks(&mst_env);
1463 stat_ev_tim_pop("heur4_initial_chunk");
1465 /* color chunks as long as there are some */
1466 while (! pqueue_empty(mst_env.chunks)) {
1467 aff_chunk_t *chunk = pqueue_pop_front(mst_env.chunks);
1469 color_aff_chunk(&mst_env, chunk);
1470 DB((dbg, LEVEL_4, "<<<====== Coloring chunk (%u) done\n", chunk->id));
1471 delete_aff_chunk(chunk);
1474 /* apply coloring */
1475 foreach_phase_irn(&mst_env.ph, irn) {
1477 const arch_register_t *reg;
1479 if (arch_irn_is_ignore(irn))
1482 mirn = get_co_mst_irn(&mst_env, irn);
1483 // assert(mirn->fixed && "Node should have fixed color");
1485 /* skip nodes where color hasn't changed */
1486 if (mirn->init_col == mirn->col)
1489 reg = arch_register_for_index(co->cls, mirn->col);
1490 arch_set_irn_register(irn, reg);
1491 DB((dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
1494 /* free allocated memory */
1495 del_pqueue(mst_env.chunks);
1496 phase_deinit(&mst_env.ph);
1498 stat_ev_tim_pop("heur4_total");
1503 static const lc_opt_table_entry_t options[] = {
1504 LC_OPT_ENT_INT ("limit", "limit recoloring", &recolor_limit),
1505 LC_OPT_ENT_DBL ("di", "dislike influence", &dislike_influence),
1509 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur4);
1510 void be_init_copyheur4(void)
1512 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1513 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1514 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1515 lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
1516 lc_opt_entry_t *heur4_grp = lc_opt_get_grp(co_grp, "heur4");
1518 static co_algo_info copyheur = {
1519 co_solve_heuristic_mst, 0
1522 lc_opt_add_table(heur4_grp, options);
1523 be_register_copyopt("heur4", ©heur);
1525 FIRM_DBG_REGISTER(dbg, "firm.be.co.heur4");