2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief More experiments on coalescing.
9 * @author Sebastian Hack
15 #include "lc_opts_enum.h"
20 #include "beintlive_t.h"
25 #include "raw_bitset.h"
28 #include "bitfiddle.h"
30 #include "irgraph_t.h"
35 #include "irnodemap.h"
40 #include "becopyopt.h"
41 #include "becopyopt_t.h"
42 #include "bechordal_t.h"
47 #define DUMP_ALL 2 * DUMP_CLOUD - 1
49 static unsigned dump_flags = 0;
50 static int subtree_iter = 4;
51 static int max_depth = 20;
52 static double constr_factor = 0.9;
54 static const lc_opt_enum_mask_items_t dump_items[] = {
55 { "before", DUMP_BEFORE },
56 { "after", DUMP_AFTER },
57 { "cloud", DUMP_CLOUD },
62 static lc_opt_enum_mask_var_t dump_var = {
63 &dump_flags, dump_items
66 static const lc_opt_table_entry_t options[] = {
67 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
68 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
69 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
70 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
76 / ___|| |_ __ _ _ __| |_
77 \___ \| __/ _` | '__| __|
78 ___) | || (_| | | | |_
79 |____/ \__\__,_|_| \__|
83 #define INFEASIBLE(cost) ((cost) == INT_MAX)
85 typedef unsigned col_t;
87 typedef struct co2_irn_t co2_irn_t;
88 typedef struct co2_cloud_t co2_cloud_t;
89 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
100 bitset_t *allocatable_regs;
104 struct list_head cloud_head;
105 DEBUG_ONLY(firm_dbg_module_t *dbg;)
110 affinity_node_t *aff;
111 co2_irn_t *touched_next;
116 unsigned tmp_fixed : 1;
117 struct list_head changed_list;
120 struct co2_cloud_irn_t {
121 struct co2_irn_t inh;
125 co2_cloud_irn_t *mst_parent;
128 co2_cloud_irn_t **mst_childs;
133 col_cost_pair_t *tmp_coloring;
134 struct list_head cloud_list;
135 struct list_head mst_list;
148 co2_cloud_irn_t *master;
149 co2_cloud_irn_t *mst_root;
150 co2_cloud_irn_t **seq;
151 struct list_head members_head;
152 struct list_head list;
156 co2_cloud_irn_t *src, *tgt;
160 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
162 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
164 co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
166 ci = OALLOCZ(&env->obst, co2_irn_t);
168 INIT_LIST_HEAD(&ci->changed_list);
169 ci->touched_next = env->touched;
170 ci->orig_col = get_irn_col(node);
175 ir_nodemap_insert(&env->map, node, ci);
180 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
182 co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
184 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
186 INIT_LIST_HEAD(&ci->inh.changed_list);
187 ci->inh.touched_next = env->touched;
188 ci->inh.orig_col = get_irn_col(node);
189 env->touched = &ci->inh;
191 ci->inh.aff = get_affinity_info(env->co, node);
193 INIT_LIST_HEAD(&ci->cloud_list);
196 ir_nodemap_insert(&env->map, node, ci);
201 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
203 static int cmp_clouds_gt(const void *a, const void *b)
205 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
206 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
207 double c = CLOUD_WEIGHT(*p);
208 double d = CLOUD_WEIGHT(*q);
209 return QSORT_CMP(d, c);
213 * An order on color/costs pairs.
214 * If the costs are equal, we use the color as a kind of normalization.
216 static int col_cost_pair_lt(const void *a, const void *b)
218 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
219 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
222 return QSORT_CMP(c, d);
225 static int cmp_edges(const void *a, const void *b)
227 const edge_t *p = (const edge_t*)a;
228 const edge_t *q = (const edge_t*)b;
229 return QSORT_CMP(q->costs, p->costs);
232 static col_t get_col(co2_t *env, const ir_node *irn)
234 co2_irn_t *ci = get_co2_irn(env, irn);
235 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
238 static inline int color_is_fix(co2_t *env, const ir_node *irn)
240 co2_irn_t *ci = get_co2_irn(env, irn);
241 return ci->fixed || ci->tmp_fixed;
244 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
246 if (ci->adm_cache == NULL) {
247 const arch_register_req_t *req;
248 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
249 req = arch_get_irn_register_req(ci->irn);
251 if (arch_register_req_is(req, limited)) {
252 rbitset_copy_to_bitset(req->limited, ci->adm_cache);
254 bitset_copy(ci->adm_cache, env->allocatable_regs);
258 return ci->adm_cache;
261 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
263 bitset_copy(bs, get_adm(env, ci));
267 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
269 bitset_t *bs = get_adm(env, ci);
270 return bitset_is_set(bs, col);
273 static void incur_constraint_costs(ir_node const *const irn, col_cost_pair_t *const col_costs, int const costs)
275 const arch_register_req_t *req = arch_get_irn_register_req(irn);
277 if (arch_register_req_is(req, limited)) {
278 unsigned const n_regs = req->cls->n_regs;
279 unsigned const n_constr = rbitset_popcount(req->limited, n_regs);
280 for (unsigned i = 0; i < n_regs; ++i) {
281 if (rbitset_is_set(req->limited, i)) {
282 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
289 * Determine costs which shall indicate how cheap/expensive it is to try
290 * to assign a node some color.
291 * The costs are computed for all colors. INT_MAX means that it is impossible
292 * to give the node that specific color.
294 * @param env The co2 this pointer.
295 * @param irn The node.
296 * @param col_costs An array of colors x costs where the costs are written to.
298 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
300 const ir_node *irn = ci->irn;
301 be_ifg_t *ifg = env->co->cenv->ifg;
302 int n_regs = env->co->cls->n_regs;
303 affinity_node_t *a = ci->aff;
305 neighbours_iter_t it;
308 /* Put all forbidden colors into the aux bitset. */
309 bitset_t *const admissible = bitset_alloca(n_regs);
310 admissible_colors(env, ci, admissible);
312 for (i = 0; i < n_regs; ++i) {
313 col_costs[i].col = i;
314 col_costs[i].costs = 0;
318 co_gs_foreach_neighb(a, n) {
319 if (color_is_fix(env, n->irn)) {
320 col_t col = get_col(env, n->irn);
321 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
324 incur_constraint_costs(n->irn, col_costs, -n->costs);
328 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
329 col_t col = get_col(env, pos);
330 if (color_is_fix(env, pos)) {
331 col_costs[col].costs = INT_MAX;
334 incur_constraint_costs(pos, col_costs, INT_MAX);
335 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
338 be_ifg_neighbours_break(&it);
340 /* Set the costs to infinity for each color which is not allowed at this node. */
341 bitset_foreach_clear(admissible, elm) {
342 col_costs[elm].costs = INT_MAX;
347 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
349 int n_regs = env->co->cls->n_regs;
352 for (i = 0; i < n_regs; ++i) {
354 seq[i].costs = INT_MAX;
358 assert(is_color_admissible(env, ci, col));
364 static void reject_coloring(struct list_head *h)
366 list_for_each_entry(co2_irn_t, pos, h, changed_list)
370 static void materialize_coloring(struct list_head *h)
372 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
373 pos->orig_col = pos->tmp_col;
378 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
380 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
382 int n_regs = env->co->cls->n_regs;
383 be_ifg_t *ifg = env->co->cenv->ifg;
384 co2_irn_t *ci = get_co2_irn(env, irn);
389 if (depth >= max_depth)
392 for (i = 0; i < n_regs; ++i) {
393 col_t tgt_col = col_list[i].col;
394 unsigned costs = col_list[i].costs;
397 struct list_head changed;
398 neighbours_iter_t it;
400 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
402 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
403 if (INFEASIBLE(costs)) {
404 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
409 /* Set the new color of the node and mark the node as temporarily fixed. */
410 ci->tmp_col = tgt_col;
414 If that color has costs > 0, there's at least one neighbor having that color,
415 so we will try to change the neighbors' colors, too.
417 INIT_LIST_HEAD(&changed);
418 list_add(&ci->changed_list, &changed);
420 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
422 /* try to re-color the neighbor if it has the target color. */
423 if (get_col(env, n) == tgt_col) {
424 struct list_head tmp;
427 Try to change the color of the neighbor and record all nodes which
428 get changed in the tmp list. Add this list to the "changed" list for
429 that color. If we did not succeed to change the color of the neighbor,
430 we bail out and try the next color.
432 INIT_LIST_HEAD(&tmp);
433 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
434 list_splice(&tmp, &changed);
439 be_ifg_neighbours_break(&it);
442 We managed to assign the target color to all neighbors, so from the perspective
443 of the current node, every thing was ok and we can return safely.
446 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
447 list_splice(&changed, parent_changed);
453 If not, that color did not succeed and we unfix all nodes we touched
454 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
457 reject_coloring(&changed);
463 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
465 co2_irn_t *ci = get_co2_irn(env, irn);
467 col_t col = get_col(env, irn);
469 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
471 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
472 if (col != not_col) {
473 if (!ci->tmp_fixed) {
478 list_add(&ci->changed_list, parent_changed);
482 /* The node has the color it should not have _and_ has not been visited yet. */
483 if (!color_is_fix(env, irn)) {
484 int n_regs = env->co->cls->n_regs;
485 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
487 /* Get the costs for giving the node a specific color. */
488 determine_color_costs(env, ci, csts);
490 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
491 csts[not_col].costs = INT_MAX;
493 /* sort the colors according costs, cheapest first. */
494 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
496 /* Try recoloring the node using the color list. */
497 res = recolor(env, irn, csts, parent_changed, depth);
500 /* If we came here, everything went ok. */
504 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
506 co2_irn_t *ci = get_co2_irn(env, irn);
507 col_t col = get_col(env, irn);
510 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
512 /* the node has the wanted color. That's fine, mark it as visited and return. */
513 if (col == tgt_col) {
514 if (!ci->tmp_fixed) {
517 list_add(&ci->changed_list, parent_changed);
524 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
525 int n_regs = env->co->cls->n_regs;
526 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
528 /* Get the costs for giving the node a specific color. */
529 single_color_cost(env, ci, tgt_col, seq);
531 /* Try recoloring the node using the color list. */
532 res = recolor(env, irn, seq, parent_changed, depth);
537 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
542 * Examine the costs of the current coloring concerning a MST subtree.
543 * @param ci The subtree root.
544 * @param col The color of @p ci.
545 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
547 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
549 int *front = FRONT_BASE(ci, col);
553 for (i = 0; i < ci->mst_n_childs; ++i) {
554 co2_cloud_irn_t *chld = ci->mst_childs[i];
555 col_t chld_col = front[i];
557 cost += examine_subtree_coloring(chld, chld_col);
558 cost += col != chld_col ? chld->mst_costs : 0;
565 * Determine color badnesses of a node.
566 * Badness means that it is unlikely that the node in question can
567 * obtain a color. The higher the badness, the more unlikely it is that
568 * the node can be assigned that color.
569 * @param ci The node.
570 * @param badness An integer array as long as there are registers.
571 * @note The array <code>badness</code> is not cleared.
573 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
575 co2_t *env = ci->cloud->env;
576 co2_irn_t *ir = &ci->inh;
577 int n_regs = env->n_regs;
578 be_ifg_t *ifg = env->co->cenv->ifg;
579 bitset_t *bs = bitset_alloca(n_regs);
581 neighbours_iter_t it;
583 admissible_colors(env, &ci->inh, bs);
584 bitset_foreach_clear(bs, elm)
585 badness[elm] = ci->costs;
587 /* Use constrained/fixed interfering neighbors to influence the color badness */
588 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
589 co2_irn_t *ni = get_co2_irn(env, irn);
591 admissible_colors(env, ni, bs);
592 if (bitset_popcount(bs) == 1) {
593 size_t c = bitset_next_set(bs, 0);
594 badness[c] += ci->costs;
597 else if (ni->fixed) {
598 col_t c = get_col(env, ni->irn);
599 badness[c] += ci->costs;
602 be_ifg_neighbours_break(&it);
606 * Determine the badness of a MST subtree.
607 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
608 * @see node_color_badness() for a definition of badness.
609 * @param ci The root of the subtree.
610 * @param depth Depth for debugging purposes.
612 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
614 co2_t *env = ci->cloud->env;
617 node_color_badness(ci, ci->color_badness);
619 /* Collect the color badness for the whole subtree */
620 for (i = 0; i < ci->mst_n_childs; ++i) {
621 co2_cloud_irn_t *child = ci->mst_childs[i];
622 determine_color_badness(child, depth + 1);
624 for (j = 0; j < env->n_regs; ++j)
625 ci->color_badness[j] += child->color_badness[j];
628 for (j = 0; j < env->n_regs; ++j)
629 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
633 * Unfix all nodes in a MST subtree.
635 static void unfix_subtree(co2_cloud_irn_t *ci)
640 for (i = 0; i < ci->mst_n_childs; ++i)
641 unfix_subtree(ci->mst_childs[i]);
644 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
646 co2_t *env = ci->cloud->env;
647 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
648 int is_root = ci->mst_parent == ci;
649 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
650 int min_badness = INT_MAX;
651 int best_col_costs = INT_MAX;
653 int n_regs = env->n_regs;
654 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
656 struct list_head changed;
659 for (i = 0; i < n_regs; ++i) {
660 int badness = ci->color_badness[i];
663 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
665 min_badness = MIN(min_badness, badness);
668 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
669 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
670 seq[parent_col].costs = min_badness - 1;
672 /* Sort the colors. The will be processed in that ordering. */
673 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
675 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
676 INIT_LIST_HEAD(&changed);
677 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
678 col_t col = seq[i].col;
679 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
681 int subtree_costs, sum_costs;
683 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
686 INIT_LIST_HEAD(&changed);
687 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
689 materialize_coloring(&changed);
696 for (j = 0; j < ci->mst_n_childs; ++j) {
697 co2_cloud_irn_t *child = ci->mst_childs[j];
698 ok = coalesce_top_down(child, j, depth + 1) >= 0;
700 child->inh.fixed = 1;
705 /* If the subtree could not be colored, we have to try another color. */
709 subtree_costs = examine_subtree_coloring(ci, col);
710 sum_costs = subtree_costs + add_cost;
711 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
713 if (sum_costs < best_col_costs) {
715 best_col_costs = sum_costs;
716 ci->col_costs[col] = subtree_costs;
724 int *front = FRONT_BASE(ci->mst_parent, parent_col);
725 front[child_nr] = best_col;
731 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
733 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
739 /* mark the node as visited and add it to the cloud. */
741 list_add(&ci->cloud_list, &cloud->members_head);
743 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
745 /* determine the nodes costs */
746 be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
747 co_gs_foreach_neighb(a, n) {
749 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
750 if (be_values_interfere(lv, a->irn, n->irn))
751 cloud->inevit += n->costs;
754 /* add the node's cost to the total costs of the cloud. */
756 cloud->costs += costs;
757 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
760 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
761 if (costs >= curr_costs) {
766 /* add all the neighbors of the node to the cloud. */
767 co_gs_foreach_neighb(a, n) {
768 affinity_node_t *an = get_affinity_info(env->co, n->irn);
770 populate_cloud(env, cloud, an, curr_costs);
774 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
776 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
779 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
780 memset(cloud, 0, sizeof(cloud[0]));
781 INIT_LIST_HEAD(&cloud->members_head);
782 INIT_LIST_HEAD(&cloud->list);
783 list_add(&cloud->list, &env->cloud_head);
784 cloud->best_costs = INT_MAX;
787 populate_cloud(env, cloud, a, 0);
788 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
790 /* Also allocate space for the node sequence and compute that sequence. */
791 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
794 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
796 cloud->seq[i++] = ci;
798 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
803 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
805 const ir_node *irn = ci->inh.irn;
806 int *front = FRONT_BASE(ci, col);
808 struct list_head changed;
810 INIT_LIST_HEAD(&changed);
812 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
813 change_color_single(ci->cloud->env, irn, col, &changed, depth);
814 materialize_coloring(&changed);
816 for (i = 0; i < ci->mst_n_childs; ++i) {
817 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
821 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
823 while (ci != ci->mst_parent)
829 static void process_cloud(co2_cloud_t *cloud)
831 co2_t *env = cloud->env;
832 int n_regs = env->n_regs;
834 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
841 /* Collect all edges in the cloud on an obstack and sort the increasingly */
842 obstack_init(&cloud->obst);
843 for (i = 0; i < cloud->n_memb; ++i) {
844 co2_cloud_irn_t *ci = cloud->seq[i];
846 co_gs_foreach_neighb(ci->inh.aff, n) {
847 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
848 if (ci->index < ni->index) {
853 obstack_grow(&cloud->obst, &e, sizeof(e));
858 edges = (edge_t*)obstack_finish(&cloud->obst);
859 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
861 /* Compute the maximum spanning tree using Kruskal/Union-Find */
862 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
863 for (i = 0; i < n_edges; ++i) {
864 edge_t *e = &edges[i];
865 co2_cloud_irn_t *rs = find_mst_root(e->src);
866 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
868 /* if the union/find roots are different */
870 int si = e->src->index;
871 int ti = e->tgt->index;
875 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
877 /* this edge is in the MST, so set it in the bitset. */
878 mst_edges[si * cloud->n_memb + ti] = e->costs;
879 mst_edges[ti * cloud->n_memb + si] = e->costs;
882 obstack_free(&cloud->obst, edges);
884 cloud->master->mst_parent = cloud->master;
885 cloud->mst_root = cloud->master;
886 q = new_pdeq1(cloud->master);
887 while (!pdeq_empty(q)) {
888 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
889 int ofs = ci->index * cloud->n_memb;
890 int end = ofs + cloud->n_memb;
893 ci->mst_n_childs = 0;
894 for (i = ofs; i < end; ++i) {
895 if (mst_edges[i] != 0) {
897 co2_cloud_irn_t *child = cloud->seq[i - ofs];
899 /* put the child to the worklist */
902 /* make ci the parent of the child and add the child to the children array of the parent */
903 child->mst_parent = ci;
904 child->mst_costs = mst_edges[i];
906 obstack_ptr_grow(&cloud->obst, child);
908 mst_edges[other * cloud->n_memb + ci->index] = 0;
913 obstack_ptr_grow(&cloud->obst, NULL);
914 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
920 DBG((env->dbg, LEVEL_3, "mst:\n"));
921 for (i = 0; i < cloud->n_memb; ++i) {
922 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
923 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
926 for (i = 0; i < cloud->n_memb; ++i) {
927 co2_cloud_irn_t *ci = cloud->seq[i];
928 int n_childs = ci->mst_n_childs;
931 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
932 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
933 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
934 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
936 for (j = 0; j < env->n_regs; j++)
937 ci->col_costs[j] = INT_MAX;
940 determine_color_badness(cloud->mst_root, 0);
941 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
942 unfix_subtree(cloud->mst_root);
943 apply_coloring(cloud->mst_root, best_col, 0);
945 /* The coloring should represent the one with the best costs. */
946 //materialize_coloring(&changed);
947 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
948 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
950 /* Fix all nodes in the cloud. */
951 for (i = 0; i < cloud->n_memb; ++i)
952 cloud->seq[i]->inh.fixed = 1;
954 /* Free all space used while optimizing this cloud. */
955 obstack_free(&cloud->obst, NULL);
958 static int cloud_costs(co2_cloud_t *cloud)
962 for (i = 0; i < cloud->n_memb; ++i) {
963 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
964 col_t col = get_col(cloud->env, ci->irn);
965 co_gs_foreach_neighb(ci->aff, n) {
966 col_t n_col = get_col(cloud->env, n->irn);
967 costs += col != n_col ? n->costs : 0;
974 static void writeback_colors(co2_t *env)
978 for (irn = env->touched; irn; irn = irn->touched_next) {
979 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
980 arch_set_irn_register((ir_node*)irn->irn, reg);
984 static void process(co2_t *env)
986 co2_cloud_t **clouds;
994 co_gs_foreach_aff_node(env->co, a) {
995 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1004 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1005 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1007 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1009 for (i = 0; i < n_clouds; ++i) {
1010 init_costs += cloud_costs(clouds[i]);
1012 /* Process the cloud. */
1013 process_cloud(clouds[i]);
1015 all_costs += clouds[i]->costs;
1016 final_costs += cloud_costs(clouds[i]);
1019 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1024 static int co_solve_heuristic_new(copy_opt_t *co)
1028 ir_nodemap_init(&env.map, co->irg);
1029 obstack_init(&env.obst);
1033 env.n_regs = co->cls->n_regs;
1034 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1035 be_put_allocatable_regs(co->irg, co->cls, env.allocatable_regs);
1036 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1037 INIT_LIST_HEAD(&env.cloud_head);
1041 writeback_colors(&env);
1042 obstack_free(&env.obst, NULL);
1043 ir_nodemap_destroy(&env.map);
1047 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1048 void be_init_copyheur2(void)
1050 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1051 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1052 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1053 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1055 static co_algo_info copyheur = {
1056 co_solve_heuristic_new, 0
1059 lc_opt_add_table(co2_grp, options);
1060 be_register_copyopt("heur2", ©heur);