2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
28 #include "raw_bitset.h"
30 #include "bipartite.h"
31 #include "hungarian.h"
34 #include "irgraph_t.h"
35 #include "irprintf_t.h"
45 #include "besched_t.h"
52 #include "bestatevent.h"
55 #include "bechordal_t.h"
56 #include "bechordal_draw.h"
58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
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 } be_chordal_alloc_env_t;
77 /* Make a fourcc for border checking. */
78 #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 DEBUG_ONLY(b->magic = BORDER_FOURCC);
136 DEBUG_ONLY(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->birg->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->chordal_env->ignore_colors);
182 return bitset_next_clear(tmp, 0);
185 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
190 bitset_copy(bs, o2->regs);
195 bitset_copy(bs, o1->regs);
199 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
201 if(bitset_contains(o1->regs, o2->regs))
202 bitset_copy(bs, o1->regs);
203 else if(bitset_contains(o2->regs, o1->regs))
204 bitset_copy(bs, o2->regs);
211 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
215 ie.ignore_colors = env->ignore_colors;
216 ie.aenv = env->birg->main_env->arch_env;
217 ie.obst = &env->obst;
219 return be_scan_insn(&ie, irn);
222 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
224 const arch_env_t *aenv = env->birg->main_env->arch_env;
225 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
226 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
227 ir_node *bl = get_nodes_block(irn);
228 be_lv_t *lv = env->birg->lv;
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 const arch_register_req_t *req;
239 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
242 reg = arch_get_irn_register(aenv, op);
244 if (reg == NULL || !arch_register_type_is(reg, ignore))
246 if(arch_register_type_is(reg, joker))
249 req = arch_get_register_req(aenv, irn, i);
250 if (!arch_register_req_is(req, limited))
253 if (rbitset_is_set(req->limited, reg->index))
256 copy = be_new_Copy(env->cls, env->irg, bl, op);
257 be_stat_ev("constr_copy", 1);
259 sched_add_before(irn, copy);
260 set_irn_n(irn, i, copy);
261 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
264 insn = chordal_scan_insn(env, irn);
266 if(!insn->has_constraints)
269 /* insert copies for nodes that occur constrained more than once. */
270 for(i = insn->use_start; i < insn->n_ops; ++i) {
271 be_operand_t *op = &insn->ops[i];
273 if(!op->has_constraints)
276 for(j = i + 1; j < insn->n_ops; ++j) {
278 be_operand_t *a_op = &insn->ops[j];
280 if(a_op->carrier != op->carrier || !a_op->has_constraints)
283 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
284 be_stat_ev("constr_copy", 1);
286 sched_add_before(insn->irn, copy);
287 set_irn_n(insn->irn, a_op->pos, copy);
288 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
292 /* collect all registers occuring in out constraints. */
293 for(i = 0; i < insn->use_start; ++i) {
294 be_operand_t *op = &insn->ops[i];
295 if(op->has_constraints)
296 bitset_or(def_constr, op->regs);
300 insert copies for all constrained arguments living through the node
301 and being constrained to a register which also occurs in out constraints.
303 for(i = insn->use_start; i < insn->n_ops; ++i) {
305 be_operand_t *op = &insn->ops[i];
307 bitset_copy(tmp, op->regs);
308 bitset_and(tmp, def_constr);
312 1) the operand is constrained.
313 2) lives through the node.
314 3) is constrained to a register occuring in out constraints.
316 if(!op->has_constraints ||
317 !values_interfere(lv, insn->irn, op->carrier) ||
318 bitset_popcnt(tmp) == 0)
322 only create the copy if the operand is no copy.
323 this is necessary since the assure constraints phase inserts
324 Copies and Keeps for operands which must be different from the results.
325 Additional copies here would destroy this.
327 if(be_is_Copy(op->carrier))
330 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
332 sched_add_before(insn->irn, copy);
333 set_irn_n(insn->irn, op->pos, copy);
334 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
335 be_liveness_update(lv, op->carrier);
339 obstack_free(&env->obst, insn);
340 return insn->next_insn;
343 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
345 be_chordal_env_t *env = data;
347 for(irn = sched_first(bl); !sched_is_end(irn);) {
348 irn = prepare_constr_insn(env, irn);
352 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
353 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
356 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
358 const be_chordal_env_t *env = alloc_env->chordal_env;
360 int n_uses = be_insn_n_uses(insn);
361 int n_defs = be_insn_n_defs(insn);
362 bitset_t *bs = bitset_alloca(env->cls->n_regs);
363 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
364 be_lv_t *lv = env->birg->lv;
369 For each out operand, try to find an in operand which can be assigned the
370 same register as the out operand.
372 for (j = 0; j < insn->use_start; ++j) {
374 int smallest_n_regs = 2 * env->cls->n_regs + 1;
375 be_operand_t *out_op = &insn->ops[j];
377 /* Try to find an in operand which has ... */
378 for(i = insn->use_start; i < insn->n_ops; ++i) {
380 const be_operand_t *op = &insn->ops[i];
382 if (op->partner != NULL)
384 if (values_interfere(lv, op->irn, op->carrier))
387 bitset_clear_all(bs);
388 bitset_copy(bs, op->regs);
389 bitset_and(bs, out_op->regs);
390 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
392 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
394 smallest_n_regs = n_total;
399 be_operand_t *partner = &insn->ops[smallest];
400 out_op->partner = partner;
401 partner->partner = out_op;
407 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
408 be_insn_t **the_insn)
410 be_chordal_env_t *env = alloc_env->chordal_env;
411 const arch_env_t *aenv = env->birg->main_env->arch_env;
412 be_insn_t *insn = *the_insn;
413 ir_node *perm = NULL;
414 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
415 const ir_edge_t *edge;
418 assert(insn->has_constraints && "only do this for constrained nodes");
421 Collect all registers that occur in output constraints.
422 This is necessary, since if the insn has one of these as an input constraint
423 and the corresponding operand interferes with the insn, the operand must
426 for(i = 0; i < insn->use_start; ++i) {
427 be_operand_t *op = &insn->ops[i];
428 if(op->has_constraints)
429 bitset_or(out_constr, op->regs);
433 Make the Perm, recompute liveness and re-scan the insn since the
434 in operands are now the Projs of the Perm.
436 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
438 /* Registers are propagated by insert_Perm_after(). Clean them here! */
442 be_stat_ev("constr_perm", get_irn_arity(perm));
443 foreach_out_edge(perm, edge) {
444 ir_node *proj = get_edge_src_irn(edge);
445 arch_set_irn_register(aenv, proj, NULL);
449 We also have to re-build the insn since the input operands are now the Projs of
450 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
451 the live sets may change.
453 // be_liveness_recompute(lv);
454 obstack_free(&env->obst, insn);
455 *the_insn = insn = chordal_scan_insn(env, insn->irn);
458 Copy the input constraints of the insn to the Perm as output
459 constraints. Succeeding phases (coalescing) will need that.
461 for(i = insn->use_start; i < insn->n_ops; ++i) {
462 be_operand_t *op = &insn->ops[i];
463 ir_node *proj = op->carrier;
465 Note that the predecessor must not be a Proj of the Perm,
466 since ignore-nodes are not Perm'ed.
468 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
469 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
476 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
478 const arch_env_t *aenv;
481 ir_node **alloc_nodes;
482 hungarian_problem_t *bp;
487 const ir_edge_t *edge;
488 ir_node *perm = NULL;
490 be_chordal_env_t *env = alloc_env->chordal_env;
491 void *base = obstack_base(&env->obst);
492 be_insn_t *insn = chordal_scan_insn(env, irn);
493 ir_node *res = insn->next_insn;
494 int be_silent = *silent;
495 be_lv_t *lv = env->birg->lv;
497 if(insn->pre_colored) {
499 for(i = 0; i < insn->use_start; ++i)
500 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
504 If the current node is a barrier toggle the silent flag.
505 If we are in the start block, we are ought to be silent at the beginning,
506 so the toggling activates the constraint handling but skips the barrier.
507 If we are in the end block we handle the in requirements of the barrier
508 and set the rest to silent.
510 if(be_is_Barrier(irn))
517 Perms inserted before the constraint handling phase are considered to be
518 correctly precolored. These Perms arise during the ABI handling phase.
520 if(!insn->has_constraints)
523 aenv = env->birg->main_env->arch_env;
524 n_regs = env->cls->n_regs;
525 bs = bitset_alloca(n_regs);
526 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
527 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
528 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
529 assignment = alloca(n_regs * sizeof(assignment[0]));
530 partners = pmap_create();
533 prepare the constraint handling of this node.
534 Perms are constructed and Copies are created for constrained values
535 interfering with the instruction.
537 perm = pre_process_constraints(alloc_env, &insn);
539 /* find suitable in operands to the out operands of the node. */
540 pair_up_operands(alloc_env, insn);
543 look at the in/out operands and add each operand (and its possible partner)
544 to a bipartite graph (left: nodes with partners, right: admissible colors).
546 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
547 be_operand_t *op = &insn->ops[i];
550 If the operand has no partner or the partner has not been marked
551 for allocation, determine the admissible registers and mark it
552 for allocation by associating the node and its partner with the
553 set of admissible registers via a bipartite graph.
555 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
557 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
558 alloc_nodes[n_alloc] = op->carrier;
560 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
562 bitset_clear_all(bs);
563 get_decisive_partner_regs(bs, op, op->partner);
565 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
567 bitset_foreach(bs, col) {
568 hungarian_add(bp, n_alloc, col, 1);
569 // bipartite_add(bp, n_alloc, col);
577 Put all nodes which live through the constrained instruction also to the
578 allocation bipartite graph. They are considered unconstrained.
581 foreach_out_edge(perm, edge) {
582 ir_node *proj = get_edge_src_irn(edge);
584 assert(is_Proj(proj));
586 if(!values_interfere(lv, proj, irn) || pmap_contains(partners, proj))
589 assert(n_alloc < n_regs);
590 alloc_nodes[n_alloc] = proj;
591 pmap_insert(partners, proj, NULL);
593 bitset_clear_all(bs);
594 arch_put_non_ignore_regs(aenv, env->cls, bs);
595 bitset_andnot(bs, env->ignore_colors);
596 bitset_foreach(bs, col) {
597 hungarian_add(bp, n_alloc, col, 1);
598 // bipartite_add(bp, n_alloc, col);
605 /* Compute a valid register allocation. */
606 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
607 match_res = hungarian_solve(bp, assignment, &cost, 1);
608 assert(match_res == 0 && "matching failed");
609 //bipartite_matching(bp, assignment);
611 /* Assign colors obtained from the matching. */
612 for(i = 0; i < n_alloc; ++i) {
613 const arch_register_t *reg;
617 assert(assignment[i] >= 0 && "there must have been a register assigned");
618 reg = arch_register_for_index(env->cls, assignment[i]);
620 nodes[0] = alloc_nodes[i];
621 nodes[1] = pmap_get(partners, alloc_nodes[i]);
623 for(j = 0; j < 2; ++j) {
627 arch_set_irn_register(aenv, nodes[j], reg);
628 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
629 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
633 /* Allocate the non-constrained Projs of the Perm. */
635 bitset_clear_all(bs);
637 /* Put the colors of all Projs in a bitset. */
638 foreach_out_edge(perm, edge) {
639 ir_node *proj = get_edge_src_irn(edge);
640 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
643 bitset_set(bs, reg->index);
646 /* Assign the not yet assigned Projs of the Perm a suitable color. */
647 foreach_out_edge(perm, edge) {
648 ir_node *proj = get_edge_src_irn(edge);
649 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
651 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
654 col = get_next_free_reg(alloc_env, bs);
655 reg = arch_register_for_index(env->cls, col);
656 bitset_set(bs, reg->index);
657 arch_set_irn_register(aenv, proj, reg);
658 pset_insert_ptr(alloc_env->pre_colored, proj);
659 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
664 //bipartite_free(bp);
666 pmap_destroy(partners);
669 obstack_free(&env->obst, base);
674 * Handle constraint nodes in each basic block.
675 * handle_constraints() inserts Perm nodes which perm
676 * over all values live at the constrained node right in front
677 * of the constrained node. These Perms signal a constrained node.
678 * For further comments, refer to handle_constraints().
680 static void constraints(ir_node *bl, void *data)
682 be_chordal_alloc_env_t *env = data;
685 Start silent in the start block.
686 The silence remains until the first barrier is seen.
687 Each other block is begun loud.
689 int silent = bl == get_irg_start_block(get_irn_irg(bl));
693 If the block is the start block search the barrier and
694 start handling constraints from there.
697 for(irn = sched_first(bl); !sched_is_end(irn);) {
698 irn = handle_constraints(env, irn, &silent);
703 * Annotate the register pressure to the nodes and compute
704 * the liveness intervals.
705 * @param block The block to do it for.
706 * @param env_ptr The environment.
708 static void pressure(ir_node *block, void *env_ptr)
710 /* Convenience macro for a def */
711 #define border_def(irn, step, real) \
712 border_add(env, head, irn, step, pressure--, 1, real)
714 /* Convenience macro for a use */
715 #define border_use(irn, step, real) \
716 border_add(env, head, irn, step, ++pressure, 0, real)
718 be_chordal_alloc_env_t *alloc_env = env_ptr;
719 be_chordal_env_t *env = alloc_env->chordal_env;
720 bitset_t *live = alloc_env->live;
722 be_lv_t *lv = env->birg->lv;
726 unsigned pressure = 0;
727 struct list_head *head;
728 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
729 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
731 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
732 bitset_clear_all(live);
734 /* Set up the border list in the block info */
735 head = obstack_alloc(&env->obst, sizeof(*head));
736 INIT_LIST_HEAD(head);
737 assert(pmap_get(env->border_heads, block) == NULL);
738 pmap_insert(env->border_heads, block, head);
741 * Make final uses of all values live out of the block.
742 * They are necessary to build up real intervals.
744 foreach_pset(live_end, irn) {
745 if(has_reg_class(env, irn)) {
746 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
747 bitset_set(live, get_irn_idx(irn));
748 border_use(irn, step, 0);
754 * Determine the last uses of a value inside the block, since they are
755 * relevant for the interval borders.
757 sched_foreach_reverse(block, irn) {
758 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
759 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
762 * If the node defines some value, which can put into a
763 * register of the current class, make a border for it.
765 if(has_reg_class(env, irn)) {
766 int nr = get_irn_idx(irn);
768 bitset_clear(live, nr);
769 border_def(irn, step, 1);
773 * If the node is no phi node we can examine the uses.
776 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
777 ir_node *op = get_irn_n(irn, i);
779 if(has_reg_class(env, op)) {
780 int nr = get_irn_idx(op);
781 const char *msg = "-";
783 if(!bitset_is_set(live, nr)) {
784 border_use(op, step, 1);
785 bitset_set(live, nr);
789 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
797 * Add initial defs for all values live in.
799 foreach_pset(live_in, irn) {
800 if(has_reg_class(env, irn)) {
802 /* Mark the value live in. */
803 bitset_set(live, get_irn_idx(irn));
806 border_def(irn, step, 0);
814 static void assign(ir_node *block, void *env_ptr)
816 be_chordal_alloc_env_t *alloc_env = env_ptr;
817 be_chordal_env_t *env = alloc_env->chordal_env;
818 bitset_t *live = alloc_env->live;
819 bitset_t *colors = alloc_env->colors;
820 bitset_t *in_colors = alloc_env->in_colors;
821 const arch_env_t *arch_env = env->birg->main_env->arch_env;
822 struct list_head *head = get_block_border_head(env, block);
823 be_lv_t *lv = env->birg->lv;
824 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
829 bitset_clear_all(colors);
830 bitset_clear_all(live);
831 bitset_clear_all(in_colors);
833 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
834 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
835 list_for_each_entry(border_t, b, head, list) {
836 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
837 b->irn, get_irn_idx(b->irn)));
841 * Add initial defs for all values live in.
842 * Since their colors have already been assigned (The dominators were
843 * allocated before), we have to mark their colors as used also.
845 foreach_pset(live_in, irn) {
846 if(has_reg_class(env, irn)) {
847 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
850 assert(reg && "Node must have been assigned a register");
851 col = arch_register_get_index(reg);
853 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
855 /* Mark the color of the live in value as used. */
856 bitset_set(colors, col);
857 bitset_set(in_colors, col);
859 /* Mark the value live in. */
860 bitset_set(live, get_irn_idx(irn));
865 * Mind that the sequence of defs from back to front defines a perfect
866 * elimination order. So, coloring the definitions from first to last
869 list_for_each_entry_reverse(border_t, b, head, list) {
870 ir_node *irn = b->irn;
871 int nr = get_irn_idx(irn);
872 int ignore = arch_irn_is(arch_env, irn, ignore);
875 * Assign a color, if it is a local def. Global defs already have a
878 if(b->is_def && !be_is_live_in(lv, block, irn)) {
879 const arch_register_t *reg;
882 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
883 reg = arch_get_irn_register(arch_env, irn);
885 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
887 col = get_next_free_reg(alloc_env, colors);
888 reg = arch_register_for_index(env->cls, col);
889 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
890 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
893 bitset_set(colors, col);
894 arch_set_irn_register(arch_env, irn, reg);
896 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
898 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
899 bitset_set(live, nr);
902 /* Clear the color upon a use. */
903 else if(!b->is_def) {
904 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
907 assert(reg && "Register must have been assigned");
909 col = arch_register_get_index(reg);
911 if(!arch_register_type_is(reg, ignore)) {
912 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
916 bitset_clear(colors, col);
917 bitset_clear(live, nr);
924 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
926 be_chordal_alloc_env_t env;
928 be_irg_t *birg = chordal_env->birg;
929 const arch_register_class_t *cls = chordal_env->cls;
931 int colors_n = arch_register_class_n_regs(cls);
932 ir_graph *irg = chordal_env->irg;
933 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
935 /* some special classes contain only ignore regs, no work to be done */
936 if(allocatable_regs == 0)
939 be_assure_dom_front(birg);
940 be_assure_liveness(birg);
943 env.chordal_env = chordal_env;
944 env.colors_n = colors_n;
945 env.colors = bitset_alloca(colors_n);
946 env.tmp_colors = bitset_alloca(colors_n);
947 env.in_colors = bitset_alloca(colors_n);
948 env.pre_colored = pset_new_ptr_default();
950 /* Handle register targeting constraints */
951 dom_tree_walk_irg(irg, constraints, NULL, &env);
953 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
954 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
955 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
958 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
960 /* First, determine the pressure */
961 dom_tree_walk_irg(irg, pressure, NULL, &env);
963 /* Assign the colors */
964 dom_tree_walk_irg(irg, assign, NULL, &env);
966 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
968 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
969 plotter = new_plotter_ps(buf);
970 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
971 plotter_free(plotter);
974 bitset_free(env.live);
975 del_pset(env.pre_colored);
978 void be_init_chordal(void)
980 FIRM_DBG_REGISTER(dbg, "firm.be.chordal.constr");
983 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);