Line data Source code
1 : /* Template classes for directed graphs.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #ifndef GCC_DIGRAPH_H
22 : #define GCC_DIGRAPH_H
23 :
24 : #include "diagnostic.h"
25 : #include "tree-diagnostic.h" /* for default_tree_printer. */
26 : #include "graphviz.h"
27 :
28 : /* Templates for a family of classes: digraph, node, edge, and cluster.
29 : This assumes a traits type with the following typedefs:
30 : node_t: the node class
31 : edge_t: the edge class
32 : dump_args_t: additional args for dot-dumps
33 : cluster_t: the cluster class (for use when generating .dot files).
34 :
35 : Using a template allows for typesafe nodes and edges: a node's
36 : predecessor and successor edges can be of a node-specific edge
37 : subclass, without needing casting. */
38 :
39 : /* Abstract base class for a node in a directed graph. */
40 :
41 : template <typename GraphTraits>
42 879820 : class dnode
43 : {
44 : public:
45 : typedef typename GraphTraits::edge_t edge_t;
46 : typedef typename GraphTraits::dump_args_t dump_args_t;
47 :
48 879820 : virtual ~dnode () {}
49 : virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
50 :
51 5812 : void add_in_edge (edge_t *e)
52 : {
53 5812 : m_preds.safe_push (e);
54 : }
55 11126 : void remove_in_edge (edge_t *e)
56 : {
57 11126 : m_preds.unordered_remove (find_edge_idx (m_preds, e));
58 11126 : }
59 : void add_out_edge (edge_t *e)
60 : {
61 : m_succs.safe_push (e);
62 : }
63 5314 : void remove_out_edge (edge_t *e)
64 : {
65 5314 : m_succs.unordered_remove (find_edge_idx (m_succs, e));
66 5314 : }
67 :
68 : public:
69 : auto_vec<edge_t *> m_preds;
70 : auto_vec<edge_t *> m_succs;
71 :
72 : private:
73 : static unsigned
74 16440 : find_edge_idx (auto_vec<edge_t *> &edges, edge_t *e)
75 : {
76 17018 : for (unsigned i = 0; i < edges.length (); ++i)
77 17018 : if (edges[i] == e)
78 16440 : return i;
79 0 : gcc_unreachable ();
80 : }
81 : };
82 :
83 : /* Abstract base class for an edge in a directed graph. */
84 :
85 : template <typename GraphTraits>
86 : class dedge
87 : {
88 : public:
89 : typedef typename GraphTraits::node_t node_t;
90 : typedef typename GraphTraits::edge_t edge_t;
91 : typedef typename GraphTraits::dump_args_t dump_args_t;
92 :
93 886916 : dedge (node_t *src, node_t *dest)
94 886916 : : m_src (src), m_dest (dest) {}
95 :
96 187243 : virtual ~dedge () {}
97 :
98 : virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = 0;
99 :
100 5812 : void set_dest (node_t *new_dest)
101 : {
102 5812 : node_t *old_dest = m_dest;
103 5812 : if (new_dest != old_dest)
104 : {
105 5812 : old_dest->remove_in_edge (static_cast<edge_t *> (this));
106 5812 : m_dest = new_dest;
107 5812 : new_dest->add_in_edge (static_cast<edge_t *> (this));
108 : }
109 5812 : }
110 :
111 : node_t *m_src;
112 : node_t *m_dest;
113 : };
114 :
115 : /* Abstract base class for a directed graph.
116 : This class maintains the vectors of nodes and edges,
117 : and owns the nodes and edges. */
118 :
119 : template <typename GraphTraits>
120 : class digraph
121 : {
122 : public:
123 : typedef typename GraphTraits::node_t node_t;
124 : typedef typename GraphTraits::edge_t edge_t;
125 : typedef typename GraphTraits::dump_args_t dump_args_t;
126 : typedef typename GraphTraits::cluster_t cluster_t;
127 :
128 19504 : digraph () {}
129 19504 : virtual ~digraph () {}
130 :
131 : void dump_dot_to_pp (pretty_printer *pp,
132 : cluster_t *root_cluster,
133 : const dump_args_t &args) const;
134 : void dump_dot_to_file (FILE *fp,
135 : cluster_t *root_cluster,
136 : const dump_args_t &args) const;
137 : void dump_dot (const char *path,
138 : cluster_t *root_cluster,
139 : const dump_args_t &args) const;
140 :
141 : void add_node (node_t *node);
142 : void add_edge (edge_t *edge);
143 :
144 : virtual void
145 16 : add_any_extra_stmts (graphviz_out &) const
146 : {
147 : // no-op hook
148 16 : }
149 :
150 : auto_delete_vec<node_t> m_nodes;
151 : auto_delete_vec<edge_t> m_edges;
152 : };
153 :
154 : /* Abstract base class for splitting dnodes into hierarchical clusters
155 : in the generated .dot file.
156 :
157 : See "Subgraphs and Clusters" within
158 : https://www.graphviz.org/doc/info/lang.html
159 : and e.g.
160 : https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html
161 :
162 : If a root_cluster is passed to dump_dot*, then all nodes will be
163 : added to it at the start of dumping, via calls to add_node.
164 :
165 : The root cluster can organize the nodes into a hierarchy of
166 : child clusters.
167 :
168 : After all nodes are added to the root cluster, dump_dot will then
169 : be called on it (and not on the nodes themselves). */
170 :
171 : template <typename GraphTraits>
172 858 : class cluster
173 : {
174 : public:
175 : typedef typename GraphTraits::node_t node_t;
176 : typedef typename GraphTraits::dump_args_t dump_args_t;
177 :
178 4 : virtual ~cluster () {}
179 :
180 : virtual void add_node (node_t *node) = 0;
181 :
182 : /* Recursively dump the cluster, all nodes, and child clusters. */
183 : virtual void dump_dot (graphviz_out *gv, const dump_args_t &) const = 0;
184 : };
185 :
186 : /* Write .dot information for this graph to PP, passing ARGS to the nodes
187 : and edges.
188 : If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
189 :
190 : template <typename GraphTraits>
191 : inline void
192 16 : digraph<GraphTraits>::dump_dot_to_pp (pretty_printer *pp,
193 : cluster_t *root_cluster,
194 : const dump_args_t &args) const
195 : {
196 16 : graphviz_out gv (pp);
197 :
198 16 : pp_string (pp, "digraph \"");
199 16 : pp_string (pp, "base");
200 16 : pp_string (pp, "\" {\n");
201 :
202 16 : gv.indent ();
203 :
204 16 : pp_string (pp, "overlap=false;\n");
205 16 : pp_string (pp, "compound=true;\n");
206 :
207 : /* If using clustering, emit all nodes via clusters. */
208 16 : if (root_cluster)
209 : {
210 : int i;
211 : node_t *n;
212 437 : FOR_EACH_VEC_ELT (m_nodes, i, n)
213 433 : root_cluster->add_node (n);
214 4 : root_cluster->dump_dot (&gv, args);
215 : }
216 : else
217 : {
218 : /* Otherwise, display all nodes at top level. */
219 : int i;
220 : node_t *n;
221 168 : FOR_EACH_VEC_ELT (m_nodes, i, n)
222 156 : n->dump_dot (&gv, args);
223 : }
224 :
225 : /* Edges. */
226 : int i;
227 : edge_t *e;
228 605 : FOR_EACH_VEC_ELT (m_edges, i, e)
229 589 : e->dump_dot (&gv, args);
230 :
231 16 : add_any_extra_stmts (gv);
232 :
233 : /* Terminate "digraph" */
234 16 : gv.outdent ();
235 16 : pp_string (pp, "}");
236 16 : pp_newline (pp);
237 16 : }
238 :
239 : /* Write .dot information for this graph to FP, passing ARGS to the nodes
240 : and edges.
241 : If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
242 :
243 : template <typename GraphTraits>
244 : inline void
245 12 : digraph<GraphTraits>::dump_dot_to_file (FILE *fp,
246 : cluster_t *root_cluster,
247 : const dump_args_t &args) const
248 : {
249 12 : pretty_printer pp;
250 : // TODO:
251 12 : pp_format_decoder (&pp) = default_tree_printer;
252 12 : pp.set_output_stream (fp);
253 12 : dump_dot_to_pp (&pp, root_cluster, args);
254 12 : pp_flush (&pp);
255 12 : }
256 :
257 : /* Write .dot information for this graph to a file at PATH, passing ARGS
258 : to the nodes and edges.
259 : If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters. */
260 :
261 : template <typename GraphTraits>
262 : inline void
263 12 : digraph<GraphTraits>::dump_dot (const char *path,
264 : cluster_t *root_cluster,
265 : const dump_args_t &args) const
266 : {
267 12 : FILE *fp = fopen (path, "w");
268 12 : dump_dot_to_file (fp, root_cluster, args);
269 12 : fclose (fp);
270 12 : }
271 :
272 : /* Add NODE to this DIGRAPH, taking ownership. */
273 :
274 : template <typename GraphTraits>
275 : inline void
276 692166 : digraph<GraphTraits>::add_node (node_t *node)
277 : {
278 692166 : m_nodes.safe_push (node);
279 : }
280 :
281 : /* Add EDGE to this digraph, and to the preds/succs of its endpoints.
282 : Take ownership of EDGE. */
283 :
284 : template <typename GraphTraits>
285 : inline void
286 886916 : digraph<GraphTraits>::add_edge (edge_t *edge)
287 : {
288 886916 : m_edges.safe_push (edge);
289 886916 : edge->m_dest->m_preds.safe_push (edge);
290 886916 : edge->m_src->m_succs.safe_push (edge);
291 :
292 886916 : }
293 :
294 : #endif /* GCC_DIGRAPH_H */
|
