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),
87 void be_init_copyheur2(void)
89 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
90 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
91 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
92 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
94 lc_opt_add_table(co2_grp, options);
97 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
101 / ___|| |_ __ _ _ __| |_
102 \___ \| __/ _` | '__| __|
103 ___) | || (_| | | | |_
104 |____/ \__\__,_|_| \__|
108 #define INFEASIBLE(cost) ((cost) == INT_MAX)
110 static be_ifg_dump_dot_cb_t ifg_dot_cb;
112 typedef unsigned col_t;
114 typedef struct _co2_irn_t co2_irn_t;
115 typedef struct _co2_cloud_t co2_cloud_t;
116 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
126 bitset_t *ignore_regs;
130 struct list_head cloud_head;
131 DEBUG_ONLY(firm_dbg_module_t *dbg;)
136 affinity_node_t *aff;
137 co2_irn_t *touched_next;
140 int last_color_change;
143 unsigned tmp_fixed : 1;
144 unsigned is_constrained : 1;
145 struct list_head changed_list;
148 struct _co2_cloud_irn_t {
149 struct _co2_irn_t inh;
153 co2_cloud_irn_t *mst_parent;
156 co2_cloud_irn_t **mst_childs;
161 col_cost_pair_t *tmp_coloring;
162 struct list_head cloud_list;
163 struct list_head mst_list;
166 struct _co2_cloud_t {
178 co2_cloud_irn_t *master;
179 co2_cloud_irn_t *mst_root;
180 co2_cloud_irn_t **seq;
181 struct list_head members_head;
182 struct list_head list;
186 co2_cloud_irn_t *src, *tgt;
190 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
192 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
193 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
195 static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
197 co2_t *env = (co2_t *) ph;
198 affinity_node_t *a = get_affinity_info(env->co, irn);
199 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
200 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
203 INIT_LIST_HEAD(&ci->changed_list);
204 ci->touched_next = env->touched;
205 ci->orig_col = get_irn_col(irn);
211 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
212 INIT_LIST_HEAD(&cci->cloud_list);
213 cci->mst_parent = cci;
219 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
221 static int cmp_clouds_gt(const void *a, const void *b)
223 const co2_cloud_t * const *p = a;
224 const co2_cloud_t * const *q = b;
225 double c = CLOUD_WEIGHT(*p);
226 double d = CLOUD_WEIGHT(*q);
227 return QSORT_CMP(d, c);
231 * An order on color/costs pairs.
232 * If the costs are equal, we use the color as a kind of normalization.
234 static int col_cost_pair_lt(const void *a, const void *b)
236 const col_cost_pair_t *p = a;
237 const col_cost_pair_t *q = b;
240 return QSORT_CMP(c, d);
243 int cmp_edges(const void *a, const void *b)
247 return QSORT_CMP(q->costs, p->costs);
250 static col_t get_col(co2_t *env, const ir_node *irn)
252 co2_irn_t *ci = get_co2_irn(env, irn);
253 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
256 static inline int color_is_fix(co2_t *env, const ir_node *irn)
258 co2_irn_t *ci = get_co2_irn(env, irn);
259 return ci->fixed || ci->tmp_fixed;
262 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
264 if(ci->adm_cache == NULL) {
265 const arch_register_req_t *req;
266 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
267 req = arch_get_register_req_out(ci->irn);
269 if(arch_register_req_is(req, limited)) {
273 for(i = 0; i < n; ++i) {
274 if(rbitset_is_set(req->limited, i))
275 bitset_set(ci->adm_cache, i);
277 ci->is_constrained = 1;
279 bitset_copy(ci->adm_cache, env->ignore_regs);
280 bitset_flip_all(ci->adm_cache);
284 return ci->adm_cache;
287 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
289 bitset_copy(bs, get_adm(env, ci));
293 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
295 bitset_t *bs = get_adm(env, ci);
296 return bitset_is_set(bs, col);
299 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
303 return ci->is_constrained;
306 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
308 const arch_register_req_t *req = arch_get_register_req_out(irn);
310 if (arch_register_req_is(req, limited)) {
311 unsigned n_regs = env->co->cls->n_regs;
312 unsigned n_constr = 0;
315 n_constr = rbitset_popcnt(req->limited, n_regs);
316 for (i = 0; i < n_regs; ++i) {
317 if (rbitset_is_set(req->limited, i)) {
318 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
325 * Determine costs which shall indicate how cheap/expensive it is to try
326 * to assign a node some color.
327 * The costs are computed for all colors. INT_MAX means that it is impossible
328 * to give the node that specific color.
330 * @param env The co2 this pointer.
331 * @param irn The node.
332 * @param col_costs An array of colors x costs where the costs are written to.
334 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
336 const ir_node *irn = ci->irn;
337 be_ifg_t *ifg = env->co->cenv->ifg;
338 int n_regs = env->co->cls->n_regs;
339 bitset_t *forb = bitset_alloca(n_regs);
340 affinity_node_t *a = ci->aff;
347 /* Put all forbidden colors into the aux bitset. */
348 admissible_colors(env, ci, forb);
349 bitset_flip_all(forb);
351 for(i = 0; i < n_regs; ++i) {
352 col_costs[i].col = i;
353 col_costs[i].costs = 0;
359 co_gs_foreach_neighb(a, n) {
360 if(color_is_fix(env, n->irn)) {
361 col_t col = get_col(env, n->irn);
362 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
365 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
369 it = be_ifg_neighbours_iter_alloca(ifg);
370 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
371 col_t col = get_col(env, pos);
372 if(color_is_fix(env, pos)) {
373 col_costs[col].costs = INT_MAX;
376 incur_constraint_costs(env, pos, col_costs, INT_MAX);
377 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
380 be_ifg_neighbours_break(ifg, it);
382 /* Set the costs to infinity for each color which is not allowed at this node. */
383 bitset_foreach(forb, elm) {
384 col_costs[elm].costs = INT_MAX;
389 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
391 int n_regs = env->co->cls->n_regs;
394 for(i = 0; i < n_regs; ++i) {
396 seq[i].costs = INT_MAX;
400 assert(is_color_admissible(env, ci, col));
406 static void reject_coloring(struct list_head *h)
410 list_for_each_entry(co2_irn_t, pos, h, changed_list)
414 static void materialize_coloring(struct list_head *h)
418 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
419 pos->orig_col = pos->tmp_col;
424 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
426 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
428 int n_regs = env->co->cls->n_regs;
429 be_ifg_t *ifg = env->co->cenv->ifg;
430 co2_irn_t *ci = get_co2_irn(env, irn);
435 if(depth >= max_depth)
438 for(i = 0; i < n_regs; ++i) {
439 col_t tgt_col = col_list[i].col;
440 unsigned costs = col_list[i].costs;
443 struct list_head changed;
447 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
449 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
450 if(INFEASIBLE(costs)) {
451 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
456 /* Set the new color of the node and mark the node as temporarily fixed. */
457 ci->tmp_col = tgt_col;
461 If that color has costs > 0, there's at least one neighbor having that color,
462 so we will try to change the neighbors' colors, too.
464 INIT_LIST_HEAD(&changed);
465 list_add(&ci->changed_list, &changed);
467 it = be_ifg_neighbours_iter_alloca(ifg);
468 be_ifg_foreach_neighbour(ifg, it, irn, n) {
470 /* try to re-color the neighbor if it has the target color. */
471 if(get_col(env, n) == tgt_col) {
472 struct list_head tmp;
475 Try to change the color of the neighbor and record all nodes which
476 get changed in the tmp list. Add this list to the "changed" list for
477 that color. If we did not succeed to change the color of the neighbor,
478 we bail out and try the next color.
480 INIT_LIST_HEAD(&tmp);
481 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
482 list_splice(&tmp, &changed);
487 be_ifg_neighbours_break(ifg, it);
490 We managed to assign the target color to all neighbors, so from the perspective
491 of the current node, every thing was ok and we can return safely.
494 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
495 list_splice(&changed, parent_changed);
501 If not, that color did not succeed and we unfix all nodes we touched
502 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
505 reject_coloring(&changed);
511 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
513 co2_irn_t *ci = get_co2_irn(env, irn);
515 col_t col = get_col(env, irn);
517 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
519 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
526 list_add(&ci->changed_list, parent_changed);
530 /* The node has the color it should not have _and_ has not been visited yet. */
531 if(!color_is_fix(env, irn)) {
532 int n_regs = env->co->cls->n_regs;
533 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
535 /* Get the costs for giving the node a specific color. */
536 determine_color_costs(env, ci, csts);
538 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
539 csts[not_col].costs = INT_MAX;
541 /* sort the colors according costs, cheapest first. */
542 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
544 /* Try recoloring the node using the color list. */
545 res = recolor(env, irn, csts, parent_changed, depth);
548 /* If we came here, everything went ok. */
552 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
554 co2_irn_t *ci = get_co2_irn(env, irn);
555 col_t col = get_col(env, irn);
558 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
560 /* the node has the wanted color. That's fine, mark it as visited and return. */
565 list_add(&ci->changed_list, parent_changed);
572 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
573 int n_regs = env->co->cls->n_regs;
574 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
576 /* Get the costs for giving the node a specific color. */
577 single_color_cost(env, ci, tgt_col, seq);
579 /* Try recoloring the node using the color list. */
580 res = recolor(env, irn, seq, parent_changed, depth);
585 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
590 * Examine the costs of the current coloring concerning a MST subtree.
591 * @param ci The subtree root.
592 * @param col The color of @p ci.
593 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
595 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
597 int *front = FRONT_BASE(ci, col);
601 for(i = 0; i < ci->mst_n_childs; ++i) {
602 co2_cloud_irn_t *chld = ci->mst_childs[i];
603 col_t chld_col = front[i];
605 cost += examine_subtree_coloring(chld, chld_col);
606 cost += col != chld_col ? chld->mst_costs : 0;
613 * Determine color badnesses of a node.
614 * Badness means that it is unlikely that the node in question can
615 * obtain a color. The higher the badness, the more unlikely it is that
616 * the node can be assigned that color.
617 * @param ci The node.
618 * @param badness An integer array as long as there are registers.
619 * @note The array <code>badness</code> is not cleared.
621 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
623 co2_t *env = ci->cloud->env;
624 co2_irn_t *ir = &ci->inh;
625 int n_regs = env->n_regs;
626 be_ifg_t *ifg = env->co->cenv->ifg;
627 bitset_t *bs = bitset_alloca(n_regs);
633 admissible_colors(env, &ci->inh, bs);
635 bitset_foreach(bs, elm)
636 badness[elm] = ci->costs;
638 /* Use constrained/fixed interfering neighbors to influence the color badness */
639 it = be_ifg_neighbours_iter_alloca(ifg);
640 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
641 co2_irn_t *ni = get_co2_irn(env, irn);
643 admissible_colors(env, ni, bs);
644 if(bitset_popcnt(bs) == 1) {
645 bitset_pos_t c = bitset_next_set(bs, 0);
646 badness[c] += ci->costs;
650 col_t c = get_col(env, ni->irn);
651 badness[c] += ci->costs;
654 be_ifg_neighbours_break(ifg, it);
658 * Determine the badness of a MST subtree.
659 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
660 * @see node_color_badness() for a definition of badness.
661 * @param ci The root of the subtree.
662 * @param depth Depth for debugging purposes.
664 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
666 co2_t *env = ci->cloud->env;
669 node_color_badness(ci, ci->color_badness);
671 /* Collect the color badness for the whole subtree */
672 for(i = 0; i < ci->mst_n_childs; ++i) {
673 co2_cloud_irn_t *child = ci->mst_childs[i];
674 determine_color_badness(child, depth + 1);
676 for(j = 0; j < env->n_regs; ++j)
677 ci->color_badness[j] += child->color_badness[j];
680 for(j = 0; j < env->n_regs; ++j)
681 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
685 * Unfix all nodes in a MST subtree.
687 static void unfix_subtree(co2_cloud_irn_t *ci)
692 for(i = 0; i < ci->mst_n_childs; ++i)
693 unfix_subtree(ci->mst_childs[i]);
696 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
698 co2_t *env = ci->cloud->env;
699 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
700 int is_root = ci->mst_parent == ci;
701 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
702 int min_badness = INT_MAX;
703 int best_col_costs = INT_MAX;
705 int n_regs = env->n_regs;
706 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
708 struct list_head changed;
711 for(i = 0; i < n_regs; ++i) {
712 int badness = ci->color_badness[i];
715 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
717 min_badness = MIN(min_badness, badness);
720 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
721 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
722 seq[parent_col].costs = min_badness - 1;
724 /* Sort the colors. The will be processed in that ordering. */
725 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
727 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
728 INIT_LIST_HEAD(&changed);
729 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
730 col_t col = seq[i].col;
731 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
733 int subtree_costs, sum_costs;
735 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
738 INIT_LIST_HEAD(&changed);
739 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
741 materialize_coloring(&changed);
748 for(j = 0; j < ci->mst_n_childs; ++j) {
749 co2_cloud_irn_t *child = ci->mst_childs[j];
750 ok = coalesce_top_down(child, j, depth + 1) >= 0;
752 child->inh.fixed = 1;
757 /* If the subtree could not be colored, we have to try another color. */
761 subtree_costs = examine_subtree_coloring(ci, col);
762 sum_costs = subtree_costs + add_cost;
763 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
765 if(sum_costs < best_col_costs) {
767 best_col_costs = sum_costs;
768 ci->col_costs[col] = subtree_costs;
776 int *front = FRONT_BASE(ci->mst_parent, parent_col);
777 front[child_nr] = best_col;
783 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
785 be_ifg_t *ifg = env->co->cenv->ifg;
786 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
793 /* mark the node as visited and add it to the cloud. */
795 list_add(&ci->cloud_list, &cloud->members_head);
797 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
799 /* determine the nodes costs */
800 co_gs_foreach_neighb(a, n) {
802 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
803 if(be_ifg_connected(ifg, a->irn, n->irn))
804 cloud->inevit += n->costs;
807 /* add the node's cost to the total costs of the cloud. */
809 cloud->costs += costs;
810 cloud->n_constr += is_constrained(env, &ci->inh);
811 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
812 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
815 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
816 if(costs >= curr_costs) {
821 /* add all the neighbors of the node to the cloud. */
822 co_gs_foreach_neighb(a, n) {
823 affinity_node_t *an = get_affinity_info(env->co, n->irn);
825 populate_cloud(env, cloud, an, curr_costs);
829 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
831 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
835 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
836 memset(cloud, 0, sizeof(cloud[0]));
837 INIT_LIST_HEAD(&cloud->members_head);
838 INIT_LIST_HEAD(&cloud->list);
839 list_add(&cloud->list, &env->cloud_head);
840 cloud->best_costs = INT_MAX;
843 populate_cloud(env, cloud, a, 0);
844 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
846 /* Also allocate space for the node sequence and compute that sequence. */
847 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
850 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
852 cloud->seq[i++] = ci;
854 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
859 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
861 const ir_node *irn = ci->inh.irn;
862 int *front = FRONT_BASE(ci, col);
864 struct list_head changed;
866 INIT_LIST_HEAD(&changed);
868 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
869 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
870 // assert(ok && "Color changing may not fail while committing the coloring");
871 materialize_coloring(&changed);
873 for(i = 0; i < ci->mst_n_childs; ++i) {
874 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
878 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
880 while(ci != ci->mst_parent)
886 static void process_cloud(co2_cloud_t *cloud)
888 co2_t *env = cloud->env;
889 int n_regs = env->n_regs;
891 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
898 /* Collect all edges in the cloud on an obstack and sort the increasingly */
899 obstack_init(&cloud->obst);
900 for(i = 0; i < cloud->n_memb; ++i) {
901 co2_cloud_irn_t *ci = cloud->seq[i];
904 co_gs_foreach_neighb(ci->inh.aff, n) {
905 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
906 if(ci->index < ni->index) {
911 obstack_grow(&cloud->obst, &e, sizeof(e));
916 edges = obstack_finish(&cloud->obst);
917 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
919 /* Compute the maximum spanning tree using Kruskal/Union-Find */
920 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
921 for(i = 0; i < n_edges; ++i) {
922 edge_t *e = &edges[i];
923 co2_cloud_irn_t *rs = find_mst_root(e->src);
924 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
926 /* if the union/find roots are different */
928 int si = e->src->index;
929 int ti = e->tgt->index;
933 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
935 /* this edge is in the MST, so set it in the bitset. */
936 mst_edges[si * cloud->n_memb + ti] = e->costs;
937 mst_edges[ti * cloud->n_memb + si] = e->costs;
940 obstack_free(&cloud->obst, edges);
942 cloud->master->mst_parent = cloud->master;
943 cloud->mst_root = cloud->master;
944 q = new_pdeq1(cloud->master);
945 while(!pdeq_empty(q)) {
946 co2_cloud_irn_t *ci = pdeq_getl(q);
947 int ofs = ci->index * cloud->n_memb;
948 int end = ofs + cloud->n_memb;
951 ci->mst_n_childs = 0;
952 for(i = ofs; i < end; ++i) {
953 if(mst_edges[i] != 0) {
955 co2_cloud_irn_t *child = cloud->seq[i - ofs];
957 /* put the child to the worklist */
960 /* make ci the parent of the child and add the child to the children array of the parent */
961 child->mst_parent = ci;
962 child->mst_costs = mst_edges[i];
964 obstack_ptr_grow(&cloud->obst, child);
966 mst_edges[other * cloud->n_memb + ci->index] = 0;
971 obstack_ptr_grow(&cloud->obst, NULL);
972 ci->mst_childs = obstack_finish(&cloud->obst);
978 DBG((env->dbg, LEVEL_3, "mst:\n"));
979 for(i = 0; i < cloud->n_memb; ++i) {
980 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
981 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
984 for(i = 0; i < cloud->n_memb; ++i) {
985 co2_cloud_irn_t *ci = cloud->seq[i];
986 int n_childs = ci->mst_n_childs;
989 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
990 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
991 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
992 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
993 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
994 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
995 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
996 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
998 for(j = 0; j < env->n_regs; j++)
999 ci->col_costs[j] = INT_MAX;
1003 determine_color_badness(cloud->mst_root, 0);
1004 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1005 unfix_subtree(cloud->mst_root);
1006 apply_coloring(cloud->mst_root, best_col, 0);
1008 /* The coloring should represent the one with the best costs. */
1009 //materialize_coloring(&changed);
1010 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1011 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1013 /* Fix all nodes in the cloud. */
1014 for(i = 0; i < cloud->n_memb; ++i)
1015 cloud->seq[i]->inh.fixed = 1;
1017 /* Free all space used while optimizing this cloud. */
1018 obstack_free(&cloud->obst, NULL);
1021 static int cloud_costs(co2_cloud_t *cloud)
1026 for(i = 0; i < cloud->n_memb; ++i) {
1027 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1028 col_t col = get_col(cloud->env, ci->irn);
1029 co_gs_foreach_neighb(ci->aff, n) {
1030 col_t n_col = get_col(cloud->env, n->irn);
1031 costs += col != n_col ? n->costs : 0;
1038 static void process(co2_t *env)
1042 co2_cloud_t **clouds;
1047 int final_costs = 0;
1050 co_gs_foreach_aff_node(env->co, a) {
1051 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1060 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1061 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1063 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1065 for(i = 0; i < n_clouds; ++i) {
1066 init_costs += cloud_costs(clouds[i]);
1068 /* Process the cloud. */
1069 process_cloud(clouds[i]);
1071 all_costs += clouds[i]->costs;
1072 final_costs += cloud_costs(clouds[i]);
1074 /* Dump the IFG if the user demanded it. */
1075 if (dump_flags & DUMP_CLOUD) {
1079 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1080 f = fopen(buf, "wt");
1082 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1088 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1093 static void writeback_colors(co2_t *env)
1097 for(irn = env->touched; irn; irn = irn->touched_next) {
1098 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1099 arch_set_irn_register((ir_node*)irn->irn, reg);
1105 ___ _____ ____ ____ ___ _____ ____ _
1106 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1107 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1108 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1109 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1113 static const char *get_dot_color_name(size_t col)
1115 static const char *const names[] = {
1149 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1152 static const char *get_dot_shape_name(co2_irn_t *ci)
1154 const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
1156 if(arch_register_req_is(req, limited))
1168 static void ifg_dump_graph_attr(FILE *f, void *self)
1171 fprintf(f, "overlay=false");
1174 static int ifg_is_dump_node(void *self, ir_node *irn)
1177 return !arch_irn_is(irn, ignore);
1180 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1183 co2_irn_t *ci = get_co2_irn(env, irn);
1189 co2_cloud_irn_t *cci = (void *) ci;
1190 if (cci->cloud && cci->cloud->mst_root == cci)
1193 if(cci->cloud && cci->cloud->mst_root)
1194 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1197 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1198 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1201 static void ifg_dump_at_end(FILE *file, void *self)
1206 co_gs_foreach_aff_node(env->co, a) {
1207 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1208 int idx = get_irn_idx(a->irn);
1211 if(ai->mst_parent != ai)
1212 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1214 co_gs_foreach_neighb(a, n) {
1215 int nidx = get_irn_idx(n->irn);
1216 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1219 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1220 const char *arr = "arrowhead=dot arrowtail=dot";
1222 if(ci->mst_parent == ai)
1223 arr = "arrowtail=normal";
1224 else if(ai->mst_parent == ci)
1225 arr = "arrowhead=normal";
1227 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1234 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1236 ifg_dump_graph_attr,
1244 int co_solve_heuristic_new(copy_opt_t *co)
1250 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1254 env.n_regs = co->cls->n_regs;
1255 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1256 be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs);
1257 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1258 INIT_LIST_HEAD(&env.cloud_head);
1260 if(dump_flags & DUMP_BEFORE) {
1261 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1262 f = fopen(buf, "wt");
1264 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1271 if(dump_flags & DUMP_AFTER) {
1272 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1273 f = fopen(buf, "wt");
1275 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1280 writeback_colors(&env);
1281 phase_free(&env.ph);