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 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
300 be_stat_ev("constr_copy", 1);
302 sched_add_before(insn->irn, copy);
303 set_irn_n(insn->irn, a_op->pos, copy);
304 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
308 /* collect all registers occuring in out constraints. */
309 for(i = 0; i < insn->use_start; ++i) {
310 be_operand_t *op = &insn->ops[i];
311 if(op->has_constraints)
312 bitset_or(def_constr, op->regs);
316 insert copies for all constrained arguments living through the node
317 and being constrained to a register which also occurs in out constraints.
319 for(i = insn->use_start; i < insn->n_ops; ++i) {
321 be_operand_t *op = &insn->ops[i];
323 bitset_copy(tmp, op->regs);
324 bitset_and(tmp, def_constr);
328 1) the operand is constrained.
329 2) lives through the node.
330 3) is constrained to a register occuring in out constraints.
332 if(!op->has_constraints ||
333 !values_interfere(birg, insn->irn, op->carrier) ||
334 bitset_popcnt(tmp) == 0)
338 only create the copy if the operand is no copy.
339 this is necessary since the assure constraints phase inserts
340 Copies and Keeps for operands which must be different from the results.
341 Additional copies here would destroy this.
343 if(be_is_Copy(op->carrier))
346 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
348 sched_add_before(insn->irn, copy);
349 set_irn_n(insn->irn, op->pos, copy);
350 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
351 be_liveness_update(lv, op->carrier);
355 obstack_free(env->obst, insn);
356 return insn->next_insn;
359 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
361 be_chordal_env_t *env = data;
363 for(irn = sched_first(bl); !sched_is_end(irn);) {
364 irn = prepare_constr_insn(env, irn);
368 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
369 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
372 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
374 const be_chordal_env_t *env = alloc_env->chordal_env;
376 int n_uses = be_insn_n_uses(insn);
377 int n_defs = be_insn_n_defs(insn);
378 bitset_t *bs = bitset_alloca(env->cls->n_regs);
379 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
384 For each out operand, try to find an in operand which can be assigned the
385 same register as the out operand.
387 for (j = 0; j < insn->use_start; ++j) {
389 int smallest_n_regs = 2 * env->cls->n_regs + 1;
390 be_operand_t *out_op = &insn->ops[j];
392 /* Try to find an in operand which has ... */
393 for(i = insn->use_start; i < insn->n_ops; ++i) {
395 const be_operand_t *op = &insn->ops[i];
397 if (op->partner != NULL)
399 if (values_interfere(env->birg, op->irn, op->carrier))
402 bitset_clear_all(bs);
403 bitset_copy(bs, op->regs);
404 bitset_and(bs, out_op->regs);
405 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
407 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
409 smallest_n_regs = n_total;
414 be_operand_t *partner = &insn->ops[smallest];
415 out_op->partner = partner;
416 partner->partner = out_op;
422 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
423 be_insn_t **the_insn)
425 be_chordal_env_t *env = alloc_env->chordal_env;
426 const arch_env_t *aenv = env->birg->main_env->arch_env;
427 be_insn_t *insn = *the_insn;
428 ir_node *perm = NULL;
429 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
430 const ir_edge_t *edge;
433 assert(insn->has_constraints && "only do this for constrained nodes");
436 Collect all registers that occur in output constraints.
437 This is necessary, since if the insn has one of these as an input constraint
438 and the corresponding operand interferes with the insn, the operand must
441 for(i = 0; i < insn->use_start; ++i) {
442 be_operand_t *op = &insn->ops[i];
443 if(op->has_constraints)
444 bitset_or(out_constr, op->regs);
448 Make the Perm, recompute liveness and re-scan the insn since the
449 in operands are now the Projs of the Perm.
451 perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
453 /* Registers are propagated by insert_Perm_after(). Clean them here! */
457 be_stat_ev("constr_perm", get_irn_arity(perm));
458 foreach_out_edge(perm, edge) {
459 ir_node *proj = get_edge_src_irn(edge);
460 arch_set_irn_register(aenv, proj, NULL);
464 We also have to re-build the insn since the input operands are now the Projs of
465 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
466 the live sets may change.
468 // be_liveness_recompute(lv);
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, ir_node *irn, int *silent)
493 const arch_env_t *aenv;
496 ir_node **alloc_nodes;
497 hungarian_problem_t *bp;
502 const ir_edge_t *edge;
503 ir_node *perm = NULL;
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;
512 if(insn->pre_colored) {
514 for(i = 0; i < insn->use_start; ++i)
515 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
519 If the current node is a barrier toggle the silent flag.
520 If we are in the start block, we are ought to be silent at the beginning,
521 so the toggling activates the constraint handling but skips the barrier.
522 If we are in the end block we handle the in requirements of the barrier
523 and set the rest to silent.
525 if(be_is_Barrier(irn))
532 Perms inserted before the constraint handling phase are considered to be
533 correctly precolored. These Perms arise during the ABI handling phase.
535 if(!insn->has_constraints)
538 aenv = env->birg->main_env->arch_env;
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 // bipartite_t *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)) {
572 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
573 alloc_nodes[n_alloc] = op->carrier;
575 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
577 bitset_clear_all(bs);
578 get_decisive_partner_regs(bs, op, op->partner);
580 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
582 bitset_foreach(bs, col) {
583 hungarian_add(bp, n_alloc, col, 1);
584 // bipartite_add(bp, n_alloc, col);
592 Put all nodes which live through the constrained instruction also to the
593 allocation bipartite graph. They are considered unconstrained.
596 foreach_out_edge(perm, edge) {
597 ir_node *proj = get_edge_src_irn(edge);
599 assert(is_Proj(proj));
601 if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
604 assert(n_alloc < n_regs);
605 alloc_nodes[n_alloc] = proj;
606 pmap_insert(partners, proj, NULL);
608 bitset_clear_all(bs);
609 arch_put_non_ignore_regs(aenv, env->cls, bs);
610 bitset_andnot(bs, env->ignore_colors);
611 bitset_foreach(bs, col) {
612 hungarian_add(bp, n_alloc, col, 1);
613 // bipartite_add(bp, n_alloc, col);
620 /* Compute a valid register allocation. */
621 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
622 match_res = hungarian_solve(bp, assignment, &cost, 1);
623 assert(match_res == 0 && "matching failed");
624 //bipartite_matching(bp, assignment);
626 /* Assign colors obtained from the matching. */
627 for(i = 0; i < n_alloc; ++i) {
628 const arch_register_t *reg;
632 assert(assignment[i] >= 0 && "there must have been a register assigned");
633 reg = arch_register_for_index(env->cls, assignment[i]);
635 nodes[0] = alloc_nodes[i];
636 nodes[1] = pmap_get(partners, alloc_nodes[i]);
638 for(j = 0; j < 2; ++j) {
642 arch_set_irn_register(aenv, nodes[j], reg);
643 (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
644 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
648 /* Allocate the non-constrained Projs of the Perm. */
650 bitset_clear_all(bs);
652 /* Put the colors of all Projs in a bitset. */
653 foreach_out_edge(perm, edge) {
654 ir_node *proj = get_edge_src_irn(edge);
655 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
658 bitset_set(bs, reg->index);
661 /* Assign the not yet assigned Projs of the Perm a suitable color. */
662 foreach_out_edge(perm, edge) {
663 ir_node *proj = get_edge_src_irn(edge);
664 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
666 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
669 col = get_next_free_reg(alloc_env, bs);
670 reg = arch_register_for_index(env->cls, col);
671 bitset_set(bs, reg->index);
672 arch_set_irn_register(aenv, proj, reg);
673 pset_insert_ptr(alloc_env->pre_colored, proj);
674 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
679 //bipartite_free(bp);
681 pmap_destroy(partners);
684 obstack_free(env->obst, base);
689 * Handle constraint nodes in each basic block.
690 * handle_constraints() inserts Perm nodes which perm
691 * over all values live at the constrained node right in front
692 * of the constrained node. These Perms signal a constrained node.
693 * For further comments, refer to handle_constraints().
695 static void constraints(ir_node *bl, void *data)
697 be_chordal_alloc_env_t *env = data;
700 Start silent in the start block.
701 The silence remains until the first barrier is seen.
702 Each other block is begun loud.
704 int silent = bl == get_irg_start_block(get_irn_irg(bl));
708 If the block is the start block search the barrier and
709 start handling constraints from there.
712 for(irn = sched_first(bl); !sched_is_end(irn);) {
713 irn = handle_constraints(env, irn, &silent);
718 * Annotate the register pressure to the nodes and compute
719 * the liveness intervals.
720 * @param block The block to do it for.
721 * @param env_ptr The environment.
723 static void pressure(ir_node *block, void *env_ptr)
725 /* Convenience macro for a def */
726 #define border_def(irn, step, real) \
727 border_add(env, head, irn, step, pressure--, 1, real)
729 /* Convenience macro for a use */
730 #define border_use(irn, step, real) \
731 border_add(env, head, irn, step, ++pressure, 0, real)
733 be_chordal_alloc_env_t *alloc_env = env_ptr;
734 be_chordal_env_t *env = alloc_env->chordal_env;
735 bitset_t *live = alloc_env->live;
737 be_lv_t *lv = env->birg->lv;
741 unsigned pressure = 0;
742 struct list_head *head;
743 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
744 pset *live_end = be_lv_pset_put_end(lv, block, pset_new_ptr_default());
746 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
747 bitset_clear_all(live);
749 /* Set up the border list in the block info */
750 head = obstack_alloc(env->obst, sizeof(*head));
751 INIT_LIST_HEAD(head);
752 assert(pmap_get(env->border_heads, block) == NULL);
753 pmap_insert(env->border_heads, block, head);
756 * Make final uses of all values live out of the block.
757 * They are necessary to build up real intervals.
759 foreach_pset(live_end, irn) {
760 if(has_reg_class(env, irn)) {
761 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
762 bitset_set(live, get_irn_idx(irn));
763 border_use(irn, step, 0);
769 * Determine the last uses of a value inside the block, since they are
770 * relevant for the interval borders.
772 sched_foreach_reverse(block, irn) {
773 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
774 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
777 * If the node defines some value, which can put into a
778 * register of the current class, make a border for it.
780 if(has_reg_class(env, irn)) {
781 int nr = get_irn_idx(irn);
783 bitset_clear(live, nr);
784 border_def(irn, step, 1);
788 * If the node is no phi node we can examine the uses.
791 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
792 ir_node *op = get_irn_n(irn, i);
794 if(has_reg_class(env, op)) {
795 int nr = get_irn_idx(op);
796 const char *msg = "-";
798 if(!bitset_is_set(live, nr)) {
799 border_use(op, step, 1);
800 bitset_set(live, nr);
804 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
812 * Add initial defs for all values live in.
814 foreach_pset(live_in, irn) {
815 if(has_reg_class(env, irn)) {
817 /* Mark the value live in. */
818 bitset_set(live, get_irn_idx(irn));
821 border_def(irn, step, 0);
829 static void assign(ir_node *block, void *env_ptr)
831 be_chordal_alloc_env_t *alloc_env = env_ptr;
832 be_chordal_env_t *env = alloc_env->chordal_env;
833 bitset_t *live = alloc_env->live;
834 bitset_t *colors = alloc_env->colors;
835 bitset_t *in_colors = alloc_env->in_colors;
836 const arch_env_t *arch_env = env->birg->main_env->arch_env;
837 struct list_head *head = get_block_border_head(env, block);
838 be_lv_t *lv = env->birg->lv;
839 pset *live_in = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
844 bitset_clear_all(colors);
845 bitset_clear_all(live);
846 bitset_clear_all(in_colors);
848 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
849 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
850 list_for_each_entry(border_t, b, head, list) {
851 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
852 b->irn, get_irn_idx(b->irn)));
856 * Add initial defs for all values live in.
857 * Since their colors have already been assigned (The dominators were
858 * allocated before), we have to mark their colors as used also.
860 foreach_pset(live_in, irn) {
861 if(has_reg_class(env, irn)) {
862 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
865 assert(reg && "Node must have been assigned a register");
866 col = arch_register_get_index(reg);
868 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
870 /* Mark the color of the live in value as used. */
871 bitset_set(colors, col);
872 bitset_set(in_colors, col);
874 /* Mark the value live in. */
875 bitset_set(live, get_irn_idx(irn));
880 * Mind that the sequence of defs from back to front defines a perfect
881 * elimination order. So, coloring the definitions from first to last
884 list_for_each_entry_reverse(border_t, b, head, list) {
885 ir_node *irn = b->irn;
886 int nr = get_irn_idx(irn);
887 int ignore = arch_irn_is(arch_env, irn, ignore);
890 * Assign a color, if it is a local def. Global defs already have a
893 if(b->is_def && !be_is_live_in(lv, block, irn)) {
894 const arch_register_t *reg;
897 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
898 reg = arch_get_irn_register(arch_env, irn);
900 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
902 col = get_next_free_reg(alloc_env, colors);
903 reg = arch_register_for_index(env->cls, col);
904 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
905 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
908 bitset_set(colors, col);
909 arch_set_irn_register(arch_env, irn, reg);
911 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
913 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
914 bitset_set(live, nr);
917 /* Clear the color upon a use. */
918 else if(!b->is_def) {
919 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
922 assert(reg && "Register must have been assigned");
924 col = arch_register_get_index(reg);
926 if(!arch_register_type_is(reg, ignore)) {
927 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
931 bitset_clear(colors, col);
932 bitset_clear(live, nr);
942 static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom)
944 be_chordal_env_t *env = alloc_env->chordal_env;
945 bitset_t *colors = alloc_env->colors;
946 bitset_t *in_colors = alloc_env->in_colors;
947 bitset_t *live = bitset_irg_malloc(env->irg);
948 const arch_env_t *arch_env = env->birg->main_env->arch_env;
949 be_irg_t *birg = env->birg;
950 lv_chk_t *lv = be_get_birg_liveness_chk(birg);
955 bitset_clear_all(colors);
956 bitset_clear_all(in_colors);
959 * All variables which are live in to this block are live out
960 * of the immediate dominator thanks to SSA properties. As we
961 * have already visited the immediate dominator, we know these
962 * variables. The only tjing left is to check wheather they are live
963 * in here (they also could be phi arguments to some ohi not
964 * in this block, hence we have to check).
966 bitset_foreach (live_end_dom, elm) {
967 ir_node *irn = get_idx_irn(env->irg, elm);
968 if (lv_chk_bl_in(lv, block, irn)) {
969 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
972 assert(be_is_live_in(env->birg->lv, block, irn));
973 assert(reg && "Node must have been assigned a register");
974 col = arch_register_get_index(reg);
976 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
978 /* Mark the color of the live in value as used. */
979 bitset_set(colors, col);
980 bitset_set(in_colors, col);
982 /* Mark the value live in. */
983 bitset_set(live, elm);
987 assert(!be_is_live_in(env->birg->lv, block, irn));
992 * Mind that the sequence of defs from back to front defines a perfect
993 * elimination order. So, coloring the definitions from first to last
996 sched_foreach (block, irn) {
997 int nr = get_irn_idx(irn);
998 int ignore = arch_irn_is(arch_env, irn, ignore);
1000 /* Clear the color upon a last use. */
1003 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1004 ir_node *op = get_irn_n(irn, i);
1007 * If the reg class matches and the operand is not live after
1008 * the node, irn is a last use of op and the register can
1011 if (has_reg_class(env, op)) {
1012 if (!be_lv_chk_after_irn(birg, op, irn)) {
1013 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
1016 assert(reg && "Register must have been assigned");
1017 col = arch_register_get_index(reg);
1018 bitset_clear(colors, col);
1019 bitset_clear(live, nr);
1025 if (has_reg_class(env, irn)) {
1026 const arch_register_t *reg;
1030 * Assign a color, if it is a local def. Global defs already have a
1033 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
1034 reg = arch_get_irn_register(arch_env, irn);
1036 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
1038 col = get_next_free_reg(alloc_env, colors);
1039 reg = arch_register_for_index(env->cls, col);
1040 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
1041 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
1044 bitset_set(colors, col);
1045 arch_set_irn_register(arch_env, irn, reg);
1047 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
1049 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
1050 bitset_set(live, nr);
1055 dominates_for_each (block, irn) {
1056 assign_new(irn, alloc_env, live);
1062 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
1064 be_chordal_alloc_env_t env;
1066 be_irg_t *birg = chordal_env->birg;
1067 const arch_register_class_t *cls = chordal_env->cls;
1069 int colors_n = arch_register_class_n_regs(cls);
1070 ir_graph *irg = chordal_env->irg;
1071 int allocatable_regs = colors_n - be_put_ignore_regs(birg, cls, NULL);
1073 /* some special classes contain only ignore regs, no work to be done */
1074 if(allocatable_regs == 0)
1077 be_assure_dom_front(birg);
1078 be_assure_liveness(birg);
1081 env.chordal_env = chordal_env;
1082 env.colors_n = colors_n;
1083 env.colors = bitset_alloca(colors_n);
1084 env.tmp_colors = bitset_alloca(colors_n);
1085 env.in_colors = bitset_alloca(colors_n);
1086 env.pre_colored = pset_new_ptr_default();
1088 /* Handle register targeting constraints */
1089 dom_tree_walk_irg(irg, constraints, NULL, &env);
1091 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1092 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1093 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1096 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1098 /* First, determine the pressure */
1099 dom_tree_walk_irg(irg, pressure, NULL, &env);
1101 /* Assign the colors */
1102 #ifdef NEW_STYLE_ASSIGN
1103 assign_new(get_irg_start_block(irg), &env, env.live);
1105 dom_tree_walk_irg(irg, assign, NULL, &env);
1108 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1110 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1111 plotter = new_plotter_ps(buf);
1112 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1113 plotter_free(plotter);
1116 bitset_free(env.live);
1117 del_pset(env.pre_colored);
1120 void be_init_chordal(void)
1122 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1125 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);