1/* Graph representation and manipulation functions.
2 Copyright (C) 2007-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
28void
29dump_graph (FILE *f, struct graph *g)
30{
31 int i;
32 struct graph_edge *e;
33
34 for (i = 0; i < g->n_vertices; i++)
35 {
36 if (!g->vertices[i].pred
37 && !g->vertices[i].succ)
38 continue;
39
40 fprintf (stream: f, format: "%d (%d)\t<-", i, g->vertices[i].component);
41 for (e = g->vertices[i].pred; e; e = e->pred_next)
42 fprintf (stream: f, format: " %d", e->src);
43 fprintf (stream: f, format: "\n");
44
45 fprintf (stream: f, format: "\t->");
46 for (e = g->vertices[i].succ; e; e = e->succ_next)
47 fprintf (stream: f, format: " %d", e->dest);
48 fprintf (stream: f, format: "\n");
49 }
50}
51
52/* Creates a new graph with N_VERTICES vertices. */
53
54struct graph *
55new_graph (int n_vertices)
56{
57 struct graph *g = XNEW (struct graph);
58
59 gcc_obstack_init (&g->ob);
60 g->n_vertices = n_vertices;
61 g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
62 memset (s: g->vertices, c: 0, n: sizeof (struct vertex) * n_vertices);
63
64 return g;
65}
66
67/* Adds an edge from F to T to graph G. The new edge is returned. */
68
69struct graph_edge *
70add_edge (struct graph *g, int f, int t)
71{
72 struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
73 struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
74
75 e->src = f;
76 e->dest = t;
77
78 e->pred_next = vt->pred;
79 vt->pred = e;
80
81 e->succ_next = vf->succ;
82 vf->succ = e;
83
84 e->data = NULL;
85 return e;
86}
87
88/* Moves all the edges incident with U to V. */
89
90void
91identify_vertices (struct graph *g, int v, int u)
92{
93 struct vertex *vv = &g->vertices[v];
94 struct vertex *uu = &g->vertices[u];
95 struct graph_edge *e, *next;
96
97 for (e = uu->succ; e; e = next)
98 {
99 next = e->succ_next;
100
101 e->src = v;
102 e->succ_next = vv->succ;
103 vv->succ = e;
104 }
105 uu->succ = NULL;
106
107 for (e = uu->pred; e; e = next)
108 {
109 next = e->pred_next;
110
111 e->dest = v;
112 e->pred_next = vv->pred;
113 vv->pred = e;
114 }
115 uu->pred = NULL;
116}
117
118/* Helper function for graphds_dfs. Returns the source vertex of E, in the
119 direction given by FORWARD. */
120
121static inline int
122dfs_edge_src (struct graph_edge *e, bool forward)
123{
124 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
130static inline int
131dfs_edge_dest (struct graph_edge *e, bool forward)
132{
133 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
141static inline struct graph_edge *
142foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph,
143 skip_edge_callback skip_edge_p)
144{
145 int d;
146
147 if (!e)
148 return e;
149
150 if (!subgraph && (!skip_edge_p || !skip_edge_p (e)))
151 return e;
152
153 while (e)
154 {
155 d = dfs_edge_dest (e, forward);
156 /* Return edge if it belongs to subgraph and shouldn't be skipped. */
157 if ((!subgraph || bitmap_bit_p (subgraph, d))
158 && (!skip_edge_p || !skip_edge_p (e)))
159 return e;
160
161 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
172static inline struct graph_edge *
173dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph,
174 skip_edge_callback skip_edge_p)
175{
176 struct graph_edge *e;
177
178 e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
179 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
187static inline struct graph_edge *
188dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph,
189 skip_edge_callback skip_edge_p)
190{
191 return foll_in_subgraph (e: 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
203int
204graphds_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 int i, tick = 0, v, comp = 0, top;
209 struct graph_edge *e;
210 struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
211 bitmap_iterator bi;
212 unsigned av;
213
214 if (subgraph)
215 {
216 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, av, bi)
217 {
218 g->vertices[av].component = -1;
219 g->vertices[av].post = -1;
220 }
221 }
222 else
223 {
224 for (i = 0; i < g->n_vertices; i++)
225 {
226 g->vertices[i].component = -1;
227 g->vertices[i].post = -1;
228 }
229 }
230
231 for (i = 0; i < nq; i++)
232 {
233 v = qs[i];
234 if (g->vertices[v].post != -1)
235 continue;
236
237 g->vertices[v].component = comp++;
238 e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
239 top = 0;
240
241 while (1)
242 {
243 while (e)
244 {
245 if (g->vertices[dfs_edge_dest (e, forward)].component
246 == -1)
247 break;
248 e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
249 }
250
251 if (!e)
252 {
253 if (qt)
254 qt->safe_push (obj: v);
255 g->vertices[v].post = tick++;
256
257 if (!top)
258 break;
259
260 e = stack[--top];
261 v = dfs_edge_src (e, forward);
262 e = dfs_next_edge (e, forward, subgraph, skip_edge_p);
263 continue;
264 }
265
266 stack[top++] = e;
267 v = dfs_edge_dest (e, forward);
268 e = dfs_fst_edge (g, v, forward, subgraph, skip_edge_p);
269 g->vertices[v].component = comp - 1;
270 }
271 }
272
273 free (ptr: stack);
274
275 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
297int
298graphds_scc (struct graph *g, bitmap subgraph,
299 skip_edge_callback skip_edge_p, vec<int> *scc_grouping)
300{
301 int *queue = XNEWVEC (int, g->n_vertices);
302 vec<int> postorder = vNULL;
303 int nq, i, comp;
304 unsigned v;
305 bitmap_iterator bi;
306
307 if (subgraph)
308 {
309 nq = 0;
310 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
311 {
312 queue[nq++] = v;
313 }
314 }
315 else
316 {
317 for (i = 0; i < g->n_vertices; i++)
318 queue[i] = i;
319 nq = g->n_vertices;
320 }
321
322 graphds_dfs (g, qs: queue, nq, qt: &postorder, forward: false, subgraph, skip_edge_p);
323 gcc_assert (postorder.length () == (unsigned) nq);
324
325 for (i = 0; i < nq; i++)
326 queue[i] = postorder[nq - i - 1];
327 comp = graphds_dfs (g, qs: queue, nq, qt: scc_grouping, forward: true, subgraph, skip_edge_p);
328
329 free (ptr: queue);
330 postorder.release ();
331
332 return comp;
333}
334
335/* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
336
337void
338for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
339{
340 struct graph_edge *e;
341 int i;
342
343 for (i = 0; i < g->n_vertices; i++)
344 for (e = g->vertices[i].succ; e; e = e->succ_next)
345 callback (g, e, data);
346}
347
348/* Releases the memory occupied by G. */
349
350void
351free_graph (struct graph *g)
352{
353 obstack_free (&g->ob, NULL);
354 free (ptr: g);
355}
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
361static int
362tree_nca (int x, int y, int *parent, int *marks, int mark)
363{
364 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 marks[x] = mark;
370 marks[y] = mark;
371
372 while (1)
373 {
374 x = parent[x];
375 if (x == -1)
376 break;
377 if (marks[x] == mark)
378 return x;
379 marks[x] = mark;
380
381 y = parent[y];
382 if (y == -1)
383 break;
384 if (marks[y] == mark)
385 return y;
386 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 if (x == -1)
393 {
394 for (y = parent[y]; marks[y] != mark; y = parent[y])
395 continue;
396
397 return y;
398 }
399 else
400 {
401 for (x = parent[x]; marks[x] != mark; x = parent[x])
402 continue;
403
404 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
411void
412graphds_domtree (struct graph *g, int entry,
413 int *parent, int *son, int *brother)
414{
415 vec<int> postorder = vNULL;
416 int *marks = XCNEWVEC (int, g->n_vertices);
417 int mark = 1, i, v, idom;
418 bool changed = true;
419 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 for (i = 0; i < g->n_vertices; i++)
440 {
441 parent[i] = -1;
442 son[i] = -1;
443 brother[i] = -1;
444 }
445 graphds_dfs (g, qs: &entry, nq: 1, qt: &postorder, forward: true, NULL);
446 gcc_assert (postorder.length () == (unsigned) g->n_vertices);
447 gcc_assert (postorder[g->n_vertices - 1] == entry);
448
449 while (changed)
450 {
451 changed = false;
452
453 for (i = g->n_vertices - 2; i >= 0; i--)
454 {
455 v = postorder[i];
456 idom = -1;
457 for (e = g->vertices[v].pred; e; e = e->pred_next)
458 {
459 if (e->src != entry
460 && parent[e->src] == -1)
461 continue;
462
463 idom = tree_nca (x: idom, y: e->src, parent, marks, mark: mark++);
464 }
465
466 if (idom != parent[v])
467 {
468 parent[v] = idom;
469 changed = true;
470 }
471 }
472 }
473
474 free (ptr: marks);
475 postorder.release ();
476
477 for (i = 0; i < g->n_vertices; i++)
478 if (parent[i] != -1)
479 {
480 brother[i] = son[parent[i]];
481 son[parent[i]] = i;
482 }
483}
484

source code of gcc/graphds.cc