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')
81 static void check_border_list(struct list_head *head)
84 list_for_each_entry(border_t, x, head, list) {
85 assert(x->magic == BORDER_FOURCC);
89 static void check_heads(be_chordal_env_t *env)
92 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
93 /* ir_printf("checking border list of block %+F\n", ent->key); */
94 check_border_list(ent->value);
100 * Add an interval border to the list of a block's list
101 * of interval border.
102 * @note You always have to create the use before the def.
103 * @param env The environment.
104 * @param head The list head to enqueue the borders.
105 * @param irn The node (value) the border belongs to.
106 * @param pressure The pressure at this point in time.
107 * @param step A time step for the border.
108 * @param is_def Is the border a use or a def.
109 * @return The created border.
111 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
112 ir_node *irn, unsigned step, unsigned pressure,
113 unsigned is_def, unsigned is_real)
120 b = obstack_alloc(&env->obst, sizeof(*b));
122 /* also allocate the def and tie it to the use. */
123 def = obstack_alloc(&env->obst, sizeof(*def));
124 memset(def, 0, sizeof(*def));
129 * Set the link field of the irn to the def.
130 * This strongly relies on the fact, that the use is always
131 * made before the def.
133 set_irn_link(irn, def);
135 b->magic = BORDER_FOURCC;
136 def->magic = BORDER_FOURCC;
140 * If the def is encountered, the use was made and so was the
141 * the def node (see the code above). It was placed into the
142 * link field of the irn, so we can get it there.
145 b = get_irn_link(irn);
147 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
150 b->pressure = pressure;
152 b->is_real = is_real;
155 list_add_tail(&b->list, head);
156 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
163 * Check, if an irn is of the register class currently under processing.
164 * @param env The chordal environment.
165 * @param irn The node.
166 * @return 1, if the node is of that register class, 0 if not.
168 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
170 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
171 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
174 #define has_limited_constr(req, irn) \
175 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
177 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
179 bitset_t *tmp = alloc_env->tmp_colors;
180 bitset_copy(tmp, colors);
181 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
182 return bitset_next_clear(tmp, 0);
185 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
190 bitset_copy(bs, o2->regs);
195 bitset_copy(bs, o1->regs);
199 assert(o1->req.cls == o2->req.cls);
201 if(bitset_contains(o1->regs, o2->regs))
202 bitset_copy(bs, o1->regs);
203 else if(bitset_contains(o2->regs, o1->regs))
204 bitset_copy(bs, o2->regs);
211 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
215 ie.ignore_colors = env->ignore_colors;
216 ie.aenv = env->birg->main_env->arch_env;
217 ie.obst = &env->obst;
219 return be_scan_insn(&ie, irn);
222 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
224 be_insn_t *insn = chordal_scan_insn(env, irn);
227 if(!insn->has_constraints)
230 for(i = insn->use_start; i < insn->n_ops; ++i) {
231 be_operand_t *op = &insn->ops[i];
232 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier)) {
233 ir_node *bl = get_nodes_block(insn->irn);
234 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
236 sched_add_before(insn->irn, copy);
237 set_irn_n(insn->irn, op->pos, copy);
238 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
239 be_liveness_update(env->lv, op->carrier);
244 obstack_free(&env->obst, insn);
245 return insn->next_insn;
248 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
250 be_chordal_env_t *env = data;
252 for(irn = sched_first(bl); !sched_is_end(irn);) {
253 irn = prepare_constr_insn(env, irn);
257 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
258 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
261 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
263 const be_chordal_env_t *env = alloc_env->chordal_env;
265 int n_uses = be_insn_n_uses(insn);
266 int n_defs = be_insn_n_defs(insn);
267 bitset_t *bs = bitset_alloca(env->cls->n_regs);
268 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
273 For each out operand, try to find an in operand which can be assigned the
274 same register as the out operand.
276 for (j = 0; j < insn->use_start; ++j) {
278 int smallest_n_regs = 2 * env->cls->n_regs + 1;
279 be_operand_t *out_op = &insn->ops[j];
281 /* Try to find an in operand which has ... */
282 for(i = insn->use_start; i < insn->n_ops; ++i) {
284 const be_operand_t *op = &insn->ops[i];
286 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
287 bitset_clear_all(bs);
288 bitset_copy(bs, op->regs);
289 bitset_and(bs, out_op->regs);
290 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
292 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
294 smallest_n_regs = n_total;
300 be_operand_t *partner = &insn->ops[smallest];
301 out_op->partner = partner;
302 partner->partner = out_op;
308 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
310 be_chordal_env_t *env = alloc_env->chordal_env;
311 const arch_env_t *aenv = env->birg->main_env->arch_env;
312 be_insn_t *insn = *the_insn;
313 ir_node *bl = get_nodes_block(insn->irn);
314 ir_node *copy = NULL;
315 ir_node *perm = NULL;
316 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
317 bitset_t *bs = bitset_alloca(env->cls->n_regs);
318 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
322 assert(insn->has_constraints && "only do this for constrained nodes");
325 Collect all registers that occur in output constraints.
326 This is necessary, since if the insn has one of these as an input constraint
327 and the corresponding operand interferes with the insn, the operand must
330 for(i = 0; i < insn->use_start; ++i) {
331 be_operand_t *op = &insn->ops[i];
332 if(op->has_constraints)
333 bitset_or(out_constr, op->regs);
337 Now, figure out which input operand must be copied since it has input
338 constraints which are also output constraints.
345 for(i = insn->use_start; i < insn->n_ops; ++i) {
346 be_operand_t *op = &insn->ops[i];
347 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
348 bitset_copy(bs, op->regs);
349 bitset_and(bs, out_constr);
352 The operand (interfering with the node) has input constraints
353 which also occur as output constraints, so insert a copy.
355 if(bitset_popcnt(bs) > 0) {
356 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
358 sched_add_before(insn->irn, copy);
359 set_irn_n(insn->irn, op->pos, op->carrier);
361 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
368 Make the Perm, recompute liveness and re-scan the insn since the
369 in operands are now the Projs of the Perm.
371 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
373 /* Registers are propagated by insert_Perm_after(). Clean them here! */
375 const ir_edge_t *edge;
377 foreach_out_edge(perm, edge) {
378 ir_node *proj = get_edge_src_irn(edge);
379 arch_set_irn_register(aenv, proj, NULL);
383 We also have to re-build the insn since the input operands are now the Projs of
384 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
385 the live sets may change.
387 // be_liveness_recompute(env->lv);
388 obstack_free(&env->obst, insn);
389 *the_insn = insn = chordal_scan_insn(env, insn->irn);
392 Copy the input constraints of the insn to the Perm as output
393 constraints. Succeeding phases (coalescing will need that).
395 for(i = insn->use_start; i < insn->n_ops; ++i) {
396 be_operand_t *op = &insn->ops[i];
397 ir_node *proj = op->carrier;
399 Note that the predecessor must not be a Proj of the Perm,
400 since ignore-nodes are not Perm'ed.
402 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
403 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
411 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
413 be_chordal_env_t *env = alloc_env->chordal_env;
414 void *base = obstack_base(&env->obst);
415 be_insn_t *insn = chordal_scan_insn(env, irn);
416 ir_node *res = insn->next_insn;
417 int be_silent = *silent;
419 if(insn->pre_colored) {
421 for(i = 0; i < insn->use_start; ++i)
422 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
426 If the current node is a barrier toggle the silent flag.
427 If we are in the start block, we are ought to be silent at the beginning,
428 so the toggling activates the constraint handling but skips the barrier.
429 If we are in the end block we handle the in requirements of the barrier
430 and set the rest to silent.
432 if(be_is_Barrier(irn))
439 Perms inserted before the constraint handling phase are considered to be
440 correctly precolored. These Perms arise during the ABI handling phase.
442 if(insn->has_constraints) {
443 const arch_env_t *aenv = env->birg->main_env->arch_env;
444 int n_regs = env->cls->n_regs;
445 bitset_t *bs = bitset_alloca(n_regs);
446 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
447 bipartite_t *bp = bipartite_new(n_regs, n_regs);
448 int *assignment = alloca(n_regs * sizeof(assignment[0]));
449 pmap *partners = pmap_create();
450 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
454 const ir_edge_t *edge;
455 ir_node *perm = NULL;
458 prepare the constraint handling of this node.
459 Perms are constructed and Copies are created for constrained values
460 interfering with the instruction.
462 perm = pre_process_constraints(alloc_env, &insn);
464 /* find suitable in operands to the out operands of the node. */
465 pair_up_operands(alloc_env, insn);
468 look at the in/out operands and add each operand (and its possible partner)
469 to a bipartite graph (left: nodes with partners, right: admissible colors).
471 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
472 be_operand_t *op = &insn->ops[i];
475 If the operand has no partner or the partner has not been marked
476 for allocation, determine the admissible registers and mark it
477 for allocation by associating the node and its partner with the
478 set of admissible registers via a bipartite graph.
480 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
482 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
483 alloc_nodes[n_alloc] = op->carrier;
485 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
487 bitset_clear_all(bs);
488 get_decisive_partner_regs(bs, op, op->partner);
490 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
492 bitset_foreach(bs, col)
493 bipartite_add(bp, n_alloc, col);
500 Put all nodes which live by the constrained instruction also to the
501 allocation bipartite graph. They are considered unconstrained.
504 foreach_out_edge(perm, edge) {
505 ir_node *proj = get_edge_src_irn(edge);
507 assert(is_Proj(proj));
509 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
510 assert(n_alloc < n_regs);
511 alloc_nodes[n_alloc] = proj;
512 pmap_insert(partners, proj, NULL);
514 bitset_clear_all(bs);
515 arch_put_non_ignore_regs(aenv, env->cls, bs);
516 bitset_foreach(bs, col)
517 bipartite_add(bp, n_alloc, col);
524 /* Compute a valid register allocation. */
525 bipartite_matching(bp, assignment);
527 /* Assign colors obtained from the matching. */
528 for(i = 0; i < n_alloc; ++i) {
529 const arch_register_t *reg;
533 assert(assignment[i] >= 0 && "there must have been a register assigned");
534 reg = arch_register_for_index(env->cls, assignment[i]);
536 nodes[0] = alloc_nodes[i];
537 nodes[1] = pmap_get(partners, alloc_nodes[i]);
539 for(j = 0; j < 2; ++j) {
543 arch_set_irn_register(aenv, nodes[j], reg);
544 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
545 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
550 /* Allocate the non-constrained Projs of the Perm. */
553 bitset_clear_all(bs);
555 /* Put the colors of all Projs in a bitset. */
556 foreach_out_edge(perm, edge) {
557 ir_node *proj = get_edge_src_irn(edge);
558 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
561 bitset_set(bs, reg->index);
564 /* Assign the not yet assigned Projs of the Perm a suitable color. */
565 foreach_out_edge(perm, edge) {
566 ir_node *proj = get_edge_src_irn(edge);
567 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
569 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
572 col = get_next_free_reg(alloc_env, bs);
573 reg = arch_register_for_index(env->cls, col);
574 bitset_set(bs, reg->index);
575 arch_set_irn_register(aenv, proj, reg);
576 pset_insert_ptr(alloc_env->pre_colored, proj);
577 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
583 pmap_destroy(partners);
587 obstack_free(&env->obst, base);
592 * Handle constraint nodes in each basic block.
593 * handle_constraints() inserts Perm nodes which perm
594 * over all values live at the constrained node right in front
595 * of the constrained node. These Perms signal a constrained node.
596 * For further comments, refer to handle_constraints().
598 static void constraints(ir_node *bl, void *data)
600 be_chordal_alloc_env_t *env = data;
603 Start silent in the start block.
604 The silence remains until the first barrier is seen.
605 Each other block is begun loud.
607 int silent = bl == get_irg_start_block(get_irn_irg(bl));
611 If the block is the start block search the barrier and
612 start handling constraints from there.
615 for(irn = sched_first(bl); !sched_is_end(irn);) {
616 irn = handle_constraints(env, irn, &silent);
621 * Annotate the register pressure to the nodes and compute
622 * the liveness intervals.
623 * @param block The block to do it for.
624 * @param env_ptr The environment.
626 static void pressure(ir_node *block, void *env_ptr)
628 /* Convenience macro for a def */
629 #define border_def(irn, step, real) \
630 border_add(env, head, irn, step, pressure--, 1, real)
632 /* Convenience macro for a use */
633 #define border_use(irn, step, real) \
634 border_add(env, head, irn, step, ++pressure, 0, real)
636 be_chordal_alloc_env_t *alloc_env = env_ptr;
637 be_chordal_env_t *env = alloc_env->chordal_env;
638 bitset_t *live = alloc_env->live;
640 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
644 unsigned pressure = 0;
645 struct list_head *head;
646 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
647 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
649 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
650 bitset_clear_all(live);
652 /* Set up the border list in the block info */
653 head = obstack_alloc(&env->obst, sizeof(*head));
654 INIT_LIST_HEAD(head);
655 assert(pmap_get(env->border_heads, block) == NULL);
656 pmap_insert(env->border_heads, block, head);
659 * Make final uses of all values live out of the block.
660 * They are necessary to build up real intervals.
662 foreach_pset(live_end, irn) {
663 if(has_reg_class(env, irn)) {
664 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
665 bitset_set(live, get_irn_idx(irn));
666 border_use(irn, step, 0);
672 * Determine the last uses of a value inside the block, since they are
673 * relevant for the interval borders.
675 sched_foreach_reverse(block, irn) {
676 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
677 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
680 * If the node defines some value, which can put into a
681 * register of the current class, make a border for it.
683 if(has_reg_class(env, irn)) {
684 int nr = get_irn_idx(irn);
686 bitset_clear(live, nr);
687 border_def(irn, step, 1);
691 * If the node is no phi node we can examine the uses.
694 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
695 ir_node *op = get_irn_n(irn, i);
697 if(has_reg_class(env, op)) {
698 int nr = get_irn_idx(op);
699 const char *msg = "-";
701 if(!bitset_is_set(live, nr)) {
702 border_use(op, step, 1);
703 bitset_set(live, nr);
707 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
715 * Add initial defs for all values live in.
717 foreach_pset(live_in, irn) {
718 if(has_reg_class(env, irn)) {
720 /* Mark the value live in. */
721 bitset_set(live, get_irn_idx(irn));
724 border_def(irn, step, 0);
732 static void assign(ir_node *block, void *env_ptr)
734 be_chordal_alloc_env_t *alloc_env = env_ptr;
735 be_chordal_env_t *env = alloc_env->chordal_env;
736 bitset_t *live = alloc_env->live;
737 bitset_t *colors = alloc_env->colors;
738 bitset_t *in_colors = alloc_env->in_colors;
739 const arch_env_t *arch_env = env->birg->main_env->arch_env;
740 struct list_head *head = get_block_border_head(env, block);
741 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
745 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
747 bitset_clear_all(colors);
748 bitset_clear_all(live);
749 bitset_clear_all(in_colors);
751 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
752 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
753 list_for_each_entry(border_t, b, head, list) {
754 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
755 b->irn, get_irn_idx(b->irn)));
759 * Add initial defs for all values live in.
760 * Since their colors have already been assigned (The dominators were
761 * allocated before), we have to mark their colors as used also.
763 foreach_pset(live_in, irn) {
764 if(has_reg_class(env, irn)) {
765 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
768 assert(reg && "Node must have been assigned a register");
769 col = arch_register_get_index(reg);
771 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
773 /* Mark the color of the live in value as used. */
774 bitset_set(colors, col);
775 bitset_set(in_colors, col);
777 /* Mark the value live in. */
778 bitset_set(live, get_irn_idx(irn));
783 * Mind that the sequence
784 * of defs from back to front defines a perfect
785 * elimination order. So, coloring the definitions from first to last
788 list_for_each_entry_reverse(border_t, b, head, list) {
789 ir_node *irn = b->irn;
790 int nr = get_irn_idx(irn);
791 int ignore = arch_irn_is(arch_env, irn, ignore);
794 * Assign a color, if it is a local def. Global defs already have a
797 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
798 const arch_register_t *reg;
801 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
802 reg = arch_get_irn_register(arch_env, irn);
804 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
808 col = get_next_free_reg(alloc_env, colors);
809 reg = arch_register_for_index(env->cls, col);
810 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
811 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
814 bitset_set(colors, col);
815 arch_set_irn_register(arch_env, irn, reg);
817 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
819 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
820 bitset_set(live, nr);
823 /* Clear the color upon a use. */
824 else if(!b->is_def) {
825 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
828 assert(reg && "Register must have been assigned");
830 col = arch_register_get_index(reg);
831 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
833 bitset_clear(colors, col);
834 bitset_clear(live, nr);
841 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
843 be_chordal_alloc_env_t env;
846 int colors_n = arch_register_class_n_regs(chordal_env->cls);
847 ir_graph *irg = chordal_env->irg;
852 env.chordal_env = chordal_env;
853 env.colors_n = colors_n;
854 env.colors = bitset_alloca(colors_n);
855 env.tmp_colors = bitset_alloca(colors_n);
856 env.in_colors = bitset_alloca(colors_n);
857 env.pre_colored = pset_new_ptr_default();
858 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
861 /* Handle register targeting constraints */
862 dom_tree_walk_irg(irg, constraints, NULL, &env);
864 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
865 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
866 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
870 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
872 /* First, determine the pressure */
873 dom_tree_walk_irg(irg, pressure, NULL, &env);
875 /* Assign the colors */
876 dom_tree_walk_irg(irg, assign, NULL, &env);
878 be_numbering_done(irg);
880 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
882 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
883 plotter = new_plotter_ps(buf);
884 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
885 plotter_free(plotter);
888 bitset_free(env.live);
889 del_pset(env.pre_colored);