2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
28 #include "raw_bitset.h"
30 #include "bipartite.h"
31 #include "hungarian.h"
34 #include "irgraph_t.h"
35 #include "irprintf_t.h"
45 #include "besched_t.h"
52 #include "bestatevent.h"
55 #include "bechordal_t.h"
56 #include "bechordal_draw.h"
58 #define DBG_LEVEL SET_LEVEL_0
59 #define DBG_LEVEL_CHECK SET_LEVEL_0
63 #define DUMP_INTERVALS
65 typedef struct _be_chordal_alloc_env_t {
66 be_chordal_env_t *chordal_env;
68 pset *pre_colored; /**< Set of precolored nodes. */
69 bitset_t *live; /**< A liveness bitset. */
70 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
71 bitset_t *colors; /**< The color mask. */
72 bitset_t *in_colors; /**< Colors used by live in values. */
73 int colors_n; /**< The number of colors. */
74 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
75 } be_chordal_alloc_env_t;
79 /* Make a fourcc for border checking. */
80 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
83 static void check_border_list(struct list_head *head)
86 list_for_each_entry(border_t, x, head, list) {
87 assert(x->magic == BORDER_FOURCC);
91 static void check_heads(be_chordal_env_t *env)
94 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
95 /* ir_printf("checking border list of block %+F\n", ent->key); */
96 check_border_list(ent->value);
102 * Add an interval border to the list of a block's list
103 * of interval border.
104 * @note You always have to create the use before the def.
105 * @param env The environment.
106 * @param head The list head to enqueue the borders.
107 * @param irn The node (value) the border belongs to.
108 * @param pressure The pressure at this point in time.
109 * @param step A time step for the border.
110 * @param is_def Is the border a use or a def.
111 * @return The created border.
113 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
114 ir_node *irn, unsigned step, unsigned pressure,
115 unsigned is_def, unsigned is_real)
122 b = obstack_alloc(&env->obst, sizeof(*b));
124 /* also allocate the def and tie it to the use. */
125 def = obstack_alloc(&env->obst, sizeof(*def));
126 memset(def, 0, sizeof(*def));
131 * Set the link field of the irn to the def.
132 * This strongly relies on the fact, that the use is always
133 * made before the def.
135 set_irn_link(irn, def);
137 DEBUG_ONLY(b->magic = BORDER_FOURCC);
138 DEBUG_ONLY(def->magic = BORDER_FOURCC);
142 * If the def is encountered, the use was made and so was the
143 * the def node (see the code above). It was placed into the
144 * link field of the irn, so we can get it there.
147 b = get_irn_link(irn);
149 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
152 b->pressure = pressure;
154 b->is_real = is_real;
157 list_add_tail(&b->list, head);
158 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
165 * Check, if an irn is of the register class currently under processing.
166 * @param env The chordal environment.
167 * @param irn The node.
168 * @return 1, if the node is of that register class, 0 if not.
170 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
172 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
173 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
176 #define has_limited_constr(req, irn) \
177 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
179 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
181 bitset_t *tmp = alloc_env->tmp_colors;
182 bitset_copy(tmp, colors);
183 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
184 return bitset_next_clear(tmp, 0);
187 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
192 bitset_copy(bs, o2->regs);
197 bitset_copy(bs, o1->regs);
201 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
203 if(bitset_contains(o1->regs, o2->regs))
204 bitset_copy(bs, o1->regs);
205 else if(bitset_contains(o2->regs, o1->regs))
206 bitset_copy(bs, o2->regs);
213 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
217 ie.ignore_colors = env->ignore_colors;
218 ie.aenv = env->birg->main_env->arch_env;
219 ie.obst = &env->obst;
221 return be_scan_insn(&ie, irn);
224 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
226 const arch_env_t *aenv = env->birg->main_env->arch_env;
227 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
228 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
229 ir_node *bl = get_nodes_block(irn);
230 be_lv_t *lv = env->birg->lv;
235 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
236 ir_node *op = get_irn_n(irn, i);
238 const arch_register_t *reg;
239 const arch_register_req_t *req;
241 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
244 reg = arch_get_irn_register(aenv, op);
246 if (reg == NULL || !arch_register_type_is(reg, ignore))
248 if(arch_register_type_is(reg, joker))
251 req = arch_get_register_req(aenv, irn, i);
252 if (!arch_register_req_is(req, limited))
255 if (rbitset_is_set(req->limited, reg->index))
258 copy = be_new_Copy(env->cls, env->irg, bl, op);
259 be_stat_ev("constr_copy", 1);
261 sched_add_before(irn, copy);
262 set_irn_n(irn, i, copy);
263 DBG((env->dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
266 insn = chordal_scan_insn(env, irn);
268 if(!insn->has_constraints)
271 /* insert copies for nodes that occur constrained more than once. */
272 for(i = insn->use_start; i < insn->n_ops; ++i) {
273 be_operand_t *op = &insn->ops[i];
275 if(!op->has_constraints)
278 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)
285 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
286 be_stat_ev("constr_copy", 1);
288 sched_add_before(insn->irn, copy);
289 set_irn_n(insn->irn, a_op->pos, copy);
290 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) {
307 be_operand_t *op = &insn->ops[i];
309 bitset_copy(tmp, op->regs);
310 bitset_and(tmp, def_constr);
314 1) the operand is constrained.
315 2) lives through the node.
316 3) is constrained to a register occuring in out constraints.
318 if(!op->has_constraints ||
319 !values_interfere(lv, insn->irn, op->carrier) ||
320 bitset_popcnt(tmp) == 0)
324 only create the copy if the operand is no copy.
325 this is necessary since the assure constraints phase inserts
326 Copies and Keeps for operands which must be different from the results.
327 Additional copies here would destroy this.
329 if(be_is_Copy(op->carrier))
332 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
334 sched_add_before(insn->irn, copy);
335 set_irn_n(insn->irn, op->pos, copy);
336 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
337 be_liveness_update(lv, op->carrier);
341 obstack_free(&env->obst, insn);
342 return insn->next_insn;
345 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
347 be_chordal_env_t *env = data;
349 for(irn = sched_first(bl); !sched_is_end(irn);) {
350 irn = prepare_constr_insn(env, irn);
354 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
355 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
358 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
360 const be_chordal_env_t *env = alloc_env->chordal_env;
362 int n_uses = be_insn_n_uses(insn);
363 int n_defs = be_insn_n_defs(insn);
364 bitset_t *bs = bitset_alloca(env->cls->n_regs);
365 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
366 be_lv_t *lv = env->birg->lv;
371 For each out operand, try to find an in operand which can be assigned the
372 same register as the out operand.
374 for (j = 0; j < insn->use_start; ++j) {
376 int smallest_n_regs = 2 * env->cls->n_regs + 1;
377 be_operand_t *out_op = &insn->ops[j];
379 /* Try to find an in operand which has ... */
380 for(i = insn->use_start; i < insn->n_ops; ++i) {
382 const be_operand_t *op = &insn->ops[i];
384 if (op->partner != NULL)
386 if (values_interfere(lv, op->irn, op->carrier))
389 bitset_clear_all(bs);
390 bitset_copy(bs, op->regs);
391 bitset_and(bs, out_op->regs);
392 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
394 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
396 smallest_n_regs = n_total;
401 be_operand_t *partner = &insn->ops[smallest];
402 out_op->partner = partner;
403 partner->partner = out_op;
409 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
410 be_insn_t **the_insn)
412 be_chordal_env_t *env = alloc_env->chordal_env;
413 const arch_env_t *aenv = env->birg->main_env->arch_env;
414 be_insn_t *insn = *the_insn;
415 ir_node *perm = NULL;
416 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
417 be_lv_t *lv = env->birg->lv;
418 const ir_edge_t *edge;
421 assert(insn->has_constraints && "only do this for constrained nodes");
424 Collect all registers that occur in output constraints.
425 This is necessary, since if the insn has one of these as an input constraint
426 and the corresponding operand interferes with the insn, the operand must
429 for(i = 0; i < insn->use_start; ++i) {
430 be_operand_t *op = &insn->ops[i];
431 if(op->has_constraints)
432 bitset_or(out_constr, op->regs);
436 Make the Perm, recompute liveness and re-scan the insn since the
437 in operands are now the Projs of the Perm.
439 perm = insert_Perm_after(aenv, lv, env->cls, env->birg->dom_front, sched_prev(insn->irn));
441 /* Registers are propagated by insert_Perm_after(). Clean them here! */
445 be_stat_ev("constr_perm", get_irn_arity(perm));
446 foreach_out_edge(perm, edge) {
447 ir_node *proj = get_edge_src_irn(edge);
448 arch_set_irn_register(aenv, proj, NULL);
452 We also have to re-build the insn since the input operands are now the Projs of
453 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
454 the live sets may change.
456 // be_liveness_recompute(lv);
457 obstack_free(&env->obst, insn);
458 *the_insn = insn = chordal_scan_insn(env, insn->irn);
461 Copy the input constraints of the insn to the Perm as output
462 constraints. Succeeding phases (coalescing) will need that.
464 for(i = insn->use_start; i < insn->n_ops; ++i) {
465 be_operand_t *op = &insn->ops[i];
466 ir_node *proj = op->carrier;
468 Note that the predecessor must not be a Proj of the Perm,
469 since ignore-nodes are not Perm'ed.
471 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
472 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
479 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
481 const arch_env_t *aenv;
484 ir_node **alloc_nodes;
485 hungarian_problem_t *bp;
488 DEBUG_ONLY(firm_dbg_module_t *dbg);
491 const ir_edge_t *edge;
492 ir_node *perm = NULL;
494 be_chordal_env_t *env = alloc_env->chordal_env;
495 void *base = obstack_base(&env->obst);
496 be_insn_t *insn = chordal_scan_insn(env, irn);
497 ir_node *res = insn->next_insn;
498 int be_silent = *silent;
499 be_lv_t *lv = env->birg->lv;
501 if(insn->pre_colored) {
503 for(i = 0; i < insn->use_start; ++i)
504 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
508 If the current node is a barrier toggle the silent flag.
509 If we are in the start block, we are ought to be silent at the beginning,
510 so the toggling activates the constraint handling but skips the barrier.
511 If we are in the end block we handle the in requirements of the barrier
512 and set the rest to silent.
514 if(be_is_Barrier(irn))
521 Perms inserted before the constraint handling phase are considered to be
522 correctly precolored. These Perms arise during the ABI handling phase.
524 if(!insn->has_constraints)
527 aenv = env->birg->main_env->arch_env;
528 n_regs = env->cls->n_regs;
529 bs = bitset_alloca(n_regs);
530 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
531 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
532 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
533 assignment = alloca(n_regs * sizeof(assignment[0]));
534 partners = pmap_create();
535 DEBUG_ONLY(dbg = alloc_env->constr_dbg;)
538 prepare the constraint handling of this node.
539 Perms are constructed and Copies are created for constrained values
540 interfering with the instruction.
542 perm = pre_process_constraints(alloc_env, &insn);
544 /* find suitable in operands to the out operands of the node. */
545 pair_up_operands(alloc_env, insn);
548 look at the in/out operands and add each operand (and its possible partner)
549 to a bipartite graph (left: nodes with partners, right: admissible colors).
551 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
552 be_operand_t *op = &insn->ops[i];
555 If the operand has no partner or the partner has not been marked
556 for allocation, determine the admissible registers and mark it
557 for allocation by associating the node and its partner with the
558 set of admissible registers via a bipartite graph.
560 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
562 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
563 alloc_nodes[n_alloc] = op->carrier;
565 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
567 bitset_clear_all(bs);
568 get_decisive_partner_regs(bs, op, op->partner);
570 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
572 bitset_foreach(bs, col) {
573 hungarian_add(bp, n_alloc, col, 1);
574 // bipartite_add(bp, n_alloc, col);
582 Put all nodes which live through the constrained instruction also to the
583 allocation bipartite graph. They are considered unconstrained.
586 foreach_out_edge(perm, edge) {
587 ir_node *proj = get_edge_src_irn(edge);
589 assert(is_Proj(proj));
591 if(!values_interfere(lv, proj, irn) || pmap_contains(partners, proj))
594 assert(n_alloc < n_regs);
595 alloc_nodes[n_alloc] = proj;
596 pmap_insert(partners, proj, NULL);
598 bitset_clear_all(bs);
599 arch_put_non_ignore_regs(aenv, env->cls, bs);
600 bitset_andnot(bs, env->ignore_colors);
601 bitset_foreach(bs, col) {
602 hungarian_add(bp, n_alloc, col, 1);
603 // bipartite_add(bp, n_alloc, col);
610 /* Compute a valid register allocation. */
611 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
612 match_res = hungarian_solve(bp, assignment, &cost, 1);
613 assert(match_res == 0 && "matching failed");
614 //bipartite_matching(bp, assignment);
616 /* Assign colors obtained from the matching. */
617 for(i = 0; i < n_alloc; ++i) {
618 const arch_register_t *reg;
622 assert(assignment[i] >= 0 && "there must have been a register assigned");
623 reg = arch_register_for_index(env->cls, assignment[i]);
625 nodes[0] = alloc_nodes[i];
626 nodes[1] = pmap_get(partners, alloc_nodes[i]);
628 for(j = 0; j < 2; ++j) {
632 arch_set_irn_register(aenv, nodes[j], reg);
633 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
634 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
638 /* Allocate the non-constrained Projs of the Perm. */
640 bitset_clear_all(bs);
642 /* Put the colors of all Projs in a bitset. */
643 foreach_out_edge(perm, edge) {
644 ir_node *proj = get_edge_src_irn(edge);
645 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
648 bitset_set(bs, reg->index);
651 /* Assign the not yet assigned Projs of the Perm a suitable color. */
652 foreach_out_edge(perm, edge) {
653 ir_node *proj = get_edge_src_irn(edge);
654 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
656 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
659 col = get_next_free_reg(alloc_env, bs);
660 reg = arch_register_for_index(env->cls, col);
661 bitset_set(bs, reg->index);
662 arch_set_irn_register(aenv, proj, reg);
663 pset_insert_ptr(alloc_env->pre_colored, proj);
664 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
669 //bipartite_free(bp);
671 pmap_destroy(partners);
674 obstack_free(&env->obst, base);
679 * Handle constraint nodes in each basic block.
680 * handle_constraints() inserts Perm nodes which perm
681 * over all values live at the constrained node right in front
682 * of the constrained node. These Perms signal a constrained node.
683 * For further comments, refer to handle_constraints().
685 static void constraints(ir_node *bl, void *data)
687 be_chordal_alloc_env_t *env = data;
690 Start silent in the start block.
691 The silence remains until the first barrier is seen.
692 Each other block is begun loud.
694 int silent = bl == get_irg_start_block(get_irn_irg(bl));
698 If the block is the start block search the barrier and
699 start handling constraints from there.
702 for(irn = sched_first(bl); !sched_is_end(irn);) {
703 irn = handle_constraints(env, irn, &silent);
708 * Annotate the register pressure to the nodes and compute
709 * the liveness intervals.
710 * @param block The block to do it for.
711 * @param env_ptr The environment.
713 static void pressure(ir_node *block, void *env_ptr)
715 /* Convenience macro for a def */
716 #define border_def(irn, step, real) \
717 border_add(env, head, irn, step, pressure--, 1, real)
719 /* Convenience macro for a use */
720 #define border_use(irn, step, real) \
721 border_add(env, head, irn, step, ++pressure, 0, real)
723 be_chordal_alloc_env_t *alloc_env = env_ptr;
724 be_chordal_env_t *env = alloc_env->chordal_env;
725 bitset_t *live = alloc_env->live;
727 be_lv_t *lv = env->birg->lv;
728 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
732 unsigned pressure = 0;
733 struct list_head *head;
734 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
735 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
737 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
738 bitset_clear_all(live);
740 /* Set up the border list in the block info */
741 head = obstack_alloc(&env->obst, sizeof(*head));
742 INIT_LIST_HEAD(head);
743 assert(pmap_get(env->border_heads, block) == NULL);
744 pmap_insert(env->border_heads, block, head);
747 * Make final uses of all values live out of the block.
748 * They are necessary to build up real intervals.
750 foreach_pset(live_end, irn) {
751 if(has_reg_class(env, irn)) {
752 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
753 bitset_set(live, get_irn_idx(irn));
754 border_use(irn, step, 0);
760 * Determine the last uses of a value inside the block, since they are
761 * relevant for the interval borders.
763 sched_foreach_reverse(block, irn) {
764 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
765 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
768 * If the node defines some value, which can put into a
769 * register of the current class, make a border for it.
771 if(has_reg_class(env, irn)) {
772 int nr = get_irn_idx(irn);
774 bitset_clear(live, nr);
775 border_def(irn, step, 1);
779 * If the node is no phi node we can examine the uses.
782 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
783 ir_node *op = get_irn_n(irn, i);
785 if(has_reg_class(env, op)) {
786 int nr = get_irn_idx(op);
787 const char *msg = "-";
789 if(!bitset_is_set(live, nr)) {
790 border_use(op, step, 1);
791 bitset_set(live, nr);
795 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
803 * Add initial defs for all values live in.
805 foreach_pset(live_in, irn) {
806 if(has_reg_class(env, irn)) {
808 /* Mark the value live in. */
809 bitset_set(live, get_irn_idx(irn));
812 border_def(irn, step, 0);
820 static void assign(ir_node *block, void *env_ptr)
822 be_chordal_alloc_env_t *alloc_env = env_ptr;
823 be_chordal_env_t *env = alloc_env->chordal_env;
824 bitset_t *live = alloc_env->live;
825 bitset_t *colors = alloc_env->colors;
826 bitset_t *in_colors = alloc_env->in_colors;
827 const arch_env_t *arch_env = env->birg->main_env->arch_env;
828 struct list_head *head = get_block_border_head(env, block);
829 be_lv_t *lv = env->birg->lv;
830 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
834 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
836 bitset_clear_all(colors);
837 bitset_clear_all(live);
838 bitset_clear_all(in_colors);
840 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
841 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
842 list_for_each_entry(border_t, b, head, list) {
843 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
844 b->irn, get_irn_idx(b->irn)));
848 * Add initial defs for all values live in.
849 * Since their colors have already been assigned (The dominators were
850 * allocated before), we have to mark their colors as used also.
852 foreach_pset(live_in, irn) {
853 if(has_reg_class(env, irn)) {
854 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
857 assert(reg && "Node must have been assigned a register");
858 col = arch_register_get_index(reg);
860 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
862 /* Mark the color of the live in value as used. */
863 bitset_set(colors, col);
864 bitset_set(in_colors, col);
866 /* Mark the value live in. */
867 bitset_set(live, get_irn_idx(irn));
872 * Mind that the sequence of defs from back to front defines a perfect
873 * elimination order. So, coloring the definitions from first to last
876 list_for_each_entry_reverse(border_t, b, head, list) {
877 ir_node *irn = b->irn;
878 int nr = get_irn_idx(irn);
879 int ignore = arch_irn_is(arch_env, irn, ignore);
882 * Assign a color, if it is a local def. Global defs already have a
885 if(b->is_def && !be_is_live_in(lv, block, irn)) {
886 const arch_register_t *reg;
889 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
890 reg = arch_get_irn_register(arch_env, irn);
892 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
894 col = get_next_free_reg(alloc_env, colors);
895 reg = arch_register_for_index(env->cls, col);
896 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
897 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
900 bitset_set(colors, col);
901 arch_set_irn_register(arch_env, irn, reg);
903 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
905 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
906 bitset_set(live, nr);
909 /* Clear the color upon a use. */
910 else if(!b->is_def) {
911 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
914 assert(reg && "Register must have been assigned");
916 col = arch_register_get_index(reg);
917 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
919 bitset_clear(colors, col);
920 bitset_clear(live, nr);
927 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
929 be_chordal_alloc_env_t env;
931 be_irg_t *birg = chordal_env->birg;
933 int colors_n = arch_register_class_n_regs(chordal_env->cls);
934 ir_graph *irg = chordal_env->irg;
937 be_assure_dom_front(birg);
938 be_assure_liveness(birg);
941 env.chordal_env = chordal_env;
942 env.colors_n = colors_n;
943 env.colors = bitset_alloca(colors_n);
944 env.tmp_colors = bitset_alloca(colors_n);
945 env.in_colors = bitset_alloca(colors_n);
946 env.pre_colored = pset_new_ptr_default();
947 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
950 /* Handle register targeting constraints */
951 dom_tree_walk_irg(irg, constraints, NULL, &env);
953 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
954 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
955 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
958 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
960 /* First, determine the pressure */
961 dom_tree_walk_irg(irg, pressure, NULL, &env);
963 /* Assign the colors */
964 dom_tree_walk_irg(irg, assign, NULL, &env);
966 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
968 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
969 plotter = new_plotter_ps(buf);
970 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
971 plotter_free(plotter);
974 bitset_free(env.live);
975 del_pset(env.pre_colored);