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 double constr_factor = 0.5;
48 /* Options using libcore */
51 static const lc_opt_enum_mask_items_t dump_items[] = {
52 { "before", DUMP_BEFORE },
53 { "after", DUMP_AFTER },
54 { "cloud", DUMP_CLOUD },
59 static lc_opt_enum_mask_var_t dump_var = {
60 &dump_flags, dump_items
63 static const lc_opt_table_entry_t options[] = {
64 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var),
65 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes (standard: 3)", &subtree_iter),
66 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
70 void be_co2_register_options(lc_opt_entry_t *grp)
72 lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
73 lc_opt_add_table(co2_grp, options);
79 / ___|| |_ __ _ _ __| |_
80 \___ \| __/ _` | '__| __|
81 ___) | || (_| | | | |_
82 |____/ \__\__,_|_| \__|
86 #define INFEASIBLE(cost) ((cost) == INT_MAX)
88 static be_ifg_dump_dot_cb_t ifg_dot_cb;
90 typedef unsigned col_t;
92 typedef struct _co2_irn_t co2_irn_t;
93 typedef struct _co2_cloud_t co2_cloud_t;
94 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
104 bitset_t *ignore_regs;
108 struct list_head cloud_head;
109 DEBUG_ONLY(firm_dbg_module_t *dbg;)
114 affinity_node_t *aff;
115 co2_irn_t *touched_next;
118 int last_color_change;
121 unsigned tmp_fixed : 1;
122 unsigned is_constrained : 1;
123 struct list_head changed_list;
126 struct _co2_cloud_irn_t {
127 struct _co2_irn_t inh;
131 co2_cloud_irn_t *mst_parent;
134 co2_cloud_irn_t **mst_childs;
139 col_cost_pair_t *tmp_coloring;
140 struct list_head cloud_list;
141 struct list_head mst_list;
144 struct _co2_cloud_t {
156 co2_cloud_irn_t *master;
157 co2_cloud_irn_t *mst_root;
158 co2_cloud_irn_t **seq;
159 struct list_head members_head;
160 struct list_head list;
164 co2_cloud_irn_t *src, *tgt;
168 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
170 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
171 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
173 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
175 co2_t *env = (co2_t *) ph;
176 affinity_node_t *a = get_affinity_info(env->co, irn);
177 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
178 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
181 INIT_LIST_HEAD(&ci->changed_list);
182 ci->touched_next = env->touched;
183 ci->orig_col = get_irn_col(env->co, irn);
189 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
190 INIT_LIST_HEAD(&cci->cloud_list);
191 cci->mst_parent = cci;
197 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
199 static int cmp_clouds_gt(const void *a, const void *b)
201 const co2_cloud_t **p = a;
202 const co2_cloud_t **q = b;
203 double c = CLOUD_WEIGHT(*p);
204 double d = CLOUD_WEIGHT(*q);
205 return QSORT_CMP(d, c);
209 * An order on color/costs pairs.
210 * If the costs are equal, we use the color as a kind of normalization.
212 static int col_cost_pair_lt(const void *a, const void *b)
214 const col_cost_pair_t *p = a;
215 const col_cost_pair_t *q = b;
218 return QSORT_CMP(c, d);
221 int cmp_edges(const void *a, const void *b)
225 return QSORT_CMP(q->costs, p->costs);
228 static col_t get_col(co2_t *env, ir_node *irn)
230 co2_irn_t *ci = get_co2_irn(env, irn);
231 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
234 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
236 co2_irn_t *ci = get_co2_irn(env, irn);
237 return ci->fixed || ci->tmp_fixed;
240 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
243 arch_register_req_t req;
244 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
245 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
246 if(arch_register_req_is(&req, limited)) {
247 req.limited(req.limited_env, ci->adm_cache);
248 ci->is_constrained = 1;
251 bitset_copy(ci->adm_cache, env->ignore_regs);
252 bitset_flip_all(ci->adm_cache);
256 return ci->adm_cache;
259 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
261 bitset_copy(bs, get_adm(env, ci));
265 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
267 bitset_t *bs = get_adm(env, ci);
268 return bitset_is_set(bs, col);
271 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
275 return ci->is_constrained;
278 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
280 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
281 arch_register_req_t req;
283 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
285 if(arch_register_req_is(&req, limited)) {
289 req.limited(req.limited_env, aux);
290 n_constr = bitset_popcnt(aux);
291 bitset_foreach(aux, elm) {
292 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
298 * Determine costs which shall indicate how cheap/expensive it is to try
299 * to assign a node some color.
300 * The costs are computed for all colors. INT_MAX means that it is impossible
301 * to give the node that specific color.
303 * @param env The co2 this pointer.
304 * @param irn The node.
305 * @param col_costs An array of colors x costs where the costs are written to.
307 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
309 ir_node *irn = ci->irn;
310 be_ifg_t *ifg = env->co->cenv->ifg;
311 int n_regs = env->co->cls->n_regs;
312 bitset_t *forb = bitset_alloca(n_regs);
313 affinity_node_t *a = ci->aff;
320 /* Put all forbidden colors into the aux bitset. */
321 admissible_colors(env, ci, forb);
322 bitset_flip_all(forb);
324 for(i = 0; i < n_regs; ++i) {
325 col_costs[i].col = i;
326 col_costs[i].costs = 0;
332 co_gs_foreach_neighb(a, n) {
333 if(color_is_fix(env, n->irn)) {
334 col_t col = get_col(env, n->irn);
335 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
338 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
342 it = be_ifg_neighbours_iter_alloca(ifg);
343 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
344 col_t col = get_col(env, pos);
345 if(color_is_fix(env, pos)) {
346 col_costs[col].costs = INT_MAX;
349 incur_constraint_costs(env, pos, col_costs, INT_MAX);
350 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
353 be_ifg_neighbours_break(ifg, it);
355 /* Set the costs to infinity for each color which is not allowed at this node. */
356 bitset_foreach(forb, elm) {
357 col_costs[elm].costs = INT_MAX;
362 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
364 int n_regs = env->co->cls->n_regs;
367 for(i = 0; i < n_regs; ++i) {
369 seq[i].costs = INT_MAX;
372 assert(is_color_admissible(env, ci, col));
378 static void reject_coloring(struct list_head *h)
382 list_for_each_entry(co2_irn_t, pos, h, changed_list)
386 static void materialize_coloring(struct list_head *h)
390 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
391 pos->orig_col = pos->tmp_col;
396 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
398 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
400 int n_regs = env->co->cls->n_regs;
401 be_ifg_t *ifg = env->co->cenv->ifg;
402 co2_irn_t *ci = get_co2_irn(env, irn);
408 for(i = 0; i < n_regs; ++i) {
409 col_t tgt_col = col_list[i].col;
410 unsigned costs = col_list[i].costs;
413 struct list_head changed;
417 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
419 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
420 if(INFEASIBLE(costs)) {
421 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
426 /* Set the new color of the node and mark the node as temporarily fixed. */
427 ci->tmp_col = tgt_col;
431 If that color has costs > 0, there's at least one neighbor having that color,
432 so we will try to change the neighbors' colors, too.
434 INIT_LIST_HEAD(&changed);
435 list_add(&ci->changed_list, &changed);
437 it = be_ifg_neighbours_iter_alloca(ifg);
438 be_ifg_foreach_neighbour(ifg, it, irn, n) {
440 /* try to re-color the neighbor if it has the target color. */
441 if(get_col(env, n) == tgt_col) {
442 struct list_head tmp;
445 Try to change the color of the neighbor and record all nodes which
446 get changed in the tmp list. Add this list to the "changed" list for
447 that color. If we did not succeed to change the color of the neighbor,
448 we bail out and try the next color.
450 INIT_LIST_HEAD(&tmp);
451 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
452 list_splice(&tmp, &changed);
457 be_ifg_neighbours_break(ifg, it);
460 We managed to assign the target color to all neighbors, so from the perspective
461 of the current node, every thing was ok and we can return safely.
464 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
465 list_splice(&changed, parent_changed);
471 If not, that color did not succeed and we unfix all nodes we touched
472 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
475 reject_coloring(&changed);
481 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
483 co2_irn_t *ci = get_co2_irn(env, irn);
485 col_t col = get_col(env, irn);
487 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
489 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
496 list_add(&ci->changed_list, parent_changed);
500 /* The node has the color it should not have _and_ has not been visited yet. */
501 if(!color_is_fix(env, irn)) {
502 int n_regs = env->co->cls->n_regs;
503 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
505 /* Get the costs for giving the node a specific color. */
506 determine_color_costs(env, ci, csts);
508 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
509 csts[not_col].costs = INT_MAX;
511 /* sort the colors according costs, cheapest first. */
512 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
514 /* Try recoloring the node using the color list. */
515 res = recolor(env, irn, csts, parent_changed, depth);
518 /* If we came here, everything went ok. */
522 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
524 co2_irn_t *ci = get_co2_irn(env, irn);
525 col_t col = get_col(env, irn);
528 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
530 /* the node has the wanted color. That's fine, mark it as visited and return. */
535 list_add(&ci->changed_list, parent_changed);
542 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
543 int n_regs = env->co->cls->n_regs;
544 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
546 /* Get the costs for giving the node a specific color. */
547 single_color_cost(env, ci, tgt_col, seq);
549 /* Try recoloring the node using the color list. */
550 res = recolor(env, irn, seq, parent_changed, depth);
555 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
560 * Examine the costs of the current coloring concerning a MST subtree.
561 * @param ci The subtree root.
562 * @param col The color of @p ci.
563 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
565 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
567 int *front = FRONT_BASE(ci, col);
571 for(i = 0; i < ci->mst_n_childs; ++i) {
572 co2_cloud_irn_t *chld = ci->mst_childs[i];
573 col_t chld_col = front[i];
575 cost += examine_subtree_coloring(chld, chld_col);
576 cost += col != chld_col ? chld->mst_costs : 0;
583 * Determine color badnesses of a node.
584 * Badness means that it is unlikely that the node in question can
585 * obtain a color. The higher the badness, the more unlikely it is that
586 * the node can be assigned that color.
587 * @param ci The node.
588 * @param badness An integer array as long as there are registers.
589 * @note The array <code>badness</code> is not cleared.
591 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
593 co2_t *env = ci->cloud->env;
594 co2_irn_t *ir = &ci->inh;
595 int n_regs = env->n_regs;
596 be_ifg_t *ifg = env->co->cenv->ifg;
597 bitset_t *bs = bitset_alloca(n_regs);
603 admissible_colors(env, &ci->inh, bs);
605 bitset_foreach(bs, elm)
606 badness[elm] = ci->costs;
608 /* Use constrained/fixed interfering neighbors to influence the color badness */
609 it = be_ifg_neighbours_iter_alloca(ifg);
610 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
611 co2_irn_t *ni = get_co2_irn(env, irn);
613 admissible_colors(env, ni, bs);
614 if(bitset_popcnt(bs) == 1) {
615 bitset_pos_t c = bitset_next_set(bs, 0);
616 badness[c] += ci->costs;
620 col_t c = get_col(env, ni->irn);
621 badness[c] += ci->costs;
624 be_ifg_neighbours_break(ifg, it);
628 * Determine the badness of a MST subtree.
629 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
630 * @see node_color_badness() for a definition of badness.
631 * @param ci The root of the subtree.
632 * @param depth Depth for debugging purposes.
634 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
636 co2_t *env = ci->cloud->env;
639 node_color_badness(ci, ci->color_badness);
641 /* Collect the color badness for the whole subtree */
642 for(i = 0; i < ci->mst_n_childs; ++i) {
643 co2_cloud_irn_t *child = ci->mst_childs[i];
644 determine_color_badness(child, depth + 1);
646 for(j = 0; j < env->n_regs; ++j)
647 ci->color_badness[j] += child->color_badness[j];
650 for(j = 0; j < env->n_regs; ++j)
651 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
655 * Unfix all nodes in a MST subtree.
657 static void unfix_subtree(co2_cloud_irn_t *ci)
662 for(i = 0; i < ci->mst_n_childs; ++i)
663 unfix_subtree(ci->mst_childs[i]);
666 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
668 co2_t *env = ci->cloud->env;
669 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
670 int is_root = ci->mst_parent == ci;
671 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
672 int min_badness = INT_MAX;
673 int best_col_costs = INT_MAX;
675 int n_regs = env->n_regs;
676 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
678 struct list_head changed;
681 for(i = 0; i < n_regs; ++i) {
682 int badness = ci->color_badness[i];
685 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
687 min_badness = MIN(min_badness, badness);
690 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
691 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
692 seq[parent_col].costs = min_badness - 1;
694 /* Sort the colors. The will be processed in that ordering. */
695 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
697 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
698 INIT_LIST_HEAD(&changed);
699 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
700 col_t col = seq[i].col;
701 int costs = seq[i].costs;
702 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
704 int subtree_costs, sum_costs;
706 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
709 INIT_LIST_HEAD(&changed);
710 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
712 materialize_coloring(&changed);
719 for(j = 0; j < ci->mst_n_childs; ++j) {
720 co2_cloud_irn_t *child = ci->mst_childs[j];
721 ok = coalesce_top_down(child, j, depth + 1) >= 0;
723 child->inh.fixed = 1;
728 /* If the subtree could not be colored, we have to try another color. */
732 subtree_costs = examine_subtree_coloring(ci, col);
733 sum_costs = subtree_costs + add_cost;
734 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
736 if(sum_costs < best_col_costs) {
738 best_col_costs = sum_costs;
739 ci->col_costs[col] = subtree_costs;
747 int *front = FRONT_BASE(ci->mst_parent, parent_col);
748 front[child_nr] = best_col;
754 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
756 be_ifg_t *ifg = env->co->cenv->ifg;
757 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
764 /* mark the node as visited and add it to the cloud. */
766 list_add(&ci->cloud_list, &cloud->members_head);
768 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
770 /* determine the nodes costs */
771 co_gs_foreach_neighb(a, n) {
773 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
774 if(be_ifg_connected(ifg, a->irn, n->irn))
775 cloud->inevit += n->costs;
778 /* add the node's cost to the total costs of the cloud. */
780 cloud->costs += costs;
781 cloud->n_constr += is_constrained(env, &ci->inh);
782 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
783 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
786 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
787 if(costs >= curr_costs) {
792 /* add all the neighbors of the node to the cloud. */
793 co_gs_foreach_neighb(a, n) {
794 affinity_node_t *an = get_affinity_info(env->co, n->irn);
796 populate_cloud(env, cloud, an, curr_costs);
800 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
802 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
806 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
807 memset(cloud, 0, sizeof(cloud[0]));
808 INIT_LIST_HEAD(&cloud->members_head);
809 INIT_LIST_HEAD(&cloud->list);
810 list_add(&cloud->list, &env->cloud_head);
811 cloud->best_costs = INT_MAX;
814 populate_cloud(env, cloud, a, 0);
815 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
817 /* Also allocate space for the node sequence and compute that sequence. */
818 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
821 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
823 cloud->seq[i++] = ci;
825 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
830 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
832 ir_node *irn = ci->inh.irn;
833 int *front = FRONT_BASE(ci, col);
835 struct list_head changed;
837 INIT_LIST_HEAD(&changed);
839 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
840 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
841 assert(ok && "Color changing may not fail while committing the coloring");
842 materialize_coloring(&changed);
844 for(i = 0; i < ci->mst_n_childs; ++i) {
845 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
849 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
851 while(ci != ci->mst_parent)
857 static void process_cloud(co2_cloud_t *cloud)
859 co2_t *env = cloud->env;
860 int n_regs = env->n_regs;
862 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
865 struct list_head changed;
870 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
872 /* Collect all edges in the cloud on an obstack and sort the increasingly */
873 obstack_init(&cloud->obst);
874 for(i = 0; i < cloud->n_memb; ++i) {
875 co2_cloud_irn_t *ci = cloud->seq[i];
878 co_gs_foreach_neighb(ci->inh.aff, n) {
879 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
880 if(ci->index < ni->index) {
885 obstack_grow(&cloud->obst, &e, sizeof(e));
890 edges = obstack_finish(&cloud->obst);
891 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
893 /* Compute the maximum spanning tree using Kruskal/Union-Find */
894 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
895 for(i = 0; i < n_edges; ++i) {
896 edge_t *e = &edges[i];
897 co2_cloud_irn_t *rs = find_mst_root(e->src);
898 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
900 /* if the union/find roots are different */
902 int si = e->src->index;
903 int ti = e->tgt->index;
907 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
909 /* this edge is in the MST, so set it in the bitset. */
910 mst_edges[si * cloud->n_memb + ti] = e->costs;
911 mst_edges[ti * cloud->n_memb + si] = e->costs;
914 obstack_free(&cloud->obst, edges);
916 cloud->master->mst_parent = cloud->master;
917 cloud->mst_root = cloud->master;
918 q = new_pdeq1(cloud->master);
919 while(!pdeq_empty(q)) {
920 co2_cloud_irn_t *ci = pdeq_getl(q);
921 int ofs = ci->index * cloud->n_memb;
922 int end = ofs + cloud->n_memb;
925 ci->mst_n_childs = 0;
926 for(i = ofs; i < end; ++i) {
927 if(mst_edges[i] != 0) {
929 co2_cloud_irn_t *child = cloud->seq[i - ofs];
931 /* put the child to the worklist */
934 /* make ci the parent of the child and add the child to the children array of the parent */
935 child->mst_parent = ci;
936 child->mst_costs = mst_edges[i];
938 obstack_ptr_grow(&cloud->obst, child);
940 mst_edges[other * cloud->n_memb + ci->index] = 0;
945 obstack_ptr_grow(&cloud->obst, NULL);
946 ci->mst_childs = obstack_finish(&cloud->obst);
952 DBG((env->dbg, LEVEL_3, "mst:\n"));
953 for(i = 0; i < cloud->n_memb; ++i) {
954 co2_cloud_irn_t *ci = cloud->seq[i];
955 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
958 for(i = 0; i < cloud->n_memb; ++i) {
959 co2_cloud_irn_t *ci = cloud->seq[i];
960 int n_childs = ci->mst_n_childs;
963 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
964 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
965 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
966 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
967 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
968 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
969 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
970 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
972 for(j = 0; j < env->n_regs; j++)
973 ci->col_costs[j] = INT_MAX;
977 determine_color_badness(cloud->mst_root, 0);
978 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
979 unfix_subtree(cloud->mst_root);
980 apply_coloring(cloud->mst_root, best_col, 0);
982 /* The coloring should represent the one with the best costs. */
983 //materialize_coloring(&changed);
984 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
985 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
987 /* Fix all nodes in the cloud. */
988 for(i = 0; i < cloud->n_memb; ++i)
989 cloud->seq[i]->inh.fixed = 1;
991 /* Free all space used while optimizing this cloud. */
992 obstack_free(&cloud->obst, NULL);
995 static int cloud_costs(co2_cloud_t *cloud)
1000 for(i = 0; i < cloud->n_memb; ++i) {
1001 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1002 col_t col = get_col(cloud->env, ci->irn);
1003 co_gs_foreach_neighb(ci->aff, n) {
1004 col_t n_col = get_col(cloud->env, n->irn);
1005 costs += col != n_col ? n->costs : 0;
1012 static void process(co2_t *env)
1016 co2_cloud_t **clouds;
1021 int final_costs = 0;
1024 co_gs_foreach_aff_node(env->co, a) {
1025 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1028 co2_cloud_t *cloud = new_cloud(env, a);
1034 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1035 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1037 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1039 for(i = 0; i < n_clouds; ++i) {
1040 init_costs += cloud_costs(clouds[i]);
1042 /* Process the cloud. */
1043 process_cloud(clouds[i]);
1045 all_costs += clouds[i]->costs;
1046 final_costs += cloud_costs(clouds[i]);
1048 /* Dump the IFG if the user demanded it. */
1049 if (dump_flags & DUMP_CLOUD) {
1053 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1054 if(f = fopen(buf, "wt")) {
1055 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1061 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1066 static void writeback_colors(co2_t *env)
1068 const arch_env_t *aenv = env->co->aenv;
1071 for(irn = env->touched; irn; irn = irn->touched_next) {
1072 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1073 arch_set_irn_register(aenv, irn->irn, reg);
1079 ___ _____ ____ ____ ___ _____ ____ _
1080 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1081 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1082 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1083 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1087 static const char *get_dot_color_name(int col)
1089 static const char *names[] = {
1123 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1126 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1128 arch_register_req_t req;
1130 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1131 if(arch_register_req_is(&req, limited))
1143 static void ifg_dump_graph_attr(FILE *f, void *self)
1145 fprintf(f, "overlay=false");
1148 static int ifg_is_dump_node(void *self, ir_node *irn)
1151 return !arch_irn_is(env->co->aenv, irn, ignore);
1154 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1157 co2_irn_t *ci = get_co2_irn(env, irn);
1163 co2_cloud_irn_t *cci = (void *) ci;
1164 if (cci->cloud && cci->cloud->mst_root == cci)
1167 if(cci->cloud && cci->cloud->mst_root)
1168 snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1171 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1172 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1175 static void ifg_dump_at_end(FILE *file, void *self)
1180 co_gs_foreach_aff_node(env->co, a) {
1181 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1182 int idx = get_irn_idx(a->irn);
1185 if(ai->mst_parent != ai)
1186 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1188 co_gs_foreach_neighb(a, n) {
1189 int nidx = get_irn_idx(n->irn);
1190 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1193 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1194 const char *arr = "arrowhead=dot arrowtail=dot";
1196 if(ci->mst_parent == ai)
1197 arr = "arrowtail=normal";
1198 else if(ai->mst_parent == ci)
1199 arr = "arrowhead=normal";
1201 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1208 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1210 ifg_dump_graph_attr,
1218 void co_solve_heuristic_new(copy_opt_t *co)
1224 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1228 env.n_regs = co->cls->n_regs;
1229 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1230 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1231 bitset_flip_all(env.ignore_regs);
1232 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1233 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1234 INIT_LIST_HEAD(&env.cloud_head);
1236 if(dump_flags & DUMP_BEFORE) {
1237 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1238 if(f = fopen(buf, "wt")) {
1239 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1246 if(dump_flags & DUMP_AFTER) {
1247 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1248 if(f = fopen(buf, "wt")) {
1249 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1254 writeback_colors(&env);
1255 phase_free(&env.ph);