Logo Search packages:      
Sourcecode: cacao-source version File versions  Download package

inline.c

/* src/vm/jit/inline/inline.c - method inlining

   Copyright (C) 1996-2005, 2006, 2007, 2008
   CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO

   This file is part of CACAO.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2, or (at
   your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301, USA.

*/


#include "config.h"

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>

#include "vm/types.h"

#include "mm/memory.h"

#include "threads/lock-common.h"
#include "threads/thread.h"

#include "toolbox/logging.h"

#include "vm/builtin.h"
#include "vm/global.h"
#include "vm/initialize.h"

#include "vm/jit/jit.h"
#include "vm/jit/parse.h"
#include "vm/jit/reg.h"
#include "vm/jit/show.h"
#include "vm/jit/stack.h"

#include "vm/jit/inline/inline.h"
#include "vm/jit/loop/loop.h"

#include "vm/jit/verify/typecheck.h"

#include "vmcore/class.h"
#include "vmcore/method.h"
#include "vmcore/options.h"
#include "vmcore/statistics.h"


/* algorithm tuning constants *************************************************/

/* Algorithm Selection                                                        */
/* Define exactly one of the following three to select the inlining           */
/* heuristics.                                                                */

/*#define INLINE_DEPTH_FIRST*/
/*#define INLINE_BREADTH_FIRST*/
#define INLINE_KNAPSACK

/* Parameters for knapsack heuristics:                                        */

#if defined(INLINE_KNAPSACK)

#define INLINE_COUNTDOWN_INIT       1000
#define INLINE_COST_OFFSET          -16
#define INLINE_COST_BUDGET          100
/*#define INLINE_WEIGHT_BUDGET        5.0*/
/*#define INLINE_ADD_NEGATIVE_TO_BUDGET*/
/*#define INLINE_MAX_DEPTH            3*/
/*#define INLINE_DIVIDE_COST_BY_FREQ */

#endif

/* Parameters for depth-first heuristics:                                     */

#if defined(INLINE_DEPTH_FIRST)

#define INLINE_MAX_DEPTH            3
#define INLINE_MAX_BLOCK_EXPANSION  10
/*#define INLINE_MAX_ICMD_EXPANSION  10*/
/*#define INLINE_CANCEL_ON_THRESHOLD*/

#endif

/* Parameters for breadth-first heuristics:                                   */

#if defined(INLINE_BREADTH_FIRST)

/*#define INLINE_MAX_BLOCK_EXPANSION  10*/
#define INLINE_MAX_ICMD_EXPANSION  5

#endif


/* debugging ******************************************************************/

#if !defined(NDEBUG)
#define INLINE_VERBOSE
#define DOLOG(code)       do{ if (opt_TraceInlining >= 2) { code; } }while(0)
#define DOLOG_SHORT(code) do{ if (opt_TraceInlining >= 1) { code; } }while(0)
#else
#define DOLOG(code)
#endif

#if defined(ENABLE_VERIFIER) && !defined(NDEBUG)
/* Define this to verify the resulting code after inlining.                 */
/* Note: This is only useful for development and may require patches to the */
/*       verifier code.                                                     */
/* #define INLINE_VERIFY_RESULT */
#endif


/* types **********************************************************************/

typedef struct inline_node inline_node;
typedef struct inline_target_ref inline_target_ref;
typedef struct inline_context inline_context;
typedef struct inline_block_map inline_block_map;
typedef struct inline_site inline_site;
typedef struct inline_candidate inline_candidate;

00135 struct inline_node {
      inline_context *ctx;

      jitdata *jd;
      methodinfo *m;
      inline_node *children;
      inline_node *next;                             /* next node at this depth */
      inline_node *prev;                             /* prev node at this depth */
      int depth;                                  /* inlining depth, 0 for root */

      /* info about the call site (if depth > 0)*/
      inline_node *parent;                /* node of the caller (NULL for root) */
      basicblock *callerblock;         /* original block containing the INVOKE* */
      instruction *callerins;               /* the original INVOKE* instruction */
      s4 callerpc;
      s4 *n_passthroughvars;
      int n_passthroughcount;
      int n_selfpassthroughcount;  /* # of pass-through vars of the call itself */
      exception_entry **o_handlers;
      int n_handlercount;                 /* # of handlers protecting this call */
      int n_resultlocal;
      int synclocal;                    /* variable used for synchr., or UNUSED */
      bool isstatic;                                   /* this is a static call */

      bool blockbefore;                  /* block boundary before inlined body? */
      bool blockafter;                   /* block boundary after inlined body?  */

      /* info about the callee */
      int localsoffset;
      int prolog_instructioncount;         /* # of ICMDs in the inlining prolog */
      int epilog_instructioncount;         /* # of ICMDs in the inlining epilog */
      int extra_instructioncount;
      int extra_exceptiontablelength;   /* # of extra handlers to put in caller */
      bool synchronize;                /* do we have to synchronize enter/exit? */
      basicblock *handler_monitorexit;     /* handler for synchronized inlinees */
      s4 *varmap;

      /* cumulative values */
      int cumul_instructioncount;  /* ICMDs in this node and its children       */
      int cumul_basicblockcount;   /* BBs started by this node and its children */
      int cumul_basicblockcount_root;  /* BBs that have to be added to the root */
                                       /* node if this node is inlined          */
      int cumul_blockmapcount;
      int cumul_maxlocals;
      int cumul_exceptiontablelength;

      /* output */
      instruction *inlined_iinstr;
      instruction *inlined_iinstr_cursor;
      basicblock *inlined_basicblocks;
      basicblock *inlined_basicblocks_cursor;

      /* register data */
      registerdata *regdata;

      /* temporary */
      inline_target_ref *refs;
      instruction *inline_start_instruction;
      s4 *javalocals;

      /* XXX debug */
      char *indent;
      int debugnr;
};

00200 struct inline_target_ref {
      inline_target_ref *next;
      union {
            basicblock **block;
            s4 *nr;
      } ref;
      basicblock *target;
      bool isnumber;
};

00210 struct inline_block_map {
      inline_node *iln;
      basicblock *o_block;
      basicblock *n_block;
};

00216 struct inline_context {
      inline_node *master;

      jitdata *resultjd;

      inline_candidate *candidates;

      int next_block_number;
      inline_block_map *blockmap;
      int blockmap_index;

      int maxinoutdepth;

      bool stopped;

      int next_debugnr; /* XXX debug */
};

00234 struct inline_site {
      bool              speculative;  /* true, if inlining would be speculative */
      bool              inlined;      /* true, if this site has been inlined    */

      basicblock       *bptr;         /* basic block containing the call site   */
      instruction      *iptr;         /* the invocation instruction             */
      exception_entry **handlers;     /* active handlers at the call site       */
      s4                nhandlers;    /* number of active handlers              */
      s4                pc;           /* PC of the invocation instruction       */
};

00245 struct inline_candidate {
      inline_candidate *next;
      int freq;
      int cost;
      double weight;
      inline_node *caller;
      methodinfo *callee;
      inline_site site;
};


/* prototypes *****************************************************************/

static bool inline_analyse_code(inline_node *iln);
static void inline_post_process(jitdata *jd);


/* debug helpers **************************************************************/

#if !defined(NDEBUG)
#include "inline_debug.inc"
#endif


/* statistics *****************************************************************/

/*#define INLINE_STATISTICS*/

#if !defined(NDEBUG)
#define INLINE_STATISTICS
#endif

#if defined(INLINE_STATISTICS)
int inline_stat_roots = 0;
int inline_stat_roots_transformed = 0;
int inline_stat_inlined_nodes = 0;
int inline_stat_max_depth = 0;

void inline_print_stats()
{
      printf("inlining statistics:\n");
      printf("    roots analysed   : %d\n", inline_stat_roots);
      printf("    roots transformed: %d\n", inline_stat_roots_transformed);
      printf("    inlined nodes    : %d\n", inline_stat_inlined_nodes);
      printf("    max depth        : %d\n", inline_stat_max_depth);
}
#endif


/* compilation of callees *****************************************************/

static bool inline_jit_compile_intern(jitdata *jd)
{
      methodinfo *m;

      /* XXX should share code with jit.c */

      assert(jd);

      /* XXX initialize the static function's class */

      m = jd->m;

      /* call the compiler passes ***********************************************/

      /* call parse pass */

      DOLOG( log_message_class("Parsing ", m->clazz) );
      if (!parse(jd)) {
            return false;
      }

      /* call stack analysis pass */

      if (!stack_analyse(jd)) {
            return false;
      }

      return true;
}


static bool inline_jit_compile(inline_node *iln)
{
      bool                r;
      methodinfo         *m;
      jitdata            *jd;

      /* XXX should share code with jit.c */

      assert(iln);
      m = iln->m;
      assert(m);

      /* enter a monitor on the method */

      LOCK_MONITOR_ENTER(m);

      /* allocate jitdata structure and fill it */

      jd = jit_jitdata_new(m);
      iln->jd = jd;

      jd->flags = 0; /* XXX */

      /* initialize the register allocator */

      reg_setup(jd);

      /* setup the codegendata memory */

      /* XXX do a pseudo setup */
      jd->cd = DNEW(codegendata);
      MZERO(jd->cd, codegendata, 1);
      jd->cd->method = m;
      /* XXX uses too much dump memory codegen_setup(jd); */

      /* now call internal compile function */

      r = inline_jit_compile_intern(jd);

      if (r) {
            iln->regdata = jd->rd;
      }

      /* free some memory */
#if 0

#if defined(ENABLE_JIT)
# if defined(ENABLE_INTRP)
      if (!opt_intrp)
# endif
            codegen_free(jd);
#endif

#endif

      /* leave the monitor */

      LOCK_MONITOR_EXIT(m);

      return r;
}


/* inlining tree handling *****************************************************/

static void inline_insert_inline_node(inline_node *parent, inline_node *child)
{
      inline_node *first;
      inline_node *succ;

      assert(parent && child);

      child->parent = parent;

      child->debugnr = parent->ctx->next_debugnr++; /* XXX debug */

      first = parent->children;
      if (!first) {
            /* insert as only node */
            parent->children = child;
            child->next = child;
            child->prev = child;
            return;
      }

      /* {there is at least one child already there} */

      /* XXX is this search necessary, or could we always add at the end? */

      succ = first;
      while (succ->callerpc < child->callerpc) {
            succ = succ->next;
            if (succ == first) {
                  /* insert as last node */
                  child->prev = first->prev;
                  child->next = first;
                  child->prev->next = child;
                  child->next->prev = child;
                  return;
            }
      }

      assert(succ->callerpc > child->callerpc);

      /* insert before succ */

      child->prev = succ->prev;
      child->next = succ;
      child->prev->next = child;
      child->next->prev = child;

      if (parent->children == succ)
            parent->children = child;
}


static void inline_remove_inline_node(inline_node *parent, inline_node *child)
{
      assert(parent);
      assert(child);
      assert(child->parent == parent);

      if (child->prev == child) {
            /* remove the only child node */
            parent->children = NULL;
      }
      else {
            child->prev->next = child->next;
            child->next->prev = child->prev;

            if (parent->children == child)
                  parent->children = child->next;
      }
}


/* inlining candidate handling ************************************************/

#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
static void inline_add_candidate(inline_context *ctx,
                                                 inline_node *caller,
                                                 methodinfo *callee,
                                                 inline_site *site)
{
      inline_candidate **link;
      inline_candidate *cand;

      cand = DNEW(inline_candidate);
#if defined(INLINE_DIVIDE_COST_BY_FREQ)
      cand->freq = INLINE_COUNTDOWN_INIT - callee->hitcountdown;
      if (cand->freq < 1)
#endif
            cand->freq = 1;
#if defined(INLINE_KNAPSACK)
      cand->cost = callee->jcodelength + INLINE_COST_OFFSET;
#endif
#if defined(INLINE_BREADTH_FIRST)
      cand->cost = caller->depth;
#endif
      cand->caller = caller;
      cand->callee = callee;
      cand->site = *site;

      cand->weight = (double)cand->cost / cand->freq;

      for (link = &(ctx->candidates); ; link = &((*link)->next)) {
            if (!*link || (*link)->weight > cand->weight) {
                  cand->next = *link;
                  *link = cand;
                  break;
            }
      }
}
#endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */

#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
static inline_candidate * inline_pick_best_candidate(inline_context *ctx)
{
      inline_candidate *cand;

      cand = ctx->candidates;

      if (cand)
            ctx->candidates = cand->next;

      return cand;
}
#endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */

#if !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST))
static void inline_candidate_println(inline_candidate *cand)
{
      printf("%10g (%5d / %5d) depth %2d ",
                  cand->weight, cand->cost, cand->freq, cand->caller->depth + 1);
      method_println(cand->callee);
}
#endif /* !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)) */


#if !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST))
static void inline_candidates_println(inline_context *ctx)
{
      inline_candidate *cand;

      for (cand = ctx->candidates; cand != NULL; cand = cand->next) {
            printf("    ");
            inline_candidate_println(cand);
      }
}
#endif /* !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)) */


/* variable handling **********************************************************/

static s4 inline_new_variable(jitdata *jd, s4 type, s4 flags)
{
      s4 index;
      s4 newcount;

      index = jd->vartop++;
      if (index >= jd->varcount) {
            newcount = jd->vartop * 2; /* XXX */
            jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, newcount);
            MZERO(jd->var + jd->varcount, varinfo, (newcount - jd->varcount));
            jd->varcount = newcount;
      }

      jd->var[index].type = type;
      jd->var[index].flags = flags;

      return index;
}


static s4 inline_new_variable_clone(jitdata *jd, jitdata *origjd, s4 origidx)
{
      varinfo *v;
      s4       newidx;

      v = &(origjd->var[origidx]);

      newidx = inline_new_variable(jd, v->type, v->flags);

      jd->var[newidx].vv = v->vv;

      return newidx;
}


static s4 inline_new_temp_variable(jitdata *jd, s4 type)
{
      return inline_new_variable(jd, type, 0);
}


static s4 inline_translate_variable(jitdata *jd, jitdata *origjd, s4 *varmap, s4 index)
{
      s4 idx;

      idx = varmap[index];

      if (idx < 0) {
            idx = inline_new_variable_clone(jd, origjd, index);
            varmap[index] = idx;
      }

      return idx;
}


static s4 *create_variable_map(inline_node *callee)
{
      s4 *varmap;
      s4 i, t;
      s4 varindex;
      s4 n_javaindex;
      s4 avail;
      varinfo *v;

      /* create the variable mapping */

      varmap = DMNEW(s4, callee->jd->varcount);
      for (i=0; i<callee->jd->varcount; ++i)
            varmap[i] = -1;

      /* translate local variables */

      for (i=0; i<callee->m->maxlocals; ++i) {
            for (t=0; t<5; ++t) {
                  varindex = callee->jd->local_map[5*i + t];
                  if (varindex == UNUSED)
                        continue;

                  v = &(callee->jd->var[varindex]);
                  assert(v->type == t || v->type == TYPE_VOID); /* XXX stack leaves VOID */
                  v->type = t; /* XXX restore if it is TYPE_VOID */

                  avail = callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t];

                  if (avail == UNUSED) {
                        avail = inline_new_variable_clone(callee->ctx->resultjd, callee->jd, varindex);
                        callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t] = avail;
                  }

                  varmap[varindex] = avail;
            }
      }

      /* for synchronized instance methods we need an extra local */

      if (callee->synchronize && !(callee->m->flags & ACC_STATIC)) {
            n_javaindex = callee->localsoffset - 1;
            assert(n_javaindex >= 0);
            assert(callee->parent);
            assert(n_javaindex == callee->parent->localsoffset + callee->parent->m->maxlocals);

            avail = callee->ctx->resultjd->local_map[5*n_javaindex + TYPE_ADR];

            if (avail == UNUSED) {
                  avail = inline_new_variable(callee->ctx->resultjd, TYPE_ADR, 0);
                  callee->ctx->resultjd->local_map[5*n_javaindex + TYPE_ADR] = avail;
            }

            callee->synclocal = avail;
      }
      else {
            callee->synclocal = UNUSED;
      }

      return varmap;
}


/* basic block translation ****************************************************/

#define INLINE_RETURN_REFERENCE(callee)  \
      ( (basicblock *) (ptrint) (0x333 + (callee)->depth) )


static void inline_add_block_reference(inline_node *iln, basicblock **blockp)
{
      inline_target_ref *ref;

      ref = DNEW(inline_target_ref);
      ref->ref.block = blockp;
      ref->isnumber = false;
      ref->next = iln->refs;
      iln->refs = ref;
}


#if 0
static void inline_add_blocknr_reference(inline_node *iln, s4 *nrp)
{
      inline_target_ref *ref;

      ref = DNEW(inline_target_ref);
      ref->ref.nr = nrp;
      ref->isnumber = true;
      ref->next = iln->refs;
      iln->refs = ref;
}
#endif


static void inline_block_translation(inline_node *iln, basicblock *o_bptr, basicblock *n_bptr)
{
      inline_context *ctx;

      ctx = iln->ctx;
      assert(ctx->blockmap_index < ctx->master->cumul_blockmapcount);

      ctx->blockmap[ctx->blockmap_index].iln = iln;
      ctx->blockmap[ctx->blockmap_index].o_block = o_bptr;
      ctx->blockmap[ctx->blockmap_index].n_block = n_bptr;

      ctx->blockmap_index++;
}


static basicblock * inline_map_block(inline_node *iln,
                                                       basicblock *o_block,
                                                       inline_node *targetiln)
{
      inline_block_map *bm;
      inline_block_map *bmend;

      assert(iln);
      assert(targetiln);

      if (!o_block)
            return NULL;

      bm = iln->ctx->blockmap;
      bmend = bm + iln->ctx->blockmap_index;

      while (bm < bmend) {
            assert(bm->iln && bm->o_block && bm->n_block);
            if (bm->o_block == o_block && bm->iln == targetiln)
                  return bm->n_block;
            bm++;
      }

      assert(false);
      return NULL; /* not reached */
}


static void inline_resolve_block_refs(inline_target_ref **refs,
                                                        basicblock *o_bptr,
                                                        basicblock *n_bptr,
                                                        bool returnref)
{
      inline_target_ref *ref;
      inline_target_ref *prev;

      prev = NULL;
      for (ref = *refs; ref != NULL; ref = ref->next) {
            if (ref->isnumber && !returnref) {
                  if (*(ref->ref.nr) == JAVALOCAL_FROM_RETADDR(o_bptr->nr)) {
                        *(ref->ref.nr) = JAVALOCAL_FROM_RETADDR(n_bptr->nr);
                        goto remove_ref;
                  }
            }
            else {
                  if (*(ref->ref.block) == o_bptr) {
                        *(ref->ref.block) = n_bptr;
                        goto remove_ref;
                  }
            }

            /* skip this ref */

            prev = ref;
            continue;

remove_ref:
            /* remove this ref */

            if (prev) {
                  prev->next = ref->next;
            }
            else {
                  *refs = ref->next;
            }
      }
}


/* basic block creation *******************************************************/

