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"
59 #define DUMP_ALL 2 * DUMP_CLOUD - 1
61 static unsigned dump_flags = 0;
62 static int subtree_iter = 4;
63 static int max_depth = 20;
64 static double constr_factor = 0.9;
66 static const lc_opt_enum_mask_items_t dump_items[] = {
67 { "before", DUMP_BEFORE },
68 { "after", DUMP_AFTER },
69 { "cloud", DUMP_CLOUD },
74 static lc_opt_enum_mask_var_t dump_var = {
75 &dump_flags, dump_items
78 static const lc_opt_table_entry_t options[] = {
79 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
80 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
81 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
82 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
88 / ___|| |_ __ _ _ __| |_
89 \___ \| __/ _` | '__| __|
90 ___) | || (_| | | | |_
91 |____/ \__\__,_|_| \__|
95 #define INFEASIBLE(cost) ((cost) == INT_MAX)
97 typedef unsigned col_t;
99 typedef struct co2_irn_t co2_irn_t;
100 typedef struct co2_cloud_t co2_cloud_t;
101 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
112 bitset_t *allocatable_regs;
116 struct list_head cloud_head;
117 DEBUG_ONLY(firm_dbg_module_t *dbg;)
122 affinity_node_t *aff;
123 co2_irn_t *touched_next;
126 int last_color_change;
129 unsigned tmp_fixed : 1;
130 unsigned is_constrained : 1;
131 struct list_head changed_list;
134 struct co2_cloud_irn_t {
135 struct co2_irn_t inh;
139 co2_cloud_irn_t *mst_parent;
142 co2_cloud_irn_t **mst_childs;
147 col_cost_pair_t *tmp_coloring;
148 struct list_head cloud_list;
149 struct list_head mst_list;
164 co2_cloud_irn_t *master;
165 co2_cloud_irn_t *mst_root;
166 co2_cloud_irn_t **seq;
167 struct list_head members_head;
168 struct list_head list;
172 co2_cloud_irn_t *src, *tgt;
176 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
178 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
180 co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
182 ci = OALLOCZ(&env->obst, co2_irn_t);
184 INIT_LIST_HEAD(&ci->changed_list);
185 ci->touched_next = env->touched;
186 ci->orig_col = get_irn_col(node);
191 ir_nodemap_insert(&env->map, node, ci);
196 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
198 co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
200 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
202 INIT_LIST_HEAD(&ci->inh.changed_list);
203 ci->inh.touched_next = env->touched;
204 ci->inh.orig_col = get_irn_col(node);
205 env->touched = &ci->inh;
207 ci->inh.aff = get_affinity_info(env->co, node);
209 INIT_LIST_HEAD(&ci->cloud_list);
212 ir_nodemap_insert(&env->map, node, ci);
217 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
219 static int cmp_clouds_gt(const void *a, const void *b)
221 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
222 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
223 double c = CLOUD_WEIGHT(*p);
224 double d = CLOUD_WEIGHT(*q);
225 return QSORT_CMP(d, c);
229 * An order on color/costs pairs.
230 * If the costs are equal, we use the color as a kind of normalization.
232 static int col_cost_pair_lt(const void *a, const void *b)
234 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
235 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
238 return QSORT_CMP(c, d);
241 static int cmp_edges(const void *a, const void *b)
243 const edge_t *p = (const edge_t*)a;
244 const edge_t *q = (const edge_t*)b;
245 return QSORT_CMP(q->costs, p->costs);
248 static col_t get_col(co2_t *env, const ir_node *irn)
250 co2_irn_t *ci = get_co2_irn(env, irn);
251 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
254 static inline int color_is_fix(co2_t *env, const ir_node *irn)
256 co2_irn_t *ci = get_co2_irn(env, irn);
257 return ci->fixed || ci->tmp_fixed;
260 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
262 if (ci->adm_cache == NULL) {
263 const arch_register_req_t *req;
264 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
265 req = arch_get_irn_register_req(ci->irn);
267 if (arch_register_req_is(req, limited)) {
271 for (i = 0; i < n; ++i) {
272 if (rbitset_is_set(req->limited, i))
273 bitset_set(ci->adm_cache, i);
275 ci->is_constrained = 1;
277 bitset_copy(ci->adm_cache, env->allocatable_regs);
281 return ci->adm_cache;
284 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
286 bitset_copy(bs, get_adm(env, ci));
290 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
292 bitset_t *bs = get_adm(env, ci);
293 return bitset_is_set(bs, col);
296 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
300 return ci->is_constrained;
303 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
305 const arch_register_req_t *req = arch_get_irn_register_req(irn);
307 if (arch_register_req_is(req, limited)) {
308 unsigned n_regs = env->co->cls->n_regs;
309 unsigned n_constr = 0;
312 n_constr = rbitset_popcount(req->limited, n_regs);
313 for (i = 0; i < n_regs; ++i) {
314 if (rbitset_is_set(req->limited, i)) {
315 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
322 * Determine costs which shall indicate how cheap/expensive it is to try
323 * to assign a node some color.
324 * The costs are computed for all colors. INT_MAX means that it is impossible
325 * to give the node that specific color.
327 * @param env The co2 this pointer.
328 * @param irn The node.
329 * @param col_costs An array of colors x costs where the costs are written to.
331 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
333 const ir_node *irn = ci->irn;
334 be_ifg_t *ifg = env->co->cenv->ifg;
335 int n_regs = env->co->cls->n_regs;
336 affinity_node_t *a = ci->aff;
339 neighbours_iter_t it;
342 /* Put all forbidden colors into the aux bitset. */
343 bitset_t *const admissible = bitset_alloca(n_regs);
344 admissible_colors(env, ci, admissible);
346 for (i = 0; i < n_regs; ++i) {
347 col_costs[i].col = i;
348 col_costs[i].costs = 0;
352 co_gs_foreach_neighb(a, n) {
353 if (color_is_fix(env, n->irn)) {
354 col_t col = get_col(env, n->irn);
355 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
358 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
362 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
363 col_t col = get_col(env, pos);
364 if (color_is_fix(env, pos)) {
365 col_costs[col].costs = INT_MAX;
368 incur_constraint_costs(env, pos, col_costs, INT_MAX);
369 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
372 be_ifg_neighbours_break(&it);
374 /* Set the costs to infinity for each color which is not allowed at this node. */
375 bitset_foreach_clear(admissible, elm) {
376 col_costs[elm].costs = INT_MAX;
381 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
383 int n_regs = env->co->cls->n_regs;
386 for (i = 0; i < n_regs; ++i) {
388 seq[i].costs = INT_MAX;
392 assert(is_color_admissible(env, ci, col));
398 static void reject_coloring(struct list_head *h)
400 list_for_each_entry(co2_irn_t, pos, h, changed_list)
404 static void materialize_coloring(struct list_head *h)
406 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
407 pos->orig_col = pos->tmp_col;
412 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
414 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
416 int n_regs = env->co->cls->n_regs;
417 be_ifg_t *ifg = env->co->cenv->ifg;
418 co2_irn_t *ci = get_co2_irn(env, irn);
423 if (depth >= max_depth)
426 for (i = 0; i < n_regs; ++i) {
427 col_t tgt_col = col_list[i].col;
428 unsigned costs = col_list[i].costs;
431 struct list_head changed;
433 neighbours_iter_t it;
435 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
437 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
438 if (INFEASIBLE(costs)) {
439 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
444 /* Set the new color of the node and mark the node as temporarily fixed. */
445 ci->tmp_col = tgt_col;
449 If that color has costs > 0, there's at least one neighbor having that color,
450 so we will try to change the neighbors' colors, too.
452 INIT_LIST_HEAD(&changed);
453 list_add(&ci->changed_list, &changed);
455 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
457 /* try to re-color the neighbor if it has the target color. */
458 if (get_col(env, n) == tgt_col) {
459 struct list_head tmp;
462 Try to change the color of the neighbor and record all nodes which
463 get changed in the tmp list. Add this list to the "changed" list for
464 that color. If we did not succeed to change the color of the neighbor,
465 we bail out and try the next color.
467 INIT_LIST_HEAD(&tmp);
468 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
469 list_splice(&tmp, &changed);
474 be_ifg_neighbours_break(&it);
477 We managed to assign the target color to all neighbors, so from the perspective
478 of the current node, every thing was ok and we can return safely.
481 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
482 list_splice(&changed, parent_changed);
488 If not, that color did not succeed and we unfix all nodes we touched
489 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
492 reject_coloring(&changed);
498 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
500 co2_irn_t *ci = get_co2_irn(env, irn);
502 col_t col = get_col(env, irn);
504 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
506 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
507 if (col != not_col) {
508 if (!ci->tmp_fixed) {
513 list_add(&ci->changed_list, parent_changed);
517 /* The node has the color it should not have _and_ has not been visited yet. */
518 if (!color_is_fix(env, irn)) {
519 int n_regs = env->co->cls->n_regs;
520 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
522 /* Get the costs for giving the node a specific color. */
523 determine_color_costs(env, ci, csts);
525 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
526 csts[not_col].costs = INT_MAX;
528 /* sort the colors according costs, cheapest first. */
529 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
531 /* Try recoloring the node using the color list. */
532 res = recolor(env, irn, csts, parent_changed, depth);
535 /* If we came here, everything went ok. */
539 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
541 co2_irn_t *ci = get_co2_irn(env, irn);
542 col_t col = get_col(env, irn);
545 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
547 /* the node has the wanted color. That's fine, mark it as visited and return. */
548 if (col == tgt_col) {
549 if (!ci->tmp_fixed) {
552 list_add(&ci->changed_list, parent_changed);
559 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
560 int n_regs = env->co->cls->n_regs;
561 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
563 /* Get the costs for giving the node a specific color. */
564 single_color_cost(env, ci, tgt_col, seq);
566 /* Try recoloring the node using the color list. */
567 res = recolor(env, irn, seq, parent_changed, depth);
572 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
577 * Examine the costs of the current coloring concerning a MST subtree.
578 * @param ci The subtree root.
579 * @param col The color of @p ci.
580 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
582 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
584 int *front = FRONT_BASE(ci, col);
588 for (i = 0; i < ci->mst_n_childs; ++i) {
589 co2_cloud_irn_t *chld = ci->mst_childs[i];
590 col_t chld_col = front[i];
592 cost += examine_subtree_coloring(chld, chld_col);
593 cost += col != chld_col ? chld->mst_costs : 0;
600 * Determine color badnesses of a node.
601 * Badness means that it is unlikely that the node in question can
602 * obtain a color. The higher the badness, the more unlikely it is that
603 * the node can be assigned that color.
604 * @param ci The node.
605 * @param badness An integer array as long as there are registers.
606 * @note The array <code>badness</code> is not cleared.
608 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
610 co2_t *env = ci->cloud->env;
611 co2_irn_t *ir = &ci->inh;
612 int n_regs = env->n_regs;
613 be_ifg_t *ifg = env->co->cenv->ifg;
614 bitset_t *bs = bitset_alloca(n_regs);
617 neighbours_iter_t it;
619 admissible_colors(env, &ci->inh, bs);
620 bitset_foreach_clear(bs, elm)
621 badness[elm] = ci->costs;
623 /* Use constrained/fixed interfering neighbors to influence the color badness */
624 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
625 co2_irn_t *ni = get_co2_irn(env, irn);
627 admissible_colors(env, ni, bs);
628 if (bitset_popcount(bs) == 1) {
629 size_t c = bitset_next_set(bs, 0);
630 badness[c] += ci->costs;
633 else if (ni->fixed) {
634 col_t c = get_col(env, ni->irn);
635 badness[c] += ci->costs;
638 be_ifg_neighbours_break(&it);
642 * Determine the badness of a MST subtree.
643 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
644 * @see node_color_badness() for a definition of badness.
645 * @param ci The root of the subtree.
646 * @param depth Depth for debugging purposes.
648 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
650 co2_t *env = ci->cloud->env;
653 node_color_badness(ci, ci->color_badness);
655 /* Collect the color badness for the whole subtree */
656 for (i = 0; i < ci->mst_n_childs; ++i) {
657 co2_cloud_irn_t *child = ci->mst_childs[i];
658 determine_color_badness(child, depth + 1);
660 for (j = 0; j < env->n_regs; ++j)
661 ci->color_badness[j] += child->color_badness[j];
664 for (j = 0; j < env->n_regs; ++j)
665 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
669 * Unfix all nodes in a MST subtree.
671 static void unfix_subtree(co2_cloud_irn_t *ci)
676 for (i = 0; i < ci->mst_n_childs; ++i)
677 unfix_subtree(ci->mst_childs[i]);
680 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
682 co2_t *env = ci->cloud->env;
683 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
684 int is_root = ci->mst_parent == ci;
685 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
686 int min_badness = INT_MAX;
687 int best_col_costs = INT_MAX;
689 int n_regs = env->n_regs;
690 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
692 struct list_head changed;
695 for (i = 0; i < n_regs; ++i) {
696 int badness = ci->color_badness[i];
699 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
701 min_badness = MIN(min_badness, badness);
704 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
705 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
706 seq[parent_col].costs = min_badness - 1;
708 /* Sort the colors. The will be processed in that ordering. */
709 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
711 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
712 INIT_LIST_HEAD(&changed);
713 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
714 col_t col = seq[i].col;
715 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
717 int subtree_costs, sum_costs;
719 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
722 INIT_LIST_HEAD(&changed);
723 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
725 materialize_coloring(&changed);
732 for (j = 0; j < ci->mst_n_childs; ++j) {
733 co2_cloud_irn_t *child = ci->mst_childs[j];
734 ok = coalesce_top_down(child, j, depth + 1) >= 0;
736 child->inh.fixed = 1;
741 /* If the subtree could not be colored, we have to try another color. */
745 subtree_costs = examine_subtree_coloring(ci, col);
746 sum_costs = subtree_costs + add_cost;
747 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
749 if (sum_costs < best_col_costs) {
751 best_col_costs = sum_costs;
752 ci->col_costs[col] = subtree_costs;
760 int *front = FRONT_BASE(ci->mst_parent, parent_col);
761 front[child_nr] = best_col;
767 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
769 be_ifg_t *ifg = env->co->cenv->ifg;
770 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
776 /* mark the node as visited and add it to the cloud. */
778 list_add(&ci->cloud_list, &cloud->members_head);
780 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
782 /* determine the nodes costs */
783 co_gs_foreach_neighb(a, n) {
785 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
786 if (be_ifg_connected(ifg, a->irn, n->irn))
787 cloud->inevit += n->costs;
790 /* add the node's cost to the total costs of the cloud. */
792 cloud->costs += costs;
793 cloud->n_constr += is_constrained(env, &ci->inh);
794 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
795 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
798 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
799 if (costs >= curr_costs) {
804 /* add all the neighbors of the node to the cloud. */
805 co_gs_foreach_neighb(a, n) {
806 affinity_node_t *an = get_affinity_info(env->co, n->irn);
808 populate_cloud(env, cloud, an, curr_costs);
812 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
814 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
817 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
818 memset(cloud, 0, sizeof(cloud[0]));
819 INIT_LIST_HEAD(&cloud->members_head);
820 INIT_LIST_HEAD(&cloud->list);
821 list_add(&cloud->list, &env->cloud_head);
822 cloud->best_costs = INT_MAX;
825 populate_cloud(env, cloud, a, 0);
826 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
828 /* Also allocate space for the node sequence and compute that sequence. */
829 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
832 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
834 cloud->seq[i++] = ci;
836 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
841 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
843 const ir_node *irn = ci->inh.irn;
844 int *front = FRONT_BASE(ci, col);
846 struct list_head changed;
848 INIT_LIST_HEAD(&changed);
850 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
851 change_color_single(ci->cloud->env, irn, col, &changed, depth);
852 materialize_coloring(&changed);
854 for (i = 0; i < ci->mst_n_childs; ++i) {
855 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
859 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
861 while (ci != ci->mst_parent)
867 static void process_cloud(co2_cloud_t *cloud)
869 co2_t *env = cloud->env;
870 int n_regs = env->n_regs;
872 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
879 /* Collect all edges in the cloud on an obstack and sort the increasingly */
880 obstack_init(&cloud->obst);
881 for (i = 0; i < cloud->n_memb; ++i) {
882 co2_cloud_irn_t *ci = cloud->seq[i];
884 co_gs_foreach_neighb(ci->inh.aff, n) {
885 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
886 if (ci->index < ni->index) {
891 obstack_grow(&cloud->obst, &e, sizeof(e));
896 edges = (edge_t*)obstack_finish(&cloud->obst);
897 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
899 /* Compute the maximum spanning tree using Kruskal/Union-Find */
900 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
901 for (i = 0; i < n_edges; ++i) {
902 edge_t *e = &edges[i];
903 co2_cloud_irn_t *rs = find_mst_root(e->src);
904 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
906 /* if the union/find roots are different */
908 int si = e->src->index;
909 int ti = e->tgt->index;
913 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
915 /* this edge is in the MST, so set it in the bitset. */
916 mst_edges[si * cloud->n_memb + ti] = e->costs;
917 mst_edges[ti * cloud->n_memb + si] = e->costs;
920 obstack_free(&cloud->obst, edges);
922 cloud->master->mst_parent = cloud->master;
923 cloud->mst_root = cloud->master;
924 q = new_pdeq1(cloud->master);
925 while (!pdeq_empty(q)) {
926 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
927 int ofs = ci->index * cloud->n_memb;
928 int end = ofs + cloud->n_memb;
931 ci->mst_n_childs = 0;
932 for (i = ofs; i < end; ++i) {
933 if (mst_edges[i] != 0) {
935 co2_cloud_irn_t *child = cloud->seq[i - ofs];
937 /* put the child to the worklist */
940 /* make ci the parent of the child and add the child to the children array of the parent */
941 child->mst_parent = ci;
942 child->mst_costs = mst_edges[i];
944 obstack_ptr_grow(&cloud->obst, child);
946 mst_edges[other * cloud->n_memb + ci->index] = 0;
951 obstack_ptr_grow(&cloud->obst, NULL);
952 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
958 DBG((env->dbg, LEVEL_3, "mst:\n"));
959 for (i = 0; i < cloud->n_memb; ++i) {
960 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
961 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
964 for (i = 0; i < cloud->n_memb; ++i) {
965 co2_cloud_irn_t *ci = cloud->seq[i];
966 int n_childs = ci->mst_n_childs;
969 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
970 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
971 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
972 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
974 for (j = 0; j < env->n_regs; j++)
975 ci->col_costs[j] = INT_MAX;
978 determine_color_badness(cloud->mst_root, 0);
979 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
980 unfix_subtree(cloud->mst_root);
981 apply_coloring(cloud->mst_root, best_col, 0);
983 /* The coloring should represent the one with the best costs. */
984 //materialize_coloring(&changed);
985 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
986 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
988 /* Fix all nodes in the cloud. */
989 for (i = 0; i < cloud->n_memb; ++i)
990 cloud->seq[i]->inh.fixed = 1;
992 /* Free all space used while optimizing this cloud. */
993 obstack_free(&cloud->obst, NULL);
996 static int cloud_costs(co2_cloud_t *cloud)
1000 for (i = 0; i < cloud->n_memb; ++i) {
1001 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1002 col_t col = get_col(cloud->env, ci->irn);
1003 co_gs_foreach_neighb(ci->aff, n) {
1004 col_t n_col = get_col(cloud->env, n->irn);
1005 costs += col != n_col ? n->costs : 0;
1012 static void writeback_colors(co2_t *env)
1016 for (irn = env->touched; irn; irn = irn->touched_next) {
1017 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1018 arch_set_irn_register((ir_node*)irn->irn, reg);
1022 static void process(co2_t *env)
1024 co2_cloud_t **clouds;
1029 int final_costs = 0;
1032 co_gs_foreach_aff_node(env->co, a) {
1033 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1042 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1043 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1045 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1047 for (i = 0; i < n_clouds; ++i) {
1048 init_costs += cloud_costs(clouds[i]);
1050 /* Process the cloud. */
1051 process_cloud(clouds[i]);
1053 all_costs += clouds[i]->costs;
1054 final_costs += cloud_costs(clouds[i]);
1057 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1062 static int co_solve_heuristic_new(copy_opt_t *co)
1066 ir_nodemap_init(&env.map, co->irg);
1067 obstack_init(&env.obst);
1071 env.n_regs = co->cls->n_regs;
1072 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1073 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1074 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1075 INIT_LIST_HEAD(&env.cloud_head);
1079 writeback_colors(&env);
1080 obstack_free(&env.obst, NULL);
1081 ir_nodemap_destroy(&env.map);
1085 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1086 void be_init_copyheur2(void)
1088 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1089 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1090 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1091 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1093 static co_algo_info copyheur = {
1094 co_solve_heuristic_new, 0
1097 lc_opt_add_table(co2_grp, options);
1098 be_register_copyopt("heur2", ©heur);