]>
Commit | Line | Data |
---|---|---|
f8032688 MM |
1 | /* Calculate (post)dominators in slightly super-linear time. |
2 | Copyright (C) 2000 Free Software Foundation, Inc. | |
3 | Contributed by Michael Matz (matz@ifh.de). | |
3a538a66 | 4 | |
1322177d | 5 | This file is part of GCC. |
3a538a66 | 6 | |
1322177d LB |
7 | GCC is free software; you can redistribute it and/or modify it |
8 | under the terms of the GNU General Public License as published by | |
f8032688 MM |
9 | the Free Software Foundation; either version 2, or (at your option) |
10 | any later version. | |
11 | ||
1322177d LB |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT |
13 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
14 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
15 | License for more details. | |
f8032688 MM |
16 | |
17 | You should have received a copy of the GNU General Public License | |
1322177d LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
f8032688 MM |
21 | |
22 | /* This file implements the well known algorithm from Lengauer and Tarjan | |
23 | to compute the dominators in a control flow graph. A basic block D is said | |
24 | to dominate another block X, when all paths from the entry node of the CFG | |
25 | to X go also over D. The dominance relation is a transitive reflexive | |
26 | relation and its minimal transitive reduction is a tree, called the | |
27 | dominator tree. So for each block X besides the entry block exists a | |
28 | block I(X), called the immediate dominator of X, which is the parent of X | |
29 | in the dominator tree. | |
30 | ||
a1f300c0 | 31 | The algorithm computes this dominator tree implicitly by computing for |
f8032688 MM |
32 | each block its immediate dominator. We use tree balancing and path |
33 | compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very | |
34 | slowly growing functional inverse of the Ackerman function. */ | |
35 | ||
36 | #include "config.h" | |
37 | #include "system.h" | |
38 | #include "rtl.h" | |
39 | #include "hard-reg-set.h" | |
40 | #include "basic-block.h" | |
8a67e083 | 41 | #include "errors.h" |
355be0dc | 42 | #include "et-forest.h" |
f8032688 | 43 | |
355be0dc JH |
44 | struct dominance_info |
45 | { | |
46 | et_forest_t forest; | |
47 | varray_type varray; | |
48 | }; | |
49 | ||
50 | #define BB_NODE(info, bb) \ | |
51 | ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2)) | |
52 | #define SET_BB_NODE(info, bb, node) \ | |
53 | (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node)) | |
f8032688 MM |
54 | |
55 | /* We name our nodes with integers, beginning with 1. Zero is reserved for | |
56 | 'undefined' or 'end of list'. The name of each node is given by the dfs | |
57 | number of the corresponding basic block. Please note, that we include the | |
58 | artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to | |
59 | support multiple entry points. As it has no real basic block index we use | |
d55bc081 | 60 | 'last_basic_block' for that. Its dfs number is of course 1. */ |
f8032688 MM |
61 | |
62 | /* Type of Basic Block aka. TBB */ | |
63 | typedef unsigned int TBB; | |
64 | ||
65 | /* We work in a poor-mans object oriented fashion, and carry an instance of | |
66 | this structure through all our 'methods'. It holds various arrays | |
67 | reflecting the (sub)structure of the flowgraph. Most of them are of type | |
68 | TBB and are also indexed by TBB. */ | |
69 | ||
70 | struct dom_info | |
71 | { | |
72 | /* The parent of a node in the DFS tree. */ | |
73 | TBB *dfs_parent; | |
74 | /* For a node x key[x] is roughly the node nearest to the root from which | |
75 | exists a way to x only over nodes behind x. Such a node is also called | |
76 | semidominator. */ | |
77 | TBB *key; | |
78 | /* The value in path_min[x] is the node y on the path from x to the root of | |
79 | the tree x is in with the smallest key[y]. */ | |
80 | TBB *path_min; | |
81 | /* bucket[x] points to the first node of the set of nodes having x as key. */ | |
82 | TBB *bucket; | |
83 | /* And next_bucket[x] points to the next node. */ | |
84 | TBB *next_bucket; | |
85 | /* After the algorithm is done, dom[x] contains the immediate dominator | |
86 | of x. */ | |
87 | TBB *dom; | |
88 | ||
89 | /* The following few fields implement the structures needed for disjoint | |
90 | sets. */ | |
91 | /* set_chain[x] is the next node on the path from x to the representant | |
92 | of the set containing x. If set_chain[x]==0 then x is a root. */ | |
93 | TBB *set_chain; | |
94 | /* set_size[x] is the number of elements in the set named by x. */ | |
95 | unsigned int *set_size; | |
96 | /* set_child[x] is used for balancing the tree representing a set. It can | |
97 | be understood as the next sibling of x. */ | |
98 | TBB *set_child; | |
99 | ||
100 | /* If b is the number of a basic block (BB->index), dfs_order[b] is the | |
101 | number of that node in DFS order counted from 1. This is an index | |
102 | into most of the other arrays in this structure. */ | |
103 | TBB *dfs_order; | |
a1f300c0 | 104 | /* If x is the DFS-index of a node which corresponds with an basic block, |
f8032688 MM |
105 | dfs_to_bb[x] is that basic block. Note, that in our structure there are |
106 | more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb | |
107 | is true for every basic block bb, but not the opposite. */ | |
108 | basic_block *dfs_to_bb; | |
109 | ||
30f7a378 | 110 | /* This is the next free DFS number when creating the DFS tree or forest. */ |
f8032688 MM |
111 | unsigned int dfsnum; |
112 | /* The number of nodes in the DFS tree (==dfsnum-1). */ | |
113 | unsigned int nodes; | |
114 | }; | |
115 | ||
116 | static void init_dom_info PARAMS ((struct dom_info *)); | |
117 | static void free_dom_info PARAMS ((struct dom_info *)); | |
118 | static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *, | |
119 | basic_block, | |
120 | enum cdi_direction)); | |
121 | static void calc_dfs_tree PARAMS ((struct dom_info *, | |
122 | enum cdi_direction)); | |
123 | static void compress PARAMS ((struct dom_info *, TBB)); | |
124 | static TBB eval PARAMS ((struct dom_info *, TBB)); | |
125 | static void link_roots PARAMS ((struct dom_info *, TBB, TBB)); | |
126 | static void calc_idoms PARAMS ((struct dom_info *, | |
127 | enum cdi_direction)); | |
355be0dc | 128 | void debug_dominance_info PARAMS ((dominance_info)); |
f8032688 MM |
129 | |
130 | /* Helper macro for allocating and initializing an array, | |
131 | for aesthetic reasons. */ | |
132 | #define init_ar(var, type, num, content) \ | |
3a538a66 KH |
133 | do \ |
134 | { \ | |
135 | unsigned int i = 1; /* Catch content == i. */ \ | |
136 | if (! (content)) \ | |
137 | (var) = (type *) xcalloc ((num), sizeof (type)); \ | |
138 | else \ | |
139 | { \ | |
140 | (var) = (type *) xmalloc ((num) * sizeof (type)); \ | |
141 | for (i = 0; i < num; i++) \ | |
142 | (var)[i] = (content); \ | |
143 | } \ | |
144 | } \ | |
145 | while (0) | |
f8032688 MM |
146 | |
147 | /* Allocate all needed memory in a pessimistic fashion (so we round up). | |
148 | This initialises the contents of DI, which already must be allocated. */ | |
149 | ||
150 | static void | |
151 | init_dom_info (di) | |
152 | struct dom_info *di; | |
153 | { | |
0b17ab2f | 154 | /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or |
f8032688 | 155 | EXIT_BLOCK. */ |
0b17ab2f | 156 | unsigned int num = n_basic_blocks + 1 + 1; |
f8032688 MM |
157 | init_ar (di->dfs_parent, TBB, num, 0); |
158 | init_ar (di->path_min, TBB, num, i); | |
159 | init_ar (di->key, TBB, num, i); | |
160 | init_ar (di->dom, TBB, num, 0); | |
161 | ||
162 | init_ar (di->bucket, TBB, num, 0); | |
163 | init_ar (di->next_bucket, TBB, num, 0); | |
164 | ||
165 | init_ar (di->set_chain, TBB, num, 0); | |
166 | init_ar (di->set_size, unsigned int, num, 1); | |
167 | init_ar (di->set_child, TBB, num, 0); | |
168 | ||
d55bc081 | 169 | init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0); |
f8032688 MM |
170 | init_ar (di->dfs_to_bb, basic_block, num, 0); |
171 | ||
172 | di->dfsnum = 1; | |
173 | di->nodes = 0; | |
174 | } | |
175 | ||
176 | #undef init_ar | |
177 | ||
178 | /* Free all allocated memory in DI, but not DI itself. */ | |
179 | ||
180 | static void | |
181 | free_dom_info (di) | |
182 | struct dom_info *di; | |
183 | { | |
184 | free (di->dfs_parent); | |
185 | free (di->path_min); | |
186 | free (di->key); | |
187 | free (di->dom); | |
188 | free (di->bucket); | |
189 | free (di->next_bucket); | |
190 | free (di->set_chain); | |
191 | free (di->set_size); | |
192 | free (di->set_child); | |
193 | free (di->dfs_order); | |
194 | free (di->dfs_to_bb); | |
195 | } | |
196 | ||
197 | /* The nonrecursive variant of creating a DFS tree. DI is our working | |
198 | structure, BB the starting basic block for this tree and REVERSE | |
199 | is true, if predecessors should be visited instead of successors of a | |
200 | node. After this is done all nodes reachable from BB were visited, have | |
201 | assigned their dfs number and are linked together to form a tree. */ | |
202 | ||
203 | static void | |
204 | calc_dfs_tree_nonrec (di, bb, reverse) | |
205 | struct dom_info *di; | |
206 | basic_block bb; | |
207 | enum cdi_direction reverse; | |
208 | { | |
30f7a378 | 209 | /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */ |
f8032688 MM |
210 | /* We call this _only_ if bb is not already visited. */ |
211 | edge e; | |
212 | TBB child_i, my_i = 0; | |
213 | edge *stack; | |
214 | int sp; | |
215 | /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward | |
216 | problem). */ | |
217 | basic_block en_block; | |
218 | /* Ending block. */ | |
219 | basic_block ex_block; | |
220 | ||
0b17ab2f | 221 | stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge)); |
f8032688 MM |
222 | sp = 0; |
223 | ||
224 | /* Initialize our border blocks, and the first edge. */ | |
225 | if (reverse) | |
226 | { | |
227 | e = bb->pred; | |
228 | en_block = EXIT_BLOCK_PTR; | |
229 | ex_block = ENTRY_BLOCK_PTR; | |
230 | } | |
231 | else | |
232 | { | |
233 | e = bb->succ; | |
234 | en_block = ENTRY_BLOCK_PTR; | |
235 | ex_block = EXIT_BLOCK_PTR; | |
236 | } | |
237 | ||
238 | /* When the stack is empty we break out of this loop. */ | |
239 | while (1) | |
240 | { | |
241 | basic_block bn; | |
242 | ||
243 | /* This loop traverses edges e in depth first manner, and fills the | |
244 | stack. */ | |
245 | while (e) | |
246 | { | |
247 | edge e_next; | |
248 | ||
249 | /* Deduce from E the current and the next block (BB and BN), and the | |
250 | next edge. */ | |
251 | if (reverse) | |
252 | { | |
253 | bn = e->src; | |
254 | ||
255 | /* If the next node BN is either already visited or a border | |
256 | block the current edge is useless, and simply overwritten | |
257 | with the next edge out of the current node. */ | |
0b17ab2f | 258 | if (bn == ex_block || di->dfs_order[bn->index]) |
f8032688 MM |
259 | { |
260 | e = e->pred_next; | |
261 | continue; | |
262 | } | |
263 | bb = e->dest; | |
264 | e_next = bn->pred; | |
265 | } | |
266 | else | |
267 | { | |
268 | bn = e->dest; | |
0b17ab2f | 269 | if (bn == ex_block || di->dfs_order[bn->index]) |
f8032688 MM |
270 | { |
271 | e = e->succ_next; | |
272 | continue; | |
273 | } | |
274 | bb = e->src; | |
275 | e_next = bn->succ; | |
276 | } | |
277 | ||
278 | if (bn == en_block) | |
279 | abort (); | |
280 | ||
281 | /* Fill the DFS tree info calculatable _before_ recursing. */ | |
282 | if (bb != en_block) | |
0b17ab2f | 283 | my_i = di->dfs_order[bb->index]; |
f8032688 | 284 | else |
d55bc081 | 285 | my_i = di->dfs_order[last_basic_block]; |
0b17ab2f | 286 | child_i = di->dfs_order[bn->index] = di->dfsnum++; |
f8032688 MM |
287 | di->dfs_to_bb[child_i] = bn; |
288 | di->dfs_parent[child_i] = my_i; | |
289 | ||
290 | /* Save the current point in the CFG on the stack, and recurse. */ | |
291 | stack[sp++] = e; | |
292 | e = e_next; | |
293 | } | |
294 | ||
295 | if (!sp) | |
296 | break; | |
297 | e = stack[--sp]; | |
298 | ||
299 | /* OK. The edge-list was exhausted, meaning normally we would | |
300 | end the recursion. After returning from the recursive call, | |
301 | there were (may be) other statements which were run after a | |
302 | child node was completely considered by DFS. Here is the | |
303 | point to do it in the non-recursive variant. | |
304 | E.g. The block just completed is in e->dest for forward DFS, | |
305 | the block not yet completed (the parent of the one above) | |
306 | in e->src. This could be used e.g. for computing the number of | |
307 | descendants or the tree depth. */ | |
308 | if (reverse) | |
309 | e = e->pred_next; | |
310 | else | |
311 | e = e->succ_next; | |
312 | } | |
313 | free (stack); | |
314 | } | |
315 | ||
316 | /* The main entry for calculating the DFS tree or forest. DI is our working | |
317 | structure and REVERSE is true, if we are interested in the reverse flow | |
318 | graph. In that case the result is not necessarily a tree but a forest, | |
319 | because there may be nodes from which the EXIT_BLOCK is unreachable. */ | |
320 | ||
321 | static void | |
322 | calc_dfs_tree (di, reverse) | |
323 | struct dom_info *di; | |
324 | enum cdi_direction reverse; | |
325 | { | |
326 | /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ | |
327 | basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; | |
d55bc081 | 328 | di->dfs_order[last_basic_block] = di->dfsnum; |
f8032688 MM |
329 | di->dfs_to_bb[di->dfsnum] = begin; |
330 | di->dfsnum++; | |
331 | ||
332 | calc_dfs_tree_nonrec (di, begin, reverse); | |
333 | ||
334 | if (reverse) | |
335 | { | |
336 | /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. | |
337 | They are reverse-unreachable. In the dom-case we disallow such | |
338 | nodes, but in post-dom we have to deal with them, so we simply | |
339 | include them in the DFS tree which actually becomes a forest. */ | |
e0082a72 ZD |
340 | basic_block b; |
341 | FOR_EACH_BB_REVERSE (b) | |
f8032688 | 342 | { |
0b17ab2f | 343 | if (di->dfs_order[b->index]) |
f8032688 | 344 | continue; |
0b17ab2f | 345 | di->dfs_order[b->index] = di->dfsnum; |
f8032688 MM |
346 | di->dfs_to_bb[di->dfsnum] = b; |
347 | di->dfsnum++; | |
348 | calc_dfs_tree_nonrec (di, b, reverse); | |
349 | } | |
350 | } | |
351 | ||
352 | di->nodes = di->dfsnum - 1; | |
353 | ||
354 | /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ | |
0b17ab2f | 355 | if (di->nodes != (unsigned int) n_basic_blocks + 1) |
f8032688 MM |
356 | abort (); |
357 | } | |
358 | ||
359 | /* Compress the path from V to the root of its set and update path_min at the | |
360 | same time. After compress(di, V) set_chain[V] is the root of the set V is | |
361 | in and path_min[V] is the node with the smallest key[] value on the path | |
362 | from V to that root. */ | |
363 | ||
364 | static void | |
365 | compress (di, v) | |
366 | struct dom_info *di; | |
367 | TBB v; | |
368 | { | |
369 | /* Btw. It's not worth to unrecurse compress() as the depth is usually not | |
370 | greater than 5 even for huge graphs (I've not seen call depth > 4). | |
371 | Also performance wise compress() ranges _far_ behind eval(). */ | |
372 | TBB parent = di->set_chain[v]; | |
373 | if (di->set_chain[parent]) | |
374 | { | |
375 | compress (di, parent); | |
376 | if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) | |
377 | di->path_min[v] = di->path_min[parent]; | |
378 | di->set_chain[v] = di->set_chain[parent]; | |
379 | } | |
380 | } | |
381 | ||
382 | /* Compress the path from V to the set root of V if needed (when the root has | |
383 | changed since the last call). Returns the node with the smallest key[] | |
384 | value on the path from V to the root. */ | |
385 | ||
386 | static inline TBB | |
387 | eval (di, v) | |
388 | struct dom_info *di; | |
389 | TBB v; | |
390 | { | |
391 | /* The representant of the set V is in, also called root (as the set | |
392 | representation is a tree). */ | |
393 | TBB rep = di->set_chain[v]; | |
394 | ||
395 | /* V itself is the root. */ | |
396 | if (!rep) | |
397 | return di->path_min[v]; | |
398 | ||
399 | /* Compress only if necessary. */ | |
400 | if (di->set_chain[rep]) | |
401 | { | |
402 | compress (di, v); | |
403 | rep = di->set_chain[v]; | |
404 | } | |
405 | ||
406 | if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) | |
407 | return di->path_min[v]; | |
408 | else | |
409 | return di->path_min[rep]; | |
410 | } | |
411 | ||
412 | /* This essentially merges the two sets of V and W, giving a single set with | |
413 | the new root V. The internal representation of these disjoint sets is a | |
414 | balanced tree. Currently link(V,W) is only used with V being the parent | |
415 | of W. */ | |
416 | ||
417 | static void | |
418 | link_roots (di, v, w) | |
419 | struct dom_info *di; | |
420 | TBB v, w; | |
421 | { | |
422 | TBB s = w; | |
423 | ||
424 | /* Rebalance the tree. */ | |
425 | while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) | |
426 | { | |
427 | if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] | |
428 | >= 2 * di->set_size[di->set_child[s]]) | |
429 | { | |
430 | di->set_chain[di->set_child[s]] = s; | |
431 | di->set_child[s] = di->set_child[di->set_child[s]]; | |
432 | } | |
433 | else | |
434 | { | |
435 | di->set_size[di->set_child[s]] = di->set_size[s]; | |
436 | s = di->set_chain[s] = di->set_child[s]; | |
437 | } | |
438 | } | |
439 | ||
440 | di->path_min[s] = di->path_min[w]; | |
441 | di->set_size[v] += di->set_size[w]; | |
442 | if (di->set_size[v] < 2 * di->set_size[w]) | |
443 | { | |
444 | TBB tmp = s; | |
445 | s = di->set_child[v]; | |
446 | di->set_child[v] = tmp; | |
447 | } | |
448 | ||
449 | /* Merge all subtrees. */ | |
450 | while (s) | |
451 | { | |
452 | di->set_chain[s] = v; | |
453 | s = di->set_child[s]; | |
454 | } | |
455 | } | |
456 | ||
457 | /* This calculates the immediate dominators (or post-dominators if REVERSE is | |
458 | true). DI is our working structure and should hold the DFS forest. | |
459 | On return the immediate dominator to node V is in di->dom[V]. */ | |
460 | ||
461 | static void | |
462 | calc_idoms (di, reverse) | |
463 | struct dom_info *di; | |
464 | enum cdi_direction reverse; | |
465 | { | |
466 | TBB v, w, k, par; | |
467 | basic_block en_block; | |
468 | if (reverse) | |
469 | en_block = EXIT_BLOCK_PTR; | |
470 | else | |
471 | en_block = ENTRY_BLOCK_PTR; | |
472 | ||
473 | /* Go backwards in DFS order, to first look at the leafs. */ | |
474 | v = di->nodes; | |
475 | while (v > 1) | |
476 | { | |
477 | basic_block bb = di->dfs_to_bb[v]; | |
478 | edge e, e_next; | |
479 | ||
480 | par = di->dfs_parent[v]; | |
481 | k = v; | |
482 | if (reverse) | |
483 | e = bb->succ; | |
484 | else | |
485 | e = bb->pred; | |
486 | ||
487 | /* Search all direct predecessors for the smallest node with a path | |
488 | to them. That way we have the smallest node with also a path to | |
489 | us only over nodes behind us. In effect we search for our | |
490 | semidominator. */ | |
491 | for (; e; e = e_next) | |
492 | { | |
493 | TBB k1; | |
494 | basic_block b; | |
495 | ||
496 | if (reverse) | |
497 | { | |
498 | b = e->dest; | |
499 | e_next = e->succ_next; | |
500 | } | |
501 | else | |
502 | { | |
503 | b = e->src; | |
504 | e_next = e->pred_next; | |
505 | } | |
506 | if (b == en_block) | |
d55bc081 | 507 | k1 = di->dfs_order[last_basic_block]; |
f8032688 | 508 | else |
0b17ab2f | 509 | k1 = di->dfs_order[b->index]; |
f8032688 MM |
510 | |
511 | /* Call eval() only if really needed. If k1 is above V in DFS tree, | |
512 | then we know, that eval(k1) == k1 and key[k1] == k1. */ | |
513 | if (k1 > v) | |
514 | k1 = di->key[eval (di, k1)]; | |
515 | if (k1 < k) | |
516 | k = k1; | |
517 | } | |
518 | ||
519 | di->key[v] = k; | |
520 | link_roots (di, par, v); | |
521 | di->next_bucket[v] = di->bucket[k]; | |
522 | di->bucket[k] = v; | |
523 | ||
524 | /* Transform semidominators into dominators. */ | |
525 | for (w = di->bucket[par]; w; w = di->next_bucket[w]) | |
526 | { | |
527 | k = eval (di, w); | |
528 | if (di->key[k] < di->key[w]) | |
529 | di->dom[w] = k; | |
530 | else | |
531 | di->dom[w] = par; | |
532 | } | |
533 | /* We don't need to cleanup next_bucket[]. */ | |
534 | di->bucket[par] = 0; | |
535 | v--; | |
536 | } | |
537 | ||
a1f300c0 | 538 | /* Explicitly define the dominators. */ |
f8032688 MM |
539 | di->dom[1] = 0; |
540 | for (v = 2; v <= di->nodes; v++) | |
541 | if (di->dom[v] != di->key[v]) | |
542 | di->dom[v] = di->dom[di->dom[v]]; | |
543 | } | |
544 | ||
f8032688 | 545 | /* The main entry point into this module. IDOM is an integer array with room |
d55bc081 ZD |
546 | for last_basic_block integers, DOMS is a preallocated sbitmap array having |
547 | room for last_basic_block^2 bits, and POST is true if the caller wants to | |
f8032688 MM |
548 | know post-dominators. |
549 | ||
550 | On return IDOM[i] will be the BB->index of the immediate (post) dominator | |
551 | of basic block i, and DOMS[i] will have set bit j if basic block j is a | |
552 | (post)dominator for block i. | |
553 | ||
554 | Either IDOM or DOMS may be NULL (meaning the caller is not interested in | |
555 | immediate resp. all dominators). */ | |
556 | ||
355be0dc JH |
557 | dominance_info |
558 | calculate_dominance_info (reverse) | |
f8032688 MM |
559 | enum cdi_direction reverse; |
560 | { | |
561 | struct dom_info di; | |
355be0dc JH |
562 | dominance_info info; |
563 | basic_block b; | |
564 | ||
565 | /* allocate structure for dominance information. */ | |
566 | info = xmalloc (sizeof (struct dominance_info)); | |
567 | info->forest = et_forest_create (); | |
568 | VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info"); | |
569 | ||
570 | /* Add the two well-known basic blocks. */ | |
571 | SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest, | |
572 | ENTRY_BLOCK_PTR)); | |
573 | SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest, | |
574 | EXIT_BLOCK_PTR)); | |
575 | FOR_EACH_BB (b) | |
576 | SET_BB_NODE (info, b, et_forest_add_node (info->forest, b)); | |
f8032688 | 577 | |
f8032688 MM |
578 | init_dom_info (&di); |
579 | calc_dfs_tree (&di, reverse); | |
580 | calc_idoms (&di, reverse); | |
581 | ||
355be0dc JH |
582 | |
583 | FOR_EACH_BB (b) | |
f8032688 | 584 | { |
355be0dc | 585 | TBB d = di.dom[di.dfs_order[b->index]]; |
e0082a72 | 586 | |
355be0dc JH |
587 | if (di.dfs_to_bb[d]) |
588 | et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b)); | |
589 | } | |
590 | ||
591 | free_dom_info (&di); | |
592 | return info; | |
593 | } | |
594 | ||
595 | /* Free dominance information. */ | |
596 | void | |
597 | free_dominance_info (info) | |
598 | dominance_info info; | |
599 | { | |
600 | basic_block bb; | |
601 | ||
602 | /* Allow users to create new basic block without setting up the dominance | |
603 | information for them. */ | |
604 | FOR_EACH_BB (bb) | |
605 | if (bb->index < (int)(info->varray->num_elements - 2) | |
606 | && BB_NODE (info, bb)) | |
607 | delete_from_dominance_info (info, bb); | |
608 | delete_from_dominance_info (info, ENTRY_BLOCK_PTR); | |
609 | delete_from_dominance_info (info, EXIT_BLOCK_PTR); | |
610 | et_forest_delete (info->forest); | |
611 | VARRAY_GROW (info->varray, 0); | |
612 | free (info); | |
613 | } | |
614 | ||
615 | /* Return the immediate dominator of basic block BB. */ | |
616 | basic_block | |
617 | get_immediate_dominator (dom, bb) | |
618 | dominance_info dom; | |
619 | basic_block bb; | |
620 | { | |
621 | return et_forest_node_value (dom->forest, | |
622 | et_forest_parent (dom->forest, | |
623 | BB_NODE (dom, bb))); | |
624 | } | |
625 | ||
626 | /* Set the immediate dominator of the block possibly removing | |
627 | existing edge. NULL can be used to remove any edge. */ | |
628 | inline void | |
629 | set_immediate_dominator (dom, bb, dominated_by) | |
630 | dominance_info dom; | |
631 | basic_block bb, dominated_by; | |
632 | { | |
633 | void *aux_bb_node; | |
634 | et_forest_node_t bb_node = BB_NODE (dom, bb); | |
635 | ||
636 | aux_bb_node = et_forest_parent (dom->forest, bb_node); | |
637 | if (aux_bb_node) | |
638 | et_forest_remove_edge (dom->forest, aux_bb_node, bb_node); | |
639 | if (dominated_by != NULL) | |
640 | { | |
641 | if (bb == dominated_by) | |
642 | abort (); | |
643 | if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node)) | |
644 | abort (); | |
645 | } | |
646 | } | |
647 | ||
648 | /* Store all basic blocks dominated by BB into BBS and return their number. */ | |
649 | int | |
650 | get_dominated_by (dom, bb, bbs) | |
651 | dominance_info dom; | |
652 | basic_block bb; | |
653 | basic_block **bbs; | |
654 | { | |
655 | int n, i; | |
656 | ||
657 | *bbs = xmalloc (n_basic_blocks * sizeof (basic_block)); | |
658 | n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs); | |
659 | for (i = 0; i < n; i++) | |
660 | (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]); | |
661 | return n; | |
662 | } | |
663 | ||
664 | /* Redirect all edges pointing to BB to TO. */ | |
665 | void | |
666 | redirect_immediate_dominators (dom, bb, to) | |
667 | dominance_info dom; | |
668 | basic_block bb; | |
669 | basic_block to; | |
670 | { | |
671 | et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block)); | |
672 | et_forest_node_t node = BB_NODE (dom, bb); | |
673 | et_forest_node_t node2 = BB_NODE (dom, to); | |
674 | int n = et_forest_enumerate_sons (dom->forest, node, bbs); | |
675 | int i; | |
676 | ||
677 | for (i = 0; i < n; i++) | |
678 | { | |
679 | et_forest_remove_edge (dom->forest, node, bbs[i]); | |
680 | et_forest_add_edge (dom->forest, node2, bbs[i]); | |
681 | } | |
682 | free (bbs); | |
683 | } | |
684 | ||
685 | /* Find first basic block in the tree dominating both BB1 and BB2. */ | |
686 | basic_block | |
687 | nearest_common_dominator (dom, bb1, bb2) | |
688 | dominance_info dom; | |
689 | basic_block bb1; | |
690 | basic_block bb2; | |
691 | { | |
692 | if (!bb1) | |
693 | return bb2; | |
694 | if (!bb2) | |
695 | return bb1; | |
696 | return et_forest_node_value (dom->forest, | |
697 | et_forest_common_ancestor (dom->forest, | |
698 | BB_NODE (dom, bb1), | |
699 | BB_NODE (dom, | |
700 | bb2))); | |
701 | } | |
702 | ||
703 | /* Return TRUE in case BB1 is dominated by BB2. */ | |
704 | bool | |
705 | dominated_by_p (dom, bb1, bb2) | |
706 | dominance_info dom; | |
707 | basic_block bb1; | |
708 | basic_block bb2; | |
709 | { | |
710 | return nearest_common_dominator (dom, bb1, bb2) == bb2; | |
711 | } | |
712 | ||
713 | /* Verify invariants of dominator structure. */ | |
714 | void | |
715 | verify_dominators (dom) | |
716 | dominance_info dom; | |
717 | { | |
718 | int err = 0; | |
719 | basic_block bb; | |
720 | ||
721 | FOR_EACH_BB (bb) | |
722 | { | |
723 | basic_block dom_bb; | |
724 | ||
725 | dom_bb = recount_dominator (dom, bb); | |
726 | if (dom_bb != get_immediate_dominator (dom, bb)) | |
f8032688 | 727 | { |
355be0dc JH |
728 | error ("dominator of %d should be %d, not %d", |
729 | bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index); | |
730 | err = 1; | |
731 | } | |
732 | } | |
733 | if (err) | |
734 | abort (); | |
735 | } | |
736 | ||
737 | /* Recount dominator of BB. */ | |
738 | basic_block | |
739 | recount_dominator (dom, bb) | |
740 | dominance_info dom; | |
741 | basic_block bb; | |
742 | { | |
743 | basic_block dom_bb = NULL; | |
744 | edge e; | |
745 | ||
746 | for (e = bb->pred; e; e = e->pred_next) | |
747 | { | |
748 | if (!dominated_by_p (dom, e->src, bb)) | |
749 | dom_bb = nearest_common_dominator (dom, dom_bb, e->src); | |
750 | } | |
f8032688 | 751 | |
355be0dc JH |
752 | return dom_bb; |
753 | } | |
754 | ||
755 | /* Iteratively recount dominators of BBS. The change is supposed to be local | |
756 | and not to grow further. */ | |
757 | void | |
758 | iterate_fix_dominators (dom, bbs, n) | |
759 | dominance_info dom; | |
760 | basic_block *bbs; | |
761 | int n; | |
762 | { | |
763 | int i, changed = 1; | |
764 | basic_block old_dom, new_dom; | |
765 | ||
766 | while (changed) | |
767 | { | |
768 | changed = 0; | |
769 | for (i = 0; i < n; i++) | |
770 | { | |
771 | old_dom = get_immediate_dominator (dom, bbs[i]); | |
772 | new_dom = recount_dominator (dom, bbs[i]); | |
773 | if (old_dom != new_dom) | |
774 | { | |
775 | changed = 1; | |
776 | set_immediate_dominator (dom, bbs[i], new_dom); | |
777 | } | |
f8032688 MM |
778 | } |
779 | } | |
355be0dc | 780 | } |
f8032688 | 781 | |
355be0dc JH |
782 | void |
783 | add_to_dominance_info (dom, bb) | |
784 | dominance_info dom; | |
785 | basic_block bb; | |
786 | { | |
787 | VARRAY_GROW (dom->varray, last_basic_block + 3); | |
788 | #ifdef ENABLE_CHECKING | |
789 | if (BB_NODE (dom, bb)) | |
790 | abort (); | |
791 | #endif | |
792 | SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb)); | |
793 | } | |
794 | ||
795 | void | |
796 | delete_from_dominance_info (dom, bb) | |
797 | dominance_info dom; | |
798 | basic_block bb; | |
799 | { | |
800 | et_forest_remove_node (dom->forest, BB_NODE (dom, bb)); | |
801 | SET_BB_NODE (dom, bb, NULL); | |
802 | } | |
803 | ||
804 | void | |
805 | debug_dominance_info (dom) | |
806 | dominance_info dom; | |
807 | { | |
808 | basic_block bb, bb2; | |
809 | FOR_EACH_BB (bb) | |
810 | if ((bb2 = get_immediate_dominator (dom, bb))) | |
811 | fprintf (stderr, "%i %i\n", bb->index, bb2->index); | |
f8032688 | 812 | } |