X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillutil.c;h=3ac055fcafec98aa5b41ce769d75ab9a45e7ecde;hb=0a8dac2b5fb9e59ea2add322baf61237b607bea5;hp=7cf3dd6c2564954ab9b8d3ca826f0edef77ed11f;hpb=939b0af78227f2d14a4362a1b5518fd9e05b1053;p=libfirm diff --git a/ir/be/bespillutil.c b/ir/be/bespillutil.c index 7cf3dd6c2..3ac055fca 100644 --- a/ir/be/bespillutil.c +++ b/ir/be/bespillutil.c @@ -22,7 +22,6 @@ * @brief implementation of the spill/reload placement abstraction layer * @author Daniel Grund, Sebastian Hack, Matthias Braun * @date 29.09.2005 - * @version $Id$ */ #include "config.h" @@ -54,7 +53,7 @@ #include "belive_t.h" #include "benode.h" #include "bechordal_t.h" -#include "bestatevent.h" +#include "statev_t.h" #include "bessaconstr.h" #include "beirg.h" #include "beirgmod.h" @@ -93,6 +92,9 @@ struct spill_info_t { double spill_costs; /**< costs needed for spilling the value */ const arch_register_class_t *reload_cls; /** the register class in which the reload should be placed */ + bool spilled_phi; /* true when the whole Phi has been spilled and + will be replaced with a PhiM. false if only the + value of the Phi gets spilled */ }; struct spill_env_t { @@ -103,15 +105,12 @@ struct spill_env_t { 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; + spill_info_t **mem_phis; /**< set of all spilled phis. */ -#ifdef FIRM_STATISTICS unsigned spill_count; unsigned reload_count; unsigned remat_count; unsigned spilled_phi_count; -#endif }; /** @@ -135,14 +134,15 @@ static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) int hash = hash_irn(value); info.to_spill = value; - res = (spill_info_t*)set_find(env->spills, &info, sizeof(info), hash); + res = set_find(spill_info_t, env->spills, &info, sizeof(info), hash); if (res == NULL) { info.reloaders = NULL; info.spills = NULL; info.spill_costs = -1; info.reload_cls = NULL; - res = (spill_info_t*)set_insert(env->spills, &info, sizeof(info), hash); + info.spilled_phi = false; + res = set_insert(spill_info_t, env->spills, &info, sizeof(info), hash); } return res; @@ -156,18 +156,15 @@ spill_env_t *be_new_spill_env(ir_graph *irg) env->spills = new_set(cmp_spillinfo, 1024); env->irg = irg; env->arch_env = arch_env; - ir_nodeset_init(&env->mem_phis); + env->mem_phis = NEW_ARR_F(spill_info_t*, 0); env->spill_cost = arch_env->spill_cost; env->reload_cost = arch_env->reload_cost; - env->exec_freq = be_get_irg_exec_freq(irg); obstack_init(&env->obst); -#ifdef FIRM_STATISTICS env->spill_count = 0; env->reload_count = 0; env->remat_count = 0; env->spilled_phi_count = 0; -#endif return env; } @@ -175,7 +172,7 @@ spill_env_t *be_new_spill_env(ir_graph *irg) void be_delete_spill_env(spill_env_t *env) { del_set(env->spills); - ir_nodeset_destroy(&env->mem_phis); + DEL_ARR_F(env->mem_phis); obstack_free(&env->obst, NULL); free(env); } @@ -253,7 +250,7 @@ void be_add_reload2(spill_env_t *env, ir_node *to_spill, ir_node *before, } } - assert(!is_Proj(before) && !be_is_Keep(before)); + assert(!be_is_Keep(before)); /* put reload into list */ rel = OALLOC(&env->obst, reloader_t); @@ -331,15 +328,6 @@ static ir_node *get_block_insertion_point(ir_node *block, int pos) return be_get_end_of_block_insertion_point(predblock); } -void be_add_reload_at_end(spill_env_t *env, ir_node *to_spill, - const ir_node *block, - const arch_register_class_t *reload_cls, - int allow_remat) -{ - ir_node *before = be_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, int pos, const arch_register_class_t *reload_cls, int allow_remat) @@ -352,10 +340,13 @@ void be_spill_phi(spill_env_t *env, ir_node *node) { ir_node *block; int i, arity; + spill_info_t *info; assert(is_Phi(node)); - ir_nodeset_insert(&env->mem_phis, node); + info = get_spillinfo(env, node); + info->spilled_phi = true; + ARR_APP1(spill_info_t*, env->mem_phis, info); /* create spills for the phi arguments */ block = get_nodes_block(node); @@ -411,7 +402,7 @@ static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) if (!sched_is_scheduled(insn)) { /* override spillinfos or create a new one */ ir_graph *irg = get_irn_irg(to_spill); - spillinfo->spills->spill = new_r_NoMem(irg); + spillinfo->spills->spill = get_irg_no_mem(irg); DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill)); return; } @@ -420,16 +411,11 @@ static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) spill = spillinfo->spills; for ( ; spill != NULL; spill = spill->next) { ir_node *after = spill->after; - ir_node *block = get_block(after); - after = determine_spill_point(after); - spill->spill = be_spill(block, to_spill); - sched_add_after(skip_Proj(after), spill->spill); + spill->spill = arch_env_new_spill(env->arch_env, to_spill, after); DB((dbg, LEVEL_1, "\t%+F after %+F\n", spill->spill, after)); -#ifdef FIRM_STATISTICS env->spill_count++; -#endif } DBG((dbg, LEVEL_1, "\n")); } @@ -472,14 +458,12 @@ static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) /* override or replace spills list... */ spill = OALLOC(&env->obst, spill_t); spill->after = determine_spill_point(phi); - spill->spill = be_new_Phi(block, arity, ins, mode_M, NULL); + spill->spill = be_new_Phi(block, arity, ins, mode_M, arch_no_register_req); spill->next = NULL; sched_add_after(block, spill->spill); spillinfo->spills = spill; -#ifdef FIRM_STATISTICS env->spilled_phi_count++; -#endif for (i = 0; i < arity; ++i) { ir_node *arg = get_irn_n(phi, i); @@ -502,15 +486,11 @@ static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) */ static void spill_node(spill_env_t *env, spill_info_t *spillinfo) { - ir_node *to_spill; - /* node is already spilled */ if (spillinfo->spills != NULL && spillinfo->spills->spill != NULL) return; - to_spill = spillinfo->to_spill; - - if (is_Phi(to_spill) && ir_nodeset_contains(&env->mem_phis, to_spill)) { + if (spillinfo->spilled_phi) { spill_phi(env, spillinfo); } else { spill_irn(env, spillinfo); @@ -622,7 +602,7 @@ static int check_remat_conditions_costs(spill_env_t *env, /** * Re-materialize a node. * - * @param senv the spill environment + * @param env the spill environment * @param spilled the node that was spilled * @param reloader a irn that requires a reload */ @@ -647,10 +627,8 @@ static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) ins[i] = arg; } else { ins[i] = do_remat(env, arg, reloader); -#ifdef FIRM_STATISTICS - /* don't count the recursive call as remat */ - env->remat_count--; -#endif + /* don't count the argument rematerialization as an extra remat */ + --env->remat_count; } } @@ -667,9 +645,7 @@ static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) /* insert in schedule */ sched_reset(res); sched_add_before(reloader, res); -#ifdef FIRM_STATISTICS - env->remat_count++; -#endif + ++env->remat_count; } return res; @@ -678,7 +654,7 @@ static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) double be_get_spill_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); + double freq = get_block_execfreq(block); (void) to_spill; return env->spill_cost * freq; @@ -699,8 +675,8 @@ unsigned be_get_reload_costs_no_weight(spill_env_t *env, const ir_node *to_spill 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); + ir_node *block = get_nodes_block(before); + double freq = get_block_execfreq(block); if (be_do_remats) { /* is the node rematerializable? */ @@ -725,6 +701,39 @@ double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, return be_get_reload_costs(env, to_spill, before); } +ir_node *be_new_spill(ir_node *value, ir_node *after) +{ + ir_graph *irg = get_irn_irg(value); + ir_node *frame = get_irg_frame(irg); + const arch_register_class_t *cls = arch_get_irn_reg_class(value); + const arch_register_class_t *cls_frame = arch_get_irn_reg_class(frame); + ir_node *block = get_block(after); + ir_node *spill + = be_new_Spill(cls, cls_frame, block, frame, value); + + sched_add_after(after, spill); + return spill; +} + +ir_node *be_new_reload(ir_node *value, ir_node *spill, ir_node *before) +{ + ir_graph *irg = get_irn_irg(value); + ir_node *frame = get_irg_frame(irg); + ir_node *block = get_block(before); + const arch_register_class_t *cls = arch_get_irn_reg_class(value); + const arch_register_class_t *cls_frame = arch_get_irn_reg_class(frame); + ir_mode *mode = get_irn_mode(value); + ir_node *reload; + + assert(be_is_Spill(spill) || is_Phi(spill)); + assert(get_irn_mode(spill) == mode_M); + + reload = be_new_Reload(cls, cls_frame, block, frame, spill, mode); + sched_add_before(before, reload); + + return reload; +} + /* * ___ _ ____ _ _ * |_ _|_ __ ___ ___ _ __| |_ | _ \ ___| | ___ __ _ __| |___ @@ -763,7 +772,7 @@ static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo) spill_t *spill = OALLOC(&env->obst, spill_t); spill->after = NULL; spill->next = NULL; - spill->spill = new_r_NoMem(irg); + spill->spill = get_irg_no_mem(irg); spillinfo->spills = spill; spillinfo->spill_costs = 0; @@ -773,9 +782,9 @@ static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo) } spill_block = get_nodes_block(insn); - spill_execfreq = get_block_execfreq(env->exec_freq, spill_block); + spill_execfreq = get_block_execfreq(spill_block); - if (is_Phi(to_spill) && ir_nodeset_contains(&env->mem_phis, to_spill)) { + if (spillinfo->spilled_phi) { /* TODO calculate correct costs... * (though we can't remat this node anyway so no big problem) */ spillinfo->spill_costs = env->spill_cost * spill_execfreq; @@ -791,7 +800,7 @@ static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo) s = spillinfo->spills; for ( ; s != NULL; s = s->next) { ir_node *spill_block = get_block(s->after); - double freq = get_block_execfreq(env->exec_freq, spill_block); + double freq = get_block_execfreq(spill_block); spills_execfreq += freq; } @@ -855,28 +864,25 @@ void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn) void be_insert_spills_reloads(spill_env_t *env) { - const ir_exec_freq *exec_freq = env->exec_freq; - spill_info_t *si; - ir_nodeset_iterator_t iter; - ir_node *node; + size_t n_mem_phis = ARR_LEN(env->mem_phis); + size_t i; be_timer_push(T_RA_SPILL_APPLY); /* create all phi-ms first, this is needed so, that phis, hanging on spilled phis work correctly */ - foreach_ir_nodeset(&env->mem_phis, node, iter) { - spill_info_t *info = get_spillinfo(env, node); + for (i = 0; i < n_mem_phis; ++i) { + spill_info_t *info = env->mem_phis[i]; spill_node(env, info); } /* process each spilled node */ - foreach_set(env->spills, spill_info_t*, si) { - reloader_t *rld; + foreach_set(env->spills, spill_info_t, si) { ir_node *to_spill = si->to_spill; - ir_mode *mode = get_irn_mode(to_spill); ir_node **copies = NEW_ARR_F(ir_node*, 0); double all_remat_costs = 0; /** costs when we would remat all nodes */ - int force_remat = 0; + bool force_remat = false; + reloader_t *rld; DBG((dbg, LEVEL_1, "\nhandling all reloaders of %+F:\n", to_spill)); @@ -918,7 +924,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 = is_Block(reloader) ? reloader : get_nodes_block(reloader); - freq = get_block_execfreq(exec_freq, block); + freq = get_block_execfreq(block); all_remat_costs += remat_cost_delta * freq; DBG((dbg, LEVEL_2, "\tremat costs delta before %+F: " "%d (rel %f)\n", reloader, remat_cost_delta, @@ -936,7 +942,7 @@ void be_insert_spills_reloads(spill_env_t *env) if (all_remat_costs < 0) { DBG((dbg, LEVEL_1, "\nforcing remats of all reloaders (%f)\n", all_remat_costs)); - force_remat = 1; + force_remat = true; } } @@ -957,11 +963,9 @@ void be_insert_spills_reloads(spill_env_t *env) /* create a reload, use the first spill for now SSA * reconstruction for memory comes below */ assert(si->spills != NULL); - copy = be_reload(si->reload_cls, rld->reloader, mode, - si->spills->spill); -#ifdef FIRM_STATISTICS + copy = arch_env_new_reload(env->arch_env, si->to_spill, + si->spills->spill, rld->reloader); env->reload_count++; -#endif } DBG((dbg, LEVEL_1, " %+F of %+F before %+F\n", @@ -1027,14 +1031,14 @@ void be_insert_spills_reloads(spill_env_t *env) /* Matze: In theory be_ssa_construction should take care of the liveness... * try to disable this again in the future */ - be_liveness_invalidate(be_get_irg_liveness(env->irg)); + be_invalidate_live_sets(env->irg); be_remove_dead_nodes_from_schedule(env->irg); be_timer_pop(T_RA_SPILL_APPLY); } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spill); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spill) void be_init_spill(void) { FIRM_DBG_REGISTER(dbg, "firm.be.spill");