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