X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=43ed0d08136cb67d70dcc50f949731b6d0cb168e;hb=857cb493902e7d54651141fd600f980c383d5fe6;hp=5738414d6c400ff89536b48297ebe564756fe9be;hpb=c9623d3dd138aca08572167934c1a7c1fb826344;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 5738414d6..43ed0d081 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -20,6 +20,7 @@ #include "debug.h" #include "irgwalk.h" #include "array.h" +#include "pdeq.h" #include "belive_t.h" #include "besched_t.h" @@ -50,52 +51,88 @@ typedef struct _spill_ctx_t { } spill_ctx_t; struct _spill_env_t { - firm_dbg_module_t *dbg; const arch_register_class_t *cls; 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 seperately */ - decide_irn_t is_mem_phi; /**< callback func to decide if a phi needs special spilling */ - void *data; /**< data passed to all callbacks */ + pset *mem_phis; /**< set of all special spilled phis. allocated and freed separately */ + ir_node **copies; /**< set of copies placed because of phi spills */ + 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. + */ +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; +} + +/** + * compare two spill contexts. + */ 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); + return p->user != q->user || p->spilled != q->spilled; } +/** + * Compare two spill infos. + */ 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); + return xx->spilled_node != yy->spilled_node; } -spill_env_t *be_new_spill_env(firm_dbg_module_t *dbg, - 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->dbg = dbg; - env->is_mem_phi = is_mem_phi; - env->data = data; - env->chordal_env = chordal_env; +DEBUG_ONLY( +/* Sets the debug module of a spill environment. */ +void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) { + env->dbg = dbg; +} +) + +/* Creates a new spill environment. */ +spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env) { + 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->chordal_env = chordal_env; + env->mem_phis = pset_new_ptr_default(); + env->copies = NEW_ARR_F(ir_node*, 0); obstack_init(&env->obst); return env; } -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); +/* Deletes a spill environment. */ +void be_delete_spill_env(spill_env_t *env) { + del_set(env->spill_ctxs); + del_set(env->spills); + del_pset(env->mem_phis); + DEL_ARR_F(env->copies); + 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; @@ -106,90 +143,235 @@ static spill_ctx_t *be_get_spill_ctx(set *sc, ir_node *to_spill, ir_node *ctx_ir return set_insert(sc, &templ, sizeof(templ), HASH_COMBINE(HASH_PTR(to_spill), HASH_PTR(ctx_irn))); } +/** + * Schedules a node after an instruction. (That is the place after all projs and phis + * that are scheduled after the instruction) + */ +static void sched_add_after_insn(ir_node *sched_after, ir_node *node) { + ir_node *next = sched_next(sched_after); + while(!sched_is_end(next)) { + if(!is_Proj(next) && !is_Phi(next)) + break; + next = sched_next(next); + } + + if(sched_is_end(next)) { + next = sched_last(get_nodes_block(sched_after)); + sched_add_after(next, node); + } else { + sched_add_before(next, node); + } +} + +/** + * Creates a spill. + * + * @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 + */ static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *ctx_irn) { spill_ctx_t *ctx; + const be_main_env_t *env = senv->chordal_env->birg->main_env; DBG((senv->dbg, LEVEL_1, "%+F in ctx %+F\n", irn, ctx_irn)); + // Has the value already been spilled? 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); + if(ctx->spill) + return ctx->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 + */ + if(be_is_Reload(irn)) { + return get_irn_n(irn, be_pos_Reload_mem); } + ctx->spill = be_spill(env->arch_env, irn, ctx_irn); + sched_add_after_insn(irn, ctx->spill); + return ctx->spill; } /** - * If the first usage of a phi result would be out of memory + * Removes all copies introduced for phi-spills + */ +static void remove_copies(spill_env_t *env) { + int i; + + for(i = 0; i < ARR_LEN(env->copies); ++i) { + ir_node *node = env->copies[i]; + ir_node *src; + const ir_edge_t *edge, *ne; + + assert(be_is_Copy(node)); + + src = be_get_Copy_op(node); + foreach_out_edge_safe(node, edge, ne) { + ir_node *user = get_edge_src_irn(edge); + int user_pos = get_edge_src_pos(edge); + + set_irn_n(user, user_pos, src); + } + } + + ARR_SETLEN(ir_node*, env->copies, 0); +} + +static INLINE ir_node *skip_projs(ir_node *node) { + while(is_Proj(node)) { + node = sched_next(node); + assert(!sched_is_end(node)); + } + + return node; +} + +/** + * Searchs the schedule backwards until we reach the first use or def of a + * value or a phi. + * Returns the node after this node (so that you can do sched_add_before) + */ +static ir_node *find_last_use_def(spill_env_t *env, ir_node *block, ir_node *value) { + ir_node *node, *last; + + last = NULL; + sched_foreach_reverse(block, node) { + int i, arity; + + if(is_Phi(node)) { + return last; + } + if(value == node) { + return skip_projs(last); + } + for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *arg = get_irn_n(node, i); + if(arg == value) { + return skip_projs(last); + } + } + last = node; + } + + // simply return first node if no def or use found + return sched_first(block); +} + +/** + * If the first usage of a Phi result would be out of memory * there is no sense in allocating a register for it. * Thus we spill it and all its operands to the same spill slot. * Therefore the phi/dataB becomes a phi/Memory + * + * @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) { - int i, n = get_irn_arity(phi); - ir_node **ins, *bl = get_nodes_block(phi); - ir_graph *irg = senv->chordal_env->irg; +static ir_node *spill_phi(spill_env_t *senv, ir_node *phi, ir_node *ctx_irn, set *already_visited_phis, bitset_t *bs) { + int i; + int arity = 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; 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, arity); + for (i = 0; i < arity; ++i) { + ins[i] = new_r_Bad(irg); + } + phi_spill = new_r_Phi(senv->chordal_env->irg, bl, arity, ins, mode_M); + key.phi = phi; + key.spill = phi_spill; + set_insert(already_visited_phis, &key, sizeof(key), HASH_PTR(phi)); + bitset_set(bs, get_irn_idx(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) { - /* build a new PhiM with dummy in-array */ - NEW_ARR_A(ir_node *, ins, n); - for(i=0; ispill = new_r_Phi(senv->chordal_env->irg, bl, n, ins, mode_M); - - /* re-wire the phiM */ - for(i=0; ispill) { + /* collect all arguments of the phi */ + for (i = 0; i < arity; ++i) { ir_node *arg = get_irn_n(phi, i); ir_node *sub_res; - - if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg)) - sub_res = be_spill_phi(senv, arg, ctx_irn); - else + phi_spill_assoc_t *entry; + + if(is_Phi(arg) && pset_find_ptr(senv->mem_phis, arg)) { + // looping edge? + if(arg == phi) { + sub_res = phi_spill; + } else if (! bitset_is_set(bs, get_irn_idx(arg))) { + sub_res = spill_phi(senv, arg, ctx_irn, already_visited_phis, bs); + } 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); + } - set_irn_n(ctx->spill, i, sub_res); + set_irn_n(phi_spill, i, sub_res); } + + ctx->spill = phi_spill; } return ctx->spill; } +/** + * Spill a node. + * + * @param senv the spill environment + * @param to_spill the node that should be spilled + * + * @return a be_Spill node + */ static ir_node *be_spill_node(spill_env_t *senv, ir_node *to_spill) { - ir_node *res; - if (pset_find_ptr(senv->mem_phis, to_spill)) - res = be_spill_phi(senv, to_spill, to_spill); - else + ir_graph *irg = get_irn_irg(to_spill); + ir_node *res; + + if (pset_find_ptr(senv->mem_phis, to_spill)) { + set *already_visited_phis = new_set(cmp_phi_spill_assoc, 10); + bitset_t *bs = bitset_alloca(get_irg_last_idx(irg)); + res = spill_phi(senv, to_spill, to_spill, already_visited_phis, bs); + del_set(already_visited_phis); + } else { res = be_spill_irn(senv, to_spill, to_spill); + } return res; } -static void phi_walker(ir_node *irn, void *env) { - spill_env_t *senv = env; - const arch_env_t *arch = senv->chordal_env->birg->main_env->arch_env; - - if (is_Phi(irn) && 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); - } -} - - #ifdef BUGGY_REMAT -static int check_remat_conditions(spill_env_t *senv, ir_node *spill, ir_node *spilled, ir_node *reloader) { +/** + * 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 *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)) + if (!arch_irn_is(senv->chordal_env->birg->main_env->arch_env, spilled, rematerializable)) return 0; /* check availability of original arguments */ @@ -237,6 +419,32 @@ is_alive: ; return 1; } +#else /* BUGGY_REMAT */ + +/** + * A very simple rematerialization checker. + * + * @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 *spilled, ir_node *reloader) { + const arch_env_t *aenv = senv->chordal_env->birg->main_env->arch_env; + + return get_irn_arity(spilled) == 0 && + arch_irn_is(aenv, spilled, rematerializable); +} + +#endif /* BUGGY_REMAT */ + +/** + * Re-materialize a node. + * + * @param senv the spill environment + * @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) { ir_node *res; ir_node *bl = (is_Block(reloader)) ? reloader : get_nodes_block(reloader); @@ -246,7 +454,8 @@ static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) get_irn_op(spilled), get_irn_mode(spilled), get_irn_arity(spilled), - get_irn_in(spilled)); + get_irn_in(spilled) + 1); + copy_node_attr(spilled, res); DBG((senv->dbg, LEVEL_1, "Insert remat %+F before reloader %+F\n", res, reloader)); @@ -261,38 +470,89 @@ static ir_node *do_remat(spill_env_t *senv, ir_node *spilled, ir_node *reloader) return res; } -#endif +static place_copies_for_phi(spill_env_t *env, ir_node* node) { + int i, arity; -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; - ir_node *irn; - spill_info_t *si; + assert(is_Phi(node)); + + /* We have to place copy nodes in the predecessor blocks to temporarily + * produce new values that get separate spill slots + */ + for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { + ir_node *pred_block, *arg, *copy, *insert_point; - /* 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); + /* Don't do anything for looping edges (there's no need + * and placing copies here breaks stuff as it suddenly + * generates new living values through the whole loop) + */ + arg = get_irn_n(node, i); + if(arg == node) + continue; + + pred_block = get_Block_cfgpred_block(get_nodes_block(node), i); + copy = be_new_Copy(env->cls, get_irn_irg(arg), pred_block, arg); + + ARR_APP1(ir_node*, env->copies, copy); + insert_point = find_last_use_def(env, pred_block, arg); + sched_add_before(insert_point, copy); + + set_irn_n(node, i, copy); + } +} + +void be_place_copies(spill_env_t *env) { + ir_node *node; + + foreach_pset(env->mem_phis, node) { + place_copies_for_phi(env, node); + } +} + +void be_spill_phi(spill_env_t *env, ir_node *node) { + spill_ctx_t *spill_ctx; + + assert(is_Phi(node)); + + pset_insert_ptr(env->mem_phis, node); + + // remove spill context for this phi (if there was one) + spill_ctx = be_get_spill_ctx(env->spill_ctxs, node, node); + if(spill_ctx != NULL) { + spill_ctx->spill = NULL; + } +} + +void be_insert_spills_reloads(spill_env_t *env) { + const arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env; + //ir_node *node; + spill_info_t *si; - /* 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)) { +#if 0 + // Matze: This should be pointless as beladies fix_block_borders + // should result in the same + DBG((env->dbg, LEVEL_1, "Reloads for mem-phis:\n")); + foreach_pset(env->mem_phis, node) { const ir_edge_t *e; - DBG((senv->dbg, LEVEL_1, " Mem-phi %+F\n", irn)); - foreach_out_edge(irn, e) { + + assert(is_Phi(node)); + + /* Add reloads for mem_phis */ + /* BETTER: These reloads (1) should only be inserted, if they are really needed */ + DBG((env->dbg, LEVEL_1, " Mem-phi %+F\n", node)); + foreach_out_edge(node, 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) */ + if (is_Phi(user) && !pset_find_ptr(env->mem_phis, user)) { + ir_node *use_bl = get_nodes_block(user); + DBG((env->dbg, LEVEL_1, " non-mem-phi user %+F\n", user)); + be_add_reload_on_edge(env, node, use_bl, e->pos); /* (1) */ } } } +#endif /* process each spilled node */ - DBG((senv->dbg, LEVEL_1, "Insert spills and reloads:\n")); - for(si = set_first(senv->spills); si; si = set_next(senv->spills)) { + DBG((env->dbg, LEVEL_1, "Insert spills and reloads:\n")); + 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); @@ -301,61 +561,78 @@ 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); + if (check_remat_conditions(env, si->spilled_node, rld->reloader)) { + new_val = do_remat(env, si->spilled_node, rld->reloader); + } else { + /* the spill for this reloader */ + ir_node *spill = be_spill_node(env, si->spilled_node); -#ifdef BUGGY_REMAT - if (check_remat_conditions(senv, spill, si->spilled_node, rld->reloader)) - new_val = do_remat(senv, si->spilled_node, rld->reloader); - else -#endif /* do a reload */ - new_val = be_reload(aenv, senv->cls, rld->reloader, mode, spill); + new_val = be_reload(arch_env, env->cls, rld->reloader, mode, spill); + } - DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", new_val, si->spilled_node, rld->reloader)); + DBG((env->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); + be_ssa_constr_set_ignore(env->chordal_env->dom_front, values, env->mem_phis); del_pset(values); } - for(irn = pset_first(senv->mem_phis); irn; irn = pset_next(senv->mem_phis)) { - int i, n; - for(i = 0, n = get_irn_arity(irn); i < n; ++i) - set_irn_n(irn, i, new_r_Bad(senv->chordal_env->irg)); - sched_remove(irn); - } + remove_copies(env); - del_pset(senv->mem_phis); + // reloads are placed now, but we might reuse the spill environment for further spilling decisions + del_set(env->spills); + env->spills = new_set(cmp_spillinfo, 1024); } -void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before) { +void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before) { spill_info_t templ, *res; reloader_t *rel; + assert(sched_is_scheduled(before)); + assert(arch_irn_consider_in_reg_alloc(env->chordal_env->birg->main_env->arch_env, env->cls, to_spill)); + templ.spilled_node = to_spill; templ.reloaders = NULL; - res = set_insert(senv->spills, &templ, sizeof(templ), HASH_PTR(to_spill)); + res = set_insert(env->spills, &templ, sizeof(templ), HASH_PTR(to_spill)); - rel = obstack_alloc(&senv->obst, sizeof(rel[0])); + rel = obstack_alloc(&env->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); -} +void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, 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))); + be_add_reload(env, to_spill, sched_first(block)); + return; + } + /* 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 + be_add_reload(env, to_spill, last); +} /**************************************** @@ -371,14 +648,17 @@ typedef struct _spill_slot_t { } spill_slot_t; typedef struct _ss_env_t { - firm_dbg_module_t *dbg; struct obstack ob; be_chordal_env_t *cenv; pmap *slots; /* maps spill_contexts to spill_slots */ - pmap *types; /* maps modes to types */ + 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; @@ -393,32 +673,48 @@ static void compute_spill_slots_walker(ir_node *spill, void *env) { 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 = get_irn_mode(get_irn_n(spill, be_pos_Spill_val)); - ss->size = get_mode_size_bytes(ss->largest_mode); - ss->align = ss->size; /* TODO Assumed for now */ + 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 { - ir_node *irn; /* values with the same spill_ctx must go into the same spill slot */ ss = entry->value; - assert(ss->size == (unsigned)get_mode_size_bytes(get_irn_mode(get_irn_n(spill, be_pos_Spill_val))) && "Different sizes for the same spill slot are not allowed yet."); - 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!"); + +#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((int) 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 = v1; - const spill_slot_t *ss2 = v2; - return ((int) ss2->size) - ((int) ss1->size); + 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); } @@ -433,7 +729,7 @@ static int ss_sorter(const void *v1, const void *v2) { * * @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) { +static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t *ass[]) { int i, o, used_slots; pmap_entry *entr; @@ -449,7 +745,8 @@ static void optimize_slots(ss_env_t *ssenv, int size, spill_slot_t **ass) { - assign a new offset to this slot - xor find another slot to coalesce with */ used_slots = 0; - for (i=0; ilargest_mode); + ir_type *res; - if (! e) { + if (! e) { char buf[64]; - snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(mode)); - res = new_type_primitive(new_id_from_str(buf), mode); - pmap_insert(types, mode, res); - } - else - res = e->value; - return res; + snprintf(buf, sizeof(buf), "spill_slot_type_%s", get_mode_name(ss->largest_mode)); + buf[sizeof(buf) - 1] = '\0'; + 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; } -static void assign_entities(ss_env_t *ssenv, int n, spill_slot_t **ss) { - int i, offset; - ir_type *frame = get_irg_frame_type(ssenv->cenv->irg); +/** + * 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; + + /* do not align the frame if no spill slots are needed */ + if (n_slots <= 0) + return; + + frame = get_irg_frame_type(ssenv->cenv->irg); /* aligning by increasing frame size */ - offset = get_type_size_bits(frame) / 8; + offset = get_type_size_bytes(frame); 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; itypes, ss[i]->largest_mode)); + 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 += ss[i]->size; + offset += round_up2(ss[i]->size, ss[i]->align); pset_foreach(ss[i]->members, irn) be_set_Spill_entity(irn, spill_ent); } + /* set final size of stack frame */ - set_type_size_bytes(frame, offset); + 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) { @@ -568,7 +891,7 @@ void be_compute_spill_offsets(be_chordal_env_t *cenv) { ssenv.cenv = cenv; ssenv.slots = pmap_create(); ssenv.types = pmap_create(); - ssenv.dbg = firm_dbg_register("ir.be.spillslots"); + FIRM_DBG_REGISTER(ssenv.dbg, "ir.be.spillslots"); /* Get initial spill slots */ irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv);