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

   Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   J. Wenninger, Institut f. Computersprachen - TU Wien

   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.

   Contact: cacao@cacaojvm.org

   Authors: Edwin Steiner

   Changes:

   $Id: inline.c 7228 2007-01-19 01:13:48Z edwin $

*/

#include "config.h"

#include "vm/types.h"

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

#include "mm/memory.h"
#include "toolbox/logging.h"
#include "vm/builtin.h"
#include "vm/global.h"
#include "vm/options.h"
#include "vm/statistics.h"
#include "vm/jit/jit.h"
#include "vm/jit/parse.h"
#include "vm/jit/inline/inline.h"
#include "vm/jit/loop/loop.h"

#include "vm/class.h"
#include "vm/initialize.h"
#include "vm/method.h"
#include "vm/jit/jit.h"
#include "vm/jit/show.h"

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

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

#if defined(ENABLE_THREADS)
# include "threads/native/threads.h"
#endif


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

#define INLINE_KNAPSACK

#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 */

#else

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

#endif


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

#if !defined(NDEBUG)
#define INLINE_VERBOSE
#define DOLOG(code) do{ if (opt_inline_debug_log) { 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;

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;
};

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

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

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 */
};

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       */
};

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->class) );
	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);

#if defined(ENABLE_THREADS)
	/* enter a monitor on the method */
	lock_monitor_enter((java_objectheader *) m);
#endif

	/* 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->maxstack = m->maxstack;
	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

#if defined(ENABLE_THREADS)
	/* leave the monitor */
	lock_monitor_exit((java_objectheader *) m );
#endif

	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)
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;
	cand->cost = callee->jcodelength + INLINE_COST_OFFSET;
	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) */

#if defined(INLINE_KNAPSACK)
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) */

#if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
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) */


#if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
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) */


/* 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 idx;
	s4 n_idx;
	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) {
			idx = callee->jd->local_map[5*i + t];
			if (idx == UNUSED)
				continue;

			v = &(callee->jd->var[idx]);
			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, idx);
				callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t] = avail;
			}

			varmap[idx] = avail;
		}
	}

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

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

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

		if (avail == UNUSED) {
			avail = inline_new_variable(callee->ctx->resultjd, TYPE_ADR, 0);
			callee->ctx->resultjd->local_map[5*n_idx + 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) )

#define RETADDRNR_FROM_BLOCK(bptr)  (UNUSED - 1 - (bptr)->nr)


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;
}


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;
}


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) == RETADDRNR_FROM_BLOCK(o_bptr)) {
				*(ref->ref.nr) = RETADDRNR_FROM_BLOCK(n_bptr);
				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->class;
		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 argvar;

	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 */

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

		/* remove preallocation from the argument variable */

		iln->ctx->resultjd->var[argvar].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 = argvar;
			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 = argvar;
			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 = argvar;
		}

		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->class;
			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)
	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->basicblockindex = NULL;
	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)) {
			*exceptionptr = NULL;
			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_inline_debug_min_size)
		&& (n_jd->instructioncount <= opt_inline_debug_max_size))
	{
	   if (debug_counter <= opt_inline_debug_end_counter)
#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(
			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)
{
	if (0
#if defined(INLINE_MAX_BLOCK_EXPANSION)
		|| (caller->cumul_basicblockcount + callee->cumul_basicblockcount
			> INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
#endif
#if defined(INLINE_MAX_ICMD_EXPANSION)
		|| (caller->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_KNAPSACK)
	inline_cumulate_counters(caller, cn);
#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)
								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

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

static bool inline_make_inlining_plan(inline_node *iln)
{
#if defined(INLINE_KNAPSACK)
	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;
#else
	return inline_analyse_code(iln);
#endif
}


/* 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)
{
	basicblock *bptr;
	instruction *iptr;
	instruction *iend;
	s4 i;
	icmdtable_entry_t *icmdt;
	s4 *live;
	methoddesc *md;
	builtintable_entry *bte;

	/* 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) {
						jd->isleafmethod = false;
						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) {
						jd->isleafmethod = false;
						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) {
						jd->isleafmethod = false;
						MARK_ALL_SAVED;
					}
					POSTPROCESS_DSTOP(dst);
					break;

				case DF_INVOKE:
					INSTRUCTION_GET_METHODDESC(iptr, md);
		post_process_call:
					jd->isleafmethod = false;
					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:
 */