3 * More experiments on coalescing.
4 * @author Sebastian Hack
15 #include "irphase_t.h"
16 #include "irgraph_t.h"
22 #include "becopyopt.h"
23 #include "becopyopt_t.h"
24 #include "bechordal_t.h"
26 typedef unsigned col_t;
28 typedef struct _co2_irn_t co2_irn_t;
33 bitset_t *ignore_regs;
35 DEBUG_ONLY(firm_dbg_module_t *dbg;)
40 co2_irn_t *touched_next;
45 unsigned tmp_fixed : 1;
46 struct list_head changed_list;
49 #define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
51 static void co2_irn_init(phase_t *ph, ir_node *irn, void *data)
53 co2_t *env = (co2_t *) ph;
56 memset(ci, 0, sizeof(ci[0]));
57 INIT_LIST_HEAD(&ci->changed_list);
59 ci->touched_next = env->touched;
60 ci->orig_col = get_irn_col(env->co, irn);
65 static int co2_irn_cmp(const void *a, const void *b)
67 const co2_irn_t **p = a;
68 const co2_irn_t **q = b;
69 return (*q)->costs - (*p)->costs;
78 * An order on color/costs pairs.
79 * If the costs are equal, we use the color as a kind of normalization.
81 static int col_cost_pair_lt(const void *a, const void *b)
83 const col_cost_pair_t *p = a;
84 const col_cost_pair_t *q = b;
85 int cost_diff = p->costs - q->costs;
88 // return cost_diff != 0 ? cost_diff : p->col - q->col;
91 static col_t get_col(co2_t *env, ir_node *irn)
93 co2_irn_t *ci = get_co2_irn(env, irn);
94 return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
97 static INLINE color_is_fix(co2_t *env, ir_node *irn)
99 co2_irn_t *ci = get_co2_irn(env, irn);
100 return ci->fixed || ci->tmp_fixed;
103 static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
105 bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
106 arch_register_req_t req;
108 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
110 if(arch_register_req_is(&req, limited)) {
114 req.limited(req.limited_env, aux);
115 n_constr = bitset_popcnt(aux);
116 bitset_foreach(aux, elm)
117 col_costs[elm].costs += costs / n_constr;
122 * Determine costs which shall indicate how cheap/expensive it is to try
123 * to assign a node some color.
124 * The costs are computed for all colors. INT_MAX means that it is impossible
125 * to give the node that specific color.
127 * @param env The co2 this pointer.
128 * @param irn The node.
129 * @param col_costs An array of colors x costs where the costs are written to.
131 static void determine_color_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs)
133 be_ifg_t *ifg = env->co->cenv->ifg;
134 int n_regs = env->co->cls->n_regs;
135 bitset_t *forb = bitset_alloca(n_regs);
136 affinity_node_t *a = get_affinity_info(env->co, irn);
138 arch_register_req_t req;
144 /* Put all forbidden colors into the aux bitset. */
145 arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
146 if(arch_register_req_is(&req, limited)) {
147 req.limited(req.limited_env, forb);
148 bitset_flip_all(forb);
151 bitset_copy(forb, env->ignore_regs);
153 for(i = 0; i < n_regs; ++i) {
154 col_costs[i].col = i;
155 col_costs[i].costs = 0;
161 co_gs_foreach_neighb(a, n) {
162 co2_irn_t *ni = get_co2_irn(env, n->irn);
165 col_t col = get_col(env, n->irn);
166 col_costs[col].costs -= 100 * n->costs;
169 incur_constraint_costs(env, n->irn, col_costs, -n->costs);
173 it = be_ifg_neighbours_iter_alloca(ifg);
174 be_ifg_foreach_neighbour(ifg, it, irn, pos) {
175 col_t col = get_col(env, pos);
176 if(color_is_fix(env, pos))
177 col_costs[col].costs = INT_MAX;
179 incur_constraint_costs(env, pos, col_costs, INT_MAX);
180 col_costs[col].costs++;
184 /* Set the costs to infinity for each color which is not allowed at this node. */
185 bitset_foreach(forb, elm)
186 col_costs[elm].costs = INT_MAX;
190 static int curr_costs(co2_t *env, affinity_node_t *a)
192 col_t a_col = get_col(env, a->irn);
196 co_gs_foreach_neighb(a, n) {
197 col_t n_col = get_col(env, n->irn);
198 costs += n_col != a_col ? n->costs : 0;
204 static void reject_coloring(struct list_head *h)
208 list_for_each_entry(co2_irn_t, pos, h, changed_list)
212 static void materialize_coloring(co2_t *env, struct list_head *h)
214 const arch_register_class_t *cls = env->co->cls;
215 const arch_env_t *aenv = env->co->aenv;
218 list_for_each_entry(co2_irn_t, pos, h, changed_list) {
219 pos->orig_col = pos->tmp_col;
224 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
227 static INLINE int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, int n_regs, struct list_head *parent_changed, int depth)
229 be_ifg_t *ifg = env->co->cenv->ifg;
230 co2_irn_t *ci = get_co2_irn(env, irn);
235 for(i = 0; i < n_regs; ++i) {
236 col_t tgt_col = col_list[i].col;
237 unsigned costs = col_list[i].costs;
240 struct list_head changed;
244 DBG((env->dbg, LEVEL_2, "\t%2Dtrying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
246 /* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
247 if(costs == INT_MAX) {
252 /* Set the new color of the node and mark the node as temporarily fixed. */
253 ci->tmp_col = tgt_col;
257 If that color has costs > 0, there's at least one neighbor having that color,
258 so we will try to change the neighbors' colors, too.
260 INIT_LIST_HEAD(&changed);
261 list_add(&ci->changed_list, &changed);
263 it = be_ifg_neighbours_iter_alloca(ifg);
264 be_ifg_foreach_neighbour(ifg, it, irn, n) {
266 /* try to re-color the neighbor if it has the target color. */
267 if(get_col(env, n) == tgt_col) {
268 struct list_head tmp;
271 Try to change the color of the neighbor and record all nodes which
272 get changed in the tmp list. Add this list to the "changed" list for
273 that color. If we did not succeed to change the color of the neighbor,
274 we bail out and try the next color.
276 INIT_LIST_HEAD(&tmp);
277 neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
278 list_splice(&tmp, &changed);
286 We managed to assign the target color to all neighbors, so from the perspective
287 of the current node, every thing was ok and we can return safely.
290 DBG((env->dbg, LEVEL_2, "\t%2Dcolor %d(%d) was ok\n", depth, tgt_col, costs));
291 list_splice(&changed, parent_changed);
297 If not, that color did not succeed and we unfix all nodes we touched
298 by traversing the changed list and setting tmp_fixed to 0 for these nodes.
301 reject_coloring(&changed);
307 static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
309 co2_irn_t *ci = get_co2_irn(env, irn);
311 col_t col = get_col(env, irn);
313 DBG((env->dbg, LEVEL_2, "\t%2Dclearing %+F(%d) of color %d\n", depth, irn, col, not_col));
315 /* the node does not have to forbidden color. That's fine, mark it as visited and return. */
322 list_add(&ci->changed_list, parent_changed);
326 /* The node has the color it should not have _and_ has not been visited yet. */
327 if(!color_is_fix(env, irn)) {
328 int n_regs = env->co->cls->n_regs;
329 col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
331 /* Get the costs for giving the node a specific color. */
332 determine_color_costs(env, irn, csts);
334 /* Since the node must not have the not_col, set the costs for that color to "infinity" */
335 csts[not_col].costs = INT_MAX;
337 /* sort the colors according costs, cheapest first. */
338 qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
340 /* Try recoloring the node using the color list. */
341 res = recolor(env, irn, csts, n_regs, parent_changed, depth);
344 /* If we came here, everything went ok. */
349 * Try to bring a node to a certain color.
351 static int try_color(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *changed)
353 co2_irn_t *ci = get_co2_irn(env, irn);
354 be_ifg_t *ifg = env->co->cenv->ifg;
360 ci->tmp_col = tgt_col;
361 list_add(&ci->changed_list, changed);
363 it = be_ifg_neighbours_iter_alloca(ifg);
364 be_ifg_foreach_neighbour(ifg, it, irn, n) {
365 col_t c = get_col(env, n);
367 /* If the neighbor has the target color, re-color the neighbor. */
369 int ok = change_color_not(env, n, tgt_col, changed, 1);
378 static INLINE int costs_sufficient(co2_irn_t *irn, int costs)
380 return costs == -irn->costs;
383 static void process_affinity_node(co2_t *env, co2_irn_t *ci)
385 int n_regs = env->co->cls->n_regs;
386 col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0]));
387 affinity_node_t *a = get_affinity_info(env->co, ci->irn);
388 int best_cost = curr_costs(env, a);
389 col_t best_col = ci->orig_col;
394 assert(a != NULL && "This node must be an affinity node");
396 /* If that node has already been fixed, leave it alone. */
400 DB((env->dbg, LEVEL_1, "affinity node %+F cost %d\n", ci->irn, ci->costs));
402 /* determine the order in which the colors shall be tried. */
403 determine_color_costs(env, ci->irn, col_seq);
404 qsort(col_seq, n_regs, sizeof(col_seq[0]), col_cost_pair_lt);
406 /* Try the colors. */
407 for(i = 0; i < n_regs; ++i) {
408 col_t col = col_seq[i].col;
409 int costs = col_seq[i].costs;
411 struct list_head changed;
414 DB((env->dbg, LEVEL_2, "\tbest color %d incurring costs %d\n", best_col, best_cost));
416 /* Also, if the costs are not more optimizable, we do not try additional colors and finish this node. */
420 if(costs == INT_MAX) {
421 DB((env->dbg, LEVEL_1, "\tall following colors after %d will be infeasible\n", col));
425 INIT_LIST_HEAD(&changed);
427 DB((env->dbg, LEVEL_1, "\ttrying color %d costing %d\n", col, costs));
429 /* try to assign the same color to the node and all its neighbors. */
430 ok = try_color(env, a->irn, col, &changed);
433 DBG((env->dbg, LEVEL_2, "\t-> failed.\n"));
434 reject_coloring(&changed);
439 Evaluate the recoloring and mark it is as new best if it was better
440 as the best current known solution.
442 costs = curr_costs(env, a);
443 DBG((env->dbg, LEVEL_2, "\t-> cost: %d\n", costs));
445 if(costs < best_cost) {
449 materialize_coloring(env, &changed);
452 /* If we had a better coloring already, reject the current one. */
454 reject_coloring(&changed);
458 /* We found the definite color for this node, so fix it. */
461 DB((env->dbg, LEVEL_1, "\tusing %d(%d)\n", best_col, best_cost));
463 /* Now, investigate all affinity neighbors of this node. */
465 co2_irn_t **neighbors = alloca(a->degree * sizeof(neighbors[0]));
468 co_gs_foreach_neighb(a, n)
469 neighbors[i++] = get_co2_irn(env, n->irn);
471 qsort(neighbors, a->degree, sizeof(neighbors[0]), co2_irn_cmp);
472 for(i = 0; i < a->degree; ++i)
473 process_affinity_node(env, neighbors[i]);
477 static void process(co2_t *env)
487 co_gs_foreach_aff_node(env->co, an) {
488 ir_node *irn = an->irn;
489 co2_irn_t *ci = get_co2_irn(env, irn);
493 co_gs_foreach_neighb(an, neighb)
494 ci->costs += neighb->costs;
496 obstack_ptr_grow(&obst, ci);
500 nodes = obstack_finish(&obst);
502 /* sort the nodes according to processing order. */
503 qsort(nodes, n, sizeof(nodes[0]), co2_irn_cmp);
505 for(i = 0; i < n; ++i) {
507 process_affinity_node(env, nodes[i]);
510 obstack_free(&obst, NULL);
513 static void writeback_colors(co2_t *env)
515 const arch_env_t *aenv = env->co->aenv;
518 for(irn = env->touched; irn; irn = irn->touched_next) {
519 const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
520 arch_set_irn_register(aenv, irn->irn, reg);
524 void co_solve_heuristic_new(copy_opt_t *co)
528 phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
531 env.ignore_regs = bitset_alloca(co->cls->n_regs);
532 arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
533 bitset_flip_all(env.ignore_regs);
534 be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
535 FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
538 writeback_colors(&env);