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