src/vm/jit/optimizing/ssa3.c

   1 /* src/vm/optimizing/ssa3.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    SSA transformation PROTOTYPE based on:
  24
  25    Moessenboeck, H.,
  26    Adding Static Single Assignment Form and a Graph Coloring Register
  27    Allocator to the Java Hotspot Client Compiler, 2000
  28    (http://www.ssw.uni-linz.ac.at/Research/Reports/Report15.html)
  29
  30    TODO
  31
  32    * Adapt for exception handling [done]
  33    * Eliminiation of redundand PHI functions. [in progress]
  34    * Handle also inout variables. [done]
  35    * Create PHI functions lazyly, when they are used for the first time
  36      (I suspect that currently PHIs are created that are never used).
  37    * REWRITE. The code was never designed for producion. [done]
  38    * Unify access to phi args.
  39 */
  40
  41 #include "vm/jit/jit.h"
  42 #include "vm/global.h"
  43 #include "mm/memory.h"
  44 #include "mm/dumpmemory.h"
  45 #include "toolbox/list.h"
  46
  47 #include <limits.h>
  48 #include <stdio.h>
  49
  50 /*#define ELIMINATE_NOP_LOAD_STORE*/
  51 #define FIXME(x) x
  52 #define SSA_VERIFY
  53 /*#define SSA_VERBOSE */
  54
  55 /*
  56 __attribute__((always_inline))
  57 */
  58
  59 /*** phi ********************************************************************/
  60
  61 typedef enum {
  62         PHI_FLAG_USED,
  63         PHI_FLAG_REDUNDANT_ALL,
  64         PHI_FLAG_REDUNDANT_ONE
  65 } phi_flags_t;
  66
  67 static inline void phi_set_flag(instruction *iptr, phi_flags_t flag) {
  68         iptr->flags.bits |= (1 << flag);
  69 }
  70
  71 static inline void phi_clear_flag(instruction *iptr, phi_flags_t flag) {
  72         iptr->flags.bits &= ~(1 << flag);
  73 }
  74
  75 static inline bool phi_has_flag(const instruction *iptr, phi_flags_t flag) {
  76         return (iptr->flags.bits & (1 << flag)) != 0;
  77 }
  78
  79 static inline instruction *phi_get_subst(instruction *iptr) {
  80         return iptr->sx.s23.s2.iargs[-1];
  81 }
  82
  83 static inline bool phi_has_subst(const instruction *iptr) {
  84         return (iptr->sx.s23.s2.iargs[-1] != NULL);
  85 }
  86
  87
  88 static inline void phi_init(instruction *iptr, unsigned argcount, s4 index) {
  89         unsigned i;
  90
  91         iptr->opc = ICMD_PHI;
  92         iptr->flags.bits = 0;
  93         iptr->dst.varindex = 0;
  94         iptr->s1.argcount = argcount;
  95         iptr->sx.s23.s2.iargs = DMNEW(instruction *, argcount + 1);
  96         iptr->sx.s23.s2.iargs += 1;
  97         iptr->sx.s23.s3.javaindex = index;
  98
  99         /* subst field - If non-null, the phi function shall be replaced by the
 100            value produced by the subst instruction. */
 101         iptr->sx.s23.s2.iargs[-1] = NULL;
 102
 103 #if !defined(NDEBUG)
 104         for (i = 0; i < argcount; ++i) {
 105                 iptr->sx.s23.s2.iargs[i] = (instruction *)0x7fffffff;
 106         }
 107 #endif
 108 }
 109
 110 #define phi_assert_opc(iptr) assert(iptr->opc == ICMD_PHI)
 111
 112 #define phi_assert_arg(iptr, arg) assert(arg < iptr->s1.argcount)
 113
 114 static inline s4 phi_arg_count(const instruction *iptr) {
 115         phi_assert_opc(iptr);
 116         return iptr->s1.argcount;
 117 }
 118
 119 static inline instruction *phi_get_arg(const instruction *iptr, unsigned arg) {
 120         phi_assert_opc(iptr);
 121         phi_assert_arg(iptr, arg);
 122         return iptr->sx.s23.s2.iargs[arg];
 123 }
 124
 125 static inline s4 phi_get_arg_var(const instruction *iptr, unsigned arg) {
 126         phi_assert_opc(iptr);
 127         phi_assert_arg(iptr, arg);
 128         return iptr->sx.s23.s2.iargs[arg]->dst.varindex;
 129 }
 130
 131 static inline void phi_set_all_args(instruction *iptr, instruction *value) {
 132         unsigned i;
 133         phi_assert_opc(iptr);
 134         for (i = 0; i < iptr->s1.argcount; ++i) {
 135                 iptr->sx.s23.s2.iargs[i] = value;
 136         }
 137 }
 138
 139 static inline s4 phi_get_index(const instruction *iptr) {
 140         phi_assert_opc(iptr);
 141         return iptr->sx.s23.s3.javaindex;
 142 }
 143
 144 static inline s4 phi_get_dst(const instruction *iptr) {
 145         phi_assert_opc(iptr);
 146         return iptr->dst.varindex;
 147 }
 148
 149 static inline void phi_set_dst(instruction *iptr, s4 dst) {
 150         phi_assert_opc(iptr);
 151         iptr->dst.varindex = dst;
 152 }
 153
 154 static inline bool phi_get_used(const instruction *iptr) {
 155         phi_assert_opc(iptr);
 156         return phi_has_flag(iptr, PHI_FLAG_USED);
 157 }
 158
 159 static void phi_set_used(instruction *iptr) {
 160         phi_assert_opc(iptr);
 161         if (! phi_has_flag(iptr, PHI_FLAG_USED)) {
 162                 phi_set_flag(iptr, PHI_FLAG_USED);
 163                 /* TODO recurse into arguments */
 164         }
 165 }
 166
 167 static instruction *phi_resolve_use(instruction *use) {
 168         if (use != NULL) {
 169                 while (use->opc == ICMD_PHI) {
 170                         if (phi_has_subst(use)) {
 171                                 use = phi_get_subst(use);
 172                         } else {
 173                                 break;
 174                         }
 175                 }
 176         }
 177         return use;
 178 }
 179
 180 static inline void phi_set_arg(instruction *iptr, unsigned arg, instruction *value) {
 181         phi_assert_opc(iptr);
 182         phi_assert_arg(iptr, arg);
 183         assert(value != NULL);
 184         iptr->sx.s23.s2.iargs[arg] = value;
 185 }
 186
 187 static inline bool phi_is_redundant(const instruction *iptr) {
 188         return (
 189                 phi_has_flag(iptr, PHI_FLAG_REDUNDANT_ONE) ||
 190                 phi_has_flag(iptr, PHI_FLAG_REDUNDANT_ALL)
 191         );
 192 }
 193
 194 static inline void phi_create_copy(instruction *iptr, unsigned arg, instruction *copy) {
 195         phi_assert_opc(iptr);
 196         phi_assert_arg(iptr, arg);
 197         copy->dst.varindex = phi_get_dst(iptr);
 198         copy->s1.varindex = phi_resolve_use(phi_get_arg(iptr, arg))->dst.varindex;
 199         if (copy->dst.varindex == copy->s1.varindex || phi_is_redundant(iptr)) {
 200                 copy->opc = ICMD_NOP;
 201         } else {
 202                 copy->opc = ICMD_COPY;
 203         }
 204 }
 205
 206 #if !defined(NDEBUG)
 207 static void phi_print(const instruction *iptr) {
 208         unsigned i;
 209         instruction *use;
 210         printf("%d = phi(", iptr->dst.varindex);
 211         for (i = 0; i < iptr->s1.argcount; ++i) {
 212                 use = phi_resolve_use(iptr->sx.s23.s2.iargs[i]);
 213                 if (use) {
 214                         printf("%d, ", use->dst.varindex);
 215                 } else {
 216                         printf("null, ");
 217                 }
 218         }
 219         printf(")\n");
 220 }
 221 #endif
 222
 223 #define FOR_EACH_PHI_USE_CAST(iptr, it, cast) \
 224         for ( \
 225                 (it) = cast (iptr)->sx.s23.s2.iargs; \
 226                 (it) != cast (iptr)->sx.s23.s2.iargs + (iptr)->s1.argcount; \
 227                 ++(it) \
 228         )
 229
 230 #define FOR_EACH_PHI_USE(iptr, it) \
 231         FOR_EACH_PHI_USE_CAST(iptr, it, )
 232
 233 #define FOR_EACH_PHI_USE_CONST(iptr, it) \
 234         FOR_EACH_PHI_USE_CAST(iptr, it, (const instruction *))
 235
 236 static void phi_calculate_redundancy(instruction *iptr) {
 237
 238         s4 dst = iptr->dst.varindex;
 239         s4 use;
 240         instruction *iuse;
 241         instruction **ituse;
 242         unsigned num_different = 0;
 243         instruction *different;
 244
 245         if (phi_is_redundant(iptr)) return; /* XXX */
 246
 247         /* x = phi(x, y, x, x) ... PHI_FLAG_REDUNDANT_ONE
 248            x = phi(x, x, x, x) ... PHI_FLAG_REDUNDANT_ALL */
 249
 250         FOR_EACH_PHI_USE(iptr, ituse) {
 251                 iuse = phi_resolve_use(*ituse);
 252                 assert(iuse);
 253
 254                 use = iuse->dst.varindex;
 255
 256                 if (use != dst) {
 257                         different = *ituse;
 258                         num_different += 1;
 259                         if (num_different >= 2) {
 260                                 phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
 261                                 phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
 262                         }
 263                 }
 264         }
 265
 266         if (num_different == 1) {
 267                 /* Set the subst field of the instruction.
 268                    I.e. the instruction will be replaced by the value produced by y. */
 269                 iptr->sx.s23.s2.iargs[-1] = different;
 270
 271                 phi_set_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
 272                 phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
 273         } else if (num_different == 0) {
 274                 assert(0);
 275                 /*iptr->sx.s23.s2.iargs[-1] = iptr->sx.s23.s2.iargs[0];*/
 276
 277                 phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ONE);
 278                 phi_clear_flag(iptr, PHI_FLAG_REDUNDANT_ALL);
 279                 /*assert(0);*/
 280         }
 281 }
 282
 283
 284 /*** goto *******************************************************************/
 285
 286 static inline void goto_init(instruction *iptr, basicblock *dst) {
 287         iptr->opc = ICMD_GOTO;
 288         iptr->dst.block = dst;
 289 }
 290
 291 /*** instruction ***********************************************************/
 292
 293 static void instruction_get_uses(const instruction *iptr, s4 *buf, s4 **puses, unsigned *puses_count) {
 294         unsigned uses_count = 0;
 295
 296         switch (icmd_table[iptr->opc].dataflow) {
 297                 case DF_3_TO_0:
 298                 case DF_3_TO_1:
 299                         buf[2] = iptr->sx.s23.s3.varindex;
 300                         uses_count += 1;
 301
 302                 case DF_2_TO_0:
 303                 case DF_2_TO_1:
 304                         buf[1] = iptr->sx.s23.s2.varindex;
 305                         uses_count += 1;
 306
 307                 case DF_1_TO_0:
 308                 case DF_1_TO_1:
 309                 case DF_COPY:
 310                 case DF_MOVE:
 311                         buf[0] = iptr->s1.varindex;
 312                         uses_count += 1;
 313
 314                         *puses_count = uses_count;
 315                         *puses = buf;
 316                         break;
 317
 318                 case DF_N_TO_1:
 319                 case DF_INVOKE:
 320                 case DF_BUILTIN:
 321
 322                         *puses = iptr->sx.s23.s2.args;
 323                         *puses_count = iptr->s1.argcount;
 324                         break;
 325
 326                 default:
 327
 328                         *puses_count = 0;
 329                         break;
 330         }
 331 }
 332
 333 static inline void instruction_set_uses(instruction *iptr, s4 *buf, s4 *uses, unsigned uses_count) {
 334         if (uses == buf) {
 335                 switch (uses_count) {
 336                         case 3:
 337                                 iptr->sx.s23.s3.varindex = buf[2];
 338                         case 2:
 339                                 iptr->sx.s23.s2.varindex = buf[1];
 340                         case 1:
 341                                 iptr->s1.varindex = buf[0];
 342                 }
 343         }
 344 }
 345
 346 /*** vars *******************************************************************/
 347
 348 #define VARS_CATEGORY_SHIFT 29
 349 #define VARS_INDEX_MASK 0x1FFFFFFF
 350
 351 #define VARS_CATEGORY_LOCAL 0
 352 #define VARS_CATEGORY_STACK 1
 353 #define VARS_CATEGORY_OTHERS 2
 354
 355 #define VAR_TYPE_SUBSTITUED 666
 356
 357 #define OLD_INDEX_UNUSED -2
 358
 359 typedef struct {
 360         varinfo v;
 361         s4 old_index;
 362 } vars_item_t;
 363
 364 typedef struct {
 365         vars_item_t items[9000]; /* XXX hardcoded max */
 366         unsigned max;
 367         unsigned count;
 368         unsigned category;
 369 } vars_t;
 370
 371 static inline unsigned vars_add_item(vars_t *vs, const varinfo *item) {
 372         unsigned i = vs->count;
 373         assert(i < vs->max);
 374         vs->count += 1;
 375         vs->items[i].v = *item;
 376         vs->items[i].old_index = OLD_INDEX_UNUSED;
 377         return (vs->category << VARS_CATEGORY_SHIFT) | i;
 378 }
 379
 380 static inline unsigned vars_add(vars_t *vs) {
 381         unsigned i = vs->count;
 382         assert(i < vs->max);
 383         vs->count += 1;
 384         return (vs->category << VARS_CATEGORY_SHIFT) | i;
 385 }
 386
 387 static inline varinfo *vars_back(vars_t *vs) {
 388         assert(vs->count > 0);
 389         return &(vs->items[vs->count - 1].v);
 390 }
 391
 392 static inline void vars_init(vars_t *vs, unsigned category) {
 393         vs->max = sizeof(vs->items) / sizeof(vs->items[0]);
 394         vs->count = 0;
 395         assert((category & 0x3) == category);
 396         vs->category = category;
 397 }
 398
 399 static inline unsigned vars_get_category(unsigned varindex) {
 400         return (varindex >> VARS_CATEGORY_SHIFT);
 401 }
 402
 403 static inline unsigned vars_get_index(unsigned varindex) {
 404         return (varindex & VARS_INDEX_MASK);
 405 }
 406
 407 static void vars_subst(vars_t *vs, unsigned varindex, unsigned replacementindex) {
 408         varindex = vars_get_index(varindex);
 409         replacementindex = vars_get_index(replacementindex);
 410
 411         vs->items[varindex].v.type = VAR_TYPE_SUBSTITUED;
 412         vs->items[varindex].v.vv.ii[1] = replacementindex;
 413 }
 414
 415 static unsigned vars_resolve_subst(const vars_t *vs, unsigned varindex) {
 416 #if !defined(NDEBUG)
 417         unsigned loop_ctr = 0;
 418 #endif
 419         varindex = vars_get_index(varindex);
 420
 421         if (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) /*fprintf(stderr, "*")*/;
 422
 423         while (vs->items[varindex].v.type == VAR_TYPE_SUBSTITUED) {
 424                 assert(loop_ctr++ != vs->count);
 425                 varindex = vs->items[varindex].v.vv.ii[1];
 426         }
 427
 428         return (vs->category << VARS_CATEGORY_SHIFT) | varindex ;
 429 }
 430
 431 static void vars_copy_to_final(vars_t *vs, varinfo *dst) {
 432         const vars_item_t *it;
 433         unsigned subst;
 434
 435         for (it = vs->items; it != vs->items + vs->count; ++it, ++dst) {
 436
 437                 /* Copy variable. */
 438
 439                 *dst = it->v;
 440
 441                 /* Eliminate VAR_TYPE_SUBSTITUED as it leads to problems. */
 442
 443                 if (dst->type == VAR_TYPE_SUBSTITUED) {
 444                         subst = vars_get_index(vars_resolve_subst(vs, it - vs->items));
 445                         dst->type = vs->items[subst].v.type;
 446
 447                 }
 448         }
 449 }
 450
 451 static void vars_import(vars_t *vs, varinfo *v, unsigned count, s4 old_index) {
 452         vars_item_t *it;
 453
 454         assert((vs->count + count) <= vs->max);
 455
 456         it = vs->items + vs->count;
 457         vs->count += count;
 458
 459         while (count-- > 0) {
 460                 it->v = *v;
 461                 it->old_index = old_index;
 462                 it += 1;
 463                 v += 1;
 464                 old_index += 1;
 465         }
 466 }
 467
 468 static inline void vars_record_old_index(vars_t *vs, unsigned varindex, s4 old_index) {
 469         vars_item_t *item;
 470         varindex = vars_get_index(varindex);
 471
 472         assert(varindex < vs->count);
 473
 474         item = vs->items + varindex;
 475
 476         assert(
 477                 item->old_index == OLD_INDEX_UNUSED ||
 478                 item->old_index == old_index
 479         );
 480
 481         item->old_index = old_index;
 482 }
 483
 484 static inline s4 vars_get_old_index(vars_t *vs, unsigned varindex) {
 485         s4 old;
 486
 487         varindex = vars_get_index(varindex);
 488
 489         assert(varindex < vs->count);
 490         old = vs->items[varindex].old_index;
 491         assert(old != OLD_INDEX_UNUSED);
 492
 493         return old;
 494 }
 495
 496 /*** phis *******************************************************************/
 497
 498 typedef struct {
 499         instruction *items;
 500         unsigned max;
 501         unsigned count;
 502 } phis_t;
 503
 504 static inline void phis_init(phis_t *ps, unsigned max) {
 505         ps->max = max;
 506         ps->count = 0;
 507         ps->items = DMNEW(instruction, max);
 508 }
 509
 510 static inline instruction *phis_add(phis_t *ps) {
 511         unsigned i = ps->count;
 512         assert(i < ps->max);
 513         ps->count += 1;
 514         return ps->items + i;
 515 }
 516
 517 static inline instruction *phis_get(const phis_t *ps, unsigned i) {
 518         assert(i < ps->count);
 519         return ps->items + i;
 520 }
 521
 522 static inline bool phis_contains(const phis_t *ps, const instruction *phi) {
 523         return (ps->items <= phi) && (phi < (ps->items + ps->max));
 524 }
 525
 526 #define FOR_EACH_PHI_FUNCTION_(ps, it) \
 527         for ((it) = (ps)->items; (it) != (ps)->items + (ps)->count; ++(it)) \
 528
 529 #define FOR_EACH_PHI_FUNCTION(ps, it) \
 530                 FOR_EACH_PHI_FUNCTION_(ps, it) if (!phi_is_redundant((it)))
 531
 532 #if !defined(NDEBUG)
 533 FIXME() inline void phis_print(const phis_t *ps) {
 534         const instruction *iptr;
 535         FOR_EACH_PHI_FUNCTION(ps, iptr) {
 536                 phi_print(iptr);
 537         }
 538 }
 539 #endif
 540
 541 static inline void phis_copy_to(const phis_t *ps, instruction *dst) {
 542         MCOPY(
 543                 dst,
 544                 ps->items,
 545                 instruction,
 546                 ps->count
 547         );
 548 }
 549
 550 /*** state_array ************************************************************/
 551
 552 typedef struct {
 553         instruction **items;
 554         unsigned count;
 555 } state_array_t;
 556
 557 static inline void state_array_init(state_array_t *sa, unsigned count) {
 558         sa->items = NULL;
 559         sa->count = count;
 560 }
 561
 562 static inline bool state_array_has_items(const state_array_t *sa) {
 563         return (sa->items != NULL);
 564 }
 565
 566 static inline s4 state_array_get_var(const state_array_t *sa, unsigned index) {
 567         assert(index < sa->count);
 568         assert(sa->items[index]);
 569         return sa->items[index]->dst.varindex;
 570 }
 571
 572 static inline instruction *state_array_get(const state_array_t *sa, unsigned index) {
 573         assert(index < sa->count);
 574         return sa->items[index];
 575 }
 576
 577 static inline void state_array_set(const state_array_t *sa, unsigned index, instruction *value) {
 578         assert(index < sa->count);
 579         sa->items[index] = value;
 580 }
 581
 582 static inline void state_array_copy(state_array_t *sa, state_array_t *other) {
 583         assert(sa->count == other->count);
 584         MCOPY(sa->items, other->items, instruction *, sa->count);
 585 }
 586
 587 #define state_array_assert_items(sa) assert(state_array_has_items(sa) || (sa->count == 0))
 588 #define state_array_assert_no_items(sa) assert(! state_array_has_items(sa))
 589
 590 static inline void state_array_allocate_items(state_array_t *sa) {
 591         sa->items = DMNEW(instruction *, sa->count);
 592         MZERO(sa->items, instruction *, sa->count);
 593 }
 594
 595 /*** basicblock_chain *******************************************************/
 596
 597 typedef struct {
 598         basicblock *first;
 599         basicblock *last;
 600 } basicblock_chain_t;
 601
 602 static void basicblock_chain_init(basicblock_chain_t *bbc) {
 603         bbc->first = NULL;
 604         bbc->last = NULL;
 605 }
 606
 607 #define basicblock_chain_clear basicblock_chain_init
 608
 609 static void basicblock_chain_add(basicblock_chain_t *bbc, basicblock *bb) {
 610         if (bbc->first == NULL) {
 611                 assert(bbc->last == NULL);
 612                 assert(bb->next == NULL);
 613                 bbc->first = bb;
 614                 bbc->last = bb;
 615         } else {
 616                 assert(bbc->last->next == NULL);
 617                 bbc->last->next = bb;
 618                 bbc->last = bb;
 619         }
 620 }
 621
 622 static inline basicblock *basicblock_chain_front(basicblock_chain_t *bbc) {
 623         assert(bbc->first);
 624         return bbc->first;
 625 }
 626
 627 static inline basicblock *basicblock_chain_back(basicblock_chain_t *bbc) {
 628         assert(bbc->last);
 629         return bbc->last;
 630 }
 631
 632 static inline bool basicblock_chain_empty(const basicblock_chain_t *bbc) {
 633         return bbc->first == NULL;
 634 }
 635
 636 /*** exception_entry_chain ***************************************************/
 637
 638 typedef struct {
 639         exception_entry *first;
 640         exception_entry *last;
 641 } exception_entry_chain_t;
 642
 643 static void exception_entry_chain_init(exception_entry_chain_t *eec) {
 644         eec->first = NULL;
 645         eec->last = NULL;
 646 }
 647
 648 #define exception_entry_chain_clear exception_entry_chain_init
 649
 650 static void exception_entry_chain_add(exception_entry_chain_t *eec, exception_entry *ee) {
 651         if (eec->first == NULL) {
 652                 eec->first = ee;
 653                 eec->last = ee;
 654         } else {
 655                 eec->last->next = ee;
 656                 eec->last->down = ee;
 657                 eec->last = ee;
 658         }
 659 }
 660
 661 static inline bool exception_entry_chain_empty(const exception_entry_chain_t *eec) {
 662         return eec->first == NULL;
 663 }
 664
 665 static inline exception_entry *exception_entry_chain_back(exception_entry_chain_t *eec) {
 666         assert(eec->last);
 667         return eec->last;
 668 }
 669
 670 static inline exception_entry *exception_entry_chain_front(exception_entry_chain_t *eec) {
 671         assert(eec->first);
 672         return eec->first;
 673 }
 674
 675 /*** traversal **************************************************************/
 676
 677 typedef struct {
 678         unsigned (*var_num_to_index)(void *vp, s4 var);
 679         varinfo *(*index_to_initial_var)(void *vp, unsigned index);
 680         varinfo *(*var_num_to_varinfo)(void *vp, s4 var);
 681         unsigned (*variables_count)(void *vp);
 682 } traversal_ops_t;
 683
 684 typedef struct {
 685         phis_t *phis;
 686         state_array_t *state_array;
 687         void *ops_vp;
 688         traversal_ops_t *ops;
 689 } traversal_t;
 690
 691 /*** basicblock_info ********************************************************/
 692
 693 typedef struct basicblock_info {
 694         bool visited;
 695         bool active;
 696         bool traversed;
 697         unsigned backward_branches;
 698
 699         traversal_t *locals;
 700         traversal_t *stack;
 701
 702         basicblock_chain_t *subbasicblocks;
 703
 704         unsigned complete_predecessors;
 705
 706 #if defined(SSA_VERIFY)
 707         unsigned num_phi_elimination;
 708 #endif
 709
 710 } basicblock_info_t;
 711
 712 /*** traversal **************************************************************/
 713
 714 void traversal_init(traversal_t *t, unsigned count, void *ops_vp, traversal_ops_t *ops) {
 715         t->phis = DNEW(phis_t);
 716         phis_init(t->phis, count);
 717
 718         t->state_array = DNEW(state_array_t);
 719         state_array_init(t->state_array, count);
 720
 721         t->ops_vp = ops_vp;
 722         t->ops = ops;
 723 }
 724
 725 instruction *traversal_create_phi(traversal_t *t, vars_t *v, unsigned argcount, s4 index) {
 726         instruction *phi = phis_add(t->phis);
 727         s4 dst;
 728
 729         phi_init(phi, argcount, index);
 730         dst = vars_add_item(v, t->ops->index_to_initial_var(t->ops_vp, index));
 731         phi_set_dst(phi, dst);
 732
 733         state_array_set(t->state_array, index, phi);
 734
 735         vars_record_old_index(v, phi->dst.varindex, index);
 736
 737         return phi;
 738 }
 739
 740 static void traversal_rename_def(traversal_t *t, vars_t *vars, instruction *iptr) {
 741         const varinfo *v;
 742         unsigned index;
 743         s4 old;
 744
 745         state_array_assert_items(t->state_array);
 746
 747         v = t->ops->var_num_to_varinfo(t->ops_vp, iptr->dst.varindex);
 748         index = t->ops->var_num_to_index(t->ops_vp, iptr->dst.varindex);
 749
 750         old = iptr->dst.varindex;
 751         iptr->dst.varindex = vars_add_item(vars, v);
 752         state_array_set(t->state_array, index, iptr);
 753
 754         vars_record_old_index(vars, iptr->dst.varindex, index);
 755 }
 756
 757 static void traversal_rename_use(traversal_t *t, vars_t *vars, s4 *puse) {
 758         unsigned index;
 759         s4 old;
 760
 761         state_array_assert_items(t->state_array);
 762
 763         index = t->ops->var_num_to_index(t->ops_vp, *puse);
 764
 765         assert(state_array_get(t->state_array, index));
 766         old = *puse;
 767         *puse = state_array_get_var(t->state_array, index);
 768
 769         vars_record_old_index(vars, *puse, index);
 770 }
 771
 772 static inline unsigned traversal_variables_count(traversal_t *t) {
 773         return t->ops->variables_count(t->ops_vp);
 774 }
 775
 776 unsigned local_var_num_to_index(void *vp, s4 var) {
 777         return (unsigned)var;
 778 }
 779
 780 varinfo *local_index_to_initial_var(void *vp, unsigned index) {
 781         jitdata *jd = (jitdata *)vp;
 782         return jd->var + index;
 783 }
 784
 785 varinfo *local_var_num_to_varinfo(void *vp, s4 var) {
 786         jitdata *jd = (jitdata *)vp;
 787         return jd->var + var;
 788 }
 789
 790 unsigned local_variables_count(void *vp) {
 791         jitdata *jd = (jitdata *)vp;
 792         return jd->localcount;
 793 }
 794
 795 traversal_ops_t traversal_local_ops = {
 796         local_var_num_to_index,
 797         local_index_to_initial_var,
 798         local_var_num_to_varinfo,
 799         local_variables_count
 800 };
 801
 802 unsigned inout_var_num_to_index(void *vp, s4 var) {
 803         basicblock *bb = (basicblock *)vp;
 804         unsigned i;
 805
 806         for (i = 0; i < bb->indepth; ++i) {
 807                 if (bb->invars[i] == var) {
 808                         return i;
 809                 }
 810         }
 811
 812         for (i = 0; i < bb->outdepth; ++i) {
 813                 if (bb->outvars[i] == var) {
 814                         return i;
 815                 }
 816         }
 817
 818         assert(0);
 819 }
 820
 821 varinfo *inout_index_to_initial_var(void *vp, unsigned index) {
 822         basicblock *bb = (basicblock *)vp;
 823         jitdata *jd = (jitdata *)(((basicblock_info_t *)bb->vp)->locals->ops_vp); /* evil hack */
 824         assert(index < bb->indepth);
 825         return jd->var + bb->invars[index];
 826 }
 827
 828 varinfo *inout_var_num_to_varinfo(void *vp, s4 var) {
 829         basicblock *bb = (basicblock *)vp;
 830         jitdata *jd = (jitdata *)(((basicblock_info_t *)bb->vp)->locals->ops_vp); /* evil hack */
 831         return jd->var + var;
 832 }
 833
 834 unsigned inout_variables_count(void *vp) {
 835         basicblock *bb = (basicblock *)vp;
 836         return bb->indepth;
 837 }
 838
 839 traversal_ops_t traversal_inout_ops = {
 840         inout_var_num_to_index,
 841         inout_index_to_initial_var,
 842         inout_var_num_to_varinfo,
 843         inout_variables_count
 844 };
 845
 846 /*** basicblock_info ********************************************************/
 847
 848 void basicblock_info_init(basicblock_info_t *bbi, basicblock *bb, jitdata *jd) {
 849         MZERO(bbi, basicblock_info_t, 1);
 850
 851         bbi->locals = DNEW(traversal_t);
 852         traversal_init(bbi->locals, jd->localcount, jd, &traversal_local_ops);
 853
 854         bbi->stack = DNEW(traversal_t);
 855         traversal_init(bbi->stack, jd->maxinterfaces, bb, &traversal_inout_ops);
 856
 857         bbi->subbasicblocks = DNEW(basicblock_chain_t);
 858         basicblock_chain_init(bbi->subbasicblocks);
 859 }
 860
 861 /*** basicblock *************************************************************/
 862
 863 static inline basicblock_info_t *basicblock_info(basicblock *bb) {
 864         return (basicblock_info_t *)(bb->vp);
 865 }
 866
 867 #define bb_info basicblock_info
 868
 869 static unsigned basicblock_get_predecessor_count(basicblock *bb) {
 870         unsigned ret;
 871         basicblock **itpred;
 872
 873         ret = bb->predecessorcount;
 874
 875         FOR_EACH_EXPREDECESSOR(bb, itpred) {
 876                 ret += (*itpred)->exouts;
 877         }
 878
 879         return ret;
 880 }
 881
 882 static unsigned basicblock_get_predecessor_index(basicblock *from, basicblock *to) {
 883         basicblock **itpred;
 884         unsigned j = 0;
 885
 886         FOR_EACH_PREDECESSOR(to, itpred) {
 887                 if (*itpred == from) break;
 888                 j++;
 889         }
 890
 891         assert(j != to->predecessorcount);
 892
 893         return j;
 894 }
 895
 896 static unsigned basicblock_get_ex_predecessor_index(basicblock *from, unsigned pei, basicblock *to) {
 897         unsigned j;
 898         basicblock **itpred;
 899
 900         j = to->predecessorcount;
 901
 902         FOR_EACH_EXPREDECESSOR(to, itpred) {
 903                 if ((*itpred)->nr == from->nr) {
 904                         j += pei;
 905                         return j;
 906                 } else {
 907                         j += (*itpred)->exouts;
 908                 }
 909         }
 910
 911         assert(0);
 912 }
 913
 914 /*** ssa_info ***************************************************************/
 915
 916 typedef struct ssa_info {
 917         jitdata *jd;
 918
 919         vars_t *locals;
 920         vars_t *stack;
 921         vars_t *others;
 922
 923         s4 s_buf[3];
 924
 925         basicblock_chain_t *new_blocks;
 926
 927         struct {
 928                 s4 maxlocals;
 929                 s4 maxinterfaces;
 930                 s4 *local_map;
 931                 varinfo *var;
 932                 s4 vartop;
 933                 s4 varcount;
 934                 s4 localcount;
 935         } original;
 936
 937         unsigned keep_in_out:1;
 938
 939 } ssa_info, ssa_info_t;
 940
 941 void ssa_info_init(ssa_info_t *ssa, jitdata *jd) {
 942         ssa->jd = jd;
 943
 944         ssa->locals = DNEW(vars_t);
 945         vars_init(ssa->locals, VARS_CATEGORY_LOCAL);
 946
 947         /* Initialize first version of locals, that is always available. */
 948         vars_import(ssa->locals, jd->var, jd->localcount, 0);
 949
 950         ssa->stack = DNEW(vars_t);
 951         vars_init(ssa->stack, VARS_CATEGORY_STACK);
 952
 953         ssa->others = DNEW(vars_t);
 954         vars_init(ssa->others, VARS_CATEGORY_OTHERS);
 955
 956         ssa->new_blocks = DNEW(basicblock_chain_t);
 957         basicblock_chain_init(ssa->new_blocks);
 958
 959         ssa->original.maxlocals = jd->maxlocals;
 960         ssa->original.maxinterfaces = jd->maxinterfaces;
 961         ssa->original.local_map = jd->local_map;
 962         ssa->original.var = jd->var;
 963         ssa->original.vartop = jd->vartop;
 964         ssa->original.varcount = jd->varcount;
 965         ssa->original.localcount = jd->localcount;
 966
 967         ssa->keep_in_out = false;
 968 }
 969
 970 /*** others_mapping *********************************************************/
 971
 972 static inline void others_mapping_set(ssa_info *ssa, s4 var, s4 new_var) {
 973         ssa->jd->var[var].vv.ii[1] = new_var;
 974 }
 975
 976 static inline s4 others_mapping_get(const ssa_info *ssa, s4 var) {
 977         return ssa->jd->var[var].vv.ii[1];
 978 }
 979
 980 /*** code *******************************************************************/
 981
 982 void fix_exception_handlers(jitdata *jd) {
 983         basicblock *bptr;
 984         basicblock *exh = NULL;
 985         instruction *iptr;
 986         exception_entry *ee;
 987         size_t add_vars;
 988         size_t avail_vars;
 989         s4 v;
 990         basicblock_chain_t chain;
 991         basicblock *last = NULL;
 992         basicblock *marker = NULL;
 993
 994         if (jd->exceptiontablelength == 0) {
 995                 return;
 996         }
 997
 998         basicblock_chain_init(&chain);
 999
1000         /* We need to allocate new iovars */
1001
1002         avail_vars = (jd->varcount - jd->vartop);
1003         add_vars = jd->exceptiontablelength;
1004
1005         if (add_vars > avail_vars) {
1006                 add_vars -= avail_vars;
1007                 jd->var = DMREALLOC(jd->var, varinfo, jd->varcount, jd->varcount + add_vars);
1008                 jd->varcount += add_vars;
1009         }
1010
1011         /* For each exception handler block, create one block with a prologue block */
1012
1013         FOR_EACH_BASICBLOCK(jd, bptr) {
1014                 if (bptr->type == BBTYPE_EXH) {
1015
1016                         bptr->type = BBTYPE_STD;
1017                         bptr->predecessorcount = 0; /* legacy */
1018
1019                         /* Create basicblock with 2 instructions */
1020
1021                         exh = DNEW(basicblock);
1022                         MZERO(exh, basicblock, 1);
1023
1024                         iptr = DMNEW(instruction, 2);
1025                         MZERO(iptr, instruction, 2);
1026
1027                         /* Create new outvar */
1028
1029                         assert(jd->vartop < jd->varcount);
1030                         v = jd->vartop;
1031                         jd->vartop += 1;
1032                         jd->var[v].type = TYPE_ADR;
1033                         jd->var[v].flags = INOUT;
1034
1035                         exh->nr = jd->basicblockcount;
1036                         jd->basicblockcount += 1;
1037                         exh->mpc = -1;
1038                         exh->type = BBTYPE_EXH;
1039                         exh->icount = 2;
1040                         exh->iinstr = iptr;
1041                         exh->outdepth = 1;
1042                         exh->outvars = DNEW(s4);
1043                         exh->outvars[0] = v;
1044                         exh->predecessorcount = -1; /* legacy */
1045                         exh->flags = BBFINISHED;
1046                         exh->method = jd->m;
1047
1048                         basicblock_chain_add(&chain, exh);
1049
1050                         /* Get exception */
1051
1052                         iptr->opc = ICMD_GETEXCEPTION;
1053                         iptr->dst.varindex = v;
1054                         iptr += 1;
1055
1056                         /* Goto real exception handler */
1057
1058                         goto_init(iptr, bptr);
1059
1060                         bptr->vp = exh;
1061                 } else {
1062                         bptr->vp = NULL;
1063                 }
1064
1065                 if (bptr->next == NULL) {
1066                         marker = bptr;
1067                 } else {
1068                         last = bptr;
1069                 }
1070         }
1071
1072         /* Put the chain of exception handlers between just before the last
1073            basic block (end marker). */
1074
1075         if (! basicblock_chain_empty(&chain)) {
1076                 marker->nr = jd->basicblockcount;
1077                 basicblock_chain_back(&chain)->next = marker;
1078                 last->next = basicblock_chain_front(&chain);
1079
1080                 assert(last->nr + 1 == basicblock_chain_front(&chain)->nr);
1081                 assert(marker->nr == jd->basicblockcount);
1082         }
1083
1084         /* Replace all exception handlers in exception table with their respective
1085            prologue blocks. */
1086
1087         for (ee = jd->exceptiontable; ee; ee = ee->down) {
1088                 assert(ee->handler->vp);
1089                 ee->handler = ee->handler->vp;
1090         }
1091
1092 }
1093
1094 void unfix_exception_handlers(jitdata *jd) {
1095         basicblock *bptr, *exh;
1096         unsigned i;
1097         exception_entry *ee;
1098 #if !defined(NDEBUG)
1099         bool found = false;
1100 #endif
1101
1102         FOR_EACH_BASICBLOCK(jd, bptr) {
1103                 if (bptr->type == BBTYPE_EXH) {
1104                         assert(bptr->iinstr[1].opc == ICMD_GOTO);
1105                         exh = bptr->iinstr[1].dst.block;
1106
1107                         bptr->type = BBDELETED;
1108                         bptr->icount = 0;
1109                         bptr->indepth = 0;
1110                         bptr->outdepth = 0;
1111                         exh->type = BBTYPE_EXH;
1112                         bptr->vp = exh;
1113
1114                         /* bptr is no more a predecessor of exh */
1115
1116                         for (i = 0; i < exh->predecessorcount; ++i) {
1117                                 if (exh->predecessors[i] == bptr) {
1118                                         exh->predecessors[i] = exh->predecessors[exh->predecessorcount - 1];
1119                                         exh->predecessorcount -= 1;
1120 #if !defined(NDEBUG)
1121                                         found = true;
1122 #endif
1123                                         break;
1124                                 }
1125                         }
1126
1127                         assert(found);
1128
1129                 } else {
1130                         bptr->vp = NULL;
1131                 }
1132         }
1133
1134         for (ee = jd->exceptiontable; ee; ee = ee->down) {
1135                 assert(ee->handler->vp);
1136                 ee->handler = ee->handler->vp;
1137         }
1138 }
1139
1140 /*** ssa_enter ***************************************************************/
1141
1142 static void ssa_enter_mark_loops_intern(basicblock *bb, unsigned num_branches) {
1143         basicblock_info_t *bbi = bb_info(bb);
1144         basicblock **itsucc;
1145
1146         if (! bbi->visited) {
1147                 bbi->visited = true;
1148                 bbi->active = true;
1149                 FOR_EACH_SUCCESSOR(bb, itsucc) {
1150                         /* There is a single branch from bb into the successor. */
1151                         ssa_enter_mark_loops_intern(*itsucc, 1);
1152                 }
1153                 FOR_EACH_EXHANDLER(bb, itsucc) {
1154                         /* For exception handler type successors,
1155                            we count a branch into the exception handler from every PEI. */
1156                         ssa_enter_mark_loops_intern(*itsucc, bb->exouts);
1157                 }
1158                 bbi->active = false;
1159         } else if (bbi->active) {
1160                 bbi->backward_branches += num_branches;
1161         }
1162 }
1163
1164 static inline void ssa_enter_mark_loops(basicblock *bb) {
1165         ssa_enter_mark_loops_intern(bb, 1);
1166 }
1167
1168 static void ssa_enter_merge(
1169         traversal_t *src,
1170         traversal_t *dst,
1171         basicblock *bdst,
1172         unsigned predecessor_index,
1173         vars_t *vdst
1174 ) {
1175
1176         basicblock_info_t *dsti = bb_info(bdst);
1177         unsigned predecessor_count = basicblock_get_predecessor_count(bdst);
1178         instruction *phi;
1179         instruction *old;
1180         s4 i;
1181
1182         /* We are merging for the first time into this block. */
1183
1184         if (! state_array_has_items(dst->state_array)) {
1185
1186                 state_array_allocate_items(dst->state_array);
1187
1188                 if (dsti->backward_branches > 0) {
1189                         /* Loop header, create phi functions for all variables. */
1190                         for (i = 0; i < traversal_variables_count(dst); ++i) {
1191                                 phi = traversal_create_phi(dst, vdst, predecessor_count, i);
1192                                 /* No need to init, they will only be filled in later. */
1193                         }
1194                 } else {
1195                         state_array_copy(dst->state_array, src->state_array);
1196                         return;
1197                 }
1198         }
1199
1200         /* We are merging another block. */
1201
1202         /* Process every variable. */
1203
1204         for (i = 0; i < traversal_variables_count(dst); ++i) {
1205                 if (dsti->traversed) {
1206
1207                         /* Back edge, all phi functions are already created.
1208                            We only need to set their arguments. */
1209
1210                         phi_set_arg(
1211                                 phis_get(dst->phis, i),
1212                                 predecessor_index,
1213                                 state_array_get(src->state_array, i)
1214                         );
1215
1216                 } else if (state_array_get(dst->state_array, i) != state_array_get(src->state_array, i)) {
1217
1218                         /* A different definition of this var reaches the block.
1219                            We need to create a phi function. */
1220
1221                         if (phis_contains(dst->phis, state_array_get(dst->state_array, i))) {
1222                                 /* There is already a phi function created for this var.
1223                                    No need to create one. */
1224                         } else {
1225                                 /* Create a new phi function.
1226                                    Set all arguments to old value in state array. */
1227                                 old = state_array_get(dst->state_array, i);
1228                                 phi = traversal_create_phi(dst, vdst, predecessor_count, i);
1229                                 phi_set_all_args(phi, old);
1230                         }
1231
1232                         /* Set argument of phi function. */
1233
1234                         phi_set_arg(
1235                                 state_array_get(dst->state_array, i),
1236                                 predecessor_index,
1237                                 state_array_get(src->state_array, i)
1238                         );
1239                 }
1240         }
1241 }
1242
1243 static void ssa_enter_process_block(ssa_info *ssa, basicblock *bb);
1244 static bool ssa_enter_eliminate_redundant_phis(traversal_t *t, vars_t *vs, basicblock_info_t *bbi);
1245
1246 #if defined(SSA_VERIFY)
1247 static void ssa_enter_verify_no_redundant_phis(ssa_info_t *ssa) {
1248         basicblock *bptr;
1249         basicblock_info_t *bbi;
1250         instruction *itph;
1251         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
1252                 if (basicblock_reached(bptr)) {
1253                         bbi = bb_info(bptr);
1254                         FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
1255                                 if (! phi_is_redundant(itph)) {
1256                                         phi_calculate_redundancy(itph);
1257                                         assert(! phi_is_redundant(itph));
1258                                 }
1259                         }
1260                         FOR_EACH_PHI_FUNCTION(bbi->stack->phis, itph) {
1261                                 if (! phi_is_redundant(itph)) {
1262                                         phi_calculate_redundancy(itph);
1263                                         assert(! phi_is_redundant(itph));
1264                                 }
1265                         }
1266                 }
1267         }
1268 }
1269 #endif
1270
1271 static void ssa_enter_traverse(ssa_info_t *ssa, basicblock *bb) {
1272         basicblock **itsucc;
1273         basicblock_info_t *succi;
1274         basicblock_info_t *bbi = bb_info(bb);
1275         unsigned predecessor_count;
1276
1277         /* Process block */
1278
1279         ssa_enter_process_block(ssa, bb);
1280
1281         /* Recurse */
1282
1283         FOR_EACH_SUCCESSOR(bb, itsucc) {
1284
1285                 succi = bb_info(*itsucc);
1286
1287                 ssa_enter_merge(
1288                         bbi->locals,
1289                         succi->locals,
1290                         *itsucc,
1291                         basicblock_get_predecessor_index(bb, *itsucc),
1292                         ssa->locals
1293                 );
1294
1295                 ssa_enter_merge(
1296                         bbi->stack,
1297                         succi->stack,
1298                         *itsucc,
1299                         basicblock_get_predecessor_index(bb, *itsucc),
1300                         ssa->stack
1301                 );
1302
1303                 succi->complete_predecessors += 1;
1304
1305                 predecessor_count = basicblock_get_predecessor_count(*itsucc);
1306
1307                 if (
1308                         succi->complete_predecessors ==
1309                         (predecessor_count - succi->backward_branches)
1310                 ) {
1311                         ssa_enter_traverse(ssa, *itsucc);
1312                 }
1313
1314                 if (
1315                         (succi->complete_predecessors == predecessor_count) &&
1316                         (succi->backward_branches > 0)
1317                 ) {
1318 #if defined(SSA_VERIFY)
1319                         assert(succi->num_phi_elimination < 2);
1320                         succi->num_phi_elimination += 1;
1321 #endif
1322                         ssa_enter_eliminate_redundant_phis(succi->locals, ssa->locals, succi);
1323                         ssa_enter_eliminate_redundant_phis(succi->stack, ssa->stack, succi);
1324                 }
1325         }
1326
1327         FOR_EACH_EXHANDLER(bb, itsucc) {
1328
1329                 succi = bb_info(*itsucc);
1330
1331                 succi->complete_predecessors += bb->exouts; /* XXX this might be 0 */
1332
1333                 predecessor_count = basicblock_get_predecessor_count(*itsucc);
1334
1335                 if (
1336                         succi->complete_predecessors ==
1337                         (predecessor_count - succi->backward_branches)
1338                 ) {
1339                         ssa_enter_traverse(ssa, *itsucc);
1340                 }
1341
1342                 if (
1343                         (succi->complete_predecessors == predecessor_count) &&
1344                         (succi->backward_branches > 0)
1345                 ) {
1346 #if defined(SSA_VERIFY)
1347                         assert(succi->num_phi_elimination < 2);
1348                         succi->num_phi_elimination += 1;
1349 #endif
1350                         ssa_enter_eliminate_redundant_phis(succi->locals, ssa->locals, succi);
1351                         ssa_enter_eliminate_redundant_phis(succi->stack, ssa->stack, succi);
1352                 }
1353
1354         }
1355
1356 }
1357
1358 static void ssa_enter_process_pei(ssa_info *ssa, basicblock *bb, unsigned pei) {
1359         basicblock_info_t *bbi = bb_info(bb);
1360         basicblock_info_t *succi;
1361         basicblock **itsucc;
1362
1363         FOR_EACH_EXHANDLER(bb, itsucc) {
1364                 succi = bb_info(*itsucc);
1365
1366                 ssa_enter_merge(
1367                         bbi->locals,
1368                         succi->locals,
1369                         *itsucc,
1370                         basicblock_get_ex_predecessor_index(bb, pei, *itsucc),
1371                         ssa->locals
1372                 );
1373         }
1374 }
1375
1376 static FIXME(bool) ssa_enter_eliminate_redundant_phis(traversal_t *t, vars_t *vs, basicblock_info_t *FIXME(bbi)) {
1377
1378         instruction *itph;
1379         bool ret = false;
1380
1381         FOR_EACH_PHI_FUNCTION(t->phis, itph) {
1382
1383                 phi_calculate_redundancy(itph);
1384
1385                 /* If the phi function is redundant,
1386                    make the variable it defines point to the value defined by the substituing
1387                    instruction. */
1388
1389                 if (phi_is_redundant(itph)) {
1390                         vars_subst(vs, itph->dst.varindex, phi_get_subst(itph)->dst.varindex);
1391                         assert(bbi->backward_branches > 0);
1392                         ret = true;
1393                 }
1394         }
1395
1396         return ret;
1397 }
1398
1399 #if 0
1400 static void ssa_enter_post_eliminate_redundand_phi(
1401         ssa_info_t *ssa,
1402         instruction *phi,
1403         state_array *sa,
1404         basicblock *bptr
1405 ) {
1406         phi_calculate_redundancy(phi);
1407         phi_set_flag(PHI_FLAG_REDUNDANCY_CHECKED);
1408
1409         /* if redundancy changed and phi function escapes block */
1410
1411         /* for each successor */
1412 }
1413
1414 static void ssa_enter_post_eliminate_redundant_phis(ssa_info_t *ssa) {
1415         basicblock *bptr;
1416         basicblock_info_t *bbi;
1417         instruction *itph;
1418
1419         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
1420                 bbi = bb_info(bptr);
1421
1422                 if (bbi->backward_branches > 0) {
1423                         /* Redundant phi functions have the left hand side as operand.
1424                            This can happen by definition only in loop headers. */
1425
1426                         FOR_EACH_PHI_FUNCTION(bbi->locals, itph) {
1427                                 if (! phi_has_flag(PHI_FLAG_REDUNDANCY_CHECKED)) {
1428                                         /* Calculate redundancy? */
1429                                         /* Changed? */
1430                                         /* If yes recurse? */
1431                                 }
1432                         }
1433
1434                         FOR_EACH_PHI_FUNCTION(bbi->stack, itph) {
1435                         }
1436                 }
1437         }
1438 }
1439 #endif
1440
1441 static void ssa_enter_init_locals(state_array_t *sa) {
1442         unsigned i;
1443         instruction *iptr;
1444
1445         for (i = 0; i < sa->count; ++i) {
1446                 iptr = DNEW(instruction);
1447                 iptr->opc = ICMD_NOP;
1448                 iptr->dst.varindex = i;
1449                 state_array_set(sa, i, iptr);
1450         }
1451 }
1452
1453 static void ssa_enter_process_block(ssa_info *ssa, basicblock *bb) {
1454         basicblock_info_t *bbi = bb_info(bb);
1455         instruction *iptr;
1456         unsigned pei = 0;
1457         s4 *ituse;
1458         s4 *uses;
1459         unsigned uses_count;
1460         s4 old;
1461
1462         /* Every basic block can be traversed only once. */
1463
1464         assert(! bbi->traversed);
1465         bbi->traversed = true;
1466
1467         /* The root basicblock needs special treatment. */
1468
1469         if (bb->predecessorcount == 0 && bb->type != BBTYPE_EXH) {
1470                 state_array_assert_no_items(bbi->locals->state_array);
1471                 state_array_allocate_items(bbi->locals->state_array);
1472                 ssa_enter_init_locals(bbi->locals->state_array);
1473
1474                 state_array_assert_no_items(bbi->stack->state_array);
1475                 state_array_allocate_items(bbi->stack->state_array);
1476         }
1477
1478         /* Exception handlers have a clean stack. */
1479
1480         if (bb->type == BBTYPE_EXH) {
1481                 state_array_assert_no_items(bbi->stack->state_array);
1482                 state_array_allocate_items(bbi->stack->state_array);
1483         }
1484
1485         /* Some in/out vars get marked as INOUT in simplereg,
1486            and are not marked at this point.
1487            Mark them manually. */
1488
1489         for (ituse = bb->invars; ituse != bb->invars + bb->indepth; ++ituse) {
1490                 if (ssa->keep_in_out && ssa->jd->var[*ituse].type == TYPE_RET) {
1491                         continue;
1492                 }
1493                 ssa->jd->var[*ituse].flags |= INOUT;
1494                 ssa->jd->var[*ituse].flags &= ~PREALLOC;
1495         }
1496
1497         for (ituse = bb->outvars; ituse != bb->outvars + bb->outdepth; ++ituse) {
1498                 if (ssa->keep_in_out && ssa->jd->var[*ituse].type == TYPE_RET) {
1499                         continue;
1500                 }
1501                 ssa->jd->var[*ituse].flags |= INOUT;
1502                 ssa->jd->var[*ituse].flags &= ~PREALLOC;
1503         }
1504
1505         /* Process instructions */
1506
1507         state_array_assert_items(bbi->locals->state_array);
1508
1509         FOR_EACH_INSTRUCTION(bb, iptr) {
1510
1511 #if defined(ELIMINATE_NOP_LOAD_STORE)
1512
1513                 /* Kill NOP instructions of the form:
1514                    LOAD foo => foo
1515                    STORE foo => foo
1516                    As they create a lot of unnecessary definitions.
1517                    For performance, definitely eliminate them. However, keeping them is a
1518                    good stress test.
1519                 */
1520
1521                 if (
1522                         (icmd_table[iptr->opc].dataflow == DF_LOAD) ||
1523                         (icmd_table[iptr->opc].dataflow == DF_STORE)
1524                 ) {
1525                         if (iptr->dst.varindex == iptr->s1.varindex) {
1526                                 iptr->opc = ICMD_NOP;
1527                                 continue;
1528                         }
1529                 }
1530 #endif
1531
1532                 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
1533                         ssa_enter_process_pei(ssa, bb, pei++);
1534                 }
1535
1536                 instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
1537
1538                 for (ituse = uses; ituse != uses + uses_count; ++ituse) {
1539                         if (var_is_local(ssa->jd, *ituse)) {
1540                                 traversal_rename_use(
1541                                         bbi->locals,
1542                                         ssa->locals,
1543                                         ituse
1544                                 );
1545                         } else if (var_is_inout(ssa->jd, *ituse)) {
1546                                 traversal_rename_use(
1547                                         bbi->stack,
1548                                         ssa->stack,
1549                                         ituse
1550                                 );
1551                         } else {
1552                                 *ituse = others_mapping_get(ssa, *ituse);
1553                         }
1554                 }
1555
1556                 instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
1557
1558                 if (instruction_has_dst(iptr)) {
1559                         if (var_is_local(ssa->jd, iptr->dst.varindex)) {
1560                                 traversal_rename_def(
1561                                         bbi->locals,
1562                                         ssa->locals,
1563                                         iptr
1564                                 );
1565                         } else if (var_is_inout(ssa->jd, iptr->dst.varindex)) {
1566                                 traversal_rename_def(
1567                                         bbi->stack,
1568                                         ssa->stack,
1569                                         iptr
1570                                 );
1571                         } else {
1572                                 old = iptr->dst.varindex;
1573                                 iptr->dst.varindex = vars_add_item(
1574                                         ssa->others,
1575                                         ssa->jd->var + iptr->dst.varindex
1576                                 );
1577                                 vars_record_old_index(ssa->others, iptr->dst.varindex, old);
1578                                 others_mapping_set(ssa, old, iptr->dst.varindex);
1579                         }
1580                 }
1581         }
1582 }
1583
1584 /*
1585
1586  [locals.........................][interaces][others]
1587  [original locals][version > 1   ]
1588  <--------------- new locals --------------->
1589 */
1590
1591 static void ssa_enter_export_variables(ssa_info *ssa) {
1592         s4 vartop;
1593         varinfo *vars;
1594         s4 *it;
1595         unsigned i, j;
1596         jitdata *jd = ssa->jd;
1597         s4 *local_map;
1598
1599         vartop = ssa->locals->count + ssa->stack->count + ssa->others->count;
1600         vars = DMNEW(varinfo, vartop);
1601
1602         vars_copy_to_final(ssa->locals, vars);
1603         vars_copy_to_final(ssa->stack, vars + ssa->locals->count);
1604         vars_copy_to_final(ssa->others, vars + ssa->locals->count + ssa->stack->count);
1605
1606         jd->var = vars;
1607         jd->vartop = jd->varcount = vartop;
1608
1609         /* Grow local map to accomodate all new locals and iovars.
1610            But keep the local map for version 1 of locals, that contains the holes. */
1611
1612         local_map = DMNEW(
1613                 s4,
1614                 5 * (jd->maxlocals + ssa->locals->count + ssa->stack->count - jd->localcount)
1615         );
1616
1617         MCOPY(local_map, jd->local_map, s4, 5 * jd->maxlocals);
1618
1619         jd->local_map = local_map;
1620
1621         it = jd->local_map + (jd->maxlocals * 5); /* start adding entries here */
1622
1623         /* Add version > 1 of all locals */
1624
1625         for (i = jd->localcount; i < ssa->locals->count; ++i) {
1626                 for (j = 0; j < 5; ++j) {
1627                         if (jd->var[i].type != j) {
1628                                 *it = UNUSED;
1629                         } else {
1630                                 *it = i;
1631                         }
1632                         it += 1;
1633                 }
1634         }
1635
1636         /* Add all io vars. */
1637
1638         for (i = ssa->locals->count; i < ssa->locals->count + ssa->stack->count; ++i) {
1639                 for (j = 0; j < 5; ++j) {
1640                         if (jd->var[i].type != j) {
1641                                 *it = UNUSED;
1642                         } else {
1643                                 *it = i;
1644                         }
1645                         it += 1;
1646                 }
1647         }
1648
1649         /* Add locals. */
1650
1651         jd->maxlocals += (ssa->locals->count + ssa->stack->count - jd->localcount);
1652         jd->localcount = ssa->locals->count + ssa->stack->count;
1653
1654         /* Eliminate interfaces. */
1655
1656         jd->maxinterfaces = 0;
1657
1658 }
1659
1660 static void ssa_enter_export_phis(ssa_info_t *ssa) {
1661         basicblock *bptr;
1662         basicblock_info_t *bbi;
1663         instruction *dst;
1664
1665         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
1666                 bbi = bb_info(bptr);
1667                 if (bbi != NULL) {
1668                         bptr->phicount =
1669                                 bbi->locals->phis->count +
1670                                 bbi->stack->phis->count;
1671
1672                         bptr->phis = DMNEW(instruction, bptr->phicount);
1673
1674                         dst = bptr->phis;
1675
1676                         phis_copy_to(bbi->locals->phis, dst);
1677
1678                         dst += bbi->locals->phis->count;
1679
1680                         phis_copy_to(bbi->stack->phis, dst);
1681                 }
1682         }
1683 }
1684
1685 /* TODO rename */
1686 static inline void ssa_enter_eliminate_category(ssa_info_t *ssa, s4 *pvar) {
1687         switch (vars_get_category(*pvar)) {
1688                 case VARS_CATEGORY_LOCAL:
1689                         *pvar = vars_get_index(vars_resolve_subst(ssa->locals, *pvar));
1690                         break;
1691                 case VARS_CATEGORY_STACK:
1692                         *pvar = vars_get_index(vars_resolve_subst(ssa->stack, *pvar)) + ssa->locals->count;
1693                         break;
1694                 case VARS_CATEGORY_OTHERS:
1695                         *pvar = vars_get_index(*pvar) + ssa->locals->count + ssa->stack->count;
1696                         break;
1697         }
1698 }
1699
1700 /* TODO rename */
1701 void ssa_enter_eliminate_categories(ssa_info_t *ssa) {
1702         basicblock *bb;
1703         instruction *iptr;
1704         s4 *ituse, *uses;
1705         unsigned uses_count;
1706         basicblock_info_t *bbi;
1707         instruction *itph;
1708
1709         FOR_EACH_BASICBLOCK(ssa->jd, bb) {
1710
1711                 bbi = bb_info(bb);
1712
1713                 if (! ssa->keep_in_out) {
1714                         bb->indepth = 0;
1715                         bb->outdepth = 0;
1716                 }
1717
1718                 if (bbi != NULL) {
1719                         FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
1720                                 ssa_enter_eliminate_category(ssa, &(itph->dst.varindex));
1721                         }
1722
1723                         FOR_EACH_PHI_FUNCTION(bbi->stack->phis, itph) {
1724                                 ssa_enter_eliminate_category(ssa, &(itph->dst.varindex));
1725                         }
1726                 }
1727
1728                 FOR_EACH_INSTRUCTION(bb, iptr) {
1729                         if (instruction_has_dst(iptr)) {
1730                                 ssa_enter_eliminate_category(ssa, &(iptr->dst.varindex));
1731                         }
1732                         instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
1733                         for (ituse = uses; ituse != uses + uses_count; ++ituse) {
1734                                 ssa_enter_eliminate_category(ssa, ituse);
1735                         }
1736                         instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
1737                 }
1738         }
1739 }
1740
1741 static void ssa_enter_create_phi_graph(ssa_info *ssa) {
1742         basicblock *bptr;
1743         basicblock_info_t *bbi;
1744         instruction *itph;
1745         instruction **ituse;
1746         unsigned i;
1747         char path[PATH_MAX], *ppath;
1748         FILE *f;
1749
1750         snprintf(path, PATH_MAX, "|tmp|graphs|%s.%s.dot", ssa->jd->m->clazz->name->text, ssa->jd->m->name->text);
1751         for (ppath = path; *ppath; ++ppath) {
1752                 if (*ppath == '|') *ppath = '/';
1753                 else if (*ppath == '/') *ppath = '.';
1754         }
1755
1756         f = fopen(path, "w");
1757
1758         if (f == NULL) return;
1759
1760         fprintf(f, "digraph G {\n");
1761
1762         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
1763                 bbi = bb_info(bptr);
1764                 if (bbi != NULL) {
1765                         FOR_EACH_PHI_FUNCTION(bbi->locals->phis, itph) {
1766                                 i = 0;
1767                                 FOR_EACH_PHI_USE(itph, ituse) {
1768                                         if ((*ituse)->opc == ICMD_PHI) {
1769                                                 fprintf(f, "%d -> %d;\n", (*ituse)->dst.varindex, itph->dst.varindex);
1770                                         }
1771                                         i += 1;
1772                                 }
1773                         }
1774                 }
1775         }
1776
1777         fprintf(f, "};\n");
1778
1779         fclose(f);
1780 }
1781
1782 static basicblock *ssa_leave_create_transition_block_intern(
1783         ssa_info *ssa,
1784         basicblock *from,
1785         basicblock *to,
1786         unsigned predecessor_index,
1787         unsigned reserved_insns
1788 ) {
1789         basicblock *bb;
1790         instruction *iptr;
1791         instruction *itph;
1792         basicblock_info_t *toi;
1793
1794         toi = bb_info(to);
1795
1796         /* Create basicblock and instruction array. */
1797
1798         bb = DNEW(basicblock);
1799         MZERO(bb, basicblock, 1);
1800
1801         bb->nr = ssa->jd->basicblockcount;
1802         ssa->jd->basicblockcount += 1;
1803         bb->mpc = -1;
1804         bb->method = ssa->jd->m;
1805         bb->type = BBTYPE_STD;
1806         bb->icount =
1807                 reserved_insns +
1808                 toi->locals->phis->count +
1809                 toi->stack->phis->count +
1810                 1;
1811         bb->iinstr = DMNEW(instruction, bb->icount);
1812         MZERO(bb->iinstr, instruction, bb->icount);
1813
1814         /* Populate instruction array. */
1815
1816         iptr = bb->iinstr + reserved_insns;
1817
1818         /* Add phi moves. */
1819
1820         FOR_EACH_PHI_FUNCTION(toi->locals->phis, itph) {
1821                 phi_create_copy(itph, predecessor_index, iptr++);
1822         }
1823
1824         FOR_EACH_PHI_FUNCTION(toi->stack->phis, itph) {
1825                 phi_create_copy(itph, predecessor_index, iptr++);
1826         }
1827
1828         /* Add goto to real block. */
1829
1830         goto_init(iptr, to);
1831
1832         /* Add basicblock to chain of newly created basicblocks. */
1833
1834         basicblock_chain_add(ssa->new_blocks, bb);
1835
1836         return bb;
1837 }
1838
1839 static inline basicblock *ssa_leave_create_transition_block(
1840         ssa_info *ssa,
1841         basicblock *from,
1842         basicblock *to
1843 ) {
1844         return ssa_leave_create_transition_block_intern(
1845                 ssa,
1846                 from,
1847                 to,
1848                 basicblock_get_predecessor_index(from, to),
1849                 0
1850         );
1851 }
1852
1853 static void ssa_leave_create_fallthrough(ssa_info *ssa, basicblock *bptr) {
1854         unsigned predecessor_index;
1855         basicblock_info_t *toi;
1856         instruction *iptr;
1857         instruction *itph;
1858         unsigned icount;
1859
1860         if (bptr->next == NULL) {
1861                 /* No fallthrough. */
1862                 return;
1863         }
1864
1865         predecessor_index = basicblock_get_predecessor_index(bptr, bptr->next);
1866         toi = bb_info(bptr->next);
1867
1868         assert(toi);
1869
1870         /* Resize instruction array to accomodate all phi moves. */
1871
1872         icount = bptr->icount + toi->locals->phis->count + toi->stack->phis->count;
1873
1874         bptr->iinstr = DMREALLOC(
1875                 bptr->iinstr,
1876                 instruction,
1877                 bptr->icount,
1878                 icount
1879         );
1880
1881         iptr = bptr->iinstr + bptr->icount;
1882         bptr->icount = icount;
1883
1884         /* Create phi moves. */
1885
1886         FOR_EACH_PHI_FUNCTION(toi->locals->phis, itph) {
1887                 phi_create_copy(itph, predecessor_index, iptr++);
1888         }
1889
1890         FOR_EACH_PHI_FUNCTION(toi->stack->phis, itph) {
1891                 phi_create_copy(itph, predecessor_index, iptr++);
1892         }
1893 }
1894
1895 static void ssa_leave_create_phi_moves(ssa_info *ssa) {
1896         basicblock *bptr;
1897         instruction *iptr;
1898         basicblock *last = NULL;
1899
1900         s4 i, l;
1901         branch_target_t *table;
1902         lookup_target_t *lookup;
1903         bool has_fallthrough;
1904
1905         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
1906
1907                 if (bptr->next == NULL) {
1908                         last = bptr;
1909                 }
1910
1911                 if (bptr->vp == NULL) {
1912                         continue;
1913                 }
1914
1915                 if (! basicblock_reached(bptr)) {
1916                         continue;
1917                 }
1918
1919                 has_fallthrough = true;
1920
1921                 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
1922                         switch (icmd_table[iptr->opc].controlflow) {
1923                                 case CF_IF:
1924                                 case CF_RET:
1925                                 case CF_GOTO:
1926                                         iptr->dst.block =
1927                                                 ssa_leave_create_transition_block(ssa, bptr, iptr->dst.block);
1928                                         break;
1929                                 case CF_TABLE:
1930                                         table = iptr->dst.table;
1931                                         l = iptr->sx.s23.s2.tablelow;
1932                                         i = iptr->sx.s23.s3.tablehigh;
1933                                         i = i - l + 1;
1934                                         i += 1; /* default */
1935                                         while (--i >= 0) {
1936                                                 table->block =
1937                                                         ssa_leave_create_transition_block(ssa, bptr, table->block);
1938                                                 ++table;
1939                                         }
1940                                         break;
1941                                 case CF_LOOKUP:
1942                                         lookup = iptr->dst.lookup;
1943                                         i = iptr->sx.s23.s2.lookupcount;
1944                                         while (--i >= 0) {
1945                                                 lookup->target.block =
1946                                                         ssa_leave_create_transition_block(ssa, bptr, lookup->target.block);
1947                                                 lookup++;
1948                                         }
1949                                         iptr->sx.s23.s3.lookupdefault.block =
1950                                                 ssa_leave_create_transition_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
1951                                         break;
1952                                 case CF_JSR:
1953                                         iptr->sx.s23.s3.jsrtarget.block =
1954                                                 ssa_leave_create_transition_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
1955                                         break;
1956                         }
1957
1958                         if (
1959                                 (iptr->opc == ICMD_GOTO) ||
1960                                 (iptr->opc == ICMD_JSR) ||
1961                                 (iptr->opc == ICMD_RET) ||
1962                                 icmd_table[iptr->opc].controlflow == CF_END ||
1963                                 (iptr->opc == ICMD_TABLESWITCH) ||
1964                                 (iptr->opc == ICMD_LOOKUPSWITCH)
1965                         ) {
1966                                 has_fallthrough = false;
1967                         } else if (iptr->opc != ICMD_NOP) {
1968                                 has_fallthrough = true;
1969                         }
1970
1971                 }
1972
1973                 if (bptr->next == NULL) {
1974                         continue;
1975                 }
1976
1977                 if (! basicblock_reached(bptr->next)) {
1978                         continue;
1979                 }
1980
1981                 if (has_fallthrough) {
1982                         ssa_leave_create_fallthrough(ssa, bptr);
1983                 }
1984         }
1985
1986         /* Add chain of new basic blocks */
1987
1988         if (last != NULL && ! basicblock_chain_empty(ssa->new_blocks)) {
1989                 last->next = basicblock_chain_front(ssa->new_blocks);
1990         }
1991
1992 }
1993
1994 static basicblock *ssa_leave_split_basicblock_at(ssa_info *ssa, basicblock *bptr, instruction *iptr) {
1995
1996         basicblock_info_t *bbi = bb_info(bptr);
1997         unsigned iidx = iptr - bptr->iinstr;
1998         basicblock *newblock;
1999         basicblock *tosplit;
2000         unsigned ileft;
2001         unsigned pos;
2002
2003         assert(iidx < bptr->icount);
2004         assert(bbi);
2005
2006         /* If there are no subbasicblocks yet, we initialize the first one to be a
2007            copy of the original basicblock. */
2008
2009         if (basicblock_chain_empty(bbi->subbasicblocks)) {
2010                 newblock = DNEW(basicblock);
2011                 *newblock = *bptr;
2012                 newblock->next = NULL;
2013                 newblock->vp = NULL;
2014                 basicblock_chain_add(bbi->subbasicblocks, newblock);
2015         }
2016
2017         /* Find the subbasicblock that will be split:
2018            the one that cointains iptr. */
2019
2020         tosplit = basicblock_chain_front(bbi->subbasicblocks);
2021         pos = 0;
2022
2023         while (tosplit->next && (iidx >= (pos + tosplit->icount))) {
2024                 assert(bptr->nr == tosplit->nr);
2025                 pos += tosplit->icount;
2026                 tosplit = tosplit->next;
2027         }
2028
2029         assert(bptr->nr == tosplit->nr);
2030
2031         /* Calculate number of instructions left in block to split. */
2032
2033         ileft = iptr - tosplit->iinstr + 1;
2034         assert(ileft <= tosplit->icount);
2035
2036         /* If there are any instructions left in the block to split, split */
2037
2038         if (ileft < tosplit->icount) {
2039                 newblock = DNEW(basicblock);
2040                 *newblock = *tosplit;
2041
2042                 tosplit->next = newblock;
2043                 tosplit->icount = ileft;
2044
2045                 newblock->icount -= ileft;
2046                 newblock->iinstr += ileft;
2047
2048                 assert(tosplit->nr == bptr->nr);
2049                 assert(newblock->nr == bptr->nr);
2050                 assert(newblock->next == NULL);
2051
2052                 if (newblock->next == NULL) {
2053                         bbi->subbasicblocks->last = newblock;
2054                 }
2055         }
2056
2057         /* We won't break pointers/references to bptr.
2058            So return bptr instread of the first fragment.
2059            Later, we will put the first fragment into the memory used by bptr.
2060         */
2061
2062         if (tosplit == basicblock_chain_front(bbi->subbasicblocks)) {
2063                 tosplit = bptr;
2064         }
2065
2066         return tosplit;
2067 }
2068
2069 static basicblock *ssa_leave_create_transition_exception_handler(
2070         ssa_info *ssa,
2071         basicblock *from,
2072         unsigned pei,
2073         basicblock *to
2074 ) {
2075         basicblock *exh;
2076
2077         /* From is a try block, to is an exception handler prologue. */
2078
2079         /* Remove old prologue. */
2080
2081         to->flags = BBDELETED;
2082
2083         /* Create new exception handler. */
2084
2085         exh = ssa_leave_create_transition_block_intern(
2086                 ssa,
2087                 from,
2088                 to,
2089                 basicblock_get_ex_predecessor_index(from, pei, to),
2090                 1
2091         );
2092         exh->type = BBTYPE_EXH;
2093
2094         /* Copy goto to real exception handler at the end of the exception handler
2095            prologue. */
2096
2097         assert(to->iinstr[to->icount - 1].opc == ICMD_GOTO);
2098         assert(exh->iinstr[exh->icount - 1].opc == ICMD_GOTO);
2099         exh->iinstr[exh->icount - 1] = to->iinstr[to->icount - 1];
2100
2101         /* Copy getexception from the old prologue. */
2102
2103         assert(to->iinstr[0].opc == ICMD_GETEXCEPTION);
2104         exh->iinstr[0] = to->iinstr[0];
2105
2106         return exh;
2107 }
2108
2109 static exception_entry *ssa_leave_create_transition_exception_entry(
2110         ssa_info_t *ssa,
2111         basicblock *from,
2112         basicblock *handler,
2113         classref_or_classinfo catchtype
2114 ) {
2115
2116         exception_entry *ee = DNEW(exception_entry);
2117         basicblock_info_t *fromi = bb_info(from);
2118
2119         ee->start = from;
2120
2121         /* If the try block has subbasicblocks, the next block is the next fragment,
2122            not the successor block. */
2123
2124         if (fromi != NULL) {
2125                 ee->end = basicblock_chain_front(fromi->subbasicblocks)->next;
2126         } else {
2127                 ee->end = from->next;
2128         }
2129         ee->handler = handler;
2130         ee->catchtype = catchtype;
2131         ee->next = NULL;
2132         ee->down = NULL;
2133
2134         return ee;
2135 }
2136
2137 static void ssa_leave_create_exceptional_phi_moves(ssa_info *ssa) {
2138         basicblock *bptr;
2139         instruction *iptr;
2140         exception_entry *ite;
2141         exception_entry_chain_t chain;
2142         classref_or_classinfo catchtype;
2143         basicblock *ittry;
2144         unsigned pei;
2145         basicblock *try;
2146         basicblock *exh;
2147         exception_entry *ee;
2148         basicblock *last = NULL;
2149
2150         if (! basicblock_chain_empty(ssa->new_blocks)) {
2151                 last = basicblock_chain_back(ssa->new_blocks);
2152         }
2153
2154         basicblock_chain_clear(ssa->new_blocks);
2155
2156         for (ite = ssa->jd->exceptiontable; ite; ite = ite->down) {
2157                 bptr = ite->handler;
2158                 catchtype = ite->catchtype;
2159                 exception_entry_chain_init(&chain);
2160                 for (ittry = ite->start; ittry != ite->end; ittry = ittry->next) {
2161                         if (basicblock_reached(ittry)) {
2162                                 /* Dead code does not have a basicblock_info_t associated. */
2163                                 pei = 0;
2164                                 FOR_EACH_INSTRUCTION(ittry, iptr) {
2165                                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
2166                                                 /* try is basicblock fragment till (including) the pei */
2167                                                 try = ssa_leave_split_basicblock_at(ssa, ittry, iptr);
2168                                                 /* ee is handler for try */
2169                                                 exh = ssa_leave_create_transition_exception_handler(
2170                                                         ssa, try, pei, bptr
2171                                                 );
2172                                                 ee = ssa_leave_create_transition_exception_entry(
2173                                                         ssa, try, exh, catchtype
2174                                                 );
2175                                                 exception_entry_chain_add(&chain, ee);
2176                                                 pei += 1;
2177                                                 ssa->jd->exceptiontablelength += 1;
2178                                         }
2179                                 }
2180                         }
2181                 }
2182                 if (! exception_entry_chain_empty(&chain)) {
2183                         exception_entry_chain_back(&chain)->down = ite->down;
2184                         exception_entry_chain_back(&chain)->next = ite->next;
2185                         /* Replace original exception entry by first new one. */
2186                         *ite = *exception_entry_chain_front(&chain);
2187                         /* Set current iteration position to last newly created one. */
2188                         ite = exception_entry_chain_back(&chain);
2189                 }
2190         }
2191
2192         if (last == NULL) {
2193                 for (last = ssa->jd->basicblocks; last->next != NULL; last = last->next);
2194         }
2195
2196         if (last != NULL && ! basicblock_chain_empty(ssa->new_blocks)) {
2197                 last->next = basicblock_chain_front(ssa->new_blocks);
2198         }
2199 }
2200
2201 void ssa_simple_leave_restore(ssa_info_t *ssa, basicblock *bptr, s4 *pvar) {
2202         s4 var = *pvar;
2203         s4 index;
2204         basicblock_info_t *bbi;
2205
2206         if (var < ssa->locals->count) {
2207                 *pvar = vars_get_old_index(ssa->locals, var);
2208         } else if (var < ssa->locals->count + ssa->stack->count) {
2209
2210                 index = vars_get_old_index(
2211                         ssa->stack,
2212                         var - ssa->locals->count
2213                 );
2214
2215                 bbi = bb_info(bptr);
2216
2217                 /* We have to determine whether to take an invar or an outvar for
2218                    the stack depth ``index''.
2219                    The state array contains the last definition of the stack element
2220                    at the given depth.
2221                 */
2222
2223                 if (state_array_get_var(bbi->stack->state_array, index) == var) {
2224                         /* The last definition of a stack depth inside the basicblock.
2225                            This is the outvar at the given depth.
2226                            If there is no outvar at the given depth, it must be an invar.
2227                         */
2228                         if (index < bptr->outdepth) {
2229                                 *pvar = bptr->outvars[index];
2230                         } else if (index < bptr->indepth) {
2231                                 *pvar = bptr->invars[index];
2232                         } else {
2233                                 assert(0);
2234                         }
2235                 } else {
2236                         /* A different than the last definition of a stack depth.
2237                            This must be an invar.
2238                         */
2239                         assert(index < bptr->indepth);
2240                         *pvar = bptr->invars[index];
2241                 }
2242         } else {
2243                 *pvar = vars_get_old_index(
2244                         ssa->others,
2245                         var - ssa->locals->count - ssa->stack->count
2246                 );
2247         }
2248 }
2249
2250 void ssa_simple_leave(ssa_info_t *ssa) {
2251         basicblock *bptr;
2252         instruction *iptr;
2253         s4 *ituse, *uses;
2254         unsigned uses_count;
2255
2256         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
2257                 if (bptr->type == BBTYPE_EXH) {
2258                         /* (Aritifical) exception handler blocks will be eliminated. */
2259                         continue;
2260                 }
2261                 /* In reverse order. We need to rename the definition after any use! */
2262                 FOR_EACH_INSTRUCTION_REV(bptr, iptr) {
2263                         if (instruction_has_dst(iptr)) {
2264                                 ssa_simple_leave_restore(ssa, bptr, &(iptr->dst.varindex));
2265                         }
2266                         instruction_get_uses(iptr, ssa->s_buf, &uses, &uses_count);
2267                         for (ituse = uses; ituse != uses + uses_count; ++ituse) {
2268                                 ssa_simple_leave_restore(ssa, bptr, ituse);
2269                         }
2270                         instruction_set_uses(iptr, ssa->s_buf, uses, uses_count);
2271                 }
2272         }
2273
2274         unfix_exception_handlers(ssa->jd);
2275
2276         ssa->jd->maxlocals = ssa->original.maxlocals;
2277         ssa->jd->maxinterfaces = ssa->original.maxinterfaces;
2278         ssa->jd->local_map =ssa->original.local_map;
2279         ssa->jd->var = ssa->original.var;
2280         ssa->jd->vartop = ssa->original.vartop;
2281         ssa->jd->varcount = ssa->original.varcount;
2282         ssa->jd->localcount = ssa->original.localcount;
2283 }
2284
2285 void yssa(jitdata *jd) {
2286         basicblock *it;
2287         basicblock_info_t *iti;
2288         ssa_info *ssa;
2289
2290 #ifdef SSA_VERBOSE
2291         bool verb = true;
2292         if (verb) {
2293                 printf("=============== [ before %s ] =========================\n", jd->m->name->text);
2294                 show_method(jd, 3);
2295                 printf("=============== [ /before ] =========================\n");
2296         }
2297 #endif
2298
2299         ssa = DNEW(ssa_info);
2300
2301         ssa_info_init(ssa, jd);
2302         ssa->keep_in_out = true;
2303
2304         FOR_EACH_BASICBLOCK(jd, it) {
2305                 if (basicblock_reached(it)) {
2306                         iti = DNEW(basicblock_info_t);
2307                         basicblock_info_init(iti, it, jd);
2308                         it->vp = iti;
2309                 } else {
2310                         it->vp = NULL;
2311                 }
2312         }
2313
2314         ssa_enter_mark_loops(jd->basicblocks);
2315
2316         ssa_enter_traverse(ssa, jd->basicblocks);
2317
2318         ssa_enter_eliminate_categories(ssa);
2319
2320         ssa_enter_export_variables(ssa);
2321
2322         ssa_enter_export_phis(ssa);
2323
2324         ssa_enter_verify_no_redundant_phis(ssa);
2325
2326         /*ssa_enter_create_phi_graph(ssa);*/
2327
2328         /*escape_analysis_perform(ssa->jd);*/
2329
2330         /*
2331         ssa_leave_create_phi_moves(ssa);
2332
2333         ssa_leave_create_exceptional_phi_moves(ssa);
2334         */
2335
2336 #ifdef SSA_VERBOSE
2337         if (verb) {
2338                 printf("=============== [ mid ] =========================\n");
2339                 show_method(jd, 3);
2340                 printf("=============== [ /mid ] =========================\n");
2341         }
2342 #endif
2343
2344         ssa_simple_leave(ssa);
2345
2346 #ifdef SSA_VERBOSE
2347         if (verb) {
2348                 printf("=============== [ after ] =========================\n");
2349                 show_method(jd, 3);
2350                 printf("=============== [ /after ] =========================\n");
2351         }
2352 #endif
2353
2354 }
2355
2356 void eliminate_subbasicblocks(jitdata *jd) {
2357         basicblock *bptr, *next;
2358         basicblock_info_t *bbi;
2359
2360         FOR_EACH_BASICBLOCK(jd, bptr) {
2361                 bbi = bb_info(bptr);
2362                 if (bbi != NULL) {
2363                         if (! basicblock_chain_empty(bbi->subbasicblocks)) {
2364                                 next = bptr->next;
2365                                 /* Copy first subblock, to keep pointers intact. */
2366                                 *bptr = *basicblock_chain_front(bbi->subbasicblocks);
2367                                 bptr = basicblock_chain_back(bbi->subbasicblocks);
2368                                 bptr->next = next;
2369                         }
2370                 }
2371         }
2372
2373 #ifdef SSA_VERBOSE
2374         printf("=============== [ elim ] =========================\n");
2375         show_method(jd, 3);
2376         printf("=============== [ /elim ] =========================\n");
2377 #endif
2378 }
2379
2380 /*
2381  * These are local overrides for various environment variables in Emacs.
2382  * Please do not remove this and leave it at the end of the file, where
2383  * Emacs will automagically detect them.
2384  * ---------------------------------------------------------------------
2385  * Local variables:
2386  * mode: c
2387  * indent-tabs-mode: t
2388  * c-basic-offset: 4
2389  * tab-width: 4
2390  * End:
2391  * vim:noexpandtab:sw=4:ts=4:
2392  */