1 /* Graph representation and manipulation functions.
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
31 /* Dumps graph G into F. */
34 dump_graph (FILE *f
, struct graph
*g
)
39 for (i
= 0; i
< g
->n_vertices
; i
++)
41 if (!g
->vertices
[i
].pred
42 && !g
->vertices
[i
].succ
)
45 fprintf (f
, "%d (%d)\t<-", i
, g
->vertices
[i
].component
);
46 for (e
= g
->vertices
[i
].pred
; e
; e
= e
->pred_next
)
47 fprintf (f
, " %d", e
->src
);
51 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
52 fprintf (f
, " %d", e
->dest
);
57 /* Creates a new graph with N_VERTICES vertices. */
60 new_graph (int n_vertices
)
62 struct graph
*g
= XNEW (struct graph
);
64 g
->n_vertices
= n_vertices
;
65 g
->vertices
= XCNEWVEC (struct vertex
, n_vertices
);
70 /* Adds an edge from F to T to graph G. The new edge is returned. */
73 add_edge (struct graph
*g
, int f
, int t
)
75 struct graph_edge
*e
= XNEW (struct graph_edge
);
76 struct vertex
*vf
= &g
->vertices
[f
], *vt
= &g
->vertices
[t
];
82 e
->pred_next
= vt
->pred
;
85 e
->succ_next
= vf
->succ
;
91 /* Moves all the edges incident with U to V. */
94 identify_vertices (struct graph
*g
, int v
, int u
)
96 struct vertex
*vv
= &g
->vertices
[v
];
97 struct vertex
*uu
= &g
->vertices
[u
];
98 struct graph_edge
*e
, *next
;
100 for (e
= uu
->succ
; e
; e
= next
)
105 e
->succ_next
= vv
->succ
;
110 for (e
= uu
->pred
; e
; e
= next
)
115 e
->pred_next
= vv
->pred
;
121 /* Helper function for graphds_dfs. Returns the source vertex of E, in the
122 direction given by FORWARD. */
125 dfs_edge_src (struct graph_edge
*e
, bool forward
)
127 return forward
? e
->src
: e
->dest
;
130 /* Helper function for graphds_dfs. Returns the destination vertex of E, in
131 the direction given by FORWARD. */
134 dfs_edge_dest (struct graph_edge
*e
, bool forward
)
136 return forward
? e
->dest
: e
->src
;
139 /* Helper function for graphds_dfs. Returns the first edge after E (including
140 E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
142 static inline struct graph_edge
*
143 foll_in_subgraph (struct graph_edge
*e
, bool forward
, bitmap subgraph
)
152 d
= dfs_edge_dest (e
, forward
);
153 if (bitmap_bit_p (subgraph
, d
))
156 e
= forward
? e
->succ_next
: e
->pred_next
;
162 /* Helper function for graphds_dfs. Select the first edge from V in G, in the
163 direction given by FORWARD, that belongs to SUBGRAPH. */
165 static inline struct graph_edge
*
166 dfs_fst_edge (struct graph
*g
, int v
, bool forward
, bitmap subgraph
)
168 struct graph_edge
*e
;
170 e
= (forward
? g
->vertices
[v
].succ
: g
->vertices
[v
].pred
);
171 return foll_in_subgraph (e
, forward
, subgraph
);
174 /* Helper function for graphds_dfs. Returns the next edge after E, in the
175 graph direction given by FORWARD, that belongs to SUBGRAPH. */
177 static inline struct graph_edge
*
178 dfs_next_edge (struct graph_edge
*e
, bool forward
, bitmap subgraph
)
180 return foll_in_subgraph (forward
? e
->succ_next
: e
->pred_next
,
184 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
185 The vertices in postorder are stored into QT. If FORWARD is false,
186 backward dfs is run. If SUBGRAPH is not NULL, it specifies the
187 subgraph of G to run DFS on. Returns the number of the components
188 of the graph (number of the restarts of DFS). */
191 graphds_dfs (struct graph
*g
, int *qs
, int nq
, VEC (int, heap
) **qt
,
192 bool forward
, bitmap subgraph
)
194 int i
, tick
= 0, v
, comp
= 0, top
;
195 struct graph_edge
*e
;
196 struct graph_edge
**stack
= XNEWVEC (struct graph_edge
*, g
->n_vertices
);
202 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, av
, bi
)
204 g
->vertices
[av
].component
= -1;
205 g
->vertices
[av
].post
= -1;
210 for (i
= 0; i
< g
->n_vertices
; i
++)
212 g
->vertices
[i
].component
= -1;
213 g
->vertices
[i
].post
= -1;
217 for (i
= 0; i
< nq
; i
++)
220 if (g
->vertices
[v
].post
!= -1)
223 g
->vertices
[v
].component
= comp
++;
224 e
= dfs_fst_edge (g
, v
, forward
, subgraph
);
231 if (g
->vertices
[dfs_edge_dest (e
, forward
)].component
234 e
= dfs_next_edge (e
, forward
, subgraph
);
240 VEC_safe_push (int, heap
, *qt
, v
);
241 g
->vertices
[v
].post
= tick
++;
247 v
= dfs_edge_src (e
, forward
);
248 e
= dfs_next_edge (e
, forward
, subgraph
);
253 v
= dfs_edge_dest (e
, forward
);
254 e
= dfs_fst_edge (g
, v
, forward
, subgraph
);
255 g
->vertices
[v
].component
= comp
- 1;
264 /* Determines the strongly connected components of G, using the algorithm of
265 Tarjan -- first determine the postorder dfs numbering in reversed graph,
266 then run the dfs on the original graph in the order given by decreasing
267 numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
268 specifies the subgraph of G whose strongly connected components we want
271 After running this function, v->component is the number of the strongly
272 connected component for each vertex of G. Returns the number of the
276 graphds_scc (struct graph
*g
, bitmap subgraph
)
278 int *queue
= XNEWVEC (int, g
->n_vertices
);
279 VEC (int, heap
) *postorder
= NULL
;
287 EXECUTE_IF_SET_IN_BITMAP (subgraph
, 0, v
, bi
)
294 for (i
= 0; i
< g
->n_vertices
; i
++)
299 graphds_dfs (g
, queue
, nq
, &postorder
, false, subgraph
);
300 gcc_assert (VEC_length (int, postorder
) == (unsigned) nq
);
302 for (i
= 0; i
< nq
; i
++)
303 queue
[i
] = VEC_index (int, postorder
, nq
- i
- 1);
304 comp
= graphds_dfs (g
, queue
, nq
, NULL
, true, subgraph
);
307 VEC_free (int, heap
, postorder
);
312 /* Runs CALLBACK for all edges in G. */
315 for_each_edge (struct graph
*g
, graphds_edge_callback callback
)
317 struct graph_edge
*e
;
320 for (i
= 0; i
< g
->n_vertices
; i
++)
321 for (e
= g
->vertices
[i
].succ
; e
; e
= e
->succ_next
)
325 /* Releases the memory occupied by G. */
328 free_graph (struct graph
*g
)
330 struct graph_edge
*e
, *n
;
334 for (i
= 0; i
< g
->n_vertices
; i
++)
337 for (e
= v
->succ
; e
; e
= n
)
347 /* Returns the nearest common ancestor of X and Y in tree whose parent
348 links are given by PARENT. MARKS is the array used to mark the
349 vertices of the tree, and MARK is the number currently used as a mark. */
352 tree_nca (int x
, int y
, int *parent
, int *marks
, int mark
)
354 if (x
== -1 || x
== y
)
357 /* We climb with X and Y up the tree, marking the visited nodes. When
358 we first arrive to a marked node, it is the common ancestor. */
367 if (marks
[x
] == mark
)
374 if (marks
[y
] == mark
)
379 /* If we reached the root with one of the vertices, continue
380 with the other one till we reach the marked part of the
384 for (y
= parent
[y
]; marks
[y
] != mark
; y
= parent
[y
])
391 for (x
= parent
[x
]; marks
[x
] != mark
; x
= parent
[x
])
398 /* Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
399 arrays), where the entry node is ENTRY. */
402 graphds_domtree (struct graph
*g
, int entry
,
403 int *parent
, int *son
, int *brother
)
405 VEC (int, heap
) *postorder
= NULL
;
406 int *marks
= XCNEWVEC (int, g
->n_vertices
);
407 int mark
= 1, i
, v
, idom
;
409 struct graph_edge
*e
;
411 /* We use a slight modification of the standard iterative algorithm, as
414 K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
417 sort vertices in reverse postorder
422 while (anything changes)
424 dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
426 The sets dom(v) are represented by the parent links in the current version
427 of the dominance tree. */
429 for (i
= 0; i
< g
->n_vertices
; i
++)
435 graphds_dfs (g
, &entry
, 1, &postorder
, true, NULL
);
436 gcc_assert (VEC_length (int, postorder
) == (unsigned) g
->n_vertices
);
437 gcc_assert (VEC_index (int, postorder
, g
->n_vertices
- 1) == entry
);
443 for (i
= g
->n_vertices
- 2; i
>= 0; i
--)
445 v
= VEC_index (int, postorder
, i
);
447 for (e
= g
->vertices
[v
].pred
; e
; e
= e
->pred_next
)
450 && parent
[e
->src
] == -1)
453 idom
= tree_nca (idom
, e
->src
, parent
, marks
, mark
++);
456 if (idom
!= parent
[v
])
465 VEC_free (int, heap
, postorder
);
467 for (i
= 0; i
< g
->n_vertices
; i
++)
470 brother
[i
] = son
[parent
[i
]];