X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=8cfaba033a399faedf5f81e6b50f628641e1d761;hb=59d142eb8e568c760c374ec99b7dc22521c67cbc;hp=48c621961e1f37704573befc687c9120fb8bd409;hpb=457275b654f3dbfc4d26ce1e7ec4c4f862ca463f;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dominance.c b/gcc/dominance.c index 48c621961e1..8cfaba033a3 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -1,5 +1,5 @@ /* Calculate (post)dominators in slightly super-linear time. - Copyright (C) 2000 Free Software Foundation, Inc. + Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc. Contributed by Michael Matz (matz@ifh.de). This file is part of GCC. @@ -16,8 +16,8 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free - Software Foundation, 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ + Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ /* This file implements the well known algorithm from Lengauer and Tarjan to compute the dominators in a control flow graph. A basic block D is said @@ -30,27 +30,22 @@ The algorithm computes this dominator tree implicitly by computing for each block its immediate dominator. We use tree balancing and path - compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very + compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very slowly growing functional inverse of the Ackerman function. */ #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "rtl.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" -#include "errors.h" +#include "toplev.h" #include "et-forest.h" -struct dominance_info -{ - et_forest_t forest; - varray_type varray; -}; - -#define BB_NODE(info, bb) \ - ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2)) -#define SET_BB_NODE(info, bb, node) \ - (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node)) +/* Whether the dominators and the postdominators are available. */ +enum dom_state dom_computed[2]; /* We name our nodes with integers, beginning with 1. Zero is reserved for 'undefined' or 'end of list'. The name of each node is given by the dfs @@ -101,31 +96,35 @@ struct dom_info number of that node in DFS order counted from 1. This is an index into most of the other arrays in this structure. */ TBB *dfs_order; - /* If x is the DFS-index of a node which corresponds with an basic block, + /* If x is the DFS-index of a node which corresponds with a basic block, dfs_to_bb[x] is that basic block. Note, that in our structure there are more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb is true for every basic block bb, but not the opposite. */ basic_block *dfs_to_bb; - /* This is the next free DFS number when creating the DFS tree or forest. */ + /* This is the next free DFS number when creating the DFS tree. */ unsigned int dfsnum; /* The number of nodes in the DFS tree (==dfsnum-1). */ unsigned int nodes; + + /* Blocks with bits set here have a fake edge to EXIT. These are used + to turn a DFS forest into a proper tree. */ + bitmap fake_exit_edge; }; -static void init_dom_info PARAMS ((struct dom_info *)); -static void free_dom_info PARAMS ((struct dom_info *)); -static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *, - basic_block, - enum cdi_direction)); -static void calc_dfs_tree PARAMS ((struct dom_info *, - enum cdi_direction)); -static void compress PARAMS ((struct dom_info *, TBB)); -static TBB eval PARAMS ((struct dom_info *, TBB)); -static void link_roots PARAMS ((struct dom_info *, TBB, TBB)); -static void calc_idoms PARAMS ((struct dom_info *, - enum cdi_direction)); -void debug_dominance_info PARAMS ((dominance_info)); +static void init_dom_info (struct dom_info *, enum cdi_direction); +static void free_dom_info (struct dom_info *); +static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, + enum cdi_direction); +static void calc_dfs_tree (struct dom_info *, enum cdi_direction); +static void compress (struct dom_info *, TBB); +static TBB eval (struct dom_info *, TBB); +static void link_roots (struct dom_info *, TBB, TBB); +static void calc_idoms (struct dom_info *, enum cdi_direction); +void debug_dominance_info (enum cdi_direction); + +/* Keeps track of the*/ +static unsigned n_bbs_in_dom_tree[2]; /* Helper macro for allocating and initializing an array, for aesthetic reasons. */ @@ -134,10 +133,10 @@ void debug_dominance_info PARAMS ((dominance_info)); { \ unsigned int i = 1; /* Catch content == i. */ \ if (! (content)) \ - (var) = (type *) xcalloc ((num), sizeof (type)); \ + (var) = xcalloc ((num), sizeof (type)); \ else \ { \ - (var) = (type *) xmalloc ((num) * sizeof (type)); \ + (var) = xmalloc ((num) * sizeof (type)); \ for (i = 0; i < num; i++) \ (var)[i] = (content); \ } \ @@ -148,8 +147,7 @@ void debug_dominance_info PARAMS ((dominance_info)); This initializes the contents of DI, which already must be allocated. */ static void -init_dom_info (di) - struct dom_info *di; +init_dom_info (struct dom_info *di, enum cdi_direction dir) { /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or EXIT_BLOCK. */ @@ -171,6 +169,8 @@ init_dom_info (di) di->dfsnum = 1; di->nodes = 0; + + di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL; } #undef init_ar @@ -178,8 +178,7 @@ init_dom_info (di) /* Free all allocated memory in DI, but not DI itself. */ static void -free_dom_info (di) - struct dom_info *di; +free_dom_info (struct dom_info *di) { free (di->dfs_parent); free (di->path_min); @@ -192,6 +191,7 @@ free_dom_info (di) free (di->set_child); free (di->dfs_order); free (di->dfs_to_bb); + BITMAP_FREE (di->fake_exit_edge); } /* The nonrecursive variant of creating a DFS tree. DI is our working @@ -201,16 +201,14 @@ free_dom_info (di) assigned their dfs number and are linked together to form a tree. */ static void -calc_dfs_tree_nonrec (di, bb, reverse) - struct dom_info *di; - basic_block bb; - enum cdi_direction reverse; +calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, + enum cdi_direction reverse) { - /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */ /* We call this _only_ if bb is not already visited. */ edge e; TBB child_i, my_i = 0; - edge *stack; + edge_iterator *stack; + edge_iterator ei, einext; int sp; /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward problem). */ @@ -218,19 +216,19 @@ calc_dfs_tree_nonrec (di, bb, reverse) /* Ending block. */ basic_block ex_block; - stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge)); + stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge_iterator)); sp = 0; /* Initialize our border blocks, and the first edge. */ if (reverse) { - e = bb->pred; + ei = ei_start (bb->preds); en_block = EXIT_BLOCK_PTR; ex_block = ENTRY_BLOCK_PTR; } else { - e = bb->succ; + ei = ei_start (bb->succs); en_block = ENTRY_BLOCK_PTR; ex_block = EXIT_BLOCK_PTR; } @@ -242,9 +240,9 @@ calc_dfs_tree_nonrec (di, bb, reverse) /* This loop traverses edges e in depth first manner, and fills the stack. */ - while (e) + while (!ei_end_p (ei)) { - edge e_next; + e = ei_edge (ei); /* Deduce from E the current and the next block (BB and BN), and the next edge. */ @@ -257,26 +255,25 @@ calc_dfs_tree_nonrec (di, bb, reverse) with the next edge out of the current node. */ if (bn == ex_block || di->dfs_order[bn->index]) { - e = e->pred_next; + ei_next (&ei); continue; } bb = e->dest; - e_next = bn->pred; + einext = ei_start (bn->preds); } else { bn = e->dest; if (bn == ex_block || di->dfs_order[bn->index]) { - e = e->succ_next; + ei_next (&ei); continue; } bb = e->src; - e_next = bn->succ; + einext = ei_start (bn->succs); } - if (bn == en_block) - abort (); + gcc_assert (bn != en_block); /* Fill the DFS tree info calculatable _before_ recursing. */ if (bb != en_block) @@ -288,13 +285,13 @@ calc_dfs_tree_nonrec (di, bb, reverse) di->dfs_parent[child_i] = my_i; /* Save the current point in the CFG on the stack, and recurse. */ - stack[sp++] = e; - e = e_next; + stack[sp++] = ei; + ei = einext; } if (!sp) break; - e = stack[--sp]; + ei = stack[--sp]; /* OK. The edge-list was exhausted, meaning normally we would end the recursion. After returning from the recursive call, @@ -305,10 +302,7 @@ calc_dfs_tree_nonrec (di, bb, reverse) the block not yet completed (the parent of the one above) in e->src. This could be used e.g. for computing the number of descendants or the tree depth. */ - if (reverse) - e = e->pred_next; - else - e = e->succ_next; + ei_next (&ei); } free (stack); } @@ -319,9 +313,7 @@ calc_dfs_tree_nonrec (di, bb, reverse) because there may be nodes from which the EXIT_BLOCK is unreachable. */ static void -calc_dfs_tree (di, reverse) - struct dom_info *di; - enum cdi_direction reverse; +calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse) { /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; @@ -335,25 +327,53 @@ calc_dfs_tree (di, reverse) { /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. They are reverse-unreachable. In the dom-case we disallow such - nodes, but in post-dom we have to deal with them, so we simply - include them in the DFS tree which actually becomes a forest. */ + nodes, but in post-dom we have to deal with them. + + There are two situations in which this occurs. First, noreturn + functions. Second, infinite loops. In the first case we need to + pretend that there is an edge to the exit block. In the second + case, we wind up with a forest. We need to process all noreturn + blocks before we know if we've got any infinite loops. */ + basic_block b; + bool saw_unconnected = false; + FOR_EACH_BB_REVERSE (b) { - if (di->dfs_order[b->index]) - continue; + if (EDGE_COUNT (b->succs) > 0) + { + if (di->dfs_order[b->index] == 0) + saw_unconnected = true; + continue; + } + bitmap_set_bit (di->fake_exit_edge, b->index); di->dfs_order[b->index] = di->dfsnum; di->dfs_to_bb[di->dfsnum] = b; + di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; di->dfsnum++; calc_dfs_tree_nonrec (di, b, reverse); } + + if (saw_unconnected) + { + FOR_EACH_BB_REVERSE (b) + { + if (di->dfs_order[b->index]) + continue; + bitmap_set_bit (di->fake_exit_edge, b->index); + di->dfs_order[b->index] = di->dfsnum; + di->dfs_to_bb[di->dfsnum] = b; + di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; + di->dfsnum++; + calc_dfs_tree_nonrec (di, b, reverse); + } + } } di->nodes = di->dfsnum - 1; - /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ - if (di->nodes != (unsigned int) n_basic_blocks + 1) - abort (); + /* Make sure there is a path from ENTRY to EXIT at all. */ + gcc_assert (di->nodes == (unsigned int) n_basic_blocks + 1); } /* Compress the path from V to the root of its set and update path_min at the @@ -362,9 +382,7 @@ calc_dfs_tree (di, reverse) from V to that root. */ static void -compress (di, v) - struct dom_info *di; - TBB v; +compress (struct dom_info *di, TBB v) { /* Btw. It's not worth to unrecurse compress() as the depth is usually not greater than 5 even for huge graphs (I've not seen call depth > 4). @@ -384,9 +402,7 @@ compress (di, v) value on the path from V to the root. */ static inline TBB -eval (di, v) - struct dom_info *di; - TBB v; +eval (struct dom_info *di, TBB v) { /* The representant of the set V is in, also called root (as the set representation is a tree). */ @@ -415,9 +431,7 @@ eval (di, v) of W. */ static void -link_roots (di, v, w) - struct dom_info *di; - TBB v, w; +link_roots (struct dom_info *di, TBB v, TBB w) { TBB s = w; @@ -459,12 +473,12 @@ link_roots (di, v, w) On return the immediate dominator to node V is in di->dom[V]. */ static void -calc_idoms (di, reverse) - struct dom_info *di; - enum cdi_direction reverse; +calc_idoms (struct dom_info *di, enum cdi_direction reverse) { TBB v, w, k, par; basic_block en_block; + edge_iterator ei, einext; + if (reverse) en_block = EXIT_BLOCK_PTR; else @@ -475,36 +489,43 @@ calc_idoms (di, reverse) while (v > 1) { basic_block bb = di->dfs_to_bb[v]; - edge e, e_next; + edge e; par = di->dfs_parent[v]; k = v; + + ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds); + if (reverse) - e = bb->succ; - else - e = bb->pred; + { + /* If this block has a fake edge to exit, process that first. */ + if (bitmap_bit_p (di->fake_exit_edge, bb->index)) + { + einext = ei; + einext.index = 0; + goto do_fake_exit_edge; + } + } /* Search all direct predecessors for the smallest node with a path to them. That way we have the smallest node with also a path to us only over nodes behind us. In effect we search for our semidominator. */ - for (; e; e = e_next) + while (!ei_end_p (ei)) { TBB k1; basic_block b; - if (reverse) - { - b = e->dest; - e_next = e->succ_next; - } - else + e = ei_edge (ei); + b = (reverse) ? e->dest : e->src; + einext = ei; + ei_next (&einext); + + if (b == en_block) { - b = e->src; - e_next = e->pred_next; + do_fake_exit_edge: + k1 = di->dfs_order[last_basic_block]; } - if (b == en_block) - k1 = di->dfs_order[last_basic_block]; else k1 = di->dfs_order[b->index]; @@ -514,6 +535,8 @@ calc_idoms (di, reverse) k1 = di->key[eval (di, k1)]; if (k1 < k) k = k1; + + ei = einext; } di->key[v] = k; @@ -542,271 +565,449 @@ calc_idoms (di, reverse) di->dom[v] = di->dom[di->dom[v]]; } -/* The main entry point into this module. IDOM is an integer array with room - for last_basic_block integers, DOMS is a preallocated sbitmap array having - room for last_basic_block^2 bits, and POST is true if the caller wants to - know post-dominators. +/* Assign dfs numbers starting from NUM to NODE and its sons. */ - On return IDOM[i] will be the BB->index of the immediate (post) dominator - of basic block i, and DOMS[i] will have set bit j if basic block j is a - (post)dominator for block i. +static void +assign_dfs_numbers (struct et_node *node, int *num) +{ + struct et_node *son; - Either IDOM or DOMS may be NULL (meaning the caller is not interested in - immediate resp. all dominators). */ + node->dfs_num_in = (*num)++; -dominance_info -calculate_dominance_info (reverse) - enum cdi_direction reverse; + if (node->son) + { + assign_dfs_numbers (node->son, num); + for (son = node->son->right; son != node->son; son = son->right) + assign_dfs_numbers (son, num); + } + + node->dfs_num_out = (*num)++; +} + +/* Compute the data necessary for fast resolving of dominator queries in a + static dominator tree. */ + +static void +compute_dom_fast_query (enum cdi_direction dir) +{ + int num = 0; + basic_block bb; + + gcc_assert (dom_info_available_p (dir)); + + if (dom_computed[dir] == DOM_OK) + return; + + FOR_ALL_BB (bb) + { + if (!bb->dom[dir]->father) + assign_dfs_numbers (bb->dom[dir], &num); + } + + dom_computed[dir] = DOM_OK; +} + +/* The main entry point into this module. DIR is set depending on whether + we want to compute dominators or postdominators. */ + +void +calculate_dominance_info (enum cdi_direction dir) { struct dom_info di; - dominance_info info; basic_block b; - /* allocate structure for dominance information. */ - info = xmalloc (sizeof (struct dominance_info)); - info->forest = et_forest_create (); - VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info"); + if (dom_computed[dir] == DOM_OK) + return; + + if (!dom_info_available_p (dir)) + { + gcc_assert (!n_bbs_in_dom_tree[dir]); - /* Add the two well-known basic blocks. */ - SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest, - ENTRY_BLOCK_PTR)); - SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest, - EXIT_BLOCK_PTR)); - FOR_EACH_BB (b) - SET_BB_NODE (info, b, et_forest_add_node (info->forest, b)); + FOR_ALL_BB (b) + { + b->dom[dir] = et_new_tree (b); + } + n_bbs_in_dom_tree[dir] = n_basic_blocks + 2; - init_dom_info (&di); - calc_dfs_tree (&di, reverse); - calc_idoms (&di, reverse); + init_dom_info (&di, dir); + calc_dfs_tree (&di, dir); + calc_idoms (&di, dir); + FOR_EACH_BB (b) + { + TBB d = di.dom[di.dfs_order[b->index]]; - FOR_EACH_BB (b) - { - TBB d = di.dom[di.dfs_order[b->index]]; + if (di.dfs_to_bb[d]) + et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]); + } - if (di.dfs_to_bb[d]) - et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b)); + free_dom_info (&di); + dom_computed[dir] = DOM_NO_FAST_QUERY; } - free_dom_info (&di); - return info; + compute_dom_fast_query (dir); } -/* Free dominance information. */ +/* Free dominance information for direction DIR. */ void -free_dominance_info (info) - dominance_info info; +free_dominance_info (enum cdi_direction dir) { basic_block bb; - /* Allow users to create new basic block without setting up the dominance - information for them. */ - FOR_EACH_BB (bb) - if (bb->index < (int)(info->varray->num_elements - 2) - && BB_NODE (info, bb)) - delete_from_dominance_info (info, bb); - delete_from_dominance_info (info, ENTRY_BLOCK_PTR); - delete_from_dominance_info (info, EXIT_BLOCK_PTR); - et_forest_delete (info->forest); - VARRAY_GROW (info->varray, 0); - free (info); + if (!dom_info_available_p (dir)) + return; + + FOR_ALL_BB (bb) + { + et_free_tree_force (bb->dom[dir]); + bb->dom[dir] = NULL; + } + + n_bbs_in_dom_tree[dir] = 0; + + dom_computed[dir] = DOM_NONE; } /* Return the immediate dominator of basic block BB. */ basic_block -get_immediate_dominator (dom, bb) - dominance_info dom; - basic_block bb; +get_immediate_dominator (enum cdi_direction dir, basic_block bb) { - return et_forest_node_value (dom->forest, - et_forest_parent (dom->forest, - BB_NODE (dom, bb))); + struct et_node *node = bb->dom[dir]; + + gcc_assert (dom_computed[dir]); + + if (!node->father) + return NULL; + + return node->father->data; } /* Set the immediate dominator of the block possibly removing existing edge. NULL can be used to remove any edge. */ inline void -set_immediate_dominator (dom, bb, dominated_by) - dominance_info dom; - basic_block bb, dominated_by; +set_immediate_dominator (enum cdi_direction dir, basic_block bb, + basic_block dominated_by) { - void *aux_bb_node; - et_forest_node_t bb_node = BB_NODE (dom, bb); + struct et_node *node = bb->dom[dir]; + + gcc_assert (dom_computed[dir]); - aux_bb_node = et_forest_parent (dom->forest, bb_node); - if (aux_bb_node) - et_forest_remove_edge (dom->forest, aux_bb_node, bb_node); - if (dominated_by != NULL) + if (node->father) { - if (bb == dominated_by) - abort (); - if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node)) - abort (); + if (node->father->data == dominated_by) + return; + et_split (node); } + + if (dominated_by) + et_set_father (node, dominated_by->dom[dir]); + + if (dom_computed[dir] == DOM_OK) + dom_computed[dir] = DOM_NO_FAST_QUERY; } -/* Store all basic blocks dominated by BB into BBS and return their number. */ +/* Store all basic blocks immediately dominated by BB into BBS and return + their number. */ int -get_dominated_by (dom, bb, bbs) - dominance_info dom; - basic_block bb; - basic_block **bbs; +get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) { - int n, i; + int n; + struct et_node *node = bb->dom[dir], *son = node->son, *ason; + + gcc_assert (dom_computed[dir]); + + if (!son) + { + *bbs = NULL; + return 0; + } + + for (ason = son->right, n = 1; ason != son; ason = ason->right) + n++; + + *bbs = xmalloc (n * sizeof (basic_block)); + (*bbs)[0] = son->data; + for (ason = son->right, n = 1; ason != son; ason = ason->right) + (*bbs)[n++] = ason->data; - *bbs = xmalloc (n_basic_blocks * sizeof (basic_block)); - n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs); - for (i = 0; i < n; i++) - (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]); return n; } +/* Find all basic blocks that are immediately dominated (in direction DIR) + by some block between N_REGION ones stored in REGION, except for blocks + in the REGION itself. The found blocks are stored to DOMS and their number + is returned. */ + +unsigned +get_dominated_by_region (enum cdi_direction dir, basic_block *region, + unsigned n_region, basic_block *doms) +{ + unsigned n_doms = 0, i; + basic_block dom; + + for (i = 0; i < n_region; i++) + region[i]->flags |= BB_DUPLICATED; + for (i = 0; i < n_region; i++) + for (dom = first_dom_son (dir, region[i]); + dom; + dom = next_dom_son (dir, dom)) + if (!(dom->flags & BB_DUPLICATED)) + doms[n_doms++] = dom; + for (i = 0; i < n_region; i++) + region[i]->flags &= ~BB_DUPLICATED; + + return n_doms; +} + /* Redirect all edges pointing to BB to TO. */ void -redirect_immediate_dominators (dom, bb, to) - dominance_info dom; - basic_block bb; - basic_block to; +redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, + basic_block to) { - et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block)); - et_forest_node_t node = BB_NODE (dom, bb); - et_forest_node_t node2 = BB_NODE (dom, to); - int n = et_forest_enumerate_sons (dom->forest, node, bbs); - int i; + struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son; - for (i = 0; i < n; i++) + gcc_assert (dom_computed[dir]); + + if (!bb_node->son) + return; + + while (bb_node->son) { - et_forest_remove_edge (dom->forest, node, bbs[i]); - et_forest_add_edge (dom->forest, node2, bbs[i]); + son = bb_node->son; + + et_split (son); + et_set_father (son, to_node); } - free (bbs); + + if (dom_computed[dir] == DOM_OK) + dom_computed[dir] = DOM_NO_FAST_QUERY; } /* Find first basic block in the tree dominating both BB1 and BB2. */ basic_block -nearest_common_dominator (dom, bb1, bb2) - dominance_info dom; - basic_block bb1; - basic_block bb2; +nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2) { + gcc_assert (dom_computed[dir]); + if (!bb1) return bb2; if (!bb2) return bb1; - return et_forest_node_value (dom->forest, - et_forest_common_ancestor (dom->forest, - BB_NODE (dom, bb1), - BB_NODE (dom, - bb2))); + + return et_nca (bb1->dom[dir], bb2->dom[dir])->data; } + +/* Find the nearest common dominator for the basic blocks in BLOCKS, + using dominance direction DIR. */ + +basic_block +nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks) +{ + unsigned i, first; + bitmap_iterator bi; + basic_block dom; + + first = bitmap_first_set_bit (blocks); + dom = BASIC_BLOCK (first); + EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) + if (dom != BASIC_BLOCK (i)) + dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i)); + + return dom; +} + + /* Return TRUE in case BB1 is dominated by BB2. */ bool -dominated_by_p (dom, bb1, bb2) - dominance_info dom; - basic_block bb1; - basic_block bb2; -{ - return nearest_common_dominator (dom, bb1, bb2) == bb2; +dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) +{ + struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir]; + + gcc_assert (dom_computed[dir]); + + if (dom_computed[dir] == DOM_OK) + return (n1->dfs_num_in >= n2->dfs_num_in + && n1->dfs_num_out <= n2->dfs_num_out); + + return et_below (n1, n2); } /* Verify invariants of dominator structure. */ void -verify_dominators (dom) - dominance_info dom; +verify_dominators (enum cdi_direction dir) { int err = 0; basic_block bb; + gcc_assert (dom_info_available_p (dir)); + FOR_EACH_BB (bb) { basic_block dom_bb; + basic_block imm_bb; - dom_bb = recount_dominator (dom, bb); - if (dom_bb != get_immediate_dominator (dom, bb)) + dom_bb = recount_dominator (dir, bb); + imm_bb = get_immediate_dominator (dir, bb); + if (dom_bb != imm_bb) { - error ("dominator of %d should be %d, not %d", - bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index); + if ((dom_bb == NULL) || (imm_bb == NULL)) + error ("dominator of %d status unknown", bb->index); + else + error ("dominator of %d should be %d, not %d", + bb->index, dom_bb->index, imm_bb->index); err = 1; } } - if (err) - abort (); + + if (dir == CDI_DOMINATORS) + { + FOR_EACH_BB (bb) + { + if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR)) + { + error ("ENTRY does not dominate bb %d", bb->index); + err = 1; + } + } + } + + gcc_assert (!err); } -/* Recount dominator of BB. */ +/* Determine immediate dominator (or postdominator, according to DIR) of BB, + assuming that dominators of other blocks are correct. We also use it to + recompute the dominators in a restricted area, by iterating it until it + reaches a fixed point. */ + basic_block -recount_dominator (dom, bb) - dominance_info dom; - basic_block bb; +recount_dominator (enum cdi_direction dir, basic_block bb) { - basic_block dom_bb = NULL; - edge e; + basic_block dom_bb = NULL; + edge e; + edge_iterator ei; - for (e = bb->pred; e; e = e->pred_next) - { - if (!dominated_by_p (dom, e->src, bb)) - dom_bb = nearest_common_dominator (dom, dom_bb, e->src); - } + gcc_assert (dom_computed[dir]); - return dom_bb; + if (dir == CDI_DOMINATORS) + { + FOR_EACH_EDGE (e, ei, bb->preds) + { + /* Ignore the predecessors that either are not reachable from + the entry block, or whose dominator was not determined yet. */ + if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR)) + continue; + + if (!dominated_by_p (dir, e->src, bb)) + dom_bb = nearest_common_dominator (dir, dom_bb, e->src); + } + } + else + { + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (!dominated_by_p (dir, e->dest, bb)) + dom_bb = nearest_common_dominator (dir, dom_bb, e->dest); + } + } + + return dom_bb; } /* Iteratively recount dominators of BBS. The change is supposed to be local and not to grow further. */ void -iterate_fix_dominators (dom, bbs, n) - dominance_info dom; - basic_block *bbs; - int n; +iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) { int i, changed = 1; basic_block old_dom, new_dom; + gcc_assert (dom_computed[dir]); + + for (i = 0; i < n; i++) + set_immediate_dominator (dir, bbs[i], NULL); + while (changed) { changed = 0; for (i = 0; i < n; i++) { - old_dom = get_immediate_dominator (dom, bbs[i]); - new_dom = recount_dominator (dom, bbs[i]); + old_dom = get_immediate_dominator (dir, bbs[i]); + new_dom = recount_dominator (dir, bbs[i]); if (old_dom != new_dom) { changed = 1; - set_immediate_dominator (dom, bbs[i], new_dom); + set_immediate_dominator (dir, bbs[i], new_dom); } } } + + for (i = 0; i < n; i++) + gcc_assert (get_immediate_dominator (dir, bbs[i])); } void -add_to_dominance_info (dom, bb) - dominance_info dom; - basic_block bb; +add_to_dominance_info (enum cdi_direction dir, basic_block bb) { - VARRAY_GROW (dom->varray, last_basic_block + 3); -#ifdef ENABLE_CHECKING - if (BB_NODE (dom, bb)) - abort (); -#endif - SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb)); + gcc_assert (dom_computed[dir]); + gcc_assert (!bb->dom[dir]); + + n_bbs_in_dom_tree[dir]++; + + bb->dom[dir] = et_new_tree (bb); + + if (dom_computed[dir] == DOM_OK) + dom_computed[dir] = DOM_NO_FAST_QUERY; } void -delete_from_dominance_info (dom, bb) - dominance_info dom; - basic_block bb; +delete_from_dominance_info (enum cdi_direction dir, basic_block bb) +{ + gcc_assert (dom_computed[dir]); + + et_free_tree (bb->dom[dir]); + bb->dom[dir] = NULL; + n_bbs_in_dom_tree[dir]--; + + if (dom_computed[dir] == DOM_OK) + dom_computed[dir] = DOM_NO_FAST_QUERY; +} + +/* Returns the first son of BB in the dominator or postdominator tree + as determined by DIR. */ + +basic_block +first_dom_son (enum cdi_direction dir, basic_block bb) +{ + struct et_node *son = bb->dom[dir]->son; + + return son ? son->data : NULL; +} + +/* Returns the next dominance son after BB in the dominator or postdominator + tree as determined by DIR, or NULL if it was the last one. */ + +basic_block +next_dom_son (enum cdi_direction dir, basic_block bb) +{ + struct et_node *next = bb->dom[dir]->right; + + return next->father->son == next ? NULL : next->data; +} + +/* Returns true if dominance information for direction DIR is available. */ + +bool +dom_info_available_p (enum cdi_direction dir) { - et_forest_remove_node (dom->forest, BB_NODE (dom, bb)); - SET_BB_NODE (dom, bb, NULL); + return dom_computed[dir] != DOM_NONE; } void -debug_dominance_info (dom) - dominance_info dom; +debug_dominance_info (enum cdi_direction dir) { basic_block bb, bb2; FOR_EACH_BB (bb) - if ((bb2 = get_immediate_dominator (dom, bb))) + if ((bb2 = get_immediate_dominator (dir, bb))) fprintf (stderr, "%i %i\n", bb->index, bb2->index); }