2 * dominators.c: Dominator computation on the control flow graph
5 * Dietmar Maurer (dietmar@ximian.com)
6 * Paolo Molaro (lupus@ximian.com)
8 * (C) 2003 Ximian, Inc.
11 #include <mono/metadata/debug-helpers.h>
15 //#define DEBUG_DOMINATORS
17 /* the simpler, dumber algorithm */
19 compute_dominators (MonoCompile *m) {
26 g_assert (!(m->comp_done & MONO_COMP_DOM));
28 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
29 /* the first is always the entry */
31 mem = mono_mempool_alloc0 (m->mempool, bitsize * (m->num_bblocks + 1));
32 bb->dominators = mono_bitset_mem_new (mem, m->num_bblocks, 0);
35 mono_bitset_set (bb->dominators, 0);
37 T = mono_bitset_mem_new (mem, m->num_bblocks, 0);
41 for (i = 1; i < m->num_bblocks; ++i) {
43 bb->dominators = mono_bitset_mem_new (mem, m->num_bblocks, 0);
45 mono_bitset_invert (bb->dominators);
47 #ifdef DEBUG_DOMINATORS
48 printf ("BB%d IN: ", bb->block_num);
49 for (j = 0; j < bb->in_count; ++j)
50 printf ("%d ", bb->in_bb [j]->block_num);
57 for (i = 1; i < m->num_bblocks; ++i) {
59 mono_bitset_set_all (T);
60 for (j = 0; j < bb->in_count; ++j) {
61 if (bb->in_bb [j]->dominators)
62 mono_bitset_intersection (T, bb->in_bb [j]->dominators);
64 mono_bitset_set (T, i);
65 if (!mono_bitset_equal (T, bb->dominators)) {
67 mono_bitset_copyto (T, bb->dominators);
72 m->comp_done |= MONO_COMP_DOM;
74 #ifdef DEBUG_DOMINATORS
75 printf ("DTREE %s %d\n", mono_method_full_name (m->method, TRUE),
76 mono_method_get_header (m->method)->num_clauses);
77 for (i = 0; i < m->num_bblocks; ++i) {
79 printf ("BB%d: ", bb->block_num);
80 mono_blockset_print (m, bb->dominators, NULL, -1);
86 compute_idominators (MonoCompile* m) {
89 MonoBitSet **T, *temp;
92 g_assert (!(m->comp_done & MONO_COMP_IDOM));
94 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
95 mem = mono_mempool_alloc (m->mempool, bitsize * (m->num_bblocks + 1));
96 T = mono_mempool_alloc (m->mempool, sizeof (MonoBitSet*) * m->num_bblocks);
98 for (i = 0; i < m->num_bblocks; ++i) {
100 T [i] = mono_bitset_mem_new (mem, m->num_bblocks, 0);
101 mono_bitset_copyto (bb->dominators, T [i]);
102 mono_bitset_clear (T [i], i);
103 if (mono_bitset_count (bb->dominators) - 1 != mono_bitset_count (T [i])) {
104 mono_blockset_print (m, bb->dominators, "dominators", -1);
105 mono_blockset_print (m, T [i], "T [i]", -1);
106 g_error ("problem at %d (%d)\n", i, bb->dfn);
110 temp = mono_bitset_mem_new (mem, m->num_bblocks, 0);
112 for (i = 1; i < m->num_bblocks; ++i) {
116 mono_bitset_foreach_bit_rev (temp, s, m->num_bblocks) {
118 mono_bitset_foreach_bit_rev (temp, t, m->num_bblocks) {
123 //if (mono_bitset_test_fast (T [s], t))
124 if (mono_bitset_test_fast (m->bblocks [s]->dominators, t))
125 mono_bitset_clear (temp, t);
129 #ifdef DEBUG_DOMINATORS
130 printf ("IDOMSET BB%d %d: ", m->bblocks [i]->block_num, m->num_bblocks);
131 mono_blockset_print (m, T [i], NULL, -1);
135 for (i = 1; i < m->num_bblocks; ++i) {
137 s = mono_bitset_find_start (T [i]);
139 /*fixme:mono_bitset_count does not really work */
140 //g_assert (mono_bitset_count (T [i]) == 1);
141 t = mono_bitset_find_first (T [i], s);
142 g_assert (t == -1 || t >= m->num_bblocks);
143 bb->idom = m->bblocks [s];
144 bb->idom->dominated = g_list_prepend (bb->idom->dominated, bb);
147 m->comp_done |= MONO_COMP_IDOM;
151 postorder_visit (MonoBasicBlock *start, int *idx, MonoBasicBlock **array)
155 /* we assume the flag was already cleared by the caller. */
156 start->flags |= BB_VISITED;
157 /*g_print ("visit %d at %p\n", *dfn, start->cil_code);*/
158 for (i = 0; i < start->out_count; ++i) {
159 if (start->out_bb [i]->flags & BB_VISITED)
161 postorder_visit (start->out_bb [i], idx, array);
163 array [*idx] = start;
168 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
172 t->flags |= BB_VISITED;
174 if (mono_bitset_test_fast (t->dominators, x->dfn)) {
175 for (i = 0; i < t->out_count; ++i) {
176 if (!(t->flags & BB_VISITED)) {
178 check_dominance_frontier (x, t->out_bb [i]);
180 for (j = 0; j < t->out_bb [i]->in_count; j++) {
181 if (t->out_bb [i]->in_bb [j] == t)
188 if (!mono_bitset_test_fast (x->dfrontier, t->dfn)) {
189 printf ("BB%d not in frontier of BB%d\n", t->block_num, x->block_num);
190 g_assert_not_reached ();
196 /* there is a bug in this code */
198 compute_dominance_frontier_old (MonoCompile *m) {
200 MonoBasicBlock **postorder;
201 MonoBasicBlock *bb, *z;
204 g_assert (!(m->comp_done & MONO_COMP_DFRONTIER));
206 postorder = mono_mempool_alloc (m->mempool, sizeof (MonoBasicBlock*) * m->num_bblocks);
208 postorder_visit (m->bb_entry, &i, postorder);
209 /*g_print ("postorder traversal:");
210 for (i = 0; i < m->num_bblocks; ++i)
211 g_print (" B%d", postorder [i]->dfn);
214 /* we could reuse the bitsets allocated in compute_idominators() */
215 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
216 mem = mono_mempool_alloc0 (m->mempool, bitsize * m->num_bblocks);
218 for (i = 0; i < m->num_bblocks; ++i) {
220 bb->dfrontier = mono_bitset_mem_new (mem, m->num_bblocks, 0);
223 for (i = 0; i < m->num_bblocks; ++i) {
225 /* the local component */
226 for (j = 0; j < bb->out_count; ++j) {
227 //if (bb->out_bb [j] != bb->idom)
228 if (bb->out_bb [j]->idom != bb)
229 mono_bitset_set (bb->dfrontier, bb->out_bb [j]->dfn);
232 for (i = 0; i < m->num_bblocks; ++i) {
234 /* the up component */
237 mono_bitset_foreach_bit (z->dfrontier, j, m->num_bblocks) {
238 //if (m->bblocks [j] != bb->idom)
239 if (m->bblocks [j]->idom != bb)
240 mono_bitset_set (bb->dfrontier, m->bblocks [j]->dfn);
245 /* this is a check for the dominator frontier */
246 for (i = 0; i < m->num_bblocks; ++i) {
247 MonoBasicBlock *x = m->bblocks [i];
249 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
250 MonoBasicBlock *w = m->bblocks [j];
252 /* x must not strictly dominates w */
253 if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
254 g_assert_not_reached ();
256 for (k = 0; k < m->num_bblocks; ++k)
257 m->bblocks [k]->flags &= ~BB_VISITED;
259 check_dominance_frontier (x, x);
263 m->comp_done |= MONO_COMP_DFRONTIER;
267 /* this is an implementation of the dominance frontier algorithm described in
268 * "modern compiler implementation in C" written by Andrew W. Appel
271 compute_dominance_frontier_appel (MonoCompile *m, int n)
277 g_assert (!(bb->flags & BB_VISITED));
278 bb->flags |= BB_VISITED;
280 for (i = 0; i < bb->out_count; ++i) {
281 MonoBasicBlock *y = bb->out_bb [i];
283 g_assert (!(mono_bitset_test_fast (y->dominators, bb->dfn) && bb->dfn != y->dfn));
284 mono_bitset_set (bb->dfrontier, y->dfn);
289 for (i = 0; i < m->num_bblocks; ++i) {
290 MonoBasicBlock *c = m->bblocks [i];
292 if (!(c->flags & BB_VISITED))
293 compute_dominance_frontier_appel (m, c->dfn);
294 mono_bitset_foreach_bit (c->dfrontier, j, m->num_bblocks) {
295 MonoBasicBlock *w = m->bblocks [j];
296 if (!(mono_bitset_test_fast (w->dominators, bb->dfn) && bb->dfn != w->dfn))
297 mono_bitset_set (bb->dfrontier, w->dfn);
304 compute_dominance_frontier (MonoCompile *m)
310 g_assert (!(m->comp_done & MONO_COMP_DFRONTIER));
312 for (i = 0; i < m->num_bblocks; ++i)
313 m->bblocks [i]->flags &= ~BB_VISITED;
315 /* we could reuse the bitsets allocated in compute_idominators() */
316 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
317 mem = mono_mempool_alloc0 (m->mempool, bitsize * m->num_bblocks);
319 for (i = 0; i < m->num_bblocks; ++i) {
321 bb->dfrontier = mono_bitset_mem_new (mem, m->num_bblocks, 0);
325 compute_dominance_frontier_appel (m, 0);
328 for (i = 0; i < m->num_bblocks; ++i) {
329 MonoBasicBlock *x = m->bblocks [i];
331 printf ("DFRONT %s BB%d: ", mono_method_full_name (m->method, TRUE), x->block_num);
332 mono_blockset_print (m, x->dfrontier, NULL, -1);
337 /* this is a check for the dominator frontier */
338 for (i = 0; i < m->num_bblocks; ++i) {
339 MonoBasicBlock *x = m->bblocks [i];
341 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
342 MonoBasicBlock *w = m->bblocks [j];
344 /* x must not strictly dominates w */
345 if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
346 g_assert_not_reached ();
348 for (k = 0; k < m->num_bblocks; ++k)
349 m->bblocks [k]->flags &= ~BB_VISITED;
351 check_dominance_frontier (x, x);
356 m->comp_done |= MONO_COMP_DFRONTIER;
360 mono_compile_dominator_info (MonoCompile *cfg, int dom_flags)
362 if ((dom_flags & MONO_COMP_DOM) && !(cfg->comp_done & MONO_COMP_DOM))
363 compute_dominators (cfg);
364 if ((dom_flags & MONO_COMP_IDOM) && !(cfg->comp_done & MONO_COMP_IDOM))
365 compute_idominators (cfg);
366 if ((dom_flags & MONO_COMP_DFRONTIER) && !(cfg->comp_done & MONO_COMP_DFRONTIER))
367 compute_dominance_frontier (cfg);
371 df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
375 mono_bitset_clear_all (dest);
376 mono_bitset_foreach_bit (set, i, m->num_bblocks) {
377 mono_bitset_union (dest, m->bblocks [i]->dfrontier);
381 /* TODO: alloc tmp and D on the stack */
383 mono_compile_iterated_dfrontier (MonoCompile *m, MonoBitSet *set)
385 MonoBitSet *result, *D;
386 int bitsize, change = TRUE;
388 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
389 result = mono_bitset_mem_new (mono_mempool_alloc (m->mempool, bitsize), m->num_bblocks, 0);
390 D = mono_bitset_mem_new (mono_mempool_alloc (m->mempool, bitsize), m->num_bblocks, 0);
392 df_set (m, result, set);
395 df_set (m, D, result);
396 mono_bitset_union (D, result);
398 if (!mono_bitset_equal (D, result)) {
399 mono_bitset_copyto (D, result);
407 //#define DEBUG_NATURAL_LOOPS
410 * code to detect loops and loop nesting level
413 mono_compute_natural_loops (MonoCompile *cfg)
417 g_assert (!(cfg->comp_done & MONO_COMP_LOOPS));
419 for (i = 0; i < cfg->num_bblocks; ++i) {
420 MonoBasicBlock *n = cfg->bblocks [i];
422 for (j = 0; j < n->out_count; j++) {
423 MonoBasicBlock *h = n->out_bb [j];
424 /* check for back-edge from n to h */
425 if (n != h && mono_bitset_test (n->dominators, h->dfn)) {
428 n->loop_body_start = 1;
430 /* already in loop_blocks? */
431 if (h->loop_blocks && g_list_find (h->loop_blocks, n))
434 todo = g_list_prepend (NULL, n);
437 MonoBasicBlock *cb = (MonoBasicBlock *)todo->data;
438 todo = g_list_delete_link (todo, todo);
440 if (g_list_find (h->loop_blocks, cb))
443 h->loop_blocks = g_list_prepend (h->loop_blocks, cb);
446 for (k = 0; k < cb->in_count; k++) {
447 MonoBasicBlock *prev = cb->in_bb [k];
448 /* add all previous blocks */
449 if (prev != h && !g_list_find (h->loop_blocks, prev)) {
450 todo = g_list_prepend (todo, prev);
455 /* add the header if not already there */
456 if (!g_list_find (h->loop_blocks, h)) {
457 h->loop_blocks = g_list_prepend (h->loop_blocks, h);
464 cfg->comp_done |= MONO_COMP_LOOPS;
466 #ifdef DEBUG_NATURAL_LOOPS
467 for (i = 0; i < cfg->num_bblocks; ++i) {
468 if (cfg->bblocks [i]->loop_blocks) {
469 MonoBasicBlock *h = (MonoBasicBlock *)cfg->bblocks [i]->loop_blocks->data;
471 printf ("LOOP START %d\n", h->block_num);
472 for (l = h->loop_blocks; l; l = l->next) {
473 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
474 printf (" BB%d %d %p\n", cb->block_num, cb->nesting, cb->loop_blocks);
483 clear_idominators (MonoCompile *cfg)
487 for (i = 0; i < cfg->num_bblocks; ++i) {
488 if (cfg->bblocks[i]->dominated) {
489 g_list_free (cfg->bblocks[i]->dominated);
490 cfg->bblocks[i]->dominated = NULL;
494 cfg->comp_done &= ~MONO_COMP_IDOM;
498 clear_loops (MonoCompile *cfg)
502 for (i = 0; i < cfg->num_bblocks; ++i) {
503 cfg->bblocks[i]->nesting = 0;
504 if (cfg->bblocks[i]->loop_blocks) {
505 g_list_free (cfg->bblocks[i]->loop_blocks);
506 cfg->bblocks[i]->loop_blocks = NULL;
510 cfg->comp_done &= ~MONO_COMP_LOOPS;
514 mono_free_loop_info (MonoCompile *cfg)
516 if (cfg->comp_done & MONO_COMP_IDOM)
517 clear_idominators (cfg);
518 if (cfg->comp_done & MONO_COMP_LOOPS)