src/vm/jit/inline/inline.c

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