src/vm/jit/optimizing/escape.c

   1 /* srcontainsc/vm/optimizing/escape.c
   2
   3    Copyright (C) 2008
   4    CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22 */
  23
  24 #include "vm/jit/jit.h"
  25 #include "vmcore/class.h"
  26 #include "vmcore/classcache.h"
  27 #include "vm/jit/optimizing/escape.h"
  28
  29 /*** escape_state *************************************************************/
  30
  31 const char *escape_state_to_string(escape_state_t escape_state) {
  32 #       define str(x) case x: return #x;
  33         switch (escape_state) {
  34                 str(ESCAPE_UNKNOWN)
  35                 str(ESCAPE_NONE)
  36                 str(ESCAPE_METHOD)
  37                 str(ESCAPE_METHOD_RETURN)
  38                 str(ESCAPE_GLOBAL)
  39                 default: return "???";
  40         }
  41 #       undef str
  42 }
  43
  44 /*** instruction **************************************************************/
  45
  46 static inline s2 instruction_get_opcode(const instruction *iptr) {
  47         if (iptr->opc == ICMD_BUILTIN) {
  48                 return iptr->sx.s23.s3.bte->opcode;
  49         } else {
  50                 return iptr->opc;
  51         }
  52 }
  53
  54 static inline bool instruction_is_unresolved(const instruction *iptr) {
  55         return iptr->flags.bits & INS_FLAG_UNRESOLVED;
  56 }
  57
  58 static inline s4 instruction_field_type(const instruction *iptr) {
  59         if (instruction_is_unresolved(iptr)) {
  60                 return iptr->sx.s23.s3.uf->fieldref->parseddesc.fd->type;
  61         } else {
  62                 return iptr->sx.s23.s3.fmiref->p.field->type;
  63         }
  64 }
  65
  66 static inline s4 instruction_s1(const instruction *iptr) {
  67         return iptr->s1.varindex;
  68 }
  69
  70 static inline s4 instruction_s2(const instruction *iptr) {
  71         return iptr->sx.s23.s2.varindex;
  72 }
  73
  74 static inline s4 instruction_s3(const instruction *iptr) {
  75         return iptr->sx.s23.s3.varindex;
  76 }
  77
  78 static inline s4 instruction_dst(const instruction *iptr) {
  79         return iptr->dst.varindex;
  80 }
  81
  82 static inline s4 instruction_arg(const instruction *iptr, int arg) {
  83         return iptr->sx.s23.s2.args[arg];
  84 }
  85
  86 static inline bool instruction_is_class_constant(const instruction *iptr) {
  87         return iptr->flags.bits & INS_FLAG_CLASS;
  88 }
  89
  90 static inline classinfo *instruction_classinfo(const instruction *iptr) {
  91         return iptr->sx.val.c.cls;
  92 }
  93
  94 static inline methodinfo *instruction_local_methodinfo(const instruction *iptr) {
  95         if (instruction_is_unresolved(iptr)) {
  96                 return NULL;
  97         } else {
  98                 return iptr->sx.s23.s3.fmiref->p.method;
  99         }
 100 }
 101
 102 static inline int instruction_dst_type(const instruction *iptr, jitdata *jd) {
 103         return VAROP(iptr->dst)->type;
 104 }
 105
 106 static inline int instruction_return_type(const instruction *iptr) {
 107         return instruction_call_site(iptr)->returntype.type;
 108 }
 109
 110 static inline s4 instruction_arg_type(const instruction *iptr, int arg) {
 111         methoddesc *md = instruction_call_site(iptr);
 112         assert(0 <= arg && arg < md->paramcount);
 113         return md->paramtypes[arg].type;
 114 }
 115
 116 static inline int instruction_arg_count(const instruction *iptr) {
 117         return instruction_call_site(iptr)->paramcount;
 118 }
 119
 120 /*** instruction_list ********************************************************/
 121
 122 typedef struct instruction_list_item {
 123         instruction *instr;
 124         struct instruction_list_item *next;
 125 } instruction_list_item_t;
 126
 127 typedef struct {
 128         instruction_list_item_t *first;
 129 } instruction_list_t;
 130
 131 void instruction_list_init(instruction_list_t *list) {
 132         list->first = NULL;
 133 }
 134
 135 void instruction_list_add(instruction_list_t *list, instruction *instr) {
 136         instruction_list_item_t *item = DNEW(instruction_list_item_t);
 137         item->instr = instr;
 138         item->next = list->first;
 139         list->first = item;
 140 }
 141
 142 #define FOR_EACH_INSTRUCTION_LIST(list, it) \
 143         for ((it) = (list)->first; (it) != NULL; (it) = (it)->next)
 144
 145 /*** escape_analysis *********************************************************/
 146
 147 struct var_extra;
 148
 149 typedef struct {
 150         jitdata *jd;
 151
 152         instruction_list_t *allocations;
 153         instruction_list_t *getfields;
 154         instruction_list_t *monitors;
 155         instruction_list_t *returns;
 156
 157         struct var_extra **var;
 158
 159         unsigned adr_args_count;
 160
 161         bool verbose;
 162
 163 } escape_analysis_t;
 164
 165 /*** dependency_list_item ****************************************************/
 166
 167 typedef struct dependency_list_item {
 168         instruction *store;
 169         struct dependency_list_item *next;
 170 } dependency_list_item_t;
 171
 172 bool dependency_list_item_compare(const dependency_list_item_t *item, const instruction *load) {
 173
 174         instruction *store = item->store;
 175         utf *storen;
 176         const utf *loadn;
 177
 178         if (load->opc == ICMD_AALOAD) {
 179
 180                 if (store->opc != ICMD_AASTORE) {
 181                         return false;
 182                 }
 183
 184                 return true;
 185
 186         } else {
 187
 188                 if (store->opc != ICMD_PUTFIELD) {
 189                         return false;
 190                 }
 191
 192                 if (
 193                         instruction_is_unresolved(store) !=
 194                         instruction_is_unresolved(load)
 195                 ) {
 196                         return false;
 197                 }
 198
 199                 if (instruction_is_unresolved(store)) {
 200                         storen = store->sx.s23.s3.uf->fieldref->name;
 201                         loadn = load->sx.s23.s3.uf->fieldref->name;
 202                 } else {
 203                         storen = store->sx.s23.s3.fmiref->name;
 204                         loadn = load->sx.s23.s3.fmiref->name;
 205                 }
 206
 207                 /* TODO pointer equality ? */
 208
 209                 if (storen->blength != loadn->blength) {
 210                         return false;
 211                 }
 212
 213                 return (strcmp(storen->text, loadn->text) == 0);
 214         }
 215 }
 216
 217 /* TODO rename */
 218 s4 dependency_list_item_get_dependency(const dependency_list_item_t *item) {
 219         switch (item->store->opc) {
 220                 case ICMD_AASTORE:
 221                         return instruction_s3(item->store);
 222                 case ICMD_PUTFIELD:
 223                         return instruction_s2(item->store);
 224                 default:
 225                         assert(0);
 226                         return 0;
 227         }
 228 }
 229
 230 /*** dependency_list *********************************************************/
 231
 232 typedef struct {
 233         dependency_list_item_t *first;
 234         dependency_list_item_t *last;
 235 } dependency_list_t;
 236
 237 void dependency_list_init(dependency_list_t *dl) {
 238         dl->first = NULL;
 239         dl->last = NULL;
 240 }
 241
 242 void dependency_list_add(dependency_list_t *dl, instruction *store) {
 243         dependency_list_item_t *item = DNEW(dependency_list_item_t);
 244
 245         item->store = store;
 246         item->next = NULL;
 247
 248         if (dl->first == NULL) {
 249                 dl->first = item;
 250                 dl->last = item;
 251         } else {
 252                 dl->last->next = item;
 253                 dl->last = item;
 254         }
 255 }
 256
 257 void dependenCy_list_import(dependency_list_t *dl, dependency_list_t *other) {
 258
 259         if (other == NULL) {
 260                 return;
 261         }
 262
 263         if (dl->first == NULL) {
 264                 *dl = *other;
 265         } else {
 266                 dl->last->next = other->first;
 267                 dl->last = other->last;
 268         }
 269
 270         other->first = NULL;
 271         other->last = NULL;
 272
 273 }
 274
 275 #define FOR_EACH_DEPENDENCY_LIST(dl, it) \
 276         for ((it) = (dl)->first; (it) != NULL; (it) = (it)->next)
 277
 278 /*** var_extra ***************************************************************/
 279
 280 typedef struct var_extra {
 281         instruction *allocation;
 282         escape_state_t escape_state;
 283         s4 representant;
 284         dependency_list_t *dependency_list;
 285         unsigned contains_arg:1;
 286         unsigned contains_only_args:1;
 287         /*signed adr_arg_num:30;*/
 288 } var_extra_t;
 289
 290 static void var_extra_init(var_extra_t *ve) {
 291         ve->allocation = NULL;
 292         ve->escape_state = ESCAPE_NONE;
 293         ve->representant = -1;
 294         ve->dependency_list = NULL;
 295         ve->contains_arg = false;
 296         ve->contains_only_args = false;
 297         /*ve->adr_arg_num = -1;*/
 298 }
 299
 300 static inline var_extra_t *var_extra_get_no_alloc(const escape_analysis_t *e, s4 var) {
 301         return e->var[var];
 302 }
 303
 304 static var_extra_t* var_extra_get(escape_analysis_t *e, s4 var) {
 305         var_extra_t *ve;
 306
 307         assert(0 <= var && var <= e->jd->vartop);
 308
 309         ve = var_extra_get_no_alloc(e, var);
 310
 311         if (ve == NULL) {
 312                 ve = DNEW(var_extra_t);
 313                 var_extra_init(ve);
 314                 e->var[var] = ve;
 315         }
 316
 317         return ve;
 318 }
 319
 320 static s4 var_extra_get_representant(escape_analysis_t *e, s4 var) {
 321         var_extra_t *ve;
 322 #if !defined(NDEBUG)
 323         int ctr = 0;
 324 #endif
 325
 326         ve = var_extra_get(e, var);
 327
 328         while (ve->representant != -1) {
 329                 assert(ctr++ < 10000);
 330                 var = ve->representant;
 331                 ve = var_extra_get_no_alloc(e, var);
 332                 assert(ve);
 333         }
 334
 335         return var;
 336 }
 337
 338 static escape_state_t var_extra_get_escape_state(escape_analysis_t *e, s4 var) {
 339         var_extra_t *ve;
 340
 341         var = var_extra_get_representant(e, var);
 342         ve = var_extra_get(e, var);
 343
 344         return ve->escape_state;
 345 }
 346
 347 static void var_extra_set_escape_state(escape_analysis_t *e, s4 var, escape_state_t escape_state) {
 348         var_extra_t *ve;
 349
 350         var = var_extra_get_representant(e, var);
 351         ve = var_extra_get(e, var);
 352
 353         ve->escape_state = escape_state;
 354 }
 355
 356 static dependency_list_t *var_extra_get_dependency_list(escape_analysis_t *e, s4 var) {
 357         var_extra_t *ve;
 358
 359         var = var_extra_get_representant(e, var);
 360         ve = var_extra_get(e, var);
 361
 362         if (ve->dependency_list == NULL) {
 363                 ve->dependency_list = DNEW(dependency_list_t);
 364                 dependency_list_init(ve->dependency_list);
 365         }
 366
 367         return ve->dependency_list;
 368 }
 369
 370 /*** escape_analysis *********************************************************/
 371
 372 static void escape_analysis_init(escape_analysis_t *e, jitdata *jd) {
 373         e->jd = jd;
 374
 375         e->allocations = DNEW(instruction_list_t);
 376         instruction_list_init(e->allocations);
 377
 378         e->getfields = DNEW(instruction_list_t);
 379         instruction_list_init(e->getfields);
 380
 381         e->monitors = DNEW(instruction_list_t);
 382         instruction_list_init(e->monitors);
 383
 384         e->returns = DNEW(instruction_list_t);
 385         instruction_list_init(e->returns);
 386
 387         e->var = DMNEW(var_extra_t *, jd->vartop);
 388         MZERO(e->var, var_extra_t *, jd->vartop);
 389
 390         e->adr_args_count = 0;
 391
 392         e->verbose = (
 393                 strcmp(e->jd->m->clazz->name->text, "gnu/java/util/regex/RESyntax") == 0
 394                 && strcmp(e->jd->m->name->text, "<clinit>") == 0
 395         );
 396         e->verbose = 1;
 397 }
 398
 399 static void escape_analysis_set_allocation(escape_analysis_t *e, s4 var, instruction *iptr) {
 400         var_extra_get(e, var)->allocation = iptr;
 401 }
 402
 403 static instruction *escape_analysis_get_allocation(const escape_analysis_t *e, s4 var) {
 404         var_extra_t *ve = var_extra_get_no_alloc(e, var);
 405
 406         assert(ve != NULL);
 407         assert(ve->allocation != NULL);
 408
 409         return ve->allocation;
 410 }
 411
 412 static void escape_analysis_set_contains_argument(escape_analysis_t *e, s4 var) {
 413         var_extra_get(e, var)->contains_arg = true;
 414 }
 415
 416 static bool escape_analysis_get_contains_argument(escape_analysis_t *e, s4 var) {
 417         return var_extra_get(e, var)->contains_arg;
 418 }
 419
 420 static void escape_analysis_set_contains_only_arguments(escape_analysis_t *e, s4 var) {
 421         var_extra_get(e, var)->contains_only_args = true;
 422 }
 423
 424 static bool escape_analysis_get_contains_only_arguments(escape_analysis_t *e, s4 var) {
 425         return var_extra_get(e, var)->contains_only_args;
 426 }
 427
 428 /*
 429 static void escape_analysis_set_adr_arg_num(escape_analysis_t *e, s4 var, s4 num) {
 430         var_extra_get(e, var)->adr_arg_num = num;
 431 }
 432
 433 static s4 escape_analysis_get_adr_arg_num(escape_analysis_t *e, s4 var) {
 434         return var_extra_get(e, var)->adr_arg_num;
 435 }
 436 */
 437
 438 static bool escape_analysis_in_same_set(escape_analysis_t *e, s4 var1, s4 var2) {
 439         return var_extra_get_representant(e, var1) == var_extra_get_representant(e, var2);
 440 }
 441
 442 static void escape_analysis_ensure_state(escape_analysis_t *e, s4 var, escape_state_t escape_state) {
 443
 444         var_extra_t *ve;
 445         dependency_list_item_t *it;
 446
 447         var = var_extra_get_representant(e, var);
 448         ve = var_extra_get(e, var);
 449
 450         if (ve->escape_state < escape_state) {
 451                 if (e->verbose) {
 452                         printf(
 453                                 "escape state of %d %s => %s\n",
 454                                 var,
 455                                 escape_state_to_string(ve->escape_state),
 456                                 escape_state_to_string(escape_state)
 457                         );
 458                 }
 459                 ve->escape_state = escape_state;
 460                 if (ve->dependency_list != NULL) {
 461                         FOR_EACH_DEPENDENCY_LIST(ve->dependency_list, it) {
 462                                 if (e->verbose) {
 463                                         printf("propagating to %s@%d\n", icmd_table[it->store->opc].name, it->store->line);
 464                                 }
 465                                 escape_analysis_ensure_state(
 466                                         e,
 467                                         dependency_list_item_get_dependency(it),
 468                                         escape_state
 469                                 );
 470                         }
 471                 }
 472         }
 473 }
 474
 475 static escape_state_t escape_analysis_get_state(escape_analysis_t *e, s4 var) {
 476         return var_extra_get_escape_state(e, var);
 477 }
 478
 479 static classinfo *escape_analysis_classinfo_in_var(escape_analysis_t *e, s4 var) {
 480         instruction *iptr = escape_analysis_get_allocation(e, var);
 481
 482         if (iptr == NULL) {
 483                 return NULL;
 484         }
 485
 486         if (! instruction_is_class_constant(iptr)) {
 487                 return NULL;
 488         }
 489
 490         if (instruction_dst(iptr) != var) {
 491                 return NULL;
 492         }
 493
 494         if (instruction_is_unresolved(iptr)) {
 495                 return NULL;
 496         }
 497
 498         return instruction_classinfo(iptr);
 499 }
 500
 501 static void escape_analysis_merge(escape_analysis_t *e, s4 var1, s4 var2) {
 502
 503         var_extra_t *ve1, *ve2;
 504         dependency_list_item_t *itd;
 505         bool has_become_arg;
 506
 507         var1 = var_extra_get_representant(e, var1);
 508         var2 = var_extra_get_representant(e, var2);
 509
 510         /* Don't merge the same escape sets. */
 511
 512         if (var1 == var2) {
 513                 return;
 514         }
 515
 516         ve1 = var_extra_get(e, var1);
 517         ve2 = var_extra_get(e, var2);
 518
 519         /* Adjust escape state to maximal escape state. */
 520
 521         escape_analysis_ensure_state(e, var1, ve2->escape_state);
 522         escape_analysis_ensure_state(e, var2, ve1->escape_state);
 523
 524         /* Representant of var1 becomes the representant of var2. */
 525
 526         ve2->representant = var1;
 527
 528         /* Adjust is_arg to logical or. */
 529
 530         has_become_arg = ve1->contains_arg != ve2->contains_arg;
 531         ve1->contains_arg = ve1->contains_arg || ve2->contains_arg;
 532
 533         if (e->verbose && has_become_arg) printf("(%d,%d) has become arg.\n", var1, var2);
 534
 535         /* Merge list of dependencies. */
 536
 537         if (ve1->dependency_list == NULL) {
 538                 ve1->dependency_list = ve2->dependency_list;
 539         } else {
 540                 dependenCy_list_import(ve1->dependency_list, ve2->dependency_list);
 541         }
 542
 543         /* If one of the merged values is an argument but the other not,
 544            all dependencies of the newly created value escape globally. */
 545
 546         if (has_become_arg && ve1->dependency_list != NULL) {
 547                 FOR_EACH_DEPENDENCY_LIST(ve1->dependency_list, itd) {
 548                         escape_analysis_ensure_state(
 549                                 e,
 550                                 dependency_list_item_get_dependency(itd),
 551                                 ESCAPE_GLOBAL
 552                         );
 553                 }
 554         }
 555
 556         /* Adjust contains_only_args to logical and. */
 557
 558         ve1->contains_only_args = ve1->contains_only_args && ve2->contains_only_args;
 559
 560         /* Adjust address argument number contained in this var. */
 561
 562         /*
 563         if (ve1->adr_arg_num != ve2->adr_arg_num) {
 564                 ve1->adr_arg_num = -1;
 565         }
 566         */
 567 }
 568
 569 static void escape_analysis_add_dependency(escape_analysis_t *e, instruction *store) {
 570         s4 obj = instruction_s1(store);
 571         dependency_list_t *dl = var_extra_get_dependency_list(e, obj);
 572
 573         assert(store->opc == ICMD_PUTFIELD || store->opc == ICMD_AASTORE);
 574
 575         dependency_list_add(dl, store);
 576
 577         if (e->verbose) {
 578                 printf("dependency_list_add\n");
 579         }
 580 }
 581
 582 static void escape_analysis_process_instruction(escape_analysis_t *e, instruction *iptr) {
 583         jitdata *jd = e->jd;
 584         classinfo *c;
 585         s4 count;
 586         u1 *paramescape;
 587         unsigned i;
 588         instruction **iarg;
 589         methodinfo *mi;
 590         escape_state_t es;
 591
 592         if (e->verbose) {
 593                 printf("processing %s@%d\n", icmd_table[iptr->opc].name, iptr->line);
 594         }
 595
 596         switch (instruction_get_opcode(iptr)) {
 597                 case ICMD_ACONST:
 598
 599                         escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 600                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_NONE);
 601
 602                         break;
 603
 604                 case ICMD_NEW:
 605                         c = escape_analysis_classinfo_in_var(e, instruction_arg(iptr, 0));
 606
 607                         escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 608
 609                         if (c == NULL) {
 610                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 611                         } else if (c->finalizer != NULL) {
 612                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 613                         } else {
 614                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_NONE);
 615                         }
 616
 617                         instruction_list_add(e->allocations, iptr);
 618
 619                         break;
 620
 621                 case ICMD_MONITORENTER:
 622                 case ICMD_MONITOREXIT:
 623
 624                         instruction_list_add(e->monitors, iptr);
 625
 626                         break;
 627
 628                 case ICMD_NEWARRAY:
 629                 case ICMD_ANEWARRAY:
 630
 631                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 632                         escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 633                         instruction_list_add(e->allocations, iptr);
 634
 635                         break;
 636
 637                 case ICMD_PUTSTATIC:
 638                         if (instruction_field_type(iptr) == TYPE_ADR) {
 639                                 escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_GLOBAL);
 640                         }
 641                         break;
 642
 643                 case ICMD_PUTFIELD:
 644                         if (instruction_field_type(iptr) == TYPE_ADR) {
 645                                 if (escape_analysis_get_contains_argument(e, instruction_s1(iptr))) {
 646                                         escape_analysis_ensure_state(e, instruction_s2(iptr), ESCAPE_GLOBAL);
 647                                         /* If s1 is currently not an argument, but can contain one later because
 648                                            of a phi function, the merge function takes care to make all
 649                                            dependencies escape globally. */
 650                                 } else {
 651                                         escape_analysis_ensure_state(e, instruction_s2(iptr), escape_analysis_get_state(e, instruction_s1(iptr)));
 652                                         escape_analysis_add_dependency(e, iptr);
 653                                 }
 654                         }
 655                         break;
 656
 657                 case ICMD_AASTORE:
 658                         if (escape_analysis_get_contains_argument(e, instruction_s1(iptr))) {
 659                                 escape_analysis_ensure_state(e, instruction_s3(iptr), ESCAPE_GLOBAL);
 660                         } else {
 661                                 escape_analysis_ensure_state(e, instruction_s3(iptr), escape_analysis_get_state(e, instruction_s1(iptr)));
 662                                 escape_analysis_add_dependency(e, iptr);
 663                         }
 664                         break;
 665
 666                 case ICMD_GETSTATIC:
 667                         if (instruction_field_type(iptr) == TYPE_ADR) {
 668                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 669                                 escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 670                         }
 671                         break;
 672
 673                 case ICMD_GETFIELD:
 674                         if (instruction_field_type(iptr) == TYPE_ADR) {
 675
 676                                 if (escape_analysis_get_contains_argument(e, instruction_s1(iptr))) {
 677                                         /* Fields loaded from arguments escape globally.
 678                                            x = arg.foo;
 679                                            x.bar = y;
 680                                            => y escapes globally. */
 681                                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 682                                 } else {
 683                                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_NONE);
 684                                 }
 685
 686                                 escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 687
 688                                 instruction_list_add(e->getfields, iptr);
 689                         }
 690                         break;
 691
 692                 case ICMD_ARRAYLENGTH:
 693                         /* TODO */
 694                         break;
 695
 696                 case ICMD_AALOAD:
 697
 698                         if (escape_analysis_get_contains_argument(e, instruction_s1(iptr))) {
 699                                 /* If store into argument, escapes globally. See ICMD_GETFIELD. */
 700                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 701                         } else {
 702                                 escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_NONE);
 703                         }
 704
 705                         escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 706
 707                         instruction_list_add(e->getfields, iptr);
 708                         break;
 709
 710                 case ICMD_IF_ACMPEQ:
 711                 case ICMD_IF_ACMPNE:
 712                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_METHOD);
 713                         escape_analysis_ensure_state(e, instruction_s2(iptr), ESCAPE_METHOD);
 714                         break;
 715
 716                 case ICMD_IFNULL:
 717                 case ICMD_IFNONNULL:
 718                 case ICMD_CHECKNULL:
 719                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_METHOD);
 720                         break;
 721
 722                 case ICMD_CHECKCAST:
 723                         escape_analysis_merge(e, instruction_s1(iptr), instruction_dst(iptr));
 724                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_METHOD);
 725                         escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 726                         break;
 727
 728                 case ICMD_INSTANCEOF:
 729                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_METHOD);
 730                         break;
 731
 732                 case ICMD_INVOKESPECIAL:
 733                 case ICMD_INVOKEVIRTUAL:
 734                 case ICMD_INVOKEINTERFACE:
 735                 case ICMD_INVOKESTATIC:
 736                         count = instruction_arg_count(iptr);
 737                         mi = instruction_local_methodinfo(iptr);
 738                         paramescape = NULL;
 739
 740                         if (mi != NULL) {
 741                                 /* If the method could be resolved, it already is. */
 742                                 paramescape = mi->paramescape;
 743
 744                                 if (paramescape == NULL) {
 745                                         if (e->verbose) {
 746                                                 printf("BC escape analyzing callee %s/%s.\n", mi->clazz->name->text, mi->name->text);
 747                                         }
 748                                         bc_escape_analysis_perform(mi);
 749                                         paramescape = mi->paramescape;
 750                                 }
 751                         } else {
 752                                 if (e->verbose) {
 753                                         printf("Unresolved callee.\n");
 754                                 }
 755                         }
 756
 757                         if (iptr->opc == ICMD_INVOKEVIRTUAL || iptr->opc == ICMD_INVOKEINTERFACE) {
 758                                 if (mi != NULL && !method_profile_is_monomorphic(mi)) {
 759                                         paramescape = NULL;
 760                                 }
 761                         }
 762
 763                         /* Set the escape state of the return value.
 764                            This is: global if we down have information of the callee, or the callee
 765                            supplied escape state. */
 766
 767                         if (instruction_return_type(iptr) == TYPE_ADR) {
 768                                 if (paramescape == NULL) {
 769                                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_GLOBAL);
 770                                 } else {
 771                                         es = escape_state_from_u1(paramescape[-1]);
 772                                         escape_analysis_ensure_state(e, instruction_dst(iptr), es);
 773                                 }
 774                                 escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 775                         }
 776
 777                         for (i = 0; i < count; ++i) {
 778                                 if (instruction_arg_type(iptr, i) == TYPE_ADR) {
 779
 780                                         if (paramescape == NULL) {
 781                                                 escape_analysis_ensure_state(
 782                                                         e,
 783                                                         instruction_arg(iptr, i),
 784                                                         ESCAPE_GLOBAL
 785                                                 );
 786                                         } else if (escape_state_from_u1(*paramescape) < ESCAPE_METHOD) {
 787                                                 es = escape_state_from_u1(*paramescape);
 788
 789                                                 if (es < ESCAPE_METHOD) {
 790                                                         es = ESCAPE_METHOD;
 791                                                 }
 792
 793                                                 escape_analysis_ensure_state(e, instruction_arg(iptr, i), es);
 794
 795                                                 if (*paramescape & 0x80) {
 796                                                         /* Parameter can be returned from method.
 797                                                            This creates an alias to the retur value.
 798                                                            If the return value escapes, the ES of the parameter needs
 799                                                            to be adjusted. */
 800                                                         escape_analysis_merge(e, instruction_arg(iptr, i), instruction_dst(iptr));
 801                                                 }
 802                                         }
 803
 804                                         if (paramescape != NULL) {
 805                                                 ++paramescape;
 806                                         }
 807                                 }
 808                         }
 809
 810                         break;
 811
 812                 case ICMD_ATHROW:
 813                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_GLOBAL);
 814                         break;
 815
 816                 case ICMD_ARETURN:
 817                         /* If we return only arguments, the return value escapes only the method.
 818                            ESCAPE_METHOD for now, and check later, if a different value than an
 819                            argument is possibly returned. */
 820                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_METHOD_RETURN);
 821                         instruction_list_add(e->returns, iptr);
 822                         break;
 823
 824                 case ICMD_ALOAD:
 825                 case ICMD_ASTORE:
 826                 case ICMD_MOVE:
 827                 case ICMD_COPY:
 828                         if (instruction_dst_type(iptr, jd) == TYPE_ADR) {
 829                                 escape_analysis_merge(e, instruction_s1(iptr), instruction_dst(iptr));
 830                                 escape_analysis_set_allocation(e, instruction_dst(iptr), iptr);
 831                         }
 832                         break;
 833
 834                 case ICMD_PHI:
 835                         for (
 836                                 iarg = iptr->sx.s23.s2.iargs;
 837                                 iarg != iptr->sx.s23.s2.iargs + iptr->s1.argcount;
 838                                 ++iarg
 839                         ) {
 840                                 escape_analysis_merge(e, instruction_dst(iptr), instruction_dst(*iarg));
 841                         }
 842                         break;
 843
 844                 case ICMD_GETEXCEPTION:
 845                         escape_analysis_ensure_state(e, instruction_dst(iptr), ESCAPE_NONE);
 846                         break;
 847         }
 848 }
 849
 850 static void escape_analysis_process_instructions(escape_analysis_t *e) {
 851         basicblock *bptr;
 852         instruction *iptr;
 853
 854         FOR_EACH_BASICBLOCK(e->jd, bptr) {
 855
 856                 for (iptr = bptr->phis; iptr != bptr->phis + bptr->phicount; ++iptr) {
 857                         escape_analysis_process_instruction(e, iptr);
 858                 }
 859
 860                 FOR_EACH_INSTRUCTION(bptr, iptr) {
 861                         escape_analysis_process_instruction(e, iptr);
 862                 }
 863
 864         }
 865 }
 866
 867 static void escape_analysis_post_process_returns(escape_analysis_t *e) {
 868         instruction_list_item_t *iti;
 869         instruction *iptr;
 870
 871         FOR_EACH_INSTRUCTION_LIST(e->getfields, iti) {
 872                 iptr = iti->instr;
 873
 874                 if (! escape_analysis_get_contains_only_arguments(e, instruction_s1(iptr))) {
 875                         escape_analysis_ensure_state(e, instruction_s1(iptr), ESCAPE_GLOBAL);
 876                 }
 877         }
 878 }
 879
 880 static void escape_analysis_post_process_getfields(escape_analysis_t *e) {
 881         instruction_list_item_t *iti;
 882         dependency_list_item_t *itd;
 883         instruction *iptr;
 884         dependency_list_t *dl;
 885
 886         FOR_EACH_INSTRUCTION_LIST(e->getfields, iti) {
 887
 888                 iptr = iti->instr;
 889
 890                 /* Get the object the field/element is loaded from. */
 891
 892                 dl = var_extra_get_dependency_list(e, instruction_s1(iptr));
 893
 894                 /* Adjust escape state of all objects in the dependency list,
 895                    referenced via the field of this getfield/arraystore. */
 896
 897                 if (dl != NULL) {
 898                         FOR_EACH_DEPENDENCY_LIST(dl, itd) {
 899                                 if (dependency_list_item_compare(itd, iptr)) {
 900
 901                                         /* Fields match. Adjust escape state. */
 902
 903                                         escape_analysis_ensure_state(
 904                                                 e,
 905                                                 dependency_list_item_get_dependency(itd),
 906                                                 escape_analysis_get_state(e, instruction_dst(iptr))
 907                                         );
 908                                 }
 909                         }
 910                 }
 911
 912         }
 913 }
 914
 915 static void escape_analysis_mark_monitors(escape_analysis_t *e) {
 916         instruction_list_item_t *iti;
 917         instruction *iptr;
 918
 919         FOR_EACH_INSTRUCTION_LIST(e->monitors, iti) {
 920                 iptr = iti->instr;
 921
 922                 /* TODO if argument does not escape, mark. */
 923                 if (escape_analysis_get_state(e, instruction_arg(iptr, 0)) != ESCAPE_GLOBAL) {
 924                         printf("Monitor on thread local object!\n");
 925                 }
 926         }
 927 }
 928
 929 static void display_allocation(escape_analysis_t *e, const char *prefix, const instruction *iptr, escape_state_t es) {
 930         const char *cl = "WTF";
 931         classinfo *c;
 932
 933         if (instruction_get_opcode(iptr) == ICMD_NEW) {
 934                 c = escape_analysis_classinfo_in_var(e, instruction_arg(iptr, 0));
 935                 if (c) {
 936                         cl = c->name->text;
 937                 }
 938         }
 939
 940
 941         printf(
 942                 " %s %s %s: %s %s @%d %s\n",
 943                 prefix,
 944                 e->jd->m->clazz->name->text,
 945                 e->jd->m->name->text,
 946                 icmd_table[iptr->opc].name,
 947                 cl,
 948                 iptr->line,
 949                 escape_state_to_string(es)
 950         );
 951 }
 952
 953 static void escape_analysis_mark_allocations(escape_analysis_t *e) {
 954         instruction_list_item_t *iti;
 955         escape_state_t es;
 956 /*
 957         FOR_EACH_INSTRUCTION_LIST(e->allocations, iti) {
 958                 es = escape_analysis_get_state(e, instruction_dst(iti->instr));
 959                 if (es < ESCAPE_GLOBAL_THROUGH_METHOD) {
 960                         display_allocation(e, "****", iti->instr, es);
 961                 }
 962                 if (es == ESCAPE_GLOBAL_THROUGH_METHOD) {
 963                         display_allocation(e, "!!!!", iti->instr, es);
 964                 }
 965         }
 966 */
 967 }
 968
 969 static void escape_analysis_process_arguments(escape_analysis_t *e) {
 970         s4 p;
 971         s4 t;
 972         s4 l;
 973         s4 varindex;
 974         methoddesc *md;
 975
 976         md = e->jd->m->parseddesc;
 977
 978         for (p = 0, l = 0; p < md->paramcount; ++p) {
 979                 t = md->paramtypes[p].type;
 980                 varindex = e->jd->local_map[l * 5 + t];
 981                 if (t == TYPE_ADR) {
 982                         if (varindex != UNUSED) {
 983                                 escape_analysis_ensure_state(e, varindex, ESCAPE_NONE);
 984                                 escape_analysis_set_contains_argument(e, varindex);
 985                                 escape_analysis_set_contains_only_arguments(e, varindex);
 986                                 /*escape_analysis_set_adr_arg_num(e, varindex, e->adr_args_count);*/
 987                         }
 988                         e->adr_args_count += 1;
 989                 }
 990                 l += IS_2_WORD_TYPE(t) ? 2 : 1;
 991         }
 992 }
 993
 994 static void escape_analysis_export_arguments(escape_analysis_t *e) {
 995         s4 p;
 996         s4 t;
 997         s4 l;
 998         s4 varindex;
 999         methoddesc *md;
1000         u1 *paramescape;
1001         instruction_list_item_t *iti;
1002         instruction *iptr;
1003         escape_state_t es, re;
1004         int ret_val_is_adr;
1005
1006         md = e->jd->m->parseddesc;
1007
1008         ret_val_is_adr = (md->returntype.type == TYPE_ADR) ? 1 : 0;
1009
1010         paramescape = MNEW(u1, e->adr_args_count + ret_val_is_adr);
1011
1012         e->jd->m->paramescape = paramescape + ret_val_is_adr;
1013
1014         for (p = 0, l = 0; p < md->paramcount; ++p) {
1015                 t = md->paramtypes[p].type;
1016                 varindex = e->jd->local_map[l * 5 + t];
1017                 if (t == TYPE_ADR) {
1018                         if (varindex == UNUSED) {
1019                                 *paramescape = (u1)ESCAPE_NONE;
1020                         } else {
1021                                 es = escape_analysis_get_state(e, varindex);
1022
1023                                 if (es == ESCAPE_METHOD_RETURN) {
1024                                         *paramescape = escape_state_to_u1(ESCAPE_METHOD) | 0x80;
1025                                         if (e->verbose) {
1026                                                 printf("non-escaping adr parameter returned: %d\n", p);
1027                                         }
1028                                 } else {
1029                                         *paramescape = escape_state_to_u1(es);
1030                                 }
1031
1032                         }
1033                         paramescape += 1;
1034                 }
1035                 l += IS_2_WORD_TYPE(t) ? 2 : 1;
1036         }
1037
1038         if (ret_val_is_adr) {
1039                 /* Calculate escape state of return value as maximum escape state of all
1040                    values returned. */
1041
1042                 re = ESCAPE_NONE;
1043
1044                 FOR_EACH_INSTRUCTION_LIST(e->returns, iti) {
1045                         iptr = iti->instr;
1046                         es = escape_analysis_get_state(e, instruction_s1(iptr));
1047
1048                         if (es > re) {
1049                                 re = es;
1050                         }
1051                 }
1052
1053                 e->jd->m->paramescape[-1] = escape_state_to_u1(re);
1054         }
1055 }
1056
1057 static void escape_analysis_display(escape_analysis_t *e) {
1058         instruction_list_item_t *iti;
1059         var_extra_t *ve;
1060         instruction *iptr;
1061
1062         FOR_EACH_INSTRUCTION_LIST(e->allocations, iti) {
1063                 iptr = iti->instr;
1064                 ve = var_extra_get(e, instruction_dst(iptr));
1065                 printf(
1066                         "%s@%d: %s\n",
1067                         icmd_table[iptr->opc].name,
1068                         iptr->line,
1069                         escape_state_to_string(ve->escape_state)
1070                 );
1071         }
1072 }
1073
1074 void escape_analysis_perform(jitdata *jd) {
1075         escape_analysis_t *e;
1076
1077         jd->m->flags |= ACC_METHOD_EA;
1078
1079         e = DNEW(escape_analysis_t);
1080         escape_analysis_init(e, jd);
1081
1082         if (e->verbose)
1083                 printf("==== %s/%s ====\n", e->jd->m->clazz->name->text, e->jd->m->name->text);
1084
1085         escape_analysis_process_arguments(e);
1086         escape_analysis_process_instructions(e);
1087         escape_analysis_post_process_getfields(e);
1088         escape_analysis_post_process_returns(e);
1089
1090         escape_analysis_export_arguments(e);
1091         if (e->verbose) escape_analysis_display(e);
1092
1093         escape_analysis_mark_allocations(e);
1094         escape_analysis_mark_monitors(e);
1095
1096         jd->m->flags &= ~ACC_METHOD_EA;
1097 }
1098
1099 void escape_analysis_escape_check(void *vp) {
1100 }
1101
1102 /*** monomorphic *************************************************************/
1103
1104 monomorphic_t monomorphic_get(methodinfo *caller, methodinfo *callee) {
1105         monomorphic_t res = { 0, 0 };
1106 }
1107
1108 bool method_profile_is_monomorphic(methodinfo *m) {
1109 return 0;
1110 }
1111
1112 #if 0
1113
1114 /*** HACK to store method monomorphy information upon shutdown ****************/
1115
1116 #include <sqlite3.h>
1117
1118 bool method_profile_is_monomorphic(methodinfo *m) {
1119         static sqlite3 *db = NULL;
1120         static sqlite3_stmt *stmt = NULL;
1121         int ret;
1122
1123         if (db == NULL) {
1124                 assert(sqlite3_open("/home/peter/cacao-dev/profile.sqlite", &db) == SQLITE_OK);
1125                 assert(sqlite3_prepare(db, "SELECT count(*) FROM monomorphic where class=? and method=? and descriptor=?", -1, &stmt, 0) == SQLITE_OK);
1126         }
1127
1128         assert(sqlite3_bind_text(stmt, 1, m->clazz->name->text, -1, SQLITE_STATIC) == SQLITE_OK);
1129         assert(sqlite3_bind_text(stmt, 2, m->name->text, -1, SQLITE_STATIC) == SQLITE_OK);
1130         assert(sqlite3_bind_text(stmt, 3, m->descriptor->text, -1, SQLITE_STATIC) == SQLITE_OK);
1131
1132         assert(sqlite3_step(stmt) == SQLITE_ROW);
1133         ret = sqlite3_column_int(stmt, 0);
1134         assert(sqlite3_reset(stmt) == SQLITE_OK);
1135
1136         return ret;
1137 }
1138 void func(classinfo *c, void *arg) {
1139         methodinfo *it;
1140         sqlite3_stmt *stmt = (sqlite3_stmt *)arg;
1141         s4 flags;
1142         for (it = c->methods; it != c->methods + c->methodscount; ++it) {
1143                 flags = it->flags;
1144                 if (flags & (ACC_STATIC | ACC_FINAL | ACC_PRIVATE)) {
1145                         continue;
1146                 }
1147                 if ((flags & (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED | ACC_ABSTRACT)) ==
1148                         (ACC_METHOD_MONOMORPHIC | ACC_METHOD_IMPLEMENTED)) {
1149                                 assert(sqlite3_bind_text(stmt, 1, c->name->text, -1, SQLITE_STATIC) == SQLITE_OK);
1150                                 assert(sqlite3_bind_text(stmt, 2, it->name->text, -1, SQLITE_STATIC) == SQLITE_OK);
1151                                 assert(sqlite3_bind_text(stmt, 3, it->descriptor->text, -1, SQLITE_STATIC) == SQLITE_OK);
1152
1153                                 assert(sqlite3_step(stmt) == SQLITE_DONE);
1154                                 assert(sqlite3_reset(stmt) == SQLITE_OK);
1155                 }
1156         }
1157 }
1158
1159
1160 void method_profile_store() {
1161         sqlite3 *db = NULL;
1162         sqlite3_stmt *stmt;
1163         assert(sqlite3_open("/home/peter/cacao-dev/profile.sqlite", &db) == SQLITE_OK);
1164         assert(sqlite3_exec(db, "DELETE FROM monomorphic", NULL, NULL, NULL) == SQLITE_OK);
1165         assert(sqlite3_prepare(db, "INSERT INTO monomorphic (class, method, descriptor) VALUES (?,?,?)", -1, &stmt, 0) == SQLITE_OK);
1166         classcache_foreach_loaded_class(func, stmt);
1167         assert(sqlite3_finalize(stmt) == SQLITE_OK);
1168         assert(sqlite3_close(db) == SQLITE_OK);
1169 }
1170
1171 void iterate_classes() {
1172         return;
1173         method_profile_store();
1174
1175 }
1176
1177 #endif
1178
1179 #if defined(ENABLE_TLH)
1180 /*** TLH (Thread local heap) hack  ********************************************/
1181
1182 #include <sys/mman.h>
1183 #include "threads/thread.h"
1184
1185 #define TLH_MAX_SIZE (20 * 1024 * 1024)
1186
1187 void tlh_init(threadobject *t) {
1188         uint8_t *heap = (uint8_t *)mmap(
1189                 NULL,
1190                 TLH_MAX_SIZE,
1191                 PROT_READ|PROT_WRITE,
1192                 MAP_ANONYMOUS|MAP_PRIVATE,
1193                 -1,
1194                 0
1195         );
1196         uint8_t *red = (uint8_t *)mmap(
1197                 heap + TLH_MAX_SIZE - getpagesize(),
1198                 getpagesize(),
1199                 PROT_NONE,
1200                 MAP_ANONYMOUS|MAP_PRIVATE|MAP_FIXED,
1201                 -1,
1202                 0
1203         );
1204         assert(heap);
1205         assert(red);
1206         t->tlhstart = heap;
1207         t->tlhtop = heap;
1208         t->tlhbase = heap;
1209 }
1210
1211 void tlh_reset(threadobject *t) {
1212         t->tlhtop = t->tlhstart;
1213         t->tlhbase = t->tlhstart;
1214 }
1215
1216 void tlh_destroy(threadobject *t) {
1217         int res = munmap(t->tlhstart, TLH_MAX_SIZE - getpagesize());
1218         int res2 = munmap(t->tlhstart + TLH_MAX_SIZE - getpagesize(), getpagesize());
1219         assert(res);
1220         assert(res2);
1221 }
1222
1223 bool tlh_sigsegv_handler(void *addr) {
1224 }
1225
1226 #endif