-/* src/vm/optimizing/ssa3.c
+/* src/vm/jit/optimizing/ssa3.c
Copyright (C) 2008
CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
* Unify access to phi args.
*/
-#include "vm/jit/jit.h"
+
+#include "config.h"
+
+#include "vm/jit/jit.hpp"
#include "vm/global.h"
-#include "mm/memory.h"
-#include "mm/dumpmemory.h"
-#include "toolbox/list.h"
+#include "mm/memory.hpp"
+#include "mm/dumpmemory.hpp"
+#include "toolbox/list.hpp"
#include <limits.h>
#include <stdio.h>
-#define ELIMINATE_NOP_LOAD_STORE
+/*#define ELIMINATE_NOP_LOAD_STORE*/
#define FIXME(x) x
#define SSA_VERIFY
-/* #define SSA_VERBOSE */
+/*#define SSA_VERBOSE */
/*
__attribute__((always_inline))
/*** vars *******************************************************************/
-#define VARS_CATEGORY_SHIFT 29
-#define VARS_INDEX_MASK 0x1FFFFFFF
+#define VARS_CATEGORY_SHIFT 28
+#define VARS_INDEX_MASK 0x0FFFFFFF
#define VARS_CATEGORY_LOCAL 0
#define VARS_CATEGORY_STACK 1
#define VAR_TYPE_SUBSTITUED 666
+#define OLD_INDEX_UNUSED -2
+
typedef struct {
- varinfo items[9000]; /* XXX hardcoded max */
+ varinfo v;
+ s4 old_index;
+} vars_item_t;
+
+typedef struct {
+ vars_item_t items[9000]; /* XXX hardcoded max */
unsigned max;
unsigned count;
unsigned category;
unsigned i = vs->count;
assert(i < vs->max);
vs->count += 1;
- vs->items[i] = *item;
+ vs->items[i].v = *item;
+ vs->items[i].old_index = OLD_INDEX_UNUSED;
return (vs->category << VARS_CATEGORY_SHIFT) | i;
}
static inline varinfo *vars_back(vars_t *vs) {
assert(vs->count > 0);
- return vs->items + (vs->count - 1);
+ return &(vs->items[vs->count - 1].v);
}
static inline void vars_init(vars_t *vs, unsigned category) {
varindex = vars_get_index(varindex);
replacementindex = vars_get_index(replacementindex);
- vs->items[varindex].type = VAR_TYPE_SUBSTITUED;
- vs->items[varindex].vv.regoff = replacementindex;
+ vs->items[varindex].v.type = VAR_TYPE_SUBSTITUED;
+ vs->items[varindex].v.vv.ii[1] = replacementindex;
}
static unsigned vars_resolve_subst(const vars_t *vs, unsigned varindex) {
#endif
varindex = vars_get_index(varindex);
- if (vs->items[varindex].type == VAR_TYPE_SUBSTITUED) /*fprintf(stderr, "*")*/;
+ if (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) /*fprintf(stderr, "*")*/;
- while (vs->items[varindex].type == VAR_TYPE_SUBSTITUED) {
+ while (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) {
assert(loop_ctr++ != vs->count);
- varindex = vs->items[varindex].vv.regoff;
+ varindex = vs->items[varindex].v.vv.ii[1];
}
return (vs->category << VARS_CATEGORY_SHIFT) | varindex ;
}
static void vars_copy_to_final(vars_t *vs, varinfo *dst) {
- const varinfo *it;
+ const vars_item_t *it;
unsigned subst;
for (it = vs->items; it != vs->items + vs->count; ++it, ++dst) {
/* Copy variable. */
- *dst = *it;
+ *dst = it->v;
/* Eliminate VAR_TYPE_SUBSTITUED as it leads to problems. */
if (dst->type == VAR_TYPE_SUBSTITUED) {
subst = vars_get_index(vars_resolve_subst(vs, it - vs->items));
- dst->type = vs->items[subst].type;
+ dst->type = vs->items[subst].v.type;
}
}
}
+static void vars_import(vars_t *vs, varinfo *v, unsigned count, s4 old_index) {
+ vars_item_t *it;
+
+ assert((vs->count + count) <= vs->max);
+
+ it = vs->items + vs->count;
+ vs->count += count;
+
+ while (count-- > 0) {
+ it->v = *v;
+ it->old_index = old_index;
+ it += 1;
+ v += 1;
+ old_index += 1;
+ }
+}
+
+static inline void vars_record_old_index(vars_t *vs, unsigned varindex, s4 old_index) {
+ vars_item_t *item;
+ varindex = vars_get_index(varindex);
+
+ assert(varindex < vs->count);
+
+ item = vs->items + varindex;
+
+ assert(
+ item->old_index == OLD_INDEX_UNUSED ||
+ item->old_index == old_index
+ );
+
+ item->old_index = old_index;
+}
+
+static inline s4 vars_get_old_index(vars_t *vs, unsigned varindex) {
+ s4 old;
+
+ varindex = vars_get_index(varindex);
+
+ assert(varindex < vs->count);
+ old = vs->items[varindex].old_index;
+ assert(old != OLD_INDEX_UNUSED);
+
+ return old;
+}
/*** phis *******************************************************************/
}
#endif
-static inline void phis_copy_to(const phis_t *ps, instruction *dst) {
- MCOPY(
- dst,
- ps->items,
- instruction,
- ps->count
- );
+static inline unsigned phis_copy_to(const phis_t *ps, instruction *dst) {
+ instruction *it;
+ instruction *out = dst;
+
+ FOR_EACH_PHI_FUNCTION(ps, it) {
+ *(out++) = *it;
+ }
+
+ return (out - dst);
}
/*** state_array ************************************************************/
state_array_set(t->state_array, index, phi);
+ vars_record_old_index(v, phi->dst.varindex, index);
+
return phi;
}
static void traversal_rename_def(traversal_t *t, vars_t *vars, instruction *iptr) {
const varinfo *v;
unsigned index;
+ s4 old;
state_array_assert_items(t->state_array);
v = t->ops->var_num_to_varinfo(t->ops_vp, iptr->dst.varindex);
index = t->ops->var_num_to_index(t->ops_vp, iptr->dst.varindex);
+ old = iptr->dst.varindex;
iptr->dst.varindex = vars_add_item(vars, v);
state_array_set(t->state_array, index, iptr);
+
+ vars_record_old_index(vars, iptr->dst.varindex, index);
}
-static void traversal_rename_use(traversal_t *t, s4 *puse) {
+static void traversal_rename_use(traversal_t *t, vars_t *vars, s4 *puse) {
unsigned index;
+ s4 old;
state_array_assert_items(t->state_array);
index = t->ops->var_num_to_index(t->ops_vp, *puse);
assert(state_array_get(t->state_array, index));
+ old = *puse;
*puse = state_array_get_var(t->state_array, index);
+
+ vars_record_old_index(vars, *puse, index);
}
static inline unsigned traversal_variables_count(traversal_t *t) {
basicblock_chain_t *new_blocks;
+ struct {
+ s4 maxlocals;
+ s4 maxinterfaces;
+ s4 *local_map;
+ varinfo *var;
+ s4 vartop;
+ s4 varcount;
+ s4 localcount;
+ } original;
+
+ unsigned keep_in_out:1;
+
} ssa_info, ssa_info_t;
void ssa_info_init(ssa_info_t *ssa, jitdata *jd) {
vars_init(ssa->locals, VARS_CATEGORY_LOCAL);
/* Initialize first version of locals, that is always available. */
- MCOPY(ssa->locals->items, jd->var, varinfo, jd->localcount);
- ssa->locals->count = jd->localcount;
+ vars_import(ssa->locals, jd->var, jd->localcount, 0);
ssa->stack = DNEW(vars_t);
vars_init(ssa->stack, VARS_CATEGORY_STACK);
ssa->new_blocks = DNEW(basicblock_chain_t);
basicblock_chain_init(ssa->new_blocks);
+
+ ssa->original.maxlocals = jd->maxlocals;
+ ssa->original.maxinterfaces = jd->maxinterfaces;
+ ssa->original.local_map = jd->local_map;
+ ssa->original.var = jd->var;
+ ssa->original.vartop = jd->vartop;
+ ssa->original.varcount = jd->varcount;
+ ssa->original.localcount = jd->localcount;
+
+ ssa->keep_in_out = false;
}
/*** others_mapping *********************************************************/
static inline void others_mapping_set(ssa_info *ssa, s4 var, s4 new_var) {
- ssa->jd->var[var].vv.regoff = new_var;
+ ssa->jd->var[var].vv.ii[1] = new_var;
}
static inline s4 others_mapping_get(const ssa_info *ssa, s4 var) {
- return ssa->jd->var[var].vv.regoff;
+ return ssa->jd->var[var].vv.ii[1];
}
/*** code *******************************************************************/
basicblock_chain_t chain;
basicblock *last = NULL;
basicblock *marker = NULL;
+ s4 vartop;
+ unsigned i;
if (jd->exceptiontablelength == 0) {
return;
basicblock_chain_init(&chain);
- /* We need to allocate new iovars */
-
- avail_vars = (jd->varcount - jd->vartop);
- add_vars = jd->exceptiontablelength;
+ /* Remember, where we started adding IO variables. */
- if (add_vars > avail_vars) {
- add_vars -= avail_vars;
- jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, jd->varcount + add_vars);
- jd->varcount += add_vars;
- }
+ vartop = jd->vartop;
/* For each exception handler block, create one block with a prologue block */
FOR_EACH_BASICBLOCK(jd, bptr) {
if (bptr->type == BBTYPE_EXH) {
+ /*
+
+ +---- EXH (exh)-------+
+ | in0 in1 in2 exc |
+ | ..... |
+ +---------------------+
+
+ === TRANSFORMED TO ===>
+
+ +---- PROL (exh) -------+
+ | in0 in1 in2 |
+ | GETEXECEPTION => OU3 |
+ | GOTO REAL_EXH |
+ | in0 in1 in2 OU3 |
+ +-----------------------+
+
+ +---- REAL_EXH (std) -+
+ | in0 in1 in2 exc |
+ | ...... |
+ +---------------------+
+
+ */
+
bptr->type = BBTYPE_STD;
bptr->predecessorcount = 0; /* legacy */
iptr = DMNEW(instruction, 2);
MZERO(iptr, instruction, 2);
+
+ /* Create outvars */
+
+ exh->outdepth = bptr->indepth;
+ if (exh->outdepth > 0) {
+ exh->outvars = DMNEW(s4, exh->outdepth);
+ for (i = 0; i < exh->outdepth; ++i) {
+ exh->outvars[i] = vartop++;
+ }
+ }
+
+ /* Create invars */
+
+ exh->indepth = exh->outdepth - 1;
+ exh->invars = exh->outvars;
+
+#if 0
/* Create new outvar */
assert(jd->vartop < jd->varcount);
jd->vartop += 1;
jd->var[v].type = TYPE_ADR;
jd->var[v].flags = INOUT;
+#endif
exh->nr = jd->basicblockcount;
jd->basicblockcount += 1;
exh->type = BBTYPE_EXH;
exh->icount = 2;
exh->iinstr = iptr;
+/*
exh->outdepth = 1;
exh->outvars = DNEW(s4);
exh->outvars[0] = v;
+*/
exh->predecessorcount = -1; /* legacy */
exh->flags = BBFINISHED;
exh->method = jd->m;
/* Get exception */
iptr->opc = ICMD_GETEXCEPTION;
- iptr->dst.varindex = v;
+ iptr->dst.varindex = exh->outvars[exh->outdepth - 1];
iptr += 1;
/* Goto real exception handler */
}
}
+ /* We need to allocate the new iovars in the var array */
+
+ avail_vars = (jd->varcount - jd->vartop);
+ add_vars = (vartop - jd->vartop);
+
+ if (add_vars > avail_vars) {
+ add_vars -= avail_vars;
+ jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, jd->varcount + add_vars);
+ jd->varcount += add_vars;
+ }
+
+ jd->vartop = vartop;
+
/* Put the chain of exception handlers between just before the last
basic block (end marker). */
for (ee = jd->exceptiontable; ee; ee = ee->down) {
assert(ee->handler->vp);
- ee->handler = ee->handler->vp;
+
+ bptr = ee->handler;
+ exh = (basicblock *)ee->handler->vp;
+
+ ee->handler = exh;
+
+ /* Set up IO variables in newly craeted exception handlers. */
+
+ for (i = 0; i < exh->outdepth; ++i) {
+ v = exh->outvars[i];
+
+ jd->var[v].flags = INOUT;
+ jd->var[v].type = jd->var[ bptr->invars[i] ].type;
+ }
+ }
+
+}
+
+void unfix_exception_handlers(jitdata *jd) {
+ basicblock *bptr, *exh;
+ unsigned i;
+ exception_entry *ee;
+#if !defined(NDEBUG)
+ bool found = false;
+#endif
+
+ FOR_EACH_BASICBLOCK(jd, bptr) {
+ if (bptr->type == BBTYPE_EXH) {
+ assert(bptr->iinstr[1].opc == ICMD_GOTO);
+ exh = bptr->iinstr[1].dst.block;
+
+ bptr->type = BBDELETED;
+ bptr->icount = 0;
+ bptr->indepth = 0;
+ bptr->outdepth = 0;
+ exh->type = BBTYPE_EXH;
+ bptr->vp = exh;
+
+ /* bptr is no more a predecessor of exh */
+
+ for (i = 0; i < exh->predecessorcount; ++i) {
+ if (exh->predecessors[i] == bptr) {
+ exh->predecessors[i] = exh->predecessors[exh->predecessorcount - 1];
+ exh->predecessorcount -= 1;
+#if !defined(NDEBUG)
+ found = true;
+#endif
+ break;
+ }
+ }
+
+ assert(found);
+
+ } else {
+ bptr->vp = NULL;
+ }
}
+ for (ee = jd->exceptiontable; ee; ee = ee->down) {
+ assert(ee->handler->vp);
+ ee->handler = ee->handler->vp;
+ }
}
/*** ssa_enter ***************************************************************/
basicblock *bptr;
basicblock_info_t *bbi;
instruction *itph;
+
+ /* XXX */
+ return;
+
FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
if (basicblock_reached(bptr)) {
bbi = bb_info(bptr);
basicblock_get_ex_predecessor_index(bb, pei, *itsucc),
ssa->locals
);
+
+ ssa_enter_merge(
+ bbi->stack,
+ succi->stack,
+ *itsucc,
+ basicblock_get_ex_predecessor_index(bb, pei, *itsucc),
+ ssa->stack
+ );
}
}
instruction *itph;
bool ret = false;
+ /* XXX */
+ return;
+
FOR_EACH_PHI_FUNCTION(t->phis, itph) {
phi_calculate_redundancy(itph);
state_array_allocate_items(bbi->stack->state_array);
}
+#if 0
/* Exception handlers have a clean stack. */
+ /* Not true with inlining. */
+
if (bb->type == BBTYPE_EXH) {
state_array_assert_no_items(bbi->stack->state_array);
state_array_allocate_items(bbi->stack->state_array);
}
+#endif
/* Some in/out vars get marked as INOUT in simplereg,
and are not marked at this point.
Mark them manually. */
for (ituse = bb->invars; ituse != bb->invars + bb->indepth; ++ituse) {
+ if (ssa->keep_in_out && ssa->jd->var[*ituse].type == TYPE_RET) {
+ continue;
+ }
ssa->jd->var[*ituse].flags |= INOUT;
ssa->jd->var[*ituse].flags &= ~PREALLOC;
}
for (ituse = bb->outvars; ituse != bb->outvars + bb->outdepth; ++ituse) {
+ if (ssa->keep_in_out && ssa->jd->var[*ituse].type == TYPE_RET) {
+ continue;
+ }
ssa->jd->var[*ituse].flags |= INOUT;
ssa->jd->var[*ituse].flags &= ~PREALLOC;
}
if (var_is_local(ssa->jd, *ituse)) {
traversal_rename_use(
bbi->locals,
+ ssa->locals,
ituse
);
} else if (var_is_inout(ssa->jd, *ituse)) {
traversal_rename_use(
bbi->stack,
+ ssa->stack,
ituse
);
} else {
ssa->others,
ssa->jd->var + iptr->dst.varindex
);
+ vars_record_old_index(ssa->others, iptr->dst.varindex, old);
others_mapping_set(ssa, old, iptr->dst.varindex);
}
}
s4 *it;
unsigned i, j;
jitdata *jd = ssa->jd;
+ s4 *local_map;
vartop = ssa->locals->count + ssa->stack->count + ssa->others->count;
vars = DMNEW(varinfo, vartop);
/* Grow local map to accomodate all new locals and iovars.
But keep the local map for version 1 of locals, that contains the holes. */
- jd->local_map = DMREALLOC(
- jd->local_map,
- s4,
- 5 * jd->maxlocals,
+ local_map = DMNEW(
+ s4,
5 * (jd->maxlocals + ssa->locals->count + ssa->stack->count - jd->localcount)
);
+ MCOPY(local_map, jd->local_map, s4, 5 * jd->maxlocals);
+
+ jd->local_map = local_map;
+
it = jd->local_map + (jd->maxlocals * 5); /* start adding entries here */
/* Add version > 1 of all locals */
FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
bbi = bb_info(bptr);
if (bbi != NULL) {
- bptr->phicount =
- bbi->locals->phis->count +
- bbi->stack->phis->count;
-
- bptr->phis = DMNEW(instruction, bptr->phicount);
+ bptr->phis = DMNEW(instruction, bbi->locals->phis->count + bbi->stack->phis->count);
dst = bptr->phis;
- phis_copy_to(bbi->locals->phis, dst);
+ dst += phis_copy_to(bbi->locals->phis, dst);
- dst += bbi->locals->phis->count;
+ dst += phis_copy_to(bbi->stack->phis, dst);
- phis_copy_to(bbi->stack->phis, dst);
+ bptr->phicount = dst - bptr->phis;
}
}
}
bbi = bb_info(bb);
- bb->indepth = 0;
- bb->outdepth = 0;
+ if (! ssa->keep_in_out) {
+ bb->indepth = 0;
+ bb->outdepth = 0;
+ }
if (bbi != NULL) {
FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
}
}
+void ssa_simple_leave_restore(ssa_info_t *ssa, basicblock *bptr, s4 *pvar) {
+ s4 var = *pvar;
+ s4 index;
+ basicblock_info_t *bbi;
+
+ if (var < ssa->locals->count) {
+ *pvar = vars_get_old_index(ssa->locals, var);
+ } else if (var < ssa->locals->count + ssa->stack->count) {
+
+ index = vars_get_old_index(
+ ssa->stack,
+ var - ssa->locals->count
+ );
+
+ bbi = bb_info(bptr);
+
+ /* We have to determine whether to take an invar or an outvar for
+ the stack depth ``index''.
+ The state array contains the last definition of the stack element
+ at the given depth.
+ */
+
+ if (state_array_get_var(bbi->stack->state_array, index) == var) {
+ /* The last definition of a stack depth inside the basicblock.
+ This is the outvar at the given depth.
+ If there is no outvar at the given depth, it must be an invar.
+ */
+ if (index < bptr->outdepth) {
+ *pvar = bptr->outvars[index];
+ } else if (index < bptr->indepth) {
+ *pvar = bptr->invars[index];
+ } else {
+ assert(0);
+ }
+ } else {
+ /* A different than the last definition of a stack depth.
+ This must be an invar.
+ */
+ assert(index < bptr->indepth);
+ *pvar = bptr->invars[index];
+ }
+ } else {
+ *pvar = vars_get_old_index(
+ ssa->others,
+ var - ssa->locals->count - ssa->stack->count
+ );
+ }
+}
+
+void ssa_simple_leave(ssa_info_t *ssa) {
+ basicblock *bptr;
+ instruction *iptr;
+ s4 *ituse, *uses;
+ unsigned uses_count;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+ if (bptr->type == BBTYPE_EXH) {
+ /* (Aritifical) exception handler blocks will be eliminated. */
+ continue;
+ }
+ /* In reverse order. We need to rename the definition after any use! */
+ FOR_EACH_INSTRUCTION_REV(bptr, iptr) {
+ if (instruction_has_dst(iptr)) {
+ ssa_simple_leave_restore(ssa, bptr, &(iptr->dst.varindex));
+ }
+ instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
+ for (ituse = uses; ituse != uses + uses_count; ++ituse) {
+ ssa_simple_leave_restore(ssa, bptr, ituse);
+ }
+ instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
+ }
+ bptr->phicount = 0;
+ }
+
+ unfix_exception_handlers(ssa->jd);
+
+ ssa->jd->maxlocals = ssa->original.maxlocals;
+ ssa->jd->maxinterfaces = ssa->original.maxinterfaces;
+ ssa->jd->local_map =ssa->original.local_map;
+ ssa->jd->var = ssa->original.var;
+ ssa->jd->vartop = ssa->original.vartop;
+ ssa->jd->varcount = ssa->original.varcount;
+ ssa->jd->localcount = ssa->original.localcount;
+}
+
+#include "vm/rt-timing.h"
+
void yssa(jitdata *jd) {
basicblock *it;
basicblock_info_t *iti;
ssa_info *ssa;
+ struct timespec bs, es, be, ee;
+
+ RT_TIMING_GET_TIME(bs);
+
#ifdef SSA_VERBOSE
- printf("=============== [ before %s ] =========================\n", jd->m->name->text);
- show_method(jd, 3);
- printf("=============== [ /before ] =========================\n");
+ bool verb = true;
+ if (verb) {
+ printf("=============== [ before %s ] =========================\n", jd->m->name->text);
+ show_method(jd, 3);
+ printf("=============== [ /before ] =========================\n");
+ }
#endif
ssa = DNEW(ssa_info);
ssa_info_init(ssa, jd);
+ ssa->keep_in_out = true;
FOR_EACH_BASICBLOCK(jd, it) {
if (basicblock_reached(it)) {
/*ssa_enter_create_phi_graph(ssa);*/
+ RT_TIMING_GET_TIME(be);
escape_analysis_perform(ssa->jd);
+ RT_TIMING_GET_TIME(ee);
+ /*
ssa_leave_create_phi_moves(ssa);
ssa_leave_create_exceptional_phi_moves(ssa);
+ */
+
+#ifdef SSA_VERBOSE
+ if (verb) {
+ printf("=============== [ mid ] =========================\n");
+ show_method(jd, 3);
+ printf("=============== [ /mid ] =========================\n");
+ }
+#endif
+
+ ssa_simple_leave(ssa);
#ifdef SSA_VERBOSE
- printf("=============== [ after ] =========================\n");
- show_method(jd, 3);
- printf("=============== [ /after ] =========================\n");
+ if (verb) {
+ printf("=============== [ after ] =========================\n");
+ show_method(jd, 3);
+ printf("=============== [ /after ] =========================\n");
+ }
#endif
+ RT_TIMING_GET_TIME(es);
+
+ RT_TIMING_TIME_DIFF(bs, es, RT_TIMING_1);
+ RT_TIMING_TIME_DIFF(be, ee, RT_TIMING_2);
}
void eliminate_subbasicblocks(jitdata *jd) {
projects / cacao.git / blobdiff