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