TODO
- * Adapt for exception handling
- * Eliminiation of redundand PHI functions
+ * Adapt for exception handling [done]
+ * Eliminiation of redundand PHI functions. [in progress]
+ * Handle also inout variables. [done]
* Create PHI functions lazyly, when they are used for the first time
(I suspect that currently PHIs are created that are never used).
+ * REWRITE. The code was never designed for producion. [done]
+ * Unify access to phi args.
*/
#include "vm/jit/jit.h"
#include "mm/dumpmemory.h"
#include "toolbox/list.h"
-#if 1
-#define printf(...) do { if (getenv("VERB")) printf(__VA_ARGS__); } while (0)
-#define show_method(...) do { if (getenv("VERB")) show_method(__VA_ARGS__); } while (0)
-#endif
+#include <limits.h>
+#include <stdio.h>
+
+/*#define ELIMINATE_NOP_LOAD_STORE*/
+#define FIXME(x) x
+#define SSA_VERIFY
+/*#define SSA_VERBOSE */
/*
-TODO
-move set and get uses into jit.h
+__attribute__((always_inline))
*/
-#define ICMD_PHI 666
+/*** phi ********************************************************************/
-static inline const char *instruction_name(const instruction *iptr) {
- if (iptr->opc == ICMD_PHI) {
- return "phi";
- } else {
- return icmd_table[iptr->opc].name;
- }
+typedef enum {
+ PHI_FLAG_USED,
+ PHI_FLAG_REDUNDANT_ALL,
+ PHI_FLAG_REDUNDANT_ONE
+} phi_flags_t;
+
+static inline void phi_set_flag(instruction *iptr, phi_flags_t flag) {
+ iptr->flags.bits |= (1 << flag);
}
-typedef struct phi_function {
- s4 dst;
- s4 *args;
- s4 local;
- instruction instr;
-} phi_function;
+static inline void phi_clear_flag(instruction *iptr, phi_flags_t flag) {
+ iptr->flags.bits &= ~(1 << flag);
+}
-typedef struct basicblock_info {
- bool visited;
- bool active;
- unsigned backward_branches;
+static inline bool phi_has_flag(const instruction *iptr, phi_flags_t flag) {
+ return (iptr->flags.bits & (1 << flag)) != 0;
+}
- instruction **state_array;
+static inline instruction *phi_get_subst(instruction *iptr) {
+ return iptr->sx.s23.s2.iargs[-1];
+}
- unsigned phi_count;
- phi_function *phi_functions;
-} basicblock_info;
+static inline bool phi_has_subst(const instruction *iptr) {
+ return (iptr->sx.s23.s2.iargs[-1] != NULL);
+}
-typedef struct ssa_info {
- jitdata *jd;
- varinfo locals[3000]; /* XXX hardcoded max */
- unsigned max_locals;
- unsigned locals_count;
+static inline void phi_init(instruction *iptr, unsigned argcount, s4 index) {
+ unsigned i;
- s4 s_buf[3];
-} ssa_info;
+ iptr->opc = ICMD_PHI;
+ iptr->flags.bits = 0;
+ iptr->dst.varindex = 0;
+ iptr->s1.argcount = argcount;
+ iptr->sx.s23.s2.iargs = DMNEW(instruction *, argcount + 1);
+ iptr->sx.s23.s2.iargs += 1;
+ iptr->sx.s23.s3.javaindex = index;
+
+ /* subst field - If non-null, the phi function shall be replaced by the
+ value produced by the subst instruction. */
+ iptr->sx.s23.s2.iargs[-1] = NULL;
+
+#if !defined(NDEBUG)
+ for (i = 0; i < argcount; ++i) {
+ iptr->sx.s23.s2.iargs[i] = (instruction *)0x7fffffff;
+ }
+#endif
+}
+
+#define phi_assert_opc(iptr) assert(iptr->opc == ICMD_PHI)
-static inline basicblock_info *bb_info(basicblock *bb) {
- return (basicblock_info *)(bb->vp);
+#define phi_assert_arg(iptr, arg) assert(arg < iptr->s1.argcount)
+
+static inline s4 phi_arg_count(const instruction *iptr) {
+ phi_assert_opc(iptr);
+ return iptr->s1.argcount;
}
-static void mark_loops(basicblock *bb) {
- basicblock_info *bbi = bb_info(bb);
- basicblock **itsucc;
+static inline instruction *phi_get_arg(const instruction *iptr, unsigned arg) {
+ phi_assert_opc(iptr);
+ phi_assert_arg(iptr, arg);
+ return iptr->sx.s23.s2.iargs[arg];
+}
- if (! bbi->visited) {
- bbi->visited = true;
- bbi->active = true;
- FOR_EACH_SUCCESSOR(bb, itsucc) {
- mark_loops(*itsucc);
- }
- bbi->active = false;
- } else if (bbi->active) {
- bbi->backward_branches += 1;
+static inline s4 phi_get_arg_var(const instruction *iptr, unsigned arg) {
+ phi_assert_opc(iptr);
+ phi_assert_arg(iptr, arg);
+ return iptr->sx.s23.s2.iargs[arg]->dst.varindex;
+}
+
+static inline void phi_set_all_args(instruction *iptr, instruction *value) {
+ unsigned i;
+ phi_assert_opc(iptr);
+ for (i = 0; i < iptr->s1.argcount; ++i) {
+ iptr->sx.s23.s2.iargs[i] = value;
}
}
-typedef void (*traverse_fun)(ssa_info *ssa, basicblock *bb);
+static inline s4 phi_get_index(const instruction *iptr) {
+ phi_assert_opc(iptr);
+ return iptr->sx.s23.s3.javaindex;
+}
-static void traverse(ssa_info *ssa, basicblock *bb, traverse_fun fun) {
- basicblock **itsucc, **itpred;
- unsigned complete_preds;
+static inline s4 phi_get_dst(const instruction *iptr) {
+ phi_assert_opc(iptr);
+ return iptr->dst.varindex;
+}
- /* Process block */
+static inline void phi_set_dst(instruction *iptr, s4 dst) {
+ phi_assert_opc(iptr);
+ iptr->dst.varindex = dst;
+}
- fun(ssa, bb);
+static inline bool phi_get_used(const instruction *iptr) {
+ phi_assert_opc(iptr);
+ return phi_has_flag(iptr, PHI_FLAG_USED);
+}
- /* Recurse */
+static void phi_set_used(instruction *iptr) {
+ phi_assert_opc(iptr);
+ if (! phi_has_flag(iptr, PHI_FLAG_USED)) {
+ phi_set_flag(iptr, PHI_FLAG_USED);
+ /* TODO recurse into arguments */
+ }
+}
- FOR_EACH_SUCCESSOR(bb, itsucc) {
- complete_preds = 0;
- FOR_EACH_PREDECESSOR(*itsucc, itpred) {
- if (bb_info(*itpred)->state_array) {
- complete_preds += 1;
+static instruction *phi_resolve_use(instruction *use) {
+ if (use != NULL) {
+ while (use->opc == ICMD_PHI) {
+ if (phi_has_subst(use)) {
+ use = phi_get_subst(use);
+ } else {
+ break;
}
}
- if (complete_preds == ((*itsucc)->predecessorcount - bb_info(*itsucc)->backward_branches)) {
- printf(" *** Traverse bb%d => bb%d\n", bb->nr, (*itsucc)->nr);
- traverse(ssa, *itsucc, fun);
- }
}
+ return use;
+}
+
+static inline void phi_set_arg(instruction *iptr, unsigned arg, instruction *value) {
+ phi_assert_opc(iptr);
+ phi_assert_arg(iptr, arg);
+ assert(value != NULL);
+ iptr->sx.s23.s2.iargs[arg] = value;
+}
+static inline bool phi_is_redundant(const instruction *iptr) {
+ return (
+ phi_has_flag(iptr, PHI_FLAG_REDUNDANT_ONE) ||
+ phi_has_flag(iptr, PHI_FLAG_REDUNDANT_ALL)
+ );
}
-static instruction *create_phi(ssa_info *ssa, basicblock *bb, s4 local) {
- basicblock_info *bbi = bb_info(bb);
- phi_function *phi;
+static inline void phi_create_copy(instruction *iptr, unsigned arg, instruction *copy) {
+ phi_assert_opc(iptr);
+ phi_assert_arg(iptr, arg);
+ copy->dst.varindex = phi_get_dst(iptr);
+ copy->s1.varindex = phi_resolve_use(phi_get_arg(iptr, arg))->dst.varindex;
+ if (copy->dst.varindex == copy->s1.varindex || phi_is_redundant(iptr)) {
+ copy->opc = ICMD_NOP;
+ } else {
+ copy->opc = ICMD_COPY;
+ }
+}
- printf(" *** BB%d phi for local %d\n", bb->nr, local);
+#if !defined(NDEBUG)
+static void phi_print(const instruction *iptr) {
+ unsigned i;
+ instruction *use;
+ printf("%d = phi(", iptr->dst.varindex);
+ for (i = 0; i < iptr->s1.argcount; ++i) {
+ use = phi_resolve_use(iptr->sx.s23.s2.iargs[i]);
+ if (use) {
+ printf("%d, ", use->dst.varindex);
+ } else {
+ printf("null, ");
+ }
+ }
+ printf(")\n");
+}
+#endif
- phi = bbi->phi_functions + bbi->phi_count;
- bbi->phi_count += 1;
+#define FOR_EACH_PHI_USE_CAST(iptr, it, cast) \
+ for ( \
+ (it) = cast (iptr)->sx.s23.s2.iargs; \
+ (it) != cast (iptr)->sx.s23.s2.iargs + (iptr)->s1.argcount; \
+ ++(it) \
+ )
- phi->local = local;
- phi->args = DMNEW(s4, bb->predecessorcount);
+#define FOR_EACH_PHI_USE(iptr, it) \
+ FOR_EACH_PHI_USE_CAST(iptr, it, )
- assert(ssa->locals_count < ssa->max_locals);
- ssa->locals[ssa->locals_count] = ssa->jd->var[local];
- phi->dst = ssa->locals_count;
- ssa->locals_count += 1;
+#define FOR_EACH_PHI_USE_CONST(iptr, it) \
+ FOR_EACH_PHI_USE_CAST(iptr, it, (const instruction *))
- phi->instr.opc = ICMD_PHI;
- phi->instr.dst.varindex = phi->dst;
- phi->instr.s1.argcount = bb->predecessorcount;
- phi->instr.sx.s23.s2.args = phi->args;
+static void phi_calculate_redundancy(instruction *iptr) {
- return &(phi->instr);
-}
+ s4 dst = iptr->dst.varindex;
+ s4 use;
+ instruction *iuse;
+ instruction **ituse;
+ unsigned num_different = 0;
+ instruction *different;
-static void rename_def(ssa_info *ssa, basicblock *bptr, instruction *iptr) {
- basicblock_info *bbi = bb_info(bptr);
- assert(bbi->state_array);
+ if (phi_is_redundant(iptr)) return; /* XXX */
- bbi->state_array[iptr->dst.varindex] = iptr;
+ /* x = phi(x, y, x, x) ... PHI_FLAG_REDUNDANT_ONE
+ x = phi(x, x, x, x) ... PHI_FLAG_REDUNDANT_ALL */
- assert(ssa->locals_count < ssa->max_locals);
+ FOR_EACH_PHI_USE(iptr, ituse) {
+ iuse = phi_resolve_use(*ituse);
+ assert(iuse);
- ssa->locals[ssa->locals_count] = ssa->jd->var[iptr->dst.varindex];
- iptr->dst.varindex = ssa->locals_count;
- printf(" *** BB%d %s def %d => %d\n", bptr->nr, instruction_name(iptr), iptr->dst.varindex, ssa->locals_count);
+ use = iuse->dst.varindex;
- ssa->locals_count += 1;
-}
+ if (use != dst) {
+ different = *ituse;
+ num_different += 1;
+ if (num_different >= 2) {
+ phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
+ phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
+ }
+ }
+ }
-static void rename_use(ssa_info *ssa, basicblock *bptr, instruction *iptr, s4 *use) {
- basicblock_info *bbi = bb_info(bptr);
- assert(bbi->state_array);
+ if (num_different == 1) {
+ /* Set the subst field of the instruction.
+ I.e. the instruction will be replaced by the value produced by y. */
+ iptr->sx.s23.s2.iargs[-1] = different;
- if (bbi->state_array[*use] != NULL) {
- printf(" *** BB%d %s use %d => %d (%s) \n", bptr->nr, instruction_name(iptr), *use, bbi->state_array[*use]->dst.varindex, instruction_name(bbi->state_array[*use]) );
- *use = bbi->state_array[*use]->dst.varindex;
- } else {
- printf(" *** BB%d %s use keep\n", bptr->nr, instruction_name(iptr));
+ phi_set_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
+ phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
+ } else if (num_different == 0) {
+ assert(0);
+ /*iptr->sx.s23.s2.iargs[-1] = iptr->sx.s23.s2.iargs[0];*/
+
+ phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
+ phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
+ /*assert(0);*/
}
}
-static void get_uses(ssa_info *ssa, instruction *iptr, s4 **puses, unsigned *puses_count) {
+
+/*** goto *******************************************************************/
+
+static inline void goto_init(instruction *iptr, basicblock *dst) {
+ iptr->opc = ICMD_GOTO;
+ iptr->dst.block = dst;
+}
+
+/*** instruction ***********************************************************/
+
+static void instruction_get_uses(const instruction *iptr, s4 *buf, s4 **puses, unsigned *puses_count) {
unsigned uses_count = 0;
switch (icmd_table[iptr->opc].dataflow) {
case DF_3_TO_0:
case DF_3_TO_1:
- ssa->s_buf[2] = iptr->sx.s23.s3.varindex;
+ buf[2] = iptr->sx.s23.s3.varindex;
uses_count += 1;
case DF_2_TO_0:
case DF_2_TO_1:
- ssa->s_buf[1] = iptr->sx.s23.s2.varindex;
+ buf[1] = iptr->sx.s23.s2.varindex;
uses_count += 1;
case DF_1_TO_0:
case DF_1_TO_1:
case DF_COPY:
case DF_MOVE:
- ssa->s_buf[0] = iptr->s1.varindex;
+ buf[0] = iptr->s1.varindex;
uses_count += 1;
*puses_count = uses_count;
- *puses = ssa->s_buf;
+ *puses = buf;
break;
case DF_N_TO_1:
}
}
-static void set_uses(ssa_info *ssa, instruction *iptr, s4 *uses, unsigned uses_count) {
- if (uses == ssa->s_buf) {
+static inline void instruction_set_uses(instruction *iptr, s4 *buf, s4 *uses, unsigned uses_count) {
+ if (uses == buf) {
switch (uses_count) {
case 3:
- iptr->sx.s23.s3.varindex = ssa->s_buf[2];
+ iptr->sx.s23.s3.varindex = buf[2];
case 2:
- iptr->sx.s23.s2.varindex = ssa->s_buf[1];
+ iptr->sx.s23.s2.varindex = buf[1];
case 1:
- iptr->s1.varindex = ssa->s_buf[0];
+ iptr->s1.varindex = buf[0];
}
}
}
-static void traverse_fun_impl(ssa_info *ssa, basicblock *bb) {
- basicblock_info *bbi = bb_info(bb), *predi;
- basicblock **itpred, *pred;
- unsigned i;
- bool need_phi;
- instruction *iptr;
- unsigned uses_count;
- s4 *uses, *ituse;
-
- if (bbi->state_array) {
- return;
- }
+/*** vars *******************************************************************/
- if (bb->predecessorcount == 0) {
- bbi->state_array = DMNEW(instruction *, ssa->jd->localcount);
- MZERO(bbi->state_array, instruction *, ssa->jd->localcount);
- goto process_instructions;
- }
+#define VARS_CATEGORY_SHIFT 28
+#define VARS_INDEX_MASK 0x0FFFFFFF
- if ((bb->predecessorcount == 1) && (bb->predecessors[0]->successorcount == 1)) {
- bbi->state_array = bb_info(bb->predecessors[0])->state_array;
- assert(bbi->state_array);
- goto process_instructions;
- }
+#define VARS_CATEGORY_LOCAL 0
+#define VARS_CATEGORY_STACK 1
+#define VARS_CATEGORY_OTHERS 2
- bbi->state_array = DMNEW(instruction *, ssa->jd->localcount);
- MZERO(bbi->state_array, instruction *, ssa->jd->localcount);
+#define VAR_TYPE_SUBSTITUED 666
- if (bbi->backward_branches > 0) {
- for (i = 0; i < ssa->jd->localcount; ++i) {
- bbi->state_array[i] = create_phi(ssa, bb, i);
- }
- } else {
- for (i = 0; i < ssa->jd->localcount; ++i) {
- need_phi = false;
- assert(bb_info(bb->predecessors[0])->state_array);
-
- FOR_EACH_PREDECESSOR(bb, itpred) {
- assert(bb_info(*itpred)->state_array);
- if (bb_info(bb->predecessors[0])->state_array[i] != bb_info(*itpred)->state_array[i]) {
- need_phi = true;
- break;
- }
- }
+#define OLD_INDEX_UNUSED -2
- if (need_phi) {
- bbi->state_array[i] = create_phi(ssa, bb, i);
- } else {
- bbi->state_array[i] = bb_info(bb->predecessors[0])->state_array[i];
- }
+typedef struct {
+ varinfo v;
+ s4 old_index;
+} vars_item_t;
- }
- }
+typedef struct {
+ vars_item_t items[9000]; /* XXX hardcoded max */
+ unsigned max;
+ unsigned count;
+ unsigned category;
+} vars_t;
-process_instructions:
+static inline unsigned vars_add_item(vars_t *vs, const varinfo *item) {
+ unsigned i = vs->count;
+ assert(i < vs->max);
+ vs->count += 1;
+ vs->items[i].v = *item;
+ vs->items[i].old_index = OLD_INDEX_UNUSED;
+ return (vs->category << VARS_CATEGORY_SHIFT) | i;
+}
- FOR_EACH_INSTRUCTION(bb, iptr) {
+static inline unsigned vars_add(vars_t *vs) {
+ unsigned i = vs->count;
+ assert(i < vs->max);
+ vs->count += 1;
+ return (vs->category << VARS_CATEGORY_SHIFT) | i;
+}
- get_uses(ssa, iptr, &uses, &uses_count);
+static inline varinfo *vars_back(vars_t *vs) {
+ assert(vs->count > 0);
+ return &(vs->items[vs->count - 1].v);
+}
- for (ituse = uses; ituse != uses + uses_count; ++ituse) {
- if (var_is_local(ssa->jd, *ituse)) {
- rename_use(ssa, bb, iptr, ituse);
- } else {
- *ituse += 0xFFFF;
- }
- }
+static inline void vars_init(vars_t *vs, unsigned category) {
+ vs->max = sizeof(vs->items) / sizeof(vs->items[0]);
+ vs->count = 0;
+ assert((category & 0x3) == category);
+ vs->category = category;
+}
- set_uses(ssa, iptr, uses, uses_count);
+static inline unsigned vars_get_category(unsigned varindex) {
+ return (varindex >> VARS_CATEGORY_SHIFT);
+}
- if (instruction_has_dst(iptr)) {
- if (var_is_local(ssa->jd, iptr->dst.varindex)) {
- rename_def(ssa, bb, iptr);
- } else {
- iptr->dst.varindex += 0xFFFF;
- }
- }
+static inline unsigned vars_get_index(unsigned varindex) {
+ return (varindex & VARS_INDEX_MASK);
+}
+
+static void vars_subst(vars_t *vs, unsigned varindex, unsigned replacementindex) {
+ varindex = vars_get_index(varindex);
+ replacementindex = vars_get_index(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) {
+#if !defined(NDEBUG)
+ unsigned loop_ctr = 0;
+#endif
+ varindex = vars_get_index(varindex);
+
+ if (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) /*fprintf(stderr, "*")*/;
+
+ while (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) {
+ assert(loop_ctr++ != vs->count);
+ varindex = vs->items[varindex].v.vv.ii[1];
}
+
+ return (vs->category << VARS_CATEGORY_SHIFT) | varindex ;
}
-static void ssa_rename_others(ssa_info *ssa) {
+static void vars_copy_to_final(vars_t *vs, varinfo *dst) {
+ const vars_item_t *it;
+ unsigned subst;
- basicblock *bb;
- instruction *iptr;
- s4 *itinout, *uses, *ituse;
- unsigned uses_count;
- unsigned off = ssa->locals_count - ssa->jd->localcount;
+ for (it = vs->items; it != vs->items + vs->count; ++it, ++dst) {
- FOR_EACH_BASICBLOCK(ssa->jd, bb) {
+ /* Copy variable. */
- if (! basicblock_reached(bb)) continue;
+ *dst = it->v;
- for (itinout = bb->invars; itinout != bb->invars + bb->indepth; ++itinout) {
- *itinout += off;
- }
+ /* Eliminate VAR_TYPE_SUBSTITUED as it leads to problems. */
- for (itinout = bb->outvars; itinout != bb->outvars + bb->outdepth; ++itinout) {
- *itinout += off;
- }
+ if (dst->type == VAR_TYPE_SUBSTITUED) {
+ subst = vars_get_index(vars_resolve_subst(vs, it - vs->items));
+ dst->type = vs->items[subst].v.type;
- FOR_EACH_INSTRUCTION(bb, iptr) {
- if (instruction_has_dst(iptr)) {
- if (iptr->dst.varindex >= 0xFFFF) {
- iptr->dst.varindex += off;
- iptr->dst.varindex -= 0xFFFF;
- }
- }
- get_uses(ssa, iptr, &uses, &uses_count);
- for (ituse = uses; ituse != uses + uses_count; ++ituse) {
- if (*ituse >= 0xFFFF) {
- *ituse += off;
- *ituse -= 0xFFFF;
- }
- }
- set_uses(ssa, iptr, uses, uses_count);
}
}
}
-static void fill_in_phi_args(ssa_info *ssa) {
- basicblock *bb;
- basicblock_info *bbi;
- phi_function *itphi;
- unsigned j;
- basicblock **itpred;
- basicblock_info *predi;
+static void vars_import(vars_t *vs, varinfo *v, unsigned count, s4 old_index) {
+ vars_item_t *it;
- FOR_EACH_BASICBLOCK(ssa->jd, bb) {
- if (!(bb->flags >= BBREACHED)) continue;
- bbi = bb_info(bb);
- j = 0;
- FOR_EACH_PREDECESSOR(bb, itpred) {
- predi = bb_info(*itpred);
- for (itphi = bbi->phi_functions; itphi != bbi->phi_functions + bbi->phi_count; ++itphi) {
- if (predi->state_array[itphi->local]) {
- itphi->args[j] = predi->state_array[itphi->local]->dst.varindex;
- } else {
- itphi->args[j] = itphi->local;
- }
- }
- ++j;
- }
+ 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 void ssa_export(ssa_info *ssa) {
- unsigned i, j;
- jitdata *jd = ssa->jd;
- varinfo *vars, *it;
- s4 vartop, varindex;
+static inline void vars_record_old_index(vars_t *vs, unsigned varindex, s4 old_index) {
+ vars_item_t *item;
+ varindex = vars_get_index(varindex);
- vartop = ssa->locals_count + jd->vartop - jd->localcount;
- vars = DMNEW(varinfo, vartop);
+ assert(varindex < vs->count);
- MCOPY(vars, ssa->locals, varinfo, ssa->locals_count);
- MCOPY(vars + ssa->locals_count, jd->var + jd->localcount, varinfo, jd->vartop - jd->localcount);
+ item = vs->items + varindex;
- jd->var = vars;
- jd->vartop = jd->varcount = vartop;
+ assert(
+ item->old_index == OLD_INDEX_UNUSED ||
+ item->old_index == old_index
+ );
- jd->local_map = DMREALLOC(jd->local_map, s4, 5 * jd->maxlocals, 5 * (jd->maxlocals + ssa->locals_count - jd->localcount));
+ item->old_index = old_index;
+}
- for (i = 0; i < ssa->locals_count - jd->localcount; ++i) {
- for (j = 0; j < 5; ++j) {
- varindex = jd->localcount + i;
- if (jd->var[varindex].type != j) {
- varindex = UNUSED;
- }
- jd->local_map[((jd->maxlocals + i) * 5) + j] = varindex;
- }
- }
+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);
- jd->maxlocals += (ssa->locals_count - jd->localcount);
- jd->localcount = ssa->locals_count;
+ return old;
}
-static unsigned get_predecessor_index(basicblock *from, basicblock *to) {
- basicblock **itpred;
- unsigned j = 0;
+/*** phis *******************************************************************/
- for (itpred = to->predecessors; itpred != to->predecessors + to->predecessorcount; ++itpred) {
- if (*itpred == from) break;
- j++;
- }
-
- if (j == to->predecessorcount) {
- assert(j != to->predecessorcount);
- }
+typedef struct {
+ instruction *items;
+ unsigned max;
+ unsigned count;
+} phis_t;
- return j;
+static inline void phis_init(phis_t *ps, unsigned max) {
+ ps->max = max;
+ ps->count = 0;
+ ps->items = DMNEW(instruction, max);
}
-static basicblock *create_block(ssa_info *ssa, basicblock *from, basicblock *to) {
- basicblock *mid;
- basicblock_info *toi;
- instruction *iptr;
- phi_function *itph;
- unsigned j = get_predecessor_index(from, to);
-
- mid = DNEW(basicblock);
- MZERO(mid, basicblock, 1);
+static inline instruction *phis_add(phis_t *ps) {
+ unsigned i = ps->count;
+ assert(i < ps->max);
+ ps->count += 1;
+ return ps->items + i;
+}
- toi = bb_info(to);
- assert(toi);
+static inline instruction *phis_get(const phis_t *ps, unsigned i) {
+ assert(i < ps->count);
+ return ps->items + i;
+}
- mid->nr = ssa->jd->basicblockcount;
- ssa->jd->basicblockcount += 1;
- mid->mpc = -1;
- mid->type = 666;
- mid->icount = toi->phi_count + 1;
- iptr = mid->iinstr = DMNEW(instruction, mid->icount);
- MZERO(mid->iinstr, instruction, mid->icount);
+static inline bool phis_contains(const phis_t *ps, const instruction *phi) {
+ return (ps->items <= phi) && (phi < (ps->items + ps->max));
+}
- for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
- iptr->opc = ICMD_COPY;
- iptr->dst.varindex = itph->dst;
- iptr->s1.varindex = itph->args[j];
- assert(itph->dst < ssa->locals_count);
- assert(itph->args[j] < ssa->locals_count);
- iptr++;
+#define FOR_EACH_PHI_FUNCTION_(ps, it) \
+ for ((it) = (ps)->items; (it) != (ps)->items + (ps)->count; ++(it)) \
+
+#define FOR_EACH_PHI_FUNCTION(ps, it) \
+ FOR_EACH_PHI_FUNCTION_(ps, it) if (!phi_is_redundant((it)))
+
+#if !defined(NDEBUG)
+FIXME() inline void phis_print(const phis_t *ps) {
+ const instruction *iptr;
+ FOR_EACH_PHI_FUNCTION(ps, iptr) {
+ phi_print(iptr);
}
+}
+#endif
- iptr->opc = ICMD_GOTO;
- iptr->dst.block = to;
+static inline unsigned phis_copy_to(const phis_t *ps, instruction *dst) {
+ instruction *it;
+ instruction *out = dst;
- while (from->next) {
- from = from->next;
+ FOR_EACH_PHI_FUNCTION(ps, it) {
+ *(out++) = *it;
}
- from->next = mid;
+ return (out - dst);
+}
+
+/*** state_array ************************************************************/
+
+typedef struct {
+ instruction **items;
+ unsigned count;
+} state_array_t;
- return mid;
+static inline void state_array_init(state_array_t *sa, unsigned count) {
+ sa->items = NULL;
+ sa->count = count;
}
-static void crate_fallthrough(ssa_info *ssa, basicblock *bptr) {
- unsigned j;
- basicblock_info *toi;
- instruction *iptr;
- phi_function *itph;
+static inline bool state_array_has_items(const state_array_t *sa) {
+ return (sa->items != NULL);
+}
- if (bptr->next == NULL) return;
+static inline s4 state_array_get_var(const state_array_t *sa, unsigned index) {
+ assert(index < sa->count);
+ assert(sa->items[index]);
+ return sa->items[index]->dst.varindex;
+}
- j = get_predecessor_index(bptr, bptr->next);
+static inline instruction *state_array_get(const state_array_t *sa, unsigned index) {
+ assert(index < sa->count);
+ return sa->items[index];
+}
- toi = bb_info(bptr->next);
- assert(toi);
+static inline void state_array_set(const state_array_t *sa, unsigned index, instruction *value) {
+ assert(index < sa->count);
+ sa->items[index] = value;
+}
- bptr->iinstr = DMREALLOC(bptr->iinstr, instruction, bptr->icount, bptr->icount + toi->phi_count);
- iptr = bptr->iinstr + bptr->icount;
- bptr->icount += toi->phi_count;
+static inline void state_array_copy(state_array_t *sa, state_array_t *other) {
+ assert(sa->count == other->count);
+ MCOPY(sa->items, other->items, instruction *, sa->count);
+}
- for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
- iptr->opc = ICMD_COPY;
- iptr->dst.varindex = itph->dst;
- iptr->s1.varindex = itph->args[j];
- assert(itph->dst < ssa->locals_count);
- assert(itph->args[j] < ssa->locals_count);
- iptr++;
- }
+#define state_array_assert_items(sa) assert(state_array_has_items(sa) || (sa->count == 0))
+#define state_array_assert_no_items(sa) assert(! state_array_has_items(sa))
+static inline void state_array_allocate_items(state_array_t *sa) {
+ sa->items = DMNEW(instruction *, sa->count);
+ MZERO(sa->items, instruction *, sa->count);
}
-static void ssa_create_phi_moves(ssa_info *ssa) {
- basicblock *bptr;
- instruction *iptr;
+/*** basicblock_chain *******************************************************/
- s4 i, l;
- branch_target_t *table;
- lookup_target_t *lookup;
- bool gt;
+typedef struct {
+ basicblock *first;
+ basicblock *last;
+} basicblock_chain_t;
- for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
- if (bptr->type == 666) {
- bptr->type = BBTYPE_STD;
- continue;
- }
- if (! bptr->vp) continue;
- if (! (bptr->flags >= BBREACHED)) continue;
- gt = false;
- for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
- switch (icmd_table[iptr->opc].controlflow) {
- case CF_IF:
- case CF_RET:
- case CF_GOTO:
- iptr->dst.block = create_block(ssa, bptr, iptr->dst.block);
- break;
- case CF_TABLE:
- table = iptr->dst.table;
- l = iptr->sx.s23.s2.tablelow;
- i = iptr->sx.s23.s3.tablehigh;
- i = i - l + 1;
- i += 1; /* default */
- while (--i >= 0) {
- table->block = create_block(ssa, bptr, table->block);
- ++table;
- }
- break;
- case CF_LOOKUP:
- lookup = iptr->dst.lookup;
- i = iptr->sx.s23.s2.lookupcount;
- while (--i >= 0) {
- lookup->target.block = create_block(ssa, bptr, lookup->target.block);
- lookup++;
- }
- iptr->sx.s23.s3.lookupdefault.block = create_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
- break;
- case CF_JSR:
- iptr->sx.s23.s3.jsrtarget.block = create_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
- break;
- }
- if ((iptr->opc == ICMD_GOTO) || icmd_table[iptr->opc].controlflow == CF_END)
- gt = true;
- else if (iptr->opc != ICMD_NOP)
- gt = false;
- }
- if (! bptr->next) continue;
- if (! (bptr->next->flags >= BBREACHED)) continue;
- if (bptr->next->type == 666) continue;
- if (!gt) crate_fallthrough(ssa, bptr);
+static void basicblock_chain_init(basicblock_chain_t *bbc) {
+ bbc->first = NULL;
+ bbc->last = NULL;
+}
+
+#define basicblock_chain_clear basicblock_chain_init
+
+static void basicblock_chain_add(basicblock_chain_t *bbc, basicblock *bb) {
+ if (bbc->first == NULL) {
+ assert(bbc->last == NULL);
+ assert(bb->next == NULL);
+ bbc->first = bb;
+ bbc->last = bb;
+ } else {
+ assert(bbc->last->next == NULL);
+ bbc->last->next = bb;
+ bbc->last = bb;
}
}
-void yssa(jitdata *jd) {
- basicblock *it;
- basicblock_info *iti;
- ssa_info *ssa;
+static inline basicblock *basicblock_chain_front(basicblock_chain_t *bbc) {
+ assert(bbc->first);
+ return bbc->first;
+}
- printf("=============== [ before %s ] =========================\n", jd->m->name->text);
- show_method(jd, 3);
- printf("=============== [ /before ] =========================\n");
+static inline basicblock *basicblock_chain_back(basicblock_chain_t *bbc) {
+ assert(bbc->last);
+ return bbc->last;
+}
- ssa = DNEW(ssa_info);
- ssa->jd = jd;
- ssa->max_locals = sizeof(ssa->locals) / sizeof(ssa->locals[0]);
- MCOPY(ssa->locals, jd->var, varinfo, jd->localcount);
- ssa->locals_count = jd->localcount;
+static inline bool basicblock_chain_empty(const basicblock_chain_t *bbc) {
+ return bbc->first == NULL;
+}
- FOR_EACH_BASICBLOCK(jd, it) {
- if (basicblock_reached(it)) {
- iti = DNEW(basicblock_info);
- MZERO(iti, basicblock_info, 1);
- if (jd->localcount > 0) {
- iti->phi_functions = DMNEW(phi_function, jd->localcount);
- }
- it->vp = iti;
- } else {
- it->vp = NULL;
- }
+/*** exception_entry_chain ***************************************************/
+
+typedef struct {
+ exception_entry *first;
+ exception_entry *last;
+} exception_entry_chain_t;
+
+static void exception_entry_chain_init(exception_entry_chain_t *eec) {
+ eec->first = NULL;
+ eec->last = NULL;
+}
+
+#define exception_entry_chain_clear exception_entry_chain_init
+
+static void exception_entry_chain_add(exception_entry_chain_t *eec, exception_entry *ee) {
+ if (eec->first == NULL) {
+ eec->first = ee;
+ eec->last = ee;
+ } else {
+ eec->last->next = ee;
+ eec->last->down = ee;
+ eec->last = ee;
}
+}
+
+static inline bool exception_entry_chain_empty(const exception_entry_chain_t *eec) {
+ return eec->first == NULL;
+}
+
+static inline exception_entry *exception_entry_chain_back(exception_entry_chain_t *eec) {
+ assert(eec->last);
+ return eec->last;
+}
+
+static inline exception_entry *exception_entry_chain_front(exception_entry_chain_t *eec) {
+ assert(eec->first);
+ return eec->first;
+}
- mark_loops(jd->basicblocks);
+/*** traversal **************************************************************/
- traverse(ssa, jd->basicblocks, traverse_fun_impl);
+typedef struct {
+ unsigned (*var_num_to_index)(void *vp, s4 var);
+ varinfo *(*index_to_initial_var)(void *vp, unsigned index);
+ varinfo *(*var_num_to_varinfo)(void *vp, s4 var);
+ unsigned (*variables_count)(void *vp);
+} traversal_ops_t;
- ssa_rename_others(ssa);
+typedef struct {
+ phis_t *phis;
+ state_array_t *state_array;
+ void *ops_vp;
+ traversal_ops_t *ops;
+} traversal_t;
- fill_in_phi_args(ssa);
+/*** basicblock_info ********************************************************/
- ssa_export(ssa);
+typedef struct basicblock_info {
+ bool visited;
+ bool active;
+ bool traversed;
+ unsigned backward_branches;
- ssa_create_phi_moves(ssa);
+ traversal_t *locals;
+ traversal_t *stack;
- printf("=============== [ after ] =========================\n");
- show_method(jd, 3);
- printf("=============== [ /after ] =========================\n");
+ basicblock_chain_t *subbasicblocks;
+
+ unsigned complete_predecessors;
+
+#if defined(SSA_VERIFY)
+ unsigned num_phi_elimination;
+#endif
+
+} basicblock_info_t;
+
+/*** traversal **************************************************************/
+
+void traversal_init(traversal_t *t, unsigned count, void *ops_vp, traversal_ops_t *ops) {
+ t->phis = DNEW(phis_t);
+ phis_init(t->phis, count);
+
+ t->state_array = DNEW(state_array_t);
+ state_array_init(t->state_array, count);
+
+ t->ops_vp = ops_vp;
+ t->ops = ops;
+}
+
+instruction *traversal_create_phi(traversal_t *t, vars_t *v, unsigned argcount, s4 index) {
+ instruction *phi = phis_add(t->phis);
+ s4 dst;
+
+ phi_init(phi, argcount, index);
+ dst = vars_add_item(v, t->ops->index_to_initial_var(t->ops_vp, index));
+ phi_set_dst(phi, dst);
+
+ 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, 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) {
+ return t->ops->variables_count(t->ops_vp);
+}
+
+unsigned local_var_num_to_index(void *vp, s4 var) {
+ return (unsigned)var;
+}
+
+varinfo *local_index_to_initial_var(void *vp, unsigned index) {
+ jitdata *jd = (jitdata *)vp;
+ return jd->var + index;
+}
+
+varinfo *local_var_num_to_varinfo(void *vp, s4 var) {
+ jitdata *jd = (jitdata *)vp;
+ return jd->var + var;
+}
+
+unsigned local_variables_count(void *vp) {
+ jitdata *jd = (jitdata *)vp;
+ return jd->localcount;
+}
+
+traversal_ops_t traversal_local_ops = {
+ local_var_num_to_index,
+ local_index_to_initial_var,
+ local_var_num_to_varinfo,
+ local_variables_count
+};
+
+unsigned inout_var_num_to_index(void *vp, s4 var) {
+ basicblock *bb = (basicblock *)vp;
+ unsigned i;
+
+ for (i = 0; i < bb->indepth; ++i) {
+ if (bb->invars[i] == var) {
+ return i;
+ }
+ }
+
+ for (i = 0; i < bb->outdepth; ++i) {
+ if (bb->outvars[i] == var) {
+ return i;
+ }
+ }
+
+ assert(0);
+}
+
+varinfo *inout_index_to_initial_var(void *vp, unsigned index) {
+ basicblock *bb = (basicblock *)vp;
+ jitdata *jd = (jitdata *)(((basicblock_info_t *)bb->vp)->locals->ops_vp); /* evil hack */
+ assert(index < bb->indepth);
+ return jd->var + bb->invars[index];
+}
+
+varinfo *inout_var_num_to_varinfo(void *vp, s4 var) {
+ basicblock *bb = (basicblock *)vp;
+ jitdata *jd = (jitdata *)(((basicblock_info_t *)bb->vp)->locals->ops_vp); /* evil hack */
+ return jd->var + var;
+}
+
+unsigned inout_variables_count(void *vp) {
+ basicblock *bb = (basicblock *)vp;
+ return bb->indepth;
+}
+
+traversal_ops_t traversal_inout_ops = {
+ inout_var_num_to_index,
+ inout_index_to_initial_var,
+ inout_var_num_to_varinfo,
+ inout_variables_count
+};
+
+/*** basicblock_info ********************************************************/
+
+void basicblock_info_init(basicblock_info_t *bbi, basicblock *bb, jitdata *jd) {
+ MZERO(bbi, basicblock_info_t, 1);
+
+ bbi->locals = DNEW(traversal_t);
+ traversal_init(bbi->locals, jd->localcount, jd, &traversal_local_ops);
+
+ bbi->stack = DNEW(traversal_t);
+ traversal_init(bbi->stack, jd->maxinterfaces, bb, &traversal_inout_ops);
+
+ bbi->subbasicblocks = DNEW(basicblock_chain_t);
+ basicblock_chain_init(bbi->subbasicblocks);
+}
+
+/*** basicblock *************************************************************/
+
+static inline basicblock_info_t *basicblock_info(basicblock *bb) {
+ return (basicblock_info_t *)(bb->vp);
+}
+
+#define bb_info basicblock_info
+
+static unsigned basicblock_get_predecessor_count(basicblock *bb) {
+ unsigned ret;
+ basicblock **itpred;
+
+ ret = bb->predecessorcount;
+
+ FOR_EACH_EXPREDECESSOR(bb, itpred) {
+ ret += (*itpred)->exouts;
+ }
+
+ return ret;
+}
+
+static unsigned basicblock_get_predecessor_index(basicblock *from, basicblock *to) {
+ basicblock **itpred;
+ unsigned j = 0;
+
+ FOR_EACH_PREDECESSOR(to, itpred) {
+ if (*itpred == from) break;
+ j++;
+ }
+
+ assert(j != to->predecessorcount);
+
+ return j;
+}
+
+static unsigned basicblock_get_ex_predecessor_index(basicblock *from, unsigned pei, basicblock *to) {
+ unsigned j;
+ basicblock **itpred;
+
+ j = to->predecessorcount;
+
+ FOR_EACH_EXPREDECESSOR(to, itpred) {
+ if ((*itpred)->nr == from->nr) {
+ j += pei;
+ return j;
+ } else {
+ j += (*itpred)->exouts;
+ }
+ }
+
+ assert(0);
+}
+
+/*** ssa_info ***************************************************************/
+
+typedef struct ssa_info {
+ jitdata *jd;
+
+ vars_t *locals;
+ vars_t *stack;
+ vars_t *others;
+
+ s4 s_buf[3];
+
+ 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) {
+ ssa->jd = jd;
+
+ ssa->locals = DNEW(vars_t);
+ vars_init(ssa->locals, VARS_CATEGORY_LOCAL);
+
+ /* Initialize first version of locals, that is always available. */
+ vars_import(ssa->locals, jd->var, jd->localcount, 0);
+
+ ssa->stack = DNEW(vars_t);
+ vars_init(ssa->stack, VARS_CATEGORY_STACK);
+
+ ssa->others = DNEW(vars_t);
+ vars_init(ssa->others, VARS_CATEGORY_OTHERS);
+
+ 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.ii[1] = new_var;
+}
+
+static inline s4 others_mapping_get(const ssa_info *ssa, s4 var) {
+ return ssa->jd->var[var].vv.ii[1];
+}
+
+/*** code *******************************************************************/
+
+void fix_exception_handlers(jitdata *jd) {
+ basicblock *bptr;
+ basicblock *exh = NULL;
+ instruction *iptr;
+ exception_entry *ee;
+ size_t add_vars;
+ size_t avail_vars;
+ s4 v;
+ basicblock_chain_t chain;
+ basicblock *last = NULL;
+ basicblock *marker = NULL;
+ s4 vartop;
+ unsigned i;
+
+ if (jd->exceptiontablelength == 0) {
+ return;
+ }
+
+ basicblock_chain_init(&chain);
+
+ /* Remember, where we started adding IO variables. */
+
+ 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 */
+
+ /* Create basicblock with 2 instructions */
+
+ exh = DNEW(basicblock);
+ MZERO(exh, basicblock, 1);
+
+ 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);
+ v = jd->vartop;
+ jd->vartop += 1;
+ jd->var[v].type = TYPE_ADR;
+ jd->var[v].flags = INOUT;
+#endif
+
+ exh->nr = jd->basicblockcount;
+ jd->basicblockcount += 1;
+ exh->mpc = -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;
+
+ basicblock_chain_add(&chain, exh);
+
+ /* Get exception */
+
+ iptr->opc = ICMD_GETEXCEPTION;
+ iptr->dst.varindex = exh->outvars[exh->outdepth - 1];
+ iptr += 1;
+
+ /* Goto real exception handler */
+
+ goto_init(iptr, bptr);
+
+ bptr->vp = exh;
+ } else {
+ bptr->vp = NULL;
+ }
+
+ if (bptr->next == NULL) {
+ marker = bptr;
+ } else {
+ last = bptr;
+ }
+ }
+
+ /* 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). */
+
+ if (! basicblock_chain_empty(&chain)) {
+ marker->nr = jd->basicblockcount;
+ basicblock_chain_back(&chain)->next = marker;
+ last->next = basicblock_chain_front(&chain);
+
+ assert(last->nr + 1 == basicblock_chain_front(&chain)->nr);
+ assert(marker->nr == jd->basicblockcount);
+ }
+
+ /* Replace all exception handlers in exception table with their respective
+ prologue blocks. */
+
+ for (ee = jd->exceptiontable; ee; ee = ee->down) {
+ assert(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 ***************************************************************/
+
+static void ssa_enter_mark_loops_intern(basicblock *bb, unsigned num_branches) {
+ basicblock_info_t *bbi = bb_info(bb);
+ basicblock **itsucc;
+
+ if (! bbi->visited) {
+ bbi->visited = true;
+ bbi->active = true;
+ FOR_EACH_SUCCESSOR(bb, itsucc) {
+ /* There is a single branch from bb into the successor. */
+ ssa_enter_mark_loops_intern(*itsucc, 1);
+ }
+ FOR_EACH_EXHANDLER(bb, itsucc) {
+ /* For exception handler type successors,
+ we count a branch into the exception handler from every PEI. */
+ ssa_enter_mark_loops_intern(*itsucc, bb->exouts);
+ }
+ bbi->active = false;
+ } else if (bbi->active) {
+ bbi->backward_branches += num_branches;
+ }
+}
+
+static inline void ssa_enter_mark_loops(basicblock *bb) {
+ ssa_enter_mark_loops_intern(bb, 1);
+}
+
+static void ssa_enter_merge(
+ traversal_t *src,
+ traversal_t *dst,
+ basicblock *bdst,
+ unsigned predecessor_index,
+ vars_t *vdst
+) {
+
+ basicblock_info_t *dsti = bb_info(bdst);
+ unsigned predecessor_count = basicblock_get_predecessor_count(bdst);
+ instruction *phi;
+ instruction *old;
+ s4 i;
+
+ /* We are merging for the first time into this block. */
+
+ if (! state_array_has_items(dst->state_array)) {
+
+ state_array_allocate_items(dst->state_array);
+
+ if (dsti->backward_branches > 0) {
+ /* Loop header, create phi functions for all variables. */
+ for (i = 0; i < traversal_variables_count(dst); ++i) {
+ phi = traversal_create_phi(dst, vdst, predecessor_count, i);
+ /* No need to init, they will only be filled in later. */
+ }
+ } else {
+ state_array_copy(dst->state_array, src->state_array);
+ return;
+ }
+ }
+
+ /* We are merging another block. */
+
+ /* Process every variable. */
+
+ for (i = 0; i < traversal_variables_count(dst); ++i) {
+ if (dsti->traversed) {
+
+ /* Back edge, all phi functions are already created.
+ We only need to set their arguments. */
+
+ phi_set_arg(
+ phis_get(dst->phis, i),
+ predecessor_index,
+ state_array_get(src->state_array, i)
+ );
+
+ } else if (state_array_get(dst->state_array, i) != state_array_get(src->state_array, i)) {
+
+ /* A different definition of this var reaches the block.
+ We need to create a phi function. */
+
+ if (phis_contains(dst->phis, state_array_get(dst->state_array, i))) {
+ /* There is already a phi function created for this var.
+ No need to create one. */
+ } else {
+ /* Create a new phi function.
+ Set all arguments to old value in state array. */
+ old = state_array_get(dst->state_array, i);
+ phi = traversal_create_phi(dst, vdst, predecessor_count, i);
+ phi_set_all_args(phi, old);
+ }
+
+ /* Set argument of phi function. */
+
+ phi_set_arg(
+ state_array_get(dst->state_array, i),
+ predecessor_index,
+ state_array_get(src->state_array, i)
+ );
+ }
+ }
+}
+
+static void ssa_enter_process_block(ssa_info *ssa, basicblock *bb);
+static bool ssa_enter_eliminate_redundant_phis(traversal_t *t, vars_t *vs, basicblock_info_t *bbi);
+
+#if defined(SSA_VERIFY)
+static void ssa_enter_verify_no_redundant_phis(ssa_info_t *ssa) {
+ basicblock *bptr;
+ basicblock_info_t *bbi;
+ instruction *itph;
+
+ /* XXX */
+ return;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+ if (basicblock_reached(bptr)) {
+ bbi = bb_info(bptr);
+ FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
+ if (! phi_is_redundant(itph)) {
+ phi_calculate_redundancy(itph);
+ assert(! phi_is_redundant(itph));
+ }
+ }
+ FOR_EACH_PHI_FUNCTION(bbi->stack->phis, itph) {
+ if (! phi_is_redundant(itph)) {
+ phi_calculate_redundancy(itph);
+ assert(! phi_is_redundant(itph));
+ }
+ }
+ }
+ }
+}
+#endif
+
+static void ssa_enter_traverse(ssa_info_t *ssa, basicblock *bb) {
+ basicblock **itsucc;
+ basicblock_info_t *succi;
+ basicblock_info_t *bbi = bb_info(bb);
+ unsigned predecessor_count;
+
+ /* Process block */
+
+ ssa_enter_process_block(ssa, bb);
+
+ /* Recurse */
+
+ FOR_EACH_SUCCESSOR(bb, itsucc) {
+
+ succi = bb_info(*itsucc);
+
+ ssa_enter_merge(
+ bbi->locals,
+ succi->locals,
+ *itsucc,
+ basicblock_get_predecessor_index(bb, *itsucc),
+ ssa->locals
+ );
+
+ ssa_enter_merge(
+ bbi->stack,
+ succi->stack,
+ *itsucc,
+ basicblock_get_predecessor_index(bb, *itsucc),
+ ssa->stack
+ );
+
+ succi->complete_predecessors += 1;
+
+ predecessor_count = basicblock_get_predecessor_count(*itsucc);
+
+ if (
+ succi->complete_predecessors ==
+ (predecessor_count - succi->backward_branches)
+ ) {
+ ssa_enter_traverse(ssa, *itsucc);
+ }
+
+ if (
+ (succi->complete_predecessors == predecessor_count) &&
+ (succi->backward_branches > 0)
+ ) {
+#if defined(SSA_VERIFY)
+ assert(succi->num_phi_elimination < 2);
+ succi->num_phi_elimination += 1;
+#endif
+ ssa_enter_eliminate_redundant_phis(succi->locals, ssa->locals, succi);
+ ssa_enter_eliminate_redundant_phis(succi->stack, ssa->stack, succi);
+ }
+ }
+
+ FOR_EACH_EXHANDLER(bb, itsucc) {
+
+ succi = bb_info(*itsucc);
+
+ succi->complete_predecessors += bb->exouts; /* XXX this might be 0 */
+
+ predecessor_count = basicblock_get_predecessor_count(*itsucc);
+
+ if (
+ succi->complete_predecessors ==
+ (predecessor_count - succi->backward_branches)
+ ) {
+ ssa_enter_traverse(ssa, *itsucc);
+ }
+
+ if (
+ (succi->complete_predecessors == predecessor_count) &&
+ (succi->backward_branches > 0)
+ ) {
+#if defined(SSA_VERIFY)
+ assert(succi->num_phi_elimination < 2);
+ succi->num_phi_elimination += 1;
+#endif
+ ssa_enter_eliminate_redundant_phis(succi->locals, ssa->locals, succi);
+ ssa_enter_eliminate_redundant_phis(succi->stack, ssa->stack, succi);
+ }
+
+ }
+
+}
+
+static void ssa_enter_process_pei(ssa_info *ssa, basicblock *bb, unsigned pei) {
+ basicblock_info_t *bbi = bb_info(bb);
+ basicblock_info_t *succi;
+ basicblock **itsucc;
+
+ FOR_EACH_EXHANDLER(bb, itsucc) {
+ succi = bb_info(*itsucc);
+
+ ssa_enter_merge(
+ bbi->locals,
+ succi->locals,
+ *itsucc,
+ 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
+ );
+ }
+}
+
+static FIXME(bool) ssa_enter_eliminate_redundant_phis(traversal_t *t, vars_t *vs, basicblock_info_t *FIXME(bbi)) {
+
+ instruction *itph;
+ bool ret = false;
+
+ /* XXX */
+ return;
+
+ FOR_EACH_PHI_FUNCTION(t->phis, itph) {
+
+ phi_calculate_redundancy(itph);
+
+ /* If the phi function is redundant,
+ make the variable it defines point to the value defined by the substituing
+ instruction. */
+
+ if (phi_is_redundant(itph)) {
+ vars_subst(vs, itph->dst.varindex, phi_get_subst(itph)->dst.varindex);
+ assert(bbi->backward_branches > 0);
+ ret = true;
+ }
+ }
+
+ return ret;
+}
+
+#if 0
+static void ssa_enter_post_eliminate_redundand_phi(
+ ssa_info_t *ssa,
+ instruction *phi,
+ state_array *sa,
+ basicblock *bptr
+) {
+ phi_calculate_redundancy(phi);
+ phi_set_flag(PHI_FLAG_REDUNDANCY_CHECKED);
+
+ /* if redundancy changed and phi function escapes block */
+
+ /* for each successor */
+}
+
+static void ssa_enter_post_eliminate_redundant_phis(ssa_info_t *ssa) {
+ basicblock *bptr;
+ basicblock_info_t *bbi;
+ instruction *itph;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+ bbi = bb_info(bptr);
+
+ if (bbi->backward_branches > 0) {
+ /* Redundant phi functions have the left hand side as operand.
+ This can happen by definition only in loop headers. */
+
+ FOR_EACH_PHI_FUNCTION(bbi->locals, itph) {
+ if (! phi_has_flag(PHI_FLAG_REDUNDANCY_CHECKED)) {
+ /* Calculate redundancy? */
+ /* Changed? */
+ /* If yes recurse? */
+ }
+ }
+
+ FOR_EACH_PHI_FUNCTION(bbi->stack, itph) {
+ }
+ }
+ }
+}
+#endif
+
+static void ssa_enter_init_locals(state_array_t *sa) {
+ unsigned i;
+ instruction *iptr;
+
+ for (i = 0; i < sa->count; ++i) {
+ iptr = DNEW(instruction);
+ iptr->opc = ICMD_NOP;
+ iptr->dst.varindex = i;
+ state_array_set(sa, i, iptr);
+ }
+}
+
+static void ssa_enter_process_block(ssa_info *ssa, basicblock *bb) {
+ basicblock_info_t *bbi = bb_info(bb);
+ instruction *iptr;
+ unsigned pei = 0;
+ s4 *ituse;
+ s4 *uses;
+ unsigned uses_count;
+ s4 old;
+
+ /* Every basic block can be traversed only once. */
+
+ assert(! bbi->traversed);
+ bbi->traversed = true;
+
+ /* The root basicblock needs special treatment. */
+
+ if (bb->predecessorcount == 0 && bb->type != BBTYPE_EXH) {
+ state_array_assert_no_items(bbi->locals->state_array);
+ state_array_allocate_items(bbi->locals->state_array);
+ ssa_enter_init_locals(bbi->locals->state_array);
+
+ state_array_assert_no_items(bbi->stack->state_array);
+ 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;
+ }
+
+ /* Process instructions */
+
+ state_array_assert_items(bbi->locals->state_array);
+
+ FOR_EACH_INSTRUCTION(bb, iptr) {
+
+#if defined(ELIMINATE_NOP_LOAD_STORE)
+
+ /* Kill NOP instructions of the form:
+ LOAD foo => foo
+ STORE foo => foo
+ As they create a lot of unnecessary definitions.
+ For performance, definitely eliminate them. However, keeping them is a
+ good stress test.
+ */
+
+ if (
+ (icmd_table[iptr->opc].dataflow == DF_LOAD) ||
+ (icmd_table[iptr->opc].dataflow == DF_STORE)
+ ) {
+ if (iptr->dst.varindex == iptr->s1.varindex) {
+ iptr->opc = ICMD_NOP;
+ continue;
+ }
+ }
+#endif
+
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
+ ssa_enter_process_pei(ssa, bb, pei++);
+ }
+
+ instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
+
+ for (ituse = uses; ituse != uses + uses_count; ++ituse) {
+ 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 {
+ *ituse = others_mapping_get(ssa, *ituse);
+ }
+ }
+
+ instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
+
+ if (instruction_has_dst(iptr)) {
+ if (var_is_local(ssa->jd, iptr->dst.varindex)) {
+ traversal_rename_def(
+ bbi->locals,
+ ssa->locals,
+ iptr
+ );
+ } else if (var_is_inout(ssa->jd, iptr->dst.varindex)) {
+ traversal_rename_def(
+ bbi->stack,
+ ssa->stack,
+ iptr
+ );
+ } else {
+ old = iptr->dst.varindex;
+ iptr->dst.varindex = vars_add_item(
+ 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);
+ }
+ }
+ }
+}
+
+/*
+
+ [locals.........................][interaces][others]
+ [original locals][version > 1 ]
+ <--------------- new locals --------------->
+*/
+
+static void ssa_enter_export_variables(ssa_info *ssa) {
+ s4 vartop;
+ varinfo *vars;
+ 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);
+
+ vars_copy_to_final(ssa->locals, vars);
+ vars_copy_to_final(ssa->stack, vars + ssa->locals->count);
+ vars_copy_to_final(ssa->others, vars + ssa->locals->count + ssa->stack->count);
+
+ jd->var = vars;
+ jd->vartop = jd->varcount = 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. */
+
+ 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 (i = jd->localcount; i < ssa->locals->count; ++i) {
+ for (j = 0; j < 5; ++j) {
+ if (jd->var[i].type != j) {
+ *it = UNUSED;
+ } else {
+ *it = i;
+ }
+ it += 1;
+ }
+ }
+
+ /* Add all io vars. */
+
+ for (i = ssa->locals->count; i < ssa->locals->count + ssa->stack->count; ++i) {
+ for (j = 0; j < 5; ++j) {
+ if (jd->var[i].type != j) {
+ *it = UNUSED;
+ } else {
+ *it = i;
+ }
+ it += 1;
+ }
+ }
+
+ /* Add locals. */
+
+ jd->maxlocals += (ssa->locals->count + ssa->stack->count - jd->localcount);
+ jd->localcount = ssa->locals->count + ssa->stack->count;
+
+ /* Eliminate interfaces. */
+
+ jd->maxinterfaces = 0;
+
+}
+
+static void ssa_enter_export_phis(ssa_info_t *ssa) {
+ basicblock *bptr;
+ basicblock_info_t *bbi;
+ instruction *dst;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+ bbi = bb_info(bptr);
+ if (bbi != NULL) {
+ bptr->phis = DMNEW(instruction, bbi->locals->phis->count + bbi->stack->phis->count);
+
+ dst = bptr->phis;
+
+ dst += phis_copy_to(bbi->locals->phis, dst);
+
+ dst += phis_copy_to(bbi->stack->phis, dst);
+
+ bptr->phicount = dst - bptr->phis;
+ }
+ }
+}
+
+/* TODO rename */
+static inline void ssa_enter_eliminate_category(ssa_info_t *ssa, s4 *pvar) {
+ switch (vars_get_category(*pvar)) {
+ case VARS_CATEGORY_LOCAL:
+ *pvar = vars_get_index(vars_resolve_subst(ssa->locals, *pvar));
+ break;
+ case VARS_CATEGORY_STACK:
+ *pvar = vars_get_index(vars_resolve_subst(ssa->stack, *pvar)) + ssa->locals->count;
+ break;
+ case VARS_CATEGORY_OTHERS:
+ *pvar = vars_get_index(*pvar) + ssa->locals->count + ssa->stack->count;
+ break;
+ }
+}
+
+/* TODO rename */
+void ssa_enter_eliminate_categories(ssa_info_t *ssa) {
+ basicblock *bb;
+ instruction *iptr;
+ s4 *ituse, *uses;
+ unsigned uses_count;
+ basicblock_info_t *bbi;
+ instruction *itph;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bb) {
+
+ bbi = bb_info(bb);
+
+ if (! ssa->keep_in_out) {
+ bb->indepth = 0;
+ bb->outdepth = 0;
+ }
+
+ if (bbi != NULL) {
+ FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
+ ssa_enter_eliminate_category(ssa, &(itph->dst.varindex));
+ }
+
+ FOR_EACH_PHI_FUNCTION(bbi->stack->phis, itph) {
+ ssa_enter_eliminate_category(ssa, &(itph->dst.varindex));
+ }
+ }
+
+ FOR_EACH_INSTRUCTION(bb, iptr) {
+ if (instruction_has_dst(iptr)) {
+ ssa_enter_eliminate_category(ssa, &(iptr->dst.varindex));
+ }
+ instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
+ for (ituse = uses; ituse != uses + uses_count; ++ituse) {
+ ssa_enter_eliminate_category(ssa, ituse);
+ }
+ instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
+ }
+ }
+}
+
+static void ssa_enter_create_phi_graph(ssa_info *ssa) {
+ basicblock *bptr;
+ basicblock_info_t *bbi;
+ instruction *itph;
+ instruction **ituse;
+ unsigned i;
+ char path[PATH_MAX], *ppath;
+ FILE *f;
+
+ snprintf(path, PATH_MAX, "|tmp|graphs|%s.%s.dot", ssa->jd->m->clazz->name->text, ssa->jd->m->name->text);
+ for (ppath = path; *ppath; ++ppath) {
+ if (*ppath == '|') *ppath = '/';
+ else if (*ppath == '/') *ppath = '.';
+ }
+
+ f = fopen(path, "w");
+
+ if (f == NULL) return;
+
+ fprintf(f, "digraph G {\n");
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+ bbi = bb_info(bptr);
+ if (bbi != NULL) {
+ FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
+ i = 0;
+ FOR_EACH_PHI_USE(itph, ituse) {
+ if ((*ituse)->opc == ICMD_PHI) {
+ fprintf(f, "%d -> %d;\n", (*ituse)->dst.varindex, itph->dst.varindex);
+ }
+ i += 1;
+ }
+ }
+ }
+ }
+
+ fprintf(f, "};\n");
+
+ fclose(f);
+}
+
+static basicblock *ssa_leave_create_transition_block_intern(
+ ssa_info *ssa,
+ basicblock *from,
+ basicblock *to,
+ unsigned predecessor_index,
+ unsigned reserved_insns
+) {
+ basicblock *bb;
+ instruction *iptr;
+ instruction *itph;
+ basicblock_info_t *toi;
+
+ toi = bb_info(to);
+
+ /* Create basicblock and instruction array. */
+
+ bb = DNEW(basicblock);
+ MZERO(bb, basicblock, 1);
+
+ bb->nr = ssa->jd->basicblockcount;
+ ssa->jd->basicblockcount += 1;
+ bb->mpc = -1;
+ bb->method = ssa->jd->m;
+ bb->type = BBTYPE_STD;
+ bb->icount =
+ reserved_insns +
+ toi->locals->phis->count +
+ toi->stack->phis->count +
+ 1;
+ bb->iinstr = DMNEW(instruction, bb->icount);
+ MZERO(bb->iinstr, instruction, bb->icount);
+
+ /* Populate instruction array. */
+
+ iptr = bb->iinstr + reserved_insns;
+
+ /* Add phi moves. */
+
+ FOR_EACH_PHI_FUNCTION(toi->locals->phis, itph) {
+ phi_create_copy(itph, predecessor_index, iptr++);
+ }
+
+ FOR_EACH_PHI_FUNCTION(toi->stack->phis, itph) {
+ phi_create_copy(itph, predecessor_index, iptr++);
+ }
+
+ /* Add goto to real block. */
+
+ goto_init(iptr, to);
+
+ /* Add basicblock to chain of newly created basicblocks. */
+
+ basicblock_chain_add(ssa->new_blocks, bb);
+
+ return bb;
+}
+
+static inline basicblock *ssa_leave_create_transition_block(
+ ssa_info *ssa,
+ basicblock *from,
+ basicblock *to
+) {
+ return ssa_leave_create_transition_block_intern(
+ ssa,
+ from,
+ to,
+ basicblock_get_predecessor_index(from, to),
+ 0
+ );
+}
+
+static void ssa_leave_create_fallthrough(ssa_info *ssa, basicblock *bptr) {
+ unsigned predecessor_index;
+ basicblock_info_t *toi;
+ instruction *iptr;
+ instruction *itph;
+ unsigned icount;
+
+ if (bptr->next == NULL) {
+ /* No fallthrough. */
+ return;
+ }
+
+ predecessor_index = basicblock_get_predecessor_index(bptr, bptr->next);
+ toi = bb_info(bptr->next);
+
+ assert(toi);
+
+ /* Resize instruction array to accomodate all phi moves. */
+
+ icount = bptr->icount + toi->locals->phis->count + toi->stack->phis->count;
+
+ bptr->iinstr = DMREALLOC(
+ bptr->iinstr,
+ instruction,
+ bptr->icount,
+ icount
+ );
+
+ iptr = bptr->iinstr + bptr->icount;
+ bptr->icount = icount;
+
+ /* Create phi moves. */
+
+ FOR_EACH_PHI_FUNCTION(toi->locals->phis, itph) {
+ phi_create_copy(itph, predecessor_index, iptr++);
+ }
+
+ FOR_EACH_PHI_FUNCTION(toi->stack->phis, itph) {
+ phi_create_copy(itph, predecessor_index, iptr++);
+ }
+}
+
+static void ssa_leave_create_phi_moves(ssa_info *ssa) {
+ basicblock *bptr;
+ instruction *iptr;
+ basicblock *last = NULL;
+
+ s4 i, l;
+ branch_target_t *table;
+ lookup_target_t *lookup;
+ bool has_fallthrough;
+
+ FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
+
+ if (bptr->next == NULL) {
+ last = bptr;
+ }
+
+ if (bptr->vp == NULL) {
+ continue;
+ }
+
+ if (! basicblock_reached(bptr)) {
+ continue;
+ }
+
+ has_fallthrough = true;
+
+ for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
+ switch (icmd_table[iptr->opc].controlflow) {
+ case CF_IF:
+ case CF_RET:
+ case CF_GOTO:
+ iptr->dst.block =
+ ssa_leave_create_transition_block(ssa, bptr, iptr->dst.block);
+ break;
+ case CF_TABLE:
+ table = iptr->dst.table;
+ l = iptr->sx.s23.s2.tablelow;
+ i = iptr->sx.s23.s3.tablehigh;
+ i = i - l + 1;
+ i += 1; /* default */
+ while (--i >= 0) {
+ table->block =
+ ssa_leave_create_transition_block(ssa, bptr, table->block);
+ ++table;
+ }
+ break;
+ case CF_LOOKUP:
+ lookup = iptr->dst.lookup;
+ i = iptr->sx.s23.s2.lookupcount;
+ while (--i >= 0) {
+ lookup->target.block =
+ ssa_leave_create_transition_block(ssa, bptr, lookup->target.block);
+ lookup++;
+ }
+ iptr->sx.s23.s3.lookupdefault.block =
+ ssa_leave_create_transition_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
+ break;
+ case CF_JSR:
+ iptr->sx.s23.s3.jsrtarget.block =
+ ssa_leave_create_transition_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
+ break;
+ }
+
+ if (
+ (iptr->opc == ICMD_GOTO) ||
+ (iptr->opc == ICMD_JSR) ||
+ (iptr->opc == ICMD_RET) ||
+ icmd_table[iptr->opc].controlflow == CF_END ||
+ (iptr->opc == ICMD_TABLESWITCH) ||
+ (iptr->opc == ICMD_LOOKUPSWITCH)
+ ) {
+ has_fallthrough = false;
+ } else if (iptr->opc != ICMD_NOP) {
+ has_fallthrough = true;
+ }
+
+ }
+
+ if (bptr->next == NULL) {
+ continue;
+ }
+
+ if (! basicblock_reached(bptr->next)) {
+ continue;
+ }
+
+ if (has_fallthrough) {
+ ssa_leave_create_fallthrough(ssa, bptr);
+ }
+ }
+
+ /* Add chain of new basic blocks */
+
+ if (last != NULL && ! basicblock_chain_empty(ssa->new_blocks)) {
+ last->next = basicblock_chain_front(ssa->new_blocks);
+ }
+
+}
+
+static basicblock *ssa_leave_split_basicblock_at(ssa_info *ssa, basicblock *bptr, instruction *iptr) {
+
+ basicblock_info_t *bbi = bb_info(bptr);
+ unsigned iidx = iptr - bptr->iinstr;
+ basicblock *newblock;
+ basicblock *tosplit;
+ unsigned ileft;
+ unsigned pos;
+
+ assert(iidx < bptr->icount);
+ assert(bbi);
+
+ /* If there are no subbasicblocks yet, we initialize the first one to be a
+ copy of the original basicblock. */
+
+ if (basicblock_chain_empty(bbi->subbasicblocks)) {
+ newblock = DNEW(basicblock);
+ *newblock = *bptr;
+ newblock->next = NULL;
+ newblock->vp = NULL;
+ basicblock_chain_add(bbi->subbasicblocks, newblock);
+ }
+
+ /* Find the subbasicblock that will be split:
+ the one that cointains iptr. */
+
+ tosplit = basicblock_chain_front(bbi->subbasicblocks);
+ pos = 0;
+
+ while (tosplit->next && (iidx >= (pos + tosplit->icount))) {
+ assert(bptr->nr == tosplit->nr);
+ pos += tosplit->icount;
+ tosplit = tosplit->next;
+ }
+
+ assert(bptr->nr == tosplit->nr);
+
+ /* Calculate number of instructions left in block to split. */
+
+ ileft = iptr - tosplit->iinstr + 1;
+ assert(ileft <= tosplit->icount);
+
+ /* If there are any instructions left in the block to split, split */
+
+ if (ileft < tosplit->icount) {
+ newblock = DNEW(basicblock);
+ *newblock = *tosplit;
+
+ tosplit->next = newblock;
+ tosplit->icount = ileft;
+
+ newblock->icount -= ileft;
+ newblock->iinstr += ileft;
+
+ assert(tosplit->nr == bptr->nr);
+ assert(newblock->nr == bptr->nr);
+ assert(newblock->next == NULL);
+
+ if (newblock->next == NULL) {
+ bbi->subbasicblocks->last = newblock;
+ }
+ }
+
+ /* We won't break pointers/references to bptr.
+ So return bptr instread of the first fragment.
+ Later, we will put the first fragment into the memory used by bptr.
+ */
+
+ if (tosplit == basicblock_chain_front(bbi->subbasicblocks)) {
+ tosplit = bptr;
+ }
+
+ return tosplit;
+}
+
+static basicblock *ssa_leave_create_transition_exception_handler(
+ ssa_info *ssa,
+ basicblock *from,
+ unsigned pei,
+ basicblock *to
+) {
+ basicblock *exh;
+
+ /* From is a try block, to is an exception handler prologue. */
+
+ /* Remove old prologue. */
+
+ to->flags = BBDELETED;
+
+ /* Create new exception handler. */
+
+ exh = ssa_leave_create_transition_block_intern(
+ ssa,
+ from,
+ to,
+ basicblock_get_ex_predecessor_index(from, pei, to),
+ 1
+ );
+ exh->type = BBTYPE_EXH;
+
+ /* Copy goto to real exception handler at the end of the exception handler
+ prologue. */
+
+ assert(to->iinstr[to->icount - 1].opc == ICMD_GOTO);
+ assert(exh->iinstr[exh->icount - 1].opc == ICMD_GOTO);
+ exh->iinstr[exh->icount - 1] = to->iinstr[to->icount - 1];
+
+ /* Copy getexception from the old prologue. */
+
+ assert(to->iinstr[0].opc == ICMD_GETEXCEPTION);
+ exh->iinstr[0] = to->iinstr[0];
+
+ return exh;
+}
+
+static exception_entry *ssa_leave_create_transition_exception_entry(
+ ssa_info_t *ssa,
+ basicblock *from,
+ basicblock *handler,
+ classref_or_classinfo catchtype
+) {
+
+ exception_entry *ee = DNEW(exception_entry);
+ basicblock_info_t *fromi = bb_info(from);
+
+ ee->start = from;
+
+ /* If the try block has subbasicblocks, the next block is the next fragment,
+ not the successor block. */
+
+ if (fromi != NULL) {
+ ee->end = basicblock_chain_front(fromi->subbasicblocks)->next;
+ } else {
+ ee->end = from->next;
+ }
+ ee->handler = handler;
+ ee->catchtype = catchtype;
+ ee->next = NULL;
+ ee->down = NULL;
+
+ return ee;
+}
+
+static void ssa_leave_create_exceptional_phi_moves(ssa_info *ssa) {
+ basicblock *bptr;
+ instruction *iptr;
+ exception_entry *ite;
+ exception_entry_chain_t chain;
+ classref_or_classinfo catchtype;
+ basicblock *ittry;
+ unsigned pei;
+ basicblock *try;
+ basicblock *exh;
+ exception_entry *ee;
+ basicblock *last = NULL;
+
+ if (! basicblock_chain_empty(ssa->new_blocks)) {
+ last = basicblock_chain_back(ssa->new_blocks);
+ }
+
+ basicblock_chain_clear(ssa->new_blocks);
+
+ for (ite = ssa->jd->exceptiontable; ite; ite = ite->down) {
+ bptr = ite->handler;
+ catchtype = ite->catchtype;
+ exception_entry_chain_init(&chain);
+ for (ittry = ite->start; ittry != ite->end; ittry = ittry->next) {
+ if (basicblock_reached(ittry)) {
+ /* Dead code does not have a basicblock_info_t associated. */
+ pei = 0;
+ FOR_EACH_INSTRUCTION(ittry, iptr) {
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
+ /* try is basicblock fragment till (including) the pei */
+ try = ssa_leave_split_basicblock_at(ssa, ittry, iptr);
+ /* ee is handler for try */
+ exh = ssa_leave_create_transition_exception_handler(
+ ssa, try, pei, bptr
+ );
+ ee = ssa_leave_create_transition_exception_entry(
+ ssa, try, exh, catchtype
+ );
+ exception_entry_chain_add(&chain, ee);
+ pei += 1;
+ ssa->jd->exceptiontablelength += 1;
+ }
+ }
+ }
+ }
+ if (! exception_entry_chain_empty(&chain)) {
+ exception_entry_chain_back(&chain)->down = ite->down;
+ exception_entry_chain_back(&chain)->next = ite->next;
+ /* Replace original exception entry by first new one. */
+ *ite = *exception_entry_chain_front(&chain);
+ /* Set current iteration position to last newly created one. */
+ ite = exception_entry_chain_back(&chain);
+ }
+ }
+
+ if (last == NULL) {
+ for (last = ssa->jd->basicblocks; last->next != NULL; last = last->next);
+ }
+
+ if (last != NULL && ! basicblock_chain_empty(ssa->new_blocks)) {
+ last->next = basicblock_chain_front(ssa->new_blocks);
+ }
+}
+
+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 "vmcore/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
+ 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)) {
+ iti = DNEW(basicblock_info_t);
+ basicblock_info_init(iti, it, jd);
+ it->vp = iti;
+ } else {
+ it->vp = NULL;
+ }
+ }
+
+ ssa_enter_mark_loops(jd->basicblocks);
+
+ ssa_enter_traverse(ssa, jd->basicblocks);
+
+ ssa_enter_eliminate_categories(ssa);
+
+ ssa_enter_export_variables(ssa);
+
+ ssa_enter_export_phis(ssa);
+
+ ssa_enter_verify_no_redundant_phis(ssa);
+
+ /*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
+ 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) {
+ basicblock *bptr, *next;
+ basicblock_info_t *bbi;
+
+ FOR_EACH_BASICBLOCK(jd, bptr) {
+ bbi = bb_info(bptr);
+ if (bbi != NULL) {
+ if (! basicblock_chain_empty(bbi->subbasicblocks)) {
+ next = bptr->next;
+ /* Copy first subblock, to keep pointers intact. */
+ *bptr = *basicblock_chain_front(bbi->subbasicblocks);
+ bptr = basicblock_chain_back(bbi->subbasicblocks);
+ bptr->next = next;
+ }
+ }
+ }
+
+#ifdef SSA_VERBOSE
+ printf("=============== [ elim ] =========================\n");
+ show_method(jd, 3);
+ printf("=============== [ /elim ] =========================\n");
+#endif
}
/*
projects / cacao.git / blobdiff