X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady3.c;h=54a7564ec75832dbca36abd5b41be149e6633d4c;hb=89dc24503c04139bb05504059b291d6d89f99661;hp=29a196a59d38eec7ac088af8172ab758f635ac78;hpb=6a172145427beca7a9e54d4edd0c23394525d9a6;p=libfirm diff --git a/ir/be/bespillbelady3.c b/ir/be/bespillbelady3.c index 29a196a59..54a7564ec 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 @@ -74,11 +74,15 @@ 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; + worklist->current_timestep = 0; + + return worklist; } static void mark_irn_not_visited(ir_node *node) @@ -99,44 +103,28 @@ 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) +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; if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) { + ir_fprintf(stderr, "adjust reload point from %+F to %+F\n", succ_block, block); reload_point = be_get_end_of_block_insertion_point(block); } - worklist_t *new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0])); + new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0])); INIT_LIST_HEAD(&new_worklist->live_values); - new_worklist->current_timestep = worklist->current_timestep; - new_worklist->n_live_values = worklist->n_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); @@ -150,8 +138,19 @@ static worklist_t *duplicate_worklist(const worklist_t *worklist, new_entry->reload_point = wl_entry->reload_point; } - list_add_tail(&new_entry->head, &new_worklist->live_values); + if(irn_not_visited(value)) { + list_add_tail(&new_entry->head, &new_worklist->live_values); + ++n_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; } @@ -167,8 +166,6 @@ static void print_worklist(const worklist_t *worklist, int level) 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)); } } @@ -296,7 +293,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; } @@ -361,15 +359,15 @@ static void process_block(ir_node *block, void *env) { int n_preds; const ir_edge_t *edge; - (void) env; + worklist_t *worklist = NULL; + double best_execfreq = -1; + ir_node *best_succ_block = NULL; + int best_pos = -1; + (void) env; DB((dbg, LEVEL_1, "Processing %+F\n", block)); /* construct worklist */ - worklist_t *worklist = NULL; - double best_execfreq = -1; - ir_node *best_succ_block = NULL; - int best_pos = -1; foreach_block_succ(block, edge) { ir_node *succ_block = get_edge_src_irn(edge); double execfreq = get_block_execfreq(exec_freq, succ_block); @@ -385,19 +383,17 @@ 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(); } 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. - */ + * 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); @@ -430,7 +426,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 +437,10 @@ 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 = 0; irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL); clear_using_irn_link(irg);