GCC Middle and Back End API Reference
supergraph.h
Go to the documentation of this file.
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
55
56/* A traits struct describing the family of node, edge and digraph
57 classes for supergraphs. */
58
60{
65 {
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
77 };
78 typedef supercluster cluster_t;
79};
80
81/* A class to manage the setting and restoring of statement uids. */
82
84{
85public:
86 void make_uid_unique (gimple *stmt);
87 void restore_uids () const;
88
89private:
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:
109
114
119
121 {
122 return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
123 }
124
126 {
127 return *const_cast <bb_to_node_t &> (m_bb_to_final_node).get (bb);
128 }
129
131 {
132 auto iter = m_node_for_stmt.find (stmt);
133 gcc_assert (iter != m_node_for_stmt.end ());
134 return iter->second;
135 }
136
138 {
139 auto iter = m_edges_for_phis.find (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 {
158 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. */
167
168 /* Implemented in supergraph-simplify.cc. */
169 void simplify (logger *);
170
171 /* Implemented in supergraph-sorting.cc. */
173
175
176 std::unique_ptr<diagnostics::digraphs::digraph>
178
179private:
180 gimple *
182 function *fun,
183 logger *logger);
184
185 void
187 supernode *dest,
188 ::edge e,
189 gimple *control_stmt,
191 logger *logger);
192
194 class loop *, function *) const;
196 basic_block, function *) const;
197
198 /* Implemented in supergraph-sorting.cc. */
199 void
200 reorder_nodes_and_ids (const std::vector<supernode *> &ordering,
201 logger *logger);
202
203 /* Data. */
204
208
209 std::map<const gimple *, supernode *> m_node_for_stmt;
210 std::map<::edge, superedge *> m_edges_for_phis;
211
214
216
217 /* Hand out unique IDs to supernodes, to make it easier
218 to track them when deleting/splitting etc (they're easier to
219 think about when debugging than pointer values). */
221 std::vector<supernode *> m_snode_by_id;
222};
223
224/* A node within a supergraph. */
225
226class supernode : public dnode<supergraph_traits>
227{
228 public:
229 supernode (function *fun, basic_block bb, int id)
230 : m_fun (fun), m_bb (bb),
233 m_id (id),
238 {}
239
240 function *get_function () const { return m_fun; }
241
242 bool entry_p () const
243 {
245 }
246 bool exit_p () const
247 {
248 return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
249 }
250
251 void dump_dot (graphviz_out *gv, const dump_args_t &args) const override;
252 void dump_dot_id (pretty_printer *pp) const;
253
254 void print (pretty_printer *pp) const
255 {
256 pp_printf (pp, "SN %i", m_id);
257 }
258
259 std::unique_ptr<json::object> to_json () const;
260
261 location_t get_location () const { return m_loc; }
262
263 tree get_label () const { return m_label; }
264
265 bool preserve_p () const { return m_preserve_p; }
266
269 location_t m_loc;
270 location_t m_stmt_loc; // for debugging
271 int m_id; /* unique within the supergraph as a whole. */
272 const int m_original_id;
276};
277
278/* An edge within the supergraph, with an optional operation.
279 Edges can be CFG edges or edges between statements, or persist
280 in order to give more opportunities for state-merging when
281 building the exploded graph. */
282
283class superedge : public dedge<supergraph_traits>
284{
285 public:
287 std::unique_ptr<operation> op,
288 ::edge cfg_edge)
289 : dedge<supergraph_traits> (src, dest),
290 m_op (std::move (op)),
291 m_cfg_edge (cfg_edge)
292 {
293 /* All edges are intraprocedural. */
295 == m_dest->get_function ());
296 }
297
298 virtual ~superedge () {}
299
300 void dump (pretty_printer *pp) const;
301 void dump () const;
302 void dump_dot (graphviz_out *gv, const dump_args_t &args)
303 const final override;
304
305 const operation *get_op () const { return m_op.get (); }
306 void set_op (std::unique_ptr<operation> op) { m_op = std::move (op); }
307
309 bool user_facing) const;
310
311 std::unique_ptr<json::object> to_json () const;
312
313 const supernode *get_dest_snode () const { return m_dest; }
314
315 ::edge get_any_cfg_edge () const { return m_cfg_edge; }
316
317 bool preserve_p () const;
318
319 label_text get_description (bool user_facing) const;
320
321 bool
323
324private:
325 std::unique_ptr<operation> m_op;
327};
328
329/* Base class for adding additional content to the .dot output
330 for a supergraph. */
331
333{
334 public:
335 virtual ~dot_annotator () = default;
336
337 virtual void
338 add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
339 const supernode &n ATTRIBUTE_UNUSED) const
340 {
341 // no-op
342 }
343
344 virtual void
345 add_extra_objects (graphviz_out *gv ATTRIBUTE_UNUSED) const
346 {
347 // no-op
348 }
349};
350
351} // namespace ana
352
353#endif /* GCC_ANALYZER_SUPERGRAPH_H */
#define ENTRY_BLOCK_PTR_FOR_FN(FN)
Definition basic-block.h:194
#define EXIT_BLOCK_PTR_FOR_FN(FN)
Definition basic-block.h:195
Definition supergraph.h:333
virtual void add_extra_objects(graphviz_out *gv) const
Definition supergraph.h:345
virtual void add_node_annotations(graphviz_out *gv, const supernode &n) const
Definition supergraph.h:338
virtual ~dot_annotator()=default
Definition exploded-graph.h:809
Definition analyzer-logging.h:36
Definition ops.h:113
Definition region-model-manager.h:36
Definition supergraph.h:84
void restore_uids() const
void make_uid_unique(gimple *stmt)
auto_vec< std::pair< gimple *, unsigned > > m_old_stmt_uids
Definition supergraph.h:90
Definition supergraph.h:284
bool preserve_p() const
::edge m_cfg_edge
Definition supergraph.h:326
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
bool supports_bulk_merge_p() const
void dump(pretty_printer *pp) const
::edge get_any_cfg_edge() const
Definition supergraph.h:315
const operation * get_op() const
Definition supergraph.h:305
label_text get_description(bool user_facing) const
superedge(supernode *src, supernode *dest, std::unique_ptr< operation > op, ::edge cfg_edge)
Definition supergraph.h:286
void dump_label_to_pp(pretty_printer *pp, bool user_facing) const
std::unique_ptr< json::object > to_json() const
std::unique_ptr< operation > m_op
Definition supergraph.h:325
const supernode * get_dest_snode() const
Definition supergraph.h:313
virtual ~superedge()
Definition supergraph.h:298
void dump() const
void set_op(std::unique_ptr< operation > op)
Definition supergraph.h:306
Definition supergraph.h:105
std::unique_ptr< json::object > to_json() const
void fixup_locations(logger *)
int num_edges() const
Definition supergraph.h:152
supernode * add_node(function *fun, basic_block bb, logger *logger)
supernode * get_initial_node_for_block(basic_block bb) const
Definition supergraph.h:120
void sort_nodes(logger *logger)
void simplify(logger *)
unsigned get_num_snodes(const function *fun) const
Definition supergraph.h:154
void reorder_nodes_and_ids(const std::vector< supernode * > &ordering, logger *logger)
int m_next_snode_id
Definition supergraph.h:220
int num_nodes() const
Definition supergraph.h:151
supernode * get_node_for_function_exit(const function &fun) const
Definition supergraph.h:115
bb_to_node_t m_bb_to_final_node
Definition supergraph.h:207
std::vector< supernode * > m_snode_by_id
Definition supergraph.h:221
void log_stats(logger *logger) const
void dump_dot_to_pp(pretty_printer *pp, const dump_args_t &) const
gimple * populate_for_basic_block(basic_block bb, function *fun, logger *logger)
std::map<::edge, superedge * > m_edges_for_phis
Definition supergraph.h:210
ordered_hash_map< basic_block, supernode * > bb_to_node_t
Definition supergraph.h:205
supernode * get_node_for_function_entry(const function &fun) const
Definition supergraph.h:110
void add_sedges_for_cfg_edge(supernode *src, supernode *dest, ::edge e, gimple *control_stmt, region_model_manager &mgr, logger *logger)
void dump_dot_to_gv_for_bb(graphviz_out &gv, const dump_args_t &, basic_block, function *) const
function_to_num_snodes_t m_function_to_num_snodes
Definition supergraph.h:213
void dump_dot_to_gv_for_loop(graphviz_out &gv, const dump_args_t &, class loop *, function *) const
superedge * get_superedge_for_phis(::edge cfg_edge) const
Definition supergraph.h:137
hash_map< const function *, unsigned > function_to_num_snodes_t
Definition supergraph.h:212
std::map< const gimple *, supernode * > m_node_for_stmt
Definition supergraph.h:209
bb_to_node_t m_bb_to_initial_node
Definition supergraph.h:206
supernode * get_supernode_for_stmt(const gimple *stmt) const
Definition supergraph.h:130
supernode * get_final_node_for_block(basic_block bb) const
Definition supergraph.h:125
void delete_nodes(const std::set< supernode * > &snodes)
void dump_dot_to_file(FILE *fp, const dump_args_t &) const
supergraph(region_model_manager &mgr, logger *logger)
void dump_dot(const char *path, const dump_args_t &) const
saved_uids m_stmt_uids
Definition supergraph.h:215
std::unique_ptr< diagnostics::digraphs::digraph > make_diagnostics_digraph() const
Definition supergraph.h:227
const int m_original_id
Definition supergraph.h:272
location_t m_loc
Definition supergraph.h:269
supernode(function *fun, basic_block bb, int id)
Definition supergraph.h:229
tree m_label
Definition supergraph.h:273
bool entry_p() const
Definition supergraph.h:242
bool m_state_merger_node
Definition supergraph.h:275
const basic_block m_bb
Definition supergraph.h:268
location_t m_stmt_loc
Definition supergraph.h:270
void dump_dot_id(pretty_printer *pp) const
location_t get_location() const
Definition supergraph.h:261
tree get_label() const
Definition supergraph.h:263
void dump_dot(graphviz_out *gv, const dump_args_t &args) const override
bool exit_p() const
Definition supergraph.h:246
bool preserve_p() const
Definition supergraph.h:265
std::unique_ptr< json::object > to_json() const
function * get_function() const
Definition supergraph.h:240
void print(pretty_printer *pp) const
Definition supergraph.h:254
int m_id
Definition supergraph.h:271
bool m_preserve_p
Definition supergraph.h:274
function *const m_fun
Definition supergraph.h:267
Definition vec.h:1667
node_t * m_dest
Definition digraph.h:112
dedge(node_t *src, node_t *dest)
Definition digraph.h:93
node_t * m_src
Definition digraph.h:111
supergraph_traits::dump_args_t dump_args_t
Definition digraph.h:91
auto_delete_vec< edge_t > m_edges
Definition digraph.h:151
auto_delete_vec< node_t > m_nodes
Definition digraph.h:150
supergraph_traits::dump_args_t dump_args_t
Definition digraph.h:125
digraph()
Definition digraph.h:128
Definition digraph.h:43
supergraph_traits::dump_args_t dump_args_t
Definition digraph.h:46
Definition graphviz.h:388
Definition hash-map.h:40
Value * get(const Key &k)
Definition hash-map.h:189
Definition cfgloop.h:120
Definition ordered-hash-map.h:35
Definition pretty-print.h:241
struct basic_block_def * basic_block
Definition coretypes.h:359
class edge_def * edge
Definition coretypes.h:356
union tree_node * tree
Definition coretypes.h:97
#define UNKNOWN_LOCATION
Definition input.h:32
Definition access-diagram.h:30
@ stmt
Definition checker-event.h:38
supergraph_dot_flags
Definition supergraph.h:52
@ SUPERGRAPH_DOT_SHOW_BBS
Definition supergraph.h:53
void pp_printf(pretty_printer *pp, const char *msg,...)
Definition pretty-print.cc:2684
dump_args_t(enum supergraph_dot_flags flags, const dot_annotator *node_annotator, const exploded_graph *eg)
Definition supergraph.h:66
const dot_annotator * m_node_annotator
Definition supergraph.h:75
enum supergraph_dot_flags m_flags
Definition supergraph.h:74
const exploded_graph * m_eg
Definition supergraph.h:76
Definition supergraph.h:60
supercluster cluster_t
Definition supergraph.h:78
supernode node_t
Definition supergraph.h:61
supergraph graph_t
Definition supergraph.h:63
superedge edge_t
Definition supergraph.h:62
Definition function.h:249
Definition gimple.h:225
Definition collect2.cc:168
Definition ira-emit.cc:158
#define gcc_assert(EXPR)
Definition system.h:772
#define false
Definition system.h:846
#define NULL_TREE
Definition tree.h:320