src/vm/jit/inline/inline.c

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