src/vm/jit/optimizing/ssa_phi.c

   1 /* src/vm/jit/optimizing/ssa.c - static single-assignment form
   2
   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
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: $
  30
  31 */
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35
  36 #include "mm/memory.h"
  37
  38 #include "toolbox/bitvector.h"
  39 #include "toolbox/worklist.h"
  40
  41 #include "vm/builtin.h"
  42
  43 #include "vm/jit/jit.h" /* icmd_table */
  44
  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"
  51
  52 #if defined(SSA_DEBUG_VERBOSE)
  53 #include "vmcore/options.h"   /* compileverbose */
  54 #endif
  55
  56 /* ssa_place_phi_functions *****************************************************
  57
  58 Algorithm is based on "modern compiler implementation in C" from andrew
  59 w. appel, edition 2004
  60
  61 Corrections:
  62 page 441 Algorithm 19.6. Inserting phi-functions:
  63
  64 ...
  65     for each Y in DF[n]
  66 -       if Y not element of A phi [n]
  67 +       if a not element of A phi [n]
  68             insert the statment a <- ...
  69 ...
  70 ...
  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]
  75            W <- W join {Y}
  76
  77
  78 ls->phi[n][a][p] is created and populated.
  79
  80 n in [0..ls->basicblockcount[
  81 a in [0..ls->ssavarcount[
  82 p in [1..Count of Predecessors of Basicblock n]
  83
  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
  88 elements.
  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.
  91
  92
  93 ls->phi[n][a] == NULL, if no phi function for Variable a for Basicblock n exists
  94
  95 or
  96
  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.
  99
 100 *******************************************************************************/
 101
 102
 103 void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
 104 {
 105         int a,i,j,n,Y;
 106         bitvector *def_sites;
 107         bitvector *A_phi;    /* [0..ls->basicblockcount[ of */
 108                              /* ls->ssavarcount Bit         */
 109         worklist *W;
 110         int num_pred;
 111
 112         lsradata *ls;
 113
 114         ls = jd->ls;
 115
 116         W = wl_new(ls->basicblockcount);
 117
 118         def_sites = DMNEW(bitvector, ls->ssavarcount);
 119         for(a = 0; a < ls->ssavarcount; a++)
 120                 def_sites[a] = bv_new(ls->basicblockcount);
 121
 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);
 129         }
 130
 131         /* copy var_def to def_sites */
 132         /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
 133
 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))
 146                                         printf("1");
 147                                 else
 148                                         printf("0");
 149                         }
 150                         printf(" (");
 151
 152                         printf("\n");
 153                 }
 154         }
 155 #endif
 156
 157         for(a = 0; a < ls->ssavarcount; a++) {
 158
 159                 /* W<-def_sites(a) */
 160
 161                 for(n = 0; n < ls->basicblockcount; n++)
 162                         if (bv_get_bit(def_sites[a],n)) {
 163                                 wl_add(W, n);
 164                         }
 165
 166                 while (!wl_is_empty(W)) { /* W not empty */
 167                         n = wl_get(W);
 168
 169                         for(i = 0; i < dd->num_DF[n]; i++) {
 170                                 Y = dd->DF[n][i];
 171
 172                                 /* Node Y is in Dominance Frontier of n -> */
 173                                 /* insert phi function for a at top of Y*/
 174
 175                                 _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
 176                                 if (bv_get_bit( A_phi[Y], a) == 0) {
 177
 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    */
 181
 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;
 186
 187                                         /* increment the number of definitions of a by one */
 188                                         /* for this phi function */
 189
 190                                         ls->num_defs[a]++;
 191
 192                                         bv_set_bit(A_phi[Y], a);
 193                                         if (bv_get_bit(ls->var_def[Y],a)==0) {
 194
 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      */
 199
 200                                                 wl_add(W, Y);
 201                                         }
 202                                 }
 203                         }
 204                 }
 205         }
 206 }
 207
 208 void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
 209         int a, i, j, pred;
 210         graphiterator iter;
 211         lsradata *ls;
 212
 213         ls = jd->ls;
 214
 215         /* count moves to be inserted at the end of each block in moves[] */
 216
 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) {
 223 #if 0
 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 */
 227                                         /* var to unused */
 228
 229                                         /* TODO: first delete use sites of arguments of phi */
 230                                         /* function */
 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;
 234                                 }
 235                                 else
 236 #endif
 237                                         {
 238                                         pred = graph_get_first_predecessor(gd, i, &iter);
 239                                         for(; pred != -1; pred = graph_get_next(&iter)) {
 240                                                 ls->num_phi_moves[pred]++;
 241                                         }
 242                                 }
 243                         }
 244
 245         /* allocate ls->phi_moves */
 246
 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
 253                 if (compileverbose)
 254                         printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
 255                                    i, ls->num_phi_moves[i]);
 256 #endif
 257         }
 258
 259         /* populate ls->phi_moves */
 260
 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) {
 271                                                 /* valid move */
 272                                                 if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
 273                                                         ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
 274                                                                 ls->phi[i][a][0];
 275                                                         ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
 276                                                                 ls->phi[i][a][j+1];
 277                                                 }
 278                                         }
 279                                 }
 280                         }
 281 }
 282
 283 #ifdef SSA_DEBUG_VERBOSE
 284 void ssa_print_phi(lsradata *ls, graphdata *gd) {
 285         int i,j,k;
 286
 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]);
 295                                 printf(")\n");
 296                         }
 297                 }
 298         }
 299
 300 }
 301 #endif
 302
 303 /*
 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  * ---------------------------------------------------------------------
 308  * Local variables:
 309  * mode: c
 310  * indent-tabs-mode: t
 311  * c-basic-offset: 4
 312  * tab-width: 4
 313  * End:
 314  */