static basicblock * create_block(inline_node *container,
                                                 inline_node *iln,
                                                 inline_node *inner,
                                                 int indepth)
{
      basicblock  *n_bptr;
      inline_node *outer;
      s4           i;
      s4           depth;
      s4           varidx;
      s4           newvaridx;

      assert(container);
      assert(iln);
      assert(inner);
      assert(indepth >= 0);

      n_bptr = container->inlined_basicblocks_cursor++;
      assert(n_bptr);
      assert((n_bptr - container->inlined_basicblocks) < container->cumul_basicblockcount);

      BASICBLOCK_INIT(n_bptr, iln->m);

      n_bptr->iinstr = container->inlined_iinstr_cursor;
      n_bptr->next = n_bptr + 1;
      n_bptr->nr = container->ctx->next_block_number++;
      n_bptr->indepth = indepth;
      n_bptr->flags = BBFINISHED; /* XXX */

      /* set the inlineinfo of the new block */

      if (iln->inline_start_instruction)
            n_bptr->inlineinfo = iln->inline_start_instruction->sx.s23.s3.inlineinfo;

      if (indepth > container->ctx->maxinoutdepth)
            container->ctx->maxinoutdepth = indepth;

      if (indepth) {
            n_bptr->invars = DMNEW(s4, indepth);


            for (i=0; i<indepth; ++i)
                  n_bptr->invars[i] = -1; /* XXX debug */

            /* pass-through variables enter the block */

            outer = inner->parent;
            while (outer != NULL) {
                  depth = outer->n_passthroughcount;

                  assert(depth + inner->n_selfpassthroughcount <= indepth);

                  for (i=0; i<inner->n_selfpassthroughcount; ++i) {
                        varidx = inner->n_passthroughvars[i];
                        newvaridx =
                              inline_new_variable_clone(container->ctx->resultjd,
                                                                    outer->jd,
                                                                    varidx);
                        n_bptr->invars[depth + i] = newvaridx;
                        outer->varmap[varidx] = newvaridx;
                  }
                  inner = outer;
                  outer = outer->parent;
            }
      }
      else {
            n_bptr->invars = NULL;
      }

      /* XXX for the verifier. should not be here */

      {
            varinfo *dv;

            dv = DMNEW(varinfo, iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
            MZERO(dv, varinfo,  iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
            n_bptr->inlocals = dv;
      }

      return n_bptr;
}


static s4 *translate_javalocals(inline_node *iln, s4 *javalocals)
{
      s4 *jl;
      s4 i, j;

      jl = DMNEW(s4, iln->jd->maxlocals);

      for (i=0; i<iln->jd->maxlocals; ++i) {
            j = javalocals[i];
            if (j > UNUSED)
                  j = inline_translate_variable(iln->ctx->resultjd, iln->jd, iln->varmap, j);
            jl[i] = j;

#if 0
            if (j < UNUSED) {
                  /* an encoded returnAddress value - must be relocated */
                  inline_add_blocknr_reference(iln, &(jl[i]));
            }
#endif
      }

      return jl;
}


static basicblock * create_body_block(inline_node *iln,
                                                        basicblock *o_bptr, s4 *varmap)
{
      basicblock *n_bptr;
      s4 i;

      n_bptr = create_block(iln, iln, iln,
                                      o_bptr->indepth + iln->n_passthroughcount);

      n_bptr->type = o_bptr->type;
      n_bptr->flags = o_bptr->flags;
      n_bptr->bitflags = o_bptr->bitflags;

      /* resolve references to this block */

      inline_resolve_block_refs(&(iln->refs), o_bptr, n_bptr, false);

      /* translate the invars of the original block */

      for (i=0; i<o_bptr->indepth; ++i) {
            n_bptr->invars[iln->n_passthroughcount + i] =
                  inline_translate_variable(iln->ctx->resultjd, iln->jd,
                        varmap,
                        o_bptr->invars[i]);
      }

      /* translate javalocals info (not for dead code) */

      if (n_bptr->flags >= BBREACHED)
            n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);

      return n_bptr;
}


static basicblock * create_epilog_block(inline_node *caller, inline_node *callee, s4 *varmap)
{
      basicblock *n_bptr;
      s4 retcount;
      s4 idx;

      /* number of return variables */

      retcount = (callee->n_resultlocal == -1
                        && callee->m->parseddesc->returntype.type != TYPE_VOID) ? 1 : 0;

      /* start the epilog block */

      n_bptr = create_block(caller, caller, callee,
                                      callee->n_passthroughcount + retcount);

      /* resolve references to the return block */

      inline_resolve_block_refs(&(callee->refs),
                                            INLINE_RETURN_REFERENCE(callee),
                                            n_bptr,
                                            true);

      /* return variable */

      if (retcount) {
            idx = inline_new_variable(caller->ctx->resultjd,
                     callee->m->parseddesc->returntype.type, 0 /* XXX */);
            n_bptr->invars[callee->n_passthroughcount] = idx;
            varmap[callee->callerins->dst.varindex] = idx;
      }

      /* set javalocals */

      n_bptr->javalocals = DMNEW(s4, caller->jd->maxlocals);
      MCOPY(n_bptr->javalocals, caller->javalocals, s4, caller->jd->maxlocals);

      /* set block flags & type */

      n_bptr->flags = /* XXX original block flags */ BBFINISHED;
      n_bptr->type = BBTYPE_STD;

      return n_bptr;
}


static void close_block(inline_node *iln, inline_node *inner, basicblock *n_bptr, s4 outdepth)
{
      inline_node *outer;
      s4           i;
      s4           depth;
      s4           varidx;

      n_bptr->outdepth = outdepth;
      n_bptr->outvars = DMNEW(s4, outdepth);

      for (i=0; i<outdepth; ++i)
            n_bptr->outvars[i] = 0; /* XXX debug */

      if (outdepth > iln->ctx->maxinoutdepth)
            iln->ctx->maxinoutdepth = outdepth;

      /* pass-through variables leave the block */

      outer = inner->parent;
      while (outer != NULL) {
            depth = outer->n_passthroughcount;

            assert(depth + inner->n_selfpassthroughcount <= outdepth);

            for (i=0; i<inner->n_selfpassthroughcount; ++i) {
                  varidx = inner->n_passthroughvars[i];
                  n_bptr->outvars[depth + i] =
                        inline_translate_variable(iln->ctx->resultjd,
                                                              outer->jd,
                                                              outer->varmap,
                                                              varidx);
            }
            inner = outer;
            outer = outer->parent;
      }
}


static void close_prolog_block(inline_node *iln,
                                             basicblock *n_bptr,
                                             inline_node *nextcall)
{
      /* XXX add original outvars! */
      close_block(iln, nextcall, n_bptr, nextcall->n_passthroughcount);

      /* pass-through variables */

      DOLOG( printf("closed prolog block:\n");
               show_basicblock(iln->ctx->resultjd, n_bptr, SHOW_STACK); );
}


static void close_body_block(inline_node *iln,
                                           basicblock *n_bptr,
                                           basicblock *o_bptr,
                                           s4 *varmap,
                                           s4 retcount,
                                           s4 retidx)
{
      s4 i;

      close_block(iln, iln, n_bptr, iln->n_passthroughcount + o_bptr->outdepth + retcount);

      /* translate the outvars of the original block */

      /* XXX reuse code */
      for (i=0; i<o_bptr->outdepth; ++i) {
            n_bptr->outvars[iln->n_passthroughcount + i] =
                  inline_translate_variable(iln->ctx->resultjd, iln->jd, varmap,
                              o_bptr->outvars[i]);
      }

      /* set the return variable, if any */

      if (retcount) {
            assert(retidx >= 0);
            n_bptr->outvars[iln->n_passthroughcount + o_bptr->outdepth] = retidx;
      }
}


/* inlined code generation ****************************************************/

static instruction * inline_instruction(inline_node *iln,
                                                            s4 opcode,
                                                            instruction *o_iptr)
{
      instruction *n_iptr;

      n_iptr = (iln->inlined_iinstr_cursor++);
      assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);

      n_iptr->opc = opcode;
      n_iptr->flags.bits = o_iptr->flags.bits & INS_FLAG_ID_MASK;
      n_iptr->line = o_iptr->line;

      return n_iptr;
}

static void inline_generate_sync_builtin(inline_node *iln,
                                                             inline_node *callee,
                                                             instruction *o_iptr,
                                                             s4 instancevar,
                                                             functionptr func)
{
      int          syncvar;
      instruction *n_ins;

      if (callee->m->flags & ACC_STATIC) {
            /* ACONST */
            syncvar = inline_new_temp_variable(iln->ctx->resultjd, TYPE_ADR);

            n_ins = inline_instruction(iln, ICMD_ACONST, o_iptr);
            n_ins->sx.val.c.cls = callee->m->clazz;
            n_ins->dst.varindex = syncvar;
            n_ins->flags.bits |= INS_FLAG_CLASS;
      }
      else {
            syncvar = instancevar;
      }

      assert(syncvar != UNUSED);

      /* MONITORENTER / MONITOREXIT */

      n_ins = inline_instruction(iln, ICMD_BUILTIN, o_iptr);
      n_ins->sx.s23.s3.bte = builtintable_get_internal(func);
      n_ins->s1.argcount = 1; /* XXX add through-vars */
      n_ins->sx.s23.s2.args = DMNEW(s4, 1);
      n_ins->sx.s23.s2.args[0] = syncvar;
}

static s4 emit_inlining_prolog(inline_node *iln,
                                             inline_node *callee,
                                             instruction *o_iptr,
                                             s4 *varmap)
{
      methodinfo *calleem;
      methoddesc *md;
      int i;
      int localindex;
      int type;
      instruction *n_ins;
      insinfo_inline *insinfo;
      s4 varindex;

      assert(iln && callee && o_iptr);

      calleem = callee->m;
      md = calleem->parseddesc;

      /* INLINE_START instruction */

      n_ins = inline_instruction(iln, ICMD_INLINE_START, o_iptr);

      insinfo = DNEW(insinfo_inline);
      insinfo->method = callee->m;
      insinfo->outer = iln->m;
      insinfo->synclocal = callee->synclocal;
      insinfo->synchronize = callee->synchronize;
      insinfo->javalocals_start = NULL;
      insinfo->javalocals_end = NULL;

      /* info about stack vars live at the INLINE_START */

      insinfo->throughcount = callee->n_passthroughcount;
      insinfo->paramcount = md->paramcount;
      insinfo->stackvarscount = o_iptr->s1.argcount;
      insinfo->stackvars = DMNEW(s4, insinfo->stackvarscount);
      for (i=0; i<insinfo->stackvarscount; ++i)
            insinfo->stackvars[i] = iln->varmap[o_iptr->sx.s23.s2.args[i]];

      /* info about the surrounding inlining */

      if (iln->inline_start_instruction)
            insinfo->parent = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
      else
            insinfo->parent = NULL;

      /* finish the INLINE_START instruction */

      n_ins->sx.s23.s3.inlineinfo = insinfo;
      callee->inline_start_instruction = n_ins;

      DOLOG( printf("%sprolog: ", iln->indent);
               show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );

      /* handle parameters for the inlined callee */

      localindex = callee->localsoffset + md->paramslots;

      for (i=md->paramcount-1; i>=0; --i) {
            assert(iln);

            type = md->paramtypes[i].type;

            localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
            assert(callee->regdata);

            /* translate the argument variable */

            varindex = varmap[o_iptr->sx.s23.s2.args[i]];
            assert(varindex != UNUSED);

            /* remove preallocation from the argument variable */

            iln->ctx->resultjd->var[varindex].flags &= ~(PREALLOC | INMEMORY);

            /* check the instance slot against NULL */
            /* we don't need that for <init> methods, as the verifier  */
            /* ensures that they are only called for an uninit. object */
            /* (which may not be NULL).                                */

            if (!callee->isstatic && i == 0 && calleem->name != utf_init) {
                  assert(type == TYPE_ADR);
                  n_ins = inline_instruction(iln, ICMD_CHECKNULL, o_iptr);
                  n_ins->s1.varindex = varindex;
                  n_ins->dst.varindex = n_ins->s1.varindex;
            }

            /* store argument into local variable of inlined callee */

            if (callee->jd->local_map[5*(localindex - callee->localsoffset) + type] != UNUSED)
            {
                  /* this value is used in the callee */

                  if (i == 0 && callee->synclocal != UNUSED) {
                        /* we also need it for synchronization, so copy it */
                        assert(type == TYPE_ADR);
                        n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
                  }
                  else {
                        n_ins = inline_instruction(iln, ICMD_ISTORE + type, o_iptr);
                        n_ins->sx.s23.s3.javaindex = UNUSED;
                  }
                  n_ins->s1.varindex = varindex;
                  n_ins->dst.varindex = iln->ctx->resultjd->local_map[5*localindex + type];
                  assert(n_ins->dst.varindex != UNUSED);
            }
            else if (i == 0 && callee->synclocal != UNUSED) {
                  /* the value is not used inside the callee, but we need it for */
                  /* synchronization                                             */
                  /* XXX In this case it actually makes no sense to create a     */
                  /*     separate synchronization variable.                      */

                  n_ins = inline_instruction(iln, ICMD_NOP, o_iptr);
            }
            else {
                  /* this value is not used, pop it */

                  n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
                  n_ins->s1.varindex = varindex;
            }

            DOLOG( printf("%sprolog: ", iln->indent);
                     show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
      }

      /* COPY for synchronized instance methods */

      if (callee->synclocal != UNUSED) {
            n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
            n_ins->s1.varindex = varmap[o_iptr->sx.s23.s2.args[0]];
            n_ins->dst.varindex = callee->synclocal;

            assert(n_ins->s1.varindex != UNUSED);
      }

      if (callee->synchronize) {
            inline_generate_sync_builtin(iln, callee, o_iptr,
                                                       (callee->isstatic) ? UNUSED : varmap[o_iptr->sx.s23.s2.args[0]],
                                                       LOCK_monitor_enter);
      }

      /* INLINE_BODY instruction */

      n_ins = inline_instruction(iln, ICMD_INLINE_BODY, callee->jd->basicblocks[0].iinstr);
      n_ins->sx.s23.s3.inlineinfo = insinfo;

      return 0; /* XXX */
}


static void emit_inlining_epilog(inline_node *iln, inline_node *callee, instruction *o_iptr)
{
      instruction *n_ins;
      s4          *jl;

      assert(iln && callee && o_iptr);
      assert(callee->inline_start_instruction);

      if (callee->synchronize) {
            inline_generate_sync_builtin(iln, callee, o_iptr,
                                                       callee->synclocal,
                                                       LOCK_monitor_exit);
      }

      /* INLINE_END instruction */

      n_ins = inline_instruction(iln, ICMD_INLINE_END, o_iptr);
      n_ins->sx.s23.s3.inlineinfo = callee->inline_start_instruction->sx.s23.s3.inlineinfo;

      /* set the javalocals */

      jl = DMNEW(s4, iln->jd->maxlocals);
      MCOPY(jl, iln->javalocals, s4, iln->jd->maxlocals);
      n_ins->sx.s23.s3.inlineinfo->javalocals_end = jl;

      DOLOG( printf("%sepilog: ", iln->indent);
               show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
}


#define TRANSLATE_VAROP(vo)  \
      n_iptr->vo.varindex = inline_translate_variable(jd, origjd, varmap, n_iptr->vo.varindex)


static void inline_clone_instruction(inline_node *iln,
                                                       jitdata *jd,
                                                       jitdata *origjd,
                                                       s4 *varmap,
                                                       instruction *o_iptr,
                                                       instruction *n_iptr)
{
      icmdtable_entry_t *icmdt;
      builtintable_entry *bte;
      methoddesc *md;
      s4 i, j;
      branch_target_t *table;
      lookup_target_t *lookup;
      inline_node *scope;

      *n_iptr = *o_iptr;

      icmdt = &(icmd_table[o_iptr->opc]);

      switch (icmdt->dataflow) {
            case DF_0_TO_0:
                  break;

            case DF_3_TO_0:
                  TRANSLATE_VAROP(sx.s23.s3);
            case DF_2_TO_0:
                  TRANSLATE_VAROP(sx.s23.s2);
            case DF_1_TO_0:
                  TRANSLATE_VAROP(s1);
                  break;

            case DF_2_TO_1:
                  TRANSLATE_VAROP(sx.s23.s2);
            case DF_1_TO_1:
            case DF_COPY:
            case DF_MOVE:
                  TRANSLATE_VAROP(s1);
            case DF_0_TO_1:
                  TRANSLATE_VAROP(dst);
                  break;

            case DF_N_TO_1:
                  n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
                  for (i=0; i<n_iptr->s1.argcount; ++i) {
                        n_iptr->sx.s23.s2.args[i] =
                              inline_translate_variable(jd, origjd, varmap,
                                          o_iptr->sx.s23.s2.args[i]);
                  }
                  TRANSLATE_VAROP(dst);
                  break;

            case DF_INVOKE:
                  INSTRUCTION_GET_METHODDESC(n_iptr, md);
clone_call:
                  n_iptr->s1.argcount += iln->n_passthroughcount;
                  n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
                  for (i=0; i<o_iptr->s1.argcount; ++i) {
                        n_iptr->sx.s23.s2.args[i] =
                              inline_translate_variable(jd, origjd, varmap,
                                          o_iptr->sx.s23.s2.args[i]);
                  }
                  for (scope = iln; scope != NULL; scope = scope->parent) {
                        for (j = 0; j < scope->n_selfpassthroughcount; ++j) {
                              n_iptr->sx.s23.s2.args[i++] =
                                    scope->parent->varmap[scope->n_passthroughvars[j]];
                        }
                  }
                  if (md->returntype.type != TYPE_VOID)
                        TRANSLATE_VAROP(dst);
                  break;

            case DF_BUILTIN:
                  bte = n_iptr->sx.s23.s3.bte;
                  md = bte->md;
                  goto clone_call;

            default:
                  assert(0);
      }

      switch (icmdt->controlflow) {
            case CF_RET:
                  TRANSLATE_VAROP(s1); /* XXX should be handled by data-flow */
                  /* FALLTHROUGH */
            case CF_IF:
            case CF_GOTO:
                  inline_add_block_reference(iln, &(n_iptr->dst.block));
                  break;

            case CF_JSR:
                  inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.jsrtarget.block));
                  break;

            case CF_TABLE:
                  i = n_iptr->sx.s23.s3.tablehigh - n_iptr->sx.s23.s2.tablelow + 1 + 1 /* default */;

                  table = DMNEW(branch_target_t, i);
                  MCOPY(table, o_iptr->dst.table, branch_target_t, i);
                  n_iptr->dst.table = table;

                  while (--i >= 0) {
                        inline_add_block_reference(iln, &(table->block));
                        table++;
                  }
                  break;

            case CF_LOOKUP:
                  inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.lookupdefault.block));

                  i = n_iptr->sx.s23.s2.lookupcount;
                  lookup = DMNEW(lookup_target_t, i);
                  MCOPY(lookup, o_iptr->dst.lookup, lookup_target_t, i);
                  n_iptr->dst.lookup = lookup;

                  while (--i >= 0) {
                        inline_add_block_reference(iln, &(lookup->target.block));
                        lookup++;
                  }
                  break;
      }

      /* XXX move this to dataflow section? */

      switch (n_iptr->opc) {
            case ICMD_ASTORE:
#if 0
                  if (n_iptr->flags.bits & INS_FLAG_RETADDR)
                        inline_add_blocknr_reference(iln, &(n_iptr->sx.s23.s2.retaddrnr));
#endif
                  /* FALLTHROUGH! */
            case ICMD_ISTORE:
            case ICMD_LSTORE:
            case ICMD_FSTORE:
            case ICMD_DSTORE:
                  stack_javalocals_store(n_iptr, iln->javalocals);
                  break;
      }
}


