X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillslots.c;h=fe4df32f4a1548b953a5f942430582afc6d0371d;hb=5474a1c188c9d59eea2c915515980cd9cbab58d8;hp=359dc7d5668b68460513b81f9bf6998a7a2ece9a;hpb=65a52a96e8ab7ed601d7f98c516d37c46b674b4a;p=libfirm diff --git a/ir/be/bespillslots.c b/ir/be/bespillslots.c index 359dc7d56..fe4df32f4 100644 --- a/ir/be/bespillslots.c +++ b/ir/be/bespillslots.c @@ -22,7 +22,6 @@ * @brief Spillslot coalescer. * @author Matthias Braun * @date 26.07.2006 - * @version $Id$ */ #include "config.h" @@ -48,39 +47,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 { +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; int slot2; } affinity_edge_t; -struct _be_fec_env_t { - struct obstack obst; - const arch_env_t *arch_env; - ir_graph *irg; - 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; @@ -88,8 +89,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; @@ -101,7 +102,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; } @@ -129,13 +130,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); @@ -156,7 +157,7 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, 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); @@ -167,7 +168,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); @@ -197,15 +198,14 @@ void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node, const ir_mode *mode, int align) { ir_node *spillnode = get_memory_edge(node); - spill_t *spill; assert(spillnode != NULL); /* walk upwards and collect all phis and spills on this way */ if (is_Phi(spillnode)) { - spill = collect_memphi(env, spillnode, mode, align); + collect_memphi(env, spillnode, mode, align); } else { - spill = collect_spill(env, spillnode, mode, align); + collect_spill(env, spillnode, mode, align); } ARR_APP1(ir_node *, env->reloads, node); @@ -367,12 +367,13 @@ static void do_greedy_coalescing(be_fec_env_t *env) DEBUG_ONLY( 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) { @@ -471,21 +472,21 @@ static void do_greedy_coalescing(be_fec_env_t *env) -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; @@ -493,8 +494,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; @@ -508,12 +509,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; @@ -521,17 +522,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 = env->irg; - 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); - - /* adjust size of the entity type... */ - ir_type *enttype = get_entity_type(res); - set_type_size_bytes(enttype, slot->size); - + 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); slot->entity = res; return res; @@ -556,8 +550,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; @@ -569,7 +563,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; } @@ -578,7 +572,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); } /** @@ -590,12 +584,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]); @@ -610,9 +602,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; @@ -627,7 +617,7 @@ static void assign_spillslots(be_fec_env_t *env) ir_node *block = get_nodes_block(node); /* should be a PhiM */ - assert(is_Phi(node)); + assert(get_irn_mode(node) == mode_M); for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *arg = get_irn_n(node, i); @@ -660,7 +650,7 @@ static void assign_spillslots(be_fec_env_t *env) } } } else { - assign_spill_entity(node, slot->entity); + assign_spill_entity(env, node, slot->entity); } } @@ -672,7 +662,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); } } @@ -701,11 +691,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 = env->irg; - memperm_t *memperm; + 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; @@ -719,8 +707,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); @@ -734,8 +722,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); } @@ -750,8 +737,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++; @@ -764,13 +750,11 @@ static int count_spillslots(const be_fec_env_t *env) be_fec_env_t *be_new_frame_entity_coalescer(ir_graph *irg) { - const arch_env_t *arch_env = be_get_irg_arch_env(irg); - 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(irg)); + be_assure_live_chk(irg); obstack_init(&env->obst); - env->arch_env = arch_env; env->irg = irg; env->spills = new_set(cmp_spill, 10); env->reloads = NEW_ARR_F(ir_node*, 0); @@ -791,8 +775,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) { @@ -806,40 +795,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; - - if (! (arch_irn_classify(node) & arch_irn_class_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(ir_graph *irg) -{ - be_fec_env_t *env = be_new_frame_entity_coalescer(irg); - - /* collect reloads */ - irg_walk_graph(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");