X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=f171e66d57f59823f7a894c75b371f63830d23c1;hb=48f0393daa5d5a14ed7e3e32ee2b090759c9371e;hp=cd9d4b0fd27b4a8d199412531adb750bd251d3d1;hpb=e9137de01e1ed5e7a8baee8d23a59e82ad634af5;p=libfirm diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index cd9d4b0fd..f171e66d5 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -47,13 +47,24 @@ #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; + const be_chordal_env_t *cenv; const arch_env_t *arch; const arch_register_class_t *cls; int n_regs; /** number of regs in this reg-class */ @@ -62,45 +73,44 @@ typedef struct _belady_env_t { be_uses_t *uses; /**< env for the next-use magic */ ir_node *instr; /**< current instruction */ unsigned instr_nr; /**< current instruction number (relative to block start) */ - pset *used; /**< holds the values used (so far) in the current BB */ - ir_node **copies; /**< holds all copies placed due to phi-spilling */ + pset *used; spill_env_t *senv; /**< see bespill.h */ } belady_env_t; -struct _workset_t { - belady_env_t *bel; - int len; /**< current length */ - loc_t vals[1]; /**< 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); } } /** * Alloc a new workset on obstack @p ob with maximum size @p max */ -static INLINE workset_t *new_workset(struct obstack *ob, belady_env_t *bel) { +static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) { workset_t *res; - size_t size = sizeof(*res) + (bel->n_regs-1)*sizeof(res->vals[0]); + size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]); res = obstack_alloc(ob, size); memset(res, 0, size); - res->bel = bel; return res; } /** * Alloc a new instance on obstack and make it equal to @param ws */ -static INLINE workset_t *workset_clone(struct obstack *ob, workset_t *ws) { +static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) { workset_t *res; - size_t size = sizeof(*res) + (ws->bel->n_regs-1)*sizeof(res->vals[0]); + size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]); res = obstack_alloc(ob, size); memcpy(res, ws, size); return res; @@ -108,10 +118,10 @@ static INLINE workset_t *workset_clone(struct obstack *ob, workset_t *ws) { /** * Do NOT alloc anything. Make @param tgt equal to @param src. - * returns @param tgt for convinience + * returns @param tgt for convenience */ -static INLINE workset_t *workset_copy(workset_t *tgt, workset_t *src) { - size_t size = sizeof(*src) + (src->bel->n_regs-1)*sizeof(src->vals[0]); +static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) { + size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]); memcpy(tgt, src, size); return tgt; } @@ -121,17 +131,19 @@ static INLINE workset_t *workset_copy(workset_t *tgt, workset_t *src) { * @param count locations given at memory @param locs. * Set the length of @param ws to count. */ -#define workset_bulk_fill(ws, count, locs) memcpy(&(ws)->vals[0], locs, ((ws)->len=count)*sizeof(locs[0])); - +static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) { + workset->len = count; + memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0])); +} /** * Inserts the value @p val into the workset, iff it is not * already contained. The workset must not be full. */ -static INLINE void workset_insert(workset_t *ws, ir_node *val) { +static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) { int i; /* check for current regclass */ - if (arch_get_irn_reg_class(ws->bel->arch, val, -1) != ws->bel->cls) { + if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) { DBG((dbg, DBG_WORKSET, "Dropped %+F\n", val)); return; } @@ -142,66 +154,37 @@ static INLINE void workset_insert(workset_t *ws, ir_node *val) { return; /* insert val */ - assert(ws->len < ws->bel->n_regs && "Workset already full!"); + assert(ws->len < env->n_regs && "Workset already full!"); ws->vals[ws->len++].irn = val; } -/** - * Inserts all values in array @p vals of length @p cnt - * into the workset. There must be enough space for the - * entries. - */ -static INLINE void workset_bulk_insert(workset_t *ws, int cnt, ir_node **vals) { - int i, o; - - for(o=0; obel->arch, val, -1) != ws->bel->cls) { - DBG((dbg, DBG_TRACE, "Wrong reg class\n")); - goto no_insert; - } - - /* check if val is already contained */ - for(i=0; ilen; ++i) - if (ws->vals[i].irn == val) { - DBG((dbg, DBG_TRACE, "Already contained\n")); - goto no_insert; - } - - /* insert val */ - assert(ws->len < ws->bel->n_regs && "Workset does not have enough room!"); - ws->vals[ws->len++].irn = val; - DBG((dbg, DBG_TRACE, "Inserted\n")); - -no_insert: - /*epsilon statement :)*/; - } -} - /** * Removes all entries from this workset */ -#define workset_clear(ws) (ws)->len = 0; +static INLINE void workset_clear(workset_t *ws) { + ws->len = 0; +} /** * Removes the value @p val from the workset if present. */ static INLINE void workset_remove(workset_t *ws, ir_node *val) { int i; - for(i=0; ilen; ++i) + for(i=0; ilen; ++i) { if (ws->vals[i].irn == val) { ws->vals[i] = ws->vals[--ws->len]; return; } + } } static INLINE int workset_contains(const workset_t *ws, const ir_node *val) { int i; - for(i=0; ilen; ++i) + for(i=0; ilen; ++i) { if (ws->vals[i].irn == val) return 1; + } + return 0; } @@ -216,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) @@ -223,6 +207,7 @@ static INLINE int workset_contains(const workset_t *ws, const ir_node *val) { typedef struct _block_info_t { workset_t *ws_start, *ws_end; + int processed; } block_info_t; @@ -230,6 +215,7 @@ static INLINE void *new_block_info(struct obstack *ob) { block_info_t *res = obstack_alloc(ob, sizeof(*res)); res->ws_start = NULL; res->ws_end = NULL; + res->processed = 0; return res; } @@ -237,30 +223,66 @@ static INLINE void *new_block_info(struct obstack *ob) { #define get_block_info(blk) ((block_info_t *)get_irn_link(blk)) #define set_block_info(blk, info) set_irn_link(blk, info) -static int is_mem_phi(const ir_node *irn, void *data) { - workset_t *sws; - ir_node *blk = get_nodes_block(irn); +/** + * @return The distance to the next use or 0 if irn has dont_spill flag set + */ +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; + + assert(! (flags & arch_irn_flags_ignore)); + + /* 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); - DBG((dbg, DBG_SPILL, "Is %+F a mem-phi?\n", irn)); - sws = get_block_info(blk)->ws_start; - DBG((dbg, DBG_SPILL, " %d\n", !workset_contains(sws, irn))); - return !workset_contains(sws, irn); + if(USES_IS_INFINITE(dist)) + dist = USES_INFINITY; + + return dist; } /** - * @return The distance to the next use - * Or 0 if irn is an ignore node + * 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); -static INLINE unsigned get_distance(belady_env_t *bel, const ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses) -{ - arch_irn_flags_t fl = arch_irn_get_flags(bel->arch, def); - unsigned dist = be_get_next_use(bel->uses, from, from_step, def, skip_from_uses); + DBG((dbg, DBG_DECIDE, "fixing dead values at %+F:\n", irn)); - if(!USES_IS_INIFINITE(dist) && (fl & (arch_irn_flags_ignore | arch_irn_flags_dont_spill)) != 0) - return 0; + 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)); + } + } - return dist; } /** @@ -272,61 +294,86 @@ static INLINE unsigned get_distance(belady_env_t *bel, const ir_node *from, unsi * @p is_usage indicates that the values in new_vals are used (not defined) * In this case reloads must be performed */ -static void displace(belady_env_t *bel, workset_t *new_vals, int is_usage) { +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 = bel->ws; - ir_node **to_insert = alloca(bel->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(bel->used, val); + 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) - be_add_reload(bel->senv, val, bel->instr); - } else { + if (is_usage) { + DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr)); + be_add_reload(env->senv, val, env->instr); + } + } + else { + assert(is_usage || "Defined value already in workset?!?"); DBG((dbg, DBG_DECIDE, " skip %+F\n", val)); } } DBG((dbg, DBG_DECIDE, " demand = %d\n", demand)); /* - * 2. Make room for at least 'demand' slots - */ - len = workset_get_length(ws); - max_allowed = bel->n_regs - demand; + 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)); /* 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(bel, bel->instr, bel->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 */ - 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 (!pset_find_ptr(bel->used, irn)) { - ir_node *curr_bb = get_nodes_block(bel->instr); + if (is_Phi(irn)) + continue; + + 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)); } } @@ -336,52 +383,80 @@ static void displace(belady_env_t *bel, workset_t *new_vals, int is_usage) { } /* - * 3. Insert the new values into the workset - */ - workset_bulk_insert(bel->ws, demand, to_insert); + 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); -/** - * Inserts a spill of a value at the earliest possible location in a block. - * That is after the last use of the value or at the beginning of the block if - * there is no use +/* + * Computes set of live-ins for each block with multiple predecessors + * and notifies spill algorithm which phis need to be spilled */ -static ir_node *insert_copy(belady_env_t *env, ir_node *block, ir_node *value) { - ir_node* node; - ir_graph *irg = get_irn_irg(block); - ir_node *copy = be_new_Copy(env->cls, irg, block, value); +static void spill_phi_walker(ir_node *block, void *data) { + belady_env_t *env = data; + block_info_t *block_info; + ir_node *first, *irn; + loc_t loc, *starters; + int i, len, ws_count; - ARR_APP1(ir_node*, env->copies, copy); + if(get_Block_n_cfgpreds(block) == 1 && get_irg_start_block(get_irn_irg(block)) != block) + return; - // walk schedule backwards until we find a usage, or until we have reached the first phi - // TODO can we do this faster somehow? This makes insert_copy O(n) in block_size... - sched_foreach_reverse(block, node) { - int i, arity; + block_info = new_block_info(&env->ob); + set_block_info(block, block_info); - if(is_Phi(node)) { - sched_add_after(node, copy); - goto placed; - } - if(value == node) { - sched_add_after(node, copy); - goto placed; - } - for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { - ir_node *arg = get_irn_n(node, i); - if(arg == value) { - sched_add_after(node, copy); - goto placed; - } - } + /* 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) { + if(!is_Phi(irn)) + break; + if(!arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)) + continue; + + loc.irn = irn; + loc.time = get_distance(env, first, 0, irn, 0); + ARR_APP1(loc_t, starters, loc); + DBG((dbg, DBG_START, " %+F:\n", irn)); + } + + be_lv_foreach(env->cenv->lv, block, be_lv_state_in, i) { + ir_node *irn = be_lv_get_irn(env->cenv->lv, block, i); + if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)) + continue; + + loc.irn = irn; + loc.time = get_distance(env, first, 0, irn, 0); + ARR_APP1(loc_t, starters, loc); + DBG((dbg, DBG_START, " %+F:\n", irn)); } - // we didn't find a use or a phi yet, so place the copy at the beginning of the block - sched_add_before(sched_first(block), copy); -placed: + // Sort start values by first use + qsort(starters, ARR_LEN(starters), sizeof(starters[0]), loc_compare); + + /* Copy the best ones from starters to start workset */ + ws_count = MIN(ARR_LEN(starters), env->n_regs); + block_info->ws_start = new_workset(env, &env->ob); + workset_bulk_fill(block_info->ws_start, ws_count, starters); + + /* The phis of this block which are not in the start set have to be spilled later. */ + for (i = ws_count, len = ARR_LEN(starters); i < len; ++i) { + irn = starters[i].irn; + if (!is_Phi(irn) || get_nodes_block(irn) != block) + continue; + + be_spill_phi(env->senv, irn); + } - return copy; + DEL_ARR_F(starters); } /** @@ -391,106 +466,34 @@ placed: * their args to break interference and make it possible to spill them to the * same spill slot. */ -static block_info_t *compute_block_start_info(ir_node *blk, void *data) { - belady_env_t *env = data; - ir_node *irn, *first; - irn_live_t *li; - int i, count, ws_count; - loc_t loc, *starters; - ir_graph *irg = get_irn_irg(blk); - struct obstack ob; - block_info_t *res = get_block_info(blk); +static block_info_t *compute_block_start_info(belady_env_t *env, ir_node *block) { + ir_node *pred_block; + block_info_t *res, *pred_info; /* Have we seen this block before? */ + res = get_block_info(block); if (res) return res; /* Create the block info for this block. */ res = new_block_info(&env->ob); - set_block_info(blk, res); - - - /* Get all values living at the block start sorted by next use*/ - obstack_init(&ob); - - DBG((dbg, DBG_START, "Living at start of %+F:\n", blk)); - first = sched_first(blk); - count = 0; - sched_foreach(blk, irn) { - if (is_Phi(irn) && arch_get_irn_reg_class(env->arch, irn, -1) == env->cls) { - loc.irn = irn; - loc.time = get_distance(env, first, 0, irn, 0); - obstack_grow(&ob, &loc, sizeof(loc)); - DBG((dbg, DBG_START, " %+F:\n", irn)); - count++; - } else - break; - } - - live_foreach(blk, li) { - if (live_is_in(li) && arch_get_irn_reg_class(env->arch, li->irn, -1) == env->cls) { - loc.irn = (ir_node *)li->irn; - loc.time = get_distance(env, first, 0, li->irn, 0); - obstack_grow(&ob, &loc, sizeof(loc)); - DBG((dbg, DBG_START, " %+F:\n", li->irn)); - count++; - } - } + set_block_info(block, res); - starters = obstack_finish(&ob); - qsort(starters, count, sizeof(starters[0]), loc_compare); + /* Use endset of predecessor block as startset */ + assert(get_Block_n_cfgpreds(block) == 1 && block != get_irg_start_block(get_irn_irg(block))); + pred_block = get_Block_cfgpred_block(block, 0); + pred_info = get_block_info(pred_block); - - /* If we have only one predecessor, we want the start_set of blk to be the end_set of pred */ - if (get_Block_n_cfgpreds(blk) == 1 && blk != get_irg_start_block(get_irn_irg(blk))) { - ir_node *pred_blk = get_Block_cfgpred_block(blk, 0); - block_info_t *pred_info = get_block_info(pred_blk); - - /* if pred block has not been processed yet, do it now */ - if (! pred_info) { - belady(pred_blk, env); - pred_info = get_block_info(pred_blk); - } - - /* now we have an end_set of pred */ - assert(pred_info->ws_end && "The recursive call (above) is supposed to compute an end_set"); - res->ws_start = workset_clone(&env->ob, pred_info->ws_end); - - } else - - /* Else we want the start_set to be the values used 'the closest' */ - { - /* Copy the best ones from starters to start workset */ - ws_count = MIN(count, env->n_regs); - res->ws_start = new_workset(&env->ob, env); - workset_bulk_fill(res->ws_start, ws_count, starters); + /* if pred block has not been processed yet, do it now */ + if (pred_info == NULL || pred_info->processed == 0) { + belady(pred_block, env); + pred_info = get_block_info(pred_block); } + /* now we have an end_set of pred */ + assert(pred_info->ws_end && "The recursive call (above) is supposed to compute an end_set"); + res->ws_start = workset_clone(env, &env->ob, pred_info->ws_end); - - /* The phis of this block which are not in the start set have to be spilled later. - * Therefore we add temporary copies in the pred_blocks so the spills can spill - * into the same spill slot. - * After spilling these copies get deleted. */ - for (i=workset_get_length(res->ws_start); iprocessed) return; /* get the starting workset for this block */ - blk_info = compute_block_start_info(blk, bel); - DBG((dbg, DBG_DECIDE, "\n")); - DBG((dbg, DBG_DECIDE, "Decide for %+F\n", blk)); + DBG((dbg, DBG_DECIDE, "Decide for %+F\n", block)); - workset_copy(bel->ws, blk_info->ws_start); - DBG((dbg, DBG_WSETS, "Start workset for %+F:\n", blk)); - workset_foreach(bel->ws, irn, iter) + workset_copy(env, env->ws, block_info->ws_start); + DBG((dbg, DBG_WSETS, "Start workset for %+F:\n", block)); + workset_foreach(env->ws, irn, iter) DBG((dbg, DBG_WSETS, " %+F\n", irn)); /* process the block from start to end */ DBG((dbg, DBG_WSETS, "Processing...\n")); - bel->used = pset_new_ptr(32); - bel->instr_nr = 0; - new_vals = new_workset(&bel->ob, bel); - sched_foreach(blk, irn) { - assert(workset_get_length(bel->ws) <= bel->n_regs && "Too much values in workset!"); - + env->used = pset_new_ptr_default(); + env->instr_nr = 0; + new_vals = new_workset(env, &env->ob); + sched_foreach(block, irn) { + int i, arity; + assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!"); /* projs are handled with the tuple value. * Phis are no real instr (see insert_starters()) @@ -541,32 +547,35 @@ static void belady(ir_node *blk, void *env) { DBG((dbg, DBG_DECIDE, " ...%+F\n", irn)); /* set instruction in the workset */ - bel->instr = irn; + env->instr = irn; /* allocate all values _used_ by this instruction */ workset_clear(new_vals); - workset_bulk_insert(new_vals, get_irn_arity(irn)+1, get_irn_in(irn)); - displace(bel, new_vals, 1); + for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) { + workset_insert(env, new_vals, get_irn_n(irn, i)); + } + displace(env, new_vals, 1); /* allocate all values _defined_ by this instruction */ workset_clear(new_vals); if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */ ir_node *proj; for(proj=sched_next(irn); is_Proj(proj); proj=sched_next(proj)) - workset_insert(new_vals, proj); + workset_insert(env, new_vals, proj); } else { - workset_insert(new_vals, irn); + workset_insert(env, new_vals, irn); } - displace(bel, new_vals, 0); + displace(env, new_vals, 0); - bel->instr_nr++; + env->instr_nr++; } - del_pset(bel->used); + del_pset(env->used); /* Remember end-workset for this block */ - blk_info->ws_end = workset_clone(&bel->ob, bel->ws); - DBG((dbg, DBG_WSETS, "End workset for %+F:\n", blk)); - workset_foreach(blk_info->ws_end, irn, iter) + block_info->ws_end = workset_clone(env, &env->ob, env->ws); + block_info->processed = 1; + DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block)); + workset_foreach(block_info->ws_end, irn, iter) DBG((dbg, DBG_WSETS, " %+F\n", irn)); } @@ -575,9 +584,9 @@ static void belady(ir_node *blk, void *env) { * about the set of live-ins. Thus we must adapt the * live-outs to the live-ins at each block-border. */ -static void fix_block_borders(ir_node *blk, void *env) { +static void fix_block_borders(ir_node *blk, void *data) { + belady_env_t *env = data; workset_t *wsb; - belady_env_t *bel = env; int i, max, iter, iter2; DBG((dbg, DBG_FIX, "\n")); @@ -595,9 +604,14 @@ static void fix_block_borders(ir_node *blk, void *env) { workset_foreach(wsb, irnb, iter) { /* if irnb is a phi of the current block we reload * the corresponding argument, else irnb itself */ - if(is_Phi(irnb) && blk == get_nodes_block(irnb)) + if(is_Phi(irnb) && blk == get_nodes_block(irnb)) { irnb = get_irn_n(irnb, i); + // we might have unknowns as argument for the phi + if(!arch_irn_consider_in_reg_alloc(env->arch, env->cls, irnb)) + continue; + } + /* Unknowns are available everywhere */ if(get_irn_opcode(irnb) == iro_Unknown) continue; @@ -608,9 +622,10 @@ static void fix_block_borders(ir_node *blk, void *env) { goto next_value; } - /* irnb is in memory at the end of pred, so we have to reload it */ + /* irnb is not in memory at the end of pred, so we have to reload it */ DBG((dbg, DBG_FIX, " reload %+F\n", irnb)); - be_add_reload_on_edge(bel->senv, irnb, blk, i); + 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: /*epsilon statement :)*/; @@ -618,69 +633,44 @@ next_value: } } -/** - * Removes all copies introduced for phi-spills - */ -static void remove_copies(belady_env_t *env) { - int i; - - for(i = 0; i < ARR_LEN(env->copies); ++i) { - ir_node *node = env->copies[i]; - ir_node *src; - const ir_edge_t *edge, *ne; - - assert(be_is_Copy(node)); - - src = be_get_Copy_op(node); - foreach_out_edge_safe(node, edge, ne) { - ir_node *user = get_edge_src_irn(edge); - int user_pos = get_edge_src_pos(edge); - - set_irn_n(user, user_pos, src); - } - } -} - void be_spill_belady(const be_chordal_env_t *chordal_env) { be_spill_belady_spill_env(chordal_env, NULL); } void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t *spill_env) { - belady_env_t bel; + belady_env_t env; FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady"); + //firm_dbg_set_mask(dbg, DBG_SPILL); /* init belady env */ - obstack_init(&bel.ob); - bel.arch = chordal_env->birg->main_env->arch_env; - bel.cls = chordal_env->cls; - bel.n_regs = arch_register_class_n_regs(bel.cls); - bel.ws = new_workset(&bel.ob, &bel); - bel.uses = be_begin_uses(chordal_env->irg, chordal_env->birg->main_env->arch_env, bel.cls); + 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 = 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->exec_freq, chordal_env->lv); if(spill_env == NULL) { - bel.senv = be_new_spill_env(chordal_env, is_mem_phi, NULL); + env.senv = be_new_spill_env(chordal_env); } else { - bel.senv = spill_env; - be_set_is_spilled_phi(bel.senv, is_mem_phi, NULL); + env.senv = spill_env; } - DEBUG_ONLY(be_set_spill_env_dbg_module(bel.senv, dbg);) - bel.copies = NEW_ARR_F(ir_node*, 0); - - DBG((dbg, LEVEL_1, "running on register class: %s\n", bel.cls->name)); + DEBUG_ONLY(be_set_spill_env_dbg_module(env.senv, dbg);) - /* do the work */ be_clear_links(chordal_env->irg); - irg_block_walk_graph(chordal_env->irg, NULL, belady, &bel); - irg_block_walk_graph(chordal_env->irg, fix_block_borders, NULL, &bel); - be_insert_spills_reloads(bel.senv); - remove_copies(&bel); - DEL_ARR_F(bel.copies); - - be_remove_dead_nodes_from_schedule(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, 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 */ + irg_block_walk_graph(chordal_env->irg, fix_block_borders, NULL, &env); + /* Insert spill/reload nodes into the graph and fix usages */ + be_insert_spills_reloads(env.senv); /* clean up */ if(spill_env == NULL) - be_delete_spill_env(bel.senv); - be_end_uses(bel.uses); - obstack_free(&bel.ob, NULL); + be_delete_spill_env(env.senv); + be_end_uses(env.uses); + obstack_free(&env.ob, NULL); }