/* src/vm/jit/inline/inline.c - method inlining
- Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
+ Copyright (C) 1996-2005, 2006, 2007 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
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- Contact: cacao@cacaojvm.org
-
- Authors: Edwin Steiner
-
- Changes:
-
- $Id: inline.c 5950 2006-11-11 17:08:14Z edwin $
-
*/
-#include "config.h"
-#include "vm/types.h"
+#include "config.h"
#include <assert.h>
+#include <limits.h>
#include <stdio.h>
#include <string.h>
-#include <limits.h>
+
+#include "vm/types.h"
#include "mm/memory.h"
+
+#include "threads/lock-common.h"
+#include "threads/threads-common.h"
+
#include "toolbox/logging.h"
+
#include "vm/builtin.h"
#include "vm/global.h"
-#include "vm/options.h"
-#include "vm/statistics.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/class.h"
-#include "vm/initialize.h"
-#include "vm/method.h"
-#include "vm/jit/jit.h"
-#include "vm/jit/show.h"
+#include "vm/jit/verify/typecheck.h"
-#include "vm/jit/reg.h"
-#include "vm/jit/stack.h"
+#include "vmcore/class.h"
+#include "vmcore/method.h"
+#include "vmcore/options.h"
+#include "vmcore/statistics.h"
-#include "vm/jit/verify/typecheck.h"
-#if defined(ENABLE_THREADS)
-# include "threads/native/threads.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
-bool inline_debug_log = 0;
-bool inline_debug_log_names = 0;
-int inline_debug_start_counter = 0;
-int inline_debug_max_size = INT_MAX;
-int inline_debug_min_size = 0;
-int inline_debug_end_counter = INT_MAX;
-int inline_count_methods = 0;
-#define DOLOG(code) do{ if (inline_debug_log) { code; } }while(0)
+#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_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;
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? */
int prolog_instructioncount; /* # of ICMDs in the inlining prolog */
int epilog_instructioncount; /* # of ICMDs in the inlining epilog */
int extra_instructioncount;
- int 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;
struct inline_target_ref {
inline_target_ref *next;
- basicblock **ref;
+ union {
+ basicblock **block;
+ s4 *nr;
+ } ref;
basicblock *target;
+ bool isnumber;
};
struct inline_block_map {
jitdata *resultjd;
+ inline_candidate *candidates;
+
int next_block_number;
inline_block_map *blockmap;
int blockmap_index;
int maxinoutdepth;
- bool calls_others;
+ 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_inline_intern(methodinfo *m, inline_node *iln);
+static bool inline_analyse_code(inline_node *iln);
static void inline_post_process(jitdata *jd);
#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("inlined callers: %d\n", inline_count_methods);
+ 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
m = iln->m;
assert(m);
-#if defined(ENABLE_THREADS)
/* enter a monitor on the method */
- lock_monitor_enter((java_objectheader *) m);
-#endif
+
+ LOCK_MONITOR_ENTER(m);
/* allocate jitdata structure and fill it */
/* 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); */
#endif
-#if defined(ENABLE_THREADS)
/* leave the monitor */
- lock_monitor_exit((java_objectheader *) m );
-#endif
+
+ LOCK_MONITOR_EXIT(m);
return r;
}
/* inlining tree handling *****************************************************/
-static void insert_inline_node(inline_node *parent, inline_node *child)
+static void inline_insert_inline_node(inline_node *parent, inline_node *child)
{
inline_node *first;
inline_node *succ;
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 **********************************************************/
{
s4 *varmap;
s4 i, t;
- s4 idx;
- s4 n_idx;
+ s4 varindex;
+ s4 n_javaindex;
s4 avail;
varinfo *v;
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)
+ varindex = callee->jd->local_map[5*i + t];
+ if (varindex == UNUSED)
continue;
- v = &(callee->jd->var[idx]);
+ 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, idx);
+ avail = inline_new_variable_clone(callee->ctx->resultjd, callee->jd, varindex);
callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t] = avail;
}
- varmap[idx] = avail;
+ varmap[varindex] = 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);
+ n_javaindex = callee->localsoffset - 1;
+ assert(n_javaindex >= 0);
assert(callee->parent);
- assert(n_idx == callee->parent->localsoffset + callee->parent->m->maxlocals);
+ assert(n_javaindex == callee->parent->localsoffset + callee->parent->m->maxlocals);
- avail = callee->ctx->resultjd->local_map[5*n_idx + TYPE_ADR];
+ 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_idx + TYPE_ADR] = avail;
+ callee->ctx->resultjd->local_map[5*n_javaindex + TYPE_ADR] = avail;
}
callee->synclocal = avail;
inline_target_ref *ref;
ref = DNEW(inline_target_ref);
- ref->ref = blockp;
+ 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_resolve_block_refs(inline_target_ref **refs,
basicblock *o_bptr,
- basicblock *n_bptr)
+ basicblock *n_bptr,
+ bool returnref)
{
inline_target_ref *ref;
inline_target_ref *prev;
- ref = *refs;
prev = NULL;
- while (ref) {
- if (*(ref->ref) == o_bptr) {
-
-#if defined(INLINE_VERBOSE)
- if (inline_debug_log) {
- if ((ptrint) o_bptr < (0x333+100)) { /* XXX */
- printf("resolving RETURN block reference %p -> new L%03d (%p)\n",
- (void*)o_bptr, n_bptr->nr, (void*)n_bptr);
- }
- else {
- printf("resolving block reference old L%03d (%p) -> new L%03d (%p)\n",
- o_bptr->nr, (void*)o_bptr, n_bptr->nr, (void*)n_bptr);
- }
+ 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;
}
-#endif
-
- *(ref->ref) = n_bptr;
- if (prev) {
- prev->next = ref->next;
- }
- else {
- *refs = ref->next;
+ }
+ 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 {
- prev = ref;
+ *refs = ref->next;
}
- ref = ref->next;
}
}
static basicblock * create_block(inline_node *container,
inline_node *iln,
inline_node *inner,
- basicblock *o_bptr,
- inline_target_ref **refs,
int indepth)
{
basicblock *n_bptr;
n_bptr->invars = NULL;
}
- /* XXX move this to callers with o_bptr != NULL? */
- if (o_bptr) {
- assert(refs);
- inline_resolve_block_refs(refs, o_bptr, n_bptr);
- }
-
/* XXX for the verifier. should not be here */
{
for (i=0; i<iln->jd->maxlocals; ++i) {
j = javalocals[i];
- if (j != UNUSED)
+ 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;
basicblock *n_bptr;
s4 i;
- n_bptr = create_block(iln, iln, iln, o_bptr, &(iln->refs),
+ 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 */
o_bptr->invars[i]);
}
- /* translate javalocals info */
+ /* translate javalocals info (not for dead code) */
- n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);
+ if (n_bptr->flags >= BBREACHED)
+ n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);
return n_bptr;
}
/* start the epilog block */
- n_bptr = create_block(caller, caller, callee, INLINE_RETURN_REFERENCE(callee),
- &(callee->refs), callee->n_passthroughcount + retcount);
+ 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 */
/* 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,
int i;
int localindex;
int type;
- bool isstatic;
instruction *n_ins;
insinfo_inline *insinfo;
- s4 argvar;
+ s4 varindex;
assert(iln && callee && o_iptr);
calleem = callee->m;
md = calleem->parseddesc;
- isstatic = (calleem->flags & ACC_STATIC);
+
+ /* 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);
- n_ins = (iln->inlined_iinstr_cursor++);
- assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
-
type = md->paramtypes[i].type;
localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
/* translate the argument variable */
- argvar = varmap[o_iptr->sx.s23.s2.args[i]];
- assert(argvar != UNUSED);
+ varindex = varmap[o_iptr->sx.s23.s2.args[i]];
+ assert(varindex != UNUSED);
/* remove preallocation from the argument variable */
- iln->ctx->resultjd->var[argvar].flags &= ~(PREALLOC | INMEMORY);
+ 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 (!isstatic && i == 0) {
+ if (!callee->isstatic && i == 0 && calleem->name != utf_init) {
assert(type == TYPE_ADR);
- n_ins->opc = ICMD_CHECKNULL;
- n_ins->s1.varindex = argvar;
+ n_ins = inline_instruction(iln, ICMD_CHECKNULL, o_iptr);
+ n_ins->s1.varindex = varindex;
n_ins->dst.varindex = n_ins->s1.varindex;
- n_ins->line = o_iptr->line;
-
- n_ins = (iln->inlined_iinstr_cursor++);
- assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
}
/* store argument into local variable of inlined callee */
if (i == 0 && callee->synclocal != UNUSED) {
/* we also need it for synchronization, so copy it */
assert(type == TYPE_ADR);
- n_ins->opc = ICMD_COPY;
+ n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
}
else {
- n_ins->opc = ICMD_ISTORE + type;
+ n_ins = inline_instruction(iln, ICMD_ISTORE + type, o_iptr);
+ n_ins->sx.s23.s3.javaindex = UNUSED;
}
- n_ins->s1.varindex = argvar;
+ n_ins->s1.varindex = varindex;
n_ins->dst.varindex = iln->ctx->resultjd->local_map[5*localindex + type];
assert(n_ins->dst.varindex != UNUSED);
}
/* XXX In this case it actually makes no sense to create a */
/* separate synchronization variable. */
- n_ins->opc = ICMD_NOP;
+ n_ins = inline_instruction(iln, ICMD_NOP, o_iptr);
}
else {
/* this value is not used, pop it */
- n_ins->opc = ICMD_POP;
- n_ins->s1.varindex = argvar;
+ n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
+ n_ins->s1.varindex = varindex;
}
- n_ins->line = o_iptr->line;
DOLOG( printf("%sprolog: ", iln->indent);
show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
}
- /* ASTORE for synchronized instance methods */
+ /* COPY for synchronized instance methods */
if (callee->synclocal != UNUSED) {
- n_ins = (iln->inlined_iinstr_cursor++);
- assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
-
- n_ins->opc = ICMD_ASTORE;
+ 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;
- n_ins->line = o_iptr->line;
assert(n_ins->s1.varindex != UNUSED);
}
- /* INLINE_START instruction */
-
- n_ins = (iln->inlined_iinstr_cursor++);
- assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
-
- 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->stackvarscount = callee->n_selfpassthroughcount;
- insinfo->stackvars = DMNEW(s4, callee->n_selfpassthroughcount);
- for (i=0; i<callee->n_selfpassthroughcount; ++i)
- insinfo->stackvars[i] = iln->varmap[callee->n_passthroughvars[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;
+ 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);
+ }
- /* finish the INLINE_START instruction */
+ /* INLINE_BODY instruction */
- n_ins->opc = ICMD_INLINE_START;
+ n_ins = inline_instruction(iln, ICMD_INLINE_BODY, callee->jd->basicblocks[0].iinstr);
n_ins->sx.s23.s3.inlineinfo = insinfo;
- n_ins->line = o_iptr->line;
- callee->inline_start_instruction = n_ins;
-
- DOLOG( printf("%sprolog: ", iln->indent);
- show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
return 0; /* XXX */
}
assert(iln && callee && o_iptr);
assert(callee->inline_start_instruction);
- /* INLINE_END instruction */
+ if (callee->synchronize) {
+ inline_generate_sync_builtin(iln, callee, o_iptr,
+ callee->synclocal,
+ LOCK_monitor_exit);
+ }
- n_ins = (iln->inlined_iinstr_cursor++);
- assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
+ /* INLINE_END instruction */
- n_ins->opc = ICMD_INLINE_END;
+ n_ins = inline_instruction(iln, ICMD_INLINE_END, o_iptr);
n_ins->sx.s23.s3.inlineinfo = callee->inline_start_instruction->sx.s23.s3.inlineinfo;
- n_ins->line = o_iptr->line;
/* set the javalocals */
/* 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:
- case ICMD_ASTORE:
- /* XXX share code with stack.c */
- j = n_iptr->dst.varindex;
- i = n_iptr->sx.s23.s3.javaindex;
- if (n_iptr->flags.bits & INS_FLAG_RETADDR)
- iln->javalocals[i] = UNUSED;
- else
- iln->javalocals[i] = j;
- if (n_iptr->flags.bits & INS_FLAG_KILL_PREV)
- iln->javalocals[i-1] = UNUSED;
- if (n_iptr->flags.bits & INS_FLAG_KILL_NEXT)
- iln->javalocals[i+1] = UNUSED;
+ stack_javalocals_store(n_iptr, iln->javalocals);
break;
}
}
-static void rewrite_method(inline_node *iln)
+static void inline_rewrite_method(inline_node *iln)
{
basicblock *o_bptr;
s4 len;
DOLOG( printf("%sentering inline ", indent);
show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
- rewrite_method(nextcall);
+ inline_rewrite_method(nextcall);
DOLOG( printf("%sleaving inline ", indent);
show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
/* emit inlining epilog */
emit_inlining_epilog(iln, nextcall, o_iptr);
- icount++; /* XXX epilog instructions */
+ icount += nextcall->epilog_instructioncount;
/* proceed to next call */
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;
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);
+ inline_resolve_block_refs(&(iln->refs), bm->o_block, bm->n_block, false);
}
#if !defined(NDEBUG)
inline_target_ref *ref;
ref = iln->refs;
while (ref) {
- if (!iln->depth || *(ref->ref) != INLINE_RETURN_REFERENCE(iln)) {
+ 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)) );
+ (void*)*(ref->ref.block)) );
assert(false);
}
ref = ref->next;
for (i=0; i<bptr->indepth; ++i) {
v = &(resultjd->var[bptr->invars[i]]);
v->flags |= INOUT;
- v->flags &= ~PREALLOC;
+ if (v->type == TYPE_RET)
+ v->flags |= PREALLOC;
+ else
+ v->flags &= ~PREALLOC;
v->flags &= ~INMEMORY;
assert(bptr->invars[i] >= resultjd->localcount);
for (i=0; i<bptr->outdepth; ++i) {
v = &(resultjd->var[bptr->outvars[i]]);
v->flags |= INOUT;
- v->flags &= ~PREALLOC;
+ if (v->type == TYPE_RET)
+ v->flags |= PREALLOC;
+ else
+ v->flags &= ~PREALLOC;
v->flags &= ~INMEMORY;
assert(bptr->outvars[i] >= resultjd->localcount);
if (iln->synchronize) {
/* create the monitorexit handler */
- n_bptr = create_block(master, iln, iln, NULL, NULL,
+ n_bptr = create_block(master, iln, iln,
iln->n_passthroughcount + 1);
n_bptr->type = BBTYPE_EXH;
n_bptr->flags = BBFINISHED;
/* second pass driver *********************************************************/
-static bool test_inlining(inline_node *iln, jitdata *jd,
- jitdata **resultjd)
+static bool inline_transform(inline_node *iln, jitdata *jd)
{
instruction *n_ins;
basicblock *n_bb;
codegendata *n_cd;
jitdata *n_jd;
s4 i;
-
-
-#if !defined(NDEBUG)
- static int debug_verify_inlined_code = 1; /* XXX */
- static int debug_compile_inlined_code_counter = 0;
+#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 && resultjd);
-
- *resultjd = jd;
+ assert(iln && jd);
n_ins = DMNEW(instruction, iln->cumul_instructioncount);
MZERO(n_ins, instruction, iln->cumul_instructioncount);
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);
n_jd->localcount = n_jd->vartop;
- /* extra variables for verification (DEBUG) */
+ /* extra variables for verification (debugging) */
-#if !defined(NDEBUG)
+#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) {
n_jd->varcount = n_jd->vartop;
}
}
-#endif
+#endif /* defined(INLINE_VERIFY_RESULT) */
/* write inlined code */
- rewrite_method(iln);
+ inline_rewrite_method(iln);
/* create exception handlers */
/* write the dummy end block */
- n_bptr = create_block(iln, iln, iln, NULL, NULL, 0);
+ 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;
inline_interface_variables(iln);
-#if defined(ENABLE_VERIFIER) && !defined(NDEBUG)
+ /* 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); );
}
debug_verify_inlined_code = 1;
}
-#endif /* defined(ENABLE_VERIFIER) */
+#endif /* defined(INLINE_VERIFY_RESULT) */
/* we need bigger free memory stacks (XXX these should not be allocated in reg_setup) */
n_jd->rd->freemem_2 = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
#endif
-#if !defined(NDEBUG)
- if (n_jd->instructioncount >= inline_debug_min_size
- && n_jd->instructioncount <= inline_debug_max_size)
+#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_compile_inlined_code_counter >= inline_debug_start_counter
- && debug_compile_inlined_code_counter <= inline_debug_end_counter)
-#endif /* NDEBUG */
+ if (debug_counter <= opt_inline_debug_end_counter)
+#endif /* defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG) */
{
- *resultjd = n_jd;
+ /* install the inlined result */
+
+ *jd->code = *n_jd->code;
+ n_jd->code = jd->code;
+ *jd = *n_jd;
+
+ /* statistics and logging */
#if !defined(NDEBUG)
- inline_count_methods++;
+ inline_stat_roots++;
- /* inline_debug_log++; */
DOLOG(
- printf("==== %d.INLINE ==================================================================\n", debug_compile_inlined_code_counter);
+ printf("==== %d.INLINE ==================================================================\n",
+ debug_counter);
printf("\ninline tree:\n");
dump_inline_tree(iln, 0);
n_jd->flags |= JITDATA_FLAG_SHOWINTERMEDIATE | JITDATA_FLAG_SHOWDISASSEMBLE;
printf("-------- DONE -----------------------------------------------------------\n");
fflush(stdout);
);
- /* inline_debug_log--; */
#endif
}
-#if !defined(NDEBUG)
- debug_compile_inlined_code_counter++;
+#if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
+ debug_counter++;
}
#endif
return true;
}
-/* first pass: build inlining tree ********************************************/
+/******************************************************************************/
+/* FIRST PASS: build inlining tree */
+/******************************************************************************/
-static bool inline_analyse_callee(inline_node *caller,
- methodinfo *callee,
- basicblock *callerblock,
- instruction *calleriptr,
- s4 callerpc,
- exception_entry **handlers,
- s4 nhandlers)
-{
- inline_node *cn; /* the callee inline_node */
- s4 argi;
- bool isstatic;
- s4 i, j;
- basicblock *bptr;
- /* create an inline tree node */
+/* inline_pre_parse_heuristics *************************************************
- cn = DNEW(inline_node);
- MZERO(cn, inline_node, 1);
+ Perform heuristic checks whether a call site should be inlined.
+ These checks are evaluated before the callee has been parsed and analysed.
- cn->ctx = caller->ctx;
- cn->m = callee;
- cn->synchronize = (callee->flags & ACC_SYNCHRONIZED);
- isstatic = (callee->flags & ACC_STATIC);
+ IN:
+ caller...........inlining node of the caller
+ callee...........the called method
+ site.............information on the call site
- /* get the intermediate representation of the callee */
+ RETURN VALUE:
+ true........consider for inlining
+ false.......don't inline
- if (!inline_jit_compile(cn))
+*******************************************************************************/
+
+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
- /* info about the call site */
+*******************************************************************************/
+
+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->callerblock = callerblock;
- cn->callerins = calleriptr;
- cn->callerpc = callerpc;
- cn->o_handlers = handlers;
- cn->n_handlercount = caller->n_handlercount + nhandlers;
+ 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 */
/* info about the callee */
cn->localsoffset = caller->localsoffset + caller->m->maxlocals;
- cn->prolog_instructioncount = callee->parseddesc->paramcount + 1;
+ 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 */
+ /* we need a CHECKNULL for instance methods, except for <init> */
- if (!isstatic)
+ if (!cn->isstatic && cn->m->name != utf_init)
cn->prolog_instructioncount += 1;
/* deal with synchronized callees */
cn->blockbefore = true;
cn->blockafter = true;
- /* for synchronized instance methods */
- /* we need an ASTORE in the prolog */
+ /* for synchronized static methods */
+ /* we need an ACONST, MONITORENTER in the prolog */
+ /* and ACONST, MONITOREXIT in the epilog */
- if (!isstatic) {
- cn->prolog_instructioncount += 1;
+ /* 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;
}
/* exception table entries */
- caller->cumul_exceptiontablelength += 1 + cn->n_handlercount;
+ cn->extra_exceptiontablelength = 1 + cn->n_handlercount;
+
+ /* add exception handler block */
+
+ cn->cumul_basicblockcount_root++;
/* we must call the builtins */
cn->regdata->memuse = md->memuse;
if (md->argintreguse > cn->regdata->argintreguse)
cn->regdata->argintreguse = md->argintreguse;
-
- caller->ctx->calls_others = true;
}
/* determine pass-through variables */
- i = calleriptr->s1.argcount - callee->parseddesc->paramcount; /* max # of pass-though vars */
+ i = site->iptr->s1.argcount - cn->m->parseddesc->paramcount; /* max # of pass-though vars */
cn->n_passthroughvars = DMNEW(s4, i);
j = 0;
- for (argi = calleriptr->s1.argcount - 1; argi >= callee->parseddesc->paramcount; --argi) {
- s4 idx = calleriptr->sx.s23.s2.args[argi];
+ 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++;
assert(j <= i);
cn->n_selfpassthroughcount = j;
cn->n_passthroughcount = caller->n_passthroughcount + cn->n_selfpassthroughcount;
+}
- /* insert the node into the inline tree */
-
- insert_inline_node(caller, cn);
- /* analyse recursively */
+/* inline_cumulate_counters ****************************************************
- if (!inline_inline_intern(callee, cn))
- return false;
+ Cumulate counters after a node has been decided to become inlined.
- /* subtract one block if we continue the caller block */
+ IN:
+ caller...........inlining node of the caller
+ callee...........inlining node of the callee (const)
- if (!cn->blockbefore)
- cn->cumul_basicblockcount -= 1;
+ OUT:
+ *caller..........gets cumulated values added
- /* add exception handler block for synchronized callees */
-
- if (cn->synchronize) {
- caller->ctx->master->cumul_basicblockcount++;
- caller->ctx->master->cumul_blockmapcount++;
- }
-
- /* cumulate counters */
+*******************************************************************************/
+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;
- if (caller->cumul_basicblockcount > 10*caller->ctx->master->jd->basicblockcount) {
-#if 0
- printf("STOPPING to avoid code explosion (%d blocks)\n",
- caller->cumul_basicblockcount);
-#endif
- return false;
- }
-
/* 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;
}
-static bool inline_inline_intern(methodinfo *m, inline_node *iln)
+/* 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;
- int opcode; /* invocation opcode */
methodinfo *callee;
- inline_node *active;
exception_entry **handlers;
exception_entry *ex;
s4 nhandlers;
+ s4 blockendpc;
jitdata *mjd;
- bool speculative;
+ inline_site site;
assert(iln);
+ m = iln->m;
mjd = iln->jd;
/* initialize cumulative counters */
/* 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->icount > 0 || bptr->next != NULL)
+ if ((bptr != mjd->basicblocks || iln->blockbefore)
+ &&
+ (bptr->icount > 0 || bptr->next != NULL))
iln->cumul_basicblockcount++;
/* skip dead code */
len = bptr->icount;
iptr = bptr->iinstr;
- iln->instructioncount += len;
+ blockendpc += len;
iln->cumul_instructioncount += len;
- for (; --len >= 0; ++iptr) {
+ /* iterate over the instructions of the block */
- opcode = iptr->opc;
-
- switch (opcode) {
- /****************************************/
- /* INVOKATIONS */
+ for (; --len >= 0; ++iptr) {
+ switch (iptr->opc) {
case ICMD_INVOKEVIRTUAL:
case ICMD_INVOKESPECIAL:
case ICMD_INVOKESTATIC:
case ICMD_INVOKEINTERFACE:
- if (!INSTRUCTION_IS_UNRESOLVED(iptr)) {
+ if (!INSTRUCTION_IS_UNRESOLVED(iptr) && !iln->ctx->stopped) {
callee = iptr->sx.s23.s3.fmiref->p.method;
-#if 0
- if (
- (strcmp(callee->class->name->text, "spec/benchmarks/_201_compress/Code_Table") == 0
- && (strcmp(callee->name->text, "of") == 0
- || strcmp(callee->name->text, "set") == 0))
- ||
- (strcmp(callee->class->name->text, "spec/benchmarks/_201_compress/Compressor") == 0
- && (strcmp(callee->name->text, "output") == 0))
- ||
- (strcmp(callee->class->name->text, "spec/benchmarks/_201_compress/Decompressor") == 0
- && (strcmp(callee->name->text, "getcode") == 0))
- ||
- (strcmp(callee->class->name->text, "spec/benchmarks/_201_compress/Output_Buffer") == 0
- && (strcmp(callee->name->text, "putbyte") == 0))
- ||
- (strcmp(callee->class->name->text, "spec/benchmarks/_201_compress/Input_Buffer") == 0
- && (strcmp(callee->name->text, "getbyte") == 0
- || strcmp(callee->name->text, "readbytes") == 0
- ))
- )
- goto force_inline;
-
- if (callee->jcodelength > 0)
- goto dont_inline;
-#endif
-
- if (callee->flags & ACC_NATIVE)
- goto dont_inline;
-
- if (iln->depth >= 3)
- goto dont_inline;
-
- if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)
- || opcode == ICMD_INVOKESPECIAL)) {
- speculative = false;
- goto maybe_inline;
- }
-
- if (callee->flags & ACC_METHOD_MONOMORPHIC) {
- /* XXX */
- if (0
- && strncmp(callee->class->name->text, "java/", 5) != 0
- && strncmp(callee->class->name->text, "gnu/", 4) != 0
- && strstr(callee->class->name->text, "compress") != NULL
- )
- {
- DOLOG( printf("SPECULATIVE INLINE: "); method_println(callee); );
- speculative = true;
- goto maybe_inline;
- }
- }
-
- /* polymorphic call site */
- goto dont_inline;
+ 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;
-maybe_inline:
- for (active = iln; active; active = active->parent) {
- if (callee == active->m) {
- DOLOG( printf("RECURSIVE!\n") );
- goto dont_inline;
+ if (!inline_process_candidate(&cand))
+ return false;
+#endif
}
}
-#if 0
-force_inline:
-#endif
- if (!inline_analyse_callee(iln, callee,
- bptr,
- iptr,
- iln->instructioncount - len - 1 /* XXX ugly */,
- handlers,
- nhandlers))
- return false;
-
- if (speculative)
- method_add_assumption_monomorphic(callee, iln->ctx->master->m);
}
-dont_inline:
break;
case ICMD_RETURN:
}
+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]--
}
-/* main driver function *******************************************************/
+/* inline_create_root_node *****************************************************
-bool inline_inline(jitdata *jd, jitdata **resultjd)
-{
- inline_node *iln;
- methodinfo *m;
+ Create the root node of the inlining tree.
- m = jd->m;
+ IN:
+ jd...............the current jitdata of the root method
- *resultjd = jd;
+ RETURN VALUE:
+ the root node of the inlining tree
- DOLOG( printf("==== INLINE ==================================================================\n");
- show_method(jd, SHOW_STACK); );
+*******************************************************************************/
+
+static inline_node * inline_create_root_node(jitdata *jd)
+{
+ inline_node *iln;
iln = DNEW(inline_node);
MZERO(iln, inline_node, 1);
- iln->ctx = DNEW(inline_context);
- MZERO(iln->ctx, inline_context, 1);
- iln->ctx->master = iln;
- iln->ctx->calls_others = false;
- iln->m = m;
+ iln->m = jd->m;
iln->jd = jd;
iln->regdata = jd->rd;
- iln->ctx->next_debugnr = 1; /* XXX debug */
iln->blockbefore = true;
iln->blockafter = true;
- /* we cannot use m->instructioncount because it may be greater than
- * the actual number of instructions in the basic blocks. */
- iln->instructioncount = 0;
iln->cumul_instructioncount = 0;
iln->cumul_basicblockcount = 1 /* dummy end block */;
- if (inline_inline_intern(m, iln)) {
+ /* create inlining context */
- DOLOG( printf("==== TEST INLINE =============================================================\n"); );
+ 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)
- test_inlining(iln, jd, resultjd);
+ inline_transform(iln, jd);
+
+#if defined(INLINE_STATISTICS)
+ inline_gather_statistics(iln);
+#endif
}
DOLOG( printf("-------- DONE -----------------------------------------------------------\n");
- fflush(stdout); );
+ fflush(stdout); );
return true;
}
projects / cacao.git / blobdiff