src/vm/jit/optimizing/ssa3.c

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