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 if (arch_get_irn_reg_class(aenv, irn, i) == env->cls) {
240 reg = arch_get_irn_register(aenv, op);
242 if (reg && arch_register_type_is(reg, ignore)) {
243 arch_get_register_req(aenv, &req, irn, i);
245 if (arch_register_req_is(&req, limited)) {
246 bitset_clear_all(tmp);
247 req.limited(req.limited_env, tmp);
249 if (! bitset_is_set(tmp, reg->index)) {
250 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op);
251 be_stat_ev("constr_copy", 1);
253 sched_add_before(irn, copy);
254 set_irn_n(irn, i, copy);
255 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
262 insn = chordal_scan_insn(env, irn);
264 if(!insn->has_constraints)
267 /* insert copies for nodes that occur constrained more than once. */
268 for(i = insn->use_start; i < insn->n_ops; ++i) {
269 be_operand_t *op = &insn->ops[i];
271 if(op->has_constraints) {
272 for(j = i + 1; j < insn->n_ops; ++j) {
273 be_operand_t *a_op = &insn->ops[j];
275 if(a_op->carrier == op->carrier && a_op->has_constraints) {
276 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
277 be_stat_ev("constr_copy", 1);
279 sched_add_before(insn->irn, copy);
280 set_irn_n(insn->irn, a_op->pos, copy);
281 DBG((env->dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
287 /* collect all registers occuring in out constraints. */
288 for(i = 0; i < insn->use_start; ++i) {
289 be_operand_t *op = &insn->ops[i];
290 if(op->has_constraints)
291 bitset_or(def_constr, op->regs);
295 insert copies for all constrained arguments living through the node
296 and being constrained to a register which also occurs in out constraints.
298 for(i = insn->use_start; i < insn->n_ops; ++i) {
299 be_operand_t *op = &insn->ops[i];
301 bitset_copy(tmp, op->regs);
302 bitset_and(tmp, def_constr);
306 1) the operand is constrained.
307 2) lives through the node.
308 3) is constrained to a register occuring in out constraints.
310 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
312 only create the copy if the operand is no copy.
313 this is necessary since the assure constraints phase inserts
314 Copies and Keeps for operands which must be different from the results.
315 Additional copies here would destroy this.
317 if(!be_is_Copy(op->carrier)) {
318 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
320 sched_add_before(insn->irn, copy);
321 set_irn_n(insn->irn, op->pos, copy);
322 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
323 be_liveness_update(env->lv, op->carrier);
329 obstack_free(&env->obst, insn);
330 return insn->next_insn;
333 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
335 be_chordal_env_t *env = data;
337 for(irn = sched_first(bl); !sched_is_end(irn);) {
338 irn = prepare_constr_insn(env, irn);
342 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
343 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
346 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
348 const be_chordal_env_t *env = alloc_env->chordal_env;
350 int n_uses = be_insn_n_uses(insn);
351 int n_defs = be_insn_n_defs(insn);
352 bitset_t *bs = bitset_alloca(env->cls->n_regs);
353 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
358 For each out operand, try to find an in operand which can be assigned the
359 same register as the out operand.
361 for (j = 0; j < insn->use_start; ++j) {
363 int smallest_n_regs = 2 * env->cls->n_regs + 1;
364 be_operand_t *out_op = &insn->ops[j];
366 /* Try to find an in operand which has ... */
367 for(i = insn->use_start; i < insn->n_ops; ++i) {
369 const be_operand_t *op = &insn->ops[i];
371 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
372 bitset_clear_all(bs);
373 bitset_copy(bs, op->regs);
374 bitset_and(bs, out_op->regs);
375 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
377 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
379 smallest_n_regs = n_total;
385 be_operand_t *partner = &insn->ops[smallest];
386 out_op->partner = partner;
387 partner->partner = out_op;
393 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
395 be_chordal_env_t *env = alloc_env->chordal_env;
396 const arch_env_t *aenv = env->birg->main_env->arch_env;
397 be_insn_t *insn = *the_insn;
398 ir_node *bl = get_nodes_block(insn->irn);
399 ir_node *copy = NULL;
400 ir_node *perm = NULL;
401 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
402 bitset_t *bs = bitset_alloca(env->cls->n_regs);
403 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
407 assert(insn->has_constraints && "only do this for constrained nodes");
410 Collect all registers that occur in output constraints.
411 This is necessary, since if the insn has one of these as an input constraint
412 and the corresponding operand interferes with the insn, the operand must
415 for(i = 0; i < insn->use_start; ++i) {
416 be_operand_t *op = &insn->ops[i];
417 if(op->has_constraints)
418 bitset_or(out_constr, op->regs);
424 DEBUG_ONLY((void) dbg;)
427 Make the Perm, recompute liveness and re-scan the insn since the
428 in operands are now the Projs of the Perm.
430 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
432 /* Registers are propagated by insert_Perm_after(). Clean them here! */
434 const ir_edge_t *edge;
436 be_stat_ev("constr_perm", get_irn_arity(perm));
437 foreach_out_edge(perm, edge) {
438 ir_node *proj = get_edge_src_irn(edge);
439 arch_set_irn_register(aenv, proj, NULL);
443 We also have to re-build the insn since the input operands are now the Projs of
444 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
445 the live sets may change.
447 // be_liveness_recompute(env->lv);
448 obstack_free(&env->obst, insn);
449 *the_insn = insn = chordal_scan_insn(env, insn->irn);
452 Copy the input constraints of the insn to the Perm as output
453 constraints. Succeeding phases (coalescing will need that).
455 for(i = insn->use_start; i < insn->n_ops; ++i) {
456 be_operand_t *op = &insn->ops[i];
457 ir_node *proj = op->carrier;
459 Note that the predecessor must not be a Proj of the Perm,
460 since ignore-nodes are not Perm'ed.
462 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
463 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
471 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
473 be_chordal_env_t *env = alloc_env->chordal_env;
474 void *base = obstack_base(&env->obst);
475 be_insn_t *insn = chordal_scan_insn(env, irn);
476 ir_node *res = insn->next_insn;
477 int be_silent = *silent;
479 if(insn->pre_colored) {
481 for(i = 0; i < insn->use_start; ++i)
482 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
486 If the current node is a barrier toggle the silent flag.
487 If we are in the start block, we are ought to be silent at the beginning,
488 so the toggling activates the constraint handling but skips the barrier.
489 If we are in the end block we handle the in requirements of the barrier
490 and set the rest to silent.
492 if(be_is_Barrier(irn))
499 Perms inserted before the constraint handling phase are considered to be
500 correctly precolored. These Perms arise during the ABI handling phase.
502 if(insn->has_constraints) {
503 const arch_env_t *aenv = env->birg->main_env->arch_env;
504 int n_regs = env->cls->n_regs;
505 bitset_t *bs = bitset_alloca(n_regs);
506 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
507 bipartite_t *bp = bipartite_new(n_regs, n_regs);
508 int *assignment = alloca(n_regs * sizeof(assignment[0]));
509 pmap *partners = pmap_create();
510 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
514 const ir_edge_t *edge;
515 ir_node *perm = NULL;
518 prepare the constraint handling of this node.
519 Perms are constructed and Copies are created for constrained values
520 interfering with the instruction.
522 perm = pre_process_constraints(alloc_env, &insn);
524 /* find suitable in operands to the out operands of the node. */
525 pair_up_operands(alloc_env, insn);
528 look at the in/out operands and add each operand (and its possible partner)
529 to a bipartite graph (left: nodes with partners, right: admissible colors).
531 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
532 be_operand_t *op = &insn->ops[i];
535 If the operand has no partner or the partner has not been marked
536 for allocation, determine the admissible registers and mark it
537 for allocation by associating the node and its partner with the
538 set of admissible registers via a bipartite graph.
540 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
542 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
543 alloc_nodes[n_alloc] = op->carrier;
545 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
547 bitset_clear_all(bs);
548 get_decisive_partner_regs(bs, op, op->partner);
550 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
552 bitset_foreach(bs, col)
553 bipartite_add(bp, n_alloc, col);
560 Put all nodes which live through the constrained instruction also to the
561 allocation bipartite graph. They are considered unconstrained.
564 foreach_out_edge(perm, edge) {
565 ir_node *proj = get_edge_src_irn(edge);
567 assert(is_Proj(proj));
569 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
570 assert(n_alloc < n_regs);
571 alloc_nodes[n_alloc] = proj;
572 pmap_insert(partners, proj, NULL);
574 bitset_clear_all(bs);
575 arch_put_non_ignore_regs(aenv, env->cls, bs);
576 bitset_andnot(bs, env->ignore_colors);
577 bitset_foreach(bs, col)
578 bipartite_add(bp, n_alloc, col);
585 /* Compute a valid register allocation. */
586 bipartite_matching(bp, assignment);
588 /* Assign colors obtained from the matching. */
589 for(i = 0; i < n_alloc; ++i) {
590 const arch_register_t *reg;
594 assert(assignment[i] >= 0 && "there must have been a register assigned");
595 reg = arch_register_for_index(env->cls, assignment[i]);
597 nodes[0] = alloc_nodes[i];
598 nodes[1] = pmap_get(partners, alloc_nodes[i]);
600 for(j = 0; j < 2; ++j) {
604 arch_set_irn_register(aenv, nodes[j], reg);
605 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
606 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
611 /* Allocate the non-constrained Projs of the Perm. */
614 bitset_clear_all(bs);
616 /* Put the colors of all Projs in a bitset. */
617 foreach_out_edge(perm, edge) {
618 ir_node *proj = get_edge_src_irn(edge);
619 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
622 bitset_set(bs, reg->index);
625 /* Assign the not yet assigned Projs of the Perm a suitable color. */
626 foreach_out_edge(perm, edge) {
627 ir_node *proj = get_edge_src_irn(edge);
628 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
630 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
633 col = get_next_free_reg(alloc_env, bs);
634 reg = arch_register_for_index(env->cls, col);
635 bitset_set(bs, reg->index);
636 arch_set_irn_register(aenv, proj, reg);
637 pset_insert_ptr(alloc_env->pre_colored, proj);
638 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
644 pmap_destroy(partners);
648 obstack_free(&env->obst, base);
653 * Handle constraint nodes in each basic block.
654 * handle_constraints() inserts Perm nodes which perm
655 * over all values live at the constrained node right in front
656 * of the constrained node. These Perms signal a constrained node.
657 * For further comments, refer to handle_constraints().
659 static void constraints(ir_node *bl, void *data)
661 be_chordal_alloc_env_t *env = data;
664 Start silent in the start block.
665 The silence remains until the first barrier is seen.
666 Each other block is begun loud.
668 int silent = bl == get_irg_start_block(get_irn_irg(bl));
672 If the block is the start block search the barrier and
673 start handling constraints from there.
676 for(irn = sched_first(bl); !sched_is_end(irn);) {
677 irn = handle_constraints(env, irn, &silent);
682 * Annotate the register pressure to the nodes and compute
683 * the liveness intervals.
684 * @param block The block to do it for.
685 * @param env_ptr The environment.
687 static void pressure(ir_node *block, void *env_ptr)
689 /* Convenience macro for a def */
690 #define border_def(irn, step, real) \
691 border_add(env, head, irn, step, pressure--, 1, real)
693 /* Convenience macro for a use */
694 #define border_use(irn, step, real) \
695 border_add(env, head, irn, step, ++pressure, 0, real)
697 be_chordal_alloc_env_t *alloc_env = env_ptr;
698 be_chordal_env_t *env = alloc_env->chordal_env;
699 bitset_t *live = alloc_env->live;
701 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
705 unsigned pressure = 0;
706 struct list_head *head;
707 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
708 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
710 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
711 bitset_clear_all(live);
713 /* Set up the border list in the block info */
714 head = obstack_alloc(&env->obst, sizeof(*head));
715 INIT_LIST_HEAD(head);
716 assert(pmap_get(env->border_heads, block) == NULL);
717 pmap_insert(env->border_heads, block, head);
720 * Make final uses of all values live out of the block.
721 * They are necessary to build up real intervals.
723 foreach_pset(live_end, irn) {
724 if(has_reg_class(env, irn)) {
725 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
726 bitset_set(live, get_irn_idx(irn));
727 border_use(irn, step, 0);
733 * Determine the last uses of a value inside the block, since they are
734 * relevant for the interval borders.
736 sched_foreach_reverse(block, irn) {
737 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
738 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
741 * If the node defines some value, which can put into a
742 * register of the current class, make a border for it.
744 if(has_reg_class(env, irn)) {
745 int nr = get_irn_idx(irn);
747 bitset_clear(live, nr);
748 border_def(irn, step, 1);
752 * If the node is no phi node we can examine the uses.
755 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
756 ir_node *op = get_irn_n(irn, i);
758 if(has_reg_class(env, op)) {
759 int nr = get_irn_idx(op);
760 const char *msg = "-";
762 if(!bitset_is_set(live, nr)) {
763 border_use(op, step, 1);
764 bitset_set(live, nr);
768 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
776 * Add initial defs for all values live in.
778 foreach_pset(live_in, irn) {
779 if(has_reg_class(env, irn)) {
781 /* Mark the value live in. */
782 bitset_set(live, get_irn_idx(irn));
785 border_def(irn, step, 0);
793 static void assign(ir_node *block, void *env_ptr)
795 be_chordal_alloc_env_t *alloc_env = env_ptr;
796 be_chordal_env_t *env = alloc_env->chordal_env;
797 bitset_t *live = alloc_env->live;
798 bitset_t *colors = alloc_env->colors;
799 bitset_t *in_colors = alloc_env->in_colors;
800 const arch_env_t *arch_env = env->birg->main_env->arch_env;
801 struct list_head *head = get_block_border_head(env, block);
802 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
806 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
808 bitset_clear_all(colors);
809 bitset_clear_all(live);
810 bitset_clear_all(in_colors);
812 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
813 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
814 list_for_each_entry(border_t, b, head, list) {
815 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
816 b->irn, get_irn_idx(b->irn)));
820 * Add initial defs for all values live in.
821 * Since their colors have already been assigned (The dominators were
822 * allocated before), we have to mark their colors as used also.
824 foreach_pset(live_in, irn) {
825 if(has_reg_class(env, irn)) {
826 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
829 assert(reg && "Node must have been assigned a register");
830 col = arch_register_get_index(reg);
832 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
834 /* Mark the color of the live in value as used. */
835 bitset_set(colors, col);
836 bitset_set(in_colors, col);
838 /* Mark the value live in. */
839 bitset_set(live, get_irn_idx(irn));
844 * Mind that the sequence
845 * of defs from back to front defines a perfect
846 * elimination order. So, coloring the definitions from first to last
849 list_for_each_entry_reverse(border_t, b, head, list) {
850 ir_node *irn = b->irn;
851 int nr = get_irn_idx(irn);
852 int ignore = arch_irn_is(arch_env, irn, ignore);
855 * Assign a color, if it is a local def. Global defs already have a
858 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
859 const arch_register_t *reg;
862 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
863 reg = arch_get_irn_register(arch_env, irn);
865 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
869 col = get_next_free_reg(alloc_env, colors);
870 reg = arch_register_for_index(env->cls, col);
871 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
872 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
875 bitset_set(colors, col);
876 arch_set_irn_register(arch_env, irn, reg);
878 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
880 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
881 bitset_set(live, nr);
884 /* Clear the color upon a use. */
885 else if(!b->is_def) {
886 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
889 assert(reg && "Register must have been assigned");
891 col = arch_register_get_index(reg);
892 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
894 bitset_clear(colors, col);
895 bitset_clear(live, nr);
902 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
904 be_chordal_alloc_env_t env;
907 int colors_n = arch_register_class_n_regs(chordal_env->cls);
908 ir_graph *irg = chordal_env->irg;
913 env.chordal_env = chordal_env;
914 env.colors_n = colors_n;
915 env.colors = bitset_alloca(colors_n);
916 env.tmp_colors = bitset_alloca(colors_n);
917 env.in_colors = bitset_alloca(colors_n);
918 env.pre_colored = pset_new_ptr_default();
919 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
922 /* Handle register targeting constraints */
923 dom_tree_walk_irg(irg, constraints, NULL, &env);
925 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
926 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
927 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
930 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
932 /* First, determine the pressure */
933 dom_tree_walk_irg(irg, pressure, NULL, &env);
935 /* Assign the colors */
936 dom_tree_walk_irg(irg, assign, NULL, &env);
938 be_numbering_done(irg);
940 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
942 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
943 plotter = new_plotter_ps(buf);
944 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
945 plotter_free(plotter);
948 bitset_free(env.live);
949 del_pset(env.pre_colored);