src/vm/jit/optimizing/ssa2.c

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