src/vm/jit/inline/inline.c

   1 /* src/vm/jit/inline/inline.c - method inlining
   2
   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
   7
   8    This file is part of CACAO.
   9
  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.
  14
  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.
  19
  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
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Edwin Steiner
  28
  29    Changes:
  30
  31    $Id: inline.c 7228 2007-01-19 01:13:48Z edwin $
  32
  33 */
  34
  35 #include "config.h"
  36
  37 #include "vm/types.h"
  38
  39 #include <assert.h>
  40 #include <stdio.h>
  41 #include <string.h>
  42 #include <limits.h>
  43
  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"
  54
  55 #include "vm/class.h"
  56 #include "vm/initialize.h"
  57 #include "vm/method.h"
  58 #include "vm/jit/jit.h"
  59 #include "vm/jit/show.h"
  60
  61 #include "vm/jit/reg.h"
  62 #include "vm/jit/stack.h"
  63
  64 #include "vm/jit/verify/typecheck.h"
  65
  66 #if defined(ENABLE_THREADS)
  67 # include "threads/native/threads.h"
  68 #endif
  69
  70
  71 /* algorithm tuning constants *************************************************/
  72
  73 #define INLINE_KNAPSACK
  74
  75 #if defined(INLINE_KNAPSACK)
  76
  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 */
  84
  85 #else
  86
  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*/
  91
  92 #endif
  93
  94
  95 /* debugging ******************************************************************/
  96
  97 #if !defined(NDEBUG)
  98 #define INLINE_VERBOSE
  99 #define DOLOG(code) do{ if (opt_inline_debug_log) { code; } }while(0)
 100 #else
 101 #define DOLOG(code)
 102 #endif
 103
 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 */
 107 /*       verifier code.                                                     */
 108 /* #define INLINE_VERIFY_RESULT */
 109 #endif
 110
 111
 112 /* types **********************************************************************/
 113
 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;
 120
 121 struct inline_node {
 122         inline_context *ctx;
 123
 124         jitdata *jd;
 125         methodinfo *m;
 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 */
 130
 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 */
 135         s4 callerpc;
 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 */
 141         int n_resultlocal;
 142         int synclocal;                    /* variable used for synchr., or UNUSED */
 143         bool isstatic;                                   /* this is a static call */
 144
 145         bool blockbefore;                  /* block boundary before inlined body? */
 146         bool blockafter;                   /* block boundary after inlined body?  */
 147
 148         /* info about the callee */
 149         int localsoffset;
 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 */
 156         s4 *varmap;
 157
 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;
 164         int cumul_maxlocals;
 165         int cumul_exceptiontablelength;
 166
 167         /* output */
 168         instruction *inlined_iinstr;
 169         instruction *inlined_iinstr_cursor;
 170         basicblock *inlined_basicblocks;
 171         basicblock *inlined_basicblocks_cursor;
 172
 173         /* register data */
 174         registerdata *regdata;
 175
 176         /* temporary */
 177         inline_target_ref *refs;
 178         instruction *inline_start_instruction;
 179         s4 *javalocals;
 180
 181         /* XXX debug */
 182         char *indent;
 183         int debugnr;
 184 };
 185
 186 struct inline_target_ref {
 187         inline_target_ref *next;
 188         union {
 189                 basicblock **block;
 190                 s4 *nr;
 191         } ref;
 192         basicblock *target;
 193         bool isnumber;
 194 };
 195
 196 struct inline_block_map {
 197         inline_node *iln;
 198         basicblock *o_block;
 199         basicblock *n_block;
 200 };
 201
 202 struct inline_context {
 203         inline_node *master;
 204
 205         jitdata *resultjd;
 206
 207         inline_candidate *candidates;
 208
 209         int next_block_number;
 210         inline_block_map *blockmap;
 211         int blockmap_index;
 212
 213         int maxinoutdepth;
 214
 215         bool stopped;
 216
 217         int next_debugnr; /* XXX debug */
 218 };
 219
 220 struct inline_site {
 221         bool              speculative;  /* true, if inlining would be speculative */
 222         bool              inlined;      /* true, if this site has been inlined    */
 223
 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       */
 229 };
 230
 231 struct inline_candidate {
 232         inline_candidate *next;
 233         int freq;
 234         int cost;
 235         double weight;
 236         inline_node *caller;
 237         methodinfo *callee;
 238         inline_site site;
 239 };
 240
 241
 242 /* prototypes *****************************************************************/
 243
 244 static bool inline_analyse_code(inline_node *iln);
 245 static void inline_post_process(jitdata *jd);
 246
 247
 248 /* debug helpers **************************************************************/
 249
 250 #if !defined(NDEBUG)
 251 #include "inline_debug.inc"
 252 #endif
 253
 254
 255 /* statistics *****************************************************************/
 256
 257 /*#define INLINE_STATISTICS*/
 258
 259 #if !defined(NDEBUG)
 260 #define INLINE_STATISTICS
 261 #endif
 262
 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;
 268
 269 void inline_print_stats()
 270 {
 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);
 276 }
 277 #endif
 278
 279
 280 /* compilation of callees *****************************************************/
 281
 282 static bool inline_jit_compile_intern(jitdata *jd)
 283 {
 284         methodinfo *m;
 285
 286         /* XXX should share code with jit.c */
 287
 288         assert(jd);
 289
 290         /* XXX initialize the static function's class */
 291
 292         m = jd->m;
 293
 294         /* call the compiler passes ***********************************************/
 295
 296         /* call parse pass */
 297
 298         DOLOG( log_message_class("Parsing ", m->class) );
 299         if (!parse(jd)) {
 300                 return false;
 301         }
 302
 303         /* call stack analysis pass */
 304
 305         if (!stack_analyse(jd)) {
 306                 return false;
 307         }
 308
 309         return true;
 310 }
 311
 312
 313 static bool inline_jit_compile(inline_node *iln)
 314 {
 315         bool                r;
 316         methodinfo         *m;
 317         jitdata            *jd;
 318
 319         /* XXX should share code with jit.c */
 320
 321         assert(iln);
 322         m = iln->m;
 323         assert(m);
 324
 325 #if defined(ENABLE_THREADS)
 326         /* enter a monitor on the method */
 327         lock_monitor_enter((java_objectheader *) m);
 328 #endif
 329
 330         /* allocate jitdata structure and fill it */
 331
 332         jd = jit_jitdata_new(m);
 333         iln->jd = jd;
 334
 335         jd->flags = 0; /* XXX */
 336
 337         /* initialize the register allocator */
 338
 339         reg_setup(jd);
 340
 341         /* setup the codegendata memory */
 342
 343         /* XXX do a pseudo setup */
 344         jd->cd = DNEW(codegendata);
 345         MZERO(jd->cd, codegendata, 1);
 346         jd->cd->maxstack = m->maxstack;
 347         jd->cd->method = m;
 348         /* XXX uses too much dump memory codegen_setup(jd); */
 349
 350         /* now call internal compile function */
 351
 352         r = inline_jit_compile_intern(jd);
 353
 354         if (r) {
 355                 iln->regdata = jd->rd;
 356         }
 357
 358         /* free some memory */
 359 #if 0
 360
 361 #if defined(ENABLE_JIT)
 362 # if defined(ENABLE_INTRP)
 363         if (!opt_intrp)
 364 # endif
 365                 codegen_free(jd);
 366 #endif
 367
 368 #endif
 369
 370 #if defined(ENABLE_THREADS)
 371         /* leave the monitor */
 372         lock_monitor_exit((java_objectheader *) m );
 373 #endif
 374
 375         return r;
 376 }
 377
 378
 379 /* inlining tree handling *****************************************************/
 380
 381 static void inline_insert_inline_node(inline_node *parent, inline_node *child)
 382 {
 383         inline_node *first;
 384         inline_node *succ;
 385
 386         assert(parent && child);
 387
 388         child->parent = parent;
 389
 390         child->debugnr = parent->ctx->next_debugnr++; /* XXX debug */
 391
 392         first = parent->children;
 393         if (!first) {
 394                 /* insert as only node */
 395                 parent->children = child;
 396                 child->next = child;
 397                 child->prev = child;
 398                 return;
 399         }
 400
 401         /* {there is at least one child already there} */
 402
 403         /* XXX is this search necessary, or could we always add at the end? */
 404
 405         succ = first;
 406         while (succ->callerpc < child->callerpc) {
 407                 succ = succ->next;
 408                 if (succ == first) {
 409                         /* insert as last node */
 410                         child->prev = first->prev;
 411                         child->next = first;
 412                         child->prev->next = child;
 413                         child->next->prev = child;
 414                         return;
 415                 }
 416         }
 417
 418         assert(succ->callerpc > child->callerpc);
 419
 420         /* insert before succ */
 421
 422         child->prev = succ->prev;
 423         child->next = succ;
 424         child->prev->next = child;
 425         child->next->prev = child;
 426
 427         if (parent->children == succ)
 428                 parent->children = child;
 429 }
 430
 431
 432 static void inline_remove_inline_node(inline_node *parent, inline_node *child)
 433 {
 434         assert(parent);
 435         assert(child);
 436         assert(child->parent == parent);
 437
 438         if (child->prev == child) {
 439                 /* remove the only child node */
 440                 parent->children = NULL;
 441         }
 442         else {
 443                 child->prev->next = child->next;
 444                 child->next->prev = child->prev;
 445
 446                 if (parent->children == child)
 447                         parent->children = child->next;
 448         }
 449 }
 450
 451
 452 /* inlining candidate handling ************************************************/
 453
 454 #if defined(INLINE_KNAPSACK)
 455 static void inline_add_candidate(inline_context *ctx,
 456                                                                  inline_node *caller,
 457                                                                  methodinfo *callee,
 458                                                                  inline_site *site)
 459 {
 460         inline_candidate **link;
 461         inline_candidate *cand;
 462
 463         cand = DNEW(inline_candidate);
 464 #if defined(INLINE_DIVIDE_COST_BY_FREQ)
 465         cand->freq = INLINE_COUNTDOWN_INIT - callee->hitcountdown;
 466         if (cand->freq < 1)
 467 #endif
 468                 cand->freq = 1;
 469         cand->cost = callee->jcodelength + INLINE_COST_OFFSET;
 470         cand->caller = caller;
 471         cand->callee = callee;
 472         cand->site = *site;
 473
 474         cand->weight = (double)cand->cost / cand->freq;
 475
 476         for (link = &(ctx->candidates); ; link = &((*link)->next)) {
 477                 if (!*link || (*link)->weight > cand->weight) {
 478                         cand->next = *link;
 479                         *link = cand;
 480                         break;
 481                 }
 482         }
 483 }
 484 #endif /* defined(INLINE_KNAPSACK) */
 485
 486 #if defined(INLINE_KNAPSACK)
 487 static inline_candidate * inline_pick_best_candidate(inline_context *ctx)
 488 {
 489         inline_candidate *cand;
 490
 491         cand = ctx->candidates;
 492
 493         if (cand)
 494                 ctx->candidates = cand->next;
 495
 496         return cand;
 497 }
 498 #endif /* defined(INLINE_KNAPSACK) */
 499
 500 #if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
 501 static void inline_candidate_println(inline_candidate *cand)
 502 {
 503         printf("%10g (%5d / %5d) depth %2d ",
 504                         cand->weight, cand->cost, cand->freq, cand->caller->depth + 1);
 505         method_println(cand->callee);
 506 }
 507 #endif /* !defined(NDEBUG) && defined(INLINE_KNAPSACK) */
 508
 509
 510 #if !defined(NDEBUG) && defined(INLINE_KNAPSACK)
 511 static void inline_candidates_println(inline_context *ctx)
 512 {
 513         inline_candidate *cand;
 514
 515         for (cand = ctx->candidates; cand != NULL; cand = cand->next) {
 516                 printf("    ");
 517                 inline_candidate_println(cand);
 518         }
 519 }
 520 #endif /* !defined(NDEBUG) && defined(INLINE_KNAPSACK) */
 521
 522
 523 /* variable handling **********************************************************/
 524
 525 static s4 inline_new_variable(jitdata *jd, s4 type, s4 flags)
 526 {
 527         s4 index;
 528         s4 newcount;
 529
 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;
 536         }
 537
 538         jd->var[index].type = type;
 539         jd->var[index].flags = flags;
 540
 541         return index;
 542 }
 543
 544
 545 static s4 inline_new_variable_clone(jitdata *jd, jitdata *origjd, s4 origidx)
 546 {
 547         varinfo *v;
 548         s4       newidx;
 549
 550         v = &(origjd->var[origidx]);
 551
 552         newidx = inline_new_variable(jd, v->type, v->flags);
 553
 554         jd->var[newidx].vv = v->vv;
 555
 556         return newidx;
 557 }
 558
 559
 560 static s4 inline_new_temp_variable(jitdata *jd, s4 type)
 561 {
 562         return inline_new_variable(jd, type, 0);
 563 }
 564
 565
 566 static s4 inline_translate_variable(jitdata *jd, jitdata *origjd, s4 *varmap, s4 index)
 567 {
 568         s4 idx;
 569
 570         idx = varmap[index];
 571
 572         if (idx < 0) {
 573                 idx = inline_new_variable_clone(jd, origjd, index);
 574                 varmap[index] = idx;
 575         }
 576
 577         return idx;
 578 }
 579
 580
 581 static s4 *create_variable_map(inline_node *callee)
 582 {
 583         s4 *varmap;
 584         s4 i, t;
 585         s4 idx;
 586         s4 n_idx;
 587         s4 avail;
 588         varinfo *v;
 589
 590         /* create the variable mapping */
 591
 592         varmap = DMNEW(s4, callee->jd->varcount);
 593         for (i=0; i<callee->jd->varcount; ++i)
 594                 varmap[i] = -1;
 595
 596         /* translate local variables */
 597
 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];
 601                         if (idx == UNUSED)
 602                                 continue;
 603
 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 */
 607
 608                         avail = callee->ctx->resultjd->local_map[5*(callee->localsoffset + i) + t];
 609
 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;
 613                         }
 614
 615                         varmap[idx] = avail;
 616                 }
 617         }
 618
 619         /* for synchronized instance methods we need an extra local */
 620
 621         if (callee->synchronize && !(callee->m->flags & ACC_STATIC)) {
 622                 n_idx = callee->localsoffset - 1;
 623                 assert(n_idx >= 0);
 624                 assert(callee->parent);
 625                 assert(n_idx == callee->parent->localsoffset + callee->parent->m->maxlocals);
 626
 627                 avail = callee->ctx->resultjd->local_map[5*n_idx + TYPE_ADR];
 628
 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;
 632                 }
 633
 634                 callee->synclocal = avail;
 635         }
 636         else {
 637                 callee->synclocal = UNUSED;
 638         }
 639
 640         return varmap;
 641 }
 642
 643
 644 /* basic block translation ****************************************************/
 645
 646 #define INLINE_RETURN_REFERENCE(callee)  \
 647         ( (basicblock *) (ptrint) (0x333 + (callee)->depth) )
 648
 649 #define RETADDRNR_FROM_BLOCK(bptr)  (UNUSED - 1 - (bptr)->nr)
 650
 651
 652 static void inline_add_block_reference(inline_node *iln, basicblock **blockp)
 653 {
 654         inline_target_ref *ref;
 655
 656         ref = DNEW(inline_target_ref);
 657         ref->ref.block = blockp;
 658         ref->isnumber = false;
 659         ref->next = iln->refs;
 660         iln->refs = ref;
 661 }
 662
 663
 664 static void inline_add_blocknr_reference(inline_node *iln, s4 *nrp)
 665 {
 666         inline_target_ref *ref;
 667
 668         ref = DNEW(inline_target_ref);
 669         ref->ref.nr = nrp;
 670         ref->isnumber = true;
 671         ref->next = iln->refs;
 672         iln->refs = ref;
 673 }
 674
 675
 676 static void inline_block_translation(inline_node *iln, basicblock *o_bptr, basicblock *n_bptr)
 677 {
 678         inline_context *ctx;
 679
 680         ctx = iln->ctx;
 681         assert(ctx->blockmap_index < ctx->master->cumul_blockmapcount);
 682
 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;
 686
 687         ctx->blockmap_index++;
 688 }
 689
 690
 691 static basicblock * inline_map_block(inline_node *iln,
 692                                                                          basicblock *o_block,
 693                                                                          inline_node *targetiln)
 694 {
 695         inline_block_map *bm;
 696         inline_block_map *bmend;
 697
 698         assert(iln);
 699         assert(targetiln);
 700
 701         if (!o_block)
 702                 return NULL;
 703
 704         bm = iln->ctx->blockmap;
 705         bmend = bm + iln->ctx->blockmap_index;
 706
 707         while (bm < bmend) {
 708                 assert(bm->iln && bm->o_block && bm->n_block);
 709                 if (bm->o_block == o_block && bm->iln == targetiln)
 710                         return bm->n_block;
 711                 bm++;
 712         }
 713
 714         assert(false);
 715         return NULL; /* not reached */
 716 }
 717
 718
 719 static void inline_resolve_block_refs(inline_target_ref **refs,
 720                                                                           basicblock *o_bptr,
 721                                                                           basicblock *n_bptr,
 722                                                                           bool returnref)
 723 {
 724         inline_target_ref *ref;
 725         inline_target_ref *prev;
 726
 727         prev = NULL;
 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);
 732                                 goto remove_ref;
 733                         }
 734                 }
 735                 else {
 736                         if (*(ref->ref.block) == o_bptr) {
 737                                 *(ref->ref.block) = n_bptr;
 738                                 goto remove_ref;
 739                         }
 740                 }
 741
 742                 /* skip this ref */
 743
 744                 prev = ref;
 745                 continue;
 746
 747 remove_ref:
 748                 /* remove this ref */
 749
 750                 if (prev) {
 751                         prev->next = ref->next;
 752                 }
 753                 else {
 754                         *refs = ref->next;
 755                 }
 756         }
 757 }
 758
 759
 760 /* basic block creation *******************************************************/
 761
 762 static basicblock * create_block(inline_node *container,
 763                                                                  inline_node *iln,
 764                                                                  inline_node *inner,
 765                                                                  int indepth)
 766 {
 767         basicblock  *n_bptr;
 768         inline_node *outer;
 769         s4           i;
 770         s4           depth;
 771         s4           varidx;
 772         s4           newvaridx;
 773
 774         assert(container);
 775         assert(iln);
 776         assert(inner);
 777         assert(indepth >= 0);
 778
 779         n_bptr = container->inlined_basicblocks_cursor++;
 780         assert(n_bptr);
 781         assert((n_bptr - container->inlined_basicblocks) < container->cumul_basicblockcount);
 782
 783         BASICBLOCK_INIT(n_bptr, iln->m);
 784
 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 */
 790
 791         /* set the inlineinfo of the new block */
 792
 793         if (iln->inline_start_instruction)
 794                 n_bptr->inlineinfo = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
 795
 796         if (indepth > container->ctx->maxinoutdepth)
 797                 container->ctx->maxinoutdepth = indepth;
 798
 799         if (indepth) {
 800                 n_bptr->invars = DMNEW(s4, indepth);
 801
 802
 803                 for (i=0; i<indepth; ++i)
 804                         n_bptr->invars[i] = -1; /* XXX debug */
 805
 806                 /* pass-through variables enter the block */
 807
 808                 outer = inner->parent;
 809                 while (outer != NULL) {
 810                         depth = outer->n_passthroughcount;
 811
 812                         assert(depth + inner->n_selfpassthroughcount <= indepth);
 813
 814                         for (i=0; i<inner->n_selfpassthroughcount; ++i) {
 815                                 varidx = inner->n_passthroughvars[i];
 816                                 newvaridx =
 817                                         inline_new_variable_clone(container->ctx->resultjd,
 818                                                                                           outer->jd,
 819                                                                                           varidx);
 820                                 n_bptr->invars[depth + i] = newvaridx;
 821                                 outer->varmap[varidx] = newvaridx;
 822                         }
 823                         inner = outer;
 824                         outer = outer->parent;
 825                 }
 826         }
 827         else {
 828                 n_bptr->invars = NULL;
 829         }
 830
 831         /* XXX for the verifier. should not be here */
 832
 833         {
 834                 varinfo *dv;
 835
 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;
 839         }
 840
 841         return n_bptr;
 842 }
 843
 844
 845 static s4 *translate_javalocals(inline_node *iln, s4 *javalocals)
 846 {
 847         s4 *jl;
 848         s4 i, j;
 849
 850         jl = DMNEW(s4, iln->jd->maxlocals);
 851
 852         for (i=0; i<iln->jd->maxlocals; ++i) {
 853                 j = javalocals[i];
 854                 if (j > UNUSED)
 855                         j = inline_translate_variable(iln->ctx->resultjd, iln->jd, iln->varmap, j);
 856                 jl[i] = j;
 857
 858 #if 0
 859                 if (j < UNUSED) {
 860                         /* an encoded returnAddress value - must be relocated */
 861                         inline_add_blocknr_reference(iln, &(jl[i]));
 862                 }
 863 #endif
 864         }
 865
 866         return jl;
 867 }
 868
 869
 870 static basicblock * create_body_block(inline_node *iln,
 871                                                                           basicblock *o_bptr, s4 *varmap)
 872 {
 873         basicblock *n_bptr;
 874         s4 i;
 875
 876         n_bptr = create_block(iln, iln, iln,
 877                                                   o_bptr->indepth + iln->n_passthroughcount);
 878
 879         n_bptr->type = o_bptr->type;
 880         n_bptr->flags = o_bptr->flags;
 881         n_bptr->bitflags = o_bptr->bitflags;
 882
 883         /* resolve references to this block */
 884
 885         inline_resolve_block_refs(&(iln->refs), o_bptr, n_bptr, false);
 886
 887         /* translate the invars of the original block */
 888
 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,
 892                                 varmap,
 893                                 o_bptr->invars[i]);
 894         }
 895
 896         /* translate javalocals info (not for dead code) */
 897
 898         if (n_bptr->flags >= BBREACHED)
 899                 n_bptr->javalocals = translate_javalocals(iln, o_bptr->javalocals);
 900
 901         return n_bptr;
 902 }
 903
 904
 905 static basicblock * create_epilog_block(inline_node *caller, inline_node *callee, s4 *varmap)
 906 {
 907         basicblock *n_bptr;
 908         s4 retcount;
 909         s4 idx;
 910
 911         /* number of return variables */
 912
 913         retcount = (callee->n_resultlocal == -1
 914                                 && callee->m->parseddesc->returntype.type != TYPE_VOID) ? 1 : 0;
 915
 916         /* start the epilog block */
 917
 918         n_bptr = create_block(caller, caller, callee,
 919                                                   callee->n_passthroughcount + retcount);
 920
 921         /* resolve references to the return block */
 922
 923         inline_resolve_block_refs(&(callee->refs),
 924                                                           INLINE_RETURN_REFERENCE(callee),
 925                                                           n_bptr,
 926                                                           true);
 927
 928         /* return variable */
 929
 930         if (retcount) {
 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;
 935         }
 936
 937         /* set javalocals */
 938
 939         n_bptr->javalocals = DMNEW(s4, caller->jd->maxlocals);
 940         MCOPY(n_bptr->javalocals, caller->javalocals, s4, caller->jd->maxlocals);
 941
 942         /* set block flags & type */
 943
 944         n_bptr->flags = /* XXX original block flags */ BBFINISHED;
 945         n_bptr->type = BBTYPE_STD;
 946
 947         return n_bptr;
 948 }
 949
 950
 951 static void close_block(inline_node *iln, inline_node *inner, basicblock *n_bptr, s4 outdepth)
 952 {
 953         inline_node *outer;
 954         s4           i;
 955         s4           depth;
 956         s4           varidx;
 957
 958         n_bptr->outdepth = outdepth;
 959         n_bptr->outvars = DMNEW(s4, outdepth);
 960
 961         for (i=0; i<outdepth; ++i)
 962                 n_bptr->outvars[i] = 0; /* XXX debug */
 963
 964         if (outdepth > iln->ctx->maxinoutdepth)
 965                 iln->ctx->maxinoutdepth = outdepth;
 966
 967         /* pass-through variables leave the block */
 968
 969         outer = inner->parent;
 970         while (outer != NULL) {
 971                 depth = outer->n_passthroughcount;
 972
 973                 assert(depth + inner->n_selfpassthroughcount <= outdepth);
 974
 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,
 979                                                                                   outer->jd,
 980                                                                                   outer->varmap,
 981                                                                                   varidx);
 982                 }
 983                 inner = outer;
 984                 outer = outer->parent;
 985         }
 986 }
 987
 988
 989 static void close_prolog_block(inline_node *iln,
 990                                                            basicblock *n_bptr,
 991                                                            inline_node *nextcall)
 992 {
 993         /* XXX add original outvars! */
 994         close_block(iln, nextcall, n_bptr, nextcall->n_passthroughcount);
 995
 996         /* pass-through variables */
 997
 998         DOLOG( printf("closed prolog block:\n");
 999                    show_basicblock(iln->ctx->resultjd, n_bptr, SHOW_STACK); );
1000 }
1001
1002
1003 static void close_body_block(inline_node *iln,
1004                                                          basicblock *n_bptr,
1005                                                          basicblock *o_bptr,
1006                                                          s4 *varmap,
1007                                                          s4 retcount,
1008                                                          s4 retidx)
1009 {
1010         s4 i;
1011
1012         close_block(iln, iln, n_bptr, iln->n_passthroughcount + o_bptr->outdepth + retcount);
1013
1014         /* translate the outvars of the original block */
1015
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]);
1021         }
1022
1023         /* set the return variable, if any */
1024
1025         if (retcount) {
1026                 assert(retidx >= 0);
1027                 n_bptr->outvars[iln->n_passthroughcount + o_bptr->outdepth] = retidx;
1028         }
1029 }
1030
1031
1032 /* inlined code generation ****************************************************/
1033
1034 static instruction * inline_instruction(inline_node *iln,
1035                                                                                 s4 opcode,
1036                                                                                 instruction *o_iptr)
1037 {
1038         instruction *n_iptr;
1039
1040         n_iptr = (iln->inlined_iinstr_cursor++);
1041         assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1042
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;
1046
1047         return n_iptr;
1048 }
1049
1050 static void inline_generate_sync_builtin(inline_node *iln,
1051                                                                                  inline_node *callee,
1052                                                                                  instruction *o_iptr,
1053                                                                                  s4 instancevar,
1054                                                                                  functionptr func)
1055 {
1056         int          syncvar;
1057         instruction *n_ins;
1058
1059         if (callee->m->flags & ACC_STATIC) {
1060                 /* ACONST */
1061                 syncvar = inline_new_temp_variable(iln->ctx->resultjd, TYPE_ADR);
1062
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;
1067         }
1068         else {
1069                 syncvar = instancevar;
1070         }
1071
1072         assert(syncvar != UNUSED);
1073
1074         /* MONITORENTER / MONITOREXIT */
1075
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;
1081 }
1082
1083 static s4 emit_inlining_prolog(inline_node *iln,
1084                                                            inline_node *callee,
1085                                                            instruction *o_iptr,
1086                                                            s4 *varmap)
1087 {
1088         methodinfo *calleem;
1089         methoddesc *md;
1090         int i;
1091         int localindex;
1092         int type;
1093         instruction *n_ins;
1094         insinfo_inline *insinfo;
1095         s4 argvar;
1096
1097         assert(iln && callee && o_iptr);
1098
1099         calleem = callee->m;
1100         md = calleem->parseddesc;
1101
1102         /* INLINE_START instruction */
1103
1104         n_ins = inline_instruction(iln, ICMD_INLINE_START, o_iptr);
1105
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;
1113
1114         /* info about stack vars live at the INLINE_START */
1115
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]];
1122
1123         /* info about the surrounding inlining */
1124
1125         if (iln->inline_start_instruction)
1126                 insinfo->parent = iln->inline_start_instruction->sx.s23.s3.inlineinfo;
1127         else
1128                 insinfo->parent = NULL;
1129
1130         /* finish the INLINE_START instruction */
1131
1132         n_ins->sx.s23.s3.inlineinfo = insinfo;
1133         callee->inline_start_instruction = n_ins;
1134
1135         DOLOG( printf("%sprolog: ", iln->indent);
1136                    show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1137
1138         /* handle parameters for the inlined callee */
1139
1140         localindex = callee->localsoffset + md->paramslots;
1141
1142         for (i=md->paramcount-1; i>=0; --i) {
1143                 assert(iln);
1144
1145                 type = md->paramtypes[i].type;
1146
1147                 localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
1148                 assert(callee->regdata);
1149
1150                 /* translate the argument variable */
1151
1152                 argvar = varmap[o_iptr->sx.s23.s2.args[i]];
1153                 assert(argvar != UNUSED);
1154
1155                 /* remove preallocation from the argument variable */
1156
1157                 iln->ctx->resultjd->var[argvar].flags &= ~(PREALLOC | INMEMORY);
1158
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).                                */
1163
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;
1169                 }
1170
1171                 /* store argument into local variable of inlined callee */
1172
1173                 if (callee->jd->local_map[5*(localindex - callee->localsoffset) + type] != UNUSED)
1174                 {
1175                         /* this value is used in the callee */
1176
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);
1181                         }
1182                         else {
1183                                 n_ins = inline_instruction(iln, ICMD_ISTORE + type, o_iptr);
1184                                 n_ins->sx.s23.s3.javaindex = UNUSED;
1185                         }
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);
1189                 }
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.                      */
1195
1196                         n_ins = inline_instruction(iln, ICMD_NOP, o_iptr);
1197                 }
1198                 else {
1199                         /* this value is not used, pop it */
1200
1201                         n_ins = inline_instruction(iln, ICMD_POP, o_iptr);
1202                         n_ins->s1.varindex = argvar;
1203                 }
1204
1205                 DOLOG( printf("%sprolog: ", iln->indent);
1206                            show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1207         }
1208
1209         /* COPY for synchronized instance methods */
1210
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;
1215
1216                 assert(n_ins->s1.varindex != UNUSED);
1217         }
1218
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);
1223         }
1224
1225         /* INLINE_BODY instruction */
1226
1227         n_ins = inline_instruction(iln, ICMD_INLINE_BODY, callee->jd->basicblocks[0].iinstr);
1228         n_ins->sx.s23.s3.inlineinfo = insinfo;
1229
1230         return 0; /* XXX */
1231 }
1232
1233
1234 static void emit_inlining_epilog(inline_node *iln, inline_node *callee, instruction *o_iptr)
1235 {
1236         instruction *n_ins;
1237         s4          *jl;
1238
1239         assert(iln && callee && o_iptr);
1240         assert(callee->inline_start_instruction);
1241
1242         if (callee->synchronize) {
1243                 inline_generate_sync_builtin(iln, callee, o_iptr,
1244                                                                          callee->synclocal,
1245                                                                          LOCK_monitor_exit);
1246         }
1247
1248         /* INLINE_END instruction */
1249
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;
1252
1253         /* set the javalocals */
1254
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;
1258
1259         DOLOG( printf("%sepilog: ", iln->indent);
1260                    show_icmd(iln->ctx->resultjd, n_ins, false, SHOW_STACK); printf("\n"); );
1261 }
1262
1263
1264 #define TRANSLATE_VAROP(vo)  \
1265         n_iptr->vo.varindex = inline_translate_variable(jd, origjd, varmap, n_iptr->vo.varindex)
1266
1267
1268 static void inline_clone_instruction(inline_node *iln,
1269                                                                          jitdata *jd,
1270                                                                          jitdata *origjd,
1271                                                                          s4 *varmap,
1272                                                                          instruction *o_iptr,
1273                                                                          instruction *n_iptr)
1274 {
1275         icmdtable_entry_t *icmdt;
1276         builtintable_entry *bte;
1277         methoddesc *md;
1278         s4 i, j;
1279         branch_target_t *table;
1280         lookup_target_t *lookup;
1281         inline_node *scope;
1282
1283         *n_iptr = *o_iptr;
1284
1285         icmdt = &(icmd_table[o_iptr->opc]);
1286
1287         switch (icmdt->dataflow) {
1288                 case DF_0_TO_0:
1289                         break;
1290
1291                 case DF_3_TO_0:
1292                         TRANSLATE_VAROP(sx.s23.s3);
1293                 case DF_2_TO_0:
1294                         TRANSLATE_VAROP(sx.s23.s2);
1295                 case DF_1_TO_0:
1296                         TRANSLATE_VAROP(s1);
1297                         break;
1298
1299                 case DF_2_TO_1:
1300                         TRANSLATE_VAROP(sx.s23.s2);
1301                 case DF_1_TO_1:
1302                 case DF_COPY:
1303                 case DF_MOVE:
1304                         TRANSLATE_VAROP(s1);
1305                 case DF_0_TO_1:
1306                         TRANSLATE_VAROP(dst);
1307                         break;
1308
1309                 case DF_N_TO_1:
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]);
1315                         }
1316                         TRANSLATE_VAROP(dst);
1317                         break;
1318
1319                 case DF_INVOKE:
1320                         INSTRUCTION_GET_METHODDESC(n_iptr, md);
1321 clone_call:
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]);
1328                         }
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]];
1333                                 }
1334                         }
1335                         if (md->returntype.type != TYPE_VOID)
1336                                 TRANSLATE_VAROP(dst);
1337                         break;
1338
1339                 case DF_BUILTIN:
1340                         bte = n_iptr->sx.s23.s3.bte;
1341                         md = bte->md;
1342                         goto clone_call;
1343
1344                 default:
1345                         assert(0);
1346         }
1347
1348         switch (icmdt->controlflow) {
1349                 case CF_RET:
1350                         TRANSLATE_VAROP(s1); /* XXX should be handled by data-flow */
1351                         /* FALLTHROUGH */
1352                 case CF_IF:
1353                 case CF_GOTO:
1354                         inline_add_block_reference(iln, &(n_iptr->dst.block));
1355                         break;
1356
1357                 case CF_JSR:
1358                         inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.jsrtarget.block));
1359                         break;
1360
1361                 case CF_TABLE:
1362                         i = n_iptr->sx.s23.s3.tablehigh - n_iptr->sx.s23.s2.tablelow + 1 + 1 /* default */;
1363
1364                         table = DMNEW(branch_target_t, i);
1365                         MCOPY(table, o_iptr->dst.table, branch_target_t, i);
1366                         n_iptr->dst.table = table;
1367
1368                         while (--i >= 0) {
1369                                 inline_add_block_reference(iln, &(table->block));
1370                                 table++;
1371                         }
1372                         break;
1373
1374                 case CF_LOOKUP:
1375                         inline_add_block_reference(iln, &(n_iptr->sx.s23.s3.lookupdefault.block));
1376
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;
1381
1382                         while (--i >= 0) {
1383                                 inline_add_block_reference(iln, &(lookup->target.block));
1384                                 lookup++;
1385                         }
1386                         break;
1387         }
1388
1389         /* XXX move this to dataflow section? */
1390
1391         switch (n_iptr->opc) {
1392                 case ICMD_ASTORE:
1393 #if 0
1394                         if (n_iptr->flags.bits & INS_FLAG_RETADDR)
1395                                 inline_add_blocknr_reference(iln, &(n_iptr->sx.s23.s2.retaddrnr));
1396 #endif
1397                         /* FALLTHROUGH! */
1398                 case ICMD_ISTORE:
1399                 case ICMD_LSTORE:
1400                 case ICMD_FSTORE:
1401                 case ICMD_DSTORE:
1402                         stack_javalocals_store(n_iptr, iln->javalocals);
1403                         break;
1404         }
1405 }
1406
1407
1408 static void inline_rewrite_method(inline_node *iln)
1409 {
1410         basicblock *o_bptr;
1411         s4 len;
1412         instruction *o_iptr;
1413         instruction *n_iptr;
1414         inline_node *nextcall;
1415         basicblock *n_bptr;
1416         inline_block_map *bm;
1417         int i;
1418         int icount;
1419         jitdata *resultjd;
1420         jitdata *origjd;
1421         char indent[100]; /* XXX debug */
1422         s4 retcount;
1423         s4 retidx;
1424
1425         assert(iln);
1426
1427         resultjd = iln->ctx->resultjd;
1428         origjd = iln->jd;
1429
1430         n_bptr = NULL;
1431         nextcall = iln->children;
1432
1433         /* XXX debug */
1434         for (i=0; i<iln->depth; ++i)
1435                 indent[i] = '\t';
1436         indent[i] = 0;
1437         iln->indent = indent;
1438
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); );
1443
1444         /* set memory cursors */
1445
1446         iln->inlined_iinstr_cursor = iln->inlined_iinstr;
1447         iln->inlined_basicblocks_cursor = iln->inlined_basicblocks;
1448
1449         /* allocate temporary buffers */
1450
1451         iln->javalocals = DMNEW(s4, iln->jd->maxlocals);
1452
1453         /* loop over basic blocks */
1454
1455         o_bptr = iln->jd->basicblocks;
1456         for (; o_bptr; o_bptr = o_bptr->next) {
1457
1458                 if (o_bptr->flags < BBREACHED) {
1459
1460                         /* ignore the dummy end block */
1461
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);
1465                                 continue;
1466                         }
1467
1468                         DOLOG(
1469                         printf("%s* skipping old L%03d (flags=%d, type=%d, oid=%d) of ",
1470                                         indent,
1471                                         o_bptr->nr, o_bptr->flags, o_bptr->type,
1472                                         o_bptr->indepth);
1473                         method_println(iln->m);
1474                         );
1475
1476                         n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1477
1478                         /* enter it in the blockmap */
1479
1480                         inline_block_translation(iln, o_bptr, n_bptr);
1481
1482                         close_body_block(iln, n_bptr, o_bptr, iln->varmap, 0, -1);
1483                         continue;
1484                 }
1485
1486                 len = o_bptr->icount;
1487                 o_iptr = o_bptr->iinstr;
1488
1489                 DOLOG(
1490                 printf("%s* rewriting old L%03d (flags=%d, type=%d, oid=%d) of ",
1491                                 indent,
1492                                 o_bptr->nr, o_bptr->flags, o_bptr->type,
1493                                 o_bptr->indepth);
1494                 method_println(iln->m);
1495                 show_basicblock(iln->jd, o_bptr, SHOW_STACK);
1496                 );
1497
1498                 if (iln->blockbefore || o_bptr != iln->jd->basicblocks) {
1499                         /* create an inlined clone of this block */
1500
1501                         n_bptr = create_body_block(iln, o_bptr, iln->varmap);
1502                         icount = 0;
1503
1504                         /* enter it in the blockmap */
1505
1506                         inline_block_translation(iln, o_bptr, n_bptr);
1507
1508                         /* initialize the javalocals */
1509
1510                         MCOPY(iln->javalocals, n_bptr->javalocals, s4, iln->jd->maxlocals);
1511                 }
1512                 else {
1513                         s4 *jl;
1514
1515                         /* continue caller block */
1516
1517                         n_bptr = iln->inlined_basicblocks_cursor - 1;
1518                         icount = n_bptr->icount;
1519
1520                         /* translate the javalocals */
1521
1522                         jl = translate_javalocals(iln, o_bptr->javalocals);
1523                         iln->inline_start_instruction->sx.s23.s3.inlineinfo->javalocals_start = jl;
1524
1525                         MCOPY(iln->javalocals, jl, s4, iln->jd->maxlocals);
1526                 }
1527
1528                 /* iterate over the ICMDs of this block */
1529
1530                 retcount = 0;
1531                 retidx = UNUSED;
1532
1533                 while (--len >= 0) {
1534
1535                         DOLOG( fputs(indent, stdout); show_icmd(iln->jd, o_iptr, false,  SHOW_STACK);
1536                                    printf("\n") );
1537
1538                         /* handle calls that will be inlined */
1539
1540                         if (nextcall && o_iptr == nextcall->callerins) {
1541
1542                                 /* write the inlining prolog */
1543
1544                                 (void) emit_inlining_prolog(iln, nextcall, o_iptr, iln->varmap);
1545                                 icount += nextcall->prolog_instructioncount;
1546
1547                                 /* end current block, or glue blocks together */
1548
1549                                 n_bptr->icount = icount;
1550
1551                                 if (nextcall->blockbefore) {
1552                                         close_prolog_block(iln, n_bptr, nextcall);
1553                                 }
1554                                 else {
1555                                         /* XXX */
1556                                 }
1557
1558                                 /* check if the result is a local variable */
1559
1560                                 if (nextcall->m->parseddesc->returntype.type != TYPE_VOID
1561                                                 && o_iptr->dst.varindex < iln->jd->localcount)
1562                                 {
1563                                         nextcall->n_resultlocal = iln->varmap[o_iptr->dst.varindex];
1564                                 }
1565                                 else
1566                                         nextcall->n_resultlocal = -1;
1567
1568                                 /* set memory pointers in the callee */
1569
1570                                 nextcall->inlined_iinstr = iln->inlined_iinstr_cursor;
1571                                 nextcall->inlined_basicblocks = iln->inlined_basicblocks_cursor;
1572
1573                                 /* recurse */
1574
1575                                 DOLOG( printf("%sentering inline ", indent);
1576                                            show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1577
1578                                 inline_rewrite_method(nextcall);
1579
1580                                 DOLOG( printf("%sleaving inline ", indent);
1581                                            show_icmd(origjd, o_iptr, false, SHOW_STACK); printf("\n") );
1582
1583                                 /* update memory cursors */
1584
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;
1591
1592                                 /* start new block, or glue blocks together */
1593
1594                                 if (nextcall->blockafter) {
1595                                         n_bptr = create_epilog_block(iln, nextcall, iln->varmap);
1596                                         icount = 0;
1597                                 }
1598                                 else {
1599                                         n_bptr = iln->inlined_basicblocks_cursor - 1;
1600                                         icount = n_bptr->icount;
1601                                         /* XXX */
1602                                 }
1603
1604                                 /* emit inlining epilog */
1605
1606                                 emit_inlining_epilog(iln, nextcall, o_iptr);
1607                                 icount += nextcall->epilog_instructioncount;
1608
1609                                 /* proceed to next call */
1610
1611                                 nextcall = nextcall->next;
1612                         }
1613                         else {
1614                                 n_iptr = (iln->inlined_iinstr_cursor++);
1615                                 assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1616
1617                                 switch (o_iptr->opc) {
1618                                         case ICMD_RETURN:
1619                                                 if (iln->depth == 0)
1620                                                         goto default_clone;
1621                                                 goto return_tail;
1622
1623                                         case ICMD_IRETURN:
1624                                         case ICMD_ARETURN:
1625                                         case ICMD_LRETURN:
1626                                         case ICMD_FRETURN:
1627                                         case ICMD_DRETURN:
1628                                                 if (iln->depth == 0)
1629                                                         goto default_clone;
1630                                                 retcount = 1;
1631                                                 retidx = iln->varmap[o_iptr->s1.varindex];
1632                                                 if (iln->n_resultlocal != -1) {
1633                                                         /* store result in a local variable */
1634
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? */
1642
1643                                                         retcount = 0;
1644                                                         retidx = UNUSED;
1645
1646                                                         n_iptr = (iln->inlined_iinstr_cursor++);
1647                                                         assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1648                                                         icount++;
1649                                                 }
1650                                                 else if ((retidx < resultjd->localcount && iln->blockafter)
1651                                                                 || !iln->blockafter) /* XXX do we really always need the MOVE? */
1652                                                 {
1653                                                         /* local must not become outvar, insert a MOVE */
1654
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;
1660
1661                                                         n_iptr = (iln->inlined_iinstr_cursor++);
1662                                                         assert((n_iptr - iln->inlined_iinstr) < iln->cumul_instructioncount);
1663                                                         icount++;
1664                                                 }
1665 return_tail:
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));
1670                                                 }
1671                                                 else {
1672                                                         n_iptr->opc = ICMD_NOP;
1673                                                 }
1674                                                 break;
1675 #if 0
1676                                                 if (o_bptr->next == NULL || (o_bptr->next->icount==0 && o_bptr->next->next == NULL)) {
1677                                                         n_iptr->opc = ICMD_NOP;
1678                                                         break;
1679                                                 }
1680                                                 goto default_clone;
1681                                                 break;
1682 #endif
1683
1684                                         default:
1685 default_clone:
1686                                                 inline_clone_instruction(iln, resultjd, iln->jd, iln->varmap, o_iptr, n_iptr);
1687                                 }
1688
1689                                 DOLOG( fputs(indent, stdout); show_icmd(resultjd, n_iptr, false, SHOW_STACK);
1690                                            printf("\n"););
1691
1692                                 icount++;
1693                         }
1694
1695                         o_iptr++;
1696                 }
1697
1698                 /* end of basic block */
1699
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;
1703
1704                         DOLOG( printf("closed body block:\n");
1705                                    show_basicblock(resultjd, n_bptr, SHOW_STACK); );
1706                 }
1707                 else {
1708                         n_bptr->icount = icount;
1709                         assert(iln->parent);
1710                         if (retidx != UNUSED)
1711                                 iln->parent->varmap[iln->callerins->dst.varindex] = retidx;
1712                 }
1713         }
1714
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);
1718                 if (bm->iln == iln)
1719                         inline_resolve_block_refs(&(iln->refs), bm->o_block, bm->n_block, false);
1720         }
1721
1722 #if !defined(NDEBUG)
1723         if (iln->refs) {
1724                 inline_target_ref *ref;
1725                 ref = iln->refs;
1726                 while (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)) );
1730                                 assert(false);
1731                         }
1732                         ref = ref->next;
1733                 }
1734         }
1735 #endif
1736 }
1737
1738
1739 static exception_entry * inline_exception_tables(inline_node *iln,
1740                                                                                                  exception_entry *n_extable,
1741                                                                                                  exception_entry **prevextable)
1742 {
1743         inline_node *child;
1744         inline_node *scope;
1745         exception_entry *et;
1746
1747         assert(iln);
1748         assert(n_extable);
1749         assert(prevextable);
1750
1751         child = iln->children;
1752         if (child) {
1753                 do {
1754                         n_extable = inline_exception_tables(child, n_extable, prevextable);
1755                         child = child->next;
1756                 } while (child != iln->children);
1757         }
1758
1759         et = iln->jd->exceptiontable;
1760         for (; et != NULL; et = et->down) {
1761                 assert(et);
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;
1767
1768                 if (*prevextable) {
1769                         (*prevextable)->down = n_extable;
1770                 }
1771                 *prevextable = n_extable;
1772
1773                 n_extable++;
1774         }
1775
1776         if (iln->handler_monitorexit) {
1777                 exception_entry **activehandlers;
1778
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 */
1784
1785                 if (*prevextable) {
1786                         (*prevextable)->down = n_extable;
1787                 }
1788                 *prevextable = n_extable;
1789
1790                 n_extable++;
1791
1792                 /* We have to protect the created handler with the same handlers */
1793                 /* that protect the method body itself.                          */
1794
1795                 for (scope = iln; scope->parent != NULL; scope = scope->parent) {
1796
1797                         activehandlers = scope->o_handlers;
1798                         assert(activehandlers);
1799
1800                         while (*activehandlers) {
1801
1802                                 assert(scope->parent);
1803
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,
1809                                                                                                                 scope->parent);
1810                                 n_extable->catchtype = (*activehandlers)->catchtype;
1811
1812                                 if (*prevextable) {
1813                                         (*prevextable)->down = n_extable;
1814                                 }
1815                                 *prevextable = n_extable;
1816
1817                                 n_extable++;
1818                                 activehandlers++;
1819                         }
1820                 }
1821         }
1822
1823         return n_extable;
1824 }
1825
1826
1827 static void inline_locals(inline_node *iln)
1828 {
1829         inline_node *child;
1830
1831         assert(iln);
1832
1833         iln->varmap = create_variable_map(iln);
1834
1835         child = iln->children;
1836         if (child) {
1837                 do {
1838                         inline_locals(child);
1839                         child = child->next;
1840                 } while (child != iln->children);
1841         }
1842
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;
1849 }
1850
1851
1852 static void inline_interface_variables(inline_node *iln)
1853 {
1854         basicblock *bptr;
1855         jitdata *resultjd;
1856         s4 i;
1857         varinfo *v;
1858
1859         resultjd = iln->ctx->resultjd;
1860
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;
1864
1865         for (bptr = resultjd->basicblocks; bptr != NULL; bptr = bptr->next) {
1866                 assert(bptr->indepth  <= iln->ctx->maxinoutdepth);
1867                 assert(bptr->outdepth <= iln->ctx->maxinoutdepth);
1868
1869                 for (i=0; i<bptr->indepth; ++i) {
1870                         v = &(resultjd->var[bptr->invars[i]]);
1871                         v->flags |= INOUT;
1872                         if (v->type == TYPE_RET)
1873                                 v->flags |= PREALLOC;
1874                         else
1875                                 v->flags &= ~PREALLOC;
1876                         v->flags &= ~INMEMORY;
1877                         assert(bptr->invars[i] >= resultjd->localcount);
1878
1879                         if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1880                                 resultjd->interface_map[5*i + v->type].flags = v->flags;
1881                         }
1882                         else {
1883                                 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1884                         }
1885                 }
1886
1887                 for (i=0; i<bptr->outdepth; ++i) {
1888                         v = &(resultjd->var[bptr->outvars[i]]);
1889                         v->flags |= INOUT;
1890                         if (v->type == TYPE_RET)
1891                                 v->flags |= PREALLOC;
1892                         else
1893                                 v->flags &= ~PREALLOC;
1894                         v->flags &= ~INMEMORY;
1895                         assert(bptr->outvars[i] >= resultjd->localcount);
1896
1897                         if (resultjd->interface_map[5*i + v->type].flags == UNUSED) {
1898                                 resultjd->interface_map[5*i + v->type].flags = v->flags;
1899                         }
1900                         else {
1901                                 resultjd->interface_map[5*i + v->type].flags |= v->flags;
1902                         }
1903                 }
1904         }
1905 }
1906
1907
1908 static void inline_write_exception_handlers(inline_node *master, inline_node *iln)
1909 {
1910         basicblock *n_bptr;
1911         instruction *n_ins;
1912         inline_node *child;
1913         builtintable_entry *bte;
1914         s4 exvar;
1915         s4 syncvar;
1916         s4 i;
1917
1918         child = iln->children;
1919         if (child) {
1920                 do {
1921                         inline_write_exception_handlers(master, child);
1922                         child = child->next;
1923                 } while (child != iln->children);
1924         }
1925
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;
1932
1933                 exvar = inline_new_variable(master->ctx->resultjd, TYPE_ADR, 0);
1934                 n_bptr->invars[iln->n_passthroughcount] = exvar;
1935
1936                 iln->handler_monitorexit = n_bptr;
1937
1938                 /* ACONST / ALOAD */
1939
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;
1945                 }
1946                 else {
1947                         n_ins->opc = ICMD_ALOAD;
1948                         n_ins->s1.varindex = iln->synclocal;
1949                         assert(n_ins->s1.varindex != UNUSED);
1950                 }
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;
1954                 n_ins->line = 0;
1955
1956                 /* MONITOREXIT */
1957
1958                 bte = builtintable_get_internal(LOCK_monitor_exit);
1959
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];
1967                 }
1968                 n_ins->sx.s23.s3.bte = bte;
1969                 n_ins->line = 0;
1970
1971                 /* ATHROW */
1972
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;
1977                 n_ins->line = 0;
1978
1979                 /* close basic block */
1980
1981                 close_block(iln, iln, n_bptr, iln->n_passthroughcount);
1982                 n_bptr->icount = 3;
1983         }
1984 }
1985
1986
1987 /* second pass driver *********************************************************/
1988
1989 static bool inline_transform(inline_node *iln, jitdata *jd)
1990 {
1991         instruction *n_ins;
1992         basicblock *n_bb;
1993         basicblock *n_bptr;
1994         exception_entry *n_ext;
1995         exception_entry *prevext;
1996         codegendata *n_cd;
1997         jitdata *n_jd;
1998         s4 i;
1999 #if defined(INLINE_VERIFY_RESULT)
2000         static int debug_verify_inlined_code = 1;
2001 #endif
2002 #if defined(ENABLE_INLINING_DEBUG)
2003         static int debug_counter = 0;
2004 #endif
2005
2006         DOLOG( dump_inline_tree(iln, 0); );
2007
2008         assert(iln && jd);
2009
2010         n_ins = DMNEW(instruction, iln->cumul_instructioncount);
2011         MZERO(n_ins, instruction, iln->cumul_instructioncount);
2012         iln->inlined_iinstr = n_ins;
2013
2014         n_bb = DMNEW(basicblock, iln->cumul_basicblockcount);
2015         MZERO(n_bb, basicblock, iln->cumul_basicblockcount);
2016         iln->inlined_basicblocks = n_bb;
2017
2018         iln->ctx->blockmap = DMNEW(inline_block_map, iln->cumul_blockmapcount);
2019
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;
2024
2025         reg_setup(n_jd);
2026
2027         /* create the local_map */
2028
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;
2032
2033         /* create / coalesce local variables */
2034
2035         n_jd->varcount = 0;
2036         n_jd->vartop = 0;
2037         n_jd->var = NULL;
2038
2039         inline_locals(iln);
2040
2041         n_jd->localcount = n_jd->vartop;
2042
2043         /* extra variables for verification (debugging) */
2044
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) {
2049                         /* XXX why? */
2050                         n_jd->var = DMREALLOC(n_jd->var, varinfo, n_jd->varcount, n_jd->vartop);
2051                         n_jd->varcount = n_jd->vartop;
2052                 }
2053         }
2054 #endif /* defined(INLINE_VERIFY_RESULT) */
2055
2056         /* write inlined code */
2057
2058         inline_rewrite_method(iln);
2059
2060         /* create exception handlers */
2061
2062         inline_write_exception_handlers(iln, iln);
2063
2064         /* write the dummy end block */
2065
2066         n_bptr = create_block(iln, iln, iln, 0);
2067         n_bptr->flags = BBUNDEF;
2068         n_bptr->type = BBTYPE_STD;
2069
2070         /* store created code in jitdata */
2071
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;
2076
2077         /* link the basic blocks (dummy end block is not counted) */
2078
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]);
2082         if (i)
2083                 n_jd->basicblocks[i-1].next = NULL;
2084
2085         /* check basicblock numbers */
2086
2087 #if !defined(NDEBUG)
2088         jit_check_basicblock_numbers(n_jd);
2089 #endif
2090
2091         /* create the exception table */
2092
2093         if (iln->cumul_exceptiontablelength) {
2094                 exception_entry *tableend;
2095
2096                 n_ext = DMNEW(exception_entry, iln->cumul_exceptiontablelength);
2097                 prevext = NULL;
2098                 tableend = inline_exception_tables(iln, n_ext, &prevext);
2099                 assert(tableend == n_ext + iln->cumul_exceptiontablelength);
2100                 if (prevext)
2101                         prevext->down = NULL;
2102
2103                 n_jd->exceptiontablelength = iln->cumul_exceptiontablelength;
2104                 n_jd->exceptiontable = n_ext;
2105         }
2106         else {
2107                 n_ext = NULL;
2108         }
2109
2110         /*******************************************************************************/
2111
2112         n_cd = n_jd->cd;
2113         memcpy(n_cd, jd->cd, sizeof(codegendata));
2114
2115         n_cd->method = NULL; /* XXX */
2116         n_jd->maxlocals = iln->cumul_maxlocals;
2117         n_jd->maxinterfaces = iln->ctx->maxinoutdepth;
2118
2119         inline_post_process(n_jd);
2120
2121         inline_interface_variables(iln);
2122
2123         /* for debugging, verify the inlined result */
2124
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") );
2132                         return false;
2133                 }
2134                 else {
2135                         DOLOG( printf("VERIFICATION PASSED.\n") );
2136                 }
2137                 debug_verify_inlined_code = 1;
2138         }
2139 #endif /* defined(INLINE_VERIFY_RESULT) */
2140
2141         /* we need bigger free memory stacks (XXX these should not be allocated in reg_setup) */
2142
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 */;
2146 #endif
2147
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))
2151         {
2152            if (debug_counter <= opt_inline_debug_end_counter)
2153 #endif /* defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG) */
2154            {
2155                         /* install the inlined result */
2156
2157                         *jd->code = *n_jd->code;
2158                         n_jd->code = jd->code;
2159                         *jd = *n_jd;
2160
2161                         /* statistics and logging */
2162
2163 #if !defined(NDEBUG)
2164                         inline_stat_roots++;
2165
2166                         DOLOG(
2167                         printf("==== %d.INLINE ==================================================================\n",
2168                                 debug_counter);
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");
2174                         fflush(stdout);
2175                         );
2176 #endif
2177            }
2178
2179 #if defined(ENABLE_INLINING_DEBUG) || !defined(NDEBUG)
2180                 debug_counter++;
2181         }
2182 #endif
2183         return true;
2184 }
2185
2186
2187 /******************************************************************************/
2188 /* FIRST PASS: build inlining tree                                            */
2189 /******************************************************************************/
2190
2191
2192 /* inline_pre_parse_heuristics *************************************************
2193
2194    Perform heuristic checks whether a call site should be inlined.
2195    These checks are evaluated before the callee has been parsed and analysed.
2196
2197    IN:
2198        caller...........inlining node of the caller
2199            callee...........the called method
2200            site.............information on the call site
2201
2202    RETURN VALUE:
2203        true........consider for inlining
2204            false.......don't inline
2205
2206 *******************************************************************************/
2207
2208 static bool inline_pre_parse_heuristics(const inline_node *caller,
2209                                                                                 const methodinfo *callee,
2210                                                                                 inline_site *site)
2211 {
2212 #if defined(INLINE_MAX_DEPTH)
2213         if (caller->depth >= INLINE_MAX_DEPTH)
2214                 return false;
2215 #endif
2216
2217         return true;
2218 }
2219
2220
2221 /* inline_post_parse_heuristics ************************************************
2222
2223    Perform heuristic checks whether a call site should be inlined.
2224    These checks are evaluated after the callee has been parsed and analysed.
2225
2226    IN:
2227        caller...........inlining node of the caller (const)
2228            callee...........the called method (const)
2229
2230    RETURN VALUE:
2231            true........consider for inlining
2232            false.......don't inline
2233
2234 *******************************************************************************/
2235
2236 static bool inline_post_parse_heuristics(const inline_node *caller,
2237                                                                                  const inline_node *callee)
2238 {
2239         return true;
2240 }
2241
2242
2243 /* inline_afterwards_heuristics ************************************************
2244
2245    Perform heuristic checks whether a call site should be inlined.
2246    These checks are evaluated after the inlining plan for the callee has
2247    been made.
2248
2249    IN:
2250        caller...........inlining node of the caller (const)
2251            callee...........the called method (const)
2252
2253    RETURN VALUE:
2254            true........consider for inlining
2255            false.......don't inline
2256
2257 *******************************************************************************/
2258
2259 static bool inline_afterwards_heuristics(const inline_node *caller,
2260                                                                                  const inline_node *callee)
2261 {
2262         if (0
2263 #if defined(INLINE_MAX_BLOCK_EXPANSION)
2264                 || (caller->cumul_basicblockcount + callee->cumul_basicblockcount
2265                         > INLINE_MAX_BLOCK_EXPANSION*caller->ctx->master->jd->basicblockcount)
2266 #endif
2267 #if defined(INLINE_MAX_ICMD_EXPANSION)
2268                 || (caller->cumul_instructioncount + callee->cumul_instructioncount
2269                         > INLINE_MAX_ICMD_EXPANSION*caller->ctx->master->jd->instructioncount)
2270 #endif
2271            )
2272         {
2273                 return false;
2274         }
2275
2276         return true;
2277 }
2278
2279
2280 /* inline_is_monomorphic *******************************************************
2281
2282    Check if the given call site can be proven to be monomorphic.
2283
2284    IN:
2285            callee...........the called method
2286            call.............the invocation instruction
2287
2288    OUT:
2289        site->speculative.....flags whether the inlining is speculative
2290                                  (only defined if return value is true)
2291
2292    RETURN VALUE:
2293        true if the call site is (currently) monomorphic,
2294            false if not or unknown
2295
2296 *******************************************************************************/
2297
2298 static bool inline_is_monomorphic(const methodinfo *callee,
2299                                                                   const instruction *call,
2300                                                                   inline_site *site)
2301 {
2302         if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)
2303                                 || call->opc == ICMD_INVOKESPECIAL))
2304         {
2305                 site->speculative = false;
2306                 return true;
2307         }
2308
2309         /* XXX search single implementation for abstract monomorphics */
2310
2311         if ((callee->flags & (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED
2312                                         | ACC_ABSTRACT))
2313                         == (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED))
2314         {
2315                 if (1) {
2316                         DOLOG( printf("SPECULATIVE INLINE: "); method_println((methodinfo*)callee); );
2317                         site->speculative = true;
2318
2319                         return true;
2320                 }
2321         }
2322
2323         /* possibly polymorphic call site */
2324
2325         return false;
2326 }
2327
2328
2329 /* inline_can_inline ***********************************************************
2330
2331    Check if inlining of the given call site is possible.
2332
2333    IN:
2334        caller...........inlining node of the caller
2335            callee...........the called method
2336            call.............the invocation instruction
2337
2338    OUT:
2339        site->speculative.....flags whether the inlining is speculative
2340                                  (only defined if return value is true)
2341
2342    RETURN VALUE:
2343        true if inlining is possible, false if not
2344
2345 *******************************************************************************/
2346
2347 static bool inline_can_inline(const inline_node *caller,
2348                                                           const methodinfo *callee,
2349                                                           const instruction *call,
2350                                                           inline_site *site)
2351 {
2352         const inline_node *active;
2353
2354         /* cannot inline native methods */
2355
2356         if (callee->flags & ACC_NATIVE)
2357                 return false;
2358
2359         /* cannot inline possibly polymorphic calls */
2360
2361         if (!inline_is_monomorphic(callee, call, site))
2362                 return false;
2363
2364         /* cannot inline recursive calls */
2365
2366         for (active = caller; active; active = active->parent) {
2367                 if (callee == active->m) {
2368                         DOLOG( printf("RECURSIVE!\n") );
2369                         return false;
2370                 }
2371         }
2372
2373         /* inlining is possible */
2374
2375         return true;
2376 }
2377
2378
2379 /* inline_create_callee_node ***************************************************
2380
2381    Create an inlining node for the given callee.
2382
2383    IN:
2384            caller...........inlining node of the caller (const)
2385            callee...........the called method
2386
2387    RETURN VALUE:
2388        the new inlining node
2389
2390 *******************************************************************************/
2391
2392 static inline_node * inline_create_callee_node(const inline_node *caller,
2393                                                                                            methodinfo *callee)
2394 {
2395         inline_node *cn;              /* the callee inline_node */
2396
2397         cn = DNEW(inline_node);
2398         MZERO(cn, inline_node, 1);
2399
2400         cn->depth = caller->depth + 1;
2401         cn->ctx = caller->ctx;
2402         cn->m = callee;
2403         cn->synchronize = (callee->flags & ACC_SYNCHRONIZED);
2404         cn->isstatic = (callee->flags & ACC_STATIC);
2405
2406         return cn;
2407 }
2408
2409
2410 /* inline_set_callee_properties ************************************************
2411
2412    Set properties of the inlined call site.
2413
2414    IN:
2415        caller...........inlining node of the caller (const)
2416            cn...............the called method
2417            site.............info about the call site (const)
2418
2419    OUT:
2420        *cn..............has the properties set
2421
2422 *******************************************************************************/
2423
2424 static void inline_set_callee_properties(const inline_node *caller,
2425                                                                                  inline_node *cn,
2426                                                                                  const inline_site *site)
2427 {
2428         s4           argi;
2429         s4           i, j;
2430         basicblock  *bptr;
2431
2432         /* set info about the call site */
2433
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;
2439
2440         /* determine if we need basic block boundaries before/after */
2441
2442         cn->blockbefore = false;
2443         cn->blockafter = false;
2444
2445         if (cn->jd->branchtoentry)
2446                 cn->blockbefore = true;
2447
2448         if (cn->jd->branchtoend)
2449                 cn->blockafter = true;
2450
2451         if (cn->jd->returncount > 1)
2452                 cn->blockafter = true;
2453
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)
2456                 ;
2457
2458         if (cn->jd->returnblock != bptr)
2459                 cn->blockafter = true;
2460
2461         /* info about the callee */
2462
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;
2467
2468         /* we need a CHECKNULL for instance methods, except for <init> */
2469
2470         if (!cn->isstatic && cn->m->name != utf_init)
2471                 cn->prolog_instructioncount += 1;
2472
2473         /* deal with synchronized callees */
2474
2475         if (cn->synchronize) {
2476                 methoddesc         *md;
2477                 builtintable_entry *bte;
2478
2479                 /* we need basic block boundaries because of the handler */
2480
2481                 cn->blockbefore = true;
2482                 cn->blockafter = true;
2483
2484                 /* for synchronized static methods                 */
2485                 /* we need an ACONST, MONITORENTER in the prolog   */
2486                 /* and ACONST, MONITOREXIT in the epilog           */
2487
2488                 /* for synchronized instance methods               */
2489                 /* we need an COPY, MONITORENTER in the prolog     */
2490                 /* and MONITOREXIT in the epilog                   */
2491
2492                 if (cn->isstatic) {
2493                         cn->prolog_instructioncount += 2;
2494                         cn->epilog_instructioncount += 2;
2495                 }
2496                 else {
2497                         cn->prolog_instructioncount += 2;
2498                         cn->epilog_instructioncount += 1;
2499                         cn->localsoffset += 1;
2500                 }
2501
2502                 /* and exception handler */
2503                 /* ALOAD, builtin_monitorexit, ATHROW */
2504
2505                 cn->extra_instructioncount += 3;
2506
2507                 /* exception table entries */
2508
2509                 cn->extra_exceptiontablelength = 1 + cn->n_handlercount;
2510
2511                 /* add exception handler block */
2512
2513                 cn->cumul_basicblockcount_root++;
2514
2515                 /* we must call the builtins */
2516
2517                 bte = builtintable_get_internal(LOCK_monitor_enter);
2518                 md = bte->md;
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;
2523
2524                 bte = builtintable_get_internal(LOCK_monitor_exit);
2525                 md = bte->md;
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;
2530         }
2531
2532         /* determine pass-through variables */
2533
2534         i = site->iptr->s1.argcount - cn->m->parseddesc->paramcount; /* max # of pass-though vars */
2535
2536         cn->n_passthroughvars = DMNEW(s4, i);
2537         j = 0;
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;
2542                         j++;
2543                 }
2544                 else {
2545                         DOLOG( printf("PASSING THROUGH LOCAL VARIABLE %d\n", idx); );
2546                 }
2547         }
2548         assert(j <= i);
2549         cn->n_selfpassthroughcount = j;
2550         cn->n_passthroughcount = caller->n_passthroughcount + cn->n_selfpassthroughcount;
2551 }
2552
2553
2554 /* inline_cumulate_counters ****************************************************
2555
2556    Cumulate counters after a node has been decided to become inlined.
2557
2558    IN:
2559        caller...........inlining node of the caller
2560            callee...........inlining node of the callee (const)
2561
2562    OUT:
2563        *caller..........gets cumulated values added
2564
2565 *******************************************************************************/
2566
2567 static void inline_cumulate_counters(inline_node *caller,
2568                                                                          const inline_node *cn)
2569 {
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*/;
2574
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;
2580
2581         if (cn->cumul_maxlocals > caller->cumul_maxlocals)
2582                 caller->cumul_maxlocals = cn->cumul_maxlocals;
2583
2584         /* XXX extra block after inlined call */
2585         if (cn->blockafter) {
2586                 caller->cumul_basicblockcount += 1;
2587                 caller->cumul_blockmapcount += 1;
2588         }
2589 }
2590
2591
2592 /* inline_analyse_callee *******************************************************
2593
2594    Analyse an inlining candidate callee.
2595
2596    IN:
2597        caller...........inlining node of the caller
2598            callee...........the called method
2599            site.............info about the call site
2600
2601    OUT:
2602        site->inlined....true if the callee has been selected for inlining
2603
2604    RETURN VALUE:
2605        the inline node of the callee, or
2606        NULL if an error has occurred (don't use the inlining plan in this case)
2607
2608 *******************************************************************************/
2609
2610 static inline_node * inline_analyse_callee(inline_node *caller,
2611                                                                                    methodinfo *callee,
2612                                                                                    inline_site *site)
2613 {
2614         inline_node *cn;              /* the callee inline_node */
2615
2616         /* create an inline tree node */
2617
2618         cn = inline_create_callee_node(caller, callee);
2619
2620         /* get the intermediate representation of the callee */
2621
2622         if (!inline_jit_compile(cn))
2623                 return NULL;
2624
2625         /* evaluate heuristics after parsing the callee */
2626
2627         if (!inline_post_parse_heuristics(caller, cn))
2628                 return cn;
2629
2630         /* the call site will be inlined */
2631
2632         site->inlined = true;
2633
2634         /* set info about the call site */
2635
2636         inline_set_callee_properties(caller, cn, site);
2637
2638         /* insert the node into the inline tree */
2639
2640         inline_insert_inline_node(caller, cn);
2641
2642         /* analyse recursively */
2643
2644         if (!inline_analyse_code(cn))
2645                 return NULL;
2646
2647         if (!inline_afterwards_heuristics(caller, cn)) {
2648 #if defined(INLINE_CANCEL_ON_THRESHOLD)
2649                 return NULL;
2650 #else
2651                 inline_remove_inline_node(caller, cn);
2652                 caller->ctx->stopped = true;
2653                 site->inlined = false;
2654                 return cn;
2655 #endif
2656         }
2657
2658         /* cumulate counters */
2659
2660 #if !defined(INLINE_KNAPSACK)
2661         inline_cumulate_counters(caller, cn);
2662 #endif
2663
2664         return cn;
2665 }
2666
2667
2668 /* inline_process_candidate ****************************************************
2669
2670    Process a selected inlining candidate.
2671
2672    IN:
2673        cand.............the candidate
2674
2675    RETURN VALUE:
2676        true........everything ok
2677            false.......an error has occurred, don't use the plan
2678
2679 *******************************************************************************/
2680
2681 static bool inline_process_candidate(inline_candidate *cand)
2682 {
2683         inline_node *cn;
2684
2685         cn = inline_analyse_callee(cand->caller,
2686                                                            cand->callee,
2687                                                            &(cand->site));
2688
2689         if (!cn)
2690                 return false;
2691
2692         if (!cand->site.inlined)
2693                 return true;
2694
2695         /* store assumptions */
2696
2697         if (cand->site.speculative)
2698                 method_add_assumption_monomorphic(cand->callee, cand->caller->ctx->master->m);
2699
2700         return true;
2701 }
2702
2703
2704 /* inline_analyse_code *********************************************************
2705
2706    Analyse the intermediate code of the given inlining node.
2707
2708    IN:
2709        iln..............the inlining node
2710
2711    OUT:
2712        *iln.............the inlining plan
2713
2714    RETURN VALUE:
2715        true........everything ok
2716            false.......an error has occurred, don't use the plan
2717
2718 *******************************************************************************/
2719
2720 static bool inline_analyse_code(inline_node *iln)
2721 {
2722         methodinfo *m;
2723         basicblock *bptr;
2724         s4 len;
2725         instruction *iptr;
2726         methodinfo *callee;
2727         exception_entry **handlers;
2728         exception_entry *ex;
2729         s4 nhandlers;
2730         s4 blockendpc;
2731         jitdata *mjd;
2732         inline_site site;
2733
2734         assert(iln);
2735
2736         m = iln->m;
2737         mjd = iln->jd;
2738
2739         /* initialize cumulative counters */
2740
2741         iln->cumul_maxlocals = iln->localsoffset + m->maxlocals;
2742         iln->cumul_exceptiontablelength += mjd->exceptiontablelength;
2743
2744         /* iterate over basic blocks */
2745
2746         blockendpc = 0;
2747
2748         for (bptr = mjd->basicblocks; bptr; bptr = bptr->next) {
2749
2750                 /* count the block */
2751                 /* ignore dummy end blocks (but count them for the blockmap) */
2752
2753                 iln->cumul_blockmapcount++;
2754                 if ((bptr != mjd->basicblocks || iln->blockbefore)
2755                                 &&
2756                         (bptr->icount > 0 || bptr->next != NULL))
2757                         iln->cumul_basicblockcount++;
2758
2759                 /* skip dead code */
2760
2761                 if (bptr->flags < BBREACHED)
2762                         continue;
2763
2764                 /* allocate the buffer of active exception handlers */
2765                 /* XXX this wastes some memory, but probably it does not matter */
2766
2767                 handlers = DMNEW(exception_entry*, mjd->exceptiontablelength + 1);
2768
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          */
2772                 nhandlers = 0;
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;
2776                         }
2777                 }
2778                 handlers[nhandlers] = NULL;
2779
2780                 len = bptr->icount;
2781                 iptr = bptr->iinstr;
2782
2783                 blockendpc += len;
2784                 iln->cumul_instructioncount += len;
2785
2786                 /* iterate over the instructions of the block */
2787
2788                 for (; --len >= 0; ++iptr) {
2789
2790                         switch (iptr->opc) {
2791                                 case ICMD_INVOKEVIRTUAL:
2792                                 case ICMD_INVOKESPECIAL:
2793                                 case ICMD_INVOKESTATIC:
2794                                 case ICMD_INVOKEINTERFACE:
2795
2796                                         if (!INSTRUCTION_IS_UNRESOLVED(iptr) && !iln->ctx->stopped) {
2797                                                 callee = iptr->sx.s23.s3.fmiref->p.method;
2798
2799                                                 if (inline_can_inline(iln, callee, iptr, &site)) {
2800                                                         site.inlined = false;
2801                                                         site.bptr = bptr;
2802                                                         site.iptr = iptr;
2803                                                         site.pc = blockendpc - len - 1;
2804                                                         site.handlers = handlers;
2805                                                         site.nhandlers = nhandlers;
2806
2807                                                         if (inline_pre_parse_heuristics(iln, callee, &site)) {
2808 #if defined(INLINE_KNAPSACK)
2809                                                                 inline_add_candidate(iln->ctx, iln, callee, &site);
2810 #else
2811                                                                 inline_candidate cand;
2812                                                                 cand.caller = iln;
2813                                                                 cand.callee = callee;
2814                                                                 cand.site   = site;
2815
2816                                                                 if (!inline_process_candidate(&cand))
2817                                                                         return false;
2818 #endif
2819                                                         }
2820                                                 }
2821                                         }
2822                                         break;
2823
2824                                 case ICMD_RETURN:
2825                                 case ICMD_IRETURN:
2826                                 case ICMD_ARETURN:
2827                                 case ICMD_LRETURN:
2828                                 case ICMD_FRETURN:
2829                                 case ICMD_DRETURN:
2830                                         /* extra ICMD_MOVE may be necessary */
2831                                         iln->cumul_instructioncount++;
2832                                         break;
2833                         }
2834                 }
2835
2836                 /* end of basic block */
2837         }
2838
2839         return true;
2840 }
2841
2842
2843 static void inline_cumulate_counters_recursive(inline_node *iln)
2844 {
2845         inline_node *child;
2846
2847         child = iln->children;
2848         if (child) {
2849                 do {
2850                         inline_cumulate_counters_recursive(child);
2851                         inline_cumulate_counters(iln, child);
2852                         child = child->next;
2853                 } while (child != iln->children);
2854         }
2855 }
2856
2857
2858 /* inline_make_inlining_plan ***************************************************
2859
2860    Make an inlining plan for the given root node
2861
2862    IN:
2863        iln..............the root node
2864
2865    OUT:
2866        *iln.............the inlining plan
2867
2868    RETURN VALUE:
2869        true........everything ok
2870            false.......an error has occurred, don't use the plan
2871
2872 *******************************************************************************/
2873
2874 static bool inline_make_inlining_plan(inline_node *iln)
2875 {
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
2881 #endif
2882 #if defined(INLINE_WEIGHT_BUDGET)
2883         double budget = INLINE_WEIGHT_BUDGET;
2884 #   define BUDGETMEMBER weight
2885 #endif
2886
2887         inline_analyse_code(iln);
2888
2889         DOLOG( printf("candidates in "); method_println(iln->m);
2890                    inline_candidates_println(iln->ctx); );
2891
2892         while ((cand = inline_pick_best_candidate(iln->ctx)) != NULL)
2893         {
2894                 if (cand->BUDGETMEMBER <= budget) {
2895                         DOLOG( printf("    picking: "); inline_candidate_println(cand); );
2896
2897                         if (!inline_process_candidate(cand))
2898                                 return false;
2899
2900 #if !defined(INLINE_ADD_NEGATIVE_TO_BUDGET)
2901                         if (cand->BUDGETMEMBER > 0)
2902 #endif
2903                                 budget -= cand->BUDGETMEMBER;
2904                 }
2905         }
2906
2907         inline_cumulate_counters_recursive(iln);
2908
2909         return true;
2910 #else
2911         return inline_analyse_code(iln);
2912 #endif
2913 }
2914
2915
2916 /* statistics *****************************************************************/
2917
2918 #if defined(INLINE_STATISTICS)
2919 static void inline_gather_statistics_recursive(inline_node *iln)
2920 {
2921         inline_node *child;
2922
2923         inline_stat_inlined_nodes++;
2924
2925         if (iln->depth > inline_stat_max_depth)
2926                 inline_stat_max_depth++;
2927
2928         child = iln->children;
2929         if (child) {
2930                 do {
2931                         inline_gather_statistics_recursive(child);
2932                         child = child->next;
2933                 } while (child != iln->children);
2934         }
2935 }
2936 #endif /* defined(INLINE_STATISTICS) */
2937
2938
2939 #if defined(INLINE_STATISTICS)
2940 static void inline_gather_statistics(inline_node *iln)
2941 {
2942         inline_stat_roots_transformed++;
2943
2944         inline_gather_statistics_recursive(iln);
2945 }
2946 #endif /* defined(INLINE_STATISTICS) */
2947
2948
2949 /* post processing ************************************************************/
2950
2951 #define POSTPROCESS_SRC(varindex)  live[varindex]--
2952 #define POSTPROCESS_DST(varindex)  live[varindex]++
2953
2954 #define POSTPROCESS_SRCOP(s)  POSTPROCESS_SRC(iptr->s.varindex)
2955 #define POSTPROCESS_DSTOP(d)  POSTPROCESS_DST(iptr->d.varindex)
2956
2957 #define MARKSAVED(varindex)  jd->var[varindex].flags |= SAVEDVAR
2958
2959 #define MARK_ALL_SAVED                                               \
2960     do {                                                             \
2961         for (i=0; i<jd->vartop; ++i)                                 \
2962             if (live[i])                                             \
2963                 MARKSAVED(i);                                        \
2964     } while (0)
2965
2966 static void inline_post_process(jitdata *jd)
2967 {
2968         basicblock *bptr;
2969         instruction *iptr;
2970         instruction *iend;
2971         s4 i;
2972         icmdtable_entry_t *icmdt;
2973         s4 *live;
2974         methoddesc *md;
2975         builtintable_entry *bte;
2976
2977         /* reset the SAVEDVAR flag of all variables */
2978
2979         for (i=0; i<jd->vartop; ++i)
2980                 jd->var[i].flags &= ~SAVEDVAR;
2981
2982         /* allocate the life counters */
2983
2984         live = DMNEW(s4, jd->vartop);
2985         MZERO(live, s4, jd->vartop);
2986
2987         /* iterate over all basic blocks */
2988
2989         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
2990                 if (bptr->flags < BBREACHED)
2991                         continue;
2992
2993                 /* make invars live */
2994
2995                 for (i=0; i<bptr->indepth; ++i)
2996                         POSTPROCESS_DST(bptr->invars[i]);
2997
2998                 iptr = bptr->iinstr;
2999                 iend = iptr + bptr->icount;
3000
3001                 for (; iptr < iend; ++iptr) {
3002
3003                         icmdt = &(icmd_table[iptr->opc]);
3004
3005                         switch (icmdt->dataflow) {
3006                                 case DF_3_TO_0:
3007                                         POSTPROCESS_SRCOP(sx.s23.s3);
3008                                 case DF_2_TO_0:
3009                                         POSTPROCESS_SRCOP(sx.s23.s2);
3010                                 case DF_1_TO_0:
3011                                         POSTPROCESS_SRCOP(s1);
3012                                 case DF_0_TO_0:
3013                                         if (icmdt->flags & ICMDTABLE_CALLS) {
3014                                                 jd->isleafmethod = false;
3015                                                 MARK_ALL_SAVED;
3016                                         }
3017                                         break;
3018
3019                                 case DF_2_TO_1:
3020                                         POSTPROCESS_SRCOP(sx.s23.s2);
3021                                 case DF_1_TO_1:
3022                                 case DF_MOVE:
3023                                         POSTPROCESS_SRCOP(s1);
3024                                 case DF_0_TO_1:
3025                                         if (icmdt->flags & ICMDTABLE_CALLS) {
3026                                                 jd->isleafmethod = false;
3027                                                 MARK_ALL_SAVED;
3028                                         }
3029                                 case DF_COPY:
3030                                         POSTPROCESS_DSTOP(dst);
3031                                         break;
3032
3033                                 case DF_N_TO_1:
3034                                         for (i=0; i<iptr->s1.argcount; ++i) {
3035                                                 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3036                                         }
3037                                         if (icmdt->flags & ICMDTABLE_CALLS) {
3038                                                 jd->isleafmethod = false;
3039                                                 MARK_ALL_SAVED;
3040                                         }
3041                                         POSTPROCESS_DSTOP(dst);
3042                                         break;
3043
3044                                 case DF_INVOKE:
3045                                         INSTRUCTION_GET_METHODDESC(iptr, md);
3046                 post_process_call:
3047                                         jd->isleafmethod = false;
3048                                         for (i=0; i<md->paramcount; ++i) {
3049                                                 POSTPROCESS_SRC(iptr->sx.s23.s2.args[i]);
3050                                         }
3051                                         for (; i<iptr->s1.argcount; ++i) {
3052                                                 MARKSAVED(iptr->sx.s23.s2.args[i]);
3053                                         }
3054                                         if (md->returntype.type != TYPE_VOID)
3055                                                 POSTPROCESS_DSTOP(dst);
3056                                         break;
3057
3058                                 case DF_BUILTIN:
3059                                         bte = iptr->sx.s23.s3.bte;
3060                                         md = bte->md;
3061                                         goto post_process_call;
3062
3063                                 default:
3064                                         assert(0);
3065                         }
3066
3067                 } /* end instruction loop */
3068
3069                 /* consume outvars */
3070
3071                 for (i=0; i<bptr->outdepth; ++i)
3072                         POSTPROCESS_SRC(bptr->outvars[i]);
3073
3074 #if !defined(NDEBUG)
3075                 for (i=jd->localcount; i < jd->vartop; ++i)
3076                         assert(live[i] == 0);
3077 #endif
3078
3079         } /* end basic block loop */
3080 }
3081
3082
3083 /* inline_create_root_node *****************************************************
3084
3085    Create the root node of the inlining tree.
3086
3087    IN:
3088            jd...............the current jitdata of the root method
3089
3090    RETURN VALUE:
3091        the root node of the inlining tree
3092
3093 *******************************************************************************/
3094
3095 static inline_node * inline_create_root_node(jitdata *jd)
3096 {
3097         inline_node *iln;
3098
3099         iln = DNEW(inline_node);
3100         MZERO(iln, inline_node, 1);
3101
3102         iln->m = jd->m;
3103         iln->jd = jd;
3104         iln->regdata = jd->rd;
3105
3106         iln->blockbefore = true;
3107         iln->blockafter = true;
3108
3109         iln->cumul_instructioncount = 0;
3110         iln->cumul_basicblockcount = 1 /* dummy end block */;
3111
3112         /* create inlining context */
3113
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 */
3118
3119         return iln;
3120 }
3121
3122
3123 /******************************************************************************/
3124 /* MAIN DRIVER FUNCTION                                                       */
3125 /******************************************************************************/
3126
3127 bool inline_inline(jitdata *jd)
3128 {
3129         inline_node *iln;
3130
3131         DOLOG( printf("==== INLINE ==================================================================\n");
3132                    show_method(jd, SHOW_STACK); );
3133
3134 #if defined(INLINE_STATISTICS)
3135         inline_stat_roots++;
3136 #endif
3137
3138         iln = inline_create_root_node(jd);
3139
3140         if (inline_make_inlining_plan(iln)) {
3141
3142                 /* add blocks to the root node */
3143
3144                 iln->cumul_basicblockcount += iln->cumul_basicblockcount_root;
3145                 iln->cumul_blockmapcount   += iln->cumul_basicblockcount_root;
3146
3147                 DOLOG( printf("==== INLINE TRANSFORM ========================================================\n"); );
3148
3149                 if (iln->children)
3150                         inline_transform(iln, jd);
3151
3152 #if defined(INLINE_STATISTICS)
3153                 inline_gather_statistics(iln);
3154 #endif
3155         }
3156
3157         DOLOG( printf("-------- DONE -----------------------------------------------------------\n");
3158                    fflush(stdout); );
3159
3160         return true;
3161 }
3162
3163 /*
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  * ---------------------------------------------------------------------
3168  * Local variables:
3169  * mode: c
3170  * indent-tabs-mode: t
3171  * c-basic-offset: 4
3172  * tab-width: 4
3173  * End:
3174  * vim:noexpandtab:sw=4:ts=4:
3175  */