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
37 #include "raw_bitset.h"
39 #include "bipartite.h"
40 #include "hungarian.h"
43 #include "irgraph_t.h"
44 #include "irprintf_t.h"
55 #include "besched_t.h"
62 #include "bestatevent.h"
64 #include "beintlive_t.h"
66 #include "bechordal_t.h"
67 #include "bechordal_draw.h"
70 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
74 #define DUMP_INTERVALS
76 typedef struct _be_chordal_alloc_env_t {
77 be_chordal_env_t *chordal_env;
79 pset *pre_colored; /**< Set of precolored nodes. */
80 bitset_t *live; /**< A liveness bitset. */
81 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
82 bitset_t *colors; /**< The color mask. */
83 bitset_t *in_colors; /**< Colors used by live in values. */
84 int colors_n; /**< The number of colors. */
85 } be_chordal_alloc_env_t;
89 /* Make a fourcc for border checking. */
90 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
93 static void check_border_list(struct list_head *head)
96 list_for_each_entry(border_t, x, head, list) {
97 assert(x->magic == BORDER_FOURCC);
101 static void check_heads(be_chordal_env_t *env)
104 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
105 /* ir_printf("checking border list of block %+F\n", ent->key); */
106 check_border_list(ent->value);
112 * Add an interval border to the list of a block's list
113 * of interval border.
114 * @note You always have to create the use before the def.
115 * @param env The environment.
116 * @param head The list head to enqueue the borders.
117 * @param irn The node (value) the border belongs to.
118 * @param pressure The pressure at this point in time.
119 * @param step A time step for the border.
120 * @param is_def Is the border a use or a def.
121 * @return The created border.
123 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
124 ir_node *irn, unsigned step, unsigned pressure,
125 unsigned is_def, unsigned is_real)
132 b = obstack_alloc(env->obst, sizeof(*b));
134 /* also allocate the def and tie it to the use. */
135 def = obstack_alloc(env->obst, sizeof(*def));
136 memset(def, 0, sizeof(*def));
141 * Set the link field of the irn to the def.
142 * This strongly relies on the fact, that the use is always
143 * made before the def.
145 set_irn_link(irn, def);
147 DEBUG_ONLY(b->magic = BORDER_FOURCC);
148 DEBUG_ONLY(def->magic = BORDER_FOURCC);
152 * If the def is encountered, the use was made and so was the
153 * the def node (see the code above). It was placed into the
154 * link field of the irn, so we can get it there.
157 b = get_irn_link(irn);
159 DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"));
162 b->pressure = pressure;
164 b->is_real = is_real;
167 list_add_tail(&b->list, head);
168 DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
175 * Check, if an irn is of the register class currently under processing.
176 * @param env The chordal environment.
177 * @param irn The node.
178 * @return 1, if the node is of that register class, 0 if not.
180 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
182 return arch_irn_consider_in_reg_alloc(env->cls, irn);
185 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
187 bitset_t *tmp = alloc_env->tmp_colors;
188 bitset_copy(tmp, colors);
189 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
190 return bitset_next_clear(tmp, 0);
193 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
198 bitset_copy(bs, o2->regs);
203 bitset_copy(bs, o1->regs);
207 assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
209 if(bitset_contains(o1->regs, o2->regs))
210 bitset_copy(bs, o1->regs);
211 else if(bitset_contains(o2->regs, o1->regs))
212 bitset_copy(bs, o2->regs);
219 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
223 ie.ignore_colors = env->ignore_colors;
226 return be_scan_insn(&ie, irn);
229 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
231 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
232 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
233 ir_node *bl = get_nodes_block(irn);
234 const be_irg_t *birg = env->birg;
235 be_lv_t *lv = birg->lv;
240 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
241 ir_node *op = get_irn_n(irn, i);
243 const arch_register_t *reg;
244 const arch_register_req_t *req;
246 if (arch_get_irn_reg_class(irn, i) != env->cls)
249 reg = arch_get_irn_register(op);
251 if (reg == NULL || !arch_register_type_is(reg, ignore))
253 if(arch_register_type_is(reg, joker))
256 req = arch_get_register_req(irn, i);
257 if (!arch_register_req_is(req, limited))
260 if (rbitset_is_set(req->limited, reg->index))
263 copy = be_new_Copy(env->cls, env->irg, bl, op);
264 be_stat_ev("constr_copy", 1);
266 sched_add_before(irn, copy);
267 set_irn_n(irn, i, copy);
268 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
271 insn = chordal_scan_insn(env, irn);
273 if(!insn->has_constraints)
276 /* insert copies for nodes that occur constrained more than once. */
277 for(i = insn->use_start; i < insn->n_ops; ++i) {
278 be_operand_t *op = &insn->ops[i];
280 if(!op->has_constraints)
283 for(j = i + 1; j < insn->n_ops; ++j) {
285 be_operand_t *a_op = &insn->ops[j];
287 if(a_op->carrier != op->carrier || !a_op->has_constraints)
290 /* if the constraint is the same, no copy is necessary
291 * TODO generalise unequal but overlapping constraints */
292 if (a_op->req == op->req)
295 if (be_is_Copy(get_irn_n(insn->irn, a_op->pos)))
298 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
299 be_stat_ev("constr_copy", 1);
301 sched_add_before(insn->irn, copy);
302 set_irn_n(insn->irn, a_op->pos, copy);
303 DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
307 /* collect all registers occurring in out constraints. */
308 for(i = 0; i < insn->use_start; ++i) {
309 be_operand_t *op = &insn->ops[i];
310 if(op->has_constraints)
311 bitset_or(def_constr, op->regs);
315 insert copies for all constrained arguments living through the node
316 and being constrained to a register which also occurs in out constraints.
318 for(i = insn->use_start; i < insn->n_ops; ++i) {
320 be_operand_t *op = &insn->ops[i];
322 bitset_copy(tmp, op->regs);
323 bitset_and(tmp, def_constr);
327 1) the operand is constrained.
328 2) lives through the node.
329 3) is constrained to a register occurring in out constraints.
331 if(!op->has_constraints ||
332 !values_interfere(birg, insn->irn, op->carrier) ||
333 bitset_popcnt(tmp) == 0)
337 only create the copy if the operand is no copy.
338 this is necessary since the assure constraints phase inserts
339 Copies and Keeps for operands which must be different from the
340 results. Additional copies here would destroy this.
342 if (be_is_Copy(get_irn_n(insn->irn, op->pos)))
345 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
347 sched_add_before(insn->irn, copy);
348 set_irn_n(insn->irn, op->pos, copy);
349 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
350 be_liveness_update(lv, op->carrier);
354 obstack_free(env->obst, insn);
355 return insn->next_insn;
358 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
360 be_chordal_env_t *env = data;
362 for(irn = sched_first(bl); !sched_is_end(irn);) {
363 irn = prepare_constr_insn(env, irn);
367 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
368 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
371 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
373 const be_chordal_env_t *env = alloc_env->chordal_env;
375 int n_uses = be_insn_n_uses(insn);
376 int n_defs = be_insn_n_defs(insn);
377 bitset_t *bs = bitset_alloca(env->cls->n_regs);
378 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
383 For each out operand, try to find an in operand which can be assigned the
384 same register as the out operand.
386 for (j = 0; j < insn->use_start; ++j) {
388 int smallest_n_regs = 2 * env->cls->n_regs + 1;
389 be_operand_t *out_op = &insn->ops[j];
391 /* Try to find an in operand which has ... */
392 for(i = insn->use_start; i < insn->n_ops; ++i) {
394 const be_operand_t *op = &insn->ops[i];
396 if (op->partner != NULL)
398 if (values_interfere(env->birg, op->irn, op->carrier))
401 bitset_clear_all(bs);
402 bitset_copy(bs, op->regs);
403 bitset_and(bs, out_op->regs);
404 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
406 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
408 smallest_n_regs = n_total;
413 be_operand_t *partner = &insn->ops[smallest];
414 for(i = insn->use_start; i < insn->n_ops; ++i) {
415 if(insn->ops[i].carrier == partner->carrier)
416 insn->ops[i].partner = out_op;
419 out_op->partner = partner;
420 partner->partner = out_op;
426 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
427 be_insn_t **the_insn)
429 be_chordal_env_t *env = alloc_env->chordal_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(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 obstack_free(env->obst, insn);
472 *the_insn = insn = chordal_scan_insn(env, insn->irn);
475 Copy the input constraints of the insn to the Perm as output
476 constraints. Succeeding phases (coalescing) will need that.
478 for(i = insn->use_start; i < insn->n_ops; ++i) {
479 be_operand_t *op = &insn->ops[i];
480 ir_node *proj = op->carrier;
482 Note that the predecessor must not be a Proj of the Perm,
483 since ignore-nodes are not Perm'ed.
485 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
486 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
493 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
494 ir_node *irn, int *silent)
498 ir_node **alloc_nodes;
499 //hungarian_problem_t *bp;
504 const ir_edge_t *edge;
505 ir_node *perm = NULL;
506 //int match_res, cost;
507 be_chordal_env_t *env = alloc_env->chordal_env;
508 void *base = obstack_base(env->obst);
509 be_insn_t *insn = chordal_scan_insn(env, irn);
510 ir_node *res = insn->next_insn;
511 int be_silent = *silent;
512 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 n_regs = env->cls->n_regs;
542 bs = bitset_alloca(n_regs);
543 alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
544 //bp = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
545 bp = bipartite_new(n_regs, n_regs);
546 assignment = alloca(n_regs * sizeof(assignment[0]));
547 partners = pmap_create();
550 prepare the constraint handling of this node.
551 Perms are constructed and Copies are created for constrained values
552 interfering with the instruction.
554 perm = pre_process_constraints(alloc_env, &insn);
556 /* find suitable in operands to the out operands of the node. */
557 pair_up_operands(alloc_env, insn);
560 look at the in/out operands and add each operand (and its possible partner)
561 to a bipartite graph (left: nodes with partners, right: admissible colors).
563 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
564 be_operand_t *op = &insn->ops[i];
567 If the operand has no partner or the partner has not been marked
568 for allocation, determine the admissible registers and mark it
569 for allocation by associating the node and its partner with the
570 set of admissible registers via a bipartite graph.
572 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
573 ir_node *partner = op->partner ? op->partner->carrier : NULL;
576 pmap_insert(partners, op->carrier, partner);
578 pmap_insert(partners, partner, op->carrier);
580 /* don't insert a node twice */
581 for(i = 0; i < n_alloc; ++i) {
582 if(alloc_nodes[i] == op->carrier) {
589 alloc_nodes[n_alloc] = op->carrier;
591 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
594 bitset_clear_all(bs);
595 get_decisive_partner_regs(bs, op, op->partner);
597 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
600 bitset_foreach(bs, col) {
601 //hungarian_add(bp, n_alloc, col, 1);
602 bipartite_add(bp, n_alloc, col);
610 Put all nodes which live through the constrained instruction also to the
611 allocation bipartite graph. They are considered unconstrained.
614 foreach_out_edge(perm, edge) {
616 ir_node *proj = get_edge_src_irn(edge);
618 assert(is_Proj(proj));
620 if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
623 /* don't insert a node twice */
624 for(i = 0; i < n_alloc; ++i) {
625 if(alloc_nodes[i] == proj) {
633 assert(n_alloc < n_regs);
635 alloc_nodes[n_alloc] = proj;
636 pmap_insert(partners, proj, NULL);
638 bitset_clear_all(bs);
639 arch_put_non_ignore_regs(env->cls, bs);
640 bitset_andnot(bs, env->ignore_colors);
641 bitset_foreach(bs, col) {
642 //hungarian_add(bp, n_alloc, col, 1);
643 bipartite_add(bp, n_alloc, col);
650 /* Compute a valid register allocation. */
652 hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
653 match_res = hungarian_solve(bp, assignment, &cost, 1);
654 assert(match_res == 0 && "matching failed");
656 bipartite_matching(bp, assignment);
659 /* Assign colors obtained from the matching. */
660 for(i = 0; i < n_alloc; ++i) {
661 const arch_register_t *reg;
664 assert(assignment[i] >= 0 && "there must have been a register assigned");
665 reg = arch_register_for_index(env->cls, assignment[i]);
666 assert(! (reg->type & arch_register_type_ignore));
668 irn = alloc_nodes[i];
670 arch_set_irn_register(irn, reg);
671 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
672 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
675 irn = pmap_get(partners, alloc_nodes[i]);
677 arch_set_irn_register(irn, reg);
678 (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
679 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
683 /* Allocate the non-constrained Projs of the Perm. */
685 bitset_clear_all(bs);
687 /* Put the colors of all Projs in a bitset. */
688 foreach_out_edge(perm, edge) {
689 ir_node *proj = get_edge_src_irn(edge);
690 const arch_register_t *reg = arch_get_irn_register(proj);
693 bitset_set(bs, reg->index);
696 /* Assign the not yet assigned Projs of the Perm a suitable color. */
697 foreach_out_edge(perm, edge) {
698 ir_node *proj = get_edge_src_irn(edge);
699 const arch_register_t *reg = arch_get_irn_register(proj);
701 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
704 col = get_next_free_reg(alloc_env, bs);
705 reg = arch_register_for_index(env->cls, col);
706 bitset_set(bs, reg->index);
707 arch_set_irn_register(proj, reg);
708 pset_insert_ptr(alloc_env->pre_colored, proj);
709 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
715 //hungarian_free(bp);
716 pmap_destroy(partners);
719 obstack_free(env->obst, base);
724 * Handle constraint nodes in each basic block.
725 * handle_constraints() inserts Perm nodes which perm
726 * over all values live at the constrained node right in front
727 * of the constrained node. These Perms signal a constrained node.
728 * For further comments, refer to handle_constraints().
730 static void constraints(ir_node *bl, void *data)
732 be_chordal_alloc_env_t *env = data;
735 Start silent in the start block.
736 The silence remains until the first barrier is seen.
737 Each other block is begun loud.
739 int silent = bl == get_irg_start_block(get_irn_irg(bl));
743 If the block is the start block search the barrier and
744 start handling constraints from there.
747 for(irn = sched_first(bl); !sched_is_end(irn);) {
748 irn = handle_constraints(env, irn, &silent);
753 * Annotate the register pressure to the nodes and compute
754 * the liveness intervals.
755 * @param block The block to do it for.
756 * @param env_ptr The environment.
758 static void pressure(ir_node *block, void *env_ptr)
760 /* Convenience macro for a def */
761 #define border_def(irn, step, real) \
762 border_add(env, head, irn, step, pressure--, 1, real)
764 /* Convenience macro for a use */
765 #define border_use(irn, step, real) \
766 border_add(env, head, irn, step, ++pressure, 0, real)
768 be_chordal_alloc_env_t *alloc_env = env_ptr;
769 be_chordal_env_t *env = alloc_env->chordal_env;
770 bitset_t *live = alloc_env->live;
772 be_lv_t *lv = env->birg->lv;
777 unsigned pressure = 0;
778 struct list_head *head;
780 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
781 bitset_clear_all(live);
783 /* Set up the border list in the block info */
784 head = obstack_alloc(env->obst, sizeof(*head));
785 INIT_LIST_HEAD(head);
786 assert(pmap_get(env->border_heads, block) == NULL);
787 pmap_insert(env->border_heads, block, head);
790 * Make final uses of all values live out of the block.
791 * They are necessary to build up real intervals.
793 be_lv_foreach(lv, block, be_lv_state_end, i) {
794 ir_node *irn = be_lv_get_irn(lv, block, i);
795 if(has_reg_class(env, irn)) {
796 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
797 bitset_set(live, get_irn_idx(irn));
798 border_use(irn, step, 0);
804 * Determine the last uses of a value inside the block, since they are
805 * relevant for the interval borders.
807 sched_foreach_reverse(block, irn) {
808 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
809 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
811 if (get_irn_mode(irn) == mode_T) {
812 const ir_edge_t *edge;
814 foreach_out_edge(irn, edge) {
815 ir_node *proj = get_edge_src_irn(edge);
818 * If the node defines some value, which can put into a
819 * register of the current class, make a border for it.
821 if(has_reg_class(env, proj)) {
822 int nr = get_irn_idx(proj);
824 bitset_clear(live, nr);
825 border_def(proj, step, 1);
831 * If the node defines some value, which can put into a
832 * register of the current class, make a border for it.
834 if(has_reg_class(env, irn)) {
835 int nr = get_irn_idx(irn);
837 bitset_clear(live, nr);
838 border_def(irn, step, 1);
842 * If the node is no phi node we can examine the uses.
845 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
846 ir_node *op = get_irn_n(irn, i);
848 if(has_reg_class(env, op)) {
849 int nr = get_irn_idx(op);
850 const char *msg = "-";
852 if(!bitset_is_set(live, nr)) {
853 border_use(op, step, 1);
854 bitset_set(live, nr);
858 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
865 bitset_foreach(live, elm) {
866 ir_node *irn = get_idx_irn(env->irg, elm);
867 if (be_is_live_in(lv, block, irn))
868 border_def(irn, step, 0);
872 static void assign(ir_node *block, void *env_ptr)
874 be_chordal_alloc_env_t *alloc_env = env_ptr;
875 be_chordal_env_t *env = alloc_env->chordal_env;
876 bitset_t *live = alloc_env->live;
877 bitset_t *colors = alloc_env->colors;
878 bitset_t *in_colors = alloc_env->in_colors;
879 struct list_head *head = get_block_border_head(env, block);
880 be_lv_t *lv = env->birg->lv;
886 bitset_clear_all(colors);
887 bitset_clear_all(live);
888 bitset_clear_all(in_colors);
890 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
891 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
892 list_for_each_entry(border_t, b, head, list) {
893 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
894 b->irn, get_irn_idx(b->irn)));
898 * Add initial defs for all values live in.
899 * Since their colors have already been assigned (The dominators were
900 * allocated before), we have to mark their colors as used also.
902 be_lv_foreach(lv, block, be_lv_state_in, idx) {
903 irn = be_lv_get_irn(lv, block, idx);
904 if(has_reg_class(env, irn)) {
905 const arch_register_t *reg = arch_get_irn_register(irn);
908 assert(reg && "Node must have been assigned a register");
909 col = arch_register_get_index(reg);
911 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
913 /* Mark the color of the live in value as used. */
914 bitset_set(colors, col);
915 bitset_set(in_colors, col);
917 /* Mark the value live in. */
918 bitset_set(live, get_irn_idx(irn));
923 * Mind that the sequence of defs from back to front defines a perfect
924 * elimination order. So, coloring the definitions from first to last
927 list_for_each_entry_reverse(border_t, b, head, list) {
928 ir_node *irn = b->irn;
929 int nr = get_irn_idx(irn);
930 int ignore = arch_irn_is(irn, ignore);
933 * Assign a color, if it is a local def. Global defs already have a
936 if(b->is_def && !be_is_live_in(lv, block, irn)) {
937 const arch_register_t *reg;
940 if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
941 reg = arch_get_irn_register(irn);
943 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
945 col = get_next_free_reg(alloc_env, colors);
946 reg = arch_register_for_index(env->cls, col);
947 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
948 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
951 bitset_set(colors, col);
952 arch_set_irn_register(irn, reg);
954 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
956 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
957 bitset_set(live, nr);
960 /* Clear the color upon a use. */
961 else if(!b->is_def) {
962 const arch_register_t *reg = arch_get_irn_register(irn);
965 assert(reg && "Register must have been assigned");
967 col = arch_register_get_index(reg);
969 if(!arch_register_type_is(reg, ignore)) {
970 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
974 bitset_clear(colors, col);
975 bitset_clear(live, nr);
980 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
982 be_chordal_alloc_env_t env;
985 be_irg_t *birg = chordal_env->birg;
986 const arch_register_class_t *cls = chordal_env->cls;
988 int colors_n = arch_register_class_n_regs(cls);
989 ir_graph *irg = chordal_env->irg;
991 lv = be_assure_liveness(birg);
992 be_liveness_assure_sets(lv);
993 be_liveness_assure_chk(lv);
997 env.chordal_env = chordal_env;
998 env.colors_n = colors_n;
999 env.colors = bitset_alloca(colors_n);
1000 env.tmp_colors = bitset_alloca(colors_n);
1001 env.in_colors = bitset_alloca(colors_n);
1002 env.pre_colored = pset_new_ptr_default();
1004 BE_TIMER_PUSH(t_constr);
1006 /* Handle register targeting constraints */
1007 dom_tree_walk_irg(irg, constraints, NULL, &env);
1009 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1010 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1011 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1014 BE_TIMER_POP(t_constr);
1016 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1018 /* First, determine the pressure */
1019 dom_tree_walk_irg(irg, pressure, NULL, &env);
1021 /* Assign the colors */
1022 dom_tree_walk_irg(irg, assign, NULL, &env);
1024 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1026 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1027 plotter = new_plotter_ps(buf);
1028 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1029 plotter_free(plotter);
1032 bitset_free(env.live);
1033 del_pset(env.pre_colored);
1036 void be_init_chordal(void)
1038 FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1041 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);