3 * More experiments on coalescing.
4 * @author Sebastian Hack
13 #include <libcore/lc_opts.h>
14 #include <libcore/lc_opts_enum.h>
15 #endif /* WITH_LIBCORE */
25 #include "bitfiddle.h"
27 #include "irphase_t.h"
28 #include "irgraph_t.h"
35 #include "becopyopt.h"
36 #include "becopyopt_t.h"
37 #include "bechordal_t.h"
42 #define DUMP_ALL 2 * DUMP_CLOUD - 1
44 static int dump_flags = 0;
45 static int subtree_iter = 4;
46 static int max_depth = 10;
47 static double constr_factor = 0.9;
49 /* Options using libcore */
52 static const lc_opt_enum_mask_items_t dump_items[] = {
53 { "before", DUMP_BEFORE },
54 { "after", DUMP_AFTER },
55 { "cloud", DUMP_CLOUD },
60 static lc_opt_enum_mask_var_t dump_var = {
61 &dump_flags, dump_items
64 static const lc_opt_table_entry_t options[] = {
65 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var),
66 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes (standard: 3)", &subtree_iter),
67 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
68 LC_OPT_ENT_INT ("max", "maximum recursion depth (default 20)", &max_depth),
72 void be_co2_register_options(lc_opt_entry_t *grp)
74 lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
75 lc_opt_add_table(co2_grp, options);
81 / ___|| |_ __ _ _ __| |_
82 \___ \| __/ _` | '__| __|
83 ___) | || (_| | | | |_
84 |____/ \__\__,_|_| \__|
88 #define INFEASIBLE(cost) ((cost) == INT_MAX)
90 static be_ifg_dump_dot_cb_t ifg_dot_cb;
92 typedef unsigned col_t;
94 typedef struct _co2_irn_t co2_irn_t;
95 typedef struct _co2_cloud_t co2_cloud_t;
96 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
106 bitset_t *ignore_regs;
110 struct list_head cloud_head;
111 DEBUG_ONLY(firm_dbg_module_t *dbg;)
116 affinity_node_t *aff;
117 co2_irn_t *touched_next;
120 int last_color_change;
123 unsigned tmp_fixed : 1;
124 unsigned is_constrained : 1;
125 struct list_head changed_list;
128 struct _co2_cloud_irn_t {
129 struct _co2_irn_t inh;
133 co2_cloud_irn_t *mst_parent;
136 co2_cloud_irn_t **mst_childs;
141 col_cost_pair_t *tmp_coloring;
142 struct list_head cloud_list;
143 struct list_head mst_list;
146 struct _co2_cloud_t {
158 co2_cloud_irn_t *master;
159 co2_cloud_irn_t *mst_root;
160 co2_cloud_irn_t **seq;
161 struct list_head members_head;
162 struct list_head list;
166 co2_cloud_irn_t *src, *tgt;
170 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
172 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
173 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
175 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
177 co2_t *env = (co2_t *) ph;
178 affinity_node_t *a = get_affinity_info(env->co, irn);
179 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
180 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
183 INIT_LIST_HEAD(&ci->changed_list);
184 ci->touched_next = env->touched;
185 ci->orig_col = get_irn_col(env->co, irn);
191 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
192 INIT_LIST_HEAD(&cci->cloud_list);
193 cci->mst_parent = cci;
199 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
201 static int cmp_clouds_gt(const void *a, const void *b)
203 const co2_cloud_t **p = a;
204 const co2_cloud_t **q = b;
205 double c = CLOUD_WEIGHT(*p);
206 double d = CLOUD_WEIGHT(*q);
207 return QSORT_CMP(d, c);
211 * An order on color/costs pairs.
212 * If the costs are equal, we use the color as a kind of normalization.
214 static int col_cost_pair_lt(const void *a, const void *b)
216 const col_cost_pair_t *p = a;
217 const col_cost_pair_t *q = b;
220 return QSORT_CMP(c, d);
223 int cmp_edges(const void *a, const void *b)
227 return QSORT_CMP(q->costs, p->costs);
230 static col_t get_col(co2_t *env, ir_node *irn)
232 co2_irn_t *ci = get_co2_irn(env, irn);
233 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
236 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
238 co2_irn_t *ci = get_co2_irn(env, irn);
239 return ci->fixed || ci->tmp_fixed;
242 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
245 arch_register_req_t req;
246 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
247 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
248 if(arch_register_req_is(&req, limited)) {
249 req.limited(req.limited_env, ci->adm_cache);
250 ci->is_constrained = 1;
253 bitset_copy(ci->adm_cache, env->ignore_regs);
254 bitset_flip_all(ci->adm_cache);
258 return ci->adm_cache;
261 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
263 bitset_copy(bs, get_adm(env, ci));
267 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
269 bitset_t *bs = get_adm(env, ci);
270 return bitset_is_set(bs, col);
273 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
277 return ci->is_constrained;
280 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
282 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
283 arch_register_req_t req;
285 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
287 if(arch_register_req_is(&req, limited)) {
291 req.limited(req.limited_env, aux);
292 n_constr = bitset_popcnt(aux);
293 bitset_foreach(aux, elm) {
294 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
300 * Determine costs which shall indicate how cheap/expensive it is to try
301 * to assign a node some color.
302 * The costs are computed for all colors. INT_MAX means that it is impossible
303 * to give the node that specific color.
305 * @param env The co2 this pointer.
306 * @param irn The node.
307 * @param col_costs An array of colors x costs where the costs are written to.
309 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
311 ir_node *irn = ci->irn;
312 be_ifg_t *ifg = env->co->cenv->ifg;
313 int n_regs = env->co->cls->n_regs;
314 bitset_t *forb = bitset_alloca(n_regs);
315 affinity_node_t *a = ci->aff;
322 /* Put all forbidden colors into the aux bitset. */
323 admissible_colors(env, ci, forb);
324 bitset_flip_all(forb);
326 for(i = 0; i < n_regs; ++i) {
327 col_costs[i].col = i;
328 col_costs[i].costs = 0;
334 co_gs_foreach_neighb(a, n) {
335 if(color_is_fix(env, n->irn)) {
336 col_t col = get_col(env, n->irn);
337 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
340 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
344 it = be_ifg_neighbours_iter_alloca(ifg);
345 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
346 col_t col = get_col(env, pos);
347 if(color_is_fix(env, pos)) {
348 col_costs[col].costs = INT_MAX;
351 incur_constraint_costs(env, pos, col_costs, INT_MAX);
352 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
355 be_ifg_neighbours_break(ifg, it);
357 /* Set the costs to infinity for each color which is not allowed at this node. */
358 bitset_foreach(forb, elm) {
359 col_costs[elm].costs = INT_MAX;
364 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
366 int n_regs = env->co->cls->n_regs;
369 for(i = 0; i < n_regs; ++i) {
371 seq[i].costs = INT_MAX;
374 assert(is_color_admissible(env, ci, col));
380 static void reject_coloring(struct list_head *h)
384 list_for_each_entry(co2_irn_t, pos, h, changed_list)
388 static void materialize_coloring(struct list_head *h)
392 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
393 pos->orig_col = pos->tmp_col;
398 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
400 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
402 int n_regs = env->co->cls->n_regs;
403 be_ifg_t *ifg = env->co->cenv->ifg;
404 co2_irn_t *ci = get_co2_irn(env, irn);
410 if(depth >= max_depth)
413 for(i = 0; i < n_regs; ++i) {
414 col_t tgt_col = col_list[i].col;
415 unsigned costs = col_list[i].costs;
418 struct list_head changed;
422 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
424 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
425 if(INFEASIBLE(costs)) {
426 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
431 /* Set the new color of the node and mark the node as temporarily fixed. */
432 ci->tmp_col = tgt_col;
436 If that color has costs > 0, there's at least one neighbor having that color,
437 so we will try to change the neighbors' colors, too.
439 INIT_LIST_HEAD(&changed);
440 list_add(&ci->changed_list, &changed);
442 it = be_ifg_neighbours_iter_alloca(ifg);
443 be_ifg_foreach_neighbour(ifg, it, irn, n) {
445 /* try to re-color the neighbor if it has the target color. */
446 if(get_col(env, n) == tgt_col) {
447 struct list_head tmp;
450 Try to change the color of the neighbor and record all nodes which
451 get changed in the tmp list. Add this list to the "changed" list for
452 that color. If we did not succeed to change the color of the neighbor,
453 we bail out and try the next color.
455 INIT_LIST_HEAD(&tmp);
456 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
457 list_splice(&tmp, &changed);
462 be_ifg_neighbours_break(ifg, it);
465 We managed to assign the target color to all neighbors, so from the perspective
466 of the current node, every thing was ok and we can return safely.
469 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
470 list_splice(&changed, parent_changed);
476 If not, that color did not succeed and we unfix all nodes we touched
477 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
480 reject_coloring(&changed);
486 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
488 co2_irn_t *ci = get_co2_irn(env, irn);
490 col_t col = get_col(env, irn);
492 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
494 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
501 list_add(&ci->changed_list, parent_changed);
505 /* The node has the color it should not have _and_ has not been visited yet. */
506 if(!color_is_fix(env, irn)) {
507 int n_regs = env->co->cls->n_regs;
508 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
510 /* Get the costs for giving the node a specific color. */
511 determine_color_costs(env, ci, csts);
513 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
514 csts[not_col].costs = INT_MAX;
516 /* sort the colors according costs, cheapest first. */
517 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
519 /* Try recoloring the node using the color list. */
520 res = recolor(env, irn, csts, parent_changed, depth);
523 /* If we came here, everything went ok. */
527 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
529 co2_irn_t *ci = get_co2_irn(env, irn);
530 col_t col = get_col(env, irn);
533 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
535 /* the node has the wanted color. That's fine, mark it as visited and return. */
540 list_add(&ci->changed_list, parent_changed);
547 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
548 int n_regs = env->co->cls->n_regs;
549 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
551 /* Get the costs for giving the node a specific color. */
552 single_color_cost(env, ci, tgt_col, seq);
554 /* Try recoloring the node using the color list. */
555 res = recolor(env, irn, seq, parent_changed, depth);
560 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
565 * Examine the costs of the current coloring concerning a MST subtree.
566 * @param ci The subtree root.
567 * @param col The color of @p ci.
568 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
570 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
572 int *front = FRONT_BASE(ci, col);
576 for(i = 0; i < ci->mst_n_childs; ++i) {
577 co2_cloud_irn_t *chld = ci->mst_childs[i];
578 col_t chld_col = front[i];
580 cost += examine_subtree_coloring(chld, chld_col);
581 cost += col != chld_col ? chld->mst_costs : 0;
588 * Determine color badnesses of a node.
589 * Badness means that it is unlikely that the node in question can
590 * obtain a color. The higher the badness, the more unlikely it is that
591 * the node can be assigned that color.
592 * @param ci The node.
593 * @param badness An integer array as long as there are registers.
594 * @note The array <code>badness</code> is not cleared.
596 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
598 co2_t *env = ci->cloud->env;
599 co2_irn_t *ir = &ci->inh;
600 int n_regs = env->n_regs;
601 be_ifg_t *ifg = env->co->cenv->ifg;
602 bitset_t *bs = bitset_alloca(n_regs);
608 admissible_colors(env, &ci->inh, bs);
610 bitset_foreach(bs, elm)
611 badness[elm] = ci->costs;
613 /* Use constrained/fixed interfering neighbors to influence the color badness */
614 it = be_ifg_neighbours_iter_alloca(ifg);
615 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
616 co2_irn_t *ni = get_co2_irn(env, irn);
618 admissible_colors(env, ni, bs);
619 if(bitset_popcnt(bs) == 1) {
620 bitset_pos_t c = bitset_next_set(bs, 0);
621 badness[c] += ci->costs;
625 col_t c = get_col(env, ni->irn);
626 badness[c] += ci->costs;
629 be_ifg_neighbours_break(ifg, it);
633 * Determine the badness of a MST subtree.
634 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
635 * @see node_color_badness() for a definition of badness.
636 * @param ci The root of the subtree.
637 * @param depth Depth for debugging purposes.
639 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
641 co2_t *env = ci->cloud->env;
644 node_color_badness(ci, ci->color_badness);
646 /* Collect the color badness for the whole subtree */
647 for(i = 0; i < ci->mst_n_childs; ++i) {
648 co2_cloud_irn_t *child = ci->mst_childs[i];
649 determine_color_badness(child, depth + 1);
651 for(j = 0; j < env->n_regs; ++j)
652 ci->color_badness[j] += child->color_badness[j];
655 for(j = 0; j < env->n_regs; ++j)
656 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
660 * Unfix all nodes in a MST subtree.
662 static void unfix_subtree(co2_cloud_irn_t *ci)
667 for(i = 0; i < ci->mst_n_childs; ++i)
668 unfix_subtree(ci->mst_childs[i]);
671 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
673 co2_t *env = ci->cloud->env;
674 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
675 int is_root = ci->mst_parent == ci;
676 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
677 int min_badness = INT_MAX;
678 int best_col_costs = INT_MAX;
680 int n_regs = env->n_regs;
681 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
683 struct list_head changed;
686 for(i = 0; i < n_regs; ++i) {
687 int badness = ci->color_badness[i];
690 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
692 min_badness = MIN(min_badness, badness);
695 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
696 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
697 seq[parent_col].costs = min_badness - 1;
699 /* Sort the colors. The will be processed in that ordering. */
700 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
702 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
703 INIT_LIST_HEAD(&changed);
704 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
705 col_t col = seq[i].col;
706 int costs = seq[i].costs;
707 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
709 int subtree_costs, sum_costs;
711 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
714 INIT_LIST_HEAD(&changed);
715 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
717 materialize_coloring(&changed);
724 for(j = 0; j < ci->mst_n_childs; ++j) {
725 co2_cloud_irn_t *child = ci->mst_childs[j];
726 ok = coalesce_top_down(child, j, depth + 1) >= 0;
728 child->inh.fixed = 1;
733 /* If the subtree could not be colored, we have to try another color. */
737 subtree_costs = examine_subtree_coloring(ci, col);
738 sum_costs = subtree_costs + add_cost;
739 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
741 if(sum_costs < best_col_costs) {
743 best_col_costs = sum_costs;
744 ci->col_costs[col] = subtree_costs;
752 int *front = FRONT_BASE(ci->mst_parent, parent_col);
753 front[child_nr] = best_col;
759 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
761 be_ifg_t *ifg = env->co->cenv->ifg;
762 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
769 /* mark the node as visited and add it to the cloud. */
771 list_add(&ci->cloud_list, &cloud->members_head);
773 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
775 /* determine the nodes costs */
776 co_gs_foreach_neighb(a, n) {
778 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
779 if(be_ifg_connected(ifg, a->irn, n->irn))
780 cloud->inevit += n->costs;
783 /* add the node's cost to the total costs of the cloud. */
785 cloud->costs += costs;
786 cloud->n_constr += is_constrained(env, &ci->inh);
787 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
788 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
791 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
792 if(costs >= curr_costs) {
797 /* add all the neighbors of the node to the cloud. */
798 co_gs_foreach_neighb(a, n) {
799 affinity_node_t *an = get_affinity_info(env->co, n->irn);
801 populate_cloud(env, cloud, an, curr_costs);
805 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
807 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
811 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
812 memset(cloud, 0, sizeof(cloud[0]));
813 INIT_LIST_HEAD(&cloud->members_head);
814 INIT_LIST_HEAD(&cloud->list);
815 list_add(&cloud->list, &env->cloud_head);
816 cloud->best_costs = INT_MAX;
819 populate_cloud(env, cloud, a, 0);
820 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
822 /* Also allocate space for the node sequence and compute that sequence. */
823 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
826 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
828 cloud->seq[i++] = ci;
830 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
835 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
837 ir_node *irn = ci->inh.irn;
838 int *front = FRONT_BASE(ci, col);
840 struct list_head changed;
842 INIT_LIST_HEAD(&changed);
844 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
845 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
846 assert(ok && "Color changing may not fail while committing the coloring");
847 materialize_coloring(&changed);
849 for(i = 0; i < ci->mst_n_childs; ++i) {
850 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
854 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
856 while(ci != ci->mst_parent)
862 static void process_cloud(co2_cloud_t *cloud)
864 co2_t *env = cloud->env;
865 int n_regs = env->n_regs;
867 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
870 struct list_head changed;
875 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
877 /* Collect all edges in the cloud on an obstack and sort the increasingly */
878 obstack_init(&cloud->obst);
879 for(i = 0; i < cloud->n_memb; ++i) {
880 co2_cloud_irn_t *ci = cloud->seq[i];
883 co_gs_foreach_neighb(ci->inh.aff, n) {
884 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
885 if(ci->index < ni->index) {
890 obstack_grow(&cloud->obst, &e, sizeof(e));
895 edges = obstack_finish(&cloud->obst);
896 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
898 /* Compute the maximum spanning tree using Kruskal/Union-Find */
899 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
900 for(i = 0; i < n_edges; ++i) {
901 edge_t *e = &edges[i];
902 co2_cloud_irn_t *rs = find_mst_root(e->src);
903 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
905 /* if the union/find roots are different */
907 int si = e->src->index;
908 int ti = e->tgt->index;
912 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
914 /* this edge is in the MST, so set it in the bitset. */
915 mst_edges[si * cloud->n_memb + ti] = e->costs;
916 mst_edges[ti * cloud->n_memb + si] = e->costs;
919 obstack_free(&cloud->obst, edges);
921 cloud->master->mst_parent = cloud->master;
922 cloud->mst_root = cloud->master;
923 q = new_pdeq1(cloud->master);
924 while(!pdeq_empty(q)) {
925 co2_cloud_irn_t *ci = pdeq_getl(q);
926 int ofs = ci->index * cloud->n_memb;
927 int end = ofs + cloud->n_memb;
930 ci->mst_n_childs = 0;
931 for(i = ofs; i < end; ++i) {
932 if(mst_edges[i] != 0) {
934 co2_cloud_irn_t *child = cloud->seq[i - ofs];
936 /* put the child to the worklist */
939 /* make ci the parent of the child and add the child to the children array of the parent */
940 child->mst_parent = ci;
941 child->mst_costs = mst_edges[i];
943 obstack_ptr_grow(&cloud->obst, child);
945 mst_edges[other * cloud->n_memb + ci->index] = 0;
950 obstack_ptr_grow(&cloud->obst, NULL);
951 ci->mst_childs = obstack_finish(&cloud->obst);
957 DBG((env->dbg, LEVEL_3, "mst:\n"));
958 for(i = 0; i < cloud->n_memb; ++i) {
959 co2_cloud_irn_t *ci = cloud->seq[i];
960 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
963 for(i = 0; i < cloud->n_memb; ++i) {
964 co2_cloud_irn_t *ci = cloud->seq[i];
965 int n_childs = ci->mst_n_childs;
968 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
969 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
970 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
971 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
972 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
973 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
974 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
975 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
977 for(j = 0; j < env->n_regs; j++)
978 ci->col_costs[j] = INT_MAX;
982 determine_color_badness(cloud->mst_root, 0);
983 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
984 unfix_subtree(cloud->mst_root);
985 apply_coloring(cloud->mst_root, best_col, 0);
987 /* The coloring should represent the one with the best costs. */
988 //materialize_coloring(&changed);
989 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
990 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
992 /* Fix all nodes in the cloud. */
993 for(i = 0; i < cloud->n_memb; ++i)
994 cloud->seq[i]->inh.fixed = 1;
996 /* Free all space used while optimizing this cloud. */
997 obstack_free(&cloud->obst, NULL);
1000 static int cloud_costs(co2_cloud_t *cloud)
1005 for(i = 0; i < cloud->n_memb; ++i) {
1006 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1007 col_t col = get_col(cloud->env, ci->irn);
1008 co_gs_foreach_neighb(ci->aff, n) {
1009 col_t n_col = get_col(cloud->env, n->irn);
1010 costs += col != n_col ? n->costs : 0;
1017 static void process(co2_t *env)
1021 co2_cloud_t **clouds;
1026 int final_costs = 0;
1029 co_gs_foreach_aff_node(env->co, a) {
1030 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1033 co2_cloud_t *cloud = new_cloud(env, a);
1039 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1040 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1042 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1044 for(i = 0; i < n_clouds; ++i) {
1045 init_costs += cloud_costs(clouds[i]);
1047 /* Process the cloud. */
1048 process_cloud(clouds[i]);
1050 all_costs += clouds[i]->costs;
1051 final_costs += cloud_costs(clouds[i]);
1053 /* Dump the IFG if the user demanded it. */
1054 if (dump_flags & DUMP_CLOUD) {
1058 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1059 if(f = fopen(buf, "wt")) {
1060 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1066 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1071 static void writeback_colors(co2_t *env)
1073 const arch_env_t *aenv = env->co->aenv;
1076 for(irn = env->touched; irn; irn = irn->touched_next) {
1077 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1078 arch_set_irn_register(aenv, irn->irn, reg);
1084 ___ _____ ____ ____ ___ _____ ____ _
1085 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1086 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1087 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1088 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1092 static const char *get_dot_color_name(int col)
1094 static const char *names[] = {
1128 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1131 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1133 arch_register_req_t req;
1135 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1136 if(arch_register_req_is(&req, limited))
1148 static void ifg_dump_graph_attr(FILE *f, void *self)
1150 fprintf(f, "overlay=false");
1153 static int ifg_is_dump_node(void *self, ir_node *irn)
1156 return !arch_irn_is(env->co->aenv, irn, ignore);
1159 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1162 co2_irn_t *ci = get_co2_irn(env, irn);
1168 co2_cloud_irn_t *cci = (void *) ci;
1169 if (cci->cloud && cci->cloud->mst_root == cci)
1172 if(cci->cloud && cci->cloud->mst_root)
1173 snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1176 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1177 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1180 static void ifg_dump_at_end(FILE *file, void *self)
1185 co_gs_foreach_aff_node(env->co, a) {
1186 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1187 int idx = get_irn_idx(a->irn);
1190 if(ai->mst_parent != ai)
1191 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1193 co_gs_foreach_neighb(a, n) {
1194 int nidx = get_irn_idx(n->irn);
1195 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1198 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1199 const char *arr = "arrowhead=dot arrowtail=dot";
1201 if(ci->mst_parent == ai)
1202 arr = "arrowtail=normal";
1203 else if(ai->mst_parent == ci)
1204 arr = "arrowhead=normal";
1206 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1213 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1215 ifg_dump_graph_attr,
1223 void co_solve_heuristic_new(copy_opt_t *co)
1229 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1233 env.n_regs = co->cls->n_regs;
1234 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1235 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1236 bitset_flip_all(env.ignore_regs);
1237 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1238 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1239 INIT_LIST_HEAD(&env.cloud_head);
1241 if(dump_flags & DUMP_BEFORE) {
1242 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1243 if(f = fopen(buf, "wt")) {
1244 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1251 if(dump_flags & DUMP_AFTER) {
1252 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1253 if(f = fopen(buf, "wt")) {
1254 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1259 writeback_colors(&env);
1260 phase_free(&env.ph);