1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
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
8 This file is part of CACAO.
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.
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.
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
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Christian Ullrich
34 #include "mm/memory.h"
36 #include "toolbox/bitvector.h"
37 #include "toolbox/worklist.h"
39 #include "vm/builtin.h"
41 #include "vm/jit/jit.h" /* icmd_table */
43 #include "vm/jit/optimizing/dominators.h"
44 #include "vm/jit/optimizing/graph.h"
45 #include "vm/jit/optimizing/lifetimes.h"
46 #include "vm/jit/optimizing/lsra.h"
48 #include "vm/jit/optimizing/ssa.h"
50 #if defined(SSA_DEBUG_VERBOSE)
51 #include "vmcore/options.h" /* compileverbose */
54 /* function prototypes */
55 void ssa_set_local_def(lsradata *, int , int);
56 void ssa_set_interface(jitdata *, basicblock *, s4 *);
58 void dead_code_elimination(jitdata *jd, graphdata *gd);
59 void copy_propagation(jitdata *jd, graphdata *gd);
60 void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
62 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
63 void ssa_rename_init(jitdata *jd, graphdata *gd);
64 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
65 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
67 void ssa_set_def(lsradata *, int , int );
68 void ssa_set_local_def(lsradata *, int , int );
69 void ssa_set_iovar(lsradata *, s4 , int , s4 *);
70 void ssa_set_interface(jitdata *, basicblock *, s4 *);
72 void ssa_generate_phi_moves(jitdata *, graphdata *);
73 int ssa_rename_def_(lsradata *ls, int a);
75 #ifdef SSA_DEBUG_VERBOSE
76 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
77 void ssa_print_lt(lsradata *ls);
78 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
79 void ssa_print_phi(lsradata *, graphdata *);
82 /* ssa ************************************************************************
86 ******************************************************************************/
88 void ssa(jitdata *jd, graphdata *gd) {
89 struct dominatordata *dd;
94 dd = compute_Dominators(gd, ls->basicblockcount);
95 computeDF(gd, dd, ls->basicblockcount, 0);
97 ssa_place_phi_functions(jd, gd, dd);
98 ssa_rename(jd, gd, dd);
99 #ifdef SSA_DEBUG_VERBOSE
100 if (compileverbose) {
101 printf("Phi before Cleanup\n");
102 ssa_print_phi(ls, gd);
106 lt_scanlifetimes(jd, gd, dd);
107 #ifdef SSA_DEBUG_VERBOSE
108 if (compileverbose) {
112 /* dead_code_elimination(jd, gd); */
113 #ifdef SSA_DEBUG_VERBOSE
114 if (compileverbose) {
115 printf("Phi after dead code elemination\n");
116 ssa_print_phi(ls, gd);
120 /* copy_propagation(jd, gd); */
121 #ifdef SSA_DEBUG_VERBOSE
122 if (compileverbose) {
123 printf("Phi after copy propagation\n");
124 ssa_print_phi(ls, gd);
129 ssa_generate_phi_moves(jd, gd);
130 transform_BB(jd, gd);
133 #ifdef SSA_DEBUG_CHECK
135 int i, j, pred, in_d, out_d;
136 graphiterator iter_pred;
143 for(i = 0; i < ls->basicblockcount; i++) {
144 if (ls->basicblocks[i]->indepth != 0) {
145 pred = graph_get_first_predecessor(gd, i, &iter_pred);
146 for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
147 in_d = ls->basicblocks[i]->indepth - 1;
148 in = ls->basicblocks[i]->invars;
149 for (; in_d >= 0; in_d--) {
151 for (j = 0; (!phi_define) && (j<ls->ssavarcount); j++) {
152 if (ls->phi[i][j] != NULL)
153 if (ls->phi[i][j][0] == in[in_d])
157 /* in not defined in phi function -> check with */
158 /* outstack(s) of predecessor(s) */
159 out_d = ls->basicblocks[pred]->outdepth - 1;
160 out = ls->basicblocks[pred]->outvars;
161 _SSA_ASSERT(out_d >= in_d);
162 for(; out_d > in_d; out_d--);
163 if ((in[in_d] != out[out_d]) ||
164 (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
165 printf("Method: %s %s\n",
166 m->class->name->text, m->name->text);
167 printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
169 printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
171 /* _SSA_ASSERT(0); */
183 #ifdef SSA_DEBUG_VERBOSE
185 ssa_print_trees(jd, gd, dd);
189 /* ssa_init *******************************************************************
191 Initialise data structures for ssa
193 IOVARS of same stackdepth and same type are coalesced:
194 interface_map[ 5 * stackdepth + type ] = new_varindex with
195 0 <= new_varindex < ls->ssavarcount
197 TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent
198 basic blocks could decrease the number of phi functions and so improve ssa
199 analysis performance!
201 All LOCALVARS and IOVARS get a new unique varindex:
202 ls->new_varindex[0..jd->varcount[ = new_varindex with
203 0 <= new_varindex < ls->ssavarcount
205 The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[
206 are set to the definitions of LOCALVARS and IOVARS. (So the only the first
207 ls->ssavarcount bits of each of these vectors contain valid data, but
208 ls->ssavarcount is computed at the same time as the definitons are stored.)
210 The basic block number used as index for the bitvector array ls->var_def is
211 already shifted by one to make space for the new basic block 0 for parameter
214 ******************************************************************************/
216 void ssa_init(jitdata *jd) {
219 int i, l, b_index, len;
222 s4 *interface_map; /* holds an new unique index for every used */
223 /* basic block inoutvar described by a dupel */
224 /*(depth,type). Used to coalesce the inoutvars*/
227 builtintable_entry *bte;
234 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
235 # if defined(SSA_DEBUG_VERBOSE)
236 if (compileverbose) {
237 printf("%s %s ",m->class->name->text, m->name->text);
238 if (jd->isleafmethod)
239 printf("**Leafmethod**");
243 if (strcmp(m->class->name->text,"spec/benchmarks/_213_javac/Parser")==0)
244 if (strcmp(m->name->text,"parseTerm")==0)
245 # if defined(SSA_DEBUG_VERBOSE)
247 printf("12-------------------12\n");
249 { int dummy=1; dummy++; }
253 #ifdef SSA_DEBUG_VERBOSE
255 printf("ssa_init: basicblockcount %3i localcount %3i\n",
256 jd->basicblockcount, jd->localcount);
259 /* As first step all definitions of local variables and in/out vars are */
260 /* gathered. in/outvars are coalesced for same type and depth */
261 /* "normal" tempvars (just living within one basicblock are) ignored */
263 /* ls->var holds the index to jd->vars */
265 ls->num_defs = DMNEW(int, jd->varcount);
266 ls->new_varindex = DMNEW(int , jd->varcount);
268 for(p = 0; p < jd->varcount; p++) {
270 ls->new_varindex[p] = UNUSED;
273 /* init Var Definition bitvectors */
275 ls->var_def = DMNEW(int *, jd->basicblockcount + 1);
276 for(i = 0; i < jd->basicblockcount + 1; i++) {
277 ls->var_def[i] = bv_new(jd->varcount);
282 /* Add parameters first in right order, so the new local indices */
283 /* 0..p will correspond to "their" parameters */
284 /* They get defined at the artificial Block 0, the real method bbs will be*/
285 /* moved to start at block 1 */
287 /* don't look at already eliminated (not used) parameters (locals) */
289 for (p = 0, l = 0; p < md->paramcount; p++) {
290 t = md->paramtypes[p].type;
291 i = jd->local_map[l * 5 + t];
293 if (IS_2_WORD_TYPE(t)) /* increment local counter a second time */
294 l++; /* for 2 word types */
297 ssa_set_local_def(ls, -1, i);
300 _SSA_ASSERT(ls->ssavarcount < jd->varcount);
302 /* coalesce bb in/out vars */
304 interface_map = DMNEW(s4, jd->stackcount * 5);
305 for(i = 0; i < jd->stackcount * 5; i++)
306 interface_map[i] = UNUSED;
308 bptr = jd->basicblocks;
310 for(; bptr != NULL; bptr = bptr->next) {
311 #ifdef SSA_DEBUG_VERBOSE
313 printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags);
315 if (bptr->flags >= BBREACHED) {
317 /* 'valid' Basic Block */
323 ssa_set_interface(jd, bptr, interface_map);
325 /* !!!!!!!!! not true for now !!!!!!!!! */
326 /* All baseline optimizations from stack.c are turned off for */
329 for (; len > 0; len--, iptr++) {
331 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
332 /* an optional dst - so they to be checked first */
335 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
336 INSTRUCTION_GET_METHODDESC(iptr,md);
337 if (md->returntype.type != TYPE_VOID)
338 v = iptr->dst.varindex;
340 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
341 bte = iptr->sx.s23.s3.bte;
343 if (md->returntype.type != TYPE_VOID)
344 v = iptr->dst.varindex;
346 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
347 v = iptr->dst.varindex;
351 if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
352 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
354 /* _SSA_ASSERT(ls->new_varindex[v] != UNUSED); */
355 ssa_set_local_def(ls, b_index, v);
361 _SSA_ASSERT(ls->ssavarcount < jd->varcount);
362 #ifdef SSA_DEBUG_VERBOSE
363 if (compileverbose) {
365 printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
367 for(i = 0; i < jd->varcount; i++) {
368 if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
369 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
370 ssa_show_variable(jd, i, VAR(i),0);
371 if (i < ls->ssavarcount) {
372 printf(" -> %3i", ls->new_varindex[i]);
381 /* ssa_set_def ****************************************************************
383 Helper for ssa_set_local_def and ssa_set_interface
385 The definition of a var is stored in the bitvector array ls->var_def.
387 The number of definitons of each var is counted, so the number of new vars with
390 ******************************************************************************/
392 void ssa_set_def(lsradata *ls, int b_index, int varindex) {
394 /* b_index + 1 to leave space for the param init block 0 */
396 bv_set_bit(ls->var_def[b_index + 1], varindex);
398 /* count number of defs for every var since SSA */
399 /* will create a new var for every definition */
401 ls->num_defs[varindex]++;
404 /* ssa_set_local_def **********************************************************
408 Assigns a new unique index for the local var varindex (if not already done so)
409 and then calls ssa_set_def to remember the definition in the bitvector array
412 ******************************************************************************/
414 void ssa_set_local_def(lsradata *ls, int b_index, int varindex) {
416 if (ls->new_varindex[varindex] == UNUSED) {
417 ls->new_varindex[varindex] = ls->ssavarcount++;
420 ssa_set_def(ls, b_index, ls->new_varindex[varindex]);
423 /* ssa_set_local_def **********************************************************
425 Helper for ssa_set_interface
427 IN: ls pointer to lsradata structure
428 iovar varindex of INOUTVAR to process
429 map_index stackdepth * 5 + type, used for coalescing IOVARS.
432 interface_map used for coalescing IOVARS. interface_map[map_index] ==
433 UNUSED, if this map_index (==stackdepth,type tupel) did not
434 occur till now. Then interface_map[map_index] will be set
435 to a new unique index.
436 ls->new_varindex will be set to this new unique index to map the old
437 varindizes to the new ones.
439 Assigns a new unique index for the local var varindex (if not already done so)
440 and then calls ssa_set_def to remember the definition in the bitvector array
443 ******************************************************************************/
445 void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) {
446 if (interface_map[map_index] == UNUSED)
447 interface_map[map_index] = ls->ssavarcount++;
449 ls->new_varindex[iovar] = interface_map[map_index];
453 /* ssa_set_interface ***********************************************************
457 IN: ls pointer to lsradata structure
458 *bptr pointer to the basic block to be processed
461 interface_map used for coalescing IOVARS. interface_map[map_index] ==
462 UNUSED, if this map_index (==stackdepth,type tupel) did not
463 occur till now. Then interface_map[map_index] will be set
464 to a new unique index. (see ssa_set_iovar)
466 Searches the basic block given by *bptr for IN and OUTVARS and coalesces them
467 for each unique stackdepth,type dupel. For each OUTVAR with a different or no
468 INVAR at the same stackdepth the definition of this OUTVAR in this basic block
469 is remembered in ls->var_def. (see ssa_set_def)
471 ******************************************************************************/
473 void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) {
476 int o_map_index, i_map_index;
483 in_d = bptr->indepth - 1;
484 out_d = bptr->outdepth - 1;
486 /* ignore top Stackelement of instack in case of EXH or SBR blocks */
487 /* These are no Interface stackslots! */
488 if ((bptr->type == BBTYPE_EXH) ||
489 (bptr->type == BBTYPE_SBR)) {
493 /* invars with no corresponding outvars are not defined here */
494 /* just set up the interface_map */
496 for(;(in_d > out_d); in_d--) {
497 i_map_index = in_d * 5 + VAR(in[in_d])->type;
498 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
501 while((out_d >= 0)) {
502 /* set up interface_map */
504 o_map_index = out_d * 5 + VAR(out[out_d])->type;
506 i_map_index = in_d * 5 + VAR(in[in_d])->type;
507 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
509 ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
511 if (in[in_d] != out[out_d]) {
513 /* out interface stackslot is defined in this basic block */
515 /* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
523 /* out interface stackslot is defined in this basic block */
525 /* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
531 /* ssa_place_phi_functions *****************************************************
533 ls->phi[n][a][p] is created and populated.
535 For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
536 ls->basicblockcount)in which a variable (0 <= a < ls->ssavarcount) is defined an
537 entry in ls->phi[Y][a] is created.
538 This entry is an array with the number of predecessors of Y elements + 1 elements.
539 This elements are all set to the variable a and represent the phi function which
540 will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
542 *******************************************************************************/
545 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
548 bitvector *def_sites;
549 bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
557 W = wl_new(ls->basicblockcount);
559 def_sites = DMNEW(bitvector, ls->ssavarcount);
560 for(a = 0; a < ls->ssavarcount; a++)
561 def_sites[a] = bv_new(ls->basicblockcount);
563 ls->phi = DMNEW(int **, ls->basicblockcount);
564 A_phi = DMNEW(bitvector, ls->basicblockcount);
565 for(i = 0; i < ls->basicblockcount; i++) {
566 ls->phi[i] = DMNEW(int *, ls->ssavarcount);
567 for(j = 0; j < ls->ssavarcount; j++)
568 ls->phi[i][j] = NULL;
569 A_phi[i] = bv_new(ls->ssavarcount);
572 /* copy var_def to def_sites */
573 /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
575 for(n = 0; n <= jd->basicblockcount; n++)
576 for(a = 0; a < ls->ssavarcount; a++)
577 if (bv_get_bit(ls->var_def[n], a))
578 bv_set_bit(def_sites[a], n);
579 #ifdef SSA_DEBUG_VERBOSE
580 if (compileverbose) {
581 printf("var Definitions:\n");
582 for(i = 0; i < ls->ssavarcount; i++) {
583 printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
584 for(j = 0; j < ls->basicblockcount; j++) {
585 if ((j % 5) == 0) printf(" ");
586 if (bv_get_bit(def_sites[i], j))
598 for(a = 0; a < ls->ssavarcount; a++) {
600 /* W<-def_sites(a) */
602 for(n = 0; n < ls->basicblockcount; n++)
603 if (bv_get_bit(def_sites[a],n)) {
607 while (!wl_is_empty(W)) { /* W not empty */
610 for(i = 0; i < dd->num_DF[n]; i++) {
612 /* Node Y is in Dominance Frontier of n -> */
613 /* insert phi function for a at top of Y*/
614 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
615 if (bv_get_bit( A_phi[Y], a) == 0) {
616 /* a is not a Element of A_phi[Y] */
617 /* a <- phi(a,a...,a) to be inserted at top of Block Y */
618 /* phi has as many arguments, as Y has predecessors */
621 /* do not add a phi function for interface stackslots */
622 /* if a predecessor is not a def site of a <==> */
623 /* the block does not have the corresponding inslot*/
625 /* if ((ls->var_to_index[a] >= 0) || */
626 /* (bv_get_bit(def_sites[a], */
627 /* graph_get_first_predecessor(gd, Y, &iter)))) */
630 /* for interface stackslots add a phi function only */
631 /* if the basicblock has the corresponding incoming */
632 /* stackslot -> it could be, that the stackslot is */
633 /* not live anymore at Y */
636 num_pred = graph_get_num_predecessor(gd, Y);
637 ls->phi[Y][a] = DMNEW(int, num_pred + 1);
638 for (j = 0; j < num_pred + 1; j++)
639 ls->phi[Y][a][j] = a;
640 /* increment the number of definitions of a by one */
641 /* for this phi function */
644 bv_set_bit(A_phi[Y], a);
645 if (bv_get_bit(ls->var_def[Y],a)==0) {
646 /* Iterated Dominance Frontier Criterion:*/
647 /* if Y had no definition for a insert it*/
648 /* into the Worklist, since now it */
649 /* defines a through the phi function */
658 /* ssa_rename ******************************************************************
660 Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
661 has only one definition (SSA form).
663 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
664 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
665 definition of each old var.
666 ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
669 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
670 ls->varcount_with_indices.
672 jd->var and jd->varcount will be set for this renamed vars.
674 *******************************************************************************/
676 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
678 int i, mi, l, j, p, t;
680 methoddesc *md = jd->m->parseddesc;
687 ssa_rename_init(jd, gd);
689 /* Consider definition of Local Vars initialized with Arguments */
691 /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
692 for (p = 0, l= 0; p < md->paramcount; p++) {
693 t = md->paramtypes[p].type;
695 i = jd->local_map[mi];
697 if (IS_2_WORD_TYPE(t))
701 /* !!!!! locals are now numbered as the parameters !!!! */
702 /* !!!!! no additional increment for 2 word types !!!!! */
703 /* this happens later on! here we still need the increment */
704 /* index of var can be in the range from 0 up to not including */
707 /* ignore return value, since first definition gives 0 -> */
708 /* no rename necessary */
710 i = ls->new_varindex[i];
711 j = ssa_rename_def_(ls, i);
713 jd->local_map[mi] = i;
715 ssa_rename_(jd, gd, dd, 0);
718 /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
719 /* if there is no use of the defined Var itself by the phi function */
720 /* for a loop path, in which this var is not used, it will not be life */
721 /* in this path and overwritten! */
723 /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
724 /* this happens if the phi function is the first definition of x or in a */
725 /* path with a backedge xi has no definition */
726 /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
727 /* this phi function would otherwise "deadlock" the dead code elemination */
728 /* invalidate means set it to ls->max_vars_with_indices */
729 /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
730 /* [1,n] can be removed */
732 for(i = 0; i < ls->ssavarcount; i++) {
733 for(t = 0; t < ls->basicblockcount; t++) {
734 if (ls->phi[t][i] != 0) {
736 for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
737 if (ls->phi[t][i][0] == ls->phi[t][i][p])
738 ls->phi[t][i][p] = ls->varcount_with_indices;
744 ls->phi[t][i] = NULL;
749 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
750 # if defined(SSA_DEBUG_VERBOSE)
751 if (compileverbose) {
752 printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
753 if (jd->isleafmethod)
754 printf("**Leafmethod**");
758 if (strcmp(jd->m->class->name->text,"fp")==0)
759 if (strcmp(jd->m->name->text,"testfloat")==0)
760 # if defined(SSA_DEBUG_VERBOSE)
762 printf("12-------------------12\n");
764 { int dummy=1; dummy++; }
767 /* recreate rd->locals[][] */
768 /* now only one (local_index/type) pair exists anymore */
769 /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
770 /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
772 new_vars = DMNEW(varinfo, ls->vartop);
773 for(i = 0; i < ls->vartop ; i++)
774 new_vars[i].type = UNUSED;
775 for(i = 0; i < jd->varcount; i++) {
776 p = ls->new_varindex[i];
778 if (p < ls->ssavarcount)
780 new_vars[p].type = VAR(i)->type;
781 new_vars[p].flags = VAR(i)->flags;
782 ls->lifetime[p].v_index = p;
783 ls->lifetime[p].type = VAR(i)->type;
787 /* take care of newly indexed local & in/out vars */
789 for(i = 0; i < ls->ssavarcount; i++) {
791 type = new_vars[j].type;
792 flags = new_vars[j].flags;
794 for (; j < ls->var_0[i + 1]; j++) {
795 new_vars[j].type = type;
796 new_vars[j].flags = flags;
797 ls->lifetime[j].v_index = j;
798 ls->lifetime[j].type = type;
802 #ifdef SSA_DEBUG_VERBOSE
803 if (compileverbose) {
805 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
807 for(i = 0; i < jd->varcount; i++) {
808 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
809 ssa_show_variable(jd, i, VAR(i),0);
810 j = ls->new_varindex[i];
811 if ((j != UNUSED) && (j < ls->ssavarcount))
812 printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
814 printf(" -> %3i", j);
821 jd->varcount = ls->vartop;
822 jd->vartop = ls->vartop;
824 #ifdef SSA_DEBUG_VERBOSE
825 if (compileverbose) {
826 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
828 for(i = 0; i < jd->varcount; i++) {
829 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
830 ssa_show_variable(jd, i, VAR(i),0);
837 /* ssa_rename_init *************************************************************
839 Setup the data structure for ssa_rename
841 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
842 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
843 definition of each old var.
844 ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
847 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
848 ls->varcount_with_indices.
850 jd->var and jd->varcount will be set for this renamed vars.
852 *******************************************************************************/
854 void ssa_rename_init(jitdata *jd, graphdata *gd)
861 /* set up new locals */
862 /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
863 /* for locals and iovars */
865 /* ls->num_defs[index] gives the number of indizes which will be created */
868 /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
869 /* ls->var_0[X] will point to each LX(0) */
870 /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
872 /* as first step cummulate the num_defs array for locals and iovars */
873 /* last element is the maximum var count */
875 ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
877 ls->varcount_with_indices = 0;
878 for(i = 0; i < ls->ssavarcount; i++) {
879 ls->varcount_with_indices += ls->num_defs[i];
880 ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
884 /* Change the var indices in phi from La to La(0) */
886 for(i = 0; i < ls->basicblockcount; i++)
887 for (a = 0; a < ls->ssavarcount; a++)
888 if (ls->phi[i][a] != NULL)
889 for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
890 ls->phi[i][a][p] = ls->var_0[a];
895 ls->count = DMNEW(int, max(1, ls->ssavarcount));
896 ls->stack = DMNEW(int *, max(1, ls->ssavarcount));
897 ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
898 for(a = 0; a < ls->ssavarcount; a++) {
900 ls->stack_top[a] = 0;
902 /* stack a has to hold number of defs of a Elements + 1 */
904 ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
905 ls->stack[a][ls->stack_top[a]++] = 0;
908 if (ls->ssavarcount > 0) {
910 /* Create the num_var_use Array */
912 ls->num_var_use = DMNEW(int *, ls->basicblockcount);
913 for(i = 0; i < ls->basicblockcount; i++) {
914 ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
915 for(a = 0; a < ls->varcount_with_indices; a++)
916 ls->num_var_use[i][a] = 0;
919 /* Create the use_sites Array of Bitvectors*/
920 /* use max(1,..), to ensure that the array is created! */
922 ls->use_sites = DMNEW(bitvector, max(1, ls->varcount_with_indices));
923 for(a = 0; a < ls->varcount_with_indices; a++)
924 ls->use_sites[a] = bv_new(ls->basicblockcount);
928 /* count number of TEMPVARs */
930 ls->lifetimecount = 0;
931 for(i = 0; i < jd->varcount; i++)
932 if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
935 ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
937 ls->lifetimecount = ls->varcount;
938 ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
939 ls->lt_used = DMNEW(int, ls->lifetimecount);
940 ls->lt_int = DMNEW(int, ls->lifetimecount);
941 ls->lt_int_count = 0;
942 ls->lt_flt = DMNEW(int, ls->lifetimecount);
943 ls->lt_flt_count = 0;
944 ls->lt_mem = DMNEW(int, ls->lifetimecount);
945 ls->lt_mem_count = 0;
946 for (i=0; i < ls->lifetimecount; i++) {
947 ls->lifetime[i].type = UNUSED;
948 ls->lifetime[i].savedvar = 0;
949 ls->lifetime[i].flags = 0;
950 ls->lifetime[i].usagecount = 0;
951 ls->lifetime[i].bb_last_use = -1;
952 ls->lifetime[i].bb_first_def = -1;
953 ls->lifetime[i].use = NULL;
954 ls->lifetime[i].def = NULL;
955 ls->lifetime[i].last_use = NULL;
958 /* for giving TEMP and PREALLOC vars a new unique index */
960 ls->vartop = ls->varcount_with_indices;
962 #ifdef SSA_DEBUG_VERBOSE
963 if (compileverbose) {
964 printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
966 for(i = 0; i < jd->varcount; i++) {
967 if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
968 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
969 ssa_show_variable(jd, i, VAR(i),0);
970 if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
971 printf(" -> %3i", ls->new_varindex[i]);
976 ssa_print_phi(ls, gd);
981 int ssa_rename_def_(lsradata *ls, int a) {
984 _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
986 i = ls->count[a] - 1;
987 /* push i on stack[a] */
988 _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
989 ls->stack[a][ls->stack_top[a]++] = i;
993 int ssa_rename_def(jitdata *jd, int *def_count, int a) {
999 a1 = ls->new_varindex[a];
1000 _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1001 if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1002 /* local or inoutvar -> normal ssa renaming */
1003 _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
1004 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
1007 i = ssa_rename_def_(ls, a1);
1008 ret = ls->var_0[a1] + i;
1011 /* TEMP or PREALLOC var */
1013 ls->new_varindex[a] = ls->vartop;
1016 _SSA_ASSERT( ls->vartop < ls->varcount);
1024 void ssa_rename_use_(lsradata *ls, int n, int a) {
1025 _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
1026 if (ls->ssavarcount > 0) {
1027 bv_set_bit(ls->use_sites[a], n);
1028 ls->num_var_use[n][a]++;
1032 int ssa_rename_use(lsradata *ls, int n, int a) {
1036 a1 = ls->new_varindex[a];
1037 _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1038 if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1039 /* local or inoutvar -> normal ssa renaming */
1040 /* i <- top(stack[a]) */
1042 _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
1043 i = ls->stack[a1][ls->stack_top[a1] - 1];
1044 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
1046 ret = ls->var_0[a1] + i;
1049 /* TEMP or PREALLOC var */
1051 ls->new_varindex[a] = ls->vartop;
1054 _SSA_ASSERT( ls->vartop < ls->varcount);
1063 #ifdef SSA_DEBUG_VERBOSE
1064 void ssa_rename_print(instruction *iptr, char *op, int from, int to) {
1065 if (compileverbose) {
1066 printf("ssa_rename_: ");
1068 printf("%s ", opcode_names[iptr->opc]);
1072 printf("%s: %3i->%3i\n", op, from, to);
1077 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
1078 int a, i, j, k, iindex, Y, v;
1081 /* [0..ls->varcount[ Number of Definitions of this var in this */
1082 /* Basic Block. Used to remove the entries off the stack at the */
1083 /* end of the function */
1085 s4 *in, *out, *argp;
1086 graphiterator iter_succ, iter_pred;
1087 struct lifetime *lt;
1091 builtintable_entry *bte;
1097 #ifdef SSA_DEBUG_VERBOSE
1099 printf("ssa_rename_: BB %i\n",n);
1102 _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
1104 def_count = DMNEW(int, max(1, ls->ssavarcount));
1105 for(i = 0; i < ls->ssavarcount; i++)
1108 /* change Store of possible phi functions from a to ai*/
1110 for(a = 0; a < ls->ssavarcount; a++)
1111 if (ls->phi[n][a] != NULL) {
1113 /* do not mark this store as use - maybee this phi function */
1114 /* can be removed for unused Vars*/
1115 j = ls->var_0[a] + ssa_rename_def_(ls, a);
1116 #ifdef SSA_DEBUG_VERBOSE
1117 ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
1119 ls->phi[n][a][0] = j;
1122 in = ls->basicblocks[n]->invars;
1123 in_d = ls->basicblocks[n]->indepth - 1;
1125 /* change use of instack Interface stackslots except top SBR and EXH */
1128 if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
1129 (ls->basicblocks[n]->type == BBTYPE_SBR)) {
1132 /* out = ls->basicblocks[n]->outvars; */
1133 /* out_d = ls->basicblocks[n]->outdepth - 1; */
1135 /* for(; out_d > in_d; out_d--); */
1137 for (; in_d >= 0; in_d--) {
1138 /* Possible Use of ls->new_varindex[jd->var[in_d]] */
1139 _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
1141 a = ls->new_varindex[in[in_d]];
1142 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1144 /* i <- top(stack[a]) */
1146 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1147 i = ls->stack[a][ls->stack_top[a]-1];
1148 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1150 /* Replace use of x with xi */
1152 #ifdef SSA_DEBUG_VERBOSE
1153 ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
1155 in[in_d] = ls->var_0[a] + i;
1156 lt = ls->lifetime + in[in_d];
1158 lt->v_index = in[in_d];
1159 lt->bb_last_use = -1;
1162 iptr = ls->basicblocks[n]->iinstr;
1164 for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
1166 /* check for use (s1, s2, s3 or special (argp) ) */
1168 switch (icmd_table[iptr->opc].dataflow) {
1170 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1171 j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
1172 #ifdef SSA_DEBUG_VERBOSE
1173 ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
1175 iptr->sx.s23.s3.varindex = j;
1177 /* now "fall through" for handling of s2 and s1 */
1180 case DF_2_TO_1: /* icmd has s1 and s2 */
1181 j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
1182 #ifdef SSA_DEBUG_VERBOSE
1183 ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
1185 iptr->sx.s23.s2.varindex = j;
1187 /* now "fall through" for handling of s1 */
1193 j = ssa_rename_use(ls, n, iptr->s1.varindex);
1194 #ifdef SSA_DEBUG_VERBOSE
1195 ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
1197 iptr->s1.varindex = j;
1203 /* do not use md->paramcount, pass-through stackslots have */
1204 /* to be renamed, too */
1205 i = iptr->s1.argcount;
1206 argp = iptr->sx.s23.s2.args;
1208 j = ssa_rename_use(ls, n, *argp);
1209 #ifdef SSA_DEBUG_VERBOSE
1210 ssa_rename_print( iptr, "arg", *argp, j);
1219 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
1220 /* an optional dst - so they to be checked first */
1223 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
1224 INSTRUCTION_GET_METHODDESC(iptr,md);
1225 if (md->returntype.type != TYPE_VOID)
1226 v = iptr->dst.varindex;
1228 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
1229 bte = iptr->sx.s23.s3.bte;
1231 if (md->returntype.type != TYPE_VOID)
1232 v = iptr->dst.varindex;
1234 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
1235 v = iptr->dst.varindex;
1239 j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
1240 #ifdef SSA_DEBUG_VERBOSE
1241 ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
1243 iptr->dst.varindex = j;
1246 /* ?????????????????????????????????????????????????????????? */
1247 /* Mark Def as use, too. Since param initialisation is in */
1248 /* var_def and this would not remove this locals, if not used */
1250 /* ?????????????????????????????????????????????????????????? */
1254 /* change outstack Interface stackslots */
1255 out = ls->basicblocks[n]->outvars;
1256 out_d = ls->basicblocks[n]->outdepth - 1;
1258 for (;out_d >= 0; out_d--) {
1259 /* Possible Use of ls->new_varindex[jd->var[out_d]] */
1260 _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
1262 a = ls->new_varindex[out[out_d]];
1263 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1265 /* i <- top(stack[a]) */
1267 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1268 i = ls->stack[a][ls->stack_top[a]-1];
1269 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1271 /* Replace use of x with xi */
1273 #ifdef SSA_DEBUG_VERBOSE
1274 ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
1276 out[out_d] = ls->var_0[a] + i;
1277 lt = ls->lifetime + out[out_d];
1279 lt->v_index = out[out_d];
1280 lt->bb_last_use = -1;
1283 /* change use in phi Functions of Successors */
1285 Y = graph_get_first_successor(gd, n, &iter_succ);
1286 for(; Y != -1; Y = graph_get_next(&iter_succ)) {
1287 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
1288 k = graph_get_first_predecessor(gd, Y, &iter_pred);
1289 for (j = 0; (k != -1) && (k != n); j++)
1290 k = graph_get_next(&iter_pred);
1291 _SSA_ASSERT(k == n);
1293 /* n is jth Predecessor of Y */
1295 for(a = 0; a < ls->ssavarcount; a++)
1296 if (ls->phi[Y][a] != NULL) {
1298 /* i <- top(stack[a]) */
1300 if (ls->stack_top[a] == 1) {
1301 /* no definition till now in controll flow */
1302 #ifdef SSA_DEBUG_VERBOSE
1303 if (compileverbose) {
1304 printf("Succ %3i Arg %3i \n", Y, j);
1305 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
1308 ls->phi[Y][a][j+1] = UNUSED;
1311 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1312 i = ls->stack[a][ls->stack_top[a]-1];
1313 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1315 /* change jth operand from a0 to ai */
1317 i = ls->var_0[a] + i;
1318 #ifdef SSA_DEBUG_VERBOSE
1319 if (compileverbose) {
1320 printf("Succ %3i Arg %3i \n", Y, j);
1321 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
1324 ls->phi[Y][a][j+1] = i;
1325 _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
1326 ls->varcount_with_indices);
1328 /* use by phi function has to be remembered, too */
1330 ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
1333 /* ????????????????????????????????????????????? */
1334 /* why was this only for local vars before ? */
1335 /* ????????????????????????????????????????????? */
1340 /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
1341 for(i = 0; i < ls->basicblockcount; i++)
1342 if (dd->idom[i] == n)
1343 ssa_rename_(jd, gd, dd, i);
1345 /* pop Stack[a] for each definition of a var a in the original S */
1346 for(a = 0; a < ls->ssavarcount; a++) {
1347 ls->stack_top[a] -= def_count[a];
1348 _SSA_ASSERT(ls->stack_top[a] >= 0);
1354 #ifdef SSA_DEBUG_VERBOSE
1355 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
1361 printf("ssa_printtrees: maxlocals %3i", jd->localcount);
1363 printf("Dominator Tree: \n");
1364 for(i = 0; i < ls->basicblockcount; i++) {
1366 for(j = 0; j < ls->basicblockcount; j++) {
1367 if (dd->idom[j] == i) {
1374 printf("Dominator Forest:\n");
1375 for(i = 0; i < ls->basicblockcount; i++) {
1377 for(j = 0; j < dd->num_DF[i]; j++) {
1378 printf(" %3i", dd->DF[i][j]);
1383 if (ls->ssavarcount > 0) {
1384 printf("Use Sites\n");
1385 for(i = 0; i < ls->ssavarcount; i++) {
1386 printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]);
1387 for(j = 0; j < ls->basicblockcount; j++) {
1388 if ((j % 5) == 0) printf(" ");
1389 if (bv_get_bit(ls->use_sites[i], j))
1398 printf("var Definitions:\n");
1399 for(i = 0; i < jd->basicblockcount; i++) {
1400 printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]);
1401 for(j = 0; j < ls->ssavarcount; j++) {
1402 if ((j % 5) == 0) printf(" ");
1403 if (bv_get_bit(ls->var_def[i], j))
1409 for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
1411 printf("%8x",ls->var_def[i][j]);
1416 void ssa_print_phi(lsradata *ls, graphdata *gd) {
1419 printf("phi Functions (varcount_with_indices: %3i):\n",
1420 ls->varcount_with_indices);
1421 for(i = 0; i < ls->basicblockcount; i++) {
1422 for(j = 0; j < ls->ssavarcount; j++) {
1423 if (ls->phi[i][j] != NULL) {
1424 printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
1425 for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
1426 printf("%3i ",ls->phi[i][j][k]);
1436 void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
1443 /* count moves to be inserted at the end of each block in moves[] */
1444 ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
1445 for(i = 0; i < ls->basicblockcount; i++)
1446 ls->num_phi_moves[i] = 0;
1447 for(i = 0; i < ls->basicblockcount; i++)
1448 for(a = 0; a < ls->ssavarcount; a++)
1449 if (ls->phi[i][a] != NULL) {
1451 if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
1452 /* Var defined (only <- SSA Form!) in this phi function */
1453 /* and not used anywhere -> delete phi function and set */
1456 /* TODO: first delete use sites of arguments of phi */
1458 VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
1459 ls->lifetime[ls->phi[i][a][0]].def = NULL;
1460 ls->phi[i][a] = NULL;
1465 pred = graph_get_first_predecessor(gd, i, &iter);
1466 for(; pred != -1; pred = graph_get_next(&iter)) {
1467 ls->num_phi_moves[pred]++;
1472 /* allocate ls->phi_moves */
1473 ls->phi_moves = DMNEW( int **, ls->basicblockcount);
1474 for(i = 0; i < ls->basicblockcount; i++) {
1475 ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
1476 for(j = 0; j <ls->num_phi_moves[i]; j++)
1477 ls->phi_moves[i][j] = DMNEW(int, 2);
1478 #ifdef SSA_DEBUG_VERBOSE
1480 printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
1481 i, ls->num_phi_moves[i]);
1485 /* populate ls->phi_moves */
1486 for(i = 0; i < ls->basicblockcount; i++)
1487 ls->num_phi_moves[i] = 0;
1488 for(i = 0; i < ls->basicblockcount; i++)
1489 for(a = 0; a < ls->ssavarcount; a++)
1490 if (ls->phi[i][a] != NULL) {
1491 pred = graph_get_first_predecessor(gd, i, &iter);
1492 for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
1493 /* target is phi[i][a][0] */
1494 /* source is phi[i][a][j+1] */
1495 if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
1497 if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
1498 ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
1500 ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
1508 /****************************************************************************
1510 ****************************************************************************/
1513 /****************************************************************************
1514 Dead Code Elimination
1515 ****************************************************************************/
1516 void dead_code_elimination(jitdata *jd, graphdata *gd) {
1521 struct lifetime *lt, *s_lt;
1523 bool remove_statement;
1527 #ifdef SSA_DEBUG_VERBOSE
1534 W = wl_new(ls->lifetimecount);
1535 if (ls->lifetimecount > 0) {
1536 /* put all lifetimes on Worklist */
1537 for(a = 0; a < ls->lifetimecount; a++) {
1538 if (ls->lifetime[a].type != -1) {
1544 /* Remove unused lifetimes */
1545 while(!wl_is_empty(W)) {
1546 /* take a var out of Worklist */
1549 lt = &(ls->lifetime[a]);
1550 if ((lt->def == NULL) || (lt->type == -1))
1551 /* lifetime was already removed -> no defs anymore */
1554 /* Remove lifetimes, which are only used in a phi function, which
1556 remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
1557 for(use = lt->use; (remove_statement && (use != NULL));
1560 remove_statement = remove_statement &&
1561 (use->b_index == lt->def->b_index) &&
1562 (use->iindex == lt->def->iindex);
1564 if (remove_statement) {
1565 #ifdef SSA_DEBUG_CHECK
1566 /* def == use can only happen in phi functions */
1567 if (remove_statement)
1568 _SSA_ASSERT(lt->use->iindex < 0);
1570 /* give it free for removal */
1574 if (lt->use == NULL) {
1575 /* Look at statement of definition of a and remove it, */
1576 /* if the Statement has no sideeffects other than the assignemnt */
1578 if (lt->def->iindex < 0 ) {
1580 /* delete use of sources , delete phi functions */
1582 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] !=
1585 for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
1589 ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1590 if ((source != ls->varcount_with_indices) &&
1591 (source != lt->v_index)) {
1593 /* phi Argument was not already removed (already in
1594 because of selfdefinition) */
1596 s_lt = &(ls->lifetime[source]);
1600 lt_remove_use_site(s_lt,lt->def->b_index,
1603 /* put it on the Worklist */
1608 /* now delete phi function itself */
1609 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1611 /* "normal" Use by ICMD */
1612 remove_statement = false;
1613 if (lt->def->b_index != 0) {
1615 /* do not look at artificial block 0 (parameter init) */
1617 iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1620 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
1621 remove_statement = false;
1623 /* if ICMD could throw an exception do not remove it! */
1627 /* ICMD_INVOKE*, ICMD_BUILTIN and ICMD_MULTIANEWARRAY */
1628 /* have possible sideeffects -> do not remove them */
1630 /* remove_statement = !(ICMD_HAS_SPECIAL(iptr->opc)); */
1632 remove_statement = !(
1633 (icmd_table[iptr->opc].dataflow == DF_INVOKE) ||
1634 (icmd_table[iptr->opc].dataflow == DF_BUILTIN) ||
1635 (icmd_table[iptr->opc].dataflow == DF_N_TO_1));
1637 if (remove_statement) {
1638 switch (icmd_table[iptr->opc].dataflow) {
1640 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1641 a = iptr->sx.s23.s3.varindex;
1642 s_lt = ls->lifetime + a;
1643 lt_remove_use_site(s_lt, lt->def->b_index,
1647 /* now "fall through" for handling of s2 and s1 */
1650 case DF_2_TO_1: /* icmd has s1 and s2 */
1651 a = iptr->sx.s23.s2.varindex;
1652 s_lt = ls->lifetime + a;
1653 lt_remove_use_site(s_lt, lt->def->b_index,
1657 /* now "fall through" for handling of s1 */
1663 a = iptr->s1.varindex;
1664 s_lt = ls->lifetime + a;
1665 lt_remove_use_site(s_lt, lt->def->b_index,
1672 if (remove_statement) {
1674 /* remove statement */
1676 #ifdef SSA_DEBUG_VERBOSE
1678 printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
1679 m->class->name->text, m->name->text,
1680 lt->def->b_index, lt->def->iindex,
1681 icmd_table[iptr->opc].name);
1683 iptr->opc = ICMD_NOP;
1685 } /* (lt->def->b_index != 0) */
1686 } /* if (lt->def->iindex < 0 ) else */
1688 /* remove definition of a */
1690 VAR(lt->v_index)->type = -1;
1693 } /* if (lt->use == NULL) */
1694 } /* while(!wl_is_empty(W)) */
1695 } /* dead_code_elimination */
1697 /****************************************************************************
1698 Simple Constant Propagation
1699 ****************************************************************************/
1701 void simple_constant_propagation() {
1704 /****************************************************************************
1706 *******************************************************************************/
1707 void copy_propagation(jitdata *jd, graphdata *gd) {
1714 struct lifetime *lt, *s_lt;
1721 W = wl_new(ls->lifetimecount);
1722 if (ls->lifetimecount > 0) {
1723 /* put all lifetimes on Worklist */
1724 for(a = 0; a < ls->lifetimecount; a++) {
1725 if (ls->lifetime[a].type != -1) {
1731 while(!wl_is_empty(W)) {
1732 /* take a var out of Worklist */
1735 lt = ls->lifetime + a;
1738 _SSA_ASSERT(lt->def != NULL);
1739 _SSA_ASSERT(lt->use != NULL);
1740 if (lt->def->iindex < 0 ) {
1743 /* look, if phi function degenerated to a x = phi(y) */
1744 /* and if so, substitute y for every use of x */
1746 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL);
1748 only_source = ls->varcount_with_indices;
1749 for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
1751 source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1752 if (source != ls->varcount_with_indices) {
1753 if (only_source == ls->varcount_with_indices) {
1754 /* first valid source argument of phi function */
1755 only_source = source;
1757 /* second valid source argument of phi function */
1759 only_source = ls->varcount_with_indices;
1764 if (only_source != ls->varcount_with_indices) {
1766 /* replace all use sites of lt with the var_index only_source */
1768 ssa_replace_use_sites( jd, gd, lt, only_source, W);
1770 /* delete def of lt and replace uses of lt with "only_source" */
1772 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1774 s_lt = ls->lifetime + only_source;
1776 VAR(lt->v_index)->type = -1;
1777 lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
1779 /* move use sites from lt to s_lt */
1780 lt_move_use_sites(lt, s_lt);
1782 } /* if (only_source != ls->varcount_with_indices) */
1783 } else { /* if (lt->def->iindex < 0 )*/
1784 /* def in "normal" ICMD */
1786 iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1790 if (lt->def->b_index == 0)
1799 if (lt->def->iindex == 0) {
1800 /* first instruction in bb -> instack==bb->instack */
1801 in = ls->basicblocks[lt->def->b_index]->instack;
1803 /* instack is (iptr-1)->dst */
1807 if (in->varkind != LOCALVAR) {
1808 #ifdef SSA_DEBUG_VERBOSE
1810 printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
1812 s_lt = &(ls->lifetime[-in->varnum-1]);
1814 for (ss = s_lt->local_ss; ss != NULL; ss = ss->next) {
1815 ss->s->varkind = LOCALVAR;
1816 ss->s->varnum = iptr->op1;
1819 /* replace all use sites of s_lt with the var_index */
1822 ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
1824 /* s_lt->def is the new def site of lt */
1825 /* the old ->def site will get a use site of def */
1826 /* only one def site */
1827 _SSA_ASSERT(lt->def->next == NULL);
1828 _SSA_ASSERT(s_lt->def != NULL);
1829 _SSA_ASSERT(s_lt->def->next == NULL);
1831 /* replace def of s_lt with iptr->op1 */
1832 if (s_lt->def->iindex < 0) {
1834 _SSA_ASSERT(ls->phi[s_lt->def->b_index]
1835 [-s_lt->def->iindex-1]
1837 ls->phi[s_lt->def->b_index][-s_lt->def->iindex-1][0]
1840 if (in->varnum != iptr->op1)
1841 printf("copy propagation: LOCALVAR ss->ISTORE BB %i II %i\n",
1842 lt->def->b_index, lt->def->iindex);
1845 /* move def to use sites of lt */
1846 lt->def->next = lt->use;
1849 lt->def = s_lt->def;
1854 /* move use sites from s_lt to lt */
1855 move_use_sites(s_lt, lt);
1856 move_stackslots(s_lt, lt);
1862 /* Def Interface Stackslot */
1870 only_source = lt->local_ss->s->varnum;
1871 if (lt->local_ss->s->varkind != LOCALVAR) {
1872 #ifdef SSA_DEBUG_VERBOSE
1874 printf("copy propagation xload: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, lt->local_ss->s->varnum);
1876 _SSA_ASSERT(iptr->dst->varnum == lt->local_ss->s->varnum);
1877 for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
1878 ss->s->varkind = LOCALVAR;
1879 ss->s->varnum = iptr->op1;
1882 /* replace all use sites of lt with the var_index iptr->op1*/
1884 ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
1888 s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
1890 /* move use sites from lt to s_lt */
1891 move_use_sites(lt, s_lt);
1892 move_stackslots(lt, s_lt);
1895 if (lt->local_ss->s->varnum != iptr->op1)
1896 printf("copy propagation: ILOAD -> LOCALVAR ss BB %i II %i\n",
1897 lt->def->b_index, lt->def->iindex);
1901 } /* localvar or interface stackslot */
1903 } /* i(lt->def->iindex < 0 ) */
1905 } /* while(!wl_is_empty(W)) */
1908 void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt,
1909 int new_v_index, worklist *W) {
1916 builtintable_entry *bte;
1920 md = jd->m->parseddesc;
1923 for(s = lt->use; s != NULL; s = s->next) {
1924 if (s->iindex < 0) {
1926 /* Use in phi function */
1928 for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
1929 source = ls->phi[s->b_index][-s->iindex-1][i];
1930 if (source == lt->v_index) {
1931 #ifdef SSA_DEBUG_VERBOSE
1934 printf("copy propagation phi: BB %3i I %3i: %3i -> \
1935 %3i\n", s->b_index, s->iindex,
1936 new_v_index, source);
1939 ls->phi[s->b_index][-s->iindex-1][i]
1945 /* Add var, which is defined by this phi function to */
1948 source = ls->phi[s->b_index][-s->iindex-1][0];
1952 else { /* use in ICMD */
1954 iptr = ls->basicblocks[s->b_index]->iinstr +
1957 /* check for use (s1, s2, s3 or special (argp) ) */
1960 switch (icmd_table[iptr->opc].dataflow) {
1962 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1963 if (iptr->sx.s23.s3.varindex == lt->v_index) {
1964 #ifdef SSA_DEBUG_VERBOSE
1967 printf("copy propagation loc: BB %3i I %3i: %3i -> \
1968 %3i\n", s->b_index, s->iindex,
1969 new_v_index, iptr->sx.s23.s3.varindex);
1972 iptr->sx.s23.s3.varindex = new_v_index;
1975 /* now "fall through" for handling of s2 and s1 */
1978 case DF_2_TO_1: /* icmd has s1 and s2 */
1979 if (iptr->sx.s23.s2.varindex == lt->v_index) {
1980 #ifdef SSA_DEBUG_VERBOSE
1983 printf("copy propagation loc: BB %3i I %3i: %3i -> \
1984 %3i\n", s->b_index, s->iindex,
1985 new_v_index, iptr->sx.s23.s2.varindex);
1988 iptr->sx.s23.s2.varindex = new_v_index;
1991 /* now "fall through" for handling of s1 */
1997 if (iptr->s1.varindex == lt->v_index) {
1998 #ifdef SSA_DEBUG_VERBOSE
2001 printf("copy propagation loc: BB %3i I %3i: %3i -> \
2002 %3i\n", s->b_index, s->iindex,
2003 new_v_index, iptr->s1.varindex);
2006 iptr->s1.varindex = new_v_index;
2011 /* ? really look at md->paramcount or iptr->s1.argcount */
2012 /* has to be taken, so that pass-through stackslots get */
2016 INSTRUCTION_GET_METHODDESC(iptr,md);
2020 bte = iptr->sx.s23.s3.bte;
2025 i = iptr->s1.argcount;
2029 argp = iptr->sx.s23.s2.args;
2031 if (*argp == lt->v_index) {
2032 #ifdef SSA_DEBUG_VERBOSE
2036 "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
2037 , s->b_index, s->iindex, new_v_index, *argp);
2040 *argp = new_v_index;
2047 } /* if (s->iindex < 0) */
2048 } /* for(s = lt->use; s != NULL; s = s->next) */
2051 #ifdef SSA_DEBUG_VERBOSE
2052 void ssa_print_lt(lsradata *ls) {
2054 struct lifetime *lt;
2057 printf("SSA LT Def/Use\n");
2058 for(i = 0; i < ls->lifetimecount; i++) {
2059 lt = ls->lifetime + i;
2060 if (lt->type != UNUSED) {
2061 printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
2062 if (lt->def != NULL)
2063 printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
2065 printf("%3i,%3i Use: ",0,0);
2066 for(use = lt->use; use != NULL; use = use->next)
2067 printf("%3i,%3i ",use->b_index, use->iindex);
2073 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage)
2079 case TYPE_INT: type = 'i'; break;
2080 case TYPE_LNG: type = 'l'; break;
2081 case TYPE_FLT: type = 'f'; break;
2082 case TYPE_DBL: type = 'd'; break;
2083 case TYPE_ADR: type = 'a'; break;
2084 case TYPE_RET: type = 'r'; break;
2085 default: type = '?';
2088 if (index < jd->localcount) {
2090 if (v->flags & (PREALLOC | INOUT))
2091 printf("<INVALID FLAGS!>");
2094 if (v->flags & PREALLOC) {
2096 if (v->flags & INOUT)
2097 printf("<INVALID FLAGS!>");
2099 else if (v->flags & INOUT)
2105 printf("%c%c%3d", kind, type, index);
2107 if (v->flags & SAVEDVAR)
2115 /****************************************************************************
2117 ****************************************************************************/
2120 * These are local overrides for various environment variables in Emacs.
2121 * Please do not remove this and leave it at the end of the file, where
2122 * Emacs will automagically detect them.
2123 * ---------------------------------------------------------------------
2126 * indent-tabs-mode: t