2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
20 #include "raw_bitset.h"
22 #include "bipartite.h"
23 #include "hungarian.h"
26 #include "irgraph_t.h"
27 #include "irprintf_t.h"
37 #include "besched_t.h"
44 #include "bestatevent.h"
47 #include "bechordal_t.h"
48 #include "bechordal_draw.h"
50 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
54 #define DUMP_INTERVALS
56 typedef struct _be_chordal_alloc_env_t {
57 be_chordal_env_t *chordal_env;
59 pset *pre_colored; /**< Set of precolored nodes. */
60 bitset_t *live; /**< A liveness bitset. */
61 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
62 bitset_t *colors; /**< The color mask. */
63 bitset_t *in_colors; /**< Colors used by live in values. */
64 int colors_n; /**< The number of colors. */
65 } be_chordal_alloc_env_t;
69 /* Make a fourcc for border checking. */
70 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
73 static void check_border_list(struct list_head *head)
76 list_for_each_entry(border_t, x, head, list) {
77 assert(x->magic == BORDER_FOURCC);
81 static void check_heads(be_chordal_env_t *env)
84 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
85 /* ir_printf("checking border list of block %+F\n", ent->key); */
86 check_border_list(ent->value);
92 * Add an interval border to the list of a block's list
94 * @note You always have to create the use before the def.
95 * @param env The environment.
96 * @param head The list head to enqueue the borders.
97 * @param irn The node (value) the border belongs to.
98 * @param pressure The pressure at this point in time.
99 * @param step A time step for the border.
100 * @param is_def Is the border a use or a def.
101 * @return The created border.
103 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
104 ir_node *irn, unsigned step, unsigned pressure,
105 unsigned is_def, unsigned is_real)
112 b = obstack_alloc(&env->obst, sizeof(*b));
114 /* also allocate the def and tie it to the use. */
115 def = obstack_alloc(&env->obst, sizeof(*def));
116 memset(def, 0, sizeof(*def));
121 * Set the link field of the irn to the def.
122 * This strongly relies on the fact, that the use is always
123 * made before the def.
125 set_irn_link(irn, def);
127 DEBUG_ONLY(b->magic = BORDER_FOURCC);
128 DEBUG_ONLY(def->magic = BORDER_FOURCC);
132 * If the def is encountered, the use was made and so was the
133 * the def node (see the code above). It was placed into the
134 * link field of the irn, so we can get it there.
137 b = get_irn_link(irn);
139 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
142 b->pressure = pressure;
144 b->is_real = is_real;
147 list_add_tail(&b->list, head);
148 DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
155 * Check, if an irn is of the register class currently under processing.
156 * @param env The chordal environment.
157 * @param irn The node.
158 * @return 1, if the node is of that register class, 0 if not.
160 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
162 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
163 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
166 #define has_limited_constr(req, irn) \
167 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
169 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
171 bitset_t *tmp = alloc_env->tmp_colors;
172 bitset_copy(tmp, colors);
173 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
174 return bitset_next_clear(tmp, 0);
177 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
182 bitset_copy(bs, o2->regs);
187 bitset_copy(bs, o1->regs);
191 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
193 if(bitset_contains(o1->regs, o2->regs))
194 bitset_copy(bs, o1->regs);
195 else if(bitset_contains(o2->regs, o1->regs))
196 bitset_copy(bs, o2->regs);
203 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
207 ie.ignore_colors = env->ignore_colors;
208 ie.aenv = env->birg->main_env->arch_env;
209 ie.obst = &env->obst;
211 return be_scan_insn(&ie, irn);
214 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
216 const arch_env_t *aenv = env->birg->main_env->arch_env;
217 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
218 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
219 ir_node *bl = get_nodes_block(irn);
220 be_lv_t *lv = env->birg->lv;
225 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
226 ir_node *op = get_irn_n(irn, i);
228 const arch_register_t *reg;
229 const arch_register_req_t *req;
231 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
234 reg = arch_get_irn_register(aenv, op);
236 if (reg == NULL || !arch_register_type_is(reg, ignore))
238 if(arch_register_type_is(reg, joker))
241 req = arch_get_register_req(aenv, irn, i);
242 if (!arch_register_req_is(req, limited))
245 if (rbitset_is_set(req->limited, reg->index))
248 copy = be_new_Copy(env->cls, env->irg, bl, op);
249 be_stat_ev("constr_copy", 1);
251 sched_add_before(irn, copy);
252 set_irn_n(irn, i, copy);
253 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
256 insn = chordal_scan_insn(env, irn);
258 if(!insn->has_constraints)
261 /* insert copies for nodes that occur constrained more than once. */
262 for(i = insn->use_start; i < insn->n_ops; ++i) {
263 be_operand_t *op = &insn->ops[i];
265 if(!op->has_constraints)
268 for(j = i + 1; j < insn->n_ops; ++j) {
270 be_operand_t *a_op = &insn->ops[j];
272 if(a_op->carrier != op->carrier || !a_op->has_constraints)
275 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
276 be_stat_ev("constr_copy", 1);
278 sched_add_before(insn->irn, copy);
279 set_irn_n(insn->irn, a_op->pos, copy);
280 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
284 /* collect all registers occuring in out constraints. */
285 for(i = 0; i < insn->use_start; ++i) {
286 be_operand_t *op = &insn->ops[i];
287 if(op->has_constraints)
288 bitset_or(def_constr, op->regs);
292 insert copies for all constrained arguments living through the node
293 and being constrained to a register which also occurs in out constraints.
295 for(i = insn->use_start; i < insn->n_ops; ++i) {
297 be_operand_t *op = &insn->ops[i];
299 bitset_copy(tmp, op->regs);
300 bitset_and(tmp, def_constr);
304 1) the operand is constrained.
305 2) lives through the node.
306 3) is constrained to a register occuring in out constraints.
308 if(!op->has_constraints ||
309 !values_interfere(lv, insn->irn, op->carrier) ||
310 bitset_popcnt(tmp) == 0)
314 only create the copy if the operand is no copy.
315 this is necessary since the assure constraints phase inserts
316 Copies and Keeps for operands which must be different from the results.
317 Additional copies here would destroy this.
319 if(be_is_Copy(op->carrier))
322 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
324 sched_add_before(insn->irn, copy);
325 set_irn_n(insn->irn, op->pos, copy);
326 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
327 be_liveness_update(lv, op->carrier);
331 obstack_free(&env->obst, insn);
332 return insn->next_insn;
335 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
337 be_chordal_env_t *env = data;
339 for(irn = sched_first(bl); !sched_is_end(irn);) {
340 irn = prepare_constr_insn(env, irn);
344 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
345 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
348 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
350 const be_chordal_env_t *env = alloc_env->chordal_env;
352 int n_uses = be_insn_n_uses(insn);
353 int n_defs = be_insn_n_defs(insn);
354 bitset_t *bs = bitset_alloca(env->cls->n_regs);
355 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
356 be_lv_t *lv = env->birg->lv;
361 For each out operand, try to find an in operand which can be assigned the
362 same register as the out operand.
364 for (j = 0; j < insn->use_start; ++j) {
366 int smallest_n_regs = 2 * env->cls->n_regs + 1;
367 be_operand_t *out_op = &insn->ops[j];
369 /* Try to find an in operand which has ... */
370 for(i = insn->use_start; i < insn->n_ops; ++i) {
372 const be_operand_t *op = &insn->ops[i];
374 if (op->partner != NULL)
376 if (values_interfere(lv, op->irn, op->carrier))
379 bitset_clear_all(bs);
380 bitset_copy(bs, op->regs);
381 bitset_and(bs, out_op->regs);
382 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
384 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
386 smallest_n_regs = n_total;
391 be_operand_t *partner = &insn->ops[smallest];
392 out_op->partner = partner;
393 partner->partner = out_op;
399 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
400 be_insn_t **the_insn)
402 be_chordal_env_t *env = alloc_env->chordal_env;
403 const arch_env_t *aenv = env->birg->main_env->arch_env;
404 be_insn_t *insn = *the_insn;
405 ir_node *perm = NULL;
406 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
407 const ir_edge_t *edge;
410 assert(insn->has_constraints && "only do this for constrained nodes");
413 Collect all registers that occur in output constraints.
414 This is necessary, since if the insn has one of these as an input constraint
415 and the corresponding operand interferes with the insn, the operand must
418 for(i = 0; i < insn->use_start; ++i) {
419 be_operand_t *op = &insn->ops[i];
420 if(op->has_constraints)
421 bitset_or(out_constr, op->regs);
425 Make the Perm, recompute liveness and re-scan the insn since the
426 in operands are now the Projs of the Perm.
428 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
430 /* Registers are propagated by insert_Perm_after(). Clean them here! */
434 be_stat_ev("constr_perm", get_irn_arity(perm));
435 foreach_out_edge(perm, edge) {
436 ir_node *proj = get_edge_src_irn(edge);
437 arch_set_irn_register(aenv, proj, NULL);
441 We also have to re-build the insn since the input operands are now the Projs of
442 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
443 the live sets may change.
445 // be_liveness_recompute(lv);
446 obstack_free(&env->obst, insn);
447 *the_insn = insn = chordal_scan_insn(env, insn->irn);
450 Copy the input constraints of the insn to the Perm as output
451 constraints. Succeeding phases (coalescing) will need that.
453 for(i = insn->use_start; i < insn->n_ops; ++i) {
454 be_operand_t *op = &insn->ops[i];
455 ir_node *proj = op->carrier;
457 Note that the predecessor must not be a Proj of the Perm,
458 since ignore-nodes are not Perm'ed.
460 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
461 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
468 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
470 const arch_env_t *aenv;
473 ir_node **alloc_nodes;
474 hungarian_problem_t *bp;
479 const ir_edge_t *edge;
480 ir_node *perm = NULL;
482 be_chordal_env_t *env = alloc_env->chordal_env;
483 void *base = obstack_base(&env->obst);
484 be_insn_t *insn = chordal_scan_insn(env, irn);
485 ir_node *res = insn->next_insn;
486 int be_silent = *silent;
487 be_lv_t *lv = env->birg->lv;
489 if(insn->pre_colored) {
491 for(i = 0; i < insn->use_start; ++i)
492 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
496 If the current node is a barrier toggle the silent flag.
497 If we are in the start block, we are ought to be silent at the beginning,
498 so the toggling activates the constraint handling but skips the barrier.
499 If we are in the end block we handle the in requirements of the barrier
500 and set the rest to silent.
502 if(be_is_Barrier(irn))
509 Perms inserted before the constraint handling phase are considered to be
510 correctly precolored. These Perms arise during the ABI handling phase.
512 if(!insn->has_constraints)
515 aenv = env->birg->main_env->arch_env;
516 n_regs = env->cls->n_regs;
517 bs = bitset_alloca(n_regs);
518 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
519 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
520 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
521 assignment = alloca(n_regs * sizeof(assignment[0]));
522 partners = pmap_create();
525 prepare the constraint handling of this node.
526 Perms are constructed and Copies are created for constrained values
527 interfering with the instruction.
529 perm = pre_process_constraints(alloc_env, &insn);
531 /* find suitable in operands to the out operands of the node. */
532 pair_up_operands(alloc_env, insn);
535 look at the in/out operands and add each operand (and its possible partner)
536 to a bipartite graph (left: nodes with partners, right: admissible colors).
538 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
539 be_operand_t *op = &insn->ops[i];
542 If the operand has no partner or the partner has not been marked
543 for allocation, determine the admissible registers and mark it
544 for allocation by associating the node and its partner with the
545 set of admissible registers via a bipartite graph.
547 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
549 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
550 alloc_nodes[n_alloc] = op->carrier;
552 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
554 bitset_clear_all(bs);
555 get_decisive_partner_regs(bs, op, op->partner);
557 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
559 bitset_foreach(bs, col) {
560 hungarian_add(bp, n_alloc, col, 1);
561 // bipartite_add(bp, n_alloc, col);
569 Put all nodes which live through the constrained instruction also to the
570 allocation bipartite graph. They are considered unconstrained.
573 foreach_out_edge(perm, edge) {
574 ir_node *proj = get_edge_src_irn(edge);
576 assert(is_Proj(proj));
578 if(!values_interfere(lv, proj, irn) || pmap_contains(partners, proj))
581 assert(n_alloc < n_regs);
582 alloc_nodes[n_alloc] = proj;
583 pmap_insert(partners, proj, NULL);
585 bitset_clear_all(bs);
586 arch_put_non_ignore_regs(aenv, env->cls, bs);
587 bitset_andnot(bs, env->ignore_colors);
588 bitset_foreach(bs, col) {
589 hungarian_add(bp, n_alloc, col, 1);
590 // bipartite_add(bp, n_alloc, col);
597 /* Compute a valid register allocation. */
598 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
599 match_res = hungarian_solve(bp, assignment, &cost, 1);
600 assert(match_res == 0 && "matching failed");
601 //bipartite_matching(bp, assignment);
603 /* Assign colors obtained from the matching. */
604 for(i = 0; i < n_alloc; ++i) {
605 const arch_register_t *reg;
609 assert(assignment[i] >= 0 && "there must have been a register assigned");
610 reg = arch_register_for_index(env->cls, assignment[i]);
612 nodes[0] = alloc_nodes[i];
613 nodes[1] = pmap_get(partners, alloc_nodes[i]);
615 for(j = 0; j < 2; ++j) {
619 arch_set_irn_register(aenv, nodes[j], reg);
620 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
621 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
625 /* Allocate the non-constrained Projs of the Perm. */
627 bitset_clear_all(bs);
629 /* Put the colors of all Projs in a bitset. */
630 foreach_out_edge(perm, edge) {
631 ir_node *proj = get_edge_src_irn(edge);
632 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
635 bitset_set(bs, reg->index);
638 /* Assign the not yet assigned Projs of the Perm a suitable color. */
639 foreach_out_edge(perm, edge) {
640 ir_node *proj = get_edge_src_irn(edge);
641 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
643 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
646 col = get_next_free_reg(alloc_env, bs);
647 reg = arch_register_for_index(env->cls, col);
648 bitset_set(bs, reg->index);
649 arch_set_irn_register(aenv, proj, reg);
650 pset_insert_ptr(alloc_env->pre_colored, proj);
651 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
656 //bipartite_free(bp);
658 pmap_destroy(partners);
661 obstack_free(&env->obst, base);
666 * Handle constraint nodes in each basic block.
667 * handle_constraints() inserts Perm nodes which perm
668 * over all values live at the constrained node right in front
669 * of the constrained node. These Perms signal a constrained node.
670 * For further comments, refer to handle_constraints().
672 static void constraints(ir_node *bl, void *data)
674 be_chordal_alloc_env_t *env = data;
677 Start silent in the start block.
678 The silence remains until the first barrier is seen.
679 Each other block is begun loud.
681 int silent = bl == get_irg_start_block(get_irn_irg(bl));
685 If the block is the start block search the barrier and
686 start handling constraints from there.
689 for(irn = sched_first(bl); !sched_is_end(irn);) {
690 irn = handle_constraints(env, irn, &silent);
695 * Annotate the register pressure to the nodes and compute
696 * the liveness intervals.
697 * @param block The block to do it for.
698 * @param env_ptr The environment.
700 static void pressure(ir_node *block, void *env_ptr)
702 /* Convenience macro for a def */
703 #define border_def(irn, step, real) \
704 border_add(env, head, irn, step, pressure--, 1, real)
706 /* Convenience macro for a use */
707 #define border_use(irn, step, real) \
708 border_add(env, head, irn, step, ++pressure, 0, real)
710 be_chordal_alloc_env_t *alloc_env = env_ptr;
711 be_chordal_env_t *env = alloc_env->chordal_env;
712 bitset_t *live = alloc_env->live;
714 be_lv_t *lv = env->birg->lv;
718 unsigned pressure = 0;
719 struct list_head *head;
720 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
721 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
723 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
724 bitset_clear_all(live);
726 /* Set up the border list in the block info */
727 head = obstack_alloc(&env->obst, sizeof(*head));
728 INIT_LIST_HEAD(head);
729 assert(pmap_get(env->border_heads, block) == NULL);
730 pmap_insert(env->border_heads, block, head);
733 * Make final uses of all values live out of the block.
734 * They are necessary to build up real intervals.
736 foreach_pset(live_end, irn) {
737 if(has_reg_class(env, irn)) {
738 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
739 bitset_set(live, get_irn_idx(irn));
740 border_use(irn, step, 0);
746 * Determine the last uses of a value inside the block, since they are
747 * relevant for the interval borders.
749 sched_foreach_reverse(block, irn) {
750 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
751 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
754 * If the node defines some value, which can put into a
755 * register of the current class, make a border for it.
757 if(has_reg_class(env, irn)) {
758 int nr = get_irn_idx(irn);
760 bitset_clear(live, nr);
761 border_def(irn, step, 1);
765 * If the node is no phi node we can examine the uses.
768 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
769 ir_node *op = get_irn_n(irn, i);
771 if(has_reg_class(env, op)) {
772 int nr = get_irn_idx(op);
773 const char *msg = "-";
775 if(!bitset_is_set(live, nr)) {
776 border_use(op, step, 1);
777 bitset_set(live, nr);
781 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
789 * Add initial defs for all values live in.
791 foreach_pset(live_in, irn) {
792 if(has_reg_class(env, irn)) {
794 /* Mark the value live in. */
795 bitset_set(live, get_irn_idx(irn));
798 border_def(irn, step, 0);
806 static void assign(ir_node *block, void *env_ptr)
808 be_chordal_alloc_env_t *alloc_env = env_ptr;
809 be_chordal_env_t *env = alloc_env->chordal_env;
810 bitset_t *live = alloc_env->live;
811 bitset_t *colors = alloc_env->colors;
812 bitset_t *in_colors = alloc_env->in_colors;
813 const arch_env_t *arch_env = env->birg->main_env->arch_env;
814 struct list_head *head = get_block_border_head(env, block);
815 be_lv_t *lv = env->birg->lv;
816 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
821 bitset_clear_all(colors);
822 bitset_clear_all(live);
823 bitset_clear_all(in_colors);
825 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
826 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
827 list_for_each_entry(border_t, b, head, list) {
828 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
829 b->irn, get_irn_idx(b->irn)));
833 * Add initial defs for all values live in.
834 * Since their colors have already been assigned (The dominators were
835 * allocated before), we have to mark their colors as used also.
837 foreach_pset(live_in, irn) {
838 if(has_reg_class(env, irn)) {
839 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
842 assert(reg && "Node must have been assigned a register");
843 col = arch_register_get_index(reg);
845 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
847 /* Mark the color of the live in value as used. */
848 bitset_set(colors, col);
849 bitset_set(in_colors, col);
851 /* Mark the value live in. */
852 bitset_set(live, get_irn_idx(irn));
857 * Mind that the sequence of defs from back to front defines a perfect
858 * elimination order. So, coloring the definitions from first to last
861 list_for_each_entry_reverse(border_t, b, head, list) {
862 ir_node *irn = b->irn;
863 int nr = get_irn_idx(irn);
864 int ignore = arch_irn_is(arch_env, irn, ignore);
867 * Assign a color, if it is a local def. Global defs already have a
870 if(b->is_def && !be_is_live_in(lv, block, irn)) {
871 const arch_register_t *reg;
874 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
875 reg = arch_get_irn_register(arch_env, irn);
877 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
879 col = get_next_free_reg(alloc_env, colors);
880 reg = arch_register_for_index(env->cls, col);
881 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
882 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
885 bitset_set(colors, col);
886 arch_set_irn_register(arch_env, irn, reg);
888 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
890 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
891 bitset_set(live, nr);
894 /* Clear the color upon a use. */
895 else if(!b->is_def) {
896 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
899 assert(reg && "Register must have been assigned");
901 col = arch_register_get_index(reg);
903 if(!arch_register_type_is(reg, ignore)) {
904 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
908 bitset_clear(colors, col);
909 bitset_clear(live, nr);
916 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
918 be_chordal_alloc_env_t env;
920 be_irg_t *birg = chordal_env->birg;
921 const arch_register_class_t *cls = chordal_env->cls;
923 int colors_n = arch_register_class_n_regs(cls);
924 ir_graph *irg = chordal_env->irg;
925 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
927 /* some special classes contain only ignore regs, no work to be done */
928 if(allocatable_regs == 0)
931 be_assure_dom_front(birg);
932 be_assure_liveness(birg);
935 env.chordal_env = chordal_env;
936 env.colors_n = colors_n;
937 env.colors = bitset_alloca(colors_n);
938 env.tmp_colors = bitset_alloca(colors_n);
939 env.in_colors = bitset_alloca(colors_n);
940 env.pre_colored = pset_new_ptr_default();
942 /* Handle register targeting constraints */
943 dom_tree_walk_irg(irg, constraints, NULL, &env);
945 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
946 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
947 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
950 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
952 /* First, determine the pressure */
953 dom_tree_walk_irg(irg, pressure, NULL, &env);
955 /* Assign the colors */
956 dom_tree_walk_irg(irg, assign, NULL, &env);
958 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
960 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
961 plotter = new_plotter_ps(buf);
962 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
963 plotter_free(plotter);
966 bitset_free(env.live);
967 del_pset(env.pre_colored);
970 void be_init_chordal(void)
972 FIRM_DBG_REGISTER(dbg, "firm.be.chordal.constr");
975 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);