Branch data Line data Source code
1 : : /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
2 : : Copyright (C) 2019-2026 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 : : #define INCLUDE_DEQUE
22 : : #include "analyzer/common.h"
23 : :
24 : : #include "timevar.h"
25 : : #include "gimple-pretty-print.h"
26 : : #include "ordered-hash-map.h"
27 : : #include "options.h"
28 : : #include "cgraph.h"
29 : : #include "cfg.h"
30 : : #include "digraph.h"
31 : : #include "tree-cfg.h"
32 : : #include "cfganal.h"
33 : : #include "except.h"
34 : :
35 : : #include "diagnostics/file-cache.h"
36 : :
37 : : #include "analyzer/supergraph.h"
38 : : #include "analyzer/analyzer-logging.h"
39 : : #include "analyzer/region-model.h"
40 : : #include "analyzer/exploded-graph.h"
41 : :
42 : : #if ENABLE_ANALYZER
43 : :
44 : : namespace ana {
45 : :
46 : : /* Get the function of the ultimate alias target being called at EDGE,
47 : : if any. */
48 : :
49 : : function *
50 : 0 : get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
51 : : {
52 : 0 : cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
53 : 0 : if (!ultimate_node)
54 : : return nullptr;
55 : 0 : return ultimate_node->get_fun ();
56 : : }
57 : :
58 : : /* class saved_uids.
59 : :
60 : : In order to ensure consistent results without relying on the ordering
61 : : of pointer values we assign a uid to each gimple stmt, globally unique
62 : : across all functions.
63 : :
64 : : Normally, the stmt uids are a scratch space that each pass can freely
65 : : assign its own values to. However, in the case of LTO, the uids are
66 : : used to associate call stmts with callgraph edges between the WPA phase
67 : : (where the analyzer runs in LTO mode) and the LTRANS phase; if the
68 : : analyzer changes them in the WPA phase, it leads to errors when
69 : : streaming the code back in at LTRANS.
70 : : lto_prepare_function_for_streaming has code to renumber the stmt UIDs
71 : : when the code is streamed back out, but for some reason this isn't
72 : : called for clones.
73 : :
74 : : Hence, as a workaround, this class has responsibility for tracking
75 : : the original uids and restoring them once the pass is complete
76 : : (in the supergraph dtor). */
77 : :
78 : : /* Give STMT a globally unique uid, storing its original uid so it can
79 : : later be restored. */
80 : :
81 : : void
82 : 126940 : saved_uids::make_uid_unique (gimple *stmt)
83 : : {
84 : 126940 : unsigned next_uid = m_old_stmt_uids.length ();
85 : 126940 : unsigned old_stmt_uid = stmt->uid;
86 : 126940 : stmt->uid = next_uid;
87 : 126940 : m_old_stmt_uids.safe_push
88 : 126940 : (std::pair<gimple *, unsigned> (stmt, old_stmt_uid));
89 : 126940 : }
90 : :
91 : : /* Restore the saved uids of all stmts. */
92 : :
93 : : void
94 : 3297 : saved_uids::restore_uids () const
95 : : {
96 : 3297 : unsigned i;
97 : 3297 : std::pair<gimple *, unsigned> *pair;
98 : 130237 : FOR_EACH_VEC_ELT (m_old_stmt_uids, i, pair)
99 : 126940 : pair->first->uid = pair->second;
100 : 3297 : }
101 : :
102 : : /* When building the supergraph, should STMT be handled
103 : : along each out-edge in the CFG, or as separate superedge
104 : : "within" the BB. */
105 : :
106 : : static bool
107 : 121766 : control_flow_stmt_p (const gimple &stmt)
108 : : {
109 : 121766 : switch (gimple_code (&stmt))
110 : : {
111 : : case GIMPLE_COND:
112 : : case GIMPLE_EH_DISPATCH:
113 : : case GIMPLE_GOTO:
114 : : case GIMPLE_SWITCH:
115 : : return true;
116 : :
117 : 113862 : case GIMPLE_ASM:
118 : 113862 : case GIMPLE_ASSIGN:
119 : 113862 : case GIMPLE_CALL:
120 : 113862 : case GIMPLE_DEBUG:
121 : 113862 : case GIMPLE_LABEL:
122 : 113862 : case GIMPLE_NOP:
123 : 113862 : case GIMPLE_PREDICT:
124 : 113862 : case GIMPLE_RESX:
125 : 113862 : case GIMPLE_RETURN:
126 : 113862 : return false;
127 : :
128 : : /* We don't expect to see any other statement kinds in the analyzer. */
129 : 0 : default:
130 : 0 : internal_error ("unexpected gimple stmt code: %qs",
131 : 0 : gimple_code_name[gimple_code (&stmt)]);
132 : : break;
133 : : }
134 : : }
135 : :
136 : : /* supergraph's ctor. Walk the callgraph, building supernodes for each
137 : : CFG basic block, splitting the basic blocks at statements. Join
138 : : together the supernodes with interprocedural superedges as appropriate.
139 : : Assign UIDs to the gimple stmts. */
140 : :
141 : 3297 : supergraph::supergraph (region_model_manager &mgr,
142 : 3297 : logger *logger)
143 : 3297 : : m_next_snode_id (0)
144 : : {
145 : 3297 : auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
146 : :
147 : 3297 : LOG_FUNC (logger);
148 : :
149 : : /* For each BB, if present, the stmt that terminates it. */
150 : 3297 : typedef ordered_hash_map<basic_block, gimple *> bb_to_stmt_t;
151 : 3297 : bb_to_stmt_t control_stmt_ending_bbs;
152 : :
153 : : /* First pass: make supernodes (and assign UIDs to the gimple stmts). */
154 : 3297 : {
155 : : /* Sort the cgraph_nodes? */
156 : 3297 : cgraph_node *node;
157 : 13414 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
158 : : {
159 : 10117 : function *fun = node->get_fun ();
160 : :
161 : 10117 : log_nesting_level log_sentinel (logger, "function: %qD", fun->decl);
162 : :
163 : : /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
164 : : the supergraph (by doing it per-function). */
165 : 10117 : auto_cfun cfun_sentinel (fun);
166 : 10117 : mark_dfs_back_edges ();
167 : :
168 : 10117 : const int start_id = m_nodes.length ();
169 : :
170 : 10117 : basic_block bb;
171 : 65999 : FOR_ALL_BB_FN (bb, fun)
172 : 111764 : if (gimple *final_control_stmt
173 : 55882 : = populate_for_basic_block (bb, fun, logger))
174 : 7904 : control_stmt_ending_bbs.put (bb, final_control_stmt);
175 : :
176 : 10117 : const unsigned num_snodes = m_nodes.length () - start_id;
177 : 10117 : m_function_to_num_snodes.put (fun, num_snodes);
178 : :
179 : 10117 : if (logger)
180 : : {
181 : 2 : const int end_id = m_nodes.length () - 1;
182 : 2 : logger->log ("SN: %i...%i: function %qD",
183 : : start_id, end_id, fun->decl);
184 : : }
185 : 10119 : }
186 : : }
187 : :
188 : : /* Second pass: make superedges between basic blocks. */
189 : 3297 : {
190 : : /* Make superedges for CFG edges. */
191 : 3297 : for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
192 : 177533 : iter != m_bb_to_final_node.end ();
193 : 55882 : ++iter)
194 : : {
195 : 55882 : basic_block bb = (*iter).first;
196 : 55882 : supernode *src_supernode = (*iter).second;
197 : :
198 : 55882 : gimple *control_stmt_ending_bb = nullptr;
199 : 55882 : if (auto control_stmt_iter = control_stmt_ending_bbs.get (bb))
200 : 7904 : control_stmt_ending_bb = *control_stmt_iter;
201 : :
202 : 55882 : ::edge cfg_edge;
203 : 55882 : int idx;
204 : 55882 : if (bb->succs)
205 : 111589 : FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
206 : : {
207 : 55707 : basic_block dest_cfg_block = cfg_edge->dest;
208 : 55707 : supernode *dest_supernode
209 : 55707 : = *m_bb_to_initial_node.get (dest_cfg_block);
210 : 55707 : add_sedges_for_cfg_edge (src_supernode,
211 : : dest_supernode,
212 : : cfg_edge,
213 : : control_stmt_ending_bb,
214 : : mgr,
215 : : logger);
216 : : }
217 : : }
218 : : }
219 : 3297 : }
220 : :
221 : : /* Create a run of supernodes and superedges for the BB within FUN
222 : : expressing all of the stmts apart from the final control flow stmt (if any).
223 : : Return the control stmt that ends this bb, if any. */
224 : :
225 : : gimple *
226 : 55882 : supergraph::populate_for_basic_block (basic_block bb,
227 : : function *fun,
228 : : logger *logger)
229 : : {
230 : 55882 : log_nesting_level sentinel (logger, "bb %i", bb->index);
231 : :
232 : 55882 : supernode *initial_snode_in_bb = add_node (fun, bb, logger);
233 : 55882 : m_bb_to_initial_node.put (bb, initial_snode_in_bb);
234 : :
235 : 55882 : if (bb->index == ENTRY_BLOCK)
236 : : /* Use the decl's location, rather than fun->function_start_locus,
237 : : which leads to more readable output. */
238 : 10117 : initial_snode_in_bb->m_loc = DECL_SOURCE_LOCATION (fun->decl);
239 : 45765 : else if (bb->index == EXIT_BLOCK)
240 : 10117 : initial_snode_in_bb->m_loc = fun->function_end_locus;
241 : 71296 : else if (gsi_end_p (gsi_start_bb (bb)))
242 : : {
243 : : /* BB has no stmts, and isn't the ENTRY or EXIT node.
244 : : Try to find a source location for it. */
245 : 727 : if (bb->succs->length () == 1)
246 : : {
247 : 727 : auto outedge = (*bb->succs)[0];
248 : 727 : if (useful_location_p (outedge->goto_locus))
249 : : {
250 : : /* We have an empty basic block with one out-edge,
251 : : perhaps part of an empty infinite loop. */
252 : 478 : if (logger)
253 : 0 : logger->log ("using location 0x%lx from outedge",
254 : : outedge->goto_locus);
255 : 478 : initial_snode_in_bb->m_loc = outedge->goto_locus;
256 : : }
257 : : }
258 : : }
259 : :
260 : 55882 : initial_snode_in_bb->m_state_merger_node = true;
261 : :
262 : 55882 : gimple *final_control_flow_stmt = nullptr;
263 : :
264 : : /* Create a run of supernodes for the stmts in BB,
265 : : connected by stmt_superedge. */
266 : 55882 : gimple_stmt_iterator gsi;
267 : 55882 : supernode *prev_snode_in_bb = initial_snode_in_bb;
268 : 230800 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
269 : : {
270 : 126940 : gimple *next_stmt = gsi_stmt (gsi);
271 : :
272 : 126940 : if (logger)
273 : : {
274 : 20 : logger->start_log_line ();
275 : 20 : logger->log_partial ("next_stmt: ");
276 : 20 : pp_gimple_stmt_1 (logger->get_printer (), next_stmt,
277 : : 0, (dump_flags_t)0);
278 : 20 : logger->end_log_line ();
279 : : }
280 : 126940 : prev_snode_in_bb->m_loc = get_stmt_location (next_stmt, fun);
281 : 126940 : prev_snode_in_bb->m_stmt_loc = next_stmt->location;
282 : 126940 : m_node_for_stmt.insert ({next_stmt, prev_snode_in_bb});
283 : :
284 : 126940 : m_stmt_uids.make_uid_unique (next_stmt);
285 : :
286 : 126940 : if (auto glabel_ = dyn_cast<const glabel *>(next_stmt))
287 : : {
288 : : /* Associate the GIMPLE_LABEL with its snode. */
289 : 8238 : prev_snode_in_bb->m_label = gimple_label_label (glabel_);
290 : :
291 : : /* Only create an snode for the label if it has location
292 : : information. */
293 : 8238 : if (glabel_->location == UNKNOWN_LOCATION)
294 : 5174 : continue;
295 : : }
296 : :
297 : : // handle control flow stmts on the edges
298 : 121766 : if (control_flow_stmt_p (*next_stmt))
299 : : {
300 : : final_control_flow_stmt = next_stmt;
301 : 55882 : break;
302 : : }
303 : :
304 : 113862 : supernode *snode_after_next_stmt = add_node (fun, bb, logger);
305 : 113862 : if (prev_snode_in_bb)
306 : : {
307 : 113862 : std::unique_ptr<operation> op;
308 : 113862 : switch (gimple_code (next_stmt))
309 : : {
310 : 0 : default:
311 : 0 : gcc_unreachable ();
312 : 210 : break;
313 : 210 : case GIMPLE_ASM:
314 : 210 : op = std::make_unique<gasm_op>
315 : 210 : (*as_a <const gasm *> (next_stmt));
316 : 210 : break;
317 : 54762 : case GIMPLE_ASSIGN:
318 : 54762 : op = std::make_unique<gassign_op>
319 : 54762 : (*as_a <const gassign *> (next_stmt));
320 : 54762 : break;
321 : 41702 : case GIMPLE_CALL:
322 : 41702 : op = call_and_return_op::make
323 : 41702 : (*as_a <const gcall *> (next_stmt));
324 : 41702 : break;
325 : 1773 : case GIMPLE_PREDICT:
326 : 1773 : op = std::make_unique<predict_op> (*next_stmt);
327 : 1773 : break;
328 : 562 : case GIMPLE_RESX:
329 : 562 : op = std::make_unique<resx_op>
330 : 562 : (*as_a <const gresx *> (next_stmt));
331 : 562 : break;
332 : 9938 : case GIMPLE_RETURN:
333 : 9938 : op = std::make_unique<greturn_op>
334 : 9938 : (*as_a <const greturn *> (next_stmt));
335 : 9938 : break;
336 : :
337 : : case GIMPLE_DEBUG:
338 : : case GIMPLE_LABEL:
339 : : case GIMPLE_NOP:
340 : : /* Treat all of these as no-ops within analyzer; though
341 : : perhaps we care about their locations. */
342 : : break;
343 : : }
344 : :
345 : 113862 : superedge *sedge
346 : : = new superedge (prev_snode_in_bb,
347 : : snode_after_next_stmt,
348 : : std::move (op),
349 : 113862 : nullptr);
350 : 113862 : add_edge (sedge);
351 : 113862 : }
352 : 113862 : prev_snode_in_bb = snode_after_next_stmt;
353 : : }
354 : :
355 : 55882 : m_bb_to_final_node.put (bb, prev_snode_in_bb);
356 : :
357 : 55882 : return final_control_flow_stmt;
358 : 55882 : }
359 : :
360 : : /* supergraph's dtor. Reset stmt uids. */
361 : :
362 : 3297 : supergraph::~supergraph ()
363 : : {
364 : 3297 : m_stmt_uids.restore_uids ();
365 : 3297 : }
366 : :
367 : : /* Dump this graph in .dot format to PP, using DUMP_ARGS.
368 : : Cluster the supernodes by function, then by BB from original CFG. */
369 : :
370 : : void
371 : 24 : supergraph::dump_dot_to_pp (pretty_printer *pp,
372 : : const dump_args_t &dump_args) const
373 : : {
374 : 24 : graphviz_out gv (pp);
375 : :
376 : 24 : pp_string (pp, "digraph \"");
377 : 24 : pp_write_text_to_stream (pp);
378 : 24 : pp_string (pp, "supergraph");
379 : 24 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
380 : 24 : pp_string (pp, "\" {\n");
381 : 24 : gv.indent ();
382 : :
383 : 24 : gv.println ("overlap=false;");
384 : 24 : gv.println ("compound=true;");
385 : :
386 : : /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
387 : : https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
388 : : */
389 : :
390 : : /* Break out the supernodes into clusters by function. */
391 : 24 : {
392 : 24 : cgraph_node *node;
393 : 96 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
394 : : {
395 : 72 : function *fun = node->get_fun ();
396 : 72 : gcc_assert (fun);
397 : 72 : auto_cfun sentinel (fun);
398 : :
399 : 72 : const char *funcname = function_name (fun);
400 : 72 : gv.println ("subgraph \"cluster_%s\" {",
401 : : funcname);
402 : 72 : gv.indent ();
403 : 72 : pp_printf (pp,
404 : : ("style=\"dashed\";"
405 : : " color=\"black\";"
406 : : " label=\"%s\";\n"),
407 : : funcname);
408 : :
409 : 72 : if (loops_for_fn (fun))
410 : 72 : dump_dot_to_gv_for_loop (gv, dump_args, get_loop (fun, 0), fun);
411 : : else
412 : : {
413 : 0 : basic_block bb;
414 : 0 : FOR_ALL_BB_FN (bb, fun)
415 : 0 : dump_dot_to_gv_for_bb (gv, dump_args, bb, fun);
416 : : }
417 : :
418 : : /* Terminate per-function "subgraph" */
419 : 72 : gv.outdent ();
420 : 72 : gv.println ("}");
421 : : }
422 : : }
423 : :
424 : : /* Superedges. */
425 : : int i;
426 : : superedge *e;
427 : 1178 : FOR_EACH_VEC_ELT (m_edges, i, e)
428 : 1154 : e->dump_dot (&gv, dump_args);
429 : :
430 : 24 : if (dump_args.m_node_annotator)
431 : 8 : dump_args.m_node_annotator->add_extra_objects (&gv);
432 : :
433 : : /* Terminate "digraph" */
434 : 24 : gv.outdent ();
435 : 24 : gv.println ("}");
436 : 24 : }
437 : :
438 : : /* Recursively dump all the snodes within LOOP and the loops
439 : : within it. */
440 : :
441 : : void
442 : 120 : supergraph::dump_dot_to_gv_for_loop (graphviz_out &gv,
443 : : const dump_args_t &dump_args,
444 : : class loop *loop,
445 : : function *fun) const
446 : : {
447 : 120 : pretty_printer *pp = gv.get_pp ();
448 : :
449 : 120 : basic_block *body;
450 : 120 : unsigned int i;
451 : : // Adapted from graph.cc:draw_cfg_nodes_for_loop
452 : 120 : const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
453 : :
454 : 120 : if (loop->header != NULL
455 : 120 : && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
456 : 48 : pp_printf (pp,
457 : : "\tsubgraph cluster_%d_%d {\n"
458 : : "\tstyle=\"filled\";\n"
459 : : "\tcolor=\"darkgreen\";\n"
460 : : "\tfillcolor=\"%s\";\n"
461 : : "\tlabel=\"loop %d\";\n"
462 : : "\tlabeljust=l;\n"
463 : : "\tpenwidth=2;\n",
464 : : fun->funcdef_no, loop->num,
465 : 48 : fillcolors[(loop_depth (loop) - 1) % 3],
466 : : loop->num);
467 : :
468 : : // Recurse
469 : 168 : for (class loop *inner = loop->inner; inner; inner = inner->next)
470 : 48 : dump_dot_to_gv_for_loop (gv, dump_args, inner, fun);
471 : :
472 : 120 : if (loop->header == NULL)
473 : 0 : return;
474 : :
475 : 120 : if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
476 : 72 : body = get_loop_body (loop);
477 : : else
478 : 48 : body = get_loop_body_in_bfs_order (loop);
479 : :
480 : 654 : for (i = 0; i < loop->num_nodes; i++)
481 : : {
482 : 534 : basic_block bb = body[i];
483 : 534 : if (bb->loop_father == loop)
484 : 438 : dump_dot_to_gv_for_bb (gv, dump_args, bb, fun);
485 : : }
486 : :
487 : 120 : free (body);
488 : :
489 : 120 : if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
490 : 48 : pp_printf (pp, "\t}\n");
491 : : }
492 : :
493 : : /* Dump all the snodes from BB. */
494 : :
495 : : void
496 : 438 : supergraph::dump_dot_to_gv_for_bb (graphviz_out &gv,
497 : : const dump_args_t &dump_args,
498 : : basic_block bb,
499 : : function *fun) const
500 : : {
501 : 438 : pretty_printer *pp = gv.get_pp ();
502 : :
503 : 438 : if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
504 : : {
505 : 365 : const char *funcname = function_name (fun);
506 : 365 : gv.println ("subgraph \"cluster_%s_bb_%i\" {",
507 : : funcname, bb->index);
508 : 365 : gv.indent ();
509 : 365 : pp_printf (pp,
510 : : ("style=\"dashed\";"
511 : : " color=\"black\";"
512 : : " label=\"bb: %i\";\n"),
513 : : bb->index);
514 : : }
515 : :
516 : : // TODO: maybe keep an index per-function/per-bb to speed this up???
517 : : int i;
518 : : supernode *n;
519 : 21518 : FOR_EACH_VEC_ELT (m_nodes, i, n)
520 : 21080 : if (n->m_fun == fun && n->m_bb == bb)
521 : 1154 : n->dump_dot (&gv, dump_args);
522 : :
523 : 438 : if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
524 : : {
525 : : /* Terminate per-bb "subgraph" */
526 : 365 : gv.outdent ();
527 : 365 : gv.println ("}");
528 : : }
529 : 438 : }
530 : :
531 : :
532 : : /* Dump this graph in .dot format to FP, using DUMP_ARGS. */
533 : :
534 : : void
535 : 24 : supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
536 : : {
537 : 24 : std::unique_ptr<pretty_printer> pp (global_dc->clone_printer ());
538 : 24 : pp_show_color (pp.get ()) = 0;
539 : : /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
540 : : trying to prettify things by showing the underlying var. */
541 : 24 : pp_format_decoder (pp.get ()) = default_tree_printer;
542 : :
543 : 24 : pp->set_output_stream (fp);
544 : 24 : dump_dot_to_pp (pp.get (), dump_args);
545 : 24 : pp_flush (pp.get ());
546 : 24 : }
547 : :
548 : : /* Dump this graph in .dot format to PATH, using DUMP_ARGS. */
549 : :
550 : : void
551 : 24 : supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
552 : : {
553 : 24 : FILE *fp = fopen (path, "w");
554 : 24 : dump_dot_to_file (fp, dump_args);
555 : 24 : fclose (fp);
556 : 24 : }
557 : :
558 : : /* Return a new json::object of the form
559 : : {"nodes" : [objs for snodes],
560 : : "edges" : [objs for sedges]}. */
561 : :
562 : : std::unique_ptr<json::object>
563 : 0 : supergraph::to_json () const
564 : : {
565 : 0 : auto sgraph_obj = std::make_unique<json::object> ();
566 : :
567 : : /* Nodes. */
568 : 0 : {
569 : 0 : auto nodes_arr = std::make_unique<json::array> ();
570 : 0 : unsigned i;
571 : 0 : supernode *n;
572 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, n)
573 : 0 : nodes_arr->append (n->to_json ());
574 : 0 : sgraph_obj->set ("nodes", std::move (nodes_arr));
575 : 0 : }
576 : :
577 : : /* Edges. */
578 : 0 : {
579 : 0 : auto edges_arr = std::make_unique<json::array> ();
580 : 0 : unsigned i;
581 : 0 : superedge *n;
582 : 0 : FOR_EACH_VEC_ELT (m_edges, i, n)
583 : 0 : edges_arr->append (n->to_json ());
584 : 0 : sgraph_obj->set ("edges", std::move (edges_arr));
585 : 0 : }
586 : :
587 : 0 : return sgraph_obj;
588 : : }
589 : :
590 : : /* Create a supernode within BB within FUN and add it to this supergraph. */
591 : :
592 : : supernode *
593 : 187383 : supergraph::add_node (function *fun, basic_block bb, logger *logger)
594 : : {
595 : 187383 : supernode *n = new supernode (fun, bb, m_next_snode_id++);
596 : 187383 : m_snode_by_id.push_back (n);
597 : 187383 : m_nodes.safe_push (n);
598 : 187383 : if (logger)
599 : 37 : logger->log ("created SN %i", n->m_id);
600 : 187383 : return n;
601 : : }
602 : :
603 : : void
604 : 3297 : supergraph::delete_nodes (const std::set<supernode *> &snodes_to_delete)
605 : : {
606 : : /* Remove nodes from m_nodes. */
607 : 3297 : unsigned read_index, write_index;
608 : 3297 : supernode **elem_ptr;
609 : 190680 : VEC_ORDERED_REMOVE_IF
610 : : (m_nodes, read_index, write_index, elem_ptr,
611 : : snodes_to_delete.find (*elem_ptr) != snodes_to_delete.end ()
612 : 3297 : );
613 : :
614 : : /* Remove nodes from m_snode_by_id, and delete them. */
615 : 8842 : for (auto iter : snodes_to_delete)
616 : : {
617 : 5545 : gcc_assert (iter->m_preds.length () == 0);
618 : 5545 : gcc_assert (iter->m_succs.length () == 0);
619 : 5545 : m_snode_by_id[iter->m_id] = nullptr;
620 : 5545 : delete iter;
621 : : }
622 : 3297 : }
623 : :
624 : : /* Create a chain of nodes and edges in this supergraph from SRC to DEST
625 : : to handle CFG_EDGE in the underlying CFG:
626 : :
627 : : +---+
628 : : |SRC|
629 : : +---+
630 : : |
631 : : | optional edge for ctrlflow_stmt (if CTRLFLOW_STMT is non-null)
632 : : | (e.g. checking conditions on a GIMPLE_COND)
633 : : |
634 : : V
635 : : +------+
636 : : |(node)|
637 : : +------+
638 : : |
639 : : | optional edge for any phi nodes in the destination basic block
640 : : |
641 : : V
642 : : +------+
643 : : |(node)|
644 : : +------+
645 : : |
646 : : | optional edge for state merging at CFG join points
647 : : |
648 : : V
649 : : +----+
650 : : |DEST|
651 : : +----+
652 : :
653 : : adding nodes where necessary between the edges, and adding a no-op edge
654 : : for the case where there is no CTRLFLOW_STMT, phi nodes, or
655 : : state merging. */
656 : :
657 : : void
658 : 55707 : supergraph::add_sedges_for_cfg_edge (supernode *src,
659 : : supernode *dest,
660 : : ::edge cfg_edge,
661 : : gimple *ctrlflow_stmt,
662 : : region_model_manager &mgr,
663 : : logger *logger)
664 : : {
665 : 55707 : log_nesting_level sentinel (logger,
666 : : "edge: bb %i -> bb %i",
667 : 55707 : cfg_edge->src->index,
668 : 55707 : cfg_edge->dest->index);
669 : 55707 : std::unique_ptr<operation> ctrlflow_op;
670 : 55707 : if (ctrlflow_stmt)
671 : 18145 : switch (gimple_code (ctrlflow_stmt))
672 : : {
673 : 0 : default:
674 : 0 : gcc_unreachable ();
675 : 14934 : break;
676 : 14934 : case GIMPLE_COND:
677 : 14934 : ctrlflow_op = std::make_unique<gcond_edge_op>
678 : 29868 : (cfg_edge,
679 : 29868 : *as_a <gcond *> (ctrlflow_stmt));
680 : 14934 : break;
681 : 188 : case GIMPLE_EH_DISPATCH:
682 : 188 : ctrlflow_op
683 : 376 : = eh_dispatch_edge_op::make (src, dest,
684 : : cfg_edge,
685 : 376 : *as_a <geh_dispatch *> (ctrlflow_stmt));
686 : 188 : break;
687 : 32 : case GIMPLE_GOTO:
688 : 32 : {
689 : 32 : ctrlflow_op = std::make_unique<ggoto_edge_op>
690 : 64 : (cfg_edge,
691 : 32 : *as_a <ggoto *> (ctrlflow_stmt),
692 : 64 : dest->m_label);
693 : : }
694 : 32 : break;
695 : 2991 : case GIMPLE_SWITCH:
696 : 2991 : ctrlflow_op = std::make_unique<switch_case_op>
697 : 5982 : (*src->get_function (),
698 : : cfg_edge,
699 : 2991 : *as_a <gswitch *> (ctrlflow_stmt),
700 : 5982 : *mgr.get_range_manager ());
701 : 2991 : break;
702 : : }
703 : : else
704 : : {
705 : 37562 : if (cfg_edge->flags & EDGE_ABNORMAL)
706 : : /* Don't create superedges for such CFG edges (though
707 : : computed gotos are handled by the GIMPLE_GOTO clause above). */
708 : 124 : return;
709 : : }
710 : :
711 : : /* Determine a location to use for any snodes within the CFG edge. */
712 : 55583 : location_t dest_loc = dest->m_loc;
713 : 55583 : if (useful_location_p (cfg_edge->goto_locus))
714 : 17994 : dest_loc = cfg_edge->goto_locus;
715 : :
716 : : /* If the dest is a control flow join point, then for each CFG in-edge
717 : : add an extra snode/sedge before DEST and route to it.
718 : : We hope this will help state-merging keep the
719 : : different in-edges separately. */
720 : 55583 : if (cfg_edge->dest->preds->length () > 1
721 : 55583 : && cfg_edge->dest->index != EXIT_BLOCK)
722 : : {
723 : 16550 : auto extra_snode = add_node (src->get_function (),
724 : : cfg_edge->dest,
725 : : logger);
726 : 16550 : extra_snode->m_loc = dest_loc;
727 : 16550 : extra_snode->m_preserve_p = true;
728 : 16550 : extra_snode->m_state_merger_node = true;
729 : 16550 : add_edge (new superedge (extra_snode, dest, nullptr, nullptr));
730 : 16550 : dest = extra_snode;
731 : : }
732 : :
733 : 55583 : std::unique_ptr<operation> phi_op;
734 : 55583 : if (phi_nodes (cfg_edge->dest))
735 : 15578 : phi_op = phis_for_edge_op::maybe_make (cfg_edge);
736 : 55583 : if (phi_op)
737 : : {
738 : 9208 : superedge *edge_for_phis_op;
739 : 9208 : if (ctrlflow_op)
740 : : {
741 : : /* We have two ops; add an edge for each:
742 : : SRC --{ctrlflow_op}--> before_phi_nodes --{phi_op}--> DEST. */
743 : 1089 : supernode *before_phi_nodes
744 : 1089 : = add_node (src->get_function (), cfg_edge->src, logger);
745 : 1089 : before_phi_nodes->m_loc = dest_loc;
746 : 1089 : add_edge (new superedge (src, before_phi_nodes,
747 : : std::move (ctrlflow_op),
748 : 2178 : cfg_edge));
749 : 2178 : edge_for_phis_op = new superedge (before_phi_nodes, dest,
750 : : std::move (phi_op),
751 : 1089 : cfg_edge);
752 : : }
753 : : else
754 : : /* We just have a phi_op; add: SRC --{phi_op}--> DEST. */
755 : 8119 : edge_for_phis_op
756 : 8119 : = new superedge (src, dest, std::move (phi_op), cfg_edge);
757 : 9208 : add_edge (edge_for_phis_op);
758 : 9208 : m_edges_for_phis.insert ({cfg_edge, edge_for_phis_op});
759 : : }
760 : : else
761 : : /* We don't have a phi op, create this edge:
762 : : SRC --{ctrlflow_op}--> DEST
763 : : where ctrlflow_op might be nullptr (for a no-op edge). */
764 : 46375 : add_edge (new superedge (src, dest, std::move (ctrlflow_op), cfg_edge));
765 : 55720 : }
766 : :
767 : : // class supernode : public dnode<supergraph_traits>
768 : :
769 : : /* Implementation of dnode::dump_dot vfunc for supernodes.
770 : :
771 : : Write a cluster for the node, and within it a .dot node showing
772 : : the phi nodes and stmts. Call into any node annotator from ARGS to
773 : : potentially add other records to the cluster. */
774 : :
775 : : void
776 : 1154 : supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
777 : : {
778 : 1154 : pretty_printer *pp = gv->get_pp ();
779 : :
780 : 1154 : gv->write_indent ();
781 : 1154 : dump_dot_id (pp);
782 : :
783 : 1154 : pp_printf (pp,
784 : : " [shape=none,margin=0,style=filled,label=<");
785 : 1154 : pp_string (pp, "<TABLE BORDER=\"0\">");
786 : 1154 : pp_write_text_to_stream (pp);
787 : :
788 : 1154 : pp_printf (pp, "<TR><TD>sn: %i (bb: %i)",
789 : 1154 : m_id, m_bb->index);
790 : 1154 : if (args.m_eg)
791 : 191 : pp_printf (pp, "; scc: %i", args.m_eg->get_scc_id (*this));
792 : 1154 : pp_string (pp, "</TD></TR>");
793 : 1154 : pp_newline (pp);
794 : :
795 : 1154 : if (m_preserve_p)
796 : : {
797 : 144 : pp_string (pp, "<TR><TD>(preserve)</TD></TR>");
798 : 144 : pp_newline (pp);
799 : : }
800 : 1154 : if (m_state_merger_node)
801 : : {
802 : 566 : pp_string (pp, "<TR><TD BGCOLOR=\"#ec7a08\">"
803 : : "<FONT COLOR=\"white\">STATE MERGER</FONT></TD></TR>");
804 : 566 : pp_newline (pp);
805 : : }
806 : 1154 : if (entry_p ())
807 : : {
808 : 72 : pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
809 : 72 : pp_newline (pp);
810 : : }
811 : 1082 : else if (exit_p ())
812 : : {
813 : 72 : pp_string (pp, "<TR><TD>EXIT</TD></TR>");
814 : 72 : pp_newline (pp);
815 : : }
816 : :
817 : : /* Source location. */
818 : : /* Highlight nodes where we're missing source location information.
819 : : Ideally this all gets fixed up by supergraph::fixup_locations. */
820 : 1154 : if (m_loc == UNKNOWN_LOCATION)
821 : 33 : pp_string (pp, "<TR><TD>UNKNOWN_LOCATION</TD></TR>");
822 : 1121 : else if (get_pure_location (m_loc) == UNKNOWN_LOCATION)
823 : : {
824 : 0 : pp_printf (pp, "<TR><TD>location: 0x%lx</TD></TR>", m_loc);
825 : 0 : pp_string (pp, "<TR><TD>UNKNOWN_LOCATION</TD></TR>");
826 : : }
827 : : else
828 : : {
829 : : /* Show the source location, but skip it for the case where it's
830 : : the same as all previous snodes (and there's a single in-edge). */
831 : 1121 : bool show_location = true;
832 : 1121 : location_t prev_loc = UNKNOWN_LOCATION;
833 : 1121 : if (m_preds.length () == 1)
834 : : {
835 : 977 : prev_loc = m_preds[0]->m_src->m_loc;
836 : 977 : if (prev_loc == m_loc)
837 : : show_location = false;
838 : : }
839 : : if (show_location)
840 : : {
841 : 870 : pp_printf (pp, "<TR><TD>location: 0x%lx</TD></TR>", m_loc);
842 : :
843 : : /* Print changes to the expanded location (or all of it if
844 : : we have multiple in-edges). */
845 : 870 : auto prev_exploc = expand_location (prev_loc);
846 : 870 : auto exploc = expand_location (m_loc);
847 : :
848 : 870 : if ((exploc.file != prev_exploc.file)
849 : 177 : && exploc.file)
850 : : {
851 : 177 : pp_string (pp, "<TR><TD>");
852 : 177 : pp_flush (pp);
853 : 177 : pp_printf (pp, "%s", exploc.file);
854 : : /* Escape, to handle cases like "<built-in>". */
855 : 177 : pp_write_text_as_html_like_dot_to_stream (pp);
856 : 177 : pp_printf (pp, ":%i:</TD></TR>", exploc.line);
857 : : }
858 : 870 : if (exploc.line != prev_exploc.line)
859 : 1120 : if (const diagnostics::char_span line
860 : 560 : = global_dc->get_file_cache ().get_source_line (exploc.file,
861 : 560 : exploc.line))
862 : : {
863 : : /* Print the source line. */
864 : 560 : pp_string (pp, "<TR><TD>");
865 : 560 : pp_string (pp, "<TABLE BORDER=\"0\"><TR>");
866 : :
867 : : // Line number:
868 : 560 : pp_printf (pp, ("<TD ALIGN=\"RIGHT\" BGCOLOR=\"#0088ce\">"
869 : : "<FONT COLOR=\"white\"> %i</FONT></TD>"),
870 : : exploc.line);
871 : :
872 : : // Line contents:
873 : 560 : pp_string (pp, "<TD ALIGN=\"LEFT\" BGCOLOR=\"white\">");
874 : 560 : pp_flush (pp);
875 : 12002 : for (size_t i = 0; i < line.length (); ++i)
876 : 11442 : pp_character (pp, line[i]);
877 : 560 : pp_write_text_as_html_like_dot_to_stream (pp);
878 : 560 : pp_string (pp, "</TD>");
879 : :
880 : 560 : pp_string (pp, "</TR></TABLE>");
881 : 560 : pp_string (pp, "</TD></TR>");
882 : : }
883 : : }
884 : : }
885 : :
886 : 1154 : pp_flush (pp);
887 : :
888 : 1154 : if (args.m_node_annotator)
889 : 382 : args.m_node_annotator->add_node_annotations (gv, *this);
890 : :
891 : 1154 : pp_printf (pp, "<TR><TD>m_stmt_loc: 0x%lx</TD></TR>", m_stmt_loc);
892 : :
893 : 1154 : pp_string (pp, "</TABLE>>];\n\n");
894 : 1154 : pp_flush (pp);
895 : 1154 : }
896 : :
897 : : /* Write an ID for this node to PP, for use in .dot output. */
898 : :
899 : : void
900 : 3462 : supernode::dump_dot_id (pretty_printer *pp) const
901 : : {
902 : 3462 : pp_printf (pp, "node_%i", m_id);
903 : 3462 : }
904 : :
905 : : /* Return a new json::object of the form
906 : : {"id": int,
907 : : "fun": optional str
908 : : "bb_idx": int}. */
909 : :
910 : : std::unique_ptr<json::object>
911 : 0 : supernode::to_json () const
912 : : {
913 : 0 : auto snode_obj = std::make_unique<json::object> ();
914 : :
915 : 0 : snode_obj->set_integer ("id", m_id);
916 : 0 : snode_obj->set_integer ("bb_idx", m_bb->index);
917 : 0 : if (function *fun = get_function ())
918 : 0 : snode_obj->set_string ("fun", function_name (fun));
919 : :
920 : 0 : return snode_obj;
921 : : }
922 : :
923 : : /* Dump this superedge to PP. */
924 : :
925 : : void
926 : 0 : superedge::dump (pretty_printer *pp) const
927 : : {
928 : 0 : pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_id, m_dest->m_id);
929 : 0 : label_text desc (get_description (false));
930 : 0 : if (strlen (desc.get ()) > 0)
931 : : {
932 : 0 : pp_space (pp);
933 : 0 : pp_string (pp, desc.get ());
934 : : }
935 : 0 : }
936 : :
937 : : /* Dump this superedge to stderr. */
938 : :
939 : : DEBUG_FUNCTION void
940 : 0 : superedge::dump () const
941 : : {
942 : 0 : tree_dump_pretty_printer pp (stderr);
943 : 0 : dump (&pp);
944 : 0 : pp_newline (&pp);
945 : 0 : }
946 : :
947 : : /* Implementation of dedge::dump_dot for superedges.
948 : : Write a .dot edge to GV representing this superedge. */
949 : :
950 : : void
951 : 1154 : superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
952 : : {
953 : 1154 : const char *style = "\"solid,bold\"";
954 : 1154 : const char *color = "black";
955 : 1154 : int weight = 10;
956 : 1154 : const char *constraint = "true";
957 : :
958 : : /* Adapted from graph.cc:draw_cfg_node_succ_edges. */
959 : 1154 : if (::edge cfg_edge = get_any_cfg_edge ())
960 : : {
961 : 422 : if (cfg_edge->flags & EDGE_FAKE)
962 : : {
963 : : style = "dotted";
964 : : color = "green";
965 : : weight = 0;
966 : : }
967 : 422 : else if (cfg_edge->flags & EDGE_DFS_BACK)
968 : : {
969 : : style = "\"dotted,bold\"";
970 : : color = "blue";
971 : : weight = 10;
972 : : }
973 : 374 : else if (cfg_edge->flags & EDGE_FALLTHRU)
974 : : {
975 : 182 : color = "blue";
976 : 182 : weight = 100;
977 : : }
978 : :
979 : 422 : if (cfg_edge->flags & EDGE_ABNORMAL)
980 : 0 : color = "red";
981 : : }
982 : :
983 : 1154 : gv->write_indent ();
984 : :
985 : 1154 : pretty_printer *pp = gv->get_pp ();
986 : :
987 : 1154 : m_src->dump_dot_id (pp);
988 : 1154 : pp_string (pp, " -> ");
989 : 1154 : m_dest->dump_dot_id (pp);
990 : 1154 : pp_printf (pp,
991 : : (" [style=%s, color=%s, weight=%d, constraint=%s,"
992 : : " headlabel=\""),
993 : : style, color, weight, constraint);
994 : 1154 : pp_flush (pp);
995 : :
996 : 1154 : dump_label_to_pp (pp, false);
997 : 1154 : pp_write_text_as_dot_label_to_stream (pp, false);
998 : :
999 : 1154 : pp_printf (pp, "\"];\n");
1000 : 1154 : }
1001 : :
1002 : : /* Return a new json::object of the form
1003 : : {"src_id": int, the index of the source supernode,
1004 : : "dst_id": int, the index of the destination supernode} */
1005 : :
1006 : : std::unique_ptr<json::object>
1007 : 49 : superedge::to_json () const
1008 : : {
1009 : 49 : auto sedge_obj = std::make_unique<json::object> ();
1010 : 49 : sedge_obj->set_integer ("src_id", m_src->m_id);
1011 : 49 : sedge_obj->set_integer ("dst_id", m_dest->m_id);
1012 : 49 : return sedge_obj;
1013 : : }
1014 : :
1015 : : /* Return true iff this edge needs to be preserved during simplification. */
1016 : :
1017 : : bool
1018 : 161707 : superedge::preserve_p () const
1019 : : {
1020 : 161707 : if (m_cfg_edge)
1021 : 42138 : if (m_cfg_edge->flags & (EDGE_EH | EDGE_DFS_BACK))
1022 : : {
1023 : : /* We use EDGE_EH in get_eh_outedge, and EDGE_DFS_BACK
1024 : : for detecting infinite loops. */
1025 : 1688 : return true;
1026 : : }
1027 : : return false;
1028 : : }
1029 : :
1030 : : /* Build a description of this superedge (e.g. "true" for the true
1031 : : edge of a conditional, or "case 42:" for a switch case).
1032 : :
1033 : : If USER_FACING is false, the result also contains any underlying
1034 : : CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)". */
1035 : :
1036 : : label_text
1037 : 7555 : superedge::get_description (bool user_facing) const
1038 : : {
1039 : 7555 : pretty_printer pp;
1040 : 7555 : pp_format_decoder (&pp) = default_tree_printer;
1041 : 7555 : dump_label_to_pp (&pp, user_facing);
1042 : 7555 : return label_text::take (xstrdup (pp_formatted_text (&pp)));
1043 : 7555 : }
1044 : :
1045 : : void
1046 : 9248 : superedge::dump_label_to_pp (pretty_printer *pp, bool user_facing) const
1047 : : {
1048 : 9248 : if (get_op ())
1049 : 8731 : get_op ()->print_as_edge_label (pp, user_facing);
1050 : : else
1051 : 517 : pp_printf (pp, "no-op");
1052 : :
1053 : 9248 : if (user_facing)
1054 : : return;
1055 : :
1056 : 1871 : if (::edge cfg_edge = get_any_cfg_edge ())
1057 : : {
1058 : 620 : if (cfg_edge->flags)
1059 : : {
1060 : 523 : pp_string (pp, " (flags ");
1061 : 523 : bool seen_flag = false;
1062 : : #define DEF_EDGE_FLAG(NAME,IDX) \
1063 : : do { \
1064 : : if (cfg_edge->flags & EDGE_##NAME) \
1065 : : { \
1066 : : if (seen_flag) \
1067 : : pp_string (pp, " | "); \
1068 : : pp_printf (pp, "%s", (#NAME)); \
1069 : : seen_flag = true; \
1070 : : } \
1071 : : } while (0);
1072 : : #include "cfg-flags.def"
1073 : : #undef DEF_EDGE_FLAG
1074 : 523 : pp_string (pp, ")");
1075 : : }
1076 : 620 : if (cfg_edge->goto_locus > BUILTINS_LOCATION)
1077 : 248 : pp_printf (pp, " (has goto_locus: 0x%lx)", cfg_edge->goto_locus);
1078 : : }
1079 : : }
1080 : :
1081 : : bool
1082 : 116351 : superedge::supports_bulk_merge_p () const
1083 : : {
1084 : 116351 : if (!m_op)
1085 : : return true;
1086 : 63378 : return m_op->supports_bulk_merge_p ();
1087 : : }
1088 : :
1089 : : } // namespace ana
1090 : :
1091 : : #endif /* #if ENABLE_ANALYZER */
|
