X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=d341f487ba3c322d5605808b540328c4d9e30f32;hb=a0028b3db29f2c7c8e55fe9d4efcf9f65038e7db;hp=680c4561c9d8c73d7d91de81abc34aa770468330;hpb=cd665a06e2398f370313e6ec3df029d06e9dfffe;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dominance.c b/gcc/dominance.c index 680c4561c9d..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 @@ -215,7 +213,7 @@ 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_iterator)); + stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator)); sp = 0; /* Initialize our border blocks, and the first edge. */ @@ -372,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 @@ -592,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; @@ -618,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); @@ -656,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; } @@ -748,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; } @@ -799,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) @@ -821,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) { @@ -841,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) { @@ -977,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) {