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