src/vm/jit/optimizing/ssa2.c

   1 #include "config.h"
   2
   3 #include "mm/memory.h"
   4
   5 #include "toolbox/bitvector.h"
   6 #include "toolbox/set.h"
   7 #include "toolbox/worklist.h"
   8
   9 #include "vm/global.h"
  10 #include "vm/jit/jit.h"
  11
  12 #if 1
  13 #define printf(...) do { if (getenv("VERB")) printf(__VA_ARGS__); } while (0)
  14 #define show_method(...) do { if (getenv("VERB")) show_method(__VA_ARGS__); } while (0)
  15 #endif
  16
  17 typedef struct phi_function {
  18         s4 dst;
  19         s4 *args;
  20 } phi_function;
  21
  22 typedef struct basicblock_info {
  23         bitvector defines;
  24         bitvector phi;
  25         unsigned phi_count;
  26         phi_function *phi_functions;
  27 } basicblock_info;
  28
  29 typedef struct var_info {
  30         set *work;
  31         unsigned num_defs;
  32
  33         unsigned offset;
  34
  35         unsigned count;
  36         unsigned *stack;
  37         unsigned *stack_top;
  38
  39 } var_info;
  40
  41 typedef struct ssa_info {
  42         jitdata *jd;
  43         var_info *vars;
  44         unsigned vars_count;
  45         unsigned total_local_count;
  46 } ssa_info;
  47
  48 static inline basicblock_info *bb_info(basicblock *bb) {
  49         return (basicblock_info *)(bb->vp);
  50 }
  51
  52 static ssa_info *ssa_init(jitdata *jd) {
  53         unsigned i;
  54         ssa_info *ssa;
  55
  56         ssa = DNEW(ssa_info);
  57         ssa->jd = jd;
  58         ssa->vars_count = jd->localcount;
  59
  60         ssa->vars = DMNEW(var_info, ssa->vars_count);
  61         MZERO(ssa->vars, var_info, ssa->vars_count);
  62         for (i = 0; i < ssa->vars_count; ++i) {
  63                 ssa->vars[i].work = set_new(jd->basicblockcount);
  64         }
  65
  66         return ssa;
  67 }
  68
  69 static void ssa_place_phi_functions(ssa_info *ssa) {
  70
  71         basicblock *bptr, *Y, *n, **itdf;
  72         basicblock_info *bbi;
  73         instruction *iptr;
  74         s4 a;
  75         set *work;
  76
  77         for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
  78
  79                 bbi = DNEW(basicblock_info);
  80                 bbi->defines = bv_new(ssa->vars_count);
  81                 bbi->phi = bv_new(ssa->vars_count);
  82                 bbi->phi_count = 0;
  83
  84                 bptr->vp = bbi;
  85
  86                 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
  87                         if (instruction_has_dst(iptr)) {
  88                                 if (
  89                                         var_is_local(ssa->jd, iptr->dst.varindex)
  90                                 ) {
  91                                         /* A_orig */
  92                                         bv_set_bit(bbi->defines, iptr->dst.varindex);
  93                                         /* defsites */
  94                                         set_insert(ssa->vars[iptr->dst.varindex].work, bptr);
  95                                         /* Accout definition */
  96                                         ssa->vars[iptr->dst.varindex].num_defs += 1;
  97                                 }
  98                         }
  99                 }
 100         }
 101
 102         bptr = ssa->jd->basicblocks;
 103         bbi = bb_info(bptr);
 104         for (a = 0;  a < ssa->vars_count; ++a) {
 105                 bv_set_bit(bbi->defines, a);
 106                 set_insert(ssa->vars[a].work, bptr);
 107                 ssa->vars[a].num_defs += 1;
 108         }
 109
 110         for (a = 0; a < ssa->vars_count; ++a) {
 111                 work = ssa->vars[a].work;
 112                 while (! set_empty(work)) {
 113                         n = (basicblock *)set_pop(work);
 114                         for (
 115                                 itdf = n->domfrontier;
 116                                 itdf != n->domfrontier + n->domfrontiercount;
 117                                 ++itdf
 118                         ) {
 119                                 Y = *itdf;
 120                                 if (! bv_get_bit(bb_info(Y)->phi, a)) {
 121                                         bv_set_bit(bb_info(Y)->phi, a);
 122                                         printf(" *** BB %d: phi for var %d\n", Y->nr, a);
 123                                         bb_info(Y)->phi_count += 1;
 124                                         ssa->vars[a].num_defs += 1;
 125                                         if (! bv_get_bit(bb_info(Y)->defines, a)) {
 126                                                 set_insert(work, Y);
 127                                         }
 128                                 }
 129                         }
 130                 }
 131         }
 132 }
 133
 134 static void ssa_create_phi_functions(ssa_info *ssa) {
 135         unsigned i, j;
 136         basicblock_info *bbi;
 137         basicblock *bptr;
 138         phi_function *itph;
 139
 140         for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
 141
 142                 bbi = bb_info(bptr);
 143                 bbi->phi_functions = DMNEW(phi_function, bbi->phi_count);
 144                 itph = bbi->phi_functions;
 145
 146                 for (i = 0; i < ssa->vars_count; ++i) {
 147                         if (bv_get_bit(bbi->phi, i)) {
 148                                 itph->dst = i;
 149                                 itph->args = DMNEW(s4, bptr->predecessorcount);
 150                                 for (j = 0; j < bptr->predecessorcount; ++j) {
 151                                         itph->args[j] = i;
 152                                 }
 153                                 itph += 1;
 154                         }
 155                 }
 156         }
 157 }
 158
 159 static void ssa_calculate_offsets(ssa_info *ssa) {
 160         int i;
 161         unsigned cur_offset = ssa->jd->localcount;
 162
 163         ssa->total_local_count = 0;
 164
 165         for (i = 0; i < ssa->vars_count; ++i) {
 166
 167                 ssa->vars[i].offset = cur_offset;
 168
 169                 ssa->total_local_count += ssa->vars[i].num_defs;
 170
 171                 if (ssa->vars[i].num_defs > 1) {
 172                         cur_offset += (ssa->vars[i].num_defs - 1);
 173                 }
 174         }
 175 }
 176
 177
 178 static s4 ssa_rename_var(ssa_info *ssa, s4 var, unsigned index) {
 179         s4 ret;
 180 #define return ret=
 181         if (var_is_local(ssa->jd, var)) {
 182                 assert(0 < index && index <= ssa->vars[var].num_defs);
 183                 if (index == 1) {
 184                         return var;
 185                 } else {
 186                         return ssa->vars[var].offset + (index - 2);
 187                 }
 188                 assert(ret < ssa->total_local_count);
 189         } else {
 190                 return ssa->total_local_count + (var - ssa->vars_count);
 191         }
 192 #undef return
 193         printf(" *** rename %c %d vers %d => %d\n", var_is_local(ssa->jd, var) ? 'L' : 'O',  var, index, ret);
 194         return ret;
 195 }
 196
 197 static void ssa_rename_uses(ssa_info *ssa, s4 *uses, unsigned uses_count) {
 198         while (uses_count > 0) {
 199                 if (var_is_local(ssa->jd, *uses)) {
 200                         *uses = ssa_rename_var(ssa, *uses, *(ssa->vars[*uses].stack_top));
 201                 } else {
 202                         *uses = ssa_rename_var(ssa, *uses, 0);
 203                 }
 204                 uses_count -= 1;
 205                 uses += 1;
 206         }
 207 }
 208
 209 static void ssa_rename_definition(ssa_info *ssa, s4 *pdef) {
 210         s4 def = *pdef;
 211         unsigned i = 0;
 212
 213         if (var_is_local(ssa->jd, def)) {
 214                 ssa->vars[def].count += 1;
 215                 i = ssa->vars[def].count;
 216                 ssa->vars[def].stack_top += 1;
 217                 *(ssa->vars[def].stack_top) = i;
 218         }
 219
 220         *pdef = ssa_rename_var(ssa, def, i);
 221 }
 222
 223 static void ssa_rename_block(ssa_info *ssa, basicblock *bptr) {
 224
 225         basicblock_info *bbi = bb_info(bptr);
 226         s4 s[3];
 227         s4 *uses;
 228         unsigned uses_count;
 229         instruction *iptr;
 230         basicblock **itsucc, **itpred, **itdsucc, *Y;
 231         phi_function *itph;
 232         unsigned j;
 233         s4 i, tmp;
 234         s4 a;
 235         s4 **orig_stack_top;
 236
 237         /* XXX */
 238         orig_stack_top = DMNEW(s4 *, ssa->vars_count);
 239         for (a = 0; a < ssa->vars_count; ++a) orig_stack_top[a] = ssa->vars[a].stack_top;
 240
 241                 int jj;
 242
 243 printf(" *** === %d ===========\n", bptr->nr);
 244
 245         ssa_rename_uses(ssa, bptr->invars, bptr->indepth);
 246
 247         /* Phi functions are the first instructions in the block */
 248 printf(" *** --- phis ---------\n");
 249         for (
 250                 itph = bbi->phi_functions;
 251                 itph != bbi->phi_functions + bbi->phi_count;
 252                 ++itph
 253         ) {
 254                 ssa_rename_definition(ssa, &(itph->dst));
 255         }
 256
 257 printf(" *** --- vars ---------\n");
 258
 259         if (bptr == ssa->jd->basicblocks) {
 260                 for (i = 0; i < ssa->jd->localcount; ++i) {
 261                         tmp = i;
 262                         ssa_rename_definition(ssa, &tmp);
 263                 }
 264         }
 265
 266         for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
 267
 268                 /* Determine uses */
 269
 270                 uses_count = 0;
 271
 272                 switch (icmd_table[iptr->opc].dataflow) {
 273                         case DF_3_TO_0:
 274                         case DF_3_TO_1:
 275                                 s[2] = iptr->sx.s23.s3.varindex;
 276                                 uses_count += 1;
 277
 278                         case DF_2_TO_0:
 279                         case DF_2_TO_1:
 280                                 s[1] = iptr->sx.s23.s2.varindex;
 281                                 uses_count += 1;
 282
 283                         case DF_1_TO_0:
 284                         case DF_1_TO_1:
 285                         case DF_COPY:
 286                         case DF_MOVE:
 287                                 s[0] = iptr->s1.varindex;
 288                                 uses_count += 1;
 289
 290                                 uses = s;
 291                                 break;
 292
 293                         case DF_N_TO_1:
 294                         case DF_INVOKE:
 295                         case DF_BUILTIN:
 296
 297                                 uses = iptr->sx.s23.s2.args;
 298                                 uses_count = iptr->s1.argcount;
 299                                 break;
 300
 301                 }
 302
 303                 printf(" *** %s uses ", icmd_table[iptr->opc].name);
 304                 for (jj = 0; jj < uses_count; ++jj) printf("%d ",uses[jj]);
 305                 printf("\n");
 306
 307                 if (uses_count > 0) {
 308                         /* Update uses, if there are any */
 309
 310                         ssa_rename_uses(ssa, uses, uses_count);
 311
 312                         /* If uses were s, then we need to update the instruction */
 313
 314                         if (uses == s) {
 315                                 switch (uses_count) {
 316                                         case 3:
 317                                                 iptr->sx.s23.s3.varindex = s[2];
 318                                         case 2:
 319                                                 iptr->sx.s23.s2.varindex = s[1];
 320                                         case 1:
 321                                                 iptr->s1.varindex = s[0];
 322                                 }
 323                         }
 324                 }
 325
 326                 /* Rename definitions */
 327
 328                 if (instruction_has_dst(iptr)) {
 329                         printf(" *** %s defines %d\n", icmd_table[iptr->opc].name, iptr->dst.varindex);
 330                         ssa_rename_definition(ssa, &(iptr->dst.varindex));
 331                 }
 332
 333         }
 334
 335         for (i = 0; i < bptr->outdepth; ++i) {
 336                 ssa_rename_definition(ssa, bptr->outvars + i);
 337         }
 338
 339         /* Successors */
 340
 341         printf(" *** succs %d\n", bptr->successorcount);
 342
 343         for (
 344                 itsucc = bptr->successors;
 345                 itsucc != bptr->successors + bptr->successorcount;
 346                 ++itsucc
 347         ) {
 348                 Y = *itsucc;
 349
 350                 for (
 351                         itpred = Y->predecessors, j = 0;
 352                         itpred != Y->predecessors + Y->predecessorcount;
 353                         ++itpred, ++j
 354                 ) {
 355                         if (*itpred == bptr) break;
 356                 }
 357
 358                 assert(j != Y->predecessorcount);
 359
 360                 for (
 361                         itph = bb_info(Y)->phi_functions;
 362                         itph != bb_info(Y)->phi_functions + bb_info(Y)->phi_count;
 363                         ++itph
 364                 ) {
 365                         ssa_rename_uses(ssa, itph->args + j, 1);
 366                 }
 367         }
 368
 369         /* Recurse */
 370
 371         for (
 372                 itdsucc = bptr->domsuccessors;
 373                 itdsucc != bptr->domsuccessors + bptr->domsuccessorcount;
 374                 ++itdsucc
 375         ) {
 376                 ssa_rename_block(ssa, *itdsucc);
 377         }
 378
 379         /* For each definition of some variable a in the original S, pop stack */
 380
 381         /* XXX */
 382         for (a = 0; a < ssa->vars_count; ++a)  ssa->vars[a].stack_top = orig_stack_top[a];
 383 }
 384
 385 static void ssa_rename(ssa_info *ssa) {
 386         unsigned i;
 387
 388         for (i = 0; i < ssa->vars_count; ++i) {
 389                 ssa->vars[i].stack = DMNEW(unsigned, ssa->vars[i].num_defs + 1);
 390                 ssa->vars[i].stack[0] = 0;
 391                 ssa->vars[i].stack_top = ssa->vars[i].stack;
 392         }
 393
 394         ssa_rename_block(ssa, ssa->jd->basicblocks);
 395 }
 396
 397 static void ssa_export(ssa_info *ssa) {
 398         unsigned i, j;
 399         jitdata *jd = ssa->jd;
 400         methoddesc *md = jd->m->parseddesc;
 401         varinfo *vars, *it;
 402         s4 vartop, varindex;
 403
 404         vartop = ssa->total_local_count + jd->vartop - jd->localcount;
 405         vars = DMNEW(varinfo, vartop);
 406
 407         printf(" *** vartop(%d) = ssa->total_local_count(%d) + jd->vartop(%d) - jd->localcount(%d)\n",
 408                 vartop , ssa->total_local_count , jd->vartop , jd->localcount);
 409
 410         it = vars;
 411
 412         /* Version 1 of each local */
 413
 414         for (i = 0; i < jd->localcount; ++i) {
 415                 *(it++) = jd->var[i];
 416         }
 417
 418         /* Other versions of each local */
 419
 420         for (i = 0; i < jd->localcount; ++i) {
 421                 for (j = 1; j < ssa->vars[i].num_defs; ++j) {
 422                         *(it++) = jd->var[i];
 423                 }
 424         }
 425
 426         /* Other vars */
 427
 428         for (i = jd->localcount; i < jd->vartop; ++i) {
 429                 *(it++) = jd->var[i];
 430         }
 431
 432         jd->var = vars;
 433         jd->vartop = jd->varcount = vartop;
 434
 435         jd->local_map = DMREALLOC(jd->local_map, s4, 5 * jd->maxlocals, 5 * (jd->maxlocals + ssa->total_local_count - jd->localcount));
 436
 437         for (i = 0; i < ssa->total_local_count - jd->localcount; ++i) {
 438                 for (j = 0; j < 5; ++j) {
 439                         varindex = jd->localcount + i;
 440                         if (jd->var[varindex].type != j) {
 441                                 varindex = UNUSED;
 442                         }
 443                         jd->local_map[((jd->maxlocals + i) * 5) + j] = varindex;
 444                 }
 445         }
 446
 447         jd->maxlocals += (ssa->total_local_count - jd->localcount);
 448         jd->localcount = ssa->total_local_count;
 449
 450         printf(" *** jd->localcount %d, jd->maxlocals %d\n", jd->localcount , jd->maxlocals);
 451 }
 452
 453 unsigned get_predecessor_index(basicblock *from, basicblock *to) {
 454         basicblock **itpred;
 455         unsigned j = 0;
 456
 457         for (itpred = to->predecessors; itpred != to->predecessors + to->predecessorcount; ++itpred) {
 458                 if (*itpred == from) break;
 459                 j++;
 460         }
 461
 462         if (j == to->predecessorcount) {
 463                 printf(" *** %d => %d\n", from->nr, to->nr);
 464                 assert(j != to->predecessorcount);
 465         }
 466
 467         return j;
 468 }
 469
 470 basicblock *create_block(ssa_info *ssa, basicblock *from, basicblock *to) {
 471         basicblock *mid;
 472         basicblock_info *toi;
 473         instruction *iptr;
 474         phi_function *itph;
 475         unsigned j = get_predecessor_index(from, to);
 476
 477         mid = DNEW(basicblock);
 478         MZERO(mid, basicblock, 1);
 479
 480         toi = bb_info(to);
 481         assert(toi);
 482
 483         mid->nr = ssa->jd->basicblockcount;
 484         ssa->jd->basicblockcount += 1;
 485         mid->mpc = -1;
 486         mid->type = 666;
 487         mid->icount = toi->phi_count + 1;
 488         iptr = mid->iinstr = DMNEW(instruction, mid->icount);
 489         MZERO(mid->iinstr, instruction, mid->icount);
 490
 491         for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
 492                 iptr->opc = ICMD_COPY;
 493                 iptr->dst.varindex = itph->dst;
 494                 iptr->s1.varindex =  itph->args[j];
 495                 assert(itph->dst < ssa->total_local_count);
 496                 assert(itph->args[j] < ssa->total_local_count);
 497                 iptr++;
 498         }
 499
 500         iptr->opc = ICMD_GOTO;
 501         iptr->dst.block = to;
 502
 503         while (from->next) {
 504                 from = from->next;
 505         }
 506
 507         from->next = mid;
 508
 509         return mid;
 510 }
 511
 512 void crate_fallthrough(ssa_info *ssa, basicblock *bptr) {
 513         unsigned j;
 514         basicblock_info *toi;
 515         instruction *iptr;
 516         phi_function *itph;
 517
 518         if (bptr->next == NULL) return;
 519
 520         j = get_predecessor_index(bptr, bptr->next);
 521
 522         toi = bb_info(bptr->next);
 523         assert(toi);
 524
 525         bptr->iinstr = DMREALLOC(bptr->iinstr, instruction, bptr->icount, bptr->icount + toi->phi_count);
 526         iptr = bptr->iinstr + bptr->icount;
 527         bptr->icount += toi->phi_count;
 528
 529         for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
 530                 iptr->opc = ICMD_COPY;
 531                 iptr->dst.varindex = itph->dst;
 532                 iptr->s1.varindex =  itph->args[j];
 533                 assert(itph->dst < ssa->total_local_count);
 534                 assert(itph->args[j] < ssa->total_local_count);
 535                 iptr++;
 536         }
 537
 538 }
 539
 540 void ssa_create_phi_moves(ssa_info *ssa) {
 541         basicblock *bptr;
 542         instruction *iptr;
 543
 544         s4 i, l;
 545         branch_target_t *table;
 546         lookup_target_t *lookup;
 547         bool gt;
 548
 549         for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
 550                 if (bptr->type == 666) {
 551                         bptr->type = BBTYPE_STD;
 552                         continue;
 553                 }
 554                 if (! bptr->vp) continue;
 555                 if (! (bptr->flags >= BBREACHED)) continue;
 556                 gt = false;
 557                 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
 558                         switch (icmd_table[iptr->opc].controlflow) {
 559                                 case CF_IF:
 560                                 case CF_RET:
 561                                 case CF_GOTO:
 562                                         iptr->dst.block = create_block(ssa, bptr, iptr->dst.block);
 563                                         break;
 564                                 case CF_TABLE:
 565                                         table = iptr->dst.table;
 566                                         l = iptr->sx.s23.s2.tablelow;
 567                                         i = iptr->sx.s23.s3.tablehigh;
 568                                         i = i - l + 1;
 569                                         i += 1; /* default */
 570                                         while (--i >= 0) {
 571                                                 table->block = create_block(ssa, bptr, table->block);
 572                                                 ++table;
 573                                         }
 574                                         break;
 575                                 case CF_LOOKUP:
 576                                         lookup = iptr->dst.lookup;
 577                                         i = iptr->sx.s23.s2.lookupcount;
 578                                         while (--i >= 0) {
 579                                                 lookup->target.block = create_block(ssa, bptr, lookup->target.block);
 580                                                 lookup++;
 581                                         }
 582                                         iptr->sx.s23.s3.lookupdefault.block = create_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
 583                                         break;
 584                                 case CF_JSR:
 585                                         iptr->sx.s23.s3.jsrtarget.block = create_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
 586                                         break;
 587                         }
 588                         if ((iptr->opc == ICMD_GOTO) || icmd_table[iptr->opc].controlflow == CF_END)
 589                                 gt = true;
 590                         else if (iptr->opc != ICMD_NOP)
 591                                 gt = false;
 592                 }
 593                 if (! bptr->next) continue;
 594                 if (! (bptr->next->flags >= BBREACHED)) continue;
 595                 if (bptr->next->type == 666) continue;
 596                 if (!gt) crate_fallthrough(ssa, bptr);
 597         }
 598 }
 599
 600 void xssa(jitdata *jd) {
 601         ssa_info *ssa = ssa_init(jd);
 602
 603         printf("=============== [ before %s ] =========================\n", jd->m->name->text);
 604         show_method(jd, 3);
 605         printf("=============== [ /before ] =========================\n");
 606
 607         ssa_place_phi_functions(ssa);
 608         ssa_create_phi_functions(ssa);
 609         ssa_calculate_offsets(ssa);
 610         ssa_rename(ssa);
 611         ssa_export(ssa);
 612         ssa_create_phi_moves(ssa);
 613
 614         printf("=============== [ after ] =========================\n");
 615         show_method(jd, 3);
 616         printf("=============== [ /after ] =========================\n");
 617 }
 618