1/* Graph representation and manipulation functions.
2 Copyright (C) 2007-2017 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 (f, "%d (%d)\t<-", i, g->vertices[i].component);
41 for (e = g->vertices[i].pred; e; e = e->pred_next)
42 fprintf (f, " %d", e->src);
43 fprintf (f, "\n");
44
45 fprintf (f, "\t->");
46 for (e = g->vertices[i].succ; e; e = e->succ_next)
47 fprintf (f, " %d", e->dest);
48 fprintf (f, "\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 (g->vertices, 0, 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 (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 (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 (stack);
274
275 return comp;
276}
277
278/* Determines the strongly connected components of G, using the algorithm of
279 Tarjan -- 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.
285
286 After running this function, v->component is the number of the strongly
287 connected component for each vertex of G. Returns the number of the
288 sccs of G. */
289
290int
291graphds_scc (struct graph *g, bitmap subgraph,
292 skip_edge_callback skip_edge_p)
293{
294 int *queue = XNEWVEC (int, g->n_vertices);
295 vec<int> postorder = vNULL;
296 int nq, i, comp;
297 unsigned v;
298 bitmap_iterator bi;
299
300 if (subgraph)
301 {
302 nq = 0;
303 EXECUTE_IF_SET_IN_BITMAP (subgraph, 0, v, bi)
304 {
305 queue[nq++] = v;
306 }
307 }
308 else
309 {
310 for (i = 0; i < g->n_vertices; i++)
311 queue[i] = i;
312 nq = g->n_vertices;
313 }
314
315 graphds_dfs (g, queue, nq, &postorder, false, subgraph, skip_edge_p);
316 gcc_assert (postorder.length () == (unsigned) nq);
317
318 for (i = 0; i < nq; i++)
319 queue[i] = postorder[nq - i - 1];
320 comp = graphds_dfs (g, queue, nq, NULL, true, subgraph, skip_edge_p);
321
322 free (queue);
323 postorder.release ();
324
325 return comp;
326}
327
328/* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
329
330void
331for_each_edge (struct graph *g, graphds_edge_callback callback, void *data)
332{
333 struct graph_edge *e;
334 int i;
335
336 for (i = 0; i < g->n_vertices; i++)
337 for (e = g->vertices[i].succ; e; e = e->succ_next)
338 callback (g, e, data);
339}
340
341/* Releases the memory occupied by G. */
342
343void
344free_graph (struct graph *g)
345{
346 obstack_free (&g->ob, NULL);
347 free (g);
348}
349
350/* Returns the nearest common ancestor of X and Y in tree whose parent
351 links are given by PARENT. MARKS is the array used to mark the
352 vertices of the tree, and MARK is the number currently used as a mark. */
353
354static int
355tree_nca (int x, int y, int *parent, int *marks, int mark)
356{
357 if (x == -1 || x == y)
358 return y;
359
360 /* We climb with X and Y up the tree, marking the visited nodes. When
361 we first arrive to a marked node, it is the common ancestor. */
362 marks[x] = mark;
363 marks[y] = mark;
364
365 while (1)
366 {
367 x = parent[x];
368 if (x == -1)
369 break;
370 if (marks[x] == mark)
371 return x;
372 marks[x] = mark;
373
374 y = parent[y];
375 if (y == -1)
376 break;
377 if (marks[y] == mark)
378 return y;
379 marks[y] = mark;
380 }
381
382 /* If we reached the root with one of the vertices, continue
383 with the other one till we reach the marked part of the
384 tree. */
385 if (x == -1)
386 {
387 for (y = parent[y]; marks[y] != mark; y = parent[y])
388 continue;
389
390 return y;
391 }
392 else
393 {
394 for (x = parent[x]; marks[x] != mark; x = parent[x])
395 continue;
396
397 return x;
398 }
399}
400
401/* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
402 arrays), where the entry node is ENTRY. */
403
404void
405graphds_domtree (struct graph *g, int entry,
406 int *parent, int *son, int *brother)
407{
408 vec<int> postorder = vNULL;
409 int *marks = XCNEWVEC (int, g->n_vertices);
410 int mark = 1, i, v, idom;
411 bool changed = true;
412 struct graph_edge *e;
413
414 /* We use a slight modification of the standard iterative algorithm, as
415 described in
416
417 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
418 Algorithm
419
420 sort vertices in reverse postorder
421 foreach v
422 dom(v) = everything
423 dom(entry) = entry;
424
425 while (anything changes)
426 foreach v
427 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
428
429 The sets dom(v) are represented by the parent links in the current version
430 of the dominance tree. */
431
432 for (i = 0; i < g->n_vertices; i++)
433 {
434 parent[i] = -1;
435 son[i] = -1;
436 brother[i] = -1;
437 }
438 graphds_dfs (g, &entry, 1, &postorder, true, NULL);
439 gcc_assert (postorder.length () == (unsigned) g->n_vertices);
440 gcc_assert (postorder[g->n_vertices - 1] == entry);
441
442 while (changed)
443 {
444 changed = false;
445
446 for (i = g->n_vertices - 2; i >= 0; i--)
447 {
448 v = postorder[i];
449 idom = -1;
450 for (e = g->vertices[v].pred; e; e = e->pred_next)
451 {
452 if (e->src != entry
453 && parent[e->src] == -1)
454 continue;
455
456 idom = tree_nca (idom, e->src, parent, marks, mark++);
457 }
458
459 if (idom != parent[v])
460 {
461 parent[v] = idom;
462 changed = true;
463 }
464 }
465 }
466
467 free (marks);
468 postorder.release ();
469
470 for (i = 0; i < g->n_vertices; i++)
471 if (parent[i] != -1)
472 {
473 brother[i] = son[parent[i]];
474 son[parent[i]] = i;
475 }
476}
477