2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
30 #include "bipartite.h"
33 #include "irgraph_t.h"
34 #include "irprintf_t.h"
45 #include "besched_t.h"
53 #include "bechordal_t.h"
54 #include "bechordal_draw.h"
56 #define DBG_LEVEL SET_LEVEL_0
57 #define DBG_LEVEL_CHECK SET_LEVEL_0
61 #define DUMP_INTERVALS
63 typedef struct _be_chordal_alloc_env_t {
64 be_chordal_env_t *chordal_env;
66 pset *pre_colored; /**< Set of precolored nodes. */
67 bitset_t *live; /**< A liveness bitset. */
68 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
69 bitset_t *colors; /**< The color mask. */
70 bitset_t *in_colors; /**< Colors used by live in values. */
71 int colors_n; /**< The number of colors. */
72 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
73 } be_chordal_alloc_env_t;
77 /* Make a fourcc for border checking. */
78 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
80 static void check_border_list(struct list_head *head)
83 list_for_each_entry(border_t, x, head, list) {
84 assert(x->magic == BORDER_FOURCC);
88 static void check_heads(be_chordal_env_t *env)
91 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
92 /* ir_printf("checking border list of block %+F\n", ent->key); */
93 check_border_list(ent->value);
99 * Add an interval border to the list of a block's list
100 * of interval border.
101 * @note You always have to create the use before the def.
102 * @param env The environment.
103 * @param head The list head to enqueue the borders.
104 * @param irn The node (value) the border belongs to.
105 * @param pressure The pressure at this point in time.
106 * @param step A time step for the border.
107 * @param is_def Is the border a use or a def.
108 * @return The created border.
110 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
111 ir_node *irn, unsigned step, unsigned pressure,
112 unsigned is_def, unsigned is_real)
119 b = obstack_alloc(&env->obst, sizeof(*b));
121 /* also allocate the def and tie it to the use. */
122 def = obstack_alloc(&env->obst, sizeof(*def));
123 memset(def, 0, sizeof(*def));
128 * Set the link field of the irn to the def.
129 * This strongly relies on the fact, that the use is always
130 * made before the def.
132 set_irn_link(irn, def);
134 b->magic = BORDER_FOURCC;
135 def->magic = BORDER_FOURCC;
139 * If the def is encountered, the use was made and so was the
140 * the def node (see the code above). It was placed into the
141 * link field of the irn, so we can get it there.
144 b = get_irn_link(irn);
146 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
149 b->pressure = pressure;
151 b->is_real = is_real;
154 list_add_tail(&b->list, head);
155 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
162 * Check, if an irn is of the register class currently under processing.
163 * @param env The chordal environment.
164 * @param irn The node.
165 * @return 1, if the node is of that register class, 0 if not.
167 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
169 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
170 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
173 #define has_limited_constr(req, irn) \
174 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
176 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
178 bitset_t *tmp = alloc_env->tmp_colors;
179 bitset_copy(tmp, colors);
180 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
181 return bitset_next_clear(tmp, 0);
184 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
189 bitset_copy(bs, o2->regs);
194 bitset_copy(bs, o1->regs);
198 assert(o1->req.cls == o2->req.cls);
200 if(bitset_contains(o1->regs, o2->regs))
201 bitset_copy(bs, o1->regs);
202 else if(bitset_contains(o2->regs, o1->regs))
203 bitset_copy(bs, o2->regs);
210 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
214 ie.ignore_colors = env->ignore_colors;
215 ie.aenv = env->birg->main_env->arch_env;
216 ie.obst = &env->obst;
218 return be_scan_insn(&ie, irn);
221 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
223 be_insn_t *insn = chordal_scan_insn(env, irn);
224 int n_uses = be_insn_n_uses(insn);
225 int n_defs = be_insn_n_defs(insn);
228 if(!insn->has_constraints)
231 for(i = insn->use_start; i < insn->n_ops; ++i) {
232 be_operand_t *op = &insn->ops[i];
233 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier)) {
234 ir_node *bl = get_nodes_block(insn->irn);
235 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
237 sched_add_before(insn->irn, copy);
238 set_irn_n(insn->irn, op->pos, copy);
239 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
240 be_liveness_update(env->lv, op->carrier);
245 obstack_free(&env->obst, insn);
246 return insn->next_insn;
249 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
251 be_chordal_env_t *env = data;
253 for(irn = sched_first(bl); !sched_is_end(irn);) {
254 irn = prepare_constr_insn(env, irn);
258 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
259 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
262 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
264 const be_chordal_env_t *env = alloc_env->chordal_env;
266 int n_uses = be_insn_n_uses(insn);
267 int n_defs = be_insn_n_defs(insn);
268 bitset_t *bs = bitset_alloca(env->cls->n_regs);
269 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
274 For each out operand, try to find an in operand which can be assigned the
275 same register as the out operand.
277 for (j = 0; j < insn->use_start; ++j) {
279 int smallest_n_regs = 2 * env->cls->n_regs + 1;
280 be_operand_t *out_op = &insn->ops[j];
282 /* Try to find an in operand which has ... */
283 for(i = insn->use_start; i < insn->n_ops; ++i) {
285 const be_operand_t *op = &insn->ops[i];
287 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
288 bitset_clear_all(bs);
289 bitset_copy(bs, op->regs);
290 bitset_and(bs, out_op->regs);
291 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
293 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
295 smallest_n_regs = n_total;
301 be_operand_t *partner = &insn->ops[smallest];
302 out_op->partner = partner;
303 partner->partner = out_op;
309 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
311 be_chordal_env_t *env = alloc_env->chordal_env;
312 const arch_env_t *aenv = env->birg->main_env->arch_env;
313 be_insn_t *insn = *the_insn;
314 ir_node *bl = get_nodes_block(insn->irn);
315 ir_node *copy = NULL;
316 ir_node *perm = NULL;
317 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
318 bitset_t *bs = bitset_alloca(env->cls->n_regs);
319 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
323 assert(insn->has_constraints && "only do this for constrained nodes");
326 Collect all registers that occur in output constraints.
327 This is necessary, since if the insn has one of these as an input constraint
328 and the corresponding operand interferes with the insn, the operand must
331 for(i = 0; i < insn->use_start; ++i) {
332 be_operand_t *op = &insn->ops[i];
333 if(op->has_constraints)
334 bitset_or(out_constr, op->regs);
338 Now, figure out which input operand must be copied since it has input
339 constraints which are also output constraints.
342 for(i = insn->use_start; i < insn->n_ops; ++i) {
343 be_operand_t *op = &insn->ops[i];
344 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
345 bitset_copy(bs, op->regs);
346 bitset_and(bs, out_constr);
349 The operand (interfering with the node) has input constraints
350 which also occur as output constraints, so insert a copy.
352 if(bitset_popcnt(bs) > 0) {
353 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
355 sched_add_before(insn->irn, copy);
356 set_irn_n(insn->irn, op->pos, op->carrier);
358 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
365 Make the Perm, recompute liveness and re-scan the insn since the
366 in operands are now the Projs of the Perm.
368 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
370 /* Registers are propagated by insert_Perm_after(). Clean them here! */
372 const ir_edge_t *edge;
374 foreach_out_edge(perm, edge) {
375 ir_node *proj = get_edge_src_irn(edge);
376 arch_set_irn_register(aenv, proj, NULL);
380 We also have to re-build the insn since the input operands are now the Projs of
381 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
382 the live sets may change.
384 // be_liveness_recompute(env->lv);
385 obstack_free(&env->obst, insn);
386 *the_insn = insn = chordal_scan_insn(env, insn->irn);
389 Copy the input constraints of the insn to the Perm as output
390 constraints. Succeeding phases (coalescing will need that).
392 for(i = insn->use_start; i < insn->n_ops; ++i) {
393 be_operand_t *op = &insn->ops[i];
394 ir_node *proj = op->carrier;
396 Note that the predecessor must not be a Proj of the Perm,
397 since ignore-nodes are not Perm'ed.
399 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
400 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
408 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
410 be_chordal_env_t *env = alloc_env->chordal_env;
411 void *base = obstack_base(&env->obst);
412 be_insn_t *insn = chordal_scan_insn(env, irn);
413 ir_node *res = insn->next_insn;
414 int be_silent = *silent;
416 if(insn->pre_colored) {
418 for(i = 0; i < insn->use_start; ++i)
419 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
423 If the current node is a barrier toggle the silent flag.
424 If we are in the start block, we are ought to be silent at the beginning,
425 so the toggling activates the constraint handling but skips the barrier.
426 If we are in the end block we handle the in requirements of the barrier
427 and set the rest to silent.
429 if(be_is_Barrier(irn))
436 Perms inserted before the constraint handling phase are considered to be
437 correctly precolored. These Perms arise during the ABI handling phase.
439 if(insn->has_constraints) {
440 const arch_env_t *aenv = env->birg->main_env->arch_env;
441 int n_regs = env->cls->n_regs;
442 bitset_t *bs = bitset_alloca(n_regs);
443 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
444 bipartite_t *bp = bipartite_new(n_regs, n_regs);
445 int *assignment = alloca(n_regs * sizeof(assignment[0]));
446 pmap *partners = pmap_create();
447 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
451 const ir_edge_t *edge;
452 ir_node *perm = NULL;
455 prepare the constraint handling of this node.
456 Perms are constructed and Copies are created for constrained values
457 interfering with the instruction.
459 perm = pre_process_constraints(alloc_env, &insn);
461 /* find suitable in operands to the out operands of the node. */
462 pair_up_operands(alloc_env, insn);
465 look at the in/out operands and add each operand (and its possible partner)
466 to a bipartite graph (left: nodes with partners, right: admissible colors).
468 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
469 be_operand_t *op = &insn->ops[i];
472 If the operand has no partner or the partner has not been marked
473 for allocation, determine the admissible registers and mark it
474 for allocation by associating the node and its partner with the
475 set of admissible registers via a bipartite graph.
477 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
479 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
480 alloc_nodes[n_alloc] = op->carrier;
482 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
484 bitset_clear_all(bs);
485 get_decisive_partner_regs(bs, op, op->partner);
487 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
489 bitset_foreach(bs, col)
490 bipartite_add(bp, n_alloc, col);
497 Put all nodes which live by the constrained instruction also to the
498 allocation bipartite graph. They are considered unconstrained.
501 foreach_out_edge(perm, edge) {
502 ir_node *proj = get_edge_src_irn(edge);
504 assert(is_Proj(proj));
506 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
507 assert(n_alloc < n_regs);
508 alloc_nodes[n_alloc] = proj;
509 pmap_insert(partners, proj, NULL);
511 bitset_clear_all(bs);
512 arch_put_non_ignore_regs(aenv, env->cls, bs);
513 bitset_foreach(bs, col)
514 bipartite_add(bp, n_alloc, col);
521 /* Compute a valid register allocation. */
522 bipartite_matching(bp, assignment);
524 /* Assign colors obtained from the matching. */
525 for(i = 0; i < n_alloc; ++i) {
526 const arch_register_t *reg;
530 assert(assignment[i] >= 0 && "there must have been a register assigned");
531 reg = arch_register_for_index(env->cls, assignment[i]);
533 nodes[0] = alloc_nodes[i];
534 nodes[1] = pmap_get(partners, alloc_nodes[i]);
536 for(j = 0; j < 2; ++j) {
540 arch_set_irn_register(aenv, nodes[j], reg);
541 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
542 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
547 /* Allocate the non-constrained Projs of the Perm. */
550 bitset_clear_all(bs);
552 /* Put the colors of all Projs in a bitset. */
553 foreach_out_edge(perm, edge) {
554 ir_node *proj = get_edge_src_irn(edge);
555 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
558 bitset_set(bs, reg->index);
561 /* Assign the not yet assigned Projs of the Perm a suitable color. */
562 foreach_out_edge(perm, edge) {
563 ir_node *proj = get_edge_src_irn(edge);
564 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
566 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
569 col = get_next_free_reg(alloc_env, bs);
570 reg = arch_register_for_index(env->cls, col);
571 bitset_set(bs, reg->index);
572 arch_set_irn_register(aenv, proj, reg);
573 pset_insert_ptr(alloc_env->pre_colored, proj);
574 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
580 pmap_destroy(partners);
584 obstack_free(&env->obst, base);
589 * Handle constraint nodes in each basic block.
590 * handle_constraints() inserts Perm nodes which perm
591 * over all values live at the constrained node right in front
592 * of the constrained node. These Perms signal a constrained node.
593 * For further comments, refer to handle_constraints().
595 static void constraints(ir_node *bl, void *data)
597 be_chordal_alloc_env_t *env = data;
600 Start silent in the start block.
601 The silence remains until the first barrier is seen.
602 Each other block is begun loud.
604 int silent = bl == get_irg_start_block(get_irn_irg(bl));
608 If the block is the start block search the barrier and
609 start handling constraints from there.
612 for(irn = sched_first(bl); !sched_is_end(irn);) {
613 irn = handle_constraints(env, irn, &silent);
618 * Annotate the register pressure to the nodes and compute
619 * the liveness intervals.
620 * @param block The block to do it for.
621 * @param env_ptr The environment.
623 static void pressure(ir_node *block, void *env_ptr)
625 /* Convenience macro for a def */
626 #define border_def(irn, step, real) \
627 border_add(env, head, irn, step, pressure--, 1, real)
629 /* Convenience macro for a use */
630 #define border_use(irn, step, real) \
631 border_add(env, head, irn, step, ++pressure, 0, real)
633 be_chordal_alloc_env_t *alloc_env = env_ptr;
634 be_chordal_env_t *env = alloc_env->chordal_env;
635 bitset_t *live = alloc_env->live;
637 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
641 unsigned pressure = 0;
642 struct list_head *head;
643 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
644 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
646 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
647 bitset_clear_all(live);
649 /* Set up the border list in the block info */
650 head = obstack_alloc(&env->obst, sizeof(*head));
651 INIT_LIST_HEAD(head);
652 assert(pmap_get(env->border_heads, block) == NULL);
653 pmap_insert(env->border_heads, block, head);
656 * Make final uses of all values live out of the block.
657 * They are necessary to build up real intervals.
659 foreach_pset(live_end, irn) {
660 if(has_reg_class(env, irn)) {
661 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
662 bitset_set(live, get_irn_idx(irn));
663 border_use(irn, step, 0);
669 * Determine the last uses of a value inside the block, since they are
670 * relevant for the interval borders.
672 sched_foreach_reverse(block, irn) {
673 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
674 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
677 * If the node defines some value, which can put into a
678 * register of the current class, make a border for it.
680 if(has_reg_class(env, irn)) {
681 int nr = get_irn_idx(irn);
683 bitset_clear(live, nr);
684 border_def(irn, step, 1);
688 * If the node is no phi node we can examine the uses.
691 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
692 ir_node *op = get_irn_n(irn, i);
694 if(has_reg_class(env, op)) {
695 int nr = get_irn_idx(op);
696 const char *msg = "-";
698 if(!bitset_is_set(live, nr)) {
699 border_use(op, step, 1);
700 bitset_set(live, nr);
704 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
712 * Add initial defs for all values live in.
714 foreach_pset(live_in, irn) {
715 if(has_reg_class(env, irn)) {
717 /* Mark the value live in. */
718 bitset_set(live, get_irn_idx(irn));
721 border_def(irn, step, 0);
729 static void assign(ir_node *block, void *env_ptr)
731 be_chordal_alloc_env_t *alloc_env = env_ptr;
732 be_chordal_env_t *env = alloc_env->chordal_env;
733 bitset_t *live = alloc_env->live;
734 bitset_t *colors = alloc_env->colors;
735 bitset_t *in_colors = alloc_env->in_colors;
736 const arch_env_t *arch_env = env->birg->main_env->arch_env;
737 struct list_head *head = get_block_border_head(env, block);
738 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
742 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
744 bitset_clear_all(colors);
745 bitset_clear_all(live);
746 bitset_clear_all(in_colors);
748 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
749 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
750 list_for_each_entry(border_t, b, head, list) {
751 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
752 b->irn, get_irn_idx(b->irn)));
756 * Add initial defs for all values live in.
757 * Since their colors have already been assigned (The dominators were
758 * allocated before), we have to mark their colors as used also.
760 foreach_pset(live_in, irn) {
761 if(has_reg_class(env, irn)) {
762 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
765 assert(reg && "Node must have been assigned a register");
766 col = arch_register_get_index(reg);
768 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
770 /* Mark the color of the live in value as used. */
771 bitset_set(colors, col);
772 bitset_set(in_colors, col);
774 /* Mark the value live in. */
775 bitset_set(live, get_irn_idx(irn));
780 * Mind that the sequence
781 * of defs from back to front defines a perfect
782 * elimination order. So, coloring the definitions from first to last
785 list_for_each_entry_reverse(border_t, b, head, list) {
786 ir_node *irn = b->irn;
787 int nr = get_irn_idx(irn);
788 int ignore = arch_irn_is(arch_env, irn, ignore);
791 * Assign a color, if it is a local def. Global defs already have a
794 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
795 const arch_register_t *reg;
798 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
799 reg = arch_get_irn_register(arch_env, irn);
801 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
805 col = get_next_free_reg(alloc_env, colors);
806 reg = arch_register_for_index(env->cls, col);
807 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
808 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
811 bitset_set(colors, col);
812 arch_set_irn_register(arch_env, irn, reg);
814 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
816 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
817 bitset_set(live, nr);
820 /* Clear the color upon a use. */
821 else if(!b->is_def) {
822 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
825 assert(reg && "Register must have been assigned");
827 col = arch_register_get_index(reg);
828 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
830 bitset_clear(colors, col);
831 bitset_clear(live, nr);
838 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
840 be_chordal_alloc_env_t env;
843 int colors_n = arch_register_class_n_regs(chordal_env->cls);
844 ir_graph *irg = chordal_env->irg;
849 env.chordal_env = chordal_env;
850 env.colors_n = colors_n;
851 env.colors = bitset_alloca(colors_n);
852 env.tmp_colors = bitset_alloca(colors_n);
853 env.in_colors = bitset_alloca(colors_n);
854 env.pre_colored = pset_new_ptr_default();
855 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
858 /* Handle register targeting constraints */
859 dom_tree_walk_irg(irg, constraints, NULL, &env);
861 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
862 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
863 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
867 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
869 /* First, determine the pressure */
870 dom_tree_walk_irg(irg, pressure, NULL, &env);
872 /* Assign the colors */
873 dom_tree_walk_irg(irg, assign, NULL, &env);
875 be_numbering_done(irg);
877 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
879 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
880 plotter = new_plotter_ps(buf);
881 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
882 plotter_free(plotter);
885 bitset_free(env.live);
886 del_pset(env.pre_colored);