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 double stop_percentage = 1.0;
46 static int subtree_iter = 4;
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 ("stop", "stop optimizing cloud at given percentage of total cloud costs", &stop_percentage),
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 {
154 co2_cloud_irn_t *master;
155 co2_cloud_irn_t *mst_root;
156 co2_cloud_irn_t **seq;
157 struct list_head members_head;
158 struct list_head list;
161 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
163 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
164 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
166 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
168 co2_t *env = (co2_t *) ph;
169 affinity_node_t *a = get_affinity_info(env->co, irn);
170 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
171 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
174 INIT_LIST_HEAD(&ci->changed_list);
175 ci->touched_next = env->touched;
176 ci->orig_col = get_irn_col(env->co, irn);
182 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
183 INIT_LIST_HEAD(&cci->cloud_list);
184 cci->mst_parent = cci;
191 static int cmp_clouds_gt(const void *a, const void *b)
193 const co2_cloud_t **p = a;
194 const co2_cloud_t **q = b;
197 return QSORT_CMP(d, c);
201 * An order on color/costs pairs.
202 * If the costs are equal, we use the color as a kind of normalization.
204 static int col_cost_pair_lt(const void *a, const void *b)
206 const col_cost_pair_t *p = a;
207 const col_cost_pair_t *q = b;
210 return QSORT_CMP(c, d);
213 static col_t get_col(co2_t *env, ir_node *irn)
215 co2_irn_t *ci = get_co2_irn(env, irn);
216 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
219 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
221 co2_irn_t *ci = get_co2_irn(env, irn);
222 return ci->fixed || ci->tmp_fixed;
225 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
228 arch_register_req_t req;
229 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
230 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
231 if(arch_register_req_is(&req, limited)) {
232 req.limited(req.limited_env, ci->adm_cache);
233 ci->is_constrained = 1;
236 bitset_copy(ci->adm_cache, env->ignore_regs);
237 bitset_flip_all(ci->adm_cache);
241 return ci->adm_cache;
244 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
246 bitset_copy(bs, get_adm(env, ci));
250 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
252 bitset_t *bs = get_adm(env, ci);
253 return bitset_is_set(bs, col);
256 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
260 return ci->is_constrained;
263 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
265 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
266 arch_register_req_t req;
268 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
270 if(arch_register_req_is(&req, limited)) {
274 req.limited(req.limited_env, aux);
275 n_constr = bitset_popcnt(aux);
276 bitset_foreach(aux, elm) {
277 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
283 * Determine costs which shall indicate how cheap/expensive it is to try
284 * to assign a node some color.
285 * The costs are computed for all colors. INT_MAX means that it is impossible
286 * to give the node that specific color.
288 * @param env The co2 this pointer.
289 * @param irn The node.
290 * @param col_costs An array of colors x costs where the costs are written to.
292 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
294 ir_node *irn = ci->irn;
295 be_ifg_t *ifg = env->co->cenv->ifg;
296 int n_regs = env->co->cls->n_regs;
297 bitset_t *forb = bitset_alloca(n_regs);
298 affinity_node_t *a = ci->aff;
305 /* Put all forbidden colors into the aux bitset. */
306 admissible_colors(env, ci, forb);
307 bitset_flip_all(forb);
309 for(i = 0; i < n_regs; ++i) {
310 col_costs[i].col = i;
311 col_costs[i].costs = 0;
317 co_gs_foreach_neighb(a, n) {
318 if(color_is_fix(env, n->irn)) {
319 col_t col = get_col(env, n->irn);
320 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
323 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
327 it = be_ifg_neighbours_iter_alloca(ifg);
328 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
329 col_t col = get_col(env, pos);
330 if(color_is_fix(env, pos)) {
331 col_costs[col].costs = INT_MAX;
334 incur_constraint_costs(env, pos, col_costs, INT_MAX);
335 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
338 be_ifg_neighbours_break(ifg, it);
340 /* Set the costs to infinity for each color which is not allowed at this node. */
341 bitset_foreach(forb, elm) {
342 col_costs[elm].costs = INT_MAX;
347 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
349 int n_regs = env->co->cls->n_regs;
352 for(i = 0; i < n_regs; ++i) {
354 seq[i].costs = INT_MAX;
357 assert(is_color_admissible(env, ci, col));
363 static void reject_coloring(struct list_head *h)
367 list_for_each_entry(co2_irn_t, pos, h, changed_list)
371 static void materialize_coloring(struct list_head *h)
375 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
376 pos->orig_col = pos->tmp_col;
386 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
391 list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
393 ent.col = pos->tmp_col;
395 obstack_grow(obst, &ent, sizeof(ent));
397 memset(&ent, 0, sizeof(ent));
398 obstack_grow(obst, &ent, sizeof(ent));
399 return obstack_finish(obst);
402 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
403 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
405 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
407 int n_regs = env->co->cls->n_regs;
408 be_ifg_t *ifg = env->co->cenv->ifg;
409 co2_irn_t *ci = get_co2_irn(env, irn);
415 for(i = 0; i < n_regs; ++i) {
416 col_t tgt_col = col_list[i].col;
417 unsigned costs = col_list[i].costs;
420 struct list_head changed;
424 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
426 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
427 if(INFEASIBLE(costs)) {
428 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
433 /* Set the new color of the node and mark the node as temporarily fixed. */
434 ci->tmp_col = tgt_col;
438 If that color has costs > 0, there's at least one neighbor having that color,
439 so we will try to change the neighbors' colors, too.
441 INIT_LIST_HEAD(&changed);
442 list_add(&ci->changed_list, &changed);
444 it = be_ifg_neighbours_iter_alloca(ifg);
445 be_ifg_foreach_neighbour(ifg, it, irn, n) {
447 /* try to re-color the neighbor if it has the target color. */
448 if(get_col(env, n) == tgt_col) {
449 struct list_head tmp;
452 Try to change the color of the neighbor and record all nodes which
453 get changed in the tmp list. Add this list to the "changed" list for
454 that color. If we did not succeed to change the color of the neighbor,
455 we bail out and try the next color.
457 INIT_LIST_HEAD(&tmp);
458 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
459 list_splice(&tmp, &changed);
464 be_ifg_neighbours_break(ifg, it);
467 We managed to assign the target color to all neighbors, so from the perspective
468 of the current node, every thing was ok and we can return safely.
471 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
472 list_splice(&changed, parent_changed);
478 If not, that color did not succeed and we unfix all nodes we touched
479 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
482 reject_coloring(&changed);
488 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
490 co2_irn_t *ci = get_co2_irn(env, irn);
492 col_t col = get_col(env, irn);
494 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
496 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
503 list_add(&ci->changed_list, parent_changed);
507 /* The node has the color it should not have _and_ has not been visited yet. */
508 if(!color_is_fix(env, irn)) {
509 int n_regs = env->co->cls->n_regs;
510 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
512 /* Get the costs for giving the node a specific color. */
513 determine_color_costs(env, ci, csts);
515 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
516 csts[not_col].costs = INT_MAX;
518 /* sort the colors according costs, cheapest first. */
519 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
521 /* Try recoloring the node using the color list. */
522 res = recolor(env, irn, csts, parent_changed, depth);
525 /* If we came here, everything went ok. */
529 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
531 co2_irn_t *ci = get_co2_irn(env, irn);
532 col_t col = get_col(env, irn);
535 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
537 /* the node has the wanted color. That's fine, mark it as visited and return. */
542 list_add(&ci->changed_list, parent_changed);
549 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
550 int n_regs = env->co->cls->n_regs;
551 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
553 /* Get the costs for giving the node a specific color. */
554 single_color_cost(env, ci, tgt_col, seq);
556 /* Try recoloring the node using the color list. */
557 res = recolor(env, irn, seq, parent_changed, depth);
562 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
566 static void front_inval_color(co2_cloud_irn_t *ci, col_t col)
568 int *base = FRONT_BASE(ci, col);
569 memset(base, -1, ci->mst_n_childs * sizeof(base[0]));
573 co2_cloud_irn_t *src, *tgt;
577 int cmp_edges(const void *a, const void *b)
581 return QSORT_CMP(q->costs, p->costs);
584 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
586 while(ci != ci->mst_parent)
592 static int cmp_parent(const void *a, const void *b)
594 const co2_cloud_irn_t *p = a;
595 const co2_cloud_irn_t *q = b;
596 return QSORT_CMP(q->mst_costs, p->mst_costs);
599 static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col)
601 int n_regs = ci->cloud->env->n_regs;
604 for(i = 0; i < ci->mst_n_childs; ++i) {
605 co2_cloud_irn_t *c = ci->mst_childs[i];
606 for(j = 0; j < n_regs; ++j) {
607 int costs = c->col_costs[j];
608 if(INFEASIBLE(costs))
609 c->tmp_coloring[j].costs = INT_MAX;
611 int add = j != (int) col ? c->mst_costs : 0;
612 c->tmp_coloring[j].costs = add + costs;
614 c->tmp_coloring[j].col = j;
616 qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt);
620 static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq)
622 int n_regs = ci->cloud->env->n_regs;
623 bitset_t *adm = bitset_alloca(n_regs);
626 // TODO: Prefer some colors depending on the neighbors, etc.
628 admissible_colors(ci->cloud->env, &ci->inh, adm);
629 for(i = 0; i < n_regs; ++i) {
632 if (!bitset_is_set(adm, i))
633 seq[i].costs = INT_MAX;
636 for(j = 0; j < ci->mst_n_childs; ++j) {
637 co2_cloud_irn_t *child = ci->mst_childs[j];
638 if (!INFEASIBLE(child->col_costs[i]))
639 seq[i].costs -= ci->mst_childs[j]->col_costs[i];
644 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
647 static int push_front(co2_cloud_irn_t *ci, int *front)
649 co2_t *env = ci->cloud->env;
650 int n_regs = env->n_regs;
651 int min_diff = INT_MAX;
655 for(i = 0; i < ci->mst_n_childs; ++i) {
656 co2_cloud_irn_t *child = ci->mst_childs[i];
660 if(idx + 1 < n_regs) {
661 int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs;
662 if(diff < min_diff) {
670 co2_cloud_irn_t *child = ci->mst_childs[min_chld];
671 DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff));
672 front[min_chld] += 1;
678 static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
680 int n_childs = ci->mst_n_childs;
682 select the front for the given color.
683 The front will determine the colors of the children.
685 int *front = FRONT_BASE(ci, col);
688 ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0);
689 for(i = 0; i < n_childs && ok; ++i) {
690 co2_cloud_irn_t *child = ci->mst_childs[i];
691 col_t col = front[i];
693 ok = color_subtree(child, col, changed, depth + 1);
699 static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth)
701 co2_t *env = ci->cloud->env;
702 struct list_head changed;
705 INIT_LIST_HEAD(&changed);
706 *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1);
708 for (i = 0; i < ci->mst_n_childs && ok; ++i) {
709 co2_cloud_irn_t *child = ci->mst_childs[i];
710 col_t tgt_col = child->tmp_coloring[front[i]].col;
712 ok = color_subtree(child, tgt_col, &changed, depth + 1);
715 reject_coloring(&changed);
720 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
722 int *front = FRONT_BASE(ci, col);
726 for(i = 0; i < ci->mst_n_childs; ++i) {
727 co2_cloud_irn_t *chld = ci->mst_childs[i];
728 col_t chld_col = front[i];
730 cost += examine_subtree_coloring(chld, chld_col);
731 cost += col != chld_col ? chld->mst_costs : 0;
737 static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth)
739 co2_t *env = ci->cloud->env;
740 int n_regs = env->n_regs;
741 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
742 int *front = alloca(ci->mst_n_childs * sizeof(front[0]));
744 int best_cost = INT_MAX;
749 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn));
751 for (i = 0; i < ci->mst_n_childs; ++i)
752 cloud_mst_build_colorings(ci->mst_childs[i], depth + 1);
754 for (i = 0; i < n_regs; ++i)
755 ci->col_costs[i] = INT_MAX;
757 /* Sort the children according to the cost of the affinity edge they have to the current node. */
758 // qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent);
760 determine_start_colors(ci, seq);
761 // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
763 for(i = 0; i < n_regs; ++i) {
764 col_t col = seq[i].col;
765 int costs = seq[i].costs;
768 if(INFEASIBLE(costs))
772 Judge, if it is worthwhile trying this color.
773 If another color was so good that we cannot get any better, bail out here.
777 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
779 /* This sorts the tmp_coloring array in the children according to the costs of the current color. */
780 fill_tmp_coloring(ci, col);
782 /* Initialize the front. It gives the indexes into the color tmp_coloring array. */
783 memset(front, 0, ci->mst_n_childs * sizeof(front));
786 As long as we have color configurations to try.
787 We try the best ones first and get worse over and over.
792 if (try_coloring(ci, col, front, &try_push, depth + 1)) {
793 int *res_front = FRONT_BASE(ci, col);
796 for(j = 0; j < ci->mst_n_childs; ++j) {
797 co2_cloud_irn_t *child = ci->mst_childs[j];
798 col_t col = child->tmp_coloring[front[j]].col;
802 costs = examine_subtree_coloring(ci, col);
803 ci->col_costs[col] = costs;
806 /* Set the current best color. */
807 if(costs < best_cost) {
813 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed"));
815 /* Worsen the configuration, if that one didn't succeed. */
817 done = try_push ? push_front(ci, front) < 0 : 1;
821 DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn));
822 for(i = 0; i < n_regs; ++i)
823 DBG((env->dbg, LEVEL_2, "%2{firm:indent} color %d costs %d\n", depth, i, ci->col_costs[i]));
828 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
830 co2_t *env = ci->cloud->env;
831 co2_irn_t *ir = &ci->inh;
832 int n_regs = env->n_regs;
833 be_ifg_t *ifg = env->co->cenv->ifg;
834 bitset_t *bs = bitset_alloca(n_regs);
840 admissible_colors(env, &ci->inh, bs);
842 bitset_foreach(bs, elm)
843 badness[elm] = ci->costs;
845 /* Use constrained/fixed interfering neighbors to influence the color badness */
846 it = be_ifg_neighbours_iter_alloca(ifg);
847 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
848 co2_irn_t *ni = get_co2_irn(env, irn);
850 admissible_colors(env, ni, bs);
851 if(bitset_popcnt(bs) == 1) {
852 bitset_pos_t c = bitset_next_set(bs, 0);
853 badness[c] += ci->costs;
857 col_t c = get_col(env, ni->irn);
858 badness[c] += ci->costs;
861 be_ifg_neighbours_break(ifg, it);
865 static int cloud_color_badness(co2_cloud_t *cloud)
867 int *badness = alloca(cloud->env->n_regs * sizeof(badness[0]));
870 memset(badness, 0, cloud->env->n_regs * sizeof(badness[0]));
871 for(i = 0; i < cloud->n_memb; ++i)
872 node_color_badness(cloud->seq[i], badness);
875 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
877 co2_t *env = ci->cloud->env;
880 node_color_badness(ci, ci->color_badness);
882 /* Collect the color badness for the whole subtree */
883 for(i = 0; i < ci->mst_n_childs; ++i) {
884 co2_cloud_irn_t *child = ci->mst_childs[i];
885 determine_color_badness(child, depth + 1);
887 for(j = 0; j < env->n_regs; ++j)
888 ci->color_badness[j] += child->color_badness[j];
891 for(j = 0; j < env->n_regs; ++j)
892 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
895 static void unfix_subtree(co2_cloud_irn_t *ci)
900 for(i = 0; i < ci->mst_n_childs; ++i)
901 unfix_subtree(ci->mst_childs[i]);
904 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
906 co2_t *env = ci->cloud->env;
907 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
908 int is_root = ci->mst_parent == ci;
909 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
910 int min_badness = INT_MAX;
911 int best_col_costs = INT_MAX;
913 int n_regs = env->n_regs;
914 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
916 struct list_head changed;
919 for(i = 0; i < n_regs; ++i) {
920 int badness = ci->color_badness[i];
923 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? ci->color_badness[i] : INT_MAX;
925 min_badness = MIN(min_badness, badness);
928 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
929 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
930 seq[parent_col].costs = min_badness - 1;
932 /* Sort the colors. The will be processed in that ordering. */
933 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
935 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
936 INIT_LIST_HEAD(&changed);
937 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
938 col_t col = seq[i].col;
939 int costs = seq[i].costs;
940 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
942 int subtree_costs, sum_costs;
944 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
947 INIT_LIST_HEAD(&changed);
948 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
950 materialize_coloring(&changed);
957 for(j = 0; j < ci->mst_n_childs; ++j) {
958 co2_cloud_irn_t *child = ci->mst_childs[j];
959 ok = coalesce_top_down(child, j, depth + 1) >= 0;
961 child->inh.fixed = 1;
966 /* If the subtree could not be colored, we have to try another color. */
970 subtree_costs = examine_subtree_coloring(ci, col);
971 sum_costs = subtree_costs + add_cost;
972 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
974 if(sum_costs < best_col_costs) {
976 best_col_costs = sum_costs;
977 ci->col_costs[col] = subtree_costs;
983 /* If we are at the root and we achieved an acceptable amount of optimization, we finish. */
985 if(is_root && (ci->cloud->inevit * stop_percentage < ci->cloud->inevit - sum_costs)) {
986 assert(best_col != -1);
993 int *front = FRONT_BASE(ci->mst_parent, parent_col);
994 front[child_nr] = best_col;
998 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}applying best color %d for %+F\n", depth, best_col, ci->inh.irn));
999 //change_color_single(env, ci->inh.irn, best_col, parent_changed, depth);
1000 // apply_coloring(ci, best_col, parent_changed, depth);
1006 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
1008 be_ifg_t *ifg = env->co->cenv->ifg;
1009 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1013 if(ci->visited >= env->visited)
1016 /* mark the node as visited and add it to the cloud. */
1017 ci->visited = env->visited;
1019 list_add(&ci->cloud_list, &cloud->members_head);
1021 DB((env->dbg, LEVEL_3, "\t%+F\n", ci->inh.irn));
1023 /* determine the nodes costs */
1024 co_gs_foreach_neighb(a, n) {
1026 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
1027 if(be_ifg_connected(ifg, a->irn, n->irn))
1028 cloud->inevit += n->costs;
1031 /* add the node's cost to the total costs of the cloud. */
1033 cloud->costs += costs;
1034 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
1037 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
1038 if(costs >= curr_costs) {
1043 /* add all the neighbors of the node to the cloud. */
1044 co_gs_foreach_neighb(a, n) {
1045 affinity_node_t *an = get_affinity_info(env->co, n->irn);
1047 populate_cloud(env, cloud, an, curr_costs);
1051 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
1053 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
1054 co2_cloud_irn_t *ci;
1057 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
1058 memset(cloud, 0, sizeof(cloud[0]));
1059 INIT_LIST_HEAD(&cloud->members_head);
1060 INIT_LIST_HEAD(&cloud->list);
1061 list_add(&cloud->list, &env->cloud_head);
1062 cloud->best_costs = INT_MAX;
1065 populate_cloud(env, cloud, a, 0);
1067 /* Allocate space for the best colors array, where the best coloring is saved. */
1068 // cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
1070 /* Also allocate space for the node sequence and compute that sequence. */
1071 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
1074 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
1076 cloud->seq[i++] = ci;
1078 DBG((env->dbg, LEVEL_2, "cloud cost %d\n", cloud->costs));
1083 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
1085 ir_node *irn = ci->inh.irn;
1086 int *front = FRONT_BASE(ci, col);
1088 struct list_head changed;
1090 INIT_LIST_HEAD(&changed);
1092 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
1093 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
1094 assert(ok && "Color changing may not fail while committing the coloring");
1095 materialize_coloring(&changed);
1097 for(i = 0; i < ci->mst_n_childs; ++i) {
1098 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
1102 static void process_cloud(co2_cloud_t *cloud)
1104 co2_t *env = cloud->env;
1107 struct list_head changed;
1112 /* Collect all edges in the cloud on an obstack and sort the increasingly */
1113 obstack_init(&cloud->obst);
1114 for(i = 0; i < cloud->n_memb; ++i) {
1115 co2_cloud_irn_t *ci = cloud->seq[i];
1118 co_gs_foreach_neighb(ci->inh.aff, n) {
1119 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
1120 if(ci->index < ni->index) {
1125 obstack_grow(&cloud->obst, &e, sizeof(e));
1130 edges = obstack_finish(&cloud->obst);
1131 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
1133 /* Compute the maximum spanning tree using Kruskal/Union-Find */
1134 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
1135 for(i = 0; i < n_edges; ++i) {
1136 edge_t *e = &edges[i];
1137 co2_cloud_irn_t *src = e->src;
1138 co2_cloud_irn_t *tgt = e->tgt;
1140 /* If both nodes are not in the same subtree, they can be unified. */
1141 if(find_mst_root(src) != find_mst_root(tgt)) {
1144 Bring the more costly nodes near to the root of the MST.
1145 Thus, tgt shall always be the more expensive node.
1147 if(src->costs > tgt->costs) {
1153 tgt->mst_n_childs++;
1154 src->mst_parent = tgt;
1155 src->mst_costs = e->costs;
1157 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", src->inh.irn, tgt->inh.irn, e->costs));
1160 obstack_free(&cloud->obst, edges);
1162 for(i = 0; i < cloud->n_memb; ++i) {
1163 co2_cloud_irn_t *ci = cloud->seq[i];
1166 ci->mst_childs = obstack_alloc(&cloud->obst, ci->mst_n_childs * sizeof(ci->mst_childs));
1167 ci->col_costs = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->col_costs[0]));
1168 ci->tmp_coloring = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->tmp_coloring[0]));
1169 ci->fronts = obstack_alloc(&cloud->obst, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1170 ci->color_badness = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->fronts[0]));
1171 memset(ci->color_badness, 0, env->n_regs * sizeof(ci->color_badness[0]));
1172 memset(ci->col_costs, 0, env->n_regs * sizeof(ci->col_costs[0]));
1173 memset(ci->tmp_coloring, 0, env->n_regs * sizeof(ci->tmp_coloring[0]));
1174 memset(ci->fronts, 0, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1176 for(j = 0; j < env->n_regs; j++)
1177 ci->col_costs[j] = INT_MAX;
1179 ci->mst_n_childs = 0;
1182 /* build the child arrays in the nodes */
1183 for(i = 0; i < cloud->n_memb; ++i) {
1184 co2_cloud_irn_t *ci = cloud->seq[i];
1185 if(ci->mst_parent != ci)
1186 ci->mst_parent->mst_childs[ci->mst_parent->mst_n_childs++] = ci;
1188 cloud->mst_root = ci;
1189 cloud->mst_costs = 0;
1193 /* Compute the "best" colorings. */
1194 // best_col = cloud_mst_build_colorings(cloud->mst_root, 0);
1196 determine_color_badness(cloud->mst_root, 0);
1197 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1198 unfix_subtree(cloud->mst_root);
1199 apply_coloring(cloud->mst_root, best_col, 0);
1201 /* The coloring should represent the one with the best costs. */
1202 //materialize_coloring(&changed);
1203 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1204 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1206 /* Fix all nodes in the cloud. */
1207 for(i = 0; i < cloud->n_memb; ++i)
1208 cloud->seq[i]->inh.fixed = 1;
1210 /* Free all space used while optimizing this cloud. */
1211 obstack_free(&cloud->obst, NULL);
1214 static int cloud_costs(co2_cloud_t *cloud)
1219 for(i = 0; i < cloud->n_memb; ++i) {
1220 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1221 col_t col = get_col(cloud->env, ci->irn);
1222 co_gs_foreach_neighb(ci->aff, n) {
1223 col_t n_col = get_col(cloud->env, n->irn);
1224 costs += col != n_col ? n->costs : 0;
1231 static void process(co2_t *env)
1235 co2_cloud_t **clouds;
1240 int final_costs = 0;
1243 co_gs_foreach_aff_node(env->co, a) {
1244 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1247 co2_cloud_t *cloud = new_cloud(env, a);
1253 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1254 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1256 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1258 for(i = 0; i < n_clouds; ++i) {
1259 init_costs += cloud_costs(clouds[i]);
1260 process_cloud(clouds[i]);
1261 all_costs += clouds[i]->costs;
1262 final_costs += cloud_costs(clouds[i]);
1264 /* Dump the IFG if the user demanded it. */
1265 if (dump_flags & DUMP_CLOUD) {
1269 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1270 if(f = fopen(buf, "wt")) {
1271 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1277 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1282 static void writeback_colors(co2_t *env)
1284 const arch_env_t *aenv = env->co->aenv;
1287 for(irn = env->touched; irn; irn = irn->touched_next) {
1288 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1289 arch_set_irn_register(aenv, irn->irn, reg);
1295 ___ _____ ____ ____ ___ _____ ____ _
1296 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1297 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1298 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1299 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1303 static const char *get_dot_color_name(int col)
1305 static const char *names[] = {
1339 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1342 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1344 arch_register_req_t req;
1346 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1347 if(arch_register_req_is(&req, limited))
1359 static void ifg_dump_graph_attr(FILE *f, void *self)
1361 fprintf(f, "overlay=false");
1364 static int ifg_is_dump_node(void *self, ir_node *irn)
1367 return !arch_irn_is(env->co->aenv, irn, ignore);
1370 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1373 co2_irn_t *ci = get_co2_irn(env, irn);
1379 co2_cloud_irn_t *cci = (void *) ci;
1380 if (cci->cloud && cci->cloud->mst_root == cci)
1383 if(cci->cloud && cci->cloud->mst_root)
1384 snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1387 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1388 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1391 static void ifg_dump_at_end(FILE *file, void *self)
1396 co_gs_foreach_aff_node(env->co, a) {
1397 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1398 int idx = get_irn_idx(a->irn);
1401 co_gs_foreach_neighb(a, n) {
1402 int nidx = get_irn_idx(n->irn);
1403 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1406 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1407 const char *arr = "arrowhead=dot arrowtail=dot";
1409 if(ci->mst_parent == ai)
1410 arr = "arrowtail=normal";
1411 else if(ai->mst_parent == ci)
1412 arr = "arrowhead=normal";
1414 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1421 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1423 ifg_dump_graph_attr,
1431 void co_solve_heuristic_new(copy_opt_t *co)
1437 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1441 env.n_regs = co->cls->n_regs;
1442 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1443 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1444 bitset_flip_all(env.ignore_regs);
1445 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1446 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1447 INIT_LIST_HEAD(&env.cloud_head);
1449 if(dump_flags & DUMP_BEFORE) {
1450 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1451 if(f = fopen(buf, "rt")) {
1452 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1459 if(dump_flags & DUMP_AFTER) {
1460 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1461 if(f = fopen(buf, "rt")) {
1462 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1467 writeback_colors(&env);
1468 phase_free(&env.ph);