X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillslots.c;h=062001fbdd24d23d937454988d5dd60e63eb91cc;hb=0fbcef83aa6060534172bb13e71cdadb04428806;hp=629dfd858ecdb87e81b6cae7e7c56ac3eb8a7c70;hpb=4d5c3365a58cba59993045a9e08e686d8ae079a7;p=libfirm diff --git a/ir/be/bespillslots.c b/ir/be/bespillslots.c index 629dfd858..062001fbd 100644 --- a/ir/be/bespillslots.c +++ b/ir/be/bespillslots.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -17,53 +17,47 @@ * PURPOSE. */ -/* - * Author: Matthias Braun - * Date: 26.7.06 - * Copyright: (c) Universitaet Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. +/** + * @file + * @brief Spillslot coalescer. + * @author Matthias Braun + * @date 26.07.2006 + * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include #include "set.h" - +#include "array.h" #include "irgwalk.h" #include "ircons.h" #include "irprintf.h" #include "execfreq.h" #include "unionfind.h" -#include "type.h" #include "irdump_t.h" #include "benode_t.h" #include "besched.h" #include "bespillslots.h" #include "bechordal_t.h" -#include "bejavacoal.h" -#include "benodesets.h" #include "bestatevent.h" #include "bespilloptions.h" #include "bemodule.h" +#include "beintlive_t.h" +#include "beirg_t.h" +#include "bearch_t.h" #define DBG_COALESCING 1 #define DBG_INTERFERENCES 2 -DEBUG_ONLY( -static firm_dbg_module_t *dbg = NULL; -) +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) typedef struct _spill_t { ir_node *spill; - /** mode of the spilled value */ - const ir_mode *mode; - /** alignment for the spilled value */ - int alignment; - /** index into spillslot_unionfind unionfind structure */ - int spillslot; + 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 { @@ -87,7 +81,7 @@ static int cmp_affinity(const void *d1, const void *d2) const affinity_edge_t * const *e1 = d1; const affinity_edge_t * const *e2 = d2; - // sort in descending order + /* sort in descending order */ return (*e1)->affinity < (*e2)->affinity ? 1 : -1; } @@ -95,13 +89,15 @@ static int cmp_spill(const void* d1, const void* d2, size_t size) { const spill_t* s1 = d1; const spill_t* s2 = d2; + (void) size; + return s1->spill != s2->spill; } static spill_t *get_spill(be_fec_env_t *env, ir_node *node) { spill_t spill, *res; - int hash = nodeset_hash(node); + int hash = hash_irn(node); spill.spill = node; res = set_find(env->spills, &spill, sizeof(spill), hash); @@ -109,14 +105,6 @@ static spill_t *get_spill(be_fec_env_t *env, ir_node *node) return res; } -/* - * ____ _ _ _ ____ _ _ _ - * / ___|___ | | | ___ ___| |_ / ___| _ __ (_) | |___ - * | | / _ \| | |/ _ \/ __| __| \___ \| '_ \| | | / __| - * | |__| (_) | | | __/ (__| |_ ___) | |_) | | | \__ \ - * \____\___/|_|_|\___|\___|\__| |____/| .__/|_|_|_|___/ - * |_| - */ static INLINE ir_node *get_memory_edge(const ir_node *node) { @@ -136,17 +124,18 @@ static spill_t *collect_spill(be_fec_env_t *env, ir_node *node, const ir_mode *mode, int align) { spill_t spill, *res; - int hash = nodeset_hash(node); + int hash = hash_irn(node); /* insert into set of spills if not already there */ spill.spill = node; - res = set_find(env->spills, &spill, sizeof(spill), hash); + res = set_find(env->spills, &spill, sizeof(spill), hash); if(res == NULL) { spill.spillslot = set_count(env->spills); - spill.mode = mode; + spill.mode = mode; spill.alignment = align; - res = set_insert(env->spills, &spill, sizeof(spill), hash); + res = set_insert(env->spills, &spill, sizeof(spill), hash); + DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node)); } else { assert(res->mode == mode); assert(res->alignment == align); @@ -160,7 +149,7 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, { int i, arity; spill_t spill, *res; - int hash = nodeset_hash(node); + int hash = hash_irn(node); const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg); assert(is_Phi(node)); @@ -174,11 +163,12 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, } spill.spillslot = set_count(env->spills); - spill.mode = mode; + spill.mode = mode; spill.alignment = align; - res = set_insert(env->spills, &spill, sizeof(spill), hash); + DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node)); + res = set_insert(env->spills, &spill, sizeof(spill), hash); - // collect attached spills and mem-phis + /* collect attached spills and mem-phis */ arity = get_irn_arity(node); for(i = 0; i < arity; ++i) { affinity_edge_t *affinty_edge; @@ -191,11 +181,11 @@ static spill_t *collect_memphi(be_fec_env_t *env, ir_node *node, arg_spill = collect_spill(env, arg, mode, align); } - // add an affinity edge - affinty_edge = obstack_alloc(&env->obst, sizeof(affinty_edge[0])); + /* add an affinity edge */ + affinty_edge = obstack_alloc(&env->obst, sizeof(affinty_edge[0])); affinty_edge->affinity = get_block_execfreq(exec_freq, get_nodes_block(arg)); - affinty_edge->slot1 = res->spillslot; - affinty_edge->slot2 = arg_spill->spillslot; + affinty_edge->slot1 = res->spillslot; + affinty_edge->slot2 = arg_spill->spillslot; ARR_APP1(affinity_edge_t*, env->affinity_edges, affinty_edge); } @@ -210,6 +200,7 @@ void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node, 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); } else { @@ -219,13 +210,7 @@ void be_node_needs_frame_entity(be_fec_env_t *env, ir_node *node, ARR_APP1(ir_node *, env->reloads, node); } -/* - * ____ _ ____ _ _ - * / ___|___ __ _| | ___ ___ ___ ___ / ___|| | ___ | |_ ___ - * | | / _ \ / _` | |/ _ \/ __|/ __/ _ \ \___ \| |/ _ \| __/ __| - * | |__| (_) | (_| | | __/\__ \ (_| __/ ___) | | (_) | |_\__ \ - * \____\___/ \__,_|_|\___||___/\___\___| |____/|_|\___/ \__|___/ - */ + static int merge_interferences(be_fec_env_t *env, bitset_t** interferences, int* spillslot_unionfind, int s1, int s2) @@ -234,9 +219,9 @@ static int merge_interferences(be_fec_env_t *env, bitset_t** interferences, int i; int spillcount; - // merge spillslots and interferences + /* merge spillslots and interferences */ res = uf_union(spillslot_unionfind, s1, s2); - // we assume that we always merge s2 to s1 so swap s1, s2 if necessary + /* we assume that we always merge s2 to s1 so swap s1, s2 if necessary */ if(res != 0) { int t = s1; s1 = s2; @@ -245,7 +230,7 @@ static int merge_interferences(be_fec_env_t *env, bitset_t** interferences, bitset_or(interferences[s1], interferences[s2]); - // update other interferences + /* update other interferences */ spillcount = set_count(env->spills); for(i = 0; i < spillcount; ++i) { bitset_t *intfs = interferences[i]; @@ -256,6 +241,98 @@ 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, + const ir_node *b) +{ + be_lv_t *lv = be_get_birg_liveness(birg); + + int a2b = _value_dominates(a, b); + int b2a = _value_dominates(b, a); + + /* If there is no dominance relation, they do not interfere. */ + if((a2b | b2a) > 0) { + const ir_edge_t *edge; + ir_node *bb; + + /* + * Adjust a and b so, that a dominates b if + * a dominates b or vice versa. + */ + if(b2a) { + const ir_node *t = a; + a = b; + b = t; + } + + bb = get_nodes_block(b); + + /* + * If a is live end in b's block it is + * live at b's definition (a dominates b) + */ + if(be_is_live_end(lv, bb, a)) + return 1; + + /* + * Look at all usages of a. + * If there's one usage of a in the block of b, then + * we check, if this use is dominated by b, if that's true + * a and b interfere. Note that b must strictly dominate the user, + * since if b is the last user of in the block, b and a do not + * interfere. + * Uses of a not in b's block can be disobeyed, because the + * check for a being live at the end of b's block is already + * performed. + */ + foreach_out_edge(a, edge) { + const ir_node *user = get_edge_src_irn(edge); + if(is_Sync(user)) { + const ir_edge_t *edge2; + foreach_out_edge(user, edge2) { + const ir_node *user2 = get_edge_src_irn(edge2); + assert(!is_Sync(user2)); + if(get_nodes_block(user2) == bb && !is_Phi(user2) && + _value_strictly_dominates(b, user2)) + return 1; + } + } else { + if(get_nodes_block(user) == bb && !is_Phi(user) && + _value_strictly_dominates(b, user)) + return 1; + } + } + } + + return 0; +} + +/** + * 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) +{ + 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)) + return 1; + } + return 0; + } else if(is_Sync(b)) { + int i, arity = get_irn_arity(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)) + return 1; + } + return 0; + } + + return my_values_interfere2(birg, a, b); +} + /** * A greedy coalescing algorithm for spillslots: * 1. Sort the list of affinity edges @@ -271,17 +348,16 @@ static void do_greedy_coalescing(be_fec_env_t *env) int affinity_edge_count; bitset_t **interferences; int* spillslot_unionfind; - const be_lv_t *lv = be_get_birg_liveness(env->birg); spillcount = set_count(env->spills); if(spillcount == 0) return; - DBG((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount)); + DB((dbg, DBG_COALESCING, "Coalescing %d spillslots\n", spillcount)); - interferences = alloca(spillcount * sizeof(interferences[0])); + interferences = alloca(spillcount * sizeof(interferences[0])); spillslot_unionfind = alloca(spillcount * sizeof(spillslot_unionfind[0])); - spilllist = alloca(spillcount * sizeof(spilllist[0])); + spilllist = alloca(spillcount * sizeof(spilllist[0])); uf_init(spillslot_unionfind, 0, spillcount); @@ -289,7 +365,8 @@ 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) { + for(spill = set_first(env->spills), i = 0; spill != NULL; + spill = set_next(env->spills), ++i) { assert(spill->spillslot < spillcount); spilllist[spill->spillslot] = spill; } @@ -298,50 +375,55 @@ static void do_greedy_coalescing(be_fec_env_t *env) interferences[i] = bitset_alloca(spillcount); } - // construct interferences - for(i = 0; i < spillcount; ++i) { + /* construct interferences */ + for (i = 0; i < spillcount; ++i) { ir_node *spill1 = spilllist[i]->spill; - if(is_NoMem(spill1)) + + if (is_NoMem(spill1)) continue; for(i2 = i+1; i2 < spillcount; ++i2) { ir_node *spill2 = spilllist[i2]->spill; - if(is_NoMem(spill2)) + + if (is_NoMem(spill2)) continue; - if(values_interfere(lv, spill1, spill2)) { - DBG((dbg, DBG_INTERFERENCES, "Slot %d and %d interfere\n", - i, i2)); + if (my_values_interfere(env->birg, spill1, spill2)) { + DB((dbg, DBG_INTERFERENCES, + "Slot %d and %d interfere\n", i, i2)); + bitset_set(interferences[i], i2); bitset_set(interferences[i2], i); } } } - // sort affinity edges + /* sort affinity edges */ affinity_edge_count = ARR_LEN(env->affinity_edges); - qsort(env->affinity_edges, affinity_edge_count, sizeof(env->affinity_edges[0]), cmp_affinity); + qsort(env->affinity_edges, affinity_edge_count, + sizeof(env->affinity_edges[0]), cmp_affinity); - //dump_interference_graph(env, interferences, "before"); + /*dump_interference_graph(env, interferences, "before"); */ - // try to merge affine nodes + /* try to merge affine nodes */ for(i = 0; i < affinity_edge_count; ++i) { const affinity_edge_t *edge = env->affinity_edges[i]; int s1 = uf_find(spillslot_unionfind, edge->slot1); int s2 = uf_find(spillslot_unionfind, edge->slot2); /* test if values interfere */ - if(bitset_is_set(interferences[s1], s2)) { + if (bitset_is_set(interferences[s1], s2)) { assert(bitset_is_set(interferences[s2], s1)); continue; } - DBG((dbg, DBG_COALESCING, "Merging %d and %d because of affinity edge\n", s1, s2)); + DB((dbg, DBG_COALESCING, + "Merging %d and %d because of affinity edge\n", s1, s2)); merge_interferences(env, interferences, spillslot_unionfind, s1, s2); } - // try to merge as much remaining spillslots as possible + /* try to merge as much remaining spillslots as possible */ for(i = 0; i < spillcount; ++i) { int s1 = uf_find(spillslot_unionfind, i); if(s1 != i) @@ -361,34 +443,28 @@ static void do_greedy_coalescing(be_fec_env_t *env) continue; } - DBG((dbg, DBG_COALESCING, "Merging %d and %d because it is possible\n", s1, s2)); + DB((dbg, DBG_COALESCING, + "Merging %d and %d because it is possible\n", s1, s2)); if(merge_interferences(env, interferences, spillslot_unionfind, s1, s2) != 0) { - // we can break the loop here, because s2 is the new supernode now - // and we'll test s2 again later anyway + /* we can break the loop here, because s2 is the new supernode + * now and we'll test s2 again later anyway */ break; } } } - // assign spillslots to spills + /* assign spillslots to spills */ for(i = 0; i < spillcount; ++i) { spill_t *spill = spilllist[i]; spill->spillslot = uf_find(spillslot_unionfind, i); } - //dump_interference_graph(env, interferences, "after"); + /*dump_interference_graph(env, interferences, "after");*/ } -/* - * _ _ _____ _ _ _ _ - * / \ ___ ___(_) __ _ _ __ | ____|_ __ | |_(_) |_(_) ___ ___ - * / _ \ / __/ __| |/ _` | '_ \ | _| | '_ \| __| | __| |/ _ \/ __| - * / ___ \\__ \__ \ | (_| | | | | | |___| | | | |_| | |_| | __/\__ \ - * /_/ \_\___/___/_|\__, |_| |_| |_____|_| |_|\__|_|\__|_|\___||___/ - * |___/ - */ + typedef struct _spill_slot_t { int size; @@ -414,6 +490,8 @@ static int cmp_memperm(const void* d1, const void* d2, size_t size) { const memperm_t* e1 = d1; const memperm_t* e2 = d2; + (void) size; + return e1->block != e2->block; } @@ -423,7 +501,7 @@ static memperm_t *get_memperm(be_fec_env_t *env, ir_node *block) int hash; entry.block = block; - hash = nodeset_hash(block); + hash = hash_irn(block); res = set_find(env->memperms, &entry, sizeof(entry), hash); @@ -440,9 +518,12 @@ 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); - ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, 0); + /* 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... + /* adjust size of the entity type... */ ir_type *enttype = get_entity_type(res); set_type_size_bytes(enttype, slot->size); @@ -470,13 +551,36 @@ static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize) } } + +static void assign_spill_entity(ir_node *node, ir_entity *entity) +{ + if(is_NoMem(node)) + return; + if(is_Sync(node)) { + int i, arity; + + arity = get_irn_arity(node); + for(i = 0; i < arity; ++i) { + ir_node *in = get_irn_n(node, i); + assert(!is_Phi(in)); + + assign_spill_entity(in, entity); + } + return; + } + + /* beware: we might have Stores with Memory Proj's, ia32 fisttp for instance */ + node = skip_Proj(node); + assert(arch_get_frame_entity(node) == NULL); + arch_set_frame_entity(node, entity); +} + /** * Create stack entities for the spillslots and assign them to the spill and * reload nodes. */ static void assign_spillslots(be_fec_env_t *env) { - const arch_env_t *arch_env = env->arch_env; int i; int spillcount; spill_t *spill; @@ -487,8 +591,10 @@ static void assign_spillslots(be_fec_env_t *env) memset(spillslots, 0, spillcount * sizeof(spillslots[0])); - // construct spillslots - for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) { + /* construct spillslots */ + for(spill = set_first(env->spills); spill != NULL; + spill = set_next(env->spills)) { + int slotid = spill->spillslot; const ir_mode *mode = spill->mode; spill_slot_t *slot = & (spillslots[slotid]); @@ -503,10 +609,12 @@ static void assign_spillslots(be_fec_env_t *env) } } - for(spill = set_first(env->spills); spill != NULL; spill = set_next(env->spills)) { + for(spill = set_first(env->spills); spill != NULL; + spill = set_next(env->spills)) { + + ir_node *node = spill->spill; + int slotid = spill->spillslot; spill_slot_t *slot; - ir_node *node = spill->spill; - int slotid = spill->spillslot; slot = &spillslots[slotid]; if(slot->entity == NULL) { @@ -517,7 +625,7 @@ static void assign_spillslots(be_fec_env_t *env) int i, arity; ir_node *block = get_nodes_block(node); - // should be a PhiM + /* should be a PhiM */ assert(is_Phi(node)); for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { @@ -551,20 +659,19 @@ static void assign_spillslots(be_fec_env_t *env) } } } else { - if(!is_NoMem(node)) - arch_set_frame_entity(arch_env, node, slot->entity); + assign_spill_entity(node, slot->entity); } } for(i = 0; i < ARR_LEN(env->reloads); ++i) { - ir_node* reload = env->reloads[i]; - ir_node* spillnode = get_memory_edge(reload); - spill_t *spill = get_spill(env, spillnode); - const spill_slot_t *slot = & spillslots[spill->spillslot]; + ir_node *reload = env->reloads[i]; + ir_node *spillnode = get_memory_edge(reload); + spill_t *spill = get_spill(env, spillnode); + const spill_slot_t *slot = & spillslots[spill->spillslot]; assert(slot->entity != NULL); - arch_set_frame_entity(arch_env, reload, slot->entity); + arch_set_frame_entity(reload, slot->entity); } } @@ -614,10 +721,10 @@ static void create_memperms(be_fec_env_t *env) mempermnode = be_new_MemPerm(arch_env, irg, memperm->block, memperm->entrycount, nodes); - // insert node into schedule + /* insert node into schedule */ blockend = get_end_of_block_insertion_point(memperm->block); sched_add_before(blockend, mempermnode); - be_stat_ev("mem_perm", memperm->entrycount); + stat_ev_dbl("mem_perm", memperm->entrycount); i = 0; for(entry = memperm->entries; entry != NULL; entry = entry->next, ++i) { @@ -628,7 +735,6 @@ static void create_memperms(be_fec_env_t *env) 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); - sched_add_before(blockend, proj); set_irn_n(entry->node, entry->pos, proj); } @@ -658,18 +764,17 @@ static int count_spillslots(const be_fec_env_t *env) be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg) { 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 = xmalloc(sizeof(env[0])); - - be_assure_liveness(birg); + be_liveness_assure_chk(be_assure_liveness(birg)); obstack_init(&env->obst); - env->arch_env = arch_env; - env->birg = birg; - env->spills = new_set(cmp_spill, 10); - env->reloads = NEW_ARR_F(ir_node*, 0); + env->arch_env = arch_env; + env->birg = birg; + 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); - env->memperms = new_set(cmp_memperm, 10); + env->memperms = new_set(cmp_memperm, 10); return env; } @@ -687,19 +792,13 @@ void be_free_frame_entity_coalescer(be_fec_env_t *env) void be_assign_entities(be_fec_env_t *env) { - if(be_stat_ev_is_active()) { - int count = set_count(env->spills); - be_stat_ev("spillslots", count); - } + stat_ev_dbl("spillslots", set_count(env->spills)); if(be_coalesce_spill_slots) { do_greedy_coalescing(env); } - if(be_stat_ev_is_active()) { - int count = count_spillslots(env); - be_stat_ev("spillslots_after_coalescing", count); - } + stat_ev_dbl("spillslots_after_coalescing", count_spillslots(env)); assign_spillslots(env); @@ -713,7 +812,6 @@ void be_assign_entities(be_fec_env_t *env) static void collect_spills_walker(ir_node *node, void *data) { be_fec_env_t *env = data; - const arch_env_t *arch_env = env->arch_env; const ir_mode *mode; const arch_register_class_t *cls; int align; @@ -722,12 +820,12 @@ static void collect_spills_walker(ir_node *node, void *data) if (is_Proj(node)) return; - if (!arch_irn_class_is(arch_env, node, reload)) + if (!arch_irn_class_is(node, reload)) return; - mode = get_irn_mode(node); - cls = arch_get_irn_reg_class(arch_env, node, -1); - align = arch_isa_get_reg_class_alignment(arch_env_get_isa(arch_env), cls); + mode = get_irn_mode(node); + cls = arch_get_irn_reg_class(node, -1); + align = arch_env_get_reg_class_alignment(env->arch_env, cls); be_node_needs_frame_entity(env, node, mode, align); }