2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
29 #include "bipartite.h"
30 #include "hungarian.h"
33 #include "irgraph_t.h"
34 #include "irprintf_t.h"
44 #include "besched_t.h"
51 #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 DEBUG_ONLY(b->magic = BORDER_FOURCC);
137 DEBUG_ONLY(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)
243 reg = arch_get_irn_register(aenv, op);
245 if (reg == NULL || !arch_register_type_is(reg, ignore))
247 if(arch_register_type_is(reg, joker))
250 arch_get_register_req(aenv, &req, irn, i);
251 if (!arch_register_req_is(&req, limited))
254 bitset_clear_all(tmp);
255 req.limited(req.limited_env, tmp);
257 if (bitset_is_set(tmp, reg->index))
260 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
261 be_stat_ev("constr_copy", 1);
263 sched_add_before(irn, copy);
264 set_irn_n(irn, i, copy);
265 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
268 insn = chordal_scan_insn(env, irn);
270 if(!insn->has_constraints)
273 /* insert copies for nodes that occur constrained more than once. */
274 for(i = insn->use_start; i < insn->n_ops; ++i) {
275 be_operand_t *op = &insn->ops[i];
277 if(!op->has_constraints)
280 for(j = i + 1; j < insn->n_ops; ++j) {
282 be_operand_t *a_op = &insn->ops[j];
284 if(a_op->carrier != op->carrier || !a_op->has_constraints)
287 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
288 be_stat_ev("constr_copy", 1);
290 sched_add_before(insn->irn, copy);
291 set_irn_n(insn->irn, a_op->pos, copy);
292 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
296 /* collect all registers occuring in out constraints. */
297 for(i = 0; i < insn->use_start; ++i) {
298 be_operand_t *op = &insn->ops[i];
299 if(op->has_constraints)
300 bitset_or(def_constr, op->regs);
304 insert copies for all constrained arguments living through the node
305 and being constrained to a register which also occurs in out constraints.
307 for(i = insn->use_start; i < insn->n_ops; ++i) {
309 be_operand_t *op = &insn->ops[i];
311 bitset_copy(tmp, op->regs);
312 bitset_and(tmp, def_constr);
316 1) the operand is constrained.
317 2) lives through the node.
318 3) is constrained to a register occuring in out constraints.
320 if(!op->has_constraints ||
321 !values_interfere(lv, insn->irn, op->carrier) ||
322 bitset_popcnt(tmp) == 0)
326 only create the copy if the operand is no copy.
327 this is necessary since the assure constraints phase inserts
328 Copies and Keeps for operands which must be different from the results.
329 Additional copies here would destroy this.
331 if(be_is_Copy(op->carrier))
334 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
336 sched_add_before(insn->irn, copy);
337 set_irn_n(insn->irn, op->pos, copy);
338 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
339 be_liveness_update(lv, op->carrier);
343 obstack_free(&env->obst, insn);
344 return insn->next_insn;
347 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
349 be_chordal_env_t *env = data;
351 for(irn = sched_first(bl); !sched_is_end(irn);) {
352 irn = prepare_constr_insn(env, irn);
356 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
357 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
360 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
362 const be_chordal_env_t *env = alloc_env->chordal_env;
364 int n_uses = be_insn_n_uses(insn);
365 int n_defs = be_insn_n_defs(insn);
366 bitset_t *bs = bitset_alloca(env->cls->n_regs);
367 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
368 be_lv_t *lv = env->birg->lv;
373 For each out operand, try to find an in operand which can be assigned the
374 same register as the out operand.
376 for (j = 0; j < insn->use_start; ++j) {
378 int smallest_n_regs = 2 * env->cls->n_regs + 1;
379 be_operand_t *out_op = &insn->ops[j];
381 /* Try to find an in operand which has ... */
382 for(i = insn->use_start; i < insn->n_ops; ++i) {
384 const be_operand_t *op = &insn->ops[i];
386 if (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
387 bitset_clear_all(bs);
388 bitset_copy(bs, op->regs);
389 bitset_and(bs, out_op->regs);
390 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
392 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
394 smallest_n_regs = n_total;
400 be_operand_t *partner = &insn->ops[smallest];
401 out_op->partner = partner;
402 partner->partner = out_op;
408 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
410 be_chordal_env_t *env = alloc_env->chordal_env;
411 const arch_env_t *aenv = env->birg->main_env->arch_env;
412 be_insn_t *insn = *the_insn;
413 ir_node *bl = get_nodes_block(insn->irn);
414 ir_node *copy = NULL;
415 ir_node *perm = NULL;
416 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
417 bitset_t *bs = bitset_alloca(env->cls->n_regs);
418 be_lv_t *lv = env->birg->lv;
419 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
423 assert(insn->has_constraints && "only do this for constrained nodes");
426 Collect all registers that occur in output constraints.
427 This is necessary, since if the insn has one of these as an input constraint
428 and the corresponding operand interferes with the insn, the operand must
431 for(i = 0; i < insn->use_start; ++i) {
432 be_operand_t *op = &insn->ops[i];
433 if(op->has_constraints)
434 bitset_or(out_constr, op->regs);
440 DEBUG_ONLY((void) dbg;)
443 Make the Perm, recompute liveness and re-scan the insn since the
444 in operands are now the Projs of the Perm.
446 perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
448 /* Registers are propagated by insert_Perm_after(). Clean them here! */
450 const ir_edge_t *edge;
452 be_stat_ev("constr_perm", get_irn_arity(perm));
453 foreach_out_edge(perm, edge) {
454 ir_node *proj = get_edge_src_irn(edge);
455 arch_set_irn_register(aenv, proj, NULL);
459 We also have to re-build the insn since the input operands are now the Projs of
460 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
461 the live sets may change.
463 // be_liveness_recompute(lv);
464 obstack_free(&env->obst, insn);
465 *the_insn = insn = chordal_scan_insn(env, insn->irn);
468 Copy the input constraints of the insn to the Perm as output
469 constraints. Succeeding phases (coalescing will need that).
471 for(i = insn->use_start; i < insn->n_ops; ++i) {
472 be_operand_t *op = &insn->ops[i];
473 ir_node *proj = op->carrier;
475 Note that the predecessor must not be a Proj of the Perm,
476 since ignore-nodes are not Perm'ed.
478 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
479 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
487 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
489 be_chordal_env_t *env = alloc_env->chordal_env;
490 void *base = obstack_base(&env->obst);
491 be_insn_t *insn = chordal_scan_insn(env, irn);
492 ir_node *res = insn->next_insn;
493 int be_silent = *silent;
494 be_lv_t *lv = env->birg->lv;
496 if(insn->pre_colored) {
498 for(i = 0; i < insn->use_start; ++i)
499 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
503 If the current node is a barrier toggle the silent flag.
504 If we are in the start block, we are ought to be silent at the beginning,
505 so the toggling activates the constraint handling but skips the barrier.
506 If we are in the end block we handle the in requirements of the barrier
507 and set the rest to silent.
509 if(be_is_Barrier(irn))
516 Perms inserted before the constraint handling phase are considered to be
517 correctly precolored. These Perms arise during the ABI handling phase.
519 if(insn->has_constraints) {
520 const arch_env_t *aenv = env->birg->main_env->arch_env;
521 int n_regs = env->cls->n_regs;
522 bitset_t *bs = bitset_alloca(n_regs);
523 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
524 hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
525 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
526 int *assignment = alloca(n_regs * sizeof(assignment[0]));
527 pmap *partners = pmap_create();
528 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
532 const ir_edge_t *edge;
533 ir_node *perm = NULL;
537 prepare the constraint handling of this node.
538 Perms are constructed and Copies are created for constrained values
539 interfering with the instruction.
541 perm = pre_process_constraints(alloc_env, &insn);
543 /* find suitable in operands to the out operands of the node. */
544 pair_up_operands(alloc_env, insn);
547 look at the in/out operands and add each operand (and its possible partner)
548 to a bipartite graph (left: nodes with partners, right: admissible colors).
550 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
551 be_operand_t *op = &insn->ops[i];
554 If the operand has no partner or the partner has not been marked
555 for allocation, determine the admissible registers and mark it
556 for allocation by associating the node and its partner with the
557 set of admissible registers via a bipartite graph.
559 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
561 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
562 alloc_nodes[n_alloc] = op->carrier;
564 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
566 bitset_clear_all(bs);
567 get_decisive_partner_regs(bs, op, op->partner);
569 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
571 bitset_foreach(bs, col)
572 hungarian_add(bp, n_alloc, col, 1);
573 // bipartite_add(bp, n_alloc, col);
580 Put all nodes which live through the constrained instruction also to the
581 allocation bipartite graph. They are considered unconstrained.
584 foreach_out_edge(perm, edge) {
585 ir_node *proj = get_edge_src_irn(edge);
587 assert(is_Proj(proj));
589 if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
590 assert(n_alloc < n_regs);
591 alloc_nodes[n_alloc] = proj;
592 pmap_insert(partners, proj, NULL);
594 bitset_clear_all(bs);
595 arch_put_non_ignore_regs(aenv, env->cls, bs);
596 bitset_andnot(bs, env->ignore_colors);
597 bitset_foreach(bs, col)
598 hungarian_add(bp, n_alloc, col, 1);
599 // bipartite_add(bp, n_alloc, col);
606 /* Compute a valid register allocation. */
607 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
608 match_res = hungarian_solve(bp, assignment, &cost, 1);
609 assert(match_res == 0 && "matching failed");
610 //bipartite_matching(bp, assignment);
612 /* Assign colors obtained from the matching. */
613 for(i = 0; i < n_alloc; ++i) {
614 const arch_register_t *reg;
618 assert(assignment[i] >= 0 && "there must have been a register assigned");
619 reg = arch_register_for_index(env->cls, assignment[i]);
621 nodes[0] = alloc_nodes[i];
622 nodes[1] = pmap_get(partners, alloc_nodes[i]);
624 for(j = 0; j < 2; ++j) {
628 arch_set_irn_register(aenv, nodes[j], reg);
629 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
630 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
635 /* Allocate the non-constrained Projs of the Perm. */
638 bitset_clear_all(bs);
640 /* Put the colors of all Projs in a bitset. */
641 foreach_out_edge(perm, edge) {
642 ir_node *proj = get_edge_src_irn(edge);
643 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
646 bitset_set(bs, reg->index);
649 /* Assign the not yet assigned Projs of the Perm a suitable color. */
650 foreach_out_edge(perm, edge) {
651 ir_node *proj = get_edge_src_irn(edge);
652 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
654 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
657 col = get_next_free_reg(alloc_env, bs);
658 reg = arch_register_for_index(env->cls, col);
659 bitset_set(bs, reg->index);
660 arch_set_irn_register(aenv, proj, reg);
661 pset_insert_ptr(alloc_env->pre_colored, proj);
662 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
667 //bipartite_free(bp);
669 pmap_destroy(partners);
673 obstack_free(&env->obst, base);
678 * Handle constraint nodes in each basic block.
679 * handle_constraints() inserts Perm nodes which perm
680 * over all values live at the constrained node right in front
681 * of the constrained node. These Perms signal a constrained node.
682 * For further comments, refer to handle_constraints().
684 static void constraints(ir_node *bl, void *data)
686 be_chordal_alloc_env_t *env = data;
689 Start silent in the start block.
690 The silence remains until the first barrier is seen.
691 Each other block is begun loud.
693 int silent = bl == get_irg_start_block(get_irn_irg(bl));
697 If the block is the start block search the barrier and
698 start handling constraints from there.
701 for(irn = sched_first(bl); !sched_is_end(irn);) {
702 irn = handle_constraints(env, irn, &silent);
707 * Annotate the register pressure to the nodes and compute
708 * the liveness intervals.
709 * @param block The block to do it for.
710 * @param env_ptr The environment.
712 static void pressure(ir_node *block, void *env_ptr)
714 /* Convenience macro for a def */
715 #define border_def(irn, step, real) \
716 border_add(env, head, irn, step, pressure--, 1, real)
718 /* Convenience macro for a use */
719 #define border_use(irn, step, real) \
720 border_add(env, head, irn, step, ++pressure, 0, real)
722 be_chordal_alloc_env_t *alloc_env = env_ptr;
723 be_chordal_env_t *env = alloc_env->chordal_env;
724 bitset_t *live = alloc_env->live;
726 be_lv_t *lv = env->birg->lv;
727 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
731 unsigned pressure = 0;
732 struct list_head *head;
733 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
734 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
736 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
737 bitset_clear_all(live);
739 /* Set up the border list in the block info */
740 head = obstack_alloc(&env->obst, sizeof(*head));
741 INIT_LIST_HEAD(head);
742 assert(pmap_get(env->border_heads, block) == NULL);
743 pmap_insert(env->border_heads, block, head);
746 * Make final uses of all values live out of the block.
747 * They are necessary to build up real intervals.
749 foreach_pset(live_end, irn) {
750 if(has_reg_class(env, irn)) {
751 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
752 bitset_set(live, get_irn_idx(irn));
753 border_use(irn, step, 0);
759 * Determine the last uses of a value inside the block, since they are
760 * relevant for the interval borders.
762 sched_foreach_reverse(block, irn) {
763 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
764 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
767 * If the node defines some value, which can put into a
768 * register of the current class, make a border for it.
770 if(has_reg_class(env, irn)) {
771 int nr = get_irn_idx(irn);
773 bitset_clear(live, nr);
774 border_def(irn, step, 1);
778 * If the node is no phi node we can examine the uses.
781 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
782 ir_node *op = get_irn_n(irn, i);
784 if(has_reg_class(env, op)) {
785 int nr = get_irn_idx(op);
786 const char *msg = "-";
788 if(!bitset_is_set(live, nr)) {
789 border_use(op, step, 1);
790 bitset_set(live, nr);
794 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
802 * Add initial defs for all values live in.
804 foreach_pset(live_in, irn) {
805 if(has_reg_class(env, irn)) {
807 /* Mark the value live in. */
808 bitset_set(live, get_irn_idx(irn));
811 border_def(irn, step, 0);
819 static void assign(ir_node *block, void *env_ptr)
821 be_chordal_alloc_env_t *alloc_env = env_ptr;
822 be_chordal_env_t *env = alloc_env->chordal_env;
823 bitset_t *live = alloc_env->live;
824 bitset_t *colors = alloc_env->colors;
825 bitset_t *in_colors = alloc_env->in_colors;
826 const arch_env_t *arch_env = env->birg->main_env->arch_env;
827 struct list_head *head = get_block_border_head(env, block);
828 be_lv_t *lv = env->birg->lv;
829 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
833 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
835 bitset_clear_all(colors);
836 bitset_clear_all(live);
837 bitset_clear_all(in_colors);
839 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
840 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
841 list_for_each_entry(border_t, b, head, list) {
842 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
843 b->irn, get_irn_idx(b->irn)));
847 * Add initial defs for all values live in.
848 * Since their colors have already been assigned (The dominators were
849 * allocated before), we have to mark their colors as used also.
851 foreach_pset(live_in, irn) {
852 if(has_reg_class(env, irn)) {
853 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
856 assert(reg && "Node must have been assigned a register");
857 col = arch_register_get_index(reg);
859 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
861 /* Mark the color of the live in value as used. */
862 bitset_set(colors, col);
863 bitset_set(in_colors, col);
865 /* Mark the value live in. */
866 bitset_set(live, get_irn_idx(irn));
871 * Mind that the sequence of defs from back to front defines a perfect
872 * elimination order. So, coloring the definitions from first to last
875 list_for_each_entry_reverse(border_t, b, head, list) {
876 ir_node *irn = b->irn;
877 int nr = get_irn_idx(irn);
878 int ignore = arch_irn_is(arch_env, irn, ignore);
881 * Assign a color, if it is a local def. Global defs already have a
884 if(b->is_def && !be_is_live_in(lv, block, irn)) {
885 const arch_register_t *reg;
888 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
889 reg = arch_get_irn_register(arch_env, irn);
891 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
895 col = get_next_free_reg(alloc_env, colors);
896 reg = arch_register_for_index(env->cls, col);
897 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
898 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
901 bitset_set(colors, col);
902 arch_set_irn_register(arch_env, irn, reg);
904 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
906 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
907 bitset_set(live, nr);
910 /* Clear the color upon a use. */
911 else if(!b->is_def) {
912 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
915 assert(reg && "Register must have been assigned");
917 col = arch_register_get_index(reg);
918 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
920 bitset_clear(colors, col);
921 bitset_clear(live, nr);
928 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
930 be_chordal_alloc_env_t env;
932 be_irg_t *birg = chordal_env->birg;
934 int colors_n = arch_register_class_n_regs(chordal_env->cls);
935 ir_graph *irg = chordal_env->irg;
938 be_assure_dom_front(birg);
939 be_assure_liveness(birg);
942 env.chordal_env = chordal_env;
943 env.colors_n = colors_n;
944 env.colors = bitset_alloca(colors_n);
945 env.tmp_colors = bitset_alloca(colors_n);
946 env.in_colors = bitset_alloca(colors_n);
947 env.pre_colored = pset_new_ptr_default();
948 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
951 /* Handle register targeting constraints */
952 dom_tree_walk_irg(irg, constraints, NULL, &env);
954 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
955 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
956 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
959 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
961 /* First, determine the pressure */
962 dom_tree_walk_irg(irg, pressure, NULL, &env);
964 /* Assign the colors */
965 dom_tree_walk_irg(irg, assign, NULL, &env);
967 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
969 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
970 plotter = new_plotter_ps(buf);
971 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
972 plotter_free(plotter);
975 bitset_free(env.live);
976 del_pset(env.pre_colored);