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>.
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 "cfganal.h"
45 #include "function.h"
46 #include "json.h"
47 #include "analyzer/analyzer.h"
48 #include "ordered-hash-map.h"
49 #include "options.h"
50 #include "cgraph.h"
51 #include "cfg.h"
52 #include "digraph.h"
53 #include "analyzer/supergraph.h"
54 #include "analyzer/analyzer-logging.h"
55
56 #if ENABLE_ANALYZER
57
58 namespace ana {
59
60 /* Get the function of the ultimate alias target being called at EDGE,
61 if any. */
62
63 static function *
get_ultimate_function_for_cgraph_edge(cgraph_edge * edge)64 get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
65 {
66 cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
67 if (!ultimate_node)
68 return NULL;
69 return ultimate_node->get_fun ();
70 }
71
72 /* Get the cgraph_edge, but only if there's an underlying function body. */
73
74 cgraph_edge *
supergraph_call_edge(function * fun,gimple * stmt)75 supergraph_call_edge (function *fun, gimple *stmt)
76 {
77 gcall *call = dyn_cast<gcall *> (stmt);
78 if (!call)
79 return NULL;
80 cgraph_edge *edge = cgraph_node::get (fun->decl)->get_edge (stmt);
81 if (!edge)
82 return NULL;
83 if (!edge->callee)
84 return NULL; /* e.g. for a function pointer. */
85 if (!get_ultimate_function_for_cgraph_edge (edge))
86 return NULL;
87 return edge;
88 }
89
90 /* class saved_uids.
91
92 In order to ensure consistent results without relying on the ordering
93 of pointer values we assign a uid to each gimple stmt, globally unique
94 across all functions.
95
96 Normally, the stmt uids are a scratch space that each pass can freely
97 assign its own values to. However, in the case of LTO, the uids are
98 used to associate call stmts with callgraph edges between the WPA phase
99 (where the analyzer runs in LTO mode) and the LTRANS phase; if the
100 analyzer changes them in the WPA phase, it leads to errors when
101 streaming the code back in at LTRANS.
102 lto_prepare_function_for_streaming has code to renumber the stmt UIDs
103 when the code is streamed back out, but for some reason this isn't
104 called for clones.
105
106 Hence, as a workaround, this class has responsibility for tracking
107 the original uids and restoring them once the pass is complete
108 (in the supergraph dtor). */
109
110 /* Give STMT a globally unique uid, storing its original uid so it can
111 later be restored. */
112
113 void
make_uid_unique(gimple * stmt)114 saved_uids::make_uid_unique (gimple *stmt)
115 {
116 unsigned next_uid = m_old_stmt_uids.length ();
117 unsigned old_stmt_uid = stmt->uid;
118 stmt->uid = next_uid;
119 m_old_stmt_uids.safe_push
120 (std::pair<gimple *, unsigned> (stmt, old_stmt_uid));
121 }
122
123 /* Restore the saved uids of all stmts. */
124
125 void
restore_uids() const126 saved_uids::restore_uids () const
127 {
128 unsigned i;
129 std::pair<gimple *, unsigned> *pair;
130 FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
131 pair->first->uid = pair->second;
132 }
133
134 /* supergraph's ctor. Walk the callgraph, building supernodes for each
135 CFG basic block, splitting the basic blocks at callsites. Join
136 together the supernodes with interprocedural and intraprocedural
137 superedges as appropriate.
138 Assign UIDs to the gimple stmts. */
139
supergraph(logger * logger)140 supergraph::supergraph (logger *logger)
141 {
142 auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
143
144 LOG_FUNC (logger);
145
146 /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
147 {
148 /* Sort the cgraph_nodes? */
149 cgraph_node *node;
150 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
151 {
152 function *fun = node->get_fun ();
153
154 /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
155 the supergraph (by doing it per-function). */
156 auto_cfun sentinel (fun);
157 mark_dfs_back_edges ();
158
159 const int start_idx = m_nodes.length ();
160
161 basic_block bb;
162 FOR_ALL_BB_FN (bb, fun)
163 {
164 /* The initial supernode for the BB gets the phi nodes (if any). */
165 supernode *node_for_stmts = add_node (fun, bb, NULL, phi_nodes (bb));
166 m_bb_to_initial_node.put (bb, node_for_stmts);
167 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
168 gsi_next (&gpi))
169 {
170 gimple *stmt = gsi_stmt (gpi);
171 m_stmt_to_node_t.put (stmt, node_for_stmts);
172 m_stmt_uids.make_uid_unique (stmt);
173 }
174
175 /* Append statements from BB to the current supernode, splitting
176 them into a new supernode at each call site; such call statements
177 appear in both supernodes (representing call and return). */
178 gimple_stmt_iterator gsi;
179 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
180 {
181 gimple *stmt = gsi_stmt (gsi);
182 node_for_stmts->m_stmts.safe_push (stmt);
183 m_stmt_to_node_t.put (stmt, node_for_stmts);
184 m_stmt_uids.make_uid_unique (stmt);
185 if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
186 {
187 m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts);
188 node_for_stmts = add_node (fun, bb, as_a <gcall *> (stmt), NULL);
189 m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
190 }
191 }
192
193 m_bb_to_final_node.put (bb, node_for_stmts);
194 }
195
196 const unsigned num_snodes = m_nodes.length () - start_idx;
197 m_function_to_num_snodes.put (fun, num_snodes);
198
199 if (logger)
200 {
201 const int end_idx = m_nodes.length () - 1;
202 logger->log ("SN: %i...%i: function %qD",
203 start_idx, end_idx, fun->decl);
204 }
205 }
206 }
207
208 /* Second pass: make superedges. */
209 {
210 /* Make superedges for CFG edges. */
211 for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
212 iter != m_bb_to_final_node.end ();
213 ++iter)
214 {
215 basic_block bb = (*iter).first;
216 supernode *src_supernode = (*iter).second;
217
218 ::edge cfg_edge;
219 int idx;
220 if (bb->succs)
221 FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
222 {
223 basic_block dest_cfg_block = cfg_edge->dest;
224 supernode *dest_supernode
225 = *m_bb_to_initial_node.get (dest_cfg_block);
226 cfg_superedge *cfg_sedge
227 = add_cfg_edge (src_supernode, dest_supernode, cfg_edge, idx);
228 m_cfg_edge_to_cfg_superedge.put (cfg_edge, cfg_sedge);
229 }
230 }
231
232 /* Make interprocedural superedges for calls. */
233 {
234 for (cgraph_edge_to_node_t::iterator iter
235 = m_cgraph_edge_to_caller_prev_node.begin ();
236 iter != m_cgraph_edge_to_caller_prev_node.end ();
237 ++iter)
238 {
239 cgraph_edge *edge = (*iter).first;
240 supernode *caller_prev_supernode = (*iter).second;
241 function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
242 if (!callee_fn || !callee_fn->cfg)
243 continue;
244 basic_block callee_cfg_block = ENTRY_BLOCK_PTR_FOR_FN (callee_fn);
245 supernode *callee_supernode
246 = *m_bb_to_initial_node.get (callee_cfg_block);
247 call_superedge *sedge
248 = add_call_superedge (caller_prev_supernode,
249 callee_supernode,
250 edge);
251 m_cgraph_edge_to_call_superedge.put (edge, sedge);
252 }
253 }
254
255 /* Make interprocedural superedges for returns. */
256 {
257 for (cgraph_edge_to_node_t::iterator iter
258 = m_cgraph_edge_to_caller_next_node.begin ();
259 iter != m_cgraph_edge_to_caller_next_node.end ();
260 ++iter)
261 {
262 cgraph_edge *edge = (*iter).first;
263 supernode *caller_next_supernode = (*iter).second;
264 function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
265 if (!callee_fn || !callee_fn->cfg)
266 continue;
267 basic_block callee_cfg_block = EXIT_BLOCK_PTR_FOR_FN (callee_fn);
268 supernode *callee_supernode
269 = *m_bb_to_initial_node.get (callee_cfg_block);
270 return_superedge *sedge
271 = add_return_superedge (callee_supernode,
272 caller_next_supernode,
273 edge);
274 m_cgraph_edge_to_return_superedge.put (edge, sedge);
275 }
276 }
277
278 /* Make intraprocedural superedges linking the two halves of a call. */
279 {
280 for (cgraph_edge_to_node_t::iterator iter
281 = m_cgraph_edge_to_caller_prev_node.begin ();
282 iter != m_cgraph_edge_to_caller_prev_node.end ();
283 ++iter)
284 {
285 cgraph_edge *edge = (*iter).first;
286 supernode *caller_prev_supernode = (*iter).second;
287 supernode *caller_next_supernode
288 = *m_cgraph_edge_to_caller_next_node.get (edge);
289 superedge *sedge
290 = new callgraph_superedge (caller_prev_supernode,
291 caller_next_supernode,
292 SUPEREDGE_INTRAPROCEDURAL_CALL,
293 edge);
294 add_edge (sedge);
295 m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
296 }
297
298 }
299 }
300 }
301
302 /* supergraph's dtor. Reset stmt uids. */
303
~supergraph()304 supergraph::~supergraph ()
305 {
306 m_stmt_uids.restore_uids ();
307 }
308
309 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
310 Cluster the supernodes by function, then by BB from original CFG. */
311
312 void
dump_dot_to_pp(pretty_printer * pp,const dump_args_t & dump_args) const313 supergraph::dump_dot_to_pp (pretty_printer *pp,
314 const dump_args_t &dump_args) const
315 {
316 graphviz_out gv (pp);
317
318 pp_string (pp, "digraph \"");
319 pp_write_text_to_stream (pp);
320 pp_string (pp, "supergraph");
321 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
322 pp_string (pp, "\" {\n");
323 gv.indent ();
324
325 gv.println ("overlap=false;");
326 gv.println ("compound=true;");
327
328 /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
329 https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
330 */
331
332 /* Break out the supernodes into clusters by function. */
333 {
334 cgraph_node *node;
335 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
336 {
337 function *fun = node->get_fun ();
338 const char *funcname = function_name (fun);
339 gv.println ("subgraph \"cluster_%s\" {",
340 funcname);
341 gv.indent ();
342 pp_printf (pp,
343 ("style=\"dashed\";"
344 " color=\"black\";"
345 " label=\"%s\";\n"),
346 funcname);
347
348 /* Break out the nodes into clusters by BB from original CFG. */
349 {
350 basic_block bb;
351 FOR_ALL_BB_FN (bb, fun)
352 {
353 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
354 {
355 gv.println ("subgraph \"cluster_%s_bb_%i\" {",
356 funcname, bb->index);
357 gv.indent ();
358 pp_printf (pp,
359 ("style=\"dashed\";"
360 " color=\"black\";"
361 " label=\"bb: %i\";\n"),
362 bb->index);
363 }
364
365 // TODO: maybe keep an index per-function/per-bb to speed this up???
366 int i;
367 supernode *n;
368 FOR_EACH_VEC_ELT (m_nodes, i, n)
369 if (n->m_fun == fun && n->m_bb == bb)
370 n->dump_dot (&gv, dump_args);
371
372 if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
373 {
374 /* Terminate per-bb "subgraph" */
375 gv.outdent ();
376 gv.println ("}");
377 }
378 }
379 }
380
381 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
382 pp_string (pp, "\t");
383 get_node_for_function_entry (fun)->dump_dot_id (pp);
384 pp_string (pp, ":s -> ");
385 get_node_for_function_exit (fun)->dump_dot_id (pp);
386 pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
387
388 /* Terminate per-function "subgraph" */
389 gv.outdent ();
390 gv.println ("}");
391 }
392 }
393
394 /* Superedges. */
395 int i;
396 superedge *e;
397 FOR_EACH_VEC_ELT (m_edges, i, e)
398 e->dump_dot (&gv, dump_args);
399
400 /* Terminate "digraph" */
401 gv.outdent ();
402 gv.println ("}");
403 }
404
405 /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
406
407 void
dump_dot_to_file(FILE * fp,const dump_args_t & dump_args) const408 supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
409 {
410 pretty_printer *pp = global_dc->printer->clone ();
411 pp_show_color (pp) = 0;
412 /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
413 trying to prettify things by showing the underlying var. */
414 pp_format_decoder (pp) = default_tree_printer;
415
416 pp->buffer->stream = fp;
417 dump_dot_to_pp (pp, dump_args);
418 pp_flush (pp);
419 delete pp;
420 }
421
422 /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
423
424 void
dump_dot(const char * path,const dump_args_t & dump_args) const425 supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
426 {
427 FILE *fp = fopen (path, "w");
428 dump_dot_to_file (fp, dump_args);
429 fclose (fp);
430 }
431
432 /* Return a new json::object of the form
433 {"nodes" : [objs for snodes],
434 "edges" : [objs for sedges]}. */
435
436 json::object *
to_json() const437 supergraph::to_json () const
438 {
439 json::object *sgraph_obj = new json::object ();
440
441 /* Nodes. */
442 {
443 json::array *nodes_arr = new json::array ();
444 unsigned i;
445 supernode *n;
446 FOR_EACH_VEC_ELT (m_nodes, i, n)
447 nodes_arr->append (n->to_json ());
448 sgraph_obj->set ("nodes", nodes_arr);
449 }
450
451 /* Edges. */
452 {
453 json::array *edges_arr = new json::array ();
454 unsigned i;
455 superedge *n;
456 FOR_EACH_VEC_ELT (m_edges, i, n)
457 edges_arr->append (n->to_json ());
458 sgraph_obj->set ("edges", edges_arr);
459 }
460
461 return sgraph_obj;
462 }
463
464 /* Create a supernode for BB within FUN and add it to this supergraph.
465
466 If RETURNING_CALL is non-NULL, the supernode represents the resumption
467 of the basic block after returning from that call.
468
469 If PHI_NODES is non-NULL, this is the initial supernode for the basic
470 block, and is responsible for any handling of the phi nodes. */
471
472 supernode *
add_node(function * fun,basic_block bb,gcall * returning_call,gimple_seq phi_nodes)473 supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
474 gimple_seq phi_nodes)
475 {
476 supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
477 m_nodes.length ());
478 m_nodes.safe_push (n);
479 return n;
480 }
481
482 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
483 adding it to this supergraph.
484
485 If the edge is for a switch statement, create a switch_cfg_superedge
486 subclass using IDX (the index of E within the out-edges from SRC's
487 underlying basic block). */
488
489 cfg_superedge *
add_cfg_edge(supernode * src,supernode * dest,::edge e,int idx)490 supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e, int idx)
491 {
492 /* Special-case switch edges. */
493 gimple *stmt = src->get_last_stmt ();
494 cfg_superedge *new_edge;
495 if (stmt && stmt->code == GIMPLE_SWITCH)
496 new_edge = new switch_cfg_superedge (src, dest, e, idx);
497 else
498 new_edge = new cfg_superedge (src, dest, e);
499 add_edge (new_edge);
500 return new_edge;
501 }
502
503 /* Create and add a call_superedge representing an interprocedural call
504 from SRC to DEST, using CEDGE. */
505
506 call_superedge *
add_call_superedge(supernode * src,supernode * dest,cgraph_edge * cedge)507 supergraph::add_call_superedge (supernode *src, supernode *dest,
508 cgraph_edge *cedge)
509 {
510 call_superedge *new_edge = new call_superedge (src, dest, cedge);
511 add_edge (new_edge);
512 return new_edge;
513 }
514
515 /* Create and add a return_superedge representing returning from an
516 interprocedural call, returning from SRC to DEST, using CEDGE. */
517
518 return_superedge *
add_return_superedge(supernode * src,supernode * dest,cgraph_edge * cedge)519 supergraph::add_return_superedge (supernode *src, supernode *dest,
520 cgraph_edge *cedge)
521 {
522 return_superedge *new_edge = new return_superedge (src, dest, cedge);
523 add_edge (new_edge);
524 return new_edge;
525 }
526
527 /* Implementation of dnode::dump_dot vfunc for supernodes.
528
529 Write a cluster for the node, and within it a .dot node showing
530 the phi nodes and stmts. Call into any node annotator from ARGS to
531 potentially add other records to the cluster. */
532
533 void
dump_dot(graphviz_out * gv,const dump_args_t & args) const534 supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
535 {
536 gv->println ("subgraph cluster_node_%i {",
537 m_index);
538 gv->indent ();
539
540 gv->println("style=\"solid\";");
541 gv->println("color=\"black\";");
542 gv->println("fillcolor=\"lightgrey\";");
543 gv->println("label=\"sn: %i (bb: %i)\";", m_index, m_bb->index);
544
545 pretty_printer *pp = gv->get_pp ();
546
547 if (args.m_node_annotator)
548 args.m_node_annotator->add_node_annotations (gv, *this, false);
549
550 gv->write_indent ();
551 dump_dot_id (pp);
552 pp_printf (pp,
553 " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
554 "lightgrey");
555 pp_string (pp, "<TABLE BORDER=\"0\">");
556 pp_write_text_to_stream (pp);
557
558 bool had_row = false;
559
560 /* Give any annotator the chance to add its own per-node TR elements. */
561 if (args.m_node_annotator)
562 if (args.m_node_annotator->add_node_annotations (gv, *this, true))
563 had_row = true;
564
565 if (m_returning_call)
566 {
567 gv->begin_trtd ();
568 pp_string (pp, "returning call: ");
569 gv->end_tdtr ();
570
571 gv->begin_tr ();
572 gv->begin_td ();
573 pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
574 pp_write_text_as_html_like_dot_to_stream (pp);
575 gv->end_td ();
576 /* Give any annotator the chance to add per-stmt TD elements to
577 this row. */
578 if (args.m_node_annotator)
579 args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
580 true);
581 gv->end_tr ();
582
583 /* Give any annotator the chance to add per-stmt TR elements. */
584 if (args.m_node_annotator)
585 args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
586 false);
587 pp_newline (pp);
588
589 had_row = true;
590 }
591
592 if (entry_p ())
593 {
594 pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
595 pp_newline (pp);
596 had_row = true;
597 }
598
599 if (return_p ())
600 {
601 pp_string (pp, "<TR><TD>EXIT</TD></TR>");
602 pp_newline (pp);
603 had_row = true;
604 }
605
606 /* Phi nodes. */
607 for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
608 !gsi_end_p (gpi); gsi_next (&gpi))
609 {
610 const gimple *stmt = gsi_stmt (gpi);
611 gv->begin_tr ();
612 gv->begin_td ();
613 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
614 pp_write_text_as_html_like_dot_to_stream (pp);
615 gv->end_td ();
616 /* Give any annotator the chance to add per-phi TD elements to
617 this row. */
618 if (args.m_node_annotator)
619 args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
620 gv->end_tr ();
621
622 /* Give any annotator the chance to add per-phi TR elements. */
623 if (args.m_node_annotator)
624 args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
625
626 pp_newline (pp);
627 had_row = true;
628 }
629
630 /* Statements. */
631 int i;
632 gimple *stmt;
633 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
634 {
635 gv->begin_tr ();
636 gv->begin_td ();
637 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
638 pp_write_text_as_html_like_dot_to_stream (pp);
639 gv->end_td ();
640 /* Give any annotator the chance to add per-stmt TD elements to
641 this row. */
642 if (args.m_node_annotator)
643 args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
644 gv->end_tr ();
645
646 /* Give any annotator the chance to add per-stmt TR elements. */
647 if (args.m_node_annotator)
648 args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
649
650 pp_newline (pp);
651 had_row = true;
652 }
653
654 /* Give any annotator the chance to add additional per-node TR elements
655 to the end of the TABLE. */
656 if (args.m_node_annotator)
657 if (args.m_node_annotator->add_after_node_annotations (gv, *this))
658 had_row = true;
659
660 /* Graphviz requires a TABLE element to have at least one TR
661 (and each TR to have at least one TD). */
662 if (!had_row)
663 {
664 pp_string (pp, "<TR><TD>(empty)</TD></TR>");
665 pp_newline (pp);
666 }
667
668 pp_string (pp, "</TABLE>>];\n\n");
669 pp_flush (pp);
670
671 /* Terminate "subgraph" */
672 gv->outdent ();
673 gv->println ("}");
674 }
675
676 /* Write an ID for this node to PP, for use in .dot output. */
677
678 void
dump_dot_id(pretty_printer * pp) const679 supernode::dump_dot_id (pretty_printer *pp) const
680 {
681 pp_printf (pp, "node_%i", m_index);
682 }
683
684 /* Return a new json::object of the form
685 {"idx": int,
686 "fun": optional str
687 "bb_idx": int,
688 "returning_call": optional str,
689 "phis": [str],
690 "stmts" : [str]}. */
691
692 json::object *
to_json() const693 supernode::to_json () const
694 {
695 json::object *snode_obj = new json::object ();
696
697 snode_obj->set ("idx", new json::integer_number (m_index));
698 snode_obj->set ("bb_idx", new json::integer_number (m_bb->index));
699 if (function *fun = get_function ())
700 snode_obj->set ("fun", new json::string (function_name (fun)));
701
702 if (m_returning_call)
703 {
704 pretty_printer pp;
705 pp_format_decoder (&pp) = default_tree_printer;
706 pp_gimple_stmt_1 (&pp, m_returning_call, 0, (dump_flags_t)0);
707 snode_obj->set ("returning_call",
708 new json::string (pp_formatted_text (&pp)));
709 }
710
711 /* Phi nodes. */
712 {
713 json::array *phi_arr = new json::array ();
714 for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
715 !gsi_end_p (gpi); gsi_next (&gpi))
716 {
717 const gimple *stmt = gsi_stmt (gpi);
718 pretty_printer pp;
719 pp_format_decoder (&pp) = default_tree_printer;
720 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
721 phi_arr->append (new json::string (pp_formatted_text (&pp)));
722 }
723 snode_obj->set ("phis", phi_arr);
724 }
725
726 /* Statements. */
727 {
728 json::array *stmt_arr = new json::array ();
729 int i;
730 gimple *stmt;
731 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
732 {
733 pretty_printer pp;
734 pp_format_decoder (&pp) = default_tree_printer;
735 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
736 stmt_arr->append (new json::string (pp_formatted_text (&pp)));
737 }
738 snode_obj->set ("stmts", stmt_arr);
739 }
740
741 return snode_obj;
742 }
743
744 /* Get a location_t for the start of this supernode. */
745
746 location_t
get_start_location() const747 supernode::get_start_location () const
748 {
749 if (m_returning_call
750 && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
751 return m_returning_call->location;
752
753 int i;
754 gimple *stmt;
755 FOR_EACH_VEC_ELT (m_stmts, i, stmt)
756 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
757 return stmt->location;
758
759 if (entry_p ())
760 {
761 // TWEAK: show the decl instead; this leads to more readable output:
762 return DECL_SOURCE_LOCATION (m_fun->decl);
763
764 return m_fun->function_start_locus;
765 }
766 if (return_p ())
767 return m_fun->function_end_locus;
768
769 return UNKNOWN_LOCATION;
770 }
771
772 /* Get a location_t for the end of this supernode. */
773
774 location_t
get_end_location() const775 supernode::get_end_location () const
776 {
777 int i;
778 gimple *stmt;
779 FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
780 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
781 return stmt->location;
782
783 if (m_returning_call
784 && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
785 return m_returning_call->location;
786
787 if (entry_p ())
788 return m_fun->function_start_locus;
789 if (return_p ())
790 return m_fun->function_end_locus;
791
792 return UNKNOWN_LOCATION;
793 }
794
795 /* Given STMT within this supernode, return its index within m_stmts. */
796
797 unsigned int
get_stmt_index(const gimple * stmt) const798 supernode::get_stmt_index (const gimple *stmt) const
799 {
800 unsigned i;
801 gimple *iter_stmt;
802 FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
803 if (iter_stmt == stmt)
804 return i;
805 gcc_unreachable ();
806 }
807
808 /* Get a string for PK. */
809
810 static const char *
edge_kind_to_string(enum edge_kind kind)811 edge_kind_to_string (enum edge_kind kind)
812 {
813 switch (kind)
814 {
815 default:
816 gcc_unreachable ();
817 case SUPEREDGE_CFG_EDGE:
818 return "SUPEREDGE_CFG_EDGE";
819 case SUPEREDGE_CALL:
820 return "SUPEREDGE_CALL";
821 case SUPEREDGE_RETURN:
822 return "SUPEREDGE_RETURN";
823 case SUPEREDGE_INTRAPROCEDURAL_CALL:
824 return "SUPEREDGE_INTRAPROCEDURAL_CALL";
825 }
826 };
827
828 /* Dump this superedge to PP. */
829
830 void
dump(pretty_printer * pp) const831 superedge::dump (pretty_printer *pp) const
832 {
833 pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_index, m_dest->m_index);
834 char *desc = get_description (false);
835 if (strlen (desc) > 0)
836 {
837 pp_space (pp);
838 pp_string (pp, desc);
839 }
840 free (desc);
841 }
842
843 /* Dump this superedge to stderr. */
844
845 DEBUG_FUNCTION void
dump() const846 superedge::dump () const
847 {
848 pretty_printer pp;
849 pp_format_decoder (&pp) = default_tree_printer;
850 pp_show_color (&pp) = pp_show_color (global_dc->printer);
851 pp.buffer->stream = stderr;
852 dump (&pp);
853 pp_newline (&pp);
854 pp_flush (&pp);
855 }
856
857 /* Implementation of dedge::dump_dot for superedges.
858 Write a .dot edge to GV representing this superedge. */
859
860 void
dump_dot(graphviz_out * gv,const dump_args_t &) const861 superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
862 {
863 const char *style = "\"solid,bold\"";
864 const char *color = "black";
865 int weight = 10;
866 const char *constraint = "true";
867
868 switch (m_kind)
869 {
870 default:
871 gcc_unreachable ();
872 case SUPEREDGE_CFG_EDGE:
873 break;
874 case SUPEREDGE_CALL:
875 color = "red";
876 break;
877 case SUPEREDGE_RETURN:
878 color = "green";
879 break;
880 case SUPEREDGE_INTRAPROCEDURAL_CALL:
881 style = "\"dotted\"";
882 break;
883 }
884
885 /* Adapted from graph.c:draw_cfg_node_succ_edges. */
886 if (::edge cfg_edge = get_any_cfg_edge ())
887 {
888 if (cfg_edge->flags & EDGE_FAKE)
889 {
890 style = "dotted";
891 color = "green";
892 weight = 0;
893 }
894 else if (cfg_edge->flags & EDGE_DFS_BACK)
895 {
896 style = "\"dotted,bold\"";
897 color = "blue";
898 weight = 10;
899 }
900 else if (cfg_edge->flags & EDGE_FALLTHRU)
901 {
902 color = "blue";
903 weight = 100;
904 }
905
906 if (cfg_edge->flags & EDGE_ABNORMAL)
907 color = "red";
908 }
909
910 gv->write_indent ();
911
912 pretty_printer *pp = gv->get_pp ();
913
914 m_src->dump_dot_id (pp);
915 pp_string (pp, " -> ");
916 m_dest->dump_dot_id (pp);
917 pp_printf (pp,
918 (" [style=%s, color=%s, weight=%d, constraint=%s,"
919 " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
920 " headlabel=\""),
921 style, color, weight, constraint,
922 m_src->m_index, m_dest->m_index);
923
924 dump_label_to_pp (pp, false);
925
926 pp_printf (pp, "\"];\n");
927 }
928
929 /* Return a new json::object of the form
930 {"kind" : str,
931 "src_idx": int, the index of the source supernode,
932 "dst_idx": int, the index of the destination supernode,
933 "desc" : str. */
934
935 json::object *
to_json() const936 superedge::to_json () const
937 {
938 json::object *sedge_obj = new json::object ();
939 sedge_obj->set ("kind", new json::string (edge_kind_to_string (m_kind)));
940 sedge_obj->set ("src_idx", new json::integer_number (m_src->m_index));
941 sedge_obj->set ("dst_idx", new json::integer_number (m_dest->m_index));
942
943 {
944 pretty_printer pp;
945 pp_format_decoder (&pp) = default_tree_printer;
946 dump_label_to_pp (&pp, false);
947 sedge_obj->set ("desc", new json::string (pp_formatted_text (&pp)));
948 }
949
950 return sedge_obj;
951 }
952
953 /* If this is an intraprocedural superedge, return the associated
954 CFG edge. Otherwise, return NULL. */
955
956 ::edge
get_any_cfg_edge() const957 superedge::get_any_cfg_edge () const
958 {
959 if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
960 return sub->get_cfg_edge ();
961 return NULL;
962 }
963
964 /* If this is an interprocedural superedge, return the associated
965 cgraph_edge *. Otherwise, return NULL. */
966
967 cgraph_edge *
get_any_callgraph_edge() const968 superedge::get_any_callgraph_edge () const
969 {
970 if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
971 return sub->m_cedge;
972 return NULL;
973 }
974
975 /* Build a description of this superedge (e.g. "true" for the true
976 edge of a conditional, or "case 42:" for a switch case).
977
978 The caller is responsible for freeing the result.
979
980 If USER_FACING is false, the result also contains any underlying
981 CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
982
983 char *
get_description(bool user_facing) const984 superedge::get_description (bool user_facing) const
985 {
986 pretty_printer pp;
987 dump_label_to_pp (&pp, user_facing);
988 return xstrdup (pp_formatted_text (&pp));
989 }
990
991 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
992 superedges.
993
994 For true/false edges, print "true" or "false" to PP.
995
996 If USER_FACING is false, also print flags on the underlying CFG edge to
997 PP. */
998
999 void
dump_label_to_pp(pretty_printer * pp,bool user_facing) const1000 cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1001 bool user_facing) const
1002 {
1003 if (true_value_p ())
1004 pp_printf (pp, "true");
1005 else if (false_value_p ())
1006 pp_printf (pp, "false");
1007
1008 if (user_facing)
1009 return;
1010
1011 /* Express edge flags as a string with " | " separator.
1012 e.g. " (flags FALLTHRU | DFS_BACK)". */
1013 if (get_flags ())
1014 {
1015 pp_string (pp, " (flags ");
1016 bool seen_flag = false;
1017 #define DEF_EDGE_FLAG(NAME,IDX) \
1018 do { \
1019 if (get_flags () & EDGE_##NAME) \
1020 { \
1021 if (seen_flag) \
1022 pp_string (pp, " | "); \
1023 pp_printf (pp, "%s", (#NAME)); \
1024 seen_flag = true; \
1025 } \
1026 } while (0);
1027 #include "cfg-flags.def"
1028 #undef DEF_EDGE_FLAG
1029 pp_string (pp, ")");
1030 }
1031
1032 /* Otherwise, no label. */
1033 }
1034
1035 /* Get the phi argument for PHI for this CFG edge. */
1036
1037 tree
get_phi_arg(const gphi * phi) const1038 cfg_superedge::get_phi_arg (const gphi *phi) const
1039 {
1040 size_t index = m_cfg_edge->dest_idx;
1041 return gimple_phi_arg_def (phi, index);
1042 }
1043
1044 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1045 "switch" statements.
1046
1047 Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1048
1049 void
dump_label_to_pp(pretty_printer * pp,bool user_facing ATTRIBUTE_UNUSED) const1050 switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1051 bool user_facing ATTRIBUTE_UNUSED) const
1052 {
1053 tree case_label = get_case_label ();
1054 gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
1055 tree lower_bound = CASE_LOW (case_label);
1056 tree upper_bound = CASE_HIGH (case_label);
1057 if (lower_bound)
1058 {
1059 pp_printf (pp, "case ");
1060 dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1061 if (upper_bound)
1062 {
1063 pp_printf (pp, " ... ");
1064 dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0, false);
1065 }
1066 pp_printf (pp, ":");
1067 }
1068 else
1069 pp_printf (pp, "default:");
1070 }
1071
1072 /* Get the case label for this "switch" superedge. */
1073
1074 tree
get_case_label() const1075 switch_cfg_superedge::get_case_label () const
1076 {
1077 return gimple_switch_label (get_switch_stmt (), m_idx);
1078 }
1079
1080 /* Implementation of superedge::dump_label_to_pp for interprocedural
1081 superedges. */
1082
1083 void
dump_label_to_pp(pretty_printer * pp,bool user_facing ATTRIBUTE_UNUSED) const1084 callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
1085 bool user_facing ATTRIBUTE_UNUSED) const
1086 {
1087 switch (m_kind)
1088 {
1089 default:
1090 case SUPEREDGE_CFG_EDGE:
1091 gcc_unreachable ();
1092
1093 case SUPEREDGE_CALL:
1094 pp_printf (pp, "call");
1095 break;
1096
1097 case SUPEREDGE_RETURN:
1098 pp_printf (pp, "return");
1099 break;
1100
1101 case SUPEREDGE_INTRAPROCEDURAL_CALL:
1102 pp_printf (pp, "intraproc link");
1103 break;
1104 }
1105 }
1106
1107 /* Get the function that was called at this interprocedural call/return
1108 edge. */
1109
1110 function *
get_callee_function() const1111 callgraph_superedge::get_callee_function () const
1112 {
1113 return get_ultimate_function_for_cgraph_edge (m_cedge);
1114 }
1115
1116 /* Get the calling function at this interprocedural call/return edge. */
1117
1118 function *
get_caller_function() const1119 callgraph_superedge::get_caller_function () const
1120 {
1121 return m_cedge->caller->get_fun ();
1122 }
1123
1124 /* Get the fndecl that was called at this interprocedural call/return
1125 edge. */
1126
1127 tree
get_callee_decl() const1128 callgraph_superedge::get_callee_decl () const
1129 {
1130 return get_callee_function ()->decl;
1131 }
1132
1133 /* Get the calling fndecl at this interprocedural call/return edge. */
1134
1135 tree
get_caller_decl() const1136 callgraph_superedge::get_caller_decl () const
1137 {
1138 return get_caller_function ()->decl;
1139 }
1140
1141 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1142 to *OUT if OUT is non-NULL), and return the corresponding argument
1143 at the callsite. */
1144
1145 tree
get_arg_for_parm(tree parm_to_find,callsite_expr * out) const1146 callgraph_superedge::get_arg_for_parm (tree parm_to_find,
1147 callsite_expr *out) const
1148 {
1149 gcc_assert (TREE_CODE (parm_to_find) == PARM_DECL);
1150
1151 tree callee = get_callee_decl ();
1152 const gcall *call_stmt = get_call_stmt ();
1153
1154 unsigned i = 0;
1155 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1156 iter_parm = DECL_CHAIN (iter_parm), ++i)
1157 {
1158 if (i >= gimple_call_num_args (call_stmt))
1159 return NULL_TREE;
1160 if (iter_parm == parm_to_find)
1161 {
1162 if (out)
1163 *out = callsite_expr::from_zero_based_param (i);
1164 return gimple_call_arg (call_stmt, i);
1165 }
1166 }
1167
1168 /* Not found. */
1169 return NULL_TREE;
1170 }
1171
1172 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1173 If found, return the default SSA def of the corresponding parm within
1174 the callee, and if OUT is non-NULL, write the index to *OUT.
1175 Only the first match is handled. */
1176
1177 tree
get_parm_for_arg(tree arg_to_find,callsite_expr * out) const1178 callgraph_superedge::get_parm_for_arg (tree arg_to_find,
1179 callsite_expr *out) const
1180 {
1181 tree callee = get_callee_decl ();
1182 const gcall *call_stmt = get_call_stmt ();
1183
1184 unsigned i = 0;
1185 for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1186 iter_parm = DECL_CHAIN (iter_parm), ++i)
1187 {
1188 if (i >= gimple_call_num_args (call_stmt))
1189 return NULL_TREE;
1190 tree param = gimple_call_arg (call_stmt, i);
1191 if (arg_to_find == param)
1192 {
1193 if (out)
1194 *out = callsite_expr::from_zero_based_param (i);
1195 return ssa_default_def (get_callee_function (), iter_parm);
1196 }
1197 }
1198
1199 /* Not found. */
1200 return NULL_TREE;
1201 }
1202
1203 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1204 If non-NULL is returned, populate OUT. */
1205
1206 tree
map_expr_from_caller_to_callee(tree caller_expr,callsite_expr * out) const1207 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
1208 callsite_expr *out) const
1209 {
1210 /* Is it an argument (actual param)? If so, convert to
1211 parameter (formal param). */
1212 tree parm = get_parm_for_arg (caller_expr, out);
1213 if (parm)
1214 return parm;
1215 /* Otherwise try return value. */
1216 if (caller_expr == gimple_call_lhs (get_call_stmt ()))
1217 {
1218 if (out)
1219 *out = callsite_expr::from_return_value ();
1220 return DECL_RESULT (get_callee_decl ());
1221 }
1222
1223 return NULL_TREE;
1224 }
1225
1226 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1227 If non-NULL is returned, populate OUT. */
1228
1229 tree
map_expr_from_callee_to_caller(tree callee_expr,callsite_expr * out) const1230 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
1231 callsite_expr *out) const
1232 {
1233 if (callee_expr == NULL_TREE)
1234 return NULL_TREE;
1235
1236 /* If it's a parameter (formal param), get the argument (actual param). */
1237 if (TREE_CODE (callee_expr) == PARM_DECL)
1238 return get_arg_for_parm (callee_expr, out);
1239
1240 /* Similar for the default SSA name of the PARM_DECL. */
1241 if (TREE_CODE (callee_expr) == SSA_NAME
1242 && SSA_NAME_IS_DEFAULT_DEF (callee_expr)
1243 && TREE_CODE (SSA_NAME_VAR (callee_expr)) == PARM_DECL)
1244 return get_arg_for_parm (SSA_NAME_VAR (callee_expr), out);
1245
1246 /* Otherwise try return value. */
1247 if (callee_expr == DECL_RESULT (get_callee_decl ()))
1248 {
1249 if (out)
1250 *out = callsite_expr::from_return_value ();
1251 return gimple_call_lhs (get_call_stmt ());
1252 }
1253
1254 return NULL_TREE;
1255 }
1256
1257 } // namespace ana
1258
1259 #endif /* #if ENABLE_ANALYZER */
1260