3 * More experiments on coalescing.
4 * @author Sebastian Hack
13 #include <libcore/lc_opts.h>
14 #include <libcore/lc_opts_enum.h>
15 #endif /* WITH_LIBCORE */
25 #include "bitfiddle.h"
27 #include "irphase_t.h"
28 #include "irgraph_t.h"
35 #include "becopyopt.h"
36 #include "becopyopt_t.h"
37 #include "bechordal_t.h"
42 #define DUMP_ALL 2 * DUMP_CLOUD - 1
44 static int dump_flags = 0;
45 static int subtree_iter = 4;
46 static int max_depth = 20;
47 static double constr_factor = 0.9;
49 /* Options using libcore */
52 static const lc_opt_enum_mask_items_t dump_items[] = {
53 { "before", DUMP_BEFORE },
54 { "after", DUMP_AFTER },
55 { "cloud", DUMP_CLOUD },
60 static lc_opt_enum_mask_var_t dump_var = {
61 &dump_flags, dump_items
64 static const lc_opt_table_entry_t options[] = {
65 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud", &dump_var),
66 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes (standard: 3)", &subtree_iter),
67 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
68 LC_OPT_ENT_INT ("max", "maximum recursion depth (default 20)", &max_depth),
72 void be_co2_register_options(lc_opt_entry_t *grp)
74 lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
75 lc_opt_add_table(co2_grp, options);
81 / ___|| |_ __ _ _ __| |_
82 \___ \| __/ _` | '__| __|
83 ___) | || (_| | | | |_
84 |____/ \__\__,_|_| \__|
88 #define INFEASIBLE(cost) ((cost) == INT_MAX)
90 static be_ifg_dump_dot_cb_t ifg_dot_cb;
92 typedef unsigned col_t;
94 typedef struct _co2_irn_t co2_irn_t;
95 typedef struct _co2_cloud_t co2_cloud_t;
96 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
106 bitset_t *ignore_regs;
110 struct list_head cloud_head;
111 DEBUG_ONLY(firm_dbg_module_t *dbg;)
116 affinity_node_t *aff;
117 co2_irn_t *touched_next;
120 int last_color_change;
123 unsigned tmp_fixed : 1;
124 unsigned is_constrained : 1;
125 struct list_head changed_list;
128 struct _co2_cloud_irn_t {
129 struct _co2_irn_t inh;
133 co2_cloud_irn_t *mst_parent;
136 co2_cloud_irn_t **mst_childs;
141 col_cost_pair_t *tmp_coloring;
142 struct list_head cloud_list;
143 struct list_head mst_list;
146 struct _co2_cloud_t {
158 co2_cloud_irn_t *master;
159 co2_cloud_irn_t *mst_root;
160 co2_cloud_irn_t **seq;
161 struct list_head members_head;
162 struct list_head list;
166 co2_cloud_irn_t *src, *tgt;
170 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
172 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
173 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
175 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
177 co2_t *env = (co2_t *) ph;
178 affinity_node_t *a = get_affinity_info(env->co, irn);
179 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
180 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
183 INIT_LIST_HEAD(&ci->changed_list);
184 ci->touched_next = env->touched;
185 ci->orig_col = get_irn_col(env->co, irn);
191 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
192 INIT_LIST_HEAD(&cci->cloud_list);
193 cci->mst_parent = cci;
199 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
201 static int cmp_clouds_gt(const void *a, const void *b)
203 const co2_cloud_t * const *p = a;
204 const co2_cloud_t * const *q = b;
205 double c = CLOUD_WEIGHT(*p);
206 double d = CLOUD_WEIGHT(*q);
207 return QSORT_CMP(d, c);
211 * An order on color/costs pairs.
212 * If the costs are equal, we use the color as a kind of normalization.
214 static int col_cost_pair_lt(const void *a, const void *b)
216 const col_cost_pair_t *p = a;
217 const col_cost_pair_t *q = b;
220 return QSORT_CMP(c, d);
223 int cmp_edges(const void *a, const void *b)
227 return QSORT_CMP(q->costs, p->costs);
230 static col_t get_col(co2_t *env, ir_node *irn)
232 co2_irn_t *ci = get_co2_irn(env, irn);
233 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
236 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
238 co2_irn_t *ci = get_co2_irn(env, irn);
239 return ci->fixed || ci->tmp_fixed;
242 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
245 arch_register_req_t req;
246 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
247 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
248 if(arch_register_req_is(&req, limited)) {
249 req.limited(req.limited_env, ci->adm_cache);
250 ci->is_constrained = 1;
253 bitset_copy(ci->adm_cache, env->ignore_regs);
254 bitset_flip_all(ci->adm_cache);
258 return ci->adm_cache;
261 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
263 bitset_copy(bs, get_adm(env, ci));
267 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
269 bitset_t *bs = get_adm(env, ci);
270 return bitset_is_set(bs, col);
273 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
277 return ci->is_constrained;
280 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
282 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
283 arch_register_req_t req;
285 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
287 if(arch_register_req_is(&req, limited)) {
291 req.limited(req.limited_env, aux);
292 n_constr = bitset_popcnt(aux);
293 bitset_foreach(aux, elm) {
294 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
300 * Determine costs which shall indicate how cheap/expensive it is to try
301 * to assign a node some color.
302 * The costs are computed for all colors. INT_MAX means that it is impossible
303 * to give the node that specific color.
305 * @param env The co2 this pointer.
306 * @param irn The node.
307 * @param col_costs An array of colors x costs where the costs are written to.
309 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
311 ir_node *irn = ci->irn;
312 be_ifg_t *ifg = env->co->cenv->ifg;
313 int n_regs = env->co->cls->n_regs;
314 bitset_t *forb = bitset_alloca(n_regs);
315 affinity_node_t *a = ci->aff;
322 /* Put all forbidden colors into the aux bitset. */
323 admissible_colors(env, ci, forb);
324 bitset_flip_all(forb);
326 for(i = 0; i < n_regs; ++i) {
327 col_costs[i].col = i;
328 col_costs[i].costs = 0;
334 co_gs_foreach_neighb(a, n) {
335 if(color_is_fix(env, n->irn)) {
336 col_t col = get_col(env, n->irn);
337 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
340 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
344 it = be_ifg_neighbours_iter_alloca(ifg);
345 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
346 col_t col = get_col(env, pos);
347 if(color_is_fix(env, pos)) {
348 col_costs[col].costs = INT_MAX;
351 incur_constraint_costs(env, pos, col_costs, INT_MAX);
352 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
355 be_ifg_neighbours_break(ifg, it);
357 /* Set the costs to infinity for each color which is not allowed at this node. */
358 bitset_foreach(forb, elm) {
359 col_costs[elm].costs = INT_MAX;
364 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
366 int n_regs = env->co->cls->n_regs;
369 for(i = 0; i < n_regs; ++i) {
371 seq[i].costs = INT_MAX;
374 assert(is_color_admissible(env, ci, col));
380 static void reject_coloring(struct list_head *h)
384 list_for_each_entry(co2_irn_t, pos, h, changed_list)
388 static void materialize_coloring(struct list_head *h)
392 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
393 pos->orig_col = pos->tmp_col;
398 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
400 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
402 int n_regs = env->co->cls->n_regs;
403 be_ifg_t *ifg = env->co->cenv->ifg;
404 co2_irn_t *ci = get_co2_irn(env, irn);
409 if(depth >= max_depth)
412 for(i = 0; i < n_regs; ++i) {
413 col_t tgt_col = col_list[i].col;
414 unsigned costs = col_list[i].costs;
417 struct list_head changed;
421 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
423 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
424 if(INFEASIBLE(costs)) {
425 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
430 /* Set the new color of the node and mark the node as temporarily fixed. */
431 ci->tmp_col = tgt_col;
435 If that color has costs > 0, there's at least one neighbor having that color,
436 so we will try to change the neighbors' colors, too.
438 INIT_LIST_HEAD(&changed);
439 list_add(&ci->changed_list, &changed);
441 it = be_ifg_neighbours_iter_alloca(ifg);
442 be_ifg_foreach_neighbour(ifg, it, irn, n) {
444 /* try to re-color the neighbor if it has the target color. */
445 if(get_col(env, n) == tgt_col) {
446 struct list_head tmp;
449 Try to change the color of the neighbor and record all nodes which
450 get changed in the tmp list. Add this list to the "changed" list for
451 that color. If we did not succeed to change the color of the neighbor,
452 we bail out and try the next color.
454 INIT_LIST_HEAD(&tmp);
455 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
456 list_splice(&tmp, &changed);
461 be_ifg_neighbours_break(ifg, it);
464 We managed to assign the target color to all neighbors, so from the perspective
465 of the current node, every thing was ok and we can return safely.
468 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
469 list_splice(&changed, parent_changed);
475 If not, that color did not succeed and we unfix all nodes we touched
476 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
479 reject_coloring(&changed);
485 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
487 co2_irn_t *ci = get_co2_irn(env, irn);
489 col_t col = get_col(env, irn);
491 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
493 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
500 list_add(&ci->changed_list, parent_changed);
504 /* The node has the color it should not have _and_ has not been visited yet. */
505 if(!color_is_fix(env, irn)) {
506 int n_regs = env->co->cls->n_regs;
507 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
509 /* Get the costs for giving the node a specific color. */
510 determine_color_costs(env, ci, csts);
512 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
513 csts[not_col].costs = INT_MAX;
515 /* sort the colors according costs, cheapest first. */
516 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
518 /* Try recoloring the node using the color list. */
519 res = recolor(env, irn, csts, parent_changed, depth);
522 /* If we came here, everything went ok. */
526 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
528 co2_irn_t *ci = get_co2_irn(env, irn);
529 col_t col = get_col(env, irn);
532 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
534 /* the node has the wanted color. That's fine, mark it as visited and return. */
539 list_add(&ci->changed_list, parent_changed);
546 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
547 int n_regs = env->co->cls->n_regs;
548 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
550 /* Get the costs for giving the node a specific color. */
551 single_color_cost(env, ci, tgt_col, seq);
553 /* Try recoloring the node using the color list. */
554 res = recolor(env, irn, seq, parent_changed, depth);
559 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
564 * Examine the costs of the current coloring concerning a MST subtree.
565 * @param ci The subtree root.
566 * @param col The color of @p ci.
567 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
569 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
571 int *front = FRONT_BASE(ci, col);
575 for(i = 0; i < ci->mst_n_childs; ++i) {
576 co2_cloud_irn_t *chld = ci->mst_childs[i];
577 col_t chld_col = front[i];
579 cost += examine_subtree_coloring(chld, chld_col);
580 cost += col != chld_col ? chld->mst_costs : 0;
587 * Determine color badnesses of a node.
588 * Badness means that it is unlikely that the node in question can
589 * obtain a color. The higher the badness, the more unlikely it is that
590 * the node can be assigned that color.
591 * @param ci The node.
592 * @param badness An integer array as long as there are registers.
593 * @note The array <code>badness</code> is not cleared.
595 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
597 co2_t *env = ci->cloud->env;
598 co2_irn_t *ir = &ci->inh;
599 int n_regs = env->n_regs;
600 be_ifg_t *ifg = env->co->cenv->ifg;
601 bitset_t *bs = bitset_alloca(n_regs);
607 admissible_colors(env, &ci->inh, bs);
609 bitset_foreach(bs, elm)
610 badness[elm] = ci->costs;
612 /* Use constrained/fixed interfering neighbors to influence the color badness */
613 it = be_ifg_neighbours_iter_alloca(ifg);
614 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
615 co2_irn_t *ni = get_co2_irn(env, irn);
617 admissible_colors(env, ni, bs);
618 if(bitset_popcnt(bs) == 1) {
619 bitset_pos_t c = bitset_next_set(bs, 0);
620 badness[c] += ci->costs;
624 col_t c = get_col(env, ni->irn);
625 badness[c] += ci->costs;
628 be_ifg_neighbours_break(ifg, it);
632 * Determine the badness of a MST subtree.
633 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
634 * @see node_color_badness() for a definition of badness.
635 * @param ci The root of the subtree.
636 * @param depth Depth for debugging purposes.
638 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
640 co2_t *env = ci->cloud->env;
643 node_color_badness(ci, ci->color_badness);
645 /* Collect the color badness for the whole subtree */
646 for(i = 0; i < ci->mst_n_childs; ++i) {
647 co2_cloud_irn_t *child = ci->mst_childs[i];
648 determine_color_badness(child, depth + 1);
650 for(j = 0; j < env->n_regs; ++j)
651 ci->color_badness[j] += child->color_badness[j];
654 for(j = 0; j < env->n_regs; ++j)
655 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
659 * Unfix all nodes in a MST subtree.
661 static void unfix_subtree(co2_cloud_irn_t *ci)
666 for(i = 0; i < ci->mst_n_childs; ++i)
667 unfix_subtree(ci->mst_childs[i]);
670 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
672 co2_t *env = ci->cloud->env;
673 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
674 int is_root = ci->mst_parent == ci;
675 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
676 int min_badness = INT_MAX;
677 int best_col_costs = INT_MAX;
679 int n_regs = env->n_regs;
680 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
682 struct list_head changed;
685 for(i = 0; i < n_regs; ++i) {
686 int badness = ci->color_badness[i];
689 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
691 min_badness = MIN(min_badness, badness);
694 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
695 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
696 seq[parent_col].costs = min_badness - 1;
698 /* Sort the colors. The will be processed in that ordering. */
699 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
701 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
702 INIT_LIST_HEAD(&changed);
703 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
704 col_t col = seq[i].col;
705 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
707 int subtree_costs, sum_costs;
709 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
712 INIT_LIST_HEAD(&changed);
713 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
715 materialize_coloring(&changed);
722 for(j = 0; j < ci->mst_n_childs; ++j) {
723 co2_cloud_irn_t *child = ci->mst_childs[j];
724 ok = coalesce_top_down(child, j, depth + 1) >= 0;
726 child->inh.fixed = 1;
731 /* If the subtree could not be colored, we have to try another color. */
735 subtree_costs = examine_subtree_coloring(ci, col);
736 sum_costs = subtree_costs + add_cost;
737 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
739 if(sum_costs < best_col_costs) {
741 best_col_costs = sum_costs;
742 ci->col_costs[col] = subtree_costs;
750 int *front = FRONT_BASE(ci->mst_parent, parent_col);
751 front[child_nr] = best_col;
757 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
759 be_ifg_t *ifg = env->co->cenv->ifg;
760 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
767 /* mark the node as visited and add it to the cloud. */
769 list_add(&ci->cloud_list, &cloud->members_head);
771 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
773 /* determine the nodes costs */
774 co_gs_foreach_neighb(a, n) {
776 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
777 if(be_ifg_connected(ifg, a->irn, n->irn))
778 cloud->inevit += n->costs;
781 /* add the node's cost to the total costs of the cloud. */
783 cloud->costs += costs;
784 cloud->n_constr += is_constrained(env, &ci->inh);
785 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
786 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
789 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
790 if(costs >= curr_costs) {
795 /* add all the neighbors of the node to the cloud. */
796 co_gs_foreach_neighb(a, n) {
797 affinity_node_t *an = get_affinity_info(env->co, n->irn);
799 populate_cloud(env, cloud, an, curr_costs);
803 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
805 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
809 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
810 memset(cloud, 0, sizeof(cloud[0]));
811 INIT_LIST_HEAD(&cloud->members_head);
812 INIT_LIST_HEAD(&cloud->list);
813 list_add(&cloud->list, &env->cloud_head);
814 cloud->best_costs = INT_MAX;
817 populate_cloud(env, cloud, a, 0);
818 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
820 /* Also allocate space for the node sequence and compute that sequence. */
821 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
824 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
826 cloud->seq[i++] = ci;
828 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
833 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
835 ir_node *irn = ci->inh.irn;
836 int *front = FRONT_BASE(ci, col);
838 struct list_head changed;
840 INIT_LIST_HEAD(&changed);
842 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
843 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
844 // assert(ok && "Color changing may not fail while committing the coloring");
845 materialize_coloring(&changed);
847 for(i = 0; i < ci->mst_n_childs; ++i) {
848 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
852 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
854 while(ci != ci->mst_parent)
860 static void process_cloud(co2_cloud_t *cloud)
862 co2_t *env = cloud->env;
863 int n_regs = env->n_regs;
865 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
872 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
874 /* Collect all edges in the cloud on an obstack and sort the increasingly */
875 obstack_init(&cloud->obst);
876 for(i = 0; i < cloud->n_memb; ++i) {
877 co2_cloud_irn_t *ci = cloud->seq[i];
880 co_gs_foreach_neighb(ci->inh.aff, n) {
881 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
882 if(ci->index < ni->index) {
887 obstack_grow(&cloud->obst, &e, sizeof(e));
892 edges = obstack_finish(&cloud->obst);
893 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
895 /* Compute the maximum spanning tree using Kruskal/Union-Find */
896 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
897 for(i = 0; i < n_edges; ++i) {
898 edge_t *e = &edges[i];
899 co2_cloud_irn_t *rs = find_mst_root(e->src);
900 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
902 /* if the union/find roots are different */
904 int si = e->src->index;
905 int ti = e->tgt->index;
909 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
911 /* this edge is in the MST, so set it in the bitset. */
912 mst_edges[si * cloud->n_memb + ti] = e->costs;
913 mst_edges[ti * cloud->n_memb + si] = e->costs;
916 obstack_free(&cloud->obst, edges);
918 cloud->master->mst_parent = cloud->master;
919 cloud->mst_root = cloud->master;
920 q = new_pdeq1(cloud->master);
921 while(!pdeq_empty(q)) {
922 co2_cloud_irn_t *ci = pdeq_getl(q);
923 int ofs = ci->index * cloud->n_memb;
924 int end = ofs + cloud->n_memb;
927 ci->mst_n_childs = 0;
928 for(i = ofs; i < end; ++i) {
929 if(mst_edges[i] != 0) {
931 co2_cloud_irn_t *child = cloud->seq[i - ofs];
933 /* put the child to the worklist */
936 /* make ci the parent of the child and add the child to the children array of the parent */
937 child->mst_parent = ci;
938 child->mst_costs = mst_edges[i];
940 obstack_ptr_grow(&cloud->obst, child);
942 mst_edges[other * cloud->n_memb + ci->index] = 0;
947 obstack_ptr_grow(&cloud->obst, NULL);
948 ci->mst_childs = obstack_finish(&cloud->obst);
954 DBG((env->dbg, LEVEL_3, "mst:\n"));
955 for(i = 0; i < cloud->n_memb; ++i) {
956 co2_cloud_irn_t *ci = cloud->seq[i];
957 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
960 for(i = 0; i < cloud->n_memb; ++i) {
961 co2_cloud_irn_t *ci = cloud->seq[i];
962 int n_childs = ci->mst_n_childs;
965 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
966 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
967 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
968 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
969 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
970 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
971 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
972 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
974 for(j = 0; j < env->n_regs; j++)
975 ci->col_costs[j] = INT_MAX;
979 determine_color_badness(cloud->mst_root, 0);
980 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
981 unfix_subtree(cloud->mst_root);
982 apply_coloring(cloud->mst_root, best_col, 0);
984 /* The coloring should represent the one with the best costs. */
985 //materialize_coloring(&changed);
986 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
987 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
989 /* Fix all nodes in the cloud. */
990 for(i = 0; i < cloud->n_memb; ++i)
991 cloud->seq[i]->inh.fixed = 1;
993 /* Free all space used while optimizing this cloud. */
994 obstack_free(&cloud->obst, NULL);
997 static int cloud_costs(co2_cloud_t *cloud)
1002 for(i = 0; i < cloud->n_memb; ++i) {
1003 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1004 col_t col = get_col(cloud->env, ci->irn);
1005 co_gs_foreach_neighb(ci->aff, n) {
1006 col_t n_col = get_col(cloud->env, n->irn);
1007 costs += col != n_col ? n->costs : 0;
1014 static void process(co2_t *env)
1018 co2_cloud_t **clouds;
1023 int final_costs = 0;
1026 co_gs_foreach_aff_node(env->co, a) {
1027 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1030 co2_cloud_t *cloud = new_cloud(env, a);
1036 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1037 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1039 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1041 for(i = 0; i < n_clouds; ++i) {
1042 init_costs += cloud_costs(clouds[i]);
1044 /* Process the cloud. */
1045 process_cloud(clouds[i]);
1047 all_costs += clouds[i]->costs;
1048 final_costs += cloud_costs(clouds[i]);
1050 /* Dump the IFG if the user demanded it. */
1051 if (dump_flags & DUMP_CLOUD) {
1055 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1056 f = fopen(buf, "wt");
1058 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1064 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1069 static void writeback_colors(co2_t *env)
1071 const arch_env_t *aenv = env->co->aenv;
1074 for(irn = env->touched; irn; irn = irn->touched_next) {
1075 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1076 arch_set_irn_register(aenv, irn->irn, reg);
1082 ___ _____ ____ ____ ___ _____ ____ _
1083 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1084 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1085 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1086 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1090 static const char *get_dot_color_name(int col)
1092 static const char *names[] = {
1126 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1129 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1131 arch_register_req_t req;
1133 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1134 if(arch_register_req_is(&req, limited))
1146 static void ifg_dump_graph_attr(FILE *f, void *self)
1148 fprintf(f, "overlay=false");
1151 static int ifg_is_dump_node(void *self, ir_node *irn)
1154 return !arch_irn_is(env->co->aenv, irn, ignore);
1157 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1160 co2_irn_t *ci = get_co2_irn(env, irn);
1166 co2_cloud_irn_t *cci = (void *) ci;
1167 if (cci->cloud && cci->cloud->mst_root == cci)
1170 if(cci->cloud && cci->cloud->mst_root)
1171 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1174 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1175 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1178 static void ifg_dump_at_end(FILE *file, void *self)
1183 co_gs_foreach_aff_node(env->co, a) {
1184 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1185 int idx = get_irn_idx(a->irn);
1188 if(ai->mst_parent != ai)
1189 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1191 co_gs_foreach_neighb(a, n) {
1192 int nidx = get_irn_idx(n->irn);
1193 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1196 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1197 const char *arr = "arrowhead=dot arrowtail=dot";
1199 if(ci->mst_parent == ai)
1200 arr = "arrowtail=normal";
1201 else if(ai->mst_parent == ci)
1202 arr = "arrowhead=normal";
1204 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1211 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1213 ifg_dump_graph_attr,
1221 int co_solve_heuristic_new(copy_opt_t *co)
1227 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1231 env.n_regs = co->cls->n_regs;
1232 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1233 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1234 bitset_flip_all(env.ignore_regs);
1235 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1236 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1237 INIT_LIST_HEAD(&env.cloud_head);
1239 if(dump_flags & DUMP_BEFORE) {
1240 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1241 f = fopen(buf, "wt");
1243 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1250 if(dump_flags & DUMP_AFTER) {
1251 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1252 f = fopen(buf, "wt");
1254 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1259 writeback_colors(&env);
1260 phase_free(&env.ph);