src/vm/jit/inline/inline.c

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