static void inline_rewrite_method(inline_node *iln)
{
      basicblock *o_bptr;
      s4 len;
      instruction *o_iptr;
      instruction *n_iptr;
      inline_node *nextcall;
      basicblock *n_bptr;
      inline_block_map *bm;
      int i;
      int icount;
      jitdata *resultjd;
      jitdata *origjd;
      char indent[100]; /* XXX debug */
      s4 retcount;
      s4 retidx;

      assert(iln);

      resultjd = iln->ctx->resultjd;
      origjd = iln->jd;

      n_bptr = NULL;
      nextcall = iln->children;

      /* XXX debug */
      for (i=0; i<iln->depth; ++i)
            indent[i] = '\t';
      indent[i] = 0;
      iln->indent = indent;

      DOLOG( printf("%srewriting: ", indent); method_println(iln->m);
               printf("%s(passthrough: %d+%d)\n",
                        indent, iln->n_passthroughcount - iln->n_selfpassthroughcount,
                        iln->n_passthroughcount); );

      /* set memory cursors */

      iln->inlined_iinstr_cursor = iln->inlined_iinstr;
      iln->inlined_basicblocks_cursor = iln->inlined_basicblocks;

      /* allocate temporary buffers */

      iln->javalocals = DMNEW(s4, iln->jd->maxlocals);

      /* loop over basic blocks */

      o_bptr = iln->jd->basicblocks;
      for (; o_bptr; o_bptr = o_bptr->next) {

            if (o_bptr->flags < BBREACHED) {

                  /* ignore the dummy end block */

                  if (o_bptr->icount == 0 && o_bptr->next == NULL) {
                        /* enter the following block as translation, for exception handler ranges */
                        inline_block_translation(iln, o_bptr, iln->inlined_basicblocks_cursor);
                        continue;
                  }

                  DOLOG(
                  printf("%s* skipping old L%03d (flags=%d, type=%d, oid=%d) of ",
                              indent,
                              o_bptr->nr, o_bptr->flags, o_bptr->type,
                              o_bptr->indepth);
                  method_println(iln->m);
                  );

                  n_bptr = create_body_block(iln, o_bptr, iln->varmap);

                  /* enter it in the blockmap */

                  inline_block_translation(iln, o_bptr, n_bptr);

                  close_body_block(iln, n_bptr, o_bptr, iln->varmap, 0, -1);
                  continue;
            }

            len = o_bptr->icount;
            o_iptr = o_bptr->iinstr;

            DOLOG(
            printf("%s* rewriting old L%03d (flags=%d, type=%d, oid=%d) of ",
                        indent,
                        o_bptr->nr, o_bptr->flags, o_bptr->type,
                        o_bptr->indepth);
            method_println(iln->m);
            show_basicblock(iln->jd, o_bptr, SHOW_STACK);
            );

            if (iln->blockbefore || o_bptr != iln->jd->basicblocks) {
                  /* create an inlined clone of this block */

                  n_bptr = create_body_block(iln, o_bptr, iln->varmap);
                  icount = 0;

                  /* enter it in the blockmap */

                  inline_block_translation(iln, o_bptr, n_bptr);

                  /* initialize the javalocals */

                  MCOPY(iln->javalocals, n_bptr->javalocals, s4, iln->jd->maxlocals);
            }
            else {
                  s4 *jl;

                  /* continue caller block */

                  n_bptr = iln->inlined_basicblocks_cursor - 1;
                  icount = n_bptr->icount;

                  /* translate the javalocals */

                  jl = translate_javalocals(iln, o_bptr->javalocals);
                  iln->inline_start_instruction->sx.s23.s3.inlineinfo->javalocals_start = jl;

                  MCOPY(iln->javalocals, jl, s4, iln->jd->maxlocals);
            }

            /* iterate over the ICMDs of this block */

            retcount = 0;
            retidx = UNUSED;

            while (--len >= 0) {

                  DOLOG( fputs(indent, stdout); show_icmd(iln->jd, o_iptr, false,  SHOW_STACK);
                           printf("\n") );

                  /* handle calls that will be inlined */

                  if (nextcall && o_iptr == nextcall->callerins) {

                        /* write the inlining prolog */

                        (void) emit_inlining_prolog(iln, nextcall, o_iptr, iln->varmap);
                        icount += nextcall->prolog_instructioncount;

                        /* end current block, or glue blocks together */

                        n_bptr->icount = icount;

                        if (nextcall->blockbefore) {
                              close_prolog_block(iln, n_bptr, nextcall);
                        }
                        else {
                              /* XXX */
                        }

                        /* check if the result is a local variable */

                        if (nextcall->m->parseddesc->returntype.type != TYPE_VOID
                                    && o_iptr->dst.varindex < iln->jd->localcount)
                        {
                              nextcall->n_resultlocal = iln->varmap[o_iptr->dst.varindex];
                        }
                        else
                              nextcall->n_resultlocal = -1;

                        /* set memory pointers in the callee */

                        nextcall->inlined_iinstr = iln->inlined_iinstr_cursor;
                        nextcall->inlined_basicblocks = iln->inlined_basicblocks_cursor;

                        /* recurse */

                        DOLOG( printf("%sentering inline ", indent);
                                 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );

                        inline_rewrite_method(nextcall);

                        DOLOG( printf("%sleaving inline ", indent);
                                 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );

                        /* update memory cursors */

                        assert(nextcall->inlined_iinstr_cursor
                                    <= iln->inlined_iinstr_cursor + nextcall->cumul_instructioncount);
                        assert(nextcall->inlined_basicblocks_cursor
                                    == iln->inlined_basicblocks_cursor + nextcall->cumul_basicblockcount);
                        iln->inlined_iinstr_cursor = nextcall->inlined_iinstr_cursor;
                        iln->inlined_basicblocks_cursor = nextcall->inlined_basicblocks_cursor;

                        /* start new block, or glue blocks together */

                        if (nextcall->blockafter) {
                              n_bptr = create_epilog_block(iln, nextcall, iln->varmap);
                              icount = 0;
                        }
                        else {
                              n_bptr = iln->inlined_basicblocks_cursor - 1;
                              icount = n_bptr->icount;
                              /* XXX */
                        }

                        /* emit inlining epilog */

                        emit_inlining_epilog(iln, nextcall, o_iptr);
                        icount += nextcall->epilog_instructioncount;

                        /* proceed to next call */

                        nextcall = nextcall->next;
                  }
                  else {
                        n_iptr = (iln->inlined_iinstr_cursor++);
                        assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);

                        switch (o_iptr->opc) {
                              case ICMD_RETURN:
                                    if (iln->depth == 0)
                                          goto default_clone;
                                    goto return_tail;

                              case ICMD_IRETURN:
                              case ICMD_ARETURN:
                              case ICMD_LRETURN:
                              case ICMD_FRETURN:
                              case ICMD_DRETURN:
                                    if (iln->depth == 0)
                                          goto default_clone;
                                    retcount = 1;
                                    retidx = iln->varmap[o_iptr->s1.varindex];
                                    if (iln->n_resultlocal != -1) {
                                          /* store result in a local variable */

                                          DOLOG( printf("USING RESULTLOCAL %d\n", iln->n_resultlocal); );
                                          /* This relies on the same sequence of types for */
                                          /* ?STORE and ?RETURN opcodes.                   */
                                          n_iptr->opc = ICMD_ISTORE + (o_iptr->opc - ICMD_IRETURN);
                                          n_iptr->s1.varindex = retidx;
                                          n_iptr->dst.varindex = iln->n_resultlocal;
                                          n_iptr->sx.s23.s3.javaindex = UNUSED; /* XXX set real javaindex? */

                                          retcount = 0;
                                          retidx = UNUSED;

                                          n_iptr = (iln->inlined_iinstr_cursor++);
                                          assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
                                          icount++;
                                    }
                                    else if ((retidx < resultjd->localcount && iln->blockafter)
                                                || !iln->blockafter) /* XXX do we really always need the MOVE? */
                                    {
                                          /* local must not become outvar, insert a MOVE */

                                          n_iptr->opc = ICMD_MOVE;
                                          n_iptr->s1.varindex = retidx;
                                          retidx = inline_new_temp_variable(resultjd,
                                                                                            resultjd->var[retidx].type);
                                          n_iptr->dst.varindex = retidx;

                                          n_iptr = (iln->inlined_iinstr_cursor++);
                                          assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
                                          icount++;
                                    }
return_tail:
                                    if (iln->blockafter) {
                                          n_iptr->opc = ICMD_GOTO;
                                          n_iptr->dst.block = INLINE_RETURN_REFERENCE(iln);
                                          inline_add_block_reference(iln, &(n_iptr->dst.block));
                                    }
                                    else {
                                          n_iptr->opc = ICMD_NOP;
                                    }
                                    break;
#if 0
                                    if (o_bptr->next == NULL || (o_bptr->next->icount==0 && o_bptr->next->next == NULL)) {
                                          n_iptr->opc = ICMD_NOP;
                                          break;
                                    }
                                    goto default_clone;
                                    break;
#endif

                              default:
default_clone:
                                    inline_clone_instruction(iln, resultjd, iln->jd, iln->varmap, o_iptr, n_iptr);
                        }

                        DOLOG( fputs(indent, stdout); show_icmd(resultjd, n_iptr, false, SHOW_STACK);
                                 printf("\n"););

                        icount++;
                  }

                  o_iptr++;
            }

            /* end of basic block */

            if (iln->blockafter || (o_bptr->next && o_bptr->next->next)) {
                  close_body_block(iln, n_bptr, o_bptr, iln->varmap, retcount, retidx);
                  n_bptr->icount = icount;

                  DOLOG( printf("closed body block:\n");
                           show_basicblock(resultjd, n_bptr, SHOW_STACK); );
            }
            else {
                  n_bptr->icount = icount;
                  assert(iln->parent);
                  if (retidx != UNUSED)
                        iln->parent->varmap[iln->callerins->dst.varindex] = retidx;
            }
      }

      bm = iln->ctx->blockmap;
      for (i=0; i<iln->ctx->blockmap_index; ++i, ++bm) {
            assert(bm->iln && bm->o_block && bm->n_block);
            if (bm->iln == iln)
                  inline_resolve_block_refs(&(iln->refs), bm->o_block, bm->n_block, false);
      }

