X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdominance.c;h=7970e242526f6aec623eb64a2ecaa4c3758e5860;hb=1ebefdcd36f307f94ec94376af932b1472089322;hp=d608391839dfd9d9c62f7fc2a5c0e2de365d045c;hpb=a8349c62da4e62b8ab039f14ee293e6a24c56026;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dominance.c b/gcc/dominance.c index d608391839d..7970e242526 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -39,6 +39,7 @@ #include "tm.h" #include "rtl.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" #include "errors.h" #include "et-forest.h" @@ -101,13 +102,17 @@ struct dom_info 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 (struct dom_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); @@ -118,6 +123,9 @@ 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. */ #define init_ar(var, type, num, content) \ @@ -139,7 +147,7 @@ void debug_dominance_info (enum cdi_direction); This initializes the contents of DI, which already must be allocated. */ static void -init_dom_info (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. */ @@ -161,6 +169,8 @@ init_dom_info (struct dom_info *di) di->dfsnum = 1; di->nodes = 0; + + di->fake_exit_edge = dir ? BITMAP_XMALLOC () : NULL; } #undef init_ar @@ -181,6 +191,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); } /* The nonrecursive variant of creating a DFS tree. DI is our working @@ -190,13 +201,14 @@ free_dom_info (struct dom_info *di) assigned their dfs number and are linked together to form a tree. */ static void -calc_dfs_tree_nonrec (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). */ @@ -204,19 +216,19 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re /* Ending block. */ basic_block ex_block; - stack = 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; } @@ -228,9 +240,9 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re /* 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. */ @@ -243,26 +255,25 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re 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) @@ -274,13 +285,13 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re 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, @@ -291,10 +302,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction re 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,25 +327,53 @@ calc_dfs_tree (struct dom_info *di, enum cdi_direction 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 (); + 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 @@ -441,6 +477,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 @@ -451,36 +489,43 @@ 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; - 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]; @@ -490,6 +535,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; @@ -531,7 +578,7 @@ assign_dfs_numbers (struct et_node *node, int *num) { assign_dfs_numbers (node->son, num); for (son = node->son->right; son != node->son; son = son->right) - assign_dfs_numbers (son, num); + assign_dfs_numbers (son, num); } node->dfs_num_out = (*num)++; @@ -546,8 +593,7 @@ compute_dom_fast_query (enum cdi_direction dir) int num = 0; basic_block bb; - if (dom_computed[dir] < DOM_NO_FAST_QUERY) - abort (); + gcc_assert (dom_info_available_p (dir)); if (dom_computed[dir] == DOM_OK) return; @@ -555,7 +601,7 @@ compute_dom_fast_query (enum cdi_direction dir) FOR_ALL_BB (bb) { if (!bb->dom[dir]->father) - assign_dfs_numbers (bb->dom[dir], &num); + assign_dfs_numbers (bb->dom[dir], &num); } dom_computed[dir] = DOM_OK; @@ -573,17 +619,17 @@ 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; - init_dom_info (&di); + init_dom_info (&di, dir); calc_dfs_tree (&di, dir); calc_idoms (&di, dir); @@ -608,7 +654,7 @@ 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) @@ -616,6 +662,9 @@ free_dominance_info (enum cdi_direction dir) delete_from_dominance_info (dir, bb); } + /* If there are any nodes left, something is wrong. */ + gcc_assert (!n_bbs_in_dom_tree[dir]); + dom_computed[dir] = DOM_NONE; } @@ -625,13 +674,12 @@ get_immediate_dominator (enum cdi_direction dir, basic_block bb) { struct et_node *node = bb->dom[dir]; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); if (!node->father) return NULL; - return node->father->data; + return node->father->data; } /* Set the immediate dominator of the block possibly removing @@ -642,13 +690,12 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb, { struct et_node *node = bb->dom[dir]; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); if (node->father) { if (node->father->data == dominated_by) - return; + return; et_split (node); } @@ -667,8 +714,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) int n; struct et_node *node = bb->dom[dir], *son = node->son, *ason; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); if (!son) { @@ -687,6 +733,32 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) 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]->rbi->duplicated = 1; + 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) + doms[n_doms++] = dom; + for (i = 0; i < n_region; i++) + region[i]->rbi->duplicated = 0; + + return n_doms; +} + /* Redirect all edges pointing to BB to TO. */ void redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, @@ -694,8 +766,7 @@ redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, { struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); if (!bb_node->son) return; @@ -716,8 +787,7 @@ redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, basic_block nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2) { - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); if (!bb1) return bb2; @@ -730,15 +800,14 @@ nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block b /* Return TRUE in case BB1 is dominated by BB2. */ bool dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2) -{ +{ struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir]; - if (!dom_computed[dir]) - abort (); + 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); + && n1->dfs_num_out <= n2->dfs_num_out); return et_below (n1, n2); } @@ -750,42 +819,78 @@ verify_dominators (enum cdi_direction dir) int err = 0; basic_block bb; - if (!dom_computed[dir]) - abort (); + 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 (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 (enum cdi_direction dir, basic_block bb) { - basic_block dom_bb = NULL; - edge e; + basic_block dom_bb = NULL; + edge e; + edge_iterator ei; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); + + 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; - for (e = bb->pred; e; e = e->pred_next) - { - if (!dominated_by_p (dir, e->src, bb)) - dom_bb = nearest_common_dominator (dir, dom_bb, e->src); - } + 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; + return dom_bb; } /* Iteratively recount dominators of BBS. The change is supposed to be local @@ -796,8 +901,10 @@ iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) int i, changed = 1; basic_block old_dom, new_dom; - if (!dom_computed[dir]) - abort (); + gcc_assert (dom_computed[dir]); + + for (i = 0; i < n; i++) + set_immediate_dominator (dir, bbs[i], NULL); while (changed) { @@ -813,17 +920,19 @@ iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) } } } + + for (i = 0; i < n; i++) + gcc_assert (get_immediate_dominator (dir, bbs[i])); } void add_to_dominance_info (enum cdi_direction dir, basic_block bb) { - if (!dom_computed[dir]) - abort (); - - if (bb->dom[dir]) - abort (); + 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) @@ -833,11 +942,11 @@ add_to_dominance_info (enum cdi_direction dir, basic_block bb) void delete_from_dominance_info (enum cdi_direction dir, basic_block bb) { - if (!dom_computed[dir]) - abort (); + 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; @@ -865,6 +974,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) {