1 /* src/vm/jit/optimizing/dominators.cpp - dominators and dominance frontier
3 Copyright (C) 2005, 2006, 2008
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2, or (at
11 your option) any later version.
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
30 #include "mm/memory.h"
32 #include "toolbox/bitvector.h"
34 #include "vm/jit/jit.hpp"
36 #include "vm/jit/optimizing/graph.h"
37 #include "vm/jit/optimizing/dominators.hpp"
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,
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);
53 /*************************************
55 *************************************/
56 dominatordata *compute_Dominators(graphdata *gd, int basicblockcount) {
57 int i,j,n,N,p,s,s_,v,y;
61 dd = (dominatordata*) DumpMemory::allocate(sizeof(dominatordata));
63 dom_Dominators_init(dd, basicblockcount);
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
75 for(i = N-1; i > 0; i--) {
76 _DOM_CHECK_BOUNDS(i, 0, basicblockcount);
78 _DOM_CHECK_BOUNDS(n, 0, basicblockcount);
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])
87 s_ = dd->semi[dom_AncestorWithLowestSemi(dd, j
88 #ifdef DOM_DEBUG_CHECK
92 _DOM_CHECK_BOUNDS(s_, 0, basicblockcount);
93 _DOM_CHECK_BOUNDS(s, 0, basicblockcount);
94 if (dd->dfnum[s_] < dd->dfnum[s])
98 _DOM_CHECK_BOUNDS(dd->num_bucket[s], 0, basicblockcount);
99 dd->bucket[s][dd->num_bucket[s]] = n;
102 #ifdef DOM_DEBUG_CHECK
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
115 _DOM_CHECK_BOUNDS(y, 0, basicblockcount);
116 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
117 if (dd->semi[y] == dd->semi[v])
122 dd->num_bucket[p] = 0;
124 for(i = 1; i < N; 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]];
135 /********************************************
136 compute Dominace Frontier
137 ********************************************/
138 void computeDF(graphdata *gd, dominatordata *dd, int basicblockcount, int n) {
143 _S = (bool*) DumpMemory::allocate(sizeof(bool) * basicblockcount);
144 for(i = 0; i < basicblockcount; i++)
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)
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;
163 for(i = 0; i < basicblockcount; i++)
165 _DOM_CHECK_BOUNDS(dd->num_DF[n], 0, basicblockcount);
166 dd->DF[n][dd->num_DF[n]] = i;
172 void dom_Dominators_init(dominatordata *dd, int basicblockcount) {
175 dd->dfnum = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
176 dd->vertex = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
177 dd->parent = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
178 dd->semi = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
179 dd->ancestor = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
180 dd->idom = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
181 dd->samedom = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
182 dd->bucket = (int**) DumpMemory::allocate(sizeof(int*) * basicblockcount);
183 dd->num_bucket = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
184 dd->DF = (int**) DumpMemory::allocate(sizeof(int*) * basicblockcount);
185 dd->num_DF = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
186 dd->best = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
187 for (i=0; i < basicblockcount; i++) {
189 dd->semi[i] = dd->ancestor[i] = dd->idom[i] = dd->samedom[i] = -1;
190 dd->num_bucket[i] = 0;
191 dd->bucket[i] = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
193 dd->DF[i] = (int*) DumpMemory::allocate(sizeof(int) * basicblockcount);
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) {
204 void dom_DFS(graphdata *gd, dominatordata *dd, int p, int n, int *N) {
209 _DOM_CHECK_BOUNDS(n,0,basicblockcount);
210 if (dd->dfnum[n] == -1) { /* not visited till now? */
212 _DOM_CHECK_BOUNDS(*N,0,basicblockcount);
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
227 #ifdef DOM_DEBUG_CHECK
228 int dom_AncestorWithLowestSemi(dominatordata *dd, int v, int basicblockcount) {
230 int dom_AncestorWithLowestSemi(dominatordata *dd, int v) {
234 _DOM_CHECK_BOUNDS(v, 0, basicblockcount);
236 _DOM_CHECK_BOUNDS(a,0,basicblockcount);
237 if (dd->ancestor[a] != -1) {
238 b = dom_AncestorWithLowestSemi(dd, a
239 #ifdef DOM_DEBUG_CHECK
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]]])
253 #ifdef DOM_DEBUG_CHECK
254 void dom_Link(dominatordata *dd, int p, int n, int basicblockcount) {
256 void dom_Link(dominatordata *dd, int p, int n) {
258 _DOM_CHECK_BOUNDS(n,0,basicblockcount);
263 /*********************************************************/
265 typedef struct basicblock_info basicblock_info;
267 struct basicblock_info {
270 basicblock_info *parent;
271 basicblock_info *semi;
272 basicblock_info *ancestor;
273 basicblock_info *best;
274 basicblock_info *idom;
275 basicblock_info *samedom;
276 basicblock_info **bucket;
277 unsigned bucketcount;
280 typedef struct dominator_tree_info dominator_tree_info;
282 struct dominator_tree_info {
284 basicblock_info *basicblocks;
285 basicblock_info **df_map;
289 static dominator_tree_info *dominator_tree_init(jitdata *jd) {
290 dominator_tree_info *di;
292 basicblock_info *iti;
294 di = (dominator_tree_info*) DumpMemory::allocate(sizeof(dominator_tree_info));
298 di->basicblocks = (basicblock_info*) DumpMemory::allocate(sizeof(basicblock_info) * jd->basicblockcount);
299 MZERO(di->basicblocks, basicblock_info, jd->basicblockcount);
301 for (iti = di->basicblocks; iti != di->basicblocks + jd->basicblockcount; ++iti) {
303 iti->bucket = (basicblock_info**) DumpMemory::allocate(sizeof(basicblock_info*) * jd->basicblockcount);
304 iti->bucketcount = 0;
307 for (itb = jd->basicblocks; itb; itb = itb->next) {
308 di->basicblocks[itb->nr].bb = itb;
311 di->df_map = (basicblock_info**) DumpMemory::allocate(sizeof(basicblock_info*) * jd->basicblockcount);
312 MZERO(di->df_map, basicblock_info *, jd->basicblockcount);
319 static inline basicblock_info *dominator_tree_get_basicblock(dominator_tree_info *di, basicblock *bb) {
320 return di->basicblocks + bb->nr;
323 static void dominator_tree_depth_first_search(
324 dominator_tree_info *di, basicblock_info *parent, basicblock_info *node
328 if (node->dfnum == -1) {
330 node->dfnum = di->df_counter;
331 node->parent = parent;
332 di->df_map[di->df_counter] = node;
335 for (it = node->bb->successors; it != node->bb->successors + node->bb->successorcount; ++it) {
336 dominator_tree_depth_first_search(
338 dominator_tree_get_basicblock(di, *it)
344 void dominator_tree_link(dominator_tree_info *di, basicblock_info *parent, basicblock_info *node) {
345 node->ancestor = parent;
349 basicblock_info *dominator_tree_ancestor_with_lowest_semi(
350 dominator_tree_info *di, basicblock_info *node
352 basicblock_info *a, *b;
356 if (a->ancestor != NULL) {
357 b = dominator_tree_ancestor_with_lowest_semi(di, a);
358 node->ancestor = a->ancestor;
359 if (b->semi->dfnum < node->best->semi->dfnum) {
367 void dominator_tree_build_intern(jitdata *jd) {
369 dominator_tree_info *di;
370 basicblock_info *node;
371 basicblock_info *semicand;
372 basicblock_info *pred;
374 basicblock_info **itii;
375 basicblock_info *v, *y;
378 di = dominator_tree_init(jd);
380 dominator_tree_depth_first_search(di, NULL, dominator_tree_get_basicblock(di, jd->basicblocks));
382 for (i = di->df_counter - 1; i >= 1; --i) {
383 node = di->df_map[i];
385 node->semi = node->parent;
388 itb = node->bb->predecessors;
389 itb != node->bb->predecessors + node->bb->predecessorcount;
393 pred = dominator_tree_get_basicblock(di, *itb);
395 if (pred->dfnum <= node->dfnum) {
398 semicand = dominator_tree_ancestor_with_lowest_semi(di, pred)->semi;
401 if (semicand->dfnum < node->semi->dfnum) {
402 node->semi = semicand;
406 node->semi->bucket[node->semi->bucketcount] = node;
407 node->semi->bucketcount += 1;
409 dominator_tree_link(di, node->parent, node);
411 for (itii = node->parent->bucket; itii != node->parent->bucket + node->parent->bucketcount; ++itii) {
413 y = dominator_tree_ancestor_with_lowest_semi(di, v);
414 if (y->semi == v->semi) {
415 v->idom = node->parent;
421 node->parent->bucketcount = 0;
424 for (i = 1; i < di->df_counter; ++i) {
425 node = di->df_map[i];
427 node->idom = node->samedom->idom;
430 node->bb->idom = node->idom->bb;
431 node->idom->bb->domsuccessorcount += 1;
435 void dominator_tree_link_children(jitdata *jd) {
437 /* basicblock number => current number of successors */
438 unsigned *numsuccessors;
440 // Create new dump memory area.
443 /* Allocate memory for successors */
445 for (bb = jd->basicblocks; bb; bb = bb->next) {
446 if (bb->domsuccessorcount > 0) {
447 bb->domsuccessors = (basicblock**) DumpMemory::allocate(sizeof(basicblock*) * bb->domsuccessorcount);
451 /* Allocate memory for per basic block counter of successors */
453 numsuccessors = (unsigned*) DumpMemory::allocate(sizeof(unsigned) * jd->basicblockcount);
454 MZERO(numsuccessors, unsigned, jd->basicblockcount);
456 /* Link immediate dominators with successors */
458 for (bb = jd->basicblocks; bb; bb = bb->next) {
460 bb->idom->domsuccessors[numsuccessors[bb->idom->nr]] = bb;
461 numsuccessors[bb->idom->nr] += 1;
466 bool dominator_tree_build(jitdata *jd) {
467 // Create new dump memory area.
470 dominator_tree_build_intern(jd);
472 dominator_tree_link_children(jd);
477 typedef struct dominance_frontier_item dominance_frontier_item;
479 struct dominance_frontier_item {
481 dominance_frontier_item *next;
484 typedef struct dominance_frontier_list dominance_frontier_list;
486 struct dominance_frontier_list {
487 dominance_frontier_item *first;
491 void dominance_frontier_list_add(dominance_frontier_list *list, basicblock *bb) {
492 dominance_frontier_item *item;
494 for (item = list->first; item; item = item->next) {
495 if (item->bb == bb) return;
498 item = (dominance_frontier_item*) DumpMemory::allocate(sizeof(dominance_frontier_item));
500 item->next = list->first;
505 typedef struct dominance_frontier_info dominance_frontier_info;
507 struct dominance_frontier_info {
509 dominance_frontier_list *map;
512 dominance_frontier_info *dominance_frontier_init(jitdata *jd) {
513 dominance_frontier_info *dfi = (dominance_frontier_info*) DumpMemory::allocate(sizeof(dominance_frontier_info));
517 dfi->map = (dominance_frontier_list*) DumpMemory::allocate(sizeof(dominance_frontier_list) * jd->basicblockcount);
518 MZERO(dfi->map, dominance_frontier_list, jd->basicblockcount);
523 bool dominance_frontier_dominates(basicblock *d, basicblock *x) {
536 void dominance_frontier_for_block(dominance_frontier_info *dfi, basicblock *b) {
538 dominance_frontier_item *itdf;
539 dominance_frontier_list s = { NULL, 0 };
541 for (it = b->successors; it != b->successors + b->successorcount; ++it) {
542 if ((*it)->idom != b) {
543 dominance_frontier_list_add(&s, *it);
547 for (it = b->domsuccessors; it != b->domsuccessors + b->domsuccessorcount; ++it) {
548 dominance_frontier_for_block(dfi, *it);
549 for (itdf = dfi->map[(*it)->nr].first; itdf; itdf = itdf->next) {
550 if (! dominance_frontier_dominates(b, itdf->bb)) {
551 dominance_frontier_list_add(&s, itdf->bb);
559 void dominance_frontier_store(dominance_frontier_info *dfi) {
561 dominance_frontier_item *itdf;
564 for (bb = dfi->jd->basicblocks; bb; bb = bb->next) {
565 if (bb->nr < dfi->jd->basicblockcount) {
566 if (dfi->map[bb->nr].count > 0) {
567 bb->domfrontiercount = dfi->map[bb->nr].count;
568 itout = bb->domfrontier = (basicblock**) DumpMemory::allocate(sizeof(basicblock*) * bb->domfrontiercount);
569 for (itdf = dfi->map[bb->nr].first; itdf; itdf = itdf->next) {
578 bool dominance_frontier_build(jitdata *jd) {
579 // Create new dump memory area.
582 dominance_frontier_info *dfi = dominance_frontier_init(jd);
583 dominance_frontier_for_block(dfi, jd->basicblocks);
584 dominance_frontier_store(dfi);
587 #include "vm/jit/show.hpp"
588 #include "vm/jit/python.h"
590 extern "C" void graph_add_edge( graphdata *gd, int from, int to );
592 void dominator_tree_validate(jitdata *jd, dominatordata *_dd) {
595 basicblock *bptr, **it;
600 // Create new dump memory area.
603 fprintf(stderr, "%s/%s: \n", jd->m->clazz->name->text, jd->m->name->text);
604 gd = graph_init(jd->basicblockcount);
606 for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
607 for (it = bptr->successors; it != bptr->successors + bptr->successorcount; ++it) {
608 graph_add_edge(gd, bptr->nr, (*it)->nr);
612 dd = compute_Dominators(gd, jd->basicblockcount);
614 for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
615 if (bptr->flags >= BBREACHED) {
616 if (bptr->idom == NULL) {
617 if (!(dd->idom[bptr->nr] == -1)) {
618 printf("-- %d %d\n", dd->idom[bptr->nr], bptr->nr);
622 assert(dd->idom[bptr->nr] == bptr->idom->nr);
627 computeDF(gd, dd, jd->basicblockcount, 0);
629 for (bptr = jd->basicblocks; bptr; bptr = bptr->next) {
630 if (bptr->flags >= BBREACHED) {
631 assert(bptr->domfrontiercount == dd->num_DF[bptr->nr]);
632 for (itnr = dd->DF[bptr->nr]; itnr != dd->DF[bptr->nr] + dd->num_DF[bptr->nr]; ++itnr) {
634 for (it = bptr->domfrontier; it != bptr->domfrontier + bptr->domfrontiercount; ++it) {
635 if ((*it)->nr == *itnr) {
647 * These are local overrides for various environment variables in Emacs.
648 * Please do not remove this and leave it at the end of the file, where
649 * Emacs will automagically detect them.
650 * ---------------------------------------------------------------------
653 * indent-tabs-mode: t