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"
54 #include "bechordal_t.h"
55 #include "bechordal_draw.h"
57 #define DBG_LEVEL SET_LEVEL_0
58 #define DBG_LEVEL_CHECK SET_LEVEL_0
62 #define DUMP_INTERVALS
64 typedef struct _be_chordal_alloc_env_t {
65 be_chordal_env_t *chordal_env;
67 pset *pre_colored; /**< Set of precolored nodes. */
68 bitset_t *live; /**< A liveness bitset. */
69 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
70 bitset_t *colors; /**< The color mask. */
71 bitset_t *in_colors; /**< Colors used by live in values. */
72 int colors_n; /**< The number of colors. */
73 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
74 } be_chordal_alloc_env_t;
78 /* Make a fourcc for border checking. */
79 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
82 static void check_border_list(struct list_head *head)
85 list_for_each_entry(border_t, x, head, list) {
86 assert(x->magic == BORDER_FOURCC);
90 static void check_heads(be_chordal_env_t *env)
93 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
94 /* ir_printf("checking border list of block %+F\n", ent->key); */
95 check_border_list(ent->value);
101 * Add an interval border to the list of a block's list
102 * of interval border.
103 * @note You always have to create the use before the def.
104 * @param env The environment.
105 * @param head The list head to enqueue the borders.
106 * @param irn The node (value) the border belongs to.
107 * @param pressure The pressure at this point in time.
108 * @param step A time step for the border.
109 * @param is_def Is the border a use or a def.
110 * @return The created border.
112 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
113 ir_node *irn, unsigned step, unsigned pressure,
114 unsigned is_def, unsigned is_real)
121 b = obstack_alloc(&env->obst, sizeof(*b));
123 /* also allocate the def and tie it to the use. */
124 def = obstack_alloc(&env->obst, sizeof(*def));
125 memset(def, 0, sizeof(*def));
130 * Set the link field of the irn to the def.
131 * This strongly relies on the fact, that the use is always
132 * made before the def.
134 set_irn_link(irn, def);
136 b->magic = BORDER_FOURCC;
137 def->magic = BORDER_FOURCC;
141 * If the def is encountered, the use was made and so was the
142 * the def node (see the code above). It was placed into the
143 * link field of the irn, so we can get it there.
146 b = get_irn_link(irn);
148 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
151 b->pressure = pressure;
153 b->is_real = is_real;
156 list_add_tail(&b->list, head);
157 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
164 * Check, if an irn is of the register class currently under processing.
165 * @param env The chordal environment.
166 * @param irn The node.
167 * @return 1, if the node is of that register class, 0 if not.
169 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
171 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
172 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
175 #define has_limited_constr(req, irn) \
176 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
178 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
180 bitset_t *tmp = alloc_env->tmp_colors;
181 bitset_copy(tmp, colors);
182 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
183 return bitset_next_clear(tmp, 0);
186 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
191 bitset_copy(bs, o2->regs);
196 bitset_copy(bs, o1->regs);
200 assert(o1->req.cls == o2->req.cls);
202 if(bitset_contains(o1->regs, o2->regs))
203 bitset_copy(bs, o1->regs);
204 else if(bitset_contains(o2->regs, o1->regs))
205 bitset_copy(bs, o2->regs);
212 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
216 ie.ignore_colors = env->ignore_colors;
217 ie.aenv = env->birg->main_env->arch_env;
218 ie.obst = &env->obst;
220 return be_scan_insn(&ie, irn);
223 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
225 const arch_env_t *aenv = env->birg->main_env->arch_env;
226 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
227 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
228 ir_node *bl = get_nodes_block(irn);
229 be_lv_t *lv = env->birg->lv;
234 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
235 ir_node *op = get_irn_n(irn, i);
237 const arch_register_t *reg;
238 arch_register_req_t req;
240 if (arch_get_irn_reg_class(aenv, irn, i) == env->cls) {
241 reg = arch_get_irn_register(aenv, op);
243 if (reg && arch_register_type_is(reg, ignore)) {
244 arch_get_register_req(aenv, &req, irn, i);
246 if (arch_register_req_is(&req, limited)) {
247 bitset_clear_all(tmp);
248 req.limited(req.limited_env, tmp);
250 if (! bitset_is_set(tmp, reg->index)) {
251 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
252 be_stat_ev("constr_copy", 1);
254 sched_add_before(irn, copy);
255 set_irn_n(irn, i, copy);
256 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
263 insn = chordal_scan_insn(env, irn);
265 if(!insn->has_constraints)
268 /* insert copies for nodes that occur constrained more than once. */
269 for(i = insn->use_start; i < insn->n_ops; ++i) {
270 be_operand_t *op = &insn->ops[i];
272 if(op->has_constraints) {
273 for(j = i + 1; j < insn->n_ops; ++j) {
274 be_operand_t *a_op = &insn->ops[j];
276 if(a_op->carrier == op->carrier && a_op->has_constraints) {
277 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
278 be_stat_ev("constr_copy", 1);
280 sched_add_before(insn->irn, copy);
281 set_irn_n(insn->irn, a_op->pos, copy);
282 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
288 /* collect all registers occuring in out constraints. */
289 for(i = 0; i < insn->use_start; ++i) {
290 be_operand_t *op = &insn->ops[i];
291 if(op->has_constraints)
292 bitset_or(def_constr, op->regs);
296 insert copies for all constrained arguments living through the node
297 and being constrained to a register which also occurs in out constraints.
299 for(i = insn->use_start; i < insn->n_ops; ++i) {
300 be_operand_t *op = &insn->ops[i];
302 bitset_copy(tmp, op->regs);
303 bitset_and(tmp, def_constr);
307 1) the operand is constrained.
308 2) lives through the node.
309 3) is constrained to a register occuring in out constraints.
311 if(op->has_constraints && values_interfere(lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
313 only create the copy if the operand is no copy.
314 this is necessary since the assure constraints phase inserts
315 Copies and Keeps for operands which must be different from the results.
316 Additional copies here would destroy this.
318 if(!be_is_Copy(op->carrier)) {
319 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
321 sched_add_before(insn->irn, copy);
322 set_irn_n(insn->irn, op->pos, copy);
323 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
324 be_liveness_update(lv, op->carrier);
330 obstack_free(&env->obst, insn);
331 return insn->next_insn;
334 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
336 be_chordal_env_t *env = data;
338 for(irn = sched_first(bl); !sched_is_end(irn);) {
339 irn = prepare_constr_insn(env, irn);
343 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
344 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
347 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
349 const be_chordal_env_t *env = alloc_env->chordal_env;
351 int n_uses = be_insn_n_uses(insn);
352 int n_defs = be_insn_n_defs(insn);
353 bitset_t *bs = bitset_alloca(env->cls->n_regs);
354 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
355 be_lv_t *lv = env->birg->lv;
360 For each out operand, try to find an in operand which can be assigned the
361 same register as the out operand.
363 for (j = 0; j < insn->use_start; ++j) {
365 int smallest_n_regs = 2 * env->cls->n_regs + 1;
366 be_operand_t *out_op = &insn->ops[j];
368 /* Try to find an in operand which has ... */
369 for(i = insn->use_start; i < insn->n_ops; ++i) {
371 const be_operand_t *op = &insn->ops[i];
373 if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
374 bitset_clear_all(bs);
375 bitset_copy(bs, op->regs);
376 bitset_and(bs, out_op->regs);
377 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
379 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
381 smallest_n_regs = n_total;
387 be_operand_t *partner = &insn->ops[smallest];
388 out_op->partner = partner;
389 partner->partner = out_op;
395 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
397 be_chordal_env_t *env = alloc_env->chordal_env;
398 const arch_env_t *aenv = env->birg->main_env->arch_env;
399 be_insn_t *insn = *the_insn;
400 ir_node *bl = get_nodes_block(insn->irn);
401 ir_node *copy = NULL;
402 ir_node *perm = NULL;
403 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
404 bitset_t *bs = bitset_alloca(env->cls->n_regs);
405 be_lv_t *lv = env->birg->lv;
406 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
410 assert(insn->has_constraints && "only do this for constrained nodes");
413 Collect all registers that occur in output constraints.
414 This is necessary, since if the insn has one of these as an input constraint
415 and the corresponding operand interferes with the insn, the operand must
418 for(i = 0; i < insn->use_start; ++i) {
419 be_operand_t *op = &insn->ops[i];
420 if(op->has_constraints)
421 bitset_or(out_constr, op->regs);
427 DEBUG_ONLY((void) dbg;)
430 Make the Perm, recompute liveness and re-scan the insn since the
431 in operands are now the Projs of the Perm.
433 perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
435 /* Registers are propagated by insert_Perm_after(). Clean them here! */
437 const ir_edge_t *edge;
439 be_stat_ev("constr_perm", get_irn_arity(perm));
440 foreach_out_edge(perm, edge) {
441 ir_node *proj = get_edge_src_irn(edge);
442 arch_set_irn_register(aenv, proj, NULL);
446 We also have to re-build the insn since the input operands are now the Projs of
447 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
448 the live sets may change.
450 // be_liveness_recompute(lv);
451 obstack_free(&env->obst, insn);
452 *the_insn = insn = chordal_scan_insn(env, insn->irn);
455 Copy the input constraints of the insn to the Perm as output
456 constraints. Succeeding phases (coalescing will need that).
458 for(i = insn->use_start; i < insn->n_ops; ++i) {
459 be_operand_t *op = &insn->ops[i];
460 ir_node *proj = op->carrier;
462 Note that the predecessor must not be a Proj of the Perm,
463 since ignore-nodes are not Perm'ed.
465 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
466 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
474 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
476 be_chordal_env_t *env = alloc_env->chordal_env;
477 void *base = obstack_base(&env->obst);
478 be_insn_t *insn = chordal_scan_insn(env, irn);
479 ir_node *res = insn->next_insn;
480 int be_silent = *silent;
481 be_lv_t *lv = env->birg->lv;
483 if(insn->pre_colored) {
485 for(i = 0; i < insn->use_start; ++i)
486 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
490 If the current node is a barrier toggle the silent flag.
491 If we are in the start block, we are ought to be silent at the beginning,
492 so the toggling activates the constraint handling but skips the barrier.
493 If we are in the end block we handle the in requirements of the barrier
494 and set the rest to silent.
496 if(be_is_Barrier(irn))
503 Perms inserted before the constraint handling phase are considered to be
504 correctly precolored. These Perms arise during the ABI handling phase.
506 if(insn->has_constraints) {
507 const arch_env_t *aenv = env->birg->main_env->arch_env;
508 int n_regs = env->cls->n_regs;
509 bitset_t *bs = bitset_alloca(n_regs);
510 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
511 hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
512 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
513 int *assignment = alloca(n_regs * sizeof(assignment[0]));
514 pmap *partners = pmap_create();
515 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
519 const ir_edge_t *edge;
520 ir_node *perm = NULL;
524 prepare the constraint handling of this node.
525 Perms are constructed and Copies are created for constrained values
526 interfering with the instruction.
528 perm = pre_process_constraints(alloc_env, &insn);
530 /* find suitable in operands to the out operands of the node. */
531 pair_up_operands(alloc_env, insn);
534 look at the in/out operands and add each operand (and its possible partner)
535 to a bipartite graph (left: nodes with partners, right: admissible colors).
537 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
538 be_operand_t *op = &insn->ops[i];
541 If the operand has no partner or the partner has not been marked
542 for allocation, determine the admissible registers and mark it
543 for allocation by associating the node and its partner with the
544 set of admissible registers via a bipartite graph.
546 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
548 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
549 alloc_nodes[n_alloc] = op->carrier;
551 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
553 bitset_clear_all(bs);
554 get_decisive_partner_regs(bs, op, op->partner);
556 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
558 bitset_foreach(bs, col)
559 hungarian_add(bp, n_alloc, col, 1);
560 // bipartite_add(bp, n_alloc, col);
567 Put all nodes which live through the constrained instruction also to the
568 allocation bipartite graph. They are considered unconstrained.
571 foreach_out_edge(perm, edge) {
572 ir_node *proj = get_edge_src_irn(edge);
574 assert(is_Proj(proj));
576 if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
577 assert(n_alloc < n_regs);
578 alloc_nodes[n_alloc] = proj;
579 pmap_insert(partners, proj, NULL);
581 bitset_clear_all(bs);
582 arch_put_non_ignore_regs(aenv, env->cls, bs);
583 bitset_andnot(bs, env->ignore_colors);
584 bitset_foreach(bs, col)
585 hungarian_add(bp, n_alloc, col, 1);
586 // bipartite_add(bp, n_alloc, col);
593 /* Compute a valid register allocation. */
594 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
595 match_res = hungarian_solve(bp, assignment, &cost, 1);
596 assert(match_res == 0 && "matching failed");
597 //bipartite_matching(bp, assignment);
599 /* Assign colors obtained from the matching. */
600 for(i = 0; i < n_alloc; ++i) {
601 const arch_register_t *reg;
605 assert(assignment[i] >= 0 && "there must have been a register assigned");
606 reg = arch_register_for_index(env->cls, assignment[i]);
608 nodes[0] = alloc_nodes[i];
609 nodes[1] = pmap_get(partners, alloc_nodes[i]);
611 for(j = 0; j < 2; ++j) {
615 arch_set_irn_register(aenv, nodes[j], reg);
616 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
617 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
622 /* Allocate the non-constrained Projs of the Perm. */
625 bitset_clear_all(bs);
627 /* Put the colors of all Projs in a bitset. */
628 foreach_out_edge(perm, edge) {
629 ir_node *proj = get_edge_src_irn(edge);
630 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
633 bitset_set(bs, reg->index);
636 /* Assign the not yet assigned Projs of the Perm a suitable color. */
637 foreach_out_edge(perm, edge) {
638 ir_node *proj = get_edge_src_irn(edge);
639 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
641 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
644 col = get_next_free_reg(alloc_env, bs);
645 reg = arch_register_for_index(env->cls, col);
646 bitset_set(bs, reg->index);
647 arch_set_irn_register(aenv, proj, reg);
648 pset_insert_ptr(alloc_env->pre_colored, proj);
649 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
654 //bipartite_free(bp);
656 pmap_destroy(partners);
660 obstack_free(&env->obst, base);
665 * Handle constraint nodes in each basic block.
666 * handle_constraints() inserts Perm nodes which perm
667 * over all values live at the constrained node right in front
668 * of the constrained node. These Perms signal a constrained node.
669 * For further comments, refer to handle_constraints().
671 static void constraints(ir_node *bl, void *data)
673 be_chordal_alloc_env_t *env = data;
676 Start silent in the start block.
677 The silence remains until the first barrier is seen.
678 Each other block is begun loud.
680 int silent = bl == get_irg_start_block(get_irn_irg(bl));
684 If the block is the start block search the barrier and
685 start handling constraints from there.
688 for(irn = sched_first(bl); !sched_is_end(irn);) {
689 irn = handle_constraints(env, irn, &silent);
694 * Annotate the register pressure to the nodes and compute
695 * the liveness intervals.
696 * @param block The block to do it for.
697 * @param env_ptr The environment.
699 static void pressure(ir_node *block, void *env_ptr)
701 /* Convenience macro for a def */
702 #define border_def(irn, step, real) \
703 border_add(env, head, irn, step, pressure--, 1, real)
705 /* Convenience macro for a use */
706 #define border_use(irn, step, real) \
707 border_add(env, head, irn, step, ++pressure, 0, real)
709 be_chordal_alloc_env_t *alloc_env = env_ptr;
710 be_chordal_env_t *env = alloc_env->chordal_env;
711 bitset_t *live = alloc_env->live;
713 be_lv_t *lv = env->birg->lv;
714 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
718 unsigned pressure = 0;
719 struct list_head *head;
720 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
721 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
723 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
724 bitset_clear_all(live);
726 /* Set up the border list in the block info */
727 head = obstack_alloc(&env->obst, sizeof(*head));
728 INIT_LIST_HEAD(head);
729 assert(pmap_get(env->border_heads, block) == NULL);
730 pmap_insert(env->border_heads, block, head);
733 * Make final uses of all values live out of the block.
734 * They are necessary to build up real intervals.
736 foreach_pset(live_end, irn) {
737 if(has_reg_class(env, irn)) {
738 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
739 bitset_set(live, get_irn_idx(irn));
740 border_use(irn, step, 0);
746 * Determine the last uses of a value inside the block, since they are
747 * relevant for the interval borders.
749 sched_foreach_reverse(block, irn) {
750 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
751 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
754 * If the node defines some value, which can put into a
755 * register of the current class, make a border for it.
757 if(has_reg_class(env, irn)) {
758 int nr = get_irn_idx(irn);
760 bitset_clear(live, nr);
761 border_def(irn, step, 1);
765 * If the node is no phi node we can examine the uses.
768 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
769 ir_node *op = get_irn_n(irn, i);
771 if(has_reg_class(env, op)) {
772 int nr = get_irn_idx(op);
773 const char *msg = "-";
775 if(!bitset_is_set(live, nr)) {
776 border_use(op, step, 1);
777 bitset_set(live, nr);
781 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
789 * Add initial defs for all values live in.
791 foreach_pset(live_in, irn) {
792 if(has_reg_class(env, irn)) {
794 /* Mark the value live in. */
795 bitset_set(live, get_irn_idx(irn));
798 border_def(irn, step, 0);
806 static void assign(ir_node *block, void *env_ptr)
808 be_chordal_alloc_env_t *alloc_env = env_ptr;
809 be_chordal_env_t *env = alloc_env->chordal_env;
810 bitset_t *live = alloc_env->live;
811 bitset_t *colors = alloc_env->colors;
812 bitset_t *in_colors = alloc_env->in_colors;
813 const arch_env_t *arch_env = env->birg->main_env->arch_env;
814 struct list_head *head = get_block_border_head(env, block);
815 be_lv_t *lv = env->birg->lv;
816 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
820 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
822 bitset_clear_all(colors);
823 bitset_clear_all(live);
824 bitset_clear_all(in_colors);
826 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
827 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
828 list_for_each_entry(border_t, b, head, list) {
829 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
830 b->irn, get_irn_idx(b->irn)));
834 * Add initial defs for all values live in.
835 * Since their colors have already been assigned (The dominators were
836 * allocated before), we have to mark their colors as used also.
838 foreach_pset(live_in, irn) {
839 if(has_reg_class(env, irn)) {
840 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
843 assert(reg && "Node must have been assigned a register");
844 col = arch_register_get_index(reg);
846 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
848 /* Mark the color of the live in value as used. */
849 bitset_set(colors, col);
850 bitset_set(in_colors, col);
852 /* Mark the value live in. */
853 bitset_set(live, get_irn_idx(irn));
858 * Mind that the sequence
859 * 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);