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
  34    * Create PHI functions lazyly, when they are used for the first time
  35      (I suspect that currently PHIs are created that are never used).
  36    * REWRITE. The code was never designed for producion.
  37 */
  38
  39 #include "vm/jit/jit.h"
  40 #include "vm/global.h"
  41 #include "mm/memory.h"
  42 #include "mm/dumpmemory.h"
  43 #include "toolbox/list.h"
  44
  45 #if 1
  46 static inline bool test_do_verbose(jitdata *jd) {
  47         return strcmp(jd->m->name->text, "close") == 0 &&
  48                 strcmp(jd->m->clazz->name->text, "antlr/PreservingFileWriter") == 0;
  49 }
  50 static bool do_verbose = 0;
  51 #define WHEN do_verbose
  52 #define printf(...) do { if (WHEN) printf(__VA_ARGS__); } while (0)
  53 #define show_method(...) do { if (WHEN) show_method(__VA_ARGS__); } while (0)
  54 #define show_basicblock(...) do { if (WHEN) show_basicblock(__VA_ARGS__); } while (0)
  55 #endif
  56
  57 /*
  58 TODO
  59 move set and get uses into jit.h
  60 */
  61
  62 #define ICMD_PHI 666
  63
  64 #define eqi(a, b) (((a) && (b) || (!(a) && !(b)))
  65
  66 #define nn(x) ((x) < 0 ? 0 : (x))
  67
  68 #define ass(dst, src) *(dst) = *(src)
  69
  70 static inline const char *instruction_name(const instruction *iptr) {
  71         if (iptr == NULL) {
  72                 return "null";
  73         } else if (iptr->opc == ICMD_PHI) {
  74                 return "phi";
  75         } else {
  76                 return icmd_table[iptr->opc].name;
  77         }
  78 }
  79
  80 static inline s4 instruction_line(const instruction *iptr) {
  81         if (iptr == NULL) {
  82                 return -1;
  83         } else {
  84                 return iptr->line;
  85         }
  86 }
  87
  88 typedef struct phi_function {
  89         s4 dst;
  90         s4 *args;
  91         s4 local;
  92         instruction instr;
  93 } phi_function;
  94
  95 typedef struct basicblock_info {
  96         bool visited;
  97         bool active;
  98         bool traversed;
  99         unsigned backward_branches;
 100
 101         instruction **state_array;
 102
 103         unsigned phi_count;
 104         unsigned phi_max;
 105         phi_function *phi_functions;
 106         unsigned complete_predecessors;
 107         bool cow;
 108 } basicblock_info;
 109
 110 typedef struct ssa_info {
 111         jitdata *jd;
 112
 113         varinfo locals[3000]; /* XXX hardcoded max */
 114         unsigned max_locals;
 115         unsigned locals_count;
 116
 117         s4 s_buf[3];
 118 } ssa_info;
 119
 120 static unsigned get_predecessor_count(basicblock *bb) {
 121         unsigned ret;
 122         basicblock **itpred;
 123
 124         ret = nn(bb->predecessorcount);
 125
 126         FOR_EACH_EXPREDECESSOR(bb, itpred) {
 127                 ret += (*itpred)->exouts;
 128         }
 129
 130         return ret;
 131 }
 132
 133 static unsigned get_predecessor_index(basicblock *from, basicblock *to) {
 134         basicblock **itpred;
 135         unsigned j = 0;
 136
 137         for (itpred = to->predecessors; itpred != to->predecessors + nn(to->predecessorcount); ++itpred) {
 138                 if (*itpred == from) break;
 139                 j++;
 140         }
 141
 142         if (j == nn(to->predecessorcount)) {
 143                 assert(j != nn(to->predecessorcount));
 144         }
 145
 146         return j;
 147 }
 148
 149 static void phi_set_argument(basicblock *bb, instruction *phi, unsigned j, instruction *value) {
 150         phi_function *pf = (phi_function *)(
 151                 (char *)phi - OFFSET(phi_function, instr)
 152         );
 153         assert(j < phi->s1.argcount);
 154         if (value == NULL) {
 155                 pf->args[j] = pf->local;
 156         } else {
 157                 pf->args[j] = value->dst.varindex;
 158         }
 159         /*phi->sx.s23.s2.args[j] = value->dst.varindex;*/
 160         printf(" *** in bb%d setting phi arg %d for local %d to %s@%d (%d)\n", bb->nr, j, pf->local, instruction_name(value), instruction_line(value), value ? value->dst.varindex : -1);
 161 }
 162
 163 static inline basicblock_info *bb_info(basicblock *bb) {
 164         return (basicblock_info *)(bb->vp);
 165 }
 166
 167 static void mark_loops(basicblock *bb) {
 168         basicblock_info *bbi = bb_info(bb);
 169         basicblock **itsucc;
 170
 171         if (! bbi->visited) {
 172                 bbi->visited = true;
 173                 bbi->active = true;
 174                 FOR_EACH_SUCCESSOR(bb, itsucc) {
 175                         mark_loops(*itsucc);
 176                 }
 177                 FOR_EACH_EXHANDLER(bb, itsucc) {
 178                         mark_loops(*itsucc);
 179                 }
 180                 bbi->active = false;
 181         } else if (bbi->active) {
 182                 bbi->backward_branches += 1;
 183         }
 184 }
 185
 186 static instruction *create_phi(ssa_info *ssa, basicblock *bb, s4 local) {
 187         basicblock_info *bbi = bb_info(bb);
 188         phi_function *phi;
 189         s4 *itarg;
 190         unsigned arg_count = get_predecessor_count(bb);
 191
 192         printf(" *** BB%d phi #%d for local %d\n", bb->nr, bbi->phi_count, local);
 193
 194         phi = bbi->phi_functions + bbi->phi_count;
 195         assert(bbi->phi_count < bbi->phi_max);
 196         bbi->phi_count += 1;
 197
 198
 199         phi->local = local;
 200         phi->args = DMNEW(s4, arg_count);
 201         for (itarg = phi->args; itarg != phi->args + arg_count; ++itarg) {
 202                 /* Invalidate */
 203                 *itarg = 0x7fffffff;
 204         }
 205
 206         assert(ssa->locals_count < ssa->max_locals);
 207         ssa->locals[ssa->locals_count] = ssa->jd->var[local];
 208         phi->dst = ssa->locals_count;
 209         ssa->locals_count += 1;
 210
 211         phi->instr.opc = ICMD_PHI;
 212         phi->instr.dst.varindex = phi->dst;
 213         phi->instr.s1.argcount = arg_count;
 214         phi->instr.sx.s23.s2.args = NULL;
 215
 216         return &(phi->instr);
 217 }
 218
 219 static bool is_my_phi(basicblock *bb, instruction *iptr) {
 220         basicblock_info *bbi = bb_info(bb);
 221         if (iptr == NULL) {
 222                 return false;
 223         }
 224         if (iptr->opc != ICMD_PHI) {
 225                 return false;
 226         }
 227         if (
 228                 ((char *)bbi->phi_functions <= (char *)iptr) &&
 229                 ((char *)iptr < (char *)(bbi->phi_functions + bbi->phi_count))
 230         ) {
 231                 return true;
 232         } else {
 233                 return false;
 234         }
 235 }
 236
 237 static void rename_def(ssa_info *ssa, basicblock *bptr, instruction *iptr) {
 238         basicblock_info *bbi = bb_info(bptr);
 239         assert(bbi->state_array);
 240
 241         bbi->state_array[iptr->dst.varindex] = iptr;
 242
 243         assert(ssa->locals_count < ssa->max_locals);
 244
 245         ssa->locals[ssa->locals_count] = ssa->jd->var[iptr->dst.varindex];
 246         iptr->dst.varindex = ssa->locals_count;
 247         printf(" *** BB%d %s def %d => %d\n", bptr->nr, instruction_name(iptr), iptr->dst.varindex, ssa->locals_count);
 248
 249         ssa->locals_count += 1;
 250 }
 251
 252 static void rename_use(ssa_info *ssa, basicblock *bptr, instruction *iptr, s4 *use) {
 253         basicblock_info *bbi = bb_info(bptr);
 254         assert(bbi->state_array);
 255
 256         if (bbi->state_array[*use] != NULL) {
 257                 printf(" *** BB%d %s use %d => %d (%s) \n", bptr->nr, instruction_name(iptr), *use, bbi->state_array[*use]->dst.varindex, instruction_name(bbi->state_array[*use]) );
 258                 *use = bbi->state_array[*use]->dst.varindex;
 259         } else {
 260                 printf(" *** BB%d %s use keep\n", bptr->nr, instruction_name(iptr));
 261         }
 262 }
 263
 264 static void get_uses(ssa_info *ssa, instruction *iptr, s4 **puses, unsigned *puses_count) {
 265         unsigned uses_count = 0;
 266
 267         switch (icmd_table[iptr->opc].dataflow) {
 268                 case DF_3_TO_0:
 269                 case DF_3_TO_1:
 270                         ssa->s_buf[2] = iptr->sx.s23.s3.varindex;
 271                         uses_count += 1;
 272
 273                 case DF_2_TO_0:
 274                 case DF_2_TO_1:
 275                         ssa->s_buf[1] = iptr->sx.s23.s2.varindex;
 276                         uses_count += 1;
 277
 278                 case DF_1_TO_0:
 279                 case DF_1_TO_1:
 280                 case DF_COPY:
 281                 case DF_MOVE:
 282                         ssa->s_buf[0] = iptr->s1.varindex;
 283                         uses_count += 1;
 284
 285                         *puses_count = uses_count;
 286                         *puses = ssa->s_buf;
 287                         break;
 288
 289                 case DF_N_TO_1:
 290                 case DF_INVOKE:
 291                 case DF_BUILTIN:
 292
 293                         *puses = iptr->sx.s23.s2.args;
 294                         *puses_count = iptr->s1.argcount;
 295                         break;
 296
 297                 default:
 298
 299                         *puses_count = 0;
 300                         break;
 301         }
 302 }
 303
 304 static void set_uses(ssa_info *ssa, instruction *iptr, s4 *uses, unsigned uses_count) {
 305         if (uses == ssa->s_buf) {
 306                 switch (uses_count) {
 307                         case 3:
 308                                 iptr->sx.s23.s3.varindex = ssa->s_buf[2];
 309                         case 2:
 310                                 iptr->sx.s23.s2.varindex = ssa->s_buf[1];
 311                         case 1:
 312                                 iptr->s1.varindex = ssa->s_buf[0];
 313                 }
 314         }
 315 }
 316
 317 typedef void (*traverse_fun)(ssa_info *ssa, basicblock *bb);
 318
 319 static void traverse(ssa_info *ssa, basicblock *bb, traverse_fun fun) {
 320         basicblock_info *bbi = bb_info(bb);
 321         basicblock **itsucc, **itpred;
 322         basicblock_info *succi;
 323         unsigned complete_preds;
 324         unsigned j;
 325
 326         /*if (bbi->traversed) {
 327                 return;
 328         }*/
 329
 330         /* Process block */
 331
 332         fun(ssa, bb);
 333
 334         /*bbi->traversed = true;*/
 335
 336         /* Recurse */
 337
 338         FOR_EACH_SUCCESSOR(bb, itsucc) {
 339                 merge(ssa, bbi->state_array, *itsucc, get_predecessor_index(bb, *itsucc));
 340                 succi = bb_info(*itsucc);
 341                 succi->complete_predecessors += 1;
 342                 if (succi->complete_predecessors == (/*nn((*itsucc)->predecessorcount)*/ get_predecessor_count(*itsucc) - succi->backward_branches)) {
 343                         printf(" *** Traverse bb%d => bb%d\n", bb->nr, (*itsucc)->nr);
 344                         traverse(ssa, *itsucc, fun);
 345                 }
 346         }
 347
 348         FOR_EACH_EXHANDLER(bb, itsucc) {
 349                 succi = bb_info(*itsucc);
 350                 succi->complete_predecessors += bb->exouts; /* XXX this might be 0 */
 351                 if (succi->complete_predecessors == (/*nn((*itsucc)->predecessorcount)*/ get_predecessor_count(*itsucc) - succi->backward_branches)) {
 352                         printf(" *** Traverse bb%d => bb%d\n", bb->nr, (*itsucc)->nr);
 353                         traverse(ssa, *itsucc, fun);
 354                 }
 355         }
 356
 357 }
 358
 359 void merge(ssa_info *ssa, instruction **state_array, basicblock *succ, unsigned j) {
 360         basicblock_info *succi = bb_info(succ);
 361         instruction *phi;
 362         unsigned i;
 363         unsigned a;
 364
 365 #define mprintf(fmt, ...) printf(" *** merge bb? => bb%d > " fmt, succ->nr, __VA_ARGS__)
 366
 367         mprintf("(%d, %p)\n", j, succi->state_array);
 368
 369         if (succi->state_array == NULL) {
 370
 371                 succi->state_array = DMNEW(instruction *, ssa->jd->localcount);
 372
 373                 mprintf("creating state_array %p\n", succi->state_array );
 374
 375
 376                 if (succi->backward_branches > 0) {
 377                         mprintf("bb%d is loop header, creating phis\n", succ->nr);
 378                         for (i = 0; i < ssa->jd->localcount; ++i) {
 379                                 succi->state_array[i] = create_phi(ssa, succ, i);
 380                         }
 381                 } else {
 382                         /*
 383                         printf(" *** merge bb%d cow state array\n", succ->nr);
 384                         succi->state_array = bbi->state_array;
 385                         succi->cow = true;
 386                         */
 387                         MCOPY(succi->state_array, state_array, instruction *, ssa->jd->localcount);
 388                         return;
 389                 }
 390         }
 391
 392         for (i = 0; i < ssa->jd->localcount; ++i) {
 393                 mprintf("local %d bb: %s@%d, succ: %s@%d\n", i, instruction_name(state_array[i]), instruction_line(state_array[i]), instruction_name(succi->state_array[i]), instruction_line(succi->state_array[i]));
 394
 395                 if (succi->traversed) {
 396                         /* Back edge, all phis already created */
 397                         /* Only fill in phi arguments */
 398                         /* We have created phis for *ALL* locals, so there is random access */
 399                         phi_set_argument(succ, &(succi->phi_functions[i].instr), j, state_array[i]);
 400                 } else if (state_array[i] != succi->state_array[i]) {
 401                         mprintf("merge bb%d need phi for local %d\n", succ->nr, i);
 402                         /* Create new state array if needed */
 403
 404                         /*if (succi->cow) {
 405                                 printf(" *** merge bb%d cloning cow state array\n", succ->nr);
 406                                 state_array = DMNEW(instruction *, ssa->jd->localcount);
 407                                 MCOPY(state_array, succi->state_array, instruction *, ssa->jd->localcount);
 408                                 succi->state_array = state_array;
 409                                 succi->cow = false;
 410                         }*/
 411
 412                         if (is_my_phi(succ, succi->state_array[i])) {
 413                                 /* State array is already phi function, just need to fill in argument */
 414                                 phi_set_argument(succ, succi->state_array[i], j, state_array[i]);
 415                         } else {
 416                                 /* Create phi and initialize all arguments with current state array value
 417                                  * (We might have already merged this value from within several blocks).
 418                                  */
 419                                 phi = create_phi(ssa, succ, i);
 420                                 for (a = 0; a < get_predecessor_count(succ); ++a) {
 421                                         phi_set_argument(succ, phi, a, succi->state_array[i]);
 422                                 }
 423                                 phi_set_argument(succ, phi, j, state_array[i]);
 424                                 succi->state_array[i] = phi;
 425                         }
 426                 }
 427         }
 428 #undef mprintf
 429 }
 430
 431 static unsigned get_ex_predecessor_index(basicblock *from, unsigned pei, basicblock *to) {
 432         unsigned i, j;
 433         basicblock **itpred;
 434         instruction *iti;
 435
 436         j = nn(to->predecessorcount);
 437
 438         FOR_EACH_EXPREDECESSOR(to, itpred) {
 439                 if ((*itpred)->nr == from->nr) {
 440                         j += pei;
 441                         return j;
 442                 } else {
 443                         j += (*itpred)->exouts;
 444                 }
 445         }
 446
 447         assert(0);
 448 }
 449
 450 static void handle_pei(ssa_info *ssa, basicblock *bb, unsigned pei) {
 451         basicblock_info *bbi = bb_info(bb);
 452         basicblock **itsucc;
 453
 454         FOR_EACH_EXHANDLER(bb, itsucc) {
 455                 merge(ssa, bbi->state_array, *itsucc, get_ex_predecessor_index(bb, pei, *itsucc));
 456         }
 457 }
 458
 459 static void traverse_fun_impl(ssa_info *ssa, basicblock *bb) {
 460         basicblock_info *bbi = bb_info(bb), *predi;
 461         basicblock **itpred, *pred;
 462         unsigned i;
 463         bool need_phi;
 464         instruction *iptr;
 465         unsigned uses_count;
 466         s4 *uses, *ituse;
 467         unsigned pei = 0;
 468
 469         assert(! bbi->traversed);
 470         bbi->traversed = true;
 471
 472         /*
 473         if (bbi->state_array) {
 474                 return;
 475         }
 476         */
 477
 478         /* bb 0 */
 479
 480         if (bb->predecessorcount == 0) {
 481                 assert(! bbi->state_array);
 482                 bbi->state_array = DMNEW(instruction *, ssa->jd->localcount);
 483                 MZERO(bbi->state_array, instruction *, ssa->jd->localcount);
 484                 goto process_instructions;
 485         }
 486
 487
 488         /*
 489         if ((bb->predecessorcount == 1) && (bb->predecessors[0]->successorcount == 1)) {
 490                 bbi->state_array = bb_info(bb->predecessors[0])->state_array;
 491                 assert(bbi->state_array);
 492                 goto process_instructions;
 493         }
 494         */
 495
 496         /*
 497         bbi->state_array = DMNEW(instruction *, ssa->jd->localcount);
 498         MZERO(bbi->state_array, instruction *, ssa->jd->localcount);
 499         */
 500
 501         /*
 502         if (bbi->backward_branches > 0) {
 503                 for (i = 0; i < ssa->jd->localcount; ++i) {
 504                         bbi->state_array[i] = create_phi(ssa, bb, i);
 505                 }
 506         } else {
 507                 for (i = 0; i < ssa->jd->localcount; ++i) {
 508                         need_phi = false;
 509                         assert(bb_info(bb->predecessors[0])->state_array);
 510
 511                         FOR_EACH_PREDECESSOR(bb, itpred) {
 512                                 assert(bb_info(*itpred)->state_array);
 513                                 if (bb_info(bb->predecessors[0])->state_array[i] != bb_info(*itpred)->state_array[i]) {
 514                                         need_phi = true;
 515                                         break;
 516                                 }
 517                         }
 518
 519                         if (need_phi) {
 520                                 bbi->state_array[i] = create_phi(ssa, bb, i);
 521                         } else {
 522                                 bbi->state_array[i] = bb_info(bb->predecessors[0])->state_array[i];
 523                         }
 524
 525                 }
 526         }
 527         */
 528
 529 process_instructions:
 530
 531         assert(bbi->state_array);
 532
 533         FOR_EACH_INSTRUCTION(bb, iptr) {
 534
 535                 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 536                         handle_pei(ssa, bb, pei++);
 537                 }
 538
 539                 get_uses(ssa, iptr, &uses, &uses_count);
 540
 541                 for (ituse = uses; ituse != uses + uses_count; ++ituse) {
 542                         if (var_is_local(ssa->jd, *ituse)) {
 543                                 rename_use(ssa, bb, iptr, ituse);
 544                         } else {
 545                                 *ituse += 0xFFFF;
 546                         }
 547                 }
 548
 549                 set_uses(ssa, iptr, uses, uses_count);
 550
 551                 if (instruction_has_dst(iptr)) {
 552                         if (var_is_local(ssa->jd, iptr->dst.varindex)) {
 553                                 rename_def(ssa, bb, iptr);
 554                         } else {
 555                                 iptr->dst.varindex += 0xFFFF;
 556                         }
 557                 }
 558         }
 559 }
 560
 561 static void ssa_rename_others(ssa_info *ssa) {
 562
 563         basicblock *bb;
 564         instruction *iptr;
 565         s4 *itinout, *uses, *ituse;
 566         unsigned uses_count;
 567         unsigned off = ssa->locals_count - ssa->jd->localcount;
 568
 569         FOR_EACH_BASICBLOCK(ssa->jd, bb) {
 570
 571                 if (! basicblock_reached(bb)) continue;
 572
 573                 for (itinout = bb->invars; itinout != bb->invars + bb->indepth; ++itinout) {
 574                         *itinout += off;
 575                 }
 576
 577                 for (itinout = bb->outvars; itinout != bb->outvars + bb->outdepth; ++itinout) {
 578                         *itinout += off;
 579                 }
 580
 581                 FOR_EACH_INSTRUCTION(bb, iptr) {
 582                         if (instruction_has_dst(iptr)) {
 583                                 if (iptr->dst.varindex >= 0xFFFF) {
 584                                         iptr->dst.varindex += off;
 585                                         iptr->dst.varindex -= 0xFFFF;
 586                                 }
 587                         }
 588                         get_uses(ssa, iptr, &uses, &uses_count);
 589                         for (ituse = uses; ituse != uses + uses_count; ++ituse) {
 590                                 if (*ituse >= 0xFFFF) {
 591                                         *ituse += off;
 592                                         *ituse -= 0xFFFF;
 593                                 }
 594                         }
 595                         set_uses(ssa, iptr, uses, uses_count);
 596                 }
 597         }
 598 }
 599
 600 static void fill_in_phi_args(ssa_info *ssa) {
 601         basicblock *bb;
 602         basicblock_info *bbi;
 603         phi_function *itphi;
 604         unsigned j;
 605         basicblock **itpred;
 606         basicblock_info *predi;
 607
 608         FOR_EACH_BASICBLOCK(ssa->jd, bb) {
 609                 if (!(bb->flags >= BBREACHED)) continue;
 610                 bbi = bb_info(bb);
 611                 j = 0;
 612                 FOR_EACH_PREDECESSOR(bb, itpred) {
 613                         predi = bb_info(*itpred);
 614                         for (itphi = bbi->phi_functions; itphi != bbi->phi_functions + bbi->phi_count; ++itphi) {
 615                                 if (predi->state_array[itphi->local]) {
 616                                         itphi->args[j] = predi->state_array[itphi->local]->dst.varindex;
 617                                 } else {
 618                                         itphi->args[j] = itphi->local;
 619                                 }
 620                         }
 621                         ++j;
 622                 }
 623         }
 624 }
 625
 626 static void ssa_export(ssa_info *ssa) {
 627         unsigned i, j;
 628         jitdata *jd = ssa->jd;
 629         varinfo *vars, *it;
 630         s4 vartop, varindex;
 631
 632         vartop = ssa->locals_count + jd->vartop - jd->localcount;
 633         vars = DMNEW(varinfo, vartop);
 634
 635         MCOPY(vars, ssa->locals, varinfo, ssa->locals_count);
 636         MCOPY(vars + ssa->locals_count, jd->var + jd->localcount, varinfo, jd->vartop - jd->localcount);
 637
 638         jd->var = vars;
 639         jd->vartop = jd->varcount = vartop;
 640
 641         jd->local_map = DMREALLOC(jd->local_map, s4, 5 * jd->maxlocals, 5 * (jd->maxlocals + ssa->locals_count - jd->localcount));
 642
 643         for (i = 0; i < ssa->locals_count - jd->localcount; ++i) {
 644                 for (j = 0; j < 5; ++j) {
 645                         varindex = jd->localcount + i;
 646                         if (jd->var[varindex].type != j) {
 647                                 varindex = UNUSED;
 648                         }
 649                         jd->local_map[((jd->maxlocals + i) * 5) + j] = varindex;
 650                 }
 651         }
 652
 653         jd->maxlocals += (ssa->locals_count - jd->localcount);
 654         jd->localcount = ssa->locals_count;
 655 }
 656
 657 static basicblock *create_block_intern(ssa_info *ssa, basicblock *from, basicblock *to, unsigned j) {
 658         basicblock *mid;
 659         basicblock_info *toi;
 660         instruction *iptr;
 661         phi_function *itph;
 662
 663         mid = DNEW(basicblock);
 664         MZERO(mid, basicblock, 1);
 665
 666         toi = bb_info(to);
 667         assert(toi);
 668
 669         mid->nr = ssa->jd->basicblockcount;
 670         ssa->jd->basicblockcount += 1;
 671         mid->mpc = -1;
 672         mid->type = 666;
 673         mid->icount = toi->phi_count + 1;
 674         iptr = mid->iinstr = DMNEW(instruction, mid->icount);
 675         MZERO(mid->iinstr, instruction, mid->icount);
 676
 677         for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
 678                 iptr->opc = ICMD_COPY;
 679                 iptr->dst.varindex = itph->dst;
 680                 iptr->s1.varindex =  itph->args[j];
 681                 assert(j < itph->instr.s1.argcount);
 682                 assert(itph->dst < ssa->locals_count);
 683                 assert(itph->args[j] < ssa->locals_count);
 684                 iptr++;
 685         }
 686
 687         iptr->opc = ICMD_GOTO;
 688         iptr->dst.block = to;
 689
 690         return mid;
 691 }
 692
 693 static basicblock *create_block(ssa_info *ssa, basicblock *from, basicblock *to) {
 694         basicblock *ret;
 695         ret = create_block_intern(ssa, from, to, get_predecessor_index(from, to));
 696
 697         while (from->next) {
 698                 from = from->next;
 699         }
 700
 701         from->next = ret;
 702
 703         return ret;
 704 }
 705
 706 static void crate_fallthrough(ssa_info *ssa, basicblock *bptr) {
 707         unsigned j;
 708         basicblock_info *toi;
 709         instruction *iptr;
 710         phi_function *itph;
 711
 712         if (bptr->next == NULL) return;
 713
 714         j = get_predecessor_index(bptr, bptr->next);
 715
 716         toi = bb_info(bptr->next);
 717         assert(toi);
 718
 719         bptr->iinstr = DMREALLOC(bptr->iinstr, instruction, bptr->icount, bptr->icount + toi->phi_count);
 720         iptr = bptr->iinstr + bptr->icount;
 721         bptr->icount += toi->phi_count;
 722
 723         for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
 724                 iptr->opc = ICMD_COPY;
 725                 iptr->dst.varindex = itph->dst;
 726                 iptr->s1.varindex =  itph->args[j];
 727                 assert(itph->dst < ssa->locals_count);
 728                 assert(itph->args[j] < ssa->locals_count);
 729                 iptr++;
 730         }
 731
 732 }
 733
 734 static void ssa_create_phi_moves(ssa_info *ssa) {
 735         basicblock *bptr;
 736         instruction *iptr;
 737
 738         s4 i, l;
 739         branch_target_t *table;
 740         lookup_target_t *lookup;
 741         bool gt;
 742
 743         for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
 744                 if (bptr->type == 666) {
 745                         bptr->type = BBTYPE_STD;
 746                         continue;
 747                 }
 748                 if (! bptr->vp) continue;
 749                 if (! (bptr->flags >= BBREACHED)) continue;
 750                 gt = false;
 751                 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
 752                         switch (icmd_table[iptr->opc].controlflow) {
 753                                 case CF_IF:
 754                                 case CF_RET:
 755                                 case CF_GOTO:
 756                                         iptr->dst.block = create_block(ssa, bptr, iptr->dst.block);
 757                                         break;
 758                                 case CF_TABLE:
 759                                         table = iptr->dst.table;
 760                                         l = iptr->sx.s23.s2.tablelow;
 761                                         i = iptr->sx.s23.s3.tablehigh;
 762                                         i = i - l + 1;
 763                                         i += 1; /* default */
 764                                         while (--i >= 0) {
 765                                                 table->block = create_block(ssa, bptr, table->block);
 766                                                 ++table;
 767                                         }
 768                                         break;
 769                                 case CF_LOOKUP:
 770                                         lookup = iptr->dst.lookup;
 771                                         i = iptr->sx.s23.s2.lookupcount;
 772                                         while (--i >= 0) {
 773                                                 lookup->target.block = create_block(ssa, bptr, lookup->target.block);
 774                                                 lookup++;
 775                                         }
 776                                         iptr->sx.s23.s3.lookupdefault.block = create_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
 777                                         break;
 778                                 case CF_JSR:
 779                                         iptr->sx.s23.s3.jsrtarget.block = create_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
 780                                         break;
 781                         }
 782                         if ((iptr->opc == ICMD_GOTO) || (iptr->opc == ICMD_JSR) || (iptr->opc == ICMD_RET) || icmd_table[iptr->opc].controlflow == CF_END || (iptr->opc == ICMD_TABLESWITCH) || (iptr->opc == ICMD_LOOKUPSWITCH))
 783                                 gt = true;
 784                         else if (iptr->opc != ICMD_NOP)
 785                                 gt = false;
 786                 }
 787                 if (! bptr->next) continue;
 788                 if (! (bptr->next->flags >= BBREACHED)) continue;
 789                 if (bptr->next->type == 666) continue;
 790                 if (!gt) crate_fallthrough(ssa, bptr);
 791         }
 792 }
 793
 794 static basicblock *split_basicblock_at(ssa_info *ssa, basicblock *bptr, instruction *iptr) {
 795
 796         basicblock *newblock;
 797         basicblock *tosplit;
 798         basicblock **pnext;
 799         unsigned icount;
 800         basicblock *it;
 801         unsigned pos;
 802
 803         unsigned origidx = iptr - bptr->iinstr;
 804
 805         printf(" *** split basicblock bb%d at %s/%d/%d\n", bptr->nr, instruction_name(iptr), instruction_line(iptr), origidx);
 806         assert(origidx < bptr->icount);
 807
 808
 809         if (! bptr->subbasicblocks) {
 810                 bptr->subbasicblocks = DNEW(basicblock);
 811                 ass(bptr->subbasicblocks, bptr);
 812                 bptr->subbasicblocks->subbasicblocks = NULL;
 813                 bptr->subbasicblocks->next = NULL;
 814         }
 815
 816         tosplit = bptr->subbasicblocks;
 817         pos = 0;
 818
 819         while (tosplit->next && (origidx >= (pos + tosplit->icount))) {
 820                 assert(bptr->nr == tosplit->nr);
 821                 pos += tosplit->icount;
 822                 tosplit = tosplit->next;
 823         }
 824
 825         assert(bptr->nr == tosplit->nr);
 826
 827         icount = iptr - tosplit->iinstr + 1;
 828         assert(icount <= tosplit->icount);
 829
 830         if (icount < tosplit->icount) {
 831                 newblock = DNEW(basicblock);
 832                 ass(newblock, tosplit);
 833
 834                 tosplit->next = newblock;
 835                 tosplit->icount = icount;
 836
 837                 newblock->icount -= icount;
 838                 newblock->iinstr += icount;
 839                 newblock->next = NULL;
 840
 841                 assert(tosplit->nr == bptr->nr);
 842                 assert(newblock->nr == bptr->nr);
 843                 assert(newblock->next == NULL);
 844         } else {
 845                 printf("xx split\n");
 846         }
 847
 848         /* To not break references to block bptr, we will replace
 849            the block by the first fragment later. */
 850
 851         if (tosplit == bptr->subbasicblocks) tosplit = bptr;
 852
 853         return tosplit;
 854 }
 855
 856 static exception_entry *create_exception_handler(ssa_info *ssa, basicblock *from, unsigned pei, basicblock *to, classref_or_classinfo catchtype) {
 857         basicblock *it;
 858         exception_entry *ee = DNEW(exception_entry);
 859         basicblock *exh = create_block_intern(ssa, from, to, get_ex_predecessor_index(from, pei, to));
 860         exh->type = BBTYPE_EXH;
 861         to->type = BBTYPE_STD;
 862
 863         exh->indepth = exh->outdepth = 1;
 864         exh->invars = exh->outvars = DNEW(s4);
 865         /* assigned in caller */
 866
 867         ee->start = from;
 868         /* XXX evil hack: if from is first fragment of BB, then from->next is not the next fragment */
 869         ee->end = from->subbasicblocks ? from->subbasicblocks->next : from->next;
 870         ee->handler = exh;
 871         ee->catchtype = catchtype;
 872         ee->next = NULL;
 873         ee->down = NULL;
 874
 875         for (it = ssa->jd->basicblocks; it->next; it = it->next);
 876
 877         it->next = exh;
 878
 879         return ee;
 880 }
 881
 882 static void ssa_create_ex_phi_moves(ssa_info *ssa) {
 883         basicblock *bptr;
 884         instruction *iptr;
 885         basicblock_info *bbi;
 886         exception_entry *ite;
 887         exception_entry *firstee, *lastee, *ee;
 888         basicblock *ittry, *try;
 889         classref_or_classinfo catchtype;
 890         unsigned pei;
 891         unsigned exhandler_count = 0;
 892         varinfo *v;
 893
 894         FOR_EACH_BASICBLOCK(ssa->jd, bptr) {
 895                 if (! bptr->vp) continue;
 896                 if (! (bptr->flags >= BBREACHED)) continue;
 897                 if (bptr->expredecessorcount == 0) continue;
 898                 bbi = bb_info(bptr);
 899                 if (bbi->phi_count == 0) continue;
 900
 901                 for (ite = ssa->jd->exceptiontable; ite; ite = ite->down) {
 902                         /* Traverse all exhandlers */
 903                         if (bptr == ite->handler) {
 904                                 printf(" *** mess with handler bb%d\n", bptr->nr);
 905                                 catchtype = ite->catchtype;
 906                                 firstee = lastee = NULL;
 907                                 /* If bptr is handler, remove exhandler */
 908                                 /* Traverse all guarded blocks */
 909                                 for (ittry = ite->start; ittry != ite->end; ittry = ittry->next) {
 910                                         pei = 0;
 911                                         FOR_EACH_INSTRUCTION(ittry, iptr) {
 912                                                 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 913                                                         /* try is basicblock fragment till (including) the pei */
 914                                                         try = split_basicblock_at(ssa, ittry, iptr);
 915                                                         /* ee is handler for try */
 916                                                         ee = create_exception_handler(ssa, try, pei, bptr, catchtype);
 917                                                         ee->handler->invars[0] = ssa->jd->vartop + exhandler_count;
 918                                                         exhandler_count += 1;
 919                                                         ssa->jd->exceptiontablelength += 1;
 920                                                         if (firstee == NULL) {
 921                                                                 firstee = lastee = ee;
 922                                                         } else {
 923                                                                 lastee->next = ee;
 924                                                                 lastee->down = ee;
 925                                                                 lastee = ee;
 926                                                         }
 927                                                         pei += 1;
 928                                                 }
 929                                         }
 930                                 }
 931                                 /* XXX
 932                                    <------------------->
 933                                    <---><--><--->missing */
 934                                 if (firstee) {
 935                                         lastee->next = ite->next;
 936                                         lastee->down = ite->down;
 937                                         *ite = *firstee;
 938                                         ite = lastee;
 939                                 }
 940                         }
 941                 }
 942         }
 943
 944         /* Allocate interface vars */
 945
 946         ssa->jd->var = DMREALLOC(ssa->jd->var, varinfo, ssa->jd->vartop, ssa->jd->vartop + exhandler_count);
 947         for (v = ssa->jd->var + ssa->jd->vartop; v != ssa->jd->var + ssa->jd->vartop + exhandler_count; ++v) {
 948                 v->type = TYPE_ADR;
 949                 v->flags = INOUT;
 950         }
 951         ssa->jd->vartop += exhandler_count;
 952         ssa->jd->varcount += exhandler_count;
 953 }
 954
 955 void yssa(jitdata *jd) {
 956         basicblock *it;
 957         basicblock_info *iti;
 958         ssa_info *ssa;
 959
 960         if (jd->localcount == 0) return;
 961
 962         if (test_do_verbose(jd)) do_verbose = 1;
 963
 964         printf("=============== [ before %s ] =========================\n", jd->m->name->text);
 965         show_method(jd, 3);
 966         printf("=============== [ /before ] =========================\n");
 967
 968         ssa = DNEW(ssa_info);
 969         ssa->jd = jd;
 970         ssa->max_locals = sizeof(ssa->locals) / sizeof(ssa->locals[0]);
 971         MCOPY(ssa->locals, jd->var, varinfo, jd->localcount);
 972         ssa->locals_count = jd->localcount;
 973
 974         FOR_EACH_BASICBLOCK(jd, it) {
 975                 if (basicblock_reached(it)) {
 976                         iti = DNEW(basicblock_info);
 977                         MZERO(iti, basicblock_info, 1);
 978                         if (jd->localcount > 0) {
 979                                 iti->phi_functions = DMNEW(phi_function, jd->localcount);
 980                                 iti->phi_max = jd->localcount;
 981                         }
 982                         it->vp = iti;
 983                 } else {
 984                         it->vp = NULL;
 985                 }
 986         }
 987
 988         mark_loops(jd->basicblocks);
 989
 990         traverse(ssa, jd->basicblocks, traverse_fun_impl);
 991
 992         ssa_rename_others(ssa);
 993
 994         /*fill_in_phi_args(ssa);*/
 995
 996         ssa_export(ssa);
 997
 998         ssa_create_phi_moves(ssa);
 999         ssa_create_ex_phi_moves(ssa);
1000
1001         printf("=============== [ after ] =========================\n");
1002         show_method(jd, 3);
1003         printf("=============== [ /after ] =========================\n");
1004
1005         do_verbose = 0;
1006 }
1007
1008 void eliminate_subbasicblocks(jitdata *jd) {
1009         basicblock *bptr, *next;
1010
1011         FOR_EACH_BASICBLOCK(jd, bptr) {
1012                 if (bptr->subbasicblocks) {
1013                         next = bptr->next;
1014                         *bptr = *(bptr->subbasicblocks);
1015                         bptr->subbasicblocks = NULL;
1016
1017                         /* *prev = bptr->subbasicblocks;
1018                         bptr = bptr->subbasicblocks; */
1019
1020                         while (bptr->next) {
1021                                 bptr = bptr->next;
1022                         }
1023                         bptr->next = next;
1024                 }
1025         }
1026
1027         if (test_do_verbose(jd)) do_verbose = 1;
1028         printf("=============== [ elim ] =========================\n");
1029         show_method(jd, 3);
1030         printf("=============== [ /elim ] =========================\n");
1031         do_verbose = 0;
1032 }
1033
1034 /*
1035  * These are local overrides for various environment variables in Emacs.
1036  * Please do not remove this and leave it at the end of the file, where
1037  * Emacs will automagically detect them.
1038  * ---------------------------------------------------------------------
1039  * Local variables:
1040  * mode: c
1041  * indent-tabs-mode: t
1042  * c-basic-offset: 4
1043  * tab-width: 4
1044  * End:
1045  * vim:noexpandtab:sw=4:ts=4:
1046  */