src/vm/jit/inline/inline.cpp

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