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];
419 for(i = insn->use_start; i < insn->n_ops; ++i) {
420 if(insn->ops[i].carrier == partner->carrier)
421 insn->ops[i].partner = out_op;
424 out_op->partner = partner;
425 partner->partner = out_op;
431 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
432 be_insn_t **the_insn)
434 be_chordal_env_t *env = alloc_env->chordal_env;
435 const arch_env_t *aenv = env->birg->main_env->arch_env;
436 be_insn_t *insn = *the_insn;
437 ir_node *perm = NULL;
438 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
439 const ir_edge_t *edge;
442 assert(insn->has_constraints && "only do this for constrained nodes");
445 Collect all registers that occur in output constraints.
446 This is necessary, since if the insn has one of these as an input constraint
447 and the corresponding operand interferes with the insn, the operand must
450 for(i = 0; i < insn->use_start; ++i) {
451 be_operand_t *op = &insn->ops[i];
452 if(op->has_constraints)
453 bitset_or(out_constr, op->regs);
457 Make the Perm, recompute liveness and re-scan the insn since the
458 in operands are now the Projs of the Perm.
460 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
462 /* Registers are propagated by insert_Perm_after(). Clean them here! */
466 be_stat_ev("constr_perm", get_irn_arity(perm));
467 foreach_out_edge(perm, edge) {
468 ir_node *proj = get_edge_src_irn(edge);
469 arch_set_irn_register(aenv, proj, NULL);
473 We also have to re-build the insn since the input operands are now the Projs of
474 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
475 the live sets may change.
477 // be_liveness_recompute(lv);
478 obstack_free(env->obst, insn);
479 *the_insn = insn = chordal_scan_insn(env, insn->irn);
482 Copy the input constraints of the insn to the Perm as output
483 constraints. Succeeding phases (coalescing) will need that.
485 for(i = insn->use_start; i < insn->n_ops; ++i) {
486 be_operand_t *op = &insn->ops[i];
487 ir_node *proj = op->carrier;
489 Note that the predecessor must not be a Proj of the Perm,
490 since ignore-nodes are not Perm'ed.
492 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
493 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
500 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
501 ir_node *irn, int *silent)
503 const arch_env_t *aenv;
506 ir_node **alloc_nodes;
507 hungarian_problem_t *bp;
512 const ir_edge_t *edge;
513 ir_node *perm = NULL;
515 be_chordal_env_t *env = alloc_env->chordal_env;
516 void *base = obstack_base(env->obst);
517 be_insn_t *insn = chordal_scan_insn(env, irn);
518 ir_node *res = insn->next_insn;
519 int be_silent = *silent;
520 be_irg_t *birg = env->birg;
522 if(insn->pre_colored) {
524 for(i = 0; i < insn->use_start; ++i)
525 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
529 If the current node is a barrier toggle the silent flag.
530 If we are in the start block, we are ought to be silent at the beginning,
531 so the toggling activates the constraint handling but skips the barrier.
532 If we are in the end block we handle the in requirements of the barrier
533 and set the rest to silent.
535 if(be_is_Barrier(irn))
542 Perms inserted before the constraint handling phase are considered to be
543 correctly precolored. These Perms arise during the ABI handling phase.
545 if(!insn->has_constraints)
548 aenv = env->birg->main_env->arch_env;
549 n_regs = env->cls->n_regs;
550 bs = bitset_alloca(n_regs);
551 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
552 bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
553 // bipartite_t *bp = bipartite_new(n_regs, n_regs);
554 assignment = alloca(n_regs * sizeof(assignment[0]));
555 partners = pmap_create();
558 prepare the constraint handling of this node.
559 Perms are constructed and Copies are created for constrained values
560 interfering with the instruction.
562 perm = pre_process_constraints(alloc_env, &insn);
564 /* find suitable in operands to the out operands of the node. */
565 pair_up_operands(alloc_env, insn);
568 look at the in/out operands and add each operand (and its possible partner)
569 to a bipartite graph (left: nodes with partners, right: admissible colors).
571 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
572 be_operand_t *op = &insn->ops[i];
575 If the operand has no partner or the partner has not been marked
576 for allocation, determine the admissible registers and mark it
577 for allocation by associating the node and its partner with the
578 set of admissible registers via a bipartite graph.
580 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
581 ir_node *partner = op->partner ? op->partner->carrier : NULL;
584 pmap_insert(partners, op->carrier, partner);
586 pmap_insert(partners, partner, op->carrier);
588 /* don't insert a node twice */
589 for(i = 0; i < n_alloc; ++i) {
590 if(alloc_nodes[i] == op->carrier) {
597 alloc_nodes[n_alloc] = op->carrier;
599 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
602 bitset_clear_all(bs);
603 get_decisive_partner_regs(bs, op, op->partner);
605 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
608 bitset_foreach(bs, col) {
609 hungarian_add(bp, n_alloc, col, 1);
610 // bipartite_add(bp, n_alloc, col);
618 Put all nodes which live through the constrained instruction also to the
619 allocation bipartite graph. They are considered unconstrained.
622 foreach_out_edge(perm, edge) {
624 ir_node *proj = get_edge_src_irn(edge);
626 assert(is_Proj(proj));
628 if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
631 /* don't insert a node twice */
632 for(i = 0; i < n_alloc; ++i) {
633 if(alloc_nodes[i] == proj) {
641 assert(n_alloc < n_regs);
643 alloc_nodes[n_alloc] = proj;
644 pmap_insert(partners, proj, NULL);
646 bitset_clear_all(bs);
647 arch_put_non_ignore_regs(aenv, env->cls, bs);
648 bitset_andnot(bs, env->ignore_colors);
649 bitset_foreach(bs, col) {
650 hungarian_add(bp, n_alloc, col, 1);
651 // bipartite_add(bp, n_alloc, col);
658 /* Compute a valid register allocation. */
659 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
660 match_res = hungarian_solve(bp, assignment, &cost, 1);
661 assert(match_res == 0 && "matching failed");
662 //bipartite_matching(bp, assignment);
664 /* Assign colors obtained from the matching. */
665 for(i = 0; i < n_alloc; ++i) {
666 const arch_register_t *reg;
670 assert(assignment[i] >= 0 && "there must have been a register assigned");
671 reg = arch_register_for_index(env->cls, assignment[i]);
673 nodes[0] = alloc_nodes[i];
674 nodes[1] = pmap_get(partners, alloc_nodes[i]);
676 for(j = 0; j < 2; ++j) {
680 assert(! (reg->type & arch_register_type_ignore));
681 arch_set_irn_register(aenv, nodes[j], reg);
682 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
683 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
687 /* Allocate the non-constrained Projs of the Perm. */
689 bitset_clear_all(bs);
691 /* Put the colors of all Projs in a bitset. */
692 foreach_out_edge(perm, edge) {
693 ir_node *proj = get_edge_src_irn(edge);
694 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
697 bitset_set(bs, reg->index);
700 /* Assign the not yet assigned Projs of the Perm a suitable color. */
701 foreach_out_edge(perm, edge) {
702 ir_node *proj = get_edge_src_irn(edge);
703 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
705 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
708 col = get_next_free_reg(alloc_env, bs);
709 reg = arch_register_for_index(env->cls, col);
710 bitset_set(bs, reg->index);
711 arch_set_irn_register(aenv, proj, reg);
712 pset_insert_ptr(alloc_env->pre_colored, proj);
713 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
718 //bipartite_free(bp);
720 pmap_destroy(partners);
723 obstack_free(env->obst, base);
728 * Handle constraint nodes in each basic block.
729 * handle_constraints() inserts Perm nodes which perm
730 * over all values live at the constrained node right in front
731 * of the constrained node. These Perms signal a constrained node.
732 * For further comments, refer to handle_constraints().
734 static void constraints(ir_node *bl, void *data)
736 be_chordal_alloc_env_t *env = data;
739 Start silent in the start block.
740 The silence remains until the first barrier is seen.
741 Each other block is begun loud.
743 int silent = bl == get_irg_start_block(get_irn_irg(bl));
747 If the block is the start block search the barrier and
748 start handling constraints from there.
751 for(irn = sched_first(bl); !sched_is_end(irn);) {
752 irn = handle_constraints(env, irn, &silent);
757 * Annotate the register pressure to the nodes and compute
758 * the liveness intervals.
759 * @param block The block to do it for.
760 * @param env_ptr The environment.
762 static void pressure(ir_node *block, void *env_ptr)
764 /* Convenience macro for a def */
765 #define border_def(irn, step, real) \
766 border_add(env, head, irn, step, pressure--, 1, real)
768 /* Convenience macro for a use */
769 #define border_use(irn, step, real) \
770 border_add(env, head, irn, step, ++pressure, 0, real)
772 be_chordal_alloc_env_t *alloc_env = env_ptr;
773 be_chordal_env_t *env = alloc_env->chordal_env;
774 bitset_t *live = alloc_env->live;
776 be_lv_t *lv = env->birg->lv;
781 unsigned pressure = 0;
782 struct list_head *head;
784 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
785 bitset_clear_all(live);
787 /* Set up the border list in the block info */
788 head = obstack_alloc(env->obst, sizeof(*head));
789 INIT_LIST_HEAD(head);
790 assert(pmap_get(env->border_heads, block) == NULL);
791 pmap_insert(env->border_heads, block, head);
794 * Make final uses of all values live out of the block.
795 * They are necessary to build up real intervals.
797 be_lv_foreach(lv, block, be_lv_state_end, i) {
798 ir_node *irn = be_lv_get_irn(lv, block, i);
799 if(has_reg_class(env, irn)) {
800 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
801 bitset_set(live, get_irn_idx(irn));
802 border_use(irn, step, 0);
808 * Determine the last uses of a value inside the block, since they are
809 * relevant for the interval borders.
811 sched_foreach_reverse(block, irn) {
812 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
813 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
815 #ifndef SCHEDULE_PROJS
816 if (get_irn_mode(irn) == mode_T) {
817 const ir_edge_t *edge;
819 foreach_out_edge(irn, edge) {
820 ir_node *proj = get_edge_src_irn(edge);
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, proj)) {
827 int nr = get_irn_idx(proj);
829 bitset_clear(live, nr);
830 border_def(proj, step, 1);
836 * If the node defines some value, which can put into a
837 * register of the current class, make a border for it.
839 if(has_reg_class(env, irn)) {
840 int nr = get_irn_idx(irn);
842 bitset_clear(live, nr);
843 border_def(irn, step, 1);
847 * If the node is no phi node we can examine the uses.
850 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
851 ir_node *op = get_irn_n(irn, i);
853 if(has_reg_class(env, op)) {
854 int nr = get_irn_idx(op);
855 const char *msg = "-";
857 if(!bitset_is_set(live, nr)) {
858 border_use(op, step, 1);
859 bitset_set(live, nr);
863 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
870 bitset_foreach(live, elm) {
871 ir_node *irn = get_idx_irn(env->irg, elm);
872 if (be_is_live_in(lv, block, irn))
873 border_def(irn, step, 0);
877 static void assign(ir_node *block, void *env_ptr)
879 be_chordal_alloc_env_t *alloc_env = env_ptr;
880 be_chordal_env_t *env = alloc_env->chordal_env;
881 bitset_t *live = alloc_env->live;
882 bitset_t *colors = alloc_env->colors;
883 bitset_t *in_colors = alloc_env->in_colors;
884 const arch_env_t *arch_env = env->birg->main_env->arch_env;
885 struct list_head *head = get_block_border_head(env, block);
886 be_lv_t *lv = env->birg->lv;
887 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
892 bitset_clear_all(colors);
893 bitset_clear_all(live);
894 bitset_clear_all(in_colors);
896 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
897 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
898 list_for_each_entry(border_t, b, head, list) {
899 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
900 b->irn, get_irn_idx(b->irn)));
904 * Add initial defs for all values live in.
905 * Since their colors have already been assigned (The dominators were
906 * allocated before), we have to mark their colors as used also.
908 foreach_pset(live_in, irn) {
909 if(has_reg_class(env, irn)) {
910 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
913 assert(reg && "Node must have been assigned a register");
914 col = arch_register_get_index(reg);
916 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
918 /* Mark the color of the live in value as used. */
919 bitset_set(colors, col);
920 bitset_set(in_colors, col);
922 /* Mark the value live in. */
923 bitset_set(live, get_irn_idx(irn));
928 * Mind that the sequence of defs from back to front defines a perfect
929 * elimination order. So, coloring the definitions from first to last
932 list_for_each_entry_reverse(border_t, b, head, list) {
933 ir_node *irn = b->irn;
934 int nr = get_irn_idx(irn);
935 int ignore = arch_irn_is(arch_env, irn, ignore);
938 * Assign a color, if it is a local def. Global defs already have a
941 if(b->is_def && !be_is_live_in(lv, block, irn)) {
942 const arch_register_t *reg;
945 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
946 reg = arch_get_irn_register(arch_env, irn);
948 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
950 col = get_next_free_reg(alloc_env, colors);
951 reg = arch_register_for_index(env->cls, col);
952 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
953 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
956 bitset_set(colors, col);
957 arch_set_irn_register(arch_env, irn, reg);
959 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
961 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
962 bitset_set(live, nr);
965 /* Clear the color upon a use. */
966 else if(!b->is_def) {
967 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
970 assert(reg && "Register must have been assigned");
972 col = arch_register_get_index(reg);
974 if(!arch_register_type_is(reg, ignore)) {
975 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
979 bitset_clear(colors, col);
980 bitset_clear(live, nr);
990 static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom)
992 be_chordal_env_t *env = alloc_env->chordal_env;
993 bitset_t *colors = alloc_env->colors;
994 bitset_t *in_colors = alloc_env->in_colors;
995 bitset_t *live = bitset_irg_malloc(env->irg);
996 const arch_env_t *arch_env = env->birg->main_env->arch_env;
997 be_irg_t *birg = env->birg;
1002 bitset_clear_all(colors);
1003 bitset_clear_all(in_colors);
1006 * All variables which are live in to this block are live out
1007 * of the immediate dominator thanks to SSA properties. As we
1008 * have already visited the immediate dominator, we know these
1009 * variables. The only tjing left is to check wheather they are live
1010 * in here (they also could be phi arguments to some ohi not
1011 * in this block, hence we have to check).
1013 bitset_foreach (live_end_dom, elm) {
1014 ir_node *irn = get_idx_irn(env->irg, elm);
1015 if (be_is_live_in(birg->lv, block, irn)) {
1016 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
1019 assert(be_is_live_in(env->birg->lv, block, irn));
1020 assert(reg && "Node must have been assigned a register");
1021 col = arch_register_get_index(reg);
1023 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
1025 /* Mark the color of the live in value as used. */
1026 bitset_set(colors, col);
1027 bitset_set(in_colors, col);
1029 /* Mark the value live in. */
1030 bitset_set(live, elm);
1034 assert(!be_is_live_in(env->birg->lv, block, irn));
1039 * Mind that the sequence of defs from back to front defines a perfect
1040 * elimination order. So, coloring the definitions from first to last
1043 sched_foreach (block, irn) {
1044 int nr = get_irn_idx(irn);
1045 int ignore = arch_irn_is(arch_env, irn, ignore);
1047 /* Clear the color upon a last use. */
1050 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1051 ir_node *op = get_irn_n(irn, i);
1054 * If the reg class matches and the operand is not live after
1055 * the node, irn is a last use of op and the register can
1058 if (has_reg_class(env, op)) {
1059 if (!be_lv_chk_after_irn(birg, op, irn)) {
1060 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
1063 assert(reg && "Register must have been assigned");
1064 col = arch_register_get_index(reg);
1065 bitset_clear(colors, col);
1066 bitset_clear(live, nr);
1072 if (has_reg_class(env, irn)) {
1073 const arch_register_t *reg;
1077 * Assign a color, if it is a local def. Global defs already have a
1080 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
1081 reg = arch_get_irn_register(arch_env, irn);
1083 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
1085 col = get_next_free_reg(alloc_env, colors);
1086 reg = arch_register_for_index(env->cls, col);
1087 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
1088 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
1091 bitset_set(colors, col);
1092 arch_set_irn_register(arch_env, irn, reg);
1094 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
1096 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
1097 bitset_set(live, nr);
1102 dominates_for_each (block, irn) {
1103 assign_new(irn, alloc_env, live);
1109 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
1111 be_chordal_alloc_env_t env;
1114 be_irg_t *birg = chordal_env->birg;
1115 const arch_register_class_t *cls = chordal_env->cls;
1117 int colors_n = arch_register_class_n_regs(cls);
1118 ir_graph *irg = chordal_env->irg;
1119 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
1121 /* some special classes contain only ignore regs, no work to be done */
1122 if(allocatable_regs == 0)
1125 be_assure_dom_front(birg);
1126 lv = be_assure_liveness(birg);
1127 be_liveness_assure_sets(lv);
1128 be_liveness_assure_chk(lv);
1132 env.chordal_env = chordal_env;
1133 env.colors_n = colors_n;
1134 env.colors = bitset_alloca(colors_n);
1135 env.tmp_colors = bitset_alloca(colors_n);
1136 env.in_colors = bitset_alloca(colors_n);
1137 env.pre_colored = pset_new_ptr_default();
1139 /* Handle register targeting constraints */
1140 dom_tree_walk_irg(irg, constraints, NULL, &env);
1142 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1143 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1144 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1147 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1149 /* First, determine the pressure */
1150 dom_tree_walk_irg(irg, pressure, NULL, &env);
1152 /* Assign the colors */
1153 #ifdef NEW_STYLE_ASSIGN
1154 assign_new(get_irg_start_block(irg), &env, env.live);
1156 dom_tree_walk_irg(irg, assign, NULL, &env);
1159 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1161 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1162 plotter = new_plotter_ps(buf);
1163 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1164 plotter_free(plotter);
1167 bitset_free(env.live);
1168 del_pset(env.pre_colored);
1171 void be_init_chordal(void)
1173 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1176 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);