+
+ gcc_assert (dom != NULL);
+ for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+ {
+ bb = VEC_index (basic_block, bbs, a);
+ set_immediate_dominator (CDI_DOMINATORS, bb, dom);
+ }
+ }
+
+ for (i = 0; i < nc; i++)
+ VEC_free (int, heap, sccs[i]);
+ free (sccs);
+
+ for (a = son[y]; a != -1; a = brother[a])
+ identify_vertices (g, y, a);
+}
+
+/* Recompute dominance information for basic blocks in the set BBS. The
+ function assumes that the immediate dominators of all the other blocks
+ in CFG are correct, and that there are no unreachable blocks.
+
+ If CONSERVATIVE is true, we additionally assume that all the ancestors of
+ a block of BBS in the current dominance tree dominate it. */
+
+void
+iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
+ bool conservative)
+{
+ unsigned i;
+ basic_block bb, dom;
+ struct graph *g;
+ int n, y;
+ size_t dom_i;
+ edge e;
+ edge_iterator ei;
+ struct pointer_map_t *map;
+ int *parent, *son, *brother;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ /* We only support updating dominators. There are some problems with
+ updating postdominators (need to add fake edges from infinite loops
+ and noreturn functions), and since we do not currently use
+ iterate_fix_dominators for postdominators, any attempt to handle these
+ problems would be unused, untested, and almost surely buggy. We keep
+ the DIR argument for consistency with the rest of the dominator analysis
+ interface. */
+ gcc_assert (dir == CDI_DOMINATORS);
+ gcc_assert (dom_computed[dir_index]);
+
+ /* The algorithm we use takes inspiration from the following papers, although
+ the details are quite different from any of them:
+
+ [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
+ Dominator Tree of a Reducible Flowgraph
+ [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
+ dominator trees
+ [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
+ Algorithm
+
+ First, we use the following heuristics to decrease the size of the BBS
+ set:
+ a) if BB has a single predecessor, then its immediate dominator is this
+ predecessor
+ additionally, if CONSERVATIVE is true:
+ b) if all the predecessors of BB except for one (X) are dominated by BB,
+ then X is the immediate dominator of BB
+ c) if the nearest common ancestor of the predecessors of BB is X and
+ X -> BB is an edge in CFG, then X is the immediate dominator of BB
+
+ Then, we need to establish the dominance relation among the basic blocks
+ in BBS. We split the dominance tree by removing the immediate dominator
+ edges from BBS, creating a forest F. We form a graph G whose vertices
+ are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
+ X' -> Y in CFG such that X' belongs to the tree of the dominance forest
+ whose root is X. We then determine dominance tree of G. Note that
+ for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
+ In this step, we can use arbitrary algorithm to determine dominators.
+ We decided to prefer the algorithm [3] to the algorithm of
+ Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
+ 10 during gcc bootstrap), and [3] should perform better in this case.
+
+ Finally, we need to determine the immediate dominators for the basic
+ blocks of BBS. If the immediate dominator of X in G is Y, then
+ the immediate dominator of X in CFG belongs to the tree of F rooted in
+ Y. We process the dominator tree T of G recursively, starting from leaves.
+ Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
+ subtrees of the dominance tree of CFG rooted in X_i are already correct.
+ Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
+ the following observations:
+ (i) the immediate dominator of all blocks in a strongly connected
+ component of G' is the same
+ (ii) if X has no predecessors in G', then the immediate dominator of X
+ is the nearest common ancestor of the predecessors of X in the
+ subtree of F rooted in Y
+ Therefore, it suffices to find the topological ordering of G', and
+ process the nodes X_i in this order using the rules (i) and (ii).
+ Then, we contract all the nodes X_i with Y in G, so that the further
+ steps work correctly. */
+
+ if (!conservative)
+ {
+ /* Split the tree now. If the idoms of blocks in BBS are not
+ conservatively correct, setting the dominators using the
+ heuristics in prune_bbs_to_update_dominators could
+ create cycles in the dominance "tree", and cause ICE. */
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+ }
+
+ prune_bbs_to_update_dominators (bbs, conservative);
+ n = VEC_length (basic_block, bbs);
+
+ if (n == 0)
+ return;
+
+ if (n == 1)
+ {
+ bb = VEC_index (basic_block, bbs, 0);
+ set_immediate_dominator (CDI_DOMINATORS, bb,
+ recompute_dominator (CDI_DOMINATORS, bb));
+ return;
+ }
+
+ /* Construct the graph G. */
+ map = pointer_map_create ();
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ /* If the dominance tree is conservatively correct, split it now. */
+ if (conservative)
+ set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
+ *pointer_map_insert (map, bb) = (void *) (size_t) i;
+ }
+ *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
+
+ g = new_graph (n + 1);
+ for (y = 0; y < g->n_vertices; y++)
+ g->vertices[y].data = BITMAP_ALLOC (NULL);
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
+ if (dom == bb)
+ continue;
+
+ dom_i = (size_t) *pointer_map_contains (map, dom);
+
+ /* Do not include parallel edges to G. */
+ if (bitmap_bit_p (g->vertices[dom_i].data, i))
+ continue;
+
+ bitmap_set_bit (g->vertices[dom_i].data, i);
+ add_edge (g, dom_i, i);
+ }
+ }
+ for (y = 0; y < g->n_vertices; y++)
+ BITMAP_FREE (g->vertices[y].data);
+ pointer_map_destroy (map);
+
+ /* Find the dominator tree of G. */
+ son = XNEWVEC (int, n + 1);
+ brother = XNEWVEC (int, n + 1);
+ parent = XNEWVEC (int, n + 1);
+ graphds_domtree (g, n, parent, son, brother);
+
+ /* Finally, traverse the tree and find the immediate dominators. */
+ for (y = n; son[y] != -1; y = son[y])
+ continue;
+ while (y != -1)
+ {
+ determine_dominators_for_sons (g, bbs, y, son, brother);
+
+ if (brother[y] != -1)
+ {
+ y = brother[y];
+ while (son[y] != -1)
+ y = son[y];
+ }
+ else
+ y = parent[y];