gcc/ChangeLog:
[official-gcc.git] / gcc / dominance.c
blobc76e62e52ee19d4378504e048c8b0d57645ee434
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).
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 size_t 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 (size_t 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 size_t num = m_n_basic_blocks;
164 m_dfs_parent = new_zero_array <TBB> (num);
165 m_dom = new_zero_array <TBB> (num);
167 m_path_min = new TBB[num];
168 m_key = new TBB[num];
169 m_set_size = new unsigned int[num];
170 for (size_t i = 0; i < num; i++)
172 m_path_min[i] = m_key[i] = i;
173 m_set_size[i] = 1;
176 m_bucket = new_zero_array <TBB> (num);
177 m_next_bucket = new_zero_array <TBB> (num);
179 m_set_chain = new_zero_array <TBB> (num);
180 m_set_child = new_zero_array <TBB> (num);
182 m_dfs_to_bb = new_zero_array <basic_block> (num);
184 m_dfsnum = 1;
185 m_nodes = 0;
188 /* Allocate all needed memory in a pessimistic fashion (so we round up). */
190 dom_info::dom_info (function *fn, cdi_direction dir)
192 m_n_basic_blocks = n_basic_blocks_for_fn (fn);
194 dom_init ();
196 unsigned last_bb_index = last_basic_block_for_fn (fn);
197 m_dfs_order = new_zero_array <TBB> (last_bb_index + 1);
198 m_dfs_last = &m_dfs_order[last_bb_index];
200 switch (dir)
202 case CDI_DOMINATORS:
203 m_reverse = false;
204 m_fake_exit_edge = NULL;
205 m_start_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
206 m_end_block = EXIT_BLOCK_PTR_FOR_FN (fn);
207 break;
208 case CDI_POST_DOMINATORS:
209 m_reverse = true;
210 m_fake_exit_edge = BITMAP_ALLOC (NULL);
211 m_start_block = EXIT_BLOCK_PTR_FOR_FN (fn);
212 m_end_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
213 break;
214 default:
215 gcc_unreachable ();
219 /* Constructor for reducible region REGION. */
221 dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
223 m_n_basic_blocks = region.length ();
224 unsigned int nm1 = m_n_basic_blocks - 1;
226 dom_init ();
228 /* Determine max basic block index in region. */
229 int max_index = region[0]->index;
230 for (size_t i = 1; i <= nm1; i++)
231 if (region[i]->index > max_index)
232 max_index = region[i]->index;
233 max_index += 1; /* set index on the first bb out of region. */
235 m_dfs_order = new_zero_array <TBB> (max_index + 1);
236 m_dfs_last = &m_dfs_order[max_index];
238 m_fake_exit_edge = NULL; /* Assume that region is reducible. */
240 switch (dir)
242 case CDI_DOMINATORS:
243 m_reverse = false;
244 m_start_block = region[0];
245 m_end_block = region[nm1];
246 break;
247 case CDI_POST_DOMINATORS:
248 m_reverse = true;
249 m_start_block = region[nm1];
250 m_end_block = region[0];
251 break;
252 default:
253 gcc_unreachable ();
257 inline basic_block
258 dom_info::get_idom (basic_block bb)
260 TBB d = m_dom[m_dfs_order[bb->index]];
261 return m_dfs_to_bb[d];
264 /* Map dominance calculation type to array index used for various
265 dominance information arrays. This version is simple -- it will need
266 to be modified, obviously, if additional values are added to
267 cdi_direction. */
269 static inline unsigned int
270 dom_convert_dir_to_idx (cdi_direction dir)
272 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
273 return dir - 1;
276 /* Free all allocated memory in dom_info. */
278 dom_info::~dom_info ()
280 delete[] m_dfs_parent;
281 delete[] m_path_min;
282 delete[] m_key;
283 delete[] m_dom;
284 delete[] m_bucket;
285 delete[] m_next_bucket;
286 delete[] m_set_chain;
287 delete[] m_set_size;
288 delete[] m_set_child;
289 delete[] m_dfs_order;
290 delete[] m_dfs_to_bb;
291 BITMAP_FREE (m_fake_exit_edge);
294 /* The nonrecursive variant of creating a DFS tree. BB is the starting basic
295 block for this tree and m_reverse is true, if predecessors should be visited
296 instead of successors of a node. After this is done all nodes reachable
297 from BB were visited, have assigned their dfs number and are linked together
298 to form a tree. */
300 void
301 dom_info::calc_dfs_tree_nonrec (basic_block bb)
303 edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
304 int sp = 0;
305 unsigned d_i = dom_convert_dir_to_idx (m_reverse ? CDI_POST_DOMINATORS
306 : CDI_DOMINATORS);
308 /* Initialize the first edge. */
309 edge_iterator ei = m_reverse ? ei_start (bb->preds)
310 : ei_start (bb->succs);
312 /* When the stack is empty we break out of this loop. */
313 while (1)
315 basic_block bn;
316 edge_iterator einext;
318 /* This loop traverses edges e in depth first manner, and fills the
319 stack. */
320 while (!ei_end_p (ei))
322 edge e = ei_edge (ei);
324 /* Deduce from E the current and the next block (BB and BN), and the
325 next edge. */
326 if (m_reverse)
328 bn = e->src;
330 /* If the next node BN is either already visited or a border
331 block or out of region the current edge is useless, and simply
332 overwritten with the next edge out of the current node. */
333 if (bn == m_end_block || bn->dom[d_i] == NULL
334 || m_dfs_order[bn->index])
336 ei_next (&ei);
337 continue;
339 bb = e->dest;
340 einext = ei_start (bn->preds);
342 else
344 bn = e->dest;
345 if (bn == m_end_block || bn->dom[d_i] == NULL
346 || m_dfs_order[bn->index])
348 ei_next (&ei);
349 continue;
351 bb = e->src;
352 einext = ei_start (bn->succs);
355 gcc_assert (bn != m_start_block);
357 /* Fill the DFS tree info calculatable _before_ recursing. */
358 TBB my_i;
359 if (bb != m_start_block)
360 my_i = m_dfs_order[bb->index];
361 else
362 my_i = *m_dfs_last;
363 TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
364 m_dfs_to_bb[child_i] = bn;
365 m_dfs_parent[child_i] = my_i;
367 /* Save the current point in the CFG on the stack, and recurse. */
368 stack[sp++] = ei;
369 ei = einext;
372 if (!sp)
373 break;
374 ei = stack[--sp];
376 /* OK. The edge-list was exhausted, meaning normally we would
377 end the recursion. After returning from the recursive call,
378 there were (may be) other statements which were run after a
379 child node was completely considered by DFS. Here is the
380 point to do it in the non-recursive variant.
381 E.g. The block just completed is in e->dest for forward DFS,
382 the block not yet completed (the parent of the one above)
383 in e->src. This could be used e.g. for computing the number of
384 descendants or the tree depth. */
385 ei_next (&ei);
387 delete[] stack;
390 /* The main entry for calculating the DFS tree or forest. m_reverse is true,
391 if we are interested in the reverse flow graph. In that case the result is
392 not necessarily a tree but a forest, because there may be nodes from which
393 the EXIT_BLOCK is unreachable. */
395 void
396 dom_info::calc_dfs_tree ()
398 *m_dfs_last = m_dfsnum;
399 m_dfs_to_bb[m_dfsnum] = m_start_block;
400 m_dfsnum++;
402 calc_dfs_tree_nonrec (m_start_block);
404 if (m_fake_exit_edge)
406 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
407 They are reverse-unreachable. In the dom-case we disallow such
408 nodes, but in post-dom we have to deal with them.
410 There are two situations in which this occurs. First, noreturn
411 functions. Second, infinite loops. In the first case we need to
412 pretend that there is an edge to the exit block. In the second
413 case, we wind up with a forest. We need to process all noreturn
414 blocks before we know if we've got any infinite loops. */
416 basic_block b;
417 bool saw_unconnected = false;
419 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
421 if (EDGE_COUNT (b->succs) > 0)
423 if (m_dfs_order[b->index] == 0)
424 saw_unconnected = true;
425 continue;
427 bitmap_set_bit (m_fake_exit_edge, b->index);
428 m_dfs_order[b->index] = m_dfsnum;
429 m_dfs_to_bb[m_dfsnum] = b;
430 m_dfs_parent[m_dfsnum] = *m_dfs_last;
431 m_dfsnum++;
432 calc_dfs_tree_nonrec (b);
435 if (saw_unconnected)
437 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
439 if (m_dfs_order[b->index])
440 continue;
441 basic_block b2 = dfs_find_deadend (b);
442 gcc_checking_assert (m_dfs_order[b2->index] == 0);
443 bitmap_set_bit (m_fake_exit_edge, b2->index);
444 m_dfs_order[b2->index] = m_dfsnum;
445 m_dfs_to_bb[m_dfsnum] = b2;
446 m_dfs_parent[m_dfsnum] = *m_dfs_last;
447 m_dfsnum++;
448 calc_dfs_tree_nonrec (b2);
449 gcc_checking_assert (m_dfs_order[b->index]);
454 m_nodes = m_dfsnum - 1;
456 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
457 gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1);
460 /* Compress the path from V to the root of its set and update path_min at the
461 same time. After compress(di, V) set_chain[V] is the root of the set V is
462 in and path_min[V] is the node with the smallest key[] value on the path
463 from V to that root. */
465 void
466 dom_info::compress (TBB v)
468 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
469 greater than 5 even for huge graphs (I've not seen call depth > 4).
470 Also performance wise compress() ranges _far_ behind eval(). */
471 TBB parent = m_set_chain[v];
472 if (m_set_chain[parent])
474 compress (parent);
475 if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
476 m_path_min[v] = m_path_min[parent];
477 m_set_chain[v] = m_set_chain[parent];
481 /* Compress the path from V to the set root of V if needed (when the root has
482 changed since the last call). Returns the node with the smallest key[]
483 value on the path from V to the root. */
485 inline TBB
486 dom_info::eval (TBB v)
488 /* The representative of the set V is in, also called root (as the set
489 representation is a tree). */
490 TBB rep = m_set_chain[v];
492 /* V itself is the root. */
493 if (!rep)
494 return m_path_min[v];
496 /* Compress only if necessary. */
497 if (m_set_chain[rep])
499 compress (v);
500 rep = m_set_chain[v];
503 if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
504 return m_path_min[v];
505 else
506 return m_path_min[rep];
509 /* This essentially merges the two sets of V and W, giving a single set with
510 the new root V. The internal representation of these disjoint sets is a
511 balanced tree. Currently link(V,W) is only used with V being the parent
512 of W. */
514 void
515 dom_info::link_roots (TBB v, TBB w)
517 TBB s = w;
519 /* Rebalance the tree. */
520 while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
522 if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
523 >= 2 * m_set_size[m_set_child[s]])
525 m_set_chain[m_set_child[s]] = s;
526 m_set_child[s] = m_set_child[m_set_child[s]];
528 else
530 m_set_size[m_set_child[s]] = m_set_size[s];
531 s = m_set_chain[s] = m_set_child[s];
535 m_path_min[s] = m_path_min[w];
536 m_set_size[v] += m_set_size[w];
537 if (m_set_size[v] < 2 * m_set_size[w])
538 std::swap (m_set_child[v], s);
540 /* Merge all subtrees. */
541 while (s)
543 m_set_chain[s] = v;
544 s = m_set_child[s];
548 /* This calculates the immediate dominators (or post-dominators). THIS is our
549 working structure and should hold the DFS forest.
550 On return the immediate dominator to node V is in m_dom[V]. */
552 void
553 dom_info::calc_idoms ()
555 /* Go backwards in DFS order, to first look at the leafs. */
556 for (TBB v = m_nodes; v > 1; v--)
558 basic_block bb = m_dfs_to_bb[v];
559 edge e;
561 TBB par = m_dfs_parent[v];
562 TBB k = v;
564 edge_iterator ei = m_reverse ? ei_start (bb->succs)
565 : ei_start (bb->preds);
566 edge_iterator einext;
568 if (m_fake_exit_edge)
570 /* If this block has a fake edge to exit, process that first. */
571 if (bitmap_bit_p (m_fake_exit_edge, bb->index))
573 einext = ei;
574 einext.index = 0;
575 goto do_fake_exit_edge;
579 /* Search all direct predecessors for the smallest node with a path
580 to them. That way we have the smallest node with also a path to
581 us only over nodes behind us. In effect we search for our
582 semidominator. */
583 while (!ei_end_p (ei))
585 basic_block b;
586 TBB k1;
588 e = ei_edge (ei);
589 b = m_reverse ? e->dest : e->src;
590 einext = ei;
591 ei_next (&einext);
593 if (b == m_start_block)
595 do_fake_exit_edge:
596 k1 = *m_dfs_last;
598 else
599 k1 = m_dfs_order[b->index];
601 /* Call eval() only if really needed. If k1 is above V in DFS tree,
602 then we know, that eval(k1) == k1 and key[k1] == k1. */
603 if (k1 > v)
604 k1 = m_key[eval (k1)];
605 if (k1 < k)
606 k = k1;
608 ei = einext;
611 m_key[v] = k;
612 link_roots (par, v);
613 m_next_bucket[v] = m_bucket[k];
614 m_bucket[k] = v;
616 /* Transform semidominators into dominators. */
617 for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
619 k = eval (w);
620 if (m_key[k] < m_key[w])
621 m_dom[w] = k;
622 else
623 m_dom[w] = par;
625 /* We don't need to cleanup next_bucket[]. */
626 m_bucket[par] = 0;
629 /* Explicitly define the dominators. */
630 m_dom[1] = 0;
631 for (TBB v = 2; v <= m_nodes; v++)
632 if (m_dom[v] != m_key[v])
633 m_dom[v] = m_dom[m_dom[v]];
636 /* Assign dfs numbers starting from NUM to NODE and its sons. */
638 static void
639 assign_dfs_numbers (struct et_node *node, int *num)
641 struct et_node *son;
643 node->dfs_num_in = (*num)++;
645 if (node->son)
647 assign_dfs_numbers (node->son, num);
648 for (son = node->son->right; son != node->son; son = son->right)
649 assign_dfs_numbers (son, num);
652 node->dfs_num_out = (*num)++;
655 /* Compute the data necessary for fast resolving of dominator queries in a
656 static dominator tree. */
658 static void
659 compute_dom_fast_query (enum cdi_direction dir)
661 int num = 0;
662 basic_block bb;
663 unsigned int dir_index = dom_convert_dir_to_idx (dir);
665 gcc_checking_assert (dom_info_available_p (dir));
667 if (dom_computed[dir_index] == DOM_OK)
668 return;
670 FOR_ALL_BB_FN (bb, cfun)
672 if (!bb->dom[dir_index]->father)
673 assign_dfs_numbers (bb->dom[dir_index], &num);
676 dom_computed[dir_index] = DOM_OK;
679 /* Analogous to the previous function but compute the data for reducible
680 region REGION. */
682 static void
683 compute_dom_fast_query_in_region (enum cdi_direction dir,
684 vec<basic_block> region)
686 int num = 0;
687 basic_block bb;
688 unsigned int dir_index = dom_convert_dir_to_idx (dir);
690 gcc_checking_assert (dom_info_available_p (dir));
692 if (dom_computed[dir_index] == DOM_OK)
693 return;
695 /* Assign dfs numbers for region nodes except for entry and exit nodes. */
696 for (unsigned int i = 1; i < region.length () - 1; i++)
698 bb = region[i];
699 if (!bb->dom[dir_index]->father)
700 assign_dfs_numbers (bb->dom[dir_index], &num);
703 dom_computed[dir_index] = DOM_OK;
706 /* The main entry point into this module. DIR is set depending on whether
707 we want to compute dominators or postdominators. */
709 void
710 calculate_dominance_info (cdi_direction dir)
712 unsigned int dir_index = dom_convert_dir_to_idx (dir);
714 if (dom_computed[dir_index] == DOM_OK)
716 checking_verify_dominators (dir);
717 return;
720 timevar_push (TV_DOMINANCE);
721 if (!dom_info_available_p (dir))
723 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
725 basic_block b;
726 FOR_ALL_BB_FN (b, cfun)
728 b->dom[dir_index] = et_new_tree (b);
730 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
732 dom_info di (cfun, dir);
733 di.calc_dfs_tree ();
734 di.calc_idoms ();
736 FOR_EACH_BB_FN (b, cfun)
738 if (basic_block d = di.get_idom (b))
739 et_set_father (b->dom[dir_index], d->dom[dir_index]);
742 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
744 else
745 checking_verify_dominators (dir);
747 compute_dom_fast_query (dir);
749 timevar_pop (TV_DOMINANCE);
752 /* Analogous to the previous function but compute dominance info for regions
753 which are single entry, multiple exit regions for CDI_DOMINATORs and
754 multiple entry, single exit regions for CDI_POST_DOMINATORs. */
756 void
757 calculate_dominance_info_for_region (cdi_direction dir,
758 vec<basic_block> region)
760 unsigned int dir_index = dom_convert_dir_to_idx (dir);
761 basic_block bb;
762 unsigned int i;
764 if (dom_computed[dir_index] == DOM_OK)
765 return;
767 timevar_push (TV_DOMINANCE);
768 /* Assume that dom info is not partially computed. */
769 gcc_assert (!dom_info_available_p (dir));
771 FOR_EACH_VEC_ELT (region, i, bb)
773 bb->dom[dir_index] = et_new_tree (bb);
775 dom_info di (region, dir);
776 di.calc_dfs_tree ();
777 di.calc_idoms ();
779 FOR_EACH_VEC_ELT (region, i, bb)
780 if (basic_block d = di.get_idom (bb))
781 et_set_father (bb->dom[dir_index], d->dom[dir_index]);
783 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
784 compute_dom_fast_query_in_region (dir, region);
786 timevar_pop (TV_DOMINANCE);
789 /* Free dominance information for direction DIR. */
790 void
791 free_dominance_info (function *fn, enum cdi_direction dir)
793 basic_block bb;
794 unsigned int dir_index = dom_convert_dir_to_idx (dir);
796 if (!dom_info_available_p (fn, dir))
797 return;
799 FOR_ALL_BB_FN (bb, fn)
801 et_free_tree_force (bb->dom[dir_index]);
802 bb->dom[dir_index] = NULL;
804 et_free_pools ();
806 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
808 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
811 void
812 free_dominance_info (enum cdi_direction dir)
814 free_dominance_info (cfun, dir);
817 /* Free dominance information for direction DIR in region REGION. */
819 void
820 free_dominance_info_for_region (function *fn,
821 enum cdi_direction dir,
822 vec<basic_block> region)
824 basic_block bb;
825 unsigned int i;
826 unsigned int dir_index = dom_convert_dir_to_idx (dir);
828 if (!dom_info_available_p (dir))
829 return;
831 FOR_EACH_VEC_ELT (region, i, bb)
833 et_free_tree_force (bb->dom[dir_index]);
834 bb->dom[dir_index] = NULL;
836 et_free_pools ();
838 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
840 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
843 /* Return the immediate dominator of basic block BB. */
844 basic_block
845 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
847 unsigned int dir_index = dom_convert_dir_to_idx (dir);
848 struct et_node *node = bb->dom[dir_index];
850 gcc_checking_assert (dom_computed[dir_index]);
852 if (!node->father)
853 return NULL;
855 return (basic_block) node->father->data;
858 /* Set the immediate dominator of the block possibly removing
859 existing edge. NULL can be used to remove any edge. */
860 void
861 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
862 basic_block dominated_by)
864 unsigned int dir_index = dom_convert_dir_to_idx (dir);
865 struct et_node *node = bb->dom[dir_index];
867 gcc_checking_assert (dom_computed[dir_index]);
869 if (node->father)
871 if (node->father->data == dominated_by)
872 return;
873 et_split (node);
876 if (dominated_by)
877 et_set_father (node, dominated_by->dom[dir_index]);
879 if (dom_computed[dir_index] == DOM_OK)
880 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
883 /* Returns the list of basic blocks immediately dominated by BB, in the
884 direction DIR. */
885 vec<basic_block>
886 get_dominated_by (enum cdi_direction dir, basic_block bb)
888 unsigned int dir_index = dom_convert_dir_to_idx (dir);
889 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
890 vec<basic_block> bbs = vNULL;
892 gcc_checking_assert (dom_computed[dir_index]);
894 if (!son)
895 return vNULL;
897 bbs.safe_push ((basic_block) son->data);
898 for (ason = son->right; ason != son; ason = ason->right)
899 bbs.safe_push ((basic_block) ason->data);
901 return bbs;
904 /* Returns the list of basic blocks that are immediately dominated (in
905 direction DIR) by some block between N_REGION ones stored in REGION,
906 except for blocks in the REGION itself. */
908 vec<basic_block>
909 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
910 unsigned n_region)
912 unsigned i;
913 basic_block dom;
914 vec<basic_block> doms = vNULL;
916 for (i = 0; i < n_region; i++)
917 region[i]->flags |= BB_DUPLICATED;
918 for (i = 0; i < n_region; i++)
919 for (dom = first_dom_son (dir, region[i]);
920 dom;
921 dom = next_dom_son (dir, dom))
922 if (!(dom->flags & BB_DUPLICATED))
923 doms.safe_push (dom);
924 for (i = 0; i < n_region; i++)
925 region[i]->flags &= ~BB_DUPLICATED;
927 return doms;
930 /* Returns the list of basic blocks including BB dominated by BB, in the
931 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
932 produce a vector containing all dominated blocks. The vector will be sorted
933 in preorder. */
935 vec<basic_block>
936 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
938 vec<basic_block> bbs = vNULL;
939 unsigned i;
940 unsigned next_level_start;
942 i = 0;
943 bbs.safe_push (bb);
944 next_level_start = 1; /* = bbs.length (); */
948 basic_block son;
950 bb = bbs[i++];
951 for (son = first_dom_son (dir, bb);
952 son;
953 son = next_dom_son (dir, son))
954 bbs.safe_push (son);
956 if (i == next_level_start && --depth)
957 next_level_start = bbs.length ();
959 while (i < next_level_start);
961 return bbs;
964 /* Returns the list of basic blocks including BB dominated by BB, in the
965 direction DIR. The vector will be sorted in preorder. */
967 vec<basic_block>
968 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
970 return get_dominated_to_depth (dir, bb, 0);
973 /* Redirect all edges pointing to BB to TO. */
974 void
975 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
976 basic_block to)
978 unsigned int dir_index = dom_convert_dir_to_idx (dir);
979 struct et_node *bb_node, *to_node, *son;
981 bb_node = bb->dom[dir_index];
982 to_node = to->dom[dir_index];
984 gcc_checking_assert (dom_computed[dir_index]);
986 if (!bb_node->son)
987 return;
989 while (bb_node->son)
991 son = bb_node->son;
993 et_split (son);
994 et_set_father (son, to_node);
997 if (dom_computed[dir_index] == DOM_OK)
998 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1001 /* Find first basic block in the tree dominating both BB1 and BB2. */
1002 basic_block
1003 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1005 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1007 gcc_checking_assert (dom_computed[dir_index]);
1009 if (!bb1)
1010 return bb2;
1011 if (!bb2)
1012 return bb1;
1014 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
1018 /* Find the nearest common dominator for the basic blocks in BLOCKS,
1019 using dominance direction DIR. */
1021 basic_block
1022 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1024 unsigned i, first;
1025 bitmap_iterator bi;
1026 basic_block dom;
1028 first = bitmap_first_set_bit (blocks);
1029 dom = BASIC_BLOCK_FOR_FN (cfun, first);
1030 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
1031 if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
1032 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
1034 return dom;
1037 /* Given a dominator tree, we can determine whether one thing
1038 dominates another in constant time by using two DFS numbers:
1040 1. The number for when we visit a node on the way down the tree
1041 2. The number for when we visit a node on the way back up the tree
1043 You can view these as bounds for the range of dfs numbers the
1044 nodes in the subtree of the dominator tree rooted at that node
1045 will contain.
1047 The dominator tree is always a simple acyclic tree, so there are
1048 only three possible relations two nodes in the dominator tree have
1049 to each other:
1051 1. Node A is above Node B (and thus, Node A dominates node B)
1060 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
1061 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
1062 because we must hit A in the dominator tree *before* B on the walk
1063 down, and we will hit A *after* B on the walk back up
1065 2. Node A is below node B (and thus, node B dominates node A)
1074 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
1075 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
1077 This is because we must hit A in the dominator tree *after* B on
1078 the walk down, and we will hit A *before* B on the walk back up
1080 3. Node A and B are siblings (and thus, neither dominates the other)
1088 In the above case, DFS_Number_In of A will *always* be <=
1089 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
1090 DFS_Number_Out of B. This is because we will always finish the dfs
1091 walk of one of the subtrees before the other, and thus, the dfs
1092 numbers for one subtree can't intersect with the range of dfs
1093 numbers for the other subtree. If you swap A and B's position in
1094 the dominator tree, the comparison changes direction, but the point
1095 is that both comparisons will always go the same way if there is no
1096 dominance relationship.
1098 Thus, it is sufficient to write
1100 A_Dominates_B (node A, node B)
1102 return DFS_Number_In(A) <= DFS_Number_In(B)
1103 && DFS_Number_Out (A) >= DFS_Number_Out(B);
1106 A_Dominated_by_B (node A, node B)
1108 return DFS_Number_In(A) >= DFS_Number_In(B)
1109 && DFS_Number_Out (A) <= DFS_Number_Out(B);
1110 } */
1112 /* Return TRUE in case BB1 is dominated by BB2. */
1113 bool
1114 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
1116 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1117 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
1119 gcc_checking_assert (dom_computed[dir_index]);
1121 if (dom_computed[dir_index] == DOM_OK)
1122 return (n1->dfs_num_in >= n2->dfs_num_in
1123 && n1->dfs_num_out <= n2->dfs_num_out);
1125 return et_below (n1, n2);
1128 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
1130 unsigned
1131 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1133 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1134 struct et_node *n = bb->dom[dir_index];
1136 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1137 return n->dfs_num_in;
1140 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
1142 unsigned
1143 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1145 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1146 struct et_node *n = bb->dom[dir_index];
1148 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1149 return n->dfs_num_out;
1152 /* Verify invariants of dominator structure. */
1153 DEBUG_FUNCTION void
1154 verify_dominators (cdi_direction dir)
1156 gcc_assert (dom_info_available_p (dir));
1158 dom_info di (cfun, dir);
1159 di.calc_dfs_tree ();
1160 di.calc_idoms ();
1162 bool err = false;
1163 basic_block bb;
1164 FOR_EACH_BB_FN (bb, cfun)
1166 basic_block imm_bb = get_immediate_dominator (dir, bb);
1167 if (!imm_bb)
1169 error ("dominator of %d status unknown", bb->index);
1170 err = true;
1171 continue;
1174 basic_block imm_bb_correct = di.get_idom (bb);
1175 if (imm_bb != imm_bb_correct)
1177 error ("dominator of %d should be %d, not %d",
1178 bb->index, imm_bb_correct->index, imm_bb->index);
1179 err = true;
1183 gcc_assert (!err);
1186 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1187 assuming that dominators of other blocks are correct. We also use it to
1188 recompute the dominators in a restricted area, by iterating it until it
1189 reaches a fixed point. */
1191 basic_block
1192 recompute_dominator (enum cdi_direction dir, basic_block bb)
1194 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1195 basic_block dom_bb = NULL;
1196 edge e;
1197 edge_iterator ei;
1199 gcc_checking_assert (dom_computed[dir_index]);
1201 if (dir == CDI_DOMINATORS)
1203 FOR_EACH_EDGE (e, ei, bb->preds)
1205 if (!dominated_by_p (dir, e->src, bb))
1206 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1209 else
1211 FOR_EACH_EDGE (e, ei, bb->succs)
1213 if (!dominated_by_p (dir, e->dest, bb))
1214 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1218 return dom_bb;
1221 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1222 of BBS. We assume that all the immediate dominators except for those of the
1223 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1224 currently recorded immediate dominators of blocks in BBS really dominate the
1225 blocks. The basic blocks for that we determine the dominator are removed
1226 from BBS. */
1228 static void
1229 prune_bbs_to_update_dominators (vec<basic_block> bbs,
1230 bool conservative)
1232 unsigned i;
1233 bool single;
1234 basic_block bb, dom = NULL;
1235 edge_iterator ei;
1236 edge e;
1238 for (i = 0; bbs.iterate (i, &bb);)
1240 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1241 goto succeed;
1243 if (single_pred_p (bb))
1245 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1246 goto succeed;
1249 if (!conservative)
1250 goto fail;
1252 single = true;
1253 dom = NULL;
1254 FOR_EACH_EDGE (e, ei, bb->preds)
1256 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1257 continue;
1259 if (!dom)
1260 dom = e->src;
1261 else
1263 single = false;
1264 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1268 gcc_assert (dom != NULL);
1269 if (single
1270 || find_edge (dom, bb))
1272 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1273 goto succeed;
1276 fail:
1277 i++;
1278 continue;
1280 succeed:
1281 bbs.unordered_remove (i);
1285 /* Returns root of the dominance tree in the direction DIR that contains
1286 BB. */
1288 static basic_block
1289 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1291 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1294 /* See the comment in iterate_fix_dominators. Finds the immediate dominators
1295 for the sons of Y, found using the SON and BROTHER arrays representing
1296 the dominance tree of graph G. BBS maps the vertices of G to the basic
1297 blocks. */
1299 static void
1300 determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1301 int y, int *son, int *brother)
1303 bitmap gprime;
1304 int i, a, nc;
1305 vec<int> *sccs;
1306 basic_block bb, dom, ybb;
1307 unsigned si;
1308 edge e;
1309 edge_iterator ei;
1311 if (son[y] == -1)
1312 return;
1313 if (y == (int) bbs.length ())
1314 ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1315 else
1316 ybb = bbs[y];
1318 if (brother[son[y]] == -1)
1320 /* Handle the common case Y has just one son specially. */
1321 bb = bbs[son[y]];
1322 set_immediate_dominator (CDI_DOMINATORS, bb,
1323 recompute_dominator (CDI_DOMINATORS, bb));
1324 identify_vertices (g, y, son[y]);
1325 return;
1328 gprime = BITMAP_ALLOC (NULL);
1329 for (a = son[y]; a != -1; a = brother[a])
1330 bitmap_set_bit (gprime, a);
1332 nc = graphds_scc (g, gprime);
1333 BITMAP_FREE (gprime);
1335 /* ??? Needed to work around the pre-processor confusion with
1336 using a multi-argument template type as macro argument. */
1337 typedef vec<int> vec_int_heap;
1338 sccs = XCNEWVEC (vec_int_heap, nc);
1339 for (a = son[y]; a != -1; a = brother[a])
1340 sccs[g->vertices[a].component].safe_push (a);
1342 for (i = nc - 1; i >= 0; i--)
1344 dom = NULL;
1345 FOR_EACH_VEC_ELT (sccs[i], si, a)
1347 bb = bbs[a];
1348 FOR_EACH_EDGE (e, ei, bb->preds)
1350 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1351 continue;
1353 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1357 gcc_assert (dom != NULL);
1358 FOR_EACH_VEC_ELT (sccs[i], si, a)
1360 bb = bbs[a];
1361 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1365 for (i = 0; i < nc; i++)
1366 sccs[i].release ();
1367 free (sccs);
1369 for (a = son[y]; a != -1; a = brother[a])
1370 identify_vertices (g, y, a);
1373 /* Recompute dominance information for basic blocks in the set BBS. The
1374 function assumes that the immediate dominators of all the other blocks
1375 in CFG are correct, and that there are no unreachable blocks.
1377 If CONSERVATIVE is true, we additionally assume that all the ancestors of
1378 a block of BBS in the current dominance tree dominate it. */
1380 void
1381 iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
1382 bool conservative)
1384 unsigned i;
1385 basic_block bb, dom;
1386 struct graph *g;
1387 int n, y;
1388 size_t dom_i;
1389 edge e;
1390 edge_iterator ei;
1391 int *parent, *son, *brother;
1392 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1394 /* We only support updating dominators. There are some problems with
1395 updating postdominators (need to add fake edges from infinite loops
1396 and noreturn functions), and since we do not currently use
1397 iterate_fix_dominators for postdominators, any attempt to handle these
1398 problems would be unused, untested, and almost surely buggy. We keep
1399 the DIR argument for consistency with the rest of the dominator analysis
1400 interface. */
1401 gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
1403 /* The algorithm we use takes inspiration from the following papers, although
1404 the details are quite different from any of them:
1406 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1407 Dominator Tree of a Reducible Flowgraph
1408 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1409 dominator trees
1410 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1411 Algorithm
1413 First, we use the following heuristics to decrease the size of the BBS
1414 set:
1415 a) if BB has a single predecessor, then its immediate dominator is this
1416 predecessor
1417 additionally, if CONSERVATIVE is true:
1418 b) if all the predecessors of BB except for one (X) are dominated by BB,
1419 then X is the immediate dominator of BB
1420 c) if the nearest common ancestor of the predecessors of BB is X and
1421 X -> BB is an edge in CFG, then X is the immediate dominator of BB
1423 Then, we need to establish the dominance relation among the basic blocks
1424 in BBS. We split the dominance tree by removing the immediate dominator
1425 edges from BBS, creating a forest F. We form a graph G whose vertices
1426 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1427 X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1428 whose root is X. We then determine dominance tree of G. Note that
1429 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1430 In this step, we can use arbitrary algorithm to determine dominators.
1431 We decided to prefer the algorithm [3] to the algorithm of
1432 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1433 10 during gcc bootstrap), and [3] should perform better in this case.
1435 Finally, we need to determine the immediate dominators for the basic
1436 blocks of BBS. If the immediate dominator of X in G is Y, then
1437 the immediate dominator of X in CFG belongs to the tree of F rooted in
1438 Y. We process the dominator tree T of G recursively, starting from leaves.
1439 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1440 subtrees of the dominance tree of CFG rooted in X_i are already correct.
1441 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1442 the following observations:
1443 (i) the immediate dominator of all blocks in a strongly connected
1444 component of G' is the same
1445 (ii) if X has no predecessors in G', then the immediate dominator of X
1446 is the nearest common ancestor of the predecessors of X in the
1447 subtree of F rooted in Y
1448 Therefore, it suffices to find the topological ordering of G', and
1449 process the nodes X_i in this order using the rules (i) and (ii).
1450 Then, we contract all the nodes X_i with Y in G, so that the further
1451 steps work correctly. */
1453 if (!conservative)
1455 /* Split the tree now. If the idoms of blocks in BBS are not
1456 conservatively correct, setting the dominators using the
1457 heuristics in prune_bbs_to_update_dominators could
1458 create cycles in the dominance "tree", and cause ICE. */
1459 FOR_EACH_VEC_ELT (bbs, i, bb)
1460 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1463 prune_bbs_to_update_dominators (bbs, conservative);
1464 n = bbs.length ();
1466 if (n == 0)
1467 return;
1469 if (n == 1)
1471 bb = bbs[0];
1472 set_immediate_dominator (CDI_DOMINATORS, bb,
1473 recompute_dominator (CDI_DOMINATORS, bb));
1474 return;
1477 /* Construct the graph G. */
1478 hash_map<basic_block, int> map (251);
1479 FOR_EACH_VEC_ELT (bbs, i, bb)
1481 /* If the dominance tree is conservatively correct, split it now. */
1482 if (conservative)
1483 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1484 map.put (bb, i);
1486 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
1488 g = new_graph (n + 1);
1489 for (y = 0; y < g->n_vertices; y++)
1490 g->vertices[y].data = BITMAP_ALLOC (NULL);
1491 FOR_EACH_VEC_ELT (bbs, i, bb)
1493 FOR_EACH_EDGE (e, ei, bb->preds)
1495 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1496 if (dom == bb)
1497 continue;
1499 dom_i = *map.get (dom);
1501 /* Do not include parallel edges to G. */
1502 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1503 continue;
1505 add_edge (g, dom_i, i);
1508 for (y = 0; y < g->n_vertices; y++)
1509 BITMAP_FREE (g->vertices[y].data);
1511 /* Find the dominator tree of G. */
1512 son = XNEWVEC (int, n + 1);
1513 brother = XNEWVEC (int, n + 1);
1514 parent = XNEWVEC (int, n + 1);
1515 graphds_domtree (g, n, parent, son, brother);
1517 /* Finally, traverse the tree and find the immediate dominators. */
1518 for (y = n; son[y] != -1; y = son[y])
1519 continue;
1520 while (y != -1)
1522 determine_dominators_for_sons (g, bbs, y, son, brother);
1524 if (brother[y] != -1)
1526 y = brother[y];
1527 while (son[y] != -1)
1528 y = son[y];
1530 else
1531 y = parent[y];
1534 free (son);
1535 free (brother);
1536 free (parent);
1538 free_graph (g);
1541 void
1542 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1544 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1546 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1548 n_bbs_in_dom_tree[dir_index]++;
1550 bb->dom[dir_index] = et_new_tree (bb);
1552 if (dom_computed[dir_index] == DOM_OK)
1553 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1556 void
1557 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1559 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1561 gcc_checking_assert (dom_computed[dir_index]);
1563 et_free_tree (bb->dom[dir_index]);
1564 bb->dom[dir_index] = NULL;
1565 n_bbs_in_dom_tree[dir_index]--;
1567 if (dom_computed[dir_index] == DOM_OK)
1568 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1571 /* Returns the first son of BB in the dominator or postdominator tree
1572 as determined by DIR. */
1574 basic_block
1575 first_dom_son (enum cdi_direction dir, basic_block bb)
1577 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1578 struct et_node *son = bb->dom[dir_index]->son;
1580 return (basic_block) (son ? son->data : NULL);
1583 /* Returns the next dominance son after BB in the dominator or postdominator
1584 tree as determined by DIR, or NULL if it was the last one. */
1586 basic_block
1587 next_dom_son (enum cdi_direction dir, basic_block bb)
1589 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1590 struct et_node *next = bb->dom[dir_index]->right;
1592 return (basic_block) (next->father->son == next ? NULL : next->data);
1595 /* Return dominance availability for dominance info DIR. */
1597 enum dom_state
1598 dom_info_state (function *fn, enum cdi_direction dir)
1600 if (!fn->cfg)
1601 return DOM_NONE;
1603 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1604 return fn->cfg->x_dom_computed[dir_index];
1607 enum dom_state
1608 dom_info_state (enum cdi_direction dir)
1610 return dom_info_state (cfun, dir);
1613 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1615 void
1616 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1618 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1620 dom_computed[dir_index] = new_state;
1623 /* Returns true if dominance information for direction DIR is available. */
1625 bool
1626 dom_info_available_p (function *fn, enum cdi_direction dir)
1628 return dom_info_state (fn, dir) != DOM_NONE;
1631 bool
1632 dom_info_available_p (enum cdi_direction dir)
1634 return dom_info_available_p (cfun, dir);
1637 DEBUG_FUNCTION void
1638 debug_dominance_info (enum cdi_direction dir)
1640 basic_block bb, bb2;
1641 FOR_EACH_BB_FN (bb, cfun)
1642 if ((bb2 = get_immediate_dominator (dir, bb)))
1643 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1646 /* Prints to stderr representation of the dominance tree (for direction DIR)
1647 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1648 the first line of the output is not indented. */
1650 static void
1651 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1652 unsigned indent, bool indent_first)
1654 basic_block son;
1655 unsigned i;
1656 bool first = true;
1658 if (indent_first)
1659 for (i = 0; i < indent; i++)
1660 fprintf (stderr, "\t");
1661 fprintf (stderr, "%d\t", root->index);
1663 for (son = first_dom_son (dir, root);
1664 son;
1665 son = next_dom_son (dir, son))
1667 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1668 first = false;
1671 if (first)
1672 fprintf (stderr, "\n");
1675 /* Prints to stderr representation of the dominance tree (for direction DIR)
1676 rooted in ROOT. */
1678 DEBUG_FUNCTION void
1679 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1681 debug_dominance_tree_1 (dir, root, 0, false);