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, 59 Temple Place - Suite 330, 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"
47 /* Whether the dominators and the postdominators are available. */
48 enum dom_state dom_computed
[2];
50 /* We name our nodes with integers, beginning with 1. Zero is reserved for
51 'undefined' or 'end of list'. The name of each node is given by the dfs
52 number of the corresponding basic block. Please note, that we include the
53 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
54 support multiple entry points. As it has no real basic block index we use
55 'last_basic_block' for that. Its dfs number is of course 1. */
57 /* Type of Basic Block aka. TBB */
58 typedef unsigned int TBB
;
60 /* We work in a poor-mans object oriented fashion, and carry an instance of
61 this structure through all our 'methods'. It holds various arrays
62 reflecting the (sub)structure of the flowgraph. Most of them are of type
63 TBB and are also indexed by TBB. */
67 /* The parent of a node in the DFS tree. */
69 /* For a node x key[x] is roughly the node nearest to the root from which
70 exists a way to x only over nodes behind x. Such a node is also called
73 /* The value in path_min[x] is the node y on the path from x to the root of
74 the tree x is in with the smallest key[y]. */
76 /* bucket[x] points to the first node of the set of nodes having x as key. */
78 /* And next_bucket[x] points to the next node. */
80 /* After the algorithm is done, dom[x] contains the immediate dominator
84 /* The following few fields implement the structures needed for disjoint
86 /* set_chain[x] is the next node on the path from x to the representant
87 of the set containing x. If set_chain[x]==0 then x is a root. */
89 /* set_size[x] is the number of elements in the set named by x. */
90 unsigned int *set_size
;
91 /* set_child[x] is used for balancing the tree representing a set. It can
92 be understood as the next sibling of x. */
95 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
96 number of that node in DFS order counted from 1. This is an index
97 into most of the other arrays in this structure. */
99 /* If x is the DFS-index of a node which corresponds with a basic block,
100 dfs_to_bb[x] is that basic block. Note, that in our structure there are
101 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
102 is true for every basic block bb, but not the opposite. */
103 basic_block
*dfs_to_bb
;
105 /* This is the next free DFS number when creating the DFS tree. */
107 /* The number of nodes in the DFS tree (==dfsnum-1). */
110 /* Blocks with bits set here have a fake edge to EXIT. These are used
111 to turn a DFS forest into a proper tree. */
112 bitmap fake_exit_edge
;
115 static void init_dom_info (struct dom_info
*, enum cdi_direction
);
116 static void free_dom_info (struct dom_info
*);
117 static void calc_dfs_tree_nonrec (struct dom_info
*, basic_block
,
119 static void calc_dfs_tree (struct dom_info
*, enum cdi_direction
);
120 static void compress (struct dom_info
*, TBB
);
121 static TBB
eval (struct dom_info
*, TBB
);
122 static void link_roots (struct dom_info
*, TBB
, TBB
);
123 static void calc_idoms (struct dom_info
*, enum cdi_direction
);
124 void debug_dominance_info (enum cdi_direction
);
126 /* Keeps track of the*/
127 static unsigned n_bbs_in_dom_tree
[2];
129 /* Helper macro for allocating and initializing an array,
130 for aesthetic reasons. */
131 #define init_ar(var, type, num, content) \
134 unsigned int i = 1; /* Catch content == i. */ \
136 (var) = xcalloc ((num), sizeof (type)); \
139 (var) = xmalloc ((num) * sizeof (type)); \
140 for (i = 0; i < num; i++) \
141 (var)[i] = (content); \
146 /* Allocate all needed memory in a pessimistic fashion (so we round up).
147 This initializes the contents of DI, which already must be allocated. */
150 init_dom_info (struct dom_info
*di
, enum cdi_direction dir
)
152 /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
154 unsigned int num
= n_basic_blocks
+ 1 + 1;
155 init_ar (di
->dfs_parent
, TBB
, num
, 0);
156 init_ar (di
->path_min
, TBB
, num
, i
);
157 init_ar (di
->key
, TBB
, num
, i
);
158 init_ar (di
->dom
, TBB
, num
, 0);
160 init_ar (di
->bucket
, TBB
, num
, 0);
161 init_ar (di
->next_bucket
, TBB
, num
, 0);
163 init_ar (di
->set_chain
, TBB
, num
, 0);
164 init_ar (di
->set_size
, unsigned int, num
, 1);
165 init_ar (di
->set_child
, TBB
, num
, 0);
167 init_ar (di
->dfs_order
, TBB
, (unsigned int) last_basic_block
+ 1, 0);
168 init_ar (di
->dfs_to_bb
, basic_block
, num
, 0);
173 di
->fake_exit_edge
= dir
? BITMAP_ALLOC (NULL
) : NULL
;
178 /* Free all allocated memory in DI, but not DI itself. */
181 free_dom_info (struct dom_info
*di
)
183 free (di
->dfs_parent
);
188 free (di
->next_bucket
);
189 free (di
->set_chain
);
191 free (di
->set_child
);
192 free (di
->dfs_order
);
193 free (di
->dfs_to_bb
);
194 BITMAP_FREE (di
->fake_exit_edge
);
197 /* The nonrecursive variant of creating a DFS tree. DI is our working
198 structure, BB the starting basic block for this tree and REVERSE
199 is true, if predecessors should be visited instead of successors of a
200 node. After this is done all nodes reachable from BB were visited, have
201 assigned their dfs number and are linked together to form a tree. */
204 calc_dfs_tree_nonrec (struct dom_info
*di
, basic_block bb
,
205 enum cdi_direction reverse
)
207 /* We call this _only_ if bb is not already visited. */
209 TBB child_i
, my_i
= 0;
210 edge_iterator
*stack
;
211 edge_iterator ei
, einext
;
213 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
215 basic_block en_block
;
217 basic_block ex_block
;
219 stack
= xmalloc ((n_basic_blocks
+ 3) * sizeof (edge_iterator
));
222 /* Initialize our border blocks, and the first edge. */
225 ei
= ei_start (bb
->preds
);
226 en_block
= EXIT_BLOCK_PTR
;
227 ex_block
= ENTRY_BLOCK_PTR
;
231 ei
= ei_start (bb
->succs
);
232 en_block
= ENTRY_BLOCK_PTR
;
233 ex_block
= EXIT_BLOCK_PTR
;
236 /* When the stack is empty we break out of this loop. */
241 /* This loop traverses edges e in depth first manner, and fills the
243 while (!ei_end_p (ei
))
247 /* Deduce from E the current and the next block (BB and BN), and the
253 /* If the next node BN is either already visited or a border
254 block the current edge is useless, and simply overwritten
255 with the next edge out of the current node. */
256 if (bn
== ex_block
|| di
->dfs_order
[bn
->index
])
262 einext
= ei_start (bn
->preds
);
267 if (bn
== ex_block
|| di
->dfs_order
[bn
->index
])
273 einext
= ei_start (bn
->succs
);
276 gcc_assert (bn
!= en_block
);
278 /* Fill the DFS tree info calculatable _before_ recursing. */
280 my_i
= di
->dfs_order
[bb
->index
];
282 my_i
= di
->dfs_order
[last_basic_block
];
283 child_i
= di
->dfs_order
[bn
->index
] = di
->dfsnum
++;
284 di
->dfs_to_bb
[child_i
] = bn
;
285 di
->dfs_parent
[child_i
] = my_i
;
287 /* Save the current point in the CFG on the stack, and recurse. */
296 /* OK. The edge-list was exhausted, meaning normally we would
297 end the recursion. After returning from the recursive call,
298 there were (may be) other statements which were run after a
299 child node was completely considered by DFS. Here is the
300 point to do it in the non-recursive variant.
301 E.g. The block just completed is in e->dest for forward DFS,
302 the block not yet completed (the parent of the one above)
303 in e->src. This could be used e.g. for computing the number of
304 descendants or the tree depth. */
310 /* The main entry for calculating the DFS tree or forest. DI is our working
311 structure and REVERSE is true, if we are interested in the reverse flow
312 graph. In that case the result is not necessarily a tree but a forest,
313 because there may be nodes from which the EXIT_BLOCK is unreachable. */
316 calc_dfs_tree (struct dom_info
*di
, enum cdi_direction reverse
)
318 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
319 basic_block begin
= reverse
? EXIT_BLOCK_PTR
: ENTRY_BLOCK_PTR
;
320 di
->dfs_order
[last_basic_block
] = di
->dfsnum
;
321 di
->dfs_to_bb
[di
->dfsnum
] = begin
;
324 calc_dfs_tree_nonrec (di
, begin
, reverse
);
328 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
329 They are reverse-unreachable. In the dom-case we disallow such
330 nodes, but in post-dom we have to deal with them.
332 There are two situations in which this occurs. First, noreturn
333 functions. Second, infinite loops. In the first case we need to
334 pretend that there is an edge to the exit block. In the second
335 case, we wind up with a forest. We need to process all noreturn
336 blocks before we know if we've got any infinite loops. */
339 bool saw_unconnected
= false;
341 FOR_EACH_BB_REVERSE (b
)
343 if (EDGE_COUNT (b
->succs
) > 0)
345 if (di
->dfs_order
[b
->index
] == 0)
346 saw_unconnected
= true;
349 bitmap_set_bit (di
->fake_exit_edge
, b
->index
);
350 di
->dfs_order
[b
->index
] = di
->dfsnum
;
351 di
->dfs_to_bb
[di
->dfsnum
] = b
;
352 di
->dfs_parent
[di
->dfsnum
] = di
->dfs_order
[last_basic_block
];
354 calc_dfs_tree_nonrec (di
, b
, reverse
);
359 FOR_EACH_BB_REVERSE (b
)
361 if (di
->dfs_order
[b
->index
])
363 bitmap_set_bit (di
->fake_exit_edge
, b
->index
);
364 di
->dfs_order
[b
->index
] = di
->dfsnum
;
365 di
->dfs_to_bb
[di
->dfsnum
] = b
;
366 di
->dfs_parent
[di
->dfsnum
] = di
->dfs_order
[last_basic_block
];
368 calc_dfs_tree_nonrec (di
, b
, reverse
);
373 di
->nodes
= di
->dfsnum
- 1;
375 /* Make sure there is a path from ENTRY to EXIT at all. */
376 gcc_assert (di
->nodes
== (unsigned int) n_basic_blocks
+ 1);
379 /* Compress the path from V to the root of its set and update path_min at the
380 same time. After compress(di, V) set_chain[V] is the root of the set V is
381 in and path_min[V] is the node with the smallest key[] value on the path
382 from V to that root. */
385 compress (struct dom_info
*di
, TBB v
)
387 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
388 greater than 5 even for huge graphs (I've not seen call depth > 4).
389 Also performance wise compress() ranges _far_ behind eval(). */
390 TBB parent
= di
->set_chain
[v
];
391 if (di
->set_chain
[parent
])
393 compress (di
, parent
);
394 if (di
->key
[di
->path_min
[parent
]] < di
->key
[di
->path_min
[v
]])
395 di
->path_min
[v
] = di
->path_min
[parent
];
396 di
->set_chain
[v
] = di
->set_chain
[parent
];
400 /* Compress the path from V to the set root of V if needed (when the root has
401 changed since the last call). Returns the node with the smallest key[]
402 value on the path from V to the root. */
405 eval (struct dom_info
*di
, TBB v
)
407 /* The representant of the set V is in, also called root (as the set
408 representation is a tree). */
409 TBB rep
= di
->set_chain
[v
];
411 /* V itself is the root. */
413 return di
->path_min
[v
];
415 /* Compress only if necessary. */
416 if (di
->set_chain
[rep
])
419 rep
= di
->set_chain
[v
];
422 if (di
->key
[di
->path_min
[rep
]] >= di
->key
[di
->path_min
[v
]])
423 return di
->path_min
[v
];
425 return di
->path_min
[rep
];
428 /* This essentially merges the two sets of V and W, giving a single set with
429 the new root V. The internal representation of these disjoint sets is a
430 balanced tree. Currently link(V,W) is only used with V being the parent
434 link_roots (struct dom_info
*di
, TBB v
, TBB w
)
438 /* Rebalance the tree. */
439 while (di
->key
[di
->path_min
[w
]] < di
->key
[di
->path_min
[di
->set_child
[s
]]])
441 if (di
->set_size
[s
] + di
->set_size
[di
->set_child
[di
->set_child
[s
]]]
442 >= 2 * di
->set_size
[di
->set_child
[s
]])
444 di
->set_chain
[di
->set_child
[s
]] = s
;
445 di
->set_child
[s
] = di
->set_child
[di
->set_child
[s
]];
449 di
->set_size
[di
->set_child
[s
]] = di
->set_size
[s
];
450 s
= di
->set_chain
[s
] = di
->set_child
[s
];
454 di
->path_min
[s
] = di
->path_min
[w
];
455 di
->set_size
[v
] += di
->set_size
[w
];
456 if (di
->set_size
[v
] < 2 * di
->set_size
[w
])
459 s
= di
->set_child
[v
];
460 di
->set_child
[v
] = tmp
;
463 /* Merge all subtrees. */
466 di
->set_chain
[s
] = v
;
467 s
= di
->set_child
[s
];
471 /* This calculates the immediate dominators (or post-dominators if REVERSE is
472 true). DI is our working structure and should hold the DFS forest.
473 On return the immediate dominator to node V is in di->dom[V]. */
476 calc_idoms (struct dom_info
*di
, enum cdi_direction reverse
)
479 basic_block en_block
;
480 edge_iterator ei
, einext
;
483 en_block
= EXIT_BLOCK_PTR
;
485 en_block
= ENTRY_BLOCK_PTR
;
487 /* Go backwards in DFS order, to first look at the leafs. */
491 basic_block bb
= di
->dfs_to_bb
[v
];
494 par
= di
->dfs_parent
[v
];
497 ei
= (reverse
) ? ei_start (bb
->succs
) : ei_start (bb
->preds
);
501 /* If this block has a fake edge to exit, process that first. */
502 if (bitmap_bit_p (di
->fake_exit_edge
, bb
->index
))
506 goto do_fake_exit_edge
;
510 /* Search all direct predecessors for the smallest node with a path
511 to them. That way we have the smallest node with also a path to
512 us only over nodes behind us. In effect we search for our
514 while (!ei_end_p (ei
))
520 b
= (reverse
) ? e
->dest
: e
->src
;
527 k1
= di
->dfs_order
[last_basic_block
];
530 k1
= di
->dfs_order
[b
->index
];
532 /* Call eval() only if really needed. If k1 is above V in DFS tree,
533 then we know, that eval(k1) == k1 and key[k1] == k1. */
535 k1
= di
->key
[eval (di
, k1
)];
543 link_roots (di
, par
, v
);
544 di
->next_bucket
[v
] = di
->bucket
[k
];
547 /* Transform semidominators into dominators. */
548 for (w
= di
->bucket
[par
]; w
; w
= di
->next_bucket
[w
])
551 if (di
->key
[k
] < di
->key
[w
])
556 /* We don't need to cleanup next_bucket[]. */
561 /* Explicitly define the dominators. */
563 for (v
= 2; v
<= di
->nodes
; v
++)
564 if (di
->dom
[v
] != di
->key
[v
])
565 di
->dom
[v
] = di
->dom
[di
->dom
[v
]];
568 /* Assign dfs numbers starting from NUM to NODE and its sons. */
571 assign_dfs_numbers (struct et_node
*node
, int *num
)
575 node
->dfs_num_in
= (*num
)++;
579 assign_dfs_numbers (node
->son
, num
);
580 for (son
= node
->son
->right
; son
!= node
->son
; son
= son
->right
)
581 assign_dfs_numbers (son
, num
);
584 node
->dfs_num_out
= (*num
)++;
587 /* Compute the data necessary for fast resolving of dominator queries in a
588 static dominator tree. */
591 compute_dom_fast_query (enum cdi_direction dir
)
596 gcc_assert (dom_info_available_p (dir
));
598 if (dom_computed
[dir
] == DOM_OK
)
603 if (!bb
->dom
[dir
]->father
)
604 assign_dfs_numbers (bb
->dom
[dir
], &num
);
607 dom_computed
[dir
] = DOM_OK
;
610 /* The main entry point into this module. DIR is set depending on whether
611 we want to compute dominators or postdominators. */
614 calculate_dominance_info (enum cdi_direction dir
)
619 if (dom_computed
[dir
] == DOM_OK
)
622 if (!dom_info_available_p (dir
))
624 gcc_assert (!n_bbs_in_dom_tree
[dir
]);
628 b
->dom
[dir
] = et_new_tree (b
);
630 n_bbs_in_dom_tree
[dir
] = n_basic_blocks
+ 2;
632 init_dom_info (&di
, dir
);
633 calc_dfs_tree (&di
, dir
);
634 calc_idoms (&di
, dir
);
638 TBB d
= di
.dom
[di
.dfs_order
[b
->index
]];
641 et_set_father (b
->dom
[dir
], di
.dfs_to_bb
[d
]->dom
[dir
]);
645 dom_computed
[dir
] = DOM_NO_FAST_QUERY
;
648 compute_dom_fast_query (dir
);
651 /* Free dominance information for direction DIR. */
653 free_dominance_info (enum cdi_direction dir
)
657 if (!dom_info_available_p (dir
))
662 et_free_tree_force (bb
->dom
[dir
]);
666 n_bbs_in_dom_tree
[dir
] = 0;
668 dom_computed
[dir
] = DOM_NONE
;
671 /* Return the immediate dominator of basic block BB. */
673 get_immediate_dominator (enum cdi_direction dir
, basic_block bb
)
675 struct et_node
*node
= bb
->dom
[dir
];
677 gcc_assert (dom_computed
[dir
]);
682 return node
->father
->data
;
685 /* Set the immediate dominator of the block possibly removing
686 existing edge. NULL can be used to remove any edge. */
688 set_immediate_dominator (enum cdi_direction dir
, basic_block bb
,
689 basic_block dominated_by
)
691 struct et_node
*node
= bb
->dom
[dir
];
693 gcc_assert (dom_computed
[dir
]);
697 if (node
->father
->data
== dominated_by
)
703 et_set_father (node
, dominated_by
->dom
[dir
]);
705 if (dom_computed
[dir
] == DOM_OK
)
706 dom_computed
[dir
] = DOM_NO_FAST_QUERY
;
709 /* Store all basic blocks immediately dominated by BB into BBS and return
712 get_dominated_by (enum cdi_direction dir
, basic_block bb
, basic_block
**bbs
)
715 struct et_node
*node
= bb
->dom
[dir
], *son
= node
->son
, *ason
;
717 gcc_assert (dom_computed
[dir
]);
725 for (ason
= son
->right
, n
= 1; ason
!= son
; ason
= ason
->right
)
728 *bbs
= xmalloc (n
* sizeof (basic_block
));
729 (*bbs
)[0] = son
->data
;
730 for (ason
= son
->right
, n
= 1; ason
!= son
; ason
= ason
->right
)
731 (*bbs
)[n
++] = ason
->data
;
736 /* Find all basic blocks that are immediately dominated (in direction DIR)
737 by some block between N_REGION ones stored in REGION, except for blocks
738 in the REGION itself. The found blocks are stored to DOMS and their number
742 get_dominated_by_region (enum cdi_direction dir
, basic_block
*region
,
743 unsigned n_region
, basic_block
*doms
)
745 unsigned n_doms
= 0, i
;
748 for (i
= 0; i
< n_region
; i
++)
749 region
[i
]->flags
|= BB_DUPLICATED
;
750 for (i
= 0; i
< n_region
; i
++)
751 for (dom
= first_dom_son (dir
, region
[i
]);
753 dom
= next_dom_son (dir
, dom
))
754 if (!(dom
->flags
& BB_DUPLICATED
))
755 doms
[n_doms
++] = dom
;
756 for (i
= 0; i
< n_region
; i
++)
757 region
[i
]->flags
&= ~BB_DUPLICATED
;
762 /* Redirect all edges pointing to BB to TO. */
764 redirect_immediate_dominators (enum cdi_direction dir
, basic_block bb
,
767 struct et_node
*bb_node
= bb
->dom
[dir
], *to_node
= to
->dom
[dir
], *son
;
769 gcc_assert (dom_computed
[dir
]);
779 et_set_father (son
, to_node
);
782 if (dom_computed
[dir
] == DOM_OK
)
783 dom_computed
[dir
] = DOM_NO_FAST_QUERY
;
786 /* Find first basic block in the tree dominating both BB1 and BB2. */
788 nearest_common_dominator (enum cdi_direction dir
, basic_block bb1
, basic_block bb2
)
790 gcc_assert (dom_computed
[dir
]);
797 return et_nca (bb1
->dom
[dir
], bb2
->dom
[dir
])->data
;
801 /* Find the nearest common dominator for the basic blocks in BLOCKS,
802 using dominance direction DIR. */
805 nearest_common_dominator_for_set (enum cdi_direction dir
, bitmap blocks
)
811 first
= bitmap_first_set_bit (blocks
);
812 dom
= BASIC_BLOCK (first
);
813 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
, bi
)
814 if (dom
!= BASIC_BLOCK (i
))
815 dom
= nearest_common_dominator (dir
, dom
, BASIC_BLOCK (i
));
821 /* Return TRUE in case BB1 is dominated by BB2. */
823 dominated_by_p (enum cdi_direction dir
, basic_block bb1
, basic_block bb2
)
825 struct et_node
*n1
= bb1
->dom
[dir
], *n2
= bb2
->dom
[dir
];
827 gcc_assert (dom_computed
[dir
]);
829 if (dom_computed
[dir
] == DOM_OK
)
830 return (n1
->dfs_num_in
>= n2
->dfs_num_in
831 && n1
->dfs_num_out
<= n2
->dfs_num_out
);
833 return et_below (n1
, n2
);
836 /* Verify invariants of dominator structure. */
838 verify_dominators (enum cdi_direction dir
)
843 gcc_assert (dom_info_available_p (dir
));
850 dom_bb
= recount_dominator (dir
, bb
);
851 imm_bb
= get_immediate_dominator (dir
, bb
);
852 if (dom_bb
!= imm_bb
)
854 if ((dom_bb
== NULL
) || (imm_bb
== NULL
))
855 error ("dominator of %d status unknown", bb
->index
);
857 error ("dominator of %d should be %d, not %d",
858 bb
->index
, dom_bb
->index
, imm_bb
->index
);
863 if (dir
== CDI_DOMINATORS
)
867 if (!dominated_by_p (dir
, bb
, ENTRY_BLOCK_PTR
))
869 error ("ENTRY does not dominate bb %d", bb
->index
);
878 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
879 assuming that dominators of other blocks are correct. We also use it to
880 recompute the dominators in a restricted area, by iterating it until it
881 reaches a fixed point. */
884 recount_dominator (enum cdi_direction dir
, basic_block bb
)
886 basic_block dom_bb
= NULL
;
890 gcc_assert (dom_computed
[dir
]);
892 if (dir
== CDI_DOMINATORS
)
894 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
896 /* Ignore the predecessors that either are not reachable from
897 the entry block, or whose dominator was not determined yet. */
898 if (!dominated_by_p (dir
, e
->src
, ENTRY_BLOCK_PTR
))
901 if (!dominated_by_p (dir
, e
->src
, bb
))
902 dom_bb
= nearest_common_dominator (dir
, dom_bb
, e
->src
);
907 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
909 if (!dominated_by_p (dir
, e
->dest
, bb
))
910 dom_bb
= nearest_common_dominator (dir
, dom_bb
, e
->dest
);
917 /* Iteratively recount dominators of BBS. The change is supposed to be local
918 and not to grow further. */
920 iterate_fix_dominators (enum cdi_direction dir
, basic_block
*bbs
, int n
)
923 basic_block old_dom
, new_dom
;
925 gcc_assert (dom_computed
[dir
]);
927 for (i
= 0; i
< n
; i
++)
928 set_immediate_dominator (dir
, bbs
[i
], NULL
);
933 for (i
= 0; i
< n
; i
++)
935 old_dom
= get_immediate_dominator (dir
, bbs
[i
]);
936 new_dom
= recount_dominator (dir
, bbs
[i
]);
937 if (old_dom
!= new_dom
)
940 set_immediate_dominator (dir
, bbs
[i
], new_dom
);
945 for (i
= 0; i
< n
; i
++)
946 gcc_assert (get_immediate_dominator (dir
, bbs
[i
]));
950 add_to_dominance_info (enum cdi_direction dir
, basic_block bb
)
952 gcc_assert (dom_computed
[dir
]);
953 gcc_assert (!bb
->dom
[dir
]);
955 n_bbs_in_dom_tree
[dir
]++;
957 bb
->dom
[dir
] = et_new_tree (bb
);
959 if (dom_computed
[dir
] == DOM_OK
)
960 dom_computed
[dir
] = DOM_NO_FAST_QUERY
;
964 delete_from_dominance_info (enum cdi_direction dir
, basic_block bb
)
966 gcc_assert (dom_computed
[dir
]);
968 et_free_tree (bb
->dom
[dir
]);
970 n_bbs_in_dom_tree
[dir
]--;
972 if (dom_computed
[dir
] == DOM_OK
)
973 dom_computed
[dir
] = DOM_NO_FAST_QUERY
;
976 /* Returns the first son of BB in the dominator or postdominator tree
977 as determined by DIR. */
980 first_dom_son (enum cdi_direction dir
, basic_block bb
)
982 struct et_node
*son
= bb
->dom
[dir
]->son
;
984 return son
? son
->data
: NULL
;
987 /* Returns the next dominance son after BB in the dominator or postdominator
988 tree as determined by DIR, or NULL if it was the last one. */
991 next_dom_son (enum cdi_direction dir
, basic_block bb
)
993 struct et_node
*next
= bb
->dom
[dir
]->right
;
995 return next
->father
->son
== next
? NULL
: next
->data
;
998 /* Returns true if dominance information for direction DIR is available. */
1001 dom_info_available_p (enum cdi_direction dir
)
1003 return dom_computed
[dir
] != DOM_NONE
;
1007 debug_dominance_info (enum cdi_direction dir
)
1009 basic_block bb
, bb2
;
1011 if ((bb2
= get_immediate_dominator (dir
, bb
)))
1012 fprintf (stderr
, "%i %i\n", bb
->index
, bb2
->index
);