3 * More experiments on coalescing.
4 * @author Sebastian Hack
12 #include <libcore/lc_opts.h>
13 #include <libcore/lc_opts_enum.h>
23 #include "bitfiddle.h"
25 #include "irphase_t.h"
26 #include "irgraph_t.h"
34 #include "becopyopt.h"
35 #include "becopyopt_t.h"
36 #include "bechordal_t.h"
41 #define DUMP_ALL 2 * DUMP_CLOUD - 1
43 static unsigned dump_flags = 0;
44 static int subtree_iter = 4;
45 static int max_depth = 20;
46 static double constr_factor = 0.9;
48 /* Options using libcore */
49 static const lc_opt_enum_mask_items_t dump_items[] = {
50 { "before", DUMP_BEFORE },
51 { "after", DUMP_AFTER },
52 { "cloud", DUMP_CLOUD },
57 static lc_opt_enum_mask_var_t dump_var = {
58 &dump_flags, dump_items
61 static const lc_opt_table_entry_t options[] = {
62 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
63 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
64 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
65 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
69 void be_init_copyheur2(void)
71 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
72 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
73 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
74 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
76 lc_opt_add_table(co2_grp, options);
79 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
83 / ___|| |_ __ _ _ __| |_
84 \___ \| __/ _` | '__| __|
85 ___) | || (_| | | | |_
86 |____/ \__\__,_|_| \__|
90 #define INFEASIBLE(cost) ((cost) == INT_MAX)
92 static be_ifg_dump_dot_cb_t ifg_dot_cb;
94 typedef unsigned col_t;
96 typedef struct _co2_irn_t co2_irn_t;
97 typedef struct _co2_cloud_t co2_cloud_t;
98 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
108 bitset_t *ignore_regs;
112 struct list_head cloud_head;
113 DEBUG_ONLY(firm_dbg_module_t *dbg;)
118 affinity_node_t *aff;
119 co2_irn_t *touched_next;
122 int last_color_change;
125 unsigned tmp_fixed : 1;
126 unsigned is_constrained : 1;
127 struct list_head changed_list;
130 struct _co2_cloud_irn_t {
131 struct _co2_irn_t inh;
135 co2_cloud_irn_t *mst_parent;
138 co2_cloud_irn_t **mst_childs;
143 col_cost_pair_t *tmp_coloring;
144 struct list_head cloud_list;
145 struct list_head mst_list;
148 struct _co2_cloud_t {
160 co2_cloud_irn_t *master;
161 co2_cloud_irn_t *mst_root;
162 co2_cloud_irn_t **seq;
163 struct list_head members_head;
164 struct list_head list;
168 co2_cloud_irn_t *src, *tgt;
172 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
174 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
175 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
177 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
179 co2_t *env = (co2_t *) ph;
180 affinity_node_t *a = get_affinity_info(env->co, irn);
181 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
182 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
185 INIT_LIST_HEAD(&ci->changed_list);
186 ci->touched_next = env->touched;
187 ci->orig_col = get_irn_col(env->co, irn);
193 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
194 INIT_LIST_HEAD(&cci->cloud_list);
195 cci->mst_parent = cci;
201 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
203 static int cmp_clouds_gt(const void *a, const void *b)
205 const co2_cloud_t * const *p = a;
206 const co2_cloud_t * const *q = b;
207 double c = CLOUD_WEIGHT(*p);
208 double d = CLOUD_WEIGHT(*q);
209 return QSORT_CMP(d, c);
213 * An order on color/costs pairs.
214 * If the costs are equal, we use the color as a kind of normalization.
216 static int col_cost_pair_lt(const void *a, const void *b)
218 const col_cost_pair_t *p = a;
219 const col_cost_pair_t *q = b;
222 return QSORT_CMP(c, d);
225 int cmp_edges(const void *a, const void *b)
229 return QSORT_CMP(q->costs, p->costs);
232 static col_t get_col(co2_t *env, ir_node *irn)
234 co2_irn_t *ci = get_co2_irn(env, irn);
235 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
238 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
240 co2_irn_t *ci = get_co2_irn(env, irn);
241 return ci->fixed || ci->tmp_fixed;
244 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
247 arch_register_req_t req;
248 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
249 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
250 if(arch_register_req_is(&req, limited)) {
251 req.limited(req.limited_env, ci->adm_cache);
252 ci->is_constrained = 1;
255 bitset_copy(ci->adm_cache, env->ignore_regs);
256 bitset_flip_all(ci->adm_cache);
260 return ci->adm_cache;
263 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
265 bitset_copy(bs, get_adm(env, ci));
269 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
271 bitset_t *bs = get_adm(env, ci);
272 return bitset_is_set(bs, col);
275 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
279 return ci->is_constrained;
282 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
284 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
285 arch_register_req_t req;
287 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
289 if(arch_register_req_is(&req, limited)) {
293 req.limited(req.limited_env, aux);
294 n_constr = bitset_popcnt(aux);
295 bitset_foreach(aux, elm) {
296 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
302 * Determine costs which shall indicate how cheap/expensive it is to try
303 * to assign a node some color.
304 * The costs are computed for all colors. INT_MAX means that it is impossible
305 * to give the node that specific color.
307 * @param env The co2 this pointer.
308 * @param irn The node.
309 * @param col_costs An array of colors x costs where the costs are written to.
311 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
313 ir_node *irn = ci->irn;
314 be_ifg_t *ifg = env->co->cenv->ifg;
315 int n_regs = env->co->cls->n_regs;
316 bitset_t *forb = bitset_alloca(n_regs);
317 affinity_node_t *a = ci->aff;
324 /* Put all forbidden colors into the aux bitset. */
325 admissible_colors(env, ci, forb);
326 bitset_flip_all(forb);
328 for(i = 0; i < n_regs; ++i) {
329 col_costs[i].col = i;
330 col_costs[i].costs = 0;
336 co_gs_foreach_neighb(a, n) {
337 if(color_is_fix(env, n->irn)) {
338 col_t col = get_col(env, n->irn);
339 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
342 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
346 it = be_ifg_neighbours_iter_alloca(ifg);
347 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
348 col_t col = get_col(env, pos);
349 if(color_is_fix(env, pos)) {
350 col_costs[col].costs = INT_MAX;
353 incur_constraint_costs(env, pos, col_costs, INT_MAX);
354 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
357 be_ifg_neighbours_break(ifg, it);
359 /* Set the costs to infinity for each color which is not allowed at this node. */
360 bitset_foreach(forb, elm) {
361 col_costs[elm].costs = INT_MAX;
366 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
368 int n_regs = env->co->cls->n_regs;
371 for(i = 0; i < n_regs; ++i) {
373 seq[i].costs = INT_MAX;
376 assert(is_color_admissible(env, ci, col));
382 static void reject_coloring(struct list_head *h)
386 list_for_each_entry(co2_irn_t, pos, h, changed_list)
390 static void materialize_coloring(struct list_head *h)
394 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
395 pos->orig_col = pos->tmp_col;
400 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
402 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
404 int n_regs = env->co->cls->n_regs;
405 be_ifg_t *ifg = env->co->cenv->ifg;
406 co2_irn_t *ci = get_co2_irn(env, irn);
411 if(depth >= max_depth)
414 for(i = 0; i < n_regs; ++i) {
415 col_t tgt_col = col_list[i].col;
416 unsigned costs = col_list[i].costs;
419 struct list_head changed;
423 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
425 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
426 if(INFEASIBLE(costs)) {
427 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
432 /* Set the new color of the node and mark the node as temporarily fixed. */
433 ci->tmp_col = tgt_col;
437 If that color has costs > 0, there's at least one neighbor having that color,
438 so we will try to change the neighbors' colors, too.
440 INIT_LIST_HEAD(&changed);
441 list_add(&ci->changed_list, &changed);
443 it = be_ifg_neighbours_iter_alloca(ifg);
444 be_ifg_foreach_neighbour(ifg, it, irn, n) {
446 /* try to re-color the neighbor if it has the target color. */
447 if(get_col(env, n) == tgt_col) {
448 struct list_head tmp;
451 Try to change the color of the neighbor and record all nodes which
452 get changed in the tmp list. Add this list to the "changed" list for
453 that color. If we did not succeed to change the color of the neighbor,
454 we bail out and try the next color.
456 INIT_LIST_HEAD(&tmp);
457 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
458 list_splice(&tmp, &changed);
463 be_ifg_neighbours_break(ifg, it);
466 We managed to assign the target color to all neighbors, so from the perspective
467 of the current node, every thing was ok and we can return safely.
470 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
471 list_splice(&changed, parent_changed);
477 If not, that color did not succeed and we unfix all nodes we touched
478 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
481 reject_coloring(&changed);
487 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
489 co2_irn_t *ci = get_co2_irn(env, irn);
491 col_t col = get_col(env, irn);
493 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
495 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
502 list_add(&ci->changed_list, parent_changed);
506 /* The node has the color it should not have _and_ has not been visited yet. */
507 if(!color_is_fix(env, irn)) {
508 int n_regs = env->co->cls->n_regs;
509 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
511 /* Get the costs for giving the node a specific color. */
512 determine_color_costs(env, ci, csts);
514 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
515 csts[not_col].costs = INT_MAX;
517 /* sort the colors according costs, cheapest first. */
518 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
520 /* Try recoloring the node using the color list. */
521 res = recolor(env, irn, csts, parent_changed, depth);
524 /* If we came here, everything went ok. */
528 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
530 co2_irn_t *ci = get_co2_irn(env, irn);
531 col_t col = get_col(env, irn);
534 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
536 /* the node has the wanted color. That's fine, mark it as visited and return. */
541 list_add(&ci->changed_list, parent_changed);
548 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
549 int n_regs = env->co->cls->n_regs;
550 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
552 /* Get the costs for giving the node a specific color. */
553 single_color_cost(env, ci, tgt_col, seq);
555 /* Try recoloring the node using the color list. */
556 res = recolor(env, irn, seq, parent_changed, depth);
561 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 * Examine the costs of the current coloring concerning a MST subtree.
567 * @param ci The subtree root.
568 * @param col The color of @p ci.
569 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
571 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
573 int *front = FRONT_BASE(ci, col);
577 for(i = 0; i < ci->mst_n_childs; ++i) {
578 co2_cloud_irn_t *chld = ci->mst_childs[i];
579 col_t chld_col = front[i];
581 cost += examine_subtree_coloring(chld, chld_col);
582 cost += col != chld_col ? chld->mst_costs : 0;
589 * Determine color badnesses of a node.
590 * Badness means that it is unlikely that the node in question can
591 * obtain a color. The higher the badness, the more unlikely it is that
592 * the node can be assigned that color.
593 * @param ci The node.
594 * @param badness An integer array as long as there are registers.
595 * @note The array <code>badness</code> is not cleared.
597 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
599 co2_t *env = ci->cloud->env;
600 co2_irn_t *ir = &ci->inh;
601 int n_regs = env->n_regs;
602 be_ifg_t *ifg = env->co->cenv->ifg;
603 bitset_t *bs = bitset_alloca(n_regs);
609 admissible_colors(env, &ci->inh, bs);
611 bitset_foreach(bs, elm)
612 badness[elm] = ci->costs;
614 /* Use constrained/fixed interfering neighbors to influence the color badness */
615 it = be_ifg_neighbours_iter_alloca(ifg);
616 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
617 co2_irn_t *ni = get_co2_irn(env, irn);
619 admissible_colors(env, ni, bs);
620 if(bitset_popcnt(bs) == 1) {
621 bitset_pos_t c = bitset_next_set(bs, 0);
622 badness[c] += ci->costs;
626 col_t c = get_col(env, ni->irn);
627 badness[c] += ci->costs;
630 be_ifg_neighbours_break(ifg, it);
634 * Determine the badness of a MST subtree.
635 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
636 * @see node_color_badness() for a definition of badness.
637 * @param ci The root of the subtree.
638 * @param depth Depth for debugging purposes.
640 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
642 co2_t *env = ci->cloud->env;
645 node_color_badness(ci, ci->color_badness);
647 /* Collect the color badness for the whole subtree */
648 for(i = 0; i < ci->mst_n_childs; ++i) {
649 co2_cloud_irn_t *child = ci->mst_childs[i];
650 determine_color_badness(child, depth + 1);
652 for(j = 0; j < env->n_regs; ++j)
653 ci->color_badness[j] += child->color_badness[j];
656 for(j = 0; j < env->n_regs; ++j)
657 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
661 * Unfix all nodes in a MST subtree.
663 static void unfix_subtree(co2_cloud_irn_t *ci)
668 for(i = 0; i < ci->mst_n_childs; ++i)
669 unfix_subtree(ci->mst_childs[i]);
672 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
674 co2_t *env = ci->cloud->env;
675 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
676 int is_root = ci->mst_parent == ci;
677 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
678 int min_badness = INT_MAX;
679 int best_col_costs = INT_MAX;
681 int n_regs = env->n_regs;
682 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
684 struct list_head changed;
687 for(i = 0; i < n_regs; ++i) {
688 int badness = ci->color_badness[i];
691 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
693 min_badness = MIN(min_badness, badness);
696 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
697 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
698 seq[parent_col].costs = min_badness - 1;
700 /* Sort the colors. The will be processed in that ordering. */
701 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
703 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
704 INIT_LIST_HEAD(&changed);
705 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
706 col_t col = seq[i].col;
707 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
709 int subtree_costs, sum_costs;
711 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
714 INIT_LIST_HEAD(&changed);
715 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
717 materialize_coloring(&changed);
724 for(j = 0; j < ci->mst_n_childs; ++j) {
725 co2_cloud_irn_t *child = ci->mst_childs[j];
726 ok = coalesce_top_down(child, j, depth + 1) >= 0;
728 child->inh.fixed = 1;
733 /* If the subtree could not be colored, we have to try another color. */
737 subtree_costs = examine_subtree_coloring(ci, col);
738 sum_costs = subtree_costs + add_cost;
739 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
741 if(sum_costs < best_col_costs) {
743 best_col_costs = sum_costs;
744 ci->col_costs[col] = subtree_costs;
752 int *front = FRONT_BASE(ci->mst_parent, parent_col);
753 front[child_nr] = best_col;
759 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
761 be_ifg_t *ifg = env->co->cenv->ifg;
762 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
769 /* mark the node as visited and add it to the cloud. */
771 list_add(&ci->cloud_list, &cloud->members_head);
773 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
775 /* determine the nodes costs */
776 co_gs_foreach_neighb(a, n) {
778 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
779 if(be_ifg_connected(ifg, a->irn, n->irn))
780 cloud->inevit += n->costs;
783 /* add the node's cost to the total costs of the cloud. */
785 cloud->costs += costs;
786 cloud->n_constr += is_constrained(env, &ci->inh);
787 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
788 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
791 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
792 if(costs >= curr_costs) {
797 /* add all the neighbors of the node to the cloud. */
798 co_gs_foreach_neighb(a, n) {
799 affinity_node_t *an = get_affinity_info(env->co, n->irn);
801 populate_cloud(env, cloud, an, curr_costs);
805 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
807 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
811 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
812 memset(cloud, 0, sizeof(cloud[0]));
813 INIT_LIST_HEAD(&cloud->members_head);
814 INIT_LIST_HEAD(&cloud->list);
815 list_add(&cloud->list, &env->cloud_head);
816 cloud->best_costs = INT_MAX;
819 populate_cloud(env, cloud, a, 0);
820 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
822 /* Also allocate space for the node sequence and compute that sequence. */
823 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
826 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
828 cloud->seq[i++] = ci;
830 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
835 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
837 ir_node *irn = ci->inh.irn;
838 int *front = FRONT_BASE(ci, col);
840 struct list_head changed;
842 INIT_LIST_HEAD(&changed);
844 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
845 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
846 // assert(ok && "Color changing may not fail while committing the coloring");
847 materialize_coloring(&changed);
849 for(i = 0; i < ci->mst_n_childs; ++i) {
850 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
854 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
856 while(ci != ci->mst_parent)
862 static void process_cloud(co2_cloud_t *cloud)
864 co2_t *env = cloud->env;
865 int n_regs = env->n_regs;
867 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
874 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
876 /* Collect all edges in the cloud on an obstack and sort the increasingly */
877 obstack_init(&cloud->obst);
878 for(i = 0; i < cloud->n_memb; ++i) {
879 co2_cloud_irn_t *ci = cloud->seq[i];
882 co_gs_foreach_neighb(ci->inh.aff, n) {
883 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
884 if(ci->index < ni->index) {
889 obstack_grow(&cloud->obst, &e, sizeof(e));
894 edges = obstack_finish(&cloud->obst);
895 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
897 /* Compute the maximum spanning tree using Kruskal/Union-Find */
898 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
899 for(i = 0; i < n_edges; ++i) {
900 edge_t *e = &edges[i];
901 co2_cloud_irn_t *rs = find_mst_root(e->src);
902 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
904 /* if the union/find roots are different */
906 int si = e->src->index;
907 int ti = e->tgt->index;
911 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
913 /* this edge is in the MST, so set it in the bitset. */
914 mst_edges[si * cloud->n_memb + ti] = e->costs;
915 mst_edges[ti * cloud->n_memb + si] = e->costs;
918 obstack_free(&cloud->obst, edges);
920 cloud->master->mst_parent = cloud->master;
921 cloud->mst_root = cloud->master;
922 q = new_pdeq1(cloud->master);
923 while(!pdeq_empty(q)) {
924 co2_cloud_irn_t *ci = pdeq_getl(q);
925 int ofs = ci->index * cloud->n_memb;
926 int end = ofs + cloud->n_memb;
929 ci->mst_n_childs = 0;
930 for(i = ofs; i < end; ++i) {
931 if(mst_edges[i] != 0) {
933 co2_cloud_irn_t *child = cloud->seq[i - ofs];
935 /* put the child to the worklist */
938 /* make ci the parent of the child and add the child to the children array of the parent */
939 child->mst_parent = ci;
940 child->mst_costs = mst_edges[i];
942 obstack_ptr_grow(&cloud->obst, child);
944 mst_edges[other * cloud->n_memb + ci->index] = 0;
949 obstack_ptr_grow(&cloud->obst, NULL);
950 ci->mst_childs = obstack_finish(&cloud->obst);
956 DBG((env->dbg, LEVEL_3, "mst:\n"));
957 for(i = 0; i < cloud->n_memb; ++i) {
958 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
959 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
962 for(i = 0; i < cloud->n_memb; ++i) {
963 co2_cloud_irn_t *ci = cloud->seq[i];
964 int n_childs = ci->mst_n_childs;
967 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
968 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
969 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
970 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
971 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
972 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
973 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
974 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
976 for(j = 0; j < env->n_regs; j++)
977 ci->col_costs[j] = INT_MAX;
981 determine_color_badness(cloud->mst_root, 0);
982 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
983 unfix_subtree(cloud->mst_root);
984 apply_coloring(cloud->mst_root, best_col, 0);
986 /* The coloring should represent the one with the best costs. */
987 //materialize_coloring(&changed);
988 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
989 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
991 /* Fix all nodes in the cloud. */
992 for(i = 0; i < cloud->n_memb; ++i)
993 cloud->seq[i]->inh.fixed = 1;
995 /* Free all space used while optimizing this cloud. */
996 obstack_free(&cloud->obst, NULL);
999 static int cloud_costs(co2_cloud_t *cloud)
1004 for(i = 0; i < cloud->n_memb; ++i) {
1005 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1006 col_t col = get_col(cloud->env, ci->irn);
1007 co_gs_foreach_neighb(ci->aff, n) {
1008 col_t n_col = get_col(cloud->env, n->irn);
1009 costs += col != n_col ? n->costs : 0;
1016 static void process(co2_t *env)
1020 co2_cloud_t **clouds;
1025 int final_costs = 0;
1028 co_gs_foreach_aff_node(env->co, a) {
1029 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1038 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1039 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1041 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1043 for(i = 0; i < n_clouds; ++i) {
1044 init_costs += cloud_costs(clouds[i]);
1046 /* Process the cloud. */
1047 process_cloud(clouds[i]);
1049 all_costs += clouds[i]->costs;
1050 final_costs += cloud_costs(clouds[i]);
1052 /* Dump the IFG if the user demanded it. */
1053 if (dump_flags & DUMP_CLOUD) {
1057 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1058 f = fopen(buf, "wt");
1060 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1066 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1071 static void writeback_colors(co2_t *env)
1073 const arch_env_t *aenv = env->co->aenv;
1076 for(irn = env->touched; irn; irn = irn->touched_next) {
1077 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1078 arch_set_irn_register(aenv, irn->irn, reg);
1084 ___ _____ ____ ____ ___ _____ ____ _
1085 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1086 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1087 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1088 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1092 static const char *get_dot_color_name(int col)
1094 static const char *names[] = {
1128 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1131 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1133 arch_register_req_t req;
1135 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1136 if(arch_register_req_is(&req, limited))
1148 static void ifg_dump_graph_attr(FILE *f, void *self)
1150 fprintf(f, "overlay=false");
1153 static int ifg_is_dump_node(void *self, ir_node *irn)
1156 return !arch_irn_is(env->co->aenv, irn, ignore);
1159 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1162 co2_irn_t *ci = get_co2_irn(env, irn);
1168 co2_cloud_irn_t *cci = (void *) ci;
1169 if (cci->cloud && cci->cloud->mst_root == cci)
1172 if(cci->cloud && cci->cloud->mst_root)
1173 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1176 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1177 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1180 static void ifg_dump_at_end(FILE *file, void *self)
1185 co_gs_foreach_aff_node(env->co, a) {
1186 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1187 int idx = get_irn_idx(a->irn);
1190 if(ai->mst_parent != ai)
1191 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1193 co_gs_foreach_neighb(a, n) {
1194 int nidx = get_irn_idx(n->irn);
1195 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1198 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1199 const char *arr = "arrowhead=dot arrowtail=dot";
1201 if(ci->mst_parent == ai)
1202 arr = "arrowtail=normal";
1203 else if(ai->mst_parent == ci)
1204 arr = "arrowhead=normal";
1206 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1213 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1215 ifg_dump_graph_attr,
1223 int co_solve_heuristic_new(copy_opt_t *co)
1229 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1233 env.n_regs = co->cls->n_regs;
1234 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1235 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1236 bitset_flip_all(env.ignore_regs);
1237 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1238 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1239 INIT_LIST_HEAD(&env.cloud_head);
1241 if(dump_flags & DUMP_BEFORE) {
1242 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1243 f = fopen(buf, "wt");
1245 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1252 if(dump_flags & DUMP_AFTER) {
1253 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1254 f = fopen(buf, "wt");
1256 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1261 writeback_colors(&env);
1262 phase_free(&env.ph);