2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief More experiments on coalescing.
23 * @author Sebastian Hack
30 #include "lc_opts_enum.h"
38 #include "raw_bitset.h"
41 #include "bitfiddle.h"
43 #include "irphase_t.h"
44 #include "irgraph_t.h"
52 #include "becopyopt.h"
53 #include "becopyopt_t.h"
54 #include "bechordal_t.h"
60 #define DUMP_ALL 2 * DUMP_CLOUD - 1
62 static unsigned dump_flags = 0;
63 static int subtree_iter = 4;
64 static int max_depth = 20;
65 static double constr_factor = 0.9;
67 static const lc_opt_enum_mask_items_t dump_items[] = {
68 { "before", DUMP_BEFORE },
69 { "after", DUMP_AFTER },
70 { "cloud", DUMP_CLOUD },
75 static lc_opt_enum_mask_var_t dump_var = {
76 &dump_flags, dump_items
79 static const lc_opt_table_entry_t options[] = {
80 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
81 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
82 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
83 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
89 / ___|| |_ __ _ _ __| |_
90 \___ \| __/ _` | '__| __|
91 ___) | || (_| | | | |_
92 |____/ \__\__,_|_| \__|
96 #define INFEASIBLE(cost) ((cost) == INT_MAX)
98 typedef unsigned col_t;
100 typedef struct co2_irn_t co2_irn_t;
101 typedef struct co2_cloud_t co2_cloud_t;
102 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
112 bitset_t *allocatable_regs;
116 struct list_head cloud_head;
117 DEBUG_ONLY(firm_dbg_module_t *dbg;)
122 affinity_node_t *aff;
123 co2_irn_t *touched_next;
126 int last_color_change;
129 unsigned tmp_fixed : 1;
130 unsigned is_constrained : 1;
131 struct list_head changed_list;
134 struct co2_cloud_irn_t {
135 struct co2_irn_t inh;
139 co2_cloud_irn_t *mst_parent;
142 co2_cloud_irn_t **mst_childs;
147 col_cost_pair_t *tmp_coloring;
148 struct list_head cloud_list;
149 struct list_head mst_list;
164 co2_cloud_irn_t *master;
165 co2_cloud_irn_t *mst_root;
166 co2_cloud_irn_t **seq;
167 struct list_head members_head;
168 struct list_head list;
172 co2_cloud_irn_t *src, *tgt;
176 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
178 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
179 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
181 static void *co2_irn_init(ir_phase *ph, const ir_node *irn)
183 co2_t *env = (co2_t *) ph;
184 affinity_node_t *a = get_affinity_info(env->co, irn);
185 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
186 co2_irn_t *ci = (co2_irn_t*)phase_alloc(ph, size);
189 INIT_LIST_HEAD(&ci->changed_list);
190 ci->touched_next = env->touched;
191 ci->orig_col = get_irn_col(irn);
197 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
198 INIT_LIST_HEAD(&cci->cloud_list);
199 cci->mst_parent = cci;
205 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
207 static int cmp_clouds_gt(const void *a, const void *b)
209 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
210 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
211 double c = CLOUD_WEIGHT(*p);
212 double d = CLOUD_WEIGHT(*q);
213 return QSORT_CMP(d, c);
217 * An order on color/costs pairs.
218 * If the costs are equal, we use the color as a kind of normalization.
220 static int col_cost_pair_lt(const void *a, const void *b)
222 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
223 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
226 return QSORT_CMP(c, d);
229 static int cmp_edges(const void *a, const void *b)
231 const edge_t *p = (const edge_t*)a;
232 const edge_t *q = (const edge_t*)b;
233 return QSORT_CMP(q->costs, p->costs);
236 static col_t get_col(co2_t *env, const ir_node *irn)
238 co2_irn_t *ci = get_co2_irn(env, irn);
239 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
242 static inline int color_is_fix(co2_t *env, const ir_node *irn)
244 co2_irn_t *ci = get_co2_irn(env, irn);
245 return ci->fixed || ci->tmp_fixed;
248 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
250 if (ci->adm_cache == NULL) {
251 const arch_register_req_t *req;
252 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
253 req = arch_get_register_req_out(ci->irn);
255 if (arch_register_req_is(req, limited)) {
259 for (i = 0; i < n; ++i) {
260 if (rbitset_is_set(req->limited, i))
261 bitset_set(ci->adm_cache, i);
263 ci->is_constrained = 1;
265 bitset_copy(ci->adm_cache, env->allocatable_regs);
269 return ci->adm_cache;
272 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
274 bitset_copy(bs, get_adm(env, ci));
278 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
280 bitset_t *bs = get_adm(env, ci);
281 return bitset_is_set(bs, col);
284 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
288 return ci->is_constrained;
291 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
293 const arch_register_req_t *req = arch_get_register_req_out(irn);
295 if (arch_register_req_is(req, limited)) {
296 unsigned n_regs = env->co->cls->n_regs;
297 unsigned n_constr = 0;
300 n_constr = rbitset_popcount(req->limited, n_regs);
301 for (i = 0; i < n_regs; ++i) {
302 if (rbitset_is_set(req->limited, i)) {
303 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
310 * Determine costs which shall indicate how cheap/expensive it is to try
311 * to assign a node some color.
312 * The costs are computed for all colors. INT_MAX means that it is impossible
313 * to give the node that specific color.
315 * @param env The co2 this pointer.
316 * @param irn The node.
317 * @param col_costs An array of colors x costs where the costs are written to.
319 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
321 const ir_node *irn = ci->irn;
322 be_ifg_t *ifg = env->co->cenv->ifg;
323 int n_regs = env->co->cls->n_regs;
324 bitset_t *forb = bitset_alloca(n_regs);
325 affinity_node_t *a = ci->aff;
329 neighbours_iter_t it;
332 /* Put all forbidden colors into the aux bitset. */
333 admissible_colors(env, ci, forb);
334 bitset_flip_all(forb);
336 for (i = 0; i < n_regs; ++i) {
337 col_costs[i].col = i;
338 col_costs[i].costs = 0;
344 co_gs_foreach_neighb(a, n) {
345 if (color_is_fix(env, n->irn)) {
346 col_t col = get_col(env, n->irn);
347 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
350 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
354 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
355 col_t col = get_col(env, pos);
356 if (color_is_fix(env, pos)) {
357 col_costs[col].costs = INT_MAX;
360 incur_constraint_costs(env, pos, col_costs, INT_MAX);
361 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
364 be_ifg_neighbours_break(&it);
366 /* Set the costs to infinity for each color which is not allowed at this node. */
367 bitset_foreach(forb, elm) {
368 col_costs[elm].costs = INT_MAX;
373 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
375 int n_regs = env->co->cls->n_regs;
378 for (i = 0; i < n_regs; ++i) {
380 seq[i].costs = INT_MAX;
384 assert(is_color_admissible(env, ci, col));
390 static void reject_coloring(struct list_head *h)
394 list_for_each_entry(co2_irn_t, pos, h, changed_list)
398 static void materialize_coloring(struct list_head *h)
402 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
403 pos->orig_col = pos->tmp_col;
408 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
410 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
412 int n_regs = env->co->cls->n_regs;
413 be_ifg_t *ifg = env->co->cenv->ifg;
414 co2_irn_t *ci = get_co2_irn(env, irn);
419 if (depth >= max_depth)
422 for (i = 0; i < n_regs; ++i) {
423 col_t tgt_col = col_list[i].col;
424 unsigned costs = col_list[i].costs;
427 struct list_head changed;
429 neighbours_iter_t it;
431 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
433 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
434 if (INFEASIBLE(costs)) {
435 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
440 /* Set the new color of the node and mark the node as temporarily fixed. */
441 ci->tmp_col = tgt_col;
445 If that color has costs > 0, there's at least one neighbor having that color,
446 so we will try to change the neighbors' colors, too.
448 INIT_LIST_HEAD(&changed);
449 list_add(&ci->changed_list, &changed);
451 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
453 /* try to re-color the neighbor if it has the target color. */
454 if (get_col(env, n) == tgt_col) {
455 struct list_head tmp;
458 Try to change the color of the neighbor and record all nodes which
459 get changed in the tmp list. Add this list to the "changed" list for
460 that color. If we did not succeed to change the color of the neighbor,
461 we bail out and try the next color.
463 INIT_LIST_HEAD(&tmp);
464 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
465 list_splice(&tmp, &changed);
470 be_ifg_neighbours_break(&it);
473 We managed to assign the target color to all neighbors, so from the perspective
474 of the current node, every thing was ok and we can return safely.
477 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
478 list_splice(&changed, parent_changed);
484 If not, that color did not succeed and we unfix all nodes we touched
485 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
488 reject_coloring(&changed);
494 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
496 co2_irn_t *ci = get_co2_irn(env, irn);
498 col_t col = get_col(env, irn);
500 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
502 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
503 if (col != not_col) {
504 if (!ci->tmp_fixed) {
509 list_add(&ci->changed_list, parent_changed);
513 /* The node has the color it should not have _and_ has not been visited yet. */
514 if (!color_is_fix(env, irn)) {
515 int n_regs = env->co->cls->n_regs;
516 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
518 /* Get the costs for giving the node a specific color. */
519 determine_color_costs(env, ci, csts);
521 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
522 csts[not_col].costs = INT_MAX;
524 /* sort the colors according costs, cheapest first. */
525 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
527 /* Try recoloring the node using the color list. */
528 res = recolor(env, irn, csts, parent_changed, depth);
531 /* If we came here, everything went ok. */
535 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
537 co2_irn_t *ci = get_co2_irn(env, irn);
538 col_t col = get_col(env, irn);
541 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
543 /* the node has the wanted color. That's fine, mark it as visited and return. */
544 if (col == tgt_col) {
545 if (!ci->tmp_fixed) {
548 list_add(&ci->changed_list, parent_changed);
555 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
556 int n_regs = env->co->cls->n_regs;
557 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
559 /* Get the costs for giving the node a specific color. */
560 single_color_cost(env, ci, tgt_col, seq);
562 /* Try recoloring the node using the color list. */
563 res = recolor(env, irn, seq, parent_changed, depth);
568 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
573 * Examine the costs of the current coloring concerning a MST subtree.
574 * @param ci The subtree root.
575 * @param col The color of @p ci.
576 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
578 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
580 int *front = FRONT_BASE(ci, col);
584 for (i = 0; i < ci->mst_n_childs; ++i) {
585 co2_cloud_irn_t *chld = ci->mst_childs[i];
586 col_t chld_col = front[i];
588 cost += examine_subtree_coloring(chld, chld_col);
589 cost += col != chld_col ? chld->mst_costs : 0;
596 * Determine color badnesses of a node.
597 * Badness means that it is unlikely that the node in question can
598 * obtain a color. The higher the badness, the more unlikely it is that
599 * the node can be assigned that color.
600 * @param ci The node.
601 * @param badness An integer array as long as there are registers.
602 * @note The array <code>badness</code> is not cleared.
604 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
606 co2_t *env = ci->cloud->env;
607 co2_irn_t *ir = &ci->inh;
608 int n_regs = env->n_regs;
609 be_ifg_t *ifg = env->co->cenv->ifg;
610 bitset_t *bs = bitset_alloca(n_regs);
614 neighbours_iter_t it;
616 admissible_colors(env, &ci->inh, bs);
618 bitset_foreach(bs, elm)
619 badness[elm] = ci->costs;
621 /* Use constrained/fixed interfering neighbors to influence the color badness */
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_popcount(bs) == 1) {
627 size_t c = bitset_next_set(bs, 0);
628 badness[c] += ci->costs;
631 else if (ni->fixed) {
632 col_t c = get_col(env, ni->irn);
633 badness[c] += ci->costs;
636 be_ifg_neighbours_break(&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 = ALLOCAN(col_cost_pair_t, env->n_regs);
682 int is_root = ci->mst_parent == ci;
683 col_t parent_col = is_root ? (col_t) -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_popcount(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 = (co2_cloud_t*)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 = (co2_cloud_irn_t**)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 const 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 = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
880 /* Collect all edges in the cloud on an obstack and sort the increasingly */
881 obstack_init(&cloud->obst);
882 for (i = 0; i < cloud->n_memb; ++i) {
883 co2_cloud_irn_t *ci = cloud->seq[i];
886 co_gs_foreach_neighb(ci->inh.aff, n) {
887 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
888 if (ci->index < ni->index) {
893 obstack_grow(&cloud->obst, &e, sizeof(e));
898 edges = (edge_t*)obstack_finish(&cloud->obst);
899 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
901 /* Compute the maximum spanning tree using Kruskal/Union-Find */
902 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
903 for (i = 0; i < n_edges; ++i) {
904 edge_t *e = &edges[i];
905 co2_cloud_irn_t *rs = find_mst_root(e->src);
906 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
908 /* if the union/find roots are different */
910 int si = e->src->index;
911 int ti = e->tgt->index;
915 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
917 /* this edge is in the MST, so set it in the bitset. */
918 mst_edges[si * cloud->n_memb + ti] = e->costs;
919 mst_edges[ti * cloud->n_memb + si] = e->costs;
922 obstack_free(&cloud->obst, edges);
924 cloud->master->mst_parent = cloud->master;
925 cloud->mst_root = cloud->master;
926 q = new_pdeq1(cloud->master);
927 while (!pdeq_empty(q)) {
928 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
929 int ofs = ci->index * cloud->n_memb;
930 int end = ofs + cloud->n_memb;
933 ci->mst_n_childs = 0;
934 for (i = ofs; i < end; ++i) {
935 if (mst_edges[i] != 0) {
937 co2_cloud_irn_t *child = cloud->seq[i - ofs];
939 /* put the child to the worklist */
942 /* make ci the parent of the child and add the child to the children array of the parent */
943 child->mst_parent = ci;
944 child->mst_costs = mst_edges[i];
946 obstack_ptr_grow(&cloud->obst, child);
948 mst_edges[other * cloud->n_memb + ci->index] = 0;
953 obstack_ptr_grow(&cloud->obst, NULL);
954 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
960 DBG((env->dbg, LEVEL_3, "mst:\n"));
961 for (i = 0; i < cloud->n_memb; ++i) {
962 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
963 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
966 for (i = 0; i < cloud->n_memb; ++i) {
967 co2_cloud_irn_t *ci = cloud->seq[i];
968 int n_childs = ci->mst_n_childs;
971 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
972 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
973 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
974 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
976 for (j = 0; j < env->n_regs; j++)
977 ci->col_costs[j] = INT_MAX;
980 determine_color_badness(cloud->mst_root, 0);
981 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
982 unfix_subtree(cloud->mst_root);
983 apply_coloring(cloud->mst_root, best_col, 0);
985 /* The coloring should represent the one with the best costs. */
986 //materialize_coloring(&changed);
987 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
988 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
990 /* Fix all nodes in the cloud. */
991 for (i = 0; i < cloud->n_memb; ++i)
992 cloud->seq[i]->inh.fixed = 1;
994 /* Free all space used while optimizing this cloud. */
995 obstack_free(&cloud->obst, NULL);
998 static int cloud_costs(co2_cloud_t *cloud)
1003 for (i = 0; i < cloud->n_memb; ++i) {
1004 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1005 col_t col = get_col(cloud->env, ci->irn);
1006 co_gs_foreach_neighb(ci->aff, n) {
1007 col_t n_col = get_col(cloud->env, n->irn);
1008 costs += col != n_col ? n->costs : 0;
1015 static void writeback_colors(co2_t *env)
1019 for (irn = env->touched; irn; irn = irn->touched_next) {
1020 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1021 arch_set_irn_register((ir_node*)irn->irn, reg);
1027 ___ _____ ____ ____ ___ _____ ____ _
1028 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1029 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1030 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1031 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1035 static const char *get_dot_color_name(size_t col)
1037 static const char *const names[] = {
1071 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1074 static const char *get_dot_shape_name(co2_irn_t *ci)
1076 const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
1078 if (arch_register_req_is(req, limited))
1090 static void ifg_dump_graph_attr(FILE *f, void *self)
1093 fprintf(f, "overlay=false");
1096 static int ifg_is_dump_node(void *self, ir_node *irn)
1098 const arch_register_req_t *req = arch_get_register_req_out(irn);
1100 return !(req->type & arch_register_req_type_ignore);
1103 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1105 co2_t *env = (co2_t*)self;
1106 co2_irn_t *ci = get_co2_irn(env, irn);
1112 co2_cloud_irn_t *cci = (co2_cloud_irn_t*) ci;
1113 if (cci->cloud && cci->cloud->mst_root == cci)
1116 if (cci->cloud && cci->cloud->mst_root)
1117 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1120 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1121 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1124 static void ifg_dump_at_end(FILE *file, void *self)
1126 co2_t *env = (co2_t*)self;
1129 co_gs_foreach_aff_node(env->co, a) {
1130 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1131 int idx = get_irn_idx(a->irn);
1134 if (ai->mst_parent != ai)
1135 fprintf(file, "\tn%d -- n%u [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1137 co_gs_foreach_neighb(a, n) {
1138 int nidx = get_irn_idx(n->irn);
1139 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1142 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1143 const char *arr = "arrowhead=dot arrowtail=dot";
1145 if (ci->mst_parent == ai)
1146 arr = "arrowtail=normal";
1147 else if (ai->mst_parent == ci)
1148 arr = "arrowhead=normal";
1150 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1156 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1158 ifg_dump_graph_attr,
1165 static void process(co2_t *env)
1169 co2_cloud_t **clouds;
1174 int final_costs = 0;
1177 co_gs_foreach_aff_node(env->co, a) {
1178 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1187 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1188 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1190 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1192 for (i = 0; i < n_clouds; ++i) {
1193 init_costs += cloud_costs(clouds[i]);
1195 /* Process the cloud. */
1196 process_cloud(clouds[i]);
1198 all_costs += clouds[i]->costs;
1199 final_costs += cloud_costs(clouds[i]);
1201 /* Dump the IFG if the user demanded it. */
1202 if (dump_flags & DUMP_CLOUD) {
1206 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1207 f = fopen(buf, "wt");
1209 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1215 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1220 int co_solve_heuristic_new(copy_opt_t *co)
1226 phase_init(&env.ph, co->cenv->irg, co2_irn_init);
1230 env.n_regs = co->cls->n_regs;
1231 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1232 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1233 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1234 INIT_LIST_HEAD(&env.cloud_head);
1236 if (dump_flags & DUMP_BEFORE) {
1237 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1238 f = fopen(buf, "wt");
1240 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1247 if (dump_flags & DUMP_AFTER) {
1248 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.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);
1256 writeback_colors(&env);
1257 phase_deinit(&env.ph);
1261 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1262 void be_init_copyheur2(void)
1264 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1265 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1266 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1267 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1269 static co_algo_info copyheur = {
1270 co_solve_heuristic_new, 0
1273 lc_opt_add_table(co2_grp, options);
1274 be_register_copyopt("heur2", ©heur);