X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillslots.c;h=b3fa6f9211951d84c3b0bacb829f8878d353f626;hb=bdc59608633f59b0541a04883c24d19b1bc0ffae;hp=fdf1922eceef82d23c15a89a6ef63462c2ade667;hpb=ea75e9d38674b468f602a0699fb64b9c01254797;p=libfirm diff --git a/ir/be/bespillslots.c b/ir/be/bespillslots.c index fdf1922ec..b3fa6f921 100644 --- a/ir/be/bespillslots.c +++ b/ir/be/bespillslots.c @@ -48,38 +48,41 @@ #include "beirg.h" #include "bearch.h" -#define DBG_COALESCING 1 -#define DBG_INTERFERENCES 2 +#define DBG_COALESCING 1 +#define DBG_INTERFERENCES 2 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -typedef struct _spill_t { - ir_node *spill; - const ir_mode *mode; /**< mode of the spilled value */ - int alignment; /**< alignment for the spilled value */ - int spillslot; /**< index into spillslot_unionfind structure */ +typedef struct spill_t { + ir_node *spill; + const ir_mode *mode; /**< mode of the spilled value */ + int alignment; /**< alignment for the spilled value */ + int spillslot; /**< index into spillslot_unionfind structure */ } spill_t; -typedef struct _affinity_edge_t { +typedef struct affinity_edge_t { double affinity; - int slot1, slot2; + int slot1; + int slot2; } affinity_edge_t; -struct _be_fec_env_t { - struct obstack obst; - const arch_env_t *arch_env; - be_irg_t *birg; - set *spills; - ir_node **reloads; - affinity_edge_t **affinity_edges; - set *memperms; +struct be_fec_env_t { + struct obstack obst; + ir_graph *irg; + set *spills; + ir_node **reloads; + affinity_edge_t **affinity_edges; + set *memperms; + set_frame_entity_func set_frame_entity; + bool at_begin; /**< frame entities should be allocate at + the beginning of the stackframe */ }; /** Compare 2 affinity edges (used in quicksort) */ static int cmp_affinity(const void *d1, const void *d2) { - const affinity_edge_t * const *e1 = d1; - const affinity_edge_t * const *e2 = d2; + const affinity_edge_t * const *e1 = (const affinity_edge_t**)d1; + const affinity_edge_t * const *e2 = (const affinity_edge_t**)d2; /* sort in descending order */ return (*e1)->affinity < (*e2)->affinity ? 1 : -1; @@ -87,8 +90,8 @@ static int cmp_affinity(const void *d1, const void *d2) static int cmp_spill(const void* d1, const void* d2, size_t size) { - const spill_t* s1 = d1; - const spill_t* s2 = d2; + const spill_t* s1 = (const spill_t*)d1; + const spill_t* s2 = (const spill_t*)d2; (void) size; return s1->spill != s2->spill; @@ -100,7 +103,7 @@ static spill_t *get_spill(be_fec_env_t *env, ir_node *node) int hash = hash_irn(node); spill.spill = node; - res = set_find(env->spills, &spill, sizeof(spill), hash); + res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); return res; } @@ -128,13 +131,13 @@ static spill_t *collect_spill(be_fec_env_t *env, ir_node *node, /* insert into set of spills if not already there */ spill.spill = node; - res = set_find(env->spills, &spill, sizeof(spill), hash); + res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); if (res == NULL) { spill.spillslot = set_count(env->spills); spill.mode = mode; spill.alignment = align; - res = set_insert(env->spills, &spill, sizeof(spill), hash); + res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash); DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node)); } else { assert(res->mode == mode); @@ -150,12 +153,12 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, int i, arity; spill_t spill, *res; int hash = hash_irn(node); - const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg); + const ir_exec_freq *exec_freq = be_get_irg_exec_freq(env->irg); assert(is_Phi(node)); spill.spill = node; - res = set_find(env->spills, &spill, sizeof(spill), hash); + res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); if (res != NULL) { assert(res->mode == mode); assert(res->alignment == align); @@ -166,7 +169,7 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, spill.mode = mode; spill.alignment = align; DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node)); - res = set_insert(env->spills, &spill, sizeof(spill), hash); + res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash); /* collect attached spills and mem-phis */ arity = get_irn_arity(node); @@ -241,10 +244,10 @@ static int merge_interferences(be_fec_env_t *env, bitset_t** interferences, return res; } -static int my_values_interfere2(be_irg_t *birg, const ir_node *a, +static int my_values_interfere2(ir_graph *irg, const ir_node *a, const ir_node *b) { - be_lv_t *lv = be_get_birg_liveness(birg); + be_lv_t *lv = be_get_irg_liveness(irg); int a2b = _value_dominates(a, b); int b2a = _value_dominates(b, a); @@ -309,13 +312,13 @@ static int my_values_interfere2(be_irg_t *birg, const ir_node *a, /** * same as values_interfere but with special handling for Syncs */ -static int my_values_interfere(be_irg_t *birg, ir_node *a, ir_node *b) +static int my_values_interfere(ir_graph *irg, ir_node *a, ir_node *b) { if (is_Sync(a)) { int i, arity = get_irn_arity(a); for (i = 0; i < arity; ++i) { ir_node *in = get_irn_n(a, i); - if (my_values_interfere(birg, in, b)) + if (my_values_interfere(irg, in, b)) return 1; } return 0; @@ -324,13 +327,13 @@ static int my_values_interfere(be_irg_t *birg, ir_node *a, ir_node *b) for (i = 0; i < arity; ++i) { ir_node *in = get_irn_n(b, i); /* a is not a sync, so no need for my_values_interfere */ - if (my_values_interfere2(birg, a, in)) + if (my_values_interfere2(irg, a, in)) return 1; } return 0; } - return my_values_interfere2(birg, a, b); + return my_values_interfere2(irg, a, b); } /** @@ -348,16 +351,19 @@ static void do_greedy_coalescing(be_fec_env_t *env) int affinity_edge_count; bitset_t **interferences; int* spillslot_unionfind; + struct obstack data; spillcount = set_count(env->spills); if (spillcount == 0) return; + obstack_init(&data); + DB((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount)); - interferences = ALLOCAN(bitset_t*, spillcount); - spillslot_unionfind = ALLOCAN(int, spillcount); - spilllist = ALLOCAN(spill_t*, spillcount); + interferences = OALLOCN(&data, bitset_t*, spillcount); + spillslot_unionfind = OALLOCN(&data, int, spillcount); + spilllist = OALLOCN(&data, spill_t*, spillcount); uf_init(spillslot_unionfind, spillcount); @@ -365,14 +371,15 @@ static void do_greedy_coalescing(be_fec_env_t *env) memset(spilllist, 0, spillcount * sizeof(spilllist[0])); ); - for (spill = set_first(env->spills), i = 0; spill != NULL; - spill = set_next(env->spills), ++i) { + i = 0; + foreach_set(env->spills, spill_t*, spill) { assert(spill->spillslot < spillcount); spilllist[spill->spillslot] = spill; + ++i; } for (i = 0; i < spillcount; ++i) { - interferences[i] = bitset_alloca(spillcount); + interferences[i] = bitset_obstack_alloc(&data, spillcount); } /* construct interferences */ @@ -388,7 +395,7 @@ static void do_greedy_coalescing(be_fec_env_t *env) if (is_NoMem(spill2)) continue; - if (my_values_interfere(env->birg, spill1, spill2)) { + if (my_values_interfere(env->irg, spill1, spill2)) { DB((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n", i, i2)); @@ -462,25 +469,26 @@ static void do_greedy_coalescing(be_fec_env_t *env) } /*dump_interference_graph(env, interferences, "after");*/ + obstack_free(&data, 0); } -typedef struct _spill_slot_t { +typedef struct spill_slot_t { int size; int align; ir_entity *entity; } spill_slot_t; -typedef struct _memperm_entry_t { +typedef struct memperm_entry_t { ir_node* node; int pos; ir_entity *in; ir_entity *out; - struct _memperm_entry_t *next; + struct memperm_entry_t *next; } memperm_entry_t; -typedef struct _memperm_t { +typedef struct memperm_t { ir_node *block; int entrycount; memperm_entry_t *entries; @@ -488,8 +496,8 @@ typedef struct _memperm_t { static int cmp_memperm(const void* d1, const void* d2, size_t size) { - const memperm_t* e1 = d1; - const memperm_t* e2 = d2; + const memperm_t* e1 = (const memperm_t*)d1; + const memperm_t* e2 = (const memperm_t*)d2; (void) size; return e1->block != e2->block; @@ -503,12 +511,12 @@ static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block) entry.block = block; hash = hash_irn(block); - res = set_find(env->memperms, &entry, sizeof(entry), hash); + res = (memperm_t*)set_find(env->memperms, &entry, sizeof(entry), hash); if (res == NULL) { entry.entrycount = 0; entry.entries = NULL; - res = set_insert(env->memperms, &entry, sizeof(entry), hash); + res = (memperm_t*)set_insert(env->memperms, &entry, sizeof(entry), hash); } return res; @@ -516,12 +524,10 @@ static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block) static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot) { - ir_graph *irg = be_get_birg_irg(env->birg); - ir_type *frame = get_irg_frame_type(irg); - /* TODO: backend should be able to specify wether we want spill slots - * at begin or end of frame */ - int at_start = 1; - ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, at_start); + ir_graph *irg = env->irg; + ir_type *frame = get_irg_frame_type(irg); + ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, + env->at_begin); /* adjust size of the entity type... */ ir_type *enttype = get_entity_type(res); @@ -551,8 +557,8 @@ static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize) } } - -static void assign_spill_entity(ir_node *node, ir_entity *entity) +static void assign_spill_entity(be_fec_env_t *env, + ir_node *node, ir_entity *entity) { if (is_NoMem(node)) return; @@ -564,7 +570,7 @@ static void assign_spill_entity(ir_node *node, ir_entity *entity) ir_node *in = get_irn_n(node, i); assert(!is_Phi(in)); - assign_spill_entity(in, entity); + assign_spill_entity(env, in, entity); } return; } @@ -573,7 +579,7 @@ static void assign_spill_entity(ir_node *node, ir_entity *entity) instance */ node = skip_Proj(node); assert(arch_get_frame_entity(node) == NULL); - arch_set_frame_entity(node, entity); + env->set_frame_entity(node, entity); } /** @@ -585,12 +591,10 @@ static void assign_spillslots(be_fec_env_t *env) int spillcount = set_count(env->spills); spill_slot_t *spillslots = ALLOCANZ(spill_slot_t, spillcount); spill_t *spill; - int i; + size_t i; /* construct spillslots */ - for (spill = set_first(env->spills); spill != NULL; - spill = set_next(env->spills)) { - + foreach_set(env->spills, spill_t*, spill) { int slotid = spill->spillslot; const ir_mode *mode = spill->mode; spill_slot_t *slot = & (spillslots[slotid]); @@ -605,9 +609,7 @@ static void assign_spillslots(be_fec_env_t *env) } } - for (spill = set_first(env->spills); spill != NULL; - spill = set_next(env->spills)) { - + foreach_set(env->spills, spill_t*, spill) { ir_node *node = spill->spill; int slotid = spill->spillslot; spill_slot_t *slot; @@ -655,7 +657,7 @@ static void assign_spillslots(be_fec_env_t *env) } } } else { - assign_spill_entity(node, slot->entity); + assign_spill_entity(env, node, slot->entity); } } @@ -667,7 +669,7 @@ static void assign_spillslots(be_fec_env_t *env) assert(slot->entity != NULL); - arch_set_frame_entity(reload, slot->entity); + env->set_frame_entity(reload, slot->entity); } } @@ -696,11 +698,9 @@ static ir_node *get_end_of_block_insertion_point(ir_node* block) static void create_memperms(be_fec_env_t *env) { - const arch_env_t *arch_env = env->arch_env; - ir_graph *irg = be_get_birg_irg(env->birg); memperm_t *memperm; - for (memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) { + foreach_set(env->memperms, memperm_t*, memperm) { ir_node **nodes = ALLOCAN(ir_node*, memperm->entrycount); memperm_entry_t *entry; ir_node *blockend; @@ -714,8 +714,8 @@ static void create_memperms(be_fec_env_t *env) nodes[i] = arg; } - mempermnode = be_new_MemPerm(arch_env, memperm->block, - memperm->entrycount, nodes); + mempermnode = be_new_MemPerm(memperm->block, memperm->entrycount, + nodes); /* insert node into schedule */ blockend = get_end_of_block_insertion_point(memperm->block); @@ -729,8 +729,7 @@ static void create_memperms(be_fec_env_t *env) be_set_MemPerm_in_entity(mempermnode, i, entry->in); be_set_MemPerm_out_entity(mempermnode, i, entry->out); - set_irg_current_block(irg, memperm->block); - proj = new_Proj(mempermnode, get_irn_mode(arg), i); + proj = new_r_Proj(mempermnode, get_irn_mode(arg), i); set_irn_n(entry->node, entry->pos, proj); } @@ -745,8 +744,7 @@ static int count_spillslots(const be_fec_env_t *env) int slotcount; slotcount = 0; - for (spill = set_first(env->spills); spill != NULL; - spill = set_next(env->spills)) { + foreach_set(env->spills, spill_t*, spill) { int spillslot = spill->spillslot; if (!bitset_is_set(counted, spillslot)) { slotcount++; @@ -757,16 +755,14 @@ static int count_spillslots(const be_fec_env_t *env) return slotcount; } -be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg) +be_fec_env_t *be_new_frame_entity_coalescer(ir_graph *irg) { - const arch_env_t *arch_env = birg->main_env->arch_env; - be_fec_env_t *env = XMALLOC(be_fec_env_t); + be_fec_env_t *env = XMALLOCZ(be_fec_env_t); - be_liveness_assure_chk(be_assure_liveness(birg)); + be_liveness_assure_chk(be_assure_liveness(irg)); obstack_init(&env->obst); - env->arch_env = arch_env; - env->birg = birg; + env->irg = irg; env->spills = new_set(cmp_spill, 10); env->reloads = NEW_ARR_F(ir_node*, 0); env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0); @@ -786,8 +782,13 @@ void be_free_frame_entity_coalescer(be_fec_env_t *env) free(env); } -void be_assign_entities(be_fec_env_t *env) +void be_assign_entities(be_fec_env_t *env, + set_frame_entity_func set_frame_entity, + bool alloc_entities_at_begin) { + env->set_frame_entity = set_frame_entity; + env->at_begin = alloc_entities_at_begin; + stat_ev_dbl("spillslots", set_count(env->spills)); if (be_coalesce_spill_slots) { @@ -801,44 +802,7 @@ void be_assign_entities(be_fec_env_t *env) create_memperms(env); } -/** - * This walker function searches for reloads and collects all the spills - * and memphis attached to them. - */ -static void collect_spills_walker(ir_node *node, void *data) -{ - be_fec_env_t *env = data; - const ir_mode *mode; - const arch_register_class_t *cls; - int align; - - /* classify returns classification of the irn the proj is attached to */ - if (is_Proj(node)) - return; - - if (!arch_irn_class_is(node, reload)) - return; - - mode = get_irn_mode(node); - cls = arch_get_irn_reg_class_out(node); - align = arch_env_get_reg_class_alignment(env->arch_env, cls); - - be_node_needs_frame_entity(env, node, mode, align); -} - -void be_coalesce_spillslots(be_irg_t *birg) -{ - be_fec_env_t *env = be_new_frame_entity_coalescer(birg); - - /* collect reloads */ - irg_walk_graph(birg->irg, NULL, collect_spills_walker, env); - - be_assign_entities(env); - - be_free_frame_entity_coalescer(env); -} - -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots) void be_init_spillslots(void) { FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");