2 * Chordal register allocation.
3 * @author Sebastian Hack
6 * Copyright (C) Universitaet Karlsruhe
7 * Released under the GPL
29 #include "bipartite.h"
32 #include "irgraph_t.h"
33 #include "irprintf_t.h"
43 #include "besched_t.h"
49 #include "bechordal_t.h"
50 #include "bechordal_draw.h"
52 #define DBG_LEVEL SET_LEVEL_0
53 #define DBG_LEVEL_CHECK SET_LEVEL_0
57 #define DUMP_INTERVALS
59 typedef struct _be_chordal_alloc_env_t {
60 be_chordal_env_t *chordal_env;
62 pset *pre_colored; /**< Set of precolored nodes. */
63 bitset_t *live; /**< A liveness bitset. */
64 bitset_t *colors; /**< The color mask. */
65 bitset_t *in_colors; /**< Colors used by live in values. */
66 int colors_n; /**< The number of colors. */
67 } be_chordal_alloc_env_t;
71 /* Make a fourcc for border checking. */
72 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
74 static void check_border_list(struct list_head *head)
77 list_for_each_entry(border_t, x, head, list) {
78 assert(x->magic == BORDER_FOURCC);
82 static void check_heads(be_chordal_env_t *env)
85 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
86 /* ir_printf("checking border list of block %+F\n", ent->key); */
87 check_border_list(ent->value);
93 * Add an interval border to the list of a block's list
95 * @note You always have to create the use before the def.
96 * @param env The environment.
97 * @param head The list head to enqueue the borders.
98 * @param irn The node (value) the border belongs to.
99 * @param pressure The pressure at this point in time.
100 * @param step A time step for the border.
101 * @param is_def Is the border a use or a def.
102 * @return The created border.
104 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
105 ir_node *irn, unsigned step, unsigned pressure,
106 unsigned is_def, unsigned is_real)
113 b = obstack_alloc(&env->obst, sizeof(*b));
115 /* also allocate the def and tie it to the use. */
116 def = obstack_alloc(&env->obst, sizeof(*def));
117 memset(def, 0, sizeof(*def));
122 * Set the link field of the irn to the def.
123 * This strongly relies on the fact, that the use is always
124 * made before the def.
126 set_irn_link(irn, def);
128 b->magic = BORDER_FOURCC;
129 def->magic = BORDER_FOURCC;
133 * If the def is encountered, the use was made and so was the
134 * the def node (see the code above). It was placed into the
135 * link field of the irn, so we can get it there.
138 b = get_irn_link(irn);
140 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
143 b->pressure = pressure;
145 b->is_real = is_real;
148 list_add_tail(&b->list, head);
149 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
156 * Check, if an irn is of the register class currently under processing.
157 * @param env The chordal environment.
158 * @param irn The node.
159 * @return 1, if the node is of that register class, 0 if not.
161 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
163 // return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
164 return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
167 #define has_limited_constr(req, irn) \
168 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
170 typedef struct _operand_t operand_t;
177 arch_register_req_t req;
185 unsigned in_constraints : 1;
186 unsigned out_constraints : 1;
187 unsigned has_constraints : 1;
188 unsigned pre_colored : 1;
191 static insn_t *scan_insn(be_chordal_env_t *env, ir_node *irn, struct obstack *obst)
193 const arch_env_t *arch_env = env->birg->main_env->arch_env;
199 insn = obstack_alloc(obst, sizeof(insn[0]));
200 memset(insn, 0, sizeof(insn[0]));
202 insn->next_insn = sched_next(irn);
203 if(get_irn_mode(irn) == mode_T) {
206 for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
207 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
210 o.pos = -(get_Proj_proj(p) + 1);
212 arch_get_register_req(arch_env, &o.req, p, -1);
213 obstack_grow(obst, &o, sizeof(o));
215 insn->out_constraints |= arch_register_req_is(&o.req, limited);
216 pre_colored += arch_get_irn_register(arch_env, p) != NULL;
223 else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
228 arch_get_register_req(arch_env, &o.req, irn, -1);
229 obstack_grow(obst, &o, sizeof(o));
231 insn->out_constraints |= arch_register_req_is(&o.req, limited);
232 pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
235 insn->pre_colored = pre_colored == insn->n_ops;
236 insn->use_start = insn->n_ops;
238 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
239 ir_node *op = get_irn_n(irn, i);
241 if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
246 arch_get_register_req(arch_env, &o.req, irn, i);
247 obstack_grow(obst, &o, sizeof(o));
249 insn->in_constraints |= arch_register_req_is(&o.req, limited);
253 insn->has_constraints = insn->in_constraints | insn->out_constraints;
254 insn->ops = obstack_finish(obst);
259 static operand_t *find_unpaired_use(insn_t *insn, const operand_t *op, int can_be_constrained)
262 operand_t *res = NULL;
264 for(i = insn->use_start; i < insn->n_ops; ++i) {
265 operand_t *op = &insn->ops[i];
266 int has_constraint = arch_register_req_is(&op->req, limited);
268 if(!values_interfere(op->carrier, op->irn) && !op->partner) {
270 if(!has_constraint || can_be_constrained) {
271 if(arch_register_req_is(&op->req, should_be_same) && op->req.other_same == op->carrier)
282 static void pair_up_operands(insn_t *insn)
284 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
287 for(i = 0; i < insn->use_start; ++i) {
288 operand_t *op = &insn->ops[i];
289 int has_constraint = arch_register_req_is(&op->req, limited);
290 operand_t *partner = find_unpaired_use(insn, op, !has_constraint);
293 op->partner = partner;
294 partner->partner = op;
300 static void add_possible_partners(insn_t *insn, int curr, const arch_register_t *out_reg, bipartite_t *bp, int can_be_constrained)
306 bs = bitset_alloca(out_reg->reg_class->n_regs);
308 for(i = insn->use_start; i < insn->n_ops; ++i) {
309 const operand_t *op = &insn->ops[i];
312 The in operand can only be paired with a def, if the node defining the
313 operand's value does not interfere with the instruction itself. That
314 would mean, that it is live at the instruction, so no result of the instruction
315 can have the same register as the operand.
317 Furthermore, if the operand has already been paired (due to previous calls)
318 to this function, we do not touch this partnership.
320 if(!values_interfere(op->irn, op->carrier) && !op->partner) {
321 int has_constraint = arch_register_req_is(&op->req, limited);
323 if(has_constraint && out_reg && out_reg->reg_class == op->req.cls) {
324 bitset_clear_all(bs);
325 op->req.limited(op->req.limited_env, bs);
326 if(bitset_is_set(bs, out_reg->index)) {
327 bipartite_add(bp, curr, i - insn->use_start);
332 if(!has_constraint || can_be_constrained) {
333 bipartite_add(bp, curr, i - insn->use_start);
334 if(arch_register_req_is(&op->req, should_be_same) && op->req.other_same == op->carrier)
341 static void pair_up_operands(const arch_env_t *arch_env, insn_t *insn) {
343 bipartite_t *bp = bipartite_new(insn->use_start, insn->n_ops - insn->use_start);
344 int *match = alloca(insn->use_start * sizeof(match[0]));
346 for(i = 0; i < insn->use_start; ++i) {
347 operand_t *op = &insn->ops[i];
348 const arch_register_t *reg = arch_get_irn_register(arch_env, op->carrier);
349 int has_constraint = arch_register_req_is(&op->req, limited);
350 add_possible_partners(insn, i, reg, bp, !has_constraint);
353 bipartite_matching(bp, match);
354 for(i = 0; i < insn->use_start; ++i) {
355 int p = match[i] + insn->use_start;
357 if(p >= insn->use_start) {
358 insn->ops[i].partner = &insn->ops[p];
359 insn->ops[p].partner = &insn->ops[i];
366 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn)
368 be_chordal_env_t *env = alloc_env->chordal_env;
369 void *base = obstack_base(&env->obst);
370 insn_t *insn = scan_insn(env, irn, &env->obst);
371 ir_node *res = insn->next_insn;
373 if(insn->pre_colored) {
375 for(i = 0; i < insn->use_start; ++i)
376 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
380 Perms inserted before the constraint handling phase are considered to be
381 correctly precolored. These Perms arise during the ABI handling phase.
383 if(insn->has_constraints && !be_is_Perm(irn)) {
384 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
385 const arch_env_t *aenv = env->birg->main_env->arch_env;
386 int n_regs = env->cls->n_regs;
387 bitset_t *bs = bitset_alloca(n_regs);
388 bitset_t *non_ignore = bitset_alloca(n_regs);
389 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
390 bipartite_t *bp = bipartite_new(n_regs, n_regs);
391 int *assignment = alloca(n_regs * sizeof(assignment[0]));
392 pmap *partners = pmap_create();
396 const ir_edge_t *edge;
397 ir_node *perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(irn));
399 arch_put_non_ignore_regs(aenv, env->cls, non_ignore);
401 /* Registers are propagated by insert_Perm_after(). Clean them here! */
403 foreach_out_edge(perm, edge) {
404 ir_node *proj = get_edge_src_irn(edge);
405 arch_set_irn_register(aenv, proj, NULL);
410 be_liveness(env->irg);
411 insn = scan_insn(env, irn, &env->obst);
413 DBG((dbg, LEVEL_1, "handling constraints for %+F\n", irn));
416 * If there was no Perm made, nothing was alive in this register class.
417 * This means, that the node has no operands, thus no input constraints.
418 * so it had output constraints. The other results then can be assigned freely.
421 pair_up_operands(aenv, insn);
423 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
424 operand_t *op = &insn->ops[i];
425 if((op->partner ? !pmap_contains(partners, op->partner->carrier) : 1)
426 && arch_register_req_is(&op->req, limited)
427 && arch_irn_consider_in_reg_alloc(aenv, env->cls, op->carrier)) {
429 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
430 alloc_nodes[n_alloc] = op->carrier;
432 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, pmap_get(partners, op->carrier)));
434 bitset_clear_all(bs);
435 op->req.limited(op->req.limited_env, bs);
436 bitset_and(bs, non_ignore);
438 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
440 bitset_foreach(bs, col)
441 bipartite_add(bp, n_alloc, col);
448 /* Make the input constraints of the node to output constraints of the Perm's Projs */
449 for(i = insn->use_start; i < insn->n_ops; ++i) {
450 operand_t *op = &insn->ops[i];
453 If the operand is an "in" operand, constrained and the carrier is a Proj to the Perm,
454 then copy the in constraint to the Perm's out constraint
456 if(arch_register_req_is(&op->req, limited) && is_Proj(op->carrier) && perm == get_Proj_pred(op->carrier))
457 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(op->carrier)), &op->req);
460 foreach_out_edge(perm, edge) {
461 ir_node *proj = get_edge_src_irn(edge);
463 assert(is_Proj(proj));
465 if(values_interfere(proj, irn)) {
466 assert(n_alloc < n_regs);
467 alloc_nodes[n_alloc] = proj;
468 pmap_insert(partners, proj, NULL);
470 bitset_clear_all(bs);
471 arch_get_allocatable_regs(aenv, proj, -1, bs);
472 bitset_and(bs, non_ignore);
473 bitset_foreach(bs, col)
474 bipartite_add(bp, n_alloc, col);
481 bipartite_matching(bp, assignment);
483 /* Assign colors obtained from the matching. */
484 for(i = 0; i < n_alloc; ++i) {
487 const arch_register_t *reg;
489 assert(assignment[i] >= 0 && "there must have been a register assigned");
490 reg = arch_register_for_index(env->cls, assignment[i]);
492 nodes[0] = alloc_nodes[i];
493 nodes[1] = pmap_get(partners, alloc_nodes[i]);
495 for(j = 0; j < 2; ++j) {
499 arch_set_irn_register(aenv, nodes[j], reg);
500 pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
501 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
506 /* Allocate the non-constrained Projs of the Perm. */
508 bitset_clear_all(bs);
510 /* Put the colors of all Projs in a bitset. */
511 foreach_out_edge(perm, edge) {
512 ir_node *proj = get_edge_src_irn(edge);
513 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
516 bitset_set(bs, reg->index);
519 /* Assign the not yet assigned Projs of the Perm a suitable color. */
520 foreach_out_edge(perm, edge) {
521 ir_node *proj = get_edge_src_irn(edge);
522 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
524 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
527 col = bitset_next_clear(bs, 0);
528 reg = arch_register_for_index(env->cls, col);
529 bitset_set(bs, reg->index);
530 arch_set_irn_register(aenv, proj, reg);
531 pset_insert_ptr(alloc_env->pre_colored, proj);
532 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
537 pmap_destroy(partners);
540 obstack_free(&env->obst, base);
545 * Handle constraint nodes in each basic block.
546 * be_insert_constr_perms() inserts Perm nodes which perm
547 * over all values live at the constrained node right in front
548 * of the constrained node. These Perms signal a constrained node.
549 * For further comments, refer to handle_constraints_at_perm().
551 static void constraints(ir_node *bl, void *data)
553 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
554 be_chordal_alloc_env_t *env = data;
555 arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
558 for(irn = sched_first(bl); !sched_is_end(irn);) {
559 irn = handle_constraints(env, irn);
564 * Annotate the register pressure to the nodes and compute
565 * the liveness intervals.
566 * @param block The block to do it for.
567 * @param env_ptr The environment.
569 static void pressure(ir_node *block, void *env_ptr)
571 /* Convenience macro for a def */
572 #define border_def(irn, step, real) \
573 border_add(env, head, irn, step, pressure--, 1, real)
575 /* Convenience macro for a use */
576 #define border_use(irn, step, real) \
577 border_add(env, head, irn, step, ++pressure, 0, real)
579 be_chordal_alloc_env_t *alloc_env = env_ptr;
580 be_chordal_env_t *env = alloc_env->chordal_env;
581 const arch_env_t *arch_env = env->birg->main_env->arch_env;
582 bitset_t *live = alloc_env->live;
583 firm_dbg_module_t *dbg = env->dbg;
588 unsigned pressure = 0;
589 struct list_head *head;
590 pset *live_in = put_live_in(block, pset_new_ptr_default());
591 pset *live_end = put_live_end(block, pset_new_ptr_default());
593 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
594 bitset_clear_all(live);
596 /* Set up the border list in the block info */
597 head = obstack_alloc(&env->obst, sizeof(*head));
598 INIT_LIST_HEAD(head);
599 assert(pmap_get(env->border_heads, block) == NULL);
600 pmap_insert(env->border_heads, block, head);
603 * Make final uses of all values live out of the block.
604 * They are necessary to build up real intervals.
606 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
607 if(has_reg_class(env, irn)) {
608 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
609 bitset_set(live, get_irn_graph_nr(irn));
610 border_use(irn, step, 0);
616 * Determine the last uses of a value inside the block, since they are
617 * relevant for the interval borders.
619 sched_foreach_reverse(block, irn) {
620 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
621 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
624 * If the node defines some value, which can put into a
625 * register of the current class, make a border for it.
627 if(has_reg_class(env, irn)) {
628 int nr = get_irn_graph_nr(irn);
630 bitset_clear(live, nr);
631 border_def(irn, step, 1);
635 * If the node is no phi node we can examine the uses.
638 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
639 ir_node *op = get_irn_n(irn, i);
641 if(has_reg_class(env, op)) {
642 int nr = get_irn_graph_nr(op);
644 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
646 if(!bitset_is_set(live, nr)) {
647 border_use(op, step, 1);
648 bitset_set(live, nr);
657 * Add initial defs for all values live in.
659 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
660 if(has_reg_class(env, irn)) {
662 /* Mark the value live in. */
663 bitset_set(live, get_irn_graph_nr(irn));
666 border_def(irn, step, 0);
675 static void assign(ir_node *block, void *env_ptr)
677 be_chordal_alloc_env_t *alloc_env = env_ptr;
678 be_chordal_env_t *env = alloc_env->chordal_env;
679 firm_dbg_module_t *dbg = env->dbg;
680 bitset_t *live = alloc_env->live;
681 bitset_t *colors = alloc_env->colors;
682 bitset_t *in_colors = alloc_env->in_colors;
683 const arch_env_t *arch_env = env->birg->main_env->arch_env;
687 struct list_head *head = get_block_border_head(env, block);
688 pset *live_in = put_live_in(block, pset_new_ptr_default());
690 bitset_clear_all(colors);
691 bitset_clear_all(live);
692 bitset_clear_all(in_colors);
694 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
695 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
696 list_for_each_entry(border_t, b, head, list) {
697 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
698 b->irn, get_irn_graph_nr(b->irn)));
702 * Add initial defs for all values live in.
703 * Since their colors have already been assigned (The dominators were
704 * allocated before), we have to mark their colors as used also.
706 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
707 if(has_reg_class(env, irn)) {
708 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
711 assert(reg && "Node must have been assigned a register");
712 col = arch_register_get_index(reg);
714 /* Mark the color of the live in value as used. */
715 bitset_set(colors, col);
716 bitset_set(in_colors, col);
718 /* Mark the value live in. */
719 bitset_set(live, get_irn_graph_nr(irn));
724 * Mind that the sequence
725 * of defs from back to front defines a perfect
726 * elimination order. So, coloring the definitions from first to last
729 list_for_each_entry_reverse(border_t, b, head, list) {
730 ir_node *irn = b->irn;
731 int nr = get_irn_graph_nr(irn);
734 * Assign a color, if it is a local def. Global defs already have a
737 if(b->is_def && !is_live_in(block, irn)) {
738 const arch_register_t *reg;
741 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
742 reg = arch_get_irn_register(arch_env, irn);
744 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
748 col = bitset_next_clear(colors, 0);
749 reg = arch_register_for_index(env->cls, col);
750 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
753 bitset_set(colors, col);
754 arch_set_irn_register(arch_env, irn, reg);
756 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
757 arch_register_get_name(reg), col, irn));
759 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
760 bitset_set(live, nr);
763 /* Clear the color upon a use. */
764 else if(!b->is_def) {
765 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
768 assert(reg && "Register must have been assigned");
770 col = arch_register_get_index(reg);
771 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
773 bitset_clear(colors, col);
774 bitset_clear(live, nr);
781 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
783 be_chordal_alloc_env_t env;
786 int colors_n = arch_register_class_n_regs(chordal_env->cls);
787 ir_graph *irg = chordal_env->irg;
790 if(get_irg_dom_state(irg) != dom_consistent)
793 env.chordal_env = chordal_env;
794 env.colors_n = colors_n;
795 env.colors = bitset_malloc(colors_n);
796 env.in_colors = bitset_malloc(colors_n);
797 env.pre_colored = pset_new_ptr_default();
799 /* Handle register targeting constraints */
800 dom_tree_walk_irg(irg, constraints, NULL, &env);
802 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
803 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
804 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
808 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
810 /* First, determine the pressure */
811 dom_tree_walk_irg(irg, pressure, NULL, &env);
813 /* Assign the colors */
814 dom_tree_walk_irg(irg, assign, NULL, &env);
816 be_numbering_done(irg);
818 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
820 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
821 plotter = new_plotter_ps(buf);
822 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
823 plotter_free(plotter);
829 del_pset(env.pre_colored);