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-2024 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 "gimple.h"
28#include "gimple-iterator.h"
29#include "digraph.h"
30
31using namespace ana;
32
33namespace ana {
34
35/* Forward decls, using indentation to show inheritance. */
36
37class supergraph;
38class supernode;
39class superedge;
41 class call_superedge;
42 class return_superedge;
43 class cfg_superedge;
45class supercluster;
46class dot_annotator;
47
48class logger;
49
50/* An enum for discriminating between superedge subclasses. */
51
59
60/* Flags for controlling the appearance of .dot dumps. */
61
66
67/* A traits struct describing the family of node, edge and digraph
68 classes for supergraphs. */
69
88
89/* A class to manage the setting and restoring of statement uids. */
90
92{
93public:
94 void make_uid_unique (gimple *stmt);
95 void restore_uids () const;
96
97private:
99};
100
101/* A "supergraph" is a directed graph formed by joining together all CFGs,
102 linking them via interprocedural call and return edges.
103
104 Basic blocks are split at callsites, so that a call statement occurs
105 twice: once at the end of a supernode, and a second instance at the
106 start of the next supernode (to handle the return). */
107
108class supergraph : public digraph<supergraph_traits>
109{
110public:
113
115 {
117 }
118
120 {
122 }
123
125 {
126 return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
127 }
128
129 /* Get the supernode containing the second half of the gcall *
130 at an interprocedural call, within the caller. */
132 {
133 return (*const_cast <cgraph_edge_to_node_t &>
135 }
136
142
148
154
156 {
157 return (*const_cast <cfg_edge_to_cfg_superedge_t &>
159 }
160
162 {
163 return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get
164 (const_cast <gimple *> (stmt)));
165 }
166
167 void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const;
168 void dump_dot_to_file (FILE *fp, const dump_args_t &) const;
169 void dump_dot (const char *path, const dump_args_t &) const;
170
172
173 int num_nodes () const { return m_nodes.length (); }
174 int num_edges () const { return m_edges.length (); }
175
177 {
178 return m_nodes[idx];
179 }
180
181 unsigned get_num_snodes (const function *fun) const
182 {
185 return *map.get (fun);
186 }
187
188private:
189 supernode *add_node (function *fun, basic_block bb, gcall *returning_call,
196
197 /* Data. */
198
202
206
210
214
218
222
225
228
230};
231
232/* A node within a supergraph. */
233
234class supernode : public dnode<supergraph_traits>
235{
236 public:
237 supernode (function *fun, basic_block bb, gcall *returning_call,
238 gimple_seq phi_nodes, int index)
239 : m_fun (fun), m_bb (bb), m_returning_call (returning_call),
240 m_phi_nodes (phi_nodes), m_index (index)
241 {}
242
243 function *get_function () const { return m_fun; }
244
245 bool entry_p () const
246 {
248 }
249
250 bool return_p () const
251 {
252 return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
253 }
254
255 void dump_dot (graphviz_out *gv, const dump_args_t &args) const override;
256 void dump_dot_id (pretty_printer *pp) const;
257
259
262
263 /* Returns iterator at the start of the list of phi nodes, if any. */
265 {
267
268 /* Adapted from gsi_start_1. */
270
272 i.seq = pseq;
273 i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
274
275 return i;
276 }
277
279 {
280 return m_returning_call;
281 }
282
284 {
285 if (m_stmts.length () == 0)
286 return NULL;
287 return m_stmts[m_stmts.length () - 1];
288 }
289
291 {
292 gimple *stmt = get_last_stmt ();
293 if (stmt == NULL)
294 return NULL;
295 return dyn_cast<gcall *> (stmt);
296 }
297
298 unsigned int get_stmt_index (const gimple *stmt) const;
299
300 tree get_label () const;
301
302 function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
304 gcall * const m_returning_call; // for handling the result of a returned call
305 gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
307 const int m_index; /* unique within the supergraph as a whole. */
308};
309
310/* An abstract base class encapsulating an edge within a supergraph.
311 Edges can be CFG edges, or calls/returns for callgraph edges. */
312
313class superedge : public dedge<supergraph_traits>
314{
315 public:
316 virtual ~superedge () {}
317
318 void dump (pretty_printer *pp) const;
319 void dump () const;
320 void dump_dot (graphviz_out *gv, const dump_args_t &args)
321 const final override;
322
324 bool user_facing) const = 0;
325
327
328 enum edge_kind get_kind () const { return m_kind; }
329
331 virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
332 virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
334 virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
336 virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
338 virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
339
342
344
345 protected:
346 superedge (supernode *src, supernode *dest, enum edge_kind kind)
347 : dedge<supergraph_traits> (src, dest),
348 m_kind (kind)
349 {}
350
351 public:
352 const enum edge_kind m_kind;
353};
354
355/* An ID representing an expression at a callsite:
356 either a parameter index, or the return value (or unknown). */
357
359{
360 public:
361 callsite_expr () : m_val (-1) {}
362
364 {
365 return callsite_expr (idx + 1);
366 }
367
369 {
370 return callsite_expr (0);
371 }
372
373 bool param_p () const
374 {
375 return m_val > 0;
376 }
377
378 bool return_value_p () const
379 {
380 return m_val == 0;
381 }
382
383 private:
384 callsite_expr (int val) : m_val (val) {}
385
386 int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown". */
387};
388
389/* A subclass of superedge with an associated callgraph edge (either a
390 call or a return). */
391
393{
394 public:
397 : superedge (src, dst, kind),
398 m_cedge (cedge)
399 {}
400
402 final override;
403
405 {
406 return this;
407 }
409 final override
410 {
411 return this;
412 }
413
422 callsite_expr *out) const;
424 callsite_expr *out) const;
425
427};
428
429} // namespace ana
430
431template <>
432template <>
433inline bool
435{
436 return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
437 || sedge->get_kind () == SUPEREDGE_CALL
438 || sedge->get_kind () == SUPEREDGE_RETURN);
439}
440
441namespace ana {
442
443/* A subclass of superedge representing an interprocedural call. */
444
446{
447 public:
451
453 {
454 return this;
455 }
457 {
458 return this;
459 }
460
462 {
463 return sg.get_edge_for_return (m_cedge);
464 }
465};
466
467} // namespace ana
468
469template <>
470template <>
471inline bool
476
477namespace ana {
478
479/* A subclass of superedge represesnting an interprocedural return. */
480
482{
483 public:
487
490 {
491 return this;
492 }
493
495 {
496 return sg.get_edge_for_call (m_cedge);
497 }
498};
499
500} // namespace ana
501
502template <>
503template <>
504inline bool
509
510namespace ana {
511
512/* A subclass of superedge that corresponds to a CFG edge. */
513
515{
516 public:
518 : superedge (src, dst, SUPEREDGE_CFG_EDGE),
519 m_cfg_edge (e)
520 {}
521
522 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const override;
523 cfg_superedge *dyn_cast_cfg_superedge () final override { return this; }
524 const cfg_superedge *dyn_cast_cfg_superedge () const final override { return this; }
525
526 ::edge get_cfg_edge () const { return m_cfg_edge; }
527 int get_flags () const { return m_cfg_edge->flags; }
528 int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
529 int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
530 int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
531
532 size_t get_phi_arg_idx () const;
533 tree get_phi_arg (const gphi *phi) const;
534
535 location_t get_goto_locus () const { return m_cfg_edge->goto_locus; }
536
537 private:
538 const ::edge m_cfg_edge;
539};
540
541} // namespace ana
542
543template <>
544template <>
545inline bool
550
551namespace ana {
552
553/* A subclass for edges from switch statements, retaining enough
554 information to identify the pertinent cases, and for adding labels
555 when rendering via graphviz. */
556
558 public:
560
562 final override
563 {
564 return this;
565 }
566
568 final override;
569
571 {
572 return as_a <gswitch *> (m_src->get_last_stmt ());
573 }
574
575 const vec<tree> &get_case_labels () const { return m_case_labels; }
576
578
579private:
581};
582
583} // namespace ana
584
585template <>
586template <>
587inline bool
589{
590 return sedge->dyn_cast_switch_cfg_superedge () != NULL;
591}
592
593namespace ana {
594
595/* Base class for adding additional content to the .dot output
596 for a supergraph. */
597
599{
600 public:
601 virtual ~dot_annotator () {}
605 const
606 {
607 return false;
608 }
615 const
616 {
617 return false;
618 }
619};
620
623
624} // namespace ana
625
626#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:446
call_superedge * dyn_cast_call_superedge() final override
Definition supergraph.h:452
call_superedge(supernode *src, supernode *dst, cgraph_edge *cedge)
Definition supergraph.h:448
const call_superedge * dyn_cast_call_superedge() const final override
Definition supergraph.h:456
return_superedge * get_edge_for_return(const supergraph &sg) const
Definition supergraph.h:461
Definition supergraph.h:393
tree map_expr_from_callee_to_caller(tree callee_expr, callsite_expr *out) const
tree get_arg_for_parm(tree parm, callsite_expr *out) const
function * get_caller_function() const
tree get_callee_decl() const
callgraph_superedge(supernode *src, supernode *dst, enum edge_kind kind, cgraph_edge *cedge)
Definition supergraph.h:395
gcall * get_call_stmt() const
cgraph_edge *const m_cedge
Definition supergraph.h:426
callgraph_superedge * dyn_cast_callgraph_superedge() final override
Definition supergraph.h:404
tree map_expr_from_caller_to_callee(tree caller_expr, callsite_expr *out) const
tree get_parm_for_arg(tree arg, callsite_expr *out) const
function * get_callee_function() const
tree get_caller_decl() const
void dump_label_to_pp(pretty_printer *pp, bool user_facing) const final override
const callgraph_superedge * dyn_cast_callgraph_superedge() const final override
Definition supergraph.h:408
Definition supergraph.h:359
static callsite_expr from_zero_based_param(int idx)
Definition supergraph.h:363
callsite_expr()
Definition supergraph.h:361
int m_val
Definition supergraph.h:386
static callsite_expr from_return_value()
Definition supergraph.h:368
bool return_value_p() const
Definition supergraph.h:378
callsite_expr(int val)
Definition supergraph.h:384
bool param_p() const
Definition supergraph.h:373
Definition supergraph.h:515
const ::edge m_cfg_edge
Definition supergraph.h:538
int true_value_p() const
Definition supergraph.h:528
location_t get_goto_locus() const
Definition supergraph.h:535
void dump_label_to_pp(pretty_printer *pp, bool user_facing) const override
size_t get_phi_arg_idx() const
cfg_superedge * dyn_cast_cfg_superedge() final override
Definition supergraph.h:523
int get_flags() const
Definition supergraph.h:527
int back_edge_p() const
Definition supergraph.h:530
cfg_superedge(supernode *src, supernode *dst, ::edge e)
Definition supergraph.h:517
const cfg_superedge * dyn_cast_cfg_superedge() const final override
Definition supergraph.h:524
tree get_phi_arg(const gphi *phi) const
::edge get_cfg_edge() const
Definition supergraph.h:526
int false_value_p() const
Definition supergraph.h:529
Definition supergraph.h:599
virtual bool add_node_annotations(graphviz_out *gv, const supernode &n, bool within_table) const
Definition supergraph.h:602
virtual void add_stmt_annotations(graphviz_out *gv, const gimple *stmt, bool within_row) const
Definition supergraph.h:609
virtual bool add_after_node_annotations(graphviz_out *gv, const supernode &n) const
Definition supergraph.h:613
virtual ~dot_annotator()
Definition supergraph.h:601
Definition analyzer-logging.h:34
Definition supergraph.h:482
call_superedge * get_edge_for_call(const supergraph &sg) const
Definition supergraph.h:494
return_superedge * dyn_cast_return_superedge() final override
Definition supergraph.h:488
return_superedge(supernode *src, supernode *dst, cgraph_edge *cedge)
Definition supergraph.h:484
const return_superedge * dyn_cast_return_superedge() const final override
Definition supergraph.h:489
Definition supergraph.h:92
void restore_uids() const
void make_uid_unique(gimple *stmt)
auto_vec< std::pair< gimple *, unsigned > > m_old_stmt_uids
Definition supergraph.h:98
Definition supergraph.h:314
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
cgraph_edge * get_any_callgraph_edge() const
enum edge_kind get_kind() const
Definition supergraph.h:328
void dump(pretty_printer *pp) const
::edge get_any_cfg_edge() const
virtual return_superedge * dyn_cast_return_superedge()
Definition supergraph.h:337
virtual const callgraph_superedge * dyn_cast_callgraph_superedge() const
Definition supergraph.h:334
superedge(supernode *src, supernode *dest, enum edge_kind kind)
Definition supergraph.h:346
virtual const switch_cfg_superedge * dyn_cast_switch_cfg_superedge() const
Definition supergraph.h:332
virtual callgraph_superedge * dyn_cast_callgraph_superedge()
Definition supergraph.h:333
virtual cfg_superedge * dyn_cast_cfg_superedge()
Definition supergraph.h:330
virtual const cfg_superedge * dyn_cast_cfg_superedge() const
Definition supergraph.h:331
label_text get_description(bool user_facing) const
enum edge_kind m_kind
Definition supergraph.h:352
virtual ~superedge()
Definition supergraph.h:316
virtual const call_superedge * dyn_cast_call_superedge() const
Definition supergraph.h:336
void dump() const
json::object * to_json() const
virtual void dump_label_to_pp(pretty_printer *pp, bool user_facing) const =0
virtual call_superedge * dyn_cast_call_superedge()
Definition supergraph.h:335
virtual const return_superedge * dyn_cast_return_superedge() const
Definition supergraph.h:338
Definition supergraph.h:109
ordered_hash_map< cgraph_edge *, return_superedge * > cgraph_edge_to_return_superedge_t
Definition supergraph.h:216
cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge
Definition supergraph.h:213
supernode * get_caller_next_node(cgraph_edge *edge) const
Definition supergraph.h:131
int num_edges() const
Definition supergraph.h:174
stmt_to_node_t m_stmt_to_node_t
Definition supergraph.h:224
supergraph(logger *logger)
ordered_hash_map< ::edge, cfg_superedge * > cfg_edge_to_cfg_superedge_t
Definition supergraph.h:208
unsigned get_num_snodes(const function *fun) const
Definition supergraph.h:181
cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge
Definition supergraph.h:221
cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node
Definition supergraph.h:205
int num_nodes() const
Definition supergraph.h:173
supernode * get_node_for_function_exit(const function &fun) const
Definition supergraph.h:119
superedge * get_intraprocedural_edge_for_call(cgraph_edge *edge) const
Definition supergraph.h:149
bb_to_node_t m_bb_to_final_node
Definition supergraph.h:201
ordered_hash_map< cgraph_edge *, supernode * > cgraph_edge_to_node_t
Definition supergraph.h:203
ordered_hash_map< cgraph_edge *, superedge * > cgraph_edge_to_intraproc_superedge_t
Definition supergraph.h:220
supernode * get_node_for_block(basic_block bb) const
Definition supergraph.h:124
ordered_hash_map< cgraph_edge *, call_superedge * > cgraph_edge_to_call_superedge_t
Definition supergraph.h:212
cfg_superedge * add_cfg_edge(supernode *src, supernode *dest, ::edge e)
cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge
Definition supergraph.h:209
supernode * get_node_by_index(int idx) const
Definition supergraph.h:176
return_superedge * add_return_superedge(supernode *src, supernode *dest, cgraph_edge *cedge)
void dump_dot_to_pp(pretty_printer *pp, const dump_args_t &) const
ordered_hash_map< basic_block, supernode * > bb_to_node_t
Definition supergraph.h:199
supernode * get_node_for_function_entry(const function &fun) const
Definition supergraph.h:114
function_to_num_snodes_t m_function_to_num_snodes
Definition supergraph.h:227
hash_map< const function *, unsigned > function_to_num_snodes_t
Definition supergraph.h:226
cfg_superedge * get_edge_for_cfg_edge(edge e) const
Definition supergraph.h:155
call_superedge * add_call_superedge(supernode *src, supernode *dest, cgraph_edge *cedge)
bb_to_node_t m_bb_to_initial_node
Definition supergraph.h:200
supernode * get_supernode_for_stmt(const gimple *stmt) const
Definition supergraph.h:161
ordered_hash_map< gimple *, supernode * > stmt_to_node_t
Definition supergraph.h:223
void dump_dot_to_file(FILE *fp, const dump_args_t &) const
cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge
Definition supergraph.h:217
call_superedge * get_edge_for_call(cgraph_edge *edge) const
Definition supergraph.h:137
void dump_dot(const char *path, const dump_args_t &) const
return_superedge * get_edge_for_return(cgraph_edge *edge) const
Definition supergraph.h:143
json::object * to_json() const
supernode * add_node(function *fun, basic_block bb, gcall *returning_call, gimple_seq phi_nodes)
saved_uids m_stmt_uids
Definition supergraph.h:229
cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node
Definition supergraph.h:204
Definition supergraph.h:235
bool entry_p() const
Definition supergraph.h:245
gimple * get_last_stmt() const
Definition supergraph.h:283
gcall * get_final_call() const
Definition supergraph.h:290
location_t get_end_location() const
gphi_iterator start_phis()
Definition supergraph.h:264
json::object * to_json() const
const basic_block m_bb
Definition supergraph.h:303
void dump_dot_id(pretty_printer *pp) const
gcall * get_returning_call() const
Definition supergraph.h:278
bool return_p() const
Definition supergraph.h:250
tree get_label() const
location_t get_start_location() const
void dump_dot(graphviz_out *gv, const dump_args_t &args) const override
gcall *const m_returning_call
Definition supergraph.h:304
unsigned int get_stmt_index(const gimple *stmt) const
function * get_function() const
Definition supergraph.h:243
supernode(function *fun, basic_block bb, gcall *returning_call, gimple_seq phi_nodes, int index)
Definition supergraph.h:237
const int m_index
Definition supergraph.h:307
auto_vec< gimple * > m_stmts
Definition supergraph.h:306
gimple_seq m_phi_nodes
Definition supergraph.h:305
function *const m_fun
Definition supergraph.h:302
Definition supergraph.h:557
bool implicitly_created_default_p() const
const switch_cfg_superedge * dyn_cast_switch_cfg_superedge() const final override
Definition supergraph.h:561
const vec< tree > & get_case_labels() const
Definition supergraph.h:575
switch_cfg_superedge(supernode *src, supernode *dst, ::edge e)
void dump_label_to_pp(pretty_printer *pp, bool user_facing) const final override
gswitch * get_switch_stmt() const
Definition supergraph.h:570
auto_vec< tree > m_case_labels
Definition supergraph.h:580
Definition vec.h:1656
Definition cgraph.h:1696
Definition digraph.h:59
node_t *const m_src
Definition digraph.h:71
GraphTraits::dump_args_t dump_args_t
Definition digraph.h:62
Definition digraph.h:81
auto_delete_vec< edge_t > m_edges
Definition digraph.h:105
auto_delete_vec< node_t > m_nodes
Definition digraph.h:104
GraphTraits::dump_args_t dump_args_t
Definition digraph.h:85
Definition digraph.h:43
GraphTraits::dump_args_t dump_args_t
Definition digraph.h:46
Definition graphviz.h:29
Definition json.h:95
Definition pretty-print.h:244
class edge_def * edge
Definition coretypes.h:342
union tree_node * tree
Definition coretypes.h:97
static struct string2counter_map map[debug_counter_number_of_counters]
Definition dbgcnt.cc:39
void final(rtx_insn *first, FILE *file, int optimize_p)
Definition final.cc:2002
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
gimple_seq phi_nodes(const_basic_block bb)
Definition gimple.h:4642
basic_block gimple_bb(const gimple *g)
Definition gimple.h:1859
gimple_seq_node gimple_seq_first(gimple_seq s)
Definition gimple.h:1683
Definition access-diagram.h:30
function * get_ultimate_function_for_cgraph_edge(cgraph_edge *edge)
supergraph_dot_flags
Definition supergraph.h:63
@ SUPERGRAPH_DOT_SHOW_BBS
Definition supergraph.h:64
cgraph_edge * supergraph_call_edge(function *fun, const gimple *stmt)
edge_kind
Definition supergraph.h:53
@ SUPEREDGE_RETURN
Definition supergraph.h:56
@ SUPEREDGE_CALL
Definition supergraph.h:55
@ SUPEREDGE_CFG_EDGE
Definition supergraph.h:54
@ SUPEREDGE_INTRAPROCEDURAL_CALL
Definition supergraph.h:57
i
Definition poly-int.h:772
Definition supergraph.h:76
dump_args_t(enum supergraph_dot_flags flags, const dot_annotator *node_annotator)
Definition supergraph.h:77
const dot_annotator * m_node_annotator
Definition supergraph.h:84
enum supergraph_dot_flags m_flags
Definition supergraph.h:83
Definition supergraph.h:71
supercluster cluster_t
Definition supergraph.h:86
supernode node_t
Definition supergraph.h:72
supergraph graph_t
Definition supergraph.h:74
superedge edge_t
Definition supergraph.h:73
Definition basic-block.h:117
Definition function.h:249
Definition gimple.h:352
gimple_seq_node ptr
Definition gimple-iterator.h:30
Definition gimple.h:225
Definition gimple-iterator.h:42
Definition gimple.h:461
Definition gimple.h:894
static bool test(U *p)
Definition vec.h:450
#define NULL
Definition system.h:50