src/vm/jit/inline/inline.c

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