Mercurial > hg > CbC > CbC_gcc
comparison gcc/graphds.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
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 } |