* [patch] Dominator analysis cleanups
@ 2007-03-25 11:10 Zdenek Dvorak
2007-03-25 12:01 ` Richard Guenther
0 siblings, 1 reply; 3+ messages in thread
From: Zdenek Dvorak @ 2007-03-25 11:10 UTC (permalink / raw)
To: gcc-patches
Hello,
this patch implements several improvements to dominance analysis:
1) Return type of get_dominated_by and get_dominated_by_region is
changed to vector, and iterate_fix_dominators takes the list of
basic blocks whose dominator needs to be updated as a vector.
2) recount_dominator is renamed to (hopefully) more correct name
recompute_dominator.
3) The algorithm used by iterate_fix_dominators is changed. The
algorithm we currently use is poorly documented, and it is fairly
nontrivial to show it is correct. Also, in some cases it may iterate
unnecessarily too much (which might be a problem, since
recompute_dominator calls are fairly expensive). For details about
the new algorithm, see the comment in iterate_fix_dominators.
4) Verify_dominators used to check only local correctness of the
dominators, i.e., it would consider any fixpoint of the equations
that define dominators correct, not necessarily only the largest one.
Instead, this patch makes us recompute all dominators, and compare
the results with the existing values.
Bootstrapped & regtested on i686, with verify_dominators calls inserted
at the end of iterate_fix_dominators. Even in this setting, the compile
time appears to be unchanged on the compilation of the preprocessed
gcc sources (iterate_fix_dominators is only used when we cannot update
the dominators in other ways, which is not too common).
Zdenek
* 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.
* 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.
* 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.
Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c (revision 123186)
--- cfgloopmanip.c (working copy)
*************** bool
*** 277,284 ****
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;
sbitmap seen;
bool irred_invalidated = false;
struct loop **deleted_loop;
--- 277,285 ----
remove_path (edge e)
{
edge ae;
! 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;
*************** remove_path (edge e)
*** 339,345 ****
/* Remove the path. */
from = e->src;
remove_branch (e);
! dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
/* Cancel loops contained in the path. */
deleted_loop = XNEWVEC (struct loop *, nrem);
--- 340,346 ----
/* Remove the path. */
from = e->src;
remove_branch (e);
! dom_bbs = NULL;
/* Cancel loops contained in the path. */
deleted_loop = XNEWVEC (struct loop *, nrem);
*************** remove_path (edge e)
*** 356,362 ****
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++)
{
--- 357,362 ----
*************** remove_path (edge e)
*** 371,384 ****
ldom;
ldom = next_dom_son (CDI_DOMINATORS, ldom))
if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
! dom_bbs[n_dom_bbs++] = ldom;
}
free (seen);
/* Recount dominators. */
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
! free (dom_bbs);
free (bord_bbs);
/* Fix placements of basic blocks inside loops and the placement of
--- 371,384 ----
ldom;
ldom = next_dom_son (CDI_DOMINATORS, ldom))
if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
! VEC_safe_push (basic_block, heap, dom_bbs, ldom);
}
free (seen);
/* Recount dominators. */
! 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
*************** loopify (edge latch_edge, edge header_ed
*** 473,480 ****
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
! basic_block *dom_bbs, *body;
! unsigned n_dom_bbs, i;
sbitmap seen;
struct loop *loop = alloc_loop ();
struct loop *outer = succ_bb->loop_father->outer;
--- 473,481 ----
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
! basic_block *body;
! VEC (basic_block, heap) *dom_bbs;
! unsigned i;
sbitmap seen;
struct loop *loop = alloc_loop ();
struct loop *outer = succ_bb->loop_father->outer;
*************** loopify (edge latch_edge, edge header_ed
*** 529,536 ****
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;
seen = sbitmap_alloc (last_basic_block);
sbitmap_zero (seen);
body = get_loop_body (loop);
--- 530,536 ----
scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE);
/* Update dominators of blocks outside of LOOP. */
! dom_bbs = NULL;
seen = sbitmap_alloc (last_basic_block);
sbitmap_zero (seen);
body = get_loop_body (loop);
*************** loopify (edge latch_edge, edge header_ed
*** 548,562 ****
if (!TEST_BIT (seen, ldom->index))
{
SET_BIT (seen, ldom->index);
! dom_bbs[n_dom_bbs++] = ldom;
}
}
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
free (body);
free (seen);
! free (dom_bbs);
return loop;
}
--- 548,562 ----
if (!TEST_BIT (seen, ldom->index))
{
SET_BIT (seen, ldom->index);
! VEC_safe_push (basic_block, heap, dom_bbs, ldom);
}
}
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
free (body);
free (seen);
! VEC_free (basic_block, heap, dom_bbs);
return loop;
}
*************** duplicate_loop_to_header_edge (struct lo
*** 1055,1077 ****
/* 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;
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++)
{
- 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);
}
free (first_active);
--- 1055,1077 ----
/* Update dominators of outer blocks if affected. */
for (i = 0; i < n; i++)
{
! basic_block dominated, dom_bb;
! VEC (basic_block, heap) *dom_bbs;
! unsigned j;
bb = bbs[i];
bb->aux = 0;
! dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
! for (j = 0; VEC_iterate (basic_block, dom_bbs, j, dominated); 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);
}
! VEC_free (basic_block, heap, dom_bbs);
}
free (first_active);
Index: cfghooks.c
===================================================================
*** cfghooks.c (revision 123186)
--- cfghooks.c (working copy)
*************** make_forwarder_block (basic_block bb, bo
*** 735,745 ****
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);
}
if (current_loops != NULL)
--- 735,745 ----
if (dom_info_available_p (CDI_DOMINATORS))
{
! 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)
Index: cfgloopanal.c
===================================================================
*** cfgloopanal.c (revision 123186)
--- cfgloopanal.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 29,34 ****
--- 29,35 ----
#include "cfgloop.h"
#include "expr.h"
#include "output.h"
+ #include "graphds.h"
/* Checks whether BB is executed exactly once in each LOOP iteration. */
*************** just_once_each_iteration_p (const struct
*** 50,206 ****
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. */
--- 51,56 ----
*************** check_irred (struct graph *g, struct edg
*** 221,258 ****
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
--- 71,76 ----
*************** mark_irreducible_loops (void)
*** 271,284 ****
basic_block act;
edge e;
edge_iterator ei;
! int i, src, dest;
struct graph *g;
int num = current_loops ? number_of_loops () : 1;
! int *queue1 = XNEWVEC (int, last_basic_block + num);
! int *queue2 = XNEWVEC (int, last_basic_block + num);
! int nq, depth;
! struct loop *cloop, *loop;
! loop_iterator li;
/* Reset the flags. */
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
--- 89,99 ----
basic_block act;
edge e;
edge_iterator ei;
! int src, dest;
struct graph *g;
int num = current_loops ? number_of_loops () : 1;
! int depth;
! struct loop *cloop;
/* Reset the flags. */
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
*************** mark_irreducible_loops (void)
*** 332,368 ****
}
}
! add_edge (g, src, dest, 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);
! }
!
! if (current_loops)
! {
! 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);
/* Mark the irreducible loops. */
for_each_edge (g, check_irred);
free_graph (g);
- free (queue1);
- free (queue2);
if (current_loops)
current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
--- 147,162 ----
}
}
! add_edge (g, src, dest)->data = e;
}
! /* Find the strongly connected components. */
! graphds_scc (g, NULL);
/* Mark the irreducible loops. */
for_each_edge (g, check_irred);
free_graph (g);
if (current_loops)
current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
Index: graphds.c
===================================================================
*** graphds.c (revision 0)
--- graphds.c (revision 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;
+ }
+ }
Index: graphds.h
===================================================================
*** graphds.h (revision 0)
--- graphds.h (revision 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);
Index: dominance.c
===================================================================
*** dominance.c (revision 123186)
--- dominance.c (working copy)
***************
*** 44,49 ****
--- 44,52 ----
#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. */
enum dom_state dom_computed[2];
*************** set_immediate_dominator (enum cdi_direct
*** 708,751 ****
dom_computed[dir] = 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)
{
int n;
struct et_node *node = bb->dom[dir], *son = node->son, *ason;
gcc_assert (dom_computed[dir]);
if (!son)
! {
! *bbs = NULL;
! return 0;
! }
!
! for (ason = son->right, n = 1; ason != son; ason = ason->right)
! n++;
! *bbs = XNEWVEC (basic_block, n);
! (*bbs)[0] = son->data;
for (ason = son->right, n = 1; ason != son; ason = ason->right)
! (*bbs)[n++] = ason->data;
! 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]->flags |= BB_DUPLICATED;
--- 711,748 ----
dom_computed[dir] = DOM_NO_FAST_QUERY;
}
! /* 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)
{
int n;
struct et_node *node = bb->dom[dir], *son = node->son, *ason;
+ VEC (basic_block, heap) *bbs = NULL;
gcc_assert (dom_computed[dir]);
if (!son)
! return NULL;
! VEC_safe_push (basic_block, heap, bbs, son->data);
for (ason = son->right, n = 1; ason != son; ason = ason->right)
! VEC_safe_push (basic_block, heap, bbs, ason->data);
! return bbs;
}
! /* 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)
{
! unsigned i;
basic_block dom;
+ VEC (basic_block, heap) *doms = NULL;
for (i = 0; i < n_region; i++)
region[i]->flags |= BB_DUPLICATED;
*************** get_dominated_by_region (enum cdi_direct
*** 754,764 ****
dom;
dom = next_dom_son (dir, dom))
if (!(dom->flags & BB_DUPLICATED))
! doms[n_doms++] = dom;
for (i = 0; i < n_region; i++)
region[i]->flags &= ~BB_DUPLICATED;
! return n_doms;
}
/* Redirect all edges pointing to BB to TO. */
--- 751,761 ----
dom;
dom = next_dom_son (dir, dom))
if (!(dom->flags & BB_DUPLICATED))
! VEC_safe_push (basic_block, heap, doms, dom);
for (i = 0; i < n_region; i++)
region[i]->flags &= ~BB_DUPLICATED;
! return doms;
}
/* Redirect all edges pointing to BB to TO. */
*************** void
*** 936,975 ****
verify_dominators (enum cdi_direction dir)
{
int err = 0;
! basic_block bb;
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);
! imm_bb = get_immediate_dominator (dir, bb);
! if (dom_bb != imm_bb)
{
! 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 (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);
}
--- 933,969 ----
verify_dominators (enum cdi_direction dir)
{
int err = 0;
! 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)
{
! old_dom[bb->index] = get_immediate_dominator (dir, bb);
! if (!old_dom[bb->index])
{
! error ("dominator of %d status unknown", bb->index);
err = 1;
}
}
! free_dominance_info (dir);
! calculate_dominance_info (dir);
!
! FOR_EACH_BB (bb)
{
! imm_bb = get_immediate_dominator (dir, bb);
! if (old_dom[bb->index] != imm_bb)
{
! 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);
}
*************** verify_dominators (enum cdi_direction di
*** 979,985 ****
reaches a fixed point. */
basic_block
! recount_dominator (enum cdi_direction dir, basic_block bb)
{
basic_block dom_bb = NULL;
edge e;
--- 973,979 ----
reaches a fixed point. */
basic_block
! recompute_dominator (enum cdi_direction dir, basic_block bb)
{
basic_block dom_bb = NULL;
edge e;
*************** recount_dominator (enum cdi_direction di
*** 991,1001 ****
{
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);
}
--- 985,990 ----
*************** recount_dominator (enum cdi_direction di
*** 1012,1047 ****
return dom_bb;
}
! /* Iteratively recount dominators of BBS. The change is supposed to be local
! and not to grow further. */
! void
! iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
{
! int i, changed = 1;
! basic_block old_dom, new_dom;
! gcc_assert (dom_computed[dir]);
! for (i = 0; i < n; i++)
! set_immediate_dominator (dir, bbs[i], NULL);
! while (changed)
{
! changed = 0;
! for (i = 0; i < n; i++)
{
! 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);
}
}
}
! for (i = 0; i < n; i++)
! gcc_assert (get_immediate_dominator (dir, bbs[i]));
}
void
--- 1001,1325 ----
return dom_bb;
}
! /* 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[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, 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;
+
+ /* 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]);
+
+ /* 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) 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;
!
! if (n == 1)
! {
! 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)
! {
! 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);
!
! free_graph (g);
}
void
Index: et-forest.c
===================================================================
*** et-forest.c (revision 123186)
--- et-forest.c (working copy)
*************** et_below (struct et_node *down, struct e
*** 747,749 ****
--- 747,766 ----
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;
+ }
Index: et-forest.h
===================================================================
*** et-forest.h (revision 123186)
--- et-forest.h (working copy)
*************** void et_set_father (struct et_node *, st
*** 79,84 ****
--- 79,85 ----
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
}
Index: gcse.c
===================================================================
*** gcse.c (revision 123186)
--- gcse.c (working copy)
*************** static void
*** 4829,4836 ****
hoist_code (void)
{
basic_block bb, dominated;
! basic_block *domby;
! unsigned int domby_len;
unsigned int i,j;
struct expr **index_map;
struct expr *expr;
--- 4829,4835 ----
hoist_code (void)
{
basic_block bb, dominated;
! VEC (basic_block, heap) *domby;
unsigned int i,j;
struct expr **index_map;
struct expr *expr;
*************** hoist_code (void)
*** 4852,4858 ****
int found = 0;
int insn_inserted_p;
! domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby);
/* 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++)
--- 4851,4857 ----
int found = 0;
int insn_inserted_p;
! 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++)
*************** hoist_code (void)
*** 4865,4873 ****
/* 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++)
{
- dominated = domby[j];
/* Ignore self dominance. */
if (bb == dominated)
continue;
--- 4864,4871 ----
/* 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; VEC_iterate (basic_block, domby, j, dominated); j++)
{
/* Ignore self dominance. */
if (bb == dominated)
continue;
*************** hoist_code (void)
*** 4906,4913 ****
/* If we found nothing to hoist, then quit now. */
if (! found)
{
! free (domby);
! continue;
}
/* Loop over all the hoistable expressions. */
--- 4904,4911 ----
/* If we found nothing to hoist, then quit now. */
if (! found)
{
! VEC_free (basic_block, heap, domby);
! continue;
}
/* Loop over all the hoistable expressions. */
*************** hoist_code (void)
*** 4923,4931 ****
/* 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++)
{
- dominated = domby[j];
/* Ignore self dominance. */
if (bb == dominated)
continue;
--- 4921,4928 ----
/* 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; VEC_iterate (basic_block, domby, j, dominated); j++)
{
/* Ignore self dominance. */
if (bb == dominated)
continue;
*************** hoist_code (void)
*** 4976,4982 ****
}
}
}
! free (domby);
}
free (index_map);
--- 4973,4979 ----
}
}
}
! VEC_free (basic_block, heap, domby);
}
free (index_map);
Index: loop-unroll.c
===================================================================
*** loop-unroll.c (revision 123186)
--- loop-unroll.c (working copy)
*************** unroll_loop_runtime_iterations (struct l
*** 949,956 ****
{
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;
sbitmap wont_exit;
int may_exit_copy;
unsigned n_peel;
--- 949,956 ----
{
rtx old_niter, niter, init_code, branch_code, tmp;
unsigned i, j, p;
! basic_block preheader, *body, swtch, ezc_swtch;
! VEC (basic_block, heap) *dom_bbs;
sbitmap wont_exit;
int may_exit_copy;
unsigned n_peel;
*************** unroll_loop_runtime_iterations (struct l
*** 968,988 ****
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;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
! unsigned nldom;
! basic_block *ldom;
! 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];
! free (ldom);
}
free (body);
--- 968,987 ----
opt_info = analyze_insns_in_loop (loop);
/* Remember blocks whose dominators will have to be updated. */
! dom_bbs = NULL;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
! VEC (basic_block, heap) *ldom;
! basic_block bb;
! 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);
! VEC_free (basic_block, heap, ldom);
}
free (body);
*************** unroll_loop_runtime_iterations (struct l
*** 1101,1107 ****
}
/* Recount dominators for outer blocks. */
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
/* And unroll loop. */
--- 1100,1106 ----
}
/* Recount dominators for outer blocks. */
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
/* And unroll loop. */
*************** unroll_loop_runtime_iterations (struct l
*** 1173,1180 ****
"in runtime, %i insns\n",
max_unroll, num_loop_insns (loop));
! if (dom_bbs)
! free (dom_bbs);
}
/* Decide whether to simply peel LOOP and how much. */
--- 1172,1178 ----
"in runtime, %i insns\n",
max_unroll, num_loop_insns (loop));
! VEC_free (basic_block, heap, dom_bbs);
}
/* Decide whether to simply peel LOOP and how much. */
Index: loop-doloop.c
===================================================================
*** loop-doloop.c (revision 123186)
--- loop-doloop.c (working copy)
*************** doloop_modify (struct loop *loop, struct
*** 422,434 ****
emit_insn_after (sequence, BB_END (set_zero));
set_immediate_dominator (CDI_DOMINATORS, set_zero,
! recount_dominator (CDI_DOMINATORS,
! set_zero));
}
set_immediate_dominator (CDI_DOMINATORS, new_preheader,
! recount_dominator (CDI_DOMINATORS,
! new_preheader));
}
/* Some targets (eg, C4x) need to initialize special looping
--- 422,434 ----
emit_insn_after (sequence, BB_END (set_zero));
set_immediate_dominator (CDI_DOMINATORS, set_zero,
! recompute_dominator (CDI_DOMINATORS,
! set_zero));
}
set_immediate_dominator (CDI_DOMINATORS, new_preheader,
! recompute_dominator (CDI_DOMINATORS,
! new_preheader));
}
/* Some targets (eg, C4x) need to initialize special looping
Index: Makefile.in
===================================================================
*** Makefile.in (revision 123186)
--- Makefile.in (working copy)
*************** OBJS-common = \
*** 1007,1012 ****
--- 1007,1013 ----
gimplify.o \
global.o \
graph.o \
+ graphds.o \
gtype-desc.o \
haifa-sched.o \
hooks.o \
*************** cfgloop.o : cfgloop.c $(CONFIG_H) $(SYST
*** 2587,2593 ****
$(OBSTACK_H) toplev.h $(TREE_FLOW_H) $(TREE_H) pointer-set.h output.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
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) \
--- 2588,2596 ----
$(OBSTACK_H) toplev.h $(TREE_FLOW_H) $(TREE_H) pointer-set.h output.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 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) \
*************** loop-unroll.o: loop-unroll.c $(CONFIG_H)
*** 2613,2619 ****
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)
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) \
--- 2616,2623 ----
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) 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) \
Index: basic-block.h
===================================================================
*** basic-block.h (revision 123186)
--- basic-block.h (working copy)
*************** extern void set_immediate_dominator (enu
*** 959,973 ****
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 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);
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 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);
--- 959,975 ----
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 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 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,
! 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);
Index: tree-cfg.c
===================================================================
*** tree-cfg.c (revision 123186)
--- tree-cfg.c (working copy)
*************** tree_duplicate_sese_region (edge entry,
*** 4412,4422 ****
basic_block *region, unsigned n_region,
basic_block *region_copy)
{
! unsigned i, n_doms;
bool free_region_copy = false, copying_header = false;
struct loop *loop = entry->dest->loop_father;
edge exit_copy;
! basic_block *doms;
edge redirected;
int total_freq = 0, entry_freq = 0;
gcov_type total_count = 0, entry_count = 0;
--- 4412,4422 ----
basic_block *region, unsigned n_region,
basic_block *region_copy)
{
! unsigned i;
bool free_region_copy = false, copying_header = false;
struct loop *loop = entry->dest->loop_father;
edge exit_copy;
! VEC (basic_block, heap) *doms;
edge redirected;
int total_freq = 0, entry_freq = 0;
gcov_type total_count = 0, entry_count = 0;
*************** tree_duplicate_sese_region (edge entry,
*** 4468,4477 ****
/* Record blocks outside the region that are dominated by something
inside. */
! doms = XNEWVEC (basic_block, n_basic_blocks);
initialize_original_copy_tables ();
! n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
if (entry->dest->count)
{
--- 4468,4477 ----
/* Record blocks outside the region that are dominated by something
inside. */
! doms = NULL;
initialize_original_copy_tables ();
! doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
if (entry->dest->count)
{
*************** tree_duplicate_sese_region (edge entry,
*** 4527,4534 ****
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);
free (doms);
/* Add the other PHI node arguments. */
--- 4527,4534 ----
region, but was dominated by something inside needs recounting as
well. */
set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
! 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. */
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [patch] Dominator analysis cleanups
2007-03-25 11:10 [patch] Dominator analysis cleanups Zdenek Dvorak
@ 2007-03-25 12:01 ` Richard Guenther
2007-03-25 14:31 ` Zdenek Dvorak
0 siblings, 1 reply; 3+ messages in thread
From: Richard Guenther @ 2007-03-25 12:01 UTC (permalink / raw)
To: Zdenek Dvorak; +Cc: gcc-patches
On 3/25/07, Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> wrote:
> Hello,
>
> this patch implements several improvements to dominance analysis:
>
> 1) Return type of get_dominated_by and get_dominated_by_region is
> changed to vector, and iterate_fix_dominators takes the list of
> basic blocks whose dominator needs to be updated as a vector.
> 2) recount_dominator is renamed to (hopefully) more correct name
> recompute_dominator.
> 3) The algorithm used by iterate_fix_dominators is changed. The
> algorithm we currently use is poorly documented, and it is fairly
> nontrivial to show it is correct. Also, in some cases it may iterate
> unnecessarily too much (which might be a problem, since
> recompute_dominator calls are fairly expensive). For details about
> the new algorithm, see the comment in iterate_fix_dominators.
> 4) Verify_dominators used to check only local correctness of the
> dominators, i.e., it would consider any fixpoint of the equations
> that define dominators correct, not necessarily only the largest one.
> Instead, this patch makes us recompute all dominators, and compare
> the results with the existing values.
>
> Bootstrapped & regtested on i686, with verify_dominators calls inserted
> at the end of iterate_fix_dominators. Even in this setting, the compile
> time appears to be unchanged on the compilation of the preprocessed
> gcc sources (iterate_fix_dominators is only used when we cannot update
> the dominators in other ways, which is not too common).
This looks like a good cleanup. I wonder if
* 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.
could be easily splitted to a separate patch?
Richard.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [patch] Dominator analysis cleanups
2007-03-25 12:01 ` Richard Guenther
@ 2007-03-25 14:31 ` Zdenek Dvorak
0 siblings, 0 replies; 3+ messages in thread
From: Zdenek Dvorak @ 2007-03-25 14:31 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
Hello,
> >this patch implements several improvements to dominance analysis:
> >
> >1) Return type of get_dominated_by and get_dominated_by_region is
> > changed to vector, and iterate_fix_dominators takes the list of
> > basic blocks whose dominator needs to be updated as a vector.
> >2) recount_dominator is renamed to (hopefully) more correct name
> > recompute_dominator.
> >3) The algorithm used by iterate_fix_dominators is changed. The
> > algorithm we currently use is poorly documented, and it is fairly
> > nontrivial to show it is correct. Also, in some cases it may iterate
> > unnecessarily too much (which might be a problem, since
> > recompute_dominator calls are fairly expensive). For details about
> > the new algorithm, see the comment in iterate_fix_dominators.
> >4) Verify_dominators used to check only local correctness of the
> > dominators, i.e., it would consider any fixpoint of the equations
> > that define dominators correct, not necessarily only the largest one.
> > Instead, this patch makes us recompute all dominators, and compare
> > the results with the existing values.
> >
> >Bootstrapped & regtested on i686, with verify_dominators calls inserted
> >at the end of iterate_fix_dominators. Even in this setting, the compile
> >time appears to be unchanged on the compilation of the preprocessed
> >gcc sources (iterate_fix_dominators is only used when we cannot update
> >the dominators in other ways, which is not too common).
>
> This looks like a good cleanup. I wonder if
>
> * 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.
>
> could be easily splitted to a separate patch?
yes, it could.
Zdenek
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2007-03-25 12:38 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-03-25 11:10 [patch] Dominator analysis cleanups Zdenek Dvorak
2007-03-25 12:01 ` Richard Guenther
2007-03-25 14:31 ` Zdenek Dvorak
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).