src/vm/jit/optimizing/ssa3.c

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