2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Chordal register allocation.
23 * @author Sebastian Hack
37 #include "raw_bitset.h"
39 #include "bipartite.h"
40 #include "hungarian.h"
43 #include "irgraph_t.h"
44 #include "irprintf_t.h"
54 #include "besched_t.h"
61 #include "bestatevent.h"
64 #include "bechordal_t.h"
65 #include "bechordal_draw.h"
68 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
72 #define DUMP_INTERVALS
74 typedef struct _be_chordal_alloc_env_t {
75 be_chordal_env_t *chordal_env;
77 pset *pre_colored; /**< Set of precolored nodes. */
78 bitset_t *live; /**< A liveness bitset. */
79 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
80 bitset_t *colors; /**< The color mask. */
81 bitset_t *in_colors; /**< Colors used by live in values. */
82 int colors_n; /**< The number of colors. */
83 } be_chordal_alloc_env_t;
87 /* Make a fourcc for border checking. */
88 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
91 static void check_border_list(struct list_head *head)
94 list_for_each_entry(border_t, x, head, list) {
95 assert(x->magic == BORDER_FOURCC);
99 static void check_heads(be_chordal_env_t *env)
102 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
103 /* ir_printf("checking border list of block %+F\n", ent->key); */
104 check_border_list(ent->value);
110 * Add an interval border to the list of a block's list
111 * of interval border.
112 * @note You always have to create the use before the def.
113 * @param env The environment.
114 * @param head The list head to enqueue the borders.
115 * @param irn The node (value) the border belongs to.
116 * @param pressure The pressure at this point in time.
117 * @param step A time step for the border.
118 * @param is_def Is the border a use or a def.
119 * @return The created border.
121 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
122 ir_node *irn, unsigned step, unsigned pressure,
123 unsigned is_def, unsigned is_real)
130 b = obstack_alloc(env->obst, sizeof(*b));
132 /* also allocate the def and tie it to the use. */
133 def = obstack_alloc(env->obst, sizeof(*def));
134 memset(def, 0, sizeof(*def));
139 * Set the link field of the irn to the def.
140 * This strongly relies on the fact, that the use is always
141 * made before the def.
143 set_irn_link(irn, def);
145 DEBUG_ONLY(b->magic = BORDER_FOURCC);
146 DEBUG_ONLY(def->magic = BORDER_FOURCC);
150 * If the def is encountered, the use was made and so was the
151 * the def node (see the code above). It was placed into the
152 * link field of the irn, so we can get it there.
155 b = get_irn_link(irn);
157 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
160 b->pressure = pressure;
162 b->is_real = is_real;
165 list_add_tail(&b->list, head);
166 DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
173 * Check, if an irn is of the register class currently under processing.
174 * @param env The chordal environment.
175 * @param irn The node.
176 * @return 1, if the node is of that register class, 0 if not.
178 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
180 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
181 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
184 #define has_limited_constr(req, irn) \
185 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
187 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
189 bitset_t *tmp = alloc_env->tmp_colors;
190 bitset_copy(tmp, colors);
191 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
192 return bitset_next_clear(tmp, 0);
195 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
200 bitset_copy(bs, o2->regs);
205 bitset_copy(bs, o1->regs);
209 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
211 if(bitset_contains(o1->regs, o2->regs))
212 bitset_copy(bs, o1->regs);
213 else if(bitset_contains(o2->regs, o1->regs))
214 bitset_copy(bs, o2->regs);
221 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
225 ie.ignore_colors = env->ignore_colors;
226 ie.aenv = env->birg->main_env->arch_env;
229 return be_scan_insn(&ie, irn);
232 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
234 const arch_env_t *aenv = env->birg->main_env->arch_env;
235 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
236 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
237 ir_node *bl = get_nodes_block(irn);
238 be_lv_t *lv = env->birg->lv;
243 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
244 ir_node *op = get_irn_n(irn, i);
246 const arch_register_t *reg;
247 const arch_register_req_t *req;
249 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
252 reg = arch_get_irn_register(aenv, op);
254 if (reg == NULL || !arch_register_type_is(reg, ignore))
256 if(arch_register_type_is(reg, joker))
259 req = arch_get_register_req(aenv, irn, i);
260 if (!arch_register_req_is(req, limited))
263 if (rbitset_is_set(req->limited, reg->index))
266 copy = be_new_Copy(env->cls, env->irg, bl, op);
267 be_stat_ev("constr_copy", 1);
269 sched_add_before(irn, copy);
270 set_irn_n(irn, i, copy);
271 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
274 insn = chordal_scan_insn(env, irn);
276 if(!insn->has_constraints)
279 /* insert copies for nodes that occur constrained more than once. */
280 for(i = insn->use_start; i < insn->n_ops; ++i) {
281 be_operand_t *op = &insn->ops[i];
283 if(!op->has_constraints)
286 for(j = i + 1; j < insn->n_ops; ++j) {
288 be_operand_t *a_op = &insn->ops[j];
290 if(a_op->carrier != op->carrier || !a_op->has_constraints)
293 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
294 be_stat_ev("constr_copy", 1);
296 sched_add_before(insn->irn, copy);
297 set_irn_n(insn->irn, a_op->pos, copy);
298 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
302 /* collect all registers occuring in out constraints. */
303 for(i = 0; i < insn->use_start; ++i) {
304 be_operand_t *op = &insn->ops[i];
305 if(op->has_constraints)
306 bitset_or(def_constr, op->regs);
310 insert copies for all constrained arguments living through the node
311 and being constrained to a register which also occurs in out constraints.
313 for(i = insn->use_start; i < insn->n_ops; ++i) {
315 be_operand_t *op = &insn->ops[i];
317 bitset_copy(tmp, op->regs);
318 bitset_and(tmp, def_constr);
322 1) the operand is constrained.
323 2) lives through the node.
324 3) is constrained to a register occuring in out constraints.
326 if(!op->has_constraints ||
327 !values_interfere(lv, insn->irn, op->carrier) ||
328 bitset_popcnt(tmp) == 0)
332 only create the copy if the operand is no copy.
333 this is necessary since the assure constraints phase inserts
334 Copies and Keeps for operands which must be different from the results.
335 Additional copies here would destroy this.
337 if(be_is_Copy(op->carrier))
340 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
342 sched_add_before(insn->irn, copy);
343 set_irn_n(insn->irn, op->pos, copy);
344 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
345 be_liveness_update(lv, op->carrier);
349 obstack_free(env->obst, insn);
350 return insn->next_insn;
353 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
355 be_chordal_env_t *env = data;
357 for(irn = sched_first(bl); !sched_is_end(irn);) {
358 irn = prepare_constr_insn(env, irn);
362 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
363 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
366 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
368 const be_chordal_env_t *env = alloc_env->chordal_env;
370 int n_uses = be_insn_n_uses(insn);
371 int n_defs = be_insn_n_defs(insn);
372 bitset_t *bs = bitset_alloca(env->cls->n_regs);
373 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
374 be_lv_t *lv = env->birg->lv;
379 For each out operand, try to find an in operand which can be assigned the
380 same register as the out operand.
382 for (j = 0; j < insn->use_start; ++j) {
384 int smallest_n_regs = 2 * env->cls->n_regs + 1;
385 be_operand_t *out_op = &insn->ops[j];
387 /* Try to find an in operand which has ... */
388 for(i = insn->use_start; i < insn->n_ops; ++i) {
390 const be_operand_t *op = &insn->ops[i];
392 if (op->partner != NULL)
394 if (values_interfere(lv, op->irn, op->carrier))
397 bitset_clear_all(bs);
398 bitset_copy(bs, op->regs);
399 bitset_and(bs, out_op->regs);
400 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
402 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
404 smallest_n_regs = n_total;
409 be_operand_t *partner = &insn->ops[smallest];
410 out_op->partner = partner;
411 partner->partner = out_op;
417 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
418 be_insn_t **the_insn)
420 be_chordal_env_t *env = alloc_env->chordal_env;
421 const arch_env_t *aenv = env->birg->main_env->arch_env;
422 be_insn_t *insn = *the_insn;
423 ir_node *perm = NULL;
424 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
425 const ir_edge_t *edge;
428 assert(insn->has_constraints && "only do this for constrained nodes");
431 Collect all registers that occur in output constraints.
432 This is necessary, since if the insn has one of these as an input constraint
433 and the corresponding operand interferes with the insn, the operand must
436 for(i = 0; i < insn->use_start; ++i) {
437 be_operand_t *op = &insn->ops[i];
438 if(op->has_constraints)
439 bitset_or(out_constr, op->regs);
443 Make the Perm, recompute liveness and re-scan the insn since the
444 in operands are now the Projs of the Perm.
446 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
448 /* Registers are propagated by insert_Perm_after(). Clean them here! */
452 be_stat_ev("constr_perm", get_irn_arity(perm));
453 foreach_out_edge(perm, edge) {
454 ir_node *proj = get_edge_src_irn(edge);
455 arch_set_irn_register(aenv, proj, NULL);
459 We also have to re-build the insn since the input operands are now the Projs of
460 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
461 the live sets may change.
463 // be_liveness_recompute(lv);
464 obstack_free(env->obst, insn);
465 *the_insn = insn = chordal_scan_insn(env, insn->irn);
468 Copy the input constraints of the insn to the Perm as output
469 constraints. Succeeding phases (coalescing) will need that.
471 for(i = insn->use_start; i < insn->n_ops; ++i) {
472 be_operand_t *op = &insn->ops[i];
473 ir_node *proj = op->carrier;
475 Note that the predecessor must not be a Proj of the Perm,
476 since ignore-nodes are not Perm'ed.
478 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
479 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
486 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
488 const arch_env_t *aenv;
491 ir_node **alloc_nodes;
492 hungarian_problem_t *bp;
497 const ir_edge_t *edge;
498 ir_node *perm = NULL;
500 be_chordal_env_t *env = alloc_env->chordal_env;
501 void *base = obstack_base(env->obst);
502 be_insn_t *insn = chordal_scan_insn(env, irn);
503 ir_node *res = insn->next_insn;
504 int be_silent = *silent;
505 be_lv_t *lv = env->birg->lv;
507 if(insn->pre_colored) {
509 for(i = 0; i < insn->use_start; ++i)
510 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
514 If the current node is a barrier toggle the silent flag.
515 If we are in the start block, we are ought to be silent at the beginning,
516 so the toggling activates the constraint handling but skips the barrier.
517 If we are in the end block we handle the in requirements of the barrier
518 and set the rest to silent.
520 if(be_is_Barrier(irn))
527 Perms inserted before the constraint handling phase are considered to be
528 correctly precolored. These Perms arise during the ABI handling phase.
530 if(!insn->has_constraints)
533 aenv = env->birg->main_env->arch_env;
534 n_regs = env->cls->n_regs;
535 bs = bitset_alloca(n_regs);
536 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
537 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
538 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
539 assignment = alloca(n_regs * sizeof(assignment[0]));
540 partners = pmap_create();
543 prepare the constraint handling of this node.
544 Perms are constructed and Copies are created for constrained values
545 interfering with the instruction.
547 perm = pre_process_constraints(alloc_env, &insn);
549 /* find suitable in operands to the out operands of the node. */
550 pair_up_operands(alloc_env, insn);
553 look at the in/out operands and add each operand (and its possible partner)
554 to a bipartite graph (left: nodes with partners, right: admissible colors).
556 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
557 be_operand_t *op = &insn->ops[i];
560 If the operand has no partner or the partner has not been marked
561 for allocation, determine the admissible registers and mark it
562 for allocation by associating the node and its partner with the
563 set of admissible registers via a bipartite graph.
565 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
567 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
568 alloc_nodes[n_alloc] = op->carrier;
570 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
572 bitset_clear_all(bs);
573 get_decisive_partner_regs(bs, op, op->partner);
575 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
577 bitset_foreach(bs, col) {
578 hungarian_add(bp, n_alloc, col, 1);
579 // bipartite_add(bp, n_alloc, col);
587 Put all nodes which live through the constrained instruction also to the
588 allocation bipartite graph. They are considered unconstrained.
591 foreach_out_edge(perm, edge) {
592 ir_node *proj = get_edge_src_irn(edge);
594 assert(is_Proj(proj));
596 if(!values_interfere(lv, proj, irn) || pmap_contains(partners, proj))
599 assert(n_alloc < n_regs);
600 alloc_nodes[n_alloc] = proj;
601 pmap_insert(partners, proj, NULL);
603 bitset_clear_all(bs);
604 arch_put_non_ignore_regs(aenv, env->cls, bs);
605 bitset_andnot(bs, env->ignore_colors);
606 bitset_foreach(bs, col) {
607 hungarian_add(bp, n_alloc, col, 1);
608 // bipartite_add(bp, n_alloc, col);
615 /* Compute a valid register allocation. */
616 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
617 match_res = hungarian_solve(bp, assignment, &cost, 1);
618 assert(match_res == 0 && "matching failed");
619 //bipartite_matching(bp, assignment);
621 /* Assign colors obtained from the matching. */
622 for(i = 0; i < n_alloc; ++i) {
623 const arch_register_t *reg;
627 assert(assignment[i] >= 0 && "there must have been a register assigned");
628 reg = arch_register_for_index(env->cls, assignment[i]);
630 nodes[0] = alloc_nodes[i];
631 nodes[1] = pmap_get(partners, alloc_nodes[i]);
633 for(j = 0; j < 2; ++j) {
637 arch_set_irn_register(aenv, nodes[j], reg);
638 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
639 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
643 /* Allocate the non-constrained Projs of the Perm. */
645 bitset_clear_all(bs);
647 /* Put the colors of all Projs in a bitset. */
648 foreach_out_edge(perm, edge) {
649 ir_node *proj = get_edge_src_irn(edge);
650 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
653 bitset_set(bs, reg->index);
656 /* Assign the not yet assigned Projs of the Perm a suitable color. */
657 foreach_out_edge(perm, edge) {
658 ir_node *proj = get_edge_src_irn(edge);
659 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
661 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
664 col = get_next_free_reg(alloc_env, bs);
665 reg = arch_register_for_index(env->cls, col);
666 bitset_set(bs, reg->index);
667 arch_set_irn_register(aenv, proj, reg);
668 pset_insert_ptr(alloc_env->pre_colored, proj);
669 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
674 //bipartite_free(bp);
676 pmap_destroy(partners);
679 obstack_free(env->obst, base);
684 * Handle constraint nodes in each basic block.
685 * handle_constraints() inserts Perm nodes which perm
686 * over all values live at the constrained node right in front
687 * of the constrained node. These Perms signal a constrained node.
688 * For further comments, refer to handle_constraints().
690 static void constraints(ir_node *bl, void *data)
692 be_chordal_alloc_env_t *env = data;
695 Start silent in the start block.
696 The silence remains until the first barrier is seen.
697 Each other block is begun loud.
699 int silent = bl == get_irg_start_block(get_irn_irg(bl));
703 If the block is the start block search the barrier and
704 start handling constraints from there.
707 for(irn = sched_first(bl); !sched_is_end(irn);) {
708 irn = handle_constraints(env, irn, &silent);
713 * Annotate the register pressure to the nodes and compute
714 * the liveness intervals.
715 * @param block The block to do it for.
716 * @param env_ptr The environment.
718 static void pressure(ir_node *block, void *env_ptr)
720 /* Convenience macro for a def */
721 #define border_def(irn, step, real) \
722 border_add(env, head, irn, step, pressure--, 1, real)
724 /* Convenience macro for a use */
725 #define border_use(irn, step, real) \
726 border_add(env, head, irn, step, ++pressure, 0, real)
728 be_chordal_alloc_env_t *alloc_env = env_ptr;
729 be_chordal_env_t *env = alloc_env->chordal_env;
730 bitset_t *live = alloc_env->live;
732 be_lv_t *lv = env->birg->lv;
736 unsigned pressure = 0;
737 struct list_head *head;
738 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
739 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
741 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
742 bitset_clear_all(live);
744 /* Set up the border list in the block info */
745 head = obstack_alloc(env->obst, sizeof(*head));
746 INIT_LIST_HEAD(head);
747 assert(pmap_get(env->border_heads, block) == NULL);
748 pmap_insert(env->border_heads, block, head);
751 * Make final uses of all values live out of the block.
752 * They are necessary to build up real intervals.
754 foreach_pset(live_end, irn) {
755 if(has_reg_class(env, irn)) {
756 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
757 bitset_set(live, get_irn_idx(irn));
758 border_use(irn, step, 0);
764 * Determine the last uses of a value inside the block, since they are
765 * relevant for the interval borders.
767 sched_foreach_reverse(block, irn) {
768 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
769 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
772 * If the node defines some value, which can put into a
773 * register of the current class, make a border for it.
775 if(has_reg_class(env, irn)) {
776 int nr = get_irn_idx(irn);
778 bitset_clear(live, nr);
779 border_def(irn, step, 1);
783 * If the node is no phi node we can examine the uses.
786 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
787 ir_node *op = get_irn_n(irn, i);
789 if(has_reg_class(env, op)) {
790 int nr = get_irn_idx(op);
791 const char *msg = "-";
793 if(!bitset_is_set(live, nr)) {
794 border_use(op, step, 1);
795 bitset_set(live, nr);
799 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
807 * Add initial defs for all values live in.
809 foreach_pset(live_in, irn) {
810 if(has_reg_class(env, irn)) {
812 /* Mark the value live in. */
813 bitset_set(live, get_irn_idx(irn));
816 border_def(irn, step, 0);
824 static void assign(ir_node *block, void *env_ptr)
826 be_chordal_alloc_env_t *alloc_env = env_ptr;
827 be_chordal_env_t *env = alloc_env->chordal_env;
828 bitset_t *live = alloc_env->live;
829 bitset_t *colors = alloc_env->colors;
830 bitset_t *in_colors = alloc_env->in_colors;
831 const arch_env_t *arch_env = env->birg->main_env->arch_env;
832 struct list_head *head = get_block_border_head(env, block);
833 be_lv_t *lv = env->birg->lv;
834 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
839 bitset_clear_all(colors);
840 bitset_clear_all(live);
841 bitset_clear_all(in_colors);
843 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
844 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
845 list_for_each_entry(border_t, b, head, list) {
846 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
847 b->irn, get_irn_idx(b->irn)));
851 * Add initial defs for all values live in.
852 * Since their colors have already been assigned (The dominators were
853 * allocated before), we have to mark their colors as used also.
855 foreach_pset(live_in, irn) {
856 if(has_reg_class(env, irn)) {
857 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
860 assert(reg && "Node must have been assigned a register");
861 col = arch_register_get_index(reg);
863 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
865 /* Mark the color of the live in value as used. */
866 bitset_set(colors, col);
867 bitset_set(in_colors, col);
869 /* Mark the value live in. */
870 bitset_set(live, get_irn_idx(irn));
875 * Mind that the sequence of defs from back to front defines a perfect
876 * elimination order. So, coloring the definitions from first to last
879 list_for_each_entry_reverse(border_t, b, head, list) {
880 ir_node *irn = b->irn;
881 int nr = get_irn_idx(irn);
882 int ignore = arch_irn_is(arch_env, irn, ignore);
885 * Assign a color, if it is a local def. Global defs already have a
888 if(b->is_def && !be_is_live_in(lv, block, irn)) {
889 const arch_register_t *reg;
892 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
893 reg = arch_get_irn_register(arch_env, irn);
895 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
897 col = get_next_free_reg(alloc_env, colors);
898 reg = arch_register_for_index(env->cls, col);
899 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
900 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
903 bitset_set(colors, col);
904 arch_set_irn_register(arch_env, irn, reg);
906 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
908 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
909 bitset_set(live, nr);
912 /* Clear the color upon a use. */
913 else if(!b->is_def) {
914 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
917 assert(reg && "Register must have been assigned");
919 col = arch_register_get_index(reg);
921 if(!arch_register_type_is(reg, ignore)) {
922 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
926 bitset_clear(colors, col);
927 bitset_clear(live, nr);
934 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
936 be_chordal_alloc_env_t env;
938 be_irg_t *birg = chordal_env->birg;
939 const arch_register_class_t *cls = chordal_env->cls;
941 int colors_n = arch_register_class_n_regs(cls);
942 ir_graph *irg = chordal_env->irg;
943 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
945 /* some special classes contain only ignore regs, no work to be done */
946 if(allocatable_regs == 0)
949 be_assure_dom_front(birg);
950 be_assure_liveness(birg);
953 env.chordal_env = chordal_env;
954 env.colors_n = colors_n;
955 env.colors = bitset_alloca(colors_n);
956 env.tmp_colors = bitset_alloca(colors_n);
957 env.in_colors = bitset_alloca(colors_n);
958 env.pre_colored = pset_new_ptr_default();
960 /* Handle register targeting constraints */
961 dom_tree_walk_irg(irg, constraints, NULL, &env);
963 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
964 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
965 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
968 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
970 /* First, determine the pressure */
971 dom_tree_walk_irg(irg, pressure, NULL, &env);
973 /* Assign the colors */
974 dom_tree_walk_irg(irg, assign, NULL, &env);
976 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
978 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
979 plotter = new_plotter_ps(buf);
980 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
981 plotter_free(plotter);
984 bitset_free(env.live);
985 del_pset(env.pre_colored);
988 void be_init_chordal(void)
990 FIRM_DBG_REGISTER(dbg, "firm.be.chordal.constr");
993 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);