src/vm/jit/optimizing/ssa.c

   1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29
  30 */
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33
  34 #include "mm/memory.h"
  35
  36 #include "toolbox/bitvector.h"
  37 #include "toolbox/worklist.h"
  38
  39 #include "vm/builtin.h"
  40
  41 #include "vm/jit/jit.h" /* icmd_table */
  42
  43 #include "vm/jit/optimizing/dominators.h"
  44 #include "vm/jit/optimizing/graph.h"
  45 #include "vm/jit/optimizing/lifetimes.h"
  46 #include "vm/jit/optimizing/lsra.h"
  47
  48 #include "vm/jit/optimizing/ssa.h"
  49
  50 #if defined(SSA_DEBUG_VERBOSE)
  51 #include "vmcore/options.h"   /* compileverbose */
  52 #endif
  53
  54 /* function prototypes */
  55 void ssa_set_local_def(lsradata *, int , int);
  56 void ssa_set_interface(jitdata *, basicblock *, s4 *);
  57
  58 void dead_code_elimination(jitdata *jd, graphdata *gd);
  59 void copy_propagation(jitdata *jd, graphdata *gd);
  60 void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
  61                                                 int , worklist *);
  62 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
  63 void ssa_rename_init(jitdata *jd, graphdata *gd);
  64 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
  65 void ssa_rename_(jitdata *jd,  graphdata *gd, dominatordata *dd, int n);
  66
  67 void ssa_set_def(lsradata *, int , int );
  68 void ssa_set_local_def(lsradata *, int , int );
  69 void ssa_set_iovar(lsradata *, s4 , int , s4 *);
  70 void ssa_set_interface(jitdata *, basicblock *, s4 *);
  71
  72 void ssa_generate_phi_moves(jitdata *, graphdata *);
  73 int ssa_rename_def_(lsradata *ls, int a);
  74
  75 #ifdef SSA_DEBUG_VERBOSE
  76 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
  77 void ssa_print_lt(lsradata *ls);
  78 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
  79 void ssa_print_phi(lsradata *, graphdata *);
  80 #endif
  81
  82 /* ssa ************************************************************************
  83
  84 SSA main procedure:
  85
  86 ******************************************************************************/
  87
  88 void ssa(jitdata *jd, graphdata *gd) {
  89         struct dominatordata *dd;
  90         lsradata *ls;
  91
  92         ls = jd->ls;
  93
  94         dd = compute_Dominators(gd, ls->basicblockcount);
  95         computeDF(gd, dd, ls->basicblockcount, 0);
  96
  97         ssa_place_phi_functions(jd, gd, dd);
  98         ssa_rename(jd, gd, dd);
  99 #ifdef SSA_DEBUG_VERBOSE
 100         if (compileverbose) {
 101                 printf("Phi before Cleanup\n");
 102                 ssa_print_phi(ls, gd);
 103                 ssa_print_lt(ls);
 104         }
 105 #endif
 106         lt_scanlifetimes(jd, gd, dd);
 107 #ifdef SSA_DEBUG_VERBOSE
 108         if (compileverbose) {
 109                 ssa_print_lt(ls);
 110         }
 111 #endif
 112 /*      dead_code_elimination(jd, gd); */
 113 #ifdef SSA_DEBUG_VERBOSE
 114         if (compileverbose) {
 115                 printf("Phi after dead code elemination\n");
 116                 ssa_print_phi(ls, gd);
 117                 ssa_print_lt(ls);
 118         }
 119 #endif
 120 /*      copy_propagation(jd, gd); */
 121 #ifdef SSA_DEBUG_VERBOSE
 122         if (compileverbose) {
 123                 printf("Phi after copy propagation\n");
 124                 ssa_print_phi(ls, gd);
 125                 ssa_print_lt(ls);
 126         }
 127 #endif
 128
 129         ssa_generate_phi_moves(jd, gd);
 130         transform_BB(jd, gd);
 131
 132
 133 #ifdef SSA_DEBUG_CHECK
 134         {
 135                 int i, j, pred, in_d, out_d;
 136                 graphiterator iter_pred;
 137                 s4 *in, *out;
 138                 bool phi_define;
 139                 methodinfo *m;
 140
 141                 m = jd->m;
 142
 143                 for(i = 0; i < ls->basicblockcount; i++) {
 144                         if (ls->basicblocks[i]->indepth != 0) {
 145                                 pred = graph_get_first_predecessor(gd, i, &iter_pred);
 146                                 for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
 147                                         in_d = ls->basicblocks[i]->indepth - 1;
 148                                         in = ls->basicblocks[i]->invars;
 149                                         for (; in_d >= 0; in_d--) {
 150                                                 phi_define = false;
 151                                                 for (j = 0; (!phi_define) && (j<ls->ssavarcount); j++) {
 152                                                         if (ls->phi[i][j] != NULL)
 153                                                                 if (ls->phi[i][j][0] == in[in_d])
 154                                                                         phi_define = true;
 155                                                 }
 156                                                 if (!phi_define) {
 157                                                         /* in not defined in phi function -> check with */
 158                                                         /* outstack(s)  of predecessor(s) */
 159                                                         out_d = ls->basicblocks[pred]->outdepth - 1;
 160                                                         out = ls->basicblocks[pred]->outvars;
 161                                                         _SSA_ASSERT(out_d >= in_d);
 162                                                         for(; out_d > in_d; out_d--);
 163                                                         if ((in[in_d] != out[out_d]) ||
 164                                                         (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
 165                                                                 printf("Method: %s %s\n",
 166                                                                            m->class->name->text, m->name->text);
 167                                                                         printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
 168                                                                 if (compileverbose)
 169                                                                         printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
 170 /*                                                              else */
 171 /*                                                                      _SSA_ASSERT(0); */
 172                                                         }
 173                                                 }
 174                                         }
 175                                 }
 176                         }
 177                 }
 178         }
 179
 180 #endif
 181
 182
 183 #ifdef SSA_DEBUG_VERBOSE
 184         if (compileverbose)
 185                 ssa_print_trees(jd, gd, dd);
 186 #endif
 187 }
 188
 189 /* ssa_init *******************************************************************
 190
 191 Initialise data structures for ssa
 192
 193 IOVARS of same stackdepth and same type are coalesced:
 194 interface_map[ 5 * stackdepth + type ] = new_varindex with
 195 0 <= new_varindex < ls->ssavarcount
 196
 197 TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent
 198 basic blocks could decrease the number of phi functions and so improve ssa
 199 analysis performance!
 200
 201 All LOCALVARS and IOVARS get a new unique varindex:
 202 ls->new_varindex[0..jd->varcount[ = new_varindex with
 203 0 <= new_varindex < ls->ssavarcount
 204
 205 The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[
 206  are set  to the definitions of LOCALVARS and IOVARS. (So the only the first
 207 ls->ssavarcount bits of each of these vectors contain valid data, but
 208 ls->ssavarcount is computed at the same time as the definitons are stored.)
 209
 210 The basic block number used as index for the bitvector array ls->var_def is
 211 already shifted by one to make space for the new basic block 0 for parameter
 212 initialization.
 213
 214 ******************************************************************************/
 215
 216 void ssa_init(jitdata *jd) {
 217         int         p, t, v;
 218         methoddesc  *md;
 219         int         i, l, b_index, len;
 220         instruction *iptr;
 221         basicblock  *bptr;
 222         s4          *interface_map; /* holds an new unique index for every used  */
 223                                     /* basic block inoutvar described by a dupel */
 224                                 /*(depth,type). Used to coalesce the inoutvars*/
 225         methodinfo   *m;
 226         lsradata     *ls;
 227         builtintable_entry *bte;
 228
 229         ls = jd->ls;
 230         m = jd->m;
 231         md = m->parseddesc;
 232
 233
 234 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
 235 # if defined(SSA_DEBUG_VERBOSE)
 236         if (compileverbose) {
 237                 printf("%s %s ",m->class->name->text, m->name->text);
 238                 if (jd->isleafmethod)
 239                         printf("**Leafmethod**");
 240                 printf("\n");
 241         }
 242 # endif
 243         if (strcmp(m->class->name->text,"spec/benchmarks/_213_javac/Parser")==0)
 244                 if (strcmp(m->name->text,"parseTerm")==0)
 245 # if defined(SSA_DEBUG_VERBOSE)
 246                         if (compileverbose)
 247                                 printf("12-------------------12\n");
 248 # else
 249                 { int dummy=1; dummy++; }
 250 # endif
 251 #endif
 252
 253 #ifdef SSA_DEBUG_VERBOSE
 254     if (compileverbose)
 255                 printf("ssa_init: basicblockcount %3i localcount %3i\n",
 256                            jd->basicblockcount, jd->localcount);
 257 #endif
 258
 259         /* As first step all definitions of local variables and in/out vars are */
 260         /* gathered. in/outvars are coalesced for same type and depth           */
 261         /* "normal" tempvars (just living within one basicblock are) ignored    */
 262
 263         /* ls->var holds the index to jd->vars  */
 264
 265         ls->num_defs = DMNEW(int, jd->varcount);
 266         ls->new_varindex = DMNEW(int , jd->varcount);
 267
 268         for(p = 0; p < jd->varcount; p++) {
 269                 ls->num_defs[p] = 0;
 270                 ls->new_varindex[p] = UNUSED;
 271         }
 272
 273         /* init Var Definition bitvectors */
 274
 275         ls->var_def = DMNEW(int *, jd->basicblockcount + 1);
 276         for(i = 0; i < jd->basicblockcount + 1; i++) {
 277                 ls->var_def[i] =  bv_new(jd->varcount);
 278         }
 279
 280         ls->ssavarcount = 0;
 281
 282         /* Add parameters first in right order, so the new local indices */
 283         /* 0..p will correspond to "their" parameters */
 284         /* They get defined at the artificial Block 0, the real method bbs will be*/
 285         /* moved to start at block 1 */
 286
 287         /* don't look at already eliminated (not used) parameters (locals) */
 288
 289         for (p = 0, l = 0; p < md->paramcount; p++) {
 290                 t = md->paramtypes[p].type;
 291                 i = jd->local_map[l * 5 + t];
 292                 l++;
 293                 if (IS_2_WORD_TYPE(t))    /* increment local counter a second time  */
 294                         l++;                  /* for 2 word types */
 295                 if (i == UNUSED)
 296                         continue;
 297                 ssa_set_local_def(ls, -1, i);
 298         }
 299
 300         _SSA_ASSERT(ls->ssavarcount < jd->varcount);
 301
 302         /* coalesce bb in/out vars */
 303
 304         interface_map = DMNEW(s4, jd->stackcount * 5);
 305         for(i = 0; i < jd->stackcount * 5; i++)
 306                 interface_map[i] = UNUSED;
 307
 308         bptr = jd->basicblocks;
 309
 310         for(; bptr != NULL; bptr = bptr->next) {
 311 #ifdef SSA_DEBUG_VERBOSE
 312         if (compileverbose)
 313                 printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags);
 314 #endif
 315                 if (bptr->flags >= BBREACHED) {
 316
 317                         /* 'valid' Basic Block */
 318
 319                         b_index = bptr->nr;
 320
 321                         len = bptr->icount;
 322                         iptr = bptr->iinstr;
 323                         ssa_set_interface(jd, bptr, interface_map);
 324
 325                         /* !!!!!!!!! not true for now !!!!!!!!! */
 326                         /* All baseline optimizations from stack.c are turned off for */
 327                         /* SSA! */
 328
 329                         for (; len > 0; len--, iptr++) {
 330
 331                                 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
 332                                 /* an optional dst - so they to be checked first */
 333
 334                                 v = UNUSED;
 335                                 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
 336                                                 INSTRUCTION_GET_METHODDESC(iptr,md);
 337                                                 if (md->returntype.type != TYPE_VOID)
 338                                                         v = iptr->dst.varindex;
 339                                 }
 340                                 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
 341                                                 bte = iptr->sx.s23.s3.bte;
 342                                                 md = bte->md;
 343                                                 if (md->returntype.type != TYPE_VOID)
 344                                                         v = iptr->dst.varindex;
 345                                 }
 346                                 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
 347                                         v = iptr->dst.varindex;
 348                                 }
 349
 350                                 if (v != UNUSED) {
 351                                         if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
 352                                   /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
 353
 354 /*                                              _SSA_ASSERT(ls->new_varindex[v] != UNUSED); */
 355                                                 ssa_set_local_def(ls, b_index, v);
 356                                         }
 357                                 }
 358                         }
 359                 }
 360         }
 361         _SSA_ASSERT(ls->ssavarcount < jd->varcount);
 362 #ifdef SSA_DEBUG_VERBOSE
 363         if (compileverbose) {
 364
 365                 printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 366                            ls->ssavarcount);
 367                 for(i = 0; i < jd->varcount; i++) {
 368                         if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
 369                                 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 370                                 ssa_show_variable(jd, i, VAR(i),0);
 371                                 if (i < ls->ssavarcount) {
 372                                         printf(" -> %3i", ls->new_varindex[i]);
 373                                 }
 374                                 printf("\n");
 375                         }
 376                 }
 377         }
 378 #endif
 379 }
 380
 381 /* ssa_set_def ****************************************************************
 382
 383 Helper for ssa_set_local_def and ssa_set_interface
 384
 385 The definition of a var is stored in the bitvector array ls->var_def.
 386
 387 The number of definitons of each var is counted, so the number of new vars with
 388 SSA is known.
 389
 390 ******************************************************************************/
 391
 392 void ssa_set_def(lsradata *ls, int b_index, int varindex) {
 393
 394         /* b_index + 1 to leave space for the param init block 0 */
 395
 396         bv_set_bit(ls->var_def[b_index + 1], varindex);
 397
 398         /* count number of defs for every var since SSA */
 399         /* will create a new var for every definition */
 400
 401         ls->num_defs[varindex]++;
 402 }
 403
 404 /* ssa_set_local_def **********************************************************
 405
 406 Helper for ssa_init
 407
 408 Assigns a new unique index for the local var varindex (if not already done so)
 409 and then calls ssa_set_def to remember the definition in the bitvector array
 410 ls->var_def
 411
 412 ******************************************************************************/
 413
 414 void ssa_set_local_def(lsradata *ls, int b_index, int varindex) {
 415
 416         if (ls->new_varindex[varindex] == UNUSED) {
 417                 ls->new_varindex[varindex] = ls->ssavarcount++;
 418         }
 419
 420         ssa_set_def(ls, b_index, ls->new_varindex[varindex]);
 421 }
 422
 423 /* ssa_set_local_def **********************************************************
 424
 425 Helper for ssa_set_interface
 426
 427 IN: ls              pointer to lsradata structure
 428     iovar           varindex of INOUTVAR to process
 429         map_index       stackdepth * 5 + type, used for coalescing IOVARS.
 430
 431 IN/OUT
 432         interface_map   used for coalescing IOVARS. interface_map[map_index] ==
 433                         UNUSED, if this map_index (==stackdepth,type tupel) did not
 434                                         occur till now. Then interface_map[map_index] will be set
 435                                         to a new unique index.
 436         ls->new_varindex will be set to this new unique index to map the old
 437                          varindizes to the new ones.
 438
 439 Assigns a new unique index for the local var varindex (if not already done so)
 440 and then calls ssa_set_def to remember the definition in the bitvector array
 441 ls->var_def
 442
 443 ******************************************************************************/
 444
 445 void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) {
 446                 if (interface_map[map_index] == UNUSED)
 447                         interface_map[map_index] = ls->ssavarcount++;
 448
 449                 ls->new_varindex[iovar] = interface_map[map_index];
 450 }
 451
 452
 453 /* ssa_set_interface ***********************************************************
 454
 455 Helper for ssa_init
 456
 457 IN: ls              pointer to lsradata structure
 458     *bptr           pointer to the basic block to be processed
 459
 460 IN/OUT
 461         interface_map   used for coalescing IOVARS. interface_map[map_index] ==
 462                         UNUSED, if this map_index (==stackdepth,type tupel) did not
 463                                         occur till now. Then interface_map[map_index] will be set
 464                                         to a new unique index. (see ssa_set_iovar)
 465
 466 Searches the basic block given by *bptr for IN and OUTVARS and coalesces them
 467 for each unique stackdepth,type dupel. For each OUTVAR with a different or no
 468 INVAR at the same stackdepth the definition of this OUTVAR in this basic block
 469 is remembered in ls->var_def. (see ssa_set_def)
 470
 471 ******************************************************************************/
 472
 473 void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) {
 474         s4 *out, *in;
 475         int in_d, out_d;
 476         int o_map_index, i_map_index;
 477         lsradata *ls;
 478
 479         ls = jd->ls;
 480
 481         out = bptr->outvars;
 482         in = bptr->invars;
 483         in_d = bptr->indepth - 1;
 484         out_d = bptr->outdepth - 1;
 485
 486         /* ignore top Stackelement of instack in case of EXH or SBR blocks */
 487         /* These are no Interface stackslots! */
 488         if ((bptr->type == BBTYPE_EXH) ||
 489                 (bptr->type == BBTYPE_SBR)) {
 490                 in_d--;
 491         }
 492
 493         /* invars with no corresponding outvars are not defined here */
 494         /* just set up the interface_map */
 495
 496         for(;(in_d > out_d); in_d--) {
 497                 i_map_index = in_d * 5 + VAR(in[in_d])->type;
 498                 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
 499         }
 500
 501         while((out_d >= 0)) {
 502                 /* set up interface_map */
 503
 504                 o_map_index = out_d * 5 + VAR(out[out_d])->type;
 505                 if (in_d >= 0) {
 506                         i_map_index = in_d * 5 + VAR(in[in_d])->type;
 507                         ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
 508                 }
 509                 ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
 510                 if (in_d == out_d) {
 511                         if (in[in_d] != out[out_d]) {
 512
 513                                 /* out interface stackslot is defined in this basic block */
 514
 515 /*                              ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
 516                         }
 517                         out_d--;
 518                         in_d--;
 519                 }
 520                 else {
 521
 522                         /* in_d < out_d */
 523                         /* out interface stackslot is defined in this basic block */
 524
 525 /*                      ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
 526                         out_d--;
 527                 }
 528         }
 529 }
 530
 531 /* ssa_place_phi_functions *****************************************************
 532
 533 ls->phi[n][a][p] is created and populated.
 534
 535 For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
 536 ls->basicblockcount)in which a variable (0 <= a < ls->ssavarcount) is defined an
 537 entry in ls->phi[Y][a] is created.
 538 This entry is an array with the number of predecessors of Y elements + 1 elements.
 539 This elements are all set to the variable a and represent the phi function which
 540 will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
 541
 542 *******************************************************************************/
 543
 544
 545 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
 546 {
 547         int a,i,j,n,Y;
 548         bitvector *def_sites;
 549         bitvector *A_phi;    /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
 550         worklist *W;
 551         int num_pred;
 552
 553         lsradata *ls;
 554
 555         ls = jd->ls;
 556
 557         W = wl_new(ls->basicblockcount);
 558
 559         def_sites = DMNEW(bitvector, ls->ssavarcount);
 560         for(a = 0; a < ls->ssavarcount; a++)
 561                 def_sites[a] = bv_new(ls->basicblockcount);
 562
 563         ls->phi = DMNEW(int **, ls->basicblockcount);
 564         A_phi = DMNEW(bitvector, ls->basicblockcount);
 565         for(i = 0; i < ls->basicblockcount; i++) {
 566                 ls->phi[i] = DMNEW(int *, ls->ssavarcount);
 567                 for(j = 0; j < ls->ssavarcount; j++)
 568                         ls->phi[i][j] = NULL;
 569                 A_phi[i] = bv_new(ls->ssavarcount);
 570         }
 571
 572         /* copy var_def to def_sites */
 573         /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
 574
 575         for(n = 0; n <= jd->basicblockcount; n++)
 576                 for(a = 0; a < ls->ssavarcount; a++)
 577                         if (bv_get_bit(ls->var_def[n], a))
 578                                 bv_set_bit(def_sites[a], n);
 579 #ifdef SSA_DEBUG_VERBOSE
 580         if (compileverbose) {
 581                 printf("var Definitions:\n");
 582                 for(i = 0; i < ls->ssavarcount; i++) {
 583                         printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
 584                         for(j = 0; j < ls->basicblockcount; j++) {
 585                                 if ((j % 5) == 0) printf(" ");
 586                                 if (bv_get_bit(def_sites[i], j))
 587                                         printf("1");
 588                                 else
 589                                         printf("0");
 590                         }
 591                         printf(" (");
 592
 593                         printf("\n");
 594                 }
 595         }
 596 #endif
 597
 598         for(a = 0; a < ls->ssavarcount; a++) {
 599
 600                 /* W<-def_sites(a) */
 601
 602                 for(n = 0; n < ls->basicblockcount; n++)
 603                         if (bv_get_bit(def_sites[a],n)) {
 604                                 wl_add(W, n);
 605                         }
 606
 607                 while (!wl_is_empty(W)) { /* W not empty */
 608                         n = wl_get(W);
 609
 610                         for(i = 0; i < dd->num_DF[n]; i++) {
 611                                 Y = dd->DF[n][i];
 612                                 /* Node Y is in Dominance Frontier of n -> */
 613                                 /* insert phi function for a at top of Y*/
 614                                 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
 615                                 if (bv_get_bit( A_phi[Y], a) == 0) {
 616                                         /* a is not a Element of A_phi[Y] */
 617                                         /* a <- phi(a,a...,a) to be inserted at top of Block Y */
 618                                         /* phi has as many arguments, as Y has predecessors    */
 619 #if 0
 620 #if 0
 621                                         /* do not add a phi function for interface stackslots */
 622                                         /* if a predecessor is not a def site of a <==>       */
 623                                         /* the block does not have the corresponding inslot*/
 624
 625 /*                                      if ((ls->var_to_index[a] >= 0) || */
 626 /*                                              (bv_get_bit(def_sites[a],  */
 627 /*                                                                      graph_get_first_predecessor(gd, Y, &iter)))) */
 628
 629 #endif
 630                                         /* for interface stackslots add a phi function only */
 631                                         /* if the basicblock has the corresponding incoming */
 632                                         /* stackslot -> it could be, that the stackslot is */
 633                                         /* not live anymore at Y */
 634
 635 #endif
 636                                         num_pred =  graph_get_num_predecessor(gd, Y);
 637                                         ls->phi[Y][a] = DMNEW(int, num_pred + 1);
 638                                         for (j = 0; j < num_pred + 1; j++)
 639                                                 ls->phi[Y][a][j] = a;
 640                                         /* increment the number of definitions of a by one */
 641                                         /* for this phi function */
 642                                         ls->num_defs[a]++;
 643
 644                                         bv_set_bit(A_phi[Y], a);
 645                                         if (bv_get_bit(ls->var_def[Y],a)==0) {
 646                                                 /* Iterated Dominance Frontier Criterion:*/
 647                                                 /* if Y had no definition for a insert it*/
 648                                                 /* into the Worklist, since now it       */
 649                                                 /* defines a through the phi function    */
 650                                                 wl_add(W, Y);
 651                                         }
 652                                 }
 653                         }
 654                 }
 655         }
 656 }
 657
 658 /* ssa_rename ******************************************************************
 659
 660 Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
 661 has only one definition (SSA form).
 662
 663 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
 664 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
 665                               definition of each old var.
 666 ls->varcount_with_indices     will be se to the new maximum varcount of LOCAL
 667                               and IOVARS.
 668
 669 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
 670 ls->varcount_with_indices.
 671
 672 jd->var and jd->varcount will be set for this renamed vars.
 673
 674 *******************************************************************************/
 675
 676 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
 677 {
 678         int i, mi, l, j, p, t;
 679         int type, flags;
 680         methoddesc *md = jd->m->parseddesc;
 681
 682         varinfo *new_vars;
 683         lsradata *ls;
 684
 685         ls = jd->ls;
 686
 687         ssa_rename_init(jd, gd);
 688
 689         /* Consider definition of Local Vars initialized with Arguments */
 690         /* in Block 0 */
 691         /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
 692         for (p = 0, l= 0; p < md->paramcount; p++) {
 693                 t = md->paramtypes[p].type;
 694                 mi = l * 5 + t;
 695                 i = jd->local_map[mi];
 696                 l++;
 697                 if (IS_2_WORD_TYPE(t))
 698                         l++;
 699                 if (i == UNUSED)
 700                         continue;
 701                 /* !!!!! locals are now numbered as the parameters !!!! */
 702                 /* !!!!! no additional increment for 2 word types !!!!! */
 703                 /* this happens later on! here we still need the increment */
 704             /* index of var can be in the range from 0 up to not including */
 705             /* CD->maxlocals */
 706
 707                 /* ignore return value, since first definition gives 0 -> */
 708                 /* no rename necessary */
 709
 710                 i = ls->new_varindex[i];
 711                 j = ssa_rename_def_(ls, i);
 712                 _SSA_ASSERT(j == 0);
 713                 jd->local_map[mi] = i;
 714         }
 715         ssa_rename_(jd, gd, dd, 0);
 716
 717 #if 0
 718         /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
 719         /* if there is no use of the defined Var itself by the phi function */
 720         /* for a loop path, in which this var is not used, it will not be life */
 721         /* in this path and overwritten! */
 722
 723         /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
 724         /* this happens if the phi function is the first definition of x or in a */
 725         /* path with a backedge xi has no definition */
 726         /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
 727         /* this phi function would otherwise "deadlock" the dead code elemination */
 728         /* invalidate means set it to ls->max_vars_with_indices */
 729         /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
 730         /* [1,n] can be removed */
 731
 732         for(i = 0; i < ls->ssavarcount; i++) {
 733                 for(t = 0; t < ls->basicblockcount; t++) {
 734                         if (ls->phi[t][i] != 0) {
 735                                 remove_phi = true;
 736                                 for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
 737                                         if (ls->phi[t][i][0] == ls->phi[t][i][p])
 738                                                 ls->phi[t][i][p] = ls->varcount_with_indices;
 739                                         else
 740                                                 remove_phi = false;
 741                                 }
 742                         }
 743                         if (remove_phi)
 744                                 ls->phi[t][i] = NULL;
 745                 }
 746         }
 747 #endif
 748
 749 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
 750 # if defined(SSA_DEBUG_VERBOSE)
 751         if (compileverbose) {
 752                 printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
 753                 if (jd->isleafmethod)
 754                         printf("**Leafmethod**");
 755                 printf("\n");
 756         }
 757 # endif
 758         if (strcmp(jd->m->class->name->text,"fp")==0)
 759                 if (strcmp(jd->m->name->text,"testfloat")==0)
 760 # if defined(SSA_DEBUG_VERBOSE)
 761                         if (compileverbose)
 762                                 printf("12-------------------12\n");
 763 # else
 764                 { int dummy=1; dummy++; }
 765 # endif
 766 #endif
 767         /* recreate rd->locals[][] */
 768         /* now only one (local_index/type) pair exists anymore     */
 769         /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
 770         /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
 771
 772         new_vars = DMNEW(varinfo, ls->vartop);
 773         for(i = 0; i < ls->vartop ; i++)
 774                 new_vars[i].type = UNUSED;
 775         for(i = 0; i < jd->varcount; i++) {
 776                         p = ls->new_varindex[i];
 777                         if (p != UNUSED) {
 778                                 if (p < ls->ssavarcount)
 779                                         p = ls->var_0[p];
 780                                 new_vars[p].type  = VAR(i)->type;
 781                                 new_vars[p].flags = VAR(i)->flags;
 782                                 ls->lifetime[p].v_index = p;
 783                                 ls->lifetime[p].type = VAR(i)->type;
 784                         }
 785         }
 786
 787         /* take care of newly indexed local & in/out vars */
 788
 789         for(i = 0; i < ls->ssavarcount; i++) {
 790                 j = ls->var_0[i];
 791                 type = new_vars[j].type;
 792                 flags = new_vars[j].flags;
 793                 j++;
 794                 for (; j < ls->var_0[i + 1]; j++) {
 795                         new_vars[j].type = type;
 796                         new_vars[j].flags = flags;
 797                         ls->lifetime[j].v_index = j;
 798                         ls->lifetime[j].type = type;
 799                 }
 800         }
 801
 802 #ifdef SSA_DEBUG_VERBOSE
 803         if (compileverbose) {
 804
 805                 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 806                            ls->ssavarcount);
 807                 for(i = 0; i < jd->varcount; i++) {
 808                         printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 809                         ssa_show_variable(jd, i, VAR(i),0);
 810                         j = ls->new_varindex[i];
 811                         if ((j != UNUSED) && (j < ls->ssavarcount))
 812                                 printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
 813                         else
 814                                 printf(" -> %3i", j);
 815                         printf("\n");
 816                 }
 817         }
 818 #endif
 819
 820         jd->var = new_vars;
 821         jd->varcount = ls->vartop;
 822         jd->vartop = ls->vartop;
 823
 824 #ifdef SSA_DEBUG_VERBOSE
 825         if (compileverbose) {
 826                 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 827                            ls->ssavarcount);
 828                 for(i = 0; i < jd->varcount; i++) {
 829                         printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 830                         ssa_show_variable(jd, i, VAR(i),0);
 831                         printf("\n");
 832                 }
 833         }
 834 #endif
 835 }
 836
 837 /* ssa_rename_init *************************************************************
 838
 839 Setup the data structure for ssa_rename
 840
 841 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
 842 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
 843                               definition of each old var.
 844 ls->varcount_with_indices     will be se to the new maximum varcount of LOCAL
 845                               and IOVARS.
 846
 847 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
 848 ls->varcount_with_indices.
 849
 850 jd->var and jd->varcount will be set for this renamed vars.
 851
 852 *******************************************************************************/
 853
 854 void ssa_rename_init(jitdata *jd, graphdata *gd)
 855 {
 856         int a, i, p;
 857         lsradata *ls;
 858
 859         ls = jd->ls;
 860
 861         /* set up new locals */
 862         /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
 863         /* for locals and iovars */
 864
 865         /* ls->num_defs[index] gives the number of indizes which will be created  */
 866         /* from SSA */
 867
 868         /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
 869         /* ls->var_0[X] will point to each LX(0)  */
 870         /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
 871
 872         /* as first step cummulate the num_defs array for locals and iovars       */
 873         /* last element is the maximum var count */
 874
 875         ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
 876         ls->var_0[0] = 0;
 877         ls->varcount_with_indices = 0;
 878         for(i = 0; i < ls->ssavarcount; i++) {
 879                 ls->varcount_with_indices += ls->num_defs[i];
 880                 ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
 881         }
 882
 883 #if 0
 884         /* Change the var indices in phi from La to La(0) */
 885
 886         for(i = 0; i < ls->basicblockcount; i++)
 887                 for (a = 0; a < ls->ssavarcount; a++)
 888                         if (ls->phi[i][a] != NULL)
 889                                 for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
 890                                         ls->phi[i][a][p] = ls->var_0[a];
 891 #endif
 892
 893         /* Initialization */
 894
 895         ls->count     = DMNEW(int, max(1, ls->ssavarcount));
 896         ls->stack     = DMNEW(int *, max(1, ls->ssavarcount));
 897         ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
 898         for(a = 0; a < ls->ssavarcount; a++) {
 899                 ls->count[a] = 0;
 900                 ls->stack_top[a] = 0;
 901
 902                 /* stack a has to hold number of defs of a Elements + 1 */
 903
 904                 ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
 905                 ls->stack[a][ls->stack_top[a]++] = 0;
 906         }
 907
 908         if (ls->ssavarcount > 0) {
 909
 910                 /* Create the num_var_use Array */
 911
 912                 ls->num_var_use = DMNEW(int *, ls->basicblockcount);
 913                 for(i = 0; i < ls->basicblockcount; i++) {
 914                         ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
 915                         for(a = 0; a < ls->varcount_with_indices; a++)
 916                                 ls->num_var_use[i][a] = 0;
 917                 }
 918
 919                 /* Create the use_sites Array of Bitvectors*/
 920                 /* use max(1,..), to ensure that the array is created! */
 921
 922                 ls->use_sites =  DMNEW(bitvector, max(1, ls->varcount_with_indices));
 923                 for(a = 0; a < ls->varcount_with_indices; a++)
 924                         ls->use_sites[a] = bv_new(ls->basicblockcount);
 925         }
 926
 927         /* init lifetimes */
 928         /* count number of TEMPVARs */
 929
 930         ls->lifetimecount = 0;
 931         for(i = 0; i < jd->varcount; i++)
 932                 if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
 933                         ls->lifetimecount++;
 934
 935         ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
 936
 937         ls->lifetimecount = ls->varcount;
 938         ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
 939         ls->lt_used = DMNEW(int, ls->lifetimecount);
 940         ls->lt_int = DMNEW(int, ls->lifetimecount);
 941         ls->lt_int_count = 0;
 942         ls->lt_flt = DMNEW(int, ls->lifetimecount);
 943         ls->lt_flt_count = 0;
 944         ls->lt_mem = DMNEW(int, ls->lifetimecount);
 945         ls->lt_mem_count = 0;
 946         for (i=0; i < ls->lifetimecount; i++) {
 947                 ls->lifetime[i].type = UNUSED;
 948                 ls->lifetime[i].savedvar = 0;
 949                 ls->lifetime[i].flags = 0;
 950                 ls->lifetime[i].usagecount = 0;
 951                 ls->lifetime[i].bb_last_use = -1;
 952                 ls->lifetime[i].bb_first_def = -1;
 953                 ls->lifetime[i].use = NULL;
 954                 ls->lifetime[i].def = NULL;
 955                 ls->lifetime[i].last_use = NULL;
 956         }
 957
 958         /* for giving TEMP and PREALLOC vars a new unique index */
 959
 960         ls->vartop = ls->varcount_with_indices;
 961
 962 #ifdef SSA_DEBUG_VERBOSE
 963         if (compileverbose) {
 964                 printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 965                            ls->ssavarcount);
 966                 for(i = 0; i < jd->varcount; i++) {
 967                         if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
 968                                 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 969                                 ssa_show_variable(jd, i, VAR(i),0);
 970                                 if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
 971                                         printf(" -> %3i", ls->new_varindex[i]);
 972                                 }
 973                                 printf("\n");
 974                         }
 975                 }
 976                 ssa_print_phi(ls, gd);
 977         }
 978 #endif
 979 }
 980
 981 int ssa_rename_def_(lsradata *ls, int a) {
 982         int i;
 983
 984         _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
 985         ls->count[a]++;
 986         i = ls->count[a] - 1;
 987         /* push i on stack[a] */
 988         _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
 989         ls->stack[a][ls->stack_top[a]++] = i;
 990         return i;
 991 }
 992
 993 int ssa_rename_def(jitdata *jd, int *def_count, int a) {
 994         int i, a1, ret;
 995         lsradata *ls;
 996
 997         ls = jd->ls;
 998
 999         a1 = ls->new_varindex[a];
1000         _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1001         if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1002                 /* local or inoutvar -> normal ssa renaming */
1003                 _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
1004                 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
1005
1006                 def_count[a1]++;
1007                 i = ssa_rename_def_(ls, a1);
1008                 ret = ls->var_0[a1] + i;
1009         }
1010         else {
1011                 /* TEMP or PREALLOC var */
1012                 if (a1 == UNUSED) {
1013                         ls->new_varindex[a] = ls->vartop;
1014                         ret = ls->vartop;
1015                         ls->vartop++;
1016                         _SSA_ASSERT( ls->vartop < ls->varcount);
1017                 }
1018                 else
1019                         ret = a1;
1020         }
1021         return ret;
1022 }
1023
1024 void ssa_rename_use_(lsradata *ls, int n, int a) {
1025         _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
1026         if (ls->ssavarcount > 0) {
1027                 bv_set_bit(ls->use_sites[a], n);
1028                 ls->num_var_use[n][a]++;
1029         }
1030 }
1031
1032 int ssa_rename_use(lsradata *ls, int n, int a) {
1033         int a1, i;
1034         int ret;
1035
1036         a1 = ls->new_varindex[a];
1037         _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1038         if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1039                 /* local or inoutvar -> normal ssa renaming */
1040                 /* i <- top(stack[a]) */
1041
1042                 _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
1043                 i = ls->stack[a1][ls->stack_top[a1] - 1];
1044                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
1045
1046                 ret = ls->var_0[a1] + i;
1047         }
1048         else {
1049                 /* TEMP or PREALLOC var */
1050                 if (a1 == UNUSED) {
1051                         ls->new_varindex[a] = ls->vartop;
1052                         ret = ls->vartop;
1053                         ls->vartop++;
1054                         _SSA_ASSERT( ls->vartop < ls->varcount);
1055                 }
1056                 else
1057                         ret = a1;
1058         }
1059
1060         return ret;
1061 }
1062
1063 #ifdef SSA_DEBUG_VERBOSE
1064 void ssa_rename_print(instruction *iptr, char *op, int from,  int to) {
1065         if (compileverbose) {
1066                 printf("ssa_rename_: ");
1067                 if (iptr != NULL)
1068                         printf("%s ", opcode_names[iptr->opc]);
1069                 else
1070                         printf("       ");
1071
1072                 printf("%s: %3i->%3i\n", op, from, to);
1073         }
1074 }
1075 #endif
1076
1077 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
1078         int a, i, j, k, iindex, Y, v;
1079         int in_d, out_d;
1080         int *def_count;
1081         /* [0..ls->varcount[ Number of Definitions of this var in this  */
1082         /* Basic Block. Used to remove the entries off the stack at the */
1083         /* end of the function */
1084         instruction *iptr;
1085         s4 *in, *out, *argp;
1086         graphiterator iter_succ, iter_pred;
1087         struct lifetime *lt;
1088
1089         methoddesc *md;
1090         methodinfo *m;
1091         builtintable_entry *bte;
1092         lsradata *ls;
1093
1094         ls = jd->ls;
1095         m  = jd->m;
1096
1097 #ifdef SSA_DEBUG_VERBOSE
1098         if (compileverbose)
1099                 printf("ssa_rename_: BB %i\n",n);
1100 #endif
1101
1102         _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
1103
1104         def_count = DMNEW(int, max(1, ls->ssavarcount));
1105         for(i = 0; i < ls->ssavarcount; i++)
1106                 def_count[i] = 0;
1107
1108         /* change Store of possible phi functions from a to ai*/
1109
1110         for(a = 0; a < ls->ssavarcount; a++)
1111                 if (ls->phi[n][a] != NULL) {
1112                         def_count[a]++;
1113                                 /* do not mark this store as use - maybee this phi function */
1114                                 /* can be removed for unused Vars*/
1115                         j = ls->var_0[a] + ssa_rename_def_(ls, a);
1116 #ifdef SSA_DEBUG_VERBOSE
1117                         ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
1118 #endif
1119                         ls->phi[n][a][0] = j;
1120                 }
1121
1122         in   = ls->basicblocks[n]->invars;
1123         in_d = ls->basicblocks[n]->indepth - 1;
1124
1125         /* change use of instack Interface stackslots except top SBR and EXH */
1126         /* stackslots */
1127
1128         if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
1129                 (ls->basicblocks[n]->type == BBTYPE_SBR)) {
1130                 in_d--;
1131         }
1132 /*      out   = ls->basicblocks[n]->outvars; */
1133 /*      out_d = ls->basicblocks[n]->outdepth - 1; */
1134
1135 /*      for(; out_d > in_d; out_d--); */
1136
1137         for (; in_d >= 0; in_d--) {
1138                 /* Possible Use of ls->new_varindex[jd->var[in_d]] */
1139                 _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
1140
1141                 a = ls->new_varindex[in[in_d]];
1142                 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1143
1144                 /* i <- top(stack[a]) */
1145
1146                 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1147                 i = ls->stack[a][ls->stack_top[a]-1];
1148                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1149
1150                 /* Replace use of x with xi */
1151
1152 #ifdef SSA_DEBUG_VERBOSE
1153                         ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
1154 #endif
1155                 in[in_d] = ls->var_0[a] + i;
1156                 lt = ls->lifetime + in[in_d];
1157
1158                 lt->v_index = in[in_d];
1159                 lt->bb_last_use = -1;
1160         }
1161
1162         iptr = ls->basicblocks[n]->iinstr;
1163
1164         for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
1165
1166                 /* check for use (s1, s2, s3 or special (argp) ) */
1167
1168                 switch (icmd_table[iptr->opc].dataflow) {
1169                 case DF_3_TO_0:
1170                 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1171                         j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
1172 #ifdef SSA_DEBUG_VERBOSE
1173                         ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
1174 #endif
1175                         iptr->sx.s23.s3.varindex = j;
1176
1177                         /* now "fall through" for handling of s2 and s1 */
1178
1179                 case DF_2_TO_0:
1180                 case DF_2_TO_1: /* icmd has s1 and s2 */
1181                         j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
1182 #ifdef SSA_DEBUG_VERBOSE
1183                         ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
1184 #endif
1185                         iptr->sx.s23.s2.varindex = j;
1186
1187                         /* now "fall through" for handling of s1 */
1188
1189                 case DF_1_TO_0:
1190                 case DF_1_TO_1:
1191                 case DF_MOVE:
1192                 case DF_COPY:
1193                         j = ssa_rename_use(ls, n, iptr->s1.varindex);
1194 #ifdef SSA_DEBUG_VERBOSE
1195                         ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
1196 #endif
1197                         iptr->s1.varindex = j;
1198                         break;
1199
1200                 case DF_INVOKE:
1201                 case DF_BUILTIN:
1202                 case DF_N_TO_1:
1203                         /* do not use md->paramcount, pass-through stackslots have */
1204                         /* to be renamed, too */
1205                         i = iptr->s1.argcount;
1206                         argp = iptr->sx.s23.s2.args;
1207                         while (--i >= 0) {
1208                                 j = ssa_rename_use(ls, n, *argp);
1209 #ifdef SSA_DEBUG_VERBOSE
1210                                 ssa_rename_print( iptr, "arg", *argp, j);
1211 #endif
1212                                 *argp = j;
1213                                 argp++;
1214                         }
1215                         break;
1216                 }
1217
1218
1219                 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
1220                 /* an optional dst - so they to be checked first */
1221
1222                 v = UNUSED;
1223                 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
1224                         INSTRUCTION_GET_METHODDESC(iptr,md);
1225                         if (md->returntype.type != TYPE_VOID)
1226                                 v = iptr->dst.varindex;
1227                 }
1228                 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
1229                         bte = iptr->sx.s23.s3.bte;
1230                         md = bte->md;
1231                         if (md->returntype.type != TYPE_VOID)
1232                                 v = iptr->dst.varindex;
1233                 }
1234                 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
1235                         v = iptr->dst.varindex;
1236                 }
1237
1238                 if (v != UNUSED) {
1239                         j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
1240 #ifdef SSA_DEBUG_VERBOSE
1241                         ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
1242 #endif
1243                         iptr->dst.varindex = j;
1244                 }
1245
1246                                 /* ?????????????????????????????????????????????????????????? */
1247                                 /* Mark Def as use, too. Since param initialisation is in     */
1248                                 /* var_def and this would not remove this locals, if not used */
1249                                 /* elsewhere   */
1250                                 /* ?????????????????????????????????????????????????????????? */
1251
1252         }
1253
1254         /* change outstack Interface stackslots */
1255         out = ls->basicblocks[n]->outvars;
1256         out_d = ls->basicblocks[n]->outdepth - 1;
1257
1258         for (;out_d >= 0; out_d--) {
1259                 /* Possible Use of ls->new_varindex[jd->var[out_d]] */
1260                 _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
1261
1262                 a = ls->new_varindex[out[out_d]];
1263                 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1264
1265                 /* i <- top(stack[a]) */
1266
1267                 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1268                 i = ls->stack[a][ls->stack_top[a]-1];
1269                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1270
1271                 /* Replace use of x with xi */
1272
1273 #ifdef SSA_DEBUG_VERBOSE
1274                         ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
1275 #endif
1276                 out[out_d] = ls->var_0[a] + i;
1277                 lt = ls->lifetime + out[out_d];
1278
1279                 lt->v_index = out[out_d];
1280                 lt->bb_last_use = -1;
1281         }
1282
1283         /* change use in phi Functions of Successors */
1284
1285         Y = graph_get_first_successor(gd, n, &iter_succ);
1286         for(; Y != -1; Y = graph_get_next(&iter_succ)) {
1287                 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
1288                 k = graph_get_first_predecessor(gd, Y, &iter_pred);
1289                 for (j = 0; (k != -1) && (k != n); j++)
1290                         k = graph_get_next(&iter_pred);
1291                 _SSA_ASSERT(k == n);
1292
1293                 /* n is jth Predecessor of Y */
1294
1295                 for(a = 0; a < ls->ssavarcount; a++)
1296                         if (ls->phi[Y][a] != NULL) {
1297
1298                                 /* i <- top(stack[a]) */
1299
1300                                 if (ls->stack_top[a] == 1) {
1301                                         /* no definition till now in controll flow */
1302 #ifdef SSA_DEBUG_VERBOSE
1303                                         if (compileverbose) {
1304                                                 printf("Succ %3i Arg %3i \n", Y, j);
1305                                                 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
1306                                         }
1307 #endif
1308                                         ls->phi[Y][a][j+1] = UNUSED;
1309                                 }
1310                                 else {
1311                                         _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1312                                         i = ls->stack[a][ls->stack_top[a]-1];
1313                                         _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1314
1315                                         /* change jth operand from a0 to ai */
1316
1317                                         i = ls->var_0[a] + i;
1318 #ifdef SSA_DEBUG_VERBOSE
1319                                         if (compileverbose) {
1320                                                 printf("Succ %3i Arg %3i \n", Y, j);
1321                                                 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
1322                                         }
1323 #endif
1324                                         ls->phi[Y][a][j+1] = i;
1325                                         _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
1326                                                                           ls->varcount_with_indices);
1327
1328                                         /* use by phi function has to be remembered, too */
1329
1330                                         ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
1331                                 }
1332
1333                                 /* ????????????????????????????????????????????? */
1334                                 /* why was this only for local vars before ?     */
1335                                 /* ????????????????????????????????????????????? */
1336
1337                         }
1338         }
1339
1340         /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
1341         for(i = 0; i < ls->basicblockcount; i++)
1342                 if (dd->idom[i] == n)
1343                         ssa_rename_(jd, gd, dd, i);
1344
1345         /* pop Stack[a] for each definition of a var a in the original S */
1346         for(a = 0; a < ls->ssavarcount; a++) {
1347                 ls->stack_top[a] -= def_count[a];
1348                 _SSA_ASSERT(ls->stack_top[a] >= 0);
1349         }
1350 }
1351
1352
1353
1354 #ifdef SSA_DEBUG_VERBOSE
1355 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
1356         int i,j;
1357         lsradata *ls;
1358
1359         ls = jd->ls;
1360
1361         printf("ssa_printtrees: maxlocals %3i", jd->localcount);
1362
1363         printf("Dominator Tree: \n");
1364         for(i = 0; i < ls->basicblockcount; i++) {
1365                 printf("%3i:",i);
1366                 for(j = 0; j < ls->basicblockcount; j++) {
1367                         if (dd->idom[j] == i) {
1368                                 printf(" %3i", j);
1369                         }
1370                 }
1371                 printf("\n");
1372         }
1373
1374         printf("Dominator Forest:\n");
1375         for(i = 0; i < ls->basicblockcount; i++) {
1376                 printf("%3i:",i);
1377                 for(j = 0; j < dd->num_DF[i]; j++) {
1378                                 printf(" %3i", dd->DF[i][j]);
1379                 }
1380                 printf("\n");
1381         }
1382 #if 0
1383         if (ls->ssavarcount > 0) {
1384         printf("Use Sites\n");
1385         for(i = 0; i < ls->ssavarcount; i++) {
1386                 printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]);
1387                 for(j = 0; j < ls->basicblockcount; j++) {
1388                         if ((j % 5) == 0) printf(" ");
1389                         if (bv_get_bit(ls->use_sites[i], j))
1390                                 printf("1");
1391                         else
1392                                 printf("0");
1393                 }
1394                 printf("\n");
1395         }
1396         }
1397 #endif
1398         printf("var Definitions:\n");
1399         for(i = 0; i < jd->basicblockcount; i++) {
1400                 printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]);
1401                 for(j = 0; j < ls->ssavarcount; j++) {
1402                         if ((j % 5) == 0) printf(" ");
1403                         if (bv_get_bit(ls->var_def[i], j))
1404                                 printf("1");
1405                         else
1406                                 printf("0");
1407                 }
1408                 printf(" (");
1409                 for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
1410                         j++)
1411                         printf("%8x",ls->var_def[i][j]);
1412                 printf(")\n");
1413         }
1414 }
1415
1416 void ssa_print_phi(lsradata *ls, graphdata *gd) {
1417         int i,j,k;
1418
1419         printf("phi Functions (varcount_with_indices: %3i):\n",
1420                    ls->varcount_with_indices);
1421         for(i = 0; i < ls->basicblockcount; i++) {
1422                 for(j = 0; j < ls->ssavarcount; j++) {
1423                         if (ls->phi[i][j] != NULL) {
1424                                 printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
1425                                 for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
1426                                         printf("%3i ",ls->phi[i][j][k]);
1427                                 printf(")\n");
1428                         }
1429                 }
1430         }
1431
1432 }
1433
1434 #endif
1435
1436 void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
1437         int a, i, j, pred;
1438         graphiterator iter;
1439         lsradata *ls;
1440
1441         ls = jd->ls;
1442
1443         /* count moves to be inserted at the end of each block in moves[] */
1444         ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
1445         for(i = 0; i < ls->basicblockcount; i++)
1446                 ls->num_phi_moves[i] = 0;
1447         for(i = 0; i < ls->basicblockcount; i++)
1448                 for(a = 0; a < ls->ssavarcount; a++)
1449                         if (ls->phi[i][a] != NULL) {
1450 #if 0
1451                                 if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
1452                                         /* Var defined (only <- SSA Form!) in this phi function */
1453                                         /* and not used anywhere -> delete phi function and set */
1454                                         /* var to unused */
1455
1456                                         /* TODO: first delete use sites of arguments of phi */
1457                                         /* function */
1458                                         VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
1459                                         ls->lifetime[ls->phi[i][a][0]].def = NULL;
1460                                         ls->phi[i][a] = NULL;
1461                                 }
1462                                 else
1463 #endif
1464                                         {
1465                                         pred = graph_get_first_predecessor(gd, i, &iter);
1466                                         for(; pred != -1; pred = graph_get_next(&iter)) {
1467                                                 ls->num_phi_moves[pred]++;
1468                                         }
1469                                 }
1470                         }
1471
1472         /* allocate ls->phi_moves */
1473         ls->phi_moves = DMNEW( int **, ls->basicblockcount);
1474         for(i = 0; i < ls->basicblockcount; i++) {
1475                 ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
1476                 for(j = 0; j <ls->num_phi_moves[i]; j++)
1477                         ls->phi_moves[i][j] = DMNEW(int, 2);
1478 #ifdef SSA_DEBUG_VERBOSE
1479                 if (compileverbose)
1480                         printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
1481                                    i, ls->num_phi_moves[i]);
1482 #endif
1483         }
1484
1485         /* populate ls->phi_moves */
1486         for(i = 0; i < ls->basicblockcount; i++)
1487                 ls->num_phi_moves[i] = 0;
1488         for(i = 0; i < ls->basicblockcount; i++)
1489                 for(a = 0; a < ls->ssavarcount; a++)
1490                         if (ls->phi[i][a] != NULL) {
1491                                 pred = graph_get_first_predecessor(gd, i, &iter);
1492                                 for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
1493                                         /* target is phi[i][a][0] */
1494                                         /* source is phi[i][a][j+1] */
1495                                         if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
1496                                                 /* valid move */
1497                                                 if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
1498                                                         ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
1499                                                                 ls->phi[i][a][0];
1500                                                         ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
1501                                                                 ls->phi[i][a][j+1];
1502                                                 }
1503                                         }
1504                                 }
1505                         }
1506 }
1507
1508 /****************************************************************************
1509 Optimizations
1510 ****************************************************************************/
1511
1512
1513 /****************************************************************************
1514 Dead Code Elimination
1515 ****************************************************************************/
1516 void dead_code_elimination(jitdata *jd, graphdata *gd) {
1517         int a, i, source;
1518         worklist *W;
1519
1520         instruction *iptr;
1521         struct lifetime *lt, *s_lt;
1522
1523         bool remove_statement;
1524         struct site *use;
1525
1526         lsradata *ls;
1527 #ifdef SSA_DEBUG_VERBOSE
1528         methodinfo *m;
1529
1530         m  = jd->m;
1531 #endif
1532         ls = jd->ls;
1533
1534         W = wl_new(ls->lifetimecount);
1535         if (ls->lifetimecount > 0) {
1536                 /* put all lifetimes on Worklist */
1537                 for(a = 0; a < ls->lifetimecount; a++) {
1538                         if (ls->lifetime[a].type != -1) {
1539                                 wl_add(W, a);
1540                         }
1541                 }
1542         }
1543
1544         /* Remove unused lifetimes */
1545         while(!wl_is_empty(W)) {
1546                 /* take a var out of Worklist */
1547                 a = wl_get(W);
1548
1549                 lt = &(ls->lifetime[a]);
1550                 if ((lt->def == NULL) || (lt->type == -1))
1551                         /* lifetime was already removed -> no defs anymore */
1552                         continue;
1553
1554                 /* Remove lifetimes, which are only used in a phi function, which
1555                    defines them! */
1556                 remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
1557                 for(use = lt->use; (remove_statement && (use != NULL));
1558                         use = use->next)
1559                 {
1560                         remove_statement = remove_statement &&
1561                                 (use->b_index == lt->def->b_index) &&
1562                                 (use->iindex == lt->def->iindex);
1563                 }
1564                 if (remove_statement) {
1565 #ifdef SSA_DEBUG_CHECK
1566                         /* def == use can only happen in phi functions */
1567                         if (remove_statement)
1568                                 _SSA_ASSERT(lt->use->iindex < 0);
1569 #endif
1570                         /* give it free for removal */
1571                         lt->use = NULL;
1572                 }
1573
1574                 if (lt->use == NULL) {
1575                         /* Look at statement of definition of a and remove it,           */
1576                         /* if the Statement has no sideeffects other than the assignemnt */
1577                         /* of a */
1578                         if (lt->def->iindex < 0 ) {
1579                                 /* phi function */
1580                                 /* delete use of sources , delete phi functions  */
1581
1582                                 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] !=
1583                                                         NULL);
1584
1585                                 for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
1586                                          i++)
1587                                         {
1588                                                 source =
1589                                                         ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1590                                                 if ((source != ls->varcount_with_indices) &&
1591                                                         (source != lt->v_index)) {
1592
1593                                                         /* phi Argument was not already removed (already in
1594                                                            because of selfdefinition) */
1595
1596                                                         s_lt = &(ls->lifetime[source]);
1597
1598                                                         /* remove it */
1599
1600                                                         lt_remove_use_site(s_lt,lt->def->b_index,
1601                                                                                         lt->def->iindex);
1602
1603                                                         /*  put it on the Worklist */
1604
1605                                                         wl_add(W, source);
1606                                                 }
1607                                         }
1608                                 /* now delete phi function itself */
1609                                 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1610                         } else {
1611                                 /* "normal" Use by ICMD */
1612                                 remove_statement = false;
1613                                 if (lt->def->b_index != 0) {
1614
1615                                         /* do not look at artificial block 0 (parameter init) */
1616
1617                                         iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1618                                                 lt->def->iindex;
1619
1620                                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
1621                                                 remove_statement = false;
1622
1623                                         /* if ICMD could throw an exception do not remove it! */
1624
1625                                         else {
1626
1627                                                 /* ICMD_INVOKE*, ICMD_BUILTIN and ICMD_MULTIANEWARRAY */
1628                                                 /* have possible sideeffects -> do not remove them    */
1629
1630 /*                                              remove_statement = !(ICMD_HAS_SPECIAL(iptr->opc)); */
1631
1632                                                 remove_statement = !(
1633                                                         (icmd_table[iptr->opc].dataflow == DF_INVOKE) ||
1634                                                         (icmd_table[iptr->opc].dataflow == DF_BUILTIN) ||
1635                                                         (icmd_table[iptr->opc].dataflow == DF_N_TO_1));
1636
1637                                                 if (remove_statement) {
1638                                                         switch (icmd_table[iptr->opc].dataflow) {
1639                                                         case DF_3_TO_0:
1640                                                         case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1641                                                                 a = iptr->sx.s23.s3.varindex;
1642                                                                 s_lt = ls->lifetime + a;
1643                                                                 lt_remove_use_site(s_lt, lt->def->b_index,
1644                                                                                                    lt->def->iindex);
1645                                                                 wl_add(W, a);
1646
1647                                                                 /* now "fall through" for handling of s2 and s1 */
1648
1649                                                         case DF_2_TO_0:
1650                                                         case DF_2_TO_1: /* icmd has s1 and s2 */
1651                                                                 a = iptr->sx.s23.s2.varindex;
1652                                                                 s_lt = ls->lifetime + a;
1653                                                                 lt_remove_use_site(s_lt, lt->def->b_index,
1654                                                                                                    lt->def->iindex);
1655                                                                 wl_add(W, a);
1656
1657                                                                 /* now "fall through" for handling of s1 */
1658
1659                                                         case DF_1_TO_0:
1660                                                         case DF_1_TO_1:
1661                                                         case DF_MOVE:
1662                                                         case DF_COPY:
1663                                                                 a = iptr->s1.varindex;
1664                                                                 s_lt = ls->lifetime + a;
1665                                                                 lt_remove_use_site(s_lt, lt->def->b_index,
1666                                                                                                    lt->def->iindex);
1667                                                                 wl_add(W, a);
1668                                                         }
1669                                                 }
1670                                         }
1671
1672                                         if (remove_statement) {
1673
1674                                                 /* remove statement */
1675
1676 #ifdef SSA_DEBUG_VERBOSE
1677                                                 if (compileverbose)
1678                                                         printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
1679                                                                    m->class->name->text, m->name->text,
1680                                                                    lt->def->b_index, lt->def->iindex,
1681                                                                    icmd_table[iptr->opc].name);
1682 #endif
1683                                                 iptr->opc = ICMD_NOP;
1684                                         }
1685                                 } /* (lt->def->b_index != 0) */
1686                         } /* if (lt->def->iindex < 0 ) else */
1687
1688                         /* remove definition of a */
1689
1690                         VAR(lt->v_index)->type = -1;
1691                         lt->type = -1;
1692                         lt->def = NULL;
1693                 } /* if (lt->use == NULL) */
1694         } /* while(!wl_is_empty(W)) */
1695 } /* dead_code_elimination */
1696
1697 /****************************************************************************
1698 Simple Constant Propagation
1699 ****************************************************************************/
1700
1701 void simple_constant_propagation() {
1702 }
1703
1704 /****************************************************************************
1705 Optimization
1706 *******************************************************************************/
1707 void copy_propagation(jitdata *jd, graphdata *gd) {
1708         int a, i, source;
1709         int only_source;
1710
1711         worklist *W;
1712
1713         instruction *iptr;
1714         struct lifetime *lt, *s_lt;
1715         s4 *in;
1716
1717         lsradata *ls;
1718
1719         ls = jd->ls;
1720
1721         W = wl_new(ls->lifetimecount);
1722         if (ls->lifetimecount > 0) {
1723                 /* put all lifetimes on Worklist */
1724                 for(a = 0; a < ls->lifetimecount; a++) {
1725                         if (ls->lifetime[a].type != -1) {
1726                                 wl_add(W, a);
1727                         }
1728                 }
1729         }
1730
1731         while(!wl_is_empty(W)) {
1732                 /* take a var out of Worklist */
1733                 a = wl_get(W);
1734
1735                 lt = ls->lifetime + a;
1736                 if (lt->type == -1)
1737                         continue;
1738                 _SSA_ASSERT(lt->def != NULL);
1739                 _SSA_ASSERT(lt->use != NULL);
1740                 if (lt->def->iindex < 0 ) {
1741
1742                         /* phi function */
1743                         /* look, if phi function degenerated to a x = phi(y) */
1744                         /* and if so, substitute y for every use of x */
1745
1746                         _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL);
1747
1748                         only_source = ls->varcount_with_indices;
1749                         for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
1750                                  i++) {
1751                                         source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1752                                         if (source != ls->varcount_with_indices) {
1753                                                 if (only_source == ls->varcount_with_indices) {
1754                                                         /* first valid source argument of phi function */
1755                                                         only_source = source;
1756                                                 } else {
1757                                                         /* second valid source argument of phi function */
1758                                                         /* exit for loop */
1759                                                         only_source = ls->varcount_with_indices;
1760                                                         break;
1761                                                 }
1762                                         }
1763                         }
1764                         if (only_source != ls->varcount_with_indices) {
1765
1766                                 /* replace all use sites of lt with the var_index only_source */
1767
1768                                 ssa_replace_use_sites( jd, gd, lt, only_source, W);
1769
1770                                 /* delete def of lt and replace uses of lt with "only_source" */
1771
1772                                 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1773
1774                                 s_lt = ls->lifetime + only_source;
1775
1776                                 VAR(lt->v_index)->type = -1;
1777                                 lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
1778                                 lt->def = NULL;
1779                                 /* move use sites from lt to s_lt */
1780                                 lt_move_use_sites(lt, s_lt);
1781                                 lt->type = -1;
1782                         } /* if (only_source != ls->varcount_with_indices) */
1783                 } else { /* if (lt->def->iindex < 0 )*/
1784                         /* def in "normal" ICMD */
1785 #if 0
1786                         iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1787                                 lt->def->iindex;
1788
1789                         if ( localvar ) {
1790                                 if (lt->def->b_index == 0)
1791                                         continue;
1792
1793                                 switch(iptr->opc) {
1794                                 case ICMD_ISTORE:
1795                                 case ICMD_LSTORE:
1796                                 case ICMD_FSTORE:
1797                                 case ICMD_DSTORE:
1798                         case ICMD_ASTORE:
1799                                         if (lt->def->iindex == 0) {
1800                                                 /* first instruction in bb -> instack==bb->instack */
1801                                                 in = ls->basicblocks[lt->def->b_index]->instack;
1802                                         } else {
1803                                                 /* instack is (iptr-1)->dst */
1804                                                 in = (iptr-1)->dst;
1805                                         }
1806
1807                                         if (in->varkind != LOCALVAR) {
1808 #ifdef SSA_DEBUG_VERBOSE
1809                                                 if (compileverbose)
1810                                                         printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
1811 #endif
1812                                                 s_lt = &(ls->lifetime[-in->varnum-1]);
1813
1814                                                 for (ss = s_lt->local_ss; ss != NULL; ss = ss->next) {
1815                                                         ss->s->varkind = LOCALVAR;
1816                                                         ss->s->varnum = iptr->op1;
1817                                                 }
1818
1819                                                 /* replace all use sites of s_lt with the var_index */
1820                                                 /* iptr->op1 */
1821
1822                                                 ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
1823
1824                                                 /* s_lt->def is the new def site of lt */
1825                                                 /* the old ->def site will get a use site of def */
1826                                                 /* only one def site */
1827                                                 _SSA_ASSERT(lt->def->next == NULL);
1828                                                 _SSA_ASSERT(s_lt->def != NULL);
1829                                                 _SSA_ASSERT(s_lt->def->next == NULL);
1830
1831                                                 /* replace def of s_lt with iptr->op1 */
1832                                                 if (s_lt->def->iindex < 0) {
1833                                                         /* phi function */
1834                                                         _SSA_ASSERT(ls->phi[s_lt->def->b_index]
1835                                                                                [-s_lt->def->iindex-1]
1836                                                                         != NULL);
1837                                                         ls->phi[s_lt->def->b_index][-s_lt->def->iindex-1][0]
1838                                                                 = iptr->op1;
1839                                                 } else
1840                                                         if (in->varnum != iptr->op1)
1841                                                                 printf("copy propagation: LOCALVAR ss->ISTORE BB %i II %i\n",
1842                                                                            lt->def->b_index, lt->def->iindex);
1843
1844
1845                                                 /* move def to use sites of lt */
1846                                                 lt->def->next = lt->use;
1847                                                 lt->use = lt->def;
1848
1849                                                 lt->def = s_lt->def;
1850
1851                                                 s_lt->def = NULL;
1852
1853
1854                                                 /* move use sites from s_lt to lt */
1855                                                 move_use_sites(s_lt, lt);
1856                                                 move_stackslots(s_lt, lt);
1857                                                 s_lt->type = -1;
1858                                         }
1859                                         break;
1860                                 }
1861                         } else {
1862                                 /* Def Interface Stackslot */
1863
1864                                 switch(iptr->opc) {
1865                                 case ICMD_ILOAD:
1866                                 case ICMD_LLOAD:
1867                                 case ICMD_FLOAD:
1868                                 case ICMD_DLOAD:
1869                                 case ICMD_ALOAD:
1870                                         only_source = lt->local_ss->s->varnum;
1871                                         if (lt->local_ss->s->varkind != LOCALVAR) {
1872 #ifdef SSA_DEBUG_VERBOSE
1873                                                 if (compileverbose)
1874                                                         printf("copy propagation xload: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, lt->local_ss->s->varnum);
1875 #endif
1876                                                 _SSA_ASSERT(iptr->dst->varnum == lt->local_ss->s->varnum);
1877                                                 for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
1878                                                         ss->s->varkind = LOCALVAR;
1879                                                         ss->s->varnum = iptr->op1;
1880                                                 }
1881
1882                                                 /* replace all use sites of lt with the var_index iptr->op1*/
1883
1884                                                 ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
1885
1886                                                 lt->def = NULL;
1887
1888                                                 s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
1889
1890                                                 /* move use sites from lt to s_lt */
1891                                                 move_use_sites(lt, s_lt);
1892                                                 move_stackslots(lt, s_lt);
1893                                                 lt->type = -1;
1894                                         } else
1895                                                 if (lt->local_ss->s->varnum != iptr->op1)
1896                                                         printf("copy propagation: ILOAD -> LOCALVAR ss BB %i II %i\n",
1897                                                                    lt->def->b_index, lt->def->iindex);
1898
1899                                         break;
1900                                 }
1901                         } /* localvar or interface stackslot */
1902 #endif
1903                 } /* i(lt->def->iindex < 0 ) */
1904
1905         } /* while(!wl_is_empty(W)) */
1906 }
1907
1908 void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt,
1909                                                    int new_v_index, worklist *W) {
1910         struct site *s;
1911         int i, source;
1912         instruction *iptr;
1913         s4 *argp;
1914
1915         methoddesc *md;
1916         builtintable_entry *bte;
1917         lsradata *ls;
1918
1919         ls = jd->ls;
1920         md = jd->m->parseddesc;
1921
1922
1923         for(s = lt->use; s != NULL; s = s->next) {
1924                 if (s->iindex < 0) {
1925
1926                         /* Use in phi function */
1927
1928                         for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
1929                                 source = ls->phi[s->b_index][-s->iindex-1][i];
1930                                 if (source == lt->v_index) {
1931 #ifdef SSA_DEBUG_VERBOSE
1932                                         if (W != NULL) {
1933                                                 if (compileverbose)
1934                                                         printf("copy propagation phi: BB %3i I %3i: %3i -> \
1935                                      %3i\n", s->b_index, s->iindex,
1936                                                                    new_v_index, source);
1937                                         }
1938 #endif
1939                                         ls->phi[s->b_index][-s->iindex-1][i]
1940                                                 = new_v_index;
1941                                 }
1942                         }
1943                         if (W != NULL) {
1944
1945                                 /* Add var, which is defined by this phi function to */
1946                                 /* the worklist */
1947
1948                                 source = ls->phi[s->b_index][-s->iindex-1][0];
1949                                 wl_add(W, source);
1950                         }
1951                 }
1952                 else { /* use in ICMD */
1953
1954                         iptr = ls->basicblocks[s->b_index]->iinstr +
1955                                 s->iindex;
1956
1957                 /* check for use (s1, s2, s3 or special (argp) ) */
1958
1959                         i = UNUSED;
1960                         switch (icmd_table[iptr->opc].dataflow) {
1961                         case DF_3_TO_0:
1962                         case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1963                                 if (iptr->sx.s23.s3.varindex == lt->v_index) {
1964 #ifdef SSA_DEBUG_VERBOSE
1965                                         if (W != NULL) {
1966                                                 if (compileverbose)
1967                                                         printf("copy propagation loc: BB %3i I %3i: %3i -> \
1968                                     %3i\n", s->b_index, s->iindex,
1969                                                                    new_v_index, iptr->sx.s23.s3.varindex);
1970                                         }
1971 #endif
1972                                         iptr->sx.s23.s3.varindex = new_v_index;
1973                                 }
1974
1975                                 /* now "fall through" for handling of s2 and s1 */
1976
1977                         case DF_2_TO_0:
1978                         case DF_2_TO_1: /* icmd has s1 and s2 */
1979                                 if (iptr->sx.s23.s2.varindex == lt->v_index) {
1980 #ifdef SSA_DEBUG_VERBOSE
1981                                         if (W != NULL) {
1982                                                 if (compileverbose)
1983                                                         printf("copy propagation loc: BB %3i I %3i: %3i -> \
1984                                     %3i\n", s->b_index, s->iindex,
1985                                                                    new_v_index, iptr->sx.s23.s2.varindex);
1986                                         }
1987 #endif
1988                                         iptr->sx.s23.s2.varindex = new_v_index;
1989                                 }
1990
1991                                 /* now "fall through" for handling of s1 */
1992
1993                         case DF_1_TO_0:
1994                         case DF_1_TO_1:
1995                         case DF_MOVE:
1996                         case DF_COPY:
1997                                 if (iptr->s1.varindex == lt->v_index) {
1998 #ifdef SSA_DEBUG_VERBOSE
1999                                         if (W != NULL) {
2000                                                 if (compileverbose)
2001                                                         printf("copy propagation loc: BB %3i I %3i: %3i -> \
2002                                     %3i\n", s->b_index, s->iindex,
2003                                                                    new_v_index, iptr->s1.varindex);
2004                                         }
2005 #endif
2006                                         iptr->s1.varindex = new_v_index;
2007                                 }
2008                                 break;
2009
2010                                 /* TODO: */
2011                                 /* ? really look at md->paramcount or iptr->s1.argcount */
2012                                 /* has to be taken, so that pass-through stackslots get */
2013                                 /* renamed, too? */
2014
2015                         case DF_INVOKE:
2016                                 INSTRUCTION_GET_METHODDESC(iptr,md);
2017                                 i = md->paramcount;
2018                                 break;
2019                         case DF_BUILTIN:
2020                                 bte = iptr->sx.s23.s3.bte;
2021                                 md = bte->md;
2022                                 i = md->paramcount;
2023                                 break;
2024                         case DF_N_TO_1:
2025                                 i = iptr->s1.argcount;
2026                                 break;
2027                         }
2028                         if (i != UNUSED) {
2029                                 argp = iptr->sx.s23.s2.args;
2030                                 while (--i >= 0) {
2031                                         if (*argp == lt->v_index) {
2032 #ifdef SSA_DEBUG_VERBOSE
2033                                                 if (W != NULL) {
2034                                                         if (compileverbose)
2035                                                                 printf(
2036                                                                            "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
2037                                                                            , s->b_index, s->iindex, new_v_index, *argp);
2038                                                 }
2039 #endif
2040                                                 *argp = new_v_index;
2041
2042                                         }
2043                                         argp++;
2044                                 }
2045                         }
2046
2047                 } /* if (s->iindex < 0) */
2048         } /* for(s = lt->use; s != NULL; s = s->next) */
2049 }
2050
2051 #ifdef SSA_DEBUG_VERBOSE
2052 void ssa_print_lt(lsradata *ls) {
2053         int i;
2054         struct lifetime *lt;
2055         struct site *use;
2056
2057         printf("SSA LT Def/Use\n");
2058         for(i = 0; i < ls->lifetimecount; i++) {
2059                 lt = ls->lifetime + i;
2060                 if (lt->type != UNUSED) {
2061                         printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
2062                         if (lt->def != NULL)
2063                                 printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
2064                         else
2065                                 printf("%3i,%3i Use: ",0,0);
2066                         for(use = lt->use; use != NULL; use = use->next)
2067                                 printf("%3i,%3i ",use->b_index, use->iindex);
2068                         printf("\n");
2069                 }
2070         }
2071 }
2072
2073 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage)
2074 {
2075         char type;
2076         char kind;
2077
2078         switch (v->type) {
2079                 case TYPE_INT: type = 'i'; break;
2080                 case TYPE_LNG: type = 'l'; break;
2081                 case TYPE_FLT: type = 'f'; break;
2082                 case TYPE_DBL: type = 'd'; break;
2083                 case TYPE_ADR: type = 'a'; break;
2084                 case TYPE_RET: type = 'r'; break;
2085                 default:       type = '?';
2086         }
2087
2088         if (index < jd->localcount) {
2089                 kind = 'L';
2090                 if (v->flags & (PREALLOC | INOUT))
2091                                 printf("<INVALID FLAGS!>");
2092         }
2093         else {
2094                 if (v->flags & PREALLOC) {
2095                         kind = 'A';
2096                         if (v->flags & INOUT)
2097                                 printf("<INVALID FLAGS!>");
2098                 }
2099                 else if (v->flags & INOUT)
2100                         kind = 'I';
2101                 else
2102                         kind = 'T';
2103         }
2104
2105         printf("%c%c%3d", kind, type, index);
2106
2107         if (v->flags & SAVEDVAR)
2108                 putchar('!');
2109
2110         putchar(' ');
2111         fflush(stdout);
2112 }
2113 #endif
2114
2115 /****************************************************************************
2116 Optimization
2117 ****************************************************************************/
2118
2119 /*
2120  * These are local overrides for various environment variables in Emacs.
2121  * Please do not remove this and leave it at the end of the file, where
2122  * Emacs will automagically detect them.
2123  * ---------------------------------------------------------------------
2124  * Local variables:
2125  * mode: c
2126  * indent-tabs-mode: t
2127  * c-basic-offset: 4
2128  * tab-width: 4
2129  * End:
2130  */