Daily bump.
[official-gcc.git] / gcc / dominance.c
blobcc63391a39a5e4913f39e453dcb50391a4b8747d
1 /* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000-2021 Free Software Foundation, Inc.
3 Contributed by Michael Matz (matz@ifh.de).
5 This file is part of GCC.
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.
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.
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/>. */
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.
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. */
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"
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. */
51 /* Type of Basic Block aka. TBB */
52 typedef unsigned int TBB;
54 namespace {
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. */
59 class dom_info
61 public:
62 dom_info (function *, cdi_direction);
63 dom_info (vec <basic_block>, cdi_direction);
64 ~dom_info ();
65 void calc_dfs_tree ();
66 void calc_idoms ();
68 inline basic_block get_idom (basic_block);
69 private:
70 void calc_dfs_tree_nonrec (basic_block);
71 void compress (TBB);
72 void dom_init (void);
73 TBB eval (TBB);
74 void link_roots (TBB, TBB);
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;
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;
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;
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;
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;
127 /* Number of basic blocks in the function being compiled. */
128 unsigned m_n_basic_blocks;
130 /* True, if we are computing postdominators (rather than dominators). */
131 bool m_reverse;
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;
140 } // anonymous namespace
142 void debug_dominance_info (cdi_direction);
143 void debug_dominance_tree (cdi_direction, basic_block);
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] {};'. */
150 template<typename T>
151 inline T *new_zero_array (unsigned num)
153 T *result = new T[num];
154 memset (result, 0, sizeof (T) * num);
155 return result;
158 /* Helper function for constructors to initialize a part of class members. */
160 void
161 dom_info::dom_init (void)
163 unsigned num = m_n_basic_blocks;
165 m_dfs_parent = new_zero_array <TBB> (num);
166 m_dom = new_zero_array <TBB> (num);
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++)
173 m_path_min[i] = m_key[i] = i;
174 m_set_size[i] = 1;
177 m_bucket = new_zero_array <TBB> (num);
178 m_next_bucket = new_zero_array <TBB> (num);
180 m_set_chain = new_zero_array <TBB> (num);
181 m_set_child = new_zero_array <TBB> (num);
183 m_dfs_to_bb = new_zero_array <basic_block> (num);
185 m_dfsnum = 1;
186 m_nodes = 0;
189 /* Allocate all needed memory in a pessimistic fashion (so we round up). */
191 dom_info::dom_info (function *fn, cdi_direction dir)
193 m_n_basic_blocks = n_basic_blocks_for_fn (fn);
195 dom_init ();
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];
201 switch (dir)
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 ();
220 /* Constructor for reducible region REGION. */
222 dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
224 m_n_basic_blocks = region.length ();
225 unsigned nm1 = m_n_basic_blocks - 1;
227 dom_init ();
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. */
236 m_dfs_order = new_zero_array <TBB> (max_index + 1);
237 m_dfs_last = &m_dfs_order[max_index];
239 m_fake_exit_edge = NULL; /* Assume that region is reducible. */
241 switch (dir)
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 ();
258 inline basic_block
259 dom_info::get_idom (basic_block bb)
261 TBB d = m_dom[m_dfs_order[bb->index]];
262 return m_dfs_to_bb[d];
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. */
270 static inline unsigned int
271 dom_convert_dir_to_idx (cdi_direction dir)
273 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
274 return dir - 1;
277 /* Free all allocated memory in dom_info. */
279 dom_info::~dom_info ()
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);
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. */
301 void
302 dom_info::calc_dfs_tree_nonrec (basic_block bb)
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);
309 /* Initialize the first edge. */
310 edge_iterator ei = m_reverse ? ei_start (bb->preds)
311 : ei_start (bb->succs);
313 /* When the stack is empty we break out of this loop. */
314 while (1)
316 basic_block bn;
317 edge_iterator einext;
319 /* This loop traverses edges e in depth first manner, and fills the
320 stack. */
321 while (!ei_end_p (ei))
323 edge e = ei_edge (ei);
325 /* Deduce from E the current and the next block (BB and BN), and the
326 next edge. */
327 if (m_reverse)
329 bn = e->src;
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])
337 ei_next (&ei);
338 continue;
340 bb = e->dest;
341 einext = ei_start (bn->preds);
343 else
345 bn = e->dest;
346 if (bn == m_end_block || bn->dom[d_i] == NULL
347 || m_dfs_order[bn->index])
349 ei_next (&ei);
350 continue;
352 bb = e->src;
353 einext = ei_start (bn->succs);
356 gcc_assert (bn != m_start_block);
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;
368 /* Save the current point in the CFG on the stack, and recurse. */
369 stack[sp++] = ei;
370 ei = einext;
373 if (!sp)
374 break;
375 ei = stack[--sp];
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);
388 delete[] stack;
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. */
396 void
397 dom_info::calc_dfs_tree ()
399 *m_dfs_last = m_dfsnum;
400 m_dfs_to_bb[m_dfsnum] = m_start_block;
401 m_dfsnum++;
403 calc_dfs_tree_nonrec (m_start_block);
405 if (m_fake_exit_edge)
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.
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. */
417 basic_block b;
418 bool saw_unconnected = false;
420 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
422 if (EDGE_COUNT (b->succs) > 0)
424 if (m_dfs_order[b->index] == 0)
425 saw_unconnected = true;
426 continue;
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);
436 if (saw_unconnected)
438 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
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]);
455 m_nodes = m_dfsnum - 1;
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);
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. */
466 void
467 dom_info::compress (TBB v)
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])
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];
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. */
486 inline TBB
487 dom_info::eval (TBB v)
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];
493 /* V itself is the root. */
494 if (!rep)
495 return m_path_min[v];
497 /* Compress only if necessary. */
498 if (m_set_chain[rep])
500 compress (v);
501 rep = m_set_chain[v];
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];
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. */
515 void
516 dom_info::link_roots (TBB v, TBB w)
518 TBB s = w;
520 /* Rebalance the tree. */
521 while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
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]])
526 m_set_chain[m_set_child[s]] = s;
527 m_set_child[s] = m_set_child[m_set_child[s]];
529 else
531 m_set_size[m_set_child[s]] = m_set_size[s];
532 s = m_set_chain[s] = m_set_child[s];
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);
541 /* Merge all subtrees. */
542 while (s)
544 m_set_chain[s] = v;
545 s = m_set_child[s];
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]. */
553 void
554 dom_info::calc_idoms ()
556 /* Go backwards in DFS order, to first look at the leafs. */
557 for (TBB v = m_nodes; v > 1; v--)
559 basic_block bb = m_dfs_to_bb[v];
560 edge e;
562 TBB par = m_dfs_parent[v];
563 TBB k = v;
565 edge_iterator ei = m_reverse ? ei_start (bb->succs)
566 : ei_start (bb->preds);
567 edge_iterator einext;
569 if (m_fake_exit_edge)
571 /* If this block has a fake edge to exit, process that first. */
572 if (bitmap_bit_p (m_fake_exit_edge, bb->index))
574 einext = ei;
575 einext.index = 0;
576 goto do_fake_exit_edge;
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))
586 basic_block b;
587 TBB k1;
589 e = ei_edge (ei);
590 b = m_reverse ? e->dest : e->src;
591 einext = ei;
592 ei_next (&einext);
594 if (b == m_start_block)
596 do_fake_exit_edge:
597 k1 = *m_dfs_last;
599 else
600 k1 = m_dfs_order[b->index];
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;
609 ei = einext;
612 m_key[v] = k;
613 link_roots (par, v);
614 m_next_bucket[v] = m_bucket[k];
615 m_bucket[k] = v;
617 /* Transform semidominators into dominators. */
618 for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
620 k = eval (w);
621 if (m_key[k] < m_key[w])
622 m_dom[w] = k;
623 else
624 m_dom[w] = par;
626 /* We don't need to cleanup next_bucket[]. */
627 m_bucket[par] = 0;
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]];
637 /* Assign dfs numbers starting from NUM to NODE and its sons. */
639 static void
640 assign_dfs_numbers (struct et_node *node, int *num)
642 struct et_node *son;
644 node->dfs_num_in = (*num)++;
646 if (node->son)
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);
653 node->dfs_num_out = (*num)++;
656 /* Compute the data necessary for fast resolving of dominator queries in a
657 static dominator tree. */
659 static void
660 compute_dom_fast_query (enum cdi_direction dir)
662 int num = 0;
663 basic_block bb;
664 unsigned int dir_index = dom_convert_dir_to_idx (dir);
666 gcc_checking_assert (dom_info_available_p (dir));
668 if (dom_computed[dir_index] == DOM_OK)
669 return;
671 FOR_ALL_BB_FN (bb, cfun)
673 if (!bb->dom[dir_index]->father)
674 assign_dfs_numbers (bb->dom[dir_index], &num);
677 dom_computed[dir_index] = DOM_OK;
680 /* Analogous to the previous function but compute the data for reducible
681 region REGION. */
683 static void
684 compute_dom_fast_query_in_region (enum cdi_direction dir,
685 vec<basic_block> region)
687 int num = 0;
688 basic_block bb;
689 unsigned int dir_index = dom_convert_dir_to_idx (dir);
691 gcc_checking_assert (dom_info_available_p (dir));
693 if (dom_computed[dir_index] == DOM_OK)
694 return;
696 /* Assign dfs numbers for region nodes except for entry and exit nodes. */
697 for (unsigned int i = 1; i < region.length () - 1; i++)
699 bb = region[i];
700 if (!bb->dom[dir_index]->father)
701 assign_dfs_numbers (bb->dom[dir_index], &num);
704 dom_computed[dir_index] = DOM_OK;
707 /* The main entry point into this module. DIR is set depending on whether
708 we want to compute dominators or postdominators. */
710 void
711 calculate_dominance_info (cdi_direction dir)
713 unsigned int dir_index = dom_convert_dir_to_idx (dir);
715 if (dom_computed[dir_index] == DOM_OK)
717 checking_verify_dominators (dir);
718 return;
721 timevar_push (TV_DOMINANCE);
722 if (!dom_info_available_p (dir))
724 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
726 basic_block b;
727 FOR_ALL_BB_FN (b, cfun)
729 b->dom[dir_index] = et_new_tree (b);
731 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
733 dom_info di (cfun, dir);
734 di.calc_dfs_tree ();
735 di.calc_idoms ();
737 FOR_EACH_BB_FN (b, cfun)
739 if (basic_block d = di.get_idom (b))
740 et_set_father (b->dom[dir_index], d->dom[dir_index]);
743 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
745 else
746 checking_verify_dominators (dir);
748 compute_dom_fast_query (dir);
750 timevar_pop (TV_DOMINANCE);
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. */
757 void
758 calculate_dominance_info_for_region (cdi_direction dir,
759 vec<basic_block> region)
761 unsigned int dir_index = dom_convert_dir_to_idx (dir);
762 basic_block bb;
763 unsigned int i;
765 if (dom_computed[dir_index] == DOM_OK)
766 return;
768 timevar_push (TV_DOMINANCE);
769 /* Assume that dom info is not partially computed. */
770 gcc_assert (!dom_info_available_p (dir));
772 FOR_EACH_VEC_ELT (region, i, bb)
774 bb->dom[dir_index] = et_new_tree (bb);
776 dom_info di (region, dir);
777 di.calc_dfs_tree ();
778 di.calc_idoms ();
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]);
784 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
785 compute_dom_fast_query_in_region (dir, region);
787 timevar_pop (TV_DOMINANCE);
790 /* Free dominance information for direction DIR. */
791 void
792 free_dominance_info (function *fn, enum cdi_direction dir)
794 basic_block bb;
795 unsigned int dir_index = dom_convert_dir_to_idx (dir);
797 if (!dom_info_available_p (fn, dir))
798 return;
800 FOR_ALL_BB_FN (bb, fn)
802 et_free_tree_force (bb->dom[dir_index]);
803 bb->dom[dir_index] = NULL;
805 et_free_pools ();
807 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
809 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
812 void
813 free_dominance_info (enum cdi_direction dir)
815 free_dominance_info (cfun, dir);
818 /* Free dominance information for direction DIR in region REGION. */
820 void
821 free_dominance_info_for_region (function *fn,
822 enum cdi_direction dir,
823 vec<basic_block> region)
825 basic_block bb;
826 unsigned int i;
827 unsigned int dir_index = dom_convert_dir_to_idx (dir);
829 if (!dom_info_available_p (dir))
830 return;
832 FOR_EACH_VEC_ELT (region, i, bb)
834 et_free_tree_force (bb->dom[dir_index]);
835 bb->dom[dir_index] = NULL;
837 et_free_pools ();
839 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
841 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
844 /* Return the immediate dominator of basic block BB. */
845 basic_block
846 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
848 unsigned int dir_index = dom_convert_dir_to_idx (dir);
849 struct et_node *node = bb->dom[dir_index];
851 gcc_checking_assert (dom_computed[dir_index]);
853 if (!node->father)
854 return NULL;
856 return (basic_block) node->father->data;
859 /* Set the immediate dominator of the block possibly removing
860 existing edge. NULL can be used to remove any edge. */
861 void
862 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
863 basic_block dominated_by)
865 unsigned int dir_index = dom_convert_dir_to_idx (dir);
866 struct et_node *node = bb->dom[dir_index];
868 gcc_checking_assert (dom_computed[dir_index]);
870 if (node->father)
872 if (node->father->data == dominated_by)
873 return;
874 et_split (node);
877 if (dominated_by)
878 et_set_father (node, dominated_by->dom[dir_index]);
880 if (dom_computed[dir_index] == DOM_OK)
881 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
884 /* Returns the list of basic blocks immediately dominated by BB, in the
885 direction DIR. */
886 auto_vec<basic_block>
887 get_dominated_by (enum cdi_direction dir, basic_block bb)
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 auto_vec<basic_block> bbs;
893 gcc_checking_assert (dom_computed[dir_index]);
895 if (!son)
896 return bbs;
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);
902 return bbs;
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. */
909 auto_vec<basic_block>
910 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
911 unsigned n_region)
913 unsigned i;
914 basic_block dom;
915 auto_vec<basic_block> doms;
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;
928 return doms;
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. */
936 auto_vec<basic_block>
937 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
939 auto_vec<basic_block> bbs;
940 unsigned i;
941 unsigned next_level_start;
943 i = 0;
944 bbs.safe_push (bb);
945 next_level_start = 1; /* = bbs.length (); */
949 basic_block son;
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);
957 if (i == next_level_start && --depth)
958 next_level_start = bbs.length ();
960 while (i < next_level_start);
962 return bbs;
965 /* Returns the list of basic blocks including BB dominated by BB, in the
966 direction DIR. The vector will be sorted in preorder. */
968 auto_vec<basic_block>
969 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
971 return get_dominated_to_depth (dir, bb, 0);
974 /* Redirect all edges pointing to BB to TO. */
975 void
976 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
977 basic_block to)
979 unsigned int dir_index = dom_convert_dir_to_idx (dir);
980 struct et_node *bb_node, *to_node, *son;
982 bb_node = bb->dom[dir_index];
983 to_node = to->dom[dir_index];
985 gcc_checking_assert (dom_computed[dir_index]);
987 if (!bb_node->son)
988 return;
990 while (bb_node->son)
992 son = bb_node->son;
994 et_split (son);
995 et_set_father (son, to_node);
998 if (dom_computed[dir_index] == DOM_OK)
999 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1002 /* Find first basic block in the tree dominating both BB1 and BB2. */
1003 basic_block
1004 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1006 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1008 gcc_checking_assert (dom_computed[dir_index]);
1010 if (!bb1)
1011 return bb2;
1012 if (!bb2)
1013 return bb1;
1015 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
1019 /* Find the nearest common dominator for the basic blocks in BLOCKS,
1020 using dominance direction DIR. */
1022 basic_block
1023 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1025 unsigned i, first;
1026 bitmap_iterator bi;
1027 basic_block dom;
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));
1035 return dom;
1038 /* Given a dominator tree, we can determine whether one thing
1039 dominates another in constant time by using two DFS numbers:
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
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.
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:
1052 1. Node A is above Node B (and thus, Node A dominates node B)
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
1066 2. Node A is below node B (and thus, node B dominates node A)
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.
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
1081 3. Node A and B are siblings (and thus, neither dominates the other)
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.
1099 Thus, it is sufficient to write
1101 A_Dominates_B (node A, node B)
1103 return DFS_Number_In(A) <= DFS_Number_In(B)
1104 && DFS_Number_Out (A) >= DFS_Number_Out(B);
1107 A_Dominated_by_B (node A, node B)
1109 return DFS_Number_In(A) >= DFS_Number_In(B)
1110 && DFS_Number_Out (A) <= DFS_Number_Out(B);
1111 } */
1113 /* Return TRUE in case BB1 is dominated by BB2. */
1114 bool
1115 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
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];
1120 gcc_checking_assert (dom_computed[dir_index]);
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);
1126 return et_below (n1, n2);
1129 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
1131 unsigned
1132 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1134 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1135 struct et_node *n = bb->dom[dir_index];
1137 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1138 return n->dfs_num_in;
1141 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
1143 unsigned
1144 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1146 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1147 struct et_node *n = bb->dom[dir_index];
1149 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1150 return n->dfs_num_out;
1153 /* Verify invariants of dominator structure. */
1154 DEBUG_FUNCTION void
1155 verify_dominators (cdi_direction dir)
1157 gcc_assert (dom_info_available_p (dir));
1159 dom_info di (cfun, dir);
1160 di.calc_dfs_tree ();
1161 di.calc_idoms ();
1163 bool err = false;
1164 basic_block bb;
1165 FOR_EACH_BB_FN (bb, cfun)
1167 basic_block imm_bb = get_immediate_dominator (dir, bb);
1168 if (!imm_bb)
1170 error ("dominator of %d status unknown", bb->index);
1171 err = true;
1172 continue;
1175 basic_block imm_bb_correct = di.get_idom (bb);
1176 if (imm_bb != imm_bb_correct)
1178 error ("dominator of %d should be %d, not %d",
1179 bb->index, imm_bb_correct->index, imm_bb->index);
1180 err = true;
1184 gcc_assert (!err);
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. */
1192 basic_block
1193 recompute_dominator (enum cdi_direction dir, basic_block bb)
1195 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1196 basic_block dom_bb = NULL;
1197 edge e;
1198 edge_iterator ei;
1200 gcc_checking_assert (dom_computed[dir_index]);
1202 if (dir == CDI_DOMINATORS)
1204 FOR_EACH_EDGE (e, ei, bb->preds)
1206 if (!dominated_by_p (dir, e->src, bb))
1207 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1210 else
1212 FOR_EACH_EDGE (e, ei, bb->succs)
1214 if (!dominated_by_p (dir, e->dest, bb))
1215 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1219 return dom_bb;
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. */
1229 static void
1230 prune_bbs_to_update_dominators (vec<basic_block> &bbs,
1231 bool conservative)
1233 unsigned i;
1234 bool single;
1235 basic_block bb, dom = NULL;
1236 edge_iterator ei;
1237 edge e;
1239 for (i = 0; bbs.iterate (i, &bb);)
1241 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1242 goto succeed;
1244 if (single_pred_p (bb))
1246 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1247 goto succeed;
1250 if (!conservative)
1251 goto fail;
1253 single = true;
1254 dom = NULL;
1255 FOR_EACH_EDGE (e, ei, bb->preds)
1257 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1258 continue;
1260 if (!dom)
1261 dom = e->src;
1262 else
1264 single = false;
1265 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1269 gcc_assert (dom != NULL);
1270 if (single
1271 || find_edge (dom, bb))
1273 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1274 goto succeed;
1277 fail:
1278 i++;
1279 continue;
1281 succeed:
1282 bbs.unordered_remove (i);
1286 /* Returns root of the dominance tree in the direction DIR that contains
1287 BB. */
1289 static basic_block
1290 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1292 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
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. */
1300 static void
1301 determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1302 int y, int *son, int *brother)
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;
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];
1319 if (brother[son[y]] == -1)
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;
1329 gprime = BITMAP_ALLOC (NULL);
1330 for (a = son[y]; a != -1; a = brother[a])
1331 bitmap_set_bit (gprime, a);
1333 nc = graphds_scc (g, gprime);
1334 BITMAP_FREE (gprime);
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);
1343 for (i = nc - 1; i >= 0; i--)
1345 dom = NULL;
1346 FOR_EACH_VEC_ELT (sccs[i], si, a)
1348 bb = bbs[a];
1349 FOR_EACH_EDGE (e, ei, bb->preds)
1351 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1352 continue;
1354 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1358 gcc_assert (dom != NULL);
1359 FOR_EACH_VEC_ELT (sccs[i], si, a)
1361 bb = bbs[a];
1362 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1366 for (i = 0; i < nc; i++)
1367 sccs[i].release ();
1368 free (sccs);
1370 for (a = son[y]; a != -1; a = brother[a])
1371 identify_vertices (g, y, a);
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.
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. */
1381 void
1382 iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> &bbs,
1383 bool conservative)
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);
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]);
1404 /* The algorithm we use takes inspiration from the following papers, although
1405 the details are quite different from any of them:
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
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
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.
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. */
1454 if (!conservative)
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);
1464 prune_bbs_to_update_dominators (bbs, conservative);
1465 n = bbs.length ();
1467 if (n == 0)
1468 return;
1470 if (n == 1)
1472 bb = bbs[0];
1473 set_immediate_dominator (CDI_DOMINATORS, bb,
1474 recompute_dominator (CDI_DOMINATORS, bb));
1475 return;
1478 timevar_push (TV_DOMINANCE);
1480 /* Construct the graph G. */
1481 hash_map<basic_block, int> map (251);
1482 FOR_EACH_VEC_ELT (bbs, i, bb)
1484 /* If the dominance tree is conservatively correct, split it now. */
1485 if (conservative)
1486 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1487 map.put (bb, i);
1489 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
1491 g = new_graph (n + 1);
1492 for (y = 0; y < g->n_vertices; y++)
1493 g->vertices[y].data = BITMAP_ALLOC (NULL);
1494 FOR_EACH_VEC_ELT (bbs, i, bb)
1496 FOR_EACH_EDGE (e, ei, bb->preds)
1498 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1499 if (dom == bb)
1500 continue;
1502 dom_i = *map.get (dom);
1504 /* Do not include parallel edges to G. */
1505 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1506 continue;
1508 add_edge (g, dom_i, i);
1511 for (y = 0; y < g->n_vertices; y++)
1512 BITMAP_FREE (g->vertices[y].data);
1514 /* Find the dominator tree of G. */
1515 son = XNEWVEC (int, n + 1);
1516 brother = XNEWVEC (int, n + 1);
1517 parent = XNEWVEC (int, n + 1);
1518 graphds_domtree (g, n, parent, son, brother);
1520 /* Finally, traverse the tree and find the immediate dominators. */
1521 for (y = n; son[y] != -1; y = son[y])
1522 continue;
1523 while (y != -1)
1525 determine_dominators_for_sons (g, bbs, y, son, brother);
1527 if (brother[y] != -1)
1529 y = brother[y];
1530 while (son[y] != -1)
1531 y = son[y];
1533 else
1534 y = parent[y];
1537 free (son);
1538 free (brother);
1539 free (parent);
1541 free_graph (g);
1543 timevar_pop (TV_DOMINANCE);
1546 void
1547 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1549 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1551 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1553 n_bbs_in_dom_tree[dir_index]++;
1555 bb->dom[dir_index] = et_new_tree (bb);
1557 if (dom_computed[dir_index] == DOM_OK)
1558 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1561 void
1562 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1564 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1566 gcc_checking_assert (dom_computed[dir_index]);
1568 et_free_tree (bb->dom[dir_index]);
1569 bb->dom[dir_index] = NULL;
1570 n_bbs_in_dom_tree[dir_index]--;
1572 if (dom_computed[dir_index] == DOM_OK)
1573 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1576 /* Returns the first son of BB in the dominator or postdominator tree
1577 as determined by DIR. */
1579 basic_block
1580 first_dom_son (enum cdi_direction dir, basic_block bb)
1582 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1583 struct et_node *son = bb->dom[dir_index]->son;
1585 return (basic_block) (son ? son->data : NULL);
1588 /* Returns the next dominance son after BB in the dominator or postdominator
1589 tree as determined by DIR, or NULL if it was the last one. */
1591 basic_block
1592 next_dom_son (enum cdi_direction dir, basic_block bb)
1594 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1595 struct et_node *next = bb->dom[dir_index]->right;
1597 return (basic_block) (next->father->son == next ? NULL : next->data);
1600 /* Return dominance availability for dominance info DIR. */
1602 enum dom_state
1603 dom_info_state (function *fn, enum cdi_direction dir)
1605 if (!fn->cfg)
1606 return DOM_NONE;
1608 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1609 return fn->cfg->x_dom_computed[dir_index];
1612 enum dom_state
1613 dom_info_state (enum cdi_direction dir)
1615 return dom_info_state (cfun, dir);
1618 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1620 void
1621 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1623 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1625 dom_computed[dir_index] = new_state;
1628 /* Returns true if dominance information for direction DIR is available. */
1630 bool
1631 dom_info_available_p (function *fn, enum cdi_direction dir)
1633 return dom_info_state (fn, dir) != DOM_NONE;
1636 bool
1637 dom_info_available_p (enum cdi_direction dir)
1639 return dom_info_available_p (cfun, dir);
1642 DEBUG_FUNCTION void
1643 debug_dominance_info (enum cdi_direction dir)
1645 basic_block bb, bb2;
1646 FOR_EACH_BB_FN (bb, cfun)
1647 if ((bb2 = get_immediate_dominator (dir, bb)))
1648 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1651 /* Prints to stderr representation of the dominance tree (for direction DIR)
1652 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1653 the first line of the output is not indented. */
1655 static void
1656 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1657 unsigned indent, bool indent_first)
1659 basic_block son;
1660 unsigned i;
1661 bool first = true;
1663 if (indent_first)
1664 for (i = 0; i < indent; i++)
1665 fprintf (stderr, "\t");
1666 fprintf (stderr, "%d\t", root->index);
1668 for (son = first_dom_son (dir, root);
1669 son;
1670 son = next_dom_son (dir, son))
1672 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1673 first = false;
1676 if (first)
1677 fprintf (stderr, "\n");
1680 /* Prints to stderr representation of the dominance tree (for direction DIR)
1681 rooted in ROOT. */
1683 DEBUG_FUNCTION void
1684 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1686 debug_dominance_tree_1 (dir, root, 0, false);