#if !defined(NDEBUG)
      if (iln->refs) {
            inline_target_ref *ref;
            ref = iln->refs;
            while (ref) {
                  if (!iln->depth || ref->isnumber || *(ref->ref.block) != INLINE_RETURN_REFERENCE(iln)) {
                        DOLOG( printf("XXX REMAINING REF at depth %d: %p\n", iln->depth,
                                 (void*)*(ref->ref.block)) );
                        assert(false);
                  }
                  ref = ref->next;
            }
      }
#endif
}


static exception_entry * inline_exception_tables(inline_node *iln,
                                                                         exception_entry *n_extable,
                                                                         exception_entry **prevextable)
{
      inline_node *child;
      inline_node *scope;
      exception_entry *et;

      assert(iln);
      assert(n_extable);
      assert(prevextable);

      child = iln->children;
      if (child) {
            do {
                  n_extable = inline_exception_tables(child, n_extable, prevextable);
                  child = child->next;
            } while (child != iln->children);
      }

      et = iln->jd->exceptiontable;
      for (; et != NULL; et = et->down) {
            assert(et);
            MZERO(n_extable, exception_entry, 1);
            n_extable->start     = inline_map_block(iln, et->start  , iln);
            n_extable->end       = inline_map_block(iln, et->end    , iln);
            n_extable->handler   = inline_map_block(iln, et->handler, iln);
            n_extable->catchtype = et->catchtype;

            if (*prevextable) {
                  (*prevextable)->down = n_extable;
            }
            *prevextable = n_extable;

            n_extable++;
      }

      if (iln->handler_monitorexit) {
            exception_entry **activehandlers;

            MZERO(n_extable, exception_entry, 1);
            n_extable->start   = iln->inlined_basicblocks;
            n_extable->end     = iln->inlined_basicblocks_cursor;
            n_extable->handler = iln->handler_monitorexit;
            n_extable->catchtype.any = NULL; /* finally */

            if (*prevextable) {
                  (*prevextable)->down = n_extable;
            }
            *prevextable = n_extable;

            n_extable++;

            /* We have to protect the created handler with the same handlers */
            /* that protect the method body itself.                          */

            for (scope = iln; scope->parent != NULL; scope = scope->parent) {

                  activehandlers = scope->o_handlers;
                  assert(activehandlers);

                  while (*activehandlers) {

                        assert(scope->parent);

                        MZERO(n_extable, exception_entry, 1);
                        n_extable->start     = iln->handler_monitorexit;
                        n_extable->end       = iln->handler_monitorexit + 1; /* XXX ok in this case? */
                        n_extable->handler   = inline_map_block(scope->parent,
                                                                                    (*activehandlers)->handler,
                                                                                    scope->parent);
                        n_extable->catchtype = (*activehandlers)->catchtype;

                        if (*prevextable) {
                              (*prevextable)->down = n_extable;
                        }
                        *prevextable = n_extable;

                        n_extable++;
                        activehandlers++;
                  }
            }
      }

      return n_extable;
}


static void inline_locals(inline_node *iln)
{
      inline_node *child;

      assert(iln);

      iln->varmap = create_variable_map(iln);

      child = iln->children;
      if (child) {
            do {
                  inline_locals(child);
                  child = child->next;
            } while (child != iln->children);
      }

      if (iln->regdata->memuse > iln->ctx->resultjd->rd->memuse)
            iln->ctx->resultjd->rd->memuse = iln->regdata->memuse;
      if (iln->regdata->argintreguse > iln->ctx->resultjd->rd->argintreguse)
            iln->ctx->resultjd->rd->argintreguse = iln->regdata->argintreguse;
      if (iln->regdata->argfltreguse > iln->ctx->resultjd->rd->argfltreguse)
            iln->ctx->resultjd->rd->argfltreguse = iln->regdata->argfltreguse;
}


static void inline_interface_variables(inline_node *iln)
{
      basicblock *bptr;
      jitdata *resultjd;
      s4 i;
      varinfo *v;

      resultjd = iln->ctx->resultjd;

      resultjd->interface_map = DMNEW(interface_info, 5*iln->ctx->maxinoutdepth);
      for (i=0; i<5*iln->ctx->maxinoutdepth; ++i)
            resultjd->interface_map[i].flags = UNUSED;

      for (bptr = resultjd->basicblocks; bptr != NULL; bptr = bptr->next) {
            assert(bptr->indepth  <= iln->ctx->maxinoutdepth);
            assert(bptr->outdepth <= iln->ctx->maxinoutdepth);

            for (i=0; i<bptr->indepth; ++i) {
                  v = &(resultjd->var[bptr->invars[i]]);
                  v->flags |= INOUT;
                  if (v->type == TYPE_RET)
                        v->flags |= PREALLOC;
                  else
                        v->flags &= ~PREALLOC;
                  v->flags &= ~INMEMORY;
                  assert(bptr->invars[i] >= resultjd->localcount);

                  if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
                        resultjd->interface_map[5*i + v->type].flags = v->flags;
                  }
                  else {
                        resultjd->interface_map[5*i + v->type].flags |= v->flags;
                  }
            }

            for (i=0; i<bptr->outdepth; ++i) {
                  v = &(resultjd->var[bptr->outvars[i]]);
                  v->flags |= INOUT;
                  if (v->type == TYPE_RET)
                        v->flags |= PREALLOC;
                  else
                        v->flags &= ~PREALLOC;
                  v->flags &= ~INMEMORY;
                  assert(bptr->outvars[i] >= resultjd->localcount);

                  if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
                        resultjd->interface_map[5*i + v->type].flags = v->flags;
                  }
                  else {
                        resultjd->interface_map[5*i + v->type].flags |= v->flags;
                  }
            }
      }
}


static void inline_write_exception_handlers(inline_node *master, inline_node *iln)
{
      basicblock *n_bptr;
      instruction *n_ins;
      inline_node *child;
      builtintable_entry *bte;
      s4 exvar;
      s4 syncvar;
      s4 i;

      child = iln->children;
      if (child) {
            do {
                  inline_write_exception_handlers(master, child);
                  child = child->next;
            } while (child != iln->children);
      }

      if (iln->synchronize) {
            /* create the monitorexit handler */
            n_bptr = create_block(master, iln, iln,
                                            iln->n_passthroughcount + 1);
            n_bptr->type = BBTYPE_EXH;
            n_bptr->flags = BBFINISHED;

            exvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
            n_bptr->invars[iln->n_passthroughcount] = exvar;

            iln->handler_monitorexit = n_bptr;

            /* ACONST / ALOAD */

            n_ins = master->inlined_iinstr_cursor++;
            if (iln->m->flags & ACC_STATIC) {
                  n_ins->opc = ICMD_ACONST;
                  n_ins->sx.val.c.cls = iln->m->clazz;
                  n_ins->flags.bits = INS_FLAG_CLASS;
            }
            else {
                  n_ins->opc = ICMD_ALOAD;
                  n_ins->s1.varindex = iln->synclocal;
                  assert(n_ins->s1.varindex != UNUSED);
            }
            /* XXX could be PREALLOCed for  builtin call */
            syncvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
            n_ins->dst.varindex = syncvar;
            n_ins->line = 0;

            /* MONITOREXIT */

            bte = builtintable_get_internal(LOCK_monitor_exit);

            n_ins = master->inlined_iinstr_cursor++;
            n_ins->opc = ICMD_BUILTIN;
            n_ins->s1.argcount = 1 + iln->n_passthroughcount + 1;
            n_ins->sx.s23.s2.args = DMNEW(s4, n_ins->s1.argcount);
            n_ins->sx.s23.s2.args[0] = syncvar;
            for (i=0; i < iln->n_passthroughcount + 1; ++i) {
                  n_ins->sx.s23.s2.args[1 + i] = n_bptr->invars[i];
            }
            n_ins->sx.s23.s3.bte = bte;
            n_ins->line = 0;

            /* ATHROW */

            n_ins = master->inlined_iinstr_cursor++;
            n_ins->opc = ICMD_ATHROW;
            n_ins->flags.bits = 0;
            n_ins->s1.varindex = exvar;
            n_ins->line = 0;

            /* close basic block */

            close_block(iln, iln, n_bptr, iln->n_passthroughcount);
            n_bptr->icount = 3;
      }
}


