3 * More experiments on coalescing.
4 * @author Sebastian Hack
16 #include "bitfiddle.h"
18 #include "irphase_t.h"
19 #include "irgraph_t.h"
25 #include "becopyopt.h"
26 #include "becopyopt_t.h"
27 #include "bechordal_t.h"
29 #define INFEASIBLE(cost) ((cost) == INT_MAX)
31 static be_ifg_dump_dot_cb_t ifg_dot_cb;
33 typedef unsigned col_t;
35 typedef struct _co2_irn_t co2_irn_t;
36 typedef struct _co2_cloud_t co2_cloud_t;
41 bitset_t *ignore_regs;
44 struct list_head cloud_head;
45 DEBUG_ONLY(firm_dbg_module_t *dbg;)
51 co2_irn_t *touched_next;
59 unsigned tmp_fixed : 1;
60 struct list_head changed_list;
61 struct list_head cloud_list;
73 struct list_head members_head;
74 struct list_head list;
77 #define NEIGHBOR_FIXED 1
78 #define NEIGHBOR_CONSTR 2
88 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
90 static void co2_irn_init(phase_t *ph, const ir_node *irn, void *data)
92 co2_t *env = (co2_t *) ph;
95 memset(ci, 0, sizeof(ci[0]));
96 INIT_LIST_HEAD(&ci->changed_list);
97 INIT_LIST_HEAD(&ci->cloud_list);
99 ci->touched_next = env->touched;
100 ci->orig_col = get_irn_col(env->co, irn);
101 ci->aff = get_affinity_info(env->co, irn);
106 static int co2_irn_cmp(const void *a, const void *b)
108 const co2_irn_t **p = a;
109 const co2_irn_t **q = b;
110 return (*q)->costs - (*p)->costs;
113 static int cmp_clouds(const void *a, const void *b)
115 const co2_cloud_t **p = a;
116 const co2_cloud_t **q = b;
117 return (*q)->costs - (*p)->costs;
120 static co2_cloud_t *new_cloud(co2_t *env)
122 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
123 memset(cloud, 0, sizeof(cloud[0]));
124 INIT_LIST_HEAD(&cloud->members_head);
125 INIT_LIST_HEAD(&cloud->list);
126 cloud->best_costs = INT_MAX;
131 * An order on color/costs pairs.
132 * If the costs are equal, we use the color as a kind of normalization.
134 static int col_cost_pair_lt(const void *a, const void *b)
136 const col_cost_pair_t *p = a;
137 const col_cost_pair_t *q = b;
141 return (c > d) - (c < d);
144 const char *flag_str(unsigned int fl)
148 buf[0] = fl & NEIGHBOR_CONSTR ? 'c' : '-';
149 buf[1] = fl & NEIGHBOR_FIXED ? 'n' : '-';
150 buf[2] = fl & SELF_CONSTR ? 'C' : '-';
151 buf[3] = fl & DONT_WANT ? 'd' : '-';
156 static col_t get_col(co2_t *env, ir_node *irn)
158 co2_irn_t *ci = get_co2_irn(env, irn);
159 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
162 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
164 co2_irn_t *ci = get_co2_irn(env, irn);
165 return ci->fixed || ci->tmp_fixed;
168 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
170 arch_register_req_t req;
172 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
173 if(arch_register_req_is(&req, limited))
174 req.limited(req.limited_env, bs);
176 bitset_copy(bs, env->ignore_regs);
183 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
185 bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
186 admissible_colors(env, ci, bs);
187 return bitset_is_set(bs, col);
190 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
192 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
193 arch_register_req_t req;
195 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
197 if(arch_register_req_is(&req, limited)) {
201 req.limited(req.limited_env, aux);
202 n_constr = bitset_popcnt(aux);
203 bitset_foreach(aux, elm) {
204 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
205 col_costs[elm].flags |= NEIGHBOR_CONSTR;
211 * Determine costs which shall indicate how cheap/expensive it is to try
212 * to assign a node some color.
213 * The costs are computed for all colors. INT_MAX means that it is impossible
214 * to give the node that specific color.
216 * @param env The co2 this pointer.
217 * @param irn The node.
218 * @param col_costs An array of colors x costs where the costs are written to.
220 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
222 ir_node *irn = ci->irn;
223 be_ifg_t *ifg = env->co->cenv->ifg;
224 int n_regs = env->co->cls->n_regs;
225 bitset_t *forb = bitset_alloca(n_regs);
226 affinity_node_t *a = get_affinity_info(env->co, irn);
233 if(get_irn_node_nr(irn) == 2040) {
237 /* Put all forbidden colors into the aux bitset. */
238 admissible_colors(env, ci, forb);
239 bitset_flip_all(forb);
241 for(i = 0; i < n_regs; ++i) {
242 col_costs[i].col = i;
243 col_costs[i].costs = 0;
244 col_costs[i].flags = 0;
250 co_gs_foreach_neighb(a, n) {
251 if(color_is_fix(env, n->irn)) {
252 col_t col = get_col(env, n->irn);
253 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
256 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
260 it = be_ifg_neighbours_iter_alloca(ifg);
261 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
262 col_t col = get_col(env, pos);
263 if(color_is_fix(env, pos)) {
264 col_costs[col].costs = INT_MAX;
265 col_costs[col].flags |= NEIGHBOR_FIXED;
268 incur_constraint_costs(env, pos, col_costs, INT_MAX);
269 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
273 /* Set the costs to infinity for each color which is not allowed at this node. */
274 bitset_foreach(forb, elm) {
275 col_costs[elm].costs = INT_MAX;
276 col_costs[elm].flags |= SELF_CONSTR;
281 static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
283 int n_regs = env->co->cls->n_regs;
286 for(i = 0; i < n_regs; ++i) {
288 seq[i].costs = INT_MAX;
290 seq[i].flags = DONT_WANT;
299 static int curr_costs(co2_t *env, affinity_node_t *a)
301 col_t a_col = get_col(env, a->irn);
305 co_gs_foreach_neighb(a, n) {
306 col_t n_col = get_col(env, n->irn);
307 costs += n_col != a_col ? n->costs : 0;
313 static int cloud_costs(co2_t *env, co2_cloud_t *cloud)
318 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
319 affinity_node_t *a = get_affinity_info(env->co, ci->irn);
320 costs += curr_costs(env, a);
326 static void reject_coloring(struct list_head *h)
330 list_for_each_entry(co2_irn_t, pos, h, changed_list)
334 static void materialize_coloring(struct list_head *h)
338 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
339 pos->orig_col = pos->tmp_col;
349 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
354 list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
356 ent.col = pos->tmp_col;
358 obstack_grow(obst, &ent, sizeof(ent));
360 memset(&ent, 0, sizeof(ent));
361 obstack_grow(obst, &ent, sizeof(ent));
362 return obstack_finish(obst);
365 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
366 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
368 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
370 int n_regs = env->co->cls->n_regs;
371 be_ifg_t *ifg = env->co->cenv->ifg;
372 co2_irn_t *ci = get_co2_irn(env, irn);
378 for(i = 0; i < n_regs; ++i) {
379 col_t tgt_col = col_list[i].col;
380 unsigned costs = col_list[i].costs;
383 struct list_head changed;
387 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
389 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
390 if(INFEASIBLE(costs)) {
391 DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible due to %s\n", depth, tgt_col, flag_str(col_list[i].flags)));
396 /* Set the new color of the node and mark the node as temporarily fixed. */
397 ci->tmp_col = tgt_col;
401 If that color has costs > 0, there's at least one neighbor having that color,
402 so we will try to change the neighbors' colors, too.
404 INIT_LIST_HEAD(&changed);
405 list_add(&ci->changed_list, &changed);
407 it = be_ifg_neighbours_iter_alloca(ifg);
408 be_ifg_foreach_neighbour(ifg, it, irn, n) {
410 /* try to re-color the neighbor if it has the target color. */
411 if(get_col(env, n) == tgt_col) {
412 struct list_head tmp;
415 Try to change the color of the neighbor and record all nodes which
416 get changed in the tmp list. Add this list to the "changed" list for
417 that color. If we did not succeed to change the color of the neighbor,
418 we bail out and try the next color.
420 INIT_LIST_HEAD(&tmp);
421 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
422 list_splice(&tmp, &changed);
429 We managed to assign the target color to all neighbors, so from the perspective
430 of the current node, every thing was ok and we can return safely.
433 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
434 list_splice(&changed, parent_changed);
440 If not, that color did not succeed and we unfix all nodes we touched
441 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
444 reject_coloring(&changed);
450 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
452 co2_irn_t *ci = get_co2_irn(env, irn);
454 col_t col = get_col(env, irn);
456 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
458 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
465 list_add(&ci->changed_list, parent_changed);
469 /* The node has the color it should not have _and_ has not been visited yet. */
470 if(!color_is_fix(env, irn)) {
471 int n_regs = env->co->cls->n_regs;
472 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
474 /* Get the costs for giving the node a specific color. */
475 determine_color_costs(env, ci, csts);
477 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
478 csts[not_col].costs = INT_MAX;
480 /* sort the colors according costs, cheapest first. */
481 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
483 /* Try recoloring the node using the color list. */
484 res = recolor(env, irn, csts, parent_changed, depth);
487 /* If we came here, everything went ok. */
491 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
493 co2_irn_t *ci = get_co2_irn(env, irn);
494 col_t col = get_col(env, irn);
497 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
499 /* If the color is already fix, bail out. */
500 if(color_is_fix(env, irn))
503 /* the node has the wanted color. That's fine, mark it as visited and return. */
510 list_add(&ci->changed_list, parent_changed);
511 DB((env->dbg, LEVEL_3, "\t\tok\n"));
516 int n_regs = env->co->cls->n_regs;
517 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
519 /* Get the costs for giving the node a specific color. */
520 single_color_cost(env, tgt_col, seq);
522 /* Try recoloring the node using the color list. */
523 res = recolor(env, irn, seq, parent_changed, depth);
525 DB((env->dbg, LEVEL_3, "\t\tcolor %d %s for %+F\n", tgt_col, res ? "was ok" : "failed", irn));
533 static void try_color(co2_t *env, co2_irn_t *ci, col_t col, struct list_head *parent_changed)
535 be_ifg_t *ifg = env->co->cenv->ifg;
536 int n_regs = env->co->cls->n_regs;
537 col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0]));
538 affinity_node_t *a = get_affinity_info(env->co, ci->irn);
539 co2_irn_t **nbs = alloca(a->degree * sizeof(nbs[0]));
545 assert(a != NULL && "This node must be an affinity node");
547 /* If that node has already been fixed, leave it alone. */
548 if(color_is_fix(env, ci->irn) || !is_color_admissible(env, ci, col)) {
549 // DB((env->dbg, LEVEL_2, "\t-> color is already fix: %d\n", get_col(env, ci->irn)));
553 DB((env->dbg, LEVEL_1, "\taffinity node %+F cost %d trying color %d\n", ci->irn, ci->costs, col));
555 single_color_cost(env, col, col_seq);
556 recolor(env, ci->irn, col_seq, parent_changed, 0);
557 new_col = get_col(env, ci->irn);
560 ci->tmp_col = new_col;
562 DB((env->dbg, LEVEL_2, "\t-> has color %d now. %d wanted\n", new_col, col));
565 co_gs_foreach_neighb(a, n)
566 nbs[i++] = get_co2_irn(env, n->irn);
568 co_gs_foreach_neighb(a, n) {
569 co2_irn_t *ni = get_co2_irn(env, n->irn);
570 col_t tgt_col = be_ifg_connected(ifg, ci->irn, ni->irn) ? get_col(env, ni->irn) : new_col;
571 try_color(env, ni, tgt_col, parent_changed);
575 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
577 int n_regs = env->co->cls->n_regs;
578 col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0]));
579 int best_costs = cloud_costs(env, cloud);
582 struct list_head changed;
588 DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn));
589 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
590 DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs));
593 determine_color_costs(env, cloud->master, cols);
594 qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt);
596 best_col = cols[0].col;
597 for(i = 0; i < n_regs; ++i) {
598 col_t col = cols[i].col;
602 INIT_LIST_HEAD(&changed);
603 DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs));
605 /* try to recolor all the cloud members. */
606 try_color(env, cloud->master, col, &changed);
608 /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */
609 costs = cloud_costs(env, cloud);
611 /* materialize the new coloring. */
612 if(costs < best_costs) {
613 materialize_coloring(&changed);
619 /* We won't get the cloud any better so stop it. */
624 reject_coloring(&changed);
627 DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs));
629 /* fix all cloud members */
630 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
638 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%F.dot", env->co->irg, env->co->cls->name, cloud->master);
639 if(f = fopen(buf, "wt")) {
640 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
646 static void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed)
648 ir_node *irn = ci->irn;
650 if(!color_is_fix(env, irn)) {
651 int n_regs = env->co->cls->n_regs;
652 bitset_t *tried = bitset_alloca(n_regs);
653 bitset_t *adm = bitset_alloca(n_regs);
654 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
656 affinity_node_t *a = get_affinity_info(env->co, irn);
657 int best_costs = cloud_costs(env, ci->cloud);
658 int best_col = get_col(env, ci->irn);
662 determine_color_costs(env, ci, seq);
663 if(!INFEASIBLE(seq[preferred].costs))
664 seq[preferred].costs = INT_MIN;
666 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
668 for(i = 0; i < n_regs; ++i) {
669 col_t col = seq[i].col;
671 struct list_head changed;
674 INIT_LIST_HEAD(&changed);
675 ok = change_color_single(env, irn, col, &changed, 0);
676 col = get_col(env, irn);
678 if(!bitset_is_set(tried, col)) {
684 list_add(&ci->changed_list, &changed);
687 co_gs_foreach_neighb(a, n) {
688 co2_irn_t *ni = get_co2_irn(env, n->irn);
689 try_affinity_node(env, ni, col, &changed);
692 examine_coloring(env, ci->cloud);
693 reject_coloring(&changed);
695 bitset_set(tried, col);
702 static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
704 int costs = cloud_costs(env, cloud);
706 if(costs < cloud->best_costs) {
709 for(i = 0; i < cloud->n_memb; ++i)
710 cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
712 cloud->best_costs = costs;
716 static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors)
718 col_t col = get_col(env, ci->irn);
722 co_gs_foreach_neighb(ci->aff, n) {
723 col_t nc = get_col(env, n->irn);
724 int fixed = color_is_fix(env, n->irn);
728 else if(!fixed || !bitset_is_set(tried_colors, nc))
732 DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance));
736 static void adjust_start_colors(co2_t *env, co2_cloud_t *cloud, col_cost_pair_t *seq)
738 int n_regs = env->co->cls->n_regs;
739 bitset_t *adm = bitset_alloca(n_regs);
743 for(i = 0; i < cloud->n_memb; ++i) {
744 co2_irn_t *ci = cloud->seq[i];
747 /* Prefer precolored neighbors. */
748 bitset_clear_all(adm);
749 admissible_colors(env, ci, adm);
750 n_constr = bitset_popcnt(adm);
752 bitset_foreach(adm, col) {
753 seq[col].costs = add_saturated(seq[col].costs, -128 * (n_regs - n_constr));
756 bitset_foreach_clear(adm, col) {
757 seq[col].costs = add_saturated(seq[col].costs, 128);
761 admissible_colors(env, cloud->master, adm);
762 bitset_flip_all(adm);
764 bitset_foreach(adm, col)
765 seq[col].costs = INT_MAX;
768 static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
770 struct list_head changed;
773 if(index < cloud->n_memb) {
774 co2_irn_t *ci = cloud->seq[index];
775 int n_regs = env->co->cls->n_regs;
776 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
777 bitset_t *cols_tried = bitset_alloca(n_regs);
779 //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0]));
783 determine_color_costs(env, ci, seq);
785 adjust_start_colors(env, cloud, seq);
789 col_t col = get_col(env, ci->irn);
790 int min_costs = INT_MAX;
793 for(i = 0; i < n_regs; ++i)
794 min_costs = MIN(min_costs, seq[i].costs);
796 seq[col].costs = min_costs - 1;
800 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
803 if(index == cloud->n_memb - 1) {
804 for(i = 0; i < n_regs; ++i)
805 if(seq[i].costs >= 0)
806 seq[i].costs = INT_MAX;
811 for(i = 0; i < n_regs && !done; ++i) {
812 col_t col = seq[i].col;
813 int costs = seq[i].costs;
817 if all affinity neighbors fixed,
818 try only color changes to affinity colors.
819 all other colors do no good.
822 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}trying %+F index %d for color %d\n", index, ci->irn, index, col));
823 if(INFEASIBLE(costs)) {
824 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
828 bitset_set(cols_tried, col);
829 INIT_LIST_HEAD(&changed);
830 ok = change_color_single(env, ci->irn, col, &changed, 0);
831 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", index, ok ? "ok" : "failed"));
833 /* if we succeeded changing the color, we will figure out the next node. */
837 /* materialize the coloring and fix the node's color. */
840 /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
841 finish = process_node(env, cloud, index + 1);
843 /* if this is the last node in the coloring sequence, examine the coloring */
844 if(index == cloud->n_memb - 1) {
845 examine_cloud_coloring(env, cloud);
846 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> current best coloring %d\n", index, cloud->best_costs));
847 if(cloud->best_costs == cloud->inevit) {
853 /* unfix the node. */
854 reject_coloring(&changed);
857 if(finish || color_change_balance(env, ci, cols_tried) <= 0) {
869 static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
875 co_gs_foreach_neighb(ci->aff, n) {
876 nbs[i++] = get_co2_irn(env, n->irn);
879 qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
883 static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
885 pdeq *q = new_pdeq1(cloud->master);
886 bitset_t *seen = bitset_malloc(get_irg_last_idx(env->co->irg));
887 co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
891 bitset_set(seen, get_irn_idx(cloud->master->irn));
892 while(!pdeq_empty(q)) {
893 co2_irn_t *curr = pdeq_getl(q);
895 cloud->seq[j++] = curr;
896 get_neighb_arr(env, curr, nbs);
898 for(i = 0; i < curr->aff->degree; ++i) {
899 co2_irn_t *ni = nbs[i];
900 int idx = get_irn_idx(ni->irn);
901 if(!bitset_is_set(seen, idx)) {
903 bitset_set(seen, idx);
912 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
914 be_ifg_t *ifg = env->co->cenv->ifg;
915 co2_irn_t *ci = get_co2_irn(env, a->irn);
919 if(ci->visited >= env->visited)
922 /* mark the node as visited and add it to the cloud. */
923 ci->visited = env->visited;
925 list_add(&ci->cloud_list, &cloud->members_head);
927 DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
929 /* determine the nodes costs */
930 co_gs_foreach_neighb(a, n) {
932 DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
933 if(be_ifg_connected(ifg, a->irn, n->irn))
934 cloud->inevit += n->costs;
937 /* add the node's cost to the total costs of the cloud. */
939 cloud->costs += costs;
940 cloud->max_degree = MAX(cloud->max_degree, ci->aff->degree);
943 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
944 if(costs >= curr_costs) {
949 /* add all the neighbors of the node to the cloud. */
950 co_gs_foreach_neighb(a, n) {
951 affinity_node_t *an = get_affinity_info(env->co, n->irn);
953 populate_cloud(env, cloud, an, curr_costs);
957 static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a)
960 populate_cloud(env, cloud, a, 0);
962 cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
963 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
965 cloud->seq[0] = cloud->master;
966 determine_coloring_sequence(env, cloud);
969 static void process_cloud(co2_t *env, co2_cloud_t *cloud, int nr)
971 struct list_head changed;
974 /* initialize the best coloring. */
975 examine_cloud_coloring(env, cloud);
977 DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
978 for(i = 0; i < cloud->n_memb; ++i) {
979 co2_irn_t *ci = cloud->seq[i];
980 DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
983 process_node(env, cloud, 0);
984 DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
986 /* re-try the best coloring. */
987 INIT_LIST_HEAD(&changed);
988 for(i = 0; i < cloud->n_memb; ++i) {
989 co2_irn_t *ci = cloud->seq[i];
990 col_t col = cloud->best_cols[i];
994 DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
995 ok = change_color_single(env, ci->irn, col, &changed, 0);
999 materialize_coloring(&changed);
1004 for(ci = env->touched; ci; ci = ci->touched_next) {
1007 ir_printf("%+F is still temp fixed\n", ci->irn);
1010 assert(!some_fixed);
1017 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, nr);
1018 if(f = fopen(buf, "wt")) {
1019 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
1026 static void process(co2_t *env)
1030 co2_cloud_t **clouds;
1035 int final_costs = 0;
1039 co_gs_foreach_aff_node(env->co, a) {
1040 co2_irn_t *ci = get_co2_irn(env, a->irn);
1043 co2_cloud_t *cloud = new_cloud(env);
1045 init_cloud(env, cloud, a);
1046 list_add(&cloud->list, &env->cloud_head);
1052 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1053 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
1055 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
1057 for(i = 0; i < n_clouds; ++i) {
1058 init_costs += cloud_costs(env, clouds[i]);
1059 process_cloud(env, clouds[i], i);
1060 all_costs += clouds[i]->costs;
1061 final_costs += clouds[i]->best_costs;
1064 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1069 static void writeback_colors(co2_t *env)
1071 const arch_env_t *aenv = env->co->aenv;
1074 for(irn = env->touched; irn; irn = irn->touched_next) {
1075 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1076 arch_set_irn_register(aenv, irn->irn, reg);
1081 ___ _____ ____ ____ ___ _____ ____ _
1082 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
1083 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1084 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
1085 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1089 static const char *get_dot_color_name(int col)
1091 static const char *names[] = {
1125 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
1128 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
1130 arch_register_req_t req;
1132 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
1133 if(arch_register_req_is(&req, limited))
1145 static void ifg_dump_graph_attr(FILE *f, void *self)
1147 fprintf(f, "overlay=false");
1150 static int ifg_is_dump_node(void *self, ir_node *irn)
1153 return !arch_irn_is(env->co->aenv, irn, ignore);
1156 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1159 co2_irn_t *ci = get_co2_irn(env, irn);
1161 ir_fprintf(f, "label=\"%+F,%d\" style=filled color=%s shape=%s", irn, ci->costs,
1162 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1165 static void ifg_dump_at_end(FILE *file, void *self)
1170 co_gs_foreach_aff_node(env->co, a) {
1171 int idx = get_irn_idx(a->irn);
1174 co_gs_foreach_neighb(a, n) {
1175 int nidx = get_irn_idx(n->irn);
1178 const char *style = get_col(env, a->irn) == get_col(env, n->irn) ? "dashed" : "dotted";
1179 fprintf(file, "\tn%d -- n%d [label=\"%d\" style=%s weight=0.01];\n", idx, nidx, n->costs, style);
1186 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1188 ifg_dump_graph_attr,
1195 void co_solve_heuristic_new(copy_opt_t *co)
1200 phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
1204 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1205 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1206 bitset_flip_all(env.ignore_regs);
1207 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1208 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1209 INIT_LIST_HEAD(&env.cloud_head);
1211 if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1212 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1218 if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1219 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1223 writeback_colors(&env);
1224 phase_free(&env.ph);