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)) {
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);
331 if(!has_constraint || can_be_constrained) {
332 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)
342 #define MAX(x, y) ((x) > (y) ? (x) : (y))
344 static void pair_up_operands(const arch_env_t *arch_env, insn_t *insn) {
346 int m = MAX(insn->n_ops - insn->use_start, 1);
347 bipartite_t *bp = bipartite_new(MAX(insn->use_start, 1), m);
348 int *match = alloca(insn->use_start * sizeof(match[0]));
350 for(i = 0; i < insn->use_start; ++i) {
351 operand_t *op = &insn->ops[i];
352 const arch_register_t *reg = arch_get_irn_register(arch_env, op->carrier);
353 int has_constraint = arch_register_req_is(&op->req, limited);
354 add_possible_partners(insn, i, reg, bp, !has_constraint);
357 bipartite_matching(bp, match);
358 for(i = 0; i < insn->use_start; ++i) {
359 int p = match[i] + insn->use_start;
361 if(p >= insn->use_start) {
362 insn->ops[i].partner = &insn->ops[p];
363 insn->ops[p].partner = &insn->ops[i];
370 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn)
372 be_chordal_env_t *env = alloc_env->chordal_env;
373 void *base = obstack_base(&env->obst);
374 insn_t *insn = scan_insn(env, irn, &env->obst);
375 ir_node *res = insn->next_insn;
378 if(insn->pre_colored) {
380 for(i = 0; i < insn->use_start; ++i)
381 pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
384 if(be_is_Perm(irn) || be_is_RegParams(irn) || (be_is_Barrier(irn) && !insn->in_constraints))
388 Perms inserted before the constraint handling phase are considered to be
389 correctly precolored. These Perms arise during the ABI handling phase.
391 if(insn->has_constraints) {
392 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
393 const arch_env_t *aenv = env->birg->main_env->arch_env;
394 int n_regs = env->cls->n_regs;
395 bitset_t *bs = bitset_alloca(n_regs);
396 bitset_t *non_ignore = bitset_alloca(n_regs);
397 ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
398 bipartite_t *bp = bipartite_new(n_regs, n_regs);
399 int *assignment = alloca(n_regs * sizeof(assignment[0]));
400 pmap *partners = pmap_create();
404 const ir_edge_t *edge;
405 ir_node *perm = NULL;
407 // if(!insn->pre_colored || insn->in_constraints)
408 perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(irn));
410 arch_put_non_ignore_regs(aenv, env->cls, non_ignore);
412 /* Registers are propagated by insert_Perm_after(). Clean them here! */
414 foreach_out_edge(perm, edge) {
415 ir_node *proj = get_edge_src_irn(edge);
416 arch_set_irn_register(aenv, proj, NULL);
421 be_liveness(env->irg);
422 insn = scan_insn(env, irn, &env->obst);
424 DBG((dbg, LEVEL_1, "handling constraints for %+F\n", irn));
427 * If there was no Perm made, nothing was alive in this register class.
428 * This means, that the node has no operands, thus no input constraints.
429 * so it had output constraints. The other results then can be assigned freely.
432 pair_up_operands(aenv, insn);
434 for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
435 operand_t *op = &insn->ops[i];
436 if((op->partner ? !pmap_contains(partners, op->partner->carrier) : 1)
437 && arch_register_req_is(&op->req, limited)
438 && arch_irn_consider_in_reg_alloc(aenv, env->cls, op->carrier)) {
440 pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
441 alloc_nodes[n_alloc] = op->carrier;
443 DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, pmap_get(partners, op->carrier)));
445 bitset_clear_all(bs);
446 op->req.limited(op->req.limited_env, bs);
447 bitset_and(bs, non_ignore);
449 DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
451 bitset_foreach(bs, col)
452 bipartite_add(bp, n_alloc, col);
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 /* Make the input constraints of the node to output constraints of the Perm's Projs */
509 for(i = insn->use_start; i < insn->n_ops; ++i) {
510 operand_t *op = &insn->ops[i];
513 If the operand is an "in" operand, constrained and the carrier is a Proj to the Perm,
514 then copy the in constraint to the Perm's out constraint
516 if(arch_register_req_is(&op->req, limited) && is_Proj(op->carrier) && perm == get_Proj_pred(op->carrier))
517 be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(op->carrier)), &op->req);
520 bitset_clear_all(bs);
522 /* Put the colors of all Projs in a bitset. */
523 foreach_out_edge(perm, edge) {
524 ir_node *proj = get_edge_src_irn(edge);
525 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
528 bitset_set(bs, reg->index);
531 /* Assign the not yet assigned Projs of the Perm a suitable color. */
532 foreach_out_edge(perm, edge) {
533 ir_node *proj = get_edge_src_irn(edge);
534 const arch_register_t *reg = arch_get_irn_register(aenv, proj);
536 DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
539 col = bitset_next_clear(bs, 0);
540 reg = arch_register_for_index(env->cls, col);
541 bitset_set(bs, reg->index);
542 arch_set_irn_register(aenv, proj, reg);
543 pset_insert_ptr(alloc_env->pre_colored, proj);
544 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
549 pmap_destroy(partners);
553 obstack_free(&env->obst, base);
558 * Handle constraint nodes in each basic block.
559 * be_insert_constr_perms() inserts Perm nodes which perm
560 * over all values live at the constrained node right in front
561 * of the constrained node. These Perms signal a constrained node.
562 * For further comments, refer to handle_constraints_at_perm().
564 static void constraints(ir_node *bl, void *data)
566 firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
567 be_chordal_alloc_env_t *env = data;
568 arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
571 for(irn = sched_first(bl); !sched_is_end(irn);) {
572 irn = handle_constraints(env, irn);
577 * Annotate the register pressure to the nodes and compute
578 * the liveness intervals.
579 * @param block The block to do it for.
580 * @param env_ptr The environment.
582 static void pressure(ir_node *block, void *env_ptr)
584 /* Convenience macro for a def */
585 #define border_def(irn, step, real) \
586 border_add(env, head, irn, step, pressure--, 1, real)
588 /* Convenience macro for a use */
589 #define border_use(irn, step, real) \
590 border_add(env, head, irn, step, ++pressure, 0, real)
592 be_chordal_alloc_env_t *alloc_env = env_ptr;
593 be_chordal_env_t *env = alloc_env->chordal_env;
594 const arch_env_t *arch_env = env->birg->main_env->arch_env;
595 bitset_t *live = alloc_env->live;
596 firm_dbg_module_t *dbg = env->dbg;
601 unsigned pressure = 0;
602 struct list_head *head;
603 pset *live_in = put_live_in(block, pset_new_ptr_default());
604 pset *live_end = put_live_end(block, pset_new_ptr_default());
606 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
607 bitset_clear_all(live);
609 /* Set up the border list in the block info */
610 head = obstack_alloc(&env->obst, sizeof(*head));
611 INIT_LIST_HEAD(head);
612 assert(pmap_get(env->border_heads, block) == NULL);
613 pmap_insert(env->border_heads, block, head);
616 * Make final uses of all values live out of the block.
617 * They are necessary to build up real intervals.
619 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
620 if(has_reg_class(env, irn)) {
621 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
622 bitset_set(live, get_irn_graph_nr(irn));
623 border_use(irn, step, 0);
629 * Determine the last uses of a value inside the block, since they are
630 * relevant for the interval borders.
632 sched_foreach_reverse(block, irn) {
633 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
634 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
637 * If the node defines some value, which can put into a
638 * register of the current class, make a border for it.
640 if(has_reg_class(env, irn)) {
641 int nr = get_irn_graph_nr(irn);
643 bitset_clear(live, nr);
644 border_def(irn, step, 1);
648 * If the node is no phi node we can examine the uses.
651 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
652 ir_node *op = get_irn_n(irn, i);
654 if(has_reg_class(env, op)) {
655 int nr = get_irn_graph_nr(op);
657 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
659 if(!bitset_is_set(live, nr)) {
660 border_use(op, step, 1);
661 bitset_set(live, nr);
670 * Add initial defs for all values live in.
672 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
673 if(has_reg_class(env, irn)) {
675 /* Mark the value live in. */
676 bitset_set(live, get_irn_graph_nr(irn));
679 border_def(irn, step, 0);
688 static void assign(ir_node *block, void *env_ptr)
690 be_chordal_alloc_env_t *alloc_env = env_ptr;
691 be_chordal_env_t *env = alloc_env->chordal_env;
692 firm_dbg_module_t *dbg = env->dbg;
693 bitset_t *live = alloc_env->live;
694 bitset_t *colors = alloc_env->colors;
695 bitset_t *in_colors = alloc_env->in_colors;
696 const arch_env_t *arch_env = env->birg->main_env->arch_env;
700 struct list_head *head = get_block_border_head(env, block);
701 pset *live_in = put_live_in(block, pset_new_ptr_default());
703 bitset_clear_all(colors);
704 bitset_clear_all(live);
705 bitset_clear_all(in_colors);
707 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
708 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
709 list_for_each_entry(border_t, b, head, list) {
710 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
711 b->irn, get_irn_graph_nr(b->irn)));
715 * Add initial defs for all values live in.
716 * Since their colors have already been assigned (The dominators were
717 * allocated before), we have to mark their colors as used also.
719 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
720 if(has_reg_class(env, irn)) {
721 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
724 assert(reg && "Node must have been assigned a register");
725 col = arch_register_get_index(reg);
727 /* Mark the color of the live in value as used. */
728 bitset_set(colors, col);
729 bitset_set(in_colors, col);
731 /* Mark the value live in. */
732 bitset_set(live, get_irn_graph_nr(irn));
737 * Mind that the sequence
738 * of defs from back to front defines a perfect
739 * elimination order. So, coloring the definitions from first to last
742 list_for_each_entry_reverse(border_t, b, head, list) {
743 ir_node *irn = b->irn;
744 int nr = get_irn_graph_nr(irn);
747 * Assign a color, if it is a local def. Global defs already have a
750 if(b->is_def && !is_live_in(block, irn)) {
751 const arch_register_t *reg;
754 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
755 reg = arch_get_irn_register(arch_env, irn);
757 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
761 col = bitset_next_clear(colors, 0);
762 reg = arch_register_for_index(env->cls, col);
763 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
766 bitset_set(colors, col);
768 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
769 arch_set_irn_register(arch_env, irn, reg);
771 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
772 arch_register_get_name(reg), col, irn));
774 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
775 bitset_set(live, nr);
778 /* Clear the color upon a use. */
779 else if(!b->is_def) {
780 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
783 assert(reg && "Register must have been assigned");
785 col = arch_register_get_index(reg);
786 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
788 bitset_clear(colors, col);
789 bitset_clear(live, nr);
796 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
798 be_chordal_alloc_env_t env;
801 int colors_n = arch_register_class_n_regs(chordal_env->cls);
802 ir_graph *irg = chordal_env->irg;
805 if(get_irg_dom_state(irg) != dom_consistent)
808 env.chordal_env = chordal_env;
809 env.colors_n = colors_n;
810 env.colors = bitset_malloc(colors_n);
811 env.in_colors = bitset_malloc(colors_n);
812 env.pre_colored = pset_new_ptr_default();
814 /* Handle register targeting constraints */
815 dom_tree_walk_irg(irg, constraints, NULL, &env);
817 if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
818 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
819 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
823 env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
825 /* First, determine the pressure */
826 dom_tree_walk_irg(irg, pressure, NULL, &env);
828 /* Assign the colors */
829 dom_tree_walk_irg(irg, assign, NULL, &env);
831 be_numbering_done(irg);
833 if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
835 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
836 plotter = new_plotter_ps(buf);
837 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
838 plotter_free(plotter);
844 del_pset(env.pre_colored);