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"
61 #include "besched_t.h"
65 #include "bechordal_t.h"
66 #include "bespilloptions.h"
67 #include "beloopana.h"
78 #define DBG_WORKSET 128
79 #define DBG_GLOBAL 256
82 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
85 * An association between a node and a point in time.
87 typedef struct _loc_t {
88 ir_node *irn; /**< A node. */
89 unsigned time; /**< A use time (see beuses.h). */
90 unsigned version; /**< That is used in the global pass below.
91 For usage see the comments below.
92 In the local belady pass, this is not
96 typedef struct _workset_t {
97 int len; /**< current length */
98 loc_t vals[0]; /**< inlined array of the values/distances in this working set */
101 typedef struct _belady_env_t {
104 const arch_env_t *arch;
105 const arch_register_class_t *cls;
109 ir_node **blocks; /**< Array of all blocks. */
110 int n_blocks; /**< Number of blocks in the graph. */
111 int n_regs; /**< number of regs in this reg-class */
112 workset_t *ws; /**< the main workset used while processing a block. ob-allocated */
113 ir_node *instr; /**< current instruction */
114 unsigned instr_nr; /**< current instruction number (relative to block start) */
116 spill_env_t *senv; /**< see bespill.h */
120 static int loc_compare(const void *a, const void *b)
124 return (int) p->time - (int) q->time;
127 static INLINE void workset_print(const workset_t *w)
131 for(i = 0; i < w->len; ++i) {
132 ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
137 * Alloc a new workset on obstack @p ob with maximum size @p max
139 static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
141 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
142 res = obstack_alloc(ob, size);
143 memset(res, 0, size);
148 * Alloc a new instance on obstack and make it equal to @param ws
150 static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
152 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
153 res = obstack_alloc(ob, size);
154 memcpy(res, ws, size);
159 * Do NOT alloc anything. Make @param tgt equal to @param src.
160 * returns @param tgt for convenience
162 static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
163 size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]);
164 memcpy(tgt, src, size);
169 * Overwrites the current content array of @param ws with the
170 * @param count locations given at memory @param locs.
171 * Set the length of @param ws to count.
173 static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
174 workset->len = count;
175 memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0]));
179 * Inserts the value @p val into the workset, iff it is not
180 * already contained. The workset must not be full.
182 static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
184 /* check for current regclass */
185 if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) {
186 DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
190 /* check if val is already contained */
191 for(i=0; i<ws->len; ++i)
192 if (ws->vals[i].irn == val)
196 assert(ws->len < env->n_regs && "Workset already full!");
197 ws->vals[ws->len++].irn = val;
201 * Removes all entries from this workset
203 static INLINE void workset_clear(workset_t *ws) {
208 * Removes the value @p val from the workset if present.
210 static INLINE void workset_remove(workset_t *ws, ir_node *val) {
212 for(i=0; i<ws->len; ++i) {
213 if (ws->vals[i].irn == val) {
214 ws->vals[i] = ws->vals[--ws->len];
220 static INLINE int workset_get_index(const workset_t *ws, const ir_node *val) {
222 for(i=0; i<ws->len; ++i) {
223 if (ws->vals[i].irn == val)
231 * Iterates over all values in the working set.
232 * @p ws The workset to iterate
233 * @p v A variable to put the current value in
234 * @p i An integer for internal use
236 #define workset_foreach(ws, v, i) for(i=0; \
237 v=(i < ws->len) ? ws->vals[i].irn : NULL, i < ws->len; \
240 #define workset_set_time(ws, i, t) (ws)->vals[i].time=t
241 #define workset_get_time(ws, i) (ws)->vals[i].time
242 #define workset_set_length(ws, length) (ws)->len = length
243 #define workset_get_length(ws) ((ws)->len)
244 #define workset_get_val(ws, i) ((ws)->vals[i].irn)
245 #define workset_sort(ws) qsort((ws)->vals, (ws)->len, sizeof((ws)->vals[0]), loc_compare);
246 #define workset_contains(ws, n) (workset_get_index(ws, n) >= 0)
248 typedef struct _block_info_t {
251 workset_t *ws_start, *ws_end;
254 ir_node *first_non_in; /**< First node in block which is not a phi. */
255 ir_node *last_ins; /**< The instruction before which end of
256 block reloads will be inserted. */
258 workset_t *entrance_reg; /**< That set will contain all values
259 transported into the block which
260 are used before they are displaced.
261 That means, we later have to care to
262 bring them into the block in a register
263 or reload them at the entry of the block. */
265 int pressure; /**< The amount of registers which remain free
266 in this block. This capacity can be used to let
267 global variables, transported into other blocks,
268 live through this block. */
270 double exec_freq; /**< The execution frequency of this block. */
273 static INLINE void *new_block_info(belady_env_t *bel, ir_node *bl) {
274 block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res));
275 memset(res, 0, sizeof(res[0]));
276 res->first_non_in = NULL;
277 res->last_ins = NULL;
280 res->entrance_reg = new_workset(bel, &bel->ob);
281 res->exec_freq = get_block_execfreq(bel->ef, bl);
282 set_irn_link(bl, res);
286 #define get_block_info(block) ((block_info_t *)get_irn_link(block))
287 #define set_block_info(block, info) set_irn_link(block, info)
289 static INLINE ir_node *block_info_get_last_ins(block_info_t *bi)
292 bi->last_ins = be_get_end_of_block_insertion_point(bi->bl);
297 typedef struct _next_use_t {
298 unsigned is_first_use : 1; /**< Indicate that this use is the first
299 in the block. Needed to identify
300 transport in values for the global
302 int step; /**< The time step of the use. */
303 struct _next_use_t *next; /**< The next use int this block
307 static void *next_use_init(ir_phase *phase, ir_node *irn, void *old)
315 static void build_next_uses(block_info_t *bi)
319 phase_init(&bi->next_uses, "next uses", bi->bel->irg, PHASE_DEFAULT_GROWTH, next_use_init, NULL);
320 sched_foreach_reverse(bi->bl, irn) {
321 int i, step = sched_get_time_step(irn);
326 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
327 ir_node *op = get_irn_n(irn, i);
328 next_use_t *curr = phase_get_irn_data(&bi->next_uses, op);
329 next_use_t *use = phase_alloc(&bi->next_uses, sizeof(use[0]));
332 use->is_first_use = 1;
337 curr->is_first_use = 0;
339 phase_set_irn_data(&bi->next_uses, op, use);
344 #define get_current_use(bi, irn) phase_get_irn_data(&(bi)->next_uses, (irn))
346 static INLINE void advance_current_use(block_info_t *bi, const ir_node *irn)
348 next_use_t *use = get_current_use(bi, irn);
351 phase_set_irn_data(&bi->next_uses, irn, use->next);
355 static INLINE int is_local_phi(const ir_node *bl, const ir_node *irn)
357 return is_Phi(irn) && get_nodes_block(irn) == bl;
361 * Check, if the value is something that is transported into a block.
362 * That is, the value is defined elsewhere or defined by a Phi in the block.
363 * @param env The belady environment.
364 * @param bl The block in question.
365 * @param irn The node in question.
366 * @return 1, if node is something transported into @p bl, 0 if not.
367 * @note The function will only give correct answers in the case
368 * where @p irn is unsed in the block @p bl which is always
369 * the case in our usage scenario.
371 static INLINE int is_transport_in(const ir_node *bl, const ir_node *irn)
373 return is_local_phi(bl, irn) || get_nodes_block(irn) != bl;
377 * Performs the actions necessary to grant the request that:
378 * - new_vals can be held in registers
379 * - as few as possible other values are disposed
380 * - the worst values get disposed
382 * @p is_usage indicates that the values in new_vals are used (not defined)
383 * In this case reloads must be performed
385 static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) {
386 belady_env_t *env = bi->bel;
387 workset_t *ws = env->ws;
388 ir_node **to_insert = alloca(env->n_regs * sizeof(to_insert[0]));
390 int i, len, max_allowed, demand, iter;
394 1. Identify the number of needed slots and the values to reload
397 workset_foreach(new_vals, val, iter) {
398 /* mark value as used */
400 if (! workset_contains(ws, val)) {
401 DBG((dbg, DBG_DECIDE, " insert %+F\n", val));
402 to_insert[demand++] = val;
404 int insert_reload = 1;
405 next_use_t *use = get_current_use(bi, val);
408 * if we use a value which is transported in this block, i.e. a
409 * phi defined here or a live in, for the first time, we check
410 * if there is room for that guy to survive from the block's
411 * entrance to here or not.
414 assert(sched_get_time_step(env->instr) == use->step);
415 if (is_transport_in(bi->bl, val) && use->is_first_use) {
416 DBG((dbg, DBG_DECIDE, "entrance node %+F, pressure %d:\n", val, bi->pressure));
417 if (bi->pressure < env->n_regs) {
418 workset_insert(env, bi->entrance_reg, val);
421 DBG((dbg, DBG_DECIDE, "... no reload. must be considered at block start\n"));
426 DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr));
427 be_add_reload(env->senv, val, env->instr, env->cls, 1);
432 assert(is_usage || "Defined value already in workset?!?");
433 DBG((dbg, DBG_DECIDE, " skip %+F\n", val));
436 DBG((dbg, DBG_DECIDE, " demand = %d\n", demand));
439 2. Make room for at least 'demand' slots
441 len = workset_get_length(ws);
442 max_allowed = env->n_regs - demand;
444 /* Only make more free room if we do not have enough */
445 if (len > max_allowed) {
446 int curr_step = sched_get_time_step(env->instr);
448 DBG((dbg, DBG_DECIDE, " disposing %d values\n", len - max_allowed));
450 /* get current next-use distance */
451 for (i = 0; i < ws->len; ++i) {
452 ir_node *val = workset_get_val(ws, i);
453 next_use_t *use = phase_get_irn_data(&bi->next_uses, val);
454 assert(use == NULL || use->step >= curr_step);
456 if (!is_usage && use)
459 workset_set_time(ws, i, use ? (unsigned) (use->step - curr_step) : DEAD);
462 /* sort entries by increasing nextuse-distance*/
465 /* kill the last 'demand' entries in the array */
466 workset_set_length(ws, max_allowed);
470 3. Insert the new values into the workset
471 Also, we update the pressure in the block info.
472 That is important for the global pass to decide
473 how many values can live through the block.
475 for (i = 0; i < demand; ++i)
476 workset_insert(env, env->ws, to_insert[i]);
478 bi->pressure = MAX(bi->pressure, workset_get_length(env->ws));
483 * For the given block @p block, decide for each values
484 * whether it is used from a register or is reloaded
487 static void belady(ir_node *block, void *data) {
488 belady_env_t *env = data;
489 block_info_t *block_info = new_block_info(env, block);
495 DBG((dbg, DBG_WSETS, "Processing %+F...\n", block_info->bl));
496 new_vals = new_workset(env, &env->ob);
497 workset_clear(env->ws);
499 /* build the next use information for this block. */
500 build_next_uses(block_info);
503 block_info->first_non_in = NULL;
505 /* process the block from start to end */
506 sched_foreach(block, irn) {
508 assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!");
510 /* projs are handled with the tuple value.
511 * Phis are no real instr (see insert_starters())
512 * instr_nr does not increase */
513 if (is_Proj(irn) || is_Phi(irn)) {
514 DBG((dbg, DBG_DECIDE, " ...%+F skipped\n", irn));
517 DBG((dbg, DBG_DECIDE, " ...%+F\n", irn));
519 if (!block_info->first_non_in)
520 block_info->first_non_in = irn;
522 /* set instruction in the workset */
525 /* allocate all values _used_ by this instruction */
526 workset_clear(new_vals);
527 for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
528 workset_insert(env, new_vals, get_irn_n(irn, i));
530 displace(block_info, new_vals, 1);
533 * set all used variables to the next use in their next_use_t list
534 * Also, kill all dead variables from the workset. They are only
535 * augmenting the pressure. Note, that a variable is dead
536 * if it has no further use in this block and is *not* live end
538 for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
539 ir_node *op = get_irn_n(irn, i);
540 next_use_t *use = get_current_use(block_info, op);
543 if (!use->next && !be_is_live_end(env->lv, block, op))
544 workset_remove(env->ws, op);
546 advance_current_use(block_info, op);
549 /* allocate all values _defined_ by this instruction */
550 workset_clear(new_vals);
551 if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */
552 const ir_edge_t *edge;
554 foreach_out_edge(irn, edge) {
555 ir_node *proj = get_edge_src_irn(edge);
556 workset_insert(env, new_vals, proj);
559 workset_insert(env, new_vals, irn);
561 displace(block_info, new_vals, 0);
566 phase_free(&block_info->next_uses);
568 /* Remember end-workset for this block */
569 block_info->ws_end = workset_clone(env, &env->ob, env->ws);
570 DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block));
571 workset_foreach(block_info->ws_end, irn, iter)
572 DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(block_info->ws_end, iter)));
573 DBG((dbg, DBG_WSETS, "Max pressure in block: %d\n", block_info->pressure));
578 |_ _| |__ ___ __ _| | ___ | |__ __ _| | | _ \ __ _ _ __| |_
579 | | | '_ \ / _ \ / _` | |/ _ \| '_ \ / _` | | | |_) / _` | '__| __|
580 | | | | | | __/ | (_| | | (_) | |_) | (_| | | | __/ (_| | | | |_
581 |_| |_| |_|\___| \__, |_|\___/|_.__/ \__,_|_| |_| \__,_|_| \__|
586 static int block_freq_gt(const void *a, const void *b)
588 const ir_node * const *p = a;
589 const ir_node * const *q = b;
590 block_info_t *pi = get_block_info(*p);
591 block_info_t *qi = get_block_info(*q);
592 double diff = qi->exec_freq - pi->exec_freq;
593 return (diff > 0) - (diff < 0);
596 typedef struct _block_end_state_t {
600 workset_t *end_state;
601 unsigned reload_at_end : 1;
602 unsigned live_through : 1;
605 typedef struct _global_end_state_t {
609 block_end_state_t *end_info;
612 } global_end_state_t;
614 static block_end_state_t *get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
618 for (i = 0; i < state->gauge; ++i) {
619 block_end_state_t *bei = &state->end_info[i];
620 if (bei->bl == bl && bei->irn == irn)
625 block_info_t *bi = get_block_info(bl);
626 block_end_state_t *curr;
628 /* make sure we have room in the array */
629 ARR_EXTO(block_end_state_t, state->end_info, (int) state->gauge);
631 curr = &state->end_info[state->gauge];
633 memset(curr, 0, sizeof(curr[0]));
636 curr->end_state = workset_clone(state->env, &state->obst, bi->ws_end);
643 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level);
645 static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
647 block_end_state_t *bes = get_block_end_state(ges, bl, irn);
648 workset_t *end = bes->end_state;
649 block_info_t *bi = get_block_info(bl);
650 int n_regs = bi->bel->n_regs;
653 DBG((dbg, DBG_GLOBAL, "\t%2Dcan make avail %+F at end of %+F (pressure %d)\n",
654 level, irn, bl, bi->pressure));
657 * to make the value available at end,
658 * we have several cases here.
660 * - we already visited that block.
661 * - If the value is in the final end set, return 0.
662 * somebody else already allocated it there.
663 * - If not and the final end set is already full,
664 * we cannot make the value available at the end
665 * of this block. return INFINITY.
666 * - Else (value not in final end set and there is room):
667 * 1) The value is in a register at the end of the local Belady pass.
668 * Allocate a slot in the final end set and return 0.
669 * 2) The value is not in the Belady end set:
670 * If the block's capacity is < k then check what it costs
671 * to transport the value from upper blocks to this block.
672 * Compare that against the reload cost in this block. If
673 * cheaper, do the other thing. If not, reload it here.
677 * we have been here before and already figured out some costs.
678 * so we can exit safely.
680 if (bes->costs >= 0.0) {
681 DBG((dbg, DBG_GLOBAL, "\t%2Dwe\'ve been here before\n", level));
685 /* if the end set contains it already, it is in a reg and it costs nothing
686 * to load it to one. */
687 index = workset_get_index(end, irn);
689 unsigned ver = end->vals[index].version;
690 DBG((dbg, DBG_GLOBAL, "\t%2Dnode is in the end set and is %s fixed\n",
691 level, ver > ges->version ? "already" : "not yet"));
694 * if the version is older, the value is already fixed
695 * and cannot be removed from the end set. If not,
696 * we fix it here by giving it our version.
698 if (ver < ges->version)
699 end->vals[index].version = ges->version;
706 * Now we have two options:
707 * 1) Reload the value at the end of the block.
708 * Therefore, perhaps, we have to erase another one from the workset.
709 * This may only be done if it has not been fixed.
710 * Since fixed means that a previous pass has decided that that value
711 * *has* to stay in the end set.
712 * 2) we can try, if the capacity of the block allows it, to let
713 * the value live through the block and make it available at
716 * First, we test the local (reload in this block) alternative
717 * and compare against the other alternative.
718 * Of course, we chose the cheaper one.
722 int len = workset_get_length(end);
726 bes->costs = HUGE_VAL;
729 * look if there is room in the end array
730 * for the variable. Note that this does not
731 * means that the var is living through the block.
732 * There is just room at the *end*
735 DBG((dbg, DBG_GLOBAL, "\t%2Dthe end set has %d free slots\n",
736 level, n_regs - len));
740 for (i = 0; i < len; ++i)
741 if (end->vals[i].version < ges->version)
745 DBG((dbg, DBG_GLOBAL, "\t%2D%+F (slot %d) can be erased from the end set\n",
746 level, end->vals[i].irn, i));
752 int gauge = ges->gauge;
753 ir_node *ins_before = block_info_get_last_ins(bi);
754 double reload_here = be_get_reload_costs(bi->bel->senv, irn, ins_before);
755 double bring_in = bi->pressure < n_regs ? can_bring_in(ges, bl, irn, level + 1) : HUGE_VAL;
757 DBG((dbg, DBG_GLOBAL, "\t%2Dthere is a free slot. capacity=%d, reload here=%f, bring in=%f\n",
758 level, n_regs - bi->pressure, reload_here, bring_in));
761 * reloading here pays off; bringing the value in from elsewhere
762 * is too expensive, hence we drop that search by resetting
765 if (reload_here <= bring_in) {
767 bes->costs = reload_here;
768 bes->reload_at_end = 1;
772 bes->live_through = 1;
773 bes->costs = bring_in;
776 end->vals[slot].irn = irn;
777 end->vals[slot].version = ges->version;
778 end->len = MAX(end->len, slot + 1);
786 DBG((dbg, DBG_GLOBAL, "\t%2D-> %f\n", level, bes->costs));
790 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
792 double glob_costs = HUGE_VAL;
794 DBG((dbg, DBG_GLOBAL, "\t%2Dcan bring in for %+F at block %+F\n", level, irn, bl));
796 if (is_transport_in(bl, irn)) {
797 int i, n = get_irn_arity(bl);
798 ir_node **nodes = alloca(get_irn_arity(bl) * sizeof(nodes[0]));
800 int gauge_begin = ges->gauge;
803 for (i = 0; i < n; ++i) {
804 ir_node *pr = get_Block_cfgpred_block(bl, i);
805 ir_node *op = is_local_phi(bl, irn) ? get_irn_n(irn, i) : irn;
806 double c = can_make_available_at_end(ges, pr, op, level + 1);
809 ges->gauge = gauge_begin;
810 glob_costs = HUGE_VAL;
819 DBG((dbg, DBG_GLOBAL, "\t%2D-> %f\n", level, glob_costs));
823 static void materialize_and_commit_end_state(global_end_state_t *ges)
825 belady_env_t *env = ges->env;
828 DBG((dbg, DBG_GLOBAL, "\tmaterializing\n"));
829 for (i = 0; i < ges->gauge; ++i) {
830 block_end_state_t *bes = &ges->end_info[i];
831 block_info_t *bi = get_block_info(bes->bl);
832 int idx, end_pressure;
834 DBG((dbg, DBG_GLOBAL, "\t\t%+F in %+F, cost %f through: %d, rel: %d\n",
835 bes->irn, bes->bl, bes->costs, bes->live_through, bes->reload_at_end));
837 /* insert the reload if the val was reloaded at the block's end */
838 if (bes->reload_at_end) {
839 be_add_reload_at_end(env->senv, bes->irn, bes->bl, env->cls, 1);
840 DBG((dbg, DBG_GLOBAL, "\t\tadding reload of %+F at end of %+F\n", bes->irn, bes->bl));
844 for (idx = workset_get_length(bes->end_state) - 1; idx >= 0; --idx)
845 if (bes->end_state->vals[idx].version >= ges->version)
849 * if the variable is live through the block,
850 * update the pressure indicator.
852 DBG((dbg, DBG_GLOBAL, "\t\told pressure %d, ", bi->pressure));
854 bi->pressure = MAX(bi->pressure + bes->live_through, end_pressure);
856 DBG((dbg, DBG_GLOBAL, "new pressure: %d, end pressure: %d, end length: %d\n",
857 bi->pressure, end_pressure, workset_get_length(bes->end_state)));
859 // workset_print(bes->end_state);
860 idx = workset_get_index(bes->end_state, bes->irn);
862 if (is_local_phi(bes->bl, bes->irn) && bes->live_through)
863 bitset_add_irn(ges->succ_phis, bes->irn);
866 * set the version number in the workset.
867 * That will mark this value as fixed in the end set
868 * and will prevent further investigations from removing
870 * Also "commit" the workset;
871 * by copying it back to the block's end workset.
874 DBG((dbg, DBG_GLOBAL, "\t\tcommiting workset of %+F with version %x\n", bes->bl, ges->version));
875 bes->end_state->vals[idx].version = ges->version;
876 workset_copy(env, bi->ws_end, bes->end_state);
882 * Examine all irns which shall be in regs at the beginning of the
885 static void fix_block_borders(global_end_state_t *ges, ir_node *block) {
886 block_info_t *bi = get_block_info(block);
887 belady_env_t *env = ges->env;
892 DBG((dbg, DBG_GLOBAL, "fixing block borders at %+F (%f)\n", block, bi->exec_freq));
894 /* process all variables which shall be in a reg at
895 * the beginning of the block in the order of the next use. */
896 workset_foreach(bi->entrance_reg, irn, i) {
897 double local_costs = be_get_reload_costs(env->senv, irn, bi->first_non_in);
898 double bring_in_costs;
900 /* reset the gauge and create a new version. */
904 DBG((dbg, DBG_GLOBAL, "\ttrans in var %+F, version %x\n", irn, ges->version));
906 bring_in_costs = can_bring_in(ges, block, irn, 1);
908 DBG((dbg, DBG_GLOBAL, "\tbring in: %f, local: %f", bring_in_costs, local_costs));
911 * we were not able to let the value arrive
912 * in a register at the entrance of the block
913 * or it is too costly, so we have to do the reload locally
915 if (bring_in_costs > local_costs) {
917 DBG((dbg, DBG_GLOBAL, " -> do local reload\n"));
918 be_add_reload(env->senv, irn, bi->first_non_in, env->cls, 1);
923 * if the transport-in was a phi (that is actually used in block)
924 * it will no longer remain and we have to spill it completely.
926 if (is_local_phi(block, irn))
927 bitset_add_irn(ges->succ_phis, irn);
929 DBG((dbg, DBG_GLOBAL, " -> do remote reload\n"));
930 materialize_and_commit_end_state(ges);
933 DBG((dbg, DBG_GLOBAL, "\n"));
937 static void global_assign(belady_env_t *env)
939 global_end_state_t ges;
942 obstack_init(&ges.obst);
946 ges.end_info = NEW_ARR_F(block_end_state_t, env->n_blocks);
947 ges.succ_phis = bitset_irg_obstack_alloc(&env->ob, env->irg);
950 * sort the blocks according to execution frequency.
951 * That's not necessary for belady() but for the global pass later on.
953 qsort(env->blocks, env->n_blocks, sizeof(env->blocks[0]), block_freq_gt);
955 for (i = 0; i < env->n_blocks; ++i)
956 fix_block_borders(&ges, env->blocks[i]);
959 * Now we spill phis which cannot be kept since they were replaced
960 * by reloads at the block entrances.
962 for (i = 0; i < env->n_blocks; ++i) {
963 ir_node *bl = env->blocks[i];
966 sched_foreach(bl, irn) {
970 if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)
971 && !bitset_contains_irn(ges.succ_phis, irn))
972 be_spill_phi(env->senv, irn);
978 static void collect_blocks(ir_node *bl, void *data)
980 belady_env_t *env = data;
982 obstack_ptr_grow(&env->ob, bl);
985 void be_spill_belady_spill_env2(be_irg_t *birg, const arch_register_class_t *cls, spill_env_t *spill_env) {
986 ir_graph *irg = be_get_birg_irg(birg);
990 /* some special classes contain only ignore regs, nothing to do then */
991 n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
997 /* init belady env */
998 obstack_init(&env.ob);
1000 env.arch = birg->main_env->arch_env;
1002 env.lv = be_get_birg_liveness(birg);
1003 env.n_regs = n_regs;
1004 env.ws = new_workset(&env, &env.ob);
1005 env.senv = spill_env ? spill_env : be_new_spill_env(birg);
1006 env.ef = be_get_birg_exec_freq(birg);
1009 irg_block_walk_graph(irg, NULL, collect_blocks, &env);
1010 obstack_ptr_grow(&env.ob, NULL);
1011 env.blocks = obstack_finish(&env.ob);
1013 /* Fix high register pressure in blocks with belady algorithm */
1014 for (i = 0; i < env.n_blocks; ++i)
1015 belady(env.blocks[i], &env);
1017 global_assign(&env);
1019 /* Insert spill/reload nodes into the graph and fix usages */
1020 be_insert_spills_reloads(env.senv);
1023 if(spill_env == NULL)
1024 be_delete_spill_env(env.senv);
1026 obstack_free(&env.ob, NULL);
1031 * Do spilling for a register class on a graph using the belady heuristic.
1032 * In the transformed graph, the register pressure never exceeds the number
1033 * of available registers.
1035 * @param birg The backend graph
1036 * @param cls The register class to spill
1038 static void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) {
1039 be_spill_belady_spill_env2(birg, cls, NULL);
1043 void be_init_spillbelady2(void)
1045 static be_spiller_t belady_spiller = {
1049 be_register_spiller("belady2", &belady_spiller);
1050 FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2");
1053 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2);