2015-12-18 Ville Voutilainen <ville.voutilainen@gmail.com>
[official-gcc.git] / gcc / graphds.c
blobc4e07330dfb59772cb7493911fd1e7033f9416cd
1 /* Graph representation and manipulation functions.
2 Copyright (C) 2007-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "bitmap.h"
24 #include "graphds.h"
26 /* Dumps graph G into F. */
28 void
29 dump_graph (FILE *f, struct graph *g)
31 int i;
32 struct graph_edge *e;
34 for (i = 0; i < g->n_vertices; i++)
36 if (!g->vertices[i].pred
37 && !g->vertices[i].succ)
38 continue;
40 fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
41 for (e = g->vertices[i].pred; e; e = e->pred_next)
42 fprintf (f, " %d", e->src);
43 fprintf (f, "\n");
45 fprintf (f, "\t->");
46 for (e = g->vertices[i].succ; e; e = e->succ_next)
47 fprintf (f, " %d", e->dest);
48 fprintf (f, "\n");
52 /* Creates a new graph with N_VERTICES vertices. */
54 struct graph *
55 new_graph (int n_vertices)
57 struct graph *g = XNEW (struct graph);
59 gcc_obstack_init (&g->ob);
60 g->n_vertices = n_vertices;
61 g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
62 memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
64 return g;
67 /* Adds an edge from F to T to graph G. The new edge is returned. */
69 struct graph_edge *
70 add_edge (struct graph *g, int f, int t)
72 struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
73 struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
75 e->src = f;
76 e->dest = t;
78 e->pred_next = vt->pred;
79 vt->pred = e;
81 e->succ_next = vf->succ;
82 vf->succ = e;
84 return e;
87 /* Moves all the edges incident with U to V. */
89 void
90 identify_vertices (struct graph *g, int v, int u)
92 struct vertex *vv = &g->vertices[v];
93 struct vertex *uu = &g->vertices[u];
94 struct graph_edge *e, *next;
96 for (e = uu->succ; e; e = next)
98 next = e->succ_next;
100 e->src = v;
101 e->succ_next = vv->succ;
102 vv->succ = e;
104 uu->succ = NULL;
106 for (e = uu->pred; e; e = next)
108 next = e->pred_next;
110 e->dest = v;
111 e->pred_next = vv->pred;
112 vv->pred = e;
114 uu->pred = NULL;
117 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
118 direction given by FORWARD. */
120 static inline int
121 dfs_edge_src (struct graph_edge *e, bool forward)
123 return forward ? e->src : e->dest;
126 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
127 the direction given by FORWARD. */
129 static inline int
130 dfs_edge_dest (struct graph_edge *e, bool forward)
132 return forward ? e->dest : e->src;
135 /* Helper function for graphds_dfs. Returns the first edge after E (including
136 E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
138 static inline struct graph_edge *
139 foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
141 int d;
143 if (!subgraph)
144 return e;
146 while (e)
148 d = dfs_edge_dest (e, forward);
149 if (bitmap_bit_p (subgraph, d))
150 return e;
152 e = forward ? e->succ_next : e->pred_next;
155 return e;
158 /* Helper function for graphds_dfs. Select the first edge from V in G, in the
159 direction given by FORWARD, that belongs to SUBGRAPH. */
161 static inline struct graph_edge *
162 dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
164 struct graph_edge *e;
166 e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
167 return foll_in_subgraph (e, forward, subgraph);
170 /* Helper function for graphds_dfs. Returns the next edge after E, in the
171 graph direction given by FORWARD, that belongs to SUBGRAPH. */
173 static inline struct graph_edge *
174 dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
176 return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
177 forward, subgraph);
180 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
181 The vertices in postorder are stored into QT. If FORWARD is false,
182 backward dfs is run. If SUBGRAPH is not NULL, it specifies the
183 subgraph of G to run DFS on. Returns the number of the components
184 of the graph (number of the restarts of DFS). */
187 graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
188 bool forward, bitmap subgraph)
190 int i, tick = 0, v, comp = 0, top;
191 struct graph_edge *e;
192 struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
193 bitmap_iterator bi;
194 unsigned av;
196 if (subgraph)
198 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
200 g->vertices[av].component = -1;
201 g->vertices[av].post = -1;
204 else
206 for (i = 0; i < g->n_vertices; i++)
208 g->vertices[i].component = -1;
209 g->vertices[i].post = -1;
213 for (i = 0; i < nq; i++)
215 v = qs[i];
216 if (g->vertices[v].post != -1)
217 continue;
219 g->vertices[v].component = comp++;
220 e = dfs_fst_edge (g, v, forward, subgraph);
221 top = 0;
223 while (1)
225 while (e)
227 if (g->vertices[dfs_edge_dest (e, forward)].component
228 == -1)
229 break;
230 e = dfs_next_edge (e, forward, subgraph);
233 if (!e)
235 if (qt)
236 qt->safe_push (v);
237 g->vertices[v].post = tick++;
239 if (!top)
240 break;
242 e = stack[--top];
243 v = dfs_edge_src (e, forward);
244 e = dfs_next_edge (e, forward, subgraph);
245 continue;
248 stack[top++] = e;
249 v = dfs_edge_dest (e, forward);
250 e = dfs_fst_edge (g, v, forward, subgraph);
251 g->vertices[v].component = comp - 1;
255 free (stack);
257 return comp;
260 /* Determines the strongly connected components of G, using the algorithm of
261 Tarjan -- first determine the postorder dfs numbering in reversed graph,
262 then run the dfs on the original graph in the order given by decreasing
263 numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
264 specifies the subgraph of G whose strongly connected components we want
265 to determine.
267 After running this function, v->component is the number of the strongly
268 connected component for each vertex of G. Returns the number of the
269 sccs of G. */
272 graphds_scc (struct graph *g, bitmap subgraph)
274 int *queue = XNEWVEC (int, g->n_vertices);
275 vec<int> postorder = vNULL;
276 int nq, i, comp;
277 unsigned v;
278 bitmap_iterator bi;
280 if (subgraph)
282 nq = 0;
283 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
285 queue[nq++] = v;
288 else
290 for (i = 0; i < g->n_vertices; i++)
291 queue[i] = i;
292 nq = g->n_vertices;
295 graphds_dfs (g, queue, nq, &postorder, false, subgraph);
296 gcc_assert (postorder.length () == (unsigned) nq);
298 for (i = 0; i < nq; i++)
299 queue[i] = postorder[nq - i - 1];
300 comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
302 free (queue);
303 postorder.release ();
305 return comp;
308 /* Runs CALLBACK for all edges in G. */
310 void
311 for_each_edge (struct graph *g, graphds_edge_callback callback)
313 struct graph_edge *e;
314 int i;
316 for (i = 0; i < g->n_vertices; i++)
317 for (e = g->vertices[i].succ; e; e = e->succ_next)
318 callback (g, e);
321 /* Releases the memory occupied by G. */
323 void
324 free_graph (struct graph *g)
326 obstack_free (&g->ob, NULL);
327 free (g);
330 /* Returns the nearest common ancestor of X and Y in tree whose parent
331 links are given by PARENT. MARKS is the array used to mark the
332 vertices of the tree, and MARK is the number currently used as a mark. */
334 static int
335 tree_nca (int x, int y, int *parent, int *marks, int mark)
337 if (x == -1 || x == y)
338 return y;
340 /* We climb with X and Y up the tree, marking the visited nodes. When
341 we first arrive to a marked node, it is the common ancestor. */
342 marks[x] = mark;
343 marks[y] = mark;
345 while (1)
347 x = parent[x];
348 if (x == -1)
349 break;
350 if (marks[x] == mark)
351 return x;
352 marks[x] = mark;
354 y = parent[y];
355 if (y == -1)
356 break;
357 if (marks[y] == mark)
358 return y;
359 marks[y] = mark;
362 /* If we reached the root with one of the vertices, continue
363 with the other one till we reach the marked part of the
364 tree. */
365 if (x == -1)
367 for (y = parent[y]; marks[y] != mark; y = parent[y])
368 continue;
370 return y;
372 else
374 for (x = parent[x]; marks[x] != mark; x = parent[x])
375 continue;
377 return x;
381 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
382 arrays), where the entry node is ENTRY. */
384 void
385 graphds_domtree (struct graph *g, int entry,
386 int *parent, int *son, int *brother)
388 vec<int> postorder = vNULL;
389 int *marks = XCNEWVEC (int, g->n_vertices);
390 int mark = 1, i, v, idom;
391 bool changed = true;
392 struct graph_edge *e;
394 /* We use a slight modification of the standard iterative algorithm, as
395 described in
397 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
398 Algorithm
400 sort vertices in reverse postorder
401 foreach v
402 dom(v) = everything
403 dom(entry) = entry;
405 while (anything changes)
406 foreach v
407 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
409 The sets dom(v) are represented by the parent links in the current version
410 of the dominance tree. */
412 for (i = 0; i < g->n_vertices; i++)
414 parent[i] = -1;
415 son[i] = -1;
416 brother[i] = -1;
418 graphds_dfs (g, &entry, 1, &postorder, true, NULL);
419 gcc_assert (postorder.length () == (unsigned) g->n_vertices);
420 gcc_assert (postorder[g->n_vertices - 1] == entry);
422 while (changed)
424 changed = false;
426 for (i = g->n_vertices - 2; i >= 0; i--)
428 v = postorder[i];
429 idom = -1;
430 for (e = g->vertices[v].pred; e; e = e->pred_next)
432 if (e->src != entry
433 && parent[e->src] == -1)
434 continue;
436 idom = tree_nca (idom, e->src, parent, marks, mark++);
439 if (idom != parent[v])
441 parent[v] = idom;
442 changed = true;
447 free (marks);
448 postorder.release ();
450 for (i = 0; i < g->n_vertices; i++)
451 if (parent[i] != -1)
453 brother[i] = son[parent[i]];
454 son[parent[i]] = i;