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"
43 static int dump_flags = 0;
45 /* Options using libcore */
48 static const lc_opt_enum_mask_items_t dump_items[] = {
49 { "before", DUMP_BEFORE },
50 { "after", DUMP_AFTER },
51 { "cloud", DUMP_CLOUD },
52 { "all", 2 * DUMP_CLOUD - 1 },
56 static lc_opt_enum_mask_var_t dump_var = {
57 &dump_flags, dump_items
60 static const lc_opt_table_entry_t options[] = {
61 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var),
65 void be_co2_register_options(lc_opt_entry_t *grp)
67 lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
68 lc_opt_add_table(co2_grp, options);
74 / ___|| |_ __ _ _ __| |_
75 \___ \| __/ _` | '__| __|
76 ___) | || (_| | | | |_
77 |____/ \__\__,_|_| \__|
81 #define INFEASIBLE(cost) ((cost) == INT_MAX)
83 static be_ifg_dump_dot_cb_t ifg_dot_cb;
85 typedef unsigned col_t;
87 typedef struct _co2_irn_t co2_irn_t;
88 typedef struct _co2_cloud_t co2_cloud_t;
89 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
99 bitset_t *ignore_regs;
103 struct list_head cloud_head;
104 DEBUG_ONLY(firm_dbg_module_t *dbg;)
109 affinity_node_t *aff;
110 co2_irn_t *touched_next;
113 int last_color_change;
115 unsigned tmp_fixed : 1;
116 struct list_head changed_list;
119 struct _co2_cloud_irn_t {
120 struct _co2_irn_t inh;
124 co2_cloud_irn_t *mst_parent;
127 co2_cloud_irn_t **mst_childs;
131 col_cost_pair_t *tmp_coloring;
132 struct list_head cloud_list;
133 struct list_head mst_list;
136 struct _co2_cloud_t {
146 co2_cloud_irn_t *master;
147 co2_cloud_irn_t *mst_root;
148 co2_cloud_irn_t **seq;
149 struct list_head members_head;
150 struct list_head list;
153 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
155 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
156 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
158 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
160 co2_t *env = (co2_t *) ph;
161 affinity_node_t *a = get_affinity_info(env->co, irn);
162 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
163 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
166 INIT_LIST_HEAD(&ci->changed_list);
167 ci->touched_next = env->touched;
168 ci->orig_col = get_irn_col(env->co, irn);
174 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
175 INIT_LIST_HEAD(&cci->cloud_list);
176 cci->mst_parent = cci;
183 static int cmp_clouds_gt(const void *a, const void *b)
185 const co2_cloud_t **p = a;
186 const co2_cloud_t **q = b;
193 * An order on color/costs pairs.
194 * If the costs are equal, we use the color as a kind of normalization.
196 static int col_cost_pair_lt(const void *a, const void *b)
198 const col_cost_pair_t *p = a;
199 const col_cost_pair_t *q = b;
205 static col_t get_col(co2_t *env, ir_node *irn)
207 co2_irn_t *ci = get_co2_irn(env, irn);
208 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
211 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
213 co2_irn_t *ci = get_co2_irn(env, irn);
214 return ci->fixed || ci->tmp_fixed;
217 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
219 arch_register_req_t req;
221 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
222 if(arch_register_req_is(&req, limited))
223 req.limited(req.limited_env, bs);
225 bitset_copy(bs, env->ignore_regs);
232 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
234 bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
235 admissible_colors(env, ci, bs);
236 return bitset_is_set(bs, col);
239 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
241 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
242 arch_register_req_t req;
244 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
246 if(arch_register_req_is(&req, limited)) {
250 req.limited(req.limited_env, aux);
251 n_constr = bitset_popcnt(aux);
252 bitset_foreach(aux, elm) {
253 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
259 * Determine costs which shall indicate how cheap/expensive it is to try
260 * to assign a node some color.
261 * The costs are computed for all colors. INT_MAX means that it is impossible
262 * to give the node that specific color.
264 * @param env The co2 this pointer.
265 * @param irn The node.
266 * @param col_costs An array of colors x costs where the costs are written to.
268 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
270 ir_node *irn = ci->irn;
271 be_ifg_t *ifg = env->co->cenv->ifg;
272 int n_regs = env->co->cls->n_regs;
273 bitset_t *forb = bitset_alloca(n_regs);
274 affinity_node_t *a = get_affinity_info(env->co, irn);
281 /* Put all forbidden colors into the aux bitset. */
282 admissible_colors(env, ci, forb);
283 bitset_flip_all(forb);
285 for(i = 0; i < n_regs; ++i) {
286 col_costs[i].col = i;
287 col_costs[i].costs = 0;
293 co_gs_foreach_neighb(a, n) {
294 if(color_is_fix(env, n->irn)) {
295 col_t col = get_col(env, n->irn);
296 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
299 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
303 it = be_ifg_neighbours_iter_alloca(ifg);
304 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
305 col_t col = get_col(env, pos);
306 if(color_is_fix(env, pos)) {
307 col_costs[col].costs = INT_MAX;
310 incur_constraint_costs(env, pos, col_costs, INT_MAX);
311 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
315 /* Set the costs to infinity for each color which is not allowed at this node. */
316 bitset_foreach(forb, elm) {
317 col_costs[elm].costs = INT_MAX;
322 static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
324 int n_regs = env->co->cls->n_regs;
327 for(i = 0; i < n_regs; ++i) {
329 seq[i].costs = INT_MAX;
337 static void reject_coloring(struct list_head *h)
341 list_for_each_entry(co2_irn_t, pos, h, changed_list)
345 static void materialize_coloring(struct list_head *h)
349 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
350 pos->orig_col = pos->tmp_col;
360 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
365 list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
367 ent.col = pos->tmp_col;
369 obstack_grow(obst, &ent, sizeof(ent));
371 memset(&ent, 0, sizeof(ent));
372 obstack_grow(obst, &ent, sizeof(ent));
373 return obstack_finish(obst);
376 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
377 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
379 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
381 int n_regs = env->co->cls->n_regs;
382 be_ifg_t *ifg = env->co->cenv->ifg;
383 co2_irn_t *ci = get_co2_irn(env, irn);
389 for(i = 0; i < n_regs; ++i) {
390 col_t tgt_col = col_list[i].col;
391 unsigned costs = col_list[i].costs;
394 struct list_head changed;
398 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
400 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
401 if(INFEASIBLE(costs)) {
402 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
407 /* Set the new color of the node and mark the node as temporarily fixed. */
408 ci->tmp_col = tgt_col;
412 If that color has costs > 0, there's at least one neighbor having that color,
413 so we will try to change the neighbors' colors, too.
415 INIT_LIST_HEAD(&changed);
416 list_add(&ci->changed_list, &changed);
418 it = be_ifg_neighbours_iter_alloca(ifg);
419 be_ifg_foreach_neighbour(ifg, it, irn, n) {
421 /* try to re-color the neighbor if it has the target color. */
422 if(get_col(env, n) == tgt_col) {
423 struct list_head tmp;
426 Try to change the color of the neighbor and record all nodes which
427 get changed in the tmp list. Add this list to the "changed" list for
428 that color. If we did not succeed to change the color of the neighbor,
429 we bail out and try the next color.
431 INIT_LIST_HEAD(&tmp);
432 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
433 list_splice(&tmp, &changed);
440 We managed to assign the target color to all neighbors, so from the perspective
441 of the current node, every thing was ok and we can return safely.
444 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
445 list_splice(&changed, parent_changed);
451 If not, that color did not succeed and we unfix all nodes we touched
452 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
455 reject_coloring(&changed);
461 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
463 co2_irn_t *ci = get_co2_irn(env, irn);
465 col_t col = get_col(env, irn);
467 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
469 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
476 list_add(&ci->changed_list, parent_changed);
480 /* The node has the color it should not have _and_ has not been visited yet. */
481 if(!color_is_fix(env, irn)) {
482 int n_regs = env->co->cls->n_regs;
483 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
485 /* Get the costs for giving the node a specific color. */
486 determine_color_costs(env, ci, csts);
488 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
489 csts[not_col].costs = INT_MAX;
491 /* sort the colors according costs, cheapest first. */
492 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
494 /* Try recoloring the node using the color list. */
495 res = recolor(env, irn, csts, parent_changed, depth);
498 /* If we came here, everything went ok. */
502 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
504 co2_irn_t *ci = get_co2_irn(env, irn);
505 col_t col = get_col(env, irn);
508 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
510 /* the node has the wanted color. That's fine, mark it as visited and return. */
515 list_add(&ci->changed_list, parent_changed);
518 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}ok\n", depth));
522 if(!color_is_fix(env, irn)) {
523 int n_regs = env->co->cls->n_regs;
524 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
526 /* Get the costs for giving the node a specific color. */
527 single_color_cost(env, tgt_col, seq);
529 /* Try recoloring the node using the color list. */
530 res = recolor(env, irn, seq, parent_changed, depth);
532 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
538 static void front_inval_color(co2_cloud_irn_t *ci, col_t col)
540 int *base = FRONT_BASE(ci, col);
541 memset(base, -1, ci->mst_n_childs * sizeof(base[0]));
545 co2_cloud_irn_t *src, *tgt;
549 int cmp_edges(const void *a, const void *b)
553 return CMP(p->costs, q->costs);
556 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
558 while(ci->mst_parent != ci->mst_parent)
564 static int cmp_parent(const void *a, const void *b)
566 const co2_cloud_irn_t *p = a;
567 const co2_cloud_irn_t *q = b;
568 return CMP(q->mst_costs, p->mst_costs);
571 static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col)
573 int n_regs = ci->cloud->env->n_regs;
576 for(i = 0; i < ci->mst_n_childs; ++i) {
577 co2_cloud_irn_t *c = ci->mst_childs[i];
578 for(j = 0; j < n_regs; ++j) {
579 int costs = c->col_costs[j];
580 if(INFEASIBLE(costs))
581 c->tmp_coloring[j].costs = INT_MAX;
583 int add = j != (int) col ? c->mst_costs : 0;
584 c->tmp_coloring[j].costs = add + costs;
586 c->tmp_coloring[j].col = j;
588 qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt);
592 static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq)
594 int n_regs = ci->cloud->env->n_regs;
595 bitset_t *adm = bitset_alloca(n_regs);
598 // TODO: Prefer some colors depending on the neighbors, etc.
600 admissible_colors(ci->cloud->env, &ci->inh, adm);
601 for(i = 0; i < n_regs; ++i) {
604 if (!bitset_is_set(adm, i))
605 seq[i].costs = INT_MAX;
608 for(j = 0; j < ci->mst_n_childs; ++j) {
609 co2_cloud_irn_t *child = ci->mst_childs[j];
610 if (!INFEASIBLE(child->col_costs[i]))
611 seq[i].costs -= ci->mst_childs[j]->col_costs[i];
616 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
619 static int push_front(co2_cloud_irn_t *ci, int *front)
621 co2_t *env = ci->cloud->env;
622 int n_regs = env->n_regs;
623 int min_diff = INT_MAX;
627 for(i = 0; i < ci->mst_n_childs; ++i) {
628 co2_cloud_irn_t *child = ci->mst_childs[i];
632 if(idx + 1 < n_regs) {
633 int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs;
634 if(diff < min_diff) {
642 co2_cloud_irn_t *child = ci->mst_childs[min_chld];
643 DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff));
644 front[min_chld] += 1;
650 static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
652 int n_childs = ci->mst_n_childs;
654 select the front for the given color.
655 The front will determine the colors of the children.
657 int *front = FRONT_BASE(ci, col);
660 ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0);
661 for(i = 0; i < n_childs && ok; ++i) {
662 co2_cloud_irn_t *child = ci->mst_childs[i];
663 col_t col = front[i];
665 ok = color_subtree(child, col, changed, depth + 1);
671 static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth)
673 co2_t *env = ci->cloud->env;
674 struct list_head changed;
677 INIT_LIST_HEAD(&changed);
678 *initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1);
680 for (i = 0; i < ci->mst_n_childs && ok; ++i) {
681 co2_cloud_irn_t *child = ci->mst_childs[i];
682 col_t tgt_col = child->tmp_coloring[front[i]].col;
684 ok = color_subtree(child, tgt_col, &changed, depth + 1);
687 reject_coloring(&changed);
692 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
694 int *front = FRONT_BASE(ci, col);
698 for(i = 0; i < ci->mst_n_childs; ++i) {
699 co2_cloud_irn_t *chld = ci->mst_childs[i];
700 col_t chld_col = front[i];
702 cost += examine_subtree_coloring(chld, chld_col);
703 cost += col != chld_col ? chld->mst_costs : 0;
709 static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth)
711 co2_t *env = ci->cloud->env;
712 int n_regs = env->n_regs;
713 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
714 int *front = alloca(ci->mst_n_childs * sizeof(front[0]));
716 int best_cost = INT_MAX;
721 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn));
723 for (i = 0; i < ci->mst_n_childs; ++i)
724 cloud_mst_build_colorings(ci->mst_childs[i], depth + 1);
726 for (i = 0; i < n_regs; ++i)
727 ci->col_costs[i] = INT_MAX;
729 /* Sort the children according to the cost of the affinity edge they have to the current node. */
730 // qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent);
732 determine_start_colors(ci, seq);
733 // qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
735 for(i = 0; i < n_regs; ++i) {
736 col_t col = seq[i].col;
737 int costs = seq[i].costs;
740 if(INFEASIBLE(costs))
744 Judge, if it is worthwhile trying this color.
745 If another color was so good that we cannot get any better, bail out here.
749 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
751 /* This sorts the tmp_coloring array in the children according to the costs of the current color. */
752 fill_tmp_coloring(ci, col);
754 /* Initialize the front. It gives the indexes into the color tmp_coloring array. */
755 memset(front, 0, ci->mst_n_childs * sizeof(front));
758 As long as we have color configurations to try.
759 We try the best ones first and get worse over and over.
764 if (try_coloring(ci, col, front, &try_push, depth + 1)) {
765 int *res_front = FRONT_BASE(ci, col);
768 for(j = 0; j < ci->mst_n_childs; ++j) {
769 co2_cloud_irn_t *child = ci->mst_childs[j];
770 col_t col = child->tmp_coloring[front[j]].col;
774 costs = examine_subtree_coloring(ci, col);
775 ci->col_costs[col] = costs;
778 /* Set the current best color. */
779 if(costs < best_cost) {
785 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed"));
787 /* Worsen the configuration, if that one didn't succeed. */
789 done = try_push ? push_front(ci, front) < 0 : 1;
793 DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn));
794 for(i = 0; i < n_regs; ++i)
795 DBG((env->dbg, LEVEL_2, "%2{firm:indent} color %d costs %d\n", depth, i, ci->col_costs[i]));
801 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
803 be_ifg_t *ifg = env->co->cenv->ifg;
804 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
808 if(ci->visited >= env->visited)
811 /* mark the node as visited and add it to the cloud. */
812 ci->visited = env->visited;
814 list_add(&ci->cloud_list, &cloud->members_head);
816 DB((env->dbg, LEVEL_3, "\t%+F\n", ci->inh.irn));
818 /* determine the nodes costs */
819 co_gs_foreach_neighb(a, n) {
821 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
822 if(be_ifg_connected(ifg, a->irn, n->irn))
823 cloud->inevit += n->costs;
826 /* add the node's cost to the total costs of the cloud. */
828 cloud->costs += costs;
829 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
832 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
833 if(costs >= curr_costs) {
838 /* add all the neighbors of the node to the cloud. */
839 co_gs_foreach_neighb(a, n) {
840 affinity_node_t *an = get_affinity_info(env->co, n->irn);
842 populate_cloud(env, cloud, an, curr_costs);
846 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
848 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
852 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
853 memset(cloud, 0, sizeof(cloud[0]));
854 INIT_LIST_HEAD(&cloud->members_head);
855 INIT_LIST_HEAD(&cloud->list);
856 list_add(&cloud->list, &env->cloud_head);
857 cloud->best_costs = INT_MAX;
860 populate_cloud(env, cloud, a, 0);
862 /* Allocate space for the best colors array, where the best coloring is saved. */
863 // cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
865 /* Also allocate space for the node sequence and compute that sequence. */
866 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
869 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
871 cloud->seq[i++] = ci;
873 DBG((env->dbg, LEVEL_2, "cloud cost %d\n", cloud->costs));
878 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
880 ir_node *irn = ci->inh.irn;
881 int *front = FRONT_BASE(ci, col);
884 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
885 ok = change_color_single(ci->cloud->env, irn, col, changed, depth);
886 assert(ok && "Color changing may not fail while committing the coloring");
888 for(i = 0; i < ci->mst_n_childs; ++i) {
889 apply_coloring(ci->mst_childs[i], front[i], changed, depth + 1);
893 static void process_cloud(co2_cloud_t *cloud)
895 co2_t *env = cloud->env;
898 struct list_head changed;
903 /* Collect all edges in the cloud on an obstack and sort the increasingly */
904 obstack_init(&cloud->obst);
905 for(i = 0; i < cloud->n_memb; ++i) {
906 co2_cloud_irn_t *ci = cloud->seq[i];
909 co_gs_foreach_neighb(ci->inh.aff, n) {
910 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
911 if(ci->index < ni->index) {
916 obstack_grow(&cloud->obst, &e, sizeof(e));
921 edges = obstack_finish(&cloud->obst);
922 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
924 /* Compute the maximum spanning tree using Kruskal/Union-Find */
925 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
926 for(i = 0; i < n_edges; ++i) {
927 edge_t *e = &edges[i];
928 co2_cloud_irn_t *p_src = find_mst_root(e->src);
929 co2_cloud_irn_t *p_tgt = find_mst_root(e->tgt);
932 p_tgt->mst_n_childs++;
933 p_src->mst_parent = p_tgt;
934 p_src->mst_costs = e->costs;
936 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", p_src->inh.irn, p_tgt->inh.irn, e->costs));
939 obstack_free(&cloud->obst, edges);
941 for(i = 0; i < cloud->n_memb; ++i) {
942 co2_cloud_irn_t *ci = cloud->seq[i];
943 ci->mst_childs = obstack_alloc(&cloud->obst, ci->mst_n_childs * sizeof(ci->mst_childs));
944 ci->col_costs = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->col_costs[0]));
945 ci->tmp_coloring = obstack_alloc(&cloud->obst, env->n_regs * sizeof(ci->tmp_coloring[0]));
946 ci->fronts = obstack_alloc(&cloud->obst, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
947 memset(ci->col_costs, 0, env->n_regs * sizeof(ci->col_costs[0]));
948 memset(ci->tmp_coloring, 0, env->n_regs * sizeof(ci->tmp_coloring[0]));
949 memset(ci->fronts, 0, env->n_regs * ci->mst_n_childs * sizeof(ci->fronts[0]));
951 ci->mst_n_childs = 0;
954 /* build the child arrays in the nodes */
955 for(i = 0; i < cloud->n_memb; ++i) {
956 co2_cloud_irn_t *ci = cloud->seq[i];
957 if(ci->mst_parent != ci)
958 ci->mst_parent->mst_childs[ci->mst_parent->mst_n_childs++] = ci;
960 cloud->mst_root = ci;
961 cloud->mst_costs = 0;
965 /* Compute the "best" colorings. */
966 best_col = cloud_mst_build_colorings(cloud->mst_root, 0);
968 for(i = 0; i < env->n_regs; ++i) {
970 c = examine_subtree_coloring(cloud->mst_root, i);
971 DBG((env->dbg, LEVEL_2, "color %d costs %d\n", i, c));
974 /* Apply the coloring for the best color in the root node and fix all nodes in this cloud */
975 INIT_LIST_HEAD(&changed);
976 apply_coloring(cloud->mst_root, best_col, &changed, 0);
977 materialize_coloring(&changed);
978 for(i = 0; i < cloud->n_memb; ++i)
979 cloud->seq[i]->inh.fixed = 1;
981 obstack_free(&cloud->obst, NULL);
984 static int cloud_costs(co2_cloud_t *cloud)
989 for(i = 0; i < cloud->n_memb; ++i) {
990 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
991 col_t col = get_col(cloud->env, ci->irn);
992 co_gs_foreach_neighb(ci->aff, n) {
993 col_t n_col = get_col(cloud->env, n->irn);
994 costs += col != n_col ? n->costs : 0;
1001 static void process(co2_t *env)
1005 co2_cloud_t **clouds;
1010 int final_costs = 0;
1013 co_gs_foreach_aff_node(env->co, a) {
1014 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1017 co2_cloud_t *cloud = new_cloud(env, a);
1023 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1024 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1026 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1028 for(i = 0; i < n_clouds; ++i) {
1029 init_costs += cloud_costs(clouds[i]);
1030 process_cloud(clouds[i]);
1031 all_costs += clouds[i]->costs;
1032 final_costs += cloud_costs(clouds[i]);
1034 /* Dump the IFG if the user demanded it. */
1035 if (dump_flags & DUMP_CLOUD) {
1039 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1040 if(f = fopen(buf, "wt")) {
1041 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1047 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1052 static void writeback_colors(co2_t *env)
1054 const arch_env_t *aenv = env->co->aenv;
1057 for(irn = env->touched; irn; irn = irn->touched_next) {
1058 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1059 arch_set_irn_register(aenv, irn->irn, reg);
1065 ___ _____ ____ ____ ___ _____ ____ _
1066 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1067 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1068 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1069 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1073 static const char *get_dot_color_name(int col)
1075 static const char *names[] = {
1109 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1112 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1114 arch_register_req_t req;
1116 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1117 if(arch_register_req_is(&req, limited))
1129 static void ifg_dump_graph_attr(FILE *f, void *self)
1131 fprintf(f, "overlay=false");
1134 static int ifg_is_dump_node(void *self, ir_node *irn)
1137 return !arch_irn_is(env->co->aenv, irn, ignore);
1140 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1143 co2_irn_t *ci = get_co2_irn(env, irn);
1147 co2_cloud_irn_t *cci = (void *) ci;
1148 if (cci->cloud && cci->cloud->mst_root == cci)
1152 ir_fprintf(f, "label=\"%+F\" style=filled peripheries=%d color=%s shape=%s", irn, peri,
1153 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1156 static void ifg_dump_at_end(FILE *file, void *self)
1161 co_gs_foreach_aff_node(env->co, a) {
1162 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1163 int idx = get_irn_idx(a->irn);
1166 co_gs_foreach_neighb(a, n) {
1167 int nidx = get_irn_idx(n->irn);
1168 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1171 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1172 const char *arr = "arrowhead=dot arrowtail=dot";
1174 if(ci->mst_parent == ai)
1175 arr = "arrowtail=normal";
1176 else if(ai->mst_parent == ci)
1177 arr = "arrowhead=normal";
1179 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1186 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1188 ifg_dump_graph_attr,
1196 void co_solve_heuristic_new(copy_opt_t *co)
1201 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1205 env.n_regs = co->cls->n_regs;
1206 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1207 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1208 bitset_flip_all(env.ignore_regs);
1209 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1210 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1211 INIT_LIST_HEAD(&env.cloud_head);
1213 if(dump_flags & DUMP_BEFORE) {
1214 if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1215 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1222 if(dump_flags & DUMP_AFTER) {
1223 if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1224 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1229 writeback_colors(&env);
1230 phase_free(&env.ph);