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 return UNKNOWN_LOCATION
;
796 /* Get a location_t for the end of this supernode. */
799 supernode::get_end_location () const
803 FOR_EACH_VEC_ELT_REVERSE (m_stmts
, i
, stmt
)
804 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
805 return stmt
->location
;
808 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
809 return m_returning_call
->location
;
812 return m_fun
->function_start_locus
;
814 return m_fun
->function_end_locus
;
816 return UNKNOWN_LOCATION
;
819 /* Given STMT within this supernode, return its index within m_stmts. */
822 supernode::get_stmt_index (const gimple
*stmt
) const
826 FOR_EACH_VEC_ELT (m_stmts
, i
, iter_stmt
)
827 if (iter_stmt
== stmt
)
832 /* Get any label_decl for this supernode, or NULL_TREE if there isn't one. */
835 supernode::get_label () const
837 if (m_stmts
.length () == 0)
839 const glabel
*label_stmt
= dyn_cast
<const glabel
*> (m_stmts
[0]);
842 return gimple_label_label (label_stmt
);
845 /* Get a string for PK. */
848 edge_kind_to_string (enum edge_kind kind
)
854 case SUPEREDGE_CFG_EDGE
:
855 return "SUPEREDGE_CFG_EDGE";
857 return "SUPEREDGE_CALL";
858 case SUPEREDGE_RETURN
:
859 return "SUPEREDGE_RETURN";
860 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
861 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
865 /* Dump this superedge to PP. */
868 superedge::dump (pretty_printer
*pp
) const
870 pp_printf (pp
, "edge: SN: %i -> SN: %i", m_src
->m_index
, m_dest
->m_index
);
871 label_text
desc (get_description (false));
872 if (strlen (desc
.get ()) > 0)
875 pp_string (pp
, desc
.get ());
879 /* Dump this superedge to stderr. */
882 superedge::dump () const
885 pp_format_decoder (&pp
) = default_tree_printer
;
886 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
887 pp
.buffer
->stream
= stderr
;
893 /* Implementation of dedge::dump_dot for superedges.
894 Write a .dot edge to GV representing this superedge. */
897 superedge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
899 const char *style
= "\"solid,bold\"";
900 const char *color
= "black";
902 const char *constraint
= "true";
908 case SUPEREDGE_CFG_EDGE
:
913 case SUPEREDGE_RETURN
:
916 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
917 style
= "\"dotted\"";
921 /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
922 if (::edge cfg_edge
= get_any_cfg_edge ())
924 if (cfg_edge
->flags
& EDGE_FAKE
)
930 else if (cfg_edge
->flags
& EDGE_DFS_BACK
)
932 style
= "\"dotted,bold\"";
936 else if (cfg_edge
->flags
& EDGE_FALLTHRU
)
942 if (cfg_edge
->flags
& EDGE_ABNORMAL
)
948 pretty_printer
*pp
= gv
->get_pp ();
950 m_src
->dump_dot_id (pp
);
951 pp_string (pp
, " -> ");
952 m_dest
->dump_dot_id (pp
);
954 (" [style=%s, color=%s, weight=%d, constraint=%s,"
955 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
957 style
, color
, weight
, constraint
,
958 m_src
->m_index
, m_dest
->m_index
);
960 dump_label_to_pp (pp
, false);
962 pp_printf (pp
, "\"];\n");
965 /* Return a new json::object of the form
967 "src_idx": int, the index of the source supernode,
968 "dst_idx": int, the index of the destination supernode,
972 superedge::to_json () const
974 json::object
*sedge_obj
= new json::object ();
975 sedge_obj
->set ("kind", new json::string (edge_kind_to_string (m_kind
)));
976 sedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
977 sedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
981 pp_format_decoder (&pp
) = default_tree_printer
;
982 dump_label_to_pp (&pp
, false);
983 sedge_obj
->set ("desc", new json::string (pp_formatted_text (&pp
)));
989 /* If this is an intraprocedural superedge, return the associated
990 CFG edge. Otherwise, return NULL. */
993 superedge::get_any_cfg_edge () const
995 if (const cfg_superedge
*sub
= dyn_cast_cfg_superedge ())
996 return sub
->get_cfg_edge ();
1000 /* If this is an interprocedural superedge, return the associated
1001 cgraph_edge *. Otherwise, return NULL. */
1004 superedge::get_any_callgraph_edge () const
1006 if (const callgraph_superedge
*sub
= dyn_cast_callgraph_superedge ())
1007 return sub
->m_cedge
;
1011 /* Build a description of this superedge (e.g. "true" for the true
1012 edge of a conditional, or "case 42:" for a switch case).
1014 If USER_FACING is false, the result also contains any underlying
1015 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1018 superedge::get_description (bool user_facing
) const
1021 dump_label_to_pp (&pp
, user_facing
);
1022 return label_text::take (xstrdup (pp_formatted_text (&pp
)));
1025 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1028 For true/false edges, print "true" or "false" to PP.
1030 If USER_FACING is false, also print flags on the underlying CFG edge to
1034 cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1035 bool user_facing
) const
1037 if (true_value_p ())
1038 pp_printf (pp
, "true");
1039 else if (false_value_p ())
1040 pp_printf (pp
, "false");
1045 /* Express edge flags as a string with " | " separator.
1046 e.g. " (flags FALLTHRU | DFS_BACK)". */
1049 pp_string (pp
, " (flags ");
1050 bool seen_flag
= false;
1051 #define DEF_EDGE_FLAG(NAME,IDX) \
1053 if (get_flags () & EDGE_##NAME) \
1056 pp_string (pp, " | "); \
1057 pp_printf (pp, "%s", (#NAME)); \
1061 #include "cfg-flags.def"
1062 #undef DEF_EDGE_FLAG
1063 pp_string (pp
, ")");
1066 /* Otherwise, no label. */
1069 /* Get the index number for this edge for use in phi stmts
1070 in its destination. */
1073 cfg_superedge::get_phi_arg_idx () const
1075 return m_cfg_edge
->dest_idx
;
1078 /* Get the phi argument for PHI for this CFG edge. */
1081 cfg_superedge::get_phi_arg (const gphi
*phi
) const
1083 size_t index
= get_phi_arg_idx ();
1084 return gimple_phi_arg_def (phi
, index
);
1087 switch_cfg_superedge::switch_cfg_superedge (supernode
*src
,
1090 : cfg_superedge (src
, dst
, e
)
1092 /* Populate m_case_labels with all cases which go to DST. */
1093 const gswitch
*gswitch
= get_switch_stmt ();
1094 for (unsigned i
= 0; i
< gimple_switch_num_labels (gswitch
); i
++)
1096 tree case_
= gimple_switch_label (gswitch
, i
);
1097 basic_block bb
= label_to_block (src
->get_function (),
1098 CASE_LABEL (case_
));
1099 if (bb
== dst
->m_bb
)
1100 m_case_labels
.safe_push (case_
);
1104 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1105 "switch" statements.
1107 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1110 switch_cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1111 bool user_facing ATTRIBUTE_UNUSED
) const
1115 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1118 pp_string (pp
, ", ");
1119 tree case_label
= m_case_labels
[i
];
1120 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1121 tree lower_bound
= CASE_LOW (case_label
);
1122 tree upper_bound
= CASE_HIGH (case_label
);
1125 pp_printf (pp
, "case ");
1126 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1129 pp_printf (pp
, " ... ");
1130 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1133 pp_printf (pp
, ":");
1136 pp_printf (pp
, "default:");
1141 pp_character (pp
, '{');
1142 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1145 pp_string (pp
, ", ");
1146 tree case_label
= m_case_labels
[i
];
1147 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1148 tree lower_bound
= CASE_LOW (case_label
);
1149 tree upper_bound
= CASE_HIGH (case_label
);
1154 pp_character (pp
, '[');
1155 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0,
1157 pp_string (pp
, ", ");
1158 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1160 pp_character (pp
, ']');
1163 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1166 pp_printf (pp
, "default");
1168 pp_character (pp
, '}');
1169 if (implicitly_created_default_p ())
1171 pp_string (pp
, " IMPLICITLY CREATED");
1176 /* Return true iff this edge is purely for an implicitly-created "default". */
1179 switch_cfg_superedge::implicitly_created_default_p () const
1181 if (m_case_labels
.length () != 1)
1184 tree case_label
= m_case_labels
[0];
1185 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1186 if (CASE_LOW (case_label
))
1189 /* We have a single "default" case.
1190 Assume that it was implicitly created if it has UNKNOWN_LOCATION. */
1191 return EXPR_LOCATION (case_label
) == UNKNOWN_LOCATION
;
1194 /* Implementation of superedge::dump_label_to_pp for interprocedural
1198 callgraph_superedge::dump_label_to_pp (pretty_printer
*pp
,
1199 bool user_facing ATTRIBUTE_UNUSED
) const
1204 case SUPEREDGE_CFG_EDGE
:
1207 case SUPEREDGE_CALL
:
1208 pp_printf (pp
, "call");
1211 case SUPEREDGE_RETURN
:
1212 pp_printf (pp
, "return");
1215 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1216 pp_printf (pp
, "intraproc link");
1221 /* Get the function that was called at this interprocedural call/return
1225 callgraph_superedge::get_callee_function () const
1227 return get_ultimate_function_for_cgraph_edge (m_cedge
);
1230 /* Get the calling function at this interprocedural call/return edge. */
1233 callgraph_superedge::get_caller_function () const
1235 return m_cedge
->caller
->get_fun ();
1238 /* Get the fndecl that was called at this interprocedural call/return
1242 callgraph_superedge::get_callee_decl () const
1244 return get_callee_function ()->decl
;
1247 /* Get the gcall * of this interprocedural call/return edge. */
1250 callgraph_superedge::get_call_stmt () const
1253 return m_cedge
->call_stmt
;
1255 return m_src
->get_final_call ();
1258 /* Get the calling fndecl at this interprocedural call/return edge. */
1261 callgraph_superedge::get_caller_decl () const
1263 return get_caller_function ()->decl
;
1266 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1267 to *OUT if OUT is non-NULL), and return the corresponding argument
1271 callgraph_superedge::get_arg_for_parm (tree parm_to_find
,
1272 callsite_expr
*out
) const
1274 gcc_assert (TREE_CODE (parm_to_find
) == PARM_DECL
);
1276 tree callee
= get_callee_decl ();
1277 const gcall
*call_stmt
= get_call_stmt ();
1280 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1281 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1283 if (i
>= gimple_call_num_args (call_stmt
))
1285 if (iter_parm
== parm_to_find
)
1288 *out
= callsite_expr::from_zero_based_param (i
);
1289 return gimple_call_arg (call_stmt
, i
);
1297 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1298 If found, return the default SSA def of the corresponding parm within
1299 the callee, and if OUT is non-NULL, write the index to *OUT.
1300 Only the first match is handled. */
1303 callgraph_superedge::get_parm_for_arg (tree arg_to_find
,
1304 callsite_expr
*out
) const
1306 tree callee
= get_callee_decl ();
1307 const gcall
*call_stmt
= get_call_stmt ();
1310 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1311 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1313 if (i
>= gimple_call_num_args (call_stmt
))
1315 tree param
= gimple_call_arg (call_stmt
, i
);
1316 if (arg_to_find
== param
)
1319 *out
= callsite_expr::from_zero_based_param (i
);
1320 return ssa_default_def (get_callee_function (), iter_parm
);
1328 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1329 If non-NULL is returned, populate OUT. */
1332 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr
,
1333 callsite_expr
*out
) const
1335 /* Is it an argument (actual param)? If so, convert to
1336 parameter (formal param). */
1337 tree parm
= get_parm_for_arg (caller_expr
, out
);
1340 /* Otherwise try return value. */
1341 if (caller_expr
== gimple_call_lhs (get_call_stmt ()))
1344 *out
= callsite_expr::from_return_value ();
1345 return DECL_RESULT (get_callee_decl ());
1351 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1352 If non-NULL is returned, populate OUT. */
1355 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr
,
1356 callsite_expr
*out
) const
1358 if (callee_expr
== NULL_TREE
)
1361 /* If it's a parameter (formal param), get the argument (actual param). */
1362 if (TREE_CODE (callee_expr
) == PARM_DECL
)
1363 return get_arg_for_parm (callee_expr
, out
);
1365 /* Similar for the default SSA name of the PARM_DECL. */
1366 if (TREE_CODE (callee_expr
) == SSA_NAME
1367 && SSA_NAME_IS_DEFAULT_DEF (callee_expr
)
1368 && TREE_CODE (SSA_NAME_VAR (callee_expr
)) == PARM_DECL
)
1369 return get_arg_for_parm (SSA_NAME_VAR (callee_expr
), out
);
1371 /* Otherwise try return value. */
1372 if (callee_expr
== DECL_RESULT (get_callee_decl ()))
1375 *out
= callsite_expr::from_return_value ();
1376 return gimple_call_lhs (get_call_stmt ());
1384 #endif /* #if ENABLE_ANALYZER */