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>.
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 /* Discard debug stmts here, so we don't have to check for
186 them anywhere within the analyzer. */
187 if (is_gimple_debug (stmt
))
189 node_for_stmts
->m_stmts
.safe_push (stmt
);
190 m_stmt_to_node_t
.put (stmt
, node_for_stmts
);
191 m_stmt_uids
.make_uid_unique (stmt
);
192 if (cgraph_edge
*edge
= supergraph_call_edge (fun
, stmt
))
194 m_cgraph_edge_to_caller_prev_node
.put(edge
, node_for_stmts
);
195 node_for_stmts
= add_node (fun
, bb
, as_a
<gcall
*> (stmt
),
197 m_cgraph_edge_to_caller_next_node
.put (edge
, node_for_stmts
);
201 // maybe call is via a function pointer
202 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
205 = cgraph_node::get (fun
->decl
)->get_edge (stmt
);
206 if (!edge
|| !edge
->callee
)
208 supernode
*old_node_for_stmts
= node_for_stmts
;
209 node_for_stmts
= add_node (fun
, bb
, call
, NULL
);
212 = new callgraph_superedge (old_node_for_stmts
,
214 SUPEREDGE_INTRAPROCEDURAL_CALL
,
222 m_bb_to_final_node
.put (bb
, node_for_stmts
);
225 const unsigned num_snodes
= m_nodes
.length () - start_idx
;
226 m_function_to_num_snodes
.put (fun
, num_snodes
);
230 const int end_idx
= m_nodes
.length () - 1;
231 logger
->log ("SN: %i...%i: function %qD",
232 start_idx
, end_idx
, fun
->decl
);
237 /* Second pass: make superedges. */
239 /* Make superedges for CFG edges. */
240 for (bb_to_node_t::iterator iter
= m_bb_to_final_node
.begin ();
241 iter
!= m_bb_to_final_node
.end ();
244 basic_block bb
= (*iter
).first
;
245 supernode
*src_supernode
= (*iter
).second
;
250 FOR_EACH_VEC_ELT (*bb
->succs
, idx
, cfg_edge
)
252 basic_block dest_cfg_block
= cfg_edge
->dest
;
253 supernode
*dest_supernode
254 = *m_bb_to_initial_node
.get (dest_cfg_block
);
255 cfg_superedge
*cfg_sedge
256 = add_cfg_edge (src_supernode
, dest_supernode
, cfg_edge
);
257 m_cfg_edge_to_cfg_superedge
.put (cfg_edge
, cfg_sedge
);
261 /* Make interprocedural superedges for calls. */
263 for (cgraph_edge_to_node_t::iterator iter
264 = m_cgraph_edge_to_caller_prev_node
.begin ();
265 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
268 cgraph_edge
*edge
= (*iter
).first
;
269 supernode
*caller_prev_supernode
= (*iter
).second
;
270 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
271 if (!callee_fn
|| !callee_fn
->cfg
)
273 basic_block callee_cfg_block
= ENTRY_BLOCK_PTR_FOR_FN (callee_fn
);
274 supernode
*callee_supernode
275 = *m_bb_to_initial_node
.get (callee_cfg_block
);
276 call_superedge
*sedge
277 = add_call_superedge (caller_prev_supernode
,
280 m_cgraph_edge_to_call_superedge
.put (edge
, sedge
);
284 /* Make interprocedural superedges for returns. */
286 for (cgraph_edge_to_node_t::iterator iter
287 = m_cgraph_edge_to_caller_next_node
.begin ();
288 iter
!= m_cgraph_edge_to_caller_next_node
.end ();
291 cgraph_edge
*edge
= (*iter
).first
;
292 supernode
*caller_next_supernode
= (*iter
).second
;
293 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
294 if (!callee_fn
|| !callee_fn
->cfg
)
296 basic_block callee_cfg_block
= EXIT_BLOCK_PTR_FOR_FN (callee_fn
);
297 supernode
*callee_supernode
298 = *m_bb_to_initial_node
.get (callee_cfg_block
);
299 return_superedge
*sedge
300 = add_return_superedge (callee_supernode
,
301 caller_next_supernode
,
303 m_cgraph_edge_to_return_superedge
.put (edge
, sedge
);
307 /* Make intraprocedural superedges linking the two halves of a call. */
309 for (cgraph_edge_to_node_t::iterator iter
310 = m_cgraph_edge_to_caller_prev_node
.begin ();
311 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
314 cgraph_edge
*edge
= (*iter
).first
;
315 supernode
*caller_prev_supernode
= (*iter
).second
;
316 supernode
*caller_next_supernode
317 = *m_cgraph_edge_to_caller_next_node
.get (edge
);
319 = new callgraph_superedge (caller_prev_supernode
,
320 caller_next_supernode
,
321 SUPEREDGE_INTRAPROCEDURAL_CALL
,
324 m_cgraph_edge_to_intraproc_superedge
.put (edge
, sedge
);
331 /* supergraph's dtor. Reset stmt uids. */
333 supergraph::~supergraph ()
335 m_stmt_uids
.restore_uids ();
338 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
339 Cluster the supernodes by function, then by BB from original CFG. */
342 supergraph::dump_dot_to_pp (pretty_printer
*pp
,
343 const dump_args_t
&dump_args
) const
345 graphviz_out
gv (pp
);
347 pp_string (pp
, "digraph \"");
348 pp_write_text_to_stream (pp
);
349 pp_string (pp
, "supergraph");
350 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/false);
351 pp_string (pp
, "\" {\n");
354 gv
.println ("overlap=false;");
355 gv
.println ("compound=true;");
357 /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
358 https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
361 /* Break out the supernodes into clusters by function. */
364 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
366 function
*fun
= node
->get_fun ();
368 const char *funcname
= function_name (fun
);
369 gv
.println ("subgraph \"cluster_%s\" {",
378 /* Break out the nodes into clusters by BB from original CFG. */
381 FOR_ALL_BB_FN (bb
, fun
)
383 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
385 gv
.println ("subgraph \"cluster_%s_bb_%i\" {",
386 funcname
, bb
->index
);
391 " label=\"bb: %i\";\n"),
395 // TODO: maybe keep an index per-function/per-bb to speed this up???
398 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
399 if (n
->m_fun
== fun
&& n
->m_bb
== bb
)
400 n
->dump_dot (&gv
, dump_args
);
402 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
404 /* Terminate per-bb "subgraph" */
411 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
412 pp_string (pp
, "\t");
413 get_node_for_function_entry (*fun
)->dump_dot_id (pp
);
414 pp_string (pp
, ":s -> ");
415 get_node_for_function_exit (*fun
)->dump_dot_id (pp
);
416 pp_string (pp
, ":n [style=\"invis\",constraint=true];\n");
418 /* Terminate per-function "subgraph" */
427 FOR_EACH_VEC_ELT (m_edges
, i
, e
)
428 e
->dump_dot (&gv
, dump_args
);
430 /* Terminate "digraph" */
435 /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
438 supergraph::dump_dot_to_file (FILE *fp
, const dump_args_t
&dump_args
) const
440 pretty_printer
*pp
= global_dc
->printer
->clone ();
441 pp_show_color (pp
) = 0;
442 /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
443 trying to prettify things by showing the underlying var. */
444 pp_format_decoder (pp
) = default_tree_printer
;
446 pp
->set_output_stream (fp
);
447 dump_dot_to_pp (pp
, dump_args
);
452 /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
455 supergraph::dump_dot (const char *path
, const dump_args_t
&dump_args
) const
457 FILE *fp
= fopen (path
, "w");
458 dump_dot_to_file (fp
, dump_args
);
462 /* Return a new json::object of the form
463 {"nodes" : [objs for snodes],
464 "edges" : [objs for sedges]}. */
467 supergraph::to_json () const
469 json::object
*sgraph_obj
= new json::object ();
473 json::array
*nodes_arr
= new json::array ();
476 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
477 nodes_arr
->append (n
->to_json ());
478 sgraph_obj
->set ("nodes", nodes_arr
);
483 json::array
*edges_arr
= new json::array ();
486 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
487 edges_arr
->append (n
->to_json ());
488 sgraph_obj
->set ("edges", edges_arr
);
494 /* Create a supernode for BB within FUN and add it to this supergraph.
496 If RETURNING_CALL is non-NULL, the supernode represents the resumption
497 of the basic block after returning from that call.
499 If PHI_NODES is non-NULL, this is the initial supernode for the basic
500 block, and is responsible for any handling of the phi nodes. */
503 supergraph::add_node (function
*fun
, basic_block bb
, gcall
*returning_call
,
504 gimple_seq phi_nodes
)
506 supernode
*n
= new supernode (fun
, bb
, returning_call
, phi_nodes
,
508 m_nodes
.safe_push (n
);
512 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
513 adding it to this supergraph.
515 If the edge is for a switch statement, create a switch_cfg_superedge
519 supergraph::add_cfg_edge (supernode
*src
, supernode
*dest
, ::edge e
)
521 /* Special-case switch edges. */
522 gimple
*stmt
= src
->get_last_stmt ();
523 cfg_superedge
*new_edge
;
524 if (stmt
&& stmt
->code
== GIMPLE_SWITCH
)
525 new_edge
= new switch_cfg_superedge (src
, dest
, e
);
527 new_edge
= new cfg_superedge (src
, dest
, e
);
532 /* Create and add a call_superedge representing an interprocedural call
533 from SRC to DEST, using CEDGE. */
536 supergraph::add_call_superedge (supernode
*src
, supernode
*dest
,
539 call_superedge
*new_edge
= new call_superedge (src
, dest
, cedge
);
544 /* Create and add a return_superedge representing returning from an
545 interprocedural call, returning from SRC to DEST, using CEDGE. */
548 supergraph::add_return_superedge (supernode
*src
, supernode
*dest
,
551 return_superedge
*new_edge
= new return_superedge (src
, dest
, cedge
);
556 /* Implementation of dnode::dump_dot vfunc for supernodes.
558 Write a cluster for the node, and within it a .dot node showing
559 the phi nodes and stmts. Call into any node annotator from ARGS to
560 potentially add other records to the cluster. */
563 supernode::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
565 gv
->println ("subgraph cluster_node_%i {",
569 gv
->println("style=\"solid\";");
570 gv
->println("color=\"black\";");
571 gv
->println("fillcolor=\"lightgrey\";");
572 gv
->println("label=\"sn: %i (bb: %i)\";", m_index
, m_bb
->index
);
574 pretty_printer
*pp
= gv
->get_pp ();
576 if (args
.m_node_annotator
)
577 args
.m_node_annotator
->add_node_annotations (gv
, *this, false);
582 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
584 pp_string (pp
, "<TABLE BORDER=\"0\">");
585 pp_write_text_to_stream (pp
);
587 bool had_row
= false;
589 /* Give any annotator the chance to add its own per-node TR elements. */
590 if (args
.m_node_annotator
)
591 if (args
.m_node_annotator
->add_node_annotations (gv
, *this, true))
594 if (m_returning_call
)
597 pp_string (pp
, "returning call: ");
602 pp_gimple_stmt_1 (pp
, m_returning_call
, 0, (dump_flags_t
)0);
603 pp_write_text_as_html_like_dot_to_stream (pp
);
605 /* Give any annotator the chance to add per-stmt TD elements to
607 if (args
.m_node_annotator
)
608 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
612 /* Give any annotator the chance to add per-stmt TR elements. */
613 if (args
.m_node_annotator
)
614 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
623 pp_string (pp
, "<TR><TD>ENTRY</TD></TR>");
630 pp_string (pp
, "<TR><TD>EXIT</TD></TR>");
636 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
637 !gsi_end_p (gpi
); gsi_next (&gpi
))
639 const gimple
*stmt
= gsi_stmt (gpi
);
642 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
643 pp_write_text_as_html_like_dot_to_stream (pp
);
645 /* Give any annotator the chance to add per-phi TD elements to
647 if (args
.m_node_annotator
)
648 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
651 /* Give any annotator the chance to add per-phi TR elements. */
652 if (args
.m_node_annotator
)
653 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
662 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
666 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
667 pp_write_text_as_html_like_dot_to_stream (pp
);
669 /* Give any annotator the chance to add per-stmt TD elements to
671 if (args
.m_node_annotator
)
672 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
675 /* Give any annotator the chance to add per-stmt TR elements. */
676 if (args
.m_node_annotator
)
677 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
683 /* Give any annotator the chance to add additional per-node TR elements
684 to the end of the TABLE. */
685 if (args
.m_node_annotator
)
686 if (args
.m_node_annotator
->add_after_node_annotations (gv
, *this))
689 /* Graphviz requires a TABLE element to have at least one TR
690 (and each TR to have at least one TD). */
693 pp_string (pp
, "<TR><TD>(empty)</TD></TR>");
697 pp_string (pp
, "</TABLE>>];\n\n");
700 /* Terminate "subgraph" */
705 /* Write an ID for this node to PP, for use in .dot output. */
708 supernode::dump_dot_id (pretty_printer
*pp
) const
710 pp_printf (pp
, "node_%i", m_index
);
713 /* Return a new json::object of the form
717 "returning_call": optional str,
722 supernode::to_json () const
724 json::object
*snode_obj
= new json::object ();
726 snode_obj
->set ("idx", new json::integer_number (m_index
));
727 snode_obj
->set ("bb_idx", new json::integer_number (m_bb
->index
));
728 if (function
*fun
= get_function ())
729 snode_obj
->set ("fun", new json::string (function_name (fun
)));
731 if (m_returning_call
)
734 pp_format_decoder (&pp
) = default_tree_printer
;
735 pp_gimple_stmt_1 (&pp
, m_returning_call
, 0, (dump_flags_t
)0);
736 snode_obj
->set ("returning_call",
737 new json::string (pp_formatted_text (&pp
)));
742 json::array
*phi_arr
= new json::array ();
743 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
744 !gsi_end_p (gpi
); gsi_next (&gpi
))
746 const gimple
*stmt
= gsi_stmt (gpi
);
748 pp_format_decoder (&pp
) = default_tree_printer
;
749 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
750 phi_arr
->append (new json::string (pp_formatted_text (&pp
)));
752 snode_obj
->set ("phis", phi_arr
);
757 json::array
*stmt_arr
= new json::array ();
760 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
763 pp_format_decoder (&pp
) = default_tree_printer
;
764 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
765 stmt_arr
->append (new json::string (pp_formatted_text (&pp
)));
767 snode_obj
->set ("stmts", stmt_arr
);
773 /* Get a location_t for the start of this supernode. */
776 supernode::get_start_location () const
779 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
780 return m_returning_call
->location
;
784 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
785 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
786 return stmt
->location
;
790 // TWEAK: show the decl instead; this leads to more readable output:
791 return DECL_SOURCE_LOCATION (m_fun
->decl
);
793 return m_fun
->function_start_locus
;
796 return m_fun
->function_end_locus
;
798 /* We have no locations for stmts. If we have a single out-edge that's
799 a CFG edge, the goto_locus of that edge is a better location for this
800 than UNKNOWN_LOCATION. */
801 if (m_succs
.length () == 1)
802 if (const cfg_superedge
*cfg_sedge
= m_succs
[0]->dyn_cast_cfg_superedge ())
803 return cfg_sedge
->get_goto_locus ();
805 return UNKNOWN_LOCATION
;
808 /* Get a location_t for the end of this supernode. */
811 supernode::get_end_location () const
815 FOR_EACH_VEC_ELT_REVERSE (m_stmts
, i
, stmt
)
816 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
817 return stmt
->location
;
820 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
821 return m_returning_call
->location
;
824 return m_fun
->function_start_locus
;
826 return m_fun
->function_end_locus
;
828 /* If we have a single out-edge that's a CFG edge, use the goto_locus of
830 if (m_succs
.length () == 1)
831 if (const cfg_superedge
*cfg_sedge
= m_succs
[0]->dyn_cast_cfg_superedge ())
832 return cfg_sedge
->get_goto_locus ();
834 return UNKNOWN_LOCATION
;
837 /* Given STMT within this supernode, return its index within m_stmts. */
840 supernode::get_stmt_index (const gimple
*stmt
) const
844 FOR_EACH_VEC_ELT (m_stmts
, i
, iter_stmt
)
845 if (iter_stmt
== stmt
)
850 /* Get any label_decl for this supernode, or NULL_TREE if there isn't one. */
853 supernode::get_label () const
855 if (m_stmts
.length () == 0)
857 const glabel
*label_stmt
= dyn_cast
<const glabel
*> (m_stmts
[0]);
860 return gimple_label_label (label_stmt
);
863 /* Get a string for PK. */
866 edge_kind_to_string (enum edge_kind kind
)
872 case SUPEREDGE_CFG_EDGE
:
873 return "SUPEREDGE_CFG_EDGE";
875 return "SUPEREDGE_CALL";
876 case SUPEREDGE_RETURN
:
877 return "SUPEREDGE_RETURN";
878 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
879 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
883 /* Dump this superedge to PP. */
886 superedge::dump (pretty_printer
*pp
) const
888 pp_printf (pp
, "edge: SN: %i -> SN: %i", m_src
->m_index
, m_dest
->m_index
);
889 label_text
desc (get_description (false));
890 if (strlen (desc
.get ()) > 0)
893 pp_string (pp
, desc
.get ());
897 /* Dump this superedge to stderr. */
900 superedge::dump () const
903 pp_format_decoder (&pp
) = default_tree_printer
;
904 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
905 pp
.set_output_stream (stderr
);
911 /* Implementation of dedge::dump_dot for superedges.
912 Write a .dot edge to GV representing this superedge. */
915 superedge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
917 const char *style
= "\"solid,bold\"";
918 const char *color
= "black";
920 const char *constraint
= "true";
926 case SUPEREDGE_CFG_EDGE
:
931 case SUPEREDGE_RETURN
:
934 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
935 style
= "\"dotted\"";
939 /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
940 if (::edge cfg_edge
= get_any_cfg_edge ())
942 if (cfg_edge
->flags
& EDGE_FAKE
)
948 else if (cfg_edge
->flags
& EDGE_DFS_BACK
)
950 style
= "\"dotted,bold\"";
954 else if (cfg_edge
->flags
& EDGE_FALLTHRU
)
960 if (cfg_edge
->flags
& EDGE_ABNORMAL
)
966 pretty_printer
*pp
= gv
->get_pp ();
968 m_src
->dump_dot_id (pp
);
969 pp_string (pp
, " -> ");
970 m_dest
->dump_dot_id (pp
);
972 (" [style=%s, color=%s, weight=%d, constraint=%s,"
973 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
975 style
, color
, weight
, constraint
,
976 m_src
->m_index
, m_dest
->m_index
);
978 dump_label_to_pp (pp
, false);
980 pp_printf (pp
, "\"];\n");
983 /* Return a new json::object of the form
985 "src_idx": int, the index of the source supernode,
986 "dst_idx": int, the index of the destination supernode,
990 superedge::to_json () const
992 json::object
*sedge_obj
= new json::object ();
993 sedge_obj
->set ("kind", new json::string (edge_kind_to_string (m_kind
)));
994 sedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
995 sedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
999 pp_format_decoder (&pp
) = default_tree_printer
;
1000 dump_label_to_pp (&pp
, false);
1001 sedge_obj
->set ("desc", new json::string (pp_formatted_text (&pp
)));
1007 /* If this is an intraprocedural superedge, return the associated
1008 CFG edge. Otherwise, return NULL. */
1011 superedge::get_any_cfg_edge () const
1013 if (const cfg_superedge
*sub
= dyn_cast_cfg_superedge ())
1014 return sub
->get_cfg_edge ();
1018 /* If this is an interprocedural superedge, return the associated
1019 cgraph_edge *. Otherwise, return NULL. */
1022 superedge::get_any_callgraph_edge () const
1024 if (const callgraph_superedge
*sub
= dyn_cast_callgraph_superedge ())
1025 return sub
->m_cedge
;
1029 /* Build a description of this superedge (e.g. "true" for the true
1030 edge of a conditional, or "case 42:" for a switch case).
1032 If USER_FACING is false, the result also contains any underlying
1033 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1036 superedge::get_description (bool user_facing
) const
1039 dump_label_to_pp (&pp
, user_facing
);
1040 return label_text::take (xstrdup (pp_formatted_text (&pp
)));
1043 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1046 For true/false edges, print "true" or "false" to PP.
1048 If USER_FACING is false, also print flags on the underlying CFG edge to
1052 cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1053 bool user_facing
) const
1055 if (true_value_p ())
1056 pp_printf (pp
, "true");
1057 else if (false_value_p ())
1058 pp_printf (pp
, "false");
1063 /* Express edge flags as a string with " | " separator.
1064 e.g. " (flags FALLTHRU | DFS_BACK)". */
1067 pp_string (pp
, " (flags ");
1068 bool seen_flag
= false;
1069 #define DEF_EDGE_FLAG(NAME,IDX) \
1071 if (get_flags () & EDGE_##NAME) \
1074 pp_string (pp, " | "); \
1075 pp_printf (pp, "%s", (#NAME)); \
1079 #include "cfg-flags.def"
1080 #undef DEF_EDGE_FLAG
1081 pp_string (pp
, ")");
1084 if (m_cfg_edge
->goto_locus
> BUILTINS_LOCATION
)
1085 pp_string (pp
, " (has goto_locus)");
1087 /* Otherwise, no label. */
1090 /* Get the index number for this edge for use in phi stmts
1091 in its destination. */
1094 cfg_superedge::get_phi_arg_idx () const
1096 return m_cfg_edge
->dest_idx
;
1099 /* Get the phi argument for PHI for this CFG edge. */
1102 cfg_superedge::get_phi_arg (const gphi
*phi
) const
1104 size_t index
= get_phi_arg_idx ();
1105 return gimple_phi_arg_def (phi
, index
);
1108 switch_cfg_superedge::switch_cfg_superedge (supernode
*src
,
1111 : cfg_superedge (src
, dst
, e
)
1113 /* Populate m_case_labels with all cases which go to DST. */
1114 const gswitch
*gswitch
= get_switch_stmt ();
1115 for (unsigned i
= 0; i
< gimple_switch_num_labels (gswitch
); i
++)
1117 tree case_
= gimple_switch_label (gswitch
, i
);
1118 basic_block bb
= label_to_block (src
->get_function (),
1119 CASE_LABEL (case_
));
1120 if (bb
== dst
->m_bb
)
1121 m_case_labels
.safe_push (case_
);
1125 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1126 "switch" statements.
1128 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1131 switch_cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1132 bool user_facing ATTRIBUTE_UNUSED
) const
1136 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1139 pp_string (pp
, ", ");
1140 tree case_label
= m_case_labels
[i
];
1141 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1142 tree lower_bound
= CASE_LOW (case_label
);
1143 tree upper_bound
= CASE_HIGH (case_label
);
1146 pp_printf (pp
, "case ");
1147 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1150 pp_printf (pp
, " ... ");
1151 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1154 pp_printf (pp
, ":");
1157 pp_printf (pp
, "default:");
1162 pp_character (pp
, '{');
1163 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1166 pp_string (pp
, ", ");
1167 tree case_label
= m_case_labels
[i
];
1168 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1169 tree lower_bound
= CASE_LOW (case_label
);
1170 tree upper_bound
= CASE_HIGH (case_label
);
1175 pp_character (pp
, '[');
1176 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0,
1178 pp_string (pp
, ", ");
1179 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1181 pp_character (pp
, ']');
1184 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1187 pp_printf (pp
, "default");
1189 pp_character (pp
, '}');
1190 if (implicitly_created_default_p ())
1192 pp_string (pp
, " IMPLICITLY CREATED");
1197 /* Return true iff this edge is purely for an implicitly-created "default". */
1200 switch_cfg_superedge::implicitly_created_default_p () const
1202 if (m_case_labels
.length () != 1)
1205 tree case_label
= m_case_labels
[0];
1206 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1207 if (CASE_LOW (case_label
))
1210 /* We have a single "default" case.
1211 Assume that it was implicitly created if it has UNKNOWN_LOCATION. */
1212 return EXPR_LOCATION (case_label
) == UNKNOWN_LOCATION
;
1215 /* Implementation of superedge::dump_label_to_pp for interprocedural
1219 callgraph_superedge::dump_label_to_pp (pretty_printer
*pp
,
1220 bool user_facing ATTRIBUTE_UNUSED
) const
1225 case SUPEREDGE_CFG_EDGE
:
1228 case SUPEREDGE_CALL
:
1229 pp_printf (pp
, "call");
1232 case SUPEREDGE_RETURN
:
1233 pp_printf (pp
, "return");
1236 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1237 pp_printf (pp
, "intraproc link");
1242 /* Get the function that was called at this interprocedural call/return
1246 callgraph_superedge::get_callee_function () const
1248 return get_ultimate_function_for_cgraph_edge (m_cedge
);
1251 /* Get the calling function at this interprocedural call/return edge. */
1254 callgraph_superedge::get_caller_function () const
1256 return m_cedge
->caller
->get_fun ();
1259 /* Get the fndecl that was called at this interprocedural call/return
1263 callgraph_superedge::get_callee_decl () const
1265 return get_callee_function ()->decl
;
1268 /* Get the gcall * of this interprocedural call/return edge. */
1271 callgraph_superedge::get_call_stmt () const
1274 return m_cedge
->call_stmt
;
1276 return m_src
->get_final_call ();
1279 /* Get the calling fndecl at this interprocedural call/return edge. */
1282 callgraph_superedge::get_caller_decl () const
1284 return get_caller_function ()->decl
;
1287 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1288 to *OUT if OUT is non-NULL), and return the corresponding argument
1292 callgraph_superedge::get_arg_for_parm (tree parm_to_find
,
1293 callsite_expr
*out
) const
1295 gcc_assert (TREE_CODE (parm_to_find
) == PARM_DECL
);
1297 tree callee
= get_callee_decl ();
1298 const gcall
*call_stmt
= get_call_stmt ();
1301 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1302 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1304 if (i
>= gimple_call_num_args (call_stmt
))
1306 if (iter_parm
== parm_to_find
)
1309 *out
= callsite_expr::from_zero_based_param (i
);
1310 return gimple_call_arg (call_stmt
, i
);
1318 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1319 If found, return the default SSA def of the corresponding parm within
1320 the callee, and if OUT is non-NULL, write the index to *OUT.
1321 Only the first match is handled. */
1324 callgraph_superedge::get_parm_for_arg (tree arg_to_find
,
1325 callsite_expr
*out
) const
1327 tree callee
= get_callee_decl ();
1328 const gcall
*call_stmt
= get_call_stmt ();
1331 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1332 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1334 if (i
>= gimple_call_num_args (call_stmt
))
1336 tree param
= gimple_call_arg (call_stmt
, i
);
1337 if (arg_to_find
== param
)
1340 *out
= callsite_expr::from_zero_based_param (i
);
1341 return ssa_default_def (get_callee_function (), iter_parm
);
1349 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1350 If non-NULL is returned, populate OUT. */
1353 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr
,
1354 callsite_expr
*out
) const
1356 /* Is it an argument (actual param)? If so, convert to
1357 parameter (formal param). */
1358 tree parm
= get_parm_for_arg (caller_expr
, out
);
1361 /* Otherwise try return value. */
1362 if (caller_expr
== gimple_call_lhs (get_call_stmt ()))
1365 *out
= callsite_expr::from_return_value ();
1366 return DECL_RESULT (get_callee_decl ());
1372 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1373 If non-NULL is returned, populate OUT. */
1376 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr
,
1377 callsite_expr
*out
) const
1379 if (callee_expr
== NULL_TREE
)
1382 /* If it's a parameter (formal param), get the argument (actual param). */
1383 if (TREE_CODE (callee_expr
) == PARM_DECL
)
1384 return get_arg_for_parm (callee_expr
, out
);
1386 /* Similar for the default SSA name of the PARM_DECL. */
1387 if (TREE_CODE (callee_expr
) == SSA_NAME
1388 && SSA_NAME_IS_DEFAULT_DEF (callee_expr
)
1389 && TREE_CODE (SSA_NAME_VAR (callee_expr
)) == PARM_DECL
)
1390 return get_arg_for_parm (SSA_NAME_VAR (callee_expr
), out
);
1392 /* Otherwise try return value. */
1393 if (callee_expr
== DECL_RESULT (get_callee_decl ()))
1396 *out
= callsite_expr::from_return_value ();
1397 return gimple_call_lhs (get_call_stmt ());
1405 #endif /* #if ENABLE_ANALYZER */