Line data Source code
1 : /* Graph representation and manipulation functions.
2 : Copyright (C) 2007-2026 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 63206125 : new_graph (int n_vertices)
51 : {
52 63206125 : struct graph *g = XNEW (struct graph);
53 :
54 63206125 : gcc_obstack_init (&g->ob);
55 63206125 : g->n_vertices = n_vertices;
56 63206125 : g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
57 63206125 : memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
58 :
59 63206125 : 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 893023195 : add_edge (struct graph *g, int f, int t)
66 : {
67 893023195 : struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
68 893023195 : struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
69 :
70 893023195 : e->src = f;
71 893023195 : e->dest = t;
72 :
73 893023195 : e->pred_next = vt->pred;
74 893023195 : vt->pred = e;
75 :
76 893023195 : e->succ_next = vf->succ;
77 893023195 : vf->succ = e;
78 :
79 893023195 : e->data = NULL;
80 893023195 : return e;
81 : }
82 :
83 : /* Moves all the edges incident with U to V. */
84 :
85 : void
86 1269140 : identify_vertices (struct graph *g, int v, int u)
87 : {
88 1269140 : struct vertex *vv = &g->vertices[v];
89 1269140 : struct vertex *uu = &g->vertices[u];
90 1269140 : struct graph_edge *e, *next;
91 :
92 3333294 : for (e = uu->succ; e; e = next)
93 : {
94 2064154 : next = e->succ_next;
95 :
96 2064154 : e->src = v;
97 2064154 : e->succ_next = vv->succ;
98 2064154 : vv->succ = e;
99 : }
100 1269140 : uu->succ = NULL;
101 :
102 4331307 : for (e = uu->pred; e; e = next)
103 : {
104 3062167 : next = e->pred_next;
105 :
106 3062167 : e->dest = v;
107 3062167 : e->pred_next = vv->pred;
108 3062167 : vv->pred = e;
109 : }
110 1269140 : uu->pred = NULL;
111 1269140 : }
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 159908255 : dfs_edge_src (struct graph_edge *e, bool forward)
118 : {
119 159908255 : 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 1783934343 : dfs_edge_dest (struct graph_edge *e, bool forward)
127 : {
128 1783934343 : 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 3705248997 : foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph,
138 : skip_edge_callback skip_edge_p)
139 : {
140 3705248997 : int d;
141 :
142 3705248997 : if (!e)
143 : return e;
144 :
145 1780853265 : if (!subgraph && (!skip_edge_p || !skip_edge_p (e)))
146 1777754093 : return e;
147 :
148 4395294 : while (e)
149 : {
150 3738186 : d = dfs_edge_dest (e, forward);
151 : /* Return edge if it belongs to subgraph and shouldn't be skipped. */
152 3656454 : if ((!subgraph || bitmap_bit_p (subgraph, d))
153 6174300 : && (!skip_edge_p || !skip_edge_p (e)))
154 2442064 : return e;
155 :
156 1296122 : 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 1925052840 : dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph,
169 : skip_edge_callback skip_edge_p)
170 : {
171 1925052840 : struct graph_edge *e;
172 :
173 1925052840 : e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
174 1925052840 : 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 1780196157 : dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph,
184 : skip_edge_callback skip_edge_p)
185 : {
186 1780196157 : 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 126243661 : 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 126243661 : int i, tick = 0, v, comp = 0, top;
204 126243661 : struct graph_edge *e;
205 126243661 : struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
206 126243661 : bitmap_iterator bi;
207 126243661 : unsigned av;
208 :
209 126243661 : if (subgraph)
210 : {
211 3390144 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
212 : {
213 2296452 : g->vertices[av].component = -1;
214 2296452 : g->vertices[av].post = -1;
215 : }
216 : }
217 : else
218 : {
219 2055609476 : for (i = 0; i < g->n_vertices; i++)
220 : {
221 1930459507 : g->vertices[i].component = -1;
222 1930459507 : g->vertices[i].post = -1;
223 : }
224 : }
225 :
226 2044779429 : for (i = 0; i < nq; i++)
227 : {
228 1918535768 : v = qs[i];
229 1918535768 : if (g->vertices[v].post != -1)
230 153391183 : continue;
231 :
232 1765144585 : g->vertices[v].component = comp++;
233 1765144585 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
234 1765144585 : top = 0;
235 :
236 : while (1)
237 : {
238 3705248997 : while (e)
239 : {
240 3560392314 : if (g->vertices[dfs_edge_dest (e, forward)].component
241 : == -1)
242 : break;
243 3240575804 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
244 : }
245 :
246 2244869350 : if (!e)
247 : {
248 1925052840 : if (qt)
249 971873960 : qt->safe_push (v);
250 1925052840 : g->vertices[v].post = tick++;
251 :
252 1925052840 : if (!top)
253 : break;
254 :
255 159908255 : e = stack[--top];
256 159908255 : v = dfs_edge_src (e, forward);
257 159908255 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
258 159908255 : continue;
259 : }
260 :
261 159908255 : stack[top++] = e;
262 159908255 : v = dfs_edge_dest (e, forward);
263 159908255 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
264 159908255 : g->vertices[v].component = comp - 1;
265 : }
266 : }
267 :
268 126243661 : free (stack);
269 :
270 126243661 : 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 62393200 : graphds_scc (struct graph *g, bitmap subgraph,
294 : skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
295 : {
296 62393200 : int *queue = XNEWVEC (int, g->n_vertices);
297 62393200 : vec<int> postorder = vNULL;
298 62393200 : int nq, i, comp;
299 62393200 : unsigned v;
300 62393200 : bitmap_iterator bi;
301 :
302 62393200 : if (subgraph)
303 : {
304 546846 : nq = 0;
305 1695072 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
306 : {
307 1148226 : queue[nq++] = v;
308 : }
309 : }
310 : else
311 : {
312 1018417773 : for (i = 0; i < g->n_vertices; i++)
313 956571419 : queue[i] = i;
314 : nq = g->n_vertices;
315 : }
316 :
317 62393200 : graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
318 124786400 : gcc_assert (postorder.length () == (unsigned) nq);
319 :
320 1020112845 : for (i = 0; i < nq; i++)
321 957719645 : queue[i] = postorder[nq - i - 1];
322 62393200 : comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p);
323 :
324 62393200 : free (queue);
325 62393200 : postorder.release ();
326 :
327 62393200 : return comp;
328 : }
329 :
330 : /* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
331 :
332 : void
333 12412 : for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
334 : {
335 12412 : struct graph_edge *e;
336 12412 : int i;
337 :
338 69672 : for (i = 0; i < g->n_vertices; i++)
339 470853 : for (e = g->vertices[i].succ; e; e = e->succ_next)
340 413593 : callback (g, e, data);
341 12412 : }
342 :
343 : /* Releases the memory occupied by G. */
344 :
345 : void
346 63205837 : free_graph (struct graph *g)
347 : {
348 63205837 : obstack_free (&g->ob, NULL);
349 63205837 : free (g);
350 63205837 : }
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 3777333 : tree_nca (int x, int y, int *parent, int *marks, int mark)
358 : {
359 3777333 : 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 1233386 : marks[x] = mark;
365 1233386 : marks[y] = mark;
366 :
367 1342598 : while (1)
368 : {
369 1287992 : x = parent[x];
370 1287992 : if (x == -1)
371 : break;
372 195696 : if (marks[x] == mark)
373 : return x;
374 137962 : marks[x] = mark;
375 :
376 137962 : y = parent[y];
377 137962 : if (y == -1)
378 : break;
379 131497 : if (marks[y] == mark)
380 : return y;
381 54606 : 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 1098761 : if (x == -1)
388 : {
389 1114940 : for (y = parent[y]; marks[y] != mark; y = parent[y])
390 22644 : continue;
391 :
392 : return y;
393 : }
394 : else
395 : {
396 6898 : for (x = parent[x]; marks[x] != mark; x = parent[x])
397 433 : 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 586589 : graphds_domtree (struct graph *g, int entry,
408 : int *parent, int *son, int *brother)
409 : {
410 586589 : vec<int> postorder = vNULL;
411 586589 : int *marks = XCNEWVEC (int, g->n_vertices);
412 586589 : int mark = 1, i, v, idom;
413 586589 : bool changed = true;
414 586589 : 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 3028907 : for (i = 0; i < g->n_vertices; i++)
435 : {
436 1855729 : parent[i] = -1;
437 1855729 : son[i] = -1;
438 1855729 : brother[i] = -1;
439 : }
440 586589 : graphds_dfs (g, &entry, 1, &postorder, true, NULL);
441 1173178 : gcc_assert (postorder.length () == (unsigned) g->n_vertices);
442 586589 : gcc_assert (postorder[g->n_vertices - 1] == entry);
443 :
444 1759935 : while (changed)
445 : {
446 1173346 : changed = false;
447 :
448 3712764 : for (i = g->n_vertices - 2; i >= 0; i--)
449 : {
450 2539418 : v = postorder[i];
451 2539418 : idom = -1;
452 6340073 : for (e = g->vertices[v].pred; e; e = e->pred_next)
453 : {
454 3800655 : if (e->src != entry
455 1503256 : && parent[e->src] == -1)
456 23322 : continue;
457 :
458 3777333 : idom = tree_nca (idom, e->src, parent, marks, mark++);
459 : }
460 :
461 2539418 : if (idom != parent[v])
462 : {
463 1269408 : parent[v] = idom;
464 1269408 : changed = true;
465 : }
466 : }
467 : }
468 :
469 586589 : free (marks);
470 586589 : postorder.release ();
471 :
472 3028907 : for (i = 0; i < g->n_vertices; i++)
473 1855729 : if (parent[i] != -1)
474 : {
475 1269140 : brother[i] = son[parent[i]];
476 1269140 : son[parent[i]] = i;
477 : }
478 586589 : }
|
