1 /* Graph representation and manipulation functions.
2 Copyright (C) 2007-2015 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
;
87 /* Moves all the edges incident with U to V. */
90 identify_vertices (struct graph
*g
, int v
, int u
)
92 struct vertex
*vv
= &g
->vertices
[v
];
93 struct vertex
*uu
= &g
->vertices
[u
];
94 struct graph_edge
*e
, *next
;
96 for (e
= uu
->succ
; e
; e
= next
)
101 e
->succ_next
= vv
->succ
;
106 for (e
= uu
->pred
; e
; e
= next
)
111 e
->pred_next
= vv
->pred
;
117 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
118 direction given by FORWARD. */
121 dfs_edge_src (struct graph_edge
*e
, bool forward
)
123 return forward
? e
->src
: e
->dest
;
126 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
127 the direction given by FORWARD. */
130 dfs_edge_dest (struct graph_edge
*e
, bool forward
)
132 return forward
? e
->dest
: e
->src
;
135 /* Helper function for graphds_dfs. Returns the first edge after E (including
136 E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
138 static inline struct graph_edge
*
139 foll_in_subgraph (struct graph_edge
*e
, bool forward
, bitmap subgraph
)
148 d
= dfs_edge_dest (e
, forward
);
149 if (bitmap_bit_p (subgraph
, d
))
152 e
= forward
? e
->succ_next
: e
->pred_next
;
158 /* Helper function for graphds_dfs. Select the first edge from V in G, in the
159 direction given by FORWARD, that belongs to SUBGRAPH. */
161 static inline struct graph_edge
*
162 dfs_fst_edge (struct graph
*g
, int v
, bool forward
, bitmap subgraph
)
164 struct graph_edge
*e
;
166 e
= (forward
? g
->vertices
[v
].succ
: g
->vertices
[v
].pred
);
167 return foll_in_subgraph (e
, forward
, subgraph
);
170 /* Helper function for graphds_dfs. Returns the next edge after E, in the
171 graph direction given by FORWARD, that belongs to SUBGRAPH. */
173 static inline struct graph_edge
*
174 dfs_next_edge (struct graph_edge
*e
, bool forward
, bitmap subgraph
)
176 return foll_in_subgraph (forward
? e
->succ_next
: e
->pred_next
,
180 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
181 The vertices in postorder are stored into QT. If FORWARD is false,
182 backward dfs is run. If SUBGRAPH is not NULL, it specifies the
183 subgraph of G to run DFS on. Returns the number of the components
184 of the graph (number of the restarts of DFS). */
187 graphds_dfs (struct graph
*g
, int *qs
, int nq
, vec
<int> *qt
,
188 bool forward
, bitmap subgraph
)
190 int i
, tick
= 0, v
, comp
= 0, top
;
191 struct graph_edge
*e
;
192 struct graph_edge
**stack
= XNEWVEC (struct graph_edge
*, g
->n_vertices
);
198 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, av
, bi
)
200 g
->vertices
[av
].component
= -1;
201 g
->vertices
[av
].post
= -1;
206 for (i
= 0; i
< g
->n_vertices
; i
++)
208 g
->vertices
[i
].component
= -1;
209 g
->vertices
[i
].post
= -1;
213 for (i
= 0; i
< nq
; i
++)
216 if (g
->vertices
[v
].post
!= -1)
219 g
->vertices
[v
].component
= comp
++;
220 e
= dfs_fst_edge (g
, v
, forward
, subgraph
);
227 if (g
->vertices
[dfs_edge_dest (e
, forward
)].component
230 e
= dfs_next_edge (e
, forward
, subgraph
);
237 g
->vertices
[v
].post
= tick
++;
243 v
= dfs_edge_src (e
, forward
);
244 e
= dfs_next_edge (e
, forward
, subgraph
);
249 v
= dfs_edge_dest (e
, forward
);
250 e
= dfs_fst_edge (g
, v
, forward
, subgraph
);
251 g
->vertices
[v
].component
= comp
- 1;
260 /* Determines the strongly connected components of G, using the algorithm of
261 Tarjan -- first determine the postorder dfs numbering in reversed graph,
262 then run the dfs on the original graph in the order given by decreasing
263 numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
264 specifies the subgraph of G whose strongly connected components we want
267 After running this function, v->component is the number of the strongly
268 connected component for each vertex of G. Returns the number of the
272 graphds_scc (struct graph
*g
, bitmap subgraph
)
274 int *queue
= XNEWVEC (int, g
->n_vertices
);
275 vec
<int> postorder
= vNULL
;
283 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, v
, bi
)
290 for (i
= 0; i
< g
->n_vertices
; i
++)
295 graphds_dfs (g
, queue
, nq
, &postorder
, false, subgraph
);
296 gcc_assert (postorder
.length () == (unsigned) nq
);
298 for (i
= 0; i
< nq
; i
++)
299 queue
[i
] = postorder
[nq
- i
- 1];
300 comp
= graphds_dfs (g
, queue
, nq
, NULL
, true, subgraph
);
303 postorder
.release ();
308 /* Runs CALLBACK for all edges in G. */
311 for_each_edge (struct graph
*g
, graphds_edge_callback callback
)
313 struct graph_edge
*e
;
316 for (i
= 0; i
< g
->n_vertices
; i
++)
317 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
321 /* Releases the memory occupied by G. */
324 free_graph (struct graph
*g
)
326 obstack_free (&g
->ob
, NULL
);
330 /* Returns the nearest common ancestor of X and Y in tree whose parent
331 links are given by PARENT. MARKS is the array used to mark the
332 vertices of the tree, and MARK is the number currently used as a mark. */
335 tree_nca (int x
, int y
, int *parent
, int *marks
, int mark
)
337 if (x
== -1 || x
== y
)
340 /* We climb with X and Y up the tree, marking the visited nodes. When
341 we first arrive to a marked node, it is the common ancestor. */
350 if (marks
[x
] == mark
)
357 if (marks
[y
] == mark
)
362 /* If we reached the root with one of the vertices, continue
363 with the other one till we reach the marked part of the
367 for (y
= parent
[y
]; marks
[y
] != mark
; y
= parent
[y
])
374 for (x
= parent
[x
]; marks
[x
] != mark
; x
= parent
[x
])
381 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
382 arrays), where the entry node is ENTRY. */
385 graphds_domtree (struct graph
*g
, int entry
,
386 int *parent
, int *son
, int *brother
)
388 vec
<int> postorder
= vNULL
;
389 int *marks
= XCNEWVEC (int, g
->n_vertices
);
390 int mark
= 1, i
, v
, idom
;
392 struct graph_edge
*e
;
394 /* We use a slight modification of the standard iterative algorithm, as
397 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
400 sort vertices in reverse postorder
405 while (anything changes)
407 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
409 The sets dom(v) are represented by the parent links in the current version
410 of the dominance tree. */
412 for (i
= 0; i
< g
->n_vertices
; i
++)
418 graphds_dfs (g
, &entry
, 1, &postorder
, true, NULL
);
419 gcc_assert (postorder
.length () == (unsigned) g
->n_vertices
);
420 gcc_assert (postorder
[g
->n_vertices
- 1] == entry
);
426 for (i
= g
->n_vertices
- 2; i
>= 0; i
--)
430 for (e
= g
->vertices
[v
].pred
; e
; e
= e
->pred_next
)
433 && parent
[e
->src
] == -1)
436 idom
= tree_nca (idom
, e
->src
, parent
, marks
, mark
++);
439 if (idom
!= parent
[v
])
448 postorder
.release ();
450 for (i
= 0; i
< g
->n_vertices
; i
++)
453 brother
[i
] = son
[parent
[i
]];