* @date 29.09.2005
* @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <stdlib.h>
+#include <stdbool.h>
#include "pset.h"
#include "irnode_t.h"
#include "belive_t.h"
#include "benode_t.h"
#include "bechordal_t.h"
-#include "bejavacoal.h"
#include "bespilloptions.h"
#include "bestatevent.h"
#include "bessaconstr.h"
typedef struct spill_t spill_t;
struct spill_t {
spill_t *next;
- ir_node *before; /**< spill has to be placed before this node (or earlier) */
+ ir_node *after; /**< spill has to be placed after this node (or earlier) */
ir_node *spill;
};
placed */
ir_nodeset_t mem_phis; /**< set of all spilled phis. */
ir_exec_freq *exec_freq;
- unsigned new_nodes_idx; /**< all old nodes idx is smaller than
- this */
#ifdef FIRM_STATISTICS
unsigned spill_count;
{
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);
*
*/
-void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *before)
+void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *after)
{
-#if 1
spill_info_t *spill_info = get_spillinfo(env, to_spill);
spill_t *spill;
spill_t *s;
spill_t *last;
- assert(! arch_irn_is(env->arch_env, to_spill, dont_spill));
- DB((dbg, LEVEL_1, "Add spill of %+F before %+F\n", to_spill, before));
+ 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 */
- for (; is_Phi(before); before = sched_next(before));
+ 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->before, before)) {
- DB((dbg, LEVEL_1, "...dominated by %+F, not added\n", s->before));
+ 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(before, s->before)) {
- DB((dbg, LEVEL_1, "...remove old spill at %+F\n", s->before));
+ 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 = obstack_alloc(&env->obst, sizeof(spill[0]));
- spill->before = before;
+ spill->after = after;
spill->next = spill_info->spills;
spill->spill = NULL;
spill_info->spills = spill;
-#endif
}
void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before,
spill_info_t *info;
reloader_t *rel;
- assert(! arch_irn_is(env->arch_env, to_spill, dont_spill));
+ assert(!arch_irn_is(to_spill, dont_spill));
info = get_spillinfo(env, to_spill);
ir_node *last = sched_last(block);
/* we might have keeps behind the jump... */
- while(be_is_Keep(last)) {
+ while (be_is_Keep(last)) {
last = sched_prev(last);
assert(!sched_is_end(last));
}
static ir_node *skip_keeps_phis(ir_node *node)
{
- node = sched_next(node);
- while(is_Phi(node) || be_is_Keep(node)) {
- node = sched_next(node);
+ while(true) {
+ ir_node *next = sched_next(node);
+ if(!is_Phi(next) && !be_is_Keep(next))
+ break;
+ node = next;
}
return node;
}
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);
+ ir_node *arg = get_irn_n(node, i);
ir_node *insert;
//get_spillinfo(env, arg);
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);
}
DBG((dbg, LEVEL_1, "spilling %+F ... \n", to_spill));
spill = spillinfo->spills;
for( ; spill != NULL; spill = spill->next) {
- ir_node *block = get_block(spill->before);
- ir_node *before = spill->before;
-
- /* place all spills before the reloads (as we can't guarantee the
- * same order as the be_add_spill and be_add_reload calls.
- * Also make sure that we do not run into Phis when going up. */
- while(get_irn_idx(sched_prev(before)) > env->new_nodes_idx && !is_Phi(sched_prev(before))) {
- before = sched_prev(before);
- }
+ ir_node *after = spill->after;
+ ir_node *block = get_block(after);
+
+ after = skip_keeps_phis(after);
- spill->spill = be_spill(env->arch_env, block, to_spill);
- sched_add_before(before, spill->spill);
- DB((dbg, LEVEL_1, "\t%+F before %+F\n", spill->spill, before));
+ 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
/* build a new PhiM */
arity = get_irn_arity(phi);
- ins = alloca(sizeof(ir_node*) * arity);
+ ins = ALLOCAN(ir_node*, arity);
unknown = new_r_Unknown(irg, mode_M);
for(i = 0; i < arity; ++i) {
ins[i] = unknown;
/* override or replace spills list... */
spill = obstack_alloc(&env->obst, sizeof(spill[0]));
- spill->before = skip_keeps_phis(phi);
+ spill->after = skip_keeps_phis(phi);
spill->spill = new_r_Phi(irg, block, arity, ins, mode_M);
spill->next = NULL;
if(arg == get_irg_frame(env->irg))
return 1;
+#if 0
/* hack for now (happens when command should be inserted at end of block) */
- if(is_Block(reloader)) {
+ if(is_Block(reloader))
return 0;
- }
+#else
+ (void)reloader;
+#endif
/*
* Ignore registers are always available
*/
- if(arch_irn_is(env->arch_env, arg, ignore)) {
- return 1;
- }
-
- /* the following test does not work while spilling,
- * because the liveness info is not adapted yet to the effects of the
- * additional spills/reloads.
- */
-#if 0
- /* we want to remat before the insn reloader
- * thus an arguments is alive if
- * - it interferes with the reloaders result
- * - or it is (last-) used by reloader itself
- */
- if (values_interfere(env->birg->lv, reloader, arg)) {
+ if (arch_irn_is_ignore(arg))
return 1;
- }
-
- arity = get_irn_arity(reloader);
- for (i = 0; i < arity; ++i) {
- ir_node *rel_arg = get_irn_n(reloader, i);
- if (rel_arg == arg)
- return 1;
- }
-#endif
return 0;
}
/**
* Checks whether the node can principally be rematerialized
*/
-static int is_remat_node(spill_env_t *env, const 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;
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(env->arch_env, spilled, modify_flags)) {
+ /* never rematerialize a node which modifies the flags.
+ * (would be better to test wether the flags are actually live at point
+ * reloader...)
+ */
+ if (arch_irn_is(spilled, modify_flags)) {
return REMAT_COST_INFINITE;
}
bl = get_nodes_block(reloader);
}
- ins = alloca(get_irn_arity(spilled) * sizeof(ins[0]));
+ ins = ALLOCAN(ir_node*, get_irn_arity(spilled));
for(i = 0, arity = get_irn_arity(spilled); i < arity; ++i) {
ir_node *arg = get_irn_n(spilled, i);
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);
DBG((dbg, LEVEL_1, "Insert remat %+F of %+F before reloader %+F\n", res, spilled, reloader));
if(spillinfo->spill_costs >= 0)
return;
- assert(! arch_irn_is(env->arch_env, to_spill, dont_spill));
+ 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
if(!sched_is_scheduled(to_spill)) {
/* override spillinfos or create a new one */
spill_t *spill = obstack_alloc(&env->obst, sizeof(spill[0]));
- spill->before = NULL;
- spill->next = NULL;
- spill->spill = new_NoMem();
+ spill->after = NULL;
+ spill->next = NULL;
+ spill->spill = new_NoMem();
spillinfo->spills = spill;
spillinfo->spill_costs = 0;
spill_t *s;
double spills_execfreq;
- /* calculate sum of executaion frequencies of individual spills */
+ /* calculate sum of execution frequencies of individual spills */
spills_execfreq = 0;
s = spillinfo->spills;
for( ; s != NULL; s = s->next) {
- ir_node *spill_block = s->before;
- double freq;
-
- if(!is_Block(spill_block)) {
- spill_block = get_nodes_block(spill_block);
- }
- freq = get_block_execfreq(env->exec_freq, spill_block);
+ ir_node *spill_block = get_block(s->after);
+ double freq = get_block_execfreq(env->exec_freq, spill_block);
spills_execfreq += freq;
}
}
/* override spillinfos or create a new one */
- spill = obstack_alloc(&env->obst, sizeof(spill[0]));
- spill->before = skip_keeps_phis(to_spill);
- spill->next = NULL;
- spill->spill = NULL;
+ 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;
* 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->before);
+ 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);
}
if (!bitset_is_empty(reloads))
- be_add_spill(env, si->to_spill, sched_next(si->to_spill));
+ be_add_spill(env, si->to_spill, si->to_spill);
}
void be_insert_spills_reloads(spill_env_t *env)
{
- ir_graph *irg = env->irg;
- 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;
BE_TIMER_PUSH(t_ra_spill_apply);
- env->new_nodes_idx = get_irg_last_idx(irg);
-
/* 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) {
/* create a reload, use the first spill for now SSA
* reconstruction for memory comes below */
assert(si->spills != NULL);
- copy = be_reload(arch_env, si->reload_cls, rld->reloader, mode,
+ copy = be_reload(si->reload_cls, rld->reloader, mode,
si->spills->spill);
#ifdef FIRM_STATISTICS
env->reload_count++;