* ChangeLog: Fix whitespace.
[official-gcc.git] / gcc / graphds.c
blob4ee71dff904d485fd501540042c338290a0d8ef3
1 /* Graph representation and manipulation functions.
2 Copyright (C) 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "obstack.h"
25 #include "bitmap.h"
26 #include "vec.h"
27 #include "vecprim.h"
28 #include "graphds.h"
30 /* Dumps graph G into F. */
32 void
33 dump_graph (FILE *f, struct graph *g)
35 int i;
36 struct graph_edge *e;
38 for (i = 0; i < g->n_vertices; i++)
40 if (!g->vertices[i].pred
41 && !g->vertices[i].succ)
42 continue;
44 fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
45 for (e = g->vertices[i].pred; e; e = e->pred_next)
46 fprintf (f, " %d", e->src);
47 fprintf (f, "\n");
49 fprintf (f, "\t->");
50 for (e = g->vertices[i].succ; e; e = e->succ_next)
51 fprintf (f, " %d", e->dest);
52 fprintf (f, "\n");
56 /* Creates a new graph with N_VERTICES vertices. */
58 struct graph *
59 new_graph (int n_vertices)
61 struct graph *g = XNEW (struct graph);
63 g->n_vertices = n_vertices;
64 g->vertices = XCNEWVEC (struct vertex, n_vertices);
66 return g;
69 /* Adds an edge from F to T to graph G. The new edge is returned. */
71 struct graph_edge *
72 add_edge (struct graph *g, int f, int t)
74 struct graph_edge *e = XNEW (struct graph_edge);
75 struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
78 e->src = f;
79 e->dest = t;
81 e->pred_next = vt->pred;
82 vt->pred = e;
84 e->succ_next = vf->succ;
85 vf->succ = e;
87 return e;
90 /* Moves all the edges incident with U to V. */
92 void
93 identify_vertices (struct graph *g, int v, int u)
95 struct vertex *vv = &g->vertices[v];
96 struct vertex *uu = &g->vertices[u];
97 struct graph_edge *e, *next;
99 for (e = uu->succ; e; e = next)
101 next = e->succ_next;
103 e->src = v;
104 e->succ_next = vv->succ;
105 vv->succ = e;
107 uu->succ = NULL;
109 for (e = uu->pred; e; e = next)
111 next = e->pred_next;
113 e->dest = v;
114 e->pred_next = vv->pred;
115 vv->pred = e;
117 uu->pred = NULL;
120 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
121 direction given by FORWARD. */
123 static inline int
124 dfs_edge_src (struct graph_edge *e, bool forward)
126 return forward ? e->src : e->dest;
129 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
130 the direction given by FORWARD. */
132 static inline int
133 dfs_edge_dest (struct graph_edge *e, bool forward)
135 return forward ? e->dest : e->src;
138 /* Helper function for graphds_dfs. Returns the first edge after E (including
139 E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
141 static inline struct graph_edge *
142 foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
144 int d;
146 if (!subgraph)
147 return e;
149 while (e)
151 d = dfs_edge_dest (e, forward);
152 if (bitmap_bit_p (subgraph, d))
153 return e;
155 e = forward ? e->succ_next : e->pred_next;
158 return e;
161 /* Helper function for graphds_dfs. Select the first edge from V in G, in the
162 direction given by FORWARD, that belongs to SUBGRAPH. */
164 static inline struct graph_edge *
165 dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
167 struct graph_edge *e;
169 e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
170 return foll_in_subgraph (e, forward, subgraph);
173 /* Helper function for graphds_dfs. Returns the next edge after E, in the
174 graph direction given by FORWARD, that belongs to SUBGRAPH. */
176 static inline struct graph_edge *
177 dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
179 return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
180 forward, subgraph);
183 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
184 The vertices in postorder are stored into QT. If FORWARD is false,
185 backward dfs is run. If SUBGRAPH is not NULL, it specifies the
186 subgraph of G to run DFS on. Returns the number of the components
187 of the graph (number of the restarts of DFS). */
190 graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
191 bool forward, bitmap subgraph)
193 int i, tick = 0, v, comp = 0, top;
194 struct graph_edge *e;
195 struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
196 bitmap_iterator bi;
197 unsigned av;
199 if (subgraph)
201 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
203 g->vertices[av].component = -1;
204 g->vertices[av].post = -1;
207 else
209 for (i = 0; i < g->n_vertices; i++)
211 g->vertices[i].component = -1;
212 g->vertices[i].post = -1;
216 for (i = 0; i < nq; i++)
218 v = qs[i];
219 if (g->vertices[v].post != -1)
220 continue;
222 g->vertices[v].component = comp++;
223 e = dfs_fst_edge (g, v, forward, subgraph);
224 top = 0;
226 while (1)
228 while (e)
230 if (g->vertices[dfs_edge_dest (e, forward)].component
231 == -1)
232 break;
233 e = dfs_next_edge (e, forward, subgraph);
236 if (!e)
238 if (qt)
239 VEC_safe_push (int, heap, *qt, v);
240 g->vertices[v].post = tick++;
242 if (!top)
243 break;
245 e = stack[--top];
246 v = dfs_edge_src (e, forward);
247 e = dfs_next_edge (e, forward, subgraph);
248 continue;
251 stack[top++] = e;
252 v = dfs_edge_dest (e, forward);
253 e = dfs_fst_edge (g, v, forward, subgraph);
254 g->vertices[v].component = comp - 1;
258 free (stack);
260 return comp;
263 /* Determines the strongly connected components of G, using the algorithm of
264 Tarjan -- first determine the postorder dfs numbering in reversed graph,
265 then run the dfs on the original graph in the order given by decreasing
266 numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
267 specifies the subgraph of G whose strongly connected components we want
268 to determine.
270 After running this function, v->component is the number of the strongly
271 connected component for each vertex of G. Returns the number of the
272 sccs of G. */
275 graphds_scc (struct graph *g, bitmap subgraph)
277 int *queue = XNEWVEC (int, g->n_vertices);
278 VEC (int, heap) *postorder = NULL;
279 int nq, i, comp;
280 unsigned v;
281 bitmap_iterator bi;
283 if (subgraph)
285 nq = 0;
286 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
288 queue[nq++] = v;
291 else
293 for (i = 0; i < g->n_vertices; i++)
294 queue[i] = i;
295 nq = g->n_vertices;
298 graphds_dfs (g, queue, nq, &postorder, false, subgraph);
299 gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
301 for (i = 0; i < nq; i++)
302 queue[i] = VEC_index (int, postorder, nq - i - 1);
303 comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
305 free (queue);
306 VEC_free (int, heap, postorder);
308 return comp;
311 /* Runs CALLBACK for all edges in G. */
313 void
314 for_each_edge (struct graph *g, graphds_edge_callback callback)
316 struct graph_edge *e;
317 int i;
319 for (i = 0; i < g->n_vertices; i++)
320 for (e = g->vertices[i].succ; e; e = e->succ_next)
321 callback (g, e);
324 /* Releases the memory occupied by G. */
326 void
327 free_graph (struct graph *g)
329 struct graph_edge *e, *n;
330 struct vertex *v;
331 int i;
333 for (i = 0; i < g->n_vertices; i++)
335 v = &g->vertices[i];
336 for (e = v->succ; e; e = n)
338 n = e->succ_next;
339 free (e);
342 free (g->vertices);
343 free (g);
346 /* Returns the nearest common ancestor of X and Y in tree whose parent
347 links are given by PARENT. MARKS is the array used to mark the
348 vertices of the tree, and MARK is the number currently used as a mark. */
350 static int
351 tree_nca (int x, int y, int *parent, int *marks, int mark)
353 if (x == -1 || x == y)
354 return y;
356 /* We climb with X and Y up the tree, marking the visited nodes. When
357 we first arrive to a marked node, it is the common ancestor. */
358 marks[x] = mark;
359 marks[y] = mark;
361 while (1)
363 x = parent[x];
364 if (x == -1)
365 break;
366 if (marks[x] == mark)
367 return x;
368 marks[x] = mark;
370 y = parent[y];
371 if (y == -1)
372 break;
373 if (marks[y] == mark)
374 return y;
375 marks[y] = mark;
378 /* If we reached the root with one of the vertices, continue
379 with the other one till we reach the marked part of the
380 tree. */
381 if (x == -1)
383 for (y = parent[y]; marks[y] != mark; y = parent[y])
384 continue;
386 return y;
388 else
390 for (x = parent[x]; marks[x] != mark; x = parent[x])
391 continue;
393 return x;
397 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
398 arrays), where the entry node is ENTRY. */
400 void
401 graphds_domtree (struct graph *g, int entry,
402 int *parent, int *son, int *brother)
404 VEC (int, heap) *postorder = NULL;
405 int *marks = XCNEWVEC (int, g->n_vertices);
406 int mark = 1, i, v, idom;
407 bool changed = true;
408 struct graph_edge *e;
410 /* We use a slight modification of the standard iterative algorithm, as
411 described in
413 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
414 Algorithm
416 sort vertices in reverse postorder
417 foreach v
418 dom(v) = everything
419 dom(entry) = entry;
421 while (anything changes)
422 foreach v
423 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
425 The sets dom(v) are represented by the parent links in the current version
426 of the dominance tree. */
428 for (i = 0; i < g->n_vertices; i++)
430 parent[i] = -1;
431 son[i] = -1;
432 brother[i] = -1;
434 graphds_dfs (g, &entry, 1, &postorder, true, NULL);
435 gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
436 gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
438 while (changed)
440 changed = false;
442 for (i = g->n_vertices - 2; i >= 0; i--)
444 v = VEC_index (int, postorder, i);
445 idom = -1;
446 for (e = g->vertices[v].pred; e; e = e->pred_next)
448 if (e->src != entry
449 && parent[e->src] == -1)
450 continue;
452 idom = tree_nca (idom, e->src, parent, marks, mark++);
455 if (idom != parent[v])
457 parent[v] = idom;
458 changed = true;
463 free (marks);
464 VEC_free (int, heap, postorder);
466 for (i = 0; i < g->n_vertices; i++)
467 if (parent[i] != -1)
469 brother[i] = son[parent[i]];
470 son[parent[i]] = i;