2 * Copyright (C) 1995-2008 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 "irphase_t.h"
44 #include "irgraph_t.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),
87 void be_init_copyheur2(void)
89 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
90 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
91 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
92 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
94 lc_opt_add_table(co2_grp, options);
97 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
101 / ___|| |_ __ _ _ __| |_
102 \___ \| __/ _` | '__| __|
103 ___) | || (_| | | | |_
104 |____/ \__\__,_|_| \__|
108 #define INFEASIBLE(cost) ((cost) == INT_MAX)
110 static be_ifg_dump_dot_cb_t ifg_dot_cb;
112 typedef unsigned col_t;
114 typedef struct _co2_irn_t co2_irn_t;
115 typedef struct _co2_cloud_t co2_cloud_t;
116 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
126 bitset_t *ignore_regs;
130 struct list_head cloud_head;
131 DEBUG_ONLY(firm_dbg_module_t *dbg;)
136 affinity_node_t *aff;
137 co2_irn_t *touched_next;
140 int last_color_change;
143 unsigned tmp_fixed : 1;
144 unsigned is_constrained : 1;
145 struct list_head changed_list;
148 struct _co2_cloud_irn_t {
149 struct _co2_irn_t inh;
153 co2_cloud_irn_t *mst_parent;
156 co2_cloud_irn_t **mst_childs;
161 col_cost_pair_t *tmp_coloring;
162 struct list_head cloud_list;
163 struct list_head mst_list;
166 struct _co2_cloud_t {
178 co2_cloud_irn_t *master;
179 co2_cloud_irn_t *mst_root;
180 co2_cloud_irn_t **seq;
181 struct list_head members_head;
182 struct list_head list;
186 co2_cloud_irn_t *src, *tgt;
190 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
192 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
193 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
195 static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
197 co2_t *env = (co2_t *) ph;
198 affinity_node_t *a = get_affinity_info(env->co, irn);
199 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
200 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
203 INIT_LIST_HEAD(&ci->changed_list);
204 ci->touched_next = env->touched;
205 ci->orig_col = get_irn_col(irn);
211 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
212 INIT_LIST_HEAD(&cci->cloud_list);
213 cci->mst_parent = cci;
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 = a;
224 const co2_cloud_t * const *q = 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 = a;
237 const col_cost_pair_t *q = b;
240 return QSORT_CMP(c, d);
243 int cmp_edges(const void *a, const void *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(phase_obst(&env->ph), env->n_regs);
267 req = arch_get_register_req(ci->irn, BE_OUT_POS(0));
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->ignore_regs);
280 bitset_flip_all(ci->adm_cache);
284 return ci->adm_cache;
287 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
289 bitset_copy(bs, get_adm(env, ci));
293 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
295 bitset_t *bs = get_adm(env, ci);
296 return bitset_is_set(bs, col);
299 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
303 return ci->is_constrained;
306 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
308 const arch_register_req_t *req;
310 req = arch_get_register_req(irn, BE_OUT_POS(0));
312 if (arch_register_req_is(req, limited)) {
313 unsigned n_regs = env->co->cls->n_regs;
314 unsigned n_constr = 0;
317 n_constr = rbitset_popcnt(req->limited, n_regs);
318 for (i = 0; i < n_regs; ++i) {
319 if (rbitset_is_set(req->limited, i)) {
320 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
327 * Determine costs which shall indicate how cheap/expensive it is to try
328 * to assign a node some color.
329 * The costs are computed for all colors. INT_MAX means that it is impossible
330 * to give the node that specific color.
332 * @param env The co2 this pointer.
333 * @param irn The node.
334 * @param col_costs An array of colors x costs where the costs are written to.
336 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
338 const ir_node *irn = ci->irn;
339 be_ifg_t *ifg = env->co->cenv->ifg;
340 int n_regs = env->co->cls->n_regs;
341 bitset_t *forb = bitset_alloca(n_regs);
342 affinity_node_t *a = ci->aff;
349 /* Put all forbidden colors into the aux bitset. */
350 admissible_colors(env, ci, forb);
351 bitset_flip_all(forb);
353 for(i = 0; i < n_regs; ++i) {
354 col_costs[i].col = i;
355 col_costs[i].costs = 0;
361 co_gs_foreach_neighb(a, n) {
362 if(color_is_fix(env, n->irn)) {
363 col_t col = get_col(env, n->irn);
364 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
367 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
371 it = be_ifg_neighbours_iter_alloca(ifg);
372 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
373 col_t col = get_col(env, pos);
374 if(color_is_fix(env, pos)) {
375 col_costs[col].costs = INT_MAX;
378 incur_constraint_costs(env, pos, col_costs, INT_MAX);
379 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
382 be_ifg_neighbours_break(ifg, it);
384 /* Set the costs to infinity for each color which is not allowed at this node. */
385 bitset_foreach(forb, elm) {
386 col_costs[elm].costs = INT_MAX;
391 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
393 int n_regs = env->co->cls->n_regs;
396 for(i = 0; i < n_regs; ++i) {
398 seq[i].costs = INT_MAX;
402 assert(is_color_admissible(env, ci, col));
408 static void reject_coloring(struct list_head *h)
412 list_for_each_entry(co2_irn_t, pos, h, changed_list)
416 static void materialize_coloring(struct list_head *h)
420 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
421 pos->orig_col = pos->tmp_col;
426 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
428 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
430 int n_regs = env->co->cls->n_regs;
431 be_ifg_t *ifg = env->co->cenv->ifg;
432 co2_irn_t *ci = get_co2_irn(env, irn);
437 if(depth >= max_depth)
440 for(i = 0; i < n_regs; ++i) {
441 col_t tgt_col = col_list[i].col;
442 unsigned costs = col_list[i].costs;
445 struct list_head changed;
449 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
451 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
452 if(INFEASIBLE(costs)) {
453 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
458 /* Set the new color of the node and mark the node as temporarily fixed. */
459 ci->tmp_col = tgt_col;
463 If that color has costs > 0, there's at least one neighbor having that color,
464 so we will try to change the neighbors' colors, too.
466 INIT_LIST_HEAD(&changed);
467 list_add(&ci->changed_list, &changed);
469 it = be_ifg_neighbours_iter_alloca(ifg);
470 be_ifg_foreach_neighbour(ifg, it, irn, n) {
472 /* try to re-color the neighbor if it has the target color. */
473 if(get_col(env, n) == tgt_col) {
474 struct list_head tmp;
477 Try to change the color of the neighbor and record all nodes which
478 get changed in the tmp list. Add this list to the "changed" list for
479 that color. If we did not succeed to change the color of the neighbor,
480 we bail out and try the next color.
482 INIT_LIST_HEAD(&tmp);
483 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
484 list_splice(&tmp, &changed);
489 be_ifg_neighbours_break(ifg, it);
492 We managed to assign the target color to all neighbors, so from the perspective
493 of the current node, every thing was ok and we can return safely.
496 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
497 list_splice(&changed, parent_changed);
503 If not, that color did not succeed and we unfix all nodes we touched
504 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
507 reject_coloring(&changed);
513 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
515 co2_irn_t *ci = get_co2_irn(env, irn);
517 col_t col = get_col(env, irn);
519 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
521 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
528 list_add(&ci->changed_list, parent_changed);
532 /* The node has the color it should not have _and_ has not been visited yet. */
533 if(!color_is_fix(env, irn)) {
534 int n_regs = env->co->cls->n_regs;
535 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
537 /* Get the costs for giving the node a specific color. */
538 determine_color_costs(env, ci, csts);
540 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
541 csts[not_col].costs = INT_MAX;
543 /* sort the colors according costs, cheapest first. */
544 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
546 /* Try recoloring the node using the color list. */
547 res = recolor(env, irn, csts, parent_changed, depth);
550 /* If we came here, everything went ok. */
554 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
556 co2_irn_t *ci = get_co2_irn(env, irn);
557 col_t col = get_col(env, irn);
560 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
562 /* the node has the wanted color. That's fine, mark it as visited and return. */
567 list_add(&ci->changed_list, parent_changed);
574 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
575 int n_regs = env->co->cls->n_regs;
576 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
578 /* Get the costs for giving the node a specific color. */
579 single_color_cost(env, ci, tgt_col, seq);
581 /* Try recoloring the node using the color list. */
582 res = recolor(env, irn, seq, parent_changed, depth);
587 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
592 * Examine the costs of the current coloring concerning a MST subtree.
593 * @param ci The subtree root.
594 * @param col The color of @p ci.
595 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
597 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
599 int *front = FRONT_BASE(ci, col);
603 for(i = 0; i < ci->mst_n_childs; ++i) {
604 co2_cloud_irn_t *chld = ci->mst_childs[i];
605 col_t chld_col = front[i];
607 cost += examine_subtree_coloring(chld, chld_col);
608 cost += col != chld_col ? chld->mst_costs : 0;
615 * Determine color badnesses of a node.
616 * Badness means that it is unlikely that the node in question can
617 * obtain a color. The higher the badness, the more unlikely it is that
618 * the node can be assigned that color.
619 * @param ci The node.
620 * @param badness An integer array as long as there are registers.
621 * @note The array <code>badness</code> is not cleared.
623 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
625 co2_t *env = ci->cloud->env;
626 co2_irn_t *ir = &ci->inh;
627 int n_regs = env->n_regs;
628 be_ifg_t *ifg = env->co->cenv->ifg;
629 bitset_t *bs = bitset_alloca(n_regs);
635 admissible_colors(env, &ci->inh, bs);
637 bitset_foreach(bs, elm)
638 badness[elm] = ci->costs;
640 /* Use constrained/fixed interfering neighbors to influence the color badness */
641 it = be_ifg_neighbours_iter_alloca(ifg);
642 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
643 co2_irn_t *ni = get_co2_irn(env, irn);
645 admissible_colors(env, ni, bs);
646 if(bitset_popcnt(bs) == 1) {
647 bitset_pos_t c = bitset_next_set(bs, 0);
648 badness[c] += ci->costs;
652 col_t c = get_col(env, ni->irn);
653 badness[c] += ci->costs;
656 be_ifg_neighbours_break(ifg, it);
660 * Determine the badness of a MST subtree.
661 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
662 * @see node_color_badness() for a definition of badness.
663 * @param ci The root of the subtree.
664 * @param depth Depth for debugging purposes.
666 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
668 co2_t *env = ci->cloud->env;
671 node_color_badness(ci, ci->color_badness);
673 /* Collect the color badness for the whole subtree */
674 for(i = 0; i < ci->mst_n_childs; ++i) {
675 co2_cloud_irn_t *child = ci->mst_childs[i];
676 determine_color_badness(child, depth + 1);
678 for(j = 0; j < env->n_regs; ++j)
679 ci->color_badness[j] += child->color_badness[j];
682 for(j = 0; j < env->n_regs; ++j)
683 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
687 * Unfix all nodes in a MST subtree.
689 static void unfix_subtree(co2_cloud_irn_t *ci)
694 for(i = 0; i < ci->mst_n_childs; ++i)
695 unfix_subtree(ci->mst_childs[i]);
698 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
700 co2_t *env = ci->cloud->env;
701 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
702 int is_root = ci->mst_parent == ci;
703 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
704 int min_badness = INT_MAX;
705 int best_col_costs = INT_MAX;
707 int n_regs = env->n_regs;
708 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
710 struct list_head changed;
713 for(i = 0; i < n_regs; ++i) {
714 int badness = ci->color_badness[i];
717 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
719 min_badness = MIN(min_badness, badness);
722 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
723 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
724 seq[parent_col].costs = min_badness - 1;
726 /* Sort the colors. The will be processed in that ordering. */
727 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
729 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
730 INIT_LIST_HEAD(&changed);
731 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
732 col_t col = seq[i].col;
733 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
735 int subtree_costs, sum_costs;
737 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
740 INIT_LIST_HEAD(&changed);
741 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
743 materialize_coloring(&changed);
750 for(j = 0; j < ci->mst_n_childs; ++j) {
751 co2_cloud_irn_t *child = ci->mst_childs[j];
752 ok = coalesce_top_down(child, j, depth + 1) >= 0;
754 child->inh.fixed = 1;
759 /* If the subtree could not be colored, we have to try another color. */
763 subtree_costs = examine_subtree_coloring(ci, col);
764 sum_costs = subtree_costs + add_cost;
765 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
767 if(sum_costs < best_col_costs) {
769 best_col_costs = sum_costs;
770 ci->col_costs[col] = subtree_costs;
778 int *front = FRONT_BASE(ci->mst_parent, parent_col);
779 front[child_nr] = best_col;
785 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
787 be_ifg_t *ifg = env->co->cenv->ifg;
788 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
795 /* mark the node as visited and add it to the cloud. */
797 list_add(&ci->cloud_list, &cloud->members_head);
799 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
801 /* determine the nodes costs */
802 co_gs_foreach_neighb(a, n) {
804 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
805 if(be_ifg_connected(ifg, a->irn, n->irn))
806 cloud->inevit += n->costs;
809 /* add the node's cost to the total costs of the cloud. */
811 cloud->costs += costs;
812 cloud->n_constr += is_constrained(env, &ci->inh);
813 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
814 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
817 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
818 if(costs >= curr_costs) {
823 /* add all the neighbors of the node to the cloud. */
824 co_gs_foreach_neighb(a, n) {
825 affinity_node_t *an = get_affinity_info(env->co, n->irn);
827 populate_cloud(env, cloud, an, curr_costs);
831 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
833 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
837 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
838 memset(cloud, 0, sizeof(cloud[0]));
839 INIT_LIST_HEAD(&cloud->members_head);
840 INIT_LIST_HEAD(&cloud->list);
841 list_add(&cloud->list, &env->cloud_head);
842 cloud->best_costs = INT_MAX;
845 populate_cloud(env, cloud, a, 0);
846 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
848 /* Also allocate space for the node sequence and compute that sequence. */
849 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
852 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
854 cloud->seq[i++] = ci;
856 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
861 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
863 const ir_node *irn = ci->inh.irn;
864 int *front = FRONT_BASE(ci, col);
866 struct list_head changed;
868 INIT_LIST_HEAD(&changed);
870 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
871 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
872 // assert(ok && "Color changing may not fail while committing the coloring");
873 materialize_coloring(&changed);
875 for(i = 0; i < ci->mst_n_childs; ++i) {
876 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
880 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
882 while(ci != ci->mst_parent)
888 static void process_cloud(co2_cloud_t *cloud)
890 co2_t *env = cloud->env;
891 int n_regs = env->n_regs;
893 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
900 /* Collect all edges in the cloud on an obstack and sort the increasingly */
901 obstack_init(&cloud->obst);
902 for(i = 0; i < cloud->n_memb; ++i) {
903 co2_cloud_irn_t *ci = cloud->seq[i];
906 co_gs_foreach_neighb(ci->inh.aff, n) {
907 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
908 if(ci->index < ni->index) {
913 obstack_grow(&cloud->obst, &e, sizeof(e));
918 edges = obstack_finish(&cloud->obst);
919 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
921 /* Compute the maximum spanning tree using Kruskal/Union-Find */
922 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
923 for(i = 0; i < n_edges; ++i) {
924 edge_t *e = &edges[i];
925 co2_cloud_irn_t *rs = find_mst_root(e->src);
926 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
928 /* if the union/find roots are different */
930 int si = e->src->index;
931 int ti = e->tgt->index;
935 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
937 /* this edge is in the MST, so set it in the bitset. */
938 mst_edges[si * cloud->n_memb + ti] = e->costs;
939 mst_edges[ti * cloud->n_memb + si] = e->costs;
942 obstack_free(&cloud->obst, edges);
944 cloud->master->mst_parent = cloud->master;
945 cloud->mst_root = cloud->master;
946 q = new_pdeq1(cloud->master);
947 while(!pdeq_empty(q)) {
948 co2_cloud_irn_t *ci = pdeq_getl(q);
949 int ofs = ci->index * cloud->n_memb;
950 int end = ofs + cloud->n_memb;
953 ci->mst_n_childs = 0;
954 for(i = ofs; i < end; ++i) {
955 if(mst_edges[i] != 0) {
957 co2_cloud_irn_t *child = cloud->seq[i - ofs];
959 /* put the child to the worklist */
962 /* make ci the parent of the child and add the child to the children array of the parent */
963 child->mst_parent = ci;
964 child->mst_costs = mst_edges[i];
966 obstack_ptr_grow(&cloud->obst, child);
968 mst_edges[other * cloud->n_memb + ci->index] = 0;
973 obstack_ptr_grow(&cloud->obst, NULL);
974 ci->mst_childs = obstack_finish(&cloud->obst);
980 DBG((env->dbg, LEVEL_3, "mst:\n"));
981 for(i = 0; i < cloud->n_memb; ++i) {
982 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
983 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
986 for(i = 0; i < cloud->n_memb; ++i) {
987 co2_cloud_irn_t *ci = cloud->seq[i];
988 int n_childs = ci->mst_n_childs;
991 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
992 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
993 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
994 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
995 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
996 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
997 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
998 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
1000 for(j = 0; j < env->n_regs; j++)
1001 ci->col_costs[j] = INT_MAX;
1005 determine_color_badness(cloud->mst_root, 0);
1006 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1007 unfix_subtree(cloud->mst_root);
1008 apply_coloring(cloud->mst_root, best_col, 0);
1010 /* The coloring should represent the one with the best costs. */
1011 //materialize_coloring(&changed);
1012 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1013 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1015 /* Fix all nodes in the cloud. */
1016 for(i = 0; i < cloud->n_memb; ++i)
1017 cloud->seq[i]->inh.fixed = 1;
1019 /* Free all space used while optimizing this cloud. */
1020 obstack_free(&cloud->obst, NULL);
1023 static int cloud_costs(co2_cloud_t *cloud)
1028 for(i = 0; i < cloud->n_memb; ++i) {
1029 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1030 col_t col = get_col(cloud->env, ci->irn);
1031 co_gs_foreach_neighb(ci->aff, n) {
1032 col_t n_col = get_col(cloud->env, n->irn);
1033 costs += col != n_col ? n->costs : 0;
1040 static void process(co2_t *env)
1044 co2_cloud_t **clouds;
1049 int final_costs = 0;
1052 co_gs_foreach_aff_node(env->co, a) {
1053 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1062 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1063 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1065 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1067 for(i = 0; i < n_clouds; ++i) {
1068 init_costs += cloud_costs(clouds[i]);
1070 /* Process the cloud. */
1071 process_cloud(clouds[i]);
1073 all_costs += clouds[i]->costs;
1074 final_costs += cloud_costs(clouds[i]);
1076 /* Dump the IFG if the user demanded it. */
1077 if (dump_flags & DUMP_CLOUD) {
1081 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1082 f = fopen(buf, "wt");
1084 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1090 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1095 static void writeback_colors(co2_t *env)
1099 for(irn = env->touched; irn; irn = irn->touched_next) {
1100 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1101 arch_set_irn_register((ir_node*)irn->irn, reg);
1107 ___ _____ ____ ____ ___ _____ ____ _
1108 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1109 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1110 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1111 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1115 static const char *get_dot_color_name(size_t col)
1117 static const char *const names[] = {
1151 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1154 static const char *get_dot_shape_name(co2_irn_t *ci)
1156 const arch_register_req_t *req;
1158 req = arch_get_register_req(ci->irn, BE_OUT_POS(0));
1159 if(arch_register_req_is(req, limited))
1171 static void ifg_dump_graph_attr(FILE *f, void *self)
1174 fprintf(f, "overlay=false");
1177 static int ifg_is_dump_node(void *self, ir_node *irn)
1180 return !arch_irn_is(irn, ignore);
1183 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1186 co2_irn_t *ci = get_co2_irn(env, irn);
1192 co2_cloud_irn_t *cci = (void *) ci;
1193 if (cci->cloud && cci->cloud->mst_root == cci)
1196 if(cci->cloud && cci->cloud->mst_root)
1197 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1200 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1201 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1204 static void ifg_dump_at_end(FILE *file, void *self)
1209 co_gs_foreach_aff_node(env->co, a) {
1210 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1211 int idx = get_irn_idx(a->irn);
1214 if(ai->mst_parent != ai)
1215 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1217 co_gs_foreach_neighb(a, n) {
1218 int nidx = get_irn_idx(n->irn);
1219 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1222 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1223 const char *arr = "arrowhead=dot arrowtail=dot";
1225 if(ci->mst_parent == ai)
1226 arr = "arrowtail=normal";
1227 else if(ai->mst_parent == ci)
1228 arr = "arrowhead=normal";
1230 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1237 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1239 ifg_dump_graph_attr,
1247 int co_solve_heuristic_new(copy_opt_t *co)
1253 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1257 env.n_regs = co->cls->n_regs;
1258 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1259 be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs);
1260 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1261 INIT_LIST_HEAD(&env.cloud_head);
1263 if(dump_flags & DUMP_BEFORE) {
1264 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1265 f = fopen(buf, "wt");
1267 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1274 if(dump_flags & DUMP_AFTER) {
1275 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1276 f = fopen(buf, "wt");
1278 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1283 writeback_colors(&env);
1284 phase_free(&env.ph);