X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=90f8cd9114b27f22c7f5074a686ecc64f3e4e2d0;hb=199f27336a34453458ca31153cbecfd8d485a1ab;hp=30b05e5e2f75a283d597e1eb25807d794bcbb076;hpb=ae515d01cd46334273438ce4019847f4ba05ab3d;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 30b05e5e2..90f8cd911 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -19,7 +19,7 @@ /** * @file - * @brief Main spill driver. + * @brief implementation of the spill/reload placement abstraction layer * @author Daniel Grund, Sebastian Hack, Matthias Braun * @date 29.09.2005 * @version $Id$ @@ -64,10 +64,6 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -/* only rematerialise when costs are less than REMAT_COST_LIMIT */ -/* TODO determine a good value here... */ -#define REMAT_COST_LIMIT 10 - #define REMAT_COST_INFINITE 1000 typedef struct reloader_t reloader_t; @@ -81,64 +77,55 @@ struct reloader_t { typedef struct spill_info_t spill_info_t; struct spill_info_t { - /** the value that should get spilled */ - ir_node *to_spill; - /** list of places where the value should get reloaded */ - reloader_t *reloaders; - - /** the spill node, or a PhiM node */ - ir_node *spill; - /** if we had the value of a phi spilled before but not the phi itself then - * this field contains the spill for the phi value */ - ir_node *old_spill; - - /** the register class in which the reload should be placed */ - const arch_register_class_t *reload_cls; + ir_node *to_spill; /**< the value that should get spilled */ + reloader_t *reloaders; /**< list of places where the value should get + reloaded */ + ir_node *spill; /**< the spill node, or a PhiM node */ + ir_node *old_spill; /**< if we had the value of a phi spilled before but + not the phi itself then this field contains the + spill for the phi value */ + const arch_register_class_t *reload_cls; /** the register class in which the + reload should be placed */ }; struct spill_env_t { const arch_env_t *arch_env; - ir_graph *irg; - struct obstack obst; - be_irg_t *birg; - int spill_cost; /**< the cost of a single spill node */ - int reload_cost; /**< the cost of a reload node */ - set *spills; /**< all spill_info_t's, which must be placed */ - ir_nodeset_t mem_phis; /**< set of all special spilled phis. allocated and freed separately */ + ir_graph *irg; + struct obstack obst; + be_irg_t *birg; + int spill_cost; /**< the cost of a single spill node */ + int reload_cost; /**< the cost of a reload node */ + set *spills; /**< all spill_info_t's, which must be + placed */ + ir_nodeset_t mem_phis; /**< set of all spilled phis. */ + ir_exec_freq *exec_freq; + #ifdef FIRM_STATISTICS - int spill_count; - int reload_count; - int remat_count; - int spilled_phi_count; + unsigned spill_count; + unsigned reload_count; + unsigned remat_count; + unsigned spilled_phi_count; #endif }; /** * Compare two spill infos. */ -static int cmp_spillinfo(const void *x, const void *y, size_t size) { +static +int cmp_spillinfo(const void *x, const void *y, size_t size) +{ const spill_info_t *xx = x; const spill_info_t *yy = y; - return xx->to_spill != yy->to_spill; -} + (void) size; -/** - * Returns spill info for a specific value (returns NULL if the info doesn't - * exist yet) - */ -static spill_info_t *find_spillinfo(const spill_env_t *env, ir_node *value) { - spill_info_t info; - int hash = nodeset_hash(value); - - info.to_spill = value; - - return set_find(env->spills, &info, sizeof(info), hash); + return xx->to_spill != yy->to_spill; } /** * Returns spill info for a specific value (the value that is to be spilled) */ -static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) +static +spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) { spill_info_t info, *res; int hash = nodeset_hash(value); @@ -157,7 +144,6 @@ static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) return res; } -/* Creates a new spill environment. */ spill_env_t *be_new_spill_env(be_irg_t *birg) { const arch_env_t *arch_env = birg->main_env->arch_env; @@ -170,7 +156,9 @@ spill_env_t *be_new_spill_env(be_irg_t *birg) ir_nodeset_init(&env->mem_phis); env->spill_cost = arch_env->isa->spill_cost; env->reload_cost = arch_env->isa->reload_cost; + env->exec_freq = be_get_birg_exec_freq(birg); obstack_init(&env->obst); + #ifdef FIRM_STATISTICS env->spill_count = 0; env->reload_count = 0; @@ -181,7 +169,6 @@ spill_env_t *be_new_spill_env(be_irg_t *birg) return env; } -/* Deletes a spill environment. */ void be_delete_spill_env(spill_env_t *env) { del_set(env->spills); @@ -212,9 +199,9 @@ void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before, reloader->next = spill_info->reloaders; reloader->reloader = before; reloader->rematted_node = rematted_node; - reloader->remat_cost_delta = 0; /* delta is 0 since we will do a remat in - each, as we will never place a reload, - we will never have a cost win */ + reloader->remat_cost_delta = 0; /* We will never have a cost win over a + reload since we're not even allowed to + create a reload */ spill_info->reloaders = reloader; @@ -254,6 +241,8 @@ void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before, #endif } + assert(!is_Proj(before) && !be_is_Keep(before)); + /* put reload into list */ rel = obstack_alloc(&env->obst, sizeof(rel[0])); rel->next = info->reloaders; @@ -273,12 +262,34 @@ void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before, to_spill, before, allow_remat ? "" : " not")); } +static ir_node *get_end_of_block_insertion_point(ir_node *block) +{ + ir_node *last = sched_last(block); + + /* we might have projs and keepanys behind the jump... */ + while(is_Proj(last) || be_is_Keep(last)) { + last = sched_prev(last); + assert(!sched_is_end(last)); + } + + if(!is_cfop(last)) { + last = sched_next(last); + /* last node must be a cfop, only exception is the start block */ + assert(last == get_irg_start_block(get_irn_irg(block))); + } + + /* add the reload before the (cond-)jump */ + return last; +} + /** * Returns the point at which you can insert a node that should be executed * before block @p block when coming from pred @p pos. */ -static ir_node *get_block_insertion_point(ir_node *block, int pos) { - ir_node *predblock, *last; +static +ir_node *get_block_insertion_point(ir_node *block, int pos) +{ + ir_node *predblock; /* simply add the reload to the beginning of the block if we only have 1 * predecessor. We don't need to check for phis as there can't be any in a @@ -290,22 +301,15 @@ static ir_node *get_block_insertion_point(ir_node *block, int pos) { /* We have to reload the value in pred-block */ predblock = get_Block_cfgpred_block(block, pos); - last = sched_last(predblock); - - /* we might have projs and keepanys behind the jump... */ - while(is_Proj(last) || be_is_Keep(last)) { - last = sched_prev(last); - assert(!sched_is_end(last)); - } - - if(!is_cfop(last)) { - last = sched_next(last); - /* last node must be a cfop, only exception is the start block */ - assert(last == get_irg_start_block(get_irn_irg(block))); - } + return get_end_of_block_insertion_point(predblock); +} - /* add the reload before the (cond-)jump */ - return last; +void be_add_reload_at_end(spill_env_t *env, ir_node *to_spill, ir_node *block, + const arch_register_class_t *reload_cls, + int allow_remat) +{ + ir_node *before = get_end_of_block_insertion_point(block); + be_add_reload(env, to_spill, before, reload_cls, allow_remat); } void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, @@ -360,7 +364,7 @@ static void sched_add_after_insn(ir_node *sched_after, ir_node *node) { ir_node *next = sched_next(sched_after); - while(is_Proj(next) || is_Phi(next)) { + while(is_Proj(next) || is_Phi(next) || be_is_Keep(next)) { next = sched_next(next); } assert(next != NULL); @@ -698,39 +702,46 @@ ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) get_irn_arity(spilled), ins); copy_node_attr(spilled, res); new_backedge_info(res); - sched_reset(res); DBG((dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res, spilled, reloader)); - /* insert in schedule */ - sched_add_before(reloader, res); + if (! is_Proj(res)) { + /* insert in schedule */ + sched_reset(res); + sched_add_before(reloader, res); #ifdef FIRM_STATISTICS - env->remat_count++; + env->remat_count++; #endif + } return res; } -int be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) +double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *after) { - spill_info_t *spill_info; + ir_node *block = get_nodes_block(after); + double freq = get_block_execfreq(env->exec_freq, block); + (void) to_spill; + + return env->spill_cost * freq; +} + +double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) +{ + ir_node *block = get_nodes_block(before); + double freq = get_block_execfreq(env->exec_freq, block); if(be_do_remats) { /* is the node rematerializable? */ int costs = check_remat_conditions_costs(env, to_spill, before, 0); - if(costs < env->spill_cost + env->reload_cost) - return costs; + if(costs < env->reload_cost) + return costs * freq; } - /* do we already have a spill? */ - spill_info = find_spillinfo(env, to_spill); - if(spill_info != NULL && spill_info->spill != NULL) - return env->reload_cost; - - return env->spill_cost + env->reload_cost; + return env->reload_cost * freq; } -int be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, +double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) { ir_node *before = get_block_insertion_point(block, pos); @@ -749,7 +760,7 @@ int be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, void be_insert_spills_reloads(spill_env_t *env) { const arch_env_t *arch_env = env->arch_env; - const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg); + const ir_exec_freq *exec_freq = env->exec_freq; spill_info_t *si; ir_nodeset_iterator_t iter; ir_node *node; @@ -805,7 +816,7 @@ void be_insert_spills_reloads(spill_env_t *env) remat_cost_delta = remat_cost - env->reload_cost; rld->remat_cost_delta = remat_cost_delta; - block = get_nodes_block(reloader); + block = is_Block(reloader) ? reloader : get_nodes_block(reloader); freq = get_block_execfreq(exec_freq, block); all_remat_costs += remat_cost_delta * freq; DBG((dbg, LEVEL_2, "\tremat costs delta before %+F: " @@ -887,19 +898,16 @@ void be_insert_spills_reloads(spill_env_t *env) si->reloaders = NULL; } -#ifdef FIRM_STATISTICS - if (be_stat_ev_is_active()) { - be_stat_ev("spill_spills", env->spill_count); - be_stat_ev("spill_reloads", env->reload_count); - be_stat_ev("spill_remats", env->remat_count); - be_stat_ev("spill_spilled_phis", env->spilled_phi_count); - } -#endif + stat_ev_dbl("spill_spills", env->spill_count); + stat_ev_dbl("spill_reloads", env->reload_count); + stat_ev_dbl("spill_remats", env->remat_count); + stat_ev_dbl("spill_spilled_phis", env->spilled_phi_count); - be_remove_dead_nodes_from_schedule(env->irg); /* Matze: In theory be_ssa_construction should take care of the liveness... * try to disable this again in the future */ - be_invalidate_liveness(env->birg); + be_liveness_invalidate(env->birg->lv); + + be_remove_dead_nodes_from_schedule(env->birg); } void be_init_spill(void)