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>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#define INCLUDE_MEMORY
23#include "system.h"
24#include "coretypes.h"
25#include "tree.h"
26#include "tm.h"
27#include "toplev.h"
28#include "hash-table.h"
29#include "vec.h"
30#include "ggc.h"
31#include "basic-block.h"
32#include "function.h"
33#include "gimple.h"
34#include "gimple-iterator.h"
35#include "gimple-fold.h"
36#include "tree-eh.h"
37#include "gimple-expr.h"
38#include "is-a.h"
39#include "timevar.h"
40#include "gimple-pretty-print.h"
41#include "tree-pretty-print.h"
42#include "graphviz.h"
43#include "cgraph.h"
44#include "tree-dfa.h"
45#include "bitmap.h"
46#include "cfganal.h"
47#include "function.h"
48#include "analyzer/analyzer.h"
49#include "ordered-hash-map.h"
50#include "options.h"
51#include "cgraph.h"
52#include "cfg.h"
53#include "digraph.h"
54#include "tree-cfg.h"
55#include "analyzer/supergraph.h"
56#include "analyzer/analyzer-logging.h"
57
58#if ENABLE_ANALYZER
59
60namespace ana {
61
62/* Get the function of the ultimate alias target being called at EDGE,
63 if any. */
64
65function *
66get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
67{
68 cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
69 if (!ultimate_node)
70 return NULL;
71 return ultimate_node->get_fun ();
72}
73
74/* Get the cgraph_edge, but only if there's an underlying function body. */
75
76cgraph_edge *
77supergraph_call_edge (function *fun, const gimple *stmt)
78{
79 const gcall *call = dyn_cast<const gcall *> (p: stmt);
80 if (!call)
81 return NULL;
82 cgraph_edge *edge
83 = cgraph_node::get (decl: fun->decl)->get_edge (call_stmt: const_cast <gimple *> (stmt));
84 if (!edge)
85 return NULL;
86 if (!edge->callee)
87 return NULL; /* e.g. for a function pointer. */
88 if (!get_ultimate_function_for_cgraph_edge (edge))
89 return NULL;
90 return edge;
91}
92
93/* class saved_uids.
94
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
97 across all functions.
98
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
107 called for clones.
108
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). */
112
113/* Give STMT a globally unique uid, storing its original uid so it can
114 later be restored. */
115
116void
117saved_uids::make_uid_unique (gimple *stmt)
118{
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 (obj: std::pair<gimple *, unsigned> (stmt, old_stmt_uid));
124}
125
126/* Restore the saved uids of all stmts. */
127
128void
129saved_uids::restore_uids () const
130{
131 unsigned i;
132 std::pair<gimple *, unsigned> *pair;
133 FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
134 pair->first->uid = pair->second;
135}
136
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. */
142
143supergraph::supergraph (logger *logger)
144{
145 auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
146
147 LOG_FUNC (logger);
148
149 /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
150 {
151 /* Sort the cgraph_nodes? */
152 cgraph_node *node;
153 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
154 {
155 function *fun = node->get_fun ();
156
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 ();
161
162 const int start_idx = m_nodes.length ();
163
164 basic_block bb;
165 FOR_ALL_BB_FN (bb, fun)
166 {
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: phi_nodes (bb));
169 m_bb_to_initial_node.put (k: bb, v: node_for_stmts);
170 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (i: gpi);
171 gsi_next (i: &gpi))
172 {
173 gimple *stmt = gsi_stmt (i: gpi);
174 m_stmt_to_node_t.put (k: stmt, v: node_for_stmts);
175 m_stmt_uids.make_uid_unique (stmt);
176 }
177
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 (i: gsi); gsi_next (i: &gsi))
183 {
184 gimple *stmt = gsi_stmt (i: 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 (gs: stmt))
188 continue;
189 node_for_stmts->m_stmts.safe_push (obj: stmt);
190 m_stmt_to_node_t.put (k: stmt, v: node_for_stmts);
191 m_stmt_uids.make_uid_unique (stmt);
192 if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
193 {
194 m_cgraph_edge_to_caller_prev_node.put(k: edge, v: node_for_stmts);
195 node_for_stmts = add_node (fun, bb, returning_call: as_a <gcall *> (p: stmt),
196 NULL);
197 m_cgraph_edge_to_caller_next_node.put (k: edge, v: node_for_stmts);
198 }
199 else
200 {
201 // maybe call is via a function pointer
202 if (gcall *call = dyn_cast<gcall *> (p: stmt))
203 {
204 cgraph_edge *edge
205 = cgraph_node::get (decl: fun->decl)->get_edge (call_stmt: stmt);
206 if (!edge || !edge->callee)
207 {
208 supernode *old_node_for_stmts = node_for_stmts;
209 node_for_stmts = add_node (fun, bb, returning_call: call, NULL);
210
211 superedge *sedge
212 = new callgraph_superedge (old_node_for_stmts,
213 node_for_stmts,
214 SUPEREDGE_INTRAPROCEDURAL_CALL,
215 NULL);
216 add_edge (edge: sedge);
217 }
218 }
219 }
220 }
221
222 m_bb_to_final_node.put (k: bb, v: node_for_stmts);
223 }
224
225 const unsigned num_snodes = m_nodes.length () - start_idx;
226 m_function_to_num_snodes.put (k: fun, v: num_snodes);
227
228 if (logger)
229 {
230 const int end_idx = m_nodes.length () - 1;
231 logger->log (fmt: "SN: %i...%i: function %qD",
232 start_idx, end_idx, fun->decl);
233 }
234 }
235 }
236
237 /* Second pass: make superedges. */
238 {
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 ();
242 ++iter)
243 {
244 basic_block bb = (*iter).first;
245 supernode *src_supernode = (*iter).second;
246
247 ::edge cfg_edge;
248 int idx;
249 if (bb->succs)
250 FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
251 {
252 basic_block dest_cfg_block = cfg_edge->dest;
253 supernode *dest_supernode
254 = *m_bb_to_initial_node.get (k: dest_cfg_block);
255 cfg_superedge *cfg_sedge
256 = add_cfg_edge (src: src_supernode, dest: dest_supernode, e: cfg_edge);
257 m_cfg_edge_to_cfg_superedge.put (k: cfg_edge, v: cfg_sedge);
258 }
259 }
260
261 /* Make interprocedural superedges for calls. */
262 {
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 ();
266 ++iter)
267 {
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)
272 continue;
273 basic_block callee_cfg_block = ENTRY_BLOCK_PTR_FOR_FN (callee_fn);
274 supernode *callee_supernode
275 = *m_bb_to_initial_node.get (k: callee_cfg_block);
276 call_superedge *sedge
277 = add_call_superedge (src: caller_prev_supernode,
278 dest: callee_supernode,
279 cedge: edge);
280 m_cgraph_edge_to_call_superedge.put (k: edge, v: sedge);
281 }
282 }
283
284 /* Make interprocedural superedges for returns. */
285 {
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 ();
289 ++iter)
290 {
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)
295 continue;
296 basic_block callee_cfg_block = EXIT_BLOCK_PTR_FOR_FN (callee_fn);
297 supernode *callee_supernode
298 = *m_bb_to_initial_node.get (k: callee_cfg_block);
299 return_superedge *sedge
300 = add_return_superedge (src: callee_supernode,
301 dest: caller_next_supernode,
302 cedge: edge);
303 m_cgraph_edge_to_return_superedge.put (k: edge, v: sedge);
304 }
305 }
306
307 /* Make intraprocedural superedges linking the two halves of a call. */
308 {
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 ();
312 ++iter)
313 {
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 (k: edge);
318 superedge *sedge
319 = new callgraph_superedge (caller_prev_supernode,
320 caller_next_supernode,
321 SUPEREDGE_INTRAPROCEDURAL_CALL,
322 edge);
323 add_edge (edge: sedge);
324 m_cgraph_edge_to_intraproc_superedge.put (k: edge, v: sedge);
325 }
326
327 }
328 }
329}
330
331/* supergraph's dtor. Reset stmt uids. */
332
333supergraph::~supergraph ()
334{
335 m_stmt_uids.restore_uids ();
336}
337
338/* Dump this graph in .dot format to PP, using DUMP_ARGS.
339 Cluster the supernodes by function, then by BB from original CFG. */
340
341void
342supergraph::dump_dot_to_pp (pretty_printer *pp,
343 const dump_args_t &dump_args) const
344{
345 graphviz_out gv (pp);
346
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");
352 gv.indent ();
353
354 gv.println (fmt: "overlap=false;");
355 gv.println (fmt: "compound=true;");
356
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
359 */
360
361 /* Break out the supernodes into clusters by function. */
362 {
363 cgraph_node *node;
364 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
365 {
366 function *fun = node->get_fun ();
367 gcc_assert (fun);
368 const char *funcname = function_name (fun);
369 gv.println (fmt: "subgraph \"cluster_%s\" {",
370 funcname);
371 gv.indent ();
372 pp_printf (pp,
373 ("style=\"dashed\";"
374 " color=\"black\";"
375 " label=\"%s\";\n"),
376 funcname);
377
378 /* Break out the nodes into clusters by BB from original CFG. */
379 {
380 basic_block bb;
381 FOR_ALL_BB_FN (bb, fun)
382 {
383 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
384 {
385 gv.println (fmt: "subgraph \"cluster_%s_bb_%i\" {",
386 funcname, bb->index);
387 gv.indent ();
388 pp_printf (pp,
389 ("style=\"dashed\";"
390 " color=\"black\";"
391 " label=\"bb: %i\";\n"),
392 bb->index);
393 }
394
395 // TODO: maybe keep an index per-function/per-bb to speed this up???
396 int i;
397 supernode *n;
398 FOR_EACH_VEC_ELT (m_nodes, i, n)
399 if (n->m_fun == fun && n->m_bb == bb)
400 n->dump_dot (gv: &gv, args: dump_args);
401
402 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
403 {
404 /* Terminate per-bb "subgraph" */
405 gv.outdent ();
406 gv.println (fmt: "}");
407 }
408 }
409 }
410
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: *fun)->dump_dot_id (pp);
414 pp_string (pp, ":s -> ");
415 get_node_for_function_exit (fun: *fun)->dump_dot_id (pp);
416 pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
417
418 /* Terminate per-function "subgraph" */
419 gv.outdent ();
420 gv.println (fmt: "}");
421 }
422 }
423
424 /* Superedges. */
425 int i;
426 superedge *e;
427 FOR_EACH_VEC_ELT (m_edges, i, e)
428 e->dump_dot (gv: &gv, args: dump_args);
429
430 /* Terminate "digraph" */
431 gv.outdent ();
432 gv.println (fmt: "}");
433}
434
435/* Dump this graph in .dot format to FP, using DUMP_ARGS. */
436
437void
438supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
439{
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;
445
446 pp->buffer->stream = fp;
447 dump_dot_to_pp (pp, dump_args);
448 pp_flush (pp);
449 delete pp;
450}
451
452/* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
453
454void
455supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
456{
457 FILE *fp = fopen (filename: path, modes: "w");
458 dump_dot_to_file (fp, dump_args);
459 fclose (stream: fp);
460}
461
462/* Return a new json::object of the form
463 {"nodes" : [objs for snodes],
464 "edges" : [objs for sedges]}. */
465
466json::object *
467supergraph::to_json () const
468{
469 json::object *sgraph_obj = new json::object ();
470
471 /* Nodes. */
472 {
473 json::array *nodes_arr = new json::array ();
474 unsigned i;
475 supernode *n;
476 FOR_EACH_VEC_ELT (m_nodes, i, n)
477 nodes_arr->append (v: n->to_json ());
478 sgraph_obj->set (key: "nodes", v: nodes_arr);
479 }
480
481 /* Edges. */
482 {
483 json::array *edges_arr = new json::array ();
484 unsigned i;
485 superedge *n;
486 FOR_EACH_VEC_ELT (m_edges, i, n)
487 edges_arr->append (v: n->to_json ());
488 sgraph_obj->set (key: "edges", v: edges_arr);
489 }
490
491 return sgraph_obj;
492}
493
494/* Create a supernode for BB within FUN and add it to this supergraph.
495
496 If RETURNING_CALL is non-NULL, the supernode represents the resumption
497 of the basic block after returning from that call.
498
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. */
501
502supernode *
503supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
504 gimple_seq phi_nodes)
505{
506 supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
507 m_nodes.length ());
508 m_nodes.safe_push (obj: n);
509 return n;
510}
511
512/* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
513 adding it to this supergraph.
514
515 If the edge is for a switch statement, create a switch_cfg_superedge
516 subclass. */
517
518cfg_superedge *
519supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e)
520{
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);
526 else
527 new_edge = new cfg_superedge (src, dest, e);
528 add_edge (edge: new_edge);
529 return new_edge;
530}
531
532/* Create and add a call_superedge representing an interprocedural call
533 from SRC to DEST, using CEDGE. */
534
535call_superedge *
536supergraph::add_call_superedge (supernode *src, supernode *dest,
537 cgraph_edge *cedge)
538{
539 call_superedge *new_edge = new call_superedge (src, dest, cedge);
540 add_edge (edge: new_edge);
541 return new_edge;
542}
543
544/* Create and add a return_superedge representing returning from an
545 interprocedural call, returning from SRC to DEST, using CEDGE. */
546
547return_superedge *
548supergraph::add_return_superedge (supernode *src, supernode *dest,
549 cgraph_edge *cedge)
550{
551 return_superedge *new_edge = new return_superedge (src, dest, cedge);
552 add_edge (edge: new_edge);
553 return new_edge;
554}
555
556/* Implementation of dnode::dump_dot vfunc for supernodes.
557
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. */
561
562void
563supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
564{
565 gv->println (fmt: "subgraph cluster_node_%i {",
566 m_index);
567 gv->indent ();
568
569 gv->println(fmt: "style=\"solid\";");
570 gv->println(fmt: "color=\"black\";");
571 gv->println(fmt: "fillcolor=\"lightgrey\";");
572 gv->println(fmt: "label=\"sn: %i (bb: %i)\";", m_index, m_bb->index);
573
574 pretty_printer *pp = gv->get_pp ();
575
576 if (args.m_node_annotator)
577 args.m_node_annotator->add_node_annotations (gv, n: *this, within_table: false);
578
579 gv->write_indent ();
580 dump_dot_id (pp);
581 pp_printf (pp,
582 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
583 "lightgrey");
584 pp_string (pp, "<TABLE BORDER=\"0\">");
585 pp_write_text_to_stream (pp);
586
587 bool had_row = false;
588
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, n: *this, within_table: true))
592 had_row = true;
593
594 if (m_returning_call)
595 {
596 gv->begin_trtd ();
597 pp_string (pp, "returning call: ");
598 gv->end_tdtr ();
599
600 gv->begin_tr ();
601 gv->begin_td ();
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);
604 gv->end_td ();
605 /* Give any annotator the chance to add per-stmt TD elements to
606 this row. */
607 if (args.m_node_annotator)
608 args.m_node_annotator->add_stmt_annotations (gv, stmt: m_returning_call,
609 within_row: true);
610 gv->end_tr ();
611
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, stmt: m_returning_call,
615 within_row: false);
616 pp_newline (pp);
617
618 had_row = true;
619 }
620
621 if (entry_p ())
622 {
623 pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
624 pp_newline (pp);
625 had_row = true;
626 }
627
628 if (return_p ())
629 {
630 pp_string (pp, "<TR><TD>EXIT</TD></TR>");
631 pp_newline (pp);
632 had_row = true;
633 }
634
635 /* Phi nodes. */
636 for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
637 !gsi_end_p (i: gpi); gsi_next (i: &gpi))
638 {
639 const gimple *stmt = gsi_stmt (i: gpi);
640 gv->begin_tr ();
641 gv->begin_td ();
642 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
643 pp_write_text_as_html_like_dot_to_stream (pp);
644 gv->end_td ();
645 /* Give any annotator the chance to add per-phi TD elements to
646 this row. */
647 if (args.m_node_annotator)
648 args.m_node_annotator->add_stmt_annotations (gv, stmt, within_row: true);
649 gv->end_tr ();
650
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, within_row: false);
654
655 pp_newline (pp);
656 had_row = true;
657 }
658
659 /* Statements. */
660 int i;
661 gimple *stmt;
662 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
663 {
664 gv->begin_tr ();
665 gv->begin_td ();
666 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
667 pp_write_text_as_html_like_dot_to_stream (pp);
668 gv->end_td ();
669 /* Give any annotator the chance to add per-stmt TD elements to
670 this row. */
671 if (args.m_node_annotator)
672 args.m_node_annotator->add_stmt_annotations (gv, stmt, within_row: true);
673 gv->end_tr ();
674
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, within_row: false);
678
679 pp_newline (pp);
680 had_row = true;
681 }
682
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, n: *this))
687 had_row = true;
688
689 /* Graphviz requires a TABLE element to have at least one TR
690 (and each TR to have at least one TD). */
691 if (!had_row)
692 {
693 pp_string (pp, "<TR><TD>(empty)</TD></TR>");
694 pp_newline (pp);
695 }
696
697 pp_string (pp, "</TABLE>>];\n\n");
698 pp_flush (pp);
699
700 /* Terminate "subgraph" */
701 gv->outdent ();
702 gv->println (fmt: "}");
703}
704
705/* Write an ID for this node to PP, for use in .dot output. */
706
707void
708supernode::dump_dot_id (pretty_printer *pp) const
709{
710 pp_printf (pp, "node_%i", m_index);
711}
712
713/* Return a new json::object of the form
714 {"idx": int,
715 "fun": optional str
716 "bb_idx": int,
717 "returning_call": optional str,
718 "phis": [str],
719 "stmts" : [str]}. */
720
721json::object *
722supernode::to_json () const
723{
724 json::object *snode_obj = new json::object ();
725
726 snode_obj->set (key: "idx", v: new json::integer_number (m_index));
727 snode_obj->set (key: "bb_idx", v: new json::integer_number (m_bb->index));
728 if (function *fun = get_function ())
729 snode_obj->set (key: "fun", v: new json::string (function_name (fun)));
730
731 if (m_returning_call)
732 {
733 pretty_printer pp;
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 (key: "returning_call",
737 v: new json::string (pp_formatted_text (&pp)));
738 }
739
740 /* Phi nodes. */
741 {
742 json::array *phi_arr = new json::array ();
743 for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
744 !gsi_end_p (i: gpi); gsi_next (i: &gpi))
745 {
746 const gimple *stmt = gsi_stmt (i: gpi);
747 pretty_printer pp;
748 pp_format_decoder (&pp) = default_tree_printer;
749 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
750 phi_arr->append (v: new json::string (pp_formatted_text (&pp)));
751 }
752 snode_obj->set (key: "phis", v: phi_arr);
753 }
754
755 /* Statements. */
756 {
757 json::array *stmt_arr = new json::array ();
758 int i;
759 gimple *stmt;
760 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
761 {
762 pretty_printer pp;
763 pp_format_decoder (&pp) = default_tree_printer;
764 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
765 stmt_arr->append (v: new json::string (pp_formatted_text (&pp)));
766 }
767 snode_obj->set (key: "stmts", v: stmt_arr);
768 }
769
770 return snode_obj;
771}
772
773/* Get a location_t for the start of this supernode. */
774
775location_t
776supernode::get_start_location () const
777{
778 if (m_returning_call
779 && get_pure_location (loc: m_returning_call->location) != UNKNOWN_LOCATION)
780 return m_returning_call->location;
781
782 int i;
783 gimple *stmt;
784 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
785 if (get_pure_location (loc: stmt->location) != UNKNOWN_LOCATION)
786 return stmt->location;
787
788 if (entry_p ())
789 {
790 // TWEAK: show the decl instead; this leads to more readable output:
791 return DECL_SOURCE_LOCATION (m_fun->decl);
792
793 return m_fun->function_start_locus;
794 }
795 if (return_p ())
796 return m_fun->function_end_locus;
797
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 ();
804
805 return UNKNOWN_LOCATION;
806}
807
808/* Get a location_t for the end of this supernode. */
809
810location_t
811supernode::get_end_location () const
812{
813 int i;
814 gimple *stmt;
815 FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
816 if (get_pure_location (loc: stmt->location) != UNKNOWN_LOCATION)
817 return stmt->location;
818
819 if (m_returning_call
820 && get_pure_location (loc: m_returning_call->location) != UNKNOWN_LOCATION)
821 return m_returning_call->location;
822
823 if (entry_p ())
824 return m_fun->function_start_locus;
825 if (return_p ())
826 return m_fun->function_end_locus;
827
828 /* If we have a single out-edge that's a CFG edge, use the goto_locus of
829 that edge. */
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 ();
833
834 return UNKNOWN_LOCATION;
835}
836
837/* Given STMT within this supernode, return its index within m_stmts. */
838
839unsigned int
840supernode::get_stmt_index (const gimple *stmt) const
841{
842 unsigned i;
843 gimple *iter_stmt;
844 FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
845 if (iter_stmt == stmt)
846 return i;
847 gcc_unreachable ();
848}
849
850/* Get any label_decl for this supernode, or NULL_TREE if there isn't one. */
851
852tree
853supernode::get_label () const
854{
855 if (m_stmts.length () == 0)
856 return NULL_TREE;
857 const glabel *label_stmt = dyn_cast<const glabel *> (p: m_stmts[0]);
858 if (!label_stmt)
859 return NULL_TREE;
860 return gimple_label_label (gs: label_stmt);
861}
862
863/* Get a string for PK. */
864
865static const char *
866edge_kind_to_string (enum edge_kind kind)
867{
868 switch (kind)
869 {
870 default:
871 gcc_unreachable ();
872 case SUPEREDGE_CFG_EDGE:
873 return "SUPEREDGE_CFG_EDGE";
874 case SUPEREDGE_CALL:
875 return "SUPEREDGE_CALL";
876 case SUPEREDGE_RETURN:
877 return "SUPEREDGE_RETURN";
878 case SUPEREDGE_INTRAPROCEDURAL_CALL:
879 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
880 }
881};
882
883/* Dump this superedge to PP. */
884
885void
886superedge::dump (pretty_printer *pp) const
887{
888 pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_index, m_dest->m_index);
889 label_text desc (get_description (user_facing: false));
890 if (strlen (s: desc.get ()) > 0)
891 {
892 pp_space (pp);
893 pp_string (pp, desc.get ());
894 }
895}
896
897/* Dump this superedge to stderr. */
898
899DEBUG_FUNCTION void
900superedge::dump () const
901{
902 pretty_printer pp;
903 pp_format_decoder (&pp) = default_tree_printer;
904 pp_show_color (&pp) = pp_show_color (global_dc->printer);
905 pp.buffer->stream = stderr;
906 dump (pp: &pp);
907 pp_newline (&pp);
908 pp_flush (&pp);
909}
910
911/* Implementation of dedge::dump_dot for superedges.
912 Write a .dot edge to GV representing this superedge. */
913
914void
915superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
916{
917 const char *style = "\"solid,bold\"";
918 const char *color = "black";
919 int weight = 10;
920 const char *constraint = "true";
921
922 switch (m_kind)
923 {
924 default:
925 gcc_unreachable ();
926 case SUPEREDGE_CFG_EDGE:
927 break;
928 case SUPEREDGE_CALL:
929 color = "red";
930 break;
931 case SUPEREDGE_RETURN:
932 color = "green";
933 break;
934 case SUPEREDGE_INTRAPROCEDURAL_CALL:
935 style = "\"dotted\"";
936 break;
937 }
938
939 /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
940 if (::edge cfg_edge = get_any_cfg_edge ())
941 {
942 if (cfg_edge->flags & EDGE_FAKE)
943 {
944 style = "dotted";
945 color = "green";
946 weight = 0;
947 }
948 else if (cfg_edge->flags & EDGE_DFS_BACK)
949 {
950 style = "\"dotted,bold\"";
951 color = "blue";
952 weight = 10;
953 }
954 else if (cfg_edge->flags & EDGE_FALLTHRU)
955 {
956 color = "blue";
957 weight = 100;
958 }
959
960 if (cfg_edge->flags & EDGE_ABNORMAL)
961 color = "red";
962 }
963
964 gv->write_indent ();
965
966 pretty_printer *pp = gv->get_pp ();
967
968 m_src->dump_dot_id (pp);
969 pp_string (pp, " -> ");
970 m_dest->dump_dot_id (pp);
971 pp_printf (pp,
972 (" [style=%s, color=%s, weight=%d, constraint=%s,"
973 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
974 " headlabel=\""),
975 style, color, weight, constraint,
976 m_src->m_index, m_dest->m_index);
977
978 dump_label_to_pp (pp, user_facing: false);
979
980 pp_printf (pp, "\"];\n");
981}
982
983/* Return a new json::object of the form
984 {"kind" : str,
985 "src_idx": int, the index of the source supernode,
986 "dst_idx": int, the index of the destination supernode,
987 "desc" : str. */
988
989json::object *
990superedge::to_json () const
991{
992 json::object *sedge_obj = new json::object ();
993 sedge_obj->set (key: "kind", v: new json::string (edge_kind_to_string (kind: m_kind)));
994 sedge_obj->set (key: "src_idx", v: new json::integer_number (m_src->m_index));
995 sedge_obj->set (key: "dst_idx", v: new json::integer_number (m_dest->m_index));
996
997 {
998 pretty_printer pp;
999 pp_format_decoder (&pp) = default_tree_printer;
1000 dump_label_to_pp (pp: &pp, user_facing: false);
1001 sedge_obj->set (key: "desc", v: new json::string (pp_formatted_text (&pp)));
1002 }
1003
1004 return sedge_obj;
1005}
1006
1007/* If this is an intraprocedural superedge, return the associated
1008 CFG edge. Otherwise, return NULL. */
1009
1010::edge
1011superedge::get_any_cfg_edge () const
1012{
1013 if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
1014 return sub->get_cfg_edge ();
1015 return NULL;
1016}
1017
1018/* If this is an interprocedural superedge, return the associated
1019 cgraph_edge *. Otherwise, return NULL. */
1020
1021cgraph_edge *
1022superedge::get_any_callgraph_edge () const
1023{
1024 if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
1025 return sub->m_cedge;
1026 return NULL;
1027}
1028
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).
1031
1032 If USER_FACING is false, the result also contains any underlying
1033 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1034
1035label_text
1036superedge::get_description (bool user_facing) const
1037{
1038 pretty_printer pp;
1039 dump_label_to_pp (pp: &pp, user_facing);
1040 return label_text::take (buffer: xstrdup (pp_formatted_text (&pp)));
1041}
1042
1043/* Implementation of superedge::dump_label_to_pp for non-switch CFG
1044 superedges.
1045
1046 For true/false edges, print "true" or "false" to PP.
1047
1048 If USER_FACING is false, also print flags on the underlying CFG edge to
1049 PP. */
1050
1051void
1052cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1053 bool user_facing) const
1054{
1055 if (true_value_p ())
1056 pp_printf (pp, "true");
1057 else if (false_value_p ())
1058 pp_printf (pp, "false");
1059
1060 if (user_facing)
1061 return;
1062
1063 /* Express edge flags as a string with " | " separator.
1064 e.g. " (flags FALLTHRU | DFS_BACK)". */
1065 if (get_flags ())
1066 {
1067 pp_string (pp, " (flags ");
1068 bool seen_flag = false;
1069#define DEF_EDGE_FLAG(NAME,IDX) \
1070 do { \
1071 if (get_flags () & EDGE_##NAME) \
1072 { \
1073 if (seen_flag) \
1074 pp_string (pp, " | "); \
1075 pp_printf (pp, "%s", (#NAME)); \
1076 seen_flag = true; \
1077 } \
1078 } while (0);
1079#include "cfg-flags.def"
1080#undef DEF_EDGE_FLAG
1081 pp_string (pp, ")");
1082 }
1083
1084 if (m_cfg_edge->goto_locus > BUILTINS_LOCATION)
1085 pp_string (pp, " (has goto_locus)");
1086
1087 /* Otherwise, no label. */
1088}
1089
1090/* Get the index number for this edge for use in phi stmts
1091 in its destination. */
1092
1093size_t
1094cfg_superedge::get_phi_arg_idx () const
1095{
1096 return m_cfg_edge->dest_idx;
1097}
1098
1099/* Get the phi argument for PHI for this CFG edge. */
1100
1101tree
1102cfg_superedge::get_phi_arg (const gphi *phi) const
1103{
1104 size_t index = get_phi_arg_idx ();
1105 return gimple_phi_arg_def (gs: phi, index);
1106}
1107
1108switch_cfg_superedge::switch_cfg_superedge (supernode *src,
1109 supernode *dst,
1110 ::edge e)
1111: cfg_superedge (src, dst, e)
1112{
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 (gs: gswitch); i++)
1116 {
1117 tree case_ = gimple_switch_label (gs: gswitch, index: 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 (obj: case_);
1122 }
1123}
1124
1125/* Implementation of superedge::dump_label_to_pp for CFG superedges for
1126 "switch" statements.
1127
1128 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1129
1130void
1131switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1132 bool user_facing ATTRIBUTE_UNUSED) const
1133{
1134 if (user_facing)
1135 {
1136 for (unsigned i = 0; i < m_case_labels.length (); ++i)
1137 {
1138 if (i > 0)
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);
1144 if (lower_bound)
1145 {
1146 pp_printf (pp, "case ");
1147 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1148 if (upper_bound)
1149 {
1150 pp_printf (pp, " ... ");
1151 dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1152 false);
1153 }
1154 pp_printf (pp, ":");
1155 }
1156 else
1157 pp_printf (pp, "default:");
1158 }
1159 }
1160 else
1161 {
1162 pp_character (pp, '{');
1163 for (unsigned i = 0; i < m_case_labels.length (); ++i)
1164 {
1165 if (i > 0)
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);
1171 if (lower_bound)
1172 {
1173 if (upper_bound)
1174 {
1175 pp_character (pp, '[');
1176 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0,
1177 false);
1178 pp_string (pp, ", ");
1179 dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1180 false);
1181 pp_character (pp, ']');
1182 }
1183 else
1184 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1185 }
1186 else
1187 pp_printf (pp, "default");
1188 }
1189 pp_character (pp, '}');
1190 if (implicitly_created_default_p ())
1191 {
1192 pp_string (pp, " IMPLICITLY CREATED");
1193 }
1194 }
1195}
1196
1197/* Return true iff this edge is purely for an implicitly-created "default". */
1198
1199bool
1200switch_cfg_superedge::implicitly_created_default_p () const
1201{
1202 if (m_case_labels.length () != 1)
1203 return false;
1204
1205 tree case_label = m_case_labels[0];
1206 gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
1207 if (CASE_LOW (case_label))
1208 return false;
1209
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;
1213}
1214
1215/* Implementation of superedge::dump_label_to_pp for interprocedural
1216 superedges. */
1217
1218void
1219callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
1220 bool user_facing ATTRIBUTE_UNUSED) const
1221{
1222 switch (m_kind)
1223 {
1224 default:
1225 case SUPEREDGE_CFG_EDGE:
1226 gcc_unreachable ();
1227
1228 case SUPEREDGE_CALL:
1229 pp_printf (pp, "call");
1230 break;
1231
1232 case SUPEREDGE_RETURN:
1233 pp_printf (pp, "return");
1234 break;
1235
1236 case SUPEREDGE_INTRAPROCEDURAL_CALL:
1237 pp_printf (pp, "intraproc link");
1238 break;
1239 }
1240}
1241
1242/* Get the function that was called at this interprocedural call/return
1243 edge. */
1244
1245function *
1246callgraph_superedge::get_callee_function () const
1247{
1248 return get_ultimate_function_for_cgraph_edge (edge: m_cedge);
1249}
1250
1251/* Get the calling function at this interprocedural call/return edge. */
1252
1253function *
1254callgraph_superedge::get_caller_function () const
1255{
1256 return m_cedge->caller->get_fun ();
1257}
1258
1259/* Get the fndecl that was called at this interprocedural call/return
1260 edge. */
1261
1262tree
1263callgraph_superedge::get_callee_decl () const
1264{
1265 return get_callee_function ()->decl;
1266}
1267
1268/* Get the gcall * of this interprocedural call/return edge. */
1269
1270gcall *
1271callgraph_superedge::get_call_stmt () const
1272{
1273 if (m_cedge)
1274 return m_cedge->call_stmt;
1275
1276 return m_src->get_final_call ();
1277}
1278
1279/* Get the calling fndecl at this interprocedural call/return edge. */
1280
1281tree
1282callgraph_superedge::get_caller_decl () const
1283{
1284 return get_caller_function ()->decl;
1285}
1286
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
1289 at the callsite. */
1290
1291tree
1292callgraph_superedge::get_arg_for_parm (tree parm_to_find,
1293 callsite_expr *out) const
1294{
1295 gcc_assert (TREE_CODE (parm_to_find) == PARM_DECL);
1296
1297 tree callee = get_callee_decl ();
1298 const gcall *call_stmt = get_call_stmt ();
1299
1300 unsigned i = 0;
1301 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1302 iter_parm = DECL_CHAIN (iter_parm), ++i)
1303 {
1304 if (i >= gimple_call_num_args (gs: call_stmt))
1305 return NULL_TREE;
1306 if (iter_parm == parm_to_find)
1307 {
1308 if (out)
1309 *out = callsite_expr::from_zero_based_param (idx: i);
1310 return gimple_call_arg (gs: call_stmt, index: i);
1311 }
1312 }
1313
1314 /* Not found. */
1315 return NULL_TREE;
1316}
1317
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. */
1322
1323tree
1324callgraph_superedge::get_parm_for_arg (tree arg_to_find,
1325 callsite_expr *out) const
1326{
1327 tree callee = get_callee_decl ();
1328 const gcall *call_stmt = get_call_stmt ();
1329
1330 unsigned i = 0;
1331 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1332 iter_parm = DECL_CHAIN (iter_parm), ++i)
1333 {
1334 if (i >= gimple_call_num_args (gs: call_stmt))
1335 return NULL_TREE;
1336 tree param = gimple_call_arg (gs: call_stmt, index: i);
1337 if (arg_to_find == param)
1338 {
1339 if (out)
1340 *out = callsite_expr::from_zero_based_param (idx: i);
1341 return ssa_default_def (get_callee_function (), iter_parm);
1342 }
1343 }
1344
1345 /* Not found. */
1346 return NULL_TREE;
1347}
1348
1349/* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1350 If non-NULL is returned, populate OUT. */
1351
1352tree
1353callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
1354 callsite_expr *out) const
1355{
1356 /* Is it an argument (actual param)? If so, convert to
1357 parameter (formal param). */
1358 tree parm = get_parm_for_arg (arg_to_find: caller_expr, out);
1359 if (parm)
1360 return parm;
1361 /* Otherwise try return value. */
1362 if (caller_expr == gimple_call_lhs (gs: get_call_stmt ()))
1363 {
1364 if (out)
1365 *out = callsite_expr::from_return_value ();
1366 return DECL_RESULT (get_callee_decl ());
1367 }
1368
1369 return NULL_TREE;
1370}
1371
1372/* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1373 If non-NULL is returned, populate OUT. */
1374
1375tree
1376callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
1377 callsite_expr *out) const
1378{
1379 if (callee_expr == NULL_TREE)
1380 return NULL_TREE;
1381
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 (parm_to_find: callee_expr, out);
1385
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);
1391
1392 /* Otherwise try return value. */
1393 if (callee_expr == DECL_RESULT (get_callee_decl ()))
1394 {
1395 if (out)
1396 *out = callsite_expr::from_return_value ();
1397 return gimple_call_lhs (gs: get_call_stmt ());
1398 }
1399
1400 return NULL_TREE;
1401}
1402
1403} // namespace ana
1404
1405#endif /* #if ENABLE_ANALYZER */
1406

source code of gcc/analyzer/supergraph.cc