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)
169 * Handle register targeting constraints signaled by a Perm.
170 * @param alloc_env Private data for the allocation phase.
171 * @param perm The Perm node guarding the constrained node.
172 * @return The constrained node.
174 Pro-coloring works as follows:
176 +-----------------------------------+
178 +---.-------.--------.---------.----+
202 1) Look at all Projs of the Perm if they have output constraints.
203 If one has an output constraint, pre-color it, else record it
204 in the set leftover. Its color has to be chosen after all
205 constrained nodes are colored. Furthermore record all colors
206 used in the pre-coloring in the set colors_used.
208 2) Look whether the first node not a Proj (this is the constrained
209 node due to which the Perm has been inserted) has an output
210 constraint. If yes, pre-color the node accordingly else do nothing
211 since the node's input constraints are modelled by the Proj's
214 There's one subtle point here: If thenode has an output constraint
215 and the live range of some Proj ends at that node, we must give
216 that Proj the color of the constrained node. Otherwise the
217 available colors may not suffice for the rest of the projs.
219 3) At last, color the Projs which have not been colored yet with the
222 So afterwards, everything including the constrained node will
223 be colored and the assign() phase can complete this coloring.
224 Note that therefore, we put the pre-colored nodes in a set
225 called pre_colored().
228 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
230 be_chordal_env_t *env = alloc_env->chordal_env;
231 firm_dbg_module_t *dbg = env->dbg;
232 const arch_env_t *arch_env = env->main_env->arch_env;
234 pset *leftover = pset_new_ptr(8);
235 bitset_t *bs = bitset_alloca(env->cls->n_regs);
236 bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
237 ir_node *irn, *cnstr;
240 arch_register_req_t req;
241 const arch_register_t *reg, *cnstr_reg = NULL;
243 assert(be_is_Perm(perm));
245 DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
248 * Color constrained Projs first.
250 for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn)) {
251 arch_register_req_t req;
253 if(has_limited_constr(&req, irn)) {
254 bitset_clear_all(bs);
255 req.data.limited(irn, -1, bs);
256 col = bitset_next_set(bs, 0);
257 reg = arch_register_for_index(env->cls, col);
259 pset_insert_ptr(alloc_env->pre_colored, irn);
260 arch_set_irn_register(arch_env, irn, reg);
261 bitset_set(colors_used, col);
263 DBG((dbg, LEVEL_2, "\tPerm Proj with constraints: %+F set to %s\n", irn, reg->name));
267 pset_insert_ptr(leftover, irn);
272 if(has_limited_constr(&req, cnstr)) {
273 bitset_clear_all(bs);
274 req.data.limited(cnstr, -1, bs);
275 col = bitset_next_set(colors_used, 0);
276 reg = arch_register_for_index(env->cls, col);
278 arch_set_irn_register(arch_env, cnstr, reg);
279 pset_insert_ptr(alloc_env->pre_colored, cnstr);
281 DBG((dbg, LEVEL_2, "\tConstrained node: %+F set to %s\n", irn, reg->name));
284 * The color of the constrained node must not be used!
285 * The Proj which has been assigned that color might
286 * interfere with the constrained node which leads
287 * to an invalid register allocation.
289 assert(!bitset_is_set(colors_used, reg->index));
292 * Look for a Proj not interfering with the constrained node.
293 * This Proj can be safely set to the constrafined nodes
296 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
297 if(!values_interfere(irn, cnstr)) {
299 DBG((dbg, LEVEL_2, "\tFound Proj not interfering with contr node %+F set to %s\n", irn, reg->name));
300 pset_insert_ptr(alloc_env->pre_colored, irn);
301 arch_set_irn_register(arch_env, irn, reg);
302 bitset_set(colors_used, reg->index);
303 pset_remove_ptr(leftover, irn);
304 pset_break(leftover);
311 * Color the leftover Projs with the leftover colors.
313 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
314 col = bitset_next_clear(colors_used, 0);
315 reg = arch_register_for_index(env->cls, col);
317 arch_set_irn_register(arch_env, irn, reg);
318 pset_insert_ptr(alloc_env->pre_colored, irn);
319 bitset_set(colors_used, col);
321 DBG((dbg, LEVEL_2, "\tLeft over %+F set to %s\n", irn, reg->name));
329 * Handle constraint nodes in each basic block.
330 * be_insert_constr_perms() inserts Perm nodes which perm
331 * over all values live at the constrained node right in front
332 * of the constrained node. These Perms signal a constrained node.
333 * For further comments, refer to handle_constraints_at_perm().
335 static void constraints(ir_node *bl, void *data)
337 be_chordal_alloc_env_t *env = data;
338 arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
341 for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
343 irn = handle_constraints_at_perm(env, irn);
348 * Annotate the register pressure to the nodes and compute
349 * the liveness intervals.
350 * @param block The block to do it for.
351 * @param env_ptr The environment.
353 static void pressure(ir_node *block, void *env_ptr)
355 /* Convenience macro for a def */
356 #define border_def(irn, step, real) \
357 border_add(env, head, irn, step, pressure--, 1, real)
359 /* Convenience macro for a use */
360 #define border_use(irn, step, real) \
361 border_add(env, head, irn, step, ++pressure, 0, real)
363 be_chordal_alloc_env_t *alloc_env = env_ptr;
364 be_chordal_env_t *env = alloc_env->chordal_env;
365 bitset_t *live = alloc_env->live;
366 firm_dbg_module_t *dbg = env->dbg;
371 unsigned pressure = 0;
372 struct list_head *head;
373 pset *live_in = put_live_in(block, pset_new_ptr_default());
374 pset *live_end = put_live_end(block, pset_new_ptr_default());
376 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
377 bitset_clear_all(live);
379 /* Set up the border list in the block info */
380 head = obstack_alloc(&env->obst, sizeof(*head));
381 INIT_LIST_HEAD(head);
382 assert(pmap_get(env->border_heads, block) == NULL);
383 pmap_insert(env->border_heads, block, head);
386 * Make final uses of all values live out of the block.
387 * They are necessary to build up real intervals.
389 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
390 if(has_reg_class(env, irn)) {
391 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
392 bitset_set(live, get_irn_graph_nr(irn));
393 border_use(irn, step, 0);
399 * Determine the last uses of a value inside the block, since they are
400 * relevant for the interval borders.
402 sched_foreach_reverse(block, irn) {
403 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
404 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
407 * If the node defines some value, which can put into a
408 * register of the current class, make a border for it.
410 if(has_reg_class(env, irn)) {
411 int nr = get_irn_graph_nr(irn);
413 bitset_clear(live, nr);
414 border_def(irn, step, 1);
418 * If the node is no phi node we can examine the uses.
421 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
422 ir_node *op = get_irn_n(irn, i);
424 if(has_reg_class(env, op)) {
425 int nr = get_irn_graph_nr(op);
427 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
429 if(!bitset_is_set(live, nr)) {
430 border_use(op, step, 1);
431 bitset_set(live, nr);
440 * Add initial defs for all values live in.
442 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
443 if(has_reg_class(env, irn)) {
445 /* Mark the value live in. */
446 bitset_set(live, get_irn_graph_nr(irn));
449 border_def(irn, step, 0);
458 static void assign(ir_node *block, void *env_ptr)
460 be_chordal_alloc_env_t *alloc_env = env_ptr;
461 be_chordal_env_t *env = alloc_env->chordal_env;
462 firm_dbg_module_t *dbg = env->dbg;
463 bitset_t *live = alloc_env->live;
464 bitset_t *colors = alloc_env->colors;
465 bitset_t *in_colors = alloc_env->in_colors;
466 const arch_env_t *arch_env = env->main_env->arch_env;
470 struct list_head *head = get_block_border_head(env, block);
471 pset *live_in = put_live_in(block, pset_new_ptr_default());
473 bitset_clear_all(live);
474 bitset_clear_all(colors);
475 bitset_clear_all(in_colors);
477 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
478 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
479 list_for_each_entry(border_t, b, head, list) {
480 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
481 b->irn, get_irn_graph_nr(b->irn)));
485 * Add initial defs for all values live in.
486 * Since their colors have already been assigned (The dominators were
487 * allocated before), we have to mark their colors as used also.
489 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
490 if(has_reg_class(env, irn)) {
491 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
494 assert(reg && "Node must have been assigned a register");
495 col = arch_register_get_index(reg);
497 /* Mark the color of the live in value as used. */
498 bitset_set(colors, col);
499 bitset_set(in_colors, col);
501 /* Mark the value live in. */
502 bitset_set(live, get_irn_graph_nr(irn));
507 * Mind that the sequence of defs from back to front defines a perfect
508 * elimination order. So, coloring the definitions from first to last
511 list_for_each_entry_reverse(border_t, b, head, list) {
512 ir_node *irn = b->irn;
513 int nr = get_irn_graph_nr(irn);
516 * Assign a color, if it is a local def. Global defs already have a
519 if(b->is_def && !is_live_in(block, irn)) {
520 const arch_register_t *reg;
523 DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
525 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
526 reg = arch_get_irn_register(arch_env, irn);
528 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
532 col = bitset_next_clear(colors, 0);
533 reg = arch_register_for_index(env->cls, col);
534 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
537 bitset_set(colors, col);
538 arch_set_irn_register(arch_env, irn, reg);
540 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
541 arch_register_get_name(reg), col, irn));
543 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
544 bitset_set(live, nr);
547 /* Clear the color upon a use. */
548 else if(!b->is_def) {
549 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
552 assert(reg && "Register must have been assigned");
554 col = arch_register_get_index(reg);
555 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
557 bitset_clear(colors, col);
558 bitset_clear(live, nr);
565 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
567 int node_count = get_graph_node_count(chordal_env->irg);
568 int colors_n = arch_register_class_n_regs(chordal_env->cls);
569 ir_graph *irg = chordal_env->irg;
571 be_chordal_alloc_env_t env;
573 if(get_irg_dom_state(irg) != dom_consistent)
576 env.chordal_env = chordal_env;
577 env.live = bitset_malloc(node_count);
578 env.colors = bitset_malloc(colors_n);
579 env.in_colors = bitset_malloc(colors_n);
580 env.colors_n = colors_n;
581 env.pre_colored = pset_new_ptr_default();
583 /* Handle register targeting constraints */
584 dom_tree_walk_irg(irg, constraints, NULL, &env);
586 /* First, determine the pressure */
587 dom_tree_walk_irg(irg, pressure, NULL, &env);
589 /* Assign the colors */
590 dom_tree_walk_irg(irg, assign, NULL, &env);
592 #ifdef DUMP_INTERVALS
597 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
598 plotter = new_plotter_ps(buf);
600 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter, env->arch_env, cls);
601 plotter_free(plotter);
609 del_pset(env.pre_colored);