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
35 #include "mm/memory.h"
37 #include "toolbox/bitvector.h"
38 #include "toolbox/worklist.h"
40 #include "vm/builtin.h"
42 #include "vm/jit/jit.h" /* icmd_table */
44 #include "vm/jit/optimizing/dominators.h"
45 #include "vm/jit/optimizing/graph.h"
46 #include "vm/jit/optimizing/lifetimes.h"
47 #include "vm/jit/optimizing/lsra.h"
49 #include "vm/jit/optimizing/ssa.h"
51 #if defined(SSA_DEBUG_VERBOSE)
52 #include "vmcore/options.h" /* compileverbose */
55 /* function prototypes */
56 void ssa_set_local_def(lsradata *, int , int);
57 void ssa_set_interface(jitdata *, basicblock *, s4 *);
59 void dead_code_elimination(jitdata *jd, graphdata *gd);
60 void copy_propagation(jitdata *jd, graphdata *gd);
61 void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
63 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
64 void ssa_rename_init(jitdata *jd, graphdata *gd);
65 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
66 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
68 void ssa_set_def(lsradata *, int , int );
69 void ssa_set_local_def(lsradata *, int , int );
70 void ssa_set_iovar(lsradata *, s4 , int , s4 *);
71 void ssa_set_interface(jitdata *, basicblock *, s4 *);
73 void ssa_generate_phi_moves(jitdata *, graphdata *);
74 int ssa_rename_def_(lsradata *ls, int a);
76 #ifdef SSA_DEBUG_VERBOSE
77 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
78 void ssa_print_lt(lsradata *ls);
79 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
80 void ssa_print_phi(lsradata *, graphdata *);
83 /* ssa ************************************************************************
87 ******************************************************************************/
89 void ssa(jitdata *jd, graphdata *gd) {
90 struct dominatordata *dd;
95 dd = compute_Dominators(gd, ls->basicblockcount);
96 computeDF(gd, dd, ls->basicblockcount, 0);
98 ssa_place_phi_functions(jd, gd, dd);
99 ssa_rename(jd, gd, dd);
100 #ifdef SSA_DEBUG_VERBOSE
101 if (compileverbose) {
102 printf("Phi before Cleanup\n");
103 ssa_print_phi(ls, gd);
107 lt_scanlifetimes(jd, gd, dd);
108 #ifdef SSA_DEBUG_VERBOSE
109 if (compileverbose) {
113 /* dead_code_elimination(jd, gd); */
114 #ifdef SSA_DEBUG_VERBOSE
115 if (compileverbose) {
116 printf("Phi after dead code elemination\n");
117 ssa_print_phi(ls, gd);
121 /* copy_propagation(jd, gd); */
122 #ifdef SSA_DEBUG_VERBOSE
123 if (compileverbose) {
124 printf("Phi after copy propagation\n");
125 ssa_print_phi(ls, gd);
130 ssa_generate_phi_moves(jd, gd);
131 transform_BB(jd, gd);
134 #ifdef SSA_DEBUG_CHECK
136 int i, j, pred, in_d, out_d;
137 graphiterator iter_pred;
144 for(i = 0; i < ls->basicblockcount; i++) {
145 if (ls->basicblocks[i]->indepth != 0) {
146 pred = graph_get_first_predecessor(gd, i, &iter_pred);
147 for (; (pred != -1); pred = graph_get_next(&iter_pred)) {
148 in_d = ls->basicblocks[i]->indepth - 1;
149 in = ls->basicblocks[i]->invars;
150 for (; in_d >= 0; in_d--) {
152 for (j = 0; (!phi_define) && (j<ls->ssavarcount); j++) {
153 if (ls->phi[i][j] != NULL)
154 if (ls->phi[i][j][0] == in[in_d])
158 /* in not defined in phi function -> check with */
159 /* outstack(s) of predecessor(s) */
160 out_d = ls->basicblocks[pred]->outdepth - 1;
161 out = ls->basicblocks[pred]->outvars;
162 _SSA_ASSERT(out_d >= in_d);
163 for(; out_d > in_d; out_d--);
164 if ((in[in_d] != out[out_d]) ||
165 (VAR(in[in_d])->flags != VAR(out[out_d])->flags)) {
166 printf("Method: %s %s\n",
167 m->class->name->text, m->name->text);
168 printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
170 printf("Error: Stack Varnum Mismatch BBin %3i BBout %3i Stackdepth %3i\n", i, pred, in_d);
172 /* _SSA_ASSERT(0); */
184 #ifdef SSA_DEBUG_VERBOSE
186 ssa_print_trees(jd, gd, dd);
190 /* ssa_init *******************************************************************
192 Initialise data structures for ssa
194 IOVARS of same stackdepth and same type are coalesced:
195 interface_map[ 5 * stackdepth + type ] = new_varindex with
196 0 <= new_varindex < ls->ssavarcount
198 TODO: check if coalescing of IOVARS of same stackdepth and type only of adjacent
199 basic blocks could decrease the number of phi functions and so improve ssa
200 analysis performance!
202 All LOCALVARS and IOVARS get a new unique varindex:
203 ls->new_varindex[0..jd->varcount[ = new_varindex with
204 0 <= new_varindex < ls->ssavarcount
206 The jd->varcount bits long bitvectors ls->var_def[0..jd->basicblockindex+1[
207 are set to the definitions of LOCALVARS and IOVARS. (So the only the first
208 ls->ssavarcount bits of each of these vectors contain valid data, but
209 ls->ssavarcount is computed at the same time as the definitons are stored.)
211 The basic block number used as index for the bitvector array ls->var_def is
212 already shifted by one to make space for the new basic block 0 for parameter
215 ******************************************************************************/
217 void ssa_init(jitdata *jd) {
220 int i, l, b_index, len;
223 s4 *interface_map; /* holds an new unique index for every used */
224 /* basic block inoutvar described by a dupel */
225 /*(depth,type). Used to coalesce the inoutvars*/
228 builtintable_entry *bte;
235 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
236 # if defined(SSA_DEBUG_VERBOSE)
237 if (compileverbose) {
238 printf("%s %s ",m->class->name->text, m->name->text);
239 if (jd->isleafmethod)
240 printf("**Leafmethod**");
244 if (strcmp(m->class->name->text,"spec/benchmarks/_213_javac/Parser")==0)
245 if (strcmp(m->name->text,"parseTerm")==0)
246 # if defined(SSA_DEBUG_VERBOSE)
248 printf("12-------------------12\n");
250 { int dummy=1; dummy++; }
254 #ifdef SSA_DEBUG_VERBOSE
256 printf("ssa_init: basicblockcount %3i localcount %3i\n",
257 jd->basicblockcount, jd->localcount);
260 /* As first step all definitions of local variables and in/out vars are */
261 /* gathered. in/outvars are coalesced for same type and depth */
262 /* "normal" tempvars (just living within one basicblock are) ignored */
264 /* ls->var holds the index to jd->vars */
266 ls->num_defs = DMNEW(int, jd->varcount);
267 ls->new_varindex = DMNEW(int , jd->varcount);
269 for(p = 0; p < jd->varcount; p++) {
271 ls->new_varindex[p] = UNUSED;
274 /* init Var Definition bitvectors */
276 ls->var_def = DMNEW(int *, jd->basicblockcount + 1);
277 for(i = 0; i < jd->basicblockcount + 1; i++) {
278 ls->var_def[i] = bv_new(jd->varcount);
283 /* Add parameters first in right order, so the new local indices */
284 /* 0..p will correspond to "their" parameters */
285 /* They get defined at the artificial Block 0, the real method bbs will be*/
286 /* moved to start at block 1 */
288 /* don't look at already eliminated (not used) parameters (locals) */
290 for (p = 0, l = 0; p < md->paramcount; p++) {
291 t = md->paramtypes[p].type;
292 i = jd->local_map[l * 5 + t];
294 if (IS_2_WORD_TYPE(t)) /* increment local counter a second time */
295 l++; /* for 2 word types */
298 ssa_set_local_def(ls, -1, i);
301 _SSA_ASSERT(ls->ssavarcount < jd->varcount);
303 /* coalesce bb in/out vars */
305 interface_map = DMNEW(s4, jd->stackcount * 5);
306 for(i = 0; i < jd->stackcount * 5; i++)
307 interface_map[i] = UNUSED;
309 bptr = jd->basicblocks;
311 for(; bptr != NULL; bptr = bptr->next) {
312 #ifdef SSA_DEBUG_VERBOSE
314 printf("ssa_init: BB %3i flags %3x\n",bptr->nr, bptr->flags);
316 if (bptr->flags >= BBREACHED) {
318 /* 'valid' Basic Block */
324 ssa_set_interface(jd, bptr, interface_map);
326 /* !!!!!!!!! not true for now !!!!!!!!! */
327 /* All baseline optimizations from stack.c are turned off for */
330 for (; len > 0; len--, iptr++) {
332 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
333 /* an optional dst - so they to be checked first */
336 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
337 INSTRUCTION_GET_METHODDESC(iptr,md);
338 if (md->returntype.type != TYPE_VOID)
339 v = iptr->dst.varindex;
341 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
342 bte = iptr->sx.s23.s3.bte;
344 if (md->returntype.type != TYPE_VOID)
345 v = iptr->dst.varindex;
347 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
348 v = iptr->dst.varindex;
352 if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
353 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
355 /* _SSA_ASSERT(ls->new_varindex[v] != UNUSED); */
356 ssa_set_local_def(ls, b_index, v);
362 _SSA_ASSERT(ls->ssavarcount < jd->varcount);
363 #ifdef SSA_DEBUG_VERBOSE
364 if (compileverbose) {
366 printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
368 for(i = 0; i < jd->varcount; i++) {
369 if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
370 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
371 ssa_show_variable(jd, i, VAR(i),0);
372 if (i < ls->ssavarcount) {
373 printf(" -> %3i", ls->new_varindex[i]);
382 /* ssa_set_def ****************************************************************
384 Helper for ssa_set_local_def and ssa_set_interface
386 The definition of a var is stored in the bitvector array ls->var_def.
388 The number of definitons of each var is counted, so the number of new vars with
391 ******************************************************************************/
393 void ssa_set_def(lsradata *ls, int b_index, int varindex) {
395 /* b_index + 1 to leave space for the param init block 0 */
397 bv_set_bit(ls->var_def[b_index + 1], varindex);
399 /* count number of defs for every var since SSA */
400 /* will create a new var for every definition */
402 ls->num_defs[varindex]++;
405 /* ssa_set_local_def **********************************************************
409 Assigns a new unique index for the local var varindex (if not already done so)
410 and then calls ssa_set_def to remember the definition in the bitvector array
413 ******************************************************************************/
415 void ssa_set_local_def(lsradata *ls, int b_index, int varindex) {
417 if (ls->new_varindex[varindex] == UNUSED) {
418 ls->new_varindex[varindex] = ls->ssavarcount++;
421 ssa_set_def(ls, b_index, ls->new_varindex[varindex]);
424 /* ssa_set_local_def **********************************************************
426 Helper for ssa_set_interface
428 IN: ls pointer to lsradata structure
429 iovar varindex of INOUTVAR to process
430 map_index stackdepth * 5 + type, used for coalescing IOVARS.
433 interface_map used for coalescing IOVARS. interface_map[map_index] ==
434 UNUSED, if this map_index (==stackdepth,type tupel) did not
435 occur till now. Then interface_map[map_index] will be set
436 to a new unique index.
437 ls->new_varindex will be set to this new unique index to map the old
438 varindizes to the new ones.
440 Assigns a new unique index for the local var varindex (if not already done so)
441 and then calls ssa_set_def to remember the definition in the bitvector array
444 ******************************************************************************/
446 void ssa_set_iovar(lsradata *ls, s4 iovar, int map_index, s4 *interface_map) {
447 if (interface_map[map_index] == UNUSED)
448 interface_map[map_index] = ls->ssavarcount++;
450 ls->new_varindex[iovar] = interface_map[map_index];
454 /* ssa_set_interface ***********************************************************
458 IN: ls pointer to lsradata structure
459 *bptr pointer to the basic block to be processed
462 interface_map used for coalescing IOVARS. interface_map[map_index] ==
463 UNUSED, if this map_index (==stackdepth,type tupel) did not
464 occur till now. Then interface_map[map_index] will be set
465 to a new unique index. (see ssa_set_iovar)
467 Searches the basic block given by *bptr for IN and OUTVARS and coalesces them
468 for each unique stackdepth,type dupel. For each OUTVAR with a different or no
469 INVAR at the same stackdepth the definition of this OUTVAR in this basic block
470 is remembered in ls->var_def. (see ssa_set_def)
472 ******************************************************************************/
474 void ssa_set_interface(jitdata *jd, basicblock *bptr, s4 *interface_map) {
477 int o_map_index, i_map_index;
484 in_d = bptr->indepth - 1;
485 out_d = bptr->outdepth - 1;
487 /* ignore top Stackelement of instack in case of EXH or SBR blocks */
488 /* These are no Interface stackslots! */
489 if ((bptr->type == BBTYPE_EXH) ||
490 (bptr->type == BBTYPE_SBR)) {
494 /* invars with no corresponding outvars are not defined here */
495 /* just set up the interface_map */
497 for(;(in_d > out_d); in_d--) {
498 i_map_index = in_d * 5 + VAR(in[in_d])->type;
499 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
502 while((out_d >= 0)) {
503 /* set up interface_map */
505 o_map_index = out_d * 5 + VAR(out[out_d])->type;
507 i_map_index = in_d * 5 + VAR(in[in_d])->type;
508 ssa_set_iovar(ls, in[in_d], i_map_index, interface_map);
510 ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
512 if (in[in_d] != out[out_d]) {
514 /* out interface stackslot is defined in this basic block */
516 /* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
524 /* out interface stackslot is defined in this basic block */
526 /* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
532 /* ssa_place_phi_functions *****************************************************
534 ls->phi[n][a][p] is created and populated.
536 For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
537 ls->basicblockcount)in which a variable (0 <= a < ls->ssavarcount) is defined an
538 entry in ls->phi[Y][a] is created.
539 This entry is an array with the number of predecessors of Y elements + 1 elements.
540 This elements are all set to the variable a and represent the phi function which
541 will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
543 *******************************************************************************/
546 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
549 bitvector *def_sites;
550 bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
558 W = wl_new(ls->basicblockcount);
560 def_sites = DMNEW(bitvector, ls->ssavarcount);
561 for(a = 0; a < ls->ssavarcount; a++)
562 def_sites[a] = bv_new(ls->basicblockcount);
564 ls->phi = DMNEW(int **, ls->basicblockcount);
565 A_phi = DMNEW(bitvector, ls->basicblockcount);
566 for(i = 0; i < ls->basicblockcount; i++) {
567 ls->phi[i] = DMNEW(int *, ls->ssavarcount);
568 for(j = 0; j < ls->ssavarcount; j++)
569 ls->phi[i][j] = NULL;
570 A_phi[i] = bv_new(ls->ssavarcount);
573 /* copy var_def to def_sites */
574 /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
576 for(n = 0; n <= jd->basicblockcount; n++)
577 for(a = 0; a < ls->ssavarcount; a++)
578 if (bv_get_bit(ls->var_def[n], a))
579 bv_set_bit(def_sites[a], n);
580 #ifdef SSA_DEBUG_VERBOSE
581 if (compileverbose) {
582 printf("var Definitions:\n");
583 for(i = 0; i < ls->ssavarcount; i++) {
584 printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
585 for(j = 0; j < ls->basicblockcount; j++) {
586 if ((j % 5) == 0) printf(" ");
587 if (bv_get_bit(def_sites[i], j))
599 for(a = 0; a < ls->ssavarcount; a++) {
601 /* W<-def_sites(a) */
603 for(n = 0; n < ls->basicblockcount; n++)
604 if (bv_get_bit(def_sites[a],n)) {
608 while (!wl_is_empty(W)) { /* W not empty */
611 for(i = 0; i < dd->num_DF[n]; i++) {
613 /* Node Y is in Dominance Frontier of n -> */
614 /* insert phi function for a at top of Y*/
615 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
616 if (bv_get_bit( A_phi[Y], a) == 0) {
617 /* a is not a Element of A_phi[Y] */
618 /* a <- phi(a,a...,a) to be inserted at top of Block Y */
619 /* phi has as many arguments, as Y has predecessors */
622 /* do not add a phi function for interface stackslots */
623 /* if a predecessor is not a def site of a <==> */
624 /* the block does not have the corresponding inslot*/
626 /* if ((ls->var_to_index[a] >= 0) || */
627 /* (bv_get_bit(def_sites[a], */
628 /* graph_get_first_predecessor(gd, Y, &iter)))) */
631 /* for interface stackslots add a phi function only */
632 /* if the basicblock has the corresponding incoming */
633 /* stackslot -> it could be, that the stackslot is */
634 /* not live anymore at Y */
637 num_pred = graph_get_num_predecessor(gd, Y);
638 ls->phi[Y][a] = DMNEW(int, num_pred + 1);
639 for (j = 0; j < num_pred + 1; j++)
640 ls->phi[Y][a][j] = a;
641 /* increment the number of definitions of a by one */
642 /* for this phi function */
645 bv_set_bit(A_phi[Y], a);
646 if (bv_get_bit(ls->var_def[Y],a)==0) {
647 /* Iterated Dominance Frontier Criterion:*/
648 /* if Y had no definition for a insert it*/
649 /* into the Worklist, since now it */
650 /* defines a through the phi function */
659 /* ssa_rename ******************************************************************
661 Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
662 has only one definition (SSA form).
664 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
665 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
666 definition of each old var.
667 ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
670 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
671 ls->varcount_with_indices.
673 jd->var and jd->varcount will be set for this renamed vars.
675 *******************************************************************************/
677 void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
679 int i, mi, l, j, p, t;
681 methoddesc *md = jd->m->parseddesc;
688 ssa_rename_init(jd, gd);
690 /* Consider definition of Local Vars initialized with Arguments */
692 /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
693 for (p = 0, l= 0; p < md->paramcount; p++) {
694 t = md->paramtypes[p].type;
696 i = jd->local_map[mi];
698 if (IS_2_WORD_TYPE(t))
702 /* !!!!! locals are now numbered as the parameters !!!! */
703 /* !!!!! no additional increment for 2 word types !!!!! */
704 /* this happens later on! here we still need the increment */
705 /* index of var can be in the range from 0 up to not including */
708 /* ignore return value, since first definition gives 0 -> */
709 /* no rename necessary */
711 i = ls->new_varindex[i];
712 j = ssa_rename_def_(ls, i);
714 jd->local_map[mi] = i;
716 ssa_rename_(jd, gd, dd, 0);
719 /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
720 /* if there is no use of the defined Var itself by the phi function */
721 /* for a loop path, in which this var is not used, it will not be life */
722 /* in this path and overwritten! */
724 /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
725 /* this happens if the phi function is the first definition of x or in a */
726 /* path with a backedge xi has no definition */
727 /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
728 /* this phi function would otherwise "deadlock" the dead code elemination */
729 /* invalidate means set it to ls->max_vars_with_indices */
730 /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
731 /* [1,n] can be removed */
733 for(i = 0; i < ls->ssavarcount; i++) {
734 for(t = 0; t < ls->basicblockcount; t++) {
735 if (ls->phi[t][i] != 0) {
737 for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
738 if (ls->phi[t][i][0] == ls->phi[t][i][p])
739 ls->phi[t][i][p] = ls->varcount_with_indices;
745 ls->phi[t][i] = NULL;
750 #if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
751 # if defined(SSA_DEBUG_VERBOSE)
752 if (compileverbose) {
753 printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
754 if (jd->isleafmethod)
755 printf("**Leafmethod**");
759 if (strcmp(jd->m->class->name->text,"fp")==0)
760 if (strcmp(jd->m->name->text,"testfloat")==0)
761 # if defined(SSA_DEBUG_VERBOSE)
763 printf("12-------------------12\n");
765 { int dummy=1; dummy++; }
768 /* recreate rd->locals[][] */
769 /* now only one (local_index/type) pair exists anymore */
770 /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
771 /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
773 new_vars = DMNEW(varinfo, ls->vartop);
774 for(i = 0; i < ls->vartop ; i++)
775 new_vars[i].type = UNUSED;
776 for(i = 0; i < jd->varcount; i++) {
777 p = ls->new_varindex[i];
779 if (p < ls->ssavarcount)
781 new_vars[p].type = VAR(i)->type;
782 new_vars[p].flags = VAR(i)->flags;
783 ls->lifetime[p].v_index = p;
784 ls->lifetime[p].type = VAR(i)->type;
788 /* take care of newly indexed local & in/out vars */
790 for(i = 0; i < ls->ssavarcount; i++) {
792 type = new_vars[j].type;
793 flags = new_vars[j].flags;
795 for (; j < ls->var_0[i + 1]; j++) {
796 new_vars[j].type = type;
797 new_vars[j].flags = flags;
798 ls->lifetime[j].v_index = j;
799 ls->lifetime[j].type = type;
803 #ifdef SSA_DEBUG_VERBOSE
804 if (compileverbose) {
806 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
808 for(i = 0; i < jd->varcount; i++) {
809 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
810 ssa_show_variable(jd, i, VAR(i),0);
811 j = ls->new_varindex[i];
812 if ((j != UNUSED) && (j < ls->ssavarcount))
813 printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
815 printf(" -> %3i", j);
822 jd->varcount = ls->vartop;
823 jd->vartop = ls->vartop;
825 #ifdef SSA_DEBUG_VERBOSE
826 if (compileverbose) {
827 printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
829 for(i = 0; i < jd->varcount; i++) {
830 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
831 ssa_show_variable(jd, i, VAR(i),0);
838 /* ssa_rename_init *************************************************************
840 Setup the data structure for ssa_rename
842 ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
843 ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
844 definition of each old var.
845 ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
848 All other vars (TEMPVAR and PREALLOC) will get a new unique index above
849 ls->varcount_with_indices.
851 jd->var and jd->varcount will be set for this renamed vars.
853 *******************************************************************************/
855 void ssa_rename_init(jitdata *jd, graphdata *gd)
862 /* set up new locals */
863 /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
864 /* for locals and iovars */
866 /* ls->num_defs[index] gives the number of indizes which will be created */
869 /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
870 /* ls->var_0[X] will point to each LX(0) */
871 /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
873 /* as first step cummulate the num_defs array for locals and iovars */
874 /* last element is the maximum var count */
876 ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
878 ls->varcount_with_indices = 0;
879 for(i = 0; i < ls->ssavarcount; i++) {
880 ls->varcount_with_indices += ls->num_defs[i];
881 ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
885 /* Change the var indices in phi from La to La(0) */
887 for(i = 0; i < ls->basicblockcount; i++)
888 for (a = 0; a < ls->ssavarcount; a++)
889 if (ls->phi[i][a] != NULL)
890 for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
891 ls->phi[i][a][p] = ls->var_0[a];
896 ls->count = DMNEW(int, max(1, ls->ssavarcount));
897 ls->stack = DMNEW(int *, max(1, ls->ssavarcount));
898 ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
899 for(a = 0; a < ls->ssavarcount; a++) {
901 ls->stack_top[a] = 0;
903 /* stack a has to hold number of defs of a Elements + 1 */
905 ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
906 ls->stack[a][ls->stack_top[a]++] = 0;
909 if (ls->ssavarcount > 0) {
911 /* Create the num_var_use Array */
913 ls->num_var_use = DMNEW(int *, ls->basicblockcount);
914 for(i = 0; i < ls->basicblockcount; i++) {
915 ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
916 for(a = 0; a < ls->varcount_with_indices; a++)
917 ls->num_var_use[i][a] = 0;
920 /* Create the use_sites Array of Bitvectors*/
921 /* use max(1,..), to ensure that the array is created! */
923 ls->use_sites = DMNEW(bitvector, max(1, ls->varcount_with_indices));
924 for(a = 0; a < ls->varcount_with_indices; a++)
925 ls->use_sites[a] = bv_new(ls->basicblockcount);
929 /* count number of TEMPVARs */
931 ls->lifetimecount = 0;
932 for(i = 0; i < jd->varcount; i++)
933 if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
936 ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
938 ls->lifetimecount = ls->varcount;
939 ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
940 ls->lt_used = DMNEW(int, ls->lifetimecount);
941 ls->lt_int = DMNEW(int, ls->lifetimecount);
942 ls->lt_int_count = 0;
943 ls->lt_flt = DMNEW(int, ls->lifetimecount);
944 ls->lt_flt_count = 0;
945 ls->lt_mem = DMNEW(int, ls->lifetimecount);
946 ls->lt_mem_count = 0;
947 for (i=0; i < ls->lifetimecount; i++) {
948 ls->lifetime[i].type = UNUSED;
949 ls->lifetime[i].savedvar = 0;
950 ls->lifetime[i].flags = 0;
951 ls->lifetime[i].usagecount = 0;
952 ls->lifetime[i].bb_last_use = -1;
953 ls->lifetime[i].bb_first_def = -1;
954 ls->lifetime[i].use = NULL;
955 ls->lifetime[i].def = NULL;
956 ls->lifetime[i].last_use = NULL;
959 /* for giving TEMP and PREALLOC vars a new unique index */
961 ls->vartop = ls->varcount_with_indices;
963 #ifdef SSA_DEBUG_VERBOSE
964 if (compileverbose) {
965 printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
967 for(i = 0; i < jd->varcount; i++) {
968 if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
969 printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
970 ssa_show_variable(jd, i, VAR(i),0);
971 if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
972 printf(" -> %3i", ls->new_varindex[i]);
977 ssa_print_phi(ls, gd);
982 int ssa_rename_def_(lsradata *ls, int a) {
985 _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
987 i = ls->count[a] - 1;
988 /* push i on stack[a] */
989 _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
990 ls->stack[a][ls->stack_top[a]++] = i;
994 int ssa_rename_def(jitdata *jd, int *def_count, int a) {
1000 a1 = ls->new_varindex[a];
1001 _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1002 if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1003 /* local or inoutvar -> normal ssa renaming */
1004 _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
1005 /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
1008 i = ssa_rename_def_(ls, a1);
1009 ret = ls->var_0[a1] + i;
1012 /* TEMP or PREALLOC var */
1014 ls->new_varindex[a] = ls->vartop;
1017 _SSA_ASSERT( ls->vartop < ls->varcount);
1025 void ssa_rename_use_(lsradata *ls, int n, int a) {
1026 _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
1027 if (ls->ssavarcount > 0) {
1028 bv_set_bit(ls->use_sites[a], n);
1029 ls->num_var_use[n][a]++;
1033 int ssa_rename_use(lsradata *ls, int n, int a) {
1037 a1 = ls->new_varindex[a];
1038 _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
1039 if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
1040 /* local or inoutvar -> normal ssa renaming */
1041 /* i <- top(stack[a]) */
1043 _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
1044 i = ls->stack[a1][ls->stack_top[a1] - 1];
1045 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
1047 ret = ls->var_0[a1] + i;
1050 /* TEMP or PREALLOC var */
1052 ls->new_varindex[a] = ls->vartop;
1055 _SSA_ASSERT( ls->vartop < ls->varcount);
1064 #ifdef SSA_DEBUG_VERBOSE
1065 void ssa_rename_print(instruction *iptr, char *op, int from, int to) {
1066 if (compileverbose) {
1067 printf("ssa_rename_: ");
1069 printf("%s ", opcode_names[iptr->opc]);
1073 printf("%s: %3i->%3i\n", op, from, to);
1078 void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
1079 int a, i, j, k, iindex, Y, v;
1082 /* [0..ls->varcount[ Number of Definitions of this var in this */
1083 /* Basic Block. Used to remove the entries off the stack at the */
1084 /* end of the function */
1086 s4 *in, *out, *argp;
1087 graphiterator iter_succ, iter_pred;
1088 struct lifetime *lt;
1092 builtintable_entry *bte;
1098 #ifdef SSA_DEBUG_VERBOSE
1100 printf("ssa_rename_: BB %i\n",n);
1103 _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
1105 def_count = DMNEW(int, max(1, ls->ssavarcount));
1106 for(i = 0; i < ls->ssavarcount; i++)
1109 /* change Store of possible phi functions from a to ai*/
1111 for(a = 0; a < ls->ssavarcount; a++)
1112 if (ls->phi[n][a] != NULL) {
1114 /* do not mark this store as use - maybee this phi function */
1115 /* can be removed for unused Vars*/
1116 j = ls->var_0[a] + ssa_rename_def_(ls, a);
1117 #ifdef SSA_DEBUG_VERBOSE
1118 ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
1120 ls->phi[n][a][0] = j;
1123 in = ls->basicblocks[n]->invars;
1124 in_d = ls->basicblocks[n]->indepth - 1;
1126 /* change use of instack Interface stackslots except top SBR and EXH */
1129 if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
1130 (ls->basicblocks[n]->type == BBTYPE_SBR)) {
1133 /* out = ls->basicblocks[n]->outvars; */
1134 /* out_d = ls->basicblocks[n]->outdepth - 1; */
1136 /* for(; out_d > in_d; out_d--); */
1138 for (; in_d >= 0; in_d--) {
1139 /* Possible Use of ls->new_varindex[jd->var[in_d]] */
1140 _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
1142 a = ls->new_varindex[in[in_d]];
1143 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1145 /* i <- top(stack[a]) */
1147 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1148 i = ls->stack[a][ls->stack_top[a]-1];
1149 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1151 /* Replace use of x with xi */
1153 #ifdef SSA_DEBUG_VERBOSE
1154 ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
1156 in[in_d] = ls->var_0[a] + i;
1157 lt = ls->lifetime + in[in_d];
1159 lt->v_index = in[in_d];
1160 lt->bb_last_use = -1;
1163 iptr = ls->basicblocks[n]->iinstr;
1165 for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
1167 /* check for use (s1, s2, s3 or special (argp) ) */
1169 switch (icmd_table[iptr->opc].dataflow) {
1171 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1172 j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
1173 #ifdef SSA_DEBUG_VERBOSE
1174 ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
1176 iptr->sx.s23.s3.varindex = j;
1178 /* now "fall through" for handling of s2 and s1 */
1181 case DF_2_TO_1: /* icmd has s1 and s2 */
1182 j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
1183 #ifdef SSA_DEBUG_VERBOSE
1184 ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
1186 iptr->sx.s23.s2.varindex = j;
1188 /* now "fall through" for handling of s1 */
1194 j = ssa_rename_use(ls, n, iptr->s1.varindex);
1195 #ifdef SSA_DEBUG_VERBOSE
1196 ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
1198 iptr->s1.varindex = j;
1204 /* do not use md->paramcount, pass-through stackslots have */
1205 /* to be renamed, too */
1206 i = iptr->s1.argcount;
1207 argp = iptr->sx.s23.s2.args;
1209 j = ssa_rename_use(ls, n, *argp);
1210 #ifdef SSA_DEBUG_VERBOSE
1211 ssa_rename_print( iptr, "arg", *argp, j);
1220 /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
1221 /* an optional dst - so they to be checked first */
1224 if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
1225 INSTRUCTION_GET_METHODDESC(iptr,md);
1226 if (md->returntype.type != TYPE_VOID)
1227 v = iptr->dst.varindex;
1229 else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
1230 bte = iptr->sx.s23.s3.bte;
1232 if (md->returntype.type != TYPE_VOID)
1233 v = iptr->dst.varindex;
1235 else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
1236 v = iptr->dst.varindex;
1240 j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
1241 #ifdef SSA_DEBUG_VERBOSE
1242 ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
1244 iptr->dst.varindex = j;
1247 /* ?????????????????????????????????????????????????????????? */
1248 /* Mark Def as use, too. Since param initialisation is in */
1249 /* var_def and this would not remove this locals, if not used */
1251 /* ?????????????????????????????????????????????????????????? */
1255 /* change outstack Interface stackslots */
1256 out = ls->basicblocks[n]->outvars;
1257 out_d = ls->basicblocks[n]->outdepth - 1;
1259 for (;out_d >= 0; out_d--) {
1260 /* Possible Use of ls->new_varindex[jd->var[out_d]] */
1261 _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
1263 a = ls->new_varindex[out[out_d]];
1264 _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
1266 /* i <- top(stack[a]) */
1268 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1269 i = ls->stack[a][ls->stack_top[a]-1];
1270 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1272 /* Replace use of x with xi */
1274 #ifdef SSA_DEBUG_VERBOSE
1275 ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
1277 out[out_d] = ls->var_0[a] + i;
1278 lt = ls->lifetime + out[out_d];
1280 lt->v_index = out[out_d];
1281 lt->bb_last_use = -1;
1284 /* change use in phi Functions of Successors */
1286 Y = graph_get_first_successor(gd, n, &iter_succ);
1287 for(; Y != -1; Y = graph_get_next(&iter_succ)) {
1288 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
1289 k = graph_get_first_predecessor(gd, Y, &iter_pred);
1290 for (j = 0; (k != -1) && (k != n); j++)
1291 k = graph_get_next(&iter_pred);
1292 _SSA_ASSERT(k == n);
1294 /* n is jth Predecessor of Y */
1296 for(a = 0; a < ls->ssavarcount; a++)
1297 if (ls->phi[Y][a] != NULL) {
1299 /* i <- top(stack[a]) */
1301 if (ls->stack_top[a] == 1) {
1302 /* no definition till now in controll flow */
1303 #ifdef SSA_DEBUG_VERBOSE
1304 if (compileverbose) {
1305 printf("Succ %3i Arg %3i \n", Y, j);
1306 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
1309 ls->phi[Y][a][j+1] = UNUSED;
1312 _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
1313 i = ls->stack[a][ls->stack_top[a]-1];
1314 _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
1316 /* change jth operand from a0 to ai */
1318 i = ls->var_0[a] + i;
1319 #ifdef SSA_DEBUG_VERBOSE
1320 if (compileverbose) {
1321 printf("Succ %3i Arg %3i \n", Y, j);
1322 ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
1325 ls->phi[Y][a][j+1] = i;
1326 _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
1327 ls->varcount_with_indices);
1329 /* use by phi function has to be remembered, too */
1331 ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
1334 /* ????????????????????????????????????????????? */
1335 /* why was this only for local vars before ? */
1336 /* ????????????????????????????????????????????? */
1341 /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
1342 for(i = 0; i < ls->basicblockcount; i++)
1343 if (dd->idom[i] == n)
1344 ssa_rename_(jd, gd, dd, i);
1346 /* pop Stack[a] for each definition of a var a in the original S */
1347 for(a = 0; a < ls->ssavarcount; a++) {
1348 ls->stack_top[a] -= def_count[a];
1349 _SSA_ASSERT(ls->stack_top[a] >= 0);
1355 #ifdef SSA_DEBUG_VERBOSE
1356 void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
1362 printf("ssa_printtrees: maxlocals %3i", jd->localcount);
1364 printf("Dominator Tree: \n");
1365 for(i = 0; i < ls->basicblockcount; i++) {
1367 for(j = 0; j < ls->basicblockcount; j++) {
1368 if (dd->idom[j] == i) {
1375 printf("Dominator Forest:\n");
1376 for(i = 0; i < ls->basicblockcount; i++) {
1378 for(j = 0; j < dd->num_DF[i]; j++) {
1379 printf(" %3i", dd->DF[i][j]);
1384 if (ls->ssavarcount > 0) {
1385 printf("Use Sites\n");
1386 for(i = 0; i < ls->ssavarcount; i++) {
1387 printf("use_sites[%3i]=%p:",i,(void *)ls->use_sites[i]);
1388 for(j = 0; j < ls->basicblockcount; j++) {
1389 if ((j % 5) == 0) printf(" ");
1390 if (bv_get_bit(ls->use_sites[i], j))
1399 printf("var Definitions:\n");
1400 for(i = 0; i < jd->basicblockcount; i++) {
1401 printf("var_def[%3i]=%p:",i,(void *)ls->var_def[i]);
1402 for(j = 0; j < ls->ssavarcount; j++) {
1403 if ((j % 5) == 0) printf(" ");
1404 if (bv_get_bit(ls->var_def[i], j))
1410 for(j=0; j < ((((ls->ssavarcount * 5+7)/8) + sizeof(int) - 1)/sizeof(int));
1412 printf("%8x",ls->var_def[i][j]);
1417 void ssa_print_phi(lsradata *ls, graphdata *gd) {
1420 printf("phi Functions (varcount_with_indices: %3i):\n",
1421 ls->varcount_with_indices);
1422 for(i = 0; i < ls->basicblockcount; i++) {
1423 for(j = 0; j < ls->ssavarcount; j++) {
1424 if (ls->phi[i][j] != NULL) {
1425 printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
1426 for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
1427 printf("%3i ",ls->phi[i][j][k]);
1437 void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
1444 /* count moves to be inserted at the end of each block in moves[] */
1445 ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
1446 for(i = 0; i < ls->basicblockcount; i++)
1447 ls->num_phi_moves[i] = 0;
1448 for(i = 0; i < ls->basicblockcount; i++)
1449 for(a = 0; a < ls->ssavarcount; a++)
1450 if (ls->phi[i][a] != NULL) {
1452 if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
1453 /* Var defined (only <- SSA Form!) in this phi function */
1454 /* and not used anywhere -> delete phi function and set */
1457 /* TODO: first delete use sites of arguments of phi */
1459 VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
1460 ls->lifetime[ls->phi[i][a][0]].def = NULL;
1461 ls->phi[i][a] = NULL;
1466 pred = graph_get_first_predecessor(gd, i, &iter);
1467 for(; pred != -1; pred = graph_get_next(&iter)) {
1468 ls->num_phi_moves[pred]++;
1473 /* allocate ls->phi_moves */
1474 ls->phi_moves = DMNEW( int **, ls->basicblockcount);
1475 for(i = 0; i < ls->basicblockcount; i++) {
1476 ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
1477 for(j = 0; j <ls->num_phi_moves[i]; j++)
1478 ls->phi_moves[i][j] = DMNEW(int, 2);
1479 #ifdef SSA_DEBUG_VERBOSE
1481 printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
1482 i, ls->num_phi_moves[i]);
1486 /* populate ls->phi_moves */
1487 for(i = 0; i < ls->basicblockcount; i++)
1488 ls->num_phi_moves[i] = 0;
1489 for(i = 0; i < ls->basicblockcount; i++)
1490 for(a = 0; a < ls->ssavarcount; a++)
1491 if (ls->phi[i][a] != NULL) {
1492 pred = graph_get_first_predecessor(gd, i, &iter);
1493 for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
1494 /* target is phi[i][a][0] */
1495 /* source is phi[i][a][j+1] */
1496 if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
1498 if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
1499 ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
1501 ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
1509 /****************************************************************************
1511 ****************************************************************************/
1514 /****************************************************************************
1515 Dead Code Elimination
1516 ****************************************************************************/
1517 void dead_code_elimination(jitdata *jd, graphdata *gd) {
1522 struct lifetime *lt, *s_lt;
1524 bool remove_statement;
1528 #ifdef SSA_DEBUG_VERBOSE
1535 W = wl_new(ls->lifetimecount);
1536 if (ls->lifetimecount > 0) {
1537 /* put all lifetimes on Worklist */
1538 for(a = 0; a < ls->lifetimecount; a++) {
1539 if (ls->lifetime[a].type != -1) {
1545 /* Remove unused lifetimes */
1546 while(!wl_is_empty(W)) {
1547 /* take a var out of Worklist */
1550 lt = &(ls->lifetime[a]);
1551 if ((lt->def == NULL) || (lt->type == -1))
1552 /* lifetime was already removed -> no defs anymore */
1555 /* Remove lifetimes, which are only used in a phi function, which
1557 remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
1558 for(use = lt->use; (remove_statement && (use != NULL));
1561 remove_statement = remove_statement &&
1562 (use->b_index == lt->def->b_index) &&
1563 (use->iindex == lt->def->iindex);
1565 if (remove_statement) {
1566 #ifdef SSA_DEBUG_CHECK
1567 /* def == use can only happen in phi functions */
1568 if (remove_statement)
1569 _SSA_ASSERT(lt->use->iindex < 0);
1571 /* give it free for removal */
1575 if (lt->use == NULL) {
1576 /* Look at statement of definition of a and remove it, */
1577 /* if the Statement has no sideeffects other than the assignemnt */
1579 if (lt->def->iindex < 0 ) {
1581 /* delete use of sources , delete phi functions */
1583 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] !=
1586 for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
1590 ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1591 if ((source != ls->varcount_with_indices) &&
1592 (source != lt->v_index)) {
1594 /* phi Argument was not already removed (already in
1595 because of selfdefinition) */
1597 s_lt = &(ls->lifetime[source]);
1601 lt_remove_use_site(s_lt,lt->def->b_index,
1604 /* put it on the Worklist */
1609 /* now delete phi function itself */
1610 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1612 /* "normal" Use by ICMD */
1613 remove_statement = false;
1614 if (lt->def->b_index != 0) {
1616 /* do not look at artificial block 0 (parameter init) */
1618 iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1621 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
1622 remove_statement = false;
1624 /* if ICMD could throw an exception do not remove it! */
1628 /* ICMD_INVOKE*, ICMD_BUILTIN and ICMD_MULTIANEWARRAY */
1629 /* have possible sideeffects -> do not remove them */
1631 /* remove_statement = !(ICMD_HAS_SPECIAL(iptr->opc)); */
1633 remove_statement = !(
1634 (icmd_table[iptr->opc].dataflow == DF_INVOKE) ||
1635 (icmd_table[iptr->opc].dataflow == DF_BUILTIN) ||
1636 (icmd_table[iptr->opc].dataflow == DF_N_TO_1));
1638 if (remove_statement) {
1639 switch (icmd_table[iptr->opc].dataflow) {
1641 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1642 a = iptr->sx.s23.s3.varindex;
1643 s_lt = ls->lifetime + a;
1644 lt_remove_use_site(s_lt, lt->def->b_index,
1648 /* now "fall through" for handling of s2 and s1 */
1651 case DF_2_TO_1: /* icmd has s1 and s2 */
1652 a = iptr->sx.s23.s2.varindex;
1653 s_lt = ls->lifetime + a;
1654 lt_remove_use_site(s_lt, lt->def->b_index,
1658 /* now "fall through" for handling of s1 */
1664 a = iptr->s1.varindex;
1665 s_lt = ls->lifetime + a;
1666 lt_remove_use_site(s_lt, lt->def->b_index,
1673 if (remove_statement) {
1675 /* remove statement */
1677 #ifdef SSA_DEBUG_VERBOSE
1679 printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
1680 m->class->name->text, m->name->text,
1681 lt->def->b_index, lt->def->iindex,
1682 icmd_table[iptr->opc].name);
1684 iptr->opc = ICMD_NOP;
1686 } /* (lt->def->b_index != 0) */
1687 } /* if (lt->def->iindex < 0 ) else */
1689 /* remove definition of a */
1691 VAR(lt->v_index)->type = -1;
1694 } /* if (lt->use == NULL) */
1695 } /* while(!wl_is_empty(W)) */
1696 } /* dead_code_elimination */
1698 /****************************************************************************
1699 Simple Constant Propagation
1700 ****************************************************************************/
1702 void simple_constant_propagation() {
1705 /****************************************************************************
1707 *******************************************************************************/
1708 void copy_propagation(jitdata *jd, graphdata *gd) {
1715 struct lifetime *lt, *s_lt;
1722 W = wl_new(ls->lifetimecount);
1723 if (ls->lifetimecount > 0) {
1724 /* put all lifetimes on Worklist */
1725 for(a = 0; a < ls->lifetimecount; a++) {
1726 if (ls->lifetime[a].type != -1) {
1732 while(!wl_is_empty(W)) {
1733 /* take a var out of Worklist */
1736 lt = ls->lifetime + a;
1739 _SSA_ASSERT(lt->def != NULL);
1740 _SSA_ASSERT(lt->use != NULL);
1741 if (lt->def->iindex < 0 ) {
1744 /* look, if phi function degenerated to a x = phi(y) */
1745 /* and if so, substitute y for every use of x */
1747 _SSA_ASSERT(ls->phi[lt->def->b_index][-lt->def->iindex-1] != NULL);
1749 only_source = ls->varcount_with_indices;
1750 for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
1752 source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
1753 if (source != ls->varcount_with_indices) {
1754 if (only_source == ls->varcount_with_indices) {
1755 /* first valid source argument of phi function */
1756 only_source = source;
1758 /* second valid source argument of phi function */
1760 only_source = ls->varcount_with_indices;
1765 if (only_source != ls->varcount_with_indices) {
1767 /* replace all use sites of lt with the var_index only_source */
1769 ssa_replace_use_sites( jd, gd, lt, only_source, W);
1771 /* delete def of lt and replace uses of lt with "only_source" */
1773 ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
1775 s_lt = ls->lifetime + only_source;
1777 VAR(lt->v_index)->type = -1;
1778 lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
1780 /* move use sites from lt to s_lt */
1781 lt_move_use_sites(lt, s_lt);
1783 } /* if (only_source != ls->varcount_with_indices) */
1784 } else { /* if (lt->def->iindex < 0 )*/
1785 /* def in "normal" ICMD */
1787 iptr = ls->basicblocks[lt->def->b_index]->iinstr +
1791 if (lt->def->b_index == 0)
1800 if (lt->def->iindex == 0) {
1801 /* first instruction in bb -> instack==bb->instack */
1802 in = ls->basicblocks[lt->def->b_index]->instack;
1804 /* instack is (iptr-1)->dst */
1808 if (in->varkind != LOCALVAR) {
1809 #ifdef SSA_DEBUG_VERBOSE
1811 printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
1813 s_lt = &(ls->lifetime[-in->varnum-1]);
1815 for (ss = s_lt->local_ss; ss != NULL; ss = ss->next) {
1816 ss->s->varkind = LOCALVAR;
1817 ss->s->varnum = iptr->op1;
1820 /* replace all use sites of s_lt with the var_index */
1823 ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
1825 /* s_lt->def is the new def site of lt */
1826 /* the old ->def site will get a use site of def */
1827 /* only one def site */
1828 _SSA_ASSERT(lt->def->next == NULL);
1829 _SSA_ASSERT(s_lt->def != NULL);
1830 _SSA_ASSERT(s_lt->def->next == NULL);
1832 /* replace def of s_lt with iptr->op1 */
1833 if (s_lt->def->iindex < 0) {
1835 _SSA_ASSERT(ls->phi[s_lt->def->b_index]
1836 [-s_lt->def->iindex-1]
1838 ls->phi[s_lt->def->b_index][-s_lt->def->iindex-1][0]
1841 if (in->varnum != iptr->op1)
1842 printf("copy propagation: LOCALVAR ss->ISTORE BB %i II %i\n",
1843 lt->def->b_index, lt->def->iindex);
1846 /* move def to use sites of lt */
1847 lt->def->next = lt->use;
1850 lt->def = s_lt->def;
1855 /* move use sites from s_lt to lt */
1856 move_use_sites(s_lt, lt);
1857 move_stackslots(s_lt, lt);
1863 /* Def Interface Stackslot */
1871 only_source = lt->local_ss->s->varnum;
1872 if (lt->local_ss->s->varkind != LOCALVAR) {
1873 #ifdef SSA_DEBUG_VERBOSE
1875 printf("copy propagation xload: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, lt->local_ss->s->varnum);
1877 _SSA_ASSERT(iptr->dst->varnum == lt->local_ss->s->varnum);
1878 for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
1879 ss->s->varkind = LOCALVAR;
1880 ss->s->varnum = iptr->op1;
1883 /* replace all use sites of lt with the var_index iptr->op1*/
1885 ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
1889 s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
1891 /* move use sites from lt to s_lt */
1892 move_use_sites(lt, s_lt);
1893 move_stackslots(lt, s_lt);
1896 if (lt->local_ss->s->varnum != iptr->op1)
1897 printf("copy propagation: ILOAD -> LOCALVAR ss BB %i II %i\n",
1898 lt->def->b_index, lt->def->iindex);
1902 } /* localvar or interface stackslot */
1904 } /* i(lt->def->iindex < 0 ) */
1906 } /* while(!wl_is_empty(W)) */
1909 void ssa_replace_use_sites(jitdata *jd, graphdata *gd, struct lifetime *lt,
1910 int new_v_index, worklist *W) {
1917 builtintable_entry *bte;
1921 md = jd->m->parseddesc;
1924 for(s = lt->use; s != NULL; s = s->next) {
1925 if (s->iindex < 0) {
1927 /* Use in phi function */
1929 for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
1930 source = ls->phi[s->b_index][-s->iindex-1][i];
1931 if (source == lt->v_index) {
1932 #ifdef SSA_DEBUG_VERBOSE
1935 printf("copy propagation phi: BB %3i I %3i: %3i -> \
1936 %3i\n", s->b_index, s->iindex,
1937 new_v_index, source);
1940 ls->phi[s->b_index][-s->iindex-1][i]
1946 /* Add var, which is defined by this phi function to */
1949 source = ls->phi[s->b_index][-s->iindex-1][0];
1953 else { /* use in ICMD */
1955 iptr = ls->basicblocks[s->b_index]->iinstr +
1958 /* check for use (s1, s2, s3 or special (argp) ) */
1961 switch (icmd_table[iptr->opc].dataflow) {
1963 case DF_3_TO_1: /* icmd has s1, s2 and s3 */
1964 if (iptr->sx.s23.s3.varindex == lt->v_index) {
1965 #ifdef SSA_DEBUG_VERBOSE
1968 printf("copy propagation loc: BB %3i I %3i: %3i -> \
1969 %3i\n", s->b_index, s->iindex,
1970 new_v_index, iptr->sx.s23.s3.varindex);
1973 iptr->sx.s23.s3.varindex = new_v_index;
1976 /* now "fall through" for handling of s2 and s1 */
1979 case DF_2_TO_1: /* icmd has s1 and s2 */
1980 if (iptr->sx.s23.s2.varindex == lt->v_index) {
1981 #ifdef SSA_DEBUG_VERBOSE
1984 printf("copy propagation loc: BB %3i I %3i: %3i -> \
1985 %3i\n", s->b_index, s->iindex,
1986 new_v_index, iptr->sx.s23.s2.varindex);
1989 iptr->sx.s23.s2.varindex = new_v_index;
1992 /* now "fall through" for handling of s1 */
1998 if (iptr->s1.varindex == lt->v_index) {
1999 #ifdef SSA_DEBUG_VERBOSE
2002 printf("copy propagation loc: BB %3i I %3i: %3i -> \
2003 %3i\n", s->b_index, s->iindex,
2004 new_v_index, iptr->s1.varindex);
2007 iptr->s1.varindex = new_v_index;
2012 /* ? really look at md->paramcount or iptr->s1.argcount */
2013 /* has to be taken, so that pass-through stackslots get */
2017 INSTRUCTION_GET_METHODDESC(iptr,md);
2021 bte = iptr->sx.s23.s3.bte;
2026 i = iptr->s1.argcount;
2030 argp = iptr->sx.s23.s2.args;
2032 if (*argp == lt->v_index) {
2033 #ifdef SSA_DEBUG_VERBOSE
2037 "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
2038 , s->b_index, s->iindex, new_v_index, *argp);
2041 *argp = new_v_index;
2048 } /* if (s->iindex < 0) */
2049 } /* for(s = lt->use; s != NULL; s = s->next) */
2052 #ifdef SSA_DEBUG_VERBOSE
2053 void ssa_print_lt(lsradata *ls) {
2055 struct lifetime *lt;
2058 printf("SSA LT Def/Use\n");
2059 for(i = 0; i < ls->lifetimecount; i++) {
2060 lt = ls->lifetime + i;
2061 if (lt->type != UNUSED) {
2062 printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
2063 if (lt->def != NULL)
2064 printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
2066 printf("%3i,%3i Use: ",0,0);
2067 for(use = lt->use; use != NULL; use = use->next)
2068 printf("%3i,%3i ",use->b_index, use->iindex);
2074 void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage)
2080 case TYPE_INT: type = 'i'; break;
2081 case TYPE_LNG: type = 'l'; break;
2082 case TYPE_FLT: type = 'f'; break;
2083 case TYPE_DBL: type = 'd'; break;
2084 case TYPE_ADR: type = 'a'; break;
2085 case TYPE_RET: type = 'r'; break;
2086 default: type = '?';
2089 if (index < jd->localcount) {
2091 if (v->flags & (PREALLOC | INOUT))
2092 printf("<INVALID FLAGS!>");
2095 if (v->flags & PREALLOC) {
2097 if (v->flags & INOUT)
2098 printf("<INVALID FLAGS!>");
2100 else if (v->flags & INOUT)
2106 printf("%c%c%3d", kind, type, index);
2108 if (v->flags & SAVEDVAR)
2116 /****************************************************************************
2118 ****************************************************************************/
2121 * These are local overrides for various environment variables in Emacs.
2122 * Please do not remove this and leave it at the end of the file, where
2123 * Emacs will automagically detect them.
2124 * ---------------------------------------------------------------------
2127 * indent-tabs-mode: t