2 * Chordal register allocation.
3 * @author Sebastian Hack
7 * Copyright (C) Universitaet Karlsruhe
8 * Released under the GPL
30 #include "bipartite.h"
33 #include "irgraph_t.h"
34 #include "irprintf_t.h"
45 #include "besched_t.h"
53 #include "bechordal_t.h"
54 #include "bechordal_draw.h"
56 #define DBG_LEVEL SET_LEVEL_0
57 #define DBG_LEVEL_CHECK SET_LEVEL_0
61 #define DUMP_INTERVALS
63 typedef struct _be_chordal_alloc_env_t {
64 be_chordal_env_t *chordal_env;
66 pset *pre_colored; /**< Set of precolored nodes. */
67 bitset_t *live; /**< A liveness bitset. */
68 bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
69 bitset_t *colors; /**< The color mask. */
70 bitset_t *in_colors; /**< Colors used by live in values. */
71 int colors_n; /**< The number of colors. */
72 DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
73 } be_chordal_alloc_env_t;
77 /* Make a fourcc for border checking. */
78 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
81 static void check_border_list(struct list_head *head)
84 list_for_each_entry(border_t, x, head, list) {
85 assert(x->magic == BORDER_FOURCC);
89 static void check_heads(be_chordal_env_t *env)
92 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
93 /* ir_printf("checking border list of block %+F\n", ent->key); */
94 check_border_list(ent->value);
100 * Add an interval border to the list of a block's list
101 * of interval border.
102 * @note You always have to create the use before the def.
103 * @param env The environment.
104 * @param head The list head to enqueue the borders.
105 * @param irn The node (value) the border belongs to.
106 * @param pressure The pressure at this point in time.
107 * @param step A time step for the border.
108 * @param is_def Is the border a use or a def.
109 * @return The created border.
111 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
112 ir_node *irn, unsigned step, unsigned pressure,
113 unsigned is_def, unsigned is_real)
120 b = obstack_alloc(&env->obst, sizeof(*b));
122 /* also allocate the def and tie it to the use. */
123 def = obstack_alloc(&env->obst, sizeof(*def));
124 memset(def, 0, sizeof(*def));
129 * Set the link field of the irn to the def.
130 * This strongly relies on the fact, that the use is always
131 * made before the def.
133 set_irn_link(irn, def);
135 b->magic = BORDER_FOURCC;
136 def->magic = BORDER_FOURCC;
140 * If the def is encountered, the use was made and so was the
141 * the def node (see the code above). It was placed into the
142 * link field of the irn, so we can get it there.
145 b = get_irn_link(irn);
147 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
150 b->pressure = pressure;
152 b->is_real = is_real;
155 list_add_tail(&b->list, head);
156 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
163 * Check, if an irn is of the register class currently under processing.
164 * @param env The chordal environment.
165 * @param irn The node.
166 * @return 1, if the node is of that register class, 0 if not.
168 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
170 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
171 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
174 #define has_limited_constr(req, irn) \
175 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
177 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
179 bitset_t *tmp = alloc_env->tmp_colors;
180 bitset_copy(tmp, colors);
181 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
182 return bitset_next_clear(tmp, 0);
185 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
190 bitset_copy(bs, o2->regs);
195 bitset_copy(bs, o1->regs);
199 assert(o1->req.cls == o2->req.cls);
201 if(bitset_contains(o1->regs, o2->regs))
202 bitset_copy(bs, o1->regs);
203 else if(bitset_contains(o2->regs, o1->regs))
204 bitset_copy(bs, o2->regs);
211 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
215 ie.ignore_colors = env->ignore_colors;
216 ie.aenv = env->birg->main_env->arch_env;
217 ie.obst = &env->obst;
219 return be_scan_insn(&ie, irn);
222 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
224 be_insn_t *insn = chordal_scan_insn(env, irn);
225 bitset_t *def_constr = bitset_alloca(env->cls->n_regs);
226 bitset_t *tmp = bitset_alloca(env->cls->n_regs);
229 if(!insn->has_constraints)
232 /* collect all registers occuring in out constraints. */
233 for(i = 0; i < insn->use_start; ++i) {
234 be_operand_t *op = &insn->ops[i];
235 if(op->has_constraints)
236 bitset_or(def_constr, op->regs);
240 insert copies for all constrained arguments living through the node
241 and being constrained to a register which also occurs in out constraints.
243 for(i = insn->use_start; i < insn->n_ops; ++i) {
244 be_operand_t *op = &insn->ops[i];
246 bitset_copy(tmp, op->regs);
247 bitset_and(tmp, def_constr);
251 1) the operand is constrained.
252 2) lives through the node.
253 3) is constrained to a register occuring in out constraints.
255 if(op->has_constraints && values_interfere(env->lv, insn->irn, op->carrier) && bitset_popcnt(tmp) > 0) {
256 ir_node *bl = get_nodes_block(insn->irn);
259 only create the copy if the operand is no copy.
260 this is necessary since the assure constraints phase inserts
261 Copies and Keeps for operands which must be different from the results.
262 Additional copies here would destroy this.
264 if(!be_is_Copy(op->carrier)) {
265 ir_node *copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
267 sched_add_before(insn->irn, copy);
268 set_irn_n(insn->irn, op->pos, copy);
269 DBG((env->dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
270 be_liveness_update(env->lv, op->carrier);
276 obstack_free(&env->obst, insn);
277 return insn->next_insn;
280 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
282 be_chordal_env_t *env = data;
284 for(irn = sched_first(bl); !sched_is_end(irn);) {
285 irn = prepare_constr_insn(env, irn);
289 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv) {
290 irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, (void *) cenv);
293 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
295 const be_chordal_env_t *env = alloc_env->chordal_env;
297 int n_uses = be_insn_n_uses(insn);
298 int n_defs = be_insn_n_defs(insn);
299 bitset_t *bs = bitset_alloca(env->cls->n_regs);
300 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
305 For each out operand, try to find an in operand which can be assigned the
306 same register as the out operand.
308 for (j = 0; j < insn->use_start; ++j) {
310 int smallest_n_regs = 2 * env->cls->n_regs + 1;
311 be_operand_t *out_op = &insn->ops[j];
313 /* Try to find an in operand which has ... */
314 for(i = insn->use_start; i < insn->n_ops; ++i) {
316 const be_operand_t *op = &insn->ops[i];
318 if (! values_interfere(env->lv, op->irn, op->carrier) && ! op->partner) {
319 bitset_clear_all(bs);
320 bitset_copy(bs, op->regs);
321 bitset_and(bs, out_op->regs);
322 n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
324 if (bitset_popcnt(bs) > 0 && n_total < smallest_n_regs) {
326 smallest_n_regs = n_total;
332 be_operand_t *partner = &insn->ops[smallest];
333 out_op->partner = partner;
334 partner->partner = out_op;
340 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
342 be_chordal_env_t *env = alloc_env->chordal_env;
343 const arch_env_t *aenv = env->birg->main_env->arch_env;
344 be_insn_t *insn = *the_insn;
345 ir_node *bl = get_nodes_block(insn->irn);
346 ir_node *copy = NULL;
347 ir_node *perm = NULL;
348 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
349 bitset_t *bs = bitset_alloca(env->cls->n_regs);
350 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
354 assert(insn->has_constraints && "only do this for constrained nodes");
357 Collect all registers that occur in output constraints.
358 This is necessary, since if the insn has one of these as an input constraint
359 and the corresponding operand interferes with the insn, the operand must
362 for(i = 0; i < insn->use_start; ++i) {
363 be_operand_t *op = &insn->ops[i];
364 if(op->has_constraints)
365 bitset_or(out_constr, op->regs);
369 Now, figure out which input operand must be copied since it has input
370 constraints which are also output constraints.
377 for(i = insn->use_start; i < insn->n_ops; ++i) {
378 be_operand_t *op = &insn->ops[i];
379 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
380 bitset_copy(bs, op->regs);
381 bitset_and(bs, out_constr);
384 The operand (interfering with the node) has input constraints
385 which also occur as output constraints, so insert a copy.
387 if(bitset_popcnt(bs) > 0) {
388 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
390 sched_add_before(insn->irn, copy);
391 set_irn_n(insn->irn, op->pos, op->carrier);
393 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
400 Make the Perm, recompute liveness and re-scan the insn since the
401 in operands are now the Projs of the Perm.
403 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
405 /* Registers are propagated by insert_Perm_after(). Clean them here! */
407 const ir_edge_t *edge;
409 foreach_out_edge(perm, edge) {
410 ir_node *proj = get_edge_src_irn(edge);
411 arch_set_irn_register(aenv, proj, NULL);
415 We also have to re-build the insn since the input operands are now the Projs of
416 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
417 the live sets may change.
419 // be_liveness_recompute(env->lv);
420 obstack_free(&env->obst, insn);
421 *the_insn = insn = chordal_scan_insn(env, insn->irn);
424 Copy the input constraints of the insn to the Perm as output
425 constraints. Succeeding phases (coalescing will need that).
427 for(i = insn->use_start; i < insn->n_ops; ++i) {
428 be_operand_t *op = &insn->ops[i];
429 ir_node *proj = op->carrier;
431 Note that the predecessor must not be a Proj of the Perm,
432 since ignore-nodes are not Perm'ed.
434 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
435 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
443 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
445 be_chordal_env_t *env = alloc_env->chordal_env;
446 void *base = obstack_base(&env->obst);
447 be_insn_t *insn = chordal_scan_insn(env, irn);
448 ir_node *res = insn->next_insn;
449 int be_silent = *silent;
451 if(insn->pre_colored) {
453 for(i = 0; i < insn->use_start; ++i)
454 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
458 If the current node is a barrier toggle the silent flag.
459 If we are in the start block, we are ought to be silent at the beginning,
460 so the toggling activates the constraint handling but skips the barrier.
461 If we are in the end block we handle the in requirements of the barrier
462 and set the rest to silent.
464 if(be_is_Barrier(irn))
471 Perms inserted before the constraint handling phase are considered to be
472 correctly precolored. These Perms arise during the ABI handling phase.
474 if(insn->has_constraints) {
475 const arch_env_t *aenv = env->birg->main_env->arch_env;
476 int n_regs = env->cls->n_regs;
477 bitset_t *bs = bitset_alloca(n_regs);
478 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
479 bipartite_t *bp = bipartite_new(n_regs, n_regs);
480 int *assignment = alloca(n_regs * sizeof(assignment[0]));
481 pmap *partners = pmap_create();
482 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
486 const ir_edge_t *edge;
487 ir_node *perm = NULL;
490 prepare the constraint handling of this node.
491 Perms are constructed and Copies are created for constrained values
492 interfering with the instruction.
494 perm = pre_process_constraints(alloc_env, &insn);
496 /* find suitable in operands to the out operands of the node. */
497 pair_up_operands(alloc_env, insn);
500 look at the in/out operands and add each operand (and its possible partner)
501 to a bipartite graph (left: nodes with partners, right: admissible colors).
503 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
504 be_operand_t *op = &insn->ops[i];
507 If the operand has no partner or the partner has not been marked
508 for allocation, determine the admissible registers and mark it
509 for allocation by associating the node and its partner with the
510 set of admissible registers via a bipartite graph.
512 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
514 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
515 alloc_nodes[n_alloc] = op->carrier;
517 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
519 bitset_clear_all(bs);
520 get_decisive_partner_regs(bs, op, op->partner);
522 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
524 bitset_foreach(bs, col)
525 bipartite_add(bp, n_alloc, col);
532 Put all nodes which live by the constrained instruction also to the
533 allocation bipartite graph. They are considered unconstrained.
536 foreach_out_edge(perm, edge) {
537 ir_node *proj = get_edge_src_irn(edge);
539 assert(is_Proj(proj));
541 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
542 assert(n_alloc < n_regs);
543 alloc_nodes[n_alloc] = proj;
544 pmap_insert(partners, proj, NULL);
546 bitset_clear_all(bs);
547 arch_put_non_ignore_regs(aenv, env->cls, bs);
548 bitset_foreach(bs, col)
549 bipartite_add(bp, n_alloc, col);
556 /* Compute a valid register allocation. */
557 bipartite_matching(bp, assignment);
559 /* Assign colors obtained from the matching. */
560 for(i = 0; i < n_alloc; ++i) {
561 const arch_register_t *reg;
565 assert(assignment[i] >= 0 && "there must have been a register assigned");
566 reg = arch_register_for_index(env->cls, assignment[i]);
568 nodes[0] = alloc_nodes[i];
569 nodes[1] = pmap_get(partners, alloc_nodes[i]);
571 for(j = 0; j < 2; ++j) {
575 arch_set_irn_register(aenv, nodes[j], reg);
576 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
577 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
582 /* Allocate the non-constrained Projs of the Perm. */
585 bitset_clear_all(bs);
587 /* Put the colors of all Projs in a bitset. */
588 foreach_out_edge(perm, edge) {
589 ir_node *proj = get_edge_src_irn(edge);
590 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
593 bitset_set(bs, reg->index);
596 /* Assign the not yet assigned Projs of the Perm a suitable color. */
597 foreach_out_edge(perm, edge) {
598 ir_node *proj = get_edge_src_irn(edge);
599 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
601 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
604 col = get_next_free_reg(alloc_env, bs);
605 reg = arch_register_for_index(env->cls, col);
606 bitset_set(bs, reg->index);
607 arch_set_irn_register(aenv, proj, reg);
608 pset_insert_ptr(alloc_env->pre_colored, proj);
609 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
615 pmap_destroy(partners);
619 obstack_free(&env->obst, base);
624 * Handle constraint nodes in each basic block.
625 * handle_constraints() inserts Perm nodes which perm
626 * over all values live at the constrained node right in front
627 * of the constrained node. These Perms signal a constrained node.
628 * For further comments, refer to handle_constraints().
630 static void constraints(ir_node *bl, void *data)
632 be_chordal_alloc_env_t *env = data;
635 Start silent in the start block.
636 The silence remains until the first barrier is seen.
637 Each other block is begun loud.
639 int silent = bl == get_irg_start_block(get_irn_irg(bl));
643 If the block is the start block search the barrier and
644 start handling constraints from there.
647 for(irn = sched_first(bl); !sched_is_end(irn);) {
648 irn = handle_constraints(env, irn, &silent);
653 * Annotate the register pressure to the nodes and compute
654 * the liveness intervals.
655 * @param block The block to do it for.
656 * @param env_ptr The environment.
658 static void pressure(ir_node *block, void *env_ptr)
660 /* Convenience macro for a def */
661 #define border_def(irn, step, real) \
662 border_add(env, head, irn, step, pressure--, 1, real)
664 /* Convenience macro for a use */
665 #define border_use(irn, step, real) \
666 border_add(env, head, irn, step, ++pressure, 0, real)
668 be_chordal_alloc_env_t *alloc_env = env_ptr;
669 be_chordal_env_t *env = alloc_env->chordal_env;
670 bitset_t *live = alloc_env->live;
672 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
676 unsigned pressure = 0;
677 struct list_head *head;
678 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
679 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
681 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
682 bitset_clear_all(live);
684 /* Set up the border list in the block info */
685 head = obstack_alloc(&env->obst, sizeof(*head));
686 INIT_LIST_HEAD(head);
687 assert(pmap_get(env->border_heads, block) == NULL);
688 pmap_insert(env->border_heads, block, head);
691 * Make final uses of all values live out of the block.
692 * They are necessary to build up real intervals.
694 foreach_pset(live_end, irn) {
695 if(has_reg_class(env, irn)) {
696 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
697 bitset_set(live, get_irn_idx(irn));
698 border_use(irn, step, 0);
704 * Determine the last uses of a value inside the block, since they are
705 * relevant for the interval borders.
707 sched_foreach_reverse(block, irn) {
708 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
709 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
712 * If the node defines some value, which can put into a
713 * register of the current class, make a border for it.
715 if(has_reg_class(env, irn)) {
716 int nr = get_irn_idx(irn);
718 bitset_clear(live, nr);
719 border_def(irn, step, 1);
723 * If the node is no phi node we can examine the uses.
726 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
727 ir_node *op = get_irn_n(irn, i);
729 if(has_reg_class(env, op)) {
730 int nr = get_irn_idx(op);
731 const char *msg = "-";
733 if(!bitset_is_set(live, nr)) {
734 border_use(op, step, 1);
735 bitset_set(live, nr);
739 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
747 * Add initial defs for all values live in.
749 foreach_pset(live_in, irn) {
750 if(has_reg_class(env, irn)) {
752 /* Mark the value live in. */
753 bitset_set(live, get_irn_idx(irn));
756 border_def(irn, step, 0);
764 static void assign(ir_node *block, void *env_ptr)
766 be_chordal_alloc_env_t *alloc_env = env_ptr;
767 be_chordal_env_t *env = alloc_env->chordal_env;
768 bitset_t *live = alloc_env->live;
769 bitset_t *colors = alloc_env->colors;
770 bitset_t *in_colors = alloc_env->in_colors;
771 const arch_env_t *arch_env = env->birg->main_env->arch_env;
772 struct list_head *head = get_block_border_head(env, block);
773 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
777 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
779 bitset_clear_all(colors);
780 bitset_clear_all(live);
781 bitset_clear_all(in_colors);
783 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
784 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
785 list_for_each_entry(border_t, b, head, list) {
786 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
787 b->irn, get_irn_idx(b->irn)));
791 * Add initial defs for all values live in.
792 * Since their colors have already been assigned (The dominators were
793 * allocated before), we have to mark their colors as used also.
795 foreach_pset(live_in, irn) {
796 if(has_reg_class(env, irn)) {
797 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
800 assert(reg && "Node must have been assigned a register");
801 col = arch_register_get_index(reg);
803 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
805 /* Mark the color of the live in value as used. */
806 bitset_set(colors, col);
807 bitset_set(in_colors, col);
809 /* Mark the value live in. */
810 bitset_set(live, get_irn_idx(irn));
815 * Mind that the sequence
816 * of defs from back to front defines a perfect
817 * elimination order. So, coloring the definitions from first to last
820 list_for_each_entry_reverse(border_t, b, head, list) {
821 ir_node *irn = b->irn;
822 int nr = get_irn_idx(irn);
823 int ignore = arch_irn_is(arch_env, irn, ignore);
826 * Assign a color, if it is a local def. Global defs already have a
829 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
830 const arch_register_t *reg;
833 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
834 reg = arch_get_irn_register(arch_env, irn);
836 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
840 col = get_next_free_reg(alloc_env, colors);
841 reg = arch_register_for_index(env->cls, col);
842 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
843 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
846 bitset_set(colors, col);
847 arch_set_irn_register(arch_env, irn, reg);
849 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
851 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
852 bitset_set(live, nr);
855 /* Clear the color upon a use. */
856 else if(!b->is_def) {
857 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
860 assert(reg && "Register must have been assigned");
862 col = arch_register_get_index(reg);
863 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
865 bitset_clear(colors, col);
866 bitset_clear(live, nr);
873 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
875 be_chordal_alloc_env_t env;
878 int colors_n = arch_register_class_n_regs(chordal_env->cls);
879 ir_graph *irg = chordal_env->irg;
884 env.chordal_env = chordal_env;
885 env.colors_n = colors_n;
886 env.colors = bitset_alloca(colors_n);
887 env.tmp_colors = bitset_alloca(colors_n);
888 env.in_colors = bitset_alloca(colors_n);
889 env.pre_colored = pset_new_ptr_default();
890 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
893 /* Handle register targeting constraints */
894 dom_tree_walk_irg(irg, constraints, NULL, &env);
896 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
897 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
898 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
902 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
904 /* First, determine the pressure */
905 dom_tree_walk_irg(irg, pressure, NULL, &env);
907 /* Assign the colors */
908 dom_tree_walk_irg(irg, assign, NULL, &env);
910 be_numbering_done(irg);
912 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
914 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
915 plotter = new_plotter_ps(buf);
916 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
917 plotter_free(plotter);
920 bitset_free(env.live);
921 del_pset(env.pre_colored);