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));
315 /* Set the costs to infinity for each color which is not allowed at this node. */
316 unsigned const *const admissible = ci->admissible;
317 rbitset_foreach_clear(admissible, n_regs, elm) {
318 col_costs[elm].costs = INT_MAX;
322 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
324 int n_regs = env->co->cls->n_regs;
327 for (i = 0; i < n_regs; ++i) {
329 seq[i].costs = INT_MAX;
333 assert(is_color_admissible(ci, col));
339 static void reject_coloring(struct list_head *h)
341 list_for_each_entry(co2_irn_t, pos, h, changed_list)
345 static void materialize_coloring(struct list_head *h)
347 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
348 pos->orig_col = pos->tmp_col;
353 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
355 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
357 int n_regs = env->co->cls->n_regs;
358 be_ifg_t *ifg = env->co->cenv->ifg;
359 co2_irn_t *ci = get_co2_irn(env, irn);
364 if (depth >= max_depth)
367 for (i = 0; i < n_regs; ++i) {
368 col_t tgt_col = col_list[i].col;
369 unsigned costs = col_list[i].costs;
372 struct list_head changed;
373 neighbours_iter_t it;
375 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
377 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
378 if (INFEASIBLE(costs)) {
379 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
384 /* Set the new color of the node and mark the node as temporarily fixed. */
385 ci->tmp_col = tgt_col;
389 If that color has costs > 0, there's at least one neighbor having that color,
390 so we will try to change the neighbors' colors, too.
392 INIT_LIST_HEAD(&changed);
393 list_add(&ci->changed_list, &changed);
395 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
397 /* try to re-color the neighbor if it has the target color. */
398 if (get_col(env, n) == tgt_col) {
399 struct list_head tmp;
402 Try to change the color of the neighbor and record all nodes which
403 get changed in the tmp list. Add this list to the "changed" list for
404 that color. If we did not succeed to change the color of the neighbor,
405 we bail out and try the next color.
407 INIT_LIST_HEAD(&tmp);
408 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
409 list_splice(&tmp, &changed);
411 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;
578 * Determine the badness of a MST subtree.
579 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
580 * @see node_color_badness() for a definition of badness.
581 * @param ci The root of the subtree.
582 * @param depth Depth for debugging purposes.
584 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
586 co2_t *env = ci->cloud->env;
589 node_color_badness(ci, ci->color_badness);
591 /* Collect the color badness for the whole subtree */
592 for (i = 0; i < ci->mst_n_childs; ++i) {
593 co2_cloud_irn_t *child = ci->mst_childs[i];
594 determine_color_badness(child, depth + 1);
596 for (j = 0; j < env->n_regs; ++j)
597 ci->color_badness[j] += child->color_badness[j];
600 for (j = 0; j < env->n_regs; ++j)
601 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
605 * Unfix all nodes in a MST subtree.
607 static void unfix_subtree(co2_cloud_irn_t *ci)
612 for (i = 0; i < ci->mst_n_childs; ++i)
613 unfix_subtree(ci->mst_childs[i]);
616 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
618 co2_t *env = ci->cloud->env;
619 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
620 int is_root = ci->mst_parent == ci;
621 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
622 int min_badness = INT_MAX;
623 int best_col_costs = INT_MAX;
625 int n_regs = env->n_regs;
626 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
628 struct list_head changed;
631 for (i = 0; i < n_regs; ++i) {
632 int badness = ci->color_badness[i];
635 seq[i].costs = is_color_admissible(&ci->inh, i) ? badness : INT_MAX;
637 min_badness = MIN(min_badness, badness);
640 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
641 if (!is_root && is_color_admissible(&ci->inh, parent_col))
642 seq[parent_col].costs = min_badness - 1;
644 /* Sort the colors. The will be processed in that ordering. */
645 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
647 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
648 INIT_LIST_HEAD(&changed);
649 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
650 col_t col = seq[i].col;
651 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
653 int subtree_costs, sum_costs;
655 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
658 INIT_LIST_HEAD(&changed);
659 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
661 materialize_coloring(&changed);
668 for (j = 0; j < ci->mst_n_childs; ++j) {
669 co2_cloud_irn_t *child = ci->mst_childs[j];
670 ok = coalesce_top_down(child, j, depth + 1) >= 0;
672 child->inh.fixed = 1;
677 /* If the subtree could not be colored, we have to try another color. */
681 subtree_costs = examine_subtree_coloring(ci, col);
682 sum_costs = subtree_costs + add_cost;
683 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
685 if (sum_costs < best_col_costs) {
687 best_col_costs = sum_costs;
688 ci->col_costs[col] = subtree_costs;
696 int *front = FRONT_BASE(ci->mst_parent, parent_col);
697 front[child_nr] = best_col;
703 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
705 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
711 /* mark the node as visited and add it to the cloud. */
713 list_add(&ci->cloud_list, &cloud->members_head);
715 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
717 /* determine the nodes costs */
718 be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
719 co_gs_foreach_neighb(a, n) {
721 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
722 if (be_values_interfere(lv, a->irn, n->irn))
723 cloud->inevit += n->costs;
726 /* add the node's cost to the total costs of the cloud. */
728 cloud->costs += costs;
729 cloud->freedom += rbitset_popcount(ci->inh.admissible, env->n_regs);
732 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
733 if (costs >= curr_costs) {
738 /* add all the neighbors of the node to the cloud. */
739 co_gs_foreach_neighb(a, n) {
740 affinity_node_t *an = get_affinity_info(env->co, n->irn);
742 populate_cloud(env, cloud, an, curr_costs);
746 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
748 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
751 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
752 memset(cloud, 0, sizeof(cloud[0]));
753 INIT_LIST_HEAD(&cloud->members_head);
754 INIT_LIST_HEAD(&cloud->list);
755 list_add(&cloud->list, &env->cloud_head);
756 cloud->best_costs = INT_MAX;
759 populate_cloud(env, cloud, a, 0);
760 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
762 /* Also allocate space for the node sequence and compute that sequence. */
763 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
766 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
768 cloud->seq[i++] = ci;
770 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
775 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
777 const ir_node *irn = ci->inh.irn;
778 int *front = FRONT_BASE(ci, col);
780 struct list_head changed;
782 INIT_LIST_HEAD(&changed);
784 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
785 change_color_single(ci->cloud->env, irn, col, &changed, depth);
786 materialize_coloring(&changed);
788 for (i = 0; i < ci->mst_n_childs; ++i) {
789 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
793 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
795 while (ci != ci->mst_parent)
801 static void process_cloud(co2_cloud_t *cloud)
803 co2_t *env = cloud->env;
804 int n_regs = env->n_regs;
806 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
813 /* Collect all edges in the cloud on an obstack and sort the increasingly */
814 obstack_init(&cloud->obst);
815 for (i = 0; i < cloud->n_memb; ++i) {
816 co2_cloud_irn_t *ci = cloud->seq[i];
818 co_gs_foreach_neighb(ci->inh.aff, n) {
819 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
820 if (ci->index < ni->index) {
825 obstack_grow(&cloud->obst, &e, sizeof(e));
830 edges = (edge_t*)obstack_finish(&cloud->obst);
831 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
833 /* Compute the maximum spanning tree using Kruskal/Union-Find */
834 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
835 for (i = 0; i < n_edges; ++i) {
836 edge_t *e = &edges[i];
837 co2_cloud_irn_t *rs = find_mst_root(e->src);
838 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
840 /* if the union/find roots are different */
842 int si = e->src->index;
843 int ti = e->tgt->index;
847 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
849 /* this edge is in the MST, so set it in the bitset. */
850 mst_edges[si * cloud->n_memb + ti] = e->costs;
851 mst_edges[ti * cloud->n_memb + si] = e->costs;
854 obstack_free(&cloud->obst, edges);
856 cloud->master->mst_parent = cloud->master;
857 cloud->mst_root = cloud->master;
858 q = new_pdeq1(cloud->master);
859 while (!pdeq_empty(q)) {
860 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
861 int ofs = ci->index * cloud->n_memb;
862 int end = ofs + cloud->n_memb;
865 ci->mst_n_childs = 0;
866 for (i = ofs; i < end; ++i) {
867 if (mst_edges[i] != 0) {
869 co2_cloud_irn_t *child = cloud->seq[i - ofs];
871 /* put the child to the worklist */
874 /* make ci the parent of the child and add the child to the children array of the parent */
875 child->mst_parent = ci;
876 child->mst_costs = mst_edges[i];
878 obstack_ptr_grow(&cloud->obst, child);
880 mst_edges[other * cloud->n_memb + ci->index] = 0;
885 obstack_ptr_grow(&cloud->obst, NULL);
886 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
892 DBG((env->dbg, LEVEL_3, "mst:\n"));
893 for (i = 0; i < cloud->n_memb; ++i) {
894 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
895 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
898 for (i = 0; i < cloud->n_memb; ++i) {
899 co2_cloud_irn_t *ci = cloud->seq[i];
900 int n_childs = ci->mst_n_childs;
903 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
904 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
905 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
906 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
908 for (j = 0; j < env->n_regs; j++)
909 ci->col_costs[j] = INT_MAX;
912 determine_color_badness(cloud->mst_root, 0);
913 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
914 unfix_subtree(cloud->mst_root);
915 apply_coloring(cloud->mst_root, best_col, 0);
917 /* The coloring should represent the one with the best costs. */
918 //materialize_coloring(&changed);
919 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
920 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
922 /* Fix all nodes in the cloud. */
923 for (i = 0; i < cloud->n_memb; ++i)
924 cloud->seq[i]->inh.fixed = 1;
926 /* Free all space used while optimizing this cloud. */
927 obstack_free(&cloud->obst, NULL);
930 static int cloud_costs(co2_cloud_t *cloud)
934 for (i = 0; i < cloud->n_memb; ++i) {
935 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
936 col_t col = get_col(cloud->env, ci->irn);
937 co_gs_foreach_neighb(ci->aff, n) {
938 col_t n_col = get_col(cloud->env, n->irn);
939 costs += col != n_col ? n->costs : 0;
946 static void writeback_colors(co2_t *env)
950 for (irn = env->touched; irn; irn = irn->touched_next) {
951 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
952 arch_set_irn_register((ir_node*)irn->irn, reg);
956 static void process(co2_t *env)
958 co2_cloud_t **clouds;
966 co_gs_foreach_aff_node(env->co, a) {
967 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
976 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
977 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
979 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
981 for (i = 0; i < n_clouds; ++i) {
982 init_costs += cloud_costs(clouds[i]);
984 /* Process the cloud. */
985 process_cloud(clouds[i]);
987 all_costs += clouds[i]->costs;
988 final_costs += cloud_costs(clouds[i]);
991 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
996 static int co_solve_heuristic_new(copy_opt_t *co)
1000 ir_nodemap_init(&env.map, co->irg);
1001 obstack_init(&env.obst);
1005 env.n_regs = co->cls->n_regs;
1006 env.allocatable_regs = co->cenv->allocatable_regs->data;
1007 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1008 INIT_LIST_HEAD(&env.cloud_head);
1012 writeback_colors(&env);
1013 obstack_free(&env.obst, NULL);
1014 ir_nodemap_destroy(&env.map);
1018 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1019 void be_init_copyheur2(void)
1021 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1022 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1023 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1024 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1026 static co_algo_info copyheur = {
1027 co_solve_heuristic_new, 0
1030 lc_opt_add_table(co2_grp, options);
1031 be_register_copyopt("heur2", ©heur);