2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
29 #include "bipartite.h"
30 #include "hungarian.h"
33 #include "irgraph_t.h"
34 #include "irprintf_t.h"
44 #include "besched_t.h"
51 #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 DEBUG_ONLY(b->magic = BORDER_FOURCC);
137 DEBUG_ONLY(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);
229 be_lv_t *lv = env->birg->lv;
234 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
235 ir_node *op = get_irn_n(irn, i);
237 const arch_register_t *reg;
238 arch_register_req_t req;
240 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
243 reg = arch_get_irn_register(aenv, op);
245 if (reg == NULL || !arch_register_type_is(reg, ignore))
247 if(arch_register_type_is(reg, joker))
250 arch_get_register_req(aenv, &req, irn, i);
252 if (!arch_register_req_is(&req, limited))
255 bitset_clear_all(tmp);
256 req.limited(req.limited_env, tmp);
258 if (bitset_is_set(tmp, reg->index))
261 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
262 be_stat_ev("constr_copy", 1);
264 sched_add_before(irn, copy);
265 set_irn_n(irn, i, copy);
266 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
269 insn = chordal_scan_insn(env, irn);
271 if(!insn->has_constraints)
274 /* insert copies for nodes that occur constrained more than once. */
275 for(i = insn->use_start; i < insn->n_ops; ++i) {
276 be_operand_t *op = &insn->ops[i];
278 if(op->has_constraints) {
279 for(j = i + 1; j < insn->n_ops; ++j) {
280 be_operand_t *a_op = &insn->ops[j];
282 if(a_op->carrier == op->carrier && a_op->has_constraints) {
283 ir_node *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));
294 /* collect all registers occuring in out constraints. */
295 for(i = 0; i < insn->use_start; ++i) {
296 be_operand_t *op = &insn->ops[i];
297 if(op->has_constraints)
298 bitset_or(def_constr, op->regs);
302 insert copies for all constrained arguments living through the node
303 and being constrained to a register which also occurs in out constraints.
305 for(i = insn->use_start; i < insn->n_ops; ++i) {
306 be_operand_t *op = &insn->ops[i];
308 bitset_copy(tmp, op->regs);
309 bitset_and(tmp, def_constr);
313 1) the operand is constrained.
314 2) lives through the node.
315 3) is constrained to a register occuring in out constraints.
317 if(!op->has_constraints ||
318 !values_interfere(lv, insn->irn, op->carrier) ||
319 bitset_popcnt(tmp) == 0)
323 only create the copy if the operand is no copy.
324 this is necessary since the assure constraints phase inserts
325 Copies and Keeps for operands which must be different from the results.
326 Additional copies here would destroy this.
328 if(!be_is_Copy(op->carrier)) {
329 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
331 sched_add_before(insn->irn, copy);
332 set_irn_n(insn->irn, op->pos, copy);
333 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
334 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 (! values_interfere(lv, op->irn, op->carrier) && ! op->partner) {
383 bitset_clear_all(bs);
384 bitset_copy(bs, op->regs);
385 bitset_and(bs, out_op->regs);
386 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
388 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
390 smallest_n_regs = n_total;
396 be_operand_t *partner = &insn->ops[smallest];
397 out_op->partner = partner;
398 partner->partner = out_op;
404 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
406 be_chordal_env_t *env = alloc_env->chordal_env;
407 const arch_env_t *aenv = env->birg->main_env->arch_env;
408 be_insn_t *insn = *the_insn;
409 ir_node *bl = get_nodes_block(insn->irn);
410 ir_node *copy = NULL;
411 ir_node *perm = NULL;
412 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
413 bitset_t *bs = bitset_alloca(env->cls->n_regs);
414 be_lv_t *lv = env->birg->lv;
415 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
419 assert(insn->has_constraints && "only do this for constrained nodes");
422 Collect all registers that occur in output constraints.
423 This is necessary, since if the insn has one of these as an input constraint
424 and the corresponding operand interferes with the insn, the operand must
427 for(i = 0; i < insn->use_start; ++i) {
428 be_operand_t *op = &insn->ops[i];
429 if(op->has_constraints)
430 bitset_or(out_constr, op->regs);
436 DEBUG_ONLY((void) dbg;)
439 Make the Perm, recompute liveness and re-scan the insn since the
440 in operands are now the Projs of the Perm.
442 perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
444 /* Registers are propagated by insert_Perm_after(). Clean them here! */
446 const ir_edge_t *edge;
448 be_stat_ev("constr_perm", get_irn_arity(perm));
449 foreach_out_edge(perm, edge) {
450 ir_node *proj = get_edge_src_irn(edge);
451 arch_set_irn_register(aenv, proj, NULL);
455 We also have to re-build the insn since the input operands are now the Projs of
456 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
457 the live sets may change.
459 // be_liveness_recompute(lv);
460 obstack_free(&env->obst, insn);
461 *the_insn = insn = chordal_scan_insn(env, insn->irn);
464 Copy the input constraints of the insn to the Perm as output
465 constraints. Succeeding phases (coalescing will need that).
467 for(i = insn->use_start; i < insn->n_ops; ++i) {
468 be_operand_t *op = &insn->ops[i];
469 ir_node *proj = op->carrier;
471 Note that the predecessor must not be a Proj of the Perm,
472 since ignore-nodes are not Perm'ed.
474 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
475 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
483 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
485 be_chordal_env_t *env = alloc_env->chordal_env;
486 void *base = obstack_base(&env->obst);
487 be_insn_t *insn = chordal_scan_insn(env, irn);
488 ir_node *res = insn->next_insn;
489 int be_silent = *silent;
490 be_lv_t *lv = env->birg->lv;
492 if(insn->pre_colored) {
494 for(i = 0; i < insn->use_start; ++i)
495 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
499 If the current node is a barrier toggle the silent flag.
500 If we are in the start block, we are ought to be silent at the beginning,
501 so the toggling activates the constraint handling but skips the barrier.
502 If we are in the end block we handle the in requirements of the barrier
503 and set the rest to silent.
505 if(be_is_Barrier(irn))
512 Perms inserted before the constraint handling phase are considered to be
513 correctly precolored. These Perms arise during the ABI handling phase.
515 if(insn->has_constraints) {
516 const arch_env_t *aenv = env->birg->main_env->arch_env;
517 int n_regs = env->cls->n_regs;
518 bitset_t *bs = bitset_alloca(n_regs);
519 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
520 hungarian_problem_t *bp= hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
521 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
522 int *assignment = alloca(n_regs * sizeof(assignment[0]));
523 pmap *partners = pmap_create();
524 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
528 const ir_edge_t *edge;
529 ir_node *perm = NULL;
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);
576 Put all nodes which live through the constrained instruction also to the
577 allocation bipartite graph. They are considered unconstrained.
580 foreach_out_edge(perm, edge) {
581 ir_node *proj = get_edge_src_irn(edge);
583 assert(is_Proj(proj));
585 if(values_interfere(lv, proj, irn) && !pmap_contains(partners, proj)) {
586 assert(n_alloc < n_regs);
587 alloc_nodes[n_alloc] = proj;
588 pmap_insert(partners, proj, NULL);
590 bitset_clear_all(bs);
591 arch_put_non_ignore_regs(aenv, env->cls, bs);
592 bitset_andnot(bs, env->ignore_colors);
593 bitset_foreach(bs, col)
594 hungarian_add(bp, n_alloc, col, 1);
595 // bipartite_add(bp, n_alloc, col);
602 /* Compute a valid register allocation. */
603 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
604 match_res = hungarian_solve(bp, assignment, &cost, 1);
605 assert(match_res == 0 && "matching failed");
606 //bipartite_matching(bp, assignment);
608 /* Assign colors obtained from the matching. */
609 for(i = 0; i < n_alloc; ++i) {
610 const arch_register_t *reg;
614 assert(assignment[i] >= 0 && "there must have been a register assigned");
615 reg = arch_register_for_index(env->cls, assignment[i]);
617 nodes[0] = alloc_nodes[i];
618 nodes[1] = pmap_get(partners, alloc_nodes[i]);
620 for(j = 0; j < 2; ++j) {
624 arch_set_irn_register(aenv, nodes[j], reg);
625 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
626 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
631 /* Allocate the non-constrained Projs of the Perm. */
634 bitset_clear_all(bs);
636 /* Put the colors of all Projs in a bitset. */
637 foreach_out_edge(perm, edge) {
638 ir_node *proj = get_edge_src_irn(edge);
639 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
642 bitset_set(bs, reg->index);
645 /* Assign the not yet assigned Projs of the Perm a suitable color. */
646 foreach_out_edge(perm, edge) {
647 ir_node *proj = get_edge_src_irn(edge);
648 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
650 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
653 col = get_next_free_reg(alloc_env, bs);
654 reg = arch_register_for_index(env->cls, col);
655 bitset_set(bs, reg->index);
656 arch_set_irn_register(aenv, proj, reg);
657 pset_insert_ptr(alloc_env->pre_colored, proj);
658 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
663 //bipartite_free(bp);
665 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;
723 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
727 unsigned pressure = 0;
728 struct list_head *head;
729 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
730 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
732 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
733 bitset_clear_all(live);
735 /* Set up the border list in the block info */
736 head = obstack_alloc(&env->obst, sizeof(*head));
737 INIT_LIST_HEAD(head);
738 assert(pmap_get(env->border_heads, block) == NULL);
739 pmap_insert(env->border_heads, block, head);
742 * Make final uses of all values live out of the block.
743 * They are necessary to build up real intervals.
745 foreach_pset(live_end, irn) {
746 if(has_reg_class(env, irn)) {
747 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
748 bitset_set(live, get_irn_idx(irn));
749 border_use(irn, step, 0);
755 * Determine the last uses of a value inside the block, since they are
756 * relevant for the interval borders.
758 sched_foreach_reverse(block, irn) {
759 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
760 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
763 * If the node defines some value, which can put into a
764 * register of the current class, make a border for it.
766 if(has_reg_class(env, irn)) {
767 int nr = get_irn_idx(irn);
769 bitset_clear(live, nr);
770 border_def(irn, step, 1);
774 * If the node is no phi node we can examine the uses.
777 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
778 ir_node *op = get_irn_n(irn, i);
780 if(has_reg_class(env, op)) {
781 int nr = get_irn_idx(op);
782 const char *msg = "-";
784 if(!bitset_is_set(live, nr)) {
785 border_use(op, step, 1);
786 bitset_set(live, nr);
790 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
798 * Add initial defs for all values live in.
800 foreach_pset(live_in, irn) {
801 if(has_reg_class(env, irn)) {
803 /* Mark the value live in. */
804 bitset_set(live, get_irn_idx(irn));
807 border_def(irn, step, 0);
815 static void assign(ir_node *block, void *env_ptr)
817 be_chordal_alloc_env_t *alloc_env = env_ptr;
818 be_chordal_env_t *env = alloc_env->chordal_env;
819 bitset_t *live = alloc_env->live;
820 bitset_t *colors = alloc_env->colors;
821 bitset_t *in_colors = alloc_env->in_colors;
822 const arch_env_t *arch_env = env->birg->main_env->arch_env;
823 struct list_head *head = get_block_border_head(env, block);
824 be_lv_t *lv = env->birg->lv;
825 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
829 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
831 bitset_clear_all(colors);
832 bitset_clear_all(live);
833 bitset_clear_all(in_colors);
835 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
836 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
837 list_for_each_entry(border_t, b, head, list) {
838 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
839 b->irn, get_irn_idx(b->irn)));
843 * Add initial defs for all values live in.
844 * Since their colors have already been assigned (The dominators were
845 * allocated before), we have to mark their colors as used also.
847 foreach_pset(live_in, irn) {
848 if(has_reg_class(env, irn)) {
849 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
852 assert(reg && "Node must have been assigned a register");
853 col = arch_register_get_index(reg);
855 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
857 /* Mark the color of the live in value as used. */
858 bitset_set(colors, col);
859 bitset_set(in_colors, col);
861 /* Mark the value live in. */
862 bitset_set(live, get_irn_idx(irn));
867 * Mind that the sequence of defs from back to front defines a perfect
868 * elimination order. So, coloring the definitions from first to last
871 list_for_each_entry_reverse(border_t, b, head, list) {
872 ir_node *irn = b->irn;
873 int nr = get_irn_idx(irn);
874 int ignore = arch_irn_is(arch_env, irn, ignore);
877 * Assign a color, if it is a local def. Global defs already have a
880 if(b->is_def && !be_is_live_in(lv, block, irn)) {
881 const arch_register_t *reg;
884 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
885 reg = arch_get_irn_register(arch_env, irn);
887 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
891 col = get_next_free_reg(alloc_env, colors);
892 reg = arch_register_for_index(env->cls, col);
893 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
894 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
897 bitset_set(colors, col);
898 arch_set_irn_register(arch_env, irn, reg);
900 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
902 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
903 bitset_set(live, nr);
906 /* Clear the color upon a use. */
907 else if(!b->is_def) {
908 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
911 assert(reg && "Register must have been assigned");
913 col = arch_register_get_index(reg);
914 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;
930 int colors_n = arch_register_class_n_regs(chordal_env->cls);
931 ir_graph *irg = chordal_env->irg;
934 be_assure_dom_front(birg);
935 be_assure_liveness(birg);
938 env.chordal_env = chordal_env;
939 env.colors_n = colors_n;
940 env.colors = bitset_alloca(colors_n);
941 env.tmp_colors = bitset_alloca(colors_n);
942 env.in_colors = bitset_alloca(colors_n);
943 env.pre_colored = pset_new_ptr_default();
944 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
947 /* Handle register targeting constraints */
948 dom_tree_walk_irg(irg, constraints, NULL, &env);
950 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
951 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
952 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
955 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
957 /* First, determine the pressure */
958 dom_tree_walk_irg(irg, pressure, NULL, &env);
960 /* Assign the colors */
961 dom_tree_walk_irg(irg, assign, NULL, &env);
963 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
965 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
966 plotter = new_plotter_ps(buf);
967 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
968 plotter_free(plotter);
971 bitset_free(env.live);
972 del_pset(env.pre_colored);