2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Beladys spillalgorithm version 2.
23 * @author Daniel Grund, Matthias Braun, Sebastian Hack
27 * The main differences to the original Belady are:
28 * - The workset is empty at the start of a block
29 * There is no attempt to fill it with variables which
30 * are not used in the block.
31 * - There is a global pass which tries to use the remaining
32 * capacity of the blocks to let global variables live through
43 #include "irnodeset.h"
45 #include "irprintf_t.h"
51 #include "iredges_t.h"
52 #include "irphase_t.h"
60 #include "bespillbelady.h"
62 #include "besched_t.h"
66 #include "bechordal_t.h"
67 #include "bespilloptions.h"
68 #include "beloopana.h"
79 #define DBG_WORKSET 128
80 #define DBG_GLOBAL 256
83 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
86 * An association between a node and a point in time.
88 typedef struct _loc_t {
89 ir_node *irn; /**< A node. */
90 unsigned time; /**< A use time (see beuses.h). */
91 unsigned version; /**< That is used in the global pass below.
92 For usage see the comments below.
93 In the local belady pass, this is not
97 typedef struct _workset_t {
98 int len; /**< current length */
99 loc_t vals[0]; /**< inlined array of the values/distances in this working set */
102 typedef struct _belady_env_t {
105 const arch_env_t *arch;
106 const arch_register_class_t *cls;
110 ir_node **blocks; /**< Array of all blocks. */
111 int n_blocks; /**< Number of blocks in the graph. */
112 int n_regs; /**< number of regs in this reg-class */
113 workset_t *ws; /**< the main workset used while processing a block. ob-allocated */
114 be_uses_t *uses; /**< env for the next-use magic */
115 ir_node *instr; /**< current instruction */
116 unsigned instr_nr; /**< current instruction number (relative to block start) */
118 spill_env_t *senv; /**< see bespill.h */
122 static int loc_compare(const void *a, const void *b)
126 return (int) p->time - (int) q->time;
129 static INLINE void workset_print(const workset_t *w)
133 for(i = 0; i < w->len; ++i) {
134 ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
139 * Alloc a new workset on obstack @p ob with maximum size @p max
141 static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
143 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
144 res = obstack_alloc(ob, size);
145 memset(res, 0, size);
150 * Alloc a new instance on obstack and make it equal to @param ws
152 static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
154 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
155 res = obstack_alloc(ob, size);
156 memcpy(res, ws, size);
161 * Do NOT alloc anything. Make @param tgt equal to @param src.
162 * returns @param tgt for convenience
164 static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
165 size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]);
166 memcpy(tgt, src, size);
171 * Overwrites the current content array of @param ws with the
172 * @param count locations given at memory @param locs.
173 * Set the length of @param ws to count.
175 static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
176 workset->len = count;
177 memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0]));
181 * Inserts the value @p val into the workset, iff it is not
182 * already contained. The workset must not be full.
184 static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
186 /* check for current regclass */
187 if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) {
188 DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
192 /* check if val is already contained */
193 for(i=0; i<ws->len; ++i)
194 if (ws->vals[i].irn == val)
198 assert(ws->len < env->n_regs && "Workset already full!");
199 ws->vals[ws->len++].irn = val;
203 * Removes all entries from this workset
205 static INLINE void workset_clear(workset_t *ws) {
210 * Removes the value @p val from the workset if present.
212 static INLINE void workset_remove(workset_t *ws, ir_node *val) {
214 for(i=0; i<ws->len; ++i) {
215 if (ws->vals[i].irn == val) {
216 ws->vals[i] = ws->vals[--ws->len];
222 static INLINE int workset_get_index(const workset_t *ws, const ir_node *val) {
224 for(i=0; i<ws->len; ++i) {
225 if (ws->vals[i].irn == val)
233 * Iterates over all values in the working set.
234 * @p ws The workset to iterate
235 * @p v A variable to put the current value in
236 * @p i An integer for internal use
238 #define workset_foreach(ws, v, i) for(i=0; \
239 v=(i < ws->len) ? ws->vals[i].irn : NULL, i < ws->len; \
242 #define workset_set_time(ws, i, t) (ws)->vals[i].time=t
243 #define workset_get_time(ws, i) (ws)->vals[i].time
244 #define workset_set_length(ws, length) (ws)->len = length
245 #define workset_get_length(ws) ((ws)->len)
246 #define workset_get_val(ws, i) ((ws)->vals[i].irn)
247 #define workset_sort(ws) qsort((ws)->vals, (ws)->len, sizeof((ws)->vals[0]), loc_compare);
248 #define workset_contains(ws, n) (workset_get_index(ws, n) >= 0)
250 typedef struct _block_info_t {
253 ir_node *first_non_in; /**< First node in block which is not a phi. */
254 workset_t *ws_start, *ws_end;
257 workset_t *entrance_reg; /**< That set will contain all values
258 transported into the block which
259 are used before they are displaced.
260 That means, we later have to care to
261 bring them into the block in a register
262 or reload them at the entry of the block. */
264 int pressure; /**< The amount of registers which remain free
265 in this block. This capacity can be used to let
266 global variables, transported into other blocks,
267 live through this block. */
269 double exec_freq; /**< The execution frequency of this block. */
272 static INLINE void *new_block_info(belady_env_t *bel, ir_node *bl) {
273 block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res));
274 memset(res, 0, sizeof(res[0]));
277 res->entrance_reg = new_workset(bel, &bel->ob);
278 res->exec_freq = get_block_execfreq(bel->ef, bl);
279 set_irn_link(bl, res);
283 #define get_block_info(block) ((block_info_t *)get_irn_link(block))
284 #define set_block_info(block, info) set_irn_link(block, info)
286 typedef struct _next_use_t {
289 struct _next_use_t *next;
292 static void *next_use_init(ir_phase *phase, ir_node *irn, void *old)
300 static void build_next_uses(block_info_t *bi)
304 phase_init(&bi->next_uses, "next uses", bi->bel->irg, PHASE_DEFAULT_GROWTH, next_use_init, NULL);
305 sched_foreach_reverse(bi->bl, irn) {
306 int i, step = sched_get_time_step(irn);
311 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
312 ir_node *op = get_irn_n(irn, i);
313 next_use_t *curr = phase_get_irn_data(&bi->next_uses, op);
314 next_use_t *use = phase_alloc(&bi->next_uses, sizeof(use[0]));
320 phase_set_irn_data(&bi->next_uses, op, use);
326 * Check, if the value is something that is transported into a block.
327 * That is, the value is live in or defined by a Phi in the block.
328 * @param env The belady environment.
329 * @param bl The block in question.
330 * @param irn The node in question.
331 * @return 1, if node is something transported into @p bl, 0 if not.
333 static INLINE int is_transport_in(belady_env_t *env, const ir_node *bl, const ir_node *irn)
335 return (is_Phi(irn) && get_nodes_block(irn) == bl) || be_is_live_in(env->lv, bl, irn);
339 * Performs the actions necessary to grant the request that:
340 * - new_vals can be held in registers
341 * - as few as possible other values are disposed
342 * - the worst values get disposed
345 * Actually, we should displace a value immediately after it was used.
346 * If we don't, the cardinality of the workset does not reflect the register pressure.
347 * That might be necessary to determine the capacity left in the block.
349 * @p is_usage indicates that the values in new_vals are used (not defined)
350 * In this case reloads must be performed
352 static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) {
353 belady_env_t *env = bi->bel;
355 int i, len, max_allowed, demand, iter;
357 workset_t *ws = env->ws;
358 ir_node **to_insert = alloca(env->n_regs * sizeof(*to_insert));
361 1. Identify the number of needed slots and the values to reload
364 workset_foreach(new_vals, val, iter) {
365 /* mark value as used */
367 if (! workset_contains(ws, val)) {
368 DBG((dbg, DBG_DECIDE, " insert %+F\n", val));
369 to_insert[demand++] = val;
371 int insert_reload = 1;
374 * if we use a value which is transported in this block,
375 * i.e. a phi defined here or a live in, we check if there
376 * is room for that guy to survive from the block's entrance
379 if (is_transport_in(env, bi->bl, val)) {
380 DBG((dbg, DBG_SPILL, "entrance node %+F, capacity %d:\n", val, bi->pressure));
381 if (bi->pressure < env->n_regs) {
383 workset_insert(env, bi->entrance_reg, val);
385 DBG((dbg, DBG_SPILL, "... no reload. must be considered at block start\n"));
390 DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr));
391 be_add_reload(env->senv, val, env->instr, env->cls, 1);
396 assert(is_usage || "Defined value already in workset?!?");
397 DBG((dbg, DBG_DECIDE, " skip %+F\n", val));
400 DBG((dbg, DBG_DECIDE, " demand = %d\n", demand));
403 2. Make room for at least 'demand' slots
405 len = workset_get_length(ws);
406 max_allowed = env->n_regs - demand;
408 DBG((dbg, DBG_DECIDE, " disposing %d values\n", ws->len - max_allowed));
410 /* Only make more free room if we do not have enough */
411 if (len > max_allowed) {
412 int curr_step = sched_get_time_step(env->instr);
413 /* get current next-use distance */
414 for (i = 0; i < ws->len; ++i) {
415 ir_node *val = workset_get_val(ws, i);
416 next_use_t *use = phase_get_irn_data(&bi->next_uses, val);
417 assert(use == NULL || use->step >= curr_step);
418 workset_set_time(ws, i, use ? (unsigned) (use->step - curr_step) : DEAD);
421 unsigned dist = get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage);
422 workset_set_time(ws, i, dist);
426 /* sort entries by increasing nextuse-distance*/
429 /* kill the last 'demand' entries in the array */
430 workset_set_length(ws, max_allowed);
434 3. Insert the new values into the workset
436 for (i = 0; i < demand; ++i)
437 workset_insert(env, env->ws, to_insert[i]);
441 * For the given block @p block, decide for each values
442 * whether it is used from a register or is reloaded
445 static void belady(ir_node *block, void *data) {
446 belady_env_t *env = data;
447 block_info_t *block_info = new_block_info(env, block);
452 /* process the block from start to end */
453 DBG((dbg, DBG_WSETS, "Processing %+F...\n", block_info->bl));
455 new_vals = new_workset(env, &env->ob);
456 block_info->first_non_in = NULL;
457 build_next_uses(block_info);
459 workset_clear(env->ws);
460 sched_foreach(block, irn) {
462 assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!");
464 /* projs are handled with the tuple value.
465 * Phis are no real instr (see insert_starters())
466 * instr_nr does not increase */
467 if (is_Proj(irn) || is_Phi(irn)) {
468 DBG((dbg, DBG_DECIDE, " ...%+F skipped\n", irn));
471 DBG((dbg, DBG_DECIDE, " ...%+F\n", irn));
473 if (!block_info->first_non_in)
474 block_info->first_non_in = irn;
476 /* set instruction in the workset */
479 /* allocate all values _used_ by this instruction */
480 workset_clear(new_vals);
481 for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
482 workset_insert(env, new_vals, get_irn_n(irn, i));
484 displace(block_info, new_vals, 1);
486 block_info->pressure = MAX(block_info->pressure, workset_get_length(env->ws));
489 * set all used variables to the next use in their next_use_t list
490 * Also, kill all dead variables from the workset. They are only
491 * augmenting the pressure. Note, that a variable is dead
492 * if it has no further use in this block and is *not* live end
494 for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
495 ir_node *op = get_irn_n(irn, i);
496 next_use_t *use = phase_get_irn_data(&block_info->next_uses, op);
499 if (!use->next && !be_is_live_end(env->lv, block, op))
500 workset_remove(env->ws, op);
502 phase_set_irn_data(&block_info->next_uses, op, use->next);
505 /* allocate all values _defined_ by this instruction */
506 workset_clear(new_vals);
507 if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */
508 const ir_edge_t *edge;
510 foreach_out_edge(irn, edge) {
511 ir_node *proj = get_edge_src_irn(edge);
512 workset_insert(env, new_vals, proj);
515 workset_insert(env, new_vals, irn);
517 displace(block_info, new_vals, 0);
522 phase_free(&block_info->next_uses);
524 /* Remember end-workset for this block */
525 block_info->ws_end = workset_clone(env, &env->ob, env->ws);
526 DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block));
527 workset_foreach(block_info->ws_end, irn, iter)
528 DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(block_info->ws_end, iter)));
533 |_ _| |__ ___ __ _| | ___ | |__ __ _| | | _ \ __ _ _ __| |_
534 | | | '_ \ / _ \ / _` | |/ _ \| '_ \ / _` | | | |_) / _` | '__| __|
535 | | | | | | __/ | (_| | | (_) | |_) | (_| | | | __/ (_| | | | |_
536 |_| |_| |_|\___| \__, |_|\___/|_.__/ \__,_|_| |_| \__,_|_| \__|
541 static int block_freq_gt(const void *a, const void *b)
543 const ir_node * const *p = a;
544 const ir_node * const *q = b;
545 block_info_t *pi = get_block_info(*p);
546 block_info_t *qi = get_block_info(*q);
547 return qi->exec_freq - pi->exec_freq;
550 typedef struct _block_end_state_t {
554 workset_t *end_state;
555 unsigned reload_at_end : 1;
556 unsigned live_through : 1;
559 typedef struct _global_end_state_t {
563 block_end_state_t *end_info;
566 } global_end_state_t;
568 static block_end_state_t *get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
572 for (i = 0; i < state->gauge; ++i) {
573 block_end_state_t *bei = &state->end_info[i];
574 if (bei->bl == bl && bei->irn == irn)
579 block_info_t *bi = get_block_info(bl);
580 block_end_state_t *curr;
582 /* make sure we have room in the array */
583 ARR_EXTO(block_end_state_t, state->end_info, (int) state->gauge);
585 curr = &state->end_info[state->gauge];
587 memset(curr, 0, sizeof(curr[0]));
590 curr->end_state = workset_clone(state->env, &state->obst, bi->ws_end);
597 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level);
599 static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
601 block_end_state_t *bes = get_block_end_state(ges, bl, irn);
602 workset_t *end = bes->end_state;
603 block_info_t *bi = get_block_info(bl);
604 int n_regs = bi->bel->n_regs;
607 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}can make avail %+F at end of %+F (pressure %d)\n",
608 level, irn, bl, bi->pressure));
611 * to make the value available at end,
612 * we have several cases here.
614 * - we already visited that block.
615 * - If the value is in the final end set, return 0.
616 * somebody else already allocated it there.
617 * - If not and the final end set is already full,
618 * we cannot make the value available at the end
619 * of this block. return INFINITY.
620 * - Else (value not in final end set and there is room):
621 * 1) The value is in a register at the end of the local Belady pass.
622 * Allocate a slot in the final end set and return 0.
623 * 2) The value is not in the Belady end set:
624 * If the block's capacity is < k then check what it costs
625 * to transport the value from upper blocks to this block.
626 * Compare that against the reload cost in this block. If
627 * cheaper, do the other thing. If not, reload it here.
631 * we have been here before and already figured out some costs.
632 * so we can exit safely.
634 if (bes->costs >= 0.0) {
635 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}we\'ve been here before\n", level));
639 /* if the end set contains it already, it is in a reg and it costs nothing
640 * to load it to one. */
641 index = workset_get_index(end, irn);
643 unsigned ver = end->vals[index].version;
644 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}node is in the end set and is %s fixed\n",
645 level, ver > ges->version ? "" : "not"));
648 * if the version is older, the value is already fixed
649 * and cannot be removed from the end set. If not,
650 * we fix it here by giving it our version.
652 if (ver < ges->version)
653 end->vals[index].version = ges->version;
660 * Now we have two options:
661 * 1) Reload the value at the end of the block.
662 * Therefore, perhaps, we have to erase another one from the workset.
663 * This may only be done if it has not been fixed.
664 * Since fixed means that a previous pass has decided that that value
665 * *has* to stay in the end set.
666 * 2) we can try, if the capacity of the block allows it, to let
667 * the value live through the block and make it available at
670 * First, we test the local (reload in this block) alternative
671 * and compare against the other alternative.
672 * Of course, we chose the cheaper one.
676 int len = workset_get_length(end);
680 bes->costs = HUGE_VAL;
683 * look if there is room in the end array
684 * for the variable. Note that this does not
685 * means that the var is living through the block.
686 * There is just room at the *end*
689 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}the end set has %d free slots\n",
690 level, n_regs - len));
694 for (i = 0; i < len; ++i)
695 if (end->vals[i].version < ges->version)
699 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}%+F (slot %d) can be erased from the end set\n",
700 level, end->vals[i].irn, i));
706 int gauge = ges->gauge;
707 double reload_here = bi->exec_freq;
708 double bring_in = bi->pressure < n_regs ? can_bring_in(ges, bl, irn, level + 1) : HUGE_VAL;
710 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}there is a free slot. capacity=%d, reload here=%f, bring in=%f\n",
711 level, n_regs - bi->pressure, reload_here, bring_in));
714 * reloading here pays off; bringing the value in from elsewhere
715 * is too expensive, hence we drop that search by resetting
718 if (reload_here <= bring_in) {
720 bes->costs = reload_here;
721 bes->reload_at_end = 1;
725 bes->live_through = 1;
726 bes->costs = bring_in;
729 end->vals[slot].irn = irn;
730 end->vals[slot].version = ges->version;
735 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}-> %f\n", level, bes->costs));
739 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
741 double glob_costs = HUGE_VAL;
742 int def_block = bl == get_nodes_block(irn);
743 int phi = is_Phi(irn);
745 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}can bring in for %+F at block %+F\n", level, irn, bl));
747 if (phi || !def_block) {
748 int i, n = get_irn_arity(bl);
749 ir_node **nodes = alloca(get_irn_arity(bl) * sizeof(nodes[0]));
751 int gauge_begin = ges->gauge;
754 for (i = 0; i < n; ++i) {
755 ir_node *pr = get_Block_cfgpred_block(bl, i);
756 ir_node *op = phi && def_block ? get_irn_n(irn, i) : irn;
757 double c = can_make_available_at_end(ges, pr, op, level + 1);
760 ges->gauge = gauge_begin;
761 glob_costs = HUGE_VAL;
770 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}-> %f\n", level, glob_costs));
774 static void materialize_and_commit_end_state(global_end_state_t *ges)
776 belady_env_t *env = ges->env;
779 DBG((dbg, DBG_GLOBAL, "\tmaterializing\n"));
780 for (i = 0; i < ges->gauge; ++i) {
781 block_end_state_t *bes = &ges->end_info[i];
782 block_info_t *bi = get_block_info(bes->bl);
785 /* insert the reload if the val was reloaded at the block's end */
786 if (bes->reload_at_end) {
787 be_add_reload_at_end(env->senv, bes->irn, bes->bl, env->cls, 1);
788 DBG((dbg, DBG_GLOBAL, "\t\tadding reload of %+F at end of %+F\n", bes->irn, bes->bl));
792 * if the variable is live through the block,
793 * update the pressure indicator.
795 bi->pressure = MAX(bi->pressure + bes->live_through, workset_get_length(bes->end_state));
797 idx = workset_get_index(bes->end_state, bes->irn);
800 * set the version number in the workset.
801 * That will mark this value as fixed in the end set
802 * and will prevent further investigations from removing
804 * Also "commit" the workset;
805 * by copying it back to the block's end workset.
808 DBG((dbg, DBG_GLOBAL, "\t\tcommiting workset of %+F with version %x\n", bes->bl, ges->version));
809 bes->end_state->vals[idx].version = ges->version;
810 workset_copy(env, bi->ws_end, bes->end_state);
816 * Examine all irns which shall be in regs at the beginning of the
819 static void fix_block_borders(global_end_state_t *ges, ir_node *block) {
820 block_info_t *bi = get_block_info(block);
821 belady_env_t *env = ges->env;
826 DBG((dbg, DBG_GLOBAL, "fixing block borders at %+F (%fHz)\n", block, bi->exec_freq));
828 /* process all variables which shall be in a reg at
829 * the beginning of the block in the order of the next use. */
830 workset_foreach(bi->entrance_reg, irn, i) {
831 int is_entrance_phi = is_Phi(irn) && get_nodes_block(irn) == block;
832 double bring_in_costs;
834 /* reset the gauge and begin the search */
838 DBG((dbg, DBG_GLOBAL, "\ttrans in var %+F, version %x\n", irn, ges->version));
840 bring_in_costs = can_bring_in(ges, block, irn, 0);
842 /* we were not able to let the value arrive
843 * in a register at the entrance of the block
844 * so we have to do the reload locally */
845 if (bring_in_costs > bi->exec_freq) {
846 DBG((dbg, DBG_GLOBAL, "\tbring in: %f, local: %f -> doing reload at beginning\n",
847 bring_in_costs, bi->exec_freq));
849 be_add_reload(env->senv, irn, bi->first_non_in, env->cls, 1);
854 * Mark this phi as succeeded.
855 * It was not replaced by a reload at the block's entrance
856 * and thus is not phi_spilled.
859 bitset_add_irn(ges->succ_phis, irn);
861 materialize_and_commit_end_state(ges);
866 static void global_assign(belady_env_t *env)
868 global_end_state_t ges;
871 obstack_init(&ges.obst);
875 ges.end_info = NEW_ARR_F(block_end_state_t, env->n_blocks);
876 ges.succ_phis = bitset_irg_obstack_alloc(&env->ob, env->irg);
879 * sort the blocks according to execution frequency.
880 * That's not necessary for belady() but for the global pass later on.
882 qsort(env->blocks, env->n_blocks, sizeof(env->blocks[0]), block_freq_gt);
884 for (i = 0; i < env->n_blocks; ++i)
885 fix_block_borders(&ges, env->blocks[i]);
888 * Now we spill phis which cannot be kept since they were replaced
889 * by reloads at the block entrances.
891 for (i = 0; i < env->n_blocks; ++i) {
892 ir_node *bl = env->blocks[i];
895 sched_foreach(bl, irn) {
899 if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)
900 && !bitset_contains_irn(ges.succ_phis, irn))
901 be_spill_phi(env->senv, irn);
907 static void collect_blocks(ir_node *bl, void *data)
909 belady_env_t *env = data;
911 obstack_ptr_grow(&env->ob, bl);
914 void be_spill_belady_spill_env2(be_irg_t *birg, const arch_register_class_t *cls, spill_env_t *spill_env) {
916 ir_graph *irg = be_get_birg_irg(birg);
919 /* some special classes contain only ignore regs, nothing to do then */
920 n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
926 /* init belady env */
927 obstack_init(&env.ob);
929 env.arch = birg->main_env->arch_env;
931 env.lv = be_get_birg_liveness(birg);
933 env.ws = new_workset(&env, &env.ob);
934 env.uses = be_begin_uses(irg, env.lv);
935 env.senv = spill_env ? spill_env : be_new_spill_env(birg);
936 env.ef = be_get_birg_exec_freq(birg);
939 irg_block_walk_graph(irg, NULL, collect_blocks, &env);
940 obstack_ptr_grow(&env.ob, NULL);
941 env.blocks = obstack_finish(&env.ob);
943 /* Fix high register pressure with belady algorithm */
944 for (i = 0; i < env.n_blocks; ++i)
945 belady(env.blocks[i], &env);
949 /* Insert spill/reload nodes into the graph and fix usages */
950 be_insert_spills_reloads(env.senv);
953 if(spill_env == NULL)
954 be_delete_spill_env(env.senv);
955 be_end_uses(env.uses);
956 obstack_free(&env.ob, NULL);
961 * Do spilling for a register class on a graph using the belady heuristic.
962 * In the transformed graph, the register pressure never exceeds the number
963 * of available registers.
965 * @param birg The backend graph
966 * @param cls The register class to spill
968 static void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) {
969 be_spill_belady_spill_env2(birg, cls, NULL);
973 void be_init_spillbelady2(void)
975 static be_spiller_t belady_spiller = {
979 be_register_spiller("belady2", &belady_spiller);
980 FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2");
983 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2);