2 * Copyright (C) 1995-2007 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
31 #include <libcore/lc_opts.h>
32 #include <libcore/lc_opts_enum.h>
40 #include "raw_bitset.h"
43 #include "bitfiddle.h"
45 #include "irphase_t.h"
46 #include "irgraph_t.h"
54 #include "becopyopt.h"
55 #include "becopyopt_t.h"
56 #include "bechordal_t.h"
62 #define DUMP_ALL 2 * DUMP_CLOUD - 1
64 static unsigned dump_flags = 0;
65 static int subtree_iter = 4;
66 static int max_depth = 20;
67 static double constr_factor = 0.9;
69 /* Options using libcore */
70 static const lc_opt_enum_mask_items_t dump_items[] = {
71 { "before", DUMP_BEFORE },
72 { "after", DUMP_AFTER },
73 { "cloud", DUMP_CLOUD },
78 static lc_opt_enum_mask_var_t dump_var = {
79 &dump_flags, dump_items
82 static const lc_opt_table_entry_t options[] = {
83 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
84 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
85 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
86 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
90 void be_init_copyheur2(void)
92 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
93 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
94 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
95 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
97 lc_opt_add_table(co2_grp, options);
100 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
104 / ___|| |_ __ _ _ __| |_
105 \___ \| __/ _` | '__| __|
106 ___) | || (_| | | | |_
107 |____/ \__\__,_|_| \__|
111 #define INFEASIBLE(cost) ((cost) == INT_MAX)
113 static be_ifg_dump_dot_cb_t ifg_dot_cb;
115 typedef unsigned col_t;
117 typedef struct _co2_irn_t co2_irn_t;
118 typedef struct _co2_cloud_t co2_cloud_t;
119 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
129 bitset_t *ignore_regs;
133 struct list_head cloud_head;
134 DEBUG_ONLY(firm_dbg_module_t *dbg;)
139 affinity_node_t *aff;
140 co2_irn_t *touched_next;
143 int last_color_change;
146 unsigned tmp_fixed : 1;
147 unsigned is_constrained : 1;
148 struct list_head changed_list;
151 struct _co2_cloud_irn_t {
152 struct _co2_irn_t inh;
156 co2_cloud_irn_t *mst_parent;
159 co2_cloud_irn_t **mst_childs;
164 col_cost_pair_t *tmp_coloring;
165 struct list_head cloud_list;
166 struct list_head mst_list;
169 struct _co2_cloud_t {
181 co2_cloud_irn_t *master;
182 co2_cloud_irn_t *mst_root;
183 co2_cloud_irn_t **seq;
184 struct list_head members_head;
185 struct list_head list;
189 co2_cloud_irn_t *src, *tgt;
193 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
195 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
196 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
198 static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
200 co2_t *env = (co2_t *) ph;
201 affinity_node_t *a = get_affinity_info(env->co, irn);
202 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
203 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
206 INIT_LIST_HEAD(&ci->changed_list);
207 ci->touched_next = env->touched;
208 ci->orig_col = get_irn_col(env->co, irn);
214 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
215 INIT_LIST_HEAD(&cci->cloud_list);
216 cci->mst_parent = cci;
222 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
224 static int cmp_clouds_gt(const void *a, const void *b)
226 const co2_cloud_t * const *p = a;
227 const co2_cloud_t * const *q = b;
228 double c = CLOUD_WEIGHT(*p);
229 double d = CLOUD_WEIGHT(*q);
230 return QSORT_CMP(d, c);
234 * An order on color/costs pairs.
235 * If the costs are equal, we use the color as a kind of normalization.
237 static int col_cost_pair_lt(const void *a, const void *b)
239 const col_cost_pair_t *p = a;
240 const col_cost_pair_t *q = b;
243 return QSORT_CMP(c, d);
246 int cmp_edges(const void *a, const void *b)
250 return QSORT_CMP(q->costs, p->costs);
253 static col_t get_col(co2_t *env, ir_node *irn)
255 co2_irn_t *ci = get_co2_irn(env, irn);
256 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
259 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
261 co2_irn_t *ci = get_co2_irn(env, irn);
262 return ci->fixed || ci->tmp_fixed;
265 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
267 if(ci->adm_cache == NULL) {
268 const arch_register_req_t *req;
269 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
270 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
272 if(arch_register_req_is(req, limited)) {
276 for(i = 0; i < n; ++i) {
277 if(rbitset_is_set(req->limited, i))
278 bitset_set(ci->adm_cache, i);
280 ci->is_constrained = 1;
282 bitset_copy(ci->adm_cache, env->ignore_regs);
283 bitset_flip_all(ci->adm_cache);
287 return ci->adm_cache;
290 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
292 bitset_copy(bs, get_adm(env, ci));
296 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
298 bitset_t *bs = get_adm(env, ci);
299 return bitset_is_set(bs, col);
302 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
306 return ci->is_constrained;
309 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
311 const arch_register_req_t *req;
313 req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
315 if (arch_register_req_is(req, limited)) {
316 unsigned n_regs = env->co->cls->n_regs;
317 unsigned n_constr = 0;
320 n_constr = rbitset_popcnt(req->limited, n_regs);
321 for (i = 0; i < n_regs; ++i) {
322 if (rbitset_is_set(req->limited, i)) {
323 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
330 * Determine costs which shall indicate how cheap/expensive it is to try
331 * to assign a node some color.
332 * The costs are computed for all colors. INT_MAX means that it is impossible
333 * to give the node that specific color.
335 * @param env The co2 this pointer.
336 * @param irn The node.
337 * @param col_costs An array of colors x costs where the costs are written to.
339 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
341 ir_node *irn = ci->irn;
342 be_ifg_t *ifg = env->co->cenv->ifg;
343 int n_regs = env->co->cls->n_regs;
344 bitset_t *forb = bitset_alloca(n_regs);
345 affinity_node_t *a = ci->aff;
352 /* Put all forbidden colors into the aux bitset. */
353 admissible_colors(env, ci, forb);
354 bitset_flip_all(forb);
356 for(i = 0; i < n_regs; ++i) {
357 col_costs[i].col = i;
358 col_costs[i].costs = 0;
364 co_gs_foreach_neighb(a, n) {
365 if(color_is_fix(env, n->irn)) {
366 col_t col = get_col(env, n->irn);
367 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
370 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
374 it = be_ifg_neighbours_iter_alloca(ifg);
375 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
376 col_t col = get_col(env, pos);
377 if(color_is_fix(env, pos)) {
378 col_costs[col].costs = INT_MAX;
381 incur_constraint_costs(env, pos, col_costs, INT_MAX);
382 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
385 be_ifg_neighbours_break(ifg, it);
387 /* Set the costs to infinity for each color which is not allowed at this node. */
388 bitset_foreach(forb, elm) {
389 col_costs[elm].costs = INT_MAX;
394 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
396 int n_regs = env->co->cls->n_regs;
399 for(i = 0; i < n_regs; ++i) {
401 seq[i].costs = INT_MAX;
405 assert(is_color_admissible(env, ci, col));
411 static void reject_coloring(struct list_head *h)
415 list_for_each_entry(co2_irn_t, pos, h, changed_list)
419 static void materialize_coloring(struct list_head *h)
423 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
424 pos->orig_col = pos->tmp_col;
429 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
431 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
433 int n_regs = env->co->cls->n_regs;
434 be_ifg_t *ifg = env->co->cenv->ifg;
435 co2_irn_t *ci = get_co2_irn(env, irn);
440 if(depth >= max_depth)
443 for(i = 0; i < n_regs; ++i) {
444 col_t tgt_col = col_list[i].col;
445 unsigned costs = col_list[i].costs;
448 struct list_head changed;
452 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
454 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
455 if(INFEASIBLE(costs)) {
456 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
461 /* Set the new color of the node and mark the node as temporarily fixed. */
462 ci->tmp_col = tgt_col;
466 If that color has costs > 0, there's at least one neighbor having that color,
467 so we will try to change the neighbors' colors, too.
469 INIT_LIST_HEAD(&changed);
470 list_add(&ci->changed_list, &changed);
472 it = be_ifg_neighbours_iter_alloca(ifg);
473 be_ifg_foreach_neighbour(ifg, it, irn, n) {
475 /* try to re-color the neighbor if it has the target color. */
476 if(get_col(env, n) == tgt_col) {
477 struct list_head tmp;
480 Try to change the color of the neighbor and record all nodes which
481 get changed in the tmp list. Add this list to the "changed" list for
482 that color. If we did not succeed to change the color of the neighbor,
483 we bail out and try the next color.
485 INIT_LIST_HEAD(&tmp);
486 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
487 list_splice(&tmp, &changed);
492 be_ifg_neighbours_break(ifg, it);
495 We managed to assign the target color to all neighbors, so from the perspective
496 of the current node, every thing was ok and we can return safely.
499 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
500 list_splice(&changed, parent_changed);
506 If not, that color did not succeed and we unfix all nodes we touched
507 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
510 reject_coloring(&changed);
516 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
518 co2_irn_t *ci = get_co2_irn(env, irn);
520 col_t col = get_col(env, irn);
522 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
524 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
531 list_add(&ci->changed_list, parent_changed);
535 /* The node has the color it should not have _and_ has not been visited yet. */
536 if(!color_is_fix(env, irn)) {
537 int n_regs = env->co->cls->n_regs;
538 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
540 /* Get the costs for giving the node a specific color. */
541 determine_color_costs(env, ci, csts);
543 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
544 csts[not_col].costs = INT_MAX;
546 /* sort the colors according costs, cheapest first. */
547 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
549 /* Try recoloring the node using the color list. */
550 res = recolor(env, irn, csts, parent_changed, depth);
553 /* If we came here, everything went ok. */
557 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
559 co2_irn_t *ci = get_co2_irn(env, irn);
560 col_t col = get_col(env, irn);
563 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
565 /* the node has the wanted color. That's fine, mark it as visited and return. */
570 list_add(&ci->changed_list, parent_changed);
577 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
578 int n_regs = env->co->cls->n_regs;
579 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
581 /* Get the costs for giving the node a specific color. */
582 single_color_cost(env, ci, tgt_col, seq);
584 /* Try recoloring the node using the color list. */
585 res = recolor(env, irn, seq, parent_changed, depth);
590 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
595 * Examine the costs of the current coloring concerning a MST subtree.
596 * @param ci The subtree root.
597 * @param col The color of @p ci.
598 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
600 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
602 int *front = FRONT_BASE(ci, col);
606 for(i = 0; i < ci->mst_n_childs; ++i) {
607 co2_cloud_irn_t *chld = ci->mst_childs[i];
608 col_t chld_col = front[i];
610 cost += examine_subtree_coloring(chld, chld_col);
611 cost += col != chld_col ? chld->mst_costs : 0;
618 * Determine color badnesses of a node.
619 * Badness means that it is unlikely that the node in question can
620 * obtain a color. The higher the badness, the more unlikely it is that
621 * the node can be assigned that color.
622 * @param ci The node.
623 * @param badness An integer array as long as there are registers.
624 * @note The array <code>badness</code> is not cleared.
626 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
628 co2_t *env = ci->cloud->env;
629 co2_irn_t *ir = &ci->inh;
630 int n_regs = env->n_regs;
631 be_ifg_t *ifg = env->co->cenv->ifg;
632 bitset_t *bs = bitset_alloca(n_regs);
638 admissible_colors(env, &ci->inh, bs);
640 bitset_foreach(bs, elm)
641 badness[elm] = ci->costs;
643 /* Use constrained/fixed interfering neighbors to influence the color badness */
644 it = be_ifg_neighbours_iter_alloca(ifg);
645 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
646 co2_irn_t *ni = get_co2_irn(env, irn);
648 admissible_colors(env, ni, bs);
649 if(bitset_popcnt(bs) == 1) {
650 bitset_pos_t c = bitset_next_set(bs, 0);
651 badness[c] += ci->costs;
655 col_t c = get_col(env, ni->irn);
656 badness[c] += ci->costs;
659 be_ifg_neighbours_break(ifg, it);
663 * Determine the badness of a MST subtree.
664 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
665 * @see node_color_badness() for a definition of badness.
666 * @param ci The root of the subtree.
667 * @param depth Depth for debugging purposes.
669 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
671 co2_t *env = ci->cloud->env;
674 node_color_badness(ci, ci->color_badness);
676 /* Collect the color badness for the whole subtree */
677 for(i = 0; i < ci->mst_n_childs; ++i) {
678 co2_cloud_irn_t *child = ci->mst_childs[i];
679 determine_color_badness(child, depth + 1);
681 for(j = 0; j < env->n_regs; ++j)
682 ci->color_badness[j] += child->color_badness[j];
685 for(j = 0; j < env->n_regs; ++j)
686 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
690 * Unfix all nodes in a MST subtree.
692 static void unfix_subtree(co2_cloud_irn_t *ci)
697 for(i = 0; i < ci->mst_n_childs; ++i)
698 unfix_subtree(ci->mst_childs[i]);
701 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
703 co2_t *env = ci->cloud->env;
704 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
705 int is_root = ci->mst_parent == ci;
706 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
707 int min_badness = INT_MAX;
708 int best_col_costs = INT_MAX;
710 int n_regs = env->n_regs;
711 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
713 struct list_head changed;
716 for(i = 0; i < n_regs; ++i) {
717 int badness = ci->color_badness[i];
720 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
722 min_badness = MIN(min_badness, badness);
725 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
726 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
727 seq[parent_col].costs = min_badness - 1;
729 /* Sort the colors. The will be processed in that ordering. */
730 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
732 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
733 INIT_LIST_HEAD(&changed);
734 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
735 col_t col = seq[i].col;
736 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
738 int subtree_costs, sum_costs;
740 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
743 INIT_LIST_HEAD(&changed);
744 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
746 materialize_coloring(&changed);
753 for(j = 0; j < ci->mst_n_childs; ++j) {
754 co2_cloud_irn_t *child = ci->mst_childs[j];
755 ok = coalesce_top_down(child, j, depth + 1) >= 0;
757 child->inh.fixed = 1;
762 /* If the subtree could not be colored, we have to try another color. */
766 subtree_costs = examine_subtree_coloring(ci, col);
767 sum_costs = subtree_costs + add_cost;
768 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
770 if(sum_costs < best_col_costs) {
772 best_col_costs = sum_costs;
773 ci->col_costs[col] = subtree_costs;
781 int *front = FRONT_BASE(ci->mst_parent, parent_col);
782 front[child_nr] = best_col;
788 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
790 be_ifg_t *ifg = env->co->cenv->ifg;
791 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
798 /* mark the node as visited and add it to the cloud. */
800 list_add(&ci->cloud_list, &cloud->members_head);
802 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
804 /* determine the nodes costs */
805 co_gs_foreach_neighb(a, n) {
807 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
808 if(be_ifg_connected(ifg, a->irn, n->irn))
809 cloud->inevit += n->costs;
812 /* add the node's cost to the total costs of the cloud. */
814 cloud->costs += costs;
815 cloud->n_constr += is_constrained(env, &ci->inh);
816 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
817 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
820 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
821 if(costs >= curr_costs) {
826 /* add all the neighbors of the node to the cloud. */
827 co_gs_foreach_neighb(a, n) {
828 affinity_node_t *an = get_affinity_info(env->co, n->irn);
830 populate_cloud(env, cloud, an, curr_costs);
834 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
836 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
840 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
841 memset(cloud, 0, sizeof(cloud[0]));
842 INIT_LIST_HEAD(&cloud->members_head);
843 INIT_LIST_HEAD(&cloud->list);
844 list_add(&cloud->list, &env->cloud_head);
845 cloud->best_costs = INT_MAX;
848 populate_cloud(env, cloud, a, 0);
849 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
851 /* Also allocate space for the node sequence and compute that sequence. */
852 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
855 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
857 cloud->seq[i++] = ci;
859 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
864 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
866 ir_node *irn = ci->inh.irn;
867 int *front = FRONT_BASE(ci, col);
869 struct list_head changed;
871 INIT_LIST_HEAD(&changed);
873 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
874 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
875 // assert(ok && "Color changing may not fail while committing the coloring");
876 materialize_coloring(&changed);
878 for(i = 0; i < ci->mst_n_childs; ++i) {
879 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
883 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
885 while(ci != ci->mst_parent)
891 static void process_cloud(co2_cloud_t *cloud)
893 co2_t *env = cloud->env;
894 int n_regs = env->n_regs;
896 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
903 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
905 /* Collect all edges in the cloud on an obstack and sort the increasingly */
906 obstack_init(&cloud->obst);
907 for(i = 0; i < cloud->n_memb; ++i) {
908 co2_cloud_irn_t *ci = cloud->seq[i];
911 co_gs_foreach_neighb(ci->inh.aff, n) {
912 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
913 if(ci->index < ni->index) {
918 obstack_grow(&cloud->obst, &e, sizeof(e));
923 edges = obstack_finish(&cloud->obst);
924 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
926 /* Compute the maximum spanning tree using Kruskal/Union-Find */
927 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
928 for(i = 0; i < n_edges; ++i) {
929 edge_t *e = &edges[i];
930 co2_cloud_irn_t *rs = find_mst_root(e->src);
931 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
933 /* if the union/find roots are different */
935 int si = e->src->index;
936 int ti = e->tgt->index;
940 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
942 /* this edge is in the MST, so set it in the bitset. */
943 mst_edges[si * cloud->n_memb + ti] = e->costs;
944 mst_edges[ti * cloud->n_memb + si] = e->costs;
947 obstack_free(&cloud->obst, edges);
949 cloud->master->mst_parent = cloud->master;
950 cloud->mst_root = cloud->master;
951 q = new_pdeq1(cloud->master);
952 while(!pdeq_empty(q)) {
953 co2_cloud_irn_t *ci = pdeq_getl(q);
954 int ofs = ci->index * cloud->n_memb;
955 int end = ofs + cloud->n_memb;
958 ci->mst_n_childs = 0;
959 for(i = ofs; i < end; ++i) {
960 if(mst_edges[i] != 0) {
962 co2_cloud_irn_t *child = cloud->seq[i - ofs];
964 /* put the child to the worklist */
967 /* make ci the parent of the child and add the child to the children array of the parent */
968 child->mst_parent = ci;
969 child->mst_costs = mst_edges[i];
971 obstack_ptr_grow(&cloud->obst, child);
973 mst_edges[other * cloud->n_memb + ci->index] = 0;
978 obstack_ptr_grow(&cloud->obst, NULL);
979 ci->mst_childs = obstack_finish(&cloud->obst);
985 DBG((env->dbg, LEVEL_3, "mst:\n"));
986 for(i = 0; i < cloud->n_memb; ++i) {
987 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
988 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
991 for(i = 0; i < cloud->n_memb; ++i) {
992 co2_cloud_irn_t *ci = cloud->seq[i];
993 int n_childs = ci->mst_n_childs;
996 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
997 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
998 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
999 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
1000 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
1001 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
1002 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
1003 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
1005 for(j = 0; j < env->n_regs; j++)
1006 ci->col_costs[j] = INT_MAX;
1010 determine_color_badness(cloud->mst_root, 0);
1011 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1012 unfix_subtree(cloud->mst_root);
1013 apply_coloring(cloud->mst_root, best_col, 0);
1015 /* The coloring should represent the one with the best costs. */
1016 //materialize_coloring(&changed);
1017 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1018 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1020 /* Fix all nodes in the cloud. */
1021 for(i = 0; i < cloud->n_memb; ++i)
1022 cloud->seq[i]->inh.fixed = 1;
1024 /* Free all space used while optimizing this cloud. */
1025 obstack_free(&cloud->obst, NULL);
1028 static int cloud_costs(co2_cloud_t *cloud)
1033 for(i = 0; i < cloud->n_memb; ++i) {
1034 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1035 col_t col = get_col(cloud->env, ci->irn);
1036 co_gs_foreach_neighb(ci->aff, n) {
1037 col_t n_col = get_col(cloud->env, n->irn);
1038 costs += col != n_col ? n->costs : 0;
1045 static void process(co2_t *env)
1049 co2_cloud_t **clouds;
1054 int final_costs = 0;
1057 co_gs_foreach_aff_node(env->co, a) {
1058 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1067 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1068 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1070 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1072 for(i = 0; i < n_clouds; ++i) {
1073 init_costs += cloud_costs(clouds[i]);
1075 /* Process the cloud. */
1076 process_cloud(clouds[i]);
1078 all_costs += clouds[i]->costs;
1079 final_costs += cloud_costs(clouds[i]);
1081 /* Dump the IFG if the user demanded it. */
1082 if (dump_flags & DUMP_CLOUD) {
1086 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1087 f = fopen(buf, "wt");
1089 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1095 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1100 static void writeback_colors(co2_t *env)
1102 const arch_env_t *aenv = env->co->aenv;
1105 for(irn = env->touched; irn; irn = irn->touched_next) {
1106 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1107 arch_set_irn_register(aenv, irn->irn, reg);
1113 ___ _____ ____ ____ ___ _____ ____ _
1114 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1115 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1116 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1117 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1121 static const char *get_dot_color_name(size_t col)
1123 static const char *names[] = {
1157 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1160 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1162 const arch_register_req_t *req;
1164 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
1165 if(arch_register_req_is(req, limited))
1177 static void ifg_dump_graph_attr(FILE *f, void *self)
1180 fprintf(f, "overlay=false");
1183 static int ifg_is_dump_node(void *self, ir_node *irn)
1186 return !arch_irn_is(env->co->aenv, irn, ignore);
1189 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1192 co2_irn_t *ci = get_co2_irn(env, irn);
1198 co2_cloud_irn_t *cci = (void *) ci;
1199 if (cci->cloud && cci->cloud->mst_root == cci)
1202 if(cci->cloud && cci->cloud->mst_root)
1203 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1206 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1207 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1210 static void ifg_dump_at_end(FILE *file, void *self)
1215 co_gs_foreach_aff_node(env->co, a) {
1216 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1217 int idx = get_irn_idx(a->irn);
1220 if(ai->mst_parent != ai)
1221 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1223 co_gs_foreach_neighb(a, n) {
1224 int nidx = get_irn_idx(n->irn);
1225 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1228 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1229 const char *arr = "arrowhead=dot arrowtail=dot";
1231 if(ci->mst_parent == ai)
1232 arr = "arrowtail=normal";
1233 else if(ai->mst_parent == ci)
1234 arr = "arrowhead=normal";
1236 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1243 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1245 ifg_dump_graph_attr,
1253 int co_solve_heuristic_new(copy_opt_t *co)
1259 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1263 env.n_regs = co->cls->n_regs;
1264 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1265 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1266 bitset_flip_all(env.ignore_regs);
1267 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1268 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1269 INIT_LIST_HEAD(&env.cloud_head);
1271 if(dump_flags & DUMP_BEFORE) {
1272 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1273 f = fopen(buf, "wt");
1275 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1282 if(dump_flags & DUMP_AFTER) {
1283 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1284 f = fopen(buf, "wt");
1286 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1291 writeback_colors(&env);
1292 phase_free(&env.ph);