/* second pass driver *********************************************************/

static bool inline_transform(inline_node *iln, jitdata *jd)
{
      instruction *n_ins;
      basicblock *n_bb;
      basicblock *n_bptr;
      exception_entry *n_ext;
      exception_entry *prevext;
      codegendata *n_cd;
      jitdata *n_jd;
      s4 i;
#if defined(INLINE_VERIFY_RESULT)
      static int debug_verify_inlined_code = 1;
#endif
#if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
      static int debug_counter = 0;
#endif

      DOLOG( dump_inline_tree(iln, 0); );

      assert(iln && jd);

      n_ins = DMNEW(instruction, iln->cumul_instructioncount);
      MZERO(n_ins, instruction, iln->cumul_instructioncount);
      iln->inlined_iinstr = n_ins;

      n_bb = DMNEW(basicblock, iln->cumul_basicblockcount);
      MZERO(n_bb, basicblock, iln->cumul_basicblockcount);
      iln->inlined_basicblocks = n_bb;

      iln->ctx->blockmap = DMNEW(inline_block_map, iln->cumul_blockmapcount);

      n_jd = jit_jitdata_new(iln->m);
      n_jd->flags = jd->flags;
      n_jd->code->optlevel = jd->code->optlevel;
      iln->ctx->resultjd = n_jd;

      reg_setup(n_jd);

      /* create the local_map */

      n_jd->local_map = DMNEW(s4, 5*iln->cumul_maxlocals);
      for (i=0; i<5*iln->cumul_maxlocals; ++i)
            n_jd->local_map[i] = UNUSED;

      /* create / coalesce local variables */

      n_jd->varcount = 0;
      n_jd->vartop = 0;
      n_jd->var = NULL;

      inline_locals(iln);

      n_jd->localcount = n_jd->vartop;

      /* extra variables for verification (debugging) */

#if defined(INLINE_VERIFY_RESULT)
      if (debug_verify_inlined_code) {
            n_jd->vartop   += VERIFIER_EXTRA_LOCALS + VERIFIER_EXTRA_VARS + 100 /* XXX m->maxstack */;
            if (n_jd->vartop > n_jd->varcount) {
                  /* XXX why? */
                  n_jd->var = DMREALLOC(n_jd->var, varinfo, n_jd->varcount, n_jd->vartop);
                  n_jd->varcount = n_jd->vartop;
            }
      }
#endif /* defined(INLINE_VERIFY_RESULT) */

      /* write inlined code */

      inline_rewrite_method(iln);

      /* create exception handlers */

      inline_write_exception_handlers(iln, iln);

      /* write the dummy end block */

      n_bptr = create_block(iln, iln, iln, 0);
      n_bptr->flags = BBUNDEF;
      n_bptr->type = BBTYPE_STD;

      /* store created code in jitdata */

      n_jd->basicblocks = iln->inlined_basicblocks;
      n_jd->instructioncount = iln->cumul_instructioncount;
      n_jd->instructions = iln->inlined_iinstr;

      /* link the basic blocks (dummy end block is not counted) */

      n_jd->basicblockcount = (iln->inlined_basicblocks_cursor - iln->inlined_basicblocks) - 1;
      for (i=0; i<n_jd->basicblockcount + 1; ++i)
            n_jd->basicblocks[i].next = &(n_jd->basicblocks[i+1]);
      if (i)
            n_jd->basicblocks[i-1].next = NULL;

      /* check basicblock numbers */

#if !defined(NDEBUG)
      jit_check_basicblock_numbers(n_jd);
#endif

      /* create the exception table */

      if (iln->cumul_exceptiontablelength) {
            exception_entry *tableend;

            n_ext = DMNEW(exception_entry, iln->cumul_exceptiontablelength);
            prevext = NULL;
            tableend = inline_exception_tables(iln, n_ext, &prevext);
            assert(tableend == n_ext + iln->cumul_exceptiontablelength);
            if (prevext)
                  prevext->down = NULL;

            n_jd->exceptiontablelength = iln->cumul_exceptiontablelength;
            n_jd->exceptiontable = n_ext;
      }
      else {
            n_ext = NULL;
      }

      /*******************************************************************************/

      n_cd = n_jd->cd;
      memcpy(n_cd, jd->cd, sizeof(codegendata));

      n_cd->method = NULL; /* XXX */
      n_jd->maxlocals = iln->cumul_maxlocals;
      n_jd->maxinterfaces = iln->ctx->maxinoutdepth;

      inline_post_process(n_jd);

      inline_interface_variables(iln);

      /* for debugging, verify the inlined result */

#if defined(INLINE_VERIFY_RESULT)
      if (debug_verify_inlined_code) {
            debug_verify_inlined_code = 0;
            DOLOG( printf("VERIFYING INLINED RESULT...\n"); fflush(stdout); );
            if (!typecheck(n_jd)) {
                  exceptions_clear_exception();
                  DOLOG( printf("XXX INLINED RESULT DID NOT PASS VERIFIER XXX\n") );
                  return false;
            }
            else {
                  DOLOG( printf("VERIFICATION PASSED.\n") );
            }
            debug_verify_inlined_code = 1;
      }
#endif /* defined(INLINE_VERIFY_RESULT) */

      /* we need bigger free memory stacks (XXX these should not be allocated in reg_setup) */

      n_jd->rd->freemem = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
#if defined(HAS_4BYTE_STACKSLOT)
      n_jd->rd->freemem_2 = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
#endif

#if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
      if (   (n_jd->instructioncount >= opt_InlineMinSize)
            && (n_jd->instructioncount <= opt_InlineMaxSize))
      {
         if (debug_counter < opt_InlineCount)
#endif /* defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG) */
         {
                  /* install the inlined result */

                  *jd->code = *n_jd->code;
                  n_jd->code = jd->code;
                  *jd = *n_jd;

                  /* statistics and logging */

#if !defined(NDEBUG)
                  inline_stat_roots++;

                  DOLOG_SHORT(
                  printf("==== %d.INLINE ==================================================================\n",
                        debug_counter);
                  printf("\ninline tree:\n");
                  dump_inline_tree(iln, 0);
                  n_jd->flags |= JITDATA_FLAG_SHOWINTERMEDIATE | JITDATA_FLAG_SHOWDISASSEMBLE;
                  /* debug_dump_inlined_code(iln, n_method, n_cd, n_rd); */
                  printf("-------- DONE -----------------------------------------------------------\n");
                  fflush(stdout);
                  );
#endif
         }

#if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
            debug_counter++;
      }
#endif
      return true;
}


/******************************************************************************/
/* FIRST PASS: build inlining tree                                            */
/******************************************************************************/


/* inline_pre_parse_heuristics *************************************************

   Perform heuristic checks whether a call site should be inlined.
   These checks are evaluated before the callee has been parsed and analysed.

   IN:
       caller...........inlining node of the caller
         callee...........the called method
         site.............information on the call site

   RETURN VALUE:
       true........consider for inlining
         false.......don't inline

*******************************************************************************/

static bool inline_pre_parse_heuristics(const inline_node *caller,
                                                            const methodinfo *callee,
                                                            inline_site *site)
{
#if defined(INLINE_MAX_DEPTH)
      if (caller->depth >= INLINE_MAX_DEPTH)
            return false;
#endif

      return true;
}


/* inline_post_parse_heuristics ************************************************

   Perform heuristic checks whether a call site should be inlined.
   These checks are evaluated after the callee has been parsed and analysed.

   IN:
       caller...........inlining node of the caller (const)
         callee...........the called method (const)

   RETURN VALUE:
         true........consider for inlining
         false.......don't inline

*******************************************************************************/

static bool inline_post_parse_heuristics(const inline_node *caller,
                                                             const inline_node *callee)
{
      return true;
}


/* inline_afterwards_heuristics ************************************************

   Perform heuristic checks whether a call site should be inlined.
   These checks are evaluated after the inlining plan for the callee has
   been made.

   IN:
       caller...........inlining node of the caller (const)
         callee...........the called method (const)

   RETURN VALUE:
         true........consider for inlining
         false.......don't inline

*******************************************************************************/

static bool inline_afterwards_heuristics(const inline_node *caller,
                                                             const inline_node *callee)
{
      inline_node *cumulator;

#if defined(INLINE_DEPTH_FIRST)
      cumulator = caller;
#else
      cumulator = caller->ctx->master;
#endif

      if (0
#if defined(INLINE_MAX_BLOCK_EXPANSION)
            || (cumulator->cumul_basicblockcount + callee->cumul_basicblockcount
                  > INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
#endif
#if defined(INLINE_MAX_ICMD_EXPANSION)
            || (cumulator->cumul_instructioncount + callee->cumul_instructioncount
                  > INLINE_MAX_ICMD_EXPANSION*caller->ctx->master->jd->instructioncount)
#endif
         )
      {
            return false;
      }

      return true;
}


/* inline_is_monomorphic *******************************************************

   Check if the given call site can be proven to be monomorphic.

   IN:
         callee...........the called method
         call.............the invocation instruction

   OUT:
       site->speculative.....flags whether the inlining is speculative
                               (only defined if return value is true)

   RETURN VALUE:
       true if the call site is (currently) monomorphic,
         false if not or unknown

*******************************************************************************/

static bool inline_is_monomorphic(const methodinfo *callee,
                                                  const instruction *call,
                                                  inline_site *site)
{
      if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)
                        || call->opc == ICMD_INVOKESPECIAL))
      {
            site->speculative = false;
            return true;
      }

      /* XXX search single implementation for abstract monomorphics */

      if ((callee->flags & (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED
                              | ACC_ABSTRACT))
                  == (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED))
      {
            if (1) {
                  DOLOG( printf("SPECULATIVE INLINE: "); method_println((methodinfo*)callee); );
                  site->speculative = true;

                  return true;
            }
      }

      /* possibly polymorphic call site */

      return false;
}


/* inline_can_inline ***********************************************************

   Check if inlining of the given call site is possible.

   IN:
       caller...........inlining node of the caller
         callee...........the called method
         call.............the invocation instruction

   OUT:
       site->speculative.....flags whether the inlining is speculative
                               (only defined if return value is true)

   RETURN VALUE:
       true if inlining is possible, false if not

*******************************************************************************/

static bool inline_can_inline(const inline_node *caller,
                                            const methodinfo *callee,
                                            const instruction *call,
                                            inline_site *site)
{
      const inline_node *active;

      /* cannot inline native methods */

      if (callee->flags & ACC_NATIVE)
            return false;

      /* cannot inline possibly polymorphic calls */

      if (!inline_is_monomorphic(callee, call, site))
            return false;

      /* cannot inline recursive calls */

      for (active = caller; active; active = active->parent) {
            if (callee == active->m) {
                  DOLOG( printf("RECURSIVE!\n") );
                  return false;
            }
      }

      /* inlining is possible */

      return true;
}


