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