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