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;
47 /* Options using libcore */
50 static const lc_opt_enum_mask_items_t dump_items[] = {
51 { "before", DUMP_BEFORE },
52 { "after", DUMP_AFTER },
53 { "cloud", DUMP_CLOUD },
58 static lc_opt_enum_mask_var_t dump_var = {
59 &dump_flags, dump_items
62 static const lc_opt_table_entry_t options[] = {
63 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var),
64 LC_OPT_ENT_DBL ("stop", "stop optimizing cloud at given percentage of total cloud costs", &stop_percentage),
68 void be_co2_register_options(lc_opt_entry_t *grp)
70 lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
71 lc_opt_add_table(co2_grp, options);
77 / ___|| |_ __ _ _ __| |_
78 \___ \| __/ _` | '__| __|
79 ___) | || (_| | | | |_
80 |____/ \__\__,_|_| \__|
84 #define INFEASIBLE(cost) ((cost) == INT_MAX)
86 static be_ifg_dump_dot_cb_t ifg_dot_cb;
88 typedef unsigned col_t;
90 typedef struct _co2_irn_t co2_irn_t;
91 typedef struct _co2_cloud_t co2_cloud_t;
92 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
102 bitset_t *ignore_regs;
106 struct list_head cloud_head;
107 DEBUG_ONLY(firm_dbg_module_t *dbg;)
112 affinity_node_t *aff;
113 co2_irn_t *touched_next;
116 int last_color_change;
119 unsigned tmp_fixed : 1;
120 struct list_head changed_list;
123 struct _co2_cloud_irn_t {
124 struct _co2_irn_t inh;
128 co2_cloud_irn_t *mst_parent;
131 co2_cloud_irn_t **mst_childs;
136 col_cost_pair_t *tmp_coloring;
137 struct list_head cloud_list;
138 struct list_head mst_list;
141 struct _co2_cloud_t {
151 co2_cloud_irn_t *master;
152 co2_cloud_irn_t *mst_root;
153 co2_cloud_irn_t **seq;
154 struct list_head members_head;
155 struct list_head list;
158 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
160 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
161 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
163 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
165 co2_t *env = (co2_t *) ph;
166 affinity_node_t *a = get_affinity_info(env->co, irn);
167 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
168 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
171 INIT_LIST_HEAD(&ci->changed_list);
172 ci->touched_next = env->touched;
173 ci->orig_col = get_irn_col(env->co, irn);
179 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
180 INIT_LIST_HEAD(&cci->cloud_list);
181 cci->mst_parent = cci;
188 static int cmp_clouds_gt(const void *a, const void *b)
190 const co2_cloud_t **p = a;
191 const co2_cloud_t **q = b;
194 return QSORT_CMP(d, c);
198 * An order on color/costs pairs.
199 * If the costs are equal, we use the color as a kind of normalization.
201 static int col_cost_pair_lt(const void *a, const void *b)
203 const col_cost_pair_t *p = a;
204 const col_cost_pair_t *q = b;
207 return QSORT_CMP(c, d);
210 static col_t get_col(co2_t *env, ir_node *irn)
212 co2_irn_t *ci = get_co2_irn(env, irn);
213 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
216 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
218 co2_irn_t *ci = get_co2_irn(env, irn);
219 return ci->fixed || ci->tmp_fixed;
222 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
225 arch_register_req_t req;
226 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
227 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
228 if(arch_register_req_is(&req, limited))
229 req.limited(req.limited_env, ci->adm_cache);
231 bitset_copy(ci->adm_cache, env->ignore_regs);
232 bitset_flip_all(ci->adm_cache);
236 return ci->adm_cache;
239 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
241 bitset_copy(bs, get_adm(env, ci));
245 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
247 bitset_t *bs = get_adm(env, ci);
248 return bitset_is_set(bs, col);
251 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
253 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
254 arch_register_req_t req;
256 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
258 if(arch_register_req_is(&req, limited)) {
262 req.limited(req.limited_env, aux);
263 n_constr = bitset_popcnt(aux);
264 bitset_foreach(aux, elm) {
265 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
271 * Determine costs which shall indicate how cheap/expensive it is to try
272 * to assign a node some color.
273 * The costs are computed for all colors. INT_MAX means that it is impossible
274 * to give the node that specific color.
276 * @param env The co2 this pointer.
277 * @param irn The node.
278 * @param col_costs An array of colors x costs where the costs are written to.
280 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
282 ir_node *irn = ci->irn;
283 be_ifg_t *ifg = env->co->cenv->ifg;
284 int n_regs = env->co->cls->n_regs;
285 bitset_t *forb = bitset_alloca(n_regs);
286 affinity_node_t *a = ci->aff;
293 /* Put all forbidden colors into the aux bitset. */
294 admissible_colors(env, ci, forb);
295 bitset_flip_all(forb);
297 for(i = 0; i < n_regs; ++i) {
298 col_costs[i].col = i;
299 col_costs[i].costs = 0;
305 co_gs_foreach_neighb(a, n) {
306 if(color_is_fix(env, n->irn)) {
307 col_t col = get_col(env, n->irn);
308 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
311 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
315 it = be_ifg_neighbours_iter_alloca(ifg);
316 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
317 col_t col = get_col(env, pos);
318 if(color_is_fix(env, pos)) {
319 col_costs[col].costs = INT_MAX;
322 incur_constraint_costs(env, pos, col_costs, INT_MAX);
323 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
327 /* Set the costs to infinity for each color which is not allowed at this node. */
328 bitset_foreach(forb, elm) {
329 col_costs[elm].costs = INT_MAX;
334 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
336 int n_regs = env->co->cls->n_regs;
339 for(i = 0; i < n_regs; ++i) {
341 seq[i].costs = INT_MAX;
344 assert(is_color_admissible(env, ci, col));
350 static void reject_coloring(struct list_head *h)
354 list_for_each_entry(co2_irn_t, pos, h, changed_list)
358 static void materialize_coloring(struct list_head *h)
362 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
363 pos->orig_col = pos->tmp_col;
373 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
378 list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
380 ent.col = pos->tmp_col;
382 obstack_grow(obst, &ent, sizeof(ent));
384 memset(&ent, 0, sizeof(ent));
385 obstack_grow(obst, &ent, sizeof(ent));
386 return obstack_finish(obst);
389 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
390 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
392 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
394 int n_regs = env->co->cls->n_regs;
395 be_ifg_t *ifg = env->co->cenv->ifg;
396 co2_irn_t *ci = get_co2_irn(env, irn);
402 for(i = 0; i < n_regs; ++i) {
403 col_t tgt_col = col_list[i].col;
404 unsigned costs = col_list[i].costs;
407 struct list_head changed;
411 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
413 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
414 if(INFEASIBLE(costs)) {
415 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
420 /* Set the new color of the node and mark the node as temporarily fixed. */
421 ci->tmp_col = tgt_col;
425 If that color has costs > 0, there's at least one neighbor having that color,
426 so we will try to change the neighbors' colors, too.
428 INIT_LIST_HEAD(&changed);
429 list_add(&ci->changed_list, &changed);
431 it = be_ifg_neighbours_iter_alloca(ifg);
432 be_ifg_foreach_neighbour(ifg, it, irn, n) {
434 /* try to re-color the neighbor if it has the target color. */
435 if(get_col(env, n) == tgt_col) {
436 struct list_head tmp;
439 Try to change the color of the neighbor and record all nodes which
440 get changed in the tmp list. Add this list to the "changed" list for
441 that color. If we did not succeed to change the color of the neighbor,
442 we bail out and try the next color.
444 INIT_LIST_HEAD(&tmp);
445 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
446 list_splice(&tmp, &changed);
453 We managed to assign the target color to all neighbors, so from the perspective
454 of the current node, every thing was ok and we can return safely.
457 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
458 list_splice(&changed, parent_changed);
464 If not, that color did not succeed and we unfix all nodes we touched
465 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
468 reject_coloring(&changed);
474 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
476 co2_irn_t *ci = get_co2_irn(env, irn);
478 col_t col = get_col(env, irn);
480 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
482 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
489 list_add(&ci->changed_list, parent_changed);
493 /* The node has the color it should not have _and_ has not been visited yet. */
494 if(!color_is_fix(env, irn)) {
495 int n_regs = env->co->cls->n_regs;
496 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
498 /* Get the costs for giving the node a specific color. */
499 determine_color_costs(env, ci, csts);
501 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
502 csts[not_col].costs = INT_MAX;
504 /* sort the colors according costs, cheapest first. */
505 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
507 /* Try recoloring the node using the color list. */
508 res = recolor(env, irn, csts, parent_changed, depth);
511 /* If we came here, everything went ok. */
515 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
517 co2_irn_t *ci = get_co2_irn(env, irn);
518 col_t col = get_col(env, irn);
521 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
523 /* the node has the wanted color. That's fine, mark it as visited and return. */
528 list_add(&ci->changed_list, parent_changed);
535 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
536 int n_regs = env->co->cls->n_regs;
537 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
539 /* Get the costs for giving the node a specific color. */
540 single_color_cost(env, ci, tgt_col, seq);
542 /* Try recoloring the node using the color list. */
543 res = recolor(env, irn, seq, parent_changed, depth);
548 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
552 static void front_inval_color(co2_cloud_irn_t *ci, col_t col)
554 int *base = FRONT_BASE(ci, col);
555 memset(base, -1, ci->mst_n_childs * sizeof(base[0]));
559 co2_cloud_irn_t *src, *tgt;
563 int cmp_edges(const void *a, const void *b)
567 return QSORT_CMP(p->costs, q->costs);
570 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
572 while(ci->mst_parent != ci->mst_parent)
578 static int cmp_parent(const void *a, const void *b)
580 const co2_cloud_irn_t *p = a;
581 const co2_cloud_irn_t *q = b;
582 return QSORT_CMP(q->mst_costs, p->mst_costs);
585 static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col)
587 int n_regs = ci->cloud->env->n_regs;
590 for(i = 0; i < ci->mst_n_childs; ++i) {
591 co2_cloud_irn_t *c = ci->mst_childs[i];
592 for(j = 0; j < n_regs; ++j) {
593 int costs = c->col_costs[j];
594 if(INFEASIBLE(costs))
595 c->tmp_coloring[j].costs = INT_MAX;
597 int add = j != (int) col ? c->mst_costs : 0;
598 c->tmp_coloring[j].costs = add + costs;
600 c->tmp_coloring[j].col = j;
602 qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt);
606 static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq)
608 int n_regs = ci->cloud->env->n_regs;
609 bitset_t *adm = bitset_alloca(n_regs);
612 // TODO: Prefer some colors depending on the neighbors, etc.
614 admissible_colors(ci->cloud->env, &ci->inh, adm);
615 for(i = 0; i < n_regs; ++i) {
618 if (!bitset_is_set(adm, i))
619 seq[i].costs = INT_MAX;
622 for(j = 0; j < ci->mst_n_childs; ++j) {
623 co2_cloud_irn_t *child = ci->mst_childs[j];
624 if (!INFEASIBLE(child->col_costs[i]))
625 seq[i].costs -= ci->mst_childs[j]->col_costs[i];
630 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
633 static int push_front(co2_cloud_irn_t *ci, int *front)
635 co2_t *env = ci->cloud->env;
636 int n_regs = env->n_regs;
637 int min_diff = INT_MAX;
641 for(i = 0; i < ci->mst_n_childs; ++i) {
642 co2_cloud_irn_t *child = ci->mst_childs[i];
646 if(idx + 1 < n_regs) {
647 int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs;
648 if(diff < min_diff) {
656 co2_cloud_irn_t *child = ci->mst_childs[min_chld];
657 DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff));
658 front[min_chld] += 1;
664 static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
666 int n_childs = ci->mst_n_childs;
668 select the front for the given color.
669 The front will determine the colors of the children.
671 int *front = FRONT_BASE(ci, col);
674 ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0);
675 for(i = 0; i < n_childs && ok; ++i) {
676 co2_cloud_irn_t *child = ci->mst_childs[i];
677 col_t col = front[i];
679 ok = color_subtree(child, col, changed, depth + 1);
685 static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth)
687 co2_t *env = ci->cloud->env;
688 struct list_head changed;
691 INIT_LIST_HEAD(&changed);
692 *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1);
694 for (i = 0; i < ci->mst_n_childs && ok; ++i) {
695 co2_cloud_irn_t *child = ci->mst_childs[i];
696 col_t tgt_col = child->tmp_coloring[front[i]].col;
698 ok = color_subtree(child, tgt_col, &changed, depth + 1);
701 reject_coloring(&changed);
706 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
708 int *front = FRONT_BASE(ci, col);
712 for(i = 0; i < ci->mst_n_childs; ++i) {
713 co2_cloud_irn_t *chld = ci->mst_childs[i];
714 col_t chld_col = front[i];
716 cost += examine_subtree_coloring(chld, chld_col);
717 cost += col != chld_col ? chld->mst_costs : 0;
723 static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth)
725 co2_t *env = ci->cloud->env;
726 int n_regs = env->n_regs;
727 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
728 int *front = alloca(ci->mst_n_childs * sizeof(front[0]));
730 int best_cost = INT_MAX;
735 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn));
737 for (i = 0; i < ci->mst_n_childs; ++i)
738 cloud_mst_build_colorings(ci->mst_childs[i], depth + 1);
740 for (i = 0; i < n_regs; ++i)
741 ci->col_costs[i] = INT_MAX;
743 /* Sort the children according to the cost of the affinity edge they have to the current node. */
744 // qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent);
746 determine_start_colors(ci, seq);
747 // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
749 for(i = 0; i < n_regs; ++i) {
750 col_t col = seq[i].col;
751 int costs = seq[i].costs;
754 if(INFEASIBLE(costs))
758 Judge, if it is worthwhile trying this color.
759 If another color was so good that we cannot get any better, bail out here.
763 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
765 /* This sorts the tmp_coloring array in the children according to the costs of the current color. */
766 fill_tmp_coloring(ci, col);
768 /* Initialize the front. It gives the indexes into the color tmp_coloring array. */
769 memset(front, 0, ci->mst_n_childs * sizeof(front));
772 As long as we have color configurations to try.
773 We try the best ones first and get worse over and over.
778 if (try_coloring(ci, col, front, &try_push, depth + 1)) {
779 int *res_front = FRONT_BASE(ci, col);
782 for(j = 0; j < ci->mst_n_childs; ++j) {
783 co2_cloud_irn_t *child = ci->mst_childs[j];
784 col_t col = child->tmp_coloring[front[j]].col;
788 costs = examine_subtree_coloring(ci, col);
789 ci->col_costs[col] = costs;
792 /* Set the current best color. */
793 if(costs < best_cost) {
799 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed"));
801 /* Worsen the configuration, if that one didn't succeed. */
803 done = try_push ? push_front(ci, front) < 0 : 1;
807 DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn));
808 for(i = 0; i < n_regs; ++i)
809 DBG((env->dbg, LEVEL_2, "%2{firm:indent} color %d costs %d\n", depth, i, ci->col_costs[i]));
815 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
817 co2_t *env = ci->cloud->env;
818 int n_regs = env->n_regs;
819 be_ifg_t *ifg = env->co->cenv->ifg;
820 co2_irn_t *ir = &ci->inh;
821 bitset_t *bs = bitset_alloca(n_regs);
828 admissible_colors(env, &ci->inh, bs);
830 bitset_foreach(bs, elm)
831 ci->color_badness[elm] = n_regs * ci->costs;
833 /* Use constrained/fixed interfering neighbors to influence the color badness */
834 it = be_ifg_neighbours_iter_alloca(ifg);
835 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
836 co2_irn_t *ni = get_co2_irn(env, irn);
839 admissible_colors(env, ni, bs);
840 n_adm = bitset_popcnt(bs);
841 bitset_foreach(bs, elm)
842 ci->color_badness[elm] += n_regs - n_adm;
845 col_t c = get_col(env, ni->irn);
846 ci->color_badness[c] += n_regs * ci->costs;
850 /* Collect the color badness for the whole subtree */
851 for(i = 0; i < ci->mst_n_childs; ++i) {
852 co2_cloud_irn_t *child = ci->mst_childs[i];
853 determine_color_badness(child, depth + 1);
855 for(j = 0; j < n_regs; ++j)
856 ci->color_badness[j] += child->color_badness[j];
859 for(j = 0; j < n_regs; ++j)
860 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
863 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth);
866 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, struct list_head *parent_changed, int depth)
868 co2_t *env = ci->cloud->env;
869 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
870 int is_root = ci->mst_parent == ci;
871 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
872 int min_badness = INT_MAX;
873 int best_col_costs = INT_MAX;
876 struct list_head changed;
879 for(i = 0; i < env->n_regs; ++i) {
880 int badness = ci->color_badness[i];
883 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? ci->color_badness[i] : INT_MAX;
885 min_badness = MIN(min_badness, badness);
888 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
889 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
890 seq[parent_col].costs = min_badness - 1;
892 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
894 INIT_LIST_HEAD(&changed);
895 for(i = 0; i < env->n_regs; ++i) {
896 col_t col = seq[i].col;
897 int costs = seq[i].costs;
898 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
900 int subtree_costs, sum_costs;
902 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
903 INIT_LIST_HEAD(&changed);
904 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
906 for(j = 0; ok && j < ci->mst_n_childs; ++j) {
907 ok = coalesce_top_down(ci->mst_childs[j], j, &changed, depth + 1) >= 0;
910 /* If the subtree could not be colored, we have to try another color. */
912 reject_coloring(&changed);
916 subtree_costs = examine_subtree_coloring(ci, col);
917 sum_costs = subtree_costs + add_cost;
918 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
920 if(sum_costs < best_col_costs) {
922 best_col_costs = sum_costs;
923 ci->col_costs[col] = subtree_costs;
926 reject_coloring(&changed);
931 /* If we are at the root and we achieved an acceptable amount of optimization, we finish. */
933 if(is_root && (ci->cloud->mst_costs * stop_percentage < ci->cloud->mst_costs - sum_costs)) {
934 assert(best_col != -1);
941 int *front = FRONT_BASE(ci->mst_parent, parent_col);
942 front[child_nr] = best_col;
946 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}applying best color %d for %+F\n", depth, best_col, ci->inh.irn));
947 apply_coloring(ci, best_col, parent_changed, depth);
953 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
955 be_ifg_t *ifg = env->co->cenv->ifg;
956 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
960 if(ci->visited >= env->visited)
963 /* mark the node as visited and add it to the cloud. */
964 ci->visited = env->visited;
966 list_add(&ci->cloud_list, &cloud->members_head);
968 DB((env->dbg, LEVEL_3, "\t%+F\n", ci->inh.irn));
970 /* determine the nodes costs */
971 co_gs_foreach_neighb(a, n) {
973 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
974 if(be_ifg_connected(ifg, a->irn, n->irn))
975 cloud->inevit += n->costs;
978 /* add the node's cost to the total costs of the cloud. */
980 cloud->costs += costs;
981 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
984 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
985 if(costs >= curr_costs) {
990 /* add all the neighbors of the node to the cloud. */
991 co_gs_foreach_neighb(a, n) {
992 affinity_node_t *an = get_affinity_info(env->co, n->irn);
994 populate_cloud(env, cloud, an, curr_costs);
998 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
1000 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
1001 co2_cloud_irn_t *ci;
1004 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
1005 memset(cloud, 0, sizeof(cloud[0]));
1006 INIT_LIST_HEAD(&cloud->members_head);
1007 INIT_LIST_HEAD(&cloud->list);
1008 list_add(&cloud->list, &env->cloud_head);
1009 cloud->best_costs = INT_MAX;
1012 populate_cloud(env, cloud, a, 0);
1014 /* Allocate space for the best colors array, where the best coloring is saved. */
1015 // cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
1017 /* Also allocate space for the node sequence and compute that sequence. */
1018 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
1021 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
1023 cloud->seq[i++] = ci;
1025 DBG((env->dbg, LEVEL_2, "cloud cost %d\n", cloud->costs));
1030 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
1032 ir_node *irn = ci->inh.irn;
1033 int *front = FRONT_BASE(ci, col);
1036 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
1037 ok = change_color_single(ci->cloud->env, irn, col, changed, depth);
1038 assert(ok && "Color changing may not fail while committing the coloring");
1040 for(i = 0; i < ci->mst_n_childs; ++i) {
1041 apply_coloring(ci->mst_childs[i], front[i], changed, depth + 1);
1045 static void process_cloud(co2_cloud_t *cloud)
1047 co2_t *env = cloud->env;
1050 struct list_head changed;
1055 /* Collect all edges in the cloud on an obstack and sort the increasingly */
1056 obstack_init(&cloud->obst);
1057 for(i = 0; i < cloud->n_memb; ++i) {
1058 co2_cloud_irn_t *ci = cloud->seq[i];
1061 co_gs_foreach_neighb(ci->inh.aff, n) {
1062 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
1063 if(ci->index < ni->index) {
1068 obstack_grow(&cloud->obst, &e, sizeof(e));
1073 edges = obstack_finish(&cloud->obst);
1074 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
1076 /* Compute the maximum spanning tree using Kruskal/Union-Find */
1077 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
1078 for(i = 0; i < n_edges; ++i) {
1079 edge_t *e = &edges[i];
1080 co2_cloud_irn_t *p_src = find_mst_root(e->src);
1081 co2_cloud_irn_t *p_tgt = find_mst_root(e->tgt);
1083 if(p_src != p_tgt) {
1086 Bring the more costly nodes near to the root of the MST.
1087 Thus, tgt shall always be the more expensive node.
1089 if(p_src->costs > p_tgt->costs) {
1095 p_tgt->mst_n_childs++;
1096 p_src->mst_parent = p_tgt;
1097 p_src->mst_costs = e->costs;
1099 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", p_src->inh.irn, p_tgt->inh.irn, e->costs));
1102 obstack_free(&cloud->obst, edges);
1104 for(i = 0; i < cloud->n_memb; ++i) {
1105 co2_cloud_irn_t *ci = cloud->seq[i];
1108 ci->mst_childs = obstack_alloc(&cloud->obst, ci->mst_n_childs * sizeof(ci->mst_childs));
1109 ci->col_costs = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->col_costs[0]));
1110 ci->tmp_coloring = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->tmp_coloring[0]));
1111 ci->fronts = obstack_alloc(&cloud->obst, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1112 ci->color_badness = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->fronts[0]));
1113 memset(ci->color_badness, 0, env->n_regs * sizeof(ci->color_badness[0]));
1114 memset(ci->col_costs, 0, env->n_regs * sizeof(ci->col_costs[0]));
1115 memset(ci->tmp_coloring, 0, env->n_regs * sizeof(ci->tmp_coloring[0]));
1116 memset(ci->fronts, 0, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
1118 for(j = 0; j < env->n_regs; j++)
1119 ci->col_costs[j] = INT_MAX;
1121 ci->mst_n_childs = 0;
1124 /* build the child arrays in the nodes */
1125 for(i = 0; i < cloud->n_memb; ++i) {
1126 co2_cloud_irn_t *ci = cloud->seq[i];
1127 if(ci->mst_parent != ci)
1128 ci->mst_parent->mst_childs[ci->mst_parent->mst_n_childs++] = ci;
1130 cloud->mst_root = ci;
1131 cloud->mst_costs = 0;
1135 /* Compute the "best" colorings. */
1136 // best_col = cloud_mst_build_colorings(cloud->mst_root, 0);
1138 determine_color_badness(cloud->mst_root, 0);
1139 INIT_LIST_HEAD(&changed);
1140 best_col = coalesce_top_down(cloud->mst_root, -1, &changed, 0);
1142 /* The coloring should represent the one with the best costs. */
1143 materialize_coloring(&changed);
1144 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1145 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1147 /* Fix all nodes in the cloud. */
1148 for(i = 0; i < cloud->n_memb; ++i)
1149 cloud->seq[i]->inh.fixed = 1;
1151 /* Free all space used while optimizing this cloud. */
1152 obstack_free(&cloud->obst, NULL);
1155 static int cloud_costs(co2_cloud_t *cloud)
1160 for(i = 0; i < cloud->n_memb; ++i) {
1161 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1162 col_t col = get_col(cloud->env, ci->irn);
1163 co_gs_foreach_neighb(ci->aff, n) {
1164 col_t n_col = get_col(cloud->env, n->irn);
1165 costs += col != n_col ? n->costs : 0;
1172 static void process(co2_t *env)
1176 co2_cloud_t **clouds;
1181 int final_costs = 0;
1184 co_gs_foreach_aff_node(env->co, a) {
1185 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1188 co2_cloud_t *cloud = new_cloud(env, a);
1194 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1195 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1197 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1199 for(i = 0; i < n_clouds; ++i) {
1200 init_costs += cloud_costs(clouds[i]);
1201 process_cloud(clouds[i]);
1202 all_costs += clouds[i]->costs;
1203 final_costs += cloud_costs(clouds[i]);
1205 /* Dump the IFG if the user demanded it. */
1206 if (dump_flags & DUMP_CLOUD) {
1210 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1211 if(f = fopen(buf, "wt")) {
1212 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1218 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1223 static void writeback_colors(co2_t *env)
1225 const arch_env_t *aenv = env->co->aenv;
1228 for(irn = env->touched; irn; irn = irn->touched_next) {
1229 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1230 arch_set_irn_register(aenv, irn->irn, reg);
1236 ___ _____ ____ ____ ___ _____ ____ _
1237 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1238 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1239 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1240 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1244 static const char *get_dot_color_name(int col)
1246 static const char *names[] = {
1280 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1283 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1285 arch_register_req_t req;
1287 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1288 if(arch_register_req_is(&req, limited))
1300 static void ifg_dump_graph_attr(FILE *f, void *self)
1302 fprintf(f, "overlay=false");
1305 static int ifg_is_dump_node(void *self, ir_node *irn)
1308 return !arch_irn_is(env->co->aenv, irn, ignore);
1311 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1314 co2_irn_t *ci = get_co2_irn(env, irn);
1318 co2_cloud_irn_t *cci = (void *) ci;
1319 if (cci->cloud && cci->cloud->mst_root == cci)
1323 ir_fprintf(f, "label=\"%+F\" style=filled peripheries=%d color=%s shape=%s", irn, peri,
1324 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1327 static void ifg_dump_at_end(FILE *file, void *self)
1332 co_gs_foreach_aff_node(env->co, a) {
1333 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1334 int idx = get_irn_idx(a->irn);
1337 co_gs_foreach_neighb(a, n) {
1338 int nidx = get_irn_idx(n->irn);
1339 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1342 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1343 const char *arr = "arrowhead=dot arrowtail=dot";
1345 if(ci->mst_parent == ai)
1346 arr = "arrowtail=normal";
1347 else if(ai->mst_parent == ci)
1348 arr = "arrowhead=normal";
1350 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1357 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1359 ifg_dump_graph_attr,
1367 void co_solve_heuristic_new(copy_opt_t *co)
1372 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1376 env.n_regs = co->cls->n_regs;
1377 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1378 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1379 bitset_flip_all(env.ignore_regs);
1380 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1381 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1382 INIT_LIST_HEAD(&env.cloud_head);
1384 if(dump_flags & DUMP_BEFORE) {
1385 if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1386 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1393 if(dump_flags & DUMP_AFTER) {
1394 if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1395 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1400 writeback_colors(&env);
1401 phase_free(&env.ph);