src/vm/jit/inline/inline.c

   1 /* src/vm/jit/inline/inline.c - code inliner
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Edwin Steiner
  28
  29    Changes:
  30
  31    $Id: inline.c 4734 2006-04-05 09:57:55Z edwin $
  32
  33 */
  34
  35 #include "config.h"
  36
  37 #include "vm/types.h"
  38
  39 #include <assert.h>
  40 #include <stdio.h>
  41 #include <string.h>
  42 #include <limits.h>
  43
  44 #include "mm/memory.h"
  45 #include "toolbox/logging.h"
  46 #include "vm/global.h"
  47 #include "vm/options.h"
  48 #include "vm/statistics.h"
  49 #include "vm/jit/jit.h"
  50 #include "vm/jit/parse.h"
  51 #include "vm/jit/inline/inline.h"
  52 #include "vm/jit/loop/loop.h"
  53
  54 #include "vm/class.h"
  55 #include "vm/initialize.h"
  56 #include "vm/method.h"
  57 #include "vm/jit/jit.h"
  58
  59 #include "vm/jit/reg.h"
  60 #include "vm/jit/stack.h"
  61
  62 #include "vm/jit/verify/typecheck.h"
  63
  64 #if defined(USE_THREADS)
  65 # if defined(NATIVE_THREADS)
  66 #  include "threads/native/threads.h"
  67 # else
  68 #  include "threads/green/threads.h"
  69 # endif
  70 #endif
  71
  72 #ifndef NDEBUG
  73 bool inline_debug_log = 0;
  74 bool inline_debug_log_names = 0;
  75 int inline_debug_start_counter = 0;
  76 int inline_debug_max_size = INT_MAX;
  77 int inline_debug_min_size = 0;
  78 int inline_debug_end_counter = INT_MAX;
  79 int inline_count_methods = 0;
  80 #define DOLOG(code) do{ if (inline_debug_log) { code; } }while(0)
  81 #else
  82 #define DOLOG(code)
  83 #endif
  84
  85 typedef struct inline_node inline_node;
  86 typedef struct inline_target_ref inline_target_ref;
  87 typedef struct inline_context inline_context;
  88 typedef struct inline_stack_translation inline_stack_translation;
  89 typedef struct inline_block_map inline_block_map;
  90
  91 struct inline_node {
  92         inline_context *ctx;
  93
  94         methodinfo *m;
  95         inline_node *children;
  96         inline_node *next;
  97         inline_node *prev;
  98         int depth;
  99
 100         /* info about the call site (if depth > 0)*/
 101         inline_node *parent;
 102         basicblock *callerblock;
 103         instruction *callerins;
 104         s4 callerpc;
 105         stackptr n_callerstack;
 106         int n_callerstackdepth;
 107         stackptr o_callerstack;
 108         exceptiontable **o_handlers;
 109
 110         /* info about the callee */
 111         int localsoffset;
 112         int prolog_instructioncount;
 113         int epilog_instructioncount;
 114         int extra_instructioncount;
 115         int instructioncount;
 116         int stackcount;
 117         bool synchronize;
 118         basicblock *handler_monitorexit;
 119
 120         /* cumulative values */
 121         int cumul_instructioncount;
 122         int cumul_stackcount;
 123         int cumul_basicblockcount;
 124         int cumul_maxstack;
 125         int cumul_maxlocals;
 126         int cumul_exceptiontablelength;
 127
 128         /* output */
 129         instruction *inlined_iinstr;
 130         instruction *inlined_iinstr_cursor;
 131         stackptr n_inlined_stack;
 132         stackptr n_inlined_stack_cursor;
 133         basicblock *inlined_basicblocks;
 134         basicblock *inlined_basicblocks_cursor;
 135
 136         /* register data */
 137         registerdata *regdata;
 138
 139         /* temporary */
 140         inline_target_ref *refs;
 141         instruction *inline_start_instruction;
 142 };
 143
 144 struct inline_target_ref {
 145         inline_target_ref *next;
 146         basicblock **ref;
 147         basicblock *target;
 148 };
 149
 150 struct inline_stack_translation {
 151         stackptr o_sp;
 152         stackptr n_sp;
 153 };
 154
 155 struct inline_block_map {
 156         inline_node *iln;
 157         basicblock *o_block;
 158         basicblock *n_block;
 159 };
 160
 161 struct inline_context {
 162         inline_node *master;
 163
 164         int next_block_number;
 165         inline_block_map *blockmap;
 166         int blockmap_index;
 167
 168         bool calls_others;
 169
 170         stackptr o_translationlimit; /* if a stackptr is smaller than this, look it up in the table */
 171         stackptr n_debug_stackbase;
 172         inline_stack_translation *stacktranslationstart;
 173
 174         inline_stack_translation stacktranslation[1]; /* XXX VARIABLE LENGTH! */
 175 };
 176
 177 static int stack_depth(stackptr sp)
 178 {
 179         int depth = 0;
 180         while (sp) {
 181                 depth++;
 182                 sp = sp->prev;
 183         }
 184         return depth;
 185 }
 186
 187 #ifndef NDEBUG
 188 #include "inline_debug.c"
 189
 190 void inline_print_stats()
 191 {
 192         printf("inlined callers: %d\n",inline_count_methods);
 193 }
 194 #endif
 195
 196 static bool inline_jit_compile_intern(jitdata *jd)
 197 {
 198         methodinfo *m;
 199
 200         assert(jd);
 201
 202         /* XXX initialize the static function's class */
 203
 204         m = jd->m;
 205         m->isleafmethod = true;
 206
 207         /* call the compiler passes ***********************************************/
 208
 209         /* call parse pass */
 210
 211         DOLOG( log_message_class("Parsing ", m->class) );
 212         if (!parse(jd)) {
 213                 return false;
 214         }
 215
 216         /* call stack analysis pass */
 217
 218         if (!stack_analyse(jd)) {
 219                 return false;
 220         }
 221
 222         return true;
 223 }
 224
 225 static bool inline_jit_compile(inline_node *iln)
 226 {
 227         bool                r;
 228         methodinfo         *m;
 229         jitdata            *jd;
 230         s4 i;
 231
 232         assert(iln);
 233         m = iln->m;
 234         assert(m);
 235
 236 #if defined(USE_THREADS)
 237         /* enter a monitor on the method */
 238         builtin_monitorenter((java_objectheader *) m);
 239 #endif
 240
 241         /* XXX dont parse these a second time because parse is not idempotent */
 242         for (i=0; i<m->jcodelength; ++i) {
 243                 if (m->jcode[i] == JAVA_TABLESWITCH || m->jcode[i] == JAVA_LOOKUPSWITCH) {
 244                         r = false;
 245                         goto return_r;
 246                 }
 247         }
 248
 249         /* allocate jitdata structure and fill it */
 250
 251         jd = DNEW(jitdata);
 252
 253         jd->m     = m;
 254         jd->cd    = DNEW(codegendata);
 255         jd->rd    = DNEW(registerdata);
 256 #if defined(ENABLE_LOOP)
 257         jd->ld    = DNEW(loopdata);
 258 #endif
 259         jd->flags = 0;
 260
 261         /* Allocate codeinfo memory from the heap as we need to keep them. */
 262
 263         jd->code  = code_codeinfo_new(m); /* XXX check allocation */
 264
 265 #if defined(ENABLE_JIT)
 266 # if defined(ENABLE_INTRP)
 267         if (!opt_intrp)
 268 # endif
 269                 /* initialize the register allocator */
 270                 reg_setup(jd);
 271 #endif
 272
 273         /* setup the codegendata memory */
 274
 275         codegen_setup(jd);
 276
 277         /* now call internal compile function */
 278
 279         r = inline_jit_compile_intern(jd);
 280
 281         if (r) {
 282                 iln->regdata = jd->rd;
 283         }
 284
 285         /* free some memory */
 286 #if 0
 287
 288
 289 #if defined(ENABLE_JIT)
 290 # if defined(ENABLE_INTRP)
 291         if (!opt_intrp)
 292 # endif
 293                 codegen_free(jd);
 294 #endif
 295
 296 #endif
 297
 298 return_r:
 299 #if defined(USE_THREADS)
 300         /* leave the monitor */
 301         builtin_monitorexit((java_objectheader *) m );
 302 #endif
 303
 304 #if 0
 305         stack_show_method(jd);
 306 #endif
 307
 308         return r;
 309 }
 310
 311 static void insert_inline_node(inline_node *parent,inline_node *child)
 312 {
 313         inline_node *first;
 314         inline_node *succ;
 315
 316         assert(parent && child);
 317
 318         child->parent = parent;
 319
 320         first = parent->children;
 321         if (!first) {
 322                 /* insert as only node */
 323                 parent->children = child;
 324                 child->next = child;
 325                 child->prev = child;
 326                 return;
 327         }
 328
 329         /* {there is at least one child already there} */
 330
 331         succ = first;
 332         while (succ->callerpc < child->callerpc) {
 333                 succ = succ->next;
 334                 if (succ == first) {
 335                         /* insert as last node */
 336                         child->prev = first->prev;
 337                         child->next = first;
 338                         child->prev->next = child;
 339                         child->next->prev = child;
 340                         return;
 341                 }
 342         }
 343
 344         assert(succ->callerpc > child->callerpc);
 345
 346         /* insert before succ */
 347
 348         child->prev = succ->prev;
 349         child->next = succ;
 350         child->prev->next = child;
 351         child->next->prev = child;
 352 }
 353
 354 static stackptr relocate_stack_ptr_intern(inline_node *iln,stackptr o_link,ptrint curreloc)
 355 {
 356         inline_stack_translation *tr;
 357
 358         if (o_link) {
 359                 /* XXX should limit range in both directions */
 360                 if (o_link < iln->ctx->o_translationlimit) {
 361                         /* this stack slot is from an earlier chunk, we must look it up */
 362                         tr = iln->ctx->stacktranslationstart;
 363                         while (tr >= iln->ctx->stacktranslation) {
 364                                 if (o_link == tr->o_sp) {
 365                                         DOLOG(printf("\t\t\ttable lookup %p -> %d\n",(void*)o_link,DEBUG_SLOT(tr->n_sp)));
 366                                         return tr->n_sp;
 367                                 }
 368                                 tr--;
 369                         }
 370                         DOLOG(debug_dump_inline_context(iln));
 371                         DOLOG(printf("\t\tFAILED TO TRANSLATE: %p\n",(void*)o_link));
 372                         assert(false);
 373                 }
 374                 else {
 375                         /* this stack slot it in the most recent chunk */
 376                         assert(curreloc);
 377                         DOLOG( printf("\t\t\toffset %d\n",(int)curreloc) );
 378                         return (stackptr) ((u1*)o_link + curreloc);
 379                 }
 380         }
 381         return iln->n_callerstack;
 382 }
 383
 384 /* XXX for debugging */
 385 static stackptr relocate_stack_ptr(inline_node *iln,stackptr o_link,ptrint curreloc)
 386 {
 387         stackptr new;
 388
 389         new = relocate_stack_ptr_intern(iln,o_link,curreloc);
 390         DOLOG(
 391                 printf("\t\treloc %p -> %d (%p)\t(translimit=%p)\n",
 392                                 (void*)o_link,DEBUG_SLOT(new),(void*)new,(void*)iln->ctx->o_translationlimit)
 393         );
 394         return new;
 395 }
 396
 397 static void emit_instruction(inline_node *iln,instruction *ins,ptrint curreloc,stackptr o_curstack)
 398 {
 399         char indent[100];
 400         int i;
 401         instruction *n_ins;
 402         inline_target_ref *ref;
 403
 404         assert(iln && ins);
 405
 406         for (i=0; i<iln->depth; ++i)
 407                 indent[i] = '\t';
 408         indent[i] = 0;
 409
 410         n_ins = (iln->inlined_iinstr_cursor++);
 411         assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
 412
 413         *n_ins = *ins;
 414
 415         switch (n_ins[0].opc) {
 416                                 /****************************************/
 417                                 /* VARIABLE ACCESS                      */
 418
 419                         case ICMD_ILOAD:
 420                         case ICMD_IINC:
 421                         case ICMD_FLOAD:
 422                         case ICMD_LLOAD:
 423                         case ICMD_DLOAD:
 424                         case ICMD_ISTORE:
 425                         case ICMD_FSTORE:
 426                         case ICMD_LSTORE:
 427                         case ICMD_DSTORE:
 428                         case ICMD_ALOAD:
 429                         case ICMD_ASTORE:
 430                     case ICMD_RET:
 431                         n_ins[0].op1 += iln->localsoffset;
 432                         break;
 433
 434                         case ICMD_GOTO:
 435                         case ICMD_IFNULL:
 436                         case ICMD_IFNONNULL:
 437                         case ICMD_IFEQ:
 438                         case ICMD_IFNE:
 439                         case ICMD_IFLT:
 440                         case ICMD_IFGE:
 441                         case ICMD_IFGT:
 442                         case ICMD_IFLE:
 443                         case ICMD_IF_ICMPEQ:
 444                         case ICMD_IF_ICMPNE:
 445                         case ICMD_IF_ICMPLT:
 446                         case ICMD_IF_ICMPGE:
 447                         case ICMD_IF_ICMPGT:
 448                         case ICMD_IF_ICMPLE:
 449                         case ICMD_IF_ACMPEQ:
 450                         case ICMD_IF_ACMPNE:
 451                         case ICMD_IF_LEQ:
 452                         case ICMD_IF_LNE:
 453                         case ICMD_IF_LLT:
 454                         case ICMD_IF_LGE:
 455                         case ICMD_IF_LGT:
 456                         case ICMD_IF_LLE:
 457                         case ICMD_IF_LCMPEQ:
 458                         case ICMD_IF_LCMPNE:
 459                         case ICMD_IF_LCMPLT:
 460                         case ICMD_IF_LCMPGE:
 461                         case ICMD_IF_LCMPGT:
 462                         case ICMD_IF_LCMPLE:
 463                         case ICMD_JSR:
 464                                 ref = DNEW(inline_target_ref);
 465                                 ref->ref = (basicblock **) &(n_ins[0].target);
 466                                 ref->next = iln->refs;
 467                                 iln->refs = ref;
 468                                 break;
 469
 470                                 /****************************************/
 471                                 /* RETURNS                              */
 472
 473                         case ICMD_RETURN:
 474                                 if (iln->parent) {
 475                                         n_ins[0].opc = ICMD_GOTO;
 476                                         n_ins[0].dst = NULL;
 477                                         goto return_tail;
 478                                 }
 479                                 break;
 480
 481                         case ICMD_ARETURN:
 482                         case ICMD_IRETURN:
 483                         case ICMD_LRETURN:
 484                         case ICMD_FRETURN:
 485                         case ICMD_DRETURN:
 486                         if (iln->parent) {
 487                                 n_ins[0].opc = ICMD_INLINE_GOTO;
 488                                 n_ins[0].dst = o_curstack;
 489 return_tail:
 490                                 n_ins[0].target = (void *) (ptrint) (iln->depth + 0x333); /* XXX */
 491                                 ref = DNEW(inline_target_ref);
 492                                 ref->ref = (basicblock **) &(n_ins[0].target);
 493                                 ref->next = iln->refs;
 494                                 iln->refs = ref;
 495                         }
 496                         break;
 497         }
 498
 499         n_ins[0].dst = relocate_stack_ptr(iln,n_ins[0].dst,curreloc);
 500 }
 501
 502 static stackptr inline_new_stackslot(inline_node *iln,stackptr n_curstack,s4 type)
 503 {
 504         stackptr n_sp;
 505
 506         n_sp = iln->n_inlined_stack_cursor++;
 507         assert((n_sp - iln->n_inlined_stack) < iln->cumul_stackcount);
 508
 509         n_sp->prev = n_curstack;
 510         n_sp->type = type;
 511         n_sp->varkind = TEMPVAR;
 512         n_sp->varnum = stack_depth(n_curstack); /* XXX inefficient */
 513         n_sp->flags = 0;
 514 #ifndef NDEBUG
 515         n_sp->regoff = (IS_FLT_DBL_TYPE(type)) ? -1 : INT_ARG_CNT;
 516 #endif
 517
 518         return n_sp;
 519 }
 520
 521 static stackptr emit_inlining_prolog(inline_node *iln,inline_node *callee,stackptr n_curstack,instruction *o_iptr)
 522 {
 523         methodinfo *calleem;
 524         methoddesc *md;
 525         int i;
 526         int localindex;
 527         int depth;
 528         int type;
 529         bool isstatic;
 530         instruction *n_ins;
 531         insinfo_inline *insinfo;
 532
 533         assert(iln && callee && o_iptr);
 534
 535         calleem = callee->m;
 536         md = calleem->parseddesc;
 537         isstatic = (calleem->flags & ACC_STATIC);
 538
 539         localindex = callee->localsoffset + md->paramslots;
 540         depth = stack_depth(n_curstack) - 1; /* XXX inefficient */
 541         for (i=md->paramcount-1; i>=0; --i) {
 542                 assert(iln);
 543
 544                 n_ins = (iln->inlined_iinstr_cursor++);
 545                 assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
 546
 547                 type = md->paramtypes[i].type;
 548
 549                 localindex -= IS_2_WORD_TYPE(type) ? 2 : 1;
 550                 assert(callee->regdata);
 551
 552                 DOLOG( printf("prologlocal %d type=%d lofs=%d in ",
 553                            localindex - callee->localsoffset,
 554                            callee->regdata->locals[localindex - callee->localsoffset][type].type,callee->localsoffset);
 555                                 method_println(callee->m); );
 556
 557                 if ((callee->regdata->locals[localindex - callee->localsoffset][type].type >= 0)
 558                                 ||
 559                         (i==0 && callee->synchronize && !isstatic))
 560                 {
 561                         n_ins->opc = ICMD_ISTORE + type;
 562                         n_ins->op1 = localindex;
 563                 }
 564                 else {
 565                         n_ins->opc = IS_2_WORD_TYPE(type) ? ICMD_POP2 : ICMD_POP; /* XXX is POP2 correct? */
 566                 }
 567                 n_ins->line = o_iptr->line;
 568                 assert(n_curstack);
 569                 if (n_curstack->varkind == ARGVAR) {
 570                         n_curstack->varkind = TEMPVAR;
 571                         n_curstack->varnum = depth;
 572                         n_curstack->flags &= ~INMEMORY;
 573                 }
 574                 n_curstack = n_curstack->prev;
 575                 n_ins->dst = n_curstack;
 576                 depth--;
 577         }
 578
 579         /* INLINE_START instruction */
 580
 581         n_ins = (iln->inlined_iinstr_cursor++);
 582         assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
 583
 584         insinfo = DNEW(insinfo_inline);
 585         insinfo->method = callee->m;
 586         insinfo->outer = iln->m;
 587         /* XXX using local 0 only works if it is read-only!! */
 588         insinfo->synclocal = callee->localsoffset;
 589         insinfo->synchronize = callee->synchronize;
 590
 591         n_ins->opc = ICMD_INLINE_START;
 592         n_ins->dst = n_curstack;
 593         n_ins->target = insinfo;
 594         n_ins->line = o_iptr->line;
 595         iln->inline_start_instruction = n_ins;
 596
 597         return n_curstack;
 598 }
 599
 600 static void emit_inlining_epilog(inline_node *iln,inline_node *callee,stackptr n_curstack,instruction *o_iptr)
 601 {
 602         instruction *n_ins;
 603
 604         assert(iln && callee && o_iptr);
 605         assert(iln->inline_start_instruction);
 606
 607         n_ins = (iln->inlined_iinstr_cursor++);
 608         assert((n_ins - iln->inlined_iinstr) < iln->cumul_instructioncount);
 609
 610         n_ins->opc = ICMD_INLINE_END;
 611         n_ins->dst = n_curstack;
 612         n_ins->target = iln->inline_start_instruction->target; /* insinfo_inline * */
 613         n_ins->line = o_iptr->line;
 614 }
 615
 616 static void rewrite_stack(inline_node *iln,stackptr o_first,stackptr o_last,ptrint curreloc)
 617 {
 618         int n;
 619         stackptr o_sp;
 620         stackptr n_sp;
 621
 622         assert(iln);
 623
 624         if (!o_first) {
 625                 assert(!o_last);
 626                 DOLOG(printf("rewrite_stack: no stack slots\n"));
 627                 return;
 628         }
 629
 630         assert(o_first);
 631         assert(o_last);
 632         assert(o_first <= o_last);
 633
 634         n = o_last - o_first + 1;
 635         assert(n >= 0);
 636
 637         o_sp = o_first;
 638         n_sp = iln->n_inlined_stack_cursor;
 639
 640         DOLOG(
 641         printf("rewrite_stack: rewriting %d stack slots (%p,%p) -> (%d,%d)\n",
 642                         n,(void*)o_first,(void*)o_last,DEBUG_SLOT(n_sp),
 643                         DEBUG_SLOT(n_sp+n-1))
 644         );
 645
 646         DOLOG( printf("o_first = "); debug_dump_stack(o_first); printf("\n") );
 647         DOLOG( printf("o_last = "); debug_dump_stack(o_last); printf("\n") );
 648
 649         while (o_sp <= o_last) {
 650                 *n_sp = *o_sp;
 651
 652                 n_sp->prev = relocate_stack_ptr(iln,n_sp->prev,curreloc);
 653                 switch (n_sp->varkind) {
 654                         case STACKVAR: n_sp->varnum += iln->n_callerstackdepth; break;
 655                         case LOCALVAR: n_sp->varnum += iln->localsoffset; break;
 656                 }
 657
 658                 o_sp++;
 659                 n_sp++;
 660         }
 661         DOLOG( printf("n_sp = "); debug_dump_stack(n_sp-1); printf("\n") );
 662
 663         iln->n_inlined_stack_cursor = n_sp;
 664         assert((n_sp - iln->n_inlined_stack) <= iln->cumul_stackcount);
 665 }
 666
 667 static void inline_resolve_block_refs(inline_target_ref **refs,basicblock *o_bptr,basicblock *n_bptr)
 668 {
 669         inline_target_ref *ref;
 670         inline_target_ref *prev;
 671
 672         ref = *refs;
 673         prev = NULL;
 674         while (ref) {
 675                 if (*(ref->ref) == o_bptr) {
 676                         DOLOG(
 677                                 if ((ptrint) o_bptr < (0x333+100)) { /* XXX */
 678                                         printf("resolving RETURN block reference %p -> new L%03d (%p)\n",
 679                                                         (void*)o_bptr,n_bptr->debug_nr,(void*)n_bptr);
 680                                 }
 681                                 else {
 682                                         printf("resolving block reference old L%03d (%p) -> new L%03d (%p)\n",
 683                                                         o_bptr->debug_nr,(void*)o_bptr,n_bptr->debug_nr,(void*)n_bptr);
 684                                 }
 685                         );
 686
 687                         *(ref->ref) = n_bptr;
 688                         if (prev) {
 689                                 prev->next = ref->next;
 690                         }
 691                         else {
 692                                 *refs = ref->next;
 693                         }
 694                 }
 695                 else {
 696                         prev = ref;
 697                 }
 698                 ref = ref->next;
 699         }
 700 }
 701
 702 static basicblock * create_block(inline_node *iln,basicblock *o_bptr,inline_target_ref **refs,int indepth)
 703 {
 704         basicblock *n_bptr;
 705         stackptr n_sp;
 706         int i;
 707
 708         assert(iln);
 709
 710         n_bptr = iln->inlined_basicblocks_cursor++;
 711         assert(n_bptr);
 712         assert((n_bptr - iln->inlined_basicblocks) < iln->cumul_basicblockcount);
 713
 714         memset(n_bptr,0,sizeof(basicblock));
 715         n_bptr->mpc = -1;
 716
 717         n_bptr->type = BBTYPE_STD; /* XXX not necessary */
 718         n_bptr->iinstr = iln->inlined_iinstr_cursor;
 719         n_bptr->next = n_bptr+1;
 720         n_bptr->debug_nr = iln->ctx->next_block_number++;
 721         n_bptr->indepth = indepth;
 722
 723         if (indepth) {
 724                 /* allocate stackslots */
 725                 iln->n_inlined_stack_cursor += indepth;
 726                 n_sp = iln->n_inlined_stack_cursor - 1;
 727                 n_bptr->instack = n_sp;
 728
 729                 assert((n_sp - iln->n_inlined_stack) < iln->cumul_stackcount);
 730
 731                 /* link the stack elements */
 732                 for (i=indepth-1; i>=0; --i) {
 733                         n_sp->varkind = STACKVAR;
 734                         n_sp->varnum = i;
 735                         n_sp->prev = (i) ? n_sp-1 : NULL;
 736                         n_sp->flags = 0; /* XXX */
 737                         n_sp--;
 738                 }
 739         }
 740
 741         if (o_bptr) {
 742                 assert(refs);
 743                 inline_resolve_block_refs(refs,o_bptr,n_bptr);
 744         }
 745
 746         return n_bptr;
 747 }
 748
 749 static void fill_translation_table(inline_node *iln,stackptr o_sp,stackptr n_sp,int n_depth)
 750 {
 751         int i;
 752
 753         DOLOG(
 754         printf("fill_translation_table (newdepth=%d):\n",n_depth);
 755         printf("\tos_sp = "); debug_dump_stack(o_sp); printf("\n");
 756         printf("\tns_sp = "); debug_dump_stack(n_sp); printf("\n");
 757         );
 758
 759         /* we must translate all stack slots that were present before the call XXX  */
 760         /* and the instack of the block */
 761         iln->ctx->stacktranslationstart = iln->ctx->stacktranslation + (n_depth - 1);
 762
 763         /* fill the translation table */
 764         if (n_depth) {
 765                 i = n_depth-1;
 766
 767                 while (o_sp) {
 768                         assert(i >= 0);
 769                         assert(n_sp);
 770                         iln->ctx->stacktranslation[i].o_sp = o_sp;
 771                         iln->ctx->stacktranslation[i].n_sp = n_sp;
 772                         n_sp->flags |= (o_sp->flags & SAVEDVAR); /* XXX correct? */
 773                         n_sp->type = o_sp->type; /* XXX we overwrite this anyway with STACKVAR, right? */
 774                         o_sp = o_sp->prev;
 775                         n_sp = n_sp->prev;
 776                         i--;
 777                 }
 778
 779                 while (n_sp) {
 780                         assert(i >= 0);
 781                         assert(iln->ctx->stacktranslation[i].o_sp);
 782                         iln->ctx->stacktranslation[i].n_sp = n_sp;
 783                         n_sp->flags |= SAVEDVAR; /* XXX this is too conservative */
 784                         n_sp = n_sp->prev;
 785                         i--;
 786                 }
 787
 788                 assert(i == -1);
 789         }
 790 }
 791
 792 static void rewrite_method(inline_node *iln)
 793 {
 794         basicblock *o_bptr;
 795         s4 len;
 796         instruction *o_iptr;
 797         instruction *n_iptr;
 798         stackptr o_dst;
 799         stackptr n_sp;
 800         stackptr o_sp;
 801         stackptr o_curstack;
 802         stackptr o_nexttorewrite;
 803         stackptr o_lasttorewrite;
 804         inline_node *nextcall;
 805         ptrint curreloc;
 806         basicblock *n_bptr;
 807         inline_block_map *bm;
 808         int i;
 809         int icount;
 810
 811         assert(iln);
 812
 813         n_bptr = NULL;
 814         nextcall = iln->children;
 815
 816         /* set memory cursors */
 817         iln->inlined_iinstr_cursor = iln->inlined_iinstr;
 818         iln->n_inlined_stack_cursor = iln->n_inlined_stack;
 819         iln->inlined_basicblocks_cursor = iln->inlined_basicblocks;
 820
 821         /* loop over basic blocks */
 822         o_bptr = iln->m->basicblocks;
 823         for (; o_bptr; o_bptr = o_bptr->next) {
 824
 825                 if (o_bptr->flags < BBREACHED) {
 826                         DOLOG(
 827                         printf("skipping old L%03d (flags=%d,type=%d,os=%p,oid=%d,ois=%p,cursor=%d,callerstack=%d) of ",
 828                                         o_bptr->debug_nr,o_bptr->flags,o_bptr->type,
 829                                         (void*)o_bptr->stack,o_bptr->indepth,(void*)o_bptr->instack,
 830                                         DEBUG_SLOT(iln->n_inlined_stack_cursor),
 831                                         DEBUG_SLOT(iln->n_callerstack));
 832                         method_println(iln->m);
 833                         );
 834
 835                         n_bptr = create_block(iln,o_bptr,&(iln->refs),o_bptr->indepth + iln->n_callerstackdepth);
 836                         n_bptr->type = o_bptr->type;
 837                         /* enter it in the blockmap */
 838                         iln->ctx->blockmap[iln->ctx->blockmap_index].iln = iln;
 839                         iln->ctx->blockmap[iln->ctx->blockmap_index].o_block = o_bptr;
 840                         iln->ctx->blockmap[iln->ctx->blockmap_index++].n_block = n_bptr;
 841                         n_bptr->flags = o_bptr->flags;
 842                         continue;
 843                 }
 844
 845                 assert(o_bptr->stack);
 846
 847                 len = o_bptr->icount;
 848                 o_iptr = o_bptr->iinstr;
 849
 850                 DOLOG(
 851                 printf("rewriting old L%03d (flags=%d,type=%d,os=%p,oid=%d,ois=%p,cursor=%d,callerstack=%d) of ",
 852                                 o_bptr->debug_nr,o_bptr->flags,o_bptr->type,
 853                                 (void*)o_bptr->stack,o_bptr->indepth,(void*)o_bptr->instack,
 854                                 DEBUG_SLOT(iln->n_inlined_stack_cursor),
 855                                 DEBUG_SLOT(iln->n_callerstack));
 856                 method_println(iln->m);
 857                 printf("o_instack: ");debug_dump_stack(o_bptr->instack);printf("\n");
 858                 printf("o_callerstack: ");debug_dump_stack(iln->o_callerstack);printf("\n");
 859                 );
 860
 861                 o_curstack = o_bptr->instack;
 862
 863                 /* create an inlined clone of this block */
 864                 n_bptr = create_block(iln,o_bptr,&(iln->refs),o_bptr->indepth + iln->n_callerstackdepth);
 865                 n_bptr->type = o_bptr->type;
 866                 n_bptr->flags = o_bptr->flags;
 867
 868                 /* enter it in the blockmap */
 869                 iln->ctx->blockmap[iln->ctx->blockmap_index].iln = iln;
 870                 iln->ctx->blockmap[iln->ctx->blockmap_index].o_block = o_bptr;
 871                 iln->ctx->blockmap[iln->ctx->blockmap_index++].n_block = n_bptr;
 872
 873                 DOLOG( debug_dump_inline_context(iln) );
 874
 875                 if (iln->n_callerstackdepth)
 876                         iln->n_callerstack = n_bptr->instack-o_bptr->indepth;
 877                 else
 878                         iln->n_callerstack = NULL;
 879                 fill_translation_table(iln,iln->o_callerstack,iln->n_callerstack,iln->n_callerstackdepth);
 880                 fill_translation_table(iln,o_bptr->instack,n_bptr->instack,n_bptr->indepth);
 881                 iln->ctx->o_translationlimit = o_bptr->stack;
 882
 883                 DOLOG( debug_dump_inline_context(iln) );
 884
 885                 /* calculate the stack element relocation */
 886                 curreloc = (u1*)iln->n_inlined_stack_cursor - (u1*)o_bptr->stack;
 887                 DOLOG( printf("curreloc <- %d = %p - %p\n",(int)curreloc,(void*)iln->n_inlined_stack_cursor,(void*)(u1*)o_bptr->stack) );
 888
 889                 o_nexttorewrite = o_bptr->stack;
 890                 o_lasttorewrite = o_bptr->stack-1;
 891                 assert(o_nexttorewrite);
 892
 893                 icount = 0;
 894
 895                 while (--len >= 0) {
 896                         o_dst = o_iptr->dst;
 897
 898                         DOLOG( printf("o_curstack = "); debug_dump_stack(o_curstack); stack_show_icmd(o_iptr,false); printf(", dst = "); debug_dump_stack(o_dst); printf("\n") );
 899
 900                         if (nextcall && o_iptr == nextcall->callerins) {
 901
 902                                 /* rewrite stack elements produced so far in this block */
 903                                 if (o_nexttorewrite <= o_lasttorewrite) {
 904                                         rewrite_stack(iln, o_nexttorewrite, o_lasttorewrite, curreloc);
 905                                 }
 906
 907                                 /* write the inlining prolog */
 908                                 n_sp = emit_inlining_prolog(iln,nextcall,relocate_stack_ptr(iln,o_curstack,curreloc),o_iptr);
 909                                 icount += nextcall->m->parseddesc->paramcount + 1; /* XXX prolog instructions */
 910
 911                                 /* find the first stack slot under the arguments of the invocation */
 912                                 o_sp = o_curstack;
 913                                 for (i=0; i < nextcall->m->parseddesc->paramcount; ++i) {
 914                                         assert(o_sp);
 915                                         o_sp = o_sp->prev;
 916                                 }
 917                                 nextcall->o_callerstack = o_sp;
 918
 919                                 /* see how deep the new stack is after the arguments have been removed */
 920                                 i = stack_depth(n_sp);
 921                                 assert(i == stack_depth(nextcall->o_callerstack) + iln->n_callerstackdepth);
 922
 923                                 /* end current block */
 924                                 n_bptr->icount = icount;
 925                                 n_bptr->outstack = n_sp;
 926                                 n_bptr->outdepth = i;
 927
 928                                 /* caller stack depth for the callee */
 929                                 assert(nextcall->n_callerstackdepth == i);
 930
 931                                 /* set memory pointers in the callee */
 932                                 nextcall->inlined_iinstr = iln->inlined_iinstr_cursor;
 933                                 nextcall->n_inlined_stack = iln->n_inlined_stack_cursor;
 934                                 nextcall->inlined_basicblocks = iln->inlined_basicblocks_cursor;
 935
 936                                 /* recurse */
 937                                 DOLOG( printf("entering inline "); stack_show_icmd(o_iptr,false); printf("\n") );
 938                                 rewrite_method(nextcall);
 939                                 DOLOG( printf("leaving inline "); stack_show_icmd(o_iptr,false); printf("\n") );
 940
 941                                 /* skip stack slots used by the inlined callee */
 942                                 curreloc += (u1*)nextcall->n_inlined_stack_cursor - (u1*)iln->n_inlined_stack_cursor;
 943
 944                                 /* update memory cursors */
 945                                 assert(nextcall->inlined_iinstr_cursor == iln->inlined_iinstr_cursor + nextcall->cumul_instructioncount);
 946                                 /* XXX m->stackcount seems to be a conservative estimate */
 947                                 assert(nextcall->n_inlined_stack_cursor <= iln->n_inlined_stack_cursor + nextcall->cumul_stackcount);
 948                                 assert(nextcall->inlined_basicblocks_cursor == iln->inlined_basicblocks_cursor + nextcall->cumul_basicblockcount);
 949                                 iln->inlined_iinstr_cursor = nextcall->inlined_iinstr_cursor;
 950                                 iln->n_inlined_stack_cursor = nextcall->n_inlined_stack_cursor;
 951                                 iln->inlined_basicblocks_cursor = nextcall->inlined_basicblocks_cursor;
 952
 953                                 /* start new block */
 954                                 i = (nextcall->m->parseddesc->returntype.type == TYPE_VOID) ? 0 : 1; /* number of return slots */
 955                                 assert(i == 0 || i == 1);
 956                                 n_bptr = create_block(iln,(void*) (ptrint) (nextcall->depth + 0x333) /*XXX*/,
 957                                                 &(nextcall->refs),nextcall->n_callerstackdepth + i);
 958                                 n_bptr->flags = o_bptr->flags;
 959                                 icount = 0;
 960
 961                                 /* skip allocated stack slots */
 962                                 curreloc += sizeof(stackelement) * (n_bptr->indepth - i);
 963
 964                                 /* fill the translation table for the slots present before the call */
 965                                 n_sp = n_bptr->instack;
 966                                 fill_translation_table(iln,nextcall->o_callerstack,(i) ? n_sp->prev : n_sp,nextcall->n_callerstackdepth);
 967
 968                                 /* the return slot */
 969                                 if (i) {
 970                                         assert(o_dst);
 971                                         assert(n_sp);
 972                                         fill_translation_table(iln,o_dst,n_sp,nextcall->n_callerstackdepth + 1);
 973
 974                                         o_nexttorewrite = o_dst + 1;
 975                                         o_lasttorewrite = o_dst;
 976                                 }
 977                                 else {
 978                                         /* the next chunk of stack slots start with (including) the slots produced */
 979                                         /* by the invocation */
 980                                         o_nexttorewrite = o_lasttorewrite + 1;
 981                                         o_lasttorewrite = o_nexttorewrite - 1;
 982                                 }
 983
 984                                 DOLOG( debug_dump_inline_context(iln) );
 985                                 iln->ctx->o_translationlimit = o_nexttorewrite;
 986
 987                                 /* emit inlining epilog */
 988                                 emit_inlining_epilog(iln,nextcall,n_sp,o_iptr);
 989                                 icount++; /* XXX epilog instructions */
 990
 991                                 /* proceed to next call */
 992                                 nextcall = nextcall->next;
 993
 994                                 DOLOG(
 995                                 printf("resuming old L%03d (flags=%d,type=%d,os=%p,oid=%d,ois=%p,cursor=%d,curreloc=%d,callerstack=%d) of ",
 996                                                 o_bptr->debug_nr,o_bptr->flags,o_bptr->type,
 997                                                 (void*)o_bptr->stack,o_bptr->indepth,(void*)o_bptr->instack,
 998                                                 DEBUG_SLOT(iln->n_inlined_stack_cursor),(int)curreloc,
 999                                                 DEBUG_SLOT(iln->n_callerstack));
1000                                 method_println(iln->m);
1001                                 );
1002                         }
1003                         else {
1004                                 emit_instruction(iln,o_iptr,curreloc,o_curstack);
1005                                 icount++;
1006
1007                                 if (o_dst > o_lasttorewrite)
1008                                         o_lasttorewrite = o_dst;
1009                         }
1010
1011                         DOLOG( printf("o_dst = %p\n",(void*)o_dst) );
1012                         o_curstack = o_dst;
1013                         o_iptr++;
1014                 }
1015
1016                 /* end of basic block */
1017                 /* rewrite stack after last call */
1018                 if (o_nexttorewrite <= o_lasttorewrite) {
1019                         rewrite_stack(iln,o_nexttorewrite,o_lasttorewrite,curreloc);
1020                 }
1021                 n_bptr->outstack = relocate_stack_ptr(iln,o_bptr->outstack,curreloc);
1022                 n_bptr->outdepth = iln->n_callerstackdepth + o_bptr->outdepth;
1023                 assert(n_bptr->outdepth == stack_depth(n_bptr->outstack));
1024 #if 0
1025                 if (n_bptr->outstack) {
1026                         assert(curreloc);
1027                         n_bptr->outstack += curreloc;
1028                 }
1029 #endif
1030                 n_bptr->icount = icount;
1031
1032                 n_iptr = iln->inlined_iinstr_cursor - 1;
1033                 if (n_iptr->opc == ICMD_INLINE_GOTO) {
1034                         DOLOG( printf("creating stack slot for ICMD_INLINE_GOTO\n") );
1035                         n_sp = iln->n_inlined_stack_cursor++;
1036                         assert(n_iptr->dst);
1037                         *n_sp = *n_iptr->dst;
1038                         n_sp->prev = iln->n_callerstack;
1039                         n_iptr->dst = n_sp;
1040
1041                         n_bptr->outdepth = iln->n_callerstackdepth + 1;
1042                         n_bptr->outstack = n_sp;
1043                 }
1044         }
1045
1046         bm = iln->ctx->blockmap;
1047         for (i=0; i<iln->ctx->blockmap_index; ++i, ++bm) {
1048                 assert(bm->iln && bm->o_block && bm->n_block);
1049                 if (bm->iln != iln)
1050                         continue;
1051                 inline_resolve_block_refs(&(iln->refs),iln->ctx->blockmap[i].o_block,iln->ctx->blockmap[i].n_block);
1052         }
1053
1054 #ifndef NDEBUG
1055         if (iln->refs) {
1056                 inline_target_ref *ref;
1057                 ref = iln->refs;
1058                 while (ref) {
1059                         if (!iln->depth || *(ref->ref) != (void*) (ptrint) (0x333 + iln->depth) /* XXX */) {
1060                                 DOLOG( printf("XXX REMAINING REF at depth %d: %p\n",iln->depth,(void*)*(ref->ref)) );
1061                                 assert(false);
1062                         }
1063                         ref = ref->next;
1064                 }
1065         }
1066 #endif
1067 }
1068
1069 static basicblock * inline_map_block(inline_node *iln,basicblock *o_block,inline_node *targetiln)
1070 {
1071         inline_block_map *bm;
1072         inline_block_map *bmend;
1073
1074         assert(iln);
1075         assert(targetiln);
1076
1077         if (!o_block)
1078                 return NULL;
1079
1080         bm = iln->ctx->blockmap;
1081         bmend = bm + iln->ctx->blockmap_index;
1082
1083         while (bm < bmend) {
1084                 assert(bm->iln && bm->o_block && bm->n_block);
1085                 if (bm->o_block == o_block && bm->iln == targetiln)
1086                         return bm->n_block;
1087                 bm++;
1088         }
1089
1090         assert(false);
1091         return NULL; /* not reached */
1092 }
1093
1094 static exceptiontable * inline_exception_tables(inline_node *iln,exceptiontable *n_extable,exceptiontable **prevextable)
1095 {
1096         inline_node *child;
1097         exceptiontable *et;
1098         int i;
1099
1100         assert(iln);
1101         assert(n_extable);
1102         assert(prevextable);
1103
1104         child = iln->children;
1105         if (child) {
1106                 do {
1107                         n_extable = inline_exception_tables(child,n_extable,prevextable);
1108                         child = child->next;
1109                 } while (child != iln->children);
1110         }
1111
1112         et = iln->m->exceptiontable;
1113         for (i=0; i<iln->m->exceptiontablelength; ++i) {
1114                 assert(et);
1115                 memset(n_extable,0,sizeof(exceptiontable));
1116                 n_extable->startpc = et->startpc;
1117                 n_extable->endpc = et->endpc;
1118                 n_extable->handlerpc = et->handlerpc;
1119                 n_extable->start = inline_map_block(iln,et->start,iln);
1120                 n_extable->end = inline_map_block(iln,et->end,iln);
1121                 n_extable->handler = inline_map_block(iln,et->handler,iln);
1122                 n_extable->catchtype = et->catchtype;
1123
1124                 if (*prevextable) {
1125                         (*prevextable)->down = n_extable;
1126                 }
1127                 *prevextable = n_extable;
1128
1129                 n_extable++;
1130                 et++;
1131         }
1132
1133         if (iln->handler_monitorexit) {
1134                 exceptiontable **activehandlers;
1135
1136                 memset(n_extable,0,sizeof(exceptiontable));
1137                 n_extable->startpc = 0; /* XXX */
1138                 n_extable->endpc = 0; /* XXX */
1139                 n_extable->handlerpc = 0; /* XXX */
1140                 n_extable->start = iln->inlined_basicblocks;
1141                 n_extable->end = iln->inlined_basicblocks_cursor;
1142                 n_extable->handler = iln->handler_monitorexit;
1143                 n_extable->catchtype.any = NULL; /* finally */
1144
1145                 if (*prevextable) {
1146                         (*prevextable)->down = n_extable;
1147                 }
1148                 *prevextable = n_extable;
1149
1150                 n_extable++;
1151
1152                 activehandlers = iln->o_handlers;
1153                 while (*activehandlers) {
1154
1155                         assert(iln->parent);
1156
1157                         memset(n_extable,0,sizeof(exceptiontable));
1158                         n_extable->startpc = 0; /* XXX */
1159                         n_extable->endpc = 0; /* XXX */
1160                         n_extable->handlerpc = 0; /* XXX */
1161                         n_extable->start = iln->handler_monitorexit;
1162                         n_extable->end = iln->handler_monitorexit + 1;
1163                         n_extable->handler = inline_map_block(iln->parent,(*activehandlers)->handler,iln->parent);
1164                         n_extable->catchtype = (*activehandlers)->catchtype;
1165
1166                         if (*prevextable) {
1167                                 (*prevextable)->down = n_extable;
1168                         }
1169                         *prevextable = n_extable;
1170
1171                         n_extable++;
1172                         activehandlers++;
1173                 }
1174
1175         }
1176
1177         return n_extable;
1178 }
1179
1180 static void inline_locals(inline_node *iln,registerdata *rd)
1181 {
1182         int i;
1183         int t;
1184         inline_node *child;
1185
1186         assert(iln);
1187         assert(rd);
1188
1189         child = iln->children;
1190         if (child) {
1191                 do {
1192                         inline_locals(child,rd);
1193                         child = child->next;
1194                 } while (child != iln->children);
1195         }
1196
1197         assert(iln->regdata);
1198
1199         for (i=0; i<iln->m->maxlocals; ++i) {
1200                 for (t=TYPE_INT; t<=TYPE_ADR; ++t) {
1201                         DOLOG( printf("local %d type=%d in ",i,iln->regdata->locals[i][t].type); method_println(iln->m); );
1202                         if (iln->regdata->locals[i][t].type >= 0) {
1203                                 rd->locals[iln->localsoffset + i][t].type = iln->regdata->locals[i][t].type;
1204                                 rd->locals[iln->localsoffset + i][t].flags |= iln->regdata->locals[i][t].flags;
1205                         }
1206                 }
1207         }
1208
1209         if (iln->regdata->memuse > rd->memuse)
1210                 rd->memuse = iln->regdata->memuse;
1211         if (iln->regdata->argintreguse > rd->argintreguse)
1212                 rd->argintreguse = iln->regdata->argintreguse;
1213         if (iln->regdata->argfltreguse > rd->argfltreguse)
1214                 rd->argfltreguse = iln->regdata->argfltreguse;
1215 }
1216
1217 static void inline_stack_interfaces(inline_node *iln,registerdata *rd)
1218 {
1219         int i;
1220         int d;
1221         basicblock *bptr;
1222         stackptr sp;
1223
1224         assert(iln);
1225         assert(rd);
1226         assert(rd->interfaces);
1227
1228         bptr = iln->inlined_basicblocks;
1229         for (i=0; i<iln->cumul_basicblockcount; ++i, ++bptr) {
1230                 DOLOG( printf("INLINE STACK INTERFACE block L%03d\n",bptr->debug_nr) );
1231                 DOLOG( printf("\toutstack = ");debug_dump_stack(bptr->outstack);printf("\n") );
1232                 DOLOG( printf("\tinstack = ");debug_dump_stack(bptr->outstack);printf("\n") );
1233
1234                 assert(bptr->outdepth == stack_depth(bptr->outstack));
1235                 assert(bptr->indepth == stack_depth(bptr->instack));
1236
1237                 sp = bptr->outstack;
1238                 d = bptr->outdepth - 1;
1239                 while (sp) {
1240                         if ((sp->varkind == STACKVAR) && (sp->varnum > d)) {
1241                                 sp->varkind = TEMPVAR;
1242                         }
1243                         else {
1244                                 sp->varkind = STACKVAR;
1245                                 sp->varnum = d;
1246                         }
1247                         DOLOG( printf("INLINE STACK INTERFACE L%03d outstack d=%d varkind=%d varnum=%d type=%d flags=%01x\n",
1248                                         bptr->debug_nr,d,sp->varkind,sp->varnum,sp->type,sp->flags) );
1249                         rd->interfaces[d][sp->type].type = sp->type;
1250                         rd->interfaces[d][sp->type].flags |= sp->flags;
1251                         d--;
1252                         sp = sp->prev;
1253                 }
1254
1255                 sp = bptr->instack;
1256                 d = bptr->indepth - 1;
1257                 while (sp) {
1258                         rd->interfaces[d][sp->type].type = sp->type;
1259                         if (sp->varkind == STACKVAR && (sp->flags & SAVEDVAR)) {
1260                                 rd->interfaces[d][sp->type].flags |= SAVEDVAR;
1261                         }
1262                         DOLOG( printf("INLINE STACK INTERFACE L%03d instack d=%d varkind=%d varnum=%d type=%d flags=%01x\n",
1263                                         bptr->debug_nr,d,sp->varkind,sp->varnum,sp->type,sp->flags) );
1264                         d--;
1265                         sp = sp->prev;
1266                 }
1267         }
1268 }
1269
1270 static bool inline_inline_intern(methodinfo *m,jitdata *jd, inline_node *iln)
1271 {
1272         basicblock *bptr;
1273         s4 len;
1274         instruction *iptr;
1275         stackptr o_dst;
1276         stackptr o_curstack;
1277         int opcode;                                   /* invocation opcode */
1278         methodinfo *callee;
1279         inline_node *calleenode;
1280         inline_node *active;
1281         stackptr sp;
1282         s4 i;
1283         bool isstatic;
1284         exceptiontable **handlers;
1285         s4 nhandlers;
1286
1287         assert(jd);
1288         assert(iln);
1289
1290         /* initialize cumulative counters */
1291
1292         iln->cumul_maxstack = iln->n_callerstackdepth + m->maxstack + 1 /* XXX builtins */;
1293         iln->cumul_maxlocals = iln->localsoffset + m->maxlocals;
1294         iln->cumul_exceptiontablelength += m->exceptiontablelength;
1295
1296         /* iterate over basic blocks */
1297
1298         bptr = m->basicblocks;
1299         for (; bptr; bptr = bptr->next) {
1300
1301                 iln->cumul_basicblockcount++;
1302
1303                 /* extra stackslots */
1304                 iln->cumul_stackcount += iln->n_callerstackdepth;
1305
1306                 if (bptr->flags < BBREACHED)
1307                         continue;
1308
1309                 /* allocate the buffer of active exception handlers */
1310                 /* XXX this wastes some memory, but probably it does not matter */
1311
1312                 handlers = DMNEW(exceptiontable*, m->exceptiontablelength + 1);
1313
1314                 /* determine the active exception handlers for this block     */
1315                 /* XXX maybe the handlers of a block should be part of our IR */
1316                 nhandlers = 0;
1317                 for (i = 0; i < m->exceptiontablelength; ++i) {
1318                         if ((m->exceptiontable[i].start <= bptr) && (m->exceptiontable[i].end > bptr)) {
1319                                 handlers[nhandlers++] = m->exceptiontable + i;
1320                         }
1321                 }
1322                 handlers[nhandlers] = NULL;
1323
1324                 assert(bptr->stack);
1325
1326                 len = bptr->icount;
1327                 iptr = bptr->iinstr;
1328                 o_curstack = bptr->instack;
1329
1330                 iln->instructioncount += len;
1331                 iln->cumul_instructioncount += len;
1332
1333 #if 0
1334                 printf("ADD INSTRUCTIONS [%d]: %d, count=%d, cumulcount=%d\n",
1335                                 iln->depth,len,iln->instructioncount,iln->cumul_instructioncount);
1336 #endif
1337
1338                 while (--len >= 0) {
1339
1340                         opcode = iptr->opc;
1341                         o_dst = iptr->dst;
1342
1343                         switch (opcode) {
1344                                 case ICMD_IINC:
1345                                         /* XXX we cannot deal with IINC's stack hacking */
1346                                         return false;
1347
1348                                 case ICMD_LOOKUPSWITCH:
1349                                 case ICMD_TABLESWITCH:
1350                                         /* XXX these are not implemented, yet. */
1351                                         return false;
1352
1353                                 /****************************************/
1354                                 /* INVOKATIONS                          */
1355
1356                                 case ICMD_INVOKEVIRTUAL:
1357                                 case ICMD_INVOKESPECIAL:
1358                                 case ICMD_INVOKESTATIC:
1359                                 case ICMD_INVOKEINTERFACE:
1360                                         callee = (methodinfo *) iptr[0].val.a;
1361
1362                                         if (callee) {
1363                                                 if ((callee->flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE) || opcode == ICMD_INVOKESPECIAL)
1364                                                     && !(callee->flags & (ACC_NATIVE)))
1365                                                 {
1366                                                         if (iln->depth < 3) {
1367                                                                 for (active = iln; active; active = active->parent) {
1368                                                                         if (callee == active->m) {
1369                                                                                 DOLOG( printf("RECURSIVE!\n") );
1370                                                                                 goto dont_inline;
1371                                                                         }
1372                                                                 }
1373
1374                                                                 calleenode = DNEW(inline_node);
1375                                                                 memset(calleenode,0,sizeof(inline_node));
1376
1377                                                                 calleenode->ctx = iln->ctx;
1378                                                                 calleenode->m = callee;
1379                                                                 calleenode->synchronize = (callee->flags & ACC_SYNCHRONIZED);
1380                                                                 isstatic = (callee->flags & ACC_STATIC);
1381
1382                                                                 if (!inline_jit_compile(calleenode))
1383                                                                         return false;
1384
1385                                                                 /* info about the call site */
1386                                                                 calleenode->depth = iln->depth+1;
1387                                                                 calleenode->callerblock = bptr;
1388                                                                 calleenode->callerins = iptr;
1389                                                                 calleenode->callerpc = iptr - m->basicblocks->iinstr;
1390                                                                 calleenode->o_handlers = handlers;
1391
1392                                                                 /* info about the callee */
1393                                                                 calleenode->localsoffset = iln->localsoffset + m->maxlocals;
1394                                                                 calleenode->prolog_instructioncount = callee->parseddesc->paramcount;
1395                                                                 calleenode->epilog_instructioncount = 0;
1396                                                                 calleenode->extra_instructioncount = 0;
1397
1398                                                                 if (calleenode->synchronize) {
1399                                                                         methoddesc         *md;
1400                                                                         builtintable_entry *bte;
1401
1402                                                                         /* and exception handler */
1403                                                                         /* ALOAD, builtin_monitorexit, ATHROW */
1404                                                                         calleenode->extra_instructioncount += 3;
1405                                                                         /* stack elements used in handler */
1406                                                                         iln->cumul_stackcount += 2;
1407
1408                                                                         /* exception table entries */
1409                                                                         iln->cumul_exceptiontablelength += 1 + nhandlers;
1410
1411                                                                         bte = builtintable_get_internal(BUILTIN_monitorenter);
1412                                                                         md = bte->md;
1413                                                                         if (md->memuse > calleenode->regdata->memuse)
1414                                                                                 calleenode->regdata->memuse = md->memuse;
1415                                                                         if (md->argintreguse > calleenode->regdata->argintreguse)
1416                                                                                 calleenode->regdata->argintreguse = md->argintreguse;
1417
1418                                                                         /* XXX
1419                                                                         bte = builtintable_get_internal(BUILTIN_staticmonitorenter);
1420                                                                         md = bte->md;
1421                                                                         if (md->memuse > calleenode->regdata->memuse)
1422                                                                                 calleenode->regdata->memuse = md->memuse;
1423                                                                         if (md->argintreguse > calleenode->regdata->argintreguse)
1424                                                                                 calleenode->regdata->argintreguse = md->argintreguse;
1425                                                                                 */
1426
1427                                                                         bte = builtintable_get_internal(BUILTIN_monitorexit);
1428                                                                         md = bte->md;
1429                                                                         if (md->memuse > calleenode->regdata->memuse)
1430                                                                                 calleenode->regdata->memuse = md->memuse;
1431                                                                         if (md->argintreguse > calleenode->regdata->argintreguse)
1432                                                                                 calleenode->regdata->argintreguse = md->argintreguse;
1433
1434                                                                         iln->ctx->calls_others = true;
1435                                                                 }
1436
1437                                                                 calleenode->stackcount = callee->stackcount;
1438                                                                 calleenode->cumul_stackcount = callee->stackcount;
1439
1440                                                                 /* see how deep the stack is below the arguments */
1441                                                                 sp = o_curstack;
1442                                                                 for (i=0; sp; sp = sp->prev)
1443                                                                         i++;
1444                                                                 calleenode->n_callerstackdepth = iln->n_callerstackdepth + i - callee->parseddesc->paramcount;
1445
1446                                                                 insert_inline_node(iln,calleenode);
1447
1448                                                                 if (!inline_inline_intern(callee,jd,calleenode))
1449                                                                         return false;
1450
1451                                                                 if (calleenode->synchronize) {
1452                                                                         /* add exception handler block */
1453                                                                         iln->ctx->master->cumul_basicblockcount++;
1454                                                                 }
1455
1456                                                                 iln->cumul_instructioncount += calleenode->prolog_instructioncount;
1457                                                                 iln->cumul_instructioncount += calleenode->epilog_instructioncount;
1458                                                                 iln->cumul_instructioncount += calleenode->extra_instructioncount;
1459                                                                 iln->cumul_instructioncount += calleenode->cumul_instructioncount - 1/*invoke*/ + 2 /*INLINE_START|END*/;
1460                                                                 iln->cumul_stackcount += calleenode->cumul_stackcount;
1461
1462                                                                 /* XXX extra block after inlined call */
1463                                                                 iln->cumul_stackcount += calleenode->n_callerstackdepth;
1464                                                                 iln->cumul_basicblockcount += 1;
1465
1466                                                                 iln->cumul_basicblockcount += calleenode->cumul_basicblockcount;
1467                                                                 iln->cumul_exceptiontablelength += calleenode->cumul_exceptiontablelength;
1468                                                                 if (calleenode->cumul_maxstack > iln->cumul_maxstack)
1469                                                                         iln->cumul_maxstack = calleenode->cumul_maxstack;
1470                                                                 if (calleenode->cumul_maxlocals > iln->cumul_maxlocals)
1471                                                                         iln->cumul_maxlocals = calleenode->cumul_maxlocals;
1472                                                         }
1473                                                 }
1474                                         }
1475 dont_inline:
1476
1477                                         break;
1478                         }
1479
1480                         o_curstack = o_dst;
1481                         ++iptr;
1482                 }
1483
1484                 /* end of basic block */
1485         }
1486
1487         return true;
1488 }
1489
1490 static void inline_write_exception_handlers(inline_node *master,inline_node *iln)
1491 {
1492         basicblock *n_bptr;
1493         stackptr n_curstack;
1494         instruction *n_ins;
1495         inline_node *child;
1496         builtintable_entry *bte;
1497
1498         child = iln->children;
1499         if (child) {
1500                 do {
1501                         inline_write_exception_handlers(master,child);
1502                         child = child->next;
1503                 } while (child != iln->children);
1504         }
1505
1506         if (iln->synchronize) {
1507                 /* create the monitorexit handler */
1508                 n_bptr = create_block(master,NULL,NULL,1 /*XXX*/);
1509                 n_bptr->type = BBTYPE_EXH;
1510                 n_bptr->flags = BBFINISHED;
1511
1512                 iln->handler_monitorexit = n_bptr;
1513
1514                 n_curstack = n_bptr->instack;
1515
1516                 /* ACONST / ALOAD */
1517
1518                 n_curstack = inline_new_stackslot(master,n_curstack,TYPE_ADR);
1519
1520                 n_ins = master->inlined_iinstr_cursor++;
1521                 if (iln->m->flags & ACC_STATIC) {
1522                         n_ins->opc = ICMD_ACONST;
1523                         n_ins->val.a = iln->m->class;
1524                         n_ins->target = class_get_self_classref(iln->m->class);
1525                 }
1526                 else {
1527                         n_ins->opc = ICMD_ALOAD;
1528                         n_ins->op1 = iln->localsoffset; /* XXX */
1529                 }
1530                 n_ins->dst = n_curstack;
1531                 n_ins->line = 0;
1532
1533                 /* MONITOREXIT */
1534
1535                 n_curstack = n_curstack->prev;
1536
1537                 bte = builtintable_get_internal(BUILTIN_monitorexit);
1538
1539                 n_ins = master->inlined_iinstr_cursor++;
1540                 n_ins->opc = ICMD_BUILTIN;
1541                 n_ins->val.a = bte;
1542                 n_ins->dst = n_curstack;
1543                 n_ins->line = 0;
1544
1545                 /* ATHROW */
1546
1547                 n_curstack = n_curstack->prev;
1548
1549                 n_ins = master->inlined_iinstr_cursor++;
1550                 n_ins->opc = ICMD_ATHROW;
1551                 n_ins->dst = n_curstack;
1552                 n_ins->line = 0;
1553
1554                 /* close basic block */
1555
1556                 n_bptr->outstack = n_curstack;
1557                 n_bptr->outdepth = stack_depth(n_curstack); /* XXX */
1558                 n_bptr->icount = 3;
1559         }
1560 }
1561
1562 static bool test_inlining(inline_node *iln,jitdata *jd,
1563                 methodinfo **resultmethod, jitdata **resultjd)
1564 {
1565         instruction *n_ins;
1566         stackptr n_stack;
1567         basicblock *n_bb;
1568         methodinfo *n_method;
1569         exceptiontable *n_ext;
1570         exceptiontable *prevext;
1571         codegendata *n_cd;
1572         registerdata *n_rd;
1573         jitdata *n_jd;
1574
1575
1576         static int debug_verify_inlined_code = 1;
1577 #ifndef NDEBUG
1578         static int debug_compile_inlined_code_counter = 0;
1579 #endif
1580
1581         assert(iln && jd && resultmethod && resultjd);
1582
1583         *resultmethod = iln->m;
1584         *resultjd = jd;
1585
1586 #if 0
1587         if (debug_compile_inlined_code_counter >5)
1588                 return false;
1589 #endif
1590
1591         n_ins = DMNEW(instruction,iln->cumul_instructioncount);
1592         iln->inlined_iinstr = n_ins;
1593
1594         n_stack = DMNEW(stackelement,iln->cumul_stackcount);
1595         iln->n_inlined_stack = n_stack;
1596         iln->ctx->n_debug_stackbase = n_stack;
1597
1598         n_bb = DMNEW(basicblock,iln->cumul_basicblockcount);
1599         iln->inlined_basicblocks = n_bb;
1600
1601         iln->ctx->blockmap = DMNEW(inline_block_map,iln->cumul_basicblockcount);
1602
1603         rewrite_method(iln);
1604         inline_write_exception_handlers(iln,iln);
1605
1606         /* end of basic blocks */
1607         if (iln->inlined_basicblocks_cursor > iln->inlined_basicblocks) {
1608                 iln->inlined_basicblocks_cursor[-1].next = NULL;
1609         }
1610
1611         if (iln->cumul_exceptiontablelength) {
1612                 exceptiontable *tableend;
1613
1614                 n_ext = DMNEW(exceptiontable,iln->cumul_exceptiontablelength);
1615                 prevext = NULL;
1616                 tableend = inline_exception_tables(iln,n_ext,&prevext);
1617                 assert(tableend == n_ext + iln->cumul_exceptiontablelength);
1618                 if (prevext)
1619                         prevext->down = NULL;
1620         }
1621         else {
1622                 n_ext = NULL;
1623         }
1624
1625         /*******************************************************************************/
1626
1627         n_method = NEW(methodinfo);
1628         memcpy(n_method,iln->m,sizeof(methodinfo));
1629         n_method->maxstack = iln->cumul_maxstack; /* XXX put into cd,rd */
1630         n_method->maxlocals = iln->cumul_maxlocals;
1631         n_method->basicblockcount = iln->cumul_basicblockcount;
1632         n_method->basicblocks = iln->inlined_basicblocks;
1633         n_method->basicblockindex = NULL;
1634         n_method->instructioncount = iln->cumul_instructioncount;
1635         n_method->instructions = iln->inlined_iinstr;
1636         n_method->stackcount = iln->cumul_stackcount;
1637         n_method->stack = iln->n_inlined_stack;
1638
1639         n_method->exceptiontablelength = iln->cumul_exceptiontablelength;
1640         n_method->exceptiontable = n_ext;
1641         n_method->linenumbercount = 0;
1642
1643         n_jd = DNEW(jitdata);
1644         n_jd->flags = 0;
1645         n_jd->m = n_method;
1646
1647         if (iln->ctx->calls_others) {
1648                 n_method->isleafmethod = false;
1649         }
1650
1651         n_jd->code = code_codeinfo_new(n_method);
1652
1653         n_cd = DNEW(codegendata);
1654         n_jd->cd = n_cd;
1655         memcpy(n_cd,jd->cd,sizeof(codegendata));
1656         n_cd->method = n_method;
1657         n_cd->maxstack = n_method->maxstack;
1658         n_cd->maxlocals = n_method->maxlocals;
1659         n_cd->exceptiontablelength = n_method->exceptiontablelength;
1660         n_cd->exceptiontable = n_method->exceptiontable;
1661
1662         n_rd = DNEW(registerdata);
1663         n_jd->rd = n_rd;
1664         reg_setup(n_jd);
1665
1666         iln->regdata = jd->rd;
1667         inline_locals(iln,n_rd);
1668         DOLOG( printf("INLINING STACK INTERFACES FOR "); method_println(iln->m) );
1669         inline_stack_interfaces(iln,n_rd);
1670
1671         if (debug_verify_inlined_code) {
1672                 debug_verify_inlined_code = 0;
1673                 DOLOG( printf("VERIFYING INLINED RESULT...\n") );
1674                 if (!typecheck(n_jd)) {
1675                         *exceptionptr = NULL;
1676                         DOLOG( printf("XXX INLINED RESULT DID NOT PASS VERIFIER XXX\n") );
1677                         return false;
1678                 }
1679                 else {
1680                         DOLOG( printf("VERIFICATION PASSED.\n") );
1681                 }
1682                 debug_verify_inlined_code = 1;
1683         }
1684
1685 #ifndef NDEBUG
1686 #if 1
1687         if (n_method->instructioncount >= inline_debug_min_size && n_method->instructioncount <= inline_debug_max_size) {
1688            if (debug_compile_inlined_code_counter >= inline_debug_start_counter
1689                            && debug_compile_inlined_code_counter <= inline_debug_end_counter)
1690 #else
1691         if (
1692                 (strcmp(n_method->class->name->text,"java/lang/reflect/Array") == 0 &&
1693                 strcmp(n_method->name->text,"<clinit>") == 0 &&
1694                 strcmp(n_method->descriptor->text,"()V") == 0)
1695                 ||
1696                 (strcmp(n_method->class->name->text,"java/lang/VMClassLoader") == 0 &&
1697                 strcmp(n_method->name->text,"getSystemClassLoader") == 0 &&
1698                 strcmp(n_method->descriptor->text,"()Ljava/lang/ClassLoader;") == 0)
1699                 )
1700
1701         {
1702 #endif
1703 #endif /* NDEBUG */
1704            {
1705                         *resultmethod = n_method;
1706                         *resultjd = n_jd;
1707
1708 #ifndef NDEBUG
1709                         inline_count_methods++;
1710                         if (inline_debug_log_names)
1711                                 method_println(n_method);
1712
1713                         DOLOG(
1714                         printf("==== %d.INLINE ==================================================================\n",debug_compile_inlined_code_counter);
1715                         method_println(n_method);
1716                         stack_show_method(jd);
1717                         dump_inline_tree(iln);
1718                         stack_show_method(n_jd);
1719                         debug_dump_inlined_code(iln,n_method,n_cd,n_rd);
1720                         printf("-------- DONE -----------------------------------------------------------\n");
1721                         fflush(stdout);
1722                         );
1723 #endif
1724            }
1725
1726 #ifndef NDEBUG
1727                 debug_compile_inlined_code_counter++;
1728         }
1729 #endif
1730         return true;
1731 }
1732
1733 bool inline_inline(jitdata *jd, methodinfo **resultmethod,
1734                                    jitdata **resultjd)
1735 {
1736         inline_node *iln;
1737         methodinfo *m;
1738
1739         m = jd->m;
1740
1741         *resultmethod = m;
1742         *resultjd = jd;
1743
1744 #if 0
1745         printf("==== INLINE ==================================================================\n");
1746         method_println(m);
1747         stack_show_method(jd);
1748 #endif
1749
1750         iln = DNEW(inline_node);
1751         memset(iln,0,sizeof(inline_node));
1752
1753         iln->ctx = (inline_context *) DMNEW(u1,sizeof(inline_context) + sizeof(inline_stack_translation) * 1000 /* XXX */);
1754         memset(iln->ctx,0,sizeof(inline_context));
1755         iln->ctx->master = iln;
1756         iln->ctx->stacktranslationstart = iln->ctx->stacktranslation - 1;
1757         iln->ctx->calls_others = false;
1758         iln->m = m;
1759
1760         /* we cannot use m->instructioncount because it may be greater than
1761          * the actual number of instructions in the basic blocks. */
1762         iln->instructioncount = 0;
1763         iln->cumul_instructioncount = 0;
1764
1765         iln->stackcount = m->stackcount;
1766         iln->cumul_stackcount = m->stackcount;
1767
1768         if (inline_inline_intern(m,jd,iln)) {
1769
1770 #if 0
1771                 printf("==== TEST INLINE =============================================================\n");
1772                 method_println(m);
1773 #endif
1774
1775                 if (iln->children)
1776                         test_inlining(iln,jd,resultmethod,resultjd);
1777         }
1778
1779 #if 0
1780         printf("-------- DONE -----------------------------------------------------------\n");
1781         fflush(stdout);
1782 #endif
1783
1784         return true;
1785 }
1786
1787 /*
1788  * These are local overrides for various environment variables in Emacs.
1789  * Please do not remove this and leave it at the end of the file, where
1790  * Emacs will automagically detect them.
1791  * ---------------------------------------------------------------------
1792  * Local variables:
1793  * mode: c
1794  * indent-tabs-mode: t
1795  * c-basic-offset: 4
1796  * tab-width: 4
1797  * End:
1798  * vim:noexpandtab:sw=4:ts=4:
1799  */