/* inline_create_callee_node ***************************************************

   Create an inlining node for the given callee.

   IN:
         caller...........inlining node of the caller (const)
         callee...........the called method

   RETURN VALUE:
       the new inlining node

*******************************************************************************/

static inline_node * inline_create_callee_node(const inline_node *caller,
                                                                     methodinfo *callee)
{
      inline_node *cn;              /* the callee inline_node */

      cn = DNEW(inline_node);
      MZERO(cn, inline_node, 1);

      cn->depth = caller->depth + 1;
      cn->ctx = caller->ctx;
      cn->m = callee;
      cn->synchronize = (callee->flags & ACC_SYNCHRONIZED);
      cn->isstatic = (callee->flags & ACC_STATIC);

      return cn;
}


/* inline_set_callee_properties ************************************************

   Set properties of the inlined call site.

   IN:
       caller...........inlining node of the caller (const)
         cn...............the called method
         site.............info about the call site (const)

   OUT:
       *cn..............has the properties set

*******************************************************************************/

static void inline_set_callee_properties(const inline_node *caller,
                                                             inline_node *cn,
                                                             const inline_site *site)
{
      s4           argi;
      s4           i, j;
      basicblock  *bptr;

      /* set info about the call site */

      cn->callerblock = site->bptr;
      cn->callerins = site->iptr;
      cn->callerpc = site->pc;
      cn->o_handlers = site->handlers;
      cn->n_handlercount = caller->n_handlercount + site->nhandlers;

      /* determine if we need basic block boundaries before/after */

      cn->blockbefore = false;
      cn->blockafter = false;

      if (cn->jd->branchtoentry)
            cn->blockbefore = true;

      if (cn->jd->branchtoend)
            cn->blockafter = true;

      if (cn->jd->returncount > 1)
            cn->blockafter = true;

      /* XXX make safer and reusable (maybe store last real block) */
      for (bptr = cn->jd->basicblocks; bptr && bptr->next && bptr->next->next; bptr = bptr->next)
            ;

      if (cn->jd->returnblock != bptr)
            cn->blockafter = true;

      /* info about the callee */

      cn->localsoffset = caller->localsoffset + caller->m->maxlocals;
      cn->prolog_instructioncount = cn->m->parseddesc->paramcount + 2;
      cn->epilog_instructioncount = 1; /* INLINE_END */
      cn->extra_instructioncount = 0;

      /* we need a CHECKNULL for instance methods, except for <init> */

      if (!cn->isstatic && cn->m->name != utf_init)
            cn->prolog_instructioncount += 1;

      /* deal with synchronized callees */

      if (cn->synchronize) {
            methoddesc         *md;
            builtintable_entry *bte;

            /* we need basic block boundaries because of the handler */

            cn->blockbefore = true;
            cn->blockafter = true;

            /* for synchronized static methods                 */
            /* we need an ACONST, MONITORENTER in the prolog   */
            /* and ACONST, MONITOREXIT in the epilog           */

            /* for synchronized instance methods               */
            /* we need an COPY, MONITORENTER in the prolog     */
            /* and MONITOREXIT in the epilog                   */

            if (cn->isstatic) {
                  cn->prolog_instructioncount += 2;
                  cn->epilog_instructioncount += 2;
            }
            else {
                  cn->prolog_instructioncount += 2;
                  cn->epilog_instructioncount += 1;
                  cn->localsoffset += 1;
            }

            /* and exception handler */
            /* ALOAD, builtin_monitorexit, ATHROW */

            cn->extra_instructioncount += 3;

            /* exception table entries */

            cn->extra_exceptiontablelength = 1 + cn->n_handlercount;

            /* add exception handler block */

            cn->cumul_basicblockcount_root++;

            /* we must call the builtins */

            bte = builtintable_get_internal(LOCK_monitor_enter);
            md = bte->md;
            if (md->memuse > cn->regdata->memuse)
                  cn->regdata->memuse = md->memuse;
            if (md->argintreguse > cn->regdata->argintreguse)
                  cn->regdata->argintreguse = md->argintreguse;

            bte = builtintable_get_internal(LOCK_monitor_exit);
            md = bte->md;
            if (md->memuse > cn->regdata->memuse)
                  cn->regdata->memuse = md->memuse;
            if (md->argintreguse > cn->regdata->argintreguse)
                  cn->regdata->argintreguse = md->argintreguse;
      }

      /* determine pass-through variables */

      i = site->iptr->s1.argcount - cn->m->parseddesc->paramcount; /* max # of pass-though vars */

      cn->n_passthroughvars = DMNEW(s4, i);
      j = 0;
      for (argi = site->iptr->s1.argcount - 1; argi >= cn->m->parseddesc->paramcount; --argi) {
            s4 idx = site->iptr->sx.s23.s2.args[argi];
            if (idx >= caller->jd->localcount) {
                  cn->n_passthroughvars[j] = idx;
                  j++;
            }
            else {
                  DOLOG( printf("PASSING THROUGH LOCAL VARIABLE %d\n", idx); );
            }
      }
      assert(j <= i);
      cn->n_selfpassthroughcount = j;
      cn->n_passthroughcount = caller->n_passthroughcount + cn->n_selfpassthroughcount;
}


/* inline_cumulate_counters ****************************************************

   Cumulate counters after a node has been decided to become inlined.

   IN:
       caller...........inlining node of the caller
         callee...........inlining node of the callee (const)

   OUT:
       *caller..........gets cumulated values added

*******************************************************************************/

static void inline_cumulate_counters(inline_node *caller,
                                                       const inline_node *cn)
{
      caller->cumul_instructioncount += cn->prolog_instructioncount;
      caller->cumul_instructioncount += cn->epilog_instructioncount;
      caller->cumul_instructioncount += cn->extra_instructioncount;
      caller->cumul_instructioncount += cn->cumul_instructioncount - 1 /*invoke*/;

      caller->cumul_basicblockcount += cn->cumul_basicblockcount;
      caller->cumul_basicblockcount_root += cn->cumul_basicblockcount_root;
      caller->cumul_blockmapcount += cn->cumul_blockmapcount;
      caller->cumul_exceptiontablelength += cn->cumul_exceptiontablelength;
      caller->cumul_exceptiontablelength += cn->extra_exceptiontablelength;

      if (cn->cumul_maxlocals > caller->cumul_maxlocals)
            caller->cumul_maxlocals = cn->cumul_maxlocals;

      /* XXX extra block after inlined call */
      if (cn->blockafter) {
            caller->cumul_basicblockcount += 1;
            caller->cumul_blockmapcount += 1;
      }
}


/* inline_analyse_callee *******************************************************

   Analyse an inlining candidate callee.

   IN:
       caller...........inlining node of the caller
         callee...........the called method
         site.............info about the call site

   OUT:
       site->inlined....true if the callee has been selected for inlining

   RETURN VALUE:
       the inline node of the callee, or
       NULL if an error has occurred (don't use the inlining plan in this case)

*******************************************************************************/

static inline_node * inline_analyse_callee(inline_node *caller,
                                                               methodinfo *callee,
                                                               inline_site *site)
{
      inline_node *cn;              /* the callee inline_node */

      /* create an inline tree node */

      cn = inline_create_callee_node(caller, callee);

      /* get the intermediate representation of the callee */

      if (!inline_jit_compile(cn))
            return NULL;

      /* evaluate heuristics after parsing the callee */

      if (!inline_post_parse_heuristics(caller, cn))
            return cn;

      /* the call site will be inlined */

      site->inlined = true;

      /* set info about the call site */

      inline_set_callee_properties(caller, cn, site);

      /* insert the node into the inline tree */

      inline_insert_inline_node(caller, cn);

      /* analyse recursively */

      if (!inline_analyse_code(cn))
            return NULL;

      if (!inline_afterwards_heuristics(caller, cn)) {
#if defined(INLINE_CANCEL_ON_THRESHOLD)
            return NULL;
#else
            inline_remove_inline_node(caller, cn);
            caller->ctx->stopped = true;
            site->inlined = false;
            return cn;
#endif
      }

      /* cumulate counters */

#if defined(INLINE_DEPTH_FIRST)
      inline_cumulate_counters(caller, cn);
#endif

#if defined(INLINE_BREADTH_FIRST)
      while (caller) {
            inline_cumulate_counters(caller, cn);
            caller = caller->parent;
      }
#endif

      return cn;
}


/* inline_process_candidate ****************************************************

   Process a selected inlining candidate.

   IN:
       cand.............the candidate

   RETURN VALUE:
       true........everything ok
         false.......an error has occurred, don't use the plan

*******************************************************************************/

static bool inline_process_candidate(inline_candidate *cand)
{
      inline_node *cn;

      cn = inline_analyse_callee(cand->caller,
                                             cand->callee,
                                             &(cand->site));

      if (!cn)
            return false;

      if (!cand->site.inlined)
            return true;

      /* store assumptions */

      if (cand->site.speculative)
            method_add_assumption_monomorphic(cand->callee, cand->caller->ctx->master->m);

      return true;
}


/* inline_analyse_code *********************************************************

   Analyse the intermediate code of the given inlining node.

   IN:
       iln..............the inlining node

   OUT:
       *iln.............the inlining plan

   RETURN VALUE:
       true........everything ok
         false.......an error has occurred, don't use the plan

*******************************************************************************/

static bool inline_analyse_code(inline_node *iln)
{
      methodinfo *m;
      basicblock *bptr;
      s4 len;
      instruction *iptr;
      methodinfo *callee;
      exception_entry **handlers;
      exception_entry *ex;
      s4 nhandlers;
      s4 blockendpc;
      jitdata *mjd;
      inline_site site;

      assert(iln);

      m = iln->m;
      mjd = iln->jd;

      /* initialize cumulative counters */

      iln->cumul_maxlocals = iln->localsoffset + m->maxlocals;
      iln->cumul_exceptiontablelength += mjd->exceptiontablelength;

      /* iterate over basic blocks */

      blockendpc = 0;

      for (bptr = mjd->basicblocks; bptr; bptr = bptr->next) {

            /* count the block */
            /* ignore dummy end blocks (but count them for the blockmap) */

            iln->cumul_blockmapcount++;
            if ((bptr != mjd->basicblocks || iln->blockbefore)
                        &&
                  (bptr->icount > 0 || bptr->next != NULL))
                  iln->cumul_basicblockcount++;

            /* skip dead code */

            if (bptr->flags < BBREACHED)
                  continue;

            /* allocate the buffer of active exception handlers */
            /* XXX this wastes some memory, but probably it does not matter */

            handlers = DMNEW(exception_entry*, mjd->exceptiontablelength + 1);

            /* determine the active exception handlers for this block     */
            /* XXX maybe the handlers of a block should be part of our IR */
            /* XXX this should share code with the type checkers          */
            nhandlers = 0;
            for (ex = mjd->exceptiontable; ex ; ex = ex->down) {
                  if ((ex->start->nr <= bptr->nr) && (ex->end->nr > bptr->nr)) {
                        handlers[nhandlers++] = ex;
                  }
            }
            handlers[nhandlers] = NULL;

            len = bptr->icount;
            iptr = bptr->iinstr;

            blockendpc += len;
            iln->cumul_instructioncount += len;

            /* iterate over the instructions of the block */

            for (; --len >= 0; ++iptr) {

                  switch (iptr->opc) {
                        case ICMD_INVOKEVIRTUAL:
                        case ICMD_INVOKESPECIAL:
                        case ICMD_INVOKESTATIC:
                        case ICMD_INVOKEINTERFACE:

                              if (!INSTRUCTION_IS_UNRESOLVED(iptr) && !iln->ctx->stopped) {
                                    callee = iptr->sx.s23.s3.fmiref->p.method;

                                    if (inline_can_inline(iln, callee, iptr, &site)) {
                                          site.inlined = false;
                                          site.bptr = bptr;
                                          site.iptr = iptr;
                                          site.pc = blockendpc - len - 1;
                                          site.handlers = handlers;
                                          site.nhandlers = nhandlers;

                                          if (inline_pre_parse_heuristics(iln, callee, &site)) {
#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
                                                inline_add_candidate(iln->ctx, iln, callee, &site);
#else
                                                inline_candidate cand;
                                                cand.caller = iln;
                                                cand.callee = callee;
                                                cand.site   = site;

                                                if (!inline_process_candidate(&cand))
                                                      return false;
#endif
                                          }
                                    }
                              }
                              break;

                        case ICMD_RETURN:
                        case ICMD_IRETURN:
                        case ICMD_ARETURN:
                        case ICMD_LRETURN:
                        case ICMD_FRETURN:
                        case ICMD_DRETURN:
                              /* extra ICMD_MOVE may be necessary */
                              iln->cumul_instructioncount++;
                              break;
                  }
            }

            /* end of basic block */
      }

      return true;
}


