1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "hash-table.h"
30 #include "basic-block.h"
32 #include "gimple-fold.h"
34 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-pretty-print.h"
40 #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
, gimple
*stmt
)
79 gcall
*call
= dyn_cast
<gcall
*> (stmt
);
82 cgraph_edge
*edge
= cgraph_node::get (fun
->decl
)->get_edge (stmt
);
86 return NULL
; /* e.g. for a function pointer. */
87 if (!get_ultimate_function_for_cgraph_edge (edge
))
94 In order to ensure consistent results without relying on the ordering
95 of pointer values we assign a uid to each gimple stmt, globally unique
98 Normally, the stmt uids are a scratch space that each pass can freely
99 assign its own values to. However, in the case of LTO, the uids are
100 used to associate call stmts with callgraph edges between the WPA phase
101 (where the analyzer runs in LTO mode) and the LTRANS phase; if the
102 analyzer changes them in the WPA phase, it leads to errors when
103 streaming the code back in at LTRANS.
104 lto_prepare_function_for_streaming has code to renumber the stmt UIDs
105 when the code is streamed back out, but for some reason this isn't
108 Hence, as a workaround, this class has responsibility for tracking
109 the original uids and restoring them once the pass is complete
110 (in the supergraph dtor). */
112 /* Give STMT a globally unique uid, storing its original uid so it can
113 later be restored. */
116 saved_uids::make_uid_unique (gimple
*stmt
)
118 unsigned next_uid
= m_old_stmt_uids
.length ();
119 unsigned old_stmt_uid
= stmt
->uid
;
120 stmt
->uid
= next_uid
;
121 m_old_stmt_uids
.safe_push
122 (std::pair
<gimple
*, unsigned> (stmt
, old_stmt_uid
));
125 /* Restore the saved uids of all stmts. */
128 saved_uids::restore_uids () const
131 std::pair
<gimple
*, unsigned> *pair
;
132 FOR_EACH_VEC_ELT (m_old_stmt_uids
, i
, pair
)
133 pair
->first
->uid
= pair
->second
;
136 /* supergraph's ctor. Walk the callgraph, building supernodes for each
137 CFG basic block, splitting the basic blocks at callsites. Join
138 together the supernodes with interprocedural and intraprocedural
139 superedges as appropriate.
140 Assign UIDs to the gimple stmts. */
142 supergraph::supergraph (logger
*logger
)
144 auto_timevar
tv (TV_ANALYZER_SUPERGRAPH
);
148 /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
150 /* Sort the cgraph_nodes? */
152 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
154 function
*fun
= node
->get_fun ();
156 /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
157 the supergraph (by doing it per-function). */
158 auto_cfun
sentinel (fun
);
159 mark_dfs_back_edges ();
161 const int start_idx
= m_nodes
.length ();
164 FOR_ALL_BB_FN (bb
, fun
)
166 /* The initial supernode for the BB gets the phi nodes (if any). */
167 supernode
*node_for_stmts
= add_node (fun
, bb
, NULL
, phi_nodes (bb
));
168 m_bb_to_initial_node
.put (bb
, node_for_stmts
);
169 for (gphi_iterator gpi
= gsi_start_phis (bb
); !gsi_end_p (gpi
);
172 gimple
*stmt
= gsi_stmt (gpi
);
173 m_stmt_to_node_t
.put (stmt
, node_for_stmts
);
174 m_stmt_uids
.make_uid_unique (stmt
);
177 /* Append statements from BB to the current supernode, splitting
178 them into a new supernode at each call site; such call statements
179 appear in both supernodes (representing call and return). */
180 gimple_stmt_iterator gsi
;
181 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
183 gimple
*stmt
= gsi_stmt (gsi
);
184 node_for_stmts
->m_stmts
.safe_push (stmt
);
185 m_stmt_to_node_t
.put (stmt
, node_for_stmts
);
186 m_stmt_uids
.make_uid_unique (stmt
);
187 if (cgraph_edge
*edge
= supergraph_call_edge (fun
, stmt
))
189 m_cgraph_edge_to_caller_prev_node
.put(edge
, node_for_stmts
);
190 node_for_stmts
= add_node (fun
, bb
, as_a
<gcall
*> (stmt
),
192 m_cgraph_edge_to_caller_next_node
.put (edge
, node_for_stmts
);
196 // maybe call is via a function pointer
197 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
200 = cgraph_node::get (fun
->decl
)->get_edge (stmt
);
201 if (!edge
|| !edge
->callee
)
203 supernode
*old_node_for_stmts
= node_for_stmts
;
204 node_for_stmts
= add_node (fun
, bb
, call
, NULL
);
207 = new callgraph_superedge (old_node_for_stmts
,
209 SUPEREDGE_INTRAPROCEDURAL_CALL
,
217 m_bb_to_final_node
.put (bb
, node_for_stmts
);
220 const unsigned num_snodes
= m_nodes
.length () - start_idx
;
221 m_function_to_num_snodes
.put (fun
, num_snodes
);
225 const int end_idx
= m_nodes
.length () - 1;
226 logger
->log ("SN: %i...%i: function %qD",
227 start_idx
, end_idx
, fun
->decl
);
232 /* Second pass: make superedges. */
234 /* Make superedges for CFG edges. */
235 for (bb_to_node_t::iterator iter
= m_bb_to_final_node
.begin ();
236 iter
!= m_bb_to_final_node
.end ();
239 basic_block bb
= (*iter
).first
;
240 supernode
*src_supernode
= (*iter
).second
;
245 FOR_EACH_VEC_ELT (*bb
->succs
, idx
, cfg_edge
)
247 basic_block dest_cfg_block
= cfg_edge
->dest
;
248 supernode
*dest_supernode
249 = *m_bb_to_initial_node
.get (dest_cfg_block
);
250 cfg_superedge
*cfg_sedge
251 = add_cfg_edge (src_supernode
, dest_supernode
, cfg_edge
);
252 m_cfg_edge_to_cfg_superedge
.put (cfg_edge
, cfg_sedge
);
256 /* Make interprocedural superedges for calls. */
258 for (cgraph_edge_to_node_t::iterator iter
259 = m_cgraph_edge_to_caller_prev_node
.begin ();
260 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
263 cgraph_edge
*edge
= (*iter
).first
;
264 supernode
*caller_prev_supernode
= (*iter
).second
;
265 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
266 if (!callee_fn
|| !callee_fn
->cfg
)
268 basic_block callee_cfg_block
= ENTRY_BLOCK_PTR_FOR_FN (callee_fn
);
269 supernode
*callee_supernode
270 = *m_bb_to_initial_node
.get (callee_cfg_block
);
271 call_superedge
*sedge
272 = add_call_superedge (caller_prev_supernode
,
275 m_cgraph_edge_to_call_superedge
.put (edge
, sedge
);
279 /* Make interprocedural superedges for returns. */
281 for (cgraph_edge_to_node_t::iterator iter
282 = m_cgraph_edge_to_caller_next_node
.begin ();
283 iter
!= m_cgraph_edge_to_caller_next_node
.end ();
286 cgraph_edge
*edge
= (*iter
).first
;
287 supernode
*caller_next_supernode
= (*iter
).second
;
288 function
* callee_fn
= get_ultimate_function_for_cgraph_edge (edge
);
289 if (!callee_fn
|| !callee_fn
->cfg
)
291 basic_block callee_cfg_block
= EXIT_BLOCK_PTR_FOR_FN (callee_fn
);
292 supernode
*callee_supernode
293 = *m_bb_to_initial_node
.get (callee_cfg_block
);
294 return_superedge
*sedge
295 = add_return_superedge (callee_supernode
,
296 caller_next_supernode
,
298 m_cgraph_edge_to_return_superedge
.put (edge
, sedge
);
302 /* Make intraprocedural superedges linking the two halves of a call. */
304 for (cgraph_edge_to_node_t::iterator iter
305 = m_cgraph_edge_to_caller_prev_node
.begin ();
306 iter
!= m_cgraph_edge_to_caller_prev_node
.end ();
309 cgraph_edge
*edge
= (*iter
).first
;
310 supernode
*caller_prev_supernode
= (*iter
).second
;
311 supernode
*caller_next_supernode
312 = *m_cgraph_edge_to_caller_next_node
.get (edge
);
314 = new callgraph_superedge (caller_prev_supernode
,
315 caller_next_supernode
,
316 SUPEREDGE_INTRAPROCEDURAL_CALL
,
319 m_cgraph_edge_to_intraproc_superedge
.put (edge
, sedge
);
326 /* supergraph's dtor. Reset stmt uids. */
328 supergraph::~supergraph ()
330 m_stmt_uids
.restore_uids ();
333 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
334 Cluster the supernodes by function, then by BB from original CFG. */
337 supergraph::dump_dot_to_pp (pretty_printer
*pp
,
338 const dump_args_t
&dump_args
) const
340 graphviz_out
gv (pp
);
342 pp_string (pp
, "digraph \"");
343 pp_write_text_to_stream (pp
);
344 pp_string (pp
, "supergraph");
345 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/false);
346 pp_string (pp
, "\" {\n");
349 gv
.println ("overlap=false;");
350 gv
.println ("compound=true;");
352 /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
353 https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
356 /* Break out the supernodes into clusters by function. */
359 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
361 function
*fun
= node
->get_fun ();
362 const char *funcname
= function_name (fun
);
363 gv
.println ("subgraph \"cluster_%s\" {",
372 /* Break out the nodes into clusters by BB from original CFG. */
375 FOR_ALL_BB_FN (bb
, fun
)
377 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
379 gv
.println ("subgraph \"cluster_%s_bb_%i\" {",
380 funcname
, bb
->index
);
385 " label=\"bb: %i\";\n"),
389 // TODO: maybe keep an index per-function/per-bb to speed this up???
392 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
393 if (n
->m_fun
== fun
&& n
->m_bb
== bb
)
394 n
->dump_dot (&gv
, dump_args
);
396 if (dump_args
.m_flags
& SUPERGRAPH_DOT_SHOW_BBS
)
398 /* Terminate per-bb "subgraph" */
405 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
406 pp_string (pp
, "\t");
407 get_node_for_function_entry (fun
)->dump_dot_id (pp
);
408 pp_string (pp
, ":s -> ");
409 get_node_for_function_exit (fun
)->dump_dot_id (pp
);
410 pp_string (pp
, ":n [style=\"invis\",constraint=true];\n");
412 /* Terminate per-function "subgraph" */
421 FOR_EACH_VEC_ELT (m_edges
, i
, e
)
422 e
->dump_dot (&gv
, dump_args
);
424 /* Terminate "digraph" */
429 /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
432 supergraph::dump_dot_to_file (FILE *fp
, const dump_args_t
&dump_args
) const
434 pretty_printer
*pp
= global_dc
->printer
->clone ();
435 pp_show_color (pp
) = 0;
436 /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
437 trying to prettify things by showing the underlying var. */
438 pp_format_decoder (pp
) = default_tree_printer
;
440 pp
->buffer
->stream
= fp
;
441 dump_dot_to_pp (pp
, dump_args
);
446 /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
449 supergraph::dump_dot (const char *path
, const dump_args_t
&dump_args
) const
451 FILE *fp
= fopen (path
, "w");
452 dump_dot_to_file (fp
, dump_args
);
456 /* Return a new json::object of the form
457 {"nodes" : [objs for snodes],
458 "edges" : [objs for sedges]}. */
461 supergraph::to_json () const
463 json::object
*sgraph_obj
= new json::object ();
467 json::array
*nodes_arr
= new json::array ();
470 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
471 nodes_arr
->append (n
->to_json ());
472 sgraph_obj
->set ("nodes", nodes_arr
);
477 json::array
*edges_arr
= new json::array ();
480 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
481 edges_arr
->append (n
->to_json ());
482 sgraph_obj
->set ("edges", edges_arr
);
488 /* Create a supernode for BB within FUN and add it to this supergraph.
490 If RETURNING_CALL is non-NULL, the supernode represents the resumption
491 of the basic block after returning from that call.
493 If PHI_NODES is non-NULL, this is the initial supernode for the basic
494 block, and is responsible for any handling of the phi nodes. */
497 supergraph::add_node (function
*fun
, basic_block bb
, gcall
*returning_call
,
498 gimple_seq phi_nodes
)
500 supernode
*n
= new supernode (fun
, bb
, returning_call
, phi_nodes
,
502 m_nodes
.safe_push (n
);
506 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
507 adding it to this supergraph.
509 If the edge is for a switch statement, create a switch_cfg_superedge
513 supergraph::add_cfg_edge (supernode
*src
, supernode
*dest
, ::edge e
)
515 /* Special-case switch edges. */
516 gimple
*stmt
= src
->get_last_stmt ();
517 cfg_superedge
*new_edge
;
518 if (stmt
&& stmt
->code
== GIMPLE_SWITCH
)
519 new_edge
= new switch_cfg_superedge (src
, dest
, e
);
521 new_edge
= new cfg_superedge (src
, dest
, e
);
526 /* Create and add a call_superedge representing an interprocedural call
527 from SRC to DEST, using CEDGE. */
530 supergraph::add_call_superedge (supernode
*src
, supernode
*dest
,
533 call_superedge
*new_edge
= new call_superedge (src
, dest
, cedge
);
538 /* Create and add a return_superedge representing returning from an
539 interprocedural call, returning from SRC to DEST, using CEDGE. */
542 supergraph::add_return_superedge (supernode
*src
, supernode
*dest
,
545 return_superedge
*new_edge
= new return_superedge (src
, dest
, cedge
);
550 /* Implementation of dnode::dump_dot vfunc for supernodes.
552 Write a cluster for the node, and within it a .dot node showing
553 the phi nodes and stmts. Call into any node annotator from ARGS to
554 potentially add other records to the cluster. */
557 supernode::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
559 gv
->println ("subgraph cluster_node_%i {",
563 gv
->println("style=\"solid\";");
564 gv
->println("color=\"black\";");
565 gv
->println("fillcolor=\"lightgrey\";");
566 gv
->println("label=\"sn: %i (bb: %i)\";", m_index
, m_bb
->index
);
568 pretty_printer
*pp
= gv
->get_pp ();
570 if (args
.m_node_annotator
)
571 args
.m_node_annotator
->add_node_annotations (gv
, *this, false);
576 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
578 pp_string (pp
, "<TABLE BORDER=\"0\">");
579 pp_write_text_to_stream (pp
);
581 bool had_row
= false;
583 /* Give any annotator the chance to add its own per-node TR elements. */
584 if (args
.m_node_annotator
)
585 if (args
.m_node_annotator
->add_node_annotations (gv
, *this, true))
588 if (m_returning_call
)
591 pp_string (pp
, "returning call: ");
596 pp_gimple_stmt_1 (pp
, m_returning_call
, 0, (dump_flags_t
)0);
597 pp_write_text_as_html_like_dot_to_stream (pp
);
599 /* Give any annotator the chance to add per-stmt TD elements to
601 if (args
.m_node_annotator
)
602 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
606 /* Give any annotator the chance to add per-stmt TR elements. */
607 if (args
.m_node_annotator
)
608 args
.m_node_annotator
->add_stmt_annotations (gv
, m_returning_call
,
617 pp_string (pp
, "<TR><TD>ENTRY</TD></TR>");
624 pp_string (pp
, "<TR><TD>EXIT</TD></TR>");
630 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
631 !gsi_end_p (gpi
); gsi_next (&gpi
))
633 const gimple
*stmt
= gsi_stmt (gpi
);
636 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
637 pp_write_text_as_html_like_dot_to_stream (pp
);
639 /* Give any annotator the chance to add per-phi TD elements to
641 if (args
.m_node_annotator
)
642 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
645 /* Give any annotator the chance to add per-phi TR elements. */
646 if (args
.m_node_annotator
)
647 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
656 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
660 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
661 pp_write_text_as_html_like_dot_to_stream (pp
);
663 /* Give any annotator the chance to add per-stmt TD elements to
665 if (args
.m_node_annotator
)
666 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, true);
669 /* Give any annotator the chance to add per-stmt TR elements. */
670 if (args
.m_node_annotator
)
671 args
.m_node_annotator
->add_stmt_annotations (gv
, stmt
, false);
677 /* Give any annotator the chance to add additional per-node TR elements
678 to the end of the TABLE. */
679 if (args
.m_node_annotator
)
680 if (args
.m_node_annotator
->add_after_node_annotations (gv
, *this))
683 /* Graphviz requires a TABLE element to have at least one TR
684 (and each TR to have at least one TD). */
687 pp_string (pp
, "<TR><TD>(empty)</TD></TR>");
691 pp_string (pp
, "</TABLE>>];\n\n");
694 /* Terminate "subgraph" */
699 /* Write an ID for this node to PP, for use in .dot output. */
702 supernode::dump_dot_id (pretty_printer
*pp
) const
704 pp_printf (pp
, "node_%i", m_index
);
707 /* Return a new json::object of the form
711 "returning_call": optional str,
716 supernode::to_json () const
718 json::object
*snode_obj
= new json::object ();
720 snode_obj
->set ("idx", new json::integer_number (m_index
));
721 snode_obj
->set ("bb_idx", new json::integer_number (m_bb
->index
));
722 if (function
*fun
= get_function ())
723 snode_obj
->set ("fun", new json::string (function_name (fun
)));
725 if (m_returning_call
)
728 pp_format_decoder (&pp
) = default_tree_printer
;
729 pp_gimple_stmt_1 (&pp
, m_returning_call
, 0, (dump_flags_t
)0);
730 snode_obj
->set ("returning_call",
731 new json::string (pp_formatted_text (&pp
)));
736 json::array
*phi_arr
= new json::array ();
737 for (gphi_iterator gpi
= const_cast<supernode
*> (this)->start_phis ();
738 !gsi_end_p (gpi
); gsi_next (&gpi
))
740 const gimple
*stmt
= gsi_stmt (gpi
);
742 pp_format_decoder (&pp
) = default_tree_printer
;
743 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
744 phi_arr
->append (new json::string (pp_formatted_text (&pp
)));
746 snode_obj
->set ("phis", phi_arr
);
751 json::array
*stmt_arr
= new json::array ();
754 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
757 pp_format_decoder (&pp
) = default_tree_printer
;
758 pp_gimple_stmt_1 (&pp
, stmt
, 0, (dump_flags_t
)0);
759 stmt_arr
->append (new json::string (pp_formatted_text (&pp
)));
761 snode_obj
->set ("stmts", stmt_arr
);
767 /* Get a location_t for the start of this supernode. */
770 supernode::get_start_location () const
773 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
774 return m_returning_call
->location
;
778 FOR_EACH_VEC_ELT (m_stmts
, i
, stmt
)
779 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
780 return stmt
->location
;
784 // TWEAK: show the decl instead; this leads to more readable output:
785 return DECL_SOURCE_LOCATION (m_fun
->decl
);
787 return m_fun
->function_start_locus
;
790 return m_fun
->function_end_locus
;
792 return UNKNOWN_LOCATION
;
795 /* Get a location_t for the end of this supernode. */
798 supernode::get_end_location () const
802 FOR_EACH_VEC_ELT_REVERSE (m_stmts
, i
, stmt
)
803 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
804 return stmt
->location
;
807 && get_pure_location (m_returning_call
->location
) != UNKNOWN_LOCATION
)
808 return m_returning_call
->location
;
811 return m_fun
->function_start_locus
;
813 return m_fun
->function_end_locus
;
815 return UNKNOWN_LOCATION
;
818 /* Given STMT within this supernode, return its index within m_stmts. */
821 supernode::get_stmt_index (const gimple
*stmt
) const
825 FOR_EACH_VEC_ELT (m_stmts
, i
, iter_stmt
)
826 if (iter_stmt
== stmt
)
831 /* Get a string for PK. */
834 edge_kind_to_string (enum edge_kind kind
)
840 case SUPEREDGE_CFG_EDGE
:
841 return "SUPEREDGE_CFG_EDGE";
843 return "SUPEREDGE_CALL";
844 case SUPEREDGE_RETURN
:
845 return "SUPEREDGE_RETURN";
846 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
847 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
851 /* Dump this superedge to PP. */
854 superedge::dump (pretty_printer
*pp
) const
856 pp_printf (pp
, "edge: SN: %i -> SN: %i", m_src
->m_index
, m_dest
->m_index
);
857 char *desc
= get_description (false);
858 if (strlen (desc
) > 0)
861 pp_string (pp
, desc
);
866 /* Dump this superedge to stderr. */
869 superedge::dump () const
872 pp_format_decoder (&pp
) = default_tree_printer
;
873 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
874 pp
.buffer
->stream
= stderr
;
880 /* Implementation of dedge::dump_dot for superedges.
881 Write a .dot edge to GV representing this superedge. */
884 superedge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
886 const char *style
= "\"solid,bold\"";
887 const char *color
= "black";
889 const char *constraint
= "true";
895 case SUPEREDGE_CFG_EDGE
:
900 case SUPEREDGE_RETURN
:
903 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
904 style
= "\"dotted\"";
908 /* Adapted from graph.c:draw_cfg_node_succ_edges. */
909 if (::edge cfg_edge
= get_any_cfg_edge ())
911 if (cfg_edge
->flags
& EDGE_FAKE
)
917 else if (cfg_edge
->flags
& EDGE_DFS_BACK
)
919 style
= "\"dotted,bold\"";
923 else if (cfg_edge
->flags
& EDGE_FALLTHRU
)
929 if (cfg_edge
->flags
& EDGE_ABNORMAL
)
935 pretty_printer
*pp
= gv
->get_pp ();
937 m_src
->dump_dot_id (pp
);
938 pp_string (pp
, " -> ");
939 m_dest
->dump_dot_id (pp
);
941 (" [style=%s, color=%s, weight=%d, constraint=%s,"
942 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
944 style
, color
, weight
, constraint
,
945 m_src
->m_index
, m_dest
->m_index
);
947 dump_label_to_pp (pp
, false);
949 pp_printf (pp
, "\"];\n");
952 /* Return a new json::object of the form
954 "src_idx": int, the index of the source supernode,
955 "dst_idx": int, the index of the destination supernode,
959 superedge::to_json () const
961 json::object
*sedge_obj
= new json::object ();
962 sedge_obj
->set ("kind", new json::string (edge_kind_to_string (m_kind
)));
963 sedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
964 sedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
968 pp_format_decoder (&pp
) = default_tree_printer
;
969 dump_label_to_pp (&pp
, false);
970 sedge_obj
->set ("desc", new json::string (pp_formatted_text (&pp
)));
976 /* If this is an intraprocedural superedge, return the associated
977 CFG edge. Otherwise, return NULL. */
980 superedge::get_any_cfg_edge () const
982 if (const cfg_superedge
*sub
= dyn_cast_cfg_superedge ())
983 return sub
->get_cfg_edge ();
987 /* If this is an interprocedural superedge, return the associated
988 cgraph_edge *. Otherwise, return NULL. */
991 superedge::get_any_callgraph_edge () const
993 if (const callgraph_superedge
*sub
= dyn_cast_callgraph_superedge ())
998 /* Build a description of this superedge (e.g. "true" for the true
999 edge of a conditional, or "case 42:" for a switch case).
1001 The caller is responsible for freeing the result.
1003 If USER_FACING is false, the result also contains any underlying
1004 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1007 superedge::get_description (bool user_facing
) const
1010 dump_label_to_pp (&pp
, user_facing
);
1011 return xstrdup (pp_formatted_text (&pp
));
1014 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1017 For true/false edges, print "true" or "false" to PP.
1019 If USER_FACING is false, also print flags on the underlying CFG edge to
1023 cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1024 bool user_facing
) const
1026 if (true_value_p ())
1027 pp_printf (pp
, "true");
1028 else if (false_value_p ())
1029 pp_printf (pp
, "false");
1034 /* Express edge flags as a string with " | " separator.
1035 e.g. " (flags FALLTHRU | DFS_BACK)". */
1038 pp_string (pp
, " (flags ");
1039 bool seen_flag
= false;
1040 #define DEF_EDGE_FLAG(NAME,IDX) \
1042 if (get_flags () & EDGE_##NAME) \
1045 pp_string (pp, " | "); \
1046 pp_printf (pp, "%s", (#NAME)); \
1050 #include "cfg-flags.def"
1051 #undef DEF_EDGE_FLAG
1052 pp_string (pp
, ")");
1055 /* Otherwise, no label. */
1058 /* Get the index number for this edge for use in phi stmts
1059 in its destination. */
1062 cfg_superedge::get_phi_arg_idx () const
1064 return m_cfg_edge
->dest_idx
;
1067 /* Get the phi argument for PHI for this CFG edge. */
1070 cfg_superedge::get_phi_arg (const gphi
*phi
) const
1072 size_t index
= get_phi_arg_idx ();
1073 return gimple_phi_arg_def (phi
, index
);
1076 switch_cfg_superedge::switch_cfg_superedge (supernode
*src
,
1079 : cfg_superedge (src
, dst
, e
)
1081 /* Populate m_case_labels with all cases which go to DST. */
1082 const gswitch
*gswitch
= get_switch_stmt ();
1083 for (unsigned i
= 0; i
< gimple_switch_num_labels (gswitch
); i
++)
1085 tree case_
= gimple_switch_label (gswitch
, i
);
1086 basic_block bb
= label_to_block (src
->get_function (),
1087 CASE_LABEL (case_
));
1088 if (bb
== dst
->m_bb
)
1089 m_case_labels
.safe_push (case_
);
1093 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1094 "switch" statements.
1096 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1099 switch_cfg_superedge::dump_label_to_pp (pretty_printer
*pp
,
1100 bool user_facing ATTRIBUTE_UNUSED
) const
1104 for (unsigned i
= 0; i
< m_case_labels
.length (); ++i
)
1107 pp_string (pp
, ", ");
1108 tree case_label
= m_case_labels
[i
];
1109 gcc_assert (TREE_CODE (case_label
) == CASE_LABEL_EXPR
);
1110 tree lower_bound
= CASE_LOW (case_label
);
1111 tree upper_bound
= CASE_HIGH (case_label
);
1114 pp_printf (pp
, "case ");
1115 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1118 pp_printf (pp
, " ... ");
1119 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1122 pp_printf (pp
, ":");
1125 pp_printf (pp
, "default:");
1130 pp_character (pp
, '{');
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
);
1143 pp_character (pp
, '[');
1144 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0,
1146 pp_string (pp
, ", ");
1147 dump_generic_node (pp
, upper_bound
, 0, (dump_flags_t
)0,
1149 pp_character (pp
, ']');
1152 dump_generic_node (pp
, lower_bound
, 0, (dump_flags_t
)0, false);
1155 pp_printf (pp
, "default");
1157 pp_character (pp
, '}');
1161 /* Implementation of superedge::dump_label_to_pp for interprocedural
1165 callgraph_superedge::dump_label_to_pp (pretty_printer
*pp
,
1166 bool user_facing ATTRIBUTE_UNUSED
) const
1171 case SUPEREDGE_CFG_EDGE
:
1174 case SUPEREDGE_CALL
:
1175 pp_printf (pp
, "call");
1178 case SUPEREDGE_RETURN
:
1179 pp_printf (pp
, "return");
1182 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1183 pp_printf (pp
, "intraproc link");
1188 /* Get the function that was called at this interprocedural call/return
1192 callgraph_superedge::get_callee_function () const
1194 return get_ultimate_function_for_cgraph_edge (m_cedge
);
1197 /* Get the calling function at this interprocedural call/return edge. */
1200 callgraph_superedge::get_caller_function () const
1202 return m_cedge
->caller
->get_fun ();
1205 /* Get the fndecl that was called at this interprocedural call/return
1209 callgraph_superedge::get_callee_decl () const
1211 return get_callee_function ()->decl
;
1214 /* Get the gcall * of this interprocedural call/return edge. */
1217 callgraph_superedge::get_call_stmt () const
1220 return m_cedge
->call_stmt
;
1222 return m_src
->get_final_call ();
1225 /* Get the calling fndecl at this interprocedural call/return edge. */
1228 callgraph_superedge::get_caller_decl () const
1230 return get_caller_function ()->decl
;
1233 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1234 to *OUT if OUT is non-NULL), and return the corresponding argument
1238 callgraph_superedge::get_arg_for_parm (tree parm_to_find
,
1239 callsite_expr
*out
) const
1241 gcc_assert (TREE_CODE (parm_to_find
) == PARM_DECL
);
1243 tree callee
= get_callee_decl ();
1244 const gcall
*call_stmt
= get_call_stmt ();
1247 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1248 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1250 if (i
>= gimple_call_num_args (call_stmt
))
1252 if (iter_parm
== parm_to_find
)
1255 *out
= callsite_expr::from_zero_based_param (i
);
1256 return gimple_call_arg (call_stmt
, i
);
1264 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1265 If found, return the default SSA def of the corresponding parm within
1266 the callee, and if OUT is non-NULL, write the index to *OUT.
1267 Only the first match is handled. */
1270 callgraph_superedge::get_parm_for_arg (tree arg_to_find
,
1271 callsite_expr
*out
) const
1273 tree callee
= get_callee_decl ();
1274 const gcall
*call_stmt
= get_call_stmt ();
1277 for (tree iter_parm
= DECL_ARGUMENTS (callee
); iter_parm
;
1278 iter_parm
= DECL_CHAIN (iter_parm
), ++i
)
1280 if (i
>= gimple_call_num_args (call_stmt
))
1282 tree param
= gimple_call_arg (call_stmt
, i
);
1283 if (arg_to_find
== param
)
1286 *out
= callsite_expr::from_zero_based_param (i
);
1287 return ssa_default_def (get_callee_function (), iter_parm
);
1295 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1296 If non-NULL is returned, populate OUT. */
1299 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr
,
1300 callsite_expr
*out
) const
1302 /* Is it an argument (actual param)? If so, convert to
1303 parameter (formal param). */
1304 tree parm
= get_parm_for_arg (caller_expr
, out
);
1307 /* Otherwise try return value. */
1308 if (caller_expr
== gimple_call_lhs (get_call_stmt ()))
1311 *out
= callsite_expr::from_return_value ();
1312 return DECL_RESULT (get_callee_decl ());
1318 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1319 If non-NULL is returned, populate OUT. */
1322 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr
,
1323 callsite_expr
*out
) const
1325 if (callee_expr
== NULL_TREE
)
1328 /* If it's a parameter (formal param), get the argument (actual param). */
1329 if (TREE_CODE (callee_expr
) == PARM_DECL
)
1330 return get_arg_for_parm (callee_expr
, out
);
1332 /* Similar for the default SSA name of the PARM_DECL. */
1333 if (TREE_CODE (callee_expr
) == SSA_NAME
1334 && SSA_NAME_IS_DEFAULT_DEF (callee_expr
)
1335 && TREE_CODE (SSA_NAME_VAR (callee_expr
)) == PARM_DECL
)
1336 return get_arg_for_parm (SSA_NAME_VAR (callee_expr
), out
);
1338 /* Otherwise try return value. */
1339 if (callee_expr
== DECL_RESULT (get_callee_decl ()))
1342 *out
= callsite_expr::from_return_value ();
1343 return gimple_call_lhs (get_call_stmt ());
1351 #endif /* #if ENABLE_ANALYZER */