X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady3.c;h=a8c70fa5064d12d619b8784925f5a8f903b80ffe;hb=3e2a1de2fc4b08ebd26778c1eac1a8bd9751d90f;hp=3c6711edd6e49bad0968d95e0361b66efa61285a;hpb=b63f534ed3ea9e6fa94b02de8809195772f29c5a;p=libfirm diff --git a/ir/be/bespillbelady3.c b/ir/be/bespillbelady3.c index 3c6711edd..a8c70fa50 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,11 +47,13 @@ #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 #define EXPENSIVE_CHECKS +#endif DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) @@ -80,11 +80,13 @@ 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; size_t n_live_values; - unsigned long visited; + ir_visited_t visited; }; typedef struct block_info_t block_info_t; @@ -93,22 +95,24 @@ struct block_info_t { worklist_t *end_worklist; }; -static const arch_env_t *arch_env; +/** 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 unsigned long worklist_visited; +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; @@ -132,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); } } @@ -173,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 @@ -181,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) @@ -193,27 +191,25 @@ static void fill_and_activate_worklist(worklist_t *new_worklist, value = get_Phi_pred(value, succ_pos); /* can happen for unknown phi preds */ - if (!arch_irn_consider_in_reg_alloc(arch_env, cls, value)) + if (!arch_irn_consider_in_reg_alloc(cls, value)) continue; } - if (irn_visited(value)) + 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); ++n_live_values; - mark_irn_visited(value); set_irn_link(value, new_entry); new_worklist->n_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); } } @@ -398,7 +395,7 @@ static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point) /* already in the worklist? move around, otherwise add at back */ worklist_entry_t *entry = get_irn_link(value); - assert(arch_irn_consider_in_reg_alloc(arch_env, cls, value)); + assert(arch_irn_consider_in_reg_alloc(cls, value)); if (worklist_contains(value)) { assert(entry != NULL); @@ -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); } @@ -463,7 +458,7 @@ static void do_spilling(ir_node *block, worklist_t *worklist) if (worklist_contains(node2)) continue; - if (!arch_irn_consider_in_reg_alloc(arch_env, cls, node2)) + if (!arch_irn_consider_in_reg_alloc(cls, node2)) continue; if (!tentative_mode) @@ -480,7 +475,7 @@ static void do_spilling(ir_node *block, worklist_t *worklist) foreach_out_edge(node, edge) { ir_node *proj = get_edge_src_irn(edge); - if (!arch_irn_consider_in_reg_alloc(arch_env, cls, proj)) + if (!arch_irn_consider_in_reg_alloc(cls, proj)) continue; if (worklist_contains(proj)) { worklist_remove(worklist, proj); @@ -488,7 +483,7 @@ static void do_spilling(ir_node *block, worklist_t *worklist) ++n_defs; } } - } else if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) { + } else if (arch_irn_consider_in_reg_alloc(cls, node)) { if (worklist_contains(node)) { worklist_remove(worklist, node); } else { @@ -504,7 +499,7 @@ static void do_spilling(ir_node *block, worklist_t *worklist) for(i = 0; i < arity; ++i) { ir_node *use = get_irn_n(node, i); - if (!arch_irn_consider_in_reg_alloc(arch_env, cls, use)) + if (!arch_irn_consider_in_reg_alloc(cls, use)) continue; val_used(worklist, use, node); @@ -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 */ @@ -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,12 +667,17 @@ 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); } +#else + (void) entry; #endif + /* check all loop successors */ for (edge = loop_info->exit_edges; edge != NULL; edge = edge->next) { ir_node *succ = edge->block; @@ -703,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); @@ -735,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; @@ -855,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); @@ -868,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) @@ -898,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); @@ -913,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")); @@ -927,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 @@ -941,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 @@ -950,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; @@ -978,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); @@ -989,24 +979,21 @@ 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); /* we might have unknowns as argument for the phi */ - if (!arch_irn_consider_in_reg_alloc(arch_env, cls, value)) + 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); } @@ -1014,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); @@ -1026,7 +1019,6 @@ static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls) return; worklist_visited = 0; - arch_env = be_get_birg_arch_env(birg); exec_freq = be_get_birg_exec_freq(birg); be_clear_links(irg); @@ -1041,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);