1 /* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000, 2003, 2004, 2005 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 2, or (at your option)
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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This file implements the well known algorithm from Lengauer and Tarjan
23 to compute the dominators in a control flow graph. A basic block D is said
24 to dominate another block X, when all paths from the entry node of the CFG
25 to X go also over D. The dominance relation is a transitive reflexive
26 relation and its minimal transitive reduction is a tree, called the
27 dominator tree. So for each block X besides the entry block exists a
28 block I(X), called the immediate dominator of X, which is the parent of X
29 in the dominator tree.
31 The algorithm computes this dominator tree implicitly by computing for
32 each block its immediate dominator. We use tree balancing and path
33 compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
34 slowly growing functional inverse of the Ackerman function. */
38 #include "coretypes.h"
41 #include "hard-reg-set.h"
43 #include "basic-block.h"
45 #include "et-forest.h"
48 #include "pointer-set.h"
51 /* Whether the dominators and the postdominators are available. */
52 static enum dom_state dom_computed[2];
54 /* We name our nodes with integers, beginning with 1. Zero is reserved for
55 'undefined' or 'end of list'. The name of each node is given by the dfs
56 number of the corresponding basic block. Please note, that we include the
57 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
58 support multiple entry points. Its dfs number is of course 1. */
60 /* Type of Basic Block aka. TBB */
61 typedef unsigned int TBB;
63 /* We work in a poor-mans object oriented fashion, and carry an instance of
64 this structure through all our 'methods'. It holds various arrays
65 reflecting the (sub)structure of the flowgraph. Most of them are of type
66 TBB and are also indexed by TBB. */
70 /* The parent of a node in the DFS tree. */
72 /* For a node x key[x] is roughly the node nearest to the root from which
73 exists a way to x only over nodes behind x. Such a node is also called
76 /* The value in path_min[x] is the node y on the path from x to the root of
77 the tree x is in with the smallest key[y]. */
79 /* bucket[x] points to the first node of the set of nodes having x as key. */
81 /* And next_bucket[x] points to the next node. */
83 /* After the algorithm is done, dom[x] contains the immediate dominator
87 /* The following few fields implement the structures needed for disjoint
89 /* set_chain[x] is the next node on the path from x to the representant
90 of the set containing x. If set_chain[x]==0 then x is a root. */
92 /* set_size[x] is the number of elements in the set named by x. */
93 unsigned int *set_size;
94 /* set_child[x] is used for balancing the tree representing a set. It can
95 be understood as the next sibling of x. */
98 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
99 number of that node in DFS order counted from 1. This is an index
100 into most of the other arrays in this structure. */
102 /* If x is the DFS-index of a node which corresponds with a basic block,
103 dfs_to_bb[x] is that basic block. Note, that in our structure there are
104 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
105 is true for every basic block bb, but not the opposite. */
106 basic_block *dfs_to_bb;
108 /* This is the next free DFS number when creating the DFS tree. */
110 /* The number of nodes in the DFS tree (==dfsnum-1). */
113 /* Blocks with bits set here have a fake edge to EXIT. These are used
114 to turn a DFS forest into a proper tree. */
115 bitmap fake_exit_edge;
118 static void init_dom_info (struct dom_info *, enum cdi_direction);
119 static void free_dom_info (struct dom_info *);
120 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
121 static void calc_dfs_tree (struct dom_info *, bool);
122 static void compress (struct dom_info *, TBB);
123 static TBB eval (struct dom_info *, TBB);
124 static void link_roots (struct dom_info *, TBB, TBB);
125 static void calc_idoms (struct dom_info *, bool);
126 void debug_dominance_info (enum cdi_direction);
127 void debug_dominance_tree (enum cdi_direction, basic_block);
129 /* Keeps track of the*/
130 static unsigned n_bbs_in_dom_tree[2];
132 /* Helper macro for allocating and initializing an array,
133 for aesthetic reasons. */
134 #define init_ar(var, type, num, content) \
137 unsigned int i = 1; /* Catch content == i. */ \
139 (var) = XCNEWVEC (type, num); \
142 (var) = XNEWVEC (type, (num)); \
143 for (i = 0; i < num; i++) \
144 (var)[i] = (content); \
149 /* Allocate all needed memory in a pessimistic fashion (so we round up).
150 This initializes the contents of DI, which already must be allocated. */
153 init_dom_info (struct dom_info *di, enum cdi_direction dir)
155 unsigned int num = n_basic_blocks;
156 init_ar (di->dfs_parent, TBB, num, 0);
157 init_ar (di->path_min, TBB, num, i);
158 init_ar (di->key, TBB, num, i);
159 init_ar (di->dom, TBB, num, 0);
161 init_ar (di->bucket, TBB, num, 0);
162 init_ar (di->next_bucket, TBB, num, 0);
164 init_ar (di->set_chain, TBB, num, 0);
165 init_ar (di->set_size, unsigned int, num, 1);
166 init_ar (di->set_child, TBB, num, 0);
168 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
169 init_ar (di->dfs_to_bb, basic_block, num, 0);
177 di->fake_exit_edge = NULL;
179 case CDI_POST_DOMINATORS:
180 di->fake_exit_edge = BITMAP_ALLOC (NULL);
190 /* Map dominance calculation type to array index used for various
191 dominance information arrays. This version is simple -- it will need
192 to be modified, obviously, if additional values are added to
196 dom_convert_dir_to_idx (enum cdi_direction dir)
198 gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
202 /* Free all allocated memory in DI, but not DI itself. */
205 free_dom_info (struct dom_info *di)
207 free (di->dfs_parent);
212 free (di->next_bucket);
213 free (di->set_chain);
215 free (di->set_child);
216 free (di->dfs_order);
217 free (di->dfs_to_bb);
218 BITMAP_FREE (di->fake_exit_edge);
221 /* The nonrecursive variant of creating a DFS tree. DI is our working
222 structure, BB the starting basic block for this tree and REVERSE
223 is true, if predecessors should be visited instead of successors of a
224 node. After this is done all nodes reachable from BB were visited, have
225 assigned their dfs number and are linked together to form a tree. */
228 calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
230 /* We call this _only_ if bb is not already visited. */
232 TBB child_i, my_i = 0;
233 edge_iterator *stack;
234 edge_iterator ei, einext;
236 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
238 basic_block en_block;
240 basic_block ex_block;
242 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
245 /* Initialize our border blocks, and the first edge. */
248 ei = ei_start (bb->preds);
249 en_block = EXIT_BLOCK_PTR;
250 ex_block = ENTRY_BLOCK_PTR;
254 ei = ei_start (bb->succs);
255 en_block = ENTRY_BLOCK_PTR;
256 ex_block = EXIT_BLOCK_PTR;
259 /* When the stack is empty we break out of this loop. */
264 /* This loop traverses edges e in depth first manner, and fills the
266 while (!ei_end_p (ei))
270 /* Deduce from E the current and the next block (BB and BN), and the
276 /* If the next node BN is either already visited or a border
277 block the current edge is useless, and simply overwritten
278 with the next edge out of the current node. */
279 if (bn == ex_block || di->dfs_order[bn->index])
285 einext = ei_start (bn->preds);
290 if (bn == ex_block || di->dfs_order[bn->index])
296 einext = ei_start (bn->succs);
299 gcc_assert (bn != en_block);
301 /* Fill the DFS tree info calculatable _before_ recursing. */
303 my_i = di->dfs_order[bb->index];
305 my_i = di->dfs_order[last_basic_block];
306 child_i = di->dfs_order[bn->index] = di->dfsnum++;
307 di->dfs_to_bb[child_i] = bn;
308 di->dfs_parent[child_i] = my_i;
310 /* Save the current point in the CFG on the stack, and recurse. */
319 /* OK. The edge-list was exhausted, meaning normally we would
320 end the recursion. After returning from the recursive call,
321 there were (may be) other statements which were run after a
322 child node was completely considered by DFS. Here is the
323 point to do it in the non-recursive variant.
324 E.g. The block just completed is in e->dest for forward DFS,
325 the block not yet completed (the parent of the one above)
326 in e->src. This could be used e.g. for computing the number of
327 descendants or the tree depth. */
333 /* The main entry for calculating the DFS tree or forest. DI is our working
334 structure and REVERSE is true, if we are interested in the reverse flow
335 graph. In that case the result is not necessarily a tree but a forest,
336 because there may be nodes from which the EXIT_BLOCK is unreachable. */
339 calc_dfs_tree (struct dom_info *di, bool reverse)
341 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
342 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
343 di->dfs_order[last_basic_block] = di->dfsnum;
344 di->dfs_to_bb[di->dfsnum] = begin;
347 calc_dfs_tree_nonrec (di, begin, reverse);
351 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
352 They are reverse-unreachable. In the dom-case we disallow such
353 nodes, but in post-dom we have to deal with them.
355 There are two situations in which this occurs. First, noreturn
356 functions. Second, infinite loops. In the first case we need to
357 pretend that there is an edge to the exit block. In the second
358 case, we wind up with a forest. We need to process all noreturn
359 blocks before we know if we've got any infinite loops. */
362 bool saw_unconnected = false;
364 FOR_EACH_BB_REVERSE (b)
366 if (EDGE_COUNT (b->succs) > 0)
368 if (di->dfs_order[b->index] == 0)
369 saw_unconnected = true;
372 bitmap_set_bit (di->fake_exit_edge, b->index);
373 di->dfs_order[b->index] = di->dfsnum;
374 di->dfs_to_bb[di->dfsnum] = b;
375 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
377 calc_dfs_tree_nonrec (di, b, reverse);
382 FOR_EACH_BB_REVERSE (b)
384 if (di->dfs_order[b->index])
386 bitmap_set_bit (di->fake_exit_edge, b->index);
387 di->dfs_order[b->index] = di->dfsnum;
388 di->dfs_to_bb[di->dfsnum] = b;
389 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
391 calc_dfs_tree_nonrec (di, b, reverse);
396 di->nodes = di->dfsnum - 1;
398 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
399 gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
402 /* Compress the path from V to the root of its set and update path_min at the
403 same time. After compress(di, V) set_chain[V] is the root of the set V is
404 in and path_min[V] is the node with the smallest key[] value on the path
405 from V to that root. */
408 compress (struct dom_info *di, TBB v)
410 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
411 greater than 5 even for huge graphs (I've not seen call depth > 4).
412 Also performance wise compress() ranges _far_ behind eval(). */
413 TBB parent = di->set_chain[v];
414 if (di->set_chain[parent])
416 compress (di, parent);
417 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
418 di->path_min[v] = di->path_min[parent];
419 di->set_chain[v] = di->set_chain[parent];
423 /* Compress the path from V to the set root of V if needed (when the root has
424 changed since the last call). Returns the node with the smallest key[]
425 value on the path from V to the root. */
428 eval (struct dom_info *di, TBB v)
430 /* The representant of the set V is in, also called root (as the set
431 representation is a tree). */
432 TBB rep = di->set_chain[v];
434 /* V itself is the root. */
436 return di->path_min[v];
438 /* Compress only if necessary. */
439 if (di->set_chain[rep])
442 rep = di->set_chain[v];
445 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
446 return di->path_min[v];
448 return di->path_min[rep];
451 /* This essentially merges the two sets of V and W, giving a single set with
452 the new root V. The internal representation of these disjoint sets is a
453 balanced tree. Currently link(V,W) is only used with V being the parent
457 link_roots (struct dom_info *di, TBB v, TBB w)
461 /* Rebalance the tree. */
462 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
464 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
465 >= 2 * di->set_size[di->set_child[s]])
467 di->set_chain[di->set_child[s]] = s;
468 di->set_child[s] = di->set_child[di->set_child[s]];
472 di->set_size[di->set_child[s]] = di->set_size[s];
473 s = di->set_chain[s] = di->set_child[s];
477 di->path_min[s] = di->path_min[w];
478 di->set_size[v] += di->set_size[w];
479 if (di->set_size[v] < 2 * di->set_size[w])
482 s = di->set_child[v];
483 di->set_child[v] = tmp;
486 /* Merge all subtrees. */
489 di->set_chain[s] = v;
490 s = di->set_child[s];
494 /* This calculates the immediate dominators (or post-dominators if REVERSE is
495 true). DI is our working structure and should hold the DFS forest.
496 On return the immediate dominator to node V is in di->dom[V]. */
499 calc_idoms (struct dom_info *di, bool reverse)
502 basic_block en_block;
503 edge_iterator ei, einext;
506 en_block = EXIT_BLOCK_PTR;
508 en_block = ENTRY_BLOCK_PTR;
510 /* Go backwards in DFS order, to first look at the leafs. */
514 basic_block bb = di->dfs_to_bb[v];
517 par = di->dfs_parent[v];
520 ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
524 /* If this block has a fake edge to exit, process that first. */
525 if (bitmap_bit_p (di->fake_exit_edge, bb->index))
529 goto do_fake_exit_edge;
533 /* Search all direct predecessors for the smallest node with a path
534 to them. That way we have the smallest node with also a path to
535 us only over nodes behind us. In effect we search for our
537 while (!ei_end_p (ei))
543 b = (reverse) ? e->dest : e->src;
550 k1 = di->dfs_order[last_basic_block];
553 k1 = di->dfs_order[b->index];
555 /* Call eval() only if really needed. If k1 is above V in DFS tree,
556 then we know, that eval(k1) == k1 and key[k1] == k1. */
558 k1 = di->key[eval (di, k1)];
566 link_roots (di, par, v);
567 di->next_bucket[v] = di->bucket[k];
570 /* Transform semidominators into dominators. */
571 for (w = di->bucket[par]; w; w = di->next_bucket[w])
574 if (di->key[k] < di->key[w])
579 /* We don't need to cleanup next_bucket[]. */
584 /* Explicitly define the dominators. */
586 for (v = 2; v <= di->nodes; v++)
587 if (di->dom[v] != di->key[v])
588 di->dom[v] = di->dom[di->dom[v]];
591 /* Assign dfs numbers starting from NUM to NODE and its sons. */
594 assign_dfs_numbers (struct et_node *node, int *num)
598 node->dfs_num_in = (*num)++;
602 assign_dfs_numbers (node->son, num);
603 for (son = node->son->right; son != node->son; son = son->right)
604 assign_dfs_numbers (son, num);
607 node->dfs_num_out = (*num)++;
610 /* Compute the data necessary for fast resolving of dominator queries in a
611 static dominator tree. */
614 compute_dom_fast_query (enum cdi_direction dir)
618 unsigned int dir_index = dom_convert_dir_to_idx (dir);
620 gcc_assert (dom_info_available_p (dir));
622 if (dom_computed[dir_index] == DOM_OK)
627 if (!bb->dom[dir_index]->father)
628 assign_dfs_numbers (bb->dom[dir_index], &num);
631 dom_computed[dir_index] = DOM_OK;
634 /* The main entry point into this module. DIR is set depending on whether
635 we want to compute dominators or postdominators. */
638 calculate_dominance_info (enum cdi_direction dir)
642 unsigned int dir_index = dom_convert_dir_to_idx (dir);
643 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
645 if (dom_computed[dir_index] == DOM_OK)
648 timevar_push (TV_DOMINANCE);
649 if (!dom_info_available_p (dir))
651 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
655 b->dom[dir_index] = et_new_tree (b);
657 n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
659 init_dom_info (&di, dir);
660 calc_dfs_tree (&di, reverse);
661 calc_idoms (&di, reverse);
665 TBB d = di.dom[di.dfs_order[b->index]];
668 et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
672 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
675 compute_dom_fast_query (dir);
677 timevar_pop (TV_DOMINANCE);
680 /* Free dominance information for direction DIR. */
682 free_dominance_info (enum cdi_direction dir)
685 unsigned int dir_index = dom_convert_dir_to_idx (dir);
687 if (!dom_info_available_p (dir))
692 et_free_tree_force (bb->dom[dir_index]);
693 bb->dom[dir_index] = NULL;
697 n_bbs_in_dom_tree[dir_index] = 0;
699 dom_computed[dir_index] = DOM_NONE;
702 /* Return the immediate dominator of basic block BB. */
704 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
706 unsigned int dir_index = dom_convert_dir_to_idx (dir);
707 struct et_node *node = bb->dom[dir_index];
709 gcc_assert (dom_computed[dir_index]);
714 return node->father->data;
717 /* Set the immediate dominator of the block possibly removing
718 existing edge. NULL can be used to remove any edge. */
720 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
721 basic_block dominated_by)
723 unsigned int dir_index = dom_convert_dir_to_idx (dir);
724 struct et_node *node = bb->dom[dir_index];
726 gcc_assert (dom_computed[dir_index]);
730 if (node->father->data == dominated_by)
736 et_set_father (node, dominated_by->dom[dir_index]);
738 if (dom_computed[dir_index] == DOM_OK)
739 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
742 /* Returns the list of basic blocks immediately dominated by BB, in the
744 VEC (basic_block, heap) *
745 get_dominated_by (enum cdi_direction dir, basic_block bb)
748 unsigned int dir_index = dom_convert_dir_to_idx (dir);
749 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
750 VEC (basic_block, heap) *bbs = NULL;
752 gcc_assert (dom_computed[dir_index]);
757 VEC_safe_push (basic_block, heap, bbs, son->data);
758 for (ason = son->right, n = 1; ason != son; ason = ason->right)
759 VEC_safe_push (basic_block, heap, bbs, ason->data);
764 /* Returns the list of basic blocks that are immediately dominated (in
765 direction DIR) by some block between N_REGION ones stored in REGION,
766 except for blocks in the REGION itself. */
768 VEC (basic_block, heap) *
769 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
774 VEC (basic_block, heap) *doms = NULL;
776 for (i = 0; i < n_region; i++)
777 region[i]->flags |= BB_DUPLICATED;
778 for (i = 0; i < n_region; i++)
779 for (dom = first_dom_son (dir, region[i]);
781 dom = next_dom_son (dir, dom))
782 if (!(dom->flags & BB_DUPLICATED))
783 VEC_safe_push (basic_block, heap, doms, dom);
784 for (i = 0; i < n_region; i++)
785 region[i]->flags &= ~BB_DUPLICATED;
790 /* Redirect all edges pointing to BB to TO. */
792 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
795 unsigned int dir_index = dom_convert_dir_to_idx (dir);
796 struct et_node *bb_node, *to_node, *son;
798 bb_node = bb->dom[dir_index];
799 to_node = to->dom[dir_index];
801 gcc_assert (dom_computed[dir_index]);
811 et_set_father (son, to_node);
814 if (dom_computed[dir_index] == DOM_OK)
815 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
818 /* Find first basic block in the tree dominating both BB1 and BB2. */
820 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
822 unsigned int dir_index = dom_convert_dir_to_idx (dir);
824 gcc_assert (dom_computed[dir_index]);
831 return et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
835 /* Find the nearest common dominator for the basic blocks in BLOCKS,
836 using dominance direction DIR. */
839 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
845 first = bitmap_first_set_bit (blocks);
846 dom = BASIC_BLOCK (first);
847 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
848 if (dom != BASIC_BLOCK (i))
849 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
854 /* Given a dominator tree, we can determine whether one thing
855 dominates another in constant time by using two DFS numbers:
857 1. The number for when we visit a node on the way down the tree
858 2. The number for when we visit a node on the way back up the tree
860 You can view these as bounds for the range of dfs numbers the
861 nodes in the subtree of the dominator tree rooted at that node
864 The dominator tree is always a simple acyclic tree, so there are
865 only three possible relations two nodes in the dominator tree have
868 1. Node A is above Node B (and thus, Node A dominates node B)
877 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
878 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
879 because we must hit A in the dominator tree *before* B on the walk
880 down, and we will hit A *after* B on the walk back up
882 2. Node A is below node B (and thus, node B dominates node A)
891 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
892 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
894 This is because we must hit A in the dominator tree *after* B on
895 the walk down, and we will hit A *before* B on the walk back up
897 3. Node A and B are siblings (and thus, neither dominates the other)
905 In the above case, DFS_Number_In of A will *always* be <=
906 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
907 DFS_Number_Out of B. This is because we will always finish the dfs
908 walk of one of the subtrees before the other, and thus, the dfs
909 numbers for one subtree can't intersect with the range of dfs
910 numbers for the other subtree. If you swap A and B's position in
911 the dominator tree, the comparison changes direction, but the point
912 is that both comparisons will always go the same way if there is no
913 dominance relationship.
915 Thus, it is sufficient to write
917 A_Dominates_B (node A, node B)
919 return DFS_Number_In(A) <= DFS_Number_In(B)
920 && DFS_Number_Out (A) >= DFS_Number_Out(B);
923 A_Dominated_by_B (node A, node B)
925 return DFS_Number_In(A) >= DFS_Number_In(A)
926 && DFS_Number_Out (A) <= DFS_Number_Out(B);
929 /* Return TRUE in case BB1 is dominated by BB2. */
931 dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
933 unsigned int dir_index = dom_convert_dir_to_idx (dir);
934 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
936 gcc_assert (dom_computed[dir_index]);
938 if (dom_computed[dir_index] == DOM_OK)
939 return (n1->dfs_num_in >= n2->dfs_num_in
940 && n1->dfs_num_out <= n2->dfs_num_out);
942 return et_below (n1, n2);
945 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
948 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
950 unsigned int dir_index = dom_convert_dir_to_idx (dir);
951 struct et_node *n = bb->dom[dir_index];
953 gcc_assert (dom_computed[dir_index] == DOM_OK);
954 return n->dfs_num_in;
957 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
960 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
962 unsigned int dir_index = dom_convert_dir_to_idx (dir);
963 struct et_node *n = bb->dom[dir_index];
965 gcc_assert (dom_computed[dir_index] == DOM_OK);
966 return n->dfs_num_out;
969 /* Verify invariants of dominator structure. */
971 verify_dominators (enum cdi_direction dir)
974 basic_block bb, imm_bb, imm_bb_correct;
976 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
978 gcc_assert (dom_info_available_p (dir));
980 init_dom_info (&di, dir);
981 calc_dfs_tree (&di, reverse);
982 calc_idoms (&di, reverse);
986 imm_bb = get_immediate_dominator (dir, bb);
989 error ("dominator of %d status unknown", bb->index);
993 imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
994 if (imm_bb != imm_bb_correct)
996 error ("dominator of %d should be %d, not %d",
997 bb->index, imm_bb_correct->index, imm_bb->index);
1002 free_dom_info (&di);
1006 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1007 assuming that dominators of other blocks are correct. We also use it to
1008 recompute the dominators in a restricted area, by iterating it until it
1009 reaches a fixed point. */
1012 recompute_dominator (enum cdi_direction dir, basic_block bb)
1014 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1015 basic_block dom_bb = NULL;
1019 gcc_assert (dom_computed[dir_index]);
1021 if (dir == CDI_DOMINATORS)
1023 FOR_EACH_EDGE (e, ei, bb->preds)
1025 if (!dominated_by_p (dir, e->src, bb))
1026 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1031 FOR_EACH_EDGE (e, ei, bb->succs)
1033 if (!dominated_by_p (dir, e->dest, bb))
1034 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1041 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1042 of BBS. We assume that all the immediate dominators except for those of the
1043 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1044 currently recorded immediate dominators of blocks in BBS really dominate the
1045 blocks. The basic blocks for that we determine the dominator are removed
1049 prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
1054 basic_block bb, dom = NULL;
1058 for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
1060 if (bb == ENTRY_BLOCK_PTR)
1063 if (single_pred_p (bb))
1065 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1074 FOR_EACH_EDGE (e, ei, bb->preds)
1076 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1084 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1088 gcc_assert (dom != NULL);
1090 || find_edge (dom, bb))
1092 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1101 VEC_unordered_remove (basic_block, bbs, i);
1105 /* Returns root of the dominance tree in the direction DIR that contains
1109 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1111 return et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1114 /* See the comment in iterate_fix_dominators. Finds the immediate dominators
1115 for the sons of Y, found using the SON and BROTHER arrays representing
1116 the dominance tree of graph G. BBS maps the vertices of G to the basic
1120 determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
1121 int y, int *son, int *brother)
1125 VEC (int, heap) **sccs;
1126 basic_block bb, dom, ybb;
1133 if (y == (int) VEC_length (basic_block, bbs))
1134 ybb = ENTRY_BLOCK_PTR;
1136 ybb = VEC_index (basic_block, bbs, y);
1138 if (brother[son[y]] == -1)
1140 /* Handle the common case Y has just one son specially. */
1141 bb = VEC_index (basic_block, bbs, son[y]);
1142 set_immediate_dominator (CDI_DOMINATORS, bb,
1143 recompute_dominator (CDI_DOMINATORS, bb));
1144 identify_vertices (g, y, son[y]);
1148 gprime = BITMAP_ALLOC (NULL);
1149 for (a = son[y]; a != -1; a = brother[a])
1150 bitmap_set_bit (gprime, a);
1152 nc = graphds_scc (g, gprime);
1153 BITMAP_FREE (gprime);
1155 sccs = XCNEWVEC (VEC (int, heap) *, nc);
1156 for (a = son[y]; a != -1; a = brother[a])
1157 VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
1159 for (i = nc - 1; i >= 0; i--)
1162 for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1164 bb = VEC_index (basic_block, bbs, a);
1165 FOR_EACH_EDGE (e, ei, bb->preds)
1167 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1170 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1174 gcc_assert (dom != NULL);
1175 for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
1177 bb = VEC_index (basic_block, bbs, a);
1178 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1182 for (i = 0; i < nc; i++)
1183 VEC_free (int, heap, sccs[i]);
1186 for (a = son[y]; a != -1; a = brother[a])
1187 identify_vertices (g, y, a);
1190 /* Recompute dominance information for basic blocks in the set BBS. The
1191 function assumes that the immediate dominators of all the other blocks
1192 in CFG are correct, and that there are no unreachable blocks.
1194 If CONSERVATIVE is true, we additionally assume that all the ancestors of
1195 a block of BBS in the current dominance tree dominate it. */
1198 iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
1202 basic_block bb, dom;
1208 struct pointer_map_t *map;
1209 int *parent, *son, *brother;
1210 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1212 /* We only support updating dominators. There are some problems with
1213 updating postdominators (need to add fake edges from infinite loops
1214 and noreturn functions), and since we do not currently use
1215 iterate_fix_dominators for postdominators, any attempt to handle these
1216 problems would be unused, untested, and almost surely buggy. We keep
1217 the DIR argument for consistency with the rest of the dominator analysis
1219 gcc_assert (dir == CDI_DOMINATORS);
1220 gcc_assert (dom_computed[dir_index]);
1222 /* The algorithm we use takes inspiration from the following papers, although
1223 the details are quite different from any of them:
1225 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1226 Dominator Tree of a Reducible Flowgraph
1227 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1229 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1232 First, we use the following heuristics to decrease the size of the BBS
1234 a) if BB has a single predecessor, then its immediate dominator is this
1236 additionally, if CONSERVATIVE is true:
1237 b) if all the predecessors of BB except for one (X) are dominated by BB,
1238 then X is the immediate dominator of BB
1239 c) if the nearest common ancestor of the predecessors of BB is X and
1240 X -> BB is an edge in CFG, then X is the immediate dominator of BB
1242 Then, we need to establish the dominance relation among the basic blocks
1243 in BBS. We split the dominance tree by removing the immediate dominator
1244 edges from BBS, creating a forrest F. We form a graph G whose vertices
1245 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1246 X' -> Y in CFG such that X' belongs to the tree of the dominance forrest
1247 whose root is X. We then determine dominance tree of G. Note that
1248 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1249 In this step, we can use arbitrary algorithm to determine dominators.
1250 We decided to prefer the algorithm [3] to the algorithm of
1251 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1252 10 during gcc bootstrap), and [3] should perform better in this case.
1254 Finally, we need to determine the immediate dominators for the basic
1255 blocks of BBS. If the immediate dominator of X in G is Y, then
1256 the immediate dominator of X in CFG belongs to the tree of F rooted in
1257 Y. We process the dominator tree T of G recursively, starting from leaves.
1258 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1259 subtrees of the dominance tree of CFG rooted in X_i are already correct.
1260 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1261 the following observations:
1262 (i) the immediate dominator of all blocks in a strongly connected
1263 component of G' is the same
1264 (ii) if X has no predecessors in G', then the immediate dominator of X
1265 is the nearest common ancestor of the predecessors of X in the
1266 subtree of F rooted in Y
1267 Therefore, it suffices to find the topological ordering of G', and
1268 process the nodes X_i in this order using the rules (i) and (ii).
1269 Then, we contract all the nodes X_i with Y in G, so that the further
1270 steps work correctly. */
1274 /* Split the tree now. If the idoms of blocks in BBS are not
1275 conservatively correct, setting the dominators using the
1276 heuristics in prune_bbs_to_update_dominators could
1277 create cycles in the dominance "tree", and cause ICE. */
1278 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1279 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1282 prune_bbs_to_update_dominators (bbs, conservative);
1283 n = VEC_length (basic_block, bbs);
1290 bb = VEC_index (basic_block, bbs, 0);
1291 set_immediate_dominator (CDI_DOMINATORS, bb,
1292 recompute_dominator (CDI_DOMINATORS, bb));
1296 /* Construct the graph G. */
1297 map = pointer_map_create ();
1298 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1300 /* If the dominance tree is conservatively correct, split it now. */
1302 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1303 *pointer_map_insert (map, bb) = (void *) (size_t) i;
1305 *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
1307 g = new_graph (n + 1);
1308 for (y = 0; y < g->n_vertices; y++)
1309 g->vertices[y].data = BITMAP_ALLOC (NULL);
1310 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
1312 FOR_EACH_EDGE (e, ei, bb->preds)
1314 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1318 dom_i = (size_t) *pointer_map_contains (map, dom);
1320 /* Do not include parallel edges to G. */
1321 if (bitmap_bit_p (g->vertices[dom_i].data, i))
1324 bitmap_set_bit (g->vertices[dom_i].data, i);
1325 add_edge (g, dom_i, i);
1328 for (y = 0; y < g->n_vertices; y++)
1329 BITMAP_FREE (g->vertices[y].data);
1330 pointer_map_destroy (map);
1332 /* Find the dominator tree of G. */
1333 son = XNEWVEC (int, n + 1);
1334 brother = XNEWVEC (int, n + 1);
1335 parent = XNEWVEC (int, n + 1);
1336 graphds_domtree (g, n, parent, son, brother);
1338 /* Finally, traverse the tree and find the immediate dominators. */
1339 for (y = n; son[y] != -1; y = son[y])
1343 determine_dominators_for_sons (g, bbs, y, son, brother);
1345 if (brother[y] != -1)
1348 while (son[y] != -1)
1363 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1365 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1367 gcc_assert (dom_computed[dir_index]);
1368 gcc_assert (!bb->dom[dir_index]);
1370 n_bbs_in_dom_tree[dir_index]++;
1372 bb->dom[dir_index] = et_new_tree (bb);
1374 if (dom_computed[dir_index] == DOM_OK)
1375 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1379 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1381 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1383 gcc_assert (dom_computed[dir_index]);
1385 et_free_tree (bb->dom[dir_index]);
1386 bb->dom[dir_index] = NULL;
1387 n_bbs_in_dom_tree[dir_index]--;
1389 if (dom_computed[dir_index] == DOM_OK)
1390 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1393 /* Returns the first son of BB in the dominator or postdominator tree
1394 as determined by DIR. */
1397 first_dom_son (enum cdi_direction dir, basic_block bb)
1399 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1400 struct et_node *son = bb->dom[dir_index]->son;
1402 return son ? son->data : NULL;
1405 /* Returns the next dominance son after BB in the dominator or postdominator
1406 tree as determined by DIR, or NULL if it was the last one. */
1409 next_dom_son (enum cdi_direction dir, basic_block bb)
1411 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1412 struct et_node *next = bb->dom[dir_index]->right;
1414 return next->father->son == next ? NULL : next->data;
1417 /* Return dominance availability for dominance info DIR. */
1420 dom_info_state (enum cdi_direction dir)
1422 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1424 return dom_computed[dir_index];
1427 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1430 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1432 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1434 dom_computed[dir_index] = new_state;
1437 /* Returns true if dominance information for direction DIR is available. */
1440 dom_info_available_p (enum cdi_direction dir)
1442 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1444 return dom_computed[dir_index] != DOM_NONE;
1448 debug_dominance_info (enum cdi_direction dir)
1450 basic_block bb, bb2;
1452 if ((bb2 = get_immediate_dominator (dir, bb)))
1453 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1456 /* Prints to stderr representation of the dominance tree (for direction DIR)
1457 rooted in ROOT, indented by INDENT tabelators. If INDENT_FIRST is false,
1458 the first line of the output is not indented. */
1461 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1462 unsigned indent, bool indent_first)
1469 for (i = 0; i < indent; i++)
1470 fprintf (stderr, "\t");
1471 fprintf (stderr, "%d\t", root->index);
1473 for (son = first_dom_son (dir, root);
1475 son = next_dom_son (dir, son))
1477 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1482 fprintf (stderr, "\n");
1485 /* Prints to stderr representation of the dominance tree (for direction DIR)
1489 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1491 debug_dominance_tree_1 (dir, root, 0, false);