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>.
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/>. */
22 #define INCLUDE_MEMORY
24 #include "coretypes.h"
28 #include "hash-table.h"
31 #include "basic-block.h"
34 #include "gimple-iterator.h"
35 #include "gimple-fold.h"
37 #include "gimple-expr.h"
40 #include "gimple-pretty-print.h"
41 #include "tree-pretty-print.h"
48 #include "analyzer/analyzer.h"
49 #include "ordered-hash-map.h"
55 #include "analyzer/supergraph.h"
56 #include "analyzer/analyzer-logging.h"
62 /* Get the function of the ultimate alias target being called at EDGE,
66 get_ultimate_function_for_cgraph_edge (cgraph_edge
*edge
)
68 cgraph_node
*ultimate_node
= edge
->callee
->ultimate_alias_target ();
71 return ultimate_node
->get_fun ();
74 /* Get the cgraph_edge, but only if there's an underlying function body. */
77 supergraph_call_edge (function
*fun
, const gimple
*stmt
)
79 const gcall
*call
= dyn_cast
<const gcall
*> (stmt
);
83 = cgraph_node::get (fun
->decl
)->get_edge (const_cast <gimple
*> (stmt
));
87 return NULL
; /* e.g. for a function pointer. */
88 if (!get_ultimate_function_for_cgraph_edge (edge
))
95 In order to ensure consistent results without relying on the ordering
96 of pointer values we assign a uid to each gimple stmt, globally unique
99 Normally, the stmt uids are a scratch space that each pass can freely
100 assign its own values to. However, in the case of LTO, the uids are
101 used to associate call stmts with callgraph edges between the WPA phase
102 (where the analyzer runs in LTO mode) and the LTRANS phase; if the
103 analyzer changes them in the WPA phase, it leads to errors when
104 streaming the code back in at LTRANS.
105 lto_prepare_function_for_streaming has code to renumber the stmt UIDs
106 when the code is streamed back out, but for some reason this isn't
109 Hence, as a workaround, this class has responsibility for tracking
110 the original uids and restoring them once the pass is complete
111 (in the supergraph dtor). */
113 /* Give STMT a globally unique uid, storing its original uid so it can
114 later be restored. */
117 saved_uids::make_uid_unique (gimple
*stmt
)
119 unsigned next_uid
= m_old_stmt_uids
.length ();
120 unsigned old_stmt_uid
= stmt
->uid
;
121 stmt
->uid
= next_uid
;
122 m_old_stmt_uids
.safe_push
123 (std::pair
<gimple
*, unsigned> (stmt
, old_stmt_uid
));
126 /* Restore the saved uids of all stmts. */
129 saved_uids::restore_uids () const
132 std::pair
<gimple
*, unsigned> *pair
;
133 FOR_EACH_VEC_ELT (m_old_stmt_uids
, i
, pair
)
134 pair
->first
->uid
= pair
->second
;
137 /* supergraph's ctor. Walk the callgraph, building supernodes for each
138 CFG basic block, splitting the basic blocks at callsites. Join
139 together the supernodes with interprocedural and intraprocedural
140 superedges as appropriate.
141 Assign UIDs to the gimple stmts. */
143 supergraph::supergraph (logger
*logger
)
145 auto_timevar
tv (TV_ANALYZER_SUPERGRAPH
);
149 /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
151 /* Sort the cgraph_nodes? */
153 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
155 function
*fun
= node
->get_fun ();
157 /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
158 the supergraph (by doing it per-function). */
159 auto_cfun
sentinel (fun
);
160 mark_dfs_back_edges ();
162 const int start_idx
= m_nodes
.length ();
165 FOR_ALL_BB_FN (bb
, fun
)
167 /* The initial supernode for the BB gets the phi nodes (if any). */
168 supernode
*node_for_stmts
= add_node (fun
, bb
, NULL
, phi_nodes (bb
));
169 m_bb_to_initial_node
.put (bb
, node_for_stmts
);
170 for (gphi_iterator gpi
= gsi_start_phis (bb
); !gsi_end_p (gpi
);
173 gimple
*stmt
= gsi_stmt (gpi
);
174 m_stmt_to_node_t
.put (stmt
, node_for_stmts
);
175 m_stmt_uids
.make_uid_unique (stmt
);
178 /* Append statements from BB to the current supernode, splitting
179 them into a new supernode at each call site; such call statements
180 appear in both supernodes (representing call and return). */
181 gimple_stmt_iterator gsi
;
182 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
184 gimple
*stmt
= gsi_stmt (gsi
);
185 node_for_stmts
->m_stmts
.safe_push (stmt
);
186 m_stmt_to_node_t
.put (stmt
, node_for_stmts
);
187 m_stmt_uids
.make_uid_unique (stmt
);
188 if (cgraph_edge
*edge
= supergraph_call_edge (fun
, stmt
))
190 m_cgraph_edge_to_caller_prev_node
.put(edge
, node_for_stmts
);
191 node_for_stmts
= add_node (fun
, bb
, as_a
<gcall
*> (stmt
),
193 m_cgraph_edge_to_caller_next_node
.put (edge
, node_for_stmts
);
197 // maybe call is via a function pointer
198 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
201 = cgraph_node::get (fun
->decl
)->get_edge (stmt
);
202 if (!edge
|| !edge
->callee
)
204 supernode
*old_node_for_stmts
= node_for_stmts
;
205 node_for_stmts
= add_node (fun
, bb
, call
, NULL
);
208 = new callgraph_superedge (old_node_for_stmts
,
210 SUPEREDGE_INTRAPROCEDURAL_CALL
,
218 m_bb_to_final_node
.put (bb
, node_for_stmts
);
221 const unsigned num_snodes
= m_nodes
.length () - start_idx
;
222 m_function_to_num_snodes
.put (fun
, num_snodes
);
226 const int end_idx
= m_nodes
.length () - 1;
227 logger
->log ("SN: %i...%i: function %qD",
228 start_idx
, end_idx
, fun
->decl
);
233 /* Second pass: make superedges. */
235 /* Make superedges for CFG edges. */
236 for (bb_to_node_t::iterator iter
= m_bb_to_final_node
.begin ();
237 iter
!= m_bb_to_final_node
.end ();
240 basic_block bb
= (*iter
).first
;
241 supernode
*src_supernode
= (*iter
).second
;
246 FOR_EACH_VEC_ELT (*bb
->succs
, idx
, cfg_edge
)
248 basic_block dest_cfg_block
= cfg_edge
->dest
;
249 supernode
*dest_supernode
250 = *m_bb_to_initial_node
.get (dest_cfg_block
);
251 cfg_superedge
*cfg_sedge
252 = add_cfg_edge (src_supernode
, dest_supernode
, cfg_edge
);
253 m_cfg_edge_to_cfg_superedge
.put (cfg_edge
, cfg_sedge
);
257 /* Make interprocedural superedges for calls. */
259 for (cgraph_edge_to_node_t::iterator iter
260 = m_cgraph_edge_to_caller_prev_node
.begin ();
261 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
264 cgraph_edge
*edge
= (*iter
).first
;
265 supernode
*caller_prev_supernode
= (*iter
).second
;
266 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
267 if (!callee_fn
|| !callee_fn
->cfg
)
269 basic_block callee_cfg_block
= ENTRY_BLOCK_PTR_FOR_FN (callee_fn
);
270 supernode
*callee_supernode
271 = *m_bb_to_initial_node
.get (callee_cfg_block
);
272 call_superedge
*sedge
273 = add_call_superedge (caller_prev_supernode
,
276 m_cgraph_edge_to_call_superedge
.put (edge
, sedge
);
280 /* Make interprocedural superedges for returns. */
282 for (cgraph_edge_to_node_t::iterator iter
283 = m_cgraph_edge_to_caller_next_node
.begin ();
284 iter
!= m_cgraph_edge_to_caller_next_node
.end ();
287 cgraph_edge
*edge
= (*iter
).first
;
288 supernode
*caller_next_supernode
= (*iter
).second
;
289 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
290 if (!callee_fn
|| !callee_fn
->cfg
)
292 basic_block callee_cfg_block
= EXIT_BLOCK_PTR_FOR_FN (callee_fn
);
293 supernode
*callee_supernode
294 = *m_bb_to_initial_node
.get (callee_cfg_block
);
295 return_superedge
*sedge
296 = add_return_superedge (callee_supernode
,
297 caller_next_supernode
,
299 m_cgraph_edge_to_return_superedge
.put (edge
, sedge
);
303 /* Make intraprocedural superedges linking the two halves of a call. */
305 for (cgraph_edge_to_node_t::iterator iter
306 = m_cgraph_edge_to_caller_prev_node
.begin ();
307 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
310 cgraph_edge
*edge
= (*iter
).first
;
311 supernode
*caller_prev_supernode
= (*iter
).second
;
312 supernode
*caller_next_supernode
313 = *m_cgraph_edge_to_caller_next_node
.get (edge
);
315 = new callgraph_superedge (caller_prev_supernode
,
316 caller_next_supernode
,
317 SUPEREDGE_INTRAPROCEDURAL_CALL
,
320 m_cgraph_edge_to_intraproc_superedge
.put (edge
, sedge
);
327 /* supergraph's dtor. Reset stmt uids. */
329 supergraph::~supergraph ()
331 m_stmt_uids
.restore_uids ();
334 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
335 Cluster the supernodes by function, then by BB from original CFG. */
338 supergraph::dump_dot_to_pp (pretty_printer
*pp
,
339 const dump_args_t
&dump_args
) const
341 graphviz_out
gv (pp
);
343 pp_string (pp
, "digraph \"");
344 pp_write_text_to_stream (pp
);
345 pp_string (pp
, "supergraph");
346 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/false);
347 pp_string (pp
, "\" {\n");
350 gv
.println ("overlap=false;");
351 gv
.println ("compound=true;");
353 /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
354 https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
357 /* Break out the supernodes into clusters by function. */
360 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
362 function
*fun
= node
->get_fun ();
363 const char *funcname
= function_name (fun
);
364 gv
.println ("subgraph \"cluster_%s\" {",
373 /* Break out the nodes into clusters by BB from original CFG. */
376 FOR_ALL_BB_FN (bb
, fun
)
378 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
380 gv
.println ("subgraph \"cluster_%s_bb_%i\" {",
381 funcname
, bb
->index
);
386 " label=\"bb: %i\";\n"),
390 // TODO: maybe keep an index per-function/per-bb to speed this up???
393 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
394 if (n
->m_fun
== fun
&& n
->m_bb
== bb
)
395 n
->dump_dot (&gv
, dump_args
);
397 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
399 /* Terminate per-bb "subgraph" */
406 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
407 pp_string (pp
, "\t");
408 get_node_for_function_entry (fun
)->dump_dot_id (pp
);
409 pp_string (pp
, ":s -> ");
410 get_node_for_function_exit (fun
)->dump_dot_id (pp
);
411 pp_string (pp
, ":n [style=\"invis\",constraint=true];\n");
413 /* Terminate per-function "subgraph" */
422 FOR_EACH_VEC_ELT (m_edges
, i
, e
)
423 e
->dump_dot (&gv
, dump_args
);
425 /* Terminate "digraph" */
430 /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
433 supergraph::dump_dot_to_file (FILE *fp
, const dump_args_t
&dump_args
) const
435 pretty_printer
*pp
= global_dc
->printer
->clone ();
436 pp_show_color (pp
) = 0;
437 /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
438 trying to prettify things by showing the underlying var. */
439 pp_format_decoder (pp
) = default_tree_printer
;
441 pp
->buffer
->stream
= fp
;
442 dump_dot_to_pp (pp
, dump_args
);
447 /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
450 supergraph::dump_dot (const char *path
, const dump_args_t
&dump_args
) const
452 FILE *fp
= fopen (path
, "w");
453 dump_dot_to_file (fp
, dump_args
);
457 /* Return a new json::object of the form
458 {"nodes" : [objs for snodes],
459 "edges" : [objs for sedges]}. */
462 supergraph::to_json () const
464 json::object
*sgraph_obj
= new json::object ();
468 json::array
*nodes_arr
= new json::array ();
471 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
472 nodes_arr
->append (n
->to_json ());
473 sgraph_obj
->set ("nodes", nodes_arr
);
478 json::array
*edges_arr
= new json::array ();
481 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
482 edges_arr
->append (n
->to_json ());
483 sgraph_obj
->set ("edges", edges_arr
);
489 /* Create a supernode for BB within FUN and add it to this supergraph.
491 If RETURNING_CALL is non-NULL, the supernode represents the resumption
492 of the basic block after returning from that call.
494 If PHI_NODES is non-NULL, this is the initial supernode for the basic
495 block, and is responsible for any handling of the phi nodes. */
498 supergraph::add_node (function
*fun
, basic_block bb
, gcall
*returning_call
,
499 gimple_seq phi_nodes
)
501 supernode
*n
= new supernode (fun
, bb
, returning_call
, phi_nodes
,
503 m_nodes
.safe_push (n
);
507 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
508 adding it to this supergraph.
510 If the edge is for a switch statement, create a switch_cfg_superedge
514 supergraph::add_cfg_edge (supernode
*src
, supernode
*dest
, ::edge e
)
516 /* Special-case switch edges. */
517 gimple
*stmt
= src
->get_last_stmt ();
518 cfg_superedge
*new_edge
;
519 if (stmt
&& stmt
->code
== GIMPLE_SWITCH
)
520 new_edge
= new switch_cfg_superedge (src
, dest
, e
);
522 new_edge
= new cfg_superedge (src
, dest
, e
);
527 /* Create and add a call_superedge representing an interprocedural call
528 from SRC to DEST, using CEDGE. */
531 supergraph::add_call_superedge (supernode
*src
, supernode
*dest
,
534 call_superedge
*new_edge
= new call_superedge (src
, dest
, cedge
);
539 /* Create and add a return_superedge representing returning from an
540 interprocedural call, returning from SRC to DEST, using CEDGE. */
543 supergraph::add_return_superedge (supernode
*src
, supernode
*dest
,
546 return_superedge
*new_edge
= new return_superedge (src
, dest
, cedge
);
551 /* Implementation of dnode::dump_dot vfunc for supernodes.
553 Write a cluster for the node, and within it a .dot node showing
554 the phi nodes and stmts. Call into any node annotator from ARGS to
555 potentially add other records to the cluster. */
558 supernode::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
560 gv
->println ("subgraph cluster_node_%i {",
564 gv
->println("style=\"solid\";");
565 gv
->println("color=\"black\";");
566 gv
->println("fillcolor=\"lightgrey\";");
567 gv
->println("label=\"sn: %i (bb: %i)\";", m_index
, m_bb
->index
);
569 pretty_printer
*pp
= gv
->get_pp ();
571 if (args
.m_node_annotator
)
572 args
.m_node_annotator
->add_node_annotations (gv
, *this, false);
577 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
579 pp_string (pp
, "<TABLE BORDER=\"0\">");
580 pp_write_text_to_stream (pp
);
582 bool had_row
= false;
584 /* Give any annotator the chance to add its own per-node TR elements. */
585 if (args
.m_node_annotator
)
586 if (args
.m_node_annotator
->add_node_annotations (gv
, *this, true))
589 if (m_returning_call
)
592 pp_string (pp
, "returning call: ");
597 pp_gimple_stmt_1 (pp
, m_returning_call
, 0, (dump_flags_t
)0);
598 pp_write_text_as_html_like_dot_to_stream (pp
);
600 /* Give any annotator the chance to add per-stmt TD elements to
602 if (args
.m_node_annotator
)
603 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
607 /* Give any annotator the chance to add per-stmt TR elements. */
608 if (args
.m_node_annotator
)
609 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
618 pp_string (pp
, "<TR><TD>ENTRY</TD></TR>");
625 pp_string (pp
, "<TR><TD>EXIT</TD></TR>");
631 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
632 !gsi_end_p (gpi
); gsi_next (&gpi
))
634 const gimple
*stmt
= gsi_stmt (gpi
);
637 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
638 pp_write_text_as_html_like_dot_to_stream (pp
);
640 /* Give any annotator the chance to add per-phi TD elements to
642 if (args
.m_node_annotator
)
643 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
646 /* Give any annotator the chance to add per-phi TR elements. */
647 if (args
.m_node_annotator
)
648 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
657 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
661 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
662 pp_write_text_as_html_like_dot_to_stream (pp
);
664 /* Give any annotator the chance to add per-stmt TD elements to
666 if (args
.m_node_annotator
)
667 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
670 /* Give any annotator the chance to add per-stmt TR elements. */
671 if (args
.m_node_annotator
)
672 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
678 /* Give any annotator the chance to add additional per-node TR elements
679 to the end of the TABLE. */
680 if (args
.m_node_annotator
)
681 if (args
.m_node_annotator
->add_after_node_annotations (gv
, *this))
684 /* Graphviz requires a TABLE element to have at least one TR
685 (and each TR to have at least one TD). */
688 pp_string (pp
, "<TR><TD>(empty)</TD></TR>");
692 pp_string (pp
, "</TABLE>>];\n\n");
695 /* Terminate "subgraph" */
700 /* Write an ID for this node to PP, for use in .dot output. */
703 supernode::dump_dot_id (pretty_printer
*pp
) const
705 pp_printf (pp
, "node_%i", m_index
);
708 /* Return a new json::object of the form
712 "returning_call": optional str,
717 supernode::to_json () const
719 json::object
*snode_obj
= new json::object ();
721 snode_obj
->set ("idx", new json::integer_number (m_index
));
722 snode_obj
->set ("bb_idx", new json::integer_number (m_bb
->index
));
723 if (function
*fun
= get_function ())
724 snode_obj
->set ("fun", new json::string (function_name (fun
)));
726 if (m_returning_call
)
729 pp_format_decoder (&pp
) = default_tree_printer
;
730 pp_gimple_stmt_1 (&pp
, m_returning_call
, 0, (dump_flags_t
)0);
731 snode_obj
->set ("returning_call",
732 new json::string (pp_formatted_text (&pp
)));
737 json::array
*phi_arr
= new json::array ();
738 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
739 !gsi_end_p (gpi
); gsi_next (&gpi
))
741 const gimple
*stmt
= gsi_stmt (gpi
);
743 pp_format_decoder (&pp
) = default_tree_printer
;
744 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
745 phi_arr
->append (new json::string (pp_formatted_text (&pp
)));
747 snode_obj
->set ("phis", phi_arr
);
752 json::array
*stmt_arr
= new json::array ();
755 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
758 pp_format_decoder (&pp
) = default_tree_printer
;
759 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
760 stmt_arr
->append (new json::string (pp_formatted_text (&pp
)));
762 snode_obj
->set ("stmts", stmt_arr
);
768 /* Get a location_t for the start of this supernode. */
771 supernode::get_start_location () const
774 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
775 return m_returning_call
->location
;
779 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
780 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
781 return stmt
->location
;
785 // TWEAK: show the decl instead; this leads to more readable output:
786 return DECL_SOURCE_LOCATION (m_fun
->decl
);
788 return m_fun
->function_start_locus
;
791 return m_fun
->function_end_locus
;
793 /* We have no locations for stmts. If we have a single out-edge that's
794 a CFG edge, the goto_locus of that edge is a better location for this
795 than UNKNOWN_LOCATION. */
796 if (m_succs
.length () == 1)
797 if (const cfg_superedge
*cfg_sedge
= m_succs
[0]->dyn_cast_cfg_superedge ())
798 return cfg_sedge
->get_goto_locus ();
800 return UNKNOWN_LOCATION
;
803 /* Get a location_t for the end of this supernode. */
806 supernode::get_end_location () const
810 FOR_EACH_VEC_ELT_REVERSE (m_stmts
, i
, stmt
)
811 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
812 return stmt
->location
;
815 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
816 return m_returning_call
->location
;
819 return m_fun
->function_start_locus
;
821 return m_fun
->function_end_locus
;
823 /* If we have a single out-edge that's a CFG edge, use the goto_locus of
825 if (m_succs
.length () == 1)
826 if (const cfg_superedge
*cfg_sedge
= m_succs
[0]->dyn_cast_cfg_superedge ())
827 return cfg_sedge
->get_goto_locus ();
829 return UNKNOWN_LOCATION
;
832 /* Given STMT within this supernode, return its index within m_stmts. */
835 supernode::get_stmt_index (const gimple
*stmt
) const
839 FOR_EACH_VEC_ELT (m_stmts
, i
, iter_stmt
)
840 if (iter_stmt
== stmt
)
845 /* Get any label_decl for this supernode, or NULL_TREE if there isn't one. */
848 supernode::get_label () const
850 if (m_stmts
.length () == 0)
852 const glabel
*label_stmt
= dyn_cast
<const glabel
*> (m_stmts
[0]);
855 return gimple_label_label (label_stmt
);
858 /* Get a string for PK. */
861 edge_kind_to_string (enum edge_kind kind
)
867 case SUPEREDGE_CFG_EDGE
:
868 return "SUPEREDGE_CFG_EDGE";
870 return "SUPEREDGE_CALL";
871 case SUPEREDGE_RETURN
:
872 return "SUPEREDGE_RETURN";
873 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
874 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
878 /* Dump this superedge to PP. */
881 superedge::dump (pretty_printer
*pp
) const
883 pp_printf (pp
, "edge: SN: %i -> SN: %i", m_src
->m_index
, m_dest
->m_index
);
884 label_text
desc (get_description (false));
885 if (strlen (desc
.get ()) > 0)
888 pp_string (pp
, desc
.get ());
892 /* Dump this superedge to stderr. */
895 superedge::dump () const
898 pp_format_decoder (&pp
) = default_tree_printer
;
899 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
900 pp
.buffer
->stream
= stderr
;
906 /* Implementation of dedge::dump_dot for superedges.
907 Write a .dot edge to GV representing this superedge. */
910 superedge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
912 const char *style
= "\"solid,bold\"";
913 const char *color
= "black";
915 const char *constraint
= "true";
921 case SUPEREDGE_CFG_EDGE
:
926 case SUPEREDGE_RETURN
:
929 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
930 style
= "\"dotted\"";
934 /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
935 if (::edge cfg_edge
= get_any_cfg_edge ())
937 if (cfg_edge
->flags
& EDGE_FAKE
)
943 else if (cfg_edge
->flags
& EDGE_DFS_BACK
)
945 style
= "\"dotted,bold\"";
949 else if (cfg_edge
->flags
& EDGE_FALLTHRU
)
955 if (cfg_edge
->flags
& EDGE_ABNORMAL
)
961 pretty_printer
*pp
= gv
->get_pp ();
963 m_src
->dump_dot_id (pp
);
964 pp_string (pp
, " -> ");
965 m_dest
->dump_dot_id (pp
);
967 (" [style=%s, color=%s, weight=%d, constraint=%s,"
968 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
970 style
, color
, weight
, constraint
,
971 m_src
->m_index
, m_dest
->m_index
);
973 dump_label_to_pp (pp
, false);
975 pp_printf (pp
, "\"];\n");
978 /* Return a new json::object of the form
980 "src_idx": int, the index of the source supernode,
981 "dst_idx": int, the index of the destination supernode,
985 superedge::to_json () const
987 json::object
*sedge_obj
= new json::object ();
988 sedge_obj
->set ("kind", new json::string (edge_kind_to_string (m_kind
)));
989 sedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
990 sedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
994 pp_format_decoder (&pp
) = default_tree_printer
;
995 dump_label_to_pp (&pp
, false);
996 sedge_obj
->set ("desc", new json::string (pp_formatted_text (&pp
)));
1002 /* If this is an intraprocedural superedge, return the associated
1003 CFG edge. Otherwise, return NULL. */
1006 superedge::get_any_cfg_edge () const
1008 if (const cfg_superedge
*sub
= dyn_cast_cfg_superedge ())
1009 return sub
->get_cfg_edge ();
1013 /* If this is an interprocedural superedge, return the associated
1014 cgraph_edge *. Otherwise, return NULL. */
1017 superedge::get_any_callgraph_edge () const
1019 if (const callgraph_superedge
*sub
= dyn_cast_callgraph_superedge ())
1020 return sub
->m_cedge
;
1024 /* Build a description of this superedge (e.g. "true" for the true
1025 edge of a conditional, or "case 42:" for a switch case).
1027 If USER_FACING is false, the result also contains any underlying
1028 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1031 superedge::get_description (bool user_facing
) const
1034 dump_label_to_pp (&pp
, user_facing
);
1035 return label_text::take (xstrdup (pp_formatted_text (&pp
)));
1038 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1041 For true/false edges, print "true" or "false" to PP.
1043 If USER_FACING is false, also print flags on the underlying CFG edge to
1047 cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1048 bool user_facing
) const
1050 if (true_value_p ())
1051 pp_printf (pp
, "true");
1052 else if (false_value_p ())
1053 pp_printf (pp
, "false");
1058 /* Express edge flags as a string with " | " separator.
1059 e.g. " (flags FALLTHRU | DFS_BACK)". */
1062 pp_string (pp
, " (flags ");
1063 bool seen_flag
= false;
1064 #define DEF_EDGE_FLAG(NAME,IDX) \
1066 if (get_flags () & EDGE_##NAME) \
1069 pp_string (pp, " | "); \
1070 pp_printf (pp, "%s", (#NAME)); \
1074 #include "cfg-flags.def"
1075 #undef DEF_EDGE_FLAG
1076 pp_string (pp
, ")");
1079 if (m_cfg_edge
->goto_locus
> BUILTINS_LOCATION
)
1080 pp_string (pp
, " (has goto_locus)");
1082 /* Otherwise, no label. */
1085 /* Get the index number for this edge for use in phi stmts
1086 in its destination. */
1089 cfg_superedge::get_phi_arg_idx () const
1091 return m_cfg_edge
->dest_idx
;
1094 /* Get the phi argument for PHI for this CFG edge. */
1097 cfg_superedge::get_phi_arg (const gphi
*phi
) const
1099 size_t index
= get_phi_arg_idx ();
1100 return gimple_phi_arg_def (phi
, index
);
1103 switch_cfg_superedge::switch_cfg_superedge (supernode
*src
,
1106 : cfg_superedge (src
, dst
, e
)
1108 /* Populate m_case_labels with all cases which go to DST. */
1109 const gswitch
*gswitch
= get_switch_stmt ();
1110 for (unsigned i
= 0; i
< gimple_switch_num_labels (gswitch
); i
++)
1112 tree case_
= gimple_switch_label (gswitch
, i
);
1113 basic_block bb
= label_to_block (src
->get_function (),
1114 CASE_LABEL (case_
));
1115 if (bb
== dst
->m_bb
)
1116 m_case_labels
.safe_push (case_
);
1120 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1121 "switch" statements.
1123 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1126 switch_cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1127 bool user_facing ATTRIBUTE_UNUSED
) const
1131 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1134 pp_string (pp
, ", ");
1135 tree case_label
= m_case_labels
[i
];
1136 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1137 tree lower_bound
= CASE_LOW (case_label
);
1138 tree upper_bound
= CASE_HIGH (case_label
);
1141 pp_printf (pp
, "case ");
1142 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1145 pp_printf (pp
, " ... ");
1146 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1149 pp_printf (pp
, ":");
1152 pp_printf (pp
, "default:");
1157 pp_character (pp
, '{');
1158 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1161 pp_string (pp
, ", ");
1162 tree case_label
= m_case_labels
[i
];
1163 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1164 tree lower_bound
= CASE_LOW (case_label
);
1165 tree upper_bound
= CASE_HIGH (case_label
);
1170 pp_character (pp
, '[');
1171 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0,
1173 pp_string (pp
, ", ");
1174 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1176 pp_character (pp
, ']');
1179 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1182 pp_printf (pp
, "default");
1184 pp_character (pp
, '}');
1185 if (implicitly_created_default_p ())
1187 pp_string (pp
, " IMPLICITLY CREATED");
1192 /* Return true iff this edge is purely for an implicitly-created "default". */
1195 switch_cfg_superedge::implicitly_created_default_p () const
1197 if (m_case_labels
.length () != 1)
1200 tree case_label
= m_case_labels
[0];
1201 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1202 if (CASE_LOW (case_label
))
1205 /* We have a single "default" case.
1206 Assume that it was implicitly created if it has UNKNOWN_LOCATION. */
1207 return EXPR_LOCATION (case_label
) == UNKNOWN_LOCATION
;
1210 /* Implementation of superedge::dump_label_to_pp for interprocedural
1214 callgraph_superedge::dump_label_to_pp (pretty_printer
*pp
,
1215 bool user_facing ATTRIBUTE_UNUSED
) const
1220 case SUPEREDGE_CFG_EDGE
:
1223 case SUPEREDGE_CALL
:
1224 pp_printf (pp
, "call");
1227 case SUPEREDGE_RETURN
:
1228 pp_printf (pp
, "return");
1231 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1232 pp_printf (pp
, "intraproc link");
1237 /* Get the function that was called at this interprocedural call/return
1241 callgraph_superedge::get_callee_function () const
1243 return get_ultimate_function_for_cgraph_edge (m_cedge
);
1246 /* Get the calling function at this interprocedural call/return edge. */
1249 callgraph_superedge::get_caller_function () const
1251 return m_cedge
->caller
->get_fun ();
1254 /* Get the fndecl that was called at this interprocedural call/return
1258 callgraph_superedge::get_callee_decl () const
1260 return get_callee_function ()->decl
;
1263 /* Get the gcall * of this interprocedural call/return edge. */
1266 callgraph_superedge::get_call_stmt () const
1269 return m_cedge
->call_stmt
;
1271 return m_src
->get_final_call ();
1274 /* Get the calling fndecl at this interprocedural call/return edge. */
1277 callgraph_superedge::get_caller_decl () const
1279 return get_caller_function ()->decl
;
1282 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1283 to *OUT if OUT is non-NULL), and return the corresponding argument
1287 callgraph_superedge::get_arg_for_parm (tree parm_to_find
,
1288 callsite_expr
*out
) const
1290 gcc_assert (TREE_CODE (parm_to_find
) == PARM_DECL
);
1292 tree callee
= get_callee_decl ();
1293 const gcall
*call_stmt
= get_call_stmt ();
1296 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1297 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1299 if (i
>= gimple_call_num_args (call_stmt
))
1301 if (iter_parm
== parm_to_find
)
1304 *out
= callsite_expr::from_zero_based_param (i
);
1305 return gimple_call_arg (call_stmt
, i
);
1313 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1314 If found, return the default SSA def of the corresponding parm within
1315 the callee, and if OUT is non-NULL, write the index to *OUT.
1316 Only the first match is handled. */
1319 callgraph_superedge::get_parm_for_arg (tree arg_to_find
,
1320 callsite_expr
*out
) const
1322 tree callee
= get_callee_decl ();
1323 const gcall
*call_stmt
= get_call_stmt ();
1326 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1327 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1329 if (i
>= gimple_call_num_args (call_stmt
))
1331 tree param
= gimple_call_arg (call_stmt
, i
);
1332 if (arg_to_find
== param
)
1335 *out
= callsite_expr::from_zero_based_param (i
);
1336 return ssa_default_def (get_callee_function (), iter_parm
);
1344 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1345 If non-NULL is returned, populate OUT. */
1348 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr
,
1349 callsite_expr
*out
) const
1351 /* Is it an argument (actual param)? If so, convert to
1352 parameter (formal param). */
1353 tree parm
= get_parm_for_arg (caller_expr
, out
);
1356 /* Otherwise try return value. */
1357 if (caller_expr
== gimple_call_lhs (get_call_stmt ()))
1360 *out
= callsite_expr::from_return_value ();
1361 return DECL_RESULT (get_callee_decl ());
1367 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1368 If non-NULL is returned, populate OUT. */
1371 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr
,
1372 callsite_expr
*out
) const
1374 if (callee_expr
== NULL_TREE
)
1377 /* If it's a parameter (formal param), get the argument (actual param). */
1378 if (TREE_CODE (callee_expr
) == PARM_DECL
)
1379 return get_arg_for_parm (callee_expr
, out
);
1381 /* Similar for the default SSA name of the PARM_DECL. */
1382 if (TREE_CODE (callee_expr
) == SSA_NAME
1383 && SSA_NAME_IS_DEFAULT_DEF (callee_expr
)
1384 && TREE_CODE (SSA_NAME_VAR (callee_expr
)) == PARM_DECL
)
1385 return get_arg_for_parm (SSA_NAME_VAR (callee_expr
), out
);
1387 /* Otherwise try return value. */
1388 if (callee_expr
== DECL_RESULT (get_callee_decl ()))
1391 *out
= callsite_expr::from_return_value ();
1392 return gimple_call_lhs (get_call_stmt ());
1400 #endif /* #if ENABLE_ANALYZER */