1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
3 Copyright (C) 2005 - 2007 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
36 #include "mm/memory.h"
38 #include "toolbox/bitvector.h"
39 #include "toolbox/worklist.h"
41 #include "vm/builtin.h"
43 #include "vm/jit/jit.h" /* icmd_table */
45 #include "vm/jit/optimizing/dominators.h"
46 #include "vm/jit/optimizing/graph.h"
47 #include "vm/jit/optimizing/lifetimes.h"
48 #include "vm/jit/optimizing/lsra.h"
49 #include "vm/jit/optimizing/ssa.h"
50 #include "vm/jit/optimizing/ssa_phi.h"
52 #if defined(SSA_DEBUG_VERBOSE)
53 #include "vmcore/options.h" /* compileverbose */
56 /* ssa_place_phi_functions *****************************************************
58 Algorithm is based on "modern compiler implementation in C" from andrew
59 w. appel, edition 2004
62 page 441 Algorithm 19.6. Inserting phi-functions:
66 - if Y not element of A phi [n]
67 + if a not element of A phi [n]
68 insert the statment a <- ...
71 - A phi [n] <- A phi [n] join {Y}
72 + A phi [n] <- A phi [n] join {a}
73 - if Y not element of A orig [n]
74 + if a not element of A orig [Y]
78 ls->phi[n][a][p] is created and populated.
80 n in [0..ls->basicblockcount[
81 a in [0..ls->ssavarcount[
82 p in [1..Count of Predecessors of Basicblock n]
84 For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
85 ls->basicblockcount) in which a variable (0 <= a < ls->ssavarcount) is defined
86 an entry in ls->phi[Y][a] is created.
87 This entry is an array with the number of predecessors of Y elements + 1
89 This elements are all set to the variable a and represent the phi function which
90 will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
93 ls->phi[n][a] == NULL, if no phi function for Variable a for Basicblock n exists
97 ls->phi[n][a][0] == a, representing the result of the phi function and
98 ls->phi[n][a][p] == a, representing the arguments of the phi function.
100 *******************************************************************************/
103 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
106 bitvector *def_sites;
107 bitvector *A_phi; /* [0..ls->basicblockcount[ of */
108 /* ls->ssavarcount Bit */
116 W = wl_new(ls->basicblockcount);
118 def_sites = DMNEW(bitvector, ls->ssavarcount);
119 for(a = 0; a < ls->ssavarcount; a++)
120 def_sites[a] = bv_new(ls->basicblockcount);
122 ls->phi = DMNEW(int **, ls->basicblockcount);
123 A_phi = DMNEW(bitvector, ls->basicblockcount);
124 for(i = 0; i < ls->basicblockcount; i++) {
125 ls->phi[i] = DMNEW(int *, ls->ssavarcount);
126 for(j = 0; j < ls->ssavarcount; j++)
127 ls->phi[i][j] = NULL;
128 A_phi[i] = bv_new(ls->ssavarcount);
131 /* copy var_def to def_sites */
132 /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
134 for(n = 0; n <= jd->basicblockcount; n++)
135 for(a = 0; a < ls->ssavarcount; a++)
136 if (bv_get_bit(ls->var_def[n], a))
137 bv_set_bit(def_sites[a], n);
138 #ifdef SSA_DEBUG_VERBOSE
139 if (compileverbose) {
140 printf("var Definitions:\n");
141 for(i = 0; i < ls->ssavarcount; i++) {
142 printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
143 for(j = 0; j < ls->basicblockcount; j++) {
144 if ((j % 5) == 0) printf(" ");
145 if (bv_get_bit(def_sites[i], j))
157 for(a = 0; a < ls->ssavarcount; a++) {
159 /* W<-def_sites(a) */
161 for(n = 0; n < ls->basicblockcount; n++)
162 if (bv_get_bit(def_sites[a],n)) {
166 while (!wl_is_empty(W)) { /* W not empty */
169 for(i = 0; i < dd->num_DF[n]; i++) {
172 /* Node Y is in Dominance Frontier of n -> */
173 /* insert phi function for a at top of Y*/
175 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
176 if (bv_get_bit( A_phi[Y], a) == 0) {
178 /* a is not a Element of A_phi[Y] */
179 /* a <- phi(a,a...,a) to be inserted at top of Block Y */
180 /* phi has as many arguments, as Y has predecessors */
182 num_pred = graph_get_num_predecessor(gd, Y);
183 ls->phi[Y][a] = DMNEW(int, num_pred + 1);
184 for (j = 0; j < num_pred + 1; j++)
185 ls->phi[Y][a][j] = a;
187 /* increment the number of definitions of a by one */
188 /* for this phi function */
192 bv_set_bit(A_phi[Y], a);
193 if (bv_get_bit(ls->var_def[Y],a)==0) {
195 /* Iterated Dominance Frontier Criterion: */
196 /* if Y had no definition for a, insert it */
197 /* into the Worklist, since now it */
198 /* defines a through the phi function */
208 void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
215 /* count moves to be inserted at the end of each block in moves[] */
217 ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
218 for(i = 0; i < ls->basicblockcount; i++)
219 ls->num_phi_moves[i] = 0;
220 for(i = 0; i < ls->basicblockcount; i++)
221 for(a = 0; a < ls->ssavarcount; a++)
222 if (ls->phi[i][a] != NULL) {
224 if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
225 /* Var defined (only <- SSA Form!) in this phi function */
226 /* and not used anywhere -> delete phi function and set */
229 /* TODO: first delete use sites of arguments of phi */
231 VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
232 ls->lifetime[ls->phi[i][a][0]].def = NULL;
233 ls->phi[i][a] = NULL;
238 pred = graph_get_first_predecessor(gd, i, &iter);
239 for(; pred != -1; pred = graph_get_next(&iter)) {
240 ls->num_phi_moves[pred]++;
245 /* allocate ls->phi_moves */
247 ls->phi_moves = DMNEW( int **, ls->basicblockcount);
248 for(i = 0; i < ls->basicblockcount; i++) {
249 ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
250 for(j = 0; j <ls->num_phi_moves[i]; j++)
251 ls->phi_moves[i][j] = DMNEW(int, 2);
252 #ifdef SSA_DEBUG_VERBOSE
254 printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
255 i, ls->num_phi_moves[i]);
259 /* populate ls->phi_moves */
261 for(i = 0; i < ls->basicblockcount; i++)
262 ls->num_phi_moves[i] = 0;
263 for(i = 0; i < ls->basicblockcount; i++)
264 for(a = 0; a < ls->ssavarcount; a++)
265 if (ls->phi[i][a] != NULL) {
266 pred = graph_get_first_predecessor(gd, i, &iter);
267 for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
268 /* target is phi[i][a][0] */
269 /* source is phi[i][a][j+1] */
270 if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
272 if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
273 ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
275 ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
283 #ifdef SSA_DEBUG_VERBOSE
284 void ssa_print_phi(lsradata *ls, graphdata *gd) {
287 printf("phi Functions (varcount_with_indices: %3i):\n",
288 ls->varcount_with_indices);
289 for(i = 0; i < ls->basicblockcount; i++) {
290 for(j = 0; j < ls->ssavarcount; j++) {
291 if (ls->phi[i][j] != NULL) {
292 printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
293 for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
294 printf("%3i ",ls->phi[i][j][k]);
304 * These are local overrides for various environment variables in Emacs.
305 * Please do not remove this and leave it at the end of the file, where
306 * Emacs will automagically detect them.
307 * ---------------------------------------------------------------------
310 * indent-tabs-mode: t