1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5 This file is part of GCC.
6
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)
10 any later version.
11
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.
16
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/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "tm.h"
26 #include "toplev.h"
27 #include "hash-table.h"
28 #include "vec.h"
29 #include "ggc.h"
30 #include "basic-block.h"
31 #include "function.h"
32 #include "gimple-fold.h"
33 #include "tree-eh.h"
34 #include "gimple-expr.h"
35 #include "is-a.h"
36 #include "timevar.h"
37 #include "gimple.h"
38 #include "gimple-iterator.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-pretty-print.h"
41 #include "graphviz.h"
42 #include "cgraph.h"
43 #include "tree-dfa.h"
44 #include "bitmap.h"
45 #include "cfganal.h"
46 #include "function.h"
47 #include "json.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
60 namespace ana {
61
62 /* Get the function of the ultimate alias target being called at EDGE,
63 if any. */
64
65 static function *
get_ultimate_function_for_cgraph_edge(cgraph_edge * edge)66 get_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
76 cgraph_edge *
supergraph_call_edge(function * fun,gimple * stmt)77 supergraph_call_edge (function *fun, gimple *stmt)
78 {
79 gcall *call = dyn_cast<gcall *> (stmt);
80 if (!call)
81 return NULL;
82 cgraph_edge *edge = cgraph_node::get (fun->decl)->get_edge (stmt);
83 if (!edge)
84 return NULL;
85 if (!edge->callee)
86 return NULL; /* e.g. for a function pointer. */
87 if (!get_ultimate_function_for_cgraph_edge (edge))
88 return NULL;
89 return edge;
90 }
91
92 /* class saved_uids.
93
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
96 across all functions.
97
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
106 called for clones.
107
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). */
111
112 /* Give STMT a globally unique uid, storing its original uid so it can
113 later be restored. */
114
115 void
make_uid_unique(gimple * stmt)116 saved_uids::make_uid_unique (gimple *stmt)
117 {
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));
123 }
124
125 /* Restore the saved uids of all stmts. */
126
127 void
restore_uids() const128 saved_uids::restore_uids () const
129 {
130 unsigned i;
131 std::pair<gimple *, unsigned> *pair;
132 FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
133 pair->first->uid = pair->second;
134 }
135
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. */
141
supergraph(logger * logger)142 supergraph::supergraph (logger *logger)
143 {
144 auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
145
146 LOG_FUNC (logger);
147
148 /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
149 {
150 /* Sort the cgraph_nodes? */
151 cgraph_node *node;
152 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
153 {
154 function *fun = node->get_fun ();
155
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 ();
160
161 const int start_idx = m_nodes.length ();
162
163 basic_block bb;
164 FOR_ALL_BB_FN (bb, fun)
165 {
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);
170 gsi_next (&gpi))
171 {
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);
175 }
176
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))
182 {
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))
188 {
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),
191 NULL);
192 m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
193 }
194 else
195 {
196 // maybe call is via a function pointer
197 if (gcall *call = dyn_cast<gcall *> (stmt))
198 {
199 cgraph_edge *edge
200 = cgraph_node::get (fun->decl)->get_edge (stmt);
201 if (!edge || !edge->callee)
202 {
203 supernode *old_node_for_stmts = node_for_stmts;
204 node_for_stmts = add_node (fun, bb, call, NULL);
205
206 superedge *sedge
207 = new callgraph_superedge (old_node_for_stmts,
208 node_for_stmts,
209 SUPEREDGE_INTRAPROCEDURAL_CALL,
210 NULL);
211 add_edge (sedge);
212 }
213 }
214 }
215 }
216
217 m_bb_to_final_node.put (bb, node_for_stmts);
218 }
219
220 const unsigned num_snodes = m_nodes.length () - start_idx;
221 m_function_to_num_snodes.put (fun, num_snodes);
222
223 if (logger)
224 {
225 const int end_idx = m_nodes.length () - 1;
226 logger->log ("SN: %i...%i: function %qD",
227 start_idx, end_idx, fun->decl);
228 }
229 }
230 }
231
232 /* Second pass: make superedges. */
233 {
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 ();
237 ++iter)
238 {
239 basic_block bb = (*iter).first;
240 supernode *src_supernode = (*iter).second;
241
242 ::edge cfg_edge;
243 int idx;
244 if (bb->succs)
245 FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
246 {
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);
253 }
254 }
255
256 /* Make interprocedural superedges for calls. */
257 {
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 ();
261 ++iter)
262 {
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)
267 continue;
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,
273 callee_supernode,
274 edge);
275 m_cgraph_edge_to_call_superedge.put (edge, sedge);
276 }
277 }
278
279 /* Make interprocedural superedges for returns. */
280 {
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 ();
284 ++iter)
285 {
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)
290 continue;
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,
297 edge);
298 m_cgraph_edge_to_return_superedge.put (edge, sedge);
299 }
300 }
301
302 /* Make intraprocedural superedges linking the two halves of a call. */
303 {
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 ();
307 ++iter)
308 {
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);
313 superedge *sedge
314 = new callgraph_superedge (caller_prev_supernode,
315 caller_next_supernode,
316 SUPEREDGE_INTRAPROCEDURAL_CALL,
317 edge);
318 add_edge (sedge);
319 m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
320 }
321
322 }
323 }
324 }
325
326 /* supergraph's dtor. Reset stmt uids. */
327
~supergraph()328 supergraph::~supergraph ()
329 {
330 m_stmt_uids.restore_uids ();
331 }
332
333 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
334 Cluster the supernodes by function, then by BB from original CFG. */
335
336 void
dump_dot_to_pp(pretty_printer * pp,const dump_args_t & dump_args) const337 supergraph::dump_dot_to_pp (pretty_printer *pp,
338 const dump_args_t &dump_args) const
339 {
340 graphviz_out gv (pp);
341
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");
347 gv.indent ();
348
349 gv.println ("overlap=false;");
350 gv.println ("compound=true;");
351
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
354 */
355
356 /* Break out the supernodes into clusters by function. */
357 {
358 cgraph_node *node;
359 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
360 {
361 function *fun = node->get_fun ();
362 const char *funcname = function_name (fun);
363 gv.println ("subgraph \"cluster_%s\" {",
364 funcname);
365 gv.indent ();
366 pp_printf (pp,
367 ("style=\"dashed\";"
368 " color=\"black\";"
369 " label=\"%s\";\n"),
370 funcname);
371
372 /* Break out the nodes into clusters by BB from original CFG. */
373 {
374 basic_block bb;
375 FOR_ALL_BB_FN (bb, fun)
376 {
377 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
378 {
379 gv.println ("subgraph \"cluster_%s_bb_%i\" {",
380 funcname, bb->index);
381 gv.indent ();
382 pp_printf (pp,
383 ("style=\"dashed\";"
384 " color=\"black\";"
385 " label=\"bb: %i\";\n"),
386 bb->index);
387 }
388
389 // TODO: maybe keep an index per-function/per-bb to speed this up???
390 int i;
391 supernode *n;
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);
395
396 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
397 {
398 /* Terminate per-bb "subgraph" */
399 gv.outdent ();
400 gv.println ("}");
401 }
402 }
403 }
404
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");
411
412 /* Terminate per-function "subgraph" */
413 gv.outdent ();
414 gv.println ("}");
415 }
416 }
417
418 /* Superedges. */
419 int i;
420 superedge *e;
421 FOR_EACH_VEC_ELT (m_edges, i, e)
422 e->dump_dot (&gv, dump_args);
423
424 /* Terminate "digraph" */
425 gv.outdent ();
426 gv.println ("}");
427 }
428
429 /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
430
431 void
dump_dot_to_file(FILE * fp,const dump_args_t & dump_args) const432 supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
433 {
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;
439
440 pp->buffer->stream = fp;
441 dump_dot_to_pp (pp, dump_args);
442 pp_flush (pp);
443 delete pp;
444 }
445
446 /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
447
448 void
dump_dot(const char * path,const dump_args_t & dump_args) const449 supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
450 {
451 FILE *fp = fopen (path, "w");
452 dump_dot_to_file (fp, dump_args);
453 fclose (fp);
454 }
455
456 /* Return a new json::object of the form
457 {"nodes" : [objs for snodes],
458 "edges" : [objs for sedges]}. */
459
460 json::object *
to_json() const461 supergraph::to_json () const
462 {
463 json::object *sgraph_obj = new json::object ();
464
465 /* Nodes. */
466 {
467 json::array *nodes_arr = new json::array ();
468 unsigned i;
469 supernode *n;
470 FOR_EACH_VEC_ELT (m_nodes, i, n)
471 nodes_arr->append (n->to_json ());
472 sgraph_obj->set ("nodes", nodes_arr);
473 }
474
475 /* Edges. */
476 {
477 json::array *edges_arr = new json::array ();
478 unsigned i;
479 superedge *n;
480 FOR_EACH_VEC_ELT (m_edges, i, n)
481 edges_arr->append (n->to_json ());
482 sgraph_obj->set ("edges", edges_arr);
483 }
484
485 return sgraph_obj;
486 }
487
488 /* Create a supernode for BB within FUN and add it to this supergraph.
489
490 If RETURNING_CALL is non-NULL, the supernode represents the resumption
491 of the basic block after returning from that call.
492
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. */
495
496 supernode *
add_node(function * fun,basic_block bb,gcall * returning_call,gimple_seq phi_nodes)497 supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
498 gimple_seq phi_nodes)
499 {
500 supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
501 m_nodes.length ());
502 m_nodes.safe_push (n);
503 return n;
504 }
505
506 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
507 adding it to this supergraph.
508
509 If the edge is for a switch statement, create a switch_cfg_superedge
510 subclass. */
511
512 cfg_superedge *
add_cfg_edge(supernode * src,supernode * dest,::edge e)513 supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e)
514 {
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);
520 else
521 new_edge = new cfg_superedge (src, dest, e);
522 add_edge (new_edge);
523 return new_edge;
524 }
525
526 /* Create and add a call_superedge representing an interprocedural call
527 from SRC to DEST, using CEDGE. */
528
529 call_superedge *
add_call_superedge(supernode * src,supernode * dest,cgraph_edge * cedge)530 supergraph::add_call_superedge (supernode *src, supernode *dest,
531 cgraph_edge *cedge)
532 {
533 call_superedge *new_edge = new call_superedge (src, dest, cedge);
534 add_edge (new_edge);
535 return new_edge;
536 }
537
538 /* Create and add a return_superedge representing returning from an
539 interprocedural call, returning from SRC to DEST, using CEDGE. */
540
541 return_superedge *
add_return_superedge(supernode * src,supernode * dest,cgraph_edge * cedge)542 supergraph::add_return_superedge (supernode *src, supernode *dest,
543 cgraph_edge *cedge)
544 {
545 return_superedge *new_edge = new return_superedge (src, dest, cedge);
546 add_edge (new_edge);
547 return new_edge;
548 }
549
550 /* Implementation of dnode::dump_dot vfunc for supernodes.
551
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. */
555
556 void
dump_dot(graphviz_out * gv,const dump_args_t & args) const557 supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
558 {
559 gv->println ("subgraph cluster_node_%i {",
560 m_index);
561 gv->indent ();
562
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);
567
568 pretty_printer *pp = gv->get_pp ();
569
570 if (args.m_node_annotator)
571 args.m_node_annotator->add_node_annotations (gv, *this, false);
572
573 gv->write_indent ();
574 dump_dot_id (pp);
575 pp_printf (pp,
576 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
577 "lightgrey");
578 pp_string (pp, "<TABLE BORDER=\"0\">");
579 pp_write_text_to_stream (pp);
580
581 bool had_row = false;
582
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))
586 had_row = true;
587
588 if (m_returning_call)
589 {
590 gv->begin_trtd ();
591 pp_string (pp, "returning call: ");
592 gv->end_tdtr ();
593
594 gv->begin_tr ();
595 gv->begin_td ();
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);
598 gv->end_td ();
599 /* Give any annotator the chance to add per-stmt TD elements to
600 this row. */
601 if (args.m_node_annotator)
602 args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
603 true);
604 gv->end_tr ();
605
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,
609 false);
610 pp_newline (pp);
611
612 had_row = true;
613 }
614
615 if (entry_p ())
616 {
617 pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
618 pp_newline (pp);
619 had_row = true;
620 }
621
622 if (return_p ())
623 {
624 pp_string (pp, "<TR><TD>EXIT</TD></TR>");
625 pp_newline (pp);
626 had_row = true;
627 }
628
629 /* Phi nodes. */
630 for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
631 !gsi_end_p (gpi); gsi_next (&gpi))
632 {
633 const gimple *stmt = gsi_stmt (gpi);
634 gv->begin_tr ();
635 gv->begin_td ();
636 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
637 pp_write_text_as_html_like_dot_to_stream (pp);
638 gv->end_td ();
639 /* Give any annotator the chance to add per-phi TD elements to
640 this row. */
641 if (args.m_node_annotator)
642 args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
643 gv->end_tr ();
644
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);
648
649 pp_newline (pp);
650 had_row = true;
651 }
652
653 /* Statements. */
654 int i;
655 gimple *stmt;
656 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
657 {
658 gv->begin_tr ();
659 gv->begin_td ();
660 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
661 pp_write_text_as_html_like_dot_to_stream (pp);
662 gv->end_td ();
663 /* Give any annotator the chance to add per-stmt TD elements to
664 this row. */
665 if (args.m_node_annotator)
666 args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
667 gv->end_tr ();
668
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);
672
673 pp_newline (pp);
674 had_row = true;
675 }
676
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))
681 had_row = true;
682
683 /* Graphviz requires a TABLE element to have at least one TR
684 (and each TR to have at least one TD). */
685 if (!had_row)
686 {
687 pp_string (pp, "<TR><TD>(empty)</TD></TR>");
688 pp_newline (pp);
689 }
690
691 pp_string (pp, "</TABLE>>];\n\n");
692 pp_flush (pp);
693
694 /* Terminate "subgraph" */
695 gv->outdent ();
696 gv->println ("}");
697 }
698
699 /* Write an ID for this node to PP, for use in .dot output. */
700
701 void
dump_dot_id(pretty_printer * pp) const702 supernode::dump_dot_id (pretty_printer *pp) const
703 {
704 pp_printf (pp, "node_%i", m_index);
705 }
706
707 /* Return a new json::object of the form
708 {"idx": int,
709 "fun": optional str
710 "bb_idx": int,
711 "returning_call": optional str,
712 "phis": [str],
713 "stmts" : [str]}. */
714
715 json::object *
to_json() const716 supernode::to_json () const
717 {
718 json::object *snode_obj = new json::object ();
719
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)));
724
725 if (m_returning_call)
726 {
727 pretty_printer pp;
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)));
732 }
733
734 /* Phi nodes. */
735 {
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))
739 {
740 const gimple *stmt = gsi_stmt (gpi);
741 pretty_printer pp;
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)));
745 }
746 snode_obj->set ("phis", phi_arr);
747 }
748
749 /* Statements. */
750 {
751 json::array *stmt_arr = new json::array ();
752 int i;
753 gimple *stmt;
754 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
755 {
756 pretty_printer pp;
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)));
760 }
761 snode_obj->set ("stmts", stmt_arr);
762 }
763
764 return snode_obj;
765 }
766
767 /* Get a location_t for the start of this supernode. */
768
769 location_t
get_start_location() const770 supernode::get_start_location () const
771 {
772 if (m_returning_call
773 && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
774 return m_returning_call->location;
775
776 int i;
777 gimple *stmt;
778 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
779 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
780 return stmt->location;
781
782 if (entry_p ())
783 {
784 // TWEAK: show the decl instead; this leads to more readable output:
785 return DECL_SOURCE_LOCATION (m_fun->decl);
786
787 return m_fun->function_start_locus;
788 }
789 if (return_p ())
790 return m_fun->function_end_locus;
791
792 return UNKNOWN_LOCATION;
793 }
794
795 /* Get a location_t for the end of this supernode. */
796
797 location_t
get_end_location() const798 supernode::get_end_location () const
799 {
800 int i;
801 gimple *stmt;
802 FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
803 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
804 return stmt->location;
805
806 if (m_returning_call
807 && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
808 return m_returning_call->location;
809
810 if (entry_p ())
811 return m_fun->function_start_locus;
812 if (return_p ())
813 return m_fun->function_end_locus;
814
815 return UNKNOWN_LOCATION;
816 }
817
818 /* Given STMT within this supernode, return its index within m_stmts. */
819
820 unsigned int
get_stmt_index(const gimple * stmt) const821 supernode::get_stmt_index (const gimple *stmt) const
822 {
823 unsigned i;
824 gimple *iter_stmt;
825 FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
826 if (iter_stmt == stmt)
827 return i;
828 gcc_unreachable ();
829 }
830
831 /* Get a string for PK. */
832
833 static const char *
edge_kind_to_string(enum edge_kind kind)834 edge_kind_to_string (enum edge_kind kind)
835 {
836 switch (kind)
837 {
838 default:
839 gcc_unreachable ();
840 case SUPEREDGE_CFG_EDGE:
841 return "SUPEREDGE_CFG_EDGE";
842 case SUPEREDGE_CALL:
843 return "SUPEREDGE_CALL";
844 case SUPEREDGE_RETURN:
845 return "SUPEREDGE_RETURN";
846 case SUPEREDGE_INTRAPROCEDURAL_CALL:
847 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
848 }
849 };
850
851 /* Dump this superedge to PP. */
852
853 void
dump(pretty_printer * pp) const854 superedge::dump (pretty_printer *pp) const
855 {
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)
859 {
860 pp_space (pp);
861 pp_string (pp, desc);
862 }
863 free (desc);
864 }
865
866 /* Dump this superedge to stderr. */
867
868 DEBUG_FUNCTION void
dump() const869 superedge::dump () const
870 {
871 pretty_printer pp;
872 pp_format_decoder (&pp) = default_tree_printer;
873 pp_show_color (&pp) = pp_show_color (global_dc->printer);
874 pp.buffer->stream = stderr;
875 dump (&pp);
876 pp_newline (&pp);
877 pp_flush (&pp);
878 }
879
880 /* Implementation of dedge::dump_dot for superedges.
881 Write a .dot edge to GV representing this superedge. */
882
883 void
dump_dot(graphviz_out * gv,const dump_args_t &) const884 superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
885 {
886 const char *style = "\"solid,bold\"";
887 const char *color = "black";
888 int weight = 10;
889 const char *constraint = "true";
890
891 switch (m_kind)
892 {
893 default:
894 gcc_unreachable ();
895 case SUPEREDGE_CFG_EDGE:
896 break;
897 case SUPEREDGE_CALL:
898 color = "red";
899 break;
900 case SUPEREDGE_RETURN:
901 color = "green";
902 break;
903 case SUPEREDGE_INTRAPROCEDURAL_CALL:
904 style = "\"dotted\"";
905 break;
906 }
907
908 /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
909 if (::edge cfg_edge = get_any_cfg_edge ())
910 {
911 if (cfg_edge->flags & EDGE_FAKE)
912 {
913 style = "dotted";
914 color = "green";
915 weight = 0;
916 }
917 else if (cfg_edge->flags & EDGE_DFS_BACK)
918 {
919 style = "\"dotted,bold\"";
920 color = "blue";
921 weight = 10;
922 }
923 else if (cfg_edge->flags & EDGE_FALLTHRU)
924 {
925 color = "blue";
926 weight = 100;
927 }
928
929 if (cfg_edge->flags & EDGE_ABNORMAL)
930 color = "red";
931 }
932
933 gv->write_indent ();
934
935 pretty_printer *pp = gv->get_pp ();
936
937 m_src->dump_dot_id (pp);
938 pp_string (pp, " -> ");
939 m_dest->dump_dot_id (pp);
940 pp_printf (pp,
941 (" [style=%s, color=%s, weight=%d, constraint=%s,"
942 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
943 " headlabel=\""),
944 style, color, weight, constraint,
945 m_src->m_index, m_dest->m_index);
946
947 dump_label_to_pp (pp, false);
948
949 pp_printf (pp, "\"];\n");
950 }
951
952 /* Return a new json::object of the form
953 {"kind" : str,
954 "src_idx": int, the index of the source supernode,
955 "dst_idx": int, the index of the destination supernode,
956 "desc" : str. */
957
958 json::object *
to_json() const959 superedge::to_json () const
960 {
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));
965
966 {
967 pretty_printer pp;
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)));
971 }
972
973 return sedge_obj;
974 }
975
976 /* If this is an intraprocedural superedge, return the associated
977 CFG edge. Otherwise, return NULL. */
978
979 ::edge
get_any_cfg_edge() const980 superedge::get_any_cfg_edge () const
981 {
982 if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
983 return sub->get_cfg_edge ();
984 return NULL;
985 }
986
987 /* If this is an interprocedural superedge, return the associated
988 cgraph_edge *. Otherwise, return NULL. */
989
990 cgraph_edge *
get_any_callgraph_edge() const991 superedge::get_any_callgraph_edge () const
992 {
993 if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
994 return sub->m_cedge;
995 return NULL;
996 }
997
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).
1000
1001 The caller is responsible for freeing the result.
1002
1003 If USER_FACING is false, the result also contains any underlying
1004 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1005
1006 char *
get_description(bool user_facing) const1007 superedge::get_description (bool user_facing) const
1008 {
1009 pretty_printer pp;
1010 dump_label_to_pp (&pp, user_facing);
1011 return xstrdup (pp_formatted_text (&pp));
1012 }
1013
1014 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1015 superedges.
1016
1017 For true/false edges, print "true" or "false" to PP.
1018
1019 If USER_FACING is false, also print flags on the underlying CFG edge to
1020 PP. */
1021
1022 void
dump_label_to_pp(pretty_printer * pp,bool user_facing) const1023 cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1024 bool user_facing) const
1025 {
1026 if (true_value_p ())
1027 pp_printf (pp, "true");
1028 else if (false_value_p ())
1029 pp_printf (pp, "false");
1030
1031 if (user_facing)
1032 return;
1033
1034 /* Express edge flags as a string with " | " separator.
1035 e.g. " (flags FALLTHRU | DFS_BACK)". */
1036 if (get_flags ())
1037 {
1038 pp_string (pp, " (flags ");
1039 bool seen_flag = false;
1040 #define DEF_EDGE_FLAG(NAME,IDX) \
1041 do { \
1042 if (get_flags () & EDGE_##NAME) \
1043 { \
1044 if (seen_flag) \
1045 pp_string (pp, " | "); \
1046 pp_printf (pp, "%s", (#NAME)); \
1047 seen_flag = true; \
1048 } \
1049 } while (0);
1050 #include "cfg-flags.def"
1051 #undef DEF_EDGE_FLAG
1052 pp_string (pp, ")");
1053 }
1054
1055 /* Otherwise, no label. */
1056 }
1057
1058 /* Get the index number for this edge for use in phi stmts
1059 in its destination. */
1060
1061 size_t
get_phi_arg_idx() const1062 cfg_superedge::get_phi_arg_idx () const
1063 {
1064 return m_cfg_edge->dest_idx;
1065 }
1066
1067 /* Get the phi argument for PHI for this CFG edge. */
1068
1069 tree
get_phi_arg(const gphi * phi) const1070 cfg_superedge::get_phi_arg (const gphi *phi) const
1071 {
1072 size_t index = get_phi_arg_idx ();
1073 return gimple_phi_arg_def (phi, index);
1074 }
1075
switch_cfg_superedge(supernode * src,supernode * dst,::edge e)1076 switch_cfg_superedge::switch_cfg_superedge (supernode *src,
1077 supernode *dst,
1078 ::edge e)
1079 : cfg_superedge (src, dst, e)
1080 {
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++)
1084 {
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_);
1090 }
1091 }
1092
1093 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1094 "switch" statements.
1095
1096 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1097
1098 void
dump_label_to_pp(pretty_printer * pp,bool user_facing ATTRIBUTE_UNUSED) const1099 switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1100 bool user_facing ATTRIBUTE_UNUSED) const
1101 {
1102 if (user_facing)
1103 {
1104 for (unsigned i = 0; i < m_case_labels.length (); ++i)
1105 {
1106 if (i > 0)
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);
1112 if (lower_bound)
1113 {
1114 pp_printf (pp, "case ");
1115 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1116 if (upper_bound)
1117 {
1118 pp_printf (pp, " ... ");
1119 dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1120 false);
1121 }
1122 pp_printf (pp, ":");
1123 }
1124 else
1125 pp_printf (pp, "default:");
1126 }
1127 }
1128 else
1129 {
1130 pp_character (pp, '{');
1131 for (unsigned i = 0; i < m_case_labels.length (); ++i)
1132 {
1133 if (i > 0)
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);
1139 if (lower_bound)
1140 {
1141 if (upper_bound)
1142 {
1143 pp_character (pp, '[');
1144 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0,
1145 false);
1146 pp_string (pp, ", ");
1147 dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1148 false);
1149 pp_character (pp, ']');
1150 }
1151 else
1152 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1153 }
1154 else
1155 pp_printf (pp, "default");
1156 }
1157 pp_character (pp, '}');
1158 }
1159 }
1160
1161 /* Implementation of superedge::dump_label_to_pp for interprocedural
1162 superedges. */
1163
1164 void
dump_label_to_pp(pretty_printer * pp,bool user_facing ATTRIBUTE_UNUSED) const1165 callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
1166 bool user_facing ATTRIBUTE_UNUSED) const
1167 {
1168 switch (m_kind)
1169 {
1170 default:
1171 case SUPEREDGE_CFG_EDGE:
1172 gcc_unreachable ();
1173
1174 case SUPEREDGE_CALL:
1175 pp_printf (pp, "call");
1176 break;
1177
1178 case SUPEREDGE_RETURN:
1179 pp_printf (pp, "return");
1180 break;
1181
1182 case SUPEREDGE_INTRAPROCEDURAL_CALL:
1183 pp_printf (pp, "intraproc link");
1184 break;
1185 }
1186 }
1187
1188 /* Get the function that was called at this interprocedural call/return
1189 edge. */
1190
1191 function *
get_callee_function() const1192 callgraph_superedge::get_callee_function () const
1193 {
1194 return get_ultimate_function_for_cgraph_edge (m_cedge);
1195 }
1196
1197 /* Get the calling function at this interprocedural call/return edge. */
1198
1199 function *
get_caller_function() const1200 callgraph_superedge::get_caller_function () const
1201 {
1202 return m_cedge->caller->get_fun ();
1203 }
1204
1205 /* Get the fndecl that was called at this interprocedural call/return
1206 edge. */
1207
1208 tree
get_callee_decl() const1209 callgraph_superedge::get_callee_decl () const
1210 {
1211 return get_callee_function ()->decl;
1212 }
1213
1214 /* Get the gcall * of this interprocedural call/return edge. */
1215
1216 gcall *
get_call_stmt() const1217 callgraph_superedge::get_call_stmt () const
1218 {
1219 if (m_cedge)
1220 return m_cedge->call_stmt;
1221
1222 return m_src->get_final_call ();
1223 }
1224
1225 /* Get the calling fndecl at this interprocedural call/return edge. */
1226
1227 tree
get_caller_decl() const1228 callgraph_superedge::get_caller_decl () const
1229 {
1230 return get_caller_function ()->decl;
1231 }
1232
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
1235 at the callsite. */
1236
1237 tree
get_arg_for_parm(tree parm_to_find,callsite_expr * out) const1238 callgraph_superedge::get_arg_for_parm (tree parm_to_find,
1239 callsite_expr *out) const
1240 {
1241 gcc_assert (TREE_CODE (parm_to_find) == PARM_DECL);
1242
1243 tree callee = get_callee_decl ();
1244 const gcall *call_stmt = get_call_stmt ();
1245
1246 unsigned i = 0;
1247 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1248 iter_parm = DECL_CHAIN (iter_parm), ++i)
1249 {
1250 if (i >= gimple_call_num_args (call_stmt))
1251 return NULL_TREE;
1252 if (iter_parm == parm_to_find)
1253 {
1254 if (out)
1255 *out = callsite_expr::from_zero_based_param (i);
1256 return gimple_call_arg (call_stmt, i);
1257 }
1258 }
1259
1260 /* Not found. */
1261 return NULL_TREE;
1262 }
1263
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. */
1268
1269 tree
get_parm_for_arg(tree arg_to_find,callsite_expr * out) const1270 callgraph_superedge::get_parm_for_arg (tree arg_to_find,
1271 callsite_expr *out) const
1272 {
1273 tree callee = get_callee_decl ();
1274 const gcall *call_stmt = get_call_stmt ();
1275
1276 unsigned i = 0;
1277 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1278 iter_parm = DECL_CHAIN (iter_parm), ++i)
1279 {
1280 if (i >= gimple_call_num_args (call_stmt))
1281 return NULL_TREE;
1282 tree param = gimple_call_arg (call_stmt, i);
1283 if (arg_to_find == param)
1284 {
1285 if (out)
1286 *out = callsite_expr::from_zero_based_param (i);
1287 return ssa_default_def (get_callee_function (), iter_parm);
1288 }
1289 }
1290
1291 /* Not found. */
1292 return NULL_TREE;
1293 }
1294
1295 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1296 If non-NULL is returned, populate OUT. */
1297
1298 tree
map_expr_from_caller_to_callee(tree caller_expr,callsite_expr * out) const1299 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
1300 callsite_expr *out) const
1301 {
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);
1305 if (parm)
1306 return parm;
1307 /* Otherwise try return value. */
1308 if (caller_expr == gimple_call_lhs (get_call_stmt ()))
1309 {
1310 if (out)
1311 *out = callsite_expr::from_return_value ();
1312 return DECL_RESULT (get_callee_decl ());
1313 }
1314
1315 return NULL_TREE;
1316 }
1317
1318 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1319 If non-NULL is returned, populate OUT. */
1320
1321 tree
map_expr_from_callee_to_caller(tree callee_expr,callsite_expr * out) const1322 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
1323 callsite_expr *out) const
1324 {
1325 if (callee_expr == NULL_TREE)
1326 return NULL_TREE;
1327
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);
1331
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);
1337
1338 /* Otherwise try return value. */
1339 if (callee_expr == DECL_RESULT (get_callee_decl ()))
1340 {
1341 if (out)
1342 *out = callsite_expr::from_return_value ();
1343 return gimple_call_lhs (get_call_stmt ());
1344 }
1345
1346 return NULL_TREE;
1347 }
1348
1349 } // namespace ana
1350
1351 #endif /* #if ENABLE_ANALYZER */
1352