diff options
-rw-r--r-- | gcc/ChangeLog | 43 | ||||
-rw-r--r-- | gcc/Makefile.in | 8 | ||||
-rw-r--r-- | gcc/basic-block.h | 12 | ||||
-rw-r--r-- | gcc/cfghooks.c | 10 | ||||
-rw-r--r-- | gcc/cfgloopanal.c | 218 | ||||
-rw-r--r-- | gcc/cfgloopmanip.c | 40 | ||||
-rw-r--r-- | gcc/dominance.c | 417 | ||||
-rw-r--r-- | gcc/et-forest.c | 17 | ||||
-rw-r--r-- | gcc/et-forest.h | 1 | ||||
-rw-r--r-- | gcc/gcse.c | 17 | ||||
-rw-r--r-- | gcc/graphds.c | 473 | ||||
-rw-r--r-- | gcc/graphds.h | 63 | ||||
-rw-r--r-- | gcc/lambda-code.c | 2 | ||||
-rw-r--r-- | gcc/loop-doloop.c | 8 | ||||
-rw-r--r-- | gcc/loop-unroll.c | 26 | ||||
-rw-r--r-- | gcc/tree-cfg.c | 16 | ||||
-rw-r--r-- | gcc/tree-ssa-threadupdate.c | 6 |
17 files changed, 1023 insertions, 354 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a336afc..2214ddf 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,46 @@ +2007-06-03 Zdenek Dvorak <dvorakz@suse.cz> + + * cfgloopmanip.c (remove_path, loopify, duplicate_loop_to_header_edge): + Change dom_bbs to vector. Add argument to iterate_fix_dominators call. + * loop-unroll.c (unroll_loop_runtime_iterations): Ditto. + * tree-cfg.c (tree_duplicate_sese_region): Change doms to vector. + Add argument to iterate_fix_dominators call. + (remove_edge_and_dominated_blocks): Pass vector to bbs_to_fix_dom. + * gcse.c (hoist_code): Change domby to vector. + * cfghooks.c (make_forwarder_block): Change doms_to_fix to vector. + Add argument to iterate_fix_dominators call. + * loop-doloop.c (doloop_modify): Changed recount_dominator to + recompute_dominator. + * lambda-code.c (perfect_nestify): Ditto. + * cfgloopanal.c: Include graphds.h. + (struct edge, struct vertex, struct graph, dump_graph, new_graph, + add_edge, dfs, for_each_edge, free_graph): Moved to graphds.c. + (mark_irreducible_loops): Use graphds_scc. Remove argument from + add_edge call. + * graphds.c: New file. + * graphds.h: New file. + * dominance.c: Include vecprim.h, pointer-set.h and graphds.h. + (get_dominated_by, get_dominated_by_region): Change return type to + vector. + (verify_dominators): Recompute all dominators and compare the results. + (recount_dominator): Renamed to ... + (recompute_dominator): ... this. Do not check that the block is + dominated by entry. + (iterate_fix_dominators): Reimplemented. + (prune_bbs_to_update_dominators, root_of_dom_tree, + determine_dominators_for_sons): New functions. + * et-forest.c (et_root): New function. + * et-forest.h (et_root): Declare. + * Makefile.in (graphds.o): Add. + (cfgloopanal.o): Add graphds.h dependency. + (dominance.o): Add graphds.h, vecprim.h and pointer-set.h dependency. + * basic-block.h (get_dominated_by, get_dominated_by_region, + iterate_fix_dominators): Declaration changed. + (recount_dominator): Renamed to ... + (recompute_dominator): ... this. + * tree-ssa-threadupdate.c (thread_block): Free dominance info. + (thread_through_all_blocks): Do not free dominance info. + 2007-06-03 Andreas Schwab <schwab@suse.de> * config/m68k/m68k.c (override_options): Don't override diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 605a0bd..a8d5046 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1009,6 +1009,7 @@ OBJS-common = \ gimplify.o \ global.o \ graph.o \ + graphds.o \ gtype-desc.o \ haifa-sched.o \ hooks.o \ @@ -2556,7 +2557,9 @@ cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \ $(GGC_H) cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \ $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h $(TM_H) \ - $(OBSTACK_H) output.h + $(OBSTACK_H) output.h graphds.h +graphds.o : graphds.c graphds.h $(CONFIG_H) $(SYSTEM_H) bitmap.h $(OBSTACK_H) \ + coretypes.h vec.h vecprim.h struct-equiv.o : struct-equiv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(RTL_H) hard-reg-set.h output.h $(FLAGS_H) $(RECOG_H) \ insn-config.h $(TARGET_H) $(TM_P_H) $(PARAMS_H) \ @@ -2582,7 +2585,8 @@ loop-unroll.o: loop-unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TM_H) \ output.h $(EXPR_H) coretypes.h $(TM_H) $(HASHTAB_H) $(RECOG_H) \ $(OBSTACK_H) dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ - hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h $(OBSTACK_H) toplev.h $(TIMEVAR_H) + hard-reg-set.h $(BASIC_BLOCK_H) et-forest.h $(OBSTACK_H) toplev.h \ + $(TIMEVAR_H) graphds.h vecprim.h pointer-set.h et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ et-forest.h alloc-pool.h $(BASIC_BLOCK_H) combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ diff --git a/gcc/basic-block.h b/gcc/basic-block.h index dd3bc1a..8d7dbe3 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -959,15 +959,17 @@ extern void set_immediate_dominator (enum cdi_direction, basic_block, basic_block); extern basic_block get_immediate_dominator (enum cdi_direction, basic_block); extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block); -extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **); -extern unsigned get_dominated_by_region (enum cdi_direction, basic_block *, - unsigned, basic_block *); +extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block); +extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction, + basic_block *, + unsigned); extern void add_to_dominance_info (enum cdi_direction, basic_block); extern void delete_from_dominance_info (enum cdi_direction, basic_block); -basic_block recount_dominator (enum cdi_direction, basic_block); +basic_block recompute_dominator (enum cdi_direction, basic_block); extern void redirect_immediate_dominators (enum cdi_direction, basic_block, basic_block); -extern void iterate_fix_dominators (enum cdi_direction, basic_block *, int); +extern void iterate_fix_dominators (enum cdi_direction, + VEC (basic_block, heap) *, bool); extern void verify_dominators (enum cdi_direction); extern basic_block first_dom_son (enum cdi_direction, basic_block); extern basic_block next_dom_son (enum cdi_direction, basic_block); diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c index 51405bb..beb377b 100644 --- a/gcc/cfghooks.c +++ b/gcc/cfghooks.c @@ -735,11 +735,11 @@ make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge), if (dom_info_available_p (CDI_DOMINATORS)) { - basic_block doms_to_fix[2]; - - doms_to_fix[0] = dummy; - doms_to_fix[1] = bb; - iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2); + VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2); + VEC_quick_push (basic_block, doms_to_fix, dummy); + VEC_quick_push (basic_block, doms_to_fix, bb); + iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false); + VEC_free (basic_block, heap, doms_to_fix); } if (current_loops != NULL) diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c index 760542a..30c8718 100644 --- a/gcc/cfgloopanal.c +++ b/gcc/cfgloopanal.c @@ -29,6 +29,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "cfgloop.h" #include "expr.h" #include "output.h" +#include "graphds.h" /* Checks whether BB is executed exactly once in each LOOP iteration. */ @@ -50,157 +51,6 @@ just_once_each_iteration_p (const struct loop *loop, basic_block bb) return true; } -/* Structure representing edge of a graph. */ - -struct edge -{ - int src, dest; /* Source and destination. */ - struct edge *pred_next, *succ_next; - /* Next edge in predecessor and successor lists. */ - void *data; /* Data attached to the edge. */ -}; - -/* Structure representing vertex of a graph. */ - -struct vertex -{ - struct edge *pred, *succ; - /* Lists of predecessors and successors. */ - int component; /* Number of dfs restarts before reaching the - vertex. */ - int post; /* Postorder number. */ -}; - -/* Structure representing a graph. */ - -struct graph -{ - int n_vertices; /* Number of vertices. */ - struct vertex *vertices; - /* The vertices. */ -}; - -/* Dumps graph G into F. */ - -extern void dump_graph (FILE *, struct graph *); - -void -dump_graph (FILE *f, struct graph *g) -{ - int i; - struct edge *e; - - for (i = 0; i < g->n_vertices; i++) - { - if (!g->vertices[i].pred - && !g->vertices[i].succ) - continue; - - fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component); - for (e = g->vertices[i].pred; e; e = e->pred_next) - fprintf (f, " %d", e->src); - fprintf (f, "\n"); - - fprintf (f, "\t->"); - for (e = g->vertices[i].succ; e; e = e->succ_next) - fprintf (f, " %d", e->dest); - fprintf (f, "\n"); - } -} - -/* Creates a new graph with N_VERTICES vertices. */ - -static struct graph * -new_graph (int n_vertices) -{ - struct graph *g = XNEW (struct graph); - - g->n_vertices = n_vertices; - g->vertices = XCNEWVEC (struct vertex, n_vertices); - - return g; -} - -/* Adds an edge from F to T to graph G, with DATA attached. */ - -static void -add_edge (struct graph *g, int f, int t, void *data) -{ - struct edge *e = xmalloc (sizeof (struct edge)); - - e->src = f; - e->dest = t; - e->data = data; - - e->pred_next = g->vertices[t].pred; - g->vertices[t].pred = e; - - e->succ_next = g->vertices[f].succ; - g->vertices[f].succ = e; -} - -/* Runs dfs search over vertices of G, from NQ vertices in queue QS. - The vertices in postorder are stored into QT. If FORWARD is false, - backward dfs is run. */ - -static void -dfs (struct graph *g, int *qs, int nq, int *qt, bool forward) -{ - int i, tick = 0, v, comp = 0, top; - struct edge *e; - struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices); - - for (i = 0; i < g->n_vertices; i++) - { - g->vertices[i].component = -1; - g->vertices[i].post = -1; - } - -#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred) -#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next) -#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest) -#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src) - - for (i = 0; i < nq; i++) - { - v = qs[i]; - if (g->vertices[v].post != -1) - continue; - - g->vertices[v].component = comp++; - e = FST_EDGE (v); - top = 0; - - while (1) - { - while (e && g->vertices[EDGE_DEST (e)].component != -1) - e = NEXT_EDGE (e); - - if (!e) - { - if (qt) - qt[tick] = v; - g->vertices[v].post = tick++; - - if (!top) - break; - - e = stack[--top]; - v = EDGE_SRC (e); - e = NEXT_EDGE (e); - continue; - } - - stack[top++] = e; - v = EDGE_DEST (e); - e = FST_EDGE (v); - g->vertices[v].component = comp - 1; - } - } - - free (stack); -} - /* Marks the edge E in graph G irreducible if it connects two vertices in the same scc. */ @@ -221,38 +71,6 @@ check_irred (struct graph *g, struct edge *e) real->src->flags |= BB_IRREDUCIBLE_LOOP; } -/* Runs CALLBACK for all edges in G. */ - -static void -for_each_edge (struct graph *g, - void (callback) (struct graph *, struct edge *)) -{ - struct edge *e; - int i; - - for (i = 0; i < g->n_vertices; i++) - for (e = g->vertices[i].succ; e; e = e->succ_next) - callback (g, e); -} - -/* Releases the memory occupied by G. */ - -static void -free_graph (struct graph *g) -{ - struct edge *e, *n; - int i; - - for (i = 0; i < g->n_vertices; i++) - for (e = g->vertices[i].succ; e; e = n) - { - n = e->succ_next; - free (e); - } - free (g->vertices); - free (g); -} - /* Marks blocks and edges that are part of non-recognized loops; i.e. we throw away all latch edges and mark blocks inside any remaining cycle. Everything is a bit complicated due to fact we do not want to do this @@ -271,15 +89,11 @@ mark_irreducible_loops (void) basic_block act; edge e; edge_iterator ei; - int i, src, dest; + int src, dest; + unsigned depth; struct graph *g; int num = number_of_loops (); - int *queue1 = XNEWVEC (int, last_basic_block + num); - int *queue2 = XNEWVEC (int, last_basic_block + num); - int nq; - unsigned depth; - struct loop *cloop, *loop; - loop_iterator li; + struct loop *cloop; gcc_assert (current_loops != NULL); @@ -332,34 +146,16 @@ mark_irreducible_loops (void) src = LOOP_REPR (cloop); } - add_edge (g, src, dest, e); + add_edge (g, src, dest)->data = e; } - /* Find the strongly connected components. Use the algorithm of Tarjan -- - first determine the postorder dfs numbering in reversed graph, then - run the dfs on the original graph in the order given by decreasing - numbers assigned by the previous pass. */ - nq = 0; - FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) - { - queue1[nq++] = BB_REPR (act); - } - - FOR_EACH_LOOP (li, loop, 0) - { - queue1[nq++] = LOOP_REPR (loop); - } - dfs (g, queue1, nq, queue2, false); - for (i = 0; i < nq; i++) - queue1[i] = queue2[nq - i - 1]; - dfs (g, queue1, nq, NULL, true); + /* Find the strongly connected components. */ + graphds_scc (g, NULL); /* Mark the irreducible loops. */ for_each_edge (g, check_irred); free_graph (g); - free (queue1); - free (queue2); current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; } diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 99b41d7..4568833 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -276,8 +276,9 @@ bool remove_path (edge e) { edge ae; - basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; - int i, nrem, n_bord_bbs, n_dom_bbs, nreml; + basic_block *rem_bbs, *bord_bbs, from, bb; + VEC (basic_block, heap) *dom_bbs; + int i, nrem, n_bord_bbs, nreml; sbitmap seen; bool irred_invalidated = false; struct loop **deleted_loop; @@ -338,7 +339,7 @@ remove_path (edge e) /* Remove the path. */ from = e->src; remove_branch (e); - dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); + dom_bbs = NULL; /* Cancel loops contained in the path. */ deleted_loop = XNEWVEC (struct loop *, nrem); @@ -355,7 +356,6 @@ remove_path (edge e) free (deleted_loop); /* Find blocks whose dominators may be affected. */ - n_dom_bbs = 0; sbitmap_zero (seen); for (i = 0; i < n_bord_bbs; i++) { @@ -370,14 +370,14 @@ remove_path (edge e) ldom; ldom = next_dom_son (CDI_DOMINATORS, ldom)) if (!dominated_by_p (CDI_DOMINATORS, from, ldom)) - dom_bbs[n_dom_bbs++] = ldom; + VEC_safe_push (basic_block, heap, dom_bbs, ldom); } free (seen); /* Recount dominators. */ - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); - free (dom_bbs); + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true); + VEC_free (basic_block, heap, dom_bbs); free (bord_bbs); /* Fix placements of basic blocks inside loops and the placement of @@ -472,8 +472,9 @@ loopify (edge latch_edge, edge header_edge, { basic_block succ_bb = latch_edge->dest; basic_block pred_bb = header_edge->src; - basic_block *dom_bbs, *body; - unsigned n_dom_bbs, i; + basic_block *body; + VEC (basic_block, heap) *dom_bbs; + unsigned i; sbitmap seen; struct loop *loop = alloc_loop (); struct loop *outer = loop_outer (succ_bb->loop_father); @@ -528,8 +529,7 @@ loopify (edge latch_edge, edge header_edge, scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE); /* Update dominators of blocks outside of LOOP. */ - dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); - n_dom_bbs = 0; + dom_bbs = NULL; seen = sbitmap_alloc (last_basic_block); sbitmap_zero (seen); body = get_loop_body (loop); @@ -547,15 +547,15 @@ loopify (edge latch_edge, edge header_edge, if (!TEST_BIT (seen, ldom->index)) { SET_BIT (seen, ldom->index); - dom_bbs[n_dom_bbs++] = ldom; + VEC_safe_push (basic_block, heap, dom_bbs, ldom); } } - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false); free (body); free (seen); - free (dom_bbs); + VEC_free (basic_block, heap, dom_bbs); return loop; } @@ -1054,23 +1054,23 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, /* Update dominators of outer blocks if affected. */ for (i = 0; i < n; i++) { - basic_block dominated, dom_bb, *dom_bbs; - int n_dom_bbs,j; + basic_block dominated, dom_bb; + VEC (basic_block, heap) *dom_bbs; + unsigned j; bb = bbs[i]; bb->aux = 0; - n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs); - for (j = 0; j < n_dom_bbs; j++) + dom_bbs = get_dominated_by (CDI_DOMINATORS, bb); + for (j = 0; VEC_iterate (basic_block, dom_bbs, j, dominated); j++) { - dominated = dom_bbs[j]; if (flow_bb_inside_loop_p (loop, dominated)) continue; dom_bb = nearest_common_dominator ( CDI_DOMINATORS, first_active[i], first_active_latch); set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb); } - free (dom_bbs); + VEC_free (basic_block, heap, dom_bbs); } free (first_active); diff --git a/gcc/dominance.c b/gcc/dominance.c index a9af9d5..57a9df6 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -44,6 +44,9 @@ #include "toplev.h" #include "et-forest.h" #include "timevar.h" +#include "vecprim.h" +#include "pointer-set.h" +#include "graphds.h" /* Whether the dominators and the postdominators are available. */ static enum dom_state dom_computed[2]; @@ -735,45 +738,39 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb, dom_computed[dir_index] = DOM_NO_FAST_QUERY; } -/* Store all basic blocks immediately dominated by BB into BBS and return - their number. */ -int -get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) +/* Returns the list of basic blocks immediately dominated by BB, in the + direction DIR. */ +VEC (basic_block, heap) * +get_dominated_by (enum cdi_direction dir, basic_block bb) { - unsigned int dir_index = dom_convert_dir_to_idx (dir); int n; + unsigned int dir_index = dom_convert_dir_to_idx (dir); struct et_node *node = bb->dom[dir_index], *son = node->son, *ason; - + VEC (basic_block, heap) *bbs = NULL; + gcc_assert (dom_computed[dir_index]); if (!son) - { - *bbs = NULL; - return 0; - } - - for (ason = son->right, n = 1; ason != son; ason = ason->right) - n++; + return NULL; - *bbs = XNEWVEC (basic_block, n); - (*bbs)[0] = son->data; + VEC_safe_push (basic_block, heap, bbs, son->data); for (ason = son->right, n = 1; ason != son; ason = ason->right) - (*bbs)[n++] = ason->data; + VEC_safe_push (basic_block, heap, bbs, ason->data); - return n; + return bbs; } -/* 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 +/* Returns the list of 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. */ + +VEC (basic_block, heap) * get_dominated_by_region (enum cdi_direction dir, basic_block *region, - unsigned n_region, basic_block *doms) + unsigned n_region) { - unsigned n_doms = 0, i; + unsigned i; basic_block dom; + VEC (basic_block, heap) *doms = NULL; for (i = 0; i < n_region; i++) region[i]->flags |= BB_DUPLICATED; @@ -782,11 +779,11 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region, dom; dom = next_dom_son (dir, dom)) if (!(dom->flags & BB_DUPLICATED)) - doms[n_doms++] = dom; + VEC_safe_push (basic_block, heap, doms, dom); for (i = 0; i < n_region; i++) region[i]->flags &= ~BB_DUPLICATED; - return n_doms; + return doms; } /* Redirect all edges pointing to BB to TO. */ @@ -973,40 +970,37 @@ void verify_dominators (enum cdi_direction dir) { int err = 0; - basic_block bb; + basic_block *old_dom = XNEWVEC (basic_block, last_basic_block); + basic_block bb, imm_bb; gcc_assert (dom_info_available_p (dir)); FOR_EACH_BB (bb) { - basic_block dom_bb; - basic_block imm_bb; + old_dom[bb->index] = get_immediate_dominator (dir, bb); - dom_bb = recount_dominator (dir, bb); - imm_bb = get_immediate_dominator (dir, bb); - if (dom_bb != imm_bb) + if (!old_dom[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); + error ("dominator of %d status unknown", bb->index); err = 1; } } - if (dir == CDI_DOMINATORS) + free_dominance_info (dir); + calculate_dominance_info (dir); + + FOR_EACH_BB (bb) { - FOR_EACH_BB (bb) + imm_bb = get_immediate_dominator (dir, bb); + if (old_dom[bb->index] != imm_bb) { - if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR)) - { - error ("ENTRY does not dominate bb %d", bb->index); - err = 1; - } + error ("dominator of %d should be %d, not %d", + bb->index, imm_bb->index, old_dom[bb->index]->index); + err = 1; } } + free (old_dom); gcc_assert (!err); } @@ -1016,7 +1010,7 @@ verify_dominators (enum cdi_direction dir) reaches a fixed point. */ basic_block -recount_dominator (enum cdi_direction dir, basic_block bb) +recompute_dominator (enum cdi_direction dir, basic_block bb) { unsigned int dir_index = dom_convert_dir_to_idx (dir); basic_block dom_bb = NULL; @@ -1029,11 +1023,6 @@ recount_dominator (enum cdi_direction dir, basic_block bb) { 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; - if (!dominated_by_p (dir, e->src, bb)) dom_bb = nearest_common_dominator (dir, dom_bb, e->src); } @@ -1050,37 +1039,325 @@ recount_dominator (enum cdi_direction dir, basic_block bb) return dom_bb; } -/* Iteratively recount dominators of BBS. The change is supposed to be local - and not to grow further. */ +/* Use simple heuristics (see iterate_fix_dominators) to determine dominators + of BBS. We assume that all the immediate dominators except for those of the + blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the + currently recorded immediate dominators of blocks in BBS really dominate the + blocks. The basic blocks for that we determine the dominator are removed + from BBS. */ + +static void +prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs, + bool conservative) +{ + unsigned i; + bool single; + basic_block bb, dom = NULL; + edge_iterator ei; + edge e; + + for (i = 0; VEC_iterate (basic_block, bbs, i, bb);) + { + if (bb == ENTRY_BLOCK_PTR) + goto succeed; + + if (single_pred_p (bb)) + { + set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb)); + goto succeed; + } + + if (!conservative) + goto fail; + + single = true; + dom = NULL; + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) + continue; + + if (!dom) + dom = e->src; + else + { + single = false; + dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src); + } + } + + gcc_assert (dom != NULL); + if (single + || find_edge (dom, bb)) + { + set_immediate_dominator (CDI_DOMINATORS, bb, dom); + goto succeed; + } + +fail: + i++; + continue; + +succeed: + VEC_unordered_remove (basic_block, bbs, i); + } +} + +/* Returns root of the dominance tree in the direction DIR that contains + BB. */ + +static basic_block +root_of_dom_tree (enum cdi_direction dir, basic_block bb) +{ + return et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data; +} + +/* See the comment in iterate_fix_dominators. Finds the immediate dominators + for the sons of Y, found using the SON and BROTHER arrays representing + the dominance tree of graph G. BBS maps the vertices of G to the basic + blocks. */ + +static void +determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs, + int y, int *son, int *brother) +{ + bitmap gprime; + int i, a, nc; + VEC (int, heap) **sccs; + basic_block bb, dom, ybb; + unsigned si; + edge e; + edge_iterator ei; + + if (son[y] == -1) + return; + if (y == (int) VEC_length (basic_block, bbs)) + ybb = ENTRY_BLOCK_PTR; + else + ybb = VEC_index (basic_block, bbs, y); + + if (brother[son[y]] == -1) + { + /* Handle the common case Y has just one son specially. */ + bb = VEC_index (basic_block, bbs, son[y]); + set_immediate_dominator (CDI_DOMINATORS, bb, + recompute_dominator (CDI_DOMINATORS, bb)); + identify_vertices (g, y, son[y]); + return; + } + + gprime = BITMAP_ALLOC (NULL); + for (a = son[y]; a != -1; a = brother[a]) + bitmap_set_bit (gprime, a); + + nc = graphds_scc (g, gprime); + BITMAP_FREE (gprime); + + sccs = XCNEWVEC (VEC (int, heap) *, nc); + for (a = son[y]; a != -1; a = brother[a]) + VEC_safe_push (int, heap, sccs[g->vertices[a].component], a); + + for (i = nc - 1; i >= 0; i--) + { + dom = NULL; + for (si = 0; VEC_iterate (int, sccs[i], si, a); si++) + { + bb = VEC_index (basic_block, bbs, a); + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb) + continue; + + dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src); + } + } + + gcc_assert (dom != NULL); + for (si = 0; VEC_iterate (int, sccs[i], si, a); si++) + { + bb = VEC_index (basic_block, bbs, a); + set_immediate_dominator (CDI_DOMINATORS, bb, dom); + } + } + + for (i = 0; i < nc; i++) + VEC_free (int, heap, sccs[i]); + free (sccs); + + for (a = son[y]; a != -1; a = brother[a]) + identify_vertices (g, y, a); +} + +/* Recompute dominance information for basic blocks in the set BBS. The + function assumes that the immediate dominators of all the other blocks + in CFG are correct, and that there are no unreachable blocks. + + If CONSERVATIVE is true, we additionally assume that all the ancestors of + a block of BBS in the current dominance tree dominate it. */ + void -iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n) +iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs, + bool conservative) { + unsigned i; + basic_block bb, dom; + struct graph *g; + int n, y; + size_t dom_i; + edge e; + edge_iterator ei; + struct pointer_map_t *map; + int *parent, *son, *brother; unsigned int dir_index = dom_convert_dir_to_idx (dir); - int i, changed = 1; - basic_block old_dom, new_dom; + /* We only support updating dominators. There are some problems with + updating postdominators (need to add fake edges from infinite loops + and noreturn functions), and since we do not currently use + iterate_fix_dominators for postdominators, any attempt to handle these + problems would be unused, untested, and almost surely buggy. We keep + the DIR argument for consistency with the rest of the dominator analysis + interface. */ + gcc_assert (dir == CDI_DOMINATORS); gcc_assert (dom_computed[dir_index]); - for (i = 0; i < n; i++) - set_immediate_dominator (dir, bbs[i], NULL); + /* The algorithm we use takes inspiration from the following papers, although + the details are quite different from any of them: + + [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the + Dominator Tree of a Reducible Flowgraph + [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of + dominator trees + [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance + Algorithm + + First, we use the following heuristics to decrease the size of the BBS + set: + a) if BB has a single predecessor, then its immediate dominator is this + predecessor + additionally, if CONSERVATIVE is true: + b) if all the predecessors of BB except for one (X) are dominated by BB, + then X is the immediate dominator of BB + c) if the nearest common ancestor of the predecessors of BB is X and + X -> BB is an edge in CFG, then X is the immediate dominator of BB + + Then, we need to establish the dominance relation among the basic blocks + in BBS. We split the dominance tree by removing the immediate dominator + edges from BBS, creating a forrest F. We form a graph G whose vertices + are BBS and ENTRY and X -> Y is an edge of G if there exists an edge + X' -> Y in CFG such that X' belongs to the tree of the dominance forrest + whose root is X. We then determine dominance tree of G. Note that + for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G. + In this step, we can use arbitrary algorithm to determine dominators. + We decided to prefer the algorithm [3] to the algorithm of + Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding + 10 during gcc bootstrap), and [3] should perform better in this case. + + Finally, we need to determine the immediate dominators for the basic + blocks of BBS. If the immediate dominator of X in G is Y, then + the immediate dominator of X in CFG belongs to the tree of F rooted in + Y. We process the dominator tree T of G recursively, starting from leaves. + Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the + subtrees of the dominance tree of CFG rooted in X_i are already correct. + Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make + the following observations: + (i) the immediate dominator of all blocks in a strongly connected + component of G' is the same + (ii) if X has no predecessors in G', then the immediate dominator of X + is the nearest common ancestor of the predecessors of X in the + subtree of F rooted in Y + Therefore, it suffices to find the topological ordering of G', and + process the nodes X_i in this order using the rules (i) and (ii). + Then, we contract all the nodes X_i with Y in G, so that the further + steps work correctly. */ + + if (!conservative) + { + /* Split the tree now. If the idoms of blocks in BBS are not + conservatively correct, setting the dominators using the + heuristics in prune_bbs_to_update_dominators could + create cycles in the dominance "tree", and cause ICE. */ + for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++) + set_immediate_dominator (CDI_DOMINATORS, bb, NULL); + } + + prune_bbs_to_update_dominators (bbs, conservative); + n = VEC_length (basic_block, bbs); + + if (n == 0) + return; - while (changed) + if (n == 1) { - changed = 0; - for (i = 0; i < n; i++) + bb = VEC_index (basic_block, bbs, 0); + set_immediate_dominator (CDI_DOMINATORS, bb, + recompute_dominator (CDI_DOMINATORS, bb)); + return; + } + + /* Construct the graph G. */ + map = pointer_map_create (); + for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++) + { + /* If the dominance tree is conservatively correct, split it now. */ + if (conservative) + set_immediate_dominator (CDI_DOMINATORS, bb, NULL); + *pointer_map_insert (map, bb) = (void *) (size_t) i; + } + *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n; + + g = new_graph (n + 1); + for (y = 0; y < g->n_vertices; y++) + g->vertices[y].data = BITMAP_ALLOC (NULL); + for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++) + { + FOR_EACH_EDGE (e, ei, bb->preds) { - old_dom = get_immediate_dominator (dir, bbs[i]); - new_dom = recount_dominator (dir, bbs[i]); - if (old_dom != new_dom) - { - changed = 1; - set_immediate_dominator (dir, bbs[i], new_dom); - } + dom = root_of_dom_tree (CDI_DOMINATORS, e->src); + if (dom == bb) + continue; + + dom_i = (size_t) *pointer_map_contains (map, dom); + + /* Do not include parallel edges to G. */ + if (bitmap_bit_p (g->vertices[dom_i].data, i)) + continue; + + bitmap_set_bit (g->vertices[dom_i].data, i); + add_edge (g, dom_i, i); } } + for (y = 0; y < g->n_vertices; y++) + BITMAP_FREE (g->vertices[y].data); + pointer_map_destroy (map); + + /* Find the dominator tree of G. */ + son = XNEWVEC (int, n + 1); + brother = XNEWVEC (int, n + 1); + parent = XNEWVEC (int, n + 1); + graphds_domtree (g, n, parent, son, brother); + + /* Finally, traverse the tree and find the immediate dominators. */ + for (y = n; son[y] != -1; y = son[y]) + continue; + while (y != -1) + { + determine_dominators_for_sons (g, bbs, y, son, brother); + + if (brother[y] != -1) + { + y = brother[y]; + while (son[y] != -1) + y = son[y]; + } + else + y = parent[y]; + } + + free (son); + free (brother); + free (parent); - for (i = 0; i < n; i++) - gcc_assert (get_immediate_dominator (dir, bbs[i])); + free_graph (g); } void diff --git a/gcc/et-forest.c b/gcc/et-forest.c index b8e5527..b9dacc9 100644 --- a/gcc/et-forest.c +++ b/gcc/et-forest.c @@ -747,3 +747,20 @@ et_below (struct et_node *down, struct et_node *up) return !d->next || d->next->min + d->depth >= 0; } + +/* Returns the root of the tree that contains NODE. */ + +struct et_node * +et_root (struct et_node *node) +{ + struct et_occ *occ = node->rightmost_occ, *r; + + /* The root of the tree corresponds to the rightmost occurence in the + represented path. */ + et_splay (occ); + for (r = occ; r->next; r = r->next) + continue; + et_splay (r); + + return r->of; +} diff --git a/gcc/et-forest.h b/gcc/et-forest.h index 1de715f..fd25cbe 100644 --- a/gcc/et-forest.h +++ b/gcc/et-forest.h @@ -79,6 +79,7 @@ void et_set_father (struct et_node *, struct et_node *); void et_split (struct et_node *); struct et_node *et_nca (struct et_node *, struct et_node *); bool et_below (struct et_node *, struct et_node *); +struct et_node *et_root (struct et_node *); #ifdef __cplusplus } @@ -4829,8 +4829,7 @@ static void hoist_code (void) { basic_block bb, dominated; - basic_block *domby; - unsigned int domby_len; + VEC (basic_block, heap) *domby; unsigned int i,j; struct expr **index_map; struct expr *expr; @@ -4852,7 +4851,7 @@ hoist_code (void) int found = 0; int insn_inserted_p; - domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby); + domby = get_dominated_by (CDI_DOMINATORS, bb); /* Examine each expression that is very busy at the exit of this block. These are the potentially hoistable expressions. */ for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++) @@ -4865,9 +4864,8 @@ hoist_code (void) /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it computes the expression. */ - for (j = 0; j < domby_len; j++) + for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { - dominated = domby[j]; /* Ignore self dominance. */ if (bb == dominated) continue; @@ -4906,8 +4904,8 @@ hoist_code (void) /* If we found nothing to hoist, then quit now. */ if (! found) { - free (domby); - continue; + VEC_free (basic_block, heap, domby); + continue; } /* Loop over all the hoistable expressions. */ @@ -4923,9 +4921,8 @@ hoist_code (void) /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it computes the expression. */ - for (j = 0; j < domby_len; j++) + for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { - dominated = domby[j]; /* Ignore self dominance. */ if (bb == dominated) continue; @@ -4976,7 +4973,7 @@ hoist_code (void) } } } - free (domby); + VEC_free (basic_block, heap, domby); } free (index_map); diff --git a/gcc/graphds.c b/gcc/graphds.c new file mode 100644 index 0000000..1496e09 --- /dev/null +++ b/gcc/graphds.c @@ -0,0 +1,473 @@ +/* Graph representation and manipulation functions. + Copyright (C) 2007 + Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +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, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "obstack.h" +#include "bitmap.h" +#include "vec.h" +#include "vecprim.h" +#include "graphds.h" + +/* Dumps graph G into F. */ + +void +dump_graph (FILE *f, struct graph *g) +{ + int i; + struct edge *e; + + for (i = 0; i < g->n_vertices; i++) + { + if (!g->vertices[i].pred + && !g->vertices[i].succ) + continue; + + fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component); + for (e = g->vertices[i].pred; e; e = e->pred_next) + fprintf (f, " %d", e->src); + fprintf (f, "\n"); + + fprintf (f, "\t->"); + for (e = g->vertices[i].succ; e; e = e->succ_next) + fprintf (f, " %d", e->dest); + fprintf (f, "\n"); + } +} + +/* Creates a new graph with N_VERTICES vertices. */ + +struct graph * +new_graph (int n_vertices) +{ + struct graph *g = XNEW (struct graph); + + g->n_vertices = n_vertices; + g->vertices = XCNEWVEC (struct vertex, n_vertices); + + return g; +} + +/* Adds an edge from F to T to graph G. The new edge is returned. */ + +struct edge * +add_edge (struct graph *g, int f, int t) +{ + struct edge *e = XNEW (struct edge); + struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t]; + + + e->src = f; + e->dest = t; + + e->pred_next = vt->pred; + vt->pred = e; + + e->succ_next = vf->succ; + vf->succ = e; + + return e; +} + +/* Moves all the edges incident with U to V. */ + +void +identify_vertices (struct graph *g, int v, int u) +{ + struct vertex *vv = &g->vertices[v]; + struct vertex *uu = &g->vertices[u]; + struct edge *e, *next; + + for (e = uu->succ; e; e = next) + { + next = e->succ_next; + + e->src = v; + e->succ_next = vv->succ; + vv->succ = e; + } + uu->succ = NULL; + + for (e = uu->pred; e; e = next) + { + next = e->pred_next; + + e->dest = v; + e->pred_next = vv->pred; + vv->pred = e; + } + uu->pred = NULL; +} + +/* Helper function for graphds_dfs. Returns the source vertex of E, in the + direction given by FORWARD. */ + +static inline int +dfs_edge_src (struct edge *e, bool forward) +{ + return forward ? e->src : e->dest; +} + +/* Helper function for graphds_dfs. Returns the destination vertex of E, in + the direction given by FORWARD. */ + +static inline int +dfs_edge_dest (struct edge *e, bool forward) +{ + return forward ? e->dest : e->src; +} + +/* Helper function for graphds_dfs. Returns the first edge after E (including + E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct edge * +foll_in_subgraph (struct edge *e, bool forward, bitmap subgraph) +{ + int d; + + if (!subgraph) + return e; + + while (e) + { + d = dfs_edge_dest (e, forward); + if (bitmap_bit_p (subgraph, d)) + return e; + + e = forward ? e->succ_next : e->pred_next; + } + + return e; +} + +/* Helper function for graphds_dfs. Select the first edge from V in G, in the + direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct edge * +dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph) +{ + struct edge *e; + + e = (forward ? g->vertices[v].succ : g->vertices[v].pred); + return foll_in_subgraph (e, forward, subgraph); +} + +/* Helper function for graphds_dfs. Returns the next edge after E, in the + graph direction given by FORWARD, that belongs to SUBGRAPH. */ + +static inline struct edge * +dfs_next_edge (struct edge *e, bool forward, bitmap subgraph) +{ + return foll_in_subgraph (forward ? e->succ_next : e->pred_next, + forward, subgraph); +} + +/* Runs dfs search over vertices of G, from NQ vertices in queue QS. + The vertices in postorder are stored into QT. If FORWARD is false, + backward dfs is run. If SUBGRAPH is not NULL, it specifies the + subgraph of G to run DFS on. Returns the number of the components + of the graph (number of the restarts of DFS). */ + +int +graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt, + bool forward, bitmap subgraph) +{ + int i, tick = 0, v, comp = 0, top; + struct edge *e; + struct edge **stack = XNEWVEC (struct edge *, g->n_vertices); + bitmap_iterator bi; + unsigned av; + + if (subgraph) + { + EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi) + { + g->vertices[av].component = -1; + g->vertices[av].post = -1; + } + } + else + { + for (i = 0; i < g->n_vertices; i++) + { + g->vertices[i].component = -1; + g->vertices[i].post = -1; + } + } + + for (i = 0; i < nq; i++) + { + v = qs[i]; + if (g->vertices[v].post != -1) + continue; + + g->vertices[v].component = comp++; + e = dfs_fst_edge (g, v, forward, subgraph); + top = 0; + + while (1) + { + while (e) + { + if (g->vertices[dfs_edge_dest (e, forward)].component + == -1) + break; + e = dfs_next_edge (e, forward, subgraph); + } + + if (!e) + { + if (qt) + VEC_safe_push (int, heap, *qt, v); + g->vertices[v].post = tick++; + + if (!top) + break; + + e = stack[--top]; + v = dfs_edge_src (e, forward); + e = dfs_next_edge (e, forward, subgraph); + continue; + } + + stack[top++] = e; + v = dfs_edge_dest (e, forward); + e = dfs_fst_edge (g, v, forward, subgraph); + g->vertices[v].component = comp - 1; + } + } + + free (stack); + + return comp; +} + +/* Determines the strongly connected components of G, using the algorithm of + Tarjan -- first determine the postorder dfs numbering in reversed graph, + then run the dfs on the original graph in the order given by decreasing + numbers assigned by the previous pass. If SUBGRAPH is not NULL, it + specifies the subgraph of G whose strongly connected components we want + to determine. + + After running this function, v->component is the number of the strongly + connected component for each vertex of G. Returns the number of the + sccs of G. */ + +int +graphds_scc (struct graph *g, bitmap subgraph) +{ + int *queue = XNEWVEC (int, g->n_vertices); + VEC (int, heap) *postorder = NULL; + int nq, i, comp; + unsigned v; + bitmap_iterator bi; + + if (subgraph) + { + nq = 0; + EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi) + { + queue[nq++] = v; + } + } + else + { + for (i = 0; i < g->n_vertices; i++) + queue[i] = i; + nq = g->n_vertices; + } + + graphds_dfs (g, queue, nq, &postorder, false, subgraph); + gcc_assert (VEC_length (int, postorder) == (unsigned) nq); + + for (i = 0; i < nq; i++) + queue[i] = VEC_index (int, postorder, nq - i - 1); + comp = graphds_dfs (g, queue, nq, NULL, true, subgraph); + + free (queue); + VEC_free (int, heap, postorder); + + return comp; +} + +/* Runs CALLBACK for all edges in G. */ + +void +for_each_edge (struct graph *g, graphds_edge_callback callback) +{ + struct edge *e; + int i; + + for (i = 0; i < g->n_vertices; i++) + for (e = g->vertices[i].succ; e; e = e->succ_next) + callback (g, e); +} + +/* Releases the memory occupied by G. */ + +void +free_graph (struct graph *g) +{ + struct edge *e, *n; + struct vertex *v; + int i; + + for (i = 0; i < g->n_vertices; i++) + { + v = &g->vertices[i]; + for (e = v->succ; e; e = n) + { + n = e->succ_next; + free (e); + } + } + free (g->vertices); + free (g); +} + +/* Returns the nearest common ancestor of X and Y in tree whose parent + links are given by PARENT. MARKS is the array used to mark the + vertices of the tree, and MARK is the number currently used as a mark. */ + +static int +tree_nca (int x, int y, int *parent, int *marks, int mark) +{ + if (x == -1 || x == y) + return y; + + /* We climb with X and Y up the tree, marking the visited nodes. When + we first arrive to a marked node, it is the common ancestor. */ + marks[x] = mark; + marks[y] = mark; + + while (1) + { + x = parent[x]; + if (x == -1) + break; + if (marks[x] == mark) + return x; + marks[x] = mark; + + y = parent[y]; + if (y == -1) + break; + if (marks[y] == mark) + return y; + marks[y] = mark; + } + + /* If we reached the root with one of the vertices, continue + with the other one till we reach the marked part of the + tree. */ + if (x == -1) + { + for (y = parent[y]; marks[y] != mark; y = parent[y]) + continue; + + return y; + } + else + { + for (x = parent[x]; marks[x] != mark; x = parent[x]) + continue; + + return x; + } +} + +/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER + arrays), where the entry node is ENTRY. */ + +void +graphds_domtree (struct graph *g, int entry, + int *parent, int *son, int *brother) +{ + VEC (int, heap) *postorder = NULL; + int *marks = XCNEWVEC (int, g->n_vertices); + int mark = 1, i, v, idom; + bool changed = true; + struct edge *e; + + /* We use a slight modification of the standard iterative algorithm, as + described in + + K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance + Algorithm + + sort vertices in reverse postorder + foreach v + dom(v) = everything + dom(entry) = entry; + + while (anything changes) + foreach v + dom(v) = {v} union (intersection of dom(p) over all predecessors of v) + + The sets dom(v) are represented by the parent links in the current version + of the dominance tree. */ + + for (i = 0; i < g->n_vertices; i++) + { + parent[i] = -1; + son[i] = -1; + brother[i] = -1; + } + graphds_dfs (g, &entry, 1, &postorder, true, NULL); + gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices); + gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry); + + while (changed) + { + changed = false; + + for (i = g->n_vertices - 2; i >= 0; i--) + { + v = VEC_index (int, postorder, i); + idom = -1; + for (e = g->vertices[v].pred; e; e = e->pred_next) + { + if (e->src != entry + && parent[e->src] == -1) + continue; + + idom = tree_nca (idom, e->src, parent, marks, mark++); + } + + if (idom != parent[v]) + { + parent[v] = idom; + changed = true; + } + } + } + + free (marks); + VEC_free (int, heap, postorder); + + for (i = 0; i < g->n_vertices; i++) + if (parent[i] != -1) + { + brother[i] = son[parent[i]]; + son[parent[i]] = i; + } +} diff --git a/gcc/graphds.h b/gcc/graphds.h new file mode 100644 index 0000000..2aad4b0 --- /dev/null +++ b/gcc/graphds.h @@ -0,0 +1,63 @@ +/* Graph representation. + Copyright (C) 2007 + Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +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, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* Structure representing edge of a graph. */ + +struct edge +{ + int src, dest; /* Source and destination. */ + struct edge *pred_next, *succ_next; + /* Next edge in predecessor and successor lists. */ + void *data; /* Data attached to the edge. */ +}; + +/* Structure representing vertex of a graph. */ + +struct vertex +{ + struct edge *pred, *succ; + /* Lists of predecessors and successors. */ + int component; /* Number of dfs restarts before reaching the + vertex. */ + int post; /* Postorder number. */ + void *data; /* Data attached to the vertex. */ +}; + +/* Structure representing a graph. */ + +struct graph +{ + int n_vertices; /* Number of vertices. */ + struct vertex *vertices; + /* The vertices. */ +}; + +struct graph *new_graph (int); +void dump_graph (FILE *, struct graph *); +struct edge *add_edge (struct graph *, int, int); +void identify_vertices (struct graph *, int, int); +int graphds_dfs (struct graph *, int *, int, + VEC (int, heap) **, bool, bitmap); +int graphds_scc (struct graph *, bitmap); +void graphds_domtree (struct graph *, int, int *, int *, int *); +typedef void (*graphds_edge_callback) (struct graph *, struct edge *); +void for_each_edge (struct graph *, graphds_edge_callback); +void free_graph (struct graph *g); diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index 62fd245..291d1d9 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -2521,7 +2521,7 @@ perfect_nestify (struct loop *loop, single_exit (loop)->src); set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb); set_immediate_dominator (CDI_DOMINATORS, olddest, - recount_dominator (CDI_DOMINATORS, olddest)); + recompute_dominator (CDI_DOMINATORS, olddest)); /* Create the new iv. */ oldivvar = VEC_index (tree, loopivs, 0); ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv"); diff --git a/gcc/loop-doloop.c b/gcc/loop-doloop.c index ef42c60..f59feae 100644 --- a/gcc/loop-doloop.c +++ b/gcc/loop-doloop.c @@ -422,13 +422,13 @@ doloop_modify (struct loop *loop, struct niter_desc *desc, emit_insn_after (sequence, BB_END (set_zero)); set_immediate_dominator (CDI_DOMINATORS, set_zero, - recount_dominator (CDI_DOMINATORS, - set_zero)); + recompute_dominator (CDI_DOMINATORS, + set_zero)); } set_immediate_dominator (CDI_DOMINATORS, new_preheader, - recount_dominator (CDI_DOMINATORS, - new_preheader)); + recompute_dominator (CDI_DOMINATORS, + new_preheader)); } /* Some targets (eg, C4x) need to initialize special looping diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index c5653b2..77d454f 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -953,8 +953,8 @@ unroll_loop_runtime_iterations (struct loop *loop) { rtx old_niter, niter, init_code, branch_code, tmp; unsigned i, j, p; - basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch; - unsigned n_dom_bbs; + basic_block preheader, *body, swtch, ezc_swtch; + VEC (basic_block, heap) *dom_bbs; sbitmap wont_exit; int may_exit_copy; unsigned n_peel; @@ -972,21 +972,20 @@ unroll_loop_runtime_iterations (struct loop *loop) opt_info = analyze_insns_in_loop (loop); /* Remember blocks whose dominators will have to be updated. */ - dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); - n_dom_bbs = 0; + dom_bbs = NULL; body = get_loop_body (loop); for (i = 0; i < loop->num_nodes; i++) { - unsigned nldom; - basic_block *ldom; + VEC (basic_block, heap) *ldom; + basic_block bb; - nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom); - for (j = 0; j < nldom; j++) - if (!flow_bb_inside_loop_p (loop, ldom[j])) - dom_bbs[n_dom_bbs++] = ldom[j]; + ldom = get_dominated_by (CDI_DOMINATORS, body[i]); + for (j = 0; VEC_iterate (basic_block, ldom, j, bb); j++) + if (!flow_bb_inside_loop_p (loop, bb)) + VEC_safe_push (basic_block, heap, dom_bbs, bb); - free (ldom); + VEC_free (basic_block, heap, ldom); } free (body); @@ -1105,7 +1104,7 @@ unroll_loop_runtime_iterations (struct loop *loop) } /* Recount dominators for outer blocks. */ - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false); /* And unroll loop. */ @@ -1177,8 +1176,7 @@ unroll_loop_runtime_iterations (struct loop *loop) "in runtime, %i insns\n", max_unroll, num_loop_insns (loop)); - if (dom_bbs) - free (dom_bbs); + VEC_free (basic_block, heap, dom_bbs); } /* Decide whether to simply peel LOOP and how much. */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 7bd4496..6dc0d3e 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -4336,11 +4336,11 @@ tree_duplicate_sese_region (edge entry, edge exit, basic_block *region, unsigned n_region, basic_block *region_copy) { - unsigned i, n_doms; + unsigned i; bool free_region_copy = false, copying_header = false; struct loop *loop = entry->dest->loop_father; edge exit_copy; - basic_block *doms; + VEC (basic_block, heap) *doms; edge redirected; int total_freq = 0, entry_freq = 0; gcov_type total_count = 0, entry_count = 0; @@ -4392,10 +4392,10 @@ tree_duplicate_sese_region (edge entry, edge exit, /* Record blocks outside the region that are dominated by something inside. */ - doms = XNEWVEC (basic_block, n_basic_blocks); + doms = NULL; initialize_original_copy_tables (); - n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms); + doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region); if (entry->dest->count) { @@ -4451,8 +4451,8 @@ tree_duplicate_sese_region (edge entry, edge exit, region, but was dominated by something inside needs recounting as well. */ set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src); - doms[n_doms++] = get_bb_original (entry->dest); - iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms); + VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest)); + iterate_fix_dominators (CDI_DOMINATORS, doms, false); free (doms); /* Add the other PHI node arguments. */ @@ -5476,9 +5476,7 @@ remove_edge_and_dominated_blocks (edge e) VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb); } - iterate_fix_dominators (CDI_DOMINATORS, - VEC_address (basic_block, bbs_to_fix_dom), - VEC_length (basic_block, bbs_to_fix_dom)); + iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); BITMAP_FREE (df); BITMAP_FREE (df_idom); diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 815c84f..e8a05ed 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -577,6 +577,9 @@ thread_block (basic_block bb, bool noloop_only) lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true; } + /* We do not update dominance info. */ + free_dominance_info (CDI_DOMINATORS); + /* Now create duplicates of BB. Note that for a block with a high outgoing degree we can waste @@ -1057,9 +1060,6 @@ thread_through_all_blocks (bool may_peel_loop_headers) retval |= thread_through_loop_header (loop, may_peel_loop_headers); } - if (retval) - free_dominance_info (CDI_DOMINATORS); - if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, "\nJumps threaded: %lu\n", thread_stats.num_threaded_edges); |