/**
* @file
- * @brief Main spill driver.
+ * @brief implementation of the spill/reload placement abstraction layer
* @author Daniel Grund, Sebastian Hack, Matthias Braun
* @date 29.09.2005
* @version $Id$
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
-/* only rematerialise when costs are less than REMAT_COST_LIMIT */
-/* TODO determine a good value here... */
-#define REMAT_COST_LIMIT 10
-
#define REMAT_COST_INFINITE 1000
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,
typedef struct spill_info_t spill_info_t;
struct spill_info_t {
- /** the value that should get spilled */
- ir_node *to_spill;
- /** list of places where the value should get reloaded */
- reloader_t *reloaders;
-
- /** the spill node, or a PhiM node */
- ir_node *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 */
- ir_node *old_spill;
-
- /** the register class in which the reload should be placed */
- const arch_register_class_t *reload_cls;
+ 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 */
+ const arch_register_class_t *reload_cls; /** the register class in which the
+ reload should be placed */
};
struct spill_env_t {
const arch_env_t *arch_env;
- ir_graph *irg;
- struct obstack obst;
- be_irg_t *birg;
- int spill_cost; /**< the cost of a single spill node */
- int reload_cost; /**< the cost of a reload node */
- set *spills; /**< all spill_info_t's, which must be placed */
- ir_nodeset_t mem_phis; /**< set of all special spilled phis. allocated and freed separately */
+ ir_graph *irg;
+ struct obstack obst;
+ be_irg_t *birg;
+ int spill_cost; /**< the cost of a single spill node */
+ int reload_cost; /**< the cost of a reload node */
+ set *spills; /**< all spill_info_t's, which must be
+ placed */
+ ir_nodeset_t mem_phis; /**< set of all spilled phis. */
+ ir_exec_freq *exec_freq;
+
#ifdef FIRM_STATISTICS
- int spill_count;
- int reload_count;
- int remat_count;
- int spilled_phi_count;
+ unsigned spill_count;
+ unsigned reload_count;
+ unsigned remat_count;
+ unsigned spilled_phi_count;
#endif
};
/**
* 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;
- return xx->to_spill != yy->to_spill;
-}
+ (void) size;
-/**
- * Returns spill info for a specific value (returns NULL if the info doesn't
- * exist yet)
- */
-static spill_info_t *find_spillinfo(const spill_env_t *env, ir_node *value) {
- spill_info_t info;
- int hash = nodeset_hash(value);
-
- info.to_spill = value;
-
- return set_find(env->spills, &info, sizeof(info), hash);
+ 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);
return res;
}
-/* Creates a new spill environment. */
spill_env_t *be_new_spill_env(be_irg_t *birg)
{
const arch_env_t *arch_env = birg->main_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->exec_freq = be_get_birg_exec_freq(birg);
obstack_init(&env->obst);
+
#ifdef FIRM_STATISTICS
env->spill_count = 0;
env->reload_count = 0;
return env;
}
-/* Deletes a spill environment. */
void be_delete_spill_env(spill_env_t *env)
{
del_set(env->spills);
reloader->next = spill_info->reloaders;
reloader->reloader = before;
reloader->rematted_node = rematted_node;
- reloader->remat_cost_delta = 0; /* delta is 0 since we will do a remat in
- each, as we will never place a reload,
- we will never have a cost win */
+ 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 */
spill_info->reloaders = reloader;
to_spill, before));
}
-void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before,
+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;
#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);
to_spill, before, allow_remat ? "" : " not"));
}
-/**
- * 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) {
- ir_node *predblock, *last;
+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);
- /* 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
- * block with only 1 pred. */
- if(get_Block_n_cfgpreds(block) == 1) {
- assert(!is_Phi(sched_first(block)));
- return sched_first(block);
- }
+}
- /* We have to reload the value in pred-block */
- predblock = get_Block_cfgpred_block(block, pos);
- last = sched_last(predblock);
+ir_node *be_get_end_of_block_insertion_point(const ir_node *block)
+{
+ ir_node *last = sched_last(block);
/* we might have projs and keepanys behind the jump... */
- while(is_Proj(last) || be_is_Keep(last)) {
+ while(be_is_Keep(last)) {
last = sched_prev(last);
assert(!sched_is_end(last));
}
return last;
}
+/**
+ * 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)
+{
+ 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
+ * block with only 1 pred. */
+ if(get_Block_n_cfgpreds(block) == 1) {
+ assert(!is_Phi(sched_first(block)));
+ return sched_first(block);
+ }
+
+ /* We have to reload the value in pred-block */
+ predblock = get_Block_cfgpred_block(block, pos);
+ return be_get_end_of_block_insertion_point(predblock);
+}
+
+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,
int pos, const arch_register_class_t *reload_cls,
int allow_remat)
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)) {
+ while(is_Proj(next) || is_Phi(next) || be_is_Keep(next)) {
next = sched_next(next);
}
assert(next != NULL);
/* build a new PhiM */
ins = alloca(sizeof(ir_node*) * arity);
for(i = 0; i < arity; ++i) {
- ins[i] = get_irg_bad(env->irg);
+ ins[i] = new_r_Unknown(env->irg, mode_M);
}
+ assert(!get_opt_cse());
spillinfo->spill = new_r_Phi(env->irg, block, arity, ins, mode_M);
#ifdef FIRM_STATISTICS
env->spilled_phi_count++;
* @returns 1 if value is available, 0 otherwise
*/
static
-int is_value_available(spill_env_t *env, ir_node *arg, ir_node *reloader)
+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;
* Checks whether the node can principally be rematerialized
*/
static
-int is_remat_node(spill_env_t *env, ir_node *node)
+int is_remat_node(spill_env_t *env, const ir_node *node)
{
const arch_env_t *arch_env = env->arch_env;
* >= 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)
+int check_remat_conditions_costs(spill_env_t *env, const ir_node *spilled,
+ const ir_node *reloader, int parentcosts)
{
int i, arity;
int argremats;
if(parentcosts + costs >= env->reload_cost + env->spill_cost) {
return REMAT_COST_INFINITE;
}
+ if(arch_irn_is(env->arch_env, spilled, modify_flags)) {
+ return REMAT_COST_INFINITE;
+ }
argremats = 0;
for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
get_irn_arity(spilled), ins);
copy_node_attr(spilled, 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;
}
-int be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
+double be_get_spill_costs(spill_env_t *env, ir_node *to_spill, ir_node *after)
{
- spill_info_t *spill_info;
+ ir_node *block = get_nodes_block(after);
+ double freq = get_block_execfreq(env->exec_freq, block);
+ (void) to_spill;
+
+ return env->spill_cost * freq;
+}
+
+double be_get_reload_costs(spill_env_t *env, ir_node *to_spill, ir_node *before)
+{
+ ir_node *block = get_nodes_block(before);
+ double freq = get_block_execfreq(env->exec_freq, block);
if(be_do_remats) {
/* is the node rematerializable? */
int costs = check_remat_conditions_costs(env, to_spill, before, 0);
- if(costs < env->spill_cost + env->reload_cost)
- return costs;
+ if(costs < env->reload_cost)
+ return costs * freq;
}
- /* do we already have a spill? */
- spill_info = find_spillinfo(env, to_spill);
- if(spill_info != NULL && spill_info->spill != NULL)
- return env->reload_cost;
+ return env->reload_cost * freq;
+}
- return env->spill_cost + env->reload_cost;
+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;
}
-int be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill,
+double be_get_reload_costs_on_edge(spill_env_t *env, ir_node *to_spill,
ir_node *block, int pos)
{
ir_node *before = get_block_insertion_point(block, pos);
void be_insert_spills_reloads(spill_env_t *env)
{
const arch_env_t *arch_env = env->arch_env;
- const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg);
+ const ir_exec_freq *exec_freq = env->exec_freq;
spill_info_t *si;
ir_nodeset_iterator_t iter;
ir_node *node;
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: "
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_invalidate_liveness(env->birg);
+ be_liveness_invalidate(env->birg->lv);
+
+ be_remove_dead_nodes_from_schedule(env->birg);
}
void be_init_spill(void)
projects / libfirm / blobdiff