2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief More experiments on coalescing.
23 * @author Sebastian Hack
29 #include "lc_opts_enum.h"
37 #include "raw_bitset.h"
40 #include "bitfiddle.h"
42 #include "irgraph_t.h"
47 #include "irnodemap.h"
52 #include "becopyopt.h"
53 #include "becopyopt_t.h"
54 #include "bechordal_t.h"
60 #define DUMP_ALL 2 * DUMP_CLOUD - 1
62 static unsigned dump_flags = 0;
63 static int subtree_iter = 4;
64 static int max_depth = 20;
65 static double constr_factor = 0.9;
67 static const lc_opt_enum_mask_items_t dump_items[] = {
68 { "before", DUMP_BEFORE },
69 { "after", DUMP_AFTER },
70 { "cloud", DUMP_CLOUD },
75 static lc_opt_enum_mask_var_t dump_var = {
76 &dump_flags, dump_items
79 static const lc_opt_table_entry_t options[] = {
80 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
81 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
82 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
83 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
89 / ___|| |_ __ _ _ __| |_
90 \___ \| __/ _` | '__| __|
91 ___) | || (_| | | | |_
92 |____/ \__\__,_|_| \__|
96 #define INFEASIBLE(cost) ((cost) == INT_MAX)
98 typedef unsigned col_t;
100 typedef struct co2_irn_t co2_irn_t;
101 typedef struct co2_cloud_t co2_cloud_t;
102 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
113 bitset_t *allocatable_regs;
117 struct list_head cloud_head;
118 DEBUG_ONLY(firm_dbg_module_t *dbg;)
123 affinity_node_t *aff;
124 co2_irn_t *touched_next;
127 int last_color_change;
130 unsigned tmp_fixed : 1;
131 unsigned is_constrained : 1;
132 struct list_head changed_list;
135 struct co2_cloud_irn_t {
136 struct co2_irn_t inh;
140 co2_cloud_irn_t *mst_parent;
143 co2_cloud_irn_t **mst_childs;
148 col_cost_pair_t *tmp_coloring;
149 struct list_head cloud_list;
150 struct list_head mst_list;
165 co2_cloud_irn_t *master;
166 co2_cloud_irn_t *mst_root;
167 co2_cloud_irn_t **seq;
168 struct list_head members_head;
169 struct list_head list;
173 co2_cloud_irn_t *src, *tgt;
177 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
179 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
181 co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
183 ci = OALLOCZ(&env->obst, co2_irn_t);
185 INIT_LIST_HEAD(&ci->changed_list);
186 ci->touched_next = env->touched;
187 ci->orig_col = get_irn_col(node);
192 ir_nodemap_insert(&env->map, node, ci);
197 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
199 co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
201 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
203 INIT_LIST_HEAD(&ci->inh.changed_list);
204 ci->inh.touched_next = env->touched;
205 ci->inh.orig_col = get_irn_col(node);
206 env->touched = &ci->inh;
208 ci->inh.aff = get_affinity_info(env->co, node);
210 INIT_LIST_HEAD(&ci->cloud_list);
213 ir_nodemap_insert(&env->map, node, ci);
218 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
220 static int cmp_clouds_gt(const void *a, const void *b)
222 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
223 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
224 double c = CLOUD_WEIGHT(*p);
225 double d = CLOUD_WEIGHT(*q);
226 return QSORT_CMP(d, c);
230 * An order on color/costs pairs.
231 * If the costs are equal, we use the color as a kind of normalization.
233 static int col_cost_pair_lt(const void *a, const void *b)
235 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
236 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
239 return QSORT_CMP(c, d);
242 static int cmp_edges(const void *a, const void *b)
244 const edge_t *p = (const edge_t*)a;
245 const edge_t *q = (const edge_t*)b;
246 return QSORT_CMP(q->costs, p->costs);
249 static col_t get_col(co2_t *env, const ir_node *irn)
251 co2_irn_t *ci = get_co2_irn(env, irn);
252 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
255 static inline int color_is_fix(co2_t *env, const ir_node *irn)
257 co2_irn_t *ci = get_co2_irn(env, irn);
258 return ci->fixed || ci->tmp_fixed;
261 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
263 if (ci->adm_cache == NULL) {
264 const arch_register_req_t *req;
265 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
266 req = arch_get_irn_register_req(ci->irn);
268 if (arch_register_req_is(req, limited)) {
272 for (i = 0; i < n; ++i) {
273 if (rbitset_is_set(req->limited, i))
274 bitset_set(ci->adm_cache, i);
276 ci->is_constrained = 1;
278 bitset_copy(ci->adm_cache, env->allocatable_regs);
282 return ci->adm_cache;
285 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
287 bitset_copy(bs, get_adm(env, ci));
291 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
293 bitset_t *bs = get_adm(env, ci);
294 return bitset_is_set(bs, col);
297 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
301 return ci->is_constrained;
304 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
306 const arch_register_req_t *req = arch_get_irn_register_req(irn);
308 if (arch_register_req_is(req, limited)) {
309 unsigned n_regs = env->co->cls->n_regs;
310 unsigned n_constr = 0;
313 n_constr = rbitset_popcount(req->limited, n_regs);
314 for (i = 0; i < n_regs; ++i) {
315 if (rbitset_is_set(req->limited, i)) {
316 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
323 * Determine costs which shall indicate how cheap/expensive it is to try
324 * to assign a node some color.
325 * The costs are computed for all colors. INT_MAX means that it is impossible
326 * to give the node that specific color.
328 * @param env The co2 this pointer.
329 * @param irn The node.
330 * @param col_costs An array of colors x costs where the costs are written to.
332 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
334 const ir_node *irn = ci->irn;
335 be_ifg_t *ifg = env->co->cenv->ifg;
336 int n_regs = env->co->cls->n_regs;
337 bitset_t *forb = bitset_alloca(n_regs);
338 affinity_node_t *a = ci->aff;
341 neighbours_iter_t it;
344 /* Put all forbidden colors into the aux bitset. */
345 admissible_colors(env, ci, forb);
346 bitset_flip_all(forb);
348 for (i = 0; i < n_regs; ++i) {
349 col_costs[i].col = i;
350 col_costs[i].costs = 0;
354 co_gs_foreach_neighb(a, n) {
355 if (color_is_fix(env, n->irn)) {
356 col_t col = get_col(env, n->irn);
357 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
360 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
364 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
365 col_t col = get_col(env, pos);
366 if (color_is_fix(env, pos)) {
367 col_costs[col].costs = INT_MAX;
370 incur_constraint_costs(env, pos, col_costs, INT_MAX);
371 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
374 be_ifg_neighbours_break(&it);
376 /* Set the costs to infinity for each color which is not allowed at this node. */
377 bitset_foreach(forb, elm) {
378 col_costs[elm].costs = INT_MAX;
383 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
385 int n_regs = env->co->cls->n_regs;
388 for (i = 0; i < n_regs; ++i) {
390 seq[i].costs = INT_MAX;
394 assert(is_color_admissible(env, ci, col));
400 static void reject_coloring(struct list_head *h)
404 list_for_each_entry(co2_irn_t, pos, h, changed_list)
408 static void materialize_coloring(struct list_head *h)
412 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
413 pos->orig_col = pos->tmp_col;
418 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
420 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
422 int n_regs = env->co->cls->n_regs;
423 be_ifg_t *ifg = env->co->cenv->ifg;
424 co2_irn_t *ci = get_co2_irn(env, irn);
429 if (depth >= max_depth)
432 for (i = 0; i < n_regs; ++i) {
433 col_t tgt_col = col_list[i].col;
434 unsigned costs = col_list[i].costs;
437 struct list_head changed;
439 neighbours_iter_t it;
441 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
443 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
444 if (INFEASIBLE(costs)) {
445 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
450 /* Set the new color of the node and mark the node as temporarily fixed. */
451 ci->tmp_col = tgt_col;
455 If that color has costs > 0, there's at least one neighbor having that color,
456 so we will try to change the neighbors' colors, too.
458 INIT_LIST_HEAD(&changed);
459 list_add(&ci->changed_list, &changed);
461 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
463 /* try to re-color the neighbor if it has the target color. */
464 if (get_col(env, n) == tgt_col) {
465 struct list_head tmp;
468 Try to change the color of the neighbor and record all nodes which
469 get changed in the tmp list. Add this list to the "changed" list for
470 that color. If we did not succeed to change the color of the neighbor,
471 we bail out and try the next color.
473 INIT_LIST_HEAD(&tmp);
474 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
475 list_splice(&tmp, &changed);
480 be_ifg_neighbours_break(&it);
483 We managed to assign the target color to all neighbors, so from the perspective
484 of the current node, every thing was ok and we can return safely.
487 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
488 list_splice(&changed, parent_changed);
494 If not, that color did not succeed and we unfix all nodes we touched
495 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
498 reject_coloring(&changed);
504 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
506 co2_irn_t *ci = get_co2_irn(env, irn);
508 col_t col = get_col(env, irn);
510 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
512 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
513 if (col != not_col) {
514 if (!ci->tmp_fixed) {
519 list_add(&ci->changed_list, parent_changed);
523 /* The node has the color it should not have _and_ has not been visited yet. */
524 if (!color_is_fix(env, irn)) {
525 int n_regs = env->co->cls->n_regs;
526 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
528 /* Get the costs for giving the node a specific color. */
529 determine_color_costs(env, ci, csts);
531 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
532 csts[not_col].costs = INT_MAX;
534 /* sort the colors according costs, cheapest first. */
535 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
537 /* Try recoloring the node using the color list. */
538 res = recolor(env, irn, csts, parent_changed, depth);
541 /* If we came here, everything went ok. */
545 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
547 co2_irn_t *ci = get_co2_irn(env, irn);
548 col_t col = get_col(env, irn);
551 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
553 /* the node has the wanted color. That's fine, mark it as visited and return. */
554 if (col == tgt_col) {
555 if (!ci->tmp_fixed) {
558 list_add(&ci->changed_list, parent_changed);
565 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
566 int n_regs = env->co->cls->n_regs;
567 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
569 /* Get the costs for giving the node a specific color. */
570 single_color_cost(env, ci, tgt_col, seq);
572 /* Try recoloring the node using the color list. */
573 res = recolor(env, irn, seq, parent_changed, depth);
578 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
583 * Examine the costs of the current coloring concerning a MST subtree.
584 * @param ci The subtree root.
585 * @param col The color of @p ci.
586 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
588 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
590 int *front = FRONT_BASE(ci, col);
594 for (i = 0; i < ci->mst_n_childs; ++i) {
595 co2_cloud_irn_t *chld = ci->mst_childs[i];
596 col_t chld_col = front[i];
598 cost += examine_subtree_coloring(chld, chld_col);
599 cost += col != chld_col ? chld->mst_costs : 0;
606 * Determine color badnesses of a node.
607 * Badness means that it is unlikely that the node in question can
608 * obtain a color. The higher the badness, the more unlikely it is that
609 * the node can be assigned that color.
610 * @param ci The node.
611 * @param badness An integer array as long as there are registers.
612 * @note The array <code>badness</code> is not cleared.
614 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
616 co2_t *env = ci->cloud->env;
617 co2_irn_t *ir = &ci->inh;
618 int n_regs = env->n_regs;
619 be_ifg_t *ifg = env->co->cenv->ifg;
620 bitset_t *bs = bitset_alloca(n_regs);
623 neighbours_iter_t it;
625 admissible_colors(env, &ci->inh, bs);
627 bitset_foreach(bs, elm)
628 badness[elm] = ci->costs;
630 /* Use constrained/fixed interfering neighbors to influence the color badness */
631 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
632 co2_irn_t *ni = get_co2_irn(env, irn);
634 admissible_colors(env, ni, bs);
635 if (bitset_popcount(bs) == 1) {
636 size_t c = bitset_next_set(bs, 0);
637 badness[c] += ci->costs;
640 else if (ni->fixed) {
641 col_t c = get_col(env, ni->irn);
642 badness[c] += ci->costs;
645 be_ifg_neighbours_break(&it);
649 * Determine the badness of a MST subtree.
650 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
651 * @see node_color_badness() for a definition of badness.
652 * @param ci The root of the subtree.
653 * @param depth Depth for debugging purposes.
655 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
657 co2_t *env = ci->cloud->env;
660 node_color_badness(ci, ci->color_badness);
662 /* Collect the color badness for the whole subtree */
663 for (i = 0; i < ci->mst_n_childs; ++i) {
664 co2_cloud_irn_t *child = ci->mst_childs[i];
665 determine_color_badness(child, depth + 1);
667 for (j = 0; j < env->n_regs; ++j)
668 ci->color_badness[j] += child->color_badness[j];
671 for (j = 0; j < env->n_regs; ++j)
672 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
676 * Unfix all nodes in a MST subtree.
678 static void unfix_subtree(co2_cloud_irn_t *ci)
683 for (i = 0; i < ci->mst_n_childs; ++i)
684 unfix_subtree(ci->mst_childs[i]);
687 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
689 co2_t *env = ci->cloud->env;
690 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
691 int is_root = ci->mst_parent == ci;
692 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
693 int min_badness = INT_MAX;
694 int best_col_costs = INT_MAX;
696 int n_regs = env->n_regs;
697 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
699 struct list_head changed;
702 for (i = 0; i < n_regs; ++i) {
703 int badness = ci->color_badness[i];
706 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
708 min_badness = MIN(min_badness, badness);
711 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
712 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
713 seq[parent_col].costs = min_badness - 1;
715 /* Sort the colors. The will be processed in that ordering. */
716 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
718 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
719 INIT_LIST_HEAD(&changed);
720 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
721 col_t col = seq[i].col;
722 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
724 int subtree_costs, sum_costs;
726 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
729 INIT_LIST_HEAD(&changed);
730 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
732 materialize_coloring(&changed);
739 for (j = 0; j < ci->mst_n_childs; ++j) {
740 co2_cloud_irn_t *child = ci->mst_childs[j];
741 ok = coalesce_top_down(child, j, depth + 1) >= 0;
743 child->inh.fixed = 1;
748 /* If the subtree could not be colored, we have to try another color. */
752 subtree_costs = examine_subtree_coloring(ci, col);
753 sum_costs = subtree_costs + add_cost;
754 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
756 if (sum_costs < best_col_costs) {
758 best_col_costs = sum_costs;
759 ci->col_costs[col] = subtree_costs;
767 int *front = FRONT_BASE(ci->mst_parent, parent_col);
768 front[child_nr] = best_col;
774 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
776 be_ifg_t *ifg = env->co->cenv->ifg;
777 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
783 /* mark the node as visited and add it to the cloud. */
785 list_add(&ci->cloud_list, &cloud->members_head);
787 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
789 /* determine the nodes costs */
790 co_gs_foreach_neighb(a, n) {
792 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
793 if (be_ifg_connected(ifg, a->irn, n->irn))
794 cloud->inevit += n->costs;
797 /* add the node's cost to the total costs of the cloud. */
799 cloud->costs += costs;
800 cloud->n_constr += is_constrained(env, &ci->inh);
801 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
802 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
805 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
806 if (costs >= curr_costs) {
811 /* add all the neighbors of the node to the cloud. */
812 co_gs_foreach_neighb(a, n) {
813 affinity_node_t *an = get_affinity_info(env->co, n->irn);
815 populate_cloud(env, cloud, an, curr_costs);
819 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
821 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
825 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
826 memset(cloud, 0, sizeof(cloud[0]));
827 INIT_LIST_HEAD(&cloud->members_head);
828 INIT_LIST_HEAD(&cloud->list);
829 list_add(&cloud->list, &env->cloud_head);
830 cloud->best_costs = INT_MAX;
833 populate_cloud(env, cloud, a, 0);
834 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
836 /* Also allocate space for the node sequence and compute that sequence. */
837 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
840 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
842 cloud->seq[i++] = ci;
844 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
849 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
851 const ir_node *irn = ci->inh.irn;
852 int *front = FRONT_BASE(ci, col);
854 struct list_head changed;
856 INIT_LIST_HEAD(&changed);
858 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
859 change_color_single(ci->cloud->env, irn, col, &changed, depth);
860 materialize_coloring(&changed);
862 for (i = 0; i < ci->mst_n_childs; ++i) {
863 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
867 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
869 while (ci != ci->mst_parent)
875 static void process_cloud(co2_cloud_t *cloud)
877 co2_t *env = cloud->env;
878 int n_regs = env->n_regs;
880 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
887 /* Collect all edges in the cloud on an obstack and sort the increasingly */
888 obstack_init(&cloud->obst);
889 for (i = 0; i < cloud->n_memb; ++i) {
890 co2_cloud_irn_t *ci = cloud->seq[i];
892 co_gs_foreach_neighb(ci->inh.aff, n) {
893 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
894 if (ci->index < ni->index) {
899 obstack_grow(&cloud->obst, &e, sizeof(e));
904 edges = (edge_t*)obstack_finish(&cloud->obst);
905 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
907 /* Compute the maximum spanning tree using Kruskal/Union-Find */
908 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
909 for (i = 0; i < n_edges; ++i) {
910 edge_t *e = &edges[i];
911 co2_cloud_irn_t *rs = find_mst_root(e->src);
912 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
914 /* if the union/find roots are different */
916 int si = e->src->index;
917 int ti = e->tgt->index;
921 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
923 /* this edge is in the MST, so set it in the bitset. */
924 mst_edges[si * cloud->n_memb + ti] = e->costs;
925 mst_edges[ti * cloud->n_memb + si] = e->costs;
928 obstack_free(&cloud->obst, edges);
930 cloud->master->mst_parent = cloud->master;
931 cloud->mst_root = cloud->master;
932 q = new_pdeq1(cloud->master);
933 while (!pdeq_empty(q)) {
934 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
935 int ofs = ci->index * cloud->n_memb;
936 int end = ofs + cloud->n_memb;
939 ci->mst_n_childs = 0;
940 for (i = ofs; i < end; ++i) {
941 if (mst_edges[i] != 0) {
943 co2_cloud_irn_t *child = cloud->seq[i - ofs];
945 /* put the child to the worklist */
948 /* make ci the parent of the child and add the child to the children array of the parent */
949 child->mst_parent = ci;
950 child->mst_costs = mst_edges[i];
952 obstack_ptr_grow(&cloud->obst, child);
954 mst_edges[other * cloud->n_memb + ci->index] = 0;
959 obstack_ptr_grow(&cloud->obst, NULL);
960 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
966 DBG((env->dbg, LEVEL_3, "mst:\n"));
967 for (i = 0; i < cloud->n_memb; ++i) {
968 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
969 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
972 for (i = 0; i < cloud->n_memb; ++i) {
973 co2_cloud_irn_t *ci = cloud->seq[i];
974 int n_childs = ci->mst_n_childs;
977 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
978 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
979 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
980 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
982 for (j = 0; j < env->n_regs; j++)
983 ci->col_costs[j] = INT_MAX;
986 determine_color_badness(cloud->mst_root, 0);
987 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
988 unfix_subtree(cloud->mst_root);
989 apply_coloring(cloud->mst_root, best_col, 0);
991 /* The coloring should represent the one with the best costs. */
992 //materialize_coloring(&changed);
993 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
994 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
996 /* Fix all nodes in the cloud. */
997 for (i = 0; i < cloud->n_memb; ++i)
998 cloud->seq[i]->inh.fixed = 1;
1000 /* Free all space used while optimizing this cloud. */
1001 obstack_free(&cloud->obst, NULL);
1004 static int cloud_costs(co2_cloud_t *cloud)
1008 for (i = 0; i < cloud->n_memb; ++i) {
1009 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1010 col_t col = get_col(cloud->env, ci->irn);
1011 co_gs_foreach_neighb(ci->aff, n) {
1012 col_t n_col = get_col(cloud->env, n->irn);
1013 costs += col != n_col ? n->costs : 0;
1020 static void writeback_colors(co2_t *env)
1024 for (irn = env->touched; irn; irn = irn->touched_next) {
1025 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1026 arch_set_irn_register((ir_node*)irn->irn, reg);
1030 static void process(co2_t *env)
1033 co2_cloud_t **clouds;
1038 int final_costs = 0;
1041 co_gs_foreach_aff_node(env->co, a) {
1042 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1051 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1052 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1054 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1056 for (i = 0; i < n_clouds; ++i) {
1057 init_costs += cloud_costs(clouds[i]);
1059 /* Process the cloud. */
1060 process_cloud(clouds[i]);
1062 all_costs += clouds[i]->costs;
1063 final_costs += cloud_costs(clouds[i]);
1066 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1071 static int co_solve_heuristic_new(copy_opt_t *co)
1075 ir_nodemap_init(&env.map, co->irg);
1076 obstack_init(&env.obst);
1080 env.n_regs = co->cls->n_regs;
1081 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1082 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1083 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1084 INIT_LIST_HEAD(&env.cloud_head);
1088 writeback_colors(&env);
1089 obstack_free(&env.obst, NULL);
1090 ir_nodemap_destroy(&env.map);
1094 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1095 void be_init_copyheur2(void)
1097 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1098 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1099 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1100 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1102 static co_algo_info copyheur = {
1103 co_solve_heuristic_new, 0
1106 lc_opt_add_table(co2_grp, options);
1107 be_register_copyopt("heur2", ©heur);