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
30 #include "lc_opts_enum.h"
38 #include "raw_bitset.h"
41 #include "bitfiddle.h"
43 #include "irgraph_t.h"
48 #include "irnodemap.h"
53 #include "becopyopt.h"
54 #include "becopyopt_t.h"
55 #include "bechordal_t.h"
61 #define DUMP_ALL 2 * DUMP_CLOUD - 1
63 static unsigned dump_flags = 0;
64 static int subtree_iter = 4;
65 static int max_depth = 20;
66 static double constr_factor = 0.9;
68 static const lc_opt_enum_mask_items_t dump_items[] = {
69 { "before", DUMP_BEFORE },
70 { "after", DUMP_AFTER },
71 { "cloud", DUMP_CLOUD },
76 static lc_opt_enum_mask_var_t dump_var = {
77 &dump_flags, dump_items
80 static const lc_opt_table_entry_t options[] = {
81 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
82 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
83 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
84 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
90 / ___|| |_ __ _ _ __| |_
91 \___ \| __/ _` | '__| __|
92 ___) | || (_| | | | |_
93 |____/ \__\__,_|_| \__|
97 #define INFEASIBLE(cost) ((cost) == INT_MAX)
99 typedef unsigned col_t;
101 typedef struct co2_irn_t co2_irn_t;
102 typedef struct co2_cloud_t co2_cloud_t;
103 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
114 bitset_t *allocatable_regs;
118 struct list_head cloud_head;
119 DEBUG_ONLY(firm_dbg_module_t *dbg;)
124 affinity_node_t *aff;
125 co2_irn_t *touched_next;
128 int last_color_change;
131 unsigned tmp_fixed : 1;
132 unsigned is_constrained : 1;
133 struct list_head changed_list;
136 struct co2_cloud_irn_t {
137 struct co2_irn_t inh;
141 co2_cloud_irn_t *mst_parent;
144 co2_cloud_irn_t **mst_childs;
149 col_cost_pair_t *tmp_coloring;
150 struct list_head cloud_list;
151 struct list_head mst_list;
166 co2_cloud_irn_t *master;
167 co2_cloud_irn_t *mst_root;
168 co2_cloud_irn_t **seq;
169 struct list_head members_head;
170 struct list_head list;
174 co2_cloud_irn_t *src, *tgt;
178 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
180 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
182 co2_irn_t *ci = ir_nodemap_get(&env->map, node);
184 ci = OALLOCZ(&env->obst, co2_irn_t);
186 INIT_LIST_HEAD(&ci->changed_list);
187 ci->touched_next = env->touched;
188 ci->orig_col = get_irn_col(node);
193 ir_nodemap_insert(&env->map, node, ci);
198 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
200 co2_cloud_irn_t *ci = ir_nodemap_get(&env->map, node);
202 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
204 INIT_LIST_HEAD(&ci->inh.changed_list);
205 ci->inh.touched_next = env->touched;
206 ci->inh.orig_col = get_irn_col(node);
207 env->touched = &ci->inh;
209 ci->inh.aff = get_affinity_info(env->co, node);
211 INIT_LIST_HEAD(&ci->cloud_list);
214 ir_nodemap_insert(&env->map, node, ci);
219 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
221 static int cmp_clouds_gt(const void *a, const void *b)
223 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
224 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
225 double c = CLOUD_WEIGHT(*p);
226 double d = CLOUD_WEIGHT(*q);
227 return QSORT_CMP(d, c);
231 * An order on color/costs pairs.
232 * If the costs are equal, we use the color as a kind of normalization.
234 static int col_cost_pair_lt(const void *a, const void *b)
236 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
237 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
240 return QSORT_CMP(c, d);
243 static int cmp_edges(const void *a, const void *b)
245 const edge_t *p = (const edge_t*)a;
246 const edge_t *q = (const edge_t*)b;
247 return QSORT_CMP(q->costs, p->costs);
250 static col_t get_col(co2_t *env, const ir_node *irn)
252 co2_irn_t *ci = get_co2_irn(env, irn);
253 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
256 static inline int color_is_fix(co2_t *env, const ir_node *irn)
258 co2_irn_t *ci = get_co2_irn(env, irn);
259 return ci->fixed || ci->tmp_fixed;
262 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
264 if (ci->adm_cache == NULL) {
265 const arch_register_req_t *req;
266 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
267 req = arch_get_irn_register_req(ci->irn);
269 if (arch_register_req_is(req, limited)) {
273 for (i = 0; i < n; ++i) {
274 if (rbitset_is_set(req->limited, i))
275 bitset_set(ci->adm_cache, i);
277 ci->is_constrained = 1;
279 bitset_copy(ci->adm_cache, env->allocatable_regs);
283 return ci->adm_cache;
286 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
288 bitset_copy(bs, get_adm(env, ci));
292 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
294 bitset_t *bs = get_adm(env, ci);
295 return bitset_is_set(bs, col);
298 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
302 return ci->is_constrained;
305 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
307 const arch_register_req_t *req = arch_get_irn_register_req(irn);
309 if (arch_register_req_is(req, limited)) {
310 unsigned n_regs = env->co->cls->n_regs;
311 unsigned n_constr = 0;
314 n_constr = rbitset_popcount(req->limited, n_regs);
315 for (i = 0; i < n_regs; ++i) {
316 if (rbitset_is_set(req->limited, i)) {
317 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
324 * Determine costs which shall indicate how cheap/expensive it is to try
325 * to assign a node some color.
326 * The costs are computed for all colors. INT_MAX means that it is impossible
327 * to give the node that specific color.
329 * @param env The co2 this pointer.
330 * @param irn The node.
331 * @param col_costs An array of colors x costs where the costs are written to.
333 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
335 const ir_node *irn = ci->irn;
336 be_ifg_t *ifg = env->co->cenv->ifg;
337 int n_regs = env->co->cls->n_regs;
338 bitset_t *forb = bitset_alloca(n_regs);
339 affinity_node_t *a = ci->aff;
343 neighbours_iter_t it;
346 /* Put all forbidden colors into the aux bitset. */
347 admissible_colors(env, ci, forb);
348 bitset_flip_all(forb);
350 for (i = 0; i < n_regs; ++i) {
351 col_costs[i].col = i;
352 col_costs[i].costs = 0;
358 co_gs_foreach_neighb(a, n) {
359 if (color_is_fix(env, n->irn)) {
360 col_t col = get_col(env, n->irn);
361 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
364 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
368 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
369 col_t col = get_col(env, pos);
370 if (color_is_fix(env, pos)) {
371 col_costs[col].costs = INT_MAX;
374 incur_constraint_costs(env, pos, col_costs, INT_MAX);
375 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
378 be_ifg_neighbours_break(&it);
380 /* Set the costs to infinity for each color which is not allowed at this node. */
381 bitset_foreach(forb, elm) {
382 col_costs[elm].costs = INT_MAX;
387 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
389 int n_regs = env->co->cls->n_regs;
392 for (i = 0; i < n_regs; ++i) {
394 seq[i].costs = INT_MAX;
398 assert(is_color_admissible(env, ci, col));
404 static void reject_coloring(struct list_head *h)
408 list_for_each_entry(co2_irn_t, pos, h, changed_list)
412 static void materialize_coloring(struct list_head *h)
416 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
417 pos->orig_col = pos->tmp_col;
422 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
424 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
426 int n_regs = env->co->cls->n_regs;
427 be_ifg_t *ifg = env->co->cenv->ifg;
428 co2_irn_t *ci = get_co2_irn(env, irn);
433 if (depth >= max_depth)
436 for (i = 0; i < n_regs; ++i) {
437 col_t tgt_col = col_list[i].col;
438 unsigned costs = col_list[i].costs;
441 struct list_head changed;
443 neighbours_iter_t it;
445 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
447 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
448 if (INFEASIBLE(costs)) {
449 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
454 /* Set the new color of the node and mark the node as temporarily fixed. */
455 ci->tmp_col = tgt_col;
459 If that color has costs > 0, there's at least one neighbor having that color,
460 so we will try to change the neighbors' colors, too.
462 INIT_LIST_HEAD(&changed);
463 list_add(&ci->changed_list, &changed);
465 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
467 /* try to re-color the neighbor if it has the target color. */
468 if (get_col(env, n) == tgt_col) {
469 struct list_head tmp;
472 Try to change the color of the neighbor and record all nodes which
473 get changed in the tmp list. Add this list to the "changed" list for
474 that color. If we did not succeed to change the color of the neighbor,
475 we bail out and try the next color.
477 INIT_LIST_HEAD(&tmp);
478 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
479 list_splice(&tmp, &changed);
484 be_ifg_neighbours_break(&it);
487 We managed to assign the target color to all neighbors, so from the perspective
488 of the current node, every thing was ok and we can return safely.
491 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
492 list_splice(&changed, parent_changed);
498 If not, that color did not succeed and we unfix all nodes we touched
499 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
502 reject_coloring(&changed);
508 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
510 co2_irn_t *ci = get_co2_irn(env, irn);
512 col_t col = get_col(env, irn);
514 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
516 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
517 if (col != not_col) {
518 if (!ci->tmp_fixed) {
523 list_add(&ci->changed_list, parent_changed);
527 /* The node has the color it should not have _and_ has not been visited yet. */
528 if (!color_is_fix(env, irn)) {
529 int n_regs = env->co->cls->n_regs;
530 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
532 /* Get the costs for giving the node a specific color. */
533 determine_color_costs(env, ci, csts);
535 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
536 csts[not_col].costs = INT_MAX;
538 /* sort the colors according costs, cheapest first. */
539 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
541 /* Try recoloring the node using the color list. */
542 res = recolor(env, irn, csts, parent_changed, depth);
545 /* If we came here, everything went ok. */
549 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
551 co2_irn_t *ci = get_co2_irn(env, irn);
552 col_t col = get_col(env, irn);
555 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
557 /* the node has the wanted color. That's fine, mark it as visited and return. */
558 if (col == tgt_col) {
559 if (!ci->tmp_fixed) {
562 list_add(&ci->changed_list, parent_changed);
569 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
570 int n_regs = env->co->cls->n_regs;
571 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
573 /* Get the costs for giving the node a specific color. */
574 single_color_cost(env, ci, tgt_col, seq);
576 /* Try recoloring the node using the color list. */
577 res = recolor(env, irn, seq, parent_changed, depth);
582 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
587 * Examine the costs of the current coloring concerning a MST subtree.
588 * @param ci The subtree root.
589 * @param col The color of @p ci.
590 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
592 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
594 int *front = FRONT_BASE(ci, col);
598 for (i = 0; i < ci->mst_n_childs; ++i) {
599 co2_cloud_irn_t *chld = ci->mst_childs[i];
600 col_t chld_col = front[i];
602 cost += examine_subtree_coloring(chld, chld_col);
603 cost += col != chld_col ? chld->mst_costs : 0;
610 * Determine color badnesses of a node.
611 * Badness means that it is unlikely that the node in question can
612 * obtain a color. The higher the badness, the more unlikely it is that
613 * the node can be assigned that color.
614 * @param ci The node.
615 * @param badness An integer array as long as there are registers.
616 * @note The array <code>badness</code> is not cleared.
618 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
620 co2_t *env = ci->cloud->env;
621 co2_irn_t *ir = &ci->inh;
622 int n_regs = env->n_regs;
623 be_ifg_t *ifg = env->co->cenv->ifg;
624 bitset_t *bs = bitset_alloca(n_regs);
628 neighbours_iter_t it;
630 admissible_colors(env, &ci->inh, bs);
632 bitset_foreach(bs, elm)
633 badness[elm] = ci->costs;
635 /* Use constrained/fixed interfering neighbors to influence the color badness */
636 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
637 co2_irn_t *ni = get_co2_irn(env, irn);
639 admissible_colors(env, ni, bs);
640 if (bitset_popcount(bs) == 1) {
641 size_t c = bitset_next_set(bs, 0);
642 badness[c] += ci->costs;
645 else if (ni->fixed) {
646 col_t c = get_col(env, ni->irn);
647 badness[c] += ci->costs;
650 be_ifg_neighbours_break(&it);
654 * Determine the badness of a MST subtree.
655 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
656 * @see node_color_badness() for a definition of badness.
657 * @param ci The root of the subtree.
658 * @param depth Depth for debugging purposes.
660 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
662 co2_t *env = ci->cloud->env;
665 node_color_badness(ci, ci->color_badness);
667 /* Collect the color badness for the whole subtree */
668 for (i = 0; i < ci->mst_n_childs; ++i) {
669 co2_cloud_irn_t *child = ci->mst_childs[i];
670 determine_color_badness(child, depth + 1);
672 for (j = 0; j < env->n_regs; ++j)
673 ci->color_badness[j] += child->color_badness[j];
676 for (j = 0; j < env->n_regs; ++j)
677 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
681 * Unfix all nodes in a MST subtree.
683 static void unfix_subtree(co2_cloud_irn_t *ci)
688 for (i = 0; i < ci->mst_n_childs; ++i)
689 unfix_subtree(ci->mst_childs[i]);
692 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
694 co2_t *env = ci->cloud->env;
695 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
696 int is_root = ci->mst_parent == ci;
697 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
698 int min_badness = INT_MAX;
699 int best_col_costs = INT_MAX;
701 int n_regs = env->n_regs;
702 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
704 struct list_head changed;
707 for (i = 0; i < n_regs; ++i) {
708 int badness = ci->color_badness[i];
711 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
713 min_badness = MIN(min_badness, badness);
716 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
717 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
718 seq[parent_col].costs = min_badness - 1;
720 /* Sort the colors. The will be processed in that ordering. */
721 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
723 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
724 INIT_LIST_HEAD(&changed);
725 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
726 col_t col = seq[i].col;
727 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
729 int subtree_costs, sum_costs;
731 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
734 INIT_LIST_HEAD(&changed);
735 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
737 materialize_coloring(&changed);
744 for (j = 0; j < ci->mst_n_childs; ++j) {
745 co2_cloud_irn_t *child = ci->mst_childs[j];
746 ok = coalesce_top_down(child, j, depth + 1) >= 0;
748 child->inh.fixed = 1;
753 /* If the subtree could not be colored, we have to try another color. */
757 subtree_costs = examine_subtree_coloring(ci, col);
758 sum_costs = subtree_costs + add_cost;
759 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
761 if (sum_costs < best_col_costs) {
763 best_col_costs = sum_costs;
764 ci->col_costs[col] = subtree_costs;
772 int *front = FRONT_BASE(ci->mst_parent, parent_col);
773 front[child_nr] = best_col;
779 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
781 be_ifg_t *ifg = env->co->cenv->ifg;
782 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
789 /* mark the node as visited and add it to the cloud. */
791 list_add(&ci->cloud_list, &cloud->members_head);
793 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
795 /* determine the nodes costs */
796 co_gs_foreach_neighb(a, n) {
798 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
799 if (be_ifg_connected(ifg, a->irn, n->irn))
800 cloud->inevit += n->costs;
803 /* add the node's cost to the total costs of the cloud. */
805 cloud->costs += costs;
806 cloud->n_constr += is_constrained(env, &ci->inh);
807 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
808 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
811 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
812 if (costs >= curr_costs) {
817 /* add all the neighbors of the node to the cloud. */
818 co_gs_foreach_neighb(a, n) {
819 affinity_node_t *an = get_affinity_info(env->co, n->irn);
821 populate_cloud(env, cloud, an, curr_costs);
825 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
827 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
831 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
832 memset(cloud, 0, sizeof(cloud[0]));
833 INIT_LIST_HEAD(&cloud->members_head);
834 INIT_LIST_HEAD(&cloud->list);
835 list_add(&cloud->list, &env->cloud_head);
836 cloud->best_costs = INT_MAX;
839 populate_cloud(env, cloud, a, 0);
840 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
842 /* Also allocate space for the node sequence and compute that sequence. */
843 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
846 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
848 cloud->seq[i++] = ci;
850 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
855 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
857 const ir_node *irn = ci->inh.irn;
858 int *front = FRONT_BASE(ci, col);
860 struct list_head changed;
862 INIT_LIST_HEAD(&changed);
864 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
865 change_color_single(ci->cloud->env, irn, col, &changed, depth);
866 materialize_coloring(&changed);
868 for (i = 0; i < ci->mst_n_childs; ++i) {
869 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
873 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
875 while (ci != ci->mst_parent)
881 static void process_cloud(co2_cloud_t *cloud)
883 co2_t *env = cloud->env;
884 int n_regs = env->n_regs;
886 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
893 /* Collect all edges in the cloud on an obstack and sort the increasingly */
894 obstack_init(&cloud->obst);
895 for (i = 0; i < cloud->n_memb; ++i) {
896 co2_cloud_irn_t *ci = cloud->seq[i];
899 co_gs_foreach_neighb(ci->inh.aff, n) {
900 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
901 if (ci->index < ni->index) {
906 obstack_grow(&cloud->obst, &e, sizeof(e));
911 edges = (edge_t*)obstack_finish(&cloud->obst);
912 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
914 /* Compute the maximum spanning tree using Kruskal/Union-Find */
915 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
916 for (i = 0; i < n_edges; ++i) {
917 edge_t *e = &edges[i];
918 co2_cloud_irn_t *rs = find_mst_root(e->src);
919 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
921 /* if the union/find roots are different */
923 int si = e->src->index;
924 int ti = e->tgt->index;
928 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
930 /* this edge is in the MST, so set it in the bitset. */
931 mst_edges[si * cloud->n_memb + ti] = e->costs;
932 mst_edges[ti * cloud->n_memb + si] = e->costs;
935 obstack_free(&cloud->obst, edges);
937 cloud->master->mst_parent = cloud->master;
938 cloud->mst_root = cloud->master;
939 q = new_pdeq1(cloud->master);
940 while (!pdeq_empty(q)) {
941 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
942 int ofs = ci->index * cloud->n_memb;
943 int end = ofs + cloud->n_memb;
946 ci->mst_n_childs = 0;
947 for (i = ofs; i < end; ++i) {
948 if (mst_edges[i] != 0) {
950 co2_cloud_irn_t *child = cloud->seq[i - ofs];
952 /* put the child to the worklist */
955 /* make ci the parent of the child and add the child to the children array of the parent */
956 child->mst_parent = ci;
957 child->mst_costs = mst_edges[i];
959 obstack_ptr_grow(&cloud->obst, child);
961 mst_edges[other * cloud->n_memb + ci->index] = 0;
966 obstack_ptr_grow(&cloud->obst, NULL);
967 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
973 DBG((env->dbg, LEVEL_3, "mst:\n"));
974 for (i = 0; i < cloud->n_memb; ++i) {
975 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
976 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
979 for (i = 0; i < cloud->n_memb; ++i) {
980 co2_cloud_irn_t *ci = cloud->seq[i];
981 int n_childs = ci->mst_n_childs;
984 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
985 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
986 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
987 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
989 for (j = 0; j < env->n_regs; j++)
990 ci->col_costs[j] = INT_MAX;
993 determine_color_badness(cloud->mst_root, 0);
994 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
995 unfix_subtree(cloud->mst_root);
996 apply_coloring(cloud->mst_root, best_col, 0);
998 /* The coloring should represent the one with the best costs. */
999 //materialize_coloring(&changed);
1000 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1001 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1003 /* Fix all nodes in the cloud. */
1004 for (i = 0; i < cloud->n_memb; ++i)
1005 cloud->seq[i]->inh.fixed = 1;
1007 /* Free all space used while optimizing this cloud. */
1008 obstack_free(&cloud->obst, NULL);
1011 static int cloud_costs(co2_cloud_t *cloud)
1016 for (i = 0; i < cloud->n_memb; ++i) {
1017 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1018 col_t col = get_col(cloud->env, ci->irn);
1019 co_gs_foreach_neighb(ci->aff, n) {
1020 col_t n_col = get_col(cloud->env, n->irn);
1021 costs += col != n_col ? n->costs : 0;
1028 static void writeback_colors(co2_t *env)
1032 for (irn = env->touched; irn; irn = irn->touched_next) {
1033 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1034 arch_set_irn_register((ir_node*)irn->irn, reg);
1040 ___ _____ ____ ____ ___ _____ ____ _
1041 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1042 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1043 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1044 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1048 static const char *get_dot_color_name(size_t col)
1050 static const char *const names[] = {
1084 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1087 static const char *get_dot_shape_name(co2_irn_t *ci)
1089 const arch_register_req_t *req = arch_get_irn_register_req(ci->irn);
1091 if (arch_register_req_is(req, limited))
1103 static void ifg_dump_graph_attr(FILE *f, void *self)
1106 fprintf(f, "overlay=false");
1109 static int ifg_is_dump_node(void *self, ir_node *irn)
1111 const arch_register_req_t *req = arch_get_irn_register_req(irn);
1113 return !(req->type & arch_register_req_type_ignore);
1116 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1118 co2_t *env = (co2_t*)self;
1119 co2_irn_t *ci = get_co2_irn(env, irn);
1125 co2_cloud_irn_t *cci = (co2_cloud_irn_t*) ci;
1126 if (cci->cloud && cci->cloud->mst_root == cci)
1129 if (cci->cloud && cci->cloud->mst_root)
1130 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1133 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1134 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1137 static void ifg_dump_at_end(FILE *file, void *self)
1139 co2_t *env = (co2_t*)self;
1142 co_gs_foreach_aff_node(env->co, a) {
1143 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1144 int idx = get_irn_idx(a->irn);
1147 if (ai->mst_parent != ai)
1148 fprintf(file, "\tn%d -- n%u [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1150 co_gs_foreach_neighb(a, n) {
1151 int nidx = get_irn_idx(n->irn);
1152 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1155 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1156 const char *arr = "arrowhead=dot arrowtail=dot";
1158 if (ci->mst_parent == ai)
1159 arr = "arrowtail=normal";
1160 else if (ai->mst_parent == ci)
1161 arr = "arrowhead=normal";
1163 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1169 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1171 ifg_dump_graph_attr,
1178 static void process(co2_t *env)
1182 co2_cloud_t **clouds;
1187 int final_costs = 0;
1190 co_gs_foreach_aff_node(env->co, a) {
1191 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1200 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1201 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1203 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1205 for (i = 0; i < n_clouds; ++i) {
1206 init_costs += cloud_costs(clouds[i]);
1208 /* Process the cloud. */
1209 process_cloud(clouds[i]);
1211 all_costs += clouds[i]->costs;
1212 final_costs += cloud_costs(clouds[i]);
1214 /* Dump the IFG if the user demanded it. */
1215 if (dump_flags & DUMP_CLOUD) {
1219 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1220 f = fopen(buf, "wt");
1222 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1228 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1233 int co_solve_heuristic_new(copy_opt_t *co)
1239 ir_nodemap_init(&env.map, co->irg);
1240 obstack_init(&env.obst);
1244 env.n_regs = co->cls->n_regs;
1245 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1246 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1247 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1248 INIT_LIST_HEAD(&env.cloud_head);
1250 if (dump_flags & DUMP_BEFORE) {
1251 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1252 f = fopen(buf, "wt");
1254 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1261 if (dump_flags & DUMP_AFTER) {
1262 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1263 f = fopen(buf, "wt");
1265 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1270 writeback_colors(&env);
1271 obstack_free(&env.obst, NULL);
1272 ir_nodemap_destroy(&env.map);
1276 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1277 void be_init_copyheur2(void)
1279 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1280 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1281 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1282 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1284 static co_algo_info copyheur = {
1285 co_solve_heuristic_new, 0
1288 lc_opt_add_table(co2_grp, options);
1289 be_register_copyopt("heur2", ©heur);