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 affinity_node_t *a = ci->aff;
340 neighbours_iter_t it;
343 /* Put all forbidden colors into the aux bitset. */
344 bitset_t *const admissible = bitset_alloca(n_regs);
345 admissible_colors(env, ci, admissible);
347 for (i = 0; i < n_regs; ++i) {
348 col_costs[i].col = i;
349 col_costs[i].costs = 0;
353 co_gs_foreach_neighb(a, n) {
354 if (color_is_fix(env, n->irn)) {
355 col_t col = get_col(env, n->irn);
356 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
359 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
363 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
364 col_t col = get_col(env, pos);
365 if (color_is_fix(env, pos)) {
366 col_costs[col].costs = INT_MAX;
369 incur_constraint_costs(env, pos, col_costs, INT_MAX);
370 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
373 be_ifg_neighbours_break(&it);
375 /* Set the costs to infinity for each color which is not allowed at this node. */
376 bitset_foreach_clear(admissible, elm) {
377 col_costs[elm].costs = INT_MAX;
382 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
384 int n_regs = env->co->cls->n_regs;
387 for (i = 0; i < n_regs; ++i) {
389 seq[i].costs = INT_MAX;
393 assert(is_color_admissible(env, ci, col));
399 static void reject_coloring(struct list_head *h)
401 list_for_each_entry(co2_irn_t, pos, h, changed_list)
405 static void materialize_coloring(struct list_head *h)
407 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
408 pos->orig_col = pos->tmp_col;
413 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
415 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
417 int n_regs = env->co->cls->n_regs;
418 be_ifg_t *ifg = env->co->cenv->ifg;
419 co2_irn_t *ci = get_co2_irn(env, irn);
424 if (depth >= max_depth)
427 for (i = 0; i < n_regs; ++i) {
428 col_t tgt_col = col_list[i].col;
429 unsigned costs = col_list[i].costs;
432 struct list_head changed;
434 neighbours_iter_t it;
436 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
438 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
439 if (INFEASIBLE(costs)) {
440 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
445 /* Set the new color of the node and mark the node as temporarily fixed. */
446 ci->tmp_col = tgt_col;
450 If that color has costs > 0, there's at least one neighbor having that color,
451 so we will try to change the neighbors' colors, too.
453 INIT_LIST_HEAD(&changed);
454 list_add(&ci->changed_list, &changed);
456 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
458 /* try to re-color the neighbor if it has the target color. */
459 if (get_col(env, n) == tgt_col) {
460 struct list_head tmp;
463 Try to change the color of the neighbor and record all nodes which
464 get changed in the tmp list. Add this list to the "changed" list for
465 that color. If we did not succeed to change the color of the neighbor,
466 we bail out and try the next color.
468 INIT_LIST_HEAD(&tmp);
469 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
470 list_splice(&tmp, &changed);
475 be_ifg_neighbours_break(&it);
478 We managed to assign the target color to all neighbors, so from the perspective
479 of the current node, every thing was ok and we can return safely.
482 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
483 list_splice(&changed, parent_changed);
489 If not, that color did not succeed and we unfix all nodes we touched
490 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
493 reject_coloring(&changed);
499 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
501 co2_irn_t *ci = get_co2_irn(env, irn);
503 col_t col = get_col(env, irn);
505 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
507 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
508 if (col != not_col) {
509 if (!ci->tmp_fixed) {
514 list_add(&ci->changed_list, parent_changed);
518 /* The node has the color it should not have _and_ has not been visited yet. */
519 if (!color_is_fix(env, irn)) {
520 int n_regs = env->co->cls->n_regs;
521 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
523 /* Get the costs for giving the node a specific color. */
524 determine_color_costs(env, ci, csts);
526 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
527 csts[not_col].costs = INT_MAX;
529 /* sort the colors according costs, cheapest first. */
530 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
532 /* Try recoloring the node using the color list. */
533 res = recolor(env, irn, csts, parent_changed, depth);
536 /* If we came here, everything went ok. */
540 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
542 co2_irn_t *ci = get_co2_irn(env, irn);
543 col_t col = get_col(env, irn);
546 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
548 /* the node has the wanted color. That's fine, mark it as visited and return. */
549 if (col == tgt_col) {
550 if (!ci->tmp_fixed) {
553 list_add(&ci->changed_list, parent_changed);
560 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
561 int n_regs = env->co->cls->n_regs;
562 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
564 /* Get the costs for giving the node a specific color. */
565 single_color_cost(env, ci, tgt_col, seq);
567 /* Try recoloring the node using the color list. */
568 res = recolor(env, irn, seq, parent_changed, depth);
573 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
578 * Examine the costs of the current coloring concerning a MST subtree.
579 * @param ci The subtree root.
580 * @param col The color of @p ci.
581 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
583 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
585 int *front = FRONT_BASE(ci, col);
589 for (i = 0; i < ci->mst_n_childs; ++i) {
590 co2_cloud_irn_t *chld = ci->mst_childs[i];
591 col_t chld_col = front[i];
593 cost += examine_subtree_coloring(chld, chld_col);
594 cost += col != chld_col ? chld->mst_costs : 0;
601 * Determine color badnesses of a node.
602 * Badness means that it is unlikely that the node in question can
603 * obtain a color. The higher the badness, the more unlikely it is that
604 * the node can be assigned that color.
605 * @param ci The node.
606 * @param badness An integer array as long as there are registers.
607 * @note The array <code>badness</code> is not cleared.
609 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
611 co2_t *env = ci->cloud->env;
612 co2_irn_t *ir = &ci->inh;
613 int n_regs = env->n_regs;
614 be_ifg_t *ifg = env->co->cenv->ifg;
615 bitset_t *bs = bitset_alloca(n_regs);
618 neighbours_iter_t it;
620 admissible_colors(env, &ci->inh, bs);
621 bitset_foreach_clear(bs, elm)
622 badness[elm] = ci->costs;
624 /* Use constrained/fixed interfering neighbors to influence the color badness */
625 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
626 co2_irn_t *ni = get_co2_irn(env, irn);
628 admissible_colors(env, ni, bs);
629 if (bitset_popcount(bs) == 1) {
630 size_t c = bitset_next_set(bs, 0);
631 badness[c] += ci->costs;
634 else if (ni->fixed) {
635 col_t c = get_col(env, ni->irn);
636 badness[c] += ci->costs;
639 be_ifg_neighbours_break(&it);
643 * Determine the badness of a MST subtree.
644 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
645 * @see node_color_badness() for a definition of badness.
646 * @param ci The root of the subtree.
647 * @param depth Depth for debugging purposes.
649 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
651 co2_t *env = ci->cloud->env;
654 node_color_badness(ci, ci->color_badness);
656 /* Collect the color badness for the whole subtree */
657 for (i = 0; i < ci->mst_n_childs; ++i) {
658 co2_cloud_irn_t *child = ci->mst_childs[i];
659 determine_color_badness(child, depth + 1);
661 for (j = 0; j < env->n_regs; ++j)
662 ci->color_badness[j] += child->color_badness[j];
665 for (j = 0; j < env->n_regs; ++j)
666 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
670 * Unfix all nodes in a MST subtree.
672 static void unfix_subtree(co2_cloud_irn_t *ci)
677 for (i = 0; i < ci->mst_n_childs; ++i)
678 unfix_subtree(ci->mst_childs[i]);
681 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
683 co2_t *env = ci->cloud->env;
684 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
685 int is_root = ci->mst_parent == ci;
686 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
687 int min_badness = INT_MAX;
688 int best_col_costs = INT_MAX;
690 int n_regs = env->n_regs;
691 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
693 struct list_head changed;
696 for (i = 0; i < n_regs; ++i) {
697 int badness = ci->color_badness[i];
700 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
702 min_badness = MIN(min_badness, badness);
705 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
706 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
707 seq[parent_col].costs = min_badness - 1;
709 /* Sort the colors. The will be processed in that ordering. */
710 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
712 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
713 INIT_LIST_HEAD(&changed);
714 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
715 col_t col = seq[i].col;
716 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
718 int subtree_costs, sum_costs;
720 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
723 INIT_LIST_HEAD(&changed);
724 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
726 materialize_coloring(&changed);
733 for (j = 0; j < ci->mst_n_childs; ++j) {
734 co2_cloud_irn_t *child = ci->mst_childs[j];
735 ok = coalesce_top_down(child, j, depth + 1) >= 0;
737 child->inh.fixed = 1;
742 /* If the subtree could not be colored, we have to try another color. */
746 subtree_costs = examine_subtree_coloring(ci, col);
747 sum_costs = subtree_costs + add_cost;
748 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
750 if (sum_costs < best_col_costs) {
752 best_col_costs = sum_costs;
753 ci->col_costs[col] = subtree_costs;
761 int *front = FRONT_BASE(ci->mst_parent, parent_col);
762 front[child_nr] = best_col;
768 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
770 be_ifg_t *ifg = env->co->cenv->ifg;
771 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
777 /* mark the node as visited and add it to the cloud. */
779 list_add(&ci->cloud_list, &cloud->members_head);
781 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
783 /* determine the nodes costs */
784 co_gs_foreach_neighb(a, n) {
786 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
787 if (be_ifg_connected(ifg, a->irn, n->irn))
788 cloud->inevit += n->costs;
791 /* add the node's cost to the total costs of the cloud. */
793 cloud->costs += costs;
794 cloud->n_constr += is_constrained(env, &ci->inh);
795 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
796 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
799 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
800 if (costs >= curr_costs) {
805 /* add all the neighbors of the node to the cloud. */
806 co_gs_foreach_neighb(a, n) {
807 affinity_node_t *an = get_affinity_info(env->co, n->irn);
809 populate_cloud(env, cloud, an, curr_costs);
813 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
815 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
818 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
819 memset(cloud, 0, sizeof(cloud[0]));
820 INIT_LIST_HEAD(&cloud->members_head);
821 INIT_LIST_HEAD(&cloud->list);
822 list_add(&cloud->list, &env->cloud_head);
823 cloud->best_costs = INT_MAX;
826 populate_cloud(env, cloud, a, 0);
827 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
829 /* Also allocate space for the node sequence and compute that sequence. */
830 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
833 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
835 cloud->seq[i++] = ci;
837 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
842 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
844 const ir_node *irn = ci->inh.irn;
845 int *front = FRONT_BASE(ci, col);
847 struct list_head changed;
849 INIT_LIST_HEAD(&changed);
851 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
852 change_color_single(ci->cloud->env, irn, col, &changed, depth);
853 materialize_coloring(&changed);
855 for (i = 0; i < ci->mst_n_childs; ++i) {
856 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
860 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
862 while (ci != ci->mst_parent)
868 static void process_cloud(co2_cloud_t *cloud)
870 co2_t *env = cloud->env;
871 int n_regs = env->n_regs;
873 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
880 /* Collect all edges in the cloud on an obstack and sort the increasingly */
881 obstack_init(&cloud->obst);
882 for (i = 0; i < cloud->n_memb; ++i) {
883 co2_cloud_irn_t *ci = cloud->seq[i];
885 co_gs_foreach_neighb(ci->inh.aff, n) {
886 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
887 if (ci->index < ni->index) {
892 obstack_grow(&cloud->obst, &e, sizeof(e));
897 edges = (edge_t*)obstack_finish(&cloud->obst);
898 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
900 /* Compute the maximum spanning tree using Kruskal/Union-Find */
901 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
902 for (i = 0; i < n_edges; ++i) {
903 edge_t *e = &edges[i];
904 co2_cloud_irn_t *rs = find_mst_root(e->src);
905 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
907 /* if the union/find roots are different */
909 int si = e->src->index;
910 int ti = e->tgt->index;
914 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
916 /* this edge is in the MST, so set it in the bitset. */
917 mst_edges[si * cloud->n_memb + ti] = e->costs;
918 mst_edges[ti * cloud->n_memb + si] = e->costs;
921 obstack_free(&cloud->obst, edges);
923 cloud->master->mst_parent = cloud->master;
924 cloud->mst_root = cloud->master;
925 q = new_pdeq1(cloud->master);
926 while (!pdeq_empty(q)) {
927 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
928 int ofs = ci->index * cloud->n_memb;
929 int end = ofs + cloud->n_memb;
932 ci->mst_n_childs = 0;
933 for (i = ofs; i < end; ++i) {
934 if (mst_edges[i] != 0) {
936 co2_cloud_irn_t *child = cloud->seq[i - ofs];
938 /* put the child to the worklist */
941 /* make ci the parent of the child and add the child to the children array of the parent */
942 child->mst_parent = ci;
943 child->mst_costs = mst_edges[i];
945 obstack_ptr_grow(&cloud->obst, child);
947 mst_edges[other * cloud->n_memb + ci->index] = 0;
952 obstack_ptr_grow(&cloud->obst, NULL);
953 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
959 DBG((env->dbg, LEVEL_3, "mst:\n"));
960 for (i = 0; i < cloud->n_memb; ++i) {
961 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
962 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
965 for (i = 0; i < cloud->n_memb; ++i) {
966 co2_cloud_irn_t *ci = cloud->seq[i];
967 int n_childs = ci->mst_n_childs;
970 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
971 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
972 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
973 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
975 for (j = 0; j < env->n_regs; j++)
976 ci->col_costs[j] = INT_MAX;
979 determine_color_badness(cloud->mst_root, 0);
980 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
981 unfix_subtree(cloud->mst_root);
982 apply_coloring(cloud->mst_root, best_col, 0);
984 /* The coloring should represent the one with the best costs. */
985 //materialize_coloring(&changed);
986 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
987 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
989 /* Fix all nodes in the cloud. */
990 for (i = 0; i < cloud->n_memb; ++i)
991 cloud->seq[i]->inh.fixed = 1;
993 /* Free all space used while optimizing this cloud. */
994 obstack_free(&cloud->obst, NULL);
997 static int cloud_costs(co2_cloud_t *cloud)
1001 for (i = 0; i < cloud->n_memb; ++i) {
1002 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1003 col_t col = get_col(cloud->env, ci->irn);
1004 co_gs_foreach_neighb(ci->aff, n) {
1005 col_t n_col = get_col(cloud->env, n->irn);
1006 costs += col != n_col ? n->costs : 0;
1013 static void writeback_colors(co2_t *env)
1017 for (irn = env->touched; irn; irn = irn->touched_next) {
1018 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1019 arch_set_irn_register((ir_node*)irn->irn, reg);
1023 static void process(co2_t *env)
1025 co2_cloud_t **clouds;
1030 int final_costs = 0;
1033 co_gs_foreach_aff_node(env->co, a) {
1034 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1043 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1044 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1046 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1048 for (i = 0; i < n_clouds; ++i) {
1049 init_costs += cloud_costs(clouds[i]);
1051 /* Process the cloud. */
1052 process_cloud(clouds[i]);
1054 all_costs += clouds[i]->costs;
1055 final_costs += cloud_costs(clouds[i]);
1058 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1063 static int co_solve_heuristic_new(copy_opt_t *co)
1067 ir_nodemap_init(&env.map, co->irg);
1068 obstack_init(&env.obst);
1072 env.n_regs = co->cls->n_regs;
1073 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1074 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1075 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1076 INIT_LIST_HEAD(&env.cloud_head);
1080 writeback_colors(&env);
1081 obstack_free(&env.obst, NULL);
1082 ir_nodemap_destroy(&env.map);
1086 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1087 void be_init_copyheur2(void)
1089 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1090 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1091 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1092 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1094 static co_algo_info copyheur = {
1095 co_solve_heuristic_new, 0
1098 lc_opt_add_table(co2_grp, options);
1099 be_register_copyopt("heur2", ©heur);