/* 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 7209 2007-01-13 22:30:25Z 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/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.h"
+#include "vm/jit/parse.h"
#include "vm/jit/reg.h"
+#include "vm/jit/show.h"
#include "vm/jit/stack.h"
+#include "vm/jit/inline/inline.h"
+#include "vm/jit/loop/loop.h"
+
#include "vm/jit/verify/typecheck.h"
-#if defined(ENABLE_THREADS)
-# include "threads/native/threads.h"
-#endif
+#include "vmcore/class.h"
+#include "vmcore/method.h"
+#include "vmcore/options.h"
+#include "vmcore/statistics.h"
/* algorithm tuning constants *************************************************/
+/* Algorithm Selection */
+/* Define exactly one of the following three to select the inlining */
+/* heuristics. */
+
+/*#define INLINE_DEPTH_FIRST*/
+/*#define INLINE_BREADTH_FIRST*/
#define INLINE_KNAPSACK
+/* Parameters for knapsack heuristics: */
+
#if defined(INLINE_KNAPSACK)
#define INLINE_COUNTDOWN_INIT 1000
/*#define INLINE_MAX_DEPTH 3*/
/*#define INLINE_DIVIDE_COST_BY_FREQ */
-#else
+#endif
+
+/* Parameters for depth-first heuristics: */
+
+#if defined(INLINE_DEPTH_FIRST)
#define INLINE_MAX_DEPTH 3
#define INLINE_MAX_BLOCK_EXPANSION 10
#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;
-#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 **********************************************************************/
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 candidate handling ************************************************/
-#if defined(INLINE_KNAPSACK)
+#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
static void inline_add_candidate(inline_context *ctx,
inline_node *caller,
methodinfo *callee,
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;
}
}
}
-#endif /* defined(INLINE_KNAPSACK) */
+#endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */
-#if defined(INLINE_KNAPSACK)
+#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
static inline_candidate * inline_pick_best_candidate(inline_context *ctx)
{
inline_candidate *cand;
return cand;
}
-#endif /* defined(INLINE_KNAPSACK) */
+#endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */
-#if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
+#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) */
+#endif /* !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)) */
-#if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
+#if !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST))
static void inline_candidates_println(inline_context *ctx)
{
inline_candidate *cand;
inline_candidate_println(cand);
}
}
-#endif /* !defined(NDEBUG) && defined(INLINE_KNAPSACK) */
+#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;
#define INLINE_RETURN_REFERENCE(callee) \
( (basicblock *) (ptrint) (0x333 + (callee)->depth) )
-#define RETADDRNR_FROM_BLOCK(bptr) (UNUSED - 1 - (bptr)->nr)
-
static void inline_add_block_reference(inline_node *iln, basicblock **blockp)
{
prev = NULL;
for (ref = *refs; ref != NULL; ref = ref->next) {
if (ref->isnumber && !returnref) {
- if (*(ref->ref.nr) == RETADDRNR_FROM_BLOCK(o_bptr)) {
- *(ref->ref.nr) = RETADDRNR_FROM_BLOCK(n_bptr);
+ if (*(ref->ref.nr) == JAVALOCAL_FROM_RETADDR(o_bptr->nr)) {
+ *(ref->ref.nr) = JAVALOCAL_FROM_RETADDR(n_bptr->nr);
goto remove_ref;
}
}
int type;
instruction *n_ins;
insinfo_inline *insinfo;
- s4 argvar;
+ s4 varindex;
assert(iln && callee && o_iptr);
/* 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 */
if (!callee->isstatic && i == 0 && calleem->name != utf_init) {
assert(type == TYPE_ADR);
n_ins = inline_instruction(iln, ICMD_CHECKNULL, o_iptr);
- n_ins->s1.varindex = argvar;
+ n_ins->s1.varindex = varindex;
n_ins->dst.varindex = n_ins->s1.varindex;
}
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);
}
/* this value is not used, pop it */
n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
- n_ins->s1.varindex = argvar;
+ n_ins->s1.varindex = varindex;
}
DOLOG( printf("%sprolog: ", iln->indent);
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); );
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 */
/* 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) && 0
+ /* 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) */
{
/* install the inlined result */
n_jd->code = jd->code;
*jd = *n_jd;
+ /* statistics and logging */
+
#if !defined(NDEBUG)
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;
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)
- || (caller->cumul_basicblockcount + callee->cumul_basicblockcount
+ || (cumulator->cumul_basicblockcount + callee->cumul_basicblockcount
> INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
#endif
#if defined(INLINE_MAX_ICMD_EXPANSION)
- || (caller->cumul_instructioncount + callee->cumul_instructioncount
+ || (cumulator->cumul_instructioncount + callee->cumul_instructioncount
> INLINE_MAX_ICMD_EXPANSION*caller->ctx->master->jd->instructioncount)
#endif
)
/* cumulate counters */
-#if !defined(INLINE_KNAPSACK)
+#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;
}
site.nhandlers = nhandlers;
if (inline_pre_parse_heuristics(iln, callee, &site)) {
-#if defined(INLINE_KNAPSACK)
+#if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
inline_add_candidate(iln->ctx, iln, callee, &site);
#else
inline_candidate cand;
*******************************************************************************/
+#if defined(INLINE_KNAPSACK)
static bool inline_make_inlining_plan(inline_node *iln)
{
-#if defined(INLINE_KNAPSACK)
inline_candidate *cand;
#if defined(INLINE_COST_BUDGET)
s4 budget = INLINE_COST_BUDGET;
inline_cumulate_counters_recursive(iln);
return true;
-#else
+}
+#endif /* defined(INLINE_KNAPSACK) */
+
+
+#if defined(INLINE_DEPTH_FIRST)
+static bool inline_make_inlining_plan(inline_node *iln)
+{
return inline_analyse_code(iln);
-#endif
}
+#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 *****************************************************************/
projects / cacao.git / blobdiff