X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady3.c;h=2bac5bba474eb78216ef908c45d63721b529b2da;hb=0378ccc621a98322785250f96d85d3b32dc0cad1;hp=1b4d40c7dc74fff5d97635ed9ed36137cbb05232;hpb=fcb579b8959da1d7563b1a7b9f008a423ffdf75a;p=libfirm diff --git a/ir/be/bespillbelady3.c b/ir/be/bespillbelady3.c index 1b4d40c7d..2bac5bba4 100644 --- a/ir/be/bespillbelady3.c +++ b/ir/be/bespillbelady3.c @@ -29,9 +29,7 @@ * - merge multiple start worksets of blocks ~ok * - how to and when to do the tentative phase... */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include @@ -49,8 +47,8 @@ #include "bemodule.h" #include "bespill.h" #include "beutil.h" -#include "bespilloptions.h" -#include "besched_t.h" +#include "bespillutil.h" +#include "besched.h" #include "be_t.h" #ifndef NDEBUG @@ -82,6 +80,8 @@ struct worklist_entry_t { ir_loop *unused_livethrough_loop; }; +#define foreach_worklist(entry, wl) list_for_each_entry(worklist_entry_t, entry, &(wl)->live_values, head) + typedef struct worklist_t worklist_t; struct worklist_t { struct list_head live_values; @@ -95,21 +95,24 @@ struct block_info_t { worklist_t *end_worklist; }; +/** The register class we currently run on. */ static const arch_register_class_t *cls; static struct obstack obst; static spill_env_t *senv; static size_t n_regs; static size_t max_register_pressure; static bool tentative_mode; -static bool should_have_reached_fixpoint; static bool do_push_unused_livethroughs; +/** Execution frequency for the current graph. */ static ir_exec_freq *exec_freq; static ir_visited_t worklist_visited; +#ifdef DEBUG_libfirm +static bool should_have_reached_fixpoint; +#endif static worklist_t *new_worklist(void) { - worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0])); - memset(worklist, 0, sizeof(worklist[0])); + worklist_t *worklist = OALLOCZ(&obst, worklist_t); INIT_LIST_HEAD(&worklist->live_values); worklist->n_live_values = 0; @@ -133,35 +136,30 @@ static block_info_t *get_block_info(ir_node *block) if (info != NULL) return info; - info = obstack_alloc(&obst, sizeof(info[0])); - memset(info, 0, sizeof(info[0])); + info = OALLOCZ(&obst, block_info_t); set_irn_link(block, info); return info; } static void deactivate_worklist(const worklist_t *worklist) { - struct list_head *entry; + worklist_entry_t *entry; - list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - assert(worklist_contains(wl_entry->value)); - mark_irn_not_visited(wl_entry->value); - set_irn_link(wl_entry->value, NULL); + foreach_worklist(entry, worklist) { + assert(worklist_contains(entry->value)); + mark_irn_not_visited(entry->value); + set_irn_link(entry->value, NULL); } } static void activate_worklist(const worklist_t *worklist) { - struct list_head *entry; + worklist_entry_t *entry; - list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - assert(!worklist_contains(wl_entry->value)); - mark_irn_visited(wl_entry->value); - set_irn_link(wl_entry->value, wl_entry); + foreach_worklist(entry, worklist) { + assert(!worklist_contains(entry->value)); + mark_irn_visited(entry->value); + set_irn_link(entry->value, entry); } } @@ -174,7 +172,7 @@ static void fill_and_activate_worklist(worklist_t *new_worklist, { ir_node *reload_point = NULL; size_t n_live_values = 0; - struct list_head *entry; + worklist_entry_t *entry; if (succ_block != NULL && (get_Block_n_cfgpreds(succ_block) > 1 @@ -182,9 +180,8 @@ static void fill_and_activate_worklist(worklist_t *new_worklist, reload_point = be_get_end_of_block_insertion_point(block); } - 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; + foreach_worklist(entry, worklist) { + ir_node *value = entry->value; worklist_entry_t *new_entry; if (new_worklist->n_live_values >= n_regs) @@ -201,14 +198,13 @@ static void fill_and_activate_worklist(worklist_t *new_worklist, if (irn_visited_else_mark(value)) continue; - new_entry = obstack_alloc(&obst, sizeof(new_entry[0])); - memset(new_entry, 0, sizeof(new_entry[0])); + new_entry = OALLOCZ(&obst, worklist_entry_t); 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->reload_point = entry->reload_point; } list_add_tail(&new_entry->head, &new_worklist->live_values); @@ -224,15 +220,13 @@ static worklist_t *duplicate_worklist(const worklist_t *worklist) worklist_t *new_worklist; struct list_head *entry; - new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0])); - memset(new_worklist, 0, sizeof(new_worklist[0])); + new_worklist = OALLOCZ(&obst, worklist_t); INIT_LIST_HEAD(&new_worklist->live_values); 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 *new_entry - = obstack_alloc(&obst, sizeof(new_entry[0])); + worklist_entry_t *new_entry = OALLOC(&obst, worklist_entry_t); memcpy(new_entry, wl_entry, sizeof(new_entry[0])); list_add_tail(&new_entry->head, &new_worklist->live_values); @@ -257,7 +251,12 @@ static void print_worklist(const worklist_t *worklist, int level) #endif - +/** + * Clear the link fields of a loop and all + * its child loops. + * + * @param loop the root loop + */ static void clear_loop_info(ir_loop *loop) { int n_elements = get_loop_n_elements(loop); @@ -279,8 +278,7 @@ static loop_info_t *get_loop_info(ir_loop *loop) if (info != NULL) return info; - info = obstack_alloc(&obst, sizeof(info[0])); - memset(info, 0, sizeof(info[0])); + info = OALLOCZ(&obst, loop_info_t); info->loop = loop; loop->link = info; return info; @@ -326,8 +324,7 @@ static void construct_loop_edges(ir_node *block, void *data) do { loop_info_t *l_info = get_loop_info(l); - edge = obstack_alloc(&obst, sizeof(edge[0])); - memset(edge, 0, sizeof(edge[0])); + edge = OALLOCZ(&obst, loop_edge_t); edge->block = block; edge->pos = i; @@ -341,7 +338,7 @@ static void construct_loop_edges(ir_node *block, void *data) assert(get_loop_depth(cfgpred_loop) < get_loop_depth(l)); } l = get_loop_outer_loop(l); - } while(l != goal); + } while (l != goal); } } @@ -374,7 +371,7 @@ static void make_room(worklist_t *worklist, size_t room_needed) return; entry = worklist->live_values.next; - for(i = spills_needed; i > 0; --i) { + for (i = spills_needed; i > 0; --i) { struct list_head *next = entry->next; worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head); @@ -406,9 +403,7 @@ static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point) list_del(&entry->head); } else { if (entry == NULL) { - entry = obstack_alloc(&obst, sizeof(entry[0])); - memset(entry, 0, sizeof(entry[0])); - + entry = OALLOCZ(&obst, worklist_entry_t); entry->value = value; set_irn_link(value, entry); } @@ -501,7 +496,7 @@ static void do_spilling(ir_node *block, worklist_t *worklist) /* put all values used by the instruction into the workset */ arity = get_irn_arity(node); - for(i = 0; i < arity; ++i) { + for (i = 0; i < arity; ++i) { ir_node *use = get_irn_n(node, i); if (!arch_irn_consider_in_reg_alloc(cls, use)) @@ -554,7 +549,7 @@ static bool fill_start_worklist(worklist_t *new_worklist, ir_node *block) double best_execfreq = -1; worklist_t *best_worklist = NULL; ir_node *best_succ_block = NULL; - int best_pos; + int best_pos = -1; const ir_edge_t *edge; /* construct worklist */ @@ -594,7 +589,7 @@ static worklist_t *construct_start_worklist(ir_node *block) ++worklist_visited; - while(fill_start_worklist(worklist, block)) { + while (fill_start_worklist(worklist, block)) { if (worklist->n_live_values >= n_regs) break; } @@ -640,13 +635,10 @@ static void process_block(ir_node *block, void *env) //assert(n_preds != 0 || worklist->n_live_values == 0); } -typedef struct block_or_loop_t block_or_loop_t; -struct block_or_loop_t { - union { - ir_node *block; - ir_loop *loop; - } v; - bool is_loop; +typedef union block_or_loop_t block_or_loop_t; +union block_or_loop_t { + ir_node *block; + ir_loop *loop; }; static block_or_loop_t *loop_blocks; @@ -666,8 +658,7 @@ static void find_in_loop(ir_loop *loop, ir_node *entry) if (Block_block_visited(some_block)) return; - block_or_loop.v.loop = loop; - block_or_loop.is_loop = true; + block_or_loop.loop = loop; ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop); #ifndef NDEBUG @@ -676,8 +667,10 @@ static void find_in_loop(ir_loop *loop, ir_node *entry) loop_edge_t *edge = loop_info->entry_edges; bool found = false; for ( ; edge != NULL; edge = edge->next) { - if (edge->block == entry) + if (edge->block == entry) { found = true; + break; + } } assert(found); } @@ -706,8 +699,7 @@ static void find_blocks(ir_node *block) if (Block_block_visited(block)) return; - block_or_loop.v.block = block; - block_or_loop.is_loop = false; + block_or_loop.block = block; ARR_APP1(block_or_loop_t, loop_blocks, block_or_loop); mark_Block_block_visited(block); @@ -738,20 +730,15 @@ static void worklist_append(worklist_t *worklist, ir_node *value, ir_node *reload_point, ir_loop *unused_livethrough_loop) { - worklist_entry_t *entry = obstack_alloc(&obst, sizeof(entry[0])); - memset(entry, 0, sizeof(entry[0])); + worklist_entry_t *entry; #ifdef EXPENSIVE_CHECKS - { - struct list_head *entry; - list_for_each(entry, &worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - assert(wl_entry->value != value); - } + foreach_worklist(entry, worklist) { + assert(entry->value != value); } #endif + entry = OALLOCZ(&obst, worklist_entry_t); entry->value = value; entry->reload_point = reload_point; entry->unused_livethrough_loop = unused_livethrough_loop; @@ -858,10 +845,10 @@ static void push_unused_livethroughs(loop_info_t *loop_info) } } -static void process_block_or_loop(const block_or_loop_t *block_or_loop) +static void process_block_or_loop(const block_or_loop_t block_or_loop) { - if (block_or_loop->is_loop) { - loop_info_t *loop_info = get_loop_info(block_or_loop->v.loop); + if (block_or_loop.loop->kind == k_ir_loop) { + loop_info_t *loop_info = get_loop_info(block_or_loop.loop); if (do_push_unused_livethroughs) push_unused_livethroughs(loop_info); @@ -871,7 +858,7 @@ static void process_block_or_loop(const block_or_loop_t *block_or_loop) return; } - process_block(block_or_loop->v.block, NULL); + process_block(block_or_loop.block, NULL); } static void process_loop(ir_loop *loop) @@ -901,7 +888,7 @@ static void process_loop(ir_loop *loop) some_block = get_irg_start_block(current_ir_graph); } - loop_blocks = NEW_ARR_F(block_or_loop_t,0); + loop_blocks = NEW_ARR_F(block_or_loop_t, 0); current_loop = loop; ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED); @@ -916,11 +903,11 @@ static void process_loop(ir_loop *loop) DB((dbg, LEVEL_3, "Block List for loop %p\n", loop)); len = ARR_LEN(loop_blocks); for (i = 0; i < len; ++i) { - block_or_loop_t *block_or_loop = &loop_blocks[i]; - if (block_or_loop->is_loop) { - DB((dbg, LEVEL_3, " L-%p", block_or_loop->v.loop)); + block_or_loop_t block_or_loop = loop_blocks[i]; + if (block_or_loop.loop->kind == k_ir_loop) { + DB((dbg, LEVEL_3, " L-%p", block_or_loop.loop)); } else { - DB((dbg, LEVEL_3, " B-%+F", block_or_loop->v.block)); + DB((dbg, LEVEL_3, " B-%+F", block_or_loop.block)); } } DB((dbg, LEVEL_3, "\n")); @@ -930,13 +917,13 @@ static void process_loop(ir_loop *loop) /* run1: tentative phase */ tentative_mode = true; for (i = len-1; i >= 0; --i) { - process_block_or_loop(&loop_blocks[i]); + process_block_or_loop(loop_blocks[i]); } /* run2: tentative phase - should reach fixpoint */ tentative_mode = true; for (i = len-1; i >= 0; --i) { - process_block_or_loop(&loop_blocks[i]); + process_block_or_loop(loop_blocks[i]); } #ifndef NDEBUG @@ -944,7 +931,7 @@ static void process_loop(ir_loop *loop) tentative_mode = true; should_have_reached_fixpoint = true; for (i = len-1; i >= 0; --i) { - process_block_or_loop(&loop_blocks[i]); + process_block_or_loop(loop_blocks[i]); } should_have_reached_fixpoint = false; #endif @@ -953,7 +940,7 @@ static void process_loop(ir_loop *loop) tentative_mode = false; do_push_unused_livethroughs = true; for (i = len-1; i >= 0; --i) { - process_block_or_loop(&loop_blocks[i]); + process_block_or_loop(loop_blocks[i]); } do_push_unused_livethroughs = false; @@ -981,7 +968,7 @@ static void fix_block_borders(ir_node *block, void *data) worklist_t *end_worklist = pred_block_info->end_worklist; ir_loop *pred_loop = get_irn_loop(pred_block); bool is_loop_entry = false; - struct list_head *entry; + worklist_entry_t *entry; assert(end_worklist != NULL); @@ -992,10 +979,11 @@ static void fix_block_borders(ir_node *block, void *data) /* reload missing values */ activate_worklist(end_worklist); - list_for_each(entry, &start_worklist->live_values) { - worklist_entry_t *wl_entry - = list_entry(entry, worklist_entry_t, head); - ir_node *value = wl_entry->value; + foreach_worklist(entry, start_worklist) { + ir_node *value = entry->value; + + if (!is_loop_entry && entry->unused_livethrough_loop != NULL) + continue; if (is_Phi(value) && get_nodes_block(value) == block) { value = get_irn_n(value, i); @@ -1004,12 +992,8 @@ static void fix_block_borders(ir_node *block, void *data) if (!arch_irn_consider_in_reg_alloc(cls, value)) continue; } - if (worklist_contains(value)) continue; - if (wl_entry->unused_livethrough_loop != NULL && !is_loop_entry) - continue; - be_add_reload_on_edge(senv, value, block, i, cls, 1); } @@ -1017,6 +1001,12 @@ static void fix_block_borders(ir_node *block, void *data) } } +/** + * Run the spill algorithm. + * + * @param birg the graph to run on + * @param ncls the register class to run on + */ static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls) { ir_graph *irg = be_get_birg_irg(birg); @@ -1043,7 +1033,7 @@ static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls) clear_loop_info(get_irg_loop(irg)); irg_block_walk_graph(irg, construct_loop_edges, NULL, NULL); - process_loop(get_irg_loop(current_ir_graph)); + process_loop(get_irg_loop(irg)); irg_block_walk_graph(irg, fix_block_borders, NULL, NULL);