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"
49 #include "bechordal_t.h"
50 #include "bechordal_draw.h"
52 #define DBG_LEVEL SET_LEVEL_0
53 #define DBG_LEVEL_CHECK SET_LEVEL_0
57 #define MAX(x, y) ((x) > (y) ? (x) : (y))
58 #define MIN(x, y) ((x) < (y) ? (x) : (y))
60 #define DUMP_INTERVALS
62 typedef struct _be_chordal_alloc_env_t {
63 be_chordal_env_t *chordal_env;
65 firm_dbg_module_t *constr_dbg; /**< Debug output for the constraint handler. */
66 pset *pre_colored; /**< Set of precolored nodes. */
67 bitset_t *live; /**< A liveness bitset. */
68 bitset_t *colors; /**< The color mask. */
69 bitset_t *in_colors; /**< Colors used by live in values. */
70 bitset_t *ignore_regs; /**< A bitset of all ignore registers in the current class. */
71 int colors_n; /**< The number of colors. */
72 } be_chordal_alloc_env_t;
76 /* Make a fourcc for border checking. */
77 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
79 static void check_border_list(struct list_head *head)
82 list_for_each_entry(border_t, x, head, list) {
83 assert(x->magic == BORDER_FOURCC);
87 static void check_heads(be_chordal_env_t *env)
90 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
91 /* ir_printf("checking border list of block %+F\n", ent->key); */
92 check_border_list(ent->value);
98 * Add an interval border to the list of a block's list
100 * @note You always have to create the use before the def.
101 * @param env The environment.
102 * @param head The list head to enqueue the borders.
103 * @param irn The node (value) the border belongs to.
104 * @param pressure The pressure at this point in time.
105 * @param step A time step for the border.
106 * @param is_def Is the border a use or a def.
107 * @return The created border.
109 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
110 ir_node *irn, unsigned step, unsigned pressure,
111 unsigned is_def, unsigned is_real)
118 b = obstack_alloc(&env->obst, sizeof(*b));
120 /* also allocate the def and tie it to the use. */
121 def = obstack_alloc(&env->obst, sizeof(*def));
122 memset(def, 0, sizeof(*def));
127 * Set the link field of the irn to the def.
128 * This strongly relies on the fact, that the use is always
129 * made before the def.
131 set_irn_link(irn, def);
133 b->magic = BORDER_FOURCC;
134 def->magic = BORDER_FOURCC;
138 * If the def is encountered, the use was made and so was the
139 * the def node (see the code above). It was placed into the
140 * link field of the irn, so we can get it there.
143 b = get_irn_link(irn);
145 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
148 b->pressure = pressure;
150 b->is_real = is_real;
153 list_add_tail(&b->list, head);
154 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
161 * Check, if an irn is of the register class currently under processing.
162 * @param env The chordal environment.
163 * @param irn The node.
164 * @return 1, if the node is of that register class, 0 if not.
166 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
168 // return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
169 return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
172 #define has_limited_constr(req, irn) \
173 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
175 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
177 bitset_or(colors, alloc_env->ignore_regs);
178 return bitset_next_clear(colors, 0);
181 typedef struct _operand_t operand_t;
189 arch_register_req_t req;
190 unsigned has_constraints : 1;
199 unsigned in_constraints : 1;
200 unsigned out_constraints : 1;
201 unsigned has_constraints : 1;
202 unsigned pre_colored : 1;
205 #define insn_n_defs(insn) ((insn)->use_start)
206 #define insn_n_uses(insn) ((insn)->n_ops - (insn)->use_start)
208 static insn_t *scan_insn(be_chordal_env_t *env, ir_node *irn, struct obstack *obst)
210 const arch_env_t *arch_env = env->birg->main_env->arch_env;
216 insn = obstack_alloc(obst, sizeof(insn[0]));
217 memset(insn, 0, sizeof(insn[0]));
220 insn->next_insn = sched_next(irn);
221 if(get_irn_mode(irn) == mode_T) {
224 for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
225 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
226 arch_get_register_req(arch_env, &o.req, p, -1);
229 o.pos = -(get_Proj_proj(p) + 1);
231 o.has_constraints = arch_register_req_is(&o.req, limited);
232 obstack_grow(obst, &o, sizeof(o));
234 insn->out_constraints |= o.has_constraints;
235 pre_colored += arch_get_irn_register(arch_env, p) != NULL;
242 else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
243 arch_get_register_req(arch_env, &o.req, irn, -1);
248 o.has_constraints = arch_register_req_is(&o.req, limited);
249 obstack_grow(obst, &o, sizeof(o));
251 insn->out_constraints |= o.has_constraints;
252 pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
255 insn->pre_colored = pre_colored == insn->n_ops && insn->n_ops > 0;
256 insn->use_start = insn->n_ops;
258 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
259 ir_node *op = get_irn_n(irn, i);
261 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
262 arch_get_register_req(arch_env, &o.req, irn, i);
267 o.has_constraints = arch_register_req_is(&o.req, limited);
268 obstack_grow(obst, &o, sizeof(o));
270 insn->in_constraints |= o.has_constraints;
274 insn->has_constraints = insn->in_constraints | insn->out_constraints;
275 insn->ops = obstack_finish(obst);
277 /* Compute the admissible registers bitsets. */
278 for(i = 0; i < insn->n_ops; ++i) {
279 operand_t *op = &insn->ops[i];
281 assert(op->req.cls == env->cls);
282 op->regs = bitset_obstack_alloc(obst, env->cls->n_regs);
284 if(arch_register_req_is(&op->req, limited))
285 op->req.limited(op->req.limited_env, op->regs);
287 arch_put_non_ignore_regs(env->birg->main_env->arch_env, env->cls, op->regs);
293 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const operand_t *o1, const operand_t *o2)
298 bitset_copy(bs, o2->regs);
303 bitset_copy(bs, o1->regs);
307 assert(o1->req.cls == o2->req.cls);
309 if(bitset_contains(o1->regs, o2->regs))
310 bitset_copy(bs, o1->regs);
311 else if(bitset_contains(o2->regs, o1->regs))
312 bitset_copy(bs, o2->regs);
319 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, insn_t *insn)
321 const be_chordal_env_t *env = alloc_env->chordal_env;
322 const arch_env_t *aenv = env->birg->main_env->arch_env;
323 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
325 int n_uses = insn_n_uses(insn);
326 int n_defs = insn_n_defs(insn);
327 int max_pairs = MIN(n_uses, n_defs);
328 bitset_t *bs = bitset_alloca(env->cls->n_regs);
329 bipartite_t *bp = bipartite_new(n_defs, n_uses);
330 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
335 For each out operand, try to find an in operand which can be assigned the
336 same register as the out operand.
338 for(j = 0; j < insn->use_start; ++j) {
339 operand_t *out_op = &insn->ops[j];
341 /* Try to find an in operand which has ... */
342 for(i = insn->use_start; i < insn->n_ops; ++i) {
343 const operand_t *op = &insn->ops[i];
346 The in operand can only be paired with a def, if the node defining the
347 operand's value does not interfere with the instruction itself. That
348 would mean, that it is live at the instruction, so no result of the instruction
349 can have the same register as the operand.
351 Furthermore, tow operands can be paired, if the admissible registers
352 of one are a subset of the other's. We record the operand whose constraints
353 count in the decisive array.
355 if(!values_interfere(op->irn, op->carrier)) {
356 if(get_decisive_partner_regs(bs, out_op, op))
357 bipartite_add(bp, j, i - insn->use_start);
362 /* Compute the pairing. */
363 bipartite_matching(bp, pairing);
364 for(i = 0; i < insn->use_start; ++i) {
365 int p = pairing[i] + insn->use_start;
367 if(p >= insn->use_start) {
368 insn->ops[i].partner = &insn->ops[p];
369 insn->ops[p].partner = &insn->ops[i];
377 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, insn_t **the_insn)
379 be_chordal_env_t *env = alloc_env->chordal_env;
380 const arch_env_t *aenv = env->birg->main_env->arch_env;
381 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
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);
391 assert(insn->has_constraints && "only do this for constrained nodes");
394 Collect all registers that occur in output constraints.
395 This is necessary, since if the insn has one of these as an input constraint
396 and the corresponding operand interferes with the insn, the operand must
399 for(i = 0; i < insn->use_start; ++i) {
400 operand_t *op = &insn->ops[i];
401 if(op->has_constraints)
402 bitset_or(out_constr, op->regs);
406 Now, figure out which input operand must be copied since it has input
407 constraints which are also output constraints.
409 for(i = insn->use_start; i < insn->n_ops; ++i) {
410 operand_t *op = &insn->ops[i];
411 if(op->has_constraints && values_interfere(op->carrier, insn->irn)) {
412 bitset_copy(bs, op->regs);
413 bitset_and(bs, out_constr);
416 The operand (interfering with the node) has input constraints
417 which also occur as output constraints, so insert a copy.
419 if(bitset_popcnt(bs) > 0) {
420 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
421 insn->ops[i].carrier = copy;
422 sched_add_before(insn->irn, copy);
424 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
430 Make the Perm, recompute liveness and re-scan the insn since the
431 in operands are now the Projs of the Perm.
433 perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(insn->irn));
435 /* Registers are propagated by insert_Perm_after(). Clean them here! */
437 const ir_edge_t *edge;
439 foreach_out_edge(perm, edge) {
440 ir_node *proj = get_edge_src_irn(edge);
441 arch_set_irn_register(aenv, proj, NULL);
445 We also have to re-build the insn since the input operands are now the Projs of
446 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
447 the live sets may change.
449 be_liveness(env->irg);
450 obstack_free(&env->obst, insn);
451 *the_insn = insn = scan_insn(env, insn->irn, &env->obst);
454 Copy the input constraints of the insn to the Perm as output
455 constraints. Succeeding phases (coalescing will need that).
457 for(i = insn->use_start; i < insn->n_ops; ++i) {
458 operand_t *op = &insn->ops[i];
459 ir_node *proj = op->carrier;
461 Note that the predecessor must not be a Proj of the Perm,
462 since ignore-nodes are not Perm'ed.
464 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
465 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
473 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn)
475 be_chordal_env_t *env = alloc_env->chordal_env;
476 void *base = obstack_base(&env->obst);
477 insn_t *insn = scan_insn(env, irn, &env->obst);
478 ir_node *res = insn->next_insn;
480 if(insn->pre_colored) {
482 for(i = 0; i < insn->use_start; ++i)
483 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
486 if(be_is_Perm(irn) || be_is_RegParams(irn) || (be_is_Barrier(irn) && !insn->in_constraints))
490 Perms inserted before the constraint handling phase are considered to be
491 correctly precolored. These Perms arise during the ABI handling phase.
493 if(insn->has_constraints) {
494 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
495 const arch_env_t *aenv = env->birg->main_env->arch_env;
496 int n_regs = env->cls->n_regs;
497 bitset_t *bs = bitset_alloca(n_regs);
498 bitset_t *non_ignore = bitset_alloca(n_regs);
499 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
500 bipartite_t *bp = bipartite_new(n_regs, n_regs);
501 int *assignment = alloca(n_regs * sizeof(assignment[0]));
502 pmap *partners = pmap_create();
506 const ir_edge_t *edge;
507 ir_node *perm = NULL;
510 prepare the constraint handling of this node.
511 Perms are constructed and Copies are created for constrained values
512 interfering with the instruction.
514 perm = pre_process_constraints(alloc_env, &insn);
516 /* find suitable in operands to the out operands of the node. */
517 pair_up_operands(alloc_env, insn);
520 look at the in/out operands and add each operand (and its possible partner)
521 to a bipartite graph (left: nodes with partners, right: admissible colors).
523 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
524 operand_t *op = &insn->ops[i];
527 If the operand has no partner or the partner has not been marked
528 for allocation, determine the admissible registers and mark it
529 for allocation by associating the node and its partner with the
530 set of admissible registers via a bipartite graph.
532 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
534 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
535 alloc_nodes[n_alloc] = op->carrier;
537 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
539 bitset_clear_all(bs);
540 get_decisive_partner_regs(bs, op, op->partner);
542 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
544 bitset_foreach(bs, col)
545 bipartite_add(bp, n_alloc, col);
552 Put all nodes which live by the constrained instruction also to the
553 allocation bipartite graph. They are considered unconstrained.
556 foreach_out_edge(perm, edge) {
557 ir_node *proj = get_edge_src_irn(edge);
559 assert(is_Proj(proj));
561 if(values_interfere(proj, irn)) {
562 assert(n_alloc < n_regs);
563 alloc_nodes[n_alloc] = proj;
564 pmap_insert(partners, proj, NULL);
566 bitset_clear_all(bs);
567 arch_put_non_ignore_regs(aenv, env->cls, bs);
568 bitset_foreach(bs, col)
569 bipartite_add(bp, n_alloc, col);
576 /* Compute a valid register allocation. */
577 bipartite_matching(bp, assignment);
579 /* Assign colors obtained from the matching. */
580 for(i = 0; i < n_alloc; ++i) {
581 const arch_register_t *reg;
585 assert(assignment[i] >= 0 && "there must have been a register assigned");
586 reg = arch_register_for_index(env->cls, assignment[i]);
588 nodes[0] = alloc_nodes[i];
589 nodes[1] = pmap_get(partners, alloc_nodes[i]);
591 for(j = 0; j < 2; ++j) {
595 arch_set_irn_register(aenv, nodes[j], reg);
596 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
597 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
602 /* Allocate the non-constrained Projs of the Perm. */
605 bitset_clear_all(bs);
607 /* Put the colors of all Projs in a bitset. */
608 foreach_out_edge(perm, edge) {
609 ir_node *proj = get_edge_src_irn(edge);
610 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
613 bitset_set(bs, reg->index);
616 /* Assign the not yet assigned Projs of the Perm a suitable color. */
617 foreach_out_edge(perm, edge) {
618 ir_node *proj = get_edge_src_irn(edge);
619 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
621 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
624 col = get_next_free_reg(alloc_env, bs);
625 reg = arch_register_for_index(env->cls, col);
626 bitset_set(bs, reg->index);
627 arch_set_irn_register(aenv, proj, reg);
628 pset_insert_ptr(alloc_env->pre_colored, proj);
629 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
634 pmap_destroy(partners);
638 obstack_free(&env->obst, base);
643 * Handle constraint nodes in each basic block.
644 * be_insert_constr_perms() inserts Perm nodes which perm
645 * over all values live at the constrained node right in front
646 * of the constrained node. These Perms signal a constrained node.
647 * For further comments, refer to handle_constraints_at_perm().
649 static void constraints(ir_node *bl, void *data)
651 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
652 be_chordal_alloc_env_t *env = data;
653 arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
656 for(irn = sched_first(bl); !sched_is_end(irn);) {
657 irn = handle_constraints(env, irn);
662 * Annotate the register pressure to the nodes and compute
663 * the liveness intervals.
664 * @param block The block to do it for.
665 * @param env_ptr The environment.
667 static void pressure(ir_node *block, void *env_ptr)
669 /* Convenience macro for a def */
670 #define border_def(irn, step, real) \
671 border_add(env, head, irn, step, pressure--, 1, real)
673 /* Convenience macro for a use */
674 #define border_use(irn, step, real) \
675 border_add(env, head, irn, step, ++pressure, 0, real)
677 be_chordal_alloc_env_t *alloc_env = env_ptr;
678 be_chordal_env_t *env = alloc_env->chordal_env;
679 const arch_env_t *arch_env = env->birg->main_env->arch_env;
680 bitset_t *live = alloc_env->live;
681 firm_dbg_module_t *dbg = env->dbg;
686 unsigned pressure = 0;
687 struct list_head *head;
688 pset *live_in = put_live_in(block, pset_new_ptr_default());
689 pset *live_end = put_live_end(block, pset_new_ptr_default());
691 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
692 bitset_clear_all(live);
694 /* Set up the border list in the block info */
695 head = obstack_alloc(&env->obst, sizeof(*head));
696 INIT_LIST_HEAD(head);
697 assert(pmap_get(env->border_heads, block) == NULL);
698 pmap_insert(env->border_heads, block, head);
701 * Make final uses of all values live out of the block.
702 * They are necessary to build up real intervals.
704 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
705 if(has_reg_class(env, irn)) {
706 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
707 bitset_set(live, get_irn_graph_nr(irn));
708 border_use(irn, step, 0);
714 * Determine the last uses of a value inside the block, since they are
715 * relevant for the interval borders.
717 sched_foreach_reverse(block, irn) {
718 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
719 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
722 * If the node defines some value, which can put into a
723 * register of the current class, make a border for it.
725 if(has_reg_class(env, irn)) {
726 int nr = get_irn_graph_nr(irn);
728 bitset_clear(live, nr);
729 border_def(irn, step, 1);
733 * If the node is no phi node we can examine the uses.
736 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
737 ir_node *op = get_irn_n(irn, i);
739 if(has_reg_class(env, op)) {
740 int nr = get_irn_graph_nr(op);
742 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
744 if(!bitset_is_set(live, nr)) {
745 border_use(op, step, 1);
746 bitset_set(live, nr);
755 * Add initial defs for all values live in.
757 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
758 if(has_reg_class(env, irn)) {
760 /* Mark the value live in. */
761 bitset_set(live, get_irn_graph_nr(irn));
764 border_def(irn, step, 0);
773 static void assign(ir_node *block, void *env_ptr)
775 be_chordal_alloc_env_t *alloc_env = env_ptr;
776 be_chordal_env_t *env = alloc_env->chordal_env;
777 firm_dbg_module_t *dbg = env->dbg;
778 bitset_t *live = alloc_env->live;
779 bitset_t *colors = alloc_env->colors;
780 bitset_t *in_colors = alloc_env->in_colors;
781 const arch_env_t *arch_env = env->birg->main_env->arch_env;
785 struct list_head *head = get_block_border_head(env, block);
786 pset *live_in = put_live_in(block, pset_new_ptr_default());
788 bitset_clear_all(colors);
789 bitset_clear_all(live);
790 bitset_clear_all(in_colors);
792 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
793 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
794 list_for_each_entry(border_t, b, head, list) {
795 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
796 b->irn, get_irn_graph_nr(b->irn)));
800 * Add initial defs for all values live in.
801 * Since their colors have already been assigned (The dominators were
802 * allocated before), we have to mark their colors as used also.
804 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
805 if(has_reg_class(env, irn)) {
806 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
809 assert(reg && "Node must have been assigned a register");
810 col = arch_register_get_index(reg);
812 /* Mark the color of the live in value as used. */
813 bitset_set(colors, col);
814 bitset_set(in_colors, col);
816 /* Mark the value live in. */
817 bitset_set(live, get_irn_graph_nr(irn));
822 * Mind that the sequence
823 * of defs from back to front defines a perfect
824 * elimination order. So, coloring the definitions from first to last
827 list_for_each_entry_reverse(border_t, b, head, list) {
828 ir_node *irn = b->irn;
829 int nr = get_irn_graph_nr(irn);
832 * Assign a color, if it is a local def. Global defs already have a
835 if(b->is_def && !is_live_in(block, irn)) {
836 const arch_register_t *reg;
839 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
840 reg = arch_get_irn_register(arch_env, irn);
842 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
846 col = get_next_free_reg(alloc_env, colors);
847 reg = arch_register_for_index(env->cls, col);
848 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
851 bitset_set(colors, col);
853 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
854 arch_set_irn_register(arch_env, irn, reg);
856 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
857 arch_register_get_name(reg), col, irn));
859 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
860 bitset_set(live, nr);
863 /* Clear the color upon a use. */
864 else if(!b->is_def) {
865 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
868 assert(reg && "Register must have been assigned");
870 col = arch_register_get_index(reg);
871 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
873 bitset_clear(colors, col);
874 bitset_clear(live, nr);
881 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
883 be_chordal_alloc_env_t env;
887 int colors_n = arch_register_class_n_regs(chordal_env->cls);
888 ir_graph *irg = chordal_env->irg;
891 if(get_irg_dom_state(irg) != dom_consistent)
894 env.chordal_env = chordal_env;
895 env.colors_n = colors_n;
896 env.colors = bitset_malloc(colors_n);
897 env.in_colors = bitset_malloc(colors_n);
898 env.ignore_regs = bitset_malloc(colors_n);
899 env.pre_colored = pset_new_ptr_default();
900 env.constr_dbg = firm_dbg_register("firm.be.chordal.constr");
902 for(i = 0; i < colors_n; ++i)
903 if(arch_register_type_is(&chordal_env->cls->regs[i], ignore))
904 bitset_set(env.ignore_regs, i);
906 /* Handle register targeting constraints */
907 dom_tree_walk_irg(irg, constraints, NULL, &env);
909 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
910 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
911 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
915 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
917 /* First, determine the pressure */
918 dom_tree_walk_irg(irg, pressure, NULL, &env);
920 /* Assign the colors */
921 dom_tree_walk_irg(irg, assign, NULL, &env);
923 be_numbering_done(irg);
925 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
927 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
928 plotter = new_plotter_ps(buf);
929 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
930 plotter_free(plotter);
936 free(env.ignore_regs);
937 del_pset(env.pre_colored);