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"
52 #include "bestatevent.h"
54 #include "bechordal_t.h"
55 #include "bechordal_draw.h"
57 #define DBG_LEVEL SET_LEVEL_0
58 #define DBG_LEVEL_CHECK SET_LEVEL_0
62 #define DUMP_INTERVALS
64 typedef struct _be_chordal_alloc_env_t {
65 be_chordal_env_t *chordal_env;
67 pset *pre_colored; /**< Set of precolored nodes. */
68 bitset_t *live; /**< A liveness bitset. */
69 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
70 bitset_t *colors; /**< The color mask. */
71 bitset_t *in_colors; /**< Colors used by live in values. */
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')
82 static void check_border_list(struct list_head *head)
85 list_for_each_entry(border_t, x, head, list) {
86 assert(x->magic == BORDER_FOURCC);
90 static void check_heads(be_chordal_env_t *env)
93 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
94 /* ir_printf("checking border list of block %+F\n", ent->key); */
95 check_border_list(ent->value);
101 * Add an interval border to the list of a block's list
102 * of interval border.
103 * @note You always have to create the use before the def.
104 * @param env The environment.
105 * @param head The list head to enqueue the borders.
106 * @param irn The node (value) the border belongs to.
107 * @param pressure The pressure at this point in time.
108 * @param step A time step for the border.
109 * @param is_def Is the border a use or a def.
110 * @return The created border.
112 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
113 ir_node *irn, unsigned step, unsigned pressure,
114 unsigned is_def, unsigned is_real)
121 b = obstack_alloc(&env->obst, sizeof(*b));
123 /* also allocate the def and tie it to the use. */
124 def = obstack_alloc(&env->obst, sizeof(*def));
125 memset(def, 0, sizeof(*def));
130 * Set the link field of the irn to the def.
131 * This strongly relies on the fact, that the use is always
132 * made before the def.
134 set_irn_link(irn, def);
136 b->magic = BORDER_FOURCC;
137 def->magic = BORDER_FOURCC;
141 * If the def is encountered, the use was made and so was the
142 * the def node (see the code above). It was placed into the
143 * link field of the irn, so we can get it there.
146 b = get_irn_link(irn);
148 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
151 b->pressure = pressure;
153 b->is_real = is_real;
156 list_add_tail(&b->list, head);
157 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
164 * Check, if an irn is of the register class currently under processing.
165 * @param env The chordal environment.
166 * @param irn The node.
167 * @return 1, if the node is of that register class, 0 if not.
169 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
171 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
172 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
175 #define has_limited_constr(req, irn) \
176 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
178 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
180 bitset_t *tmp = alloc_env->tmp_colors;
181 bitset_copy(tmp, colors);
182 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
183 return bitset_next_clear(tmp, 0);
186 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
191 bitset_copy(bs, o2->regs);
196 bitset_copy(bs, o1->regs);
200 assert(o1->req.cls == o2->req.cls);
202 if(bitset_contains(o1->regs, o2->regs))
203 bitset_copy(bs, o1->regs);
204 else if(bitset_contains(o2->regs, o1->regs))
205 bitset_copy(bs, o2->regs);
212 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
216 ie.ignore_colors = env->ignore_colors;
217 ie.aenv = env->birg->main_env->arch_env;
218 ie.obst = &env->obst;
220 return be_scan_insn(&ie, irn);
223 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
225 be_insn_t *insn = chordal_scan_insn(env, irn);
226 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
227 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
228 ir_node *bl = get_nodes_block(insn->irn);
231 if(!insn->has_constraints)
234 /* insert copies for nodes that occur constrained more than once. */
235 for(i = insn->use_start; i < insn->n_ops; ++i) {
236 be_operand_t *op = &insn->ops[i];
238 if(op->has_constraints) {
239 for(j = i + 1; j < insn->n_ops; ++j) {
240 be_operand_t *a_op = &insn->ops[j];
242 if(a_op->carrier == op->carrier && a_op->has_constraints) {
243 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
245 sched_add_before(insn->irn, copy);
246 set_irn_n(insn->irn, a_op->pos, copy);
247 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
253 /* collect all registers occuring in out constraints. */
254 for(i = 0; i < insn->use_start; ++i) {
255 be_operand_t *op = &insn->ops[i];
256 if(op->has_constraints)
257 bitset_or(def_constr, op->regs);
261 insert copies for all constrained arguments living through the node
262 and being constrained to a register which also occurs in out constraints.
264 for(i = insn->use_start; i < insn->n_ops; ++i) {
265 be_operand_t *op = &insn->ops[i];
267 bitset_copy(tmp, op->regs);
268 bitset_and(tmp, def_constr);
272 1) the operand is constrained.
273 2) lives through the node.
274 3) is constrained to a register occuring in out constraints.
276 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
278 only create the copy if the operand is no copy.
279 this is necessary since the assure constraints phase inserts
280 Copies and Keeps for operands which must be different from the results.
281 Additional copies here would destroy this.
283 if(!be_is_Copy(op->carrier)) {
284 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
286 sched_add_before(insn->irn, copy);
287 set_irn_n(insn->irn, op->pos, copy);
288 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
289 be_liveness_update(env->lv, op->carrier);
295 obstack_free(&env->obst, insn);
296 return insn->next_insn;
299 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
301 be_chordal_env_t *env = data;
303 for(irn = sched_first(bl); !sched_is_end(irn);) {
304 irn = prepare_constr_insn(env, irn);
308 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
309 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
312 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
314 const be_chordal_env_t *env = alloc_env->chordal_env;
316 int n_uses = be_insn_n_uses(insn);
317 int n_defs = be_insn_n_defs(insn);
318 bitset_t *bs = bitset_alloca(env->cls->n_regs);
319 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
324 For each out operand, try to find an in operand which can be assigned the
325 same register as the out operand.
327 for (j = 0; j < insn->use_start; ++j) {
329 int smallest_n_regs = 2 * env->cls->n_regs + 1;
330 be_operand_t *out_op = &insn->ops[j];
332 /* Try to find an in operand which has ... */
333 for(i = insn->use_start; i < insn->n_ops; ++i) {
335 const be_operand_t *op = &insn->ops[i];
337 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
338 bitset_clear_all(bs);
339 bitset_copy(bs, op->regs);
340 bitset_and(bs, out_op->regs);
341 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
343 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
345 smallest_n_regs = n_total;
351 be_operand_t *partner = &insn->ops[smallest];
352 out_op->partner = partner;
353 partner->partner = out_op;
359 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
361 be_chordal_env_t *env = alloc_env->chordal_env;
362 const arch_env_t *aenv = env->birg->main_env->arch_env;
363 be_insn_t *insn = *the_insn;
364 ir_node *bl = get_nodes_block(insn->irn);
365 ir_node *copy = NULL;
366 ir_node *perm = NULL;
367 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
368 bitset_t *bs = bitset_alloca(env->cls->n_regs);
369 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
373 assert(insn->has_constraints && "only do this for constrained nodes");
376 Collect all registers that occur in output constraints.
377 This is necessary, since if the insn has one of these as an input constraint
378 and the corresponding operand interferes with the insn, the operand must
381 for(i = 0; i < insn->use_start; ++i) {
382 be_operand_t *op = &insn->ops[i];
383 if(op->has_constraints)
384 bitset_or(out_constr, op->regs);
388 Now, figure out which input operand must be copied since it has input
389 constraints which are also output constraints.
396 for(i = insn->use_start; i < insn->n_ops; ++i) {
397 be_operand_t *op = &insn->ops[i];
398 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
399 bitset_copy(bs, op->regs);
400 bitset_and(bs, out_constr);
403 The operand (interfering with the node) has input constraints
404 which also occur as output constraints, so insert a copy.
406 if(bitset_popcnt(bs) > 0) {
407 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
409 sched_add_before(insn->irn, copy);
410 set_irn_n(insn->irn, op->pos, op->carrier);
412 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
419 Make the Perm, recompute liveness and re-scan the insn since the
420 in operands are now the Projs of the Perm.
422 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
424 /* Registers are propagated by insert_Perm_after(). Clean them here! */
426 const ir_edge_t *edge;
428 be_stat_ev("constr_perm", get_irn_arity(perm));
429 foreach_out_edge(perm, edge) {
430 ir_node *proj = get_edge_src_irn(edge);
431 arch_set_irn_register(aenv, proj, NULL);
435 We also have to re-build the insn since the input operands are now the Projs of
436 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
437 the live sets may change.
439 // be_liveness_recompute(env->lv);
440 obstack_free(&env->obst, insn);
441 *the_insn = insn = chordal_scan_insn(env, insn->irn);
444 Copy the input constraints of the insn to the Perm as output
445 constraints. Succeeding phases (coalescing will need that).
447 for(i = insn->use_start; i < insn->n_ops; ++i) {
448 be_operand_t *op = &insn->ops[i];
449 ir_node *proj = op->carrier;
451 Note that the predecessor must not be a Proj of the Perm,
452 since ignore-nodes are not Perm'ed.
454 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
455 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
463 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
465 be_chordal_env_t *env = alloc_env->chordal_env;
466 void *base = obstack_base(&env->obst);
467 be_insn_t *insn = chordal_scan_insn(env, irn);
468 ir_node *res = insn->next_insn;
469 int be_silent = *silent;
471 if(insn->pre_colored) {
473 for(i = 0; i < insn->use_start; ++i)
474 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
478 If the current node is a barrier toggle the silent flag.
479 If we are in the start block, we are ought to be silent at the beginning,
480 so the toggling activates the constraint handling but skips the barrier.
481 If we are in the end block we handle the in requirements of the barrier
482 and set the rest to silent.
484 if(be_is_Barrier(irn))
491 Perms inserted before the constraint handling phase are considered to be
492 correctly precolored. These Perms arise during the ABI handling phase.
494 if(insn->has_constraints) {
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 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
499 bipartite_t *bp = bipartite_new(n_regs, n_regs);
500 int *assignment = alloca(n_regs * sizeof(assignment[0]));
501 pmap *partners = pmap_create();
502 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
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 be_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(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
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_andnot(bs, env->ignore_colors);
569 bitset_foreach(bs, col)
570 bipartite_add(bp, n_alloc, col);
577 /* Compute a valid register allocation. */
578 bipartite_matching(bp, assignment);
580 /* Assign colors obtained from the matching. */
581 for(i = 0; i < n_alloc; ++i) {
582 const arch_register_t *reg;
586 assert(assignment[i] >= 0 && "there must have been a register assigned");
587 reg = arch_register_for_index(env->cls, assignment[i]);
589 nodes[0] = alloc_nodes[i];
590 nodes[1] = pmap_get(partners, alloc_nodes[i]);
592 for(j = 0; j < 2; ++j) {
596 arch_set_irn_register(aenv, nodes[j], reg);
597 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
598 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
603 /* Allocate the non-constrained Projs of the Perm. */
606 bitset_clear_all(bs);
608 /* Put the colors of all Projs in a bitset. */
609 foreach_out_edge(perm, edge) {
610 ir_node *proj = get_edge_src_irn(edge);
611 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
614 bitset_set(bs, reg->index);
617 /* Assign the not yet assigned Projs of the Perm a suitable color. */
618 foreach_out_edge(perm, edge) {
619 ir_node *proj = get_edge_src_irn(edge);
620 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
622 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
625 col = get_next_free_reg(alloc_env, bs);
626 reg = arch_register_for_index(env->cls, col);
627 bitset_set(bs, reg->index);
628 arch_set_irn_register(aenv, proj, reg);
629 pset_insert_ptr(alloc_env->pre_colored, proj);
630 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
636 pmap_destroy(partners);
640 obstack_free(&env->obst, base);
645 * Handle constraint nodes in each basic block.
646 * handle_constraints() inserts Perm nodes which perm
647 * over all values live at the constrained node right in front
648 * of the constrained node. These Perms signal a constrained node.
649 * For further comments, refer to handle_constraints().
651 static void constraints(ir_node *bl, void *data)
653 be_chordal_alloc_env_t *env = data;
656 Start silent in the start block.
657 The silence remains until the first barrier is seen.
658 Each other block is begun loud.
660 int silent = bl == get_irg_start_block(get_irn_irg(bl));
664 If the block is the start block search the barrier and
665 start handling constraints from there.
668 for(irn = sched_first(bl); !sched_is_end(irn);) {
669 irn = handle_constraints(env, irn, &silent);
674 * Annotate the register pressure to the nodes and compute
675 * the liveness intervals.
676 * @param block The block to do it for.
677 * @param env_ptr The environment.
679 static void pressure(ir_node *block, void *env_ptr)
681 /* Convenience macro for a def */
682 #define border_def(irn, step, real) \
683 border_add(env, head, irn, step, pressure--, 1, real)
685 /* Convenience macro for a use */
686 #define border_use(irn, step, real) \
687 border_add(env, head, irn, step, ++pressure, 0, real)
689 be_chordal_alloc_env_t *alloc_env = env_ptr;
690 be_chordal_env_t *env = alloc_env->chordal_env;
691 bitset_t *live = alloc_env->live;
693 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
697 unsigned pressure = 0;
698 struct list_head *head;
699 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
700 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
702 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
703 bitset_clear_all(live);
705 /* Set up the border list in the block info */
706 head = obstack_alloc(&env->obst, sizeof(*head));
707 INIT_LIST_HEAD(head);
708 assert(pmap_get(env->border_heads, block) == NULL);
709 pmap_insert(env->border_heads, block, head);
712 * Make final uses of all values live out of the block.
713 * They are necessary to build up real intervals.
715 foreach_pset(live_end, irn) {
716 if(has_reg_class(env, irn)) {
717 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
718 bitset_set(live, get_irn_idx(irn));
719 border_use(irn, step, 0);
725 * Determine the last uses of a value inside the block, since they are
726 * relevant for the interval borders.
728 sched_foreach_reverse(block, irn) {
729 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
730 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
733 * If the node defines some value, which can put into a
734 * register of the current class, make a border for it.
736 if(has_reg_class(env, irn)) {
737 int nr = get_irn_idx(irn);
739 bitset_clear(live, nr);
740 border_def(irn, step, 1);
744 * If the node is no phi node we can examine the uses.
747 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
748 ir_node *op = get_irn_n(irn, i);
750 if(has_reg_class(env, op)) {
751 int nr = get_irn_idx(op);
752 const char *msg = "-";
754 if(!bitset_is_set(live, nr)) {
755 border_use(op, step, 1);
756 bitset_set(live, nr);
760 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
768 * Add initial defs for all values live in.
770 foreach_pset(live_in, irn) {
771 if(has_reg_class(env, irn)) {
773 /* Mark the value live in. */
774 bitset_set(live, get_irn_idx(irn));
777 border_def(irn, step, 0);
785 static void assign(ir_node *block, void *env_ptr)
787 be_chordal_alloc_env_t *alloc_env = env_ptr;
788 be_chordal_env_t *env = alloc_env->chordal_env;
789 bitset_t *live = alloc_env->live;
790 bitset_t *colors = alloc_env->colors;
791 bitset_t *in_colors = alloc_env->in_colors;
792 const arch_env_t *arch_env = env->birg->main_env->arch_env;
793 struct list_head *head = get_block_border_head(env, block);
794 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
798 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
800 bitset_clear_all(colors);
801 bitset_clear_all(live);
802 bitset_clear_all(in_colors);
804 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
805 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
806 list_for_each_entry(border_t, b, head, list) {
807 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
808 b->irn, get_irn_idx(b->irn)));
812 * Add initial defs for all values live in.
813 * Since their colors have already been assigned (The dominators were
814 * allocated before), we have to mark their colors as used also.
816 foreach_pset(live_in, irn) {
817 if(has_reg_class(env, irn)) {
818 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
821 assert(reg && "Node must have been assigned a register");
822 col = arch_register_get_index(reg);
824 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
826 /* Mark the color of the live in value as used. */
827 bitset_set(colors, col);
828 bitset_set(in_colors, col);
830 /* Mark the value live in. */
831 bitset_set(live, get_irn_idx(irn));
836 * Mind that the sequence
837 * of defs from back to front defines a perfect
838 * elimination order. So, coloring the definitions from first to last
841 list_for_each_entry_reverse(border_t, b, head, list) {
842 ir_node *irn = b->irn;
843 int nr = get_irn_idx(irn);
844 int ignore = arch_irn_is(arch_env, irn, ignore);
847 * Assign a color, if it is a local def. Global defs already have a
850 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
851 const arch_register_t *reg;
854 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
855 reg = arch_get_irn_register(arch_env, irn);
857 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
861 col = get_next_free_reg(alloc_env, colors);
862 reg = arch_register_for_index(env->cls, col);
863 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
864 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
867 bitset_set(colors, col);
868 arch_set_irn_register(arch_env, irn, reg);
870 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
872 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
873 bitset_set(live, nr);
876 /* Clear the color upon a use. */
877 else if(!b->is_def) {
878 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
881 assert(reg && "Register must have been assigned");
883 col = arch_register_get_index(reg);
884 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
886 bitset_clear(colors, col);
887 bitset_clear(live, nr);
894 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
896 be_chordal_alloc_env_t env;
899 int colors_n = arch_register_class_n_regs(chordal_env->cls);
900 ir_graph *irg = chordal_env->irg;
905 env.chordal_env = chordal_env;
906 env.colors_n = colors_n;
907 env.colors = bitset_alloca(colors_n);
908 env.tmp_colors = bitset_alloca(colors_n);
909 env.in_colors = bitset_alloca(colors_n);
910 env.pre_colored = pset_new_ptr_default();
911 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
914 /* Handle register targeting constraints */
915 dom_tree_walk_irg(irg, constraints, NULL, &env);
917 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
918 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
919 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
923 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
925 /* First, determine the pressure */
926 dom_tree_walk_irg(irg, pressure, NULL, &env);
928 /* Assign the colors */
929 dom_tree_walk_irg(irg, assign, NULL, &env);
931 be_numbering_done(irg);
933 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
935 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
936 plotter = new_plotter_ps(buf);
937 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
938 plotter_free(plotter);
941 bitset_free(env.live);
942 del_pset(env.pre_colored);