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 | |
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 (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 | |
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 (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 | |
313 | class 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 | |
358 | class 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 | |
392 | class 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 | |
431 | template <> |
432 | template <> |
433 | inline bool |
434 | is_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 | |
441 | namespace ana { |
442 | |
443 | /* A subclass of superedge representing an interprocedural call. */ |
444 | |
445 | class 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 | |
469 | template <> |
470 | template <> |
471 | inline bool |
472 | is_a_helper <const call_superedge *>::test (const superedge *sedge) |
473 | { |
474 | return sedge->get_kind () == SUPEREDGE_CALL; |
475 | } |
476 | |
477 | namespace ana { |
478 | |
479 | /* A subclass of superedge represesnting an interprocedural return. */ |
480 | |
481 | class 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 | |
502 | template <> |
503 | template <> |
504 | inline bool |
505 | is_a_helper <const return_superedge *>::test (const superedge *sedge) |
506 | { |
507 | return sedge->get_kind () == SUPEREDGE_RETURN; |
508 | } |
509 | |
510 | namespace ana { |
511 | |
512 | /* A subclass of superedge that corresponds to a CFG edge. */ |
513 | |
514 | class 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 | |
543 | template <> |
544 | template <> |
545 | inline bool |
546 | is_a_helper <const cfg_superedge *>::test (const superedge *sedge) |
547 | { |
548 | return sedge->get_kind () == SUPEREDGE_CFG_EDGE; |
549 | } |
550 | |
551 | namespace 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 | |
557 | class 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 | |
579 | private: |
580 | auto_vec<tree> m_case_labels; |
581 | }; |
582 | |
583 | } // namespace ana |
584 | |
585 | template <> |
586 | template <> |
587 | inline bool |
588 | is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge) |
589 | { |
590 | return sedge->dyn_cast_switch_cfg_superedge () != NULL; |
591 | } |
592 | |
593 | namespace ana { |
594 | |
595 | /* Base class for adding additional content to the .dot output |
596 | for a supergraph. */ |
597 | |
598 | class 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 | |
621 | extern cgraph_edge *supergraph_call_edge (function *fun, const gimple *stmt); |
622 | extern function *get_ultimate_function_for_cgraph_edge (cgraph_edge *edge); |
623 | |
624 | } // namespace ana |
625 | |
626 | #endif /* GCC_ANALYZER_SUPERGRAPH_H */ |
627 | |