src/vm/jit/optimizing/dominators.c

   1 /* src/vm/jit/optimizing/dominators.c - dominators and dominance frontier
   2
   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
   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
  30 */
  31 #include "mm/memory.h"
  32
  33 #include "toolbox/bitvector.h"
  34
  35 #include "vm/jit/jit.h"
  36
  37 #include "vm/jit/optimizing/graph.h"
  38 #include "vm/jit/optimizing/dominators.h"
  39
  40 /* function prototypes */
  41 void dom_Dominators_init(dominatordata *dd, int basicblockcount);
  42 #ifdef DOM_DEBUG_CHECK
  43 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount);
  44 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount);
  45 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N,
  46                          int basicblockcount);
  47 #else
  48 int dom_AncestorWithLowestSemi(dominatordata *dd, int v);
  49 void dom_Link(dominatordata *dd, int p, int n);
  50 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N);
  51 #endif
  52
  53 /*************************************
  54 Calculate Dominators
  55 *************************************/
  56 dominatordata *compute_Dominators(graphdata *gd, int basicblockcount) {
  57         int i,j,n,N,p,s,s_,v,y;
  58         graphiterator iter;
  59         dominatordata *dd;
  60
  61         dd = DNEW(dominatordata);
  62
  63         dom_Dominators_init(dd, basicblockcount);
  64
  65         N=0;
  66
  67         /* 1 ist the root node of the method                    */
  68         /* 0 is the artificial parent, where locals are set to their parameters */
  69         dom_DFS(gd, dd, -1, 0, &N
  70 #ifdef DOM_DEBUG_CHECK
  71                         ,basicblockcount
  72 #endif
  73                         );
  74
  75         for(i = N-1; i > 0; i--) {
  76                 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
  77                 n = dd->vertex[i];
  78                 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
  79                 p = dd->parent[n];
  80                 s = p;
  81                 j = graph_get_first_predecessor(gd, n, &iter);
  82                 for (; j != -1; j = graph_get_next(&iter)) {
  83                 _DOM_CHECK_BOUNDS(j, 0, basicblockcount);
  84                         if (dd->dfnum[j] <= dd->dfnum[n])
  85                                 s_ = j;
  86                         else
  87                                 s_ = dd->semi[dom_AncestorWithLowestSemi(dd, j
  88 #ifdef DOM_DEBUG_CHECK
  89                                                                                                                  ,basicblockcount
  90 #endif
  91                                                                                                                  )];
  92                 _DOM_CHECK_BOUNDS(s_, 0, basicblockcount);
  93                 _DOM_CHECK_BOUNDS(s, 0, basicblockcount);
  94                         if (dd->dfnum[s_] < dd->dfnum[s])
  95                                 s = s_;
  96                 }
  97                 dd->semi[n] = s;
  98                 _DOM_CHECK_BOUNDS(dd->num_bucket[s], 0, basicblockcount);
  99                 dd->bucket[s][dd->num_bucket[s]] = n;
 100                 dd->num_bucket[s]++;
 101                 dom_Link(dd, p, n
 102 #ifdef DOM_DEBUG_CHECK
 103                                  , basicblockcount
 104 #endif
 105                                  );
 106                 _DOM_CHECK_BOUNDS(p, 0, basicblockcount);
 107                 for(j = 0; j < dd->num_bucket[p]; j++) {
 108                 _DOM_CHECK_BOUNDS(j, 0, basicblockcount);
 109                         v = dd->bucket[p][j];
 110                         y = dom_AncestorWithLowestSemi(dd, v
 111 #ifdef DOM_DEBUG_CHECK
 112                                                                                    , basicblockcount
 113 #endif
 114                                                                                    );
 115                 _DOM_CHECK_BOUNDS(y, 0, basicblockcount);
 116                 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
 117             if (dd->semi[y] == dd->semi[v])
 118                                 dd->idom[v] = p;
 119                         else
 120                                 dd->samedom[v] = y;
 121                 }
 122                 dd->num_bucket[p] = 0;
 123         }
 124         for(i = 1; i < N; i++) {
 125                 n = dd->vertex[i];
 126                 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
 127             if (dd->samedom[n] != -1) {
 128                         _DOM_CHECK_BOUNDS(dd->samedom[n], 0, basicblockcount);
 129                         dd->idom[n] = dd->idom[dd->samedom[n]];
 130                 }
 131         }
 132         return dd;
 133 }
 134
 135 /********************************************
 136 compute Dominace Frontier
 137 ********************************************/
 138 void computeDF(graphdata *gd, dominatordata *dd, int basicblockcount, int n) {
 139         int c,i,j;
 140         bool *_S;
 141         graphiterator iter;
 142
 143         _S = DMNEW(bool, basicblockcount);
 144         for(i = 0; i < basicblockcount; i++)
 145                 _S[i] = false;
 146         i = graph_get_first_successor(gd, n, &iter);
 147         for (; i != -1; i = graph_get_next(&iter)) {
 148                 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
 149                 if (dd->idom[i] != n)
 150                         _S[i] = true;
 151         }
 152         for(c=0; c < basicblockcount; c++) {
 153                 if (dd->idom[c] == n) {
 154                         computeDF(gd, dd, basicblockcount, c);
 155                         for(j=0; j < dd->num_DF[c]; j++) {
 156                 _DOM_CHECK_BOUNDS(dd->DF[c][j], 0, basicblockcount);
 157                     if (n != dd->idom[dd->DF[c][j]])
 158                                         /* n does not dominate DF[c][j] -> traverse idom list? */
 159                                         _S[dd->DF[c][j]] = true;
 160                         }
 161                 }
 162         }
 163         for(i = 0; i < basicblockcount; i++)
 164                 if (_S[i]) {
 165                 _DOM_CHECK_BOUNDS(dd->num_DF[n], 0, basicblockcount);
 166                         dd->DF[n][dd->num_DF[n]] = i;
 167                         dd->num_DF[n]++;
 168                 }
 169 }
 170
 171
 172 void dom_Dominators_init(dominatordata *dd, int basicblockcount) {
 173         int i;
 174
 175         dd->dfnum  = DMNEW(int, basicblockcount);
 176         dd->vertex = DMNEW(int, basicblockcount);
 177         dd->parent = DMNEW(int, basicblockcount);
 178         dd->semi   = DMNEW(int, basicblockcount);
 179         dd->ancestor = DMNEW(int, basicblockcount);
 180         dd->idom     = DMNEW(int, basicblockcount);
 181         dd->samedom  = DMNEW(int, basicblockcount);
 182         dd->bucket   = DMNEW(int*, basicblockcount);
 183         dd->num_bucket = DMNEW(int, basicblockcount);
 184         dd->DF       = DMNEW(int*, basicblockcount);
 185         dd->num_DF   = DMNEW(int, basicblockcount);
 186         dd->best     = DMNEW(int, basicblockcount);
 187         for (i=0; i < basicblockcount; i++) {
 188                 dd->dfnum[i] = -1;
 189                 dd->semi[i] = dd->ancestor[i] = dd->idom[i] = dd->samedom[i] = -1;
 190                 dd->num_bucket[i] = 0;
 191                 dd->bucket[i] = DMNEW(int, basicblockcount);
 192                 dd->num_DF[i] = 0;
 193                 dd->DF[i] = DMNEW(int, basicblockcount);
 194         }
 195 }
 196
 197 /**************************************
 198 Create Depth First Spanning Tree
 199 **************************************/
 200 #ifdef DOM_DEBUG_CHECK
 201 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N,
 202                          int basicblockcount) {
 203 #else
 204 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N) {
 205 #endif
 206     int i;
 207         graphiterator iter;
 208
 209         _DOM_CHECK_BOUNDS(n,0,basicblockcount);
 210         if (dd->dfnum[n] == -1) { /* not visited till now? */
 211                 dd->dfnum[n] = *N;
 212                 _DOM_CHECK_BOUNDS(*N,0,basicblockcount);
 213                 dd->vertex[*N] = n;
 214                 dd->parent[n] = p;
 215                 (*N)++;
 216                 i = graph_get_first_successor(gd, n, &iter);
 217                 for (; i != -1; i = graph_get_next(&iter)) {
 218                         dom_DFS(gd, dd, n, i, N
 219 #ifdef DOM_DEBUG_CHECK
 220                                         , basicblockcount
 221 #endif
 222                                         );
 223                 }
 224         }
 225 }
 226
 227 #ifdef DOM_DEBUG_CHECK
 228 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount) {
 229 #else
 230 int dom_AncestorWithLowestSemi(dominatordata *dd, int v) {
 231 #endif
 232         int a,b;
 233
 234         _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
 235         a = dd->ancestor[v];
 236         _DOM_CHECK_BOUNDS(a,0,basicblockcount);
 237         if (dd->ancestor[a] != -1) {
 238                 b = dom_AncestorWithLowestSemi(dd, a
 239 #ifdef DOM_DEBUG_CHECK
 240                                                                            , basicblockcount
 241 #endif
 242                                                                            );
 243                 dd->ancestor[v] = dd->ancestor[a];
 244                 _DOM_CHECK_BOUNDS(b,0,basicblockcount);
 245                 _DOM_CHECK_BOUNDS(dd->best[v],0,basicblockcount);
 246                 _DOM_CHECK_BOUNDS(dd->semi[dd->best[v]],0,basicblockcount);
 247                 if (dd->dfnum[dd->semi[b]] < dd->dfnum[dd->semi[dd->best[v]]])
 248                         dd->best[v] = b;
 249         }
 250         return dd->best[v];
 251 }
 252
 253 #ifdef DOM_DEBUG_CHECK
 254 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount) {
 255 #else
 256 void dom_Link(dominatordata *dd, int p, int n) {
 257 #endif
 258         _DOM_CHECK_BOUNDS(n,0,basicblockcount);
 259         dd->ancestor[n] = p;
 260         dd->best[n] = n;
 261 }
 262
 263 /*
 264  * These are local overrides for various environment variables in Emacs.
 265  * Please do not remove this and leave it at the end of the file, where
 266  * Emacs will automagically detect them.
 267  * ---------------------------------------------------------------------
 268  * Local variables:
 269  * mode: c
 270  * indent-tabs-mode: t
 271  * c-basic-offset: 4
 272  * tab-width: 4
 273  * End:
 274  */