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;
40 class callgraph_superedge;
41 class call_superedge;
42 class return_superedge;
43 class cfg_superedge;
44 class switch_cfg_superedge;
45class supercluster;
46class dot_annotator;
47
48class logger;
49
50/* An enum for discriminating between superedge subclasses. */
51
52enum edge_kind
53{
54 SUPEREDGE_CFG_EDGE,
55 SUPEREDGE_CALL,
56 SUPEREDGE_RETURN,
57 SUPEREDGE_INTRAPROCEDURAL_CALL
58};
59
60/* Flags for controlling the appearance of .dot dumps. */
61
62enum supergraph_dot_flags
63{
64 SUPERGRAPH_DOT_SHOW_BBS = (1 << 0)
65};
66
67/* A traits struct describing the family of node, edge and digraph
68 classes for supergraphs. */
69
70struct supergraph_traits
71{
72 typedef supernode node_t;
73 typedef superedge edge_t;
74 typedef supergraph graph_t;
75 struct dump_args_t
76 {
77 dump_args_t (enum supergraph_dot_flags flags,
78 const dot_annotator *node_annotator)
79 : m_flags (flags),
80 m_node_annotator (node_annotator)
81 {}
82
83 enum supergraph_dot_flags m_flags;
84 const dot_annotator *m_node_annotator;
85 };
86 typedef supercluster cluster_t;
87};
88
89/* A class to manage the setting and restoring of statement uids. */
90
91class saved_uids
92{
93public:
94 void make_uid_unique (gimple *stmt);
95 void restore_uids () const;
96
97private:
98 auto_vec<std::pair<gimple *, unsigned> > m_old_stmt_uids;
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:
111 supergraph (logger *logger);
112 ~supergraph ();
113
114 supernode *get_node_for_function_entry (const function &fun) const
115 {
116 return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (&fun));
117 }
118
119 supernode *get_node_for_function_exit (const function &fun) const
120 {
121 return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (&fun));
122 }
123
124 supernode *get_node_for_block (basic_block bb) const
125 {
126 return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (k: bb);
127 }
128
129 /* Get the supernode containing the second half of the gcall *
130 at an interprocedural call, within the caller. */
131 supernode *get_caller_next_node (cgraph_edge *edge) const
132 {
133 return (*const_cast <cgraph_edge_to_node_t &>
134 (m_cgraph_edge_to_caller_next_node).get (k: edge));
135 }
136
137 call_superedge *get_edge_for_call (cgraph_edge *edge) const
138 {
139 return (*const_cast <cgraph_edge_to_call_superedge_t &>
140 (m_cgraph_edge_to_call_superedge).get (k: edge));
141 }
142
143 return_superedge *get_edge_for_return (cgraph_edge *edge) const
144 {
145 return (*const_cast <cgraph_edge_to_return_superedge_t &>
146 (m_cgraph_edge_to_return_superedge).get (k: edge));
147 }
148
149 superedge *get_intraprocedural_edge_for_call (cgraph_edge *edge) const
150 {
151 return (*const_cast <cgraph_edge_to_intraproc_superedge_t &>
152 (m_cgraph_edge_to_intraproc_superedge).get (k: edge));
153 }
154
155 cfg_superedge *get_edge_for_cfg_edge (edge e) const
156 {
157 return (*const_cast <cfg_edge_to_cfg_superedge_t &>
158 (m_cfg_edge_to_cfg_superedge).get (k: e));
159 }
160
161 supernode *get_supernode_for_stmt (const gimple *stmt) const
162 {
163 return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get
164 (k: 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
171 json::object *to_json () const;
172
173 int num_nodes () const { return m_nodes.length (); }
174 int num_edges () const { return m_edges.length (); }
175
176 supernode *get_node_by_index (int idx) const
177 {
178 return m_nodes[idx];
179 }
180
181 unsigned get_num_snodes (const function *fun) const
182 {
183 function_to_num_snodes_t &map
184 = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
185 return *map.get (k: fun);
186 }
187
188private:
189 supernode *add_node (function *fun, basic_block bb, gcall *returning_call,
190 gimple_seq phi_nodes);
191 cfg_superedge *add_cfg_edge (supernode *src, supernode *dest, ::edge e);
192 call_superedge *add_call_superedge (supernode *src, supernode *dest,
193 cgraph_edge *cedge);
194 return_superedge *add_return_superedge (supernode *src, supernode *dest,
195 cgraph_edge *cedge);
196
197 /* Data. */
198
199 typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t;
200 bb_to_node_t m_bb_to_initial_node;
201 bb_to_node_t m_bb_to_final_node;
202
203 typedef ordered_hash_map<cgraph_edge *, supernode *> cgraph_edge_to_node_t;
204 cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node;
205 cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node;
206
207 typedef ordered_hash_map< ::edge, cfg_superedge *>
208 cfg_edge_to_cfg_superedge_t;
209 cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge;
210
211 typedef ordered_hash_map<cgraph_edge *, call_superedge *>
212 cgraph_edge_to_call_superedge_t;
213 cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge;
214
215 typedef ordered_hash_map<cgraph_edge *, return_superedge *>
216 cgraph_edge_to_return_superedge_t;
217 cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge;
218
219 typedef ordered_hash_map<cgraph_edge *, superedge *>
220 cgraph_edge_to_intraproc_superedge_t;
221 cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge;
222
223 typedef ordered_hash_map<gimple *, supernode *> stmt_to_node_t;
224 stmt_to_node_t m_stmt_to_node_t;
225
226 typedef hash_map<const function *, unsigned> function_to_num_snodes_t;
227 function_to_num_snodes_t m_function_to_num_snodes;
228
229 saved_uids m_stmt_uids;
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 {
247 return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
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
258 json::object *to_json () const;
259
260 location_t get_start_location () const;
261 location_t get_end_location () const;
262
263 /* Returns iterator at the start of the list of phi nodes, if any. */
264 gphi_iterator start_phis ()
265 {
266 gimple_seq *pseq = &m_phi_nodes;
267
268 /* Adapted from gsi_start_1. */
269 gphi_iterator i;
270
271 i.ptr = gimple_seq_first (s: *pseq);
272 i.seq = pseq;
273 i.bb = i.ptr ? gimple_bb (g: i.ptr) : NULL;
274
275 return i;
276 }
277
278 gcall *get_returning_call () const
279 {
280 return m_returning_call;
281 }
282
283 gimple *get_last_stmt () const
284 {
285 if (m_stmts.length () == 0)
286 return NULL;
287 return m_stmts[m_stmts.length () - 1];
288 }
289
290 gcall *get_final_call () const
291 {
292 gimple *stmt = get_last_stmt ();
293 if (stmt == NULL)
294 return NULL;
295 return dyn_cast<gcall *> (p: 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
303 const basic_block m_bb;
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
306 auto_vec<gimple *> m_stmts;
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
323 virtual void dump_label_to_pp (pretty_printer *pp,
324 bool user_facing) const = 0;
325
326 json::object *to_json () const;
327
328 enum edge_kind get_kind () const { return m_kind; }
329
330 virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
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; }
333 virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
334 virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
335 virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
336 virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
337 virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
338 virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
339
340 ::edge get_any_cfg_edge () const;
341 cgraph_edge *get_any_callgraph_edge () const;
342
343 label_text get_description (bool user_facing) const;
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
358class callsite_expr
359{
360 public:
361 callsite_expr () : m_val (-1) {}
362
363 static callsite_expr from_zero_based_param (int idx)
364 {
365 return callsite_expr (idx + 1);
366 }
367
368 static callsite_expr from_return_value ()
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
392class callgraph_superedge : public superedge
393{
394 public:
395 callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
396 cgraph_edge *cedge)
397 : superedge (src, dst, kind),
398 m_cedge (cedge)
399 {}
400
401 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
402 final override;
403
404 callgraph_superedge *dyn_cast_callgraph_superedge () final override
405 {
406 return this;
407 }
408 const callgraph_superedge *dyn_cast_callgraph_superedge () const
409 final override
410 {
411 return this;
412 }
413
414 function *get_callee_function () const;
415 function *get_caller_function () const;
416 tree get_callee_decl () const;
417 tree get_caller_decl () const;
418 gcall *get_call_stmt () const;
419 tree get_arg_for_parm (tree parm, callsite_expr *out) const;
420 tree get_parm_for_arg (tree arg, callsite_expr *out) const;
421 tree map_expr_from_caller_to_callee (tree caller_expr,
422 callsite_expr *out) const;
423 tree map_expr_from_callee_to_caller (tree callee_expr,
424 callsite_expr *out) const;
425
426 cgraph_edge *const m_cedge;
427};
428
429} // namespace ana
430
431template <>
432template <>
433inline bool
434is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
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
445class call_superedge : public callgraph_superedge
446{
447 public:
448 call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
449 : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
450 {}
451
452 call_superedge *dyn_cast_call_superedge () final override
453 {
454 return this;
455 }
456 const call_superedge *dyn_cast_call_superedge () const final override
457 {
458 return this;
459 }
460
461 return_superedge *get_edge_for_return (const supergraph &sg) const
462 {
463 return sg.get_edge_for_return (edge: m_cedge);
464 }
465};
466
467} // namespace ana
468
469template <>
470template <>
471inline bool
472is_a_helper <const call_superedge *>::test (const superedge *sedge)
473{
474 return sedge->get_kind () == SUPEREDGE_CALL;
475}
476
477namespace ana {
478
479/* A subclass of superedge represesnting an interprocedural return. */
480
481class return_superedge : public callgraph_superedge
482{
483 public:
484 return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
485 : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
486 {}
487
488 return_superedge *dyn_cast_return_superedge () final override { return this; }
489 const return_superedge *dyn_cast_return_superedge () const final override
490 {
491 return this;
492 }
493
494 call_superedge *get_edge_for_call (const supergraph &sg) const
495 {
496 return sg.get_edge_for_call (edge: m_cedge);
497 }
498};
499
500} // namespace ana
501
502template <>
503template <>
504inline bool
505is_a_helper <const return_superedge *>::test (const superedge *sedge)
506{
507 return sedge->get_kind () == SUPEREDGE_RETURN;
508}
509
510namespace ana {
511
512/* A subclass of superedge that corresponds to a CFG edge. */
513
514class cfg_superedge : public superedge
515{
516 public:
517 cfg_superedge (supernode *src, supernode *dst, ::edge e)
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
546is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
547{
548 return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
549}
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
557class switch_cfg_superedge : public cfg_superedge {
558 public:
559 switch_cfg_superedge (supernode *src, supernode *dst, ::edge e);
560
561 const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
562 final override
563 {
564 return this;
565 }
566
567 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
568 final override;
569
570 gswitch *get_switch_stmt () const
571 {
572 return as_a <gswitch *> (p: m_src->get_last_stmt ());
573 }
574
575 const vec<tree> &get_case_labels () const { return m_case_labels; }
576
577 bool implicitly_created_default_p () const;
578
579private:
580 auto_vec<tree> m_case_labels;
581};
582
583} // namespace ana
584
585template <>
586template <>
587inline bool
588is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
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
598class dot_annotator
599{
600 public:
601 virtual ~dot_annotator () {}
602 virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
603 const supernode &n ATTRIBUTE_UNUSED,
604 bool within_table ATTRIBUTE_UNUSED)
605 const
606 {
607 return false;
608 }
609 virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
610 const gimple *stmt ATTRIBUTE_UNUSED,
611 bool within_row ATTRIBUTE_UNUSED)
612 const {}
613 virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
614 const supernode &n ATTRIBUTE_UNUSED)
615 const
616 {
617 return false;
618 }
619};
620
621extern cgraph_edge *supergraph_call_edge (function *fun, const gimple *stmt);
622extern function *get_ultimate_function_for_cgraph_edge (cgraph_edge *edge);
623
624} // namespace ana
625
626#endif /* GCC_ANALYZER_SUPERGRAPH_H */
627

source code of gcc/analyzer/supergraph.h