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
18 * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
19 * it is the entry bblock.
21 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
24 * Compute dominators and immediate dominators using the algorithm in the
25 * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
26 * Timothy J. Harvey, and Ken Kennedy:
27 * http://citeseer.ist.psu.edu/cooper01simple.html
30 compute_dominators (MonoCompile
*cfg
)
32 int bindex
, i
, bitsize
;
34 MonoBasicBlock
*entry
;
35 MonoBasicBlock
**doms
;
38 g_assert (!(cfg
->comp_done
& MONO_COMP_DOM
));
40 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
42 mem
= mono_mempool_alloc0 (cfg
->mempool
, bitsize
* cfg
->num_bblocks
);
44 entry
= cfg
->bblocks
[0];
46 doms
= g_new0 (MonoBasicBlock
*, cfg
->num_bblocks
);
47 doms
[entry
->dfn
] = entry
;
49 #ifdef DEBUG_DOMINATORS
50 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
51 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
53 printf ("BB%d IN: ", bb
->block_num
);
54 for (j
= 0; j
< bb
->in_count
; ++j
)
55 printf ("%d ", bb
->in_bb
[j
]->block_num
);
64 for (bindex
= 0; bindex
< cfg
->num_bblocks
; ++bindex
) {
65 MonoBasicBlock
*bb
= cfg
->bblocks
[bindex
];
69 for (i
= 0; i
< bb
->in_count
; ++i
) {
70 MonoBasicBlock
*in_bb
= bb
->in_bb
[i
];
71 if ((in_bb
!= bb
) && doms
[in_bb
->dfn
]) {
76 if (bb
!= cfg
->bblocks
[0])
79 while (i
< bb
->in_count
) {
80 MonoBasicBlock
*in_bb
= bb
->in_bb
[i
];
82 if (HAS_DFN (in_bb
, entry
) && doms
[in_bb
->dfn
]) {
84 MonoBasicBlock
*f1
= idom
;
85 MonoBasicBlock
*f2
= in_bb
;
88 if (f1
->dfn
< f2
->dfn
)
99 if (idom
!= doms
[bb
->dfn
]) {
100 if (bb
== cfg
->bblocks
[0])
103 doms
[bb
->dfn
] = idom
;
107 //printf ("A: bb=%d dfn=%d dom:%d\n", bb->block_num, bb->dfn, doms [bb->dfn]->block_num);
112 /* Compute bb->dominators for each bblock */
113 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
114 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
116 MonoBitSet
*dominators
;
118 bb
->dominators
= dominators
= mono_bitset_mem_new (mem
, cfg
->num_bblocks
, 0);
121 mono_bitset_set_fast (dominators
, bb
->dfn
);
124 for (cbb
= doms
[bb
->dfn
]; cbb
->dfn
; cbb
= doms
[cbb
->dfn
])
125 mono_bitset_set_fast (dominators
, cbb
->dfn
);
127 bb
->idom
= doms
[bb
->dfn
];
129 bb
->idom
->dominated
= g_list_prepend (bb
->idom
->dominated
, bb
);
133 mono_bitset_set_fast (dominators
, 0);
138 cfg
->comp_done
|= MONO_COMP_DOM
| MONO_COMP_IDOM
;
140 #ifdef DEBUG_DOMINATORS
141 printf ("DTREE %s %d\n", mono_method_full_name (cfg
->method
, TRUE
),
142 mono_method_get_header (cfg
->method
)->num_clauses
);
143 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
144 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
145 printf ("BB%d(dfn=%d) (IDOM=BB%d): ", bb
->block_num
, bb
->dfn
, bb
->idom
? bb
->idom
->block_num
: -1);
146 mono_blockset_print (cfg
, bb
->dominators
, NULL
, -1);
152 check_dominance_frontier (MonoBasicBlock
*x
, MonoBasicBlock
*t
)
156 t
->flags
|= BB_VISITED
;
158 if (mono_bitset_test_fast (t
->dominators
, x
->dfn
)) {
159 for (i
= 0; i
< t
->out_count
; ++i
) {
160 if (!(t
->flags
& BB_VISITED
)) {
162 check_dominance_frontier (x
, t
->out_bb
[i
]);
164 for (j
= 0; j
< t
->out_bb
[i
]->in_count
; j
++) {
165 if (t
->out_bb
[i
]->in_bb
[j
] == t
)
172 if (!mono_bitset_test_fast (x
->dfrontier
, t
->dfn
)) {
173 printf ("BB%d not in frontier of BB%d\n", t
->block_num
, x
->block_num
);
174 g_assert_not_reached ();
180 * Compute dominance frontiers using the algorithm from the same paper.
183 compute_dominance_frontier (MonoCompile
*cfg
)
188 g_assert (!(cfg
->comp_done
& MONO_COMP_DFRONTIER
));
190 for (i
= 0; i
< cfg
->num_bblocks
; ++i
)
191 cfg
->bblocks
[i
]->flags
&= ~BB_VISITED
;
193 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
194 mem
= mono_mempool_alloc0 (cfg
->mempool
, bitsize
* cfg
->num_bblocks
);
196 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
197 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
198 bb
->dfrontier
= mono_bitset_mem_new (mem
, cfg
->num_bblocks
, 0);
202 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
203 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
205 if (bb
->in_count
> 1) {
206 for (j
= 0; j
< bb
->in_count
; ++j
) {
207 MonoBasicBlock
*p
= bb
->in_bb
[j
];
209 if (p
->dfn
|| (p
== cfg
->bblocks
[0])) {
210 while (p
!= bb
->idom
) {
211 mono_bitset_set_fast (p
->dfrontier
, bb
->dfn
);
220 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
221 MonoBasicBlock
*bb
= cfg
->bblocks
[i
];
223 printf ("DFRONT %s BB%d: ", mono_method_full_name (cfg
->method
, TRUE
), bb
->block_num
);
224 mono_blockset_print (cfg
, bb
->dfrontier
, NULL
, -1);
229 /* this is a check for the dominator frontier */
230 for (i
= 0; i
< m
->num_bblocks
; ++i
) {
231 MonoBasicBlock
*x
= m
->bblocks
[i
];
233 mono_bitset_foreach_bit ((x
->dfrontier
), j
, (m
->num_bblocks
)) {
234 MonoBasicBlock
*w
= m
->bblocks
[j
];
236 /* x must not strictly dominates w */
237 if (mono_bitset_test_fast (w
->dominators
, x
->dfn
) && w
!= x
)
238 g_assert_not_reached ();
240 for (k
= 0; k
< m
->num_bblocks
; ++k
)
241 m
->bblocks
[k
]->flags
&= ~BB_VISITED
;
243 check_dominance_frontier (x
, x
);
248 cfg
->comp_done
|= MONO_COMP_DFRONTIER
;
252 df_set (MonoCompile
*m
, MonoBitSet
* dest
, MonoBitSet
*set
)
256 mono_bitset_foreach_bit (set
, i
, m
->num_bblocks
) {
257 mono_bitset_union (dest
, m
->bblocks
[i
]->dfrontier
);
262 mono_compile_iterated_dfrontier (MonoCompile
*m
, MonoBitSet
*set
)
265 int bitsize
, count1
, count2
;
267 bitsize
= mono_bitset_alloc_size (m
->num_bblocks
, 0);
268 result
= mono_bitset_mem_new (mono_mempool_alloc0 (m
->mempool
, bitsize
), m
->num_bblocks
, 0);
270 df_set (m
, result
, set
);
271 count2
= mono_bitset_count (result
);
274 df_set (m
, result
, result
);
275 count2
= mono_bitset_count (result
);
276 } while (count2
> count1
);
282 mono_compile_dominator_info (MonoCompile
*cfg
, int dom_flags
)
284 if ((dom_flags
& MONO_COMP_DOM
) && !(cfg
->comp_done
& MONO_COMP_DOM
))
285 compute_dominators (cfg
);
286 if ((dom_flags
& MONO_COMP_DFRONTIER
) && !(cfg
->comp_done
& MONO_COMP_DFRONTIER
))
287 compute_dominance_frontier (cfg
);
290 //#define DEBUG_NATURAL_LOOPS
293 * code to detect loops and loop nesting level
296 mono_compute_natural_loops (MonoCompile
*cfg
)
299 MonoBitSet
*in_loop_blocks
;
302 g_assert (!(cfg
->comp_done
& MONO_COMP_LOOPS
));
304 in_loop_blocks
= mono_bitset_new (cfg
->num_bblocks
+ 1, 0);
305 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
306 MonoBasicBlock
*n
= cfg
->bblocks
[i
];
308 for (j
= 0; j
< n
->out_count
; j
++) {
309 MonoBasicBlock
*h
= n
->out_bb
[j
];
310 /* check for back-edge from n to h */
311 if (n
!= h
&& mono_bitset_test_fast (n
->dominators
, h
->dfn
)) {
314 /* already in loop_blocks? */
315 if (h
->loop_blocks
&& g_list_find (h
->loop_blocks
, n
)) {
319 mono_bitset_clear_all (in_loop_blocks
);
320 if (h
->loop_blocks
) {
323 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
324 MonoBasicBlock
*b
= l
->data
;
326 mono_bitset_set_fast (in_loop_blocks
, b
->dfn
);
329 todo
= g_slist_prepend (NULL
, n
);
332 MonoBasicBlock
*cb
= (MonoBasicBlock
*)todo
->data
;
333 todo
= g_slist_delete_link (todo
, todo
);
335 if ((cb
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, cb
->dfn
)) || (!cb
->dfn
&& g_list_find (h
->loop_blocks
, cb
)))
338 h
->loop_blocks
= g_list_prepend (h
->loop_blocks
, cb
);
341 mono_bitset_set_fast (in_loop_blocks
, cb
->dfn
);
343 for (k
= 0; k
< cb
->in_count
; k
++) {
344 MonoBasicBlock
*prev
= cb
->in_bb
[k
];
345 /* add all previous blocks */
346 if (prev
!= h
&& !((prev
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, prev
->dfn
)) || (!prev
->dfn
&& g_list_find (h
->loop_blocks
, prev
)))) {
347 todo
= g_slist_prepend (todo
, prev
);
352 /* add the header if not already there */
353 if (!((h
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, h
->dfn
)) || (!h
->dfn
&& g_list_find (h
->loop_blocks
, h
)))) {
354 h
->loop_blocks
= g_list_prepend (h
->loop_blocks
, h
);
360 mono_bitset_free (in_loop_blocks
);
362 cfg
->comp_done
|= MONO_COMP_LOOPS
;
364 /* Compute loop_body_start for each loop */
365 bb_indexes
= g_new0 (int, cfg
->num_bblocks
);
369 for (i
= 0, bb
= cfg
->bb_entry
; bb
; i
++, bb
= bb
->next_bb
) {
371 bb_indexes
[bb
->dfn
] = i
;
374 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
375 if (cfg
->bblocks
[i
]->loop_blocks
) {
376 /* The loop body start is the first bblock in the order they will be emitted */
377 MonoBasicBlock
*h
= cfg
->bblocks
[i
];
378 MonoBasicBlock
*body_start
= h
;
381 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
382 MonoBasicBlock
*cb
= (MonoBasicBlock
*)l
->data
;
384 if (cb
->dfn
&& bb_indexes
[cb
->dfn
] < bb_indexes
[body_start
->dfn
]) {
389 body_start
->loop_body_start
= 1;
394 #ifdef DEBUG_NATURAL_LOOPS
395 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
396 if (cfg
->bblocks
[i
]->loop_blocks
) {
397 MonoBasicBlock
*h
= (MonoBasicBlock
*)cfg
->bblocks
[i
]->loop_blocks
->data
;
399 printf ("LOOP START %d\n", h
->block_num
);
400 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
401 MonoBasicBlock
*cb
= (MonoBasicBlock
*)l
->data
;
402 printf (" BB%d %d %p\n", cb
->block_num
, cb
->nesting
, cb
->loop_blocks
);
411 clear_idominators (MonoCompile
*cfg
)
415 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
416 if (cfg
->bblocks
[i
]->dominated
) {
417 g_list_free (cfg
->bblocks
[i
]->dominated
);
418 cfg
->bblocks
[i
]->dominated
= NULL
;
422 cfg
->comp_done
&= ~MONO_COMP_IDOM
;
426 clear_loops (MonoCompile
*cfg
)
430 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
431 cfg
->bblocks
[i
]->nesting
= 0;
432 if (cfg
->bblocks
[i
]->loop_blocks
) {
433 g_list_free (cfg
->bblocks
[i
]->loop_blocks
);
434 cfg
->bblocks
[i
]->loop_blocks
= NULL
;
438 cfg
->comp_done
&= ~MONO_COMP_LOOPS
;
442 mono_free_loop_info (MonoCompile
*cfg
)
444 if (cfg
->comp_done
& MONO_COMP_IDOM
)
445 clear_idominators (cfg
);
446 if (cfg
->comp_done
& MONO_COMP_LOOPS
)