1 /* Graph representation and manipulation functions.
2 Copyright (C) 2007-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
26 /* Dumps graph G into F. */
29 dump_graph (FILE *f
, struct graph
*g
)
34 for (i
= 0; i
< g
->n_vertices
; i
++)
36 if (!g
->vertices
[i
].pred
37 && !g
->vertices
[i
].succ
)
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
);
46 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
47 fprintf (f
, " %d", e
->dest
);
52 /* Creates a new graph with N_VERTICES vertices. */
55 new_graph (int n_vertices
)
57 struct graph
*g
= XNEW (struct graph
);
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
);
67 /* Adds an edge from F to T to graph G. The new edge is returned. */
70 add_edge (struct graph
*g
, int f
, int t
)
72 struct graph_edge
*e
= XOBNEW (&g
->ob
, struct graph_edge
);
73 struct vertex
*vf
= &g
->vertices
[f
], *vt
= &g
->vertices
[t
];
78 e
->pred_next
= vt
->pred
;
81 e
->succ_next
= vf
->succ
;
88 /* Moves all the edges incident with U to V. */
91 identify_vertices (struct graph
*g
, int v
, int u
)
93 struct vertex
*vv
= &g
->vertices
[v
];
94 struct vertex
*uu
= &g
->vertices
[u
];
95 struct graph_edge
*e
, *next
;
97 for (e
= uu
->succ
; e
; e
= next
)
102 e
->succ_next
= vv
->succ
;
107 for (e
= uu
->pred
; e
; e
= next
)
112 e
->pred_next
= vv
->pred
;
118 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
119 direction given by FORWARD. */
122 dfs_edge_src (struct graph_edge
*e
, bool forward
)
124 return forward
? e
->src
: e
->dest
;
127 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
128 the direction given by FORWARD. */
131 dfs_edge_dest (struct graph_edge
*e
, bool forward
)
133 return forward
? e
->dest
: e
->src
;
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. */
141 static inline struct graph_edge
*
142 foll_in_subgraph (struct graph_edge
*e
, bool forward
, bitmap subgraph
,
143 skip_edge_callback skip_edge_p
)
150 if (!subgraph
&& (!skip_edge_p
|| !skip_edge_p (e
)))
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
)))
161 e
= forward
? e
->succ_next
: e
->pred_next
;
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. */
172 static inline struct graph_edge
*
173 dfs_fst_edge (struct graph
*g
, int v
, bool forward
, bitmap subgraph
,
174 skip_edge_callback skip_edge_p
)
176 struct graph_edge
*e
;
178 e
= (forward
? g
->vertices
[v
].succ
: g
->vertices
[v
].pred
);
179 return foll_in_subgraph (e
, forward
, subgraph
, skip_edge_p
);
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. */
187 static inline struct graph_edge
*
188 dfs_next_edge (struct graph_edge
*e
, bool forward
, bitmap subgraph
,
189 skip_edge_callback skip_edge_p
)
191 return foll_in_subgraph (forward
? e
->succ_next
: e
->pred_next
,
192 forward
, subgraph
, skip_edge_p
);
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. */
204 graphds_dfs (struct graph
*g
, int *qs
, int nq
, vec
<int> *qt
,
205 bool forward
, bitmap subgraph
,
206 skip_edge_callback skip_edge_p
)
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
);
216 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, av
, bi
)
218 g
->vertices
[av
].component
= -1;
219 g
->vertices
[av
].post
= -1;
224 for (i
= 0; i
< g
->n_vertices
; i
++)
226 g
->vertices
[i
].component
= -1;
227 g
->vertices
[i
].post
= -1;
231 for (i
= 0; i
< nq
; i
++)
234 if (g
->vertices
[v
].post
!= -1)
237 g
->vertices
[v
].component
= comp
++;
238 e
= dfs_fst_edge (g
, v
, forward
, subgraph
, skip_edge_p
);
245 if (g
->vertices
[dfs_edge_dest (e
, forward
)].component
248 e
= dfs_next_edge (e
, forward
, subgraph
, skip_edge_p
);
255 g
->vertices
[v
].post
= tick
++;
261 v
= dfs_edge_src (e
, forward
);
262 e
= dfs_next_edge (e
, forward
, subgraph
, skip_edge_p
);
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;
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.
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
291 graphds_scc (struct graph
*g
, bitmap subgraph
,
292 skip_edge_callback skip_edge_p
)
294 int *queue
= XNEWVEC (int, g
->n_vertices
);
295 vec
<int> postorder
= vNULL
;
303 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, v
, bi
)
310 for (i
= 0; i
< g
->n_vertices
; i
++)
315 graphds_dfs (g
, queue
, nq
, &postorder
, false, subgraph
, skip_edge_p
);
316 gcc_assert (postorder
.length () == (unsigned) nq
);
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
);
323 postorder
.release ();
328 /* Runs CALLBACK for all edges in G. DATA is private data for CALLBACK. */
331 for_each_edge (struct graph
*g
, graphds_edge_callback callback
, void *data
)
333 struct graph_edge
*e
;
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
);
341 /* Releases the memory occupied by G. */
344 free_graph (struct graph
*g
)
346 obstack_free (&g
->ob
, NULL
);
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. */
355 tree_nca (int x
, int y
, int *parent
, int *marks
, int mark
)
357 if (x
== -1 || x
== y
)
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. */
370 if (marks
[x
] == mark
)
377 if (marks
[y
] == mark
)
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
387 for (y
= parent
[y
]; marks
[y
] != mark
; y
= parent
[y
])
394 for (x
= parent
[x
]; marks
[x
] != mark
; x
= parent
[x
])
401 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
402 arrays), where the entry node is ENTRY. */
405 graphds_domtree (struct graph
*g
, int entry
,
406 int *parent
, int *son
, int *brother
)
408 vec
<int> postorder
= vNULL
;
409 int *marks
= XCNEWVEC (int, g
->n_vertices
);
410 int mark
= 1, i
, v
, idom
;
412 struct graph_edge
*e
;
414 /* We use a slight modification of the standard iterative algorithm, as
417 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
420 sort vertices in reverse postorder
425 while (anything changes)
427 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
429 The sets dom(v) are represented by the parent links in the current version
430 of the dominance tree. */
432 for (i
= 0; i
< g
->n_vertices
; i
++)
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
);
446 for (i
= g
->n_vertices
- 2; i
>= 0; i
--)
450 for (e
= g
->vertices
[v
].pred
; e
; e
= e
->pred_next
)
453 && parent
[e
->src
] == -1)
456 idom
= tree_nca (idom
, e
->src
, parent
, marks
, mark
++);
459 if (idom
!= parent
[v
])
468 postorder
.release ();
470 for (i
= 0; i
< g
->n_vertices
; i
++)
473 brother
[i
] = son
[parent
[i
]];