2 * Chordal register allocation.
3 * @author Sebastian Hack
6 * Copyright (C) Universitaet Karlsruhe
7 * Released under the GPL
29 #include "bipartite.h"
32 #include "irgraph_t.h"
33 #include "irprintf_t.h"
43 #include "besched_t.h"
50 #include "bechordal_t.h"
51 #include "bechordal_draw.h"
53 #define DBG_LEVEL SET_LEVEL_0
54 #define DBG_LEVEL_CHECK SET_LEVEL_0
58 #define MAX(x, y) ((x) > (y) ? (x) : (y))
59 #define MIN(x, y) ((x) < (y) ? (x) : (y))
61 #define DUMP_INTERVALS
63 typedef struct _be_chordal_alloc_env_t {
64 be_chordal_env_t *chordal_env;
66 firm_dbg_module_t *constr_dbg; /**< Debug output for the constraint handler. */
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 bitset_t *ignore_regs; /**< A bitset of all ignore registers in the current class. */
73 int colors_n; /**< The number of colors. */
74 } be_chordal_alloc_env_t;
78 /* Make a fourcc for border checking. */
79 #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 b->magic = BORDER_FOURCC;
136 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->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->ignore_regs);
182 return bitset_next_clear(tmp, 0);
185 typedef struct _operand_t operand_t;
193 arch_register_req_t req;
194 unsigned has_constraints : 1;
203 unsigned in_constraints : 1;
204 unsigned out_constraints : 1;
205 unsigned has_constraints : 1;
206 unsigned pre_colored : 1;
209 #define insn_n_defs(insn) ((insn)->use_start)
210 #define insn_n_uses(insn) ((insn)->n_ops - (insn)->use_start)
212 static insn_t *scan_insn(be_chordal_alloc_env_t *alloc_env, ir_node *irn, struct obstack *obst)
214 const be_chordal_env_t *env = alloc_env->chordal_env;
215 const arch_env_t *arch_env = env->birg->main_env->arch_env;
221 insn = obstack_alloc(obst, sizeof(insn[0]));
222 memset(insn, 0, sizeof(insn[0]));
225 insn->next_insn = sched_next(irn);
226 if(get_irn_mode(irn) == mode_T) {
229 for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
230 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
231 arch_get_register_req(arch_env, &o.req, p, -1);
234 o.pos = -(get_Proj_proj(p) + 1);
236 o.has_constraints = arch_register_req_is(&o.req, limited);
237 obstack_grow(obst, &o, sizeof(o));
239 insn->out_constraints |= o.has_constraints;
240 pre_colored += arch_get_irn_register(arch_env, p) != NULL;
247 else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
248 arch_get_register_req(arch_env, &o.req, irn, -1);
253 o.has_constraints = arch_register_req_is(&o.req, limited);
254 obstack_grow(obst, &o, sizeof(o));
256 insn->out_constraints |= o.has_constraints;
257 pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
260 insn->pre_colored = pre_colored == insn->n_ops && insn->n_ops > 0;
261 insn->use_start = insn->n_ops;
263 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
264 ir_node *op = get_irn_n(irn, i);
266 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
267 arch_get_register_req(arch_env, &o.req, irn, i);
272 o.has_constraints = arch_register_req_is(&o.req, limited);
273 obstack_grow(obst, &o, sizeof(o));
275 insn->in_constraints |= o.has_constraints;
279 insn->has_constraints = insn->in_constraints | insn->out_constraints;
280 insn->ops = obstack_finish(obst);
282 /* Compute the admissible registers bitsets. */
283 for(i = 0; i < insn->n_ops; ++i) {
284 operand_t *op = &insn->ops[i];
286 assert(op->req.cls == env->cls);
287 op->regs = bitset_obstack_alloc(obst, env->cls->n_regs);
289 if(arch_register_req_is(&op->req, limited))
290 op->req.limited(op->req.limited_env, op->regs);
292 arch_put_non_ignore_regs(env->birg->main_env->arch_env, env->cls, op->regs);
298 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const operand_t *o1, const operand_t *o2)
303 bitset_copy(bs, o2->regs);
308 bitset_copy(bs, o1->regs);
312 assert(o1->req.cls == o2->req.cls);
314 if(bitset_contains(o1->regs, o2->regs))
315 bitset_copy(bs, o1->regs);
316 else if(bitset_contains(o2->regs, o1->regs))
317 bitset_copy(bs, o2->regs);
324 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, insn_t *insn)
326 const be_chordal_env_t *env = alloc_env->chordal_env;
327 const arch_env_t *aenv = env->birg->main_env->arch_env;
328 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
330 int n_uses = insn_n_uses(insn);
331 int n_defs = insn_n_defs(insn);
332 int max_pairs = MIN(n_uses, n_defs);
333 bitset_t *bs = bitset_alloca(env->cls->n_regs);
334 bipartite_t *bp = bipartite_new(n_defs, n_uses);
335 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
340 For each out operand, try to find an in operand which can be assigned the
341 same register as the out operand.
343 for(j = 0; j < insn->use_start; ++j) {
344 operand_t *out_op = &insn->ops[j];
346 /* Try to find an in operand which has ... */
347 for(i = insn->use_start; i < insn->n_ops; ++i) {
348 const operand_t *op = &insn->ops[i];
351 The in operand can only be paired with a def, if the node defining the
352 operand's value does not interfere with the instruction itself. That
353 would mean, that it is live at the instruction, so no result of the instruction
354 can have the same register as the operand.
356 Furthermore, tow operands can be paired, if the admissible registers
357 of one are a subset of the other's. We record the operand whose constraints
358 count in the decisive array.
360 if(!values_interfere(op->irn, op->carrier)) {
361 if(get_decisive_partner_regs(bs, out_op, op))
362 bipartite_add(bp, j, i - insn->use_start);
367 /* Compute the pairing. */
368 bipartite_matching(bp, pairing);
369 for(i = 0; i < insn->use_start; ++i) {
370 int p = pairing[i] + insn->use_start;
372 if(p >= insn->use_start) {
373 insn->ops[i].partner = &insn->ops[p];
374 insn->ops[p].partner = &insn->ops[i];
382 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, insn_t **the_insn)
384 be_chordal_env_t *env = alloc_env->chordal_env;
385 const arch_env_t *aenv = env->birg->main_env->arch_env;
386 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
387 insn_t *insn = *the_insn;
388 ir_node *bl = get_nodes_block(insn->irn);
389 ir_node *copy = NULL;
390 ir_node *perm = NULL;
391 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
392 bitset_t *bs = bitset_alloca(env->cls->n_regs);
396 assert(insn->has_constraints && "only do this for constrained nodes");
399 Collect all registers that occur in output constraints.
400 This is necessary, since if the insn has one of these as an input constraint
401 and the corresponding operand interferes with the insn, the operand must
404 for(i = 0; i < insn->use_start; ++i) {
405 operand_t *op = &insn->ops[i];
406 if(op->has_constraints)
407 bitset_or(out_constr, op->regs);
411 Now, figure out which input operand must be copied since it has input
412 constraints which are also output constraints.
414 for(i = insn->use_start; i < insn->n_ops; ++i) {
415 operand_t *op = &insn->ops[i];
416 if(op->has_constraints && (values_interfere(op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
417 bitset_copy(bs, op->regs);
418 bitset_and(bs, out_constr);
421 The operand (interfering with the node) has input constraints
422 which also occur as output constraints, so insert a copy.
424 if(bitset_popcnt(bs) > 0) {
425 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
426 insn->ops[i].carrier = copy;
427 sched_add_before(insn->irn, copy);
429 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
435 Make the Perm, recompute liveness and re-scan the insn since the
436 in operands are now the Projs of the Perm.
438 perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(insn->irn));
440 /* Registers are propagated by insert_Perm_after(). Clean them here! */
442 const ir_edge_t *edge;
444 foreach_out_edge(perm, edge) {
445 ir_node *proj = get_edge_src_irn(edge);
446 arch_set_irn_register(aenv, proj, NULL);
450 We also have to re-build the insn since the input operands are now the Projs of
451 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
452 the live sets may change.
454 be_liveness(env->irg);
455 obstack_free(&env->obst, insn);
456 *the_insn = insn = scan_insn(alloc_env, insn->irn, &env->obst);
459 Copy the input constraints of the insn to the Perm as output
460 constraints. Succeeding phases (coalescing will need that).
462 for(i = insn->use_start; i < insn->n_ops; ++i) {
463 operand_t *op = &insn->ops[i];
464 ir_node *proj = op->carrier;
466 Note that the predecessor must not be a Proj of the Perm,
467 since ignore-nodes are not Perm'ed.
469 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
470 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
478 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
480 be_chordal_env_t *env = alloc_env->chordal_env;
481 void *base = obstack_base(&env->obst);
482 insn_t *insn = scan_insn(alloc_env, irn, &env->obst);
483 ir_node *res = insn->next_insn;
484 int be_silent = *silent;
486 if(insn->pre_colored) {
488 for(i = 0; i < insn->use_start; ++i)
489 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
493 If the current node is a barrier toggle the silent flag.
494 If we are in the start block, we are ought to be silent at the beginning,
495 so the toggling activates the constraint handling but skips the barrier.
496 If we are in the end block we handle the in requirements of the barrier
497 and set the rest to silent.
499 if(be_is_Barrier(irn))
506 Perms inserted before the constraint handling phase are considered to be
507 correctly precolored. These Perms arise during the ABI handling phase.
509 if(insn->has_constraints) {
510 firm_dbg_module_t *dbg = alloc_env->constr_dbg;
511 const arch_env_t *aenv = env->birg->main_env->arch_env;
512 int n_regs = env->cls->n_regs;
513 bitset_t *bs = bitset_alloca(n_regs);
514 bitset_t *non_ignore = bitset_alloca(n_regs);
515 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
516 bipartite_t *bp = bipartite_new(n_regs, n_regs);
517 int *assignment = alloca(n_regs * sizeof(assignment[0]));
518 pmap *partners = pmap_create();
522 const ir_edge_t *edge;
523 ir_node *perm = NULL;
526 prepare the constraint handling of this node.
527 Perms are constructed and Copies are created for constrained values
528 interfering with the instruction.
530 perm = pre_process_constraints(alloc_env, &insn);
532 /* find suitable in operands to the out operands of the node. */
533 pair_up_operands(alloc_env, insn);
536 look at the in/out operands and add each operand (and its possible partner)
537 to a bipartite graph (left: nodes with partners, right: admissible colors).
539 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
540 operand_t *op = &insn->ops[i];
543 If the operand has no partner or the partner has not been marked
544 for allocation, determine the admissible registers and mark it
545 for allocation by associating the node and its partner with the
546 set of admissible registers via a bipartite graph.
548 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
550 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
551 alloc_nodes[n_alloc] = op->carrier;
553 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
555 bitset_clear_all(bs);
556 get_decisive_partner_regs(bs, op, op->partner);
558 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
560 bitset_foreach(bs, col)
561 bipartite_add(bp, n_alloc, col);
568 Put all nodes which live by the constrained instruction also to the
569 allocation bipartite graph. They are considered unconstrained.
572 foreach_out_edge(perm, edge) {
573 ir_node *proj = get_edge_src_irn(edge);
575 assert(is_Proj(proj));
577 if(values_interfere(proj, irn) && !pmap_contains(partners, proj)) {
578 assert(n_alloc < n_regs);
579 alloc_nodes[n_alloc] = proj;
580 pmap_insert(partners, proj, NULL);
582 bitset_clear_all(bs);
583 arch_put_non_ignore_regs(aenv, env->cls, bs);
584 bitset_foreach(bs, col)
585 bipartite_add(bp, n_alloc, col);
592 /* Compute a valid register allocation. */
593 bipartite_matching(bp, assignment);
595 /* Assign colors obtained from the matching. */
596 for(i = 0; i < n_alloc; ++i) {
597 const arch_register_t *reg;
601 assert(assignment[i] >= 0 && "there must have been a register assigned");
602 reg = arch_register_for_index(env->cls, assignment[i]);
604 nodes[0] = alloc_nodes[i];
605 nodes[1] = pmap_get(partners, alloc_nodes[i]);
607 for(j = 0; j < 2; ++j) {
611 arch_set_irn_register(aenv, nodes[j], reg);
612 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
613 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
618 /* Allocate the non-constrained Projs of the Perm. */
621 bitset_clear_all(bs);
623 /* Put the colors of all Projs in a bitset. */
624 foreach_out_edge(perm, edge) {
625 ir_node *proj = get_edge_src_irn(edge);
626 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
629 bitset_set(bs, reg->index);
632 /* Assign the not yet assigned Projs of the Perm a suitable color. */
633 foreach_out_edge(perm, edge) {
634 ir_node *proj = get_edge_src_irn(edge);
635 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
637 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
640 col = get_next_free_reg(alloc_env, bs);
641 reg = arch_register_for_index(env->cls, col);
642 bitset_set(bs, reg->index);
643 arch_set_irn_register(aenv, proj, reg);
644 pset_insert_ptr(alloc_env->pre_colored, proj);
645 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
650 pmap_destroy(partners);
654 obstack_free(&env->obst, base);
659 * Handle constraint nodes in each basic block.
660 * handle_constraints() inserts Perm nodes which perm
661 * over all values live at the constrained node right in front
662 * of the constrained node. These Perms signal a constrained node.
663 * For further comments, refer to handle_constraints().
665 static void constraints(ir_node *bl, void *data)
667 be_chordal_alloc_env_t *env = data;
668 arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
669 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "firm.be.chordal.constr");
672 Start silent in the start block.
673 The silence remains until the first barrier is seen.
674 Each other block is begun loud.
676 int silent = bl == get_irg_start_block(get_irn_irg(bl));
680 If the block is the start block search the barrier and
681 start handling constraints from there.
684 for(irn = sched_first(bl); !sched_is_end(irn);) {
685 irn = handle_constraints(env, irn, &silent);
690 * Annotate the register pressure to the nodes and compute
691 * the liveness intervals.
692 * @param block The block to do it for.
693 * @param env_ptr The environment.
695 static void pressure(ir_node *block, void *env_ptr)
697 /* Convenience macro for a def */
698 #define border_def(irn, step, real) \
699 border_add(env, head, irn, step, pressure--, 1, real)
701 /* Convenience macro for a use */
702 #define border_use(irn, step, real) \
703 border_add(env, head, irn, step, ++pressure, 0, real)
705 be_chordal_alloc_env_t *alloc_env = env_ptr;
706 be_chordal_env_t *env = alloc_env->chordal_env;
707 const arch_env_t *arch_env = env->birg->main_env->arch_env;
708 bitset_t *live = alloc_env->live;
709 firm_dbg_module_t *dbg = env->dbg;
714 unsigned pressure = 0;
715 struct list_head *head;
716 pset *live_in = put_live_in(block, pset_new_ptr_default());
717 pset *live_end = put_live_end(block, pset_new_ptr_default());
719 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
720 bitset_clear_all(live);
722 /* Set up the border list in the block info */
723 head = obstack_alloc(&env->obst, sizeof(*head));
724 INIT_LIST_HEAD(head);
725 assert(pmap_get(env->border_heads, block) == NULL);
726 pmap_insert(env->border_heads, block, head);
729 * Make final uses of all values live out of the block.
730 * They are necessary to build up real intervals.
732 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
733 if(has_reg_class(env, irn)) {
734 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
735 bitset_set(live, get_irn_graph_nr(irn));
736 border_use(irn, step, 0);
742 * Determine the last uses of a value inside the block, since they are
743 * relevant for the interval borders.
745 sched_foreach_reverse(block, irn) {
746 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
747 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
750 * If the node defines some value, which can put into a
751 * register of the current class, make a border for it.
753 if(has_reg_class(env, irn)) {
754 int nr = get_irn_graph_nr(irn);
756 bitset_clear(live, nr);
757 border_def(irn, step, 1);
761 * If the node is no phi node we can examine the uses.
764 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
765 ir_node *op = get_irn_n(irn, i);
767 if(has_reg_class(env, op)) {
768 int nr = get_irn_graph_nr(op);
770 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
772 if(!bitset_is_set(live, nr)) {
773 border_use(op, step, 1);
774 bitset_set(live, nr);
783 * Add initial defs for all values live in.
785 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
786 if(has_reg_class(env, irn)) {
788 /* Mark the value live in. */
789 bitset_set(live, get_irn_graph_nr(irn));
792 border_def(irn, step, 0);
801 static void assign(ir_node *block, void *env_ptr)
803 be_chordal_alloc_env_t *alloc_env = env_ptr;
804 be_chordal_env_t *env = alloc_env->chordal_env;
805 firm_dbg_module_t *dbg = env->dbg;
806 bitset_t *live = alloc_env->live;
807 bitset_t *colors = alloc_env->colors;
808 bitset_t *in_colors = alloc_env->in_colors;
809 const arch_env_t *arch_env = env->birg->main_env->arch_env;
813 struct list_head *head = get_block_border_head(env, block);
814 pset *live_in = put_live_in(block, pset_new_ptr_default());
816 bitset_clear_all(colors);
817 bitset_clear_all(live);
818 bitset_clear_all(in_colors);
820 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
821 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
822 list_for_each_entry(border_t, b, head, list) {
823 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
824 b->irn, get_irn_graph_nr(b->irn)));
828 * Add initial defs for all values live in.
829 * Since their colors have already been assigned (The dominators were
830 * allocated before), we have to mark their colors as used also.
832 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
833 if(has_reg_class(env, irn)) {
834 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
837 assert(reg && "Node must have been assigned a register");
838 col = arch_register_get_index(reg);
840 /* Mark the color of the live in value as used. */
841 bitset_set(colors, col);
842 bitset_set(in_colors, col);
844 /* Mark the value live in. */
845 bitset_set(live, get_irn_graph_nr(irn));
850 * Mind that the sequence
851 * of defs from back to front defines a perfect
852 * elimination order. So, coloring the definitions from first to last
855 list_for_each_entry_reverse(border_t, b, head, list) {
856 ir_node *irn = b->irn;
857 int nr = get_irn_graph_nr(irn);
860 * Assign a color, if it is a local def. Global defs already have a
863 if(b->is_def && !is_live_in(block, irn)) {
864 const arch_register_t *reg;
867 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
868 reg = arch_get_irn_register(arch_env, irn);
870 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
874 col = get_next_free_reg(alloc_env, colors);
875 reg = arch_register_for_index(env->cls, col);
876 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
877 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
880 bitset_set(colors, col);
881 arch_set_irn_register(arch_env, irn, reg);
883 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
884 arch_register_get_name(reg), col, irn));
886 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
887 bitset_set(live, nr);
890 /* Clear the color upon a use. */
891 else if(!b->is_def) {
892 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
895 assert(reg && "Register must have been assigned");
897 col = arch_register_get_index(reg);
898 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
900 bitset_clear(colors, col);
901 bitset_clear(live, nr);
908 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
910 be_chordal_alloc_env_t env;
914 int colors_n = arch_register_class_n_regs(chordal_env->cls);
915 ir_graph *irg = chordal_env->irg;
918 if(get_irg_dom_state(irg) != dom_consistent)
921 env.chordal_env = chordal_env;
922 env.colors_n = colors_n;
923 env.colors = bitset_alloca(colors_n);
924 env.tmp_colors = bitset_alloca(colors_n);
925 env.in_colors = bitset_alloca(colors_n);
926 env.ignore_regs = bitset_alloca(colors_n);
927 env.pre_colored = pset_new_ptr_default();
928 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
930 for(i = 0; i < colors_n; ++i)
931 if(arch_register_type_is(&chordal_env->cls->regs[i], ignore))
932 bitset_set(env.ignore_regs, i);
934 /* Handle register targeting constraints */
935 dom_tree_walk_irg(irg, constraints, NULL, &env);
937 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
938 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
939 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
943 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
945 /* First, determine the pressure */
946 dom_tree_walk_irg(irg, pressure, NULL, &env);
948 /* Assign the colors */
949 dom_tree_walk_irg(irg, assign, NULL, &env);
951 be_numbering_done(irg);
953 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
955 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
956 plotter = new_plotter_ps(buf);
957 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
958 plotter_free(plotter);
961 del_pset(env.pre_colored);