Line data Source code
1 : /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
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_ANALYZER_SUPERGRAPH_H
22 : #define GCC_ANALYZER_SUPERGRAPH_H
23 :
24 : #include "ordered-hash-map.h"
25 : #include "cfg.h"
26 : #include "basic-block.h"
27 : #include "cfgloop.h"
28 : #include "gimple.h"
29 : #include "gimple-iterator.h"
30 : #include "digraph.h"
31 : #include "except.h"
32 :
33 : #include "analyzer/ops.h"
34 :
35 : using namespace ana;
36 :
37 : namespace ana {
38 :
39 : /* Forward decls, using indentation to show inheritance. */
40 :
41 : class supergraph;
42 : class supernode;
43 : class superedge;
44 : class supercluster;
45 : class dot_annotator;
46 :
47 : class logger;
48 :
49 : /* Flags for controlling the appearance of .dot dumps. */
50 :
51 : enum supergraph_dot_flags
52 : {
53 : SUPERGRAPH_DOT_SHOW_BBS = (1 << 0)
54 : };
55 :
56 : /* A traits struct describing the family of node, edge and digraph
57 : classes for supergraphs. */
58 :
59 : struct supergraph_traits
60 : {
61 : typedef supernode node_t;
62 : typedef superedge edge_t;
63 : typedef supergraph graph_t;
64 : struct dump_args_t
65 : {
66 24 : dump_args_t (enum supergraph_dot_flags flags,
67 : const dot_annotator *node_annotator,
68 : const exploded_graph *eg)
69 24 : : m_flags (flags),
70 24 : m_node_annotator (node_annotator),
71 24 : m_eg (eg)
72 : {}
73 :
74 : enum supergraph_dot_flags m_flags;
75 : const dot_annotator *m_node_annotator;
76 : const exploded_graph *m_eg;
77 : };
78 : typedef supercluster cluster_t;
79 : };
80 :
81 : /* A class to manage the setting and restoring of statement uids. */
82 :
83 6754 : class saved_uids
84 : {
85 : public:
86 : void make_uid_unique (gimple *stmt);
87 : void restore_uids () const;
88 :
89 : private:
90 : auto_vec<std::pair<gimple *, unsigned> > m_old_stmt_uids;
91 : };
92 :
93 : /* A directed graph class representing the users's code,
94 : with nodes representing locations within functions, and
95 : edges representing transitions between them.
96 :
97 : For historical reasons we call this the "supergraph", although
98 : this is now a misnomer as we no longer add callgraph edges to this
99 : graph: the edges within the supergraph are purely intraprocedural:
100 : either linking consecutive stmts in a basic block, or linking
101 : basic blocks (corresponding to CFG edges). However, all functions
102 : are within the same graph. */
103 :
104 : class supergraph : public digraph<supergraph_traits>
105 : {
106 : public:
107 : supergraph (region_model_manager &mgr, logger *logger);
108 : ~supergraph ();
109 :
110 27068 : supernode *get_node_for_function_entry (const function &fun) const
111 : {
112 54136 : return get_initial_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (&fun));
113 : }
114 :
115 34 : supernode *get_node_for_function_exit (const function &fun) const
116 : {
117 68 : return get_final_node_for_block (EXIT_BLOCK_PTR_FOR_FN (&fun));
118 : }
119 :
120 27068 : supernode *get_initial_node_for_block (basic_block bb) const
121 : {
122 27068 : return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
123 : }
124 :
125 34 : supernode *get_final_node_for_block (basic_block bb) const
126 : {
127 34 : return *const_cast <bb_to_node_t &> (m_bb_to_final_node).get (bb);
128 : }
129 :
130 432399 : supernode *get_supernode_for_stmt (const gimple *stmt) const
131 : {
132 432399 : auto iter = m_node_for_stmt.find (stmt);
133 432399 : gcc_assert (iter != m_node_for_stmt.end ());
134 432399 : return iter->second;
135 : }
136 :
137 10496 : superedge *get_superedge_for_phis (::edge cfg_edge) const
138 : {
139 10496 : auto iter = m_edges_for_phis.find (cfg_edge);
140 10496 : if (iter != m_edges_for_phis.end ())
141 10430 : return iter->second;
142 : return nullptr;
143 : }
144 :
145 : void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const;
146 : void dump_dot_to_file (FILE *fp, const dump_args_t &) const;
147 : void dump_dot (const char *path, const dump_args_t &) const;
148 :
149 : std::unique_ptr<json::object> to_json () const;
150 :
151 719266 : int num_nodes () const { return m_nodes.length (); }
152 : int num_edges () const { return m_edges.length (); }
153 :
154 1043 : unsigned get_num_snodes (const function *fun) const
155 : {
156 1043 : function_to_num_snodes_t &map
157 : = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
158 1043 : return *map.get (fun);
159 : }
160 :
161 : void log_stats (logger *logger) const;
162 :
163 : void delete_nodes (const std::set<supernode *> &snodes);
164 :
165 : /* Implemented in supergraph-fixup-locations.cc. */
166 : void fixup_locations (logger *);
167 :
168 : /* Implemented in supergraph-simplify.cc. */
169 : void simplify (logger *);
170 :
171 : /* Implemented in supergraph-sorting.cc. */
172 : void sort_nodes (logger *logger);
173 :
174 : supernode *add_node (function *fun, basic_block bb, logger *logger);
175 :
176 : private:
177 : gimple *
178 : populate_for_basic_block (basic_block bb,
179 : function *fun,
180 : logger *logger);
181 :
182 : void
183 : add_sedges_for_cfg_edge (supernode *src,
184 : supernode *dest,
185 : ::edge e,
186 : gimple *control_stmt,
187 : region_model_manager &mgr,
188 : logger *logger);
189 :
190 : void dump_dot_to_gv_for_loop (graphviz_out &gv, const dump_args_t &,
191 : class loop *, function *) const;
192 : void dump_dot_to_gv_for_bb (graphviz_out &gv, const dump_args_t &,
193 : basic_block, function *) const;
194 :
195 : /* Implemented in supergraph-sorting.cc. */
196 : void
197 : reorder_nodes_and_ids (const std::vector<supernode *> &ordering,
198 : logger *logger);
199 :
200 : /* Data. */
201 :
202 : typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t;
203 : bb_to_node_t m_bb_to_initial_node;
204 : bb_to_node_t m_bb_to_final_node;
205 :
206 : std::map<const gimple *, supernode *> m_node_for_stmt;
207 : std::map<::edge, superedge *> m_edges_for_phis;
208 :
209 : typedef hash_map<const function *, unsigned> function_to_num_snodes_t;
210 : function_to_num_snodes_t m_function_to_num_snodes;
211 :
212 : saved_uids m_stmt_uids;
213 :
214 : /* Hand out unique IDs to supernodes, to make it easier
215 : to track them when deleting/splitting etc (they're easier to
216 : think about when debugging than pointer values). */
217 : int m_next_snode_id;
218 : std::vector<supernode *> m_snode_by_id;
219 : };
220 :
221 : /* A node within a supergraph. */
222 :
223 : class supernode : public dnode<supergraph_traits>
224 : {
225 : public:
226 187654 : supernode (function *fun, basic_block bb, int id)
227 187654 : : m_fun (fun), m_bb (bb),
228 187654 : m_loc (UNKNOWN_LOCATION),
229 187654 : m_stmt_loc (UNKNOWN_LOCATION),
230 187654 : m_id (id),
231 187654 : m_original_id (id),
232 187654 : m_label (NULL_TREE),
233 187654 : m_preserve_p (false),
234 187654 : m_state_merger_node (false)
235 : {}
236 :
237 6352387 : function *get_function () const { return m_fun; }
238 :
239 373111 : bool entry_p () const
240 : {
241 373111 : return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
242 : }
243 365129 : bool exit_p () const
244 : {
245 365129 : return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
246 : }
247 :
248 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const override;
249 : void dump_dot_id (pretty_printer *pp) const;
250 :
251 3901 : void print (pretty_printer *pp) const
252 : {
253 3901 : pp_printf (pp, "SN %i", m_id);
254 : }
255 :
256 : std::unique_ptr<json::object> to_json () const;
257 :
258 385210 : location_t get_location () const { return m_loc; }
259 :
260 191 : tree get_label () const { return m_label; }
261 :
262 174346 : bool preserve_p () const { return m_preserve_p; }
263 :
264 : function * const m_fun;
265 : const basic_block m_bb;
266 : location_t m_loc;
267 : location_t m_stmt_loc; // for debugging
268 : int m_id; /* unique within the supergraph as a whole. */
269 : const int m_original_id;
270 : tree m_label;
271 : bool m_preserve_p;
272 : bool m_state_merger_node;
273 : };
274 :
275 : /* An edge within the supergraph, with an optional operation.
276 : Edges can be CFG edges or edges between statements, or persist
277 : in order to give more opportunities for state-merging when
278 : building the exploded graph. */
279 :
280 : class superedge : public dedge<supergraph_traits>
281 : {
282 : public:
283 187243 : superedge (supernode *src, supernode *dest,
284 : std::unique_ptr<operation> op,
285 : ::edge cfg_edge)
286 187243 : : dedge<supergraph_traits> (src, dest),
287 187243 : m_op (std::move (op)),
288 187243 : m_cfg_edge (cfg_edge)
289 : {
290 : /* All edges are intraprocedural. */
291 187243 : gcc_assert (m_src->get_function ()
292 : == m_dest->get_function ());
293 187243 : }
294 :
295 187243 : virtual ~superedge () {}
296 :
297 : void dump (pretty_printer *pp) const;
298 : void dump () const;
299 : void dump_dot (graphviz_out *gv, const dump_args_t &args)
300 : const final override;
301 :
302 2032667 : const operation *get_op () const { return m_op.get (); }
303 : void set_op (std::unique_ptr<operation> op) { m_op = std::move (op); }
304 :
305 : void dump_label_to_pp (pretty_printer *pp,
306 : bool user_facing) const;
307 :
308 : std::unique_ptr<json::object> to_json () const;
309 :
310 : const supernode *get_dest_snode () const { return m_dest; }
311 :
312 753362 : ::edge get_any_cfg_edge () const { return m_cfg_edge; }
313 :
314 : bool preserve_p () const;
315 :
316 : label_text get_description (bool user_facing) const;
317 :
318 : bool
319 : supports_bulk_merge_p () const;
320 :
321 : private:
322 : std::unique_ptr<operation> m_op;
323 : ::edge m_cfg_edge;
324 : };
325 :
326 : /* An ID representing an expression at a callsite:
327 : either a parameter index, or the return value (or unknown). */
328 :
329 : class callsite_expr
330 : {
331 : public:
332 1624 : callsite_expr () : m_val (-1) {}
333 :
334 310 : static callsite_expr from_zero_based_param (int idx)
335 : {
336 310 : return callsite_expr (idx + 1);
337 : }
338 :
339 94 : static callsite_expr from_return_value ()
340 : {
341 94 : return callsite_expr (0);
342 : }
343 :
344 215 : bool param_p () const
345 : {
346 215 : return m_val > 0;
347 : }
348 :
349 185 : bool return_value_p () const
350 : {
351 185 : return m_val == 0;
352 : }
353 :
354 : private:
355 404 : callsite_expr (int val) : m_val (val) {}
356 :
357 : int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown". */
358 : };
359 :
360 : /* Base class for adding additional content to the .dot output
361 : for a supergraph. */
362 :
363 8 : class dot_annotator
364 : {
365 : public:
366 8 : virtual ~dot_annotator () = default;
367 :
368 : virtual void
369 0 : add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
370 : const supernode &n ATTRIBUTE_UNUSED) const
371 : {
372 : // no-op
373 0 : }
374 :
375 : virtual void
376 4 : add_extra_objects (graphviz_out *gv ATTRIBUTE_UNUSED) const
377 : {
378 : // no-op
379 4 : }
380 : };
381 :
382 : } // namespace ana
383 :
384 : #endif /* GCC_ANALYZER_SUPERGRAPH_H */
|
