src/vm/jit/inline/inline.c

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