2 * More experiments on coalescing.
3 * @author Sebastian Hack
10 #include <libcore/lc_opts.h>
11 #include <libcore/lc_opts_enum.h>
19 #include "raw_bitset.h"
22 #include "bitfiddle.h"
24 #include "irphase_t.h"
25 #include "irgraph_t.h"
33 #include "becopyopt.h"
34 #include "becopyopt_t.h"
35 #include "bechordal_t.h"
40 #define DUMP_ALL 2 * DUMP_CLOUD - 1
42 static unsigned dump_flags = 0;
43 static int subtree_iter = 4;
44 static int max_depth = 20;
45 static double constr_factor = 0.9;
47 /* 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 },
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 cloud", &dump_var),
62 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
63 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
64 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
68 void be_init_copyheur2(void)
70 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
71 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
72 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
73 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
75 lc_opt_add_table(co2_grp, options);
78 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
82 / ___|| |_ __ _ _ __| |_
83 \___ \| __/ _` | '__| __|
84 ___) | || (_| | | | |_
85 |____/ \__\__,_|_| \__|
89 #define INFEASIBLE(cost) ((cost) == INT_MAX)
91 static be_ifg_dump_dot_cb_t ifg_dot_cb;
93 typedef unsigned col_t;
95 typedef struct _co2_irn_t co2_irn_t;
96 typedef struct _co2_cloud_t co2_cloud_t;
97 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
107 bitset_t *ignore_regs;
111 struct list_head cloud_head;
112 DEBUG_ONLY(firm_dbg_module_t *dbg;)
117 affinity_node_t *aff;
118 co2_irn_t *touched_next;
121 int last_color_change;
124 unsigned tmp_fixed : 1;
125 unsigned is_constrained : 1;
126 struct list_head changed_list;
129 struct _co2_cloud_irn_t {
130 struct _co2_irn_t inh;
134 co2_cloud_irn_t *mst_parent;
137 co2_cloud_irn_t **mst_childs;
142 col_cost_pair_t *tmp_coloring;
143 struct list_head cloud_list;
144 struct list_head mst_list;
147 struct _co2_cloud_t {
159 co2_cloud_irn_t *master;
160 co2_cloud_irn_t *mst_root;
161 co2_cloud_irn_t **seq;
162 struct list_head members_head;
163 struct list_head list;
167 co2_cloud_irn_t *src, *tgt;
171 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
173 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
174 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
176 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
178 co2_t *env = (co2_t *) ph;
179 affinity_node_t *a = get_affinity_info(env->co, irn);
180 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
181 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
184 INIT_LIST_HEAD(&ci->changed_list);
185 ci->touched_next = env->touched;
186 ci->orig_col = get_irn_col(env->co, irn);
192 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
193 INIT_LIST_HEAD(&cci->cloud_list);
194 cci->mst_parent = cci;
200 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
202 static int cmp_clouds_gt(const void *a, const void *b)
204 const co2_cloud_t * const *p = a;
205 const co2_cloud_t * const *q = b;
206 double c = CLOUD_WEIGHT(*p);
207 double d = CLOUD_WEIGHT(*q);
208 return QSORT_CMP(d, c);
212 * An order on color/costs pairs.
213 * If the costs are equal, we use the color as a kind of normalization.
215 static int col_cost_pair_lt(const void *a, const void *b)
217 const col_cost_pair_t *p = a;
218 const col_cost_pair_t *q = b;
221 return QSORT_CMP(c, d);
224 int cmp_edges(const void *a, const void *b)
228 return QSORT_CMP(q->costs, p->costs);
231 static col_t get_col(co2_t *env, ir_node *irn)
233 co2_irn_t *ci = get_co2_irn(env, irn);
234 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
237 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
239 co2_irn_t *ci = get_co2_irn(env, irn);
240 return ci->fixed || ci->tmp_fixed;
243 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
245 if(ci->adm_cache == NULL) {
246 const arch_register_req_t *req;
247 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
248 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
250 if(arch_register_req_is(req, limited)) {
254 for(i = 0; i < n; ++i) {
255 if(rbitset_is_set(req->limited, i))
256 bitset_set(ci->adm_cache, i);
258 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 const arch_register_req_t *req;
291 req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
293 if(arch_register_req_is(req, limited)) {
294 unsigned n_regs = env->co->cls->n_regs;
295 unsigned n_constr = 0;
298 n_constr = rbitset_popcnt(req->limited, n_regs);
299 for(i = 0; i < n_regs; ++i) {
300 if(rbitset_is_set(req->limited, i)) {
301 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
308 * Determine costs which shall indicate how cheap/expensive it is to try
309 * to assign a node some color.
310 * The costs are computed for all colors. INT_MAX means that it is impossible
311 * to give the node that specific color.
313 * @param env The co2 this pointer.
314 * @param irn The node.
315 * @param col_costs An array of colors x costs where the costs are written to.
317 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
319 ir_node *irn = ci->irn;
320 be_ifg_t *ifg = env->co->cenv->ifg;
321 int n_regs = env->co->cls->n_regs;
322 bitset_t *forb = bitset_alloca(n_regs);
323 affinity_node_t *a = ci->aff;
330 /* Put all forbidden colors into the aux bitset. */
331 admissible_colors(env, ci, forb);
332 bitset_flip_all(forb);
334 for(i = 0; i < n_regs; ++i) {
335 col_costs[i].col = i;
336 col_costs[i].costs = 0;
342 co_gs_foreach_neighb(a, n) {
343 if(color_is_fix(env, n->irn)) {
344 col_t col = get_col(env, n->irn);
345 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
348 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
352 it = be_ifg_neighbours_iter_alloca(ifg);
353 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
354 col_t col = get_col(env, pos);
355 if(color_is_fix(env, pos)) {
356 col_costs[col].costs = INT_MAX;
359 incur_constraint_costs(env, pos, col_costs, INT_MAX);
360 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
363 be_ifg_neighbours_break(ifg, it);
365 /* Set the costs to infinity for each color which is not allowed at this node. */
366 bitset_foreach(forb, elm) {
367 col_costs[elm].costs = INT_MAX;
372 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
374 int n_regs = env->co->cls->n_regs;
377 for(i = 0; i < n_regs; ++i) {
379 seq[i].costs = INT_MAX;
382 assert(is_color_admissible(env, ci, col));
388 static void reject_coloring(struct list_head *h)
392 list_for_each_entry(co2_irn_t, pos, h, changed_list)
396 static void materialize_coloring(struct list_head *h)
400 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
401 pos->orig_col = pos->tmp_col;
406 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
408 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
410 int n_regs = env->co->cls->n_regs;
411 be_ifg_t *ifg = env->co->cenv->ifg;
412 co2_irn_t *ci = get_co2_irn(env, irn);
417 if(depth >= max_depth)
420 for(i = 0; i < n_regs; ++i) {
421 col_t tgt_col = col_list[i].col;
422 unsigned costs = col_list[i].costs;
425 struct list_head changed;
429 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
431 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
432 if(INFEASIBLE(costs)) {
433 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
438 /* Set the new color of the node and mark the node as temporarily fixed. */
439 ci->tmp_col = tgt_col;
443 If that color has costs > 0, there's at least one neighbor having that color,
444 so we will try to change the neighbors' colors, too.
446 INIT_LIST_HEAD(&changed);
447 list_add(&ci->changed_list, &changed);
449 it = be_ifg_neighbours_iter_alloca(ifg);
450 be_ifg_foreach_neighbour(ifg, it, irn, n) {
452 /* try to re-color the neighbor if it has the target color. */
453 if(get_col(env, n) == tgt_col) {
454 struct list_head tmp;
457 Try to change the color of the neighbor and record all nodes which
458 get changed in the tmp list. Add this list to the "changed" list for
459 that color. If we did not succeed to change the color of the neighbor,
460 we bail out and try the next color.
462 INIT_LIST_HEAD(&tmp);
463 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
464 list_splice(&tmp, &changed);
469 be_ifg_neighbours_break(ifg, it);
472 We managed to assign the target color to all neighbors, so from the perspective
473 of the current node, every thing was ok and we can return safely.
476 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
477 list_splice(&changed, parent_changed);
483 If not, that color did not succeed and we unfix all nodes we touched
484 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
487 reject_coloring(&changed);
493 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
495 co2_irn_t *ci = get_co2_irn(env, irn);
497 col_t col = get_col(env, irn);
499 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
501 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
508 list_add(&ci->changed_list, parent_changed);
512 /* The node has the color it should not have _and_ has not been visited yet. */
513 if(!color_is_fix(env, irn)) {
514 int n_regs = env->co->cls->n_regs;
515 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
517 /* Get the costs for giving the node a specific color. */
518 determine_color_costs(env, ci, csts);
520 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
521 csts[not_col].costs = INT_MAX;
523 /* sort the colors according costs, cheapest first. */
524 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
526 /* Try recoloring the node using the color list. */
527 res = recolor(env, irn, csts, parent_changed, depth);
530 /* If we came here, everything went ok. */
534 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
536 co2_irn_t *ci = get_co2_irn(env, irn);
537 col_t col = get_col(env, irn);
540 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
542 /* the node has the wanted color. That's fine, mark it as visited and return. */
547 list_add(&ci->changed_list, parent_changed);
554 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
555 int n_regs = env->co->cls->n_regs;
556 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
558 /* Get the costs for giving the node a specific color. */
559 single_color_cost(env, ci, tgt_col, seq);
561 /* Try recoloring the node using the color list. */
562 res = recolor(env, irn, seq, parent_changed, depth);
567 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
572 * Examine the costs of the current coloring concerning a MST subtree.
573 * @param ci The subtree root.
574 * @param col The color of @p ci.
575 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
577 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
579 int *front = FRONT_BASE(ci, col);
583 for(i = 0; i < ci->mst_n_childs; ++i) {
584 co2_cloud_irn_t *chld = ci->mst_childs[i];
585 col_t chld_col = front[i];
587 cost += examine_subtree_coloring(chld, chld_col);
588 cost += col != chld_col ? chld->mst_costs : 0;
595 * Determine color badnesses of a node.
596 * Badness means that it is unlikely that the node in question can
597 * obtain a color. The higher the badness, the more unlikely it is that
598 * the node can be assigned that color.
599 * @param ci The node.
600 * @param badness An integer array as long as there are registers.
601 * @note The array <code>badness</code> is not cleared.
603 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
605 co2_t *env = ci->cloud->env;
606 co2_irn_t *ir = &ci->inh;
607 int n_regs = env->n_regs;
608 be_ifg_t *ifg = env->co->cenv->ifg;
609 bitset_t *bs = bitset_alloca(n_regs);
615 admissible_colors(env, &ci->inh, bs);
617 bitset_foreach(bs, elm)
618 badness[elm] = ci->costs;
620 /* Use constrained/fixed interfering neighbors to influence the color badness */
621 it = be_ifg_neighbours_iter_alloca(ifg);
622 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
623 co2_irn_t *ni = get_co2_irn(env, irn);
625 admissible_colors(env, ni, bs);
626 if(bitset_popcnt(bs) == 1) {
627 bitset_pos_t c = bitset_next_set(bs, 0);
628 badness[c] += ci->costs;
632 col_t c = get_col(env, ni->irn);
633 badness[c] += ci->costs;
636 be_ifg_neighbours_break(ifg, it);
640 * Determine the badness of a MST subtree.
641 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
642 * @see node_color_badness() for a definition of badness.
643 * @param ci The root of the subtree.
644 * @param depth Depth for debugging purposes.
646 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
648 co2_t *env = ci->cloud->env;
651 node_color_badness(ci, ci->color_badness);
653 /* Collect the color badness for the whole subtree */
654 for(i = 0; i < ci->mst_n_childs; ++i) {
655 co2_cloud_irn_t *child = ci->mst_childs[i];
656 determine_color_badness(child, depth + 1);
658 for(j = 0; j < env->n_regs; ++j)
659 ci->color_badness[j] += child->color_badness[j];
662 for(j = 0; j < env->n_regs; ++j)
663 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
667 * Unfix all nodes in a MST subtree.
669 static void unfix_subtree(co2_cloud_irn_t *ci)
674 for(i = 0; i < ci->mst_n_childs; ++i)
675 unfix_subtree(ci->mst_childs[i]);
678 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
680 co2_t *env = ci->cloud->env;
681 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
682 int is_root = ci->mst_parent == ci;
683 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
684 int min_badness = INT_MAX;
685 int best_col_costs = INT_MAX;
687 int n_regs = env->n_regs;
688 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
690 struct list_head changed;
693 for(i = 0; i < n_regs; ++i) {
694 int badness = ci->color_badness[i];
697 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
699 min_badness = MIN(min_badness, badness);
702 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
703 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
704 seq[parent_col].costs = min_badness - 1;
706 /* Sort the colors. The will be processed in that ordering. */
707 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
709 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
710 INIT_LIST_HEAD(&changed);
711 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
712 col_t col = seq[i].col;
713 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
715 int subtree_costs, sum_costs;
717 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
720 INIT_LIST_HEAD(&changed);
721 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
723 materialize_coloring(&changed);
730 for(j = 0; j < ci->mst_n_childs; ++j) {
731 co2_cloud_irn_t *child = ci->mst_childs[j];
732 ok = coalesce_top_down(child, j, depth + 1) >= 0;
734 child->inh.fixed = 1;
739 /* If the subtree could not be colored, we have to try another color. */
743 subtree_costs = examine_subtree_coloring(ci, col);
744 sum_costs = subtree_costs + add_cost;
745 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
747 if(sum_costs < best_col_costs) {
749 best_col_costs = sum_costs;
750 ci->col_costs[col] = subtree_costs;
758 int *front = FRONT_BASE(ci->mst_parent, parent_col);
759 front[child_nr] = best_col;
765 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
767 be_ifg_t *ifg = env->co->cenv->ifg;
768 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
775 /* mark the node as visited and add it to the cloud. */
777 list_add(&ci->cloud_list, &cloud->members_head);
779 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
781 /* determine the nodes costs */
782 co_gs_foreach_neighb(a, n) {
784 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
785 if(be_ifg_connected(ifg, a->irn, n->irn))
786 cloud->inevit += n->costs;
789 /* add the node's cost to the total costs of the cloud. */
791 cloud->costs += costs;
792 cloud->n_constr += is_constrained(env, &ci->inh);
793 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
794 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
797 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
798 if(costs >= curr_costs) {
803 /* add all the neighbors of the node to the cloud. */
804 co_gs_foreach_neighb(a, n) {
805 affinity_node_t *an = get_affinity_info(env->co, n->irn);
807 populate_cloud(env, cloud, an, curr_costs);
811 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
813 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
817 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
818 memset(cloud, 0, sizeof(cloud[0]));
819 INIT_LIST_HEAD(&cloud->members_head);
820 INIT_LIST_HEAD(&cloud->list);
821 list_add(&cloud->list, &env->cloud_head);
822 cloud->best_costs = INT_MAX;
825 populate_cloud(env, cloud, a, 0);
826 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
828 /* Also allocate space for the node sequence and compute that sequence. */
829 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
832 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
834 cloud->seq[i++] = ci;
836 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
841 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
843 ir_node *irn = ci->inh.irn;
844 int *front = FRONT_BASE(ci, col);
846 struct list_head changed;
848 INIT_LIST_HEAD(&changed);
850 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
851 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
852 // assert(ok && "Color changing may not fail while committing the coloring");
853 materialize_coloring(&changed);
855 for(i = 0; i < ci->mst_n_childs; ++i) {
856 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
860 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
862 while(ci != ci->mst_parent)
868 static void process_cloud(co2_cloud_t *cloud)
870 co2_t *env = cloud->env;
871 int n_regs = env->n_regs;
873 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
880 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
882 /* Collect all edges in the cloud on an obstack and sort the increasingly */
883 obstack_init(&cloud->obst);
884 for(i = 0; i < cloud->n_memb; ++i) {
885 co2_cloud_irn_t *ci = cloud->seq[i];
888 co_gs_foreach_neighb(ci->inh.aff, n) {
889 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
890 if(ci->index < ni->index) {
895 obstack_grow(&cloud->obst, &e, sizeof(e));
900 edges = obstack_finish(&cloud->obst);
901 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
903 /* Compute the maximum spanning tree using Kruskal/Union-Find */
904 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
905 for(i = 0; i < n_edges; ++i) {
906 edge_t *e = &edges[i];
907 co2_cloud_irn_t *rs = find_mst_root(e->src);
908 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
910 /* if the union/find roots are different */
912 int si = e->src->index;
913 int ti = e->tgt->index;
917 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
919 /* this edge is in the MST, so set it in the bitset. */
920 mst_edges[si * cloud->n_memb + ti] = e->costs;
921 mst_edges[ti * cloud->n_memb + si] = e->costs;
924 obstack_free(&cloud->obst, edges);
926 cloud->master->mst_parent = cloud->master;
927 cloud->mst_root = cloud->master;
928 q = new_pdeq1(cloud->master);
929 while(!pdeq_empty(q)) {
930 co2_cloud_irn_t *ci = pdeq_getl(q);
931 int ofs = ci->index * cloud->n_memb;
932 int end = ofs + cloud->n_memb;
935 ci->mst_n_childs = 0;
936 for(i = ofs; i < end; ++i) {
937 if(mst_edges[i] != 0) {
939 co2_cloud_irn_t *child = cloud->seq[i - ofs];
941 /* put the child to the worklist */
944 /* make ci the parent of the child and add the child to the children array of the parent */
945 child->mst_parent = ci;
946 child->mst_costs = mst_edges[i];
948 obstack_ptr_grow(&cloud->obst, child);
950 mst_edges[other * cloud->n_memb + ci->index] = 0;
955 obstack_ptr_grow(&cloud->obst, NULL);
956 ci->mst_childs = obstack_finish(&cloud->obst);
962 DBG((env->dbg, LEVEL_3, "mst:\n"));
963 for(i = 0; i < cloud->n_memb; ++i) {
964 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
965 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
968 for(i = 0; i < cloud->n_memb; ++i) {
969 co2_cloud_irn_t *ci = cloud->seq[i];
970 int n_childs = ci->mst_n_childs;
973 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
974 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
975 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
976 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
977 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
978 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
979 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
980 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
982 for(j = 0; j < env->n_regs; j++)
983 ci->col_costs[j] = INT_MAX;
987 determine_color_badness(cloud->mst_root, 0);
988 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
989 unfix_subtree(cloud->mst_root);
990 apply_coloring(cloud->mst_root, best_col, 0);
992 /* The coloring should represent the one with the best costs. */
993 //materialize_coloring(&changed);
994 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
995 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
997 /* Fix all nodes in the cloud. */
998 for(i = 0; i < cloud->n_memb; ++i)
999 cloud->seq[i]->inh.fixed = 1;
1001 /* Free all space used while optimizing this cloud. */
1002 obstack_free(&cloud->obst, NULL);
1005 static int cloud_costs(co2_cloud_t *cloud)
1010 for(i = 0; i < cloud->n_memb; ++i) {
1011 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1012 col_t col = get_col(cloud->env, ci->irn);
1013 co_gs_foreach_neighb(ci->aff, n) {
1014 col_t n_col = get_col(cloud->env, n->irn);
1015 costs += col != n_col ? n->costs : 0;
1022 static void process(co2_t *env)
1026 co2_cloud_t **clouds;
1031 int final_costs = 0;
1034 co_gs_foreach_aff_node(env->co, a) {
1035 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1044 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1045 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1047 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1049 for(i = 0; i < n_clouds; ++i) {
1050 init_costs += cloud_costs(clouds[i]);
1052 /* Process the cloud. */
1053 process_cloud(clouds[i]);
1055 all_costs += clouds[i]->costs;
1056 final_costs += cloud_costs(clouds[i]);
1058 /* Dump the IFG if the user demanded it. */
1059 if (dump_flags & DUMP_CLOUD) {
1063 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1064 f = fopen(buf, "wt");
1066 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1072 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1077 static void writeback_colors(co2_t *env)
1079 const arch_env_t *aenv = env->co->aenv;
1082 for(irn = env->touched; irn; irn = irn->touched_next) {
1083 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1084 arch_set_irn_register(aenv, irn->irn, reg);
1090 ___ _____ ____ ____ ___ _____ ____ _
1091 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1092 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1093 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1094 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1098 static const char *get_dot_color_name(int col)
1100 static const char *names[] = {
1134 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1137 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1139 const arch_register_req_t *req;
1141 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
1142 if(arch_register_req_is(req, limited))
1154 static void ifg_dump_graph_attr(FILE *f, void *self)
1156 fprintf(f, "overlay=false");
1159 static int ifg_is_dump_node(void *self, ir_node *irn)
1162 return !arch_irn_is(env->co->aenv, irn, ignore);
1165 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1168 co2_irn_t *ci = get_co2_irn(env, irn);
1174 co2_cloud_irn_t *cci = (void *) ci;
1175 if (cci->cloud && cci->cloud->mst_root == cci)
1178 if(cci->cloud && cci->cloud->mst_root)
1179 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1182 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1183 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1186 static void ifg_dump_at_end(FILE *file, void *self)
1191 co_gs_foreach_aff_node(env->co, a) {
1192 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1193 int idx = get_irn_idx(a->irn);
1196 if(ai->mst_parent != ai)
1197 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1199 co_gs_foreach_neighb(a, n) {
1200 int nidx = get_irn_idx(n->irn);
1201 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1204 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1205 const char *arr = "arrowhead=dot arrowtail=dot";
1207 if(ci->mst_parent == ai)
1208 arr = "arrowtail=normal";
1209 else if(ai->mst_parent == ci)
1210 arr = "arrowhead=normal";
1212 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1219 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1221 ifg_dump_graph_attr,
1229 int co_solve_heuristic_new(copy_opt_t *co)
1235 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1239 env.n_regs = co->cls->n_regs;
1240 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1241 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1242 bitset_flip_all(env.ignore_regs);
1243 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1244 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1245 INIT_LIST_HEAD(&env.cloud_head);
1247 if(dump_flags & DUMP_BEFORE) {
1248 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1249 f = fopen(buf, "wt");
1251 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1258 if(dump_flags & DUMP_AFTER) {
1259 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1260 f = fopen(buf, "wt");
1262 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1267 writeback_colors(&env);
1268 phase_free(&env.ph);