Branch data Line data Source code
1 : : /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 : : Copyright (C) 2019-2025 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 "analyzer/common.h"
22 : :
23 : : #include "timevar.h"
24 : : #include "gimple-pretty-print.h"
25 : : #include "ordered-hash-map.h"
26 : : #include "options.h"
27 : : #include "cgraph.h"
28 : : #include "cfg.h"
29 : : #include "digraph.h"
30 : : #include "tree-cfg.h"
31 : : #include "tree-dfa.h"
32 : : #include "cfganal.h"
33 : : #include "except.h"
34 : :
35 : : #include "analyzer/supergraph.h"
36 : : #include "analyzer/analyzer-logging.h"
37 : : #include "analyzer/region-model.h"
38 : :
39 : : #if ENABLE_ANALYZER
40 : :
41 : : namespace ana {
42 : :
43 : : /* Get the function of the ultimate alias target being called at EDGE,
44 : : if any. */
45 : :
46 : : function *
47 : 120694 : get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
48 : : {
49 : 120694 : cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
50 : 120694 : if (!ultimate_node)
51 : : return nullptr;
52 : 120694 : return ultimate_node->get_fun ();
53 : : }
54 : :
55 : : /* Get the cgraph_edge, but only if there's an underlying function body. */
56 : :
57 : : cgraph_edge *
58 : 373389 : supergraph_call_edge (function *fun, const gimple *stmt)
59 : : {
60 : 462043 : const gcall *call = dyn_cast<const gcall *> (stmt);
61 : 105093 : if (!call)
62 : : return nullptr;
63 : 105093 : cgraph_edge *edge
64 : 105093 : = cgraph_node::get (fun->decl)->get_edge (const_cast <gimple *> (stmt));
65 : 105093 : if (!edge)
66 : : return nullptr;
67 : 102770 : if (!edge->callee)
68 : : return nullptr; /* e.g. for a function pointer. */
69 : 101306 : if (!get_ultimate_function_for_cgraph_edge (edge))
70 : : return nullptr;
71 : : return edge;
72 : : }
73 : :
74 : : /* class saved_uids.
75 : :
76 : : In order to ensure consistent results without relying on the ordering
77 : : of pointer values we assign a uid to each gimple stmt, globally unique
78 : : across all functions.
79 : :
80 : : Normally, the stmt uids are a scratch space that each pass can freely
81 : : assign its own values to. However, in the case of LTO, the uids are
82 : : used to associate call stmts with callgraph edges between the WPA phase
83 : : (where the analyzer runs in LTO mode) and the LTRANS phase; if the
84 : : analyzer changes them in the WPA phase, it leads to errors when
85 : : streaming the code back in at LTRANS.
86 : : lto_prepare_function_for_streaming has code to renumber the stmt UIDs
87 : : when the code is streamed back out, but for some reason this isn't
88 : : called for clones.
89 : :
90 : : Hence, as a workaround, this class has responsibility for tracking
91 : : the original uids and restoring them once the pass is complete
92 : : (in the supergraph dtor). */
93 : :
94 : : /* Give STMT a globally unique uid, storing its original uid so it can
95 : : later be restored. */
96 : :
97 : : void
98 : 132819 : saved_uids::make_uid_unique (gimple *stmt)
99 : : {
100 : 132819 : unsigned next_uid = m_old_stmt_uids.length ();
101 : 132819 : unsigned old_stmt_uid = stmt->uid;
102 : 132819 : stmt->uid = next_uid;
103 : 132819 : m_old_stmt_uids.safe_push
104 : 132819 : (std::pair<gimple *, unsigned> (stmt, old_stmt_uid));
105 : 132819 : }
106 : :
107 : : /* Restore the saved uids of all stmts. */
108 : :
109 : : void
110 : 3308 : saved_uids::restore_uids () const
111 : : {
112 : 3308 : unsigned i;
113 : 3308 : std::pair<gimple *, unsigned> *pair;
114 : 136127 : FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
115 : 132819 : pair->first->uid = pair->second;
116 : 3308 : }
117 : :
118 : : /* supergraph's ctor. Walk the callgraph, building supernodes for each
119 : : CFG basic block, splitting the basic blocks at callsites. Join
120 : : together the supernodes with interprocedural and intraprocedural
121 : : superedges as appropriate.
122 : : Assign UIDs to the gimple stmts. */
123 : :
124 : 3308 : supergraph::supergraph (logger *logger)
125 : : {
126 : 3308 : auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
127 : :
128 : 3308 : LOG_FUNC (logger);
129 : :
130 : : /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
131 : 3308 : {
132 : : /* Sort the cgraph_nodes? */
133 : 3308 : cgraph_node *node;
134 : 13417 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
135 : : {
136 : 10109 : function *fun = node->get_fun ();
137 : :
138 : : /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
139 : : the supergraph (by doing it per-function). */
140 : 10109 : auto_cfun sentinel (fun);
141 : 10109 : mark_dfs_back_edges ();
142 : :
143 : 10109 : const int start_idx = m_nodes.length ();
144 : :
145 : 10109 : basic_block bb;
146 : 67533 : FOR_ALL_BB_FN (bb, fun)
147 : : {
148 : : /* The initial supernode for the BB gets the phi nodes (if any). */
149 : 57424 : supernode *node_for_stmts
150 : 57424 : = add_node (fun, bb, nullptr, phi_nodes (bb));
151 : 57424 : m_bb_to_initial_node.put (bb, node_for_stmts);
152 : 66645 : for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
153 : 9221 : gsi_next (&gpi))
154 : : {
155 : 9221 : gimple *stmt = gsi_stmt (gpi);
156 : 9221 : m_stmt_to_node_t.put (stmt, node_for_stmts);
157 : 9221 : m_stmt_uids.make_uid_unique (stmt);
158 : : }
159 : :
160 : : /* Append statements from BB to the current supernode, splitting
161 : : them into a new supernode at each call site; such call statements
162 : : appear in both supernodes (representing call and return). */
163 : 57424 : gimple_stmt_iterator gsi;
164 : 240231 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
165 : : {
166 : 125383 : gimple *stmt = gsi_stmt (gsi);
167 : : /* Discard debug stmts here, so we don't have to check for
168 : : them anywhere within the analyzer. */
169 : 125383 : if (is_gimple_debug (stmt))
170 : 1785 : continue;
171 : 123598 : node_for_stmts->m_stmts.safe_push (stmt);
172 : 123598 : m_stmt_to_node_t.put (stmt, node_for_stmts);
173 : 123598 : m_stmt_uids.make_uid_unique (stmt);
174 : 123598 : if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
175 : : {
176 : 3609 : m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts);
177 : 3609 : node_for_stmts = add_node (fun, bb, as_a <gcall *> (stmt),
178 : : nullptr);
179 : 3609 : m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
180 : : }
181 : : else
182 : : {
183 : : // maybe call is via a function pointer
184 : 159599 : if (gcall *call = dyn_cast<gcall *> (stmt))
185 : : {
186 : 36001 : cgraph_edge *edge
187 : 36001 : = cgraph_node::get (fun->decl)->get_edge (stmt);
188 : 36001 : if (!edge || !edge->callee)
189 : : {
190 : 745 : supernode *old_node_for_stmts = node_for_stmts;
191 : 745 : node_for_stmts = add_node (fun, bb, call, nullptr);
192 : :
193 : 745 : superedge *sedge
194 : : = new callgraph_superedge (old_node_for_stmts,
195 : : node_for_stmts,
196 : : SUPEREDGE_INTRAPROCEDURAL_CALL,
197 : 745 : nullptr);
198 : 745 : add_edge (sedge);
199 : : }
200 : : }
201 : : }
202 : : }
203 : :
204 : 57424 : m_bb_to_final_node.put (bb, node_for_stmts);
205 : : }
206 : :
207 : 10109 : const unsigned num_snodes = m_nodes.length () - start_idx;
208 : 10109 : m_function_to_num_snodes.put (fun, num_snodes);
209 : :
210 : 10109 : if (logger)
211 : : {
212 : 2 : const int end_idx = m_nodes.length () - 1;
213 : 2 : logger->log ("SN: %i...%i: function %qD",
214 : : start_idx, end_idx, fun->decl);
215 : : }
216 : : }
217 : : }
218 : :
219 : : /* Second pass: make superedges. */
220 : 3308 : {
221 : : /* Make superedges for CFG edges. */
222 : 3308 : for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
223 : 121460 : iter != m_bb_to_final_node.end ();
224 : 57424 : ++iter)
225 : : {
226 : 57424 : basic_block bb = (*iter).first;
227 : 57424 : supernode *src_supernode = (*iter).second;
228 : :
229 : 57424 : ::edge cfg_edge;
230 : 57424 : int idx;
231 : 57424 : if (bb->succs)
232 : 115727 : FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
233 : : {
234 : 58303 : basic_block dest_cfg_block = cfg_edge->dest;
235 : 58303 : supernode *dest_supernode
236 : 58303 : = *m_bb_to_initial_node.get (dest_cfg_block);
237 : 58303 : cfg_superedge *cfg_sedge
238 : 58303 : = add_cfg_edge (src_supernode, dest_supernode, cfg_edge);
239 : 58303 : m_cfg_edge_to_cfg_superedge.put (cfg_edge, cfg_sedge);
240 : : }
241 : : }
242 : :
243 : : /* Make interprocedural superedges for calls. */
244 : 3308 : {
245 : 3308 : for (cgraph_edge_to_node_t::iterator iter
246 : 3308 : = m_cgraph_edge_to_caller_prev_node.begin ();
247 : 11514 : iter != m_cgraph_edge_to_caller_prev_node.end ();
248 : 3609 : ++iter)
249 : : {
250 : 3609 : cgraph_edge *edge = (*iter).first;
251 : 3609 : supernode *caller_prev_supernode = (*iter).second;
252 : 3609 : function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
253 : 3609 : if (!callee_fn || !callee_fn->cfg)
254 : 0 : continue;
255 : 3609 : basic_block callee_cfg_block = ENTRY_BLOCK_PTR_FOR_FN (callee_fn);
256 : 3609 : supernode *callee_supernode
257 : 3609 : = *m_bb_to_initial_node.get (callee_cfg_block);
258 : 3609 : call_superedge *sedge
259 : 3609 : = add_call_superedge (caller_prev_supernode,
260 : : callee_supernode,
261 : 3609 : edge);
262 : 3609 : m_cgraph_edge_to_call_superedge.put (edge, sedge);
263 : : }
264 : : }
265 : :
266 : : /* Make interprocedural superedges for returns. */
267 : 3308 : {
268 : 3308 : for (cgraph_edge_to_node_t::iterator iter
269 : 3308 : = m_cgraph_edge_to_caller_next_node.begin ();
270 : 11514 : iter != m_cgraph_edge_to_caller_next_node.end ();
271 : 3609 : ++iter)
272 : : {
273 : 3609 : cgraph_edge *edge = (*iter).first;
274 : 3609 : supernode *caller_next_supernode = (*iter).second;
275 : 3609 : function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
276 : 3609 : if (!callee_fn || !callee_fn->cfg)
277 : 0 : continue;
278 : 3609 : basic_block callee_cfg_block = EXIT_BLOCK_PTR_FOR_FN (callee_fn);
279 : 3609 : supernode *callee_supernode
280 : 3609 : = *m_bb_to_initial_node.get (callee_cfg_block);
281 : 3609 : return_superedge *sedge
282 : 3609 : = add_return_superedge (callee_supernode,
283 : : caller_next_supernode,
284 : 3609 : edge);
285 : 3609 : m_cgraph_edge_to_return_superedge.put (edge, sedge);
286 : : }
287 : : }
288 : :
289 : : /* Make intraprocedural superedges linking the two halves of a call. */
290 : 3308 : {
291 : 3308 : for (cgraph_edge_to_node_t::iterator iter
292 : 3308 : = m_cgraph_edge_to_caller_prev_node.begin ();
293 : 11514 : iter != m_cgraph_edge_to_caller_prev_node.end ();
294 : 3609 : ++iter)
295 : : {
296 : 3609 : cgraph_edge *edge = (*iter).first;
297 : 3609 : supernode *caller_prev_supernode = (*iter).second;
298 : 3609 : supernode *caller_next_supernode
299 : 3609 : = *m_cgraph_edge_to_caller_next_node.get (edge);
300 : 3609 : superedge *sedge
301 : : = new callgraph_superedge (caller_prev_supernode,
302 : : caller_next_supernode,
303 : : SUPEREDGE_INTRAPROCEDURAL_CALL,
304 : 3609 : edge);
305 : 3609 : add_edge (sedge);
306 : 3609 : m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
307 : : }
308 : :
309 : : }
310 : : }
311 : 3308 : }
312 : :
313 : : /* supergraph's dtor. Reset stmt uids. */
314 : :
315 : 3308 : supergraph::~supergraph ()
316 : : {
317 : 3308 : m_stmt_uids.restore_uids ();
318 : 3308 : }
319 : :
320 : : /* Dump this graph in .dot format to PP, using DUMP_ARGS.
321 : : Cluster the supernodes by function, then by BB from original CFG. */
322 : :
323 : : void
324 : 12 : supergraph::dump_dot_to_pp (pretty_printer *pp,
325 : : const dump_args_t &dump_args) const
326 : : {
327 : 12 : graphviz_out gv (pp);
328 : :
329 : 12 : pp_string (pp, "digraph \"");
330 : 12 : pp_write_text_to_stream (pp);
331 : 12 : pp_string (pp, "supergraph");
332 : 12 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
333 : 12 : pp_string (pp, "\" {\n");
334 : 12 : gv.indent ();
335 : :
336 : 12 : gv.println ("overlap=false;");
337 : 12 : gv.println ("compound=true;");
338 : :
339 : : /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
340 : : https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
341 : : */
342 : :
343 : : /* Break out the supernodes into clusters by function. */
344 : 12 : {
345 : 12 : cgraph_node *node;
346 : 48 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
347 : : {
348 : 36 : function *fun = node->get_fun ();
349 : 36 : gcc_assert (fun);
350 : 36 : const char *funcname = function_name (fun);
351 : 36 : gv.println ("subgraph \"cluster_%s\" {",
352 : : funcname);
353 : 36 : gv.indent ();
354 : 36 : pp_printf (pp,
355 : : ("style=\"dashed\";"
356 : : " color=\"black\";"
357 : : " label=\"%s\";\n"),
358 : : funcname);
359 : :
360 : : /* Break out the nodes into clusters by BB from original CFG. */
361 : 36 : {
362 : 36 : basic_block bb;
363 : 252 : FOR_ALL_BB_FN (bb, fun)
364 : : {
365 : 216 : if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
366 : : {
367 : 0 : gv.println ("subgraph \"cluster_%s_bb_%i\" {",
368 : : funcname, bb->index);
369 : 0 : gv.indent ();
370 : 0 : pp_printf (pp,
371 : : ("style=\"dashed\";"
372 : : " color=\"black\";"
373 : : " label=\"bb: %i\";\n"),
374 : : bb->index);
375 : : }
376 : :
377 : : // TODO: maybe keep an index per-function/per-bb to speed this up???
378 : : int i;
379 : : supernode *n;
380 : 4320 : FOR_EACH_VEC_ELT (m_nodes, i, n)
381 : 4104 : if (n->m_fun == fun && n->m_bb == bb)
382 : 228 : n->dump_dot (&gv, dump_args);
383 : :
384 : 216 : if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
385 : : {
386 : : /* Terminate per-bb "subgraph" */
387 : 0 : gv.outdent ();
388 : 0 : gv.println ("}");
389 : : }
390 : : }
391 : : }
392 : :
393 : : /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
394 : 36 : pp_string (pp, "\t");
395 : 36 : get_node_for_function_entry (*fun)->dump_dot_id (pp);
396 : 36 : pp_string (pp, ":s -> ");
397 : 36 : get_node_for_function_exit (*fun)->dump_dot_id (pp);
398 : 36 : pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
399 : :
400 : : /* Terminate per-function "subgraph" */
401 : 36 : gv.outdent ();
402 : 36 : gv.println ("}");
403 : : }
404 : : }
405 : :
406 : : /* Superedges. */
407 : : int i;
408 : : superedge *e;
409 : 264 : FOR_EACH_VEC_ELT (m_edges, i, e)
410 : 252 : e->dump_dot (&gv, dump_args);
411 : :
412 : : /* Terminate "digraph" */
413 : 12 : gv.outdent ();
414 : 12 : gv.println ("}");
415 : 12 : }
416 : :
417 : : /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
418 : :
419 : : void
420 : 12 : supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
421 : : {
422 : 12 : std::unique_ptr<pretty_printer> pp (global_dc->clone_printer ());
423 : 12 : pp_show_color (pp.get ()) = 0;
424 : : /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
425 : : trying to prettify things by showing the underlying var. */
426 : 12 : pp_format_decoder (pp.get ()) = default_tree_printer;
427 : :
428 : 12 : pp->set_output_stream (fp);
429 : 12 : dump_dot_to_pp (pp.get (), dump_args);
430 : 12 : pp_flush (pp.get ());
431 : 12 : }
432 : :
433 : : /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
434 : :
435 : : void
436 : 12 : supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
437 : : {
438 : 12 : FILE *fp = fopen (path, "w");
439 : 12 : dump_dot_to_file (fp, dump_args);
440 : 12 : fclose (fp);
441 : 12 : }
442 : :
443 : : /* Return a new json::object of the form
444 : : {"nodes" : [objs for snodes],
445 : : "edges" : [objs for sedges]}. */
446 : :
447 : : std::unique_ptr<json::object>
448 : 0 : supergraph::to_json () const
449 : : {
450 : 0 : auto sgraph_obj = std::make_unique<json::object> ();
451 : :
452 : : /* Nodes. */
453 : 0 : {
454 : 0 : auto nodes_arr = std::make_unique<json::array> ();
455 : 0 : unsigned i;
456 : 0 : supernode *n;
457 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, n)
458 : 0 : nodes_arr->append (n->to_json ());
459 : 0 : sgraph_obj->set ("nodes", std::move (nodes_arr));
460 : 0 : }
461 : :
462 : : /* Edges. */
463 : 0 : {
464 : 0 : auto edges_arr = std::make_unique<json::array> ();
465 : 0 : unsigned i;
466 : 0 : superedge *n;
467 : 0 : FOR_EACH_VEC_ELT (m_edges, i, n)
468 : 0 : edges_arr->append (n->to_json ());
469 : 0 : sgraph_obj->set ("edges", std::move (edges_arr));
470 : 0 : }
471 : :
472 : 0 : return sgraph_obj;
473 : : }
474 : :
475 : : /* Create a supernode for BB within FUN and add it to this supergraph.
476 : :
477 : : If RETURNING_CALL is non-NULL, the supernode represents the resumption
478 : : of the basic block after returning from that call.
479 : :
480 : : If PHI_NODES is non-NULL, this is the initial supernode for the basic
481 : : block, and is responsible for any handling of the phi nodes. */
482 : :
483 : : supernode *
484 : 61778 : supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
485 : : gimple_seq phi_nodes)
486 : : {
487 : 61778 : supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
488 : 120252 : m_nodes.length ());
489 : 61778 : m_nodes.safe_push (n);
490 : 61778 : return n;
491 : : }
492 : :
493 : : /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
494 : : adding it to this supergraph.
495 : :
496 : : If the edge is for a switch or eh_dispatch statement, create a
497 : : switch_cfg_superedge or eh_dispatch_cfg_superedge subclass,
498 : : respectively */
499 : :
500 : : cfg_superedge *
501 : 58303 : supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e)
502 : : {
503 : : /* Special-case switch and eh_dispatch edges. */
504 : 58303 : gimple *stmt = src->get_last_stmt ();
505 : 58303 : std::unique_ptr<cfg_superedge> new_edge;
506 : 58303 : if (stmt && stmt->code == GIMPLE_SWITCH)
507 : 3031 : new_edge = std::make_unique<switch_cfg_superedge> (src, dest, e);
508 : 43351 : else if (stmt && stmt->code == GIMPLE_EH_DISPATCH)
509 : 384 : new_edge = eh_dispatch_cfg_superedge::make (src, dest, e,
510 : 384 : as_a <geh_dispatch *> (stmt));
511 : : else
512 : 55080 : new_edge = std::make_unique<cfg_superedge> (src, dest, e);
513 : 58303 : add_edge (new_edge.get ());
514 : 58303 : return new_edge.release ();
515 : 58303 : }
516 : :
517 : : /* Create and add a call_superedge representing an interprocedural call
518 : : from SRC to DEST, using CEDGE. */
519 : :
520 : : call_superedge *
521 : 3609 : supergraph::add_call_superedge (supernode *src, supernode *dest,
522 : : cgraph_edge *cedge)
523 : : {
524 : 3609 : call_superedge *new_edge = new call_superedge (src, dest, cedge);
525 : 3609 : add_edge (new_edge);
526 : 3609 : return new_edge;
527 : : }
528 : :
529 : : /* Create and add a return_superedge representing returning from an
530 : : interprocedural call, returning from SRC to DEST, using CEDGE. */
531 : :
532 : : return_superedge *
533 : 3609 : supergraph::add_return_superedge (supernode *src, supernode *dest,
534 : : cgraph_edge *cedge)
535 : : {
536 : 3609 : return_superedge *new_edge = new return_superedge (src, dest, cedge);
537 : 3609 : add_edge (new_edge);
538 : 3609 : return new_edge;
539 : : }
540 : :
541 : : /* Implementation of dnode::dump_dot vfunc for supernodes.
542 : :
543 : : Write a cluster for the node, and within it a .dot node showing
544 : : the phi nodes and stmts. Call into any node annotator from ARGS to
545 : : potentially add other records to the cluster. */
546 : :
547 : : void
548 : 228 : supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
549 : : {
550 : 228 : gv->println ("subgraph cluster_node_%i {",
551 : 228 : m_index);
552 : 228 : gv->indent ();
553 : :
554 : 228 : gv->println("style=\"solid\";");
555 : 228 : gv->println("color=\"black\";");
556 : 228 : gv->println("fillcolor=\"lightgrey\";");
557 : 228 : gv->println("label=\"sn: %i (bb: %i)\";", m_index, m_bb->index);
558 : :
559 : 228 : pretty_printer *pp = gv->get_pp ();
560 : :
561 : 228 : if (args.m_node_annotator)
562 : 152 : args.m_node_annotator->add_node_annotations (gv, *this, false);
563 : :
564 : 228 : gv->write_indent ();
565 : 228 : dump_dot_id (pp);
566 : 228 : pp_printf (pp,
567 : : " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
568 : : "lightgrey");
569 : 228 : pp_string (pp, "<TABLE BORDER=\"0\">");
570 : 228 : pp_write_text_to_stream (pp);
571 : :
572 : 228 : bool had_row = false;
573 : :
574 : : /* Give any annotator the chance to add its own per-node TR elements. */
575 : 228 : if (args.m_node_annotator)
576 : 152 : if (args.m_node_annotator->add_node_annotations (gv, *this, true))
577 : 228 : had_row = true;
578 : :
579 : 228 : if (m_returning_call)
580 : : {
581 : 12 : gv->begin_trtd ();
582 : 12 : pp_string (pp, "returning call: ");
583 : 12 : gv->end_tdtr ();
584 : :
585 : 12 : gv->begin_tr ();
586 : 12 : gv->begin_td ();
587 : 12 : pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
588 : 12 : pp_write_text_as_html_like_dot_to_stream (pp);
589 : 12 : gv->end_td ();
590 : : /* Give any annotator the chance to add per-stmt TD elements to
591 : : this row. */
592 : 12 : if (args.m_node_annotator)
593 : 8 : args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
594 : : true);
595 : 12 : gv->end_tr ();
596 : :
597 : : /* Give any annotator the chance to add per-stmt TR elements. */
598 : 12 : if (args.m_node_annotator)
599 : 8 : args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
600 : : false);
601 : 12 : pp_newline (pp);
602 : :
603 : 12 : had_row = true;
604 : : }
605 : :
606 : 228 : if (entry_p ())
607 : : {
608 : 36 : pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
609 : 36 : pp_newline (pp);
610 : 36 : had_row = true;
611 : : }
612 : :
613 : 228 : if (return_p ())
614 : : {
615 : 36 : pp_string (pp, "<TR><TD>EXIT</TD></TR>");
616 : 36 : pp_newline (pp);
617 : 36 : had_row = true;
618 : : }
619 : :
620 : : /* Phi nodes. */
621 : 228 : for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
622 : 264 : !gsi_end_p (gpi); gsi_next (&gpi))
623 : : {
624 : 36 : const gimple *stmt = gsi_stmt (gpi);
625 : 36 : gv->begin_tr ();
626 : 36 : gv->begin_td ();
627 : 36 : pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
628 : 36 : pp_write_text_as_html_like_dot_to_stream (pp);
629 : 36 : gv->end_td ();
630 : : /* Give any annotator the chance to add per-phi TD elements to
631 : : this row. */
632 : 36 : if (args.m_node_annotator)
633 : 24 : args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
634 : 36 : gv->end_tr ();
635 : :
636 : : /* Give any annotator the chance to add per-phi TR elements. */
637 : 36 : if (args.m_node_annotator)
638 : 24 : args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
639 : :
640 : 36 : pp_newline (pp);
641 : 36 : had_row = true;
642 : : }
643 : :
644 : : /* Statements. */
645 : : int i;
646 : : gimple *stmt;
647 : 585 : FOR_EACH_VEC_ELT (m_stmts, i, stmt)
648 : : {
649 : 357 : gv->begin_tr ();
650 : 357 : gv->begin_td ();
651 : 357 : pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
652 : 357 : pp_write_text_as_html_like_dot_to_stream (pp);
653 : 357 : gv->end_td ();
654 : : /* Give any annotator the chance to add per-stmt TD elements to
655 : : this row. */
656 : 357 : if (args.m_node_annotator)
657 : 238 : args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
658 : 357 : gv->end_tr ();
659 : :
660 : : /* Give any annotator the chance to add per-stmt TR elements. */
661 : 357 : if (args.m_node_annotator)
662 : 238 : args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
663 : :
664 : 357 : pp_newline (pp);
665 : 357 : had_row = true;
666 : : }
667 : :
668 : : /* Give any annotator the chance to add additional per-node TR elements
669 : : to the end of the TABLE. */
670 : 228 : if (args.m_node_annotator)
671 : 152 : if (args.m_node_annotator->add_after_node_annotations (gv, *this))
672 : : had_row = true;
673 : :
674 : : /* Graphviz requires a TABLE element to have at least one TR
675 : : (and each TR to have at least one TD). */
676 : 152 : if (!had_row)
677 : : {
678 : 8 : pp_string (pp, "<TR><TD>(empty)</TD></TR>");
679 : 8 : pp_newline (pp);
680 : : }
681 : :
682 : 228 : pp_string (pp, "</TABLE>>];\n\n");
683 : 228 : pp_flush (pp);
684 : :
685 : : /* Terminate "subgraph" */
686 : 228 : gv->outdent ();
687 : 228 : gv->println ("}");
688 : 228 : }
689 : :
690 : : /* Write an ID for this node to PP, for use in .dot output. */
691 : :
692 : : void
693 : 804 : supernode::dump_dot_id (pretty_printer *pp) const
694 : : {
695 : 804 : pp_printf (pp, "node_%i", m_index);
696 : 804 : }
697 : :
698 : : /* Return a new json::object of the form
699 : : {"idx": int,
700 : : "fun": optional str
701 : : "bb_idx": int,
702 : : "returning_call": optional str,
703 : : "phis": [str],
704 : : "stmts" : [str]}. */
705 : :
706 : : std::unique_ptr<json::object>
707 : 0 : supernode::to_json () const
708 : : {
709 : 0 : auto snode_obj = std::make_unique<json::object> ();
710 : :
711 : 0 : snode_obj->set_integer ("idx", m_index);
712 : 0 : snode_obj->set_integer ("bb_idx", m_bb->index);
713 : 0 : if (function *fun = get_function ())
714 : 0 : snode_obj->set_string ("fun", function_name (fun));
715 : :
716 : 0 : if (m_returning_call)
717 : : {
718 : 0 : pretty_printer pp;
719 : 0 : pp_format_decoder (&pp) = default_tree_printer;
720 : 0 : pp_gimple_stmt_1 (&pp, m_returning_call, 0, (dump_flags_t)0);
721 : 0 : snode_obj->set_string ("returning_call", pp_formatted_text (&pp));
722 : 0 : }
723 : :
724 : : /* Phi nodes. */
725 : 0 : {
726 : 0 : auto phi_arr = std::make_unique<json::array> ();
727 : 0 : for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
728 : 0 : !gsi_end_p (gpi); gsi_next (&gpi))
729 : : {
730 : 0 : const gimple *stmt = gsi_stmt (gpi);
731 : 0 : pretty_printer pp;
732 : 0 : pp_format_decoder (&pp) = default_tree_printer;
733 : 0 : pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
734 : 0 : phi_arr->append_string (pp_formatted_text (&pp));
735 : 0 : }
736 : 0 : snode_obj->set ("phis", std::move (phi_arr));
737 : 0 : }
738 : :
739 : : /* Statements. */
740 : 0 : {
741 : 0 : auto stmt_arr = std::make_unique<json::array> ();
742 : 0 : int i;
743 : 0 : gimple *stmt;
744 : 0 : FOR_EACH_VEC_ELT (m_stmts, i, stmt)
745 : : {
746 : 0 : pretty_printer pp;
747 : 0 : pp_format_decoder (&pp) = default_tree_printer;
748 : 0 : pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
749 : 0 : stmt_arr->append_string (pp_formatted_text (&pp));
750 : 0 : }
751 : 0 : snode_obj->set ("stmts", std::move (stmt_arr));
752 : 0 : }
753 : :
754 : 0 : return snode_obj;
755 : : }
756 : :
757 : : /* Get a location_t for the start of this supernode. */
758 : :
759 : : location_t
760 : 21758 : supernode::get_start_location () const
761 : : {
762 : 21758 : if (m_returning_call
763 : 21758 : && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
764 : 0 : return m_returning_call->location;
765 : :
766 : : int i;
767 : : gimple *stmt;
768 : 23032 : FOR_EACH_VEC_ELT (m_stmts, i, stmt)
769 : 16085 : if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
770 : 14811 : return stmt->location;
771 : :
772 : 6947 : if (entry_p ())
773 : : {
774 : : // TWEAK: show the decl instead; this leads to more readable output:
775 : 5387 : return DECL_SOURCE_LOCATION (m_fun->decl);
776 : :
777 : : return m_fun->function_start_locus;
778 : : }
779 : 1560 : if (return_p ())
780 : 1096 : return m_fun->function_end_locus;
781 : :
782 : : /* We have no locations for stmts. If we have a single out-edge that's
783 : : a CFG edge, the goto_locus of that edge is a better location for this
784 : : than UNKNOWN_LOCATION. */
785 : 464 : if (m_succs.length () == 1)
786 : 424 : if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ())
787 : 424 : return cfg_sedge->get_goto_locus ();
788 : :
789 : : return UNKNOWN_LOCATION;
790 : : }
791 : :
792 : : /* Get a location_t for the end of this supernode. */
793 : :
794 : : location_t
795 : 98 : supernode::get_end_location () const
796 : : {
797 : 98 : int i;
798 : 98 : gimple *stmt;
799 : 98 : FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
800 : 0 : if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
801 : 0 : return stmt->location;
802 : :
803 : 98 : if (m_returning_call
804 : 98 : && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
805 : 33 : return m_returning_call->location;
806 : :
807 : 65 : if (entry_p ())
808 : 0 : return m_fun->function_start_locus;
809 : 65 : if (return_p ())
810 : 5 : return m_fun->function_end_locus;
811 : :
812 : : /* If we have a single out-edge that's a CFG edge, use the goto_locus of
813 : : that edge. */
814 : 60 : if (m_succs.length () == 1)
815 : 60 : if (const cfg_superedge *cfg_sedge = m_succs[0]->dyn_cast_cfg_superedge ())
816 : 60 : return cfg_sedge->get_goto_locus ();
817 : :
818 : : return UNKNOWN_LOCATION;
819 : : }
820 : :
821 : : /* Given STMT within this supernode, return its index within m_stmts. */
822 : :
823 : : unsigned int
824 : 82707 : supernode::get_stmt_index (const gimple *stmt) const
825 : : {
826 : 82707 : unsigned i;
827 : 82707 : gimple *iter_stmt;
828 : 12446140 : FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
829 : 12446140 : if (iter_stmt == stmt)
830 : 82707 : return i;
831 : 0 : gcc_unreachable ();
832 : : }
833 : :
834 : : /* Get any label_decl for this supernode, or NULL_TREE if there isn't one. */
835 : :
836 : : tree
837 : 271 : supernode::get_label () const
838 : : {
839 : 271 : if (m_stmts.length () == 0)
840 : : return NULL_TREE;
841 : 271 : const glabel *label_stmt = dyn_cast<const glabel *> (m_stmts[0]);
842 : 208 : if (!label_stmt)
843 : : return NULL_TREE;
844 : 208 : return gimple_label_label (label_stmt);
845 : : }
846 : :
847 : : /* Get a string for PK. */
848 : :
849 : : static const char *
850 : 26 : edge_kind_to_string (enum edge_kind kind)
851 : : {
852 : 26 : switch (kind)
853 : : {
854 : 0 : default:
855 : 0 : gcc_unreachable ();
856 : : case SUPEREDGE_CFG_EDGE:
857 : : return "SUPEREDGE_CFG_EDGE";
858 : 3 : case SUPEREDGE_CALL:
859 : 3 : return "SUPEREDGE_CALL";
860 : 3 : case SUPEREDGE_RETURN:
861 : 3 : return "SUPEREDGE_RETURN";
862 : 0 : case SUPEREDGE_INTRAPROCEDURAL_CALL:
863 : 0 : return "SUPEREDGE_INTRAPROCEDURAL_CALL";
864 : : }
865 : : };
866 : :
867 : : /* Dump this superedge to PP. */
868 : :
869 : : void
870 : 0 : superedge::dump (pretty_printer *pp) const
871 : : {
872 : 0 : pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_index, m_dest->m_index);
873 : 0 : label_text desc (get_description (false));
874 : 0 : if (strlen (desc.get ()) > 0)
875 : : {
876 : 0 : pp_space (pp);
877 : 0 : pp_string (pp, desc.get ());
878 : : }
879 : 0 : }
880 : :
881 : : /* Dump this superedge to stderr. */
882 : :
883 : : DEBUG_FUNCTION void
884 : 0 : superedge::dump () const
885 : : {
886 : 0 : tree_dump_pretty_printer pp (stderr);
887 : 0 : dump (&pp);
888 : 0 : pp_newline (&pp);
889 : 0 : }
890 : :
891 : : /* Implementation of dedge::dump_dot for superedges.
892 : : Write a .dot edge to GV representing this superedge. */
893 : :
894 : : void
895 : 252 : superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
896 : : {
897 : 252 : const char *style = "\"solid,bold\"";
898 : 252 : const char *color = "black";
899 : 252 : int weight = 10;
900 : 252 : const char *constraint = "true";
901 : :
902 : 252 : switch (m_kind)
903 : : {
904 : 0 : default:
905 : 0 : gcc_unreachable ();
906 : : case SUPEREDGE_CFG_EDGE:
907 : : break;
908 : 12 : case SUPEREDGE_CALL:
909 : 12 : color = "red";
910 : 12 : break;
911 : 12 : case SUPEREDGE_RETURN:
912 : 12 : color = "green";
913 : 12 : break;
914 : 12 : case SUPEREDGE_INTRAPROCEDURAL_CALL:
915 : 12 : style = "\"dotted\"";
916 : 12 : break;
917 : : }
918 : :
919 : : /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
920 : 252 : if (::edge cfg_edge = get_any_cfg_edge ())
921 : : {
922 : 216 : if (cfg_edge->flags & EDGE_FAKE)
923 : : {
924 : : style = "dotted";
925 : : color = "green";
926 : : weight = 0;
927 : : }
928 : 216 : else if (cfg_edge->flags & EDGE_DFS_BACK)
929 : : {
930 : : style = "\"dotted,bold\"";
931 : : color = "blue";
932 : : weight = 10;
933 : : }
934 : 192 : else if (cfg_edge->flags & EDGE_FALLTHRU)
935 : : {
936 : 96 : color = "blue";
937 : 96 : weight = 100;
938 : : }
939 : :
940 : 216 : if (cfg_edge->flags & EDGE_ABNORMAL)
941 : 0 : color = "red";
942 : : }
943 : :
944 : 252 : gv->write_indent ();
945 : :
946 : 252 : pretty_printer *pp = gv->get_pp ();
947 : :
948 : 252 : m_src->dump_dot_id (pp);
949 : 252 : pp_string (pp, " -> ");
950 : 252 : m_dest->dump_dot_id (pp);
951 : 252 : pp_printf (pp,
952 : : (" [style=%s, color=%s, weight=%d, constraint=%s,"
953 : : " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
954 : : " headlabel=\""),
955 : : style, color, weight, constraint,
956 : 252 : m_src->m_index, m_dest->m_index);
957 : :
958 : 252 : dump_label_to_pp (pp, false);
959 : :
960 : 252 : pp_printf (pp, "\"];\n");
961 : 252 : }
962 : :
963 : : /* Return a new json::object of the form
964 : : {"kind" : str,
965 : : "src_idx": int, the index of the source supernode,
966 : : "dst_idx": int, the index of the destination supernode,
967 : : "desc" : str. */
968 : :
969 : : std::unique_ptr<json::object>
970 : 26 : superedge::to_json () const
971 : : {
972 : 26 : auto sedge_obj = std::make_unique<json::object> ();
973 : 26 : sedge_obj->set_string ("kind", edge_kind_to_string (m_kind));
974 : 26 : sedge_obj->set_integer ("src_idx", m_src->m_index);
975 : 26 : sedge_obj->set_integer ("dst_idx", m_dest->m_index);
976 : :
977 : 26 : {
978 : 26 : pretty_printer pp;
979 : 26 : pp_format_decoder (&pp) = default_tree_printer;
980 : 26 : dump_label_to_pp (&pp, false);
981 : 26 : sedge_obj->set_string ("desc", pp_formatted_text (&pp));
982 : 26 : }
983 : :
984 : 26 : return sedge_obj;
985 : : }
986 : :
987 : : /* If this is an intraprocedural superedge, return the associated
988 : : CFG edge. Otherwise, return nullptr. */
989 : :
990 : : ::edge
991 : 8144 : superedge::get_any_cfg_edge () const
992 : : {
993 : 8144 : if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
994 : 7775 : return sub->get_cfg_edge ();
995 : : return nullptr;
996 : : }
997 : :
998 : : /* If this is an interprocedural superedge, return the associated
999 : : cgraph_edge *. Otherwise, return nullptr. */
1000 : :
1001 : : cgraph_edge *
1002 : 9058 : superedge::get_any_callgraph_edge () const
1003 : : {
1004 : 9058 : if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
1005 : 9058 : return sub->m_cedge;
1006 : : return nullptr;
1007 : : }
1008 : :
1009 : : /* Build a description of this superedge (e.g. "true" for the true
1010 : : edge of a conditional, or "case 42:" for a switch case).
1011 : :
1012 : : If USER_FACING is false, the result also contains any underlying
1013 : : CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1014 : :
1015 : : label_text
1016 : 15764 : superedge::get_description (bool user_facing) const
1017 : : {
1018 : 15764 : pretty_printer pp;
1019 : 15764 : pp_format_decoder (&pp) = default_tree_printer;
1020 : 15764 : dump_label_to_pp (&pp, user_facing);
1021 : 15764 : return label_text::take (xstrdup (pp_formatted_text (&pp)));
1022 : 15764 : }
1023 : :
1024 : : /* Implementation of superedge::dump_label_to_pp for non-switch CFG
1025 : : superedges.
1026 : :
1027 : : For true/false edges, print "true" or "false" to PP.
1028 : :
1029 : : If USER_FACING is false, also print flags on the underlying CFG edge to
1030 : : PP. */
1031 : :
1032 : : void
1033 : 15766 : cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1034 : : bool user_facing) const
1035 : : {
1036 : 15766 : if (true_value_p ())
1037 : 3894 : pp_printf (pp, "true");
1038 : 11872 : else if (false_value_p ())
1039 : 3423 : pp_printf (pp, "false");
1040 : :
1041 : 15766 : if (user_facing)
1042 : : return;
1043 : :
1044 : : /* Express edge flags as a string with " | " separator.
1045 : : e.g. " (flags FALLTHRU | DFS_BACK)". */
1046 : 463 : if (get_flags ())
1047 : : {
1048 : 402 : pp_string (pp, " (flags ");
1049 : 402 : bool seen_flag = false;
1050 : : #define DEF_EDGE_FLAG(NAME,IDX) \
1051 : : do { \
1052 : : if (get_flags () & EDGE_##NAME) \
1053 : : { \
1054 : : if (seen_flag) \
1055 : : pp_string (pp, " | "); \
1056 : : pp_printf (pp, "%s", (#NAME)); \
1057 : : seen_flag = true; \
1058 : : } \
1059 : : } while (0);
1060 : : #include "cfg-flags.def"
1061 : : #undef DEF_EDGE_FLAG
1062 : 402 : pp_string (pp, ")");
1063 : : }
1064 : :
1065 : 463 : if (m_cfg_edge->goto_locus > BUILTINS_LOCATION)
1066 : 180 : pp_string (pp, " (has goto_locus)");
1067 : :
1068 : : /* Otherwise, no label. */
1069 : : }
1070 : :
1071 : : /* Get the index number for this edge for use in phi stmts
1072 : : in its destination. */
1073 : :
1074 : : size_t
1075 : 86183 : cfg_superedge::get_phi_arg_idx () const
1076 : : {
1077 : 86183 : return m_cfg_edge->dest_idx;
1078 : : }
1079 : :
1080 : : /* Get the phi argument for PHI for this CFG edge. */
1081 : :
1082 : : tree
1083 : 75138 : cfg_superedge::get_phi_arg (const gphi *phi) const
1084 : : {
1085 : 75138 : size_t index = get_phi_arg_idx ();
1086 : 75138 : return gimple_phi_arg_def (phi, index);
1087 : : }
1088 : :
1089 : : /* class switch_cfg_superedge : public cfg_superedge. */
1090 : :
1091 : 3031 : switch_cfg_superedge::switch_cfg_superedge (supernode *src,
1092 : : supernode *dst,
1093 : 3031 : ::edge e)
1094 : 3031 : : cfg_superedge (src, dst, e)
1095 : : {
1096 : : /* Populate m_case_labels with all cases which go to DST. */
1097 : 3031 : const gswitch *gswitch = get_switch_stmt ();
1098 : 542778 : for (unsigned i = 0; i < gimple_switch_num_labels (gswitch); i++)
1099 : : {
1100 : 539747 : tree case_ = gimple_switch_label (gswitch, i);
1101 : 539747 : basic_block bb = label_to_block (src->get_function (),
1102 : 539747 : CASE_LABEL (case_));
1103 : 539747 : if (bb == dst->m_bb)
1104 : 3599 : m_case_labels.safe_push (case_);
1105 : : }
1106 : 3031 : }
1107 : :
1108 : : /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1109 : : "switch" statements.
1110 : :
1111 : : Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP. */
1112 : :
1113 : : void
1114 : 411 : switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1115 : : bool user_facing ATTRIBUTE_UNUSED) const
1116 : : {
1117 : 411 : if (user_facing)
1118 : : {
1119 : 828 : for (unsigned i = 0; i < m_case_labels.length (); ++i)
1120 : : {
1121 : 417 : if (i > 0)
1122 : 6 : pp_string (pp, ", ");
1123 : 417 : tree case_label = m_case_labels[i];
1124 : 417 : gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
1125 : 417 : tree lower_bound = CASE_LOW (case_label);
1126 : 417 : tree upper_bound = CASE_HIGH (case_label);
1127 : 417 : if (lower_bound)
1128 : : {
1129 : 162 : pp_printf (pp, "case ");
1130 : 162 : dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1131 : 162 : if (upper_bound)
1132 : : {
1133 : 12 : pp_printf (pp, " ... ");
1134 : 12 : dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1135 : : false);
1136 : : }
1137 : 162 : pp_printf (pp, ":");
1138 : : }
1139 : : else
1140 : 255 : pp_printf (pp, "default:");
1141 : : }
1142 : : }
1143 : : else
1144 : : {
1145 : 0 : pp_character (pp, '{');
1146 : 0 : for (unsigned i = 0; i < m_case_labels.length (); ++i)
1147 : : {
1148 : 0 : if (i > 0)
1149 : 0 : pp_string (pp, ", ");
1150 : 0 : tree case_label = m_case_labels[i];
1151 : 0 : gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
1152 : 0 : tree lower_bound = CASE_LOW (case_label);
1153 : 0 : tree upper_bound = CASE_HIGH (case_label);
1154 : 0 : if (lower_bound)
1155 : : {
1156 : 0 : if (upper_bound)
1157 : : {
1158 : 0 : pp_character (pp, '[');
1159 : 0 : dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0,
1160 : : false);
1161 : 0 : pp_string (pp, ", ");
1162 : 0 : dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0,
1163 : : false);
1164 : 0 : pp_character (pp, ']');
1165 : : }
1166 : : else
1167 : 0 : dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
1168 : : }
1169 : : else
1170 : 0 : pp_printf (pp, "default");
1171 : : }
1172 : 0 : pp_character (pp, '}');
1173 : 0 : if (implicitly_created_default_p ())
1174 : : {
1175 : 0 : pp_string (pp, " IMPLICITLY CREATED");
1176 : : }
1177 : : }
1178 : 411 : }
1179 : :
1180 : : /* Return true iff this edge is purely for an implicitly-created "default". */
1181 : :
1182 : : bool
1183 : 614 : switch_cfg_superedge::implicitly_created_default_p () const
1184 : : {
1185 : 614 : if (m_case_labels.length () != 1)
1186 : : return false;
1187 : :
1188 : 554 : tree case_label = m_case_labels[0];
1189 : 554 : gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
1190 : 554 : if (CASE_LOW (case_label))
1191 : : return false;
1192 : :
1193 : : /* We have a single "default" case.
1194 : : Assume that it was implicitly created if it has UNKNOWN_LOCATION. */
1195 : 163 : return EXPR_LOCATION (case_label) == UNKNOWN_LOCATION;
1196 : : }
1197 : :
1198 : : /* class eh_dispatch_cfg_superedge : public cfg_superedge. */
1199 : :
1200 : : /* Given an ERT_TRY region, get the eh_catch corresponding to
1201 : : the label of DST_SNODE, if any. */
1202 : :
1203 : : static eh_catch
1204 : 180 : get_catch (eh_region eh_reg, supernode *dst_snode)
1205 : : {
1206 : 180 : gcc_assert (eh_reg->type == ERT_TRY);
1207 : :
1208 : 180 : tree dst_snode_label = dst_snode->get_label ();
1209 : 180 : if (!dst_snode_label)
1210 : : return nullptr;
1211 : :
1212 : 123 : for (eh_catch iter = eh_reg->u.eh_try.first_catch;
1213 : 183 : iter;
1214 : 60 : iter = iter->next_catch)
1215 : 183 : if (iter->label == dst_snode_label)
1216 : : return iter;
1217 : :
1218 : : return nullptr;
1219 : : }
1220 : :
1221 : : std::unique_ptr<eh_dispatch_cfg_superedge>
1222 : 192 : eh_dispatch_cfg_superedge::make (supernode *src_snode,
1223 : : supernode *dst_snode,
1224 : : ::edge e,
1225 : : const geh_dispatch *eh_dispatch_stmt)
1226 : : {
1227 : 192 : const eh_status *eh = src_snode->get_function ()->eh;
1228 : 192 : gcc_assert (eh);
1229 : 192 : int region_idx = gimple_eh_dispatch_region (eh_dispatch_stmt);
1230 : 192 : gcc_assert (region_idx > 0);
1231 : 192 : gcc_assert ((*eh->region_array)[region_idx]);
1232 : 192 : eh_region eh_reg = (*eh->region_array)[region_idx];
1233 : 192 : gcc_assert (eh_reg);
1234 : 192 : switch (eh_reg->type)
1235 : : {
1236 : 0 : default:
1237 : 0 : gcc_unreachable ();
1238 : 0 : case ERT_CLEANUP:
1239 : : // TODO
1240 : 0 : gcc_unreachable ();
1241 : 180 : break;
1242 : 180 : case ERT_TRY:
1243 : 180 : {
1244 : 180 : eh_catch ehc = get_catch (eh_reg, dst_snode);
1245 : 180 : return std::make_unique<eh_dispatch_try_cfg_superedge>
1246 : 180 : (src_snode, dst_snode,
1247 : : e, eh_dispatch_stmt,
1248 : 180 : eh_reg, ehc);
1249 : : }
1250 : 12 : break;
1251 : 12 : case ERT_ALLOWED_EXCEPTIONS:
1252 : 12 : return std::make_unique<eh_dispatch_allowed_cfg_superedge>
1253 : 12 : (src_snode, dst_snode,
1254 : : e, eh_dispatch_stmt,
1255 : 12 : eh_reg);
1256 : 0 : break;
1257 : 0 : case ERT_MUST_NOT_THROW:
1258 : : // TODO
1259 : 0 : gcc_unreachable ();
1260 : : break;
1261 : : }
1262 : : }
1263 : :
1264 : 192 : eh_dispatch_cfg_superedge::
1265 : : eh_dispatch_cfg_superedge (supernode *src,
1266 : : supernode *dst,
1267 : : ::edge e,
1268 : : const geh_dispatch *eh_dispatch_stmt,
1269 : 192 : eh_region eh_reg)
1270 : : : cfg_superedge (src, dst, e),
1271 : 192 : m_eh_dispatch_stmt (eh_dispatch_stmt),
1272 : 192 : m_eh_region (eh_reg)
1273 : : {
1274 : 192 : gcc_assert (m_eh_region);
1275 : 192 : }
1276 : :
1277 : : const eh_status &
1278 : 0 : eh_dispatch_cfg_superedge::get_eh_status () const
1279 : : {
1280 : 0 : const eh_status *eh = m_src->get_function ()->eh;
1281 : 0 : gcc_assert (eh);
1282 : 0 : return *eh;
1283 : : }
1284 : :
1285 : : // class eh_dispatch_try_cfg_superedge : public eh_dispatch_cfg_superedge
1286 : :
1287 : : /* Implementation of superedge::dump_label_to_pp for CFG superedges for
1288 : : "eh_dispatch" statements for ERT_TRY regions. */
1289 : :
1290 : : void
1291 : 0 : eh_dispatch_try_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1292 : : bool user_facing) const
1293 : : {
1294 : 0 : if (!user_facing)
1295 : 0 : pp_string (pp, "ERT_TRY: ");
1296 : 0 : if (m_eh_catch)
1297 : : {
1298 : 0 : bool first = true;
1299 : 0 : for (tree iter = m_eh_catch->type_list; iter; iter = TREE_CHAIN (iter))
1300 : : {
1301 : 0 : if (!first)
1302 : 0 : pp_string (pp, ", ");
1303 : 0 : pp_printf (pp, "on catch %qT", TREE_VALUE (iter));
1304 : 0 : first = false;
1305 : : }
1306 : : }
1307 : : else
1308 : 0 : pp_string (pp, "on uncaught exception");
1309 : 0 : }
1310 : :
1311 : : bool
1312 : 240 : eh_dispatch_try_cfg_superedge::
1313 : : apply_constraints (region_model *model,
1314 : : region_model_context *ctxt,
1315 : : tree exception_type,
1316 : : std::unique_ptr<rejected_constraint> *out) const
1317 : : {
1318 : 240 : return model->apply_constraints_for_eh_dispatch_try
1319 : 240 : (*this, ctxt, exception_type, out);
1320 : : }
1321 : :
1322 : : // class eh_dispatch_allowed_cfg_superedge : public eh_dispatch_cfg_superedge
1323 : :
1324 : 12 : eh_dispatch_allowed_cfg_superedge::
1325 : : eh_dispatch_allowed_cfg_superedge (supernode *src, supernode *dst, ::edge e,
1326 : : const geh_dispatch *eh_dispatch_stmt,
1327 : 12 : eh_region eh_reg)
1328 : 12 : : eh_dispatch_cfg_superedge (src, dst, e, eh_dispatch_stmt, eh_reg)
1329 : : {
1330 : 12 : gcc_assert (eh_reg->type == ERT_ALLOWED_EXCEPTIONS);
1331 : :
1332 : : /* We expect two sibling out-edges at an eh_dispatch from such a region:
1333 : :
1334 : : - one to a bb without a gimple label, with a resx,
1335 : : for exceptions of expected types
1336 : :
1337 : : - one to a bb with a gimple label, with a call to __cxa_unexpected,
1338 : : for exceptions of unexpected types.
1339 : :
1340 : : Set m_kind for this edge accordingly. */
1341 : 12 : gcc_assert (e->src->succs->length () == 2);
1342 : 12 : tree label_for_unexpected_exceptions = eh_reg->u.allowed.label;
1343 : 12 : tree label_for_dest_enode = dst->get_label ();
1344 : 12 : if (label_for_dest_enode == label_for_unexpected_exceptions)
1345 : 6 : m_kind = eh_kind::unexpected;
1346 : : else
1347 : : {
1348 : 6 : gcc_assert (label_for_dest_enode == nullptr);
1349 : 6 : m_kind = eh_kind::expected;
1350 : : }
1351 : 12 : }
1352 : :
1353 : : void
1354 : 3 : eh_dispatch_allowed_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
1355 : : bool user_facing) const
1356 : : {
1357 : 3 : if (!user_facing)
1358 : : {
1359 : 0 : switch (m_kind)
1360 : : {
1361 : 0 : default:
1362 : 0 : gcc_unreachable ();
1363 : 0 : case eh_dispatch_allowed_cfg_superedge::eh_kind::expected:
1364 : 0 : pp_string (pp, "expected: ");
1365 : 0 : break;
1366 : 0 : case eh_dispatch_allowed_cfg_superedge::eh_kind::unexpected:
1367 : 0 : pp_string (pp, "unexpected: ");
1368 : 0 : break;
1369 : : }
1370 : 0 : pp_string (pp, "ERT_ALLOWED_EXCEPTIONS: ");
1371 : 0 : eh_region eh_reg = get_eh_region ();
1372 : 0 : bool first = true;
1373 : 0 : for (tree iter = eh_reg->u.allowed.type_list; iter;
1374 : 0 : iter = TREE_CHAIN (iter))
1375 : : {
1376 : 0 : if (!first)
1377 : 0 : pp_string (pp, ", ");
1378 : 0 : pp_printf (pp, "%qT", TREE_VALUE (iter));
1379 : 0 : first = false;
1380 : : }
1381 : : }
1382 : 3 : }
1383 : :
1384 : : bool
1385 : 13 : eh_dispatch_allowed_cfg_superedge::
1386 : : apply_constraints (region_model *model,
1387 : : region_model_context *ctxt,
1388 : : tree exception_type,
1389 : : std::unique_ptr<rejected_constraint> *out) const
1390 : : {
1391 : 13 : return model->apply_constraints_for_eh_dispatch_allowed
1392 : 13 : (*this, ctxt, exception_type, out);
1393 : : }
1394 : :
1395 : : /* Implementation of superedge::dump_label_to_pp for interprocedural
1396 : : superedges. */
1397 : :
1398 : : void
1399 : 58 : callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
1400 : : bool user_facing ATTRIBUTE_UNUSED) const
1401 : : {
1402 : 58 : switch (m_kind)
1403 : : {
1404 : 0 : default:
1405 : 0 : case SUPEREDGE_CFG_EDGE:
1406 : 0 : gcc_unreachable ();
1407 : :
1408 : 23 : case SUPEREDGE_CALL:
1409 : 23 : pp_printf (pp, "call");
1410 : 23 : break;
1411 : :
1412 : 23 : case SUPEREDGE_RETURN:
1413 : 23 : pp_printf (pp, "return");
1414 : 23 : break;
1415 : :
1416 : 12 : case SUPEREDGE_INTRAPROCEDURAL_CALL:
1417 : 12 : pp_printf (pp, "intraproc link");
1418 : 12 : break;
1419 : : }
1420 : 58 : }
1421 : :
1422 : : /* Get the function that was called at this interprocedural call/return
1423 : : edge. */
1424 : :
1425 : : function *
1426 : 11183 : callgraph_superedge::get_callee_function () const
1427 : : {
1428 : 11183 : return get_ultimate_function_for_cgraph_edge (m_cedge);
1429 : : }
1430 : :
1431 : : /* Get the calling function at this interprocedural call/return edge. */
1432 : :
1433 : : function *
1434 : 0 : callgraph_superedge::get_caller_function () const
1435 : : {
1436 : 0 : return m_cedge->caller->get_fun ();
1437 : : }
1438 : :
1439 : : /* Get the fndecl that was called at this interprocedural call/return
1440 : : edge. */
1441 : :
1442 : : tree
1443 : 990 : callgraph_superedge::get_callee_decl () const
1444 : : {
1445 : 990 : return get_callee_function ()->decl;
1446 : : }
1447 : :
1448 : : /* Get the gcall * of this interprocedural call/return edge. */
1449 : :
1450 : : const gcall &
1451 : 19668 : callgraph_superedge::get_call_stmt () const
1452 : : {
1453 : 19668 : if (m_cedge)
1454 : 19668 : return *m_cedge->call_stmt;
1455 : :
1456 : 0 : return *m_src->get_final_call ();
1457 : : }
1458 : :
1459 : : /* Get the calling fndecl at this interprocedural call/return edge. */
1460 : :
1461 : : tree
1462 : 0 : callgraph_superedge::get_caller_decl () const
1463 : : {
1464 : 0 : return get_caller_function ()->decl;
1465 : : }
1466 : :
1467 : : /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1468 : : to *OUT if OUT is non-NULL), and return the corresponding argument
1469 : : at the callsite. */
1470 : :
1471 : : tree
1472 : 233 : callgraph_superedge::get_arg_for_parm (tree parm_to_find,
1473 : : callsite_expr *out) const
1474 : : {
1475 : 233 : gcc_assert (TREE_CODE (parm_to_find) == PARM_DECL);
1476 : :
1477 : 233 : tree callee = get_callee_decl ();
1478 : 233 : const gcall &call_stmt = get_call_stmt ();
1479 : :
1480 : 233 : unsigned i = 0;
1481 : 255 : for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1482 : 22 : iter_parm = DECL_CHAIN (iter_parm), ++i)
1483 : : {
1484 : 222 : if (i >= gimple_call_num_args (&call_stmt))
1485 : : return NULL_TREE;
1486 : 222 : if (iter_parm == parm_to_find)
1487 : : {
1488 : 200 : if (out)
1489 : 200 : *out = callsite_expr::from_zero_based_param (i);
1490 : 200 : return gimple_call_arg (&call_stmt, i);
1491 : : }
1492 : : }
1493 : :
1494 : : /* Not found. */
1495 : : return NULL_TREE;
1496 : : }
1497 : :
1498 : : /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1499 : : If found, return the default SSA def of the corresponding parm within
1500 : : the callee, and if OUT is non-NULL, write the index to *OUT.
1501 : : Only the first match is handled. */
1502 : :
1503 : : tree
1504 : 475 : callgraph_superedge::get_parm_for_arg (tree arg_to_find,
1505 : : callsite_expr *out) const
1506 : : {
1507 : 475 : tree callee = get_callee_decl ();
1508 : 475 : const gcall &call_stmt = get_call_stmt ();
1509 : :
1510 : 475 : unsigned i = 0;
1511 : 826 : for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1512 : 351 : iter_parm = DECL_CHAIN (iter_parm), ++i)
1513 : : {
1514 : 435 : if (i >= gimple_call_num_args (&call_stmt))
1515 : : return NULL_TREE;
1516 : 434 : tree param = gimple_call_arg (&call_stmt, i);
1517 : 434 : if (arg_to_find == param)
1518 : : {
1519 : 83 : if (out)
1520 : 83 : *out = callsite_expr::from_zero_based_param (i);
1521 : 83 : return ssa_default_def (get_callee_function (), iter_parm);
1522 : : }
1523 : : }
1524 : :
1525 : : /* Not found. */
1526 : : return NULL_TREE;
1527 : : }
1528 : :
1529 : : /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1530 : : If non-NULL is returned, populate OUT. */
1531 : :
1532 : : tree
1533 : 475 : callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
1534 : : callsite_expr *out) const
1535 : : {
1536 : : /* Is it an argument (actual param)? If so, convert to
1537 : : parameter (formal param). */
1538 : 475 : tree parm = get_parm_for_arg (caller_expr, out);
1539 : 475 : if (parm)
1540 : : return parm;
1541 : : /* Otherwise try return value. */
1542 : 396 : if (caller_expr == gimple_call_lhs (&get_call_stmt ()))
1543 : : {
1544 : 69 : if (out)
1545 : 69 : *out = callsite_expr::from_return_value ();
1546 : 69 : return DECL_RESULT (get_callee_decl ());
1547 : : }
1548 : :
1549 : : return NULL_TREE;
1550 : : }
1551 : :
1552 : : /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1553 : : If non-NULL is returned, populate OUT. */
1554 : :
1555 : : tree
1556 : 1208 : callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
1557 : : callsite_expr *out) const
1558 : : {
1559 : 1208 : if (callee_expr == NULL_TREE)
1560 : : return NULL_TREE;
1561 : :
1562 : : /* If it's a parameter (formal param), get the argument (actual param). */
1563 : 446 : if (TREE_CODE (callee_expr) == PARM_DECL)
1564 : 10 : return get_arg_for_parm (callee_expr, out);
1565 : :
1566 : : /* Similar for the default SSA name of the PARM_DECL. */
1567 : 436 : if (TREE_CODE (callee_expr) == SSA_NAME
1568 : 348 : && SSA_NAME_IS_DEFAULT_DEF (callee_expr)
1569 : 659 : && TREE_CODE (SSA_NAME_VAR (callee_expr)) == PARM_DECL)
1570 : 223 : return get_arg_for_parm (SSA_NAME_VAR (callee_expr), out);
1571 : :
1572 : : /* Otherwise try return value. */
1573 : 213 : if (callee_expr == DECL_RESULT (get_callee_decl ()))
1574 : : {
1575 : 0 : if (out)
1576 : 0 : *out = callsite_expr::from_return_value ();
1577 : 0 : return gimple_call_lhs (&get_call_stmt ());
1578 : : }
1579 : :
1580 : : return NULL_TREE;
1581 : : }
1582 : :
1583 : : } // namespace ana
1584 : :
1585 : : #endif /* #if ENABLE_ANALYZER */
|