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
29 #include "lc_opts_enum.h"
37 #include "raw_bitset.h"
40 #include "bitfiddle.h"
42 #include "irgraph_t.h"
47 #include "irnodemap.h"
52 #include "becopyopt.h"
53 #include "becopyopt_t.h"
54 #include "bechordal_t.h"
59 #define DUMP_ALL 2 * DUMP_CLOUD - 1
61 static unsigned dump_flags = 0;
62 static int subtree_iter = 4;
63 static int max_depth = 20;
64 static double constr_factor = 0.9;
66 static const lc_opt_enum_mask_items_t dump_items[] = {
67 { "before", DUMP_BEFORE },
68 { "after", DUMP_AFTER },
69 { "cloud", DUMP_CLOUD },
74 static lc_opt_enum_mask_var_t dump_var = {
75 &dump_flags, dump_items
78 static const lc_opt_table_entry_t options[] = {
79 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
80 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
81 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
82 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
88 / ___|| |_ __ _ _ __| |_
89 \___ \| __/ _` | '__| __|
90 ___) | || (_| | | | |_
91 |____/ \__\__,_|_| \__|
95 #define INFEASIBLE(cost) ((cost) == INT_MAX)
97 typedef unsigned col_t;
99 typedef struct co2_irn_t co2_irn_t;
100 typedef struct co2_cloud_t co2_cloud_t;
101 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 static co2_irn_t *get_co2_irn(co2_t *env, const ir_node *node)
180 co2_irn_t *ci = ir_nodemap_get(co2_irn_t, &env->map, node);
182 ci = OALLOCZ(&env->obst, co2_irn_t);
184 INIT_LIST_HEAD(&ci->changed_list);
185 ci->touched_next = env->touched;
186 ci->orig_col = get_irn_col(node);
191 ir_nodemap_insert(&env->map, node, ci);
196 static co2_cloud_irn_t *get_co2_cloud_irn(co2_t *env, const ir_node *node)
198 co2_cloud_irn_t *ci = ir_nodemap_get(co2_cloud_irn_t, &env->map, node);
200 ci = OALLOCZ(&env->obst, co2_cloud_irn_t);
202 INIT_LIST_HEAD(&ci->inh.changed_list);
203 ci->inh.touched_next = env->touched;
204 ci->inh.orig_col = get_irn_col(node);
205 env->touched = &ci->inh;
207 ci->inh.aff = get_affinity_info(env->co, node);
209 INIT_LIST_HEAD(&ci->cloud_list);
212 ir_nodemap_insert(&env->map, node, ci);
217 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
219 static int cmp_clouds_gt(const void *a, const void *b)
221 const co2_cloud_t * const *p = (const co2_cloud_t*const*)a;
222 const co2_cloud_t * const *q = (const co2_cloud_t*const*)b;
223 double c = CLOUD_WEIGHT(*p);
224 double d = CLOUD_WEIGHT(*q);
225 return QSORT_CMP(d, c);
229 * An order on color/costs pairs.
230 * If the costs are equal, we use the color as a kind of normalization.
232 static int col_cost_pair_lt(const void *a, const void *b)
234 const col_cost_pair_t *p = (const col_cost_pair_t*)a;
235 const col_cost_pair_t *q = (const col_cost_pair_t*)b;
238 return QSORT_CMP(c, d);
241 static int cmp_edges(const void *a, const void *b)
243 const edge_t *p = (const edge_t*)a;
244 const edge_t *q = (const edge_t*)b;
245 return QSORT_CMP(q->costs, p->costs);
248 static col_t get_col(co2_t *env, const ir_node *irn)
250 co2_irn_t *ci = get_co2_irn(env, irn);
251 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
254 static inline int color_is_fix(co2_t *env, const ir_node *irn)
256 co2_irn_t *ci = get_co2_irn(env, irn);
257 return ci->fixed || ci->tmp_fixed;
260 static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
262 if (ci->adm_cache == NULL) {
263 const arch_register_req_t *req;
264 ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
265 req = arch_get_irn_register_req(ci->irn);
267 if (arch_register_req_is(req, limited)) {
271 for (i = 0; i < n; ++i) {
272 if (rbitset_is_set(req->limited, i))
273 bitset_set(ci->adm_cache, i);
275 ci->is_constrained = 1;
277 bitset_copy(ci->adm_cache, env->allocatable_regs);
281 return ci->adm_cache;
284 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
286 bitset_copy(bs, get_adm(env, ci));
290 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
292 bitset_t *bs = get_adm(env, ci);
293 return bitset_is_set(bs, col);
296 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
300 return ci->is_constrained;
303 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
305 const arch_register_req_t *req = arch_get_irn_register_req(irn);
307 if (arch_register_req_is(req, limited)) {
308 unsigned n_regs = env->co->cls->n_regs;
309 unsigned n_constr = 0;
312 n_constr = rbitset_popcount(req->limited, n_regs);
313 for (i = 0; i < n_regs; ++i) {
314 if (rbitset_is_set(req->limited, i)) {
315 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
322 * Determine costs which shall indicate how cheap/expensive it is to try
323 * to assign a node some color.
324 * The costs are computed for all colors. INT_MAX means that it is impossible
325 * to give the node that specific color.
327 * @param env The co2 this pointer.
328 * @param irn The node.
329 * @param col_costs An array of colors x costs where the costs are written to.
331 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
333 const ir_node *irn = ci->irn;
334 be_ifg_t *ifg = env->co->cenv->ifg;
335 int n_regs = env->co->cls->n_regs;
336 affinity_node_t *a = ci->aff;
338 neighbours_iter_t it;
341 /* Put all forbidden colors into the aux bitset. */
342 bitset_t *const admissible = bitset_alloca(n_regs);
343 admissible_colors(env, ci, admissible);
345 for (i = 0; i < n_regs; ++i) {
346 col_costs[i].col = i;
347 col_costs[i].costs = 0;
351 co_gs_foreach_neighb(a, n) {
352 if (color_is_fix(env, n->irn)) {
353 col_t col = get_col(env, n->irn);
354 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
357 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
361 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
362 col_t col = get_col(env, pos);
363 if (color_is_fix(env, pos)) {
364 col_costs[col].costs = INT_MAX;
367 incur_constraint_costs(env, pos, col_costs, INT_MAX);
368 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
371 be_ifg_neighbours_break(&it);
373 /* Set the costs to infinity for each color which is not allowed at this node. */
374 bitset_foreach_clear(admissible, elm) {
375 col_costs[elm].costs = INT_MAX;
380 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
382 int n_regs = env->co->cls->n_regs;
385 for (i = 0; i < n_regs; ++i) {
387 seq[i].costs = INT_MAX;
391 assert(is_color_admissible(env, ci, col));
397 static void reject_coloring(struct list_head *h)
399 list_for_each_entry(co2_irn_t, pos, h, changed_list)
403 static void materialize_coloring(struct list_head *h)
405 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
406 pos->orig_col = pos->tmp_col;
411 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
413 static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
415 int n_regs = env->co->cls->n_regs;
416 be_ifg_t *ifg = env->co->cenv->ifg;
417 co2_irn_t *ci = get_co2_irn(env, irn);
422 if (depth >= max_depth)
425 for (i = 0; i < n_regs; ++i) {
426 col_t tgt_col = col_list[i].col;
427 unsigned costs = col_list[i].costs;
430 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);
614 neighbours_iter_t it;
616 admissible_colors(env, &ci->inh, bs);
617 bitset_foreach_clear(bs, elm)
618 badness[elm] = ci->costs;
620 /* Use constrained/fixed interfering neighbors to influence the color badness */
621 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
622 co2_irn_t *ni = get_co2_irn(env, irn);
624 admissible_colors(env, ni, bs);
625 if (bitset_popcount(bs) == 1) {
626 size_t c = bitset_next_set(bs, 0);
627 badness[c] += ci->costs;
630 else if (ni->fixed) {
631 col_t c = get_col(env, ni->irn);
632 badness[c] += ci->costs;
635 be_ifg_neighbours_break(&it);
639 * Determine the badness of a MST subtree.
640 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
641 * @see node_color_badness() for a definition of badness.
642 * @param ci The root of the subtree.
643 * @param depth Depth for debugging purposes.
645 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
647 co2_t *env = ci->cloud->env;
650 node_color_badness(ci, ci->color_badness);
652 /* Collect the color badness for the whole subtree */
653 for (i = 0; i < ci->mst_n_childs; ++i) {
654 co2_cloud_irn_t *child = ci->mst_childs[i];
655 determine_color_badness(child, depth + 1);
657 for (j = 0; j < env->n_regs; ++j)
658 ci->color_badness[j] += child->color_badness[j];
661 for (j = 0; j < env->n_regs; ++j)
662 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
666 * Unfix all nodes in a MST subtree.
668 static void unfix_subtree(co2_cloud_irn_t *ci)
673 for (i = 0; i < ci->mst_n_childs; ++i)
674 unfix_subtree(ci->mst_childs[i]);
677 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
679 co2_t *env = ci->cloud->env;
680 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
681 int is_root = ci->mst_parent == ci;
682 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
683 int min_badness = INT_MAX;
684 int best_col_costs = INT_MAX;
686 int n_regs = env->n_regs;
687 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
689 struct list_head changed;
692 for (i = 0; i < n_regs; ++i) {
693 int badness = ci->color_badness[i];
696 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
698 min_badness = MIN(min_badness, badness);
701 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
702 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
703 seq[parent_col].costs = min_badness - 1;
705 /* Sort the colors. The will be processed in that ordering. */
706 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
708 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
709 INIT_LIST_HEAD(&changed);
710 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
711 col_t col = seq[i].col;
712 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
714 int subtree_costs, sum_costs;
716 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
719 INIT_LIST_HEAD(&changed);
720 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
722 materialize_coloring(&changed);
729 for (j = 0; j < ci->mst_n_childs; ++j) {
730 co2_cloud_irn_t *child = ci->mst_childs[j];
731 ok = coalesce_top_down(child, j, depth + 1) >= 0;
733 child->inh.fixed = 1;
738 /* If the subtree could not be colored, we have to try another color. */
742 subtree_costs = examine_subtree_coloring(ci, col);
743 sum_costs = subtree_costs + add_cost;
744 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
746 if (sum_costs < best_col_costs) {
748 best_col_costs = sum_costs;
749 ci->col_costs[col] = subtree_costs;
757 int *front = FRONT_BASE(ci->mst_parent, parent_col);
758 front[child_nr] = best_col;
764 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
766 be_ifg_t *ifg = env->co->cenv->ifg;
767 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
773 /* mark the node as visited and add it to the cloud. */
775 list_add(&ci->cloud_list, &cloud->members_head);
777 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
779 /* determine the nodes costs */
780 co_gs_foreach_neighb(a, n) {
782 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
783 if (be_ifg_connected(ifg, a->irn, n->irn))
784 cloud->inevit += n->costs;
787 /* add the node's cost to the total costs of the cloud. */
789 cloud->costs += costs;
790 cloud->n_constr += is_constrained(env, &ci->inh);
791 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
792 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
795 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
796 if (costs >= curr_costs) {
801 /* add all the neighbors of the node to the cloud. */
802 co_gs_foreach_neighb(a, n) {
803 affinity_node_t *an = get_affinity_info(env->co, n->irn);
805 populate_cloud(env, cloud, an, curr_costs);
809 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
811 co2_cloud_t *cloud = OALLOC(&env->obst, co2_cloud_t);
814 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
815 memset(cloud, 0, sizeof(cloud[0]));
816 INIT_LIST_HEAD(&cloud->members_head);
817 INIT_LIST_HEAD(&cloud->list);
818 list_add(&cloud->list, &env->cloud_head);
819 cloud->best_costs = INT_MAX;
822 populate_cloud(env, cloud, a, 0);
823 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
825 /* Also allocate space for the node sequence and compute that sequence. */
826 cloud->seq = OALLOCN(&env->obst, co2_cloud_irn_t*, cloud->n_memb);
829 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
831 cloud->seq[i++] = ci;
833 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
838 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
840 const ir_node *irn = ci->inh.irn;
841 int *front = FRONT_BASE(ci, col);
843 struct list_head changed;
845 INIT_LIST_HEAD(&changed);
847 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
848 change_color_single(ci->cloud->env, irn, col, &changed, depth);
849 materialize_coloring(&changed);
851 for (i = 0; i < ci->mst_n_childs; ++i) {
852 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
856 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
858 while (ci != ci->mst_parent)
864 static void process_cloud(co2_cloud_t *cloud)
866 co2_t *env = cloud->env;
867 int n_regs = env->n_regs;
869 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
876 /* Collect all edges in the cloud on an obstack and sort the increasingly */
877 obstack_init(&cloud->obst);
878 for (i = 0; i < cloud->n_memb; ++i) {
879 co2_cloud_irn_t *ci = cloud->seq[i];
881 co_gs_foreach_neighb(ci->inh.aff, n) {
882 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
883 if (ci->index < ni->index) {
888 obstack_grow(&cloud->obst, &e, sizeof(e));
893 edges = (edge_t*)obstack_finish(&cloud->obst);
894 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
896 /* Compute the maximum spanning tree using Kruskal/Union-Find */
897 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
898 for (i = 0; i < n_edges; ++i) {
899 edge_t *e = &edges[i];
900 co2_cloud_irn_t *rs = find_mst_root(e->src);
901 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
903 /* if the union/find roots are different */
905 int si = e->src->index;
906 int ti = e->tgt->index;
910 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
912 /* this edge is in the MST, so set it in the bitset. */
913 mst_edges[si * cloud->n_memb + ti] = e->costs;
914 mst_edges[ti * cloud->n_memb + si] = e->costs;
917 obstack_free(&cloud->obst, edges);
919 cloud->master->mst_parent = cloud->master;
920 cloud->mst_root = cloud->master;
921 q = new_pdeq1(cloud->master);
922 while (!pdeq_empty(q)) {
923 co2_cloud_irn_t *ci = (co2_cloud_irn_t*)pdeq_getl(q);
924 int ofs = ci->index * cloud->n_memb;
925 int end = ofs + cloud->n_memb;
928 ci->mst_n_childs = 0;
929 for (i = ofs; i < end; ++i) {
930 if (mst_edges[i] != 0) {
932 co2_cloud_irn_t *child = cloud->seq[i - ofs];
934 /* put the child to the worklist */
937 /* make ci the parent of the child and add the child to the children array of the parent */
938 child->mst_parent = ci;
939 child->mst_costs = mst_edges[i];
941 obstack_ptr_grow(&cloud->obst, child);
943 mst_edges[other * cloud->n_memb + ci->index] = 0;
948 obstack_ptr_grow(&cloud->obst, NULL);
949 ci->mst_childs = (co2_cloud_irn_t**)obstack_finish(&cloud->obst);
955 DBG((env->dbg, LEVEL_3, "mst:\n"));
956 for (i = 0; i < cloud->n_memb; ++i) {
957 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i];)
958 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
961 for (i = 0; i < cloud->n_memb; ++i) {
962 co2_cloud_irn_t *ci = cloud->seq[i];
963 int n_childs = ci->mst_n_childs;
966 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
967 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
968 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
969 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
971 for (j = 0; j < env->n_regs; j++)
972 ci->col_costs[j] = INT_MAX;
975 determine_color_badness(cloud->mst_root, 0);
976 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
977 unfix_subtree(cloud->mst_root);
978 apply_coloring(cloud->mst_root, best_col, 0);
980 /* The coloring should represent the one with the best costs. */
981 //materialize_coloring(&changed);
982 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
983 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
985 /* Fix all nodes in the cloud. */
986 for (i = 0; i < cloud->n_memb; ++i)
987 cloud->seq[i]->inh.fixed = 1;
989 /* Free all space used while optimizing this cloud. */
990 obstack_free(&cloud->obst, NULL);
993 static int cloud_costs(co2_cloud_t *cloud)
997 for (i = 0; i < cloud->n_memb; ++i) {
998 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
999 col_t col = get_col(cloud->env, ci->irn);
1000 co_gs_foreach_neighb(ci->aff, n) {
1001 col_t n_col = get_col(cloud->env, n->irn);
1002 costs += col != n_col ? n->costs : 0;
1009 static void writeback_colors(co2_t *env)
1013 for (irn = env->touched; irn; irn = irn->touched_next) {
1014 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1015 arch_set_irn_register((ir_node*)irn->irn, reg);
1019 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]);
1054 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1059 static int co_solve_heuristic_new(copy_opt_t *co)
1063 ir_nodemap_init(&env.map, co->irg);
1064 obstack_init(&env.obst);
1068 env.n_regs = co->cls->n_regs;
1069 env.allocatable_regs = bitset_alloca(co->cls->n_regs);
1070 be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
1071 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1072 INIT_LIST_HEAD(&env.cloud_head);
1076 writeback_colors(&env);
1077 obstack_free(&env.obst, NULL);
1078 ir_nodemap_destroy(&env.map);
1082 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2)
1083 void be_init_copyheur2(void)
1085 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1086 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1087 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1088 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1090 static co_algo_info copyheur = {
1091 co_solve_heuristic_new, 0
1094 lc_opt_add_table(co2_grp, options);
1095 be_register_copyopt("heur2", ©heur);