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"
46 #include "besched_t.h"
53 #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 b->magic = BORDER_FOURCC;
138 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);
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(env->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(env->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]));
359 For each out operand, try to find an in operand which can be assigned the
360 same register as the out operand.
362 for (j = 0; j < insn->use_start; ++j) {
364 int smallest_n_regs = 2 * env->cls->n_regs + 1;
365 be_operand_t *out_op = &insn->ops[j];
367 /* Try to find an in operand which has ... */
368 for(i = insn->use_start; i < insn->n_ops; ++i) {
370 const be_operand_t *op = &insn->ops[i];
372 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
373 bitset_clear_all(bs);
374 bitset_copy(bs, op->regs);
375 bitset_and(bs, out_op->regs);
376 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
378 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
380 smallest_n_regs = n_total;
386 be_operand_t *partner = &insn->ops[smallest];
387 out_op->partner = partner;
388 partner->partner = out_op;
394 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
396 be_chordal_env_t *env = alloc_env->chordal_env;
397 const arch_env_t *aenv = env->birg->main_env->arch_env;
398 be_insn_t *insn = *the_insn;
399 ir_node *bl = get_nodes_block(insn->irn);
400 ir_node *copy = NULL;
401 ir_node *perm = NULL;
402 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
403 bitset_t *bs = bitset_alloca(env->cls->n_regs);
404 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
408 assert(insn->has_constraints && "only do this for constrained nodes");
411 Collect all registers that occur in output constraints.
412 This is necessary, since if the insn has one of these as an input constraint
413 and the corresponding operand interferes with the insn, the operand must
416 for(i = 0; i < insn->use_start; ++i) {
417 be_operand_t *op = &insn->ops[i];
418 if(op->has_constraints)
419 bitset_or(out_constr, op->regs);
425 DEBUG_ONLY((void) dbg;)
428 Make the Perm, recompute liveness and re-scan the insn since the
429 in operands are now the Projs of the Perm.
431 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
433 /* Registers are propagated by insert_Perm_after(). Clean them here! */
435 const ir_edge_t *edge;
437 be_stat_ev("constr_perm", get_irn_arity(perm));
438 foreach_out_edge(perm, edge) {
439 ir_node *proj = get_edge_src_irn(edge);
440 arch_set_irn_register(aenv, proj, NULL);
444 We also have to re-build the insn since the input operands are now the Projs of
445 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
446 the live sets may change.
448 // be_liveness_recompute(env->lv);
449 obstack_free(&env->obst, insn);
450 *the_insn = insn = chordal_scan_insn(env, insn->irn);
453 Copy the input constraints of the insn to the Perm as output
454 constraints. Succeeding phases (coalescing will need that).
456 for(i = insn->use_start; i < insn->n_ops; ++i) {
457 be_operand_t *op = &insn->ops[i];
458 ir_node *proj = op->carrier;
460 Note that the predecessor must not be a Proj of the Perm,
461 since ignore-nodes are not Perm'ed.
463 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
464 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
472 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
474 be_chordal_env_t *env = alloc_env->chordal_env;
475 void *base = obstack_base(&env->obst);
476 be_insn_t *insn = chordal_scan_insn(env, irn);
477 ir_node *res = insn->next_insn;
478 int be_silent = *silent;
480 if(insn->pre_colored) {
482 for(i = 0; i < insn->use_start; ++i)
483 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
487 If the current node is a barrier toggle the silent flag.
488 If we are in the start block, we are ought to be silent at the beginning,
489 so the toggling activates the constraint handling but skips the barrier.
490 If we are in the end block we handle the in requirements of the barrier
491 and set the rest to silent.
493 if(be_is_Barrier(irn))
500 Perms inserted before the constraint handling phase are considered to be
501 correctly precolored. These Perms arise during the ABI handling phase.
503 if(insn->has_constraints) {
504 const arch_env_t *aenv = env->birg->main_env->arch_env;
505 int n_regs = env->cls->n_regs;
506 bitset_t *bs = bitset_alloca(n_regs);
507 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
508 hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
509 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
510 int *assignment = alloca(n_regs * sizeof(assignment[0]));
511 pmap *partners = pmap_create();
512 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
516 const ir_edge_t *edge;
517 ir_node *perm = NULL;
521 prepare the constraint handling of this node.
522 Perms are constructed and Copies are created for constrained values
523 interfering with the instruction.
525 perm = pre_process_constraints(alloc_env, &insn);
527 /* find suitable in operands to the out operands of the node. */
528 pair_up_operands(alloc_env, insn);
531 look at the in/out operands and add each operand (and its possible partner)
532 to a bipartite graph (left: nodes with partners, right: admissible colors).
534 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
535 be_operand_t *op = &insn->ops[i];
538 If the operand has no partner or the partner has not been marked
539 for allocation, determine the admissible registers and mark it
540 for allocation by associating the node and its partner with the
541 set of admissible registers via a bipartite graph.
543 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
545 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
546 alloc_nodes[n_alloc] = op->carrier;
548 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
550 bitset_clear_all(bs);
551 get_decisive_partner_regs(bs, op, op->partner);
553 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
555 bitset_foreach(bs, col)
556 hungarian_add(bp, n_alloc, col, 1);
557 // bipartite_add(bp, n_alloc, col);
564 Put all nodes which live through the constrained instruction also to the
565 allocation bipartite graph. They are considered unconstrained.
568 foreach_out_edge(perm, edge) {
569 ir_node *proj = get_edge_src_irn(edge);
571 assert(is_Proj(proj));
573 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
574 assert(n_alloc < n_regs);
575 alloc_nodes[n_alloc] = proj;
576 pmap_insert(partners, proj, NULL);
578 bitset_clear_all(bs);
579 arch_put_non_ignore_regs(aenv, env->cls, bs);
580 bitset_andnot(bs, env->ignore_colors);
581 bitset_foreach(bs, col)
582 hungarian_add(bp, n_alloc, col, 1);
583 // bipartite_add(bp, n_alloc, col);
590 /* Compute a valid register allocation. */
591 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
592 match_res = hungarian_solve(bp, assignment, &cost, 1);
593 assert(match_res == 0 && "matching failed");
594 //bipartite_matching(bp, assignment);
596 /* Assign colors obtained from the matching. */
597 for(i = 0; i < n_alloc; ++i) {
598 const arch_register_t *reg;
602 assert(assignment[i] >= 0 && "there must have been a register assigned");
603 reg = arch_register_for_index(env->cls, assignment[i]);
605 nodes[0] = alloc_nodes[i];
606 nodes[1] = pmap_get(partners, alloc_nodes[i]);
608 for(j = 0; j < 2; ++j) {
612 arch_set_irn_register(aenv, nodes[j], reg);
613 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
614 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
619 /* Allocate the non-constrained Projs of the Perm. */
622 bitset_clear_all(bs);
624 /* Put the colors of all Projs in a bitset. */
625 foreach_out_edge(perm, edge) {
626 ir_node *proj = get_edge_src_irn(edge);
627 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
630 bitset_set(bs, reg->index);
633 /* Assign the not yet assigned Projs of the Perm a suitable color. */
634 foreach_out_edge(perm, edge) {
635 ir_node *proj = get_edge_src_irn(edge);
636 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
638 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
641 col = get_next_free_reg(alloc_env, bs);
642 reg = arch_register_for_index(env->cls, col);
643 bitset_set(bs, reg->index);
644 arch_set_irn_register(aenv, proj, reg);
645 pset_insert_ptr(alloc_env->pre_colored, proj);
646 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
651 //bipartite_free(bp);
653 pmap_destroy(partners);
657 obstack_free(&env->obst, base);
662 * Handle constraint nodes in each basic block.
663 * handle_constraints() inserts Perm nodes which perm
664 * over all values live at the constrained node right in front
665 * of the constrained node. These Perms signal a constrained node.
666 * For further comments, refer to handle_constraints().
668 static void constraints(ir_node *bl, void *data)
670 be_chordal_alloc_env_t *env = data;
673 Start silent in the start block.
674 The silence remains until the first barrier is seen.
675 Each other block is begun loud.
677 int silent = bl == get_irg_start_block(get_irn_irg(bl));
681 If the block is the start block search the barrier and
682 start handling constraints from there.
685 for(irn = sched_first(bl); !sched_is_end(irn);) {
686 irn = handle_constraints(env, irn, &silent);
691 * Annotate the register pressure to the nodes and compute
692 * the liveness intervals.
693 * @param block The block to do it for.
694 * @param env_ptr The environment.
696 static void pressure(ir_node *block, void *env_ptr)
698 /* Convenience macro for a def */
699 #define border_def(irn, step, real) \
700 border_add(env, head, irn, step, pressure--, 1, real)
702 /* Convenience macro for a use */
703 #define border_use(irn, step, real) \
704 border_add(env, head, irn, step, ++pressure, 0, real)
706 be_chordal_alloc_env_t *alloc_env = env_ptr;
707 be_chordal_env_t *env = alloc_env->chordal_env;
708 bitset_t *live = alloc_env->live;
710 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
714 unsigned pressure = 0;
715 struct list_head *head;
716 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
717 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
719 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
720 bitset_clear_all(live);
722 /* Set up the border list in the block info */
723 head = obstack_alloc(&env->obst, sizeof(*head));
724 INIT_LIST_HEAD(head);
725 assert(pmap_get(env->border_heads, block) == NULL);
726 pmap_insert(env->border_heads, block, head);
729 * Make final uses of all values live out of the block.
730 * They are necessary to build up real intervals.
732 foreach_pset(live_end, irn) {
733 if(has_reg_class(env, irn)) {
734 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
735 bitset_set(live, get_irn_idx(irn));
736 border_use(irn, step, 0);
742 * Determine the last uses of a value inside the block, since they are
743 * relevant for the interval borders.
745 sched_foreach_reverse(block, irn) {
746 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
747 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
750 * If the node defines some value, which can put into a
751 * register of the current class, make a border for it.
753 if(has_reg_class(env, irn)) {
754 int nr = get_irn_idx(irn);
756 bitset_clear(live, nr);
757 border_def(irn, step, 1);
761 * If the node is no phi node we can examine the uses.
764 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
765 ir_node *op = get_irn_n(irn, i);
767 if(has_reg_class(env, op)) {
768 int nr = get_irn_idx(op);
769 const char *msg = "-";
771 if(!bitset_is_set(live, nr)) {
772 border_use(op, step, 1);
773 bitset_set(live, nr);
777 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
785 * Add initial defs for all values live in.
787 foreach_pset(live_in, irn) {
788 if(has_reg_class(env, irn)) {
790 /* Mark the value live in. */
791 bitset_set(live, get_irn_idx(irn));
794 border_def(irn, step, 0);
802 static void assign(ir_node *block, void *env_ptr)
804 be_chordal_alloc_env_t *alloc_env = env_ptr;
805 be_chordal_env_t *env = alloc_env->chordal_env;
806 bitset_t *live = alloc_env->live;
807 bitset_t *colors = alloc_env->colors;
808 bitset_t *in_colors = alloc_env->in_colors;
809 const arch_env_t *arch_env = env->birg->main_env->arch_env;
810 struct list_head *head = get_block_border_head(env, block);
811 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
815 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
817 bitset_clear_all(colors);
818 bitset_clear_all(live);
819 bitset_clear_all(in_colors);
821 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
822 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
823 list_for_each_entry(border_t, b, head, list) {
824 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
825 b->irn, get_irn_idx(b->irn)));
829 * Add initial defs for all values live in.
830 * Since their colors have already been assigned (The dominators were
831 * allocated before), we have to mark their colors as used also.
833 foreach_pset(live_in, irn) {
834 if(has_reg_class(env, irn)) {
835 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
838 assert(reg && "Node must have been assigned a register");
839 col = arch_register_get_index(reg);
841 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
843 /* Mark the color of the live in value as used. */
844 bitset_set(colors, col);
845 bitset_set(in_colors, col);
847 /* Mark the value live in. */
848 bitset_set(live, get_irn_idx(irn));
853 * Mind that the sequence
854 * of defs from back to front defines a perfect
855 * elimination order. So, coloring the definitions from first to last
858 list_for_each_entry_reverse(border_t, b, head, list) {
859 ir_node *irn = b->irn;
860 int nr = get_irn_idx(irn);
861 int ignore = arch_irn_is(arch_env, irn, ignore);
864 * Assign a color, if it is a local def. Global defs already have a
867 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
868 const arch_register_t *reg;
871 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
872 reg = arch_get_irn_register(arch_env, irn);
874 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
878 col = get_next_free_reg(alloc_env, colors);
879 reg = arch_register_for_index(env->cls, col);
880 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
881 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
884 bitset_set(colors, col);
885 arch_set_irn_register(arch_env, irn, reg);
887 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
889 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
890 bitset_set(live, nr);
893 /* Clear the color upon a use. */
894 else if(!b->is_def) {
895 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
898 assert(reg && "Register must have been assigned");
900 col = arch_register_get_index(reg);
901 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
903 bitset_clear(colors, col);
904 bitset_clear(live, nr);
911 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
913 be_chordal_alloc_env_t env;
916 int colors_n = arch_register_class_n_regs(chordal_env->cls);
917 ir_graph *irg = chordal_env->irg;
922 env.chordal_env = chordal_env;
923 env.colors_n = colors_n;
924 env.colors = bitset_alloca(colors_n);
925 env.tmp_colors = bitset_alloca(colors_n);
926 env.in_colors = bitset_alloca(colors_n);
927 env.pre_colored = pset_new_ptr_default();
928 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
931 /* Handle register targeting constraints */
932 dom_tree_walk_irg(irg, constraints, NULL, &env);
934 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
935 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
936 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
939 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
941 /* First, determine the pressure */
942 dom_tree_walk_irg(irg, pressure, NULL, &env);
944 /* Assign the colors */
945 dom_tree_walk_irg(irg, assign, NULL, &env);
947 be_numbering_done(irg);
949 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
951 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
952 plotter = new_plotter_ps(buf);
953 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
954 plotter_free(plotter);
957 bitset_free(env.live);
958 del_pset(env.pre_colored);