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 const arch_env_t *aenv = env->birg->main_env->arch_env;
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(irn);
233 for(i = get_irn_arity(irn) - 1; i >= 0; --i) {
234 ir_node *op = get_irn_n(irn, i);
236 const arch_register_t *reg;
237 arch_register_req_t req;
239 reg = arch_get_irn_register(aenv, op);
241 if(reg && arch_register_type_is(reg, ignore)) {
242 arch_get_register_req(aenv, &req, irn, i);
243 if(arch_register_req_is(&req, limited)) {
244 bitset_clear_all(tmp);
245 req.limited(req.limited_env, tmp);
246 if(!bitset_is_set(tmp, reg->index)) {
247 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
248 be_stat_ev("constr_copy", 1);
250 sched_add_before(irn, copy);
251 set_irn_n(irn, i, copy);
252 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
258 insn = chordal_scan_insn(env, irn);
260 if(!insn->has_constraints)
263 /* insert copies for nodes that occur constrained more than once. */
264 for(i = insn->use_start; i < insn->n_ops; ++i) {
265 be_operand_t *op = &insn->ops[i];
267 if(op->has_constraints) {
268 for(j = i + 1; j < insn->n_ops; ++j) {
269 be_operand_t *a_op = &insn->ops[j];
271 if(a_op->carrier == op->carrier && a_op->has_constraints) {
272 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
273 be_stat_ev("constr_copy", 1);
275 sched_add_before(insn->irn, copy);
276 set_irn_n(insn->irn, a_op->pos, copy);
277 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
283 /* collect all registers occuring in out constraints. */
284 for(i = 0; i < insn->use_start; ++i) {
285 be_operand_t *op = &insn->ops[i];
286 if(op->has_constraints)
287 bitset_or(def_constr, op->regs);
291 insert copies for all constrained arguments living through the node
292 and being constrained to a register which also occurs in out constraints.
294 for(i = insn->use_start; i < insn->n_ops; ++i) {
295 be_operand_t *op = &insn->ops[i];
297 bitset_copy(tmp, op->regs);
298 bitset_and(tmp, def_constr);
302 1) the operand is constrained.
303 2) lives through the node.
304 3) is constrained to a register occuring in out constraints.
306 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
308 only create the copy if the operand is no copy.
309 this is necessary since the assure constraints phase inserts
310 Copies and Keeps for operands which must be different from the results.
311 Additional copies here would destroy this.
313 if(!be_is_Copy(op->carrier)) {
314 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
316 sched_add_before(insn->irn, copy);
317 set_irn_n(insn->irn, op->pos, copy);
318 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
319 be_liveness_update(env->lv, op->carrier);
325 obstack_free(&env->obst, insn);
326 return insn->next_insn;
329 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
331 be_chordal_env_t *env = data;
333 for(irn = sched_first(bl); !sched_is_end(irn);) {
334 irn = prepare_constr_insn(env, irn);
338 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
339 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
342 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
344 const be_chordal_env_t *env = alloc_env->chordal_env;
346 int n_uses = be_insn_n_uses(insn);
347 int n_defs = be_insn_n_defs(insn);
348 bitset_t *bs = bitset_alloca(env->cls->n_regs);
349 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
354 For each out operand, try to find an in operand which can be assigned the
355 same register as the out operand.
357 for (j = 0; j < insn->use_start; ++j) {
359 int smallest_n_regs = 2 * env->cls->n_regs + 1;
360 be_operand_t *out_op = &insn->ops[j];
362 /* Try to find an in operand which has ... */
363 for(i = insn->use_start; i < insn->n_ops; ++i) {
365 const be_operand_t *op = &insn->ops[i];
367 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
368 bitset_clear_all(bs);
369 bitset_copy(bs, op->regs);
370 bitset_and(bs, out_op->regs);
371 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
373 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
375 smallest_n_regs = n_total;
381 be_operand_t *partner = &insn->ops[smallest];
382 out_op->partner = partner;
383 partner->partner = out_op;
389 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
391 be_chordal_env_t *env = alloc_env->chordal_env;
392 const arch_env_t *aenv = env->birg->main_env->arch_env;
393 be_insn_t *insn = *the_insn;
394 ir_node *bl = get_nodes_block(insn->irn);
395 ir_node *copy = NULL;
396 ir_node *perm = NULL;
397 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
398 bitset_t *bs = bitset_alloca(env->cls->n_regs);
399 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
403 assert(insn->has_constraints && "only do this for constrained nodes");
406 Collect all registers that occur in output constraints.
407 This is necessary, since if the insn has one of these as an input constraint
408 and the corresponding operand interferes with the insn, the operand must
411 for(i = 0; i < insn->use_start; ++i) {
412 be_operand_t *op = &insn->ops[i];
413 if(op->has_constraints)
414 bitset_or(out_constr, op->regs);
420 DEBUG_ONLY((void) dbg;)
423 Make the Perm, recompute liveness and re-scan the insn since the
424 in operands are now the Projs of the Perm.
426 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
428 /* Registers are propagated by insert_Perm_after(). Clean them here! */
430 const ir_edge_t *edge;
432 be_stat_ev("constr_perm", get_irn_arity(perm));
433 foreach_out_edge(perm, edge) {
434 ir_node *proj = get_edge_src_irn(edge);
435 arch_set_irn_register(aenv, proj, NULL);
439 We also have to re-build the insn since the input operands are now the Projs of
440 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
441 the live sets may change.
443 // be_liveness_recompute(env->lv);
444 obstack_free(&env->obst, insn);
445 *the_insn = insn = chordal_scan_insn(env, insn->irn);
448 Copy the input constraints of the insn to the Perm as output
449 constraints. Succeeding phases (coalescing will need that).
451 for(i = insn->use_start; i < insn->n_ops; ++i) {
452 be_operand_t *op = &insn->ops[i];
453 ir_node *proj = op->carrier;
455 Note that the predecessor must not be a Proj of the Perm,
456 since ignore-nodes are not Perm'ed.
458 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
459 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
467 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
469 be_chordal_env_t *env = alloc_env->chordal_env;
470 void *base = obstack_base(&env->obst);
471 be_insn_t *insn = chordal_scan_insn(env, irn);
472 ir_node *res = insn->next_insn;
473 int be_silent = *silent;
475 if(insn->pre_colored) {
477 for(i = 0; i < insn->use_start; ++i)
478 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
482 If the current node is a barrier toggle the silent flag.
483 If we are in the start block, we are ought to be silent at the beginning,
484 so the toggling activates the constraint handling but skips the barrier.
485 If we are in the end block we handle the in requirements of the barrier
486 and set the rest to silent.
488 if(be_is_Barrier(irn))
495 Perms inserted before the constraint handling phase are considered to be
496 correctly precolored. These Perms arise during the ABI handling phase.
498 if(insn->has_constraints) {
499 const arch_env_t *aenv = env->birg->main_env->arch_env;
500 int n_regs = env->cls->n_regs;
501 bitset_t *bs = bitset_alloca(n_regs);
502 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
503 bipartite_t *bp = bipartite_new(n_regs, n_regs);
504 int *assignment = alloca(n_regs * sizeof(assignment[0]));
505 pmap *partners = pmap_create();
506 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
510 const ir_edge_t *edge;
511 ir_node *perm = NULL;
514 prepare the constraint handling of this node.
515 Perms are constructed and Copies are created for constrained values
516 interfering with the instruction.
518 perm = pre_process_constraints(alloc_env, &insn);
520 /* find suitable in operands to the out operands of the node. */
521 pair_up_operands(alloc_env, insn);
524 look at the in/out operands and add each operand (and its possible partner)
525 to a bipartite graph (left: nodes with partners, right: admissible colors).
527 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
528 be_operand_t *op = &insn->ops[i];
531 If the operand has no partner or the partner has not been marked
532 for allocation, determine the admissible registers and mark it
533 for allocation by associating the node and its partner with the
534 set of admissible registers via a bipartite graph.
536 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
538 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
539 alloc_nodes[n_alloc] = op->carrier;
541 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
543 bitset_clear_all(bs);
544 get_decisive_partner_regs(bs, op, op->partner);
546 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
548 bitset_foreach(bs, col)
549 bipartite_add(bp, n_alloc, col);
556 Put all nodes which live through the constrained instruction also to the
557 allocation bipartite graph. They are considered unconstrained.
560 foreach_out_edge(perm, edge) {
561 ir_node *proj = get_edge_src_irn(edge);
563 assert(is_Proj(proj));
565 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
566 assert(n_alloc < n_regs);
567 alloc_nodes[n_alloc] = proj;
568 pmap_insert(partners, proj, NULL);
570 bitset_clear_all(bs);
571 arch_put_non_ignore_regs(aenv, env->cls, bs);
572 bitset_andnot(bs, env->ignore_colors);
573 bitset_foreach(bs, col)
574 bipartite_add(bp, n_alloc, col);
581 /* Compute a valid register allocation. */
582 bipartite_matching(bp, assignment);
584 /* Assign colors obtained from the matching. */
585 for(i = 0; i < n_alloc; ++i) {
586 const arch_register_t *reg;
590 assert(assignment[i] >= 0 && "there must have been a register assigned");
591 reg = arch_register_for_index(env->cls, assignment[i]);
593 nodes[0] = alloc_nodes[i];
594 nodes[1] = pmap_get(partners, alloc_nodes[i]);
596 for(j = 0; j < 2; ++j) {
600 arch_set_irn_register(aenv, nodes[j], reg);
601 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
602 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
607 /* Allocate the non-constrained Projs of the Perm. */
610 bitset_clear_all(bs);
612 /* Put the colors of all Projs in a bitset. */
613 foreach_out_edge(perm, edge) {
614 ir_node *proj = get_edge_src_irn(edge);
615 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
618 bitset_set(bs, reg->index);
621 /* Assign the not yet assigned Projs of the Perm a suitable color. */
622 foreach_out_edge(perm, edge) {
623 ir_node *proj = get_edge_src_irn(edge);
624 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
626 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
629 col = get_next_free_reg(alloc_env, bs);
630 reg = arch_register_for_index(env->cls, col);
631 bitset_set(bs, reg->index);
632 arch_set_irn_register(aenv, proj, reg);
633 pset_insert_ptr(alloc_env->pre_colored, proj);
634 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
640 pmap_destroy(partners);
644 obstack_free(&env->obst, base);
649 * Handle constraint nodes in each basic block.
650 * handle_constraints() inserts Perm nodes which perm
651 * over all values live at the constrained node right in front
652 * of the constrained node. These Perms signal a constrained node.
653 * For further comments, refer to handle_constraints().
655 static void constraints(ir_node *bl, void *data)
657 be_chordal_alloc_env_t *env = data;
660 Start silent in the start block.
661 The silence remains until the first barrier is seen.
662 Each other block is begun loud.
664 int silent = bl == get_irg_start_block(get_irn_irg(bl));
668 If the block is the start block search the barrier and
669 start handling constraints from there.
672 for(irn = sched_first(bl); !sched_is_end(irn);) {
673 irn = handle_constraints(env, irn, &silent);
678 * Annotate the register pressure to the nodes and compute
679 * the liveness intervals.
680 * @param block The block to do it for.
681 * @param env_ptr The environment.
683 static void pressure(ir_node *block, void *env_ptr)
685 /* Convenience macro for a def */
686 #define border_def(irn, step, real) \
687 border_add(env, head, irn, step, pressure--, 1, real)
689 /* Convenience macro for a use */
690 #define border_use(irn, step, real) \
691 border_add(env, head, irn, step, ++pressure, 0, real)
693 be_chordal_alloc_env_t *alloc_env = env_ptr;
694 be_chordal_env_t *env = alloc_env->chordal_env;
695 bitset_t *live = alloc_env->live;
697 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
701 unsigned pressure = 0;
702 struct list_head *head;
703 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
704 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
706 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
707 bitset_clear_all(live);
709 /* Set up the border list in the block info */
710 head = obstack_alloc(&env->obst, sizeof(*head));
711 INIT_LIST_HEAD(head);
712 assert(pmap_get(env->border_heads, block) == NULL);
713 pmap_insert(env->border_heads, block, head);
716 * Make final uses of all values live out of the block.
717 * They are necessary to build up real intervals.
719 foreach_pset(live_end, irn) {
720 if(has_reg_class(env, irn)) {
721 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
722 bitset_set(live, get_irn_idx(irn));
723 border_use(irn, step, 0);
729 * Determine the last uses of a value inside the block, since they are
730 * relevant for the interval borders.
732 sched_foreach_reverse(block, irn) {
733 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
734 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
737 * If the node defines some value, which can put into a
738 * register of the current class, make a border for it.
740 if(has_reg_class(env, irn)) {
741 int nr = get_irn_idx(irn);
743 bitset_clear(live, nr);
744 border_def(irn, step, 1);
748 * If the node is no phi node we can examine the uses.
751 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
752 ir_node *op = get_irn_n(irn, i);
754 if(has_reg_class(env, op)) {
755 int nr = get_irn_idx(op);
756 const char *msg = "-";
758 if(!bitset_is_set(live, nr)) {
759 border_use(op, step, 1);
760 bitset_set(live, nr);
764 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
772 * Add initial defs for all values live in.
774 foreach_pset(live_in, irn) {
775 if(has_reg_class(env, irn)) {
777 /* Mark the value live in. */
778 bitset_set(live, get_irn_idx(irn));
781 border_def(irn, step, 0);
789 static void assign(ir_node *block, void *env_ptr)
791 be_chordal_alloc_env_t *alloc_env = env_ptr;
792 be_chordal_env_t *env = alloc_env->chordal_env;
793 bitset_t *live = alloc_env->live;
794 bitset_t *colors = alloc_env->colors;
795 bitset_t *in_colors = alloc_env->in_colors;
796 const arch_env_t *arch_env = env->birg->main_env->arch_env;
797 struct list_head *head = get_block_border_head(env, block);
798 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
802 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
804 bitset_clear_all(colors);
805 bitset_clear_all(live);
806 bitset_clear_all(in_colors);
808 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
809 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
810 list_for_each_entry(border_t, b, head, list) {
811 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
812 b->irn, get_irn_idx(b->irn)));
816 * Add initial defs for all values live in.
817 * Since their colors have already been assigned (The dominators were
818 * allocated before), we have to mark their colors as used also.
820 foreach_pset(live_in, irn) {
821 if(has_reg_class(env, irn)) {
822 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
825 assert(reg && "Node must have been assigned a register");
826 col = arch_register_get_index(reg);
828 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
830 /* Mark the color of the live in value as used. */
831 bitset_set(colors, col);
832 bitset_set(in_colors, col);
834 /* Mark the value live in. */
835 bitset_set(live, get_irn_idx(irn));
840 * Mind that the sequence
841 * of defs from back to front defines a perfect
842 * elimination order. So, coloring the definitions from first to last
845 list_for_each_entry_reverse(border_t, b, head, list) {
846 ir_node *irn = b->irn;
847 int nr = get_irn_idx(irn);
848 int ignore = arch_irn_is(arch_env, irn, ignore);
851 * Assign a color, if it is a local def. Global defs already have a
854 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
855 const arch_register_t *reg;
858 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
859 reg = arch_get_irn_register(arch_env, irn);
861 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
865 col = get_next_free_reg(alloc_env, colors);
866 reg = arch_register_for_index(env->cls, col);
867 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
868 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
871 bitset_set(colors, col);
872 arch_set_irn_register(arch_env, irn, reg);
874 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
876 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
877 bitset_set(live, nr);
880 /* Clear the color upon a use. */
881 else if(!b->is_def) {
882 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
885 assert(reg && "Register must have been assigned");
887 col = arch_register_get_index(reg);
888 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
890 bitset_clear(colors, col);
891 bitset_clear(live, nr);
898 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
900 be_chordal_alloc_env_t env;
903 int colors_n = arch_register_class_n_regs(chordal_env->cls);
904 ir_graph *irg = chordal_env->irg;
909 env.chordal_env = chordal_env;
910 env.colors_n = colors_n;
911 env.colors = bitset_alloca(colors_n);
912 env.tmp_colors = bitset_alloca(colors_n);
913 env.in_colors = bitset_alloca(colors_n);
914 env.pre_colored = pset_new_ptr_default();
915 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
918 /* Handle register targeting constraints */
919 dom_tree_walk_irg(irg, constraints, NULL, &env);
921 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
922 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
923 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
926 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
928 /* First, determine the pressure */
929 dom_tree_walk_irg(irg, pressure, NULL, &env);
931 /* Assign the colors */
932 dom_tree_walk_irg(irg, assign, NULL, &env);
934 be_numbering_done(irg);
936 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
938 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
939 plotter = new_plotter_ps(buf);
940 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
941 plotter_free(plotter);
944 bitset_free(env.live);
945 del_pset(env.pre_colored);