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 = (co2_irn_t*)ir_nodemap_get(&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 = (co2_cloud_irn_t*)ir_nodemap_get(&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;
342 neighbours_iter_t it;
345 /* Put all forbidden colors into the aux bitset. */
346 admissible_colors(env, ci, forb);
347 bitset_flip_all(forb);
349 for (i = 0; i < n_regs; ++i) {
350 col_costs[i].col = i;
351 col_costs[i].costs = 0;
357 co_gs_foreach_neighb(a, n) {
358 if (color_is_fix(env, n->irn)) {
359 col_t col = get_col(env, n->irn);
360 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
363 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
367 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
368 col_t col = get_col(env, pos);
369 if (color_is_fix(env, pos)) {
370 col_costs[col].costs = INT_MAX;
373 incur_constraint_costs(env, pos, col_costs, INT_MAX);
374 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
377 be_ifg_neighbours_break(&it);
379 /* Set the costs to infinity for each color which is not allowed at this node. */
380 bitset_foreach(forb, elm) {
381 col_costs[elm].costs = INT_MAX;
386 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
388 int n_regs = env->co->cls->n_regs;
391 for (i = 0; i < n_regs; ++i) {
393 seq[i].costs = INT_MAX;
397 assert(is_color_admissible(env, ci, col));
403 static void reject_coloring(struct list_head *h)
407 list_for_each_entry(co2_irn_t, pos, h, changed_list)
411 static void materialize_coloring(struct list_head *h)
415 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
416 pos->orig_col = pos->tmp_col;
421 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
423 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
425 int n_regs = env->co->cls->n_regs;
426 be_ifg_t *ifg = env->co->cenv->ifg;
427 co2_irn_t *ci = get_co2_irn(env, irn);
432 if (depth >= max_depth)
435 for (i = 0; i < n_regs; ++i) {
436 col_t tgt_col = col_list[i].col;
437 unsigned costs = col_list[i].costs;
440 struct list_head changed;
442 neighbours_iter_t it;
444 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
446 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
447 if (INFEASIBLE(costs)) {
448 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
453 /* Set the new color of the node and mark the node as temporarily fixed. */
454 ci->tmp_col = tgt_col;
458 If that color has costs > 0, there's at least one neighbor having that color,
459 so we will try to change the neighbors' colors, too.
461 INIT_LIST_HEAD(&changed);
462 list_add(&ci->changed_list, &changed);
464 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
466 /* try to re-color the neighbor if it has the target color. */
467 if (get_col(env, n) == tgt_col) {
468 struct list_head tmp;
471 Try to change the color of the neighbor and record all nodes which
472 get changed in the tmp list. Add this list to the "changed" list for
473 that color. If we did not succeed to change the color of the neighbor,
474 we bail out and try the next color.
476 INIT_LIST_HEAD(&tmp);
477 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
478 list_splice(&tmp, &changed);
483 be_ifg_neighbours_break(&it);
486 We managed to assign the target color to all neighbors, so from the perspective
487 of the current node, every thing was ok and we can return safely.
490 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
491 list_splice(&changed, parent_changed);
497 If not, that color did not succeed and we unfix all nodes we touched
498 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
501 reject_coloring(&changed);
507 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
509 co2_irn_t *ci = get_co2_irn(env, irn);
511 col_t col = get_col(env, irn);
513 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
515 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
516 if (col != not_col) {
517 if (!ci->tmp_fixed) {
522 list_add(&ci->changed_list, parent_changed);
526 /* The node has the color it should not have _and_ has not been visited yet. */
527 if (!color_is_fix(env, irn)) {
528 int n_regs = env->co->cls->n_regs;
529 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
531 /* Get the costs for giving the node a specific color. */
532 determine_color_costs(env, ci, csts);
534 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
535 csts[not_col].costs = INT_MAX;
537 /* sort the colors according costs, cheapest first. */
538 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
540 /* Try recoloring the node using the color list. */
541 res = recolor(env, irn, csts, parent_changed, depth);
544 /* If we came here, everything went ok. */
548 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
550 co2_irn_t *ci = get_co2_irn(env, irn);
551 col_t col = get_col(env, irn);
554 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
556 /* the node has the wanted color. That's fine, mark it as visited and return. */
557 if (col == tgt_col) {
558 if (!ci->tmp_fixed) {
561 list_add(&ci->changed_list, parent_changed);
568 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
569 int n_regs = env->co->cls->n_regs;
570 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
572 /* Get the costs for giving the node a specific color. */
573 single_color_cost(env, ci, tgt_col, seq);
575 /* Try recoloring the node using the color list. */
576 res = recolor(env, irn, seq, parent_changed, depth);
581 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
586 * Examine the costs of the current coloring concerning a MST subtree.
587 * @param ci The subtree root.
588 * @param col The color of @p ci.
589 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
591 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
593 int *front = FRONT_BASE(ci, col);
597 for (i = 0; i < ci->mst_n_childs; ++i) {
598 co2_cloud_irn_t *chld = ci->mst_childs[i];
599 col_t chld_col = front[i];
601 cost += examine_subtree_coloring(chld, chld_col);
602 cost += col != chld_col ? chld->mst_costs : 0;
609 * Determine color badnesses of a node.
610 * Badness means that it is unlikely that the node in question can
611 * obtain a color. The higher the badness, the more unlikely it is that
612 * the node can be assigned that color.
613 * @param ci The node.
614 * @param badness An integer array as long as there are registers.
615 * @note The array <code>badness</code> is not cleared.
617 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
619 co2_t *env = ci->cloud->env;
620 co2_irn_t *ir = &ci->inh;
621 int n_regs = env->n_regs;
622 be_ifg_t *ifg = env->co->cenv->ifg;
623 bitset_t *bs = bitset_alloca(n_regs);
627 neighbours_iter_t it;
629 admissible_colors(env, &ci->inh, bs);
631 bitset_foreach(bs, elm)
632 badness[elm] = ci->costs;
634 /* Use constrained/fixed interfering neighbors to influence the color badness */
635 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
636 co2_irn_t *ni = get_co2_irn(env, irn);
638 admissible_colors(env, ni, bs);
639 if (bitset_popcount(bs) == 1) {
640 size_t c = bitset_next_set(bs, 0);
641 badness[c] += ci->costs;
644 else if (ni->fixed) {
645 col_t c = get_col(env, ni->irn);
646 badness[c] += ci->costs;
649 be_ifg_neighbours_break(&it);
653 * Determine the badness of a MST subtree.
654 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
655 * @see node_color_badness() for a definition of badness.
656 * @param ci The root of the subtree.
657 * @param depth Depth for debugging purposes.
659 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
661 co2_t *env = ci->cloud->env;
664 node_color_badness(ci, ci->color_badness);
666 /* Collect the color badness for the whole subtree */
667 for (i = 0; i < ci->mst_n_childs; ++i) {
668 co2_cloud_irn_t *child = ci->mst_childs[i];
669 determine_color_badness(child, depth + 1);
671 for (j = 0; j < env->n_regs; ++j)
672 ci->color_badness[j] += child->color_badness[j];
675 for (j = 0; j < env->n_regs; ++j)
676 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
680 * Unfix all nodes in a MST subtree.
682 static void unfix_subtree(co2_cloud_irn_t *ci)
687 for (i = 0; i < ci->mst_n_childs; ++i)
688 unfix_subtree(ci->mst_childs[i]);
691 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
693 co2_t *env = ci->cloud->env;
694 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
695 int is_root = ci->mst_parent == ci;
696 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
697 int min_badness = INT_MAX;
698 int best_col_costs = INT_MAX;
700 int n_regs = env->n_regs;
701 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
703 struct list_head changed;
706 for (i = 0; i < n_regs; ++i) {
707 int badness = ci->color_badness[i];
710 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
712 min_badness = MIN(min_badness, badness);
715 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
716 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
717 seq[parent_col].costs = min_badness - 1;
719 /* Sort the colors. The will be processed in that ordering. */
720 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
722 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
723 INIT_LIST_HEAD(&changed);
724 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
725 col_t col = seq[i].col;
726 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
728 int subtree_costs, sum_costs;
730 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
733 INIT_LIST_HEAD(&changed);
734 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
736 materialize_coloring(&changed);
743 for (j = 0; j < ci->mst_n_childs; ++j) {
744 co2_cloud_irn_t *child = ci->mst_childs[j];
745 ok = coalesce_top_down(child, j, depth + 1) >= 0;
747 child->inh.fixed = 1;
752 /* If the subtree could not be colored, we have to try another color. */
756 subtree_costs = examine_subtree_coloring(ci, col);
757 sum_costs = subtree_costs + add_cost;
758 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
760 if (sum_costs < best_col_costs) {
762 best_col_costs = sum_costs;
763 ci->col_costs[col] = subtree_costs;
771 int *front = FRONT_BASE(ci->mst_parent, parent_col);
772 front[child_nr] = best_col;
778 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
780 be_ifg_t *ifg = env->co->cenv->ifg;
781 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
788 /* mark the node as visited and add it to the cloud. */
790 list_add(&ci->cloud_list, &cloud->members_head);
792 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
794 /* determine the nodes costs */
795 co_gs_foreach_neighb(a, n) {
797 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
798 if (be_ifg_connected(ifg, a->irn, n->irn))
799 cloud->inevit += n->costs;
802 /* add the node's cost to the total costs of the cloud. */
804 cloud->costs += costs;
805 cloud->n_constr += is_constrained(env, &ci->inh);
806 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
807 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
810 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
811 if (costs >= curr_costs) {
816 /* add all the neighbors of the node to the cloud. */
817 co_gs_foreach_neighb(a, n) {
818 affinity_node_t *an = get_affinity_info(env->co, n->irn);
820 populate_cloud(env, cloud, an, curr_costs);
824 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
826 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
830 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
831 memset(cloud, 0, sizeof(cloud[0]));
832 INIT_LIST_HEAD(&cloud->members_head);
833 INIT_LIST_HEAD(&cloud->list);
834 list_add(&cloud->list, &env->cloud_head);
835 cloud->best_costs = INT_MAX;
838 populate_cloud(env, cloud, a, 0);
839 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
841 /* Also allocate space for the node sequence and compute that sequence. */
842 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
845 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
847 cloud->seq[i++] = ci;
849 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
854 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
856 const ir_node *irn = ci->inh.irn;
857 int *front = FRONT_BASE(ci, col);
859 struct list_head changed;
861 INIT_LIST_HEAD(&changed);
863 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
864 change_color_single(ci->cloud->env, irn, col, &changed, depth);
865 materialize_coloring(&changed);
867 for (i = 0; i < ci->mst_n_childs; ++i) {
868 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
872 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
874 while (ci != ci->mst_parent)
880 static void process_cloud(co2_cloud_t *cloud)
882 co2_t *env = cloud->env;
883 int n_regs = env->n_regs;
885 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
892 /* Collect all edges in the cloud on an obstack and sort the increasingly */
893 obstack_init(&cloud->obst);
894 for (i = 0; i < cloud->n_memb; ++i) {
895 co2_cloud_irn_t *ci = cloud->seq[i];
898 co_gs_foreach_neighb(ci->inh.aff, n) {
899 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
900 if (ci->index < ni->index) {
905 obstack_grow(&cloud->obst, &e, sizeof(e));
910 edges = (edge_t*)obstack_finish(&cloud->obst);
911 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
913 /* Compute the maximum spanning tree using Kruskal/Union-Find */
914 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
915 for (i = 0; i < n_edges; ++i) {
916 edge_t *e = &edges[i];
917 co2_cloud_irn_t *rs = find_mst_root(e->src);
918 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
920 /* if the union/find roots are different */
922 int si = e->src->index;
923 int ti = e->tgt->index;
927 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
929 /* this edge is in the MST, so set it in the bitset. */
930 mst_edges[si * cloud->n_memb + ti] = e->costs;
931 mst_edges[ti * cloud->n_memb + si] = e->costs;
934 obstack_free(&cloud->obst, edges);
936 cloud->master->mst_parent = cloud->master;
937 cloud->mst_root = cloud->master;
938 q = new_pdeq1(cloud->master);
939 while (!pdeq_empty(q)) {
940 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
941 int ofs = ci->index * cloud->n_memb;
942 int end = ofs + cloud->n_memb;
945 ci->mst_n_childs = 0;
946 for (i = ofs; i < end; ++i) {
947 if (mst_edges[i] != 0) {
949 co2_cloud_irn_t *child = cloud->seq[i - ofs];
951 /* put the child to the worklist */
954 /* make ci the parent of the child and add the child to the children array of the parent */
955 child->mst_parent = ci;
956 child->mst_costs = mst_edges[i];
958 obstack_ptr_grow(&cloud->obst, child);
960 mst_edges[other * cloud->n_memb + ci->index] = 0;
965 obstack_ptr_grow(&cloud->obst, NULL);
966 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
972 DBG((env->dbg, LEVEL_3, "mst:\n"));
973 for (i = 0; i < cloud->n_memb; ++i) {
974 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
975 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
978 for (i = 0; i < cloud->n_memb; ++i) {
979 co2_cloud_irn_t *ci = cloud->seq[i];
980 int n_childs = ci->mst_n_childs;
983 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
984 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
985 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
986 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
988 for (j = 0; j < env->n_regs; j++)
989 ci->col_costs[j] = INT_MAX;
992 determine_color_badness(cloud->mst_root, 0);
993 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
994 unfix_subtree(cloud->mst_root);
995 apply_coloring(cloud->mst_root, best_col, 0);
997 /* The coloring should represent the one with the best costs. */
998 //materialize_coloring(&changed);
999 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1000 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1002 /* Fix all nodes in the cloud. */
1003 for (i = 0; i < cloud->n_memb; ++i)
1004 cloud->seq[i]->inh.fixed = 1;
1006 /* Free all space used while optimizing this cloud. */
1007 obstack_free(&cloud->obst, NULL);
1010 static int cloud_costs(co2_cloud_t *cloud)
1015 for (i = 0; i < cloud->n_memb; ++i) {
1016 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1017 col_t col = get_col(cloud->env, ci->irn);
1018 co_gs_foreach_neighb(ci->aff, n) {
1019 col_t n_col = get_col(cloud->env, n->irn);
1020 costs += col != n_col ? n->costs : 0;
1027 static void writeback_colors(co2_t *env)
1031 for (irn = env->touched; irn; irn = irn->touched_next) {
1032 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1033 arch_set_irn_register((ir_node*)irn->irn, reg);
1037 static void process(co2_t *env)
1041 co2_cloud_t **clouds;
1046 int final_costs = 0;
1049 co_gs_foreach_aff_node(env->co, a) {
1050 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1059 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1060 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1062 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1064 for (i = 0; i < n_clouds; ++i) {
1065 init_costs += cloud_costs(clouds[i]);
1067 /* Process the cloud. */
1068 process_cloud(clouds[i]);
1070 all_costs += clouds[i]->costs;
1071 final_costs += cloud_costs(clouds[i]);
1074 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1079 static int co_solve_heuristic_new(copy_opt_t *co)
1083 ir_nodemap_init(&env.map, co->irg);
1084 obstack_init(&env.obst);
1088 env.n_regs = co->cls->n_regs;
1089 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1090 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1091 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1092 INIT_LIST_HEAD(&env.cloud_head);
1096 writeback_colors(&env);
1097 obstack_free(&env.obst, NULL);
1098 ir_nodemap_destroy(&env.map);
1102 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1103 void be_init_copyheur2(void)
1105 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1106 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1107 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1108 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1110 static co_algo_info copyheur = {
1111 co_solve_heuristic_new, 0
1114 lc_opt_add_table(co2_grp, options);
1115 be_register_copyopt("heur2", ©heur);