X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespill.c;h=04c886064602fbdfe5ff48c6cd720be8ae2109c5;hb=70481aa342e22f5f285dc863b366a56393d888af;hp=57cfbd35c720a126fc30017820e17e72adae2bc8;hpb=3c2f7c0c9e0bff5d97a973bc224579922bb7df81;p=libfirm diff --git a/ir/be/bespill.c b/ir/be/bespill.c index 57cfbd35c..04c886064 100644 --- a/ir/be/bespill.c +++ b/ir/be/bespill.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. * @@ -24,11 +24,10 @@ * @date 29.09.2005 * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include +#include #include "pset.h" #include "irnode_t.h" @@ -45,6 +44,7 @@ #include "pdeq.h" #include "execfreq.h" #include "irnodeset.h" +#include "error.h" #include "bearch_t.h" #include "belive_t.h" @@ -53,14 +53,13 @@ #include "belive_t.h" #include "benode_t.h" #include "bechordal_t.h" -#include "bejavacoal.h" -#include "benodesets.h" #include "bespilloptions.h" #include "bestatevent.h" #include "bessaconstr.h" #include "beirg_t.h" #include "beintlive_t.h" #include "bemodule.h" +#include "be_t.h" DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) @@ -69,21 +68,28 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) typedef struct reloader_t reloader_t; struct reloader_t { reloader_t *next; + ir_node *can_spill_after; ir_node *reloader; ir_node *rematted_node; int remat_cost_delta; /** costs needed for rematerialization, compared to placing a reload */ }; +typedef struct spill_t spill_t; +struct spill_t { + spill_t *next; + ir_node *after; /**< spill has to be placed after this node (or earlier) */ + ir_node *spill; +}; + typedef struct spill_info_t spill_info_t; struct spill_info_t { ir_node *to_spill; /**< the value that should get spilled */ reloader_t *reloaders; /**< list of places where the value should get reloaded */ - ir_node *spill; /**< the spill node, or a PhiM node */ - ir_node *old_spill; /**< if we had the value of a phi spilled before but - not the phi itself then this field contains the - spill for the phi value */ + spill_t *spills; /**< list of latest places where spill must be + placed */ + double spill_costs; /**< costs needed for spilling the value */ const arch_register_class_t *reload_cls; /** the register class in which the reload should be placed */ }; @@ -111,31 +117,31 @@ struct spill_env_t { /** * Compare two spill infos. */ -static -int cmp_spillinfo(const void *x, const void *y, size_t size) +static int cmp_spillinfo(const void *x, const void *y, size_t size) { const spill_info_t *xx = x; const spill_info_t *yy = y; + (void) size; + return xx->to_spill != yy->to_spill; } /** * Returns spill info for a specific value (the value that is to be spilled) */ -static -spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) +static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) { spill_info_t info, *res; - int hash = nodeset_hash(value); + int hash = hash_irn(value); info.to_spill = value; res = set_find(env->spills, &info, sizeof(info), hash); if (res == NULL) { - info.reloaders = NULL; - info.spill = NULL; - info.old_spill = NULL; - info.reload_cls = NULL; + info.reloaders = NULL; + info.spills = NULL; + info.spill_costs = -1; + info.reload_cls = NULL; res = set_insert(env->spills, &info, sizeof(info), hash); } @@ -146,14 +152,14 @@ spill_env_t *be_new_spill_env(be_irg_t *birg) { const arch_env_t *arch_env = birg->main_env->arch_env; - spill_env_t *env = xmalloc(sizeof(env[0])); + spill_env_t *env = XMALLOC(spill_env_t); env->spills = new_set(cmp_spillinfo, 1024); env->irg = be_get_birg_irg(birg); env->birg = birg; env->arch_env = arch_env; ir_nodeset_init(&env->mem_phis); - env->spill_cost = arch_env->isa->spill_cost; - env->reload_cost = arch_env->isa->reload_cost; + env->spill_cost = arch_env->spill_cost; + env->reload_cost = arch_env->reload_cost; env->exec_freq = be_get_birg_exec_freq(birg); obstack_init(&env->obst); @@ -184,6 +190,49 @@ void be_delete_spill_env(spill_env_t *env) * */ +void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *after) +{ + spill_info_t *spill_info = get_spillinfo(env, to_spill); + spill_t *spill; + spill_t *s; + spill_t *last; + + assert(!arch_irn_is(to_spill, dont_spill)); + DB((dbg, LEVEL_1, "Add spill of %+F after %+F\n", to_spill, after)); + + /* Just for safety make sure that we do not insert the spill in front of a phi */ + assert(!is_Phi(sched_next(after))); + + /* spills that are dominated by others are not needed */ + last = NULL; + s = spill_info->spills; + for( ; s != NULL; s = s->next) { + /* no need to add this spill if it is dominated by another */ + if(value_dominates(s->after, after)) { + DB((dbg, LEVEL_1, "...dominated by %+F, not added\n", s->after)); + return; + } + /* remove spills that we dominate */ + if(value_dominates(after, s->after)) { + DB((dbg, LEVEL_1, "...remove old spill at %+F\n", s->after)); + if(last != NULL) { + last->next = s->next; + } else { + spill_info->spills = s->next; + } + } else { + last = s; + } + } + + spill = obstack_alloc(&env->obst, sizeof(spill[0])); + spill->after = after; + spill->next = spill_info->spills; + spill->spill = NULL; + + spill_info->spills = spill; +} + void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before, ir_node *rematted_node) { @@ -193,10 +242,10 @@ void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before, spill_info = get_spillinfo(env, to_spill); /* add the remat information */ - reloader = obstack_alloc(&env->obst, sizeof(reloader[0])); - reloader->next = spill_info->reloaders; - reloader->reloader = before; - reloader->rematted_node = rematted_node; + reloader = obstack_alloc(&env->obst, sizeof(reloader[0])); + reloader->next = spill_info->reloaders; + reloader->reloader = before; + reloader->rematted_node = rematted_node; reloader->remat_cost_delta = 0; /* We will never have a cost win over a reload since we're not even allowed to create a reload */ @@ -207,12 +256,15 @@ void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before, to_spill, before)); } -void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before, - const arch_register_class_t *reload_cls, int allow_remat) +void be_add_reload2(spill_env_t *env, ir_node *to_spill, ir_node *before, + ir_node *can_spill_after, const arch_register_class_t *reload_cls, + int allow_remat) { spill_info_t *info; reloader_t *rel; + assert(!arch_irn_is(to_spill, dont_spill)); + info = get_spillinfo(env, to_spill); if (is_Phi(to_spill)) { @@ -223,34 +275,17 @@ void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before, ir_node *arg = get_irn_n(to_spill, i); get_spillinfo(env, arg); } - -#if 1 - /* hackery... sometimes the morgan algo spilled the value of a phi, - * the belady algo decides later to spill the whole phi, then sees the - * spill node and adds a reload for that spill node, problem is the - * reload gets attach to that same spill (and is totally unnecessary) - */ - if (info->old_spill != NULL && - (before == info->old_spill || value_dominates(before, info->old_spill))) - { - printf("spilledphi hack was needed...\n"); - before = sched_next(info->old_spill); - } -#endif } assert(!is_Proj(before) && !be_is_Keep(before)); /* put reload into list */ - rel = obstack_alloc(&env->obst, sizeof(rel[0])); - rel->next = info->reloaders; - rel->reloader = before; - rel->rematted_node = NULL; - if(!allow_remat) { - rel->remat_cost_delta = REMAT_COST_INFINITE; - } else { - rel->remat_cost_delta = 0; - } + rel = obstack_alloc(&env->obst, sizeof(rel[0])); + rel->next = info->reloaders; + rel->reloader = before; + rel->rematted_node = NULL; + rel->can_spill_after = can_spill_after; + rel->remat_cost_delta = allow_remat ? 0 : REMAT_COST_INFINITE; info->reloaders = rel; assert(info->reload_cls == NULL || info->reload_cls == reload_cls); @@ -260,14 +295,47 @@ void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before, to_spill, before, allow_remat ? "" : " not")); } +void be_add_reload(spill_env_t *senv, ir_node *to_spill, ir_node *before, + const arch_register_class_t *reload_cls, int allow_remat) +{ + be_add_reload2(senv, to_spill, before, to_spill, reload_cls, allow_remat); + +} + +ir_node *be_get_end_of_block_insertion_point(const ir_node *block) +{ + ir_node *last = sched_last(block); + + /* we might have keeps behind the jump... */ + while (be_is_Keep(last)) { + last = sched_prev(last); + assert(!sched_is_end(last)); + } + + assert(is_cfop(last)); + + /* add the reload before the (cond-)jump */ + return last; +} + +static ir_node *skip_keeps_phis(ir_node *node) +{ + while(true) { + ir_node *next = sched_next(node); + if(!is_Phi(next) && !be_is_Keep(next)) + break; + node = next; + } + return node; +} + /** * Returns the point at which you can insert a node that should be executed * before block @p block when coming from pred @p pos. */ -static -ir_node *get_block_insertion_point(ir_node *block, int pos) +static ir_node *get_block_insertion_point(ir_node *block, int pos) { - ir_node *predblock, *last; + ir_node *predblock; /* simply add the reload to the beginning of the block if we only have 1 * predecessor. We don't need to check for phis as there can't be any in a @@ -279,22 +347,16 @@ ir_node *get_block_insertion_point(ir_node *block, int pos) /* We have to reload the value in pred-block */ predblock = get_Block_cfgpred_block(block, pos); - last = sched_last(predblock); - - /* we might have projs and keepanys behind the jump... */ - while(is_Proj(last) || be_is_Keep(last)) { - last = sched_prev(last); - assert(!sched_is_end(last)); - } - - if(!is_cfop(last)) { - last = sched_next(last); - /* last node must be a cfop, only exception is the start block */ - assert(last == get_irg_start_block(get_irn_irg(block))); - } + return be_get_end_of_block_insertion_point(predblock); +} - /* add the reload before the (cond-)jump */ - return last; +void be_add_reload_at_end(spill_env_t *env, ir_node *to_spill, + const ir_node *block, + const arch_register_class_t *reload_cls, + int allow_remat) +{ + ir_node *before = be_get_end_of_block_insertion_point(block); + be_add_reload(env, to_spill, before, reload_cls, allow_remat); } void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, @@ -307,6 +369,7 @@ void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, void be_spill_phi(spill_env_t *env, ir_node *node) { + ir_node *block; spill_info_t* spill; int i, arity; @@ -314,20 +377,25 @@ void be_spill_phi(spill_env_t *env, ir_node *node) ir_nodeset_insert(&env->mem_phis, node); - /* create spillinfos for the phi arguments */ + /* create spills for the phi arguments */ + block = get_nodes_block(node); spill = get_spillinfo(env, node); for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *arg = get_irn_n(node, i); - get_spillinfo(env, arg); - } + ir_node *insert; + //get_spillinfo(env, arg); + + /* some backends have virtual noreg/unknown nodes that are not scheduled + * and simply always available. */ + if(!sched_is_scheduled(arg)) { + ir_node *pred_block = get_Block_cfgpred_block(block, i); + insert = be_get_end_of_block_insertion_point(pred_block); + insert = sched_prev(insert); + } else { + insert = skip_keeps_phis(arg); + } - /* if we had a spill for the phi value before, then remove this spill from - * schedule, as we will remove it in the insert spill/reload phase - */ - if(spill->spill != NULL && !is_Phi(spill->spill)) { - assert(spill->old_spill == NULL); - spill->old_spill = spill->spill; - spill->spill = NULL; + be_add_spill(env, arg, insert); } } @@ -340,26 +408,7 @@ void be_spill_phi(spill_env_t *env, ir_node *node) * |_| */ -/** - * Schedules a node after an instruction. That is the place after all projs and - * phis that are scheduled after the instruction. This function also skips phi - * nodes at the beginning of a block - */ -static -void sched_add_after_insn(ir_node *sched_after, ir_node *node) -{ - ir_node *next = sched_next(sched_after); - while(is_Proj(next) || is_Phi(next) || be_is_Keep(next)) { - next = sched_next(next); - } - assert(next != NULL); - - if(sched_is_end(next)) { - sched_add_after(sched_last(get_nodes_block(sched_after)), node); - } else { - sched_add_before(next, node); - } -} +static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo); /** * Creates a spill. @@ -370,58 +419,42 @@ void sched_add_after_insn(ir_node *sched_after, ir_node *node) * * @return a be_Spill node */ -static -void spill_irn(spill_env_t *env, spill_info_t *spillinfo) +static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) { - optimization_state_t opt; - ir_node *to_spill = spillinfo->to_spill; - - DBG((dbg, LEVEL_1, "spilling %+F ... ", to_spill)); - - /* Trying to spill an already spilled value, no need for a new spill - * node then, we can simply connect to the same one for this reload - * - * Normally reloads get simply rematerialized instead of spilled again; this - * can happen annyway when the reload is the pred of a phi to spill) - */ - if (be_is_Reload(to_spill)) { - spillinfo->spill = get_irn_n(to_spill, be_pos_Reload_mem); - DB((dbg, LEVEL_1, "skip reload, using existing spill %+F\n", spillinfo->spill)); - return; - } + ir_node *to_spill = spillinfo->to_spill; + spill_t *spill; - assert(!(arch_irn_is(env->arch_env, to_spill, dont_spill) - && "Attempt to spill a node marked 'dont_spill'")); + /* determine_spill_costs must have been run before */ + assert(spillinfo->spill_costs >= 0); - /* some backends have virtual noreg/unknown nodes that are not scheduled */ + /* some backends have virtual noreg/unknown nodes that are not scheduled + * and simply always available. */ if(!sched_is_scheduled(to_spill)) { - spillinfo->spill = new_NoMem(); + /* override spillinfos or create a new one */ + spillinfo->spills->spill = new_NoMem(); + DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill)); return; } + DBG((dbg, LEVEL_1, "spilling %+F ... \n", to_spill)); + spill = spillinfo->spills; + for( ; spill != NULL; spill = spill->next) { + ir_node *after = spill->after; + ir_node *block = get_block(after); - /* - * We switch on optimizations here to get CSE. This is needed as the STA - * backends has some extra spill phases and we want to make use of those - * spills instead of creating new ones. - */ - save_optimization_state(&opt); - set_optimize(1); - spillinfo->spill = be_spill(env->arch_env, to_spill); - restore_optimization_state(&opt); - if (! sched_is_scheduled(spillinfo->spill)) { - DB((dbg, LEVEL_1, "add spill %+F after %+F\n", spillinfo->spill, to_spill)); + after = skip_keeps_phis(after); + + spill->spill = be_spill(block, to_spill); + sched_add_after(after, spill->spill); + DB((dbg, LEVEL_1, "\t%+F after %+F\n", spill->spill, after)); #ifdef FIRM_STATISTICS env->spill_count++; #endif - sched_add_after_insn(to_spill, spillinfo->spill); - } else { - DB((dbg, LEVEL_1, "re-using spill %+F after %+F\n", spillinfo->spill, to_spill)); } + DBG((dbg, LEVEL_1, "\n")); } -static -void spill_node(spill_env_t *env, spill_info_t *spillinfo); +static void spill_node(spill_env_t *env, spill_info_t *spillinfo); /** * If the first usage of a Phi result would be out of memory @@ -433,59 +466,51 @@ void spill_node(spill_env_t *env, spill_info_t *spillinfo); * @param phi the Phi node that should be spilled * @param ctx_irn an user of the spilled node */ -static -void spill_phi(spill_env_t *env, spill_info_t *spillinfo) +static void spill_phi(spill_env_t *env, spill_info_t *spillinfo) { - ir_node *phi = spillinfo->to_spill; - int i; - int arity = get_irn_arity(phi); - ir_node *block = get_nodes_block(phi); - ir_node **ins; + ir_graph *irg = env->irg; + ir_node *phi = spillinfo->to_spill; + ir_node *block = get_nodes_block(phi); + ir_node *unknown; + ir_node **ins; + spill_t *spill; + int i; + int arity; assert(is_Phi(phi)); - + assert(!get_opt_cse()); DBG((dbg, LEVEL_1, "spilling Phi %+F:\n", phi)); + /* build a new PhiM */ - ins = alloca(sizeof(ir_node*) * arity); + arity = get_irn_arity(phi); + ins = alloca(sizeof(ir_node*) * arity); + unknown = new_r_Unknown(irg, mode_M); for(i = 0; i < arity; ++i) { - ins[i] = get_irg_bad(env->irg); + ins[i] = unknown; } - spillinfo->spill = new_r_Phi(env->irg, block, arity, ins, mode_M); + + /* override or replace spills list... */ + spill = obstack_alloc(&env->obst, sizeof(spill[0])); + spill->after = skip_keeps_phis(phi); + spill->spill = new_r_Phi(irg, block, arity, ins, mode_M); + spill->next = NULL; + + spillinfo->spills = spill; #ifdef FIRM_STATISTICS env->spilled_phi_count++; #endif for(i = 0; i < arity; ++i) { - ir_node *arg = get_irn_n(phi, i); + ir_node *arg = get_irn_n(phi, i); spill_info_t *arg_info = get_spillinfo(env, arg); + determine_spill_costs(env, arg_info); spill_node(env, arg_info); - set_irn_n(spillinfo->spill, i, arg_info->spill); - } - DBG((dbg, LEVEL_1, "... done spilling Phi %+F, created PhiM %+F\n", phi, spillinfo->spill)); - - /* rewire reloads from old_spill to phi */ - if (spillinfo->old_spill != NULL) { - const ir_edge_t *edge, *next; - ir_node *old_spill = spillinfo->old_spill; - - DBG((dbg, LEVEL_1, "old spill found, rewiring reloads:\n")); - - foreach_out_edge_safe(old_spill, edge, next) { - ir_node *reload = get_edge_src_irn(edge); - int pos = get_edge_src_pos(edge); - - DBG((dbg, LEVEL_1, "\tset input %d of %+F to %+F\n", pos, reload, spillinfo->spill)); - - assert(be_is_Reload(reload) || is_Phi(reload)); - set_irn_n(reload, pos, spillinfo->spill); - } - DBG((dbg, LEVEL_1, "\tset input of %+F to BAD\n", old_spill)); - set_irn_n(old_spill, be_pos_Spill_val, new_Bad()); - /* sched_remove(old_spill); */ - spillinfo->old_spill = NULL; + set_irn_n(spill->spill, i, arg_info->spills->spill); } + DBG((dbg, LEVEL_1, "... done spilling Phi %+F, created PhiM %+F\n", phi, + spill->spill)); } /** @@ -494,13 +519,12 @@ void spill_phi(spill_env_t *env, spill_info_t *spillinfo) * @param senv the spill environment * @param to_spill the node that should be spilled */ -static -void spill_node(spill_env_t *env, spill_info_t *spillinfo) +static void spill_node(spill_env_t *env, spill_info_t *spillinfo) { ir_node *to_spill; - /* the node should be tagged for spilling already... */ - if(spillinfo->spill != NULL) + /* node is already spilled */ + if(spillinfo->spills != NULL && spillinfo->spills->spill != NULL) return; to_spill = spillinfo->to_spill; @@ -526,8 +550,8 @@ void spill_node(spill_env_t *env, spill_info_t *spillinfo) * Tests whether value @p arg is available before node @p reloader * @returns 1 if value is available, 0 otherwise */ -static -int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader) +static int is_value_available(spill_env_t *env, const ir_node *arg, + const ir_node *reloader) { if(is_Unknown(arg) || arg == new_NoMem()) return 1; @@ -546,7 +570,7 @@ int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader) /* * Ignore registers are always available */ - if(arch_irn_is(env->arch_env, arg, ignore)) { + if (arch_irn_is(arg, ignore)) { return 1; } @@ -578,14 +602,11 @@ int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader) /** * Checks whether the node can principally be rematerialized */ -static -int is_remat_node(spill_env_t *env, ir_node *node) +static int is_remat_node(const ir_node *node) { - const arch_env_t *arch_env = env->arch_env; - assert(!be_is_Spill(node)); - if(arch_irn_is(arch_env, node, rematerializable)) + if (arch_irn_is(node, rematerializable)) return 1; return 0; @@ -601,25 +622,27 @@ int is_remat_node(spill_env_t *env, ir_node *node) * Returns the costs needed for rematerialisation or something * >= REMAT_COST_INFINITE if remat is not possible. */ -static -int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, - ir_node *reloader, int parentcosts) +static int check_remat_conditions_costs(spill_env_t *env, + const ir_node *spilled, const ir_node *reloader, int parentcosts) { int i, arity; int argremats; int costs = 0; - if(!is_remat_node(env, spilled)) + if (!is_remat_node(spilled)) return REMAT_COST_INFINITE; if(be_is_Reload(spilled)) { costs += 2; } else { - costs += arch_get_op_estimated_cost(env->arch_env, spilled); + costs += arch_get_op_estimated_cost(spilled); } if(parentcosts + costs >= env->reload_cost + env->spill_cost) { return REMAT_COST_INFINITE; } + if (arch_irn_is(spilled, modify_flags)) { + return REMAT_COST_INFINITE; + } argremats = 0; for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) { @@ -637,7 +660,8 @@ int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, } argremats++; - costs += check_remat_conditions_costs(env, arg, reloader, parentcosts + costs); + costs += check_remat_conditions_costs(env, arg, reloader, + parentcosts + costs); if(parentcosts + costs >= env->reload_cost + env->spill_cost) return REMAT_COST_INFINITE; } @@ -652,8 +676,7 @@ int check_remat_conditions_costs(spill_env_t *env, ir_node *spilled, * @param spilled the node that was spilled * @param reloader a irn that requires a reload */ -static -ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) +static ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) { int i, arity; ir_node *res; @@ -686,28 +709,45 @@ ir_node *do_remat(spill_env_t *env, ir_node *spilled, ir_node *reloader) get_irn_op(spilled), get_irn_mode(spilled), get_irn_arity(spilled), ins); copy_node_attr(spilled, res); + arch_env_mark_remat(env->arch_env, res); new_backedge_info(res); - sched_reset(res); DBG((dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res, spilled, reloader)); - /* insert in schedule */ - sched_add_before(reloader, res); + if (! is_Proj(res)) { + /* insert in schedule */ + sched_reset(res); + sched_add_before(reloader, res); #ifdef FIRM_STATISTICS - env->remat_count++; + env->remat_count++; #endif + } return res; } -double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *after) +double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) { - ir_node *block = get_nodes_block(after); + ir_node *block = get_nodes_block(before); double freq = get_block_execfreq(env->exec_freq, block); + (void) to_spill; return env->spill_cost * freq; } +unsigned be_get_reload_costs_no_weight(spill_env_t *env, const ir_node *to_spill, + const ir_node *before) +{ + if(be_do_remats) { + /* is the node rematerializable? */ + unsigned costs = check_remat_conditions_costs(env, to_spill, before, 0); + if(costs < (unsigned) env->reload_cost) + return costs; + } + + return env->reload_cost; +} + double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) { ir_node *block = get_nodes_block(before); @@ -723,8 +763,14 @@ double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before) return env->reload_cost * freq; } +int be_is_rematerializable(spill_env_t *env, const ir_node *to_remat, + const ir_node *before) +{ + return check_remat_conditions_costs(env, to_remat, before, 0) < REMAT_COST_INFINITE; +} + double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, - ir_node *block, int pos) + ir_node *block, int pos) { ir_node *before = get_block_insertion_point(block, pos); return be_get_reload_costs(env, to_spill, before); @@ -739,14 +785,132 @@ double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill, * */ +/** + * analyzes how to best spill a node and determine costs for that + */ +static void determine_spill_costs(spill_env_t *env, spill_info_t *spillinfo) +{ + ir_node *to_spill = spillinfo->to_spill; + ir_node *spill_block; + spill_t *spill; + double spill_execfreq; + + /* already calculated? */ + if(spillinfo->spill_costs >= 0) + return; + + assert(!arch_irn_is(to_spill, dont_spill)); + assert(!be_is_Reload(to_spill)); + + /* some backends have virtual noreg/unknown nodes that are not scheduled + * and simply always available. + * TODO: this is kinda hairy, the NoMem is correct for an Unknown as Phi + * predecessor (of a PhiM) but this test might match other things too... + */ + if(!sched_is_scheduled(to_spill)) { + /* override spillinfos or create a new one */ + spill_t *spill = obstack_alloc(&env->obst, sizeof(spill[0])); + spill->after = NULL; + spill->next = NULL; + spill->spill = new_NoMem(); + + spillinfo->spills = spill; + spillinfo->spill_costs = 0; + + DB((dbg, LEVEL_1, "don't spill %+F use NoMem\n", to_spill)); + return; + } + + spill_block = get_nodes_block(to_spill); + spill_execfreq = get_block_execfreq(env->exec_freq, spill_block); + + if (is_Phi(to_spill) && ir_nodeset_contains(&env->mem_phis, to_spill)) { + /* TODO calculate correct costs... + * (though we can't remat this node anyway so no big problem) */ + spillinfo->spill_costs = env->spill_cost * spill_execfreq; + return; + } + + if(spillinfo->spills != NULL) { + spill_t *s; + double spills_execfreq; + + /* calculate sum of execution frequencies of individual spills */ + spills_execfreq = 0; + s = spillinfo->spills; + for( ; s != NULL; s = s->next) { + ir_node *spill_block = get_block(s->after); + double freq = get_block_execfreq(env->exec_freq, spill_block); + + spills_execfreq += freq; + } + + DB((dbg, LEVEL_1, "%+F: latespillcosts %f after def: %f\n", to_spill, + spills_execfreq * env->spill_cost, + spill_execfreq * env->spill_cost)); + + /* multi-/latespill is advantageous -> return*/ + if(spills_execfreq < spill_execfreq) { + DB((dbg, LEVEL_1, "use latespills for %+F\n", to_spill)); + spillinfo->spill_costs = spills_execfreq * env->spill_cost; + return; + } + } + + /* override spillinfos or create a new one */ + spill = obstack_alloc(&env->obst, sizeof(spill[0])); + spill->after = skip_keeps_phis(to_spill); + spill->next = NULL; + spill->spill = NULL; + + spillinfo->spills = spill; + spillinfo->spill_costs = spill_execfreq * env->spill_cost; + DB((dbg, LEVEL_1, "spill %+F after definition\n", to_spill)); +} + +void make_spill_locations_dominate_irn(spill_env_t *env, ir_node *irn) +{ + const spill_info_t *si = get_spillinfo(env, irn); + ir_node *start_block = get_irg_start_block(get_irn_irg(irn)); + int n_blocks = get_Block_dom_max_subtree_pre_num(start_block); + bitset_t *reloads = bitset_alloca(n_blocks); + reloader_t *r; + spill_t *s; + + if (si == NULL) + return; + + /* Fill the bitset with the dominance pre-order numbers + * of the blocks the reloads are located in. */ + for (r = si->reloaders; r != NULL; r = r->next) { + ir_node *bl = get_nodes_block(r->reloader); + bitset_set(reloads, get_Block_dom_tree_pre_num(bl)); + } + + /* Now, cancel out all the blocks that are dominated by each spill. + * If the bitset is not empty after that, we have reloads that are + * not dominated by any spill. */ + for (s = si->spills; s != NULL; s = s->next) { + ir_node *bl = get_nodes_block(s->after); + int start = get_Block_dom_tree_pre_num(bl); + int end = get_Block_dom_max_subtree_pre_num(bl); + + bitset_clear_range(reloads, start, end); + } + + if (!bitset_is_empty(reloads)) + be_add_spill(env, si->to_spill, si->to_spill); +} + void be_insert_spills_reloads(spill_env_t *env) { - const arch_env_t *arch_env = env->arch_env; const ir_exec_freq *exec_freq = env->exec_freq; spill_info_t *si; ir_nodeset_iterator_t iter; ir_node *node; + BE_TIMER_PUSH(t_ra_spill_apply); + /* create all phi-ms first, this is needed so, that phis, hanging on spilled phis work correctly */ foreach_ir_nodeset(&env->mem_phis, node, iter) { @@ -765,8 +929,12 @@ void be_insert_spills_reloads(spill_env_t *env) DBG((dbg, LEVEL_1, "\nhandling all reloaders of %+F:\n", to_spill)); + determine_spill_costs(env, si); + /* determine possibility of rematerialisations */ if(be_do_remats) { + /* calculate cost savings for each indivial value when it would + be rematted instead of reloaded */ for (rld = si->reloaders; rld != NULL; rld = rld->next) { double freq; int remat_cost; @@ -798,7 +966,7 @@ void be_insert_spills_reloads(spill_env_t *env) remat_cost_delta = remat_cost - env->reload_cost; rld->remat_cost_delta = remat_cost_delta; - block = get_nodes_block(reloader); + block = is_Block(reloader) ? reloader : get_nodes_block(reloader); freq = get_block_execfreq(exec_freq, block); all_remat_costs += remat_cost_delta * freq; DBG((dbg, LEVEL_2, "\tremat costs delta before %+F: " @@ -806,14 +974,12 @@ void be_insert_spills_reloads(spill_env_t *env) remat_cost_delta * freq)); } if(all_remat_costs < REMAT_COST_INFINITE) { - ir_node *block = get_nodes_block(to_spill); - double freq = get_block_execfreq(exec_freq, block); /* we don't need the costs for the spill if we can remat all reloaders */ - all_remat_costs -= env->spill_cost * freq; + all_remat_costs -= si->spill_costs; DBG((dbg, LEVEL_2, "\tspill costs %d (rel %f)\n", - env->spill_cost, env->spill_cost * freq)); + env->spill_cost, si->spill_costs)); } if(all_remat_costs < 0) { @@ -835,13 +1001,13 @@ void be_insert_spills_reloads(spill_env_t *env) copy = do_remat(env, to_spill, rld->reloader); } else { /* make sure we have a spill */ - if (si->spill == NULL) { - spill_node(env, si); - } + spill_node(env, si); - /* create a reload */ - copy = be_reload(arch_env, si->reload_cls, rld->reloader, mode, - si->spill); + /* create a reload, use the first spill for now SSA + * reconstruction for memory comes below */ + assert(si->spills != NULL); + copy = be_reload(si->reload_cls, rld->reloader, mode, + si->spills->spill); #ifdef FIRM_STATISTICS env->reload_count++; #endif @@ -875,24 +1041,46 @@ void be_insert_spills_reloads(spill_env_t *env) #endif be_ssa_construction_destroy(&senv); } + /* need to reconstruct SSA form if we had multiple spills */ + if (si->spills != NULL && si->spills->next != NULL) { + spill_t *spill; + int spill_count = 0; + + be_ssa_construction_env_t senv; + + be_ssa_construction_init(&senv, env->birg); + spill = si->spills; + for( ; spill != NULL; spill = spill->next) { + /* maybe we rematerialized the value and need no spill */ + if(spill->spill == NULL) + continue; + be_ssa_construction_add_copy(&senv, spill->spill); + spill_count++; + } + if(spill_count > 1) { + /* all reloads are attached to the first spill, fix them now */ + be_ssa_construction_fix_users(&senv, si->spills->spill); + } + + be_ssa_construction_destroy(&senv); + } DEL_ARR_F(copies); si->reloaders = NULL; } -#ifdef FIRM_STATISTICS - if (be_stat_ev_is_active()) { - be_stat_ev("spill_spills", env->spill_count); - be_stat_ev("spill_reloads", env->reload_count); - be_stat_ev("spill_remats", env->remat_count); - be_stat_ev("spill_spilled_phis", env->spilled_phi_count); - } -#endif + stat_ev_dbl("spill_spills", env->spill_count); + stat_ev_dbl("spill_reloads", env->reload_count); + stat_ev_dbl("spill_remats", env->remat_count); + stat_ev_dbl("spill_spilled_phis", env->spilled_phi_count); - be_remove_dead_nodes_from_schedule(env->irg); /* Matze: In theory be_ssa_construction should take care of the liveness... * try to disable this again in the future */ be_liveness_invalidate(env->birg->lv); + + be_remove_dead_nodes_from_schedule(env->birg); + + BE_TIMER_POP(t_ra_spill_apply); } void be_init_spill(void)