2 * Chordal register allocation.
3 * @author Sebastian Hack
6 * Copyright (C) Universitaet Karlsruhe
7 * Released under the GPL
29 #include "bipartite.h"
32 #include "irgraph_t.h"
33 #include "irprintf_t.h"
43 #include "besched_t.h"
50 #include "bechordal_t.h"
51 #include "bechordal_draw.h"
53 #define DBG_LEVEL SET_LEVEL_0
54 #define DBG_LEVEL_CHECK SET_LEVEL_0
58 #define MAX(x, y) ((x) > (y) ? (x) : (y))
59 #define MIN(x, y) ((x) < (y) ? (x) : (y))
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->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 typedef struct _operand_t operand_t;
192 arch_register_req_t req;
193 unsigned has_constraints : 1;
202 unsigned in_constraints : 1;
203 unsigned out_constraints : 1;
204 unsigned has_constraints : 1;
205 unsigned pre_colored : 1;
208 #define insn_n_defs(insn) ((insn)->use_start)
209 #define insn_n_uses(insn) ((insn)->n_ops - (insn)->use_start)
211 static insn_t *scan_insn(be_chordal_alloc_env_t *alloc_env, ir_node *irn, struct obstack *obst)
213 const be_chordal_env_t *env = alloc_env->chordal_env;
214 const arch_env_t *arch_env = env->birg->main_env->arch_env;
220 insn = obstack_alloc(obst, sizeof(insn[0]));
221 memset(insn, 0, sizeof(insn[0]));
224 insn->next_insn = sched_next(irn);
225 if(get_irn_mode(irn) == mode_T) {
228 for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
229 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
230 arch_get_register_req(arch_env, &o.req, p, -1);
233 o.pos = -(get_Proj_proj(p) + 1);
235 o.has_constraints = arch_register_req_is(&o.req, limited);
236 obstack_grow(obst, &o, sizeof(o));
238 insn->out_constraints |= o.has_constraints;
239 pre_colored += arch_get_irn_register(arch_env, p) != NULL;
246 else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
247 arch_get_register_req(arch_env, &o.req, irn, -1);
252 o.has_constraints = arch_register_req_is(&o.req, limited);
253 obstack_grow(obst, &o, sizeof(o));
255 insn->out_constraints |= o.has_constraints;
256 pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
259 insn->pre_colored = pre_colored == insn->n_ops && insn->n_ops > 0;
260 insn->use_start = insn->n_ops;
262 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
263 ir_node *op = get_irn_n(irn, i);
265 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
266 arch_get_register_req(arch_env, &o.req, irn, i);
271 o.has_constraints = arch_register_req_is(&o.req, limited);
272 obstack_grow(obst, &o, sizeof(o));
274 insn->in_constraints |= o.has_constraints;
278 insn->has_constraints = insn->in_constraints | insn->out_constraints;
279 insn->ops = obstack_finish(obst);
281 /* Compute the admissible registers bitsets. */
282 for(i = 0; i < insn->n_ops; ++i) {
283 operand_t *op = &insn->ops[i];
285 assert(op->req.cls == env->cls);
286 op->regs = bitset_obstack_alloc(obst, env->cls->n_regs);
288 if(arch_register_req_is(&op->req, limited))
289 op->req.limited(op->req.limited_env, op->regs);
291 arch_put_non_ignore_regs(env->birg->main_env->arch_env, env->cls, op->regs);
297 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const operand_t *o1, const operand_t *o2)
302 bitset_copy(bs, o2->regs);
307 bitset_copy(bs, o1->regs);
311 assert(o1->req.cls == o2->req.cls);
313 if(bitset_contains(o1->regs, o2->regs))
314 bitset_copy(bs, o1->regs);
315 else if(bitset_contains(o2->regs, o1->regs))
316 bitset_copy(bs, o2->regs);
323 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, insn_t *insn)
325 const be_chordal_env_t *env = alloc_env->chordal_env;
327 int n_uses = insn_n_uses(insn);
328 int n_defs = insn_n_defs(insn);
329 bitset_t *bs = bitset_alloca(env->cls->n_regs);
330 bipartite_t *bp = bipartite_new(n_defs, n_uses);
331 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
336 For each out operand, try to find an in operand which can be assigned the
337 same register as the out operand.
339 for(j = 0; j < insn->use_start; ++j) {
340 operand_t *out_op = &insn->ops[j];
342 /* Try to find an in operand which has ... */
343 for(i = insn->use_start; i < insn->n_ops; ++i) {
344 const operand_t *op = &insn->ops[i];
347 The in operand can only be paired with a def, if the node defining the
348 operand's value does not interfere with the instruction itself. That
349 would mean, that it is live at the instruction, so no result of the instruction
350 can have the same register as the operand.
352 Furthermore, tow operands can be paired, if the admissible registers
353 of one are a subset of the other's. We record the operand whose constraints
354 count in the decisive array.
356 if(!values_interfere(op->irn, op->carrier)) {
357 if(get_decisive_partner_regs(bs, out_op, op))
358 bipartite_add(bp, j, i - insn->use_start);
363 /* Compute the pairing. */
364 bipartite_matching(bp, pairing);
365 for(i = 0; i < insn->use_start; ++i) {
366 int p = pairing[i] + insn->use_start;
368 if(p >= insn->use_start) {
369 insn->ops[i].partner = &insn->ops[p];
370 insn->ops[p].partner = &insn->ops[i];
378 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, insn_t **the_insn)
380 be_chordal_env_t *env = alloc_env->chordal_env;
381 const arch_env_t *aenv = env->birg->main_env->arch_env;
382 insn_t *insn = *the_insn;
383 ir_node *bl = get_nodes_block(insn->irn);
384 ir_node *copy = NULL;
385 ir_node *perm = NULL;
386 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
387 bitset_t *bs = bitset_alloca(env->cls->n_regs);
388 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
392 assert(insn->has_constraints && "only do this for constrained nodes");
395 Collect all registers that occur in output constraints.
396 This is necessary, since if the insn has one of these as an input constraint
397 and the corresponding operand interferes with the insn, the operand must
400 for(i = 0; i < insn->use_start; ++i) {
401 operand_t *op = &insn->ops[i];
402 if(op->has_constraints)
403 bitset_or(out_constr, op->regs);
407 Now, figure out which input operand must be copied since it has input
408 constraints which are also output constraints.
410 for(i = insn->use_start; i < insn->n_ops; ++i) {
411 operand_t *op = &insn->ops[i];
412 if(op->has_constraints && (values_interfere(op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
413 bitset_copy(bs, op->regs);
414 bitset_and(bs, out_constr);
417 The operand (interfering with the node) has input constraints
418 which also occur as output constraints, so insert a copy.
420 if(bitset_popcnt(bs) > 0) {
421 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
422 insn->ops[i].carrier = copy;
423 sched_add_before(insn->irn, copy);
425 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
431 Make the Perm, recompute liveness and re-scan the insn since the
432 in operands are now the Projs of the Perm.
434 perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(insn->irn));
436 /* Registers are propagated by insert_Perm_after(). Clean them here! */
438 const ir_edge_t *edge;
440 foreach_out_edge(perm, edge) {
441 ir_node *proj = get_edge_src_irn(edge);
442 arch_set_irn_register(aenv, proj, NULL);
446 We also have to re-build the insn since the input operands are now the Projs of
447 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
448 the live sets may change.
450 be_liveness(env->irg);
451 obstack_free(&env->obst, insn);
452 *the_insn = insn = scan_insn(alloc_env, insn->irn, &env->obst);
455 Copy the input constraints of the insn to the Perm as output
456 constraints. Succeeding phases (coalescing will need that).
458 for(i = insn->use_start; i < insn->n_ops; ++i) {
459 operand_t *op = &insn->ops[i];
460 ir_node *proj = op->carrier;
462 Note that the predecessor must not be a Proj of the Perm,
463 since ignore-nodes are not Perm'ed.
465 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
466 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
474 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
476 be_chordal_env_t *env = alloc_env->chordal_env;
477 void *base = obstack_base(&env->obst);
478 insn_t *insn = scan_insn(alloc_env, irn, &env->obst);
479 ir_node *res = insn->next_insn;
480 int be_silent = *silent;
482 if(insn->pre_colored) {
484 for(i = 0; i < insn->use_start; ++i)
485 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
489 If the current node is a barrier toggle the silent flag.
490 If we are in the start block, we are ought to be silent at the beginning,
491 so the toggling activates the constraint handling but skips the barrier.
492 If we are in the end block we handle the in requirements of the barrier
493 and set the rest to silent.
495 if(be_is_Barrier(irn))
502 Perms inserted before the constraint handling phase are considered to be
503 correctly precolored. These Perms arise during the ABI handling phase.
505 if(insn->has_constraints) {
506 const arch_env_t *aenv = env->birg->main_env->arch_env;
507 int n_regs = env->cls->n_regs;
508 bitset_t *bs = bitset_alloca(n_regs);
509 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
510 bipartite_t *bp = bipartite_new(n_regs, n_regs);
511 int *assignment = alloca(n_regs * sizeof(assignment[0]));
512 pmap *partners = pmap_create();
513 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
517 const ir_edge_t *edge;
518 ir_node *perm = NULL;
521 prepare the constraint handling of this node.
522 Perms are constructed and Copies are created for constrained values
523 interfering with the instruction.
525 perm = pre_process_constraints(alloc_env, &insn);
527 /* find suitable in operands to the out operands of the node. */
528 pair_up_operands(alloc_env, insn);
531 look at the in/out operands and add each operand (and its possible partner)
532 to a bipartite graph (left: nodes with partners, right: admissible colors).
534 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
535 operand_t *op = &insn->ops[i];
538 If the operand has no partner or the partner has not been marked
539 for allocation, determine the admissible registers and mark it
540 for allocation by associating the node and its partner with the
541 set of admissible registers via a bipartite graph.
543 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
545 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
546 alloc_nodes[n_alloc] = op->carrier;
548 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
550 bitset_clear_all(bs);
551 get_decisive_partner_regs(bs, op, op->partner);
553 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
555 bitset_foreach(bs, col)
556 bipartite_add(bp, n_alloc, col);
563 Put all nodes which live by the constrained instruction also to the
564 allocation bipartite graph. They are considered unconstrained.
567 foreach_out_edge(perm, edge) {
568 ir_node *proj = get_edge_src_irn(edge);
570 assert(is_Proj(proj));
572 if(values_interfere(proj, irn) && !pmap_contains(partners, proj)) {
573 assert(n_alloc < n_regs);
574 alloc_nodes[n_alloc] = proj;
575 pmap_insert(partners, proj, NULL);
577 bitset_clear_all(bs);
578 arch_put_non_ignore_regs(aenv, env->cls, bs);
579 bitset_foreach(bs, col)
580 bipartite_add(bp, n_alloc, col);
587 /* Compute a valid register allocation. */
588 bipartite_matching(bp, assignment);
590 /* Assign colors obtained from the matching. */
591 for(i = 0; i < n_alloc; ++i) {
592 const arch_register_t *reg;
596 assert(assignment[i] >= 0 && "there must have been a register assigned");
597 reg = arch_register_for_index(env->cls, assignment[i]);
599 nodes[0] = alloc_nodes[i];
600 nodes[1] = pmap_get(partners, alloc_nodes[i]);
602 for(j = 0; j < 2; ++j) {
606 arch_set_irn_register(aenv, nodes[j], reg);
607 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
608 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
613 /* Allocate the non-constrained Projs of the Perm. */
616 bitset_clear_all(bs);
618 /* Put the colors of all Projs in a bitset. */
619 foreach_out_edge(perm, edge) {
620 ir_node *proj = get_edge_src_irn(edge);
621 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
624 bitset_set(bs, reg->index);
627 /* Assign the not yet assigned Projs of the Perm a suitable color. */
628 foreach_out_edge(perm, edge) {
629 ir_node *proj = get_edge_src_irn(edge);
630 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
632 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
635 col = get_next_free_reg(alloc_env, bs);
636 reg = arch_register_for_index(env->cls, col);
637 bitset_set(bs, reg->index);
638 arch_set_irn_register(aenv, proj, reg);
639 pset_insert_ptr(alloc_env->pre_colored, proj);
640 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
645 pmap_destroy(partners);
649 obstack_free(&env->obst, base);
654 * Handle constraint nodes in each basic block.
655 * handle_constraints() inserts Perm nodes which perm
656 * over all values live at the constrained node right in front
657 * of the constrained node. These Perms signal a constrained node.
658 * For further comments, refer to handle_constraints().
660 static void constraints(ir_node *bl, void *data)
662 be_chordal_alloc_env_t *env = data;
665 Start silent in the start block.
666 The silence remains until the first barrier is seen.
667 Each other block is begun loud.
669 int silent = bl == get_irg_start_block(get_irn_irg(bl));
673 If the block is the start block search the barrier and
674 start handling constraints from there.
677 for(irn = sched_first(bl); !sched_is_end(irn);) {
678 irn = handle_constraints(env, irn, &silent);
683 * Annotate the register pressure to the nodes and compute
684 * the liveness intervals.
685 * @param block The block to do it for.
686 * @param env_ptr The environment.
688 static void pressure(ir_node *block, void *env_ptr)
690 /* Convenience macro for a def */
691 #define border_def(irn, step, real) \
692 border_add(env, head, irn, step, pressure--, 1, real)
694 /* Convenience macro for a use */
695 #define border_use(irn, step, real) \
696 border_add(env, head, irn, step, ++pressure, 0, real)
698 be_chordal_alloc_env_t *alloc_env = env_ptr;
699 be_chordal_env_t *env = alloc_env->chordal_env;
700 bitset_t *live = alloc_env->live;
702 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
706 unsigned pressure = 0;
707 struct list_head *head;
708 pset *live_in = put_live_in(block, pset_new_ptr_default());
709 pset *live_end = put_live_end(block, pset_new_ptr_default());
711 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
712 bitset_clear_all(live);
714 /* Set up the border list in the block info */
715 head = obstack_alloc(&env->obst, sizeof(*head));
716 INIT_LIST_HEAD(head);
717 assert(pmap_get(env->border_heads, block) == NULL);
718 pmap_insert(env->border_heads, block, head);
721 * Make final uses of all values live out of the block.
722 * They are necessary to build up real intervals.
724 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
725 if(has_reg_class(env, irn)) {
726 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
727 bitset_set(live, get_irn_graph_nr(irn));
728 border_use(irn, step, 0);
734 * Determine the last uses of a value inside the block, since they are
735 * relevant for the interval borders.
737 sched_foreach_reverse(block, irn) {
738 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
739 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
742 * If the node defines some value, which can put into a
743 * register of the current class, make a border for it.
745 if(has_reg_class(env, irn)) {
746 int nr = get_irn_graph_nr(irn);
748 bitset_clear(live, nr);
749 border_def(irn, step, 1);
753 * If the node is no phi node we can examine the uses.
756 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
757 ir_node *op = get_irn_n(irn, i);
759 if(has_reg_class(env, op)) {
760 int nr = get_irn_graph_nr(op);
762 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
764 if(!bitset_is_set(live, nr)) {
765 border_use(op, step, 1);
766 bitset_set(live, nr);
775 * Add initial defs for all values live in.
777 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
778 if(has_reg_class(env, irn)) {
780 /* Mark the value live in. */
781 bitset_set(live, get_irn_graph_nr(irn));
784 border_def(irn, step, 0);
793 static void assign(ir_node *block, void *env_ptr)
795 be_chordal_alloc_env_t *alloc_env = env_ptr;
796 be_chordal_env_t *env = alloc_env->chordal_env;
797 bitset_t *live = alloc_env->live;
798 bitset_t *colors = alloc_env->colors;
799 bitset_t *in_colors = alloc_env->in_colors;
800 const arch_env_t *arch_env = env->birg->main_env->arch_env;
801 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
805 struct list_head *head = get_block_border_head(env, block);
806 pset *live_in = put_live_in(block, pset_new_ptr_default());
808 bitset_clear_all(colors);
809 bitset_clear_all(live);
810 bitset_clear_all(in_colors);
812 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
813 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
814 list_for_each_entry(border_t, b, head, list) {
815 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
816 b->irn, get_irn_graph_nr(b->irn)));
820 * Add initial defs for all values live in.
821 * Since their colors have already been assigned (The dominators were
822 * allocated before), we have to mark their colors as used also.
824 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
825 if(has_reg_class(env, irn)) {
826 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
829 assert(reg && "Node must have been assigned a register");
830 col = arch_register_get_index(reg);
832 /* Mark the color of the live in value as used. */
833 bitset_set(colors, col);
834 bitset_set(in_colors, col);
836 /* Mark the value live in. */
837 bitset_set(live, get_irn_graph_nr(irn));
842 * Mind that the sequence
843 * of defs from back to front defines a perfect
844 * elimination order. So, coloring the definitions from first to last
847 list_for_each_entry_reverse(border_t, b, head, list) {
848 ir_node *irn = b->irn;
849 int nr = get_irn_graph_nr(irn);
852 * Assign a color, if it is a local def. Global defs already have a
855 if(b->is_def && !is_live_in(block, irn)) {
856 const arch_register_t *reg;
859 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
860 reg = arch_get_irn_register(arch_env, irn);
862 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
866 col = get_next_free_reg(alloc_env, colors);
867 reg = arch_register_for_index(env->cls, col);
868 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
869 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
872 bitset_set(colors, col);
873 arch_set_irn_register(arch_env, irn, reg);
875 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
876 arch_register_get_name(reg), col, irn));
878 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
879 bitset_set(live, nr);
882 /* Clear the color upon a use. */
883 else if(!b->is_def) {
884 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
887 assert(reg && "Register must have been assigned");
889 col = arch_register_get_index(reg);
890 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
892 bitset_clear(colors, col);
893 bitset_clear(live, nr);
900 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
902 be_chordal_alloc_env_t env;
905 int colors_n = arch_register_class_n_regs(chordal_env->cls);
906 ir_graph *irg = chordal_env->irg;
909 if(get_irg_dom_state(irg) != dom_consistent)
912 env.chordal_env = chordal_env;
913 env.colors_n = colors_n;
914 env.colors = bitset_alloca(colors_n);
915 env.tmp_colors = bitset_alloca(colors_n);
916 env.in_colors = bitset_alloca(colors_n);
917 env.pre_colored = pset_new_ptr_default();
918 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
921 /* Handle register targeting constraints */
922 dom_tree_walk_irg(irg, constraints, NULL, &env);
924 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
925 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
926 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
930 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
932 /* First, determine the pressure */
933 dom_tree_walk_irg(irg, pressure, NULL, &env);
935 /* Assign the colors */
936 dom_tree_walk_irg(irg, assign, NULL, &env);
938 be_numbering_done(irg);
940 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
942 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
943 plotter = new_plotter_ps(buf);
944 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
945 plotter_free(plotter);
948 del_pset(env.pre_colored);