X-Git-Url: http://git.ipfire.org/?a=blobdiff_plain;f=gcc%2Fcfganal.c;h=0db040fe8ec643915c391fcadc32919ac055625f;hb=4c73896d18e03c31a811c941082a6ed94605a905;hp=651f15345528179070506803ea625b7ac5287609;hpb=3cd8c58a83c5dcd0a2f6aaea392c378dd75bff3b;p=thirdparty%2Fgcc.git diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 651f15345528..0db040fe8ec6 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1,6 +1,6 @@ /* Control flow graph analysis code for GNU compiler. Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc. + 1999, 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of GCC. @@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "coretypes.h" #include "tm.h" #include "rtl.h" +#include "obstack.h" #include "hard-reg-set.h" #include "basic-block.h" #include "insn-config.h" @@ -50,7 +51,8 @@ typedef struct depth_first_search_dsS *depth_first_search_ds; static void flow_dfs_compute_reverse_init (depth_first_search_ds); static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds, basic_block); -static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds); +static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds, + basic_block); static void flow_dfs_compute_reverse_finish (depth_first_search_ds); static bool flow_active_insn_p (rtx); @@ -67,7 +69,7 @@ flow_active_insn_p (rtx insn) programs that fail to return a value. Its effect is to keep the return value from being live across the entire function. If we allow it to be skipped, we introduce the - possibility for register livetime aborts. */ + possibility for register lifetime confusion. */ if (GET_CODE (PATTERN (insn)) == CLOBBER && REG_P (XEXP (PATTERN (insn), 0)) && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) @@ -85,7 +87,7 @@ forwarder_block_p (basic_block bb) rtx insn; if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR - || EDGE_COUNT (bb->succs) != 1) + || !single_succ_p (bb)) return false; for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) @@ -306,11 +308,15 @@ find_unreachable_blocks (void) basic_block b = *--tos; FOR_EACH_EDGE (e, ei, b->succs) - if (!(e->dest->flags & BB_REACHABLE)) - { - *tos++ = e->dest; - e->dest->flags |= BB_REACHABLE; - } + { + basic_block dest = e->dest; + + if (!(dest->flags & BB_REACHABLE)) + { + *tos++ = dest; + dest->flags |= BB_REACHABLE; + } + } } free (worklist); @@ -478,9 +484,18 @@ find_edge (basic_block pred, basic_block succ) edge e; edge_iterator ei; - FOR_EACH_EDGE (e, ei, pred->succs) - if (e->dest == succ) - return e; + if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) + { + FOR_EACH_EDGE (e, ei, pred->succs) + if (e->dest == succ) + return e; + } + else + { + FOR_EACH_EDGE (e, ei, succ->preds) + if (e->src == pred) + return e; + } return NULL; } @@ -506,13 +521,15 @@ find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ void flow_nodes_print (const char *str, const sbitmap nodes, FILE *file) { - int node; + unsigned int node; + sbitmap_iterator sbi; if (! nodes) return; fprintf (file, "%s { ", str); - EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);}); + EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi) + fprintf (file, "%d ", node); fputs ("}\n", file); } @@ -604,7 +621,7 @@ add_noreturn_fake_exit_edges (void) void connect_infinite_loops_to_exit (void) { - basic_block unvisited_block; + basic_block unvisited_block = EXIT_BLOCK_PTR; struct depth_first_search_dsS dfs_ds; /* Perform depth-first search in the reverse graph to find nodes @@ -615,7 +632,8 @@ connect_infinite_loops_to_exit (void) /* Repeatedly add fake edges, updating the unreachable nodes. */ while (1) { - unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds); + unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds, + unvisited_block); if (!unvisited_block) break; @@ -838,7 +856,8 @@ flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb) available. */ static basic_block -flow_dfs_compute_reverse_execute (depth_first_search_ds data) +flow_dfs_compute_reverse_execute (depth_first_search_ds data, + basic_block last_unvisited) { basic_block bb; edge e; @@ -856,7 +875,7 @@ flow_dfs_compute_reverse_execute (depth_first_search_ds data) } /* Determine if there are unvisited basic blocks. */ - FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) + FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1))) return bb; @@ -883,10 +902,45 @@ dfs_enumerate_from (basic_block bb, int reverse, { basic_block *st, lbb; int sp = 0, tv = 0; + unsigned size; + + /* A bitmap to keep track of visited blocks. Allocating it each time + this function is called is not possible, since dfs_enumerate_from + is often used on small (almost) disjoint parts of cfg (bodies of + loops), and allocating a large sbitmap would lead to quadratic + behavior. */ + static sbitmap visited; + static unsigned v_size; + +#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2)) +#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index + 2)) +#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2)) + + /* Resize the VISITED sbitmap if necessary. */ + size = last_basic_block + 2; + if (size < 10) + size = 10; + + if (!visited) + { + + visited = sbitmap_alloc (size); + sbitmap_zero (visited); + v_size = size; + } + else if (v_size < size) + { + /* Ensure that we increase the size of the sbitmap exponentially. */ + if (2 * v_size > size) + size = 2 * v_size; + + visited = sbitmap_resize (visited, size, 0); + v_size = size; + } st = xcalloc (rslt_max, sizeof (basic_block)); rslt[tv++] = st[sp++] = bb; - bb->flags |= BB_VISITED; + MARK_VISITED (bb); while (sp) { edge e; @@ -895,105 +949,94 @@ dfs_enumerate_from (basic_block bb, int reverse, if (reverse) { FOR_EACH_EDGE (e, ei, lbb->preds) - if (!(e->src->flags & BB_VISITED) && predicate (e->src, data)) + if (!VISITED_P (e->src) && predicate (e->src, data)) { gcc_assert (tv != rslt_max); rslt[tv++] = st[sp++] = e->src; - e->src->flags |= BB_VISITED; + MARK_VISITED (e->src); } } else { FOR_EACH_EDGE (e, ei, lbb->succs) - if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data)) + if (!VISITED_P (e->dest) && predicate (e->dest, data)) { gcc_assert (tv != rslt_max); rslt[tv++] = st[sp++] = e->dest; - e->dest->flags |= BB_VISITED; + MARK_VISITED (e->dest); } } } free (st); for (sp = 0; sp < tv; sp++) - rslt[sp]->flags &= ~BB_VISITED; + UNMARK_VISITED (rslt[sp]); return tv; +#undef MARK_VISITED +#undef UNMARK_VISITED +#undef VISITED_P } -/* Computing the Dominance Frontier: +/* Compute dominance frontiers, ala Harvey, Ferrante, et al. + + This algorithm can be found in Timothy Harvey's PhD thesis, at + http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative + dominance algorithms. - As described in Morgan, section 3.5, this may be done simply by - walking the dominator tree bottom-up, computing the frontier for - the children before the parent. When considering a block B, - there are two cases: + First, we identify each join point, j (any node with more than one + incoming edge is a join point). - (1) A flow graph edge leaving B that does not lead to a child - of B in the dominator tree must be a block that is either equal - to B or not dominated by B. Such blocks belong in the frontier - of B. + We then examine each predecessor, p, of j and walk up the dominator tree + starting at p. + + We stop the walk when we reach j's immediate dominator - j is in the + dominance frontier of each of the nodes in the walk, except for j's + immediate dominator. Intuitively, all of the rest of j's dominators are + shared by j's predecessors as well. + Since they dominate j, they will not have j in their dominance frontiers. + + The number of nodes touched by this algorithm is equal to the size + of the dominance frontiers, no more, no less. +*/ - (2) Consider a block X in the frontier of one of the children C - of B. If X is not equal to B and is not dominated by B, it - is in the frontier of B. */ static void -compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done) +compute_dominance_frontiers_1 (bitmap *frontiers) { - edge e; + edge p; edge_iterator ei; - basic_block c; - - SET_BIT (done, bb->index); - - /* Do the frontier of the children first. Not all children in the - dominator tree (blocks dominated by this one) are children in the - CFG, so check all blocks. */ - for (c = first_dom_son (CDI_DOMINATORS, bb); - c; - c = next_dom_son (CDI_DOMINATORS, c)) - { - if (! TEST_BIT (done, c->index)) - compute_dominance_frontiers_1 (frontiers, c, done); - } - - /* Find blocks conforming to rule (1) above. */ - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (e->dest == EXIT_BLOCK_PTR) - continue; - if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb) - bitmap_set_bit (frontiers[bb->index], e->dest->index); - } - - /* Find blocks conforming to rule (2). */ - for (c = first_dom_son (CDI_DOMINATORS, bb); - c; - c = next_dom_son (CDI_DOMINATORS, c)) + basic_block b; + FOR_EACH_BB (b) { - unsigned x; - bitmap_iterator bi; - - EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi) + if (EDGE_COUNT (b->preds) >= 2) { - if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb) - bitmap_set_bit (frontiers[bb->index], x); + FOR_EACH_EDGE (p, ei, b->preds) + { + basic_block runner = p->src; + basic_block domsb; + if (runner == ENTRY_BLOCK_PTR) + continue; + + domsb = get_immediate_dominator (CDI_DOMINATORS, b); + while (runner != domsb) + { + bitmap_set_bit (frontiers[runner->index], + b->index); + runner = get_immediate_dominator (CDI_DOMINATORS, + runner); + } + } } } -} - +} + void compute_dominance_frontiers (bitmap *frontiers) { - sbitmap done = sbitmap_alloc (last_basic_block); - timevar_push (TV_DOM_FRONTIERS); - sbitmap_zero (done); - - compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done); - - sbitmap_free (done); + compute_dominance_frontiers_1 (frontiers); timevar_pop (TV_DOM_FRONTIERS); }