2 * Copyright (C) 1995-2008 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
35 #include "raw_bitset.h"
37 #include "bipartite.h"
38 #include "hungarian.h"
41 #include "irgraph_t.h"
42 #include "irprintf_t.h"
53 #include "besched_t.h"
60 #include "bestatevent.h"
62 #include "beintlive_t.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);
149 * If the def is encountered, the use was made and so was the
150 * the def node (see the code above). It was placed into the
151 * link field of the irn, so we can get it there.
153 b = get_irn_link(irn);
155 DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"));
158 b->pressure = pressure;
160 b->is_real = is_real;
163 list_add_tail(&b->list, head);
164 DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
171 * Check, if an irn is of the register class currently under processing.
172 * @param env The chordal environment.
173 * @param irn The node.
174 * @return 1, if the node is of that register class, 0 if not.
176 static inline int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
178 return arch_irn_consider_in_reg_alloc(env->cls, irn);
181 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
183 bitset_t *tmp = alloc_env->tmp_colors;
184 bitset_copy(tmp, colors);
185 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
186 return bitset_next_clear(tmp, 0);
189 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
194 bitset_copy(bs, o2->regs);
199 bitset_copy(bs, o1->regs);
203 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
205 if (bitset_contains(o1->regs, o2->regs)) {
206 bitset_copy(bs, o1->regs);
207 } else if (bitset_contains(o2->regs, o1->regs)) {
208 bitset_copy(bs, o2->regs);
216 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
220 ie.ignore_colors = env->ignore_colors;
223 return be_scan_insn(&ie, irn);
226 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
228 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
229 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
230 ir_node *bl = get_nodes_block(irn);
231 const be_irg_t *birg = env->birg;
232 be_lv_t *lv = birg->lv;
237 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
238 ir_node *op = get_irn_n(irn, i);
240 const arch_register_t *reg;
241 const arch_register_req_t *req;
243 req = arch_get_register_req(irn, i);
244 if (req->cls != env->cls)
247 reg = arch_get_irn_register(op);
249 if (reg == NULL || !arch_register_type_is(reg, ignore))
251 if (arch_register_type_is(reg, joker))
254 if (!arch_register_req_is(req, limited))
257 if (rbitset_is_set(req->limited, reg->index))
260 copy = be_new_Copy(env->cls, env->irg, bl, op);
261 be_stat_ev("constr_copy", 1);
263 sched_add_before(irn, copy);
264 set_irn_n(irn, i, copy);
265 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
268 insn = chordal_scan_insn(env, irn);
270 if (!insn->has_constraints)
273 /* insert copies for nodes that occur constrained more than once. */
274 for (i = insn->use_start; i < insn->n_ops; ++i) {
275 be_operand_t *op = &insn->ops[i];
277 if (!op->has_constraints)
280 for (j = i + 1; j < insn->n_ops; ++j) {
282 be_operand_t *a_op = &insn->ops[j];
284 if (a_op->carrier != op->carrier || !a_op->has_constraints)
287 /* if the constraint is the same, no copy is necessary
288 * TODO generalise unequal but overlapping constraints */
289 if (a_op->req == op->req)
292 if (be_is_Copy(get_irn_n(insn->irn, a_op->pos)))
295 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
296 be_stat_ev("constr_copy", 1);
298 sched_add_before(insn->irn, copy);
299 set_irn_n(insn->irn, a_op->pos, copy);
300 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
304 /* collect all registers occurring in out constraints. */
305 for (i = 0; i < insn->use_start; ++i) {
306 be_operand_t *op = &insn->ops[i];
307 if (op->has_constraints)
308 bitset_or(def_constr, op->regs);
312 * insert copies for all constrained arguments living through the node
313 * and being constrained to a register which also occurs in out constraints.
315 for (i = insn->use_start; i < insn->n_ops; ++i) {
317 be_operand_t *op = &insn->ops[i];
319 bitset_copy(tmp, op->regs);
320 bitset_and(tmp, def_constr);
324 * 1) the operand is constrained.
325 * 2) lives through the node.
326 * 3) is constrained to a register occurring in out constraints.
328 if (!op->has_constraints ||
329 !values_interfere(birg, insn->irn, op->carrier) ||
330 bitset_is_empty(tmp))
334 * only create the copy if the operand is no copy.
335 * this is necessary since the assure constraints phase inserts
336 * Copies and Keeps for operands which must be different from the
337 * results. Additional copies here would destroy this.
339 if (be_is_Copy(get_irn_n(insn->irn, op->pos)))
342 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
344 sched_add_before(insn->irn, copy);
345 set_irn_n(insn->irn, op->pos, copy);
346 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
347 be_liveness_update(lv, op->carrier);
351 obstack_free(env->obst, insn);
352 return insn->next_insn;
355 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
357 be_chordal_env_t *env = data;
359 for (irn = sched_first(bl); !sched_is_end(irn);) {
360 irn = prepare_constr_insn(env, irn);
364 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv)
366 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, cenv);
369 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
371 const be_chordal_env_t *env = alloc_env->chordal_env;
372 bitset_t *bs = bitset_alloca(env->cls->n_regs);
377 * For each out operand, try to find an in operand which can be assigned the
378 * same register as the out operand.
380 for (j = 0; j < insn->use_start; ++j) {
382 int smallest_n_regs = 2 * env->cls->n_regs + 1;
383 be_operand_t *out_op = &insn->ops[j];
385 /* Try to find an in operand which has ... */
386 for (i = insn->use_start; i < insn->n_ops; ++i) {
388 const be_operand_t *op = &insn->ops[i];
390 if (op->partner != NULL)
392 if (values_interfere(env->birg, op->irn, op->carrier))
395 bitset_clear_all(bs);
396 bitset_copy(bs, op->regs);
397 bitset_and(bs, out_op->regs);
398 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
400 if (!bitset_is_empty(bs) && n_total < smallest_n_regs) {
402 smallest_n_regs = n_total;
407 be_operand_t *partner = &insn->ops[smallest];
408 for (i = insn->use_start; i < insn->n_ops; ++i) {
409 if (insn->ops[i].carrier == partner->carrier)
410 insn->ops[i].partner = out_op;
413 out_op->partner = partner;
414 partner->partner = out_op;
420 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
421 be_insn_t **the_insn)
423 be_chordal_env_t *env = alloc_env->chordal_env;
424 be_insn_t *insn = *the_insn;
425 ir_node *perm = NULL;
426 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
427 const ir_edge_t *edge;
430 assert(insn->has_constraints && "only do this for constrained nodes");
433 * Collect all registers that occur in output constraints.
434 * This is necessary, since if the insn has one of these as an input constraint
435 * and the corresponding operand interferes with the insn, the operand must
438 for (i = 0; i < insn->use_start; ++i) {
439 be_operand_t *op = &insn->ops[i];
440 if (op->has_constraints)
441 bitset_or(out_constr, op->regs);
445 * Make the Perm, recompute liveness and re-scan the insn since the
446 * in operands are now the Projs of the Perm.
448 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
450 /* Registers are propagated by insert_Perm_after(). Clean them here! */
454 be_stat_ev("constr_perm", get_irn_arity(perm));
455 foreach_out_edge(perm, edge) {
456 ir_node *proj = get_edge_src_irn(edge);
457 arch_set_irn_register(proj, NULL);
461 * We also have to re-build the insn since the input operands are now the Projs of
462 * the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
463 * the live sets may change.
465 obstack_free(env->obst, insn);
466 *the_insn = insn = chordal_scan_insn(env, insn->irn);
469 * Copy the input constraints of the insn to the Perm as output
470 * constraints. Succeeding phases (coalescing) will need that.
472 for (i = insn->use_start; i < insn->n_ops; ++i) {
473 be_operand_t *op = &insn->ops[i];
474 ir_node *proj = op->carrier;
476 * Note that the predecessor must not be a Proj of the Perm,
477 * since ignore-nodes are not Perm'ed.
479 if (op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
480 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
487 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
488 ir_node *irn, int *silent)
492 ir_node **alloc_nodes;
493 //hungarian_problem_t *bp;
498 const ir_edge_t *edge;
499 ir_node *perm = NULL;
500 //int match_res, cost;
501 be_chordal_env_t *env = alloc_env->chordal_env;
502 void *base = obstack_base(env->obst);
503 be_insn_t *insn = chordal_scan_insn(env, irn);
504 ir_node *res = insn->next_insn;
505 int be_silent = *silent;
506 be_irg_t *birg = env->birg;
509 if (insn->pre_colored) {
511 for (i = 0; i < insn->use_start; ++i)
512 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
516 * If the current node is a barrier toggle the silent flag.
517 * If we are in the start block, we are ought to be silent at the beginning,
518 * so the toggling activates the constraint handling but skips the barrier.
519 * If we are in the end block we handle the in requirements of the barrier
520 * and set the rest to silent.
522 if (be_is_Barrier(irn))
529 * Perms inserted before the constraint handling phase are considered to be
530 * correctly precolored. These Perms arise during the ABI handling phase.
532 if (!insn->has_constraints)
535 n_regs = env->cls->n_regs;
536 bs = bitset_alloca(n_regs);
537 alloc_nodes = ALLOCAN(ir_node*, n_regs);
538 //bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
539 bp = bipartite_new(n_regs, n_regs);
540 assignment = ALLOCAN(int, n_regs);
541 partners = pmap_create();
544 * prepare the constraint handling of this node.
545 * Perms are constructed and Copies are created for constrained values
546 * interfering with the instruction.
548 perm = pre_process_constraints(alloc_env, &insn);
550 /* find suitable in operands to the out operands of the node. */
551 pair_up_operands(alloc_env, insn);
554 * look at the in/out operands and add each operand (and its possible partner)
555 * to a bipartite graph (left: nodes with partners, right: admissible colors).
557 for (i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
558 be_operand_t *op = &insn->ops[i];
561 * If the operand has no partner or the partner has not been marked
562 * for allocation, determine the admissible registers and mark it
563 * for allocation by associating the node and its partner with the
564 * set of admissible registers via a bipartite graph.
566 if (!op->partner || !pmap_contains(partners, op->partner->carrier)) {
567 ir_node *partner = op->partner ? op->partner->carrier : NULL;
570 pmap_insert(partners, op->carrier, partner);
572 pmap_insert(partners, partner, op->carrier);
574 /* don't insert a node twice */
575 for (i = 0; i < n_alloc; ++i) {
576 if (alloc_nodes[i] == op->carrier) {
583 alloc_nodes[n_alloc] = op->carrier;
585 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
588 bitset_clear_all(bs);
589 get_decisive_partner_regs(bs, op, op->partner);
591 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
594 bitset_foreach(bs, col) {
595 //hungarian_add(bp, n_alloc, col, 1);
596 bipartite_add(bp, n_alloc, col);
604 * Put all nodes which live through the constrained instruction also to the
605 * allocation bipartite graph. They are considered unconstrained.
608 foreach_out_edge(perm, edge) {
610 ir_node *proj = get_edge_src_irn(edge);
612 assert(is_Proj(proj));
614 if (!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
617 /* don't insert a node twice */
618 for (i = 0; i < n_alloc; ++i) {
619 if (alloc_nodes[i] == proj) {
627 assert(n_alloc < n_regs);
629 alloc_nodes[n_alloc] = proj;
630 pmap_insert(partners, proj, NULL);
632 bitset_clear_all(bs);
633 arch_put_non_ignore_regs(env->cls, bs);
634 bitset_andnot(bs, env->ignore_colors);
635 bitset_foreach(bs, col) {
636 //hungarian_add(bp, n_alloc, col, 1);
637 bipartite_add(bp, n_alloc, col);
644 /* Compute a valid register allocation. */
646 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
647 match_res = hungarian_solve(bp, assignment, &cost, 1);
648 assert(match_res == 0 && "matching failed");
650 bipartite_matching(bp, assignment);
653 /* Assign colors obtained from the matching. */
654 for (i = 0; i < n_alloc; ++i) {
655 const arch_register_t *reg;
658 assert(assignment[i] >= 0 && "there must have been a register assigned");
659 reg = arch_register_for_index(env->cls, assignment[i]);
660 assert(! (reg->type & arch_register_type_ignore));
662 irn = alloc_nodes[i];
664 arch_set_irn_register(irn, reg);
665 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
666 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
669 irn = pmap_get(partners, alloc_nodes[i]);
671 arch_set_irn_register(irn, reg);
672 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
673 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
677 /* Allocate the non-constrained Projs of the Perm. */
679 bitset_clear_all(bs);
681 /* Put the colors of all Projs in a bitset. */
682 foreach_out_edge(perm, edge) {
683 ir_node *proj = get_edge_src_irn(edge);
684 const arch_register_t *reg = arch_get_irn_register(proj);
687 bitset_set(bs, reg->index);
690 /* Assign the not yet assigned Projs of the Perm a suitable color. */
691 foreach_out_edge(perm, edge) {
692 ir_node *proj = get_edge_src_irn(edge);
693 const arch_register_t *reg = arch_get_irn_register(proj);
695 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
698 col = get_next_free_reg(alloc_env, bs);
699 reg = arch_register_for_index(env->cls, col);
700 bitset_set(bs, reg->index);
701 arch_set_irn_register(proj, reg);
702 pset_insert_ptr(alloc_env->pre_colored, proj);
703 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
709 //hungarian_free(bp);
710 pmap_destroy(partners);
713 obstack_free(env->obst, base);
718 * Handle constraint nodes in each basic block.
719 * handle_constraints() inserts Perm nodes which perm
720 * over all values live at the constrained node right in front
721 * of the constrained node. These Perms signal a constrained node.
722 * For further comments, refer to handle_constraints().
724 static void constraints(ir_node *bl, void *data)
727 * Start silent in the start block.
728 * The silence remains until the first barrier is seen.
729 * Each other block is begun loud.
731 int silent = bl == get_irg_start_block(get_irn_irg(bl));
732 be_chordal_alloc_env_t *env = data;
736 * If the block is the start block search the barrier and
737 * start handling constraints from there.
739 for (irn = sched_first(bl); !sched_is_end(irn);) {
740 irn = handle_constraints(env, irn, &silent);
745 * Annotate the register pressure to the nodes and compute
746 * the liveness intervals.
747 * @param block The block to do it for.
748 * @param env_ptr The environment.
750 static void pressure(ir_node *block, void *env_ptr)
752 /* Convenience macro for a def */
753 #define border_def(irn, step, real) \
754 border_add(env, head, irn, step, pressure--, 1, real)
756 /* Convenience macro for a use */
757 #define border_use(irn, step, real) \
758 border_add(env, head, irn, step, ++pressure, 0, real)
760 be_chordal_alloc_env_t *alloc_env = env_ptr;
761 be_chordal_env_t *env = alloc_env->chordal_env;
762 bitset_t *live = alloc_env->live;
764 be_lv_t *lv = env->birg->lv;
769 unsigned pressure = 0;
770 struct list_head *head;
772 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
773 bitset_clear_all(live);
775 /* Set up the border list in the block info */
776 head = obstack_alloc(env->obst, sizeof(*head));
777 INIT_LIST_HEAD(head);
778 assert(pmap_get(env->border_heads, block) == NULL);
779 pmap_insert(env->border_heads, block, head);
782 * Make final uses of all values live out of the block.
783 * They are necessary to build up real intervals.
785 be_lv_foreach(lv, block, be_lv_state_end, i) {
786 ir_node *irn = be_lv_get_irn(lv, block, i);
787 if (has_reg_class(env, irn)) {
788 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
789 bitset_set(live, get_irn_idx(irn));
790 border_use(irn, step, 0);
796 * Determine the last uses of a value inside the block, since they are
797 * relevant for the interval borders.
799 sched_foreach_reverse(block, irn) {
800 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
801 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
803 if (get_irn_mode(irn) == mode_T) {
804 const ir_edge_t *edge;
806 foreach_out_edge(irn, edge) {
807 ir_node *proj = get_edge_src_irn(edge);
810 * If the node defines some value, which can put into a
811 * register of the current class, make a border for it.
813 if (has_reg_class(env, proj)) {
814 int nr = get_irn_idx(proj);
816 bitset_clear(live, nr);
817 border_def(proj, step, 1);
823 * If the node defines some value, which can put into a
824 * register of the current class, make a border for it.
826 if (has_reg_class(env, irn)) {
827 int nr = get_irn_idx(irn);
829 bitset_clear(live, nr);
830 border_def(irn, step, 1);
834 * If the node is no phi node we can examine the uses.
837 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
838 ir_node *op = get_irn_n(irn, i);
840 if (has_reg_class(env, op)) {
841 int nr = get_irn_idx(op);
842 const char *msg = "-";
844 if (!bitset_is_set(live, nr)) {
845 border_use(op, step, 1);
846 bitset_set(live, nr);
850 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
857 bitset_foreach(live, elm) {
858 ir_node *irn = get_idx_irn(env->irg, elm);
859 if (be_is_live_in(lv, block, irn))
860 border_def(irn, step, 0);
864 static void assign(ir_node *block, void *env_ptr)
866 be_chordal_alloc_env_t *alloc_env = env_ptr;
867 be_chordal_env_t *env = alloc_env->chordal_env;
868 bitset_t *live = alloc_env->live;
869 bitset_t *colors = alloc_env->colors;
870 bitset_t *in_colors = alloc_env->in_colors;
871 struct list_head *head = get_block_border_head(env, block);
872 be_lv_t *lv = env->birg->lv;
878 bitset_clear_all(colors);
879 bitset_clear_all(live);
880 bitset_clear_all(in_colors);
882 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
883 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
884 list_for_each_entry(border_t, b, head, list) {
885 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
886 b->irn, get_irn_idx(b->irn)));
890 * Add initial defs for all values live in.
891 * Since their colors have already been assigned (The dominators were
892 * allocated before), we have to mark their colors as used also.
894 be_lv_foreach(lv, block, be_lv_state_in, idx) {
895 irn = be_lv_get_irn(lv, block, idx);
896 if (has_reg_class(env, irn)) {
897 const arch_register_t *reg = arch_get_irn_register(irn);
900 assert(reg && "Node must have been assigned a register");
901 col = arch_register_get_index(reg);
903 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
905 /* Mark the color of the live in value as used. */
906 bitset_set(colors, col);
907 bitset_set(in_colors, col);
909 /* Mark the value live in. */
910 bitset_set(live, get_irn_idx(irn));
915 * Mind that the sequence of defs from back to front defines a perfect
916 * elimination order. So, coloring the definitions from first to last
919 list_for_each_entry_reverse(border_t, b, head, list) {
920 ir_node *irn = b->irn;
921 int nr = get_irn_idx(irn);
922 int ignore = arch_irn_is_ignore(irn);
925 * Assign a color, if it is a local def. Global defs already have a
928 if (b->is_def && !be_is_live_in(lv, block, irn)) {
929 const arch_register_t *reg;
932 if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
933 reg = arch_get_irn_register(irn);
935 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
937 col = get_next_free_reg(alloc_env, colors);
938 reg = arch_register_for_index(env->cls, col);
939 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
940 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
943 bitset_set(colors, col);
944 arch_set_irn_register(irn, reg);
946 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
948 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
949 bitset_set(live, nr);
950 } else if (!b->is_def) {
951 /* Clear the color upon a use. */
952 const arch_register_t *reg = arch_get_irn_register(irn);
955 assert(reg && "Register must have been assigned");
957 col = arch_register_get_index(reg);
959 if (!arch_register_type_is(reg, ignore)) {
960 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
964 bitset_clear(colors, col);
965 bitset_clear(live, nr);
970 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
972 be_chordal_alloc_env_t env;
975 be_irg_t *birg = chordal_env->birg;
976 const arch_register_class_t *cls = chordal_env->cls;
978 int colors_n = arch_register_class_n_regs(cls);
979 ir_graph *irg = chordal_env->irg;
981 lv = be_assure_liveness(birg);
982 be_liveness_assure_sets(lv);
983 be_liveness_assure_chk(lv);
987 env.chordal_env = chordal_env;
988 env.colors_n = colors_n;
989 env.colors = bitset_alloca(colors_n);
990 env.tmp_colors = bitset_alloca(colors_n);
991 env.in_colors = bitset_alloca(colors_n);
992 env.pre_colored = pset_new_ptr_default();
994 BE_TIMER_PUSH(t_constr);
996 /* Handle register targeting constraints */
997 dom_tree_walk_irg(irg, constraints, NULL, &env);
999 if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1000 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1001 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1004 BE_TIMER_POP(t_constr);
1006 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1008 /* First, determine the pressure */
1009 dom_tree_walk_irg(irg, pressure, NULL, &env);
1011 /* Assign the colors */
1012 dom_tree_walk_irg(irg, assign, NULL, &env);
1014 if (chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1016 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1017 plotter = new_plotter_ps(buf);
1018 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1019 plotter_free(plotter);
1022 bitset_free(env.live);
1023 del_pset(env.pre_colored);
1026 void be_init_chordal(void)
1028 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1031 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);