Branch data Line data Source code
1 : : /* Graph representation and manipulation functions.
2 : : Copyright (C) 2007-2024 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
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.
10 : :
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.
15 : :
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/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "bitmap.h"
24 : : #include "graphds.h"
25 : :
26 : : /* Dumps graph G into F. */
27 : :
28 : : void
29 : 0 : dump_graph (FILE *f, struct graph *g)
30 : : {
31 : 0 : int i;
32 : 0 : struct graph_edge *e;
33 : :
34 : 0 : fprintf (f, "digraph {\n");
35 : 0 : for (i = 0; i < g->n_vertices; i++)
36 : : {
37 : 0 : fprintf (f, "\"%d\" [label=\"%d (%d): %p\"];\n",
38 : 0 : i, i, g->vertices[i].component, g->vertices[i].data);
39 : 0 : for (e = g->vertices[i].pred; e; e = e->pred_next)
40 : 0 : fprintf (f, "\"%d\" -> \"%d\" [label=\"%p\"];\n", e->src, e->dest, e->data);
41 : 0 : for (e = g->vertices[i].succ; e; e = e->succ_next)
42 : 0 : fprintf (f, "\"%d\" -> \"%d\";\n", e->src, e->dest);
43 : : }
44 : 0 : fprintf (f, "}\n");
45 : 0 : }
46 : :
47 : : /* Creates a new graph with N_VERTICES vertices. */
48 : :
49 : : struct graph *
50 : 64052585 : new_graph (int n_vertices)
51 : : {
52 : 64052585 : struct graph *g = XNEW (struct graph);
53 : :
54 : 64052585 : gcc_obstack_init (&g->ob);
55 : 64052585 : g->n_vertices = n_vertices;
56 : 64052585 : g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
57 : 64052585 : memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
58 : :
59 : 64052585 : return g;
60 : : }
61 : :
62 : : /* Adds an edge from F to T to graph G. The new edge is returned. */
63 : :
64 : : struct graph_edge *
65 : 881157906 : add_edge (struct graph *g, int f, int t)
66 : : {
67 : 881157906 : struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
68 : 881157906 : struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
69 : :
70 : 881157906 : e->src = f;
71 : 881157906 : e->dest = t;
72 : :
73 : 881157906 : e->pred_next = vt->pred;
74 : 881157906 : vt->pred = e;
75 : :
76 : 881157906 : e->succ_next = vf->succ;
77 : 881157906 : vf->succ = e;
78 : :
79 : 881157906 : e->data = NULL;
80 : 881157906 : return e;
81 : : }
82 : :
83 : : /* Moves all the edges incident with U to V. */
84 : :
85 : : void
86 : 1707969 : identify_vertices (struct graph *g, int v, int u)
87 : : {
88 : 1707969 : struct vertex *vv = &g->vertices[v];
89 : 1707969 : struct vertex *uu = &g->vertices[u];
90 : 1707969 : struct graph_edge *e, *next;
91 : :
92 : 3449368 : for (e = uu->succ; e; e = next)
93 : : {
94 : 1741399 : next = e->succ_next;
95 : :
96 : 1741399 : e->src = v;
97 : 1741399 : e->succ_next = vv->succ;
98 : 1741399 : vv->succ = e;
99 : : }
100 : 1707969 : uu->succ = NULL;
101 : :
102 : 4958734 : for (e = uu->pred; e; e = next)
103 : : {
104 : 3250765 : next = e->pred_next;
105 : :
106 : 3250765 : e->dest = v;
107 : 3250765 : e->pred_next = vv->pred;
108 : 3250765 : vv->pred = e;
109 : : }
110 : 1707969 : uu->pred = NULL;
111 : 1707969 : }
112 : :
113 : : /* Helper function for graphds_dfs. Returns the source vertex of E, in the
114 : : direction given by FORWARD. */
115 : :
116 : : static inline int
117 : 178837558 : dfs_edge_src (struct graph_edge *e, bool forward)
118 : : {
119 : 178837558 : return forward ? e->src : e->dest;
120 : : }
121 : :
122 : : /* Helper function for graphds_dfs. Returns the destination vertex of E, in
123 : : the direction given by FORWARD. */
124 : :
125 : : static inline int
126 : 1754922840 : dfs_edge_dest (struct graph_edge *e, bool forward)
127 : : {
128 : 1754922840 : return forward ? e->dest : e->src;
129 : : }
130 : :
131 : : /* Helper function for graphds_dfs. Returns the first edge after E (including
132 : : E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. If
133 : : SKIP_EDGE_P is not NULL, it points to a callback function. Edge E will be
134 : : skipped if callback function returns true. */
135 : :
136 : : static inline struct graph_edge *
137 : 3670365213 : foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph,
138 : : skip_edge_callback skip_edge_p)
139 : : {
140 : 3670365213 : int d;
141 : :
142 : 3670365213 : if (!e)
143 : : return e;
144 : :
145 : 1752249292 : if (!subgraph && (!skip_edge_p || !skip_edge_p (e)))
146 : 1749492343 : return e;
147 : :
148 : 4195764 : while (e)
149 : : {
150 : 3434656 : d = dfs_edge_dest (e, forward);
151 : : /* Return edge if it belongs to subgraph and shouldn't be skipped. */
152 : 3350285 : if ((!subgraph || bitmap_bit_p (subgraph, d))
153 : 5424102 : && (!skip_edge_p || !skip_edge_p (e)))
154 : 1995841 : return e;
155 : :
156 : 1438815 : e = forward ? e->succ_next : e->pred_next;
157 : : }
158 : :
159 : : return e;
160 : : }
161 : :
162 : : /* Helper function for graphds_dfs. Select the first edge from V in G, in the
163 : : direction given by FORWARD, that belongs to SUBGRAPH. If SKIP_EDGE_P is not
164 : : NULL, it points to a callback function. Edge E will be skipped if callback
165 : : function returns true. */
166 : :
167 : : static inline struct graph_edge *
168 : 1918877029 : dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph,
169 : : skip_edge_callback skip_edge_p)
170 : : {
171 : 1918877029 : struct graph_edge *e;
172 : :
173 : 1918877029 : e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
174 : 1918877029 : return foll_in_subgraph (e, forward, subgraph, skip_edge_p);
175 : : }
176 : :
177 : : /* Helper function for graphds_dfs. Returns the next edge after E, in the
178 : : graph direction given by FORWARD, that belongs to SUBGRAPH. If SKIP_EDGE_P
179 : : is not NULL, it points to a callback function. Edge E will be skipped if
180 : : callback function returns true. */
181 : :
182 : : static inline struct graph_edge *
183 : 1751488184 : dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph,
184 : : skip_edge_callback skip_edge_p)
185 : : {
186 : 1751488184 : return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
187 : : forward, subgraph, skip_edge_p);
188 : : }
189 : :
190 : : /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
191 : : The vertices in postorder are stored into QT. If FORWARD is false,
192 : : backward dfs is run. If SUBGRAPH is not NULL, it specifies the
193 : : subgraph of G to run DFS on. Returns the number of the components
194 : : of the graph (number of the restarts of DFS). If SKIP_EDGE_P is not
195 : : NULL, it points to a callback function. Edge E will be skipped if
196 : : callback function returns true. */
197 : :
198 : : int
199 : 127253363 : graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
200 : : bool forward, bitmap subgraph,
201 : : skip_edge_callback skip_edge_p)
202 : : {
203 : 127253363 : int i, tick = 0, v, comp = 0, top;
204 : 127253363 : struct graph_edge *e;
205 : 127253363 : struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
206 : 127253363 : bitmap_iterator bi;
207 : 127253363 : unsigned av;
208 : :
209 : 127253363 : if (subgraph)
210 : : {
211 : 4002454 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
212 : : {
213 : 2699440 : g->vertices[av].component = -1;
214 : 2699440 : g->vertices[av].post = -1;
215 : : }
216 : : }
217 : : else
218 : : {
219 : 2048708448 : for (i = 0; i < g->n_vertices; i++)
220 : : {
221 : 1922758099 : g->vertices[i].component = -1;
222 : 1922758099 : g->vertices[i].post = -1;
223 : : }
224 : : }
225 : :
226 : 2037409932 : for (i = 0; i < nq; i++)
227 : : {
228 : 1910156569 : v = qs[i];
229 : 1910156569 : if (g->vertices[v].post != -1)
230 : 170117098 : continue;
231 : :
232 : 1740039471 : g->vertices[v].component = comp++;
233 : 1740039471 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
234 : 1740039471 : top = 0;
235 : :
236 : : while (1)
237 : : {
238 : 3670365213 : while (e)
239 : : {
240 : 3502976368 : if (g->vertices[dfs_edge_dest (e, forward)].component
241 : : == -1)
242 : : break;
243 : 3145301252 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
244 : : }
245 : :
246 : 2276552145 : if (!e)
247 : : {
248 : 1918877029 : if (qt)
249 : 978225962 : qt->safe_push (v);
250 : 1918877029 : g->vertices[v].post = tick++;
251 : :
252 : 1918877029 : if (!top)
253 : : break;
254 : :
255 : 178837558 : e = stack[--top];
256 : 178837558 : v = dfs_edge_src (e, forward);
257 : 178837558 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
258 : 178837558 : continue;
259 : : }
260 : :
261 : 178837558 : stack[top++] = e;
262 : 178837558 : v = dfs_edge_dest (e, forward);
263 : 178837558 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
264 : 178837558 : g->vertices[v].component = comp - 1;
265 : : }
266 : : }
267 : :
268 : 127253363 : free (stack);
269 : :
270 : 127253363 : return comp;
271 : : }
272 : :
273 : : /* Determines the strongly connected components of G, using the algorithm of
274 : : Kosaraju -- first determine the postorder dfs numbering in reversed graph,
275 : : then run the dfs on the original graph in the order given by decreasing
276 : : numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
277 : : specifies the subgraph of G whose strongly connected components we want
278 : : to determine. If SKIP_EDGE_P is not NULL, it points to a callback function.
279 : : Edge E will be skipped if callback function returns true. If SCC_GROUPING
280 : : is not null, the nodes will be added to it in the following order:
281 : :
282 : : - If SCC A is a direct or indirect predecessor of SCC B in the SCC dag,
283 : : A's nodes come before B's nodes.
284 : :
285 : : - All of an SCC's nodes are listed consecutively, although the order
286 : : of the nodes within an SCC is not really meaningful.
287 : :
288 : : After running this function, v->component is the number of the strongly
289 : : connected component for each vertex of G. Returns the number of the
290 : : sccs of G. */
291 : :
292 : : int
293 : 62465338 : graphds_scc (struct graph *g, bitmap subgraph,
294 : : skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
295 : : {
296 : 62465338 : int *queue = XNEWVEC (int, g->n_vertices);
297 : 62465338 : vec<int> postorder = vNULL;
298 : 62465338 : int nq, i, comp;
299 : 62465338 : unsigned v;
300 : 62465338 : bitmap_iterator bi;
301 : :
302 : 62465338 : if (subgraph)
303 : : {
304 : 651507 : nq = 0;
305 : 2001227 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
306 : : {
307 : 1349720 : queue[nq++] = v;
308 : : }
309 : : }
310 : : else
311 : : {
312 : 1011825950 : for (i = 0; i < g->n_vertices; i++)
313 : 950012119 : queue[i] = i;
314 : : nq = g->n_vertices;
315 : : }
316 : :
317 : 62465338 : graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
318 : 124930676 : gcc_assert (postorder.length () == (unsigned) nq);
319 : :
320 : 1013827177 : for (i = 0; i < nq; i++)
321 : 951361839 : queue[i] = postorder[nq - i - 1];
322 : 62465338 : comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p);
323 : :
324 : 62465338 : free (queue);
325 : 62465338 : postorder.release ();
326 : :
327 : 62465338 : return comp;
328 : : }
329 : :
330 : : /* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
331 : :
332 : : void
333 : 11369 : for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
334 : : {
335 : 11369 : struct graph_edge *e;
336 : 11369 : int i;
337 : :
338 : 64532 : for (i = 0; i < g->n_vertices; i++)
339 : 89318 : for (e = g->vertices[i].succ; e; e = e->succ_next)
340 : 36155 : callback (g, e, data);
341 : 11369 : }
342 : :
343 : : /* Releases the memory occupied by G. */
344 : :
345 : : void
346 : 64052585 : free_graph (struct graph *g)
347 : : {
348 : 64052585 : obstack_free (&g->ob, NULL);
349 : 64052585 : free (g);
350 : 64052585 : }
351 : :
352 : : /* Returns the nearest common ancestor of X and Y in tree whose parent
353 : : links are given by PARENT. MARKS is the array used to mark the
354 : : vertices of the tree, and MARK is the number currently used as a mark. */
355 : :
356 : : static int
357 : 4899589 : tree_nca (int x, int y, int *parent, int *marks, int mark)
358 : : {
359 : 4899589 : if (x == -1 || x == y)
360 : : return y;
361 : :
362 : : /* We climb with X and Y up the tree, marking the visited nodes. When
363 : : we first arrive to a marked node, it is the common ancestor. */
364 : 1479053 : marks[x] = mark;
365 : 1479053 : marks[y] = mark;
366 : :
367 : 1556311 : while (1)
368 : : {
369 : 1517682 : x = parent[x];
370 : 1517682 : if (x == -1)
371 : : break;
372 : 157381 : if (marks[x] == mark)
373 : : return x;
374 : 107575 : marks[x] = mark;
375 : :
376 : 107575 : y = parent[y];
377 : 107575 : if (y == -1)
378 : : break;
379 : 99193 : if (marks[y] == mark)
380 : : return y;
381 : 38629 : marks[y] = mark;
382 : : }
383 : :
384 : : /* If we reached the root with one of the vertices, continue
385 : : with the other one till we reach the marked part of the
386 : : tree. */
387 : 1368683 : if (x == -1)
388 : : {
389 : 1443379 : for (y = parent[y]; marks[y] != mark; y = parent[y])
390 : 83078 : continue;
391 : :
392 : : return y;
393 : : }
394 : : else
395 : : {
396 : 8694 : for (x = parent[x]; marks[x] != mark; x = parent[x])
397 : 312 : continue;
398 : :
399 : : return x;
400 : : }
401 : : }
402 : :
403 : : /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
404 : : arrays), where the entry node is ENTRY. */
405 : :
406 : : void
407 : 816032 : graphds_domtree (struct graph *g, int entry,
408 : : int *parent, int *son, int *brother)
409 : : {
410 : 816032 : vec<int> postorder = vNULL;
411 : 816032 : int *marks = XCNEWVEC (int, g->n_vertices);
412 : 816032 : int mark = 1, i, v, idom;
413 : 816032 : bool changed = true;
414 : 816032 : struct graph_edge *e;
415 : :
416 : : /* We use a slight modification of the standard iterative algorithm, as
417 : : described in
418 : :
419 : : K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
420 : : Algorithm
421 : :
422 : : sort vertices in reverse postorder
423 : : foreach v
424 : : dom(v) = everything
425 : : dom(entry) = entry;
426 : :
427 : : while (anything changes)
428 : : foreach v
429 : : dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
430 : :
431 : : The sets dom(v) are represented by the parent links in the current version
432 : : of the dominance tree. */
433 : :
434 : 4156065 : for (i = 0; i < g->n_vertices; i++)
435 : : {
436 : 2524001 : parent[i] = -1;
437 : 2524001 : son[i] = -1;
438 : 2524001 : brother[i] = -1;
439 : : }
440 : 816032 : graphds_dfs (g, &entry, 1, &postorder, true, NULL);
441 : 1632064 : gcc_assert (postorder.length () == (unsigned) g->n_vertices);
442 : 816032 : gcc_assert (postorder[g->n_vertices - 1] == entry);
443 : :
444 : 2448208 : while (changed)
445 : : {
446 : 1632176 : changed = false;
447 : :
448 : 5048887 : for (i = g->n_vertices - 2; i >= 0; i--)
449 : : {
450 : 3416711 : v = postorder[i];
451 : 3416711 : idom = -1;
452 : 8403904 : for (e = g->vertices[v].pred; e; e = e->pred_next)
453 : : {
454 : 4987193 : if (e->src != entry
455 : 2022177 : && parent[e->src] == -1)
456 : 87604 : continue;
457 : :
458 : 4899589 : idom = tree_nca (idom, e->src, parent, marks, mark++);
459 : : }
460 : :
461 : 3416711 : if (idom != parent[v])
462 : : {
463 : 1708152 : parent[v] = idom;
464 : 1708152 : changed = true;
465 : : }
466 : : }
467 : : }
468 : :
469 : 816032 : free (marks);
470 : 816032 : postorder.release ();
471 : :
472 : 4156065 : for (i = 0; i < g->n_vertices; i++)
473 : 2524001 : if (parent[i] != -1)
474 : : {
475 : 1707969 : brother[i] = son[parent[i]];
476 : 1707969 : son[parent[i]] = i;
477 : : }
478 : 816032 : }
|
