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;
45 struct list_head cloud_head;
46 DEBUG_ONLY(firm_dbg_module_t *dbg;)
52 co2_irn_t *touched_next;
59 int last_color_change;
61 unsigned tmp_fixed : 1;
62 struct list_head changed_list;
63 struct list_head cloud_list;
77 int **failrure_matrix;
78 struct list_head members_head;
79 struct list_head list;
82 #define NEIGHBOR_FIXED 1
83 #define NEIGHBOR_CONSTR 2
93 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
95 static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
97 co2_t *env = (co2_t *) ph;
98 co2_irn_t *ci = data ? data : phase_alloc(ph, sizeof(ci[0]));
100 memset(ci, 0, sizeof(ci[0]));
101 INIT_LIST_HEAD(&ci->changed_list);
102 INIT_LIST_HEAD(&ci->cloud_list);
104 ci->touched_next = env->touched;
105 ci->orig_col = get_irn_col(env->co, irn);
106 ci->aff = get_affinity_info(env->co, (ir_node *)irn);
112 static int co2_irn_cmp(const void *a, const void *b)
114 const co2_irn_t **p = a;
115 const co2_irn_t **q = b;
116 return (*q)->costs - (*p)->costs;
119 static int cmp_clouds(const void *a, const void *b)
121 const co2_cloud_t **p = a;
122 const co2_cloud_t **q = b;
123 return (*q)->costs - (*p)->costs;
127 * An order on color/costs pairs.
128 * If the costs are equal, we use the color as a kind of normalization.
130 static int col_cost_pair_lt(const void *a, const void *b)
132 const col_cost_pair_t *p = a;
133 const col_cost_pair_t *q = b;
137 return (c > d) - (c < d);
140 const char *flag_str(unsigned int fl)
144 buf[0] = fl & NEIGHBOR_CONSTR ? 'c' : '-';
145 buf[1] = fl & NEIGHBOR_FIXED ? 'n' : '-';
146 buf[2] = fl & SELF_CONSTR ? 'C' : '-';
147 buf[3] = fl & DONT_WANT ? 'd' : '-';
152 static col_t get_col(co2_t *env, ir_node *irn)
154 co2_irn_t *ci = get_co2_irn(env, irn);
155 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
158 static INLINE int color_is_fix(co2_t *env, ir_node *irn)
160 co2_irn_t *ci = get_co2_irn(env, irn);
161 return ci->fixed || ci->tmp_fixed;
164 static bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
166 arch_register_req_t req;
168 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
169 if(arch_register_req_is(&req, limited))
170 req.limited(req.limited_env, bs);
172 bitset_copy(bs, env->ignore_regs);
179 static int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
181 bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
182 admissible_colors(env, ci, bs);
183 return bitset_is_set(bs, col);
186 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
188 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
189 arch_register_req_t req;
191 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
193 if(arch_register_req_is(&req, limited)) {
197 req.limited(req.limited_env, aux);
198 n_constr = bitset_popcnt(aux);
199 bitset_foreach(aux, elm) {
200 col_costs[elm].costs = add_saturated(col_costs[elm].costs, costs / n_constr);
201 col_costs[elm].flags |= NEIGHBOR_CONSTR;
207 * Determine costs which shall indicate how cheap/expensive it is to try
208 * to assign a node some color.
209 * The costs are computed for all colors. INT_MAX means that it is impossible
210 * to give the node that specific color.
212 * @param env The co2 this pointer.
213 * @param irn The node.
214 * @param col_costs An array of colors x costs where the costs are written to.
216 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
218 ir_node *irn = ci->irn;
219 be_ifg_t *ifg = env->co->cenv->ifg;
220 int n_regs = env->co->cls->n_regs;
221 bitset_t *forb = bitset_alloca(n_regs);
222 affinity_node_t *a = get_affinity_info(env->co, irn);
230 if(get_irn_node_nr(irn) == 2040) {
235 /* Put all forbidden colors into the aux bitset. */
236 admissible_colors(env, ci, forb);
237 bitset_flip_all(forb);
239 for(i = 0; i < n_regs; ++i) {
240 col_costs[i].col = i;
241 col_costs[i].costs = 0;
242 col_costs[i].flags = 0;
248 co_gs_foreach_neighb(a, n) {
249 if(color_is_fix(env, n->irn)) {
250 col_t col = get_col(env, n->irn);
251 col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
254 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
258 it = be_ifg_neighbours_iter_alloca(ifg);
259 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
260 col_t col = get_col(env, pos);
261 if(color_is_fix(env, pos)) {
262 col_costs[col].costs = INT_MAX;
263 col_costs[col].flags |= NEIGHBOR_FIXED;
266 incur_constraint_costs(env, pos, col_costs, INT_MAX);
267 col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
271 /* Set the costs to infinity for each color which is not allowed at this node. */
272 bitset_foreach(forb, elm) {
273 col_costs[elm].costs = INT_MAX;
274 col_costs[elm].flags |= SELF_CONSTR;
279 static void single_color_cost(co2_t *env, col_t col, col_cost_pair_t *seq)
281 int n_regs = env->co->cls->n_regs;
284 for(i = 0; i < n_regs; ++i) {
286 seq[i].costs = INT_MAX;
288 seq[i].flags = DONT_WANT;
297 static int curr_costs(co2_t *env, affinity_node_t *a)
299 col_t a_col = get_col(env, a->irn);
303 co_gs_foreach_neighb(a, n) {
304 col_t n_col = get_col(env, n->irn);
305 costs += n_col != a_col ? n->costs : 0;
311 static int cloud_costs(co2_t *env, co2_cloud_t *cloud)
316 list_for_each_entry(co2_irn_t, ci, &cloud->members_head, cloud_list) {
317 affinity_node_t *a = get_affinity_info(env->co, ci->irn);
318 costs += curr_costs(env, a);
324 static void reject_coloring(struct list_head *h)
328 list_for_each_entry(co2_irn_t, pos, h, changed_list)
332 static void materialize_coloring(struct list_head *h)
336 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
337 pos->orig_col = pos->tmp_col;
347 static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
352 list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
354 ent.col = pos->tmp_col;
356 obstack_grow(obst, &ent, sizeof(ent));
358 memset(&ent, 0, sizeof(ent));
359 obstack_grow(obst, &ent, sizeof(ent));
360 return obstack_finish(obst);
363 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
364 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
366 static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
368 int n_regs = env->co->cls->n_regs;
369 be_ifg_t *ifg = env->co->cenv->ifg;
370 co2_irn_t *ci = get_co2_irn(env, irn);
376 for(i = 0; i < n_regs; ++i) {
377 col_t tgt_col = col_list[i].col;
378 unsigned costs = col_list[i].costs;
381 struct list_head changed;
385 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
387 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
388 if(INFEASIBLE(costs)) {
389 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)));
394 /* Set the new color of the node and mark the node as temporarily fixed. */
395 ci->tmp_col = tgt_col;
399 If that color has costs > 0, there's at least one neighbor having that color,
400 so we will try to change the neighbors' colors, too.
402 INIT_LIST_HEAD(&changed);
403 list_add(&ci->changed_list, &changed);
405 it = be_ifg_neighbours_iter_alloca(ifg);
406 be_ifg_foreach_neighbour(ifg, it, irn, n) {
408 /* try to re-color the neighbor if it has the target color. */
409 if(get_col(env, n) == tgt_col) {
410 struct list_head tmp;
413 Try to change the color of the neighbor and record all nodes which
414 get changed in the tmp list. Add this list to the "changed" list for
415 that color. If we did not succeed to change the color of the neighbor,
416 we bail out and try the next color.
418 INIT_LIST_HEAD(&tmp);
419 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
420 list_splice(&tmp, &changed);
427 We managed to assign the target color to all neighbors, so from the perspective
428 of the current node, every thing was ok and we can return safely.
431 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
432 list_splice(&changed, parent_changed);
438 If not, that color did not succeed and we unfix all nodes we touched
439 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
442 reject_coloring(&changed);
448 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
450 co2_irn_t *ci = get_co2_irn(env, irn);
452 col_t col = get_col(env, irn);
454 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
456 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
463 list_add(&ci->changed_list, parent_changed);
467 /* The node has the color it should not have _and_ has not been visited yet. */
468 if(!color_is_fix(env, irn)) {
469 int n_regs = env->co->cls->n_regs;
470 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
472 /* Get the costs for giving the node a specific color. */
473 determine_color_costs(env, ci, csts);
475 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
476 csts[not_col].costs = INT_MAX;
478 /* sort the colors according costs, cheapest first. */
479 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
481 /* Try recoloring the node using the color list. */
482 res = recolor(env, irn, csts, parent_changed, depth);
485 /* If we came here, everything went ok. */
489 static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
491 co2_irn_t *ci = get_co2_irn(env, irn);
492 col_t col = get_col(env, irn);
495 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
497 /* the node has the wanted color. That's fine, mark it as visited and return. */
502 list_add(&ci->changed_list, parent_changed);
505 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}ok\n", depth));
509 if(!color_is_fix(env, irn)) {
510 int n_regs = env->co->cls->n_regs;
511 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
513 /* Get the costs for giving the node a specific color. */
514 single_color_cost(env, tgt_col, seq);
516 /* Try recoloring the node using the color list. */
517 res = recolor(env, irn, seq, parent_changed, depth);
519 DB((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d %s for %+F\n", depth, tgt_col, res ? "was ok" : "failed", irn));
525 static void examine_cloud_coloring(co2_t *env, co2_cloud_t *cloud)
527 int costs = cloud_costs(env, cloud);
529 if(costs < cloud->best_costs) {
532 for(i = 0; i < cloud->n_memb; ++i)
533 cloud->best_cols[i] = get_col(env, cloud->seq[i]->irn);
535 cloud->best_costs = costs;
539 static int color_change_balance(co2_t *env, co2_irn_t *ci, bitset_t *tried_colors, int depth)
541 col_t col = get_col(env, ci->irn);
545 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}node %+F has color %d\n", depth, ci->irn, col));
546 co_gs_foreach_neighb(ci->aff, n) {
547 col_t nc = get_col(env, n->irn);
548 int fixed = color_is_fix(env, n->irn);
554 else if(!bitset_is_set(tried_colors, nc))
564 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}neighbor %+F has the same color, bonus %d\n", depth, n->irn, -n->costs));
568 DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}non fixed neighbor %+F has different color %d, malus %d\n", depth, n->irn, nc, n->costs));
576 static void adjust_start_colors(co2_t *env, co2_cloud_t *cloud, col_cost_pair_t *seq)
578 int n_regs = env->co->cls->n_regs;
579 bitset_t *adm = bitset_alloca(n_regs);
583 for(i = 0; i < cloud->n_memb; ++i) {
584 co2_irn_t *ci = cloud->seq[i];
587 /* Prefer precolored neighbors. */
588 bitset_clear_all(adm);
589 admissible_colors(env, ci, adm);
590 n_constr = bitset_popcnt(adm);
592 bitset_foreach(adm, col) {
593 seq[col].costs = add_saturated(seq[col].costs, -128 * (n_regs - n_constr));
596 bitset_foreach_clear(adm, col) {
597 seq[col].costs = add_saturated(seq[col].costs, 128);
601 admissible_colors(env, cloud->master, adm);
602 bitset_flip_all(adm);
604 bitset_foreach(adm, col)
605 seq[col].costs = INT_MAX;
608 static int process_node(co2_t *env, co2_cloud_t *cloud, int index)
610 struct list_head changed;
613 if(index < cloud->n_memb) {
614 co2_irn_t *ci = cloud->seq[index];
615 int n_regs = env->co->cls->n_regs;
616 col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
617 bitset_t *cols_tried = bitset_alloca(n_regs);
626 Investigate if one of the fixed neighbors of this node has changed
627 its color since this node changed its color. If so we will
628 consider changing this node's color again.
631 co_gs_foreach_neighb(ci->aff, n) {
632 co2_irn_t *ni = get_co2_irn(env, n->irn);
633 n_fixed += ni->fixed;
634 n_new_fixed += ni->fixed && ni->last_color_change > ci->last_color_change;
637 if(n_fixed > 0 && n_new_fixed == 0)
638 return process_node(env, cloud, index + 1);
640 determine_color_costs(env, ci, seq);
642 /* If this is the first node, adjust the sequence of the coloring. */
644 adjust_start_colors(env, cloud, seq);
646 qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
648 for(i = 0; i < n_regs && !done; ++i) {
649 col_t col = seq[i].col;
650 int costs = seq[i].costs;
654 if all affinity neighbors fixed,
655 try only color changes to affinity colors.
656 all other colors do no good.
659 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}trying %+F index %d for color %d\n", index, ci->irn, index, col));
660 if(INFEASIBLE(costs)) {
661 DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> color is infeasible due to %s\n", index, flag_str(seq[i].flags)));
665 bitset_set(cols_tried, col);
666 INIT_LIST_HEAD(&changed);
668 ok = change_color_single(env, ci->irn, col, &changed, index);
669 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", index, ok ? "ok" : "failed"));
671 /* if we succeeded changing the color, we will figure out the next node. */
676 /* Mark the time of the last color change */
677 ci->last_color_change = cloud->ticks;
679 /* materialize the coloring and fix the node's color. */
682 /* process the next nodes. if the function returns one, we found an optimal coloring already, so get out. */
683 finish = process_node(env, cloud, index + 1);
685 /* if this is the last node in the coloring sequence, examine the coloring */
686 if(index == cloud->n_memb - 1) {
687 examine_cloud_coloring(env, cloud);
688 DB((env->dbg, LEVEL_2, "\t%2{firm:indent}-> current best coloring %d\n", index, cloud->best_costs));
689 if(cloud->best_costs == cloud->inevit)
693 /* Compute the recoloring balance for this solution. */
694 balance = color_change_balance(env, ci, cols_tried, index);
695 DBG((env->dbg, LEVEL_3, "\t%2{firm:indent}balance for further color changing: %d\n", index, balance));
697 /* unfix the node. */
698 reject_coloring(&changed);
701 if(finish || balance <= 0) {
712 static co2_irn_t **get_neighb_arr(co2_t *env, co2_irn_t *ci, co2_irn_t **nbs)
718 co_gs_foreach_neighb(ci->aff, n) {
719 nbs[i++] = get_co2_irn(env, n->irn);
722 qsort(nbs, ci->aff->degree, sizeof(nbs[0]), co2_irn_cmp);
726 static void determine_coloring_sequence(co2_t *env, co2_cloud_t *cloud)
728 pdeq *q = new_pdeq1(cloud->master);
729 bitset_t *seen = bitset_malloc(get_irg_last_idx(env->co->irg));
730 co2_irn_t **nbs = alloca(cloud->max_degree * sizeof(nbs[0]));
734 bitset_set(seen, get_irn_idx(cloud->master->irn));
735 while(!pdeq_empty(q)) {
736 co2_irn_t *curr = pdeq_getl(q);
738 cloud->seq[j++] = curr;
739 get_neighb_arr(env, curr, nbs);
741 for(i = 0; i < curr->aff->degree; ++i) {
742 co2_irn_t *ni = nbs[i];
743 int idx = get_irn_idx(ni->irn);
744 if(!bitset_is_set(seen, idx)) {
746 bitset_set(seen, idx);
755 static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
757 be_ifg_t *ifg = env->co->cenv->ifg;
758 co2_irn_t *ci = get_co2_irn(env, a->irn);
762 if(ci->visited >= env->visited)
765 /* mark the node as visited and add it to the cloud. */
766 ci->visited = env->visited;
768 list_add(&ci->cloud_list, &cloud->members_head);
770 DB((env->dbg, LEVEL_3, "%+F\n", ci->irn));
772 /* determine the nodes costs */
773 co_gs_foreach_neighb(a, n) {
775 DB((env->dbg, LEVEL_3, "\t%+F\n", n->irn));
776 if(be_ifg_connected(ifg, a->irn, n->irn))
777 cloud->inevit += n->costs;
780 /* add the node's cost to the total costs of the cloud. */
782 cloud->costs += costs;
783 cloud->max_degree = MAX(cloud->max_degree, ci->aff->degree);
786 /* If this is the heaviest node in the cloud, set it as the cloud's master. */
787 if(costs >= curr_costs) {
792 /* add all the neighbors of the node to the cloud. */
793 co_gs_foreach_neighb(a, n) {
794 affinity_node_t *an = get_affinity_info(env->co, n->irn);
796 populate_cloud(env, cloud, an, curr_costs);
800 static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
802 co2_cloud_t *cloud = phase_alloc(&env->ph, sizeof(cloud[0]));
803 memset(cloud, 0, sizeof(cloud[0]));
804 INIT_LIST_HEAD(&cloud->members_head);
805 INIT_LIST_HEAD(&cloud->list);
806 list_add(&cloud->list, &env->cloud_head);
807 cloud->best_costs = INT_MAX;
810 populate_cloud(env, cloud, a, 0);
812 /* Allocate space for the best colors array, where the best coloring is saved. */
813 cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
815 /* Also allocate space for the node sequence and compute that sequence. */
816 cloud->seq = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
817 cloud->seq[0] = cloud->master;
819 determine_coloring_sequence(env, cloud);
822 /* Allocate the failure matrix. */
823 cloud->failrure_matrix = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->failrure_matrix[0]));
824 for(i = 0; i < env->n_regs; ++i) {
825 cloud->failrure_matrix[i] = phase_alloc(&env->ph, env->n_regs * sizeof(cloud->failrure_matrix[i][0]));
826 memset(cloud->failrure_matrix[i], 0, env->n_regs * sizeof(cloud->failrure_matrix[i][0]));
832 static void process_cloud(co2_t *env, co2_cloud_t *cloud, int nr)
834 struct list_head changed;
837 /* initialize the best coloring. */
838 examine_cloud_coloring(env, cloud);
840 DB((env->dbg, LEVEL_1, "\nnew cloud\nall costs %d, initial costs %d, inevit %d\n", cloud->costs, cloud->best_costs, cloud->inevit));
841 for(i = 0; i < cloud->n_memb; ++i) {
842 co2_irn_t *ci = cloud->seq[i];
843 DB((env->dbg, LEVEL_1, "\tmember %+F cost %d col %d\n", ci->irn, ci->costs, get_col(env, ci->irn)));
846 process_node(env, cloud, 0);
847 DB((env->dbg, LEVEL_1, "final coloring costs %d\n", cloud->best_costs));
849 /* re-try the best coloring. */
850 INIT_LIST_HEAD(&changed);
851 for(i = 0; i < cloud->n_memb; ++i) {
852 co2_irn_t *ci = cloud->seq[i];
853 col_t col = cloud->best_cols[i];
857 DB((env->dbg, LEVEL_2, "\tsetting %+F to %d\n", ci->irn, col));
858 ok = change_color_single(env, ci->irn, col, &changed, 0);
862 materialize_coloring(&changed);
867 for(ci = env->touched; ci; ci = ci->touched_next) {
870 ir_printf("%+F is still temp fixed\n", ci->irn);
880 ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, nr);
881 if(f = fopen(buf, "wt")) {
882 be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
889 static void process(co2_t *env)
893 co2_cloud_t **clouds;
901 co_gs_foreach_aff_node(env->co, a) {
902 co2_irn_t *ci = get_co2_irn(env, a->irn);
905 co2_cloud_t *cloud = new_cloud(env, a);
911 clouds = xmalloc(n_clouds * sizeof(clouds[0]));
912 list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
914 qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds);
916 for(i = 0; i < n_clouds; ++i) {
917 init_costs += cloud_costs(env, clouds[i]);
918 process_cloud(env, clouds[i], i);
919 all_costs += clouds[i]->costs;
920 final_costs += clouds[i]->best_costs;
923 DB((env->dbg, LEVEL_1, "all costs: %d, init costs: %d, final costs: %d\n", all_costs, init_costs, final_costs));
928 static void writeback_colors(co2_t *env)
930 const arch_env_t *aenv = env->co->aenv;
933 for(irn = env->touched; irn; irn = irn->touched_next) {
934 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
935 arch_set_irn_register(aenv, irn->irn, reg);
940 ___ _____ ____ ____ ___ _____ ____ _
941 |_ _| ___/ ___| | _ \ / _ \_ _| | _ \ _ _ _ __ ___ _ __ (_)_ __ __ _
942 | || |_ | | _ | | | | | | || | | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
943 | || _|| |_| | | |_| | |_| || | | |_| | |_| | | | | | | |_) | | | | | (_| |
944 |___|_| \____| |____/ \___/ |_| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
948 static const char *get_dot_color_name(int col)
950 static const char *names[] = {
984 return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
987 static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
989 arch_register_req_t req;
991 arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
992 if(arch_register_req_is(&req, limited))
1004 static void ifg_dump_graph_attr(FILE *f, void *self)
1006 fprintf(f, "overlay=false");
1009 static int ifg_is_dump_node(void *self, ir_node *irn)
1012 return !arch_irn_is(env->co->aenv, irn, ignore);
1015 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
1018 co2_irn_t *ci = get_co2_irn(env, irn);
1020 ir_fprintf(f, "label=\"%+F,%d\" style=filled color=%s shape=%s", irn, ci->costs,
1021 get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
1024 static void ifg_dump_at_end(FILE *file, void *self)
1029 co_gs_foreach_aff_node(env->co, a) {
1030 int idx = get_irn_idx(a->irn);
1033 co_gs_foreach_neighb(a, n) {
1034 int nidx = get_irn_idx(n->irn);
1037 const char *style = get_col(env, a->irn) == get_col(env, n->irn) ? "dashed" : "dotted";
1038 fprintf(file, "\tn%d -- n%d [label=\"%d\" style=%s weight=0.01];\n", idx, nidx, n->costs, style);
1045 static be_ifg_dump_dot_cb_t ifg_dot_cb = {
1047 ifg_dump_graph_attr,
1054 void co_solve_heuristic_new(copy_opt_t *co)
1059 phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
1063 env.ignore_regs = bitset_alloca(co->cls->n_regs);
1064 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
1065 bitset_flip_all(env.ignore_regs);
1066 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
1067 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
1068 INIT_LIST_HEAD(&env.cloud_head);
1070 if(f = be_chordal_open(co->cenv, "ifg_before_", "dot")) {
1071 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1077 if(f = be_chordal_open(co->cenv, "ifg_after_", "dot")) {
1078 be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
1082 writeback_colors(&env);
1083 phase_free(&env.ph);