1 /* src/vm/jit/inline/inline.c - method inlining
3 Copyright (C) 1996-2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
4 C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
5 E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
6 J. Wenninger, Institut f. Computersprachen - TU Wien
8 This file is part of CACAO.
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2, or (at
13 your option) any later version.
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
37 #include "mm/memory.h"
39 #include "threads/lock-common.h"
40 #include "threads/threads-common.h"
42 #include "toolbox/logging.h"
44 #include "vm/builtin.h"
45 #include "vm/global.h"
46 #include "vm/initialize.h"
48 #include "vm/jit/jit.h"
49 #include "vm/jit/parse.h"
50 #include "vm/jit/reg.h"
51 #include "vm/jit/show.h"
52 #include "vm/jit/stack.h"
54 #include "vm/jit/inline/inline.h"
55 #include "vm/jit/loop/loop.h"
57 #include "vm/jit/verify/typecheck.h"
59 #include "vmcore/class.h"
60 #include "vmcore/method.h"
61 #include "vmcore/options.h"
62 #include "vmcore/statistics.h"
65 /* algorithm tuning constants *************************************************/
67 /* Algorithm Selection */
68 /* Define exactly one of the following three to select the inlining */
71 /*#define INLINE_DEPTH_FIRST*/
72 /*#define INLINE_BREADTH_FIRST*/
73 #define INLINE_KNAPSACK
75 /* Parameters for knapsack heuristics: */
77 #if defined(INLINE_KNAPSACK)
79 #define INLINE_COUNTDOWN_INIT 1000
80 #define INLINE_COST_OFFSET -16
81 #define INLINE_COST_BUDGET 100
82 /*#define INLINE_WEIGHT_BUDGET 5.0*/
83 /*#define INLINE_ADD_NEGATIVE_TO_BUDGET*/
84 /*#define INLINE_MAX_DEPTH 3*/
85 /*#define INLINE_DIVIDE_COST_BY_FREQ */
89 /* Parameters for depth-first heuristics: */
91 #if defined(INLINE_DEPTH_FIRST)
93 #define INLINE_MAX_DEPTH 3
94 #define INLINE_MAX_BLOCK_EXPANSION 10
95 /*#define INLINE_MAX_ICMD_EXPANSION 10*/
96 /*#define INLINE_CANCEL_ON_THRESHOLD*/
100 /* Parameters for breadth-first heuristics: */
102 #if defined(INLINE_BREADTH_FIRST)
104 /*#define INLINE_MAX_BLOCK_EXPANSION 10*/
105 #define INLINE_MAX_ICMD_EXPANSION 5
110 /* debugging ******************************************************************/
113 #define INLINE_VERBOSE
114 #define DOLOG(code) do{ if (opt_inline_debug_log) { code; } }while(0)
119 #if defined(ENABLE_VERIFIER) && !defined(NDEBUG)
120 /* Define this to verify the resulting code after inlining. */
121 /* Note: This is only useful for development and may require patches to the */
123 /* #define INLINE_VERIFY_RESULT */
127 /* types **********************************************************************/
129 typedef struct inline_node inline_node;
130 typedef struct inline_target_ref inline_target_ref;
131 typedef struct inline_context inline_context;
132 typedef struct inline_block_map inline_block_map;
133 typedef struct inline_site inline_site;
134 typedef struct inline_candidate inline_candidate;
141 inline_node *children;
142 inline_node *next; /* next node at this depth */
143 inline_node *prev; /* prev node at this depth */
144 int depth; /* inlining depth, 0 for root */
146 /* info about the call site (if depth > 0)*/
147 inline_node *parent; /* node of the caller (NULL for root) */
148 basicblock *callerblock; /* original block containing the INVOKE* */
149 instruction *callerins; /* the original INVOKE* instruction */
151 s4 *n_passthroughvars;
152 int n_passthroughcount;
153 int n_selfpassthroughcount; /* # of pass-through vars of the call itself */
154 exception_entry **o_handlers;
155 int n_handlercount; /* # of handlers protecting this call */
157 int synclocal; /* variable used for synchr., or UNUSED */
158 bool isstatic; /* this is a static call */
160 bool blockbefore; /* block boundary before inlined body? */
161 bool blockafter; /* block boundary after inlined body? */
163 /* info about the callee */
165 int prolog_instructioncount; /* # of ICMDs in the inlining prolog */
166 int epilog_instructioncount; /* # of ICMDs in the inlining epilog */
167 int extra_instructioncount;
168 int extra_exceptiontablelength; /* # of extra handlers to put in caller */
169 bool synchronize; /* do we have to synchronize enter/exit? */
170 basicblock *handler_monitorexit; /* handler for synchronized inlinees */
173 /* cumulative values */
174 int cumul_instructioncount; /* ICMDs in this node and its children */
175 int cumul_basicblockcount; /* BBs started by this node and its children */
176 int cumul_basicblockcount_root; /* BBs that have to be added to the root */
177 /* node if this node is inlined */
178 int cumul_blockmapcount;
180 int cumul_exceptiontablelength;
183 instruction *inlined_iinstr;
184 instruction *inlined_iinstr_cursor;
185 basicblock *inlined_basicblocks;
186 basicblock *inlined_basicblocks_cursor;
189 registerdata *regdata;
192 inline_target_ref *refs;
193 instruction *inline_start_instruction;
201 struct inline_target_ref {
202 inline_target_ref *next;
211 struct inline_block_map {
217 struct inline_context {
222 inline_candidate *candidates;
224 int next_block_number;
225 inline_block_map *blockmap;
232 int next_debugnr; /* XXX debug */
236 bool speculative; /* true, if inlining would be speculative */
237 bool inlined; /* true, if this site has been inlined */
239 basicblock *bptr; /* basic block containing the call site */
240 instruction *iptr; /* the invocation instruction */
241 exception_entry **handlers; /* active handlers at the call site */
242 s4 nhandlers; /* number of active handlers */
243 s4 pc; /* PC of the invocation instruction */
246 struct inline_candidate {
247 inline_candidate *next;
257 /* prototypes *****************************************************************/
259 static bool inline_analyse_code(inline_node *iln);
260 static void inline_post_process(jitdata *jd);
263 /* debug helpers **************************************************************/
266 #include "inline_debug.inc"
270 /* statistics *****************************************************************/
272 /*#define INLINE_STATISTICS*/
275 #define INLINE_STATISTICS
278 #if defined(INLINE_STATISTICS)
279 int inline_stat_roots = 0;
280 int inline_stat_roots_transformed = 0;
281 int inline_stat_inlined_nodes = 0;
282 int inline_stat_max_depth = 0;
284 void inline_print_stats()
286 printf("inlining statistics:\n");
287 printf(" roots analysed : %d\n", inline_stat_roots);
288 printf(" roots transformed: %d\n", inline_stat_roots_transformed);
289 printf(" inlined nodes : %d\n", inline_stat_inlined_nodes);
290 printf(" max depth : %d\n", inline_stat_max_depth);
295 /* compilation of callees *****************************************************/
297 static bool inline_jit_compile_intern(jitdata *jd)
301 /* XXX should share code with jit.c */
305 /* XXX initialize the static function's class */
309 /* call the compiler passes ***********************************************/
311 /* call parse pass */
313 DOLOG( log_message_class("Parsing ", m->class) );
318 /* call stack analysis pass */
320 if (!stack_analyse(jd)) {
328 static bool inline_jit_compile(inline_node *iln)
334 /* XXX should share code with jit.c */
340 /* enter a monitor on the method */
342 LOCK_MONITOR_ENTER(m);
344 /* allocate jitdata structure and fill it */
346 jd = jit_jitdata_new(m);
349 jd->flags = 0; /* XXX */
351 /* initialize the register allocator */
355 /* setup the codegendata memory */
357 /* XXX do a pseudo setup */
358 jd->cd = DNEW(codegendata);
359 MZERO(jd->cd, codegendata, 1);
361 /* XXX uses too much dump memory codegen_setup(jd); */
363 /* now call internal compile function */
365 r = inline_jit_compile_intern(jd);
368 iln->regdata = jd->rd;
371 /* free some memory */
374 #if defined(ENABLE_JIT)
375 # if defined(ENABLE_INTRP)
383 /* leave the monitor */
385 LOCK_MONITOR_EXIT(m);
391 /* inlining tree handling *****************************************************/
393 static void inline_insert_inline_node(inline_node *parent, inline_node *child)
398 assert(parent && child);
400 child->parent = parent;
402 child->debugnr = parent->ctx->next_debugnr++; /* XXX debug */
404 first = parent->children;
406 /* insert as only node */
407 parent->children = child;
413 /* {there is at least one child already there} */
415 /* XXX is this search necessary, or could we always add at the end? */
418 while (succ->callerpc < child->callerpc) {
421 /* insert as last node */
422 child->prev = first->prev;
424 child->prev->next = child;
425 child->next->prev = child;
430 assert(succ->callerpc > child->callerpc);
432 /* insert before succ */
434 child->prev = succ->prev;
436 child->prev->next = child;
437 child->next->prev = child;
439 if (parent->children == succ)
440 parent->children = child;
444 static void inline_remove_inline_node(inline_node *parent, inline_node *child)
448 assert(child->parent == parent);
450 if (child->prev == child) {
451 /* remove the only child node */
452 parent->children = NULL;
455 child->prev->next = child->next;
456 child->next->prev = child->prev;
458 if (parent->children == child)
459 parent->children = child->next;
464 /* inlining candidate handling ************************************************/
466 #if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
467 static void inline_add_candidate(inline_context *ctx,
472 inline_candidate **link;
473 inline_candidate *cand;
475 cand = DNEW(inline_candidate);
476 #if defined(INLINE_DIVIDE_COST_BY_FREQ)
477 cand->freq = INLINE_COUNTDOWN_INIT - callee->hitcountdown;
481 #if defined(INLINE_KNAPSACK)
482 cand->cost = callee->jcodelength + INLINE_COST_OFFSET;
484 #if defined(INLINE_BREADTH_FIRST)
485 cand->cost = caller->depth;
487 cand->caller = caller;
488 cand->callee = callee;
491 cand->weight = (double)cand->cost / cand->freq;
493 for (link = &(ctx->candidates); ; link = &((*link)->next)) {
494 if (!*link || (*link)->weight > cand->weight) {
501 #endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */
503 #if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
504 static inline_candidate * inline_pick_best_candidate(inline_context *ctx)
506 inline_candidate *cand;
508 cand = ctx->candidates;
511 ctx->candidates = cand->next;
515 #endif /* defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST) */
517 #if !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST))
518 static void inline_candidate_println(inline_candidate *cand)
520 printf("%10g (%5d / %5d) depth %2d ",
521 cand->weight, cand->cost, cand->freq, cand->caller->depth + 1);
522 method_println(cand->callee);
524 #endif /* !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)) */
527 #if !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST))
528 static void inline_candidates_println(inline_context *ctx)
530 inline_candidate *cand;
532 for (cand = ctx->candidates; cand != NULL; cand = cand->next) {
534 inline_candidate_println(cand);
537 #endif /* !defined(NDEBUG) && (defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)) */
540 /* variable handling **********************************************************/
542 static s4 inline_new_variable(jitdata *jd, s4 type, s4 flags)
547 index = jd->vartop++;
548 if (index >= jd->varcount) {
549 newcount = jd->vartop * 2; /* XXX */
550 jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, newcount);
551 MZERO(jd->var + jd->varcount, varinfo, (newcount - jd->varcount));
552 jd->varcount = newcount;
555 jd->var[index].type = type;
556 jd->var[index].flags = flags;
562 static s4 inline_new_variable_clone(jitdata *jd, jitdata *origjd, s4 origidx)
567 v = &(origjd->var[origidx]);
569 newidx = inline_new_variable(jd, v->type, v->flags);
571 jd->var[newidx].vv = v->vv;
577 static s4 inline_new_temp_variable(jitdata *jd, s4 type)
579 return inline_new_variable(jd, type, 0);
583 static s4 inline_translate_variable(jitdata *jd, jitdata *origjd, s4 *varmap, s4 index)
590 idx = inline_new_variable_clone(jd, origjd, index);
598 static s4 *create_variable_map(inline_node *callee)
607 /* create the variable mapping */
609 varmap = DMNEW(s4, callee->jd->varcount);
610 for (i=0; i<callee->jd->varcount; ++i)
613 /* translate local variables */
615 for (i=0; i<callee->m->maxlocals; ++i) {
616 for (t=0; t<5; ++t) {
617 varindex = callee->jd->local_map[5*i + t];
618 if (varindex == UNUSED)
621 v = &(callee->jd->var[varindex]);
622 assert(v->type == t || v->type == TYPE_VOID); /* XXX stack leaves VOID */
623 v->type = t; /* XXX restore if it is TYPE_VOID */
625 avail = callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t];
627 if (avail == UNUSED) {
628 avail = inline_new_variable_clone(callee->ctx->resultjd, callee->jd, varindex);
629 callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t] = avail;
632 varmap[varindex] = avail;
636 /* for synchronized instance methods we need an extra local */
638 if (callee->synchronize && !(callee->m->flags & ACC_STATIC)) {
639 n_javaindex = callee->localsoffset - 1;
640 assert(n_javaindex >= 0);
641 assert(callee->parent);
642 assert(n_javaindex == callee->parent->localsoffset + callee->parent->m->maxlocals);
644 avail = callee->ctx->resultjd->local_map[5*n_javaindex + TYPE_ADR];
646 if (avail == UNUSED) {
647 avail = inline_new_variable(callee->ctx->resultjd, TYPE_ADR, 0);
648 callee->ctx->resultjd->local_map[5*n_javaindex + TYPE_ADR] = avail;
651 callee->synclocal = avail;
654 callee->synclocal = UNUSED;
661 /* basic block translation ****************************************************/
663 #define INLINE_RETURN_REFERENCE(callee) \
664 ( (basicblock *) (ptrint) (0x333 + (callee)->depth) )
667 static void inline_add_block_reference(inline_node *iln, basicblock **blockp)
669 inline_target_ref *ref;
671 ref = DNEW(inline_target_ref);
672 ref->ref.block = blockp;
673 ref->isnumber = false;
674 ref->next = iln->refs;
679 static void inline_add_blocknr_reference(inline_node *iln, s4 *nrp)
681 inline_target_ref *ref;
683 ref = DNEW(inline_target_ref);
685 ref->isnumber = true;
686 ref->next = iln->refs;
691 static void inline_block_translation(inline_node *iln, basicblock *o_bptr, basicblock *n_bptr)
696 assert(ctx->blockmap_index < ctx->master->cumul_blockmapcount);
698 ctx->blockmap[ctx->blockmap_index].iln = iln;
699 ctx->blockmap[ctx->blockmap_index].o_block = o_bptr;
700 ctx->blockmap[ctx->blockmap_index].n_block = n_bptr;
702 ctx->blockmap_index++;
706 static basicblock * inline_map_block(inline_node *iln,
708 inline_node *targetiln)
710 inline_block_map *bm;
711 inline_block_map *bmend;
719 bm = iln->ctx->blockmap;
720 bmend = bm + iln->ctx->blockmap_index;
723 assert(bm->iln && bm->o_block && bm->n_block);
724 if (bm->o_block == o_block && bm->iln == targetiln)
730 return NULL; /* not reached */
734 static void inline_resolve_block_refs(inline_target_ref **refs,
739 inline_target_ref *ref;
740 inline_target_ref *prev;
743 for (ref = *refs; ref != NULL; ref = ref->next) {
744 if (ref->isnumber && !returnref) {
745 if (*(ref->ref.nr) == JAVALOCAL_FROM_RETADDR(o_bptr->nr)) {
746 *(ref->ref.nr) = JAVALOCAL_FROM_RETADDR(n_bptr->nr);
751 if (*(ref->ref.block) == o_bptr) {
752 *(ref->ref.block) = n_bptr;
763 /* remove this ref */
766 prev->next = ref->next;
775 /* basic block creation *******************************************************/
777 static basicblock * create_block(inline_node *container,
792 assert(indepth >= 0);
794 n_bptr = container->inlined_basicblocks_cursor++;
796 assert((n_bptr - container->inlined_basicblocks) < container->cumul_basicblockcount);
798 BASICBLOCK_INIT(n_bptr, iln->m);
800 n_bptr->iinstr = container->inlined_iinstr_cursor;
801 n_bptr->next = n_bptr + 1;
802 n_bptr->nr = container->ctx->next_block_number++;
803 n_bptr->indepth = indepth;
804 n_bptr->flags = BBFINISHED; /* XXX */
806 /* set the inlineinfo of the new block */
808 if (iln->inline_start_instruction)
809 n_bptr->inlineinfo = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
811 if (indepth > container->ctx->maxinoutdepth)
812 container->ctx->maxinoutdepth = indepth;
815 n_bptr->invars = DMNEW(s4, indepth);
818 for (i=0; i<indepth; ++i)
819 n_bptr->invars[i] = -1; /* XXX debug */
821 /* pass-through variables enter the block */
823 outer = inner->parent;
824 while (outer != NULL) {
825 depth = outer->n_passthroughcount;
827 assert(depth + inner->n_selfpassthroughcount <= indepth);
829 for (i=0; i<inner->n_selfpassthroughcount; ++i) {
830 varidx = inner->n_passthroughvars[i];
832 inline_new_variable_clone(container->ctx->resultjd,
835 n_bptr->invars[depth + i] = newvaridx;
836 outer->varmap[varidx] = newvaridx;
839 outer = outer->parent;
843 n_bptr->invars = NULL;
846 /* XXX for the verifier. should not be here */
851 dv = DMNEW(varinfo, iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
852 MZERO(dv, varinfo, iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
853 n_bptr->inlocals = dv;
860 static s4 *translate_javalocals(inline_node *iln, s4 *javalocals)
865 jl = DMNEW(s4, iln->jd->maxlocals);
867 for (i=0; i<iln->jd->maxlocals; ++i) {
870 j = inline_translate_variable(iln->ctx->resultjd, iln->jd, iln->varmap, j);
875 /* an encoded returnAddress value - must be relocated */
876 inline_add_blocknr_reference(iln, &(jl[i]));
885 static basicblock * create_body_block(inline_node *iln,
886 basicblock *o_bptr, s4 *varmap)
891 n_bptr = create_block(iln, iln, iln,
892 o_bptr->indepth + iln->n_passthroughcount);
894 n_bptr->type = o_bptr->type;
895 n_bptr->flags = o_bptr->flags;
896 n_bptr->bitflags = o_bptr->bitflags;
898 /* resolve references to this block */
900 inline_resolve_block_refs(&(iln->refs), o_bptr, n_bptr, false);
902 /* translate the invars of the original block */
904 for (i=0; i<o_bptr->indepth; ++i) {
905 n_bptr->invars[iln->n_passthroughcount + i] =
906 inline_translate_variable(iln->ctx->resultjd, iln->jd,
911 /* translate javalocals info (not for dead code) */
913 if (n_bptr->flags >= BBREACHED)
914 n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);
920 static basicblock * create_epilog_block(inline_node *caller, inline_node *callee, s4 *varmap)
926 /* number of return variables */
928 retcount = (callee->n_resultlocal == -1
929 && callee->m->parseddesc->returntype.type != TYPE_VOID) ? 1 : 0;
931 /* start the epilog block */
933 n_bptr = create_block(caller, caller, callee,
934 callee->n_passthroughcount + retcount);
936 /* resolve references to the return block */
938 inline_resolve_block_refs(&(callee->refs),
939 INLINE_RETURN_REFERENCE(callee),
943 /* return variable */
946 idx = inline_new_variable(caller->ctx->resultjd,
947 callee->m->parseddesc->returntype.type, 0 /* XXX */);
948 n_bptr->invars[callee->n_passthroughcount] = idx;
949 varmap[callee->callerins->dst.varindex] = idx;
954 n_bptr->javalocals = DMNEW(s4, caller->jd->maxlocals);
955 MCOPY(n_bptr->javalocals, caller->javalocals, s4, caller->jd->maxlocals);
957 /* set block flags & type */
959 n_bptr->flags = /* XXX original block flags */ BBFINISHED;
960 n_bptr->type = BBTYPE_STD;
966 static void close_block(inline_node *iln, inline_node *inner, basicblock *n_bptr, s4 outdepth)
973 n_bptr->outdepth = outdepth;
974 n_bptr->outvars = DMNEW(s4, outdepth);
976 for (i=0; i<outdepth; ++i)
977 n_bptr->outvars[i] = 0; /* XXX debug */
979 if (outdepth > iln->ctx->maxinoutdepth)
980 iln->ctx->maxinoutdepth = outdepth;
982 /* pass-through variables leave the block */
984 outer = inner->parent;
985 while (outer != NULL) {
986 depth = outer->n_passthroughcount;
988 assert(depth + inner->n_selfpassthroughcount <= outdepth);
990 for (i=0; i<inner->n_selfpassthroughcount; ++i) {
991 varidx = inner->n_passthroughvars[i];
992 n_bptr->outvars[depth + i] =
993 inline_translate_variable(iln->ctx->resultjd,
999 outer = outer->parent;
1004 static void close_prolog_block(inline_node *iln,
1006 inline_node *nextcall)
1008 /* XXX add original outvars! */
1009 close_block(iln, nextcall, n_bptr, nextcall->n_passthroughcount);
1011 /* pass-through variables */
1013 DOLOG( printf("closed prolog block:\n");
1014 show_basicblock(iln->ctx->resultjd, n_bptr, SHOW_STACK); );
1018 static void close_body_block(inline_node *iln,
1027 close_block(iln, iln, n_bptr, iln->n_passthroughcount + o_bptr->outdepth + retcount);
1029 /* translate the outvars of the original block */
1031 /* XXX reuse code */
1032 for (i=0; i<o_bptr->outdepth; ++i) {
1033 n_bptr->outvars[iln->n_passthroughcount + i] =
1034 inline_translate_variable(iln->ctx->resultjd, iln->jd, varmap,
1035 o_bptr->outvars[i]);
1038 /* set the return variable, if any */
1041 assert(retidx >= 0);
1042 n_bptr->outvars[iln->n_passthroughcount + o_bptr->outdepth] = retidx;
1047 /* inlined code generation ****************************************************/
1049 static instruction * inline_instruction(inline_node *iln,
1051 instruction *o_iptr)
1053 instruction *n_iptr;
1055 n_iptr = (iln->inlined_iinstr_cursor++);
1056 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1058 n_iptr->opc = opcode;
1059 n_iptr->flags.bits = o_iptr->flags.bits & INS_FLAG_ID_MASK;
1060 n_iptr->line = o_iptr->line;
1065 static void inline_generate_sync_builtin(inline_node *iln,
1066 inline_node *callee,
1067 instruction *o_iptr,
1074 if (callee->m->flags & ACC_STATIC) {
1076 syncvar = inline_new_temp_variable(iln->ctx->resultjd, TYPE_ADR);
1078 n_ins = inline_instruction(iln, ICMD_ACONST, o_iptr);
1079 n_ins->sx.val.c.cls = callee->m->class;
1080 n_ins->dst.varindex = syncvar;
1081 n_ins->flags.bits |= INS_FLAG_CLASS;
1084 syncvar = instancevar;
1087 assert(syncvar != UNUSED);
1089 /* MONITORENTER / MONITOREXIT */
1091 n_ins = inline_instruction(iln, ICMD_BUILTIN, o_iptr);
1092 n_ins->sx.s23.s3.bte = builtintable_get_internal(func);
1093 n_ins->s1.argcount = 1; /* XXX add through-vars */
1094 n_ins->sx.s23.s2.args = DMNEW(s4, 1);
1095 n_ins->sx.s23.s2.args[0] = syncvar;
1098 static s4 emit_inlining_prolog(inline_node *iln,
1099 inline_node *callee,
1100 instruction *o_iptr,
1103 methodinfo *calleem;
1109 insinfo_inline *insinfo;
1112 assert(iln && callee && o_iptr);
1114 calleem = callee->m;
1115 md = calleem->parseddesc;
1117 /* INLINE_START instruction */
1119 n_ins = inline_instruction(iln, ICMD_INLINE_START, o_iptr);
1121 insinfo = DNEW(insinfo_inline);
1122 insinfo->method = callee->m;
1123 insinfo->outer = iln->m;
1124 insinfo->synclocal = callee->synclocal;
1125 insinfo->synchronize = callee->synchronize;
1126 insinfo->javalocals_start = NULL;
1127 insinfo->javalocals_end = NULL;
1129 /* info about stack vars live at the INLINE_START */
1131 insinfo->throughcount = callee->n_passthroughcount;
1132 insinfo->paramcount = md->paramcount;
1133 insinfo->stackvarscount = o_iptr->s1.argcount;
1134 insinfo->stackvars = DMNEW(s4, insinfo->stackvarscount);
1135 for (i=0; i<insinfo->stackvarscount; ++i)
1136 insinfo->stackvars[i] = iln->varmap[o_iptr->sx.s23.s2.args[i]];
1138 /* info about the surrounding inlining */
1140 if (iln->inline_start_instruction)
1141 insinfo->parent = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
1143 insinfo->parent = NULL;
1145 /* finish the INLINE_START instruction */
1147 n_ins->sx.s23.s3.inlineinfo = insinfo;
1148 callee->inline_start_instruction = n_ins;
1150 DOLOG( printf("%sprolog: ", iln->indent);
1151 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1153 /* handle parameters for the inlined callee */
1155 localindex = callee->localsoffset + md->paramslots;
1157 for (i=md->paramcount-1; i>=0; --i) {
1160 type = md->paramtypes[i].type;
1162 localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
1163 assert(callee->regdata);
1165 /* translate the argument variable */
1167 varindex = varmap[o_iptr->sx.s23.s2.args[i]];
1168 assert(varindex != UNUSED);
1170 /* remove preallocation from the argument variable */
1172 iln->ctx->resultjd->var[varindex].flags &= ~(PREALLOC | INMEMORY);
1174 /* check the instance slot against NULL */
1175 /* we don't need that for <init> methods, as the verifier */
1176 /* ensures that they are only called for an uninit. object */
1177 /* (which may not be NULL). */
1179 if (!callee->isstatic && i == 0 && calleem->name != utf_init) {
1180 assert(type == TYPE_ADR);
1181 n_ins = inline_instruction(iln, ICMD_CHECKNULL, o_iptr);
1182 n_ins->s1.varindex = varindex;
1183 n_ins->dst.varindex = n_ins->s1.varindex;
1186 /* store argument into local variable of inlined callee */
1188 if (callee->jd->local_map[5*(localindex - callee->localsoffset) + type] != UNUSED)
1190 /* this value is used in the callee */
1192 if (i == 0 && callee->synclocal != UNUSED) {
1193 /* we also need it for synchronization, so copy it */
1194 assert(type == TYPE_ADR);
1195 n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
1198 n_ins = inline_instruction(iln, ICMD_ISTORE + type, o_iptr);
1199 n_ins->sx.s23.s3.javaindex = UNUSED;
1201 n_ins->s1.varindex = varindex;
1202 n_ins->dst.varindex = iln->ctx->resultjd->local_map[5*localindex + type];
1203 assert(n_ins->dst.varindex != UNUSED);
1205 else if (i == 0 && callee->synclocal != UNUSED) {
1206 /* the value is not used inside the callee, but we need it for */
1207 /* synchronization */
1208 /* XXX In this case it actually makes no sense to create a */
1209 /* separate synchronization variable. */
1211 n_ins = inline_instruction(iln, ICMD_NOP, o_iptr);
1214 /* this value is not used, pop it */
1216 n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
1217 n_ins->s1.varindex = varindex;
1220 DOLOG( printf("%sprolog: ", iln->indent);
1221 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1224 /* COPY for synchronized instance methods */
1226 if (callee->synclocal != UNUSED) {
1227 n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
1228 n_ins->s1.varindex = varmap[o_iptr->sx.s23.s2.args[0]];
1229 n_ins->dst.varindex = callee->synclocal;
1231 assert(n_ins->s1.varindex != UNUSED);
1234 if (callee->synchronize) {
1235 inline_generate_sync_builtin(iln, callee, o_iptr,
1236 (callee->isstatic) ? UNUSED : varmap[o_iptr->sx.s23.s2.args[0]],
1237 LOCK_monitor_enter);
1240 /* INLINE_BODY instruction */
1242 n_ins = inline_instruction(iln, ICMD_INLINE_BODY, callee->jd->basicblocks[0].iinstr);
1243 n_ins->sx.s23.s3.inlineinfo = insinfo;
1249 static void emit_inlining_epilog(inline_node *iln, inline_node *callee, instruction *o_iptr)
1254 assert(iln && callee && o_iptr);
1255 assert(callee->inline_start_instruction);
1257 if (callee->synchronize) {
1258 inline_generate_sync_builtin(iln, callee, o_iptr,
1263 /* INLINE_END instruction */
1265 n_ins = inline_instruction(iln, ICMD_INLINE_END, o_iptr);
1266 n_ins->sx.s23.s3.inlineinfo = callee->inline_start_instruction->sx.s23.s3.inlineinfo;
1268 /* set the javalocals */
1270 jl = DMNEW(s4, iln->jd->maxlocals);
1271 MCOPY(jl, iln->javalocals, s4, iln->jd->maxlocals);
1272 n_ins->sx.s23.s3.inlineinfo->javalocals_end = jl;
1274 DOLOG( printf("%sepilog: ", iln->indent);
1275 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1279 #define TRANSLATE_VAROP(vo) \
1280 n_iptr->vo.varindex = inline_translate_variable(jd, origjd, varmap, n_iptr->vo.varindex)
1283 static void inline_clone_instruction(inline_node *iln,
1287 instruction *o_iptr,
1288 instruction *n_iptr)
1290 icmdtable_entry_t *icmdt;
1291 builtintable_entry *bte;
1294 branch_target_t *table;
1295 lookup_target_t *lookup;
1300 icmdt = &(icmd_table[o_iptr->opc]);
1302 switch (icmdt->dataflow) {
1307 TRANSLATE_VAROP(sx.s23.s3);
1309 TRANSLATE_VAROP(sx.s23.s2);
1311 TRANSLATE_VAROP(s1);
1315 TRANSLATE_VAROP(sx.s23.s2);
1319 TRANSLATE_VAROP(s1);
1321 TRANSLATE_VAROP(dst);
1325 n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
1326 for (i=0; i<n_iptr->s1.argcount; ++i) {
1327 n_iptr->sx.s23.s2.args[i] =
1328 inline_translate_variable(jd, origjd, varmap,
1329 o_iptr->sx.s23.s2.args[i]);
1331 TRANSLATE_VAROP(dst);
1335 INSTRUCTION_GET_METHODDESC(n_iptr, md);
1337 n_iptr->s1.argcount += iln->n_passthroughcount;
1338 n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
1339 for (i=0; i<o_iptr->s1.argcount; ++i) {
1340 n_iptr->sx.s23.s2.args[i] =
1341 inline_translate_variable(jd, origjd, varmap,
1342 o_iptr->sx.s23.s2.args[i]);
1344 for (scope = iln; scope != NULL; scope = scope->parent) {
1345 for (j = 0; j < scope->n_selfpassthroughcount; ++j) {
1346 n_iptr->sx.s23.s2.args[i++] =
1347 scope->parent->varmap[scope->n_passthroughvars[j]];
1350 if (md->returntype.type != TYPE_VOID)
1351 TRANSLATE_VAROP(dst);
1355 bte = n_iptr->sx.s23.s3.bte;
1363 switch (icmdt->controlflow) {
1365 TRANSLATE_VAROP(s1); /* XXX should be handled by data-flow */
1369 inline_add_block_reference(iln, &(n_iptr->dst.block));
1373 inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.jsrtarget.block));
1377 i = n_iptr->sx.s23.s3.tablehigh - n_iptr->sx.s23.s2.tablelow + 1 + 1 /* default */;
1379 table = DMNEW(branch_target_t, i);
1380 MCOPY(table, o_iptr->dst.table, branch_target_t, i);
1381 n_iptr->dst.table = table;
1384 inline_add_block_reference(iln, &(table->block));
1390 inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.lookupdefault.block));
1392 i = n_iptr->sx.s23.s2.lookupcount;
1393 lookup = DMNEW(lookup_target_t, i);
1394 MCOPY(lookup, o_iptr->dst.lookup, lookup_target_t, i);
1395 n_iptr->dst.lookup = lookup;
1398 inline_add_block_reference(iln, &(lookup->target.block));
1404 /* XXX move this to dataflow section? */
1406 switch (n_iptr->opc) {
1409 if (n_iptr->flags.bits & INS_FLAG_RETADDR)
1410 inline_add_blocknr_reference(iln, &(n_iptr->sx.s23.s2.retaddrnr));
1417 stack_javalocals_store(n_iptr, iln->javalocals);
1423 static void inline_rewrite_method(inline_node *iln)
1427 instruction *o_iptr;
1428 instruction *n_iptr;
1429 inline_node *nextcall;
1431 inline_block_map *bm;
1436 char indent[100]; /* XXX debug */
1442 resultjd = iln->ctx->resultjd;
1446 nextcall = iln->children;
1449 for (i=0; i<iln->depth; ++i)
1452 iln->indent = indent;
1454 DOLOG( printf("%srewriting: ", indent); method_println(iln->m);
1455 printf("%s(passthrough: %d+%d)\n",
1456 indent, iln->n_passthroughcount - iln->n_selfpassthroughcount,
1457 iln->n_passthroughcount); );
1459 /* set memory cursors */
1461 iln->inlined_iinstr_cursor = iln->inlined_iinstr;
1462 iln->inlined_basicblocks_cursor = iln->inlined_basicblocks;
1464 /* allocate temporary buffers */
1466 iln->javalocals = DMNEW(s4, iln->jd->maxlocals);
1468 /* loop over basic blocks */
1470 o_bptr = iln->jd->basicblocks;
1471 for (; o_bptr; o_bptr = o_bptr->next) {
1473 if (o_bptr->flags < BBREACHED) {
1475 /* ignore the dummy end block */
1477 if (o_bptr->icount == 0 && o_bptr->next == NULL) {
1478 /* enter the following block as translation, for exception handler ranges */
1479 inline_block_translation(iln, o_bptr, iln->inlined_basicblocks_cursor);
1484 printf("%s* skipping old L%03d (flags=%d, type=%d, oid=%d) of ",
1486 o_bptr->nr, o_bptr->flags, o_bptr->type,
1488 method_println(iln->m);
1491 n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1493 /* enter it in the blockmap */
1495 inline_block_translation(iln, o_bptr, n_bptr);
1497 close_body_block(iln, n_bptr, o_bptr, iln->varmap, 0, -1);
1501 len = o_bptr->icount;
1502 o_iptr = o_bptr->iinstr;
1505 printf("%s* rewriting old L%03d (flags=%d, type=%d, oid=%d) of ",
1507 o_bptr->nr, o_bptr->flags, o_bptr->type,
1509 method_println(iln->m);
1510 show_basicblock(iln->jd, o_bptr, SHOW_STACK);
1513 if (iln->blockbefore || o_bptr != iln->jd->basicblocks) {
1514 /* create an inlined clone of this block */
1516 n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1519 /* enter it in the blockmap */
1521 inline_block_translation(iln, o_bptr, n_bptr);
1523 /* initialize the javalocals */
1525 MCOPY(iln->javalocals, n_bptr->javalocals, s4, iln->jd->maxlocals);
1530 /* continue caller block */
1532 n_bptr = iln->inlined_basicblocks_cursor - 1;
1533 icount = n_bptr->icount;
1535 /* translate the javalocals */
1537 jl = translate_javalocals(iln, o_bptr->javalocals);
1538 iln->inline_start_instruction->sx.s23.s3.inlineinfo->javalocals_start = jl;
1540 MCOPY(iln->javalocals, jl, s4, iln->jd->maxlocals);
1543 /* iterate over the ICMDs of this block */
1548 while (--len >= 0) {
1550 DOLOG( fputs(indent, stdout); show_icmd(iln->jd, o_iptr, false, SHOW_STACK);
1553 /* handle calls that will be inlined */
1555 if (nextcall && o_iptr == nextcall->callerins) {
1557 /* write the inlining prolog */
1559 (void) emit_inlining_prolog(iln, nextcall, o_iptr, iln->varmap);
1560 icount += nextcall->prolog_instructioncount;
1562 /* end current block, or glue blocks together */
1564 n_bptr->icount = icount;
1566 if (nextcall->blockbefore) {
1567 close_prolog_block(iln, n_bptr, nextcall);
1573 /* check if the result is a local variable */
1575 if (nextcall->m->parseddesc->returntype.type != TYPE_VOID
1576 && o_iptr->dst.varindex < iln->jd->localcount)
1578 nextcall->n_resultlocal = iln->varmap[o_iptr->dst.varindex];
1581 nextcall->n_resultlocal = -1;
1583 /* set memory pointers in the callee */
1585 nextcall->inlined_iinstr = iln->inlined_iinstr_cursor;
1586 nextcall->inlined_basicblocks = iln->inlined_basicblocks_cursor;
1590 DOLOG( printf("%sentering inline ", indent);
1591 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1593 inline_rewrite_method(nextcall);
1595 DOLOG( printf("%sleaving inline ", indent);
1596 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1598 /* update memory cursors */
1600 assert(nextcall->inlined_iinstr_cursor
1601 <= iln->inlined_iinstr_cursor + nextcall->cumul_instructioncount);
1602 assert(nextcall->inlined_basicblocks_cursor
1603 == iln->inlined_basicblocks_cursor + nextcall->cumul_basicblockcount);
1604 iln->inlined_iinstr_cursor = nextcall->inlined_iinstr_cursor;
1605 iln->inlined_basicblocks_cursor = nextcall->inlined_basicblocks_cursor;
1607 /* start new block, or glue blocks together */
1609 if (nextcall->blockafter) {
1610 n_bptr = create_epilog_block(iln, nextcall, iln->varmap);
1614 n_bptr = iln->inlined_basicblocks_cursor - 1;
1615 icount = n_bptr->icount;
1619 /* emit inlining epilog */
1621 emit_inlining_epilog(iln, nextcall, o_iptr);
1622 icount += nextcall->epilog_instructioncount;
1624 /* proceed to next call */
1626 nextcall = nextcall->next;
1629 n_iptr = (iln->inlined_iinstr_cursor++);
1630 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1632 switch (o_iptr->opc) {
1634 if (iln->depth == 0)
1643 if (iln->depth == 0)
1646 retidx = iln->varmap[o_iptr->s1.varindex];
1647 if (iln->n_resultlocal != -1) {
1648 /* store result in a local variable */
1650 DOLOG( printf("USING RESULTLOCAL %d\n", iln->n_resultlocal); );
1651 /* This relies on the same sequence of types for */
1652 /* ?STORE and ?RETURN opcodes. */
1653 n_iptr->opc = ICMD_ISTORE + (o_iptr->opc - ICMD_IRETURN);
1654 n_iptr->s1.varindex = retidx;
1655 n_iptr->dst.varindex = iln->n_resultlocal;
1656 n_iptr->sx.s23.s3.javaindex = UNUSED; /* XXX set real javaindex? */
1661 n_iptr = (iln->inlined_iinstr_cursor++);
1662 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1665 else if ((retidx < resultjd->localcount && iln->blockafter)
1666 || !iln->blockafter) /* XXX do we really always need the MOVE? */
1668 /* local must not become outvar, insert a MOVE */
1670 n_iptr->opc = ICMD_MOVE;
1671 n_iptr->s1.varindex = retidx;
1672 retidx = inline_new_temp_variable(resultjd,
1673 resultjd->var[retidx].type);
1674 n_iptr->dst.varindex = retidx;
1676 n_iptr = (iln->inlined_iinstr_cursor++);
1677 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1681 if (iln->blockafter) {
1682 n_iptr->opc = ICMD_GOTO;
1683 n_iptr->dst.block = INLINE_RETURN_REFERENCE(iln);
1684 inline_add_block_reference(iln, &(n_iptr->dst.block));
1687 n_iptr->opc = ICMD_NOP;
1691 if (o_bptr->next == NULL || (o_bptr->next->icount==0 && o_bptr->next->next == NULL)) {
1692 n_iptr->opc = ICMD_NOP;
1701 inline_clone_instruction(iln, resultjd, iln->jd, iln->varmap, o_iptr, n_iptr);
1704 DOLOG( fputs(indent, stdout); show_icmd(resultjd, n_iptr, false, SHOW_STACK);
1713 /* end of basic block */
1715 if (iln->blockafter || (o_bptr->next && o_bptr->next->next)) {
1716 close_body_block(iln, n_bptr, o_bptr, iln->varmap, retcount, retidx);
1717 n_bptr->icount = icount;
1719 DOLOG( printf("closed body block:\n");
1720 show_basicblock(resultjd, n_bptr, SHOW_STACK); );
1723 n_bptr->icount = icount;
1724 assert(iln->parent);
1725 if (retidx != UNUSED)
1726 iln->parent->varmap[iln->callerins->dst.varindex] = retidx;
1730 bm = iln->ctx->blockmap;
1731 for (i=0; i<iln->ctx->blockmap_index; ++i, ++bm) {
1732 assert(bm->iln && bm->o_block && bm->n_block);
1734 inline_resolve_block_refs(&(iln->refs), bm->o_block, bm->n_block, false);
1737 #if !defined(NDEBUG)
1739 inline_target_ref *ref;
1742 if (!iln->depth || ref->isnumber || *(ref->ref.block) != INLINE_RETURN_REFERENCE(iln)) {
1743 DOLOG( printf("XXX REMAINING REF at depth %d: %p\n", iln->depth,
1744 (void*)*(ref->ref.block)) );
1754 static exception_entry * inline_exception_tables(inline_node *iln,
1755 exception_entry *n_extable,
1756 exception_entry **prevextable)
1760 exception_entry *et;
1764 assert(prevextable);
1766 child = iln->children;
1769 n_extable = inline_exception_tables(child, n_extable, prevextable);
1770 child = child->next;
1771 } while (child != iln->children);
1774 et = iln->jd->exceptiontable;
1775 for (; et != NULL; et = et->down) {
1777 MZERO(n_extable, exception_entry, 1);
1778 n_extable->start = inline_map_block(iln, et->start , iln);
1779 n_extable->end = inline_map_block(iln, et->end , iln);
1780 n_extable->handler = inline_map_block(iln, et->handler, iln);
1781 n_extable->catchtype = et->catchtype;
1784 (*prevextable)->down = n_extable;
1786 *prevextable = n_extable;
1791 if (iln->handler_monitorexit) {
1792 exception_entry **activehandlers;
1794 MZERO(n_extable, exception_entry, 1);
1795 n_extable->start = iln->inlined_basicblocks;
1796 n_extable->end = iln->inlined_basicblocks_cursor;
1797 n_extable->handler = iln->handler_monitorexit;
1798 n_extable->catchtype.any = NULL; /* finally */
1801 (*prevextable)->down = n_extable;
1803 *prevextable = n_extable;
1807 /* We have to protect the created handler with the same handlers */
1808 /* that protect the method body itself. */
1810 for (scope = iln; scope->parent != NULL; scope = scope->parent) {
1812 activehandlers = scope->o_handlers;
1813 assert(activehandlers);
1815 while (*activehandlers) {
1817 assert(scope->parent);
1819 MZERO(n_extable, exception_entry, 1);
1820 n_extable->start = iln->handler_monitorexit;
1821 n_extable->end = iln->handler_monitorexit + 1; /* XXX ok in this case? */
1822 n_extable->handler = inline_map_block(scope->parent,
1823 (*activehandlers)->handler,
1825 n_extable->catchtype = (*activehandlers)->catchtype;
1828 (*prevextable)->down = n_extable;
1830 *prevextable = n_extable;
1842 static void inline_locals(inline_node *iln)
1848 iln->varmap = create_variable_map(iln);
1850 child = iln->children;
1853 inline_locals(child);
1854 child = child->next;
1855 } while (child != iln->children);
1858 if (iln->regdata->memuse > iln->ctx->resultjd->rd->memuse)
1859 iln->ctx->resultjd->rd->memuse = iln->regdata->memuse;
1860 if (iln->regdata->argintreguse > iln->ctx->resultjd->rd->argintreguse)
1861 iln->ctx->resultjd->rd->argintreguse = iln->regdata->argintreguse;
1862 if (iln->regdata->argfltreguse > iln->ctx->resultjd->rd->argfltreguse)
1863 iln->ctx->resultjd->rd->argfltreguse = iln->regdata->argfltreguse;
1867 static void inline_interface_variables(inline_node *iln)
1874 resultjd = iln->ctx->resultjd;
1876 resultjd->interface_map = DMNEW(interface_info, 5*iln->ctx->maxinoutdepth);
1877 for (i=0; i<5*iln->ctx->maxinoutdepth; ++i)
1878 resultjd->interface_map[i].flags = UNUSED;
1880 for (bptr = resultjd->basicblocks; bptr != NULL; bptr = bptr->next) {
1881 assert(bptr->indepth <= iln->ctx->maxinoutdepth);
1882 assert(bptr->outdepth <= iln->ctx->maxinoutdepth);
1884 for (i=0; i<bptr->indepth; ++i) {
1885 v = &(resultjd->var[bptr->invars[i]]);
1887 if (v->type == TYPE_RET)
1888 v->flags |= PREALLOC;
1890 v->flags &= ~PREALLOC;
1891 v->flags &= ~INMEMORY;
1892 assert(bptr->invars[i] >= resultjd->localcount);
1894 if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1895 resultjd->interface_map[5*i + v->type].flags = v->flags;
1898 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1902 for (i=0; i<bptr->outdepth; ++i) {
1903 v = &(resultjd->var[bptr->outvars[i]]);
1905 if (v->type == TYPE_RET)
1906 v->flags |= PREALLOC;
1908 v->flags &= ~PREALLOC;
1909 v->flags &= ~INMEMORY;
1910 assert(bptr->outvars[i] >= resultjd->localcount);
1912 if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1913 resultjd->interface_map[5*i + v->type].flags = v->flags;
1916 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1923 static void inline_write_exception_handlers(inline_node *master, inline_node *iln)
1928 builtintable_entry *bte;
1933 child = iln->children;
1936 inline_write_exception_handlers(master, child);
1937 child = child->next;
1938 } while (child != iln->children);
1941 if (iln->synchronize) {
1942 /* create the monitorexit handler */
1943 n_bptr = create_block(master, iln, iln,
1944 iln->n_passthroughcount + 1);
1945 n_bptr->type = BBTYPE_EXH;
1946 n_bptr->flags = BBFINISHED;
1948 exvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
1949 n_bptr->invars[iln->n_passthroughcount] = exvar;
1951 iln->handler_monitorexit = n_bptr;
1953 /* ACONST / ALOAD */
1955 n_ins = master->inlined_iinstr_cursor++;
1956 if (iln->m->flags & ACC_STATIC) {
1957 n_ins->opc = ICMD_ACONST;
1958 n_ins->sx.val.c.cls = iln->m->class;
1959 n_ins->flags.bits = INS_FLAG_CLASS;
1962 n_ins->opc = ICMD_ALOAD;
1963 n_ins->s1.varindex = iln->synclocal;
1964 assert(n_ins->s1.varindex != UNUSED);
1966 /* XXX could be PREALLOCed for builtin call */
1967 syncvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
1968 n_ins->dst.varindex = syncvar;
1973 bte = builtintable_get_internal(LOCK_monitor_exit);
1975 n_ins = master->inlined_iinstr_cursor++;
1976 n_ins->opc = ICMD_BUILTIN;
1977 n_ins->s1.argcount = 1 + iln->n_passthroughcount + 1;
1978 n_ins->sx.s23.s2.args = DMNEW(s4, n_ins->s1.argcount);
1979 n_ins->sx.s23.s2.args[0] = syncvar;
1980 for (i=0; i < iln->n_passthroughcount + 1; ++i) {
1981 n_ins->sx.s23.s2.args[1 + i] = n_bptr->invars[i];
1983 n_ins->sx.s23.s3.bte = bte;
1988 n_ins = master->inlined_iinstr_cursor++;
1989 n_ins->opc = ICMD_ATHROW;
1990 n_ins->flags.bits = 0;
1991 n_ins->s1.varindex = exvar;
1994 /* close basic block */
1996 close_block(iln, iln, n_bptr, iln->n_passthroughcount);
2002 /* second pass driver *********************************************************/
2004 static bool inline_transform(inline_node *iln, jitdata *jd)
2009 exception_entry *n_ext;
2010 exception_entry *prevext;
2014 #if defined(INLINE_VERIFY_RESULT)
2015 static int debug_verify_inlined_code = 1;
2017 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2018 static int debug_counter = 0;
2021 DOLOG( dump_inline_tree(iln, 0); );
2025 n_ins = DMNEW(instruction, iln->cumul_instructioncount);
2026 MZERO(n_ins, instruction, iln->cumul_instructioncount);
2027 iln->inlined_iinstr = n_ins;
2029 n_bb = DMNEW(basicblock, iln->cumul_basicblockcount);
2030 MZERO(n_bb, basicblock, iln->cumul_basicblockcount);
2031 iln->inlined_basicblocks = n_bb;
2033 iln->ctx->blockmap = DMNEW(inline_block_map, iln->cumul_blockmapcount);
2035 n_jd = jit_jitdata_new(iln->m);
2036 n_jd->flags = jd->flags;
2037 n_jd->code->optlevel = jd->code->optlevel;
2038 iln->ctx->resultjd = n_jd;
2042 /* create the local_map */
2044 n_jd->local_map = DMNEW(s4, 5*iln->cumul_maxlocals);
2045 for (i=0; i<5*iln->cumul_maxlocals; ++i)
2046 n_jd->local_map[i] = UNUSED;
2048 /* create / coalesce local variables */
2056 n_jd->localcount = n_jd->vartop;
2058 /* extra variables for verification (debugging) */
2060 #if defined(INLINE_VERIFY_RESULT)
2061 if (debug_verify_inlined_code) {
2062 n_jd->vartop += VERIFIER_EXTRA_LOCALS + VERIFIER_EXTRA_VARS + 100 /* XXX m->maxstack */;
2063 if (n_jd->vartop > n_jd->varcount) {
2065 n_jd->var = DMREALLOC(n_jd->var, varinfo, n_jd->varcount, n_jd->vartop);
2066 n_jd->varcount = n_jd->vartop;
2069 #endif /* defined(INLINE_VERIFY_RESULT) */
2071 /* write inlined code */
2073 inline_rewrite_method(iln);
2075 /* create exception handlers */
2077 inline_write_exception_handlers(iln, iln);
2079 /* write the dummy end block */
2081 n_bptr = create_block(iln, iln, iln, 0);
2082 n_bptr->flags = BBUNDEF;
2083 n_bptr->type = BBTYPE_STD;
2085 /* store created code in jitdata */
2087 n_jd->basicblocks = iln->inlined_basicblocks;
2088 n_jd->instructioncount = iln->cumul_instructioncount;
2089 n_jd->instructions = iln->inlined_iinstr;
2091 /* link the basic blocks (dummy end block is not counted) */
2093 n_jd->basicblockcount = (iln->inlined_basicblocks_cursor - iln->inlined_basicblocks) - 1;
2094 for (i=0; i<n_jd->basicblockcount + 1; ++i)
2095 n_jd->basicblocks[i].next = &(n_jd->basicblocks[i+1]);
2097 n_jd->basicblocks[i-1].next = NULL;
2099 /* check basicblock numbers */
2101 #if !defined(NDEBUG)
2102 jit_check_basicblock_numbers(n_jd);
2105 /* create the exception table */
2107 if (iln->cumul_exceptiontablelength) {
2108 exception_entry *tableend;
2110 n_ext = DMNEW(exception_entry, iln->cumul_exceptiontablelength);
2112 tableend = inline_exception_tables(iln, n_ext, &prevext);
2113 assert(tableend == n_ext + iln->cumul_exceptiontablelength);
2115 prevext->down = NULL;
2117 n_jd->exceptiontablelength = iln->cumul_exceptiontablelength;
2118 n_jd->exceptiontable = n_ext;
2124 /*******************************************************************************/
2127 memcpy(n_cd, jd->cd, sizeof(codegendata));
2129 n_cd->method = NULL; /* XXX */
2130 n_jd->maxlocals = iln->cumul_maxlocals;
2131 n_jd->maxinterfaces = iln->ctx->maxinoutdepth;
2133 inline_post_process(n_jd);
2135 inline_interface_variables(iln);
2137 /* for debugging, verify the inlined result */
2139 #if defined(INLINE_VERIFY_RESULT)
2140 if (debug_verify_inlined_code) {
2141 debug_verify_inlined_code = 0;
2142 DOLOG( printf("VERIFYING INLINED RESULT...\n"); fflush(stdout); );
2143 if (!typecheck(n_jd)) {
2144 *exceptionptr = NULL;
2145 DOLOG( printf("XXX INLINED RESULT DID NOT PASS VERIFIER XXX\n") );
2149 DOLOG( printf("VERIFICATION PASSED.\n") );
2151 debug_verify_inlined_code = 1;
2153 #endif /* defined(INLINE_VERIFY_RESULT) */
2155 /* we need bigger free memory stacks (XXX these should not be allocated in reg_setup) */
2157 n_jd->rd->freemem = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
2158 #if defined(HAS_4BYTE_STACKSLOT)
2159 n_jd->rd->freemem_2 = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
2162 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2163 if ( (n_jd->instructioncount >= opt_inline_debug_min_size)
2164 && (n_jd->instructioncount <= opt_inline_debug_max_size))
2166 if (debug_counter <= opt_inline_debug_end_counter)
2167 #endif /* defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG) */
2169 /* install the inlined result */
2171 *jd->code = *n_jd->code;
2172 n_jd->code = jd->code;
2175 /* statistics and logging */
2177 #if !defined(NDEBUG)
2178 inline_stat_roots++;
2181 printf("==== %d.INLINE ==================================================================\n",
2183 printf("\ninline tree:\n");
2184 dump_inline_tree(iln, 0);
2185 n_jd->flags |= JITDATA_FLAG_SHOWINTERMEDIATE | JITDATA_FLAG_SHOWDISASSEMBLE;
2186 /* debug_dump_inlined_code(iln, n_method, n_cd, n_rd); */
2187 printf("-------- DONE -----------------------------------------------------------\n");
2193 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2201 /******************************************************************************/
2202 /* FIRST PASS: build inlining tree */
2203 /******************************************************************************/
2206 /* inline_pre_parse_heuristics *************************************************
2208 Perform heuristic checks whether a call site should be inlined.
2209 These checks are evaluated before the callee has been parsed and analysed.
2212 caller...........inlining node of the caller
2213 callee...........the called method
2214 site.............information on the call site
2217 true........consider for inlining
2218 false.......don't inline
2220 *******************************************************************************/
2222 static bool inline_pre_parse_heuristics(const inline_node *caller,
2223 const methodinfo *callee,
2226 #if defined(INLINE_MAX_DEPTH)
2227 if (caller->depth >= INLINE_MAX_DEPTH)
2235 /* inline_post_parse_heuristics ************************************************
2237 Perform heuristic checks whether a call site should be inlined.
2238 These checks are evaluated after the callee has been parsed and analysed.
2241 caller...........inlining node of the caller (const)
2242 callee...........the called method (const)
2245 true........consider for inlining
2246 false.......don't inline
2248 *******************************************************************************/
2250 static bool inline_post_parse_heuristics(const inline_node *caller,
2251 const inline_node *callee)
2257 /* inline_afterwards_heuristics ************************************************
2259 Perform heuristic checks whether a call site should be inlined.
2260 These checks are evaluated after the inlining plan for the callee has
2264 caller...........inlining node of the caller (const)
2265 callee...........the called method (const)
2268 true........consider for inlining
2269 false.......don't inline
2271 *******************************************************************************/
2273 static bool inline_afterwards_heuristics(const inline_node *caller,
2274 const inline_node *callee)
2276 inline_node *cumulator;
2278 #if defined(INLINE_DEPTH_FIRST)
2281 cumulator = caller->ctx->master;
2285 #if defined(INLINE_MAX_BLOCK_EXPANSION)
2286 || (cumulator->cumul_basicblockcount + callee->cumul_basicblockcount
2287 > INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
2289 #if defined(INLINE_MAX_ICMD_EXPANSION)
2290 || (cumulator->cumul_instructioncount + callee->cumul_instructioncount
2291 > INLINE_MAX_ICMD_EXPANSION*caller->ctx->master->jd->instructioncount)
2302 /* inline_is_monomorphic *******************************************************
2304 Check if the given call site can be proven to be monomorphic.
2307 callee...........the called method
2308 call.............the invocation instruction
2311 site->speculative.....flags whether the inlining is speculative
2312 (only defined if return value is true)
2315 true if the call site is (currently) monomorphic,
2316 false if not or unknown
2318 *******************************************************************************/
2320 static bool inline_is_monomorphic(const methodinfo *callee,
2321 const instruction *call,
2324 if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)
2325 || call->opc == ICMD_INVOKESPECIAL))
2327 site->speculative = false;
2331 /* XXX search single implementation for abstract monomorphics */
2333 if ((callee->flags & (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED
2335 == (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED))
2338 DOLOG( printf("SPECULATIVE INLINE: "); method_println((methodinfo*)callee); );
2339 site->speculative = true;
2345 /* possibly polymorphic call site */
2351 /* inline_can_inline ***********************************************************
2353 Check if inlining of the given call site is possible.
2356 caller...........inlining node of the caller
2357 callee...........the called method
2358 call.............the invocation instruction
2361 site->speculative.....flags whether the inlining is speculative
2362 (only defined if return value is true)
2365 true if inlining is possible, false if not
2367 *******************************************************************************/
2369 static bool inline_can_inline(const inline_node *caller,
2370 const methodinfo *callee,
2371 const instruction *call,
2374 const inline_node *active;
2376 /* cannot inline native methods */
2378 if (callee->flags & ACC_NATIVE)
2381 /* cannot inline possibly polymorphic calls */
2383 if (!inline_is_monomorphic(callee, call, site))
2386 /* cannot inline recursive calls */
2388 for (active = caller; active; active = active->parent) {
2389 if (callee == active->m) {
2390 DOLOG( printf("RECURSIVE!\n") );
2395 /* inlining is possible */
2401 /* inline_create_callee_node ***************************************************
2403 Create an inlining node for the given callee.
2406 caller...........inlining node of the caller (const)
2407 callee...........the called method
2410 the new inlining node
2412 *******************************************************************************/
2414 static inline_node * inline_create_callee_node(const inline_node *caller,
2417 inline_node *cn; /* the callee inline_node */
2419 cn = DNEW(inline_node);
2420 MZERO(cn, inline_node, 1);
2422 cn->depth = caller->depth + 1;
2423 cn->ctx = caller->ctx;
2425 cn->synchronize = (callee->flags & ACC_SYNCHRONIZED);
2426 cn->isstatic = (callee->flags & ACC_STATIC);
2432 /* inline_set_callee_properties ************************************************
2434 Set properties of the inlined call site.
2437 caller...........inlining node of the caller (const)
2438 cn...............the called method
2439 site.............info about the call site (const)
2442 *cn..............has the properties set
2444 *******************************************************************************/
2446 static void inline_set_callee_properties(const inline_node *caller,
2448 const inline_site *site)
2454 /* set info about the call site */
2456 cn->callerblock = site->bptr;
2457 cn->callerins = site->iptr;
2458 cn->callerpc = site->pc;
2459 cn->o_handlers = site->handlers;
2460 cn->n_handlercount = caller->n_handlercount + site->nhandlers;
2462 /* determine if we need basic block boundaries before/after */
2464 cn->blockbefore = false;
2465 cn->blockafter = false;
2467 if (cn->jd->branchtoentry)
2468 cn->blockbefore = true;
2470 if (cn->jd->branchtoend)
2471 cn->blockafter = true;
2473 if (cn->jd->returncount > 1)
2474 cn->blockafter = true;
2476 /* XXX make safer and reusable (maybe store last real block) */
2477 for (bptr = cn->jd->basicblocks; bptr && bptr->next && bptr->next->next; bptr = bptr->next)
2480 if (cn->jd->returnblock != bptr)
2481 cn->blockafter = true;
2483 /* info about the callee */
2485 cn->localsoffset = caller->localsoffset + caller->m->maxlocals;
2486 cn->prolog_instructioncount = cn->m->parseddesc->paramcount + 2;
2487 cn->epilog_instructioncount = 1; /* INLINE_END */
2488 cn->extra_instructioncount = 0;
2490 /* we need a CHECKNULL for instance methods, except for <init> */
2492 if (!cn->isstatic && cn->m->name != utf_init)
2493 cn->prolog_instructioncount += 1;
2495 /* deal with synchronized callees */
2497 if (cn->synchronize) {
2499 builtintable_entry *bte;
2501 /* we need basic block boundaries because of the handler */
2503 cn->blockbefore = true;
2504 cn->blockafter = true;
2506 /* for synchronized static methods */
2507 /* we need an ACONST, MONITORENTER in the prolog */
2508 /* and ACONST, MONITOREXIT in the epilog */
2510 /* for synchronized instance methods */
2511 /* we need an COPY, MONITORENTER in the prolog */
2512 /* and MONITOREXIT in the epilog */
2515 cn->prolog_instructioncount += 2;
2516 cn->epilog_instructioncount += 2;
2519 cn->prolog_instructioncount += 2;
2520 cn->epilog_instructioncount += 1;
2521 cn->localsoffset += 1;
2524 /* and exception handler */
2525 /* ALOAD, builtin_monitorexit, ATHROW */
2527 cn->extra_instructioncount += 3;
2529 /* exception table entries */
2531 cn->extra_exceptiontablelength = 1 + cn->n_handlercount;
2533 /* add exception handler block */
2535 cn->cumul_basicblockcount_root++;
2537 /* we must call the builtins */
2539 bte = builtintable_get_internal(LOCK_monitor_enter);
2541 if (md->memuse > cn->regdata->memuse)
2542 cn->regdata->memuse = md->memuse;
2543 if (md->argintreguse > cn->regdata->argintreguse)
2544 cn->regdata->argintreguse = md->argintreguse;
2546 bte = builtintable_get_internal(LOCK_monitor_exit);
2548 if (md->memuse > cn->regdata->memuse)
2549 cn->regdata->memuse = md->memuse;
2550 if (md->argintreguse > cn->regdata->argintreguse)
2551 cn->regdata->argintreguse = md->argintreguse;
2554 /* determine pass-through variables */
2556 i = site->iptr->s1.argcount - cn->m->parseddesc->paramcount; /* max # of pass-though vars */
2558 cn->n_passthroughvars = DMNEW(s4, i);
2560 for (argi = site->iptr->s1.argcount - 1; argi >= cn->m->parseddesc->paramcount; --argi) {
2561 s4 idx = site->iptr->sx.s23.s2.args[argi];
2562 if (idx >= caller->jd->localcount) {
2563 cn->n_passthroughvars[j] = idx;
2567 DOLOG( printf("PASSING THROUGH LOCAL VARIABLE %d\n", idx); );
2571 cn->n_selfpassthroughcount = j;
2572 cn->n_passthroughcount = caller->n_passthroughcount + cn->n_selfpassthroughcount;
2576 /* inline_cumulate_counters ****************************************************
2578 Cumulate counters after a node has been decided to become inlined.
2581 caller...........inlining node of the caller
2582 callee...........inlining node of the callee (const)
2585 *caller..........gets cumulated values added
2587 *******************************************************************************/
2589 static void inline_cumulate_counters(inline_node *caller,
2590 const inline_node *cn)
2592 caller->cumul_instructioncount += cn->prolog_instructioncount;
2593 caller->cumul_instructioncount += cn->epilog_instructioncount;
2594 caller->cumul_instructioncount += cn->extra_instructioncount;
2595 caller->cumul_instructioncount += cn->cumul_instructioncount - 1 /*invoke*/;
2597 caller->cumul_basicblockcount += cn->cumul_basicblockcount;
2598 caller->cumul_basicblockcount_root += cn->cumul_basicblockcount_root;
2599 caller->cumul_blockmapcount += cn->cumul_blockmapcount;
2600 caller->cumul_exceptiontablelength += cn->cumul_exceptiontablelength;
2601 caller->cumul_exceptiontablelength += cn->extra_exceptiontablelength;
2603 if (cn->cumul_maxlocals > caller->cumul_maxlocals)
2604 caller->cumul_maxlocals = cn->cumul_maxlocals;
2606 /* XXX extra block after inlined call */
2607 if (cn->blockafter) {
2608 caller->cumul_basicblockcount += 1;
2609 caller->cumul_blockmapcount += 1;
2614 /* inline_analyse_callee *******************************************************
2616 Analyse an inlining candidate callee.
2619 caller...........inlining node of the caller
2620 callee...........the called method
2621 site.............info about the call site
2624 site->inlined....true if the callee has been selected for inlining
2627 the inline node of the callee, or
2628 NULL if an error has occurred (don't use the inlining plan in this case)
2630 *******************************************************************************/
2632 static inline_node * inline_analyse_callee(inline_node *caller,
2636 inline_node *cn; /* the callee inline_node */
2638 /* create an inline tree node */
2640 cn = inline_create_callee_node(caller, callee);
2642 /* get the intermediate representation of the callee */
2644 if (!inline_jit_compile(cn))
2647 /* evaluate heuristics after parsing the callee */
2649 if (!inline_post_parse_heuristics(caller, cn))
2652 /* the call site will be inlined */
2654 site->inlined = true;
2656 /* set info about the call site */
2658 inline_set_callee_properties(caller, cn, site);
2660 /* insert the node into the inline tree */
2662 inline_insert_inline_node(caller, cn);
2664 /* analyse recursively */
2666 if (!inline_analyse_code(cn))
2669 if (!inline_afterwards_heuristics(caller, cn)) {
2670 #if defined(INLINE_CANCEL_ON_THRESHOLD)
2673 inline_remove_inline_node(caller, cn);
2674 caller->ctx->stopped = true;
2675 site->inlined = false;
2680 /* cumulate counters */
2682 #if defined(INLINE_DEPTH_FIRST)
2683 inline_cumulate_counters(caller, cn);
2686 #if defined(INLINE_BREADTH_FIRST)
2688 inline_cumulate_counters(caller, cn);
2689 caller = caller->parent;
2697 /* inline_process_candidate ****************************************************
2699 Process a selected inlining candidate.
2702 cand.............the candidate
2705 true........everything ok
2706 false.......an error has occurred, don't use the plan
2708 *******************************************************************************/
2710 static bool inline_process_candidate(inline_candidate *cand)
2714 cn = inline_analyse_callee(cand->caller,
2721 if (!cand->site.inlined)
2724 /* store assumptions */
2726 if (cand->site.speculative)
2727 method_add_assumption_monomorphic(cand->callee, cand->caller->ctx->master->m);
2733 /* inline_analyse_code *********************************************************
2735 Analyse the intermediate code of the given inlining node.
2738 iln..............the inlining node
2741 *iln.............the inlining plan
2744 true........everything ok
2745 false.......an error has occurred, don't use the plan
2747 *******************************************************************************/
2749 static bool inline_analyse_code(inline_node *iln)
2756 exception_entry **handlers;
2757 exception_entry *ex;
2768 /* initialize cumulative counters */
2770 iln->cumul_maxlocals = iln->localsoffset + m->maxlocals;
2771 iln->cumul_exceptiontablelength += mjd->exceptiontablelength;
2773 /* iterate over basic blocks */
2777 for (bptr = mjd->basicblocks; bptr; bptr = bptr->next) {
2779 /* count the block */
2780 /* ignore dummy end blocks (but count them for the blockmap) */
2782 iln->cumul_blockmapcount++;
2783 if ((bptr != mjd->basicblocks || iln->blockbefore)
2785 (bptr->icount > 0 || bptr->next != NULL))
2786 iln->cumul_basicblockcount++;
2788 /* skip dead code */
2790 if (bptr->flags < BBREACHED)
2793 /* allocate the buffer of active exception handlers */
2794 /* XXX this wastes some memory, but probably it does not matter */
2796 handlers = DMNEW(exception_entry*, mjd->exceptiontablelength + 1);
2798 /* determine the active exception handlers for this block */
2799 /* XXX maybe the handlers of a block should be part of our IR */
2800 /* XXX this should share code with the type checkers */
2802 for (ex = mjd->exceptiontable; ex ; ex = ex->down) {
2803 if ((ex->start->nr <= bptr->nr) && (ex->end->nr > bptr->nr)) {
2804 handlers[nhandlers++] = ex;
2807 handlers[nhandlers] = NULL;
2810 iptr = bptr->iinstr;
2813 iln->cumul_instructioncount += len;
2815 /* iterate over the instructions of the block */
2817 for (; --len >= 0; ++iptr) {
2819 switch (iptr->opc) {
2820 case ICMD_INVOKEVIRTUAL:
2821 case ICMD_INVOKESPECIAL:
2822 case ICMD_INVOKESTATIC:
2823 case ICMD_INVOKEINTERFACE:
2825 if (!INSTRUCTION_IS_UNRESOLVED(iptr) && !iln->ctx->stopped) {
2826 callee = iptr->sx.s23.s3.fmiref->p.method;
2828 if (inline_can_inline(iln, callee, iptr, &site)) {
2829 site.inlined = false;
2832 site.pc = blockendpc - len - 1;
2833 site.handlers = handlers;
2834 site.nhandlers = nhandlers;
2836 if (inline_pre_parse_heuristics(iln, callee, &site)) {
2837 #if defined(INLINE_KNAPSACK) || defined(INLINE_BREADTH_FIRST)
2838 inline_add_candidate(iln->ctx, iln, callee, &site);
2840 inline_candidate cand;
2842 cand.callee = callee;
2845 if (!inline_process_candidate(&cand))
2859 /* extra ICMD_MOVE may be necessary */
2860 iln->cumul_instructioncount++;
2865 /* end of basic block */
2872 static void inline_cumulate_counters_recursive(inline_node *iln)
2876 child = iln->children;
2879 inline_cumulate_counters_recursive(child);
2880 inline_cumulate_counters(iln, child);
2881 child = child->next;
2882 } while (child != iln->children);
2887 /* inline_make_inlining_plan ***************************************************
2889 Make an inlining plan for the given root node
2892 iln..............the root node
2895 *iln.............the inlining plan
2898 true........everything ok
2899 false.......an error has occurred, don't use the plan
2901 *******************************************************************************/
2903 #if defined(INLINE_KNAPSACK)
2904 static bool inline_make_inlining_plan(inline_node *iln)
2906 inline_candidate *cand;
2907 #if defined(INLINE_COST_BUDGET)
2908 s4 budget = INLINE_COST_BUDGET;
2909 # define BUDGETMEMBER cost
2911 #if defined(INLINE_WEIGHT_BUDGET)
2912 double budget = INLINE_WEIGHT_BUDGET;
2913 # define BUDGETMEMBER weight
2916 inline_analyse_code(iln);
2918 DOLOG( printf("candidates in "); method_println(iln->m);
2919 inline_candidates_println(iln->ctx); );
2921 while ((cand = inline_pick_best_candidate(iln->ctx)) != NULL)
2923 if (cand->BUDGETMEMBER <= budget) {
2924 DOLOG( printf(" picking: "); inline_candidate_println(cand); );
2926 if (!inline_process_candidate(cand))
2929 #if !defined(INLINE_ADD_NEGATIVE_TO_BUDGET)
2930 if (cand->BUDGETMEMBER > 0)
2932 budget -= cand->BUDGETMEMBER;
2936 inline_cumulate_counters_recursive(iln);
2940 #endif /* defined(INLINE_KNAPSACK) */
2943 #if defined(INLINE_DEPTH_FIRST)
2944 static bool inline_make_inlining_plan(inline_node *iln)
2946 return inline_analyse_code(iln);
2948 #endif /* defined(INLINE_DEPTH_FIRST) */
2951 #if defined(INLINE_BREADTH_FIRST)
2952 static bool inline_make_inlining_plan(inline_node *iln)
2954 inline_candidate *cand;
2956 inline_analyse_code(iln);
2958 DOLOG( printf("candidates in "); method_println(iln->m);
2959 inline_candidates_println(iln->ctx); );
2961 while (!iln->ctx->stopped
2962 && (cand = inline_pick_best_candidate(iln->ctx)) != NULL)
2964 DOLOG( printf(" picking: "); inline_candidate_println(cand); );
2966 if (!inline_process_candidate(cand))
2972 #endif /* defined(INLINE_BREADTH_FIRST) */
2975 /* statistics *****************************************************************/
2977 #if defined(INLINE_STATISTICS)
2978 static void inline_gather_statistics_recursive(inline_node *iln)
2982 inline_stat_inlined_nodes++;
2984 if (iln->depth > inline_stat_max_depth)
2985 inline_stat_max_depth++;
2987 child = iln->children;
2990 inline_gather_statistics_recursive(child);
2991 child = child->next;
2992 } while (child != iln->children);
2995 #endif /* defined(INLINE_STATISTICS) */
2998 #if defined(INLINE_STATISTICS)
2999 static void inline_gather_statistics(inline_node *iln)
3001 inline_stat_roots_transformed++;
3003 inline_gather_statistics_recursive(iln);
3005 #endif /* defined(INLINE_STATISTICS) */
3008 /* post processing ************************************************************/
3010 #define POSTPROCESS_SRC(varindex) live[varindex]--
3011 #define POSTPROCESS_DST(varindex) live[varindex]++
3013 #define POSTPROCESS_SRCOP(s) POSTPROCESS_SRC(iptr->s.varindex)
3014 #define POSTPROCESS_DSTOP(d) POSTPROCESS_DST(iptr->d.varindex)
3016 #define MARKSAVED(varindex) jd->var[varindex].flags |= SAVEDVAR
3018 #define MARK_ALL_SAVED \
3020 for (i=0; i<jd->vartop; ++i) \
3025 static void inline_post_process(jitdata *jd)
3031 icmdtable_entry_t *icmdt;
3034 builtintable_entry *bte;
3036 /* reset the SAVEDVAR flag of all variables */
3038 for (i=0; i<jd->vartop; ++i)
3039 jd->var[i].flags &= ~SAVEDVAR;
3041 /* allocate the life counters */
3043 live = DMNEW(s4, jd->vartop);
3044 MZERO(live, s4, jd->vartop);
3046 /* iterate over all basic blocks */
3048 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
3049 if (bptr->flags < BBREACHED)
3052 /* make invars live */
3054 for (i=0; i<bptr->indepth; ++i)
3055 POSTPROCESS_DST(bptr->invars[i]);
3057 iptr = bptr->iinstr;
3058 iend = iptr + bptr->icount;
3060 for (; iptr < iend; ++iptr) {
3062 icmdt = &(icmd_table[iptr->opc]);
3064 switch (icmdt->dataflow) {
3066 POSTPROCESS_SRCOP(sx.s23.s3);
3068 POSTPROCESS_SRCOP(sx.s23.s2);
3070 POSTPROCESS_SRCOP(s1);
3072 if (icmdt->flags & ICMDTABLE_CALLS) {
3073 jd->isleafmethod = false;
3079 POSTPROCESS_SRCOP(sx.s23.s2);
3082 POSTPROCESS_SRCOP(s1);
3084 if (icmdt->flags & ICMDTABLE_CALLS) {
3085 jd->isleafmethod = false;
3089 POSTPROCESS_DSTOP(dst);
3093 for (i=0; i<iptr->s1.argcount; ++i) {
3094 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3096 if (icmdt->flags & ICMDTABLE_CALLS) {
3097 jd->isleafmethod = false;
3100 POSTPROCESS_DSTOP(dst);
3104 INSTRUCTION_GET_METHODDESC(iptr, md);
3106 jd->isleafmethod = false;
3107 for (i=0; i<md->paramcount; ++i) {
3108 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3110 for (; i<iptr->s1.argcount; ++i) {
3111 MARKSAVED(iptr->sx.s23.s2.args[i]);
3113 if (md->returntype.type != TYPE_VOID)
3114 POSTPROCESS_DSTOP(dst);
3118 bte = iptr->sx.s23.s3.bte;
3120 goto post_process_call;
3126 } /* end instruction loop */
3128 /* consume outvars */
3130 for (i=0; i<bptr->outdepth; ++i)
3131 POSTPROCESS_SRC(bptr->outvars[i]);
3133 #if !defined(NDEBUG)
3134 for (i=jd->localcount; i < jd->vartop; ++i)
3135 assert(live[i] == 0);
3138 } /* end basic block loop */
3142 /* inline_create_root_node *****************************************************
3144 Create the root node of the inlining tree.
3147 jd...............the current jitdata of the root method
3150 the root node of the inlining tree
3152 *******************************************************************************/
3154 static inline_node * inline_create_root_node(jitdata *jd)
3158 iln = DNEW(inline_node);
3159 MZERO(iln, inline_node, 1);
3163 iln->regdata = jd->rd;
3165 iln->blockbefore = true;
3166 iln->blockafter = true;
3168 iln->cumul_instructioncount = 0;
3169 iln->cumul_basicblockcount = 1 /* dummy end block */;
3171 /* create inlining context */
3173 iln->ctx = DNEW(inline_context);
3174 MZERO(iln->ctx, inline_context, 1);
3175 iln->ctx->master = iln;
3176 iln->ctx->next_debugnr = 1; /* XXX debug */
3182 /******************************************************************************/
3183 /* MAIN DRIVER FUNCTION */
3184 /******************************************************************************/
3186 bool inline_inline(jitdata *jd)
3190 DOLOG( printf("==== INLINE ==================================================================\n");
3191 show_method(jd, SHOW_STACK); );
3193 #if defined(INLINE_STATISTICS)
3194 inline_stat_roots++;
3197 iln = inline_create_root_node(jd);
3199 if (inline_make_inlining_plan(iln)) {
3201 /* add blocks to the root node */
3203 iln->cumul_basicblockcount += iln->cumul_basicblockcount_root;
3204 iln->cumul_blockmapcount += iln->cumul_basicblockcount_root;
3206 DOLOG( printf("==== INLINE TRANSFORM ========================================================\n"); );
3209 inline_transform(iln, jd);
3211 #if defined(INLINE_STATISTICS)
3212 inline_gather_statistics(iln);
3216 DOLOG( printf("-------- DONE -----------------------------------------------------------\n");
3223 * These are local overrides for various environment variables in Emacs.
3224 * Please do not remove this and leave it at the end of the file, where
3225 * Emacs will automagically detect them.
3226 * ---------------------------------------------------------------------
3229 * indent-tabs-mode: t
3233 * vim:noexpandtab:sw=4:ts=4: