/* Graph representation and manipulation functions.
|
/* Graph representation and manipulation functions.
|
Copyright (C) 2007
|
Copyright (C) 2007
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "bitmap.h"
|
#include "bitmap.h"
|
#include "vec.h"
|
#include "vec.h"
|
#include "vecprim.h"
|
#include "vecprim.h"
|
#include "graphds.h"
|
#include "graphds.h"
|
|
|
/* Dumps graph G into F. */
|
/* Dumps graph G into F. */
|
|
|
void
|
void
|
dump_graph (FILE *f, struct graph *g)
|
dump_graph (FILE *f, struct graph *g)
|
{
|
{
|
int i;
|
int i;
|
struct graph_edge *e;
|
struct graph_edge *e;
|
|
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
{
|
{
|
if (!g->vertices[i].pred
|
if (!g->vertices[i].pred
|
&& !g->vertices[i].succ)
|
&& !g->vertices[i].succ)
|
continue;
|
continue;
|
|
|
fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
|
fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
|
for (e = g->vertices[i].pred; e; e = e->pred_next)
|
for (e = g->vertices[i].pred; e; e = e->pred_next)
|
fprintf (f, " %d", e->src);
|
fprintf (f, " %d", e->src);
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
|
|
fprintf (f, "\t->");
|
fprintf (f, "\t->");
|
for (e = g->vertices[i].succ; e; e = e->succ_next)
|
for (e = g->vertices[i].succ; e; e = e->succ_next)
|
fprintf (f, " %d", e->dest);
|
fprintf (f, " %d", e->dest);
|
fprintf (f, "\n");
|
fprintf (f, "\n");
|
}
|
}
|
}
|
}
|
|
|
/* Creates a new graph with N_VERTICES vertices. */
|
/* Creates a new graph with N_VERTICES vertices. */
|
|
|
struct graph *
|
struct graph *
|
new_graph (int n_vertices)
|
new_graph (int n_vertices)
|
{
|
{
|
struct graph *g = XNEW (struct graph);
|
struct graph *g = XNEW (struct graph);
|
|
|
g->n_vertices = n_vertices;
|
g->n_vertices = n_vertices;
|
g->vertices = XCNEWVEC (struct vertex, n_vertices);
|
g->vertices = XCNEWVEC (struct vertex, n_vertices);
|
|
|
return g;
|
return g;
|
}
|
}
|
|
|
/* Adds an edge from F to T to graph G. The new edge is returned. */
|
/* Adds an edge from F to T to graph G. The new edge is returned. */
|
|
|
struct graph_edge *
|
struct graph_edge *
|
add_edge (struct graph *g, int f, int t)
|
add_edge (struct graph *g, int f, int t)
|
{
|
{
|
struct graph_edge *e = XNEW (struct graph_edge);
|
struct graph_edge *e = XNEW (struct graph_edge);
|
struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
|
struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
|
|
|
|
|
e->src = f;
|
e->src = f;
|
e->dest = t;
|
e->dest = t;
|
|
|
e->pred_next = vt->pred;
|
e->pred_next = vt->pred;
|
vt->pred = e;
|
vt->pred = e;
|
|
|
e->succ_next = vf->succ;
|
e->succ_next = vf->succ;
|
vf->succ = e;
|
vf->succ = e;
|
|
|
return e;
|
return e;
|
}
|
}
|
|
|
/* Moves all the edges incident with U to V. */
|
/* Moves all the edges incident with U to V. */
|
|
|
void
|
void
|
identify_vertices (struct graph *g, int v, int u)
|
identify_vertices (struct graph *g, int v, int u)
|
{
|
{
|
struct vertex *vv = &g->vertices[v];
|
struct vertex *vv = &g->vertices[v];
|
struct vertex *uu = &g->vertices[u];
|
struct vertex *uu = &g->vertices[u];
|
struct graph_edge *e, *next;
|
struct graph_edge *e, *next;
|
|
|
for (e = uu->succ; e; e = next)
|
for (e = uu->succ; e; e = next)
|
{
|
{
|
next = e->succ_next;
|
next = e->succ_next;
|
|
|
e->src = v;
|
e->src = v;
|
e->succ_next = vv->succ;
|
e->succ_next = vv->succ;
|
vv->succ = e;
|
vv->succ = e;
|
}
|
}
|
uu->succ = NULL;
|
uu->succ = NULL;
|
|
|
for (e = uu->pred; e; e = next)
|
for (e = uu->pred; e; e = next)
|
{
|
{
|
next = e->pred_next;
|
next = e->pred_next;
|
|
|
e->dest = v;
|
e->dest = v;
|
e->pred_next = vv->pred;
|
e->pred_next = vv->pred;
|
vv->pred = e;
|
vv->pred = e;
|
}
|
}
|
uu->pred = NULL;
|
uu->pred = NULL;
|
}
|
}
|
|
|
/* Helper function for graphds_dfs. Returns the source vertex of E, in the
|
/* Helper function for graphds_dfs. Returns the source vertex of E, in the
|
direction given by FORWARD. */
|
direction given by FORWARD. */
|
|
|
static inline int
|
static inline int
|
dfs_edge_src (struct graph_edge *e, bool forward)
|
dfs_edge_src (struct graph_edge *e, bool forward)
|
{
|
{
|
return forward ? e->src : e->dest;
|
return forward ? e->src : e->dest;
|
}
|
}
|
|
|
/* Helper function for graphds_dfs. Returns the destination vertex of E, in
|
/* Helper function for graphds_dfs. Returns the destination vertex of E, in
|
the direction given by FORWARD. */
|
the direction given by FORWARD. */
|
|
|
static inline int
|
static inline int
|
dfs_edge_dest (struct graph_edge *e, bool forward)
|
dfs_edge_dest (struct graph_edge *e, bool forward)
|
{
|
{
|
return forward ? e->dest : e->src;
|
return forward ? e->dest : e->src;
|
}
|
}
|
|
|
/* Helper function for graphds_dfs. Returns the first edge after E (including
|
/* Helper function for graphds_dfs. Returns the first edge after E (including
|
E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
|
E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
|
|
|
static inline struct graph_edge *
|
static inline struct graph_edge *
|
foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
|
foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
|
{
|
{
|
int d;
|
int d;
|
|
|
if (!subgraph)
|
if (!subgraph)
|
return e;
|
return e;
|
|
|
while (e)
|
while (e)
|
{
|
{
|
d = dfs_edge_dest (e, forward);
|
d = dfs_edge_dest (e, forward);
|
if (bitmap_bit_p (subgraph, d))
|
if (bitmap_bit_p (subgraph, d))
|
return e;
|
return e;
|
|
|
e = forward ? e->succ_next : e->pred_next;
|
e = forward ? e->succ_next : e->pred_next;
|
}
|
}
|
|
|
return e;
|
return e;
|
}
|
}
|
|
|
/* Helper function for graphds_dfs. Select the first edge from V in G, in the
|
/* Helper function for graphds_dfs. Select the first edge from V in G, in the
|
direction given by FORWARD, that belongs to SUBGRAPH. */
|
direction given by FORWARD, that belongs to SUBGRAPH. */
|
|
|
static inline struct graph_edge *
|
static inline struct graph_edge *
|
dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
|
dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
|
{
|
{
|
struct graph_edge *e;
|
struct graph_edge *e;
|
|
|
e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
|
e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
|
return foll_in_subgraph (e, forward, subgraph);
|
return foll_in_subgraph (e, forward, subgraph);
|
}
|
}
|
|
|
/* Helper function for graphds_dfs. Returns the next edge after E, in the
|
/* Helper function for graphds_dfs. Returns the next edge after E, in the
|
graph direction given by FORWARD, that belongs to SUBGRAPH. */
|
graph direction given by FORWARD, that belongs to SUBGRAPH. */
|
|
|
static inline struct graph_edge *
|
static inline struct graph_edge *
|
dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
|
dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
|
{
|
{
|
return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
|
return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
|
forward, subgraph);
|
forward, subgraph);
|
}
|
}
|
|
|
/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
|
/* 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,
|
The vertices in postorder are stored into QT. If FORWARD is false,
|
backward dfs is run. If SUBGRAPH is not NULL, it specifies the
|
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
|
subgraph of G to run DFS on. Returns the number of the components
|
of the graph (number of the restarts of DFS). */
|
of the graph (number of the restarts of DFS). */
|
|
|
int
|
int
|
graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
|
graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
|
bool forward, bitmap subgraph)
|
bool forward, bitmap subgraph)
|
{
|
{
|
int i, tick = 0, v, comp = 0, top;
|
int i, tick = 0, v, comp = 0, top;
|
struct graph_edge *e;
|
struct graph_edge *e;
|
struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
|
struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned av;
|
unsigned av;
|
|
|
if (subgraph)
|
if (subgraph)
|
{
|
{
|
EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
|
EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
|
{
|
{
|
g->vertices[av].component = -1;
|
g->vertices[av].component = -1;
|
g->vertices[av].post = -1;
|
g->vertices[av].post = -1;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
{
|
{
|
g->vertices[i].component = -1;
|
g->vertices[i].component = -1;
|
g->vertices[i].post = -1;
|
g->vertices[i].post = -1;
|
}
|
}
|
}
|
}
|
|
|
for (i = 0; i < nq; i++)
|
for (i = 0; i < nq; i++)
|
{
|
{
|
v = qs[i];
|
v = qs[i];
|
if (g->vertices[v].post != -1)
|
if (g->vertices[v].post != -1)
|
continue;
|
continue;
|
|
|
g->vertices[v].component = comp++;
|
g->vertices[v].component = comp++;
|
e = dfs_fst_edge (g, v, forward, subgraph);
|
e = dfs_fst_edge (g, v, forward, subgraph);
|
top = 0;
|
top = 0;
|
|
|
while (1)
|
while (1)
|
{
|
{
|
while (e)
|
while (e)
|
{
|
{
|
if (g->vertices[dfs_edge_dest (e, forward)].component
|
if (g->vertices[dfs_edge_dest (e, forward)].component
|
== -1)
|
== -1)
|
break;
|
break;
|
e = dfs_next_edge (e, forward, subgraph);
|
e = dfs_next_edge (e, forward, subgraph);
|
}
|
}
|
|
|
if (!e)
|
if (!e)
|
{
|
{
|
if (qt)
|
if (qt)
|
VEC_safe_push (int, heap, *qt, v);
|
VEC_safe_push (int, heap, *qt, v);
|
g->vertices[v].post = tick++;
|
g->vertices[v].post = tick++;
|
|
|
if (!top)
|
if (!top)
|
break;
|
break;
|
|
|
e = stack[--top];
|
e = stack[--top];
|
v = dfs_edge_src (e, forward);
|
v = dfs_edge_src (e, forward);
|
e = dfs_next_edge (e, forward, subgraph);
|
e = dfs_next_edge (e, forward, subgraph);
|
continue;
|
continue;
|
}
|
}
|
|
|
stack[top++] = e;
|
stack[top++] = e;
|
v = dfs_edge_dest (e, forward);
|
v = dfs_edge_dest (e, forward);
|
e = dfs_fst_edge (g, v, forward, subgraph);
|
e = dfs_fst_edge (g, v, forward, subgraph);
|
g->vertices[v].component = comp - 1;
|
g->vertices[v].component = comp - 1;
|
}
|
}
|
}
|
}
|
|
|
free (stack);
|
free (stack);
|
|
|
return comp;
|
return comp;
|
}
|
}
|
|
|
/* Determines the strongly connected components of G, using the algorithm of
|
/* Determines the strongly connected components of G, using the algorithm of
|
Tarjan -- first determine the postorder dfs numbering in reversed graph,
|
Tarjan -- first determine the postorder dfs numbering in reversed graph,
|
then run the dfs on the original graph in the order given by decreasing
|
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
|
numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
|
specifies the subgraph of G whose strongly connected components we want
|
specifies the subgraph of G whose strongly connected components we want
|
to determine.
|
to determine.
|
|
|
After running this function, v->component is the number of the strongly
|
After running this function, v->component is the number of the strongly
|
connected component for each vertex of G. Returns the number of the
|
connected component for each vertex of G. Returns the number of the
|
sccs of G. */
|
sccs of G. */
|
|
|
int
|
int
|
graphds_scc (struct graph *g, bitmap subgraph)
|
graphds_scc (struct graph *g, bitmap subgraph)
|
{
|
{
|
int *queue = XNEWVEC (int, g->n_vertices);
|
int *queue = XNEWVEC (int, g->n_vertices);
|
VEC (int, heap) *postorder = NULL;
|
VEC (int, heap) *postorder = NULL;
|
int nq, i, comp;
|
int nq, i, comp;
|
unsigned v;
|
unsigned v;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
if (subgraph)
|
if (subgraph)
|
{
|
{
|
nq = 0;
|
nq = 0;
|
EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
|
EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
|
{
|
{
|
queue[nq++] = v;
|
queue[nq++] = v;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
queue[i] = i;
|
queue[i] = i;
|
nq = g->n_vertices;
|
nq = g->n_vertices;
|
}
|
}
|
|
|
graphds_dfs (g, queue, nq, &postorder, false, subgraph);
|
graphds_dfs (g, queue, nq, &postorder, false, subgraph);
|
gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
|
gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
|
|
|
for (i = 0; i < nq; i++)
|
for (i = 0; i < nq; i++)
|
queue[i] = VEC_index (int, postorder, nq - i - 1);
|
queue[i] = VEC_index (int, postorder, nq - i - 1);
|
comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
|
comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
|
|
|
free (queue);
|
free (queue);
|
VEC_free (int, heap, postorder);
|
VEC_free (int, heap, postorder);
|
|
|
return comp;
|
return comp;
|
}
|
}
|
|
|
/* Runs CALLBACK for all edges in G. */
|
/* Runs CALLBACK for all edges in G. */
|
|
|
void
|
void
|
for_each_edge (struct graph *g, graphds_edge_callback callback)
|
for_each_edge (struct graph *g, graphds_edge_callback callback)
|
{
|
{
|
struct graph_edge *e;
|
struct graph_edge *e;
|
int i;
|
int i;
|
|
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
for (e = g->vertices[i].succ; e; e = e->succ_next)
|
for (e = g->vertices[i].succ; e; e = e->succ_next)
|
callback (g, e);
|
callback (g, e);
|
}
|
}
|
|
|
/* Releases the memory occupied by G. */
|
/* Releases the memory occupied by G. */
|
|
|
void
|
void
|
free_graph (struct graph *g)
|
free_graph (struct graph *g)
|
{
|
{
|
struct graph_edge *e, *n;
|
struct graph_edge *e, *n;
|
struct vertex *v;
|
struct vertex *v;
|
int i;
|
int i;
|
|
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
{
|
{
|
v = &g->vertices[i];
|
v = &g->vertices[i];
|
for (e = v->succ; e; e = n)
|
for (e = v->succ; e; e = n)
|
{
|
{
|
n = e->succ_next;
|
n = e->succ_next;
|
free (e);
|
free (e);
|
}
|
}
|
}
|
}
|
free (g->vertices);
|
free (g->vertices);
|
free (g);
|
free (g);
|
}
|
}
|
|
|
/* Returns the nearest common ancestor of X and Y in tree whose parent
|
/* 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
|
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. */
|
vertices of the tree, and MARK is the number currently used as a mark. */
|
|
|
static int
|
static int
|
tree_nca (int x, int y, int *parent, int *marks, int mark)
|
tree_nca (int x, int y, int *parent, int *marks, int mark)
|
{
|
{
|
if (x == -1 || x == y)
|
if (x == -1 || x == y)
|
return y;
|
return y;
|
|
|
/* We climb with X and Y up the tree, marking the visited nodes. When
|
/* 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. */
|
we first arrive to a marked node, it is the common ancestor. */
|
marks[x] = mark;
|
marks[x] = mark;
|
marks[y] = mark;
|
marks[y] = mark;
|
|
|
while (1)
|
while (1)
|
{
|
{
|
x = parent[x];
|
x = parent[x];
|
if (x == -1)
|
if (x == -1)
|
break;
|
break;
|
if (marks[x] == mark)
|
if (marks[x] == mark)
|
return x;
|
return x;
|
marks[x] = mark;
|
marks[x] = mark;
|
|
|
y = parent[y];
|
y = parent[y];
|
if (y == -1)
|
if (y == -1)
|
break;
|
break;
|
if (marks[y] == mark)
|
if (marks[y] == mark)
|
return y;
|
return y;
|
marks[y] = mark;
|
marks[y] = mark;
|
}
|
}
|
|
|
/* If we reached the root with one of the vertices, continue
|
/* If we reached the root with one of the vertices, continue
|
with the other one till we reach the marked part of the
|
with the other one till we reach the marked part of the
|
tree. */
|
tree. */
|
if (x == -1)
|
if (x == -1)
|
{
|
{
|
for (y = parent[y]; marks[y] != mark; y = parent[y])
|
for (y = parent[y]; marks[y] != mark; y = parent[y])
|
continue;
|
continue;
|
|
|
return y;
|
return y;
|
}
|
}
|
else
|
else
|
{
|
{
|
for (x = parent[x]; marks[x] != mark; x = parent[x])
|
for (x = parent[x]; marks[x] != mark; x = parent[x])
|
continue;
|
continue;
|
|
|
return x;
|
return x;
|
}
|
}
|
}
|
}
|
|
|
/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
|
/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
|
arrays), where the entry node is ENTRY. */
|
arrays), where the entry node is ENTRY. */
|
|
|
void
|
void
|
graphds_domtree (struct graph *g, int entry,
|
graphds_domtree (struct graph *g, int entry,
|
int *parent, int *son, int *brother)
|
int *parent, int *son, int *brother)
|
{
|
{
|
VEC (int, heap) *postorder = NULL;
|
VEC (int, heap) *postorder = NULL;
|
int *marks = XCNEWVEC (int, g->n_vertices);
|
int *marks = XCNEWVEC (int, g->n_vertices);
|
int mark = 1, i, v, idom;
|
int mark = 1, i, v, idom;
|
bool changed = true;
|
bool changed = true;
|
struct graph_edge *e;
|
struct graph_edge *e;
|
|
|
/* We use a slight modification of the standard iterative algorithm, as
|
/* We use a slight modification of the standard iterative algorithm, as
|
described in
|
described in
|
|
|
K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
Algorithm
|
Algorithm
|
|
|
sort vertices in reverse postorder
|
sort vertices in reverse postorder
|
foreach v
|
foreach v
|
dom(v) = everything
|
dom(v) = everything
|
dom(entry) = entry;
|
dom(entry) = entry;
|
|
|
while (anything changes)
|
while (anything changes)
|
foreach v
|
foreach v
|
dom(v) = {v} union (intersection of dom(p) over all predecessors of 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
|
The sets dom(v) are represented by the parent links in the current version
|
of the dominance tree. */
|
of the dominance tree. */
|
|
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
{
|
{
|
parent[i] = -1;
|
parent[i] = -1;
|
son[i] = -1;
|
son[i] = -1;
|
brother[i] = -1;
|
brother[i] = -1;
|
}
|
}
|
graphds_dfs (g, &entry, 1, &postorder, true, NULL);
|
graphds_dfs (g, &entry, 1, &postorder, true, NULL);
|
gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
|
gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
|
gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
|
gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
|
|
|
while (changed)
|
while (changed)
|
{
|
{
|
changed = false;
|
changed = false;
|
|
|
for (i = g->n_vertices - 2; i >= 0; i--)
|
for (i = g->n_vertices - 2; i >= 0; i--)
|
{
|
{
|
v = VEC_index (int, postorder, i);
|
v = VEC_index (int, postorder, i);
|
idom = -1;
|
idom = -1;
|
for (e = g->vertices[v].pred; e; e = e->pred_next)
|
for (e = g->vertices[v].pred; e; e = e->pred_next)
|
{
|
{
|
if (e->src != entry
|
if (e->src != entry
|
&& parent[e->src] == -1)
|
&& parent[e->src] == -1)
|
continue;
|
continue;
|
|
|
idom = tree_nca (idom, e->src, parent, marks, mark++);
|
idom = tree_nca (idom, e->src, parent, marks, mark++);
|
}
|
}
|
|
|
if (idom != parent[v])
|
if (idom != parent[v])
|
{
|
{
|
parent[v] = idom;
|
parent[v] = idom;
|
changed = true;
|
changed = true;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
free (marks);
|
free (marks);
|
VEC_free (int, heap, postorder);
|
VEC_free (int, heap, postorder);
|
|
|
for (i = 0; i < g->n_vertices; i++)
|
for (i = 0; i < g->n_vertices; i++)
|
if (parent[i] != -1)
|
if (parent[i] != -1)
|
{
|
{
|
brother[i] = son[parent[i]];
|
brother[i] = son[parent[i]];
|
son[parent[i]] = i;
|
son[parent[i]] = i;
|
}
|
}
|
}
|
}
|
|
|
