X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=819e7d450299d9214be7bc03cee85b5f777d6327;hb=f5b1f90b7b0020267c34487a1ab6da238c3712b3;hp=278254719af907232cebda09c588e8fccf3ee258;hpb=d8b5b4fe9870aed9c10f607b488bb9b20428b8e9;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dominance.c b/gcc/dominance.c index 278254719af..819e7d45029 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -1,5 +1,5 @@ /* Calculate (post)dominators in slightly super-linear time. - Copyright (C) 2000, 2003, 2004 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,7 +30,7 @@ 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" @@ -39,9 +39,11 @@ #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" +#include "timevar.h" /* Whether the dominators and the postdominators are available. */ enum dom_state dom_computed[2]; @@ -50,8 +52,7 @@ enum dom_state dom_computed[2]; 'undefined' or 'end of list'. The name of each node is given by the dfs number of the corresponding basic block. Please note, that we include the artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to - support multiple entry points. As it has no real basic block index we use - 'last_basic_block' for that. Its dfs number is of course 1. */ + support multiple entry points. Its dfs number is of course 1. */ /* Type of Basic Block aka. TBB */ typedef unsigned int TBB; @@ -132,10 +133,10 @@ static unsigned n_bbs_in_dom_tree[2]; { \ unsigned int i = 1; /* Catch content == i. */ \ if (! (content)) \ - (var) = xcalloc ((num), sizeof (type)); \ + (var) = XCNEWVEC (type, num); \ else \ { \ - (var) = xmalloc ((num) * sizeof (type)); \ + (var) = XNEWVEC (type, (num)); \ for (i = 0; i < num; i++) \ (var)[i] = (content); \ } \ @@ -148,9 +149,7 @@ static unsigned n_bbs_in_dom_tree[2]; static void 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. */ - unsigned int num = n_basic_blocks + 1 + 1; + unsigned int num = n_basic_blocks; init_ar (di->dfs_parent, TBB, num, 0); init_ar (di->path_min, TBB, num, i); init_ar (di->key, TBB, num, i); @@ -169,7 +168,7 @@ init_dom_info (struct dom_info *di, enum cdi_direction dir) di->dfsnum = 1; di->nodes = 0; - di->fake_exit_edge = dir ? BITMAP_XMALLOC () : NULL; + di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL; } #undef init_ar @@ -190,7 +189,7 @@ free_dom_info (struct dom_info *di) free (di->set_child); free (di->dfs_order); free (di->dfs_to_bb); - BITMAP_XFREE (di->fake_exit_edge); + BITMAP_FREE (di->fake_exit_edge); } /* The nonrecursive variant of creating a DFS tree. DI is our working @@ -206,7 +205,8 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, /* 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). */ @@ -214,19 +214,19 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, /* Ending block. */ basic_block ex_block; - stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge)); + stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 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; } @@ -238,9 +238,9 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, /* 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. */ @@ -253,22 +253,22 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, 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); } gcc_assert (bn != en_block); @@ -283,13 +283,13 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, 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, @@ -300,10 +300,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, 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); } @@ -341,7 +338,7 @@ calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse) FOR_EACH_BB_REVERSE (b) { - if (b->succ) + if (EDGE_COUNT (b->succs) > 0) { if (di->dfs_order[b->index] == 0) saw_unconnected = true; @@ -374,7 +371,7 @@ calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse) di->nodes = di->dfsnum - 1; /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ - gcc_assert (di->nodes == (unsigned int) n_basic_blocks + 1); + 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 @@ -478,6 +475,8 @@ 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 @@ -488,43 +487,38 @@ calc_idoms (struct dom_info *di, enum cdi_direction 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; - /* If this block has a fake edge to exit, process that first. */ if (bitmap_bit_p (di->fake_exit_edge, bb->index)) { - e_next = e; + einext = ei; + einext.index = 0; goto do_fake_exit_edge; } } - else - e = bb->pred; /* 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 - { - b = e->src; - e_next = e->pred_next; - } + e = ei_edge (ei); + b = (reverse) ? e->dest : e->src; + einext = ei; + ei_next (&einext); + if (b == en_block) { do_fake_exit_edge: @@ -539,6 +533,8 @@ calc_idoms (struct dom_info *di, enum cdi_direction reverse) k1 = di->key[eval (di, k1)]; if (k1 < k) k = k1; + + ei = einext; } di->key[v] = k; @@ -595,7 +591,7 @@ compute_dom_fast_query (enum cdi_direction dir) int num = 0; basic_block bb; - gcc_assert (dom_computed[dir] >= DOM_NO_FAST_QUERY); + gcc_assert (dom_info_available_p (dir)); if (dom_computed[dir] == DOM_OK) return; @@ -621,18 +617,16 @@ calculate_dominance_info (enum cdi_direction dir) if (dom_computed[dir] == DOM_OK) return; - if (dom_computed[dir] != DOM_NO_FAST_QUERY) + timevar_push (TV_DOMINANCE); + if (!dom_info_available_p (dir)) { - if (dom_computed[dir] != DOM_NONE) - free_dominance_info (dir); - gcc_assert (!n_bbs_in_dom_tree[dir]); FOR_ALL_BB (b) { b->dom[dir] = et_new_tree (b); } - n_bbs_in_dom_tree[dir] = n_basic_blocks + 2; + n_bbs_in_dom_tree[dir] = n_basic_blocks; init_dom_info (&di, dir); calc_dfs_tree (&di, dir); @@ -651,6 +645,8 @@ calculate_dominance_info (enum cdi_direction dir) } compute_dom_fast_query (dir); + + timevar_pop (TV_DOMINANCE); } /* Free dominance information for direction DIR. */ @@ -659,16 +655,17 @@ free_dominance_info (enum cdi_direction dir) { basic_block bb; - if (!dom_computed[dir]) + if (!dom_info_available_p (dir)) return; FOR_ALL_BB (bb) { - delete_from_dominance_info (dir, bb); + et_free_tree_force (bb->dom[dir]); + bb->dom[dir] = NULL; } + et_free_pools (); - /* If there are any nodes left, something is wrong. */ - gcc_assert (!n_bbs_in_dom_tree[dir]); + n_bbs_in_dom_tree[dir] = 0; dom_computed[dir] = DOM_NONE; } @@ -730,7 +727,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) for (ason = son->right, n = 1; ason != son; ason = ason->right) n++; - *bbs = xmalloc (n * sizeof (basic_block)); + *bbs = XNEWVEC (basic_block, n); (*bbs)[0] = son->data; for (ason = son->right, n = 1; ason != son; ason = ason->right) (*bbs)[n++] = ason->data; @@ -751,15 +748,15 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region, basic_block dom; for (i = 0; i < n_region; i++) - region[i]->rbi->duplicated = 1; + 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->rbi->duplicated) + if (!(dom->flags & BB_DUPLICATED)) doms[n_doms++] = dom; for (i = 0; i < n_region; i++) - region[i]->rbi->duplicated = 0; + region[i]->flags &= ~BB_DUPLICATED; return n_doms; } @@ -802,6 +799,101 @@ nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block b 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; +} + +/* Given a dominator tree, we can determine whether one thing + dominates another in constant time by using two DFS numbers: + + 1. The number for when we visit a node on the way down the tree + 2. The number for when we visit a node on the way back up the tree + + You can view these as bounds for the range of dfs numbers the + nodes in the subtree of the dominator tree rooted at that node + will contain. + + The dominator tree is always a simple acyclic tree, so there are + only three possible relations two nodes in the dominator tree have + to each other: + + 1. Node A is above Node B (and thus, Node A dominates node B) + + A + | + C + / \ + B D + + + In the above case, DFS_Number_In of A will be <= DFS_Number_In of + B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is + because we must hit A in the dominator tree *before* B on the walk + down, and we will hit A *after* B on the walk back up + + 2. Node A is below node B (and thus, node B dominates node A) + + + B + | + A + / \ + C D + + In the above case, DFS_Number_In of A will be >= DFS_Number_In of + B, and DFS_Number_Out of A will be <= DFS_Number_Out of B. + + This is because we must hit A in the dominator tree *after* B on + the walk down, and we will hit A *before* B on the walk back up + + 3. Node A and B are siblings (and thus, neither dominates the other) + + C + | + D + / \ + A B + + In the above case, DFS_Number_In of A will *always* be <= + DFS_Number_In of B, and DFS_Number_Out of A will *always* be <= + DFS_Number_Out of B. This is because we will always finish the dfs + walk of one of the subtrees before the other, and thus, the dfs + numbers for one subtree can't intersect with the range of dfs + numbers for the other subtree. If you swap A and B's position in + the dominator tree, the comparison changes direction, but the point + is that both comparisons will always go the same way if there is no + dominance relationship. + + Thus, it is sufficient to write + + A_Dominates_B (node A, node B) + { + return DFS_Number_In(A) <= DFS_Number_In(B) + && DFS_Number_Out (A) >= DFS_Number_Out(B); + } + + A_Dominated_by_B (node A, node B) + { + return DFS_Number_In(A) >= DFS_Number_In(A) + && DFS_Number_Out (A) <= DFS_Number_Out(B); + } */ + /* Return TRUE in case BB1 is dominated by BB2. */ bool dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) @@ -817,6 +909,28 @@ dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) return et_below (n1, n2); } +/* Returns the entry dfs number for basic block BB, in the direction DIR. */ + +unsigned +bb_dom_dfs_in (enum cdi_direction dir, basic_block bb) +{ + struct et_node *n = bb->dom[dir]; + + gcc_assert (dom_computed[dir] == DOM_OK); + return n->dfs_num_in; +} + +/* Returns the exit dfs number for basic block BB, in the direction DIR. */ + +unsigned +bb_dom_dfs_out (enum cdi_direction dir, basic_block bb) +{ + struct et_node *n = bb->dom[dir]; + + gcc_assert (dom_computed[dir] == DOM_OK); + return n->dfs_num_out; +} + /* Verify invariants of dominator structure. */ void verify_dominators (enum cdi_direction dir) @@ -824,23 +938,27 @@ verify_dominators (enum cdi_direction dir) int err = 0; basic_block bb; - gcc_assert (dom_computed[dir]); + gcc_assert (dom_info_available_p (dir)); FOR_EACH_BB (bb) { basic_block dom_bb; + basic_block imm_bb; dom_bb = recount_dominator (dir, bb); - if (dom_bb != get_immediate_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(dir, 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 (dir == CDI_DOMINATORS - && dom_computed[dir] >= DOM_NO_FAST_QUERY) + if (dir == CDI_DOMINATORS) { FOR_EACH_BB (bb) { @@ -865,12 +983,13 @@ recount_dominator (enum cdi_direction dir, basic_block bb) { basic_block dom_bb = NULL; edge e; + edge_iterator ei; gcc_assert (dom_computed[dir]); if (dir == CDI_DOMINATORS) { - for (e = bb->pred; e; e = e->pred_next) + 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. */ @@ -883,7 +1002,7 @@ recount_dominator (enum cdi_direction dir, basic_block bb) } else { - for (e = bb->succ; e; e = e->succ_next) + 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); @@ -974,6 +1093,14 @@ next_dom_son (enum cdi_direction dir, basic_block bb) 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) +{ + return dom_computed[dir] != DOM_NONE; +} + void debug_dominance_info (enum cdi_direction dir) {