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)
174 && req.type == arch_register_req_type_limited) {
176 bitset_t *bs = bitset_alloca(env->cls->n_regs);
177 const arch_register_t *reg;
180 req.data.limited(irn, -1, bs);
181 col = bitset_next_set(bs, 0);
182 reg = arch_register_for_index(env->cls, col);
184 pset_insert_ptr(pre_colored, irn);
185 arch_set_irn_register(env->main_env->arch_env, irn, reg);
187 bitset_set(colors_used, col);
189 DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name));
198 * Handle register targeting constraints signaled by a Perm.
199 * @param alloc_env Private data for the allocation phase.
200 * @param perm The Perm node guarding the constrained node.
201 * @return The constrained node.
203 Pro-coloring works as follows:
205 +-----------------------------------+
207 +---.-------.--------.---------.----+
231 1) Look at all Projs of the Perm if they have output constraints.
232 If one has an output constraint, pre-color it, else record it
233 in the set leftover. Its color has to be chosen after all
234 constrained nodes are colored. Furthermore record all colors
235 used in the pre-coloring in the set colors_used.
237 2) Look whether the first node not a Proj (this is the constrained
238 node due to which the Perm has been inserted) has an output
239 constraint. If yes, pre-color the node accordingly else do nothing
240 since the node's input constraints are modelled by the Proj's
243 There's one subtle point here: If thenode has an output constraint
244 and the live range of some Proj ends at that node, we must give
245 that Proj the color of the constrained node. Otherwise the
246 available colors may not suffice for the rest of the projs.
248 3) At last, color the Projs which have not been colored yet with the
251 So afterwards, everything including the constrained node will
252 be colored and the assign() phase can complete this coloring.
253 Note that therefore, we put the pre-colored nodes in a set
254 called pre_colored().
257 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
259 be_chordal_env_t *env = alloc_env->chordal_env;
260 firm_dbg_module_t *dbg = env->dbg;
261 const arch_env_t *arch_env = env->main_env->arch_env;
263 pset *leftover = pset_new_ptr(8);
264 pset *pre_colored = pset_new_ptr(8);
265 bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
266 ir_node *irn, *cnstr, *last;
269 assert(be_is_Perm(perm));
271 DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
274 * Color constrained Projs first.
276 for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn))
277 if(!try_pre_color(env, irn, pre_colored, colors_used))
278 pset_insert_ptr(leftover, irn);
283 if(get_irn_mode(cnstr) == mode_T) {
284 for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn))
285 if(!try_pre_color(env, irn, pre_colored, colors_used))
286 pset_insert_ptr(leftover, irn);
288 last = sched_prev(irn);
292 try_pre_color(env, cnstr, pre_colored, colors_used);
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 if(!values_interfere(irn, precol)) {
301 reg = arch_get_irn_register(arch_env, irn);
302 arch_set_irn_register(arch_env, irn, reg);
303 pset_break(pre_colored);
310 int col = bitset_next_clear(colors_used, 0);
312 assert(col >=0 && "There must be a register left");
313 reg = arch_register_for_index(env->cls, col);
314 arch_set_irn_register(arch_env, irn, reg);
315 bitset_set(colors_used, reg->index);
316 pset_insert_ptr(alloc_env->pre_colored, irn);
318 DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
322 pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
325 del_pset(pre_colored);
331 * Handle constraint nodes in each basic block.
332 * be_insert_constr_perms() inserts Perm nodes which perm
333 * over all values live at the constrained node right in front
334 * of the constrained node. These Perms signal a constrained node.
335 * For further comments, refer to handle_constraints_at_perm().
337 static void constraints(ir_node *bl, void *data)
339 be_chordal_alloc_env_t *env = data;
340 arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
343 for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
344 if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
345 irn = handle_constraints_at_perm(env, irn);
350 * Annotate the register pressure to the nodes and compute
351 * the liveness intervals.
352 * @param block The block to do it for.
353 * @param env_ptr The environment.
355 static void pressure(ir_node *block, void *env_ptr)
357 /* Convenience macro for a def */
358 #define border_def(irn, step, real) \
359 border_add(env, head, irn, step, pressure--, 1, real)
361 /* Convenience macro for a use */
362 #define border_use(irn, step, real) \
363 border_add(env, head, irn, step, ++pressure, 0, real)
365 be_chordal_alloc_env_t *alloc_env = env_ptr;
366 be_chordal_env_t *env = alloc_env->chordal_env;
367 bitset_t *live = alloc_env->live;
368 firm_dbg_module_t *dbg = env->dbg;
373 unsigned pressure = 0;
374 struct list_head *head;
375 pset *live_in = put_live_in(block, pset_new_ptr_default());
376 pset *live_end = put_live_end(block, pset_new_ptr_default());
378 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
379 bitset_clear_all(live);
381 /* Set up the border list in the block info */
382 head = obstack_alloc(&env->obst, sizeof(*head));
383 INIT_LIST_HEAD(head);
384 assert(pmap_get(env->border_heads, block) == NULL);
385 pmap_insert(env->border_heads, block, head);
388 * Make final uses of all values live out of the block.
389 * They are necessary to build up real intervals.
391 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
392 if(has_reg_class(env, irn)) {
393 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
394 bitset_set(live, get_irn_graph_nr(irn));
395 border_use(irn, step, 0);
401 * Determine the last uses of a value inside the block, since they are
402 * relevant for the interval borders.
404 sched_foreach_reverse(block, irn) {
405 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
406 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
409 * If the node defines some value, which can put into a
410 * register of the current class, make a border for it.
412 if(has_reg_class(env, irn)) {
413 int nr = get_irn_graph_nr(irn);
415 bitset_clear(live, nr);
416 border_def(irn, step, 1);
420 * If the node is no phi node we can examine the uses.
423 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
424 ir_node *op = get_irn_n(irn, i);
426 if(has_reg_class(env, op)) {
427 int nr = get_irn_graph_nr(op);
429 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
431 if(!bitset_is_set(live, nr)) {
432 border_use(op, step, 1);
433 bitset_set(live, nr);
442 * Add initial defs for all values live in.
444 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
445 if(has_reg_class(env, irn)) {
447 /* Mark the value live in. */
448 bitset_set(live, get_irn_graph_nr(irn));
451 border_def(irn, step, 0);
460 static void assign(ir_node *block, void *env_ptr)
462 be_chordal_alloc_env_t *alloc_env = env_ptr;
463 be_chordal_env_t *env = alloc_env->chordal_env;
464 firm_dbg_module_t *dbg = env->dbg;
465 bitset_t *live = alloc_env->live;
466 bitset_t *colors = alloc_env->colors;
467 bitset_t *in_colors = alloc_env->in_colors;
468 const arch_env_t *arch_env = env->main_env->arch_env;
472 struct list_head *head = get_block_border_head(env, block);
473 pset *live_in = put_live_in(block, pset_new_ptr_default());
475 bitset_clear_all(live);
476 bitset_clear_all(colors);
477 bitset_clear_all(in_colors);
479 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
480 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
481 list_for_each_entry(border_t, b, head, list) {
482 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
483 b->irn, get_irn_graph_nr(b->irn)));
487 * Add initial defs for all values live in.
488 * Since their colors have already been assigned (The dominators were
489 * allocated before), we have to mark their colors as used also.
491 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
492 if(has_reg_class(env, irn)) {
493 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
496 assert(reg && "Node must have been assigned a register");
497 col = arch_register_get_index(reg);
499 /* Mark the color of the live in value as used. */
500 bitset_set(colors, col);
501 bitset_set(in_colors, col);
503 /* Mark the value live in. */
504 bitset_set(live, get_irn_graph_nr(irn));
509 * Mind that the sequence of defs from back to front defines a perfect
510 * elimination order. So, coloring the definitions from first to last
513 list_for_each_entry_reverse(border_t, b, head, list) {
514 ir_node *irn = b->irn;
515 int nr = get_irn_graph_nr(irn);
518 * Assign a color, if it is a local def. Global defs already have a
521 if(b->is_def && !is_live_in(block, irn)) {
522 const arch_register_t *reg;
525 DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
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", cls->name, irg);
600 plotter = new_plotter_ps(buf);
602 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter, env->arch_env, cls);
603 plotter_free(plotter);
611 del_pset(env.pre_colored);