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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
35using namespace ana;
36
37namespace ana {
38
39/* Forward decls, using indentation to show inheritance. */
40
41class supergraph;
42class supernode;
43class superedge;
44class supercluster;
45class dot_annotator;
46
47class logger;
48
49/* Flags for controlling the appearance of .dot dumps. */
50
51enum 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
59struct 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 dump_args_t (enum supergraph_dot_flags flags,
67 const dot_annotator *node_annotator,
68 const exploded_graph *eg)
69 : m_flags (flags),
70 m_node_annotator (node_annotator),
71 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
83class saved_uids
84{
85public:
86 void make_uid_unique (gimple *stmt);
87 void restore_uids () const;
88
89private:
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
104class supergraph : public digraph<supergraph_traits>
105{
106public:
107 supergraph (region_model_manager &mgr, logger *logger);
108 ~supergraph ();
109
110 supernode *get_node_for_function_entry (const function &fun) const
111 {
112 return get_initial_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (&fun));
113 }
114
115 supernode *get_node_for_function_exit (const function &fun) const
116 {
117 return get_final_node_for_block (EXIT_BLOCK_PTR_FOR_FN (&fun));
118 }
119
120 supernode *get_initial_node_for_block (basic_block bb) const
121 {
122 return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (k: bb);
123 }
124
125 supernode *get_final_node_for_block (basic_block bb) const
126 {
127 return *const_cast <bb_to_node_t &> (m_bb_to_final_node).get (k: bb);
128 }
129
130 supernode *get_supernode_for_stmt (const gimple *stmt) const
131 {
132 auto iter = m_node_for_stmt.find (x: stmt);
133 gcc_assert (iter != m_node_for_stmt.end ());
134 return iter->second;
135 }
136
137 superedge *get_superedge_for_phis (::edge cfg_edge) const
138 {
139 auto iter = m_edges_for_phis.find (x: cfg_edge);
140 if (iter != m_edges_for_phis.end ())
141 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 int num_nodes () const { return m_nodes.length (); }
152 int num_edges () const { return m_edges.length (); }
153
154 unsigned get_num_snodes (const function *fun) const
155 {
156 function_to_num_snodes_t &map
157 = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
158 return *map.get (k: 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
176private:
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
223class supernode : public dnode<supergraph_traits>
224{
225 public:
226 supernode (function *fun, basic_block bb, int id)
227 : m_fun (fun), m_bb (bb),
228 m_loc (UNKNOWN_LOCATION),
229 m_stmt_loc (UNKNOWN_LOCATION),
230 m_id (id),
231 m_original_id (id),
232 m_label (NULL_TREE),
233 m_preserve_p (false),
234 m_state_merger_node (false)
235 {}
236
237 function *get_function () const { return m_fun; }
238
239 bool entry_p () const
240 {
241 return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
242 }
243 bool exit_p () const
244 {
245 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 void print (pretty_printer *pp) const
252 {
253 pp_printf (pp, "SN %i", m_id);
254 }
255
256 std::unique_ptr<json::object> to_json () const;
257
258 location_t get_location () const { return m_loc; }
259
260 tree get_label () const { return m_label; }
261
262 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
280class superedge : public dedge<supergraph_traits>
281{
282 public:
283 superedge (supernode *src, supernode *dest,
284 std::unique_ptr<operation> op,
285 ::edge cfg_edge)
286 : dedge<supergraph_traits> (src, dest),
287 m_op (std::move (op)),
288 m_cfg_edge (cfg_edge)
289 {
290 /* All edges are intraprocedural. */
291 gcc_assert (m_src->get_function ()
292 == m_dest->get_function ());
293 }
294
295 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 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 ::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
321private:
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
329class callsite_expr
330{
331 public:
332 callsite_expr () : m_val (-1) {}
333
334 static callsite_expr from_zero_based_param (int idx)
335 {
336 return callsite_expr (idx + 1);
337 }
338
339 static callsite_expr from_return_value ()
340 {
341 return callsite_expr (0);
342 }
343
344 bool param_p () const
345 {
346 return m_val > 0;
347 }
348
349 bool return_value_p () const
350 {
351 return m_val == 0;
352 }
353
354 private:
355 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
363class dot_annotator
364{
365 public:
366 virtual ~dot_annotator () = default;
367
368 virtual void
369 add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
370 const supernode &n ATTRIBUTE_UNUSED) const
371 {
372 // no-op
373 }
374
375 virtual void
376 add_extra_objects (graphviz_out *gv ATTRIBUTE_UNUSED) const
377 {
378 // no-op
379 }
380};
381
382} // namespace ana
383
384#endif /* GCC_ANALYZER_SUPERGRAPH_H */
385

source code of gcc/analyzer/supergraph.h