#include "beirg.h"
#include "bearch.h"
-#define DBG_COALESCING 1
-#define DBG_INTERFERENCES 2
+#define DBG_COALESCING 1
+#define DBG_INTERFERENCES 2
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
-typedef struct _spill_t {
- ir_node *spill;
- const ir_mode *mode; /**< mode of the spilled value */
- int alignment; /**< alignment for the spilled value */
- int spillslot; /**< index into spillslot_unionfind structure */
+typedef struct spill_t {
+ ir_node *spill;
+ const ir_mode *mode; /**< mode of the spilled value */
+ int alignment; /**< alignment for the spilled value */
+ int spillslot; /**< index into spillslot_unionfind structure */
} spill_t;
-typedef struct _affinity_edge_t {
+typedef struct affinity_edge_t {
double affinity;
- int slot1, slot2;
+ int slot1;
+ int slot2;
} affinity_edge_t;
-struct _be_fec_env_t {
- struct obstack obst;
- const arch_env_t *arch_env;
- be_irg_t *birg;
- set *spills;
- ir_node **reloads;
- affinity_edge_t **affinity_edges;
- set *memperms;
+struct be_fec_env_t {
+ struct obstack obst;
+ ir_graph *irg;
+ set *spills;
+ ir_node **reloads;
+ affinity_edge_t **affinity_edges;
+ set *memperms;
+ set_frame_entity_func set_frame_entity;
+ bool at_begin; /**< frame entities should be allocate at
+ the beginning of the stackframe */
};
/** Compare 2 affinity edges (used in quicksort) */
static int cmp_affinity(const void *d1, const void *d2)
{
- const affinity_edge_t * const *e1 = d1;
- const affinity_edge_t * const *e2 = d2;
+ const affinity_edge_t * const *e1 = (const affinity_edge_t**)d1;
+ const affinity_edge_t * const *e2 = (const affinity_edge_t**)d2;
/* sort in descending order */
return (*e1)->affinity < (*e2)->affinity ? 1 : -1;
static int cmp_spill(const void* d1, const void* d2, size_t size)
{
- const spill_t* s1 = d1;
- const spill_t* s2 = d2;
+ const spill_t* s1 = (const spill_t*)d1;
+ const spill_t* s2 = (const spill_t*)d2;
(void) size;
return s1->spill != s2->spill;
int hash = hash_irn(node);
spill.spill = node;
- res = set_find(env->spills, &spill, sizeof(spill), hash);
+ res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash);
return res;
}
/* insert into set of spills if not already there */
spill.spill = node;
- res = set_find(env->spills, &spill, sizeof(spill), hash);
+ res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash);
if (res == NULL) {
spill.spillslot = set_count(env->spills);
spill.mode = mode;
spill.alignment = align;
- res = set_insert(env->spills, &spill, sizeof(spill), hash);
+ res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash);
DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node));
} else {
assert(res->mode == mode);
int i, arity;
spill_t spill, *res;
int hash = hash_irn(node);
- const ir_exec_freq *exec_freq = be_get_birg_exec_freq(env->birg);
+ const ir_exec_freq *exec_freq = be_get_irg_exec_freq(env->irg);
assert(is_Phi(node));
spill.spill = node;
- res = set_find(env->spills, &spill, sizeof(spill), hash);
+ res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash);
if (res != NULL) {
assert(res->mode == mode);
assert(res->alignment == align);
spill.mode = mode;
spill.alignment = align;
DB((dbg, DBG_COALESCING, "Slot %d: %+F\n", spill.spillslot, node));
- res = set_insert(env->spills, &spill, sizeof(spill), hash);
+ res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash);
/* collect attached spills and mem-phis */
arity = get_irn_arity(node);
return res;
}
-static int my_values_interfere2(be_irg_t *birg, const ir_node *a,
+static int my_values_interfere2(ir_graph *irg, const ir_node *a,
const ir_node *b)
{
- be_lv_t *lv = be_get_birg_liveness(birg);
+ be_lv_t *lv = be_get_irg_liveness(irg);
int a2b = _value_dominates(a, b);
int b2a = _value_dominates(b, a);
/**
* same as values_interfere but with special handling for Syncs
*/
-static int my_values_interfere(be_irg_t *birg, ir_node *a, ir_node *b)
+static int my_values_interfere(ir_graph *irg, ir_node *a, ir_node *b)
{
if (is_Sync(a)) {
int i, arity = get_irn_arity(a);
for (i = 0; i < arity; ++i) {
ir_node *in = get_irn_n(a, i);
- if (my_values_interfere(birg, in, b))
+ if (my_values_interfere(irg, in, b))
return 1;
}
return 0;
for (i = 0; i < arity; ++i) {
ir_node *in = get_irn_n(b, i);
/* a is not a sync, so no need for my_values_interfere */
- if (my_values_interfere2(birg, a, in))
+ if (my_values_interfere2(irg, a, in))
return 1;
}
return 0;
}
- return my_values_interfere2(birg, a, b);
+ return my_values_interfere2(irg, a, b);
}
/**
memset(spilllist, 0, spillcount * sizeof(spilllist[0]));
);
- for (spill = set_first(env->spills), i = 0; spill != NULL;
- spill = set_next(env->spills), ++i) {
+ i = 0;
+ foreach_set(env->spills, spill_t*, spill) {
assert(spill->spillslot < spillcount);
spilllist[spill->spillslot] = spill;
+ ++i;
}
for (i = 0; i < spillcount; ++i) {
if (is_NoMem(spill2))
continue;
- if (my_values_interfere(env->birg, spill1, spill2)) {
+ if (my_values_interfere(env->irg, spill1, spill2)) {
DB((dbg, DBG_INTERFERENCES,
"Slot %d and %d interfere\n", i, i2));
-typedef struct _spill_slot_t {
+typedef struct spill_slot_t {
int size;
int align;
ir_entity *entity;
} spill_slot_t;
-typedef struct _memperm_entry_t {
+typedef struct memperm_entry_t {
ir_node* node;
int pos;
ir_entity *in;
ir_entity *out;
- struct _memperm_entry_t *next;
+ struct memperm_entry_t *next;
} memperm_entry_t;
-typedef struct _memperm_t {
+typedef struct memperm_t {
ir_node *block;
int entrycount;
memperm_entry_t *entries;
static int cmp_memperm(const void* d1, const void* d2, size_t size)
{
- const memperm_t* e1 = d1;
- const memperm_t* e2 = d2;
+ const memperm_t* e1 = (const memperm_t*)d1;
+ const memperm_t* e2 = (const memperm_t*)d2;
(void) size;
return e1->block != e2->block;
entry.block = block;
hash = hash_irn(block);
- res = set_find(env->memperms, &entry, sizeof(entry), hash);
+ res = (memperm_t*)set_find(env->memperms, &entry, sizeof(entry), hash);
if (res == NULL) {
entry.entrycount = 0;
entry.entries = NULL;
- res = set_insert(env->memperms, &entry, sizeof(entry), hash);
+ res = (memperm_t*)set_insert(env->memperms, &entry, sizeof(entry), hash);
}
return res;
static ir_entity* create_stack_entity(be_fec_env_t *env, spill_slot_t *slot)
{
- ir_graph *irg = be_get_birg_irg(env->birg);
- ir_type *frame = get_irg_frame_type(irg);
- /* TODO: backend should be able to specify wether we want spill slots
- * at begin or end of frame */
- int at_start = 1;
- ir_entity *res = frame_alloc_area(frame, slot->size, slot->align, at_start);
+ ir_graph *irg = env->irg;
+ ir_type *frame = get_irg_frame_type(irg);
+ ir_entity *res = frame_alloc_area(frame, slot->size, slot->align,
+ env->at_begin);
/* adjust size of the entity type... */
ir_type *enttype = get_entity_type(res);
}
}
-
-static void assign_spill_entity(ir_node *node, ir_entity *entity)
+static void assign_spill_entity(be_fec_env_t *env,
+ ir_node *node, ir_entity *entity)
{
if (is_NoMem(node))
return;
ir_node *in = get_irn_n(node, i);
assert(!is_Phi(in));
- assign_spill_entity(in, entity);
+ assign_spill_entity(env, in, entity);
}
return;
}
instance */
node = skip_Proj(node);
assert(arch_get_frame_entity(node) == NULL);
- arch_set_frame_entity(node, entity);
+ env->set_frame_entity(node, entity);
}
/**
int spillcount = set_count(env->spills);
spill_slot_t *spillslots = ALLOCANZ(spill_slot_t, spillcount);
spill_t *spill;
- int i;
+ size_t i;
/* construct spillslots */
- for (spill = set_first(env->spills); spill != NULL;
- spill = set_next(env->spills)) {
-
+ foreach_set(env->spills, spill_t*, spill) {
int slotid = spill->spillslot;
const ir_mode *mode = spill->mode;
spill_slot_t *slot = & (spillslots[slotid]);
}
}
- for (spill = set_first(env->spills); spill != NULL;
- spill = set_next(env->spills)) {
-
+ foreach_set(env->spills, spill_t*, spill) {
ir_node *node = spill->spill;
int slotid = spill->spillslot;
spill_slot_t *slot;
}
}
} else {
- assign_spill_entity(node, slot->entity);
+ assign_spill_entity(env, node, slot->entity);
}
}
assert(slot->entity != NULL);
- arch_set_frame_entity(reload, slot->entity);
+ env->set_frame_entity(reload, slot->entity);
}
}
static void create_memperms(be_fec_env_t *env)
{
- const arch_env_t *arch_env = env->arch_env;
- ir_graph *irg = be_get_birg_irg(env->birg);
memperm_t *memperm;
- for (memperm = set_first(env->memperms); memperm != NULL; memperm = set_next(env->memperms)) {
+ foreach_set(env->memperms, memperm_t*, memperm) {
ir_node **nodes = ALLOCAN(ir_node*, memperm->entrycount);
memperm_entry_t *entry;
ir_node *blockend;
nodes[i] = arg;
}
- mempermnode = be_new_MemPerm(arch_env, memperm->block,
- memperm->entrycount, nodes);
+ mempermnode = be_new_MemPerm(memperm->block, memperm->entrycount,
+ nodes);
/* insert node into schedule */
blockend = get_end_of_block_insertion_point(memperm->block);
be_set_MemPerm_in_entity(mempermnode, i, entry->in);
be_set_MemPerm_out_entity(mempermnode, i, entry->out);
- set_irg_current_block(irg, memperm->block);
- proj = new_Proj(mempermnode, get_irn_mode(arg), i);
+ proj = new_r_Proj(mempermnode, get_irn_mode(arg), i);
set_irn_n(entry->node, entry->pos, proj);
}
int slotcount;
slotcount = 0;
- for (spill = set_first(env->spills); spill != NULL;
- spill = set_next(env->spills)) {
+ foreach_set(env->spills, spill_t*, spill) {
int spillslot = spill->spillslot;
if (!bitset_is_set(counted, spillslot)) {
slotcount++;
return slotcount;
}
-be_fec_env_t *be_new_frame_entity_coalescer(be_irg_t *birg)
+be_fec_env_t *be_new_frame_entity_coalescer(ir_graph *irg)
{
- const arch_env_t *arch_env = birg->main_env->arch_env;
- be_fec_env_t *env = XMALLOC(be_fec_env_t);
+ be_fec_env_t *env = XMALLOCZ(be_fec_env_t);
- be_liveness_assure_chk(be_assure_liveness(birg));
+ be_liveness_assure_chk(be_assure_liveness(irg));
obstack_init(&env->obst);
- env->arch_env = arch_env;
- env->birg = birg;
+ env->irg = irg;
env->spills = new_set(cmp_spill, 10);
env->reloads = NEW_ARR_F(ir_node*, 0);
env->affinity_edges = NEW_ARR_F(affinity_edge_t*, 0);
free(env);
}
-void be_assign_entities(be_fec_env_t *env)
+void be_assign_entities(be_fec_env_t *env,
+ set_frame_entity_func set_frame_entity,
+ bool alloc_entities_at_begin)
{
+ env->set_frame_entity = set_frame_entity;
+ env->at_begin = alloc_entities_at_begin;
+
stat_ev_dbl("spillslots", set_count(env->spills));
if (be_coalesce_spill_slots) {
create_memperms(env);
}
-/**
- * This walker function searches for reloads and collects all the spills
- * and memphis attached to them.
- */
-static void collect_spills_walker(ir_node *node, void *data)
-{
- be_fec_env_t *env = data;
- const ir_mode *mode;
- const arch_register_class_t *cls;
- int align;
-
- if (! (arch_irn_classify(node) & arch_irn_class_reload))
- return;
-
- mode = get_irn_mode(node);
- cls = arch_get_irn_reg_class_out(node);
- align = arch_env_get_reg_class_alignment(env->arch_env, cls);
-
- be_node_needs_frame_entity(env, node, mode, align);
-}
-
-void be_coalesce_spillslots(be_irg_t *birg)
-{
- be_fec_env_t *env = be_new_frame_entity_coalescer(birg);
-
- /* collect reloads */
- irg_walk_graph(birg->irg, NULL, collect_spills_walker, env);
-
- be_assign_entities(env);
-
- be_free_frame_entity_coalescer(env);
-}
-
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots);
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillslots)
void be_init_spillslots(void)
{
FIRM_DBG_REGISTER(dbg, "firm.be.spillslots");
projects / libfirm / blobdiff