3 * Dominator computation on the control flow graph
6 * Dietmar Maurer (dietmar@ximian.com)
7 * Paolo Molaro (lupus@ximian.com)
9 * (C) 2003 Ximian, Inc.
10 * Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
11 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
15 #include <mono/metadata/debug-helpers.h>
16 #include <mono/metadata/mempool.h>
17 #include <mono/metadata/mempool-internals.h>
24 * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
25 * it is the entry bblock.
27 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
30 * Compute dominators and immediate dominators using the algorithm in the
31 * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
32 * Timothy J. Harvey, and Ken Kennedy:
33 * http://citeseer.ist.psu.edu/cooper01simple.html
36 compute_dominators (MonoCompile
*cfg
)
38 int bindex
, i
, bitsize
;
39 MonoBasicBlock
*entry
;
40 MonoBasicBlock
**doms
;
43 g_assert (!(cfg
->comp_done
& MONO_COMP_DOM
));
45 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
47 entry
= cfg
->bblocks
[0];
49 doms
= g_new0 (MonoBasicBlock
*, cfg
->num_bblocks
);
50 doms
[entry
->dfn
] = entry
;
52 if (cfg
->verbose_level
> 1) {
53 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
55 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
57 printf ("BB%d IN: ", bb
->block_num
);
58 for (j
= 0; j
< bb
->in_count
; ++j
)
59 printf ("%d ", bb
->in_bb
[j
]->block_num
);
68 for (bindex
= 0; bindex
< cfg
->num_bblocks
; ++bindex
) {
69 MonoBasicBlock
*bb
= cfg
->bblocks
[bindex
];
73 for (i
= 0; i
< bb
->in_count
; ++i
) {
74 MonoBasicBlock
*in_bb
= bb
->in_bb
[i
];
75 if ((in_bb
!= bb
) && doms
[in_bb
->dfn
]) {
80 if (bb
!= cfg
->bblocks
[0])
83 while (i
< bb
->in_count
) {
84 MonoBasicBlock
*in_bb
= bb
->in_bb
[i
];
86 if (HAS_DFN (in_bb
, entry
) && doms
[in_bb
->dfn
]) {
88 MonoBasicBlock
*f1
= idom
;
89 MonoBasicBlock
*f2
= in_bb
;
92 if (f1
->dfn
< f2
->dfn
)
103 if (idom
!= doms
[bb
->dfn
]) {
104 if (bb
== cfg
->bblocks
[0])
107 doms
[bb
->dfn
] = idom
;
111 //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
116 /* Compute bb->dominators for each bblock */
117 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
118 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
120 MonoBitSet
*dominators
;
123 mem
= (char *)mono_mempool_alloc0 (cfg
->mempool
, bitsize
);
125 bb
->dominators
= dominators
= mono_bitset_mem_new (mem
, cfg
->num_bblocks
, 0);
128 mono_bitset_set_fast (dominators
, bb
->dfn
);
131 for (cbb
= doms
[bb
->dfn
]; cbb
->dfn
; cbb
= doms
[cbb
->dfn
])
132 mono_bitset_set_fast (dominators
, cbb
->dfn
);
134 bb
->idom
= doms
[bb
->dfn
];
136 bb
->idom
->dominated
= g_slist_prepend_mempool (cfg
->mempool
, bb
->idom
->dominated
, bb
);
140 mono_bitset_set_fast (dominators
, 0);
145 cfg
->comp_done
|= MONO_COMP_DOM
| MONO_COMP_IDOM
;
147 if (cfg
->verbose_level
> 1) {
148 printf ("DTREE %s %d\n", mono_method_full_name (cfg
->method
, TRUE
),
149 cfg
->header
->num_clauses
);
150 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
151 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
152 printf ("BB%d(dfn=%d) (IDOM=BB%d): ", bb
->block_num
, bb
->dfn
, bb
->idom
? bb
->idom
->block_num
: -1);
153 mono_blockset_print (cfg
, bb
->dominators
, NULL
, -1);
161 check_dominance_frontier (MonoBasicBlock
*x
, MonoBasicBlock
*t
)
165 t
->flags
|= BB_VISITED
;
167 if (mono_bitset_test_fast (t
->dominators
, x
->dfn
)) {
168 for (i
= 0; i
< t
->out_count
; ++i
) {
169 if (!(t
->flags
& BB_VISITED
)) {
171 check_dominance_frontier (x
, t
->out_bb
[i
]);
173 for (j
= 0; j
< t
->out_bb
[i
]->in_count
; j
++) {
174 if (t
->out_bb
[i
]->in_bb
[j
] == t
)
181 if (!mono_bitset_test_fast (x
->dfrontier
, t
->dfn
)) {
182 printf ("BB%d not in frontier of BB%d\n", t
->block_num
, x
->block_num
);
183 g_assert_not_reached ();
191 * Compute dominance frontiers using the algorithm from the same paper.
194 compute_dominance_frontier (MonoCompile
*cfg
)
199 g_assert (!(cfg
->comp_done
& MONO_COMP_DFRONTIER
));
201 for (i
= 0; i
< cfg
->num_bblocks
; ++i
)
202 cfg
->bblocks
[i
]->flags
&= ~BB_VISITED
;
204 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
205 mem
= (char *)mono_mempool_alloc0 (cfg
->mempool
, bitsize
* cfg
->num_bblocks
);
207 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
208 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
209 bb
->dfrontier
= mono_bitset_mem_new (mem
, cfg
->num_bblocks
, 0);
213 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
214 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
216 if (bb
->in_count
> 1) {
217 for (j
= 0; j
< bb
->in_count
; ++j
) {
218 MonoBasicBlock
*p
= bb
->in_bb
[j
];
220 if (p
->dfn
|| (p
== cfg
->bblocks
[0])) {
221 while (p
!= bb
->idom
) {
222 mono_bitset_set_fast (p
->dfrontier
, bb
->dfn
);
231 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
232 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
234 printf ("DFRONT %s BB%d: ", mono_method_full_name (cfg
->method
, TRUE
), bb
->block_num
);
235 mono_blockset_print (cfg
, bb
->dfrontier
, NULL
, -1);
240 /* this is a check for the dominator frontier */
241 for (i
= 0; i
< m
->num_bblocks
; ++i
) {
242 MonoBasicBlock
*x
= m
->bblocks
[i
];
244 mono_bitset_foreach_bit ((x
->dfrontier
), j
, (m
->num_bblocks
)) {
245 MonoBasicBlock
*w
= m
->bblocks
[j
];
247 /* x must not strictly dominates w */
248 if (mono_bitset_test_fast (w
->dominators
, x
->dfn
) && w
!= x
)
249 g_assert_not_reached ();
251 for (k
= 0; k
< m
->num_bblocks
; ++k
)
252 m
->bblocks
[k
]->flags
&= ~BB_VISITED
;
254 check_dominance_frontier (x
, x
);
259 cfg
->comp_done
|= MONO_COMP_DFRONTIER
;
263 df_set (MonoCompile
*m
, MonoBitSet
* dest
, MonoBitSet
*set
)
267 mono_bitset_foreach_bit (set
, i
, m
->num_bblocks
) {
268 mono_bitset_union_fast (dest
, m
->bblocks
[i
]->dfrontier
);
273 mono_compile_iterated_dfrontier (MonoCompile
*m
, MonoBitSet
*set
)
276 int bitsize
, count1
, count2
;
278 bitsize
= mono_bitset_alloc_size (m
->num_bblocks
, 0);
279 result
= mono_bitset_mem_new (mono_mempool_alloc0 (m
->mempool
, bitsize
), m
->num_bblocks
, 0);
281 df_set (m
, result
, set
);
282 count2
= mono_bitset_count (result
);
285 df_set (m
, result
, result
);
286 count2
= mono_bitset_count (result
);
287 } while (count2
> count1
);
293 mono_compile_dominator_info (MonoCompile
*cfg
, int dom_flags
)
295 if ((dom_flags
& MONO_COMP_DOM
) && !(cfg
->comp_done
& MONO_COMP_DOM
))
296 compute_dominators (cfg
);
297 if ((dom_flags
& MONO_COMP_DFRONTIER
) && !(cfg
->comp_done
& MONO_COMP_DFRONTIER
))
298 compute_dominance_frontier (cfg
);
302 * code to detect loops and loop nesting level
305 mono_compute_natural_loops (MonoCompile
*cfg
)
308 MonoBitSet
*in_loop_blocks
;
311 g_assert (!(cfg
->comp_done
& MONO_COMP_LOOPS
));
313 in_loop_blocks
= mono_bitset_new (cfg
->num_bblocks
+ 1, 0);
314 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
315 MonoBasicBlock
*n
= cfg
->bblocks
[i
];
317 for (j
= 0; j
< n
->out_count
; j
++) {
318 MonoBasicBlock
*h
= n
->out_bb
[j
];
319 /* check for single block loops */
321 h
->loop_blocks
= g_list_prepend_mempool (cfg
->mempool
, h
->loop_blocks
, h
);
324 /* check for back-edge from n to h */
325 else if (n
!= h
&& mono_bitset_test_fast (n
->dominators
, h
->dfn
)) {
328 /* already in loop_blocks? */
329 if (h
->loop_blocks
&& g_list_find (h
->loop_blocks
, n
)) {
333 mono_bitset_clear_all (in_loop_blocks
);
334 if (h
->loop_blocks
) {
337 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
338 MonoBasicBlock
*b
= (MonoBasicBlock
*)l
->data
;
340 mono_bitset_set_fast (in_loop_blocks
, b
->dfn
);
343 todo
= g_slist_prepend (NULL
, n
);
346 MonoBasicBlock
*cb
= (MonoBasicBlock
*)todo
->data
;
347 todo
= g_slist_delete_link (todo
, todo
);
349 if ((cb
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, cb
->dfn
)) || (!cb
->dfn
&& g_list_find (h
->loop_blocks
, cb
)))
352 h
->loop_blocks
= g_list_prepend_mempool (cfg
->mempool
, h
->loop_blocks
, cb
);
355 mono_bitset_set_fast (in_loop_blocks
, cb
->dfn
);
357 for (k
= 0; k
< cb
->in_count
; k
++) {
358 MonoBasicBlock
*prev
= cb
->in_bb
[k
];
359 /* add all previous blocks */
360 if (prev
!= h
&& !((prev
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, prev
->dfn
)) || (!prev
->dfn
&& g_list_find (h
->loop_blocks
, prev
)))) {
361 todo
= g_slist_prepend (todo
, prev
);
366 /* add the header if not already there */
367 if (!((h
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, h
->dfn
)) || (!h
->dfn
&& g_list_find (h
->loop_blocks
, h
)))) {
368 h
->loop_blocks
= g_list_prepend_mempool (cfg
->mempool
, h
->loop_blocks
, h
);
374 mono_bitset_free (in_loop_blocks
);
376 cfg
->comp_done
|= MONO_COMP_LOOPS
;
378 /* Compute loop_body_start for each loop */
379 bb_indexes
= g_new0 (int, cfg
->num_bblocks
);
383 for (i
= 0, bb
= cfg
->bb_entry
; bb
; i
++, bb
= bb
->next_bb
) {
385 bb_indexes
[bb
->dfn
] = i
;
388 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
389 if (cfg
->bblocks
[i
]->loop_blocks
) {
390 /* The loop body start is the first bblock in the order they will be emitted */
391 MonoBasicBlock
*h
= cfg
->bblocks
[i
];
392 MonoBasicBlock
*body_start
= h
;
395 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
396 MonoBasicBlock
*cb
= (MonoBasicBlock
*)l
->data
;
398 if (cb
->dfn
&& bb_indexes
[cb
->dfn
] < bb_indexes
[body_start
->dfn
]) {
403 body_start
->loop_body_start
= 1;
408 if (cfg
->verbose_level
> 1) {
409 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
410 if (cfg
->bblocks
[i
]->loop_blocks
) {
411 MonoBasicBlock
*h
= (MonoBasicBlock
*)cfg
->bblocks
[i
]->loop_blocks
->data
;
413 printf ("LOOP START %d\n", h
->block_num
);
414 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
415 MonoBasicBlock
*cb
= (MonoBasicBlock
*)l
->data
;
416 printf ("\tBB%d %d %p\n", cb
->block_num
, cb
->nesting
, cb
->loop_blocks
);
424 clear_idominators (MonoCompile
*cfg
)
428 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
429 if (cfg
->bblocks
[i
]->dominated
) {
430 cfg
->bblocks
[i
]->dominated
= NULL
;
434 cfg
->comp_done
&= ~MONO_COMP_IDOM
;
438 clear_loops (MonoCompile
*cfg
)
442 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
443 cfg
->bblocks
[i
]->nesting
= 0;
444 cfg
->bblocks
[i
]->loop_blocks
= NULL
;
447 cfg
->comp_done
&= ~MONO_COMP_LOOPS
;
451 mono_free_loop_info (MonoCompile
*cfg
)
453 if (cfg
->comp_done
& MONO_COMP_IDOM
)
454 clear_idominators (cfg
);
455 if (cfg
->comp_done
& MONO_COMP_LOOPS
)
459 #else /* DISABLE_JIT */
462 mono_free_loop_info (MonoCompile
*cfg
)
466 #endif /* DISABLE_JIT */