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