|
0
|
1 /* Graph representation and manipulation functions.
|
|
|
2 Copyright (C) 2007
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
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.
|
|
|
11
|
|
|
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.
|
|
|
16
|
|
|
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/>. */
|
|
|
20
|
|
|
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"
|
|
|
29
|
|
|
30 /* Dumps graph G into F. */
|
|
|
31
|
|
|
32 void
|
|
|
33 dump_graph (FILE *f, struct graph *g)
|
|
|
34 {
|
|
|
35 int i;
|
|
|
36 struct graph_edge *e;
|
|
|
37
|
|
|
38 for (i = 0; i < g->n_vertices; i++)
|
|
|
39 {
|
|
|
40 if (!g->vertices[i].pred
|
|
|
41 && !g->vertices[i].succ)
|
|
|
42 continue;
|
|
|
43
|
|
|
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");
|
|
|
48
|
|
|
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");
|
|
|
53 }
|
|
|
54 }
|
|
|
55
|
|
|
56 /* Creates a new graph with N_VERTICES vertices. */
|
|
|
57
|
|
|
58 struct graph *
|
|
|
59 new_graph (int n_vertices)
|
|
|
60 {
|
|
|
61 struct graph *g = XNEW (struct graph);
|
|
|
62
|
|
|
63 g->n_vertices = n_vertices;
|
|
|
64 g->vertices = XCNEWVEC (struct vertex, n_vertices);
|
|
|
65
|
|
|
66 return g;
|
|
|
67 }
|
|
|
68
|
|
|
69 /* Adds an edge from F to T to graph G. The new edge is returned. */
|
|
|
70
|
|
|
71 struct graph_edge *
|
|
|
72 add_edge (struct graph *g, int f, int t)
|
|
|
73 {
|
|
|
74 struct graph_edge *e = XNEW (struct graph_edge);
|
|
|
75 struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
|
|
|
76
|
|
|
77
|
|
|
78 e->src = f;
|
|
|
79 e->dest = t;
|
|
|
80
|
|
|
81 e->pred_next = vt->pred;
|
|
|
82 vt->pred = e;
|
|
|
83
|
|
|
84 e->succ_next = vf->succ;
|
|
|
85 vf->succ = e;
|
|
|
86
|
|
|
87 return e;
|
|
|
88 }
|
|
|
89
|
|
|
90 /* Moves all the edges incident with U to V. */
|
|
|
91
|
|
|
92 void
|
|
|
93 identify_vertices (struct graph *g, int v, int u)
|
|
|
94 {
|
|
|
95 struct vertex *vv = &g->vertices[v];
|
|
|
96 struct vertex *uu = &g->vertices[u];
|
|
|
97 struct graph_edge *e, *next;
|
|
|
98
|
|
|
99 for (e = uu->succ; e; e = next)
|
|
|
100 {
|
|
|
101 next = e->succ_next;
|
|
|
102
|
|
|
103 e->src = v;
|
|
|
104 e->succ_next = vv->succ;
|
|
|
105 vv->succ = e;
|
|
|
106 }
|
|
|
107 uu->succ = NULL;
|
|
|
108
|
|
|
109 for (e = uu->pred; e; e = next)
|
|
|
110 {
|
|
|
111 next = e->pred_next;
|
|
|
112
|
|
|
113 e->dest = v;
|
|
|
114 e->pred_next = vv->pred;
|
|
|
115 vv->pred = e;
|
|
|
116 }
|
|
|
117 uu->pred = NULL;
|
|
|
118 }
|
|
|
119
|
|
|
120 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
|
|
|
121 direction given by FORWARD. */
|
|
|
122
|
|
|
123 static inline int
|
|
|
124 dfs_edge_src (struct graph_edge *e, bool forward)
|
|
|
125 {
|
|
|
126 return forward ? e->src : e->dest;
|
|
|
127 }
|
|
|
128
|
|
|
129 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
|
|
|
130 the direction given by FORWARD. */
|
|
|
131
|
|
|
132 static inline int
|
|
|
133 dfs_edge_dest (struct graph_edge *e, bool forward)
|
|
|
134 {
|
|
|
135 return forward ? e->dest : e->src;
|
|
|
136 }
|
|
|
137
|
|
|
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. */
|
|
|
140
|
|
|
141 static inline struct graph_edge *
|
|
|
142 foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
|
|
|
143 {
|
|
|
144 int d;
|
|
|
145
|
|
|
146 if (!subgraph)
|
|
|
147 return e;
|
|
|
148
|
|
|
149 while (e)
|
|
|
150 {
|
|
|
151 d = dfs_edge_dest (e, forward);
|
|
|
152 if (bitmap_bit_p (subgraph, d))
|
|
|
153 return e;
|
|
|
154
|
|
|
155 e = forward ? e->succ_next : e->pred_next;
|
|
|
156 }
|
|
|
157
|
|
|
158 return e;
|
|
|
159 }
|
|
|
160
|
|
|
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. */
|
|
|
163
|
|
|
164 static inline struct graph_edge *
|
|
|
165 dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
|
|
|
166 {
|
|
|
167 struct graph_edge *e;
|
|
|
168
|
|
|
169 e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
|
|
|
170 return foll_in_subgraph (e, forward, subgraph);
|
|
|
171 }
|
|
|
172
|
|
|
173 /* Helper function for graphds_dfs. Returns the next edge after E, in the
|
|
|
174 graph direction given by FORWARD, that belongs to SUBGRAPH. */
|
|
|
175
|
|
|
176 static inline struct graph_edge *
|
|
|
177 dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
|
|
|
178 {
|
|
|
179 return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
|
|
|
180 forward, subgraph);
|
|
|
181 }
|
|
|
182
|
|
|
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). */
|
|
|
188
|
|
|
189 int
|
|
|
190 graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
|
|
|
191 bool forward, bitmap subgraph)
|
|
|
192 {
|
|
|
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;
|
|
|
198
|
|
|
199 if (subgraph)
|
|
|
200 {
|
|
|
201 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
|
|
|
202 {
|
|
|
203 g->vertices[av].component = -1;
|
|
|
204 g->vertices[av].post = -1;
|
|
|
205 }
|
|
|
206 }
|
|
|
207 else
|
|
|
208 {
|
|
|
209 for (i = 0; i < g->n_vertices; i++)
|
|
|
210 {
|
|
|
211 g->vertices[i].component = -1;
|
|
|
212 g->vertices[i].post = -1;
|
|
|
213 }
|
|
|
214 }
|
|
|
215
|
|
|
216 for (i = 0; i < nq; i++)
|
|
|
217 {
|
|
|
218 v = qs[i];
|
|
|
219 if (g->vertices[v].post != -1)
|
|
|
220 continue;
|
|
|
221
|
|
|
222 g->vertices[v].component = comp++;
|
|
|
223 e = dfs_fst_edge (g, v, forward, subgraph);
|
|
|
224 top = 0;
|
|
|
225
|
|
|
226 while (1)
|
|
|
227 {
|
|
|
228 while (e)
|
|
|
229 {
|
|
|
230 if (g->vertices[dfs_edge_dest (e, forward)].component
|
|
|
231 == -1)
|
|
|
232 break;
|
|
|
233 e = dfs_next_edge (e, forward, subgraph);
|
|
|
234 }
|
|
|
235
|
|
|
236 if (!e)
|
|
|
237 {
|
|
|
238 if (qt)
|
|
|
239 VEC_safe_push (int, heap, *qt, v);
|
|
|
240 g->vertices[v].post = tick++;
|
|
|
241
|
|
|
242 if (!top)
|
|
|
243 break;
|
|
|
244
|
|
|
245 e = stack[--top];
|
|
|
246 v = dfs_edge_src (e, forward);
|
|
|
247 e = dfs_next_edge (e, forward, subgraph);
|
|
|
248 continue;
|
|
|
249 }
|
|
|
250
|
|
|
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;
|
|
|
255 }
|
|
|
256 }
|
|
|
257
|
|
|
258 free (stack);
|
|
|
259
|
|
|
260 return comp;
|
|
|
261 }
|
|
|
262
|
|
|
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.
|
|
|
269
|
|
|
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. */
|
|
|
273
|
|
|
274 int
|
|
|
275 graphds_scc (struct graph *g, bitmap subgraph)
|
|
|
276 {
|
|
|
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;
|
|
|
282
|
|
|
283 if (subgraph)
|
|
|
284 {
|
|
|
285 nq = 0;
|
|
|
286 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
|
|
|
287 {
|
|
|
288 queue[nq++] = v;
|
|
|
289 }
|
|
|
290 }
|
|
|
291 else
|
|
|
292 {
|
|
|
293 for (i = 0; i < g->n_vertices; i++)
|
|
|
294 queue[i] = i;
|
|
|
295 nq = g->n_vertices;
|
|
|
296 }
|
|
|
297
|
|
|
298 graphds_dfs (g, queue, nq, &postorder, false, subgraph);
|
|
|
299 gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
|
|
|
300
|
|
|
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);
|
|
|
304
|
|
|
305 free (queue);
|
|
|
306 VEC_free (int, heap, postorder);
|
|
|
307
|
|
|
308 return comp;
|
|
|
309 }
|
|
|
310
|
|
|
311 /* Runs CALLBACK for all edges in G. */
|
|
|
312
|
|
|
313 void
|
|
|
314 for_each_edge (struct graph *g, graphds_edge_callback callback)
|
|
|
315 {
|
|
|
316 struct graph_edge *e;
|
|
|
317 int i;
|
|
|
318
|
|
|
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);
|
|
|
322 }
|
|
|
323
|
|
|
324 /* Releases the memory occupied by G. */
|
|
|
325
|
|
|
326 void
|
|
|
327 free_graph (struct graph *g)
|
|
|
328 {
|
|
|
329 struct graph_edge *e, *n;
|
|
|
330 struct vertex *v;
|
|
|
331 int i;
|
|
|
332
|
|
|
333 for (i = 0; i < g->n_vertices; i++)
|
|
|
334 {
|
|
|
335 v = &g->vertices[i];
|
|
|
336 for (e = v->succ; e; e = n)
|
|
|
337 {
|
|
|
338 n = e->succ_next;
|
|
|
339 free (e);
|
|
|
340 }
|
|
|
341 }
|
|
|
342 free (g->vertices);
|
|
|
343 free (g);
|
|
|
344 }
|
|
|
345
|
|
|
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. */
|
|
|
349
|
|
|
350 static int
|
|
|
351 tree_nca (int x, int y, int *parent, int *marks, int mark)
|
|
|
352 {
|
|
|
353 if (x == -1 || x == y)
|
|
|
354 return y;
|
|
|
355
|
|
|
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;
|
|
|
360
|
|
|
361 while (1)
|
|
|
362 {
|
|
|
363 x = parent[x];
|
|
|
364 if (x == -1)
|
|
|
365 break;
|
|
|
366 if (marks[x] == mark)
|
|
|
367 return x;
|
|
|
368 marks[x] = mark;
|
|
|
369
|
|
|
370 y = parent[y];
|
|
|
371 if (y == -1)
|
|
|
372 break;
|
|
|
373 if (marks[y] == mark)
|
|
|
374 return y;
|
|
|
375 marks[y] = mark;
|
|
|
376 }
|
|
|
377
|
|
|
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)
|
|
|
382 {
|
|
|
383 for (y = parent[y]; marks[y] != mark; y = parent[y])
|
|
|
384 continue;
|
|
|
385
|
|
|
386 return y;
|
|
|
387 }
|
|
|
388 else
|
|
|
389 {
|
|
|
390 for (x = parent[x]; marks[x] != mark; x = parent[x])
|
|
|
391 continue;
|
|
|
392
|
|
|
393 return x;
|
|
|
394 }
|
|
|
395 }
|
|
|
396
|
|
|
397 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
|
|
|
398 arrays), where the entry node is ENTRY. */
|
|
|
399
|
|
|
400 void
|
|
|
401 graphds_domtree (struct graph *g, int entry,
|
|
|
402 int *parent, int *son, int *brother)
|
|
|
403 {
|
|
|
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;
|
|
|
409
|
|
|
410 /* We use a slight modification of the standard iterative algorithm, as
|
|
|
411 described in
|
|
|
412
|
|
|
413 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
|
|
414 Algorithm
|
|
|
415
|
|
|
416 sort vertices in reverse postorder
|
|
|
417 foreach v
|
|
|
418 dom(v) = everything
|
|
|
419 dom(entry) = entry;
|
|
|
420
|
|
|
421 while (anything changes)
|
|
|
422 foreach v
|
|
|
423 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
|
|
|
424
|
|
|
425 The sets dom(v) are represented by the parent links in the current version
|
|
|
426 of the dominance tree. */
|
|
|
427
|
|
|
428 for (i = 0; i < g->n_vertices; i++)
|
|
|
429 {
|
|
|
430 parent[i] = -1;
|
|
|
431 son[i] = -1;
|
|
|
432 brother[i] = -1;
|
|
|
433 }
|
|
|
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);
|
|
|
437
|
|
|
438 while (changed)
|
|
|
439 {
|
|
|
440 changed = false;
|
|
|
441
|
|
|
442 for (i = g->n_vertices - 2; i >= 0; i--)
|
|
|
443 {
|
|
|
444 v = VEC_index (int, postorder, i);
|
|
|
445 idom = -1;
|
|
|
446 for (e = g->vertices[v].pred; e; e = e->pred_next)
|
|
|
447 {
|
|
|
448 if (e->src != entry
|
|
|
449 && parent[e->src] == -1)
|
|
|
450 continue;
|
|
|
451
|
|
|
452 idom = tree_nca (idom, e->src, parent, marks, mark++);
|
|
|
453 }
|
|
|
454
|
|
|
455 if (idom != parent[v])
|
|
|
456 {
|
|
|
457 parent[v] = idom;
|
|
|
458 changed = true;
|
|
|
459 }
|
|
|
460 }
|
|
|
461 }
|
|
|
462
|
|
|
463 free (marks);
|
|
|
464 VEC_free (int, heap, postorder);
|
|
|
465
|
|
|
466 for (i = 0; i < g->n_vertices; i++)
|
|
|
467 if (parent[i] != -1)
|
|
|
468 {
|
|
|
469 brother[i] = son[parent[i]];
|
|
|
470 son[parent[i]] = i;
|
|
|
471 }
|
|
|
472 }
|