static void inline_cumulate_counters_recursive(inline_node *iln)
{
      inline_node *child;

      child = iln->children;
      if (child) {
            do {
                  inline_cumulate_counters_recursive(child);
                  inline_cumulate_counters(iln, child);
                  child = child->next;
            } while (child != iln->children);
      }
}


/* inline_make_inlining_plan ***************************************************

   Make an inlining plan for the given root node

   IN:
       iln..............the root node

   OUT:
       *iln.............the inlining plan

   RETURN VALUE:
       true........everything ok
         false.......an error has occurred, don't use the plan

*******************************************************************************/

#if defined(INLINE_KNAPSACK)
static bool inline_make_inlining_plan(inline_node *iln)
{
      inline_candidate *cand;
#if defined(INLINE_COST_BUDGET)
      s4 budget = INLINE_COST_BUDGET;
#   define BUDGETMEMBER cost
#endif
#if defined(INLINE_WEIGHT_BUDGET)
      double budget = INLINE_WEIGHT_BUDGET;
#   define BUDGETMEMBER weight
#endif

      inline_analyse_code(iln);

      DOLOG( printf("candidates in "); method_println(iln->m);
               inline_candidates_println(iln->ctx); );

      while ((cand = inline_pick_best_candidate(iln->ctx)) != NULL)
      {
            if (cand->BUDGETMEMBER <= budget) {
                  DOLOG( printf("    picking: "); inline_candidate_println(cand); );

                  if (!inline_process_candidate(cand))
                        return false;

#if !defined(INLINE_ADD_NEGATIVE_TO_BUDGET)
                  if (cand->BUDGETMEMBER > 0)
#endif
                        budget -= cand->BUDGETMEMBER;
            }
      }

      inline_cumulate_counters_recursive(iln);

      return true;
}
#endif /* defined(INLINE_KNAPSACK) */


#if defined(INLINE_DEPTH_FIRST)
static bool inline_make_inlining_plan(inline_node *iln)
{
      return inline_analyse_code(iln);
}
#endif /* defined(INLINE_DEPTH_FIRST) */


#if defined(INLINE_BREADTH_FIRST)
static bool inline_make_inlining_plan(inline_node *iln)
{
      inline_candidate *cand;

      inline_analyse_code(iln);

      DOLOG( printf("candidates in "); method_println(iln->m);
               inline_candidates_println(iln->ctx); );

      while (!iln->ctx->stopped
               && (cand = inline_pick_best_candidate(iln->ctx)) != NULL)
      {
            DOLOG( printf("    picking: "); inline_candidate_println(cand); );

            if (!inline_process_candidate(cand))
                  return false;
      }

      return true;
}
#endif /* defined(INLINE_BREADTH_FIRST) */


/* statistics *****************************************************************/

#if defined(INLINE_STATISTICS)
static void inline_gather_statistics_recursive(inline_node *iln)
{
      inline_node *child;

      inline_stat_inlined_nodes++;

      if (iln->depth > inline_stat_max_depth)
            inline_stat_max_depth++;

      child = iln->children;
      if (child) {
            do {
                  inline_gather_statistics_recursive(child);
                  child = child->next;
            } while (child != iln->children);
      }
}
#endif /* defined(INLINE_STATISTICS) */


#if defined(INLINE_STATISTICS)
static void inline_gather_statistics(inline_node *iln)
{
      inline_stat_roots_transformed++;

      inline_gather_statistics_recursive(iln);
}
#endif /* defined(INLINE_STATISTICS) */


/* post processing ************************************************************/

#define POSTPROCESS_SRC(varindex)  live[varindex]--
#define POSTPROCESS_DST(varindex)  live[varindex]++

#define POSTPROCESS_SRCOP(s)  POSTPROCESS_SRC(iptr->s.varindex)
#define POSTPROCESS_DSTOP(d)  POSTPROCESS_DST(iptr->d.varindex)

#define MARKSAVED(varindex)  jd->var[varindex].flags |= SAVEDVAR

#define MARK_ALL_SAVED                                               \
    do {                                                             \
        for (i=0; i<jd->vartop; ++i)                                 \
            if (live[i])                                             \
                MARKSAVED(i);                                        \
    } while (0)

static void inline_post_process(jitdata *jd)
{
      codeinfo   *code;
      basicblock *bptr;
      instruction *iptr;
      instruction *iend;
      s4 i;
      icmdtable_entry_t *icmdt;
      s4 *live;
      methoddesc *md;
      builtintable_entry *bte;

      /* Get required compiler data. */

      code = jd->code;

      /* reset the SAVEDVAR flag of all variables */

      for (i=0; i<jd->vartop; ++i)
            jd->var[i].flags &= ~SAVEDVAR;

      /* allocate the life counters */

      live = DMNEW(s4, jd->vartop);
      MZERO(live, s4, jd->vartop);

      /* iterate over all basic blocks */

      for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
            if (bptr->flags < BBREACHED)
                  continue;

            /* make invars live */

            for (i=0; i<bptr->indepth; ++i)
                  POSTPROCESS_DST(bptr->invars[i]);

            iptr = bptr->iinstr;
            iend = iptr + bptr->icount;

            for (; iptr < iend; ++iptr) {

                  icmdt = &(icmd_table[iptr->opc]);

                  switch (icmdt->dataflow) {
                        case DF_3_TO_0:
                              POSTPROCESS_SRCOP(sx.s23.s3);
                        case DF_2_TO_0:
                              POSTPROCESS_SRCOP(sx.s23.s2);
                        case DF_1_TO_0:
                              POSTPROCESS_SRCOP(s1);
                        case DF_0_TO_0:
                              if (icmdt->flags & ICMDTABLE_CALLS) {
                                    code_unflag_leafmethod(code);
                                    MARK_ALL_SAVED;
                              }
                              break;

                        case DF_2_TO_1:
                              POSTPROCESS_SRCOP(sx.s23.s2);
                        case DF_1_TO_1:
                        case DF_MOVE:
                              POSTPROCESS_SRCOP(s1);
                        case DF_0_TO_1:
                              if (icmdt->flags & ICMDTABLE_CALLS) {
                                    code_unflag_leafmethod(code);
                                    MARK_ALL_SAVED;
                              }
                        case DF_COPY:
                              POSTPROCESS_DSTOP(dst);
                              break;

                        case DF_N_TO_1:
                              for (i=0; i<iptr->s1.argcount; ++i) {
                                    POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
                              }
                              if (icmdt->flags & ICMDTABLE_CALLS) {
                                    code_unflag_leafmethod(code);
                                    MARK_ALL_SAVED;
                              }
                              POSTPROCESS_DSTOP(dst);
                              break;

                        case DF_INVOKE:
                              INSTRUCTION_GET_METHODDESC(iptr, md);
            post_process_call:
                              code_unflag_leafmethod(code);
                              for (i=0; i<md->paramcount; ++i) {
                                    POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
                              }
                              for (; i<iptr->s1.argcount; ++i) {
                                    MARKSAVED(iptr->sx.s23.s2.args[i]);
                              }
                              if (md->returntype.type != TYPE_VOID)
                                    POSTPROCESS_DSTOP(dst);
                              break;

                        case DF_BUILTIN:
                              bte = iptr->sx.s23.s3.bte;
                              md = bte->md;
                              goto post_process_call;

                        default:
                              assert(0);
                  }

            } /* end instruction loop */

            /* consume outvars */

            for (i=0; i<bptr->outdepth; ++i)
                  POSTPROCESS_SRC(bptr->outvars[i]);

#if !defined(NDEBUG)
            for (i=jd->localcount; i < jd->vartop; ++i)
                  assert(live[i] == 0);
#endif

      } /* end basic block loop */
}


/* inline_create_root_node *****************************************************

   Create the root node of the inlining tree.

   IN:
         jd...............the current jitdata of the root method

   RETURN VALUE:
       the root node of the inlining tree

*******************************************************************************/

static inline_node * inline_create_root_node(jitdata *jd)
{
      inline_node *iln;

      iln = DNEW(inline_node);
      MZERO(iln, inline_node, 1);

      iln->m = jd->m;
      iln->jd = jd;
      iln->regdata = jd->rd;

      iln->blockbefore = true;
      iln->blockafter = true;

      iln->cumul_instructioncount = 0;
      iln->cumul_basicblockcount = 1 /* dummy end block */;

      /* create inlining context */

      iln->ctx = DNEW(inline_context);
      MZERO(iln->ctx, inline_context, 1);
      iln->ctx->master = iln;
      iln->ctx->next_debugnr = 1; /* XXX debug */

      return iln;
}


/******************************************************************************/
/* MAIN DRIVER FUNCTION                                                       */
/******************************************************************************/

bool inline_inline(jitdata *jd)
{
      inline_node *iln;

      DOLOG( printf("==== INLINE ==================================================================\n");
               show_method(jd, SHOW_STACK); );

#if defined(INLINE_STATISTICS)
      inline_stat_roots++;
#endif

      iln = inline_create_root_node(jd);

      if (inline_make_inlining_plan(iln)) {

            /* add blocks to the root node */

            iln->cumul_basicblockcount += iln->cumul_basicblockcount_root;
            iln->cumul_blockmapcount   += iln->cumul_basicblockcount_root;

            DOLOG( printf("==== INLINE TRANSFORM ========================================================\n"); );

            if (iln->children)
                  inline_transform(iln, jd);

#if defined(INLINE_STATISTICS)
            inline_gather_statistics(iln);
#endif
      }

      DOLOG( printf("-------- DONE -----------------------------------------------------------\n");
               fflush(stdout); );

      return true;
}

/*
 * These are local overrides for various environment variables in Emacs.
 * Please do not remove this and leave it at the end of the file, where
 * Emacs will automagically detect them.
 * ---------------------------------------------------------------------
 * Local variables:
 * mode: c
 * indent-tabs-mode: t
 * c-basic-offset: 4
 * tab-width: 4
 * End:
 * vim:noexpandtab:sw=4:ts=4:
 */

Generated by  Doxygen 1.6.0   Back to index