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);
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 DEBUG_ONLY(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_consider_in_reg_alloc(env->cls, irn);
183 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
185 bitset_t *tmp = alloc_env->tmp_colors;
186 bitset_copy(tmp, colors);
187 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
188 return bitset_next_clear(tmp, 0);
191 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
196 bitset_copy(bs, o2->regs);
201 bitset_copy(bs, o1->regs);
205 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
207 if(bitset_contains(o1->regs, o2->regs))
208 bitset_copy(bs, o1->regs);
209 else if(bitset_contains(o2->regs, o1->regs))
210 bitset_copy(bs, o2->regs);
217 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
221 ie.ignore_colors = env->ignore_colors;
224 return be_scan_insn(&ie, irn);
227 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
229 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
230 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
231 ir_node *bl = get_nodes_block(irn);
232 const be_irg_t *birg = env->birg;
233 be_lv_t *lv = birg->lv;
238 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
239 ir_node *op = get_irn_n(irn, i);
241 const arch_register_t *reg;
242 const arch_register_req_t *req;
244 if (arch_get_irn_reg_class(irn, i) != 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 req = arch_get_register_req(irn, i);
255 if (!arch_register_req_is(req, limited))
258 if (rbitset_is_set(req->limited, reg->index))
261 copy = be_new_Copy(env->cls, env->irg, bl, op);
262 be_stat_ev("constr_copy", 1);
264 sched_add_before(irn, copy);
265 set_irn_n(irn, i, copy);
266 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
269 insn = chordal_scan_insn(env, irn);
271 if(!insn->has_constraints)
274 /* insert copies for nodes that occur constrained more than once. */
275 for(i = insn->use_start; i < insn->n_ops; ++i) {
276 be_operand_t *op = &insn->ops[i];
278 if(!op->has_constraints)
281 for(j = i + 1; j < insn->n_ops; ++j) {
283 be_operand_t *a_op = &insn->ops[j];
285 if(a_op->carrier != op->carrier || !a_op->has_constraints)
288 /* if the constraint is the same, no copy is necessary
289 * TODO generalise unequal but overlapping constraints */
290 if (a_op->req == op->req)
293 if (be_is_Copy(get_irn_n(insn->irn, a_op->pos)))
296 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
297 be_stat_ev("constr_copy", 1);
299 sched_add_before(insn->irn, copy);
300 set_irn_n(insn->irn, a_op->pos, copy);
301 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
305 /* collect all registers occurring in out constraints. */
306 for(i = 0; i < insn->use_start; ++i) {
307 be_operand_t *op = &insn->ops[i];
308 if(op->has_constraints)
309 bitset_or(def_constr, op->regs);
313 insert copies for all constrained arguments living through the node
314 and being constrained to a register which also occurs in out constraints.
316 for(i = insn->use_start; i < insn->n_ops; ++i) {
318 be_operand_t *op = &insn->ops[i];
320 bitset_copy(tmp, op->regs);
321 bitset_and(tmp, def_constr);
325 1) the operand is constrained.
326 2) lives through the node.
327 3) is constrained to a register occurring in out constraints.
329 if(!op->has_constraints ||
330 !values_interfere(birg, insn->irn, op->carrier) ||
331 bitset_popcnt(tmp) == 0)
335 only create the copy if the operand is no copy.
336 this is necessary since the assure constraints phase inserts
337 Copies and Keeps for operands which must be different from the
338 results. Additional copies here would destroy this.
340 if (be_is_Copy(get_irn_n(insn->irn, op->pos)))
343 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
345 sched_add_before(insn->irn, copy);
346 set_irn_n(insn->irn, op->pos, copy);
347 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
348 be_liveness_update(lv, op->carrier);
352 obstack_free(env->obst, insn);
353 return insn->next_insn;
356 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
358 be_chordal_env_t *env = data;
360 for(irn = sched_first(bl); !sched_is_end(irn);) {
361 irn = prepare_constr_insn(env, irn);
365 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
366 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) 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;
373 int n_uses = be_insn_n_uses(insn);
374 int n_defs = be_insn_n_defs(insn);
375 bitset_t *bs = bitset_alloca(env->cls->n_regs);
376 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
381 For each out operand, try to find an in operand which can be assigned the
382 same register as the out operand.
384 for (j = 0; j < insn->use_start; ++j) {
386 int smallest_n_regs = 2 * env->cls->n_regs + 1;
387 be_operand_t *out_op = &insn->ops[j];
389 /* Try to find an in operand which has ... */
390 for(i = insn->use_start; i < insn->n_ops; ++i) {
392 const be_operand_t *op = &insn->ops[i];
394 if (op->partner != NULL)
396 if (values_interfere(env->birg, op->irn, op->carrier))
399 bitset_clear_all(bs);
400 bitset_copy(bs, op->regs);
401 bitset_and(bs, out_op->regs);
402 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
404 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
406 smallest_n_regs = n_total;
411 be_operand_t *partner = &insn->ops[smallest];
412 for(i = insn->use_start; i < insn->n_ops; ++i) {
413 if(insn->ops[i].carrier == partner->carrier)
414 insn->ops[i].partner = out_op;
417 out_op->partner = partner;
418 partner->partner = out_op;
424 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
425 be_insn_t **the_insn)
427 be_chordal_env_t *env = alloc_env->chordal_env;
428 be_insn_t *insn = *the_insn;
429 ir_node *perm = NULL;
430 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
431 const ir_edge_t *edge;
434 assert(insn->has_constraints && "only do this for constrained nodes");
437 Collect all registers that occur in output constraints.
438 This is necessary, since if the insn has one of these as an input constraint
439 and the corresponding operand interferes with the insn, the operand must
442 for(i = 0; i < insn->use_start; ++i) {
443 be_operand_t *op = &insn->ops[i];
444 if(op->has_constraints)
445 bitset_or(out_constr, op->regs);
449 Make the Perm, recompute liveness and re-scan the insn since the
450 in operands are now the Projs of the Perm.
452 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
454 /* Registers are propagated by insert_Perm_after(). Clean them here! */
458 be_stat_ev("constr_perm", get_irn_arity(perm));
459 foreach_out_edge(perm, edge) {
460 ir_node *proj = get_edge_src_irn(edge);
461 arch_set_irn_register(proj, NULL);
465 We also have to re-build the insn since the input operands are now the Projs of
466 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
467 the live sets may change.
469 obstack_free(env->obst, insn);
470 *the_insn = insn = chordal_scan_insn(env, insn->irn);
473 Copy the input constraints of the insn to the Perm as output
474 constraints. Succeeding phases (coalescing) will need that.
476 for(i = insn->use_start; i < insn->n_ops; ++i) {
477 be_operand_t *op = &insn->ops[i];
478 ir_node *proj = op->carrier;
480 Note that the predecessor must not be a Proj of the Perm,
481 since ignore-nodes are not Perm'ed.
483 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
484 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
491 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
492 ir_node *irn, int *silent)
496 ir_node **alloc_nodes;
497 //hungarian_problem_t *bp;
502 const ir_edge_t *edge;
503 ir_node *perm = NULL;
504 //int match_res, cost;
505 be_chordal_env_t *env = alloc_env->chordal_env;
506 void *base = obstack_base(env->obst);
507 be_insn_t *insn = chordal_scan_insn(env, irn);
508 ir_node *res = insn->next_insn;
509 int be_silent = *silent;
510 be_irg_t *birg = env->birg;
513 if(insn->pre_colored) {
515 for(i = 0; i < insn->use_start; ++i)
516 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
520 If the current node is a barrier toggle the silent flag.
521 If we are in the start block, we are ought to be silent at the beginning,
522 so the toggling activates the constraint handling but skips the barrier.
523 If we are in the end block we handle the in requirements of the barrier
524 and set the rest to silent.
526 if(be_is_Barrier(irn))
533 Perms inserted before the constraint handling phase are considered to be
534 correctly precolored. These Perms arise during the ABI handling phase.
536 if(!insn->has_constraints)
539 n_regs = env->cls->n_regs;
540 bs = bitset_alloca(n_regs);
541 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
542 //bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
543 bp = bipartite_new(n_regs, n_regs);
544 assignment = alloca(n_regs * sizeof(assignment[0]));
545 partners = pmap_create();
548 prepare the constraint handling of this node.
549 Perms are constructed and Copies are created for constrained values
550 interfering with the instruction.
552 perm = pre_process_constraints(alloc_env, &insn);
554 /* find suitable in operands to the out operands of the node. */
555 pair_up_operands(alloc_env, insn);
558 look at the in/out operands and add each operand (and its possible partner)
559 to a bipartite graph (left: nodes with partners, right: admissible colors).
561 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
562 be_operand_t *op = &insn->ops[i];
565 If the operand has no partner or the partner has not been marked
566 for allocation, determine the admissible registers and mark it
567 for allocation by associating the node and its partner with the
568 set of admissible registers via a bipartite graph.
570 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
571 ir_node *partner = op->partner ? op->partner->carrier : NULL;
574 pmap_insert(partners, op->carrier, partner);
576 pmap_insert(partners, partner, op->carrier);
578 /* don't insert a node twice */
579 for(i = 0; i < n_alloc; ++i) {
580 if(alloc_nodes[i] == op->carrier) {
587 alloc_nodes[n_alloc] = op->carrier;
589 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
592 bitset_clear_all(bs);
593 get_decisive_partner_regs(bs, op, op->partner);
595 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
598 bitset_foreach(bs, col) {
599 //hungarian_add(bp, n_alloc, col, 1);
600 bipartite_add(bp, n_alloc, col);
608 Put all nodes which live through the constrained instruction also to the
609 allocation bipartite graph. They are considered unconstrained.
612 foreach_out_edge(perm, edge) {
614 ir_node *proj = get_edge_src_irn(edge);
616 assert(is_Proj(proj));
618 if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
621 /* don't insert a node twice */
622 for(i = 0; i < n_alloc; ++i) {
623 if(alloc_nodes[i] == proj) {
631 assert(n_alloc < n_regs);
633 alloc_nodes[n_alloc] = proj;
634 pmap_insert(partners, proj, NULL);
636 bitset_clear_all(bs);
637 arch_put_non_ignore_regs(env->cls, bs);
638 bitset_andnot(bs, env->ignore_colors);
639 bitset_foreach(bs, col) {
640 //hungarian_add(bp, n_alloc, col, 1);
641 bipartite_add(bp, n_alloc, col);
648 /* Compute a valid register allocation. */
650 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
651 match_res = hungarian_solve(bp, assignment, &cost, 1);
652 assert(match_res == 0 && "matching failed");
654 bipartite_matching(bp, assignment);
657 /* Assign colors obtained from the matching. */
658 for(i = 0; i < n_alloc; ++i) {
659 const arch_register_t *reg;
662 assert(assignment[i] >= 0 && "there must have been a register assigned");
663 reg = arch_register_for_index(env->cls, assignment[i]);
664 assert(! (reg->type & arch_register_type_ignore));
666 irn = alloc_nodes[i];
668 arch_set_irn_register(irn, reg);
669 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
670 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
673 irn = pmap_get(partners, alloc_nodes[i]);
675 arch_set_irn_register(irn, reg);
676 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
677 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
681 /* Allocate the non-constrained Projs of the Perm. */
683 bitset_clear_all(bs);
685 /* Put the colors of all Projs in a bitset. */
686 foreach_out_edge(perm, edge) {
687 ir_node *proj = get_edge_src_irn(edge);
688 const arch_register_t *reg = arch_get_irn_register(proj);
691 bitset_set(bs, reg->index);
694 /* Assign the not yet assigned Projs of the Perm a suitable color. */
695 foreach_out_edge(perm, edge) {
696 ir_node *proj = get_edge_src_irn(edge);
697 const arch_register_t *reg = arch_get_irn_register(proj);
699 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
702 col = get_next_free_reg(alloc_env, bs);
703 reg = arch_register_for_index(env->cls, col);
704 bitset_set(bs, reg->index);
705 arch_set_irn_register(proj, reg);
706 pset_insert_ptr(alloc_env->pre_colored, proj);
707 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
713 //hungarian_free(bp);
714 pmap_destroy(partners);
717 obstack_free(env->obst, base);
722 * Handle constraint nodes in each basic block.
723 * handle_constraints() inserts Perm nodes which perm
724 * over all values live at the constrained node right in front
725 * of the constrained node. These Perms signal a constrained node.
726 * For further comments, refer to handle_constraints().
728 static void constraints(ir_node *bl, void *data)
730 be_chordal_alloc_env_t *env = data;
733 Start silent in the start block.
734 The silence remains until the first barrier is seen.
735 Each other block is begun loud.
737 int silent = bl == get_irg_start_block(get_irn_irg(bl));
741 If the block is the start block search the barrier and
742 start handling constraints from there.
745 for(irn = sched_first(bl); !sched_is_end(irn);) {
746 irn = handle_constraints(env, irn, &silent);
751 * Annotate the register pressure to the nodes and compute
752 * the liveness intervals.
753 * @param block The block to do it for.
754 * @param env_ptr The environment.
756 static void pressure(ir_node *block, void *env_ptr)
758 /* Convenience macro for a def */
759 #define border_def(irn, step, real) \
760 border_add(env, head, irn, step, pressure--, 1, real)
762 /* Convenience macro for a use */
763 #define border_use(irn, step, real) \
764 border_add(env, head, irn, step, ++pressure, 0, real)
766 be_chordal_alloc_env_t *alloc_env = env_ptr;
767 be_chordal_env_t *env = alloc_env->chordal_env;
768 bitset_t *live = alloc_env->live;
770 be_lv_t *lv = env->birg->lv;
775 unsigned pressure = 0;
776 struct list_head *head;
778 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
779 bitset_clear_all(live);
781 /* Set up the border list in the block info */
782 head = obstack_alloc(env->obst, sizeof(*head));
783 INIT_LIST_HEAD(head);
784 assert(pmap_get(env->border_heads, block) == NULL);
785 pmap_insert(env->border_heads, block, head);
788 * Make final uses of all values live out of the block.
789 * They are necessary to build up real intervals.
791 be_lv_foreach(lv, block, be_lv_state_end, i) {
792 ir_node *irn = be_lv_get_irn(lv, block, i);
793 if(has_reg_class(env, irn)) {
794 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
795 bitset_set(live, get_irn_idx(irn));
796 border_use(irn, step, 0);
802 * Determine the last uses of a value inside the block, since they are
803 * relevant for the interval borders.
805 sched_foreach_reverse(block, irn) {
806 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
807 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
809 if (get_irn_mode(irn) == mode_T) {
810 const ir_edge_t *edge;
812 foreach_out_edge(irn, edge) {
813 ir_node *proj = get_edge_src_irn(edge);
816 * If the node defines some value, which can put into a
817 * register of the current class, make a border for it.
819 if(has_reg_class(env, proj)) {
820 int nr = get_irn_idx(proj);
822 bitset_clear(live, nr);
823 border_def(proj, step, 1);
829 * If the node defines some value, which can put into a
830 * register of the current class, make a border for it.
832 if(has_reg_class(env, irn)) {
833 int nr = get_irn_idx(irn);
835 bitset_clear(live, nr);
836 border_def(irn, step, 1);
840 * If the node is no phi node we can examine the uses.
843 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
844 ir_node *op = get_irn_n(irn, i);
846 if(has_reg_class(env, op)) {
847 int nr = get_irn_idx(op);
848 const char *msg = "-";
850 if(!bitset_is_set(live, nr)) {
851 border_use(op, step, 1);
852 bitset_set(live, nr);
856 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
863 bitset_foreach(live, elm) {
864 ir_node *irn = get_idx_irn(env->irg, elm);
865 if (be_is_live_in(lv, block, irn))
866 border_def(irn, step, 0);
870 static void assign(ir_node *block, void *env_ptr)
872 be_chordal_alloc_env_t *alloc_env = env_ptr;
873 be_chordal_env_t *env = alloc_env->chordal_env;
874 bitset_t *live = alloc_env->live;
875 bitset_t *colors = alloc_env->colors;
876 bitset_t *in_colors = alloc_env->in_colors;
877 struct list_head *head = get_block_border_head(env, block);
878 be_lv_t *lv = env->birg->lv;
884 bitset_clear_all(colors);
885 bitset_clear_all(live);
886 bitset_clear_all(in_colors);
888 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
889 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
890 list_for_each_entry(border_t, b, head, list) {
891 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
892 b->irn, get_irn_idx(b->irn)));
896 * Add initial defs for all values live in.
897 * Since their colors have already been assigned (The dominators were
898 * allocated before), we have to mark their colors as used also.
900 be_lv_foreach(lv, block, be_lv_state_in, idx) {
901 irn = be_lv_get_irn(lv, block, idx);
902 if(has_reg_class(env, irn)) {
903 const arch_register_t *reg = arch_get_irn_register(irn);
906 assert(reg && "Node must have been assigned a register");
907 col = arch_register_get_index(reg);
909 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
911 /* Mark the color of the live in value as used. */
912 bitset_set(colors, col);
913 bitset_set(in_colors, col);
915 /* Mark the value live in. */
916 bitset_set(live, get_irn_idx(irn));
921 * Mind that the sequence of defs from back to front defines a perfect
922 * elimination order. So, coloring the definitions from first to last
925 list_for_each_entry_reverse(border_t, b, head, list) {
926 ir_node *irn = b->irn;
927 int nr = get_irn_idx(irn);
928 int ignore = arch_irn_is(irn, ignore);
931 * Assign a color, if it is a local def. Global defs already have a
934 if(b->is_def && !be_is_live_in(lv, block, irn)) {
935 const arch_register_t *reg;
938 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
939 reg = arch_get_irn_register(irn);
941 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
943 col = get_next_free_reg(alloc_env, colors);
944 reg = arch_register_for_index(env->cls, col);
945 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
946 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
949 bitset_set(colors, col);
950 arch_set_irn_register(irn, reg);
952 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
954 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
955 bitset_set(live, nr);
958 /* Clear the color upon a use. */
959 else if(!b->is_def) {
960 const arch_register_t *reg = arch_get_irn_register(irn);
963 assert(reg && "Register must have been assigned");
965 col = arch_register_get_index(reg);
967 if(!arch_register_type_is(reg, ignore)) {
968 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
972 bitset_clear(colors, col);
973 bitset_clear(live, nr);
978 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
980 be_chordal_alloc_env_t env;
983 be_irg_t *birg = chordal_env->birg;
984 const arch_register_class_t *cls = chordal_env->cls;
986 int colors_n = arch_register_class_n_regs(cls);
987 ir_graph *irg = chordal_env->irg;
989 lv = be_assure_liveness(birg);
990 be_liveness_assure_sets(lv);
991 be_liveness_assure_chk(lv);
995 env.chordal_env = chordal_env;
996 env.colors_n = colors_n;
997 env.colors = bitset_alloca(colors_n);
998 env.tmp_colors = bitset_alloca(colors_n);
999 env.in_colors = bitset_alloca(colors_n);
1000 env.pre_colored = pset_new_ptr_default();
1002 BE_TIMER_PUSH(t_constr);
1004 /* Handle register targeting constraints */
1005 dom_tree_walk_irg(irg, constraints, NULL, &env);
1007 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1008 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1009 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1012 BE_TIMER_POP(t_constr);
1014 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1016 /* First, determine the pressure */
1017 dom_tree_walk_irg(irg, pressure, NULL, &env);
1019 /* Assign the colors */
1020 dom_tree_walk_irg(irg, assign, NULL, &env);
1022 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1024 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1025 plotter = new_plotter_ps(buf);
1026 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1027 plotter_free(plotter);
1030 bitset_free(env.live);
1031 del_pset(env.pre_colored);
1034 void be_init_chordal(void)
1036 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1039 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);