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')
80 static void check_border_list(struct list_head *head)
83 list_for_each_entry(border_t, x, head, list) {
84 assert(x->magic == BORDER_FOURCC);
88 static void check_heads(be_chordal_env_t *env)
91 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
92 /* ir_printf("checking border list of block %+F\n", ent->key); */
93 check_border_list(ent->value);
99 * Add an interval border to the list of a block's list
100 * of interval border.
101 * @note You always have to create the use before the def.
102 * @param env The environment.
103 * @param head The list head to enqueue the borders.
104 * @param irn The node (value) the border belongs to.
105 * @param pressure The pressure at this point in time.
106 * @param step A time step for the border.
107 * @param is_def Is the border a use or a def.
108 * @return The created border.
110 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
111 ir_node *irn, unsigned step, unsigned pressure,
112 unsigned is_def, unsigned is_real)
119 b = obstack_alloc(&env->obst, sizeof(*b));
121 /* also allocate the def and tie it to the use. */
122 def = obstack_alloc(&env->obst, sizeof(*def));
123 memset(def, 0, sizeof(*def));
128 * Set the link field of the irn to the def.
129 * This strongly relies on the fact, that the use is always
130 * made before the def.
132 set_irn_link(irn, def);
134 b->magic = BORDER_FOURCC;
135 def->magic = BORDER_FOURCC;
139 * If the def is encountered, the use was made and so was the
140 * the def node (see the code above). It was placed into the
141 * link field of the irn, so we can get it there.
144 b = get_irn_link(irn);
146 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
149 b->pressure = pressure;
151 b->is_real = is_real;
154 list_add_tail(&b->list, head);
155 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
162 * Check, if an irn is of the register class currently under processing.
163 * @param env The chordal environment.
164 * @param irn The node.
165 * @return 1, if the node is of that register class, 0 if not.
167 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
169 return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
170 // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
173 #define has_limited_constr(req, irn) \
174 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
176 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
178 bitset_t *tmp = alloc_env->tmp_colors;
179 bitset_copy(tmp, colors);
180 bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
181 return bitset_next_clear(tmp, 0);
184 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
189 bitset_copy(bs, o2->regs);
194 bitset_copy(bs, o1->regs);
198 assert(o1->req.cls == o2->req.cls);
200 if(bitset_contains(o1->regs, o2->regs))
201 bitset_copy(bs, o1->regs);
202 else if(bitset_contains(o2->regs, o1->regs))
203 bitset_copy(bs, o2->regs);
210 static be_insn_t *chordal_scan_insn(be_chordal_alloc_env_t *env, ir_node *irn)
214 ie.ignore_colors = env->chordal_env->ignore_colors;
215 ie.aenv = env->chordal_env->birg->main_env->arch_env;
216 ie.obst = &env->chordal_env->obst;
217 ie.cls = env->chordal_env->cls;
218 return be_scan_insn(&ie, irn);
221 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
223 const be_chordal_env_t *env = alloc_env->chordal_env;
225 int n_uses = be_insn_n_uses(insn);
226 int n_defs = be_insn_n_defs(insn);
227 bitset_t *bs = bitset_alloca(env->cls->n_regs);
228 bipartite_t *bp = bipartite_new(n_defs, n_uses);
229 int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
234 For each out operand, try to find an in operand which can be assigned the
235 same register as the out operand.
237 for(j = 0; j < insn->use_start; ++j) {
238 be_operand_t *out_op = &insn->ops[j];
240 /* Try to find an in operand which has ... */
241 for(i = insn->use_start; i < insn->n_ops; ++i) {
242 const be_operand_t *op = &insn->ops[i];
245 The in operand can only be paired with a def, if the node defining the
246 operand's value does not interfere with the instruction itself. That
247 would mean, that it is live at the instruction, so no result of the instruction
248 can have the same register as the operand.
250 Furthermore, tow operands can be paired, if the admissible registers
251 of one are a subset of the other's. We record the operand whose constraints
252 count in the decisive array.
254 if(!values_interfere(env->lv, op->irn, op->carrier)) {
255 if(get_decisive_partner_regs(bs, out_op, op))
256 bipartite_add(bp, j, i - insn->use_start);
261 /* Compute the pairing. */
262 bipartite_matching(bp, pairing);
263 for(i = 0; i < insn->use_start; ++i) {
264 int p = pairing[i] + insn->use_start;
266 if(p >= insn->use_start) {
267 insn->ops[i].partner = &insn->ops[p];
268 insn->ops[p].partner = &insn->ops[i];
276 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
278 be_chordal_env_t *env = alloc_env->chordal_env;
279 const arch_env_t *aenv = env->birg->main_env->arch_env;
280 be_insn_t *insn = *the_insn;
281 ir_node *bl = get_nodes_block(insn->irn);
282 ir_node *copy = NULL;
283 ir_node *perm = NULL;
284 bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
285 bitset_t *bs = bitset_alloca(env->cls->n_regs);
286 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
290 assert(insn->has_constraints && "only do this for constrained nodes");
293 Collect all registers that occur in output constraints.
294 This is necessary, since if the insn has one of these as an input constraint
295 and the corresponding operand interferes with the insn, the operand must
298 for(i = 0; i < insn->use_start; ++i) {
299 be_operand_t *op = &insn->ops[i];
300 if(op->has_constraints)
301 bitset_or(out_constr, op->regs);
305 Now, figure out which input operand must be copied since it has input
306 constraints which are also output constraints.
308 for(i = insn->use_start; i < insn->n_ops; ++i) {
309 be_operand_t *op = &insn->ops[i];
310 if(op->has_constraints && (values_interfere(env->lv, op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
311 bitset_copy(bs, op->regs);
312 bitset_and(bs, out_constr);
315 The operand (interfering with the node) has input constraints
316 which also occur as output constraints, so insert a copy.
318 if(bitset_popcnt(bs) > 0) {
319 copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
321 sched_add_before(insn->irn, copy);
322 set_irn_n(insn->irn, op->pos, op->carrier);
324 DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
330 Make the Perm, recompute liveness and re-scan the insn since the
331 in operands are now the Projs of the Perm.
333 perm = insert_Perm_after(aenv, env->lv, env->cls, env->dom_front, sched_prev(insn->irn));
335 /* Registers are propagated by insert_Perm_after(). Clean them here! */
337 const ir_edge_t *edge;
339 foreach_out_edge(perm, edge) {
340 ir_node *proj = get_edge_src_irn(edge);
341 arch_set_irn_register(aenv, proj, NULL);
345 We also have to re-build the insn since the input operands are now the Projs of
346 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
347 the live sets may change.
349 // be_liveness_recompute(env->lv);
350 obstack_free(&env->obst, insn);
351 *the_insn = insn = chordal_scan_insn(alloc_env, insn->irn);
354 Copy the input constraints of the insn to the Perm as output
355 constraints. Succeeding phases (coalescing will need that).
357 for(i = insn->use_start; i < insn->n_ops; ++i) {
358 be_operand_t *op = &insn->ops[i];
359 ir_node *proj = op->carrier;
361 Note that the predecessor must not be a Proj of the Perm,
362 since ignore-nodes are not Perm'ed.
364 if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
365 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
373 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
375 be_chordal_env_t *env = alloc_env->chordal_env;
376 void *base = obstack_base(&env->obst);
377 be_insn_t *insn = chordal_scan_insn(alloc_env, irn);
378 ir_node *res = insn->next_insn;
379 int be_silent = *silent;
381 if(insn->pre_colored) {
383 for(i = 0; i < insn->use_start; ++i)
384 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
388 If the current node is a barrier toggle the silent flag.
389 If we are in the start block, we are ought to be silent at the beginning,
390 so the toggling activates the constraint handling but skips the barrier.
391 If we are in the end block we handle the in requirements of the barrier
392 and set the rest to silent.
394 if(be_is_Barrier(irn))
401 Perms inserted before the constraint handling phase are considered to be
402 correctly precolored. These Perms arise during the ABI handling phase.
404 if(insn->has_constraints) {
405 const arch_env_t *aenv = env->birg->main_env->arch_env;
406 int n_regs = env->cls->n_regs;
407 bitset_t *bs = bitset_alloca(n_regs);
408 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
409 bipartite_t *bp = bipartite_new(n_regs, n_regs);
410 int *assignment = alloca(n_regs * sizeof(assignment[0]));
411 pmap *partners = pmap_create();
412 DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
416 const ir_edge_t *edge;
417 ir_node *perm = NULL;
420 prepare the constraint handling of this node.
421 Perms are constructed and Copies are created for constrained values
422 interfering with the instruction.
424 perm = pre_process_constraints(alloc_env, &insn);
426 /* find suitable in operands to the out operands of the node. */
427 pair_up_operands(alloc_env, insn);
430 look at the in/out operands and add each operand (and its possible partner)
431 to a bipartite graph (left: nodes with partners, right: admissible colors).
433 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
434 be_operand_t *op = &insn->ops[i];
437 If the operand has no partner or the partner has not been marked
438 for allocation, determine the admissible registers and mark it
439 for allocation by associating the node and its partner with the
440 set of admissible registers via a bipartite graph.
442 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
444 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
445 alloc_nodes[n_alloc] = op->carrier;
447 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
449 bitset_clear_all(bs);
450 get_decisive_partner_regs(bs, op, op->partner);
452 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
454 bitset_foreach(bs, col)
455 bipartite_add(bp, n_alloc, col);
462 Put all nodes which live by the constrained instruction also to the
463 allocation bipartite graph. They are considered unconstrained.
466 foreach_out_edge(perm, edge) {
467 ir_node *proj = get_edge_src_irn(edge);
469 assert(is_Proj(proj));
471 if(values_interfere(env->lv, proj, irn) && !pmap_contains(partners, proj)) {
472 assert(n_alloc < n_regs);
473 alloc_nodes[n_alloc] = proj;
474 pmap_insert(partners, proj, NULL);
476 bitset_clear_all(bs);
477 arch_put_non_ignore_regs(aenv, env->cls, bs);
478 bitset_foreach(bs, col)
479 bipartite_add(bp, n_alloc, col);
486 /* Compute a valid register allocation. */
487 bipartite_matching(bp, assignment);
489 /* Assign colors obtained from the matching. */
490 for(i = 0; i < n_alloc; ++i) {
491 const arch_register_t *reg;
495 assert(assignment[i] >= 0 && "there must have been a register assigned");
496 reg = arch_register_for_index(env->cls, assignment[i]);
498 nodes[0] = alloc_nodes[i];
499 nodes[1] = pmap_get(partners, alloc_nodes[i]);
501 for(j = 0; j < 2; ++j) {
505 arch_set_irn_register(aenv, nodes[j], reg);
506 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
507 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
512 /* Allocate the non-constrained Projs of the Perm. */
515 bitset_clear_all(bs);
517 /* Put the colors of all Projs in a bitset. */
518 foreach_out_edge(perm, edge) {
519 ir_node *proj = get_edge_src_irn(edge);
520 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
523 bitset_set(bs, reg->index);
526 /* Assign the not yet assigned Projs of the Perm a suitable color. */
527 foreach_out_edge(perm, edge) {
528 ir_node *proj = get_edge_src_irn(edge);
529 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
531 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
534 col = get_next_free_reg(alloc_env, bs);
535 reg = arch_register_for_index(env->cls, col);
536 bitset_set(bs, reg->index);
537 arch_set_irn_register(aenv, proj, reg);
538 pset_insert_ptr(alloc_env->pre_colored, proj);
539 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
545 pmap_destroy(partners);
549 obstack_free(&env->obst, base);
554 * Handle constraint nodes in each basic block.
555 * handle_constraints() inserts Perm nodes which perm
556 * over all values live at the constrained node right in front
557 * of the constrained node. These Perms signal a constrained node.
558 * For further comments, refer to handle_constraints().
560 static void constraints(ir_node *bl, void *data)
562 be_chordal_alloc_env_t *env = data;
565 Start silent in the start block.
566 The silence remains until the first barrier is seen.
567 Each other block is begun loud.
569 int silent = bl == get_irg_start_block(get_irn_irg(bl));
573 If the block is the start block search the barrier and
574 start handling constraints from there.
577 for(irn = sched_first(bl); !sched_is_end(irn);) {
578 irn = handle_constraints(env, irn, &silent);
583 * Annotate the register pressure to the nodes and compute
584 * the liveness intervals.
585 * @param block The block to do it for.
586 * @param env_ptr The environment.
588 static void pressure(ir_node *block, void *env_ptr)
590 /* Convenience macro for a def */
591 #define border_def(irn, step, real) \
592 border_add(env, head, irn, step, pressure--, 1, real)
594 /* Convenience macro for a use */
595 #define border_use(irn, step, real) \
596 border_add(env, head, irn, step, ++pressure, 0, real)
598 be_chordal_alloc_env_t *alloc_env = env_ptr;
599 be_chordal_env_t *env = alloc_env->chordal_env;
600 bitset_t *live = alloc_env->live;
602 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
606 unsigned pressure = 0;
607 struct list_head *head;
608 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
609 pset *live_end = be_lv_pset_put_end(env->lv, block, pset_new_ptr_default());
611 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
612 bitset_clear_all(live);
614 /* Set up the border list in the block info */
615 head = obstack_alloc(&env->obst, sizeof(*head));
616 INIT_LIST_HEAD(head);
617 assert(pmap_get(env->border_heads, block) == NULL);
618 pmap_insert(env->border_heads, block, head);
621 * Make final uses of all values live out of the block.
622 * They are necessary to build up real intervals.
624 foreach_pset(live_end, irn) {
625 if(has_reg_class(env, irn)) {
626 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
627 bitset_set(live, get_irn_idx(irn));
628 border_use(irn, step, 0);
634 * Determine the last uses of a value inside the block, since they are
635 * relevant for the interval borders.
637 sched_foreach_reverse(block, irn) {
638 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
639 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
642 * If the node defines some value, which can put into a
643 * register of the current class, make a border for it.
645 if(has_reg_class(env, irn)) {
646 int nr = get_irn_idx(irn);
648 bitset_clear(live, nr);
649 border_def(irn, step, 1);
653 * If the node is no phi node we can examine the uses.
656 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
657 ir_node *op = get_irn_n(irn, i);
659 if(has_reg_class(env, op)) {
660 int nr = get_irn_idx(op);
661 const char *msg = "-";
663 if(!bitset_is_set(live, nr)) {
664 border_use(op, step, 1);
665 bitset_set(live, nr);
669 DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
677 * Add initial defs for all values live in.
679 foreach_pset(live_in, irn) {
680 if(has_reg_class(env, irn)) {
682 /* Mark the value live in. */
683 bitset_set(live, get_irn_idx(irn));
686 border_def(irn, step, 0);
694 static void assign(ir_node *block, void *env_ptr)
696 be_chordal_alloc_env_t *alloc_env = env_ptr;
697 be_chordal_env_t *env = alloc_env->chordal_env;
698 bitset_t *live = alloc_env->live;
699 bitset_t *colors = alloc_env->colors;
700 bitset_t *in_colors = alloc_env->in_colors;
701 const arch_env_t *arch_env = env->birg->main_env->arch_env;
702 struct list_head *head = get_block_border_head(env, block);
703 pset *live_in = be_lv_pset_put_in(env->lv, block, pset_new_ptr_default());
707 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
709 bitset_clear_all(colors);
710 bitset_clear_all(live);
711 bitset_clear_all(in_colors);
713 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
714 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
715 list_for_each_entry(border_t, b, head, list) {
716 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
717 b->irn, get_irn_idx(b->irn)));
721 * Add initial defs for all values live in.
722 * Since their colors have already been assigned (The dominators were
723 * allocated before), we have to mark their colors as used also.
725 foreach_pset(live_in, irn) {
726 if(has_reg_class(env, irn)) {
727 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
730 assert(reg && "Node must have been assigned a register");
731 col = arch_register_get_index(reg);
733 DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
735 /* Mark the color of the live in value as used. */
736 bitset_set(colors, col);
737 bitset_set(in_colors, col);
739 /* Mark the value live in. */
740 bitset_set(live, get_irn_idx(irn));
745 * Mind that the sequence
746 * of defs from back to front defines a perfect
747 * elimination order. So, coloring the definitions from first to last
750 list_for_each_entry_reverse(border_t, b, head, list) {
751 ir_node *irn = b->irn;
752 int nr = get_irn_idx(irn);
753 int ignore = arch_irn_is(arch_env, irn, ignore);
756 * Assign a color, if it is a local def. Global defs already have a
759 if(b->is_def && !be_is_live_in(env->lv, block, irn)) {
760 const arch_register_t *reg;
763 if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
764 reg = arch_get_irn_register(arch_env, irn);
766 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
770 col = get_next_free_reg(alloc_env, colors);
771 reg = arch_register_for_index(env->cls, col);
772 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
773 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
776 bitset_set(colors, col);
777 arch_set_irn_register(arch_env, irn, reg);
779 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
781 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
782 bitset_set(live, nr);
785 /* Clear the color upon a use. */
786 else if(!b->is_def) {
787 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
790 assert(reg && "Register must have been assigned");
792 col = arch_register_get_index(reg);
793 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
795 bitset_clear(colors, col);
796 bitset_clear(live, nr);
803 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
805 be_chordal_alloc_env_t env;
808 int colors_n = arch_register_class_n_regs(chordal_env->cls);
809 ir_graph *irg = chordal_env->irg;
814 env.chordal_env = chordal_env;
815 env.colors_n = colors_n;
816 env.colors = bitset_alloca(colors_n);
817 env.tmp_colors = bitset_alloca(colors_n);
818 env.in_colors = bitset_alloca(colors_n);
819 env.pre_colored = pset_new_ptr_default();
820 FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
823 /* Handle register targeting constraints */
824 dom_tree_walk_irg(irg, constraints, NULL, &env);
826 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
827 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
828 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
832 env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
834 /* First, determine the pressure */
835 dom_tree_walk_irg(irg, pressure, NULL, &env);
837 /* Assign the colors */
838 dom_tree_walk_irg(irg, assign, NULL, &env);
840 be_numbering_done(irg);
842 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
844 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
845 plotter = new_plotter_ps(buf);
846 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
847 plotter_free(plotter);
850 bitset_free(env.live);
851 del_pset(env.pre_colored);