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 *ignore_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->ignore_regs);
268 bitset_flip_all(ci->adm_cache);
272 return ci->adm_cache;
275 static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
277 bitset_copy(bs, get_adm(env, ci));
281 static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
283 bitset_t *bs = get_adm(env, ci);
284 return bitset_is_set(bs, col);
287 static inline int is_constrained(co2_t *env, co2_irn_t *ci)
291 return ci->is_constrained;
294 static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
296 const arch_register_req_t *req = arch_get_register_req_out(irn);
298 if (arch_register_req_is(req, limited)) {
299 unsigned n_regs = env->co->cls->n_regs;
300 unsigned n_constr = 0;
303 n_constr = rbitset_popcount(req->limited, n_regs);
304 for (i = 0; i < n_regs; ++i) {
305 if (rbitset_is_set(req->limited, i)) {
306 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
313 * Determine costs which shall indicate how cheap/expensive it is to try
314 * to assign a node some color.
315 * The costs are computed for all colors. INT_MAX means that it is impossible
316 * to give the node that specific color.
318 * @param env The co2 this pointer.
319 * @param irn The node.
320 * @param col_costs An array of colors x costs where the costs are written to.
322 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
324 const ir_node *irn = ci->irn;
325 be_ifg_t *ifg = env->co->cenv->ifg;
326 int n_regs = env->co->cls->n_regs;
327 bitset_t *forb = bitset_alloca(n_regs);
328 affinity_node_t *a = ci->aff;
332 neighbours_iter_t it;
335 /* Put all forbidden colors into the aux bitset. */
336 admissible_colors(env, ci, forb);
337 bitset_flip_all(forb);
339 for (i = 0; i < n_regs; ++i) {
340 col_costs[i].col = i;
341 col_costs[i].costs = 0;
347 co_gs_foreach_neighb(a, n) {
348 if (color_is_fix(env, n->irn)) {
349 col_t col = get_col(env, n->irn);
350 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
353 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
357 be_ifg_foreach_neighbour(ifg, &it, irn, pos) {
358 col_t col = get_col(env, pos);
359 if (color_is_fix(env, pos)) {
360 col_costs[col].costs = INT_MAX;
363 incur_constraint_costs(env, pos, col_costs, INT_MAX);
364 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
367 be_ifg_neighbours_break(&it);
369 /* Set the costs to infinity for each color which is not allowed at this node. */
370 bitset_foreach(forb, elm) {
371 col_costs[elm].costs = INT_MAX;
376 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
378 int n_regs = env->co->cls->n_regs;
381 for (i = 0; i < n_regs; ++i) {
383 seq[i].costs = INT_MAX;
387 assert(is_color_admissible(env, ci, col));
393 static void reject_coloring(struct list_head *h)
397 list_for_each_entry(co2_irn_t, pos, h, changed_list)
401 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;
432 neighbours_iter_t it;
434 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
436 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
437 if (INFEASIBLE(costs)) {
438 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
443 /* Set the new color of the node and mark the node as temporarily fixed. */
444 ci->tmp_col = tgt_col;
448 If that color has costs > 0, there's at least one neighbor having that color,
449 so we will try to change the neighbors' colors, too.
451 INIT_LIST_HEAD(&changed);
452 list_add(&ci->changed_list, &changed);
454 be_ifg_foreach_neighbour(ifg, &it, irn, n) {
456 /* try to re-color the neighbor if it has the target color. */
457 if (get_col(env, n) == tgt_col) {
458 struct list_head tmp;
461 Try to change the color of the neighbor and record all nodes which
462 get changed in the tmp list. Add this list to the "changed" list for
463 that color. If we did not succeed to change the color of the neighbor,
464 we bail out and try the next color.
466 INIT_LIST_HEAD(&tmp);
467 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
468 list_splice(&tmp, &changed);
473 be_ifg_neighbours_break(&it);
476 We managed to assign the target color to all neighbors, so from the perspective
477 of the current node, every thing was ok and we can return safely.
480 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
481 list_splice(&changed, parent_changed);
487 If not, that color did not succeed and we unfix all nodes we touched
488 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
491 reject_coloring(&changed);
497 static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
499 co2_irn_t *ci = get_co2_irn(env, irn);
501 col_t col = get_col(env, irn);
503 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
505 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
506 if (col != not_col) {
507 if (!ci->tmp_fixed) {
512 list_add(&ci->changed_list, parent_changed);
516 /* The node has the color it should not have _and_ has not been visited yet. */
517 if (!color_is_fix(env, irn)) {
518 int n_regs = env->co->cls->n_regs;
519 col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
521 /* Get the costs for giving the node a specific color. */
522 determine_color_costs(env, ci, csts);
524 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
525 csts[not_col].costs = INT_MAX;
527 /* sort the colors according costs, cheapest first. */
528 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
530 /* Try recoloring the node using the color list. */
531 res = recolor(env, irn, csts, parent_changed, depth);
534 /* If we came here, everything went ok. */
538 static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
540 co2_irn_t *ci = get_co2_irn(env, irn);
541 col_t col = get_col(env, irn);
544 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
546 /* the node has the wanted color. That's fine, mark it as visited and return. */
547 if (col == tgt_col) {
548 if (!ci->tmp_fixed) {
551 list_add(&ci->changed_list, parent_changed);
558 if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
559 int n_regs = env->co->cls->n_regs;
560 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
562 /* Get the costs for giving the node a specific color. */
563 single_color_cost(env, ci, tgt_col, seq);
565 /* Try recoloring the node using the color list. */
566 res = recolor(env, irn, seq, parent_changed, depth);
571 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
576 * Examine the costs of the current coloring concerning a MST subtree.
577 * @param ci The subtree root.
578 * @param col The color of @p ci.
579 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
581 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
583 int *front = FRONT_BASE(ci, col);
587 for (i = 0; i < ci->mst_n_childs; ++i) {
588 co2_cloud_irn_t *chld = ci->mst_childs[i];
589 col_t chld_col = front[i];
591 cost += examine_subtree_coloring(chld, chld_col);
592 cost += col != chld_col ? chld->mst_costs : 0;
599 * Determine color badnesses of a node.
600 * Badness means that it is unlikely that the node in question can
601 * obtain a color. The higher the badness, the more unlikely it is that
602 * the node can be assigned that color.
603 * @param ci The node.
604 * @param badness An integer array as long as there are registers.
605 * @note The array <code>badness</code> is not cleared.
607 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
609 co2_t *env = ci->cloud->env;
610 co2_irn_t *ir = &ci->inh;
611 int n_regs = env->n_regs;
612 be_ifg_t *ifg = env->co->cenv->ifg;
613 bitset_t *bs = bitset_alloca(n_regs);
617 neighbours_iter_t it;
619 admissible_colors(env, &ci->inh, bs);
621 bitset_foreach(bs, elm)
622 badness[elm] = ci->costs;
624 /* Use constrained/fixed interfering neighbors to influence the color badness */
625 be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
626 co2_irn_t *ni = get_co2_irn(env, irn);
628 admissible_colors(env, ni, bs);
629 if (bitset_popcount(bs) == 1) {
630 unsigned c = bitset_next_set(bs, 0);
631 badness[c] += ci->costs;
634 else if (ni->fixed) {
635 col_t c = get_col(env, ni->irn);
636 badness[c] += ci->costs;
639 be_ifg_neighbours_break(&it);
643 * Determine the badness of a MST subtree.
644 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
645 * @see node_color_badness() for a definition of badness.
646 * @param ci The root of the subtree.
647 * @param depth Depth for debugging purposes.
649 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
651 co2_t *env = ci->cloud->env;
654 node_color_badness(ci, ci->color_badness);
656 /* Collect the color badness for the whole subtree */
657 for (i = 0; i < ci->mst_n_childs; ++i) {
658 co2_cloud_irn_t *child = ci->mst_childs[i];
659 determine_color_badness(child, depth + 1);
661 for (j = 0; j < env->n_regs; ++j)
662 ci->color_badness[j] += child->color_badness[j];
665 for (j = 0; j < env->n_regs; ++j)
666 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
670 * Unfix all nodes in a MST subtree.
672 static void unfix_subtree(co2_cloud_irn_t *ci)
677 for (i = 0; i < ci->mst_n_childs; ++i)
678 unfix_subtree(ci->mst_childs[i]);
681 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
683 co2_t *env = ci->cloud->env;
684 col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
685 int is_root = ci->mst_parent == ci;
686 col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
687 int min_badness = INT_MAX;
688 int best_col_costs = INT_MAX;
690 int n_regs = env->n_regs;
691 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
693 struct list_head changed;
696 for (i = 0; i < n_regs; ++i) {
697 int badness = ci->color_badness[i];
700 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
702 min_badness = MIN(min_badness, badness);
705 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
706 if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
707 seq[parent_col].costs = min_badness - 1;
709 /* Sort the colors. The will be processed in that ordering. */
710 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
712 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
713 INIT_LIST_HEAD(&changed);
714 for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
715 col_t col = seq[i].col;
716 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
718 int subtree_costs, sum_costs;
720 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
723 INIT_LIST_HEAD(&changed);
724 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
726 materialize_coloring(&changed);
733 for (j = 0; j < ci->mst_n_childs; ++j) {
734 co2_cloud_irn_t *child = ci->mst_childs[j];
735 ok = coalesce_top_down(child, j, depth + 1) >= 0;
737 child->inh.fixed = 1;
742 /* If the subtree could not be colored, we have to try another color. */
746 subtree_costs = examine_subtree_coloring(ci, col);
747 sum_costs = subtree_costs + add_cost;
748 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
750 if (sum_costs < best_col_costs) {
752 best_col_costs = sum_costs;
753 ci->col_costs[col] = subtree_costs;
761 int *front = FRONT_BASE(ci->mst_parent, parent_col);
762 front[child_nr] = best_col;
768 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
770 be_ifg_t *ifg = env->co->cenv->ifg;
771 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
778 /* mark the node as visited and add it to the cloud. */
780 list_add(&ci->cloud_list, &cloud->members_head);
782 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
784 /* determine the nodes costs */
785 co_gs_foreach_neighb(a, n) {
787 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
788 if (be_ifg_connected(ifg, a->irn, n->irn))
789 cloud->inevit += n->costs;
792 /* add the node's cost to the total costs of the cloud. */
794 cloud->costs += costs;
795 cloud->n_constr += is_constrained(env, &ci->inh);
796 cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
797 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
800 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
801 if (costs >= curr_costs) {
806 /* add all the neighbors of the node to the cloud. */
807 co_gs_foreach_neighb(a, n) {
808 affinity_node_t *an = get_affinity_info(env->co, n->irn);
810 populate_cloud(env, cloud, an, curr_costs);
814 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
816 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
820 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
821 memset(cloud, 0, sizeof(cloud[0]));
822 INIT_LIST_HEAD(&cloud->members_head);
823 INIT_LIST_HEAD(&cloud->list);
824 list_add(&cloud->list, &env->cloud_head);
825 cloud->best_costs = INT_MAX;
828 populate_cloud(env, cloud, a, 0);
829 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
831 /* Also allocate space for the node sequence and compute that sequence. */
832 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
835 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
837 cloud->seq[i++] = ci;
839 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
844 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
846 const ir_node *irn = ci->inh.irn;
847 int *front = FRONT_BASE(ci, col);
849 struct list_head changed;
851 INIT_LIST_HEAD(&changed);
853 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
854 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
855 // assert(ok && "Color changing may not fail while committing the coloring");
856 materialize_coloring(&changed);
858 for (i = 0; i < ci->mst_n_childs; ++i) {
859 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
863 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
865 while (ci != ci->mst_parent)
871 static void process_cloud(co2_cloud_t *cloud)
873 co2_t *env = cloud->env;
874 int n_regs = env->n_regs;
876 int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
883 /* Collect all edges in the cloud on an obstack and sort the increasingly */
884 obstack_init(&cloud->obst);
885 for (i = 0; i < cloud->n_memb; ++i) {
886 co2_cloud_irn_t *ci = cloud->seq[i];
889 co_gs_foreach_neighb(ci->inh.aff, n) {
890 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
891 if (ci->index < ni->index) {
896 obstack_grow(&cloud->obst, &e, sizeof(e));
901 edges = obstack_finish(&cloud->obst);
902 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
904 /* Compute the maximum spanning tree using Kruskal/Union-Find */
905 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
906 for (i = 0; i < n_edges; ++i) {
907 edge_t *e = &edges[i];
908 co2_cloud_irn_t *rs = find_mst_root(e->src);
909 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
911 /* if the union/find roots are different */
913 int si = e->src->index;
914 int ti = e->tgt->index;
918 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
920 /* this edge is in the MST, so set it in the bitset. */
921 mst_edges[si * cloud->n_memb + ti] = e->costs;
922 mst_edges[ti * cloud->n_memb + si] = e->costs;
925 obstack_free(&cloud->obst, edges);
927 cloud->master->mst_parent = cloud->master;
928 cloud->mst_root = cloud->master;
929 q = new_pdeq1(cloud->master);
930 while (!pdeq_empty(q)) {
931 co2_cloud_irn_t *ci = pdeq_getl(q);
932 int ofs = ci->index * cloud->n_memb;
933 int end = ofs + cloud->n_memb;
936 ci->mst_n_childs = 0;
937 for (i = ofs; i < end; ++i) {
938 if (mst_edges[i] != 0) {
940 co2_cloud_irn_t *child = cloud->seq[i - ofs];
942 /* put the child to the worklist */
945 /* make ci the parent of the child and add the child to the children array of the parent */
946 child->mst_parent = ci;
947 child->mst_costs = mst_edges[i];
949 obstack_ptr_grow(&cloud->obst, child);
951 mst_edges[other * cloud->n_memb + ci->index] = 0;
956 obstack_ptr_grow(&cloud->obst, NULL);
957 ci->mst_childs = obstack_finish(&cloud->obst);
963 DBG((env->dbg, LEVEL_3, "mst:\n"));
964 for (i = 0; i < cloud->n_memb; ++i) {
965 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
966 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
969 for (i = 0; i < cloud->n_memb; ++i) {
970 co2_cloud_irn_t *ci = cloud->seq[i];
971 int n_childs = ci->mst_n_childs;
974 ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
975 ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
976 ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
977 ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
979 for (j = 0; j < env->n_regs; j++)
980 ci->col_costs[j] = INT_MAX;
983 determine_color_badness(cloud->mst_root, 0);
984 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
985 unfix_subtree(cloud->mst_root);
986 apply_coloring(cloud->mst_root, best_col, 0);
988 /* The coloring should represent the one with the best costs. */
989 //materialize_coloring(&changed);
990 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
991 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
993 /* Fix all nodes in the cloud. */
994 for (i = 0; i < cloud->n_memb; ++i)
995 cloud->seq[i]->inh.fixed = 1;
997 /* Free all space used while optimizing this cloud. */
998 obstack_free(&cloud->obst, NULL);
1001 static int cloud_costs(co2_cloud_t *cloud)
1006 for (i = 0; i < cloud->n_memb; ++i) {
1007 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1008 col_t col = get_col(cloud->env, ci->irn);
1009 co_gs_foreach_neighb(ci->aff, n) {
1010 col_t n_col = get_col(cloud->env, n->irn);
1011 costs += col != n_col ? n->costs : 0;
1018 static void process(co2_t *env)
1022 co2_cloud_t **clouds;
1027 int final_costs = 0;
1030 co_gs_foreach_aff_node(env->co, a) {
1031 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1040 clouds = XMALLOCN(co2_cloud_t*, n_clouds);
1041 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1043 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1045 for (i = 0; i < n_clouds; ++i) {
1046 init_costs += cloud_costs(clouds[i]);
1048 /* Process the cloud. */
1049 process_cloud(clouds[i]);
1051 all_costs += clouds[i]->costs;
1052 final_costs += cloud_costs(clouds[i]);
1054 /* Dump the IFG if the user demanded it. */
1055 if (dump_flags & DUMP_CLOUD) {
1059 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1060 f = fopen(buf, "wt");
1062 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1068 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1073 static void writeback_colors(co2_t *env)
1077 for (irn = env->touched; irn; irn = irn->touched_next) {
1078 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1079 arch_set_irn_register((ir_node*)irn->irn, reg);
1085 ___ _____ ____ ____ ___ _____ ____ _
1086 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1087 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1088 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1089 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1093 static const char *get_dot_color_name(size_t col)
1095 static const char *const names[] = {
1129 return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
1132 static const char *get_dot_shape_name(co2_irn_t *ci)
1134 const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
1136 if (arch_register_req_is(req, limited))
1148 static void ifg_dump_graph_attr(FILE *f, void *self)
1151 fprintf(f, "overlay=false");
1154 static int ifg_is_dump_node(void *self, ir_node *irn)
1156 const arch_register_req_t *req = arch_get_register_req_out(irn);
1158 return !(req->type & arch_register_req_type_ignore);
1161 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1164 co2_irn_t *ci = get_co2_irn(env, irn);
1170 co2_cloud_irn_t *cci = (void *) ci;
1171 if (cci->cloud && cci->cloud->mst_root == cci)
1174 if (cci->cloud && cci->cloud->mst_root)
1175 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1178 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1179 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
1182 static void ifg_dump_at_end(FILE *file, void *self)
1187 co_gs_foreach_aff_node(env->co, a) {
1188 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1189 int idx = get_irn_idx(a->irn);
1192 if (ai->mst_parent != ai)
1193 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1195 co_gs_foreach_neighb(a, n) {
1196 int nidx = get_irn_idx(n->irn);
1197 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1200 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1201 const char *arr = "arrowhead=dot arrowtail=dot";
1203 if (ci->mst_parent == ai)
1204 arr = "arrowtail=normal";
1205 else if (ai->mst_parent == ci)
1206 arr = "arrowhead=normal";
1208 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1215 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1217 ifg_dump_graph_attr,
1224 int co_solve_heuristic_new(copy_opt_t *co)
1230 phase_init(&env.ph, co->cenv->irg, co2_irn_init);
1234 env.n_regs = co->cls->n_regs;
1235 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1236 be_put_ignore_regs(co->cenv->irg, co->cls, env.ignore_regs);
1237 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1238 INIT_LIST_HEAD(&env.cloud_head);
1240 if (dump_flags & DUMP_BEFORE) {
1241 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1242 f = fopen(buf, "wt");
1244 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1251 if (dump_flags & DUMP_AFTER) {
1252 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1253 f = fopen(buf, "wt");
1255 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1260 writeback_colors(&env);
1261 phase_deinit(&env.ph);
1265 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
1266 void be_init_copyheur2(void)
1268 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
1269 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
1270 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
1271 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
1273 static co_algo_info copyheur = {
1274 co_solve_heuristic_new, 0
1277 lc_opt_add_table(co2_grp, options);
1278 be_register_copyopt("heur2", ©heur);