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 bipartite_t *bp = bipartite_new(n_defs, n_uses);
270 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
275 For each out operand, try to find an in operand which can be assigned the
276 same register as the out operand.
278 for(j = 0; j < insn->use_start; ++j) {
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) {
283 const be_operand_t *op = &insn->ops[i];
286 The in operand can only be paired with a def, if the node defining the
287 operand's value does not interfere with the instruction itself. That
288 would mean, that it is live at the instruction, so no result of the instruction
289 can have the same register as the operand.
291 Furthermore, tow operands can be paired, if the admissible registers
292 of one are a subset of the other's. We record the operand whose constraints
293 count in the decisive array.
295 if(!values_interfere(env->lv, op->irn, op->carrier)) {
296 if(get_decisive_partner_regs(bs, out_op, op))
297 bipartite_add(bp, j, i - insn->use_start);
302 /* Compute the pairing. */
303 bipartite_matching(bp, pairing);
304 for(i = 0; i < insn->use_start; ++i) {
305 int p = pairing[i] + insn->use_start;
307 if(p >= insn->use_start) {
308 insn->ops[i].partner = &insn->ops[p];
309 insn->ops[p].partner = &insn->ops[i];
317 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
319 be_chordal_env_t *env = alloc_env->chordal_env;
320 const arch_env_t *aenv = env->birg->main_env->arch_env;
321 be_insn_t *insn = *the_insn;
322 ir_node *bl = get_nodes_block(insn->irn);
323 ir_node *copy = NULL;
324 ir_node *perm = NULL;
325 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
326 bitset_t *bs = bitset_alloca(env->cls->n_regs);
327 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
331 assert(insn->has_constraints && "only do this for constrained nodes");
334 Collect all registers that occur in output constraints.
335 This is necessary, since if the insn has one of these as an input constraint
336 and the corresponding operand interferes with the insn, the operand must
339 for(i = 0; i < insn->use_start; ++i) {
340 be_operand_t *op = &insn->ops[i];
341 if(op->has_constraints)
342 bitset_or(out_constr, op->regs);
346 Now, figure out which input operand must be copied since it has input
347 constraints which are also output constraints.
350 for(i = insn->use_start; i < insn->n_ops; ++i) {
351 be_operand_t *op = &insn->ops[i];
352 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
353 bitset_copy(bs, op->regs);
354 bitset_and(bs, out_constr);
357 The operand (interfering with the node) has input constraints
358 which also occur as output constraints, so insert a copy.
360 if(bitset_popcnt(bs) > 0) {
361 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
363 sched_add_before(insn->irn, copy);
364 set_irn_n(insn->irn, op->pos, op->carrier);
366 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
373 Make the Perm, recompute liveness and re-scan the insn since the
374 in operands are now the Projs of the Perm.
376 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
378 /* Registers are propagated by insert_Perm_after(). Clean them here! */
380 const ir_edge_t *edge;
382 foreach_out_edge(perm, edge) {
383 ir_node *proj = get_edge_src_irn(edge);
384 arch_set_irn_register(aenv, proj, NULL);
388 We also have to re-build the insn since the input operands are now the Projs of
389 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
390 the live sets may change.
392 // be_liveness_recompute(env->lv);
393 obstack_free(&env->obst, insn);
394 *the_insn = insn = chordal_scan_insn(env, insn->irn);
397 Copy the input constraints of the insn to the Perm as output
398 constraints. Succeeding phases (coalescing will need that).
400 for(i = insn->use_start; i < insn->n_ops; ++i) {
401 be_operand_t *op = &insn->ops[i];
402 ir_node *proj = op->carrier;
404 Note that the predecessor must not be a Proj of the Perm,
405 since ignore-nodes are not Perm'ed.
407 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
408 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
416 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
418 be_chordal_env_t *env = alloc_env->chordal_env;
419 void *base = obstack_base(&env->obst);
420 be_insn_t *insn = chordal_scan_insn(env, irn);
421 ir_node *res = insn->next_insn;
422 int be_silent = *silent;
424 if(insn->pre_colored) {
426 for(i = 0; i < insn->use_start; ++i)
427 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
431 If the current node is a barrier toggle the silent flag.
432 If we are in the start block, we are ought to be silent at the beginning,
433 so the toggling activates the constraint handling but skips the barrier.
434 If we are in the end block we handle the in requirements of the barrier
435 and set the rest to silent.
437 if(be_is_Barrier(irn))
444 Perms inserted before the constraint handling phase are considered to be
445 correctly precolored. These Perms arise during the ABI handling phase.
447 if(insn->has_constraints) {
448 const arch_env_t *aenv = env->birg->main_env->arch_env;
449 int n_regs = env->cls->n_regs;
450 bitset_t *bs = bitset_alloca(n_regs);
451 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
452 bipartite_t *bp = bipartite_new(n_regs, n_regs);
453 int *assignment = alloca(n_regs * sizeof(assignment[0]));
454 pmap *partners = pmap_create();
455 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
459 const ir_edge_t *edge;
460 ir_node *perm = NULL;
463 prepare the constraint handling of this node.
464 Perms are constructed and Copies are created for constrained values
465 interfering with the instruction.
467 perm = pre_process_constraints(alloc_env, &insn);
469 /* find suitable in operands to the out operands of the node. */
470 pair_up_operands(alloc_env, insn);
473 look at the in/out operands and add each operand (and its possible partner)
474 to a bipartite graph (left: nodes with partners, right: admissible colors).
476 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
477 be_operand_t *op = &insn->ops[i];
480 If the operand has no partner or the partner has not been marked
481 for allocation, determine the admissible registers and mark it
482 for allocation by associating the node and its partner with the
483 set of admissible registers via a bipartite graph.
485 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
487 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
488 alloc_nodes[n_alloc] = op->carrier;
490 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
492 bitset_clear_all(bs);
493 get_decisive_partner_regs(bs, op, op->partner);
495 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
497 bitset_foreach(bs, col)
498 bipartite_add(bp, n_alloc, col);
505 Put all nodes which live by the constrained instruction also to the
506 allocation bipartite graph. They are considered unconstrained.
509 foreach_out_edge(perm, edge) {
510 ir_node *proj = get_edge_src_irn(edge);
512 assert(is_Proj(proj));
514 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
515 assert(n_alloc < n_regs);
516 alloc_nodes[n_alloc] = proj;
517 pmap_insert(partners, proj, NULL);
519 bitset_clear_all(bs);
520 arch_put_non_ignore_regs(aenv, env->cls, bs);
521 bitset_foreach(bs, col)
522 bipartite_add(bp, n_alloc, col);
529 /* Compute a valid register allocation. */
530 bipartite_matching(bp, assignment);
532 /* Assign colors obtained from the matching. */
533 for(i = 0; i < n_alloc; ++i) {
534 const arch_register_t *reg;
538 assert(assignment[i] >= 0 && "there must have been a register assigned");
539 reg = arch_register_for_index(env->cls, assignment[i]);
541 nodes[0] = alloc_nodes[i];
542 nodes[1] = pmap_get(partners, alloc_nodes[i]);
544 for(j = 0; j < 2; ++j) {
548 arch_set_irn_register(aenv, nodes[j], reg);
549 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
550 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
555 /* Allocate the non-constrained Projs of the Perm. */
558 bitset_clear_all(bs);
560 /* Put the colors of all Projs in a bitset. */
561 foreach_out_edge(perm, edge) {
562 ir_node *proj = get_edge_src_irn(edge);
563 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
566 bitset_set(bs, reg->index);
569 /* Assign the not yet assigned Projs of the Perm a suitable color. */
570 foreach_out_edge(perm, edge) {
571 ir_node *proj = get_edge_src_irn(edge);
572 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
574 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
577 col = get_next_free_reg(alloc_env, bs);
578 reg = arch_register_for_index(env->cls, col);
579 bitset_set(bs, reg->index);
580 arch_set_irn_register(aenv, proj, reg);
581 pset_insert_ptr(alloc_env->pre_colored, proj);
582 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
588 pmap_destroy(partners);
592 obstack_free(&env->obst, base);
597 * Handle constraint nodes in each basic block.
598 * handle_constraints() inserts Perm nodes which perm
599 * over all values live at the constrained node right in front
600 * of the constrained node. These Perms signal a constrained node.
601 * For further comments, refer to handle_constraints().
603 static void constraints(ir_node *bl, void *data)
605 be_chordal_alloc_env_t *env = data;
608 Start silent in the start block.
609 The silence remains until the first barrier is seen.
610 Each other block is begun loud.
612 int silent = bl == get_irg_start_block(get_irn_irg(bl));
616 If the block is the start block search the barrier and
617 start handling constraints from there.
620 for(irn = sched_first(bl); !sched_is_end(irn);) {
621 irn = handle_constraints(env, irn, &silent);
626 * Annotate the register pressure to the nodes and compute
627 * the liveness intervals.
628 * @param block The block to do it for.
629 * @param env_ptr The environment.
631 static void pressure(ir_node *block, void *env_ptr)
633 /* Convenience macro for a def */
634 #define border_def(irn, step, real) \
635 border_add(env, head, irn, step, pressure--, 1, real)
637 /* Convenience macro for a use */
638 #define border_use(irn, step, real) \
639 border_add(env, head, irn, step, ++pressure, 0, real)
641 be_chordal_alloc_env_t *alloc_env = env_ptr;
642 be_chordal_env_t *env = alloc_env->chordal_env;
643 bitset_t *live = alloc_env->live;
645 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
649 unsigned pressure = 0;
650 struct list_head *head;
651 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
652 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
654 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
655 bitset_clear_all(live);
657 /* Set up the border list in the block info */
658 head = obstack_alloc(&env->obst, sizeof(*head));
659 INIT_LIST_HEAD(head);
660 assert(pmap_get(env->border_heads, block) == NULL);
661 pmap_insert(env->border_heads, block, head);
664 * Make final uses of all values live out of the block.
665 * They are necessary to build up real intervals.
667 foreach_pset(live_end, irn) {
668 if(has_reg_class(env, irn)) {
669 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
670 bitset_set(live, get_irn_idx(irn));
671 border_use(irn, step, 0);
677 * Determine the last uses of a value inside the block, since they are
678 * relevant for the interval borders.
680 sched_foreach_reverse(block, irn) {
681 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
682 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
685 * If the node defines some value, which can put into a
686 * register of the current class, make a border for it.
688 if(has_reg_class(env, irn)) {
689 int nr = get_irn_idx(irn);
691 bitset_clear(live, nr);
692 border_def(irn, step, 1);
696 * If the node is no phi node we can examine the uses.
699 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
700 ir_node *op = get_irn_n(irn, i);
702 if(has_reg_class(env, op)) {
703 int nr = get_irn_idx(op);
704 const char *msg = "-";
706 if(!bitset_is_set(live, nr)) {
707 border_use(op, step, 1);
708 bitset_set(live, nr);
712 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
720 * Add initial defs for all values live in.
722 foreach_pset(live_in, irn) {
723 if(has_reg_class(env, irn)) {
725 /* Mark the value live in. */
726 bitset_set(live, get_irn_idx(irn));
729 border_def(irn, step, 0);
737 static void assign(ir_node *block, void *env_ptr)
739 be_chordal_alloc_env_t *alloc_env = env_ptr;
740 be_chordal_env_t *env = alloc_env->chordal_env;
741 bitset_t *live = alloc_env->live;
742 bitset_t *colors = alloc_env->colors;
743 bitset_t *in_colors = alloc_env->in_colors;
744 const arch_env_t *arch_env = env->birg->main_env->arch_env;
745 struct list_head *head = get_block_border_head(env, block);
746 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
750 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
752 bitset_clear_all(colors);
753 bitset_clear_all(live);
754 bitset_clear_all(in_colors);
756 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
757 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
758 list_for_each_entry(border_t, b, head, list) {
759 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
760 b->irn, get_irn_idx(b->irn)));
764 * Add initial defs for all values live in.
765 * Since their colors have already been assigned (The dominators were
766 * allocated before), we have to mark their colors as used also.
768 foreach_pset(live_in, irn) {
769 if(has_reg_class(env, irn)) {
770 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
773 assert(reg && "Node must have been assigned a register");
774 col = arch_register_get_index(reg);
776 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
778 /* Mark the color of the live in value as used. */
779 bitset_set(colors, col);
780 bitset_set(in_colors, col);
782 /* Mark the value live in. */
783 bitset_set(live, get_irn_idx(irn));
788 * Mind that the sequence
789 * of defs from back to front defines a perfect
790 * elimination order. So, coloring the definitions from first to last
793 list_for_each_entry_reverse(border_t, b, head, list) {
794 ir_node *irn = b->irn;
795 int nr = get_irn_idx(irn);
796 int ignore = arch_irn_is(arch_env, irn, ignore);
799 * Assign a color, if it is a local def. Global defs already have a
802 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
803 const arch_register_t *reg;
806 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
807 reg = arch_get_irn_register(arch_env, irn);
809 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
813 col = get_next_free_reg(alloc_env, colors);
814 reg = arch_register_for_index(env->cls, col);
815 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
816 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
819 bitset_set(colors, col);
820 arch_set_irn_register(arch_env, irn, reg);
822 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
824 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
825 bitset_set(live, nr);
828 /* Clear the color upon a use. */
829 else if(!b->is_def) {
830 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
833 assert(reg && "Register must have been assigned");
835 col = arch_register_get_index(reg);
836 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
838 bitset_clear(colors, col);
839 bitset_clear(live, nr);
846 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
848 be_chordal_alloc_env_t env;
851 int colors_n = arch_register_class_n_regs(chordal_env->cls);
852 ir_graph *irg = chordal_env->irg;
857 env.chordal_env = chordal_env;
858 env.colors_n = colors_n;
859 env.colors = bitset_alloca(colors_n);
860 env.tmp_colors = bitset_alloca(colors_n);
861 env.in_colors = bitset_alloca(colors_n);
862 env.pre_colored = pset_new_ptr_default();
863 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
866 /* Handle register targeting constraints */
867 dom_tree_walk_irg(irg, constraints, NULL, &env);
869 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
870 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
871 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
875 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
877 /* First, determine the pressure */
878 dom_tree_walk_irg(irg, pressure, NULL, &env);
880 /* Assign the colors */
881 dom_tree_walk_irg(irg, assign, NULL, &env);
883 be_numbering_done(irg);
885 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
887 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
888 plotter = new_plotter_ps(buf);
889 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
890 plotter_free(plotter);
893 bitset_free(env.live);
894 del_pset(env.pre_colored);