src/vm/jit/optimizing/ssa_rename.c

   1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
   2
   3    Copyright (C) 2005, 2006, 2007, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  21    02111-1307, USA.
  22
  23 */
  24
  25
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30
  31 #include "mm/memory.h"
  32
  33 #include "toolbox/bitvector.h"
  34 #include "toolbox/worklist.h"
  35
  36 #include "vm/jit/builtin.hpp"
  37
  38 #include "vm/jit/jit.hpp" /* icmd_table */
  39
  40 #include "vm/jit/optimizing/dominators.hpp"
  41 #include "vm/jit/optimizing/graph.h"
  42 #include "vm/jit/optimizing/lifetimes.h"
  43 #include "vm/jit/optimizing/lsra.h"
  44 #include "vm/jit/optimizing/ssa.h"
  45 #include "vm/jit/optimizing/ssa_rename.h"
  46
  47 #if defined(SSA_DEBUG_VERBOSE)
  48 #include "vm/options.h"   /* compileverbose */
  49 #endif
  50
  51 /* function prototypes */
  52 void ssa_rename_(jitdata *jd,  graphdata *gd, dominatordata *dd, int n);
  53 int ssa_rename_def_(lsradata *ls, int a);
  54
  55 /* ssa_rename ******************************************************************
  56
  57 Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
  58 has only one definition (SSA form).
  59
  60 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
  61 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
  62                               definition of each old var.
  63 ls->varcount_with_indices     will be se to the new maximum varcount of LOCAL
  64                               and IOVARS.
  65
  66 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
  67 ls->varcount_with_indices.
  68
  69 jd->var and jd->varcount will be set for this renamed vars.
  70
  71 *******************************************************************************/
  72
  73 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
  74 {
  75         int i, mi, l, j, p, t;
  76         int type, flags;
  77         methoddesc *md = jd->m->parseddesc;
  78
  79         varinfo *new_vars;
  80         lsradata *ls;
  81
  82         ls = jd->ls;
  83
  84         ssa_rename_init(jd, gd);
  85
  86         /* Consider definition of Local Vars initialized with Arguments */
  87         /* in Block 0 */
  88         /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
  89
  90         for (p = 0, l= 0; p < md->paramcount; p++) {
  91                 t = md->paramtypes[p].type;
  92                 mi = l * 5 + t;
  93                 i = jd->local_map[mi];
  94                 l++;
  95                 if (IS_2_WORD_TYPE(t))
  96                         l++;
  97                 if (i == UNUSED)
  98                         continue;
  99
 100                 /* !!!!! locals are now numbered as the parameters !!!!       */
 101                 /* !!!!! no additional increment for 2 word types !!!!!       */
 102                 /* this happens later on! here we still need the increment    */
 103                 /* index of var can be in the range from 0 up to not including*/
 104                 /* jd->varcount */
 105
 106
 107                 i = ls->new_varindex[i];
 108
 109                 /* ignore return value, since first definition gives 0 -> */
 110                 /* no rename necessary */
 111
 112                 j = ssa_rename_def_(ls, i);
 113                 _SSA_ASSERT(j == 0);
 114                 jd->local_map[mi] = i;
 115         }
 116         ssa_rename_(jd, gd, dd, 0);
 117
 118 #if 0
 119         /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens!   */
 120         /* if there is no use of the defined Var itself by the phi function   */
 121         /* for a loop path, in which this var is not used, it will not be life*/
 122         /* in this path and overwritten! */
 123
 124         /* Invalidate all xij from xi0=phi(xi1,xi2,xi3,..,xin) with xij == xi0*/
 125         /* this happens if the phi function is the first definition of x or in*/
 126         /* a path with a backedge xi has no definition */
 127         /* a phi(xij) = ...,xij,... with the only use and definition of xij by*/
 128         /* this phi function would otherwise "deadlock" the dead code         */
 129         /* elemination (invalidate means set it to UNUSED)                    */
 130         /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in*/
 131         /* [1,n] can be removed */
 132
 133         for(i = 0; i < ls->ssavarcount; i++) {
 134           for(t = 0; t < ls->basicblockcount; t++) {
 135             if (ls->phi[t][i] != 0) {
 136               remove_phi = true;
 137               for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
 138                 if (ls->phi[t][i][0] == ls->phi[t][i][p])
 139                   ls->phi[t][i][p] = UNUSED;
 140                 else
 141                   remove_phi = false;
 142               }
 143             }
 144             if (remove_phi)
 145               ls->phi[t][i] = NULL;
 146           }
 147         }
 148 #endif
 149
 150 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
 151 # if defined(SSA_DEBUG_VERBOSE)
 152         if (compileverbose) {
 153                 printf("%s %s ",jd->m->clazz->name->text, jd->m->name->text);
 154                 if (code_is_leafmethod(jd->code))
 155                         printf("**Leafmethod**");
 156                 printf("\n");
 157         }
 158 # endif
 159         if (strcmp(jd->m->clazz->name->text,"fp")==0)
 160                 if (strcmp(jd->m->name->text,"testfloat")==0)
 161 # if defined(SSA_DEBUG_VERBOSE)
 162                         if (compileverbose)
 163                                 printf("12-------------------12\n");
 164 # else
 165                 { int dummy=1; dummy++; }
 166 # endif
 167 #endif
 168
 169         /* recreate rd->locals[][] */
 170         /* now only one (local_index/type) pair exists anymore     */
 171         /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
 172         /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
 173
 174         new_vars = DMNEW(varinfo, ls->vartop);
 175         for(i = 0; i < ls->vartop ; i++)
 176                 new_vars[i].type = UNUSED;
 177         for(i = 0; i < jd->varcount; i++) {
 178                         p = ls->new_varindex[i];
 179                         if (p != UNUSED) {
 180                                 if (p < ls->ssavarcount)
 181                                         p = ls->var_0[p];
 182                                 new_vars[p].type  = VAR(i)->type;
 183                                 new_vars[p].flags = VAR(i)->flags;
 184                                 ls->lifetime[p].v_index = p;
 185                                 ls->lifetime[p].type = VAR(i)->type;
 186                         }
 187         }
 188
 189         /* take care of newly indexed local & in/out vars */
 190
 191         for(i = 0; i < ls->ssavarcount; i++) {
 192                 j = ls->var_0[i];
 193                 type = new_vars[j].type;
 194                 flags = new_vars[j].flags;
 195                 j++;
 196                 for (; j < ls->var_0[i + 1]; j++) {
 197                         new_vars[j].type = type;
 198                         new_vars[j].flags = flags;
 199                         ls->lifetime[j].v_index = j;
 200                         ls->lifetime[j].type = type;
 201                 }
 202         }
 203
 204 #ifdef SSA_DEBUG_VERBOSE
 205         if (compileverbose) {
 206
 207                 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 208                            ls->ssavarcount);
 209                 for(i = 0; i < jd->varcount; i++) {
 210                         printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 211                         ssa_show_variable(jd, i, VAR(i),0);
 212                         j = ls->new_varindex[i];
 213                         if ((j != UNUSED) && (j < ls->ssavarcount))
 214                                 printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
 215                         else
 216                                 printf(" -> %3i", j);
 217                         printf("\n");
 218                 }
 219         }
 220 #endif
 221
 222         jd->var = new_vars;
 223         jd->varcount = ls->vartop;
 224         jd->vartop = ls->vartop;
 225
 226 #ifdef SSA_DEBUG_VERBOSE
 227         if (compileverbose) {
 228                 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 229                            ls->ssavarcount);
 230                 for(i = 0; i < jd->varcount; i++) {
 231                         printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 232                         ssa_show_variable(jd, i, VAR(i),0);
 233                         printf("\n");
 234                 }
 235         }
 236 #endif
 237 }
 238
 239 /* ssa_rename_init *************************************************************
 240
 241 Setup the data structure for ssa_rename
 242
 243 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
 244 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
 245                               definition of each old var.
 246 ls->varcount_with_indices     will be se to the new maximum varcount of LOCAL
 247                               and IOVARS.
 248
 249 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
 250 ls->varcount_with_indices.
 251
 252 jd->var and jd->varcount will be set for this renamed vars.
 253
 254 *******************************************************************************/
 255
 256 void ssa_rename_init(jitdata *jd, graphdata *gd)
 257 {
 258         int a, i;
 259 #if 0
 260         int p;
 261 #endif
 262         lsradata *ls;
 263
 264         ls = jd->ls;
 265
 266         /* set up new locals */
 267         /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
 268         /* for locals and iovars */
 269
 270         /* ls->num_defs[index] gives the number of indizes which will be created  */
 271         /* from SSA */
 272
 273         /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
 274         /* ls->var_0[X] will point to each LX(0)  */
 275         /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
 276
 277         /* as first step cummulate the num_defs array for locals and iovars       */
 278         /* last element is the maximum var count */
 279
 280         ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
 281         ls->var_0[0] = 0;
 282         ls->varcount_with_indices = 0;
 283         for(i = 0; i < ls->ssavarcount; i++) {
 284                 ls->varcount_with_indices += ls->num_defs[i];
 285                 ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
 286         }
 287
 288 #if 0
 289         /* Change the var indices in phi from La to La(0) */
 290
 291         for(i = 0; i < ls->basicblockcount; i++)
 292                 for (a = 0; a < ls->ssavarcount; a++)
 293                         if (ls->phi[i][a] != NULL)
 294                                 for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
 295                                         ls->phi[i][a][p] = ls->var_0[a];
 296 #endif
 297
 298         /* Initialization */
 299
 300         ls->count     = DMNEW(int, max(1, ls->ssavarcount));
 301         ls->stack     = DMNEW(int *, max(1, ls->ssavarcount));
 302         ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
 303         for(a = 0; a < ls->ssavarcount; a++) {
 304                 ls->count[a] = 0;
 305                 ls->stack_top[a] = 0;
 306
 307                 /* stack a has to hold number of defs of a Elements + 1 */
 308
 309                 ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
 310                 ls->stack[a][ls->stack_top[a]++] = 0;
 311         }
 312
 313         if (ls->ssavarcount > 0) {
 314
 315                 /* Create the num_var_use Array */
 316
 317                 ls->num_var_use = DMNEW(int *, ls->basicblockcount);
 318                 for(i = 0; i < ls->basicblockcount; i++) {
 319                         ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
 320                         for(a = 0; a < ls->varcount_with_indices; a++)
 321                                 ls->num_var_use[i][a] = 0;
 322                 }
 323
 324                 /* Create the use_sites Array of Bitvectors*/
 325                 /* use max(1,..), to ensure that the array is created! */
 326
 327                 ls->use_sites =  DMNEW(bitvector, max(1, ls->varcount_with_indices));
 328                 for(a = 0; a < ls->varcount_with_indices; a++)
 329                         ls->use_sites[a] = bv_new(ls->basicblockcount);
 330         }
 331
 332         /* init lifetimes */
 333         /* count number of TEMPVARs */
 334
 335         ls->lifetimecount = 0;
 336         for(i = 0; i < jd->varcount; i++)
 337                 if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
 338                         ls->lifetimecount++;
 339
 340         ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
 341
 342         ls->lifetimecount = ls->varcount;
 343         ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
 344         ls->lt_used = DMNEW(int, ls->lifetimecount);
 345         ls->lt_int = DMNEW(int, ls->lifetimecount);
 346         ls->lt_int_count = 0;
 347         ls->lt_flt = DMNEW(int, ls->lifetimecount);
 348         ls->lt_flt_count = 0;
 349         ls->lt_mem = DMNEW(int, ls->lifetimecount);
 350         ls->lt_mem_count = 0;
 351         for (i=0; i < ls->lifetimecount; i++) {
 352                 ls->lifetime[i].type = UNUSED;
 353                 ls->lifetime[i].savedvar = 0;
 354                 ls->lifetime[i].flags = 0;
 355                 ls->lifetime[i].usagecount = 0;
 356                 ls->lifetime[i].bb_last_use = -1;
 357                 ls->lifetime[i].bb_first_def = -1;
 358                 ls->lifetime[i].use = NULL;
 359                 ls->lifetime[i].def = NULL;
 360                 ls->lifetime[i].last_use = NULL;
 361         }
 362
 363         /* for giving TEMP and PREALLOC vars a new unique index */
 364
 365         ls->vartop = ls->varcount_with_indices;
 366
 367 #ifdef SSA_DEBUG_VERBOSE
 368         if (compileverbose) {
 369                 printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
 370                            ls->ssavarcount);
 371                 for(i = 0; i < jd->varcount; i++) {
 372                         if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
 373                                 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
 374                                 ssa_show_variable(jd, i, VAR(i),0);
 375                                 if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
 376                                         printf(" -> %3i", ls->new_varindex[i]);
 377                                 }
 378                                 printf("\n");
 379                         }
 380                 }
 381                 ssa_print_phi(ls, gd);
 382         }
 383 #endif
 384 }
 385
 386 int ssa_rename_def_(lsradata *ls, int a) {
 387         int i;
 388
 389         _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
 390         ls->count[a]++;
 391         i = ls->count[a] - 1;
 392         /* push i on stack[a] */
 393         _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
 394         ls->stack[a][ls->stack_top[a]++] = i;
 395         return i;
 396 }
 397
 398 int ssa_rename_def(jitdata *jd, int *def_count, int a) {
 399         int i, a1, ret;
 400         lsradata *ls;
 401
 402         ls = jd->ls;
 403
 404         a1 = ls->new_varindex[a];
 405         _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
 406         if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
 407                 /* local or inoutvar -> normal ssa renaming */
 408                 _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
 409                 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
 410
 411                 def_count[a1]++;
 412                 i = ssa_rename_def_(ls, a1);
 413                 ret = ls->var_0[a1] + i;
 414         }
 415         else {
 416                 /* TEMP or PREALLOC var */
 417                 if (a1 == UNUSED) {
 418                         ls->new_varindex[a] = ls->vartop;
 419                         ret = ls->vartop;
 420                         ls->vartop++;
 421                         _SSA_ASSERT( ls->vartop < ls->varcount);
 422                 }
 423                 else
 424                         ret = a1;
 425         }
 426         return ret;
 427 }
 428
 429 void ssa_rename_use_(lsradata *ls, int n, int a) {
 430         _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
 431         if (ls->ssavarcount > 0) {
 432                 bv_set_bit(ls->use_sites[a], n);
 433                 ls->num_var_use[n][a]++;
 434         }
 435 }
 436
 437 int ssa_rename_use(lsradata *ls, int n, int a) {
 438         int a1, i;
 439         int ret;
 440
 441         a1 = ls->new_varindex[a];
 442         _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
 443         if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
 444                 /* local or inoutvar -> normal ssa renaming */
 445                 /* i <- top(stack[a]) */
 446
 447                 _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
 448                 i = ls->stack[a1][ls->stack_top[a1] - 1];
 449                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
 450
 451                 ret = ls->var_0[a1] + i;
 452         }
 453         else {
 454                 /* TEMP or PREALLOC var */
 455                 if (a1 == UNUSED) {
 456                         ls->new_varindex[a] = ls->vartop;
 457                         ret = ls->vartop;
 458                         ls->vartop++;
 459                         _SSA_ASSERT( ls->vartop < ls->varcount);
 460                 }
 461                 else
 462                         ret = a1;
 463         }
 464
 465         return ret;
 466 }
 467
 468 #ifdef SSA_DEBUG_VERBOSE
 469 void ssa_rename_print(instruction *iptr, char *op, int from,  int to) {
 470         if (compileverbose) {
 471                 printf("ssa_rename_: ");
 472                 if (iptr != NULL)
 473                         printf("%s ", bytecode[iptr->opc].mnemonic);
 474                 else
 475                         printf("       ");
 476
 477                 printf("%s: %3i->%3i\n", op, from, to);
 478         }
 479 }
 480 #endif
 481
 482 /* ssa_rename_ ****************************************************************
 483
 484 Algorithm is based on "modern compiler implementation in C" from andrew
 485 w. appel, edition 2004
 486
 487 page 443 Algorithm 19.7. Renaming Variables
 488
 489 *******************************************************************************/
 490
 491 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
 492         int a, i, j, k, iindex, Y, v;
 493         int in_d, out_d;
 494         int *def_count;
 495         /* [0..ls->varcount[ Number of Definitions of this var in this  */
 496         /* Basic Block. Used to remove the entries off the stack at the */
 497         /* end of the function */
 498         instruction *iptr;
 499         s4 *in, *out, *argp;
 500         graphiterator iter_succ, iter_pred;
 501         struct lifetime *lt;
 502
 503         methoddesc *md;
 504         methodinfo *m;
 505         builtintable_entry *bte;
 506         lsradata *ls;
 507
 508         ls = jd->ls;
 509         m  = jd->m;
 510
 511 #ifdef SSA_DEBUG_VERBOSE
 512         if (compileverbose)
 513                 printf("ssa_rename_: BB %i\n",n);
 514 #endif
 515
 516         _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
 517
 518         def_count = DMNEW(int, max(1, ls->ssavarcount));
 519         for(i = 0; i < ls->ssavarcount; i++)
 520                 def_count[i] = 0;
 521
 522         /* change Store of possible phi functions from a to ai*/
 523
 524         for(a = 0; a < ls->ssavarcount; a++)
 525                 if (ls->phi[n][a] != NULL) {
 526                         def_count[a]++;
 527
 528                         /* do not mark this store as use - maybe this phi function */
 529                         /* can be removed for unused Vars*/
 530
 531                         j = ls->var_0[a] + ssa_rename_def_(ls, a);
 532 #ifdef SSA_DEBUG_VERBOSE
 533                         ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
 534 #endif
 535                         ls->phi[n][a][0] = j;
 536                 }
 537
 538         in   = ls->basicblocks[n]->invars;
 539         in_d = ls->basicblocks[n]->indepth - 1;
 540
 541         /* change use of instack Interface stackslots except top SBR and EXH */
 542         /* stackslots */
 543
 544         if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
 545                 (ls->basicblocks[n]->type == BBTYPE_SBR)) {
 546                 in_d--;
 547         }
 548 /*      out   = ls->basicblocks[n]->outvars; */
 549 /*      out_d = ls->basicblocks[n]->outdepth - 1; */
 550
 551 /*      for(; out_d > in_d; out_d--); */
 552
 553         for (; in_d >= 0; in_d--) {
 554                 /* Possible Use of ls->new_varindex[jd->var[in_d]] */
 555                 _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
 556
 557                 a = ls->new_varindex[in[in_d]];
 558                 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
 559
 560                 /* i <- top(stack[a]) */
 561
 562                 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
 563                 i = ls->stack[a][ls->stack_top[a]-1];
 564                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
 565
 566                 /* Replace use of x with xi */
 567
 568 #ifdef SSA_DEBUG_VERBOSE
 569                         ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
 570 #endif
 571                 in[in_d] = ls->var_0[a] + i;
 572                 lt = ls->lifetime + in[in_d];
 573
 574                 lt->v_index = in[in_d];
 575                 lt->bb_last_use = -1;
 576         }
 577
 578         iptr = ls->basicblocks[n]->iinstr;
 579
 580         for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
 581
 582                 /* check for use (s1, s2, s3 or special (argp) ) */
 583
 584                 switch (icmd_table[iptr->opc].dataflow) {
 585                 case DF_3_TO_0:
 586                 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
 587                         j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
 588 #ifdef SSA_DEBUG_VERBOSE
 589                         ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
 590 #endif
 591                         iptr->sx.s23.s3.varindex = j;
 592
 593                         /* now "fall through" for handling of s2 and s1 */
 594
 595                 case DF_2_TO_0:
 596                 case DF_2_TO_1: /* icmd has s1 and s2 */
 597                         j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
 598 #ifdef SSA_DEBUG_VERBOSE
 599                         ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
 600 #endif
 601                         iptr->sx.s23.s2.varindex = j;
 602
 603                         /* now "fall through" for handling of s1 */
 604
 605                 case DF_1_TO_0:
 606                 case DF_1_TO_1:
 607                 case DF_MOVE:
 608                 case DF_COPY:
 609                         j = ssa_rename_use(ls, n, iptr->s1.varindex);
 610 #ifdef SSA_DEBUG_VERBOSE
 611                         ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
 612 #endif
 613                         iptr->s1.varindex = j;
 614                         break;
 615
 616                 case DF_INVOKE:
 617                 case DF_BUILTIN:
 618                 case DF_N_TO_1:
 619                         /* do not use md->paramcount, pass-through stackslots have */
 620                         /* to be renamed, too */
 621                         i = iptr->s1.argcount;
 622                         argp = iptr->sx.s23.s2.args;
 623                         while (--i >= 0) {
 624                                 j = ssa_rename_use(ls, n, *argp);
 625 #ifdef SSA_DEBUG_VERBOSE
 626                                 ssa_rename_print( iptr, "arg", *argp, j);
 627 #endif
 628                                 *argp = j;
 629                                 argp++;
 630                         }
 631                         break;
 632                 }
 633
 634
 635                 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
 636                 /* an optional dst - so they to be checked first */
 637
 638                 v = UNUSED;
 639                 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
 640                         INSTRUCTION_GET_METHODDESC(iptr,md);
 641                         if (md->returntype.type != TYPE_VOID)
 642                                 v = iptr->dst.varindex;
 643                 }
 644                 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
 645                         bte = iptr->sx.s23.s3.bte;
 646                         md = bte->md;
 647                         if (md->returntype.type != TYPE_VOID)
 648                                 v = iptr->dst.varindex;
 649                 }
 650                 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
 651                         v = iptr->dst.varindex;
 652                 }
 653
 654                 if (v != UNUSED) {
 655                         j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
 656 #ifdef SSA_DEBUG_VERBOSE
 657                         ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
 658 #endif
 659                         iptr->dst.varindex = j;
 660                 }
 661
 662                                 /* ?????????????????????????????????????????????????????????? */
 663                                 /* Mark Def as use, too. Since param initialisation is in     */
 664                                 /* var_def and this would not remove this locals, if not used */
 665                                 /* elsewhere   */
 666                                 /* ?????????????????????????????????????????????????????????? */
 667
 668         }
 669
 670         /* change outstack Interface stackslots */
 671         out = ls->basicblocks[n]->outvars;
 672         out_d = ls->basicblocks[n]->outdepth - 1;
 673
 674         for (;out_d >= 0; out_d--) {
 675                 /* Possible Use of ls->new_varindex[jd->var[out_d]] */
 676                 _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
 677
 678                 a = ls->new_varindex[out[out_d]];
 679                 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
 680
 681                 /* i <- top(stack[a]) */
 682
 683                 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
 684                 i = ls->stack[a][ls->stack_top[a]-1];
 685                 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
 686
 687                 /* Replace use of x with xi */
 688
 689 #ifdef SSA_DEBUG_VERBOSE
 690                         ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
 691 #endif
 692                 out[out_d] = ls->var_0[a] + i;
 693                 lt = ls->lifetime + out[out_d];
 694
 695                 lt->v_index = out[out_d];
 696                 lt->bb_last_use = -1;
 697         }
 698
 699         /* change use in phi Functions of Successors */
 700
 701         Y = graph_get_first_successor(gd, n, &iter_succ);
 702         for(; Y != -1; Y = graph_get_next(&iter_succ)) {
 703                 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
 704                 k = graph_get_first_predecessor(gd, Y, &iter_pred);
 705                 for (j = 0; (k != -1) && (k != n); j++)
 706                         k = graph_get_next(&iter_pred);
 707                 _SSA_ASSERT(k == n);
 708
 709                 /* n is jth Predecessor of Y */
 710
 711                 for(a = 0; a < ls->ssavarcount; a++)
 712                         if (ls->phi[Y][a] != NULL) {
 713
 714                                 /* i <- top(stack[a]) */
 715
 716                                 if (ls->stack_top[a] == 1) {
 717                                         /* no definition till now in controll flow */
 718 #ifdef SSA_DEBUG_VERBOSE
 719                                         if (compileverbose) {
 720                                                 printf("Succ %3i Arg %3i \n", Y, j);
 721                                                 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
 722                                         }
 723 #endif
 724                                         ls->phi[Y][a][j+1] = UNUSED;
 725                                 }
 726                                 else {
 727                                         _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
 728                                         i = ls->stack[a][ls->stack_top[a]-1];
 729                                         _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
 730
 731                                         /* change jth operand from a0 to ai */
 732
 733                                         i = ls->var_0[a] + i;
 734 #ifdef SSA_DEBUG_VERBOSE
 735                                         if (compileverbose) {
 736                                                 printf("Succ %3i Arg %3i \n", Y, j);
 737                                                 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
 738                                         }
 739 #endif
 740                                         ls->phi[Y][a][j+1] = i;
 741                                         _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
 742                                                                           ls->varcount_with_indices);
 743
 744                                         /* use by phi function has to be remembered, too */
 745
 746                                         ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
 747                                 }
 748
 749                                 /* ????????????????????????????????????????????? */
 750                                 /* why was this only for local vars before ?     */
 751                                 /* ????????????????????????????????????????????? */
 752
 753                         }
 754         }
 755
 756         /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
 757         for(i = 0; i < ls->basicblockcount; i++)
 758                 if (dd->idom[i] == n)
 759                         ssa_rename_(jd, gd, dd, i);
 760
 761         /* pop Stack[a] for each definition of a var a in the original S */
 762         for(a = 0; a < ls->ssavarcount; a++) {
 763                 ls->stack_top[a] -= def_count[a];
 764                 _SSA_ASSERT(ls->stack_top[a] >= 0);
 765         }
 766 }
 767
 768 /*
 769  * These are local overrides for various environment variables in Emacs.
 770  * Please do not remove this and leave it at the end of the file, where
 771  * Emacs will automagically detect them.
 772  * ---------------------------------------------------------------------
 773  * Local variables:
 774  * mode: c
 775  * indent-tabs-mode: t
 776  * c-basic-offset: 4
 777  * tab-width: 4
 778  * End:
 779  */