1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
21 #ifndef GCC_ANALYZER_SUPERGRAPH_H
22 #define GCC_ANALYZER_SUPERGRAPH_H
28 /* Forward decls, using indentation to show inheritance. */
33 class callgraph_superedge
;
35 class return_superedge
;
37 class switch_cfg_superedge
;
43 /* An enum for discriminating between superedge subclasses. */
50 SUPEREDGE_INTRAPROCEDURAL_CALL
53 /* Flags for controlling the appearance of .dot dumps. */
55 enum supergraph_dot_flags
57 SUPERGRAPH_DOT_SHOW_BBS
= (1 << 0)
60 /* A traits struct describing the family of node, edge and digraph
61 classes for supergraphs. */
63 struct supergraph_traits
65 typedef supernode node_t
;
66 typedef superedge edge_t
;
67 typedef supergraph graph_t
;
70 dump_args_t (enum supergraph_dot_flags flags
,
71 const dot_annotator
*node_annotator
)
73 m_node_annotator (node_annotator
)
76 enum supergraph_dot_flags m_flags
;
77 const dot_annotator
*m_node_annotator
;
79 typedef supercluster cluster_t
;
82 /* A "supergraph" is a directed graph formed by joining together all CFGs,
83 linking them via interprocedural call and return edges.
85 Basic blocks are split at callsites, so that a call statement occurs
86 twice: once at the end of a supernode, and a second instance at the
87 start of the next supernode (to handle the return). */
89 class supergraph
: public digraph
<supergraph_traits
>
92 supergraph (logger
*logger
);
94 supernode
*get_node_for_function_entry (function
*fun
) const
96 return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (fun
));
99 supernode
*get_node_for_function_exit (function
*fun
) const
101 return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (fun
));
104 supernode
*get_node_for_block (basic_block bb
) const
106 return *const_cast <bb_to_node_t
&> (m_bb_to_initial_node
).get (bb
);
109 /* Get the supernode containing the second half of the gcall *
110 at an interprocedural call, within the caller. */
111 supernode
*get_caller_next_node (cgraph_edge
*edge
) const
113 return (*const_cast <cgraph_edge_to_node_t
&>
114 (m_cgraph_edge_to_caller_next_node
).get (edge
));
117 call_superedge
*get_edge_for_call (cgraph_edge
*edge
) const
119 return (*const_cast <cgraph_edge_to_call_superedge_t
&>
120 (m_cgraph_edge_to_call_superedge
).get (edge
));
123 return_superedge
*get_edge_for_return (cgraph_edge
*edge
) const
125 return (*const_cast <cgraph_edge_to_return_superedge_t
&>
126 (m_cgraph_edge_to_return_superedge
).get (edge
));
129 superedge
*get_intraprocedural_edge_for_call (cgraph_edge
*edge
) const
131 return (*const_cast <cgraph_edge_to_intraproc_superedge_t
&>
132 (m_cgraph_edge_to_intraproc_superedge
).get (edge
));
135 cfg_superedge
*get_edge_for_cfg_edge (edge e
) const
137 return (*const_cast <cfg_edge_to_cfg_superedge_t
&>
138 (m_cfg_edge_to_cfg_superedge
).get (e
));
141 supernode
*get_supernode_for_stmt (const gimple
*stmt
) const
143 return (*const_cast <stmt_to_node_t
&>(m_stmt_to_node_t
).get
144 (const_cast <gimple
*> (stmt
)));
147 void dump_dot_to_pp (pretty_printer
*pp
, const dump_args_t
&) const;
148 void dump_dot_to_file (FILE *fp
, const dump_args_t
&) const;
149 void dump_dot (const char *path
, const dump_args_t
&) const;
151 json::object
*to_json () const;
153 int num_nodes () const { return m_nodes
.length (); }
154 int num_edges () const { return m_edges
.length (); }
156 supernode
*get_node_by_index (int idx
) const
161 unsigned get_num_snodes (const function
*fun
) const
163 function_to_num_snodes_t
&map
164 = const_cast <function_to_num_snodes_t
&>(m_function_to_num_snodes
);
165 return *map
.get (fun
);
169 supernode
*add_node (function
*fun
, basic_block bb
, gcall
*returning_call
,
170 gimple_seq phi_nodes
);
171 cfg_superedge
*add_cfg_edge (supernode
*src
, supernode
*dest
, ::edge e
, int idx
);
172 call_superedge
*add_call_superedge (supernode
*src
, supernode
*dest
,
174 return_superedge
*add_return_superedge (supernode
*src
, supernode
*dest
,
179 typedef ordered_hash_map
<basic_block
, supernode
*> bb_to_node_t
;
180 bb_to_node_t m_bb_to_initial_node
;
181 bb_to_node_t m_bb_to_final_node
;
183 typedef ordered_hash_map
<cgraph_edge
*, supernode
*> cgraph_edge_to_node_t
;
184 cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node
;
185 cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node
;
187 typedef ordered_hash_map
< ::edge
, cfg_superedge
*>
188 cfg_edge_to_cfg_superedge_t
;
189 cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge
;
191 typedef ordered_hash_map
<cgraph_edge
*, call_superedge
*>
192 cgraph_edge_to_call_superedge_t
;
193 cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge
;
195 typedef ordered_hash_map
<cgraph_edge
*, return_superedge
*>
196 cgraph_edge_to_return_superedge_t
;
197 cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge
;
199 typedef ordered_hash_map
<cgraph_edge
*, superedge
*>
200 cgraph_edge_to_intraproc_superedge_t
;
201 cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge
;
203 typedef ordered_hash_map
<gimple
*, supernode
*> stmt_to_node_t
;
204 stmt_to_node_t m_stmt_to_node_t
;
206 typedef hash_map
<const function
*, unsigned> function_to_num_snodes_t
;
207 function_to_num_snodes_t m_function_to_num_snodes
;
210 /* A node within a supergraph. */
212 class supernode
: public dnode
<supergraph_traits
>
215 supernode (function
*fun
, basic_block bb
, gcall
*returning_call
,
216 gimple_seq phi_nodes
, int index
)
217 : m_fun (fun
), m_bb (bb
), m_returning_call (returning_call
),
218 m_phi_nodes (phi_nodes
), m_index (index
)
221 function
*get_function () const { return m_fun
; }
223 bool entry_p () const
225 return m_bb
== ENTRY_BLOCK_PTR_FOR_FN (m_fun
);
228 bool return_p () const
230 return m_bb
== EXIT_BLOCK_PTR_FOR_FN (m_fun
);
233 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const OVERRIDE
;
234 void dump_dot_id (pretty_printer
*pp
) const;
236 json::object
*to_json () const;
238 location_t
get_start_location () const;
239 location_t
get_end_location () const;
241 /* Returns iterator at the start of the list of phi nodes, if any. */
242 gphi_iterator
start_phis ()
244 gimple_seq
*pseq
= &m_phi_nodes
;
246 /* Adapted from gsi_start_1. */
249 i
.ptr
= gimple_seq_first (*pseq
);
251 i
.bb
= i
.ptr
? gimple_bb (i
.ptr
) : NULL
;
256 gimple
*get_last_stmt () const
258 if (m_stmts
.length () == 0)
260 return m_stmts
[m_stmts
.length () - 1];
263 gcall
*get_final_call () const
265 gimple
*stmt
= get_last_stmt ();
268 return dyn_cast
<gcall
*> (stmt
);
271 unsigned int get_stmt_index (const gimple
*stmt
) const;
273 function
* const m_fun
; // alternatively could be stored as runs of indices within the supergraph
274 const basic_block m_bb
;
275 gcall
* const m_returning_call
; // for handling the result of a returned call
276 gimple_seq m_phi_nodes
; // ptr to that of the underlying BB, for the first supernode for the BB
277 auto_vec
<gimple
*> m_stmts
;
278 const int m_index
; /* unique within the supergraph as a whole. */
281 /* An abstract base class encapsulating an edge within a supergraph.
282 Edges can be CFG edges, or calls/returns for callgraph edges. */
284 class superedge
: public dedge
<supergraph_traits
>
287 virtual ~superedge () {}
289 void dump (pretty_printer
*pp
) const;
291 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const;
293 virtual void dump_label_to_pp (pretty_printer
*pp
,
294 bool user_facing
) const = 0;
296 json::object
*to_json () const;
298 enum edge_kind
get_kind () const { return m_kind
; }
300 virtual cfg_superedge
*dyn_cast_cfg_superedge () { return NULL
; }
301 virtual const cfg_superedge
*dyn_cast_cfg_superedge () const { return NULL
; }
302 virtual const switch_cfg_superedge
*dyn_cast_switch_cfg_superedge () const { return NULL
; }
303 virtual callgraph_superedge
*dyn_cast_callgraph_superedge () { return NULL
; }
304 virtual const callgraph_superedge
*dyn_cast_callgraph_superedge () const { return NULL
; }
305 virtual call_superedge
*dyn_cast_call_superedge () { return NULL
; }
306 virtual const call_superedge
*dyn_cast_call_superedge () const { return NULL
; }
307 virtual return_superedge
*dyn_cast_return_superedge () { return NULL
; }
308 virtual const return_superedge
*dyn_cast_return_superedge () const { return NULL
; }
310 ::edge
get_any_cfg_edge () const;
311 cgraph_edge
*get_any_callgraph_edge () const;
313 char *get_description (bool user_facing
) const;
316 superedge (supernode
*src
, supernode
*dest
, enum edge_kind kind
)
317 : dedge
<supergraph_traits
> (src
, dest
),
322 const enum edge_kind m_kind
;
325 /* An ID representing an expression at a callsite:
326 either a parameter index, or the return value (or unknown). */
331 callsite_expr () : m_val (-1) {}
333 static callsite_expr
from_zero_based_param (int idx
)
335 return callsite_expr (idx
+ 1);
338 static callsite_expr
from_return_value ()
340 return callsite_expr (0);
343 bool param_p () const
348 bool return_value_p () const
354 callsite_expr (int val
) : m_val (val
) {}
356 int m_val
; /* 1-based parm, 0 for return value, or -1 for "unknown". */
359 /* A subclass of superedge with an associated callgraph edge (either a
360 call or a return). */
362 class callgraph_superedge
: public superedge
365 callgraph_superedge (supernode
*src
, supernode
*dst
, enum edge_kind kind
,
367 : superedge (src
, dst
, kind
),
371 void dump_label_to_pp (pretty_printer
*pp
, bool user_facing
) const
374 function
*get_callee_function () const;
375 function
*get_caller_function () const;
376 tree
get_callee_decl () const;
377 tree
get_caller_decl () const;
378 gcall
*get_call_stmt () const { return m_cedge
->call_stmt
; }
379 tree
get_arg_for_parm (tree parm
, callsite_expr
*out
) const;
380 tree
get_parm_for_arg (tree arg
, callsite_expr
*out
) const;
381 tree
map_expr_from_caller_to_callee (tree caller_expr
,
382 callsite_expr
*out
) const;
383 tree
map_expr_from_callee_to_caller (tree callee_expr
,
384 callsite_expr
*out
) const;
386 cgraph_edge
*const m_cedge
;
394 is_a_helper
<const callgraph_superedge
*>::test (const superedge
*sedge
)
396 return (sedge
->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
397 || sedge
->get_kind () == SUPEREDGE_CALL
398 || sedge
->get_kind () == SUPEREDGE_RETURN
);
403 /* A subclass of superedge representing an interprocedural call. */
405 class call_superedge
: public callgraph_superedge
408 call_superedge (supernode
*src
, supernode
*dst
, cgraph_edge
*cedge
)
409 : callgraph_superedge (src
, dst
, SUPEREDGE_CALL
, cedge
)
412 callgraph_superedge
*dyn_cast_callgraph_superedge () FINAL OVERRIDE
416 const callgraph_superedge
*dyn_cast_callgraph_superedge () const
422 call_superedge
*dyn_cast_call_superedge () FINAL OVERRIDE
426 const call_superedge
*dyn_cast_call_superedge () const FINAL OVERRIDE
431 return_superedge
*get_edge_for_return (const supergraph
&sg
) const
433 return sg
.get_edge_for_return (m_cedge
);
442 is_a_helper
<const call_superedge
*>::test (const superedge
*sedge
)
444 return sedge
->get_kind () == SUPEREDGE_CALL
;
449 /* A subclass of superedge represesnting an interprocedural return. */
451 class return_superedge
: public callgraph_superedge
454 return_superedge (supernode
*src
, supernode
*dst
, cgraph_edge
*cedge
)
455 : callgraph_superedge (src
, dst
, SUPEREDGE_RETURN
, cedge
)
458 callgraph_superedge
*dyn_cast_callgraph_superedge () FINAL OVERRIDE
462 const callgraph_superedge
*dyn_cast_callgraph_superedge () const
466 return_superedge
*dyn_cast_return_superedge () FINAL OVERRIDE
{ return this; }
467 const return_superedge
*dyn_cast_return_superedge () const FINAL OVERRIDE
472 call_superedge
*get_edge_for_call (const supergraph
&sg
) const
474 return sg
.get_edge_for_call (m_cedge
);
483 is_a_helper
<const return_superedge
*>::test (const superedge
*sedge
)
485 return sedge
->get_kind () == SUPEREDGE_RETURN
;
490 /* A subclass of superedge that corresponds to a CFG edge. */
492 class cfg_superedge
: public superedge
495 cfg_superedge (supernode
*src
, supernode
*dst
, ::edge e
)
496 : superedge (src
, dst
, SUPEREDGE_CFG_EDGE
),
500 void dump_label_to_pp (pretty_printer
*pp
, bool user_facing
) const OVERRIDE
;
501 cfg_superedge
*dyn_cast_cfg_superedge () FINAL OVERRIDE
{ return this; }
502 const cfg_superedge
*dyn_cast_cfg_superedge () const FINAL OVERRIDE
{ return this; }
504 ::edge
get_cfg_edge () const { return m_cfg_edge
; }
505 int get_flags () const { return m_cfg_edge
->flags
; }
506 int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE
; }
507 int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE
; }
508 int back_edge_p () const { return get_flags () & EDGE_DFS_BACK
; }
510 tree
get_phi_arg (const gphi
*phi
) const;
513 const ::edge m_cfg_edge
;
521 is_a_helper
<const cfg_superedge
*>::test (const superedge
*sedge
)
523 return sedge
->get_kind () == SUPEREDGE_CFG_EDGE
;
528 /* A subclass for edges from switch statements, retaining enough
529 information to identify the pertinent case, and for adding labels
530 when rendering via graphviz. */
532 class switch_cfg_superedge
: public cfg_superedge
{
534 switch_cfg_superedge (supernode
*src
, supernode
*dst
, ::edge e
, int idx
)
535 : cfg_superedge (src
, dst
, e
),
539 const switch_cfg_superedge
*dyn_cast_switch_cfg_superedge () const
545 void dump_label_to_pp (pretty_printer
*pp
, bool user_facing
) const
548 gswitch
*get_switch_stmt () const
550 return as_a
<gswitch
*> (m_src
->get_last_stmt ());
553 tree
get_case_label () const;
564 is_a_helper
<const switch_cfg_superedge
*>::test (const superedge
*sedge
)
566 return sedge
->dyn_cast_switch_cfg_superedge () != NULL
;
571 /* Base class for adding additional content to the .dot output
577 virtual ~dot_annotator () {}
578 virtual bool add_node_annotations (graphviz_out
*gv ATTRIBUTE_UNUSED
,
579 const supernode
&n ATTRIBUTE_UNUSED
,
580 bool within_table ATTRIBUTE_UNUSED
)
585 virtual void add_stmt_annotations (graphviz_out
*gv ATTRIBUTE_UNUSED
,
586 const gimple
*stmt ATTRIBUTE_UNUSED
,
587 bool within_row ATTRIBUTE_UNUSED
)
589 virtual bool add_after_node_annotations (graphviz_out
*gv ATTRIBUTE_UNUSED
,
590 const supernode
&n ATTRIBUTE_UNUSED
)
597 extern cgraph_edge
*supergraph_call_edge (function
*fun
, gimple
*stmt
);
601 #endif /* GCC_ANALYZER_SUPERGRAPH_H */