|
0
|
1 /* Calculate (post)dominators in slightly super-linear time.
|
|
|
2 Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008 Free
|
|
|
3 Software Foundation, Inc.
|
|
|
4 Contributed by Michael Matz (matz@ifh.de).
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify it
|
|
|
9 under the terms of the GNU General Public License as published by
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
11 any later version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT
|
|
|
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
|
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
|
|
16 License for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
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
|
|
|
31 The algorithm computes this dominator tree implicitly by computing for
|
|
|
32 each block its immediate dominator. We use tree balancing and path
|
|
|
33 compression, so it's 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 "coretypes.h"
|
|
|
39 #include "tm.h"
|
|
|
40 #include "rtl.h"
|
|
|
41 #include "hard-reg-set.h"
|
|
|
42 #include "obstack.h"
|
|
|
43 #include "basic-block.h"
|
|
|
44 #include "toplev.h"
|
|
|
45 #include "et-forest.h"
|
|
|
46 #include "timevar.h"
|
|
|
47 #include "vecprim.h"
|
|
|
48 #include "pointer-set.h"
|
|
|
49 #include "graphds.h"
|
|
|
50
|
|
|
51 /* We name our nodes with integers, beginning with 1. Zero is reserved for
|
|
|
52 'undefined' or 'end of list'. The name of each node is given by the dfs
|
|
|
53 number of the corresponding basic block. Please note, that we include the
|
|
|
54 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
|
|
|
55 support multiple entry points. Its dfs number is of course 1. */
|
|
|
56
|
|
|
57 /* Type of Basic Block aka. TBB */
|
|
|
58 typedef unsigned int TBB;
|
|
|
59
|
|
|
60 /* We work in a poor-mans object oriented fashion, and carry an instance of
|
|
|
61 this structure through all our 'methods'. It holds various arrays
|
|
|
62 reflecting the (sub)structure of the flowgraph. Most of them are of type
|
|
|
63 TBB and are also indexed by TBB. */
|
|
|
64
|
|
|
65 struct dom_info
|
|
|
66 {
|
|
|
67 /* The parent of a node in the DFS tree. */
|
|
|
68 TBB *dfs_parent;
|
|
|
69 /* For a node x key[x] is roughly the node nearest to the root from which
|
|
|
70 exists a way to x only over nodes behind x. Such a node is also called
|
|
|
71 semidominator. */
|
|
|
72 TBB *key;
|
|
|
73 /* The value in path_min[x] is the node y on the path from x to the root of
|
|
|
74 the tree x is in with the smallest key[y]. */
|
|
|
75 TBB *path_min;
|
|
|
76 /* bucket[x] points to the first node of the set of nodes having x as key. */
|
|
|
77 TBB *bucket;
|
|
|
78 /* And next_bucket[x] points to the next node. */
|
|
|
79 TBB *next_bucket;
|
|
|
80 /* After the algorithm is done, dom[x] contains the immediate dominator
|
|
|
81 of x. */
|
|
|
82 TBB *dom;
|
|
|
83
|
|
|
84 /* The following few fields implement the structures needed for disjoint
|
|
|
85 sets. */
|
|
|
86 /* set_chain[x] is the next node on the path from x to the representative
|
|
|
87 of the set containing x. If set_chain[x]==0 then x is a root. */
|
|
|
88 TBB *set_chain;
|
|
|
89 /* set_size[x] is the number of elements in the set named by x. */
|
|
|
90 unsigned int *set_size;
|
|
|
91 /* set_child[x] is used for balancing the tree representing a set. It can
|
|
|
92 be understood as the next sibling of x. */
|
|
|
93 TBB *set_child;
|
|
|
94
|
|
|
95 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
|
|
|
96 number of that node in DFS order counted from 1. This is an index
|
|
|
97 into most of the other arrays in this structure. */
|
|
|
98 TBB *dfs_order;
|
|
|
99 /* If x is the DFS-index of a node which corresponds with a basic block,
|
|
|
100 dfs_to_bb[x] is that basic block. Note, that in our structure there are
|
|
|
101 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
|
|
|
102 is true for every basic block bb, but not the opposite. */
|
|
|
103 basic_block *dfs_to_bb;
|
|
|
104
|
|
|
105 /* This is the next free DFS number when creating the DFS tree. */
|
|
|
106 unsigned int dfsnum;
|
|
|
107 /* The number of nodes in the DFS tree (==dfsnum-1). */
|
|
|
108 unsigned int nodes;
|
|
|
109
|
|
|
110 /* Blocks with bits set here have a fake edge to EXIT. These are used
|
|
|
111 to turn a DFS forest into a proper tree. */
|
|
|
112 bitmap fake_exit_edge;
|
|
|
113 };
|
|
|
114
|
|
|
115 static void init_dom_info (struct dom_info *, enum cdi_direction);
|
|
|
116 static void free_dom_info (struct dom_info *);
|
|
|
117 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
|
|
|
118 static void calc_dfs_tree (struct dom_info *, bool);
|
|
|
119 static void compress (struct dom_info *, TBB);
|
|
|
120 static TBB eval (struct dom_info *, TBB);
|
|
|
121 static void link_roots (struct dom_info *, TBB, TBB);
|
|
|
122 static void calc_idoms (struct dom_info *, bool);
|
|
|
123 void debug_dominance_info (enum cdi_direction);
|
|
|
124 void debug_dominance_tree (enum cdi_direction, basic_block);
|
|
|
125
|
|
|
126 /* Helper macro for allocating and initializing an array,
|
|
|
127 for aesthetic reasons. */
|
|
|
128 #define init_ar(var, type, num, content) \
|
|
|
129 do \
|
|
|
130 { \
|
|
|
131 unsigned int i = 1; /* Catch content == i. */ \
|
|
|
132 if (! (content)) \
|
|
|
133 (var) = XCNEWVEC (type, num); \
|
|
|
134 else \
|
|
|
135 { \
|
|
|
136 (var) = XNEWVEC (type, (num)); \
|
|
|
137 for (i = 0; i < num; i++) \
|
|
|
138 (var)[i] = (content); \
|
|
|
139 } \
|
|
|
140 } \
|
|
|
141 while (0)
|
|
|
142
|
|
|
143 /* Allocate all needed memory in a pessimistic fashion (so we round up).
|
|
|
144 This initializes the contents of DI, which already must be allocated. */
|
|
|
145
|
|
|
146 static void
|
|
|
147 init_dom_info (struct dom_info *di, enum cdi_direction dir)
|
|
|
148 {
|
|
|
149 /* We need memory for n_basic_blocks nodes. */
|
|
|
150 unsigned int num = n_basic_blocks;
|
|
|
151 init_ar (di->dfs_parent, TBB, num, 0);
|
|
|
152 init_ar (di->path_min, TBB, num, i);
|
|
|
153 init_ar (di->key, TBB, num, i);
|
|
|
154 init_ar (di->dom, TBB, num, 0);
|
|
|
155
|
|
|
156 init_ar (di->bucket, TBB, num, 0);
|
|
|
157 init_ar (di->next_bucket, TBB, num, 0);
|
|
|
158
|
|
|
159 init_ar (di->set_chain, TBB, num, 0);
|
|
|
160 init_ar (di->set_size, unsigned int, num, 1);
|
|
|
161 init_ar (di->set_child, TBB, num, 0);
|
|
|
162
|
|
|
163 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
|
|
|
164 init_ar (di->dfs_to_bb, basic_block, num, 0);
|
|
|
165
|
|
|
166 di->dfsnum = 1;
|
|
|
167 di->nodes = 0;
|
|
|
168
|
|
|
169 switch (dir)
|
|
|
170 {
|
|
|
171 case CDI_DOMINATORS:
|
|
|
172 di->fake_exit_edge = NULL;
|
|
|
173 break;
|
|
|
174 case CDI_POST_DOMINATORS:
|
|
|
175 di->fake_exit_edge = BITMAP_ALLOC (NULL);
|
|
|
176 break;
|
|
|
177 default:
|
|
|
178 gcc_unreachable ();
|
|
|
179 break;
|
|
|
180 }
|
|
|
181 }
|
|
|
182
|
|
|
183 #undef init_ar
|
|
|
184
|
|
|
185 /* Map dominance calculation type to array index used for various
|
|
|
186 dominance information arrays. This version is simple -- it will need
|
|
|
187 to be modified, obviously, if additional values are added to
|
|
|
188 cdi_direction. */
|
|
|
189
|
|
|
190 static unsigned int
|
|
|
191 dom_convert_dir_to_idx (enum cdi_direction dir)
|
|
|
192 {
|
|
|
193 gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
|
|
|
194 return dir - 1;
|
|
|
195 }
|
|
|
196
|
|
|
197 /* Free all allocated memory in DI, but not DI itself. */
|
|
|
198
|
|
|
199 static void
|
|
|
200 free_dom_info (struct dom_info *di)
|
|
|
201 {
|
|
|
202 free (di->dfs_parent);
|
|
|
203 free (di->path_min);
|
|
|
204 free (di->key);
|
|
|
205 free (di->dom);
|
|
|
206 free (di->bucket);
|
|
|
207 free (di->next_bucket);
|
|
|
208 free (di->set_chain);
|
|
|
209 free (di->set_size);
|
|
|
210 free (di->set_child);
|
|
|
211 free (di->dfs_order);
|
|
|
212 free (di->dfs_to_bb);
|
|
|
213 BITMAP_FREE (di->fake_exit_edge);
|
|
|
214 }
|
|
|
215
|
|
|
216 /* The nonrecursive variant of creating a DFS tree. DI is our working
|
|
|
217 structure, BB the starting basic block for this tree and REVERSE
|
|
|
218 is true, if predecessors should be visited instead of successors of a
|
|
|
219 node. After this is done all nodes reachable from BB were visited, have
|
|
|
220 assigned their dfs number and are linked together to form a tree. */
|
|
|
221
|
|
|
222 static void
|
|
|
223 calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
|
|
|
224 {
|
|
|
225 /* We call this _only_ if bb is not already visited. */
|
|
|
226 edge e;
|
|
|
227 TBB child_i, my_i = 0;
|
|
|
228 edge_iterator *stack;
|
|
|
229 edge_iterator ei, einext;
|
|
|
230 int sp;
|
|
|
231 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
|
|
|
232 problem). */
|
|
|
233 basic_block en_block;
|
|
|
234 /* Ending block. */
|
|
|
235 basic_block ex_block;
|
|
|
236
|
|
|
237 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
|
|
|
238 sp = 0;
|
|
|
239
|
|
|
240 /* Initialize our border blocks, and the first edge. */
|
|
|
241 if (reverse)
|
|
|
242 {
|
|
|
243 ei = ei_start (bb->preds);
|
|
|
244 en_block = EXIT_BLOCK_PTR;
|
|
|
245 ex_block = ENTRY_BLOCK_PTR;
|
|
|
246 }
|
|
|
247 else
|
|
|
248 {
|
|
|
249 ei = ei_start (bb->succs);
|
|
|
250 en_block = ENTRY_BLOCK_PTR;
|
|
|
251 ex_block = EXIT_BLOCK_PTR;
|
|
|
252 }
|
|
|
253
|
|
|
254 /* When the stack is empty we break out of this loop. */
|
|
|
255 while (1)
|
|
|
256 {
|
|
|
257 basic_block bn;
|
|
|
258
|
|
|
259 /* This loop traverses edges e in depth first manner, and fills the
|
|
|
260 stack. */
|
|
|
261 while (!ei_end_p (ei))
|
|
|
262 {
|
|
|
263 e = ei_edge (ei);
|
|
|
264
|
|
|
265 /* Deduce from E the current and the next block (BB and BN), and the
|
|
|
266 next edge. */
|
|
|
267 if (reverse)
|
|
|
268 {
|
|
|
269 bn = e->src;
|
|
|
270
|
|
|
271 /* If the next node BN is either already visited or a border
|
|
|
272 block the current edge is useless, and simply overwritten
|
|
|
273 with the next edge out of the current node. */
|
|
|
274 if (bn == ex_block || di->dfs_order[bn->index])
|
|
|
275 {
|
|
|
276 ei_next (&ei);
|
|
|
277 continue;
|
|
|
278 }
|
|
|
279 bb = e->dest;
|
|
|
280 einext = ei_start (bn->preds);
|
|
|
281 }
|
|
|
282 else
|
|
|
283 {
|
|
|
284 bn = e->dest;
|
|
|
285 if (bn == ex_block || di->dfs_order[bn->index])
|
|
|
286 {
|
|
|
287 ei_next (&ei);
|
|
|
288 continue;
|
|
|
289 }
|
|
|
290 bb = e->src;
|
|
|
291 einext = ei_start (bn->succs);
|
|
|
292 }
|
|
|
293
|
|
|
294 gcc_assert (bn != en_block);
|
|
|
295
|
|
|
296 /* Fill the DFS tree info calculatable _before_ recursing. */
|
|
|
297 if (bb != en_block)
|
|
|
298 my_i = di->dfs_order[bb->index];
|
|
|
299 else
|
|
|
300 my_i = di->dfs_order[last_basic_block];
|
|
|
301 child_i = di->dfs_order[bn->index] = di->dfsnum++;
|
|
|
302 di->dfs_to_bb[child_i] = bn;
|
|
|
303 di->dfs_parent[child_i] = my_i;
|
|
|
304
|
|
|
305 /* Save the current point in the CFG on the stack, and recurse. */
|
|
|
306 stack[sp++] = ei;
|
|
|
307 ei = einext;
|
|
|
308 }
|
|
|
309
|
|
|
310 if (!sp)
|
|
|
311 break;
|
|
|
312 ei = stack[--sp];
|
|
|
313
|
|
|
314 /* OK. The edge-list was exhausted, meaning normally we would
|
|
|
315 end the recursion. After returning from the recursive call,
|
|
|
316 there were (may be) other statements which were run after a
|
|
|
317 child node was completely considered by DFS. Here is the
|
|
|
318 point to do it in the non-recursive variant.
|
|
|
319 E.g. The block just completed is in e->dest for forward DFS,
|
|
|
320 the block not yet completed (the parent of the one above)
|
|
|
321 in e->src. This could be used e.g. for computing the number of
|
|
|
322 descendants or the tree depth. */
|
|
|
323 ei_next (&ei);
|
|
|
324 }
|
|
|
325 free (stack);
|
|
|
326 }
|
|
|
327
|
|
|
328 /* The main entry for calculating the DFS tree or forest. DI is our working
|
|
|
329 structure and REVERSE is true, if we are interested in the reverse flow
|
|
|
330 graph. In that case the result is not necessarily a tree but a forest,
|
|
|
331 because there may be nodes from which the EXIT_BLOCK is unreachable. */
|
|
|
332
|
|
|
333 static void
|
|
|
334 calc_dfs_tree (struct dom_info *di, bool reverse)
|
|
|
335 {
|
|
|
336 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
|
|
|
337 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
|
|
|
338 di->dfs_order[last_basic_block] = di->dfsnum;
|
|
|
339 di->dfs_to_bb[di->dfsnum] = begin;
|
|
|
340 di->dfsnum++;
|
|
|
341
|
|
|
342 calc_dfs_tree_nonrec (di, begin, reverse);
|
|
|
343
|
|
|
344 if (reverse)
|
|
|
345 {
|
|
|
346 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
|
|
|
347 They are reverse-unreachable. In the dom-case we disallow such
|
|
|
348 nodes, but in post-dom we have to deal with them.
|
|
|
349
|
|
|
350 There are two situations in which this occurs. First, noreturn
|
|
|
351 functions. Second, infinite loops. In the first case we need to
|
|
|
352 pretend that there is an edge to the exit block. In the second
|
|
|
353 case, we wind up with a forest. We need to process all noreturn
|
|
|
354 blocks before we know if we've got any infinite loops. */
|
|
|
355
|
|
|
356 basic_block b;
|
|
|
357 bool saw_unconnected = false;
|
|
|
358
|
|
|
359 FOR_EACH_BB_REVERSE (b)
|
|
|
360 {
|
|
|
361 if (EDGE_COUNT (b->succs) > 0)
|
|
|
362 {
|
|
|
363 if (di->dfs_order[b->index] == 0)
|
|
|
364 saw_unconnected = true;
|
|
|
365 continue;
|
|
|
366 }
|
|
|
367 bitmap_set_bit (di->fake_exit_edge, b->index);
|
|
|
368 di->dfs_order[b->index] = di->dfsnum;
|
|
|
369 di->dfs_to_bb[di->dfsnum] = b;
|
|
|
370 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
|
|
371 di->dfsnum++;
|
|
|
372 calc_dfs_tree_nonrec (di, b, reverse);
|
|
|
373 }
|
|
|
374
|
|
|
375 if (saw_unconnected)
|
|
|
376 {
|
|
|
377 FOR_EACH_BB_REVERSE (b)
|
|
|
378 {
|
|
|
379 if (di->dfs_order[b->index])
|
|
|
380 continue;
|
|
|
381 bitmap_set_bit (di->fake_exit_edge, b->index);
|
|
|
382 di->dfs_order[b->index] = di->dfsnum;
|
|
|
383 di->dfs_to_bb[di->dfsnum] = b;
|
|
|
384 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
|
|
385 di->dfsnum++;
|
|
|
386 calc_dfs_tree_nonrec (di, b, reverse);
|
|
|
387 }
|
|
|
388 }
|
|
|
389 }
|
|
|
390
|
|
|
391 di->nodes = di->dfsnum - 1;
|
|
|
392
|
|
|
393 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
|
|
|
394 gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
|
|
|
395 }
|
|
|
396
|
|
|
397 /* Compress the path from V to the root of its set and update path_min at the
|
|
|
398 same time. After compress(di, V) set_chain[V] is the root of the set V is
|
|
|
399 in and path_min[V] is the node with the smallest key[] value on the path
|
|
|
400 from V to that root. */
|
|
|
401
|
|
|
402 static void
|
|
|
403 compress (struct dom_info *di, TBB v)
|
|
|
404 {
|
|
|
405 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
|
|
|
406 greater than 5 even for huge graphs (I've not seen call depth > 4).
|
|
|
407 Also performance wise compress() ranges _far_ behind eval(). */
|
|
|
408 TBB parent = di->set_chain[v];
|
|
|
409 if (di->set_chain[parent])
|
|
|
410 {
|
|
|
411 compress (di, parent);
|
|
|
412 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
|
|
|
413 di->path_min[v] = di->path_min[parent];
|
|
|
414 di->set_chain[v] = di->set_chain[parent];
|
|
|
415 }
|
|
|
416 }
|
|
|
417
|
|
|
418 /* Compress the path from V to the set root of V if needed (when the root has
|
|
|
419 changed since the last call). Returns the node with the smallest key[]
|
|
|
420 value on the path from V to the root. */
|
|
|
421
|
|
|
422 static inline TBB
|
|
|
423 eval (struct dom_info *di, TBB v)
|
|
|
424 {
|
|
|
425 /* The representative of the set V is in, also called root (as the set
|
|
|
426 representation is a tree). */
|
|
|
427 TBB rep = di->set_chain[v];
|
|
|
428
|
|
|
429 /* V itself is the root. */
|
|
|
430 if (!rep)
|
|
|
431 return di->path_min[v];
|
|
|
432
|
|
|
433 /* Compress only if necessary. */
|
|
|
434 if (di->set_chain[rep])
|
|
|
435 {
|
|
|
436 compress (di, v);
|
|
|
437 rep = di->set_chain[v];
|
|
|
438 }
|
|
|
439
|
|
|
440 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
|
|
|
441 return di->path_min[v];
|
|
|
442 else
|
|
|
443 return di->path_min[rep];
|
|
|
444 }
|
|
|
445
|
|
|
446 /* This essentially merges the two sets of V and W, giving a single set with
|
|
|
447 the new root V. The internal representation of these disjoint sets is a
|
|
|
448 balanced tree. Currently link(V,W) is only used with V being the parent
|
|
|
449 of W. */
|
|
|
450
|
|
|
451 static void
|
|
|
452 link_roots (struct dom_info *di, TBB v, TBB w)
|
|
|
453 {
|
|
|
454 TBB s = w;
|
|
|
455
|
|
|
456 /* Rebalance the tree. */
|
|
|
457 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
|
|
|
458 {
|
|
|
459 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
|
|
|
460 >= 2 * di->set_size[di->set_child[s]])
|
|
|
461 {
|
|
|
462 di->set_chain[di->set_child[s]] = s;
|
|
|
463 di->set_child[s] = di->set_child[di->set_child[s]];
|
|
|
464 }
|
|
|
465 else
|
|
|
466 {
|
|
|
467 di->set_size[di->set_child[s]] = di->set_size[s];
|
|
|
468 s = di->set_chain[s] = di->set_child[s];
|
|
|
469 }
|
|
|
470 }
|
|
|
471
|
|
|
472 di->path_min[s] = di->path_min[w];
|
|
|
473 di->set_size[v] += di->set_size[w];
|
|
|
474 if (di->set_size[v] < 2 * di->set_size[w])
|
|
|
475 {
|
|
|
476 TBB tmp = s;
|
|
|
477 s = di->set_child[v];
|
|
|
478 di->set_child[v] = tmp;
|
|
|
479 }
|
|
|
480
|
|
|
481 /* Merge all subtrees. */
|
|
|
482 while (s)
|
|
|
483 {
|
|
|
484 di->set_chain[s] = v;
|
|
|
485 s = di->set_child[s];
|
|
|
486 }
|
|
|
487 }
|
|
|
488
|
|
|
489 /* This calculates the immediate dominators (or post-dominators if REVERSE is
|
|
|
490 true). DI is our working structure and should hold the DFS forest.
|
|
|
491 On return the immediate dominator to node V is in di->dom[V]. */
|
|
|
492
|
|
|
493 static void
|
|
|
494 calc_idoms (struct dom_info *di, bool reverse)
|
|
|
495 {
|
|
|
496 TBB v, w, k, par;
|
|
|
497 basic_block en_block;
|
|
|
498 edge_iterator ei, einext;
|
|
|
499
|
|
|
500 if (reverse)
|
|
|
501 en_block = EXIT_BLOCK_PTR;
|
|
|
502 else
|
|
|
503 en_block = ENTRY_BLOCK_PTR;
|
|
|
504
|
|
|
505 /* Go backwards in DFS order, to first look at the leafs. */
|
|
|
506 v = di->nodes;
|
|
|
507 while (v > 1)
|
|
|
508 {
|
|
|
509 basic_block bb = di->dfs_to_bb[v];
|
|
|
510 edge e;
|
|
|
511
|
|
|
512 par = di->dfs_parent[v];
|
|
|
513 k = v;
|
|
|
514
|
|
|
515 ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
|
|
|
516
|
|
|
517 if (reverse)
|
|
|
518 {
|
|
|
519 /* If this block has a fake edge to exit, process that first. */
|
|
|
520 if (bitmap_bit_p (di->fake_exit_edge, bb->index))
|
|
|
521 {
|
|
|
522 einext = ei;
|
|
|
523 einext.index = 0;
|
|
|
524 goto do_fake_exit_edge;
|
|
|
525 }
|
|
|
526 }
|
|
|
527
|
|
|
528 /* Search all direct predecessors for the smallest node with a path
|
|
|
529 to them. That way we have the smallest node with also a path to
|
|
|
530 us only over nodes behind us. In effect we search for our
|
|
|
531 semidominator. */
|
|
|
532 while (!ei_end_p (ei))
|
|
|
533 {
|
|
|
534 TBB k1;
|
|
|
535 basic_block b;
|
|
|
536
|
|
|
537 e = ei_edge (ei);
|
|
|
538 b = (reverse) ? e->dest : e->src;
|
|
|
539 einext = ei;
|
|
|
540 ei_next (&einext);
|
|
|
541
|
|
|
542 if (b == en_block)
|
|
|
543 {
|
|
|
544 do_fake_exit_edge:
|
|
|
545 k1 = di->dfs_order[last_basic_block];
|
|
|
546 }
|
|
|
547 else
|
|
|
548 k1 = di->dfs_order[b->index];
|
|
|
549
|
|
|
550 /* Call eval() only if really needed. If k1 is above V in DFS tree,
|
|
|
551 then we know, that eval(k1) == k1 and key[k1] == k1. */
|
|
|
552 if (k1 > v)
|
|
|
553 k1 = di->key[eval (di, k1)];
|
|
|
554 if (k1 < k)
|
|
|
555 k = k1;
|
|
|
556
|
|
|
557 ei = einext;
|
|
|
558 }
|
|
|
559
|
|
|
560 di->key[v] = k;
|
|
|
561 link_roots (di, par, v);
|
|
|
562 di->next_bucket[v] = di->bucket[k];
|
|
|
563 di->bucket[k] = v;
|
|
|
564
|
|
|
565 /* Transform semidominators into dominators. */
|
|
|
566 for (w = di->bucket[par]; w; w = di->next_bucket[w])
|
|
|
567 {
|
|
|
568 k = eval (di, w);
|
|
|
569 if (di->key[k] < di->key[w])
|
|
|
570 di->dom[w] = k;
|
|
|
571 else
|
|
|
572 di->dom[w] = par;
|
|
|
573 }
|
|
|
574 /* We don't need to cleanup next_bucket[]. */
|
|
|
575 di->bucket[par] = 0;
|
|
|
576 v--;
|
|
|
577 }
|
|
|
578
|
|
|
579 /* Explicitly define the dominators. */
|
|
|
580 di->dom[1] = 0;
|
|
|
581 for (v = 2; v <= di->nodes; v++)
|
|
|
582 if (di->dom[v] != di->key[v])
|
|
|
583 di->dom[v] = di->dom[di->dom[v]];
|
|
|
584 }
|
|
|
585
|
|
|
586 /* Assign dfs numbers starting from NUM to NODE and its sons. */
|
|
|
587
|
|
|
588 static void
|
|
|
589 assign_dfs_numbers (struct et_node *node, int *num)
|
|
|
590 {
|
|
|
591 struct et_node *son;
|
|
|
592
|
|
|
593 node->dfs_num_in = (*num)++;
|
|
|
594
|
|
|
595 if (node->son)
|
|
|
596 {
|
|
|
597 assign_dfs_numbers (node->son, num);
|
|
|
598 for (son = node->son->right; son != node->son; son = son->right)
|
|
|
599 assign_dfs_numbers (son, num);
|
|
|
600 }
|
|
|
601
|
|
|
602 node->dfs_num_out = (*num)++;
|
|
|
603 }
|
|
|
604
|
|
|
605 /* Compute the data necessary for fast resolving of dominator queries in a
|
|
|
606 static dominator tree. */
|
|
|
607
|
|
|
608 static void
|
|
|
609 compute_dom_fast_query (enum cdi_direction dir)
|
|
|
610 {
|
|
|
611 int num = 0;
|
|
|
612 basic_block bb;
|
|
|
613 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
614
|
|
|
615 gcc_assert (dom_info_available_p (dir));
|
|
|
616
|
|
|
617 if (dom_computed[dir_index] == DOM_OK)
|
|
|
618 return;
|
|
|
619
|
|
|
620 FOR_ALL_BB (bb)
|
|
|
621 {
|
|
|
622 if (!bb->dom[dir_index]->father)
|
|
|
623 assign_dfs_numbers (bb->dom[dir_index], &num);
|
|
|
624 }
|
|
|
625
|
|
|
626 dom_computed[dir_index] = DOM_OK;
|
|
|
627 }
|
|
|
628
|
|
|
629 /* The main entry point into this module. DIR is set depending on whether
|
|
|
630 we want to compute dominators or postdominators. */
|
|
|
631
|
|
|
632 void
|
|
|
633 calculate_dominance_info (enum cdi_direction dir)
|
|
|
634 {
|
|
|
635 struct dom_info di;
|
|
|
636 basic_block b;
|
|
|
637 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
638 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
|
|
639
|
|
|
640 if (dom_computed[dir_index] == DOM_OK)
|
|
|
641 return;
|
|
|
642
|
|
|
643 timevar_push (TV_DOMINANCE);
|
|
|
644 if (!dom_info_available_p (dir))
|
|
|
645 {
|
|
|
646 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
|
|
|
647
|
|
|
648 FOR_ALL_BB (b)
|
|
|
649 {
|
|
|
650 b->dom[dir_index] = et_new_tree (b);
|
|
|
651 }
|
|
|
652 n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
|
|
|
653
|
|
|
654 init_dom_info (&di, dir);
|
|
|
655 calc_dfs_tree (&di, reverse);
|
|
|
656 calc_idoms (&di, reverse);
|
|
|
657
|
|
|
658 FOR_EACH_BB (b)
|
|
|
659 {
|
|
|
660 TBB d = di.dom[di.dfs_order[b->index]];
|
|
|
661
|
|
|
662 if (di.dfs_to_bb[d])
|
|
|
663 et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
|
|
|
664 }
|
|
|
665
|
|
|
666 free_dom_info (&di);
|
|
|
667 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
|
|
668 }
|
|
|
669
|
|
|
670 compute_dom_fast_query (dir);
|
|
|
671
|
|
|
672 timevar_pop (TV_DOMINANCE);
|
|
|
673 }
|
|
|
674
|
|
|
675 /* Free dominance information for direction DIR. */
|
|
|
676 void
|
|
|
677 free_dominance_info (enum cdi_direction dir)
|
|
|
678 {
|
|
|
679 basic_block bb;
|
|
|
680 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
681
|
|
|
682 if (!dom_info_available_p (dir))
|
|
|
683 return;
|
|
|
684
|
|
|
685 FOR_ALL_BB (bb)
|
|
|
686 {
|
|
|
687 et_free_tree_force (bb->dom[dir_index]);
|
|
|
688 bb->dom[dir_index] = NULL;
|
|
|
689 }
|
|
|
690 et_free_pools ();
|
|
|
691
|
|
|
692 n_bbs_in_dom_tree[dir_index] = 0;
|
|
|
693
|
|
|
694 dom_computed[dir_index] = DOM_NONE;
|
|
|
695 }
|
|
|
696
|
|
|
697 /* Return the immediate dominator of basic block BB. */
|
|
|
698 basic_block
|
|
|
699 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
|
|
|
700 {
|
|
|
701 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
702 struct et_node *node = bb->dom[dir_index];
|
|
|
703
|
|
|
704 gcc_assert (dom_computed[dir_index]);
|
|
|
705
|
|
|
706 if (!node->father)
|
|
|
707 return NULL;
|
|
|
708
|
|
|
709 return (basic_block) node->father->data;
|
|
|
710 }
|
|
|
711
|
|
|
712 /* Set the immediate dominator of the block possibly removing
|
|
|
713 existing edge. NULL can be used to remove any edge. */
|
|
|
714 inline void
|
|
|
715 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
|
|
|
716 basic_block dominated_by)
|
|
|
717 {
|
|
|
718 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
719 struct et_node *node = bb->dom[dir_index];
|
|
|
720
|
|
|
721 gcc_assert (dom_computed[dir_index]);
|
|
|
722
|
|
|
723 if (node->father)
|
|
|
724 {
|
|
|
725 if (node->father->data == dominated_by)
|
|
|
726 return;
|
|
|
727 et_split (node);
|
|
|
728 }
|
|
|
729
|
|
|
730 if (dominated_by)
|
|
|
731 et_set_father (node, dominated_by->dom[dir_index]);
|
|
|
732
|
|
|
733 if (dom_computed[dir_index] == DOM_OK)
|
|
|
734 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
|
|
735 }
|
|
|
736
|
|
|
737 /* Returns the list of basic blocks immediately dominated by BB, in the
|
|
|
738 direction DIR. */
|
|
|
739 VEC (basic_block, heap) *
|
|
|
740 get_dominated_by (enum cdi_direction dir, basic_block bb)
|
|
|
741 {
|
|
|
742 int n;
|
|
|
743 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
744 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
|
|
|
745 VEC (basic_block, heap) *bbs = NULL;
|
|
|
746
|
|
|
747 gcc_assert (dom_computed[dir_index]);
|
|
|
748
|
|
|
749 if (!son)
|
|
|
750 return NULL;
|
|
|
751
|
|
|
752 VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
|
|
|
753 for (ason = son->right, n = 1; ason != son; ason = ason->right)
|
|
|
754 VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
|
|
|
755
|
|
|
756 return bbs;
|
|
|
757 }
|
|
|
758
|
|
|
759 /* Returns the list of basic blocks that are immediately dominated (in
|
|
|
760 direction DIR) by some block between N_REGION ones stored in REGION,
|
|
|
761 except for blocks in the REGION itself. */
|
|
|
762
|
|
|
763 VEC (basic_block, heap) *
|
|
|
764 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
|
|
|
765 unsigned n_region)
|
|
|
766 {
|
|
|
767 unsigned i;
|
|
|
768 basic_block dom;
|
|
|
769 VEC (basic_block, heap) *doms = NULL;
|
|
|
770
|
|
|
771 for (i = 0; i < n_region; i++)
|
|
|
772 region[i]->flags |= BB_DUPLICATED;
|
|
|
773 for (i = 0; i < n_region; i++)
|
|
|
774 for (dom = first_dom_son (dir, region[i]);
|
|
|
775 dom;
|
|
|
776 dom = next_dom_son (dir, dom))
|
|
|
777 if (!(dom->flags & BB_DUPLICATED))
|
|
|
778 VEC_safe_push (basic_block, heap, doms, dom);
|
|
|
779 for (i = 0; i < n_region; i++)
|
|
|
780 region[i]->flags &= ~BB_DUPLICATED;
|
|
|
781
|
|
|
782 return doms;
|
|
|
783 }
|
|
|
784
|
|
|
785 /* Redirect all edges pointing to BB to TO. */
|
|
|
786 void
|
|
|
787 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
|
|
|
788 basic_block to)
|
|
|
789 {
|
|
|
790 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
791 struct et_node *bb_node, *to_node, *son;
|
|
|
792
|
|
|
793 bb_node = bb->dom[dir_index];
|
|
|
794 to_node = to->dom[dir_index];
|
|
|
795
|
|
|
796 gcc_assert (dom_computed[dir_index]);
|
|
|
797
|
|
|
798 if (!bb_node->son)
|
|
|
799 return;
|
|
|
800
|
|
|
801 while (bb_node->son)
|
|
|
802 {
|
|
|
803 son = bb_node->son;
|
|
|
804
|
|
|
805 et_split (son);
|
|
|
806 et_set_father (son, to_node);
|
|
|
807 }
|
|
|
808
|
|
|
809 if (dom_computed[dir_index] == DOM_OK)
|
|
|
810 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
|
|
811 }
|
|
|
812
|
|
|
813 /* Find first basic block in the tree dominating both BB1 and BB2. */
|
|
|
814 basic_block
|
|
|
815 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
|
|
|
816 {
|
|
|
817 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
818
|
|
|
819 gcc_assert (dom_computed[dir_index]);
|
|
|
820
|
|
|
821 if (!bb1)
|
|
|
822 return bb2;
|
|
|
823 if (!bb2)
|
|
|
824 return bb1;
|
|
|
825
|
|
|
826 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
|
|
|
827 }
|
|
|
828
|
|
|
829
|
|
|
830 /* Find the nearest common dominator for the basic blocks in BLOCKS,
|
|
|
831 using dominance direction DIR. */
|
|
|
832
|
|
|
833 basic_block
|
|
|
834 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
|
|
|
835 {
|
|
|
836 unsigned i, first;
|
|
|
837 bitmap_iterator bi;
|
|
|
838 basic_block dom;
|
|
|
839
|
|
|
840 first = bitmap_first_set_bit (blocks);
|
|
|
841 dom = BASIC_BLOCK (first);
|
|
|
842 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
|
|
|
843 if (dom != BASIC_BLOCK (i))
|
|
|
844 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
|
|
|
845
|
|
|
846 return dom;
|
|
|
847 }
|
|
|
848
|
|
|
849 /* Given a dominator tree, we can determine whether one thing
|
|
|
850 dominates another in constant time by using two DFS numbers:
|
|
|
851
|
|
|
852 1. The number for when we visit a node on the way down the tree
|
|
|
853 2. The number for when we visit a node on the way back up the tree
|
|
|
854
|
|
|
855 You can view these as bounds for the range of dfs numbers the
|
|
|
856 nodes in the subtree of the dominator tree rooted at that node
|
|
|
857 will contain.
|
|
|
858
|
|
|
859 The dominator tree is always a simple acyclic tree, so there are
|
|
|
860 only three possible relations two nodes in the dominator tree have
|
|
|
861 to each other:
|
|
|
862
|
|
|
863 1. Node A is above Node B (and thus, Node A dominates node B)
|
|
|
864
|
|
|
865 A
|
|
|
866 |
|
|
|
867 C
|
|
|
868 / \
|
|
|
869 B D
|
|
|
870
|
|
|
871
|
|
|
872 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
|
|
|
873 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
|
|
|
874 because we must hit A in the dominator tree *before* B on the walk
|
|
|
875 down, and we will hit A *after* B on the walk back up
|
|
|
876
|
|
|
877 2. Node A is below node B (and thus, node B dominates node A)
|
|
|
878
|
|
|
879
|
|
|
880 B
|
|
|
881 |
|
|
|
882 A
|
|
|
883 / \
|
|
|
884 C D
|
|
|
885
|
|
|
886 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
|
|
|
887 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
|
|
|
888
|
|
|
889 This is because we must hit A in the dominator tree *after* B on
|
|
|
890 the walk down, and we will hit A *before* B on the walk back up
|
|
|
891
|
|
|
892 3. Node A and B are siblings (and thus, neither dominates the other)
|
|
|
893
|
|
|
894 C
|
|
|
895 |
|
|
|
896 D
|
|
|
897 / \
|
|
|
898 A B
|
|
|
899
|
|
|
900 In the above case, DFS_Number_In of A will *always* be <=
|
|
|
901 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
|
|
|
902 DFS_Number_Out of B. This is because we will always finish the dfs
|
|
|
903 walk of one of the subtrees before the other, and thus, the dfs
|
|
|
904 numbers for one subtree can't intersect with the range of dfs
|
|
|
905 numbers for the other subtree. If you swap A and B's position in
|
|
|
906 the dominator tree, the comparison changes direction, but the point
|
|
|
907 is that both comparisons will always go the same way if there is no
|
|
|
908 dominance relationship.
|
|
|
909
|
|
|
910 Thus, it is sufficient to write
|
|
|
911
|
|
|
912 A_Dominates_B (node A, node B)
|
|
|
913 {
|
|
|
914 return DFS_Number_In(A) <= DFS_Number_In(B)
|
|
|
915 && DFS_Number_Out (A) >= DFS_Number_Out(B);
|
|
|
916 }
|
|
|
917
|
|
|
918 A_Dominated_by_B (node A, node B)
|
|
|
919 {
|
|
|
920 return DFS_Number_In(A) >= DFS_Number_In(A)
|
|
|
921 && DFS_Number_Out (A) <= DFS_Number_Out(B);
|
|
|
922 } */
|
|
|
923
|
|
|
924 /* Return TRUE in case BB1 is dominated by BB2. */
|
|
|
925 bool
|
|
|
926 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
|
|
|
927 {
|
|
|
928 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
929 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
|
|
|
930
|
|
|
931 gcc_assert (dom_computed[dir_index]);
|
|
|
932
|
|
|
933 if (dom_computed[dir_index] == DOM_OK)
|
|
|
934 return (n1->dfs_num_in >= n2->dfs_num_in
|
|
|
935 && n1->dfs_num_out <= n2->dfs_num_out);
|
|
|
936
|
|
|
937 return et_below (n1, n2);
|
|
|
938 }
|
|
|
939
|
|
|
940 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
|
|
|
941
|
|
|
942 unsigned
|
|
|
943 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
|
|
|
944 {
|
|
|
945 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
946 struct et_node *n = bb->dom[dir_index];
|
|
|
947
|
|
|
948 gcc_assert (dom_computed[dir_index] == DOM_OK);
|
|
|
949 return n->dfs_num_in;
|
|
|
950 }
|
|
|
951
|
|
|
952 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
|
|
|
953
|
|
|
954 unsigned
|
|
|
955 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
|
|
|
956 {
|
|
|
957 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
958 struct et_node *n = bb->dom[dir_index];
|
|
|
959
|
|
|
960 gcc_assert (dom_computed[dir_index] == DOM_OK);
|
|
|
961 return n->dfs_num_out;
|
|
|
962 }
|
|
|
963
|
|
|
964 /* Verify invariants of dominator structure. */
|
|
|
965 void
|
|
|
966 verify_dominators (enum cdi_direction dir)
|
|
|
967 {
|
|
|
968 int err = 0;
|
|
|
969 basic_block bb, imm_bb, imm_bb_correct;
|
|
|
970 struct dom_info di;
|
|
|
971 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
|
|
972
|
|
|
973 gcc_assert (dom_info_available_p (dir));
|
|
|
974
|
|
|
975 init_dom_info (&di, dir);
|
|
|
976 calc_dfs_tree (&di, reverse);
|
|
|
977 calc_idoms (&di, reverse);
|
|
|
978
|
|
|
979 FOR_EACH_BB (bb)
|
|
|
980 {
|
|
|
981 imm_bb = get_immediate_dominator (dir, bb);
|
|
|
982 if (!imm_bb)
|
|
|
983 {
|
|
|
984 error ("dominator of %d status unknown", bb->index);
|
|
|
985 err = 1;
|
|
|
986 }
|
|
|
987
|
|
|
988 imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
|
|
|
989 if (imm_bb != imm_bb_correct)
|
|
|
990 {
|
|
|
991 error ("dominator of %d should be %d, not %d",
|
|
|
992 bb->index, imm_bb_correct->index, imm_bb->index);
|
|
|
993 err = 1;
|
|
|
994 }
|
|
|
995 }
|
|
|
996
|
|
|
997 free_dom_info (&di);
|
|
|
998 gcc_assert (!err);
|
|
|
999 }
|
|
|
1000
|
|
|
1001 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
|
|
|
1002 assuming that dominators of other blocks are correct. We also use it to
|
|
|
1003 recompute the dominators in a restricted area, by iterating it until it
|
|
|
1004 reaches a fixed point. */
|
|
|
1005
|
|
|
1006 basic_block
|
|
|
1007 recompute_dominator (enum cdi_direction dir, basic_block bb)
|
|
|
1008 {
|
|
|
1009 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1010 basic_block dom_bb = NULL;
|
|
|
1011 edge e;
|
|
|
1012 edge_iterator ei;
|
|
|
1013
|
|
|
1014 gcc_assert (dom_computed[dir_index]);
|
|
|
1015
|
|
|
1016 if (dir == CDI_DOMINATORS)
|
|
|
1017 {
|
|
|
1018 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1019 {
|
|
|
1020 if (!dominated_by_p (dir, e->src, bb))
|
|
|
1021 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
|
|
|
1022 }
|
|
|
1023 }
|
|
|
1024 else
|
|
|
1025 {
|
|
|
1026 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1027 {
|
|
|
1028 if (!dominated_by_p (dir, e->dest, bb))
|
|
|
1029 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
|
|
|
1030 }
|
|
|
1031 }
|
|
|
1032
|
|
|
1033 return dom_bb;
|
|
|
1034 }
|
|
|
1035
|
|
|
1036 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
|
|
|
1037 of BBS. We assume that all the immediate dominators except for those of the
|
|
|
1038 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
|
|
|
1039 currently recorded immediate dominators of blocks in BBS really dominate the
|
|
|
1040 blocks. The basic blocks for that we determine the dominator are removed
|
|
|
1041 from BBS. */
|
|
|
1042
|
|
|
1043 static void
|
|
|
1044 prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
|
|
|
1045 bool conservative)
|
|
|
1046 {
|
|
|
1047 unsigned i;
|
|
|
1048 bool single;
|
|
|
1049 basic_block bb, dom = NULL;
|
|
|
1050 edge_iterator ei;
|
|
|
1051 edge e;
|
|
|
1052
|
|
|
1053 for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
|
|
|
1054 {
|
|
|
1055 if (bb == ENTRY_BLOCK_PTR)
|
|
|
1056 goto succeed;
|
|
|
1057
|
|
|
1058 if (single_pred_p (bb))
|
|
|
1059 {
|
|
|
1060 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
|
|
|
1061 goto succeed;
|
|
|
1062 }
|
|
|
1063
|
|
|
1064 if (!conservative)
|
|
|
1065 goto fail;
|
|
|
1066
|
|
|
1067 single = true;
|
|
|
1068 dom = NULL;
|
|
|
1069 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1070 {
|
|
|
1071 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
|
|
|
1072 continue;
|
|
|
1073
|
|
|
1074 if (!dom)
|
|
|
1075 dom = e->src;
|
|
|
1076 else
|
|
|
1077 {
|
|
|
1078 single = false;
|
|
|
1079 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
|
|
1080 }
|
|
|
1081 }
|
|
|
1082
|
|
|
1083 gcc_assert (dom != NULL);
|
|
|
1084 if (single
|
|
|
1085 || find_edge (dom, bb))
|
|
|
1086 {
|
|
|
1087 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
|
|
1088 goto succeed;
|
|
|
1089 }
|
|
|
1090
|
|
|
1091 fail:
|
|
|
1092 i++;
|
|
|
1093 continue;
|
|
|
1094
|
|
|
1095 succeed:
|
|
|
1096 VEC_unordered_remove (basic_block, bbs, i);
|
|
|
1097 }
|
|
|
1098 }
|
|
|
1099
|
|
|
1100 /* Returns root of the dominance tree in the direction DIR that contains
|
|
|
1101 BB. */
|
|
|
1102
|
|
|
1103 static basic_block
|
|
|
1104 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
|
|
|
1105 {
|
|
|
1106 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
|
|
|
1107 }
|
|
|
1108
|
|
|
1109 /* See the comment in iterate_fix_dominators. Finds the immediate dominators
|
|
|
1110 for the sons of Y, found using the SON and BROTHER arrays representing
|
|
|
1111 the dominance tree of graph G. BBS maps the vertices of G to the basic
|
|
|
1112 blocks. */
|
|
|
1113
|
|
|
1114 static void
|
|
|
1115 determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
|
|
|
1116 int y, int *son, int *brother)
|
|
|
1117 {
|
|
|
1118 bitmap gprime;
|
|
|
1119 int i, a, nc;
|
|
|
1120 VEC (int, heap) **sccs;
|
|
|
1121 basic_block bb, dom, ybb;
|
|
|
1122 unsigned si;
|
|
|
1123 edge e;
|
|
|
1124 edge_iterator ei;
|
|
|
1125
|
|
|
1126 if (son[y] == -1)
|
|
|
1127 return;
|
|
|
1128 if (y == (int) VEC_length (basic_block, bbs))
|
|
|
1129 ybb = ENTRY_BLOCK_PTR;
|
|
|
1130 else
|
|
|
1131 ybb = VEC_index (basic_block, bbs, y);
|
|
|
1132
|
|
|
1133 if (brother[son[y]] == -1)
|
|
|
1134 {
|
|
|
1135 /* Handle the common case Y has just one son specially. */
|
|
|
1136 bb = VEC_index (basic_block, bbs, son[y]);
|
|
|
1137 set_immediate_dominator (CDI_DOMINATORS, bb,
|
|
|
1138 recompute_dominator (CDI_DOMINATORS, bb));
|
|
|
1139 identify_vertices (g, y, son[y]);
|
|
|
1140 return;
|
|
|
1141 }
|
|
|
1142
|
|
|
1143 gprime = BITMAP_ALLOC (NULL);
|
|
|
1144 for (a = son[y]; a != -1; a = brother[a])
|
|
|
1145 bitmap_set_bit (gprime, a);
|
|
|
1146
|
|
|
1147 nc = graphds_scc (g, gprime);
|
|
|
1148 BITMAP_FREE (gprime);
|
|
|
1149
|
|
|
1150 sccs = XCNEWVEC (VEC (int, heap) *, nc);
|
|
|
1151 for (a = son[y]; a != -1; a = brother[a])
|
|
|
1152 VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
|
|
|
1153
|
|
|
1154 for (i = nc - 1; i >= 0; i--)
|
|
|
1155 {
|
|
|
1156 dom = NULL;
|
|
|
1157 for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
|
|
1158 {
|
|
|
1159 bb = VEC_index (basic_block, bbs, a);
|
|
|
1160 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1161 {
|
|
|
1162 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
|
|
|
1163 continue;
|
|
|
1164
|
|
|
1165 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
|
|
1166 }
|
|
|
1167 }
|
|
|
1168
|
|
|
1169 gcc_assert (dom != NULL);
|
|
|
1170 for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
|
|
1171 {
|
|
|
1172 bb = VEC_index (basic_block, bbs, a);
|
|
|
1173 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
|
|
1174 }
|
|
|
1175 }
|
|
|
1176
|
|
|
1177 for (i = 0; i < nc; i++)
|
|
|
1178 VEC_free (int, heap, sccs[i]);
|
|
|
1179 free (sccs);
|
|
|
1180
|
|
|
1181 for (a = son[y]; a != -1; a = brother[a])
|
|
|
1182 identify_vertices (g, y, a);
|
|
|
1183 }
|
|
|
1184
|
|
|
1185 /* Recompute dominance information for basic blocks in the set BBS. The
|
|
|
1186 function assumes that the immediate dominators of all the other blocks
|
|
|
1187 in CFG are correct, and that there are no unreachable blocks.
|
|
|
1188
|
|
|
1189 If CONSERVATIVE is true, we additionally assume that all the ancestors of
|
|
|
1190 a block of BBS in the current dominance tree dominate it. */
|
|
|
1191
|
|
|
1192 void
|
|
|
1193 iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
|
|
|
1194 bool conservative)
|
|
|
1195 {
|
|
|
1196 unsigned i;
|
|
|
1197 basic_block bb, dom;
|
|
|
1198 struct graph *g;
|
|
|
1199 int n, y;
|
|
|
1200 size_t dom_i;
|
|
|
1201 edge e;
|
|
|
1202 edge_iterator ei;
|
|
|
1203 struct pointer_map_t *map;
|
|
|
1204 int *parent, *son, *brother;
|
|
|
1205 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1206
|
|
|
1207 /* We only support updating dominators. There are some problems with
|
|
|
1208 updating postdominators (need to add fake edges from infinite loops
|
|
|
1209 and noreturn functions), and since we do not currently use
|
|
|
1210 iterate_fix_dominators for postdominators, any attempt to handle these
|
|
|
1211 problems would be unused, untested, and almost surely buggy. We keep
|
|
|
1212 the DIR argument for consistency with the rest of the dominator analysis
|
|
|
1213 interface. */
|
|
|
1214 gcc_assert (dir == CDI_DOMINATORS);
|
|
|
1215 gcc_assert (dom_computed[dir_index]);
|
|
|
1216
|
|
|
1217 /* The algorithm we use takes inspiration from the following papers, although
|
|
|
1218 the details are quite different from any of them:
|
|
|
1219
|
|
|
1220 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
|
|
|
1221 Dominator Tree of a Reducible Flowgraph
|
|
|
1222 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
|
|
|
1223 dominator trees
|
|
|
1224 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
|
|
1225 Algorithm
|
|
|
1226
|
|
|
1227 First, we use the following heuristics to decrease the size of the BBS
|
|
|
1228 set:
|
|
|
1229 a) if BB has a single predecessor, then its immediate dominator is this
|
|
|
1230 predecessor
|
|
|
1231 additionally, if CONSERVATIVE is true:
|
|
|
1232 b) if all the predecessors of BB except for one (X) are dominated by BB,
|
|
|
1233 then X is the immediate dominator of BB
|
|
|
1234 c) if the nearest common ancestor of the predecessors of BB is X and
|
|
|
1235 X -> BB is an edge in CFG, then X is the immediate dominator of BB
|
|
|
1236
|
|
|
1237 Then, we need to establish the dominance relation among the basic blocks
|
|
|
1238 in BBS. We split the dominance tree by removing the immediate dominator
|
|
|
1239 edges from BBS, creating a forest F. We form a graph G whose vertices
|
|
|
1240 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
|
|
|
1241 X' -> Y in CFG such that X' belongs to the tree of the dominance forest
|
|
|
1242 whose root is X. We then determine dominance tree of G. Note that
|
|
|
1243 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
|
|
|
1244 In this step, we can use arbitrary algorithm to determine dominators.
|
|
|
1245 We decided to prefer the algorithm [3] to the algorithm of
|
|
|
1246 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
|
|
|
1247 10 during gcc bootstrap), and [3] should perform better in this case.
|
|
|
1248
|
|
|
1249 Finally, we need to determine the immediate dominators for the basic
|
|
|
1250 blocks of BBS. If the immediate dominator of X in G is Y, then
|
|
|
1251 the immediate dominator of X in CFG belongs to the tree of F rooted in
|
|
|
1252 Y. We process the dominator tree T of G recursively, starting from leaves.
|
|
|
1253 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
|
|
|
1254 subtrees of the dominance tree of CFG rooted in X_i are already correct.
|
|
|
1255 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
|
|
|
1256 the following observations:
|
|
|
1257 (i) the immediate dominator of all blocks in a strongly connected
|
|
|
1258 component of G' is the same
|
|
|
1259 (ii) if X has no predecessors in G', then the immediate dominator of X
|
|
|
1260 is the nearest common ancestor of the predecessors of X in the
|
|
|
1261 subtree of F rooted in Y
|
|
|
1262 Therefore, it suffices to find the topological ordering of G', and
|
|
|
1263 process the nodes X_i in this order using the rules (i) and (ii).
|
|
|
1264 Then, we contract all the nodes X_i with Y in G, so that the further
|
|
|
1265 steps work correctly. */
|
|
|
1266
|
|
|
1267 if (!conservative)
|
|
|
1268 {
|
|
|
1269 /* Split the tree now. If the idoms of blocks in BBS are not
|
|
|
1270 conservatively correct, setting the dominators using the
|
|
|
1271 heuristics in prune_bbs_to_update_dominators could
|
|
|
1272 create cycles in the dominance "tree", and cause ICE. */
|
|
|
1273 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
|
|
1274 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
|
|
1275 }
|
|
|
1276
|
|
|
1277 prune_bbs_to_update_dominators (bbs, conservative);
|
|
|
1278 n = VEC_length (basic_block, bbs);
|
|
|
1279
|
|
|
1280 if (n == 0)
|
|
|
1281 return;
|
|
|
1282
|
|
|
1283 if (n == 1)
|
|
|
1284 {
|
|
|
1285 bb = VEC_index (basic_block, bbs, 0);
|
|
|
1286 set_immediate_dominator (CDI_DOMINATORS, bb,
|
|
|
1287 recompute_dominator (CDI_DOMINATORS, bb));
|
|
|
1288 return;
|
|
|
1289 }
|
|
|
1290
|
|
|
1291 /* Construct the graph G. */
|
|
|
1292 map = pointer_map_create ();
|
|
|
1293 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
|
|
1294 {
|
|
|
1295 /* If the dominance tree is conservatively correct, split it now. */
|
|
|
1296 if (conservative)
|
|
|
1297 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
|
|
1298 *pointer_map_insert (map, bb) = (void *) (size_t) i;
|
|
|
1299 }
|
|
|
1300 *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
|
|
|
1301
|
|
|
1302 g = new_graph (n + 1);
|
|
|
1303 for (y = 0; y < g->n_vertices; y++)
|
|
|
1304 g->vertices[y].data = BITMAP_ALLOC (NULL);
|
|
|
1305 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
|
|
1306 {
|
|
|
1307 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1308 {
|
|
|
1309 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
|
|
|
1310 if (dom == bb)
|
|
|
1311 continue;
|
|
|
1312
|
|
|
1313 dom_i = (size_t) *pointer_map_contains (map, dom);
|
|
|
1314
|
|
|
1315 /* Do not include parallel edges to G. */
|
|
|
1316 if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
|
|
|
1317 continue;
|
|
|
1318
|
|
|
1319 bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
|
|
|
1320 add_edge (g, dom_i, i);
|
|
|
1321 }
|
|
|
1322 }
|
|
|
1323 for (y = 0; y < g->n_vertices; y++)
|
|
|
1324 BITMAP_FREE (g->vertices[y].data);
|
|
|
1325 pointer_map_destroy (map);
|
|
|
1326
|
|
|
1327 /* Find the dominator tree of G. */
|
|
|
1328 son = XNEWVEC (int, n + 1);
|
|
|
1329 brother = XNEWVEC (int, n + 1);
|
|
|
1330 parent = XNEWVEC (int, n + 1);
|
|
|
1331 graphds_domtree (g, n, parent, son, brother);
|
|
|
1332
|
|
|
1333 /* Finally, traverse the tree and find the immediate dominators. */
|
|
|
1334 for (y = n; son[y] != -1; y = son[y])
|
|
|
1335 continue;
|
|
|
1336 while (y != -1)
|
|
|
1337 {
|
|
|
1338 determine_dominators_for_sons (g, bbs, y, son, brother);
|
|
|
1339
|
|
|
1340 if (brother[y] != -1)
|
|
|
1341 {
|
|
|
1342 y = brother[y];
|
|
|
1343 while (son[y] != -1)
|
|
|
1344 y = son[y];
|
|
|
1345 }
|
|
|
1346 else
|
|
|
1347 y = parent[y];
|
|
|
1348 }
|
|
|
1349
|
|
|
1350 free (son);
|
|
|
1351 free (brother);
|
|
|
1352 free (parent);
|
|
|
1353
|
|
|
1354 free_graph (g);
|
|
|
1355 }
|
|
|
1356
|
|
|
1357 void
|
|
|
1358 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
|
|
|
1359 {
|
|
|
1360 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1361
|
|
|
1362 gcc_assert (dom_computed[dir_index]);
|
|
|
1363 gcc_assert (!bb->dom[dir_index]);
|
|
|
1364
|
|
|
1365 n_bbs_in_dom_tree[dir_index]++;
|
|
|
1366
|
|
|
1367 bb->dom[dir_index] = et_new_tree (bb);
|
|
|
1368
|
|
|
1369 if (dom_computed[dir_index] == DOM_OK)
|
|
|
1370 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
|
|
1371 }
|
|
|
1372
|
|
|
1373 void
|
|
|
1374 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
|
|
|
1375 {
|
|
|
1376 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1377
|
|
|
1378 gcc_assert (dom_computed[dir_index]);
|
|
|
1379
|
|
|
1380 et_free_tree (bb->dom[dir_index]);
|
|
|
1381 bb->dom[dir_index] = NULL;
|
|
|
1382 n_bbs_in_dom_tree[dir_index]--;
|
|
|
1383
|
|
|
1384 if (dom_computed[dir_index] == DOM_OK)
|
|
|
1385 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
|
|
1386 }
|
|
|
1387
|
|
|
1388 /* Returns the first son of BB in the dominator or postdominator tree
|
|
|
1389 as determined by DIR. */
|
|
|
1390
|
|
|
1391 basic_block
|
|
|
1392 first_dom_son (enum cdi_direction dir, basic_block bb)
|
|
|
1393 {
|
|
|
1394 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1395 struct et_node *son = bb->dom[dir_index]->son;
|
|
|
1396
|
|
|
1397 return (basic_block) (son ? son->data : NULL);
|
|
|
1398 }
|
|
|
1399
|
|
|
1400 /* Returns the next dominance son after BB in the dominator or postdominator
|
|
|
1401 tree as determined by DIR, or NULL if it was the last one. */
|
|
|
1402
|
|
|
1403 basic_block
|
|
|
1404 next_dom_son (enum cdi_direction dir, basic_block bb)
|
|
|
1405 {
|
|
|
1406 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1407 struct et_node *next = bb->dom[dir_index]->right;
|
|
|
1408
|
|
|
1409 return (basic_block) (next->father->son == next ? NULL : next->data);
|
|
|
1410 }
|
|
|
1411
|
|
|
1412 /* Return dominance availability for dominance info DIR. */
|
|
|
1413
|
|
|
1414 enum dom_state
|
|
|
1415 dom_info_state (enum cdi_direction dir)
|
|
|
1416 {
|
|
|
1417 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1418
|
|
|
1419 return dom_computed[dir_index];
|
|
|
1420 }
|
|
|
1421
|
|
|
1422 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
|
|
|
1423
|
|
|
1424 void
|
|
|
1425 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
|
|
|
1426 {
|
|
|
1427 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1428
|
|
|
1429 dom_computed[dir_index] = new_state;
|
|
|
1430 }
|
|
|
1431
|
|
|
1432 /* Returns true if dominance information for direction DIR is available. */
|
|
|
1433
|
|
|
1434 bool
|
|
|
1435 dom_info_available_p (enum cdi_direction dir)
|
|
|
1436 {
|
|
|
1437 unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
1438
|
|
|
1439 return dom_computed[dir_index] != DOM_NONE;
|
|
|
1440 }
|
|
|
1441
|
|
|
1442 void
|
|
|
1443 debug_dominance_info (enum cdi_direction dir)
|
|
|
1444 {
|
|
|
1445 basic_block bb, bb2;
|
|
|
1446 FOR_EACH_BB (bb)
|
|
|
1447 if ((bb2 = get_immediate_dominator (dir, bb)))
|
|
|
1448 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
|
|
|
1449 }
|
|
|
1450
|
|
|
1451 /* Prints to stderr representation of the dominance tree (for direction DIR)
|
|
|
1452 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
|
|
|
1453 the first line of the output is not indented. */
|
|
|
1454
|
|
|
1455 static void
|
|
|
1456 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
|
|
|
1457 unsigned indent, bool indent_first)
|
|
|
1458 {
|
|
|
1459 basic_block son;
|
|
|
1460 unsigned i;
|
|
|
1461 bool first = true;
|
|
|
1462
|
|
|
1463 if (indent_first)
|
|
|
1464 for (i = 0; i < indent; i++)
|
|
|
1465 fprintf (stderr, "\t");
|
|
|
1466 fprintf (stderr, "%d\t", root->index);
|
|
|
1467
|
|
|
1468 for (son = first_dom_son (dir, root);
|
|
|
1469 son;
|
|
|
1470 son = next_dom_son (dir, son))
|
|
|
1471 {
|
|
|
1472 debug_dominance_tree_1 (dir, son, indent + 1, !first);
|
|
|
1473 first = false;
|
|
|
1474 }
|
|
|
1475
|
|
|
1476 if (first)
|
|
|
1477 fprintf (stderr, "\n");
|
|
|
1478 }
|
|
|
1479
|
|
|
1480 /* Prints to stderr representation of the dominance tree (for direction DIR)
|
|
|
1481 rooted in ROOT. */
|
|
|
1482
|
|
|
1483 void
|
|
|
1484 debug_dominance_tree (enum cdi_direction dir, basic_block root)
|
|
|
1485 {
|
|
|
1486 debug_dominance_tree_1 (dir, root, 0, false);
|
|
|
1487 }
|
