+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;
+}
+
+/*** traversal **************************************************************/
+
+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;
+
+typedef struct {
+ phis_t *phis;
+ state_array_t *state_array;
+ void *ops_vp;
+ traversal_ops_t *ops;
+} traversal_t;
+
+/*** basicblock_info ********************************************************/
+
+typedef struct basicblock_info {
+ bool visited;
+ bool active;
+ bool traversed;
+ unsigned backward_branches;
+
+ traversal_t *locals;
+ traversal_t *stack;
+
+ 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);
+ }
+ }
+ }