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
34 #include "irnodeset.h"
35 #include "irprintf_t.h"
41 #include "iredges_t.h"
49 #include "bespillbelady.h"
51 #include "besched_t.h"
55 #include "bechordal_t.h"
56 #include "bespilloptions.h"
57 #include "beloopana.h"
68 #define DBG_WORKSET 128
69 #define DBG_GLOBAL 256
70 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
74 * An association between a node and a point in time.
76 typedef struct _loc_t {
77 ir_node *irn; /**< A node. */
78 unsigned time; /**< A use time (see beuses.h). */
79 unsigned version; /**< That is used in the global pass below.
80 For usage see the comments below.
81 In the local belady pass, this is not
85 typedef struct _workset_t {
86 int len; /**< current length */
87 loc_t vals[0]; /**< inlined array of the values/distances in this working set */
90 typedef struct _belady_env_t {
92 const arch_env_t *arch;
93 const arch_register_class_t *cls;
97 ir_node **blocks; /**< Array of all blocks. */
98 int n_blocks; /**< Number of blocks in the graph. */
99 int n_regs; /**< number of regs in this reg-class */
100 workset_t *ws; /**< the main workset used while processing a block. ob-allocated */
101 be_uses_t *uses; /**< env for the next-use magic */
102 ir_node *instr; /**< current instruction */
103 unsigned instr_nr; /**< current instruction number (relative to block start) */
105 spill_env_t *senv; /**< see bespill.h */
109 static int loc_compare_idx(const void *a, const void *b)
113 return (int) get_irn_idx(p->irn) - (int) get_irn_idx(q->irn);
115 static int loc_compare(const void *a, const void *b)
119 int diff = (int) p->time - (int) q->time;
120 return diff != 0 ? diff : loc_compare_idx(a, b);
123 static INLINE void workset_print(const workset_t *w)
127 for(i = 0; i < w->len; ++i) {
128 ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
133 * Alloc a new workset on obstack @p ob with maximum size @p max
135 static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
137 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
138 res = obstack_alloc(ob, size);
139 memset(res, 0, size);
144 * Alloc a new instance on obstack and make it equal to @param ws
146 static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
148 size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
149 res = obstack_alloc(ob, size);
150 memcpy(res, ws, size);
155 * Do NOT alloc anything. Make @param tgt equal to @param src.
156 * returns @param tgt for convenience
158 static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
159 size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]);
160 memcpy(tgt, src, size);
165 * Overwrites the current content array of @param ws with the
166 * @param count locations given at memory @param locs.
167 * Set the length of @param ws to count.
169 static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
170 workset->len = count;
171 memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0]));
175 * Inserts the value @p val into the workset, iff it is not
176 * already contained. The workset must not be full.
178 static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
180 /* check for current regclass */
181 if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) {
182 DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
186 /* check if val is already contained */
187 for(i=0; i<ws->len; ++i)
188 if (ws->vals[i].irn == val)
192 assert(ws->len < env->n_regs && "Workset already full!");
193 ws->vals[ws->len++].irn = val;
197 * Removes all entries from this workset
199 static INLINE void workset_clear(workset_t *ws) {
204 * Removes the value @p val from the workset if present.
206 static INLINE void workset_remove(workset_t *ws, ir_node *val) {
208 for(i=0; i<ws->len; ++i) {
209 if (ws->vals[i].irn == val) {
210 ws->vals[i] = ws->vals[--ws->len];
216 static INLINE int workset_get_index(const workset_t *ws, const ir_node *val) {
218 for(i=0; i<ws->len; ++i) {
219 if (ws->vals[i].irn == val)
227 * Iterates over all values in the working set.
228 * @p ws The workset to iterate
229 * @p v A variable to put the current value in
230 * @p i An integer for internal use
232 #define workset_foreach(ws, v, i) for(i=0; \
233 v=(i < ws->len) ? ws->vals[i].irn : NULL, i < ws->len; \
236 #define workset_set_time(ws, i, t) (ws)->vals[i].time=t
237 #define workset_get_time(ws, i) (ws)->vals[i].time
238 #define workset_set_length(ws, length) (ws)->len = length
239 #define workset_get_length(ws) ((ws)->len)
240 #define workset_get_val(ws, i) ((ws)->vals[i].irn)
241 #define workset_sort(ws) qsort((ws)->vals, (ws)->len, sizeof((ws)->vals[0]), loc_compare);
242 #define workset_contains(ws, n) (workset_get_index(ws, n) >= 0)
244 typedef struct _block_use_t {
245 struct _block_use_t *next;
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;
256 workset_t *entrance_reg; /**< That set will contain all values
257 transported into the block which
258 are used before they are displaced.
259 That means, we later have to care to
260 bring them into the block in a register
261 or reload them at the entry of the block. */
263 workset_t * entrance_mem; /**< That set will contain all variables
264 (transported into the block)
265 which are in the memory upon entering
267 entrance_reg U entrance_mem = live-in + local phis. */
269 int pressure; /**< The amount of registers which remain free
270 in this block. This capacity can be used to let
271 global variables, transported into other blocks,
272 live through this block. */
274 double exec_freq; /**< The execution frequency of this block. */
278 static INLINE void *new_block_info(belady_env_t *bel, ir_node *bl) {
279 block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res));
280 memset(res, 0, sizeof(res[0]));
283 res->entrance_reg = new_workset(bel, &bel->ob);
284 res->exec_freq = get_block_execfreq(bel->ef, bl);
285 set_irn_link(bl, res);
289 #define get_block_info(block) ((block_info_t *)get_irn_link(block))
290 #define set_block_info(block, info) set_irn_link(block, info)
293 * @return The distance to the next use or 0 if irn has dont_spill flag set
295 static INLINE unsigned get_distance(belady_env_t *env, ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses)
298 int flags = arch_irn_get_flags(env->arch, def);
300 assert(! (flags & arch_irn_flags_ignore));
302 use = be_get_next_use(env->uses, from, from_step, def, skip_from_uses);
303 if(USES_IS_INFINITE(use.time))
304 return USES_INFINITY;
306 /* We have to keep nonspillable nodes in the workingset */
307 if(flags & arch_irn_flags_dont_spill)
314 * Check, if the value is something that is transported into a block.
315 * That is, the value is live in or defined by a Phi in the block.
316 * @param env The belady environment.
317 * @param bl The block in question.
318 * @param irn The node in question.
319 * @return 1, if node is something transported into @p bl, 0 if not.
321 static INLINE int is_transport_in(belady_env_t *env, const ir_node *bl, const ir_node *irn)
323 return (is_Phi(irn) && get_nodes_block(irn) == bl) || be_is_live_in(env->lv, bl, irn);
327 * Performs the actions necessary to grant the request that:
328 * - new_vals can be held in registers
329 * - as few as possible other values are disposed
330 * - the worst values get disposed
333 * Actually, we should displace a value immediately after it was used.
334 * If we don't, the cardinality of the workset does not reflect the register pressure.
335 * That might be necessary to determine the capacity left in the block.
337 * @p is_usage indicates that the values in new_vals are used (not defined)
338 * In this case reloads must be performed
340 static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) {
341 belady_env_t *env = bi->bel;
343 int i, len, max_allowed, demand, iter;
345 workset_t *ws = env->ws;
346 ir_node **to_insert = alloca(env->n_regs * sizeof(*to_insert));
349 1. Identify the number of needed slots and the values to reload
352 workset_foreach(new_vals, val, iter) {
353 /* mark value as used */
355 if (! workset_contains(ws, val)) {
356 DBG((dbg, DBG_DECIDE, " insert %+F\n", val));
357 to_insert[demand++] = val;
359 int insert_reload = 1;
362 * if we use a value which is transported in this block,
363 * i.e. a phi defined here or a live in, we check if there
364 * is room for that guy to survive from the block's entrance
367 if (is_transport_in(env, bi->bl, val)) {
368 DBG((dbg, DBG_SPILL, "entrance node %+F, capacity %d:\n", val, bi->pressure));
369 if (bi->pressure < env->n_regs) {
371 workset_insert(env, bi->entrance_reg, val);
373 DBG((dbg, DBG_SPILL, "... no reload. must be considered at block start\n"));
378 DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr));
379 be_add_reload(env->senv, val, env->instr, env->cls, 1);
384 assert(is_usage || "Defined value already in workset?!?");
385 DBG((dbg, DBG_DECIDE, " skip %+F\n", val));
388 DBG((dbg, DBG_DECIDE, " demand = %d\n", demand));
391 2. Make room for at least 'demand' slots
393 len = workset_get_length(ws);
394 max_allowed = env->n_regs - demand;
396 DBG((dbg, DBG_DECIDE, " disposing %d values\n", ws->len - max_allowed));
398 /* Only make more free room if we do not have enough */
399 if (len > max_allowed) {
400 /* get current next-use distance */
401 for (i = 0; i < ws->len; ++i) {
402 unsigned dist = get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage);
403 workset_set_time(ws, i, dist);
406 /* sort entries by increasing nextuse-distance*/
409 /* kill the last 'demand' entries in the array */
410 workset_set_length(ws, max_allowed);
414 3. Insert the new values into the workset
416 for (i = 0; i < demand; ++i)
417 workset_insert(env, env->ws, to_insert[i]);
421 * For the given block @p block, decide for each values
422 * whether it is used from a register or is reloaded
425 static void belady(ir_node *block, void *data) {
426 belady_env_t *env = data;
427 block_info_t *block_info = new_block_info(env, block);
432 /* process the block from start to end */
433 DBG((dbg, DBG_WSETS, "Processing...\n"));
435 new_vals = new_workset(env, &env->ob);
436 block_info->first_non_in = NULL;
438 sched_foreach(block, irn) {
440 assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!");
442 /* projs are handled with the tuple value.
443 * Phis are no real instr (see insert_starters())
444 * instr_nr does not increase */
445 if (is_Proj(irn) || is_Phi(irn)) {
446 DBG((dbg, DBG_DECIDE, " ...%+F skipped\n", irn));
449 DBG((dbg, DBG_DECIDE, " ...%+F\n", irn));
451 if (!block_info->first_non_in)
452 block_info->first_non_in = irn;
454 /* set instruction in the workset */
457 /* allocate all values _used_ by this instruction */
458 workset_clear(new_vals);
459 for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
460 workset_insert(env, new_vals, get_irn_n(irn, i));
462 displace(block_info, new_vals, 1);
464 /* allocate all values _defined_ by this instruction */
465 workset_clear(new_vals);
466 if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */
467 const ir_edge_t *edge;
469 foreach_out_edge(irn, edge) {
470 ir_node *proj = get_edge_src_irn(edge);
471 workset_insert(env, new_vals, proj);
474 workset_insert(env, new_vals, irn);
476 displace(block_info, new_vals, 0);
478 block_info->pressure = MAX(block_info->pressure, workset_get_length(env->ws));
482 /* Remember end-workset for this block */
483 block_info->ws_end = workset_clone(env, &env->ob, env->ws);
484 DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block));
485 workset_foreach(block_info->ws_end, irn, iter)
486 DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(block_info->ws_end, iter)));
491 |_ _| |__ ___ __ _| | ___ | |__ __ _| | | _ \ __ _ _ __| |_
492 | | | '_ \ / _ \ / _` | |/ _ \| '_ \ / _` | | | |_) / _` | '__| __|
493 | | | | | | __/ | (_| | | (_) | |_) | (_| | | | __/ (_| | | | |_
494 |_| |_| |_|\___| \__, |_|\___/|_.__/ \__,_|_| |_| \__,_|_| \__|
499 static int block_freq_gt(const void *a, const void *b)
501 const ir_node * const *p = a;
502 const ir_node * const *q = b;
503 block_info_t *pi = get_block_info(*p);
504 block_info_t *qi = get_block_info(*q);
505 return qi->exec_freq - pi->exec_freq;
508 typedef struct _block_end_state_t {
512 workset_t *end_state;
513 unsigned reload_at_end : 1;
514 unsigned live_through : 1;
517 typedef struct _global_end_state_t {
520 block_end_state_t *end_info;
523 } global_end_state_t;
525 static block_end_state_t *get_block_end_state(global_end_state_t *state, ir_node *bl, ir_node *irn)
529 for (i = 0; i < state->gauge; ++i) {
530 block_end_state_t *bei = &state->end_info[i];
531 if (bei->bl == bl && bei->irn == irn)
536 block_info_t *bi = get_block_info(bl);
537 block_end_state_t *curr;
539 /* make sure we have room in the array */
540 ARR_EXTO(block_end_state_t, state->end_info, (int) state->gauge);
542 curr = &state->end_info[state->gauge];
544 memset(curr, 0, sizeof(curr[0]));
547 curr->end_state = workset_clone(state->env, &state->obst, bi->ws_end);
554 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level);
556 static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
558 block_end_state_t *bes = get_block_end_state(ges, bl, irn);
559 workset_t *end = bes->end_state;
560 block_info_t *bi = get_block_info(bl);
561 int n_regs = bi->bel->n_regs;
564 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}can make avail %+F at end of %+F (pressure %d)\n",
565 level, irn, bl, bi->pressure));
568 * to make the value available at end,
569 * we have several cases here.
571 * - we already visited that block.
572 * - If the value is in the final end set, return 0.
573 * somebody else already allocated it there.
574 * - If not and the final end set is already full,
575 * we cannot make the value available at the end
576 * of this block. return INFINITY.
577 * - Else (value not in final end set and there is room):
578 * 1) The value is in a register at the end of the local Belady pass.
579 * Allocate a slot in the final end set and return 0.
580 * 2) The value is not in the Belady end set:
581 * If the block's capacity is < k then check what it costs
582 * to transport the value from upper blocks to this block.
583 * Compare that against the reload cost in this block. If
584 * cheaper, do the other thing. If not, reload it here.
588 * we have been here before and already figured out some costs.
589 * so we can exit safely.
591 if (bes->costs >= 0.0) {
592 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}we\'ve been here before\n", level));
596 /* if the end set contains it already, it is in a reg and it costs nothing
597 * to load it to one. */
598 index = workset_get_index(end, irn);
600 unsigned ver = end->vals[index].version;
601 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}node is in the end set and is %s fixed\n",
602 level, ver > ges->version ? "" : "not"));
605 * if the version is older, the value is already fixed
606 * and cannot be removed from the end set. If not,
607 * we fix it here by giving it our version.
609 if (ver < ges->version)
610 end->vals[index].version = ges->version;
617 * Now we have two options:
618 * 1) Reload the value at the end of the block.
619 * Therefore, perhaps, we have to erase another one from the workset.
620 * This may only be done if it has not been fixed.
621 * Since fixed means that a previous pass has decided that that value
622 * *has* to stay in the end set.
623 * 2) we can try, if the capacity of the block allows it, to let
624 * the value live through the block and make it available at
627 * First, we test the local (reload in this block) alternative
628 * and compare against the other alternative.
629 * Of course, we chose the cheaper one.
633 int len = workset_get_length(end);
637 bes->costs = HUGE_VAL;
640 * look if there is room in the end array
641 * for the variable. Note that this does not
642 * means that the var is living through the block.
643 * There is just room at the *end*
646 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}the end set has %d free slots\n",
647 level, n_regs - len));
651 for (i = 0; i < len; ++i)
652 if (end->vals[i].version < ges->version)
656 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}%+F (slot %d) can be erased from the end set\n",
657 level, end->vals[i].irn, i));
663 int gauge = ges->gauge;
664 double reload_here = get_block_execfreq(bi->bel->ef, bl);
665 double bring_in = bi->pressure < n_regs ? can_bring_in(ges, bl, irn, level + 1) : HUGE_VAL;
667 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}there is a free slot. capacity=%d, reload here=%f, bring in=%f\n",
668 level, n_regs - bi->pressure, reload_here, bring_in));
671 * reloading here pays off; bringing the value in from elsewhere
672 * is too expensive, hence we drop that search by resetting
675 if (reload_here <= bring_in) {
677 bes->costs = reload_here;
678 bes->reload_at_end = 1;
682 bes->live_through = 1;
683 bes->costs = bring_in;
689 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}-> %f\n", level, bes->costs));
693 static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, int level)
695 double glob_costs = HUGE_VAL;
696 int def_block = bl == get_nodes_block(irn);
697 int phi = is_Phi(irn);
699 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}can bring in for %+F at block %+F\n", level, irn, bl));
701 if (phi || !def_block) {
702 int i, n = get_irn_arity(bl);
703 ir_node **nodes = alloca(get_irn_arity(bl) * sizeof(nodes[0]));
705 int gauge_begin = ges->gauge;
708 for (i = 0; i < n; ++i) {
709 ir_node *pr = get_Block_cfgpred_block(bl, i);
710 ir_node *op = phi && def_block ? get_irn_n(irn, i) : irn;
711 double c = can_make_available_at_end(ges, pr, op, level + 1);
714 ges->gauge = gauge_begin;
715 glob_costs = HUGE_VAL;
724 DBG((dbg, DBG_GLOBAL, "\t%{firm:indent}-> %f\n", level, glob_costs));
728 static void materialize_and_commit_end_state(global_end_state_t *ges)
730 belady_env_t *env = ges->env;
733 DBG((dbg, DBG_GLOBAL, "\tmaterializing\n"));
734 for (i = 0; i < ges->gauge; ++i) {
735 block_end_state_t *bes = &ges->end_info[i];
736 block_info_t *bi = get_block_info(bes->bl);
739 /* insert the reload if the val was reloaded at the block's end */
740 if (bes->reload_at_end) {
741 be_add_reload(env->senv, bes->irn, bes->bl, env->cls, 1);
742 DBG((dbg, DBG_GLOBAL, "\t\tadding reload of %+F at end of %+F\n", bes->irn, bes->bl));
746 * if the variable is live through the block,
747 * update the pressure indicator.
749 bi->pressure += bes->live_through;
751 idx = workset_get_index(bes->end_state, bes->irn);
754 * set the version number in the workset.
755 * That will mark this value as fixed in the end set
756 * and will prevent further investigations from removing
758 * Also "commit" the workset;
759 * by copying it back to the block's end workset.
762 DBG((dbg, DBG_GLOBAL, "\t\tcommiting workset of %+F with version %x\n", bes->bl, ges->version));
763 bes->end_state->vals[idx].version = ges->version;
764 workset_copy(env, bi->ws_end, bes->end_state);
770 * Examine all irns which shall be in regs at the beginning of the
773 static void fix_block_borders(global_end_state_t *ges, ir_node *block) {
774 block_info_t *bi = get_block_info(block);
775 belady_env_t *env = ges->env;
780 DBG((dbg, DBG_GLOBAL, "fixing block borders at %+F (%fHz)\n", block, bi->exec_freq));
782 /* process all variables which shall be in a reg at
783 * the beginning of the block in the order of the next use. */
784 workset_foreach(bi->entrance_reg, irn, i) {
785 double bring_in_costs;
787 /* reset the gauge and begin the search */
791 DBG((dbg, DBG_GLOBAL, "\ttrans in var %+F, version %x\n", irn, ges->version));
793 bring_in_costs = can_bring_in(ges, block, irn, 0);
795 /* we were not able to let the value arrive
796 * in a register at the entrance of the block
797 * so we have to do the reload locally */
798 if (bring_in_costs >= HUGE_VAL) {
799 if (is_Phi(irn) && get_nodes_block(irn) == block)
800 be_spill_phi(env->senv, irn);
802 be_add_reload(env->senv, irn, bi->first_non_in, env->cls, 1);
806 materialize_and_commit_end_state(ges);
810 static void global_assign(belady_env_t *env)
812 global_end_state_t ges;
815 obstack_init(&ges.obst);
819 ges.end_info = NEW_ARR_F(block_end_state_t, env->n_blocks);
822 * sort the blocks according to execution frequency.
823 * That's not necessary for belady() but for the global pass later on.
825 qsort(env->blocks, env->n_blocks, sizeof(env->blocks[0]), block_freq_gt);
827 for (i = 0; i < env->n_blocks; ++i)
828 fix_block_borders(&ges, env->blocks[i]);
831 static void collect_blocks(ir_node *bl, void *data)
833 belady_env_t *env = data;
835 obstack_ptr_grow(&env->ob, bl);
838 void be_spill_belady_spill_env2(be_irg_t *birg, const arch_register_class_t *cls, spill_env_t *spill_env) {
840 ir_graph *irg = be_get_birg_irg(birg);
843 /* some special classes contain only ignore regs, nothing to do then */
844 n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
850 /* init belady env */
851 obstack_init(&env.ob);
852 env.arch = birg->main_env->arch_env;
854 env.lv = be_get_birg_liveness(birg);
856 env.ws = new_workset(&env, &env.ob);
857 env.uses = be_begin_uses(irg, env.lv);
858 env.senv = spill_env ? spill_env : be_new_spill_env(birg);
859 env.ef = be_get_birg_exec_freq(birg);
862 irg_block_walk_graph(irg, NULL, collect_blocks, &env);
863 obstack_ptr_grow(&env.ob, NULL);
864 env.blocks = obstack_finish(&env.ob);
866 /* Fix high register pressure with belady algorithm */
867 for (i = 0; i < env.n_blocks; ++i)
868 belady(env.blocks[i], &env);
872 /* Insert spill/reload nodes into the graph and fix usages */
873 be_insert_spills_reloads(env.senv);
876 if(spill_env == NULL)
877 be_delete_spill_env(env.senv);
878 be_end_uses(env.uses);
879 obstack_free(&env.ob, NULL);
884 * Do spilling for a register class on a graph using the belady heuristic.
885 * In the transformed graph, the register pressure never exceeds the number
886 * of available registers.
888 * @param birg The backend graph
889 * @param cls The register class to spill
891 static void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) {
892 be_spill_belady_spill_env2(birg, cls, NULL);
896 void be_init_spillbelady2(void)
898 static be_spiller_t belady_spiller = {
902 be_register_spiller("belady2", &belady_spiller);
903 FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2");
906 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2);