+/* stack_grow_variable_array ***************************************************
+
+ Grow the variable array so the given number of additional variables fits in.
+
+ IN:
+ sd...........stack analysis data
+ num..........number of additional variables
+
+*******************************************************************************/
+
+static void stack_grow_variable_array(stackdata_t *sd, s4 num)
+{
+ s4 newcount;
+
+ assert(num >= 0);
+
+ if (num == 0)
+ return;
+
+ /* XXX avoid too many reallocations */
+ newcount = sd->varcount + num;
+
+ sd->var = DMREALLOC(sd->var, varinfo, sd->varcount, newcount);
+ sd->varcount = newcount;
+ sd->jd->var = sd->var;
+ sd->jd->varcount = newcount;
+}
+
+
+/* stack_append_block **********************************************************
+
+ Append the given block after the last real block of the method (before
+ the pseudo-block at the end).
+
+ IN:
+ sd...........stack analysis data
+ b............the block to append
+
+*******************************************************************************/
+
+static void stack_append_block(stackdata_t *sd, basicblock *b)
+{
+#if defined(STACK_VERBOSE)
+ printf("APPENDING BLOCK L%0d\n", b->nr);
+#endif
+
+ b->next = sd->last_real_block->next;
+ sd->last_real_block->next = b;
+ sd->last_real_block = b;
+ sd->jd->new_basicblockcount++;
+}
+
+
+/* stack_clone_block ***********************************************************
+
+ Create a copy of the given block and insert it at the end of the method.
+
+ CAUTION: This function does not copy the any variables or the instruction
+ list. It _does_, however, reserve space for the block's invars in the
+ variable array.
+
+ IN:
+ sd...........stack analysis data
+ b............the block to clone
+
+ RETURN VALUE:
+ a pointer to the copy
+
+*******************************************************************************/
+
+static basicblock * stack_clone_block(stackdata_t *sd, basicblock *b)
+{
+ basicblock *clone;
+
+ clone = DNEW(basicblock);
+ *clone = *b;
+
+ clone->iinstr = NULL;
+ clone->inlocals = NULL;
+ clone->invars = NULL;
+
+ clone->original = (b->original) ? b->original : b;
+ clone->copied_to = clone->original->copied_to;
+ clone->original->copied_to = clone;
+ clone->nr = sd->m->c_debug_nr++;
+ clone->next = NULL;
+ clone->flags = BBREACHED;
+
+ stack_append_block(sd, clone);
+
+ /* allocate space for the invars of the clone */
+
+ stack_grow_variable_array(sd, b->indepth);
+
+#if defined(STACK_VERBOSE)
+ printf("cloning block L%03d ------> L%03d\n", b->nr, clone->nr);
+#endif
+
+ return clone;
+}
+
+
+/* stack_create_invars *********************************************************
+
+ Create the invars for the given basic block. Also make a copy of the locals.
+
+ IN:
+ sd...........stack analysis data
+ b............block to create the invars for
+ curstack.....current stack top
+ stackdepth...current stack depth
+
+ This function creates STACKDEPTH invars and sets their types to the
+ types to the types of the corresponding slot in the current stack.
+
+*******************************************************************************/
+
+static void stack_create_invars(stackdata_t *sd, basicblock *b,
+ stackptr curstack, int stackdepth)
+{
+ stackptr sp;
+ int i;
+ int index;
+ varinfo *v;
+
+ assert(sd->vartop + stackdepth <= sd->varcount);
+
+ b->indepth = stackdepth;
+ b->invars = DMNEW(s4, stackdepth);
+
+ /* allocate the variable indices */
+ index = (sd->vartop += stackdepth);
+
+ i = stackdepth;
+ for (sp = curstack; i--; sp = sp->prev) {
+ b->invars[i] = --index;
+ v = sd->var + index;
+ v->type = sp->type;
+ v->flags = OUTVAR;
+ v->vv = sd->var[sp->varnum].vv;
+#if defined(STACK_VERBOSE) && 0
+ printf("\tinvar[%d]: %d\n", i, sd->var[b->invars[i]]);
+#endif
+ }
+
+ /* copy the current state of the local variables */
+
+ v = DMNEW(varinfo, sd->localcount);
+ b->inlocals = v;
+ for (i=0; i<sd->localcount; ++i)
+ *v++ = sd->var[i];
+}
+
+
+/* stack_create_invars_from_outvars ********************************************
+
+ Create the invars for the given basic block. Also make a copy of the locals.
+ Types are propagated from the outvars of the current block.
+
+ IN:
+ sd...........stack analysis data
+ b............block to create the invars for
+
+*******************************************************************************/
+
+static void stack_create_invars_from_outvars(stackdata_t *sd, basicblock *b)
+{
+ int i;
+ int n;
+ varinfo *sv, *dv;
+
+ n = sd->bptr->outdepth;
+ assert(sd->vartop + n <= sd->varcount);
+
+ b->indepth = n;
+ b->invars = DMNEW(s4, n);
+
+ if (n) {
+ dv = sd->var + sd->vartop;
+
+ /* allocate the invars */
+
+ for (i=0; i<n; ++i, ++dv) {
+ sv = sd->var + sd->bptr->outvars[i];
+ b->invars[i] = sd->vartop++;
+ dv->type = sv->type;
+ dv->flags = OUTVAR;
+ dv->vv = sv->vv;
+ }
+ }
+
+ /* copy the current state of the local variables */
+
+ dv = DMNEW(varinfo, sd->localcount);
+ b->inlocals = dv;
+ for (i=0; i<sd->localcount; ++i)
+ *dv++ = sd->var[i];
+}
+
+
+/* stack_check_invars **********************************************************
+
+ Check the current stack against the invars of the given basic block.
+ Depth and types must match.
+
+ IN:
+ sd...........stack analysis data
+ b............block which invars to check against
+ curstack.....current stack top
+ stackdepth...current stack depth
+
+ RETURN VALUE:
+ the destinaton block
+ NULL.........a VerifyError has been thrown
+
+*******************************************************************************/
+
+static basicblock * stack_check_invars(stackdata_t *sd, basicblock *b,
+ stackptr curstack, int stackdepth)
+{
+ int i;
+ stackptr sp;
+ basicblock *orig;
+ bool separable;
+
+#if defined(STACK_VERBOSE)
+ printf("stack_check_invars(L%03d)\n", b->nr);
+#endif
+
+ /* find original of b */
+ if (b->original)
+ b = b->original;
+ orig = b;
+
+#if defined(STACK_VERBOSE)
+ printf("original is L%03d\n", orig->nr);
+#endif
+
+ i = orig->indepth;
+
+ if (i != stackdepth) {
+ exceptions_throw_verifyerror(sd->m, "Stack depth mismatch");
+ return NULL;
+ }
+
+ do {
+ separable = false;
+
+#if defined(STACK_VERBOSE)
+ printf("checking against ");
+ stack_verbose_show_block(sd, b); printf("\n");
+#endif
+
+ sp = curstack;
+ for (i = orig->indepth; i--; sp = sp->prev) {
+ if (sd->var[b->invars[i]].type != sp->type) {
+ exceptions_throw_verifyerror_for_stack(sd->m,
+ sd->var[b->invars[i]].type);
+ return NULL;
+ }
+
+ if (sp->type == TYPE_RET) {
+ if (sd->var[b->invars[i]].vv.retaddr != sd->var[sp->varnum].vv.retaddr) {
+ separable = true;
+ break;
+ }
+ }
+ }
+
+ if (b->inlocals) {
+ for (i=0; i<sd->localcount; ++i) {
+ if (sd->var[i].type == TYPE_RET && b->inlocals[i].type == TYPE_RET) {
+ if (sd->var[i].vv.retaddr != b->inlocals[i].vv.retaddr) {
+ separable = true;
+ break;
+ }
+ }
+ }
+ }
+
+ if (!separable) {
+ /* XXX mark mixed type variables void */
+ /* XXX cascading collapse? */
+#if defined(STACK_VERBOSE)
+ printf("------> using L%03d\n", b->nr);
+#endif
+ return b;
+ }
+ } while ((b = b->copied_to) != NULL);
+
+ b = stack_clone_block(sd, orig);
+ if (!b)
+ return NULL;
+
+ stack_create_invars(sd, b, curstack, stackdepth);
+ return b;
+}
+
+
+/* stack_check_invars_from_outvars *********************************************
+
+ Check the outvars of the current block against the invars of the given block.
+ Depth and types must match.
+
+ IN:
+ sd...........stack analysis data
+ b............block which invars to check against
+
+ RETURN VALUE:
+ the destinaton block
+ NULL.........a VerifyError has been thrown
+
+*******************************************************************************/
+
+static basicblock * stack_check_invars_from_outvars(stackdata_t *sd, basicblock *b)
+{
+ int i;
+ int n;
+ varinfo *sv, *dv;
+ basicblock *orig;
+ bool separable;
+
+#if defined(STACK_VERBOSE)
+ printf("stack_check_invars_from_outvars(L%03d)\n", b->nr);
+#endif
+
+ /* find original of b */
+ if (b->original)
+ b = b->original;
+ orig = b;
+
+#if defined(STACK_VERBOSE)
+ printf("original is L%03d\n", orig->nr);
+#endif
+
+ i = orig->indepth;
+ n = sd->bptr->outdepth;
+
+ if (i != n) {
+ exceptions_throw_verifyerror(sd->m, "Stack depth mismatch");
+ return NULL;
+ }
+
+ do {
+ separable = false;
+
+#if defined(STACK_VERBOSE)
+ printf("checking against ");
+ stack_verbose_show_block(sd, b); printf("\n");
+#endif
+
+ if (n) {
+ dv = sd->var + b->invars[0];
+
+ for (i=0; i<n; ++i, ++dv) {
+ sv = sd->var + sd->bptr->outvars[i];
+ if (sv->type != dv->type) {
+ exceptions_throw_verifyerror_for_stack(sd->m, dv->type);
+ return NULL;
+ }
+
+ if (dv->type == TYPE_RET) {
+ if (sv->vv.retaddr != dv->vv.retaddr) {
+ separable = true;
+ break;
+ }
+ }
+ }
+ }
+
+ if (b->inlocals) {
+ for (i=0; i<sd->localcount; ++i) {
+ if (sd->var[i].type == TYPE_RET && b->inlocals[i].type == TYPE_RET) {
+ if (sd->var[i].vv.retaddr != b->inlocals[i].vv.retaddr) {
+ separable = true;
+ break;
+ }
+ }
+ }
+ }
+
+ if (!separable) {
+ /* XXX mark mixed type variables void */
+ /* XXX cascading collapse? */
+#if defined(STACK_VERBOSE)
+ printf("------> using L%03d\n", b->nr);
+#endif
+ return b;
+ }
+ } while ((b = b->copied_to) != NULL);
+
+ b = stack_clone_block(sd, orig);
+ if (!b)
+ return NULL;
+
+ stack_create_invars_from_outvars(sd, b);
+ return b;
+}
+
+
+/* stack_create_instack ********************************************************
+
+ Create the instack of the current basic block.
+
+ IN:
+ sd...........stack analysis data
+
+ RETURN VALUE:
+ the current stack top at the start of the basic block.
+
+*******************************************************************************/
+
+static stackptr stack_create_instack(stackdata_t *sd)
+{
+ stackptr sp;
+ int depth;
+ int index;
+
+ if ((depth = sd->bptr->indepth) == 0)
+ return NULL;
+
+ sp = (sd->new += depth);
+
+ while (depth--) {
+ sp--;
+ index = sd->bptr->invars[depth];
+ sp->varnum = index;
+ sp->type = sd->var[index].type;
+ sp->prev = sp - 1;
+ sp->creator = NULL;
+ sp->flags = 0;
+ sp->varkind = STACKVAR;
+ }
+ sp->prev = NULL;
+
+ /* return the top of the created stack */
+ return sd->new - 1;
+}
+
+
+/* stack_mark_reached **********************************************************
+
+ Mark the given block reached and propagate the current stack and locals to
+ it. This function specializes the target block, if necessary, and returns
+ a pointer to the specialized target.
+
+ IN:
+ sd...........stack analysis data
+ b............the block to reach
+ curstack.....the current stack top
+ stackdepth...the current stack depth
+
+ RETURN VALUE:
+ a pointer to (a specialized version of) the target
+ NULL.........a VerifyError has been thrown
+
+*******************************************************************************/
+
+static basicblock *stack_mark_reached(stackdata_t *sd, basicblock *b, stackptr curstack, int stackdepth)
+{
+#if defined(STACK_VERBOSE)
+ printf("stack_mark_reached(L%03d from L%03d)\n", b->nr, sd->bptr->nr);
+#endif
+ /* mark targets of backward branches */
+ if (b <= sd->bptr)
+ b->bitflags |= BBFLAG_REPLACEMENT;
+
+ if (b->flags < BBREACHED) {
+ /* b is reached for the first time. Create its invars. */
+
+#if defined(STACK_VERBOSE)
+ printf("reached L%03d for the first time\n", b->nr);
+#endif
+
+ stack_create_invars(sd, b, curstack, stackdepth);
+
+ b->flags = BBREACHED;
+
+ return b;
+ }
+ else {
+ /* b has been reached before. Check that its invars match. */
+
+ return stack_check_invars(sd, b, curstack, stackdepth);
+ }
+}
+
+
+/* stack_mark_reached_from_outvars *********************************************
+
+ Mark the given block reached and propagate the outvars of the current block
+ and the current locals to it. This function specializes the target block,
+ if necessary, and returns a pointer to the specialized target.
+
+ IN:
+ sd...........stack analysis data
+ b............the block to reach
+
+ RETURN VALUE:
+ a pointer to (a specialized version of) the target
+ NULL.........a VerifyError has been thrown
+
+*******************************************************************************/
+
+static basicblock *stack_mark_reached_from_outvars(stackdata_t *sd, basicblock *b)
+{
+#if defined(STACK_VERBOSE)
+ printf("stack_mark_reached_from_outvars(L%03d from L%03d)\n", b->nr, sd->bptr->nr);
+#endif
+ /* mark targets of backward branches */
+ if (b <= sd->bptr)
+ b->bitflags |= BBFLAG_REPLACEMENT;
+
+ if (b->flags < BBREACHED) {
+ /* b is reached for the first time. Create its invars. */
+
+#if defined(STACK_VERBOSE)
+ printf("reached L%03d for the first time\n", b->nr);
+#endif
+
+ stack_create_invars_from_outvars(sd, b);
+
+ b->flags = BBREACHED;
+
+ return b;
+ }
+ else {
+ /* b has been reached before. Check that its invars match. */
+
+ return stack_check_invars_from_outvars(sd, b);
+ }
+}
+
+
+/* stack_reach_next_block ******************************************************
+
+ Mark the following block reached and propagate the outvars of the current block
+ and the current locals to it. This function specializes the target block,
+ if necessary, and returns a pointer to the specialized target.
+
+ IN:
+ sd...........stack analysis data
+
+ RETURN VALUE:
+ a pointer to (a specialized version of) the following block
+ NULL.........a VerifyError has been thrown
+
+*******************************************************************************/
+
+static bool stack_reach_next_block(stackdata_t *sd)
+{
+ basicblock *tbptr;
+ instruction *iptr;
+
+ tbptr = (sd->bptr->original) ? sd->bptr->original : sd->bptr;
+ tbptr = stack_mark_reached_from_outvars(sd, tbptr->next);
+ if (!tbptr)
+ return false;
+
+ if (tbptr != sd->bptr->next) {
+#if defined(STACK_VERBOSE)
+ printf("NEXT IS NON-CONSEQUITIVE L%03d\n", tbptr->nr);