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)
12 #include <mono/metadata/debug-helpers.h>
13 #include <mono/metadata/mempool.h>
14 #include <mono/metadata/mempool-internals.h>
20 //#define DEBUG_DOMINATORS
23 * bb->dfn == 0 means either the bblock is ignored by the dfn calculation, or
24 * it is the entry bblock.
26 #define HAS_DFN(bb, entry) ((bb)->dfn || ((bb) == entry))
29 * Compute dominators and immediate dominators using the algorithm in the
30 * paper "A Simple, Fast Dominance Algorithm" by Keith D. Cooper,
31 * Timothy J. Harvey, and Ken Kennedy:
32 * http://citeseer.ist.psu.edu/cooper01simple.html
35 compute_dominators (MonoCompile
*cfg
)
37 int bindex
, i
, bitsize
;
38 MonoBasicBlock
*entry
;
39 MonoBasicBlock
**doms
;
42 g_assert (!(cfg
->comp_done
& MONO_COMP_DOM
));
44 bitsize
= mono_bitset_alloc_size (cfg
->num_bblocks
, 0);
46 entry
= cfg
->bblocks
[0];
48 doms
= g_new0 (MonoBasicBlock
*, cfg
->num_bblocks
);
49 doms
[entry
->dfn
] = entry
;
51 #ifdef DEBUG_DOMINATORS
52 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
= 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 #ifdef DEBUG_DOMINATORS
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
= 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
);
299 //#define DEBUG_NATURAL_LOOPS
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 back-edge from n to h */
320 if (n
!= h
&& mono_bitset_test_fast (n
->dominators
, h
->dfn
)) {
323 /* already in loop_blocks? */
324 if (h
->loop_blocks
&& g_list_find (h
->loop_blocks
, n
)) {
328 mono_bitset_clear_all (in_loop_blocks
);
329 if (h
->loop_blocks
) {
332 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
333 MonoBasicBlock
*b
= l
->data
;
335 mono_bitset_set_fast (in_loop_blocks
, b
->dfn
);
338 todo
= g_slist_prepend (NULL
, n
);
341 MonoBasicBlock
*cb
= (MonoBasicBlock
*)todo
->data
;
342 todo
= g_slist_delete_link (todo
, todo
);
344 if ((cb
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, cb
->dfn
)) || (!cb
->dfn
&& g_list_find (h
->loop_blocks
, cb
)))
347 h
->loop_blocks
= g_list_prepend_mempool (cfg
->mempool
, h
->loop_blocks
, cb
);
350 mono_bitset_set_fast (in_loop_blocks
, cb
->dfn
);
352 for (k
= 0; k
< cb
->in_count
; k
++) {
353 MonoBasicBlock
*prev
= cb
->in_bb
[k
];
354 /* add all previous blocks */
355 if (prev
!= h
&& !((prev
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, prev
->dfn
)) || (!prev
->dfn
&& g_list_find (h
->loop_blocks
, prev
)))) {
356 todo
= g_slist_prepend (todo
, prev
);
361 /* add the header if not already there */
362 if (!((h
->dfn
&& mono_bitset_test_fast (in_loop_blocks
, h
->dfn
)) || (!h
->dfn
&& g_list_find (h
->loop_blocks
, h
)))) {
363 h
->loop_blocks
= g_list_prepend_mempool (cfg
->mempool
, h
->loop_blocks
, h
);
369 mono_bitset_free (in_loop_blocks
);
371 cfg
->comp_done
|= MONO_COMP_LOOPS
;
373 /* Compute loop_body_start for each loop */
374 bb_indexes
= g_new0 (int, cfg
->num_bblocks
);
378 for (i
= 0, bb
= cfg
->bb_entry
; bb
; i
++, bb
= bb
->next_bb
) {
380 bb_indexes
[bb
->dfn
] = i
;
383 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
384 if (cfg
->bblocks
[i
]->loop_blocks
) {
385 /* The loop body start is the first bblock in the order they will be emitted */
386 MonoBasicBlock
*h
= cfg
->bblocks
[i
];
387 MonoBasicBlock
*body_start
= h
;
388 #if defined(__native_client_codegen__)
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 #if defined(__native_client_codegen__)
402 /* Instrument the loop (GC back branch safe point) */
403 MONO_INST_NEW (cfg
, inst
, OP_NACL_GC_SAFE_POINT
);
404 inst
->dreg
= mono_alloc_dreg (cfg
, STACK_I4
);
405 mono_bblock_insert_before_ins (body_start
, NULL
, inst
);
407 body_start
->loop_body_start
= 1;
412 #ifdef DEBUG_NATURAL_LOOPS
413 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
414 if (cfg
->bblocks
[i
]->loop_blocks
) {
415 MonoBasicBlock
*h
= (MonoBasicBlock
*)cfg
->bblocks
[i
]->loop_blocks
->data
;
417 printf ("LOOP START %d\n", h
->block_num
);
418 for (l
= h
->loop_blocks
; l
; l
= l
->next
) {
419 MonoBasicBlock
*cb
= (MonoBasicBlock
*)l
->data
;
420 printf (" BB%d %d %p\n", cb
->block_num
, cb
->nesting
, cb
->loop_blocks
);
429 clear_idominators (MonoCompile
*cfg
)
433 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
434 if (cfg
->bblocks
[i
]->dominated
) {
435 cfg
->bblocks
[i
]->dominated
= NULL
;
439 cfg
->comp_done
&= ~MONO_COMP_IDOM
;
443 clear_loops (MonoCompile
*cfg
)
447 for (i
= 0; i
< cfg
->num_bblocks
; ++i
) {
448 cfg
->bblocks
[i
]->nesting
= 0;
449 cfg
->bblocks
[i
]->loop_blocks
= NULL
;
452 cfg
->comp_done
&= ~MONO_COMP_LOOPS
;
456 mono_free_loop_info (MonoCompile
*cfg
)
458 if (cfg
->comp_done
& MONO_COMP_IDOM
)
459 clear_idominators (cfg
);
460 if (cfg
->comp_done
& MONO_COMP_LOOPS
)
464 #else /* DISABLE_JIT */
467 mono_free_loop_info (MonoCompile
*cfg
)
471 #endif /* DISABLE_JIT */