X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=f8df2a8c65a4e6bdf45538a3b9e9dd7fc57d3c5b;hb=f6803e61a5c32b49e3d8f9cdd3ce10d0036c5b37;hp=dc684d011878e49ee7abbb567ccbcf59774eec4f;hpb=416f5cea230b1061936ff71810aeef66044e50f7;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index dc684d011..f8df2a8c6 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.c @@ -8,11 +8,14 @@ #include "config.h" #endif +#include + #include "pset.h" #include "irnode_t.h" #include "ircons_t.h" #include "iredges_t.h" #include "debug.h" +#include "irgwalk.h" #include "besched.h" #include "bespill.h" @@ -102,7 +105,7 @@ static ir_node *be_spill_irn(spill_env_t *senv, ir_node *irn, ir_node *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->main_env; - ctx->spill = be_spill(env->node_factory, env->arch_env, irn, ctx_irn); + ctx->spill = be_spill(env->arch_env, irn, ctx_irn); } return ctx->spill; @@ -216,8 +219,7 @@ void be_insert_spills_reloads(spill_env_t *senv, pset *reload_set) { /* the reload */ ir_node *bl = is_Block(rld->reloader) ? rld->reloader : get_nodes_block(rld->reloader); - ir_node *reload = new_Reload(senv->chordal_env->main_env->node_factory, - senv->cls, irg, bl, mode, spill); + ir_node *reload = be_new_Reload(senv->cls, irg, bl, mode, spill); DBG((senv->dbg, LEVEL_1, " %+F of %+F before %+F\n", reload, si->spilled_node, rld->reloader)); if(reload_set) @@ -266,3 +268,170 @@ void be_add_reload_on_edge(spill_env_t *senv, ir_node *to_spill, ir_node *bl, in 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 offset; + pset *members; +} 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 */ +} ss_env_t; + + +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) { + /* this is a new spill context */ + ss = obstack_alloc(&ssenv->ob, sizeof(*ss)); + ss->members = pset_new_ptr(8); + ss->size = get_mode_size_bytes(get_irn_mode(get_irn_n(spill, 0))); + 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, 0))) && "Different sizes for the same spill slot"); + 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!"); + } + } + + pset_insert_ptr(ss->members, spill); +} + +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); +} + + +/* NOTE/TODO: This function assumes, that all spill slot sizes are a power of 2. + Further it assumes, that the alignment is equal to the size and the + baseaddr of the spill area is aligned sufficiently for all possible aligments. +*/ +static void coalesce_slots(ss_env_t *ssenv) { + int i, o, used_slots; + unsigned curr_offset; + pmap_entry *entr; + spill_slot_t **ass; + + /* Build an array of all spill slots */ + int count = pmap_count(ssenv->slots); + ass = obstack_alloc(&ssenv->ob, count * sizeof(*ass)); + + 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, count, sizeof(ass[0]), ss_sorter); + + /* For each spill slot: + - assign a new offset to this slot + - xor find another slot to coalesce with */ + curr_offset = 0; + 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*/ ; + } + + /* 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++; + + ass[tgt_slot]->offset = curr_offset; + curr_offset += ass[i]->size; + + /* 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); + } + } + + /* copy the members to the target pset */ + for(n1 = pset_first(ass[i]->members); n1; n1 = pset_next(ass[i]->members)) { + /* NOTE: If src and tgt pset are the same, inserting while iterating is not allowed */ + if (tgt_slot != i) + pset_insert_ptr(ass[tgt_slot]->members, n1); + + be_set_Spill_offset(n1, ass[tgt_slot]->offset); + DBG((ssenv->dbg, LEVEL_1, " Offset %+F %d\n", n1, ass[tgt_slot]->offset)); + } + } + + /* free all used psets, all other stuff is on the ssenv-obstack */ + for (i=0; imembers); + +} + +void be_compute_spill_offsets(be_chordal_env_t *cenv) { + ss_env_t ssenv; + + obstack_init(&ssenv.ob); + ssenv.cenv = cenv; + ssenv.slots = pmap_create(); + ssenv.dbg = firm_dbg_register("ir.be.spillslots"); + + irg_walk_graph(cenv->irg, NULL, compute_spill_slots_walker, &ssenv); + coalesce_slots(&ssenv); + + pmap_destroy(ssenv.slots); + obstack_free(&ssenv.ob, NULL); +}