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)
174 && req.cls == env->cls
175 && arch_register_req_is(&req, limited)) {
177 bitset_t *bs = bitset_alloca(env->cls->n_regs);
178 const arch_register_t *reg;
181 req.limited(req.limited_env, bs);
182 col = bitset_next_set(bs, 0);
183 reg = arch_register_for_index(env->cls, col);
185 pset_insert_ptr(pre_colored, irn);
186 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 pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
296 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
297 const arch_register_t *reg;
301 for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) {
302 const arch_register_t *pre_col_reg = arch_get_irn_register(arch_env, precol);
304 if(!values_interfere(irn, precol)) {
305 reg = arch_get_irn_register(arch_env, precol);
306 pset_break(pre_colored);
307 pset_remove_ptr(pre_colored, precol);
308 DBG((dbg, LEVEL_2, "non-interfering %+F setting to %s\n", irn, reg->name));
315 int col = bitset_next_clear(colors_used, 0);
317 assert(col >= 0 && col < env->cls->n_regs && "There must be a register left");
318 reg = arch_register_for_index(env->cls, col);
320 DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
323 arch_set_irn_register(arch_env, irn, reg);
324 pset_insert_ptr(alloc_env->pre_colored, irn);
325 bitset_set(colors_used, reg->index);
329 del_pset(pre_colored);
335 * Handle constraint nodes in each basic block.
336 * be_insert_constr_perms() inserts Perm nodes which perm
337 * over all values live at the constrained node right in front
338 * of the constrained node. These Perms signal a constrained node.
339 * For further comments, refer to handle_constraints_at_perm().
341 static void constraints(ir_node *bl, void *data)
343 be_chordal_alloc_env_t *env = data;
344 arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
347 for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
348 if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
349 irn = handle_constraints_at_perm(env, irn);
354 * Annotate the register pressure to the nodes and compute
355 * the liveness intervals.
356 * @param block The block to do it for.
357 * @param env_ptr The environment.
359 static void pressure(ir_node *block, void *env_ptr)
361 /* Convenience macro for a def */
362 #define border_def(irn, step, real) \
363 border_add(env, head, irn, step, pressure--, 1, real)
365 /* Convenience macro for a use */
366 #define border_use(irn, step, real) \
367 border_add(env, head, irn, step, ++pressure, 0, real)
369 be_chordal_alloc_env_t *alloc_env = env_ptr;
370 be_chordal_env_t *env = alloc_env->chordal_env;
371 bitset_t *live = alloc_env->live;
372 firm_dbg_module_t *dbg = env->dbg;
377 unsigned pressure = 0;
378 struct list_head *head;
379 pset *live_in = put_live_in(block, pset_new_ptr_default());
380 pset *live_end = put_live_end(block, pset_new_ptr_default());
382 DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
383 bitset_clear_all(live);
385 /* Set up the border list in the block info */
386 head = obstack_alloc(&env->obst, sizeof(*head));
387 INIT_LIST_HEAD(head);
388 assert(pmap_get(env->border_heads, block) == NULL);
389 pmap_insert(env->border_heads, block, head);
392 * Make final uses of all values live out of the block.
393 * They are necessary to build up real intervals.
395 for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
396 if(has_reg_class(env, irn)) {
397 DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
398 bitset_set(live, get_irn_graph_nr(irn));
399 border_use(irn, step, 0);
405 * Determine the last uses of a value inside the block, since they are
406 * relevant for the interval borders.
408 sched_foreach_reverse(block, irn) {
409 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
410 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
413 * If the node defines some value, which can put into a
414 * register of the current class, make a border for it.
416 if(has_reg_class(env, irn)) {
417 int nr = get_irn_graph_nr(irn);
419 bitset_clear(live, nr);
420 border_def(irn, step, 1);
424 * If the node is no phi node we can examine the uses.
427 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
428 ir_node *op = get_irn_n(irn, i);
430 if(has_reg_class(env, op)) {
431 int nr = get_irn_graph_nr(op);
433 DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
435 if(!bitset_is_set(live, nr)) {
436 border_use(op, step, 1);
437 bitset_set(live, nr);
446 * Add initial defs for all values live in.
448 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
449 if(has_reg_class(env, irn)) {
451 /* Mark the value live in. */
452 bitset_set(live, get_irn_graph_nr(irn));
455 border_def(irn, step, 0);
464 static void assign(ir_node *block, void *env_ptr)
466 be_chordal_alloc_env_t *alloc_env = env_ptr;
467 be_chordal_env_t *env = alloc_env->chordal_env;
468 firm_dbg_module_t *dbg = env->dbg;
469 bitset_t *live = alloc_env->live;
470 bitset_t *colors = alloc_env->colors;
471 bitset_t *in_colors = alloc_env->in_colors;
472 const arch_env_t *arch_env = env->main_env->arch_env;
476 struct list_head *head = get_block_border_head(env, block);
477 pset *live_in = put_live_in(block, pset_new_ptr_default());
479 bitset_clear_all(live);
480 bitset_clear_all(colors);
481 bitset_clear_all(in_colors);
483 DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
484 DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
485 list_for_each_entry(border_t, b, head, list) {
486 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
487 b->irn, get_irn_graph_nr(b->irn)));
491 * Add initial defs for all values live in.
492 * Since their colors have already been assigned (The dominators were
493 * allocated before), we have to mark their colors as used also.
495 for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
496 if(has_reg_class(env, irn)) {
497 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
500 assert(reg && "Node must have been assigned a register");
501 col = arch_register_get_index(reg);
503 /* Mark the color of the live in value as used. */
504 bitset_set(colors, col);
505 bitset_set(in_colors, col);
507 /* Mark the value live in. */
508 bitset_set(live, get_irn_graph_nr(irn));
513 * Mind that the sequence of defs from back to front defines a perfect
514 * elimination order. So, coloring the definitions from first to last
517 list_for_each_entry_reverse(border_t, b, head, list) {
518 ir_node *irn = b->irn;
519 int nr = get_irn_graph_nr(irn);
522 * Assign a color, if it is a local def. Global defs already have a
525 if(b->is_def && !is_live_in(block, irn)) {
526 const arch_register_t *reg;
529 if(pset_find_ptr(alloc_env->pre_colored, irn)) {
530 reg = arch_get_irn_register(arch_env, irn);
532 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
536 col = bitset_next_clear(colors, 0);
537 reg = arch_register_for_index(env->cls, col);
538 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
541 bitset_set(colors, col);
542 arch_set_irn_register(arch_env, irn, reg);
544 DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
545 arch_register_get_name(reg), col, irn));
547 assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
548 bitset_set(live, nr);
551 /* Clear the color upon a use. */
552 else if(!b->is_def) {
553 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
556 assert(reg && "Register must have been assigned");
558 col = arch_register_get_index(reg);
559 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
561 bitset_clear(colors, col);
562 bitset_clear(live, nr);
569 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
571 int node_count = get_graph_node_count(chordal_env->irg);
572 int colors_n = arch_register_class_n_regs(chordal_env->cls);
573 ir_graph *irg = chordal_env->irg;
575 be_chordal_alloc_env_t env;
577 if(get_irg_dom_state(irg) != dom_consistent)
580 env.chordal_env = chordal_env;
581 env.live = bitset_malloc(node_count);
582 env.colors = bitset_malloc(colors_n);
583 env.in_colors = bitset_malloc(colors_n);
584 env.colors_n = colors_n;
585 env.pre_colored = pset_new_ptr_default();
587 /* Handle register targeting constraints */
588 dom_tree_walk_irg(irg, constraints, NULL, &env);
590 /* First, determine the pressure */
591 dom_tree_walk_irg(irg, pressure, NULL, &env);
593 /* Assign the colors */
594 dom_tree_walk_irg(irg, assign, NULL, &env);
596 #ifdef DUMP_INTERVALS
601 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
602 plotter = new_plotter_ps(buf);
604 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
605 plotter_free(plotter);
613 del_pset(env.pre_colored);