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"
56 #include "besched_t.h"
63 #include "bestatevent.h"
65 #include "beintlive_t.h"
67 #include "bechordal_t.h"
68 #include "bechordal_draw.h"
71 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
75 #define DUMP_INTERVALS
77 /* new style assign routine without borders. */
78 #undef NEW_STYLE_ASSIGN
80 typedef struct _be_chordal_alloc_env_t {
81 be_chordal_env_t *chordal_env;
83 pset *pre_colored; /**< Set of precolored nodes. */
84 bitset_t *live; /**< A liveness bitset. */
85 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
86 bitset_t *colors; /**< The color mask. */
87 bitset_t *in_colors; /**< Colors used by live in values. */
88 int colors_n; /**< The number of colors. */
89 } be_chordal_alloc_env_t;
93 /* Make a fourcc for border checking. */
94 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
97 static void check_border_list(struct list_head *head)
100 list_for_each_entry(border_t, x, head, list) {
101 assert(x->magic == BORDER_FOURCC);
105 static void check_heads(be_chordal_env_t *env)
108 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
109 /* ir_printf("checking border list of block %+F\n", ent->key); */
110 check_border_list(ent->value);
116 * Add an interval border to the list of a block's list
117 * of interval border.
118 * @note You always have to create the use before the def.
119 * @param env The environment.
120 * @param head The list head to enqueue the borders.
121 * @param irn The node (value) the border belongs to.
122 * @param pressure The pressure at this point in time.
123 * @param step A time step for the border.
124 * @param is_def Is the border a use or a def.
125 * @return The created border.
127 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
128 ir_node *irn, unsigned step, unsigned pressure,
129 unsigned is_def, unsigned is_real)
136 b = obstack_alloc(env->obst, sizeof(*b));
138 /* also allocate the def and tie it to the use. */
139 def = obstack_alloc(env->obst, sizeof(*def));
140 memset(def, 0, sizeof(*def));
145 * Set the link field of the irn to the def.
146 * This strongly relies on the fact, that the use is always
147 * made before the def.
149 set_irn_link(irn, def);
151 DEBUG_ONLY(b->magic = BORDER_FOURCC);
152 DEBUG_ONLY(def->magic = BORDER_FOURCC);
156 * If the def is encountered, the use was made and so was the
157 * the def node (see the code above). It was placed into the
158 * link field of the irn, so we can get it there.
161 b = get_irn_link(irn);
163 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
166 b->pressure = pressure;
168 b->is_real = is_real;
171 list_add_tail(&b->list, head);
172 DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
179 * Check, if an irn is of the register class currently under processing.
180 * @param env The chordal environment.
181 * @param irn The node.
182 * @return 1, if the node is of that register class, 0 if not.
184 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
186 return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
189 #define has_limited_constr(req, irn) \
190 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
192 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
194 bitset_t *tmp = alloc_env->tmp_colors;
195 bitset_copy(tmp, colors);
196 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
197 return bitset_next_clear(tmp, 0);
200 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
205 bitset_copy(bs, o2->regs);
210 bitset_copy(bs, o1->regs);
214 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
216 if(bitset_contains(o1->regs, o2->regs))
217 bitset_copy(bs, o1->regs);
218 else if(bitset_contains(o2->regs, o1->regs))
219 bitset_copy(bs, o2->regs);
226 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
230 ie.ignore_colors = env->ignore_colors;
231 ie.aenv = env->birg->main_env->arch_env;
234 return be_scan_insn(&ie, irn);
237 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
239 const be_irg_t *birg = env->birg;
240 const arch_env_t *aenv = birg->main_env->arch_env;
241 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
242 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
243 ir_node *bl = get_nodes_block(irn);
244 be_lv_t *lv = env->birg->lv;
249 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
250 ir_node *op = get_irn_n(irn, i);
252 const arch_register_t *reg;
253 const arch_register_req_t *req;
255 if (arch_get_irn_reg_class(aenv, irn, i) != env->cls)
258 reg = arch_get_irn_register(aenv, op);
260 if (reg == NULL || !arch_register_type_is(reg, ignore))
262 if(arch_register_type_is(reg, joker))
265 req = arch_get_register_req(aenv, irn, i);
266 if (!arch_register_req_is(req, limited))
269 if (rbitset_is_set(req->limited, reg->index))
272 copy = be_new_Copy(env->cls, env->irg, bl, op);
273 be_stat_ev("constr_copy", 1);
275 sched_add_before(irn, copy);
276 set_irn_n(irn, i, copy);
277 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
280 insn = chordal_scan_insn(env, irn);
282 if(!insn->has_constraints)
285 /* insert copies for nodes that occur constrained more than once. */
286 for(i = insn->use_start; i < insn->n_ops; ++i) {
287 be_operand_t *op = &insn->ops[i];
289 if(!op->has_constraints)
292 for(j = i + 1; j < insn->n_ops; ++j) {
294 be_operand_t *a_op = &insn->ops[j];
296 if(a_op->carrier != op->carrier || !a_op->has_constraints)
299 if (be_is_Copy(get_irn_n(insn->irn, a_op->pos)))
302 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
303 be_stat_ev("constr_copy", 1);
305 sched_add_before(insn->irn, copy);
306 set_irn_n(insn->irn, a_op->pos, copy);
307 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
311 /* collect all registers occuring in out constraints. */
312 for(i = 0; i < insn->use_start; ++i) {
313 be_operand_t *op = &insn->ops[i];
314 if(op->has_constraints)
315 bitset_or(def_constr, op->regs);
319 insert copies for all constrained arguments living through the node
320 and being constrained to a register which also occurs in out constraints.
322 for(i = insn->use_start; i < insn->n_ops; ++i) {
324 be_operand_t *op = &insn->ops[i];
326 bitset_copy(tmp, op->regs);
327 bitset_and(tmp, def_constr);
331 1) the operand is constrained.
332 2) lives through the node.
333 3) is constrained to a register occuring in out constraints.
335 if(!op->has_constraints ||
336 !values_interfere(birg, insn->irn, op->carrier) ||
337 bitset_popcnt(tmp) == 0)
341 only create the copy if the operand is no copy.
342 this is necessary since the assure constraints phase inserts
343 Copies and Keeps for operands which must be different from the results.
344 Additional copies here would destroy this.
346 if (be_is_Copy(get_irn_n(insn->irn, op->pos)))
349 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
351 sched_add_before(insn->irn, copy);
352 set_irn_n(insn->irn, op->pos, copy);
353 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
354 be_liveness_update(lv, op->carrier);
358 obstack_free(env->obst, insn);
359 return insn->next_insn;
362 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
364 be_chordal_env_t *env = data;
366 for(irn = sched_first(bl); !sched_is_end(irn);) {
367 irn = prepare_constr_insn(env, irn);
371 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
372 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
375 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
377 const be_chordal_env_t *env = alloc_env->chordal_env;
379 int n_uses = be_insn_n_uses(insn);
380 int n_defs = be_insn_n_defs(insn);
381 bitset_t *bs = bitset_alloca(env->cls->n_regs);
382 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
387 For each out operand, try to find an in operand which can be assigned the
388 same register as the out operand.
390 for (j = 0; j < insn->use_start; ++j) {
392 int smallest_n_regs = 2 * env->cls->n_regs + 1;
393 be_operand_t *out_op = &insn->ops[j];
395 /* Try to find an in operand which has ... */
396 for(i = insn->use_start; i < insn->n_ops; ++i) {
398 const be_operand_t *op = &insn->ops[i];
400 if (op->partner != NULL)
402 if (values_interfere(env->birg, op->irn, op->carrier))
405 bitset_clear_all(bs);
406 bitset_copy(bs, op->regs);
407 bitset_and(bs, out_op->regs);
408 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
410 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
412 smallest_n_regs = n_total;
417 be_operand_t *partner = &insn->ops[smallest];
418 out_op->partner = partner;
419 partner->partner = out_op;
425 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
426 be_insn_t **the_insn)
428 be_chordal_env_t *env = alloc_env->chordal_env;
429 const arch_env_t *aenv = env->birg->main_env->arch_env;
430 be_insn_t *insn = *the_insn;
431 ir_node *perm = NULL;
432 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
433 const ir_edge_t *edge;
436 assert(insn->has_constraints && "only do this for constrained nodes");
439 Collect all registers that occur in output constraints.
440 This is necessary, since if the insn has one of these as an input constraint
441 and the corresponding operand interferes with the insn, the operand must
444 for(i = 0; i < insn->use_start; ++i) {
445 be_operand_t *op = &insn->ops[i];
446 if(op->has_constraints)
447 bitset_or(out_constr, op->regs);
451 Make the Perm, recompute liveness and re-scan the insn since the
452 in operands are now the Projs of the Perm.
454 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
456 /* Registers are propagated by insert_Perm_after(). Clean them here! */
460 be_stat_ev("constr_perm", get_irn_arity(perm));
461 foreach_out_edge(perm, edge) {
462 ir_node *proj = get_edge_src_irn(edge);
463 arch_set_irn_register(aenv, proj, NULL);
467 We also have to re-build the insn since the input operands are now the Projs of
468 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
469 the live sets may change.
471 // be_liveness_recompute(lv);
472 obstack_free(env->obst, insn);
473 *the_insn = insn = chordal_scan_insn(env, insn->irn);
476 Copy the input constraints of the insn to the Perm as output
477 constraints. Succeeding phases (coalescing) will need that.
479 for(i = insn->use_start; i < insn->n_ops; ++i) {
480 be_operand_t *op = &insn->ops[i];
481 ir_node *proj = op->carrier;
483 Note that the predecessor must not be a Proj of the Perm,
484 since ignore-nodes are not Perm'ed.
486 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
487 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
494 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
496 const arch_env_t *aenv;
499 ir_node **alloc_nodes;
500 hungarian_problem_t *bp;
505 const ir_edge_t *edge;
506 ir_node *perm = NULL;
508 be_chordal_env_t *env = alloc_env->chordal_env;
509 void *base = obstack_base(env->obst);
510 be_insn_t *insn = chordal_scan_insn(env, irn);
511 ir_node *res = insn->next_insn;
512 int be_silent = *silent;
513 be_irg_t *birg = env->birg;
515 if(insn->pre_colored) {
517 for(i = 0; i < insn->use_start; ++i)
518 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
522 If the current node is a barrier toggle the silent flag.
523 If we are in the start block, we are ought to be silent at the beginning,
524 so the toggling activates the constraint handling but skips the barrier.
525 If we are in the end block we handle the in requirements of the barrier
526 and set the rest to silent.
528 if(be_is_Barrier(irn))
535 Perms inserted before the constraint handling phase are considered to be
536 correctly precolored. These Perms arise during the ABI handling phase.
538 if(!insn->has_constraints)
541 aenv = env->birg->main_env->arch_env;
542 n_regs = env->cls->n_regs;
543 bs = bitset_alloca(n_regs);
544 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
545 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
546 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
547 assignment = alloca(n_regs * sizeof(assignment[0]));
548 partners = pmap_create();
551 prepare the constraint handling of this node.
552 Perms are constructed and Copies are created for constrained values
553 interfering with the instruction.
555 perm = pre_process_constraints(alloc_env, &insn);
557 /* find suitable in operands to the out operands of the node. */
558 pair_up_operands(alloc_env, insn);
561 look at the in/out operands and add each operand (and its possible partner)
562 to a bipartite graph (left: nodes with partners, right: admissible colors).
564 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
565 be_operand_t *op = &insn->ops[i];
568 If the operand has no partner or the partner has not been marked
569 for allocation, determine the admissible registers and mark it
570 for allocation by associating the node and its partner with the
571 set of admissible registers via a bipartite graph.
573 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
575 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
576 alloc_nodes[n_alloc] = op->carrier;
578 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
580 bitset_clear_all(bs);
581 get_decisive_partner_regs(bs, op, op->partner);
583 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
585 bitset_foreach(bs, col) {
586 hungarian_add(bp, n_alloc, col, 1);
587 // bipartite_add(bp, n_alloc, col);
595 Put all nodes which live through the constrained instruction also to the
596 allocation bipartite graph. They are considered unconstrained.
599 foreach_out_edge(perm, edge) {
600 ir_node *proj = get_edge_src_irn(edge);
602 assert(is_Proj(proj));
604 if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
607 assert(n_alloc < n_regs);
608 alloc_nodes[n_alloc] = proj;
609 pmap_insert(partners, proj, NULL);
611 bitset_clear_all(bs);
612 arch_put_non_ignore_regs(aenv, env->cls, bs);
613 bitset_andnot(bs, env->ignore_colors);
614 bitset_foreach(bs, col) {
615 hungarian_add(bp, n_alloc, col, 1);
616 // bipartite_add(bp, n_alloc, col);
623 /* Compute a valid register allocation. */
624 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
625 match_res = hungarian_solve(bp, assignment, &cost, 1);
626 assert(match_res == 0 && "matching failed");
627 //bipartite_matching(bp, assignment);
629 /* Assign colors obtained from the matching. */
630 for(i = 0; i < n_alloc; ++i) {
631 const arch_register_t *reg;
635 assert(assignment[i] >= 0 && "there must have been a register assigned");
636 reg = arch_register_for_index(env->cls, assignment[i]);
638 nodes[0] = alloc_nodes[i];
639 nodes[1] = pmap_get(partners, alloc_nodes[i]);
641 for(j = 0; j < 2; ++j) {
645 arch_set_irn_register(aenv, nodes[j], reg);
646 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
647 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
651 /* Allocate the non-constrained Projs of the Perm. */
653 bitset_clear_all(bs);
655 /* Put the colors of all Projs in a bitset. */
656 foreach_out_edge(perm, edge) {
657 ir_node *proj = get_edge_src_irn(edge);
658 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
661 bitset_set(bs, reg->index);
664 /* Assign the not yet assigned Projs of the Perm a suitable color. */
665 foreach_out_edge(perm, edge) {
666 ir_node *proj = get_edge_src_irn(edge);
667 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
669 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
672 col = get_next_free_reg(alloc_env, bs);
673 reg = arch_register_for_index(env->cls, col);
674 bitset_set(bs, reg->index);
675 arch_set_irn_register(aenv, proj, reg);
676 pset_insert_ptr(alloc_env->pre_colored, proj);
677 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
682 //bipartite_free(bp);
684 pmap_destroy(partners);
687 obstack_free(env->obst, base);
692 * Handle constraint nodes in each basic block.
693 * handle_constraints() inserts Perm nodes which perm
694 * over all values live at the constrained node right in front
695 * of the constrained node. These Perms signal a constrained node.
696 * For further comments, refer to handle_constraints().
698 static void constraints(ir_node *bl, void *data)
700 be_chordal_alloc_env_t *env = data;
703 Start silent in the start block.
704 The silence remains until the first barrier is seen.
705 Each other block is begun loud.
707 int silent = bl == get_irg_start_block(get_irn_irg(bl));
711 If the block is the start block search the barrier and
712 start handling constraints from there.
715 for(irn = sched_first(bl); !sched_is_end(irn);) {
716 irn = handle_constraints(env, irn, &silent);
721 * Annotate the register pressure to the nodes and compute
722 * the liveness intervals.
723 * @param block The block to do it for.
724 * @param env_ptr The environment.
726 static void pressure(ir_node *block, void *env_ptr)
728 /* Convenience macro for a def */
729 #define border_def(irn, step, real) \
730 border_add(env, head, irn, step, pressure--, 1, real)
732 /* Convenience macro for a use */
733 #define border_use(irn, step, real) \
734 border_add(env, head, irn, step, ++pressure, 0, real)
736 be_chordal_alloc_env_t *alloc_env = env_ptr;
737 be_chordal_env_t *env = alloc_env->chordal_env;
738 bitset_t *live = alloc_env->live;
740 be_lv_t *lv = env->birg->lv;
745 unsigned pressure = 0;
746 struct list_head *head;
748 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
749 bitset_clear_all(live);
751 /* Set up the border list in the block info */
752 head = obstack_alloc(env->obst, sizeof(*head));
753 INIT_LIST_HEAD(head);
754 assert(pmap_get(env->border_heads, block) == NULL);
755 pmap_insert(env->border_heads, block, head);
758 * Make final uses of all values live out of the block.
759 * They are necessary to build up real intervals.
761 be_lv_foreach(lv, block, be_lv_state_end, i) {
762 ir_node *irn = be_lv_get_irn(lv, block, i);
763 if(has_reg_class(env, irn)) {
764 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
765 bitset_set(live, get_irn_idx(irn));
766 border_use(irn, step, 0);
772 * Determine the last uses of a value inside the block, since they are
773 * relevant for the interval borders.
775 sched_foreach_reverse(block, irn) {
776 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
777 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
779 #ifndef SCHEDULE_PROJS
780 if (get_irn_mode(irn) == mode_T) {
781 const ir_edge_t *edge;
783 foreach_out_edge(irn, edge) {
784 ir_node *proj = get_edge_src_irn(edge);
787 * If the node defines some value, which can put into a
788 * register of the current class, make a border for it.
790 if(has_reg_class(env, proj)) {
791 int nr = get_irn_idx(proj);
793 bitset_clear(live, nr);
794 border_def(proj, step, 1);
800 * If the node defines some value, which can put into a
801 * register of the current class, make a border for it.
803 if(has_reg_class(env, irn)) {
804 int nr = get_irn_idx(irn);
806 bitset_clear(live, nr);
807 border_def(irn, step, 1);
811 * If the node is no phi node we can examine the uses.
814 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
815 ir_node *op = get_irn_n(irn, i);
817 if(has_reg_class(env, op)) {
818 int nr = get_irn_idx(op);
819 const char *msg = "-";
821 if(!bitset_is_set(live, nr)) {
822 border_use(op, step, 1);
823 bitset_set(live, nr);
827 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
834 bitset_foreach(live, elm) {
835 ir_node *irn = get_idx_irn(env->irg, elm);
836 if (be_is_live_in(lv, block, irn))
837 border_def(irn, step, 0);
841 static void assign(ir_node *block, void *env_ptr)
843 be_chordal_alloc_env_t *alloc_env = env_ptr;
844 be_chordal_env_t *env = alloc_env->chordal_env;
845 bitset_t *live = alloc_env->live;
846 bitset_t *colors = alloc_env->colors;
847 bitset_t *in_colors = alloc_env->in_colors;
848 const arch_env_t *arch_env = env->birg->main_env->arch_env;
849 struct list_head *head = get_block_border_head(env, block);
850 be_lv_t *lv = env->birg->lv;
851 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
856 bitset_clear_all(colors);
857 bitset_clear_all(live);
858 bitset_clear_all(in_colors);
860 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
861 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
862 list_for_each_entry(border_t, b, head, list) {
863 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
864 b->irn, get_irn_idx(b->irn)));
868 * Add initial defs for all values live in.
869 * Since their colors have already been assigned (The dominators were
870 * allocated before), we have to mark their colors as used also.
872 foreach_pset(live_in, irn) {
873 if(has_reg_class(env, irn)) {
874 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
877 assert(reg && "Node must have been assigned a register");
878 col = arch_register_get_index(reg);
880 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
882 /* Mark the color of the live in value as used. */
883 bitset_set(colors, col);
884 bitset_set(in_colors, col);
886 /* Mark the value live in. */
887 bitset_set(live, get_irn_idx(irn));
892 * Mind that the sequence of defs from back to front defines a perfect
893 * elimination order. So, coloring the definitions from first to last
896 list_for_each_entry_reverse(border_t, b, head, list) {
897 ir_node *irn = b->irn;
898 int nr = get_irn_idx(irn);
899 int ignore = arch_irn_is(arch_env, irn, ignore);
902 * Assign a color, if it is a local def. Global defs already have a
905 if(b->is_def && !be_is_live_in(lv, block, irn)) {
906 const arch_register_t *reg;
909 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
910 reg = arch_get_irn_register(arch_env, irn);
912 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
914 col = get_next_free_reg(alloc_env, colors);
915 reg = arch_register_for_index(env->cls, col);
916 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
917 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
920 bitset_set(colors, col);
921 arch_set_irn_register(arch_env, irn, reg);
923 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
925 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
926 bitset_set(live, nr);
929 /* Clear the color upon a use. */
930 else if(!b->is_def) {
931 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
934 assert(reg && "Register must have been assigned");
936 col = arch_register_get_index(reg);
938 if(!arch_register_type_is(reg, ignore)) {
939 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
943 bitset_clear(colors, col);
944 bitset_clear(live, nr);
954 static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom)
956 be_chordal_env_t *env = alloc_env->chordal_env;
957 bitset_t *colors = alloc_env->colors;
958 bitset_t *in_colors = alloc_env->in_colors;
959 bitset_t *live = bitset_irg_malloc(env->irg);
960 const arch_env_t *arch_env = env->birg->main_env->arch_env;
961 be_irg_t *birg = env->birg;
966 bitset_clear_all(colors);
967 bitset_clear_all(in_colors);
970 * All variables which are live in to this block are live out
971 * of the immediate dominator thanks to SSA properties. As we
972 * have already visited the immediate dominator, we know these
973 * variables. The only tjing left is to check wheather they are live
974 * in here (they also could be phi arguments to some ohi not
975 * in this block, hence we have to check).
977 bitset_foreach (live_end_dom, elm) {
978 ir_node *irn = get_idx_irn(env->irg, elm);
979 if (be_is_live_in(birg->lv, block, irn)) {
980 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
983 assert(be_is_live_in(env->birg->lv, block, irn));
984 assert(reg && "Node must have been assigned a register");
985 col = arch_register_get_index(reg);
987 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
989 /* Mark the color of the live in value as used. */
990 bitset_set(colors, col);
991 bitset_set(in_colors, col);
993 /* Mark the value live in. */
994 bitset_set(live, elm);
998 assert(!be_is_live_in(env->birg->lv, block, irn));
1003 * Mind that the sequence of defs from back to front defines a perfect
1004 * elimination order. So, coloring the definitions from first to last
1007 sched_foreach (block, irn) {
1008 int nr = get_irn_idx(irn);
1009 int ignore = arch_irn_is(arch_env, irn, ignore);
1011 /* Clear the color upon a last use. */
1014 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1015 ir_node *op = get_irn_n(irn, i);
1018 * If the reg class matches and the operand is not live after
1019 * the node, irn is a last use of op and the register can
1022 if (has_reg_class(env, op)) {
1023 if (!be_lv_chk_after_irn(birg, op, irn)) {
1024 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
1027 assert(reg && "Register must have been assigned");
1028 col = arch_register_get_index(reg);
1029 bitset_clear(colors, col);
1030 bitset_clear(live, nr);
1036 if (has_reg_class(env, irn)) {
1037 const arch_register_t *reg;
1041 * Assign a color, if it is a local def. Global defs already have a
1044 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
1045 reg = arch_get_irn_register(arch_env, irn);
1047 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
1049 col = get_next_free_reg(alloc_env, colors);
1050 reg = arch_register_for_index(env->cls, col);
1051 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
1052 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
1055 bitset_set(colors, col);
1056 arch_set_irn_register(arch_env, irn, reg);
1058 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
1060 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
1061 bitset_set(live, nr);
1066 dominates_for_each (block, irn) {
1067 assign_new(irn, alloc_env, live);
1073 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
1075 be_chordal_alloc_env_t env;
1078 be_irg_t *birg = chordal_env->birg;
1079 const arch_register_class_t *cls = chordal_env->cls;
1081 int colors_n = arch_register_class_n_regs(cls);
1082 ir_graph *irg = chordal_env->irg;
1083 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
1085 /* some special classes contain only ignore regs, no work to be done */
1086 if(allocatable_regs == 0)
1089 be_assure_dom_front(birg);
1090 lv = be_assure_liveness(birg);
1091 be_liveness_assure_sets(lv);
1092 be_liveness_assure_chk(lv);
1096 env.chordal_env = chordal_env;
1097 env.colors_n = colors_n;
1098 env.colors = bitset_alloca(colors_n);
1099 env.tmp_colors = bitset_alloca(colors_n);
1100 env.in_colors = bitset_alloca(colors_n);
1101 env.pre_colored = pset_new_ptr_default();
1103 /* Handle register targeting constraints */
1104 dom_tree_walk_irg(irg, constraints, NULL, &env);
1106 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1107 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1108 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1111 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1113 /* First, determine the pressure */
1114 dom_tree_walk_irg(irg, pressure, NULL, &env);
1116 /* Assign the colors */
1117 #ifdef NEW_STYLE_ASSIGN
1118 assign_new(get_irg_start_block(irg), &env, env.live);
1120 dom_tree_walk_irg(irg, assign, NULL, &env);
1123 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1125 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1126 plotter = new_plotter_ps(buf);
1127 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1128 plotter_free(plotter);
1131 bitset_free(env.live);
1132 del_pset(env.pre_colored);
1135 void be_init_chordal(void)
1137 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1140 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);