Branch data Line data Source code
1 : : /* Calculate (post)dominators in slightly super-linear time.
2 : : Copyright (C) 2000-2024 Free Software Foundation, Inc.
3 : : Contributed by Michael Matz (matz@ifh.de).
4 : :
5 : : This file is part of GCC.
6 : :
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
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
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.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : /* This file implements the well known algorithm from Lengauer and Tarjan
22 : : to compute the dominators in a control flow graph. A basic block D is said
23 : : to dominate another block X, when all paths from the entry node of the CFG
24 : : to X go also over D. The dominance relation is a transitive reflexive
25 : : relation and its minimal transitive reduction is a tree, called the
26 : : dominator tree. So for each block X besides the entry block exists a
27 : : block I(X), called the immediate dominator of X, which is the parent of X
28 : : in the dominator tree.
29 : :
30 : : The algorithm computes this dominator tree implicitly by computing for
31 : : each block its immediate dominator. We use tree balancing and path
32 : : compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
33 : : slowly growing functional inverse of the Ackerman function. */
34 : :
35 : : #include "config.h"
36 : : #include "system.h"
37 : : #include "coretypes.h"
38 : : #include "backend.h"
39 : : #include "timevar.h"
40 : : #include "diagnostic-core.h"
41 : : #include "cfganal.h"
42 : : #include "et-forest.h"
43 : : #include "graphds.h"
44 : :
45 : : /* We name our nodes with integers, beginning with 1. Zero is reserved for
46 : : 'undefined' or 'end of list'. The name of each node is given by the dfs
47 : : number of the corresponding basic block. Please note, that we include the
48 : : artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
49 : : support multiple entry points. Its dfs number is of course 1. */
50 : :
51 : : /* Type of Basic Block aka. TBB */
52 : : typedef unsigned int TBB;
53 : :
54 : : namespace {
55 : :
56 : : /* This class holds various arrays reflecting the (sub)structure of the
57 : : flowgraph. Most of them are of type TBB and are also indexed by TBB. */
58 : :
59 : : class dom_info
60 : : {
61 : : public:
62 : : dom_info (function *, cdi_direction);
63 : : dom_info (vec <basic_block>, cdi_direction);
64 : : ~dom_info ();
65 : : void calc_dfs_tree ();
66 : : void calc_idoms ();
67 : :
68 : : inline basic_block get_idom (basic_block);
69 : : private:
70 : : void calc_dfs_tree_nonrec (basic_block);
71 : : void compress (TBB);
72 : : void dom_init (void);
73 : : TBB eval (TBB);
74 : : void link_roots (TBB, TBB);
75 : :
76 : : /* The parent of a node in the DFS tree. */
77 : : TBB *m_dfs_parent;
78 : : /* For a node x m_key[x] is roughly the node nearest to the root from which
79 : : exists a way to x only over nodes behind x. Such a node is also called
80 : : semidominator. */
81 : : TBB *m_key;
82 : : /* The value in m_path_min[x] is the node y on the path from x to the root of
83 : : the tree x is in with the smallest m_key[y]. */
84 : : TBB *m_path_min;
85 : : /* m_bucket[x] points to the first node of the set of nodes having x as
86 : : key. */
87 : : TBB *m_bucket;
88 : : /* And m_next_bucket[x] points to the next node. */
89 : : TBB *m_next_bucket;
90 : : /* After the algorithm is done, m_dom[x] contains the immediate dominator
91 : : of x. */
92 : : TBB *m_dom;
93 : :
94 : : /* The following few fields implement the structures needed for disjoint
95 : : sets. */
96 : : /* m_set_chain[x] is the next node on the path from x to the representative
97 : : of the set containing x. If m_set_chain[x]==0 then x is a root. */
98 : : TBB *m_set_chain;
99 : : /* m_set_size[x] is the number of elements in the set named by x. */
100 : : unsigned int *m_set_size;
101 : : /* m_set_child[x] is used for balancing the tree representing a set. It can
102 : : be understood as the next sibling of x. */
103 : : TBB *m_set_child;
104 : :
105 : : /* If b is the number of a basic block (BB->index), m_dfs_order[b] is the
106 : : number of that node in DFS order counted from 1. This is an index
107 : : into most of the other arrays in this structure. */
108 : : TBB *m_dfs_order;
109 : : /* Points to last element in m_dfs_order array. */
110 : : TBB *m_dfs_last;
111 : : /* If x is the DFS-index of a node which corresponds with a basic block,
112 : : m_dfs_to_bb[x] is that basic block. Note, that in our structure there are
113 : : more nodes that basic blocks, so only
114 : : m_dfs_to_bb[m_dfs_order[bb->index]]==bb is true for every basic block bb,
115 : : but not the opposite. */
116 : : basic_block *m_dfs_to_bb;
117 : :
118 : : /* This is the next free DFS number when creating the DFS tree. */
119 : : unsigned int m_dfsnum;
120 : : /* The number of nodes in the DFS tree (==m_dfsnum-1). */
121 : : unsigned int m_nodes;
122 : :
123 : : /* Blocks with bits set here have a fake edge to EXIT. These are used
124 : : to turn a DFS forest into a proper tree. */
125 : : bitmap m_fake_exit_edge;
126 : :
127 : : /* Number of basic blocks in the function being compiled. */
128 : : unsigned m_n_basic_blocks;
129 : :
130 : : /* True, if we are computing postdominators (rather than dominators). */
131 : : bool m_reverse;
132 : :
133 : : /* Start block (the entry block for forward problem, exit block for backward
134 : : problem). */
135 : : basic_block m_start_block;
136 : : /* Ending block. */
137 : : basic_block m_end_block;
138 : : };
139 : :
140 : : } // anonymous namespace
141 : :
142 : : void debug_dominance_info (cdi_direction);
143 : : void debug_dominance_tree (cdi_direction, basic_block);
144 : :
145 : : /* Allocate and zero-initialize NUM elements of type T (T must be a
146 : : POD-type). Note: after transition to C++11 or later,
147 : : `x = new_zero_array <T> (num);' can be replaced with
148 : : `x = new T[num] {};'. */
149 : :
150 : : template<typename T>
151 : 7903387952 : inline T *new_zero_array (unsigned num)
152 : : {
153 : 7903387952 : T *result = new T[num];
154 : 7903387952 : memset (result, 0, sizeof (T) * num);
155 : 7903387952 : return result;
156 : : }
157 : :
158 : : /* Helper function for constructors to initialize a part of class members. */
159 : :
160 : : void
161 : 987923494 : dom_info::dom_init (void)
162 : : {
163 : 987923494 : unsigned num = m_n_basic_blocks;
164 : :
165 : 987923494 : m_dfs_parent = new_zero_array <TBB> (num);
166 : 987923494 : m_dom = new_zero_array <TBB> (num);
167 : :
168 : 987923494 : m_path_min = new TBB[num];
169 : 987923494 : m_key = new TBB[num];
170 : 987923494 : m_set_size = new unsigned int[num];
171 : 12239007494 : for (unsigned i = 0; i < num; i++)
172 : : {
173 : 11251084000 : m_path_min[i] = m_key[i] = i;
174 : 11251084000 : m_set_size[i] = 1;
175 : : }
176 : :
177 : 987923494 : m_bucket = new_zero_array <TBB> (num);
178 : 987923494 : m_next_bucket = new_zero_array <TBB> (num);
179 : :
180 : 987923494 : m_set_chain = new_zero_array <TBB> (num);
181 : 987923494 : m_set_child = new_zero_array <TBB> (num);
182 : :
183 : 987923494 : m_dfs_to_bb = new_zero_array <basic_block> (num);
184 : :
185 : 987923494 : m_dfsnum = 1;
186 : 987923494 : m_nodes = 0;
187 : 987923494 : }
188 : :
189 : : /* Allocate all needed memory in a pessimistic fashion (so we round up). */
190 : :
191 : 987890609 : dom_info::dom_info (function *fn, cdi_direction dir)
192 : : {
193 : 987890609 : m_n_basic_blocks = n_basic_blocks_for_fn (fn);
194 : :
195 : 987890609 : dom_init ();
196 : :
197 : 987890609 : unsigned last_bb_index = last_basic_block_for_fn (fn);
198 : 987890609 : m_dfs_order = new_zero_array <TBB> (last_bb_index + 1);
199 : 987890609 : m_dfs_last = &m_dfs_order[last_bb_index];
200 : :
201 : 987890609 : switch (dir)
202 : : {
203 : 963170825 : case CDI_DOMINATORS:
204 : 963170825 : m_reverse = false;
205 : 963170825 : m_fake_exit_edge = NULL;
206 : 963170825 : m_start_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
207 : 963170825 : m_end_block = EXIT_BLOCK_PTR_FOR_FN (fn);
208 : 963170825 : break;
209 : 24719784 : case CDI_POST_DOMINATORS:
210 : 24719784 : m_reverse = true;
211 : 24719784 : m_fake_exit_edge = BITMAP_ALLOC (NULL);
212 : 24719784 : m_start_block = EXIT_BLOCK_PTR_FOR_FN (fn);
213 : 24719784 : m_end_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
214 : 24719784 : break;
215 : 0 : default:
216 : 0 : gcc_unreachable ();
217 : : }
218 : 987890609 : }
219 : :
220 : : /* Constructor for reducible region REGION. */
221 : :
222 : 32885 : dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
223 : : {
224 : 32885 : m_n_basic_blocks = region.length ();
225 : 32885 : unsigned nm1 = m_n_basic_blocks - 1;
226 : :
227 : 32885 : dom_init ();
228 : :
229 : : /* Determine max basic block index in region. */
230 : 32885 : int max_index = region[0]->index;
231 : 244463 : for (unsigned i = 1; i <= nm1; i++)
232 : 211578 : if (region[i]->index > max_index)
233 : : max_index = region[i]->index;
234 : 32885 : max_index += 1; /* set index on the first bb out of region. */
235 : :
236 : 32885 : m_dfs_order = new_zero_array <TBB> (max_index + 1);
237 : 32885 : m_dfs_last = &m_dfs_order[max_index];
238 : :
239 : 32885 : m_fake_exit_edge = NULL; /* Assume that region is reducible. */
240 : :
241 : 32885 : switch (dir)
242 : : {
243 : 0 : case CDI_DOMINATORS:
244 : 0 : m_reverse = false;
245 : 0 : m_start_block = region[0];
246 : 0 : m_end_block = region[nm1];
247 : 0 : break;
248 : 32885 : case CDI_POST_DOMINATORS:
249 : 32885 : m_reverse = true;
250 : 32885 : m_start_block = region[nm1];
251 : 32885 : m_end_block = region[0];
252 : 32885 : break;
253 : 0 : default:
254 : 0 : gcc_unreachable ();
255 : : }
256 : 32885 : }
257 : :
258 : : inline basic_block
259 : 9275302782 : dom_info::get_idom (basic_block bb)
260 : : {
261 : 9275302782 : TBB d = m_dom[m_dfs_order[bb->index]];
262 : 9275302782 : return m_dfs_to_bb[d];
263 : : }
264 : :
265 : : /* Map dominance calculation type to array index used for various
266 : : dominance information arrays. This version is simple -- it will need
267 : : to be modified, obviously, if additional values are added to
268 : : cdi_direction. */
269 : :
270 : : static inline unsigned int
271 : 29954291775 : dom_convert_dir_to_idx (cdi_direction dir)
272 : : {
273 : 29954291775 : gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
274 : 29954291775 : return dir - 1;
275 : : }
276 : :
277 : : /* Free all allocated memory in dom_info. */
278 : :
279 : 987923494 : dom_info::~dom_info ()
280 : : {
281 : 987923494 : delete[] m_dfs_parent;
282 : 987923494 : delete[] m_path_min;
283 : 987923494 : delete[] m_key;
284 : 987923494 : delete[] m_dom;
285 : 987923494 : delete[] m_bucket;
286 : 987923494 : delete[] m_next_bucket;
287 : 987923494 : delete[] m_set_chain;
288 : 987923494 : delete[] m_set_size;
289 : 987923494 : delete[] m_set_child;
290 : 987923494 : delete[] m_dfs_order;
291 : 987923494 : delete[] m_dfs_to_bb;
292 : 987923494 : BITMAP_FREE (m_fake_exit_edge);
293 : 987923494 : }
294 : :
295 : : /* The nonrecursive variant of creating a DFS tree. BB is the starting basic
296 : : block for this tree and m_reverse is true, if predecessors should be visited
297 : : instead of successors of a node. After this is done all nodes reachable
298 : : from BB were visited, have assigned their dfs number and are linked together
299 : : to form a tree. */
300 : :
301 : : void
302 : 999906719 : dom_info::calc_dfs_tree_nonrec (basic_block bb)
303 : : {
304 : 999906719 : edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
305 : 999906719 : int sp = 0;
306 : 1963077544 : unsigned d_i = dom_convert_dir_to_idx (m_reverse ? CDI_POST_DOMINATORS
307 : : : CDI_DOMINATORS);
308 : :
309 : : /* Initialize the first edge. */
310 : 999906719 : edge_iterator ei = m_reverse ? ei_start (bb->preds)
311 : 963170825 : : ei_start (bb->succs);
312 : :
313 : : /* When the stack is empty we break out of this loop. */
314 : 9263253787 : while (1)
315 : : {
316 : : basic_block bn;
317 : : edge_iterator einext;
318 : :
319 : : /* This loop traverses edges e in depth first manner, and fills the
320 : : stack. */
321 : 24227899923 : while (!ei_end_p (ei))
322 : : {
323 : 13964739417 : edge e = ei_edge (ei);
324 : :
325 : : /* Deduce from E the current and the next block (BB and BN), and the
326 : : next edge. */
327 : 13964739417 : if (m_reverse)
328 : : {
329 : 314599173 : bn = e->src;
330 : :
331 : : /* If the next node BN is either already visited or a border
332 : : block or out of region the current edge is useless, and simply
333 : : overwritten with the next edge out of the current node. */
334 : 314599173 : if (bn == m_end_block || bn->dom[d_i] == NULL
335 : 289845645 : || m_dfs_order[bn->index])
336 : : {
337 : 117967018 : ei_next (&ei);
338 : 117967018 : continue;
339 : : }
340 : 196632155 : bb = e->dest;
341 : 196632155 : einext = ei_start (bn->preds);
342 : : }
343 : : else
344 : : {
345 : 13650140244 : bn = e->dest;
346 : 13650140244 : if (bn == m_end_block || bn->dom[d_i] == NULL
347 : 12698303572 : || m_dfs_order[bn->index])
348 : : {
349 : 4583518612 : ei_next (&ei);
350 : 4583518612 : continue;
351 : : }
352 : 9066621632 : bb = e->src;
353 : 9066621632 : einext = ei_start (bn->succs);
354 : : }
355 : :
356 : 9263253787 : gcc_assert (bn != m_start_block);
357 : :
358 : : /* Fill the DFS tree info calculatable _before_ recursing. */
359 : 9263253787 : TBB my_i;
360 : 9263253787 : if (bb != m_start_block)
361 : 8273711319 : my_i = m_dfs_order[bb->index];
362 : : else
363 : 989542468 : my_i = *m_dfs_last;
364 : 9263253787 : TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
365 : 9263253787 : m_dfs_to_bb[child_i] = bn;
366 : 9263253787 : m_dfs_parent[child_i] = my_i;
367 : :
368 : : /* Save the current point in the CFG on the stack, and recurse. */
369 : 9263253787 : stack[sp++] = ei;
370 : 9263253787 : ei = einext;
371 : : }
372 : :
373 : 10263160506 : if (!sp)
374 : : break;
375 : 9263253787 : ei = stack[--sp];
376 : :
377 : : /* OK. The edge-list was exhausted, meaning normally we would
378 : : end the recursion. After returning from the recursive call,
379 : : there were (may be) other statements which were run after a
380 : : child node was completely considered by DFS. Here is the
381 : : point to do it in the non-recursive variant.
382 : : E.g. The block just completed is in e->dest for forward DFS,
383 : : the block not yet completed (the parent of the one above)
384 : : in e->src. This could be used e.g. for computing the number of
385 : : descendants or the tree depth. */
386 : 9263253787 : ei_next (&ei);
387 : 9263253787 : }
388 : 999906719 : delete[] stack;
389 : 999906719 : }
390 : :
391 : : /* The main entry for calculating the DFS tree or forest. m_reverse is true,
392 : : if we are interested in the reverse flow graph. In that case the result is
393 : : not necessarily a tree but a forest, because there may be nodes from which
394 : : the EXIT_BLOCK is unreachable. */
395 : :
396 : : void
397 : 987923494 : dom_info::calc_dfs_tree ()
398 : : {
399 : 987923494 : *m_dfs_last = m_dfsnum;
400 : 987923494 : m_dfs_to_bb[m_dfsnum] = m_start_block;
401 : 987923494 : m_dfsnum++;
402 : :
403 : 987923494 : calc_dfs_tree_nonrec (m_start_block);
404 : :
405 : 987923494 : if (m_fake_exit_edge)
406 : : {
407 : : /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
408 : : They are reverse-unreachable. In the dom-case we disallow such
409 : : nodes, but in post-dom we have to deal with them.
410 : :
411 : : There are two situations in which this occurs. First, noreturn
412 : : functions. Second, infinite loops. In the first case we need to
413 : : pretend that there is an edge to the exit block. In the second
414 : : case, we wind up with a forest. We need to process all noreturn
415 : : blocks before we know if we've got any infinite loops. */
416 : :
417 : 24719784 : basic_block b;
418 : 24719784 : bool saw_unconnected = false;
419 : :
420 : 233156471 : FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
421 : : {
422 : 208436687 : if (EDGE_COUNT (b->succs) > 0)
423 : : {
424 : 196537493 : if (m_dfs_order[b->index] == 0)
425 : 1190680 : saw_unconnected = true;
426 : 196537493 : continue;
427 : : }
428 : 11899194 : bitmap_set_bit (m_fake_exit_edge, b->index);
429 : 11899194 : m_dfs_order[b->index] = m_dfsnum;
430 : 11899194 : m_dfs_to_bb[m_dfsnum] = b;
431 : 11899194 : m_dfs_parent[m_dfsnum] = *m_dfs_last;
432 : 11899194 : m_dfsnum++;
433 : 11899194 : calc_dfs_tree_nonrec (b);
434 : : }
435 : :
436 : 24719784 : if (saw_unconnected)
437 : : {
438 : 8891821 : FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
439 : : {
440 : 8627753 : if (m_dfs_order[b->index])
441 : 8543722 : continue;
442 : 84031 : basic_block b2 = dfs_find_deadend (b);
443 : 84031 : gcc_checking_assert (m_dfs_order[b2->index] == 0);
444 : 84031 : bitmap_set_bit (m_fake_exit_edge, b2->index);
445 : 84031 : m_dfs_order[b2->index] = m_dfsnum;
446 : 84031 : m_dfs_to_bb[m_dfsnum] = b2;
447 : 84031 : m_dfs_parent[m_dfsnum] = *m_dfs_last;
448 : 84031 : m_dfsnum++;
449 : 84031 : calc_dfs_tree_nonrec (b2);
450 : 84031 : gcc_checking_assert (m_dfs_order[b->index]);
451 : : }
452 : : }
453 : : }
454 : :
455 : 987923494 : m_nodes = m_dfsnum - 1;
456 : :
457 : : /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
458 : 987923494 : gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1);
459 : 987923494 : }
460 : :
461 : : /* Compress the path from V to the root of its set and update path_min at the
462 : : same time. After compress(di, V) set_chain[V] is the root of the set V is
463 : : in and path_min[V] is the node with the smallest key[] value on the path
464 : : from V to that root. */
465 : :
466 : : void
467 : 3600064428 : dom_info::compress (TBB v)
468 : : {
469 : : /* Btw. It's not worth to unrecurse compress() as the depth is usually not
470 : : greater than 5 even for huge graphs (I've not seen call depth > 4).
471 : : Also performance wise compress() ranges _far_ behind eval(). */
472 : 3600064428 : TBB parent = m_set_chain[v];
473 : 3600064428 : if (m_set_chain[parent])
474 : : {
475 : 1994689774 : compress (parent);
476 : 1994689774 : if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
477 : 1359151351 : m_path_min[v] = m_path_min[parent];
478 : 1994689774 : m_set_chain[v] = m_set_chain[parent];
479 : : }
480 : 3600064428 : }
481 : :
482 : : /* Compress the path from V to the set root of V if needed (when the root has
483 : : changed since the last call). Returns the node with the smallest key[]
484 : : value on the path from V to the root. */
485 : :
486 : : inline TBB
487 : 12245898066 : dom_info::eval (TBB v)
488 : : {
489 : : /* The representative of the set V is in, also called root (as the set
490 : : representation is a tree). */
491 : 12245898066 : TBB rep = m_set_chain[v];
492 : :
493 : : /* V itself is the root. */
494 : 12245898066 : if (!rep)
495 : 2575673873 : return m_path_min[v];
496 : :
497 : : /* Compress only if necessary. */
498 : 9670224193 : if (m_set_chain[rep])
499 : : {
500 : 1605374654 : compress (v);
501 : 1605374654 : rep = m_set_chain[v];
502 : : }
503 : :
504 : 9670224193 : if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
505 : : return m_path_min[v];
506 : : else
507 : 1666674834 : return m_path_min[rep];
508 : : }
509 : :
510 : : /* This essentially merges the two sets of V and W, giving a single set with
511 : : the new root V. The internal representation of these disjoint sets is a
512 : : balanced tree. Currently link(V,W) is only used with V being the parent
513 : : of W. */
514 : :
515 : : void
516 : 9275237012 : dom_info::link_roots (TBB v, TBB w)
517 : : {
518 : 9275237012 : TBB s = w;
519 : :
520 : : /* Rebalance the tree. */
521 : 13739986016 : while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
522 : : {
523 : 4464749004 : if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
524 : 4464749004 : >= 2 * m_set_size[m_set_child[s]])
525 : : {
526 : 1451451437 : m_set_chain[m_set_child[s]] = s;
527 : 1451451437 : m_set_child[s] = m_set_child[m_set_child[s]];
528 : : }
529 : : else
530 : : {
531 : 3013297567 : m_set_size[m_set_child[s]] = m_set_size[s];
532 : 3013297567 : s = m_set_chain[s] = m_set_child[s];
533 : : }
534 : : }
535 : :
536 : 9275237012 : m_path_min[s] = m_path_min[w];
537 : 9275237012 : m_set_size[v] += m_set_size[w];
538 : 9275237012 : if (m_set_size[v] < 2 * m_set_size[w])
539 : 5314141547 : std::swap (m_set_child[v], s);
540 : :
541 : : /* Merge all subtrees. */
542 : 13551991166 : while (s)
543 : : {
544 : 4276754154 : m_set_chain[s] = v;
545 : 4276754154 : s = m_set_child[s];
546 : : }
547 : 9275237012 : }
548 : :
549 : : /* This calculates the immediate dominators (or post-dominators). THIS is our
550 : : working structure and should hold the DFS forest.
551 : : On return the immediate dominator to node V is in m_dom[V]. */
552 : :
553 : : void
554 : 987923494 : dom_info::calc_idoms ()
555 : : {
556 : : /* Go backwards in DFS order, to first look at the leafs. */
557 : 10263160506 : for (TBB v = m_nodes; v > 1; v--)
558 : : {
559 : 9275237012 : basic_block bb = m_dfs_to_bb[v];
560 : 9275237012 : edge e;
561 : :
562 : 9275237012 : TBB par = m_dfs_parent[v];
563 : 9275237012 : TBB k = v;
564 : :
565 : 9275237012 : edge_iterator ei = m_reverse ? ei_start (bb->succs)
566 : 9066621632 : : ei_start (bb->preds);
567 : 9275237012 : edge_iterator einext;
568 : :
569 : 9275237012 : if (m_fake_exit_edge)
570 : : {
571 : : /* If this block has a fake edge to exit, process that first. */
572 : 208436687 : if (bitmap_bit_p (m_fake_exit_edge, bb->index))
573 : : {
574 : 11983225 : einext = ei;
575 : 11983225 : einext.index = 0;
576 : 11983225 : goto do_fake_exit_edge;
577 : : }
578 : : }
579 : :
580 : : /* Search all direct predecessors for the smallest node with a path
581 : : to them. That way we have the smallest node with also a path to
582 : : us only over nodes behind us. In effect we search for our
583 : : semidominator. */
584 : 22263386229 : while (!ei_end_p (ei))
585 : : {
586 : 12988149217 : basic_block b;
587 : 12988149217 : TBB k1;
588 : :
589 : 12988149217 : e = ei_edge (ei);
590 : 12988149217 : b = m_reverse ? e->dest : e->src;
591 : 12988149217 : einext = ei;
592 : 12988149217 : ei_next (&einext);
593 : :
594 : 12988149217 : if (b == m_start_block)
595 : : {
596 : 989542471 : do_fake_exit_edge:
597 : 1001525696 : k1 = *m_dfs_last;
598 : : }
599 : : else
600 : 11998606746 : k1 = m_dfs_order[b->index];
601 : :
602 : : /* Call eval() only if really needed. If k1 is above V in DFS tree,
603 : : then we know, that eval(k1) == k1 and key[k1] == k1. */
604 : 13000132442 : if (k1 > v)
605 : 2970661054 : k1 = m_key[eval (k1)];
606 : 13000132442 : if (k1 < k)
607 : : k = k1;
608 : :
609 : 13000132442 : ei = einext;
610 : : }
611 : :
612 : 9275237012 : m_key[v] = k;
613 : 9275237012 : link_roots (par, v);
614 : 9275237012 : m_next_bucket[v] = m_bucket[k];
615 : 9275237012 : m_bucket[k] = v;
616 : :
617 : : /* Transform semidominators into dominators. */
618 : 18550474024 : for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
619 : : {
620 : 9275237012 : k = eval (w);
621 : 9275237012 : if (m_key[k] < m_key[w])
622 : 45551271 : m_dom[w] = k;
623 : : else
624 : 9229685741 : m_dom[w] = par;
625 : : }
626 : : /* We don't need to cleanup next_bucket[]. */
627 : 9275237012 : m_bucket[par] = 0;
628 : : }
629 : :
630 : : /* Explicitly define the dominators. */
631 : 987923494 : m_dom[1] = 0;
632 : 10263160506 : for (TBB v = 2; v <= m_nodes; v++)
633 : 9275237012 : if (m_dom[v] != m_key[v])
634 : 45551271 : m_dom[v] = m_dom[m_dom[v]];
635 : 987923494 : }
636 : :
637 : : /* Assign dfs numbers starting from NUM to NODE and its sons. */
638 : :
639 : : static void
640 : 493653349 : assign_dfs_numbers (struct et_node *node, int *num)
641 : : {
642 : 493653349 : et_node *n = node;
643 : 2715801987 : while (1)
644 : : {
645 : 2715801987 : n->dfs_num_in = (*num)++;
646 : 2715801987 : if (n->son)
647 : : n = n->son;
648 : : else
649 : : {
650 : 2715801987 : while (!n->right || n->right == n->father->son)
651 : : {
652 : 1825396998 : n->dfs_num_out = (*num)++;
653 : 1825396998 : if (n == node)
654 : 493653349 : return;
655 : 1331743649 : n = n->father;
656 : : }
657 : 890404989 : n->dfs_num_out = (*num)++;
658 : 890404989 : n = n->right;
659 : : }
660 : : }
661 : : }
662 : :
663 : : /* Compute the data necessary for fast resolving of dominator queries in a
664 : : static dominator tree. */
665 : :
666 : : static void
667 : 246826784 : compute_dom_fast_query (enum cdi_direction dir)
668 : : {
669 : 246826784 : int num = 0;
670 : 246826784 : basic_block bb;
671 : 246826784 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
672 : :
673 : 246826784 : gcc_checking_assert (dom_info_available_p (dir));
674 : :
675 : 246826784 : if (dom_computed[dir_index] == DOM_OK)
676 : 0 : return;
677 : :
678 : 2962628771 : FOR_ALL_BB_FN (bb, cfun)
679 : : {
680 : 2715801987 : if (!bb->dom[dir_index]->father)
681 : 493653349 : assign_dfs_numbers (bb->dom[dir_index], &num);
682 : : }
683 : :
684 : 246826784 : dom_computed[dir_index] = DOM_OK;
685 : : }
686 : :
687 : : /* Analogous to the previous function but compute the data for reducible
688 : : region REGION. */
689 : :
690 : : static void
691 : 32885 : compute_dom_fast_query_in_region (enum cdi_direction dir,
692 : : vec<basic_block> region)
693 : : {
694 : 32885 : int num = 0;
695 : 32885 : basic_block bb;
696 : 32885 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
697 : :
698 : 32885 : gcc_checking_assert (dom_info_available_p (dir));
699 : :
700 : 32885 : if (dom_computed[dir_index] == DOM_OK)
701 : 0 : return;
702 : :
703 : : /* Assign dfs numbers for region nodes except for entry and exit nodes. */
704 : 423156 : for (unsigned int i = 1; i < region.length () - 1; i++)
705 : : {
706 : 178693 : bb = region[i];
707 : 178693 : if (!bb->dom[dir_index]->father)
708 : 0 : assign_dfs_numbers (bb->dom[dir_index], &num);
709 : : }
710 : :
711 : 32885 : dom_computed[dir_index] = DOM_OK;
712 : : }
713 : :
714 : : /* The main entry point into this module. DIR is set depending on whether
715 : : we want to compute dominators or postdominators. If COMPUTE_FAST_QUERY
716 : : is false then the DFS numbers allowing for a O(1) dominance query
717 : : are not computed. */
718 : :
719 : : void
720 : 516590713 : calculate_dominance_info (cdi_direction dir, bool compute_fast_query)
721 : : {
722 : 516590713 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
723 : :
724 : 516590713 : if (dom_computed[dir_index] == DOM_OK)
725 : : {
726 : 261559328 : checking_verify_dominators (dir);
727 : 261559328 : return;
728 : : }
729 : :
730 : 255031385 : timevar_push (TV_DOMINANCE);
731 : 255031385 : if (!dom_info_available_p (dir))
732 : : {
733 : 232471894 : gcc_assert (!n_bbs_in_dom_tree[dir_index]);
734 : :
735 : 232471894 : basic_block b;
736 : 2565549287 : FOR_ALL_BB_FN (b, cfun)
737 : : {
738 : 2333077393 : b->dom[dir_index] = et_new_tree (b);
739 : : }
740 : 232471894 : n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
741 : :
742 : 232471894 : dom_info di (cfun, dir);
743 : 232471894 : di.calc_dfs_tree ();
744 : 232471894 : di.calc_idoms ();
745 : :
746 : 2100605499 : FOR_EACH_BB_FN (b, cfun)
747 : : {
748 : 1868133605 : if (basic_block d = di.get_idom (b))
749 : 1868133605 : et_set_father (b->dom[dir_index], d->dom[dir_index]);
750 : : }
751 : :
752 : 232471894 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
753 : 232471894 : }
754 : : else
755 : 22559491 : checking_verify_dominators (dir);
756 : :
757 : 255031385 : if (compute_fast_query)
758 : 246826784 : compute_dom_fast_query (dir);
759 : :
760 : 255031385 : timevar_pop (TV_DOMINANCE);
761 : : }
762 : :
763 : : /* Analogous to the previous function but compute dominance info for regions
764 : : which are single entry, multiple exit regions for CDI_DOMINATORs and
765 : : multiple entry, single exit regions for CDI_POST_DOMINATORs. */
766 : :
767 : : void
768 : 32885 : calculate_dominance_info_for_region (cdi_direction dir,
769 : : vec<basic_block> region)
770 : : {
771 : 32885 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
772 : 32885 : basic_block bb;
773 : 32885 : unsigned int i;
774 : :
775 : 32885 : if (dom_computed[dir_index] == DOM_OK)
776 : 0 : return;
777 : :
778 : 32885 : timevar_push (TV_DOMINANCE);
779 : : /* Assume that dom info is not partially computed. */
780 : 32885 : gcc_assert (!dom_info_available_p (dir));
781 : :
782 : 277348 : FOR_EACH_VEC_ELT (region, i, bb)
783 : : {
784 : 244463 : bb->dom[dir_index] = et_new_tree (bb);
785 : : }
786 : 32885 : dom_info di (region, dir);
787 : 32885 : di.calc_dfs_tree ();
788 : 32885 : di.calc_idoms ();
789 : :
790 : 277348 : FOR_EACH_VEC_ELT (region, i, bb)
791 : 244463 : if (basic_block d = di.get_idom (bb))
792 : 178693 : et_set_father (bb->dom[dir_index], d->dom[dir_index]);
793 : :
794 : 32885 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
795 : 32885 : compute_dom_fast_query_in_region (dir, region);
796 : :
797 : 32885 : timevar_pop (TV_DOMINANCE);
798 : 32885 : }
799 : :
800 : : /* Free dominance information for direction DIR. */
801 : : void
802 : 414373039 : free_dominance_info (function *fn, enum cdi_direction dir)
803 : : {
804 : 414373039 : basic_block bb;
805 : 414373039 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
806 : :
807 : 414373039 : if (!dom_info_available_p (fn, dir))
808 : : return;
809 : :
810 : 2551467551 : FOR_ALL_BB_FN (bb, fn)
811 : : {
812 : 2319060466 : et_free_tree_force (bb->dom[dir_index]);
813 : 2319060466 : bb->dom[dir_index] = NULL;
814 : : }
815 : 232407085 : et_free_pools ();
816 : :
817 : 232407085 : fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
818 : :
819 : 232407085 : fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
820 : : }
821 : :
822 : : void
823 : 269443130 : free_dominance_info (enum cdi_direction dir)
824 : : {
825 : 269443130 : free_dominance_info (cfun, dir);
826 : 269443130 : }
827 : :
828 : : /* Free dominance information for direction DIR in region REGION. */
829 : :
830 : : void
831 : 32885 : free_dominance_info_for_region (function *fn,
832 : : enum cdi_direction dir,
833 : : vec<basic_block> region)
834 : : {
835 : 32885 : basic_block bb;
836 : 32885 : unsigned int i;
837 : 32885 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
838 : :
839 : 32885 : if (!dom_info_available_p (dir))
840 : 32885 : return;
841 : :
842 : 277348 : FOR_EACH_VEC_ELT (region, i, bb)
843 : : {
844 : 244463 : et_free_tree_force (bb->dom[dir_index]);
845 : 244463 : bb->dom[dir_index] = NULL;
846 : : }
847 : 32885 : et_free_pools ();
848 : :
849 : 32885 : fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
850 : :
851 : 32885 : fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
852 : : }
853 : :
854 : : /* Return the immediate dominator of basic block BB. */
855 : : basic_block
856 : 9235284329 : get_immediate_dominator (enum cdi_direction dir, basic_block bb)
857 : : {
858 : 9235284329 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
859 : 9235284329 : struct et_node *node = bb->dom[dir_index];
860 : :
861 : 9235284329 : gcc_checking_assert (dom_computed[dir_index]);
862 : :
863 : 9235284329 : if (!node->father)
864 : : return NULL;
865 : :
866 : 9210998036 : return (basic_block) node->father->data;
867 : : }
868 : :
869 : : /* Set the immediate dominator of the block possibly removing
870 : : existing edge. NULL can be used to remove any edge. */
871 : : void
872 : 71985059 : set_immediate_dominator (enum cdi_direction dir, basic_block bb,
873 : : basic_block dominated_by)
874 : : {
875 : 71985059 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
876 : 71985059 : struct et_node *node = bb->dom[dir_index];
877 : :
878 : 71985059 : gcc_checking_assert (dom_computed[dir_index]);
879 : :
880 : 71985059 : if (node->father)
881 : : {
882 : 38874271 : if (node->father->data == dominated_by)
883 : : return;
884 : 16493260 : et_split (node);
885 : : }
886 : :
887 : 49604048 : if (dominated_by)
888 : 47067034 : et_set_father (node, dominated_by->dom[dir_index]);
889 : :
890 : 49604048 : if (dom_computed[dir_index] == DOM_OK)
891 : 1289678 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
892 : : }
893 : :
894 : : /* Returns the list of basic blocks immediately dominated by BB, in the
895 : : direction DIR. */
896 : : auto_vec<basic_block>
897 : 769111 : get_dominated_by (enum cdi_direction dir, basic_block bb)
898 : : {
899 : 769111 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
900 : 769111 : struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
901 : 769111 : auto_vec<basic_block> bbs;
902 : :
903 : 769111 : gcc_checking_assert (dom_computed[dir_index]);
904 : :
905 : 769111 : if (!son)
906 : : return bbs;
907 : :
908 : 466837 : bbs.safe_push ((basic_block) son->data);
909 : 793655 : for (ason = son->right; ason != son; ason = ason->right)
910 : 326818 : bbs.safe_push ((basic_block) ason->data);
911 : :
912 : : return bbs;
913 : : }
914 : :
915 : : /* Returns the list of basic blocks that are immediately dominated (in
916 : : direction DIR) by some block between N_REGION ones stored in REGION,
917 : : except for blocks in the REGION itself. */
918 : :
919 : : auto_vec<basic_block>
920 : 714836 : get_dominated_by_region (enum cdi_direction dir, basic_block *region,
921 : : unsigned n_region)
922 : : {
923 : 714836 : unsigned i;
924 : 714836 : basic_block dom;
925 : 714836 : auto_vec<basic_block> doms;
926 : :
927 : 1989351 : for (i = 0; i < n_region; i++)
928 : 1274515 : region[i]->flags |= BB_DUPLICATED;
929 : 1989351 : for (i = 0; i < n_region; i++)
930 : 1274515 : for (dom = first_dom_son (dir, region[i]);
931 : 3163981 : dom;
932 : 1889466 : dom = next_dom_son (dir, dom))
933 : 1889466 : if (!(dom->flags & BB_DUPLICATED))
934 : 1329787 : doms.safe_push (dom);
935 : 1989351 : for (i = 0; i < n_region; i++)
936 : 1274515 : region[i]->flags &= ~BB_DUPLICATED;
937 : :
938 : 714836 : return doms;
939 : : }
940 : :
941 : : /* Returns the list of basic blocks including BB dominated by BB, in the
942 : : direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
943 : : produce a vector containing all dominated blocks. The vector will be sorted
944 : : in preorder. */
945 : :
946 : : auto_vec<basic_block>
947 : 11774979 : get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
948 : : {
949 : 11774979 : auto_vec<basic_block> bbs;
950 : 11774979 : unsigned i;
951 : 11774979 : unsigned next_level_start;
952 : :
953 : 11774979 : i = 0;
954 : 11774979 : bbs.safe_push (bb);
955 : 11774979 : next_level_start = 1; /* = bbs.length (); */
956 : :
957 : 111970920 : do
958 : : {
959 : 111970920 : basic_block son;
960 : :
961 : 111970920 : bb = bbs[i++];
962 : 111970920 : for (son = first_dom_son (dir, bb);
963 : 212251158 : son;
964 : 100280238 : son = next_dom_son (dir, son))
965 : 100280238 : bbs.safe_push (son);
966 : :
967 : 111970920 : if (i == next_level_start && --depth)
968 : 50059038 : next_level_start = bbs.length ();
969 : : }
970 : 111970920 : while (i < next_level_start);
971 : :
972 : 11774979 : return bbs;
973 : : }
974 : :
975 : : /* Returns the list of basic blocks including BB dominated by BB, in the
976 : : direction DIR. The vector will be sorted in preorder. */
977 : :
978 : : auto_vec<basic_block>
979 : 11387028 : get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
980 : : {
981 : 11387028 : return get_dominated_to_depth (dir, bb, 0);
982 : : }
983 : :
984 : : /* Redirect all edges pointing to BB to TO. */
985 : : void
986 : 14654835 : redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
987 : : basic_block to)
988 : : {
989 : 14654835 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
990 : 14654835 : struct et_node *bb_node, *to_node, *son;
991 : :
992 : 14654835 : bb_node = bb->dom[dir_index];
993 : 14654835 : to_node = to->dom[dir_index];
994 : :
995 : 14654835 : gcc_checking_assert (dom_computed[dir_index]);
996 : :
997 : 14654835 : if (!bb_node->son)
998 : : return;
999 : :
1000 : 26340558 : while (bb_node->son)
1001 : : {
1002 : 15503615 : son = bb_node->son;
1003 : :
1004 : 15503615 : et_split (son);
1005 : 15503615 : et_set_father (son, to_node);
1006 : : }
1007 : :
1008 : 10836943 : if (dom_computed[dir_index] == DOM_OK)
1009 : 1196019 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1010 : : }
1011 : :
1012 : : /* Find first basic block in the tree dominating both BB1 and BB2. */
1013 : : basic_block
1014 : 111377526 : nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1015 : : {
1016 : 111377526 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1017 : :
1018 : 111377526 : gcc_checking_assert (dom_computed[dir_index]);
1019 : :
1020 : 111377526 : if (!bb1)
1021 : : return bb2;
1022 : 108680911 : if (!bb2)
1023 : : return bb1;
1024 : :
1025 : 108680911 : return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
1026 : : }
1027 : :
1028 : :
1029 : : /* Find the nearest common dominator for the basic blocks in BLOCKS,
1030 : : using dominance direction DIR. */
1031 : :
1032 : : basic_block
1033 : 10584384 : nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1034 : : {
1035 : 10584384 : unsigned i, first;
1036 : 10584384 : bitmap_iterator bi;
1037 : 10584384 : basic_block dom;
1038 : :
1039 : 10584384 : first = bitmap_first_set_bit (blocks);
1040 : 10584384 : dom = BASIC_BLOCK_FOR_FN (cfun, first);
1041 : 64535526 : EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
1042 : 53951142 : if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
1043 : 42932191 : dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
1044 : :
1045 : 10584384 : return dom;
1046 : : }
1047 : :
1048 : : /* Given a dominator tree, we can determine whether one thing
1049 : : dominates another in constant time by using two DFS numbers:
1050 : :
1051 : : 1. The number for when we visit a node on the way down the tree
1052 : : 2. The number for when we visit a node on the way back up the tree
1053 : :
1054 : : You can view these as bounds for the range of dfs numbers the
1055 : : nodes in the subtree of the dominator tree rooted at that node
1056 : : will contain.
1057 : :
1058 : : The dominator tree is always a simple acyclic tree, so there are
1059 : : only three possible relations two nodes in the dominator tree have
1060 : : to each other:
1061 : :
1062 : : 1. Node A is above Node B (and thus, Node A dominates node B)
1063 : :
1064 : : A
1065 : : |
1066 : : C
1067 : : / \
1068 : : B D
1069 : :
1070 : :
1071 : : In the above case, DFS_Number_In of A will be <= DFS_Number_In of
1072 : : B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
1073 : : because we must hit A in the dominator tree *before* B on the walk
1074 : : down, and we will hit A *after* B on the walk back up
1075 : :
1076 : : 2. Node A is below node B (and thus, node B dominates node A)
1077 : :
1078 : :
1079 : : B
1080 : : |
1081 : : A
1082 : : / \
1083 : : C D
1084 : :
1085 : : In the above case, DFS_Number_In of A will be >= DFS_Number_In of
1086 : : B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
1087 : :
1088 : : This is because we must hit A in the dominator tree *after* B on
1089 : : the walk down, and we will hit A *before* B on the walk back up
1090 : :
1091 : : 3. Node A and B are siblings (and thus, neither dominates the other)
1092 : :
1093 : : C
1094 : : |
1095 : : D
1096 : : / \
1097 : : A B
1098 : :
1099 : : In the above case, DFS_Number_In of A will *always* be <=
1100 : : DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
1101 : : DFS_Number_Out of B. This is because we will always finish the dfs
1102 : : walk of one of the subtrees before the other, and thus, the dfs
1103 : : numbers for one subtree can't intersect with the range of dfs
1104 : : numbers for the other subtree. If you swap A and B's position in
1105 : : the dominator tree, the comparison changes direction, but the point
1106 : : is that both comparisons will always go the same way if there is no
1107 : : dominance relationship.
1108 : :
1109 : : Thus, it is sufficient to write
1110 : :
1111 : : A_Dominates_B (node A, node B)
1112 : : {
1113 : : return DFS_Number_In(A) <= DFS_Number_In(B)
1114 : : && DFS_Number_Out (A) >= DFS_Number_Out(B);
1115 : : }
1116 : :
1117 : : A_Dominated_by_B (node A, node B)
1118 : : {
1119 : : return DFS_Number_In(A) >= DFS_Number_In(B)
1120 : : && DFS_Number_Out (A) <= DFS_Number_Out(B);
1121 : : } */
1122 : :
1123 : : /* Return TRUE in case BB1 is dominated by BB2. */
1124 : : bool
1125 : 10436197338 : dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
1126 : : {
1127 : 10436197338 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1128 : 10436197338 : struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
1129 : :
1130 : 10436197338 : gcc_checking_assert (dom_computed[dir_index]);
1131 : :
1132 : 10436197338 : if (dom_computed[dir_index] == DOM_OK)
1133 : 9712062243 : return (n1->dfs_num_in >= n2->dfs_num_in
1134 : 14734298465 : && n1->dfs_num_out <= n2->dfs_num_out);
1135 : :
1136 : 724135095 : return et_below (n1, n2);
1137 : : }
1138 : :
1139 : : /* Returns the entry dfs number for basic block BB, in the direction DIR. */
1140 : :
1141 : : unsigned
1142 : 77165407 : bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1143 : : {
1144 : 77165407 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1145 : 77165407 : struct et_node *n = bb->dom[dir_index];
1146 : :
1147 : 77165407 : gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1148 : 77165407 : return n->dfs_num_in;
1149 : : }
1150 : :
1151 : : /* Returns the exit dfs number for basic block BB, in the direction DIR. */
1152 : :
1153 : : unsigned
1154 : 44150142 : bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1155 : : {
1156 : 44150142 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1157 : 44150142 : struct et_node *n = bb->dom[dir_index];
1158 : :
1159 : 44150142 : gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1160 : 44150142 : return n->dfs_num_out;
1161 : : }
1162 : :
1163 : : /* Verify invariants of dominator structure. */
1164 : : DEBUG_FUNCTION void
1165 : 755418715 : verify_dominators (cdi_direction dir)
1166 : : {
1167 : 755418715 : gcc_assert (dom_info_available_p (dir));
1168 : :
1169 : 755418715 : dom_info di (cfun, dir);
1170 : 755418715 : di.calc_dfs_tree ();
1171 : 755418715 : di.calc_idoms ();
1172 : :
1173 : 755418715 : bool err = false;
1174 : 755418715 : basic_block bb;
1175 : 8162343429 : FOR_EACH_BB_FN (bb, cfun)
1176 : : {
1177 : 7406924714 : basic_block imm_bb = get_immediate_dominator (dir, bb);
1178 : 7406924714 : if (!imm_bb)
1179 : : {
1180 : 0 : error ("dominator of %d status unknown", bb->index);
1181 : 0 : err = true;
1182 : 0 : continue;
1183 : : }
1184 : :
1185 : 7406924714 : basic_block imm_bb_correct = di.get_idom (bb);
1186 : 7406924714 : if (imm_bb != imm_bb_correct)
1187 : : {
1188 : 0 : error ("dominator of %d should be %d, not %d",
1189 : : bb->index, imm_bb_correct->index, imm_bb->index);
1190 : 0 : err = true;
1191 : : }
1192 : : }
1193 : :
1194 : 755418715 : gcc_assert (!err);
1195 : 755418715 : }
1196 : :
1197 : : /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1198 : : assuming that dominators of other blocks are correct. We also use it to
1199 : : recompute the dominators in a restricted area, by iterating it until it
1200 : : reaches a fixed point. */
1201 : :
1202 : : basic_block
1203 : 665666 : recompute_dominator (enum cdi_direction dir, basic_block bb)
1204 : : {
1205 : 665666 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1206 : 665666 : basic_block dom_bb = NULL;
1207 : 665666 : edge e;
1208 : 665666 : edge_iterator ei;
1209 : :
1210 : 665666 : gcc_checking_assert (dom_computed[dir_index]);
1211 : :
1212 : 665666 : if (dir == CDI_DOMINATORS)
1213 : : {
1214 : 3413040 : FOR_EACH_EDGE (e, ei, bb->preds)
1215 : : {
1216 : 2747374 : if (!dominated_by_p (dir, e->src, bb))
1217 : 2454537 : dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1218 : : }
1219 : : }
1220 : : else
1221 : : {
1222 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1223 : : {
1224 : 0 : if (!dominated_by_p (dir, e->dest, bb))
1225 : 0 : dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1226 : : }
1227 : : }
1228 : :
1229 : 665666 : return dom_bb;
1230 : : }
1231 : :
1232 : : /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1233 : : of BBS. We assume that all the immediate dominators except for those of the
1234 : : blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1235 : : currently recorded immediate dominators of blocks in BBS really dominate the
1236 : : blocks. The basic blocks for that we determine the dominator are removed
1237 : : from BBS. */
1238 : :
1239 : : static void
1240 : 1629987 : prune_bbs_to_update_dominators (vec<basic_block> &bbs,
1241 : : bool conservative)
1242 : : {
1243 : 1629987 : unsigned i;
1244 : 1629987 : bool single;
1245 : 1629987 : basic_block bb, dom = NULL;
1246 : 1629987 : edge_iterator ei;
1247 : 1629987 : edge e;
1248 : :
1249 : 5538826 : for (i = 0; bbs.iterate (i, &bb);)
1250 : : {
1251 : 3908839 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1252 : 0 : goto succeed;
1253 : :
1254 : 3908839 : if (single_pred_p (bb))
1255 : : {
1256 : 1472022 : set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1257 : 1472022 : goto succeed;
1258 : : }
1259 : :
1260 : 2436817 : if (!conservative)
1261 : 1726226 : goto fail;
1262 : :
1263 : 710591 : single = true;
1264 : 710591 : dom = NULL;
1265 : 12912095 : FOR_EACH_EDGE (e, ei, bb->preds)
1266 : : {
1267 : 12201504 : if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1268 : 13274 : continue;
1269 : :
1270 : 12188230 : if (!dom)
1271 : 710591 : dom = e->src;
1272 : : else
1273 : : {
1274 : 11477639 : single = false;
1275 : 11477639 : dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1276 : : }
1277 : : }
1278 : :
1279 : 710591 : gcc_assert (dom != NULL);
1280 : 710591 : if (single
1281 : 710591 : || find_edge (dom, bb))
1282 : : {
1283 : 505862 : set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1284 : 505862 : goto succeed;
1285 : : }
1286 : :
1287 : 1930955 : fail:
1288 : 1930955 : i++;
1289 : 1930955 : continue;
1290 : :
1291 : 1977884 : succeed:
1292 : 1977884 : bbs.unordered_remove (i);
1293 : : }
1294 : 1930955 : }
1295 : :
1296 : : /* Returns root of the dominance tree in the direction DIR that contains
1297 : : BB. */
1298 : :
1299 : : static basic_block
1300 : 8589448 : root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1301 : : {
1302 : 8589448 : return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1303 : : }
1304 : :
1305 : : /* See the comment in iterate_fix_dominators. Finds the immediate dominators
1306 : : for the sons of Y, found using the SON and BROTHER arrays representing
1307 : : the dominance tree of graph G. BBS maps the vertices of G to the basic
1308 : : blocks. */
1309 : :
1310 : : static void
1311 : 2524001 : determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1312 : : int y, int *son, int *brother)
1313 : : {
1314 : 2524001 : bitmap gprime;
1315 : 2524001 : int i, a, nc;
1316 : 2524001 : vec<int> *sccs;
1317 : 2524001 : basic_block bb, dom, ybb;
1318 : 2524001 : unsigned si;
1319 : 2524001 : edge e;
1320 : 2524001 : edge_iterator ei;
1321 : :
1322 : 2524001 : if (son[y] == -1)
1323 : 1872494 : return;
1324 : 2019512 : if (y == (int) bbs.length ())
1325 : 816032 : ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1326 : : else
1327 : 193724 : ybb = bbs[y];
1328 : :
1329 : 1009756 : if (brother[son[y]] == -1)
1330 : : {
1331 : : /* Handle the common case Y has just one son specially. */
1332 : 358249 : bb = bbs[son[y]];
1333 : 358249 : set_immediate_dominator (CDI_DOMINATORS, bb,
1334 : : recompute_dominator (CDI_DOMINATORS, bb));
1335 : 358249 : identify_vertices (g, y, son[y]);
1336 : 358249 : return;
1337 : : }
1338 : :
1339 : 651507 : gprime = BITMAP_ALLOC (NULL);
1340 : 2001227 : for (a = son[y]; a != -1; a = brother[a])
1341 : 1349720 : bitmap_set_bit (gprime, a);
1342 : :
1343 : 651507 : nc = graphds_scc (g, gprime);
1344 : 651507 : BITMAP_FREE (gprime);
1345 : :
1346 : : /* ??? Needed to work around the pre-processor confusion with
1347 : : using a multi-argument template type as macro argument. */
1348 : 651507 : typedef vec<int> vec_int_heap;
1349 : 651507 : sccs = XCNEWVEC (vec_int_heap, nc);
1350 : 2001227 : for (a = son[y]; a != -1; a = brother[a])
1351 : 1349720 : sccs[g->vertices[a].component].safe_push (a);
1352 : :
1353 : 2000586 : for (i = nc - 1; i >= 0; i--)
1354 : : {
1355 : : dom = NULL;
1356 : 2698799 : FOR_EACH_VEC_ELT (sccs[i], si, a)
1357 : : {
1358 : 1349720 : bb = bbs[a];
1359 : 5239094 : FOR_EACH_EDGE (e, ei, bb->preds)
1360 : : {
1361 : 3889374 : if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1362 : 614428 : continue;
1363 : :
1364 : 3274946 : dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1365 : : }
1366 : : }
1367 : :
1368 : 1349079 : gcc_assert (dom != NULL);
1369 : 4047878 : FOR_EACH_VEC_ELT (sccs[i], si, a)
1370 : : {
1371 : 1349720 : bb = bbs[a];
1372 : 1349720 : set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1373 : : }
1374 : : }
1375 : :
1376 : 2000586 : for (i = 0; i < nc; i++)
1377 : 1349079 : sccs[i].release ();
1378 : 651507 : free (sccs);
1379 : :
1380 : 2001227 : for (a = son[y]; a != -1; a = brother[a])
1381 : 1349720 : identify_vertices (g, y, a);
1382 : : }
1383 : :
1384 : : /* Recompute dominance information for basic blocks in the set BBS. The
1385 : : function assumes that the immediate dominators of all the other blocks
1386 : : in CFG are correct, and that there are no unreachable blocks.
1387 : :
1388 : : If CONSERVATIVE is true, we additionally assume that all the ancestors of
1389 : : a block of BBS in the current dominance tree dominate it. */
1390 : :
1391 : : void
1392 : 1629987 : iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> &bbs,
1393 : : bool conservative)
1394 : : {
1395 : 1629987 : unsigned i;
1396 : 1629987 : basic_block bb, dom;
1397 : 1629987 : struct graph *g;
1398 : 1629987 : int n, y;
1399 : 1629987 : size_t dom_i;
1400 : 1629987 : edge e;
1401 : 1629987 : edge_iterator ei;
1402 : 1629987 : int *parent, *son, *brother;
1403 : 1629987 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1404 : :
1405 : : /* We only support updating dominators. There are some problems with
1406 : : updating postdominators (need to add fake edges from infinite loops
1407 : : and noreturn functions), and since we do not currently use
1408 : : iterate_fix_dominators for postdominators, any attempt to handle these
1409 : : problems would be unused, untested, and almost surely buggy. We keep
1410 : : the DIR argument for consistency with the rest of the dominator analysis
1411 : : interface. */
1412 : 1629987 : gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
1413 : :
1414 : : /* The algorithm we use takes inspiration from the following papers, although
1415 : : the details are quite different from any of them:
1416 : :
1417 : : [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1418 : : Dominator Tree of a Reducible Flowgraph
1419 : : [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1420 : : dominator trees
1421 : : [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1422 : : Algorithm
1423 : :
1424 : : First, we use the following heuristics to decrease the size of the BBS
1425 : : set:
1426 : : a) if BB has a single predecessor, then its immediate dominator is this
1427 : : predecessor
1428 : : additionally, if CONSERVATIVE is true:
1429 : : b) if all the predecessors of BB except for one (X) are dominated by BB,
1430 : : then X is the immediate dominator of BB
1431 : : c) if the nearest common ancestor of the predecessors of BB is X and
1432 : : X -> BB is an edge in CFG, then X is the immediate dominator of BB
1433 : :
1434 : : Then, we need to establish the dominance relation among the basic blocks
1435 : : in BBS. We split the dominance tree by removing the immediate dominator
1436 : : edges from BBS, creating a forest F. We form a graph G whose vertices
1437 : : are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1438 : : X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1439 : : whose root is X. We then determine dominance tree of G. Note that
1440 : : for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1441 : : In this step, we can use arbitrary algorithm to determine dominators.
1442 : : We decided to prefer the algorithm [3] to the algorithm of
1443 : : Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1444 : : 10 during gcc bootstrap), and [3] should perform better in this case.
1445 : :
1446 : : Finally, we need to determine the immediate dominators for the basic
1447 : : blocks of BBS. If the immediate dominator of X in G is Y, then
1448 : : the immediate dominator of X in CFG belongs to the tree of F rooted in
1449 : : Y. We process the dominator tree T of G recursively, starting from leaves.
1450 : : Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1451 : : subtrees of the dominance tree of CFG rooted in X_i are already correct.
1452 : : Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1453 : : the following observations:
1454 : : (i) the immediate dominator of all blocks in a strongly connected
1455 : : component of G' is the same
1456 : : (ii) if X has no predecessors in G', then the immediate dominator of X
1457 : : is the nearest common ancestor of the predecessors of X in the
1458 : : subtree of F rooted in Y
1459 : : Therefore, it suffices to find the topological ordering of G', and
1460 : : process the nodes X_i in this order using the rules (i) and (ii).
1461 : : Then, we contract all the nodes X_i with Y in G, so that the further
1462 : : steps work correctly. */
1463 : :
1464 : 1629987 : if (!conservative)
1465 : : {
1466 : : /* Split the tree now. If the idoms of blocks in BBS are not
1467 : : conservatively correct, setting the dominators using the
1468 : : heuristics in prune_bbs_to_update_dominators could
1469 : : create cycles in the dominance "tree", and cause ICE. */
1470 : 3369902 : FOR_EACH_VEC_ELT (bbs, i, bb)
1471 : 2439122 : set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1472 : : }
1473 : :
1474 : 1629987 : prune_bbs_to_update_dominators (bbs, conservative);
1475 : 1629987 : n = bbs.length ();
1476 : :
1477 : 1629987 : if (n == 0)
1478 : 813955 : return;
1479 : :
1480 : 1039018 : if (n == 1)
1481 : : {
1482 : 222986 : bb = bbs[0];
1483 : 222986 : set_immediate_dominator (CDI_DOMINATORS, bb,
1484 : : recompute_dominator (CDI_DOMINATORS, bb));
1485 : 222986 : return;
1486 : : }
1487 : :
1488 : 816032 : timevar_push (TV_DOMINANCE);
1489 : :
1490 : : /* Construct the graph G. */
1491 : 816032 : hash_map<basic_block, int> map (251);
1492 : 3340033 : FOR_EACH_VEC_ELT (bbs, i, bb)
1493 : : {
1494 : : /* If the dominance tree is conservatively correct, split it now. */
1495 : 1707969 : if (conservative)
1496 : 97892 : set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1497 : 1707969 : map.put (bb, i);
1498 : : }
1499 : 816032 : map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
1500 : :
1501 : 816032 : g = new_graph (n + 1);
1502 : 4156065 : for (y = 0; y < g->n_vertices; y++)
1503 : 2524001 : g->vertices[y].data = BITMAP_ALLOC (NULL);
1504 : 2524001 : FOR_EACH_VEC_ELT (bbs, i, bb)
1505 : : {
1506 : 6408043 : FOR_EACH_EDGE (e, ei, bb->preds)
1507 : : {
1508 : 4700074 : dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1509 : 4700074 : if (dom == bb)
1510 : 719250 : continue;
1511 : :
1512 : 3980824 : dom_i = *map.get (dom);
1513 : :
1514 : : /* Do not include parallel edges to G. */
1515 : 3980824 : if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1516 : 1488074 : continue;
1517 : :
1518 : 2492750 : add_edge (g, dom_i, i);
1519 : : }
1520 : : }
1521 : 3340033 : for (y = 0; y < g->n_vertices; y++)
1522 : 2524001 : BITMAP_FREE (g->vertices[y].data);
1523 : :
1524 : : /* Find the dominator tree of G. */
1525 : 816032 : son = XNEWVEC (int, n + 1);
1526 : 816032 : brother = XNEWVEC (int, n + 1);
1527 : 816032 : parent = XNEWVEC (int, n + 1);
1528 : 816032 : graphds_domtree (g, n, parent, son, brother);
1529 : :
1530 : : /* Finally, traverse the tree and find the immediate dominators. */
1531 : 2623907 : for (y = n; son[y] != -1; y = son[y])
1532 : 991843 : continue;
1533 : 3340033 : while (y != -1)
1534 : : {
1535 : 2524001 : determine_dominators_for_sons (g, bbs, y, son, brother);
1536 : :
1537 : 2524001 : if (brother[y] != -1)
1538 : : {
1539 : : y = brother[y];
1540 : 716126 : while (son[y] != -1)
1541 : : y = son[y];
1542 : : }
1543 : : else
1544 : 1825788 : y = parent[y];
1545 : : }
1546 : :
1547 : 816032 : free (son);
1548 : 816032 : free (brother);
1549 : 816032 : free (parent);
1550 : :
1551 : 816032 : free_graph (g);
1552 : :
1553 : 816032 : timevar_pop (TV_DOMINANCE);
1554 : 816032 : }
1555 : :
1556 : : void
1557 : 32736188 : add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1558 : : {
1559 : 32736188 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1560 : :
1561 : 32736188 : gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1562 : :
1563 : 32736188 : n_bbs_in_dom_tree[dir_index]++;
1564 : :
1565 : 32736188 : bb->dom[dir_index] = et_new_tree (bb);
1566 : :
1567 : 32736188 : if (dom_computed[dir_index] == DOM_OK)
1568 : 5003006 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1569 : 32736188 : }
1570 : :
1571 : : void
1572 : 46247562 : delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1573 : : {
1574 : 46247562 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1575 : :
1576 : 46247562 : gcc_checking_assert (dom_computed[dir_index]);
1577 : :
1578 : 46247562 : et_free_tree (bb->dom[dir_index]);
1579 : 46247562 : bb->dom[dir_index] = NULL;
1580 : 46247562 : n_bbs_in_dom_tree[dir_index]--;
1581 : :
1582 : 46247562 : if (dom_computed[dir_index] == DOM_OK)
1583 : 2325674 : dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1584 : 46247562 : }
1585 : :
1586 : : /* Returns the first son of BB in the dominator or postdominator tree
1587 : : as determined by DIR. */
1588 : :
1589 : : basic_block
1590 : 720589465 : first_dom_son (enum cdi_direction dir, basic_block bb)
1591 : : {
1592 : 720589465 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1593 : 720589465 : struct et_node *son = bb->dom[dir_index]->son;
1594 : :
1595 : 720589465 : return (basic_block) (son ? son->data : NULL);
1596 : : }
1597 : :
1598 : : /* Returns the next dominance son after BB in the dominator or postdominator
1599 : : tree as determined by DIR, or NULL if it was the last one. */
1600 : :
1601 : : basic_block
1602 : 632236176 : next_dom_son (enum cdi_direction dir, basic_block bb)
1603 : : {
1604 : 632236176 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1605 : 632236176 : struct et_node *next = bb->dom[dir_index]->right;
1606 : :
1607 : 632236176 : return (basic_block) (next->father->son == next ? NULL : next->data);
1608 : : }
1609 : :
1610 : : /* Return dominance availability for dominance info DIR. */
1611 : :
1612 : : enum dom_state
1613 : 6287427946 : dom_info_state (function *fn, enum cdi_direction dir)
1614 : : {
1615 : 6287427946 : if (!fn->cfg)
1616 : : return DOM_NONE;
1617 : :
1618 : 6140236697 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1619 : 6140236697 : return fn->cfg->x_dom_computed[dir_index];
1620 : : }
1621 : :
1622 : : enum dom_state
1623 : 536763849 : dom_info_state (enum cdi_direction dir)
1624 : : {
1625 : 536763849 : return dom_info_state (cfun, dir);
1626 : : }
1627 : :
1628 : : /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1629 : :
1630 : : void
1631 : 201980929 : set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1632 : : {
1633 : 201980929 : unsigned int dir_index = dom_convert_dir_to_idx (dir);
1634 : :
1635 : 201980929 : dom_computed[dir_index] = new_state;
1636 : 201980929 : }
1637 : :
1638 : : /* Returns true if dominance information for direction DIR is available. */
1639 : :
1640 : : bool
1641 : 2640567415 : dom_info_available_p (function *fn, enum cdi_direction dir)
1642 : : {
1643 : 2640567415 : return dom_info_state (fn, dir) != DOM_NONE;
1644 : : }
1645 : :
1646 : : bool
1647 : 2223179483 : dom_info_available_p (enum cdi_direction dir)
1648 : : {
1649 : 2223179483 : return dom_info_available_p (cfun, dir);
1650 : : }
1651 : :
1652 : : DEBUG_FUNCTION void
1653 : 0 : debug_dominance_info (enum cdi_direction dir)
1654 : : {
1655 : 0 : basic_block bb, bb2;
1656 : 0 : FOR_EACH_BB_FN (bb, cfun)
1657 : 0 : if ((bb2 = get_immediate_dominator (dir, bb)))
1658 : 0 : fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1659 : 0 : }
1660 : :
1661 : : /* Dump the dominance tree in direction DIR to the file F in dot form.
1662 : : This allows easily visualizing the tree using graphviz. */
1663 : :
1664 : : DEBUG_FUNCTION void
1665 : 0 : dot_dominance_tree (FILE *f, enum cdi_direction dir)
1666 : : {
1667 : 0 : fprintf (f, "digraph {\n");
1668 : 0 : basic_block bb, idom;
1669 : 0 : FOR_EACH_BB_FN (bb, cfun)
1670 : 0 : if ((idom = get_immediate_dominator (dir, bb)))
1671 : 0 : fprintf (f, "%i -> %i;\n", idom->index, bb->index);
1672 : 0 : fprintf (f, "}\n");
1673 : 0 : }
1674 : :
1675 : : /* Convenience wrapper around the above that dumps the dominance tree in
1676 : : direction DIR to the file at path FNAME in dot form. */
1677 : :
1678 : : DEBUG_FUNCTION void
1679 : 0 : dot_dominance_tree (const char *fname, enum cdi_direction dir)
1680 : : {
1681 : 0 : FILE *f = fopen (fname, "w");
1682 : 0 : if (f)
1683 : : {
1684 : 0 : dot_dominance_tree (f, dir);
1685 : 0 : fclose (f);
1686 : : }
1687 : : else
1688 : 0 : fprintf (stderr, "failed to open %s: %s\n", fname, xstrerror (errno));
1689 : 0 : }
1690 : :
1691 : : /* Prints to stderr representation of the dominance tree (for direction DIR)
1692 : : rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1693 : : the first line of the output is not indented. */
1694 : :
1695 : : static void
1696 : 0 : debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1697 : : unsigned indent, bool indent_first)
1698 : : {
1699 : 0 : basic_block son;
1700 : 0 : unsigned i;
1701 : 0 : bool first = true;
1702 : :
1703 : 0 : if (indent_first)
1704 : 0 : for (i = 0; i < indent; i++)
1705 : 0 : fprintf (stderr, "\t");
1706 : 0 : fprintf (stderr, "%d\t", root->index);
1707 : :
1708 : 0 : for (son = first_dom_son (dir, root);
1709 : 0 : son;
1710 : 0 : son = next_dom_son (dir, son))
1711 : : {
1712 : 0 : debug_dominance_tree_1 (dir, son, indent + 1, !first);
1713 : 0 : first = false;
1714 : : }
1715 : :
1716 : 0 : if (first)
1717 : 0 : fprintf (stderr, "\n");
1718 : 0 : }
1719 : :
1720 : : /* Prints to stderr representation of the dominance tree (for direction DIR)
1721 : : rooted in ROOT. */
1722 : :
1723 : : DEBUG_FUNCTION void
1724 : 0 : debug_dominance_tree (enum cdi_direction dir, basic_block root)
1725 : : {
1726 : 0 : debug_dominance_tree_1 (dir, root, 0, false);
1727 : 0 : }
|
