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 req = arch_get_register_req(irn, i);
245 if (req->cls != env->cls)
248 reg = arch_get_irn_register(op);
250 if (reg == NULL || !arch_register_type_is(reg, ignore))
252 if(arch_register_type_is(reg, joker))
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;
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_popcnt(bs) > 0 && 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 = alloca(n_regs * sizeof(alloc_nodes[0]));
538 //bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
539 bp = bipartite_new(n_regs, n_regs);
540 assignment = alloca(n_regs * sizeof(assignment[0]));
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)
726 be_chordal_alloc_env_t *env = data;
729 Start silent in the start block.
730 The silence remains until the first barrier is seen.
731 Each other block is begun loud.
733 int silent = bl == get_irg_start_block(get_irn_irg(bl));
737 If the block is the start block search the barrier and
738 start handling constraints from there.
741 for(irn = sched_first(bl); !sched_is_end(irn);) {
742 irn = handle_constraints(env, irn, &silent);
747 * Annotate the register pressure to the nodes and compute
748 * the liveness intervals.
749 * @param block The block to do it for.
750 * @param env_ptr The environment.
752 static void pressure(ir_node *block, void *env_ptr)
754 /* Convenience macro for a def */
755 #define border_def(irn, step, real) \
756 border_add(env, head, irn, step, pressure--, 1, real)
758 /* Convenience macro for a use */
759 #define border_use(irn, step, real) \
760 border_add(env, head, irn, step, ++pressure, 0, real)
762 be_chordal_alloc_env_t *alloc_env = env_ptr;
763 be_chordal_env_t *env = alloc_env->chordal_env;
764 bitset_t *live = alloc_env->live;
766 be_lv_t *lv = env->birg->lv;
771 unsigned pressure = 0;
772 struct list_head *head;
774 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
775 bitset_clear_all(live);
777 /* Set up the border list in the block info */
778 head = obstack_alloc(env->obst, sizeof(*head));
779 INIT_LIST_HEAD(head);
780 assert(pmap_get(env->border_heads, block) == NULL);
781 pmap_insert(env->border_heads, block, head);
784 * Make final uses of all values live out of the block.
785 * They are necessary to build up real intervals.
787 be_lv_foreach(lv, block, be_lv_state_end, i) {
788 ir_node *irn = be_lv_get_irn(lv, block, i);
789 if(has_reg_class(env, irn)) {
790 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
791 bitset_set(live, get_irn_idx(irn));
792 border_use(irn, step, 0);
798 * Determine the last uses of a value inside the block, since they are
799 * relevant for the interval borders.
801 sched_foreach_reverse(block, irn) {
802 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
803 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
805 if (get_irn_mode(irn) == mode_T) {
806 const ir_edge_t *edge;
808 foreach_out_edge(irn, edge) {
809 ir_node *proj = get_edge_src_irn(edge);
812 * If the node defines some value, which can put into a
813 * register of the current class, make a border for it.
815 if(has_reg_class(env, proj)) {
816 int nr = get_irn_idx(proj);
818 bitset_clear(live, nr);
819 border_def(proj, step, 1);
825 * If the node defines some value, which can put into a
826 * register of the current class, make a border for it.
828 if(has_reg_class(env, irn)) {
829 int nr = get_irn_idx(irn);
831 bitset_clear(live, nr);
832 border_def(irn, step, 1);
836 * If the node is no phi node we can examine the uses.
839 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
840 ir_node *op = get_irn_n(irn, i);
842 if(has_reg_class(env, op)) {
843 int nr = get_irn_idx(op);
844 const char *msg = "-";
846 if(!bitset_is_set(live, nr)) {
847 border_use(op, step, 1);
848 bitset_set(live, nr);
852 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
859 bitset_foreach(live, elm) {
860 ir_node *irn = get_idx_irn(env->irg, elm);
861 if (be_is_live_in(lv, block, irn))
862 border_def(irn, step, 0);
866 static void assign(ir_node *block, void *env_ptr)
868 be_chordal_alloc_env_t *alloc_env = env_ptr;
869 be_chordal_env_t *env = alloc_env->chordal_env;
870 bitset_t *live = alloc_env->live;
871 bitset_t *colors = alloc_env->colors;
872 bitset_t *in_colors = alloc_env->in_colors;
873 struct list_head *head = get_block_border_head(env, block);
874 be_lv_t *lv = env->birg->lv;
880 bitset_clear_all(colors);
881 bitset_clear_all(live);
882 bitset_clear_all(in_colors);
884 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
885 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
886 list_for_each_entry(border_t, b, head, list) {
887 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
888 b->irn, get_irn_idx(b->irn)));
892 * Add initial defs for all values live in.
893 * Since their colors have already been assigned (The dominators were
894 * allocated before), we have to mark their colors as used also.
896 be_lv_foreach(lv, block, be_lv_state_in, idx) {
897 irn = be_lv_get_irn(lv, block, idx);
898 if(has_reg_class(env, irn)) {
899 const arch_register_t *reg = arch_get_irn_register(irn);
902 assert(reg && "Node must have been assigned a register");
903 col = arch_register_get_index(reg);
905 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
907 /* Mark the color of the live in value as used. */
908 bitset_set(colors, col);
909 bitset_set(in_colors, col);
911 /* Mark the value live in. */
912 bitset_set(live, get_irn_idx(irn));
917 * Mind that the sequence of defs from back to front defines a perfect
918 * elimination order. So, coloring the definitions from first to last
921 list_for_each_entry_reverse(border_t, b, head, list) {
922 ir_node *irn = b->irn;
923 int nr = get_irn_idx(irn);
924 int ignore = arch_irn_is(irn, ignore);
927 * Assign a color, if it is a local def. Global defs already have a
930 if(b->is_def && !be_is_live_in(lv, block, irn)) {
931 const arch_register_t *reg;
934 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
935 reg = arch_get_irn_register(irn);
937 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
939 col = get_next_free_reg(alloc_env, colors);
940 reg = arch_register_for_index(env->cls, col);
941 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
942 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
945 bitset_set(colors, col);
946 arch_set_irn_register(irn, reg);
948 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
950 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
951 bitset_set(live, nr);
954 /* Clear the color upon a use. */
955 else if(!b->is_def) {
956 const arch_register_t *reg = arch_get_irn_register(irn);
959 assert(reg && "Register must have been assigned");
961 col = arch_register_get_index(reg);
963 if(!arch_register_type_is(reg, ignore)) {
964 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
968 bitset_clear(colors, col);
969 bitset_clear(live, nr);
974 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
976 be_chordal_alloc_env_t env;
979 be_irg_t *birg = chordal_env->birg;
980 const arch_register_class_t *cls = chordal_env->cls;
982 int colors_n = arch_register_class_n_regs(cls);
983 ir_graph *irg = chordal_env->irg;
985 lv = be_assure_liveness(birg);
986 be_liveness_assure_sets(lv);
987 be_liveness_assure_chk(lv);
991 env.chordal_env = chordal_env;
992 env.colors_n = colors_n;
993 env.colors = bitset_alloca(colors_n);
994 env.tmp_colors = bitset_alloca(colors_n);
995 env.in_colors = bitset_alloca(colors_n);
996 env.pre_colored = pset_new_ptr_default();
998 BE_TIMER_PUSH(t_constr);
1000 /* Handle register targeting constraints */
1001 dom_tree_walk_irg(irg, constraints, NULL, &env);
1003 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1004 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1005 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1008 BE_TIMER_POP(t_constr);
1010 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1012 /* First, determine the pressure */
1013 dom_tree_walk_irg(irg, pressure, NULL, &env);
1015 /* Assign the colors */
1016 dom_tree_walk_irg(irg, assign, NULL, &env);
1018 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1020 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1021 plotter = new_plotter_ps(buf);
1022 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1023 plotter_free(plotter);
1026 bitset_free(env.live);
1027 del_pset(env.pre_colored);
1030 void be_init_chordal(void)
1032 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1035 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);