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 bitset_t *ignore_regs; /**< A bitset of all ignore registers in the current class. */
72 int colors_n; /**< The number of colors. */
73 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
74 } be_chordal_alloc_env_t;
78 /* Make a fourcc for border checking. */
79 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
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->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->ignore_regs);
182 return bitset_next_clear(tmp, 0);
185 typedef struct _operand_t operand_t;
193 arch_register_req_t req;
194 unsigned has_constraints : 1;
203 unsigned in_constraints : 1;
204 unsigned out_constraints : 1;
205 unsigned has_constraints : 1;
206 unsigned pre_colored : 1;
209 #define insn_n_defs(insn) ((insn)->use_start)
210 #define insn_n_uses(insn) ((insn)->n_ops - (insn)->use_start)
212 static insn_t *scan_insn(be_chordal_alloc_env_t *alloc_env, ir_node *irn, struct obstack *obst)
214 const be_chordal_env_t *env = alloc_env->chordal_env;
215 const arch_env_t *arch_env = env->birg->main_env->arch_env;
221 insn = obstack_alloc(obst, sizeof(insn[0]));
222 memset(insn, 0, sizeof(insn[0]));
225 insn->next_insn = sched_next(irn);
226 if(get_irn_mode(irn) == mode_T) {
229 for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
230 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
231 arch_get_register_req(arch_env, &o.req, p, -1);
234 o.pos = -(get_Proj_proj(p) + 1);
236 o.has_constraints = arch_register_req_is(&o.req, limited);
237 obstack_grow(obst, &o, sizeof(o));
239 insn->out_constraints |= o.has_constraints;
240 pre_colored += arch_get_irn_register(arch_env, p) != NULL;
247 else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
248 arch_get_register_req(arch_env, &o.req, irn, -1);
253 o.has_constraints = arch_register_req_is(&o.req, limited);
254 obstack_grow(obst, &o, sizeof(o));
256 insn->out_constraints |= o.has_constraints;
257 pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
260 insn->pre_colored = pre_colored == insn->n_ops && insn->n_ops > 0;
261 insn->use_start = insn->n_ops;
263 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
264 ir_node *op = get_irn_n(irn, i);
266 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
267 arch_get_register_req(arch_env, &o.req, irn, i);
272 o.has_constraints = arch_register_req_is(&o.req, limited);
273 obstack_grow(obst, &o, sizeof(o));
275 insn->in_constraints |= o.has_constraints;
279 insn->has_constraints = insn->in_constraints | insn->out_constraints;
280 insn->ops = obstack_finish(obst);
282 /* Compute the admissible registers bitsets. */
283 for(i = 0; i < insn->n_ops; ++i) {
284 operand_t *op = &insn->ops[i];
286 assert(op->req.cls == env->cls);
287 op->regs = bitset_obstack_alloc(obst, env->cls->n_regs);
289 if(arch_register_req_is(&op->req, limited))
290 op->req.limited(op->req.limited_env, op->regs);
292 arch_put_non_ignore_regs(env->birg->main_env->arch_env, env->cls, op->regs);
298 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const operand_t *o1, const operand_t *o2)
303 bitset_copy(bs, o2->regs);
308 bitset_copy(bs, o1->regs);
312 assert(o1->req.cls == o2->req.cls);
314 if(bitset_contains(o1->regs, o2->regs))
315 bitset_copy(bs, o1->regs);
316 else if(bitset_contains(o2->regs, o1->regs))
317 bitset_copy(bs, o2->regs);
324 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, insn_t *insn)
326 const be_chordal_env_t *env = alloc_env->chordal_env;
328 int n_uses = insn_n_uses(insn);
329 int n_defs = insn_n_defs(insn);
330 bitset_t *bs = bitset_alloca(env->cls->n_regs);
331 bipartite_t *bp = bipartite_new(n_defs, n_uses);
332 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
337 For each out operand, try to find an in operand which can be assigned the
338 same register as the out operand.
340 for(j = 0; j < insn->use_start; ++j) {
341 operand_t *out_op = &insn->ops[j];
343 /* Try to find an in operand which has ... */
344 for(i = insn->use_start; i < insn->n_ops; ++i) {
345 const operand_t *op = &insn->ops[i];
348 The in operand can only be paired with a def, if the node defining the
349 operand's value does not interfere with the instruction itself. That
350 would mean, that it is live at the instruction, so no result of the instruction
351 can have the same register as the operand.
353 Furthermore, tow operands can be paired, if the admissible registers
354 of one are a subset of the other's. We record the operand whose constraints
355 count in the decisive array.
357 if(!values_interfere(op->irn, op->carrier)) {
358 if(get_decisive_partner_regs(bs, out_op, op))
359 bipartite_add(bp, j, i - insn->use_start);
364 /* Compute the pairing. */
365 bipartite_matching(bp, pairing);
366 for(i = 0; i < insn->use_start; ++i) {
367 int p = pairing[i] + insn->use_start;
369 if(p >= insn->use_start) {
370 insn->ops[i].partner = &insn->ops[p];
371 insn->ops[p].partner = &insn->ops[i];
379 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, insn_t **the_insn)
381 be_chordal_env_t *env = alloc_env->chordal_env;
382 const arch_env_t *aenv = env->birg->main_env->arch_env;
383 insn_t *insn = *the_insn;
384 ir_node *bl = get_nodes_block(insn->irn);
385 ir_node *copy = NULL;
386 ir_node *perm = NULL;
387 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
388 bitset_t *bs = bitset_alloca(env->cls->n_regs);
389 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
393 assert(insn->has_constraints && "only do this for constrained nodes");
396 Collect all registers that occur in output constraints.
397 This is necessary, since if the insn has one of these as an input constraint
398 and the corresponding operand interferes with the insn, the operand must
401 for(i = 0; i < insn->use_start; ++i) {
402 operand_t *op = &insn->ops[i];
403 if(op->has_constraints)
404 bitset_or(out_constr, op->regs);
408 Now, figure out which input operand must be copied since it has input
409 constraints which are also output constraints.
411 for(i = insn->use_start; i < insn->n_ops; ++i) {
412 operand_t *op = &insn->ops[i];
413 if(op->has_constraints && (values_interfere(op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
414 bitset_copy(bs, op->regs);
415 bitset_and(bs, out_constr);
418 The operand (interfering with the node) has input constraints
419 which also occur as output constraints, so insert a copy.
421 if(bitset_popcnt(bs) > 0) {
422 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
423 insn->ops[i].carrier = copy;
424 sched_add_before(insn->irn, copy);
426 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
432 Make the Perm, recompute liveness and re-scan the insn since the
433 in operands are now the Projs of the Perm.
435 perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(insn->irn));
437 /* Registers are propagated by insert_Perm_after(). Clean them here! */
439 const ir_edge_t *edge;
441 foreach_out_edge(perm, edge) {
442 ir_node *proj = get_edge_src_irn(edge);
443 arch_set_irn_register(aenv, proj, NULL);
447 We also have to re-build the insn since the input operands are now the Projs of
448 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
449 the live sets may change.
451 be_liveness(env->irg);
452 obstack_free(&env->obst, insn);
453 *the_insn = insn = scan_insn(alloc_env, insn->irn, &env->obst);
456 Copy the input constraints of the insn to the Perm as output
457 constraints. Succeeding phases (coalescing will need that).
459 for(i = insn->use_start; i < insn->n_ops; ++i) {
460 operand_t *op = &insn->ops[i];
461 ir_node *proj = op->carrier;
463 Note that the predecessor must not be a Proj of the Perm,
464 since ignore-nodes are not Perm'ed.
466 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
467 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
475 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
477 be_chordal_env_t *env = alloc_env->chordal_env;
478 void *base = obstack_base(&env->obst);
479 insn_t *insn = scan_insn(alloc_env, irn, &env->obst);
480 ir_node *res = insn->next_insn;
481 int be_silent = *silent;
483 if(insn->pre_colored) {
485 for(i = 0; i < insn->use_start; ++i)
486 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
490 If the current node is a barrier toggle the silent flag.
491 If we are in the start block, we are ought to be silent at the beginning,
492 so the toggling activates the constraint handling but skips the barrier.
493 If we are in the end block we handle the in requirements of the barrier
494 and set the rest to silent.
496 if(be_is_Barrier(irn))
503 Perms inserted before the constraint handling phase are considered to be
504 correctly precolored. These Perms arise during the ABI handling phase.
506 if(insn->has_constraints) {
507 const arch_env_t *aenv = env->birg->main_env->arch_env;
508 int n_regs = env->cls->n_regs;
509 bitset_t *bs = bitset_alloca(n_regs);
510 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
511 bipartite_t *bp = bipartite_new(n_regs, n_regs);
512 int *assignment = alloca(n_regs * sizeof(assignment[0]));
513 pmap *partners = pmap_create();
514 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
518 const ir_edge_t *edge;
519 ir_node *perm = NULL;
522 prepare the constraint handling of this node.
523 Perms are constructed and Copies are created for constrained values
524 interfering with the instruction.
526 perm = pre_process_constraints(alloc_env, &insn);
528 /* find suitable in operands to the out operands of the node. */
529 pair_up_operands(alloc_env, insn);
532 look at the in/out operands and add each operand (and its possible partner)
533 to a bipartite graph (left: nodes with partners, right: admissible colors).
535 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
536 operand_t *op = &insn->ops[i];
539 If the operand has no partner or the partner has not been marked
540 for allocation, determine the admissible registers and mark it
541 for allocation by associating the node and its partner with the
542 set of admissible registers via a bipartite graph.
544 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
546 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
547 alloc_nodes[n_alloc] = op->carrier;
549 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
551 bitset_clear_all(bs);
552 get_decisive_partner_regs(bs, op, op->partner);
554 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
556 bitset_foreach(bs, col)
557 bipartite_add(bp, n_alloc, col);
564 Put all nodes which live by the constrained instruction also to the
565 allocation bipartite graph. They are considered unconstrained.
568 foreach_out_edge(perm, edge) {
569 ir_node *proj = get_edge_src_irn(edge);
571 assert(is_Proj(proj));
573 if(values_interfere(proj, irn) && !pmap_contains(partners, proj)) {
574 assert(n_alloc < n_regs);
575 alloc_nodes[n_alloc] = proj;
576 pmap_insert(partners, proj, NULL);
578 bitset_clear_all(bs);
579 arch_put_non_ignore_regs(aenv, env->cls, bs);
580 bitset_foreach(bs, col)
581 bipartite_add(bp, n_alloc, col);
588 /* Compute a valid register allocation. */
589 bipartite_matching(bp, assignment);
591 /* Assign colors obtained from the matching. */
592 for(i = 0; i < n_alloc; ++i) {
593 const arch_register_t *reg;
597 assert(assignment[i] >= 0 && "there must have been a register assigned");
598 reg = arch_register_for_index(env->cls, assignment[i]);
600 nodes[0] = alloc_nodes[i];
601 nodes[1] = pmap_get(partners, alloc_nodes[i]);
603 for(j = 0; j < 2; ++j) {
607 arch_set_irn_register(aenv, nodes[j], reg);
608 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
609 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
614 /* Allocate the non-constrained Projs of the Perm. */
617 bitset_clear_all(bs);
619 /* Put the colors of all Projs in a bitset. */
620 foreach_out_edge(perm, edge) {
621 ir_node *proj = get_edge_src_irn(edge);
622 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
625 bitset_set(bs, reg->index);
628 /* Assign the not yet assigned Projs of the Perm a suitable color. */
629 foreach_out_edge(perm, edge) {
630 ir_node *proj = get_edge_src_irn(edge);
631 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
633 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
636 col = get_next_free_reg(alloc_env, bs);
637 reg = arch_register_for_index(env->cls, col);
638 bitset_set(bs, reg->index);
639 arch_set_irn_register(aenv, proj, reg);
640 pset_insert_ptr(alloc_env->pre_colored, proj);
641 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
646 pmap_destroy(partners);
650 obstack_free(&env->obst, base);
655 * Handle constraint nodes in each basic block.
656 * handle_constraints() inserts Perm nodes which perm
657 * over all values live at the constrained node right in front
658 * of the constrained node. These Perms signal a constrained node.
659 * For further comments, refer to handle_constraints().
661 static void constraints(ir_node *bl, void *data)
663 be_chordal_alloc_env_t *env = data;
666 Start silent in the start block.
667 The silence remains until the first barrier is seen.
668 Each other block is begun loud.
670 int silent = bl == get_irg_start_block(get_irn_irg(bl));
674 If the block is the start block search the barrier and
675 start handling constraints from there.
678 for(irn = sched_first(bl); !sched_is_end(irn);) {
679 irn = handle_constraints(env, irn, &silent);
684 * Annotate the register pressure to the nodes and compute
685 * the liveness intervals.
686 * @param block The block to do it for.
687 * @param env_ptr The environment.
689 static void pressure(ir_node *block, void *env_ptr)
691 /* Convenience macro for a def */
692 #define border_def(irn, step, real) \
693 border_add(env, head, irn, step, pressure--, 1, real)
695 /* Convenience macro for a use */
696 #define border_use(irn, step, real) \
697 border_add(env, head, irn, step, ++pressure, 0, real)
699 be_chordal_alloc_env_t *alloc_env = env_ptr;
700 be_chordal_env_t *env = alloc_env->chordal_env;
701 bitset_t *live = alloc_env->live;
703 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
707 unsigned pressure = 0;
708 struct list_head *head;
709 pset *live_in = put_live_in(block, pset_new_ptr_default());
710 pset *live_end = put_live_end(block, pset_new_ptr_default());
712 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
713 bitset_clear_all(live);
715 /* Set up the border list in the block info */
716 head = obstack_alloc(&env->obst, sizeof(*head));
717 INIT_LIST_HEAD(head);
718 assert(pmap_get(env->border_heads, block) == NULL);
719 pmap_insert(env->border_heads, block, head);
722 * Make final uses of all values live out of the block.
723 * They are necessary to build up real intervals.
725 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
726 if(has_reg_class(env, irn)) {
727 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
728 bitset_set(live, get_irn_graph_nr(irn));
729 border_use(irn, step, 0);
735 * Determine the last uses of a value inside the block, since they are
736 * relevant for the interval borders.
738 sched_foreach_reverse(block, irn) {
739 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
740 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
743 * If the node defines some value, which can put into a
744 * register of the current class, make a border for it.
746 if(has_reg_class(env, irn)) {
747 int nr = get_irn_graph_nr(irn);
749 bitset_clear(live, nr);
750 border_def(irn, step, 1);
754 * If the node is no phi node we can examine the uses.
757 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
758 ir_node *op = get_irn_n(irn, i);
760 if(has_reg_class(env, op)) {
761 int nr = get_irn_graph_nr(op);
763 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
765 if(!bitset_is_set(live, nr)) {
766 border_use(op, step, 1);
767 bitset_set(live, nr);
776 * Add initial defs for all values live in.
778 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
779 if(has_reg_class(env, irn)) {
781 /* Mark the value live in. */
782 bitset_set(live, get_irn_graph_nr(irn));
785 border_def(irn, step, 0);
794 static void assign(ir_node *block, void *env_ptr)
796 be_chordal_alloc_env_t *alloc_env = env_ptr;
797 be_chordal_env_t *env = alloc_env->chordal_env;
798 bitset_t *live = alloc_env->live;
799 bitset_t *colors = alloc_env->colors;
800 bitset_t *in_colors = alloc_env->in_colors;
801 const arch_env_t *arch_env = env->birg->main_env->arch_env;
802 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
806 struct list_head *head = get_block_border_head(env, block);
807 pset *live_in = put_live_in(block, pset_new_ptr_default());
809 bitset_clear_all(colors);
810 bitset_clear_all(live);
811 bitset_clear_all(in_colors);
813 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
814 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
815 list_for_each_entry(border_t, b, head, list) {
816 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
817 b->irn, get_irn_graph_nr(b->irn)));
821 * Add initial defs for all values live in.
822 * Since their colors have already been assigned (The dominators were
823 * allocated before), we have to mark their colors as used also.
825 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
826 if(has_reg_class(env, irn)) {
827 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
830 assert(reg && "Node must have been assigned a register");
831 col = arch_register_get_index(reg);
833 /* Mark the color of the live in value as used. */
834 bitset_set(colors, col);
835 bitset_set(in_colors, col);
837 /* Mark the value live in. */
838 bitset_set(live, get_irn_graph_nr(irn));
843 * Mind that the sequence
844 * of defs from back to front defines a perfect
845 * elimination order. So, coloring the definitions from first to last
848 list_for_each_entry_reverse(border_t, b, head, list) {
849 ir_node *irn = b->irn;
850 int nr = get_irn_graph_nr(irn);
853 * Assign a color, if it is a local def. Global defs already have a
856 if(b->is_def && !is_live_in(block, irn)) {
857 const arch_register_t *reg;
860 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
861 reg = arch_get_irn_register(arch_env, irn);
863 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
867 col = get_next_free_reg(alloc_env, colors);
868 reg = arch_register_for_index(env->cls, col);
869 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
870 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
873 bitset_set(colors, col);
874 arch_set_irn_register(arch_env, irn, reg);
876 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
877 arch_register_get_name(reg), col, irn));
879 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
880 bitset_set(live, nr);
883 /* Clear the color upon a use. */
884 else if(!b->is_def) {
885 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
888 assert(reg && "Register must have been assigned");
890 col = arch_register_get_index(reg);
891 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
893 bitset_clear(colors, col);
894 bitset_clear(live, nr);
901 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
903 be_chordal_alloc_env_t env;
907 int colors_n = arch_register_class_n_regs(chordal_env->cls);
908 ir_graph *irg = chordal_env->irg;
911 if(get_irg_dom_state(irg) != dom_consistent)
914 env.chordal_env = chordal_env;
915 env.colors_n = colors_n;
916 env.colors = bitset_alloca(colors_n);
917 env.tmp_colors = bitset_alloca(colors_n);
918 env.in_colors = bitset_alloca(colors_n);
919 env.ignore_regs = bitset_alloca(colors_n);
920 env.pre_colored = pset_new_ptr_default();
921 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
923 for(i = 0; i < colors_n; ++i)
924 if(arch_register_type_is(&chordal_env->cls->regs[i], ignore))
925 bitset_set(env.ignore_regs, i);
927 /* Handle register targeting constraints */
928 dom_tree_walk_irg(irg, constraints, NULL, &env);
930 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
931 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
932 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
936 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
938 /* First, determine the pressure */
939 dom_tree_walk_irg(irg, pressure, NULL, &env);
941 /* Assign the colors */
942 dom_tree_walk_irg(irg, assign, NULL, &env);
944 be_numbering_done(irg);
946 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
948 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
949 plotter = new_plotter_ps(buf);
950 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
951 plotter_free(plotter);
954 del_pset(env.pre_colored);