2 * Copyright (C) 1995-2008 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 static be_ifg_dump_dot_cb_t ifg_dot_cb;
100 typedef unsigned col_t;
102 typedef struct co2_irn_t co2_irn_t;
103 typedef struct co2_cloud_t co2_cloud_t;
104 typedef struct co2_cloud_irn_t co2_cloud_irn_t;
114 bitset_t *allocatable_regs;
118 struct list_head cloud_head;
119 DEBUG_ONLY(firm_dbg_module_t *dbg;)
124 affinity_node_t *aff;
125 co2_irn_t *touched_next;
128 int last_color_change;
131 unsigned tmp_fixed : 1;
132 unsigned is_constrained : 1;
133 struct list_head changed_list;
136 struct co2_cloud_irn_t {
137 struct co2_irn_t inh;
141 co2_cloud_irn_t *mst_parent;
144 co2_cloud_irn_t **mst_childs;
149 col_cost_pair_t *tmp_coloring;
150 struct list_head cloud_list;
151 struct list_head mst_list;
166 co2_cloud_irn_t *master;
167 co2_cloud_irn_t *mst_root;
168 co2_cloud_irn_t **seq;
169 struct list_head members_head;
170 struct list_head list;
174 co2_cloud_irn_t *src, *tgt;
178 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
180 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
181 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
183 static void *co2_irn_init(ir_phase *ph, const ir_node *irn)
185 co2_t *env = (co2_t *) ph;
186 affinity_node_t *a = get_affinity_info(env->co, irn);
187 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
188 co2_irn_t *ci = phase_alloc(ph, size);
191 INIT_LIST_HEAD(&ci->changed_list);
192 ci->touched_next = env->touched;
193 ci->orig_col = get_irn_col(irn);
199 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
200 INIT_LIST_HEAD(&cci->cloud_list);
201 cci->mst_parent = cci;
207 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
209 static int cmp_clouds_gt(const void *a, const void *b)
211 const co2_cloud_t * const *p = a;
212 const co2_cloud_t * const *q = b;
213 double c = CLOUD_WEIGHT(*p);
214 double d = CLOUD_WEIGHT(*q);
215 return QSORT_CMP(d, c);
219 * An order on color/costs pairs.
220 * If the costs are equal, we use the color as a kind of normalization.
222 static int col_cost_pair_lt(const void *a, const void *b)
224 const col_cost_pair_t *p = a;
225 const col_cost_pair_t *q = b;
228 return QSORT_CMP(c, d);
231 static int cmp_edges(const void *a, const void *b)
235 return QSORT_CMP(q->costs, p->costs);
238 static col_t get_col(co2_t *env, const ir_node *irn)
240 co2_irn_t *ci = get_co2_irn(env, irn);
241 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
244 static inline int color_is_fix(co2_t *env, const ir_node *irn)
246 co2_irn_t *ci = get_co2_irn(env, irn);
247 return ci->fixed || ci->tmp_fixed;
250 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
252 if (ci->adm_cache == NULL) {
253 const arch_register_req_t *req;
254 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
255 req = arch_get_register_req_out(ci->irn);
257 if (arch_register_req_is(req, limited)) {
261 for (i = 0; i < n; ++i) {
262 if (rbitset_is_set(req->limited, i))
263 bitset_set(ci->adm_cache, i);
265 ci->is_constrained = 1;
267 bitset_copy(ci->adm_cache, env->allocatable_regs);
271 return ci->adm_cache;
274 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
276 bitset_copy(bs, get_adm(env, ci));
280 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
282 bitset_t *bs = get_adm(env, ci);
283 return bitset_is_set(bs, col);
286 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
290 return ci->is_constrained;
293 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
295 const arch_register_req_t *req = arch_get_register_req_out(irn);
297 if (arch_register_req_is(req, limited)) {
298 unsigned n_regs = env->co->cls->n_regs;
299 unsigned n_constr = 0;
302 n_constr = rbitset_popcount(req->limited, n_regs);
303 for (i = 0; i < n_regs; ++i) {
304 if (rbitset_is_set(req->limited, i)) {
305 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
312 * Determine costs which shall indicate how cheap/expensive it is to try
313 * to assign a node some color.
314 * The costs are computed for all colors. INT_MAX means that it is impossible
315 * to give the node that specific color.
317 * @param env The co2 this pointer.
318 * @param irn The node.
319 * @param col_costs An array of colors x costs where the costs are written to.
321 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
323 const ir_node *irn = ci->irn;
324 be_ifg_t *ifg = env->co->cenv->ifg;
325 int n_regs = env->co->cls->n_regs;
326 bitset_t *forb = bitset_alloca(n_regs);
327 affinity_node_t *a = ci->aff;
331 neighbours_iter_t it;
334 /* Put all forbidden colors into the aux bitset. */
335 admissible_colors(env, ci, forb);
336 bitset_flip_all(forb);
338 for (i = 0; i < n_regs; ++i) {
339 col_costs[i].col = i;
340 col_costs[i].costs = 0;
346 co_gs_foreach_neighb(a, n) {
347 if (color_is_fix(env, n->irn)) {
348 col_t col = get_col(env, n->irn);
349 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
352 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
356 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
357 col_t col = get_col(env, pos);
358 if (color_is_fix(env, pos)) {
359 col_costs[col].costs = INT_MAX;
362 incur_constraint_costs(env, pos, col_costs, INT_MAX);
363 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
366 be_ifg_neighbours_break(&it);
368 /* Set the costs to infinity for each color which is not allowed at this node. */
369 bitset_foreach(forb, elm) {
370 col_costs[elm].costs = INT_MAX;
375 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
377 int n_regs = env->co->cls->n_regs;
380 for (i = 0; i < n_regs; ++i) {
382 seq[i].costs = INT_MAX;
386 assert(is_color_admissible(env, ci, col));
392 static void reject_coloring(struct list_head *h)
396 list_for_each_entry(co2_irn_t, pos, h, changed_list)
400 static void materialize_coloring(struct list_head *h)
404 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
405 pos->orig_col = pos->tmp_col;
410 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
412 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
414 int n_regs = env->co->cls->n_regs;
415 be_ifg_t *ifg = env->co->cenv->ifg;
416 co2_irn_t *ci = get_co2_irn(env, irn);
421 if (depth >= max_depth)
424 for (i = 0; i < n_regs; ++i) {
425 col_t tgt_col = col_list[i].col;
426 unsigned costs = col_list[i].costs;
429 struct list_head changed;
431 neighbours_iter_t it;
433 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
435 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
436 if (INFEASIBLE(costs)) {
437 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
442 /* Set the new color of the node and mark the node as temporarily fixed. */
443 ci->tmp_col = tgt_col;
447 If that color has costs > 0, there's at least one neighbor having that color,
448 so we will try to change the neighbors' colors, too.
450 INIT_LIST_HEAD(&changed);
451 list_add(&ci->changed_list, &changed);
453 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
455 /* try to re-color the neighbor if it has the target color. */
456 if (get_col(env, n) == tgt_col) {
457 struct list_head tmp;
460 Try to change the color of the neighbor and record all nodes which
461 get changed in the tmp list. Add this list to the "changed" list for
462 that color. If we did not succeed to change the color of the neighbor,
463 we bail out and try the next color.
465 INIT_LIST_HEAD(&tmp);
466 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
467 list_splice(&tmp, &changed);
472 be_ifg_neighbours_break(&it);
475 We managed to assign the target color to all neighbors, so from the perspective
476 of the current node, every thing was ok and we can return safely.
479 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
480 list_splice(&changed, parent_changed);
486 If not, that color did not succeed and we unfix all nodes we touched
487 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
490 reject_coloring(&changed);
496 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
498 co2_irn_t *ci = get_co2_irn(env, irn);
500 col_t col = get_col(env, irn);
502 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
504 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
505 if (col != not_col) {
506 if (!ci->tmp_fixed) {
511 list_add(&ci->changed_list, parent_changed);
515 /* The node has the color it should not have _and_ has not been visited yet. */
516 if (!color_is_fix(env, irn)) {
517 int n_regs = env->co->cls->n_regs;
518 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
520 /* Get the costs for giving the node a specific color. */
521 determine_color_costs(env, ci, csts);
523 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
524 csts[not_col].costs = INT_MAX;
526 /* sort the colors according costs, cheapest first. */
527 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
529 /* Try recoloring the node using the color list. */
530 res = recolor(env, irn, csts, parent_changed, depth);
533 /* If we came here, everything went ok. */
537 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
539 co2_irn_t *ci = get_co2_irn(env, irn);
540 col_t col = get_col(env, irn);
543 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
545 /* the node has the wanted color. That's fine, mark it as visited and return. */
546 if (col == tgt_col) {
547 if (!ci->tmp_fixed) {
550 list_add(&ci->changed_list, parent_changed);
557 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
558 int n_regs = env->co->cls->n_regs;
559 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
561 /* Get the costs for giving the node a specific color. */
562 single_color_cost(env, ci, tgt_col, seq);
564 /* Try recoloring the node using the color list. */
565 res = recolor(env, irn, seq, parent_changed, depth);
570 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
575 * Examine the costs of the current coloring concerning a MST subtree.
576 * @param ci The subtree root.
577 * @param col The color of @p ci.
578 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
580 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
582 int *front = FRONT_BASE(ci, col);
586 for (i = 0; i < ci->mst_n_childs; ++i) {
587 co2_cloud_irn_t *chld = ci->mst_childs[i];
588 col_t chld_col = front[i];
590 cost += examine_subtree_coloring(chld, chld_col);
591 cost += col != chld_col ? chld->mst_costs : 0;
598 * Determine color badnesses of a node.
599 * Badness means that it is unlikely that the node in question can
600 * obtain a color. The higher the badness, the more unlikely it is that
601 * the node can be assigned that color.
602 * @param ci The node.
603 * @param badness An integer array as long as there are registers.
604 * @note The array <code>badness</code> is not cleared.
606 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
608 co2_t *env = ci->cloud->env;
609 co2_irn_t *ir = &ci->inh;
610 int n_regs = env->n_regs;
611 be_ifg_t *ifg = env->co->cenv->ifg;
612 bitset_t *bs = bitset_alloca(n_regs);
616 neighbours_iter_t it;
618 admissible_colors(env, &ci->inh, bs);
620 bitset_foreach(bs, elm)
621 badness[elm] = ci->costs;
623 /* Use constrained/fixed interfering neighbors to influence the color badness */
624 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
625 co2_irn_t *ni = get_co2_irn(env, irn);
627 admissible_colors(env, ni, bs);
628 if (bitset_popcount(bs) == 1) {
629 unsigned c = bitset_next_set(bs, 0);
630 badness[c] += ci->costs;
633 else if (ni->fixed) {
634 col_t c = get_col(env, ni->irn);
635 badness[c] += ci->costs;
638 be_ifg_neighbours_break(&it);
642 * Determine the badness of a MST subtree.
643 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
644 * @see node_color_badness() for a definition of badness.
645 * @param ci The root of the subtree.
646 * @param depth Depth for debugging purposes.
648 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
650 co2_t *env = ci->cloud->env;
653 node_color_badness(ci, ci->color_badness);
655 /* Collect the color badness for the whole subtree */
656 for (i = 0; i < ci->mst_n_childs; ++i) {
657 co2_cloud_irn_t *child = ci->mst_childs[i];
658 determine_color_badness(child, depth + 1);
660 for (j = 0; j < env->n_regs; ++j)
661 ci->color_badness[j] += child->color_badness[j];
664 for (j = 0; j < env->n_regs; ++j)
665 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
669 * Unfix all nodes in a MST subtree.
671 static void unfix_subtree(co2_cloud_irn_t *ci)
676 for (i = 0; i < ci->mst_n_childs; ++i)
677 unfix_subtree(ci->mst_childs[i]);
680 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
682 co2_t *env = ci->cloud->env;
683 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
684 int is_root = ci->mst_parent == ci;
685 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
686 int min_badness = INT_MAX;
687 int best_col_costs = INT_MAX;
689 int n_regs = env->n_regs;
690 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
692 struct list_head changed;
695 for (i = 0; i < n_regs; ++i) {
696 int badness = ci->color_badness[i];
699 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
701 min_badness = MIN(min_badness, badness);
704 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
705 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
706 seq[parent_col].costs = min_badness - 1;
708 /* Sort the colors. The will be processed in that ordering. */
709 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
711 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
712 INIT_LIST_HEAD(&changed);
713 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
714 col_t col = seq[i].col;
715 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
717 int subtree_costs, sum_costs;
719 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
722 INIT_LIST_HEAD(&changed);
723 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
725 materialize_coloring(&changed);
732 for (j = 0; j < ci->mst_n_childs; ++j) {
733 co2_cloud_irn_t *child = ci->mst_childs[j];
734 ok = coalesce_top_down(child, j, depth + 1) >= 0;
736 child->inh.fixed = 1;
741 /* If the subtree could not be colored, we have to try another color. */
745 subtree_costs = examine_subtree_coloring(ci, col);
746 sum_costs = subtree_costs + add_cost;
747 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
749 if (sum_costs < best_col_costs) {
751 best_col_costs = sum_costs;
752 ci->col_costs[col] = subtree_costs;
760 int *front = FRONT_BASE(ci->mst_parent, parent_col);
761 front[child_nr] = best_col;
767 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
769 be_ifg_t *ifg = env->co->cenv->ifg;
770 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
777 /* mark the node as visited and add it to the cloud. */
779 list_add(&ci->cloud_list, &cloud->members_head);
781 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
783 /* determine the nodes costs */
784 co_gs_foreach_neighb(a, n) {
786 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
787 if (be_ifg_connected(ifg, a->irn, n->irn))
788 cloud->inevit += n->costs;
791 /* add the node's cost to the total costs of the cloud. */
793 cloud->costs += costs;
794 cloud->n_constr += is_constrained(env, &ci->inh);
795 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
796 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
799 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
800 if (costs >= curr_costs) {
805 /* add all the neighbors of the node to the cloud. */
806 co_gs_foreach_neighb(a, n) {
807 affinity_node_t *an = get_affinity_info(env->co, n->irn);
809 populate_cloud(env, cloud, an, curr_costs);
813 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
815 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
819 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
820 memset(cloud, 0, sizeof(cloud[0]));
821 INIT_LIST_HEAD(&cloud->members_head);
822 INIT_LIST_HEAD(&cloud->list);
823 list_add(&cloud->list, &env->cloud_head);
824 cloud->best_costs = INT_MAX;
827 populate_cloud(env, cloud, a, 0);
828 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
830 /* Also allocate space for the node sequence and compute that sequence. */
831 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
834 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
836 cloud->seq[i++] = ci;
838 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
843 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
845 const ir_node *irn = ci->inh.irn;
846 int *front = FRONT_BASE(ci, col);
848 struct list_head changed;
850 INIT_LIST_HEAD(&changed);
852 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
853 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
854 // assert(ok && "Color changing may not fail while committing the coloring");
855 materialize_coloring(&changed);
857 for (i = 0; i < ci->mst_n_childs; ++i) {
858 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
862 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
864 while (ci != ci->mst_parent)
870 static void process_cloud(co2_cloud_t *cloud)
872 co2_t *env = cloud->env;
873 int n_regs = env->n_regs;
875 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
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 = OALLOCNZ(&cloud->obst, int, n_regs);
974 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
975 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
976 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
978 for (j = 0; j < env->n_regs; j++)
979 ci->col_costs[j] = INT_MAX;
982 determine_color_badness(cloud->mst_root, 0);
983 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
984 unfix_subtree(cloud->mst_root);
985 apply_coloring(cloud->mst_root, best_col, 0);
987 /* The coloring should represent the one with the best costs. */
988 //materialize_coloring(&changed);
989 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
990 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
992 /* Fix all nodes in the cloud. */
993 for (i = 0; i < cloud->n_memb; ++i)
994 cloud->seq[i]->inh.fixed = 1;
996 /* Free all space used while optimizing this cloud. */
997 obstack_free(&cloud->obst, NULL);
1000 static int cloud_costs(co2_cloud_t *cloud)
1005 for (i = 0; i < cloud->n_memb; ++i) {
1006 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1007 col_t col = get_col(cloud->env, ci->irn);
1008 co_gs_foreach_neighb(ci->aff, n) {
1009 col_t n_col = get_col(cloud->env, n->irn);
1010 costs += col != n_col ? n->costs : 0;
1017 static void process(co2_t *env)
1021 co2_cloud_t **clouds;
1026 int final_costs = 0;
1029 co_gs_foreach_aff_node(env->co, a) {
1030 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1039 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1040 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1042 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1044 for (i = 0; i < n_clouds; ++i) {
1045 init_costs += cloud_costs(clouds[i]);
1047 /* Process the cloud. */
1048 process_cloud(clouds[i]);
1050 all_costs += clouds[i]->costs;
1051 final_costs += cloud_costs(clouds[i]);
1053 /* Dump the IFG if the user demanded it. */
1054 if (dump_flags & DUMP_CLOUD) {
1058 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1059 f = fopen(buf, "wt");
1061 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1067 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1072 static void writeback_colors(co2_t *env)
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((ir_node*)irn->irn, reg);
1084 ___ _____ ____ ____ ___ _____ ____ _
1085 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1086 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1087 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1088 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1092 static const char *get_dot_color_name(size_t col)
1094 static const char *const names[] = {
1128 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1131 static const char *get_dot_shape_name(co2_irn_t *ci)
1133 const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
1135 if (arch_register_req_is(req, limited))
1147 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)
1155 const arch_register_req_t *req = arch_get_register_req_out(irn);
1157 return !(req->type & arch_register_req_type_ignore);
1160 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1163 co2_irn_t *ci = get_co2_irn(env, irn);
1169 co2_cloud_irn_t *cci = (void *) ci;
1170 if (cci->cloud && cci->cloud->mst_root == cci)
1173 if (cci->cloud && cci->cloud->mst_root)
1174 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1177 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1178 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1181 static void ifg_dump_at_end(FILE *file, void *self)
1186 co_gs_foreach_aff_node(env->co, a) {
1187 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1188 int idx = get_irn_idx(a->irn);
1191 if (ai->mst_parent != ai)
1192 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1194 co_gs_foreach_neighb(a, n) {
1195 int nidx = get_irn_idx(n->irn);
1196 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1199 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1200 const char *arr = "arrowhead=dot arrowtail=dot";
1202 if (ci->mst_parent == ai)
1203 arr = "arrowtail=normal";
1204 else if (ai->mst_parent == ci)
1205 arr = "arrowhead=normal";
1207 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1214 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1216 ifg_dump_graph_attr,
1223 int co_solve_heuristic_new(copy_opt_t *co)
1229 phase_init(&env.ph, co->cenv->irg, co2_irn_init);
1233 env.n_regs = co->cls->n_regs;
1234 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1235 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_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_deinit(&env.ph);
1264 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
1265 void be_init_copyheur2(void)
1267 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1268 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1269 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1270 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1272 static co_algo_info copyheur = {
1273 co_solve_heuristic_new, 0
1276 lc_opt_add_table(co2_grp, options);
1277 be_register_copyopt("heur2", ©heur);