1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 Copyright (C) 2019-2023 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 "gimple.h"
28 #include "gimple-iterator.h"
29 #include "digraph.h"
30
31 using namespace ana;
32
33 namespace ana {
34
35 /* Forward decls, using indentation to show inheritance. */
36
37 class supergraph;
38 class supernode;
39 class superedge;
40 class callgraph_superedge;
41 class call_superedge;
42 class return_superedge;
43 class cfg_superedge;
44 class switch_cfg_superedge;
45 class supercluster;
46 class dot_annotator;
47
48 class logger;
49
50 /* An enum for discriminating between superedge subclasses. */
51
52 enum 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
62 enum 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
70 struct 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
91 class saved_uids
92 {
93 public:
94 void make_uid_unique (gimple *stmt);
95 void restore_uids () const;
96
97 private:
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
108 class supergraph : public digraph<supergraph_traits>
109 {
110 public:
111 supergraph (logger *logger);
112 ~supergraph ();
113
114 supernode *get_node_for_function_entry (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 (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 (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 (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 (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 (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 (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 (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 (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 (fun);
186 }
187
188 private:
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
234 class 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 (*pseq);
272 i.seq = pseq;
273 i.bb = i.ptr ? gimple_bb (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 *> (stmt);
296 }
297
298 unsigned int get_stmt_index (const gimple *stmt) const;
299
300 function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
301 const basic_block m_bb;
302 gcall * const m_returning_call; // for handling the result of a returned call
303 gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
304 auto_vec<gimple *> m_stmts;
305 const int m_index; /* unique within the supergraph as a whole. */
306 };
307
308 /* An abstract base class encapsulating an edge within a supergraph.
309 Edges can be CFG edges, or calls/returns for callgraph edges. */
310
311 class superedge : public dedge<supergraph_traits>
312 {
313 public:
314 virtual ~superedge () {}
315
316 void dump (pretty_printer *pp) const;
317 void dump () const;
318 void dump_dot (graphviz_out *gv, const dump_args_t &args)
319 const final override;
320
321 virtual void dump_label_to_pp (pretty_printer *pp,
322 bool user_facing) const = 0;
323
324 json::object *to_json () const;
325
326 enum edge_kind get_kind () const { return m_kind; }
327
328 virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
329 virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
330 virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
331 virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
332 virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
333 virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
334 virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
335 virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
336 virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
337
338 ::edge get_any_cfg_edge () const;
339 cgraph_edge *get_any_callgraph_edge () const;
340
341 label_text get_description (bool user_facing) const;
342
343 protected:
344 superedge (supernode *src, supernode *dest, enum edge_kind kind)
345 : dedge<supergraph_traits> (src, dest),
346 m_kind (kind)
347 {}
348
349 public:
350 const enum edge_kind m_kind;
351 };
352
353 /* An ID representing an expression at a callsite:
354 either a parameter index, or the return value (or unknown). */
355
356 class callsite_expr
357 {
358 public:
359 callsite_expr () : m_val (-1) {}
360
361 static callsite_expr from_zero_based_param (int idx)
362 {
363 return callsite_expr (idx + 1);
364 }
365
366 static callsite_expr from_return_value ()
367 {
368 return callsite_expr (0);
369 }
370
371 bool param_p () const
372 {
373 return m_val > 0;
374 }
375
376 bool return_value_p () const
377 {
378 return m_val == 0;
379 }
380
381 private:
382 callsite_expr (int val) : m_val (val) {}
383
384 int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown". */
385 };
386
387 /* A subclass of superedge with an associated callgraph edge (either a
388 call or a return). */
389
390 class callgraph_superedge : public superedge
391 {
392 public:
393 callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
394 cgraph_edge *cedge)
395 : superedge (src, dst, kind),
396 m_cedge (cedge)
397 {}
398
399 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
400 final override;
401
402 callgraph_superedge *dyn_cast_callgraph_superedge () final override
403 {
404 return this;
405 }
406 const callgraph_superedge *dyn_cast_callgraph_superedge () const
407 final override
408 {
409 return this;
410 }
411
412 function *get_callee_function () const;
413 function *get_caller_function () const;
414 tree get_callee_decl () const;
415 tree get_caller_decl () const;
416 gcall *get_call_stmt () const;
417 tree get_arg_for_parm (tree parm, callsite_expr *out) const;
418 tree get_parm_for_arg (tree arg, callsite_expr *out) const;
419 tree map_expr_from_caller_to_callee (tree caller_expr,
420 callsite_expr *out) const;
421 tree map_expr_from_callee_to_caller (tree callee_expr,
422 callsite_expr *out) const;
423
424 cgraph_edge *const m_cedge;
425 };
426
427 } // namespace ana
428
429 template <>
430 template <>
431 inline bool
432 is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
433 {
434 return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
435 || sedge->get_kind () == SUPEREDGE_CALL
436 || sedge->get_kind () == SUPEREDGE_RETURN);
437 }
438
439 namespace ana {
440
441 /* A subclass of superedge representing an interprocedural call. */
442
443 class call_superedge : public callgraph_superedge
444 {
445 public:
446 call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
447 : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
448 {}
449
450 call_superedge *dyn_cast_call_superedge () final override
451 {
452 return this;
453 }
454 const call_superedge *dyn_cast_call_superedge () const final override
455 {
456 return this;
457 }
458
459 return_superedge *get_edge_for_return (const supergraph &sg) const
460 {
461 return sg.get_edge_for_return (m_cedge);
462 }
463 };
464
465 } // namespace ana
466
467 template <>
468 template <>
469 inline bool
470 is_a_helper <const call_superedge *>::test (const superedge *sedge)
471 {
472 return sedge->get_kind () == SUPEREDGE_CALL;
473 }
474
475 namespace ana {
476
477 /* A subclass of superedge represesnting an interprocedural return. */
478
479 class return_superedge : public callgraph_superedge
480 {
481 public:
482 return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
483 : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
484 {}
485
486 return_superedge *dyn_cast_return_superedge () final override { return this; }
487 const return_superedge *dyn_cast_return_superedge () const final override
488 {
489 return this;
490 }
491
492 call_superedge *get_edge_for_call (const supergraph &sg) const
493 {
494 return sg.get_edge_for_call (m_cedge);
495 }
496 };
497
498 } // namespace ana
499
500 template <>
501 template <>
502 inline bool
503 is_a_helper <const return_superedge *>::test (const superedge *sedge)
504 {
505 return sedge->get_kind () == SUPEREDGE_RETURN;
506 }
507
508 namespace ana {
509
510 /* A subclass of superedge that corresponds to a CFG edge. */
511
512 class cfg_superedge : public superedge
513 {
514 public:
515 cfg_superedge (supernode *src, supernode *dst, ::edge e)
516 : superedge (src, dst, SUPEREDGE_CFG_EDGE),
517 m_cfg_edge (e)
518 {}
519
520 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const override;
521 cfg_superedge *dyn_cast_cfg_superedge () final override { return this; }
522 const cfg_superedge *dyn_cast_cfg_superedge () const final override { return this; }
523
524 ::edge get_cfg_edge () const { return m_cfg_edge; }
525 int get_flags () const { return m_cfg_edge->flags; }
526 int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
527 int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
528 int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
529
530 size_t get_phi_arg_idx () const;
531 tree get_phi_arg (const gphi *phi) const;
532
533 private:
534 const ::edge m_cfg_edge;
535 };
536
537 } // namespace ana
538
539 template <>
540 template <>
541 inline bool
542 is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
543 {
544 return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
545 }
546
547 namespace ana {
548
549 /* A subclass for edges from switch statements, retaining enough
550 information to identify the pertinent cases, and for adding labels
551 when rendering via graphviz. */
552
553 class switch_cfg_superedge : public cfg_superedge {
554 public:
555 switch_cfg_superedge (supernode *src, supernode *dst, ::edge e);
556
557 const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
558 final override
559 {
560 return this;
561 }
562
563 void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
564 final override;
565
566 gswitch *get_switch_stmt () const
567 {
568 return as_a <gswitch *> (m_src->get_last_stmt ());
569 }
570
571 const vec<tree> &get_case_labels () const { return m_case_labels; }
572
573 bool implicitly_created_default_p () const;
574
575 private:
576 auto_vec<tree> m_case_labels;
577 };
578
579 } // namespace ana
580
581 template <>
582 template <>
583 inline bool
584 is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
585 {
586 return sedge->dyn_cast_switch_cfg_superedge () != NULL;
587 }
588
589 namespace ana {
590
591 /* Base class for adding additional content to the .dot output
592 for a supergraph. */
593
594 class dot_annotator
595 {
596 public:
597 virtual ~dot_annotator () {}
598 virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
599 const supernode &n ATTRIBUTE_UNUSED,
600 bool within_table ATTRIBUTE_UNUSED)
601 const
602 {
603 return false;
604 }
605 virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
606 const gimple *stmt ATTRIBUTE_UNUSED,
607 bool within_row ATTRIBUTE_UNUSED)
608 const {}
609 virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
610 const supernode &n ATTRIBUTE_UNUSED)
611 const
612 {
613 return false;
614 }
615 };
616
617 extern cgraph_edge *supergraph_call_edge (function *fun, const gimple *stmt);
618 extern function *get_ultimate_function_for_cgraph_edge (cgraph_edge *edge);
619
620 } // namespace ana
621
622 #endif /* GCC_ANALYZER_SUPERGRAPH_H */