1/* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000-2023 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 */
52typedef unsigned int TBB;
53
54namespace {
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
59class dom_info
60{
61public:
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);
69private:
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
142void debug_dominance_info (cdi_direction);
143void 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
150template<typename T>
151inline T *new_zero_array (unsigned num)
152{
153 T *result = new T[num];
154 memset (result, 0, sizeof (T) * num);
155 return result;
156}
157
158/* Helper function for constructors to initialize a part of class members. */
159
160void
161dom_info::dom_init (void)
162{
163 unsigned num = m_n_basic_blocks;
164
165 m_dfs_parent = new_zero_array <TBB> (num);
166 m_dom = new_zero_array <TBB> (num);
167
168 m_path_min = new TBB[num];
169 m_key = new TBB[num];
170 m_set_size = new unsigned int[num];
171 for (unsigned i = 0; i < num; i++)
172 {
173 m_path_min[i] = m_key[i] = i;
174 m_set_size[i] = 1;
175 }
176
177 m_bucket = new_zero_array <TBB> (num);
178 m_next_bucket = new_zero_array <TBB> (num);
179
180 m_set_chain = new_zero_array <TBB> (num);
181 m_set_child = new_zero_array <TBB> (num);
182
183 m_dfs_to_bb = new_zero_array <basic_block> (num);
184
185 m_dfsnum = 1;
186 m_nodes = 0;
187}
188
189/* Allocate all needed memory in a pessimistic fashion (so we round up). */
190
191dom_info::dom_info (function *fn, cdi_direction dir)
192{
193 m_n_basic_blocks = n_basic_blocks_for_fn (fn);
194
195 dom_init ();
196
197 unsigned last_bb_index = last_basic_block_for_fn (fn);
198 m_dfs_order = new_zero_array <TBB> (num: last_bb_index + 1);
199 m_dfs_last = &m_dfs_order[last_bb_index];
200
201 switch (dir)
202 {
203 case CDI_DOMINATORS:
204 m_reverse = false;
205 m_fake_exit_edge = NULL;
206 m_start_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
207 m_end_block = EXIT_BLOCK_PTR_FOR_FN (fn);
208 break;
209 case CDI_POST_DOMINATORS:
210 m_reverse = true;
211 m_fake_exit_edge = BITMAP_ALLOC (NULL);
212 m_start_block = EXIT_BLOCK_PTR_FOR_FN (fn);
213 m_end_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
214 break;
215 default:
216 gcc_unreachable ();
217 }
218}
219
220/* Constructor for reducible region REGION. */
221
222dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
223{
224 m_n_basic_blocks = region.length ();
225 unsigned nm1 = m_n_basic_blocks - 1;
226
227 dom_init ();
228
229 /* Determine max basic block index in region. */
230 int max_index = region[0]->index;
231 for (unsigned i = 1; i <= nm1; i++)
232 if (region[i]->index > max_index)
233 max_index = region[i]->index;
234 max_index += 1; /* set index on the first bb out of region. */
235
236 m_dfs_order = new_zero_array <TBB> (num: max_index + 1);
237 m_dfs_last = &m_dfs_order[max_index];
238
239 m_fake_exit_edge = NULL; /* Assume that region is reducible. */
240
241 switch (dir)
242 {
243 case CDI_DOMINATORS:
244 m_reverse = false;
245 m_start_block = region[0];
246 m_end_block = region[nm1];
247 break;
248 case CDI_POST_DOMINATORS:
249 m_reverse = true;
250 m_start_block = region[nm1];
251 m_end_block = region[0];
252 break;
253 default:
254 gcc_unreachable ();
255 }
256}
257
258inline basic_block
259dom_info::get_idom (basic_block bb)
260{
261 TBB d = m_dom[m_dfs_order[bb->index]];
262 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
270static inline unsigned int
271dom_convert_dir_to_idx (cdi_direction dir)
272{
273 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
274 return dir - 1;
275}
276
277/* Free all allocated memory in dom_info. */
278
279dom_info::~dom_info ()
280{
281 delete[] m_dfs_parent;
282 delete[] m_path_min;
283 delete[] m_key;
284 delete[] m_dom;
285 delete[] m_bucket;
286 delete[] m_next_bucket;
287 delete[] m_set_chain;
288 delete[] m_set_size;
289 delete[] m_set_child;
290 delete[] m_dfs_order;
291 delete[] m_dfs_to_bb;
292 BITMAP_FREE (m_fake_exit_edge);
293}
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
301void
302dom_info::calc_dfs_tree_nonrec (basic_block bb)
303{
304 edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
305 int sp = 0;
306 unsigned d_i = dom_convert_dir_to_idx (dir: m_reverse ? CDI_POST_DOMINATORS
307 : CDI_DOMINATORS);
308
309 /* Initialize the first edge. */
310 edge_iterator ei = m_reverse ? ei_start (bb->preds)
311 : ei_start (bb->succs);
312
313 /* When the stack is empty we break out of this loop. */
314 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 while (!ei_end_p (i: ei))
322 {
323 edge e = ei_edge (i: ei);
324
325 /* Deduce from E the current and the next block (BB and BN), and the
326 next edge. */
327 if (m_reverse)
328 {
329 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 if (bn == m_end_block || bn->dom[d_i] == NULL
335 || m_dfs_order[bn->index])
336 {
337 ei_next (i: &ei);
338 continue;
339 }
340 bb = e->dest;
341 einext = ei_start (bn->preds);
342 }
343 else
344 {
345 bn = e->dest;
346 if (bn == m_end_block || bn->dom[d_i] == NULL
347 || m_dfs_order[bn->index])
348 {
349 ei_next (i: &ei);
350 continue;
351 }
352 bb = e->src;
353 einext = ei_start (bn->succs);
354 }
355
356 gcc_assert (bn != m_start_block);
357
358 /* Fill the DFS tree info calculatable _before_ recursing. */
359 TBB my_i;
360 if (bb != m_start_block)
361 my_i = m_dfs_order[bb->index];
362 else
363 my_i = *m_dfs_last;
364 TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
365 m_dfs_to_bb[child_i] = bn;
366 m_dfs_parent[child_i] = my_i;
367
368 /* Save the current point in the CFG on the stack, and recurse. */
369 stack[sp++] = ei;
370 ei = einext;
371 }
372
373 if (!sp)
374 break;
375 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 ei_next (i: &ei);
387 }
388 delete[] stack;
389}
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
396void
397dom_info::calc_dfs_tree ()
398{
399 *m_dfs_last = m_dfsnum;
400 m_dfs_to_bb[m_dfsnum] = m_start_block;
401 m_dfsnum++;
402
403 calc_dfs_tree_nonrec (bb: m_start_block);
404
405 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 basic_block b;
418 bool saw_unconnected = false;
419
420 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
421 {
422 if (EDGE_COUNT (b->succs) > 0)
423 {
424 if (m_dfs_order[b->index] == 0)
425 saw_unconnected = true;
426 continue;
427 }
428 bitmap_set_bit (m_fake_exit_edge, b->index);
429 m_dfs_order[b->index] = m_dfsnum;
430 m_dfs_to_bb[m_dfsnum] = b;
431 m_dfs_parent[m_dfsnum] = *m_dfs_last;
432 m_dfsnum++;
433 calc_dfs_tree_nonrec (bb: b);
434 }
435
436 if (saw_unconnected)
437 {
438 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
439 {
440 if (m_dfs_order[b->index])
441 continue;
442 basic_block b2 = dfs_find_deadend (b);
443 gcc_checking_assert (m_dfs_order[b2->index] == 0);
444 bitmap_set_bit (m_fake_exit_edge, b2->index);
445 m_dfs_order[b2->index] = m_dfsnum;
446 m_dfs_to_bb[m_dfsnum] = b2;
447 m_dfs_parent[m_dfsnum] = *m_dfs_last;
448 m_dfsnum++;
449 calc_dfs_tree_nonrec (bb: b2);
450 gcc_checking_assert (m_dfs_order[b->index]);
451 }
452 }
453 }
454
455 m_nodes = m_dfsnum - 1;
456
457 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
458 gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1);
459}
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
466void
467dom_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 TBB parent = m_set_chain[v];
473 if (m_set_chain[parent])
474 {
475 compress (v: parent);
476 if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
477 m_path_min[v] = m_path_min[parent];
478 m_set_chain[v] = m_set_chain[parent];
479 }
480}
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
486inline TBB
487dom_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 TBB rep = m_set_chain[v];
492
493 /* V itself is the root. */
494 if (!rep)
495 return m_path_min[v];
496
497 /* Compress only if necessary. */
498 if (m_set_chain[rep])
499 {
500 compress (v);
501 rep = m_set_chain[v];
502 }
503
504 if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
505 return m_path_min[v];
506 else
507 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
515void
516dom_info::link_roots (TBB v, TBB w)
517{
518 TBB s = w;
519
520 /* Rebalance the tree. */
521 while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
522 {
523 if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
524 >= 2 * m_set_size[m_set_child[s]])
525 {
526 m_set_chain[m_set_child[s]] = s;
527 m_set_child[s] = m_set_child[m_set_child[s]];
528 }
529 else
530 {
531 m_set_size[m_set_child[s]] = m_set_size[s];
532 s = m_set_chain[s] = m_set_child[s];
533 }
534 }
535
536 m_path_min[s] = m_path_min[w];
537 m_set_size[v] += m_set_size[w];
538 if (m_set_size[v] < 2 * m_set_size[w])
539 std::swap (a&: m_set_child[v], b&: s);
540
541 /* Merge all subtrees. */
542 while (s)
543 {
544 m_set_chain[s] = v;
545 s = m_set_child[s];
546 }
547}
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
553void
554dom_info::calc_idoms ()
555{
556 /* Go backwards in DFS order, to first look at the leafs. */
557 for (TBB v = m_nodes; v > 1; v--)
558 {
559 basic_block bb = m_dfs_to_bb[v];
560 edge e;
561
562 TBB par = m_dfs_parent[v];
563 TBB k = v;
564
565 edge_iterator ei = m_reverse ? ei_start (bb->succs)
566 : ei_start (bb->preds);
567 edge_iterator einext;
568
569 if (m_fake_exit_edge)
570 {
571 /* If this block has a fake edge to exit, process that first. */
572 if (bitmap_bit_p (m_fake_exit_edge, bb->index))
573 {
574 einext = ei;
575 einext.index = 0;
576 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 while (!ei_end_p (i: ei))
585 {
586 basic_block b;
587 TBB k1;
588
589 e = ei_edge (i: ei);
590 b = m_reverse ? e->dest : e->src;
591 einext = ei;
592 ei_next (i: &einext);
593
594 if (b == m_start_block)
595 {
596 do_fake_exit_edge:
597 k1 = *m_dfs_last;
598 }
599 else
600 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 if (k1 > v)
605 k1 = m_key[eval (v: k1)];
606 if (k1 < k)
607 k = k1;
608
609 ei = einext;
610 }
611
612 m_key[v] = k;
613 link_roots (v: par, w: v);
614 m_next_bucket[v] = m_bucket[k];
615 m_bucket[k] = v;
616
617 /* Transform semidominators into dominators. */
618 for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
619 {
620 k = eval (v: w);
621 if (m_key[k] < m_key[w])
622 m_dom[w] = k;
623 else
624 m_dom[w] = par;
625 }
626 /* We don't need to cleanup next_bucket[]. */
627 m_bucket[par] = 0;
628 }
629
630 /* Explicitly define the dominators. */
631 m_dom[1] = 0;
632 for (TBB v = 2; v <= m_nodes; v++)
633 if (m_dom[v] != m_key[v])
634 m_dom[v] = m_dom[m_dom[v]];
635}
636
637/* Assign dfs numbers starting from NUM to NODE and its sons. */
638
639static void
640assign_dfs_numbers (struct et_node *node, int *num)
641{
642 et_node *n = node;
643 while (1)
644 {
645 n->dfs_num_in = (*num)++;
646 if (n->son)
647 n = n->son;
648 else
649 {
650 while (!n->right || n->right == n->father->son)
651 {
652 n->dfs_num_out = (*num)++;
653 if (n == node)
654 return;
655 n = n->father;
656 }
657 n->dfs_num_out = (*num)++;
658 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
666static void
667compute_dom_fast_query (enum cdi_direction dir)
668{
669 int num = 0;
670 basic_block bb;
671 unsigned int dir_index = dom_convert_dir_to_idx (dir);
672
673 gcc_checking_assert (dom_info_available_p (dir));
674
675 if (dom_computed[dir_index] == DOM_OK)
676 return;
677
678 FOR_ALL_BB_FN (bb, cfun)
679 {
680 if (!bb->dom[dir_index]->father)
681 assign_dfs_numbers (node: bb->dom[dir_index], num: &num);
682 }
683
684 dom_computed[dir_index] = DOM_OK;
685}
686
687/* Analogous to the previous function but compute the data for reducible
688 region REGION. */
689
690static void
691compute_dom_fast_query_in_region (enum cdi_direction dir,
692 vec<basic_block> region)
693{
694 int num = 0;
695 basic_block bb;
696 unsigned int dir_index = dom_convert_dir_to_idx (dir);
697
698 gcc_checking_assert (dom_info_available_p (dir));
699
700 if (dom_computed[dir_index] == DOM_OK)
701 return;
702
703 /* Assign dfs numbers for region nodes except for entry and exit nodes. */
704 for (unsigned int i = 1; i < region.length () - 1; i++)
705 {
706 bb = region[i];
707 if (!bb->dom[dir_index]->father)
708 assign_dfs_numbers (node: bb->dom[dir_index], num: &num);
709 }
710
711 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
719void
720calculate_dominance_info (cdi_direction dir, bool compute_fast_query)
721{
722 unsigned int dir_index = dom_convert_dir_to_idx (dir);
723
724 if (dom_computed[dir_index] == DOM_OK)
725 {
726 checking_verify_dominators (dir);
727 return;
728 }
729
730 timevar_push (tv: TV_DOMINANCE);
731 if (!dom_info_available_p (dir))
732 {
733 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
734
735 basic_block b;
736 FOR_ALL_BB_FN (b, cfun)
737 {
738 b->dom[dir_index] = et_new_tree (data: b);
739 }
740 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
741
742 dom_info di (cfun, dir);
743 di.calc_dfs_tree ();
744 di.calc_idoms ();
745
746 FOR_EACH_BB_FN (b, cfun)
747 {
748 if (basic_block d = di.get_idom (bb: b))
749 et_set_father (b->dom[dir_index], d->dom[dir_index]);
750 }
751
752 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
753 }
754 else
755 checking_verify_dominators (dir);
756
757 if (compute_fast_query)
758 compute_dom_fast_query (dir);
759
760 timevar_pop (tv: 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
767void
768calculate_dominance_info_for_region (cdi_direction dir,
769 vec<basic_block> region)
770{
771 unsigned int dir_index = dom_convert_dir_to_idx (dir);
772 basic_block bb;
773 unsigned int i;
774
775 if (dom_computed[dir_index] == DOM_OK)
776 return;
777
778 timevar_push (tv: TV_DOMINANCE);
779 /* Assume that dom info is not partially computed. */
780 gcc_assert (!dom_info_available_p (dir));
781
782 FOR_EACH_VEC_ELT (region, i, bb)
783 {
784 bb->dom[dir_index] = et_new_tree (data: bb);
785 }
786 dom_info di (region, dir);
787 di.calc_dfs_tree ();
788 di.calc_idoms ();
789
790 FOR_EACH_VEC_ELT (region, i, bb)
791 if (basic_block d = di.get_idom (bb))
792 et_set_father (bb->dom[dir_index], d->dom[dir_index]);
793
794 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
795 compute_dom_fast_query_in_region (dir, region);
796
797 timevar_pop (tv: TV_DOMINANCE);
798}
799
800/* Free dominance information for direction DIR. */
801void
802free_dominance_info (function *fn, enum cdi_direction dir)
803{
804 basic_block bb;
805 unsigned int dir_index = dom_convert_dir_to_idx (dir);
806
807 if (!dom_info_available_p (fn, dir))
808 return;
809
810 FOR_ALL_BB_FN (bb, fn)
811 {
812 et_free_tree_force (bb->dom[dir_index]);
813 bb->dom[dir_index] = NULL;
814 }
815 et_free_pools ();
816
817 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
818
819 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
820}
821
822void
823free_dominance_info (enum cdi_direction dir)
824{
825 free_dominance_info (cfun, dir);
826}
827
828/* Free dominance information for direction DIR in region REGION. */
829
830void
831free_dominance_info_for_region (function *fn,
832 enum cdi_direction dir,
833 vec<basic_block> region)
834{
835 basic_block bb;
836 unsigned int i;
837 unsigned int dir_index = dom_convert_dir_to_idx (dir);
838
839 if (!dom_info_available_p (dir))
840 return;
841
842 FOR_EACH_VEC_ELT (region, i, bb)
843 {
844 et_free_tree_force (bb->dom[dir_index]);
845 bb->dom[dir_index] = NULL;
846 }
847 et_free_pools ();
848
849 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
850
851 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
852}
853
854/* Return the immediate dominator of basic block BB. */
855basic_block
856get_immediate_dominator (enum cdi_direction dir, basic_block bb)
857{
858 unsigned int dir_index = dom_convert_dir_to_idx (dir);
859 struct et_node *node = bb->dom[dir_index];
860
861 gcc_checking_assert (dom_computed[dir_index]);
862
863 if (!node->father)
864 return NULL;
865
866 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. */
871void
872set_immediate_dominator (enum cdi_direction dir, basic_block bb,
873 basic_block dominated_by)
874{
875 unsigned int dir_index = dom_convert_dir_to_idx (dir);
876 struct et_node *node = bb->dom[dir_index];
877
878 gcc_checking_assert (dom_computed[dir_index]);
879
880 if (node->father)
881 {
882 if (node->father->data == dominated_by)
883 return;
884 et_split (node);
885 }
886
887 if (dominated_by)
888 et_set_father (node, dominated_by->dom[dir_index]);
889
890 if (dom_computed[dir_index] == DOM_OK)
891 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. */
896auto_vec<basic_block>
897get_dominated_by (enum cdi_direction dir, basic_block bb)
898{
899 unsigned int dir_index = dom_convert_dir_to_idx (dir);
900 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
901 auto_vec<basic_block> bbs;
902
903 gcc_checking_assert (dom_computed[dir_index]);
904
905 if (!son)
906 return bbs;
907
908 bbs.safe_push (obj: (basic_block) son->data);
909 for (ason = son->right; ason != son; ason = ason->right)
910 bbs.safe_push (obj: (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
919auto_vec<basic_block>
920get_dominated_by_region (enum cdi_direction dir, basic_block *region,
921 unsigned n_region)
922{
923 unsigned i;
924 basic_block dom;
925 auto_vec<basic_block> doms;
926
927 for (i = 0; i < n_region; i++)
928 region[i]->flags |= BB_DUPLICATED;
929 for (i = 0; i < n_region; i++)
930 for (dom = first_dom_son (dir, region[i]);
931 dom;
932 dom = next_dom_son (dir, dom))
933 if (!(dom->flags & BB_DUPLICATED))
934 doms.safe_push (obj: dom);
935 for (i = 0; i < n_region; i++)
936 region[i]->flags &= ~BB_DUPLICATED;
937
938 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
946auto_vec<basic_block>
947get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
948{
949 auto_vec<basic_block> bbs;
950 unsigned i;
951 unsigned next_level_start;
952
953 i = 0;
954 bbs.safe_push (obj: bb);
955 next_level_start = 1; /* = bbs.length (); */
956
957 do
958 {
959 basic_block son;
960
961 bb = bbs[i++];
962 for (son = first_dom_son (dir, bb);
963 son;
964 son = next_dom_son (dir, son))
965 bbs.safe_push (obj: son);
966
967 if (i == next_level_start && --depth)
968 next_level_start = bbs.length ();
969 }
970 while (i < next_level_start);
971
972 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
978auto_vec<basic_block>
979get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
980{
981 return get_dominated_to_depth (dir, bb, depth: 0);
982}
983
984/* Redirect all edges pointing to BB to TO. */
985void
986redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
987 basic_block to)
988{
989 unsigned int dir_index = dom_convert_dir_to_idx (dir);
990 struct et_node *bb_node, *to_node, *son;
991
992 bb_node = bb->dom[dir_index];
993 to_node = to->dom[dir_index];
994
995 gcc_checking_assert (dom_computed[dir_index]);
996
997 if (!bb_node->son)
998 return;
999
1000 while (bb_node->son)
1001 {
1002 son = bb_node->son;
1003
1004 et_split (son);
1005 et_set_father (son, to_node);
1006 }
1007
1008 if (dom_computed[dir_index] == DOM_OK)
1009 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1010}
1011
1012/* Find first basic block in the tree dominating both BB1 and BB2. */
1013basic_block
1014nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1015{
1016 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1017
1018 gcc_checking_assert (dom_computed[dir_index]);
1019
1020 if (!bb1)
1021 return bb2;
1022 if (!bb2)
1023 return bb1;
1024
1025 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
1032basic_block
1033nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1034{
1035 unsigned i, first;
1036 bitmap_iterator bi;
1037 basic_block dom;
1038
1039 first = bitmap_first_set_bit (blocks);
1040 dom = BASIC_BLOCK_FOR_FN (cfun, first);
1041 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
1042 if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
1043 dom = nearest_common_dominator (dir, bb1: dom, BASIC_BLOCK_FOR_FN (cfun, i));
1044
1045 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. */
1124bool
1125dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
1126{
1127 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1128 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
1129
1130 gcc_checking_assert (dom_computed[dir_index]);
1131
1132 if (dom_computed[dir_index] == DOM_OK)
1133 return (n1->dfs_num_in >= n2->dfs_num_in
1134 && n1->dfs_num_out <= n2->dfs_num_out);
1135
1136 return et_below (n1, n2);
1137}
1138
1139/* Returns the entry dfs number for basic block BB, in the direction DIR. */
1140
1141unsigned
1142bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1143{
1144 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1145 struct et_node *n = bb->dom[dir_index];
1146
1147 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1148 return n->dfs_num_in;
1149}
1150
1151/* Returns the exit dfs number for basic block BB, in the direction DIR. */
1152
1153unsigned
1154bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1155{
1156 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1157 struct et_node *n = bb->dom[dir_index];
1158
1159 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1160 return n->dfs_num_out;
1161}
1162
1163/* Verify invariants of dominator structure. */
1164DEBUG_FUNCTION void
1165verify_dominators (cdi_direction dir)
1166{
1167 gcc_assert (dom_info_available_p (dir));
1168
1169 dom_info di (cfun, dir);
1170 di.calc_dfs_tree ();
1171 di.calc_idoms ();
1172
1173 bool err = false;
1174 basic_block bb;
1175 FOR_EACH_BB_FN (bb, cfun)
1176 {
1177 basic_block imm_bb = get_immediate_dominator (dir, bb);
1178 if (!imm_bb)
1179 {
1180 error ("dominator of %d status unknown", bb->index);
1181 err = true;
1182 continue;
1183 }
1184
1185 basic_block imm_bb_correct = di.get_idom (bb);
1186 if (imm_bb != imm_bb_correct)
1187 {
1188 error ("dominator of %d should be %d, not %d",
1189 bb->index, imm_bb_correct->index, imm_bb->index);
1190 err = true;
1191 }
1192 }
1193
1194 gcc_assert (!err);
1195}
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
1202basic_block
1203recompute_dominator (enum cdi_direction dir, basic_block bb)
1204{
1205 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1206 basic_block dom_bb = NULL;
1207 edge e;
1208 edge_iterator ei;
1209
1210 gcc_checking_assert (dom_computed[dir_index]);
1211
1212 if (dir == CDI_DOMINATORS)
1213 {
1214 FOR_EACH_EDGE (e, ei, bb->preds)
1215 {
1216 if (!dominated_by_p (dir, bb1: e->src, bb2: bb))
1217 dom_bb = nearest_common_dominator (dir, bb1: dom_bb, bb2: e->src);
1218 }
1219 }
1220 else
1221 {
1222 FOR_EACH_EDGE (e, ei, bb->succs)
1223 {
1224 if (!dominated_by_p (dir, bb1: e->dest, bb2: bb))
1225 dom_bb = nearest_common_dominator (dir, bb1: dom_bb, bb2: e->dest);
1226 }
1227 }
1228
1229 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
1239static void
1240prune_bbs_to_update_dominators (vec<basic_block> &bbs,
1241 bool conservative)
1242{
1243 unsigned i;
1244 bool single;
1245 basic_block bb, dom = NULL;
1246 edge_iterator ei;
1247 edge e;
1248
1249 for (i = 0; bbs.iterate (ix: i, ptr: &bb);)
1250 {
1251 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1252 goto succeed;
1253
1254 if (single_pred_p (bb))
1255 {
1256 set_immediate_dominator (dir: CDI_DOMINATORS, bb, dominated_by: single_pred (bb));
1257 goto succeed;
1258 }
1259
1260 if (!conservative)
1261 goto fail;
1262
1263 single = true;
1264 dom = NULL;
1265 FOR_EACH_EDGE (e, ei, bb->preds)
1266 {
1267 if (dominated_by_p (dir: CDI_DOMINATORS, bb1: e->src, bb2: bb))
1268 continue;
1269
1270 if (!dom)
1271 dom = e->src;
1272 else
1273 {
1274 single = false;
1275 dom = nearest_common_dominator (dir: CDI_DOMINATORS, bb1: dom, bb2: e->src);
1276 }
1277 }
1278
1279 gcc_assert (dom != NULL);
1280 if (single
1281 || find_edge (dom, bb))
1282 {
1283 set_immediate_dominator (dir: CDI_DOMINATORS, bb, dominated_by: dom);
1284 goto succeed;
1285 }
1286
1287fail:
1288 i++;
1289 continue;
1290
1291succeed:
1292 bbs.unordered_remove (ix: i);
1293 }
1294}
1295
1296/* Returns root of the dominance tree in the direction DIR that contains
1297 BB. */
1298
1299static basic_block
1300root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1301{
1302 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
1310static void
1311determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1312 int y, int *son, int *brother)
1313{
1314 bitmap gprime;
1315 int i, a, nc;
1316 vec<int> *sccs;
1317 basic_block bb, dom, ybb;
1318 unsigned si;
1319 edge e;
1320 edge_iterator ei;
1321
1322 if (son[y] == -1)
1323 return;
1324 if (y == (int) bbs.length ())
1325 ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1326 else
1327 ybb = bbs[y];
1328
1329 if (brother[son[y]] == -1)
1330 {
1331 /* Handle the common case Y has just one son specially. */
1332 bb = bbs[son[y]];
1333 set_immediate_dominator (dir: CDI_DOMINATORS, bb,
1334 dominated_by: recompute_dominator (dir: CDI_DOMINATORS, bb));
1335 identify_vertices (g, y, son[y]);
1336 return;
1337 }
1338
1339 gprime = BITMAP_ALLOC (NULL);
1340 for (a = son[y]; a != -1; a = brother[a])
1341 bitmap_set_bit (gprime, a);
1342
1343 nc = graphds_scc (g, gprime);
1344 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 typedef vec<int> vec_int_heap;
1349 sccs = XCNEWVEC (vec_int_heap, nc);
1350 for (a = son[y]; a != -1; a = brother[a])
1351 sccs[g->vertices[a].component].safe_push (obj: a);
1352
1353 for (i = nc - 1; i >= 0; i--)
1354 {
1355 dom = NULL;
1356 FOR_EACH_VEC_ELT (sccs[i], si, a)
1357 {
1358 bb = bbs[a];
1359 FOR_EACH_EDGE (e, ei, bb->preds)
1360 {
1361 if (root_of_dom_tree (dir: CDI_DOMINATORS, bb: e->src) != ybb)
1362 continue;
1363
1364 dom = nearest_common_dominator (dir: CDI_DOMINATORS, bb1: dom, bb2: e->src);
1365 }
1366 }
1367
1368 gcc_assert (dom != NULL);
1369 FOR_EACH_VEC_ELT (sccs[i], si, a)
1370 {
1371 bb = bbs[a];
1372 set_immediate_dominator (dir: CDI_DOMINATORS, bb, dominated_by: dom);
1373 }
1374 }
1375
1376 for (i = 0; i < nc; i++)
1377 sccs[i].release ();
1378 free (ptr: sccs);
1379
1380 for (a = son[y]; a != -1; a = brother[a])
1381 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
1391void
1392iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> &bbs,
1393 bool conservative)
1394{
1395 unsigned i;
1396 basic_block bb, dom;
1397 struct graph *g;
1398 int n, y;
1399 size_t dom_i;
1400 edge e;
1401 edge_iterator ei;
1402 int *parent, *son, *brother;
1403 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 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 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 FOR_EACH_VEC_ELT (bbs, i, bb)
1471 set_immediate_dominator (dir: CDI_DOMINATORS, bb, NULL);
1472 }
1473
1474 prune_bbs_to_update_dominators (bbs, conservative);
1475 n = bbs.length ();
1476
1477 if (n == 0)
1478 return;
1479
1480 if (n == 1)
1481 {
1482 bb = bbs[0];
1483 set_immediate_dominator (dir: CDI_DOMINATORS, bb,
1484 dominated_by: recompute_dominator (dir: CDI_DOMINATORS, bb));
1485 return;
1486 }
1487
1488 timevar_push (tv: TV_DOMINANCE);
1489
1490 /* Construct the graph G. */
1491 hash_map<basic_block, int> map (251);
1492 FOR_EACH_VEC_ELT (bbs, i, bb)
1493 {
1494 /* If the dominance tree is conservatively correct, split it now. */
1495 if (conservative)
1496 set_immediate_dominator (dir: CDI_DOMINATORS, bb, NULL);
1497 map.put (k: bb, v: i);
1498 }
1499 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), v: n);
1500
1501 g = new_graph (n + 1);
1502 for (y = 0; y < g->n_vertices; y++)
1503 g->vertices[y].data = BITMAP_ALLOC (NULL);
1504 FOR_EACH_VEC_ELT (bbs, i, bb)
1505 {
1506 FOR_EACH_EDGE (e, ei, bb->preds)
1507 {
1508 dom = root_of_dom_tree (dir: CDI_DOMINATORS, bb: e->src);
1509 if (dom == bb)
1510 continue;
1511
1512 dom_i = *map.get (k: dom);
1513
1514 /* Do not include parallel edges to G. */
1515 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1516 continue;
1517
1518 add_edge (g, dom_i, i);
1519 }
1520 }
1521 for (y = 0; y < g->n_vertices; y++)
1522 BITMAP_FREE (g->vertices[y].data);
1523
1524 /* Find the dominator tree of G. */
1525 son = XNEWVEC (int, n + 1);
1526 brother = XNEWVEC (int, n + 1);
1527 parent = XNEWVEC (int, n + 1);
1528 graphds_domtree (g, n, parent, son, brother);
1529
1530 /* Finally, traverse the tree and find the immediate dominators. */
1531 for (y = n; son[y] != -1; y = son[y])
1532 continue;
1533 while (y != -1)
1534 {
1535 determine_dominators_for_sons (g, bbs, y, son, brother);
1536
1537 if (brother[y] != -1)
1538 {
1539 y = brother[y];
1540 while (son[y] != -1)
1541 y = son[y];
1542 }
1543 else
1544 y = parent[y];
1545 }
1546
1547 free (ptr: son);
1548 free (ptr: brother);
1549 free (ptr: parent);
1550
1551 free_graph (g);
1552
1553 timevar_pop (tv: TV_DOMINANCE);
1554}
1555
1556void
1557add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1558{
1559 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1560
1561 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1562
1563 n_bbs_in_dom_tree[dir_index]++;
1564
1565 bb->dom[dir_index] = et_new_tree (data: bb);
1566
1567 if (dom_computed[dir_index] == DOM_OK)
1568 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1569}
1570
1571void
1572delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1573{
1574 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1575
1576 gcc_checking_assert (dom_computed[dir_index]);
1577
1578 et_free_tree (bb->dom[dir_index]);
1579 bb->dom[dir_index] = NULL;
1580 n_bbs_in_dom_tree[dir_index]--;
1581
1582 if (dom_computed[dir_index] == DOM_OK)
1583 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1584}
1585
1586/* Returns the first son of BB in the dominator or postdominator tree
1587 as determined by DIR. */
1588
1589basic_block
1590first_dom_son (enum cdi_direction dir, basic_block bb)
1591{
1592 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1593 struct et_node *son = bb->dom[dir_index]->son;
1594
1595 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
1601basic_block
1602next_dom_son (enum cdi_direction dir, basic_block bb)
1603{
1604 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1605 struct et_node *next = bb->dom[dir_index]->right;
1606
1607 return (basic_block) (next->father->son == next ? NULL : next->data);
1608}
1609
1610/* Return dominance availability for dominance info DIR. */
1611
1612enum dom_state
1613dom_info_state (function *fn, enum cdi_direction dir)
1614{
1615 if (!fn->cfg)
1616 return DOM_NONE;
1617
1618 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1619 return fn->cfg->x_dom_computed[dir_index];
1620}
1621
1622enum dom_state
1623dom_info_state (enum cdi_direction dir)
1624{
1625 return dom_info_state (cfun, dir);
1626}
1627
1628/* Set the dominance availability for dominance info DIR to NEW_STATE. */
1629
1630void
1631set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1632{
1633 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1634
1635 dom_computed[dir_index] = new_state;
1636}
1637
1638/* Returns true if dominance information for direction DIR is available. */
1639
1640bool
1641dom_info_available_p (function *fn, enum cdi_direction dir)
1642{
1643 return dom_info_state (fn, dir) != DOM_NONE;
1644}
1645
1646bool
1647dom_info_available_p (enum cdi_direction dir)
1648{
1649 return dom_info_available_p (cfun, dir);
1650}
1651
1652DEBUG_FUNCTION void
1653debug_dominance_info (enum cdi_direction dir)
1654{
1655 basic_block bb, bb2;
1656 FOR_EACH_BB_FN (bb, cfun)
1657 if ((bb2 = get_immediate_dominator (dir, bb)))
1658 fprintf (stderr, format: "%i %i\n", bb->index, bb2->index);
1659}
1660
1661/* Prints to stderr representation of the dominance tree (for direction DIR)
1662 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1663 the first line of the output is not indented. */
1664
1665static void
1666debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1667 unsigned indent, bool indent_first)
1668{
1669 basic_block son;
1670 unsigned i;
1671 bool first = true;
1672
1673 if (indent_first)
1674 for (i = 0; i < indent; i++)
1675 fprintf (stderr, format: "\t");
1676 fprintf (stderr, format: "%d\t", root->index);
1677
1678 for (son = first_dom_son (dir, bb: root);
1679 son;
1680 son = next_dom_son (dir, bb: son))
1681 {
1682 debug_dominance_tree_1 (dir, root: son, indent: indent + 1, indent_first: !first);
1683 first = false;
1684 }
1685
1686 if (first)
1687 fprintf (stderr, format: "\n");
1688}
1689
1690/* Prints to stderr representation of the dominance tree (for direction DIR)
1691 rooted in ROOT. */
1692
1693DEBUG_FUNCTION void
1694debug_dominance_tree (enum cdi_direction dir, basic_block root)
1695{
1696 debug_dominance_tree_1 (dir, root, indent: 0, indent_first: false);
1697}
1698

source code of gcc/dominance.cc