2 * Copyright (C) 1995-2007 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
31 #include <libcore/lc_opts.h>
32 #include <libcore/lc_opts_enum.h>
40 #include "raw_bitset.h"
43 #include "bitfiddle.h"
45 #include "irphase_t.h"
46 #include "irgraph_t.h"
54 #include "becopyopt.h"
55 #include "becopyopt_t.h"
56 #include "bechordal_t.h"
62 #define DUMP_ALL 2 * DUMP_CLOUD - 1
64 static unsigned dump_flags = 0;
65 static int subtree_iter = 4;
66 static int max_depth = 20;
67 static double constr_factor = 0.9;
69 /* Options using libcore */
70 static const lc_opt_enum_mask_items_t dump_items[] = {
71 { "before", DUMP_BEFORE },
72 { "after", DUMP_AFTER },
73 { "cloud", DUMP_CLOUD },
78 static lc_opt_enum_mask_var_t dump_var = {
79 &dump_flags, dump_items
82 static const lc_opt_table_entry_t options[] = {
83 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
84 LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
85 LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
86 LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
90 void be_init_copyheur2(void)
92 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
93 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
94 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
95 lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
97 lc_opt_add_table(co2_grp, options);
100 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
104 / ___|| |_ __ _ _ __| |_
105 \___ \| __/ _` | '__| __|
106 ___) | || (_| | | | |_
107 |____/ \__\__,_|_| \__|
111 #define INFEASIBLE(cost) ((cost) == INT_MAX)
113 static be_ifg_dump_dot_cb_t ifg_dot_cb;
115 typedef unsigned col_t;
117 typedef struct _co2_irn_t co2_irn_t;
118 typedef struct _co2_cloud_t co2_cloud_t;
119 typedef struct _co2_cloud_irn_t co2_cloud_irn_t;
129 bitset_t *ignore_regs;
133 struct list_head cloud_head;
134 DEBUG_ONLY(firm_dbg_module_t *dbg;)
139 affinity_node_t *aff;
140 co2_irn_t *touched_next;
143 int last_color_change;
146 unsigned tmp_fixed : 1;
147 unsigned is_constrained : 1;
148 struct list_head changed_list;
151 struct _co2_cloud_irn_t {
152 struct _co2_irn_t inh;
156 co2_cloud_irn_t *mst_parent;
159 co2_cloud_irn_t **mst_childs;
164 col_cost_pair_t *tmp_coloring;
165 struct list_head cloud_list;
166 struct list_head mst_list;
169 struct _co2_cloud_t {
181 co2_cloud_irn_t *master;
182 co2_cloud_irn_t *mst_root;
183 co2_cloud_irn_t **seq;
184 struct list_head members_head;
185 struct list_head list;
189 co2_cloud_irn_t *src, *tgt;
193 #define FRONT_BASE(ci,col) ((ci)->fronts + col * (ci)->mst_n_childs)
195 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
196 #define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
198 static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
200 co2_t *env = (co2_t *) ph;
201 affinity_node_t *a = get_affinity_info(env->co, irn);
202 size_t size = a ? sizeof(co2_cloud_irn_t) : sizeof(co2_irn_t);
203 co2_irn_t *ci = data ? data : phase_alloc(ph, size);
206 INIT_LIST_HEAD(&ci->changed_list);
207 ci->touched_next = env->touched;
208 ci->orig_col = get_irn_col(env->co, irn);
214 co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
215 INIT_LIST_HEAD(&cci->cloud_list);
216 cci->mst_parent = cci;
222 #define CLOUD_WEIGHT(c) ((1 - constr_factor) * (c)->costs + constr_factor * (c)->freedom)
224 static int cmp_clouds_gt(const void *a, const void *b)
226 const co2_cloud_t * const *p = a;
227 const co2_cloud_t * const *q = b;
228 double c = CLOUD_WEIGHT(*p);
229 double d = CLOUD_WEIGHT(*q);
230 return QSORT_CMP(d, c);
234 * An order on color/costs pairs.
235 * If the costs are equal, we use the color as a kind of normalization.
237 static int col_cost_pair_lt(const void *a, const void *b)
239 const col_cost_pair_t *p = a;
240 const col_cost_pair_t *q = b;
243 return QSORT_CMP(c, d);
246 int cmp_edges(const void *a, const void *b)
250 return QSORT_CMP(q->costs, p->costs);
253 static col_t get_col(co2_t *env, ir_node *irn)
255 co2_irn_t *ci = get_co2_irn(env, irn);
256 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
259 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
261 co2_irn_t *ci = get_co2_irn(env, irn);
262 return ci->fixed || ci->tmp_fixed;
265 static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
267 if(ci->adm_cache == NULL) {
268 const arch_register_req_t *req;
269 ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
270 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
272 if(arch_register_req_is(req, limited)) {
276 for(i = 0; i < n; ++i) {
277 if(rbitset_is_set(req->limited, i))
278 bitset_set(ci->adm_cache, i);
280 ci->is_constrained = 1;
282 bitset_copy(ci->adm_cache, env->ignore_regs);
283 bitset_flip_all(ci->adm_cache);
287 return ci->adm_cache;
290 static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
292 bitset_copy(bs, get_adm(env, ci));
296 static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
298 bitset_t *bs = get_adm(env, ci);
299 return bitset_is_set(bs, col);
302 static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
306 return ci->is_constrained;
309 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
311 const arch_register_req_t *req;
313 req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
315 if (arch_register_req_is(req, limited)) {
316 unsigned n_regs = env->co->cls->n_regs;
317 unsigned n_constr = 0;
320 n_constr = rbitset_popcnt(req->limited, n_regs);
321 for (i = 0; i < n_regs; ++i) {
322 if (rbitset_is_set(req->limited, i)) {
323 col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
330 * Determine costs which shall indicate how cheap/expensive it is to try
331 * to assign a node some color.
332 * The costs are computed for all colors. INT_MAX means that it is impossible
333 * to give the node that specific color.
335 * @param env The co2 this pointer.
336 * @param irn The node.
337 * @param col_costs An array of colors x costs where the costs are written to.
339 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
341 ir_node *irn = ci->irn;
342 be_ifg_t *ifg = env->co->cenv->ifg;
343 int n_regs = env->co->cls->n_regs;
344 bitset_t *forb = bitset_alloca(n_regs);
345 affinity_node_t *a = ci->aff;
352 /* Put all forbidden colors into the aux bitset. */
353 admissible_colors(env, ci, forb);
354 bitset_flip_all(forb);
356 for(i = 0; i < n_regs; ++i) {
357 col_costs[i].col = i;
358 col_costs[i].costs = 0;
364 co_gs_foreach_neighb(a, n) {
365 if(color_is_fix(env, n->irn)) {
366 col_t col = get_col(env, n->irn);
367 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
370 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
374 it = be_ifg_neighbours_iter_alloca(ifg);
375 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
376 col_t col = get_col(env, pos);
377 if(color_is_fix(env, pos)) {
378 col_costs[col].costs = INT_MAX;
381 incur_constraint_costs(env, pos, col_costs, INT_MAX);
382 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
385 be_ifg_neighbours_break(ifg, it);
387 /* Set the costs to infinity for each color which is not allowed at this node. */
388 bitset_foreach(forb, elm) {
389 col_costs[elm].costs = INT_MAX;
394 static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
396 int n_regs = env->co->cls->n_regs;
399 for(i = 0; i < n_regs; ++i) {
401 seq[i].costs = INT_MAX;
404 assert(is_color_admissible(env, ci, col));
410 static void reject_coloring(struct list_head *h)
414 list_for_each_entry(co2_irn_t, pos, h, changed_list)
418 static void materialize_coloring(struct list_head *h)
422 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
423 pos->orig_col = pos->tmp_col;
428 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
430 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
432 int n_regs = env->co->cls->n_regs;
433 be_ifg_t *ifg = env->co->cenv->ifg;
434 co2_irn_t *ci = get_co2_irn(env, irn);
439 if(depth >= max_depth)
442 for(i = 0; i < n_regs; ++i) {
443 col_t tgt_col = col_list[i].col;
444 unsigned costs = col_list[i].costs;
447 struct list_head changed;
451 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
453 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
454 if(INFEASIBLE(costs)) {
455 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
460 /* Set the new color of the node and mark the node as temporarily fixed. */
461 ci->tmp_col = tgt_col;
465 If that color has costs > 0, there's at least one neighbor having that color,
466 so we will try to change the neighbors' colors, too.
468 INIT_LIST_HEAD(&changed);
469 list_add(&ci->changed_list, &changed);
471 it = be_ifg_neighbours_iter_alloca(ifg);
472 be_ifg_foreach_neighbour(ifg, it, irn, n) {
474 /* try to re-color the neighbor if it has the target color. */
475 if(get_col(env, n) == tgt_col) {
476 struct list_head tmp;
479 Try to change the color of the neighbor and record all nodes which
480 get changed in the tmp list. Add this list to the "changed" list for
481 that color. If we did not succeed to change the color of the neighbor,
482 we bail out and try the next color.
484 INIT_LIST_HEAD(&tmp);
485 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
486 list_splice(&tmp, &changed);
491 be_ifg_neighbours_break(ifg, it);
494 We managed to assign the target color to all neighbors, so from the perspective
495 of the current node, every thing was ok and we can return safely.
498 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
499 list_splice(&changed, parent_changed);
505 If not, that color did not succeed and we unfix all nodes we touched
506 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
509 reject_coloring(&changed);
515 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
517 co2_irn_t *ci = get_co2_irn(env, irn);
519 col_t col = get_col(env, irn);
521 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
523 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
530 list_add(&ci->changed_list, parent_changed);
534 /* The node has the color it should not have _and_ has not been visited yet. */
535 if(!color_is_fix(env, irn)) {
536 int n_regs = env->co->cls->n_regs;
537 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
539 /* Get the costs for giving the node a specific color. */
540 determine_color_costs(env, ci, csts);
542 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
543 csts[not_col].costs = INT_MAX;
545 /* sort the colors according costs, cheapest first. */
546 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
548 /* Try recoloring the node using the color list. */
549 res = recolor(env, irn, csts, parent_changed, depth);
552 /* If we came here, everything went ok. */
556 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
558 co2_irn_t *ci = get_co2_irn(env, irn);
559 col_t col = get_col(env, irn);
562 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
564 /* the node has the wanted color. That's fine, mark it as visited and return. */
569 list_add(&ci->changed_list, parent_changed);
576 if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
577 int n_regs = env->co->cls->n_regs;
578 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
580 /* Get the costs for giving the node a specific color. */
581 single_color_cost(env, ci, tgt_col, seq);
583 /* Try recoloring the node using the color list. */
584 res = recolor(env, irn, seq, parent_changed, depth);
589 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
594 * Examine the costs of the current coloring concerning a MST subtree.
595 * @param ci The subtree root.
596 * @param col The color of @p ci.
597 * @return The best coloring for that subtree under the assumption that @p ci has color @p col.
599 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
601 int *front = FRONT_BASE(ci, col);
605 for(i = 0; i < ci->mst_n_childs; ++i) {
606 co2_cloud_irn_t *chld = ci->mst_childs[i];
607 col_t chld_col = front[i];
609 cost += examine_subtree_coloring(chld, chld_col);
610 cost += col != chld_col ? chld->mst_costs : 0;
617 * Determine color badnesses of a node.
618 * Badness means that it is unlikely that the node in question can
619 * obtain a color. The higher the badness, the more unlikely it is that
620 * the node can be assigned that color.
621 * @param ci The node.
622 * @param badness An integer array as long as there are registers.
623 * @note The array <code>badness</code> is not cleared.
625 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
627 co2_t *env = ci->cloud->env;
628 co2_irn_t *ir = &ci->inh;
629 int n_regs = env->n_regs;
630 be_ifg_t *ifg = env->co->cenv->ifg;
631 bitset_t *bs = bitset_alloca(n_regs);
637 admissible_colors(env, &ci->inh, bs);
639 bitset_foreach(bs, elm)
640 badness[elm] = ci->costs;
642 /* Use constrained/fixed interfering neighbors to influence the color badness */
643 it = be_ifg_neighbours_iter_alloca(ifg);
644 be_ifg_foreach_neighbour(ifg, it, ir->irn, irn) {
645 co2_irn_t *ni = get_co2_irn(env, irn);
647 admissible_colors(env, ni, bs);
648 if(bitset_popcnt(bs) == 1) {
649 bitset_pos_t c = bitset_next_set(bs, 0);
650 badness[c] += ci->costs;
654 col_t c = get_col(env, ni->irn);
655 badness[c] += ci->costs;
658 be_ifg_neighbours_break(ifg, it);
662 * Determine the badness of a MST subtree.
663 * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
664 * @see node_color_badness() for a definition of badness.
665 * @param ci The root of the subtree.
666 * @param depth Depth for debugging purposes.
668 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
670 co2_t *env = ci->cloud->env;
673 node_color_badness(ci, ci->color_badness);
675 /* Collect the color badness for the whole subtree */
676 for(i = 0; i < ci->mst_n_childs; ++i) {
677 co2_cloud_irn_t *child = ci->mst_childs[i];
678 determine_color_badness(child, depth + 1);
680 for(j = 0; j < env->n_regs; ++j)
681 ci->color_badness[j] += child->color_badness[j];
684 for(j = 0; j < env->n_regs; ++j)
685 DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
689 * Unfix all nodes in a MST subtree.
691 static void unfix_subtree(co2_cloud_irn_t *ci)
696 for(i = 0; i < ci->mst_n_childs; ++i)
697 unfix_subtree(ci->mst_childs[i]);
700 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
702 co2_t *env = ci->cloud->env;
703 col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
704 int is_root = ci->mst_parent == ci;
705 col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
706 int min_badness = INT_MAX;
707 int best_col_costs = INT_MAX;
709 int n_regs = env->n_regs;
710 int n_iter = is_root ? MIN(n_regs, subtree_iter) : 1;
712 struct list_head changed;
715 for(i = 0; i < n_regs; ++i) {
716 int badness = ci->color_badness[i];
719 seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
721 min_badness = MIN(min_badness, badness);
724 /* If we are not the root and the parent's color is allowed for this node give it top prio. */
725 if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
726 seq[parent_col].costs = min_badness - 1;
728 /* Sort the colors. The will be processed in that ordering. */
729 qsort(seq, env->n_regs, sizeof(seq[0]), col_cost_pair_lt);
731 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
732 INIT_LIST_HEAD(&changed);
733 for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
734 col_t col = seq[i].col;
735 int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
737 int subtree_costs, sum_costs;
739 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
742 INIT_LIST_HEAD(&changed);
743 ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
745 materialize_coloring(&changed);
752 for(j = 0; j < ci->mst_n_childs; ++j) {
753 co2_cloud_irn_t *child = ci->mst_childs[j];
754 ok = coalesce_top_down(child, j, depth + 1) >= 0;
756 child->inh.fixed = 1;
761 /* If the subtree could not be colored, we have to try another color. */
765 subtree_costs = examine_subtree_coloring(ci, col);
766 sum_costs = subtree_costs + add_cost;
767 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
769 if(sum_costs < best_col_costs) {
771 best_col_costs = sum_costs;
772 ci->col_costs[col] = subtree_costs;
780 int *front = FRONT_BASE(ci->mst_parent, parent_col);
781 front[child_nr] = best_col;
787 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
789 be_ifg_t *ifg = env->co->cenv->ifg;
790 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
797 /* mark the node as visited and add it to the cloud. */
799 list_add(&ci->cloud_list, &cloud->members_head);
801 DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
803 /* determine the nodes costs */
804 co_gs_foreach_neighb(a, n) {
806 DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
807 if(be_ifg_connected(ifg, a->irn, n->irn))
808 cloud->inevit += n->costs;
811 /* add the node's cost to the total costs of the cloud. */
813 cloud->costs += costs;
814 cloud->n_constr += is_constrained(env, &ci->inh);
815 cloud->freedom += bitset_popcnt(get_adm(env, &ci->inh));
816 cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
819 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
820 if(costs >= curr_costs) {
825 /* add all the neighbors of the node to the cloud. */
826 co_gs_foreach_neighb(a, n) {
827 affinity_node_t *an = get_affinity_info(env->co, n->irn);
829 populate_cloud(env, cloud, an, curr_costs);
833 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
835 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
839 DBG((env->dbg, LEVEL_2, "new cloud with %+F\n", a->irn));
840 memset(cloud, 0, sizeof(cloud[0]));
841 INIT_LIST_HEAD(&cloud->members_head);
842 INIT_LIST_HEAD(&cloud->list);
843 list_add(&cloud->list, &env->cloud_head);
844 cloud->best_costs = INT_MAX;
847 populate_cloud(env, cloud, a, 0);
848 cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
850 /* Also allocate space for the node sequence and compute that sequence. */
851 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
854 list_for_each_entry(co2_cloud_irn_t, ci, &cloud->members_head, cloud_list) {
856 cloud->seq[i++] = ci;
858 DBG((env->dbg, LEVEL_2, "cloud cost %d, freedom %f\n", cloud->costs, cloud->freedom));
863 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
865 ir_node *irn = ci->inh.irn;
866 int *front = FRONT_BASE(ci, col);
868 struct list_head changed;
870 INIT_LIST_HEAD(&changed);
872 DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
873 ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
874 // assert(ok && "Color changing may not fail while committing the coloring");
875 materialize_coloring(&changed);
877 for(i = 0; i < ci->mst_n_childs; ++i) {
878 apply_coloring(ci->mst_childs[i], front[i], depth + 1);
882 static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
884 while(ci != ci->mst_parent)
890 static void process_cloud(co2_cloud_t *cloud)
892 co2_t *env = cloud->env;
893 int n_regs = env->n_regs;
895 int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
902 memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
904 /* Collect all edges in the cloud on an obstack and sort the increasingly */
905 obstack_init(&cloud->obst);
906 for(i = 0; i < cloud->n_memb; ++i) {
907 co2_cloud_irn_t *ci = cloud->seq[i];
910 co_gs_foreach_neighb(ci->inh.aff, n) {
911 co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
912 if(ci->index < ni->index) {
917 obstack_grow(&cloud->obst, &e, sizeof(e));
922 edges = obstack_finish(&cloud->obst);
923 qsort(edges, n_edges, sizeof(edges[0]), cmp_edges);
925 /* Compute the maximum spanning tree using Kruskal/Union-Find */
926 DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
927 for(i = 0; i < n_edges; ++i) {
928 edge_t *e = &edges[i];
929 co2_cloud_irn_t *rs = find_mst_root(e->src);
930 co2_cloud_irn_t *rt = find_mst_root(e->tgt);
932 /* if the union/find roots are different */
934 int si = e->src->index;
935 int ti = e->tgt->index;
939 DBG((env->dbg, LEVEL_2, "\tadding edge %+F -- %+F cost %d\n", rs->inh.irn, rt->inh.irn, e->costs));
941 /* this edge is in the MST, so set it in the bitset. */
942 mst_edges[si * cloud->n_memb + ti] = e->costs;
943 mst_edges[ti * cloud->n_memb + si] = e->costs;
946 obstack_free(&cloud->obst, edges);
948 cloud->master->mst_parent = cloud->master;
949 cloud->mst_root = cloud->master;
950 q = new_pdeq1(cloud->master);
951 while(!pdeq_empty(q)) {
952 co2_cloud_irn_t *ci = pdeq_getl(q);
953 int ofs = ci->index * cloud->n_memb;
954 int end = ofs + cloud->n_memb;
957 ci->mst_n_childs = 0;
958 for(i = ofs; i < end; ++i) {
959 if(mst_edges[i] != 0) {
961 co2_cloud_irn_t *child = cloud->seq[i - ofs];
963 /* put the child to the worklist */
966 /* make ci the parent of the child and add the child to the children array of the parent */
967 child->mst_parent = ci;
968 child->mst_costs = mst_edges[i];
970 obstack_ptr_grow(&cloud->obst, child);
972 mst_edges[other * cloud->n_memb + ci->index] = 0;
977 obstack_ptr_grow(&cloud->obst, NULL);
978 ci->mst_childs = obstack_finish(&cloud->obst);
984 DBG((env->dbg, LEVEL_3, "mst:\n"));
985 for(i = 0; i < cloud->n_memb; ++i) {
986 DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
987 DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
990 for(i = 0; i < cloud->n_memb; ++i) {
991 co2_cloud_irn_t *ci = cloud->seq[i];
992 int n_childs = ci->mst_n_childs;
995 ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
996 ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
997 ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
998 ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
999 memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
1000 memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
1001 memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
1002 memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
1004 for(j = 0; j < env->n_regs; j++)
1005 ci->col_costs[j] = INT_MAX;
1009 determine_color_badness(cloud->mst_root, 0);
1010 best_col = coalesce_top_down(cloud->mst_root, -1, 0);
1011 unfix_subtree(cloud->mst_root);
1012 apply_coloring(cloud->mst_root, best_col, 0);
1014 /* The coloring should represent the one with the best costs. */
1015 //materialize_coloring(&changed);
1016 DBG((env->dbg, LEVEL_2, "\tbest coloring for root %+F was %d costing %d\n",
1017 cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
1019 /* Fix all nodes in the cloud. */
1020 for(i = 0; i < cloud->n_memb; ++i)
1021 cloud->seq[i]->inh.fixed = 1;
1023 /* Free all space used while optimizing this cloud. */
1024 obstack_free(&cloud->obst, NULL);
1027 static int cloud_costs(co2_cloud_t *cloud)
1032 for(i = 0; i < cloud->n_memb; ++i) {
1033 co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
1034 col_t col = get_col(cloud->env, ci->irn);
1035 co_gs_foreach_neighb(ci->aff, n) {
1036 col_t n_col = get_col(cloud->env, n->irn);
1037 costs += col != n_col ? n->costs : 0;
1044 static void process(co2_t *env)
1048 co2_cloud_t **clouds;
1053 int final_costs = 0;
1056 co_gs_foreach_aff_node(env->co, a) {
1057 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
1066 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1067 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1069 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
1071 for(i = 0; i < n_clouds; ++i) {
1072 init_costs += cloud_costs(clouds[i]);
1074 /* Process the cloud. */
1075 process_cloud(clouds[i]);
1077 all_costs += clouds[i]->costs;
1078 final_costs += cloud_costs(clouds[i]);
1080 /* Dump the IFG if the user demanded it. */
1081 if (dump_flags & DUMP_CLOUD) {
1085 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
1086 f = fopen(buf, "wt");
1088 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1094 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1099 static void writeback_colors(co2_t *env)
1101 const arch_env_t *aenv = env->co->aenv;
1104 for(irn = env->touched; irn; irn = irn->touched_next) {
1105 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1106 arch_set_irn_register(aenv, irn->irn, reg);
1112 ___ _____ ____ ____ ___ _____ ____ _
1113 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1114 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1115 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1116 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1120 static const char *get_dot_color_name(int col)
1122 static const char *names[] = {
1156 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1159 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1161 const arch_register_req_t *req;
1163 req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
1164 if(arch_register_req_is(req, limited))
1176 static void ifg_dump_graph_attr(FILE *f, void *self)
1178 fprintf(f, "overlay=false");
1181 static int ifg_is_dump_node(void *self, ir_node *irn)
1184 return !arch_irn_is(env->co->aenv, irn, ignore);
1187 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1190 co2_irn_t *ci = get_co2_irn(env, irn);
1196 co2_cloud_irn_t *cci = (void *) ci;
1197 if (cci->cloud && cci->cloud->mst_root == cci)
1200 if(cci->cloud && cci->cloud->mst_root)
1201 ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
1204 ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
1205 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1208 static void ifg_dump_at_end(FILE *file, void *self)
1213 co_gs_foreach_aff_node(env->co, a) {
1214 co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
1215 int idx = get_irn_idx(a->irn);
1218 if(ai->mst_parent != ai)
1219 fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
1221 co_gs_foreach_neighb(a, n) {
1222 int nidx = get_irn_idx(n->irn);
1223 co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
1226 const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
1227 const char *arr = "arrowhead=dot arrowtail=dot";
1229 if(ci->mst_parent == ai)
1230 arr = "arrowtail=normal";
1231 else if(ai->mst_parent == ci)
1232 arr = "arrowhead=normal";
1234 fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
1241 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1243 ifg_dump_graph_attr,
1251 int co_solve_heuristic_new(copy_opt_t *co)
1257 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
1261 env.n_regs = co->cls->n_regs;
1262 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1263 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1264 bitset_flip_all(env.ignore_regs);
1265 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1266 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1267 INIT_LIST_HEAD(&env.cloud_head);
1269 if(dump_flags & DUMP_BEFORE) {
1270 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
1271 f = fopen(buf, "wt");
1273 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1280 if(dump_flags & DUMP_AFTER) {
1281 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
1282 f = fopen(buf, "wt");
1284 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1289 writeback_colors(&env);
1290 phase_free(&env.ph);