X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=f171e66d57f59823f7a894c75b371f63830d23c1;hb=48f0393daa5d5a14ed7e3e32ee2b090759c9371e;hp=a0a8d1dfd7c9f05ccacdf31b439605e583063613;hpb=48f893878b07f6e334389ff52abda5cc2adbf179;p=libfirm diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index a0a8d1dfd..f171e66d5 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -47,10 +47,20 @@ #define DBG_SLOTS 32 #define DBG_TRACE 64 #define DBG_WORKSET 128 -#define DEBUG_LVL 0 //(DBG_START | DBG_DECIDE | DBG_WSETS | DBG_FIX | DBG_SPILL) DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -typedef struct _workset_t workset_t; +/** + * An association between a node and a point in time. + */ +typedef struct _loc_t { + ir_node *irn; /**< A node. */ + unsigned time; /**< A use time (see beuses.h). */ +} loc_t; + +typedef struct _workset_t { + int len; /**< current length */ + loc_t vals[0]; /**< inlined array of the values/distances in this working set */ +} workset_t; typedef struct _belady_env_t { struct obstack ob; @@ -68,17 +78,19 @@ typedef struct _belady_env_t { spill_env_t *senv; /**< see bespill.h */ } belady_env_t; -struct _workset_t { - int len; /**< current length */ - loc_t vals[0]; /**< inlined array of the values/distances in this working set */ -}; +static int loc_compare(const void *a, const void *b) +{ + const loc_t *p = a; + const loc_t *q = b; + return p->time - q->time; +} void workset_print(const workset_t *w) { int i; for(i = 0; i < w->len; ++i) { - ir_printf("%+F %d\n", w->vals[i].irn, w->vals[i].time); + ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time); } } @@ -187,6 +199,7 @@ static INLINE int workset_contains(const workset_t *ws, const ir_node *val) { ++i) #define workset_set_time(ws, i, t) (ws)->vals[i].time=t +#define workset_get_time(ws, i) (ws)->vals[i].time #define workset_set_length(ws, length) (ws)->len = length #define workset_get_length(ws) ((ws)->len) #define workset_get_val(ws, i) ((ws)->vals[i].irn) @@ -216,16 +229,62 @@ static INLINE void *new_block_info(struct obstack *ob) { static INLINE unsigned get_distance(belady_env_t *env, const ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses) { int flags = arch_irn_get_flags(env->arch, def); - unsigned dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses); + unsigned dist; assert(! (flags & arch_irn_flags_ignore)); - // we have to keep nonspillable nodes in the workingset + + /* We have to keep nonspillable nodes in the workingset */ if(flags & arch_irn_flags_dont_spill) return 0; + dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses); + + if(USES_IS_INFINITE(dist)) + dist = USES_INFINITY; + return dist; } +/** + * Fix to remove dead nodes (especially don't spill nodes) from workset. + */ +static void fix_dead_values(workset_t *ws, ir_node *irn) { + int idx; + ir_node *node; + ir_node *block = get_nodes_block(irn); + + DBG((dbg, DBG_DECIDE, "fixing dead values at %+F:\n", irn)); + + workset_foreach(ws, node, idx) { + const ir_edge_t *edge; + int fixme = 1; + + /* skip already fixed nodes */ + if (workset_get_time(ws, idx) == INT_MAX) + continue; + + /* check all users */ + foreach_out_edge(node, edge) { + ir_node *user = get_edge_src_irn(edge); + + if ((get_nodes_block(user) != block) || /* user is in a different block */ + (sched_is_scheduled(user) && sched_comes_after(irn, user)) || /* user is scheduled after irn */ + user == irn) /* irn is the user */ + { /* => don't fix distance */ + fixme = 0; + break; + } + } + + /* all users scheduled prior to current irn in in same block as irn -> fix */ + if (fixme) { + workset_set_time(ws, idx, INT_MAX); + DBG((dbg, DBG_DECIDE, "\tfixing time for %+F to INT_MAX\n", node)); + } + } + +} + /** * Performs the actions necessary to grant the request that: * - new_vals can be held in registers @@ -237,25 +296,29 @@ static INLINE unsigned get_distance(belady_env_t *env, const ir_node *from, unsi */ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) { ir_node *val; - int i, len, max_allowed, demand, iter; - workset_t *ws = env->ws; - ir_node **to_insert = alloca(env->n_regs * sizeof(*to_insert)); + int i, len, max_allowed, demand, iter; + + workset_t *ws = env->ws; + ir_node **to_insert = alloca(env->n_regs * sizeof(*to_insert)); /* - * 1. Identify the number of needed slots and the values to reload - */ + 1. Identify the number of needed slots and the values to reload + */ demand = 0; workset_foreach(new_vals, val, iter) { /* mark value as used */ if (is_usage) pset_insert_ptr(env->used, val); - if (!workset_contains(ws, val)) { + if (! workset_contains(ws, val)) { DBG((dbg, DBG_DECIDE, " insert %+F\n", val)); to_insert[demand++] = val; - if (is_usage) + if (is_usage) { + DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr)); be_add_reload(env->senv, val, env->instr); - } else { + } + } + else { assert(is_usage || "Defined value already in workset?!?"); DBG((dbg, DBG_DECIDE, " skip %+F\n", val)); } @@ -263,9 +326,9 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) { DBG((dbg, DBG_DECIDE, " demand = %d\n", demand)); /* - * 2. Make room for at least 'demand' slots - */ - len = workset_get_length(ws); + 2. Make room for at least 'demand' slots + */ + len = workset_get_length(ws); max_allowed = env->n_regs - demand; DBG((dbg, DBG_DECIDE, " disposing %d values\n", ws->len - max_allowed)); @@ -273,29 +336,44 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) { /* Only make more free room if we do not have enough */ if (len > max_allowed) { /* get current next-use distance */ - for (i=0; ilen; ++i) - workset_set_time(ws, i, get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage)); + for (i = 0; i < ws->len; ++i) { + unsigned dist = get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage); + workset_set_time(ws, i, dist); + } + + /* + FIX for don't spill nodes: + Problem is that get_distance always returns 0 for those nodes even if they are not + needed anymore (all their usages have already been visited). + Even if we change this behavior, get_distance doesn't distinguish between not + used anymore (dead) and live out of block. + Solution: Set distances of all nodes having all their usages in schedule prior to + current instruction to MAX_INT. + */ + fix_dead_values(ws, env->instr); /* sort entries by increasing nextuse-distance*/ workset_sort(ws); - /* Logic for not needed live-ins: If a value is disposed - * before its first usage, remove it from start workset - * We don't do this for phis though - */ - for (i=max_allowed; ilen; ++i) { + /* + Logic for not needed live-ins: If a value is disposed + before its first usage, remove it from start workset + We don't do this for phis though + */ + for (i = max_allowed; i < ws->len; ++i) { ir_node *irn = ws->vals[i].irn; - if(is_Phi(irn)) + if (is_Phi(irn)) continue; - if (!pset_find_ptr(env->used, irn)) { - ir_node *curr_bb = get_nodes_block(env->instr); + if (! pset_find_ptr(env->used, irn)) { + ir_node *curr_bb = get_nodes_block(env->instr); workset_t *ws_start = get_block_info(curr_bb)->ws_start; workset_remove(ws_start, irn); DBG((dbg, DBG_DECIDE, " dispose %+F dumb\n", irn)); - } else { + } + else { DBG((dbg, DBG_DECIDE, " dispose %+F\n", irn)); } } @@ -305,19 +383,19 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) { } /* - * 3. Insert the new values into the workset - */ - for(i = 0; i < demand; ++i) + 3. Insert the new values into the workset + */ + for (i = 0; i < demand; ++i) workset_insert(env, env->ws, to_insert[i]); } static void belady(ir_node *blk, void *env); /* - * Computes set of live-ins for each block with multiple predecessors and - * places copies in the predecessors when phis get spilled + * Computes set of live-ins for each block with multiple predecessors + * and notifies spill algorithm which phis need to be spilled */ -static void place_copy_walker(ir_node *block, void *data) { +static void spill_phi_walker(ir_node *block, void *data) { belady_env_t *env = data; block_info_t *block_info; ir_node *first, *irn; @@ -333,6 +411,9 @@ static void place_copy_walker(ir_node *block, void *data) { /* Collect all values living at start of block */ starters = NEW_ARR_F(loc_t, 0); + /* rebuild schedule time information, because it seems to be broken */ + sched_renumber(block); + DBG((dbg, DBG_START, "Living at start of %+F:\n", block)); first = sched_first(block); sched_foreach(block, irn) { @@ -543,6 +624,7 @@ static void fix_block_borders(ir_node *blk, void *data) { /* irnb is not in memory at the end of pred, so we have to reload it */ DBG((dbg, DBG_FIX, " reload %+F\n", irnb)); + DBG((dbg, DBG_SPILL, "Reload %+F before %+F,%d\n", irnb, blk, i)); be_add_reload_on_edge(env->senv, irnb, blk, i); next_value: @@ -559,16 +641,16 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t belady_env_t env; FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady"); - //firm_dbg_set_mask(dbg, DBG_WSETS); + //firm_dbg_set_mask(dbg, DBG_SPILL); /* init belady env */ obstack_init(&env.ob); env.cenv = chordal_env; env.arch = chordal_env->birg->main_env->arch_env; env.cls = chordal_env->cls; - env.n_regs = arch_count_non_ignore_regs(env.arch, env.cls); + env.n_regs = env.cls->n_regs - be_put_ignore_regs(chordal_env->birg, chordal_env->cls, NULL); env.ws = new_workset(&env, &env.ob); - env.uses = be_begin_uses(chordal_env->irg, chordal_env->lv, chordal_env->birg->main_env->arch_env, env.cls); + env.uses = be_begin_uses(chordal_env->irg, chordal_env->exec_freq, chordal_env->lv); if(spill_env == NULL) { env.senv = be_new_spill_env(chordal_env); } else { @@ -576,12 +658,9 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t } DEBUG_ONLY(be_set_spill_env_dbg_module(env.senv, dbg);) - DBG((dbg, LEVEL_1, "running on register class: %s\n", env.cls->name)); - be_clear_links(chordal_env->irg); /* Decide which phi nodes will be spilled and place copies for them into the graph */ - irg_block_walk_graph(chordal_env->irg, place_copy_walker, NULL, &env); - be_place_copies(env.senv); + irg_block_walk_graph(chordal_env->irg, spill_phi_walker, NULL, &env); /* Fix high register pressure with belady algorithm */ irg_block_walk_graph(chordal_env->irg, NULL, belady, &env); /* belady was block-local, fix the global flow by adding reloads on the edges */ @@ -589,9 +668,6 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t /* Insert spill/reload nodes into the graph and fix usages */ be_insert_spills_reloads(env.senv); - be_remove_dead_nodes_from_schedule(chordal_env->irg); - be_liveness_recompute(chordal_env->lv); - /* clean up */ if(spill_env == NULL) be_delete_spill_env(env.senv);