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),
89 / ___|| |_ __ _ _ __| |_
90 \___ \| __/ _` | '__| __|
91 ___) | || (_| | | | |_
92 |____/ \__\__,_|_| \__|
96 #define INFEASIBLE(cost) ((cost) == INT_MAX)
98 static be_ifg_dump_dot_cb_t ifg_dot_cb;
100 typedef unsigned col_t;
102 typedef struct _co2_irn_t co2_irn_t;
103 typedef struct _co2_cloud_t co2_cloud_t;
104 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
114 bitset_t *ignore_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;
154 struct _co2_cloud_t {
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 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
181 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
183 static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
185 co2_t *env = (co2_t *) ph;
186 affinity_node_t *a = get_affinity_info(env->co, irn);
187 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
188 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
191 INIT_LIST_HEAD(&ci->changed_list);
192 ci->touched_next = env->touched;
193 ci->orig_col = get_irn_col(irn);
199 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
200 INIT_LIST_HEAD(&cci->cloud_list);
201 cci->mst_parent = cci;
207 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
209 static int cmp_clouds_gt(const void *a, const void *b)
211 const co2_cloud_t * const *p = a;
212 const co2_cloud_t * const *q = b;
213 double c = CLOUD_WEIGHT(*p);
214 double d = CLOUD_WEIGHT(*q);
215 return QSORT_CMP(d, c);
219 * An order on color/costs pairs.
220 * If the costs are equal, we use the color as a kind of normalization.
222 static int col_cost_pair_lt(const void *a, const void *b)
224 const col_cost_pair_t *p = a;
225 const col_cost_pair_t *q = b;
228 return QSORT_CMP(c, d);
231 static int cmp_edges(const void *a, const void *b)
235 return QSORT_CMP(q->costs, p->costs);
238 static col_t get_col(co2_t *env, const ir_node *irn)
240 co2_irn_t *ci = get_co2_irn(env, irn);
241 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
244 static inline int color_is_fix(co2_t *env, const ir_node *irn)
246 co2_irn_t *ci = get_co2_irn(env, irn);
247 return ci->fixed || ci->tmp_fixed;
250 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
252 if (ci->adm_cache == NULL) {
253 const arch_register_req_t *req;
254 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
255 req = arch_get_register_req_out(ci->irn);
257 if (arch_register_req_is(req, limited)) {
261 for (i = 0; i < n; ++i) {
262 if (rbitset_is_set(req->limited, i))
263 bitset_set(ci->adm_cache, i);
265 ci->is_constrained = 1;
267 bitset_copy(ci->adm_cache, env->ignore_regs);
268 bitset_flip_all(ci->adm_cache);
272 return ci->adm_cache;
275 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
277 bitset_copy(bs, get_adm(env, ci));
281 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
283 bitset_t *bs = get_adm(env, ci);
284 return bitset_is_set(bs, col);
287 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
291 return ci->is_constrained;
294 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
296 const arch_register_req_t *req = arch_get_register_req_out(irn);
298 if (arch_register_req_is(req, limited)) {
299 unsigned n_regs = env->co->cls->n_regs;
300 unsigned n_constr = 0;
303 n_constr = rbitset_popcount(req->limited, n_regs);
304 for (i = 0; i < n_regs; ++i) {
305 if (rbitset_is_set(req->limited, i)) {
306 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
313 * Determine costs which shall indicate how cheap/expensive it is to try
314 * to assign a node some color.
315 * The costs are computed for all colors. INT_MAX means that it is impossible
316 * to give the node that specific color.
318 * @param env The co2 this pointer.
319 * @param irn The node.
320 * @param col_costs An array of colors x costs where the costs are written to.
322 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
324 const ir_node *irn = ci->irn;
325 be_ifg_t *ifg = env->co->cenv->ifg;
326 int n_regs = env->co->cls->n_regs;
327 bitset_t *forb = bitset_alloca(n_regs);
328 affinity_node_t *a = ci->aff;
335 /* Put all forbidden colors into the aux bitset. */
336 admissible_colors(env, ci, forb);
337 bitset_flip_all(forb);
339 for (i = 0; i < n_regs; ++i) {
340 col_costs[i].col = i;
341 col_costs[i].costs = 0;
347 co_gs_foreach_neighb(a, n) {
348 if (color_is_fix(env, n->irn)) {
349 col_t col = get_col(env, n->irn);
350 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
353 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
357 it = be_ifg_neighbours_iter_alloca(ifg);
358 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
359 col_t col = get_col(env, pos);
360 if (color_is_fix(env, pos)) {
361 col_costs[col].costs = INT_MAX;
364 incur_constraint_costs(env, pos, col_costs, INT_MAX);
365 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
368 be_ifg_neighbours_break(ifg, it);
370 /* Set the costs to infinity for each color which is not allowed at this node. */
371 bitset_foreach(forb, elm) {
372 col_costs[elm].costs = INT_MAX;
377 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
379 int n_regs = env->co->cls->n_regs;
382 for (i = 0; i < n_regs; ++i) {
384 seq[i].costs = INT_MAX;
388 assert(is_color_admissible(env, ci, col));
394 static void reject_coloring(struct list_head *h)
398 list_for_each_entry(co2_irn_t, pos, h, changed_list)
402 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;
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 it = be_ifg_neighbours_iter_alloca(ifg);
456 be_ifg_foreach_neighbour(ifg, it, irn, n) {
458 /* try to re-color the neighbor if it has the target color. */
459 if (get_col(env, n) == tgt_col) {
460 struct list_head tmp;
463 Try to change the color of the neighbor and record all nodes which
464 get changed in the tmp list. Add this list to the "changed" list for
465 that color. If we did not succeed to change the color of the neighbor,
466 we bail out and try the next color.
468 INIT_LIST_HEAD(&tmp);
469 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
470 list_splice(&tmp, &changed);
475 be_ifg_neighbours_break(ifg, it);
478 We managed to assign the target color to all neighbors, so from the perspective
479 of the current node, every thing was ok and we can return safely.
482 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
483 list_splice(&changed, parent_changed);
489 If not, that color did not succeed and we unfix all nodes we touched
490 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
493 reject_coloring(&changed);
499 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
501 co2_irn_t *ci = get_co2_irn(env, irn);
503 col_t col = get_col(env, irn);
505 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
507 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
508 if (col != not_col) {
509 if (!ci->tmp_fixed) {
514 list_add(&ci->changed_list, parent_changed);
518 /* The node has the color it should not have _and_ has not been visited yet. */
519 if (!color_is_fix(env, irn)) {
520 int n_regs = env->co->cls->n_regs;
521 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
523 /* Get the costs for giving the node a specific color. */
524 determine_color_costs(env, ci, csts);
526 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
527 csts[not_col].costs = INT_MAX;
529 /* sort the colors according costs, cheapest first. */
530 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
532 /* Try recoloring the node using the color list. */
533 res = recolor(env, irn, csts, parent_changed, depth);
536 /* If we came here, everything went ok. */
540 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
542 co2_irn_t *ci = get_co2_irn(env, irn);
543 col_t col = get_col(env, irn);
546 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
548 /* the node has the wanted color. That's fine, mark it as visited and return. */
549 if (col == tgt_col) {
550 if (!ci->tmp_fixed) {
553 list_add(&ci->changed_list, parent_changed);
560 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
561 int n_regs = env->co->cls->n_regs;
562 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
564 /* Get the costs for giving the node a specific color. */
565 single_color_cost(env, ci, tgt_col, seq);
567 /* Try recoloring the node using the color list. */
568 res = recolor(env, irn, seq, parent_changed, depth);
573 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
578 * Examine the costs of the current coloring concerning a MST subtree.
579 * @param ci The subtree root.
580 * @param col The color of @p ci.
581 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
583 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
585 int *front = FRONT_BASE(ci, col);
589 for (i = 0; i < ci->mst_n_childs; ++i) {
590 co2_cloud_irn_t *chld = ci->mst_childs[i];
591 col_t chld_col = front[i];
593 cost += examine_subtree_coloring(chld, chld_col);
594 cost += col != chld_col ? chld->mst_costs : 0;
601 * Determine color badnesses of a node.
602 * Badness means that it is unlikely that the node in question can
603 * obtain a color. The higher the badness, the more unlikely it is that
604 * the node can be assigned that color.
605 * @param ci The node.
606 * @param badness An integer array as long as there are registers.
607 * @note The array <code>badness</code> is not cleared.
609 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
611 co2_t *env = ci->cloud->env;
612 co2_irn_t *ir = &ci->inh;
613 int n_regs = env->n_regs;
614 be_ifg_t *ifg = env->co->cenv->ifg;
615 bitset_t *bs = bitset_alloca(n_regs);
621 admissible_colors(env, &ci->inh, bs);
623 bitset_foreach(bs, elm)
624 badness[elm] = ci->costs;
626 /* Use constrained/fixed interfering neighbors to influence the color badness */
627 it = be_ifg_neighbours_iter_alloca(ifg);
628 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
629 co2_irn_t *ni = get_co2_irn(env, irn);
631 admissible_colors(env, ni, bs);
632 if (bitset_popcount(bs) == 1) {
633 unsigned c = bitset_next_set(bs, 0);
634 badness[c] += ci->costs;
637 else if (ni->fixed) {
638 col_t c = get_col(env, ni->irn);
639 badness[c] += ci->costs;
642 be_ifg_neighbours_break(ifg, it);
646 * Determine the badness of a MST subtree.
647 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
648 * @see node_color_badness() for a definition of badness.
649 * @param ci The root of the subtree.
650 * @param depth Depth for debugging purposes.
652 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
654 co2_t *env = ci->cloud->env;
657 node_color_badness(ci, ci->color_badness);
659 /* Collect the color badness for the whole subtree */
660 for (i = 0; i < ci->mst_n_childs; ++i) {
661 co2_cloud_irn_t *child = ci->mst_childs[i];
662 determine_color_badness(child, depth + 1);
664 for (j = 0; j < env->n_regs; ++j)
665 ci->color_badness[j] += child->color_badness[j];
668 for (j = 0; j < env->n_regs; ++j)
669 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
673 * Unfix all nodes in a MST subtree.
675 static void unfix_subtree(co2_cloud_irn_t *ci)
680 for (i = 0; i < ci->mst_n_childs; ++i)
681 unfix_subtree(ci->mst_childs[i]);
684 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
686 co2_t *env = ci->cloud->env;
687 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
688 int is_root = ci->mst_parent == ci;
689 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
690 int min_badness = INT_MAX;
691 int best_col_costs = INT_MAX;
693 int n_regs = env->n_regs;
694 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
696 struct list_head changed;
699 for (i = 0; i < n_regs; ++i) {
700 int badness = ci->color_badness[i];
703 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
705 min_badness = MIN(min_badness, badness);
708 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
709 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
710 seq[parent_col].costs = min_badness - 1;
712 /* Sort the colors. The will be processed in that ordering. */
713 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
715 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
716 INIT_LIST_HEAD(&changed);
717 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
718 col_t col = seq[i].col;
719 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
721 int subtree_costs, sum_costs;
723 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
726 INIT_LIST_HEAD(&changed);
727 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
729 materialize_coloring(&changed);
736 for (j = 0; j < ci->mst_n_childs; ++j) {
737 co2_cloud_irn_t *child = ci->mst_childs[j];
738 ok = coalesce_top_down(child, j, depth + 1) >= 0;
740 child->inh.fixed = 1;
745 /* If the subtree could not be colored, we have to try another color. */
749 subtree_costs = examine_subtree_coloring(ci, col);
750 sum_costs = subtree_costs + add_cost;
751 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
753 if (sum_costs < best_col_costs) {
755 best_col_costs = sum_costs;
756 ci->col_costs[col] = subtree_costs;
764 int *front = FRONT_BASE(ci->mst_parent, parent_col);
765 front[child_nr] = best_col;
771 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
773 be_ifg_t *ifg = env->co->cenv->ifg;
774 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
781 /* mark the node as visited and add it to the cloud. */
783 list_add(&ci->cloud_list, &cloud->members_head);
785 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
787 /* determine the nodes costs */
788 co_gs_foreach_neighb(a, n) {
790 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
791 if (be_ifg_connected(ifg, a->irn, n->irn))
792 cloud->inevit += n->costs;
795 /* add the node's cost to the total costs of the cloud. */
797 cloud->costs += costs;
798 cloud->n_constr += is_constrained(env, &ci->inh);
799 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
800 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
803 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
804 if (costs >= curr_costs) {
809 /* add all the neighbors of the node to the cloud. */
810 co_gs_foreach_neighb(a, n) {
811 affinity_node_t *an = get_affinity_info(env->co, n->irn);
813 populate_cloud(env, cloud, an, curr_costs);
817 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
819 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
823 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
824 memset(cloud, 0, sizeof(cloud[0]));
825 INIT_LIST_HEAD(&cloud->members_head);
826 INIT_LIST_HEAD(&cloud->list);
827 list_add(&cloud->list, &env->cloud_head);
828 cloud->best_costs = INT_MAX;
831 populate_cloud(env, cloud, a, 0);
832 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
834 /* Also allocate space for the node sequence and compute that sequence. */
835 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
838 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
840 cloud->seq[i++] = ci;
842 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
847 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
849 const ir_node *irn = ci->inh.irn;
850 int *front = FRONT_BASE(ci, col);
852 struct list_head changed;
854 INIT_LIST_HEAD(&changed);
856 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
857 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
858 // assert(ok && "Color changing may not fail while committing the coloring");
859 materialize_coloring(&changed);
861 for (i = 0; i < ci->mst_n_childs; ++i) {
862 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
866 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
868 while (ci != ci->mst_parent)
874 static void process_cloud(co2_cloud_t *cloud)
876 co2_t *env = cloud->env;
877 int n_regs = env->n_regs;
879 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
886 /* Collect all edges in the cloud on an obstack and sort the increasingly */
887 obstack_init(&cloud->obst);
888 for (i = 0; i < cloud->n_memb; ++i) {
889 co2_cloud_irn_t *ci = cloud->seq[i];
892 co_gs_foreach_neighb(ci->inh.aff, n) {
893 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
894 if (ci->index < ni->index) {
899 obstack_grow(&cloud->obst, &e, sizeof(e));
904 edges = obstack_finish(&cloud->obst);
905 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
907 /* Compute the maximum spanning tree using Kruskal/Union-Find */
908 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
909 for (i = 0; i < n_edges; ++i) {
910 edge_t *e = &edges[i];
911 co2_cloud_irn_t *rs = find_mst_root(e->src);
912 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
914 /* if the union/find roots are different */
916 int si = e->src->index;
917 int ti = e->tgt->index;
921 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
923 /* this edge is in the MST, so set it in the bitset. */
924 mst_edges[si * cloud->n_memb + ti] = e->costs;
925 mst_edges[ti * cloud->n_memb + si] = e->costs;
928 obstack_free(&cloud->obst, edges);
930 cloud->master->mst_parent = cloud->master;
931 cloud->mst_root = cloud->master;
932 q = new_pdeq1(cloud->master);
933 while (!pdeq_empty(q)) {
934 co2_cloud_irn_t *ci = pdeq_getl(q);
935 int ofs = ci->index * cloud->n_memb;
936 int end = ofs + cloud->n_memb;
939 ci->mst_n_childs = 0;
940 for (i = ofs; i < end; ++i) {
941 if (mst_edges[i] != 0) {
943 co2_cloud_irn_t *child = cloud->seq[i - ofs];
945 /* put the child to the worklist */
948 /* make ci the parent of the child and add the child to the children array of the parent */
949 child->mst_parent = ci;
950 child->mst_costs = mst_edges[i];
952 obstack_ptr_grow(&cloud->obst, child);
954 mst_edges[other * cloud->n_memb + ci->index] = 0;
959 obstack_ptr_grow(&cloud->obst, NULL);
960 ci->mst_childs = obstack_finish(&cloud->obst);
966 DBG((env->dbg, LEVEL_3, "mst:\n"));
967 for (i = 0; i < cloud->n_memb; ++i) {
968 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
969 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
972 for (i = 0; i < cloud->n_memb; ++i) {
973 co2_cloud_irn_t *ci = cloud->seq[i];
974 int n_childs = ci->mst_n_childs;
977 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
978 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
979 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
980 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
982 for (j = 0; j < env->n_regs; j++)
983 ci->col_costs[j] = INT_MAX;
986 determine_color_badness(cloud->mst_root, 0);
987 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
988 unfix_subtree(cloud->mst_root);
989 apply_coloring(cloud->mst_root, best_col, 0);
991 /* The coloring should represent the one with the best costs. */
992 //materialize_coloring(&changed);
993 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
994 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
996 /* Fix all nodes in the cloud. */
997 for (i = 0; i < cloud->n_memb; ++i)
998 cloud->seq[i]->inh.fixed = 1;
1000 /* Free all space used while optimizing this cloud. */
1001 obstack_free(&cloud->obst, NULL);
1004 static int cloud_costs(co2_cloud_t *cloud)
1009 for (i = 0; i < cloud->n_memb; ++i) {
1010 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1011 col_t col = get_col(cloud->env, ci->irn);
1012 co_gs_foreach_neighb(ci->aff, n) {
1013 col_t n_col = get_col(cloud->env, n->irn);
1014 costs += col != n_col ? n->costs : 0;
1021 static void process(co2_t *env)
1025 co2_cloud_t **clouds;
1030 int final_costs = 0;
1033 co_gs_foreach_aff_node(env->co, a) {
1034 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1043 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1044 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1046 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1048 for (i = 0; i < n_clouds; ++i) {
1049 init_costs += cloud_costs(clouds[i]);
1051 /* Process the cloud. */
1052 process_cloud(clouds[i]);
1054 all_costs += clouds[i]->costs;
1055 final_costs += cloud_costs(clouds[i]);
1057 /* Dump the IFG if the user demanded it. */
1058 if (dump_flags & DUMP_CLOUD) {
1062 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1063 f = fopen(buf, "wt");
1065 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1071 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1076 static void writeback_colors(co2_t *env)
1080 for (irn = env->touched; irn; irn = irn->touched_next) {
1081 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1082 arch_set_irn_register((ir_node*)irn->irn, reg);
1088 ___ _____ ____ ____ ___ _____ ____ _
1089 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1090 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1091 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1092 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1096 static const char *get_dot_color_name(size_t col)
1098 static const char *const names[] = {
1132 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1135 static const char *get_dot_shape_name(co2_irn_t *ci)
1137 const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
1139 if (arch_register_req_is(req, limited))
1151 static void ifg_dump_graph_attr(FILE *f, void *self)
1154 fprintf(f, "overlay=false");
1157 static int ifg_is_dump_node(void *self, ir_node *irn)
1159 const arch_register_req_t *req = arch_get_register_req_out(irn);
1161 return !(req->type & arch_register_req_type_ignore);
1164 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1167 co2_irn_t *ci = get_co2_irn(env, irn);
1173 co2_cloud_irn_t *cci = (void *) ci;
1174 if (cci->cloud && cci->cloud->mst_root == cci)
1177 if (cci->cloud && cci->cloud->mst_root)
1178 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1181 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1182 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1185 static void ifg_dump_at_end(FILE *file, void *self)
1190 co_gs_foreach_aff_node(env->co, a) {
1191 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1192 int idx = get_irn_idx(a->irn);
1195 if (ai->mst_parent != ai)
1196 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1198 co_gs_foreach_neighb(a, n) {
1199 int nidx = get_irn_idx(n->irn);
1200 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1203 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1204 const char *arr = "arrowhead=dot arrowtail=dot";
1206 if (ci->mst_parent == ai)
1207 arr = "arrowtail=normal";
1208 else if (ai->mst_parent == ci)
1209 arr = "arrowhead=normal";
1211 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1218 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1220 ifg_dump_graph_attr,
1227 int co_solve_heuristic_new(copy_opt_t *co)
1233 phase_init(&env.ph, co->cenv->birg->irg, co2_irn_init);
1237 env.n_regs = co->cls->n_regs;
1238 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1239 be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs);
1240 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1241 INIT_LIST_HEAD(&env.cloud_head);
1243 if (dump_flags & DUMP_BEFORE) {
1244 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1245 f = fopen(buf, "wt");
1247 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1254 if (dump_flags & DUMP_AFTER) {
1255 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1256 f = fopen(buf, "wt");
1258 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1263 writeback_colors(&env);
1264 phase_deinit(&env.ph);
1268 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
1269 void be_init_copyheur2(void)
1271 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1272 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1273 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1274 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1276 static co_algo_info copyheur = {
1277 co_solve_heuristic_new, 0
1280 lc_opt_add_table(co2_grp, options);
1281 be_register_copyopt("heur2", ©heur);