2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
30 #include "bipartite.h"
31 #include "hungarian.h"
34 #include "irgraph_t.h"
35 #include "irprintf_t.h"
45 #include "besched_t.h"
52 #include "bestatevent.h"
55 #include "bechordal_t.h"
56 #include "bechordal_draw.h"
58 #define DBG_LEVEL SET_LEVEL_0
59 #define DBG_LEVEL_CHECK SET_LEVEL_0
63 #define DUMP_INTERVALS
65 typedef struct _be_chordal_alloc_env_t {
66 be_chordal_env_t *chordal_env;
68 pset *pre_colored; /**< Set of precolored nodes. */
69 bitset_t *live; /**< A liveness bitset. */
70 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
71 bitset_t *colors; /**< The color mask. */
72 bitset_t *in_colors; /**< Colors used by live in values. */
73 int colors_n; /**< The number of colors. */
74 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
75 } be_chordal_alloc_env_t;
79 /* Make a fourcc for border checking. */
80 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
83 static void check_border_list(struct list_head *head)
86 list_for_each_entry(border_t, x, head, list) {
87 assert(x->magic == BORDER_FOURCC);
91 static void check_heads(be_chordal_env_t *env)
94 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
95 /* ir_printf("checking border list of block %+F\n", ent->key); */
96 check_border_list(ent->value);
102 * Add an interval border to the list of a block's list
103 * of interval border.
104 * @note You always have to create the use before the def.
105 * @param env The environment.
106 * @param head The list head to enqueue the borders.
107 * @param irn The node (value) the border belongs to.
108 * @param pressure The pressure at this point in time.
109 * @param step A time step for the border.
110 * @param is_def Is the border a use or a def.
111 * @return The created border.
113 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
114 ir_node *irn, unsigned step, unsigned pressure,
115 unsigned is_def, unsigned is_real)
122 b = obstack_alloc(&env->obst, sizeof(*b));
124 /* also allocate the def and tie it to the use. */
125 def = obstack_alloc(&env->obst, sizeof(*def));
126 memset(def, 0, sizeof(*def));
131 * Set the link field of the irn to the def.
132 * This strongly relies on the fact, that the use is always
133 * made before the def.
135 set_irn_link(irn, def);
137 DEBUG_ONLY(b->magic = BORDER_FOURCC);
138 DEBUG_ONLY(def->magic = BORDER_FOURCC);
142 * If the def is encountered, the use was made and so was the
143 * the def node (see the code above). It was placed into the
144 * link field of the irn, so we can get it there.
147 b = get_irn_link(irn);
149 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
152 b->pressure = pressure;
154 b->is_real = is_real;
157 list_add_tail(&b->list, head);
158 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
165 * Check, if an irn is of the register class currently under processing.
166 * @param env The chordal environment.
167 * @param irn The node.
168 * @return 1, if the node is of that register class, 0 if not.
170 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
172 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
173 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
176 #define has_limited_constr(req, irn) \
177 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
179 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
181 bitset_t *tmp = alloc_env->tmp_colors;
182 bitset_copy(tmp, colors);
183 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
184 return bitset_next_clear(tmp, 0);
187 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
192 bitset_copy(bs, o2->regs);
197 bitset_copy(bs, o1->regs);
201 assert(o1->req.cls == o2->req.cls);
203 if(bitset_contains(o1->regs, o2->regs))
204 bitset_copy(bs, o1->regs);
205 else if(bitset_contains(o2->regs, o1->regs))
206 bitset_copy(bs, o2->regs);
213 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
217 ie.ignore_colors = env->ignore_colors;
218 ie.aenv = env->birg->main_env->arch_env;
219 ie.obst = &env->obst;
221 return be_scan_insn(&ie, irn);
224 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
226 const arch_env_t *aenv = env->birg->main_env->arch_env;
227 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
228 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
229 ir_node *bl = get_nodes_block(irn);
230 be_lv_t *lv = env->birg->lv;
235 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
236 ir_node *op = get_irn_n(irn, i);
238 const arch_register_t *reg;
239 arch_register_req_t req;
241 if (arch_get_irn_reg_class(aenv, irn, i) == env->cls) {
242 reg = arch_get_irn_register(aenv, op);
244 if (reg && arch_register_type_is(reg, ignore)) {
245 arch_get_register_req(aenv, &req, irn, i);
247 if (arch_register_req_is(&req, limited)) {
248 bitset_clear_all(tmp);
249 req.limited(req.limited_env, tmp);
251 if (! bitset_is_set(tmp, reg->index)) {
252 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
253 be_stat_ev("constr_copy", 1);
255 sched_add_before(irn, copy);
256 set_irn_n(irn, i, copy);
257 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
264 insn = chordal_scan_insn(env, irn);
266 if(!insn->has_constraints)
269 /* insert copies for nodes that occur constrained more than once. */
270 for(i = insn->use_start; i < insn->n_ops; ++i) {
271 be_operand_t *op = &insn->ops[i];
273 if(op->has_constraints) {
274 for(j = i + 1; j < insn->n_ops; ++j) {
275 be_operand_t *a_op = &insn->ops[j];
277 if(a_op->carrier == op->carrier && a_op->has_constraints) {
278 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
279 be_stat_ev("constr_copy", 1);
281 sched_add_before(insn->irn, copy);
282 set_irn_n(insn->irn, a_op->pos, copy);
283 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
289 /* collect all registers occuring in out constraints. */
290 for(i = 0; i < insn->use_start; ++i) {
291 be_operand_t *op = &insn->ops[i];
292 if(op->has_constraints)
293 bitset_or(def_constr, op->regs);
297 insert copies for all constrained arguments living through the node
298 and being constrained to a register which also occurs in out constraints.
300 for(i = insn->use_start; i < insn->n_ops; ++i) {
301 be_operand_t *op = &insn->ops[i];
303 bitset_copy(tmp, op->regs);
304 bitset_and(tmp, def_constr);
308 1) the operand is constrained.
309 2) lives through the node.
310 3) is constrained to a register occuring in out constraints.
312 if(op->has_constraints && values_interfere(lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
314 only create the copy if the operand is no copy.
315 this is necessary since the assure constraints phase inserts
316 Copies and Keeps for operands which must be different from the results.
317 Additional copies here would destroy this.
319 if(!be_is_Copy(op->carrier)) {
320 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
322 sched_add_before(insn->irn, copy);
323 set_irn_n(insn->irn, op->pos, copy);
324 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
325 be_liveness_update(lv, op->carrier);
331 obstack_free(&env->obst, insn);
332 return insn->next_insn;
335 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
337 be_chordal_env_t *env = data;
339 for(irn = sched_first(bl); !sched_is_end(irn);) {
340 irn = prepare_constr_insn(env, irn);
344 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
345 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
348 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
350 const be_chordal_env_t *env = alloc_env->chordal_env;
352 int n_uses = be_insn_n_uses(insn);
353 int n_defs = be_insn_n_defs(insn);
354 bitset_t *bs = bitset_alloca(env->cls->n_regs);
355 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
356 be_lv_t *lv = env->birg->lv;
361 For each out operand, try to find an in operand which can be assigned the
362 same register as the out operand.
364 for (j = 0; j < insn->use_start; ++j) {
366 int smallest_n_regs = 2 * env->cls->n_regs + 1;
367 be_operand_t *out_op = &insn->ops[j];
369 /* Try to find an in operand which has ... */
370 for(i = insn->use_start; i < insn->n_ops; ++i) {
372 const be_operand_t *op = &insn->ops[i];
374 if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
375 bitset_clear_all(bs);
376 bitset_copy(bs, op->regs);
377 bitset_and(bs, out_op->regs);
378 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
380 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
382 smallest_n_regs = n_total;
388 be_operand_t *partner = &insn->ops[smallest];
389 out_op->partner = partner;
390 partner->partner = out_op;
396 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
398 be_chordal_env_t *env = alloc_env->chordal_env;
399 const arch_env_t *aenv = env->birg->main_env->arch_env;
400 be_insn_t *insn = *the_insn;
401 ir_node *bl = get_nodes_block(insn->irn);
402 ir_node *copy = NULL;
403 ir_node *perm = NULL;
404 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
405 bitset_t *bs = bitset_alloca(env->cls->n_regs);
406 be_lv_t *lv = env->birg->lv;
407 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
411 assert(insn->has_constraints && "only do this for constrained nodes");
414 Collect all registers that occur in output constraints.
415 This is necessary, since if the insn has one of these as an input constraint
416 and the corresponding operand interferes with the insn, the operand must
419 for(i = 0; i < insn->use_start; ++i) {
420 be_operand_t *op = &insn->ops[i];
421 if(op->has_constraints)
422 bitset_or(out_constr, op->regs);
428 DEBUG_ONLY((void) dbg;)
431 Make the Perm, recompute liveness and re-scan the insn since the
432 in operands are now the Projs of the Perm.
434 perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
436 /* Registers are propagated by insert_Perm_after(). Clean them here! */
438 const ir_edge_t *edge;
440 be_stat_ev("constr_perm", get_irn_arity(perm));
441 foreach_out_edge(perm, edge) {
442 ir_node *proj = get_edge_src_irn(edge);
443 arch_set_irn_register(aenv, proj, NULL);
447 We also have to re-build the insn since the input operands are now the Projs of
448 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
449 the live sets may change.
451 // be_liveness_recompute(lv);
452 obstack_free(&env->obst, insn);
453 *the_insn = insn = chordal_scan_insn(env, insn->irn);
456 Copy the input constraints of the insn to the Perm as output
457 constraints. Succeeding phases (coalescing will need that).
459 for(i = insn->use_start; i < insn->n_ops; ++i) {
460 be_operand_t *op = &insn->ops[i];
461 ir_node *proj = op->carrier;
463 Note that the predecessor must not be a Proj of the Perm,
464 since ignore-nodes are not Perm'ed.
466 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
467 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
475 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
477 be_chordal_env_t *env = alloc_env->chordal_env;
478 void *base = obstack_base(&env->obst);
479 be_insn_t *insn = chordal_scan_insn(env, irn);
480 ir_node *res = insn->next_insn;
481 int be_silent = *silent;
482 be_lv_t *lv = env->birg->lv;
484 if(insn->pre_colored) {
486 for(i = 0; i < insn->use_start; ++i)
487 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
491 If the current node is a barrier toggle the silent flag.
492 If we are in the start block, we are ought to be silent at the beginning,
493 so the toggling activates the constraint handling but skips the barrier.
494 If we are in the end block we handle the in requirements of the barrier
495 and set the rest to silent.
497 if(be_is_Barrier(irn))
504 Perms inserted before the constraint handling phase are considered to be
505 correctly precolored. These Perms arise during the ABI handling phase.
507 if(insn->has_constraints) {
508 const arch_env_t *aenv = env->birg->main_env->arch_env;
509 int n_regs = env->cls->n_regs;
510 bitset_t *bs = bitset_alloca(n_regs);
511 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
512 hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
513 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
514 int *assignment = alloca(n_regs * sizeof(assignment[0]));
515 pmap *partners = pmap_create();
516 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
520 const ir_edge_t *edge;
521 ir_node *perm = NULL;
525 prepare the constraint handling of this node.
526 Perms are constructed and Copies are created for constrained values
527 interfering with the instruction.
529 perm = pre_process_constraints(alloc_env, &insn);
531 /* find suitable in operands to the out operands of the node. */
532 pair_up_operands(alloc_env, insn);
535 look at the in/out operands and add each operand (and its possible partner)
536 to a bipartite graph (left: nodes with partners, right: admissible colors).
538 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
539 be_operand_t *op = &insn->ops[i];
542 If the operand has no partner or the partner has not been marked
543 for allocation, determine the admissible registers and mark it
544 for allocation by associating the node and its partner with the
545 set of admissible registers via a bipartite graph.
547 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
549 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
550 alloc_nodes[n_alloc] = op->carrier;
552 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
554 bitset_clear_all(bs);
555 get_decisive_partner_regs(bs, op, op->partner);
557 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
559 bitset_foreach(bs, col)
560 hungarian_add(bp, n_alloc, col, 1);
561 // bipartite_add(bp, n_alloc, col);
568 Put all nodes which live through the constrained instruction also to the
569 allocation bipartite graph. They are considered unconstrained.
572 foreach_out_edge(perm, edge) {
573 ir_node *proj = get_edge_src_irn(edge);
575 assert(is_Proj(proj));
577 if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
578 assert(n_alloc < n_regs);
579 alloc_nodes[n_alloc] = proj;
580 pmap_insert(partners, proj, NULL);
582 bitset_clear_all(bs);
583 arch_put_non_ignore_regs(aenv, env->cls, bs);
584 bitset_andnot(bs, env->ignore_colors);
585 bitset_foreach(bs, col)
586 hungarian_add(bp, n_alloc, col, 1);
587 // bipartite_add(bp, n_alloc, col);
594 /* Compute a valid register allocation. */
595 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
596 match_res = hungarian_solve(bp, assignment, &cost, 1);
597 assert(match_res == 0 && "matching failed");
598 //bipartite_matching(bp, assignment);
600 /* Assign colors obtained from the matching. */
601 for(i = 0; i < n_alloc; ++i) {
602 const arch_register_t *reg;
606 assert(assignment[i] >= 0 && "there must have been a register assigned");
607 reg = arch_register_for_index(env->cls, assignment[i]);
609 nodes[0] = alloc_nodes[i];
610 nodes[1] = pmap_get(partners, alloc_nodes[i]);
612 for(j = 0; j < 2; ++j) {
616 arch_set_irn_register(aenv, nodes[j], reg);
617 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
618 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
623 /* Allocate the non-constrained Projs of the Perm. */
626 bitset_clear_all(bs);
628 /* Put the colors of all Projs in a bitset. */
629 foreach_out_edge(perm, edge) {
630 ir_node *proj = get_edge_src_irn(edge);
631 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
634 bitset_set(bs, reg->index);
637 /* Assign the not yet assigned Projs of the Perm a suitable color. */
638 foreach_out_edge(perm, edge) {
639 ir_node *proj = get_edge_src_irn(edge);
640 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
642 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
645 col = get_next_free_reg(alloc_env, bs);
646 reg = arch_register_for_index(env->cls, col);
647 bitset_set(bs, reg->index);
648 arch_set_irn_register(aenv, proj, reg);
649 pset_insert_ptr(alloc_env->pre_colored, proj);
650 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
655 //bipartite_free(bp);
657 pmap_destroy(partners);
661 obstack_free(&env->obst, base);
666 * Handle constraint nodes in each basic block.
667 * handle_constraints() inserts Perm nodes which perm
668 * over all values live at the constrained node right in front
669 * of the constrained node. These Perms signal a constrained node.
670 * For further comments, refer to handle_constraints().
672 static void constraints(ir_node *bl, void *data)
674 be_chordal_alloc_env_t *env = data;
677 Start silent in the start block.
678 The silence remains until the first barrier is seen.
679 Each other block is begun loud.
681 int silent = bl == get_irg_start_block(get_irn_irg(bl));
685 If the block is the start block search the barrier and
686 start handling constraints from there.
689 for(irn = sched_first(bl); !sched_is_end(irn);) {
690 irn = handle_constraints(env, irn, &silent);
695 * Annotate the register pressure to the nodes and compute
696 * the liveness intervals.
697 * @param block The block to do it for.
698 * @param env_ptr The environment.
700 static void pressure(ir_node *block, void *env_ptr)
702 /* Convenience macro for a def */
703 #define border_def(irn, step, real) \
704 border_add(env, head, irn, step, pressure--, 1, real)
706 /* Convenience macro for a use */
707 #define border_use(irn, step, real) \
708 border_add(env, head, irn, step, ++pressure, 0, real)
710 be_chordal_alloc_env_t *alloc_env = env_ptr;
711 be_chordal_env_t *env = alloc_env->chordal_env;
712 bitset_t *live = alloc_env->live;
714 be_lv_t *lv = env->birg->lv;
715 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
719 unsigned pressure = 0;
720 struct list_head *head;
721 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
722 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
724 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
725 bitset_clear_all(live);
727 /* Set up the border list in the block info */
728 head = obstack_alloc(&env->obst, sizeof(*head));
729 INIT_LIST_HEAD(head);
730 assert(pmap_get(env->border_heads, block) == NULL);
731 pmap_insert(env->border_heads, block, head);
734 * Make final uses of all values live out of the block.
735 * They are necessary to build up real intervals.
737 foreach_pset(live_end, irn) {
738 if(has_reg_class(env, irn)) {
739 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
740 bitset_set(live, get_irn_idx(irn));
741 border_use(irn, step, 0);
747 * Determine the last uses of a value inside the block, since they are
748 * relevant for the interval borders.
750 sched_foreach_reverse(block, irn) {
751 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
752 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
755 * If the node defines some value, which can put into a
756 * register of the current class, make a border for it.
758 if(has_reg_class(env, irn)) {
759 int nr = get_irn_idx(irn);
761 bitset_clear(live, nr);
762 border_def(irn, step, 1);
766 * If the node is no phi node we can examine the uses.
769 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
770 ir_node *op = get_irn_n(irn, i);
772 if(has_reg_class(env, op)) {
773 int nr = get_irn_idx(op);
774 const char *msg = "-";
776 if(!bitset_is_set(live, nr)) {
777 border_use(op, step, 1);
778 bitset_set(live, nr);
782 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
790 * Add initial defs for all values live in.
792 foreach_pset(live_in, irn) {
793 if(has_reg_class(env, irn)) {
795 /* Mark the value live in. */
796 bitset_set(live, get_irn_idx(irn));
799 border_def(irn, step, 0);
807 static void assign(ir_node *block, void *env_ptr)
809 be_chordal_alloc_env_t *alloc_env = env_ptr;
810 be_chordal_env_t *env = alloc_env->chordal_env;
811 bitset_t *live = alloc_env->live;
812 bitset_t *colors = alloc_env->colors;
813 bitset_t *in_colors = alloc_env->in_colors;
814 const arch_env_t *arch_env = env->birg->main_env->arch_env;
815 struct list_head *head = get_block_border_head(env, block);
816 be_lv_t *lv = env->birg->lv;
817 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
821 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
823 bitset_clear_all(colors);
824 bitset_clear_all(live);
825 bitset_clear_all(in_colors);
827 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
828 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
829 list_for_each_entry(border_t, b, head, list) {
830 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
831 b->irn, get_irn_idx(b->irn)));
835 * Add initial defs for all values live in.
836 * Since their colors have already been assigned (The dominators were
837 * allocated before), we have to mark their colors as used also.
839 foreach_pset(live_in, irn) {
840 if(has_reg_class(env, irn)) {
841 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
844 assert(reg && "Node must have been assigned a register");
845 col = arch_register_get_index(reg);
847 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
849 /* Mark the color of the live in value as used. */
850 bitset_set(colors, col);
851 bitset_set(in_colors, col);
853 /* Mark the value live in. */
854 bitset_set(live, get_irn_idx(irn));
859 * Mind that the sequence of defs from back to front defines a perfect
860 * elimination order. So, coloring the definitions from first to last
863 list_for_each_entry_reverse(border_t, b, head, list) {
864 ir_node *irn = b->irn;
865 int nr = get_irn_idx(irn);
866 int ignore = arch_irn_is(arch_env, irn, ignore);
869 * Assign a color, if it is a local def. Global defs already have a
872 if(b->is_def && !be_is_live_in(lv, block, irn)) {
873 const arch_register_t *reg;
876 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
877 reg = arch_get_irn_register(arch_env, irn);
879 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
883 col = get_next_free_reg(alloc_env, colors);
884 reg = arch_register_for_index(env->cls, col);
885 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
886 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
889 bitset_set(colors, col);
890 arch_set_irn_register(arch_env, irn, reg);
892 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
894 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
895 bitset_set(live, nr);
898 /* Clear the color upon a use. */
899 else if(!b->is_def) {
900 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
903 assert(reg && "Register must have been assigned");
905 col = arch_register_get_index(reg);
906 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
908 bitset_clear(colors, col);
909 bitset_clear(live, nr);
916 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
918 be_chordal_alloc_env_t env;
920 be_irg_t *birg = chordal_env->birg;
922 int colors_n = arch_register_class_n_regs(chordal_env->cls);
923 ir_graph *irg = chordal_env->irg;
926 be_assure_dom_front(birg);
927 be_assure_liveness(birg);
930 env.chordal_env = chordal_env;
931 env.colors_n = colors_n;
932 env.colors = bitset_alloca(colors_n);
933 env.tmp_colors = bitset_alloca(colors_n);
934 env.in_colors = bitset_alloca(colors_n);
935 env.pre_colored = pset_new_ptr_default();
936 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
939 /* Handle register targeting constraints */
940 dom_tree_walk_irg(irg, constraints, NULL, &env);
942 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
943 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
944 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
947 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
949 /* First, determine the pressure */
950 dom_tree_walk_irg(irg, pressure, NULL, &env);
952 /* Assign the colors */
953 dom_tree_walk_irg(irg, assign, NULL, &env);
955 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
957 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
958 plotter = new_plotter_ps(buf);
959 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
960 plotter_free(plotter);
963 bitset_free(env.live);
964 del_pset(env.pre_colored);