1 /* src/vm/jit/inline/inline.c - method inlining
3 Copyright (C) 1996-2005, 2006 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
25 Contact: cacao@cacaojvm.org
27 Authors: Edwin Steiner
31 $Id: inline.c 7228 2007-01-19 01:13:48Z edwin $
44 #include "mm/memory.h"
45 #include "toolbox/logging.h"
46 #include "vm/builtin.h"
47 #include "vm/global.h"
48 #include "vm/options.h"
49 #include "vm/statistics.h"
50 #include "vm/jit/jit.h"
51 #include "vm/jit/parse.h"
52 #include "vm/jit/inline/inline.h"
53 #include "vm/jit/loop/loop.h"
56 #include "vm/initialize.h"
57 #include "vm/method.h"
58 #include "vm/jit/jit.h"
59 #include "vm/jit/show.h"
61 #include "vm/jit/reg.h"
62 #include "vm/jit/stack.h"
64 #include "vm/jit/verify/typecheck.h"
66 #if defined(ENABLE_THREADS)
67 # include "threads/native/threads.h"
71 /* algorithm tuning constants *************************************************/
73 #define INLINE_KNAPSACK
75 #if defined(INLINE_KNAPSACK)
77 #define INLINE_COUNTDOWN_INIT 1000
78 #define INLINE_COST_OFFSET -16
79 #define INLINE_COST_BUDGET 100
80 /*#define INLINE_WEIGHT_BUDGET 5.0*/
81 /*#define INLINE_ADD_NEGATIVE_TO_BUDGET*/
82 /*#define INLINE_MAX_DEPTH 3*/
83 /*#define INLINE_DIVIDE_COST_BY_FREQ */
87 #define INLINE_MAX_DEPTH 3
88 #define INLINE_MAX_BLOCK_EXPANSION 10
89 /*#define INLINE_MAX_ICMD_EXPANSION 10*/
90 /*#define INLINE_CANCEL_ON_THRESHOLD*/
95 /* debugging ******************************************************************/
98 #define INLINE_VERBOSE
99 #define DOLOG(code) do{ if (opt_inline_debug_log) { code; } }while(0)
104 #if defined(ENABLE_VERIFIER) && !defined(NDEBUG)
105 /* Define this to verify the resulting code after inlining. */
106 /* Note: This is only useful for development and may require patches to the */
108 /* #define INLINE_VERIFY_RESULT */
112 /* types **********************************************************************/
114 typedef struct inline_node inline_node;
115 typedef struct inline_target_ref inline_target_ref;
116 typedef struct inline_context inline_context;
117 typedef struct inline_block_map inline_block_map;
118 typedef struct inline_site inline_site;
119 typedef struct inline_candidate inline_candidate;
126 inline_node *children;
127 inline_node *next; /* next node at this depth */
128 inline_node *prev; /* prev node at this depth */
129 int depth; /* inlining depth, 0 for root */
131 /* info about the call site (if depth > 0)*/
132 inline_node *parent; /* node of the caller (NULL for root) */
133 basicblock *callerblock; /* original block containing the INVOKE* */
134 instruction *callerins; /* the original INVOKE* instruction */
136 s4 *n_passthroughvars;
137 int n_passthroughcount;
138 int n_selfpassthroughcount; /* # of pass-through vars of the call itself */
139 exception_entry **o_handlers;
140 int n_handlercount; /* # of handlers protecting this call */
142 int synclocal; /* variable used for synchr., or UNUSED */
143 bool isstatic; /* this is a static call */
145 bool blockbefore; /* block boundary before inlined body? */
146 bool blockafter; /* block boundary after inlined body? */
148 /* info about the callee */
150 int prolog_instructioncount; /* # of ICMDs in the inlining prolog */
151 int epilog_instructioncount; /* # of ICMDs in the inlining epilog */
152 int extra_instructioncount;
153 int extra_exceptiontablelength; /* # of extra handlers to put in caller */
154 bool synchronize; /* do we have to synchronize enter/exit? */
155 basicblock *handler_monitorexit; /* handler for synchronized inlinees */
158 /* cumulative values */
159 int cumul_instructioncount; /* ICMDs in this node and its children */
160 int cumul_basicblockcount; /* BBs started by this node and its children */
161 int cumul_basicblockcount_root; /* BBs that have to be added to the root */
162 /* node if this node is inlined */
163 int cumul_blockmapcount;
165 int cumul_exceptiontablelength;
168 instruction *inlined_iinstr;
169 instruction *inlined_iinstr_cursor;
170 basicblock *inlined_basicblocks;
171 basicblock *inlined_basicblocks_cursor;
174 registerdata *regdata;
177 inline_target_ref *refs;
178 instruction *inline_start_instruction;
186 struct inline_target_ref {
187 inline_target_ref *next;
196 struct inline_block_map {
202 struct inline_context {
207 inline_candidate *candidates;
209 int next_block_number;
210 inline_block_map *blockmap;
217 int next_debugnr; /* XXX debug */
221 bool speculative; /* true, if inlining would be speculative */
222 bool inlined; /* true, if this site has been inlined */
224 basicblock *bptr; /* basic block containing the call site */
225 instruction *iptr; /* the invocation instruction */
226 exception_entry **handlers; /* active handlers at the call site */
227 s4 nhandlers; /* number of active handlers */
228 s4 pc; /* PC of the invocation instruction */
231 struct inline_candidate {
232 inline_candidate *next;
242 /* prototypes *****************************************************************/
244 static bool inline_analyse_code(inline_node *iln);
245 static void inline_post_process(jitdata *jd);
248 /* debug helpers **************************************************************/
251 #include "inline_debug.inc"
255 /* statistics *****************************************************************/
257 /*#define INLINE_STATISTICS*/
260 #define INLINE_STATISTICS
263 #if defined(INLINE_STATISTICS)
264 int inline_stat_roots = 0;
265 int inline_stat_roots_transformed = 0;
266 int inline_stat_inlined_nodes = 0;
267 int inline_stat_max_depth = 0;
269 void inline_print_stats()
271 printf("inlining statistics:\n");
272 printf(" roots analysed : %d\n", inline_stat_roots);
273 printf(" roots transformed: %d\n", inline_stat_roots_transformed);
274 printf(" inlined nodes : %d\n", inline_stat_inlined_nodes);
275 printf(" max depth : %d\n", inline_stat_max_depth);
280 /* compilation of callees *****************************************************/
282 static bool inline_jit_compile_intern(jitdata *jd)
286 /* XXX should share code with jit.c */
290 /* XXX initialize the static function's class */
294 /* call the compiler passes ***********************************************/
296 /* call parse pass */
298 DOLOG( log_message_class("Parsing ", m->class) );
303 /* call stack analysis pass */
305 if (!stack_analyse(jd)) {
313 static bool inline_jit_compile(inline_node *iln)
319 /* XXX should share code with jit.c */
325 #if defined(ENABLE_THREADS)
326 /* enter a monitor on the method */
327 lock_monitor_enter((java_objectheader *) m);
330 /* allocate jitdata structure and fill it */
332 jd = jit_jitdata_new(m);
335 jd->flags = 0; /* XXX */
337 /* initialize the register allocator */
341 /* setup the codegendata memory */
343 /* XXX do a pseudo setup */
344 jd->cd = DNEW(codegendata);
345 MZERO(jd->cd, codegendata, 1);
346 jd->cd->maxstack = m->maxstack;
348 /* XXX uses too much dump memory codegen_setup(jd); */
350 /* now call internal compile function */
352 r = inline_jit_compile_intern(jd);
355 iln->regdata = jd->rd;
358 /* free some memory */
361 #if defined(ENABLE_JIT)
362 # if defined(ENABLE_INTRP)
370 #if defined(ENABLE_THREADS)
371 /* leave the monitor */
372 lock_monitor_exit((java_objectheader *) m );
379 /* inlining tree handling *****************************************************/
381 static void inline_insert_inline_node(inline_node *parent, inline_node *child)
386 assert(parent && child);
388 child->parent = parent;
390 child->debugnr = parent->ctx->next_debugnr++; /* XXX debug */
392 first = parent->children;
394 /* insert as only node */
395 parent->children = child;
401 /* {there is at least one child already there} */
403 /* XXX is this search necessary, or could we always add at the end? */
406 while (succ->callerpc < child->callerpc) {
409 /* insert as last node */
410 child->prev = first->prev;
412 child->prev->next = child;
413 child->next->prev = child;
418 assert(succ->callerpc > child->callerpc);
420 /* insert before succ */
422 child->prev = succ->prev;
424 child->prev->next = child;
425 child->next->prev = child;
427 if (parent->children == succ)
428 parent->children = child;
432 static void inline_remove_inline_node(inline_node *parent, inline_node *child)
436 assert(child->parent == parent);
438 if (child->prev == child) {
439 /* remove the only child node */
440 parent->children = NULL;
443 child->prev->next = child->next;
444 child->next->prev = child->prev;
446 if (parent->children == child)
447 parent->children = child->next;
452 /* inlining candidate handling ************************************************/
454 #if defined(INLINE_KNAPSACK)
455 static void inline_add_candidate(inline_context *ctx,
460 inline_candidate **link;
461 inline_candidate *cand;
463 cand = DNEW(inline_candidate);
464 #if defined(INLINE_DIVIDE_COST_BY_FREQ)
465 cand->freq = INLINE_COUNTDOWN_INIT - callee->hitcountdown;
469 cand->cost = callee->jcodelength + INLINE_COST_OFFSET;
470 cand->caller = caller;
471 cand->callee = callee;
474 cand->weight = (double)cand->cost / cand->freq;
476 for (link = &(ctx->candidates); ; link = &((*link)->next)) {
477 if (!*link || (*link)->weight > cand->weight) {
484 #endif /* defined(INLINE_KNAPSACK) */
486 #if defined(INLINE_KNAPSACK)
487 static inline_candidate * inline_pick_best_candidate(inline_context *ctx)
489 inline_candidate *cand;
491 cand = ctx->candidates;
494 ctx->candidates = cand->next;
498 #endif /* defined(INLINE_KNAPSACK) */
500 #if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
501 static void inline_candidate_println(inline_candidate *cand)
503 printf("%10g (%5d / %5d) depth %2d ",
504 cand->weight, cand->cost, cand->freq, cand->caller->depth + 1);
505 method_println(cand->callee);
507 #endif /* !defined(NDEBUG) && defined(INLINE_KNAPSACK) */
510 #if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
511 static void inline_candidates_println(inline_context *ctx)
513 inline_candidate *cand;
515 for (cand = ctx->candidates; cand != NULL; cand = cand->next) {
517 inline_candidate_println(cand);
520 #endif /* !defined(NDEBUG) && defined(INLINE_KNAPSACK) */
523 /* variable handling **********************************************************/
525 static s4 inline_new_variable(jitdata *jd, s4 type, s4 flags)
530 index = jd->vartop++;
531 if (index >= jd->varcount) {
532 newcount = jd->vartop * 2; /* XXX */
533 jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, newcount);
534 MZERO(jd->var + jd->varcount, varinfo, (newcount - jd->varcount));
535 jd->varcount = newcount;
538 jd->var[index].type = type;
539 jd->var[index].flags = flags;
545 static s4 inline_new_variable_clone(jitdata *jd, jitdata *origjd, s4 origidx)
550 v = &(origjd->var[origidx]);
552 newidx = inline_new_variable(jd, v->type, v->flags);
554 jd->var[newidx].vv = v->vv;
560 static s4 inline_new_temp_variable(jitdata *jd, s4 type)
562 return inline_new_variable(jd, type, 0);
566 static s4 inline_translate_variable(jitdata *jd, jitdata *origjd, s4 *varmap, s4 index)
573 idx = inline_new_variable_clone(jd, origjd, index);
581 static s4 *create_variable_map(inline_node *callee)
590 /* create the variable mapping */
592 varmap = DMNEW(s4, callee->jd->varcount);
593 for (i=0; i<callee->jd->varcount; ++i)
596 /* translate local variables */
598 for (i=0; i<callee->m->maxlocals; ++i) {
599 for (t=0; t<5; ++t) {
600 idx = callee->jd->local_map[5*i + t];
604 v = &(callee->jd->var[idx]);
605 assert(v->type == t || v->type == TYPE_VOID); /* XXX stack leaves VOID */
606 v->type = t; /* XXX restore if it is TYPE_VOID */
608 avail = callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t];
610 if (avail == UNUSED) {
611 avail = inline_new_variable_clone(callee->ctx->resultjd, callee->jd, idx);
612 callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t] = avail;
619 /* for synchronized instance methods we need an extra local */
621 if (callee->synchronize && !(callee->m->flags & ACC_STATIC)) {
622 n_idx = callee->localsoffset - 1;
624 assert(callee->parent);
625 assert(n_idx == callee->parent->localsoffset + callee->parent->m->maxlocals);
627 avail = callee->ctx->resultjd->local_map[5*n_idx + TYPE_ADR];
629 if (avail == UNUSED) {
630 avail = inline_new_variable(callee->ctx->resultjd, TYPE_ADR, 0);
631 callee->ctx->resultjd->local_map[5*n_idx + TYPE_ADR] = avail;
634 callee->synclocal = avail;
637 callee->synclocal = UNUSED;
644 /* basic block translation ****************************************************/
646 #define INLINE_RETURN_REFERENCE(callee) \
647 ( (basicblock *) (ptrint) (0x333 + (callee)->depth) )
649 #define RETADDRNR_FROM_BLOCK(bptr) (UNUSED - 1 - (bptr)->nr)
652 static void inline_add_block_reference(inline_node *iln, basicblock **blockp)
654 inline_target_ref *ref;
656 ref = DNEW(inline_target_ref);
657 ref->ref.block = blockp;
658 ref->isnumber = false;
659 ref->next = iln->refs;
664 static void inline_add_blocknr_reference(inline_node *iln, s4 *nrp)
666 inline_target_ref *ref;
668 ref = DNEW(inline_target_ref);
670 ref->isnumber = true;
671 ref->next = iln->refs;
676 static void inline_block_translation(inline_node *iln, basicblock *o_bptr, basicblock *n_bptr)
681 assert(ctx->blockmap_index < ctx->master->cumul_blockmapcount);
683 ctx->blockmap[ctx->blockmap_index].iln = iln;
684 ctx->blockmap[ctx->blockmap_index].o_block = o_bptr;
685 ctx->blockmap[ctx->blockmap_index].n_block = n_bptr;
687 ctx->blockmap_index++;
691 static basicblock * inline_map_block(inline_node *iln,
693 inline_node *targetiln)
695 inline_block_map *bm;
696 inline_block_map *bmend;
704 bm = iln->ctx->blockmap;
705 bmend = bm + iln->ctx->blockmap_index;
708 assert(bm->iln && bm->o_block && bm->n_block);
709 if (bm->o_block == o_block && bm->iln == targetiln)
715 return NULL; /* not reached */
719 static void inline_resolve_block_refs(inline_target_ref **refs,
724 inline_target_ref *ref;
725 inline_target_ref *prev;
728 for (ref = *refs; ref != NULL; ref = ref->next) {
729 if (ref->isnumber && !returnref) {
730 if (*(ref->ref.nr) == RETADDRNR_FROM_BLOCK(o_bptr)) {
731 *(ref->ref.nr) = RETADDRNR_FROM_BLOCK(n_bptr);
736 if (*(ref->ref.block) == o_bptr) {
737 *(ref->ref.block) = n_bptr;
748 /* remove this ref */
751 prev->next = ref->next;
760 /* basic block creation *******************************************************/
762 static basicblock * create_block(inline_node *container,
777 assert(indepth >= 0);
779 n_bptr = container->inlined_basicblocks_cursor++;
781 assert((n_bptr - container->inlined_basicblocks) < container->cumul_basicblockcount);
783 BASICBLOCK_INIT(n_bptr, iln->m);
785 n_bptr->iinstr = container->inlined_iinstr_cursor;
786 n_bptr->next = n_bptr + 1;
787 n_bptr->nr = container->ctx->next_block_number++;
788 n_bptr->indepth = indepth;
789 n_bptr->flags = BBFINISHED; /* XXX */
791 /* set the inlineinfo of the new block */
793 if (iln->inline_start_instruction)
794 n_bptr->inlineinfo = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
796 if (indepth > container->ctx->maxinoutdepth)
797 container->ctx->maxinoutdepth = indepth;
800 n_bptr->invars = DMNEW(s4, indepth);
803 for (i=0; i<indepth; ++i)
804 n_bptr->invars[i] = -1; /* XXX debug */
806 /* pass-through variables enter the block */
808 outer = inner->parent;
809 while (outer != NULL) {
810 depth = outer->n_passthroughcount;
812 assert(depth + inner->n_selfpassthroughcount <= indepth);
814 for (i=0; i<inner->n_selfpassthroughcount; ++i) {
815 varidx = inner->n_passthroughvars[i];
817 inline_new_variable_clone(container->ctx->resultjd,
820 n_bptr->invars[depth + i] = newvaridx;
821 outer->varmap[varidx] = newvaridx;
824 outer = outer->parent;
828 n_bptr->invars = NULL;
831 /* XXX for the verifier. should not be here */
836 dv = DMNEW(varinfo, iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
837 MZERO(dv, varinfo, iln->ctx->resultjd->localcount + VERIFIER_EXTRA_LOCALS);
838 n_bptr->inlocals = dv;
845 static s4 *translate_javalocals(inline_node *iln, s4 *javalocals)
850 jl = DMNEW(s4, iln->jd->maxlocals);
852 for (i=0; i<iln->jd->maxlocals; ++i) {
855 j = inline_translate_variable(iln->ctx->resultjd, iln->jd, iln->varmap, j);
860 /* an encoded returnAddress value - must be relocated */
861 inline_add_blocknr_reference(iln, &(jl[i]));
870 static basicblock * create_body_block(inline_node *iln,
871 basicblock *o_bptr, s4 *varmap)
876 n_bptr = create_block(iln, iln, iln,
877 o_bptr->indepth + iln->n_passthroughcount);
879 n_bptr->type = o_bptr->type;
880 n_bptr->flags = o_bptr->flags;
881 n_bptr->bitflags = o_bptr->bitflags;
883 /* resolve references to this block */
885 inline_resolve_block_refs(&(iln->refs), o_bptr, n_bptr, false);
887 /* translate the invars of the original block */
889 for (i=0; i<o_bptr->indepth; ++i) {
890 n_bptr->invars[iln->n_passthroughcount + i] =
891 inline_translate_variable(iln->ctx->resultjd, iln->jd,
896 /* translate javalocals info (not for dead code) */
898 if (n_bptr->flags >= BBREACHED)
899 n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);
905 static basicblock * create_epilog_block(inline_node *caller, inline_node *callee, s4 *varmap)
911 /* number of return variables */
913 retcount = (callee->n_resultlocal == -1
914 && callee->m->parseddesc->returntype.type != TYPE_VOID) ? 1 : 0;
916 /* start the epilog block */
918 n_bptr = create_block(caller, caller, callee,
919 callee->n_passthroughcount + retcount);
921 /* resolve references to the return block */
923 inline_resolve_block_refs(&(callee->refs),
924 INLINE_RETURN_REFERENCE(callee),
928 /* return variable */
931 idx = inline_new_variable(caller->ctx->resultjd,
932 callee->m->parseddesc->returntype.type, 0 /* XXX */);
933 n_bptr->invars[callee->n_passthroughcount] = idx;
934 varmap[callee->callerins->dst.varindex] = idx;
939 n_bptr->javalocals = DMNEW(s4, caller->jd->maxlocals);
940 MCOPY(n_bptr->javalocals, caller->javalocals, s4, caller->jd->maxlocals);
942 /* set block flags & type */
944 n_bptr->flags = /* XXX original block flags */ BBFINISHED;
945 n_bptr->type = BBTYPE_STD;
951 static void close_block(inline_node *iln, inline_node *inner, basicblock *n_bptr, s4 outdepth)
958 n_bptr->outdepth = outdepth;
959 n_bptr->outvars = DMNEW(s4, outdepth);
961 for (i=0; i<outdepth; ++i)
962 n_bptr->outvars[i] = 0; /* XXX debug */
964 if (outdepth > iln->ctx->maxinoutdepth)
965 iln->ctx->maxinoutdepth = outdepth;
967 /* pass-through variables leave the block */
969 outer = inner->parent;
970 while (outer != NULL) {
971 depth = outer->n_passthroughcount;
973 assert(depth + inner->n_selfpassthroughcount <= outdepth);
975 for (i=0; i<inner->n_selfpassthroughcount; ++i) {
976 varidx = inner->n_passthroughvars[i];
977 n_bptr->outvars[depth + i] =
978 inline_translate_variable(iln->ctx->resultjd,
984 outer = outer->parent;
989 static void close_prolog_block(inline_node *iln,
991 inline_node *nextcall)
993 /* XXX add original outvars! */
994 close_block(iln, nextcall, n_bptr, nextcall->n_passthroughcount);
996 /* pass-through variables */
998 DOLOG( printf("closed prolog block:\n");
999 show_basicblock(iln->ctx->resultjd, n_bptr, SHOW_STACK); );
1003 static void close_body_block(inline_node *iln,
1012 close_block(iln, iln, n_bptr, iln->n_passthroughcount + o_bptr->outdepth + retcount);
1014 /* translate the outvars of the original block */
1016 /* XXX reuse code */
1017 for (i=0; i<o_bptr->outdepth; ++i) {
1018 n_bptr->outvars[iln->n_passthroughcount + i] =
1019 inline_translate_variable(iln->ctx->resultjd, iln->jd, varmap,
1020 o_bptr->outvars[i]);
1023 /* set the return variable, if any */
1026 assert(retidx >= 0);
1027 n_bptr->outvars[iln->n_passthroughcount + o_bptr->outdepth] = retidx;
1032 /* inlined code generation ****************************************************/
1034 static instruction * inline_instruction(inline_node *iln,
1036 instruction *o_iptr)
1038 instruction *n_iptr;
1040 n_iptr = (iln->inlined_iinstr_cursor++);
1041 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1043 n_iptr->opc = opcode;
1044 n_iptr->flags.bits = o_iptr->flags.bits & INS_FLAG_ID_MASK;
1045 n_iptr->line = o_iptr->line;
1050 static void inline_generate_sync_builtin(inline_node *iln,
1051 inline_node *callee,
1052 instruction *o_iptr,
1059 if (callee->m->flags & ACC_STATIC) {
1061 syncvar = inline_new_temp_variable(iln->ctx->resultjd, TYPE_ADR);
1063 n_ins = inline_instruction(iln, ICMD_ACONST, o_iptr);
1064 n_ins->sx.val.c.cls = callee->m->class;
1065 n_ins->dst.varindex = syncvar;
1066 n_ins->flags.bits |= INS_FLAG_CLASS;
1069 syncvar = instancevar;
1072 assert(syncvar != UNUSED);
1074 /* MONITORENTER / MONITOREXIT */
1076 n_ins = inline_instruction(iln, ICMD_BUILTIN, o_iptr);
1077 n_ins->sx.s23.s3.bte = builtintable_get_internal(func);
1078 n_ins->s1.argcount = 1; /* XXX add through-vars */
1079 n_ins->sx.s23.s2.args = DMNEW(s4, 1);
1080 n_ins->sx.s23.s2.args[0] = syncvar;
1083 static s4 emit_inlining_prolog(inline_node *iln,
1084 inline_node *callee,
1085 instruction *o_iptr,
1088 methodinfo *calleem;
1094 insinfo_inline *insinfo;
1097 assert(iln && callee && o_iptr);
1099 calleem = callee->m;
1100 md = calleem->parseddesc;
1102 /* INLINE_START instruction */
1104 n_ins = inline_instruction(iln, ICMD_INLINE_START, o_iptr);
1106 insinfo = DNEW(insinfo_inline);
1107 insinfo->method = callee->m;
1108 insinfo->outer = iln->m;
1109 insinfo->synclocal = callee->synclocal;
1110 insinfo->synchronize = callee->synchronize;
1111 insinfo->javalocals_start = NULL;
1112 insinfo->javalocals_end = NULL;
1114 /* info about stack vars live at the INLINE_START */
1116 insinfo->throughcount = callee->n_passthroughcount;
1117 insinfo->paramcount = md->paramcount;
1118 insinfo->stackvarscount = o_iptr->s1.argcount;
1119 insinfo->stackvars = DMNEW(s4, insinfo->stackvarscount);
1120 for (i=0; i<insinfo->stackvarscount; ++i)
1121 insinfo->stackvars[i] = iln->varmap[o_iptr->sx.s23.s2.args[i]];
1123 /* info about the surrounding inlining */
1125 if (iln->inline_start_instruction)
1126 insinfo->parent = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
1128 insinfo->parent = NULL;
1130 /* finish the INLINE_START instruction */
1132 n_ins->sx.s23.s3.inlineinfo = insinfo;
1133 callee->inline_start_instruction = n_ins;
1135 DOLOG( printf("%sprolog: ", iln->indent);
1136 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1138 /* handle parameters for the inlined callee */
1140 localindex = callee->localsoffset + md->paramslots;
1142 for (i=md->paramcount-1; i>=0; --i) {
1145 type = md->paramtypes[i].type;
1147 localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
1148 assert(callee->regdata);
1150 /* translate the argument variable */
1152 argvar = varmap[o_iptr->sx.s23.s2.args[i]];
1153 assert(argvar != UNUSED);
1155 /* remove preallocation from the argument variable */
1157 iln->ctx->resultjd->var[argvar].flags &= ~(PREALLOC | INMEMORY);
1159 /* check the instance slot against NULL */
1160 /* we don't need that for <init> methods, as the verifier */
1161 /* ensures that they are only called for an uninit. object */
1162 /* (which may not be NULL). */
1164 if (!callee->isstatic && i == 0 && calleem->name != utf_init) {
1165 assert(type == TYPE_ADR);
1166 n_ins = inline_instruction(iln, ICMD_CHECKNULL, o_iptr);
1167 n_ins->s1.varindex = argvar;
1168 n_ins->dst.varindex = n_ins->s1.varindex;
1171 /* store argument into local variable of inlined callee */
1173 if (callee->jd->local_map[5*(localindex - callee->localsoffset) + type] != UNUSED)
1175 /* this value is used in the callee */
1177 if (i == 0 && callee->synclocal != UNUSED) {
1178 /* we also need it for synchronization, so copy it */
1179 assert(type == TYPE_ADR);
1180 n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
1183 n_ins = inline_instruction(iln, ICMD_ISTORE + type, o_iptr);
1184 n_ins->sx.s23.s3.javaindex = UNUSED;
1186 n_ins->s1.varindex = argvar;
1187 n_ins->dst.varindex = iln->ctx->resultjd->local_map[5*localindex + type];
1188 assert(n_ins->dst.varindex != UNUSED);
1190 else if (i == 0 && callee->synclocal != UNUSED) {
1191 /* the value is not used inside the callee, but we need it for */
1192 /* synchronization */
1193 /* XXX In this case it actually makes no sense to create a */
1194 /* separate synchronization variable. */
1196 n_ins = inline_instruction(iln, ICMD_NOP, o_iptr);
1199 /* this value is not used, pop it */
1201 n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
1202 n_ins->s1.varindex = argvar;
1205 DOLOG( printf("%sprolog: ", iln->indent);
1206 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1209 /* COPY for synchronized instance methods */
1211 if (callee->synclocal != UNUSED) {
1212 n_ins = inline_instruction(iln, ICMD_COPY, o_iptr);
1213 n_ins->s1.varindex = varmap[o_iptr->sx.s23.s2.args[0]];
1214 n_ins->dst.varindex = callee->synclocal;
1216 assert(n_ins->s1.varindex != UNUSED);
1219 if (callee->synchronize) {
1220 inline_generate_sync_builtin(iln, callee, o_iptr,
1221 (callee->isstatic) ? UNUSED : varmap[o_iptr->sx.s23.s2.args[0]],
1222 LOCK_monitor_enter);
1225 /* INLINE_BODY instruction */
1227 n_ins = inline_instruction(iln, ICMD_INLINE_BODY, callee->jd->basicblocks[0].iinstr);
1228 n_ins->sx.s23.s3.inlineinfo = insinfo;
1234 static void emit_inlining_epilog(inline_node *iln, inline_node *callee, instruction *o_iptr)
1239 assert(iln && callee && o_iptr);
1240 assert(callee->inline_start_instruction);
1242 if (callee->synchronize) {
1243 inline_generate_sync_builtin(iln, callee, o_iptr,
1248 /* INLINE_END instruction */
1250 n_ins = inline_instruction(iln, ICMD_INLINE_END, o_iptr);
1251 n_ins->sx.s23.s3.inlineinfo = callee->inline_start_instruction->sx.s23.s3.inlineinfo;
1253 /* set the javalocals */
1255 jl = DMNEW(s4, iln->jd->maxlocals);
1256 MCOPY(jl, iln->javalocals, s4, iln->jd->maxlocals);
1257 n_ins->sx.s23.s3.inlineinfo->javalocals_end = jl;
1259 DOLOG( printf("%sepilog: ", iln->indent);
1260 show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1264 #define TRANSLATE_VAROP(vo) \
1265 n_iptr->vo.varindex = inline_translate_variable(jd, origjd, varmap, n_iptr->vo.varindex)
1268 static void inline_clone_instruction(inline_node *iln,
1272 instruction *o_iptr,
1273 instruction *n_iptr)
1275 icmdtable_entry_t *icmdt;
1276 builtintable_entry *bte;
1279 branch_target_t *table;
1280 lookup_target_t *lookup;
1285 icmdt = &(icmd_table[o_iptr->opc]);
1287 switch (icmdt->dataflow) {
1292 TRANSLATE_VAROP(sx.s23.s3);
1294 TRANSLATE_VAROP(sx.s23.s2);
1296 TRANSLATE_VAROP(s1);
1300 TRANSLATE_VAROP(sx.s23.s2);
1304 TRANSLATE_VAROP(s1);
1306 TRANSLATE_VAROP(dst);
1310 n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
1311 for (i=0; i<n_iptr->s1.argcount; ++i) {
1312 n_iptr->sx.s23.s2.args[i] =
1313 inline_translate_variable(jd, origjd, varmap,
1314 o_iptr->sx.s23.s2.args[i]);
1316 TRANSLATE_VAROP(dst);
1320 INSTRUCTION_GET_METHODDESC(n_iptr, md);
1322 n_iptr->s1.argcount += iln->n_passthroughcount;
1323 n_iptr->sx.s23.s2.args = DMNEW(s4, n_iptr->s1.argcount);
1324 for (i=0; i<o_iptr->s1.argcount; ++i) {
1325 n_iptr->sx.s23.s2.args[i] =
1326 inline_translate_variable(jd, origjd, varmap,
1327 o_iptr->sx.s23.s2.args[i]);
1329 for (scope = iln; scope != NULL; scope = scope->parent) {
1330 for (j = 0; j < scope->n_selfpassthroughcount; ++j) {
1331 n_iptr->sx.s23.s2.args[i++] =
1332 scope->parent->varmap[scope->n_passthroughvars[j]];
1335 if (md->returntype.type != TYPE_VOID)
1336 TRANSLATE_VAROP(dst);
1340 bte = n_iptr->sx.s23.s3.bte;
1348 switch (icmdt->controlflow) {
1350 TRANSLATE_VAROP(s1); /* XXX should be handled by data-flow */
1354 inline_add_block_reference(iln, &(n_iptr->dst.block));
1358 inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.jsrtarget.block));
1362 i = n_iptr->sx.s23.s3.tablehigh - n_iptr->sx.s23.s2.tablelow + 1 + 1 /* default */;
1364 table = DMNEW(branch_target_t, i);
1365 MCOPY(table, o_iptr->dst.table, branch_target_t, i);
1366 n_iptr->dst.table = table;
1369 inline_add_block_reference(iln, &(table->block));
1375 inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.lookupdefault.block));
1377 i = n_iptr->sx.s23.s2.lookupcount;
1378 lookup = DMNEW(lookup_target_t, i);
1379 MCOPY(lookup, o_iptr->dst.lookup, lookup_target_t, i);
1380 n_iptr->dst.lookup = lookup;
1383 inline_add_block_reference(iln, &(lookup->target.block));
1389 /* XXX move this to dataflow section? */
1391 switch (n_iptr->opc) {
1394 if (n_iptr->flags.bits & INS_FLAG_RETADDR)
1395 inline_add_blocknr_reference(iln, &(n_iptr->sx.s23.s2.retaddrnr));
1402 stack_javalocals_store(n_iptr, iln->javalocals);
1408 static void inline_rewrite_method(inline_node *iln)
1412 instruction *o_iptr;
1413 instruction *n_iptr;
1414 inline_node *nextcall;
1416 inline_block_map *bm;
1421 char indent[100]; /* XXX debug */
1427 resultjd = iln->ctx->resultjd;
1431 nextcall = iln->children;
1434 for (i=0; i<iln->depth; ++i)
1437 iln->indent = indent;
1439 DOLOG( printf("%srewriting: ", indent); method_println(iln->m);
1440 printf("%s(passthrough: %d+%d)\n",
1441 indent, iln->n_passthroughcount - iln->n_selfpassthroughcount,
1442 iln->n_passthroughcount); );
1444 /* set memory cursors */
1446 iln->inlined_iinstr_cursor = iln->inlined_iinstr;
1447 iln->inlined_basicblocks_cursor = iln->inlined_basicblocks;
1449 /* allocate temporary buffers */
1451 iln->javalocals = DMNEW(s4, iln->jd->maxlocals);
1453 /* loop over basic blocks */
1455 o_bptr = iln->jd->basicblocks;
1456 for (; o_bptr; o_bptr = o_bptr->next) {
1458 if (o_bptr->flags < BBREACHED) {
1460 /* ignore the dummy end block */
1462 if (o_bptr->icount == 0 && o_bptr->next == NULL) {
1463 /* enter the following block as translation, for exception handler ranges */
1464 inline_block_translation(iln, o_bptr, iln->inlined_basicblocks_cursor);
1469 printf("%s* skipping old L%03d (flags=%d, type=%d, oid=%d) of ",
1471 o_bptr->nr, o_bptr->flags, o_bptr->type,
1473 method_println(iln->m);
1476 n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1478 /* enter it in the blockmap */
1480 inline_block_translation(iln, o_bptr, n_bptr);
1482 close_body_block(iln, n_bptr, o_bptr, iln->varmap, 0, -1);
1486 len = o_bptr->icount;
1487 o_iptr = o_bptr->iinstr;
1490 printf("%s* rewriting old L%03d (flags=%d, type=%d, oid=%d) of ",
1492 o_bptr->nr, o_bptr->flags, o_bptr->type,
1494 method_println(iln->m);
1495 show_basicblock(iln->jd, o_bptr, SHOW_STACK);
1498 if (iln->blockbefore || o_bptr != iln->jd->basicblocks) {
1499 /* create an inlined clone of this block */
1501 n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1504 /* enter it in the blockmap */
1506 inline_block_translation(iln, o_bptr, n_bptr);
1508 /* initialize the javalocals */
1510 MCOPY(iln->javalocals, n_bptr->javalocals, s4, iln->jd->maxlocals);
1515 /* continue caller block */
1517 n_bptr = iln->inlined_basicblocks_cursor - 1;
1518 icount = n_bptr->icount;
1520 /* translate the javalocals */
1522 jl = translate_javalocals(iln, o_bptr->javalocals);
1523 iln->inline_start_instruction->sx.s23.s3.inlineinfo->javalocals_start = jl;
1525 MCOPY(iln->javalocals, jl, s4, iln->jd->maxlocals);
1528 /* iterate over the ICMDs of this block */
1533 while (--len >= 0) {
1535 DOLOG( fputs(indent, stdout); show_icmd(iln->jd, o_iptr, false, SHOW_STACK);
1538 /* handle calls that will be inlined */
1540 if (nextcall && o_iptr == nextcall->callerins) {
1542 /* write the inlining prolog */
1544 (void) emit_inlining_prolog(iln, nextcall, o_iptr, iln->varmap);
1545 icount += nextcall->prolog_instructioncount;
1547 /* end current block, or glue blocks together */
1549 n_bptr->icount = icount;
1551 if (nextcall->blockbefore) {
1552 close_prolog_block(iln, n_bptr, nextcall);
1558 /* check if the result is a local variable */
1560 if (nextcall->m->parseddesc->returntype.type != TYPE_VOID
1561 && o_iptr->dst.varindex < iln->jd->localcount)
1563 nextcall->n_resultlocal = iln->varmap[o_iptr->dst.varindex];
1566 nextcall->n_resultlocal = -1;
1568 /* set memory pointers in the callee */
1570 nextcall->inlined_iinstr = iln->inlined_iinstr_cursor;
1571 nextcall->inlined_basicblocks = iln->inlined_basicblocks_cursor;
1575 DOLOG( printf("%sentering inline ", indent);
1576 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1578 inline_rewrite_method(nextcall);
1580 DOLOG( printf("%sleaving inline ", indent);
1581 show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1583 /* update memory cursors */
1585 assert(nextcall->inlined_iinstr_cursor
1586 <= iln->inlined_iinstr_cursor + nextcall->cumul_instructioncount);
1587 assert(nextcall->inlined_basicblocks_cursor
1588 == iln->inlined_basicblocks_cursor + nextcall->cumul_basicblockcount);
1589 iln->inlined_iinstr_cursor = nextcall->inlined_iinstr_cursor;
1590 iln->inlined_basicblocks_cursor = nextcall->inlined_basicblocks_cursor;
1592 /* start new block, or glue blocks together */
1594 if (nextcall->blockafter) {
1595 n_bptr = create_epilog_block(iln, nextcall, iln->varmap);
1599 n_bptr = iln->inlined_basicblocks_cursor - 1;
1600 icount = n_bptr->icount;
1604 /* emit inlining epilog */
1606 emit_inlining_epilog(iln, nextcall, o_iptr);
1607 icount += nextcall->epilog_instructioncount;
1609 /* proceed to next call */
1611 nextcall = nextcall->next;
1614 n_iptr = (iln->inlined_iinstr_cursor++);
1615 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1617 switch (o_iptr->opc) {
1619 if (iln->depth == 0)
1628 if (iln->depth == 0)
1631 retidx = iln->varmap[o_iptr->s1.varindex];
1632 if (iln->n_resultlocal != -1) {
1633 /* store result in a local variable */
1635 DOLOG( printf("USING RESULTLOCAL %d\n", iln->n_resultlocal); );
1636 /* This relies on the same sequence of types for */
1637 /* ?STORE and ?RETURN opcodes. */
1638 n_iptr->opc = ICMD_ISTORE + (o_iptr->opc - ICMD_IRETURN);
1639 n_iptr->s1.varindex = retidx;
1640 n_iptr->dst.varindex = iln->n_resultlocal;
1641 n_iptr->sx.s23.s3.javaindex = UNUSED; /* XXX set real javaindex? */
1646 n_iptr = (iln->inlined_iinstr_cursor++);
1647 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1650 else if ((retidx < resultjd->localcount && iln->blockafter)
1651 || !iln->blockafter) /* XXX do we really always need the MOVE? */
1653 /* local must not become outvar, insert a MOVE */
1655 n_iptr->opc = ICMD_MOVE;
1656 n_iptr->s1.varindex = retidx;
1657 retidx = inline_new_temp_variable(resultjd,
1658 resultjd->var[retidx].type);
1659 n_iptr->dst.varindex = retidx;
1661 n_iptr = (iln->inlined_iinstr_cursor++);
1662 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1666 if (iln->blockafter) {
1667 n_iptr->opc = ICMD_GOTO;
1668 n_iptr->dst.block = INLINE_RETURN_REFERENCE(iln);
1669 inline_add_block_reference(iln, &(n_iptr->dst.block));
1672 n_iptr->opc = ICMD_NOP;
1676 if (o_bptr->next == NULL || (o_bptr->next->icount==0 && o_bptr->next->next == NULL)) {
1677 n_iptr->opc = ICMD_NOP;
1686 inline_clone_instruction(iln, resultjd, iln->jd, iln->varmap, o_iptr, n_iptr);
1689 DOLOG( fputs(indent, stdout); show_icmd(resultjd, n_iptr, false, SHOW_STACK);
1698 /* end of basic block */
1700 if (iln->blockafter || (o_bptr->next && o_bptr->next->next)) {
1701 close_body_block(iln, n_bptr, o_bptr, iln->varmap, retcount, retidx);
1702 n_bptr->icount = icount;
1704 DOLOG( printf("closed body block:\n");
1705 show_basicblock(resultjd, n_bptr, SHOW_STACK); );
1708 n_bptr->icount = icount;
1709 assert(iln->parent);
1710 if (retidx != UNUSED)
1711 iln->parent->varmap[iln->callerins->dst.varindex] = retidx;
1715 bm = iln->ctx->blockmap;
1716 for (i=0; i<iln->ctx->blockmap_index; ++i, ++bm) {
1717 assert(bm->iln && bm->o_block && bm->n_block);
1719 inline_resolve_block_refs(&(iln->refs), bm->o_block, bm->n_block, false);
1722 #if !defined(NDEBUG)
1724 inline_target_ref *ref;
1727 if (!iln->depth || ref->isnumber || *(ref->ref.block) != INLINE_RETURN_REFERENCE(iln)) {
1728 DOLOG( printf("XXX REMAINING REF at depth %d: %p\n", iln->depth,
1729 (void*)*(ref->ref.block)) );
1739 static exception_entry * inline_exception_tables(inline_node *iln,
1740 exception_entry *n_extable,
1741 exception_entry **prevextable)
1745 exception_entry *et;
1749 assert(prevextable);
1751 child = iln->children;
1754 n_extable = inline_exception_tables(child, n_extable, prevextable);
1755 child = child->next;
1756 } while (child != iln->children);
1759 et = iln->jd->exceptiontable;
1760 for (; et != NULL; et = et->down) {
1762 MZERO(n_extable, exception_entry, 1);
1763 n_extable->start = inline_map_block(iln, et->start , iln);
1764 n_extable->end = inline_map_block(iln, et->end , iln);
1765 n_extable->handler = inline_map_block(iln, et->handler, iln);
1766 n_extable->catchtype = et->catchtype;
1769 (*prevextable)->down = n_extable;
1771 *prevextable = n_extable;
1776 if (iln->handler_monitorexit) {
1777 exception_entry **activehandlers;
1779 MZERO(n_extable, exception_entry, 1);
1780 n_extable->start = iln->inlined_basicblocks;
1781 n_extable->end = iln->inlined_basicblocks_cursor;
1782 n_extable->handler = iln->handler_monitorexit;
1783 n_extable->catchtype.any = NULL; /* finally */
1786 (*prevextable)->down = n_extable;
1788 *prevextable = n_extable;
1792 /* We have to protect the created handler with the same handlers */
1793 /* that protect the method body itself. */
1795 for (scope = iln; scope->parent != NULL; scope = scope->parent) {
1797 activehandlers = scope->o_handlers;
1798 assert(activehandlers);
1800 while (*activehandlers) {
1802 assert(scope->parent);
1804 MZERO(n_extable, exception_entry, 1);
1805 n_extable->start = iln->handler_monitorexit;
1806 n_extable->end = iln->handler_monitorexit + 1; /* XXX ok in this case? */
1807 n_extable->handler = inline_map_block(scope->parent,
1808 (*activehandlers)->handler,
1810 n_extable->catchtype = (*activehandlers)->catchtype;
1813 (*prevextable)->down = n_extable;
1815 *prevextable = n_extable;
1827 static void inline_locals(inline_node *iln)
1833 iln->varmap = create_variable_map(iln);
1835 child = iln->children;
1838 inline_locals(child);
1839 child = child->next;
1840 } while (child != iln->children);
1843 if (iln->regdata->memuse > iln->ctx->resultjd->rd->memuse)
1844 iln->ctx->resultjd->rd->memuse = iln->regdata->memuse;
1845 if (iln->regdata->argintreguse > iln->ctx->resultjd->rd->argintreguse)
1846 iln->ctx->resultjd->rd->argintreguse = iln->regdata->argintreguse;
1847 if (iln->regdata->argfltreguse > iln->ctx->resultjd->rd->argfltreguse)
1848 iln->ctx->resultjd->rd->argfltreguse = iln->regdata->argfltreguse;
1852 static void inline_interface_variables(inline_node *iln)
1859 resultjd = iln->ctx->resultjd;
1861 resultjd->interface_map = DMNEW(interface_info, 5*iln->ctx->maxinoutdepth);
1862 for (i=0; i<5*iln->ctx->maxinoutdepth; ++i)
1863 resultjd->interface_map[i].flags = UNUSED;
1865 for (bptr = resultjd->basicblocks; bptr != NULL; bptr = bptr->next) {
1866 assert(bptr->indepth <= iln->ctx->maxinoutdepth);
1867 assert(bptr->outdepth <= iln->ctx->maxinoutdepth);
1869 for (i=0; i<bptr->indepth; ++i) {
1870 v = &(resultjd->var[bptr->invars[i]]);
1872 if (v->type == TYPE_RET)
1873 v->flags |= PREALLOC;
1875 v->flags &= ~PREALLOC;
1876 v->flags &= ~INMEMORY;
1877 assert(bptr->invars[i] >= resultjd->localcount);
1879 if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1880 resultjd->interface_map[5*i + v->type].flags = v->flags;
1883 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1887 for (i=0; i<bptr->outdepth; ++i) {
1888 v = &(resultjd->var[bptr->outvars[i]]);
1890 if (v->type == TYPE_RET)
1891 v->flags |= PREALLOC;
1893 v->flags &= ~PREALLOC;
1894 v->flags &= ~INMEMORY;
1895 assert(bptr->outvars[i] >= resultjd->localcount);
1897 if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1898 resultjd->interface_map[5*i + v->type].flags = v->flags;
1901 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1908 static void inline_write_exception_handlers(inline_node *master, inline_node *iln)
1913 builtintable_entry *bte;
1918 child = iln->children;
1921 inline_write_exception_handlers(master, child);
1922 child = child->next;
1923 } while (child != iln->children);
1926 if (iln->synchronize) {
1927 /* create the monitorexit handler */
1928 n_bptr = create_block(master, iln, iln,
1929 iln->n_passthroughcount + 1);
1930 n_bptr->type = BBTYPE_EXH;
1931 n_bptr->flags = BBFINISHED;
1933 exvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
1934 n_bptr->invars[iln->n_passthroughcount] = exvar;
1936 iln->handler_monitorexit = n_bptr;
1938 /* ACONST / ALOAD */
1940 n_ins = master->inlined_iinstr_cursor++;
1941 if (iln->m->flags & ACC_STATIC) {
1942 n_ins->opc = ICMD_ACONST;
1943 n_ins->sx.val.c.cls = iln->m->class;
1944 n_ins->flags.bits = INS_FLAG_CLASS;
1947 n_ins->opc = ICMD_ALOAD;
1948 n_ins->s1.varindex = iln->synclocal;
1949 assert(n_ins->s1.varindex != UNUSED);
1951 /* XXX could be PREALLOCed for builtin call */
1952 syncvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
1953 n_ins->dst.varindex = syncvar;
1958 bte = builtintable_get_internal(LOCK_monitor_exit);
1960 n_ins = master->inlined_iinstr_cursor++;
1961 n_ins->opc = ICMD_BUILTIN;
1962 n_ins->s1.argcount = 1 + iln->n_passthroughcount + 1;
1963 n_ins->sx.s23.s2.args = DMNEW(s4, n_ins->s1.argcount);
1964 n_ins->sx.s23.s2.args[0] = syncvar;
1965 for (i=0; i < iln->n_passthroughcount + 1; ++i) {
1966 n_ins->sx.s23.s2.args[1 + i] = n_bptr->invars[i];
1968 n_ins->sx.s23.s3.bte = bte;
1973 n_ins = master->inlined_iinstr_cursor++;
1974 n_ins->opc = ICMD_ATHROW;
1975 n_ins->flags.bits = 0;
1976 n_ins->s1.varindex = exvar;
1979 /* close basic block */
1981 close_block(iln, iln, n_bptr, iln->n_passthroughcount);
1987 /* second pass driver *********************************************************/
1989 static bool inline_transform(inline_node *iln, jitdata *jd)
1994 exception_entry *n_ext;
1995 exception_entry *prevext;
1999 #if defined(INLINE_VERIFY_RESULT)
2000 static int debug_verify_inlined_code = 1;
2002 #if defined(ENABLE_INLINING_DEBUG)
2003 static int debug_counter = 0;
2006 DOLOG( dump_inline_tree(iln, 0); );
2010 n_ins = DMNEW(instruction, iln->cumul_instructioncount);
2011 MZERO(n_ins, instruction, iln->cumul_instructioncount);
2012 iln->inlined_iinstr = n_ins;
2014 n_bb = DMNEW(basicblock, iln->cumul_basicblockcount);
2015 MZERO(n_bb, basicblock, iln->cumul_basicblockcount);
2016 iln->inlined_basicblocks = n_bb;
2018 iln->ctx->blockmap = DMNEW(inline_block_map, iln->cumul_blockmapcount);
2020 n_jd = jit_jitdata_new(iln->m);
2021 n_jd->flags = jd->flags;
2022 n_jd->code->optlevel = jd->code->optlevel;
2023 iln->ctx->resultjd = n_jd;
2027 /* create the local_map */
2029 n_jd->local_map = DMNEW(s4, 5*iln->cumul_maxlocals);
2030 for (i=0; i<5*iln->cumul_maxlocals; ++i)
2031 n_jd->local_map[i] = UNUSED;
2033 /* create / coalesce local variables */
2041 n_jd->localcount = n_jd->vartop;
2043 /* extra variables for verification (debugging) */
2045 #if defined(INLINE_VERIFY_RESULT)
2046 if (debug_verify_inlined_code) {
2047 n_jd->vartop += VERIFIER_EXTRA_LOCALS + VERIFIER_EXTRA_VARS + 100 /* XXX m->maxstack */;
2048 if (n_jd->vartop > n_jd->varcount) {
2050 n_jd->var = DMREALLOC(n_jd->var, varinfo, n_jd->varcount, n_jd->vartop);
2051 n_jd->varcount = n_jd->vartop;
2054 #endif /* defined(INLINE_VERIFY_RESULT) */
2056 /* write inlined code */
2058 inline_rewrite_method(iln);
2060 /* create exception handlers */
2062 inline_write_exception_handlers(iln, iln);
2064 /* write the dummy end block */
2066 n_bptr = create_block(iln, iln, iln, 0);
2067 n_bptr->flags = BBUNDEF;
2068 n_bptr->type = BBTYPE_STD;
2070 /* store created code in jitdata */
2072 n_jd->basicblocks = iln->inlined_basicblocks;
2073 n_jd->basicblockindex = NULL;
2074 n_jd->instructioncount = iln->cumul_instructioncount;
2075 n_jd->instructions = iln->inlined_iinstr;
2077 /* link the basic blocks (dummy end block is not counted) */
2079 n_jd->basicblockcount = (iln->inlined_basicblocks_cursor - iln->inlined_basicblocks) - 1;
2080 for (i=0; i<n_jd->basicblockcount + 1; ++i)
2081 n_jd->basicblocks[i].next = &(n_jd->basicblocks[i+1]);
2083 n_jd->basicblocks[i-1].next = NULL;
2085 /* check basicblock numbers */
2087 #if !defined(NDEBUG)
2088 jit_check_basicblock_numbers(n_jd);
2091 /* create the exception table */
2093 if (iln->cumul_exceptiontablelength) {
2094 exception_entry *tableend;
2096 n_ext = DMNEW(exception_entry, iln->cumul_exceptiontablelength);
2098 tableend = inline_exception_tables(iln, n_ext, &prevext);
2099 assert(tableend == n_ext + iln->cumul_exceptiontablelength);
2101 prevext->down = NULL;
2103 n_jd->exceptiontablelength = iln->cumul_exceptiontablelength;
2104 n_jd->exceptiontable = n_ext;
2110 /*******************************************************************************/
2113 memcpy(n_cd, jd->cd, sizeof(codegendata));
2115 n_cd->method = NULL; /* XXX */
2116 n_jd->maxlocals = iln->cumul_maxlocals;
2117 n_jd->maxinterfaces = iln->ctx->maxinoutdepth;
2119 inline_post_process(n_jd);
2121 inline_interface_variables(iln);
2123 /* for debugging, verify the inlined result */
2125 #if defined(INLINE_VERIFY_RESULT)
2126 if (debug_verify_inlined_code) {
2127 debug_verify_inlined_code = 0;
2128 DOLOG( printf("VERIFYING INLINED RESULT...\n"); fflush(stdout); );
2129 if (!typecheck(n_jd)) {
2130 *exceptionptr = NULL;
2131 DOLOG( printf("XXX INLINED RESULT DID NOT PASS VERIFIER XXX\n") );
2135 DOLOG( printf("VERIFICATION PASSED.\n") );
2137 debug_verify_inlined_code = 1;
2139 #endif /* defined(INLINE_VERIFY_RESULT) */
2141 /* we need bigger free memory stacks (XXX these should not be allocated in reg_setup) */
2143 n_jd->rd->freemem = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
2144 #if defined(HAS_4BYTE_STACKSLOT)
2145 n_jd->rd->freemem_2 = DMNEW(s4, iln->ctx->maxinoutdepth + 1000) /* XXX max vars/block */;
2148 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2149 if ( (n_jd->instructioncount >= opt_inline_debug_min_size)
2150 && (n_jd->instructioncount <= opt_inline_debug_max_size))
2152 if (debug_counter <= opt_inline_debug_end_counter)
2153 #endif /* defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG) */
2155 /* install the inlined result */
2157 *jd->code = *n_jd->code;
2158 n_jd->code = jd->code;
2161 /* statistics and logging */
2163 #if !defined(NDEBUG)
2164 inline_stat_roots++;
2167 printf("==== %d.INLINE ==================================================================\n",
2169 printf("\ninline tree:\n");
2170 dump_inline_tree(iln, 0);
2171 n_jd->flags |= JITDATA_FLAG_SHOWINTERMEDIATE | JITDATA_FLAG_SHOWDISASSEMBLE;
2172 /* debug_dump_inlined_code(iln, n_method, n_cd, n_rd); */
2173 printf("-------- DONE -----------------------------------------------------------\n");
2179 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2187 /******************************************************************************/
2188 /* FIRST PASS: build inlining tree */
2189 /******************************************************************************/
2192 /* inline_pre_parse_heuristics *************************************************
2194 Perform heuristic checks whether a call site should be inlined.
2195 These checks are evaluated before the callee has been parsed and analysed.
2198 caller...........inlining node of the caller
2199 callee...........the called method
2200 site.............information on the call site
2203 true........consider for inlining
2204 false.......don't inline
2206 *******************************************************************************/
2208 static bool inline_pre_parse_heuristics(const inline_node *caller,
2209 const methodinfo *callee,
2212 #if defined(INLINE_MAX_DEPTH)
2213 if (caller->depth >= INLINE_MAX_DEPTH)
2221 /* inline_post_parse_heuristics ************************************************
2223 Perform heuristic checks whether a call site should be inlined.
2224 These checks are evaluated after the callee has been parsed and analysed.
2227 caller...........inlining node of the caller (const)
2228 callee...........the called method (const)
2231 true........consider for inlining
2232 false.......don't inline
2234 *******************************************************************************/
2236 static bool inline_post_parse_heuristics(const inline_node *caller,
2237 const inline_node *callee)
2243 /* inline_afterwards_heuristics ************************************************
2245 Perform heuristic checks whether a call site should be inlined.
2246 These checks are evaluated after the inlining plan for the callee has
2250 caller...........inlining node of the caller (const)
2251 callee...........the called method (const)
2254 true........consider for inlining
2255 false.......don't inline
2257 *******************************************************************************/
2259 static bool inline_afterwards_heuristics(const inline_node *caller,
2260 const inline_node *callee)
2263 #if defined(INLINE_MAX_BLOCK_EXPANSION)
2264 || (caller->cumul_basicblockcount + callee->cumul_basicblockcount
2265 > INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
2267 #if defined(INLINE_MAX_ICMD_EXPANSION)
2268 || (caller->cumul_instructioncount + callee->cumul_instructioncount
2269 > INLINE_MAX_ICMD_EXPANSION*caller->ctx->master->jd->instructioncount)
2280 /* inline_is_monomorphic *******************************************************
2282 Check if the given call site can be proven to be monomorphic.
2285 callee...........the called method
2286 call.............the invocation instruction
2289 site->speculative.....flags whether the inlining is speculative
2290 (only defined if return value is true)
2293 true if the call site is (currently) monomorphic,
2294 false if not or unknown
2296 *******************************************************************************/
2298 static bool inline_is_monomorphic(const methodinfo *callee,
2299 const instruction *call,
2302 if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)
2303 || call->opc == ICMD_INVOKESPECIAL))
2305 site->speculative = false;
2309 /* XXX search single implementation for abstract monomorphics */
2311 if ((callee->flags & (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED
2313 == (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED))
2316 DOLOG( printf("SPECULATIVE INLINE: "); method_println((methodinfo*)callee); );
2317 site->speculative = true;
2323 /* possibly polymorphic call site */
2329 /* inline_can_inline ***********************************************************
2331 Check if inlining of the given call site is possible.
2334 caller...........inlining node of the caller
2335 callee...........the called method
2336 call.............the invocation instruction
2339 site->speculative.....flags whether the inlining is speculative
2340 (only defined if return value is true)
2343 true if inlining is possible, false if not
2345 *******************************************************************************/
2347 static bool inline_can_inline(const inline_node *caller,
2348 const methodinfo *callee,
2349 const instruction *call,
2352 const inline_node *active;
2354 /* cannot inline native methods */
2356 if (callee->flags & ACC_NATIVE)
2359 /* cannot inline possibly polymorphic calls */
2361 if (!inline_is_monomorphic(callee, call, site))
2364 /* cannot inline recursive calls */
2366 for (active = caller; active; active = active->parent) {
2367 if (callee == active->m) {
2368 DOLOG( printf("RECURSIVE!\n") );
2373 /* inlining is possible */
2379 /* inline_create_callee_node ***************************************************
2381 Create an inlining node for the given callee.
2384 caller...........inlining node of the caller (const)
2385 callee...........the called method
2388 the new inlining node
2390 *******************************************************************************/
2392 static inline_node * inline_create_callee_node(const inline_node *caller,
2395 inline_node *cn; /* the callee inline_node */
2397 cn = DNEW(inline_node);
2398 MZERO(cn, inline_node, 1);
2400 cn->depth = caller->depth + 1;
2401 cn->ctx = caller->ctx;
2403 cn->synchronize = (callee->flags & ACC_SYNCHRONIZED);
2404 cn->isstatic = (callee->flags & ACC_STATIC);
2410 /* inline_set_callee_properties ************************************************
2412 Set properties of the inlined call site.
2415 caller...........inlining node of the caller (const)
2416 cn...............the called method
2417 site.............info about the call site (const)
2420 *cn..............has the properties set
2422 *******************************************************************************/
2424 static void inline_set_callee_properties(const inline_node *caller,
2426 const inline_site *site)
2432 /* set info about the call site */
2434 cn->callerblock = site->bptr;
2435 cn->callerins = site->iptr;
2436 cn->callerpc = site->pc;
2437 cn->o_handlers = site->handlers;
2438 cn->n_handlercount = caller->n_handlercount + site->nhandlers;
2440 /* determine if we need basic block boundaries before/after */
2442 cn->blockbefore = false;
2443 cn->blockafter = false;
2445 if (cn->jd->branchtoentry)
2446 cn->blockbefore = true;
2448 if (cn->jd->branchtoend)
2449 cn->blockafter = true;
2451 if (cn->jd->returncount > 1)
2452 cn->blockafter = true;
2454 /* XXX make safer and reusable (maybe store last real block) */
2455 for (bptr = cn->jd->basicblocks; bptr && bptr->next && bptr->next->next; bptr = bptr->next)
2458 if (cn->jd->returnblock != bptr)
2459 cn->blockafter = true;
2461 /* info about the callee */
2463 cn->localsoffset = caller->localsoffset + caller->m->maxlocals;
2464 cn->prolog_instructioncount = cn->m->parseddesc->paramcount + 2;
2465 cn->epilog_instructioncount = 1; /* INLINE_END */
2466 cn->extra_instructioncount = 0;
2468 /* we need a CHECKNULL for instance methods, except for <init> */
2470 if (!cn->isstatic && cn->m->name != utf_init)
2471 cn->prolog_instructioncount += 1;
2473 /* deal with synchronized callees */
2475 if (cn->synchronize) {
2477 builtintable_entry *bte;
2479 /* we need basic block boundaries because of the handler */
2481 cn->blockbefore = true;
2482 cn->blockafter = true;
2484 /* for synchronized static methods */
2485 /* we need an ACONST, MONITORENTER in the prolog */
2486 /* and ACONST, MONITOREXIT in the epilog */
2488 /* for synchronized instance methods */
2489 /* we need an COPY, MONITORENTER in the prolog */
2490 /* and MONITOREXIT in the epilog */
2493 cn->prolog_instructioncount += 2;
2494 cn->epilog_instructioncount += 2;
2497 cn->prolog_instructioncount += 2;
2498 cn->epilog_instructioncount += 1;
2499 cn->localsoffset += 1;
2502 /* and exception handler */
2503 /* ALOAD, builtin_monitorexit, ATHROW */
2505 cn->extra_instructioncount += 3;
2507 /* exception table entries */
2509 cn->extra_exceptiontablelength = 1 + cn->n_handlercount;
2511 /* add exception handler block */
2513 cn->cumul_basicblockcount_root++;
2515 /* we must call the builtins */
2517 bte = builtintable_get_internal(LOCK_monitor_enter);
2519 if (md->memuse > cn->regdata->memuse)
2520 cn->regdata->memuse = md->memuse;
2521 if (md->argintreguse > cn->regdata->argintreguse)
2522 cn->regdata->argintreguse = md->argintreguse;
2524 bte = builtintable_get_internal(LOCK_monitor_exit);
2526 if (md->memuse > cn->regdata->memuse)
2527 cn->regdata->memuse = md->memuse;
2528 if (md->argintreguse > cn->regdata->argintreguse)
2529 cn->regdata->argintreguse = md->argintreguse;
2532 /* determine pass-through variables */
2534 i = site->iptr->s1.argcount - cn->m->parseddesc->paramcount; /* max # of pass-though vars */
2536 cn->n_passthroughvars = DMNEW(s4, i);
2538 for (argi = site->iptr->s1.argcount - 1; argi >= cn->m->parseddesc->paramcount; --argi) {
2539 s4 idx = site->iptr->sx.s23.s2.args[argi];
2540 if (idx >= caller->jd->localcount) {
2541 cn->n_passthroughvars[j] = idx;
2545 DOLOG( printf("PASSING THROUGH LOCAL VARIABLE %d\n", idx); );
2549 cn->n_selfpassthroughcount = j;
2550 cn->n_passthroughcount = caller->n_passthroughcount + cn->n_selfpassthroughcount;
2554 /* inline_cumulate_counters ****************************************************
2556 Cumulate counters after a node has been decided to become inlined.
2559 caller...........inlining node of the caller
2560 callee...........inlining node of the callee (const)
2563 *caller..........gets cumulated values added
2565 *******************************************************************************/
2567 static void inline_cumulate_counters(inline_node *caller,
2568 const inline_node *cn)
2570 caller->cumul_instructioncount += cn->prolog_instructioncount;
2571 caller->cumul_instructioncount += cn->epilog_instructioncount;
2572 caller->cumul_instructioncount += cn->extra_instructioncount;
2573 caller->cumul_instructioncount += cn->cumul_instructioncount - 1 /*invoke*/;
2575 caller->cumul_basicblockcount += cn->cumul_basicblockcount;
2576 caller->cumul_basicblockcount_root += cn->cumul_basicblockcount_root;
2577 caller->cumul_blockmapcount += cn->cumul_blockmapcount;
2578 caller->cumul_exceptiontablelength += cn->cumul_exceptiontablelength;
2579 caller->cumul_exceptiontablelength += cn->extra_exceptiontablelength;
2581 if (cn->cumul_maxlocals > caller->cumul_maxlocals)
2582 caller->cumul_maxlocals = cn->cumul_maxlocals;
2584 /* XXX extra block after inlined call */
2585 if (cn->blockafter) {
2586 caller->cumul_basicblockcount += 1;
2587 caller->cumul_blockmapcount += 1;
2592 /* inline_analyse_callee *******************************************************
2594 Analyse an inlining candidate callee.
2597 caller...........inlining node of the caller
2598 callee...........the called method
2599 site.............info about the call site
2602 site->inlined....true if the callee has been selected for inlining
2605 the inline node of the callee, or
2606 NULL if an error has occurred (don't use the inlining plan in this case)
2608 *******************************************************************************/
2610 static inline_node * inline_analyse_callee(inline_node *caller,
2614 inline_node *cn; /* the callee inline_node */
2616 /* create an inline tree node */
2618 cn = inline_create_callee_node(caller, callee);
2620 /* get the intermediate representation of the callee */
2622 if (!inline_jit_compile(cn))
2625 /* evaluate heuristics after parsing the callee */
2627 if (!inline_post_parse_heuristics(caller, cn))
2630 /* the call site will be inlined */
2632 site->inlined = true;
2634 /* set info about the call site */
2636 inline_set_callee_properties(caller, cn, site);
2638 /* insert the node into the inline tree */
2640 inline_insert_inline_node(caller, cn);
2642 /* analyse recursively */
2644 if (!inline_analyse_code(cn))
2647 if (!inline_afterwards_heuristics(caller, cn)) {
2648 #if defined(INLINE_CANCEL_ON_THRESHOLD)
2651 inline_remove_inline_node(caller, cn);
2652 caller->ctx->stopped = true;
2653 site->inlined = false;
2658 /* cumulate counters */
2660 #if !defined(INLINE_KNAPSACK)
2661 inline_cumulate_counters(caller, cn);
2668 /* inline_process_candidate ****************************************************
2670 Process a selected inlining candidate.
2673 cand.............the candidate
2676 true........everything ok
2677 false.......an error has occurred, don't use the plan
2679 *******************************************************************************/
2681 static bool inline_process_candidate(inline_candidate *cand)
2685 cn = inline_analyse_callee(cand->caller,
2692 if (!cand->site.inlined)
2695 /* store assumptions */
2697 if (cand->site.speculative)
2698 method_add_assumption_monomorphic(cand->callee, cand->caller->ctx->master->m);
2704 /* inline_analyse_code *********************************************************
2706 Analyse the intermediate code of the given inlining node.
2709 iln..............the inlining node
2712 *iln.............the inlining plan
2715 true........everything ok
2716 false.......an error has occurred, don't use the plan
2718 *******************************************************************************/
2720 static bool inline_analyse_code(inline_node *iln)
2727 exception_entry **handlers;
2728 exception_entry *ex;
2739 /* initialize cumulative counters */
2741 iln->cumul_maxlocals = iln->localsoffset + m->maxlocals;
2742 iln->cumul_exceptiontablelength += mjd->exceptiontablelength;
2744 /* iterate over basic blocks */
2748 for (bptr = mjd->basicblocks; bptr; bptr = bptr->next) {
2750 /* count the block */
2751 /* ignore dummy end blocks (but count them for the blockmap) */
2753 iln->cumul_blockmapcount++;
2754 if ((bptr != mjd->basicblocks || iln->blockbefore)
2756 (bptr->icount > 0 || bptr->next != NULL))
2757 iln->cumul_basicblockcount++;
2759 /* skip dead code */
2761 if (bptr->flags < BBREACHED)
2764 /* allocate the buffer of active exception handlers */
2765 /* XXX this wastes some memory, but probably it does not matter */
2767 handlers = DMNEW(exception_entry*, mjd->exceptiontablelength + 1);
2769 /* determine the active exception handlers for this block */
2770 /* XXX maybe the handlers of a block should be part of our IR */
2771 /* XXX this should share code with the type checkers */
2773 for (ex = mjd->exceptiontable; ex ; ex = ex->down) {
2774 if ((ex->start->nr <= bptr->nr) && (ex->end->nr > bptr->nr)) {
2775 handlers[nhandlers++] = ex;
2778 handlers[nhandlers] = NULL;
2781 iptr = bptr->iinstr;
2784 iln->cumul_instructioncount += len;
2786 /* iterate over the instructions of the block */
2788 for (; --len >= 0; ++iptr) {
2790 switch (iptr->opc) {
2791 case ICMD_INVOKEVIRTUAL:
2792 case ICMD_INVOKESPECIAL:
2793 case ICMD_INVOKESTATIC:
2794 case ICMD_INVOKEINTERFACE:
2796 if (!INSTRUCTION_IS_UNRESOLVED(iptr) && !iln->ctx->stopped) {
2797 callee = iptr->sx.s23.s3.fmiref->p.method;
2799 if (inline_can_inline(iln, callee, iptr, &site)) {
2800 site.inlined = false;
2803 site.pc = blockendpc - len - 1;
2804 site.handlers = handlers;
2805 site.nhandlers = nhandlers;
2807 if (inline_pre_parse_heuristics(iln, callee, &site)) {
2808 #if defined(INLINE_KNAPSACK)
2809 inline_add_candidate(iln->ctx, iln, callee, &site);
2811 inline_candidate cand;
2813 cand.callee = callee;
2816 if (!inline_process_candidate(&cand))
2830 /* extra ICMD_MOVE may be necessary */
2831 iln->cumul_instructioncount++;
2836 /* end of basic block */
2843 static void inline_cumulate_counters_recursive(inline_node *iln)
2847 child = iln->children;
2850 inline_cumulate_counters_recursive(child);
2851 inline_cumulate_counters(iln, child);
2852 child = child->next;
2853 } while (child != iln->children);
2858 /* inline_make_inlining_plan ***************************************************
2860 Make an inlining plan for the given root node
2863 iln..............the root node
2866 *iln.............the inlining plan
2869 true........everything ok
2870 false.......an error has occurred, don't use the plan
2872 *******************************************************************************/
2874 static bool inline_make_inlining_plan(inline_node *iln)
2876 #if defined(INLINE_KNAPSACK)
2877 inline_candidate *cand;
2878 #if defined(INLINE_COST_BUDGET)
2879 s4 budget = INLINE_COST_BUDGET;
2880 # define BUDGETMEMBER cost
2882 #if defined(INLINE_WEIGHT_BUDGET)
2883 double budget = INLINE_WEIGHT_BUDGET;
2884 # define BUDGETMEMBER weight
2887 inline_analyse_code(iln);
2889 DOLOG( printf("candidates in "); method_println(iln->m);
2890 inline_candidates_println(iln->ctx); );
2892 while ((cand = inline_pick_best_candidate(iln->ctx)) != NULL)
2894 if (cand->BUDGETMEMBER <= budget) {
2895 DOLOG( printf(" picking: "); inline_candidate_println(cand); );
2897 if (!inline_process_candidate(cand))
2900 #if !defined(INLINE_ADD_NEGATIVE_TO_BUDGET)
2901 if (cand->BUDGETMEMBER > 0)
2903 budget -= cand->BUDGETMEMBER;
2907 inline_cumulate_counters_recursive(iln);
2911 return inline_analyse_code(iln);
2916 /* statistics *****************************************************************/
2918 #if defined(INLINE_STATISTICS)
2919 static void inline_gather_statistics_recursive(inline_node *iln)
2923 inline_stat_inlined_nodes++;
2925 if (iln->depth > inline_stat_max_depth)
2926 inline_stat_max_depth++;
2928 child = iln->children;
2931 inline_gather_statistics_recursive(child);
2932 child = child->next;
2933 } while (child != iln->children);
2936 #endif /* defined(INLINE_STATISTICS) */
2939 #if defined(INLINE_STATISTICS)
2940 static void inline_gather_statistics(inline_node *iln)
2942 inline_stat_roots_transformed++;
2944 inline_gather_statistics_recursive(iln);
2946 #endif /* defined(INLINE_STATISTICS) */
2949 /* post processing ************************************************************/
2951 #define POSTPROCESS_SRC(varindex) live[varindex]--
2952 #define POSTPROCESS_DST(varindex) live[varindex]++
2954 #define POSTPROCESS_SRCOP(s) POSTPROCESS_SRC(iptr->s.varindex)
2955 #define POSTPROCESS_DSTOP(d) POSTPROCESS_DST(iptr->d.varindex)
2957 #define MARKSAVED(varindex) jd->var[varindex].flags |= SAVEDVAR
2959 #define MARK_ALL_SAVED \
2961 for (i=0; i<jd->vartop; ++i) \
2966 static void inline_post_process(jitdata *jd)
2972 icmdtable_entry_t *icmdt;
2975 builtintable_entry *bte;
2977 /* reset the SAVEDVAR flag of all variables */
2979 for (i=0; i<jd->vartop; ++i)
2980 jd->var[i].flags &= ~SAVEDVAR;
2982 /* allocate the life counters */
2984 live = DMNEW(s4, jd->vartop);
2985 MZERO(live, s4, jd->vartop);
2987 /* iterate over all basic blocks */
2989 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
2990 if (bptr->flags < BBREACHED)
2993 /* make invars live */
2995 for (i=0; i<bptr->indepth; ++i)
2996 POSTPROCESS_DST(bptr->invars[i]);
2998 iptr = bptr->iinstr;
2999 iend = iptr + bptr->icount;
3001 for (; iptr < iend; ++iptr) {
3003 icmdt = &(icmd_table[iptr->opc]);
3005 switch (icmdt->dataflow) {
3007 POSTPROCESS_SRCOP(sx.s23.s3);
3009 POSTPROCESS_SRCOP(sx.s23.s2);
3011 POSTPROCESS_SRCOP(s1);
3013 if (icmdt->flags & ICMDTABLE_CALLS) {
3014 jd->isleafmethod = false;
3020 POSTPROCESS_SRCOP(sx.s23.s2);
3023 POSTPROCESS_SRCOP(s1);
3025 if (icmdt->flags & ICMDTABLE_CALLS) {
3026 jd->isleafmethod = false;
3030 POSTPROCESS_DSTOP(dst);
3034 for (i=0; i<iptr->s1.argcount; ++i) {
3035 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3037 if (icmdt->flags & ICMDTABLE_CALLS) {
3038 jd->isleafmethod = false;
3041 POSTPROCESS_DSTOP(dst);
3045 INSTRUCTION_GET_METHODDESC(iptr, md);
3047 jd->isleafmethod = false;
3048 for (i=0; i<md->paramcount; ++i) {
3049 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3051 for (; i<iptr->s1.argcount; ++i) {
3052 MARKSAVED(iptr->sx.s23.s2.args[i]);
3054 if (md->returntype.type != TYPE_VOID)
3055 POSTPROCESS_DSTOP(dst);
3059 bte = iptr->sx.s23.s3.bte;
3061 goto post_process_call;
3067 } /* end instruction loop */
3069 /* consume outvars */
3071 for (i=0; i<bptr->outdepth; ++i)
3072 POSTPROCESS_SRC(bptr->outvars[i]);
3074 #if !defined(NDEBUG)
3075 for (i=jd->localcount; i < jd->vartop; ++i)
3076 assert(live[i] == 0);
3079 } /* end basic block loop */
3083 /* inline_create_root_node *****************************************************
3085 Create the root node of the inlining tree.
3088 jd...............the current jitdata of the root method
3091 the root node of the inlining tree
3093 *******************************************************************************/
3095 static inline_node * inline_create_root_node(jitdata *jd)
3099 iln = DNEW(inline_node);
3100 MZERO(iln, inline_node, 1);
3104 iln->regdata = jd->rd;
3106 iln->blockbefore = true;
3107 iln->blockafter = true;
3109 iln->cumul_instructioncount = 0;
3110 iln->cumul_basicblockcount = 1 /* dummy end block */;
3112 /* create inlining context */
3114 iln->ctx = DNEW(inline_context);
3115 MZERO(iln->ctx, inline_context, 1);
3116 iln->ctx->master = iln;
3117 iln->ctx->next_debugnr = 1; /* XXX debug */
3123 /******************************************************************************/
3124 /* MAIN DRIVER FUNCTION */
3125 /******************************************************************************/
3127 bool inline_inline(jitdata *jd)
3131 DOLOG( printf("==== INLINE ==================================================================\n");
3132 show_method(jd, SHOW_STACK); );
3134 #if defined(INLINE_STATISTICS)
3135 inline_stat_roots++;
3138 iln = inline_create_root_node(jd);
3140 if (inline_make_inlining_plan(iln)) {
3142 /* add blocks to the root node */
3144 iln->cumul_basicblockcount += iln->cumul_basicblockcount_root;
3145 iln->cumul_blockmapcount += iln->cumul_basicblockcount_root;
3147 DOLOG( printf("==== INLINE TRANSFORM ========================================================\n"); );
3150 inline_transform(iln, jd);
3152 #if defined(INLINE_STATISTICS)
3153 inline_gather_statistics(iln);
3157 DOLOG( printf("-------- DONE -----------------------------------------------------------\n");
3164 * These are local overrides for various environment variables in Emacs.
3165 * Please do not remove this and leave it at the end of the file, where
3166 * Emacs will automagically detect them.
3167 * ---------------------------------------------------------------------
3170 * indent-tabs-mode: t
3174 * vim:noexpandtab:sw=4:ts=4: