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 unsigned const *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;
114 unsigned const *admissible;
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 arch_register_req_t const *const req = arch_get_irn_register_req(node);
176 ci->admissible = arch_register_req_is(req, limited) ? req->limited : env->allocatable_regs;
178 ir_nodemap_insert(&env->map, node, ci);
183 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
185 co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
187 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
189 INIT_LIST_HEAD(&ci->inh.changed_list);
190 ci->inh.touched_next = env->touched;
191 ci->inh.orig_col = get_irn_col(node);
192 env->touched = &ci->inh;
194 ci->inh.aff = get_affinity_info(env->co, node);
196 INIT_LIST_HEAD(&ci->cloud_list);
199 ir_nodemap_insert(&env->map, node, ci);
204 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
206 static int cmp_clouds_gt(const void *a, const void *b)
208 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
209 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
210 double c = CLOUD_WEIGHT(*p);
211 double d = CLOUD_WEIGHT(*q);
212 return QSORT_CMP(d, c);
216 * An order on color/costs pairs.
217 * If the costs are equal, we use the color as a kind of normalization.
219 static int col_cost_pair_lt(const void *a, const void *b)
221 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
222 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
225 return QSORT_CMP(c, d);
228 static int cmp_edges(const void *a, const void *b)
230 const edge_t *p = (const edge_t*)a;
231 const edge_t *q = (const edge_t*)b;
232 return QSORT_CMP(q->costs, p->costs);
235 static col_t get_col(co2_t *env, const ir_node *irn)
237 co2_irn_t *ci = get_co2_irn(env, irn);
238 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
241 static inline int color_is_fix(co2_t *env, const ir_node *irn)
243 co2_irn_t *ci = get_co2_irn(env, irn);
244 return ci->fixed || ci->tmp_fixed;
247 static inline int is_color_admissible(co2_irn_t *const ci, col_t const col)
249 unsigned const *const bs = ci->admissible;
250 return rbitset_is_set(bs, col);
253 static void incur_constraint_costs(ir_node const *const irn, col_cost_pair_t *const col_costs, int const costs)
255 const arch_register_req_t *req = arch_get_irn_register_req(irn);
257 if (arch_register_req_is(req, limited)) {
258 unsigned const n_regs = req->cls->n_regs;
259 unsigned const n_constr = rbitset_popcount(req->limited, n_regs);
260 for (unsigned i = 0; i < n_regs; ++i) {
261 if (rbitset_is_set(req->limited, i)) {
262 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
269 * Determine costs which shall indicate how cheap/expensive it is to try
270 * to assign a node some color.
271 * The costs are computed for all colors. INT_MAX means that it is impossible
272 * to give the node that specific color.
274 * @param env The co2 this pointer.
275 * @param irn The node.
276 * @param col_costs An array of colors x costs where the costs are written to.
278 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
280 const ir_node *irn = ci->irn;
281 be_ifg_t *ifg = env->co->cenv->ifg;
282 int n_regs = env->co->cls->n_regs;
283 affinity_node_t *a = ci->aff;
285 neighbours_iter_t it;
288 for (i = 0; i < n_regs; ++i) {
289 col_costs[i].col = i;
290 col_costs[i].costs = 0;
294 co_gs_foreach_neighb(a, n) {
295 if (color_is_fix(env, n->irn)) {
296 col_t col = get_col(env, n->irn);
297 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
300 incur_constraint_costs(n->irn, col_costs, -n->costs);
304 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
305 col_t col = get_col(env, pos);
306 if (color_is_fix(env, pos)) {
307 col_costs[col].costs = INT_MAX;
310 incur_constraint_costs(pos, col_costs, INT_MAX);
311 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
314 be_ifg_neighbours_break(&it);
316 /* Set the costs to infinity for each color which is not allowed at this node. */
317 unsigned const *const admissible = ci->admissible;
318 rbitset_foreach_clear(admissible, n_regs, elm) {
319 col_costs[elm].costs = INT_MAX;
323 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
325 int n_regs = env->co->cls->n_regs;
328 for (i = 0; i < n_regs; ++i) {
330 seq[i].costs = INT_MAX;
334 assert(is_color_admissible(ci, col));
340 static void reject_coloring(struct list_head *h)
342 list_for_each_entry(co2_irn_t, pos, h, changed_list)
346 static void materialize_coloring(struct list_head *h)
348 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
349 pos->orig_col = pos->tmp_col;
354 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
356 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
358 int n_regs = env->co->cls->n_regs;
359 be_ifg_t *ifg = env->co->cenv->ifg;
360 co2_irn_t *ci = get_co2_irn(env, irn);
365 if (depth >= max_depth)
368 for (i = 0; i < n_regs; ++i) {
369 col_t tgt_col = col_list[i].col;
370 unsigned costs = col_list[i].costs;
373 struct list_head changed;
374 neighbours_iter_t it;
376 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
378 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
379 if (INFEASIBLE(costs)) {
380 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
385 /* Set the new color of the node and mark the node as temporarily fixed. */
386 ci->tmp_col = tgt_col;
390 If that color has costs > 0, there's at least one neighbor having that color,
391 so we will try to change the neighbors' colors, too.
393 INIT_LIST_HEAD(&changed);
394 list_add(&ci->changed_list, &changed);
396 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
398 /* try to re-color the neighbor if it has the target color. */
399 if (get_col(env, n) == tgt_col) {
400 struct list_head tmp;
403 Try to change the color of the neighbor and record all nodes which
404 get changed in the tmp list. Add this list to the "changed" list for
405 that color. If we did not succeed to change the color of the neighbor,
406 we bail out and try the next color.
408 INIT_LIST_HEAD(&tmp);
409 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
410 list_splice(&tmp, &changed);
415 be_ifg_neighbours_break(&it);
418 We managed to assign the target color to all neighbors, so from the perspective
419 of the current node, every thing was ok and we can return safely.
422 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
423 list_splice(&changed, parent_changed);
429 If not, that color did not succeed and we unfix all nodes we touched
430 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
433 reject_coloring(&changed);
439 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
441 co2_irn_t *ci = get_co2_irn(env, irn);
443 col_t col = get_col(env, irn);
445 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
447 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
448 if (col != not_col) {
449 if (!ci->tmp_fixed) {
454 list_add(&ci->changed_list, parent_changed);
458 /* The node has the color it should not have _and_ has not been visited yet. */
459 if (!color_is_fix(env, irn)) {
460 int n_regs = env->co->cls->n_regs;
461 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
463 /* Get the costs for giving the node a specific color. */
464 determine_color_costs(env, ci, csts);
466 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
467 csts[not_col].costs = INT_MAX;
469 /* sort the colors according costs, cheapest first. */
470 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
472 /* Try recoloring the node using the color list. */
473 res = recolor(env, irn, csts, parent_changed, depth);
476 /* If we came here, everything went ok. */
480 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
482 co2_irn_t *ci = get_co2_irn(env, irn);
483 col_t col = get_col(env, irn);
486 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
488 /* the node has the wanted color. That's fine, mark it as visited and return. */
489 if (col == tgt_col) {
490 if (!ci->tmp_fixed) {
493 list_add(&ci->changed_list, parent_changed);
500 if (!color_is_fix(env, irn) && is_color_admissible(ci, tgt_col)) {
501 int n_regs = env->co->cls->n_regs;
502 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
504 /* Get the costs for giving the node a specific color. */
505 single_color_cost(env, ci, tgt_col, seq);
507 /* Try recoloring the node using the color list. */
508 res = recolor(env, irn, seq, parent_changed, depth);
513 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
518 * Examine the costs of the current coloring concerning a MST subtree.
519 * @param ci The subtree root.
520 * @param col The color of @p ci.
521 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
523 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
525 int *front = FRONT_BASE(ci, col);
529 for (i = 0; i < ci->mst_n_childs; ++i) {
530 co2_cloud_irn_t *chld = ci->mst_childs[i];
531 col_t chld_col = front[i];
533 cost += examine_subtree_coloring(chld, chld_col);
534 cost += col != chld_col ? chld->mst_costs : 0;
541 * Determine color badnesses of a node.
542 * Badness means that it is unlikely that the node in question can
543 * obtain a color. The higher the badness, the more unlikely it is that
544 * the node can be assigned that color.
545 * @param ci The node.
546 * @param badness An integer array as long as there are registers.
547 * @note The array <code>badness</code> is not cleared.
549 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
551 co2_t *const env = ci->cloud->env;
552 size_t const n_regs = env->n_regs;
554 neighbours_iter_t it;
557 unsigned const *const bs = ci->inh.admissible;
558 rbitset_foreach_clear(bs, n_regs, elm)
559 badness[elm] = ci->costs;
562 /* Use constrained/fixed interfering neighbors to influence the color badness */
563 be_ifg_foreach_neighbour(env->co->cenv->ifg, &it, ci->inh.irn, irn) {
564 co2_irn_t *ni = get_co2_irn(env, irn);
566 unsigned const *const bs = ni->admissible;
567 if (rbitset_popcount(bs, n_regs) == 1) {
568 size_t const c = rbitset_next_max(bs, 0, n_regs, true);
569 badness[c] += ci->costs;
570 } else if (ni->fixed) {
571 col_t c = get_col(env, ni->irn);
572 badness[c] += ci->costs;
575 be_ifg_neighbours_break(&it);
579 * Determine the badness of a MST subtree.
580 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
581 * @see node_color_badness() for a definition of badness.
582 * @param ci The root of the subtree.
583 * @param depth Depth for debugging purposes.
585 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
587 co2_t *env = ci->cloud->env;
590 node_color_badness(ci, ci->color_badness);
592 /* Collect the color badness for the whole subtree */
593 for (i = 0; i < ci->mst_n_childs; ++i) {
594 co2_cloud_irn_t *child = ci->mst_childs[i];
595 determine_color_badness(child, depth + 1);
597 for (j = 0; j < env->n_regs; ++j)
598 ci->color_badness[j] += child->color_badness[j];
601 for (j = 0; j < env->n_regs; ++j)
602 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
606 * Unfix all nodes in a MST subtree.
608 static void unfix_subtree(co2_cloud_irn_t *ci)
613 for (i = 0; i < ci->mst_n_childs; ++i)
614 unfix_subtree(ci->mst_childs[i]);
617 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
619 co2_t *env = ci->cloud->env;
620 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
621 int is_root = ci->mst_parent == ci;
622 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
623 int min_badness = INT_MAX;
624 int best_col_costs = INT_MAX;
626 int n_regs = env->n_regs;
627 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
629 struct list_head changed;
632 for (i = 0; i < n_regs; ++i) {
633 int badness = ci->color_badness[i];
636 seq[i].costs = is_color_admissible(&ci->inh, i) ? badness : INT_MAX;
638 min_badness = MIN(min_badness, badness);
641 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
642 if (!is_root && is_color_admissible(&ci->inh, parent_col))
643 seq[parent_col].costs = min_badness - 1;
645 /* Sort the colors. The will be processed in that ordering. */
646 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
648 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
649 INIT_LIST_HEAD(&changed);
650 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
651 col_t col = seq[i].col;
652 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
654 int subtree_costs, sum_costs;
656 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
659 INIT_LIST_HEAD(&changed);
660 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
662 materialize_coloring(&changed);
669 for (j = 0; j < ci->mst_n_childs; ++j) {
670 co2_cloud_irn_t *child = ci->mst_childs[j];
671 ok = coalesce_top_down(child, j, depth + 1) >= 0;
673 child->inh.fixed = 1;
678 /* If the subtree could not be colored, we have to try another color. */
682 subtree_costs = examine_subtree_coloring(ci, col);
683 sum_costs = subtree_costs + add_cost;
684 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
686 if (sum_costs < best_col_costs) {
688 best_col_costs = sum_costs;
689 ci->col_costs[col] = subtree_costs;
697 int *front = FRONT_BASE(ci->mst_parent, parent_col);
698 front[child_nr] = best_col;
704 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
706 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
712 /* mark the node as visited and add it to the cloud. */
714 list_add(&ci->cloud_list, &cloud->members_head);
716 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
718 /* determine the nodes costs */
719 be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
720 co_gs_foreach_neighb(a, n) {
722 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
723 if (be_values_interfere(lv, a->irn, n->irn))
724 cloud->inevit += n->costs;
727 /* add the node's cost to the total costs of the cloud. */
729 cloud->costs += costs;
730 cloud->freedom += rbitset_popcount(ci->inh.admissible, env->n_regs);
733 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
734 if (costs >= curr_costs) {
739 /* add all the neighbors of the node to the cloud. */
740 co_gs_foreach_neighb(a, n) {
741 affinity_node_t *an = get_affinity_info(env->co, n->irn);
743 populate_cloud(env, cloud, an, curr_costs);
747 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
749 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
752 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
753 memset(cloud, 0, sizeof(cloud[0]));
754 INIT_LIST_HEAD(&cloud->members_head);
755 INIT_LIST_HEAD(&cloud->list);
756 list_add(&cloud->list, &env->cloud_head);
757 cloud->best_costs = INT_MAX;
760 populate_cloud(env, cloud, a, 0);
761 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
763 /* Also allocate space for the node sequence and compute that sequence. */
764 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
767 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
769 cloud->seq[i++] = ci;
771 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
776 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
778 const ir_node *irn = ci->inh.irn;
779 int *front = FRONT_BASE(ci, col);
781 struct list_head changed;
783 INIT_LIST_HEAD(&changed);
785 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
786 change_color_single(ci->cloud->env, irn, col, &changed, depth);
787 materialize_coloring(&changed);
789 for (i = 0; i < ci->mst_n_childs; ++i) {
790 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
794 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
796 while (ci != ci->mst_parent)
802 static void process_cloud(co2_cloud_t *cloud)
804 co2_t *env = cloud->env;
805 int n_regs = env->n_regs;
807 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
814 /* Collect all edges in the cloud on an obstack and sort the increasingly */
815 obstack_init(&cloud->obst);
816 for (i = 0; i < cloud->n_memb; ++i) {
817 co2_cloud_irn_t *ci = cloud->seq[i];
819 co_gs_foreach_neighb(ci->inh.aff, n) {
820 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
821 if (ci->index < ni->index) {
826 obstack_grow(&cloud->obst, &e, sizeof(e));
831 edges = (edge_t*)obstack_finish(&cloud->obst);
832 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
834 /* Compute the maximum spanning tree using Kruskal/Union-Find */
835 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
836 for (i = 0; i < n_edges; ++i) {
837 edge_t *e = &edges[i];
838 co2_cloud_irn_t *rs = find_mst_root(e->src);
839 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
841 /* if the union/find roots are different */
843 int si = e->src->index;
844 int ti = e->tgt->index;
848 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
850 /* this edge is in the MST, so set it in the bitset. */
851 mst_edges[si * cloud->n_memb + ti] = e->costs;
852 mst_edges[ti * cloud->n_memb + si] = e->costs;
855 obstack_free(&cloud->obst, edges);
857 cloud->master->mst_parent = cloud->master;
858 cloud->mst_root = cloud->master;
859 q = new_pdeq1(cloud->master);
860 while (!pdeq_empty(q)) {
861 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
862 int ofs = ci->index * cloud->n_memb;
863 int end = ofs + cloud->n_memb;
866 ci->mst_n_childs = 0;
867 for (i = ofs; i < end; ++i) {
868 if (mst_edges[i] != 0) {
870 co2_cloud_irn_t *child = cloud->seq[i - ofs];
872 /* put the child to the worklist */
875 /* make ci the parent of the child and add the child to the children array of the parent */
876 child->mst_parent = ci;
877 child->mst_costs = mst_edges[i];
879 obstack_ptr_grow(&cloud->obst, child);
881 mst_edges[other * cloud->n_memb + ci->index] = 0;
886 obstack_ptr_grow(&cloud->obst, NULL);
887 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
893 DBG((env->dbg, LEVEL_3, "mst:\n"));
894 for (i = 0; i < cloud->n_memb; ++i) {
895 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
896 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
899 for (i = 0; i < cloud->n_memb; ++i) {
900 co2_cloud_irn_t *ci = cloud->seq[i];
901 int n_childs = ci->mst_n_childs;
904 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
905 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
906 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
907 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
909 for (j = 0; j < env->n_regs; j++)
910 ci->col_costs[j] = INT_MAX;
913 determine_color_badness(cloud->mst_root, 0);
914 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
915 unfix_subtree(cloud->mst_root);
916 apply_coloring(cloud->mst_root, best_col, 0);
918 /* The coloring should represent the one with the best costs. */
919 //materialize_coloring(&changed);
920 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
921 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
923 /* Fix all nodes in the cloud. */
924 for (i = 0; i < cloud->n_memb; ++i)
925 cloud->seq[i]->inh.fixed = 1;
927 /* Free all space used while optimizing this cloud. */
928 obstack_free(&cloud->obst, NULL);
931 static int cloud_costs(co2_cloud_t *cloud)
935 for (i = 0; i < cloud->n_memb; ++i) {
936 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
937 col_t col = get_col(cloud->env, ci->irn);
938 co_gs_foreach_neighb(ci->aff, n) {
939 col_t n_col = get_col(cloud->env, n->irn);
940 costs += col != n_col ? n->costs : 0;
947 static void writeback_colors(co2_t *env)
951 for (irn = env->touched; irn; irn = irn->touched_next) {
952 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
953 arch_set_irn_register((ir_node*)irn->irn, reg);
957 static void process(co2_t *env)
959 co2_cloud_t **clouds;
967 co_gs_foreach_aff_node(env->co, a) {
968 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
977 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
978 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
980 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
982 for (i = 0; i < n_clouds; ++i) {
983 init_costs += cloud_costs(clouds[i]);
985 /* Process the cloud. */
986 process_cloud(clouds[i]);
988 all_costs += clouds[i]->costs;
989 final_costs += cloud_costs(clouds[i]);
992 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
997 static int co_solve_heuristic_new(copy_opt_t *co)
1001 ir_nodemap_init(&env.map, co->irg);
1002 obstack_init(&env.obst);
1006 env.n_regs = co->cls->n_regs;
1007 env.allocatable_regs = co->cenv->allocatable_regs->data;
1008 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1009 INIT_LIST_HEAD(&env.cloud_head);
1013 writeback_colors(&env);
1014 obstack_free(&env.obst, NULL);
1015 ir_nodemap_destroy(&env.map);
1019 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1020 void be_init_copyheur2(void)
1022 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1023 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1024 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1025 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1027 static co_algo_info copyheur = {
1028 co_solve_heuristic_new, 0
1031 lc_opt_add_table(co2_grp, options);
1032 be_register_copyopt("heur2", ©heur);