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