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 : for (i = 0; i < g->n_vertices; i++)
35 : : {
36 : 0 : if (!g->vertices[i].pred
37 : 0 : && !g->vertices[i].succ)
38 : 0 : continue;
39 : :
40 : 0 : fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
41 : 0 : for (e = g->vertices[i].pred; e; e = e->pred_next)
42 : 0 : fprintf (f, " %d", e->src);
43 : 0 : fprintf (f, "\n");
44 : :
45 : 0 : fprintf (f, "\t->");
46 : 0 : for (e = g->vertices[i].succ; e; e = e->succ_next)
47 : 0 : fprintf (f, " %d", e->dest);
48 : 0 : fprintf (f, "\n");
49 : : }
50 : 0 : }
51 : :
52 : : /* Creates a new graph with N_VERTICES vertices. */
53 : :
54 : : struct graph *
55 : 56971423 : new_graph (int n_vertices)
56 : : {
57 : 56971423 : struct graph *g = XNEW (struct graph);
58 : :
59 : 56971423 : gcc_obstack_init (&g->ob);
60 : 56971423 : g->n_vertices = n_vertices;
61 : 56971423 : g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
62 : 56971423 : memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
63 : :
64 : 56971423 : return g;
65 : : }
66 : :
67 : : /* Adds an edge from F to T to graph G. The new edge is returned. */
68 : :
69 : : struct graph_edge *
70 : 765779402 : add_edge (struct graph *g, int f, int t)
71 : : {
72 : 765779402 : struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
73 : 765779402 : struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
74 : :
75 : 765779402 : e->src = f;
76 : 765779402 : e->dest = t;
77 : :
78 : 765779402 : e->pred_next = vt->pred;
79 : 765779402 : vt->pred = e;
80 : :
81 : 765779402 : e->succ_next = vf->succ;
82 : 765779402 : vf->succ = e;
83 : :
84 : 765779402 : e->data = NULL;
85 : 765779402 : return e;
86 : : }
87 : :
88 : : /* Moves all the edges incident with U to V. */
89 : :
90 : : void
91 : 1280126 : identify_vertices (struct graph *g, int v, int u)
92 : : {
93 : 1280126 : struct vertex *vv = &g->vertices[v];
94 : 1280126 : struct vertex *uu = &g->vertices[u];
95 : 1280126 : struct graph_edge *e, *next;
96 : :
97 : 2781193 : for (e = uu->succ; e; e = next)
98 : : {
99 : 1501067 : next = e->succ_next;
100 : :
101 : 1501067 : e->src = v;
102 : 1501067 : e->succ_next = vv->succ;
103 : 1501067 : vv->succ = e;
104 : : }
105 : 1280126 : uu->succ = NULL;
106 : :
107 : 3878240 : for (e = uu->pred; e; e = next)
108 : : {
109 : 2598114 : next = e->pred_next;
110 : :
111 : 2598114 : e->dest = v;
112 : 2598114 : e->pred_next = vv->pred;
113 : 2598114 : vv->pred = e;
114 : : }
115 : 1280126 : uu->pred = NULL;
116 : 1280126 : }
117 : :
118 : : /* Helper function for graphds_dfs. Returns the source vertex of E, in the
119 : : direction given by FORWARD. */
120 : :
121 : : static inline int
122 : 139633141 : dfs_edge_src (struct graph_edge *e, bool forward)
123 : : {
124 : 139633141 : return forward ? e->src : e->dest;
125 : : }
126 : :
127 : : /* Helper function for graphds_dfs. Returns the destination vertex of E, in
128 : : the direction given by FORWARD. */
129 : :
130 : : static inline int
131 : 1532620955 : dfs_edge_dest (struct graph_edge *e, bool forward)
132 : : {
133 : 1532620955 : return forward ? e->dest : e->src;
134 : : }
135 : :
136 : : /* Helper function for graphds_dfs. Returns the first edge after E (including
137 : : E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. If
138 : : SKIP_EDGE_P is not NULL, it points to a callback function. Edge E will be
139 : : skipped if callback function returns true. */
140 : :
141 : : static inline struct graph_edge *
142 : 3178310259 : foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph,
143 : : skip_edge_callback skip_edge_p)
144 : : {
145 : 3178310259 : int d;
146 : :
147 : 3178310259 : if (!e)
148 : : return e;
149 : :
150 : 1530588769 : if (!subgraph && (!skip_edge_p || !skip_edge_p (e)))
151 : 1528535196 : return e;
152 : :
153 : 3007552 : while (e)
154 : : {
155 : 2519869 : d = dfs_edge_dest (e, forward);
156 : : /* Return edge if it belongs to subgraph and shouldn't be skipped. */
157 : 2505968 : if ((!subgraph || bitmap_bit_p (subgraph, d))
158 : 4081587 : && (!skip_edge_p || !skip_edge_p (e)))
159 : 1565890 : return e;
160 : :
161 : 953979 : e = forward ? e->succ_next : e->pred_next;
162 : : }
163 : :
164 : : return e;
165 : : }
166 : :
167 : : /* Helper function for graphds_dfs. Select the first edge from V in G, in the
168 : : direction given by FORWARD, that belongs to SUBGRAPH. If SKIP_EDGE_P is not
169 : : NULL, it points to a callback function. Edge E will be skipped if callback
170 : : function returns true. */
171 : :
172 : : static inline struct graph_edge *
173 : 1648209173 : dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph,
174 : : skip_edge_callback skip_edge_p)
175 : : {
176 : 1648209173 : struct graph_edge *e;
177 : :
178 : 1648209173 : e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
179 : 1648209173 : return foll_in_subgraph (e, forward, subgraph, skip_edge_p);
180 : : }
181 : :
182 : : /* Helper function for graphds_dfs. Returns the next edge after E, in the
183 : : graph direction given by FORWARD, that belongs to SUBGRAPH. If SKIP_EDGE_P
184 : : is not NULL, it points to a callback function. Edge E will be skipped if
185 : : callback function returns true. */
186 : :
187 : : static inline struct graph_edge *
188 : 1530101086 : dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph,
189 : : skip_edge_callback skip_edge_p)
190 : : {
191 : 1530101086 : return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
192 : : forward, subgraph, skip_edge_p);
193 : : }
194 : :
195 : : /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
196 : : The vertices in postorder are stored into QT. If FORWARD is false,
197 : : backward dfs is run. If SUBGRAPH is not NULL, it specifies the
198 : : subgraph of G to run DFS on. Returns the number of the components
199 : : of the graph (number of the restarts of DFS). If SKIP_EDGE_P is not
200 : : NULL, it points to a callback function. Edge E will be skipped if
201 : : callback function returns true. */
202 : :
203 : : int
204 : 114491566 : graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
205 : : bool forward, bitmap subgraph,
206 : : skip_edge_callback skip_edge_p)
207 : : {
208 : 114491566 : int i, tick = 0, v, comp = 0, top;
209 : 114491566 : struct graph_edge *e;
210 : 114491566 : struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
211 : 114491566 : bitmap_iterator bi;
212 : 114491566 : unsigned av;
213 : :
214 : 114491566 : if (subgraph)
215 : : {
216 : 2773192 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
217 : : {
218 : 1878732 : g->vertices[av].component = -1;
219 : 1878732 : g->vertices[av].post = -1;
220 : : }
221 : : }
222 : : else
223 : : {
224 : 1766456735 : for (i = 0; i < g->n_vertices; i++)
225 : : {
226 : 1652859629 : g->vertices[i].component = -1;
227 : 1652859629 : g->vertices[i].post = -1;
228 : : }
229 : : }
230 : :
231 : 1757904967 : for (i = 0; i < nq; i++)
232 : : {
233 : 1643413401 : v = qs[i];
234 : 1643413401 : if (g->vertices[v].post != -1)
235 : 134837369 : continue;
236 : :
237 : 1508576032 : g->vertices[v].component = comp++;
238 : 1508576032 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
239 : 1508576032 : top = 0;
240 : :
241 : : while (1)
242 : : {
243 : 3178310259 : while (e)
244 : : {
245 : 3060202172 : if (g->vertices[dfs_edge_dest (e, forward)].component
246 : : == -1)
247 : : break;
248 : 2780935890 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
249 : : }
250 : :
251 : 1927475455 : if (!e)
252 : : {
253 : 1648209173 : if (qt)
254 : 829347880 : qt->safe_push (v);
255 : 1648209173 : g->vertices[v].post = tick++;
256 : :
257 : 1648209173 : if (!top)
258 : : break;
259 : :
260 : 139633141 : e = stack[--top];
261 : 139633141 : v = dfs_edge_src (e, forward);
262 : 139633141 : e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
263 : 139633141 : continue;
264 : : }
265 : :
266 : 139633141 : stack[top++] = e;
267 : 139633141 : v = dfs_edge_dest (e, forward);
268 : 139633141 : e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
269 : 139633141 : g->vertices[v].component = comp - 1;
270 : : }
271 : : }
272 : :
273 : 114491566 : free (stack);
274 : :
275 : 114491566 : return comp;
276 : : }
277 : :
278 : : /* Determines the strongly connected components of G, using the algorithm of
279 : : Kosaraju -- first determine the postorder dfs numbering in reversed graph,
280 : : then run the dfs on the original graph in the order given by decreasing
281 : : numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
282 : : specifies the subgraph of G whose strongly connected components we want
283 : : to determine. If SKIP_EDGE_P is not NULL, it points to a callback function.
284 : : Edge E will be skipped if callback function returns true. If SCC_GROUPING
285 : : is not null, the nodes will be added to it in the following order:
286 : :
287 : : - If SCC A is a direct or indirect predecessor of SCC B in the SCC dag,
288 : : A's nodes come before B's nodes.
289 : :
290 : : - All of an SCC's nodes are listed consecutively, although the order
291 : : of the nodes within an SCC is not really meaningful.
292 : :
293 : : After running this function, v->component is the number of the strongly
294 : : connected component for each vertex of G. Returns the number of the
295 : : sccs of G. */
296 : :
297 : : int
298 : 56691865 : graphds_scc (struct graph *g, bitmap subgraph,
299 : : skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
300 : : {
301 : 56691865 : int *queue = XNEWVEC (int, g->n_vertices);
302 : 56691865 : vec<int> postorder = vNULL;
303 : 56691865 : int nq, i, comp;
304 : 56691865 : unsigned v;
305 : 56691865 : bitmap_iterator bi;
306 : :
307 : 56691865 : if (subgraph)
308 : : {
309 : 447230 : nq = 0;
310 : 1386596 : EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
311 : : {
312 : 939366 : queue[nq++] = v;
313 : : }
314 : : }
315 : : else
316 : : {
317 : 876113431 : for (i = 0; i < g->n_vertices; i++)
318 : 819868796 : queue[i] = i;
319 : : nq = g->n_vertices;
320 : : }
321 : :
322 : 56691865 : graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
323 : 113383730 : gcc_assert (postorder.length () == (unsigned) nq);
324 : :
325 : 877500027 : for (i = 0; i < nq; i++)
326 : 820808162 : queue[i] = postorder[nq - i - 1];
327 : 56691865 : comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p);
328 : :
329 : 56691865 : free (queue);
330 : 56691865 : postorder.release ();
331 : :
332 : 56691865 : return comp;
333 : : }
334 : :
335 : : /* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
336 : :
337 : : void
338 : 10844 : for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
339 : : {
340 : 10844 : struct graph_edge *e;
341 : 10844 : int i;
342 : :
343 : 61166 : for (i = 0; i < g->n_vertices; i++)
344 : 88474 : for (e = g->vertices[i].succ; e; e = e->succ_next)
345 : 38152 : callback (g, e, data);
346 : 10844 : }
347 : :
348 : : /* Releases the memory occupied by G. */
349 : :
350 : : void
351 : 56971423 : free_graph (struct graph *g)
352 : : {
353 : 56971423 : obstack_free (&g->ob, NULL);
354 : 56971423 : free (g);
355 : 56971423 : }
356 : :
357 : : /* Returns the nearest common ancestor of X and Y in tree whose parent
358 : : links are given by PARENT. MARKS is the array used to mark the
359 : : vertices of the tree, and MARK is the number currently used as a mark. */
360 : :
361 : : static int
362 : 3627526 : tree_nca (int x, int y, int *parent, int *marks, int mark)
363 : : {
364 : 3627526 : if (x == -1 || x == y)
365 : : return y;
366 : :
367 : : /* We climb with X and Y up the tree, marking the visited nodes. When
368 : : we first arrive to a marked node, it is the common ancestor. */
369 : 1063997 : marks[x] = mark;
370 : 1063997 : marks[y] = mark;
371 : :
372 : 1139103 : while (1)
373 : : {
374 : 1101550 : x = parent[x];
375 : 1101550 : if (x == -1)
376 : : break;
377 : 150768 : if (marks[x] == mark)
378 : 47315 : return x;
379 : 103453 : marks[x] = mark;
380 : :
381 : 103453 : y = parent[y];
382 : 103453 : if (y == -1)
383 : : break;
384 : 95940 : if (marks[y] == mark)
385 : 58387 : return y;
386 : 37553 : marks[y] = mark;
387 : : }
388 : :
389 : : /* If we reached the root with one of the vertices, continue
390 : : with the other one till we reach the marked part of the
391 : : tree. */
392 : 958295 : if (x == -1)
393 : : {
394 : 1030482 : for (y = parent[y]; marks[y] != mark; y = parent[y])
395 : 79700 : continue;
396 : :
397 : 950782 : return y;
398 : : }
399 : : else
400 : : {
401 : 7847 : for (x = parent[x]; marks[x] != mark; x = parent[x])
402 : 334 : continue;
403 : :
404 : 7513 : return x;
405 : : }
406 : : }
407 : :
408 : : /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
409 : : arrays), where the entry node is ENTRY. */
410 : :
411 : : void
412 : 603484 : graphds_domtree (struct graph *g, int entry,
413 : : int *parent, int *son, int *brother)
414 : : {
415 : 603484 : vec<int> postorder = vNULL;
416 : 603484 : int *marks = XCNEWVEC (int, g->n_vertices);
417 : 603484 : int mark = 1, i, v, idom;
418 : 603484 : bool changed = true;
419 : 603484 : struct graph_edge *e;
420 : :
421 : : /* We use a slight modification of the standard iterative algorithm, as
422 : : described in
423 : :
424 : : K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
425 : : Algorithm
426 : :
427 : : sort vertices in reverse postorder
428 : : foreach v
429 : : dom(v) = everything
430 : : dom(entry) = entry;
431 : :
432 : : while (anything changes)
433 : : foreach v
434 : : dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
435 : :
436 : : The sets dom(v) are represented by the parent links in the current version
437 : : of the dominance tree. */
438 : :
439 : 3090578 : for (i = 0; i < g->n_vertices; i++)
440 : : {
441 : 1883610 : parent[i] = -1;
442 : 1883610 : son[i] = -1;
443 : 1883610 : brother[i] = -1;
444 : : }
445 : 603484 : graphds_dfs (g, &entry, 1, &postorder, true, NULL);
446 : 1206968 : gcc_assert (postorder.length () == (unsigned) g->n_vertices);
447 : 603484 : gcc_assert (postorder[g->n_vertices - 1] == entry);
448 : :
449 : 1810529 : while (changed)
450 : : {
451 : 1207045 : changed = false;
452 : :
453 : 3767713 : for (i = g->n_vertices - 2; i >= 0; i--)
454 : : {
455 : 2560668 : v = postorder[i];
456 : 2560668 : idom = -1;
457 : 6271983 : for (e = g->vertices[v].pred; e; e = e->pred_next)
458 : : {
459 : 3711315 : if (e->src != entry
460 : 1583349 : && parent[e->src] == -1)
461 : 83789 : continue;
462 : :
463 : 3627526 : idom = tree_nca (idom, e->src, parent, marks, mark++);
464 : : }
465 : :
466 : 2560668 : if (idom != parent[v])
467 : : {
468 : 1280213 : parent[v] = idom;
469 : 1280213 : changed = true;
470 : : }
471 : : }
472 : : }
473 : :
474 : 603484 : free (marks);
475 : 603484 : postorder.release ();
476 : :
477 : 3090578 : for (i = 0; i < g->n_vertices; i++)
478 : 1883610 : if (parent[i] != -1)
479 : : {
480 : 1280126 : brother[i] = son[parent[i]];
481 : 1280126 : son[parent[i]] = i;
482 : : }
483 : 603484 : }
|
