1/* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000-2017 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> (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> (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 (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 (ei))
322 {
323 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 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 (&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 (&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 (&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 (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 (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 (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 (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 (m_set_child[v], 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 (ei))
585 {
586 basic_block b;
587 TBB k1;
588
589 e = ei_edge (ei);
590 b = m_reverse ? e->dest : e->src;
591 einext = ei;
592 ei_next (&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 (k1)];
606 if (k1 < k)
607 k = k1;
608
609 ei = einext;
610 }
611
612 m_key[v] = k;
613 link_roots (par, 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 (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 struct et_node *son;
643
644 node->dfs_num_in = (*num)++;
645
646 if (node->son)
647 {
648 assign_dfs_numbers (node->son, num);
649 for (son = node->son->right; son != node->son; son = son->right)
650 assign_dfs_numbers (son, num);
651 }
652
653 node->dfs_num_out = (*num)++;
654}
655
656/* Compute the data necessary for fast resolving of dominator queries in a
657 static dominator tree. */
658
659static void
660compute_dom_fast_query (enum cdi_direction dir)
661{
662 int num = 0;
663 basic_block bb;
664 unsigned int dir_index = dom_convert_dir_to_idx (dir);
665
666 gcc_checking_assert (dom_info_available_p (dir));
667
668 if (dom_computed[dir_index] == DOM_OK)
669 return;
670
671 FOR_ALL_BB_FN (bb, cfun)
672 {
673 if (!bb->dom[dir_index]->father)
674 assign_dfs_numbers (bb->dom[dir_index], &num);
675 }
676
677 dom_computed[dir_index] = DOM_OK;
678}
679
680/* Analogous to the previous function but compute the data for reducible
681 region REGION. */
682
683static void
684compute_dom_fast_query_in_region (enum cdi_direction dir,
685 vec<basic_block> region)
686{
687 int num = 0;
688 basic_block bb;
689 unsigned int dir_index = dom_convert_dir_to_idx (dir);
690
691 gcc_checking_assert (dom_info_available_p (dir));
692
693 if (dom_computed[dir_index] == DOM_OK)
694 return;
695
696 /* Assign dfs numbers for region nodes except for entry and exit nodes. */
697 for (unsigned int i = 1; i < region.length () - 1; i++)
698 {
699 bb = region[i];
700 if (!bb->dom[dir_index]->father)
701 assign_dfs_numbers (bb->dom[dir_index], &num);
702 }
703
704 dom_computed[dir_index] = DOM_OK;
705}
706
707/* The main entry point into this module. DIR is set depending on whether
708 we want to compute dominators or postdominators. */
709
710void
711calculate_dominance_info (cdi_direction dir)
712{
713 unsigned int dir_index = dom_convert_dir_to_idx (dir);
714
715 if (dom_computed[dir_index] == DOM_OK)
716 {
717 checking_verify_dominators (dir);
718 return;
719 }
720
721 timevar_push (TV_DOMINANCE);
722 if (!dom_info_available_p (dir))
723 {
724 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
725
726 basic_block b;
727 FOR_ALL_BB_FN (b, cfun)
728 {
729 b->dom[dir_index] = et_new_tree (b);
730 }
731 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
732
733 dom_info di (cfun, dir);
734 di.calc_dfs_tree ();
735 di.calc_idoms ();
736
737 FOR_EACH_BB_FN (b, cfun)
738 {
739 if (basic_block d = di.get_idom (b))
740 et_set_father (b->dom[dir_index], d->dom[dir_index]);
741 }
742
743 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
744 }
745 else
746 checking_verify_dominators (dir);
747
748 compute_dom_fast_query (dir);
749
750 timevar_pop (TV_DOMINANCE);
751}
752
753/* Analogous to the previous function but compute dominance info for regions
754 which are single entry, multiple exit regions for CDI_DOMINATORs and
755 multiple entry, single exit regions for CDI_POST_DOMINATORs. */
756
757void
758calculate_dominance_info_for_region (cdi_direction dir,
759 vec<basic_block> region)
760{
761 unsigned int dir_index = dom_convert_dir_to_idx (dir);
762 basic_block bb;
763 unsigned int i;
764
765 if (dom_computed[dir_index] == DOM_OK)
766 return;
767
768 timevar_push (TV_DOMINANCE);
769 /* Assume that dom info is not partially computed. */
770 gcc_assert (!dom_info_available_p (dir));
771
772 FOR_EACH_VEC_ELT (region, i, bb)
773 {
774 bb->dom[dir_index] = et_new_tree (bb);
775 }
776 dom_info di (region, dir);
777 di.calc_dfs_tree ();
778 di.calc_idoms ();
779
780 FOR_EACH_VEC_ELT (region, i, bb)
781 if (basic_block d = di.get_idom (bb))
782 et_set_father (bb->dom[dir_index], d->dom[dir_index]);
783
784 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
785 compute_dom_fast_query_in_region (dir, region);
786
787 timevar_pop (TV_DOMINANCE);
788}
789
790/* Free dominance information for direction DIR. */
791void
792free_dominance_info (function *fn, enum cdi_direction dir)
793{
794 basic_block bb;
795 unsigned int dir_index = dom_convert_dir_to_idx (dir);
796
797 if (!dom_info_available_p (fn, dir))
798 return;
799
800 FOR_ALL_BB_FN (bb, fn)
801 {
802 et_free_tree_force (bb->dom[dir_index]);
803 bb->dom[dir_index] = NULL;
804 }
805 et_free_pools ();
806
807 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
808
809 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
810}
811
812void
813free_dominance_info (enum cdi_direction dir)
814{
815 free_dominance_info (cfun, dir);
816}
817
818/* Free dominance information for direction DIR in region REGION. */
819
820void
821free_dominance_info_for_region (function *fn,
822 enum cdi_direction dir,
823 vec<basic_block> region)
824{
825 basic_block bb;
826 unsigned int i;
827 unsigned int dir_index = dom_convert_dir_to_idx (dir);
828
829 if (!dom_info_available_p (dir))
830 return;
831
832 FOR_EACH_VEC_ELT (region, i, bb)
833 {
834 et_free_tree_force (bb->dom[dir_index]);
835 bb->dom[dir_index] = NULL;
836 }
837 et_free_pools ();
838
839 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
840
841 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
842}
843
844/* Return the immediate dominator of basic block BB. */
845basic_block
846get_immediate_dominator (enum cdi_direction dir, basic_block bb)
847{
848 unsigned int dir_index = dom_convert_dir_to_idx (dir);
849 struct et_node *node = bb->dom[dir_index];
850
851 gcc_checking_assert (dom_computed[dir_index]);
852
853 if (!node->father)
854 return NULL;
855
856 return (basic_block) node->father->data;
857}
858
859/* Set the immediate dominator of the block possibly removing
860 existing edge. NULL can be used to remove any edge. */
861void
862set_immediate_dominator (enum cdi_direction dir, basic_block bb,
863 basic_block dominated_by)
864{
865 unsigned int dir_index = dom_convert_dir_to_idx (dir);
866 struct et_node *node = bb->dom[dir_index];
867
868 gcc_checking_assert (dom_computed[dir_index]);
869
870 if (node->father)
871 {
872 if (node->father->data == dominated_by)
873 return;
874 et_split (node);
875 }
876
877 if (dominated_by)
878 et_set_father (node, dominated_by->dom[dir_index]);
879
880 if (dom_computed[dir_index] == DOM_OK)
881 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
882}
883
884/* Returns the list of basic blocks immediately dominated by BB, in the
885 direction DIR. */
886vec<basic_block>
887get_dominated_by (enum cdi_direction dir, basic_block bb)
888{
889 unsigned int dir_index = dom_convert_dir_to_idx (dir);
890 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
891 vec<basic_block> bbs = vNULL;
892
893 gcc_checking_assert (dom_computed[dir_index]);
894
895 if (!son)
896 return vNULL;
897
898 bbs.safe_push ((basic_block) son->data);
899 for (ason = son->right; ason != son; ason = ason->right)
900 bbs.safe_push ((basic_block) ason->data);
901
902 return bbs;
903}
904
905/* Returns the list of basic blocks that are immediately dominated (in
906 direction DIR) by some block between N_REGION ones stored in REGION,
907 except for blocks in the REGION itself. */
908
909vec<basic_block>
910get_dominated_by_region (enum cdi_direction dir, basic_block *region,
911 unsigned n_region)
912{
913 unsigned i;
914 basic_block dom;
915 vec<basic_block> doms = vNULL;
916
917 for (i = 0; i < n_region; i++)
918 region[i]->flags |= BB_DUPLICATED;
919 for (i = 0; i < n_region; i++)
920 for (dom = first_dom_son (dir, region[i]);
921 dom;
922 dom = next_dom_son (dir, dom))
923 if (!(dom->flags & BB_DUPLICATED))
924 doms.safe_push (dom);
925 for (i = 0; i < n_region; i++)
926 region[i]->flags &= ~BB_DUPLICATED;
927
928 return doms;
929}
930
931/* Returns the list of basic blocks including BB dominated by BB, in the
932 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
933 produce a vector containing all dominated blocks. The vector will be sorted
934 in preorder. */
935
936vec<basic_block>
937get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
938{
939 vec<basic_block> bbs = vNULL;
940 unsigned i;
941 unsigned next_level_start;
942
943 i = 0;
944 bbs.safe_push (bb);
945 next_level_start = 1; /* = bbs.length (); */
946
947 do
948 {
949 basic_block son;
950
951 bb = bbs[i++];
952 for (son = first_dom_son (dir, bb);
953 son;
954 son = next_dom_son (dir, son))
955 bbs.safe_push (son);
956
957 if (i == next_level_start && --depth)
958 next_level_start = bbs.length ();
959 }
960 while (i < next_level_start);
961
962 return bbs;
963}
964
965/* Returns the list of basic blocks including BB dominated by BB, in the
966 direction DIR. The vector will be sorted in preorder. */
967
968vec<basic_block>
969get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
970{
971 return get_dominated_to_depth (dir, bb, 0);
972}
973
974/* Redirect all edges pointing to BB to TO. */
975void
976redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
977 basic_block to)
978{
979 unsigned int dir_index = dom_convert_dir_to_idx (dir);
980 struct et_node *bb_node, *to_node, *son;
981
982 bb_node = bb->dom[dir_index];
983 to_node = to->dom[dir_index];
984
985 gcc_checking_assert (dom_computed[dir_index]);
986
987 if (!bb_node->son)
988 return;
989
990 while (bb_node->son)
991 {
992 son = bb_node->son;
993
994 et_split (son);
995 et_set_father (son, to_node);
996 }
997
998 if (dom_computed[dir_index] == DOM_OK)
999 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1000}
1001
1002/* Find first basic block in the tree dominating both BB1 and BB2. */
1003basic_block
1004nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1005{
1006 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1007
1008 gcc_checking_assert (dom_computed[dir_index]);
1009
1010 if (!bb1)
1011 return bb2;
1012 if (!bb2)
1013 return bb1;
1014
1015 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
1016}
1017
1018
1019/* Find the nearest common dominator for the basic blocks in BLOCKS,
1020 using dominance direction DIR. */
1021
1022basic_block
1023nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1024{
1025 unsigned i, first;
1026 bitmap_iterator bi;
1027 basic_block dom;
1028
1029 first = bitmap_first_set_bit (blocks);
1030 dom = BASIC_BLOCK_FOR_FN (cfun, first);
1031 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
1032 if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
1033 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
1034
1035 return dom;
1036}
1037
1038/* Given a dominator tree, we can determine whether one thing
1039 dominates another in constant time by using two DFS numbers:
1040
1041 1. The number for when we visit a node on the way down the tree
1042 2. The number for when we visit a node on the way back up the tree
1043
1044 You can view these as bounds for the range of dfs numbers the
1045 nodes in the subtree of the dominator tree rooted at that node
1046 will contain.
1047
1048 The dominator tree is always a simple acyclic tree, so there are
1049 only three possible relations two nodes in the dominator tree have
1050 to each other:
1051
1052 1. Node A is above Node B (and thus, Node A dominates node B)
1053
1054 A
1055 |
1056 C
1057 / \
1058 B D
1059
1060
1061 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
1062 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
1063 because we must hit A in the dominator tree *before* B on the walk
1064 down, and we will hit A *after* B on the walk back up
1065
1066 2. Node A is below node B (and thus, node B dominates node A)
1067
1068
1069 B
1070 |
1071 A
1072 / \
1073 C D
1074
1075 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
1076 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
1077
1078 This is because we must hit A in the dominator tree *after* B on
1079 the walk down, and we will hit A *before* B on the walk back up
1080
1081 3. Node A and B are siblings (and thus, neither dominates the other)
1082
1083 C
1084 |
1085 D
1086 / \
1087 A B
1088
1089 In the above case, DFS_Number_In of A will *always* be <=
1090 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
1091 DFS_Number_Out of B. This is because we will always finish the dfs
1092 walk of one of the subtrees before the other, and thus, the dfs
1093 numbers for one subtree can't intersect with the range of dfs
1094 numbers for the other subtree. If you swap A and B's position in
1095 the dominator tree, the comparison changes direction, but the point
1096 is that both comparisons will always go the same way if there is no
1097 dominance relationship.
1098
1099 Thus, it is sufficient to write
1100
1101 A_Dominates_B (node A, node B)
1102 {
1103 return DFS_Number_In(A) <= DFS_Number_In(B)
1104 && DFS_Number_Out (A) >= DFS_Number_Out(B);
1105 }
1106
1107 A_Dominated_by_B (node A, node B)
1108 {
1109 return DFS_Number_In(A) >= DFS_Number_In(B)
1110 && DFS_Number_Out (A) <= DFS_Number_Out(B);
1111 } */
1112
1113/* Return TRUE in case BB1 is dominated by BB2. */
1114bool
1115dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
1116{
1117 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1118 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
1119
1120 gcc_checking_assert (dom_computed[dir_index]);
1121
1122 if (dom_computed[dir_index] == DOM_OK)
1123 return (n1->dfs_num_in >= n2->dfs_num_in
1124 && n1->dfs_num_out <= n2->dfs_num_out);
1125
1126 return et_below (n1, n2);
1127}
1128
1129/* Returns the entry dfs number for basic block BB, in the direction DIR. */
1130
1131unsigned
1132bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1133{
1134 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1135 struct et_node *n = bb->dom[dir_index];
1136
1137 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1138 return n->dfs_num_in;
1139}
1140
1141/* Returns the exit dfs number for basic block BB, in the direction DIR. */
1142
1143unsigned
1144bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1145{
1146 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1147 struct et_node *n = bb->dom[dir_index];
1148
1149 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1150 return n->dfs_num_out;
1151}
1152
1153/* Verify invariants of dominator structure. */
1154DEBUG_FUNCTION void
1155verify_dominators (cdi_direction dir)
1156{
1157 gcc_assert (dom_info_available_p (dir));
1158
1159 dom_info di (cfun, dir);
1160 di.calc_dfs_tree ();
1161 di.calc_idoms ();
1162
1163 bool err = false;
1164 basic_block bb;
1165 FOR_EACH_BB_FN (bb, cfun)
1166 {
1167 basic_block imm_bb = get_immediate_dominator (dir, bb);
1168 if (!imm_bb)
1169 {
1170 error ("dominator of %d status unknown", bb->index);
1171 err = true;
1172 continue;
1173 }
1174
1175 basic_block imm_bb_correct = di.get_idom (bb);
1176 if (imm_bb != imm_bb_correct)
1177 {
1178 error ("dominator of %d should be %d, not %d",
1179 bb->index, imm_bb_correct->index, imm_bb->index);
1180 err = true;
1181 }
1182 }
1183
1184 gcc_assert (!err);
1185}
1186
1187/* Determine immediate dominator (or postdominator, according to DIR) of BB,
1188 assuming that dominators of other blocks are correct. We also use it to
1189 recompute the dominators in a restricted area, by iterating it until it
1190 reaches a fixed point. */
1191
1192basic_block
1193recompute_dominator (enum cdi_direction dir, basic_block bb)
1194{
1195 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1196 basic_block dom_bb = NULL;
1197 edge e;
1198 edge_iterator ei;
1199
1200 gcc_checking_assert (dom_computed[dir_index]);
1201
1202 if (dir == CDI_DOMINATORS)
1203 {
1204 FOR_EACH_EDGE (e, ei, bb->preds)
1205 {
1206 if (!dominated_by_p (dir, e->src, bb))
1207 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1208 }
1209 }
1210 else
1211 {
1212 FOR_EACH_EDGE (e, ei, bb->succs)
1213 {
1214 if (!dominated_by_p (dir, e->dest, bb))
1215 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1216 }
1217 }
1218
1219 return dom_bb;
1220}
1221
1222/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1223 of BBS. We assume that all the immediate dominators except for those of the
1224 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1225 currently recorded immediate dominators of blocks in BBS really dominate the
1226 blocks. The basic blocks for that we determine the dominator are removed
1227 from BBS. */
1228
1229static void
1230prune_bbs_to_update_dominators (vec<basic_block> bbs,
1231 bool conservative)
1232{
1233 unsigned i;
1234 bool single;
1235 basic_block bb, dom = NULL;
1236 edge_iterator ei;
1237 edge e;
1238
1239 for (i = 0; bbs.iterate (i, &bb);)
1240 {
1241 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1242 goto succeed;
1243
1244 if (single_pred_p (bb))
1245 {
1246 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1247 goto succeed;
1248 }
1249
1250 if (!conservative)
1251 goto fail;
1252
1253 single = true;
1254 dom = NULL;
1255 FOR_EACH_EDGE (e, ei, bb->preds)
1256 {
1257 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1258 continue;
1259
1260 if (!dom)
1261 dom = e->src;
1262 else
1263 {
1264 single = false;
1265 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1266 }
1267 }
1268
1269 gcc_assert (dom != NULL);
1270 if (single
1271 || find_edge (dom, bb))
1272 {
1273 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1274 goto succeed;
1275 }
1276
1277fail:
1278 i++;
1279 continue;
1280
1281succeed:
1282 bbs.unordered_remove (i);
1283 }
1284}
1285
1286/* Returns root of the dominance tree in the direction DIR that contains
1287 BB. */
1288
1289static basic_block
1290root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1291{
1292 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1293}
1294
1295/* See the comment in iterate_fix_dominators. Finds the immediate dominators
1296 for the sons of Y, found using the SON and BROTHER arrays representing
1297 the dominance tree of graph G. BBS maps the vertices of G to the basic
1298 blocks. */
1299
1300static void
1301determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1302 int y, int *son, int *brother)
1303{
1304 bitmap gprime;
1305 int i, a, nc;
1306 vec<int> *sccs;
1307 basic_block bb, dom, ybb;
1308 unsigned si;
1309 edge e;
1310 edge_iterator ei;
1311
1312 if (son[y] == -1)
1313 return;
1314 if (y == (int) bbs.length ())
1315 ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1316 else
1317 ybb = bbs[y];
1318
1319 if (brother[son[y]] == -1)
1320 {
1321 /* Handle the common case Y has just one son specially. */
1322 bb = bbs[son[y]];
1323 set_immediate_dominator (CDI_DOMINATORS, bb,
1324 recompute_dominator (CDI_DOMINATORS, bb));
1325 identify_vertices (g, y, son[y]);
1326 return;
1327 }
1328
1329 gprime = BITMAP_ALLOC (NULL);
1330 for (a = son[y]; a != -1; a = brother[a])
1331 bitmap_set_bit (gprime, a);
1332
1333 nc = graphds_scc (g, gprime);
1334 BITMAP_FREE (gprime);
1335
1336 /* ??? Needed to work around the pre-processor confusion with
1337 using a multi-argument template type as macro argument. */
1338 typedef vec<int> vec_int_heap;
1339 sccs = XCNEWVEC (vec_int_heap, nc);
1340 for (a = son[y]; a != -1; a = brother[a])
1341 sccs[g->vertices[a].component].safe_push (a);
1342
1343 for (i = nc - 1; i >= 0; i--)
1344 {
1345 dom = NULL;
1346 FOR_EACH_VEC_ELT (sccs[i], si, a)
1347 {
1348 bb = bbs[a];
1349 FOR_EACH_EDGE (e, ei, bb->preds)
1350 {
1351 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1352 continue;
1353
1354 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1355 }
1356 }
1357
1358 gcc_assert (dom != NULL);
1359 FOR_EACH_VEC_ELT (sccs[i], si, a)
1360 {
1361 bb = bbs[a];
1362 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1363 }
1364 }
1365
1366 for (i = 0; i < nc; i++)
1367 sccs[i].release ();
1368 free (sccs);
1369
1370 for (a = son[y]; a != -1; a = brother[a])
1371 identify_vertices (g, y, a);
1372}
1373
1374/* Recompute dominance information for basic blocks in the set BBS. The
1375 function assumes that the immediate dominators of all the other blocks
1376 in CFG are correct, and that there are no unreachable blocks.
1377
1378 If CONSERVATIVE is true, we additionally assume that all the ancestors of
1379 a block of BBS in the current dominance tree dominate it. */
1380
1381void
1382iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
1383 bool conservative)
1384{
1385 unsigned i;
1386 basic_block bb, dom;
1387 struct graph *g;
1388 int n, y;
1389 size_t dom_i;
1390 edge e;
1391 edge_iterator ei;
1392 int *parent, *son, *brother;
1393 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1394
1395 /* We only support updating dominators. There are some problems with
1396 updating postdominators (need to add fake edges from infinite loops
1397 and noreturn functions), and since we do not currently use
1398 iterate_fix_dominators for postdominators, any attempt to handle these
1399 problems would be unused, untested, and almost surely buggy. We keep
1400 the DIR argument for consistency with the rest of the dominator analysis
1401 interface. */
1402 gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
1403
1404 /* The algorithm we use takes inspiration from the following papers, although
1405 the details are quite different from any of them:
1406
1407 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1408 Dominator Tree of a Reducible Flowgraph
1409 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1410 dominator trees
1411 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1412 Algorithm
1413
1414 First, we use the following heuristics to decrease the size of the BBS
1415 set:
1416 a) if BB has a single predecessor, then its immediate dominator is this
1417 predecessor
1418 additionally, if CONSERVATIVE is true:
1419 b) if all the predecessors of BB except for one (X) are dominated by BB,
1420 then X is the immediate dominator of BB
1421 c) if the nearest common ancestor of the predecessors of BB is X and
1422 X -> BB is an edge in CFG, then X is the immediate dominator of BB
1423
1424 Then, we need to establish the dominance relation among the basic blocks
1425 in BBS. We split the dominance tree by removing the immediate dominator
1426 edges from BBS, creating a forest F. We form a graph G whose vertices
1427 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1428 X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1429 whose root is X. We then determine dominance tree of G. Note that
1430 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1431 In this step, we can use arbitrary algorithm to determine dominators.
1432 We decided to prefer the algorithm [3] to the algorithm of
1433 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1434 10 during gcc bootstrap), and [3] should perform better in this case.
1435
1436 Finally, we need to determine the immediate dominators for the basic
1437 blocks of BBS. If the immediate dominator of X in G is Y, then
1438 the immediate dominator of X in CFG belongs to the tree of F rooted in
1439 Y. We process the dominator tree T of G recursively, starting from leaves.
1440 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1441 subtrees of the dominance tree of CFG rooted in X_i are already correct.
1442 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1443 the following observations:
1444 (i) the immediate dominator of all blocks in a strongly connected
1445 component of G' is the same
1446 (ii) if X has no predecessors in G', then the immediate dominator of X
1447 is the nearest common ancestor of the predecessors of X in the
1448 subtree of F rooted in Y
1449 Therefore, it suffices to find the topological ordering of G', and
1450 process the nodes X_i in this order using the rules (i) and (ii).
1451 Then, we contract all the nodes X_i with Y in G, so that the further
1452 steps work correctly. */
1453
1454 if (!conservative)
1455 {
1456 /* Split the tree now. If the idoms of blocks in BBS are not
1457 conservatively correct, setting the dominators using the
1458 heuristics in prune_bbs_to_update_dominators could
1459 create cycles in the dominance "tree", and cause ICE. */
1460 FOR_EACH_VEC_ELT (bbs, i, bb)
1461 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1462 }
1463
1464 prune_bbs_to_update_dominators (bbs, conservative);
1465 n = bbs.length ();
1466
1467 if (n == 0)
1468 return;
1469
1470 if (n == 1)
1471 {
1472 bb = bbs[0];
1473 set_immediate_dominator (CDI_DOMINATORS, bb,
1474 recompute_dominator (CDI_DOMINATORS, bb));
1475 return;
1476 }
1477
1478 /* Construct the graph G. */
1479 hash_map<basic_block, int> map (251);
1480 FOR_EACH_VEC_ELT (bbs, i, bb)
1481 {
1482 /* If the dominance tree is conservatively correct, split it now. */
1483 if (conservative)
1484 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1485 map.put (bb, i);
1486 }
1487 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
1488
1489 g = new_graph (n + 1);
1490 for (y = 0; y < g->n_vertices; y++)
1491 g->vertices[y].data = BITMAP_ALLOC (NULL);
1492 FOR_EACH_VEC_ELT (bbs, i, bb)
1493 {
1494 FOR_EACH_EDGE (e, ei, bb->preds)
1495 {
1496 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1497 if (dom == bb)
1498 continue;
1499
1500 dom_i = *map.get (dom);
1501
1502 /* Do not include parallel edges to G. */
1503 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1504 continue;
1505
1506 add_edge (g, dom_i, i);
1507 }
1508 }
1509 for (y = 0; y < g->n_vertices; y++)
1510 BITMAP_FREE (g->vertices[y].data);
1511
1512 /* Find the dominator tree of G. */
1513 son = XNEWVEC (int, n + 1);
1514 brother = XNEWVEC (int, n + 1);
1515 parent = XNEWVEC (int, n + 1);
1516 graphds_domtree (g, n, parent, son, brother);
1517
1518 /* Finally, traverse the tree and find the immediate dominators. */
1519 for (y = n; son[y] != -1; y = son[y])
1520 continue;
1521 while (y != -1)
1522 {
1523 determine_dominators_for_sons (g, bbs, y, son, brother);
1524
1525 if (brother[y] != -1)
1526 {
1527 y = brother[y];
1528 while (son[y] != -1)
1529 y = son[y];
1530 }
1531 else
1532 y = parent[y];
1533 }
1534
1535 free (son);
1536 free (brother);
1537 free (parent);
1538
1539 free_graph (g);
1540}
1541
1542void
1543add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1544{
1545 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1546
1547 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1548
1549 n_bbs_in_dom_tree[dir_index]++;
1550
1551 bb->dom[dir_index] = et_new_tree (bb);
1552
1553 if (dom_computed[dir_index] == DOM_OK)
1554 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1555}
1556
1557void
1558delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1559{
1560 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1561
1562 gcc_checking_assert (dom_computed[dir_index]);
1563
1564 et_free_tree (bb->dom[dir_index]);
1565 bb->dom[dir_index] = NULL;
1566 n_bbs_in_dom_tree[dir_index]--;
1567
1568 if (dom_computed[dir_index] == DOM_OK)
1569 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1570}
1571
1572/* Returns the first son of BB in the dominator or postdominator tree
1573 as determined by DIR. */
1574
1575basic_block
1576first_dom_son (enum cdi_direction dir, basic_block bb)
1577{
1578 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1579 struct et_node *son = bb->dom[dir_index]->son;
1580
1581 return (basic_block) (son ? son->data : NULL);
1582}
1583
1584/* Returns the next dominance son after BB in the dominator or postdominator
1585 tree as determined by DIR, or NULL if it was the last one. */
1586
1587basic_block
1588next_dom_son (enum cdi_direction dir, basic_block bb)
1589{
1590 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1591 struct et_node *next = bb->dom[dir_index]->right;
1592
1593 return (basic_block) (next->father->son == next ? NULL : next->data);
1594}
1595
1596/* Return dominance availability for dominance info DIR. */
1597
1598enum dom_state
1599dom_info_state (function *fn, enum cdi_direction dir)
1600{
1601 if (!fn->cfg)
1602 return DOM_NONE;
1603
1604 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1605 return fn->cfg->x_dom_computed[dir_index];
1606}
1607
1608enum dom_state
1609dom_info_state (enum cdi_direction dir)
1610{
1611 return dom_info_state (cfun, dir);
1612}
1613
1614/* Set the dominance availability for dominance info DIR to NEW_STATE. */
1615
1616void
1617set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1618{
1619 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1620
1621 dom_computed[dir_index] = new_state;
1622}
1623
1624/* Returns true if dominance information for direction DIR is available. */
1625
1626bool
1627dom_info_available_p (function *fn, enum cdi_direction dir)
1628{
1629 return dom_info_state (fn, dir) != DOM_NONE;
1630}
1631
1632bool
1633dom_info_available_p (enum cdi_direction dir)
1634{
1635 return dom_info_available_p (cfun, dir);
1636}
1637
1638DEBUG_FUNCTION void
1639debug_dominance_info (enum cdi_direction dir)
1640{
1641 basic_block bb, bb2;
1642 FOR_EACH_BB_FN (bb, cfun)
1643 if ((bb2 = get_immediate_dominator (dir, bb)))
1644 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1645}
1646
1647/* Prints to stderr representation of the dominance tree (for direction DIR)
1648 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1649 the first line of the output is not indented. */
1650
1651static void
1652debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1653 unsigned indent, bool indent_first)
1654{
1655 basic_block son;
1656 unsigned i;
1657 bool first = true;
1658
1659 if (indent_first)
1660 for (i = 0; i < indent; i++)
1661 fprintf (stderr, "\t");
1662 fprintf (stderr, "%d\t", root->index);
1663
1664 for (son = first_dom_son (dir, root);
1665 son;
1666 son = next_dom_son (dir, son))
1667 {
1668 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1669 first = false;
1670 }
1671
1672 if (first)
1673 fprintf (stderr, "\n");
1674}
1675
1676/* Prints to stderr representation of the dominance tree (for direction DIR)
1677 rooted in ROOT. */
1678
1679DEBUG_FUNCTION void
1680debug_dominance_tree (enum cdi_direction dir, basic_block root)
1681{
1682 debug_dominance_tree_1 (dir, root, 0, false);
1683}
1684