1 /* src/vm/jit/optimizing/dominators.c - dominators and dominance frontier
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
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
32 #include "mm/memory.h"
34 #include "toolbox/bitvector.h"
36 #include "vm/jit/optimizing/graph.h"
37 #include "vm/jit/optimizing/dominators.h"
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,
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);
52 /*************************************
54 *************************************/
55 dominatordata *compute_Dominators(graphdata *gd, int basicblockcount) {
56 int i,j,n,N,p,s,s_,v,y;
60 dd = DNEW(dominatordata);
62 dom_Dominators_init(dd, basicblockcount);
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
74 for(i = N-1; i > 0; i--) {
75 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
77 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
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])
86 s_ = dd->semi[dom_AncestorWithLowestSemi(dd, j
87 #ifdef DOM_DEBUG_CHECK
91 _DOM_CHECK_BOUNDS(s_, 0, basicblockcount);
92 _DOM_CHECK_BOUNDS(s, 0, basicblockcount);
93 if (dd->dfnum[s_] < dd->dfnum[s])
97 _DOM_CHECK_BOUNDS(dd->num_bucket[s], 0, basicblockcount);
98 dd->bucket[s][dd->num_bucket[s]] = n;
101 #ifdef DOM_DEBUG_CHECK
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
114 _DOM_CHECK_BOUNDS(y, 0, basicblockcount);
115 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
116 if (dd->semi[y] == dd->semi[v])
121 dd->num_bucket[p] = 0;
123 for(i = 1; i < N; 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]];
134 /********************************************
135 compute Dominace Frontier
136 ********************************************/
137 void computeDF(graphdata *gd, dominatordata *dd, int basicblockcount, int n) {
142 _S = DMNEW(bool, basicblockcount);
143 for(i = 0; i < basicblockcount; i++)
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)
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;
162 for(i = 0; i < basicblockcount; i++)
164 _DOM_CHECK_BOUNDS(dd->num_DF[n], 0, basicblockcount);
165 dd->DF[n][dd->num_DF[n]] = i;
171 void dom_Dominators_init(dominatordata *dd, int basicblockcount) {
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++) {
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);
192 dd->DF[i] = DMNEW(int, basicblockcount);
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) {
203 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N) {
208 _DOM_CHECK_BOUNDS(n,0,basicblockcount);
209 if (dd->dfnum[n] == -1) { /* not visited till now? */
211 _DOM_CHECK_BOUNDS(*N,0,basicblockcount);
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
226 #ifdef DOM_DEBUG_CHECK
227 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount) {
229 int dom_AncestorWithLowestSemi(dominatordata *dd, int v) {
233 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
235 _DOM_CHECK_BOUNDS(a,0,basicblockcount);
236 if (dd->ancestor[a] != -1) {
237 b = dom_AncestorWithLowestSemi(dd, a
238 #ifdef DOM_DEBUG_CHECK
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]]])
252 #ifdef DOM_DEBUG_CHECK
253 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount) {
255 void dom_Link(dominatordata *dd, int p, int n) {
257 _DOM_CHECK_BOUNDS(n,0,basicblockcount);
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 * ---------------------------------------------------------------------
269 * indent-tabs-mode: t