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)) {
255 for (i = 0; i < n; ++i) {
256 if (rbitset_is_set(req->limited, i))
257 bitset_set(ci->adm_cache, i);
260 bitset_copy(ci->adm_cache, env->allocatable_regs);
264 return ci->adm_cache;
267 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
269 bitset_copy(bs, get_adm(env, ci));
273 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
275 bitset_t *bs = get_adm(env, ci);
276 return bitset_is_set(bs, col);
279 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
281 const arch_register_req_t *req = arch_get_irn_register_req(irn);
283 if (arch_register_req_is(req, limited)) {
284 unsigned n_regs = env->co->cls->n_regs;
285 unsigned n_constr = 0;
288 n_constr = rbitset_popcount(req->limited, n_regs);
289 for (i = 0; i < n_regs; ++i) {
290 if (rbitset_is_set(req->limited, i)) {
291 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
298 * Determine costs which shall indicate how cheap/expensive it is to try
299 * to assign a node some color.
300 * The costs are computed for all colors. INT_MAX means that it is impossible
301 * to give the node that specific color.
303 * @param env The co2 this pointer.
304 * @param irn The node.
305 * @param col_costs An array of colors x costs where the costs are written to.
307 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
309 const ir_node *irn = ci->irn;
310 be_ifg_t *ifg = env->co->cenv->ifg;
311 int n_regs = env->co->cls->n_regs;
312 affinity_node_t *a = ci->aff;
314 neighbours_iter_t it;
317 /* Put all forbidden colors into the aux bitset. */
318 bitset_t *const admissible = bitset_alloca(n_regs);
319 admissible_colors(env, ci, admissible);
321 for (i = 0; i < n_regs; ++i) {
322 col_costs[i].col = i;
323 col_costs[i].costs = 0;
327 co_gs_foreach_neighb(a, n) {
328 if (color_is_fix(env, n->irn)) {
329 col_t col = get_col(env, n->irn);
330 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
333 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
337 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
338 col_t col = get_col(env, pos);
339 if (color_is_fix(env, pos)) {
340 col_costs[col].costs = INT_MAX;
343 incur_constraint_costs(env, pos, col_costs, INT_MAX);
344 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
347 be_ifg_neighbours_break(&it);
349 /* Set the costs to infinity for each color which is not allowed at this node. */
350 bitset_foreach_clear(admissible, elm) {
351 col_costs[elm].costs = INT_MAX;
356 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
358 int n_regs = env->co->cls->n_regs;
361 for (i = 0; i < n_regs; ++i) {
363 seq[i].costs = INT_MAX;
367 assert(is_color_admissible(env, ci, col));
373 static void reject_coloring(struct list_head *h)
375 list_for_each_entry(co2_irn_t, pos, h, changed_list)
379 static void materialize_coloring(struct list_head *h)
381 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
382 pos->orig_col = pos->tmp_col;
387 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
389 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
391 int n_regs = env->co->cls->n_regs;
392 be_ifg_t *ifg = env->co->cenv->ifg;
393 co2_irn_t *ci = get_co2_irn(env, irn);
398 if (depth >= max_depth)
401 for (i = 0; i < n_regs; ++i) {
402 col_t tgt_col = col_list[i].col;
403 unsigned costs = col_list[i].costs;
406 struct list_head changed;
407 neighbours_iter_t it;
409 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
411 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
412 if (INFEASIBLE(costs)) {
413 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
418 /* Set the new color of the node and mark the node as temporarily fixed. */
419 ci->tmp_col = tgt_col;
423 If that color has costs > 0, there's at least one neighbor having that color,
424 so we will try to change the neighbors' colors, too.
426 INIT_LIST_HEAD(&changed);
427 list_add(&ci->changed_list, &changed);
429 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
431 /* try to re-color the neighbor if it has the target color. */
432 if (get_col(env, n) == tgt_col) {
433 struct list_head tmp;
436 Try to change the color of the neighbor and record all nodes which
437 get changed in the tmp list. Add this list to the "changed" list for
438 that color. If we did not succeed to change the color of the neighbor,
439 we bail out and try the next color.
441 INIT_LIST_HEAD(&tmp);
442 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
443 list_splice(&tmp, &changed);
448 be_ifg_neighbours_break(&it);
451 We managed to assign the target color to all neighbors, so from the perspective
452 of the current node, every thing was ok and we can return safely.
455 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
456 list_splice(&changed, parent_changed);
462 If not, that color did not succeed and we unfix all nodes we touched
463 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
466 reject_coloring(&changed);
472 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
474 co2_irn_t *ci = get_co2_irn(env, irn);
476 col_t col = get_col(env, irn);
478 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
480 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
481 if (col != not_col) {
482 if (!ci->tmp_fixed) {
487 list_add(&ci->changed_list, parent_changed);
491 /* The node has the color it should not have _and_ has not been visited yet. */
492 if (!color_is_fix(env, irn)) {
493 int n_regs = env->co->cls->n_regs;
494 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
496 /* Get the costs for giving the node a specific color. */
497 determine_color_costs(env, ci, csts);
499 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
500 csts[not_col].costs = INT_MAX;
502 /* sort the colors according costs, cheapest first. */
503 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
505 /* Try recoloring the node using the color list. */
506 res = recolor(env, irn, csts, parent_changed, depth);
509 /* If we came here, everything went ok. */
513 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
515 co2_irn_t *ci = get_co2_irn(env, irn);
516 col_t col = get_col(env, irn);
519 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
521 /* the node has the wanted color. That's fine, mark it as visited and return. */
522 if (col == tgt_col) {
523 if (!ci->tmp_fixed) {
526 list_add(&ci->changed_list, parent_changed);
533 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
534 int n_regs = env->co->cls->n_regs;
535 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
537 /* Get the costs for giving the node a specific color. */
538 single_color_cost(env, ci, tgt_col, seq);
540 /* Try recoloring the node using the color list. */
541 res = recolor(env, irn, seq, parent_changed, depth);
546 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
551 * Examine the costs of the current coloring concerning a MST subtree.
552 * @param ci The subtree root.
553 * @param col The color of @p ci.
554 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
556 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
558 int *front = FRONT_BASE(ci, col);
562 for (i = 0; i < ci->mst_n_childs; ++i) {
563 co2_cloud_irn_t *chld = ci->mst_childs[i];
564 col_t chld_col = front[i];
566 cost += examine_subtree_coloring(chld, chld_col);
567 cost += col != chld_col ? chld->mst_costs : 0;
574 * Determine color badnesses of a node.
575 * Badness means that it is unlikely that the node in question can
576 * obtain a color. The higher the badness, the more unlikely it is that
577 * the node can be assigned that color.
578 * @param ci The node.
579 * @param badness An integer array as long as there are registers.
580 * @note The array <code>badness</code> is not cleared.
582 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
584 co2_t *env = ci->cloud->env;
585 co2_irn_t *ir = &ci->inh;
586 int n_regs = env->n_regs;
587 be_ifg_t *ifg = env->co->cenv->ifg;
588 bitset_t *bs = bitset_alloca(n_regs);
590 neighbours_iter_t it;
592 admissible_colors(env, &ci->inh, bs);
593 bitset_foreach_clear(bs, elm)
594 badness[elm] = ci->costs;
596 /* Use constrained/fixed interfering neighbors to influence the color badness */
597 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
598 co2_irn_t *ni = get_co2_irn(env, irn);
600 admissible_colors(env, ni, bs);
601 if (bitset_popcount(bs) == 1) {
602 size_t c = bitset_next_set(bs, 0);
603 badness[c] += ci->costs;
606 else if (ni->fixed) {
607 col_t c = get_col(env, ni->irn);
608 badness[c] += ci->costs;
611 be_ifg_neighbours_break(&it);
615 * Determine the badness of a MST subtree.
616 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
617 * @see node_color_badness() for a definition of badness.
618 * @param ci The root of the subtree.
619 * @param depth Depth for debugging purposes.
621 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
623 co2_t *env = ci->cloud->env;
626 node_color_badness(ci, ci->color_badness);
628 /* Collect the color badness for the whole subtree */
629 for (i = 0; i < ci->mst_n_childs; ++i) {
630 co2_cloud_irn_t *child = ci->mst_childs[i];
631 determine_color_badness(child, depth + 1);
633 for (j = 0; j < env->n_regs; ++j)
634 ci->color_badness[j] += child->color_badness[j];
637 for (j = 0; j < env->n_regs; ++j)
638 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
642 * Unfix all nodes in a MST subtree.
644 static void unfix_subtree(co2_cloud_irn_t *ci)
649 for (i = 0; i < ci->mst_n_childs; ++i)
650 unfix_subtree(ci->mst_childs[i]);
653 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
655 co2_t *env = ci->cloud->env;
656 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
657 int is_root = ci->mst_parent == ci;
658 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
659 int min_badness = INT_MAX;
660 int best_col_costs = INT_MAX;
662 int n_regs = env->n_regs;
663 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
665 struct list_head changed;
668 for (i = 0; i < n_regs; ++i) {
669 int badness = ci->color_badness[i];
672 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
674 min_badness = MIN(min_badness, badness);
677 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
678 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
679 seq[parent_col].costs = min_badness - 1;
681 /* Sort the colors. The will be processed in that ordering. */
682 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
684 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
685 INIT_LIST_HEAD(&changed);
686 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
687 col_t col = seq[i].col;
688 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
690 int subtree_costs, sum_costs;
692 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
695 INIT_LIST_HEAD(&changed);
696 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
698 materialize_coloring(&changed);
705 for (j = 0; j < ci->mst_n_childs; ++j) {
706 co2_cloud_irn_t *child = ci->mst_childs[j];
707 ok = coalesce_top_down(child, j, depth + 1) >= 0;
709 child->inh.fixed = 1;
714 /* If the subtree could not be colored, we have to try another color. */
718 subtree_costs = examine_subtree_coloring(ci, col);
719 sum_costs = subtree_costs + add_cost;
720 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
722 if (sum_costs < best_col_costs) {
724 best_col_costs = sum_costs;
725 ci->col_costs[col] = subtree_costs;
733 int *front = FRONT_BASE(ci->mst_parent, parent_col);
734 front[child_nr] = best_col;
740 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
742 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
748 /* mark the node as visited and add it to the cloud. */
750 list_add(&ci->cloud_list, &cloud->members_head);
752 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
754 /* determine the nodes costs */
755 be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
756 co_gs_foreach_neighb(a, n) {
758 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
759 if (be_values_interfere(lv, a->irn, n->irn))
760 cloud->inevit += n->costs;
763 /* add the node's cost to the total costs of the cloud. */
765 cloud->costs += costs;
766 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
769 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
770 if (costs >= curr_costs) {
775 /* add all the neighbors of the node to the cloud. */
776 co_gs_foreach_neighb(a, n) {
777 affinity_node_t *an = get_affinity_info(env->co, n->irn);
779 populate_cloud(env, cloud, an, curr_costs);
783 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
785 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
788 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
789 memset(cloud, 0, sizeof(cloud[0]));
790 INIT_LIST_HEAD(&cloud->members_head);
791 INIT_LIST_HEAD(&cloud->list);
792 list_add(&cloud->list, &env->cloud_head);
793 cloud->best_costs = INT_MAX;
796 populate_cloud(env, cloud, a, 0);
797 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
799 /* Also allocate space for the node sequence and compute that sequence. */
800 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
803 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
805 cloud->seq[i++] = ci;
807 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
812 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
814 const ir_node *irn = ci->inh.irn;
815 int *front = FRONT_BASE(ci, col);
817 struct list_head changed;
819 INIT_LIST_HEAD(&changed);
821 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
822 change_color_single(ci->cloud->env, irn, col, &changed, depth);
823 materialize_coloring(&changed);
825 for (i = 0; i < ci->mst_n_childs; ++i) {
826 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
830 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
832 while (ci != ci->mst_parent)
838 static void process_cloud(co2_cloud_t *cloud)
840 co2_t *env = cloud->env;
841 int n_regs = env->n_regs;
843 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
850 /* Collect all edges in the cloud on an obstack and sort the increasingly */
851 obstack_init(&cloud->obst);
852 for (i = 0; i < cloud->n_memb; ++i) {
853 co2_cloud_irn_t *ci = cloud->seq[i];
855 co_gs_foreach_neighb(ci->inh.aff, n) {
856 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
857 if (ci->index < ni->index) {
862 obstack_grow(&cloud->obst, &e, sizeof(e));
867 edges = (edge_t*)obstack_finish(&cloud->obst);
868 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
870 /* Compute the maximum spanning tree using Kruskal/Union-Find */
871 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
872 for (i = 0; i < n_edges; ++i) {
873 edge_t *e = &edges[i];
874 co2_cloud_irn_t *rs = find_mst_root(e->src);
875 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
877 /* if the union/find roots are different */
879 int si = e->src->index;
880 int ti = e->tgt->index;
884 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
886 /* this edge is in the MST, so set it in the bitset. */
887 mst_edges[si * cloud->n_memb + ti] = e->costs;
888 mst_edges[ti * cloud->n_memb + si] = e->costs;
891 obstack_free(&cloud->obst, edges);
893 cloud->master->mst_parent = cloud->master;
894 cloud->mst_root = cloud->master;
895 q = new_pdeq1(cloud->master);
896 while (!pdeq_empty(q)) {
897 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
898 int ofs = ci->index * cloud->n_memb;
899 int end = ofs + cloud->n_memb;
902 ci->mst_n_childs = 0;
903 for (i = ofs; i < end; ++i) {
904 if (mst_edges[i] != 0) {
906 co2_cloud_irn_t *child = cloud->seq[i - ofs];
908 /* put the child to the worklist */
911 /* make ci the parent of the child and add the child to the children array of the parent */
912 child->mst_parent = ci;
913 child->mst_costs = mst_edges[i];
915 obstack_ptr_grow(&cloud->obst, child);
917 mst_edges[other * cloud->n_memb + ci->index] = 0;
922 obstack_ptr_grow(&cloud->obst, NULL);
923 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
929 DBG((env->dbg, LEVEL_3, "mst:\n"));
930 for (i = 0; i < cloud->n_memb; ++i) {
931 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
932 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
935 for (i = 0; i < cloud->n_memb; ++i) {
936 co2_cloud_irn_t *ci = cloud->seq[i];
937 int n_childs = ci->mst_n_childs;
940 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
941 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
942 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
943 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
945 for (j = 0; j < env->n_regs; j++)
946 ci->col_costs[j] = INT_MAX;
949 determine_color_badness(cloud->mst_root, 0);
950 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
951 unfix_subtree(cloud->mst_root);
952 apply_coloring(cloud->mst_root, best_col, 0);
954 /* The coloring should represent the one with the best costs. */
955 //materialize_coloring(&changed);
956 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
957 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
959 /* Fix all nodes in the cloud. */
960 for (i = 0; i < cloud->n_memb; ++i)
961 cloud->seq[i]->inh.fixed = 1;
963 /* Free all space used while optimizing this cloud. */
964 obstack_free(&cloud->obst, NULL);
967 static int cloud_costs(co2_cloud_t *cloud)
971 for (i = 0; i < cloud->n_memb; ++i) {
972 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
973 col_t col = get_col(cloud->env, ci->irn);
974 co_gs_foreach_neighb(ci->aff, n) {
975 col_t n_col = get_col(cloud->env, n->irn);
976 costs += col != n_col ? n->costs : 0;
983 static void writeback_colors(co2_t *env)
987 for (irn = env->touched; irn; irn = irn->touched_next) {
988 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
989 arch_set_irn_register((ir_node*)irn->irn, reg);
993 static void process(co2_t *env)
995 co2_cloud_t **clouds;
1000 int final_costs = 0;
1003 co_gs_foreach_aff_node(env->co, a) {
1004 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1013 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1014 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1016 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1018 for (i = 0; i < n_clouds; ++i) {
1019 init_costs += cloud_costs(clouds[i]);
1021 /* Process the cloud. */
1022 process_cloud(clouds[i]);
1024 all_costs += clouds[i]->costs;
1025 final_costs += cloud_costs(clouds[i]);
1028 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1033 static int co_solve_heuristic_new(copy_opt_t *co)
1037 ir_nodemap_init(&env.map, co->irg);
1038 obstack_init(&env.obst);
1042 env.n_regs = co->cls->n_regs;
1043 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1044 be_put_allocatable_regs(co->irg, co->cls, env.allocatable_regs);
1045 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1046 INIT_LIST_HEAD(&env.cloud_head);
1050 writeback_colors(&env);
1051 obstack_free(&env.obst, NULL);
1052 ir_nodemap_destroy(&env.map);
1056 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1057 void be_init_copyheur2(void)
1059 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1060 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1061 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1062 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1064 static co_algo_info copyheur = {
1065 co_solve_heuristic_new, 0
1068 lc_opt_add_table(co2_grp, options);
1069 be_register_copyopt("heur2", ©heur);