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"
36 #include "becopyopt.h"
37 #include "becopyopt_t.h"
38 #include "bechordal_t.h"
43 #define DUMP_ALL 2 * DUMP_CLOUD - 1
45 static unsigned dump_flags = 0;
46 static int subtree_iter = 4;
47 static int max_depth = 20;
48 static double constr_factor = 0.9;
50 /* Options using libcore */
53 static const lc_opt_enum_mask_items_t dump_items[] = {
54 { "before", DUMP_BEFORE },
55 { "after", DUMP_AFTER },
56 { "cloud", DUMP_CLOUD },
61 static lc_opt_enum_mask_var_t dump_var = {
62 &dump_flags, dump_items
65 static const lc_opt_table_entry_t options[] = {
66 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
67 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
68 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
69 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
73 void be_init_copyheur2(void)
75 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
76 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
77 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
78 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
80 lc_opt_add_table(co2_grp, options);
83 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
88 / ___|| |_ __ _ _ __| |_
89 \___ \| __/ _` | '__| __|
90 ___) | || (_| | | | |_
91 |____/ \__\__,_|_| \__|
95 #define INFEASIBLE(cost) ((cost) == INT_MAX)
97 static be_ifg_dump_dot_cb_t ifg_dot_cb;
99 typedef unsigned col_t;
101 typedef struct _co2_irn_t co2_irn_t;
102 typedef struct _co2_cloud_t co2_cloud_t;
103 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
113 bitset_t *ignore_regs;
117 struct list_head cloud_head;
118 DEBUG_ONLY(firm_dbg_module_t *dbg;)
123 affinity_node_t *aff;
124 co2_irn_t *touched_next;
127 int last_color_change;
130 unsigned tmp_fixed : 1;
131 unsigned is_constrained : 1;
132 struct list_head changed_list;
135 struct _co2_cloud_irn_t {
136 struct _co2_irn_t inh;
140 co2_cloud_irn_t *mst_parent;
143 co2_cloud_irn_t **mst_childs;
148 col_cost_pair_t *tmp_coloring;
149 struct list_head cloud_list;
150 struct list_head mst_list;
153 struct _co2_cloud_t {
165 co2_cloud_irn_t *master;
166 co2_cloud_irn_t *mst_root;
167 co2_cloud_irn_t **seq;
168 struct list_head members_head;
169 struct list_head list;
173 co2_cloud_irn_t *src, *tgt;
177 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
179 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
180 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
182 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
184 co2_t *env = (co2_t *) ph;
185 affinity_node_t *a = get_affinity_info(env->co, irn);
186 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
187 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
190 INIT_LIST_HEAD(&ci->changed_list);
191 ci->touched_next = env->touched;
192 ci->orig_col = get_irn_col(env->co, irn);
198 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
199 INIT_LIST_HEAD(&cci->cloud_list);
200 cci->mst_parent = cci;
206 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
208 static int cmp_clouds_gt(const void *a, const void *b)
210 const co2_cloud_t * const *p = a;
211 const co2_cloud_t * const *q = b;
212 double c = CLOUD_WEIGHT(*p);
213 double d = CLOUD_WEIGHT(*q);
214 return QSORT_CMP(d, c);
218 * An order on color/costs pairs.
219 * If the costs are equal, we use the color as a kind of normalization.
221 static int col_cost_pair_lt(const void *a, const void *b)
223 const col_cost_pair_t *p = a;
224 const col_cost_pair_t *q = b;
227 return QSORT_CMP(c, d);
230 int cmp_edges(const void *a, const void *b)
234 return QSORT_CMP(q->costs, p->costs);
237 static col_t get_col(co2_t *env, ir_node *irn)
239 co2_irn_t *ci = get_co2_irn(env, irn);
240 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
243 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
245 co2_irn_t *ci = get_co2_irn(env, irn);
246 return ci->fixed || ci->tmp_fixed;
249 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
252 arch_register_req_t req;
253 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
254 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
255 if(arch_register_req_is(&req, limited)) {
256 req.limited(req.limited_env, ci->adm_cache);
257 ci->is_constrained = 1;
260 bitset_copy(ci->adm_cache, env->ignore_regs);
261 bitset_flip_all(ci->adm_cache);
265 return ci->adm_cache;
268 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
270 bitset_copy(bs, get_adm(env, ci));
274 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
276 bitset_t *bs = get_adm(env, ci);
277 return bitset_is_set(bs, col);
280 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
284 return ci->is_constrained;
287 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
289 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
290 arch_register_req_t req;
292 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
294 if(arch_register_req_is(&req, limited)) {
298 req.limited(req.limited_env, aux);
299 n_constr = bitset_popcnt(aux);
300 bitset_foreach(aux, elm) {
301 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
307 * Determine costs which shall indicate how cheap/expensive it is to try
308 * to assign a node some color.
309 * The costs are computed for all colors. INT_MAX means that it is impossible
310 * to give the node that specific color.
312 * @param env The co2 this pointer.
313 * @param irn The node.
314 * @param col_costs An array of colors x costs where the costs are written to.
316 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
318 ir_node *irn = ci->irn;
319 be_ifg_t *ifg = env->co->cenv->ifg;
320 int n_regs = env->co->cls->n_regs;
321 bitset_t *forb = bitset_alloca(n_regs);
322 affinity_node_t *a = ci->aff;
329 /* Put all forbidden colors into the aux bitset. */
330 admissible_colors(env, ci, forb);
331 bitset_flip_all(forb);
333 for(i = 0; i < n_regs; ++i) {
334 col_costs[i].col = i;
335 col_costs[i].costs = 0;
341 co_gs_foreach_neighb(a, n) {
342 if(color_is_fix(env, n->irn)) {
343 col_t col = get_col(env, n->irn);
344 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
347 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
351 it = be_ifg_neighbours_iter_alloca(ifg);
352 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
353 col_t col = get_col(env, pos);
354 if(color_is_fix(env, pos)) {
355 col_costs[col].costs = INT_MAX;
358 incur_constraint_costs(env, pos, col_costs, INT_MAX);
359 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
362 be_ifg_neighbours_break(ifg, it);
364 /* Set the costs to infinity for each color which is not allowed at this node. */
365 bitset_foreach(forb, elm) {
366 col_costs[elm].costs = INT_MAX;
371 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
373 int n_regs = env->co->cls->n_regs;
376 for(i = 0; i < n_regs; ++i) {
378 seq[i].costs = INT_MAX;
381 assert(is_color_admissible(env, ci, col));
387 static void reject_coloring(struct list_head *h)
391 list_for_each_entry(co2_irn_t, pos, h, changed_list)
395 static void materialize_coloring(struct list_head *h)
399 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
400 pos->orig_col = pos->tmp_col;
405 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
407 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
409 int n_regs = env->co->cls->n_regs;
410 be_ifg_t *ifg = env->co->cenv->ifg;
411 co2_irn_t *ci = get_co2_irn(env, irn);
416 if(depth >= max_depth)
419 for(i = 0; i < n_regs; ++i) {
420 col_t tgt_col = col_list[i].col;
421 unsigned costs = col_list[i].costs;
424 struct list_head changed;
428 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
430 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
431 if(INFEASIBLE(costs)) {
432 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
437 /* Set the new color of the node and mark the node as temporarily fixed. */
438 ci->tmp_col = tgt_col;
442 If that color has costs > 0, there's at least one neighbor having that color,
443 so we will try to change the neighbors' colors, too.
445 INIT_LIST_HEAD(&changed);
446 list_add(&ci->changed_list, &changed);
448 it = be_ifg_neighbours_iter_alloca(ifg);
449 be_ifg_foreach_neighbour(ifg, it, irn, n) {
451 /* try to re-color the neighbor if it has the target color. */
452 if(get_col(env, n) == tgt_col) {
453 struct list_head tmp;
456 Try to change the color of the neighbor and record all nodes which
457 get changed in the tmp list. Add this list to the "changed" list for
458 that color. If we did not succeed to change the color of the neighbor,
459 we bail out and try the next color.
461 INIT_LIST_HEAD(&tmp);
462 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
463 list_splice(&tmp, &changed);
468 be_ifg_neighbours_break(ifg, it);
471 We managed to assign the target color to all neighbors, so from the perspective
472 of the current node, every thing was ok and we can return safely.
475 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
476 list_splice(&changed, parent_changed);
482 If not, that color did not succeed and we unfix all nodes we touched
483 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
486 reject_coloring(&changed);
492 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
494 co2_irn_t *ci = get_co2_irn(env, irn);
496 col_t col = get_col(env, irn);
498 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
500 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
507 list_add(&ci->changed_list, parent_changed);
511 /* The node has the color it should not have _and_ has not been visited yet. */
512 if(!color_is_fix(env, irn)) {
513 int n_regs = env->co->cls->n_regs;
514 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
516 /* Get the costs for giving the node a specific color. */
517 determine_color_costs(env, ci, csts);
519 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
520 csts[not_col].costs = INT_MAX;
522 /* sort the colors according costs, cheapest first. */
523 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
525 /* Try recoloring the node using the color list. */
526 res = recolor(env, irn, csts, parent_changed, depth);
529 /* If we came here, everything went ok. */
533 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
535 co2_irn_t *ci = get_co2_irn(env, irn);
536 col_t col = get_col(env, irn);
539 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
541 /* the node has the wanted color. That's fine, mark it as visited and return. */
546 list_add(&ci->changed_list, parent_changed);
553 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
554 int n_regs = env->co->cls->n_regs;
555 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
557 /* Get the costs for giving the node a specific color. */
558 single_color_cost(env, ci, tgt_col, seq);
560 /* Try recoloring the node using the color list. */
561 res = recolor(env, irn, seq, parent_changed, depth);
566 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
571 * Examine the costs of the current coloring concerning a MST subtree.
572 * @param ci The subtree root.
573 * @param col The color of @p ci.
574 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
576 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
578 int *front = FRONT_BASE(ci, col);
582 for(i = 0; i < ci->mst_n_childs; ++i) {
583 co2_cloud_irn_t *chld = ci->mst_childs[i];
584 col_t chld_col = front[i];
586 cost += examine_subtree_coloring(chld, chld_col);
587 cost += col != chld_col ? chld->mst_costs : 0;
594 * Determine color badnesses of a node.
595 * Badness means that it is unlikely that the node in question can
596 * obtain a color. The higher the badness, the more unlikely it is that
597 * the node can be assigned that color.
598 * @param ci The node.
599 * @param badness An integer array as long as there are registers.
600 * @note The array <code>badness</code> is not cleared.
602 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
604 co2_t *env = ci->cloud->env;
605 co2_irn_t *ir = &ci->inh;
606 int n_regs = env->n_regs;
607 be_ifg_t *ifg = env->co->cenv->ifg;
608 bitset_t *bs = bitset_alloca(n_regs);
614 admissible_colors(env, &ci->inh, bs);
616 bitset_foreach(bs, elm)
617 badness[elm] = ci->costs;
619 /* Use constrained/fixed interfering neighbors to influence the color badness */
620 it = be_ifg_neighbours_iter_alloca(ifg);
621 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
622 co2_irn_t *ni = get_co2_irn(env, irn);
624 admissible_colors(env, ni, bs);
625 if(bitset_popcnt(bs) == 1) {
626 bitset_pos_t c = bitset_next_set(bs, 0);
627 badness[c] += ci->costs;
631 col_t c = get_col(env, ni->irn);
632 badness[c] += ci->costs;
635 be_ifg_neighbours_break(ifg, it);
639 * Determine the badness of a MST subtree.
640 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
641 * @see node_color_badness() for a definition of badness.
642 * @param ci The root of the subtree.
643 * @param depth Depth for debugging purposes.
645 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
647 co2_t *env = ci->cloud->env;
650 node_color_badness(ci, ci->color_badness);
652 /* Collect the color badness for the whole subtree */
653 for(i = 0; i < ci->mst_n_childs; ++i) {
654 co2_cloud_irn_t *child = ci->mst_childs[i];
655 determine_color_badness(child, depth + 1);
657 for(j = 0; j < env->n_regs; ++j)
658 ci->color_badness[j] += child->color_badness[j];
661 for(j = 0; j < env->n_regs; ++j)
662 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
666 * Unfix all nodes in a MST subtree.
668 static void unfix_subtree(co2_cloud_irn_t *ci)
673 for(i = 0; i < ci->mst_n_childs; ++i)
674 unfix_subtree(ci->mst_childs[i]);
677 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
679 co2_t *env = ci->cloud->env;
680 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
681 int is_root = ci->mst_parent == ci;
682 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
683 int min_badness = INT_MAX;
684 int best_col_costs = INT_MAX;
686 int n_regs = env->n_regs;
687 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
689 struct list_head changed;
692 for(i = 0; i < n_regs; ++i) {
693 int badness = ci->color_badness[i];
696 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
698 min_badness = MIN(min_badness, badness);
701 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
702 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
703 seq[parent_col].costs = min_badness - 1;
705 /* Sort the colors. The will be processed in that ordering. */
706 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
708 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
709 INIT_LIST_HEAD(&changed);
710 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
711 col_t col = seq[i].col;
712 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
714 int subtree_costs, sum_costs;
716 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
719 INIT_LIST_HEAD(&changed);
720 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
722 materialize_coloring(&changed);
729 for(j = 0; j < ci->mst_n_childs; ++j) {
730 co2_cloud_irn_t *child = ci->mst_childs[j];
731 ok = coalesce_top_down(child, j, depth + 1) >= 0;
733 child->inh.fixed = 1;
738 /* If the subtree could not be colored, we have to try another color. */
742 subtree_costs = examine_subtree_coloring(ci, col);
743 sum_costs = subtree_costs + add_cost;
744 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
746 if(sum_costs < best_col_costs) {
748 best_col_costs = sum_costs;
749 ci->col_costs[col] = subtree_costs;
757 int *front = FRONT_BASE(ci->mst_parent, parent_col);
758 front[child_nr] = best_col;
764 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
766 be_ifg_t *ifg = env->co->cenv->ifg;
767 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
774 /* mark the node as visited and add it to the cloud. */
776 list_add(&ci->cloud_list, &cloud->members_head);
778 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
780 /* determine the nodes costs */
781 co_gs_foreach_neighb(a, n) {
783 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
784 if(be_ifg_connected(ifg, a->irn, n->irn))
785 cloud->inevit += n->costs;
788 /* add the node's cost to the total costs of the cloud. */
790 cloud->costs += costs;
791 cloud->n_constr += is_constrained(env, &ci->inh);
792 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
793 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
796 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
797 if(costs >= curr_costs) {
802 /* add all the neighbors of the node to the cloud. */
803 co_gs_foreach_neighb(a, n) {
804 affinity_node_t *an = get_affinity_info(env->co, n->irn);
806 populate_cloud(env, cloud, an, curr_costs);
810 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
812 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
816 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
817 memset(cloud, 0, sizeof(cloud[0]));
818 INIT_LIST_HEAD(&cloud->members_head);
819 INIT_LIST_HEAD(&cloud->list);
820 list_add(&cloud->list, &env->cloud_head);
821 cloud->best_costs = INT_MAX;
824 populate_cloud(env, cloud, a, 0);
825 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
827 /* Also allocate space for the node sequence and compute that sequence. */
828 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
831 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
833 cloud->seq[i++] = ci;
835 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
840 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
842 ir_node *irn = ci->inh.irn;
843 int *front = FRONT_BASE(ci, col);
845 struct list_head changed;
847 INIT_LIST_HEAD(&changed);
849 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
850 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
851 // assert(ok && "Color changing may not fail while committing the coloring");
852 materialize_coloring(&changed);
854 for(i = 0; i < ci->mst_n_childs; ++i) {
855 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
859 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
861 while(ci != ci->mst_parent)
867 static void process_cloud(co2_cloud_t *cloud)
869 co2_t *env = cloud->env;
870 int n_regs = env->n_regs;
872 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
879 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
881 /* Collect all edges in the cloud on an obstack and sort the increasingly */
882 obstack_init(&cloud->obst);
883 for(i = 0; i < cloud->n_memb; ++i) {
884 co2_cloud_irn_t *ci = cloud->seq[i];
887 co_gs_foreach_neighb(ci->inh.aff, n) {
888 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
889 if(ci->index < ni->index) {
894 obstack_grow(&cloud->obst, &e, sizeof(e));
899 edges = obstack_finish(&cloud->obst);
900 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
902 /* Compute the maximum spanning tree using Kruskal/Union-Find */
903 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
904 for(i = 0; i < n_edges; ++i) {
905 edge_t *e = &edges[i];
906 co2_cloud_irn_t *rs = find_mst_root(e->src);
907 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
909 /* if the union/find roots are different */
911 int si = e->src->index;
912 int ti = e->tgt->index;
916 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
918 /* this edge is in the MST, so set it in the bitset. */
919 mst_edges[si * cloud->n_memb + ti] = e->costs;
920 mst_edges[ti * cloud->n_memb + si] = e->costs;
923 obstack_free(&cloud->obst, edges);
925 cloud->master->mst_parent = cloud->master;
926 cloud->mst_root = cloud->master;
927 q = new_pdeq1(cloud->master);
928 while(!pdeq_empty(q)) {
929 co2_cloud_irn_t *ci = pdeq_getl(q);
930 int ofs = ci->index * cloud->n_memb;
931 int end = ofs + cloud->n_memb;
934 ci->mst_n_childs = 0;
935 for(i = ofs; i < end; ++i) {
936 if(mst_edges[i] != 0) {
938 co2_cloud_irn_t *child = cloud->seq[i - ofs];
940 /* put the child to the worklist */
943 /* make ci the parent of the child and add the child to the children array of the parent */
944 child->mst_parent = ci;
945 child->mst_costs = mst_edges[i];
947 obstack_ptr_grow(&cloud->obst, child);
949 mst_edges[other * cloud->n_memb + ci->index] = 0;
954 obstack_ptr_grow(&cloud->obst, NULL);
955 ci->mst_childs = obstack_finish(&cloud->obst);
961 DBG((env->dbg, LEVEL_3, "mst:\n"));
962 for(i = 0; i < cloud->n_memb; ++i) {
963 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
964 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
967 for(i = 0; i < cloud->n_memb; ++i) {
968 co2_cloud_irn_t *ci = cloud->seq[i];
969 int n_childs = ci->mst_n_childs;
972 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
973 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
974 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
975 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
976 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
977 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
978 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
979 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
981 for(j = 0; j < env->n_regs; j++)
982 ci->col_costs[j] = INT_MAX;
986 determine_color_badness(cloud->mst_root, 0);
987 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
988 unfix_subtree(cloud->mst_root);
989 apply_coloring(cloud->mst_root, best_col, 0);
991 /* The coloring should represent the one with the best costs. */
992 //materialize_coloring(&changed);
993 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
994 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
996 /* Fix all nodes in the cloud. */
997 for(i = 0; i < cloud->n_memb; ++i)
998 cloud->seq[i]->inh.fixed = 1;
1000 /* Free all space used while optimizing this cloud. */
1001 obstack_free(&cloud->obst, NULL);
1004 static int cloud_costs(co2_cloud_t *cloud)
1009 for(i = 0; i < cloud->n_memb; ++i) {
1010 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1011 col_t col = get_col(cloud->env, ci->irn);
1012 co_gs_foreach_neighb(ci->aff, n) {
1013 col_t n_col = get_col(cloud->env, n->irn);
1014 costs += col != n_col ? n->costs : 0;
1021 static void process(co2_t *env)
1025 co2_cloud_t **clouds;
1030 int final_costs = 0;
1033 co_gs_foreach_aff_node(env->co, a) {
1034 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1043 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1044 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1046 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1048 for(i = 0; i < n_clouds; ++i) {
1049 init_costs += cloud_costs(clouds[i]);
1051 /* Process the cloud. */
1052 process_cloud(clouds[i]);
1054 all_costs += clouds[i]->costs;
1055 final_costs += cloud_costs(clouds[i]);
1057 /* Dump the IFG if the user demanded it. */
1058 if (dump_flags & DUMP_CLOUD) {
1062 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1063 f = fopen(buf, "wt");
1065 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1071 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1076 static void writeback_colors(co2_t *env)
1078 const arch_env_t *aenv = env->co->aenv;
1081 for(irn = env->touched; irn; irn = irn->touched_next) {
1082 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1083 arch_set_irn_register(aenv, irn->irn, reg);
1089 ___ _____ ____ ____ ___ _____ ____ _
1090 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1091 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1092 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1093 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1097 static const char *get_dot_color_name(int col)
1099 static const char *names[] = {
1133 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1136 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1138 arch_register_req_t req;
1140 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1141 if(arch_register_req_is(&req, limited))
1153 static void ifg_dump_graph_attr(FILE *f, void *self)
1155 fprintf(f, "overlay=false");
1158 static int ifg_is_dump_node(void *self, ir_node *irn)
1161 return !arch_irn_is(env->co->aenv, irn, ignore);
1164 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1167 co2_irn_t *ci = get_co2_irn(env, irn);
1173 co2_cloud_irn_t *cci = (void *) ci;
1174 if (cci->cloud && cci->cloud->mst_root == cci)
1177 if(cci->cloud && cci->cloud->mst_root)
1178 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1181 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1182 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1185 static void ifg_dump_at_end(FILE *file, void *self)
1190 co_gs_foreach_aff_node(env->co, a) {
1191 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1192 int idx = get_irn_idx(a->irn);
1195 if(ai->mst_parent != ai)
1196 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1198 co_gs_foreach_neighb(a, n) {
1199 int nidx = get_irn_idx(n->irn);
1200 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1203 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1204 const char *arr = "arrowhead=dot arrowtail=dot";
1206 if(ci->mst_parent == ai)
1207 arr = "arrowtail=normal";
1208 else if(ai->mst_parent == ci)
1209 arr = "arrowhead=normal";
1211 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1218 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1220 ifg_dump_graph_attr,
1228 int co_solve_heuristic_new(copy_opt_t *co)
1234 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1238 env.n_regs = co->cls->n_regs;
1239 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1240 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1241 bitset_flip_all(env.ignore_regs);
1242 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1243 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1244 INIT_LIST_HEAD(&env.cloud_head);
1246 if(dump_flags & DUMP_BEFORE) {
1247 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1248 f = fopen(buf, "wt");
1250 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1257 if(dump_flags & DUMP_AFTER) {
1258 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1259 f = fopen(buf, "wt");
1261 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1266 writeback_colors(&env);
1267 phase_free(&env.ph);