X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady3.c;h=ad3f50b3ce746cbb26ef4b344eaade6e38aef880;hb=248729a36ccf67f00f7b29a02562b0e72df8923a;hp=32f9ef20d70b153df9203f2f1b8a5b513c3ccddc;hpb=cd038d3027364295ee3056eebc9929b55f4514ef;p=libfirm diff --git a/ir/be/bespillbelady3.c b/ir/be/bespillbelady3.c index 32f9ef20d..ad3f50b3c 100644 --- a/ir/be/bespillbelady3.c +++ b/ir/be/bespillbelady3.c @@ -25,8 +25,8 @@ * @version $Id$ * * TODO: - * - handle phis correctly, decide wether we should spill them - * - merge multiple start worksets of blocks + * - handle phis correctly, decide wether we should spill them ~ok + * - merge multiple start worksets of blocks ~ok * - how to and when to do the tentative phase... */ #ifdef HAVE_CONFIG_H @@ -55,15 +55,14 @@ typedef struct worklist_entry_t worklist_entry_t; struct worklist_entry_t { struct list_head head; ir_node *value; - unsigned timestep; ir_node *reload_point; + worklist_entry_t *next_reload; }; typedef struct worklist_t worklist_t; struct worklist_t { struct list_head live_values; size_t n_live_values; - unsigned current_timestep; }; static const arch_env_t *arch_env; @@ -74,11 +73,14 @@ static size_t n_regs; static int tentative_mode; static ir_exec_freq *exec_freq; -static void init_worklist(worklist_t *worklist, unsigned timestep) +static worklist_t *new_worklist(void) { + worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0])); + INIT_LIST_HEAD(&worklist->live_values); worklist->n_live_values = 0; - worklist->current_timestep = timestep; + + return worklist; } static void mark_irn_not_visited(ir_node *node) @@ -99,59 +101,55 @@ static void deactivate_worklist(const worklist_t *worklist) } } -static void activate_worklist(const worklist_t *worklist) -{ - struct list_head *entry; - - list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - ir_node *value = wl_entry->value; - - assert(irn_not_visited(value)); - mark_irn_visited(value); - set_irn_link(value, wl_entry); - } -} - -static worklist_t *duplicate_worklist(const worklist_t *worklist, - ir_node *block, - ir_node *succ_block, int succ_pos) +/** + * duplicate a worklist and directly activates it + */ +static worklist_t *duplicate_activate_worklist(const worklist_t *worklist, + ir_node *block, ir_node *succ_block, int succ_pos) { - ir_node *reload_point = NULL; + ir_node *reload_point = NULL; + size_t n_live_values = 0; + worklist_t *new_worklist; struct list_head *entry; - worklist_t *new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0])); - - INIT_LIST_HEAD(&new_worklist->live_values); if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) { reload_point = be_get_end_of_block_insertion_point(block); } - new_worklist->current_timestep = worklist->current_timestep; - new_worklist->n_live_values = worklist->n_live_values; + new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0])); + INIT_LIST_HEAD(&new_worklist->live_values); list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); + worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head); + ir_node *value = wl_entry->value; worklist_entry_t *new_entry = obstack_alloc(&obst, sizeof(new_entry[0])); - ir_node *value = wl_entry->value; if(is_Phi(value) && get_nodes_block(value) == succ_block) { value = get_Phi_pred(value, succ_pos); } - new_entry->value = value; - new_entry->timestep = wl_entry->timestep; + new_entry->value = value; if(reload_point != NULL) { new_entry->reload_point = reload_point; } else { new_entry->reload_point = wl_entry->reload_point; } + new_entry->next_reload = NULL; + + if(irn_not_visited(value)) { + list_add_tail(&new_entry->head, &new_worklist->live_values); + ++n_live_values; - list_add_tail(&new_entry->head, &new_worklist->live_values); + mark_irn_visited(value); + set_irn_link(value, new_entry); + } else { + /* the only way we might visit a value again, is when we get it as + * phi predecessor */ + assert(is_Phi(wl_entry->value)); + } } + new_worklist->n_live_values = n_live_values; return new_worklist; } @@ -161,14 +159,11 @@ static void print_worklist(const worklist_t *worklist, int level) { struct list_head *entry; - DB((dbg, level, "%d values (TS %u): ", worklist->n_live_values, - worklist->current_timestep)); + DB((dbg, level, "%d values: ", worklist->n_live_values)); list_for_each(entry, &worklist->live_values) { worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head); - //DB((dbg, level, "%+F(%+F) ", wl_entry->value, - // wl_entry->reload_point)); DB((dbg, level, "%+F ", wl_entry->value)); } } @@ -178,24 +173,57 @@ static void place_reload(worklist_entry_t *entry) { if(tentative_mode) return; - DB((dbg, LEVEL_1, "reload of %+F before %+F", entry->value, - entry->reload_point)); - be_add_reload(senv, entry->value, entry->reload_point, cls, 1); + + /* walk list of reload points */ + do { + DB((dbg, LEVEL_1, "reload of %+F before %+F\n", entry->value, + entry->reload_point)); + assert(entry->reload_point != NULL); + be_add_reload(senv, entry->value, entry->reload_point, cls, 1); + entry->reload_point = NULL; + + entry = entry->next_reload; + } while(entry != NULL); } -static void spill_non_live_nodes(const worklist_t *worklist) +/** + * does stuff required for non-active worklists: spills all values not live + * in the active worklist; links live values to the current worklist + */ +static void process_non_active_worklist(const worklist_t *worklist, + worklist_t *current_worklist) { struct list_head *entry; list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - ir_node *value = wl_entry->value; - - if(irn_visited(value)) - continue; - - place_reload(wl_entry); + worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head); + ir_node *value = wl_entry->value; + + if(!irn_visited(value)) { + /* if we still have room in the worklist, then we can simply take + * the value */ + if(current_worklist->n_live_values < n_regs) { + worklist_entry_t *new_entry + = obstack_alloc(&obst, sizeof(new_entry[0])); + + new_entry->value = value; + new_entry->reload_point = wl_entry->reload_point; + new_entry->next_reload = wl_entry->next_reload; + set_irn_link(value, new_entry); + mark_irn_visited(value); + list_add(&new_entry->head, ¤t_worklist->live_values); + ++current_worklist->n_live_values; + } else { + /* value is not in current worklist, place reloads */ + place_reload(wl_entry); + } + } else { + /* value is in current worklist, link it with the reload point + * from this path */ + worklist_entry_t *active_entry = get_irn_link(value); + wl_entry->next_reload = active_entry->next_reload; + active_entry->next_reload = wl_entry; + } } } @@ -247,8 +275,8 @@ static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point) mark_irn_visited(value); } - entry->timestep = worklist->current_timestep; entry->reload_point = sched_point; + entry->next_reload = NULL; list_add_tail(&entry->head, &worklist->live_values); } @@ -269,12 +297,6 @@ static void do_spilling(ir_node *block, worklist_t *worklist) assert(worklist != NULL); -#ifdef DEBUG_libfirm - DB((dbg, LEVEL_1, "worklist at end of %+F:", block)); - print_worklist(worklist, LEVEL_1); - DB((dbg, LEVEL_1, "\n")); -#endif - sched_foreach_reverse(block, node) { int i, arity; size_t n_defs = 0; @@ -296,7 +318,8 @@ static void do_spilling(ir_node *block, worklist_t *worklist) if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node2)) continue; - be_spill_phi(senv, node2); + if(!tentative_mode) + be_spill_phi(senv, node2); } break; } @@ -342,8 +365,6 @@ static void do_spilling(ir_node *block, worklist_t *worklist) * some */ make_room(worklist, 0); - ++worklist->current_timestep; - #ifdef DEBUG_libfirm print_worklist(worklist, LEVEL_2); DB((dbg, LEVEL_2, "\n")); @@ -385,27 +406,37 @@ static void process_block(ir_node *block, void *env) } } if(worklist == NULL) { - /* only the end-block has 0 successors */ - assert(block == get_irg_end_block(get_irn_irg(block))); + /* at least 1 successor block must have been processed unless it was + * the end block */ + assert(tentative_mode || block == get_irg_end_block(get_irn_irg(block))); - worklist = obstack_alloc(&obst, sizeof(worklist[0])); - init_worklist(worklist, 0); + worklist = new_worklist(); +#ifdef DEBUG_libfirm + DB((dbg, LEVEL_1, "worklist at end of %+F:", block)); + print_worklist(worklist, LEVEL_1); + DB((dbg, LEVEL_1, "\n")); +#endif } else { - worklist = duplicate_worklist(worklist, block, best_succ_block, - best_pos); - activate_worklist(worklist); + worklist = duplicate_activate_worklist(worklist, block, best_succ_block, + best_pos); /* now we could have live values in the succ worklists that are not - * live anymore in the worklist we picked. We need reloads for them. - */ - if(!tentative_mode) { - foreach_block_succ(block, edge) { - ir_node *succ_block = get_edge_src_irn(edge); - worklist_t *succ_worklist = get_irn_link(succ_block); - - spill_non_live_nodes(succ_worklist); - } + * live anymore in the worklist we picked. We need reloads for them. */ + foreach_block_succ(block, edge) { + ir_node *succ_block = get_edge_src_irn(edge); + worklist_t *succ_worklist = get_irn_link(succ_block); + + if(succ_block == best_succ_block) + continue; + + process_non_active_worklist(succ_worklist, worklist); } + +#ifdef DEBUG_libfirm + DB((dbg, LEVEL_1, "worklist at end of %+F:", block)); + print_worklist(worklist, LEVEL_1); + DB((dbg, LEVEL_1, "\n")); +#endif } do_spilling(block, worklist); @@ -430,7 +461,6 @@ static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls) arch_env = be_get_birg_arch_env(birg); exec_freq = be_get_birg_exec_freq(birg); - tentative_mode = 0; be_clear_links(irg); set_using_irn_link(irg); @@ -442,6 +472,13 @@ static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls) /* do a post-order walk over the CFG to make sure we have a maximum number * of preds processed before entering a block */ + tentative_mode = 1; + irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL); + + tentative_mode = 1; + irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL); + + tentative_mode = 0; irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL); clear_using_irn_link(irg);