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
56 #define DUMP_INTERVALS
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);
185 bitset_set(colors_used, col);
187 DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name));
196 * Handle register targeting constraints signaled by a Perm.
197 * @param alloc_env Private data for the allocation phase.
198 * @param perm The Perm node guarding the constrained node.
199 * @return The constrained node.
201 Pro-coloring works as follows:
203 +-----------------------------------+
205 +---.-------.--------.---------.----+
229 1) Look at all Projs of the Perm if they have output constraints.
230 If one has an output constraint, pre-color it, else record it
231 in the set leftover. Its color has to be chosen after all
232 constrained nodes are colored. Furthermore record all colors
233 used in the pre-coloring in the set colors_used.
235 2) Look whether the first node not a Proj (this is the constrained
236 node due to which the Perm has been inserted) has an output
237 constraint. If yes, pre-color the node accordingly else do nothing
238 since the node's input constraints are modelled by the Proj's
241 There's one subtle point here: If thenode has an output constraint
242 and the live range of some Proj ends at that node, we must give
243 that Proj the color of the constrained node. Otherwise the
244 available colors may not suffice for the rest of the projs.
246 3) At last, color the Projs which have not been colored yet with the
249 So afterwards, everything including the constrained node will
250 be colored and the assign() phase can complete this coloring.
251 Note that therefore, we put the pre-colored nodes in a set
252 called pre_colored().
255 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
257 be_chordal_env_t *env = alloc_env->chordal_env;
258 firm_dbg_module_t *dbg = env->dbg;
259 const arch_env_t *arch_env = env->main_env->arch_env;
261 pset *leftover = pset_new_ptr(8);
262 pset *pre_colored = pset_new_ptr(8);
263 bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
264 ir_node *irn, *cnstr, *last;
267 assert(be_is_Perm(perm));
269 DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
272 * Color constrained Projs first.
274 for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn))
275 if(!try_pre_color(env, irn, pre_colored, colors_used))
276 pset_insert_ptr(leftover, irn);
281 if(get_irn_mode(cnstr) == mode_T) {
282 for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn))
283 if(!try_pre_color(env, irn, pre_colored, colors_used))
284 pset_insert_ptr(leftover, irn);
286 last = sched_prev(irn);
290 try_pre_color(env, cnstr, pre_colored, colors_used);
292 pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
294 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
295 const arch_register_t *reg;
299 for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) {
300 const arch_register_t *pre_col_reg = arch_get_irn_register(arch_env, precol);
302 if(!values_interfere(irn, precol)) {
303 reg = arch_get_irn_register(arch_env, precol);
304 pset_break(pre_colored);
305 pset_remove_ptr(pre_colored, precol);
306 DBG((dbg, LEVEL_2, "non-interfering %+F setting to %s\n", irn, reg->name));
313 int col = bitset_next_clear(colors_used, 0);
315 assert(col >= 0 && col < env->cls->n_regs && "There must be a register left");
316 reg = arch_register_for_index(env->cls, col);
318 DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
321 arch_set_irn_register(arch_env, irn, reg);
322 pset_insert_ptr(alloc_env->pre_colored, irn);
323 bitset_set(colors_used, reg->index);
327 del_pset(pre_colored);
333 * Handle constraint nodes in each basic block.
334 * be_insert_constr_perms() inserts Perm nodes which perm
335 * over all values live at the constrained node right in front
336 * of the constrained node. These Perms signal a constrained node.
337 * For further comments, refer to handle_constraints_at_perm().
339 static void constraints(ir_node *bl, void *data)
341 be_chordal_alloc_env_t *env = data;
342 arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
345 for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
346 if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
347 irn = handle_constraints_at_perm(env, irn);
352 * Annotate the register pressure to the nodes and compute
353 * the liveness intervals.
354 * @param block The block to do it for.
355 * @param env_ptr The environment.
357 static void pressure(ir_node *block, void *env_ptr)
359 /* Convenience macro for a def */
360 #define border_def(irn, step, real) \
361 border_add(env, head, irn, step, pressure--, 1, real)
363 /* Convenience macro for a use */
364 #define border_use(irn, step, real) \
365 border_add(env, head, irn, step, ++pressure, 0, real)
367 be_chordal_alloc_env_t *alloc_env = env_ptr;
368 be_chordal_env_t *env = alloc_env->chordal_env;
369 bitset_t *live = alloc_env->live;
370 firm_dbg_module_t *dbg = env->dbg;
375 unsigned pressure = 0;
376 struct list_head *head;
377 pset *live_in = put_live_in(block, pset_new_ptr_default());
378 pset *live_end = put_live_end(block, pset_new_ptr_default());
380 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
381 bitset_clear_all(live);
383 /* Set up the border list in the block info */
384 head = obstack_alloc(&env->obst, sizeof(*head));
385 INIT_LIST_HEAD(head);
386 assert(pmap_get(env->border_heads, block) == NULL);
387 pmap_insert(env->border_heads, block, head);
390 * Make final uses of all values live out of the block.
391 * They are necessary to build up real intervals.
393 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
394 if(has_reg_class(env, irn)) {
395 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
396 bitset_set(live, get_irn_graph_nr(irn));
397 border_use(irn, step, 0);
403 * Determine the last uses of a value inside the block, since they are
404 * relevant for the interval borders.
406 sched_foreach_reverse(block, irn) {
407 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
408 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
411 * If the node defines some value, which can put into a
412 * register of the current class, make a border for it.
414 if(has_reg_class(env, irn)) {
415 int nr = get_irn_graph_nr(irn);
417 bitset_clear(live, nr);
418 border_def(irn, step, 1);
422 * If the node is no phi node we can examine the uses.
425 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
426 ir_node *op = get_irn_n(irn, i);
428 if(has_reg_class(env, op)) {
429 int nr = get_irn_graph_nr(op);
431 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
433 if(!bitset_is_set(live, nr)) {
434 border_use(op, step, 1);
435 bitset_set(live, nr);
444 * Add initial defs for all values live in.
446 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
447 if(has_reg_class(env, irn)) {
449 /* Mark the value live in. */
450 bitset_set(live, get_irn_graph_nr(irn));
453 border_def(irn, step, 0);
462 static void assign(ir_node *block, void *env_ptr)
464 be_chordal_alloc_env_t *alloc_env = env_ptr;
465 be_chordal_env_t *env = alloc_env->chordal_env;
466 firm_dbg_module_t *dbg = env->dbg;
467 bitset_t *live = alloc_env->live;
468 bitset_t *colors = alloc_env->colors;
469 bitset_t *in_colors = alloc_env->in_colors;
470 const arch_env_t *arch_env = env->main_env->arch_env;
474 struct list_head *head = get_block_border_head(env, block);
475 pset *live_in = put_live_in(block, pset_new_ptr_default());
477 bitset_clear_all(live);
478 bitset_clear_all(colors);
479 bitset_clear_all(in_colors);
481 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
482 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
483 list_for_each_entry(border_t, b, head, list) {
484 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
485 b->irn, get_irn_graph_nr(b->irn)));
489 * Add initial defs for all values live in.
490 * Since their colors have already been assigned (The dominators were
491 * allocated before), we have to mark their colors as used also.
493 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
494 if(has_reg_class(env, irn)) {
495 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
498 assert(reg && "Node must have been assigned a register");
499 col = arch_register_get_index(reg);
501 /* Mark the color of the live in value as used. */
502 bitset_set(colors, col);
503 bitset_set(in_colors, col);
505 /* Mark the value live in. */
506 bitset_set(live, get_irn_graph_nr(irn));
511 * Mind that the sequence of defs from back to front defines a perfect
512 * elimination order. So, coloring the definitions from first to last
515 list_for_each_entry_reverse(border_t, b, head, list) {
516 ir_node *irn = b->irn;
517 int nr = get_irn_graph_nr(irn);
520 * Assign a color, if it is a local def. Global defs already have a
523 if(b->is_def && !is_live_in(block, irn)) {
524 const arch_register_t *reg;
527 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
528 reg = arch_get_irn_register(arch_env, irn);
530 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
534 col = bitset_next_clear(colors, 0);
535 reg = arch_register_for_index(env->cls, col);
536 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
539 bitset_set(colors, col);
540 arch_set_irn_register(arch_env, irn, reg);
542 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
543 arch_register_get_name(reg), col, irn));
545 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
546 bitset_set(live, nr);
549 /* Clear the color upon a use. */
550 else if(!b->is_def) {
551 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
554 assert(reg && "Register must have been assigned");
556 col = arch_register_get_index(reg);
557 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
559 bitset_clear(colors, col);
560 bitset_clear(live, nr);
567 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
569 int node_count = get_graph_node_count(chordal_env->irg);
570 int colors_n = arch_register_class_n_regs(chordal_env->cls);
571 ir_graph *irg = chordal_env->irg;
573 be_chordal_alloc_env_t env;
575 if(get_irg_dom_state(irg) != dom_consistent)
578 env.chordal_env = chordal_env;
579 env.live = bitset_malloc(node_count);
580 env.colors = bitset_malloc(colors_n);
581 env.in_colors = bitset_malloc(colors_n);
582 env.colors_n = colors_n;
583 env.pre_colored = pset_new_ptr_default();
585 /* Handle register targeting constraints */
586 dom_tree_walk_irg(irg, constraints, NULL, &env);
588 /* First, determine the pressure */
589 dom_tree_walk_irg(irg, pressure, NULL, &env);
591 /* Assign the colors */
592 dom_tree_walk_irg(irg, assign, NULL, &env);
594 #ifdef DUMP_INTERVALS
599 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
600 plotter = new_plotter_ps(buf);
602 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
603 plotter_free(plotter);
611 del_pset(env.pre_colored);