X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=d341f487ba3c322d5605808b540328c4d9e30f32;hb=a0028b3db29f2c7c8e55fe9d4efcf9f65038e7db;hp=bbb0b21484b0a5a61ad562adc8b709367426c991;hpb=8b218cb774b6bd5362fb10e938289a81027f2c44;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dominance.c b/gcc/dominance.c index bbb0b21484b..d341f487ba3 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,8 +39,9 @@ #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" /* Whether the dominators and the postdominators are available. */ @@ -50,8 +51,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; @@ -148,9 +148,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 +167,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 +188,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 +204,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 +213,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 = xmalloc ((n_basic_blocks + 1) * 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; } @@ -238,9 +237,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 +252,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 +282,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 +299,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 +337,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 +370,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 +474,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 +486,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 +532,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 +590,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 +616,15 @@ calculate_dominance_info (enum cdi_direction dir) if (dom_computed[dir] == DOM_OK) return; - if (dom_computed[dir] != DOM_NO_FAST_QUERY) + 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); @@ -659,16 +651,16 @@ 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; } - /* 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; } @@ -751,15 +743,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 +794,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) @@ -824,7 +911,7 @@ 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) { @@ -844,8 +931,7 @@ verify_dominators (enum cdi_direction dir) } } - if (dir == CDI_DOMINATORS - && dom_computed[dir] >= DOM_NO_FAST_QUERY) + if (dir == CDI_DOMINATORS) { FOR_EACH_BB (bb) { @@ -870,12 +956,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. */ @@ -888,7 +975,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); @@ -979,6 +1066,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) {