/* 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
+ Copyright (C) 1996-2005, 2006, 2007, 2008
+ CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
This file is part of CACAO.
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.hpp"
+#include "threads/mutex.hpp"
+#include "threads/thread.hpp"
+
#include "toolbox/logging.h"
-#include "vm/builtin.h"
+
+#include "vm/jit/builtin.hpp"
+#include "vm/class.hpp"
#include "vm/global.h"
+#include "vm/initialize.hpp"
+#include "vm/method.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/jit.hpp"
+#include "vm/jit/parse.hpp"
#include "vm/jit/reg.h"
+#include "vm/jit/show.hpp"
#include "vm/jit/stack.h"
+#include "vm/jit/inline/inline.h"
+#include "vm/jit/loop/loop.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_TraceInlining >= 2) { code; } }while(0)
+#define DOLOG_SHORT(code) do{ if (opt_TraceInlining >= 1) { code; } }while(0)
#else
#define DOLOG(code)
#endif
+#if defined(ENABLE_VERIFIER) && !defined(NDEBUG)
+/* Define this to verify the resulting code after inlining. */
+/* Note: This is only useful for development and may require patches to the */
+/* verifier code. */
+/* #define INLINE_VERIFY_RESULT */
+#endif
+
/* types **********************************************************************/
typedef struct inline_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
/* call parse pass */
- DOLOG( log_message_class("Parsing ", m->class) );
+ DOLOG( log_message_class("Parsing ", m->clazz) );
if (!parse(jd)) {
return false;
}
m = iln->m;
assert(m);
-#if defined(ENABLE_THREADS)
/* enter a monitor on the method */
- lock_monitor_enter((java_objectheader *) m);
-#endif
+
+ Mutex_lock(m->mutex);
/* 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
+
+ Mutex_unlock(m->mutex);
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;
+}
+
+
+#if 0
+static void inline_add_blocknr_reference(inline_node *iln, s4 *nrp)
+{
+ inline_target_ref *ref;
+
+ ref = DNEW(inline_target_ref);
+ ref->ref.nr = nrp;
+ ref->isnumber = true;
ref->next = iln->refs;
iln->refs = ref;
}
+#endif
static void inline_block_translation(inline_node *iln, basicblock *o_bptr, basicblock *n_bptr)
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);
- }
- }
-#endif
-
- *(ref->ref) = n_bptr;
- if (prev) {
- prev->next = ref->next;
+ for (ref = *refs; ref != NULL; ref = ref->next) {
+ if (ref->isnumber && !returnref) {
+ if (*(ref->ref.nr) == JAVALOCAL_FROM_RETADDR(o_bptr->nr)) {
+ *(ref->ref.nr) = JAVALOCAL_FROM_RETADDR(n_bptr->nr);
+ goto remove_ref;
}
- else {
- *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->clazz;
+ n_ins->dst.varindex = syncvar;
+ n_ins->flags.bits |= INS_FLAG_CLASS;
+ }
+ else {
+ syncvar = instancevar;
+ }
+
+ assert(syncvar != UNUSED);
+
+ /* MONITORENTER / MONITOREXIT */
+
+ n_ins = inline_instruction(iln, ICMD_BUILTIN, o_iptr);
+ n_ins->sx.s23.s3.bte = builtintable_get_internal(func);
+ n_ins->s1.argcount = 1; /* XXX add through-vars */
+ n_ins->sx.s23.s2.args = DMNEW(s4, 1);
+ n_ins->sx.s23.s2.args[0] = syncvar;
+}
+
static s4 emit_inlining_prolog(inline_node *iln,
inline_node *callee,
instruction *o_iptr,
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;
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->sx.val.c.cls = iln->m->clazz;
n_ins->flags.bits = INS_FLAG_CLASS;
}
else {
/* 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); );
if (!typecheck(n_jd)) {
- *exceptionptr = NULL;
+ exceptions_clear_exception();
DOLOG( printf("XXX INLINED RESULT DID NOT PASS VERIFIER XXX\n") );
return false;
}
}
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 = 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(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_InlineMinSize)
+ && (n_jd->instructioncount <= opt_InlineMaxSize))
{
- 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_InlineCount)
+#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);
+ DOLOG_SHORT(
+ printf("==== %d.INLINE ==================================================================\n",
+ debug_counter);
printf("\ninline tree:\n");
dump_inline_tree(iln, 0);
n_jd->flags |= JITDATA_FLAG_SHOWINTERMEDIATE | JITDATA_FLAG_SHOWDISASSEMBLE;
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;
- /* info about the call site */
+ /* 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->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 */
+
+ /* for synchronized instance methods */
+ /* we need an COPY, MONITORENTER in the prolog */
+ /* and MONITOREXIT in the epilog */
- if (!isstatic) {
- cn->prolog_instructioncount += 1;
+ 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) {
-
- opcode = iptr->opc;
+ /* iterate over the instructions of the block */
- 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]--
static void inline_post_process(jitdata *jd)
{
+ codeinfo *code;
basicblock *bptr;
instruction *iptr;
instruction *iend;
methoddesc *md;
builtintable_entry *bte;
+ /* Get required compiler data. */
+
+ code = jd->code;
+
/* reset the SAVEDVAR flag of all variables */
for (i=0; i<jd->vartop; ++i)
POSTPROCESS_SRCOP(s1);
case DF_0_TO_0:
if (icmdt->flags & ICMDTABLE_CALLS) {
- jd->isleafmethod = false;
+ code_unflag_leafmethod(code);
MARK_ALL_SAVED;
}
break;
POSTPROCESS_SRCOP(s1);
case DF_0_TO_1:
if (icmdt->flags & ICMDTABLE_CALLS) {
- jd->isleafmethod = false;
+ code_unflag_leafmethod(code);
MARK_ALL_SAVED;
}
case DF_COPY:
POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
}
if (icmdt->flags & ICMDTABLE_CALLS) {
- jd->isleafmethod = false;
+ code_unflag_leafmethod(code);
MARK_ALL_SAVED;
}
POSTPROCESS_DSTOP(dst);
case DF_INVOKE:
INSTRUCTION_GET_METHODDESC(iptr, md);
post_process_call:
- jd->isleafmethod = false;
+ code_unflag_leafmethod(code);
for (i=0; i<md->paramcount; ++i) {
POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
}
}
-/* 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