-/* 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. */
-
-static void
-check_irred (struct graph *g, struct edge *e)
-{
- edge real = e->data;
-
- /* All edges should lead from a component with higher number to the
- one with lower one. */
- gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
-
- if (g->vertices[e->src].component != g->vertices[e->dest].component)
- return;
-
- real->flags |= EDGE_IRREDUCIBLE_LOOP;
- if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
- 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);
-}
-
OSDN Git Service
