3 * More experiments on coalescing.
4 * @author Sebastian Hack
16 #include "irphase_t.h"
17 #include "irgraph_t.h"
23 #include "becopyopt.h"
24 #include "becopyopt_t.h"
25 #include "bechordal_t.h"
27 #define INFEASIBLE(col) ((col) > (INT_MAX - 10))
29 typedef unsigned col_t;
31 typedef struct _co2_irn_t co2_irn_t;
32 typedef struct _co2_cloud_t co2_cloud_t;
37 bitset_t *ignore_regs;
40 DEBUG_ONLY(firm_dbg_module_t *dbg;)
46 co2_irn_t *touched_next;
54 unsigned tmp_fixed : 1;
55 struct list_head changed_list;
56 struct list_head cloud_list;
68 struct list_head members_head;
69 struct list_head list;
72 #define NEIGHBOR_FIXED 1
73 #define NEIGHBOR_CONSTR 2
83 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
85 static void co2_irn_init(phase_t *ph, ir_node *irn, void *data)
87 co2_t *env = (co2_t *) ph;
90 memset(ci, 0, sizeof(ci[0]));
91 INIT_LIST_HEAD(&ci->changed_list);
92 INIT_LIST_HEAD(&ci->cloud_list);
94 ci->touched_next = env->touched;
95 ci->orig_col = get_irn_col(env->co, irn);
96 ci->aff = get_affinity_info(env->co, irn);
101 static int co2_irn_cmp(const void *a, const void *b)
103 const co2_irn_t **p = a;
104 const co2_irn_t **q = b;
105 return (*q)->costs - (*p)->costs;
108 static int cmp_clouds(const void *a, const void *b)
110 const co2_cloud_t **p = a;
111 const co2_cloud_t **q = b;
112 return (*q)->costs - (*p)->costs;
115 static co2_cloud_t *new_cloud(co2_t *env)
117 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
118 memset(cloud, 0, sizeof(cloud[0]));
119 INIT_LIST_HEAD(&cloud->members_head);
120 INIT_LIST_HEAD(&cloud->list);
121 cloud->best_costs = INT_MAX;
126 * An order on color/costs pairs.
127 * If the costs are equal, we use the color as a kind of normalization.
129 static int col_cost_pair_lt(const void *a, const void *b)
131 const col_cost_pair_t *p = a;
132 const col_cost_pair_t *q = b;
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 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 += 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 -= 100 * n->costs;
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 += 10 * 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%2Ntrying 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%2Ncolor %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%2Ncolor %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%2Nclearing %+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%2Ntrying 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);
576 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
578 int n_regs = env->co->cls->n_regs;
579 col_cost_pair_t *cols = alloca(n_regs * sizeof(cols[0]));
580 int best_costs = cloud_costs(env, cloud);
583 struct list_head changed;
589 DB((env->dbg, LEVEL_2, "processing cloud with costs %d and master %+F containing:\n", cloud->costs, cloud->master->irn));
590 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
591 DB((env->dbg, LEVEL_2, "\t%+F %d\n", ci->irn, ci->costs));
594 determine_color_costs(env, cloud->master, cols);
595 qsort(cols, n_regs, sizeof(cols[0]), col_cost_pair_lt);
597 best_col = cols[0].col;
598 for(i = 0; i < n_regs; ++i) {
599 col_t col = cols[i].col;
603 INIT_LIST_HEAD(&changed);
604 DBG((env->dbg, LEVEL_2, "\n\ttrying color %d. current costs: %d\n", col, best_costs));
606 /* try to recolor all the cloud members. */
607 try_color(env, cloud->master, col, &changed);
609 /* recoloring of all nodes did succeed. measure the costs and decide if the coloring shall be kept. */
610 costs = cloud_costs(env, cloud);
612 /* materialize the new coloring. */
613 if(costs < best_costs) {
614 materialize_coloring(&changed);
620 /* We won't get the cloud any better so stop it. */
625 reject_coloring(&changed);
628 DB((env->dbg, LEVEL_2, "\tfinished cloud with costs %d\n", best_costs));
630 /* fix all cloud members */
631 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
637 static void try_affinity_node(co2_t *env, co2_irn_t *ci, col_t preferred, struct list_head *parent_changed)
639 ir_node *irn = ci->irn;
641 if(!color_is_fix(env, irn)) {
642 int n_regs = env->co->cls->n_regs;
643 bitset_t *tried = bitset_alloca(n_regs);
644 bitset_t *adm = bitset_alloca(n_regs);
645 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
647 affinity_node_t *a = get_affinity_info(env->co, irn);
648 int best_costs = cloud_costs(env, ci->cloud);
649 int best_col = get_col(env, ci->irn);
653 determine_color_costs(env, ci, seq);
654 if(!INFEASIBLE(seq[preferred].costs))
655 seq[preferred].costs = INT_MIN;
657 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
659 for(i = 0; i < n_regs; ++i) {
660 col_t col = seq[i].col;
662 struct list_head changed;
665 INIT_LIST_HEAD(&changed);
666 ok = change_color_single(env, irn, col, &changed, 0);
667 col = get_col(env, irn);
669 if(!bitset_is_set(tried, col)) {
675 list_add(&ci->changed_list, &changed);
678 co_gs_foreach_neighb(a, n) {
679 co2_irn_t *ni = get_co2_irn(env, n->irn);
680 try_affinity_node(env, ni, col, &changed);
683 examine_coloring(env, ci->cloud);
684 reject_coloring(&changed);
686 bitset_set(tried, col);
693 static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
695 int costs = cloud_costs(env, cloud);
697 if(costs < cloud->best_costs) {
700 for(i = 0; i < cloud->n_memb; ++i)
701 cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
703 cloud->best_costs = costs;
707 static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors)
709 col_t col = get_col(env, ci->irn);
713 co_gs_foreach_neighb(ci->aff, n) {
714 col_t nc = get_col(env, n->irn);
715 int fixed = color_is_fix(env, n->irn);
719 else if(!fixed || !bitset_is_set(tried_colors, nc))
723 DBG((env->dbg, LEVEL_4, "\t\tbalance for changing %+F color %d\n", ci->irn, balance));
727 static void keep_sensible_colors(co2_t *env, co2_irn_t *ci, col_cost_pair_t *seq)
729 bitset_t *fixed_cols = bitset_alloca(env->co->cls->n_regs);
733 co_gs_foreach_neighb(ci->aff, n) {
734 all_fixed &= color_is_fix(env, n->irn);
735 bitset_set(fixed_cols, get_col(env, n->irn));
740 bitset_flip_all(fixed_cols);
741 bitset_foreach(fixed_cols, i)
742 seq[i].costs = INT_MAX;
746 static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
748 struct list_head changed;
751 if(index < cloud->n_memb) {
752 co2_irn_t *ci = cloud->seq[index];
753 int n_regs = env->co->cls->n_regs;
754 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
755 bitset_t *cols_tried = bitset_alloca(n_regs);
757 //col_cost_pair_t *single = alloca(n_regs * sizeof(seq[0]));
761 determine_color_costs(env, ci, seq);
764 col_t col = get_col(env, ci->irn);
765 int min_costs = INT_MAX;
768 for(i = 0; i < n_regs; ++i)
769 min_costs = MIN(min_costs, seq[i].costs);
771 seq[col].costs = min_costs - 1;
774 //keep_sensible_colors(env, ci, seq);
775 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
778 if(index == cloud->n_memb - 1) {
779 for(i = 0; i < n_regs; ++i)
780 if(seq[i].costs >= 0)
781 seq[i].costs = INT_MAX;
786 for(i = 0; i < n_regs && !done; ++i) {
787 col_t col = seq[i].col;
788 int costs = seq[i].costs;
792 if all affinity neighbors fixed,
793 try only color changes to affinity colors.
794 all other colors do no good.
797 DB((env->dbg, LEVEL_2, "\t%2Ntrying %+F index %d for color %d\n", index, ci->irn, index, col));
798 if(INFEASIBLE(costs)) {
799 DBG((env->dbg, LEVEL_2, "\t%2N-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
803 bitset_set(cols_tried, col);
804 INIT_LIST_HEAD(&changed);
805 ok = change_color_single(env, ci->irn, col, &changed, 0);
806 DB((env->dbg, LEVEL_2, "\t%2N-> %s\n", index, ok ? "ok" : "failed"));
808 /* if we succeeded changing the color, we will figure out the next node. */
812 /* materialize the coloring and fix the node's color. */
815 /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
816 finish = process_node(env, cloud, index + 1);
818 /* if this is the last node in the coloring sequence, examine the coloring */
819 if(index == cloud->n_memb - 1) {
820 examine_cloud_coloring(env, cloud);
821 DB((env->dbg, LEVEL_2, "\t%2N-> current best coloring %d\n", index, cloud->best_costs));
822 if(cloud->best_costs == cloud->inevit) {
828 /* unfix the node. */
829 reject_coloring(&changed);
832 if(finish || color_change_balance(env, ci, cols_tried) <= 0) {
844 static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
850 co_gs_foreach_neighb(ci->aff, n) {
851 nbs[i++] = get_co2_irn(env, n->irn);
854 qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
858 static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
860 pdeq *q = new_pdeq1(cloud->master);
861 bitset_t *seen = bitset_malloc(get_irg_last_idx(env->co->irg));
862 co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
866 bitset_set(seen, get_irn_idx(cloud->master->irn));
867 while(!pdeq_empty(q)) {
868 co2_irn_t *curr = pdeq_getl(q);
870 cloud->seq[j++] = curr;
871 get_neighb_arr(env, curr, nbs);
873 for(i = 0; i < curr->aff->degree; ++i) {
874 co2_irn_t *ni = nbs[i];
875 int idx = get_irn_idx(ni->irn);
876 if(!bitset_is_set(seen, idx)) {
878 bitset_set(seen, idx);
887 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
889 be_ifg_t *ifg = env->co->cenv->ifg;
890 co2_irn_t *ci = get_co2_irn(env, a->irn);
894 if(ci->visited >= env->visited)
897 /* mark the node as visited and add it to the cloud. */
898 ci->visited = env->visited;
900 list_add(&ci->cloud_list, &cloud->members_head);
902 DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
904 /* determine the nodes costs */
905 co_gs_foreach_neighb(a, n) {
907 DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
908 if(be_ifg_connected(ifg, a->irn, n->irn))
909 cloud->inevit += n->costs;
912 /* add the node's cost to the total costs of the cloud. */
914 cloud->costs += costs;
915 cloud->max_degree = MAX(cloud->max_degree, ci->aff->degree);
918 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
919 if(costs >= curr_costs) {
924 /* add all the neighbors of the node to the cloud. */
925 co_gs_foreach_neighb(a, n) {
926 affinity_node_t *an = get_affinity_info(env->co, n->irn);
928 populate_cloud(env, cloud, an, curr_costs);
932 static void init_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a)
935 populate_cloud(env, cloud, a, 0);
937 cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
938 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
940 cloud->seq[0] = cloud->master;
941 determine_coloring_sequence(env, cloud);
944 static void process_cloud(co2_t *env, co2_cloud_t *cloud)
946 struct list_head changed;
949 /* initialize the best coloring. */
950 examine_cloud_coloring(env, cloud);
952 DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
953 for(i = 0; i < cloud->n_memb; ++i) {
954 co2_irn_t *ci = cloud->seq[i];
955 DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
958 process_node(env, cloud, 0);
959 DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
961 /* re-try the best coloring. */
962 INIT_LIST_HEAD(&changed);
963 for(i = 0; i < cloud->n_memb; ++i) {
964 co2_irn_t *ci = cloud->seq[i];
965 col_t col = cloud->best_cols[i];
969 DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
970 ok = change_color_single(env, ci->irn, col, &changed, 0);
974 materialize_coloring(&changed);
979 for(ci = env->touched; ci; ci = ci->touched_next) {
982 ir_printf("%+F is still temp fixed\n", ci->irn);
989 static void process(co2_t *env)
992 struct list_head cloud_head;
994 co2_cloud_t **clouds;
1002 INIT_LIST_HEAD(&cloud_head);
1005 co_gs_foreach_aff_node(env->co, a) {
1006 co2_irn_t *ci = get_co2_irn(env, a->irn);
1009 co2_cloud_t *cloud = new_cloud(env);
1011 init_cloud(env, cloud, a);
1012 list_add(&cloud->list, &cloud_head);
1018 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
1019 list_for_each_entry(co2_cloud_t, pos, &cloud_head, list)
1021 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
1023 for(i = 0; i < n_clouds; ++i) {
1024 init_costs += cloud_costs(env, clouds[i]);
1025 process_cloud(env, clouds[i]);
1026 all_costs += clouds[i]->costs;
1027 final_costs += clouds[i]->best_costs;
1030 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
1035 static void writeback_colors(co2_t *env)
1037 const arch_env_t *aenv = env->co->aenv;
1040 for(irn = env->touched; irn; irn = irn->touched_next) {
1041 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
1042 arch_set_irn_register(aenv, irn->irn, reg);
1046 void co_solve_heuristic_new(copy_opt_t *co)
1050 phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
1054 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1055 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1056 bitset_flip_all(env.ignore_regs);
1057 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1058 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1061 writeback_colors(&env);
1062 phase_free(&env.ph);