X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=778481788aff8d2a3fcb55d30f9c744a279c7f7b;hb=97927c8e372f337e8342b698072facf4ffa453ad;hp=85e49f62369a641966c0a4a63eead4a9bd2bdf56;hpb=472a1a6afb9abcd08de787cc4d22297a63505977;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 85e49f623..778481788 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -1,5 +1,5 @@ -/** - * Author: Daniel Grund, Sebastian Hack +/* + * Author: Daniel Grund, Sebastian Hack, Matthias Braun * Date: 29.09.2005 * Copyright: (c) Universitaet Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. @@ -14,6 +14,8 @@ #include "irnode_t.h" #include "ircons_t.h" #include "iredges_t.h" +#include "irbackedge_t.h" +#include "irprintf.h" #include "ident_t.h" #include "type_t.h" #include "entity_t.h" @@ -21,79 +23,95 @@ #include "irgwalk.h" #include "array.h" #include "pdeq.h" +#include "unionfind.h" +#include "execfreq.h" #include "belive_t.h" #include "besched_t.h" #include "bespill.h" +#include "belive_t.h" #include "benode_t.h" #include "bechordal_t.h" +#include "bejavacoal.h" +#include "benodesets.h" -#define REMAT -/* This enables re-computation of values. Current state: Unfinished and buggy. */ -#undef BUGGY_REMAT +// only rematerialise when costs are less than REMAT_COST_LIMIT +// TODO determine a good value here... +#define REMAT_COST_LIMIT 10 typedef struct _reloader_t reloader_t; -typedef struct _spill_info_t spill_info_t; struct _reloader_t { reloader_t *next; ir_node *reloader; }; -struct _spill_info_t { +typedef struct _spill_info_t { + /** the value that should get spilled */ ir_node *spilled_node; + /** list of places where the value should get reloaded */ reloader_t *reloaders; -}; -typedef struct _spill_ctx_t { - ir_node *spilled; /**< The spilled node. */ - ir_node *user; /**< The node this spill is for. */ - ir_node *spill; /**< The spill itself. */ -} spill_ctx_t; + /** 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; +} spill_info_t; struct _spill_env_t { const arch_register_class_t *cls; + const arch_env_t *arch_env; const be_chordal_env_t *chordal_env; struct obstack obst; - set *spill_ctxs; - set *spills; /**< all spill_info_t's, which must be placed */ - pset *mem_phis; /**< set of all special spilled phis. allocated and freed separately */ - decide_irn_t is_mem_phi; /**< callback func to decide if a phi needs special spilling */ - void *data; /**< data passed to all callbacks */ + 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 */ + pset *mem_phis; /**< set of all special spilled phis. allocated and freed separately */ + DEBUG_ONLY(firm_dbg_module_t *dbg;) }; -/* associated Phi -> Spill*/ -typedef struct _phi_spill_assoc_t { - ir_node *phi; - ir_node *spill; -} phi_spill_assoc_t; - /** - * Compare two Phi->Spill associations. + * Compare two spill infos. */ -static int cmp_phi_spill_assoc(const void *a, const void *b, size_t n) { - const phi_spill_assoc_t *p1 = a; - const phi_spill_assoc_t *p2 = b; - return p1->phi != p2->phi; +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->spilled_node != yy->spilled_node; } /** - * compare two spill contexts. + * Returns spill info for a specific value (returns NULL if the info doesn't + * exist yet) */ -static int cmp_spillctx(const void *a, const void *b, size_t n) { - const spill_ctx_t *p = a; - const spill_ctx_t *q = b; - return p->user != q->user || p->spilled != q->spilled; +static spill_info_t *find_spillinfo(const spill_env_t *env, ir_node *value) { + spill_info_t info; + int hash = nodeset_hash(value); + + info.spilled_node = value; + + return set_find(env->spills, &info, sizeof(info), hash); } /** - * Compare two spill infos. + * Returns spill info for a specific value (the value that is to be spilled) */ -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->spilled_node != yy->spilled_node; +static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) { + spill_info_t info, *res; + int hash = nodeset_hash(value); + + info.spilled_node = value; + res = set_find(env->spills, &info, sizeof(info), hash); + + if (res == NULL) { + info.reloaders = NULL; + info.spill = NULL; + info.old_spill = NULL; + res = set_insert(env->spills, &info, sizeof(info), hash); + } + + return res; } DEBUG_ONLY( @@ -104,43 +122,141 @@ void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) { ) /* Creates a new spill environment. */ -spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env, decide_irn_t is_mem_phi, void *data) { - spill_env_t *env = xmalloc(sizeof(env[0])); - env->spill_ctxs = new_set(cmp_spillctx, 1024); - env->spills = new_set(cmp_spillinfo, 1024); - env->cls = chordal_env->cls; - env->is_mem_phi = is_mem_phi; - env->data = data; - env->chordal_env = chordal_env; +spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env) { + spill_env_t *env = xmalloc(sizeof(env[0])); + env->spills = new_set(cmp_spillinfo, 1024); + env->cls = chordal_env->cls; + env->chordal_env = chordal_env; + env->arch_env = env->chordal_env->birg->main_env->arch_env; + env->mem_phis = pset_new_ptr_default(); + // TODO, ask backend about costs... + env->spill_cost = 8; + env->reload_cost = 5; obstack_init(&env->obst); return env; } /* Deletes a spill environment. */ -void be_delete_spill_env(spill_env_t *senv) { - del_set(senv->spill_ctxs); - del_set(senv->spills); - obstack_free(&senv->obst, NULL); - free(senv); +void be_delete_spill_env(spill_env_t *env) { + del_set(env->spills); + del_pset(env->mem_phis); + obstack_free(&env->obst, NULL); + free(env); } -/** - * Returns a spill context. If the context did not exists, create one. - * - * @param sc the set containing all spill contexts - * @param to_spill the node that should be spilled - * @param ctx_irn an user of the spilled node +/* + * ____ _ ____ _ _ + * | _ \| | __ _ ___ ___ | _ \ ___| | ___ __ _ __| |___ + * | |_) | |/ _` |/ __/ _ \ | |_) / _ \ |/ _ \ / _` |/ _` / __| + * | __/| | (_| | (_| __/ | _ < __/ | (_) | (_| | (_| \__ \ + * |_| |_|\__,_|\___\___| |_| \_\___|_|\___/ \__,_|\__,_|___/ * - * @return a spill context. */ -static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_irn) { - spill_ctx_t templ; - templ.spilled = to_spill; - templ.user = ctx_irn; - templ.spill = NULL; +void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before) { + spill_info_t *info; + reloader_t *rel; + + assert(sched_is_scheduled(before)); + assert(arch_irn_consider_in_reg_alloc(env->arch_env, env->cls, to_spill)); + + info = get_spillinfo(env, to_spill); + + if(is_Phi(to_spill)) { + int i, arity; + // create spillinfos for the phi arguments + for(i = 0, arity = get_irn_arity(to_spill); i < arity; ++i) { + ir_node *arg = get_irn_n(to_spill, i); + get_spillinfo(env, arg); + } + } + + rel = obstack_alloc(&env->obst, sizeof(rel[0])); + rel->reloader = before; + rel->next = info->reloaders; + info->reloaders = rel; +} + +static ir_node *get_reload_insertion_point(ir_node *block, int pos) { + ir_node *predblock, *last; + + /* 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 block with only 1 pred) + */ + if(get_Block_n_cfgpreds(block) == 1) { + assert(!is_Phi(sched_first(block))); + return sched_first(block); + } + + /* 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)); + } + assert(is_cfop(last)); + + // add the reload before the (cond-)jump + return last; +} + +void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) { + ir_node *before = get_reload_insertion_point(block, pos); + be_add_reload(env, to_spill, before); +} + +void be_spill_phi(spill_env_t *env, ir_node *node) { + spill_info_t* spill; + int i, arity; + + assert(is_Phi(node)); + + pset_insert_ptr(env->mem_phis, node); + + // create spillinfos for the phi arguments + spill = get_spillinfo(env, node); + for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *arg = get_irn_n(node, i); + get_spillinfo(env, arg); + } + + // if we had a spill for the phi value before, then remove this spill from + // schedule, as we will remove it in the insert spill/reload phase + if(spill->spill != NULL && !is_Phi(spill->spill)) { + spill->old_spill = spill->spill; + spill->spill = NULL; + } +} + +/* + * ____ _ ____ _ _ _ + * / ___|_ __ ___ __ _| |_ ___ / ___| _ __ (_) | |___ + * | | | '__/ _ \/ _` | __/ _ \ \___ \| '_ \| | | / __| + * | |___| | | __/ (_| | || __/ ___) | |_) | | | \__ \ + * \____|_| \___|\__,_|\__\___| |____/| .__/|_|_|_|___/ + * |_| + */ + +/** + * Schedules a node after an instruction. (That is the place after all projs and phis + * that are scheduled after the instruction) + * This function also skips phi nodes at the beginning of a block + */ +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)) { + next = sched_next(next); + } + assert(next != NULL); - return set_insert(sc, &templ, sizeof(templ), HASH_COMBINE(HASH_PTR(to_spill), HASH_PTR(ctx_irn))); + if(sched_is_end(next)) { + sched_add_after(sched_last(get_nodes_block(sched_after)), node); + } else { + sched_add_before(next, node); + } } /** @@ -152,19 +268,35 @@ static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_ir * * @return a be_Spill node */ -static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) { - spill_ctx_t *ctx; - DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn)); - - ctx = be_get_spill_ctx(senv->spill_ctxs, irn, ctx_irn); - if(!ctx->spill) { - const be_main_env_t *env = senv->chordal_env->birg->main_env; - ctx->spill = be_spill(env->arch_env, irn, ctx_irn); +static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) { + ir_node *to_spill = spillinfo->spilled_node; + + DBG((env->dbg, LEVEL_1, "%+F\n", to_spill)); + + /* Trying to spill an already spilled value, no need for a new spill + * node then, we can simply connect to the same one for this reload + * + * (although rematerialization code should handle most of these cases + * this can still happen when spilling Phis) + */ + if(be_is_Reload(to_spill)) { + spillinfo->spill = get_irn_n(to_spill, be_pos_Reload_mem); + return; + } + + if (arch_irn_is(env->arch_env, to_spill, dont_spill)) { + if (env->chordal_env->opts->vrfy_option == BE_CH_VRFY_WARN) + ir_fprintf(stderr, "Verify warning: spilling 'dont_spill' node %+F\n", to_spill); + else if (env->chordal_env->opts->vrfy_option == BE_CH_VRFY_ASSERT) + assert(0 && "Attempt to spill a node marked 'dont_spill'"); } - return ctx->spill; + spillinfo->spill = be_spill(env->arch_env, to_spill); + sched_add_after_insn(to_spill, spillinfo->spill); } +static void spill_node(spill_env_t *env, spill_info_t *spillinfo); + /** * If the first usage of a Phi result would be out of memory * there is no sense in allocating a register for it. @@ -174,189 +306,193 @@ static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) * @param senv the spill environment * @param phi the Phi node that should be spilled * @param ctx_irn an user of the spilled node - * - * @return a be_Spill node */ -static ir_node *be_spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn, unsigned visited_nr, set *already_visited_phis) { - int i, n = get_irn_arity(phi); - ir_graph *irg = senv->chordal_env->irg; - ir_node *bl = get_nodes_block(phi); - ir_node **ins, *phi_spill; - phi_spill_assoc_t key; - spill_ctx_t *ctx; +static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) { + ir_node *phi = spillinfo->spilled_node; + int i; + int arity = get_irn_arity(phi); + ir_node *block = get_nodes_block(phi); + ir_node **ins; assert(is_Phi(phi)); - DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", phi, ctx_irn)); /* build a new PhiM */ - NEW_ARR_A(ir_node *, ins, n); - for (i = 0; i < n; ++i) { - ins[i] = new_r_Bad(irg); + ins = alloca(sizeof(ir_node*) * arity); + for(i = 0; i < arity; ++i) { + ins[i] = get_irg_bad(env->chordal_env->irg); } - phi_spill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M); - key.phi = phi; - key.spill = phi_spill; - set_insert(already_visited_phis, &key, sizeof(key), HASH_PTR(phi)); - - /* search an existing spill for this context */ - ctx = be_get_spill_ctx(senv->spill_ctxs, phi, ctx_irn); - - /* if not found spill the phi */ - if (! ctx->spill) { - set_irn_visited(phi, visited_nr); - - /* collect all arguments of the phi */ - for (i = 0; i < n; ++i) { - ir_node *arg = get_irn_n(phi, i); - ir_node *sub_res; - phi_spill_assoc_t *entry; - - if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg)) { - if (get_irn_visited(arg) < visited_nr) - sub_res = be_spill_phi(senv, arg, ctx_irn, visited_nr, already_visited_phis); - else { - /* we already visited the argument phi: get it's spill */ - key.phi = arg; - key.spill = NULL; - entry = set_find(already_visited_phis, &key, sizeof(key), HASH_PTR(arg)); - assert(entry && "argument phi already visited, but no spill found?!?"); - sub_res = entry->spill; - assert(sub_res && "spill missing?!?"); - } - } - else - sub_res = be_spill_irn(senv, arg, ctx_irn); + spillinfo->spill = new_r_Phi(env->chordal_env->irg, block, arity, ins, mode_M); - set_irn_n(phi_spill, i, sub_res); - } + for(i = 0; i < arity; ++i) { + ir_node *arg = get_irn_n(phi, i); + spill_info_t *arg_info = get_spillinfo(env, arg); + + spill_node(env, arg_info); - ctx->spill = phi_spill; + set_irn_n(spillinfo->spill, i, arg_info->spill); + } + + // rewire reloads from old_spill to phi + if(spillinfo->old_spill != NULL) { + const ir_edge_t *edge, *next; + foreach_out_edge_safe(spillinfo->old_spill, edge, next) { + ir_node* reload = get_edge_src_irn(edge); + assert(be_is_Reload(reload) || is_Phi(reload)); + set_irn_n(reload, get_edge_src_pos(edge), spillinfo->spill); + } + spillinfo->old_spill = NULL; } - return ctx->spill; } /** * Spill a node. * * @param senv the spill environment - * @param irn the node that should be spilled - * @param ctx_irn an user of the spilled node - * - * @return a be_Spill node + * @param to_spill the node that should be spilled */ -static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill, unsigned visited_nr) { - ir_graph *irg = get_irn_irg(to_spill); - int save_optimize = get_optimize(); - int save_normalize = get_opt_normalize(); - set *already_visited_phis = new_set(cmp_phi_spill_assoc, 10); - ir_node *res; - - /* - * Disable optimization so that the phi functions do not - * disappear. - */ - set_optimize(0); - set_opt_normalize(0); - - if (pset_find_ptr(senv->mem_phis, to_spill)) - res = be_spill_phi(senv, to_spill, to_spill, visited_nr, already_visited_phis); - else - res = be_spill_irn(senv, to_spill, to_spill); +static void spill_node(spill_env_t *env, spill_info_t *spillinfo) { + ir_node *to_spill; - del_set(already_visited_phis); - - /* reset the optimizations */ - set_optimize(save_optimize); - set_opt_normalize(save_normalize); + // the node should be tagged for spilling already... + if(spillinfo->spill != NULL) + return; - return res; + to_spill = spillinfo->spilled_node; + if (is_Phi(to_spill) && pset_find_ptr(env->mem_phis, spillinfo->spilled_node)) { + spill_phi(env, spillinfo); + } else { + spill_irn(env, spillinfo); + } } -#ifdef REMAT - -#ifdef BUGGY_REMAT - -/** - * Check if a spilled node could be rematerialized. +/* + * + * ____ _ _ _ _ + * | _ \ ___ _ __ ___ __ _| |_ ___ _ __(_) __ _| (_)_______ + * | |_) / _ \ '_ ` _ \ / _` | __/ _ \ '__| |/ _` | | |_ / _ \ + * | _ < __/ | | | | | (_| | || __/ | | | (_| | | |/ / __/ + * |_| \_\___|_| |_| |_|\__,_|\__\___|_| |_|\__,_|_|_/___\___| * - * @param senv the spill environment - * @param spill the Spill node - * @param spilled the node that was spilled - * @param reloader a irn that requires a reload */ -static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) { - int pos, max; - /* check for 'normal' spill and general remat condition */ - if (!be_is_Spill(spill) || !arch_irn_is(senv->chordal_env->birg->main_env->arch_env, spilled, rematerializable)) - return 0; +/** + * Tests whether value @p arg is available before node @p reloader + * @returns 1 if value is available, 0 otherwise + */ +static int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader) { + if(is_Unknown(arg) || arg == new_NoMem()) + return 1; - /* check availability of original arguments */ - if (is_Block(reloader)) { + if(be_is_Spill(arg)) + return 1; - /* we want to remat at the end of a block. - * thus all arguments must be alive at the end of the block - */ - for (pos=0, max=get_irn_arity(spilled); poschordal_env->irg)) + return 1; - } else { + /* the following test does not work while spilling, + * because the liveness info is not adapted yet to the effects of the + * additional spills/reloads. + * + * So we can only do this test for ignore registers (of our register class) + */ + if(arch_get_irn_reg_class(env->arch_env, arg, -1) == env->chordal_env->cls + && arch_irn_is(env->arch_env, arg, ignore)) { + int i, arity; /* we want to remat before the insn reloader * thus an arguments is alive if * - it interferes with the reloaders result - * or * - or it is (last-) used by reloader itself */ - for (pos=0, max=get_irn_arity(spilled); poschordal_env->lv, reloader, arg)) { + return 1; + } - for (i=0, m=get_irn_arity(reloader); iarch_env; - } + assert(!be_is_Spill(node)); + if(arch_irn_is(arch_env, node, rematerializable)) { + return 1; } - return 1; -} + if(be_is_StackParam(node)) + return 1; -#else /* BUGGY_REMAT */ + return 0; +} /** - * A very simple rematerialization checker. + * Check if a node is rematerializable. This tests for the following conditions: * - * @param senv the spill environment - * @param spill the Spill node - * @param spilled the node that was spilled - * @param reloader a irn that requires a reload + * - The node itself is rematerializable + * - All arguments of the node are available or also rematerialisable + * - The costs for the rematerialisation operation is less or equal a limit + * + * Returns the costs needed for rematerialisation or something + * > REMAT_COST_LIMIT if remat is not possible. */ -static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) { - const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env; +static int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, ir_node *reloader, int parentcosts) { + int i, arity; + int argremats; + int costs = 0; + + if(!is_remat_node(env, spilled)) + return REMAT_COST_LIMIT; - return get_irn_arity(spilled) == 0 && - be_is_Spill(spill) && - arch_irn_is(aenv, spilled, rematerializable); + if(be_is_Reload(spilled)) { + costs += 2; + } else { + costs += arch_get_op_estimated_cost(env->arch_env, spilled); + } + if(parentcosts + costs >= REMAT_COST_LIMIT) { + return REMAT_COST_LIMIT; + } + + argremats = 0; + for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) { + ir_node *arg = get_irn_n(spilled, i); + + if(is_value_available(env, arg, reloader)) + continue; + + // we have to rematerialize the argument as well... + if(argremats >= 1) { + /* we only support rematerializing 1 argument at the moment, + * so that we don't have to care about register pressure + */ + return REMAT_COST_LIMIT; + } + argremats++; + + costs += check_remat_conditions_costs(env, arg, reloader, parentcosts + costs); + if(parentcosts + costs >= REMAT_COST_LIMIT) + return REMAT_COST_LIMIT; + } + + return costs; } -#endif /* BUGGY_REMAT */ +static int check_remat_conditions(spill_env_t *env, ir_node *spilled, ir_node *reloader) { + int costs = check_remat_conditions_costs(env, spilled, reloader, 0); -#endif /* REMAT */ + return costs < REMAT_COST_LIMIT; +} /** * Re-materialize a node. @@ -365,84 +501,77 @@ static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *sp * @param spilled the node that was spilled * @param reloader a irn that requires a reload */ -static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) { +static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) { + int i, arity; ir_node *res; - ir_node *bl = (is_Block(reloader)) ? reloader : get_nodes_block(reloader); + ir_node *bl = get_nodes_block(reloader); + ir_node **ins; - /* recompute the value */ - res = new_ir_node(get_irn_dbg_info(spilled), senv->chordal_env->irg, bl, + ins = alloca(get_irn_arity(spilled) * sizeof(ins[0])); + for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) { + ir_node *arg = get_irn_n(spilled, i); + + if(is_value_available(env, arg, reloader)) { + ins[i] = arg; + } else { + ins[i] = do_remat(env, arg, reloader); + } + } + + /* create a copy of the node */ + res = new_ir_node(get_irn_dbg_info(spilled), env->chordal_env->irg, bl, get_irn_op(spilled), get_irn_mode(spilled), get_irn_arity(spilled), - get_irn_in(spilled) + 1); + ins); copy_node_attr(spilled, res); + new_backedge_info(res); - DBG((senv->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader)); + DBG((env->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader)); /* insert in schedule */ - if (is_Block(reloader)) { - ir_node *insert = sched_skip(reloader, 0, sched_skip_cf_predicator, (void *) senv->chordal_env->birg->main_env->arch_env); - sched_add_after(insert, res); - } else { - sched_add_before(reloader, res); - } + assert(!is_Block(reloader)); + sched_add_before(reloader, res); return res; } -/** - * Walker: fills the mem_phis set by evaluating Phi nodes - * using the is_mem_phi() callback. - */ -static void phi_walker(ir_node *irn, void *env) { - spill_env_t *senv = env; - - if (is_Phi(irn)) { - const arch_env_t *arch = senv->chordal_env->birg->main_env->arch_env; - if (arch_irn_has_reg_class(arch, irn, 0, senv->cls) && - senv->is_mem_phi(irn, senv->data)) { - DBG((senv->dbg, LEVEL_1, " %+F\n", irn)); - pset_insert_ptr(senv->mem_phis, irn); - } - } +int be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) { + spill_info_t *spill_info; + + // is the node rematerializable? + int costs = check_remat_conditions_costs(env, to_spill, before, 0); + if(costs < REMAT_COST_LIMIT) + return costs; + + // 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; } -void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) { - const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env; - ir_graph *irg = senv->chordal_env->irg; - unsigned visited_nr; - ir_node *irn; - spill_info_t *si; - pdeq *possibly_dead; - - /* get all special spilled phis */ - DBG((senv->dbg, LEVEL_1, "Mem-phis:\n")); - senv->mem_phis = pset_new_ptr_default(); - irg_walk_graph(senv->chordal_env->irg, phi_walker, NULL, senv); - - /* Add reloads for mem_phis */ - /* BETTER: These reloads (1) should only be inserted, if they are really needed */ - DBG((senv->dbg, LEVEL_1, "Reloads for mem-phis:\n")); - for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) { - const ir_edge_t *e; - DBG((senv->dbg, LEVEL_1, " Mem-phi %+F\n", irn)); - foreach_out_edge(irn, e) { - ir_node *user = e->src; - if (is_Phi(user) && !pset_find_ptr(senv->mem_phis, user)) { - ir_node *use_bl = get_nodes_block(user); - DBG((senv->dbg, LEVEL_1, " non-mem-phi user %+F\n", user)); - be_add_reload_on_edge(senv, irn, use_bl, e->pos); /* (1) */ - } - } - } +int be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) { + ir_node *before = get_reload_insertion_point(block, pos); + return be_get_reload_costs(env, to_spill, before); +} + +/* + * ___ _ ____ _ _ + * |_ _|_ __ ___ ___ _ __| |_ | _ \ ___| | ___ __ _ __| |___ + * | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ |/ _ \ / _` |/ _` / __| + * | || | | \__ \ __/ | | |_ | _ < __/ | (_) | (_| | (_| \__ \ + * |___|_| |_|___/\___|_| \__| |_| \_\___|_|\___/ \__,_|\__,_|___/ + * + */ - visited_nr = get_irg_visited(irg) + 1; - set_irg_visited(irg, visited_nr); +void be_insert_spills_reloads(spill_env_t *env) { + const arch_env_t *arch_env = env->arch_env; + spill_info_t *si; /* process each spilled node */ - DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n")); - possibly_dead = new_pdeq(); - for(si = set_first(senv->spills); si; si = set_next(senv->spills)) { + for(si = set_first(env->spills); si; si = set_next(env->spills)) { reloader_t *rld; ir_mode *mode = get_irn_mode(si->spilled_node); pset *values = pset_new_ptr(16); @@ -451,348 +580,31 @@ void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) { for(rld = si->reloaders; rld; rld = rld->next) { ir_node *new_val; - /* the spill for this reloader */ - ir_node *spill = be_spill_node(senv, si->spilled_node, visited_nr); + if (check_remat_conditions(env, si->spilled_node, rld->reloader)) { + new_val = do_remat(env, si->spilled_node, rld->reloader); + } else { + /* make sure we have a spill */ + spill_node(env, si); -#ifdef REMAT - if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader)) { - new_val = do_remat(senv, si->spilled_node, rld->reloader); - pdeq_putl(possibly_dead, spill); - } - else -#endif /* do a reload */ - new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill); - - DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader)); - pset_insert_ptr(values, new_val); - if(reload_set) - pset_insert_ptr(reload_set, new_val); - } - - /* introduce copies, rewire the uses */ - assert(pset_count(values) > 0 && "???"); - pset_insert_ptr(values, si->spilled_node); - be_ssa_constr_set_ignore(senv->chordal_env->dom_front, values, senv->mem_phis); - - del_pset(values); - } - - foreach_pset(senv->mem_phis, irn) { - int i, n; - for (i = 0, n = get_irn_arity(irn); i < n; ++i) { - pdeq_putl(possibly_dead, get_irn_n(irn, i)); - set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg)); - } - sched_remove(irn); - } - - /* check if possibly dead nodes are really dead yet */ - while (! pdeq_empty(possibly_dead)) { - ir_node *irn = pdeq_getr(possibly_dead); - const ir_edge_t *edge = get_irn_out_edge_first(irn); - - if (! edge) { - int i; - for (i = get_irn_arity(irn) - 1; i >= 0; --i) { - pdeq_putl(possibly_dead, get_irn_n(irn, i)); - set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg)); + new_val = be_reload(arch_env, env->cls, rld->reloader, mode, si->spill); } - sched_remove(irn); - } - } - del_pdeq(possibly_dead); - del_pset(senv->mem_phis); -} -void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) { - spill_info_t templ, *res; - reloader_t *rel; - - templ.spilled_node = to_spill; - templ.reloaders = NULL; - res = set_insert(senv->spills, &templ, sizeof(templ), HASH_PTR(to_spill)); - - rel = obstack_alloc(&senv->obst, sizeof(rel[0])); - rel->reloader = before; - rel->next = res->reloaders; - res->reloaders = rel; -} - -void be_add_reload_on_edge(spill_env_t *senv, ir_node *to_spill, ir_node *bl, int pos) { - ir_node *insert_bl = get_irn_arity(bl) == 1 ? sched_first(bl) : get_Block_cfgpred_block(bl, pos); - be_add_reload(senv, to_spill, insert_bl); -} - - - -/**************************************** - - SPILL SLOT MANAGEMENT AND OPTS - -****************************************/ - -typedef struct _spill_slot_t { - unsigned size; - unsigned align; - pset *members; - ir_mode *largest_mode; /* the mode of all members with largest size */ -} spill_slot_t; - -typedef struct _ss_env_t { - struct obstack ob; - be_chordal_env_t *cenv; - pmap *slots; /* maps spill_contexts to spill_slots */ - pmap *types; /* maps modes to types */ - DEBUG_ONLY(firm_dbg_module_t *dbg;) -} ss_env_t; - - -/** - * Walker: compute the spill slots - */ -static void compute_spill_slots_walker(ir_node *spill, void *env) { - ss_env_t *ssenv = env; - ir_node *ctx; - pmap_entry *entry; - spill_slot_t *ss; - - if (!be_is_Spill(spill)) - return; - - /* check, if this spill is for a context already known */ - ctx = be_get_Spill_context(spill); - entry = pmap_find(ssenv->slots, ctx); - - if (!entry) { - struct _arch_env_t *arch_env = ssenv->cenv->birg->main_env->arch_env; - const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val); - ir_mode *largest_mode = arch_register_class_mode(cls); - - /* this is a new spill context */ - ss = obstack_alloc(&ssenv->ob, sizeof(*ss)); - ss->members = pset_new_ptr(8); - ss->largest_mode = largest_mode; - ss->size = get_mode_size_bytes(ss->largest_mode); - ss->align = arch_isa_get_reg_class_alignment(arch_env->isa, cls); - pmap_insert(ssenv->slots, ctx, ss); - } else { - /* values with the same spill_ctx must go into the same spill slot */ - ss = entry->value; - -#ifndef NDEBUG - /* ugly mega assert :-) */ - { - ir_node *irn; - struct _arch_env_t *arch_env = ssenv->cenv->birg->main_env->arch_env; - const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, spill, be_pos_Spill_val); - int size = get_mode_size_bytes(arch_register_class_mode(cls)); - assert(ss->size == size && "Different sizes for the same spill slot are not allowed."); - for (irn = pset_first(ss->members); irn; irn = pset_next(ss->members)) { - /* use values_interfere here, because it uses the dominance check, - which does work for values in memory */ - assert(!values_interfere(spill, irn) && "Spills for the same spill slot must not interfere!"); - } - } -#endif /* NDEBUG */ - } - - pset_insert_ptr(ss->members, spill); -} - -/** - * qsort compare function, sort spill slots by size. - */ -static int ss_sorter(const void *v1, const void *v2) { - const spill_slot_t **ss1 = (const spill_slot_t **)v1; - const spill_slot_t **ss2 = (const spill_slot_t **)v2; - return ((int) (*ss2)->size) - ((int) (*ss1)->size); -} - - -/** - * This function should optimize the spill slots. - * - Coalescing of multiple slots - * - Ordering the slots - * - * Input slots are in @p ssenv->slots - * @p size The count of initial spill slots in @p ssenv->slots - * This also is the size of the preallocated array @p ass - * - * @return An array of spill slots @p ass in specific order - **/ -static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) { - int i, o, used_slots; - pmap_entry *entr; - - i=0; - pmap_foreach(ssenv->slots, entr) - ass[i++] = entr->value; - - /* Sort the array to minimize fragmentation and cache footprint. - Large slots come first */ - qsort(ass, size, sizeof(ass[0]), ss_sorter); - - /* For each spill slot: - - assign a new offset to this slot - - xor find another slot to coalesce with */ - used_slots = 0; - for (i=0; idbg, LEVEL_1, "Spill slot %d members:\n", i)); - for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members)) - DBG((ssenv->dbg, LEVEL_1, " %+F\n", n1)); - - - for (o=0; o < used_slots && tgt_slot == -1; ++o) { /* for each offset-assigned spill slot */ - /* check inter-slot-pairs for interference */ - ir_node *n2; - for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members)) - for(n2 = pset_first(ass[o]->members); n2; n2 = pset_next(ass[o]->members)) - if(values_interfere(n1, n2)) { - pset_break(ass[i]->members); - pset_break(ass[o]->members); - DBG((ssenv->dbg, LEVEL_1, " Interf %+F -- %+F\n", n1, n2)); - goto interf_detected; - } - - /* if we are here, there is no interference between ass[i] and ass[o] */ - tgt_slot = o; - -interf_detected: /*nothing*/ ; + DBG((env->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader)); + pset_insert_ptr(values, new_val); } - /* now the members of ass[i] join the members of ass[tgt_slot] */ - - /* do we need a new slot? */ - if (tgt_slot == -1) { - tgt_slot = used_slots; - used_slots++; - - /* init slot */ - if (tgt_slot != i) { - ass[tgt_slot]->size = ass[i]->size; - del_pset(ass[tgt_slot]->members); - ass[tgt_slot]->members = pset_new_ptr(8); - } + if(pset_count(values) > 0) { + /* introduce copies, rewire the uses */ + pset_insert_ptr(values, si->spilled_node); + be_ssa_constr_set_ignore(env->chordal_env->dom_front, env->chordal_env->lv, values, env->mem_phis); } - /* copy the members to the target pset */ - /* NOTE: If src and tgt pset are the same, inserting while iterating is not allowed */ - if (tgt_slot != i) - for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members)) - pset_insert_ptr(ass[tgt_slot]->members, n1); - } -} - -#define ALIGN_SPILL_AREA 16 -#define pset_foreach(pset, elm) for(elm=pset_first(pset); elm; elm=pset_next(pset)) - -/** - * Returns a spill type for a mode. Keep them in a map to reduce - * the number of types. - * - * @param types a map containing all created types - * @param ss the spill slot - * - * Note that type types should are identical for every mode. - * This rule might break if two different register classes return the same - * mode but different alignments. - */ -static ir_type *get_spill_type(pmap *types, spill_slot_t *ss) { - pmap_entry *e = pmap_find(types, ss->largest_mode); - ir_type *res; - - if (! e) { - char buf[64]; - snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(ss->largest_mode)); - res = new_type_primitive(new_id_from_str(buf), ss->largest_mode); - set_type_alignment_bytes(res, ss->align); - pmap_insert(types, ss->largest_mode, res); - } - else { - res = e->value; - assert(get_type_alignment_bytes(res) == (int)ss->align); - } - return res; -} + del_pset(values); -/** - * Create spill slot entities on the frame type. - * - * @param ssenv the spill environment - * @param n number of spill slots - * @param ss array of spill slots - */ -static void assign_entities(ss_env_t *ssenv, int n_slots, spill_slot_t *ss[]) { - int i, offset, frame_align; - ir_type *frame = get_irg_frame_type(ssenv->cenv->irg); - - /* aligning by increasing frame size */ - offset = get_type_size_bits(frame) / 8; - offset = round_up2(offset, ALIGN_SPILL_AREA); - set_type_size_bytes(frame, -1); - - /* create entities and assign offsets according to size and alignment*/ - for (i = 0; i < n_slots; ++i) { - char buf[64]; - ident *name; - entity *spill_ent; - ir_node *irn; - - /* build entity */ - snprintf(buf, sizeof(buf), "spill_slot_%d", i); - name = new_id_from_str(buf); - - spill_ent = new_entity(frame, name, get_spill_type(ssenv->types, ss[i])); - - /* align */ - offset = round_up2(offset, ss[i]->align); - /* set */ - set_entity_offset_bytes(spill_ent, offset); - /* next possible offset */ - offset += round_up2(ss[i]->size, ss[i]->align); - - pset_foreach(ss[i]->members, irn) - be_set_Spill_entity(irn, spill_ent); + si->reloaders = NULL; } - /* set final size of stack frame */ - frame_align = get_type_alignment_bytes(frame); - set_type_size_bytes(frame, round_up2(offset, frame_align)); -} - -void be_compute_spill_offsets(be_chordal_env_t *cenv) { - ss_env_t ssenv; - spill_slot_t **ss; - int ss_size; - pmap_entry *pme; - - obstack_init(&ssenv.ob); - ssenv.cenv = cenv; - ssenv.slots = pmap_create(); - ssenv.types = pmap_create(); - FIRM_DBG_REGISTER(ssenv.dbg, "ir.be.spillslots"); - - /* Get initial spill slots */ - irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv); - - /* Build an empty array for optimized spill slots */ - ss_size = pmap_count(ssenv.slots); - ss = obstack_alloc(&ssenv.ob, ss_size * sizeof(*ss)); - optimize_slots(&ssenv, ss_size, ss); - - /* Integrate slots into the stack frame entity */ - assign_entities(&ssenv, ss_size, ss); - - /* Clean up */ - pmap_foreach(ssenv.slots, pme) - del_pset(((spill_slot_t *)pme->value)->members); - pmap_destroy(ssenv.slots); - pmap_destroy(ssenv.types); - obstack_free(&ssenv.ob, NULL); - - be_copy_entities_to_reloads(cenv->irg); + be_remove_dead_nodes_from_schedule(env->chordal_env->irg); + be_liveness_recompute(env->chordal_env->lv); }