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
37 #include "raw_bitset.h"
40 #include "bitfiddle.h"
42 #include "irphase_t.h"
43 #include "irgraph_t.h"
51 #include "becopyopt.h"
52 #include "becopyopt_t.h"
53 #include "bechordal_t.h"
59 #define DUMP_ALL 2 * DUMP_CLOUD - 1
61 static unsigned dump_flags = 0;
62 static int subtree_iter = 4;
63 static int max_depth = 20;
64 static double constr_factor = 0.9;
67 #include <libcore/lc_opts.h>
68 #include <libcore/lc_opts_enum.h>
70 /* Options using libcore */
71 static const lc_opt_enum_mask_items_t dump_items[] = {
72 { "before", DUMP_BEFORE },
73 { "after", DUMP_AFTER },
74 { "cloud", DUMP_CLOUD },
79 static lc_opt_enum_mask_var_t dump_var = {
80 &dump_flags, dump_items
83 static const lc_opt_table_entry_t options[] = {
84 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
85 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
86 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
87 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
90 #endif /* WITH_LIBCORE */
92 void be_init_copyheur2(void)
95 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
96 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
97 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
98 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
100 lc_opt_add_table(co2_grp, options);
104 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
108 / ___|| |_ __ _ _ __| |_
109 \___ \| __/ _` | '__| __|
110 ___) | || (_| | | | |_
111 |____/ \__\__,_|_| \__|
115 #define INFEASIBLE(cost) ((cost) == INT_MAX)
117 static be_ifg_dump_dot_cb_t ifg_dot_cb;
119 typedef unsigned col_t;
121 typedef struct _co2_irn_t co2_irn_t;
122 typedef struct _co2_cloud_t co2_cloud_t;
123 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
133 bitset_t *ignore_regs;
137 struct list_head cloud_head;
138 DEBUG_ONLY(firm_dbg_module_t *dbg;)
143 affinity_node_t *aff;
144 co2_irn_t *touched_next;
147 int last_color_change;
150 unsigned tmp_fixed : 1;
151 unsigned is_constrained : 1;
152 struct list_head changed_list;
155 struct _co2_cloud_irn_t {
156 struct _co2_irn_t inh;
160 co2_cloud_irn_t *mst_parent;
163 co2_cloud_irn_t **mst_childs;
168 col_cost_pair_t *tmp_coloring;
169 struct list_head cloud_list;
170 struct list_head mst_list;
173 struct _co2_cloud_t {
185 co2_cloud_irn_t *master;
186 co2_cloud_irn_t *mst_root;
187 co2_cloud_irn_t **seq;
188 struct list_head members_head;
189 struct list_head list;
193 co2_cloud_irn_t *src, *tgt;
197 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
199 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
200 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
202 static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
204 co2_t *env = (co2_t *) ph;
205 affinity_node_t *a = get_affinity_info(env->co, irn);
206 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
207 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
210 INIT_LIST_HEAD(&ci->changed_list);
211 ci->touched_next = env->touched;
212 ci->orig_col = get_irn_col(env->co, irn);
218 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
219 INIT_LIST_HEAD(&cci->cloud_list);
220 cci->mst_parent = cci;
226 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
228 static int cmp_clouds_gt(const void *a, const void *b)
230 const co2_cloud_t * const *p = a;
231 const co2_cloud_t * const *q = b;
232 double c = CLOUD_WEIGHT(*p);
233 double d = CLOUD_WEIGHT(*q);
234 return QSORT_CMP(d, c);
238 * An order on color/costs pairs.
239 * If the costs are equal, we use the color as a kind of normalization.
241 static int col_cost_pair_lt(const void *a, const void *b)
243 const col_cost_pair_t *p = a;
244 const col_cost_pair_t *q = b;
247 return QSORT_CMP(c, d);
250 int cmp_edges(const void *a, const void *b)
254 return QSORT_CMP(q->costs, p->costs);
257 static col_t get_col(co2_t *env, ir_node *irn)
259 co2_irn_t *ci = get_co2_irn(env, irn);
260 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
263 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
265 co2_irn_t *ci = get_co2_irn(env, irn);
266 return ci->fixed || ci->tmp_fixed;
269 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
271 if(ci->adm_cache == NULL) {
272 const arch_register_req_t *req;
273 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
274 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
276 if(arch_register_req_is(req, limited)) {
280 for(i = 0; i < n; ++i) {
281 if(rbitset_is_set(req->limited, i))
282 bitset_set(ci->adm_cache, i);
284 ci->is_constrained = 1;
286 bitset_copy(ci->adm_cache, env->ignore_regs);
287 bitset_flip_all(ci->adm_cache);
291 return ci->adm_cache;
294 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
296 bitset_copy(bs, get_adm(env, ci));
300 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
302 bitset_t *bs = get_adm(env, ci);
303 return bitset_is_set(bs, col);
306 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
310 return ci->is_constrained;
313 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
315 const arch_register_req_t *req;
317 req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
319 if (arch_register_req_is(req, limited)) {
320 unsigned n_regs = env->co->cls->n_regs;
321 unsigned n_constr = 0;
324 n_constr = rbitset_popcnt(req->limited, n_regs);
325 for (i = 0; i < n_regs; ++i) {
326 if (rbitset_is_set(req->limited, i)) {
327 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
334 * Determine costs which shall indicate how cheap/expensive it is to try
335 * to assign a node some color.
336 * The costs are computed for all colors. INT_MAX means that it is impossible
337 * to give the node that specific color.
339 * @param env The co2 this pointer.
340 * @param irn The node.
341 * @param col_costs An array of colors x costs where the costs are written to.
343 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
345 ir_node *irn = ci->irn;
346 be_ifg_t *ifg = env->co->cenv->ifg;
347 int n_regs = env->co->cls->n_regs;
348 bitset_t *forb = bitset_alloca(n_regs);
349 affinity_node_t *a = ci->aff;
356 /* Put all forbidden colors into the aux bitset. */
357 admissible_colors(env, ci, forb);
358 bitset_flip_all(forb);
360 for(i = 0; i < n_regs; ++i) {
361 col_costs[i].col = i;
362 col_costs[i].costs = 0;
368 co_gs_foreach_neighb(a, n) {
369 if(color_is_fix(env, n->irn)) {
370 col_t col = get_col(env, n->irn);
371 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
374 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
378 it = be_ifg_neighbours_iter_alloca(ifg);
379 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
380 col_t col = get_col(env, pos);
381 if(color_is_fix(env, pos)) {
382 col_costs[col].costs = INT_MAX;
385 incur_constraint_costs(env, pos, col_costs, INT_MAX);
386 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
389 be_ifg_neighbours_break(ifg, it);
391 /* Set the costs to infinity for each color which is not allowed at this node. */
392 bitset_foreach(forb, elm) {
393 col_costs[elm].costs = INT_MAX;
398 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
400 int n_regs = env->co->cls->n_regs;
403 for(i = 0; i < n_regs; ++i) {
405 seq[i].costs = INT_MAX;
408 assert(is_color_admissible(env, ci, col));
414 static void reject_coloring(struct list_head *h)
418 list_for_each_entry(co2_irn_t, pos, h, changed_list)
422 static void materialize_coloring(struct list_head *h)
426 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
427 pos->orig_col = pos->tmp_col;
432 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
434 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
436 int n_regs = env->co->cls->n_regs;
437 be_ifg_t *ifg = env->co->cenv->ifg;
438 co2_irn_t *ci = get_co2_irn(env, irn);
443 if(depth >= max_depth)
446 for(i = 0; i < n_regs; ++i) {
447 col_t tgt_col = col_list[i].col;
448 unsigned costs = col_list[i].costs;
451 struct list_head changed;
455 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
457 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
458 if(INFEASIBLE(costs)) {
459 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
464 /* Set the new color of the node and mark the node as temporarily fixed. */
465 ci->tmp_col = tgt_col;
469 If that color has costs > 0, there's at least one neighbor having that color,
470 so we will try to change the neighbors' colors, too.
472 INIT_LIST_HEAD(&changed);
473 list_add(&ci->changed_list, &changed);
475 it = be_ifg_neighbours_iter_alloca(ifg);
476 be_ifg_foreach_neighbour(ifg, it, irn, n) {
478 /* try to re-color the neighbor if it has the target color. */
479 if(get_col(env, n) == tgt_col) {
480 struct list_head tmp;
483 Try to change the color of the neighbor and record all nodes which
484 get changed in the tmp list. Add this list to the "changed" list for
485 that color. If we did not succeed to change the color of the neighbor,
486 we bail out and try the next color.
488 INIT_LIST_HEAD(&tmp);
489 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
490 list_splice(&tmp, &changed);
495 be_ifg_neighbours_break(ifg, it);
498 We managed to assign the target color to all neighbors, so from the perspective
499 of the current node, every thing was ok and we can return safely.
502 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
503 list_splice(&changed, parent_changed);
509 If not, that color did not succeed and we unfix all nodes we touched
510 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
513 reject_coloring(&changed);
519 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
521 co2_irn_t *ci = get_co2_irn(env, irn);
523 col_t col = get_col(env, irn);
525 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
527 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
534 list_add(&ci->changed_list, parent_changed);
538 /* The node has the color it should not have _and_ has not been visited yet. */
539 if(!color_is_fix(env, irn)) {
540 int n_regs = env->co->cls->n_regs;
541 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
543 /* Get the costs for giving the node a specific color. */
544 determine_color_costs(env, ci, csts);
546 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
547 csts[not_col].costs = INT_MAX;
549 /* sort the colors according costs, cheapest first. */
550 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
552 /* Try recoloring the node using the color list. */
553 res = recolor(env, irn, csts, parent_changed, depth);
556 /* If we came here, everything went ok. */
560 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
562 co2_irn_t *ci = get_co2_irn(env, irn);
563 col_t col = get_col(env, irn);
566 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
568 /* the node has the wanted color. That's fine, mark it as visited and return. */
573 list_add(&ci->changed_list, parent_changed);
580 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
581 int n_regs = env->co->cls->n_regs;
582 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
584 /* Get the costs for giving the node a specific color. */
585 single_color_cost(env, ci, tgt_col, seq);
587 /* Try recoloring the node using the color list. */
588 res = recolor(env, irn, seq, parent_changed, depth);
593 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
598 * Examine the costs of the current coloring concerning a MST subtree.
599 * @param ci The subtree root.
600 * @param col The color of @p ci.
601 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
603 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
605 int *front = FRONT_BASE(ci, col);
609 for(i = 0; i < ci->mst_n_childs; ++i) {
610 co2_cloud_irn_t *chld = ci->mst_childs[i];
611 col_t chld_col = front[i];
613 cost += examine_subtree_coloring(chld, chld_col);
614 cost += col != chld_col ? chld->mst_costs : 0;
621 * Determine color badnesses of a node.
622 * Badness means that it is unlikely that the node in question can
623 * obtain a color. The higher the badness, the more unlikely it is that
624 * the node can be assigned that color.
625 * @param ci The node.
626 * @param badness An integer array as long as there are registers.
627 * @note The array <code>badness</code> is not cleared.
629 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
631 co2_t *env = ci->cloud->env;
632 co2_irn_t *ir = &ci->inh;
633 int n_regs = env->n_regs;
634 be_ifg_t *ifg = env->co->cenv->ifg;
635 bitset_t *bs = bitset_alloca(n_regs);
641 admissible_colors(env, &ci->inh, bs);
643 bitset_foreach(bs, elm)
644 badness[elm] = ci->costs;
646 /* Use constrained/fixed interfering neighbors to influence the color badness */
647 it = be_ifg_neighbours_iter_alloca(ifg);
648 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
649 co2_irn_t *ni = get_co2_irn(env, irn);
651 admissible_colors(env, ni, bs);
652 if(bitset_popcnt(bs) == 1) {
653 bitset_pos_t c = bitset_next_set(bs, 0);
654 badness[c] += ci->costs;
658 col_t c = get_col(env, ni->irn);
659 badness[c] += ci->costs;
662 be_ifg_neighbours_break(ifg, it);
666 * Determine the badness of a MST subtree.
667 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
668 * @see node_color_badness() for a definition of badness.
669 * @param ci The root of the subtree.
670 * @param depth Depth for debugging purposes.
672 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
674 co2_t *env = ci->cloud->env;
677 node_color_badness(ci, ci->color_badness);
679 /* Collect the color badness for the whole subtree */
680 for(i = 0; i < ci->mst_n_childs; ++i) {
681 co2_cloud_irn_t *child = ci->mst_childs[i];
682 determine_color_badness(child, depth + 1);
684 for(j = 0; j < env->n_regs; ++j)
685 ci->color_badness[j] += child->color_badness[j];
688 for(j = 0; j < env->n_regs; ++j)
689 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
693 * Unfix all nodes in a MST subtree.
695 static void unfix_subtree(co2_cloud_irn_t *ci)
700 for(i = 0; i < ci->mst_n_childs; ++i)
701 unfix_subtree(ci->mst_childs[i]);
704 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
706 co2_t *env = ci->cloud->env;
707 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
708 int is_root = ci->mst_parent == ci;
709 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
710 int min_badness = INT_MAX;
711 int best_col_costs = INT_MAX;
713 int n_regs = env->n_regs;
714 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
716 struct list_head changed;
719 for(i = 0; i < n_regs; ++i) {
720 int badness = ci->color_badness[i];
723 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
725 min_badness = MIN(min_badness, badness);
728 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
729 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
730 seq[parent_col].costs = min_badness - 1;
732 /* Sort the colors. The will be processed in that ordering. */
733 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
735 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
736 INIT_LIST_HEAD(&changed);
737 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
738 col_t col = seq[i].col;
739 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
741 int subtree_costs, sum_costs;
743 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
746 INIT_LIST_HEAD(&changed);
747 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
749 materialize_coloring(&changed);
756 for(j = 0; j < ci->mst_n_childs; ++j) {
757 co2_cloud_irn_t *child = ci->mst_childs[j];
758 ok = coalesce_top_down(child, j, depth + 1) >= 0;
760 child->inh.fixed = 1;
765 /* If the subtree could not be colored, we have to try another color. */
769 subtree_costs = examine_subtree_coloring(ci, col);
770 sum_costs = subtree_costs + add_cost;
771 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
773 if(sum_costs < best_col_costs) {
775 best_col_costs = sum_costs;
776 ci->col_costs[col] = subtree_costs;
784 int *front = FRONT_BASE(ci->mst_parent, parent_col);
785 front[child_nr] = best_col;
791 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
793 be_ifg_t *ifg = env->co->cenv->ifg;
794 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
801 /* mark the node as visited and add it to the cloud. */
803 list_add(&ci->cloud_list, &cloud->members_head);
805 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
807 /* determine the nodes costs */
808 co_gs_foreach_neighb(a, n) {
810 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
811 if(be_ifg_connected(ifg, a->irn, n->irn))
812 cloud->inevit += n->costs;
815 /* add the node's cost to the total costs of the cloud. */
817 cloud->costs += costs;
818 cloud->n_constr += is_constrained(env, &ci->inh);
819 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
820 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
823 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
824 if(costs >= curr_costs) {
829 /* add all the neighbors of the node to the cloud. */
830 co_gs_foreach_neighb(a, n) {
831 affinity_node_t *an = get_affinity_info(env->co, n->irn);
833 populate_cloud(env, cloud, an, curr_costs);
837 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
839 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
843 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
844 memset(cloud, 0, sizeof(cloud[0]));
845 INIT_LIST_HEAD(&cloud->members_head);
846 INIT_LIST_HEAD(&cloud->list);
847 list_add(&cloud->list, &env->cloud_head);
848 cloud->best_costs = INT_MAX;
851 populate_cloud(env, cloud, a, 0);
852 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
854 /* Also allocate space for the node sequence and compute that sequence. */
855 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
858 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
860 cloud->seq[i++] = ci;
862 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
867 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
869 ir_node *irn = ci->inh.irn;
870 int *front = FRONT_BASE(ci, col);
872 struct list_head changed;
874 INIT_LIST_HEAD(&changed);
876 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
877 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
878 // assert(ok && "Color changing may not fail while committing the coloring");
879 materialize_coloring(&changed);
881 for(i = 0; i < ci->mst_n_childs; ++i) {
882 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
886 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
888 while(ci != ci->mst_parent)
894 static void process_cloud(co2_cloud_t *cloud)
896 co2_t *env = cloud->env;
897 int n_regs = env->n_regs;
899 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
906 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
908 /* Collect all edges in the cloud on an obstack and sort the increasingly */
909 obstack_init(&cloud->obst);
910 for(i = 0; i < cloud->n_memb; ++i) {
911 co2_cloud_irn_t *ci = cloud->seq[i];
914 co_gs_foreach_neighb(ci->inh.aff, n) {
915 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
916 if(ci->index < ni->index) {
921 obstack_grow(&cloud->obst, &e, sizeof(e));
926 edges = obstack_finish(&cloud->obst);
927 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
929 /* Compute the maximum spanning tree using Kruskal/Union-Find */
930 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
931 for(i = 0; i < n_edges; ++i) {
932 edge_t *e = &edges[i];
933 co2_cloud_irn_t *rs = find_mst_root(e->src);
934 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
936 /* if the union/find roots are different */
938 int si = e->src->index;
939 int ti = e->tgt->index;
943 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
945 /* this edge is in the MST, so set it in the bitset. */
946 mst_edges[si * cloud->n_memb + ti] = e->costs;
947 mst_edges[ti * cloud->n_memb + si] = e->costs;
950 obstack_free(&cloud->obst, edges);
952 cloud->master->mst_parent = cloud->master;
953 cloud->mst_root = cloud->master;
954 q = new_pdeq1(cloud->master);
955 while(!pdeq_empty(q)) {
956 co2_cloud_irn_t *ci = pdeq_getl(q);
957 int ofs = ci->index * cloud->n_memb;
958 int end = ofs + cloud->n_memb;
961 ci->mst_n_childs = 0;
962 for(i = ofs; i < end; ++i) {
963 if(mst_edges[i] != 0) {
965 co2_cloud_irn_t *child = cloud->seq[i - ofs];
967 /* put the child to the worklist */
970 /* make ci the parent of the child and add the child to the children array of the parent */
971 child->mst_parent = ci;
972 child->mst_costs = mst_edges[i];
974 obstack_ptr_grow(&cloud->obst, child);
976 mst_edges[other * cloud->n_memb + ci->index] = 0;
981 obstack_ptr_grow(&cloud->obst, NULL);
982 ci->mst_childs = obstack_finish(&cloud->obst);
988 DBG((env->dbg, LEVEL_3, "mst:\n"));
989 for(i = 0; i < cloud->n_memb; ++i) {
990 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
991 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
994 for(i = 0; i < cloud->n_memb; ++i) {
995 co2_cloud_irn_t *ci = cloud->seq[i];
996 int n_childs = ci->mst_n_childs;
999 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
1000 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
1001 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
1002 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
1003 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
1004 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
1005 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
1006 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
1008 for(j = 0; j < env->n_regs; j++)
1009 ci->col_costs[j] = INT_MAX;
1013 determine_color_badness(cloud->mst_root, 0);
1014 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1015 unfix_subtree(cloud->mst_root);
1016 apply_coloring(cloud->mst_root, best_col, 0);
1018 /* The coloring should represent the one with the best costs. */
1019 //materialize_coloring(&changed);
1020 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1021 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1023 /* Fix all nodes in the cloud. */
1024 for(i = 0; i < cloud->n_memb; ++i)
1025 cloud->seq[i]->inh.fixed = 1;
1027 /* Free all space used while optimizing this cloud. */
1028 obstack_free(&cloud->obst, NULL);
1031 static int cloud_costs(co2_cloud_t *cloud)
1036 for(i = 0; i < cloud->n_memb; ++i) {
1037 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1038 col_t col = get_col(cloud->env, ci->irn);
1039 co_gs_foreach_neighb(ci->aff, n) {
1040 col_t n_col = get_col(cloud->env, n->irn);
1041 costs += col != n_col ? n->costs : 0;
1048 static void process(co2_t *env)
1052 co2_cloud_t **clouds;
1057 int final_costs = 0;
1060 co_gs_foreach_aff_node(env->co, a) {
1061 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1070 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1071 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1073 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1075 for(i = 0; i < n_clouds; ++i) {
1076 init_costs += cloud_costs(clouds[i]);
1078 /* Process the cloud. */
1079 process_cloud(clouds[i]);
1081 all_costs += clouds[i]->costs;
1082 final_costs += cloud_costs(clouds[i]);
1084 /* Dump the IFG if the user demanded it. */
1085 if (dump_flags & DUMP_CLOUD) {
1089 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1090 f = fopen(buf, "wt");
1092 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1098 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1103 static void writeback_colors(co2_t *env)
1105 const arch_env_t *aenv = env->co->aenv;
1108 for(irn = env->touched; irn; irn = irn->touched_next) {
1109 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1110 arch_set_irn_register(aenv, irn->irn, reg);
1116 ___ _____ ____ ____ ___ _____ ____ _
1117 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1118 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1119 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1120 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1124 static const char *get_dot_color_name(size_t col)
1126 static const char *names[] = {
1160 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1163 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1165 const arch_register_req_t *req;
1167 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
1168 if(arch_register_req_is(req, limited))
1180 static void ifg_dump_graph_attr(FILE *f, void *self)
1183 fprintf(f, "overlay=false");
1186 static int ifg_is_dump_node(void *self, ir_node *irn)
1189 return !arch_irn_is(env->co->aenv, irn, ignore);
1192 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1195 co2_irn_t *ci = get_co2_irn(env, irn);
1201 co2_cloud_irn_t *cci = (void *) ci;
1202 if (cci->cloud && cci->cloud->mst_root == cci)
1205 if(cci->cloud && cci->cloud->mst_root)
1206 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1209 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1210 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1213 static void ifg_dump_at_end(FILE *file, void *self)
1218 co_gs_foreach_aff_node(env->co, a) {
1219 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1220 int idx = get_irn_idx(a->irn);
1223 if(ai->mst_parent != ai)
1224 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1226 co_gs_foreach_neighb(a, n) {
1227 int nidx = get_irn_idx(n->irn);
1228 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1231 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1232 const char *arr = "arrowhead=dot arrowtail=dot";
1234 if(ci->mst_parent == ai)
1235 arr = "arrowtail=normal";
1236 else if(ai->mst_parent == ci)
1237 arr = "arrowhead=normal";
1239 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1246 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1248 ifg_dump_graph_attr,
1256 int co_solve_heuristic_new(copy_opt_t *co)
1262 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1266 env.n_regs = co->cls->n_regs;
1267 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1268 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1269 bitset_flip_all(env.ignore_regs);
1270 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1271 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1272 INIT_LIST_HEAD(&env.cloud_head);
1274 if(dump_flags & DUMP_BEFORE) {
1275 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.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);
1285 if(dump_flags & DUMP_AFTER) {
1286 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1287 f = fopen(buf, "wt");
1289 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1294 writeback_colors(&env);
1295 phase_free(&env.ph);