2 * Copyright (C) 1995-2008 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 MIN-algorithm with some twists (aka belady spiller v3)
23 * @author Matthias Braun
28 * - handle phis correctly, decide wether we should spill them ~ok
29 * - merge multiple start worksets of blocks ~ok
30 * - how to and when to do the tentative phase...
42 #include "iredges_t.h"
48 #include "bespilloptions.h"
49 #include "besched_t.h"
52 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
54 typedef struct worklist_entry_t worklist_entry_t;
55 struct worklist_entry_t {
56 struct list_head head;
58 ir_node *reload_point;
59 worklist_entry_t *next_reload;
62 typedef struct worklist_t worklist_t;
64 struct list_head live_values;
68 static const arch_env_t *arch_env;
69 static const arch_register_class_t *cls;
70 static struct obstack obst;
71 static spill_env_t *senv;
73 static int tentative_mode;
74 static ir_exec_freq *exec_freq;
76 static worklist_t *new_worklist(void)
78 worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0]));
80 INIT_LIST_HEAD(&worklist->live_values);
81 worklist->n_live_values = 0;
86 static void mark_irn_not_visited(ir_node *node)
88 set_irn_visited(node, get_irg_visited(current_ir_graph) - 1);
91 static void deactivate_worklist(const worklist_t *worklist)
93 struct list_head *entry;
95 list_for_each(entry, &worklist->live_values) {
96 worklist_entry_t *wl_entry
97 = list_entry(entry, worklist_entry_t, head);
98 assert(irn_visited(wl_entry->value));
99 mark_irn_not_visited(wl_entry->value);
100 set_irn_link(wl_entry->value, NULL);
105 * duplicate a worklist and directly activates it
107 static worklist_t *duplicate_activate_worklist(const worklist_t *worklist,
108 ir_node *block, ir_node *succ_block, int succ_pos)
110 ir_node *reload_point = NULL;
111 size_t n_live_values = 0;
112 worklist_t *new_worklist;
113 struct list_head *entry;
115 if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) {
116 reload_point = be_get_end_of_block_insertion_point(block);
119 new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
120 INIT_LIST_HEAD(&new_worklist->live_values);
122 list_for_each(entry, &worklist->live_values) {
123 worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
124 ir_node *value = wl_entry->value;
125 worklist_entry_t *new_entry
126 = obstack_alloc(&obst, sizeof(new_entry[0]));
128 if(is_Phi(value) && get_nodes_block(value) == succ_block) {
129 value = get_Phi_pred(value, succ_pos);
132 new_entry->value = value;
133 if(reload_point != NULL) {
134 new_entry->reload_point = reload_point;
136 new_entry->reload_point = wl_entry->reload_point;
138 new_entry->next_reload = NULL;
140 if(irn_not_visited(value)) {
141 list_add_tail(&new_entry->head, &new_worklist->live_values);
144 mark_irn_visited(value);
145 set_irn_link(value, new_entry);
147 /* the only way we might visit a value again, is when we get it as
149 assert(is_Phi(wl_entry->value));
152 new_worklist->n_live_values = n_live_values;
158 static void print_worklist(const worklist_t *worklist, int level)
160 struct list_head *entry;
162 DB((dbg, level, "%d values: ", worklist->n_live_values));
163 list_for_each(entry, &worklist->live_values) {
164 worklist_entry_t *wl_entry
165 = list_entry(entry, worklist_entry_t, head);
167 DB((dbg, level, "%+F ", wl_entry->value));
172 static void place_reload(worklist_entry_t *entry)
177 /* walk list of reload points */
179 DB((dbg, LEVEL_1, "reload of %+F before %+F\n", entry->value,
180 entry->reload_point));
181 assert(entry->reload_point != NULL);
182 be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
183 entry->reload_point = NULL;
185 entry = entry->next_reload;
186 } while(entry != NULL);
190 * does stuff required for non-active worklists: spills all values not live
191 * in the active worklist; links live values to the current worklist
193 static void process_non_active_worklist(const worklist_t *worklist,
194 worklist_t *current_worklist)
196 struct list_head *entry;
198 list_for_each(entry, &worklist->live_values) {
199 worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
200 ir_node *value = wl_entry->value;
202 if(!irn_visited(value)) {
203 /* if we still have room in the worklist, then we can simply take
205 if(current_worklist->n_live_values < n_regs) {
206 worklist_entry_t *new_entry
207 = obstack_alloc(&obst, sizeof(new_entry[0]));
209 new_entry->value = value;
210 new_entry->reload_point = wl_entry->reload_point;
211 new_entry->next_reload = wl_entry->next_reload;
212 set_irn_link(value, new_entry);
213 mark_irn_visited(value);
214 list_add(&new_entry->head, ¤t_worklist->live_values);
215 ++current_worklist->n_live_values;
217 /* value is not in current worklist, place reloads */
218 place_reload(wl_entry);
221 /* value is in current worklist, link it with the reload point
223 worklist_entry_t *active_entry = get_irn_link(value);
224 wl_entry->next_reload = active_entry->next_reload;
225 active_entry->next_reload = wl_entry;
231 * makes sure the worklist contains not more than n_regs - room_needed entries
233 static void make_room(worklist_t *worklist, size_t room_needed)
235 int spills_needed = worklist->n_live_values + room_needed - n_regs;
236 if(spills_needed > 0) {
237 int i = spills_needed;
238 struct list_head *entry = worklist->live_values.next;
239 for(i = spills_needed; i > 0; --i) {
240 struct list_head *next = entry->next;
241 worklist_entry_t *wl_entry
242 = list_entry(entry, worklist_entry_t, head);
243 assert(irn_visited(wl_entry->value));
244 mark_irn_not_visited(wl_entry->value);
245 place_reload(wl_entry);
250 worklist->n_live_values -= spills_needed;
255 * a value was used, so bring it to the back of the worklist (which might
256 * result in a spill of another value).
258 static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point)
260 /* is the node in the worklist already? */
261 worklist_entry_t *entry = get_irn_link(value);
262 if(irn_visited(value)) {
263 assert(entry != NULL);
265 assert(irn_visited(value));
266 list_del(&entry->head);
269 entry = obstack_alloc(&obst, sizeof(entry[0]));
270 entry->value = value;
271 set_irn_link(value, entry);
274 ++worklist->n_live_values;
275 mark_irn_visited(value);
278 entry->reload_point = sched_point;
279 entry->next_reload = NULL;
280 list_add_tail(&entry->head, &worklist->live_values);
283 static void worklist_remove(worklist_t *worklist, ir_node *value)
285 worklist_entry_t *entry = get_irn_link(value);
286 assert(entry != NULL);
287 list_del(&entry->head);
288 --worklist->n_live_values;
290 assert(irn_visited(value));
291 mark_irn_not_visited(value);
294 static void do_spilling(ir_node *block, worklist_t *worklist)
298 assert(worklist != NULL);
300 sched_foreach_reverse(block, node) {
304 DB((dbg, LEVEL_2, "\t%+F... ", node));
308 /* TODO: if we have some free registers, then we could decide to
309 * not spill some phis (but not for phis where at least 1 input is
312 /* we have to spill all phis that are not live */
313 sched_foreach_reverse_from(node, node2) {
314 assert(is_Phi(node2));
316 if(irn_visited(node2))
318 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node2))
322 be_spill_phi(senv, node2);
327 /* remove values defined by this instruction from the workset. Values
328 * defined but not in the workset need free registers */
329 if(get_irn_mode(node) == mode_T) {
330 const ir_edge_t *edge;
332 foreach_out_edge(node, edge) {
333 ir_node *proj = get_edge_src_irn(edge);
334 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, proj))
336 if(irn_visited(proj)) {
337 worklist_remove(worklist, proj);
342 } else if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
343 if(irn_visited(node)) {
344 worklist_remove(worklist, node);
350 /* make sure we have enough free registers for the spills */
351 make_room(worklist, n_defs);
353 /* put all values by the instruction into the workset */
354 arity = get_irn_arity(node);
355 for(i = 0; i < arity; ++i) {
356 ir_node *use = get_irn_n(node, i);
358 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, use))
361 val_used(worklist, use, node);
364 /* we might have too many values in the worklist now and need to spill
366 make_room(worklist, 0);
369 print_worklist(worklist, LEVEL_2);
370 DB((dbg, LEVEL_2, "\n"));
375 DB((dbg, LEVEL_1, "worklist at begin of %+F:", block));
376 print_worklist(worklist, LEVEL_1);
377 DB((dbg, LEVEL_1, "\n"));
381 static void process_block(ir_node *block, void *env)
384 const ir_edge_t *edge;
385 worklist_t *worklist = NULL;
386 double best_execfreq = -1;
387 ir_node *best_succ_block = NULL;
391 DB((dbg, LEVEL_1, "Processing %+F\n", block));
393 /* construct worklist */
394 foreach_block_succ(block, edge) {
395 ir_node *succ_block = get_edge_src_irn(edge);
396 double execfreq = get_block_execfreq(exec_freq, succ_block);
398 if(execfreq > best_execfreq) {
399 worklist_t *succ_worklist = get_irn_link(succ_block);
400 if(succ_worklist != NULL) {
401 best_execfreq = execfreq;
402 worklist = succ_worklist;
403 best_succ_block = succ_block;
404 best_pos = get_edge_src_pos(edge);
408 if(worklist == NULL) {
409 /* at least 1 successor block must have been processed unless it was
411 assert(tentative_mode || block == get_irg_end_block(get_irn_irg(block)));
413 worklist = new_worklist();
415 DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
416 print_worklist(worklist, LEVEL_1);
417 DB((dbg, LEVEL_1, "\n"));
420 worklist = duplicate_activate_worklist(worklist, block, best_succ_block,
423 /* now we could have live values in the succ worklists that are not
424 * live anymore in the worklist we picked. We need reloads for them. */
425 foreach_block_succ(block, edge) {
426 ir_node *succ_block = get_edge_src_irn(edge);
427 worklist_t *succ_worklist = get_irn_link(succ_block);
429 if(succ_block == best_succ_block)
432 process_non_active_worklist(succ_worklist, worklist);
436 DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
437 print_worklist(worklist, LEVEL_1);
438 DB((dbg, LEVEL_1, "\n"));
442 do_spilling(block, worklist);
443 deactivate_worklist(worklist);
445 set_irn_link(block, worklist);
447 /* we shouldn't have any live values left at the start block */
448 n_preds = get_Block_n_cfgpreds(block);
449 assert(n_preds != 0 || worklist->n_live_values == 0);
452 static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls)
454 ir_graph *irg = be_get_birg_irg(birg);
457 n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
462 arch_env = be_get_birg_arch_env(birg);
463 exec_freq = be_get_birg_exec_freq(birg);
466 set_using_irn_link(irg);
467 set_using_irn_visited(irg);
468 inc_irg_visited(irg);
471 senv = be_new_spill_env(birg);
473 /* do a post-order walk over the CFG to make sure we have a maximum number
474 * of preds processed before entering a block */
476 irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
479 irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
482 irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
484 clear_using_irn_link(irg);
485 clear_using_irn_visited(irg);
487 be_insert_spills_reloads(senv);
489 obstack_free(&obst, NULL);
492 be_delete_spill_env(senv);
495 void be_init_spillbelady3(void)
497 static be_spiller_t belady3_spiller = {
501 be_register_spiller("belady3", &belady3_spiller);
502 FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady3");
505 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady3);