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.
9 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
13 #include <mono/metadata/debug-helpers.h>
14 #include <mono/metadata/mempool.h>
15 #include <mono/metadata/mempool-internals.h>
22 * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
23 * it is the entry bblock.
25 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
28 * Compute dominators and immediate dominators using the algorithm in the
29 * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
30 * Timothy J. Harvey, and Ken Kennedy:
31 * http://citeseer.ist.psu.edu/cooper01simple.html
34 compute_dominators (MonoCompile *cfg)
36 int bindex, i, bitsize;
37 MonoBasicBlock *entry;
38 MonoBasicBlock **doms;
41 g_assert (!(cfg->comp_done & MONO_COMP_DOM));
43 bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
45 entry = cfg->bblocks [0];
47 doms = g_new0 (MonoBasicBlock*, cfg->num_bblocks);
48 doms [entry->dfn] = entry;
50 if (cfg->verbose_level > 1) {
51 for (i = 0; i < cfg->num_bblocks; ++i) {
53 MonoBasicBlock *bb = cfg->bblocks [i];
55 printf ("BB%d IN: ", bb->block_num);
56 for (j = 0; j < bb->in_count; ++j)
57 printf ("%d ", bb->in_bb [j]->block_num);
66 for (bindex = 0; bindex < cfg->num_bblocks; ++bindex) {
67 MonoBasicBlock *bb = cfg->bblocks [bindex];
71 for (i = 0; i < bb->in_count; ++i) {
72 MonoBasicBlock *in_bb = bb->in_bb [i];
73 if ((in_bb != bb) && doms [in_bb->dfn]) {
78 if (bb != cfg->bblocks [0])
81 while (i < bb->in_count) {
82 MonoBasicBlock *in_bb = bb->in_bb [i];
84 if (HAS_DFN (in_bb, entry) && doms [in_bb->dfn]) {
86 MonoBasicBlock *f1 = idom;
87 MonoBasicBlock *f2 = in_bb;
90 if (f1->dfn < f2->dfn)
101 if (idom != doms [bb->dfn]) {
102 if (bb == cfg->bblocks [0])
105 doms [bb->dfn] = idom;
109 //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
114 /* Compute bb->dominators for each bblock */
115 for (i = 0; i < cfg->num_bblocks; ++i) {
116 MonoBasicBlock *bb = cfg->bblocks [i];
118 MonoBitSet *dominators;
121 mem = (char *)mono_mempool_alloc0 (cfg->mempool, bitsize);
123 bb->dominators = dominators = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
126 mono_bitset_set_fast (dominators, bb->dfn);
129 for (cbb = doms [bb->dfn]; cbb->dfn; cbb = doms [cbb->dfn])
130 mono_bitset_set_fast (dominators, cbb->dfn);
132 bb->idom = doms [bb->dfn];
134 bb->idom->dominated = g_slist_prepend_mempool (cfg->mempool, bb->idom->dominated, bb);
138 mono_bitset_set_fast (dominators, 0);
143 cfg->comp_done |= MONO_COMP_DOM | MONO_COMP_IDOM;
145 if (cfg->verbose_level > 1) {
146 printf ("DTREE %s %d\n", mono_method_full_name (cfg->method, TRUE),
147 cfg->header->num_clauses);
148 for (i = 0; i < cfg->num_bblocks; ++i) {
149 MonoBasicBlock *bb = cfg->bblocks [i];
150 printf ("BB%d(dfn=%d) (IDOM=BB%d): ", bb->block_num, bb->dfn, bb->idom ? bb->idom->block_num : -1);
151 mono_blockset_print (cfg, bb->dominators, NULL, -1);
159 check_dominance_frontier (MonoBasicBlock *x, MonoBasicBlock *t)
163 t->flags |= BB_VISITED;
165 if (mono_bitset_test_fast (t->dominators, x->dfn)) {
166 for (i = 0; i < t->out_count; ++i) {
167 if (!(t->flags & BB_VISITED)) {
169 check_dominance_frontier (x, t->out_bb [i]);
171 for (j = 0; j < t->out_bb [i]->in_count; j++) {
172 if (t->out_bb [i]->in_bb [j] == t)
179 if (!mono_bitset_test_fast (x->dfrontier, t->dfn)) {
180 printf ("BB%d not in frontier of BB%d\n", t->block_num, x->block_num);
181 g_assert_not_reached ();
189 * Compute dominance frontiers using the algorithm from the same paper.
192 compute_dominance_frontier (MonoCompile *cfg)
197 g_assert (!(cfg->comp_done & MONO_COMP_DFRONTIER));
199 for (i = 0; i < cfg->num_bblocks; ++i)
200 cfg->bblocks [i]->flags &= ~BB_VISITED;
202 bitsize = mono_bitset_alloc_size (cfg->num_bblocks, 0);
203 mem = (char *)mono_mempool_alloc0 (cfg->mempool, bitsize * cfg->num_bblocks);
205 for (i = 0; i < cfg->num_bblocks; ++i) {
206 MonoBasicBlock *bb = cfg->bblocks [i];
207 bb->dfrontier = mono_bitset_mem_new (mem, cfg->num_bblocks, 0);
211 for (i = 0; i < cfg->num_bblocks; ++i) {
212 MonoBasicBlock *bb = cfg->bblocks [i];
214 if (bb->in_count > 1) {
215 for (j = 0; j < bb->in_count; ++j) {
216 MonoBasicBlock *p = bb->in_bb [j];
218 if (p->dfn || (p == cfg->bblocks [0])) {
219 while (p != bb->idom) {
220 mono_bitset_set_fast (p->dfrontier, bb->dfn);
229 for (i = 0; i < cfg->num_bblocks; ++i) {
230 MonoBasicBlock *bb = cfg->bblocks [i];
232 printf ("DFRONT %s BB%d: ", mono_method_full_name (cfg->method, TRUE), bb->block_num);
233 mono_blockset_print (cfg, bb->dfrontier, NULL, -1);
238 /* this is a check for the dominator frontier */
239 for (i = 0; i < m->num_bblocks; ++i) {
240 MonoBasicBlock *x = m->bblocks [i];
242 mono_bitset_foreach_bit ((x->dfrontier), j, (m->num_bblocks)) {
243 MonoBasicBlock *w = m->bblocks [j];
245 /* x must not strictly dominates w */
246 if (mono_bitset_test_fast (w->dominators, x->dfn) && w != x)
247 g_assert_not_reached ();
249 for (k = 0; k < m->num_bblocks; ++k)
250 m->bblocks [k]->flags &= ~BB_VISITED;
252 check_dominance_frontier (x, x);
257 cfg->comp_done |= MONO_COMP_DFRONTIER;
261 df_set (MonoCompile *m, MonoBitSet* dest, MonoBitSet *set)
265 mono_bitset_foreach_bit (set, i, m->num_bblocks) {
266 mono_bitset_union_fast (dest, m->bblocks [i]->dfrontier);
271 mono_compile_iterated_dfrontier (MonoCompile *m, MonoBitSet *set)
274 int bitsize, count1, count2;
276 bitsize = mono_bitset_alloc_size (m->num_bblocks, 0);
277 result = mono_bitset_mem_new (mono_mempool_alloc0 (m->mempool, bitsize), m->num_bblocks, 0);
279 df_set (m, result, set);
280 count2 = mono_bitset_count (result);
283 df_set (m, result, result);
284 count2 = mono_bitset_count (result);
285 } while (count2 > count1);
291 mono_compile_dominator_info (MonoCompile *cfg, int dom_flags)
293 if ((dom_flags & MONO_COMP_DOM) && !(cfg->comp_done & MONO_COMP_DOM))
294 compute_dominators (cfg);
295 if ((dom_flags & MONO_COMP_DFRONTIER) && !(cfg->comp_done & MONO_COMP_DFRONTIER))
296 compute_dominance_frontier (cfg);
300 * code to detect loops and loop nesting level
303 mono_compute_natural_loops (MonoCompile *cfg)
306 MonoBitSet *in_loop_blocks;
309 g_assert (!(cfg->comp_done & MONO_COMP_LOOPS));
311 in_loop_blocks = mono_bitset_new (cfg->num_bblocks + 1, 0);
312 for (i = 0; i < cfg->num_bblocks; ++i) {
313 MonoBasicBlock *n = cfg->bblocks [i];
315 for (j = 0; j < n->out_count; j++) {
316 MonoBasicBlock *h = n->out_bb [j];
317 /* check for single block loops */
319 h->loop_blocks = g_list_prepend_mempool (cfg->mempool, h->loop_blocks, h);
322 /* check for back-edge from n to h */
323 else if (n != h && mono_bitset_test_fast (n->dominators, h->dfn)) {
326 /* already in loop_blocks? */
327 if (h->loop_blocks && g_list_find (h->loop_blocks, n)) {
331 mono_bitset_clear_all (in_loop_blocks);
332 if (h->loop_blocks) {
335 for (l = h->loop_blocks; l; l = l->next) {
336 MonoBasicBlock *b = (MonoBasicBlock *)l->data;
338 mono_bitset_set_fast (in_loop_blocks, b->dfn);
341 todo = g_slist_prepend (NULL, n);
344 MonoBasicBlock *cb = (MonoBasicBlock *)todo->data;
345 todo = g_slist_delete_link (todo, todo);
347 if ((cb->dfn && mono_bitset_test_fast (in_loop_blocks, cb->dfn)) || (!cb->dfn && g_list_find (h->loop_blocks, cb)))
350 h->loop_blocks = g_list_prepend_mempool (cfg->mempool, h->loop_blocks, cb);
353 mono_bitset_set_fast (in_loop_blocks, cb->dfn);
355 for (k = 0; k < cb->in_count; k++) {
356 MonoBasicBlock *prev = cb->in_bb [k];
357 /* add all previous blocks */
358 if (prev != h && !((prev->dfn && mono_bitset_test_fast (in_loop_blocks, prev->dfn)) || (!prev->dfn && g_list_find (h->loop_blocks, prev)))) {
359 todo = g_slist_prepend (todo, prev);
364 /* add the header if not already there */
365 if (!((h->dfn && mono_bitset_test_fast (in_loop_blocks, h->dfn)) || (!h->dfn && g_list_find (h->loop_blocks, h)))) {
366 h->loop_blocks = g_list_prepend_mempool (cfg->mempool, h->loop_blocks, h);
372 mono_bitset_free (in_loop_blocks);
374 cfg->comp_done |= MONO_COMP_LOOPS;
376 /* Compute loop_body_start for each loop */
377 bb_indexes = g_new0 (int, cfg->num_bblocks);
381 for (i = 0, bb = cfg->bb_entry; bb; i ++, bb = bb->next_bb) {
383 bb_indexes [bb->dfn] = i;
386 for (i = 0; i < cfg->num_bblocks; ++i) {
387 if (cfg->bblocks [i]->loop_blocks) {
388 /* The loop body start is the first bblock in the order they will be emitted */
389 MonoBasicBlock *h = cfg->bblocks [i];
390 MonoBasicBlock *body_start = h;
393 for (l = h->loop_blocks; l; l = l->next) {
394 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
396 if (cb->dfn && bb_indexes [cb->dfn] < bb_indexes [body_start->dfn]) {
401 body_start->loop_body_start = 1;
406 if (cfg->verbose_level > 1) {
407 for (i = 0; i < cfg->num_bblocks; ++i) {
408 if (cfg->bblocks [i]->loop_blocks) {
409 MonoBasicBlock *h = (MonoBasicBlock *)cfg->bblocks [i]->loop_blocks->data;
411 printf ("LOOP START %d\n", h->block_num);
412 for (l = h->loop_blocks; l; l = l->next) {
413 MonoBasicBlock *cb = (MonoBasicBlock *)l->data;
414 printf ("\tBB%d %d %p\n", cb->block_num, cb->nesting, cb->loop_blocks);
422 clear_idominators (MonoCompile *cfg)
426 for (i = 0; i < cfg->num_bblocks; ++i) {
427 if (cfg->bblocks[i]->dominated) {
428 cfg->bblocks[i]->dominated = NULL;
432 cfg->comp_done &= ~MONO_COMP_IDOM;
436 clear_loops (MonoCompile *cfg)
440 for (i = 0; i < cfg->num_bblocks; ++i) {
441 cfg->bblocks[i]->nesting = 0;
442 cfg->bblocks[i]->loop_blocks = NULL;
445 cfg->comp_done &= ~MONO_COMP_LOOPS;
449 mono_free_loop_info (MonoCompile *cfg)
451 if (cfg->comp_done & MONO_COMP_IDOM)
452 clear_idominators (cfg);
453 if (cfg->comp_done & MONO_COMP_LOOPS)
457 #else /* DISABLE_JIT */
460 mono_free_loop_info (MonoCompile *cfg)
464 #endif /* DISABLE_JIT */