2 * Chordal register allocation.
3 * @author Sebastian Hack
6 * Copyright (C) Universitaet Karlsruhe
7 * Released under the GPL
31 #include "irgraph_t.h"
32 #include "irprintf_t.h"
42 #include "besched_t.h"
48 #include "bechordal_t.h"
49 #include "bechordal_draw.h"
51 #define DBG_LEVEL SET_LEVEL_0
52 #define DBG_LEVEL_CHECK SET_LEVEL_0
58 typedef struct _be_chordal_alloc_env_t {
59 be_chordal_env_t *chordal_env;
61 pset *pre_colored; /**< Set of precolored nodes. */
62 bitset_t *live; /**< A liveness bitset. */
63 bitset_t *colors; /**< The color mask. */
64 bitset_t *in_colors; /**< Colors used by live in values. */
65 int colors_n; /**< The number of colors. */
66 } be_chordal_alloc_env_t;
70 /* Make a fourcc for border checking. */
71 #define BORDER_FOURCC FOURCC('B', 'O', 'R', 'D')
73 static void check_border_list(struct list_head *head)
76 list_for_each_entry(border_t, x, head, list) {
77 assert(x->magic == BORDER_FOURCC);
81 static void check_heads(be_chordal_env_t *env)
84 for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
85 /* ir_printf("checking border list of block %+F\n", ent->key); */
86 check_border_list(ent->value);
92 * Add an interval border to the list of a block's list
94 * @note You always have to create the use before the def.
95 * @param env The environment.
96 * @param head The list head to enqueue the borders.
97 * @param irn The node (value) the border belongs to.
98 * @param pressure The pressure at this point in time.
99 * @param step A time step for the border.
100 * @param is_def Is the border a use or a def.
101 * @return The created border.
103 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
104 ir_node *irn, unsigned step, unsigned pressure,
105 unsigned is_def, unsigned is_real)
112 b = obstack_alloc(&env->obst, sizeof(*b));
114 /* also allocate the def and tie it to the use. */
115 def = obstack_alloc(&env->obst, sizeof(*def));
116 memset(def, 0, sizeof(*def));
121 * Set the link field of the irn to the def.
122 * This strongly relies on the fact, that the use is always
123 * made before the def.
125 set_irn_link(irn, def);
127 b->magic = BORDER_FOURCC;
128 def->magic = BORDER_FOURCC;
132 * If the def is encountered, the use was made and so was the
133 * the def node (see the code above). It was placed into the
134 * link field of the irn, so we can get it there.
137 b = get_irn_link(irn);
139 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
142 b->pressure = pressure;
144 b->is_real = is_real;
147 list_add_tail(&b->list, head);
148 DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
155 * Check, if an irn is of the register class currently under processing.
156 * @param env The chordal environment.
157 * @param irn The node.
158 * @return 1, if the node is of that register class, 0 if not.
160 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
162 return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
165 #define has_limited_constr(req, irn) \
166 (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
168 static int try_pre_color(be_chordal_env_t *env, ir_node *irn,
169 pset *pre_colored, bitset_t *colors_used)
171 arch_register_req_t req;
173 if(arch_get_register_req(env->main_env->arch_env, &req, irn, -1) && arch_register_req_is(&req, limited)) {
175 bitset_t *bs = bitset_alloca(env->cls->n_regs);
176 const arch_register_t *reg;
179 req.limited(irn, -1, bs);
180 col = bitset_next_set(bs, 0);
181 reg = arch_register_for_index(env->cls, col);
183 pset_insert_ptr(pre_colored, irn);
184 arch_set_irn_register(env->main_env->arch_env, irn, reg);
186 bitset_set(colors_used, col);
188 DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name));
197 * Handle register targeting constraints signaled by a Perm.
198 * @param alloc_env Private data for the allocation phase.
199 * @param perm The Perm node guarding the constrained node.
200 * @return The constrained node.
202 Pro-coloring works as follows:
204 +-----------------------------------+
206 +---.-------.--------.---------.----+
230 1) Look at all Projs of the Perm if they have output constraints.
231 If one has an output constraint, pre-color it, else record it
232 in the set leftover. Its color has to be chosen after all
233 constrained nodes are colored. Furthermore record all colors
234 used in the pre-coloring in the set colors_used.
236 2) Look whether the first node not a Proj (this is the constrained
237 node due to which the Perm has been inserted) has an output
238 constraint. If yes, pre-color the node accordingly else do nothing
239 since the node's input constraints are modelled by the Proj's
242 There's one subtle point here: If thenode has an output constraint
243 and the live range of some Proj ends at that node, we must give
244 that Proj the color of the constrained node. Otherwise the
245 available colors may not suffice for the rest of the projs.
247 3) At last, color the Projs which have not been colored yet with the
250 So afterwards, everything including the constrained node will
251 be colored and the assign() phase can complete this coloring.
252 Note that therefore, we put the pre-colored nodes in a set
253 called pre_colored().
256 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
258 be_chordal_env_t *env = alloc_env->chordal_env;
259 firm_dbg_module_t *dbg = env->dbg;
260 const arch_env_t *arch_env = env->main_env->arch_env;
262 pset *leftover = pset_new_ptr(8);
263 pset *pre_colored = pset_new_ptr(8);
264 bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
265 ir_node *irn, *cnstr, *last;
268 assert(be_is_Perm(perm));
270 DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
273 * Color constrained Projs first.
275 for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn))
276 if(!try_pre_color(env, irn, pre_colored, colors_used))
277 pset_insert_ptr(leftover, irn);
282 if(get_irn_mode(cnstr) == mode_T) {
283 for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn))
284 if(!try_pre_color(env, irn, pre_colored, colors_used))
285 pset_insert_ptr(leftover, irn);
287 last = sched_prev(irn);
291 try_pre_color(env, cnstr, pre_colored, colors_used);
293 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
294 const arch_register_t *reg;
298 for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) {
299 if(!values_interfere(irn, precol)) {
300 reg = arch_get_irn_register(arch_env, irn);
301 arch_set_irn_register(arch_env, irn, reg);
302 pset_break(pre_colored);
309 int col = bitset_next_clear(colors_used, 0);
311 assert(col >=0 && "There must be a register left");
312 reg = arch_register_for_index(env->cls, col);
313 arch_set_irn_register(arch_env, irn, reg);
314 bitset_set(colors_used, reg->index);
315 pset_insert_ptr(alloc_env->pre_colored, irn);
317 DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
321 pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
324 del_pset(pre_colored);
330 * Handle constraint nodes in each basic block.
331 * be_insert_constr_perms() inserts Perm nodes which perm
332 * over all values live at the constrained node right in front
333 * of the constrained node. These Perms signal a constrained node.
334 * For further comments, refer to handle_constraints_at_perm().
336 static void constraints(ir_node *bl, void *data)
338 be_chordal_alloc_env_t *env = data;
339 arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
342 for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
343 if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
344 irn = handle_constraints_at_perm(env, irn);
349 * Annotate the register pressure to the nodes and compute
350 * the liveness intervals.
351 * @param block The block to do it for.
352 * @param env_ptr The environment.
354 static void pressure(ir_node *block, void *env_ptr)
356 /* Convenience macro for a def */
357 #define border_def(irn, step, real) \
358 border_add(env, head, irn, step, pressure--, 1, real)
360 /* Convenience macro for a use */
361 #define border_use(irn, step, real) \
362 border_add(env, head, irn, step, ++pressure, 0, real)
364 be_chordal_alloc_env_t *alloc_env = env_ptr;
365 be_chordal_env_t *env = alloc_env->chordal_env;
366 bitset_t *live = alloc_env->live;
367 firm_dbg_module_t *dbg = env->dbg;
372 unsigned pressure = 0;
373 struct list_head *head;
374 pset *live_in = put_live_in(block, pset_new_ptr_default());
375 pset *live_end = put_live_end(block, pset_new_ptr_default());
377 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
378 bitset_clear_all(live);
380 /* Set up the border list in the block info */
381 head = obstack_alloc(&env->obst, sizeof(*head));
382 INIT_LIST_HEAD(head);
383 assert(pmap_get(env->border_heads, block) == NULL);
384 pmap_insert(env->border_heads, block, head);
387 * Make final uses of all values live out of the block.
388 * They are necessary to build up real intervals.
390 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
391 if(has_reg_class(env, irn)) {
392 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
393 bitset_set(live, get_irn_graph_nr(irn));
394 border_use(irn, step, 0);
400 * Determine the last uses of a value inside the block, since they are
401 * relevant for the interval borders.
403 sched_foreach_reverse(block, irn) {
404 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
405 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
408 * If the node defines some value, which can put into a
409 * register of the current class, make a border for it.
411 if(has_reg_class(env, irn)) {
412 int nr = get_irn_graph_nr(irn);
414 bitset_clear(live, nr);
415 border_def(irn, step, 1);
419 * If the node is no phi node we can examine the uses.
422 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
423 ir_node *op = get_irn_n(irn, i);
425 if(has_reg_class(env, op)) {
426 int nr = get_irn_graph_nr(op);
428 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
430 if(!bitset_is_set(live, nr)) {
431 border_use(op, step, 1);
432 bitset_set(live, nr);
441 * Add initial defs for all values live in.
443 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
444 if(has_reg_class(env, irn)) {
446 /* Mark the value live in. */
447 bitset_set(live, get_irn_graph_nr(irn));
450 border_def(irn, step, 0);
459 static void assign(ir_node *block, void *env_ptr)
461 be_chordal_alloc_env_t *alloc_env = env_ptr;
462 be_chordal_env_t *env = alloc_env->chordal_env;
463 firm_dbg_module_t *dbg = env->dbg;
464 bitset_t *live = alloc_env->live;
465 bitset_t *colors = alloc_env->colors;
466 bitset_t *in_colors = alloc_env->in_colors;
467 const arch_env_t *arch_env = env->main_env->arch_env;
471 struct list_head *head = get_block_border_head(env, block);
472 pset *live_in = put_live_in(block, pset_new_ptr_default());
474 bitset_clear_all(live);
475 bitset_clear_all(colors);
476 bitset_clear_all(in_colors);
478 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
479 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
480 list_for_each_entry(border_t, b, head, list) {
481 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
482 b->irn, get_irn_graph_nr(b->irn)));
486 * Add initial defs for all values live in.
487 * Since their colors have already been assigned (The dominators were
488 * allocated before), we have to mark their colors as used also.
490 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
491 if(has_reg_class(env, irn)) {
492 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
495 assert(reg && "Node must have been assigned a register");
496 col = arch_register_get_index(reg);
498 /* Mark the color of the live in value as used. */
499 bitset_set(colors, col);
500 bitset_set(in_colors, col);
502 /* Mark the value live in. */
503 bitset_set(live, get_irn_graph_nr(irn));
508 * Mind that the sequence of defs from back to front defines a perfect
509 * elimination order. So, coloring the definitions from first to last
512 list_for_each_entry_reverse(border_t, b, head, list) {
513 ir_node *irn = b->irn;
514 int nr = get_irn_graph_nr(irn);
517 * Assign a color, if it is a local def. Global defs already have a
520 if(b->is_def && !is_live_in(block, irn)) {
521 const arch_register_t *reg;
524 DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
526 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
527 reg = arch_get_irn_register(arch_env, irn);
529 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
533 col = bitset_next_clear(colors, 0);
534 reg = arch_register_for_index(env->cls, col);
535 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
538 bitset_set(colors, col);
539 arch_set_irn_register(arch_env, irn, reg);
541 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
542 arch_register_get_name(reg), col, irn));
544 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
545 bitset_set(live, nr);
548 /* Clear the color upon a use. */
549 else if(!b->is_def) {
550 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
553 assert(reg && "Register must have been assigned");
555 col = arch_register_get_index(reg);
556 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
558 bitset_clear(colors, col);
559 bitset_clear(live, nr);
566 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
568 int node_count = get_graph_node_count(chordal_env->irg);
569 int colors_n = arch_register_class_n_regs(chordal_env->cls);
570 ir_graph *irg = chordal_env->irg;
572 be_chordal_alloc_env_t env;
574 if(get_irg_dom_state(irg) != dom_consistent)
577 env.chordal_env = chordal_env;
578 env.live = bitset_malloc(node_count);
579 env.colors = bitset_malloc(colors_n);
580 env.in_colors = bitset_malloc(colors_n);
581 env.colors_n = colors_n;
582 env.pre_colored = pset_new_ptr_default();
584 /* Handle register targeting constraints */
585 dom_tree_walk_irg(irg, constraints, NULL, &env);
587 /* First, determine the pressure */
588 dom_tree_walk_irg(irg, pressure, NULL, &env);
590 /* Assign the colors */
591 dom_tree_walk_irg(irg, assign, NULL, &env);
593 #ifdef DUMP_INTERVALS
598 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
599 plotter = new_plotter_ps(buf);
601 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter, env->arch_env, cls);
602 plotter_free(plotter);
610 del_pset(env.pre_colored);